LLVM API Documentation

ScheduleDAG.h

Go to the documentation of this file.
00001 //===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the ScheduleDAG class, which is used as the common
00011 // base class for instruction schedulers.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
00016 #define LLVM_CODEGEN_SCHEDULEDAG_H
00017 
00018 #include "llvm/CodeGen/MachineBasicBlock.h"
00019 #include "llvm/ADT/DenseMap.h"
00020 #include "llvm/ADT/BitVector.h"
00021 #include "llvm/ADT/GraphTraits.h"
00022 #include "llvm/ADT/SmallVector.h"
00023 #include "llvm/ADT/PointerIntPair.h"
00024 
00025 namespace llvm {
00026   class SUnit;
00027   class MachineConstantPool;
00028   class MachineFunction;
00029   class MachineModuleInfo;
00030   class MachineRegisterInfo;
00031   class MachineInstr;
00032   class TargetRegisterInfo;
00033   class ScheduleDAG;
00034   class SDNode;
00035   class TargetInstrInfo;
00036   class TargetInstrDesc;
00037   class TargetLowering;
00038   class TargetMachine;
00039   class TargetRegisterClass;
00040   template<class Graph> class GraphWriter;
00041 
00042   /// SDep - Scheduling dependency. This represents one direction of an
00043   /// edge in the scheduling DAG.
00044   class SDep {
00045   public:
00046     /// Kind - These are the different kinds of scheduling dependencies.
00047     enum Kind {
00048       Data,        ///< Regular data dependence (aka true-dependence).
00049       Anti,        ///< A register anti-dependedence (aka WAR).
00050       Output,      ///< A register output-dependence (aka WAW).
00051       Order        ///< Any other ordering dependency.
00052     };
00053 
00054   private:
00055     /// Dep - A pointer to the depending/depended-on SUnit, and an enum
00056     /// indicating the kind of the dependency.
00057     PointerIntPair<SUnit *, 2, Kind> Dep;
00058 
00059     /// Contents - A union discriminated by the dependence kind.
00060     union {
00061       /// Reg - For Data, Anti, and Output dependencies, the associated
00062       /// register. For Data dependencies that don't currently have a register
00063       /// assigned, this is set to zero.
00064       unsigned Reg;
00065 
00066       /// Order - Additional information about Order dependencies.
00067       struct {
00068         /// isNormalMemory - True if both sides of the dependence
00069         /// access memory in non-volatile and fully modeled ways.
00070         bool isNormalMemory : 1;
00071 
00072         /// isMustAlias - True if both sides of the dependence are known to
00073         /// access the same memory.
00074         bool isMustAlias : 1;
00075 
00076         /// isArtificial - True if this is an artificial dependency, meaning
00077         /// it is not necessary for program correctness, and may be safely
00078         /// deleted if necessary.
00079         bool isArtificial : 1;
00080       } Order;
00081     } Contents;
00082 
00083     /// Latency - The time associated with this edge. Often this is just
00084     /// the value of the Latency field of the predecessor, however advanced
00085     /// models may provide additional information about specific edges.
00086     unsigned Latency;
00087 
00088   public:
00089     /// SDep - Construct a null SDep. This is only for use by container
00090     /// classes which require default constructors. SUnits may not
00091     /// have null SDep edges.
00092     SDep() : Dep(0, Data) {}
00093 
00094     /// SDep - Construct an SDep with the specified values.
00095     SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0,
00096          bool isNormalMemory = false, bool isMustAlias = false,
00097          bool isArtificial = false)
00098       : Dep(S, kind), Contents(), Latency(latency) {
00099       switch (kind) {
00100       case Anti:
00101       case Output:
00102         assert(Reg != 0 &&
00103                "SDep::Anti and SDep::Output must use a non-zero Reg!");
00104         // fall through
00105       case Data:
00106         assert(!isMustAlias && "isMustAlias only applies with SDep::Order!");
00107         assert(!isArtificial && "isArtificial only applies with SDep::Order!");
00108         Contents.Reg = Reg;
00109         break;
00110       case Order:
00111         assert(Reg == 0 && "Reg given for non-register dependence!");
00112         Contents.Order.isNormalMemory = isNormalMemory;
00113         Contents.Order.isMustAlias = isMustAlias;
00114         Contents.Order.isArtificial = isArtificial;
00115         break;
00116       }
00117     }
00118 
00119     bool operator==(const SDep &Other) const {
00120       if (Dep != Other.Dep || Latency != Other.Latency) return false;
00121       switch (Dep.getInt()) {
00122       case Data:
00123       case Anti:
00124       case Output:
00125         return Contents.Reg == Other.Contents.Reg;
00126       case Order:
00127         return Contents.Order.isNormalMemory ==
00128                  Other.Contents.Order.isNormalMemory &&
00129                Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias &&
00130                Contents.Order.isArtificial == Other.Contents.Order.isArtificial;
00131       }
00132       assert(0 && "Invalid dependency kind!");
00133       return false;
00134     }
00135 
00136     bool operator!=(const SDep &Other) const {
00137       return !operator==(Other);
00138     }
00139 
00140     /// getLatency - Return the latency value for this edge, which roughly
00141     /// means the minimum number of cycles that must elapse between the
00142     /// predecessor and the successor, given that they have this edge
00143     /// between them.
00144     unsigned getLatency() const {
00145       return Latency;
00146     }
00147 
00148     /// setLatency - Set the latency for this edge.
00149     void setLatency(unsigned Lat) {
00150       Latency = Lat;
00151     }
00152 
00153     //// getSUnit - Return the SUnit to which this edge points.
00154     SUnit *getSUnit() const {
00155       return Dep.getPointer();
00156     }
00157 
00158     //// setSUnit - Assign the SUnit to which this edge points.
00159     void setSUnit(SUnit *SU) {
00160       Dep.setPointer(SU);
00161     }
00162 
00163     /// getKind - Return an enum value representing the kind of the dependence.
00164     Kind getKind() const {
00165       return Dep.getInt();
00166     }
00167 
00168     /// isCtrl - Shorthand for getKind() != SDep::Data.
00169     bool isCtrl() const {
00170       return getKind() != Data;
00171     }
00172 
00173     /// isNormalMemory - Test if this is an Order dependence between two
00174     /// memory accesses where both sides of the dependence access memory
00175     /// in non-volatile and fully modeled ways.
00176     bool isNormalMemory() const {
00177       return getKind() == Order && Contents.Order.isNormalMemory;
00178     }
00179 
00180     /// isMustAlias - Test if this is an Order dependence that is marked
00181     /// as "must alias", meaning that the SUnits at either end of the edge
00182     /// have a memory dependence on a known memory location.
00183     bool isMustAlias() const {
00184       return getKind() == Order && Contents.Order.isMustAlias;
00185     }
00186 
00187     /// isArtificial - Test if this is an Order dependence that is marked
00188     /// as "artificial", meaning it isn't necessary for correctness.
00189     bool isArtificial() const {
00190       return getKind() == Order && Contents.Order.isArtificial;
00191     }
00192 
00193     /// isAssignedRegDep - Test if this is a Data dependence that is
00194     /// associated with a register.
00195     bool isAssignedRegDep() const {
00196       return getKind() == Data && Contents.Reg != 0;
00197     }
00198 
00199     /// getReg - Return the register associated with this edge. This is
00200     /// only valid on Data, Anti, and Output edges. On Data edges, this
00201     /// value may be zero, meaning there is no associated register.
00202     unsigned getReg() const {
00203       assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
00204              "getReg called on non-register dependence edge!");
00205       return Contents.Reg;
00206     }
00207 
00208     /// setReg - Assign the associated register for this edge. This is
00209     /// only valid on Data, Anti, and Output edges. On Anti and Output
00210     /// edges, this value must not be zero. On Data edges, the value may
00211     /// be zero, which would mean that no specific register is associated
00212     /// with this edge.
00213     void setReg(unsigned Reg) {
00214       assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
00215              "setReg called on non-register dependence edge!");
00216       assert((getKind() != Anti || Reg != 0) &&
00217              "SDep::Anti edge cannot use the zero register!");
00218       assert((getKind() != Output || Reg != 0) &&
00219              "SDep::Output edge cannot use the zero register!");
00220       Contents.Reg = Reg;
00221     }
00222   };
00223 
00224   /// SUnit - Scheduling unit. This is a node in the scheduling DAG.
00225   class SUnit {
00226   private:
00227     SDNode *Node;                       // Representative node.
00228     MachineInstr *Instr;                // Alternatively, a MachineInstr.
00229   public:
00230     SUnit *OrigNode;                    // If not this, the node from which
00231                                         // this node was cloned.
00232     
00233     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
00234     // is true if the edge is a token chain edge, false if it is a value edge. 
00235     SmallVector<SDep, 4> Preds;  // All sunit predecessors.
00236     SmallVector<SDep, 4> Succs;  // All sunit successors.
00237 
00238     typedef SmallVector<SDep, 4>::iterator pred_iterator;
00239     typedef SmallVector<SDep, 4>::iterator succ_iterator;
00240     typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
00241     typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
00242     
00243     unsigned NodeNum;                   // Entry # of node in the node vector.
00244     unsigned NodeQueueId;               // Queue id of node.
00245     unsigned short Latency;             // Node latency.
00246     short NumPreds;                     // # of SDep::Data preds.
00247     short NumSuccs;                     // # of SDep::Data sucss.
00248     short NumPredsLeft;                 // # of preds not scheduled.
00249     short NumSuccsLeft;                 // # of succs not scheduled.
00250     bool isTwoAddress     : 1;          // Is a two-address instruction.
00251     bool isCommutable     : 1;          // Is a commutable instruction.
00252     bool hasPhysRegDefs   : 1;          // Has physreg defs that are being used.
00253     bool hasPhysRegClobbers : 1;        // Has any physreg defs, used or not.
00254     bool isPending        : 1;          // True once pending.
00255     bool isAvailable      : 1;          // True once available.
00256     bool isScheduled      : 1;          // True once scheduled.
00257     bool isScheduleHigh   : 1;          // True if preferable to schedule high.
00258     bool isCloned         : 1;          // True if this node has been cloned.
00259   private:
00260     bool isDepthCurrent   : 1;          // True if Depth is current.
00261     bool isHeightCurrent  : 1;          // True if Height is current.
00262     unsigned Depth;                     // Node depth.
00263     unsigned Height;                    // Node height.
00264   public:
00265     const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
00266     const TargetRegisterClass *CopySrcRC;
00267     
00268     /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
00269     /// an SDNode and any nodes flagged to it.
00270     SUnit(SDNode *node, unsigned nodenum)
00271       : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
00272         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
00273         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
00274         hasPhysRegClobbers(false),
00275         isPending(false), isAvailable(false), isScheduled(false),
00276         isScheduleHigh(false), isCloned(false),
00277         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
00278         CopyDstRC(NULL), CopySrcRC(NULL) {}
00279 
00280     /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
00281     /// a MachineInstr.
00282     SUnit(MachineInstr *instr, unsigned nodenum)
00283       : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
00284         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
00285         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
00286         hasPhysRegClobbers(false),
00287         isPending(false), isAvailable(false), isScheduled(false),
00288         isScheduleHigh(false), isCloned(false),
00289         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
00290         CopyDstRC(NULL), CopySrcRC(NULL) {}
00291 
00292     /// SUnit - Construct a placeholder SUnit.
00293     SUnit()
00294       : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), NodeQueueId(0),
00295         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
00296         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
00297         hasPhysRegClobbers(false),
00298         isPending(false), isAvailable(false), isScheduled(false),
00299         isScheduleHigh(false), isCloned(false),
00300         isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
00301         CopyDstRC(NULL), CopySrcRC(NULL) {}
00302 
00303     /// setNode - Assign the representative SDNode for this SUnit.
00304     /// This may be used during pre-regalloc scheduling.
00305     void setNode(SDNode *N) {
00306       assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
00307       Node = N;
00308     }
00309 
00310     /// getNode - Return the representative SDNode for this SUnit.
00311     /// This may be used during pre-regalloc scheduling.
00312     SDNode *getNode() const {
00313       assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
00314       return Node;
00315     }
00316 
00317     /// setInstr - Assign the instruction for the SUnit.
00318     /// This may be used during post-regalloc scheduling.
00319     void setInstr(MachineInstr *MI) {
00320       assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
00321       Instr = MI;
00322     }
00323 
00324     /// getInstr - Return the representative MachineInstr for this SUnit.
00325     /// This may be used during post-regalloc scheduling.
00326     MachineInstr *getInstr() const {
00327       assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
00328       return Instr;
00329     }
00330 
00331     /// addPred - This adds the specified edge as a pred of the current node if
00332     /// not already.  It also adds the current node as a successor of the
00333     /// specified node.
00334     void addPred(const SDep &D);
00335 
00336     /// removePred - This removes the specified edge as a pred of the current
00337     /// node if it exists.  It also removes the current node as a successor of
00338     /// the specified node.
00339     void removePred(const SDep &D);
00340 
00341     /// getDepth - Return the depth of this node, which is the length of the
00342     /// maximum path up to any node with has no predecessors.
00343     unsigned getDepth() const {
00344       if (!isDepthCurrent) const_cast<SUnit *>(this)->ComputeDepth();
00345       return Depth;
00346     }
00347 
00348     /// getHeight - Return the height of this node, which is the length of the
00349     /// maximum path down to any node with has no successors.
00350     unsigned getHeight() const {
00351       if (!isHeightCurrent) const_cast<SUnit *>(this)->ComputeHeight();
00352       return Height;
00353     }
00354 
00355     /// setDepthToAtLeast - If NewDepth is greater than this node's depth
00356     /// value, set it to be the new depth value. This also recursively
00357     /// marks successor nodes dirty.
00358     void setDepthToAtLeast(unsigned NewDepth);
00359 
00360     /// setDepthToAtLeast - If NewDepth is greater than this node's depth
00361     /// value, set it to be the new height value. This also recursively
00362     /// marks predecessor nodes dirty.
00363     void setHeightToAtLeast(unsigned NewHeight);
00364 
00365     /// setDepthDirty - Set a flag in this node to indicate that its
00366     /// stored Depth value will require recomputation the next time
00367     /// getDepth() is called.
00368     void setDepthDirty();
00369 
00370     /// setHeightDirty - Set a flag in this node to indicate that its
00371     /// stored Height value will require recomputation the next time
00372     /// getHeight() is called.
00373     void setHeightDirty();
00374 
00375     /// isPred - Test if node N is a predecessor of this node.
00376     bool isPred(SUnit *N) {
00377       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
00378         if (Preds[i].getSUnit() == N)
00379           return true;
00380       return false;
00381     }
00382     
00383     /// isSucc - Test if node N is a successor of this node.
00384     bool isSucc(SUnit *N) {
00385       for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
00386         if (Succs[i].getSUnit() == N)
00387           return true;
00388       return false;
00389     }
00390     
00391     void dump(const ScheduleDAG *G) const;
00392     void dumpAll(const ScheduleDAG *G) const;
00393     void print(raw_ostream &O, const ScheduleDAG *G) const;
00394 
00395   private:
00396     void ComputeDepth();
00397     void ComputeHeight();
00398   };
00399 
00400   //===--------------------------------------------------------------------===//
00401   /// SchedulingPriorityQueue - This interface is used to plug different
00402   /// priorities computation algorithms into the list scheduler. It implements
00403   /// the interface of a standard priority queue, where nodes are inserted in 
00404   /// arbitrary order and returned in priority order.  The computation of the
00405   /// priority and the representation of the queue are totally up to the
00406   /// implementation to decide.
00407   /// 
00408   class SchedulingPriorityQueue {
00409   public:
00410     virtual ~SchedulingPriorityQueue() {}
00411   
00412     virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
00413     virtual void addNode(const SUnit *SU) = 0;
00414     virtual void updateNode(const SUnit *SU) = 0;
00415     virtual void releaseState() = 0;
00416 
00417     virtual unsigned size() const = 0;
00418     virtual bool empty() const = 0;
00419     virtual void push(SUnit *U) = 0;
00420   
00421     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
00422     virtual SUnit *pop() = 0;
00423 
00424     virtual void remove(SUnit *SU) = 0;
00425 
00426     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
00427     /// allows the priority function to adjust the priority of related
00428     /// unscheduled nodes, for example.
00429     ///
00430     virtual void ScheduledNode(SUnit *) {}
00431 
00432     virtual void UnscheduledNode(SUnit *) {}
00433   };
00434 
00435   class ScheduleDAG {
00436   public:
00437     MachineBasicBlock *BB;                // The block in which to insert instructions.
00438     MachineBasicBlock::iterator InsertPos;// The position to insert instructions.
00439     const TargetMachine &TM;              // Target processor
00440     const TargetInstrInfo *TII;           // Target instruction information
00441     const TargetRegisterInfo *TRI;        // Target processor register info
00442     const TargetLowering *TLI;            // Target lowering info
00443     MachineFunction &MF;                  // Machine function
00444     MachineRegisterInfo &MRI;             // Virtual/real register map
00445     MachineConstantPool *ConstPool;       // Target constant pool
00446     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
00447                                           // represent noop instructions.
00448     std::vector<SUnit> SUnits;            // The scheduling units.
00449     SUnit EntrySU;                        // Special node for the region entry.
00450     SUnit ExitSU;                         // Special node for the region exit.
00451 
00452     explicit ScheduleDAG(MachineFunction &mf);
00453 
00454     virtual ~ScheduleDAG();
00455 
00456     /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
00457     /// using 'dot'.
00458     ///
00459     void viewGraph();
00460   
00461     /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
00462     /// according to the order specified in Sequence.
00463     ///
00464     virtual MachineBasicBlock *EmitSchedule() = 0;
00465 
00466     void dumpSchedule() const;
00467 
00468     virtual void dumpNode(const SUnit *SU) const = 0;
00469 
00470     /// getGraphNodeLabel - Return a label for an SUnit node in a visualization
00471     /// of the ScheduleDAG.
00472     virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
00473 
00474     /// addCustomGraphFeatures - Add custom features for a visualization of
00475     /// the ScheduleDAG.
00476     virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
00477 
00478 #ifndef NDEBUG
00479     /// VerifySchedule - Verify that all SUnits were scheduled and that
00480     /// their state is consistent.
00481     void VerifySchedule(bool isBottomUp);
00482 #endif
00483 
00484   protected:
00485     /// Run - perform scheduling.
00486     ///
00487     void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos);
00488 
00489     /// BuildSchedGraph - Build SUnits and set up their Preds and Succs
00490     /// to form the scheduling dependency graph.
00491     ///
00492     virtual void BuildSchedGraph() = 0;
00493 
00494     /// ComputeLatency - Compute node latency.
00495     ///
00496     virtual void ComputeLatency(SUnit *SU) = 0;
00497 
00498     /// ComputeOperandLatency - Override dependence edge latency using
00499     /// operand use/def information
00500     ///
00501     virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use,
00502                                        SDep& dep) const { };
00503 
00504     /// Schedule - Order nodes according to selected style, filling
00505     /// in the Sequence member.
00506     ///
00507     virtual void Schedule() = 0;
00508 
00509     /// ForceUnitLatencies - Return true if all scheduling edges should be given a
00510     /// latency value of one.  The default is to return false; schedulers may
00511     /// override this as needed.
00512     virtual bool ForceUnitLatencies() const { return false; }
00513 
00514     /// EmitNoop - Emit a noop instruction.
00515     ///
00516     void EmitNoop();
00517 
00518     void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO);
00519 
00520     void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
00521 
00522   private:
00523     /// EmitLiveInCopy - Emit a copy for a live in physical register. If the
00524     /// physical register has only a single copy use, then coalesced the copy
00525     /// if possible.
00526     void EmitLiveInCopy(MachineBasicBlock *MBB,
00527                         MachineBasicBlock::iterator &InsertPos,
00528                         unsigned VirtReg, unsigned PhysReg,
00529                         const TargetRegisterClass *RC,
00530                         DenseMap<MachineInstr*, unsigned> &CopyRegMap);
00531 
00532     /// EmitLiveInCopies - If this is the first basic block in the function,
00533     /// and if it has live ins that need to be copied into vregs, emit the
00534     /// copies into the top of the block.
00535     void EmitLiveInCopies(MachineBasicBlock *MBB);
00536   };
00537 
00538   class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> {
00539     SUnit *Node;
00540     unsigned Operand;
00541 
00542     SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
00543   public:
00544     bool operator==(const SUnitIterator& x) const {
00545       return Operand == x.Operand;
00546     }
00547     bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
00548 
00549     const SUnitIterator &operator=(const SUnitIterator &I) {
00550       assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
00551       Operand = I.Operand;
00552       return *this;
00553     }
00554 
00555     pointer operator*() const {
00556       return Node->Preds[Operand].getSUnit();
00557     }
00558     pointer operator->() const { return operator*(); }
00559 
00560     SUnitIterator& operator++() {                // Preincrement
00561       ++Operand;
00562       return *this;
00563     }
00564     SUnitIterator operator++(int) { // Postincrement
00565       SUnitIterator tmp = *this; ++*this; return tmp;
00566     }
00567 
00568     static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
00569     static SUnitIterator end  (SUnit *N) {
00570       return SUnitIterator(N, (unsigned)N->Preds.size());
00571     }
00572 
00573     unsigned getOperand() const { return Operand; }
00574     const SUnit *getNode() const { return Node; }
00575     /// isCtrlDep - Test if this is not an SDep::Data dependence.
00576     bool isCtrlDep() const {
00577       return getSDep().isCtrl();
00578     }
00579     bool isArtificialDep() const {
00580       return getSDep().isArtificial();
00581     }
00582     const SDep &getSDep() const {
00583       return Node->Preds[Operand];
00584     }
00585   };
00586 
00587   template <> struct GraphTraits<SUnit*> {
00588     typedef SUnit NodeType;
00589     typedef SUnitIterator ChildIteratorType;
00590     static inline NodeType *getEntryNode(SUnit *N) { return N; }
00591     static inline ChildIteratorType child_begin(NodeType *N) {
00592       return SUnitIterator::begin(N);
00593     }
00594     static inline ChildIteratorType child_end(NodeType *N) {
00595       return SUnitIterator::end(N);
00596     }
00597   };
00598 
00599   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
00600     typedef std::vector<SUnit>::iterator nodes_iterator;
00601     static nodes_iterator nodes_begin(ScheduleDAG *G) {
00602       return G->SUnits.begin();
00603     }
00604     static nodes_iterator nodes_end(ScheduleDAG *G) {
00605       return G->SUnits.end();
00606     }
00607   };
00608 
00609   /// ScheduleDAGTopologicalSort is a class that computes a topological
00610   /// ordering for SUnits and provides methods for dynamically updating
00611   /// the ordering as new edges are added.
00612   ///
00613   /// This allows a very fast implementation of IsReachable, for example.
00614   ///
00615   class ScheduleDAGTopologicalSort {
00616     /// SUnits - A reference to the ScheduleDAG's SUnits.
00617     std::vector<SUnit> &SUnits;
00618 
00619     /// Index2Node - Maps topological index to the node number.
00620     std::vector<int> Index2Node;
00621     /// Node2Index - Maps the node number to its topological index.
00622     std::vector<int> Node2Index;
00623     /// Visited - a set of nodes visited during a DFS traversal.
00624     BitVector Visited;
00625 
00626     /// DFS - make a DFS traversal and mark all nodes affected by the 
00627     /// edge insertion. These nodes will later get new topological indexes
00628     /// by means of the Shift method.
00629     void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
00630 
00631     /// Shift - reassign topological indexes for the nodes in the DAG
00632     /// to preserve the topological ordering.
00633     void Shift(BitVector& Visited, int LowerBound, int UpperBound);
00634 
00635     /// Allocate - assign the topological index to the node n.
00636     void Allocate(int n, int index);
00637 
00638   public:
00639     explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits);
00640 
00641     /// InitDAGTopologicalSorting - create the initial topological 
00642     /// ordering from the DAG to be scheduled.
00643     void InitDAGTopologicalSorting();
00644 
00645     /// IsReachable - Checks if SU is reachable from TargetSU.
00646     bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
00647 
00648     /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU
00649     /// will create a cycle.
00650     bool WillCreateCycle(SUnit *SU, SUnit *TargetSU);
00651 
00652     /// AddPred - Updates the topological ordering to accomodate an edge
00653     /// to be added from SUnit X to SUnit Y.
00654     void AddPred(SUnit *Y, SUnit *X);
00655 
00656     /// RemovePred - Updates the topological ordering to accomodate an
00657     /// an edge to be removed from the specified node N from the predecessors
00658     /// of the current node M.
00659     void RemovePred(SUnit *M, SUnit *N);
00660 
00661     typedef std::vector<int>::iterator iterator;
00662     typedef std::vector<int>::const_iterator const_iterator;
00663     iterator begin() { return Index2Node.begin(); }
00664     const_iterator begin() const { return Index2Node.begin(); }
00665     iterator end() { return Index2Node.end(); }
00666     const_iterator end() const { return Index2Node.end(); }
00667 
00668     typedef std::vector<int>::reverse_iterator reverse_iterator;
00669     typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
00670     reverse_iterator rbegin() { return Index2Node.rbegin(); }
00671     const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
00672     reverse_iterator rend() { return Index2Node.rend(); }
00673     const_reverse_iterator rend() const { return Index2Node.rend(); }
00674   };
00675 }
00676 
00677 #endif