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