diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index a89bfa1..4d3b60e 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 @@
   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 @@
     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 @@
       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 @@
       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 @@
 
     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 @@
     }
 
     pointer operator*() const {
-      return Node->Preds[Operand].Dep;
+      return Node->Preds[Operand].getSUnit();
     }
     pointer operator->() const { return operator*(); }
 
@@ -385,8 +547,13 @@
 
     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 cc2cb0f..2b6c1d3 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 e795649..fa78faa 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 8a6d1f2..131da27 100644
--- a/lib/CodeGen/LatencyPriorityQueue.cpp
+++ b/lib/CodeGen/LatencyPriorityQueue.cpp
@@ -57,14 +57,13 @@
     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 @@
       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 *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 @@
   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::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 5ee6ed0..2f7c011 100644
--- a/lib/CodeGen/PostRASchedulerList.cpp
+++ b/lib/CodeGen/PostRASchedulerList.cpp
@@ -78,7 +78,7 @@
     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 @@
     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 @@
   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 @@
     // 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 @@
 
 /// 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 @@
   // 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 @@
   // 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 @@
         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 42d0fca..809fc8d 100644
--- a/lib/CodeGen/ScheduleDAG.cpp
+++ b/lib/CodeGen/ScheduleDAG.cpp
@@ -67,7 +67,7 @@
     // 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 @@
     // 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 @@
     // 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 @@
     // 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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 @@
     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 ce3283d..d10d670 100644
--- a/lib/CodeGen/ScheduleDAGEmit.cpp
+++ b/lib/CodeGen/ScheduleDAGEmit.cpp
@@ -40,31 +40,31 @@
                                   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 fba8192..30e1846 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -30,7 +30,6 @@
 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 @@
     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 @@
       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 @@
       // 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 *>::iterator I = MemDefs.begin(),
            E = MemDefs.end(); I != E; ++I) {
-        I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+        I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
         I->second = SU;
       }
       for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
            MemUses.begin(), E = MemUses.end(); I != E; ++I) {
         for (unsigned i = 0, e = I->second.size(); i != e; ++i)
-          I->second[i]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+          I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency));
         I->second.clear();
       }
       // See if it is known to just have a single memory reference.
@@ -156,7 +157,8 @@
         // Handle the def in MemDefs, if there is one.
         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
         if (I != MemDefs.end()) {
-          I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+          I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
+                                  /*isNormalMemory=*/true));
           I->second = SU;
         } else {
           MemDefs[V] = SU;
@@ -166,12 +168,13 @@
           MemUses.find(V);
         if (J != MemUses.end()) {
           for (unsigned i = 0, e = J->second.size(); i != e; ++i)
-            J->second[i]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+            J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
+                                       /*isNormalMemory=*/true));
           J->second.clear();
         }
         // Add a general dependence too, if needed.
         if (Chain)
-          Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+          Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
       } else
         // Treat all other stores conservatively.
         goto new_chain;
@@ -186,13 +189,14 @@
         const Value *V = MI->memoperands_begin()->getValue();
         std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
         if (I != MemDefs.end())
-          I->second->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+          I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
+                                  /*isNormalMemory=*/true));
         MemUses[V].push_back(SU);
 
         // Add a general dependence too, if needed.
         if (Chain && (!ChainMMO ||
                       (ChainMMO->isStore() || ChainMMO->isVolatile())))
-          Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+          Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
       } else if (MI->hasVolatileMemoryRef()) {
         // Treat volatile loads conservatively. Note that this includes
         // cases where memoperand information is unavailable.
@@ -200,7 +204,7 @@
       } else {
         // A normal load. Just depend on the general chain.
         if (Chain)
-          Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+          Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
         PendingLoads.push_back(SU);
       }
     }
@@ -208,12 +212,9 @@
     // Add chain edges from the terminator to ensure that all the work of the
     // block is completed before any control transfers.
     if (Terminator && SU->Succs.empty())
-      Terminator->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
+      Terminator->addPred(SDep(SU, SDep::Order, SU->Latency));
     if (TID.isTerminator() || MI->isLabel())
       Terminator = SU;
-
-    // Assign the Latency field of SU using target-provided information.
-    ComputeLatency(SU);
   }
 }
 
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
index d0b8927..9eefc7f 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp
@@ -77,18 +77,20 @@
 
   void Schedule();
 
