11 files changed, 74 insertions, 308 deletions

diff --git a/include/llvm/CodeGen/DAGISelHeader.h b/include/llvm/CodeGen/DAGISelHeader.h
index ec72152180..783c567a52 100644
--- a/include/llvm/CodeGen/DAGISelHeader.h
+++ b/include/llvm/CodeGen/DAGISelHeader.h
@@ -21,15 +21,10 @@
 #ifndef LLVM_CODEGEN_DAGISEL_HEADER_H
 #define LLVM_CODEGEN_DAGISEL_HEADER_H
 
-/// ISelQueue - Instruction selector priority queue sorted 
-/// in the order of decreasing NodeId() values.
-std::vector<SDNode*> ISelQueue;
-
-/// Keep track of nodes which have already been added to queue.
-unsigned char *ISelQueued;
-
-/// Keep track of nodes which have already been selected.
-unsigned char *ISelSelected;
+/// ISelPosition - Node iterator marking the current position of
+/// instruction selection as it procedes through the topologically-sorted
+/// node list.
+SelectionDAG::allnodes_iterator ISelPosition;
 
 /// IsChainCompatible - Returns true if Chain is Op or Chain does
 /// not reach Op.
@@ -46,97 +41,38 @@ static bool IsChainCompatible(SDNode *Chain, SDNode *Op) {
   return true;
 }
 
-/// isel_sort - Sorting functions for the selection queue in the
-/// decreasing NodeId order.
-struct isel_sort : public std::binary_function<SDNode*, SDNode*, bool> {
-  bool operator()(const SDNode* left, const SDNode* right) const {
-    return left->getNodeId() < right->getNodeId();
-  }
-};
-
-/// setQueued - marks the node with a given NodeId() as element of the 
-/// instruction selection queue.
-inline void setQueued(int Id) {
-  ISelQueued[Id / 8] |= 1 << (Id % 8);
-}
-
-/// isSelected - checks if the node with a given NodeId() is
-/// in the instruction selection queue already.
-inline bool isQueued(int Id) {
-  return ISelQueued[Id / 8] & (1 << (Id % 8));
-}
-
-/// setSelected - marks the node with a given NodeId() as selected.
-inline void setSelected(int Id) {
-  ISelSelected[Id / 8] |= 1 << (Id % 8);
-}
-
-/// isSelected - checks if the node with a given NodeId() is
-/// selected already.
-inline bool isSelected(int Id) {
-  return ISelSelected[Id / 8] & (1 << (Id % 8));
-}
-
-/// AddToISelQueue - adds a node to the instruction 
-/// selection queue.
-void AddToISelQueue(SDValue N) DISABLE_INLINE {
-  int Id = N.getNode()->getNodeId();
-  if (Id != -1 && !isQueued(Id)) {
-    ISelQueue.push_back(N.getNode());
-    std::push_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
-    setQueued(Id);
+/// ISelUpdater - helper class to handle updates of the 
+/// instruciton selection graph.
+class VISIBILITY_HIDDEN ISelUpdater : public SelectionDAG::DAGUpdateListener {
+  SelectionDAG::allnodes_iterator &ISelPosition;
+  bool HadDelete; // Indicate if any deletions were done.
+public:
+  explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp)
+    : ISelPosition(isp) {}
+  
+  /// NodeDeleted - remove node from the selection queue.
+  virtual void NodeDeleted(SDNode *N, SDNode *E) {
+    if (ISelPosition == SelectionDAG::allnodes_iterator(N))
+      ++ISelPosition;
   }
-}
-
-/// ISelQueueUpdater - helper class to handle updates of the 
-/// instruciton selection queue.
-class VISIBILITY_HIDDEN ISelQueueUpdater :
-  public SelectionDAG::DAGUpdateListener {
-    std::vector<SDNode*> &ISelQueue;
-    bool HadDelete; // Indicate if any deletions were done.
-  public:
-    explicit ISelQueueUpdater(std::vector<SDNode*> &isq)
-      : ISelQueue(isq), HadDelete(false) {}
-    
-    bool hadDelete() const { return HadDelete; }
-
-    /// NodeDeleted - remove node from the selection queue.
-    virtual void NodeDeleted(SDNode *N, SDNode *E) {
-      ISelQueue.erase(std::remove(ISelQueue.begin(), ISelQueue.end(), N),
-                      ISelQueue.end());
-      HadDelete = true;
-    }
-
-    /// NodeUpdated - Ignore updates for now.
-    virtual void NodeUpdated(SDNode *N) {}
-  };
-
-/// UpdateQueue - update the instruction selction queue to maintain 
-/// the decreasing NodeId() ordering property.
-inline void UpdateQueue(const ISelQueueUpdater &ISQU) {
-  if (ISQU.hadDelete())
-    std::make_heap(ISelQueue.begin(), ISelQueue.end(),isel_sort());
-}
 
+  /// NodeUpdated - Ignore updates for now.
+  virtual void NodeUpdated(SDNode *N) {}
+};
 
 /// ReplaceUses - replace all uses of the old node F with the use
 /// of the new node T.
 void ReplaceUses(SDValue F, SDValue T) DISABLE_INLINE {
-  ISelQueueUpdater ISQU(ISelQueue);
-  CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISQU);
-  setSelected(F.getNode()->getNodeId());
-  UpdateQueue(ISQU);
+  ISelUpdater ISU(ISelPosition);
+  CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU);
 }
 
 /// ReplaceUses - replace all uses of the old nodes F with the use
 /// of the new nodes T.
 void ReplaceUses(const SDValue *F, const SDValue *T,
                  unsigned Num) DISABLE_INLINE {
-  ISelQueueUpdater ISQU(ISelQueue);
-  CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISQU);
-  for (unsigned i = 0; i != Num; ++i)
-    setSelected(F[i].getNode()->getNodeId());
-  UpdateQueue(ISQU);
+  ISelUpdater ISU(ISelPosition);
+  CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU);
 }
 
 /// ReplaceUses - replace all uses of the old node F with the use
