diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index e24a294..9f44c6a 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -78,7 +78,7 @@
     void AddUsersToWorkList(SDNode *N) {
       for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
            UI != UE; ++UI)
-        AddToWorkList(*UI);
+        AddToWorkList(UI->getUser());
     }
 
     /// visit - call the node-specific routine that knows how to fold each
@@ -2704,7 +2704,7 @@
   bool isTruncFree = TLI.isTruncateFree(N->getValueType(0), N0.getValueType());
   for (SDNode::use_iterator UI = N0.Val->use_begin(), UE = N0.Val->use_end();
        UI != UE; ++UI) {
-    SDNode *User = *UI;
+    SDNode *User = UI->getUser();
     if (User == N)
       continue;
     // FIXME: Only extend SETCC N, N and SETCC N, c for now.
@@ -2743,7 +2743,7 @@
     bool BothLiveOut = false;
     for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
          UI != UE; ++UI) {
-      SDNode *User = *UI;
+      SDNode *User = UI->getUser();
       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
         SDOperand UseOp = User->getOperand(i);
         if (UseOp.Val == N && UseOp.ResNo == 0) {
@@ -3880,7 +3880,7 @@
   MVT::ValueType VT = N->getValueType(0);
   
   // If this is fp_round(fpextend), don't fold it, allow ourselves to be folded.
-  if (N->hasOneUse() && (*N->use_begin())->getOpcode() == ISD::FP_ROUND)
+  if (N->hasOneUse() && (N->use_begin())->getOpcode() == ISD::FP_ROUND)
     return SDOperand();
 
   // fold (fp_extend c1fp) -> c1fp
@@ -4101,7 +4101,7 @@
   bool RealUse = false;
   for (SDNode::use_iterator I = Ptr.Val->use_begin(),
          E = Ptr.Val->use_end(); I != E; ++I) {
-    SDNode *Use = *I;
+    SDNode *Use = I->getUser();
     if (Use == N)
       continue;
     if (Use->isPredecessorOf(N))
@@ -4186,7 +4186,7 @@
   
   for (SDNode::use_iterator I = Ptr.Val->use_begin(),
          E = Ptr.Val->use_end(); I != E; ++I) {
-    SDNode *Op = *I;
+    SDNode *Op = I->getUser();
     if (Op == N ||
         (Op->getOpcode() != ISD::ADD && Op->getOpcode() != ISD::SUB))
       continue;
@@ -4214,7 +4214,7 @@
       bool TryNext = false;
       for (SDNode::use_iterator II = BasePtr.Val->use_begin(),
              EE = BasePtr.Val->use_end(); II != EE; ++II) {
-        SDNode *Use = *II;
+        SDNode *Use = II->getUser();
         if (Use == Ptr.Val)
           continue;
 
@@ -4224,7 +4224,7 @@
           bool RealUse = false;
           for (SDNode::use_iterator III = Use->use_begin(),
                  EEE = Use->use_end(); III != EEE; ++III) {
-            SDNode *UseUse = *III;
+            SDNode *UseUse = III->getUser();
             if (!((UseUse->getOpcode() == ISD::LOAD &&
                    cast<LoadSDNode>(UseUse)->getBasePtr().Val == Use) ||
                   (UseUse->getOpcode() == ISD::STORE &&
diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index d318cb4..0d629db 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -85,17 +85,17 @@
   /// LegalizedNodes - For nodes that are of legal width, and that have more
   /// than one use, this map indicates what regularized operand to use.  This
   /// allows us to avoid legalizing the same thing more than once.
-  DenseMap<SDOperand, SDOperand> LegalizedNodes;
+  DenseMap<SDOperandImpl, SDOperand> LegalizedNodes;
 
   /// PromotedNodes - For nodes that are below legal width, and that have more
   /// than one use, this map indicates what promoted value to use.  This allows
   /// us to avoid promoting the same thing more than once.
-  DenseMap<SDOperand, SDOperand> PromotedNodes;
+  DenseMap<SDOperandImpl, SDOperand> PromotedNodes;
 
   /// ExpandedNodes - For nodes that need to be expanded this map indicates
   /// which which operands are the expanded version of the input.  This allows
   /// us to avoid expanding the same node more than once.
-  DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
+  DenseMap<SDOperandImpl, std::pair<SDOperand, SDOperand> > ExpandedNodes;
 
   /// SplitNodes - For vector nodes that need to be split, this map indicates
   /// which which operands are the split version of the input.  This allows us
@@ -308,7 +308,7 @@
     // are now done.
     for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
          UI != E; ++UI)
-      Worklist.push_back(*UI);
+      Worklist.push_back(UI->getUser());
   }
 
   assert(Order.size() == Visited.size() &&
@@ -381,7 +381,7 @@
        E = Node->use_end(); UI != E; ++UI) {
     
     // Make sure to only follow users of our token chain.
-    SDNode *User = *UI;
+    SDNode *User = UI->getUser();
     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
       if (User->getOperand(i) == TheChain)
         if (SDNode *Result = FindCallEndFromCallStart(User))
@@ -783,7 +783,7 @@
 
   // Note that LegalizeOp may be reentered even from single-use nodes, which
   // means that we always must cache transformed nodes.
-  DenseMap<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
+  DenseMap<SDOperandImpl, SDOperand>::iterator I = LegalizedNodes.find(Op);
   if (I != LegalizedNodes.end()) return I->second;
 
   SDOperand Tmp1, Tmp2, Tmp3, Tmp4;
@@ -1599,7 +1599,7 @@
     // will cause this node to be legalized as well as handling libcalls right.
     if (LastCALLSEQ_END.Val != Node) {
       LegalizeOp(SDOperand(FindCallStartFromCallEnd(Node), 0));
-      DenseMap<SDOperand, SDOperand>::iterator I = LegalizedNodes.find(Op);
+      DenseMap<SDOperandImpl, SDOperand>::iterator I = LegalizedNodes.find(Op);
       assert(I != LegalizedNodes.end() &&
              "Legalizing the call start should have legalized this node!");
       return I->second;
@@ -4136,7 +4136,7 @@
   SDOperand Result;
   SDNode *Node = Op.Val;
 
-  DenseMap<SDOperand, SDOperand>::iterator I = PromotedNodes.find(Op);
+  DenseMap<SDOperandImpl, SDOperand>::iterator I = PromotedNodes.find(Op);
   if (I != PromotedNodes.end()) return I->second;
 
   switch (Node->getOpcode()) {
@@ -5833,7 +5833,7 @@
          "Cannot expand to FP value or to larger int value!");
 
   // See if we already expanded it.
-  DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator I
+  DenseMap<SDOperandImpl, std::pair<SDOperand, SDOperand> >::iterator I
     = ExpandedNodes.find(Op);
   if (I != ExpandedNodes.end()) {
     Lo = I->second.first;
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
index cc9caf0..6511cff 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
@@ -137,7 +137,7 @@
     
     for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
          UI != E; ++UI) {
-      SDNode *User = *UI;
+      SDNode *User = UI->getUser();
       int NodeID = User->getNodeId();
       assert(NodeID != ReadyToProcess && NodeID != Processed &&
              "Invalid node id for user of unprocessed node!");
@@ -344,7 +344,7 @@
 /// RemapNode - If the specified value was already legalized to another value,
 /// replace it by that value.
 void DAGTypeLegalizer::RemapNode(SDOperand &N) {
-  DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.find(N);
+  DenseMap<SDOperandImpl, SDOperand>::iterator I = ReplacedNodes.find(N);
   if (I != ReplacedNodes.end()) {
     // Use path compression to speed up future lookups if values get multiply
     // replaced with other values.
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.h b/lib/CodeGen/SelectionDAG/LegalizeTypes.h
index b8047bc..48d4b39 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.h
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.h
@@ -110,27 +110,27 @@
 
   /// PromotedNodes - For nodes that are below legal width, this map indicates
   /// what promoted value to use.
-  DenseMap<SDOperand, SDOperand> PromotedNodes;
+  DenseMap<SDOperandImpl, SDOperand> PromotedNodes;
   
   /// ExpandedNodes - For nodes that need to be expanded this map indicates
   /// which operands are the expanded version of the input.
-  DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > ExpandedNodes;
+  DenseMap<SDOperandImpl, std::pair<SDOperand, SDOperand> > ExpandedNodes;
 
   /// FloatToIntedNodes - For floating point nodes converted to integers of
   /// the same size, this map indicates the converted value to use.
-  DenseMap<SDOperand, SDOperand> FloatToIntedNodes;
+  DenseMap<SDOperandImpl, SDOperand> FloatToIntedNodes;
 
   /// ScalarizedNodes - For nodes that are <1 x ty>, this map indicates the
   /// scalar value of type 'ty' to use.
-  DenseMap<SDOperand, SDOperand> ScalarizedNodes;
+  DenseMap<SDOperandImpl, SDOperand> ScalarizedNodes;
 
   /// SplitNodes - For nodes that need to be split this map indicates
   /// which operands are the expanded version of the input.
-  DenseMap<SDOperand, std::pair<SDOperand, SDOperand> > SplitNodes;
+  DenseMap<SDOperandImpl, std::pair<SDOperand, SDOperand> > SplitNodes;
   
   /// ReplacedNodes - For nodes that have been replaced with another,
   /// indicates the replacement node to use.
-  DenseMap<SDOperand, SDOperand> ReplacedNodes;
+  DenseMap<SDOperandImpl, SDOperand> ReplacedNodes;
 
   /// Worklist - This defines a worklist of nodes to process.  In order to be
   /// pushed onto this worklist, all operands of a node must have already been
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 048ee2c..da83132 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -135,11 +135,11 @@
       bool HasFlagUse = false;
       for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); 
            UI != E; ++UI)
-        if (FlagVal.isOperandOf(*UI)) {
+        if (FlagVal.isOperandOf(UI->getUser())) {
           HasFlagUse = true;
           NodeSUnit->FlaggedNodes.push_back(N);
           SUnitMap[N].push_back(NodeSUnit);
-          N = *UI;
+          N = UI->getUser();
           break;
         }
       if (!HasFlagUse) break;
@@ -398,7 +398,7 @@
 
 void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
                                   unsigned InstanceNo, unsigned SrcReg,
-                                  DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                                  DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
     // Just use the input register directly!
@@ -414,7 +414,7 @@
   bool MatchReg = true;
   for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
        UI != E; ++UI) {
-    SDNode *Use = *UI;
+    SDNode *Use = UI->getUser();
     bool Match = true;
     if (Use->getOpcode() == ISD::CopyToReg && 
         Use->getOperand(2).Val == Node &&
@@ -469,7 +469,7 @@
 
 void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
                                          const TargetInstrDesc &II,
-                                     DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                                     DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   for (unsigned i = 0; i < II.getNumDefs(); ++i) {
     // If the specific node value is only used by a CopyToReg and the dest reg
     // is a vreg, use the CopyToReg'd destination register instead of creating
@@ -477,7 +477,7 @@
     unsigned VRBase = 0;
     for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
          UI != E; ++UI) {
-      SDNode *Use = *UI;
+      SDNode *Use = UI->getUser();
       if (Use->getOpcode() == ISD::CopyToReg && 
           Use->getOperand(2).Val == Node &&
           Use->getOperand(2).ResNo == i) {
@@ -512,8 +512,8 @@
 
 /// getVR - Return the virtual register corresponding to the specified result
 /// of the specified node.
-static unsigned getVR(SDOperand Op, DenseMap<SDOperand, unsigned> &VRBaseMap) {
-  DenseMap<SDOperand, unsigned>::iterator I = VRBaseMap.find(Op);
+static unsigned getVR(SDOperand Op, DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
+  DenseMap<SDOperandImpl, unsigned>::iterator I = VRBaseMap.find(Op);
   assert(I != VRBaseMap.end() && "Node emitted out of order - late");
   return I->second;
 }
@@ -526,7 +526,7 @@
 void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op,
                              unsigned IIOpNum,
                              const TargetInstrDesc *II,
-                             DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                             DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   if (Op.isTargetOpcode()) {
     // Note that this case is redundant with the final else block, but we
     // include it because it is the most common and it makes the logic
@@ -658,7 +658,7 @@
 /// EmitSubregNode - Generate machine code for subreg nodes.
 ///
 void ScheduleDAG::EmitSubregNode(SDNode *Node, 
-                           DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                           DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
   unsigned Opc = Node->getTargetOpcode();
   
@@ -666,7 +666,7 @@
   // the CopyToReg'd destination register instead of creating a new vreg.
   for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
        UI != E; ++UI) {
-    SDNode *Use = *UI;
+    SDNode *Use = UI->getUser();
     if (Use->getOpcode() == ISD::CopyToReg && 
         Use->getOperand(2).Val == Node) {
       unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
@@ -750,7 +750,7 @@
 /// EmitNode - Generate machine code for an node and needed dependencies.
 ///
 void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
-                           DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                           DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   // If machine instruction
   if (Node->isTargetOpcode()) {
     unsigned Opc = Node->getTargetOpcode();
@@ -1067,7 +1067,7 @@
   }
 
   // Finally, emit the code for all of the scheduled instructions.
-  DenseMap<SDOperand, unsigned> VRBaseMap;
+  DenseMap<SDOperandImpl, unsigned> VRBaseMap;
   DenseMap<SUnit*, unsigned> CopyVRBaseMap;
   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     if (SUnit *SU = Sequence[i]) {
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index ed564b2..b01b525 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -10,7 +10,6 @@
 // This implements the SelectionDAG class.
 //
 //===----------------------------------------------------------------------===//
-
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/Constants.h"
 #include "llvm/GlobalAlias.h"
@@ -465,14 +464,15 @@
     // no cycles in the graph.
     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
       SDNode *Operand = I->Val;
-      Operand->removeUser(N);
+      Operand->removeUser(std::distance(N->op_begin(), I), N);
       
       // Now that we removed this operand, see if there are no uses of it left.
       if (Operand->use_empty())
         DeadNodes.push_back(Operand);
     }
-    if (N->OperandsNeedDelete)
+    if (N->OperandsNeedDelete) {
       delete[] N->OperandList;
+    }
     N->OperandList = 0;
     N->NumOperands = 0;
     
@@ -504,14 +504,15 @@
     // no cycles in the graph.
     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
       SDNode *Operand = I->Val;
-      Operand->removeUser(N);
+      Operand->removeUser(std::distance(N->op_begin(), I), N);
       
       // Now that we removed this operand, see if there are no uses of it left.
       if (Operand->use_empty())
         DeadNodes.push_back(Operand);
     }
-    if (N->OperandsNeedDelete)
+    if (N->OperandsNeedDelete) {
       delete[] N->OperandList;
+    }
     N->OperandList = 0;
     N->NumOperands = 0;
     
@@ -538,9 +539,10 @@
     
   // Drop all of the operands and decrement used nodes use counts.
   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
-    I->Val->removeUser(N);
-  if (N->OperandsNeedDelete)
+    I->Val->removeUser(std::distance(N->op_begin(), I), N);
+  if (N->OperandsNeedDelete) {
     delete[] N->OperandList;
+  }
   N->OperandList = 0;
   N->NumOperands = 0;
   
@@ -701,8 +703,9 @@
   while (!AllNodes.empty()) {
     SDNode *N = AllNodes.begin();
     N->SetNextInBucket(0);
-    if (N->OperandsNeedDelete)
+    if (N->OperandsNeedDelete) {
       delete [] N->OperandList;
+    }
     N->OperandList = 0;
     N->NumOperands = 0;
     AllNodes.pop_front();
@@ -2920,9 +2923,10 @@
     RemoveNodeFromCSEMaps(N);
   
   // Now we update the operands.
-  N->OperandList[0].Val->removeUser(N);
-  Op.Val->addUser(N);
+  N->OperandList[0].Val->removeUser(0, N);
   N->OperandList[0] = Op;
+  N->OperandList[0].setUser(N);
+  Op.Val->addUser(0, N);
   
   // If this gets put into a CSE map, add it.
   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
@@ -2949,14 +2953,16 @@
   
   // Now we update the operands.
   if (N->OperandList[0] != Op1) {
-    N->OperandList[0].Val->removeUser(N);
-    Op1.Val->addUser(N);
+    N->OperandList[0].Val->removeUser(0, N);
     N->OperandList[0] = Op1;
+    N->OperandList[0].setUser(N);
+    Op1.Val->addUser(0, N);
   }
   if (N->OperandList[1] != Op2) {
-    N->OperandList[1].Val->removeUser(N);
-    Op2.Val->addUser(N);
+    N->OperandList[1].Val->removeUser(1, N);
     N->OperandList[1] = Op2;
+    N->OperandList[1].setUser(N);
+    Op2.Val->addUser(1, N);
   }
   
   // If this gets put into a CSE map, add it.
@@ -2984,7 +2990,6 @@
   return UpdateNodeOperands(N, Ops, 5);
 }
 
-
 SDOperand SelectionDAG::
 UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
   SDNode *N = InN.Val;
@@ -3015,9 +3020,10 @@
   // Now we update the operands.
   for (unsigned i = 0; i != NumOps; ++i) {
     if (N->OperandList[i] != Ops[i]) {
-      N->OperandList[i].Val->removeUser(N);
-      Ops[i].Val->addUser(N);
+      N->OperandList[i].Val->removeUser(i, N);
       N->OperandList[i] = Ops[i];
+      N->OperandList[i].setUser(N);
+      Ops[i].Val->addUser(i, N);
     }
   }
 
@@ -3026,7 +3032,6 @@
   return InN;
 }
 
-
 /// MorphNodeTo - This frees the operands of the current node, resets the
 /// opcode, types, and operands to the specified value.  This should only be
 /// used by the SelectionDAG class.
@@ -3039,13 +3044,14 @@
   // Clear the operands list, updating used nodes to remove this from their
   // use list.
   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
-    I->Val->removeUser(this);
+    I->Val->removeUser(std::distance(op_begin(), I), this);
   
   // If NumOps is larger than the # of operands we currently have, reallocate
   // the operand list.
   if (NumOps > NumOperands) {
-    if (OperandsNeedDelete)
+    if (OperandsNeedDelete) {
       delete [] OperandList;
+    }
     OperandList = new SDOperand[NumOps];
     OperandsNeedDelete = true;
   }
@@ -3055,8 +3061,10 @@
   
   for (unsigned i = 0, e = NumOps; i != e; ++i) {
     OperandList[i] = Ops[i];
+    OperandList[i].setUser(this);
     SDNode *N = OperandList[i].Val;
-    N->Uses.push_back(this);
+    N->addUser(i, this);
+    ++N->UsesSize;
   }
 }
 
@@ -3324,21 +3332,27 @@
   assert(From->getNumValues() == 1 && FromN.ResNo == 0 && 
          "Cannot replace with this method!");
   assert(From != To.Val && "Cannot replace uses of with self");
-  
+
+  SmallSetVector<SDNode*, 16> Users;
   while (!From->use_empty()) {
-    // Process users until they are all gone.
-    SDNode *U = *From->use_begin();
-    
+    SDNode::use_iterator UI = From->use_begin();
+    SDNode *U = UI->getUser();
+
+    // Remember that this node is about to morph.
+    if (Users.count(U)) 
+      continue;
+    Users.insert(U);
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(U);
-    
-    for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
-         I != E; ++I)
+    int operandNum = 0;
+    for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
+         I != E; ++I, ++operandNum)
       if (I->Val == From) {
-        From->removeUser(U);
+        From->removeUser(operandNum, U);
         *I = To;
-        To.Val->addUser(U);
-      }
+        I->setUser(U);
+        To.Val->addUser(operandNum, U);
+      }    
 
     // Now that we have modified U, add it back to the CSE maps.  If it already
     // exists there, recursively merge the results together.
@@ -3372,21 +3386,26 @@
     return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
                               UpdateListener);
   
+  SmallSetVector<SDNode*, 16> Users;
   while (!From->use_empty()) {
-    // Process users until they are all gone.
-    SDNode *U = *From->use_begin();
-    
+    SDNode::use_iterator UI = From->use_begin();
+    SDNode *U = UI->getUser();
+
+    // Remember that this node is about to morph.
+    if (Users.count(U)) 
+      continue;
+    Users.insert(U);
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(U);
-    
-    for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
-         I != E; ++I)
+    int operandNum = 0;
+    for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
+         I != E; ++I, ++operandNum)
       if (I->Val == From) {
-        From->removeUser(U);
+        From->removeUser(operandNum, U);
         I->Val = To;
-        To->addUser(U);
+        To->addUser(operandNum, U);
       }
-        
+
     // Now that we have modified U, add it back to the CSE maps.  If it already
     // exists there, recursively merge the results together.
     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
@@ -3415,22 +3434,28 @@
   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
     return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
 
+  SmallSetVector<SDNode*, 16> Users;
   while (!From->use_empty()) {
-    // Process users until they are all gone.
-    SDNode *U = *From->use_begin();
-    
+    SDNode::use_iterator UI = From->use_begin();
+    SDNode *U = UI->getUser();
+
+    // Remember that this node is about to morph.
+    if (Users.count(U)) 
+      continue;
+    Users.insert(U);
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(U);
-    
-    for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
-         I != E; ++I)
+    int operandNum = 0;
+    for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
+         I != E; ++I, ++operandNum)
       if (I->Val == From) {
         const SDOperand &ToOp = To[I->ResNo];
-        From->removeUser(U);
+        From->removeUser(operandNum, U);
         *I = ToOp;
-        ToOp.Val->addUser(U);
+        I->setUser(U);
+        ToOp.Val->addUser(operandNum, U);
       }
-        
+
     // Now that we have modified U, add it back to the CSE maps.  If it already
     // exists there, recursively merge the results together.
     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
@@ -3460,7 +3485,7 @@
     ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
                               SelectionDAG::DAGUpdateListener *chain)
       : Set(set), Chain(chain) {}
-    
+ 
     virtual void NodeDeleted(SDNode *N) {
       Set.remove(N);
       if (Chain) Chain->NodeDeleted(N);
@@ -3488,7 +3513,13 @@
 
   // Get all of the users of From.Val.  We want these in a nice,
   // deterministically ordered and uniqued set, so we use a SmallSetVector.
-  SmallSetVector<SDNode*, 16> Users(From.Val->use_begin(), From.Val->use_end());
+  SmallSetVector<SDNode*, 16> Users;
+  for (SDNode::use_iterator UI = From.Val->use_begin(), 
+      E = From.Val->use_end(); UI != E; ++UI) {
+    SDNode *User = UI->getUser();
+    if (!Users.count(User))
+    Users.insert(User);
+  }
 
   // When one of the recursive merges deletes nodes from the graph, we need to
   // make sure that UpdateListener is notified *and* that the node is removed
@@ -3502,7 +3533,7 @@
     Users.pop_back();
     
     // Scan for an operand that matches From.
-    SDOperand *Op = User->OperandList, *E = User->OperandList+User->NumOperands;
+    SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
     for (; Op != E; ++Op)
       if (*Op == From) break;
     
@@ -3516,9 +3547,10 @@
     // Update all operands that match "From" in case there are multiple uses.
     for (; Op != E; ++Op) {
       if (*Op == From) {
-        From.Val->removeUser(User);
-        *Op = To;
-        To.Val->addUser(User);
+        From.Val->removeUser(Op-User->op_begin(), User);
+	*Op = To;
+        Op->setUser(User);
+        To.Val->addUser(Op-User->op_begin(), User);
       }
     }
                
@@ -3698,16 +3730,13 @@
 
   SmallPtrSet<SDNode*, 32> UsersHandled;
 
-  for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) {
-    SDNode *User = *UI;
-    if (User->getNumOperands() == 1 ||
-        UsersHandled.insert(User))     // First time we've seen this?
-      for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
-        if (User->getOperand(i) == TheValue) {
-          if (NUses == 0)
-            return false;   // too many uses
-          --NUses;
-        }
+  // TODO: Only iterate over uses of a given value of the node
+	for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
+	  if (*UI == TheValue) {
+	    if (NUses == 0)
+	      return false;
+      --NUses;
+    }
   }
 
   // Found exactly the right number of uses?
@@ -3726,8 +3755,8 @@
 
   SmallPtrSet<SDNode*, 32> UsersHandled;
 
-  for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) {
-    SDNode *User = *UI;
+  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
+    SDNode *User = UI->getUser();
     if (User->getNumOperands() == 1 ||
         UsersHandled.insert(User))     // First time we've seen this?
       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
@@ -3745,7 +3774,7 @@
 bool SDNode::isOnlyUseOf(SDNode *N) const {
   bool Seen = false;
   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
-    SDNode *User = *I;
+    SDNode *User = I->getUser();
     if (User == this)
       Seen = true;
     else
@@ -3757,7 +3786,7 @@
 
 /// isOperand - Return true if this node is an operand of N.
 ///
-bool SDOperand::isOperandOf(SDNode *N) const {
+bool SDOperandImpl::isOperandOf(SDNode *N) const {
   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
     if (*this == N->getOperand(i))
       return true;
@@ -3776,7 +3805,7 @@
 /// side-effecting instructions.  In practice, this looks through token
 /// factors and non-volatile loads.  In order to remain efficient, this only
 /// looks a couple of nodes in, it does not do an exhaustive search.
-bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest, 
+bool SDOperandImpl::reachesChainWithoutSideEffects(SDOperandImpl Dest, 
                                                unsigned Depth) const {
   if (*this == Dest) return true;