-  /// AddPred - This adds the specified node X as a predecessor of 
-  /// the current node Y if not already.
+  /// AddPred - adds a predecessor edge to SUnit SU.
   /// This returns true if this is a new predecessor.
-  bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isArtificial,
-               unsigned PhyReg = 0, int Cost = 1);
+  bool AddPred(SUnit *SU, const SDep &D) {
+    return SU->addPred(D);
+  }
 
-  /// RemovePred - This removes the specified node N from the predecessors of 
-  /// the current node M.
-  bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isArtificial);
+  /// RemovePred - removes a predecessor edge from SUnit SU.
+  /// This returns true if an edge was removed.
+  bool RemovePred(SUnit *SU, const SDep &D) {
+    return SU->removePred(D);
+  }
 
 private:
-  void ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain);
+  void ReleasePred(SUnit *SU, SDep *PredEdge);
   void ScheduleNodeBottomUp(SUnit*, unsigned);
   SUnit *CopyAndMoveSuccessors(SUnit*);
   void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned,
@@ -125,7 +127,8 @@
 
 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGFast::ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain) {
+void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {
+  SUnit *PredSU = PredEdge->getSUnit();
   --PredSU->NumSuccsLeft;
   
 #ifndef NDEBUG
@@ -156,16 +159,16 @@
   // Bottom up: release predecessors
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    ReleasePred(SU, I->Dep, I->isCtrl);
-    if (I->Cost < 0)  {
+    ReleasePred(SU, &*I);
+    if (I->isAssignedRegDep()) {
       // This is a physical register dependency and it's impossible or
       // expensive to copy the register. Make sure nothing that can 
       // clobber the register is scheduled between the predecessor and
       // this node.
-      if (!LiveRegDefs[I->Reg]) {
+      if (!LiveRegDefs[I->getReg()]) {
         ++NumLiveRegs;
-        LiveRegDefs[I->Reg] = I->Dep;
-        LiveRegCycles[I->Reg] = CurCycle;
+        LiveRegDefs[I->getReg()] = I->getSUnit();
+        LiveRegCycles[I->getReg()] = CurCycle;
       }
     }
   }
@@ -173,14 +176,14 @@
   // Release all the implicit physical register defs that are live.
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->Cost < 0)  {
-      if (LiveRegCycles[I->Reg] == I->Dep->Cycle) {
+    if (I->isAssignedRegDep()) {
+      if (LiveRegCycles[I->getReg()] == I->getSUnit()->Cycle) {
         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-        assert(LiveRegDefs[I->Reg] == SU &&
+        assert(LiveRegDefs[I->getReg()] == SU &&
                "Physical register dependency violated?");
         --NumLiveRegs;
-        LiveRegDefs[I->Reg] = NULL;
-        LiveRegCycles[I->Reg] = 0;
+        LiveRegDefs[I->getReg()] = NULL;
+        LiveRegCycles[I->getReg()] = 0;
       }
     }
   }
@@ -188,19 +191,6 @@
   SU->isScheduled = true;
 }
 
-/// AddPred - adds an edge from SUnit X to SUnit Y.
-bool ScheduleDAGFast::AddPred(SUnit *Y, SUnit *X, bool isCtrl,
-                              bool isArtificial, unsigned PhyReg, int Cost) {
-  return Y->addPred(X, isCtrl, isArtificial, PhyReg, Cost);
-}
-
-/// RemovePred - This removes the specified node N from the predecessors of 
-/// the current node M.
-bool ScheduleDAGFast::RemovePred(SUnit *M, SUnit *N, 
-                                 bool isCtrl, bool isArtificial) {
-  return M->removePred(N, isCtrl, isArtificial, false);
-}
-
 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
 /// successors to the newly created node.
 SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {
@@ -277,65 +267,66 @@
       LoadSU->Height = SU->Height;
     }
 
-    SUnit *ChainPred = NULL;
+    SDep ChainPred;
     SmallVector<SDep, 4> ChainSuccs;
     SmallVector<SDep, 4> LoadPreds;
     SmallVector<SDep, 4> NodePreds;
     SmallVector<SDep, 4> NodeSuccs;
     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      if (I->isCtrl)
-        ChainPred = I->Dep;
-      else if (I->Dep->getNode() && I->Dep->getNode()->isOperandOf(LoadNode))
-        LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+      if (I->isCtrl())
+        ChainPred = *I;
+      else if (I->getSUnit()->getNode() &&
+               I->getSUnit()->getNode()->isOperandOf(LoadNode))
+        LoadPreds.push_back(*I);
       else
-        NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+        NodePreds.push_back(*I);
     }
     for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
          I != E; ++I) {
-      if (I->isCtrl)
-        ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
-                                  I->isCtrl, I->isArtificial, I->isAntiDep));
+      if (I->isCtrl())
+        ChainSuccs.push_back(*I);
       else
