diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index 17938d7..ad44b24 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -79,12 +79,13 @@
   /// 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.
-    bool      isCtrl;   // True iff it's a control dependency.
-    unsigned  PhyReg;   // If non-zero, this dep is a phy register dependency.
-    int       Cost;     // Cost of the dependency.
-    SDep(SUnit *d, bool c, unsigned r, int t)
-      : Dep(d), isCtrl(c), PhyReg(r), Cost(t) {}
+    SUnit    *Dep;           // Dependent - either a predecessor or a successor.
+    unsigned  Reg;           // If non-zero, this dep is a phy register dependency.
+    int       Cost;          // Cost of the dependency.
+    bool      isCtrl    : 1; // True iff it's a control dependency.
+    bool      isSpecial : 1; // True iff it's a special ctrl dep added during sched.
+    SDep(SUnit *d, unsigned r, int t, bool c, bool s)
+      : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {}
   };
 
   /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
@@ -92,6 +93,8 @@
   struct SUnit {
     SDNode *Node;                       // Representative node.
     SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node.
+    unsigned InstanceNo;                // Instance#. One SDNode can be multiple
+                                        // SUnit due to cloning.
     
     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
     // is true if the edge is a token chain edge, false if it is a value edge. 
@@ -103,6 +106,8 @@
     typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
     typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
     
+    unsigned NodeNum;                   // Entry # of node in the node vector.
+    unsigned short Latency;             // Node latency.
     short NumPreds;                     // # of preds.
     short NumSuccs;                     // # of sucss.
     short NumPredsLeft;                 // # of preds not scheduled.
@@ -111,42 +116,94 @@
     short NumChainSuccsLeft;            // # of chain succs not scheduled.
     bool isTwoAddress     : 1;          // Is a two-address instruction.
     bool isCommutable     : 1;          // Is a commutable instruction.
+    bool hasImplicitDefs  : 1;          // Has implicit physical reg defs.
     bool isPending        : 1;          // True once pending.
     bool isAvailable      : 1;          // True once available.
     bool isScheduled      : 1;          // True once scheduled.
-    unsigned short Latency;             // Node latency.
     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
     unsigned Cycle;                     // Once scheduled, the cycle of the op.
     unsigned Depth;                     // Node depth;
     unsigned Height;                    // Node height;
-    unsigned NodeNum;                   // Entry # of node in the node vector.
     
     SUnit(SDNode *node, unsigned nodenum)
-      : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
+      : Node(node), InstanceNo(0), NodeNum(nodenum), Latency(0),
+        NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
         NumChainPredsLeft(0), NumChainSuccsLeft(0),
-        isTwoAddress(false), isCommutable(false),
+        isTwoAddress(false), isCommutable(false), hasImplicitDefs(false),
         isPending(false), isAvailable(false), isScheduled(false),
-        Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0),
-        NodeNum(nodenum) {}
-    
+        CycleBound(0), Cycle(0), Depth(0), Height(0) {}
+
     /// addPred - This adds the specified node as a pred of the current node if
     /// not already.  This returns true if this is a new pred.
-    bool addPred(SUnit *N, bool isCtrl, unsigned PhyReg = 0, int Cost = 1) {
+    bool addPred(SUnit *N, bool isCtrl, bool isSpecial,
+                 unsigned PhyReg = 0, int Cost = 1) {
       for (unsigned i = 0, e = Preds.size(); i != e; ++i)
-        if (Preds[i].Dep == N && Preds[i].isCtrl == isCtrl)
+        if (Preds[i].Dep == N &&
+            Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial)
           return false;
-      Preds.push_back(SDep(N, isCtrl, PhyReg, Cost));
+      Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial));
+      N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial));
+      if (isCtrl) {
+        if (!N->isScheduled)
+          ++NumChainPredsLeft;
+        if (!isScheduled)
+          ++N->NumChainSuccsLeft;
+      } else {
+        ++NumPreds;
+        ++N->NumSuccs;
+        if (!N->isScheduled)
+          ++NumPredsLeft;
+        if (!isScheduled)
+          ++N->NumSuccsLeft;
+      }
       return true;
     }
 
-    /// addSucc - This adds the specified node as a succ of the current node if
-    /// not already.  This returns true if this is a new succ.
-    bool addSucc(SUnit *N, bool isCtrl, unsigned PhyReg = 0, int Cost = 1) {
+    bool removePred(SUnit *N, bool isCtrl, bool isSpecial) {
+      for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
+           I != E; ++I)
+        if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) {
+          bool FoundSucc = false;
+          for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
+                 EE = N->Succs.end(); II != EE; ++II)
+            if (II->Dep == this &&
+                II->isCtrl == isCtrl && II->isSpecial == isSpecial) {
+              FoundSucc = true;
+              N->Succs.erase(II);
+              break;
+            }
+          assert(FoundSucc && "Mismatching preds / succs lists!");
+          Preds.erase(I);
+          if (isCtrl) {
+            if (!N->isScheduled)
+              --NumChainPredsLeft;
+            if (!isScheduled)
+              --NumChainSuccsLeft;
+          } else {
+            --NumPreds;
+            --N->NumSuccs;
+            if (!N->isScheduled)
+              --NumPredsLeft;
+            if (!isScheduled)
+              --N->NumSuccsLeft;
+          }
+          return true;
+        }
+      return false;
+    }
+
+    bool isPred(SUnit *N) {
+      for (unsigned i = 0, e = Preds.size(); i != e; ++i)
+        if (Preds[i].Dep == N)
+          return true;
+      return false;
+    }
+    
+    bool isSucc(SUnit *N) {
       for (unsigned i = 0, e = Succs.size(); i != e; ++i)
-        if (Succs[i].Dep == N && Succs[i].isCtrl == isCtrl)
-          return false;
-      Succs.push_back(SDep(N, isCtrl, PhyReg, Cost));
-      return true;
+        if (Succs[i].Dep == N)
+          return true;
+      return false;
     }
     
     void dump(const SelectionDAG *G) const;
@@ -165,20 +222,27 @@
   public:
     virtual ~SchedulingPriorityQueue() {}
   
-    virtual void initNodes(DenseMap<SDNode*, SUnit*> &SUMap,
+    virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &SUMap,
                            std::vector<SUnit> &SUnits) = 0;
