Line data Source code
1 : //===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
11 : //
12 : // Software pipelining (SWP) is an instruction scheduling technique for loops
13 : // that overlap loop iterations and exploits ILP via a compiler transformation.
14 : //
15 : // Swing Modulo Scheduling is an implementation of software pipelining
16 : // that generates schedules that are near optimal in terms of initiation
17 : // interval, register requirements, and stage count. See the papers:
18 : //
19 : // "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa,
20 : // A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996
21 : // Conference on Parallel Architectures and Compilation Techiniques.
22 : //
23 : // "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J.
24 : // Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE
25 : // Transactions on Computers, Vol. 50, No. 3, 2001.
26 : //
27 : // "An Implementation of Swing Modulo Scheduling With Extensions for
28 : // Superblocks", by T. Lattner, Master's Thesis, University of Illinois at
29 : // Urbana-Chambpain, 2005.
30 : //
31 : //
32 : // The SMS algorithm consists of three main steps after computing the minimal
33 : // initiation interval (MII).
34 : // 1) Analyze the dependence graph and compute information about each
35 : // instruction in the graph.
36 : // 2) Order the nodes (instructions) by priority based upon the heuristics
37 : // described in the algorithm.
38 : // 3) Attempt to schedule the nodes in the specified order using the MII.
39 : //
40 : // This SMS implementation is a target-independent back-end pass. When enabled,
41 : // the pass runs just prior to the register allocation pass, while the machine
42 : // IR is in SSA form. If software pipelining is successful, then the original
43 : // loop is replaced by the optimized loop. The optimized loop contains one or
44 : // more prolog blocks, the pipelined kernel, and one or more epilog blocks. If
45 : // the instructions cannot be scheduled in a given MII, we increase the MII by
46 : // one and try again.
47 : //
48 : // The SMS implementation is an extension of the ScheduleDAGInstrs class. We
49 : // represent loop carried dependences in the DAG as order edges to the Phi
50 : // nodes. We also perform several passes over the DAG to eliminate unnecessary
51 : // edges that inhibit the ability to pipeline. The implementation uses the
52 : // DFAPacketizer class to compute the minimum initiation interval and the check
53 : // where an instruction may be inserted in the pipelined schedule.
54 : //
55 : // In order for the SMS pass to work, several target specific hooks need to be
56 : // implemented to get information about the loop structure and to rewrite
57 : // instructions.
58 : //
59 : //===----------------------------------------------------------------------===//
60 :
61 : #include "llvm/ADT/ArrayRef.h"
62 : #include "llvm/ADT/BitVector.h"
63 : #include "llvm/ADT/DenseMap.h"
64 : #include "llvm/ADT/MapVector.h"
65 : #include "llvm/ADT/PriorityQueue.h"
66 : #include "llvm/ADT/SetVector.h"
67 : #include "llvm/ADT/SmallPtrSet.h"
68 : #include "llvm/ADT/SmallSet.h"
69 : #include "llvm/ADT/SmallVector.h"
70 : #include "llvm/ADT/Statistic.h"
71 : #include "llvm/ADT/iterator_range.h"
72 : #include "llvm/Analysis/AliasAnalysis.h"
73 : #include "llvm/Analysis/MemoryLocation.h"
74 : #include "llvm/Analysis/ValueTracking.h"
75 : #include "llvm/CodeGen/DFAPacketizer.h"
76 : #include "llvm/CodeGen/LiveIntervals.h"
77 : #include "llvm/CodeGen/MachineBasicBlock.h"
78 : #include "llvm/CodeGen/MachineDominators.h"
79 : #include "llvm/CodeGen/MachineFunction.h"
80 : #include "llvm/CodeGen/MachineFunctionPass.h"
81 : #include "llvm/CodeGen/MachineInstr.h"
82 : #include "llvm/CodeGen/MachineInstrBuilder.h"
83 : #include "llvm/CodeGen/MachineLoopInfo.h"
84 : #include "llvm/CodeGen/MachineMemOperand.h"
85 : #include "llvm/CodeGen/MachineOperand.h"
86 : #include "llvm/CodeGen/MachineRegisterInfo.h"
87 : #include "llvm/CodeGen/RegisterClassInfo.h"
88 : #include "llvm/CodeGen/RegisterPressure.h"
89 : #include "llvm/CodeGen/ScheduleDAG.h"
90 : #include "llvm/CodeGen/ScheduleDAGInstrs.h"
91 : #include "llvm/CodeGen/ScheduleDAGMutation.h"
92 : #include "llvm/CodeGen/TargetInstrInfo.h"
93 : #include "llvm/CodeGen/TargetOpcodes.h"
94 : #include "llvm/CodeGen/TargetRegisterInfo.h"
95 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
96 : #include "llvm/Config/llvm-config.h"
97 : #include "llvm/IR/Attributes.h"
98 : #include "llvm/IR/DebugLoc.h"
99 : #include "llvm/IR/Function.h"
100 : #include "llvm/MC/LaneBitmask.h"
101 : #include "llvm/MC/MCInstrDesc.h"
102 : #include "llvm/MC/MCInstrItineraries.h"
103 : #include "llvm/MC/MCRegisterInfo.h"
104 : #include "llvm/Pass.h"
105 : #include "llvm/Support/Casting.h"
106 : #include "llvm/Support/CommandLine.h"
107 : #include "llvm/Support/Compiler.h"
108 : #include "llvm/Support/Debug.h"
109 : #include "llvm/Support/MathExtras.h"
110 : #include "llvm/Support/raw_ostream.h"
111 : #include <algorithm>
112 : #include <cassert>
113 : #include <climits>
114 : #include <cstdint>
115 : #include <deque>
116 : #include <functional>
117 : #include <iterator>
118 : #include <map>
119 : #include <memory>
120 : #include <tuple>
121 : #include <utility>
122 : #include <vector>
123 :
124 : using namespace llvm;
125 :
126 : #define DEBUG_TYPE "pipeliner"
127 :
128 : STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline");
129 : STATISTIC(NumPipelined, "Number of loops software pipelined");
130 : STATISTIC(NumNodeOrderIssues, "Number of node order issues found");
131 :
132 : /// A command line option to turn software pipelining on or off.
133 : static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true),
134 : cl::ZeroOrMore,
135 : cl::desc("Enable Software Pipelining"));
136 :
137 : /// A command line option to enable SWP at -Os.
138 : static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size",
139 : cl::desc("Enable SWP at Os."), cl::Hidden,
140 : cl::init(false));
141 :
142 : /// A command line argument to limit minimum initial interval for pipelining.
143 : static cl::opt<int> SwpMaxMii("pipeliner-max-mii",
144 : cl::desc("Size limit for the MII."),
145 : cl::Hidden, cl::init(27));
146 :
147 : /// A command line argument to limit the number of stages in the pipeline.
148 : static cl::opt<int>
149 : SwpMaxStages("pipeliner-max-stages",
150 : cl::desc("Maximum stages allowed in the generated scheduled."),
151 : cl::Hidden, cl::init(3));
152 :
153 : /// A command line option to disable the pruning of chain dependences due to
154 : /// an unrelated Phi.
155 : static cl::opt<bool>
156 : SwpPruneDeps("pipeliner-prune-deps",
157 : cl::desc("Prune dependences between unrelated Phi nodes."),
158 : cl::Hidden, cl::init(true));
159 :
160 : /// A command line option to disable the pruning of loop carried order
161 : /// dependences.
162 : static cl::opt<bool>
163 : SwpPruneLoopCarried("pipeliner-prune-loop-carried",
164 : cl::desc("Prune loop carried order dependences."),
165 : cl::Hidden, cl::init(true));
166 :
167 : #ifndef NDEBUG
168 : static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
169 : #endif
170 :
171 : static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
172 : cl::ReallyHidden, cl::init(false),
173 : cl::ZeroOrMore, cl::desc("Ignore RecMII"));
174 :
175 : // A command line option to enable the CopyToPhi DAG mutation.
176 : static cl::opt<bool>
177 : SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
178 : cl::init(true), cl::ZeroOrMore,
179 : cl::desc("Enable CopyToPhi DAG Mutation"));
180 :
181 : namespace {
182 :
183 : class NodeSet;
184 : class SMSchedule;
185 :
186 : /// The main class in the implementation of the target independent
187 : /// software pipeliner pass.
188 : class MachinePipeliner : public MachineFunctionPass {
189 : public:
190 : MachineFunction *MF = nullptr;
191 : const MachineLoopInfo *MLI = nullptr;
192 : const MachineDominatorTree *MDT = nullptr;
193 : const InstrItineraryData *InstrItins;
194 : const TargetInstrInfo *TII = nullptr;
195 : RegisterClassInfo RegClassInfo;
196 :
197 : #ifndef NDEBUG
198 : static int NumTries;
199 : #endif
200 :
201 : /// Cache the target analysis information about the loop.
202 843 : struct LoopInfo {
203 : MachineBasicBlock *TBB = nullptr;
204 : MachineBasicBlock *FBB = nullptr;
205 : SmallVector<MachineOperand, 4> BrCond;
206 : MachineInstr *LoopInductionVar = nullptr;
207 : MachineInstr *LoopCompare = nullptr;
208 : };
209 : LoopInfo LI;
210 :
211 : static char ID;
212 :
213 843 : MachinePipeliner() : MachineFunctionPass(ID) {
214 843 : initializeMachinePipelinerPass(*PassRegistry::getPassRegistry());
215 843 : }
216 :
217 : bool runOnMachineFunction(MachineFunction &MF) override;
218 :
219 836 : void getAnalysisUsage(AnalysisUsage &AU) const override {
220 : AU.addRequired<AAResultsWrapperPass>();
221 : AU.addPreserved<AAResultsWrapperPass>();
222 : AU.addRequired<MachineLoopInfo>();
223 : AU.addRequired<MachineDominatorTree>();
224 : AU.addRequired<LiveIntervals>();
225 836 : MachineFunctionPass::getAnalysisUsage(AU);
226 836 : }
227 :
228 : private:
229 : void preprocessPhiNodes(MachineBasicBlock &B);
230 : bool canPipelineLoop(MachineLoop &L);
231 : bool scheduleLoop(MachineLoop &L);
232 : bool swingModuloScheduler(MachineLoop &L);
233 : };
234 :
235 : /// This class builds the dependence graph for the instructions in a loop,
236 : /// and attempts to schedule the instructions using the SMS algorithm.
237 : class SwingSchedulerDAG : public ScheduleDAGInstrs {
238 : MachinePipeliner &Pass;
239 : /// The minimum initiation interval between iterations for this schedule.
240 : unsigned MII = 0;
241 : /// Set to true if a valid pipelined schedule is found for the loop.
242 : bool Scheduled = false;
243 : MachineLoop &Loop;
244 : LiveIntervals &LIS;
245 : const RegisterClassInfo &RegClassInfo;
246 :
247 : /// A toplogical ordering of the SUnits, which is needed for changing
248 : /// dependences and iterating over the SUnits.
249 : ScheduleDAGTopologicalSort Topo;
250 :
251 : struct NodeInfo {
252 : int ASAP = 0;
253 : int ALAP = 0;
254 : int ZeroLatencyDepth = 0;
255 : int ZeroLatencyHeight = 0;
256 :
257 : NodeInfo() = default;
258 : };
259 : /// Computed properties for each node in the graph.
260 : std::vector<NodeInfo> ScheduleInfo;
261 :
262 : enum OrderKind { BottomUp = 0, TopDown = 1 };
263 : /// Computed node ordering for scheduling.
264 : SetVector<SUnit *> NodeOrder;
265 :
266 : using NodeSetType = SmallVector<NodeSet, 8>;
267 : using ValueMapTy = DenseMap<unsigned, unsigned>;
268 : using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>;
269 : using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>;
270 :
271 : /// Instructions to change when emitting the final schedule.
272 : DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
273 :
274 : /// We may create a new instruction, so remember it because it
275 : /// must be deleted when the pass is finished.
276 : SmallPtrSet<MachineInstr *, 4> NewMIs;
277 :
278 : /// Ordered list of DAG postprocessing steps.
279 : std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
280 :
281 : /// Helper class to implement Johnson's circuit finding algorithm.
282 : class Circuits {
283 : std::vector<SUnit> &SUnits;
284 : SetVector<SUnit *> Stack;
285 : BitVector Blocked;
286 : SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
287 : SmallVector<SmallVector<int, 4>, 16> AdjK;
288 : // Node to Index from ScheduleDAGTopologicalSort
289 : std::vector<int> *Node2Idx;
290 : unsigned NumPaths;
291 : static unsigned MaxPaths;
292 :
293 : public:
294 190 : Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo)
295 570 : : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {
296 380 : Node2Idx = new std::vector<int>(SUs.size());
297 : unsigned Idx = 0;
298 2201 : for (const auto &NodeNum : Topo)
299 2011 : Node2Idx->at(NodeNum) = Idx++;
300 190 : }
301 :
302 380 : ~Circuits() { delete Node2Idx; }
303 :
304 : /// Reset the data structures used in the circuit algorithm.
305 2011 : void reset() {
306 : Stack.clear();
307 : Blocked.reset();
308 6033 : B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
309 2011 : NumPaths = 0;
310 2011 : }
311 :
312 : void createAdjacencyStructure(SwingSchedulerDAG *DAG);
313 : bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
314 : void unblock(int U);
315 : };
316 :
317 190 : struct CopyToPhiMutation : public ScheduleDAGMutation {
318 : void apply(ScheduleDAGInstrs *DAG) override;
319 : };
320 :
321 : public:
322 190 : SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis,
323 : const RegisterClassInfo &rci)
324 380 : : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
325 380 : RegClassInfo(rci), Topo(SUnits, &ExitSU) {
326 190 : P.MF->getSubtarget().getSMSMutations(Mutations);
327 190 : if (SwpEnableCopyToPhi)
328 190 : Mutations.push_back(llvm::make_unique<CopyToPhiMutation>());
329 190 : }
330 :
331 : void schedule() override;
332 : void finishBlock() override;
333 :
334 : /// Return true if the loop kernel has been scheduled.
335 0 : bool hasNewSchedule() { return Scheduled; }
336 :
337 : /// Return the earliest time an instruction may be scheduled.
338 10092 : int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; }
339 :
340 : /// Return the latest time an instruction my be scheduled.
341 8948 : int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; }
342 :
343 : /// The mobility function, which the number of slots in which
344 : /// an instruction may be scheduled.
345 4582 : int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); }
346 :
347 : /// The depth, in the dependence graph, for a node.
348 0 : unsigned getDepth(SUnit *Node) { return Node->getDepth(); }
349 :
350 : /// The maximum unweighted length of a path from an arbitrary node to the
351 : /// given node in which each edge has latency 0
352 0 : int getZeroLatencyDepth(SUnit *Node) {
353 8440 : return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth;
354 : }
355 :
356 : /// The height, in the dependence graph, for a node.
357 0 : unsigned getHeight(SUnit *Node) { return Node->getHeight(); }
358 :
359 : /// The maximum unweighted length of a path from the given node to an
360 : /// arbitrary node in which each edge has latency 0
361 0 : int getZeroLatencyHeight(SUnit *Node) {
362 5940 : return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight;
363 : }
364 :
365 : /// Return true if the dependence is a back-edge in the data dependence graph.
366 : /// Since the DAG doesn't contain cycles, we represent a cycle in the graph
367 : /// using an anti dependence from a Phi to an instruction.
368 0 : bool isBackedge(SUnit *Source, const SDep &Dep) {
369 0 : if (Dep.getKind() != SDep::Anti)
370 0 : return false;
371 0 : return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI();
372 : }
373 :
374 : bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true);
375 :
376 : /// The distance function, which indicates that operation V of iteration I
377 : /// depends on operations U of iteration I-distance.
378 0 : unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
379 : // Instructions that feed a Phi have a distance of 1. Computing larger
380 : // values for arrays requires data dependence information.
381 436 : if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
382 0 : return 1;
383 : return 0;
384 : }
385 :
386 : /// Set the Minimum Initiation Interval for this schedule attempt.
387 : void setMII(unsigned mii) { MII = mii; }
388 :
389 : void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
390 :
391 : void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
392 :
393 : /// Return the new base register that was stored away for the changed
394 : /// instruction.
395 : unsigned getInstrBaseReg(SUnit *SU) {
396 : DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
397 434 : InstrChanges.find(SU);
398 434 : if (It != InstrChanges.end())
399 53 : return It->second.first;
400 : return 0;
401 : }
402 :
403 : void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
404 : Mutations.push_back(std::move(Mutation));
405 : }
406 :
407 : static bool classof(const ScheduleDAGInstrs *DAG) { return true; }
408 :
409 : private:
410 : void addLoopCarriedDependences(AliasAnalysis *AA);
411 : void updatePhiDependences();
412 : void changeDependences();
413 : unsigned calculateResMII();
414 : unsigned calculateRecMII(NodeSetType &RecNodeSets);
415 : void findCircuits(NodeSetType &NodeSets);
416 : void fuseRecs(NodeSetType &NodeSets);
417 : void removeDuplicateNodes(NodeSetType &NodeSets);
418 : void computeNodeFunctions(NodeSetType &NodeSets);
419 : void registerPressureFilter(NodeSetType &NodeSets);
420 : void colocateNodeSets(NodeSetType &NodeSets);
421 : void checkNodeSets(NodeSetType &NodeSets);
422 : void groupRemainingNodes(NodeSetType &NodeSets);
423 : void addConnectedNodes(SUnit *SU, NodeSet &NewSet,
424 : SetVector<SUnit *> &NodesAdded);
425 : void computeNodeOrder(NodeSetType &NodeSets);
426 : void checkValidNodeOrder(const NodeSetType &Circuits) const;
427 : bool schedulePipeline(SMSchedule &Schedule);
428 : void generatePipelinedLoop(SMSchedule &Schedule);
429 : void generateProlog(SMSchedule &Schedule, unsigned LastStage,
430 : MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
431 : MBBVectorTy &PrologBBs);
432 : void generateEpilog(SMSchedule &Schedule, unsigned LastStage,
433 : MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
434 : MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs);
435 : void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
436 : MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
437 : SMSchedule &Schedule, ValueMapTy *VRMap,
438 : InstrMapTy &InstrMap, unsigned LastStageNum,
439 : unsigned CurStageNum, bool IsLast);
440 : void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
441 : MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
442 : SMSchedule &Schedule, ValueMapTy *VRMap,
443 : InstrMapTy &InstrMap, unsigned LastStageNum,
444 : unsigned CurStageNum, bool IsLast);
445 : void removeDeadInstructions(MachineBasicBlock *KernelBB,
446 : MBBVectorTy &EpilogBBs);
447 : void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
448 : SMSchedule &Schedule);
449 : void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB,
450 : MBBVectorTy &EpilogBBs, SMSchedule &Schedule,
451 : ValueMapTy *VRMap);
452 : bool computeDelta(MachineInstr &MI, unsigned &Delta);
453 : void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
454 : unsigned Num);
455 : MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
456 : unsigned InstStageNum);
457 : MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
458 : unsigned InstStageNum,
459 : SMSchedule &Schedule);
460 : void updateInstruction(MachineInstr *NewMI, bool LastDef,
461 : unsigned CurStageNum, unsigned InstrStageNum,
462 : SMSchedule &Schedule, ValueMapTy *VRMap);
463 : MachineInstr *findDefInLoop(unsigned Reg);
464 : unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
465 : unsigned LoopStage, ValueMapTy *VRMap,
466 : MachineBasicBlock *BB);
467 : void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
468 : SMSchedule &Schedule, ValueMapTy *VRMap,
469 : InstrMapTy &InstrMap);
470 : void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule,
471 : InstrMapTy &InstrMap, unsigned CurStageNum,
472 : unsigned PhiNum, MachineInstr *Phi,
473 : unsigned OldReg, unsigned NewReg,
474 : unsigned PrevReg = 0);
475 : bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
476 : unsigned &OffsetPos, unsigned &NewBase,
477 : int64_t &NewOffset);
478 : void postprocessDAG();
479 : };
480 :
481 : /// A NodeSet contains a set of SUnit DAG nodes with additional information
482 : /// that assigns a priority to the set.
483 3324 : class NodeSet {
484 : SetVector<SUnit *> Nodes;
485 : bool HasRecurrence = false;
486 : unsigned RecMII = 0;
487 : int MaxMOV = 0;
488 : unsigned MaxDepth = 0;
489 : unsigned Colocate = 0;
490 : SUnit *ExceedPressure = nullptr;
491 : unsigned Latency = 0;
492 :
493 : public:
494 : using iterator = SetVector<SUnit *>::const_iterator;
495 :
496 188 : NodeSet() = default;
497 578 : NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
498 : Latency = 0;
499 2492 : for (unsigned i = 0, e = Nodes.size(); i < e; ++i)
500 6963 : for (const SDep &Succ : Nodes[i]->Succs)
501 3135 : if (Nodes.count(Succ.getSUnit()))
502 1946 : Latency += Succ.getLatency();
503 578 : }
504 :
505 545 : bool insert(SUnit *SU) { return Nodes.insert(SU); }
506 :
507 83 : void insert(iterator S, iterator E) { Nodes.insert(S, E); }
508 :
509 : template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
510 0 : return Nodes.remove_if(P);
511 : }
512 :
513 : unsigned count(SUnit *SU) const { return Nodes.count(SU); }
514 :
515 : bool hasRecurrence() { return HasRecurrence; };
516 :
517 420 : unsigned size() const { return Nodes.size(); }
518 :
519 : bool empty() const { return Nodes.empty(); }
520 :
521 1 : SUnit *getNode(unsigned i) const { return Nodes[i]; };
522 :
523 0 : void setRecMII(unsigned mii) { RecMII = mii; };
524 :
525 0 : void setColocate(unsigned c) { Colocate = c; };
526 :
527 1 : void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
528 :
529 0 : bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
530 :
531 0 : int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
532 :
533 0 : int getRecMII() { return RecMII; }
534 :
535 : /// Summarize node functions for the entire node set.
536 420 : void computeNodeSetInfo(SwingSchedulerDAG *SSD) {
537 1656 : for (SUnit *SU : *this) {
538 1519 : MaxMOV = std::max(MaxMOV, SSD->getMOV(SU));
539 1890 : MaxDepth = std::max(MaxDepth, SSD->getDepth(SU));
540 : }
541 420 : }
542 :
543 0 : unsigned getLatency() { return Latency; }
544 :
545 0 : unsigned getMaxDepth() { return MaxDepth; }
546 :
547 : void clear() {
548 : Nodes.clear();
549 197 : RecMII = 0;
550 197 : HasRecurrence = false;
551 197 : MaxMOV = 0;
552 197 : MaxDepth = 0;
553 197 : Colocate = 0;
554 197 : ExceedPressure = nullptr;
555 : }
556 :
557 420 : operator SetVector<SUnit *> &() { return Nodes; }
558 :
559 : /// Sort the node sets by importance. First, rank them by recurrence MII,
560 : /// then by mobility (least mobile done first), and finally by depth.
561 : /// Each node set may contain a colocate value which is used as the first
562 : /// tie breaker, if it's set.
563 : bool operator>(const NodeSet &RHS) const {
564 0 : if (RecMII == RHS.RecMII) {
565 0 : if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
566 0 : return Colocate < RHS.Colocate;
567 0 : if (MaxMOV == RHS.MaxMOV)
568 0 : return MaxDepth > RHS.MaxDepth;
569 0 : return MaxMOV < RHS.MaxMOV;
570 : }
571 0 : return RecMII > RHS.RecMII;
572 : }
573 :
574 : bool operator==(const NodeSet &RHS) const {
575 : return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
576 : MaxDepth == RHS.MaxDepth;
577 : }
578 :
579 : bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
580 :
581 : iterator begin() { return Nodes.begin(); }
582 : iterator end() { return Nodes.end(); }
583 :
584 : void print(raw_ostream &os) const {
585 : os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
586 : << " depth " << MaxDepth << " col " << Colocate << "\n";
587 : for (const auto &I : Nodes)
588 : os << " SU(" << I->NodeNum << ") " << *(I->getInstr());
589 : os << "\n";
590 : }
591 :
592 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
593 : LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
594 : #endif
595 : };
596 :
597 : /// This class represents the scheduled code. The main data structure is a
598 : /// map from scheduled cycle to instructions. During scheduling, the
599 : /// data structure explicitly represents all stages/iterations. When
600 : /// the algorithm finshes, the schedule is collapsed into a single stage,
601 : /// which represents instructions from different loop iterations.
602 : ///
603 : /// The SMS algorithm allows negative values for cycles, so the first cycle
604 : /// in the schedule is the smallest cycle value.
605 : class SMSchedule {
606 : private:
607 : /// Map from execution cycle to instructions.
608 : DenseMap<int, std::deque<SUnit *>> ScheduledInstrs;
609 :
610 : /// Map from instruction to execution cycle.
611 : std::map<SUnit *, int> InstrToCycle;
612 :
613 : /// Map for each register and the max difference between its uses and def.
614 : /// The first element in the pair is the max difference in stages. The
615 : /// second is true if the register defines a Phi value and loop value is
616 : /// scheduled before the Phi.
617 : std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
618 :
619 : /// Keep track of the first cycle value in the schedule. It starts
620 : /// as zero, but the algorithm allows negative values.
621 : int FirstCycle = 0;
622 :
623 : /// Keep track of the last cycle value in the schedule.
624 : int LastCycle = 0;
625 :
626 : /// The initiation interval (II) for the schedule.
627 : int InitiationInterval = 0;
628 :
629 : /// Target machine information.
630 : const TargetSubtargetInfo &ST;
631 :
632 : /// Virtual register information.
633 : MachineRegisterInfo &MRI;
634 :
635 : std::unique_ptr<DFAPacketizer> Resources;
636 :
637 : public:
638 188 : SMSchedule(MachineFunction *mf)
639 564 : : ST(mf->getSubtarget()), MRI(mf->getRegInfo()),
640 188 : Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) {}
641 :
642 277 : void reset() {
643 277 : ScheduledInstrs.clear();
644 : InstrToCycle.clear();
645 : RegToStageDiff.clear();
646 277 : FirstCycle = 0;
647 277 : LastCycle = 0;
648 277 : InitiationInterval = 0;
649 277 : }
650 :
651 : /// Set the initiation interval for this schedule.
652 272 : void setInitiationInterval(int ii) { InitiationInterval = ii; }
653 :
654 : /// Return the first cycle in the completed schedule. This
655 : /// can be a negative value.
656 0 : int getFirstCycle() const { return FirstCycle; }
657 :
658 : /// Return the last cycle in the finalized schedule.
659 1150 : int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; }
660 :
661 : /// Return the cycle of the earliest scheduled instruction in the dependence
662 : /// chain.
663 : int earliestCycleInChain(const SDep &Dep);
664 :
665 : /// Return the cycle of the latest scheduled instruction in the dependence
666 : /// chain.
667 : int latestCycleInChain(const SDep &Dep);
668 :
669 : void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
670 : int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG);
671 : bool insert(SUnit *SU, int StartCycle, int EndCycle, int II);
672 :
673 : /// Iterators for the cycle to instruction map.
674 : using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator;
675 : using const_sched_iterator =
676 : DenseMap<int, std::deque<SUnit *>>::const_iterator;
677 :
678 : /// Return true if the instruction is scheduled at the specified stage.
679 4788 : bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
680 4788 : return (stageScheduled(SU) == (int)StageNum);
681 : }
682 :
683 : /// Return the stage for a scheduled instruction. Return -1 if
684 : /// the instruction has not been scheduled.
685 : int stageScheduled(SUnit *SU) const {
686 : std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
687 29593 : if (it == InstrToCycle.end())
688 : return -1;
689 28080 : return (it->second - FirstCycle) / InitiationInterval;
690 : }
691 :
692 : /// Return the cycle for a scheduled instruction. This function normalizes
693 : /// the first cycle to be 0.
694 : unsigned cycleScheduled(SUnit *SU) const {
695 : std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
696 : assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
697 5955 : return (it->second - FirstCycle) % InitiationInterval;
698 : }
699 :
700 : /// Return the maximum stage count needed for this schedule.
701 : unsigned getMaxStageCount() {
702 500 : return (LastCycle - FirstCycle) / InitiationInterval;
703 : }
704 :
705 : /// Return the max. number of stages/iterations that can occur between a
706 : /// register definition and its uses.
707 3078 : unsigned getStagesForReg(int Reg, unsigned CurStage) {
708 3078 : std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
709 3078 : if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second)
710 6 : return 1;
711 : return Stages.first;
712 : }
713 :
714 : /// The number of stages for a Phi is a little different than other
715 : /// instructions. The minimum value computed in RegToStageDiff is 1
716 : /// because we assume the Phi is needed for at least 1 iteration.
717 : /// This is not the case if the loop value is scheduled prior to the
718 : /// Phi in the same stage. This function returns the number of stages
719 : /// or iterations needed between the Phi definition and any uses.
720 : unsigned getStagesForPhi(int Reg) {
721 864 : std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
722 432 : if (Stages.second)
723 : return Stages.first;
724 399 : return Stages.first - 1;
725 : }
726 :
727 : /// Return the instructions that are scheduled at the specified cycle.
728 : std::deque<SUnit *> &getInstructions(int cycle) {
729 24141 : return ScheduledInstrs[cycle];
730 : }
731 :
732 : bool isValidSchedule(SwingSchedulerDAG *SSD);
733 : void finalizeSchedule(SwingSchedulerDAG *SSD);
734 : void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
735 : std::deque<SUnit *> &Insts);
736 : bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi);
737 : bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def,
738 : MachineOperand &MO);
739 : void print(raw_ostream &os) const;
740 : void dump() const;
741 : };
742 :
743 : } // end anonymous namespace
744 :
745 : unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
746 : char MachinePipeliner::ID = 0;
747 : #ifndef NDEBUG
748 : int MachinePipeliner::NumTries = 0;
749 : #endif
750 : char &llvm::MachinePipelinerID = MachinePipeliner::ID;
751 :
752 31780 : INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE,
753 : "Modulo Software Pipelining", false, false)
754 31780 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
755 31780 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
756 31780 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
757 31780 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
758 85990 : INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE,
759 : "Modulo Software Pipelining", false, false)
760 :
761 : /// The "main" function for implementing Swing Modulo Scheduling.
762 3294 : bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) {
763 3294 : if (skipFunction(mf.getFunction()))
764 : return false;
765 :
766 3284 : if (!EnableSWP)
767 : return false;
768 :
769 3275 : if (mf.getFunction().getAttributes().hasAttribute(
770 3275 : AttributeList::FunctionIndex, Attribute::OptimizeForSize) &&
771 33 : !EnableSWPOptSize.getPosition())
772 31 : return false;
773 :
774 3244 : MF = &mf;
775 3244 : MLI = &getAnalysis<MachineLoopInfo>();
776 3244 : MDT = &getAnalysis<MachineDominatorTree>();
777 3244 : TII = MF->getSubtarget().getInstrInfo();
778 3244 : RegClassInfo.runOnMachineFunction(*MF);
779 :
780 3601 : for (auto &L : *MLI)
781 357 : scheduleLoop(*L);
782 :
783 : return false;
784 : }
785 :
786 : /// Attempt to perform the SMS algorithm on the specified loop. This function is
787 : /// the main entry point for the algorithm. The function identifies candidate
788 : /// loops, calculates the minimum initiation interval, and attempts to schedule
789 : /// the loop.
790 395 : bool MachinePipeliner::scheduleLoop(MachineLoop &L) {
791 : bool Changed = false;
792 433 : for (auto &InnerLoop : L)
793 38 : Changed |= scheduleLoop(*InnerLoop);
794 :
795 : #ifndef NDEBUG
796 : // Stop trying after reaching the limit (if any).
797 : int Limit = SwpLoopLimit;
798 : if (Limit >= 0) {
799 : if (NumTries >= SwpLoopLimit)
800 : return Changed;
801 : NumTries++;
802 : }
803 : #endif
804 :
805 395 : if (!canPipelineLoop(L))
806 : return Changed;
807 :
808 : ++NumTrytoPipeline;
809 :
810 190 : Changed = swingModuloScheduler(L);
811 :
812 190 : return Changed;
813 : }
814 :
815 : /// Return true if the loop can be software pipelined. The algorithm is
816 : /// restricted to loops with a single basic block. Make sure that the
817 : /// branch in the loop can be analyzed.
818 395 : bool MachinePipeliner::canPipelineLoop(MachineLoop &L) {
819 395 : if (L.getNumBlocks() != 1)
820 : return false;
821 :
822 : // Check if the branch can't be understood because we can't do pipelining
823 : // if that's the case.
824 333 : LI.TBB = nullptr;
825 333 : LI.FBB = nullptr;
826 : LI.BrCond.clear();
827 666 : if (TII->analyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond))
828 : return false;
829 :
830 333 : LI.LoopInductionVar = nullptr;
831 333 : LI.LoopCompare = nullptr;
832 333 : if (TII->analyzeLoop(L, LI.LoopInductionVar, LI.LoopCompare))
833 : return false;
834 :
835 191 : if (!L.getLoopPreheader())
836 : return false;
837 :
838 : // Remove any subregisters from inputs to phi nodes.
839 190 : preprocessPhiNodes(*L.getHeader());
840 190 : return true;
841 : }
842 :
843 190 : void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) {
844 190 : MachineRegisterInfo &MRI = MF->getRegInfo();
845 190 : SlotIndexes &Slots = *getAnalysis<LiveIntervals>().getSlotIndexes();
846 :
847 803 : for (MachineInstr &PI : make_range(B.begin(), B.getFirstNonPHI())) {
848 423 : MachineOperand &DefOp = PI.getOperand(0);
849 : assert(DefOp.getSubReg() == 0);
850 423 : auto *RC = MRI.getRegClass(DefOp.getReg());
851 :
852 1269 : for (unsigned i = 1, n = PI.getNumOperands(); i != n; i += 2) {
853 846 : MachineOperand &RegOp = PI.getOperand(i);
854 846 : if (RegOp.getSubReg() == 0)
855 833 : continue;
856 :
857 : // If the operand uses a subregister, replace it with a new register
858 : // without subregisters, and generate a copy to the new register.
859 13 : unsigned NewReg = MRI.createVirtualRegister(RC);
860 13 : MachineBasicBlock &PredB = *PI.getOperand(i+1).getMBB();
861 13 : MachineBasicBlock::iterator At = PredB.getFirstTerminator();
862 : const DebugLoc &DL = PredB.findDebugLoc(At);
863 26 : auto Copy = BuildMI(PredB, At, DL, TII->get(TargetOpcode::COPY), NewReg)
864 : .addReg(RegOp.getReg(), getRegState(RegOp),
865 13 : RegOp.getSubReg());
866 13 : Slots.insertMachineInstrInMaps(*Copy);
867 13 : RegOp.setReg(NewReg);
868 : RegOp.setSubReg(0);
869 : }
870 : }
871 190 : }
872 :
873 : /// The SMS algorithm consists of the following main steps:
874 : /// 1. Computation and analysis of the dependence graph.
875 : /// 2. Ordering of the nodes (instructions).
876 : /// 3. Attempt to Schedule the loop.
877 190 : bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) {
878 : assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.");
879 :
880 190 : SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo);
881 :
882 : MachineBasicBlock *MBB = L.getHeader();
883 : // The kernel should not include any terminator instructions. These
884 : // will be added back later.
885 190 : SMS.startBlock(MBB);
886 :
887 : // Compute the number of 'real' instructions in the basic block by
888 : // ignoring terminators.
889 : unsigned size = MBB->size();
890 569 : for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
891 : E = MBB->instr_end();
892 569 : I != E; ++I, --size)
893 : ;
894 :
895 190 : SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size);
896 190 : SMS.schedule();
897 190 : SMS.exitRegion();
898 :
899 190 : SMS.finishBlock();
900 190 : return SMS.hasNewSchedule();
901 : }
902 :
903 : /// We override the schedule function in ScheduleDAGInstrs to implement the
904 : /// scheduling part of the Swing Modulo Scheduling algorithm.
905 190 : void SwingSchedulerDAG::schedule() {
906 190 : AliasAnalysis *AA = &Pass.getAnalysis<AAResultsWrapperPass>().getAAResults();
907 190 : buildSchedGraph(AA);
908 190 : addLoopCarriedDependences(AA);
909 190 : updatePhiDependences();
910 190 : Topo.InitDAGTopologicalSorting();
911 190 : changeDependences();
912 : postprocessDAG();
913 : LLVM_DEBUG(dump());
914 :
915 125 : NodeSetType NodeSets;
916 190 : findCircuits(NodeSets);
917 125 : NodeSetType Circuits = NodeSets;
918 :
919 : // Calculate the MII.
920 190 : unsigned ResMII = calculateResMII();
921 190 : unsigned RecMII = calculateRecMII(NodeSets);
922 :
923 190 : fuseRecs(NodeSets);
924 :
925 : // This flag is used for testing and can cause correctness problems.
926 190 : if (SwpIgnoreRecMII)
927 1 : RecMII = 0;
928 :
929 190 : MII = std::max(ResMII, RecMII);
930 : LLVM_DEBUG(dbgs() << "MII = " << MII << " (rec=" << RecMII
931 : << ", res=" << ResMII << ")\n");
932 :
933 : // Can't schedule a loop without a valid MII.
934 190 : if (MII == 0)
935 65 : return;
936 :
937 : // Don't pipeline large loops.
938 190 : if (SwpMaxMii != -1 && (int)MII > SwpMaxMii)
939 : return;
940 :
941 188 : computeNodeFunctions(NodeSets);
942 :
943 188 : registerPressureFilter(NodeSets);
944 :
945 188 : colocateNodeSets(NodeSets);
946 :
947 188 : checkNodeSets(NodeSets);
948 :
949 : LLVM_DEBUG({
950 : for (auto &I : NodeSets) {
951 : dbgs() << " Rec NodeSet ";
952 : I.dump();
953 : }
954 : });
955 :
956 : std::stable_sort(NodeSets.begin(), NodeSets.end(), std::greater<NodeSet>());
957 :
958 188 : groupRemainingNodes(NodeSets);
959 :
960 188 : removeDuplicateNodes(NodeSets);
961 :
962 : LLVM_DEBUG({
963 : for (auto &I : NodeSets) {
964 : dbgs() << " NodeSet ";
965 : I.dump();
966 : }
967 : });
968 :
969 188 : computeNodeOrder(NodeSets);
970 :
971 : // check for node order issues
972 188 : checkValidNodeOrder(Circuits);
973 :
974 313 : SMSchedule Schedule(Pass.MF);
975 188 : Scheduled = schedulePipeline(Schedule);
976 :
977 188 : if (!Scheduled)
978 63 : return;
979 :
980 : unsigned numStages = Schedule.getMaxStageCount();
981 : // No need to generate pipeline if there are no overlapped iterations.
982 125 : if (numStages == 0)
983 : return;
984 :
985 : // Check that the maximum stage count is less than user-defined limit.
986 125 : if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages)
987 : return;
988 :
989 125 : generatePipelinedLoop(Schedule);
990 : ++NumPipelined;
991 : }
992 :
993 : /// Clean up after the software pipeliner runs.
994 190 : void SwingSchedulerDAG::finishBlock() {
995 211 : for (MachineInstr *I : NewMIs)
996 21 : MF.DeleteMachineInstr(I);
997 190 : NewMIs.clear();
998 :
999 : // Call the superclass.
1000 190 : ScheduleDAGInstrs::finishBlock();
1001 190 : }
1002 :
1003 : /// Return the register values for the operands of a Phi instruction.
1004 : /// This function assume the instruction is a Phi.
1005 : static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
1006 : unsigned &InitVal, unsigned &LoopVal) {
1007 : assert(Phi.isPHI() && "Expecting a Phi.");
1008 :
1009 : InitVal = 0;
1010 : LoopVal = 0;
1011 8049 : for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
1012 10732 : if (Phi.getOperand(i + 1).getMBB() != Loop)
1013 1048 : InitVal = Phi.getOperand(i).getReg();
1014 : else
1015 2683 : LoopVal = Phi.getOperand(i).getReg();
1016 :
1017 : assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.");
1018 : }
1019 :
1020 : /// Return the Phi register value that comes from the incoming block.
1021 : static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
1022 342 : for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
1023 684 : if (Phi.getOperand(i + 1).getMBB() != LoopBB)
1024 342 : return Phi.getOperand(i).getReg();
1025 : return 0;
1026 : }
1027 :
1028 : /// Return the Phi register value that comes the loop block.
1029 : static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
1030 931 : for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
1031 1750 : if (Phi.getOperand(i + 1).getMBB() == LoopBB)
1032 382 : return Phi.getOperand(i).getReg();
1033 : return 0;
1034 : }
1035 :
1036 : /// Return true if SUb can be reached from SUa following the chain edges.
1037 364 : static bool isSuccOrder(SUnit *SUa, SUnit *SUb) {
1038 : SmallPtrSet<SUnit *, 8> Visited;
1039 : SmallVector<SUnit *, 8> Worklist;
1040 364 : Worklist.push_back(SUa);
1041 530 : while (!Worklist.empty()) {
1042 : const SUnit *SU = Worklist.pop_back_val();
1043 1118 : for (auto &SI : SU->Succs) {
1044 952 : SUnit *SuccSU = SI.getSUnit();
1045 952 : if (SI.getKind() == SDep::Order) {
1046 543 : if (Visited.count(SuccSU))
1047 0 : continue;
1048 543 : if (SuccSU == SUb)
1049 275 : return true;
1050 268 : Worklist.push_back(SuccSU);
1051 268 : Visited.insert(SuccSU);
1052 : }
1053 : }
1054 : }
1055 : return false;
1056 : }
1057 :
1058 : /// Return true if the instruction causes a chain between memory
1059 : /// references before and after it.
1060 2011 : static bool isDependenceBarrier(MachineInstr &MI, AliasAnalysis *AA) {
1061 4020 : return MI.isCall() || MI.hasUnmodeledSideEffects() ||
1062 2010 : (MI.hasOrderedMemoryRef() &&
1063 2 : (!MI.mayLoad() || !MI.isDereferenceableInvariantLoad(AA)));
1064 : }
1065 :
1066 : /// Return the underlying objects for the memory references of an instruction.
1067 : /// This function calls the code in ValueTracking, but first checks that the
1068 : /// instruction has a memory operand.
1069 484 : static void getUnderlyingObjects(MachineInstr *MI,
1070 : SmallVectorImpl<Value *> &Objs,
1071 : const DataLayout &DL) {
1072 484 : if (!MI->hasOneMemOperand())
1073 : return;
1074 446 : MachineMemOperand *MM = *MI->memoperands_begin();
1075 446 : if (!MM->getValue())
1076 : return;
1077 446 : GetUnderlyingObjects(const_cast<Value *>(MM->getValue()), Objs, DL);
1078 598 : for (Value *V : Objs) {
1079 446 : if (!isIdentifiedObject(V)) {
1080 : Objs.clear();
1081 294 : return;
1082 : }
1083 152 : Objs.push_back(V);
1084 : }
1085 : }
1086 :
1087 : /// Add a chain edge between a load and store if the store can be an
1088 : /// alias of the load on a subsequent iteration, i.e., a loop carried
1089 : /// dependence. This code is very similar to the code in ScheduleDAGInstrs
1090 : /// but that code doesn't create loop carried dependences.
1091 190 : void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) {
1092 : MapVector<Value *, SmallVector<SUnit *, 4>> PendingLoads;
1093 : Value *UnknownValue =
1094 190 : UndefValue::get(Type::getVoidTy(MF.getFunction().getContext()));
1095 2201 : for (auto &SU : SUnits) {
1096 2011 : MachineInstr &MI = *SU.getInstr();
1097 2011 : if (isDependenceBarrier(MI, AA))
1098 : PendingLoads.clear();
1099 2008 : else if (MI.mayLoad()) {
1100 : SmallVector<Value *, 4> Objs;
1101 325 : getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
1102 325 : if (Objs.empty())
1103 226 : Objs.push_back(UnknownValue);
1104 749 : for (auto V : Objs) {
1105 424 : SmallVector<SUnit *, 4> &SUs = PendingLoads[V];
1106 424 : SUs.push_back(&SU);
1107 : }
1108 1683 : } else if (MI.mayStore()) {
1109 : SmallVector<Value *, 4> Objs;
1110 159 : getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
1111 159 : if (Objs.empty())
1112 106 : Objs.push_back(UnknownValue);
1113 371 : for (auto V : Objs) {
1114 : MapVector<Value *, SmallVector<SUnit *, 4>>::iterator I =
1115 212 : PendingLoads.find(V);
1116 212 : if (I == PendingLoads.end())
1117 : continue;
1118 476 : for (auto Load : I->second) {
1119 364 : if (isSuccOrder(Load, &SU))
1120 299 : continue;
1121 89 : MachineInstr &LdMI = *Load->getInstr();
1122 : // First, perform the cheaper check that compares the base register.
1123 : // If they are the same and the load offset is less than the store
1124 : // offset, then mark the dependence as loop carried potentially.
1125 : unsigned BaseReg1, BaseReg2;
1126 : int64_t Offset1, Offset2;
1127 177 : if (TII->getMemOpBaseRegImmOfs(LdMI, BaseReg1, Offset1, TRI) &&
1128 88 : TII->getMemOpBaseRegImmOfs(MI, BaseReg2, Offset2, TRI)) {
1129 86 : if (BaseReg1 == BaseReg2 && (int)Offset1 < (int)Offset2) {
1130 : assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI, AA) &&
1131 : "What happened to the chain edge?");
1132 : SDep Dep(Load, SDep::Barrier);
1133 : Dep.setLatency(1);
1134 24 : SU.addPred(Dep);
1135 : continue;
1136 : }
1137 : }
1138 : // Second, the more expensive check that uses alias analysis on the
1139 : // base registers. If they alias, and the load offset is less than
1140 : // the store offset, the mark the dependence as loop carried.
1141 65 : if (!AA) {
1142 : SDep Dep(Load, SDep::Barrier);
1143 : Dep.setLatency(1);
1144 0 : SU.addPred(Dep);
1145 : continue;
1146 : }
1147 65 : MachineMemOperand *MMO1 = *LdMI.memoperands_begin();
1148 65 : MachineMemOperand *MMO2 = *MI.memoperands_begin();
1149 130 : if (!MMO1->getValue() || !MMO2->getValue()) {
1150 : SDep Dep(Load, SDep::Barrier);
1151 : Dep.setLatency(1);
1152 0 : SU.addPred(Dep);
1153 : continue;
1154 : }
1155 65 : if (MMO1->getValue() == MMO2->getValue() &&
1156 20 : MMO1->getOffset() <= MMO2->getOffset()) {
1157 : SDep Dep(Load, SDep::Barrier);
1158 : Dep.setLatency(1);
1159 0 : SU.addPred(Dep);
1160 : continue;
1161 : }
1162 65 : AliasResult AAResult = AA->alias(
1163 65 : MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
1164 : MMO1->getAAInfo()),
1165 65 : MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
1166 : MMO2->getAAInfo()));
1167 :
1168 65 : if (AAResult != NoAlias) {
1169 : SDep Dep(Load, SDep::Barrier);
1170 : Dep.setLatency(1);
1171 20 : SU.addPred(Dep);
1172 : }
1173 : }
1174 : }
1175 : }
1176 : }
1177 190 : }
1178 :
1179 : /// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer
1180 : /// processes dependences for PHIs. This function adds true dependences
1181 : /// from a PHI to a use, and a loop carried dependence from the use to the
1182 : /// PHI. The loop carried dependence is represented as an anti dependence
1183 : /// edge. This function also removes chain dependences between unrelated
1184 : /// PHIs.
1185 190 : void SwingSchedulerDAG::updatePhiDependences() {
1186 : SmallVector<SDep, 4> RemoveDeps;
1187 190 : const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>();
1188 :
1189 : // Iterate over each DAG node.
1190 2201 : for (SUnit &I : SUnits) {
1191 : RemoveDeps.clear();
1192 : // Set to true if the instruction has an operand defined by a Phi.
1193 : unsigned HasPhiUse = 0;
1194 : unsigned HasPhiDef = 0;
1195 2011 : MachineInstr *MI = I.getInstr();
1196 : // Iterate over each operand, and we process the definitions.
1197 7591 : for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
1198 2011 : MOE = MI->operands_end();
1199 9602 : MOI != MOE; ++MOI) {
1200 7591 : if (!MOI->isReg())
1201 : continue;
1202 5668 : unsigned Reg = MOI->getReg();
1203 5668 : if (MOI->isDef()) {
1204 : // If the register is used by a Phi, then create an anti dependence.
1205 2738 : for (MachineRegisterInfo::use_instr_iterator
1206 2014 : UI = MRI.use_instr_begin(Reg),
1207 : UE = MRI.use_instr_end();
1208 7490 : UI != UE; ++UI) {
1209 : MachineInstr *UseMI = &*UI;
1210 : SUnit *SU = getSUnit(UseMI);
1211 2665 : if (SU != nullptr && UseMI->isPHI()) {
1212 : if (!MI->isPHI()) {
1213 : SDep Dep(SU, SDep::Anti, Reg);
1214 : Dep.setLatency(1);
1215 394 : I.addPred(Dep);
1216 : } else {
1217 : HasPhiDef = Reg;
1218 : // Add a chain edge to a dependent Phi that isn't an existing
1219 : // predecessor.
1220 40 : if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
1221 14 : I.addPred(SDep(SU, SDep::Barrier));
1222 : }
1223 : }
1224 : }
1225 : } else if (MOI->isUse()) {
1226 : // If the register is defined by a Phi, then create a true dependence.
1227 3654 : MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg);
1228 3654 : if (DefMI == nullptr)
1229 : continue;
1230 : SUnit *SU = getSUnit(DefMI);
1231 2688 : if (SU != nullptr && DefMI->isPHI()) {
1232 : if (!MI->isPHI()) {
1233 : SDep Dep(SU, SDep::Data, Reg);
1234 : Dep.setLatency(0);
1235 757 : ST.adjustSchedDependency(SU, &I, Dep);
1236 757 : I.addPred(Dep);
1237 : } else {
1238 : HasPhiUse = Reg;
1239 : // Add a chain edge to a dependent Phi that isn't an existing
1240 : // predecessor.
1241 38 : if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
1242 0 : I.addPred(SDep(SU, SDep::Barrier));
1243 : }
1244 : }
1245 : }
1246 : }
1247 : // Remove order dependences from an unrelated Phi.
1248 2011 : if (!SwpPruneDeps)
1249 : continue;
1250 4897 : for (auto &PI : I.Preds) {
1251 2886 : MachineInstr *PMI = PI.getSUnit()->getInstr();
1252 1176 : if (PMI->isPHI() && PI.getKind() == SDep::Order) {
1253 14 : if (I.getInstr()->isPHI()) {
1254 14 : if (PMI->getOperand(0).getReg() == HasPhiUse)
1255 : continue;
1256 28 : if (getLoopPhiReg(*PMI, PMI->getParent()) == HasPhiDef)
1257 : continue;
1258 : }
1259 0 : RemoveDeps.push_back(PI);
1260 : }
1261 : }
1262 2011 : for (int i = 0, e = RemoveDeps.size(); i != e; ++i)
1263 0 : I.removePred(RemoveDeps[i]);
1264 : }
1265 190 : }
1266 :
1267 : /// Iterate over each DAG node and see if we can change any dependences
1268 : /// in order to reduce the recurrence MII.
1269 190 : void SwingSchedulerDAG::changeDependences() {
1270 : // See if an instruction can use a value from the previous iteration.
1271 : // If so, we update the base and offset of the instruction and change
1272 : // the dependences.
1273 2201 : for (SUnit &I : SUnits) {
1274 2011 : unsigned BasePos = 0, OffsetPos = 0, NewBase = 0;
1275 2011 : int64_t NewOffset = 0;
1276 2011 : if (!canUseLastOffsetValue(I.getInstr(), BasePos, OffsetPos, NewBase,
1277 : NewOffset))
1278 1986 : continue;
1279 :
1280 : // Get the MI and SUnit for the instruction that defines the original base.
1281 25 : unsigned OrigBase = I.getInstr()->getOperand(BasePos).getReg();
1282 25 : MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase);
1283 25 : if (!DefMI)
1284 : continue;
1285 : SUnit *DefSU = getSUnit(DefMI);
1286 25 : if (!DefSU)
1287 0 : continue;
1288 : // Get the MI and SUnit for the instruction that defins the new base.
1289 25 : MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase);
1290 25 : if (!LastMI)
1291 : continue;
1292 : SUnit *LastSU = getSUnit(LastMI);
1293 25 : if (!LastSU)
1294 0 : continue;
1295 :
1296 25 : if (Topo.IsReachable(&I, LastSU))
1297 : continue;
1298 :
1299 : // Remove the dependence. The value now depends on a prior iteration.
1300 : SmallVector<SDep, 4> Deps;
1301 50 : for (SUnit::pred_iterator P = I.Preds.begin(), E = I.Preds.end(); P != E;
1302 : ++P)
1303 25 : if (P->getSUnit() == DefSU)
1304 25 : Deps.push_back(*P);
1305 50 : for (int i = 0, e = Deps.size(); i != e; i++) {
1306 50 : Topo.RemovePred(&I, Deps[i].getSUnit());
1307 25 : I.removePred(Deps[i]);
1308 : }
1309 : // Remove the chain dependence between the instructions.
1310 : Deps.clear();
1311 123 : for (auto &P : LastSU->Preds)
1312 98 : if (P.getSUnit() == &I && P.getKind() == SDep::Order)
1313 22 : Deps.push_back(P);
1314 47 : for (int i = 0, e = Deps.size(); i != e; i++) {
1315 44 : Topo.RemovePred(LastSU, Deps[i].getSUnit());
1316 22 : LastSU->removePred(Deps[i]);
1317 : }
1318 :
1319 : // Add a dependence between the new instruction and the instruction
1320 : // that defines the new base.
1321 25 : SDep Dep(&I, SDep::Anti, NewBase);
1322 25 : Topo.AddPred(LastSU, &I);
1323 25 : LastSU->addPred(Dep);
1324 :
1325 : // Remember the base and offset information so that we can update the
1326 : // instruction during code generation.
1327 25 : InstrChanges[&I] = std::make_pair(NewBase, NewOffset);
1328 : }
1329 190 : }
1330 :
1331 : namespace {
1332 :
1333 : // FuncUnitSorter - Comparison operator used to sort instructions by
1334 : // the number of functional unit choices.
1335 12744 : struct FuncUnitSorter {
1336 : const InstrItineraryData *InstrItins;
1337 : DenseMap<unsigned, unsigned> Resources;
1338 :
1339 190 : FuncUnitSorter(const InstrItineraryData *IID) : InstrItins(IID) {}
1340 :
1341 : // Compute the number of functional unit alternatives needed
1342 : // at each stage, and take the minimum value. We prioritize the
1343 : // instructions by the least number of choices first.
1344 0 : unsigned minFuncUnits(const MachineInstr *Inst, unsigned &F) const {
1345 5895 : unsigned schedClass = Inst->getDesc().getSchedClass();
1346 : unsigned min = UINT_MAX;
1347 17794 : for (const InstrStage *IS = InstrItins->beginStage(schedClass),
1348 : *IE = InstrItins->endStage(schedClass);
1349 29584 : IS != IE; ++IS) {
1350 17794 : unsigned funcUnits = IS->getUnits();
1351 : unsigned numAlternatives = countPopulation(funcUnits);
1352 17794 : if (numAlternatives < min) {
1353 : min = numAlternatives;
1354 13113 : F = funcUnits;
1355 : }
1356 : }
1357 0 : return min;
1358 : }
1359 :
1360 : // Compute the critical resources needed by the instruction. This
1361 : // function records the functional units needed by instructions that
1362 : // must use only one functional unit. We use this as a tie breaker
1363 : // for computing the resource MII. The instrutions that require
1364 : // the same, highly used, functional unit have high priority.
1365 1589 : void calcCriticalResources(MachineInstr &MI) {
1366 1589 : unsigned SchedClass = MI.getDesc().getSchedClass();
1367 3945 : for (const InstrStage *IS = InstrItins->beginStage(SchedClass),
1368 : *IE = InstrItins->endStage(SchedClass);
1369 3945 : IS != IE; ++IS) {
1370 2356 : unsigned FuncUnits = IS->getUnits();
1371 2356 : if (countPopulation(FuncUnits) == 1)
1372 674 : Resources[FuncUnits]++;
1373 : }
1374 1589 : }
1375 :
1376 : /// Return true if IS1 has less priority than IS2.
1377 5895 : bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const {
1378 5895 : unsigned F1 = 0, F2 = 0;
1379 5895 : unsigned MFUs1 = minFuncUnits(IS1, F1);
1380 : unsigned MFUs2 = minFuncUnits(IS2, F2);
1381 5895 : if (MFUs1 == 1 && MFUs2 == 1)
1382 2232 : return Resources.lookup(F1) < Resources.lookup(F2);
1383 4779 : return MFUs1 > MFUs2;
1384 : }
1385 : };
1386 :
1387 : } // end anonymous namespace
1388 :
1389 : /// Calculate the resource constrained minimum initiation interval for the
1390 : /// specified loop. We use the DFA to model the resources needed for
1391 : /// each instruction, and we ignore dependences. A different DFA is created
1392 : /// for each cycle that is required. When adding a new instruction, we attempt
1393 : /// to add it to each existing DFA, until a legal space is found. If the
1394 : /// instruction cannot be reserved in an existing DFA, we create a new one.
1395 190 : unsigned SwingSchedulerDAG::calculateResMII() {
1396 : SmallVector<DFAPacketizer *, 8> Resources;
1397 190 : MachineBasicBlock *MBB = Loop.getHeader();
1398 190 : Resources.push_back(TII->CreateTargetScheduleState(MF.getSubtarget()));
1399 :
1400 : // Sort the instructions by the number of available choices for scheduling,
1401 : // least to most. Use the number of critical resources as the tie breaker.
1402 : FuncUnitSorter FUS =
1403 190 : FuncUnitSorter(MF.getSubtarget().getInstrItineraryData());
1404 190 : for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
1405 190 : E = MBB->getFirstTerminator();
1406 1779 : I != E; ++I)
1407 1589 : FUS.calcCriticalResources(*I);
1408 : PriorityQueue<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
1409 190 : FuncUnitOrder(FUS);
1410 :
1411 190 : for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
1412 190 : E = MBB->getFirstTerminator();
1413 1779 : I != E; ++I)
1414 1589 : FuncUnitOrder.push(&*I);
1415 :
1416 1779 : while (!FuncUnitOrder.empty()) {
1417 1589 : MachineInstr *MI = FuncUnitOrder.top();
1418 1589 : FuncUnitOrder.pop();
1419 3178 : if (TII->isZeroCost(MI->getOpcode()))
1420 : continue;
1421 : // Attempt to reserve the instruction in an existing DFA. At least one
1422 : // DFA is needed for each cycle.
1423 1507 : unsigned NumCycles = getSUnit(MI)->Latency;
1424 : unsigned ReservedCycles = 0;
1425 : SmallVectorImpl<DFAPacketizer *>::iterator RI = Resources.begin();
1426 : SmallVectorImpl<DFAPacketizer *>::iterator RE = Resources.end();
1427 3014 : for (unsigned C = 0; C < NumCycles; ++C)
1428 6050 : while (RI != RE) {
1429 5715 : if ((*RI++)->canReserveResources(*MI)) {
1430 1172 : ++ReservedCycles;
1431 1172 : break;
1432 : }
1433 : }
1434 : // Start reserving resources using existing DFAs.
1435 2679 : for (unsigned C = 0; C < ReservedCycles; ++C) {
1436 1172 : --RI;
1437 1172 : (*RI)->reserveResources(*MI);
1438 : }
1439 : // Add new DFAs, if needed, to reserve resources.
1440 1842 : for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
1441 : DFAPacketizer *NewResource =
1442 335 : TII->CreateTargetScheduleState(MF.getSubtarget());
1443 : assert(NewResource->canReserveResources(*MI) && "Reserve error.");
1444 335 : NewResource->reserveResources(*MI);
1445 335 : Resources.push_back(NewResource);
1446 : }
1447 : }
1448 190 : int Resmii = Resources.size();
1449 : // Delete the memory for each of the DFAs that were created earlier.
1450 715 : for (DFAPacketizer *RI : Resources) {
1451 : DFAPacketizer *D = RI;
1452 1050 : delete D;
1453 : }
1454 : Resources.clear();
1455 190 : return Resmii;
1456 : }
1457 :
1458 : /// Calculate the recurrence-constrainted minimum initiation interval.
1459 : /// Iterate over each circuit. Compute the delay(c) and distance(c)
1460 : /// for each circuit. The II needs to satisfy the inequality
1461 : /// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest
1462 : /// II that satisfies the inequality, and the RecMII is the maximum
1463 : /// of those values.
1464 0 : unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) {
1465 : unsigned RecMII = 0;
1466 :
1467 768 : for (NodeSet &Nodes : NodeSets) {
1468 578 : if (Nodes.empty())
1469 0 : continue;
1470 :
1471 578 : unsigned Delay = Nodes.getLatency();
1472 : unsigned Distance = 1;
1473 :
1474 : // ii = ceil(delay / distance)
1475 : unsigned CurMII = (Delay + Distance - 1) / Distance;
1476 : Nodes.setRecMII(CurMII);
1477 578 : if (CurMII > RecMII)
1478 : RecMII = CurMII;
1479 : }
1480 :
1481 0 : return RecMII;
1482 : }
1483 :
1484 : /// Swap all the anti dependences in the DAG. That means it is no longer a DAG,
1485 : /// but we do this to find the circuits, and then change them back.
1486 380 : static void swapAntiDependences(std::vector<SUnit> &SUnits) {
1487 : SmallVector<std::pair<SUnit *, SDep>, 8> DepsAdded;
1488 4782 : for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
1489 4022 : SUnit *SU = &SUnits[i];
1490 5736 : for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end();
1491 9758 : IP != EP; ++IP) {
1492 5736 : if (IP->getKind() != SDep::Anti)
1493 : continue;
1494 842 : DepsAdded.push_back(std::make_pair(SU, *IP));
1495 : }
1496 : }
1497 842 : for (SmallVector<std::pair<SUnit *, SDep>, 8>::iterator I = DepsAdded.begin(),
1498 : E = DepsAdded.end();
1499 1222 : I != E; ++I) {
1500 : // Remove this anti dependency and add one in the reverse direction.
1501 842 : SUnit *SU = I->first;
1502 842 : SDep &D = I->second;
1503 : SUnit *TargetSU = D.getSUnit();
1504 842 : unsigned Reg = D.getReg();
1505 842 : unsigned Lat = D.getLatency();
1506 842 : SU->removePred(D);
1507 : SDep Dep(SU, SDep::Anti, Reg);
1508 : Dep.setLatency(Lat);
1509 842 : TargetSU->addPred(Dep);
1510 : }
1511 380 : }
1512 :
1513 : /// Create the adjacency structure of the nodes in the graph.
1514 190 : void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
1515 : SwingSchedulerDAG *DAG) {
1516 380 : BitVector Added(SUnits.size());
1517 : DenseMap<int, int> OutputDeps;
1518 2391 : for (int i = 0, e = SUnits.size(); i != e; ++i) {
1519 : Added.reset();
1520 : // Add any successor to the adjacency matrix and exclude duplicates.
1521 4879 : for (auto &SI : SUnits[i].Succs) {
1522 : // Only create a back-edge on the first and last nodes of a dependence
1523 : // chain. This records any chains and adds them later.
1524 2868 : if (SI.getKind() == SDep::Output) {
1525 0 : int N = SI.getSUnit()->NodeNum;
1526 0 : int BackEdge = i;
1527 0 : auto Dep = OutputDeps.find(BackEdge);
1528 0 : if (Dep != OutputDeps.end()) {
1529 0 : BackEdge = Dep->second;
1530 : OutputDeps.erase(Dep);
1531 : }
1532 0 : OutputDeps[N] = BackEdge;
1533 : }
1534 : // Do not process a boundary node and a back-edge is processed only
1535 : // if it goes to a Phi.
1536 2868 : if (SI.getSUnit()->isBoundaryNode() ||
1537 421 : (SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI()))
1538 27 : continue;
1539 2841 : int N = SI.getSUnit()->NodeNum;
1540 2841 : if (!Added.test(N)) {
1541 2826 : AdjK[i].push_back(N);
1542 2826 : Added.set(N);
1543 : }
1544 : }
1545 : // A chain edge between a store and a load is treated as a back-edge in the
1546 : // adjacency matrix.
1547 4879 : for (auto &PI : SUnits[i].Preds) {
1548 6246 : if (!SUnits[i].getInstr()->mayStore() ||
1549 1020 : !DAG->isLoopCarriedDep(&SUnits[i], PI, false))
1550 2750 : continue;
1551 118 : if (PI.getKind() == SDep::Order && PI.getSUnit()->getInstr()->mayLoad()) {
1552 117 : int N = PI.getSUnit()->NodeNum;
1553 117 : if (!Added.test(N)) {
1554 117 : AdjK[i].push_back(N);
1555 117 : Added.set(N);
1556 : }
1557 : }
1558 : }
1559 : }
1560 : // Add back-eges in the adjacency matrix for the output dependences.
1561 190 : for (auto &OD : OutputDeps)
1562 0 : if (!Added.test(OD.second)) {
1563 0 : AdjK[OD.first].push_back(OD.second);
1564 0 : Added.set(OD.second);
1565 : }
1566 190 : }
1567 :
1568 : /// Identify an elementary circuit in the dependence graph starting at the
1569 : /// specified node.
1570 16475 : bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
1571 : bool HasBackedge) {
1572 16475 : SUnit *SV = &SUnits[V];
1573 : bool F = false;
1574 16475 : Stack.insert(SV);
1575 16475 : Blocked.set(V);
1576 :
1577 39508 : for (auto W : AdjK[V]) {
1578 23927 : if (NumPaths > MaxPaths)
1579 : break;
1580 23788 : if (W < S)
1581 : continue;
1582 20524 : if (W == S) {
1583 755 : if (!HasBackedge)
1584 1734 : NodeSets.push_back(NodeSet(Stack.begin(), Stack.end()));
1585 : F = true;
1586 755 : ++NumPaths;
1587 : break;
1588 39538 : } else if (!Blocked.test(W)) {
1589 14464 : if (circuit(W, S, NodeSets,
1590 14464 : Node2Idx->at(W) < Node2Idx->at(V) ? true : HasBackedge))
1591 : F = true;
1592 : }
1593 : }
1594 :
1595 15720 : if (F)
1596 2418 : unblock(V);
1597 : else {
1598 33142 : for (auto W : AdjK[V]) {
1599 19085 : if (W < S)
1600 : continue;
1601 32306 : if (B[W].count(SV) == 0)
1602 15629 : B[W].insert(SV);
1603 : }
1604 : }
1605 : Stack.pop_back();
1606 16475 : return F;
1607 : }
1608 :
1609 : /// Unblock a node in the circuit finding algorithm.
1610 5468 : void SwingSchedulerDAG::Circuits::unblock(int U) {
1611 5468 : Blocked.reset(U);
1612 5468 : SmallPtrSet<SUnit *, 4> &BU = B[U];
1613 10230 : while (!BU.empty()) {
1614 4762 : SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
1615 : assert(SI != BU.end() && "Invalid B set.");
1616 4762 : SUnit *W = *SI;
1617 : BU.erase(W);
1618 9524 : if (Blocked.test(W->NodeNum))
1619 3050 : unblock(W->NodeNum);
1620 : }
1621 5468 : }
1622 :
1623 : /// Identify all the elementary circuits in the dependence graph using
1624 : /// Johnson's circuit algorithm.
1625 190 : void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {
1626 : // Swap all the anti dependences in the DAG. That means it is no longer a DAG,
1627 : // but we do this to find the circuits, and then change them back.
1628 190 : swapAntiDependences(SUnits);
1629 :
1630 380 : Circuits Cir(SUnits, Topo);
1631 : // Create the adjacency structure.
1632 190 : Cir.createAdjacencyStructure(this);
1633 2391 : for (int i = 0, e = SUnits.size(); i != e; ++i) {
1634 2011 : Cir.reset();
1635 2011 : Cir.circuit(i, i, NodeSets);
1636 : }
1637 :
1638 : // Change the dependences back so that we've created a DAG again.
1639 190 : swapAntiDependences(SUnits);
1640 190 : }
1641 :
1642 : // Create artificial dependencies between the source of COPY/REG_SEQUENCE that
1643 : // is loop-carried to the USE in next iteration. This will help pipeliner avoid
1644 : // additional copies that are needed across iterations. An artificial dependence
1645 : // edge is added from USE to SOURCE of COPY/REG_SEQUENCE.
1646 :
1647 : // PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried)
1648 : // SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE
1649 : // PHI-------True-Dep------> USEOfPhi
1650 :
1651 : // The mutation creates
1652 : // USEOfPHI -------Artificial-Dep---> SRCOfCopy
1653 :
1654 : // This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy
1655 : // (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled
1656 : // late to avoid additional copies across iterations. The possible scheduling
1657 : // order would be
1658 : // USEOfPHI --- SRCOfCopy--- COPY/REG_SEQUENCE.
1659 :
1660 190 : void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) {
1661 2201 : for (SUnit &SU : DAG->SUnits) {
1662 : // Find the COPY/REG_SEQUENCE instruction.
1663 4022 : if (!SU.getInstr()->isCopy() && !SU.getInstr()->isRegSequence())
1664 2004 : continue;
1665 :
1666 : // Record the loop carried PHIs.
1667 : SmallVector<SUnit *, 4> PHISUs;
1668 : // Record the SrcSUs that feed the COPY/REG_SEQUENCE instructions.
1669 : SmallVector<SUnit *, 4> SrcSUs;
1670 :
1671 228 : for (auto &Dep : SU.Preds) {
1672 148 : SUnit *TmpSU = Dep.getSUnit();
1673 148 : MachineInstr *TmpMI = TmpSU->getInstr();
1674 : SDep::Kind DepKind = Dep.getKind();
1675 : // Save the loop carried PHI.
1676 148 : if (DepKind == SDep::Anti && TmpMI->isPHI())
1677 8 : PHISUs.push_back(TmpSU);
1678 : // Save the source of COPY/REG_SEQUENCE.
1679 : // If the source has no pre-decessors, we will end up creating cycles.
1680 258 : else if (DepKind == SDep::Data && !TmpMI->isPHI() && TmpSU->NumPreds > 0)
1681 115 : SrcSUs.push_back(TmpSU);
1682 : }
1683 :
1684 80 : if (PHISUs.size() == 0 || SrcSUs.size() == 0)
1685 : continue;
1686 :
1687 : // Find the USEs of PHI. If the use is a PHI or REG_SEQUENCE, push back this
1688 : // SUnit to the container.
1689 : SmallVector<SUnit *, 8> UseSUs;
1690 18 : for (auto I = PHISUs.begin(); I != PHISUs.end(); ++I) {
1691 29 : for (auto &Dep : (*I)->Succs) {
1692 18 : if (Dep.getKind() != SDep::Data)
1693 11 : continue;
1694 :
1695 11 : SUnit *TmpSU = Dep.getSUnit();
1696 11 : MachineInstr *TmpMI = TmpSU->getInstr();
1697 11 : if (TmpMI->isPHI() || TmpMI->isRegSequence()) {
1698 4 : PHISUs.push_back(TmpSU);
1699 4 : continue;
1700 : }
1701 7 : UseSUs.push_back(TmpSU);
1702 : }
1703 : }
1704 :
1705 14 : if (UseSUs.size() == 0)
1706 : continue;
1707 :
1708 : SwingSchedulerDAG *SDAG = cast<SwingSchedulerDAG>(DAG);
1709 : // Add the artificial dependencies if it does not form a cycle.
1710 14 : for (auto I : UseSUs) {
1711 14 : for (auto Src : SrcSUs) {
1712 7 : if (!SDAG->Topo.IsReachable(I, Src) && Src != I) {
1713 4 : Src->addPred(SDep(I, SDep::Artificial));
1714 4 : SDAG->Topo.AddPred(Src, I);
1715 : }
1716 : }
1717 : }
1718 : }
1719 190 : }
1720 :
1721 : /// Return true for DAG nodes that we ignore when computing the cost functions.
1722 : /// We ignore the back-edge recurrence in order to avoid unbounded recursion
1723 : /// in the calculation of the ASAP, ALAP, etc functions.
1724 : static bool ignoreDependence(const SDep &D, bool isPred) {
1725 : if (D.isArtificial())
1726 : return true;
1727 13613 : return D.getKind() == SDep::Anti && isPred;
1728 : }
1729 :
1730 : /// Compute several functions need to order the nodes for scheduling.
1731 : /// ASAP - Earliest time to schedule a node.
1732 : /// ALAP - Latest time to schedule a node.
1733 : /// MOV - Mobility function, difference between ALAP and ASAP.
1734 : /// D - Depth of each node.
1735 : /// H - Height of each node.
1736 188 : void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) {
1737 376 : ScheduleInfo.resize(SUnits.size());
1738 :
1739 : LLVM_DEBUG({
1740 : for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
1741 : E = Topo.end();
1742 : I != E; ++I) {
1743 : const SUnit &SU = SUnits[*I];
1744 : dumpNode(SU);
1745 : }
1746 : });
1747 :
1748 188 : int maxASAP = 0;
1749 : // Compute ASAP and ZeroLatencyDepth.
1750 : for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
1751 : E = Topo.end();
1752 2033 : I != E; ++I) {
1753 1845 : int asap = 0;
1754 1845 : int zeroLatencyDepth = 0;
1755 1845 : SUnit *SU = &SUnits[*I];
1756 2603 : for (SUnit::const_pred_iterator IP = SU->Preds.begin(),
1757 : EP = SU->Preds.end();
1758 4448 : IP != EP; ++IP) {
1759 : SUnit *pred = IP->getSUnit();
1760 2603 : if (IP->getLatency() == 0)
1761 1100 : zeroLatencyDepth =
1762 3032 : std::max(zeroLatencyDepth, getZeroLatencyDepth(pred) + 1);
1763 : if (ignoreDependence(*IP, true))
1764 : continue;
1765 5328 : asap = std::max(asap, (int)(getASAP(pred) + IP->getLatency() -
1766 : getDistance(pred, SU, *IP) * MII));
1767 : }
1768 1845 : maxASAP = std::max(maxASAP, asap);
1769 1845 : ScheduleInfo[*I].ASAP = asap;
1770 3690 : ScheduleInfo[*I].ZeroLatencyDepth = zeroLatencyDepth;
1771 : }
1772 :
1773 : // Compute ALAP, ZeroLatencyHeight, and MOV.
1774 : for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(),
1775 : E = Topo.rend();
1776 2033 : I != E; ++I) {
1777 1845 : int alap = maxASAP;
1778 1845 : int zeroLatencyHeight = 0;
1779 1845 : SUnit *SU = &SUnits[*I];
1780 2603 : for (SUnit::const_succ_iterator IS = SU->Succs.begin(),
1781 : ES = SU->Succs.end();
1782 4448 : IS != ES; ++IS) {
1783 : SUnit *succ = IS->getSUnit();
1784 2603 : if (IS->getLatency() == 0)
1785 1100 : zeroLatencyHeight =
1786 2952 : std::max(zeroLatencyHeight, getZeroLatencyHeight(succ) + 1);
1787 : if (ignoreDependence(*IS, true))
1788 : continue;
1789 5738 : alap = std::min(alap, (int)(getALAP(succ) - IS->getLatency() +
1790 : getDistance(SU, succ, *IS) * MII));
1791 : }
1792 :
1793 1845 : ScheduleInfo[*I].ALAP = alap;
1794 3690 : ScheduleInfo[*I].ZeroLatencyHeight = zeroLatencyHeight;
1795 : }
1796 :
1797 : // After computing the node functions, compute the summary for each node set.
1798 608 : for (NodeSet &I : NodeSets)
1799 420 : I.computeNodeSetInfo(this);
1800 :
1801 : LLVM_DEBUG({
1802 : for (unsigned i = 0; i < SUnits.size(); i++) {
1803 : dbgs() << "\tNode " << i << ":\n";
1804 : dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n";
1805 : dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n";
1806 : dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n";
1807 : dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n";
1808 : dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n";
1809 : dbgs() << "\t ZLD = " << getZeroLatencyDepth(&SUnits[i]) << "\n";
1810 : dbgs() << "\t ZLH = " << getZeroLatencyHeight(&SUnits[i]) << "\n";
1811 : }
1812 : });
1813 188 : }
1814 :
1815 : /// Compute the Pred_L(O) set, as defined in the paper. The set is defined
1816 : /// as the predecessors of the elements of NodeOrder that are not also in
1817 : /// NodeOrder.
1818 849 : static bool pred_L(SetVector<SUnit *> &NodeOrder,
1819 : SmallSetVector<SUnit *, 8> &Preds,
1820 : const NodeSet *S = nullptr) {
1821 849 : Preds.clear();
1822 : for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
1823 7472 : I != E; ++I) {
1824 17998 : for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end();
1825 17998 : PI != PE; ++PI) {
1826 11375 : if (S && S->count(PI->getSUnit()) == 0)
1827 2948 : continue;
1828 : if (ignoreDependence(*PI, true))
1829 : continue;
1830 7095 : if (NodeOrder.count(PI->getSUnit()) == 0)
1831 1018 : Preds.insert(PI->getSUnit());
1832 : }
1833 : // Back-edges are predecessors with an anti-dependence.
1834 16597 : for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(),
1835 : ES = (*I)->Succs.end();
1836 16597 : IS != ES; ++IS) {
1837 9974 : if (IS->getKind() != SDep::Anti)
1838 : continue;
1839 1313 : if (S && S->count(IS->getSUnit()) == 0)
1840 304 : continue;
1841 1009 : if (NodeOrder.count(IS->getSUnit()) == 0)
1842 0 : Preds.insert(IS->getSUnit());
1843 : }
1844 : }
1845 849 : return !Preds.empty();
1846 : }
1847 :
1848 : /// Compute the Succ_L(O) set, as defined in the paper. The set is defined
1849 : /// as the successors of the elements of NodeOrder that are not also in
1850 : /// NodeOrder.
1851 2476 : static bool succ_L(SetVector<SUnit *> &NodeOrder,
1852 : SmallSetVector<SUnit *, 8> &Succs,
1853 : const NodeSet *S = nullptr) {
1854 2476 : Succs.clear();
1855 : for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
1856 14473 : I != E; ++I) {
1857 30113 : for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end();
1858 30113 : SI != SE; ++SI) {
1859 18116 : if (S && S->count(SI->getSUnit()) == 0)
1860 2946 : continue;
1861 : if (ignoreDependence(*SI, false))
1862 : continue;
1863 15128 : if (NodeOrder.count(SI->getSUnit()) == 0)
1864 1933 : Succs.insert(SI->getSUnit());
1865 : }
1866 33558 : for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(),
1867 : PE = (*I)->Preds.end();
1868 33558 : PI != PE; ++PI) {
1869 21561 : if (PI->getKind() != SDep::Anti)
1870 : continue;
1871 3741 : if (S && S->count(PI->getSUnit()) == 0)
1872 468 : continue;
1873 3273 : if (NodeOrder.count(PI->getSUnit()) == 0)
1874 887 : Succs.insert(PI->getSUnit());
1875 : }
1876 : }
1877 2476 : return !Succs.empty();
1878 : }
1879 :
1880 : /// Return true if there is a path from the specified node to any of the nodes
1881 : /// in DestNodes. Keep track and return the nodes in any path.
1882 5219 : static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
1883 : SetVector<SUnit *> &DestNodes,
1884 : SetVector<SUnit *> &Exclude,
1885 : SmallPtrSet<SUnit *, 8> &Visited) {
1886 5219 : if (Cur->isBoundaryNode())
1887 : return false;
1888 5219 : if (Exclude.count(Cur) != 0)
1889 : return false;
1890 8898 : if (DestNodes.count(Cur) != 0)
1891 : return true;
1892 3951 : if (!Visited.insert(Cur).second)
1893 1816 : return Path.count(Cur) != 0;
1894 : bool FoundPath = false;
1895 6937 : for (auto &SI : Cur->Succs)
1896 3894 : FoundPath |= computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited);
1897 7901 : for (auto &PI : Cur->Preds)
1898 4858 : if (PI.getKind() == SDep::Anti)
1899 291 : FoundPath |=
1900 291 : computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited);
1901 3043 : if (FoundPath)
1902 693 : Path.insert(Cur);
1903 : return FoundPath;
1904 : }
1905 :
1906 : /// Return true if Set1 is a subset of Set2.
1907 571 : template <class S1Ty, class S2Ty> static bool isSubset(S1Ty &Set1, S2Ty &Set2) {
1908 1034 : for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I)
1909 1004 : if (Set2.count(*I) == 0)
1910 192 : return false;
1911 : return true;
1912 : }
1913 391 :
1914 787 : /// Compute the live-out registers for the instructions in a node-set.
1915 588 : /// The live-out registers are those that are defined in the node-set,
1916 192 : /// but not used. Except for use operands of Phis.
1917 : static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker,
1918 : NodeSet &NS) {
1919 180 : const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1920 247 : MachineRegisterInfo &MRI = MF.getRegInfo();
1921 416 : SmallVector<RegisterMaskPair, 8> LiveOutRegs;
1922 : SmallSet<unsigned, 4> Uses;
1923 : for (SUnit *SU : NS) {
1924 : const MachineInstr *MI = SU->getInstr();
1925 : if (MI->isPHI())
1926 : continue;
1927 : for (const MachineOperand &MO : MI->operands())
1928 : if (MO.isReg() && MO.isUse()) {
1929 83 : unsigned Reg = MO.getReg();
1930 : if (TargetRegisterInfo::isVirtualRegister(Reg))
1931 83 : Uses.insert(Reg);
1932 83 : else if (MRI.isAllocatable(Reg))
1933 : for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1934 83 : Uses.insert(*Units);
1935 645 : }
1936 562 : }
1937 : for (SUnit *SU : NS)
1938 : for (const MachineOperand &MO : SU->getInstr()->operands())
1939 2519 : if (MO.isReg() && MO.isDef() && !MO.isDead()) {
1940 1976 : unsigned Reg = MO.getReg();
1941 1131 : if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1942 1131 : if (!Uses.count(Reg))
1943 1129 : LiveOutRegs.push_back(RegisterMaskPair(Reg,
1944 2 : LaneBitmask::getNone()));
1945 0 : } else if (MRI.isAllocatable(Reg)) {
1946 0 : for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1947 : if (!Uses.count(*Units))
1948 : LiveOutRegs.push_back(RegisterMaskPair(*Units,
1949 645 : LaneBitmask::getNone()));
1950 2633 : }
1951 2071 : }
1952 542 : RPTracker.addLiveRegs(LiveOutRegs);
1953 542 : }
1954 542 :
1955 95 : /// A heuristic to filter nodes in recurrent node-sets if the register
1956 : /// pressure of a set is too high.
1957 0 : void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) {
1958 0 : for (auto &NS : NodeSets) {
1959 0 : // Skip small node-sets since they won't cause register pressure problems.
1960 0 : if (NS.size() <= 2)
1961 : continue;
1962 : IntervalPressure RecRegPressure;
1963 : RegPressureTracker RecRPTracker(RecRegPressure);
1964 83 : RecRPTracker.init(&MF, &RegClassInfo, &LIS, BB, BB->end(), false, true);
1965 83 : computeLiveOuts(MF, RecRPTracker, NS);
1966 : RecRPTracker.closeBottom();
1967 :
1968 : std::vector<SUnit *> SUnits(NS.begin(), NS.end());
1969 188 : llvm::sort(SUnits, [](const SUnit *A, const SUnit *B) {
1970 608 : return A->NodeNum > B->NodeNum;
1971 : });
1972 420 :
1973 337 : for (auto &SU : SUnits) {
1974 : // Since we're computing the register pressure for a subset of the
1975 83 : // instructions in a block, we need to set the tracker for each
1976 166 : // instruction in the node-set. The tracker is set to the instruction
1977 83 : // just after the one we're interested in.
1978 83 : MachineBasicBlock::const_iterator CurInstI = SU->getInstr();
1979 : RecRPTracker.setPos(std::next(CurInstI));
1980 :
1981 : RegPressureDelta RPDelta;
1982 0 : ArrayRef<PressureChange> CriticalPSets;
1983 : RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta,
1984 : CriticalPSets,
1985 639 : RecRegPressure.MaxSetPressure);
1986 : if (RPDelta.Excess.isValid()) {
1987 : LLVM_DEBUG(
1988 : dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") "
1989 : << TRI->getRegPressureSetName(RPDelta.Excess.getPSet())
1990 557 : << ":" << RPDelta.Excess.getUnitInc());
1991 557 : NS.setExceedPressure(SU);
1992 : break;
1993 557 : }
1994 557 : RecRPTracker.recede();
1995 557 : }
1996 : }
1997 : }
1998 557 :
1999 : /// A heuristic to colocate node sets that have the same set of
2000 : /// successors.
2001 : void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) {
2002 : unsigned Colocate = 0;
2003 1 : for (int i = 0, e = NodeSets.size(); i < e; ++i) {
2004 1 : NodeSet &N1 = NodeSets[i];
2005 : SmallSetVector<SUnit *, 8> S1;
2006 556 : if (N1.empty() || !succ_L(N1, S1))
2007 : continue;
2008 : for (int j = i + 1; j < e; ++j) {
2009 188 : NodeSet &N2 = NodeSets[j];
2010 : if (N1.compareRecMII(N2) != 0)
2011 : continue;
2012 : SmallSetVector<SUnit *, 8> S2;
2013 0 : if (N2.empty() || !succ_L(N2, S2))
2014 : continue;
2015 0 : if (isSubset(S1, S2) && S1.size() == S2.size()) {
2016 0 : N1.setColocate(++Colocate);
2017 : N2.setColocate(Colocate);
2018 0 : break;
2019 : }
2020 0 : }
2021 0 : }
2022 0 : }
2023 0 :
2024 : /// Check if the existing node-sets are profitable. If not, then ignore the
2025 0 : /// recurrent node-sets, and attempt to schedule all nodes together. This is
2026 : /// a heuristic. If the MII is large and all the recurrent node-sets are small,
2027 0 : /// then it's best to try to schedule all instructions together instead of
2028 0 : /// starting with the recurrent node-sets.
2029 : void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) {
2030 : // Look for loops with a large MII.
2031 : if (MII < 17)
2032 : return;
2033 : // Check if the node-set contains only a simple add recurrence.
2034 0 : for (auto &NS : NodeSets) {
2035 : if (NS.getRecMII() > 2)
2036 : return;
2037 : if (NS.getMaxDepth() > MII)
2038 : return;
2039 : }
2040 : NodeSets.clear();
2041 0 : LLVM_DEBUG(dbgs() << "Clear recurrence node-sets\n");
2042 : return;
2043 0 : }
2044 0 :
2045 : /// Add the nodes that do not belong to a recurrence set into groups
2046 0 : /// based upon connected componenets.
2047 0 : void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) {
2048 0 : SetVector<SUnit *> NodesAdded;
2049 0 : SmallPtrSet<SUnit *, 8> Visited;
2050 0 : // Add the nodes that are on a path between the previous node sets and
2051 : // the current node set.
2052 : for (NodeSet &I : NodeSets) {
2053 : SmallSetVector<SUnit *, 8> N;
2054 : // Add the nodes from the current node set to the previous node set.
2055 : if (succ_L(I, N)) {
2056 : SetVector<SUnit *> Path;
2057 : for (SUnit *NI : N) {
2058 : Visited.clear();
2059 188 : computePath(NI, Path, NodesAdded, I, Visited);
2060 188 : }
2061 : if (!Path.empty())
2062 : I.insert(Path.begin(), Path.end());
2063 : }
2064 608 : // Add the nodes from the previous node set to the current node set.
2065 : N.clear();
2066 : if (succ_L(NodesAdded, N)) {
2067 420 : SetVector<SUnit *> Path;
2068 315 : for (SUnit *NI : N) {
2069 922 : Visited.clear();
2070 607 : computePath(NI, Path, I, NodesAdded, Visited);
2071 607 : }
2072 : if (!Path.empty())
2073 315 : I.insert(Path.begin(), Path.end());
2074 53 : }
2075 : NodesAdded.insert(I.begin(), I.end());
2076 : }
2077 :
2078 420 : // Create a new node set with the connected nodes of any successor of a node
2079 165 : // in a recurrent set.
2080 592 : NodeSet NewSet;
2081 427 : SmallSetVector<SUnit *, 8> N;
2082 427 : if (succ_L(NodesAdded, N))
2083 : for (SUnit *I : N)
2084 165 : addConnectedNodes(I, NewSet, NodesAdded);
2085 30 : if (!NewSet.empty())
2086 : NodeSets.push_back(NewSet);
2087 420 :
2088 : // Create a new node set with the connected nodes of any predecessor of a node
2089 : // in a recurrent set.
2090 : NewSet.clear();
2091 : if (pred_L(NodesAdded, N))
2092 : for (SUnit *I : N)
2093 : addConnectedNodes(I, NewSet, NodesAdded);
2094 188 : if (!NewSet.empty())
2095 218 : NodeSets.push_back(NewSet);
2096 141 :
2097 188 : // Create new nodes sets with the connected nodes any remaining node that
2098 77 : // has no predecessor.
2099 : for (unsigned i = 0; i < SUnits.size(); ++i) {
2100 : SUnit *SU = &SUnits[i];
2101 : if (NodesAdded.count(SU) == 0) {
2102 : NewSet.clear();
2103 188 : addConnectedNodes(SU, NewSet, NodesAdded);
2104 49 : if (!NewSet.empty())
2105 33 : NodeSets.push_back(NewSet);
2106 188 : }
2107 16 : }
2108 : }
2109 :
2110 : /// Add the node to the set, and add all is its connected nodes to the set.
2111 2221 : void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
2112 : SetVector<SUnit *> &NodesAdded) {
2113 1845 : NewSet.insert(SU);
2114 : NodesAdded.insert(SU);
2115 9 : for (auto &SI : SU->Succs) {
2116 9 : SUnit *Successor = SI.getSUnit();
2117 9 : if (!SI.isArtificial() && NodesAdded.count(Successor) == 0)
2118 : addConnectedNodes(Successor, NewSet, NodesAdded);
2119 : }
2120 188 : for (auto &PI : SU->Preds) {
2121 : SUnit *Predecessor = PI.getSUnit();
2122 : if (!PI.isArtificial() && NodesAdded.count(Predecessor) == 0)
2123 545 : addConnectedNodes(Predecessor, NewSet, NodesAdded);
2124 : }
2125 545 : }
2126 545 :
2127 1219 : /// Return true if Set1 contains elements in Set2. The elements in common
2128 : /// are returned in a different container.
2129 674 : static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2,
2130 196 : SmallSetVector<SUnit *, 8> &Result) {
2131 : Result.clear();
2132 1254 : for (unsigned i = 0, e = Set1.size(); i != e; ++i) {
2133 : SUnit *SU = Set1[i];
2134 709 : if (Set2.count(SU) != 0)
2135 166 : Result.insert(SU);
2136 : }
2137 545 : return !Result.empty();
2138 : }
2139 :
2140 : /// Merge the recurrence node sets that have the same initial node.
2141 306 : void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) {
2142 : for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
2143 306 : ++I) {
2144 628 : NodeSet &NI = *I;
2145 644 : for (NodeSetType::iterator J = I + 1; J != E;) {
2146 : NodeSet &NJ = *J;
2147 63 : if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) {
2148 : if (NJ.compareRecMII(NI) > 0)
2149 306 : NI.setRecMII(NJ.getRecMII());
2150 : for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI;
2151 : ++NII)
2152 : I->insert(*NII);
2153 0 : NodeSets.erase(J);
2154 0 : E = NodeSets.end();
2155 : } else {
2156 : ++J;
2157 0 : }
2158 : }
2159 0 : }
2160 0 : }
2161 :
2162 0 : /// Remove nodes that have been scheduled in previous NodeSets.
2163 : void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) {
2164 0 : for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
2165 0 : ++I)
2166 : for (NodeSetType::iterator J = I + 1; J != E;) {
2167 : J->remove_if([&](SUnit *SUJ) { return I->count(SUJ); });
2168 0 :
2169 : if (J->empty()) {
2170 : NodeSets.erase(J);
2171 : E = NodeSets.end();
2172 0 : } else {
2173 : ++J;
2174 : }
2175 0 : }
2176 0 : }
2177 :
2178 0 : /// Compute an ordered list of the dependence graph nodes, which
2179 2960 : /// indicates the order that the nodes will be scheduled. This is a
2180 : /// two-level algorithm. First, a partial order is created, which
2181 0 : /// consists of a list of sets ordered from highest to lowest priority.
2182 0 : void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) {
2183 : SmallSetVector<SUnit *, 8> R;
2184 : NodeOrder.clear();
2185 0 :
2186 : for (auto &Nodes : NodeSets) {
2187 : LLVM_DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n");
2188 0 : OrderKind Order;
2189 : SmallSetVector<SUnit *, 8> N;
2190 : if (pred_L(NodeOrder, N) && isSubset(N, Nodes)) {
2191 : R.insert(N.begin(), N.end());
2192 : Order = BottomUp;
2193 : LLVM_DEBUG(dbgs() << " Bottom up (preds) ");
2194 188 : } else if (succ_L(NodeOrder, N) && isSubset(N, Nodes)) {
2195 : R.insert(N.begin(), N.end());
2196 188 : Order = TopDown;
2197 : LLVM_DEBUG(dbgs() << " Top down (succs) ");
2198 693 : } else if (isIntersect(N, Nodes, R)) {
2199 : // If some of the successors are in the existing node-set, then use the
2200 : // top-down ordering.
2201 : Order = TopDown;
2202 505 : LLVM_DEBUG(dbgs() << " Top down (intersect) ");
2203 95 : } else if (NodeSets.size() == 1) {
2204 : for (auto &N : Nodes)
2205 : if (N->Succs.size() == 0)
2206 410 : R.insert(N);
2207 104 : Order = BottomUp;
2208 : LLVM_DEBUG(dbgs() << " Bottom up (all) ");
2209 : } else {
2210 306 : // Find the node with the highest ASAP.
2211 : SUnit *maxASAP = nullptr;
2212 : for (SUnit *SU : Nodes) {
2213 : if (maxASAP == nullptr || getASAP(SU) > getASAP(maxASAP) ||
2214 : (getASAP(SU) == getASAP(maxASAP) && SU->NodeNum > maxASAP->NodeNum))
2215 265 : maxASAP = SU;
2216 179 : }
2217 169 : R.insert(maxASAP);
2218 13 : Order = BottomUp;
2219 : LLVM_DEBUG(dbgs() << " Bottom up (default) ");
2220 : }
2221 :
2222 : while (!R.empty()) {
2223 255 : if (Order == TopDown) {
2224 936 : // Choose the node with the maximum height. If more than one, choose
2225 681 : // the node wiTH the maximum ZeroLatencyHeight. If still more than one,
2226 211 : // choose the node with the lowest MOV.
2227 625 : while (!R.empty()) {
2228 : SUnit *maxHeight = nullptr;
2229 255 : for (SUnit *I : R) {
2230 : if (maxHeight == nullptr || getHeight(I) > getHeight(maxHeight))
2231 : maxHeight = I;
2232 : else if (getHeight(I) == getHeight(maxHeight) &&
2233 : getZeroLatencyHeight(I) > getZeroLatencyHeight(maxHeight))
2234 1029 : maxHeight = I;
2235 524 : else if (getHeight(I) == getHeight(maxHeight) &&
2236 : getZeroLatencyHeight(I) ==
2237 : getZeroLatencyHeight(maxHeight) &&
2238 : getMOV(I) < getMOV(maxHeight))
2239 723 : maxHeight = I;
2240 567 : }
2241 2044 : NodeOrder.insert(maxHeight);
2242 2422 : LLVM_DEBUG(dbgs() << maxHeight->NodeNum << " ");
2243 703 : R.remove(maxHeight);
2244 774 : for (const auto &I : maxHeight->Succs) {
2245 968 : if (Nodes.count(I.getSUnit()) == 0)
2246 33 : continue;
2247 1192 : if (NodeOrder.count(I.getSUnit()) != 0)
2248 451 : continue;
2249 741 : if (ignoreDependence(I, false))
2250 : continue;
2251 19 : R.insert(I.getSUnit());
2252 : }
2253 567 : // Back-edges are predecessors with an anti-dependence.
2254 : for (const auto &I : maxHeight->Preds) {
2255 567 : if (I.getKind() != SDep::Anti)
2256 1252 : continue;
2257 : if (Nodes.count(I.getSUnit()) == 0)
2258 155 : continue;
2259 530 : if (NodeOrder.count(I.getSUnit()) != 0)
2260 : continue;
2261 : R.insert(I.getSUnit());
2262 : }
2263 421 : }
2264 : Order = BottomUp;
2265 : LLVM_DEBUG(dbgs() << "\n Switching order to bottom up ");
2266 1415 : SmallSetVector<SUnit *, 8> N;
2267 848 : if (pred_L(NodeOrder, N, &Nodes))
2268 : R.insert(N.begin(), N.end());
2269 : } else {
2270 6 : // Choose the node with the maximum depth. If more than one, choose
2271 60 : // the node with the maximum ZeroLatencyDepth. If still more than one,
2272 : // choose the node with the lowest MOV.
2273 58 : while (!R.empty()) {
2274 : SUnit *maxDepth = nullptr;
2275 : for (SUnit *I : R) {
2276 : if (maxDepth == nullptr || getDepth(I) > getDepth(maxDepth))
2277 : maxDepth = I;
2278 : else if (getDepth(I) == getDepth(maxDepth) &&
2279 156 : getZeroLatencyDepth(I) > getZeroLatencyDepth(maxDepth))
2280 8 : maxDepth = I;
2281 : else if (getDepth(I) == getDepth(maxDepth) &&
2282 : getZeroLatencyDepth(I) == getZeroLatencyDepth(maxDepth) &&
2283 : getMOV(I) < getMOV(maxDepth))
2284 : maxDepth = I;
2285 1645 : }
2286 1278 : NodeOrder.insert(maxDepth);
2287 4354 : LLVM_DEBUG(dbgs() << maxDepth->NodeNum << " ");
2288 4882 : R.remove(maxDepth);
2289 1635 : if (Nodes.isExceedSU(maxDepth)) {
2290 1441 : Order = TopDown;
2291 1608 : R.clear();
2292 48 : R.insert(Nodes.getNode(0));
2293 2149 : break;
2294 1393 : }
2295 : for (const auto &I : maxDepth->Preds) {
2296 172 : if (Nodes.count(I.getSUnit()) == 0)
2297 : continue;
2298 1278 : if (NodeOrder.count(I.getSUnit()) != 0)
2299 : continue;
2300 1278 : R.insert(I.getSUnit());
2301 1278 : }
2302 : // Back-edges are predecessors with an anti-dependence.
2303 : for (const auto &I : maxDepth->Succs) {
2304 1 : if (I.getKind() != SDep::Anti)
2305 1 : continue;
2306 : if (Nodes.count(I.getSUnit()) == 0)
2307 3030 : continue;
2308 : if (NodeOrder.count(I.getSUnit()) != 0)
2309 429 : continue;
2310 1324 : R.insert(I.getSUnit());
2311 : }
2312 1236 : }
2313 : Order = TopDown;
2314 : LLVM_DEBUG(dbgs() << "\n Switching order to top down ");
2315 3194 : SmallSetVector<SUnit *, 8> N;
2316 1917 : if (succ_L(NodeOrder, N, &Nodes))
2317 : R.insert(N.begin(), N.end());
2318 : }
2319 38 : }
2320 263 : LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n");
2321 : }
2322 47 :
2323 : LLVM_DEBUG({
2324 : dbgs() << "Node order: ";
2325 : for (SUnit *I : NodeOrder)
2326 : dbgs() << " " << I->NodeNum << " ";
2327 : dbgs() << "\n";
2328 368 : });
2329 11 : }
2330 :
2331 : /// Process the nodes in the computed order and create the pipelined schedule
2332 : /// of the instructions, if possible. Return true if a schedule is found.
2333 : bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) {
2334 : if (NodeOrder.empty())
2335 : return false;
2336 :
2337 : bool scheduleFound = false;
2338 : // Keep increasing II until a valid schedule is found.
2339 : for (unsigned II = MII; II < MII + 10 && !scheduleFound; ++II) {
2340 : Schedule.reset();
2341 188 : Schedule.setInitiationInterval(II);
2342 : LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n");
2343 :
2344 : SetVector<SUnit *>::iterator NI = NodeOrder.begin();
2345 188 : SetVector<SUnit *>::iterator NE = NodeOrder.end();
2346 188 : do {
2347 : SUnit *SU = *NI;
2348 :
2349 : // Compute the schedule time for the instruction, which is based
2350 : // upon the scheduled time for any predecessors/successors.
2351 452 : int EarlyStart = INT_MIN;
2352 272 : int LateStart = INT_MAX;
2353 272 : // These values are set when the size of the schedule window is limited
2354 : // due to chain dependences.
2355 : int SchedEnd = INT_MAX;
2356 : int SchedStart = INT_MIN;
2357 : Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart,
2358 : II, this);
2359 3030 : LLVM_DEBUG({
2360 : dbgs() << "Inst (" << SU->NodeNum << ") ";
2361 : SU->getInstr()->dump();
2362 : dbgs() << "\n";
2363 3030 : });
2364 3030 : LLVM_DEBUG({
2365 : dbgs() << "\tes: " << EarlyStart << " ls: " << LateStart
2366 : << " me: " << SchedEnd << " ms: " << SchedStart << "\n";
2367 3030 : });
2368 3030 :
2369 3030 : if (EarlyStart > LateStart || SchedEnd < EarlyStart ||
2370 : SchedStart > LateStart)
2371 : scheduleFound = false;
2372 : else if (EarlyStart != INT_MIN && LateStart == INT_MAX) {
2373 : SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1);
2374 : scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
2375 : } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) {
2376 : SchedStart = std::max(SchedStart, LateStart - (int)II + 1);
2377 : scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II);
2378 : } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) {
2379 : SchedEnd =
2380 : std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1));
2381 3030 : // When scheduling a Phi it is better to start at the late cycle and go
2382 2982 : // backwards. The default order may insert the Phi too far away from
2383 : // its first dependence.
2384 2952 : if (SU->getInstr()->isPHI())
2385 698 : scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II);
2386 698 : else
2387 2254 : scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
2388 1498 : } else {
2389 1498 : int FirstCycle = Schedule.getFirstCycle();
2390 756 : scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU),
2391 418 : FirstCycle + getASAP(SU) + II - 1, II);
2392 418 : }
2393 : // Even if we find a schedule, make sure the schedule doesn't exceed the
2394 : // allowable number of stages. We keep trying if this happens.
2395 : if (scheduleFound)
2396 418 : if (SwpMaxStages > -1 &&
2397 335 : Schedule.getMaxStageCount() > (unsigned)SwpMaxStages)
2398 : scheduleFound = false;
2399 83 :
2400 : LLVM_DEBUG({
2401 338 : if (!scheduleFound)
2402 338 : dbgs() << "\tCan't schedule\n";
2403 676 : });
2404 : } while (++NI != NE && scheduleFound);
2405 :
2406 : // If a schedule is found, check if it is a valid schedule too.
2407 2952 : if (scheduleFound)
2408 2940 : scheduleFound = Schedule.isValidSchedule(this);
2409 2940 : }
2410 :
2411 : LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound << "\n");
2412 :
2413 : if (scheduleFound)
2414 : Schedule.finalizeSchedule(this);
2415 : else
2416 3030 : Schedule.reset();
2417 :
2418 : return scheduleFound && Schedule.getMaxStageCount() > 0;
2419 272 : }
2420 175 :
2421 : /// Given a schedule for the loop, generate a new version of the loop,
2422 : /// and replace the old version. This function generates a prolog
2423 : /// that contains the initial iterations in the pipeline, and kernel
2424 : /// loop, and the epilogue that contains the code for the final
2425 180 : /// iterations.
2426 175 : void SwingSchedulerDAG::generatePipelinedLoop(SMSchedule &Schedule) {
2427 : // Create a new basic block for the kernel and add it to the CFG.
2428 5 : MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
2429 :
2430 180 : unsigned MaxStageCount = Schedule.getMaxStageCount();
2431 :
2432 : // Remember the registers that are used in different stages. The index is
2433 : // the iteration, or stage, that the instruction is scheduled in. This is
2434 : // a map between register names in the original block and the names created
2435 : // in each stage of the pipelined loop.
2436 : ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2];
2437 : InstrMapTy InstrMap;
2438 125 :
2439 : SmallVector<MachineBasicBlock *, 4> PrologBBs;
2440 125 : // Generate the prolog instructions that set up the pipeline.
2441 : generateProlog(Schedule, MaxStageCount, KernelBB, VRMap, PrologBBs);
2442 : MF.insert(BB->getIterator(), KernelBB);
2443 :
2444 : // Rearrange the instructions to generate the new, pipelined loop,
2445 : // and update register names as needed.
2446 : for (int Cycle = Schedule.getFirstCycle(),
2447 : LastCycle = Schedule.getFinalCycle();
2448 715 : Cycle <= LastCycle; ++Cycle) {
2449 : std::deque<SUnit *> &CycleInstrs = Schedule.getInstructions(Cycle);
2450 : // This inner loop schedules each instruction in the cycle.
2451 : for (SUnit *CI : CycleInstrs) {
2452 : if (CI->getInstr()->isPHI())
2453 125 : continue;
2454 125 : unsigned StageNum = Schedule.stageScheduled(getSUnit(CI->getInstr()));
2455 : MachineInstr *NewMI = cloneInstr(CI->getInstr(), MaxStageCount, StageNum);
2456 : updateInstruction(NewMI, false, MaxStageCount, StageNum, Schedule, VRMap);
2457 : KernelBB->push_back(NewMI);
2458 347 : InstrMap[NewMI] = CI->getInstr();
2459 125 : }
2460 472 : }
2461 347 :
2462 : // Copy any terminator instructions to the new kernel, and update
2463 1602 : // names as needed.
2464 1255 : for (MachineBasicBlock::iterator I = BB->getFirstTerminator(),
2465 268 : E = BB->instr_end();
2466 987 : I != E; ++I) {
2467 987 : MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
2468 987 : updateInstruction(NewMI, false, MaxStageCount, 0, Schedule, VRMap);
2469 987 : KernelBB->push_back(NewMI);
2470 987 : InstrMap[NewMI] = &*I;
2471 : }
2472 :
2473 : KernelBB->transferSuccessors(BB);
2474 : KernelBB->replaceSuccessor(BB, KernelBB);
2475 :
2476 125 : generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule,
2477 125 : VRMap, InstrMap, MaxStageCount, MaxStageCount, false);
2478 375 : generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule, VRMap,
2479 250 : InstrMap, MaxStageCount, MaxStageCount, false);
2480 250 :
2481 250 : LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump(););
2482 250 :
2483 : SmallVector<MachineBasicBlock *, 4> EpilogBBs;
2484 : // Generate the epilog instructions to complete the pipeline.
2485 125 : generateEpilog(Schedule, MaxStageCount, KernelBB, VRMap, EpilogBBs,
2486 125 : PrologBBs);
2487 :
2488 125 : // We need this step because the register allocation doesn't handle some
2489 : // situations well, so we insert copies to help out.
2490 125 : splitLifetimes(KernelBB, EpilogBBs, Schedule);
2491 :
2492 : // Remove dead instructions due to loop induction variables.
2493 : removeDeadInstructions(KernelBB, EpilogBBs);
2494 :
2495 : // Add branches between prolog and epilog blocks.
2496 : addBranches(PrologBBs, KernelBB, EpilogBBs, Schedule, VRMap);
2497 125 :
2498 : // Remove the original loop since it's no longer referenced.
2499 : for (auto &I : *BB)
2500 : LIS.RemoveMachineInstrFromMaps(I);
2501 : BB->clear();
2502 125 : BB->eraseFromParent();
2503 :
2504 : delete[] VRMap;
2505 125 : }
2506 :
2507 : /// Generate the pipeline prolog code.
2508 125 : void SwingSchedulerDAG::generateProlog(SMSchedule &Schedule, unsigned LastStage,
2509 : MachineBasicBlock *KernelBB,
2510 : ValueMapTy *VRMap,
2511 1630 : MBBVectorTy &PrologBBs) {
2512 1505 : MachineBasicBlock *PreheaderBB = MLI->getLoopFor(BB)->getLoopPreheader();
2513 125 : assert(PreheaderBB != nullptr &&
2514 125 : "Need to add code to handle loops w/o preheader");
2515 : MachineBasicBlock *PredBB = PreheaderBB;
2516 250 : InstrMapTy InstrMap;
2517 125 :
2518 : // Generate a basic block for each stage, not including the last stage,
2519 : // which will be generated in the kernel. Each basic block may contain
2520 125 : // instructions from multiple stages/iterations.
2521 : for (unsigned i = 0; i < LastStage; ++i) {
2522 : // Create and insert the prolog basic block prior to the original loop
2523 : // basic block. The original loop is removed later.
2524 250 : MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
2525 : PrologBBs.push_back(NewBB);
2526 : MF.insert(BB->getIterator(), NewBB);
2527 : NewBB->transferSuccessors(PredBB);
2528 : PredBB->addSuccessor(NewBB);
2529 : PredBB = NewBB;
2530 :
2531 : // Generate instructions for each appropriate stage. Process instructions
2532 : // in original program order.
2533 295 : for (int StageNum = i; StageNum >= 0; --StageNum) {
2534 : for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
2535 : BBE = BB->getFirstTerminator();
2536 170 : BBI != BBE; ++BBI) {
2537 170 : if (Schedule.isScheduledAtStage(getSUnit(&*BBI), (unsigned)StageNum)) {
2538 170 : if (BBI->isPHI())
2539 170 : continue;
2540 170 : MachineInstr *NewMI =
2541 170 : cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum, Schedule);
2542 : updateInstruction(NewMI, false, i, (unsigned)StageNum, Schedule,
2543 : VRMap);
2544 : NewBB->push_back(NewMI);
2545 394 : InstrMap[NewMI] = &*BBI;
2546 224 : }
2547 224 : }
2548 2659 : }
2549 4870 : rewritePhiValues(NewBB, i, Schedule, VRMap, InstrMap);
2550 : LLVM_DEBUG({
2551 259 : dbgs() << "prolog:\n";
2552 : NewBB->dump();
2553 776 : });
2554 776 : }
2555 :
2556 776 : PredBB->replaceSuccessor(BB, KernelBB);
2557 776 :
2558 : // Check if we need to remove the branch from the preheader to the original
2559 : // loop, and replace it with a branch to the new loop.
2560 : unsigned numBranches = TII->removeBranch(*PreheaderBB);
2561 170 : if (numBranches) {
2562 : SmallVector<MachineOperand, 0> Cond;
2563 : TII->insertBranch(*PreheaderBB, PrologBBs[0], nullptr, Cond, DebugLoc());
2564 : }
2565 : }
2566 :
2567 : /// Generate the pipeline epilog code. The epilog code finishes the iterations
2568 125 : /// that were started in either the prolog or the kernel. We create a basic
2569 : /// block for each stage that needs to complete.
2570 : void SwingSchedulerDAG::generateEpilog(SMSchedule &Schedule, unsigned LastStage,
2571 : MachineBasicBlock *KernelBB,
2572 125 : ValueMapTy *VRMap,
2573 125 : MBBVectorTy &EpilogBBs,
2574 : MBBVectorTy &PrologBBs) {
2575 70 : // We need to change the branch from the kernel to the first epilog block, so
2576 : // this call to analyze branch uses the kernel rather than the original BB.
2577 125 : MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
2578 : SmallVector<MachineOperand, 4> Cond;
2579 : bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond);
2580 : assert(!checkBranch && "generateEpilog must be able to analyze the branch");
2581 : if (checkBranch)
2582 125 : return;
2583 :
2584 : MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
2585 : if (*LoopExitI == KernelBB)
2586 : ++LoopExitI;
2587 : assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
2588 : MachineBasicBlock *LoopExitBB = *LoopExitI;
2589 125 :
2590 : MachineBasicBlock *PredBB = KernelBB;
2591 125 : MachineBasicBlock *EpilogStart = LoopExitBB;
2592 : InstrMapTy InstrMap;
2593 125 :
2594 : // Generate a basic block for each stage, not including the last stage,
2595 : // which was generated for the kernel. Each basic block may contain
2596 : // instructions from multiple stages/iterations.
2597 125 : int EpilogStage = LastStage + 1;
2598 : for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
2599 : MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
2600 125 : EpilogBBs.push_back(NewBB);
2601 : MF.insert(BB->getIterator(), NewBB);
2602 :
2603 : PredBB->replaceSuccessor(LoopExitBB, NewBB);
2604 : NewBB->addSuccessor(LoopExitBB);
2605 :
2606 : if (EpilogStart == LoopExitBB)
2607 : EpilogStart = NewBB;
2608 :
2609 125 : // Add instructions to the epilog depending on the current block.
2610 295 : // Process instructions in original program order.
2611 170 : for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
2612 170 : for (auto &BBI : *BB) {
2613 170 : if (BBI.isPHI())
2614 : continue;
2615 170 : MachineInstr *In = &BBI;
2616 170 : if (Schedule.isScheduledAtStage(getSUnit(In), StageNum)) {
2617 : // Instructions with memoperands in the epilog are updated with
2618 170 : // conservative values.
2619 125 : MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0);
2620 : updateInstruction(NewMI, i == 1, EpilogStage, 0, Schedule, VRMap);
2621 : NewBB->push_back(NewMI);
2622 : InstrMap[NewMI] = In;
2623 394 : }
2624 3107 : }
2625 : }
2626 : generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, Schedule,
2627 : VRMap, InstrMap, LastStage, EpilogStage, i == 1);
2628 2353 : generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, Schedule, VRMap,
2629 : InstrMap, LastStage, EpilogStage, i == 1);
2630 : PredBB = NewBB;
2631 643 :
2632 643 : LLVM_DEBUG({
2633 643 : dbgs() << "epilog:\n";
2634 643 : NewBB->dump();
2635 : });
2636 : }
2637 :
2638 340 : // Fix any Phi nodes in the loop exit block.
2639 : for (MachineInstr &MI : *LoopExitBB) {
2640 170 : if (!MI.isPHI())
2641 : break;
2642 170 : for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
2643 : MachineOperand &MO = MI.getOperand(i);
2644 : if (MO.getMBB() == BB)
2645 : MO.setMBB(PredBB);
2646 : }
2647 : }
2648 :
2649 : // Create a branch to the new epilog from the kernel.
2650 : // Remove the original branch and add a new branch to the epilog.
2651 139 : TII->removeBranch(*KernelBB);
2652 : TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc());
2653 : // Add a branch to the loop exit.
2654 45 : if (EpilogBBs.size() > 0) {
2655 31 : MachineBasicBlock *LastEpilogBB = EpilogBBs.back();
2656 31 : SmallVector<MachineOperand, 4> Cond1;
2657 : TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc());
2658 : }
2659 : }
2660 :
2661 : /// Replace all uses of FromReg that appear outside the specified
2662 : /// basic block with ToReg.
2663 125 : static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg,
2664 250 : MachineBasicBlock *MBB,
2665 : MachineRegisterInfo &MRI,
2666 250 : LiveIntervals &LIS) {
2667 125 : for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg),
2668 : E = MRI.use_end();
2669 250 : I != E;) {
2670 : MachineOperand &O = *I;
2671 : ++I;
2672 : if (O.getParent()->getParent() != MBB)
2673 : O.setReg(ToReg);
2674 : }
2675 960 : if (!LIS.hasInterval(ToReg))
2676 : LIS.createEmptyInterval(ToReg);
2677 : }
2678 :
2679 960 : /// Return true if the register has a use that occurs outside the
2680 : /// specified loop.
2681 2324 : static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB,
2682 : MachineRegisterInfo &MRI) {
2683 : for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg),
2684 1364 : E = MRI.use_end();
2685 70 : I != E; ++I)
2686 : if (I->getParent()->getParent() != BB)
2687 : return true;
2688 960 : return false;
2689 960 : }
2690 :
2691 : /// Generate Phis for the specific block in the generated pipelined code.
2692 : /// This function looks at the Phis from the original code to guide the
2693 370 : /// creation of new Phis.
2694 : void SwingSchedulerDAG::generateExistingPhis(
2695 370 : MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
2696 : MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap,
2697 780 : InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
2698 418 : bool IsLast) {
2699 : // Compute the stage number for the initial value of the Phi, which
2700 : // comes from the prolog. The prolog to use depends on to which kernel/
2701 : // epilog that we're adding the Phi.
2702 : unsigned PrologStage = 0;
2703 : unsigned PrevStage = 0;
2704 : bool InKernel = (LastStageNum == CurStageNum);
2705 : if (InKernel) {
2706 295 : PrologStage = LastStageNum - 1;
2707 : PrevStage = CurStageNum;
2708 : } else {
2709 : PrologStage = LastStageNum - (CurStageNum - LastStageNum);
2710 : PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1;
2711 : }
2712 :
2713 : for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
2714 : BBE = BB->getFirstNonPHI();
2715 : BBI != BBE; ++BBI) {
2716 295 : unsigned Def = BBI->getOperand(0).getReg();
2717 295 :
2718 125 : unsigned InitVal = 0;
2719 : unsigned LoopVal = 0;
2720 : getPhiRegs(*BBI, BB, InitVal, LoopVal);
2721 170 :
2722 170 : unsigned PhiOp1 = 0;
2723 : // The Phi value from the loop body typically is defined in the loop, but
2724 : // not always. So, we need to check if the value is defined in the loop.
2725 295 : unsigned PhiOp2 = LoopVal;
2726 295 : if (VRMap[LastStageNum].count(LoopVal))
2727 953 : PhiOp2 = VRMap[LastStageNum][LoopVal];
2728 658 :
2729 : int StageScheduled = Schedule.stageScheduled(getSUnit(&*BBI));
2730 : int LoopValStage =
2731 658 : Schedule.stageScheduled(getSUnit(MRI.getVRegDef(LoopVal)));
2732 658 : unsigned NumStages = Schedule.getStagesForReg(Def, CurStageNum);
2733 : if (NumStages == 0) {
2734 658 : // We don't need to generate a Phi anymore, but we need to rename any uses
2735 : // of the Phi value.
2736 : unsigned NewReg = VRMap[PrevStage][LoopVal];
2737 658 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, 0, &*BBI,
2738 658 : Def, InitVal, NewReg);
2739 650 : if (VRMap[CurStageNum].count(LoopVal))
2740 : VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal];
2741 658 : }
2742 : // Adjust the number of Phis needed depending on the number of prologs left,
2743 658 : // and the distance from where the Phi is first scheduled. The number of
2744 658 : // Phis cannot exceed the number of prolog stages. Each stage can
2745 658 : // potentially define two values.
2746 : unsigned MaxPhis = PrologStage + 2;
2747 : if (!InKernel && (int)PrologStage <= LoopValStage)
2748 5 : MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1);
2749 5 : unsigned NumPhis = std::min(NumStages, MaxPhis);
2750 :
2751 5 : unsigned NewReg = 0;
2752 5 : unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled;
2753 : // In the epilog, we may need to look back one stage to get the correct
2754 : // Phi name because the epilog and prolog blocks execute the same stage.
2755 : // The correct name is from the previous block only when the Phi has
2756 : // been completely scheduled prior to the epilog, and Phi value is not
2757 : // needed in multiple stages.
2758 658 : int StageDiff = 0;
2759 658 : if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 &&
2760 366 : NumPhis == 1)
2761 658 : StageDiff = 1;
2762 : // Adjust the computations below when the phi and the loop definition
2763 : // are scheduled in different stages.
2764 658 : if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage)
2765 : StageDiff = StageScheduled - LoopValStage;
2766 : for (unsigned np = 0; np < NumPhis; ++np) {
2767 : // If the Phi hasn't been scheduled, then use the initial Phi operand
2768 : // value. Otherwise, use the scheduled version of the instruction. This
2769 : // is a little complicated when a Phi references another Phi.
2770 : if (np > PrologStage || StageScheduled >= (int)LastStageNum)
2771 658 : PhiOp1 = InitVal;
2772 368 : // Check if the Phi has already been scheduled in a prolog stage.
2773 : else if (PrologStage >= AccessStage + StageDiff + np &&
2774 : VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0)
2775 : PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal];
2776 658 : // Check if the Phi has already been scheduled, but the loop intruction
2777 1 : // is either another Phi, or doesn't occur in the loop.
2778 1376 : else if (PrologStage >= AccessStage + StageDiff + np) {
2779 : // If the Phi references another Phi, we need to examine the other
2780 : // Phi to get the correct value.
2781 : PhiOp1 = LoopVal;
2782 718 : MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1);
2783 228 : int Indirects = 1;
2784 : while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) {
2785 490 : int PhiStage = Schedule.stageScheduled(getSUnit(InstOp1));
2786 307 : if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects)
2787 279 : PhiOp1 = getInitPhiReg(*InstOp1, BB);
2788 : else
2789 : PhiOp1 = getLoopPhiReg(*InstOp1, BB);
2790 211 : InstOp1 = MRI.getVRegDef(PhiOp1);
2791 : int PhiOpStage = Schedule.stageScheduled(getSUnit(InstOp1));
2792 : int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0);
2793 28 : if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np &&
2794 28 : VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) {
2795 : PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1];
2796 75 : break;
2797 28 : }
2798 28 : ++Indirects;
2799 36 : }
2800 : } else
2801 20 : PhiOp1 = InitVal;
2802 28 : // If this references a generated Phi in the kernel, get the Phi operand
2803 18 : // from the incoming block.
2804 10 : if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1))
2805 28 : if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
2806 10 : PhiOp1 = getInitPhiReg(*InstOp1, KernelBB);
2807 10 :
2808 10 : MachineInstr *PhiInst = MRI.getVRegDef(LoopVal);
2809 : bool LoopDefIsPhi = PhiInst && PhiInst->isPHI();
2810 18 : // In the epilog, a map lookup is needed to get the value from the kernel,
2811 : // or previous epilog block. How is does this depends on if the
2812 : // instruction is scheduled in the previous block.
2813 183 : if (!InKernel) {
2814 : int StageDiffAdj = 0;
2815 : if (LoopValStage != -1 && StageScheduled > LoopValStage)
2816 718 : StageDiffAdj = StageScheduled - LoopValStage;
2817 68 : // Use the loop value defined in the kernel, unless the kernel
2818 8 : // contains the last definition of the Phi.
2819 : if (np == 0 && PrevStage == LastStageNum &&
2820 718 : (StageScheduled != 0 || LoopValStage != 0) &&
2821 718 : VRMap[PrevStage - StageDiffAdj].count(LoopVal))
2822 : PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal];
2823 : // Use the value defined by the Phi. We add one because we switch
2824 : // from looking at the loop value to the Phi definition.
2825 718 : else if (np > 0 && PrevStage == LastStageNum &&
2826 : VRMap[PrevStage - np + 1].count(Def))
2827 428 : PhiOp2 = VRMap[PrevStage - np + 1][Def];
2828 3 : // Use the loop value defined in the kernel.
2829 : else if (static_cast<unsigned>(LoopValStage) > PrologStage + 1 &&
2830 : VRMap[PrevStage - StageDiffAdj - np].count(LoopVal))
2831 696 : PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal];
2832 428 : // Use the value defined by the Phi, unless we're generating the first
2833 104 : // epilog and the Phi refers to a Phi in a different stage.
2834 104 : else if (VRMap[PrevStage - np].count(Def) &&
2835 : (!LoopDefIsPhi || PrevStage != LastStageNum))
2836 : PhiOp2 = VRMap[PrevStage - np][Def];
2837 324 : }
2838 27 :
2839 27 : // Check if we can reuse an existing Phi. This occurs when a Phi
2840 : // references another Phi, and the other Phi is scheduled in an
2841 297 : // earlier stage. We can try to reuse an existing Phi up until the last
2842 38 : // stage of the current Phi.
2843 38 : if (LoopDefIsPhi) {
2844 : if (static_cast<int>(PrologStage - np) >= StageScheduled) {
2845 : int LVNumStages = Schedule.getStagesForPhi(LoopVal);
2846 259 : int StageDiff = (StageScheduled - LoopValStage);
2847 259 : LVNumStages -= StageDiff;
2848 244 : // Make sure the loop value Phi has been processed already.
2849 : if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) {
2850 : NewReg = PhiOp2;
2851 : unsigned ReuseStage = CurStageNum;
2852 : if (Schedule.isLoopCarried(this, *PhiInst))
2853 : ReuseStage -= LVNumStages;
2854 : // Check if the Phi to reuse has been generated yet. If not, then
2855 718 : // there is nothing to reuse.
2856 51 : if (VRMap[ReuseStage - np].count(LoopVal)) {
2857 42 : NewReg = VRMap[ReuseStage - np][LoopVal];
2858 42 :
2859 42 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np,
2860 : &*BBI, Def, NewReg);
2861 42 : // Update the map with the new Phi name.
2862 : VRMap[CurStageNum - np][Def] = NewReg;
2863 : PhiOp2 = NewReg;
2864 0 : if (VRMap[LastStageNum - np - 1].count(LoopVal))
2865 0 : PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal];
2866 :
2867 : if (IsLast && np == NumPhis - 1)
2868 0 : replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
2869 0 : continue;
2870 : }
2871 0 : }
2872 : }
2873 : if (InKernel && StageDiff > 0 &&
2874 0 : VRMap[CurStageNum - StageDiff - np].count(LoopVal))
2875 : PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal];
2876 0 : }
2877 0 :
2878 : const TargetRegisterClass *RC = MRI.getRegClass(Def);
2879 0 : NewReg = MRI.createVirtualRegister(RC);
2880 0 :
2881 0 : MachineInstrBuilder NewPhi =
2882 : BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
2883 : TII->get(TargetOpcode::PHI), NewReg);
2884 : NewPhi.addReg(PhiOp1).addMBB(BB1);
2885 51 : NewPhi.addReg(PhiOp2).addMBB(BB2);
2886 1 : if (np == 0)
2887 1 : InstrMap[NewPhi] = &*BBI;
2888 :
2889 : // We define the Phis after creating the new pipelined code, so
2890 718 : // we need to rename the Phi values in scheduled instructions.
2891 718 :
2892 : unsigned PrevReg = 0;
2893 : if (InKernel && VRMap[PrevStage - np].count(LoopVal))
2894 1436 : PrevReg = VRMap[PrevStage - np][LoopVal];
2895 718 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, &*BBI,
2896 718 : Def, NewReg, PrevReg);
2897 718 : // If the Phi has been scheduled, use the new name for rewriting.
2898 718 : if (VRMap[CurStageNum - np].count(Def)) {
2899 653 : unsigned R = VRMap[CurStageNum - np][Def];
2900 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, &*BBI,
2901 : R, NewReg);
2902 : }
2903 :
2904 : // Check if we need to rename any uses that occurs after the loop. The
2905 718 : // register to replace depends on whether the Phi is scheduled in the
2906 280 : // epilog.
2907 718 : if (IsLast && np == NumPhis - 1)
2908 : replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
2909 :
2910 718 : // In the kernel, a dependent Phi uses the value from this Phi.
2911 38 : if (InKernel)
2912 38 : PhiOp2 = NewReg;
2913 :
2914 : // Update the map with the new Phi name.
2915 : VRMap[CurStageNum - np][Def] = NewReg;
2916 : }
2917 :
2918 : while (NumPhis++ < NumStages) {
2919 718 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, NumPhis,
2920 268 : &*BBI, Def, NewReg, 0);
2921 : }
2922 :
2923 718 : // Check if we need to rename a Phi that has been eliminated due to
2924 : // scheduling.
2925 : if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal))
2926 : replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS);
2927 718 : }
2928 : }
2929 :
2930 668 : /// Generate Phis for the specified block in the generated pipelined code.
2931 10 : /// These are new Phis needed because the definition is scheduled after the
2932 : /// use in the pipelined sequence.
2933 : void SwingSchedulerDAG::generatePhis(
2934 : MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
2935 : MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap,
2936 : InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
2937 658 : bool IsLast) {
2938 0 : // Compute the stage number that contains the initial Phi value, and
2939 : // the Phi from the previous stage.
2940 295 : unsigned PrologStage = 0;
2941 : unsigned PrevStage = 0;
2942 : unsigned StageDiff = CurStageNum - LastStageNum;
2943 : bool InKernel = (StageDiff == 0);
2944 : if (InKernel) {
2945 295 : PrologStage = LastStageNum - 1;
2946 : PrevStage = CurStageNum;
2947 : } else {
2948 : PrologStage = LastStageNum - StageDiff;
2949 : PrevStage = LastStageNum + StageDiff - 1;
2950 : }
2951 :
2952 : for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(),
2953 : BBE = BB->instr_end();
2954 295 : BBI != BBE; ++BBI) {
2955 : for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) {
2956 295 : MachineOperand &MO = BBI->getOperand(i);
2957 125 : if (!MO.isReg() || !MO.isDef() ||
2958 : !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
2959 : continue;
2960 170 :
2961 170 : int StageScheduled = Schedule.stageScheduled(getSUnit(&*BBI));
2962 : assert(StageScheduled != -1 && "Expecting scheduled instruction.");
2963 : unsigned Def = MO.getReg();
2964 295 : unsigned NumPhis = Schedule.getStagesForReg(Def, CurStageNum);
2965 295 : // An instruction scheduled in stage 0 and is used after the loop
2966 3291 : // requires a phi in the epilog for the last definition from either
2967 13248 : // the kernel or prolog.
2968 10252 : if (!InKernel && NumPhis == 0 && StageScheduled == 0 &&
2969 10252 : hasUseAfterLoop(Def, BB, MRI))
2970 3376 : NumPhis = 1;
2971 8401 : if (!InKernel && (unsigned)StageScheduled > PrologStage)
2972 : continue;
2973 2420 :
2974 : unsigned PhiOp2 = VRMap[PrevStage][Def];
2975 2420 : if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2))
2976 2420 : if (InstOp2->isPHI() && InstOp2->getParent() == NewBB)
2977 : PhiOp2 = getLoopPhiReg(*InstOp2, BB2);
2978 : // The number of Phis can't exceed the number of prolog stages. The
2979 : // prolog stage number is zero based.
2980 2790 : if (NumPhis > PrologStage + 1 - StageScheduled)
2981 370 : NumPhis = PrologStage + 1 - StageScheduled;
2982 : for (unsigned np = 0; np < NumPhis; ++np) {
2983 2420 : unsigned PhiOp1 = VRMap[PrologStage][Def];
2984 : if (np <= PrologStage)
2985 : PhiOp1 = VRMap[PrologStage - np][Def];
2986 1851 : if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) {
2987 1851 : if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB)
2988 88 : PhiOp1 = getInitPhiReg(*InstOp1, KernelBB);
2989 : if (InstOp1->isPHI() && InstOp1->getParent() == NewBB)
2990 : PhiOp1 = getInitPhiReg(*InstOp1, NewBB);
2991 : }
2992 1851 : if (!InKernel)
2993 : PhiOp2 = VRMap[PrevStage - np][Def];
2994 2524 :
2995 673 : const TargetRegisterClass *RC = MRI.getRegClass(Def);
2996 673 : unsigned NewReg = MRI.createVirtualRegister(RC);
2997 673 :
2998 673 : MachineInstrBuilder NewPhi =
2999 306 : BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(),
3000 : TII->get(TargetOpcode::PHI), NewReg);
3001 306 : NewPhi.addReg(PhiOp1).addMBB(BB1);
3002 : NewPhi.addReg(PhiOp2).addMBB(BB2);
3003 : if (np == 0)
3004 673 : InstrMap[NewPhi] = &*BBI;
3005 385 :
3006 : // Rewrite uses and update the map. The actions depend upon whether
3007 673 : // we generating code for the kernel or epilog blocks.
3008 673 : if (InKernel) {
3009 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np,
3010 : &*BBI, PhiOp1, NewReg);
3011 1346 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np,
3012 673 : &*BBI, PhiOp2, NewReg);
3013 673 :
3014 673 : PhiOp2 = NewReg;
3015 673 : VRMap[PrevStage - np - 1][Def] = NewReg;
3016 636 : } else {
3017 : VRMap[CurStageNum - np][Def] = NewReg;
3018 : if (np == NumPhis - 1)
3019 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np,
3020 673 : &*BBI, Def, NewReg);
3021 288 : }
3022 : if (IsLast && np == NumPhis - 1)
3023 288 : replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS);
3024 : }
3025 : }
3026 : }
3027 288 : }
3028 :
3029 385 : /// Remove instructions that generate values with no uses.
3030 385 : /// Typically, these are induction variable operations that generate values
3031 365 : /// used in the loop itself. A dead instruction has a definition with
3032 : /// no uses, or uses that occur in the original loop only.
3033 : void SwingSchedulerDAG::removeDeadInstructions(MachineBasicBlock *KernelBB,
3034 673 : MBBVectorTy &EpilogBBs) {
3035 221 : // For each epilog block, check that the value defined by each instruction
3036 : // is used. If not, delete it.
3037 : for (MBBVectorTy::reverse_iterator MBB = EpilogBBs.rbegin(),
3038 : MBE = EpilogBBs.rend();
3039 295 : MBB != MBE; ++MBB)
3040 : for (MachineBasicBlock::reverse_instr_iterator MI = (*MBB)->instr_rbegin(),
3041 : ME = (*MBB)->instr_rend();
3042 : MI != ME;) {
3043 : // From DeadMachineInstructionElem. Don't delete inline assembly.
3044 : if (MI->isInlineAsm()) {
3045 125 : ++MI;
3046 : continue;
3047 : }
3048 : bool SawStore = false;
3049 : // Check if it's safe to remove the instruction due to side effects.
3050 : // We can, and want to, remove Phis here.
3051 295 : if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) {
3052 170 : ++MI;
3053 : continue;
3054 1751 : }
3055 : bool used = true;
3056 1581 : for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
3057 : MOE = MI->operands_end();
3058 523 : MOI != MOE; ++MOI) {
3059 : if (!MOI->isReg() || !MOI->isDef())
3060 1581 : continue;
3061 : unsigned reg = MOI->getReg();
3062 : // Assume physical registers are used, unless they are marked dead.
3063 1581 : if (TargetRegisterInfo::isPhysicalRegister(reg)) {
3064 : used = !MOI->isDead();
3065 268 : if (used)
3066 : break;
3067 : continue;
3068 1252 : }
3069 1313 : unsigned realUses = 0;
3070 2565 : for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(reg),
3071 2310 : EI = MRI.use_end();
3072 : UI != EI; ++UI) {
3073 1313 : // Check if there are any uses that occur only in the original
3074 : // loop. If so, that's not a real use.
3075 1313 : if (UI->getParent()->getParent() != BB) {
3076 0 : realUses++;
3077 0 : used = true;
3078 : break;
3079 : }
3080 : }
3081 : if (realUses > 0)
3082 1313 : break;
3083 : used = false;
3084 1313 : }
3085 : if (!used) {
3086 : LIS.RemoveMachineInstrFromMaps(*MI);
3087 1058 : MI++->eraseFromParent();
3088 : continue;
3089 : }
3090 : ++MI;
3091 : }
3092 : // In the kernel block, check if we can remove a Phi that generates a value
3093 1313 : // used in an instruction removed in the epilog block.
3094 : for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(),
3095 : BBE = KernelBB->getFirstNonPHI();
3096 : BBI != BBE;) {
3097 1313 : MachineInstr *MI = &*BBI;
3098 255 : ++BBI;
3099 255 : unsigned reg = MI->getOperand(0).getReg();
3100 255 : if (MRI.use_begin(reg) == MRI.use_end()) {
3101 : LIS.RemoveMachineInstrFromMaps(*MI);
3102 : MI->eraseFromParent();
3103 : }
3104 : }
3105 : }
3106 :
3107 125 : /// For loop carried definitions, we split the lifetime of a virtual register
3108 703 : /// that has uses past the definition in the next iteration. A copy with a new
3109 : /// virtual register is inserted before the definition, which helps with
3110 : /// generating a better register assignment.
3111 578 : ///
3112 578 : /// v1 = phi(a, v2) v1 = phi(a, v2)
3113 0 : /// v2 = phi(b, v3) v2 = phi(b, v3)
3114 0 : /// v3 = .. v4 = copy v1
3115 : /// .. = V1 v3 = ..
3116 : /// .. = v4
3117 125 : void SwingSchedulerDAG::splitLifetimes(MachineBasicBlock *KernelBB,
3118 : MBBVectorTy &EpilogBBs,
3119 : SMSchedule &Schedule) {
3120 : const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3121 : for (auto &PHI : KernelBB->phis()) {
3122 : unsigned Def = PHI.getOperand(0).getReg();
3123 : // Check for any Phi definition that used as an operand of another Phi
3124 : // in the same block.
3125 : for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def),
3126 : E = MRI.use_instr_end();
3127 : I != E; ++I) {
3128 : if (I->isPHI() && I->getParent() == KernelBB) {
3129 0 : // Get the loop carried definition.
3130 : unsigned LCDef = getLoopPhiReg(PHI, KernelBB);
3131 : if (!LCDef)
3132 0 : continue;
3133 0 : MachineInstr *MI = MRI.getVRegDef(LCDef);
3134 0 : if (!MI || MI->getParent() != KernelBB || MI->isPHI())
3135 : continue;
3136 : // Search through the rest of the block looking for uses of the Phi
3137 0 : // definition. If one occurs, then split the lifetime.
3138 : unsigned SplitReg = 0;
3139 0 : for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI),
3140 0 : KernelBB->instr_end()))
3141 : if (BBJ.readsRegister(Def)) {
3142 : // We split the lifetime when we find the first use.
3143 0 : if (SplitReg == 0) {
3144 0 : SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def));
3145 0 : BuildMI(*KernelBB, MI, MI->getDebugLoc(),
3146 0 : TII->get(TargetOpcode::COPY), SplitReg)
3147 0 : .addReg(Def);
3148 : }
3149 : BBJ.substituteRegister(Def, SplitReg, 0, *TRI);
3150 : }
3151 : if (!SplitReg)
3152 0 : continue;
3153 0 : // Search through each of the epilog blocks for any uses to be renamed.
3154 : for (auto &Epilog : EpilogBBs)
3155 0 : for (auto &I : *Epilog)
3156 0 : if (I.readsRegister(Def))
3157 0 : I.substituteRegister(Def, SplitReg, 0, *TRI);
3158 0 : break;
3159 0 : }
3160 : }
3161 0 : }
3162 : }
3163 0 :
3164 0 : /// Remove the incoming block from the Phis in a basic block.
3165 : static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) {
3166 0 : for (MachineInstr &MI : *BB) {
3167 0 : if (!MI.isPHI())
3168 0 : break;
3169 0 : for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2)
3170 : if (MI.getOperand(i + 1).getMBB() == Incoming) {
3171 : MI.RemoveOperand(i + 1);
3172 : MI.RemoveOperand(i);
3173 : break;
3174 0 : }
3175 : }
3176 : }
3177 41 :
3178 176 : /// Create branches from each prolog basic block to the appropriate epilog
3179 : /// block. These edges are needed if the loop ends before reaching the
3180 : /// kernel.
3181 161 : void SwingSchedulerDAG::addBranches(MBBVectorTy &PrologBBs,
3182 322 : MachineBasicBlock *KernelBB,
3183 135 : MBBVectorTy &EpilogBBs,
3184 135 : SMSchedule &Schedule, ValueMapTy *VRMap) {
3185 135 : assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch");
3186 : MachineInstr *IndVar = Pass.LI.LoopInductionVar;
3187 : MachineInstr *Cmp = Pass.LI.LoopCompare;
3188 41 : MachineBasicBlock *LastPro = KernelBB;
3189 : MachineBasicBlock *LastEpi = KernelBB;
3190 :
3191 : // Start from the blocks connected to the kernel and work "out"
3192 : // to the first prolog and the last epilog blocks.
3193 125 : SmallVector<MachineInstr *, 4> PrevInsts;
3194 : unsigned MaxIter = PrologBBs.size() - 1;
3195 : unsigned LC = UINT_MAX;
3196 : unsigned LCMin = UINT_MAX;
3197 : for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {
3198 125 : // Add branches to the prolog that go to the corresponding
3199 125 : // epilog, and the fall-thru prolog/kernel block.
3200 : MachineBasicBlock *Prolog = PrologBBs[j];
3201 : MachineBasicBlock *Epilog = EpilogBBs[i];
3202 : // We've executed one iteration, so decrement the loop count and check for
3203 : // the loop end.
3204 : SmallVector<MachineOperand, 4> Cond;
3205 : // Check if the LOOP0 has already been removed. If so, then there is no need
3206 125 : // to reduce the trip count.
3207 : if (LC != 0)
3208 : LC = TII->reduceLoopCount(*Prolog, IndVar, *Cmp, Cond, PrevInsts, j,
3209 295 : MaxIter);
3210 :
3211 : // Record the value of the first trip count, which is used to determine if
3212 170 : // branches and blocks can be removed for constant trip counts.
3213 340 : if (LCMin == UINT_MAX)
3214 : LCMin = LC;
3215 :
3216 : unsigned numAdded = 0;
3217 : if (TargetRegisterInfo::isVirtualRegister(LC)) {
3218 : Prolog->addSuccessor(Epilog);
3219 170 : numAdded = TII->insertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc());
3220 338 : } else if (j >= LCMin) {
3221 169 : Prolog->addSuccessor(Epilog);
3222 : Prolog->removeSuccessor(LastPro);
3223 : LastEpi->removeSuccessor(Epilog);
3224 : numAdded = TII->insertBranch(*Prolog, Epilog, nullptr, Cond, DebugLoc());
3225 170 : removePhis(Epilog, LastEpi);
3226 : // Remove the blocks that are no longer referenced.
3227 : if (LastPro != LastEpi) {
3228 : LastEpi->clear();
3229 170 : LastEpi->eraseFromParent();
3230 129 : }
3231 258 : LastPro->clear();
3232 41 : LastPro->eraseFromParent();
3233 5 : } else {
3234 5 : numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc());
3235 5 : removePhis(Epilog, Prolog);
3236 10 : }
3237 5 : LastPro = Prolog;
3238 : LastEpi = Epilog;
3239 5 : for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(),
3240 : E = Prolog->instr_rend();
3241 1 : I != E && numAdded > 0; ++I, --numAdded)
3242 : updateInstruction(&*I, false, j, 0, Schedule, VRMap);
3243 : }
3244 5 : }
3245 :
3246 72 : /// Return true if we can compute the amount the instruction changes
3247 36 : /// during each iteration. Set Delta to the amount of the change.
3248 : bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) {
3249 : const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3250 : unsigned BaseReg;
3251 299 : int64_t Offset;
3252 : if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI))
3253 469 : return false;
3254 299 :
3255 : MachineRegisterInfo &MRI = MF.getRegInfo();
3256 125 : // Check if there is a Phi. If so, get the definition in the loop.
3257 : MachineInstr *BaseDef = MRI.getVRegDef(BaseReg);
3258 : if (BaseDef && BaseDef->isPHI()) {
3259 : BaseReg = getLoopPhiReg(*BaseDef, MI.getParent());
3260 0 : BaseDef = MRI.getVRegDef(BaseReg);
3261 0 : }
3262 : if (!BaseDef)
3263 : return false;
3264 0 :
3265 0 : int D = 0;
3266 : if (!TII->getIncrementValue(*BaseDef, D) && D >= 0)
3267 0 : return false;
3268 :
3269 0 : Delta = D;
3270 0 : return true;
3271 0 : }
3272 0 :
3273 : /// Update the memory operand with a new offset when the pipeliner
3274 0 : /// generates a new copy of the instruction that refers to a
3275 0 : /// different memory location.
3276 : void SwingSchedulerDAG::updateMemOperands(MachineInstr &NewMI,
3277 0 : MachineInstr &OldMI, unsigned Num) {
3278 0 : if (Num == 0)
3279 0 : return;
3280 : // If the instruction has memory operands, then adjust the offset
3281 0 : // when the instruction appears in different stages.
3282 0 : if (NewMI.memoperands_empty())
3283 : return;
3284 : SmallVector<MachineMemOperand *, 2> NewMMOs;
3285 : for (MachineMemOperand *MMO : NewMI.memoperands()) {
3286 : if (MMO->isVolatile() || (MMO->isInvariant() && MMO->isDereferenceable()) ||
3287 : (!MMO->getValue())) {
3288 2406 : NewMMOs.push_back(MMO);
3289 : continue;
3290 2406 : }
3291 1956 : unsigned Delta;
3292 : if (Num != UINT_MAX && computeDelta(OldMI, Delta)) {
3293 : int64_t AdjOffset = Delta * Num;
3294 1419 : NewMMOs.push_back(
3295 : MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize()));
3296 : } else {
3297 930 : NewMMOs.push_back(
3298 1440 : MF.getMachineMemOperand(MMO, 0, MemoryLocation::UnknownSize));
3299 : }
3300 0 : }
3301 0 : NewMI.setMemRefs(MF, NewMMOs);
3302 : }
3303 :
3304 480 : /// Clone the instruction for the new pipelined loop and update the
3305 192 : /// memory operands, if needed.
3306 192 : MachineInstr *SwingSchedulerDAG::cloneInstr(MachineInstr *OldMI,
3307 192 : unsigned CurStageNum,
3308 : unsigned InstStageNum) {
3309 288 : MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
3310 288 : // Check for tied operands in inline asm instructions. This should be handled
3311 : // elsewhere, but I'm not sure of the best solution.
3312 : if (OldMI->isInlineAsm())
3313 450 : for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
3314 : const auto &MO = OldMI->getOperand(i);
3315 : if (MO.isReg() && MO.isUse())
3316 : break;
3317 : unsigned UseIdx;
3318 1630 : if (OldMI->isRegTiedToUseOperand(i, &UseIdx))
3319 : NewMI->tieOperands(i, UseIdx);
3320 : }
3321 1630 : updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
3322 : return NewMI;
3323 : }
3324 1630 :
3325 0 : /// Clone the instruction for the new pipelined loop. If needed, this
3326 0 : /// function updates the instruction using the values saved in the
3327 0 : /// InstrChanges structure.
3328 : MachineInstr *SwingSchedulerDAG::cloneAndChangeInstr(MachineInstr *OldMI,
3329 : unsigned CurStageNum,
3330 0 : unsigned InstStageNum,
3331 0 : SMSchedule &Schedule) {
3332 : MachineInstr *NewMI = MF.CloneMachineInstr(OldMI);
3333 1630 : DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
3334 1630 : InstrChanges.find(getSUnit(OldMI));
3335 : if (It != InstrChanges.end()) {
3336 : std::pair<unsigned, int64_t> RegAndOffset = It->second;
3337 : unsigned BasePos, OffsetPos;
3338 : if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos))
3339 : return nullptr;
3340 776 : int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm();
3341 : MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first);
3342 : if (Schedule.stageScheduled(getSUnit(LoopDef)) > (signed)InstStageNum)
3343 : NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum);
3344 776 : NewMI->getOperand(OffsetPos).setImm(NewOffset);
3345 : }
3346 1552 : updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum);
3347 776 : return NewMI;
3348 26 : }
3349 :
3350 26 : /// Update the machine instruction with new virtual registers. This
3351 0 : /// function may change the defintions and/or uses.
3352 26 : void SwingSchedulerDAG::updateInstruction(MachineInstr *NewMI, bool LastDef,
3353 26 : unsigned CurStageNum,
3354 26 : unsigned InstrStageNum,
3355 26 : SMSchedule &Schedule,
3356 26 : ValueMapTy *VRMap) {
3357 : for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
3358 776 : MachineOperand &MO = NewMI->getOperand(i);
3359 776 : if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
3360 : continue;
3361 : unsigned reg = MO.getReg();
3362 : if (MO.isDef()) {
3363 : // Create a new virtual register for the definition.
3364 2955 : const TargetRegisterClass *RC = MRI.getRegClass(reg);
3365 : unsigned NewReg = MRI.createVirtualRegister(RC);
3366 : MO.setReg(NewReg);
3367 : VRMap[CurStageNum][reg] = NewReg;
3368 : if (LastDef)
3369 12744 : replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS);
3370 9789 : } else if (MO.isUse()) {
3371 9789 : MachineInstr *Def = MRI.getVRegDef(reg);
3372 3091 : // Compute the stage that contains the last definition for instruction.
3373 6698 : int DefStageNum = Schedule.stageScheduled(getSUnit(Def));
3374 6698 : unsigned StageNum = CurStageNum;
3375 : if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) {
3376 2420 : // Compute the difference in stages between the defintion and the use.
3377 2420 : unsigned StageDiff = (InstrStageNum - DefStageNum);
3378 2420 : // Make an adjustment to get the last definition.
3379 2420 : StageNum -= StageDiff;
3380 2420 : }
3381 471 : if (VRMap[StageNum].count(reg))
3382 : MO.setReg(VRMap[StageNum][reg]);
3383 4278 : }
3384 : }
3385 4278 : }
3386 :
3387 4278 : /// Return the instruction in the loop that defines the register.
3388 : /// If the definition is a Phi, then follow the Phi operand to
3389 466 : /// the instruction in the loop.
3390 : MachineInstr *SwingSchedulerDAG::findDefInLoop(unsigned Reg) {
3391 466 : SmallPtrSet<MachineInstr *, 8> Visited;
3392 : MachineInstr *Def = MRI.getVRegDef(Reg);
3393 4278 : while (Def->isPHI()) {
3394 1938 : if (!Visited.insert(Def).second)
3395 : break;
3396 : for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
3397 2955 : if (Def->getOperand(i + 1).getMBB() == BB) {
3398 : Def = MRI.getVRegDef(Def->getOperand(i).getReg());
3399 : break;
3400 : }
3401 : }
3402 0 : return Def;
3403 : }
3404 0 :
3405 : /// Return the new name for the value from the previous stage.
3406 0 : unsigned SwingSchedulerDAG::getPrevMapVal(unsigned StageNum, unsigned PhiStage,
3407 : unsigned LoopVal, unsigned LoopStage,
3408 0 : ValueMapTy *VRMap,
3409 0 : MachineBasicBlock *BB) {
3410 0 : unsigned PrevVal = 0;
3411 0 : if (StageNum > PhiStage) {
3412 : MachineInstr *LoopInst = MRI.getVRegDef(LoopVal);
3413 : if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal))
3414 0 : // The name is defined in the previous stage.
3415 : PrevVal = VRMap[StageNum - 1][LoopVal];
3416 : else if (VRMap[StageNum].count(LoopVal))
3417 : // The previous name is defined in the current stage when the instruction
3418 412 : // order is swapped.
3419 : PrevVal = VRMap[StageNum][LoopVal];
3420 : else if (!LoopInst->isPHI() || LoopInst->getParent() != BB)
3421 : // The loop value hasn't yet been scheduled.
3422 : PrevVal = LoopVal;
3423 412 : else if (StageNum == PhiStage + 1)
3424 69 : // The loop value is another phi, which has not been scheduled.
3425 69 : PrevVal = getInitPhiReg(*LoopInst, BB);
3426 : else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB)
3427 52 : // The loop value is another phi, which has been scheduled.
3428 17 : PrevVal =
3429 : getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB),
3430 : LoopStage, VRMap, BB);
3431 7 : }
3432 10 : return PrevVal;
3433 : }
3434 0 :
3435 10 : /// Rewrite the Phi values in the specified block to use the mappings
3436 : /// from the initial operand. Once the Phi is scheduled, we switch
3437 : /// to using the loop value instead of the Phi value, so those names
3438 0 : /// do not need to be rewritten.
3439 : void SwingSchedulerDAG::rewritePhiValues(MachineBasicBlock *NewBB,
3440 : unsigned StageNum,
3441 0 : SMSchedule &Schedule,
3442 : ValueMapTy *VRMap,
3443 : InstrMapTy &InstrMap) {
3444 412 : for (auto &PHI : BB->phis()) {
3445 : unsigned InitVal = 0;
3446 : unsigned LoopVal = 0;
3447 : getPhiRegs(PHI, BB, InitVal, LoopVal);
3448 : unsigned PhiDef = PHI.getOperand(0).getReg();
3449 :
3450 : unsigned PhiStage =
3451 170 : (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(PhiDef)));
3452 : unsigned LoopStage =
3453 : (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(LoopVal)));
3454 : unsigned NumPhis = Schedule.getStagesForPhi(PhiDef);
3455 : if (NumPhis > StageNum)
3456 730 : NumPhis = StageNum;
3457 : for (unsigned np = 0; np <= NumPhis; ++np) {
3458 : unsigned NewVal =
3459 390 : getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB);
3460 390 : if (!NewVal)
3461 : NewVal = InitVal;
3462 : rewriteScheduledInstr(NewBB, Schedule, InstrMap, StageNum - np, np, &PHI,
3463 390 : PhiDef, NewVal);
3464 : }
3465 780 : }
3466 : }
3467 390 :
3468 : /// Rewrite a previously scheduled instruction to use the register value
3469 802 : /// from the new instruction. Make sure the instruction occurs in the
3470 : /// basic block, and we don't change the uses in the new instruction.
3471 412 : void SwingSchedulerDAG::rewriteScheduledInstr(
3472 412 : MachineBasicBlock *BB, SMSchedule &Schedule, InstrMapTy &InstrMap,
3473 : unsigned CurStageNum, unsigned PhiNum, MachineInstr *Phi, unsigned OldReg,
3474 412 : unsigned NewReg, unsigned PrevReg) {
3475 : bool InProlog = (CurStageNum < Schedule.getMaxStageCount());
3476 : int StagePhi = Schedule.stageScheduled(getSUnit(Phi)) + PhiNum;
3477 : // Rewrite uses that have been scheduled already to use the new
3478 170 : // Phi register.
3479 : for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(OldReg),
3480 : EI = MRI.use_end();
3481 : UI != EI;) {
3482 : MachineOperand &UseOp = *UI;
3483 2124 : MachineInstr *UseMI = UseOp.getParent();
3484 : ++UI;
3485 : if (UseMI->getParent() != BB)
3486 : continue;
3487 2124 : if (UseMI->isPHI()) {
3488 2124 : if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg)
3489 : continue;
3490 : if (getLoopPhiReg(*UseMI, BB) != OldReg)
3491 2124 : continue;
3492 : }
3493 7328 : InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI);
3494 : assert(OrigInstr != InstrMap.end() && "Instruction not scheduled.");
3495 5204 : SUnit *OrigMISU = getSUnit(OrigInstr->second);
3496 : int StageSched = Schedule.stageScheduled(OrigMISU);
3497 5204 : int CycleSched = Schedule.cycleScheduled(OrigMISU);
3498 3346 : unsigned ReplaceReg = 0;
3499 : // This is the stage for the scheduled instruction.
3500 598 : if (StagePhi == StageSched && Phi->isPHI()) {
3501 : int CyclePhi = Schedule.cycleScheduled(getSUnit(Phi));
3502 86 : if (PrevReg && InProlog)
3503 : ReplaceReg = PrevReg;
3504 : else if (PrevReg && !Schedule.isLoopCarried(this, *Phi) &&
3505 1858 : (CyclePhi <= CycleSched || OrigMISU->getInstr()->isPHI()))
3506 : ReplaceReg = PrevReg;
3507 1858 : else
3508 1858 : ReplaceReg = NewReg;
3509 1858 : }
3510 : // The scheduled instruction occurs before the scheduled Phi, and the
3511 : // Phi is not loop carried.
3512 1858 : if (!InProlog && StagePhi + 1 == StageSched &&
3513 977 : !Schedule.isLoopCarried(this, *Phi))
3514 977 : ReplaceReg = NewReg;
3515 : if (StagePhi > StageSched && Phi->isPHI())
3516 977 : ReplaceReg = NewReg;
3517 0 : if (!InProlog && !Phi->isPHI() && StagePhi < StageSched)
3518 : ReplaceReg = NewReg;
3519 : if (ReplaceReg) {
3520 : MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg));
3521 : UseOp.setReg(ReplaceReg);
3522 : }
3523 : }
3524 2594 : }
3525 736 :
3526 : /// Check if we can change the instruction to use an offset value from the
3527 1858 : /// previous iteration. If so, return true and set the base and offset values
3528 : /// so that we can rewrite the load, if necessary.
3529 2559 : /// v1 = Phi(v0, v3)
3530 : /// v2 = load v1, 0
3531 1858 : /// v3 = post_store v1, 4, x
3532 3392 : /// This function enables the load to be rewritten as v2 = load v3, 4.
3533 1696 : bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI,
3534 : unsigned &BasePos,
3535 : unsigned &OffsetPos,
3536 2124 : unsigned &NewBase,
3537 : int64_t &Offset) {
3538 : // Get the load instruction.
3539 : if (TII->isPostIncrement(*MI))
3540 : return false;
3541 : unsigned BasePosLd, OffsetPosLd;
3542 : if (!TII->getBaseAndOffsetPosition(*MI, BasePosLd, OffsetPosLd))
3543 : return false;
3544 : unsigned BaseReg = MI->getOperand(BasePosLd).getReg();
3545 0 :
3546 : // Look for the Phi instruction.
3547 : MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
3548 : MachineInstr *Phi = MRI.getVRegDef(BaseReg);
3549 : if (!Phi || !Phi->isPHI())
3550 : return false;
3551 0 : // Get the register defined in the loop block.
3552 0 : unsigned PrevReg = getLoopPhiReg(*Phi, MI->getParent());
3553 : if (!PrevReg)
3554 0 : return false;
3555 0 :
3556 0 : // Check for the post-increment load/store instruction.
3557 : MachineInstr *PrevDef = MRI.getVRegDef(PrevReg);
3558 : if (!PrevDef || PrevDef == MI)
3559 0 : return false;
3560 0 :
3561 0 : if (!TII->isPostIncrement(*PrevDef))
3562 0 : return false;
3563 :
3564 0 : unsigned BasePos1 = 0, OffsetPos1 = 0;
3565 0 : if (!TII->getBaseAndOffsetPosition(*PrevDef, BasePos1, OffsetPos1))
3566 0 : return false;
3567 :
3568 : // Make sure that the instructions do not access the same memory location in
3569 0 : // the next iteration.
3570 0 : int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm();
3571 0 : int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm();
3572 : MachineInstr *NewMI = MF.CloneMachineInstr(MI);
3573 0 : NewMI->getOperand(OffsetPosLd).setImm(LoadOffset + StoreOffset);
3574 0 : bool Disjoint = TII->areMemAccessesTriviallyDisjoint(*NewMI, *PrevDef);
3575 : MF.DeleteMachineInstr(NewMI);
3576 0 : if (!Disjoint)
3577 0 : return false;
3578 0 :
3579 : // Set the return value once we determine that we return true.
3580 : BasePos = BasePosLd;
3581 : OffsetPos = OffsetPosLd;
3582 0 : NewBase = PrevReg;
3583 0 : Offset = StoreOffset;
3584 0 : return true;
3585 0 : }
3586 0 :
3587 0 : /// Apply changes to the instruction if needed. The changes are need
3588 0 : /// to improve the scheduling and depend up on the final schedule.
3589 0 : void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI,
3590 : SMSchedule &Schedule) {
3591 : SUnit *SU = getSUnit(MI);
3592 0 : DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
3593 0 : InstrChanges.find(SU);
3594 0 : if (It != InstrChanges.end()) {
3595 0 : std::pair<unsigned, int64_t> RegAndOffset = It->second;
3596 0 : unsigned BasePos, OffsetPos;
3597 : if (!TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
3598 : return;
3599 : unsigned BaseReg = MI->getOperand(BasePos).getReg();
3600 : MachineInstr *LoopDef = findDefInLoop(BaseReg);
3601 1633 : int DefStageNum = Schedule.stageScheduled(getSUnit(LoopDef));
3602 : int DefCycleNum = Schedule.cycleScheduled(getSUnit(LoopDef));
3603 : int BaseStageNum = Schedule.stageScheduled(SU);
3604 : int BaseCycleNum = Schedule.cycleScheduled(SU);
3605 1633 : if (BaseStageNum < DefStageNum) {
3606 1633 : MachineInstr *NewMI = MF.CloneMachineInstr(MI);
3607 25 : int OffsetDiff = DefStageNum - BaseStageNum;
3608 : if (DefCycleNum < BaseCycleNum) {
3609 25 : NewMI->getOperand(BasePos).setReg(RegAndOffset.first);
3610 0 : if (OffsetDiff > 0)
3611 25 : --OffsetDiff;
3612 25 : }
3613 25 : int64_t NewOffset =
3614 25 : MI->getOperand(OffsetPos).getImm() + RegAndOffset.second * OffsetDiff;
3615 25 : NewMI->getOperand(OffsetPos).setImm(NewOffset);
3616 25 : SU->setInstr(NewMI);
3617 25 : MISUnitMap[NewMI] = SU;
3618 19 : NewMIs.insert(NewMI);
3619 19 : }
3620 19 : }
3621 4 : }
3622 :
3623 2 : /// Return true for an order or output dependence that is loop carried
3624 : /// potentially. A dependence is loop carried if the destination defines a valu
3625 : /// that may be used or defined by the source in a subsequent iteration.
3626 19 : bool SwingSchedulerDAG::isLoopCarriedDep(SUnit *Source, const SDep &Dep,
3627 19 : bool isSucc) {
3628 : if ((Dep.getKind() != SDep::Order && Dep.getKind() != SDep::Output) ||
3629 19 : Dep.isArtificial())
3630 19 : return false;
3631 :
3632 : if (!SwpPruneLoopCarried)
3633 : return true;
3634 :
3635 : if (Dep.getKind() == SDep::Output)
3636 : return true;
3637 :
3638 4214 : MachineInstr *SI = Source->getInstr();
3639 : MachineInstr *DI = Dep.getSUnit()->getInstr();
3640 4214 : if (!isSucc)
3641 : std::swap(SI, DI);
3642 : assert(SI != nullptr && DI != nullptr && "Expecting SUnit with an MI.");
3643 :
3644 712 : // Assume ordered loads and stores may have a loop carried dependence.
3645 : if (SI->hasUnmodeledSideEffects() || DI->hasUnmodeledSideEffects() ||
3646 : SI->hasOrderedMemoryRef() || DI->hasOrderedMemoryRef())
3647 710 : return true;
3648 :
3649 : // Only chain dependences between a load and store can be loop carried.
3650 710 : if (!DI->mayStore() || !SI->mayLoad())
3651 710 : return false;
3652 710 :
3653 : unsigned DeltaS, DeltaD;
3654 : if (!computeDelta(*SI, DeltaS) || !computeDelta(*DI, DeltaD))
3655 : return true;
3656 :
3657 2124 : unsigned BaseRegS, BaseRegD;
3658 2124 : int64_t OffsetS, OffsetD;
3659 3 : const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3660 : if (!TII->getMemOpBaseRegImmOfs(*SI, BaseRegS, OffsetS, TRI) ||
3661 : !TII->getMemOpBaseRegImmOfs(*DI, BaseRegD, OffsetD, TRI))
3662 707 : return true;
3663 104 :
3664 : if (BaseRegS != BaseRegD)
3665 : return true;
3666 603 :
3667 218 : // Check that the base register is incremented by a constant value for each
3668 : // iteration.
3669 : MachineInstr *Def = MRI.getVRegDef(BaseRegS);
3670 : if (!Def || !Def->isPHI())
3671 385 : return true;
3672 770 : unsigned InitVal = 0;
3673 385 : unsigned LoopVal = 0;
3674 0 : getPhiRegs(*Def, BB, InitVal, LoopVal);
3675 : MachineInstr *LoopDef = MRI.getVRegDef(LoopVal);
3676 385 : int D = 0;
3677 : if (!LoopDef || !TII->getIncrementValue(*LoopDef, D))
3678 : return true;
3679 :
3680 : uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize();
3681 118 : uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize();
3682 118 :
3683 : // This is the main test, which checks the offset values and the loop
3684 : // increment value to determine if the accesses may be loop carried.
3685 : if (OffsetS >= OffsetD)
3686 118 : return OffsetS + AccessSizeS > DeltaS;
3687 118 : else
3688 118 : return OffsetD + AccessSizeD > DeltaD;
3689 118 :
3690 0 : return true;
3691 : }
3692 118 :
3693 118 : void SwingSchedulerDAG::postprocessDAG() {
3694 : for (auto &M : Mutations)
3695 : M->apply(this);
3696 : }
3697 118 :
3698 72 : /// Try to schedule the node at the specified StartCycle and continue
3699 : /// until the node is schedule or the EndCycle is reached. This function
3700 46 : /// returns true if the node is scheduled. This routine may search either
3701 : /// forward or backward for a place to insert the instruction based upon
3702 : /// the relative values of StartCycle and EndCycle.
3703 : bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) {
3704 : bool forward = true;
3705 : if (StartCycle > EndCycle)
3706 760 : forward = false;
3707 570 :
3708 : // The terminating condition depends on the direction.
3709 : int termCycle = forward ? EndCycle + 1 : EndCycle - 1;
3710 : for (int curCycle = StartCycle; curCycle != termCycle;
3711 : forward ? ++curCycle : --curCycle) {
3712 :
3713 : // Add the already scheduled instructions at the specified cycle to the DFA.
3714 : Resources->clearResources();
3715 2952 : for (int checkCycle = FirstCycle + ((curCycle - FirstCycle) % II);
3716 : checkCycle <= LastCycle; checkCycle += II) {
3717 2952 : std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[checkCycle];
3718 :
3719 : for (std::deque<SUnit *>::iterator I = cycleInstrs.begin(),
3720 : E = cycleInstrs.end();
3721 2952 : I != E; ++I) {
3722 4686 : if (ST.getInstrInfo()->isZeroCost((*I)->getInstr()->getOpcode()))
3723 : continue;
3724 : assert(Resources->canReserveResources(*(*I)->getInstr()) &&
3725 : "These instructions have already been scheduled.");
3726 : Resources->reserveResources(*(*I)->getInstr());
3727 3807 : }
3728 8642 : }
3729 4835 : if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) ||
3730 : Resources->canReserveResources(*SU->getInstr())) {
3731 : LLVM_DEBUG({
3732 : dbgs() << "\tinsert at cycle " << curCycle << " ";
3733 10479 : SU->getInstr()->dump();
3734 5644 : });
3735 :
3736 : ScheduledInstrs[curCycle].push_back(SU);
3737 : InstrToCycle.insert(std::make_pair(SU, curCycle));
3738 4339 : if (curCycle > LastCycle)
3739 : LastCycle = curCycle;
3740 : if (curCycle < FirstCycle)
3741 7045 : FirstCycle = curCycle;
3742 3238 : return true;
3743 : }
3744 : LLVM_DEBUG({
3745 : dbgs() << "\tfailed to insert at cycle " << curCycle << " ";
3746 : SU->getInstr()->dump();
3747 : });
3748 2940 : }
3749 2940 : return false;
3750 2940 : }
3751 424 :
3752 2940 : // Return the cycle of the earliest scheduled instruction in the chain.
3753 110 : int SMSchedule::earliestCycleInChain(const SDep &Dep) {
3754 2940 : SmallPtrSet<SUnit *, 8> Visited;
3755 : SmallVector<SDep, 8> Worklist;
3756 : Worklist.push_back(Dep);
3757 : int EarlyCycle = INT_MAX;
3758 : while (!Worklist.empty()) {
3759 : const SDep &Cur = Worklist.pop_back_val();
3760 : SUnit *PrevSU = Cur.getSUnit();
3761 12 : if (Visited.count(PrevSU))
3762 : continue;
3763 : std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(PrevSU);
3764 : if (it == InstrToCycle.end())
3765 16 : continue;
3766 : EarlyCycle = std::min(EarlyCycle, it->second);
3767 : for (const auto &PI : PrevSU->Preds)
3768 16 : if (PI.getKind() == SDep::Order || Dep.getKind() == SDep::Output)
3769 16 : Worklist.push_back(PI);
3770 33 : Visited.insert(PrevSU);
3771 17 : }
3772 17 : return EarlyCycle;
3773 17 : }
3774 1 :
3775 : // Return the cycle of the latest scheduled instruction in the chain.
3776 17 : int SMSchedule::latestCycleInChain(const SDep &Dep) {
3777 : SmallPtrSet<SUnit *, 8> Visited;
3778 16 : SmallVector<SDep, 8> Worklist;
3779 41 : Worklist.push_back(Dep);
3780 25 : int LateCycle = INT_MIN;
3781 1 : while (!Worklist.empty()) {
3782 16 : const SDep &Cur = Worklist.pop_back_val();
3783 : SUnit *SuccSU = Cur.getSUnit();
3784 16 : if (Visited.count(SuccSU))
3785 : continue;
3786 : std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SuccSU);
3787 : if (it == InstrToCycle.end())
3788 356 : continue;
3789 : LateCycle = std::max(LateCycle, it->second);
3790 : for (const auto &SI : SuccSU->Succs)
3791 356 : if (SI.getKind() == SDep::Order || Dep.getKind() == SDep::Output)
3792 356 : Worklist.push_back(SI);
3793 1093 : Visited.insert(SuccSU);
3794 737 : }
3795 737 : return LateCycle;
3796 737 : }
3797 140 :
3798 : /// If an instruction has a use that spans multiple iterations, then
3799 633 : /// return true. These instructions are characterized by having a back-ege
3800 : /// to a Phi, which contains a reference to another Phi.
3801 597 : static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) {
3802 1127 : for (auto &P : SU->Preds)
3803 530 : if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI())
3804 381 : for (auto &S : P.getSUnit()->Succs)
3805 597 : if (S.getKind() == SDep::Data && S.getSUnit()->getInstr()->isPHI())
3806 : return P.getSUnit();
3807 356 : return nullptr;
3808 : }
3809 :
3810 : /// Compute the scheduling start slot for the instruction. The start slot
3811 : /// depends on any predecessor or successor nodes scheduled already.
3812 : void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
3813 0 : int *MinEnd, int *MaxStart, int II,
3814 0 : SwingSchedulerDAG *DAG) {
3815 0 : // Iterate over each instruction that has been scheduled already. The start
3816 0 : // slot computation depends on whether the previously scheduled instruction
3817 0 : // is a predecessor or successor of the specified instruction.
3818 : for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) {
3819 :
3820 : // Iterate over each instruction in the current cycle.
3821 : for (SUnit *I : getInstructions(cycle)) {
3822 : // Because we're processing a DAG for the dependences, we recognize
3823 : // the back-edge in recurrences by anti dependences.
3824 3030 : for (unsigned i = 0, e = (unsigned)SU->Preds.size(); i != e; ++i) {
3825 : const SDep &Dep = SU->Preds[i];
3826 : if (Dep.getSUnit() == I) {
3827 : if (!DAG->isBackedge(SU, Dep)) {
3828 : int EarlyStart = cycle + Dep.getLatency() -
3829 : DAG->getDistance(Dep.getSUnit(), SU, Dep) * II;
3830 26824 : *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
3831 : if (DAG->isLoopCarriedDep(SU, Dep, false)) {
3832 : int End = earliestCycleInChain(Dep) + (II - 1);
3833 73425 : *MinEnd = std::min(*MinEnd, End);
3834 : }
3835 : } else {
3836 63805 : int LateStart = cycle - Dep.getLatency() +
3837 37968 : DAG->getDistance(SU, Dep.getSUnit(), Dep) * II;
3838 37968 : *MinLateStart = std::min(*MinLateStart, LateStart);
3839 1109 : }
3840 1063 : }
3841 1063 : // For instruction that requires multiple iterations, make sure that
3842 1063 : // the dependent instruction is not scheduled past the definition.
3843 1063 : SUnit *BE = multipleIterations(I, DAG);
3844 16 : if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() &&
3845 16 : !SU->isPred(I))
3846 : *MinLateStart = std::min(*MinLateStart, cycle);
3847 : }
3848 46 : for (unsigned i = 0, e = (unsigned)SU->Succs.size(); i != e; ++i) {
3849 46 : if (SU->Succs[i].getSUnit() == I) {
3850 46 : const SDep &Dep = SU->Succs[i];
3851 : if (!DAG->isBackedge(SU, Dep)) {
3852 : int LateStart = cycle - Dep.getLatency() +
3853 : DAG->getDistance(SU, Dep.getSUnit(), Dep) * II;
3854 : *MinLateStart = std::min(*MinLateStart, LateStart);
3855 37968 : if (DAG->isLoopCarriedDep(SU, Dep)) {
3856 37977 : int Start = latestCycleInChain(Dep) + 1 - II;
3857 : *MaxStart = std::max(*MaxStart, Start);
3858 9 : }
3859 : } else {
3860 65665 : int EarlyStart = cycle + Dep.getLatency() -
3861 79656 : DAG->getDistance(Dep.getSUnit(), SU, Dep) * II;
3862 : *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
3863 3007 : }
3864 2641 : }
3865 2641 : }
3866 2641 : }
3867 2641 : }
3868 356 : }
3869 356 :
3870 : /// Order the instructions within a cycle so that the definitions occur
3871 : /// before the uses. Returns true if the instruction is added to the start
3872 366 : /// of the list, or false if added to the end.
3873 366 : void SMSchedule::orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
3874 366 : std::deque<SUnit *> &Insts) {
3875 : MachineInstr *MI = SU->getInstr();
3876 : bool OrderBeforeUse = false;
3877 : bool OrderAfterDef = false;
3878 : bool OrderBeforeDef = false;
3879 : unsigned MoveDef = 0;
3880 3030 : unsigned MoveUse = 0;
3881 : int StageInst1 = stageScheduled(SU);
3882 :
3883 : unsigned Pos = 0;
3884 : for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E;
3885 1398 : ++I, ++Pos) {
3886 : for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
3887 1398 : MachineOperand &MO = MI->getOperand(i);
3888 : if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
3889 : continue;
3890 :
3891 : unsigned Reg = MO.getReg();
3892 : unsigned BasePos, OffsetPos;
3893 1398 : if (ST.getInstrInfo()->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
3894 : if (MI->getOperand(BasePos).getReg() == Reg)
3895 : if (unsigned NewReg = SSD->getInstrBaseReg(SU))
3896 2825 : Reg = NewReg;
3897 : bool Reads, Writes;
3898 6127 : std::tie(Reads, Writes) =
3899 4700 : (*I)->getInstr()->readsWritesVirtualRegister(Reg);
3900 4700 : if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) {
3901 1045 : OrderBeforeUse = true;
3902 : if (MoveUse == 0)
3903 : MoveUse = Pos;
3904 : } else if (MO.isDef() && Reads && stageScheduled(*I) > StageInst1) {
3905 3655 : // Add the instruction after the scheduled instruction.
3906 1818 : OrderAfterDef = true;
3907 487 : MoveDef = Pos;
3908 : } else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) {
3909 : if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) {
3910 : OrderBeforeUse = true;
3911 3655 : if (MoveUse == 0)
3912 3877 : MoveUse = Pos;
3913 : } else {
3914 97 : OrderAfterDef = true;
3915 : MoveDef = Pos;
3916 3683 : }
3917 : } else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) {
3918 : OrderBeforeUse = true;
3919 : if (MoveUse == 0)
3920 3552 : MoveUse = Pos;
3921 84 : if (MoveUse != 0) {
3922 : OrderAfterDef = true;
3923 0 : MoveDef = Pos - 1;
3924 : }
3925 : } else if (MO.isUse() && Writes && stageScheduled(*I) < StageInst1) {
3926 : // Add the instruction before the scheduled instruction.
3927 : OrderBeforeUse = true;
3928 : if (MoveUse == 0)
3929 3468 : MoveUse = Pos;
3930 : } else if (MO.isUse() && stageScheduled(*I) == StageInst1 &&
3931 28 : isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) {
3932 : if (MoveUse == 0) {
3933 28 : OrderBeforeDef = true;
3934 : MoveUse = Pos;
3935 12 : }
3936 : }
3937 3412 : }
3938 : // Check for order dependences between instructions. Make sure the source
3939 : // is ordered before the destination.
3940 49 : for (auto &S : SU->Succs) {
3941 : if (S.getSUnit() != *I)
3942 6635 : continue;
3943 1196 : if (S.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) {
3944 98 : OrderBeforeUse = true;
3945 : if (Pos < MoveUse)
3946 : MoveUse = Pos;
3947 : }
3948 : }
3949 : for (auto &P : SU->Preds) {
3950 : if (P.getSUnit() != *I)
3951 : continue;
3952 2993 : if (P.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) {
3953 1566 : OrderAfterDef = true;
3954 : MoveDef = Pos;
3955 266 : }
3956 : }
3957 6 : }
3958 :
3959 : // A circular dependence.
3960 : if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef)
3961 3467 : OrderBeforeUse = false;
3962 2040 :
3963 : // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due
3964 99 : // to a loop-carried dependence.
3965 : if (OrderBeforeDef)
3966 : OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef);
3967 :
3968 : // The uncommon case when the instruction order needs to be updated because
3969 : // there is both a use and def.
3970 : if (OrderBeforeUse && OrderAfterDef) {
3971 : SUnit *UseSU = Insts.at(MoveUse);
3972 1398 : SUnit *DefSU = Insts.at(MoveDef);
3973 : if (MoveUse > MoveDef) {
3974 : Insts.erase(Insts.begin() + MoveUse);
3975 : Insts.erase(Insts.begin() + MoveDef);
3976 : } else {
3977 1398 : Insts.erase(Insts.begin() + MoveDef);
3978 97 : Insts.erase(Insts.begin() + MoveUse);
3979 : }
3980 : orderDependence(SSD, UseSU, Insts);
3981 : orderDependence(SSD, SU, Insts);
3982 1398 : orderDependence(SSD, DefSU, Insts);
3983 47 : return;
3984 47 : }
3985 47 : // Put the new instruction first if there is a use in the list. Otherwise,
3986 86 : // put it at the end of the list.
3987 129 : if (OrderBeforeUse)
3988 : Insts.push_front(SU);
3989 8 : else
3990 12 : Insts.push_back(SU);
3991 : }
3992 47 :
3993 47 : /// Return true if the scheduled Phi has a loop carried operand.
3994 47 : bool SMSchedule::isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi) {
3995 47 : if (!Phi.isPHI())
3996 : return false;
3997 : assert(Phi.isPHI() && "Expecting a Phi.");
3998 : SUnit *DefSU = SSD->getSUnit(&Phi);
3999 1351 : unsigned DefCycle = cycleScheduled(DefSU);
4000 : int DefStage = stageScheduled(DefSU);
4001 :
4002 : unsigned InitVal = 0;
4003 : unsigned LoopVal = 0;
4004 : getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
4005 : SUnit *UseSU = SSD->getSUnit(MRI.getVRegDef(LoopVal));
4006 2149 : if (!UseSU)
4007 : return true;
4008 : if (UseSU->getInstr()->isPHI())
4009 : return true;
4010 : unsigned LoopCycle = cycleScheduled(UseSU);
4011 1517 : int LoopStage = stageScheduled(UseSU);
4012 1517 : return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
4013 : }
4014 :
4015 : /// Return true if the instruction is a definition that is loop carried
4016 1517 : /// and defines the use on the next iteration.
4017 1517 : /// v1 = phi(v2, v3)
4018 1515 : /// (Def) v3 = op v1
4019 2 : /// (MO) = v1
4020 1515 : /// If MO appears before Def, then then v1 and v3 may get assigned to the same
4021 : /// register.
4022 1469 : bool SMSchedule::isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD,
4023 1469 : MachineInstr *Def, MachineOperand &MO) {
4024 1469 : if (!MO.isReg())
4025 : return false;
4026 : if (Def->isPHI())
4027 : return false;
4028 : MachineInstr *Phi = MRI.getVRegDef(MO.getReg());
4029 : if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent())
4030 : return false;
4031 : if (!isLoopCarried(SSD, *Phi))
4032 : return false;
4033 : unsigned LoopReg = getLoopPhiReg(*Phi, Phi->getParent());
4034 1196 : for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) {
4035 : MachineOperand &DMO = Def->getOperand(i);
4036 1196 : if (!DMO.isReg() || !DMO.isDef())
4037 : continue;
4038 : if (DMO.getReg() == LoopReg)
4039 : return true;
4040 1196 : }
4041 1561 : return false;
4042 : }
4043 348 :
4044 : // Check if the generated schedule is valid. This function checks if
4045 328 : // an instruction that uses a physical register is scheduled in a
4046 1093 : // different stage than the definition. The pipeliner does not handle
4047 863 : // physical register values that may cross a basic block boundary.
4048 863 : bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) {
4049 : for (int i = 0, e = SSD->SUnits.size(); i < e; ++i) {
4050 327 : SUnit &SU = SSD->SUnits[i];
4051 : if (!SU.hasPhysRegDefs)
4052 : continue;
4053 : int StageDef = stageScheduled(&SU);
4054 : assert(StageDef != -1 && "Instruction should have been scheduled.");
4055 : for (auto &SI : SU.Succs)
4056 : if (SI.isAssignedRegDep())
4057 : if (ST.getRegisterInfo()->isPhysicalRegister(SI.getReg()))
4058 : if (stageScheduled(SI.getSUnit()) != StageDef)
4059 : return false;
4060 175 : }
4061 1983 : return true;
4062 1633 : }
4063 1633 :
4064 : /// A property of the node order in swing-modulo-scheduling is
4065 0 : /// that for nodes outside circuits the following holds:
4066 : /// none of them is scheduled after both a successor and a
4067 0 : /// predecessor.
4068 : /// The method below checks whether the property is met.
4069 0 : /// If not, debug information is printed and statistics information updated.
4070 0 : /// Note that we do not use an assert statement.
4071 : /// The reason is that although an invalid node oder may prevent
4072 : /// the pipeliner from finding a pipelined schedule for arbitrary II,
4073 : /// it does not lead to the generation of incorrect code.
4074 : void SwingSchedulerDAG::checkValidNodeOrder(const NodeSetType &Circuits) const {
4075 :
4076 : // a sorted vector that maps each SUnit to its index in the NodeOrder
4077 : typedef std::pair<SUnit *, unsigned> UnitIndex;
4078 : std::vector<UnitIndex> Indices(NodeOrder.size(), std::make_pair(nullptr, 0));
4079 :
4080 : for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i)
4081 : Indices.push_back(std::make_pair(NodeOrder[i], i));
4082 :
4083 : auto CompareKey = [](UnitIndex i1, UnitIndex i2) {
4084 : return std::get<0>(i1) < std::get<0>(i2);
4085 : };
4086 188 :
4087 : // sort, so that we can perform a binary search
4088 : llvm::sort(Indices, CompareKey);
4089 :
4090 188 : bool Valid = true;
4091 : (void)Valid;
4092 2033 : // for each SUnit in the NodeOrder, check whether
4093 3690 : // it appears after both a successor and a predecessor
4094 : // of the SUnit. If this is the case, and the SUnit
4095 : // is not part of circuit, then the NodeOrder is not
4096 0 : // valid.
4097 : for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i) {
4098 : SUnit *SU = NodeOrder[i];
4099 : unsigned Index = i;
4100 :
4101 : bool PredBefore = false;
4102 : bool SuccBefore = false;
4103 :
4104 : SUnit *Succ;
4105 : SUnit *Pred;
4106 : (void)Succ;
4107 : (void)Pred;
4108 :
4109 2033 : for (SDep &PredEdge : SU->Preds) {
4110 3690 : SUnit *PredSU = PredEdge.getSUnit();
4111 : unsigned PredIndex =
4112 : std::get<1>(*std::lower_bound(Indices.begin(), Indices.end(),
4113 : std::make_pair(PredSU, 0), CompareKey));
4114 : if (!PredSU->getInstr()->isPHI() && PredIndex < Index) {
4115 : PredBefore = true;
4116 : Pred = PredSU;
4117 : break;
4118 : }
4119 : }
4120 :
4121 3761 : for (SDep &SuccEdge : SU->Succs) {
4122 : SUnit *SuccSU = SuccEdge.getSUnit();
4123 : unsigned SuccIndex =
4124 : std::get<1>(*std::lower_bound(Indices.begin(), Indices.end(),
4125 2256 : std::make_pair(SuccSU, 0), CompareKey));
4126 3572 : if (!SuccSU->getInstr()->isPHI() && SuccIndex < Index) {
4127 : SuccBefore = true;
4128 : Succ = SuccSU;
4129 : break;
4130 : }
4131 : }
4132 :
4133 2420 : if (PredBefore && SuccBefore && !SU->getInstr()->isPHI()) {
4134 : // instructions in circuits are allowed to be scheduled
4135 : // after both a successor and predecessor.
4136 : bool InCircuit = std::any_of(
4137 1703 : Circuits.begin(), Circuits.end(),
4138 3396 : [SU](const NodeSet &Circuit) { return Circuit.count(SU); });
4139 : if (InCircuit)
4140 : LLVM_DEBUG(dbgs() << "In a circuit, predecessor ";);
4141 : else {
4142 : Valid = false;
4143 : NumNodeOrderIssues++;
4144 : LLVM_DEBUG(dbgs() << "Predecessor ";);
4145 1845 : }
4146 : LLVM_DEBUG(dbgs() << Pred->NodeNum << " and successor " << Succ->NodeNum
4147 : << " are scheduled before node " << SU->NodeNum
4148 : << "\n";);
4149 : }
4150 : }
4151 :
4152 : LLVM_DEBUG({
4153 : if (!Valid)
4154 : dbgs() << "Invalid node order found!\n";
4155 : });
4156 : }
4157 :
4158 : /// Attempt to fix the degenerate cases when the instruction serialization
4159 : /// causes the register lifetimes to overlap. For example,
4160 : /// p' = store_pi(p, b)
4161 : /// = load p, offset
4162 : /// In this case p and p' overlap, which means that two registers are needed.
4163 : /// Instead, this function changes the load to use p' and updates the offset.
4164 : void SwingSchedulerDAG::fixupRegisterOverlaps(std::deque<SUnit *> &Instrs) {
4165 : unsigned OverlapReg = 0;
4166 : unsigned NewBaseReg = 0;
4167 : for (SUnit *SU : Instrs) {
4168 188 : MachineInstr *MI = SU->getInstr();
4169 : for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
4170 : const MachineOperand &MO = MI->getOperand(i);
4171 : // Look for an instruction that uses p. The instruction occurs in the
4172 : // same cycle but occurs later in the serialized order.
4173 : if (MO.isReg() && MO.isUse() && MO.getReg() == OverlapReg) {
4174 : // Check that the instruction appears in the InstrChanges structure,
4175 : // which contains instructions that can have the offset updated.
4176 500 : DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
4177 : InstrChanges.find(SU);
4178 : if (It != InstrChanges.end()) {
4179 2133 : unsigned BasePos, OffsetPos;
4180 1633 : // Update the base register and adjust the offset.
4181 6817 : if (TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos)) {
4182 5434 : MachineInstr *NewMI = MF.CloneMachineInstr(MI);
4183 : NewMI->getOperand(BasePos).setReg(NewBaseReg);
4184 : int64_t NewOffset =
4185 5434 : MI->getOperand(OffsetPos).getImm() - It->second.second;
4186 : NewMI->getOperand(OffsetPos).setImm(NewOffset);
4187 : SU->setInstr(NewMI);
4188 : MISUnitMap[NewMI] = SU;
4189 2 : NewMIs.insert(NewMI);
4190 2 : }
4191 : }
4192 : OverlapReg = 0;
4193 2 : NewBaseReg = 0;
4194 2 : break;
4195 4 : }
4196 : // Look for an instruction of the form p' = op(p), which uses and defines
4197 2 : // two virtual registers that get allocated to the same physical register.
4198 2 : unsigned TiedUseIdx = 0;
4199 : if (MI->isRegTiedToUseOperand(i, &TiedUseIdx)) {
4200 2 : // OverlapReg is p in the example above.
4201 2 : OverlapReg = MI->getOperand(TiedUseIdx).getReg();
4202 : // NewBaseReg is p' in the example above.
4203 : NewBaseReg = MI->getOperand(i).getReg();
4204 : break;
4205 : }
4206 : }
4207 : }
4208 : }
4209 :
4210 5432 : /// After the schedule has been formed, call this function to combine
4211 5432 : /// the instructions from the different stages/cycles. That is, this
4212 : /// function creates a schedule that represents a single iteration.
4213 496 : void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) {
4214 : // Move all instructions to the first stage from later stages.
4215 248 : for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
4216 248 : for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage;
4217 : ++stage) {
4218 : std::deque<SUnit *> &cycleInstrs =
4219 : ScheduledInstrs[cycle + (stage * InitiationInterval)];
4220 500 : for (std::deque<SUnit *>::reverse_iterator I = cycleInstrs.rbegin(),
4221 : E = cycleInstrs.rend();
4222 : I != E; ++I)
4223 : ScheduledInstrs[cycle].push_front(*I);
4224 : }
4225 175 : }
4226 : // Iterate over the definitions in each instruction, and compute the
4227 675 : // stage difference for each use. Keep the maximum value.
4228 983 : for (auto &I : InstrToCycle) {
4229 : int DefStage = stageScheduled(I.first);
4230 : MachineInstr *MI = I.first->getInstr();
4231 483 : for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
4232 : MachineOperand &Op = MI->getOperand(i);
4233 : if (!Op.isReg() || !Op.isDef())
4234 1107 : continue;
4235 :
4236 : unsigned Reg = Op.getReg();
4237 : unsigned MaxDiff = 0;
4238 : bool PhiIsSwapped = false;
4239 : for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(Reg),
4240 1808 : EI = MRI.use_end();
4241 1633 : UI != EI; ++UI) {
4242 1633 : MachineOperand &UseOp = *UI;
4243 7733 : MachineInstr *UseMI = UseOp.getParent();
4244 6100 : SUnit *SUnitUse = SSD->getSUnit(UseMI);
4245 6100 : int UseStage = stageScheduled(SUnitUse);
4246 4476 : unsigned Diff = 0;
4247 : if (UseStage != -1 && UseStage >= DefStage)
4248 1624 : Diff = UseStage - DefStage;
4249 1624 : if (MI->isPHI()) {
4250 : if (isLoopCarried(SSD, *MI))
4251 1624 : ++Diff;
4252 : else
4253 3789 : PhiIsSwapped = true;
4254 : }
4255 2165 : MaxDiff = std::max(Diff, MaxDiff);
4256 : }
4257 2165 : RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped);
4258 2165 : }
4259 2165 : }
4260 2058 :
4261 : // Erase all the elements in the later stages. Only one iteration should
4262 659 : // remain in the scheduled list, and it contains all the instructions.
4263 632 : for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle)
4264 : ScheduledInstrs.erase(cycle);
4265 :
4266 : // Change the registers in instruction as specified in the InstrChanges
4267 2165 : // map. We need to use the new registers to create the correct order.
4268 : for (int i = 0, e = SSD->SUnits.size(); i != e; ++i) {
4269 1624 : SUnit *SU = &SSD->SUnits[i];
4270 : SSD->applyInstrChange(SU->getInstr(), *this);
4271 : }
4272 :
4273 : // Reorder the instructions in each cycle to fix and improve the
4274 : // generated code.
4275 591 : for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) {
4276 416 : std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle];
4277 : std::deque<SUnit *> newOrderPhi;
4278 : for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
4279 : SUnit *SU = cycleInstrs[i];
4280 1983 : if (SU->getInstr()->isPHI())
4281 1633 : newOrderPhi.push_back(SU);
4282 1633 : }
4283 : std::deque<SUnit *> newOrderI;
4284 : for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
4285 : SUnit *SU = cycleInstrs[i];
4286 : if (!SU->getInstr()->isPHI())
4287 675 : orderDependence(SSD, SU, newOrderI);
4288 500 : }
4289 : // Replace the old order with the new order.
4290 2133 : cycleInstrs.swap(newOrderPhi);
4291 1633 : cycleInstrs.insert(cycleInstrs.end(), newOrderI.begin(), newOrderI.end());
4292 1633 : SSD->fixupRegisterOverlaps(cycleInstrs);
4293 : }
4294 :
4295 : LLVM_DEBUG(dump(););
4296 2133 : }
4297 1633 :
4298 1633 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4299 1257 : /// Print the schedule information to the given output.
4300 : void SMSchedule::print(raw_ostream &os) const {
4301 : // Iterate over each cycle.
4302 : for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
4303 500 : // Iterate over each instruction in the cycle.
4304 500 : const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
4305 : for (SUnit *CI : cycleInstrs->second) {
4306 : os << "cycle " << cycle << " (" << stageScheduled(CI) << ") ";
4307 : os << "(" << CI->NodeNum << ") ";
4308 175 : CI->getInstr()->print(os);
4309 : os << "\n";
4310 : }
4311 : }
4312 : }
4313 :
4314 : /// Utility function used for debugging to print the schedule.
4315 : LLVM_DUMP_METHOD void SMSchedule::dump() const { print(dbgs()); }
4316 : #endif
|
