diff --git a/lib/Target/ARM/ARMISelDAGToDAG.cpp b/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 34d972f..915684a 100644
--- a/lib/Target/ARM/ARMISelDAGToDAG.cpp
+++ b/lib/Target/ARM/ARMISelDAGToDAG.cpp
@@ -26,6 +26,7 @@
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Support/Debug.h"
 #include <iostream>
+#include <queue>
 #include <set>
 using namespace llvm;
 
@@ -306,9 +307,6 @@
   DEBUG(BB->dump());
 
   DAG.setRoot(SelectRoot(DAG.getRoot()));
-  CodeGenMap.clear();
-  HandleMap.clear();
-  ReplaceMap.clear();
   DAG.RemoveDeadNodes();
 
   ScheduleAndEmitDAG(DAG);
diff --git a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
index 78a7814..811aab8 100644
--- a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
+++ b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
@@ -30,6 +30,7 @@
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <iostream>
+#include <queue>
 #include <set>
 using namespace llvm;
 
@@ -129,7 +130,7 @@
       switch (ConstraintCode) {
       default: return true;
       case 'm':   // memory
-	Select(Op0, Op);
+	AddToQueue(Op0, Op);
         break;
       }
       
@@ -172,9 +173,6 @@
   
   // Select target instructions for the DAG.
   DAG.setRoot(SelectRoot(DAG.getRoot()));
-  CodeGenMap.clear();
-  HandleMap.clear();
-  ReplaceMap.clear();
   DAG.RemoveDeadNodes();
   
   // Emit machine code to BB. 
@@ -191,13 +189,6 @@
     return;   // Already selected.
   }
 
-  // If this has already been converted, use it.
-  std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
-  if (CGMI != CodeGenMap.end()) {
-    Result = CGMI->second;
-    return;
-  }
-
   switch (N->getOpcode()) {
   default: break;
   case AlphaISD::CALL:
@@ -213,17 +204,19 @@
   }
   case AlphaISD::GlobalBaseReg: 
     Result = getGlobalBaseReg();
+    ReplaceUses(Op, Result);
     return;
   case AlphaISD::GlobalRetAddr:
     Result = getGlobalRetAddr();
+    ReplaceUses(Op, Result);
     return;
   
   case AlphaISD::DivCall: {
     SDOperand Chain = CurDAG->getEntryNode();
     SDOperand N0, N1, N2;
-    Select(N0, Op.getOperand(0));
-    Select(N1, Op.getOperand(1));
-    Select(N2, Op.getOperand(2));
+    AddToQueue(N0, Op.getOperand(0));
+    AddToQueue(N1, Op.getOperand(1));
+    AddToQueue(N2, Op.getOperand(2));
     Chain = CurDAG->getCopyToReg(Chain, Alpha::R24, N1, 
 				 SDOperand(0,0));
     Chain = CurDAG->getCopyToReg(Chain, Alpha::R25, N2, 
@@ -241,8 +234,11 @@
 
   case ISD::READCYCLECOUNTER: {
     SDOperand Chain;
-    Select(Chain, N->getOperand(0)); //Select chain
-    Result = CurDAG->SelectNodeTo(N, Alpha::RPCC, MVT::i64, Chain);
+    AddToQueue(Chain, N->getOperand(0)); //Select chain
+    Result = SDOperand(CurDAG->getTargetNode(Alpha::RPCC, MVT::i64, MVT::Other,
+                                             Chain), Op.ResNo);
+    ReplaceUses(Op.getValue(0), Result.getValue(0));
+    ReplaceUses(Op.getValue(1), Result.getValue(1));
     return;
   }
 
@@ -252,6 +248,7 @@
     if (uval == 0) {
       Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), Alpha::R31,
                                       MVT::i64);
+      ReplaceUses(Op, Result);
       return;
     }
 
@@ -311,8 +308,8 @@
       case ISD::SETNE: case ISD::SETONE: case ISD::SETUNE: Opc = Alpha::CMPTEQ; isNE = true; break;
       };
       SDOperand tmp1, tmp2;
-      Select(tmp1, N->getOperand(0));
-      Select(tmp2, N->getOperand(1));
+      AddToQueue(tmp1, N->getOperand(0));
+      AddToQueue(tmp2, N->getOperand(1));
       SDNode *cmp = CurDAG->getTargetNode(Opc, MVT::f64, 
                                           rev?tmp2:tmp1,
                                           rev?tmp1:tmp2);
@@ -338,6 +335,7 @@
       Result = SDOperand(CurDAG->getTargetNode(Alpha::CMPULT, MVT::i64, 
                                                CurDAG->getRegister(Alpha::R31, MVT::i64),
                                                LD), 0);
+      ReplaceUses(Op, Result);
       return;
     }
     break;
@@ -352,9 +350,9 @@
       //move int to fp
       bool isDouble = N->getValueType(0) == MVT::f64;
       SDOperand LD, cond, TV, FV;
-      Select(cond, N->getOperand(0));
-      Select(TV, N->getOperand(1));
-      Select(FV, N->getOperand(2));
+      AddToQueue(cond, N->getOperand(0));
+      AddToQueue(TV, N->getOperand(1));
+      AddToQueue(FV, N->getOperand(2));
       
       if (AlphaLowering.hasITOF()) {
 	LD = CurDAG->getNode(AlphaISD::ITOFT_, MVT::f64, cond);
@@ -371,6 +369,7 @@
       }
       Result = SDOperand(CurDAG->getTargetNode(isDouble?Alpha::FCMOVNET:Alpha::FCMOVNES,
                                                MVT::f64, FV, TV, LD), 0);
+      ReplaceUses(Op, Result);
       return;
     }
     break;
@@ -396,12 +395,13 @@
 
 	if (get_zapImm(mask)) {
 	  SDOperand Src;
-	  Select(Src, N->getOperand(0).getOperand(0));
+	  AddToQueue(Src, N->getOperand(0).getOperand(0));
 	  SDOperand Z = 
 	    SDOperand(CurDAG->getTargetNode(Alpha::ZAPNOTi, MVT::i64, Src, 
 					    getI64Imm(get_zapImm(mask))), 0);
 	  Result = SDOperand(CurDAG->getTargetNode(Alpha::SRL, MVT::i64, Z, 
 						   getI64Imm(sval)), 0);
+          ReplaceUses(Op, Result);
 	  return;
 	}
       }
