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