-        NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
-                                 I->isCtrl, I->isArtificial, I->isAntiDep));
+        NodeSuccs.push_back(*I);
     }
 
-    if (ChainPred) {
-      RemovePred(SU, ChainPred, true, false);
+    if (ChainPred.getSUnit()) {
+      RemovePred(SU, ChainPred);
       if (isNewLoad)
-        AddPred(LoadSU, ChainPred, true, false);
+        AddPred(LoadSU, ChainPred);
     }
     for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
-      SDep *Pred = &LoadPreds[i];
-      RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
+      const SDep &Pred = LoadPreds[i];
+      RemovePred(SU, Pred);
       if (isNewLoad) {
-        AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
-                Pred->Reg, Pred->Cost);
+        AddPred(LoadSU, Pred);
       }
     }
     for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
-      SDep *Pred = &NodePreds[i];
-      RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
-      AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
-              Pred->Reg, Pred->Cost);
+      const SDep &Pred = NodePreds[i];
+      RemovePred(SU, Pred);
+      AddPred(NewSU, Pred);
     }
     for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
-      SDep *Succ = &NodeSuccs[i];
-      RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
-      AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isArtificial,
-              Succ->Reg, Succ->Cost);
+      SDep D = NodeSuccs[i];
+      SUnit *SuccDep = D.getSUnit();
+      D.setSUnit(SU);
+      RemovePred(SuccDep, D);
+      D.setSUnit(NewSU);
+      AddPred(SuccDep, D);
     }
     for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
-      SDep *Succ = &ChainSuccs[i];
-      RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
+      SDep D = ChainSuccs[i];
+      SUnit *SuccDep = D.getSUnit();
+      D.setSUnit(SU);
+      RemovePred(SuccDep, D);
       if (isNewLoad) {
-        AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isArtificial,
-                Succ->Reg, Succ->Cost);
+        D.setSUnit(LoadSU);
+        AddPred(SuccDep, D);
       }
     } 
     if (isNewLoad) {
-      AddPred(NewSU, LoadSU, false, false);
+      AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency));
     }
 
     ++NumUnfolds;
@@ -353,28 +344,30 @@
   // New SUnit has the exact same predecessors.
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I)
-    if (!I->isArtificial) {
-      AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost);
-      NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
+    if (!I->isArtificial()) {
+      AddPred(NewSU, *I);
+      NewSU->Depth = std::max(NewSU->Depth, I->getSUnit()->Depth+1);
     }
 
   // Only copy scheduled successors. Cut them from old node's successor
   // list and move them over.
-  SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->isArtificial)
+    if (I->isArtificial())
       continue;
-    if (I->Dep->isScheduled) {
-      NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
-      AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost);
-      DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+    SUnit *SuccSU = I->getSUnit();
+    if (SuccSU->isScheduled) {
+      NewSU->Height = std::max(NewSU->Height, SuccSU->Height+1);
+      SDep D = *I;
+      D.setSUnit(NewSU);
+      AddPred(SuccSU, D);
+      D.setSUnit(SU);
+      DelDeps.push_back(std::make_pair(SuccSU, D));
     }
   }
   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
-    SUnit *Succ = DelDeps[i].first;
-    bool isCtrl = DelDeps[i].second;
-    RemovePred(Succ, SU, isCtrl, false);
+    RemovePred(DelDeps[i].first, DelDeps[i].second);
   }
 
   ++NumDups;
@@ -397,24 +390,25 @@
 
   // Only copy scheduled successors. Cut them from old node's successor
   // list and move them over.
-  SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->isArtificial)
+    if (I->isArtificial())
       continue;