@@ -420,7 +420,7 @@
   SDOperand Chain;
   SDOperand Addr = N->getOperand(1);
   SDOperand InFlag(0,0);  // Null incoming flag value.
-  Select(Chain, N->getOperand(0));
+  AddToQueue(Chain, N->getOperand(0));
 
    std::vector<SDOperand> CallOperands;
    std::vector<MVT::ValueType> TypeOperands;
@@ -429,7 +429,7 @@
    for(int i = 2, e = N->getNumOperands(); i < e; ++i) {
      SDOperand Tmp;
      TypeOperands.push_back(N->getOperand(i).getValueType());
-     Select(Tmp, N->getOperand(i));
+     AddToQueue(Tmp, N->getOperand(i));
      CallOperands.push_back(Tmp);
    }
    int count = N->getNumOperands() - 2;
@@ -474,7 +474,7 @@
      Chain = SDOperand(CurDAG->getTargetNode(Alpha::BSR, MVT::Other, MVT::Flag, 
                                              Addr.getOperand(0), Chain, InFlag), 0);
    } else {
-     Select(Addr, Addr);
+     AddToQueue(Addr, Addr);
      Chain = CurDAG->getCopyToReg(Chain, Alpha::R27, Addr, InFlag);
      InFlag = Chain.getValue(1);
      Chain = SDOperand(CurDAG->getTargetNode(Alpha::JSR, MVT::Other, MVT::Flag, 
@@ -503,7 +503,7 @@
 
    CallResults.push_back(Chain);
    for (unsigned i = 0, e = CallResults.size(); i != e; ++i)
-     CodeGenMap[Op.getValue(i)] = CallResults[i];
+     ReplaceUses(Op.getValue(i), CallResults[i]);
    return CallResults[Op.ResNo];
 }
 
diff --git a/lib/Target/IA64/IA64ISelDAGToDAG.cpp b/lib/Target/IA64/IA64ISelDAGToDAG.cpp
index fe5a7bb..8013f87 100644
--- a/lib/Target/IA64/IA64ISelDAGToDAG.cpp
+++ b/lib/Target/IA64/IA64ISelDAGToDAG.cpp
@@ -28,6 +28,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
 #include <iostream>
+#include <queue>
 #include <set>
 using namespace llvm;
 
@@ -101,50 +102,9 @@
 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 void IA64DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
   DEBUG(BB->dump());
-  
-  // The selection process is inherently a bottom-up recursive process (users
-  // select their uses before themselves).  Given infinite stack space, we
-  // could just start selecting on the root and traverse the whole graph.  In
-  // practice however, this causes us to run out of stack space on large basic
-  // blocks.  To avoid this problem, select the entry node, then all its uses,
-  // iteratively instead of recursively.
-  std::vector<SDOperand> Worklist;
-  Worklist.push_back(DAG.getEntryNode());
-  
-  // Note that we can do this in the IA64 target (scanning forward across token
-  // chain edges) because no nodes ever get folded across these edges.  On a
-  // target like X86 which supports load/modify/store operations, this would
-  // have to be more careful.
-  while (!Worklist.empty()) {
-    SDOperand Node = Worklist.back();
-    Worklist.pop_back();
 
-    if ((Node.Val->getOpcode() >= ISD::BUILTIN_OP_END &&
-         Node.Val->getOpcode() < IA64ISD::FIRST_NUMBER) ||
-        CodeGenMap.count(Node)) continue;
-    
-    for (SDNode::use_iterator UI = Node.Val->use_begin(),
-         E = Node.Val->use_end(); UI != E; ++UI) {
-      // Scan the values.  If this use has a value that is a token chain, add it
-      // to the worklist.
-      SDNode *User = *UI;
-      for (unsigned i = 0, e = User->getNumValues(); i != e; ++i)
-        if (User->getValueType(i) == MVT::Other) {
-          Worklist.push_back(SDOperand(User, i));
-          break; 
-        }
-    }
-
-    // Finally, legalize this node.
-    SDOperand Dummy;
-    Select(Dummy, Node);
-  }
-    
   // Select target instructions for the DAG.
   DAG.setRoot(SelectRoot(DAG.getRoot()));
-  CodeGenMap.clear();
-  HandleMap.clear();
-  ReplaceMap.clear();
   DAG.RemoveDeadNodes();
   
   // Emit machine code to BB. 
@@ -154,10 +114,10 @@
 SDOperand IA64DAGToDAGISel::SelectDIV(SDOperand Op) {
   SDNode *N = Op.Val;
   SDOperand Chain, Tmp1, Tmp2;
-  Select(Chain, N->getOperand(0));
+  AddToQueue(Chain, N->getOperand(0));
 
-  Select(Tmp1, N->getOperand(0));
-  Select(Tmp2, N->getOperand(1));
+  AddToQueue(Tmp1, N->getOperand(0));
+  AddToQueue(Tmp2, N->getOperand(1));
 
   bool isFP=false;
 
@@ -344,13 +304,6 @@
     return;   // Already selected.
   }
 
-  // If this has already been converted, use it.
-  std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
-  if (CGMI != CodeGenMap.end()) {
-    Result = CGMI->second;
-    return;
-  }
-  
   switch (N->getOpcode()) {
   default: break;
 
@@ -358,9 +311,9 @@
     SDOperand Chain;
     SDOperand InFlag;  // Null incoming flag value.
 
-    Select(Chain, N->getOperand(0));
+    AddToQueue(Chain, N->getOperand(0));
     if(N->getNumOperands()==3) // we have an incoming chain, callee and flag
-      Select(InFlag, N->getOperand(2));
+      AddToQueue(InFlag, N->getOperand(2));
 
     unsigned CallOpcode;
     SDOperand CallOperand;
@@ -382,7 +335,7 @@
     // load the branch target (function)'s entry point and GP,
     // branch (call) then restore the GP
     SDOperand FnDescriptor;
-    Select(FnDescriptor, N->getOperand(1));
+    AddToQueue(FnDescriptor, N->getOperand(1));
    
     // load the branch target's entry point [mem] and 
     // GP value [mem+8]
@@ -421,16 +374,16 @@
    CallResults.push_back(InFlag);
 
    for (unsigned i = 0, e = CallResults.size(); i != e; ++i)
-     CodeGenMap[Op.getValue(i)] = CallResults[i];
+     ReplaceUses(Op.getValue(i), CallResults[i]);
    Result = CallResults[Op.ResNo];
    return;
   }
   
   case IA64ISD::GETFD: {
     SDOperand Input;
-    Select(Input, N->getOperand(0));
+    AddToQueue(Input, N->getOperand(0));
     Result = SDOperand(CurDAG->getTargetNode(IA64::GETFD, MVT::i64, Input), 0);
-    CodeGenMap[Op] = Result;
+    ReplaceUses(Op, Result);
     return;
   } 
   
@@ -440,6 +393,7 @@
   case ISD::SREM:
   case ISD::UREM:
     Result = SelectDIV(Op);
+    ReplaceUses(Op, Result);
     return;
  
   case ISD::TargetConstantFP: {
@@ -459,9 +413,11 @@
     if (N->hasOneUse())
       Result = CurDAG->SelectNodeTo(N, IA64::MOV, MVT::i64,
                                   CurDAG->getTargetFrameIndex(FI, MVT::i64));
-    else
-      Result = CodeGenMap[Op] = SDOperand(CurDAG->getTargetNode(IA64::MOV, MVT::i64,
+    else {
+      Result = SDOperand(CurDAG->getTargetNode(IA64::MOV, MVT::i64,
                                 CurDAG->getTargetFrameIndex(FI, MVT::i64)), 0);
+      ReplaceUses(Op, Result);
+    }
     return;
   }
 
@@ -473,6 +429,7 @@
                                                   CP->getAlignment());
     Result = SDOperand(CurDAG->getTargetNode(IA64::ADDL_GA, MVT::i64, // ?
 	                      CurDAG->getRegister(IA64::r1, MVT::i64), CPI), 0);
+    ReplaceUses(Op, Result);
     return;
   }
 
@@ -482,6 +439,7 @@
     SDOperand Tmp = SDOperand(CurDAG->getTargetNode(IA64::ADDL_GA, MVT::i64, 
 	                          CurDAG->getRegister(IA64::r1, MVT::i64), GA), 0);
     Result = SDOperand(CurDAG->getTargetNode(IA64::LD8, MVT::i64, Tmp), 0);
+    ReplaceUses(Op, Result);
     return;
   }
   
@@ -498,8 +456,8 @@
   case ISD::EXTLOAD: // FIXME: load -1, not 1, for bools?
   case ISD::ZEXTLOAD: {
     SDOperand Chain, Address;
-    Select(Chain, N->getOperand(0));
-    Select(Address, N->getOperand(1));
+    AddToQueue(Chain, N->getOperand(0));
+    AddToQueue(Address, N->getOperand(1));
 
     MVT::ValueType TypeBeingLoaded = (N->getOpcode() == ISD::LOAD) ?
       N->getValueType(0) : cast<VTSDNode>(N->getOperand(3))->getVT();
@@ -540,8 +498,8 @@
   case ISD::TRUNCSTORE:
   case ISD::STORE: {
     SDOperand Address, Chain;
-    Select(Address, N->getOperand(2));
-    Select(Chain, N->getOperand(0));
+    AddToQueue(Address, N->getOperand(2));
+    AddToQueue(Chain, N->getOperand(0));
    
     unsigned Opc;
     if (N->getOpcode() == ISD::STORE) {
@@ -554,7 +512,7 @@
 	Chain = Initial.getValue(1);
 	// then load 1 into the same reg iff the predicate to store is 1
         SDOperand Tmp;
-        Select(Tmp, N->getOperand(1));
+        AddToQueue(Tmp, N->getOperand(1));
         Tmp = SDOperand(CurDAG->getTargetNode(IA64::TPCADDS, MVT::i64, Initial,
                                               CurDAG->getConstant(1, MVT::i64),
                                               Tmp), 0);
@@ -575,16 +533,16 @@
     }
     
     SDOperand N1, N2;
-    Select(N1, N->getOperand(1));
-    Select(N2, N->getOperand(2));
+    AddToQueue(N1, N->getOperand(1));
+    AddToQueue(N2, N->getOperand(2));
     Result = CurDAG->SelectNodeTo(N, Opc, MVT::Other, N2, N1, Chain);
     return;
   }
 
   case ISD::BRCOND: {
     SDOperand Chain, CC;
-    Select(Chain, N->getOperand(0));
-    Select(CC, N->getOperand(1));
+    AddToQueue(Chain, N->getOperand(0));
+    AddToQueue(CC, N->getOperand(1));
     MachineBasicBlock *Dest =
       cast<BasicBlockSDNode>(N->getOperand(2))->getBasicBlock();
     //FIXME - we do NOT need long branches all the time
@@ -599,7 +557,7 @@
     unsigned Opc = N->getOpcode() == ISD::CALLSEQ_START ?
                        IA64::ADJUSTCALLSTACKDOWN : IA64::ADJUSTCALLSTACKUP;
     SDOperand N0;
-    Select(N0, N->getOperand(0));
+    AddToQueue(N0, N->getOperand(0));
     Result = CurDAG->SelectNodeTo(N, Opc, MVT::Other, getI64Imm(Amt), N0);
     return;
   }
@@ -607,7 +565,7 @@
   case ISD::BR:
 		 // FIXME: we don't need long branches all the time!
     SDOperand N0;
-    Select(N0, N->getOperand(0));
+    AddToQueue(N0, N->getOperand(0));
     Result = CurDAG->SelectNodeTo(N, IA64::BRL_NOTCALL, MVT::Other, 
                                 N->getOperand(1), N0);
     return;
diff --git a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
index 937092a..4346c5e 100644
--- a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
+++ b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
@@ -30,6 +30,7 @@
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Visibility.h"
 #include <iostream>
+#include <queue>
 #include <set>
 using namespace llvm;
 
@@ -123,7 +124,7 @@
         break;
       case 'o':   // offsetable
         if (!SelectAddrImm(Op, Op0, Op1)) {
-          Select(Op0, Op);     // r+0.
+          AddToQueue(Op0, Op);     // r+0.
           Op1 = getSmallIPtrImm(0);
         }
         break;
@@ -174,50 +175,9 @@
 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 void PPCDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
   DEBUG(BB->dump());
-  
-  // The selection process is inherently a bottom-up recursive process (users
-  // select their uses before themselves).  Given infinite stack space, we
-  // could just start selecting on the root and traverse the whole graph.  In
-  // practice however, this causes us to run out of stack space on large basic
-  // blocks.  To avoid this problem, select the entry node, then all its uses,
-  // iteratively instead of recursively.
-  std::vector<SDOperand> Worklist;
-  Worklist.push_back(DAG.getEntryNode());
-  
-  // Note that we can do this in the PPC target (scanning forward across token
-  // chain edges) because no nodes ever get folded across these edges.  On a
-  // target like X86 which supports load/modify/store operations, this would
-  // have to be more careful.
-  while (!Worklist.empty()) {
-    SDOperand Node = Worklist.back();
-    Worklist.pop_back();
 
-    if ((Node.Val->getOpcode() >= ISD::BUILTIN_OP_END &&
-         Node.Val->getOpcode() < PPCISD::FIRST_NUMBER) ||
-        CodeGenMap.count(Node)) continue;
-    
-    for (SDNode::use_iterator UI = Node.Val->use_begin(),
-         E = Node.Val->use_end(); UI != E; ++UI) {
-      // Scan the values.  If this use has a value that is a token chain, add it
-      // to the worklist.
-      SDNode *User = *UI;
-      for (unsigned i = 0, e = User->getNumValues(); i != e; ++i)
-        if (User->getValueType(i) == MVT::Other) {
-          Worklist.push_back(SDOperand(User, i));
-          break; 
-        }
-    }
-
-    // Finally, legalize this node.
-    SDOperand Dummy;
-    Select(Dummy, Node);
-  }
-    
   // Select target instructions for the DAG.
   DAG.setRoot(SelectRoot(DAG.getRoot()));
-  CodeGenMap.clear();
-  HandleMap.clear();
-  ReplaceMap.clear();
   DAG.RemoveDeadNodes();
   
   // Emit machine code to BB.
@@ -493,8 +453,8 @@
       }
       
       Tmp3 = (Op0Opc == ISD::AND && DisjointMask) ? Op0.getOperand(0) : Op0;
-      Select(Tmp1, Tmp3);
-      Select(Tmp2, Op1);
+      AddToQueue(Tmp1, Tmp3);
+      AddToQueue(Tmp2, Op1);
       SH &= 31;
       return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Tmp1, Tmp2,
                                    getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
@@ -732,7 +692,7 @@
 SDOperand PPCDAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
                                     ISD::CondCode CC) {
   // Always select the LHS.
-  Select(LHS, LHS);
+  AddToQueue(LHS, LHS);
   unsigned Opc;
   
   if (LHS.getValueType() == MVT::i32) {
@@ -771,7 +731,7 @@
     assert(LHS.getValueType() == MVT::f64 && "Unknown vt!");
     Opc = PPC::FCMPUD;
   }
-  Select(RHS, RHS);
+  AddToQueue(RHS, RHS);
   return SDOperand(CurDAG->getTargetNode(Opc, MVT::i32, LHS, RHS), 0);
 }
 