+    virtual void addNode(const SUnit *SU) = 0;
+    virtual void updateNode(const SUnit *SU) = 0;
     virtual void releaseState() = 0;
-  
+
+    virtual unsigned size() const = 0;
     virtual bool empty() const = 0;
     virtual void push(SUnit *U) = 0;
   
     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
     virtual SUnit *pop() = 0;
 
+    virtual void remove(SUnit *SU) = 0;
+
     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
     /// allows the priority function to adjust the priority of node that have
     /// already been emitted.
     virtual void ScheduledNode(SUnit *Node) {}
+
+    virtual void UnscheduledNode(SUnit *Node) {}
   };
 
   class ScheduleDAG {
@@ -192,7 +256,8 @@
     MachineConstantPool *ConstPool;       // Target constant pool
     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
                                           // represent noop instructions.
-    DenseMap<SDNode*, SUnit*> SUnitMap;   // SDNode to SUnit mapping (n -> 1).
+    DenseMap<SDNode*, std::vector<SUnit*> > SUnitMap;
+                                          // SDNode to SUnit mapping (n -> n).
     std::vector<SUnit> SUnits;            // The scheduling units.
     SmallSet<SDNode*, 16> CommuteSet;     // Nodes the should be commuted.
 
@@ -232,6 +297,10 @@
       return &SUnits.back();
     }
 
+    /// Clone - Creates a clone of the specified SUnit. It does not copy the
+    /// predecessors / successors info nor the temporary scheduling states.
+    SUnit *Clone(SUnit *N);
+    
     /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
     /// This SUnit graph is similar to the SelectionDAG, but represents flagged
     /// together nodes with a single SUnit.
@@ -256,7 +325,8 @@
     /// VRBaseMap contains, for each already emitted node, the first virtual
     /// register number for the results of the node.
     ///
-    void EmitNode(SDNode *Node, DenseMap<SDOperand, unsigned> &VRBaseMap);
+    void EmitNode(SDNode *Node, unsigned InstNo,
+                  DenseMap<SDOperand, unsigned> &VRBaseMap);
     
     /// EmitNoop - Emit a noop instruction.
     ///
@@ -264,7 +334,8 @@
 
     /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
     /// implicit physical register output.
-    void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned SrcReg,
+    void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo,
+                         unsigned SrcReg,
                          DenseMap<SDOperand, unsigned> &VRBaseMap);
     
     void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 1346595..b775122 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -27,6 +27,65 @@
 #include "llvm/Support/MathExtras.h"
 using namespace llvm;
 
+
+/// getPhysicalRegisterRegClass - Returns the Register Class of a physical
+/// register.
+static const TargetRegisterClass *getPhysicalRegisterRegClass(
+        const MRegisterInfo *MRI,
+        MVT::ValueType VT,
+        unsigned reg) {
+  assert(MRegisterInfo::isPhysicalRegister(reg) &&
+         "reg must be a physical register");
+  // Pick the register class of the right type that contains this physreg.
+  for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
+         E = MRI->regclass_end(); I != E; ++I)
+    if ((*I)->hasType(VT) && (*I)->contains(reg))
+      return *I;
+  assert(false && "Couldn't find the register class");
+  return 0;
+}
+
+
+/// CheckForPhysRegDependency - Check if the dependency between def and use of
+/// a specified operand is a physical register dependency. If so, returns the
+/// register and the cost of copying the register.
+static void CheckForPhysRegDependency(SDNode *Def, SDNode *Use, unsigned Op,
+                                      const MRegisterInfo *MRI, 
+                                      const TargetInstrInfo *TII,
+                                      unsigned &PhysReg, int &Cost) {
+  if (Op != 2 || Use->getOpcode() != ISD::CopyToReg)
+    return;
+
+  unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
+  if (MRegisterInfo::isVirtualRegister(Reg))
+    return;
+
+  unsigned ResNo = Use->getOperand(2).ResNo;
+  if (Def->isTargetOpcode()) {
+    const TargetInstrDescriptor &II = TII->get(Def->getTargetOpcode());
+    if (ResNo >= II.numDefs &&
+        II.ImplicitDefs[ResNo - II.numDefs] == Reg) {
+      PhysReg = Reg;
+      const TargetRegisterClass *RC =
+        getPhysicalRegisterRegClass(MRI, Def->getValueType(ResNo), Reg);
+      Cost = RC->getCopyCost();
+    }
+  }
+}
+
+SUnit *ScheduleDAG::Clone(SUnit *Old) {
+  SUnit *SU = NewSUnit(Old->Node);
+  for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i)
+    SU->FlaggedNodes.push_back(SU->FlaggedNodes[i]);
+  SU->InstanceNo = SUnitMap[Old->Node].size();
+  SU->Latency = Old->Latency;
+  SU->isTwoAddress = Old->isTwoAddress;
+  SU->isCommutable = Old->isCommutable;
+  SU->hasImplicitDefs = Old->hasImplicitDefs;
+  SUnitMap[Old->Node].push_back(SU);
+  return SU;
+}
+
 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
 /// together nodes with a single SUnit.
@@ -44,7 +103,7 @@
       continue;
     
     // If this node has already been processed, stop now.
-    if (SUnitMap[NI]) continue;
+    if (SUnitMap[NI].size()) continue;
     
     SUnit *NodeSUnit = NewSUnit(NI);
     
