Match tablegen isel changes.

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

6 files changed, 164 insertions, 315 deletions

diff --git a/lib/Target/ARM/ARMISelDAGToDAG.cpp b/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 34d972ffa7..915684ad17 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 @@ void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
   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 78a78143c1..811aab85d0 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 @@ namespace {
       switch (ConstraintCode) {
       default: return true;
       case 'm':   // memory
-	Select(Op0, Op);
+	AddToQueue(Op0, Op);
         break;
       }
       
@@ -172,9 +173,6 @@ void AlphaDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
   
   // 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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   }
   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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
 
   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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     if (uval == 0) {
       Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), Alpha::R31,
                                       MVT::i64);
+      ReplaceUses(Op, Result);
       return;
     }
 
@@ -311,8 +308,8 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       //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 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       }
       Result = SDOperand(CurDAG->getTargetNode(isDouble?Alpha::FCMOVNET:Alpha::FCMOVNES,
                                                MVT::f64, FV, TV, LD), 0);
+      ReplaceUses(Op, Result);
       return;
     }
     break;
@@ -396,12 +395,13 @@ void AlphaDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
 
 	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 AlphaDAGToDAGISel::SelectCALL(SDOperand Op) {
   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 @@ SDOperand AlphaDAGToDAGISel::SelectCALL(SDOperand Op) {
    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 @@ SDOperand AlphaDAGToDAGISel::SelectCALL(SDOperand Op) {
      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 @@ SDOperand AlphaDAGToDAGISel::SelectCALL(SDOperand Op) {
 
    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 fe5a7bb0ab..8013f87589 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 @@ private:
 /// 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 @@ void IA64DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     // 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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
    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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   case ISD::SREM:
   case ISD::UREM:
     Result = SelectDIV(Op);
+    ReplaceUses(Op, Result);
     return;
  
   case ISD::TargetConstantFP: {
@@ -459,9 +413,11 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
                                                   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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
 	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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     }
     
     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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void IA64DAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   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 937092ab02..4346c5e21d 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 @@ namespace {
         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 @@ private:
 /// 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 @@ SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
       }
       
       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 @@ bool PPCDAGToDAGISel::SelectAddrImmShift(SDOperand N, SDOperand &Disp,
 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 @@ SDOperand PPCDAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
     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 @@ SDOperand PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
     // 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 @@ SDOperand PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
       }
     } 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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     return;
   case PPCISD::GlobalBaseReg:
     Result = getGlobalBaseReg();
+    ReplaceUses(Op, Result);
     return;
     
   case ISD::FrameIndex: {
@@ -973,22 +927,23 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
                                     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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
               // 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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
       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 @@ void PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   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 @@ void PPCDAGToDAGISel::MySelect_PPCbctrl(SDOperand &Result, SDOperand N) {
   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 @@ void PPCDAGToDAGISel::MySelect_PPCcall(SDOperand &Result, SDOperand N) {
     
     // 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 @@ void PPCDAGToDAGISel::MySelect_PPCcall(SDOperand &Result, SDOperand N) {
 
     // 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 @@ void PPCDAGToDAGISel::MySelect_PPCcall(SDOperand &Result, SDOperand N) {
     
     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 @@ void PPCDAGToDAGISel::MySelect_PPCcall(SDOperand &Result, SDOperand N) {
 
     // 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 @@ void PPCDAGToDAGISel::MySelect_PPCcall(SDOperand &Result, SDOperand N) {
 
     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 1004109524..a0f52f0f3e 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 @@ void SparcDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
   
   // 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 @@ void SparcDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
     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 @@ void SparcDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
   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,