Add a new function, ReplaceAllUsesOfValuesWith, which handles bulk

replacement of multiple values. This is slightly more efficient
than doing multiple ReplaceAllUsesOfValueWith calls, and theoretically
could be optimized even further. However, an important property of this
new function is that it handles the case where the source value set and
destination value set overlap. This makes it feasible for isel to use
SelectNodeTo in many very common cases, which is advantageous because
SelectNodeTo avoids a temporary node and it doesn't require CSEMap
updates for users of values that don't change position.

Revamp MorphNodeTo, which is what does all the work of SelectNodeTo, to
handle operand lists more efficiently, and to correctly handle a number
of corner cases to which its new wider use exposes it.

This commit also includes a change to the encoding of post-isel opcodes
in SDNodes; now instead of being sandwiched between the target-independent
pre-isel opcodes and the target-dependent pre-isel opcodes, post-isel
opcodes are now represented as negative values. This makes it possible
to test if an opcode is pre-isel or post-isel without having to know
the size of the current target's post-isel instruction set.

These changes speed up llc overall by 3% and reduce memory usage by 10%
on the InstructionCombining.cpp testcase with -fast and -regalloc=local.


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

4 files changed, 365 insertions, 225 deletions

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 982bbab..4f793a5 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -63,8 +63,8 @@ static void CheckForPhysRegDependency(SDNode *Def, SDNode *Use, unsigned Op,
     return;
 
   unsigned ResNo = Use->getOperand(2).ResNo;
-  if (Def->isTargetOpcode()) {
-    const TargetInstrDesc &II = TII->get(Def->getTargetOpcode());
+  if (Def->isMachineOpcode()) {
+    const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
     if (ResNo >= II.getNumDefs() &&
         II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
       PhysReg = Reg;
@@ -167,8 +167,8 @@ void ScheduleDAG::BuildSchedUnits() {
     SUnit *SU = &SUnits[su];
     SDNode *MainNode = SU->Node;
     
-    if (MainNode->isTargetOpcode()) {
-      unsigned Opc = MainNode->getTargetOpcode();
+    if (MainNode->isMachineOpcode()) {
+      unsigned Opc = MainNode->getMachineOpcode();
       const TargetInstrDesc &TID = TII->get(Opc);
       for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
         if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
@@ -186,9 +186,9 @@ void ScheduleDAG::BuildSchedUnits() {
     
     for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
       SDNode *N = SU->FlaggedNodes[n];
-      if (N->isTargetOpcode() &&
-          TII->get(N->getTargetOpcode()).getImplicitDefs() &&
-          CountResults(N) > TII->get(N->getTargetOpcode()).getNumDefs())
+      if (N->isMachineOpcode() &&
+          TII->get(N->getMachineOpcode()).getImplicitDefs() &&
+          CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs())
         SU->hasPhysRegDefs = true;
       
       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
@@ -227,8 +227,8 @@ void ScheduleDAG::ComputeLatency(SUnit *SU) {
   }
 
   SU->Latency = 0;
-  if (SU->Node->isTargetOpcode()) {
-    unsigned SchedClass = TII->get(SU->Node->getTargetOpcode()).getSchedClass();
+  if (SU->Node->isMachineOpcode()) {
+    unsigned SchedClass = TII->get(SU->Node->getMachineOpcode()).getSchedClass();
     const InstrStage *S = InstrItins.begin(SchedClass);
     const InstrStage *E = InstrItins.end(SchedClass);
     for (; S != E; ++S)
@@ -236,8 +236,8 @@ void ScheduleDAG::ComputeLatency(SUnit *SU) {
   }
   for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) {
     SDNode *FNode = SU->FlaggedNodes[i];
-    if (FNode->isTargetOpcode()) {
-      unsigned SchedClass = TII->get(FNode->getTargetOpcode()).getSchedClass();
+    if (FNode->isMachineOpcode()) {
+      unsigned SchedClass = TII->get(FNode->getMachineOpcode()).getSchedClass();
       const InstrStage *S = InstrItins.begin(SchedClass);
       const InstrStage *E = InstrItins.end(SchedClass);
       for (; S != E; ++S)
@@ -501,7 +501,7 @@ unsigned ScheduleDAG::getDstOfOnlyCopyToRegUse(SDNode *Node,
 void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
                                  const TargetInstrDesc &II,
                                  DenseMap<SDOperand, unsigned> &VRBaseMap) {
-  assert(Node->getTargetOpcode() != TargetInstrInfo::IMPLICIT_DEF &&
+  assert(Node->getMachineOpcode() != TargetInstrInfo::IMPLICIT_DEF &&
          "IMPLICIT_DEF should have been handled as a special case elsewhere!");
 
   for (unsigned i = 0; i < II.getNumDefs(); ++i) {
@@ -544,8 +544,8 @@ void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 /// of the specified node.
 unsigned ScheduleDAG::getVR(SDOperand Op,
                             DenseMap<SDOperand, unsigned> &VRBaseMap) {
-  if (Op.isTargetOpcode() &&
-      Op.getTargetOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+  if (Op.isMachineOpcode() &&
+      Op.getMachineOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
     // Add an IMPLICIT_DEF instruction before every use.
     unsigned VReg = getDstOfOnlyCopyToRegUse(Op.Val, Op.ResNo);
     // IMPLICIT_DEF can produce any type of result so its TargetInstrDesc
@@ -572,7 +572,7 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op,
                              unsigned IIOpNum,
                              const TargetInstrDesc *II,
                              DenseMap<SDOperand, unsigned> &VRBaseMap) {
-  if (Op.isTargetOpcode()) {
+  if (Op.isMachineOpcode()) {
     // 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
     // simpler here.
@@ -704,7 +704,7 @@ getSuperRegisterRegClass(const TargetRegisterClass *TRC,
 void ScheduleDAG::EmitSubregNode(SDNode *Node, 
                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
-  unsigned Opc = Node->getTargetOpcode();
+  unsigned Opc = Node->getMachineOpcode();
   
   // 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.
@@ -799,8 +799,8 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node,
 void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone,
                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
   // If machine instruction
-  if (Node->isTargetOpcode()) {
-    unsigned Opc = Node->getTargetOpcode();
+  if (Node->isMachineOpcode()) {
+    unsigned Opc = Node->getMachineOpcode();
     
     // Handle subreg insert/extract specially
     if (Opc == TargetInstrInfo::EXTRACT_SUBREG || 
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index 39aadd5..4b09b7c 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -206,7 +206,7 @@ void ScheduleDAGList::ListScheduleTopDown() {
       // If this is a pseudo op, like copyfromreg, look to see if there is a
       // real target node flagged to it.  If so, use the target node.
       for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size(); 
-           FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
+           !FoundNode->isMachineOpcode() && i != e; ++i)
         FoundNode = CurSUnit->FlaggedNodes[i];
       
       HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode);
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index 098b799..43fbd4b 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -216,7 +216,7 @@ void ScheduleDAGRRList::CommuteNodesToReducePressure() {
     SUnit *SU = Sequence[i];
     if (!SU || !SU->Node) continue;
     if (SU->isCommutable) {
-      unsigned Opc = SU->Node->getTargetOpcode();
+      unsigned Opc = SU->Node->getMachineOpcode();
       const TargetInstrDesc &TID = TII->get(Opc);
       unsigned NumRes = TID.getNumDefs();
       unsigned NumOps = TID.getNumOperands() - NumRes;
@@ -678,7 +678,7 @@ SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
     assert(N->getNodeId() == -1 && "Node already inserted!");
     N->setNodeId(NewSU->NodeNum);
       
-    const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
+    const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
     for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
       if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
         NewSU->isTwoAddress = true;
@@ -872,7 +872,7 @@ void ScheduleDAGRRList::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
 /// FIXME: Move to SelectionDAG?
 static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
                                  const TargetInstrInfo *TII) {
-  const TargetInstrDesc &TID = TII->get(N->getTargetOpcode());
+  const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
   assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
   unsigned NumRes = TID.getNumDefs();
   for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
@@ -913,9 +913,9 @@ bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
 
   for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) {
     SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1];
-    if (!Node || !Node->isTargetOpcode())
+    if (!Node || !Node->isMachineOpcode())
       continue;
-    const TargetInstrDesc &TID = TII->get(Node->getTargetOpcode());
+    const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
     if (!TID.ImplicitDefs)
       continue;
     for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) {
@@ -1673,7 +1673,7 @@ bu_ls_rr_fast_sort::operator()(const SUnit *left, const SUnit *right) const {
 bool
 BURegReductionPriorityQueue::canClobber(const SUnit *SU, const SUnit *Op) {
   if (SU->isTwoAddress) {
-    unsigned Opc = SU->Node->getTargetOpcode();
+    unsigned Opc = SU->Node->getMachineOpcode();
     const TargetInstrDesc &TID = TII->get(Opc);
     unsigned NumRes = TID.getNumDefs();
     unsigned NumOps = TID.getNumOperands() - NumRes;
@@ -1709,11 +1709,11 @@ static bool canClobberPhysRegDefs(SUnit *SuccSU, SUnit *SU,
                                   const TargetInstrInfo *TII,
                                   const TargetRegisterInfo *TRI) {
   SDNode *N = SuccSU->Node;
-  unsigned NumDefs = TII->get(N->getTargetOpcode()).getNumDefs();
-  const unsigned *ImpDefs = TII->get(N->getTargetOpcode()).getImplicitDefs();
+  unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
+  const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
   assert(ImpDefs && "Caller should check hasPhysRegDefs");
   const unsigned *SUImpDefs =
-    TII->get(SU->Node->getTargetOpcode()).getImplicitDefs();
+    TII->get(SU->Node->getMachineOpcode()).getImplicitDefs();
   if (!SUImpDefs)
     return false;
   for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
@@ -1744,10 +1744,10 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
       continue;
 
     SDNode *Node = SU->Node;
-    if (!Node || !Node->isTargetOpcode() || SU->FlaggedNodes.size() > 0)
+    if (!Node || !Node->isMachineOpcode() || SU->FlaggedNodes.size() > 0)
       continue;
 
-    unsigned Opc = Node->getTargetOpcode();
+    unsigned Opc = Node->getMachineOpcode();
     const TargetInstrDesc &TID = TII->get(Opc);
     unsigned NumRes = TID.getNumDefs();
     unsigned NumOps = TID.getNumOperands() - NumRes;
@@ -1768,7 +1768,7 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
           // depth and height.
           if (SuccSU->Height < SU->Height && (SU->Height - SuccSU->Height) > 1)
             continue;
-          if (!SuccSU->Node || !SuccSU->Node->isTargetOpcode())
+          if (!SuccSU->Node || !SuccSU->Node->isMachineOpcode())
             continue;
           // Don't constrain nodes with physical register defs if the
           // predecessor can clobber them.
@@ -1778,7 +1778,7 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() {
           }
           // Don't constraint extract_subreg / insert_subreg these may be
           // coalesced away. We don't them close to their uses.
-          unsigned SuccOpc = SuccSU->Node->getTargetOpcode();
+          unsigned SuccOpc = SuccSU->Node->getMachineOpcode();
           if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
               SuccOpc == TargetInstrInfo::INSERT_SUBREG)
             continue;
@@ -1836,8 +1836,8 @@ static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU,
 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
   unsigned LPriority = SPQ->getNodePriority(left);
   unsigned RPriority = SPQ->getNodePriority(right);
-  bool LIsTarget = left->Node && left->Node->isTargetOpcode();
-  bool RIsTarget = right->Node && right->Node->isTargetOpcode();
+  bool LIsTarget = left->Node && left->Node->isMachineOpcode();
+  bool RIsTarget = right->Node && right->Node->isMachineOpcode();
   bool LIsFloater = LIsTarget && left->NumPreds == 0;
   bool RIsFloater = RIsTarget && right->NumPreds == 0;
   unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index f793713..e757133 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -197,8 +197,8 @@ bool ISD::isDebugLabel(const SDNode *N) {
   SDOperand Zero;
   if (N->getOpcode() == ISD::DBG_LABEL)
     return true;
-  if (N->isTargetOpcode() &&
-      N->getTargetOpcode() == TargetInstrInfo::DBG_LABEL)
+  if (N->isMachineOpcode() &&
+      N->getMachineOpcode() == TargetInstrInfo::DBG_LABEL)
     return true;
   return false;
 }
@@ -532,8 +532,7 @@ void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
 }
 
 void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
-  SmallVector<SDNode*, 16> DeadNodes;
-  DeadNodes.push_back(N);
+  SmallVector<SDNode*, 16> DeadNodes(1, N);
   RemoveDeadNodes(DeadNodes, UpdateListener);
 }
 
@@ -3523,31 +3522,33 @@ SDVTList SelectionDAG::getVTList(MVT VT) {
 }
 
 SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2) {
-  for (std::list<std::vector<MVT> >::iterator I = VTList.begin(),
-       E = VTList.end(); I != E; ++I) {
-    if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
-      return makeVTList(&(*I)[0], 2);
-  }
-  std::vector<MVT> V;
-  V.push_back(VT1);
-  V.push_back(VT2);
-  VTList.push_front(V);
-  return makeVTList(&(*VTList.begin())[0], 2);
-}
-SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2,
-                                 MVT VT3) {
-  for (std::list<std::vector<MVT> >::iterator I = VTList.begin(),
-       E = VTList.end(); I != E; ++I) {
-    if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
-        (*I)[2] == VT3)
-      return makeVTList(&(*I)[0], 3);
-  }
-  std::vector<MVT> V;
-  V.push_back(VT1);
-  V.push_back(VT2);
-  V.push_back(VT3);
-  VTList.push_front(V);
-  return makeVTList(&(*VTList.begin())[0], 3);
+  for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
+       E = VTList.rend(); I != E; ++I)
+    if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2)
+      return *I;
+
+  MVT *Array = Allocator.Allocate<MVT>(2);
+  Array[0] = VT1;
+  Array[1] = VT2;
+  SDVTList Result = makeVTList(Array, 2);
+  VTList.push_back(Result);
+  return Result;
+}
+
+SDVTList SelectionDAG::getVTList(MVT VT1, MVT VT2, MVT VT3) {
+  for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
+       E = VTList.rend(); I != E; ++I)
+    if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 &&
+                          I->VTs[2] == VT3)
+      return *I;
+
+  MVT *Array = Allocator.Allocate<MVT>(3);
+  Array[0] = VT1;
+  Array[1] = VT2;
+  Array[2] = VT3;
+  SDVTList Result = makeVTList(Array, 3);
+  VTList.push_back(Result);
+  return Result;
 }
 
 SDVTList SelectionDAG::getVTList(const MVT *VTs, unsigned NumVTs) {
@@ -3559,22 +3560,26 @@ SDVTList SelectionDAG::getVTList(const MVT *VTs, unsigned NumVTs) {
     default: break;
   }
 
-  for (std::list<std::vector<MVT> >::iterator I = VTList.begin(),
-       E = VTList.end(); I != E; ++I) {
-    if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
+  for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(),
+       E = VTList.rend(); I != E; ++I) {
+    if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1])
+      continue;
    
     bool NoMatch = false;
     for (unsigned i = 2; i != NumVTs; ++i)
-      if (VTs[i] != (*I)[i]) {
+      if (VTs[i] != I->VTs[i]) {
         NoMatch = true;
         break;
       }
     if (!NoMatch)
-      return makeVTList(&*I->begin(), NumVTs);
+      return *I;
   }
   
-  VTList.push_front(std::vector<MVT>(VTs, VTs+NumVTs));
-  return makeVTList(&*VTList.begin()->begin(), NumVTs);
+  MVT *Array = Allocator.Allocate<MVT>(NumVTs);
+  std::copy(VTs, VTs+NumVTs, Array);
+  SDVTList Result = makeVTList(Array, NumVTs);
+  VTList.push_back(Result);
+  return Result;
 }
 
 
@@ -3711,61 +3716,9 @@ UpdateNodeOperands(SDOperand InN, const 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.
-void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
-                         const SDOperand *Ops, unsigned NumOps,
-                         SmallVectorImpl<SDNode *> &DeadNodes) {
-  NodeType = Opc;
-  ValueList = L.VTs;
-  NumValues = L.NumVTs;
-  
-  // Clear the operands list, updating used nodes to remove this from their
-  // use list.  Keep track of any operands that become dead as a result.
-  SmallPtrSet<SDNode*, 16> DeadNodeSet;
-  for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) {
-    SDNode *N = I->getVal();
-    N->removeUser(std::distance(op_begin(), I), this);
-    if (N->use_empty())
-      DeadNodeSet.insert(N);
-  }
-
-  // If NumOps is larger than the # of operands we currently have, reallocate
-  // the operand list.
-  if (NumOps > NumOperands) {
-    if (OperandsNeedDelete) {
-      delete [] OperandList;
-    }
-    OperandList = new SDUse[NumOps];
-    OperandsNeedDelete = true;
-  }
-  
-  // Assign the new operands.
-  NumOperands = NumOps;
-  
-  for (unsigned i = 0, e = NumOps; i != e; ++i) {
-    OperandList[i] = Ops[i];
-    OperandList[i].setUser(this);
-    SDNode *N = OperandList[i].getVal();
-    N->addUser(i, this);
-    DeadNodeSet.erase(N);
-  }
-
-  // Clean up any nodes that are still dead after adding the uses for the
-  // new operands.
-  for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
-       E = DeadNodeSet.end(); I != E; ++I)
-    DeadNodes.push_back(*I);
-}
-
 /// DropOperands - Release the operands and set this node to have
-/// zero operands.  This should only be used by HandleSDNode to clear
-/// its operand list.
+/// zero operands.
 void SDNode::DropOperands() {
-  assert(NodeType == ISD::HANDLENODE &&
-         "DropOperands is for HANDLENODE only!");
-
   // Unlike the code in MorphNodeTo that does this, we don't need to
   // watch for dead nodes here.
   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
@@ -3774,112 +3727,257 @@ void SDNode::DropOperands() {
   NumOperands = 0;
 }
 
-/// SelectNodeTo - These are used for target selectors to *mutate* the
-/// specified node to have the specified return type, Target opcode, and
-/// operands.  Note that target opcodes are stored as
-/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
+/// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
+/// machine opcode.
 ///
-/// Note that SelectNodeTo returns the resultant node.  If there is already a
-/// node of the specified opcode and operands, it returns that node instead of
-/// the current one.
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT) {
   SDVTList VTs = getVTList(VT);
-  return SelectNodeTo(N, TargetOpc, VTs, 0, 0);
+  return SelectNodeTo(N, MachineOpc, VTs, 0, 0);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT, SDOperand Op1) {
   SDVTList VTs = getVTList(VT);
   SDOperand Ops[] = { Op1 };
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, 1);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT, SDOperand Op1,
                                    SDOperand Op2) {
   SDVTList VTs = getVTList(VT);
   SDOperand Ops[] = { Op1, Op2 };
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, 2);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT, SDOperand Op1,
                                    SDOperand Op2, SDOperand Op3) {
   SDVTList VTs = getVTList(VT);
   SDOperand Ops[] = { Op1, Op2, Op3 };
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, 3);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT, const SDOperand *Ops,
                                    unsigned NumOps) {
   SDVTList VTs = getVTList(VT);
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT1, MVT VT2, const SDOperand *Ops,
                                    unsigned NumOps) {
   SDVTList VTs = getVTList(VT1, VT2);
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT1, MVT VT2) {
   SDVTList VTs = getVTList(VT1, VT2);
-  return SelectNodeTo(N, TargetOpc, VTs, (SDOperand *)0, 0);
+  return SelectNodeTo(N, MachineOpc, VTs, (SDOperand *)0, 0);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT1, MVT VT2, MVT VT3,
                                    const SDOperand *Ops, unsigned NumOps) {
   SDVTList VTs = getVTList(VT1, VT2, VT3);
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, NumOps);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 
                                    MVT VT1, MVT VT2,
                                    SDOperand Op1) {
   SDVTList VTs = getVTList(VT1, VT2);
   SDOperand Ops[] = { Op1 };
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, 1);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, 1);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 
                                    MVT VT1, MVT VT2,
                                    SDOperand Op1, SDOperand Op2) {
   SDVTList VTs = getVTList(VT1, VT2);
   SDOperand Ops[] = { Op1, Op2 };
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, 2);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, 2);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    MVT VT1, MVT VT2,
                                    SDOperand Op1, SDOperand Op2, 
                                    SDOperand Op3) {
   SDVTList VTs = getVTList(VT1, VT2);
   SDOperand Ops[] = { Op1, Op2, Op3 };
-  return SelectNodeTo(N, TargetOpc, VTs, Ops, 3);
+  return SelectNodeTo(N, MachineOpc, VTs, Ops, 3);
 }
 
-SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
+SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
                                    SDVTList VTs, const SDOperand *Ops,
                                    unsigned NumOps) {
+  return MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT) {
+  SDVTList VTs = getVTList(VT);
+  return MorphNodeTo(N, Opc, VTs, 0, 0);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT, SDOperand Op1) {
+  SDVTList VTs = getVTList(VT);
+  SDOperand Ops[] = { Op1 };
+  return MorphNodeTo(N, Opc, VTs, Ops, 1);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT, SDOperand Op1,
+                                  SDOperand Op2) {
+  SDVTList VTs = getVTList(VT);
+  SDOperand Ops[] = { Op1, Op2 };
+  return MorphNodeTo(N, Opc, VTs, Ops, 2);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT, SDOperand Op1,
+                                  SDOperand Op2, SDOperand Op3) {
+  SDVTList VTs = getVTList(VT);
+  SDOperand Ops[] = { Op1, Op2, Op3 };
+  return MorphNodeTo(N, Opc, VTs, Ops, 3);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT, const SDOperand *Ops,
+                                  unsigned NumOps) {
+  SDVTList VTs = getVTList(VT);
+  return MorphNodeTo(N, Opc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT1, MVT VT2, const SDOperand *Ops,
+                                  unsigned NumOps) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  return MorphNodeTo(N, Opc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT1, MVT VT2) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  return MorphNodeTo(N, Opc, VTs, (SDOperand *)0, 0);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT1, MVT VT2, MVT VT3,
+                                  const SDOperand *Ops, unsigned NumOps) {
+  SDVTList VTs = getVTList(VT1, VT2, VT3);
+  return MorphNodeTo(N, Opc, VTs, Ops, NumOps);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 
+                                  MVT VT1, MVT VT2,
+                                  SDOperand Op1) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  SDOperand Ops[] = { Op1 };
+  return MorphNodeTo(N, Opc, VTs, Ops, 1);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 
+                                  MVT VT1, MVT VT2,
+                                  SDOperand Op1, SDOperand Op2) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  SDOperand Ops[] = { Op1, Op2 };
+  return MorphNodeTo(N, Opc, VTs, Ops, 2);
+}
+
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  MVT VT1, MVT VT2,
+                                  SDOperand Op1, SDOperand Op2, 
+                                  SDOperand Op3) {
+  SDVTList VTs = getVTList(VT1, VT2);
+  SDOperand Ops[] = { Op1, Op2, Op3 };
+  return MorphNodeTo(N, Opc, VTs, Ops, 3);
+}
+
+/// MorphNodeTo - These *mutate* the specified node to have the specified
+/// return type, opcode, and operands.
+///
+/// Note that MorphNodeTo returns the resultant node.  If there is already a
+/// node of the specified opcode and operands, it returns that node instead of
+/// the current one.
+///
+/// Using MorphNodeTo is faster than creating a new node and swapping it in
+/// with ReplaceAllUsesWith both because it often avoids allocating a new
+/// node, and because it doesn't require CSE recalulation for any of
+/// the node's users.
+///
+SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
+                                  SDVTList VTs, const SDOperand *Ops,
+                                  unsigned NumOps) {
   // If an identical node already exists, use it.
-  FoldingSetNodeID ID;
-  AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
   void *IP = 0;
-  if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
-    return ON;
+  if (VTs.VTs[VTs.NumVTs-1] != MVT::Flag) {
+    FoldingSetNodeID ID;
+    AddNodeIDNode(ID, Opc, VTs, Ops, NumOps);
+    if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
+      return ON;
+  }
 
   RemoveNodeFromCSEMaps(N);
 
+  // Start the morphing.
+  N->NodeType = Opc;
+  N->ValueList = VTs.VTs;
+  N->NumValues = VTs.NumVTs;
+  
+  // Clear the operands list, updating used nodes to remove this from their
+  // use list.  Keep track of any operands that become dead as a result.
+  SmallPtrSet<SDNode*, 16> DeadNodeSet;
+  for (SDNode::op_iterator B = N->op_begin(), I = B, E = N->op_end();
+       I != E; ++I) {
+    SDNode *Used = I->getVal();
+    Used->removeUser(std::distance(B, I), N);
+    if (Used->use_empty())
+      DeadNodeSet.insert(Used);
+  }
+
+  // If NumOps is larger than the # of operands we currently have, reallocate
+  // the operand list.
+  if (NumOps > N->NumOperands) {
+    if (N->OperandsNeedDelete)
+      delete[] N->OperandList;
+    if (N->isMachineOpcode()) {
+      // We're creating a final node that will live unmorphed for the
+      // remainder of this SelectionDAG's duration, so we can allocate the
+      // operands directly out of the pool with no recycling metadata.
+      N->OperandList = Allocator.Allocate<SDUse>(NumOps);
+      N->OperandsNeedDelete = false;
+    } else {
+      N->OperandList = new SDUse[NumOps];
+      N->OperandsNeedDelete = true;
+    }
+  }
+  
+  // Assign the new operands.
+  N->NumOperands = NumOps;
+  for (unsigned i = 0, e = NumOps; i != e; ++i) {
+    N->OperandList[i] = Ops[i];
+    N->OperandList[i].setUser(N);
+    SDNode *ToUse = N->OperandList[i].getVal();
+    ToUse->addUser(i, N);
+    DeadNodeSet.erase(ToUse);
+  }
+
+  // Delete any nodes that are still dead after adding the uses for the
+  // new operands.
   SmallVector<SDNode *, 16> DeadNodes;
-  N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps, DeadNodes);
+  for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
+       E = DeadNodeSet.end(); I != E; ++I)
+    if ((*I)->use_empty())
+      DeadNodes.push_back(*I);
   RemoveDeadNodes(DeadNodes);
 
-  CSEMap.InsertNode(N, IP);   // Memoize the new node.
+  if (IP)
+    CSEMap.InsertNode(N, IP);   // Memoize the new node.
   return N;
 }
 
@@ -3891,70 +3989,70 @@ SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
 /// node of the specified opcode and operands, it returns that node instead of
 /// the current one.
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT) {
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
+  return getNode(~Opcode, VT).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT, SDOperand Op1) {
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
+  return getNode(~Opcode, VT, Op1).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
                                     SDOperand Op1, SDOperand Op2) {
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
+  return getNode(~Opcode, VT, Op1, Op2).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
                                     SDOperand Op1, SDOperand Op2,
                                     SDOperand Op3) {
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
+  return getNode(~Opcode, VT, Op1, Op2, Op3).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT,
                                     const SDOperand *Ops, unsigned NumOps) {
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
+  return getNode(~Opcode, VT, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2);
   SDOperand Op;
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op, 0).Val;
+  return getNode(~Opcode, VTs, 2, &Op, 0).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
                                     MVT VT2, SDOperand Op1) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2);
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
+  return getNode(~Opcode, VTs, 2, &Op1, 1).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
                                     MVT VT2, SDOperand Op1,
                                     SDOperand Op2) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2);
   SDOperand Ops[] = { Op1, Op2 };
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
+  return getNode(~Opcode, VTs, 2, Ops, 2).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
                                     MVT VT2, SDOperand Op1,
                                     SDOperand Op2, SDOperand Op3) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2);
   SDOperand Ops[] = { Op1, Op2, Op3 };
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
+  return getNode(~Opcode, VTs, 2, Ops, 3).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2,
                                     const SDOperand *Ops, unsigned NumOps) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2);
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
+  return getNode(~Opcode, VTs, 2, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
                                     SDOperand Op1, SDOperand Op2) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
   SDOperand Ops[] = { Op1, Op2 };
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
+  return getNode(~Opcode, VTs, 3, Ops, 2).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
                                     SDOperand Op1, SDOperand Op2,
                                     SDOperand Op3) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
   SDOperand Ops[] = { Op1, Op2, Op3 };
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val;
+  return getNode(~Opcode, VTs, 3, Ops, 3).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1, MVT VT2, MVT VT3,
                                     const SDOperand *Ops, unsigned NumOps) {
   const MVT *VTs = getNodeValueTypes(VT1, VT2, VT3);
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
+  return getNode(~Opcode, VTs, 3, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
                                     MVT VT2, MVT VT3, MVT VT4,
@@ -3965,13 +4063,13 @@ SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT VT1,
   VTList.push_back(VT3);
   VTList.push_back(VT4);
   const MVT *VTs = getNodeValueTypes(VTList);
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val;
+  return getNode(~Opcode, VTs, 4, Ops, NumOps).Val;
 }
 SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
                                     const std::vector<MVT> &ResultTys,
                                     const SDOperand *Ops, unsigned NumOps) {
   const MVT *VTs = getNodeValueTypes(ResultTys);
-  return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(),
+  return getNode(~Opcode, VTs, ResultTys.size(),
                  Ops, NumOps).Val;
 }
 
