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 SelectionDAG-based instruction scheduler.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
  16 #define LLVM_CODEGEN_SCHEDULEDAG_H
  17
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/CodeGen/SelectionDAG.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/GraphTraits.h"
  22 #include "llvm/ADT/SmallSet.h"
  23
  24 namespace llvm {
  25   struct SUnit;
  26   class MachineConstantPool;
  27   class MachineFunction;
  28   class MachineModuleInfo;
  29   class MachineRegisterInfo;
  30   class MachineInstr;
  31   class TargetRegisterInfo;
  32   class SelectionDAG;
  33   class SelectionDAGISel;
  34   class TargetInstrInfo;
  35   class TargetInstrDesc;
  36   class TargetLowering;
  37   class TargetMachine;
  38   class TargetRegisterClass;
  39
  40   /// HazardRecognizer - This determines whether or not an instruction can be
  41   /// issued this cycle, and whether or not a noop needs to be inserted to handle
  42   /// the hazard.
  43   class HazardRecognizer {
  44   public:
  45     virtual ~HazardRecognizer();
  46
  47     enum HazardType {
  48       NoHazard,      // This instruction can be emitted at this cycle.
  49       Hazard,        // This instruction can't be emitted at this cycle.
  50       NoopHazard     // This instruction can't be emitted, and needs noops.
  51     };
  52
  53     /// getHazardType - Return the hazard type of emitting this node.  There are
  54     /// three possible results.  Either:
  55     ///  * NoHazard: it is legal to issue this instruction on this cycle.
  56     ///  * Hazard: issuing this instruction would stall the machine.  If some
  57     ///     other instruction is available, issue it first.
  58     ///  * NoopHazard: issuing this instruction would break the program.  If
  59     ///     some other instruction can be issued, do so, otherwise issue a noop.
  60     virtual HazardType getHazardType(SDNode *) {
  61       return NoHazard;
  62     }
  63
  64     /// EmitInstruction - This callback is invoked when an instruction is
  65     /// emitted, to advance the hazard state.
  66     virtual void EmitInstruction(SDNode *) {}
  67
  68     /// AdvanceCycle - This callback is invoked when no instructions can be
  69     /// issued on this cycle without a hazard.  This should increment the
  70     /// internal state of the hazard recognizer so that previously "Hazard"
  71     /// instructions will now not be hazards.
  72     virtual void AdvanceCycle() {}
  73
  74     /// EmitNoop - This callback is invoked when a noop was added to the
  75     /// instruction stream.
  76     virtual void EmitNoop() {}
  77   };
  78
  79   /// SDep - Scheduling dependency. It keeps track of dependent nodes,
  80   /// cost of the depdenency, etc.
  81   struct SDep {
  82     SUnit    *Dep;           // Dependent - either a predecessor or a successor.
  83     unsigned  Reg;           // If non-zero, this dep is a phy register dependency.
  84     int       Cost;          // Cost of the dependency.
  85     bool      isCtrl    : 1; // True iff it's a control dependency.
  86     bool      isSpecial : 1; // True iff it's a special ctrl dep added during sched.
  87     SDep(SUnit *d, unsigned r, int t, bool c, bool s)
  88       : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {}
  89   };
  90
  91   /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
  92   /// a group of nodes flagged together.
  93   struct SUnit {
  94   private:
  95     SDNode *Node;                       // Representative node.
  96     MachineInstr *Instr;                // Alternatively, a MachineInstr.
  97   public:
  98     SUnit *OrigNode;                    // If not this, the node from which
  99                                         // this node was cloned.
 100
 101     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
 102     // is true if the edge is a token chain edge, false if it is a value edge.
 103     SmallVector<SDep, 4> Preds;  // All sunit predecessors.
 104     SmallVector<SDep, 4> Succs;  // All sunit successors.
 105
 106     typedef SmallVector<SDep, 4>::iterator pred_iterator;
 107     typedef SmallVector<SDep, 4>::iterator succ_iterator;
 108     typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
 109     typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
 110
 111     unsigned NodeNum;                   // Entry # of node in the node vector.
 112     unsigned NodeQueueId;               // Queue id of node.
 113     unsigned short Latency;             // Node latency.
 114     short NumPreds;                     // # of non-control preds.
 115     short NumSuccs;                     // # of non-control sucss.
 116     short NumPredsLeft;                 // # of preds not scheduled.
 117     short NumSuccsLeft;                 // # of succs not scheduled.
 118     bool isTwoAddress     : 1;          // Is a two-address instruction.
 119     bool isCommutable     : 1;          // Is a commutable instruction.
 120     bool hasPhysRegDefs   : 1;          // Has physreg defs that are being used.
 121     bool isPending        : 1;          // True once pending.
 122     bool isAvailable      : 1;          // True once available.
 123     bool isScheduled      : 1;          // True once scheduled.
 124     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
 125     unsigned Cycle;                     // Once scheduled, the cycle of the op.
 126     unsigned Depth;                     // Node depth;
 127     unsigned Height;                    // Node height;
 128     const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
 129     const TargetRegisterClass *CopySrcRC;
 130
 131     /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
 132     /// an SDNode and any nodes flagged to it.
 133     SUnit(SDNode *node, unsigned nodenum)
 134       : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
 135         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
 136         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
 137         isPending(false), isAvailable(false), isScheduled(false),
 138         CycleBound(0), Cycle(0), Depth(0), Height(0),
 139         CopyDstRC(NULL), CopySrcRC(NULL) {}
 140
 141     /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
 142     /// a MachineInstr.
 143     SUnit(MachineInstr *instr, unsigned nodenum)
 144       : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
 145         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
 146         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
 147         isPending(false), isAvailable(false), isScheduled(false),
 148         CycleBound(0), Cycle(0), Depth(0), Height(0),
 149         CopyDstRC(NULL), CopySrcRC(NULL) {}
 150
 151     /// setNode - Assign the representative SDNode for this SUnit.
 152     /// This may be used during pre-regalloc scheduling.
 153     void setNode(SDNode *N) {
 154       assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
 155       Node = N;
 156     }
 157
 158     /// getNode - Return the representative SDNode for this SUnit.
 159     /// This may be used during pre-regalloc scheduling.
 160     SDNode *getNode() const {
 161       assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
 162       return Node;
 163     }
 164
 165     /// setInstr - Assign the instruction for the SUnit.
 166     /// This may be used during post-regalloc scheduling.
 167     void setInstr(MachineInstr *MI) {
 168       assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
 169       Instr = MI;
 170     }
 171
 172     /// getInstr - Return the representative MachineInstr for this SUnit.
 173     /// This may be used during post-regalloc scheduling.
 174     MachineInstr *getInstr() const {
 175       assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
 176       return Instr;
 177     }
 178
 179     /// addPred - This adds the specified node as a pred of the current node if
 180     /// not already.  This returns true if this is a new pred.
 181     bool addPred(SUnit *N, bool isCtrl, bool isSpecial,
 182                  unsigned PhyReg = 0, int Cost = 1) {
 183       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
 184         if (Preds[i].Dep == N &&
 185             Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial)
 186           return false;
 187       Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial));
 188       N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial));
 189       if (!isCtrl) {
 190         ++NumPreds;
 191         ++N->NumSuccs;
 192       }
 193       if (!N->isScheduled)
 194         ++NumPredsLeft;
 195       if (!isScheduled)
 196         ++N->NumSuccsLeft;
 197       return true;
 198     }
 199
 200     bool removePred(SUnit *N, bool isCtrl, bool isSpecial) {
 201       for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
 202            I != E; ++I)
 203         if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) {
 204           bool FoundSucc = false;
 205           for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
 206                  EE = N->Succs.end(); II != EE; ++II)
 207             if (II->Dep == this &&
 208                 II->isCtrl == isCtrl && II->isSpecial == isSpecial) {
 209               FoundSucc = true;
 210               N->Succs.erase(II);
 211               break;
 212             }
 213           assert(FoundSucc && "Mismatching preds / succs lists!");
 214           Preds.erase(I);
 215           if (!isCtrl) {
 216             --NumPreds;
 217             --N->NumSuccs;
 218           }
 219           if (!N->isScheduled)
 220             --NumPredsLeft;
 221           if (!isScheduled)
 222             --N->NumSuccsLeft;
 223           return true;
 224         }
 225       return false;
 226     }
 227
 228     bool isPred(SUnit *N) {
 229       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
 230         if (Preds[i].Dep == N)
 231           return true;
 232       return false;
 233     }
 234
 235     bool isSucc(SUnit *N) {
 236       for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
 237         if (Succs[i].Dep == N)
 238           return true;
 239       return false;
 240     }
 241
 242     void dump(const SelectionDAG *G) const;
 243     void dumpAll(const SelectionDAG *G) const;
 244   };
 245
 246   //===--------------------------------------------------------------------===//
 247   /// SchedulingPriorityQueue - This interface is used to plug different
 248   /// priorities computation algorithms into the list scheduler. It implements
 249   /// the interface of a standard priority queue, where nodes are inserted in
 250   /// arbitrary order and returned in priority order.  The computation of the
 251   /// priority and the representation of the queue are totally up to the
 252   /// implementation to decide.
 253   ///
 254   class SchedulingPriorityQueue {
 255   public:
 256     virtual ~SchedulingPriorityQueue() {}
 257
 258     virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
 259     virtual void addNode(const SUnit *SU) = 0;
 260     virtual void updateNode(const SUnit *SU) = 0;
 261     virtual void releaseState() = 0;
 262
 263     virtual unsigned size() const = 0;
 264     virtual bool empty() const = 0;
 265     virtual void push(SUnit *U) = 0;
 266
 267     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
 268     virtual SUnit *pop() = 0;
 269
 270     virtual void remove(SUnit *SU) = 0;
 271
 272     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
 273     /// allows the priority function to adjust the priority of related
 274     /// unscheduled nodes, for example.
 275     ///
 276     virtual void ScheduledNode(SUnit *) {}
 277
 278     virtual void UnscheduledNode(SUnit *) {}
 279   };
 280
 281   class ScheduleDAG {
 282   public:
 283     SelectionDAG *DAG;                    // DAG of the current basic block
 284     MachineBasicBlock *BB;                // Current basic block
 285     const TargetMachine &TM;              // Target processor
 286     const TargetInstrInfo *TII;           // Target instruction information
 287     const TargetRegisterInfo *TRI;        // Target processor register info
 288     TargetLowering *TLI;                  // Target lowering info
 289     MachineFunction *MF;                  // Machine function
 290     MachineRegisterInfo &MRI;             // Virtual/real register map
 291     MachineConstantPool *ConstPool;       // Target constant pool
 292     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
 293                                           // represent noop instructions.
 294     std::vector<SUnit> SUnits;            // The scheduling units.
 295     SmallSet<SDNode*, 16> CommuteSet;     // Nodes that should be commuted.
 296
 297     ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
 298                 const TargetMachine &tm);
 299
 300     virtual ~ScheduleDAG() {}
 301
 302     /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
 303     /// using 'dot'.
 304     ///
 305     void viewGraph();
 306
 307     /// Run - perform scheduling.
 308     ///
 309     void Run();
 310
 311     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 312     ///
 313     static bool isPassiveNode(SDNode *Node) {
 314       if (isa<ConstantSDNode>(Node))       return true;
 315       if (isa<ConstantFPSDNode>(Node))     return true;
 316       if (isa<RegisterSDNode>(Node))       return true;
 317       if (isa<GlobalAddressSDNode>(Node))  return true;
 318       if (isa<BasicBlockSDNode>(Node))     return true;
 319       if (isa<FrameIndexSDNode>(Node))     return true;
 320       if (isa<ConstantPoolSDNode>(Node))   return true;
 321       if (isa<JumpTableSDNode>(Node))      return true;
 322       if (isa<ExternalSymbolSDNode>(Node)) return true;
 323       if (isa<MemOperandSDNode>(Node))     return true;
 324       if (Node->getOpcode() == ISD::EntryToken) return true;
 325       return false;
 326     }
 327
 328     /// NewSUnit - Creates a new SUnit and return a ptr to it.
 329     ///
 330     SUnit *NewSUnit(SDNode *N) {
 331       SUnits.push_back(SUnit(N, (unsigned)SUnits.size()));
 332       SUnits.back().OrigNode = &SUnits.back();
 333       return &SUnits.back();
 334     }
 335
 336     /// NewSUnit - Creates a new SUnit and return a ptr to it.
 337     ///
 338     SUnit *NewSUnit(MachineInstr *MI) {
 339       SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
 340       SUnits.back().OrigNode = &SUnits.back();
 341       return &SUnits.back();
 342     }
 343
 344     /// Clone - Creates a clone of the specified SUnit. It does not copy the
 345     /// predecessors / successors info nor the temporary scheduling states.
 346     SUnit *Clone(SUnit *N);
 347
 348     /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
 349     /// This SUnit graph is similar to the SelectionDAG, but represents flagged
 350     /// together nodes with a single SUnit.
 351     void BuildSchedUnits();
 352
 353     /// ComputeLatency - Compute node latency.
 354     ///
 355     void ComputeLatency(SUnit *SU);
 356
 357     /// CalculateDepths, CalculateHeights - Calculate node depth / height.
 358     ///
 359     void CalculateDepths();
 360     void CalculateHeights();
 361
 362     /// CountResults - The results of target nodes have register or immediate
 363     /// operands first, then an optional chain, and optional flag operands
 364     /// (which do not go into the machine instrs.)
 365     static unsigned CountResults(SDNode *Node);
 366
 367     /// CountOperands - The inputs to target nodes have any actual inputs first,
 368     /// followed by special operands that describe memory references, then an
 369     /// optional chain operand, then flag operands.  Compute the number of
 370     /// actual operands that will go into the resulting MachineInstr.
 371     static unsigned CountOperands(SDNode *Node);
 372
 373     /// ComputeMemOperandsEnd - Find the index one past the last
 374     /// MemOperandSDNode operand
 375     static unsigned ComputeMemOperandsEnd(SDNode *Node);
 376
 377     /// EmitNode - Generate machine code for an node and needed dependencies.
 378     /// VRBaseMap contains, for each already emitted node, the first virtual
 379     /// register number for the results of the node.
 380     ///
 381     void EmitNode(SDNode *Node, bool IsClone,
 382                   DenseMap<SDValue, unsigned> &VRBaseMap);
 383
 384     /// EmitNoop - Emit a noop instruction.
 385     ///
 386     void EmitNoop();
 387
 388     MachineBasicBlock *EmitSchedule();
 389
 390     void dumpSchedule() const;
 391
 392     /// Schedule - Order nodes according to selected style, filling
 393     /// in the Sequence member.
 394     ///
 395     virtual void Schedule() = 0;
 396
 397   private:
 398     /// EmitSubregNode - Generate machine code for subreg nodes.
 399     ///
 400     void EmitSubregNode(SDNode *Node,
 401                         DenseMap<SDValue, unsigned> &VRBaseMap);
 402
 403     /// getVR - Return the virtual register corresponding to the specified result
 404     /// of the specified node.
 405     unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap);
 406
 407     /// getDstOfCopyToRegUse - If the only use of the specified result number of
 408     /// node is a CopyToReg, return its destination register. Return 0 otherwise.
 409     unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const;
 410
 411     void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum,
 412                     const TargetInstrDesc *II,
 413                     DenseMap<SDValue, unsigned> &VRBaseMap);
 414     void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO);
 415
 416     void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
 417
 418     /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
 419     /// implicit physical register output.
 420     void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone,
 421                          unsigned SrcReg,
 422                          DenseMap<SDValue, unsigned> &VRBaseMap);
 423
 424     void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 425                                 const TargetInstrDesc &II,
 426                                 DenseMap<SDValue, unsigned> &VRBaseMap);
 427
 428     /// EmitLiveInCopy - Emit a copy for a live in physical register. If the
 429     /// physical register has only a single copy use, then coalesced the copy
 430     /// if possible.
 431     void EmitLiveInCopy(MachineBasicBlock *MBB,
 432                         MachineBasicBlock::iterator &InsertPos,
 433                         unsigned VirtReg, unsigned PhysReg,
 434                         const TargetRegisterClass *RC,
 435                         DenseMap<MachineInstr*, unsigned> &CopyRegMap);
 436
 437     /// EmitLiveInCopies - If this is the first basic block in the function,
 438     /// and if it has live ins that need to be copied into vregs, emit the
 439     /// copies into the top of the block.
 440     void EmitLiveInCopies(MachineBasicBlock *MBB);
 441
 442     /// BuildSchedUnitsFromMBB - Build SUnits from the MachineBasicBlock.
 443     /// This SUnit graph is similar to the pre-regalloc SUnit graph, but represents
 444     /// MachineInstrs directly instead of SDNodes.
 445     void BuildSchedUnitsFromMBB();
 446   };
 447
 448   /// createBURRListDAGScheduler - This creates a bottom up register usage
 449   /// reduction list scheduler.
 450   ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS,
 451                                           SelectionDAG *DAG,
 452                                           const TargetMachine *TM,
 453                                           MachineBasicBlock *BB,
 454                                           bool Fast);
 455
 456   /// createTDRRListDAGScheduler - This creates a top down register usage
 457   /// reduction list scheduler.
 458   ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS,
 459                                           SelectionDAG *DAG,
 460                                           const TargetMachine *TM,
 461                                           MachineBasicBlock *BB,
 462                                           bool Fast);
 463
 464   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 465   /// a hazard recognizer.
 466   ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS,
 467                                         SelectionDAG *DAG,
 468                                         const TargetMachine *TM,
 469                                         MachineBasicBlock *BB,
 470                                         bool Fast);
 471
 472   /// createFastDAGScheduler - This creates a "fast" scheduler.
 473   ///
 474   ScheduleDAG *createFastDAGScheduler(SelectionDAGISel *IS,
 475                                       SelectionDAG *DAG,
 476                                       const TargetMachine *TM,
 477                                       MachineBasicBlock *BB,
 478                                       bool Fast);
 479
 480   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 481   /// for the target.
 482   ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
 483                                       SelectionDAG *DAG,
 484                                       const TargetMachine *TM,
 485                                       MachineBasicBlock *BB,
 486                                       bool Fast);
 487
 488   class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> {
 489     SUnit *Node;
 490     unsigned Operand;
 491
 492     SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
 493   public:
 494     bool operator==(const SUnitIterator& x) const {
 495       return Operand == x.Operand;
 496     }
 497     bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
 498
 499     const SUnitIterator &operator=(const SUnitIterator &I) {
 500       assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
 501       Operand = I.Operand;
 502       return *this;
 503     }
 504
 505     pointer operator*() const {
 506       return Node->Preds[Operand].Dep;
 507     }
 508     pointer operator->() const { return operator*(); }
 509
 510     SUnitIterator& operator++() {                // Preincrement
 511       ++Operand;
 512       return *this;
 513     }
 514     SUnitIterator operator++(int) { // Postincrement
 515       SUnitIterator tmp = *this; ++*this; return tmp;
 516     }
 517
 518     static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
 519     static SUnitIterator end  (SUnit *N) {
 520       return SUnitIterator(N, (unsigned)N->Preds.size());
 521     }
 522
 523     unsigned getOperand() const { return Operand; }
 524     const SUnit *getNode() const { return Node; }
 525     bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; }
 526     bool isSpecialDep() const { return Node->Preds[Operand].isSpecial; }
 527   };
 528
 529   template <> struct GraphTraits<SUnit*> {
 530     typedef SUnit NodeType;
 531     typedef SUnitIterator ChildIteratorType;
 532     static inline NodeType *getEntryNode(SUnit *N) { return N; }
 533     static inline ChildIteratorType child_begin(NodeType *N) {
 534       return SUnitIterator::begin(N);
 535     }
 536     static inline ChildIteratorType child_end(NodeType *N) {
 537       return SUnitIterator::end(N);
 538     }
 539   };
 540
 541   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
 542     typedef std::vector<SUnit>::iterator nodes_iterator;
 543     static nodes_iterator nodes_begin(ScheduleDAG *G) {
 544       return G->SUnits.begin();
 545     }
 546     static nodes_iterator nodes_end(ScheduleDAG *G) {
 547       return G->SUnits.end();
 548     }
 549   };
 550 }
 551
 552 #endif