@@ -59,7 +118,7 @@
       do {
         N = N->getOperand(N->getNumOperands()-1).Val;
         NodeSUnit->FlaggedNodes.push_back(N);
-        SUnitMap[N] = NodeSUnit;
+        SUnitMap[N].push_back(NodeSUnit);
       } while (N->getNumOperands() &&
                N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
       std::reverse(NodeSUnit->FlaggedNodes.begin(),
@@ -79,7 +138,7 @@
         if (FlagVal.isOperand(*UI)) {
           HasFlagUse = true;
           NodeSUnit->FlaggedNodes.push_back(N);
-          SUnitMap[N] = NodeSUnit;
+          SUnitMap[N].push_back(NodeSUnit);
           N = *UI;
           break;
         }
@@ -89,7 +148,7 @@
     // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
     // Update the SUnit
     NodeSUnit->Node = N;
-    SUnitMap[N] = NodeSUnit;
+    SUnitMap[N].push_back(NodeSUnit);
     
     // Compute the latency for the node.  We use the sum of the latencies for
     // all nodes flagged together into this SUnit.
@@ -125,13 +184,16 @@
     
     if (MainNode->isTargetOpcode()) {
       unsigned Opc = MainNode->getTargetOpcode();
-      for (unsigned i = 0, ee = TII->getNumOperands(Opc); i != ee; ++i) {
-        if (TII->getOperandConstraint(Opc, i, TOI::TIED_TO) != -1) {
+      const TargetInstrDescriptor &TID = TII->get(Opc);
+      if (TID.ImplicitDefs)
+        SU->hasImplicitDefs = true;
+      for (unsigned i = 0; i != TID.numOperands; ++i) {
+        if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
           SU->isTwoAddress = true;
           break;
         }
       }
-      if (TII->isCommutableInstr(Opc))
+      if (TID.Flags & M_COMMUTABLE)
         SU->isCommutable = true;
     }
     
@@ -141,34 +203,25 @@
     
     for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
       SDNode *N = SU->FlaggedNodes[n];
+      if (N->isTargetOpcode() && TII->getImplicitDefs(N->getTargetOpcode()))
+        SU->hasImplicitDefs = true;
       
       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
         SDNode *OpN = N->getOperand(i).Val;
         if (isPassiveNode(OpN)) continue;   // Not scheduled.
-        SUnit *OpSU = SUnitMap[OpN];
+        SUnit *OpSU = SUnitMap[OpN].front();
         assert(OpSU && "Node has no SUnit!");
         if (OpSU == SU) continue;           // In the same group.
 
         MVT::ValueType OpVT = N->getOperand(i).getValueType();
         assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
         bool isChain = OpVT == MVT::Other;
-        
-        if (SU->addPred(OpSU, isChain)) {
-          if (!isChain) {
-            SU->NumPreds++;
-            SU->NumPredsLeft++;
-          } else {
-            SU->NumChainPredsLeft++;
-          }
-        }
-        if (OpSU->addSucc(SU, isChain)) {
-          if (!isChain) {
-            OpSU->NumSuccs++;
-            OpSU->NumSuccsLeft++;
-          } else {
-            OpSU->NumChainSuccsLeft++;
-          }
-        }
+
+        unsigned PhysReg = 0;
+        int Cost = 1;
+        // Determine if this is a physical register dependency.
+        CheckForPhysRegDependency(OpN, N, i, MRI, TII, PhysReg, Cost);
+        SU->addPred(OpSU, isChain, false, PhysReg, Cost);
       }
     }
     
@@ -200,7 +253,7 @@
 
 void ScheduleDAG::CalculateHeights() {
   std::vector<std::pair<SUnit*, unsigned> > WorkList;
-  SUnit *Root = SUnitMap[DAG.getRoot().Val];
+  SUnit *Root = SUnitMap[DAG.getRoot().Val].front();
   WorkList.push_back(std::make_pair(Root, 0U));
 
   while (!WorkList.empty()) {
@@ -254,27 +307,14 @@
          ? TII->getPointerRegClass() : MRI->getRegClass(toi.RegClass);
 }
 
-// Returns the Register Class of a physical register
-static const TargetRegisterClass *getPhysicalRegisterRegClass(
-        const MRegisterInfo *MRI,
-        MVT::ValueType VT,
-        unsigned reg) {
-  assert(MRegisterInfo::isPhysicalRegister(reg) &&
-         "reg must be a physical register");
-  // Pick the register class of the right type that contains this physreg.
-  for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
-         E = MRI->regclass_end(); I != E; ++I)
-    if ((*I)->hasType(VT) && (*I)->contains(reg))
-      return *I;
-  assert(false && "Couldn't find the register class");
-  return 0;
-}
-
-void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned SrcReg,
+void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
+                                  unsigned InstanceNo, unsigned SrcReg,
                                   DenseMap<SDOperand, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
   if (MRegisterInfo::isVirtualRegister(SrcReg)) {
     // Just use the input register directly!
+    if (InstanceNo > 0)
+      VRBaseMap.erase(SDOperand(Node, ResNo));
     bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo),SrcReg));
     assert(isNew && "Node emitted out of order - early");
     return;
@@ -282,32 +322,54 @@
 
   // If the node is only used by a CopyToReg and the dest reg is a vreg, use
   // the CopyToReg'd destination register instead of creating a new vreg.
+  bool MatchReg = true;
   for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
        UI != E; ++UI) {
     SDNode *Use = *UI;
+    bool Match = true;
     if (Use->getOpcode() == ISD::CopyToReg && 
         Use->getOperand(2).Val == Node &&
         Use->getOperand(2).ResNo == ResNo) {
       unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
       if (MRegisterInfo::isVirtualRegister(DestReg)) {
         VRBase = DestReg;
-        break;
+        Match = false;
+      } else if (DestReg != SrcReg)
+        Match = false;
+    } else {
+      for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
+        SDOperand Op = Use->getOperand(i);
+        if (Op.Val != Node)
+          continue;
+        MVT::ValueType VT = Node->getValueType(Op.ResNo);
+        if (VT != MVT::Other && VT != MVT::Flag)
+          Match = false;
       }
     }
+    MatchReg &= Match;
+    if (VRBase)
+      break;
   }
 
-  // Figure out the register class to create for the destreg.
   const TargetRegisterClass *TRC = 0;
-  if (VRBase) {
+  // Figure out the register class to create for the destreg.
+  if (VRBase)
     TRC = RegMap->getRegClass(VRBase);
-  } else {
+  else
     TRC = getPhysicalRegisterRegClass(MRI, Node->getValueType(ResNo), SrcReg);
-
+    
+  // If all uses are reading from the src physical register and copying the
+  // register is either impossible or very expensive, then don't create a copy.
+  if (MatchReg && TRC->getCopyCost() < 0) {
+    VRBase = SrcReg;
+  } else {
     // Create the reg, emit the copy.
     VRBase = RegMap->createVirtualRegister(TRC);
+    MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
   }
-  MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
 
+  if (InstanceNo > 0)
+    VRBaseMap.erase(SDOperand(Node, ResNo));
   bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo), VRBase));
   assert(isNew && "Node emitted out of order - early");
 }
