Rewrite the SDep class, and simplify some of the related code.

The Cost field is removed. It was only being used in a very limited way,
to indicate when the scheduler should attempt to protect a live register,
and it isn't really needed to do that. If we ever want the scheduler to
start inserting copies in non-prohibitive situations, we'll have to
rethink some things anyway.

A Latency field is added. Instead of giving each node a single
fixed latency, each edge can have its own latency. This will eventually
be used to model various micro-architecture properties more accurately.

The PointerIntPair class and an internal union are now used, which
reduce the overall size.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60806 91177308-0d34-0410-b5e6-96231b3b80d8

12 files changed, 526 insertions, 376 deletions

diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index a89bfa1490..4d3b60e59a 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -20,6 +20,7 @@
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/PointerIntPair.h"
 
 namespace llvm {
   struct SUnit;
@@ -39,20 +40,174 @@ namespace llvm {
   class TargetRegisterClass;
   template<class Graph> class GraphWriter;
 
-  /// SDep - Scheduling dependency. It keeps track of dependent nodes,
-  /// cost of the depdenency, etc.
-  struct SDep {
-    SUnit    *Dep;           // Dependent - either a predecessor or a successor.
-    unsigned  Reg;           // If non-zero, this dep is a physreg dependency.
-    int       Cost;          // Cost of the dependency.
-    bool      isCtrl    : 1; // True iff it's a control dependency.
-    bool      isArtificial : 1; // True iff it's an artificial ctrl dep added
-                                // during sched that may be safely deleted if
-                                // necessary.
-    bool      isAntiDep : 1; // True iff it's an anti-dependency (on a physical
-                             // register.
-    SDep(SUnit *d, unsigned r, int t, bool c, bool a, bool anti)
-      : Dep(d), Reg(r), Cost(t), isCtrl(c), isArtificial(a), isAntiDep(anti) {}
+  /// SDep - Scheduling dependency. This represents one direction of an
+  /// edge in the scheduling DAG.
+  class SDep {
+  public:
+    /// Kind - These are the different kinds of scheduling dependencies.
+    enum Kind {
+      Data,        ///< Regular data dependence (aka true-dependence).
+      Anti,        ///< A register anti-dependedence (aka WAR).
+      Output,      ///< A register output-dependence (aka WAW).
+      Order        ///< Any other ordering dependency.
+    };
+
+  private:
+    /// Dep - A pointer to the depending/depended-on SUnit, and an enum
+    /// indicating the kind of the dependency.
+    PointerIntPair<SUnit *, 2, Kind> Dep;
+
+    /// Contents - A union discriminated by the dependence kind.
+    union {
+      /// Reg - For Data, Anti, and Output dependencies, the associated
+      /// register. For Data dependencies that don't currently have a register
+      /// assigned, this is set to zero.
+      unsigned Reg;
+
+      /// Order - Additional information about Order dependencies.
+      struct {
+        /// isNormalMemory - True if both sides of the dependence
+        /// access memory in non-volatile and fully modeled ways.
+        bool isNormalMemory : 1;
+
+        /// isMustAlias - True if both sides of the dependence are known to
+        /// access the same memory.
+        bool isMustAlias : 1;
+
+        /// isArtificial - True if this is an artificial dependency, meaning
+        /// it is not necessary for program correctness, and may be safely
+        /// deleted if necessary.
+        bool isArtificial : 1;
+      } Order;
+    } Contents;
+
+    /// Latency - The time associated with this edge. Often this is just
+    /// the value of the Latency field of the predecessor, however advanced
+    /// models may provide additional information about specific edges.
+    unsigned Latency;
+
+  public:
+    /// SDep - Construct a null SDep. This is only for use by container
+    /// classes which require default constructors. SUnits may not
+    /// have null SDep edges.
+    SDep() : Dep(0, Data) {}
+
+    /// SDep - Construct an SDep with the specified values.
+    SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0,
+         bool isNormalMemory = false, bool isMustAlias = false,
+         bool isArtificial = false)
+      : Dep(S, kind), Contents(), Latency(latency) {
+      switch (kind) {
+      case Anti:
+      case Output:
+        assert(Reg != 0 &&
+               "SDep::Anti and SDep::Output must use a non-zero Reg!");
+        // fall through
+      case Data:
+        assert(!isMustAlias && "isMustAlias only applies with SDep::Order!");
+        assert(!isArtificial && "isArtificial only applies with SDep::Order!");
+        Contents.Reg = Reg;
+        break;
+      case Order:
+        assert(Reg == 0 && "Reg given for non-register dependence!");
+        Contents.Order.isNormalMemory = isNormalMemory;
+        Contents.Order.isMustAlias = isMustAlias;
+        Contents.Order.isArtificial = isArtificial;
+        break;
+      }
+    }
+
+    bool operator==(const SDep &Other) const {
+      if (Dep != Other.Dep) return false;
+      switch (Dep.getInt()) {
+      case Data:
+      case Anti:
+      case Output:
+        return Contents.Reg == Other.Contents.Reg;
+      case Order:
+        return Contents.Order.isNormalMemory ==
+                 Other.Contents.Order.isNormalMemory &&
+               Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias &&
+               Contents.Order.isArtificial == Other.Contents.Order.isArtificial;
+      }
+      assert(0 && "Invalid dependency kind!");
+      return false;
+    }
+
+    bool operator!=(const SDep &Other) const {
+      return !operator==(Other);
+    }
+
+    /// getLatency - Return the latency value for this edge, which roughly
+    /// means the minimum number of cycles that must elapse between the
+    /// predecessor and the successor, given that they have this edge
+    /// between them.
+    unsigned getLatency() const {
+      return Latency;
+    }
+
+    //// getSUnit - Return the SUnit to which this edge points.
+    SUnit *getSUnit() const {
+      return Dep.getPointer();
+    }
+
+    //// setSUnit - Assign the SUnit to which this edge points.
+    void setSUnit(SUnit *SU) {
+      Dep.setPointer(SU);
+    }
+
+    /// getKind - Return an enum value representing the kind of the dependence.
+    Kind getKind() const {
+      return Dep.getInt();
+    }
+
+    /// isCtrl - Shorthand for getKind() != SDep::Data.
+    bool isCtrl() const {
+      return getKind() != Data;
+    }
+
+    /// isArtificial - Test if this is an Order dependence that is marked
+    /// as "artificial", meaning it isn't necessary for correctness.
+    bool isArtificial() const {
+      return getKind() == Order && Contents.Order.isArtificial;
+    }
+
+    /// isMustAlias - Test if this is an Order dependence that is marked
+    /// as "must alias", meaning that the SUnits at either end of the edge
+    /// have a memory dependence on a known memory location.
+    bool isMustAlias() const {
+      return getKind() == Order && Contents.Order.isMustAlias;
+    }
+
+    /// isAssignedRegDep - Test if this is a Data dependence that is
+    /// associated with a register.
+    bool isAssignedRegDep() const {
+      return getKind() == Data && Contents.Reg != 0;
+    }
+
+    /// getReg - Return the register associated with this edge. This is
+    /// only valid on Data, Anti, and Output edges. On Data edges, this
+    /// value may be zero, meaning there is no associated register.
+    unsigned getReg() const {
+      assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
+             "getReg called on non-register dependence edge!");
+      return Contents.Reg;
+    }
+
+    /// setReg - Assign the associated register for this edge. This is
+    /// only valid on Data, Anti, and Output edges. On Anti and Output
+    /// edges, this value must not be zero. On Data edges, the value may
+    /// be zero, which would mean that no specific register is associated
+    /// with this edge.
+    void setReg(unsigned Reg) {
+      assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
+             "setReg called on non-register dependence edge!");
+      assert((getKind() != Anti || Reg != 0) &&
+             "SDep::Anti edge cannot use the zero register!");
+      assert((getKind() != Output || Reg != 0) &&
+             "SDep::Output edge cannot use the zero register!");
+      Contents.Reg = Reg;
+    }
   };
 
   /// SUnit - Scheduling unit. This is a node in the scheduling DAG.
