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