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/PointerIntPair.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/iterator.h" 24 #include "llvm/CodeGen/MachineInstr.h" 25 #include "llvm/CodeGen/TargetLowering.h" 26 #include "llvm/Support/ErrorHandling.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 LLVMTargetMachine; 37 class MachineFunction; 38 class MachineRegisterInfo; 39 class MCInstrDesc; 40 struct MCSchedClassDesc; 41 class SDNode; 42 class SUnit; 43 class ScheduleDAG; 44 class TargetInstrInfo; 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-dependence (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 dependence. 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 /// 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. SDep()102 SDep() : Dep(nullptr, Data) {} 103 104 /// Constructs an SDep with the specified values. SDep(SUnit * S,Kind kind,unsigned Reg)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 SDep(SUnit * S,OrderKind kind)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 /// 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. getLatency()143 unsigned getLatency() const { 144 return Latency; 145 } 146 147 /// Sets the latency for this edge. setLatency(unsigned Lat)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. isCtrl()162 bool isCtrl() const { 163 return getKind() != Data; 164 } 165 166 /// 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. isNormalMemory()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. isBarrier()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. isNormalMemoryOrBarrier()180 bool isNormalMemoryOrBarrier() const { 181 return (isNormalMemory() || isBarrier()); 182 } 183 184 /// 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. isMustAlias()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. isWeak()195 bool isWeak() const { 196 return getKind() == Order && Contents.OrdKind >= Weak; 197 } 198 199 /// Tests if this is an Order dependence that is marked as 200 /// "artificial", meaning it isn't necessary for correctness. isArtificial()201 bool isArtificial() const { 202 return getKind() == Order && Contents.OrdKind == Artificial; 203 } 204 205 /// Tests if this is an Order dependence that is marked as "cluster", 206 /// meaning it is artificial and wants to be adjacent. isCluster()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. isAssignedRegDep()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. getReg()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. setReg(unsigned Reg)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 void dump(const TargetRegisterInfo *TRI = nullptr) const; 240 }; 241 242 template <> 243 struct isPodLike<SDep> { static const bool value = true; }; 244 245 /// Scheduling unit. This is a node in the scheduling DAG. 246 class SUnit { 247 private: 248 enum : unsigned { BoundaryID = ~0u }; 249 250 SDNode *Node = nullptr; ///< Representative node. 251 MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr. 252 253 public: 254 SUnit *OrigNode = nullptr; ///< If not this, the node from which this node 255 /// was cloned. (SD scheduling only) 256 257 const MCSchedClassDesc *SchedClass = 258 nullptr; ///< nullptr or resolved SchedClass. 259 260 SmallVector<SDep, 4> Preds; ///< All sunit predecessors. 261 SmallVector<SDep, 4> Succs; ///< All sunit successors. 262 263 typedef SmallVectorImpl<SDep>::iterator pred_iterator; 264 typedef SmallVectorImpl<SDep>::iterator succ_iterator; 265 typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator; 266 typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator; 267 268 unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector. 269 unsigned NodeQueueId = 0; ///< Queue id of node. 270 unsigned NumPreds = 0; ///< # of SDep::Data preds. 271 unsigned NumSuccs = 0; ///< # of SDep::Data sucss. 272 unsigned NumPredsLeft = 0; ///< # of preds not scheduled. 273 unsigned NumSuccsLeft = 0; ///< # of succs not scheduled. 274 unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled. 275 unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled. 276 unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use. 277 unsigned short Latency = 0; ///< Node latency. 278 bool isVRegCycle : 1; ///< May use and def the same vreg. 279 bool isCall : 1; ///< Is a function call. 280 bool isCallOp : 1; ///< Is a function call operand. 281 bool isTwoAddress : 1; ///< Is a two-address instruction. 282 bool isCommutable : 1; ///< Is a commutable instruction. 283 bool hasPhysRegUses : 1; ///< Has physreg uses. 284 bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used. 285 bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not. 286 bool isPending : 1; ///< True once pending. 287 bool isAvailable : 1; ///< True once available. 288 bool isScheduled : 1; ///< True once scheduled. 289 bool isScheduleHigh : 1; ///< True if preferable to schedule high. 290 bool isScheduleLow : 1; ///< True if preferable to schedule low. 291 bool isCloned : 1; ///< True if this node has been cloned. 292 bool isUnbuffered : 1; ///< Uses an unbuffered resource. 293 bool hasReservedResource : 1; ///< Uses a reserved resource. 294 Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference. 295 296 private: 297 bool isDepthCurrent : 1; ///< True if Depth is current. 298 bool isHeightCurrent : 1; ///< True if Height is current. 299 unsigned Depth = 0; ///< Node depth. 300 unsigned Height = 0; ///< Node height. 301 302 public: 303 unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready. 304 unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready. 305 306 const TargetRegisterClass *CopyDstRC = 307 nullptr; ///< Is a special copy node if != nullptr. 308 const TargetRegisterClass *CopySrcRC = nullptr; 309 310 /// Constructs an SUnit for pre-regalloc scheduling to represent an 311 /// SDNode and any nodes flagged to it. 312 SUnit(SDNode *node, unsigned nodenum) 313 : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false), 314 isCallOp(false), isTwoAddress(false), isCommutable(false), 315 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 316 isPending(false), isAvailable(false), isScheduled(false), 317 isScheduleHigh(false), isScheduleLow(false), isCloned(false), 318 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 319 isHeightCurrent(false) {} 320 321 /// Constructs an SUnit for post-regalloc scheduling to represent a 322 /// MachineInstr. 323 SUnit(MachineInstr *instr, unsigned nodenum) 324 : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false), 325 isCallOp(false), isTwoAddress(false), isCommutable(false), 326 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 327 isPending(false), isAvailable(false), isScheduled(false), 328 isScheduleHigh(false), isScheduleLow(false), isCloned(false), 329 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false), 330 isHeightCurrent(false) {} 331 332 /// Constructs a placeholder SUnit. 333 SUnit() 334 : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 335 isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false), 336 hasPhysRegClobbers(false), isPending(false), isAvailable(false), 337 isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 338 isCloned(false), isUnbuffered(false), hasReservedResource(false), 339 isDepthCurrent(false), isHeightCurrent(false) {} 340 341 /// Boundary nodes are placeholders for the boundary of the 342 /// scheduling region. 343 /// 344 /// BoundaryNodes can have DAG edges, including Data edges, but they do not 345 /// correspond to schedulable entities (e.g. instructions) and do not have a 346 /// valid ID. Consequently, always check for boundary nodes before accessing 347 /// an associative data structure keyed on node ID. 348 bool isBoundaryNode() const { return NodeNum == BoundaryID; } 349 350 /// Assigns the representative SDNode for this SUnit. This may be used 351 /// during pre-regalloc scheduling. 352 void setNode(SDNode *N) { 353 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 354 Node = N; 355 } 356 357 /// Returns the representative SDNode for this SUnit. This may be used 358 /// during pre-regalloc scheduling. 359 SDNode *getNode() const { 360 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 361 return Node; 362 } 363 364 /// Returns true if this SUnit refers to a machine instruction as 365 /// opposed to an SDNode. 366 bool isInstr() const { return Instr; } 367 368 /// Assigns the instruction for the SUnit. This may be used during 369 /// post-regalloc scheduling. 370 void setInstr(MachineInstr *MI) { 371 assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 372 Instr = MI; 373 } 374 375 /// Returns the representative MachineInstr for this SUnit. This may be used 376 /// during post-regalloc scheduling. 377 MachineInstr *getInstr() const { 378 assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 379 return Instr; 380 } 381 382 /// Adds the specified edge as a pred of the current node if not already. 383 /// It also adds the current node as a successor of the specified node. 384 bool addPred(const SDep &D, bool Required = true); 385 386 /// Adds a barrier edge to SU by calling addPred(), with latency 0 387 /// generally or latency 1 for a store followed by a load. 388 bool addPredBarrier(SUnit *SU) { 389 SDep Dep(SU, SDep::Barrier); 390 unsigned TrueMemOrderLatency = 391 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0); 392 Dep.setLatency(TrueMemOrderLatency); 393 return addPred(Dep); 394 } 395 396 /// Removes the specified edge as a pred of the current node if it exists. 397 /// It also removes the current node as a successor of the specified node. 398 void removePred(const SDep &D); 399 400 /// Returns the depth of this node, which is the length of the maximum path 401 /// up to any node which has no predecessors. 402 unsigned getDepth() const { 403 if (!isDepthCurrent) 404 const_cast<SUnit *>(this)->ComputeDepth(); 405 return Depth; 406 } 407 408 /// Returns the height of this node, which is the length of the 409 /// maximum path down to any node which has no successors. 410 unsigned getHeight() const { 411 if (!isHeightCurrent) 412 const_cast<SUnit *>(this)->ComputeHeight(); 413 return Height; 414 } 415 416 /// If NewDepth is greater than this node's depth value, sets it to 417 /// be the new depth value. This also recursively marks successor nodes 418 /// dirty. 419 void setDepthToAtLeast(unsigned NewDepth); 420 421 /// If NewDepth is greater than this node's depth value, set it to be 422 /// the new height value. This also recursively marks predecessor nodes 423 /// dirty. 424 void setHeightToAtLeast(unsigned NewHeight); 425 426 /// Sets a flag in this node to indicate that its stored Depth value 427 /// will require recomputation the next time getDepth() is called. 428 void setDepthDirty(); 429 430 /// Sets a flag in this node to indicate that its stored Height value 431 /// will require recomputation the next time getHeight() is called. 432 void setHeightDirty(); 433 434 /// Tests if node N is a predecessor of this node. 435 bool isPred(const SUnit *N) const { 436 for (const SDep &Pred : Preds) 437 if (Pred.getSUnit() == N) 438 return true; 439 return false; 440 } 441 442 /// Tests if node N is a successor of this node. 443 bool isSucc(const SUnit *N) const { 444 for (const SDep &Succ : Succs) 445 if (Succ.getSUnit() == N) 446 return true; 447 return false; 448 } 449 450 bool isTopReady() const { 451 return NumPredsLeft == 0; 452 } 453 bool isBottomReady() const { 454 return NumSuccsLeft == 0; 455 } 456 457 /// Orders this node's predecessor edges such that the critical path 458 /// edge occurs first. 459 void biasCriticalPath(); 460 461 void dumpAttributes() 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 /// 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 LLVMTargetMachine &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 virtual void dump() const = 0; 596 void dumpNodeName(const SUnit &SU) const; 597 598 /// Returns a label for an SUnit node in a visualization of the ScheduleDAG. 599 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 600 601 /// Returns a label for the region of code covered by the DAG. 602 virtual std::string getDAGName() const = 0; 603 604 /// Adds custom features for a visualization of the ScheduleDAG. 605 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 606 607 #ifndef NDEBUG 608 /// Verifies that all SUnits were scheduled and that their state is 609 /// consistent. Returns the number of scheduled SUnits. 610 unsigned VerifyScheduledDAG(bool isBottomUp); 611 #endif 612 613 protected: 614 void dumpNodeAll(const SUnit &SU) const; 615 616 private: 617 /// Returns the MCInstrDesc of this SDNode or NULL. 618 const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 619 }; 620 621 class SUnitIterator : public std::iterator<std::forward_iterator_tag, 622 SUnit, ptrdiff_t> { 623 SUnit *Node; 624 unsigned Operand; 625 626 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 627 628 public: 629 bool operator==(const SUnitIterator& x) const { 630 return Operand == x.Operand; 631 } 632 bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 633 634 pointer operator*() const { 635 return Node->Preds[Operand].getSUnit(); 636 } 637 pointer operator->() const { return operator*(); } 638 639 SUnitIterator& operator++() { // Preincrement 640 ++Operand; 641 return *this; 642 } 643 SUnitIterator operator++(int) { // Postincrement 644 SUnitIterator tmp = *this; ++*this; return tmp; 645 } 646 647 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 648 static SUnitIterator end (SUnit *N) { 649 return SUnitIterator(N, (unsigned)N->Preds.size()); 650 } 651 652 unsigned getOperand() const { return Operand; } 653 const SUnit *getNode() const { return Node; } 654 655 /// Tests if this is not an SDep::Data dependence. 656 bool isCtrlDep() const { 657 return getSDep().isCtrl(); 658 } 659 bool isArtificialDep() const { 660 return getSDep().isArtificial(); 661 } 662 const SDep &getSDep() const { 663 return Node->Preds[Operand]; 664 } 665 }; 666 667 template <> struct GraphTraits<SUnit*> { 668 typedef SUnit *NodeRef; 669 typedef SUnitIterator ChildIteratorType; 670 static NodeRef getEntryNode(SUnit *N) { return N; } 671 static ChildIteratorType child_begin(NodeRef N) { 672 return SUnitIterator::begin(N); 673 } 674 static ChildIteratorType child_end(NodeRef N) { 675 return SUnitIterator::end(N); 676 } 677 }; 678 679 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 680 typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator; 681 static nodes_iterator nodes_begin(ScheduleDAG *G) { 682 return nodes_iterator(G->SUnits.begin()); 683 } 684 static nodes_iterator nodes_end(ScheduleDAG *G) { 685 return nodes_iterator(G->SUnits.end()); 686 } 687 }; 688 689 /// This class can compute a topological ordering for SUnits and provides 690 /// methods for dynamically updating the ordering as new edges are added. 691 /// 692 /// This allows a very fast implementation of IsReachable, for example. 693 class ScheduleDAGTopologicalSort { 694 /// A reference to the ScheduleDAG's SUnits. 695 std::vector<SUnit> &SUnits; 696 SUnit *ExitSU; 697 698 /// Maps topological index to the node number. 699 std::vector<int> Index2Node; 700 /// Maps the node number to its topological index. 701 std::vector<int> Node2Index; 702 /// a set of nodes visited during a DFS traversal. 703 BitVector Visited; 704 705 /// Makes a DFS traversal and mark all nodes affected by the edge insertion. 706 /// These nodes will later get new topological indexes by means of the Shift 707 /// method. 708 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 709 710 /// Reassigns topological indexes for the nodes in the DAG to 711 /// preserve the topological ordering. 712 void Shift(BitVector& Visited, int LowerBound, int UpperBound); 713 714 /// Assigns the topological index to the node n. 715 void Allocate(int n, int index); 716 717 public: 718 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 719 720 /// Creates the initial topological ordering from the DAG to be scheduled. 721 void InitDAGTopologicalSorting(); 722 723 /// Returns an array of SUs that are both in the successor 724 /// subtree of StartSU and in the predecessor subtree of TargetSU. 725 /// StartSU and TargetSU are not in the array. 726 /// Success is false if TargetSU is not in the successor subtree of 727 /// StartSU, else it is true. 728 std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, 729 bool &Success); 730 731 /// Checks if \p SU is reachable from \p TargetSU. 732 bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 733 734 /// Returns true if addPred(TargetSU, SU) creates a cycle. 735 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); 736 737 /// Updates the topological ordering to accommodate an edge to be 738 /// added from SUnit \p X to SUnit \p Y. 739 void AddPred(SUnit *Y, SUnit *X); 740 741 /// Updates the topological ordering to accommodate an an edge to be 742 /// removed from the specified node \p N from the predecessors of the 743 /// current node \p M. 744 void RemovePred(SUnit *M, SUnit *N); 745 746 typedef std::vector<int>::iterator iterator; 747 typedef std::vector<int>::const_iterator const_iterator; 748 iterator begin() { return Index2Node.begin(); } 749 const_iterator begin() const { return Index2Node.begin(); } 750 iterator end() { return Index2Node.end(); } 751 const_iterator end() const { return Index2Node.end(); } 752 753 typedef std::vector<int>::reverse_iterator reverse_iterator; 754 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 755 reverse_iterator rbegin() { return Index2Node.rbegin(); } 756 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 757 reverse_iterator rend() { return Index2Node.rend(); } 758 const_reverse_iterator rend() const { return Index2Node.rend(); } 759 }; 760 761 } // end namespace llvm 762 763 #endif // LLVM_CODEGEN_SCHEDULEDAG_H 764