-    if (I->Dep->isScheduled) {
-      AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost);
-      DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+    SUnit *SuccSU = I->getSUnit();
+    if (SuccSU->isScheduled) {
+      SDep D = *I;
+      D.setSUnit(CopyToSU);
+      AddPred(SuccSU, D);
+      DelDeps.push_back(std::make_pair(SuccSU, *I));
     }
   }
   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
-    SUnit *Succ = DelDeps[i].first;
-    bool isCtrl = DelDeps[i].second;
-    RemovePred(Succ, SU, isCtrl, false);
+    RemovePred(DelDeps[i].first, DelDeps[i].second);
   }
 
-  AddPred(CopyFromSU, SU, false, false, Reg, -1);
-  AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1);
+  AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
+  AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
 
   Copies.push_back(CopyFromSU);
   Copies.push_back(CopyToSU);
@@ -451,15 +445,15 @@
   // If this node would clobber any "live" register, then it's not ready.
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    if (I->Cost < 0)  {
-      unsigned Reg = I->Reg;
-      if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->Dep) {
+    if (I->isAssignedRegDep()) {
+      unsigned Reg = I->getReg();
+      if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) {
         if (RegAdded.insert(Reg))
           LRegs.push_back(Reg);
       }
       for (const unsigned *Alias = TRI->getAliasSet(Reg);
            *Alias; ++Alias)
-        if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) {
+        if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) {
           if (RegAdded.insert(*Alias))
             LRegs.push_back(*Alias);
         }
@@ -550,14 +544,18 @@
           InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
           DOUT << "Adding an edge from SU # " << TrySU->NodeNum
                << " to SU #" << Copies.front()->NodeNum << "\n";
-          AddPred(TrySU, Copies.front(), true, true);
+          AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
+                              /*Reg=*/0, /*isNormalMemory=*/false,
+                              /*isMustAlias=*/false, /*isArtificial=*/true));
           NewDef = Copies.back();
         }
 
         DOUT << "Adding an edge from SU # " << NewDef->NodeNum
              << " to SU #" << TrySU->NodeNum << "\n";
         LiveRegDefs[Reg] = NewDef;
-        AddPred(NewDef, TrySU, true, true);
+        AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
+                             /*Reg=*/0, /*isNormalMemory=*/false,
+                             /*isMustAlias=*/false, /*isArtificial=*/true));
         TrySU->isAvailable = false;
         CurSU = NewDef;
       }
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index d4acf5f..b01700e 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -78,7 +78,7 @@
   void Schedule();
 
 private:
-  void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
+  void ReleaseSucc(SUnit *SU, const SDep &D);
   void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
   void ListScheduleTopDown();
 };
@@ -107,7 +107,8 @@
 
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void ScheduleDAGList::ReleaseSucc(SUnit *SU, const SDep &D) {
+  SUnit *SuccSU = D.getSUnit();
   --SuccSU->NumPredsLeft;
   
 #ifndef NDEBUG
@@ -121,14 +122,7 @@
   
   // Compute the cycle when this SUnit 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 + SU->Latency;
   SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
   
   if (SuccSU->NumPredsLeft == 0) {
@@ -149,7 +143,7 @@
   // 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);
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index 02cc285..1a18b81 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -98,27 +98,26 @@
     return Topo.WillCreateCycle(SU, TargetSU);
   }
 
-  /// AddPred - This adds the specified node X as a predecessor of 
-  /// the current node Y if not already.
+  /// AddPred - adds a predecessor edge to SUnit SU.
   /// This returns true if this is a new predecessor.
   /// Updates the topological ordering if required.
-  bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isArtificial,
-               unsigned PhyReg = 0, int Cost = 1) {
-    Topo.AddPred(Y, X);
-    return Y->addPred(X, isCtrl, isArtificial, PhyReg, Cost);
+  bool AddPred(SUnit *SU, const SDep &D) {
+    Topo.AddPred(SU, D.getSUnit());
+    return SU->addPred(D);
   }
 
-  /// RemovePred - This removes the specified node N from the predecessors of 
-  /// the current node M. Updates the topological ordering if required.
-  bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isArtificial) {
-    Topo.RemovePred(M, N);
-    return M->removePred(N, isCtrl, isArtificial, false);
+  /// RemovePred - removes a predecessor edge from SUnit SU.
+  /// This returns true if an edge was removed.
+  /// Updates the topological ordering if required.
+  bool RemovePred(SUnit *SU, const SDep &D) {
+    Topo.RemovePred(SU, D.getSUnit());
+    return SU->removePred(D);
   }
 
 private:
-  void ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain);
-  void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
-  void CapturePred(SUnit*, SUnit*, bool);
+  void ReleasePred(SUnit *SU, SDep *PredEdge);
+  void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
+  void CapturePred(SDep *PredEdge);
   void ScheduleNodeBottomUp(SUnit*, unsigned);
   void ScheduleNodeTopDown(SUnit*, unsigned);
   void UnscheduleNodeBottomUp(SUnit*);
