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