@@ -611,7 +673,7 @@
 
 /// EmitNode - Generate machine code for an node and needed dependencies.
 ///
-void ScheduleDAG::EmitNode(SDNode *Node, 
+void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
   // If machine instruction
   if (Node->isTargetOpcode()) {
@@ -677,7 +739,7 @@
       for (unsigned i = II.numDefs; i < NumResults; ++i) {
         unsigned Reg = II.ImplicitDefs[i - II.numDefs];
         if (Node->hasAnyUseOfValue(i))
-          EmitCopyFromReg(Node, i, Reg, VRBaseMap);
+          EmitCopyFromReg(Node, i, InstanceNo, Reg, VRBaseMap);
       }
     }
   } else {
@@ -713,7 +775,7 @@
     }
     case ISD::CopyFromReg: {
       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
-      EmitCopyFromReg(Node, 0, SrcReg, VRBaseMap);
+      EmitCopyFromReg(Node, 0, InstanceNo, SrcReg, VRBaseMap);
       break;
     }
     case ISD::INLINEASM: {
@@ -802,9 +864,9 @@
   DenseMap<SDOperand, unsigned> VRBaseMap;
   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     if (SUnit *SU = Sequence[i]) {
-      for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++)
-        EmitNode(SU->FlaggedNodes[j], VRBaseMap);
-      EmitNode(SU->Node, VRBaseMap);
+      for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j)
+        EmitNode(SU->FlaggedNodes[j], SU->InstanceNo, VRBaseMap);
+      EmitNode(SU->Node, SU->InstanceNo, VRBaseMap);
     } else {
       // Null SUnit* is a noop.
       EmitNoop();
@@ -869,7 +931,10 @@
         cerr << "   ch  #";
       else
         cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")\n";
+      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+      if (I->isSpecial)
+        cerr << " *";
+      cerr << "\n";
     }
   }
   if (Succs.size() != 0) {
@@ -880,7 +945,10 @@
         cerr << "   ch  #";
       else
         cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")\n";
+      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+      if (I->isSpecial)
+        cerr << " *";
+      cerr << "\n";
     }
   }
   cerr << "\n";
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index 7b09749..33d7910 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -168,7 +168,7 @@
 /// schedulers.
 void ScheduleDAGList::ListScheduleTopDown() {
   unsigned CurCycle = 0;
-  SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
+  SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
 
   // All leaves to Available queue.
   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
@@ -328,12 +328,24 @@
     LatencyPriorityQueue() : Queue(latency_sort(this)) {
     }
     
-    void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
+    void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
                    std::vector<SUnit> &sunits) {
       SUnits = &sunits;
       // Calculate node priorities.
       CalculatePriorities();
     }
+
+    void addNode(const SUnit *SU) {
+      Latencies.resize(SUnits->size(), -1);
+      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
+      CalcLatency(*SU);
+    }
+
+    void updateNode(const SUnit *SU) {
+      Latencies[SU->NodeNum] = -1;
+      CalcLatency(*SU);
+    }
+
     void releaseState() {
       SUnits = 0;
       Latencies.clear();
@@ -349,6 +361,8 @@
       return NumNodesSolelyBlocking[NodeNum];
     }
     
+    unsigned size() const { return Queue.size(); }
+
     bool empty() const { return Queue.empty(); }
     
     virtual void push(SUnit *U) {
@@ -368,22 +382,10 @@
       return V;
     }
 
-    // ScheduledNode - As nodes are scheduled, we look to see if there are any
-    // successor nodes that have a single unscheduled predecessor.  If so, that
-    // single predecessor has a higher priority, since scheduling it will make
-    // the node available.
-    void ScheduledNode(SUnit *Node);
-
-private:
-    void CalculatePriorities();
-    int CalcLatency(const SUnit &SU);
-    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
-    SUnit *getSingleUnscheduledPred(SUnit *SU);
-
-    /// RemoveFromPriorityQueue - This is a really inefficient way to remove a
-    /// node from a priority queue.  We should roll our own heap to make this
-    /// better or something.
-    void RemoveFromPriorityQueue(SUnit *SU) {
+    /// remove - This is a really inefficient way to remove a node from a
+    /// priority queue.  We should roll our own heap to make this better or
+    /// something.
+    void remove(SUnit *SU) {
       std::vector<SUnit*> Temp;
       
       assert(!Queue.empty() && "Not in queue!");
@@ -400,6 +402,18 @@
       for (unsigned i = 0, e = Temp.size(); i != e; ++i)
         Queue.push(Temp[i]);
     }
+
+    // ScheduledNode - As nodes are scheduled, we look to see if there are any
+    // successor nodes that have a single unscheduled predecessor.  If so, that
+    // single predecessor has a higher priority, since scheduling it will make
+    // the node available.
+    void ScheduledNode(SUnit *Node);
+
+private:
+    void CalculatePriorities();
+    int CalcLatency(const SUnit &SU);
+    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
+    SUnit *getSingleUnscheduledPred(SUnit *SU);
   };
 }
 
@@ -507,7 +521,7 @@
   
   // Okay, we found a single predecessor that is available, but not scheduled.
   // Since it is available, it must be in the priority queue.  First remove it.
-  RemoveFromPriorityQueue(OnlyAvailablePred);
+  remove(OnlyAvailablePred);
 
   // Reinsert the node into the priority queue, which recomputes its
   // NumNodesSolelyBlocking value.
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index ea23c27..0228d8a 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -25,6 +25,7 @@
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include <climits>
 #include <queue>
@@ -52,9 +53,16 @@
   bool isBottomUp;
   
   /// AvailableQueue - The priority queue to use for the available SUnits.
-  ///
+  ///a
   SchedulingPriorityQueue *AvailableQueue;
 
+  /// LiveRegs / LiveRegDefs - A set of physical registers and their definition
+  /// that are "live". These nodes must be scheduled before any other nodes that
+  /// modifies the registers can be scheduled.
+  SmallSet<unsigned, 4> LiveRegs;
+  std::vector<SUnit*> LiveRegDefs;
+  std::vector<unsigned> LiveRegCycles;
+
 public:
   ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb,
                   const TargetMachine &tm, bool isbottomup,