@@ -235,8 +234,8 @@
 
     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      if (!I->isCtrl)
-        OperandSeen.insert(I->Dep->OrigNode);
+      if (!I->isCtrl())
+        OperandSeen.insert(I->getSUnit()->OrigNode);
     }
   }
 }
@@ -247,7 +246,8 @@
 
 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGRRList::ReleasePred(SUnit *SU, SUnit *PredSU, bool isChain) {
+void ScheduleDAGRRList::ReleasePred(SUnit *SU, SDep *PredEdge) {
+  SUnit *PredSU = PredEdge->getSUnit();
   --PredSU->NumSuccsLeft;
   
 #ifndef NDEBUG
@@ -278,16 +278,16 @@
   // Bottom up: release predecessors
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    ReleasePred(SU, I->Dep, I->isCtrl);
-    if (I->Cost < 0)  {
+    ReleasePred(SU, &*I);
+    if (I->isAssignedRegDep()) {
       // This is a physical register dependency and it's impossible or
       // expensive to copy the register. Make sure nothing that can 
       // clobber the register is scheduled between the predecessor and
       // this node.
-      if (!LiveRegDefs[I->Reg]) {
+      if (!LiveRegDefs[I->getReg()]) {
         ++NumLiveRegs;
-        LiveRegDefs[I->Reg] = I->Dep;
-        LiveRegCycles[I->Reg] = CurCycle;
+        LiveRegDefs[I->getReg()] = I->getSUnit();
+        LiveRegCycles[I->getReg()] = CurCycle;
       }
     }
   }
@@ -295,14 +295,14 @@
   // Release all the implicit physical register defs that are live.
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->Cost < 0)  {
-      if (LiveRegCycles[I->Reg] == I->Dep->Cycle) {
+    if (I->isAssignedRegDep()) {
+      if (LiveRegCycles[I->getReg()] == I->getSUnit()->Cycle) {
         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-        assert(LiveRegDefs[I->Reg] == SU &&
+        assert(LiveRegDefs[I->getReg()] == SU &&
                "Physical register dependency violated?");
         --NumLiveRegs;
-        LiveRegDefs[I->Reg] = NULL;
-        LiveRegCycles[I->Reg] = 0;
+        LiveRegDefs[I->getReg()] = NULL;
+        LiveRegCycles[I->getReg()] = 0;
       }
     }
   }
@@ -314,7 +314,8 @@
 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
 /// unscheduled, incrcease the succ left count of its predecessors. Remove
 /// them from AvailableQueue if necessary.
-void ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) {  
+void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {  
+  SUnit *PredSU = PredEdge->getSUnit();
   if (PredSU->isAvailable) {
     PredSU->isAvailable = false;
     if (!PredSU->isPending)
@@ -334,26 +335,26 @@
 
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    CapturePred(I->Dep, SU, I->isCtrl);
-    if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg])  {
+    CapturePred(&*I);
+    if (I->isAssignedRegDep() && SU->Cycle == LiveRegCycles[I->getReg()]) {
       assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-      assert(LiveRegDefs[I->Reg] == I->Dep &&
+      assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
              "Physical register dependency violated?");
       --NumLiveRegs;
-      LiveRegDefs[I->Reg] = NULL;
-      LiveRegCycles[I->Reg] = 0;
+      LiveRegDefs[I->getReg()] = NULL;
+      LiveRegCycles[I->getReg()] = 0;
     }
   }
 
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->Cost < 0)  {
-      if (!LiveRegDefs[I->Reg]) {
-        LiveRegDefs[I->Reg] = SU;
+    if (I->isAssignedRegDep()) {
+      if (!LiveRegDefs[I->getReg()]) {
+        LiveRegDefs[I->getReg()] = SU;
         ++NumLiveRegs;
       }
-      if (I->Dep->Cycle < LiveRegCycles[I->Reg])
-        LiveRegCycles[I->Reg] = I->Dep->Cycle;
+      if (I->getSUnit()->Cycle < LiveRegCycles[I->getReg()])
+        LiveRegCycles[I->getReg()] = I->getSUnit()->Cycle;
     }
   }
 
@@ -466,65 +467,66 @@
     NewSU->Height = SU->Height;
     ComputeLatency(NewSU);
 
-    SUnit *ChainPred = NULL;
+    SDep ChainPred;
     SmallVector<SDep, 4> ChainSuccs;
     SmallVector<SDep, 4> LoadPreds;
     SmallVector<SDep, 4> NodePreds;
     SmallVector<SDep, 4> NodeSuccs;
     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
-      if (I->isCtrl)
-        ChainPred = I->Dep;
-      else if (I->Dep->getNode() && I->Dep->getNode()->isOperandOf(LoadNode))
-        LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+      if (I->isCtrl())
+        ChainPred = *I;
+      else if (I->getSUnit()->getNode() &&
+               I->getSUnit()->getNode()->isOperandOf(LoadNode))
+        LoadPreds.push_back(*I);
       else
-        NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false, false));
+        NodePreds.push_back(*I);
     }
     for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
          I != E; ++I) {
-      if (I->isCtrl)
-        ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
-                                  I->isCtrl, I->isArtificial, I->isAntiDep));
+      if (I->isCtrl())
+        ChainSuccs.push_back(*I);
       else
