Eliminate the ISel priority queue, which used the topological order for a

priority function. Instead, just iterate over the AllNodes list, which is
already in topological order. This eliminates a fair amount of bookkeeping,
and speeds up the isel phase by about 15% on many testcases.

The impact on most targets is that AddToISelQueue calls can be simply removed.

In the x86 target, there are two additional notable changes.

The rule-bending AND+SHIFT optimization in MatchAddress that creates new
pre-isel nodes during isel is now a little more verbose, but more robust.
Instead of either creating an invalid DAG or creating an invalid topological
sort, as it has historically done, it can now just insert the new nodes into
the node list at a position where they will be consistent with the topological
ordering.

Also, the address-matching code has logic that checked to see if a node was
"already selected". However, when a node is selected, it has all its uses
taken away via ReplaceAllUsesWith or equivalent, so it won't recieve any
further visits from MatchAddress. This code is now removed.

llvm-svn: 58748

8 files changed, 30 insertions, 165 deletions

diff --git a/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp b/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 060f61ca70c..b281f84cb72 100644
--- a/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
+++ b/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
@@ -599,8 +599,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
       std::swap(LHSR, RHSR);
     }
     if (RHSR && RHSR->getReg() == ARM::SP) {
-      AddToISelQueue(N0);
-      AddToISelQueue(N1);
       return CurDAG->SelectNodeTo(N, ARM::tADDhirr, Op.getValueType(), N0, N1);
     }
     break;
@@ -613,7 +611,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
       if (!RHSV) break;
       if (isPowerOf2_32(RHSV-1)) {  // 2^n+1?
         SDValue V = Op.getOperand(0);
-        AddToISelQueue(V);
         unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV-1));
         SDValue Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
                             CurDAG->getTargetConstant(ShImm, MVT::i32),
@@ -623,7 +620,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
       }
       if (isPowerOf2_32(RHSV+1)) {  // 2^n-1?
         SDValue V = Op.getOperand(0);
-        AddToISelQueue(V);
         unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV+1));
         SDValue Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
                             CurDAG->getTargetConstant(ShImm, MVT::i32),
@@ -634,21 +630,16 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
     }
     break;
   case ARMISD::FMRRD:
-    AddToISelQueue(Op.getOperand(0));
     return CurDAG->getTargetNode(ARM::FMRRD, MVT::i32, MVT::i32,
                                  Op.getOperand(0), getAL(CurDAG),
                                  CurDAG->getRegister(0, MVT::i32));
   case ISD::UMUL_LOHI: {
-    AddToISelQueue(Op.getOperand(0));
-    AddToISelQueue(Op.getOperand(1));
     SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
                         CurDAG->getRegister(0, MVT::i32) };
     return CurDAG->getTargetNode(ARM::UMULL, MVT::i32, MVT::i32, Ops, 5);
   }
   case ISD::SMUL_LOHI: {
-    AddToISelQueue(Op.getOperand(0));
-    AddToISelQueue(Op.getOperand(1));
     SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
                         CurDAG->getRegister(0, MVT::i32) };
@@ -690,9 +681,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
       if (Match) {
         SDValue Chain = LD->getChain();
         SDValue Base = LD->getBasePtr();
-        AddToISelQueue(Chain);
-        AddToISelQueue(Base);
-        AddToISelQueue(Offset);
         SDValue Ops[]= { Base, Offset, AMOpc, getAL(CurDAG),
                            CurDAG->getRegister(0, MVT::i32), Chain };
         return CurDAG->getTargetNode(Opcode, MVT::i32, MVT::i32,
@@ -721,9 +709,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
     assert(N2.getOpcode() == ISD::Constant);
     assert(N3.getOpcode() == ISD::Register);
 
-    AddToISelQueue(Chain);
-    AddToISelQueue(N1);
-    AddToISelQueue(InFlag);
     SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
                                cast<ConstantSDNode>(N2)->getZExtValue()),
                                MVT::i32);
@@ -756,11 +741,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
     SDValue CPTmp2;
     if (!isThumb && VT == MVT::i32 &&
         SelectShifterOperandReg(Op, N1, CPTmp0, CPTmp1, CPTmp2)) {
-      AddToISelQueue(N0);
-      AddToISelQueue(CPTmp0);
-      AddToISelQueue(CPTmp1);
-      AddToISelQueue(CPTmp2);
-      AddToISelQueue(InFlag);
       SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
                                cast<ConstantSDNode>(N2)->getZExtValue()),
                                MVT::i32);
@@ -777,8 +757,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
     if (VT == MVT::i32 &&
         N3.getOpcode() == ISD::Constant &&
         Predicate_so_imm(N3.getNode())) {
-      AddToISelQueue(N0);
-      AddToISelQueue(InFlag);
       SDValue Tmp1 = CurDAG->getTargetConstant(((unsigned)
                                cast<ConstantSDNode>(N1)->getZExtValue()),
                                MVT::i32);
@@ -799,9 +777,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
     // Pattern complexity = 6  cost = 11  size = 0
     //
     // Also FCPYScc and FCPYDcc.
-    AddToISelQueue(N0);
-    AddToISelQueue(N1);
-    AddToISelQueue(InFlag);
     SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
                                cast<ConstantSDNode>(N2)->getZExtValue()),
                                MVT::i32);