@@ -72,8 +80,13 @@
 private:
   void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
   void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
+  void CapturePred(SUnit *PredSU, SUnit *SU, bool isChain);
   void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
   void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
+  void UnscheduleNodeBottomUp(SUnit *SU);
+  SUnit *BackTrackBottomUp(SUnit*, unsigned, unsigned&, bool&);
+  SUnit *CopyAndMoveSuccessors(SUnit *SU);
+  bool DelayForLiveRegsBottomUp(SUnit *SU, unsigned &CurCycle);
   void ListScheduleTopDown();
   void ListScheduleBottomUp();
   void CommuteNodesToReducePressure();
@@ -84,7 +97,10 @@
 /// Schedule - Schedule the DAG using list scheduling.
 void ScheduleDAGRRList::Schedule() {
   DOUT << "********** List Scheduling **********\n";
-  
+
+  LiveRegDefs.resize(MRI->getNumRegs(), NULL);  
+  LiveRegCycles.resize(MRI->getNumRegs(), 0);
+
   // Build scheduling units.
   BuildSchedUnits();
 
@@ -130,7 +146,7 @@
           continue;
 
         SDNode *OpN = SU->Node->getOperand(j).Val;
-        SUnit *OpSU = SUnitMap[OpN];
+        SUnit *OpSU = SUnitMap[OpN][SU->InstanceNo];
         if (OpSU && OperandSeen.count(OpSU) == 1) {
           // Ok, so SU is not the last use of OpSU, but SU is two-address so
           // it will clobber OpSU. Try to commute SU if no other source operands
@@ -139,7 +155,7 @@
           for (unsigned k = 0; k < NumOps; ++k) {
             if (k != j) {
               OpN = SU->Node->getOperand(k).Val;
-              OpSU = SUnitMap[OpN];
+              OpSU = SUnitMap[OpN][SU->InstanceNo];
               if (OpSU && OperandSeen.count(OpSU) == 1) {
                 DoCommute = false;
                 break;
@@ -178,9 +194,9 @@
   PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
 
   if (!isChain)
-    PredSU->NumSuccsLeft--;
+    --PredSU->NumSuccsLeft;
   else
-    PredSU->NumChainSuccsLeft--;
+    --PredSU->NumChainSuccsLeft;
   
 #ifndef NDEBUG
   if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
@@ -209,19 +225,273 @@
   SU->Cycle = CurCycle;
 
   AvailableQueue->ScheduledNode(SU);
-  Sequence.push_back(SU);
 
   // Bottom up: release predecessors
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
-       I != E; ++I)
+       I != E; ++I) {
     ReleasePred(I->Dep, I->isCtrl, CurCycle);
+    if (I->Cost < 0)  {
+      // 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 (LiveRegs.insert(I->Reg)) {
+        LiveRegDefs[I->Reg] = I->Dep;
+        LiveRegCycles[I->Reg] = CurCycle;
+      }
+    }
+  }
+
+  // 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) {
+        LiveRegs.erase(I->Reg);
+        assert(LiveRegDefs[I->Reg] == SU &&
+               "Physical register dependency violated?");
+        LiveRegDefs[I->Reg] = NULL;
+        LiveRegCycles[I->Reg] = 0;
+      }
+    }
+  }
+
   SU->isScheduled = true;
 }
 