-        NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost,
-                                 I->isCtrl, I->isArtificial, I->isAntiDep));
+        NodeSuccs.push_back(*I);
     }
 
-    if (ChainPred) {
-      RemovePred(SU, ChainPred, true, false);
+    if (ChainPred.getSUnit()) {
+      RemovePred(SU, ChainPred);
       if (isNewLoad)
-        AddPred(LoadSU, ChainPred, true, false);
+        AddPred(LoadSU, ChainPred);
     }
     for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
-      SDep *Pred = &LoadPreds[i];
-      RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
+      const SDep &Pred = LoadPreds[i];
+      RemovePred(SU, Pred);
       if (isNewLoad) {
-        AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
-                Pred->Reg, Pred->Cost);
+        AddPred(LoadSU, Pred);
       }
     }
     for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
-      SDep *Pred = &NodePreds[i];
-      RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isArtificial);
-      AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isArtificial,
-              Pred->Reg, Pred->Cost);
+      const SDep &Pred = NodePreds[i];
+      RemovePred(SU, Pred);
+      AddPred(NewSU, Pred);
     }
     for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
-      SDep *Succ = &NodeSuccs[i];
-      RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
-      AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isArtificial,
-              Succ->Reg, Succ->Cost);
+      SDep D = NodeSuccs[i];
+      SUnit *SuccDep = D.getSUnit();
+      D.setSUnit(SU);
+      RemovePred(SuccDep, D);
+      D.setSUnit(NewSU);
+      AddPred(SuccDep, D);
     }
     for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
-      SDep *Succ = &ChainSuccs[i];
-      RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isArtificial);
+      SDep D = ChainSuccs[i];
+      SUnit *SuccDep = D.getSUnit();
+      D.setSUnit(SU);
+      RemovePred(SuccDep, D);
       if (isNewLoad) {
-        AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isArtificial,
-                Succ->Reg, Succ->Cost);
+        D.setSUnit(LoadSU);
+        AddPred(SuccDep, D);
       }
     } 
     if (isNewLoad) {
-      AddPred(NewSU, LoadSU, false, false);
+      AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency));
     }
 
     if (isNewLoad)
@@ -546,28 +548,30 @@
   // New SUnit has the exact same predecessors.
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I)
-    if (!I->isArtificial) {
-      AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost);
-      NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
+    if (!I->isArtificial()) {
+      AddPred(NewSU, *I);
+      NewSU->Depth = std::max(NewSU->Depth, I->getSUnit()->Depth+1);
     }
 
   // Only copy scheduled successors. Cut them from old node's successor
   // list and move them over.
