Re-commit of the r48822, where the infinite looping problem discovered

by Dan Gohman is fixed.



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

9 files changed, 131 insertions, 117 deletions

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 00ef6c9..4eccb81 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 ed1f718..5cb13e3 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()) {
@@ -5841,7 +5841,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 e9fa4bf..7d245ab 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 4d4c929..00b5677 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -137,11 +137,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;
@@ -400,7 +400,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!
@@ -416,7 +416,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 &&
@@ -475,7 +475,7 @@ unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node,
   if (!Node->hasOneUse())
     return 0;
 
-  SDNode *Use = *Node->use_begin();
+  SDNode *Use = Node->use_begin()->getUser();
   if (Use->getOpcode() == ISD::CopyToReg && 
       Use->getOperand(2).Val == Node &&
       Use->getOperand(2).ResNo == ResNo) {
@@ -488,7 +488,7 @@ unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node,
 
 void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
                                  const TargetInstrDesc &II,
-                                 DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                                 DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   assert(Node->getTargetOpcode() != TargetInstrInfo::IMPLICIT_DEF &&
          "IMPLICIT_DEF should have been handled as a special case elsewhere!");
 
@@ -499,7 +499,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) {
@@ -529,7 +529,7 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 /// getVR - Return the virtual register corresponding to the specified result
 /// of the specified node.
 unsigned ScheduleDAG::getVR(SDOperand Op,
-                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
+                            DenseMap<SDOperandImpl, unsigned> &VRBaseMap) {
   if (Op.isTargetOpcode() &&
       Op.getTargetOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
     // Add an IMPLICIT_DEF instruction before every use.
@@ -544,7 +544,7 @@ unsigned ScheduleDAG::getVR(SDOperand Op,
     return VReg;
   }
 
-  DenseMap<SDOperand, unsigned>::iterator I = VRBaseMap.find(Op);
+  DenseMap<SDOperandImpl, unsigned>::iterator I = VRBaseMap.find(Op);
   assert(I != VRBaseMap.end() && "Node emitted out of order - late");
   return I->second;
 }
@@ -557,7 +557,7 @@ unsigned ScheduleDAG::getVR(SDOperand Op,
 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
@@ -688,7 +688,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();
   
@@ -696,7 +696,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();
@@ -779,7 +779,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();
@@ -1099,7 +1099,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++) {
     SUnit *SU = Sequence[i];
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index f259b2b..a3a0c82 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();
@@ -2894,9 +2897,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);
@@ -2923,14 +2927,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.
@@ -2958,7 +2964,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;
@@ -2989,9 +2994,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);
     }
   }
 
@@ -3000,7 +3006,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.
@@ -3013,13 +3018,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;
   }
@@ -3029,8 +3035,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;
   }
 }
 
@@ -3298,21 +3306,22 @@ 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");
-  
+
   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();
+
     // 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.
@@ -3347,20 +3356,20 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
                               UpdateListener);
   
   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();
+
     // 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)) {
@@ -3390,21 +3399,22 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
     return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
 
   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();
+
     // 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)) {
@@ -3434,7 +3444,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);
@@ -3462,7 +3472,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
@@ -3476,7 +3492,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;
     
@@ -3490,9 +3506,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);
       }
     }
                
@@ -3672,16 +3689,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?
@@ -3700,8 +3714,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)
@@ -3719,7 +3733,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
@@ -3731,7 +3745,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;
@@ -3750,7 +3764,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;
   
diff --git a/lib/Target/PowerPC/PPCISelLowering.cpp b/lib/Target/PowerPC/PPCISelLowering.cpp
index 4055920..f307184 100644
--- a/lib/Target/PowerPC/PPCISelLowering.cpp
+++ b/lib/Target/PowerPC/PPCISelLowering.cpp
@@ -3662,11 +3662,11 @@ SDOperand PPCTargetLowering::PerformDAGCombine(SDNode *N,
       SDNode *LHSN = N->getOperand(0).Val;
       for (SDNode::use_iterator UI = LHSN->use_begin(), E = LHSN->use_end();
            UI != E; ++UI)
-        if ((*UI)->getOpcode() == PPCISD::VCMPo &&
-            (*UI)->getOperand(1) == N->getOperand(1) &&
-            (*UI)->getOperand(2) == N->getOperand(2) &&
-            (*UI)->getOperand(0) == N->getOperand(0)) {
-          VCMPoNode = *UI;
+        if ((*UI).getUser()->getOpcode() == PPCISD::VCMPo &&
+            (*UI).getUser()->getOperand(1) == N->getOperand(1) &&
+            (*UI).getUser()->getOperand(2) == N->getOperand(2) &&
+            (*UI).getUser()->getOperand(0) == N->getOperand(0)) {
+          VCMPoNode = UI->getUser();
           break;
         }
       
@@ -3682,7 +3682,7 @@ SDOperand PPCTargetLowering::PerformDAGCombine(SDNode *N,
       for (SDNode::use_iterator UI = VCMPoNode->use_begin(); 
            FlagUser == 0; ++UI) {
         assert(UI != VCMPoNode->use_end() && "Didn't find user!");
-        SDNode *User = *UI;
+        SDNode *User = UI->getUser();
         for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
           if (User->getOperand(i) == SDOperand(VCMPoNode, 1)) {
             FlagUser = User;
diff --git a/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp
index e2e7633..252a018 100644
--- a/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -225,7 +225,7 @@ namespace {
 static SDNode *findFlagUse(SDNode *N) {
   unsigned FlagResNo = N->getNumValues()-1;
   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
-    SDNode *User = *I;
+    SDNode *User = I->getUser();
     for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) {
       SDOperand Op = User->getOperand(i);
       if (Op.Val == N && Op.ResNo == FlagResNo)
diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp
index f73c3c2..a8407ca 100644
--- a/lib/Target/X86/X86ISelLowering.cpp
+++ b/lib/Target/X86/X86ISelLowering.cpp
@@ -3734,7 +3734,7 @@ X86TargetLowering::LowerEXTRACT_VECTOR_ELT_SSE4(SDOperand Op,
     // result has a single use which is a store.
     if (!Op.hasOneUse())
       return SDOperand();
-    SDNode *User = *Op.Val->use_begin();
+    SDNode *User = Op.Val->use_begin()->getUser();
     if (User->getOpcode() != ISD::STORE)
       return SDOperand();
     SDOperand Extract = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, MVT::i32,