@@ -832,9 +807,6 @@ SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
     assert(N2.getOpcode() == ISD::Constant);
     assert(N3.getOpcode() == ISD::Register);
 
-    AddToISelQueue(N0);
-    AddToISelQueue(N1);
-    AddToISelQueue(InFlag);
     SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
                                cast<ConstantSDNode>(N2)->getZExtValue()),
                                MVT::i32);
diff --git a/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp b/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
index e0ae5564ed8..801db44faf7 100644
--- a/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
@@ -174,7 +174,6 @@ namespace {
       default: return true;
       case 'm':   // memory
         Op0 = Op;
-        AddToISelQueue(Op0);
         break;
       }
       
@@ -270,9 +269,6 @@ SDNode *AlphaDAGToDAGISel::Select(SDValue Op) {
     SDValue N0 = Op.getOperand(0);
     SDValue N1 = Op.getOperand(1);
     SDValue N2 = Op.getOperand(2);
-    AddToISelQueue(N0);
-    AddToISelQueue(N1);
-    AddToISelQueue(N2);
     Chain = CurDAG->getCopyToReg(Chain, Alpha::R24, N1, 
                                  SDValue(0,0));
     Chain = CurDAG->getCopyToReg(Chain, Alpha::R25, N2, 
@@ -289,7 +285,6 @@ SDNode *AlphaDAGToDAGISel::Select(SDValue Op) {
 
   case ISD::READCYCLECOUNTER: {
     SDValue Chain = N->getOperand(0);
-    AddToISelQueue(Chain); //Select chain
     return CurDAG->getTargetNode(Alpha::RPCC, MVT::i64, MVT::Other,
                                  Chain);
   }
@@ -368,8 +363,6 @@ SDNode *AlphaDAGToDAGISel::Select(SDValue Op) {
       };
       SDValue tmp1 = N->getOperand(rev?1:0);
       SDValue tmp2 = N->getOperand(rev?0:1);
-      AddToISelQueue(tmp1);
-      AddToISelQueue(tmp2);
       SDNode *cmp = CurDAG->getTargetNode(Opc, MVT::f64, tmp1, tmp2);
       if (inv) 
         cmp = CurDAG->getTargetNode(Alpha::CMPTEQ, MVT::f64, SDValue(cmp, 0), 
@@ -406,9 +399,6 @@ SDNode *AlphaDAGToDAGISel::Select(SDValue Op) {
       SDValue cond = N->getOperand(0);
       SDValue TV = N->getOperand(1);
       SDValue FV = N->getOperand(2);
-      AddToISelQueue(cond);
-      AddToISelQueue(TV);
-      AddToISelQueue(FV);
       
       SDNode* LD = CurDAG->getTargetNode(Alpha::ITOFT, MVT::f64, cond);
       return CurDAG->getTargetNode(isDouble?Alpha::FCMOVNET:Alpha::FCMOVNES,
@@ -436,7 +426,6 @@ SDNode *AlphaDAGToDAGISel::Select(SDValue Op) {
         mask = mask | dontcare;
       
       if (get_zapImm(mask)) {
-        AddToISelQueue(N->getOperand(0).getOperand(0));
         SDValue Z = 
           SDValue(CurDAG->getTargetNode(Alpha::ZAPNOTi, MVT::i64,
                                           N->getOperand(0).getOperand(0),
@@ -460,7 +449,6 @@ void AlphaDAGToDAGISel::SelectCALL(SDValue Op) {
   SDValue Chain = N->getOperand(0);
   SDValue Addr = N->getOperand(1);
   SDValue InFlag(0,0);  // Null incoming flag value.
-  AddToISelQueue(Chain);
 
    std::vector<SDValue> CallOperands;
    std::vector<MVT> TypeOperands;
@@ -468,7 +456,6 @@ void AlphaDAGToDAGISel::SelectCALL(SDValue Op) {
    //grab the arguments
    for(int i = 2, e = N->getNumOperands(); i < e; ++i) {
      TypeOperands.push_back(N->getOperand(i).getValueType());
-     AddToISelQueue(N->getOperand(i));
      CallOperands.push_back(N->getOperand(i));
    }
    int count = N->getNumOperands() - 2;
@@ -514,7 +501,6 @@ void AlphaDAGToDAGISel::SelectCALL(SDValue Op) {
      Chain = SDValue(CurDAG->getTargetNode(Alpha::BSR, MVT::Other, MVT::Flag, 
                                              Addr.getOperand(0), Chain, InFlag), 0);
    } else {
-     AddToISelQueue(Addr);
      Chain = CurDAG->getCopyToReg(Chain, Alpha::R27, Addr, InFlag);
      InFlag = Chain.getValue(1);
      Chain = SDValue(CurDAG->getTargetNode(Alpha::JSR, MVT::Other, MVT::Flag, 
diff --git a/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp b/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
index d6a492b575c..144f5781cda 100644
--- a/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
+++ b/llvm/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
@@ -296,7 +296,6 @@ public:
       if (!SelectDFormAddr(Op, Op, Op0, Op1)
           && !SelectAFormAddr(Op, Op, Op0, Op1)) {
         Op0 = Op;
-        AddToISelQueue(Op0);     // r+0.
         Op1 = getSmallIPtrImm(0);
       }
       break;
@@ -609,8 +608,6 @@ SPUDAGToDAGISel::Select(SDValue Op) {
       Ops[0] = CurDAG->getRegister(SPU::R1, PtrVT);
       Ops[1] = CurDAG->getConstant(FI, PtrVT);
       n_ops = 2;
-
-      AddToISelQueue(Ops[1]);
     }
   } else if (Opc == ISD::ZERO_EXTEND) {
     // (zero_extend:i16 (and:i8 <arg>, <const>))
@@ -643,19 +640,16 @@ SPUDAGToDAGISel::Select(SDValue Op) {
       abort();
     }
 
-    AddToISelQueue(Arg);
     Opc = vtm->ldresult_ins;
     if (vtm->ldresult_imm) {
       SDValue Zero = CurDAG->getTargetConstant(0, VT);
 
-      AddToISelQueue(Zero);
       Result = CurDAG->getTargetNode(Opc, VT, MVT::Other, Arg, Zero, Chain);
     } else {
       Result = CurDAG->getTargetNode(Opc, MVT::Other, Arg, Arg, Chain);
     }
 
     Chain = SDValue(Result, 1);
-    AddToISelQueue(Chain);
 
     return Result;
   } else if (Opc == SPUISD::IndirectAddr) {
@@ -676,8 +670,6 @@ SPUDAGToDAGISel::Select(SDValue Op) {
         ConstantSDNode *CN = cast<ConstantSDNode>(Op1);
         Op1 = CurDAG->getTargetConstant(CN->getZExtValue(), VT);
         NewOpc = (isI32IntS10Immediate(CN) ? SPU::AIr32 : SPU::Ar32);
-        AddToISelQueue(Op0);
-        AddToISelQueue(Op1);
         Ops[0] = Op0;
         Ops[1] = Op1;
         n_ops = 2;
diff --git a/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp b/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp
index ae59ea2489d..4532ed2623d 100644
--- a/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/IA64/IA64ISelDAGToDAG.cpp
@@ -106,10 +106,6 @@ SDNode *IA64DAGToDAGISel::SelectDIV(SDValue Op) {
   SDValue Chain = N->getOperand(0);
   SDValue Tmp1 = N->getOperand(0);
   SDValue Tmp2 = N->getOperand(1);
-  AddToISelQueue(Chain);
-
-  AddToISelQueue(Tmp1);
-  AddToISelQueue(Tmp2);
 
   bool isFP=false;
 
@@ -312,10 +308,8 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
     SDValue Chain = N->getOperand(0);
     SDValue InFlag;  // Null incoming flag value.
 
-    AddToISelQueue(Chain);
     if(N->getNumOperands()==3) { // we have an incoming chain, callee and flag
       InFlag = N->getOperand(2);
-      AddToISelQueue(InFlag);
     }
 
     unsigned CallOpcode;
@@ -336,7 +330,6 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
     // load the branch target (function)'s entry point and GP,
     // branch (call) then restore the GP
     SDValue FnDescriptor = N->getOperand(1);
-    AddToISelQueue(FnDescriptor);
    
     // load the branch target's entry point [mem] and 
     // GP value [mem+8]
@@ -385,7 +378,6 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
   
   case IA64ISD::GETFD: {
     SDValue Input = N->getOperand(0);
-    AddToISelQueue(Input);
     return CurDAG->getTargetNode(IA64::GETFD, MVT::i64, Input);
   } 
   
@@ -461,8 +453,6 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
     LoadSDNode *LD = cast<LoadSDNode>(N);
     SDValue Chain = LD->getChain();
     SDValue Address = LD->getBasePtr();
-    AddToISelQueue(Chain);
-    AddToISelQueue(Address);
 
     MVT TypeBeingLoaded = LD->getMemoryVT();
     unsigned Opc;
@@ -501,8 +491,6 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
     StoreSDNode *ST = cast<StoreSDNode>(N);
     SDValue Address = ST->getBasePtr();
     SDValue Chain = ST->getChain();
-    AddToISelQueue(Address);
-    AddToISelQueue(Chain);
    
     unsigned Opc;
     if (ISD::isNON_TRUNCStore(N)) {
@@ -515,7 +503,6 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
         Chain = Initial.getValue(1);
         // then load 1 into the same reg iff the predicate to store is 1
         SDValue Tmp = ST->getValue();
-        AddToISelQueue(Tmp);
         Tmp =
           SDValue(CurDAG->getTargetNode(IA64::TPCADDS, MVT::i64, Initial,
                                           CurDAG->getTargetConstant(1,
@@ -538,16 +525,12 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
     
     SDValue N1 = N->getOperand(1);
     SDValue N2 = N->getOperand(2);
-    AddToISelQueue(N1);
-    AddToISelQueue(N2);
     return CurDAG->SelectNodeTo(N, Opc, MVT::Other, N2, N1, Chain);
   }
 
   case ISD::BRCOND: {
     SDValue Chain = N->getOperand(0);
     SDValue CC = N->getOperand(1);
-    AddToISelQueue(Chain);
-    AddToISelQueue(CC);
     MachineBasicBlock *Dest =
       cast<BasicBlockSDNode>(N->getOperand(2))->getBasicBlock();
     //FIXME - we do NOT need long branches all the time
@@ -561,14 +544,12 @@ SDNode *IA64DAGToDAGISel::Select(SDValue Op) {
     unsigned Opc = N->getOpcode() == ISD::CALLSEQ_START ?
       IA64::ADJUSTCALLSTACKDOWN : IA64::ADJUSTCALLSTACKUP;
     SDValue N0 = N->getOperand(0);
-    AddToISelQueue(N0);
     return CurDAG->SelectNodeTo(N, Opc, MVT::Other, getI64Imm(Amt), N0);
   }
 
   case ISD::BR:
     // FIXME: we don't need long branches all the time!
     SDValue N0 = N->getOperand(0);
-    AddToISelQueue(N0);
     return CurDAG->SelectNodeTo(N, IA64::BRL_NOTCALL, MVT::Other, 
                                 N->getOperand(1), N0);
   }
diff --git a/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp b/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp
index b31bcbdc0b3..95854bb5485 100644
--- a/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Mips/MipsISelDAGToDAG.cpp
@@ -236,8 +236,6 @@ Select(SDValue N)
 
       SDValue LHS = Node->getOperand(0);
       SDValue RHS = Node->getOperand(1);
-      AddToISelQueue(LHS);
-      AddToISelQueue(RHS);
 
       MVT VT = LHS.getValueType();
       SDNode *Carry = CurDAG->getTargetNode(Mips::SLTu, VT, Ops, 2);
@@ -255,8 +253,6 @@ Select(SDValue N)
     case ISD::UMUL_LOHI: {
       SDValue Op1 = Node->getOperand(0);
       SDValue Op2 = Node->getOperand(1);
-      AddToISelQueue(Op1);
-      AddToISelQueue(Op2);
 
       unsigned Op;
       if (Opcode == ISD::UMUL_LOHI || Opcode == ISD::SMUL_LOHI)
@@ -287,8 +283,6 @@ Select(SDValue N)
     case ISD::MULHU: {
       SDValue MulOp1 = Node->getOperand(0);
       SDValue MulOp2 = Node->getOperand(1);
-      AddToISelQueue(MulOp1);
-      AddToISelQueue(MulOp2);
 
       unsigned MulOp  = (Opcode == ISD::MULHU ? Mips::MULTu : Mips::MULT);
       SDNode *MulNode = CurDAG->getTargetNode(MulOp, MVT::Flag, MulOp1, MulOp2);
@@ -308,8 +302,6 @@ Select(SDValue N)
     case ISD::UDIV: {
       SDValue Op1 = Node->getOperand(0);
       SDValue Op2 = Node->getOperand(1);
-      AddToISelQueue(Op1);
-      AddToISelQueue(Op2);
 
       unsigned Op, MOp;
       if (Opcode == ISD::SDIV || Opcode == ISD::UDIV) {
@@ -341,7 +333,6 @@ Select(SDValue N)
         //bool isCodeLarge = (TM.getCodeModel() == CodeModel::Large);
         SDValue Chain  = Node->getOperand(0);
         SDValue Callee = Node->getOperand(1);
-        AddToISelQueue(Chain);
         SDValue T9Reg = CurDAG->getRegister(Mips::T9, MVT::i32);
         SDValue InFlag(0, 0);
 
@@ -356,7 +347,6 @@ Select(SDValue N)
           SDValue Load = SDValue(CurDAG->getTargetNode(Mips::LW, MVT::i32, 
                                      MVT::Other, Ops, 3), 0);
           Chain = Load.getValue(1);
-          AddToISelQueue(Chain);
 
           // Call target must be on T9
           Chain = CurDAG->getCopyToReg(Chain, T9Reg, Load, InFlag);
@@ -364,8 +354,6 @@ Select(SDValue N)
           /// Indirect call
           Chain = CurDAG->getCopyToReg(Chain, T9Reg, Callee, InFlag);
 
-        AddToISelQueue(Chain);
-
         // Emit Jump and Link Register
         SDNode *ResNode = CurDAG->getTargetNode(Mips::JALR, MVT::Other,
                                   MVT::Flag, T9Reg, Chain);
diff --git a/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
index 37ca2be85d6..c839121c33b 100644
--- a/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
+++ b/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
@@ -153,7 +153,6 @@ namespace {
       case 'o':   // offsetable
         if (!SelectAddrImm(Op, Op, Op0, Op1)) {
           Op0 = Op;
-          AddToISelQueue(Op0);     // r+0.
           Op1 = getSmallIPtrImm(0);
         }
         break;
@@ -477,8 +476,6 @@ SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
       }
       
       Tmp3 = (Op0Opc == ISD::AND && DisjointMask) ? Op0.getOperand(0) : Op0;
-      AddToISelQueue(Tmp3);
-      AddToISelQueue(Op1);
       SH &= 31;
       SDValue Ops[] = { Tmp3, Op1, getI32Imm(SH), getI32Imm(MB),
                           getI32Imm(ME) };
@@ -493,7 +490,6 @@ SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
 SDValue PPCDAGToDAGISel::SelectCC(SDValue LHS, SDValue RHS,
                                     ISD::CondCode CC) {
   // Always select the LHS.
-  AddToISelQueue(LHS);
   unsigned Opc;
   
   if (LHS.getValueType() == MVT::i32) {
@@ -586,7 +582,6 @@ SDValue PPCDAGToDAGISel::SelectCC(SDValue LHS, SDValue RHS,
     assert(LHS.getValueType() == MVT::f64 && "Unknown vt!");
     Opc = PPC::FCMPUD;
   }
-  AddToISelQueue(RHS);
   return SDValue(CurDAG->getTargetNode(Opc, MVT::i32, LHS, RHS), 0);
 }
 
@@ -662,7 +657,6 @@ SDNode *PPCDAGToDAGISel::SelectSETCC(SDValue Op) {
     // setcc op, 0
     if (Imm == 0) {
       SDValue Op = N->getOperand(0);
-      AddToISelQueue(Op);
       switch (CC) {
       default: break;
       case ISD::SETEQ: {
@@ -691,7 +685,6 @@ SDNode *PPCDAGToDAGISel::SelectSETCC(SDValue Op) {
       }
     } else if (Imm == ~0U) {        // setcc op, -1
       SDValue Op = N->getOperand(0);
-      AddToISelQueue(Op);
       switch (CC) {
       default: break;
       case ISD::SETEQ:
@@ -872,7 +865,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
 
   case PPCISD::MFCR: {
     SDValue InFlag = N->getOperand(1);
-    AddToISelQueue(InFlag);
     // Use MFOCRF if supported.
     if (PPCSubTarget.isGigaProcessor())
       return CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32,
@@ -890,7 +882,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     unsigned Imm;
     if (isInt32Immediate(N->getOperand(1), Imm)) {
       SDValue N0 = N->getOperand(0);
-      AddToISelQueue(N0);
       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
         SDNode *Op =
           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
@@ -955,9 +946,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
       
       SDValue Chain = LD->getChain();
       SDValue Base = LD->getBasePtr();
-      AddToISelQueue(Chain);
-      AddToISelQueue(Base);
-      AddToISelQueue(Offset);
       SDValue Ops[] = { Offset, Base, Chain };
       // FIXME: PPC64
       return CurDAG->getTargetNode(Opcode, LD->getValueType(0),
@@ -976,7 +964,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     if (isInt32Immediate(N->getOperand(1), Imm) &&
         isRotateAndMask(N->getOperand(0).getNode(), Imm, false, SH, MB, ME)) {
       SDValue Val = N->getOperand(0).getOperand(0);
-      AddToISelQueue(Val);
       SDValue Ops[] = { Val, getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
     }
@@ -986,13 +973,11 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
         isRunOfOnes(Imm, MB, ME) && 
         N->getOperand(0).getOpcode() != ISD::ROTL) {
       SDValue Val = N->getOperand(0);
-      AddToISelQueue(Val);
       SDValue Ops[] = { Val, getI32Imm(0), getI32Imm(MB), getI32Imm(ME) };
       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
     }
     // AND X, 0 -> 0, not "rlwinm 32".
     if (isInt32Immediate(N->getOperand(1), Imm) && (Imm == 0)) {
-      AddToISelQueue(N->getOperand(1));
       ReplaceUses(SDValue(N, 0), N->getOperand(1));
       return NULL;
     }
@@ -1004,8 +989,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
       unsigned MB, ME;
       Imm = ~(Imm^Imm2);
       if (isRunOfOnes(Imm, MB, ME)) {
-        AddToISelQueue(N->getOperand(0).getOperand(0));
-        AddToISelQueue(N->getOperand(0).getOperand(1));
         SDValue Ops[] = { N->getOperand(0).getOperand(0),
                             N->getOperand(0).getOperand(1),
                             getI32Imm(0), getI32Imm(MB),getI32Imm(ME) };
@@ -1027,7 +1010,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     unsigned Imm, SH, MB, ME;
     if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
-      AddToISelQueue(N->getOperand(0).getOperand(0));
       SDValue Ops[] = { N->getOperand(0).getOperand(0),
                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
@@ -1040,7 +1022,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     unsigned Imm, SH, MB, ME;
     if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
         isRotateAndMask(N, Imm, true, SH, MB, ME)) { 
-      AddToISelQueue(N->getOperand(0).getOperand(0));
       SDValue Ops[] = { N->getOperand(0).getOperand(0),
                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
@@ -1060,7 +1041,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
               N2C->getZExtValue() == 1ULL && CC == ISD::SETNE &&
               // FIXME: Implement this optzn for PPC64.
               N->getValueType(0) == MVT::i32) {
-            AddToISelQueue(N->getOperand(0));
             SDNode *Tmp =
               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
                                     N->getOperand(0), getI32Imm(~0U));
@@ -1084,18 +1064,15 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     else
       SelectCCOp = PPC::SELECT_CC_VRRC;
 
-    AddToISelQueue(N->getOperand(2));
-    AddToISelQueue(N->getOperand(3));
     SDValue Ops[] = { CCReg, N->getOperand(2), N->getOperand(3),
                         getI32Imm(BROpc) };
     return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), Ops, 4);
   }
   case PPCISD::COND_BRANCH: {
-    AddToISelQueue(N->getOperand(0));  // Op #0 is the Chain.
     // Op #1 is the PPC::PRED_* number.
     // Op #2 is the CR#
     // Op #3 is the Dest MBB
-    AddToISelQueue(N->getOperand(4));  // Op #4 is the Flag.
+    // Op #4 is the Flag.
     // Prevent PPC::PRED_* from being selected into LI.
     SDValue Pred =
       getI32Imm(cast<ConstantSDNode>(N->getOperand(1))->getZExtValue());
@@ -1104,7 +1081,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops, 5);
   }
   case ISD::BR_CC: {
-    AddToISelQueue(N->getOperand(0));
     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
     SDValue CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
     SDValue Ops[] = { getI32Imm(getPredicateForSetCC(CC)), CondCode, 
@@ -1115,8 +1091,6 @@ SDNode *PPCDAGToDAGISel::Select(SDValue Op) {
     // FIXME: Should custom lower this.
     SDValue Chain = N->getOperand(0);
     SDValue Target = N->getOperand(1);
-    AddToISelQueue(Chain);
-    AddToISelQueue(Target);
     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
     Chain = SDValue(CurDAG->getTargetNode(Opc, MVT::Other, Target,
                                             Chain), 0);
diff --git a/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index ceba75d7889..34846529b21 100644
--- a/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Sparc/SparcISelDAGToDAG.cpp
@@ -151,8 +151,6 @@ SDNode *SparcDAGToDAGISel::Select(SDValue Op) {
     // FIXME: should use a custom expander to expose the SRA to the dag.
     SDValue DivLHS = N->getOperand(0);
     SDValue DivRHS = N->getOperand(1);
-    AddToISelQueue(DivLHS);
-    AddToISelQueue(DivRHS);
 
     // Set the Y register to the high-part.
     SDValue TopPart;
@@ -175,8 +173,6 @@ SDNode *SparcDAGToDAGISel::Select(SDValue Op) {
     // FIXME: Handle mul by immediate.
     SDValue MulLHS = N->getOperand(0);
     SDValue MulRHS = N->getOperand(1);
-    AddToISelQueue(MulLHS);
-    AddToISelQueue(MulRHS);
     unsigned Opcode = N->getOpcode() == ISD::MULHU ? SP::UMULrr : SP::SMULrr;
     SDNode *Mul = CurDAG->getTargetNode(Opcode, MVT::i32, MVT::Flag,
                                         MulLHS, MulRHS);
diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
index 7ba62189ca0..137944ac88d 100644
--- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -777,9 +777,6 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
     return true;
   }
 
-  int id = N.getNode()->getNodeId();
-  bool AlreadySelected = isSelected(id); // Already selected, not yet replaced.
-
   switch (N.getOpcode()) {
   default: break;
   case ISD::Constant: {
@@ -794,7 +791,6 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
   case X86ISD::Wrapper: {
     DOUT << "Wrapper: 64bit " << is64Bit;
     DOUT << " AM "; DEBUG(AM.dump()); DOUT << "\n";
-    DOUT << "AlreadySelected " << AlreadySelected << "\n";
     // Under X86-64 non-small code model, GV (and friends) are 64-bits.
     // Also, base and index reg must be 0 in order to use rip as base.
     if (is64Bit && (TM.getCodeModel() != CodeModel::Small ||
@@ -805,7 +801,7 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
     // If value is available in a register both base and index components have
     // been picked, we can't fit the result available in the register in the
     // addressing mode. Duplicate GlobalAddress or ConstantPool as displacement.
-    if (!AlreadySelected || (AM.Base.Reg.getNode() && AM.IndexReg.getNode())) {
+    {
       SDValue N0 = N.getOperand(0);
       if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
         if (!is64Bit || isInt32(AM.Disp + G->getOffset())) {
@@ -846,8 +842,7 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
     break;
 
   case ISD::SHL:
-    if (AlreadySelected || AM.IndexReg.getNode() != 0
-        || AM.Scale != 1 || AM.isRIPRel)
+    if (AM.IndexReg.getNode() != 0 || AM.Scale != 1 || AM.isRIPRel)
       break;
       
     if (ConstantSDNode
@@ -885,8 +880,7 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
     // FALL THROUGH
   case ISD::MUL:
     // X*[3,5,9] -> X+X*[2,4,8]
-    if (!AlreadySelected &&
-        AM.BaseType == X86ISelAddressMode::RegBase &&
+    if (AM.BaseType == X86ISelAddressMode::RegBase &&
         AM.Base.Reg.getNode() == 0 &&
         AM.IndexReg.getNode() == 0 &&
         !AM.isRIPRel) {
@@ -924,7 +918,7 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
     break;
 
   case ISD::ADD:
-    if (!AlreadySelected) {
+    {
       X86ISelAddressMode Backup = AM;
       if (!MatchAddress(N.getNode()->getOperand(0), AM, false, Depth+1) &&
           !MatchAddress(N.getNode()->getOperand(1), AM, false, Depth+1))
@@ -939,8 +933,6 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
 
   case ISD::OR:
     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
-    if (AlreadySelected) break;
-      
     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
       X86ISelAddressMode Backup = AM;
       // Start with the LHS as an addr mode.
@@ -961,10 +953,9 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
   case ISD::AND: {
     // Handle "(x << C1) & C2" as "(X & (C2>>C1)) << C1" if safe and if this
     // allows us to fold the shift into this addressing mode.
-    if (AlreadySelected) break;
     SDValue Shift = N.getOperand(0);
     if (Shift.getOpcode() != ISD::SHL) break;
-    
+
     // Scale must not be used already.
     if (AM.IndexReg.getNode() != 0 || AM.Scale != 1) break;
 
@@ -987,14 +978,34 @@ bool X86DAGToDAGISel::MatchAddress(SDValue N, X86ISelAddressMode &AM,
       break;
     
     // Get the new AND mask, this folds to a constant.
+    SDValue X = Shift.getOperand(0);
     SDValue NewANDMask = CurDAG->getNode(ISD::SRL, N.getValueType(),
                                          SDValue(C2, 0), SDValue(C1, 0));
-    SDValue NewAND = CurDAG->getNode(ISD::AND, N.getValueType(),
-                                     Shift.getOperand(0), NewANDMask);
+    SDValue NewAND = CurDAG->getNode(ISD::AND, N.getValueType(), X, NewANDMask);
     SDValue NewSHIFT = CurDAG->getNode(ISD::SHL, N.getValueType(),
                                        NewAND, SDValue(C1, 0));
-    NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId());
-    NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId());
+
+    // Insert the new nodes into the topological ordering.
+    if (C1->getNodeId() > X.getNode()->getNodeId()) {
+      CurDAG->RepositionNode(X.getNode(), C1);
+      C1->setNodeId(X.getNode()->getNodeId());
+    }
+    if (NewANDMask.getNode()->getNodeId() == -1 ||
+        NewANDMask.getNode()->getNodeId() > X.getNode()->getNodeId()) {
+      CurDAG->RepositionNode(X.getNode(), NewANDMask.getNode());
+      NewANDMask.getNode()->setNodeId(X.getNode()->getNodeId());
+    }
+    if (NewAND.getNode()->getNodeId() == -1 ||
+        NewAND.getNode()->getNodeId() > Shift.getNode()->getNodeId()) {
+      CurDAG->RepositionNode(Shift.getNode(), NewAND.getNode());
+      NewAND.getNode()->setNodeId(Shift.getNode()->getNodeId());
+    }
+    if (NewSHIFT.getNode()->getNodeId() == -1 ||
+        NewSHIFT.getNode()->getNodeId() > N.getNode()->getNodeId()) {
+      CurDAG->RepositionNode(N.getNode(), NewSHIFT.getNode());
+      NewSHIFT.getNode()->setNodeId(N.getNode()->getNodeId());
+    }
+
     CurDAG->ReplaceAllUsesWith(N, NewSHIFT);
     
     AM.Scale = 1 << ShiftCst;
@@ -1212,14 +1223,6 @@ SDNode *X86DAGToDAGISel::SelectAtomic64(SDNode *Node, unsigned Opc) {
   if (!SelectAddr(In1, In1, Tmp0, Tmp1, Tmp2, Tmp3))
     return NULL;
   SDValue LSI = Node->getOperand(4);    // MemOperand
-  AddToISelQueue(Tmp0);
-  AddToISelQueue(Tmp1);
-  AddToISelQueue(Tmp2);
-  AddToISelQueue(Tmp3);
-  AddToISelQueue(In2L);
-  AddToISelQueue(In2H);
-  // For now, don't select the MemOperand object, we don't know how.
-  AddToISelQueue(Chain);
   const SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, In2L, In2H, LSI, Chain };
   return CurDAG->getTargetNode(Opc, MVT::i32, MVT::i32, MVT::Other, Ops, 8);
 }
@@ -1308,16 +1311,10 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
           std::swap(N0, N1);
       }
 
-      AddToISelQueue(N0);
       SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), LoReg,
                                               N0, SDValue()).getValue(1);
 
       if (foldedLoad) {
-        AddToISelQueue(N1.getOperand(0));
-        AddToISelQueue(Tmp0);
-        AddToISelQueue(Tmp1);
-        AddToISelQueue(Tmp2);
-        AddToISelQueue(Tmp3);
         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, N1.getOperand(0), InFlag };
         SDNode *CNode =
           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Ops, 6);
@@ -1325,7 +1322,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
         // Update the chain.
         ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
       } else {
-        AddToISelQueue(N1);
         InFlag =
           SDValue(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
       }
@@ -1436,18 +1432,12 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
         SDValue Tmp0, Tmp1, Tmp2, Tmp3, Move, Chain;
         if (TryFoldLoad(N, N0, Tmp0, Tmp1, Tmp2, Tmp3)) {
           SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, N0.getOperand(0) };
-          AddToISelQueue(N0.getOperand(0));
-          AddToISelQueue(Tmp0);
-          AddToISelQueue(Tmp1);
-          AddToISelQueue(Tmp2);
-          AddToISelQueue(Tmp3);
           Move =
             SDValue(CurDAG->getTargetNode(X86::MOVZX16rm8, MVT::i16, MVT::Other,
                                             Ops, 5), 0);
           Chain = Move.getValue(1);
           ReplaceUses(N0.getValue(1), Chain);
         } else {
-          AddToISelQueue(N0);
           Move =
             SDValue(CurDAG->getTargetNode(X86::MOVZX16rr8, MVT::i16, N0), 0);
           Chain = CurDAG->getEntryNode();
@@ -1455,7 +1445,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
         Chain  = CurDAG->getCopyToReg(Chain, X86::AX, Move, SDValue());
         InFlag = Chain.getValue(1);
       } else {
-        AddToISelQueue(N0);
         InFlag =
           CurDAG->getCopyToReg(CurDAG->getEntryNode(),
                                LoReg, N0, SDValue()).getValue(1);
@@ -1472,11 +1461,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
       }
 
       if (foldedLoad) {
-        AddToISelQueue(N1.getOperand(0));
-        AddToISelQueue(Tmp0);
-        AddToISelQueue(Tmp1);
-        AddToISelQueue(Tmp2);
-        AddToISelQueue(Tmp3);
         SDValue Ops[] = { Tmp0, Tmp1, Tmp2, Tmp3, N1.getOperand(0), InFlag };
         SDNode *CNode =
           CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Ops, 6);
@@ -1484,7 +1468,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
         // Update the chain.
         ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
       } else {
-        AddToISelQueue(N1);
         InFlag =
           SDValue(CurDAG->getTargetNode(Opc, MVT::Flag, N1, InFlag), 0);
       }
@@ -1540,7 +1523,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
       MVT SVT = cast<VTSDNode>(Node->getOperand(1))->getVT();
       if (SVT == MVT::i8 && !Subtarget->is64Bit()) {
         SDValue N0 = Node->getOperand(0);
-        AddToISelQueue(N0);
       
         SDValue TruncOp = SDValue(getTruncateTo8Bit(N0), 0);
         unsigned Opc = 0;
@@ -1573,7 +1555,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
     case ISD::TRUNCATE: {
       if (NVT == MVT::i8 && !Subtarget->is64Bit()) {
         SDValue Input = Node->getOperand(0);
-        AddToISelQueue(Node->getOperand(0));
         SDNode *ResNode = getTruncateTo8Bit(Input);
       
 #ifndef NDEBUG
@@ -1605,7 +1586,6 @@ SDNode *X86DAGToDAGISel::Select(SDValue N) {
           cast<GlobalAddressSDNode>(N2.getOperand(0))->getGlobal();
         SDValue Tmp1 = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
         SDValue Tmp2 = CurDAG->getTargetGlobalAddress(GV, TLI.getPointerTy());
-        AddToISelQueue(Chain);
         SDValue Ops[] = { Tmp1, Tmp2, Chain };
         return CurDAG->getTargetNode(TargetInstrInfo::DECLARE,
                                      MVT::Other, Ops, 3);
@@ -1647,10 +1627,6 @@ SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
   OutOps.push_back(Op1);
   OutOps.push_back(Op2);
   OutOps.push_back(Op3);
-  AddToISelQueue(Op0);
-  AddToISelQueue(Op1);
-  AddToISelQueue(Op2);
-  AddToISelQueue(Op3);
   return false;
 }