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