-/// isReady - True if node's lower cycle bound is less or equal to the current
-/// scheduling cycle. Always true if all nodes have uniform latency 1.
-static inline bool isReady(SUnit *SU, unsigned CurCycle) {
-  return SU->CycleBound <= CurCycle;
+/// 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) {
+  PredSU->CycleBound = 0;
+  for (SUnit::succ_iterator I = PredSU->Succs.begin(), E = PredSU->Succs.end();
+       I != E; ++I) {
+    if (I->Dep == SU)
+      continue;
+    PredSU->CycleBound = std::max(PredSU->CycleBound,
+                                  I->Dep->Cycle + PredSU->Latency);
+  }
+
+  if (PredSU->isAvailable) {
+    PredSU->isAvailable = false;
+    if (!PredSU->isPending)
+      AvailableQueue->remove(PredSU);
+  }
+
+  if (!isChain)
+    ++PredSU->NumSuccsLeft;
+  else
+    ++PredSU->NumChainSuccsLeft;
+}
+
+/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
+/// its predecessor states to reflect the change.
+void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
+  DOUT << "*** Unscheduling [" << SU->Cycle << "]: ";
+  DEBUG(SU->dump(&DAG));
+
+  AvailableQueue->UnscheduledNode(SU);
+
+  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])  {
+      LiveRegs.erase(I->Reg);
+      assert(LiveRegDefs[I->Reg] == I->Dep &&
+             "Physical register dependency violated?");
+      LiveRegDefs[I->Reg] = NULL;
+      LiveRegCycles[I->Reg] = 0;
+    }
+  }
+
+  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+       I != E; ++I) {
+    if (I->Cost < 0)  {
+      if (LiveRegs.insert(I->Reg)) {
+        assert(!LiveRegDefs[I->Reg] &&
+               "Physical register dependency violated?");
+        LiveRegDefs[I->Reg] = SU;
+      }
+      if (I->Dep->Cycle < LiveRegCycles[I->Reg])
+        LiveRegCycles[I->Reg] = I->Dep->Cycle;
+    }
+  }
+
+  SU->Cycle = 0;
+  SU->isScheduled = false;
+  SU->isAvailable = true;
+  AvailableQueue->push(SU);
+}
+
+/// BackTrackBottomUp - Back track scheduling to a previous cycle specified in
+/// BTCycle in order to schedule a specific node. Returns the last unscheduled
+/// SUnit. Also returns if a successor is unscheduled in the process.
+SUnit *ScheduleDAGRRList::BackTrackBottomUp(SUnit *SU, unsigned BTCycle,
+                                        unsigned &CurCycle, bool &SuccUnsched) {
+  SuccUnsched = false;
+  SUnit *OldSU = NULL;
+  while (CurCycle > BTCycle) {
+    OldSU = Sequence.back();
+    Sequence.pop_back();
+    if (SU->isSucc(OldSU))
+      SuccUnsched = true;
+    UnscheduleNodeBottomUp(OldSU);
+    --CurCycle;
+  }
+
+      
+  if (SU->isSucc(OldSU)) {
+    assert(false && "Something is wrong!");
+    abort();
+  }
+
+  return OldSU;
+}
+
+/// isSafeToCopy - True if the SUnit for the given SDNode can safely cloned,
+/// i.e. the node does not produce a flag, it does not read a flag and it does
+/// not have an incoming chain.
+static bool isSafeToCopy(SDNode *N) {
+  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
+    if (N->getValueType(i) == MVT::Flag)
+      return false;
+  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
+    const SDOperand &Op = N->getOperand(i);
+    MVT::ValueType VT = Op.Val->getValueType(Op.ResNo);
+    if (VT == MVT::Other || VT == MVT::Flag)
+      return false;
+  }
+
+  return true;
+}
+
+/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
+/// successors to the newly created node.
+SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
+  SUnit *NewSU = Clone(SU);
+
+  // New SUnit has the exact same predecessors.
+  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+       I != E; ++I)
+    if (!I->isSpecial) {
+      NewSU->addPred(I->Dep, I->isCtrl, false, I->Reg, I->Cost);
+      NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1);
+    }
+
+  // Only copy scheduled successors. Cut them from old node's successor
+  // list and move them over.
+  SmallVector<SDep*, 2> DelDeps;
+  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+       I != E; ++I) {
+    if (I->isSpecial)
+      continue;
+    NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1);
+    if (I->Dep->isScheduled) {
+      I->Dep->addPred(NewSU, I->isCtrl, false, I->Reg, I->Cost);
+      DelDeps.push_back(I);
+    }
+  }
+  for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
+    SUnit *Succ = DelDeps[i]->Dep;
+    bool isCtrl = DelDeps[i]->isCtrl;
+    Succ->removePred(SU, isCtrl, false);
+  }
+
+  AvailableQueue->updateNode(SU);
+  AvailableQueue->addNode(NewSU);
+
+  return NewSU;
+}
+
+/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
+/// scheduling of the given node to satisfy live physical register dependencies.
+/// If the specific node is the last one that's available to schedule, do
+/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
+bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, unsigned &CurCycle){
+  if (LiveRegs.empty())
+    return false;
+
+  // If this node would clobber any "live" register, then it's not ready.
+  // However, if this is the last "available" node, then we may have to
+  // backtrack.
+  bool MustSched = AvailableQueue->empty();
+  SmallVector<unsigned, 4> LRegs;
+  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+       I != E; ++I) {
+    if (I->Cost < 0)  {
+      unsigned Reg = I->Reg;
+      if (LiveRegs.count(Reg) && LiveRegDefs[Reg] != I->Dep)
+        LRegs.push_back(Reg);
+      for (const unsigned *Alias = MRI->getAliasSet(Reg);
+           *Alias; ++Alias)
+        if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != I->Dep)
+          LRegs.push_back(*Alias);
+    }
+  }
+
+  for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) {
+    SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1];
+    if (!Node->isTargetOpcode())
+      continue;
+    const TargetInstrDescriptor &TID = TII->get(Node->getTargetOpcode());
+    if (!TID.ImplicitDefs)
+      continue;
+    for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) {
+      if (LiveRegs.count(*Reg) && LiveRegDefs[*Reg] != SU)
+        LRegs.push_back(*Reg);
+      for (const unsigned *Alias = MRI->getAliasSet(*Reg);
+           *Alias; ++Alias)
+        if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != SU)
+          LRegs.push_back(*Alias);
+    }
+  }
+
+  if (MustSched && !LRegs.empty()) {
+    // We have made a mistake by scheduling some nodes too early. Now we must
+    // schedule the current node which will end up clobbering some live
+    // registers that are expensive / impossible to copy. Try unscheduling
+    // up to the point where it's safe to schedule the current node.
+    unsigned LiveCycle = CurCycle;
+    for (unsigned i = 0, e = LRegs.size(); i != e; ++i) {
+      unsigned Reg = LRegs[i];
+      unsigned LCycle = LiveRegCycles[Reg];
+      LiveCycle = std::min(LiveCycle, LCycle);
+    }
+
+    if (SU->CycleBound < LiveCycle)  {
+      bool SuccUnsched = false;
+      SUnit *OldSU = BackTrackBottomUp(SU, LiveCycle, CurCycle, SuccUnsched);
+      // Force the current node to be scheduled before the node that
+      // requires the physical reg dep.
+      if (OldSU->isAvailable) {
+        OldSU->isAvailable = false;
+        AvailableQueue->remove(OldSU);
+      }
+      SU->addPred(OldSU, true, true);
+      // If a successor has been unscheduled, then it's not possible to
+      // schedule the current node.
+      return SuccUnsched;
+    } else {
+      // Try duplicating the nodes that produces these "expensive to copy"
+      // values to break the dependency.
+      for (unsigned i = 0, e = LRegs.size(); i != e; ++i) {
+        unsigned Reg = LRegs[i];
+        SUnit *LRDef = LiveRegDefs[Reg];
+        if (isSafeToCopy(LRDef->Node)) {
+          SUnit *NewDef = CopyAndMoveSuccessors(LRDef);
+          LiveRegDefs[Reg] = NewDef;
+          NewDef->addPred(SU, true, true);
+          SU->isAvailable = false;
+          AvailableQueue->push(NewDef);
+        } else {
+          assert(false && "Expensive copying is required?");
+          abort();
+        }
+      }
+      return true;
+    }
+  }
+  return !LRegs.empty();
 }
 
 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
