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