@@ -845,7 +805,7 @@
     // setcc op, 0
     if (Imm == 0) {
       SDOperand Op;
-      Select(Op, N->getOperand(0));
+      AddToQueue(Op, N->getOperand(0));
       switch (CC) {
       default: break;
       case ISD::SETEQ:
@@ -872,7 +832,7 @@
       }
     } else if (Imm == ~0U) {        // setcc op, -1
       SDOperand Op;
-      Select(Op, N->getOperand(0));
+      AddToQueue(Op, N->getOperand(0));
       switch (CC) {
       default: break;
       case ISD::SETEQ:
@@ -948,13 +908,6 @@
     return;   // Already selected.
   }
 
-  // If this has already been converted, use it.
-  std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
-  if (CGMI != CodeGenMap.end()) {
-    Result = CGMI->second;
-    return;
-  }
-  
   switch (N->getOpcode()) {
   default: break;
   case ISD::SETCC:
@@ -962,6 +915,7 @@
     return;
   case PPCISD::GlobalBaseReg:
     Result = getGlobalBaseReg();
+    ReplaceUses(Op, Result);
     return;
     
   case ISD::FrameIndex: {
@@ -973,22 +927,23 @@
                                     getSmallIPtrImm(0));
       return;
     }
-    Result = CodeGenMap[Op] = 
+    Result =
       SDOperand(CurDAG->getTargetNode(Opc, Op.getValueType(), TFI,
                                       getSmallIPtrImm(0)), 0);
+    ReplaceUses(Op, Result);
     return;
   }
 
   case PPCISD::MFCR: {
     SDOperand InFlag;
-    Select(InFlag, N->getOperand(1));
+    AddToQueue(InFlag, N->getOperand(1));
     // Use MFOCRF if supported.
     if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
       Result = SDOperand(CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32,
                                                N->getOperand(0), InFlag), 0);
     else
       Result = SDOperand(CurDAG->getTargetNode(PPC::MFCR, MVT::i32, InFlag), 0);
