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