include/llvm/CodeGen/ScheduleDAG.h

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