-    CodeGenMap[Op] = Result;
+    ReplaceUses(Op, Result);
     return;
   }
     
@@ -1001,7 +956,7 @@
     unsigned Imm;
     if (isInt32Immediate(N->getOperand(1), Imm)) {
       SDOperand N0;
-      Select(N0, N->getOperand(0));
+      AddToQueue(N0, N->getOperand(0));
       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
         SDNode *Op =
           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
@@ -1033,13 +988,13 @@
       SDOperand Val;
       unsigned SH, MB, ME;
       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
-        Select(Val, N->getOperand(0).getOperand(0));
+        AddToQueue(Val, N->getOperand(0).getOperand(0));
       } else if (Imm == 0) {
         // AND X, 0 -> 0, not "rlwinm 32".
-        Select(Result, N->getOperand(1));
+        AddToQueue(Result, N->getOperand(1));
         return ;
       } else {        
-        Select(Val, N->getOperand(0));
+        AddToQueue(Val, N->getOperand(0));
         isRunOfOnes(Imm, MB, ME);
         SH = 0;
       }
@@ -1057,12 +1012,13 @@
       Imm = ~(Imm^Imm2);
       if (isRunOfOnes(Imm, MB, ME)) {
         SDOperand Tmp1, Tmp2;
-        Select(Tmp1, N->getOperand(0).getOperand(0));
-        Select(Tmp2, N->getOperand(0).getOperand(1));
+        AddToQueue(Tmp1, N->getOperand(0).getOperand(0));
+        AddToQueue(Tmp2, N->getOperand(0).getOperand(1));
         Result = SDOperand(CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32,
                                                  Tmp1, Tmp2,
                                                  getI32Imm(0), getI32Imm(MB),
                                                  getI32Imm(ME)), 0);
