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