1 //===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===// 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 /// \file Implements the ScheduleDAG class, which is used as the common base 11 /// class for instruction schedulers. This encapsulates the scheduling DAG, 12 /// which is shared between SelectionDAG and MachineInstr scheduling. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H 17 #define LLVM_CODEGEN_SCHEDULEDAG_H 18 19 #include "llvm/ADT/BitVector.h" 20 #include "llvm/ADT/GraphTraits.h" 21 #include "llvm/ADT/iterator.h" 22 #include "llvm/ADT/PointerIntPair.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/CodeGen/MachineInstr.h" 25 #include "llvm/Support/ErrorHandling.h" 26 #include "llvm/Target/TargetLowering.h" 27 #include <cassert> 28 #include <cstddef> 29 #include <iterator> 30 #include <string> 31 #include <vector> 32 33 namespace llvm { 34 35 template<class Graph> class GraphWriter; 36 class MachineFunction; 37 class MachineRegisterInfo; 38 class MCInstrDesc; 39 struct MCSchedClassDesc; 40 class ScheduleDAG; 41 class SDNode; 42 class SUnit; 43 class TargetInstrInfo; 44 class TargetMachine; 45 class TargetRegisterClass; 46 class TargetRegisterInfo; 47 48 /// Scheduling dependency. This represents one direction of an edge in the 49 /// scheduling DAG. 50 class SDep { 51 public: 52 /// These are the different kinds of scheduling dependencies. 53 enum Kind { 54 Data, ///< Regular data dependence (aka true-dependence). 55 Anti, ///< A register anti-dependedence (aka WAR). 56 Output, ///< A register output-dependence (aka WAW). 57 Order ///< Any other ordering dependency. 58 }; 59 60 // Strong dependencies must be respected by the scheduler. Artificial 61 // dependencies may be removed only if they are redundant with another 62 // strong depedence. 63 // 64 // Weak dependencies may be violated by the scheduling strategy, but only if 65 // the strategy can prove it is correct to do so. 66 // 67 // Strong OrderKinds must occur before "Weak". 68 // Weak OrderKinds must occur after "Weak". 69 enum OrderKind { 70 Barrier, ///< An unknown scheduling barrier. 71 MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. 72 MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. 73 Artificial, ///< Arbitrary strong DAG edge (no real dependence). 74 Weak, ///< Arbitrary weak DAG edge. 75 Cluster ///< Weak DAG edge linking a chain of clustered instrs. 76 }; 77 78 private: 79 /// \brief A pointer to the depending/depended-on SUnit, and an enum 80 /// indicating the kind of the dependency. 81 PointerIntPair<SUnit *, 2, Kind> Dep; 82 83 /// A union discriminated by the dependence kind. 84 union { 85 /// For Data, Anti, and Output dependencies, the associated register. For 86 /// Data dependencies that don't currently have a register/ assigned, this 87 /// is set to zero. 88 unsigned Reg; 89 90 /// Additional information about Order dependencies. 91 unsigned OrdKind; // enum OrderKind 92 } Contents; 93 94 /// The time associated with this edge. Often this is just the value of the 95 /// Latency field of the predecessor, however advanced models may provide 96 /// additional information about specific edges. 97 unsigned Latency; 98 99 public: 100 /// Constructs a null SDep. This is only for use by container classes which 101 /// require default constructors. SUnits may not/ have null SDep edges. 102 SDep() : Dep(nullptr, Data) {} 103 104 /// Constructs an SDep with the specified values. 105 SDep(SUnit *S, Kind kind, unsigned Reg) 106 : Dep(S, kind), Contents() { 107 switch (kind) { 108 default: 109 llvm_unreachable("Reg given for non-register dependence!"); 110 case Anti: 111 case Output: 112 assert(Reg != 0 && 113 "SDep::Anti and SDep::Output must use a non-zero Reg!"); 114 Contents.Reg = Reg; 115 Latency = 0; 116 break; 117 case Data: 118 Contents.Reg = Reg; 119 Latency = 1; 120 break; 121 } 122 } 123 124 SDep(SUnit *S, OrderKind kind) 125 : Dep(S, Order), Contents(), Latency(0) { 126 Contents.OrdKind = kind; 127 } 128 129 /// Returns true if the specified SDep is equivalent except for latency. 130 bool overlaps(const SDep &Other) const; 131 132 bool operator==(const SDep &Other) const { 133 return overlaps(Other) && Latency == Other.Latency; 134 } 135 136 bool operator!=(const SDep &Other) const { 137 return !operator==(Other); 138 } 139 140 /// \brief Returns the latency value for this edge, which roughly means the 141 /// minimum number of cycles that must elapse between the predecessor and 142 /// the successor, given that they have this edge between them. 143 unsigned getLatency() const { 144 return Latency; 145 } 146 147 /// Sets the latency for this edge. 148 void setLatency(unsigned Lat) { 149 Latency = Lat; 150 } 151 152 //// Returns the SUnit to which this edge points. 153 SUnit *getSUnit() const; 154 155 //// Assigns the SUnit to which this edge points. 156 void setSUnit(SUnit *SU); 157 158 /// Returns an enum value representing the kind of the dependence. 159 Kind getKind() const; 160 161 /// Shorthand for getKind() != SDep::Data. 162 bool isCtrl() const { 163 return getKind() != Data; 164 } 165 166 /// \brief Tests if this is an Order dependence between two memory accesses 167 /// where both sides of the dependence access memory in non-volatile and 168 /// fully modeled ways. 169 bool isNormalMemory() const { 170 return getKind() == Order && (Contents.OrdKind == MayAliasMem 171 || Contents.OrdKind == MustAliasMem); 172 } 173 174 /// Tests if this is an Order dependence that is marked as a barrier. 175 bool isBarrier() const { 176 return getKind() == Order && Contents.OrdKind == Barrier; 177 } 178 179 /// Tests if this is could be any kind of memory dependence. 180 bool isNormalMemoryOrBarrier() const { 181 return (isNormalMemory() || isBarrier()); 182 } 183 184 /// \brief Tests if this is an Order dependence that is marked as 185 /// "must alias", meaning that the SUnits at either end of the edge have a 186 /// memory dependence on a known memory location. 187 bool isMustAlias() const { 188 return getKind() == Order && Contents.OrdKind == MustAliasMem; 189 } 190 191 /// Tests if this a weak dependence. Weak dependencies are considered DAG 192 /// edges for height computation and other heuristics, but do not force 193 /// ordering. Breaking a weak edge may require the scheduler to compensate, 194 /// for example by inserting a copy. 195 bool isWeak() const { 196 return getKind() == Order && Contents.OrdKind >= Weak; 197 } 198 199 /// \brief Tests if this is an Order dependence that is marked as 200 /// "artificial", meaning it isn't necessary for correctness. 201 bool isArtificial() const { 202 return getKind() == Order && Contents.OrdKind == Artificial; 203 } 204 205 /// \brief Tests if this is an Order dependence that is marked as "cluster", 206 /// meaning it is artificial and wants to be adjacent. 207 bool isCluster() const { 208 return getKind() == Order && Contents.OrdKind == Cluster; 209 } 210 211 /// Tests if this is a Data dependence that is associated with a register. 212 bool isAssignedRegDep() const { 213 return getKind() == Data && Contents.Reg != 0; 214 } 215 216 /// Returns the register associated with this edge. This is only valid on 217 /// Data, Anti, and Output edges. On Data edges, this value may be zero, 218 /// meaning there is no associated register. 219 unsigned getReg() const { 220 assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 221 "getReg called on non-register dependence edge!"); 222 return Contents.Reg; 223 } 224 225 /// Assigns the associated register for this edge. This is only valid on 226 /// Data, Anti, and Output edges. On Anti and Output edges, this value must 227 /// not be zero. On Data edges, the value may be zero, which would mean that 228 /// no specific register is associated with this edge. 229 void setReg(unsigned Reg) { 230 assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 231 "setReg called on non-register dependence edge!"); 232 assert((getKind() != Anti || Reg != 0) && 233 "SDep::Anti edge cannot use the zero register!"); 234 assert((getKind() != Output || Reg != 0) && 235 "SDep::Output edge cannot use the zero register!"); 236 Contents.Reg = Reg; 237 } 238 }; 239 240 template <> 241 struct isPodLike<SDep> { static const bool value = true; }; 242 243 /// Scheduling unit. This is a node in the scheduling DAG. 244 class SUnit { 245 private: 246 enum : unsigned { BoundaryID = ~0u }; 247 248 SDNode *Node = nullptr; ///< Representative node. 249 MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr. 250 251 public: 252 SUnit *OrigNode = nullptr; ///< If not this, the node from which this node 253 /// was cloned. (SD scheduling only) 254 255 const MCSchedClassDesc *SchedClass = 256 nullptr; ///< nullptr or resolved SchedClass. 257 258 SmallVector<SDep, 4> Preds; ///< All sunit predecessors. 259 SmallVector<SDep, 4> Succs; ///< All sunit successors. 260 261 typedef SmallVectorImpl<SDep>::iterator pred_iterator; 262 typedef SmallVectorImpl<SDep>::iterator succ_iterator; 263 typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator; 264 typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator; 265 266 unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector. 267 unsigned NodeQueueId = 0; ///< Queue id of node. 268 unsigned NumPreds = 0; ///< # of SDep::Data preds. 269 unsigned NumSuccs = 0; ///< # of SDep::Data sucss. 270 unsigned NumPredsLeft = 0; ///< # of preds not scheduled. 271 unsigned NumSuccsLeft = 0; ///< # of succs not scheduled. 272 unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled. 273 unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled. 274 unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use. 275 unsigned short Latency = 0; ///< Node latency. 276 bool isVRegCycle : 1; ///< May use and def the same vreg. 277 bool isCall : 1; ///< Is a function call. 278 bool isCallOp : 1; ///< Is a function call operand. 279 bool isTwoAddress : 1; ///< Is a two-address instruction. 280 bool isCommutable : 1; ///< Is a commutable instruction. 281 bool hasPhysRegUses : 1; ///< Has physreg uses. 282 bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used. 283 bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not. 284 bool isPending : 1; ///< True once pending. 285 bool isAvailable : 1; ///< True once available. 286 bool isScheduled : 1; ///< True once scheduled. 287 bool isScheduleHigh : 1; ///< True if preferable to schedule high. 288 bool isScheduleLow : 1; ///< True if preferable to schedule low. 289 bool isCloned : 1; ///< True if this node has been cloned. 290 bool isUnbuffered : 1; ///< Uses an unbuffered resource. 291 bool hasReservedResource : 1; ///< Uses a reserved resource. 292 Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference. 293 294 private: 295 bool isDepthCurrent : 1; ///< True if Depth is current. 296 bool isHeightCurrent : 1; ///< True if Height is current. 297 unsigned Depth = 0; ///< Node depth. 298 unsigned Height = 0; ///< Node height. 299 300 public: 301 unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready. 302 unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready. 303 304 const TargetRegisterClass *CopyDstRC = 305 nullptr; ///< Is a special copy node if != nullptr. 306 const TargetRegisterClass *CopySrcRC = nullptr; 307 308 /// \brief Constructs an SUnit for pre-regalloc scheduling to represent an 309 /// SDNode and any nodes flagged to it. 310 SUnit(SDNode *node, unsigned nodenum) 311 : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false), 312 isCallOp(false), isTwoAddress(false), isCommutable(false), 313 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 314 isPending(false), isAvailable(false), isScheduled(false), 315 isScheduleHigh(false), isScheduleLow(false), isCloned(false), 316 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 317 isHeightCurrent(false) {} 318 319 /// \brief Constructs an SUnit for post-regalloc scheduling to represent a 320 /// MachineInstr. 321 SUnit(MachineInstr *instr, unsigned nodenum) 322 : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false), 323 isCallOp(false), isTwoAddress(false), isCommutable(false), 324 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 325 isPending(false), isAvailable(false), isScheduled(false), 326 isScheduleHigh(false), isScheduleLow(false), isCloned(false), 327 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 328 isHeightCurrent(false) {} 329 330 /// \brief Constructs a placeholder SUnit. 331 SUnit() 332 : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 333 isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false), 334 hasPhysRegClobbers(false), isPending(false), isAvailable(false), 335 isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 336 isCloned(false), isUnbuffered(false), hasReservedResource(false), 337 isDepthCurrent(false), isHeightCurrent(false) {} 338 339 /// \brief Boundary nodes are placeholders for the boundary of the 340 /// scheduling region. 341 /// 342 /// BoundaryNodes can have DAG edges, including Data edges, but they do not 343 /// correspond to schedulable entities (e.g. instructions) and do not have a 344 /// valid ID. Consequently, always check for boundary nodes before accessing 345 /// an assoicative data structure keyed on node ID. 346 bool isBoundaryNode() const { return NodeNum == BoundaryID; } 347 348 /// Assigns the representative SDNode for this SUnit. This may be used 349 /// during pre-regalloc scheduling. 350 void setNode(SDNode *N) { 351 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 352 Node = N; 353 } 354 355 /// Returns the representative SDNode for this SUnit. This may be used 356 /// during pre-regalloc scheduling. 357 SDNode *getNode() const { 358 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 359 return Node; 360 } 361 362 /// \brief Returns true if this SUnit refers to a machine instruction as 363 /// opposed to an SDNode. 364 bool isInstr() const { return Instr; } 365 366 /// Assigns the instruction for the SUnit. This may be used during 367 /// post-regalloc scheduling. 368 void setInstr(MachineInstr *MI) { 369 assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 370 Instr = MI; 371 } 372 373 /// Returns the representative MachineInstr for this SUnit. This may be used 374 /// during post-regalloc scheduling. 375 MachineInstr *getInstr() const { 376 assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 377 return Instr; 378 } 379 380 /// Adds the specified edge as a pred of the current node if not already. 381 /// It also adds the current node as a successor of the specified node. 382 bool addPred(const SDep &D, bool Required = true); 383 384 /// \brief Adds a barrier edge to SU by calling addPred(), with latency 0 385 /// generally or latency 1 for a store followed by a load. 386 bool addPredBarrier(SUnit *SU) { 387 SDep Dep(SU, SDep::Barrier); 388 unsigned TrueMemOrderLatency = 389 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0); 390 Dep.setLatency(TrueMemOrderLatency); 391 return addPred(Dep); 392 } 393 394 /// Removes the specified edge as a pred of the current node if it exists. 395 /// It also removes the current node as a successor of the specified node. 396 void removePred(const SDep &D); 397 398 /// Returns the depth of this node, which is the length of the maximum path 399 /// up to any node which has no predecessors. 400 unsigned getDepth() const { 401 if (!isDepthCurrent) 402 const_cast<SUnit *>(this)->ComputeDepth(); 403 return Depth; 404 } 405 406 /// \brief Returns the height of this node, which is the length of the 407 /// maximum path down to any node which has no successors. 408 unsigned getHeight() const { 409 if (!isHeightCurrent) 410 const_cast<SUnit *>(this)->ComputeHeight(); 411 return Height; 412 } 413 414 /// \brief If NewDepth is greater than this node's depth value, sets it to 415 /// be the new depth value. This also recursively marks successor nodes 416 /// dirty. 417 void setDepthToAtLeast(unsigned NewDepth); 418 419 /// \brief If NewDepth is greater than this node's depth value, set it to be 420 /// the new height value. This also recursively marks predecessor nodes 421 /// dirty. 422 void setHeightToAtLeast(unsigned NewHeight); 423 424 /// \brief Sets a flag in this node to indicate that its stored Depth value 425 /// will require recomputation the next time getDepth() is called. 426 void setDepthDirty(); 427 428 /// \brief Sets a flag in this node to indicate that its stored Height value 429 /// will require recomputation the next time getHeight() is called. 430 void setHeightDirty(); 431 432 /// Tests if node N is a predecessor of this node. 433 bool isPred(const SUnit *N) const { 434 for (const SDep &Pred : Preds) 435 if (Pred.getSUnit() == N) 436 return true; 437 return false; 438 } 439 440 /// Tests if node N is a successor of this node. 441 bool isSucc(const SUnit *N) const { 442 for (const SDep &Succ : Succs) 443 if (Succ.getSUnit() == N) 444 return true; 445 return false; 446 } 447 448 bool isTopReady() const { 449 return NumPredsLeft == 0; 450 } 451 bool isBottomReady() const { 452 return NumSuccsLeft == 0; 453 } 454 455 /// \brief Orders this node's predecessor edges such that the critical path 456 /// edge occurs first. 457 void biasCriticalPath(); 458 459 void dump(const ScheduleDAG *G) const; 460 void dumpAll(const ScheduleDAG *G) const; 461 void print(raw_ostream &O, const ScheduleDAG *G) const; 462 463 private: 464 void ComputeDepth(); 465 void ComputeHeight(); 466 }; 467 468 /// Returns true if the specified SDep is equivalent except for latency. 469 inline bool SDep::overlaps(const SDep &Other) const { 470 if (Dep != Other.Dep) 471 return false; 472 switch (Dep.getInt()) { 473 case Data: 474 case Anti: 475 case Output: 476 return Contents.Reg == Other.Contents.Reg; 477 case Order: 478 return Contents.OrdKind == Other.Contents.OrdKind; 479 } 480 llvm_unreachable("Invalid dependency kind!"); 481 } 482 483 //// Returns the SUnit to which this edge points. 484 inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); } 485 486 //// Assigns the SUnit to which this edge points. 487 inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); } 488 489 /// Returns an enum value representing the kind of the dependence. 490 inline SDep::Kind SDep::getKind() const { return Dep.getInt(); } 491 492 //===--------------------------------------------------------------------===// 493 494 /// \brief This interface is used to plug different priorities computation 495 /// algorithms into the list scheduler. It implements the interface of a 496 /// standard priority queue, where nodes are inserted in arbitrary order and 497 /// returned in priority order. The computation of the priority and the 498 /// representation of the queue are totally up to the implementation to 499 /// decide. 500 class SchedulingPriorityQueue { 501 virtual void anchor(); 502 503 unsigned CurCycle = 0; 504 bool HasReadyFilter; 505 506 public: 507 SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {} 508 509 virtual ~SchedulingPriorityQueue() = default; 510 511 virtual bool isBottomUp() const = 0; 512 513 virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 514 virtual void addNode(const SUnit *SU) = 0; 515 virtual void updateNode(const SUnit *SU) = 0; 516 virtual void releaseState() = 0; 517 518 virtual bool empty() const = 0; 519 520 bool hasReadyFilter() const { return HasReadyFilter; } 521 522 virtual bool tracksRegPressure() const { return false; } 523 524 virtual bool isReady(SUnit *) const { 525 assert(!HasReadyFilter && "The ready filter must override isReady()"); 526 return true; 527 } 528 529 virtual void push(SUnit *U) = 0; 530 531 void push_all(const std::vector<SUnit *> &Nodes) { 532 for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 533 E = Nodes.end(); I != E; ++I) 534 push(*I); 535 } 536 537 virtual SUnit *pop() = 0; 538 539 virtual void remove(SUnit *SU) = 0; 540 541 virtual void dump(ScheduleDAG *) const {} 542 543 /// As each node is scheduled, this method is invoked. This allows the 544 /// priority function to adjust the priority of related unscheduled nodes, 545 /// for example. 546 virtual void scheduledNode(SUnit *) {} 547 548 virtual void unscheduledNode(SUnit *) {} 549 550 void setCurCycle(unsigned Cycle) { 551 CurCycle = Cycle; 552 } 553 554 unsigned getCurCycle() const { 555 return CurCycle; 556 } 557 }; 558 559 class ScheduleDAG { 560 public: 561 const TargetMachine &TM; ///< Target processor 562 const TargetInstrInfo *TII; ///< Target instruction information 563 const TargetRegisterInfo *TRI; ///< Target processor register info 564 MachineFunction &MF; ///< Machine function 565 MachineRegisterInfo &MRI; ///< Virtual/real register map 566 std::vector<SUnit> SUnits; ///< The scheduling units. 567 SUnit EntrySU; ///< Special node for the region entry. 568 SUnit ExitSU; ///< Special node for the region exit. 569 570 #ifdef NDEBUG 571 static const bool StressSched = false; 572 #else 573 bool StressSched; 574 #endif 575 576 explicit ScheduleDAG(MachineFunction &mf); 577 578 virtual ~ScheduleDAG(); 579 580 /// Clears the DAG state (between regions). 581 void clearDAG(); 582 583 /// Returns the MCInstrDesc of this SUnit. 584 /// Returns NULL for SDNodes without a machine opcode. 585 const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 586 if (SU->isInstr()) return &SU->getInstr()->getDesc(); 587 return getNodeDesc(SU->getNode()); 588 } 589 590 /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'. 591 virtual void viewGraph(const Twine &Name, const Twine &Title); 592 virtual void viewGraph(); 593 594 virtual void dumpNode(const SUnit *SU) const = 0; 595 596 /// Returns a label for an SUnit node in a visualization of the ScheduleDAG. 597 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 598 599 /// Returns a label for the region of code covered by the DAG. 600 virtual std::string getDAGName() const = 0; 601 602 /// Adds custom features for a visualization of the ScheduleDAG. 603 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 604 605 #ifndef NDEBUG 606 /// \brief Verifies that all SUnits were scheduled and that their state is 607 /// consistent. Returns the number of scheduled SUnits. 608 unsigned VerifyScheduledDAG(bool isBottomUp); 609 #endif 610 611 private: 612 /// Returns the MCInstrDesc of this SDNode or NULL. 613 const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 614 }; 615 616 class SUnitIterator : public std::iterator<std::forward_iterator_tag, 617 SUnit, ptrdiff_t> { 618 SUnit *Node; 619 unsigned Operand; 620 621 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 622 623 public: 624 bool operator==(const SUnitIterator& x) const { 625 return Operand == x.Operand; 626 } 627 bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 628 629 pointer operator*() const { 630 return Node->Preds[Operand].getSUnit(); 631 } 632 pointer operator->() const { return operator*(); } 633 634 SUnitIterator& operator++() { // Preincrement 635 ++Operand; 636 return *this; 637 } 638 SUnitIterator operator++(int) { // Postincrement 639 SUnitIterator tmp = *this; ++*this; return tmp; 640 } 641 642 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 643 static SUnitIterator end (SUnit *N) { 644 return SUnitIterator(N, (unsigned)N->Preds.size()); 645 } 646 647 unsigned getOperand() const { return Operand; } 648 const SUnit *getNode() const { return Node; } 649 650 /// Tests if this is not an SDep::Data dependence. 651 bool isCtrlDep() const { 652 return getSDep().isCtrl(); 653 } 654 bool isArtificialDep() const { 655 return getSDep().isArtificial(); 656 } 657 const SDep &getSDep() const { 658 return Node->Preds[Operand]; 659 } 660 }; 661 662 template <> struct GraphTraits<SUnit*> { 663 typedef SUnit *NodeRef; 664 typedef SUnitIterator ChildIteratorType; 665 static NodeRef getEntryNode(SUnit *N) { return N; } 666 static ChildIteratorType child_begin(NodeRef N) { 667 return SUnitIterator::begin(N); 668 } 669 static ChildIteratorType child_end(NodeRef N) { 670 return SUnitIterator::end(N); 671 } 672 }; 673 674 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 675 typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator; 676 static nodes_iterator nodes_begin(ScheduleDAG *G) { 677 return nodes_iterator(G->SUnits.begin()); 678 } 679 static nodes_iterator nodes_end(ScheduleDAG *G) { 680 return nodes_iterator(G->SUnits.end()); 681 } 682 }; 683 684 /// This class can compute a topological ordering for SUnits and provides 685 /// methods for dynamically updating the ordering as new edges are added. 686 /// 687 /// This allows a very fast implementation of IsReachable, for example. 688 class ScheduleDAGTopologicalSort { 689 /// A reference to the ScheduleDAG's SUnits. 690 std::vector<SUnit> &SUnits; 691 SUnit *ExitSU; 692 693 /// Maps topological index to the node number. 694 std::vector<int> Index2Node; 695 /// Maps the node number to its topological index. 696 std::vector<int> Node2Index; 697 /// a set of nodes visited during a DFS traversal. 698 BitVector Visited; 699 700 /// Makes a DFS traversal and mark all nodes affected by the edge insertion. 701 /// These nodes will later get new topological indexes by means of the Shift 702 /// method. 703 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 704 705 /// \brief Reassigns topological indexes for the nodes in the DAG to 706 /// preserve the topological ordering. 707 void Shift(BitVector& Visited, int LowerBound, int UpperBound); 708 709 /// Assigns the topological index to the node n. 710 void Allocate(int n, int index); 711 712 public: 713 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 714 715 /// Creates the initial topological ordering from the DAG to be scheduled. 716 void InitDAGTopologicalSorting(); 717 718 /// Returns an array of SUs that are both in the successor 719 /// subtree of StartSU and in the predecessor subtree of TargetSU. 720 /// StartSU and TargetSU are not in the array. 721 /// Success is false if TargetSU is not in the successor subtree of 722 /// StartSU, else it is true. 723 std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, 724 bool &Success); 725 726 /// Checks if \p SU is reachable from \p TargetSU. 727 bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 728 729 /// Returns true if addPred(TargetSU, SU) creates a cycle. 730 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); 731 732 /// \brief Updates the topological ordering to accommodate an edge to be 733 /// added from SUnit \p X to SUnit \p Y. 734 void AddPred(SUnit *Y, SUnit *X); 735 736 /// \brief Updates the topological ordering to accommodate an an edge to be 737 /// removed from the specified node \p N from the predecessors of the 738 /// current node \p M. 739 void RemovePred(SUnit *M, SUnit *N); 740 741 typedef std::vector<int>::iterator iterator; 742 typedef std::vector<int>::const_iterator const_iterator; 743 iterator begin() { return Index2Node.begin(); } 744 const_iterator begin() const { return Index2Node.begin(); } 745 iterator end() { return Index2Node.end(); } 746 const_iterator end() const { return Index2Node.end(); } 747 748 typedef std::vector<int>::reverse_iterator reverse_iterator; 749 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 750 reverse_iterator rbegin() { return Index2Node.rbegin(); } 751 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 752 reverse_iterator rend() { return Index2Node.rend(); } 753 const_reverse_iterator rend() const { return Index2Node.rend(); } 754 }; 755 756 } // end namespace llvm 757 758 #endif // LLVM_CODEGEN_SCHEDULEDAG_H 759