+        ReplaceUses(Op, Result);
         return;
       }
     }
@@ -1073,7 +1029,8 @@
   case ISD::OR:
     if (N->getValueType(0) == MVT::i32)
       if (SDNode *I = SelectBitfieldInsert(N)) {
-        Result = CodeGenMap[Op] = SDOperand(I, 0);
+        Result = SDOperand(I, 0);
+        ReplaceUses(Op, Result);
         return;
       }
       
@@ -1084,7 +1041,7 @@
     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
       SDOperand Val;
-      Select(Val, N->getOperand(0).getOperand(0));
+      AddToQueue(Val, N->getOperand(0).getOperand(0));
       Result = CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, 
                                     Val, getI32Imm(SH), getI32Imm(MB),
                                     getI32Imm(ME));
@@ -1099,7 +1056,7 @@
     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
         isRotateAndMask(N, Imm, true, SH, MB, ME)) { 
       SDOperand Val;
-      Select(Val, N->getOperand(0).getOperand(0));
+      AddToQueue(Val, N->getOperand(0).getOperand(0));
       Result = CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, 
                                     Val, getI32Imm(SH), getI32Imm(MB),
                                     getI32Imm(ME));
@@ -1121,7 +1078,7 @@
               // FIXME: Implement this optzn for PPC64.
               N->getValueType(0) == MVT::i32) {
             SDOperand LHS;
-            Select(LHS, N->getOperand(0));
+            AddToQueue(LHS, N->getOperand(0));
             SDNode *Tmp =
               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
                                     LHS, getI32Imm(~0U));
@@ -1148,15 +1105,15 @@
       SelectCCOp = PPC::SELECT_CC_VRRC;
 
     SDOperand N2, N3;
-    Select(N2, N->getOperand(2));
-    Select(N3, N->getOperand(3));
+    AddToQueue(N2, N->getOperand(2));
+    AddToQueue(N3, N->getOperand(3));
     Result = CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), CCReg,
                                   N2, N3, getI32Imm(BROpc));
     return;
   }
   case ISD::BR_CC: {
     SDOperand Chain;
-    Select(Chain, N->getOperand(0));
+    AddToQueue(Chain, N->getOperand(0));
     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
     Result = CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other, 
@@ -1167,8 +1124,8 @@
   case ISD::BRIND: {
     // FIXME: Should custom lower this.
     SDOperand Chain, Target;
-    Select(Chain, N->getOperand(0));
-    Select(Target,N->getOperand(1));
+    AddToQueue(Chain, N->getOperand(0));
+    AddToQueue(Target,N->getOperand(1));
     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
     Chain = SDOperand(CurDAG->getTargetNode(Opc, MVT::Other, Target,
                                             Chain), 0);
@@ -1198,25 +1155,23 @@
   std::vector<SDOperand> Ops;
   // Push varargs arguments, including optional flag.
   for (unsigned i = 1, e = N.getNumOperands()-hasFlag; i != e; ++i) {
-    Select(Chain, N.getOperand(i));
+    AddToQueue(Chain, N.getOperand(i));
     Ops.push_back(Chain);
   }
 
-  Select(Chain, N.getOperand(0));
+  AddToQueue(Chain, N.getOperand(0));
   Ops.push_back(Chain);
 
   if (hasFlag) {
-    Select(Chain, N.getOperand(N.getNumOperands()-1));
+    AddToQueue(Chain, N.getOperand(N.getNumOperands()-1));
     Ops.push_back(Chain);
   }
   
   ResNode = CurDAG->getTargetNode(PPC::BCTRL, MVT::Other, MVT::Flag, Ops);
   Chain = SDOperand(ResNode, 0);
   InFlag = SDOperand(ResNode, 1);
-  SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, Chain.Val,
-                                   Chain.ResNo);
-  SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, InFlag.Val,
-                                   InFlag.ResNo);
+  ReplaceUses(SDOperand(N.Val, 0), Chain);
+  ReplaceUses(SDOperand(N.Val, 1), InFlag);
   Result = SDOperand(ResNode, N.ResNo);
   return;
 }
@@ -1246,23 +1201,21 @@
     
     // Push varargs arguments, not including optional flag.
     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
-      Select(Chain, N.getOperand(i));
+      AddToQueue(Chain, N.getOperand(i));
       Ops.push_back(Chain);
     }
-    Select(Chain, N.getOperand(0));
+    AddToQueue(Chain, N.getOperand(0));
     Ops.push_back(Chain);
     if (hasFlag) {
-      Select(Chain, N.getOperand(N.getNumOperands()-1));
+      AddToQueue(Chain, N.getOperand(N.getNumOperands()-1));
       Ops.push_back(Chain);
     }
     ResNode = CurDAG->getTargetNode(PPC::BLA, MVT::Other, MVT::Flag, Ops);
     
     Chain = SDOperand(ResNode, 0);
     InFlag = SDOperand(ResNode, 1);
