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

21 files changed, 520 insertions, 310 deletions

diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h
index f1774bf..79f6276 100644
--- a/include/llvm/CodeGen/DAGISelHeader.h
+++ b/include/llvm/CodeGen/DAGISelHeader.h
@@ -124,6 +124,17 @@ void ReplaceUses(SDOperand F, SDOperand T) DISABLE_INLINE {
   UpdateQueue(ISQU);
 }
 
+/// ReplaceUses - replace all uses of the old nodes F with the use
+/// of the new nodes T.
+void ReplaceUses(const SDOperand *F, const SDOperand *T,
+                 unsigned Num) DISABLE_INLINE {
+  ISelQueueUpdater ISQU(ISelQueue);
+  CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISQU);
+  for (unsigned i = 0; i != Num; ++i)
+    setSelected(F[i].Val->getNodeId());
+  UpdateQueue(ISQU);
+}
+
 /// ReplaceUses - replace all uses of the old node F with the use
 /// of the new node T.
 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 636e36d..f530f33 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -60,6 +60,10 @@ class SelectionDAG {
   /// CSE with existing nodes with a duplicate is requested.
   FoldingSet<SDNode> CSEMap;
 
+  /// Allocator - Pool allocation for misc. objects that are created once per
+  /// SelectionDAG.
+  BumpPtrAllocator Allocator;
+
 public:
   SelectionDAG(TargetLowering &tli, MachineFunction &mf, 
                FunctionLoweringInfo &fli, MachineModuleInfo *mmi,
@@ -457,8 +461,7 @@ public:
   /// 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.  The 0th value
-  /// of the resultant node is returned.
+  /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT);
   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT, SDOperand Op1);
   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT VT,
@@ -481,6 +484,29 @@ public:
   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
                        const SDOperand *Ops, unsigned NumOps);
 
+  /// MorphNodeTo - These *mutate* the specified node to have the specified
+  /// return type, opcode, and operands.
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT, SDOperand Op1);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT,
+                      SDOperand Op1, SDOperand Op2);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT,
+                      SDOperand Op1, SDOperand Op2, SDOperand Op3);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT,
+                      const SDOperand *Ops, unsigned NumOps);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1, MVT VT2);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1,
+                      MVT VT2, const SDOperand *Ops, unsigned NumOps);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1,
+                      MVT VT2, MVT VT3, const SDOperand *Ops, unsigned NumOps);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1,
+                      MVT VT2, SDOperand Op1);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1,
+                      MVT VT2, SDOperand Op1, SDOperand Op2);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, MVT VT1,
+                      MVT VT2, SDOperand Op1, SDOperand Op2, SDOperand Op3);
+  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
+                      const SDOperand *Ops, unsigned NumOps);
 
   /// getTargetNode - These are used for target selectors to create a new node
   /// with specified return type(s), target opcode, and operands.
@@ -565,6 +591,13 @@ public:
   void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
                                  DAGUpdateListener *UpdateListener = 0);
 
+  /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
+  /// for multiple values at once. This correctly handles the case where
+  /// there is an overlap between the From values and the To values.
+  void ReplaceAllUsesOfValuesWith(const SDOperand *From, const SDOperand *To,
+                                  unsigned Num,
+                                  DAGUpdateListener *UpdateListener = 0);
+
   /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
   /// based on their topological order. It returns the maximum id and a vector
   /// of the SDNodes* in assigned order by reference.
@@ -654,7 +687,7 @@ private:
   unsigned getMVTAlignment(MVT MemoryVT) const;
   
   // List of non-single value types.
-  std::list<std::vector<MVT> > VTList;
+  std::vector<SDVTList> VTList;
   
   // Maps to auto-CSE operations.
   std::vector<CondCodeSDNode*> CondCodeNodes;
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index d1363e9..78897cb 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -846,7 +846,8 @@ public:
   inline const SDOperand &getOperand(unsigned i) const;
   inline uint64_t getConstantOperandVal(unsigned i) const;
   inline bool isTargetOpcode() const;