-  SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->isArtificial)
+    if (I->isArtificial())
       continue;
-    if (I->Dep->isScheduled) {
-      NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
-      AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost);
-      DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+    SUnit *SuccSU = I->getSUnit();
+    if (SuccSU->isScheduled) {
+      NewSU->Height = std::max(NewSU->Height, SuccSU->Height+1);
+      SDep D = *I;
+      D.setSUnit(NewSU);
+      AddPred(SuccSU, D);
+      D.setSUnit(SU);
+      DelDeps.push_back(std::make_pair(SuccSU, D));
     }
   }
   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
-    SUnit *Succ = DelDeps[i].first;
-    bool isCtrl = DelDeps[i].second;
-    RemovePred(Succ, SU, isCtrl, false);
+    RemovePred(DelDeps[i].first, DelDeps[i].second);
   }
 
   AvailableQueue->updateNode(SU);
@@ -595,25 +599,25 @@
 
   // Only copy scheduled successors. Cut them from old node's successor
   // list and move them over.
-  SmallVector<std::pair<SUnit*, bool>, 4> DelDeps;
+  SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->isArtificial)
+    if (I->isArtificial())
       continue;
-    if (I->Dep->isScheduled) {
-      CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1);
-      AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost);
-      DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl));
+    SUnit *SuccSU = I->getSUnit();
+    if (SuccSU->isScheduled) {
+      SDep D = *I;
+      D.setSUnit(CopyToSU);
+      AddPred(SuccSU, D);
+      DelDeps.push_back(std::make_pair(SuccSU, *I));
     }
   }
   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
-    SUnit *Succ = DelDeps[i].first;
-    bool isCtrl = DelDeps[i].second;
-    RemovePred(Succ, SU, isCtrl, false);
+    RemovePred(DelDeps[i].first, DelDeps[i].second);
   }
 
-  AddPred(CopyFromSU, SU, false, false, Reg, -1);
-  AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1);
+  AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
+  AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
 
   AvailableQueue->updateNode(SU);
   AvailableQueue->addNode(CopyFromSU);
@@ -653,15 +657,15 @@
   // If this node would clobber any "live" register, then it's not ready.
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    if (I->Cost < 0)  {
-      unsigned Reg = I->Reg;
-      if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->Dep) {
+    if (I->isAssignedRegDep()) {
+      unsigned Reg = I->getReg();
+      if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) {
         if (RegAdded.insert(Reg))
           LRegs.push_back(Reg);
       }
       for (const unsigned *Alias = TRI->getAliasSet(Reg);
            *Alias; ++Alias)
-        if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) {
+        if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) {
           if (RegAdded.insert(*Alias))
             LRegs.push_back(*Alias);
         }
@@ -749,7 +753,9 @@
             OldSU->isAvailable = false;
             AvailableQueue->remove(OldSU);
           }
-          AddPred(TrySU, OldSU, true, true);
+          AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
+                              /*Reg=*/0, /*isNormalMemory=*/false,
+                              /*isMustAlias=*/false, /*isArtificial=*/true));
           // If one or more successors has been unscheduled, then the current
           // node is no longer avaialable. Schedule a successor that's now
           // available instead.
@@ -788,14 +794,18 @@
           InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
           DOUT << "Adding an edge from SU # " << TrySU->NodeNum
                << " to SU #" << Copies.front()->NodeNum << "\n";
-          AddPred(TrySU, Copies.front(), true, true);
+          AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
+                              /*Reg=*/0, /*isMustAlias=*/false,
+                              /*isArtificial=*/true));
           NewDef = Copies.back();
         }
 
         DOUT << "Adding an edge from SU # " << NewDef->NodeNum
              << " to SU #" << TrySU->NodeNum << "\n";
         LiveRegDefs[Reg] = NewDef;
-        AddPred(NewDef, TrySU, true, true);
+        AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
+                             /*Reg=*/0, /*isMustAlias=*/false,
+                             /*isArtificial=*/true));
         TrySU->isAvailable = false;
         CurSU = NewDef;
       }
@@ -834,7 +844,8 @@
 
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
-void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
+void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
+  SUnit *SuccSU = SuccEdge->getSUnit();
   --SuccSU->NumPredsLeft;
   
 #ifndef NDEBUG