-    SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, Chain.Val, 
-                                     Chain.ResNo);
-    SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, InFlag.Val, 
-                                     InFlag.ResNo);
+    ReplaceUses(SDOperand(N.Val, 0), Chain);
+    ReplaceUses(SDOperand(N.Val, 1), InFlag);
     Result = SDOperand(ResNode, N.ResNo);
     return;
   }
@@ -1279,13 +1232,13 @@
 
     // Push varargs arguments, not including optional flag.
     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
-      Select(Chain, N.getOperand(i));
+      AddToQueue(Chain, N.getOperand(i));
       Ops.push_back(Chain);
     }
-    Select(Chain, N.getOperand(0));
+    AddToQueue(Chain, N.getOperand(0));
     Ops.push_back(Chain);
     if (hasFlag) {
-      Select(Chain, N.getOperand(N.getNumOperands()-1));
+      AddToQueue(Chain, N.getOperand(N.getNumOperands()-1));
       Ops.push_back(Chain);
     }
     
@@ -1293,10 +1246,8 @@
     
     Chain = SDOperand(ResNode, 0);
     InFlag = SDOperand(ResNode, 1);
-    SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, Chain.Val,
-                                     Chain.ResNo);
-    SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, InFlag.Val, 
-                                     InFlag.ResNo);
+    ReplaceUses(SDOperand(N.Val, 0), Chain);
+    ReplaceUses(SDOperand(N.Val, 1), InFlag);
     Result = SDOperand(ResNode, N.ResNo);
     return;
   }
@@ -1313,13 +1264,13 @@
 
     // Push varargs arguments, not including optional flag.
     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
-      Select(Chain, N.getOperand(i));
+      AddToQueue(Chain, N.getOperand(i));
       Ops.push_back(Chain);
     }
-    Select(Chain, N.getOperand(0));
+    AddToQueue(Chain, N.getOperand(0));
     Ops.push_back(Chain);
     if (hasFlag) {
-      Select(Chain, N.getOperand(N.getNumOperands()-1));
+      AddToQueue(Chain, N.getOperand(N.getNumOperands()-1));
       Ops.push_back(Chain);
     }
     
@@ -1327,10 +1278,8 @@
 
     Chain = SDOperand(ResNode, 0);
     InFlag = SDOperand(ResNode, 1);
-    SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 0, Chain.Val,
-                                     Chain.ResNo);
-    SelectionDAG::InsertISelMapEntry(CodeGenMap, N.Val, 1, InFlag.Val,
-                                     InFlag.ResNo);
+    ReplaceUses(SDOperand(N.Val, 0), Chain);
+    ReplaceUses(SDOperand(N.Val, 1), InFlag);
     Result = SDOperand(ResNode, N.ResNo);
     return;
   }
diff --git a/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index 1004109..a0f52f0 100644
--- a/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
@@ -25,6 +25,7 @@
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Support/Debug.h"
 #include <iostream>
+#include <queue>
 #include <set>
 using namespace llvm;
 
@@ -1001,9 +1002,6 @@
   
   // Select target instructions for the DAG.
   DAG.setRoot(SelectRoot(DAG.getRoot()));
-  CodeGenMap.clear();
-  HandleMap.clear();
-  ReplaceMap.clear();
   DAG.RemoveDeadNodes();
   
   // Emit machine code to BB. 
@@ -1083,21 +1081,14 @@
     return;   // Already selected.
   }
 