@@ -144,42 +80,30 @@ void ReplaceUses(const SDValue *F, const SDValue *T,
 void ReplaceUses(SDNode *F, SDNode *T) DISABLE_INLINE {
   unsigned FNumVals = F->getNumValues();
   unsigned TNumVals = T->getNumValues();
-  ISelQueueUpdater ISQU(ISelQueue);
+  ISelUpdater ISU(ISelPosition);
   if (FNumVals != TNumVals) {
     for (unsigned i = 0, e = std::min(FNumVals, TNumVals); i < e; ++i)
-     CurDAG->ReplaceAllUsesOfValueWith(SDValue(F, i), SDValue(T, i), &ISQU);
+     CurDAG->ReplaceAllUsesOfValueWith(SDValue(F, i), SDValue(T, i), &ISU);
   } else {
-    CurDAG->ReplaceAllUsesWith(F, T, &ISQU);
+    CurDAG->ReplaceAllUsesWith(F, T, &ISU);
   }
-  setSelected(F->getNodeId());
-  UpdateQueue(ISQU);
 }
 
 /// SelectRoot - Top level entry to DAG instruction selector.
 /// Selects instructions starting at the root of the current DAG.
 void SelectRoot(SelectionDAG &DAG) {
   SelectRootInit();
-  unsigned NumBytes = (DAGSize + 7) / 8;
-  ISelQueued   = new unsigned char[NumBytes];
-  ISelSelected = new unsigned char[NumBytes];
-  memset(ISelQueued,   0, NumBytes);
-  memset(ISelSelected, 0, NumBytes);
 
   // Create a dummy node (which is not added to allnodes), that adds
   // a reference to the root node, preventing it from being deleted,
   // and tracking any changes of the root.
   HandleSDNode Dummy(CurDAG->getRoot());
-  ISelQueue.push_back(CurDAG->getRoot().getNode());
+  ISelPosition = next(SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()));
 
   // Select pending nodes from the instruction selection queue
   // until no more nodes are left for selection.
-  while (!ISelQueue.empty()) {
-    SDNode *Node = ISelQueue.front();
-    std::pop_heap(ISelQueue.begin(), ISelQueue.end(), isel_sort());
-    ISelQueue.pop_back();
-    // Skip already selected nodes.
-    if (isSelected(Node->getNodeId()))
-      continue;
+  while (ISelPosition != CurDAG->allnodes_begin()) {
+    SDNode *Node = --ISelPosition;
 #if 0
     DAG.setSubgraphColor(Node, "red");
 #endif
@@ -199,16 +123,11 @@ void SelectRoot(SelectionDAG &DAG) {
     // If after the replacement this node is not used any more,
     // remove this dead node.
     if (Node->use_empty()) { // Don't delete EntryToken, etc.
-      ISelQueueUpdater ISQU(ISelQueue);
-      CurDAG->RemoveDeadNode(Node, &ISQU);
-      UpdateQueue(ISQU);
+      ISelUpdater ISU(ISelPosition);
+      CurDAG->RemoveDeadNode(Node, &ISU);
     }
   }
 
-  delete[] ISelQueued;
-  ISelQueued = NULL;
-  delete[] ISelSelected;
-  ISelSelected = NULL;
   CurDAG->setRoot(Dummy.getValue());
 }
 
diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 3e550c0a37..1459c89ea0 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -693,6 +693,13 @@ public:
   /// topological order. Returns the number of nodes.
   unsigned AssignTopologicalOrder();
 
+  /// RepositionNode - Move node N in the AllNodes list to be immediately
+  /// before the given iterator Position. This may be used to update the
+  /// topological ordering when the list of nodes is modified.
+  void RepositionNode(allnodes_iterator Position, SDNode *N) {
+    AllNodes.insert(Position, AllNodes.remove(N));
+  }
+
   /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
   /// operation.
   static bool isCommutativeBinOp(unsigned Opcode) {
diff --git a/lib/Target/ARM/ARMISelDAGToDAG.cpp b/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 060f61ca70..b281f84cb7 100644
--- a/lib/Target/ARM/ARMISelDAGToDAG.cpp
+++ b/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/lib/Target/Alpha/AlphaISelDAGToDAG.cpp b/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
index e0ae5564ed..801db44faf 100644
--- a/lib/Target/Alpha/AlphaISelDAGToDAG.cpp
+++ b/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/lib/Target/CellSPU/SPUISelDAGToDAG.cpp b/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
index d6a492b575..144f5781cd 100644
--- a/lib/Target/CellSPU/SPUISelDAGToDAG.cpp
+++ b/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/lib/Target/IA64/IA64ISelDAGToDAG.cpp b/lib/Target/IA64/IA64ISelDAGToDAG.cpp
index ae59ea2489..4532ed2623 100644
--- a/lib/Target/IA64/IA64ISelDAGToDAG.cpp
+++ b/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/lib/Target/Mips/MipsISelDAGToDAG.cpp b/lib/Target/Mips/MipsISelDAGToDAG.cpp
index b31bcbdc0b..95854bb548 100644
--- a/lib/Target/Mips/MipsISelDAGToDAG.cpp
+++ b/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/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
index 37ca2be85d..c839121c33 100644
--- a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp
+++ b/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/lib/Target/Sparc/SparcISelDAGToDAG.cpp b/lib/Target/Sparc/SparcISelDAGToDAG.cpp
index ceba75d788..34846529b2 100644
--- a/lib/Target/Sparc/SparcISelDAGToDAG.cpp
+++ b/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/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp
index 7ba62189ca..137944ac88 100644
--- a/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/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(