@@ -229,30 +499,49 @@
 void ScheduleDAGRRList::ListScheduleBottomUp() {
   unsigned CurCycle = 0;
   // Add root to Available queue.
-  AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
+  SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front();
+  RootSU->isAvailable = true;
+  AvailableQueue->push(RootSU);
 
   // While Available queue is not empty, grab the node with the highest
   // priority. If it is not ready put it back.  Schedule the node.
-  std::vector<SUnit*> NotReady;
+  SmallVector<SUnit*, 4> NotReady;
   while (!AvailableQueue->empty()) {
-    SUnit *CurNode = AvailableQueue->pop();
-    while (CurNode && !isReady(CurNode, CurCycle)) {
-      NotReady.push_back(CurNode);
-      CurNode = AvailableQueue->pop();
+    SUnit *CurSU = AvailableQueue->pop();
+    while (CurSU) {
+      if (CurSU->CycleBound <= CurCycle)
+        if (!DelayForLiveRegsBottomUp(CurSU, CurCycle))
+          break;
+
+      // Verify node is still ready. It may not be in case the
+      // scheduler has backtracked.
+      if (CurSU->isAvailable) {
+        CurSU->isPending = true;
+        NotReady.push_back(CurSU);
+      }
+      CurSU = AvailableQueue->pop();
     }
     
     // Add the nodes that aren't ready back onto the available list.
-    AvailableQueue->push_all(NotReady);
+    for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
+      NotReady[i]->isPending = false;
+      if (NotReady[i]->isAvailable)
+        AvailableQueue->push(NotReady[i]);
+    }
     NotReady.clear();
 
-    if (CurNode != NULL)
-      ScheduleNodeBottomUp(CurNode, CurCycle);
-    CurCycle++;
+    if (!CurSU)
+      Sequence.push_back(0);
+    else {
+      ScheduleNodeBottomUp(CurSU, CurCycle);
+      Sequence.push_back(CurSU);
+    }
+    ++CurCycle;
   }
 
   // Add entry node last
   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
-    SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
+    SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
     Sequence.push_back(Entry);
   }
 
@@ -291,9 +580,9 @@
   SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency);
 
   if (!isChain)
-    SuccSU->NumPredsLeft--;
+    --SuccSU->NumPredsLeft;
   else
-    SuccSU->NumChainPredsLeft--;
+    --SuccSU->NumChainPredsLeft;
   
 #ifndef NDEBUG
   if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
@@ -320,7 +609,6 @@
   SU->Cycle = CurCycle;
 
   AvailableQueue->ScheduledNode(SU);
-  Sequence.push_back(SU);
 
   // Top down: release successors
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
@@ -333,7 +621,7 @@
 /// schedulers.
 void ScheduleDAGRRList::ListScheduleTopDown() {
   unsigned CurCycle = 0;
-  SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
+  SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
 
   // All leaves to Available queue.
   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
@@ -346,24 +634,29 @@
   
   // Emit the entry node first.
   ScheduleNodeTopDown(Entry, CurCycle);
-  CurCycle++;
+  Sequence.push_back(Entry);
+  ++CurCycle;
 
   // While Available queue is not empty, grab the node with the highest
   // priority. If it is not ready put it back.  Schedule the node.
   std::vector<SUnit*> NotReady;
   while (!AvailableQueue->empty()) {
-    SUnit *CurNode = AvailableQueue->pop();
-    while (CurNode && !isReady(CurNode, CurCycle)) {
-      NotReady.push_back(CurNode);
-      CurNode = AvailableQueue->pop();
+    SUnit *CurSU = AvailableQueue->pop();
+    while (CurSU && CurSU->CycleBound > CurCycle) {
+      NotReady.push_back(CurSU);
+      CurSU = AvailableQueue->pop();
     }
     
     // Add the nodes that aren't ready back onto the available list.
     AvailableQueue->push_all(NotReady);
     NotReady.clear();
 
-    if (CurNode != NULL)
-      ScheduleNodeTopDown(CurNode, CurCycle);
+    if (!CurSU)
+      Sequence.push_back(0);
+    else {
+      ScheduleNodeTopDown(CurSU, CurCycle);
+      Sequence.push_back(CurSU);
+    }
     CurCycle++;
   }
   
@@ -431,14 +724,21 @@
     RegReductionPriorityQueue() :
     Queue(SF(this)) {}
     
-    virtual void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
+    virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
                            std::vector<SUnit> &sunits) {}
+
+    virtual void addNode(const SUnit *SU) {}
+
+    virtual void updateNode(const SUnit *SU) {}
+
     virtual void releaseState() {}
     
     virtual unsigned getNodePriority(const SUnit *SU) const {
       return 0;
     }
     
+    unsigned size() const { return Queue.size(); }
+
     bool empty() const { return Queue.empty(); }
     
     void push(SUnit *U) {
@@ -456,16 +756,33 @@
       return V;
     }
 
-    virtual bool isDUOperand(const SUnit *SU1, const SUnit *SU2) {
-      return false;
+    /// remove - This is a really inefficient way to remove a node from a
+    /// priority queue.  We should roll our own heap to make this better or
+    /// something.
+    void remove(SUnit *SU) {
+      std::vector<SUnit*> Temp;
+      
+      assert(!Queue.empty() && "Not in queue!");
+      while (Queue.top() != SU) {
+        Temp.push_back(Queue.top());
+        Queue.pop();
+        assert(!Queue.empty() && "Not in queue!");
+      }
+
+      // Remove the node from the PQ.
+      Queue.pop();
+      
+      // Add all the other nodes back.
+      for (unsigned i = 0, e = Temp.size(); i != e; ++i)
+        Queue.push(Temp[i]);
     }
   };
 
   template<class SF>
   class VISIBILITY_HIDDEN BURegReductionPriorityQueue
    : public RegReductionPriorityQueue<SF> {
-    // SUnitMap SDNode to SUnit mapping (n -> 1).
-    DenseMap<SDNode*, SUnit*> *SUnitMap;
+    // SUnitMap SDNode to SUnit mapping (n -> n).
+    DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
 
     // SUnits - The SUnits for the current graph.
     const std::vector<SUnit> *SUnits;
@@ -478,7 +795,7 @@
     explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii)
       : TII(tii) {}
 
-    void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
+    void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
                    std::vector<SUnit> &sunits) {
       SUnitMap = &sumap;
       SUnits = &sunits;
@@ -488,6 +805,16 @@
       CalculateSethiUllmanNumbers();
     }
 
