include/llvm/CodeGen/MachinePipeliner.h

   1 //===- MachinePipeliner.h - Machine Software Pipeliner Pass -------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
  10 //
  11 // Software pipelining (SWP) is an instruction scheduling technique for loops
  12 // that overlap loop iterations and exploits ILP via a compiler transformation.
  13 //
  14 // Swing Modulo Scheduling is an implementation of software pipelining
  15 // that generates schedules that are near optimal in terms of initiation
  16 // interval, register requirements, and stage count. See the papers:
  17 //
  18 // "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa,
  19 // A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996
  20 // Conference on Parallel Architectures and Compilation Techiniques.
  21 //
  22 // "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J.
  23 // Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE
  24 // Transactions on Computers, Vol. 50, No. 3, 2001.
  25 //
  26 // "An Implementation of Swing Modulo Scheduling With Extensions for
  27 // Superblocks", by T. Lattner, Master's Thesis, University of Illinois at
  28 // Urbana-Champaign, 2005.
  29 //
  30 //
  31 // The SMS algorithm consists of three main steps after computing the minimal
  32 // initiation interval (MII).
  33 // 1) Analyze the dependence graph and compute information about each
  34 //    instruction in the graph.
  35 // 2) Order the nodes (instructions) by priority based upon the heuristics
  36 //    described in the algorithm.
  37 // 3) Attempt to schedule the nodes in the specified order using the MII.
  38 //
  39 //===----------------------------------------------------------------------===//
  40 #ifndef LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
  41 #define LLVM_LIB_CODEGEN_MACHINEPIPELINER_H
  42
  43 #include "llvm/Analysis/AliasAnalysis.h"
  44
  45 #include "llvm/CodeGen/MachineDominators.h"
  46 #include "llvm/CodeGen/RegisterClassInfo.h"
  47 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  48 #include "llvm/CodeGen/TargetInstrInfo.h"
  49
  50 namespace llvm {
  51
  52 class NodeSet;
  53 class SMSchedule;
  54
  55 extern cl::opt<bool> SwpEnableCopyToPhi;
  56
  57 /// The main class in the implementation of the target independent
  58 /// software pipeliner pass.
  59 class MachinePipeliner : public MachineFunctionPass {
  60 public:
  61   MachineFunction *MF = nullptr;
  62   const MachineLoopInfo *MLI = nullptr;
  63   const MachineDominatorTree *MDT = nullptr;
  64   const InstrItineraryData *InstrItins;
  65   const TargetInstrInfo *TII = nullptr;
  66   RegisterClassInfo RegClassInfo;
  67   bool disabledByPragma = false;
  68   unsigned II_setByPragma = 0;
  69
  70 #ifndef NDEBUG
  71   static int NumTries;
  72 #endif
  73
  74   /// Cache the target analysis information about the loop.
  75   struct LoopInfo {
  76     MachineBasicBlock *TBB = nullptr;
  77     MachineBasicBlock *FBB = nullptr;
  78     SmallVector<MachineOperand, 4> BrCond;
  79     MachineInstr *LoopInductionVar = nullptr;
  80     MachineInstr *LoopCompare = nullptr;
  81   };
  82   LoopInfo LI;
  83
  84   static char ID;
  85
  86   MachinePipeliner() : MachineFunctionPass(ID) {
  87     initializeMachinePipelinerPass(*PassRegistry::getPassRegistry());
  88   }
  89
  90   bool runOnMachineFunction(MachineFunction &MF) override;
  91
  92   void getAnalysisUsage(AnalysisUsage &AU) const override {
  93     AU.addRequired<AAResultsWrapperPass>();
  94     AU.addPreserved<AAResultsWrapperPass>();
  95     AU.addRequired<MachineLoopInfo>();
  96     AU.addRequired<MachineDominatorTree>();
  97     AU.addRequired<LiveIntervals>();
  98     MachineFunctionPass::getAnalysisUsage(AU);
  99   }
 100
 101 private:
 102   void preprocessPhiNodes(MachineBasicBlock &B);
 103   bool canPipelineLoop(MachineLoop &L);
 104   bool scheduleLoop(MachineLoop &L);
 105   bool swingModuloScheduler(MachineLoop &L);
 106   void setPragmaPipelineOptions(MachineLoop &L);
 107 };
 108
 109 /// This class builds the dependence graph for the instructions in a loop,
 110 /// and attempts to schedule the instructions using the SMS algorithm.
 111 class SwingSchedulerDAG : public ScheduleDAGInstrs {
 112   MachinePipeliner &Pass;
 113   /// The minimum initiation interval between iterations for this schedule.
 114   unsigned MII = 0;
 115   /// The maximum initiation interval between iterations for this schedule.
 116   unsigned MAX_II = 0;
 117   /// Set to true if a valid pipelined schedule is found for the loop.
 118   bool Scheduled = false;
 119   MachineLoop &Loop;
 120   LiveIntervals &LIS;
 121   const RegisterClassInfo &RegClassInfo;
 122   unsigned II_setByPragma = 0;
 123
 124   /// A toplogical ordering of the SUnits, which is needed for changing
 125   /// dependences and iterating over the SUnits.
 126   ScheduleDAGTopologicalSort Topo;
 127
 128   struct NodeInfo {
 129     int ASAP = 0;
 130     int ALAP = 0;
 131     int ZeroLatencyDepth = 0;
 132     int ZeroLatencyHeight = 0;
 133
 134     NodeInfo() = default;
 135   };
 136   /// Computed properties for each node in the graph.
 137   std::vector<NodeInfo> ScheduleInfo;
 138
 139   enum OrderKind { BottomUp = 0, TopDown = 1 };
 140   /// Computed node ordering for scheduling.
 141   SetVector<SUnit *> NodeOrder;
 142
 143   using NodeSetType = SmallVector<NodeSet, 8>;
 144   using ValueMapTy = DenseMap<unsigned, unsigned>;
 145   using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>;
 146   using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>;
 147
 148   /// Instructions to change when emitting the final schedule.
 149   DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
 150
 151   /// We may create a new instruction, so remember it because it
 152   /// must be deleted when the pass is finished.
 153   DenseMap<MachineInstr*, MachineInstr *> NewMIs;
 154
 155   /// Ordered list of DAG postprocessing steps.
 156   std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
 157
 158   /// Helper class to implement Johnson's circuit finding algorithm.
 159   class Circuits {
 160     std::vector<SUnit> &SUnits;
 161     SetVector<SUnit *> Stack;
 162     BitVector Blocked;
 163     SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
 164     SmallVector<SmallVector<int, 4>, 16> AdjK;
 165     // Node to Index from ScheduleDAGTopologicalSort
 166     std::vector<int> *Node2Idx;
 167     unsigned NumPaths;
 168     static unsigned MaxPaths;
 169
 170   public:
 171     Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo)
 172         : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {
 173       Node2Idx = new std::vector<int>(SUs.size());
 174       unsigned Idx = 0;
 175       for (const auto &NodeNum : Topo)
 176         Node2Idx->at(NodeNum) = Idx++;
 177     }
 178
 179     ~Circuits() { delete Node2Idx; }
 180
 181     /// Reset the data structures used in the circuit algorithm.
 182     void reset() {
 183       Stack.clear();
 184       Blocked.reset();
 185       B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
 186       NumPaths = 0;
 187     }
 188
 189     void createAdjacencyStructure(SwingSchedulerDAG *DAG);
 190     bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
 191     void unblock(int U);
 192   };
 193
 194   struct CopyToPhiMutation : public ScheduleDAGMutation {
 195     void apply(ScheduleDAGInstrs *DAG) override;
 196   };
 197
 198 public:
 199   SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis,
 200                     const RegisterClassInfo &rci, unsigned II)
 201       : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
 202         RegClassInfo(rci), II_setByPragma(II), Topo(SUnits, &ExitSU) {
 203     P.MF->getSubtarget().getSMSMutations(Mutations);
 204     if (SwpEnableCopyToPhi)
 205       Mutations.push_back(std::make_unique<CopyToPhiMutation>());
 206   }
 207
 208   void schedule() override;
 209   void finishBlock() override;
 210
 211   /// Return true if the loop kernel has been scheduled.
 212   bool hasNewSchedule() { return Scheduled; }
 213
 214   /// Return the earliest time an instruction may be scheduled.
 215   int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; }
 216
 217   /// Return the latest time an instruction my be scheduled.
 218   int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; }
 219
 220   /// The mobility function, which the number of slots in which
 221   /// an instruction may be scheduled.
 222   int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); }
 223
 224   /// The depth, in the dependence graph, for a node.
 225   unsigned getDepth(SUnit *Node) { return Node->getDepth(); }
 226
 227   /// The maximum unweighted length of a path from an arbitrary node to the
 228   /// given node in which each edge has latency 0
 229   int getZeroLatencyDepth(SUnit *Node) {
 230     return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth;
 231   }
 232
 233   /// The height, in the dependence graph, for a node.
 234   unsigned getHeight(SUnit *Node) { return Node->getHeight(); }
 235
 236   /// The maximum unweighted length of a path from the given node to an
 237   /// arbitrary node in which each edge has latency 0
 238   int getZeroLatencyHeight(SUnit *Node) {
 239     return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight;
 240   }
 241
 242   /// Return true if the dependence is a back-edge in the data dependence graph.
 243   /// Since the DAG doesn't contain cycles, we represent a cycle in the graph
 244   /// using an anti dependence from a Phi to an instruction.
 245   bool isBackedge(SUnit *Source, const SDep &Dep) {
 246     if (Dep.getKind() != SDep::Anti)
 247       return false;
 248     return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI();
 249   }
 250
 251   bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true);
 252
 253   /// The distance function, which indicates that operation V of iteration I
 254   /// depends on operations U of iteration I-distance.
 255   unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
 256     // Instructions that feed a Phi have a distance of 1. Computing larger
 257     // values for arrays requires data dependence information.
 258     if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
 259       return 1;
 260     return 0;
 261   }
 262
 263   void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
 264
 265   void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
 266
 267   /// Return the new base register that was stored away for the changed
 268   /// instruction.
 269   unsigned getInstrBaseReg(SUnit *SU) {
 270     DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
 271         InstrChanges.find(SU);
 272     if (It != InstrChanges.end())
 273       return It->second.first;
 274     return 0;
 275   }
 276
 277   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
 278     Mutations.push_back(std::move(Mutation));
 279   }
 280
 281   static bool classof(const ScheduleDAGInstrs *DAG) { return true; }
 282
 283 private:
 284   void addLoopCarriedDependences(AliasAnalysis *AA);
 285   void updatePhiDependences();
 286   void changeDependences();
 287   unsigned calculateResMII();
 288   unsigned calculateRecMII(NodeSetType &RecNodeSets);
 289   void findCircuits(NodeSetType &NodeSets);
 290   void fuseRecs(NodeSetType &NodeSets);
 291   void removeDuplicateNodes(NodeSetType &NodeSets);
 292   void computeNodeFunctions(NodeSetType &NodeSets);
 293   void registerPressureFilter(NodeSetType &NodeSets);
 294   void colocateNodeSets(NodeSetType &NodeSets);
 295   void checkNodeSets(NodeSetType &NodeSets);
 296   void groupRemainingNodes(NodeSetType &NodeSets);
 297   void addConnectedNodes(SUnit *SU, NodeSet &NewSet,
 298                          SetVector<SUnit *> &NodesAdded);
 299   void computeNodeOrder(NodeSetType &NodeSets);
 300   void checkValidNodeOrder(const NodeSetType &Circuits) const;
 301   bool schedulePipeline(SMSchedule &Schedule);
 302   bool computeDelta(MachineInstr &MI, unsigned &Delta);
 303   MachineInstr *findDefInLoop(unsigned Reg);
 304   bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
 305                              unsigned &OffsetPos, unsigned &NewBase,
 306                              int64_t &NewOffset);
 307   void postprocessDAG();
 308   /// Set the Minimum Initiation Interval for this schedule attempt.
 309   void setMII(unsigned ResMII, unsigned RecMII);
 310   /// Set the Maximum Initiation Interval for this schedule attempt.
 311   void setMAX_II();
 312 };
 313
 314 /// A NodeSet contains a set of SUnit DAG nodes with additional information
 315 /// that assigns a priority to the set.
 316 class NodeSet {
 317   SetVector<SUnit *> Nodes;
 318   bool HasRecurrence = false;
 319   unsigned RecMII = 0;
 320   int MaxMOV = 0;
 321   unsigned MaxDepth = 0;
 322   unsigned Colocate = 0;
 323   SUnit *ExceedPressure = nullptr;
 324   unsigned Latency = 0;
 325
 326 public:
 327   using iterator = SetVector<SUnit *>::const_iterator;
 328
 329   NodeSet() = default;
 330   NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
 331     Latency = 0;
 332     for (unsigned i = 0, e = Nodes.size(); i < e; ++i)
 333       for (const SDep &Succ : Nodes[i]->Succs)
 334         if (Nodes.count(Succ.getSUnit()))
 335           Latency += Succ.getLatency();
 336   }
 337
 338   bool insert(SUnit *SU) { return Nodes.insert(SU); }
 339
 340   void insert(iterator S, iterator E) { Nodes.insert(S, E); }
 341
 342   template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
 343     return Nodes.remove_if(P);
 344   }
 345
 346   unsigned count(SUnit *SU) const { return Nodes.count(SU); }
 347
 348   bool hasRecurrence() { return HasRecurrence; };
 349
 350   unsigned size() const { return Nodes.size(); }
 351
 352   bool empty() const { return Nodes.empty(); }
 353
 354   SUnit *getNode(unsigned i) const { return Nodes[i]; };
 355
 356   void setRecMII(unsigned mii) { RecMII = mii; };
 357
 358   void setColocate(unsigned c) { Colocate = c; };
 359
 360   void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
 361
 362   bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
 363
 364   int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
 365
 366   int getRecMII() { return RecMII; }
 367
 368   /// Summarize node functions for the entire node set.
 369   void computeNodeSetInfo(SwingSchedulerDAG *SSD) {
 370     for (SUnit *SU : *this) {
 371       MaxMOV = std::max(MaxMOV, SSD->getMOV(SU));
 372       MaxDepth = std::max(MaxDepth, SSD->getDepth(SU));
 373     }
 374   }
 375
 376   unsigned getLatency() { return Latency; }
 377
 378   unsigned getMaxDepth() { return MaxDepth; }
 379
 380   void clear() {
 381     Nodes.clear();
 382     RecMII = 0;
 383     HasRecurrence = false;
 384     MaxMOV = 0;
 385     MaxDepth = 0;
 386     Colocate = 0;
 387     ExceedPressure = nullptr;
 388   }
 389
 390   operator SetVector<SUnit *> &() { return Nodes; }
 391
 392   /// Sort the node sets by importance. First, rank them by recurrence MII,
 393   /// then by mobility (least mobile done first), and finally by depth.
 394   /// Each node set may contain a colocate value which is used as the first
 395   /// tie breaker, if it's set.
 396   bool operator>(const NodeSet &RHS) const {
 397     if (RecMII == RHS.RecMII) {
 398       if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
 399         return Colocate < RHS.Colocate;
 400       if (MaxMOV == RHS.MaxMOV)
 401         return MaxDepth > RHS.MaxDepth;
 402       return MaxMOV < RHS.MaxMOV;
 403     }
 404     return RecMII > RHS.RecMII;
 405   }
 406
 407   bool operator==(const NodeSet &RHS) const {
 408     return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
 409            MaxDepth == RHS.MaxDepth;
 410   }
 411
 412   bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
 413
 414   iterator begin() { return Nodes.begin(); }
 415   iterator end() { return Nodes.end(); }
 416   void print(raw_ostream &os) const;
 417
 418 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 419   LLVM_DUMP_METHOD void dump() const;
 420 #endif
 421 };
 422
 423 // 16 was selected based on the number of ProcResource kinds for all
 424 // existing Subtargets, so that SmallVector don't need to resize too often.
 425 static const int DefaultProcResSize = 16;
 426
 427 class ResourceManager {
 428 private:
 429   const MCSubtargetInfo *STI;
 430   const MCSchedModel &SM;
 431   const bool UseDFA;
 432   std::unique_ptr<DFAPacketizer> DFAResources;
 433   /// Each processor resource is associated with a so-called processor resource
 434   /// mask. This vector allows to correlate processor resource IDs with
 435   /// processor resource masks. There is exactly one element per each processor
 436   /// resource declared by the scheduling model.
 437   llvm::SmallVector<uint64_t, DefaultProcResSize> ProcResourceMasks;
 438
 439   llvm::SmallVector<uint64_t, DefaultProcResSize> ProcResourceCount;
 440
 441 public:
 442   ResourceManager(const TargetSubtargetInfo *ST)
 443       : STI(ST), SM(ST->getSchedModel()), UseDFA(ST->useDFAforSMS()),
 444         ProcResourceMasks(SM.getNumProcResourceKinds(), 0),
 445         ProcResourceCount(SM.getNumProcResourceKinds(), 0) {
 446     if (UseDFA)
 447       DFAResources.reset(ST->getInstrInfo()->CreateTargetScheduleState(*ST));
 448     initProcResourceVectors(SM, ProcResourceMasks);
 449   }
 450
 451   void initProcResourceVectors(const MCSchedModel &SM,
 452                                SmallVectorImpl<uint64_t> &Masks);
 453   /// Check if the resources occupied by a MCInstrDesc are available in
 454   /// the current state.
 455   bool canReserveResources(const MCInstrDesc *MID) const;
 456
 457   /// Reserve the resources occupied by a MCInstrDesc and change the current
 458   /// state to reflect that change.
 459   void reserveResources(const MCInstrDesc *MID);
 460
 461   /// Check if the resources occupied by a machine instruction are available
 462   /// in the current state.
 463   bool canReserveResources(const MachineInstr &MI) const;
 464
 465   /// Reserve the resources occupied by a machine instruction and change the
 466   /// current state to reflect that change.
 467   void reserveResources(const MachineInstr &MI);
 468
 469   /// Reset the state
 470   void clearResources();
 471 };
 472
 473 /// This class represents the scheduled code.  The main data structure is a
 474 /// map from scheduled cycle to instructions.  During scheduling, the
 475 /// data structure explicitly represents all stages/iterations.   When
 476 /// the algorithm finshes, the schedule is collapsed into a single stage,
 477 /// which represents instructions from different loop iterations.
 478 ///
 479 /// The SMS algorithm allows negative values for cycles, so the first cycle
 480 /// in the schedule is the smallest cycle value.
 481 class SMSchedule {
 482 private:
 483   /// Map from execution cycle to instructions.
 484   DenseMap<int, std::deque<SUnit *>> ScheduledInstrs;
 485
 486   /// Map from instruction to execution cycle.
 487   std::map<SUnit *, int> InstrToCycle;
 488
 489   /// Keep track of the first cycle value in the schedule.  It starts
 490   /// as zero, but the algorithm allows negative values.
 491   int FirstCycle = 0;
 492
 493   /// Keep track of the last cycle value in the schedule.
 494   int LastCycle = 0;
 495
 496   /// The initiation interval (II) for the schedule.
 497   int InitiationInterval = 0;
 498
 499   /// Target machine information.
 500   const TargetSubtargetInfo &ST;
 501
 502   /// Virtual register information.
 503   MachineRegisterInfo &MRI;
 504
 505   ResourceManager ProcItinResources;
 506
 507 public:
 508   SMSchedule(MachineFunction *mf)
 509       : ST(mf->getSubtarget()), MRI(mf->getRegInfo()), ProcItinResources(&ST) {}
 510
 511   void reset() {
 512     ScheduledInstrs.clear();
 513     InstrToCycle.clear();
 514     FirstCycle = 0;
 515     LastCycle = 0;
 516     InitiationInterval = 0;
 517   }
 518
 519   /// Set the initiation interval for this schedule.
 520   void setInitiationInterval(int ii) { InitiationInterval = ii; }
 521
 522   /// Return the first cycle in the completed schedule.  This
 523   /// can be a negative value.
 524   int getFirstCycle() const { return FirstCycle; }
 525
 526   /// Return the last cycle in the finalized schedule.
 527   int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; }
 528
 529   /// Return the cycle of the earliest scheduled instruction in the dependence
 530   /// chain.
 531   int earliestCycleInChain(const SDep &Dep);
 532
 533   /// Return the cycle of the latest scheduled instruction in the dependence
 534   /// chain.
 535   int latestCycleInChain(const SDep &Dep);
 536
 537   void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
 538                     int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG);
 539   bool insert(SUnit *SU, int StartCycle, int EndCycle, int II);
 540
 541   /// Iterators for the cycle to instruction map.
 542   using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator;
 543   using const_sched_iterator =
 544       DenseMap<int, std::deque<SUnit *>>::const_iterator;
 545
 546   /// Return true if the instruction is scheduled at the specified stage.
 547   bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
 548     return (stageScheduled(SU) == (int)StageNum);
 549   }
 550
 551   /// Return the stage for a scheduled instruction.  Return -1 if
 552   /// the instruction has not been scheduled.
 553   int stageScheduled(SUnit *SU) const {
 554     std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
 555     if (it == InstrToCycle.end())
 556       return -1;
 557     return (it->second - FirstCycle) / InitiationInterval;
 558   }
 559
 560   /// Return the cycle for a scheduled instruction. This function normalizes
 561   /// the first cycle to be 0.
 562   unsigned cycleScheduled(SUnit *SU) const {
 563     std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
 564     assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
 565     return (it->second - FirstCycle) % InitiationInterval;
 566   }
 567
 568   /// Return the maximum stage count needed for this schedule.
 569   unsigned getMaxStageCount() {
 570     return (LastCycle - FirstCycle) / InitiationInterval;
 571   }
 572
 573   /// Return the instructions that are scheduled at the specified cycle.
 574   std::deque<SUnit *> &getInstructions(int cycle) {
 575     return ScheduledInstrs[cycle];
 576   }
 577
 578   bool isValidSchedule(SwingSchedulerDAG *SSD);
 579   void finalizeSchedule(SwingSchedulerDAG *SSD);
 580   void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
 581                        std::deque<SUnit *> &Insts);
 582   bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi);
 583   bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def,
 584                              MachineOperand &MO);
 585   void print(raw_ostream &os) const;
 586   void dump() const;
 587 };
 588
 589 } // end namespace llvm
 590
 591 #endif // LLVM_LIB_CODEGEN_MACHINEPIPELINER_H