contrib/llvm/include/llvm/CodeGen/ScheduleDAG.h

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