+    void addNode(const SUnit *SU) {
+      SethiUllmanNumbers.resize(SUnits->size(), 0);
+      CalcNodeSethiUllmanNumber(SU);
+    }
+
+    void updateNode(const SUnit *SU) {
+      SethiUllmanNumbers[SU->NodeNum] = 0;
+      CalcNodeSethiUllmanNumber(SU);
+    }
+
     void releaseState() {
       SUnits = 0;
       SethiUllmanNumbers.clear();
@@ -519,18 +846,6 @@
         return SethiUllmanNumbers[SU->NodeNum];
     }
 
-    bool isDUOperand(const SUnit *SU1, const SUnit *SU2) {
-      unsigned Opc = SU1->Node->getTargetOpcode();
-      unsigned NumRes = TII->getNumDefs(Opc);
-      unsigned NumOps = ScheduleDAG::CountOperands(SU1->Node);
-      for (unsigned i = 0; i != NumOps; ++i) {
-        if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) == -1)
-          continue;
-        if (SU1->Node->getOperand(i).isOperand(SU2->Node))
-          return true;
-      }
-      return false;
-    }
   private:
     bool canClobber(SUnit *SU, SUnit *Op);
     void AddPseudoTwoAddrDeps();
@@ -542,8 +857,8 @@
   template<class SF>
   class VISIBILITY_HIDDEN TDRegReductionPriorityQueue
    : public RegReductionPriorityQueue<SF> {
-    // SUnitMap SDNode to SUnit mapping (n -> 1).
-    DenseMap<SDNode*, SUnit*> *SUnitMap;
+    // SUnitMap SDNode to SUnit mapping (n -> n).
+    DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap;
 
     // SUnits - The SUnits for the current graph.
     const std::vector<SUnit> *SUnits;
@@ -554,7 +869,7 @@
   public:
     TDRegReductionPriorityQueue() {}
 
-    void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
+    void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
                    std::vector<SUnit> &sunits) {
       SUnitMap = &sumap;
       SUnits = &sunits;
@@ -562,6 +877,16 @@
       CalculateSethiUllmanNumbers();
     }
 
+    void addNode(const SUnit *SU) {
+      SethiUllmanNumbers.resize(SUnits->size(), 0);
+      CalcNodeSethiUllmanNumber(SU);
+    }
+
+    void updateNode(const SUnit *SU) {
+      SethiUllmanNumbers[SU->NodeNum] = 0;
+      CalcNodeSethiUllmanNumber(SU);
+    }
+
     void releaseState() {
       SUnits = 0;
       SethiUllmanNumbers.clear();
@@ -710,7 +1035,7 @@
     for (unsigned i = 0; i != NumOps; ++i) {
       if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) != -1) {
         SDNode *DU = SU->Node->getOperand(i).Val;
-        if (Op == (*SUnitMap)[DU])
+        if (Op == (*SUnitMap)[DU][SU->InstanceNo])
           return true;
       }
     }
@@ -740,23 +1065,25 @@
     for (unsigned j = 0; j != NumOps; ++j) {
       if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) != -1) {
         SDNode *DU = SU->Node->getOperand(j).Val;
-        SUnit *DUSU = (*SUnitMap)[DU];
+        SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo];
         if (!DUSU) continue;
         for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
              I != E; ++I) {
           if (I->isCtrl) continue;
           SUnit *SuccSU = I->Dep;
-          if (SuccSU != SU &&
-              (!canClobber(SuccSU, DUSU) ||
-               (!SU->isCommutable && SuccSU->isCommutable))){
-            if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) {
-              DOUT << "Adding an edge from SU # " << SU->NodeNum
-                   << " to SU #" << SuccSU->NodeNum << "\n";
-              if (SU->addPred(SuccSU, true))
-                SU->NumChainPredsLeft++;
-              if (SuccSU->addSucc(SU, true))
-                SuccSU->NumChainSuccsLeft++;
-            }
+          // Don't constraint nodes with implicit defs. It can create cycles
+          // plus it may increase register pressures.
+          if (SuccSU == SU || SuccSU->hasImplicitDefs)
+            continue;
+          // Be conservative. Ignore if nodes aren't at the same depth.
+          if (SuccSU->Depth != SU->Depth)
+            continue;
+          if ((!canClobber(SuccSU, DUSU) ||
+               (!SU->isCommutable && SuccSU->isCommutable)) &&
+              !isReachable(SuccSU, SU)) {
+            DOUT << "Adding an edge from SU # " << SU->NodeNum
+                 << " to SU #" << SuccSU->NodeNum << "\n";
+            SU->addPred(SuccSU, true, true);
           }
         }
       }
@@ -783,7 +1110,7 @@
       SethiUllmanNumber = PredSethiUllman;
       Extra = 0;
     } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
-      Extra++;
+      ++Extra;
   }
 
   SethiUllmanNumber += Extra;
@@ -813,7 +1140,7 @@
          EE = SuccSU->Preds.end(); II != EE; ++II) {
       SUnit *PredSU = II->Dep;
       if (!PredSU->isScheduled)
-        Sum++;
+        ++Sum;
     }
   }
 
@@ -906,7 +1233,7 @@
         SethiUllmanNumber = PredSethiUllman;
         Extra = 0;
       } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl)
-        Extra++;
+        ++Extra;
     }
 
     SethiUllmanNumber += Extra;
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp
index 6014fe9..286ef1f 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp
@@ -697,9 +697,9 @@
     NodeInfo *NI = Ordering[i];
     if (NI->isInGroup()) {
       NodeGroupIterator NGI(Ordering[i]);
-      while (NodeInfo *NI = NGI.next()) EmitNode(NI->Node, VRBaseMap);
+      while (NodeInfo *NI = NGI.next()) EmitNode(NI->Node, 0, VRBaseMap);
     } else {
-      EmitNode(NI->Node, VRBaseMap);
+      EmitNode(NI->Node, 0, VRBaseMap);
     }
   }
 }
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
index 73902b8..734d0f2 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGPrinter.cpp
@@ -281,7 +281,7 @@
                                        GraphWriter<ScheduleDAG*> &GW) {
       GW.emitSimpleNode(0, "plaintext=circle", "GraphRoot");
       if (G->DAG.getRoot().Val)
-        GW.emitEdge(0, -1, G->SUnitMap[G->DAG.getRoot().Val], -1, "");
+        GW.emitEdge(0, -1, G->SUnitMap[G->DAG.getRoot().Val].front(), -1, "");
     }
   };
 }