@@ -4043,13 +4141,14 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
 ///
 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
                                       DAGUpdateListener *UpdateListener) {
-  assert(From != To && "Cannot replace uses of with self");
-  assert(From->getNumValues() == To->getNumValues() &&
+  assert(From->getVTList().VTs == To->getVTList().VTs &&
+         From->getNumValues() == To->getNumValues() &&
          "Cannot use this version of ReplaceAllUsesWith!");
-  if (From->getNumValues() == 1)   // If possible, use the faster version.
-    return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
-                              UpdateListener);
-  
+
+  // Handle the trivial case.
+  if (From == To)
+    return;
+
   while (!From->use_empty()) {
     SDNode::use_iterator UI = From->use_begin();
     SDNode *U = UI->getUser();
@@ -4127,36 +4226,14 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
   }
 }
 
-namespace {
-  /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes
-  /// any deleted nodes from the set passed into its constructor and recursively
-  /// notifies another update listener if specified.
-  class ChainedSetUpdaterListener : 
-  public SelectionDAG::DAGUpdateListener {
-    SmallSetVector<SDNode*, 16> &Set;
-    SelectionDAG::DAGUpdateListener *Chain;
-  public:
-    ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
-                              SelectionDAG::DAGUpdateListener *chain)
-      : Set(set), Chain(chain) {}
- 
-    virtual void NodeDeleted(SDNode *N, SDNode *E) {
-      Set.remove(N);
-      if (Chain) Chain->NodeDeleted(N, E);
-    }
-    virtual void NodeUpdated(SDNode *N) {
-      if (Chain) Chain->NodeUpdated(N);
-    }
-  };
-}
-
 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
 /// uses of other values produced by From.Val alone.  The Deleted vector is
 /// handled the same way as for ReplaceAllUsesWith.
 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
                                              DAGUpdateListener *UpdateListener){
-  assert(From != To && "Cannot replace a value with itself");
-  
+  // Handle the really simple, really trivial case efficiently.
+  if (From == To) return;
+
   // Handle the simple, trivial, case efficiently.
   if (From.Val->getNumValues() == 1) {
     ReplaceAllUsesWith(From, To, UpdateListener);
@@ -4174,11 +4251,6 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
     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
-  // from Users if present.  CSUL does this.
-  ChainedSetUpdaterListener CSUL(Users, UpdateListener);
-  
   while (!Users.empty()) {
     // We know that this user uses some value of From.  If it is the right
     // value, update it.
@@ -4217,10 +4289,74 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
     
     // If there was already an existing matching node, use ReplaceAllUsesWith
     // to replace the dead one with the existing one.  This can cause
-    // recursive merging of other unrelated nodes down the line.  The merging
-    // can cause deletion of nodes that used the old value.  To handle this, we
-    // use CSUL to remove them from the Users set.
-    ReplaceAllUsesWith(User, Existing, &CSUL);
+    // recursive merging of other unrelated nodes down the line.
+    ReplaceAllUsesWith(User, Existing, UpdateListener);
+    
+    // User is now dead.  Notify a listener if present.
+    if (UpdateListener) UpdateListener->NodeDeleted(User, Existing);
+    DeleteNodeNotInCSEMaps(User);
+  }
+}
+
+/// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
+/// uses of other values produced by From.Val alone.  The same value may
+/// appear in both the From and To list.  The Deleted vector is
+/// handled the same way as for ReplaceAllUsesWith.
+void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDOperand *From,
+                                              const SDOperand *To,
+                                              unsigned Num,
+                                              DAGUpdateListener *UpdateListener){
+  // Handle the simple, trivial case efficiently.
+  if (Num == 1)
+    return ReplaceAllUsesOfValueWith(*From, *To, UpdateListener);
+
+  SmallVector<std::pair<SDNode *, unsigned>, 16> Users;
+  for (unsigned i = 0; i != Num; ++i)
+    for (SDNode::use_iterator UI = From[i].Val->use_begin(), 
+         E = From[i].Val->use_end(); UI != E; ++UI)
+      Users.push_back(std::make_pair(UI->getUser(), i));
+
+  while (!Users.empty()) {
+    // We know that this user uses some value of From.  If it is the right
+    // value, update it.
+    SDNode *User = Users.back().first;
+    unsigned i = Users.back().second;
+    Users.pop_back();
+    
+    // Scan for an operand that matches From.
+    SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
+    for (; Op != E; ++Op)
+      if (*Op == From[i]) break;
+    
+    // If there are no matches, the user must use some other result of From.
+    if (Op == E) continue;
+      
+    // Okay, we know this user needs to be updated.  Remove its old self
+    // from the CSE maps.
+    RemoveNodeFromCSEMaps(User);
+    
+    // Update all operands that match "From" in case there are multiple uses.
+    for (; Op != E; ++Op) {
+      if (*Op == From[i]) {
+        From[i].Val->removeUser(Op-User->op_begin(), User);
+        *Op = To[i];
+        Op->setUser(User);
+        To[i].Val->addUser(Op-User->op_begin(), User);
+      }
+    }
+               
+    // Now that we have modified User, add it back to the CSE maps.  If it
+    // already exists there, recursively merge the results together.
+    SDNode *Existing = AddNonLeafNodeToCSEMaps(User);
+    if (!Existing) {
+      if (UpdateListener) UpdateListener->NodeUpdated(User);
+      continue;  // Continue on to next user.
+    }
+    
+    // If there was already an existing matching node, use ReplaceAllUsesWith
+    // to replace the dead one with the existing one.  This can cause
+    // recursive merging of other unrelated nodes down the line.
+    ReplaceAllUsesWith(User, Existing, UpdateListener);
     
     // User is now dead.  Notify a listener if present.
     if (UpdateListener) UpdateListener->NodeDeleted(User, Existing);
@@ -4507,21 +4643,25 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const {
   default:
     if (getOpcode() < ISD::BUILTIN_OP_END)
       return "<<Unknown DAG Node>>";
-    else {
-      if (G) {
+    if (isMachineOpcode()) {
+      if (G)
         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
-          if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
-            return TII->get(getOpcode()-ISD::BUILTIN_OP_END).getName();
-
-        TargetLowering &TLI = G->getTargetLoweringInfo();
-        const char *Name =
-          TLI.getTargetNodeName(getOpcode());
-        if (Name) return Name;
-      }
-
+          if (getMachineOpcode() < TII->getNumOpcodes())
+            return TII->get(getMachineOpcode()).getName();
+      return "<<Unknown Machine Node>>";
+    }
+    if (G) {
+      TargetLowering &TLI = G->getTargetLoweringInfo();
+      const char *Name = TLI.getTargetNodeName(getOpcode());
+      if (Name) return Name;
       return "<<Unknown Target Node>>";
     }
+    return "<<Unknown Node>>";
    
+#ifndef NDEBUG
+  case ISD::DELETED_NODE:
+    return "<<Deleted Node!>>";
+#endif
   case ISD::PREFETCH:      return "Prefetch";
   case ISD::MEMBARRIER:    return "MemBarrier";
   case ISD::ATOMIC_CMP_SWAP:  return "AtomicCmpSwap";