-  inline unsigned getTargetOpcode() const;
+  inline bool isMachineOpcode() const;
+  inline unsigned getMachineOpcode() const;
 
   
   /// reachesChainWithoutSideEffects - Return true if this operand (which must
@@ -1028,7 +1029,7 @@ class SDNode : public FoldingSetNode {
 private:
   /// NodeType - The operation that this node performs.
   ///
-  unsigned short NodeType;
+  short NodeType;
   
   /// OperandsNeedDelete - This is true if OperandList was new[]'d.  If true,
   /// then they will be delete[]'d when the node is destroyed.
@@ -1072,11 +1073,27 @@ public:
   //===--------------------------------------------------------------------===//
   //  Accessors
   //
-  unsigned getOpcode()  const { return NodeType; }
+
+  /// getOpcode - Return the SelectionDAG opcode value for this node. For
+  /// pre-isel nodes (those for which isMachineOpcode returns false), these
+  /// are the opcode values in the ISD and <target>ISD namespaces. For
+  /// post-isel opcodes, see getMachineOpcode.
+  unsigned getOpcode()  const { return (unsigned short)NodeType; }
+
+  /// isTargetOpcode - Test if this node has a target-specific opcode (in the
+  /// <target>ISD namespace).
   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
-  unsigned getTargetOpcode() const {
-    assert(isTargetOpcode() && "Not a target opcode!");
-    return NodeType - ISD::BUILTIN_OP_END;
+
+  /// isMachineOpcode - Test if this node has a post-isel opcode, directly
+  /// corresponding to a MachineInstr opcode.
+  bool isMachineOpcode() const { return NodeType < 0; }
+
+  /// getMachineOpcode - This may only be called if isMachineOpcode returns
+  /// true. It returns the MachineInstr opcode value that the node's opcode
+  /// corresponds to.
+  unsigned getMachineOpcode() const {
+    assert(isMachineOpcode() && "Not a target opcode!");
+    return ~NodeType;
   }
 
   size_t use_size() const { return std::distance(use_begin(), use_end()); }
@@ -1314,17 +1331,9 @@ protected:
   }
 
   /// 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 DropOperands();
   
-  /// 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 MorphNodeTo(unsigned Opc, SDVTList L,
-                   const SDOperand *Ops, unsigned NumOps,
-                   SmallVectorImpl<SDNode *> &DeadNodes);
-  
   void addUser(unsigned i, SDNode *User) {
     assert(User->OperandList[i].getUser() && "Node without parent");
     addUse(User->OperandList[i]);
@@ -1358,8 +1367,11 @@ inline uint64_t SDOperand::getConstantOperandVal(unsigned i) const {
 inline bool SDOperand::isTargetOpcode() const {
   return Val->isTargetOpcode();
 }
-inline unsigned SDOperand::getTargetOpcode() const {
-  return Val->getTargetOpcode();
+inline bool SDOperand::isMachineOpcode() const {
+  return Val->isMachineOpcode();
+}
+inline unsigned SDOperand::getMachineOpcode() const {
+  return Val->getMachineOpcode();
 }
 inline bool SDOperand::hasOneUse() const {
   return Val->hasNUsesOfValue(1, ResNo);
diff --git a/include/llvm/Support/Allocator.h b/include/llvm/Support/Allocator.h
index eab6d33..bc36535 100644
--- a/include/llvm/Support/Allocator.h
+++ b/include/llvm/Support/Allocator.h
@@ -58,6 +58,11 @@ public:
     return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
   }
   
+  template <typename T>
+  T *Allocate(size_t Num) { 
+    return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
+  }
+  
   void Deallocate(void * /*Ptr*/) {}
 
   void PrintStats() const;
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";
diff --git a/lib/Target/ARM/ARMISelDAGToDAG.cpp b/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 37d647b..2d1136f 100644
--- a/lib/Target/ARM/ARMISelDAGToDAG.cpp
+++ b/lib/Target/ARM/ARMISelDAGToDAG.cpp
@@ -530,9 +530,8 @@ static inline SDOperand getAL(SelectionDAG *CurDAG) {
 
 SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  unsigned Opcode = N->getOpcode();
 
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < ARMISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
diff --git a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
index 5275f7c..01a6856 100644
--- a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
+++ b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
@@ -244,8 +244,7 @@ void AlphaDAGToDAGISel::InstructionSelect(SelectionDAG &DAG) {
 // target-specific node if it hasn't already been changed.
 SDNode *AlphaDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < AlphaISD::FIRST_NUMBER) {
+  if (N->isMachineOpcode()) {
     return NULL;   // Already selected.
   }
 
diff --git a/lib/Target/CellSPU/SPUISelDAGToDAG.cpp b/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
index a672b13..0e935ac 100644
--- a/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
+++ b/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
@@ -587,7 +587,7 @@ SPUDAGToDAGISel::Select(SDOperand Op) {
   MVT OpVT = Op.getValueType();
   SDOperand Ops[8];
 
-  if (Opc >= ISD::BUILTIN_OP_END && Opc < SPUISD::FIRST_NUMBER) {
+  if (N->isMachineOpcode()) {
     return NULL;   // Already selected.
   } else if (Opc == ISD::FrameIndex) {
     // Selects to (add $sp, FI * stackSlotSize)
diff --git a/lib/Target/IA64/IA64ISelDAGToDAG.cpp b/lib/Target/IA64/IA64ISelDAGToDAG.cpp
index 06f6072..8f6840e 100644
--- a/lib/Target/IA64/IA64ISelDAGToDAG.cpp
+++ b/lib/Target/IA64/IA64ISelDAGToDAG.cpp
@@ -305,8 +305,7 @@ SDNode *IA64DAGToDAGISel::SelectDIV(SDOperand Op) {
 // target-specific node if it hasn't already been changed.
 SDNode *IA64DAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < IA64ISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
diff --git a/lib/Target/Mips/MipsISelDAGToDAG.cpp b/lib/Target/Mips/MipsISelDAGToDAG.cpp
index 0ea146b..388f5be 100644
--- a/lib/Target/Mips/MipsISelDAGToDAG.cpp
+++ b/lib/Target/Mips/MipsISelDAGToDAG.cpp
@@ -205,7 +205,7 @@ Select(SDOperand N)
   #endif
 
   // If we have a custom node, we already have selected!
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < MipsISD::FIRST_NUMBER) {
+  if (Node->isMachineOpcode()) {
     #ifndef NDEBUG
     DOUT << std::string(Indent-2, ' ') << "== ";
     DEBUG(Node->dump(CurDAG));
diff --git a/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp b/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp
index 5929675..509ba83 100644
--- a/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp
+++ b/lib/Target/PIC16/PIC16ISelDAGToDAG.cpp
@@ -239,7 +239,7 @@ SDNode* PIC16DAGToDAGISel::Select(SDOperand N)
 #endif
 
   // If we have a custom node, we already have selected!
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < PIC16ISD::FIRST_NUMBER) {
+  if (Node->isMachineOpcode()) {
 #ifndef NDEBUG
     DOUT << std::string(Indent-2, ' ') << "== ";
     DEBUG(Node->dump(CurDAG));
diff --git a/lib/Target/PowerPC/PPCHazardRecognizers.cpp b/lib/Target/PowerPC/PPCHazardRecognizers.cpp
index 58df0d6..717ce60 100644
--- a/lib/Target/PowerPC/PPCHazardRecognizers.cpp
+++ b/lib/Target/PowerPC/PPCHazardRecognizers.cpp
@@ -64,11 +64,11 @@ PPCHazardRecognizer970::GetInstrType(unsigned Opcode,
                                      bool &isFirst, bool &isSingle,
                                      bool &isCracked,
                                      bool &isLoad, bool &isStore) {
-  if (Opcode < ISD::BUILTIN_OP_END) {
+  if ((int)Opcode >= 0) {
     isFirst = isSingle = isCracked = isLoad = isStore = false;
     return PPCII::PPC970_Pseudo;
   }
-  Opcode -= ISD::BUILTIN_OP_END;
+  Opcode = ~Opcode;
   
   const TargetInstrDesc &TID = TII.get(Opcode);
   
@@ -125,7 +125,7 @@ getHazardType(SDNode *Node) {
     GetInstrType(Node->getOpcode(), isFirst, isSingle, isCracked,
                  isLoad, isStore);
   if (InstrType == PPCII::PPC970_Pseudo) return NoHazard;  
-  unsigned Opcode = Node->getOpcode()-ISD::BUILTIN_OP_END;
+  unsigned Opcode = Node->getMachineOpcode();
 
   // We can only issue a PPC970_First/PPC970_Single instruction (such as
   // crand/mtspr/etc) if this is the first cycle of the dispatch group.
@@ -223,7 +223,7 @@ void PPCHazardRecognizer970::EmitInstruction(SDNode *Node) {
     GetInstrType(Node->getOpcode(), isFirst, isSingle, isCracked,
                  isLoad, isStore);
   if (InstrType == PPCII::PPC970_Pseudo) return;  
-  unsigned Opcode = Node->getOpcode()-ISD::BUILTIN_OP_END;
+  unsigned Opcode = Node->getMachineOpcode();
 
   // Update structural hazard information.
   if (Opcode == PPC::MTCTR) HasCTRSet = true;
diff --git a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
index 09563c4..fb27999 100644
--- a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
+++ b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
@@ -775,8 +775,7 @@ SDNode *PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
 // target-specific node if it hasn't already been changed.
 SDNode *PPCDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < PPCISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
@@ -962,7 +961,8 @@ SDNode *PPCDAGToDAGISel::Select(SDOperand Op) {
       AddToISelQueue(Offset);
       SDOperand Ops[] = { Offset, Base, Chain };
       // FIXME: PPC64
-      return CurDAG->getTargetNode(Opcode, MVT::i32, MVT::i32,
+      return CurDAG->getTargetNode(Opcode, LD->getValueType(0),
+                                   PPCLowering.getPointerTy(),
                                    MVT::Other, Ops, 3);
     } else {
       assert(0 && "R+R preindex loads not supported yet!");
diff --git a/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index df07d51..d1d2b5b 100644
--- a/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
@@ -137,8 +137,7 @@ bool SparcDAGToDAGISel::SelectADDRrr(SDOperand Op, SDOperand Addr,
 
 SDNode *SparcDAGToDAGISel::Select(SDOperand Op) {
   SDNode *N = Op.Val;
-  if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
-      N->getOpcode() < SPISD::FIRST_NUMBER)
+  if (N->isMachineOpcode())
     return NULL;   // Already selected.
 
   switch (N->getOpcode()) {
diff --git a/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp
index e646d4d..74100f8 100644
--- a/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -1159,7 +1159,7 @@ SDNode *X86DAGToDAGISel::Select(SDOperand N) {
   Indent += 2;
 #endif
 
-  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER) {
+  if (Node->isMachineOpcode()) {
 #ifndef NDEBUG
     DOUT << std::string(Indent-2, ' ') << "== ";
     DEBUG(Node->dump(CurDAG));
diff --git a/lib/Target/X86/X86InstrInfo.cpp b/lib/Target/X86/X86InstrInfo.cpp
index 2f191ff..32eb53c 100644
--- a/lib/Target/X86/X86InstrInfo.cpp
+++ b/lib/Target/X86/X86InstrInfo.cpp
@@ -2239,11 +2239,11 @@ bool X86InstrInfo::unfoldMemoryOperand(MachineFunction &MF, MachineInstr *MI,
 bool
 X86InstrInfo::unfoldMemoryOperand(SelectionDAG &DAG, SDNode *N,
                                      SmallVectorImpl<SDNode*> &NewNodes) const {
-  if (!N->isTargetOpcode())
+  if (!N->isMachineOpcode())
     return false;
 
   DenseMap<unsigned*, std::pair<unsigned,unsigned> >::iterator I =
-    MemOp2RegOpTable.find((unsigned*)N->getTargetOpcode());
+    MemOp2RegOpTable.find((unsigned*)N->getMachineOpcode());
   if (I == MemOp2RegOpTable.end())
     return false;
   unsigned Opc = I->second.first;
diff --git a/test/CodeGen/PowerPC/LargeAbsoluteAddr.ll b/test/CodeGen/PowerPC/LargeAbsoluteAddr.ll
index f3ded0e..1705379 100644
--- a/test/CodeGen/PowerPC/LargeAbsoluteAddr.ll
+++ b/test/CodeGen/PowerPC/LargeAbsoluteAddr.ll
@@ -1,7 +1,7 @@
 ; RUN: llvm-as < %s | llc -march=ppc32 -mtriple=powerpc-apple-darwin | \
-; RUN:   grep {stw r2, 32751}
+; RUN:   grep {stw r3, 32751}
 ; RUN: llvm-as < %s | llc -march=ppc64 -mtriple=powerpc-apple-darwin | \
-; RUN:   grep {stw r2, 32751}
+; RUN:   grep {stw r3, 32751}
 ; RUN: llvm-as < %s | llc -march=ppc64 -mtriple=powerpc-apple-darwin | \
 ; RUN:   grep {std r2, 9024}
 
diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index bdb7fcf..2df9e88 100644
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -1157,7 +1157,8 @@ public:
       if (!isRoot)
         Code += "), 0";
 
-      bool NeedReplace = false;
+      std::vector<std::string> ReplaceFroms;
+      std::vector<std::string> ReplaceTos;
       if (!isRoot) {
         NodeOps.push_back("Tmp" + utostr(ResNo));
       } else {
@@ -1176,33 +1177,35 @@ public:
 
       if (FoldedChains.size() > 0) {
         std::string Code;
-        for (unsigned j = 0, e = FoldedChains.size(); j < e; j++)
-          After.push_back("ReplaceUses(SDOperand(" +
-                          FoldedChains[j].first + ".Val, " + 
-                          utostr(FoldedChains[j].second) +
-                          "), SDOperand(ResNode, " +
-                          utostr(NumResults+NumDstRegs) + "));");
-        NeedReplace = true;
+        for (unsigned j = 0, e = FoldedChains.size(); j < e; j++) {
+          ReplaceFroms.push_back("SDOperand(" +
+                                 FoldedChains[j].first + ".Val, " +
+                                 utostr(FoldedChains[j].second) +
+                                 ")");
+          ReplaceTos.push_back("SDOperand(ResNode, " +
+                               utostr(NumResults+NumDstRegs) + ")");
+        }
       }
 
       if (NodeHasOutFlag) {
         if (FoldedFlag.first != "") {
-          After.push_back("ReplaceUses(SDOperand(" + FoldedFlag.first +
-                          ".Val, " +
-                          utostr(FoldedFlag.second) + "), InFlag);");
+          ReplaceFroms.push_back("SDOperand(" + FoldedFlag.first + ".Val, " +
+                                 utostr(FoldedFlag.second) + ")");
+          ReplaceTos.push_back("InFlag");
         } else {
           assert(NodeHasProperty(Pattern, SDNPOutFlag, CGP));
-          After.push_back("ReplaceUses(SDOperand(N.Val, " +
-                          utostr(NumPatResults + (unsigned)InputHasChain)
-                          +"), InFlag);");
+          ReplaceFroms.push_back("SDOperand(N.Val, " +
+                                 utostr(NumPatResults + (unsigned)InputHasChain)
+                                 + ")");
+          ReplaceTos.push_back("InFlag");
         }
-        NeedReplace = true;
       }
 
-      if (NeedReplace && InputHasChain) {
-        After.push_back("ReplaceUses(SDOperand(N.Val, " + 
-                        utostr(NumPatResults) + "), SDOperand(" + ChainName
-                        + ".Val, " + ChainName + ".ResNo" + "));");
+      if (!ReplaceFroms.empty() && InputHasChain) {
+        ReplaceFroms.push_back("SDOperand(N.Val, " +
+                               utostr(NumPatResults) + ")");
+        ReplaceTos.push_back("SDOperand(" + ChainName + ".Val, " +
+                             ChainName + ".ResNo" + ")");
         ChainAssignmentNeeded |= NodeHasChain;
       }
 
@@ -1211,13 +1214,15 @@ public:
         ;
       } else if (InputHasChain && !NodeHasChain) {
         // One of the inner node produces a chain.
-        if (NodeHasOutFlag)
-          After.push_back("ReplaceUses(SDOperand(N.Val, " +
-                          utostr(NumPatResults+1) +
-                          "), SDOperand(ResNode, N.ResNo-1));");
-        After.push_back("ReplaceUses(SDOperand(N.Val, " +
-                        utostr(NumPatResults) + "), " + ChainName + ");");
-        NeedReplace = true;
+        if (NodeHasOutFlag) {
+          ReplaceFroms.push_back("SDOperand(N.Val, " +
+                                 utostr(NumPatResults+1) +
+                                 ")");
+          ReplaceTos.push_back("SDOperand(ResNode, N.ResNo-1)");
+        }
+        ReplaceFroms.push_back("SDOperand(N.Val, " +
+                               utostr(NumPatResults) + ")");
+        ReplaceTos.push_back(ChainName);
       }
       }
 
@@ -1234,21 +1239,31 @@ public:
         After.push_front(ChainAssign);
       }
 
-      // Use getTargetNode or SelectNodeTo? The safe choice is getTargetNode,
-      // but SelectNodeTo can be faster.
-      //
-      // SelectNodeTo is not safe in a non-root context, or if there is any
-      // replacement of results needed.
+      if (ReplaceFroms.size() == 1) {
+        After.push_back("ReplaceUses(" + ReplaceFroms[0] + ", " +
+                        ReplaceTos[0] + ");");
+      } else if (!ReplaceFroms.empty()) {
+        After.push_back("const SDOperand Froms[] = {");
+        for (unsigned i = 0, e = ReplaceFroms.size(); i != e; ++i)
+          After.push_back("  " + ReplaceFroms[i] + (i + 1 != e ? "," : ""));
+        After.push_back("};");
+        After.push_back("const SDOperand Tos[] = {");
+        for (unsigned i = 0, e = ReplaceFroms.size(); i != e; ++i)
+          After.push_back("  " + ReplaceTos[i] + (i + 1 != e ? "," : ""));
+        After.push_back("};");
+        After.push_back("ReplaceUses(Froms, Tos, " +
+                        itostr(ReplaceFroms.size()) + ");");
+      }
+
+      // We prefer to use SelectNodeTo since it avoids allocation when
+      // possible and it avoids CSE map recalculation for the node's
+      // users, however it's tricky to use in a non-root context.
       //
-      // SelectNodeTo is not profitable if it would require a dynamically
-      // allocated operand list in a situation where getTargetNode would be
-      // able to reuse a co-allocated operand list (as in a unary, binary or
-      // ternary SDNode, for example).
+      // We also don't use if the pattern replacement is being used to
+      // jettison a chain result, since morphing the node in place
+      // would leave users of the chain dangling.
       //
-      if (!isRoot || NeedReplace ||
-          (!IsVariadic && AllOps.size() < 4 &&
-           Pattern->getNumChildren() + InputHasChain + NodeHasInFlag <
-             AllOps.size())) {
+      if (!isRoot || (InputHasChain && !NodeHasChain)) {
         Code = "CurDAG->getTargetNode(" + Code;
       } else {
         Code = "CurDAG->SelectNodeTo(N.Val, " + Code;
@@ -1952,9 +1967,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
 
   OS << "// The main instruction selector code.\n"
      << "SDNode *SelectCode(SDOperand N) {\n"
-     << "  if (N.getOpcode() >= ISD::BUILTIN_OP_END &&\n"
-     << "      N.getOpcode() < (ISD::BUILTIN_OP_END+" << InstNS
-     << "INSTRUCTION_LIST_END)) {\n"
+     << "  if (N.isMachineOpcode()) {\n"
      << "    return NULL;   // Already selected.\n"
      << "  }\n\n"
      << "  MVT::SimpleValueType NVT = N.Val->getValueType(0).getSimpleVT();\n"