@@ -865,7 +876,7 @@
   // 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);
@@ -948,13 +959,13 @@
   unsigned Extra = 0;
   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    if (I->isCtrl) continue;  // ignore chain preds
-    SUnit *PredSU = I->Dep;
+    if (I->isCtrl()) continue;  // ignore chain preds
+    SUnit *PredSU = I->getSUnit();
     unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
     if (PredSethiUllman > SethiUllmanNumber) {
       SethiUllmanNumber = PredSethiUllman;
       Extra = 0;
-    } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
+    } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl())
       ++Extra;
   }
 
@@ -1099,11 +1110,12 @@
   unsigned MaxCycle = 0;
   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    unsigned Cycle = I->Dep->Cycle;
+    unsigned Cycle = I->getSUnit()->Cycle;
     // If there are bunch of CopyToRegs stacked up, they should be considered
     // to be at the same position.
-    if (I->Dep->getNode() && I->Dep->getNode()->getOpcode() == ISD::CopyToReg)
-      Cycle = closestSucc(I->Dep)+1;
+    if (I->getSUnit()->getNode() &&
+        I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
+      Cycle = closestSucc(I->getSUnit())+1;
     if (Cycle > MaxCycle)
       MaxCycle = Cycle;
   }
@@ -1117,14 +1129,16 @@
   unsigned Scratches = 0;
   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->getNode() || I->Dep->getNode()->getOpcode() != ISD::CopyFromReg)
+    if (I->isCtrl()) continue;  // ignore chain preds
+    if (!I->getSUnit()->getNode() ||
+        I->getSUnit()->getNode()->getOpcode() != ISD::CopyFromReg)
       Scratches++;
   }
   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->isCtrl) continue;  // ignore chain succs
-    if (!I->Dep->getNode() || I->Dep->getNode()->getOpcode() != ISD::CopyToReg)
+    if (I->isCtrl()) continue;  // ignore chain succs
+    if (!I->getSUnit()->getNode() ||
+        I->getSUnit()->getNode()->getOpcode() != ISD::CopyToReg)
       Scratches += 10;
   }
   return Scratches;
@@ -1205,8 +1219,8 @@
 static bool hasCopyToRegUse(const SUnit *SU) {
   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    if (I->isCtrl) continue;
-    const SUnit *SuccSU = I->Dep;
+    if (I->isCtrl()) continue;
+    const SUnit *SuccSU = I->getSUnit();
     if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
       return true;
   }
@@ -1274,8 +1288,8 @@
       if (!DUSU) continue;
       for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
            E = DUSU->Succs.end(); I != E; ++I) {
-        if (I->isCtrl) continue;
-        SUnit *SuccSU = I->Dep;
+        if (I->isCtrl()) continue;
+        SUnit *SuccSU = I->getSUnit();
         if (SuccSU == SU)
           continue;
         // Be conservative. Ignore if nodes aren't at roughly the same
@@ -1302,7 +1316,9 @@
             !scheduleDAG->IsReachable(SuccSU, SU)) {
           DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum
                << " to SU #" << SuccSU->NodeNum << "\n";
-          scheduleDAG->AddPred(SU, SuccSU, true, true);
+          scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/1,
+                                        /*Reg=*/0, /*isMustAlias=*/false,
+                                        /*isArtificial=*/true));
         }
       }
     }
@@ -1327,10 +1343,10 @@
   unsigned Sum = 0;
   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
-    const SUnit *SuccSU = I->Dep;
+    const SUnit *SuccSU = I->getSUnit();
     for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
          EE = SuccSU->Preds.end(); II != EE; ++II) {
-      SUnit *PredSU = II->Dep;
+      SUnit *PredSU = II->getSUnit();
       if (!PredSU->isScheduled)
         if (++Sum > Limit)
           return Sum;
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
index aef23c5..69d3045 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
@@ -176,7 +176,10 @@
         int Cost = 1;
         // Determine if this is a physical register dependency.
         CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
-        SU->addPred(OpSU, isChain, false, PhysReg, Cost);
+        assert((PhysReg == 0 || !isChain) &&
+               "Chain dependence via physreg data?");
+        SU->addPred(SDep(OpSU, isChain ? SDep::Order : SDep::Data,
+                         OpSU->Latency, PhysReg));
       }
     }
   }