-                 // If this has already been converted, use it.
-  std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
-  if (CGMI != CodeGenMap.end()) {
-    Result = CGMI->second;
-    return;
-  }
-  
   switch (N->getOpcode()) {
   default: break;
   case ISD::SDIV:
   case ISD::UDIV: {
     // FIXME: should use a custom expander to expose the SRA to the dag.
     SDOperand DivLHS, DivRHS;
-    Select(DivLHS, N->getOperand(0));
-    Select(DivRHS, N->getOperand(1));
+    AddToQueue(DivLHS, N->getOperand(0));
+    AddToQueue(DivRHS, N->getOperand(1));
     
     // Set the Y register to the high-part.
     SDOperand TopPart;
@@ -1119,8 +1110,8 @@
   case ISD::MULHS: {
     // FIXME: Handle mul by immediate.
     SDOperand MulLHS, MulRHS;
-    Select(MulLHS, N->getOperand(0));
-    Select(MulRHS, N->getOperand(1));
+    AddToQueue(MulLHS, N->getOperand(0));
+    AddToQueue(MulRHS, N->getOperand(1));
     unsigned Opcode = N->getOpcode() == ISD::MULHU ? SP::UMULrr : SP::SMULrr;
     SDNode *Mul = CurDAG->getTargetNode(Opcode, MVT::i32, MVT::Flag,
                                         MulLHS, MulRHS);
diff --git a/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp
index 3239df9..c2d5067 100644
--- a/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -12,7 +12,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "isel"
+#define DEBUG_TYPE "x86-isel"
 #include "X86.h"
 #include "X86InstrBuilder.h"
 #include "X86ISelLowering.h"
@@ -35,6 +35,7 @@
 #include "llvm/ADT/Statistic.h"
 #include <deque>
 #include <iostream>
+#include <queue>
 #include <set>
 using namespace llvm;
 
@@ -99,7 +100,7 @@
       : SelectionDAGISel(X86Lowering),
         X86Lowering(*TM.getTargetLowering()),
         Subtarget(&TM.getSubtarget<X86Subtarget>()),
-        DAGSize(0), ReachabilityMatrix(NULL), ReachMatrixRange(NULL) {}
+        ReachabilityMatrix(NULL) {}
 
     virtual bool runOnFunction(Function &Fn) {
       // Make sure we re-emit a set of the global base reg if necessary
@@ -123,7 +124,7 @@
 #include "X86GenDAGISel.inc"
 
   private:
-    void DetermineReachability(SDNode *f, SDNode *t);
+    void DetermineReachability();
 
     void Select(SDOperand &Result, SDOperand N);
 
@@ -135,6 +136,18 @@
     bool TryFoldLoad(SDOperand P, SDOperand N,
                      SDOperand &Base, SDOperand &Scale,
                      SDOperand &Index, SDOperand &Disp);
+
+    virtual void SelectRootInit() {
+      DAGSize = CurDAG->AssignTopologicalOrder(TopOrder);
+      unsigned NumBytes = (DAGSize + 7) / 8;
+      UnfoldableSet = new unsigned char[NumBytes];
+      memset(UnfoldableSet, 0, NumBytes);
+      unsigned RMSize = (DAGSize * DAGSize + 7) / 8;
+      ReachabilityMatrix = new unsigned char[RMSize];
+      memset(ReachabilityMatrix, 0, RMSize);
+      DetermineReachability();
+    }
+
     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
     /// inline asm expressions.
     virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op,
@@ -179,22 +192,10 @@
     /// base register.  Return the virtual register that holds this value.
     SDOperand getGlobalBaseReg();
 
-    /// DAGSize - Number of nodes in the DAG.
-    ///
-    unsigned DAGSize;
-
-    /// TopOrder - Topological ordering of all nodes in the DAG.
-    ///
-    std::vector<SDNode*> TopOrder;
-
     /// ReachabilityMatrix - A N x N matrix representing all pairs reachability
     /// information. One bit per potential edge.
     unsigned char *ReachabilityMatrix;
 
-    /// ReachMatrixRange - The range of reachability information available for
-    /// the particular source node.
-    unsigned *ReachMatrixRange;
-
     inline void setReachable(SDNode *f, SDNode *t) {
       unsigned Idx = f->getNodeId() * DAGSize + t->getNodeId();
       ReachabilityMatrix[Idx / 8] |= 1 << (Idx % 8);
@@ -243,7 +244,6 @@
   //      /        [X]
   //      |         ^
   //     [U]--------|
-  DetermineReachability(U, N);
   assert(isReachable(U, N) && "Attempting to fold a non-operand node?");
   for (SDNode::op_iterator I = U->op_begin(), E = U->op_end(); I != E; ++I) {
     SDNode *P = I->Val;
@@ -255,23 +255,15 @@
 
 /// DetermineReachability - Determine reachability between all pairs of nodes
 /// between f and t in topological order.
-void X86DAGToDAGISel::DetermineReachability(SDNode *f, SDNode *t) {
-  unsigned Orderf = f->getNodeId();
-  unsigned Ordert = t->getNodeId();
-  unsigned Range = ReachMatrixRange[Orderf];
-  if (Range >= Ordert)
-    return;
-  if (Range < Orderf)
-    Range = Orderf;
-
-  for (unsigned i = Range; i < Ordert; ++i) {
+void X86DAGToDAGISel::DetermineReachability() {
+  for (unsigned i = 0; i < DAGSize; ++i) {
     SDNode *N = TopOrder[i];
     setReachable(N, N);
     // If N is a leaf node, there is nothing more to do.
     if (N->getNumOperands() == 0)
       continue;
 
-    for (unsigned i2 = Range; ; ++i2) {
+    for (unsigned i2 = 0; ; ++i2) {
       SDNode *M = TopOrder[i2];
       if (isReachable(M, N)) {
         // Update reachability from M to N's operands.
@@ -284,8 +276,6 @@
       if (M == N) break;
     }
   }
-
-  ReachMatrixRange[Orderf] = Ordert;
 }
 
 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
@@ -294,16 +284,6 @@
   DEBUG(BB->dump());
   MachineFunction::iterator FirstMBB = BB;
 
-  DAGSize = DAG.AssignTopologicalOrder(TopOrder);
-  unsigned RMSize = (DAGSize * DAGSize + 7) / 8;
-  ReachabilityMatrix = new unsigned char[RMSize];
-  memset(ReachabilityMatrix, 0, RMSize);
-  ReachMatrixRange = new unsigned[DAGSize];
-  memset(ReachMatrixRange, 0, DAGSize * sizeof(unsigned));
-  unsigned NumBytes = (DAGSize + 7) / 8;
-  UnfoldableSet = new unsigned char[NumBytes];
-  memset(UnfoldableSet, 0, NumBytes);
-
   // Codegen the basic block.
 #ifndef NDEBUG
   DEBUG(std::cerr << "===== Instruction selection begins:\n");
@@ -315,15 +295,9 @@
 #endif
 
   delete[] ReachabilityMatrix;
-  delete[] ReachMatrixRange;
   delete[] UnfoldableSet;
   ReachabilityMatrix = NULL;
-  ReachMatrixRange = NULL;
   UnfoldableSet = NULL;
-  TopOrder.clear();
-  CodeGenMap.clear();
-  HandleMap.clear();
-  ReplaceMap.clear();
   DAG.RemoveDeadNodes();
 
   // Emit machine code to BB. 
@@ -414,13 +388,8 @@
 /// addressing mode
 bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM,
                                    bool isRoot) {
-  bool Available = false;
-  // If N has already been selected, reuse the result unless in some very
-  // specific cases.
-  std::map<SDOperand, SDOperand>::iterator CGMI= CodeGenMap.find(N.getValue(0));
-  if (CGMI != CodeGenMap.end()) {
-    Available = true;
-  }
+  int id = N.Val->getNodeId();
+  bool Available = isSelected(id);
 
   switch (N.getOpcode()) {
   default: break;
@@ -664,7 +633,6 @@
                                   SDOperand &Index, SDOperand &Disp) {
   if (N.getOpcode() == ISD::LOAD &&
       N.hasOneUse() &&
-      !CodeGenMap.count(N.getValue(0)) &&
       !CanBeFoldedBy(N.Val, P.Val))
     return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp);
   return false;
@@ -727,23 +695,11 @@
     return;   // Already selected.
   }
 
-  std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(N);
-  if (CGMI != CodeGenMap.end()) {
-    Result = CGMI->second;
-#ifndef NDEBUG
-    DEBUG(std::cerr << std::string(Indent-2, ' '));
-    DEBUG(std::cerr << "== ");
-    DEBUG(Result.Val->dump(CurDAG));
-    DEBUG(std::cerr << "\n");
-    Indent -= 2;
-#endif
-    return;
-  }
-  
   switch (Opcode) {
     default: break;
     case X86ISD::GlobalBaseReg: 
       Result = getGlobalBaseReg();
+      ReplaceUses(N, Result);
       return;
 
     case ISD::ADD: {
@@ -774,7 +730,8 @@
             Result = CurDAG->SelectNodeTo(N.Val, X86::MOV32ri, MVT::i32, C);
           } else {
             SDNode *ResNode = CurDAG->getTargetNode(X86::MOV32ri, MVT::i32, C);
-            Result = CodeGenMap[N] = SDOperand(ResNode, 0);
+            Result = SDOperand(ResNode, 0);
+            ReplaceUses(N, Result);
           }
           return;
         }
@@ -826,42 +783,40 @@
 
       SDOperand Chain;
       if (foldedLoad)
-        Select(Chain, N1.getOperand(0));
+        AddToQueue(Chain, N1.getOperand(0));
       else
         Chain = CurDAG->getEntryNode();
 
       SDOperand InFlag(0, 0);
-      Select(N0, N0);
+      AddToQueue(N0, N0);
       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
                                     N0, InFlag);
       InFlag = Chain.getValue(1);
 
       if (foldedLoad) {
-        Select(Tmp0, Tmp0);
-        Select(Tmp1, Tmp1);
-        Select(Tmp2, Tmp2);
-        Select(Tmp3, Tmp3);
+        AddToQueue(Tmp0, Tmp0);
+        AddToQueue(Tmp1, Tmp1);
+        AddToQueue(Tmp2, Tmp2);
+        AddToQueue(Tmp3, Tmp3);
         SDNode *CNode =
           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
                                 Tmp2, Tmp3, Chain, InFlag);
         Chain  = SDOperand(CNode, 0);
         InFlag = SDOperand(CNode, 1);
       } else {
-        Select(N1, N1);
+        AddToQueue(N1, N1);
         InFlag =
           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
       }
 
       Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag);
-      CodeGenMap[N.getValue(0)] = Result;
-      if (foldedLoad) {
-        CodeGenMap[N1.getValue(1)] = Result.getValue(1);
-        AddHandleReplacement(N1.Val, 1, Result.Val, 1);
-      }
+      ReplaceUses(N.getValue(0), Result);
+      if (foldedLoad)
+        ReplaceUses(N1.getValue(1), Result.getValue(1));
 
 #ifndef NDEBUG
       DEBUG(std::cerr << std::string(Indent-2, ' '));
-      DEBUG(std::cerr << "== ");
+      DEBUG(std::cerr << "=> ");
       DEBUG(Result.Val->dump(CurDAG));
       DEBUG(std::cerr << "\n");
       Indent -= 2;
@@ -919,12 +874,12 @@
       foldedLoad = TryFoldLoad(N, N1, Tmp0, Tmp1, Tmp2, Tmp3);
       SDOperand Chain;
       if (foldedLoad)
-        Select(Chain, N1.getOperand(0));
+        AddToQueue(Chain, N1.getOperand(0));
       else
         Chain = CurDAG->getEntryNode();
 
       SDOperand InFlag(0, 0);
-      Select(N0, N0);
+      AddToQueue(N0, N0);
       Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
                                     N0, InFlag);
       InFlag = Chain.getValue(1);
@@ -942,32 +897,30 @@
       }
 
       if (foldedLoad) {
-        Select(Tmp0, Tmp0);
-        Select(Tmp1, Tmp1);
-        Select(Tmp2, Tmp2);
-        Select(Tmp3, Tmp3);
+        AddToQueue(Tmp0, Tmp0);
+        AddToQueue(Tmp1, Tmp1);
+        AddToQueue(Tmp2, Tmp2);
+        AddToQueue(Tmp3, Tmp3);
         SDNode *CNode =
           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
                                 Tmp2, Tmp3, Chain, InFlag);
         Chain  = SDOperand(CNode, 0);
         InFlag = SDOperand(CNode, 1);
       } else {
-        Select(N1, N1);
+        AddToQueue(N1, N1);
         InFlag =
           SDOperand(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
       }
 
       Result = CurDAG->getCopyFromReg(Chain, isDiv ? LoReg : HiReg,
                                       NVT, InFlag);
-      CodeGenMap[N.getValue(0)] = Result;
-      if (foldedLoad) {
-        CodeGenMap[N1.getValue(1)] = Result.getValue(1);
-        AddHandleReplacement(N1.Val, 1, Result.Val, 1);
-      }
+      ReplaceUses(N.getValue(0), Result);
+      if (foldedLoad)
+        ReplaceUses(N1.getValue(1), Result.getValue(1));
 
 #ifndef NDEBUG
       DEBUG(std::cerr << std::string(Indent-2, ' '));
-      DEBUG(std::cerr << "== ");
+      DEBUG(std::cerr << "=> ");
       DEBUG(Result.Val->dump(CurDAG));
       DEBUG(std::cerr << "\n");
       Indent -= 2;
@@ -994,14 +947,14 @@
         }
 
         SDOperand Tmp0, Tmp1;
-        Select(Tmp0, Node->getOperand(0));
+        AddToQueue(Tmp0, Node->getOperand(0));
         Tmp1 = SDOperand(CurDAG->getTargetNode(Opc, VT, Tmp0), 0);
-        Result = CodeGenMap[N] =
-          SDOperand(CurDAG->getTargetNode(Opc2, NVT, Tmp1), 0);
+        Result = SDOperand(CurDAG->getTargetNode(Opc2, NVT, Tmp1), 0);
+        ReplaceUses(N, Result);
       
 #ifndef NDEBUG
         DEBUG(std::cerr << std::string(Indent-2, ' '));
-        DEBUG(std::cerr << "== ");
+        DEBUG(std::cerr << "=> ");
         DEBUG(Result.Val->dump(CurDAG));
         DEBUG(std::cerr << "\n");
         Indent -= 2;
@@ -1038,10 +991,10 @@
   }
   
   OutOps.resize(4);
-  Select(OutOps[0], Op0);
-  Select(OutOps[1], Op1);
-  Select(OutOps[2], Op2);
-  Select(OutOps[3], Op3);
+  AddToQueue(OutOps[0], Op0);
+  AddToQueue(OutOps[1], Op1);
+  AddToQueue(OutOps[2], Op2);
+  AddToQueue(OutOps[3], Op3);
   return false;
 }