Use a linked data structure for the uses lists of an SDNode, just like

LLVM Value/Use does and MachineRegisterInfo/MachineOperand does.
This allows constant time for all uses list maintenance operations.

The idea was suggested by Chris. Reviewed by Evan and Dan.
Patch is tested and approved by Dan.

On normal use-cases compilation speed is not affected. On very big basic
blocks there are compilation speedups in the range of 15-20% or even better. 



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

6 files changed, 137 insertions, 108 deletions

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 @@ namespace {
     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 @@ static bool ExtendUsesToFormExtLoad(SDNode *N, SDOperand N0,
   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 @@ static bool ExtendUsesToFormExtLoad(SDNode *N, SDOperand N0,
     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 @@ SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) {
   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 DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) {
   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 @@ bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) {
   
   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 DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) {
       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 DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) {
           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 @@ class VISIBILITY_HIDDEN SelectionDAGLegalize {
   /// 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 @@ static void ComputeTopDownOrdering(SelectionDAG &DAG,
     // 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 @@ static SDNode *FindCallEndFromCallStart(SDNode *Node) {
        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 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
 
   // 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 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     // 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 SelectionDAGLegalize::PromoteOp(SDOperand Op) {
   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 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){
          "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 @@ NodeDone:
     
     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 @@ void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) {
 /// 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 @@ private:
 
   /// 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 @@ void ScheduleDAG::BuildSchedUnits() {
       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 @@ static const TargetRegisterClass *getInstrOperandRegClass(
 
 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 @@ void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
   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::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
 
 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 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
     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 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 
 /// 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 @@ static unsigned getVR(SDOperand Op, DenseMap<SDOperand, unsigned> &VRBaseMap) {
 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 @@ static const TargetRegisterClass *getSuperregRegisterClass(
 /// 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 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node,
   // 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 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node,
 /// 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 @@ void ScheduleDAG::EmitSchedule() {
   }
 
   // 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 @@ void SelectionDAG::RemoveDeadNodes() {
     // 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 @@ void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
     // 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 @@ void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
     
   // 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 @@ SelectionDAG::~SelectionDAG() {
   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 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op) {
     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 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
   
   // 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 @@ UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
   return UpdateNodeOperands(N, Ops, 5);
 }
 
-
 SDOperand SelectionDAG::
 UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
   SDNode *N = InN.Val;
@@ -3015,9 +3020,10 @@ UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
   // 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 @@ UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
   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 @@ void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
   // 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 @@ void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
   
   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 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
   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 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
     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 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
   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 @@ namespace {
     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 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
 
   // 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 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
     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 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
     // 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 @@ bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
 
   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 @@ bool SDNode::hasAnyUseOfValue(unsigned Value) const {
 
   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::hasAnyUseOfValue(unsigned Value) const {
 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 @@ bool SDNode::isOnlyUseOf(SDNode *N) const {
 
 /// 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 @@ bool SDNode::isOperandOf(SDNode *N) const {
 /// 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;