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