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