@@ -77,8 +232,8 @@ namespace llvm {
     unsigned NodeNum;                   // Entry # of node in the node vector.
     unsigned NodeQueueId;               // Queue id of node.
     unsigned short Latency;             // Node latency.
-    short NumPreds;                     // # of non-control preds.
-    short NumSuccs;                     // # of non-control sucss.
+    short NumPreds;                     // # of SDep::Data preds.
+    short NumSuccs;                     // # of SDep::Data sucss.
     short NumPredsLeft;                 // # of preds not scheduled.
     short NumSuccsLeft;                 // # of succs not scheduled.
     bool isTwoAddress     : 1;          // Is a two-address instruction.
@@ -142,21 +297,23 @@ namespace llvm {
       return Instr;
     }
 
-    /// addPred - This adds the specified node as a pred of the current node if
+    /// addPred - This adds the specified edge as a pred of the current node if
     /// not already.  It also adds the current node as a successor of the
     /// specified node.  This returns true if this is a new pred.
-    bool addPred(SUnit *N, bool isCtrl, bool isArtificial,
-                 unsigned PhyReg = 0, int Cost = 1, bool isAntiDep = false) {
+    bool addPred(const SDep &D) {
+      // If this node already has this depenence, don't add a redundant one.
       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
-        if (Preds[i].Dep == N &&
-            Preds[i].isCtrl == isCtrl &&
-            Preds[i].isArtificial == isArtificial &&
-            Preds[i].isAntiDep == isAntiDep)
+        if (Preds[i] == D)
           return false;
-      Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isArtificial, isAntiDep));
-      N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl,
-                              isArtificial, isAntiDep));
-      if (!isCtrl) {
+      // Add a pred to this SUnit.
+      Preds.push_back(D);
+      // Now add a corresponding succ to N.
+      SDep P = D;
+      P.setSUnit(this);
+      SUnit *N = D.getSUnit();
+      N->Succs.push_back(P);
+      // Update the bookkeeping.
+      if (D.getKind() == SDep::Data) {
         ++NumPreds;
         ++N->NumSuccs;
       }
@@ -167,26 +324,31 @@ namespace llvm {
       return true;
     }
 
-    bool removePred(SUnit *N, bool isCtrl, bool isArtificial, bool isAntiDep) {
+    /// removePred - This removes the specified edge as a pred of the current
+    /// node if it exists.  It also removes the current node as a successor of
+    /// the specified node.  This returns true if the edge existed and was
+    /// removed.
+    bool removePred(const SDep &D) {
+      // Find the matching predecessor.
       for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
            I != E; ++I)
-        if (I->Dep == N &&
-            I->isCtrl == isCtrl &&
-            I->isArtificial == isArtificial &&
-            I->isAntiDep == isAntiDep) {
+        if (*I == D) {
           bool FoundSucc = false;
+          // Find the corresponding successor in N.
+          SDep P = D;
+          P.setSUnit(this);
+          SUnit *N = D.getSUnit();
           for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
                  EE = N->Succs.end(); II != EE; ++II)
-            if (II->Dep == this &&
-                II->isCtrl == isCtrl && II->isArtificial == isArtificial &&
-                II->isAntiDep == isAntiDep) {
+            if (*II == P) {
               FoundSucc = true;
               N->Succs.erase(II);
               break;
             }
           assert(FoundSucc && "Mismatching preds / succs lists!");
           Preds.erase(I);
-          if (!isCtrl) {
+          // Update the bookkeeping;
+          if (D.getKind() == SDep::Data) {
             --NumPreds;
             --N->NumSuccs;
           }
@@ -201,14 +363,14 @@ namespace llvm {
 
     bool isPred(SUnit *N) {
       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
-        if (Preds[i].Dep == N)
+        if (Preds[i].getSUnit() == N)
           return true;
       return false;
     }
     
     bool isSucc(SUnit *N) {
       for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
-        if (Succs[i].Dep == N)
+        if (Succs[i].getSUnit() == N)
           return true;
       return false;
     }
@@ -366,7 +528,7 @@ namespace llvm {
     }
 
     pointer operator*() const {
-      return Node->Preds[Operand].Dep;
+      return Node->Preds[Operand].getSUnit();
     }
     pointer operator->() const { return operator*(); }
 
@@ -385,8 +547,13 @@ namespace llvm {
 
     unsigned getOperand() const { return Operand; }
     const SUnit *getNode() const { return Node; }
-    bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; }
-    bool isArtificialDep() const { return Node->Preds[Operand].isArtificial; }
+    /// isCtrlDep - Test if this is not an SDep::Data dependence.
+    bool isCtrlDep() const {
+      return Node->Preds[Operand].isCtrl();
+    }
+    bool isArtificialDep() const {
+      return Node->Preds[Operand].isArtificial();
+    }
   };
 
   template <> struct GraphTraits<SUnit*> {
diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h
index cc2cb0f392..2b6c1d3a55 100644
--- a/include/llvm/CodeGen/ScheduleDAGInstrs.h
+++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h
@@ -18,22 +18,6 @@
 #include "llvm/CodeGen/ScheduleDAG.h"
 
 namespace llvm {
-  struct SUnit;
-  class MachineConstantPool;
-  class MachineFunction;
-  class MachineModuleInfo;
-  class MachineRegisterInfo;
-  class MachineInstr;
-  class TargetRegisterInfo;
-  class ScheduleDAG;
-  class SelectionDAG;
-  class SelectionDAGISel;
-  class TargetInstrInfo;
-  class TargetInstrDesc;
-  class TargetLowering;
-  class TargetMachine;
-  class TargetRegisterClass;
-
   class ScheduleDAGInstrs : public ScheduleDAG {
   public:
     ScheduleDAGInstrs(MachineBasicBlock *bb,
diff --git a/include/llvm/CodeGen/ScheduleDAGSDNodes.h b/include/llvm/CodeGen/ScheduleDAGSDNodes.h
index e795649153..fa78faaecd 100644
--- a/include/llvm/CodeGen/ScheduleDAGSDNodes.h
+++ b/include/llvm/CodeGen/ScheduleDAGSDNodes.h
@@ -20,22 +20,6 @@
 #include "llvm/ADT/SmallSet.h"
 
 namespace llvm {
-  struct SUnit;
-  class MachineConstantPool;
-  class MachineFunction;
-  class MachineModuleInfo;
-  class MachineRegisterInfo;
-  class MachineInstr;
-  class TargetRegisterInfo;
-  class ScheduleDAG;
-  class SelectionDAG;
-  class SelectionDAGISel;
-  class TargetInstrInfo;
-  class TargetInstrDesc;
-  class TargetLowering;
-  class TargetMachine;
-  class TargetRegisterClass;
-
   /// HazardRecognizer - This determines whether or not an instruction can be
   /// issued this cycle, and whether or not a noop needs to be inserted to handle
   /// the hazard.
diff --git a/lib/CodeGen/LatencyPriorityQueue.cpp b/lib/CodeGen/LatencyPriorityQueue.cpp
index 8a6d1f23af..131da27c33 100644
--- a/lib/CodeGen/LatencyPriorityQueue.cpp
+++ b/lib/CodeGen/LatencyPriorityQueue.cpp
@@ -57,14 +57,13 @@ int LatencyPriorityQueue::CalcLatency(const SUnit &SU) {
     unsigned MaxSuccLatency = 0;
     for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end();
          I != E; ++I) {
-      int SuccLatency = Latencies[I->Dep->NodeNum];
+      int SuccLatency = Latencies[I->getSUnit()->NodeNum];
       if (SuccLatency == -1) {
         AllDone = false;
-        WorkList.push_back(I->Dep);
+        WorkList.push_back(I->getSUnit());
       } else {
         // This assumes that there's no delay for reusing registers.
-        unsigned NewLatency =
-          SuccLatency + ((I->isCtrl && I->Reg != 0) ? 1 : CurLatency);
+        unsigned NewLatency = SuccLatency + CurLatency;
         MaxSuccLatency = std::max(MaxSuccLatency, NewLatency);
       }
     }
@@ -99,7 +98,7 @@ void LatencyPriorityQueue::CalculatePriorities() {
       Latency = SU->Latency + SuccLat;
       for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
            I != E; ++I)
-        WorkList.push_back(std::make_pair(I->Dep, Latency));
+        WorkList.push_back(std::make_pair(I->getSUnit(), Latency));
     }
   }
 }
@@ -110,7 +109,7 @@ SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
   SUnit *OnlyAvailablePred = 0;
   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    SUnit &Pred = *I->Dep;
+    SUnit &Pred = *I->getSUnit();
     if (!Pred.isScheduled) {
       // We found an available, but not scheduled, predecessor.  If it's the
       // only one we have found, keep track of it... otherwise give up.
@@ -129,7 +128,7 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) {
   unsigned NumNodesBlocking = 0;
   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I)
-    if (getSingleUnscheduledPred(I->Dep) == SU)
+    if (getSingleUnscheduledPred(I->getSUnit()) == SU)
       ++NumNodesBlocking;
   NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
   
@@ -144,7 +143,7 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) {
 void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I)
-    AdjustPriorityOfUnscheduledPreds(I->Dep);
+    AdjustPriorityOfUnscheduledPreds(I->getSUnit());
 }
 
 /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp
index 5ee6ed0852..2f7c0118a0 100644
--- a/lib/CodeGen/PostRASchedulerList.cpp
+++ b/lib/CodeGen/PostRASchedulerList.cpp
@@ -78,7 +78,7 @@ namespace {
     void Schedule();
 
   private:
-    void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
+    void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
     void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
     void ListScheduleTopDown();
     bool BreakAntiDependencies();
@@ -160,12 +160,13 @@ bool SchedulePostRATDList::BreakAntiDependencies() {
     SUnit *SU = &SUnits[*I];
     for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
          P != PE; ++P) {
-      SUnit *PredSU = P->Dep;
+      SUnit *PredSU = P->getSUnit();
       // This assumes that there's no delay for reusing registers.
-      unsigned PredLatency = (P->isCtrl && P->Reg != 0) ? 1 : PredSU->Latency;
+      unsigned PredLatency = P->getLatency();
       unsigned PredTotalLatency = PredSU->CycleBound + PredLatency;
       if (SU->CycleBound < PredTotalLatency ||
-          (SU->CycleBound == PredTotalLatency && !P->isAntiDep)) {
+          (SU->CycleBound == PredTotalLatency &&
+           P->getKind() == SDep::Anti)) {
         SU->CycleBound = PredTotalLatency;
         CriticalPath[*I] = &*P;
       }
@@ -195,13 +196,13 @@ bool SchedulePostRATDList::BreakAntiDependencies() {
   BitVector AllocatableSet = TRI->getAllocatableSet(*MF);
   DenseMap<MachineInstr *, unsigned> CriticalAntiDeps;
   for (SUnit *SU = Max; CriticalPath[SU->NodeNum];
-       SU = CriticalPath[SU->NodeNum]->Dep) {
+       SU = CriticalPath[SU->NodeNum]->getSUnit()) {
     SDep *Edge = CriticalPath[SU->NodeNum];
-    SUnit *NextSU = Edge->Dep;
-    unsigned AntiDepReg = Edge->Reg;
+    SUnit *NextSU = Edge->getSUnit();
     // Only consider anti-dependence edges.
-    if (!Edge->isAntiDep)
+    if (Edge->getKind() != SDep::Anti)
       continue;
+    unsigned AntiDepReg = Edge->getReg();
     assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
     // Don't break anti-dependencies on non-allocatable registers.
     if (!AllocatableSet.test(AntiDepReg))
@@ -213,9 +214,9 @@ bool SchedulePostRATDList::BreakAntiDependencies() {
     // break it.
     for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
          P != PE; ++P)
-      if (P->Dep == NextSU ?
-            (!P->isAntiDep || P->Reg != AntiDepReg) :
-            (!P->isCtrl && !P->isAntiDep && P->Reg == AntiDepReg)) {
+      if (P->getSUnit() == NextSU ?
+            (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
+            (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
         AntiDepReg = 0;
         break;
       }
@@ -539,7 +540,8 @@ bool SchedulePostRATDList::BreakAntiDependencies() {
 
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
-void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
+  SUnit *SuccSU = SuccEdge->getSUnit();
   --SuccSU->NumPredsLeft;
   
 #ifndef NDEBUG
@@ -554,14 +556,7 @@ void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
   // Compute how many cycles it will be before this actually becomes
   // available.  This is the max of the start time of all predecessors plus
   // their latencies.
-  // If this is a token edge, we don't need to wait for the latency of the
-  // preceeding instruction (e.g. a long-latency load) unless there is also
-  // some other data dependence.
-  unsigned PredDoneCycle = SU->Cycle;
-  if (!isChain)
-    PredDoneCycle += SU->Latency;
-  else if (SU->Latency)
-    PredDoneCycle += 1;
+  unsigned PredDoneCycle = SU->Cycle + SuccEdge->getLatency();
   SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
   
   if (SuccSU->NumPredsLeft == 0) {
@@ -582,7 +577,7 @@ void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
   // Top down: release successors.
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I)
-    ReleaseSucc(SU, I->Dep, I->isCtrl);
+    ReleaseSucc(SU, &*I);
 
   SU->isScheduled = true;
   AvailableQueue.ScheduledNode(SU);
@@ -616,7 +611,7 @@ void SchedulePostRATDList::ListScheduleTopDown() {
         PendingQueue.pop_back();
         --i; --e;
       } else {
-        assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?");
+        assert(PendingQueue[i]->CycleBound > CurCycle && "Non-positive latency?");
       }
     }
     
diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp
index 42d0fca76e..809fc8d068 100644
--- a/lib/CodeGen/ScheduleDAG.cpp
+++ b/lib/CodeGen/ScheduleDAG.cpp
@@ -67,7 +67,7 @@ void ScheduleDAG::CalculateDepths() {
     // So, just iterate over all predecessors and take the longest path
     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      unsigned PredDepth = I->Dep->Depth;
+      unsigned PredDepth = I->getSUnit()->Depth;
       if (PredDepth+1 > SUDepth) {
         SUDepth = PredDepth + 1;
       }
@@ -78,7 +78,7 @@ void ScheduleDAG::CalculateDepths() {
     // Update degrees of all nodes depending on current SUnit
     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
          I != E; ++I) {
-      SUnit *SU = I->Dep;
+      SUnit *SU = I->getSUnit();
       if (!--SU->Depth)
         // If all dependencies of the node are processed already,
         // then the longest path for the node can be computed now
@@ -122,7 +122,7 @@ void ScheduleDAG::CalculateHeights() {
     // So, just iterate over all successors and take the longest path
     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
          I != E; ++I) {
-      unsigned SuccHeight = I->Dep->Height;
+      unsigned SuccHeight = I->getSUnit()->Height;
       if (SuccHeight+1 > SUHeight) {
         SUHeight = SuccHeight + 1;
       }
@@ -133,7 +133,7 @@ void ScheduleDAG::CalculateHeights() {
     // Update degrees of all nodes depending on current SUnit
     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      SUnit *SU = I->Dep;
+      SUnit *SU = I->getSUnit();
       if (!--SU->Height)
         // If all dependencies of the node are processed already,
         // then the longest path for the node can be computed now
@@ -183,12 +183,16 @@ void SUnit::dumpAll(const ScheduleDAG *G) const {
     cerr << "  Predecessors:\n";
     for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
          I != E; ++I) {
-      if (I->isCtrl)
-        cerr << "   ch  #";
-      else
-        cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
-      if (I->isArtificial)
+      cerr << "   ";
+      switch (I->getKind()) {
+      case SDep::Data:        cerr << "val "; break;
+      case SDep::Anti:        cerr << "anti"; break;
+      case SDep::Output:      cerr << "out "; break;
+      case SDep::Order:       cerr << "ch  "; break;
+      }
+      cerr << "#";
+      cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")";
+      if (I->isArtificial())
         cerr << " *";
       cerr << "\n";
     }
@@ -197,12 +201,16 @@ void SUnit::dumpAll(const ScheduleDAG *G) const {
     cerr << "  Successors:\n";
     for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
          I != E; ++I) {
-      if (I->isCtrl)
-        cerr << "   ch  #";
-      else
-        cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
-      if (I->isArtificial)
+      cerr << "   ";
+      switch (I->getKind()) {
+      case SDep::Data:        cerr << "val "; break;
+      case SDep::Anti:        cerr << "anti"; break;
+      case SDep::Output:      cerr << "out "; break;
+      case SDep::Order:       cerr << "ch  "; break;
+      }
+      cerr << "#";
+      cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")";
+      if (I->isArtificial())
         cerr << " *";
       cerr << "\n";
     }
@@ -324,7 +332,7 @@ void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
     Allocate(SU->NodeNum, --Id);
     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      SUnit *SU = I->Dep;
+      SUnit *SU = I->getSUnit();
       if (!--Node2Index[SU->NodeNum])
         // If all dependencies of the node are processed already,
         // then the node can be computed now.
@@ -340,7 +348,7 @@ void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
     SUnit *SU = &SUnits[i];
     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      assert(Node2Index[SU->NodeNum] > Node2Index[I->Dep->NodeNum] && 
+      assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 
       "Wrong topological sorting");
     }
   }
@@ -386,14 +394,14 @@ void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
     WorkList.pop_back();
     Visited.set(SU->NodeNum);
     for (int I = SU->Succs.size()-1; I >= 0; --I) {
-      int s = SU->Succs[I].Dep->NodeNum;
+      int s = SU->Succs[I].getSUnit()->NodeNum;
       if (Node2Index[s] == UpperBound) {
         HasLoop = true; 
         return;
       }
       // Visit successors if not already and in affected region.
       if (!Visited.test(s) && Node2Index[s] < UpperBound) {
-        WorkList.push_back(SU->Succs[I].Dep);
+        WorkList.push_back(SU->Succs[I].getSUnit());
       } 
     } 
   }
@@ -434,7 +442,8 @@ bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
     return true;
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I)
-    if (I->Cost < 0 && IsReachable(TargetSU, I->Dep))
+    if (I->isAssignedRegDep() &&
+        IsReachable(TargetSU, I->getSUnit()))
       return true;
   return false;
 }
diff --git a/lib/CodeGen/ScheduleDAGEmit.cpp b/lib/CodeGen/ScheduleDAGEmit.cpp
index ce3283dc3d..d10d670d34 100644
--- a/lib/CodeGen/ScheduleDAGEmit.cpp
+++ b/lib/CodeGen/ScheduleDAGEmit.cpp
@@ -40,31 +40,31 @@ void ScheduleDAG::EmitCrossRCCopy(SUnit *SU,
                                   DenseMap<SUnit*, unsigned> &VRBaseMap) {
   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    if (I->isCtrl) continue;  // ignore chain preds
-    if (I->Dep->CopyDstRC) {
+    if (I->isCtrl()) continue;  // ignore chain preds
+    if (I->getSUnit()->CopyDstRC) {
       // Copy to physical register.
-      DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->Dep);
+      DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit());
       assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
       // Find the destination physical register.
       unsigned Reg = 0;
       for (SUnit::const_succ_iterator II = SU->Succs.begin(),
              EE = SU->Succs.end(); II != EE; ++II) {
-        if (I->Reg) {
-          Reg = I->Reg;
+        if (I->getReg()) {
+          Reg = I->getReg();
           break;
         }
       }
-      assert(I->Reg && "Unknown physical register!");
+      assert(I->getReg() && "Unknown physical register!");
       TII->copyRegToReg(*BB, BB->end(), Reg, VRI->second,
                         SU->CopyDstRC, SU->CopySrcRC);
     } else {
       // Copy from physical register.
-      assert(I->Reg && "Unknown physical register!");
+      assert(I->getReg() && "Unknown physical register!");
       unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
       bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
       isNew = isNew; // Silence compiler warning.
       assert(isNew && "Node emitted out of order - early");
-      TII->copyRegToReg(*BB, BB->end(), VRBase, I->Reg,
+      TII->copyRegToReg(*BB, BB->end(), VRBase, I->getReg(),
                         SU->CopyDstRC, SU->CopySrcRC);
     }
     break;
diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
index fba8192c01..30e1846ef8 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -30,7 +30,6 @@ ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
 void ScheduleDAGInstrs::BuildSchedUnits() {
   SUnits.clear();
   SUnits.reserve(BB->size());
-  int Cost = 1; // FIXME
 
   // We build scheduling units by walking a block's instruction list from bottom
   // to top.
@@ -63,6 +62,9 @@ void ScheduleDAGInstrs::BuildSchedUnits() {
     MachineInstr *MI = prior(MII);
     SUnit *SU = NewSUnit(MI);
 
+    // Assign the Latency field of SU using target-provided information.
+    ComputeLatency(SU);
+
     // Add register-based dependencies (data, anti, and output).
     for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
       const MachineOperand &MO = MI->getOperand(j);
@@ -74,28 +76,27 @@ void ScheduleDAGInstrs::BuildSchedUnits() {
       std::vector<SUnit *> &UseList = Uses[Reg];
       SUnit *&Def = Defs[Reg];
       // Optionally add output and anti dependencies.
+      // TODO: Using a latency of 1 here assumes there's no cost for
+      //       reusing registers.
+      SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
       if (Def && Def != SU)
-        Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
-                     /*PhyReg=*/Reg, Cost, /*isAntiDep=*/MO.isUse());
+        Def->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/Reg));
       for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
         SUnit *&Def = Defs[*Alias];
         if (Def && Def != SU)
-          Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
-                       /*PhyReg=*/*Alias, Cost, /*isAntiDep=*/MO.isUse());
+          Def->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/ *Alias));
       }
 
       if (MO.isDef()) {
         // Add any data dependencies.
         for (unsigned i = 0, e = UseList.size(); i != e; ++i)
           if (UseList[i] != SU)
-            UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
-                                /*PhysReg=*/Reg, Cost);
+            UseList[i]->addPred(SDep(SU, SDep::Data, SU->Latency, Reg));
         for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
           std::vector<SUnit *> &UseList = Uses[*Alias];
           for (unsigned i = 0, e = UseList.size(); i != e; ++i)
             if (UseList[i] != SU)
-              UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
-                                  /*PhysReg=*/*Alias, Cost);
+              UseList[i]->addPred(SDep(SU, SDep::Data, SU->Latency, *Alias));
         }
 
         UseList.clear();
@@ -117,20 +118,20 @@ void ScheduleDAGInstrs::BuildSchedUnits() {
       // This is the conservative case. Add dependencies on all memory
       // references.
       if (Chain)
-        Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+        Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
       Chain = SU;
       for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
-        PendingLoads[k]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+        PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
       PendingLoads.clear();
       for (std::map<const Value *, SUnit *>