Eliminate the ISel priority queue, which used the topological order for a
authorDan Gohman <gohman@apple.com>
Wed, 5 Nov 2008 04:14:16 +0000 (04:14 +0000)
committerDan Gohman <gohman@apple.com>
Wed, 5 Nov 2008 04:14:16 +0000 (04:14 +0000)
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.

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

include/llvm/CodeGen/DAGISelHeader.h
include/llvm/CodeGen/SelectionDAG.h
lib/Target/ARM/ARMISelDAGToDAG.cpp
lib/Target/Alpha/AlphaISelDAGToDAG.cpp
lib/Target/CellSPU/SPUISelDAGToDAG.cpp
lib/Target/IA64/IA64ISelDAGToDAG.cpp
lib/Target/Mips/MipsISelDAGToDAG.cpp
lib/Target/PowerPC/PPCISelDAGToDAG.cpp
lib/Target/Sparc/SparcISelDAGToDAG.cpp
lib/Target/X86/X86ISelDAGToDAG.cpp
utils/TableGen/DAGISelEmitter.cpp

index ec7215218048d8824900eec5ea7400dedb963580..783c567a527bd8cb218947957108002aede2e8e9 100644 (file)
 #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());
 }
 
index 3e550c0a37ea3679c31f215d24bd3e4662a6fabf..1459c89ea0e558e016287b53d8c835a5275b29a4 100644 (file)
@@ -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) {
index 060f61ca70cb412d225b16fc5b94fa592c3ad71f..b281f84cb7207a249684b2f019fb74b623e3d87b 100644 (file)
@@ -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);
index e0ae5564ed81841ab1eca7e647732190a61d9fc5..801db44faf79847ba0304e0ca098c21e72405849 100644 (file)
@@ -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, 
index d6a492b575c74778160d3769b3bf27c12834d6fe..144f5781cda81dddc5e829299e63ce517331cc98 100644 (file)
@@ -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;
index ae59ea2489d4d2070ad0165033274f58f196961a..4532ed2623d956f9640f781f1d945bccea4dbda3 100644 (file)
@@ -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);
   }
index b31bcbdc0b365b83da4d2d444033ce1277270d32..95854bb5485599e6d4ff1346def9be950b8ef4be 100644 (file)
@@ -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);
index 37ca2be85d69a6f4e54f5a2f4fd89b3e3f96042a..c839121c33b0bace45f40a4d218da8ad93ed6610 100644 (file)
@@ -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);
index ceba75d788955b6dfe7a42d21658e7eb66ddd0f3..34846529b21cf239335113f032f1958f87237553 100644 (file)
@@ -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);
index 7ba62189ca068359c40bae864292773e0d1427c8..137944ac88d113214f0ee301fdc4f6bba8bfc480 100644 (file)
@@ -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;
 }
 
index 82d414884b57bff3adff8096f28de246ab61643c..18293314263ae73f389acb8530e31a93bb38370a 100644 (file)
@@ -856,14 +856,12 @@ public:
         NodeOps.push_back(Val);
       } else if (N->isLeaf() && (CP = NodeGetComplexPattern(N, CGP))) {
         for (unsigned i = 0; i < CP->getNumOperands(); ++i) {
-          emitCode("AddToISelQueue(CPTmp" + utostr(i) + ");");
           NodeOps.push_back("CPTmp" + utostr(i));
         }
       } else {
         // This node, probably wrapped in a SDNodeXForm, behaves like a leaf
         // node even if it isn't one. Don't select it.
         if (!LikeLeaf) {
-          emitCode("AddToISelQueue(" + Val + ");");
           if (isRoot && N->isLeaf()) {
             emitCode("ReplaceUses(N, " + Val + ");");
             emitCode("return NULL;");
@@ -969,11 +967,9 @@ public:
         for (unsigned i = 0, e = OrigChains.size(); i < e; ++i) {
           emitCode("if (" + OrigChains[i].first + ".getNode() != " +
                    OrigChains[i].second + ".getNode()) {");
-          emitCode("  AddToISelQueue(" + OrigChains[i].first + ");");
           emitCode("  InChains.push_back(" + OrigChains[i].first + ");");
           emitCode("}");
         }
-        emitCode("AddToISelQueue(" + ChainName + ");");
         emitCode("InChains.push_back(" + ChainName + ");");
         emitCode(ChainName + " = CurDAG->getNode(ISD::TokenFactor, MVT::Other, "
                  "&InChains[0], InChains.size());");
@@ -1020,8 +1016,6 @@ public:
 
       // Emit all the chain and CopyToReg stuff.
       bool ChainEmitted = NodeHasChain;
-      if (NodeHasChain)
-        emitCode("AddToISelQueue(" + ChainName + ");");
       if (NodeHasInFlag || HasImpInputs)
         EmitInFlagSelectCode(Pattern, "N", ChainEmitted,
                              InFlagDecled, ResNodeDecled, true);
@@ -1033,7 +1027,6 @@ public:
         if (NodeHasOptInFlag) {
           emitCode("if (HasInFlag) {");
           emitCode("  InFlag = N.getOperand(N.getNumOperands()-1);");
-          emitCode("  AddToISelQueue(InFlag);");
           emitCode("}");
         }
       }
@@ -1098,7 +1091,6 @@ public:
         emitCode("for (unsigned i = NumInputRootOps + " + utostr(NodeHasChain) +
                  ", e = N.getNumOperands()" + EndAdjust + "; i != e; ++i) {");
 
-        emitCode("  AddToISelQueue(N.getOperand(i));");
         emitCode("  Ops" + utostr(OpsNo) + ".push_back(N.getOperand(i));");
         emitCode("}");
       }
@@ -1383,14 +1375,12 @@ private:
                 InFlagDecled = true;
               } else
                 emitCode("InFlag = " + RootName + utostr(OpNo) + ";");
-              emitCode("AddToISelQueue(InFlag);");
             } else {
               if (!ChainEmitted) {
                 emitCode("SDValue Chain = CurDAG->getEntryNode();");
                 ChainName = "Chain";
                 ChainEmitted = true;
               }
-              emitCode("AddToISelQueue(" + RootName + utostr(OpNo) + ");");
               if (!InFlagDecled) {
                 emitCode("SDValue InFlag(0, 0);");
                 InFlagDecled = true;
@@ -1416,7 +1406,6 @@ private:
       } else
         emitCode("InFlag = " + RootName +
                ".getOperand(" + utostr(OpNo) + ");");
-      emitCode("AddToISelQueue(InFlag);");
     }
   }
 };
@@ -1901,10 +1890,6 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  std::vector<SDValue> Ops(N.getNode()->op_begin(), N.getNode()->op_end());\n"
      << "  SelectInlineAsmMemoryOperands(Ops);\n\n"
     
-     << "  // Ensure that the asm operands are themselves selected.\n"
-     << "  for (unsigned j = 0, e = Ops.size(); j != e; ++j)\n"
-     << "    AddToISelQueue(Ops[j]);\n\n"
-    
      << "  std::vector<MVT> VTs;\n"
      << "  VTs.push_back(MVT::Other);\n"
      << "  VTs.push_back(MVT::Flag);\n"
@@ -1922,7 +1907,6 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  SDValue Chain = N.getOperand(0);\n"
      << "  unsigned C = cast<LabelSDNode>(N)->getLabelID();\n"
      << "  SDValue Tmp = CurDAG->getTargetConstant(C, MVT::i32);\n"
-     << "  AddToISelQueue(Chain);\n"
      << "  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::DBG_LABEL,\n"
      << "                              MVT::Other, Tmp, Chain);\n"
      << "}\n\n";
@@ -1931,7 +1915,6 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  SDValue Chain = N.getOperand(0);\n"
      << "  unsigned C = cast<LabelSDNode>(N)->getLabelID();\n"
      << "  SDValue Tmp = CurDAG->getTargetConstant(C, MVT::i32);\n"
-     << "  AddToISelQueue(Chain);\n"
      << "  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::EH_LABEL,\n"
      << "                              MVT::Other, Tmp, Chain);\n"
      << "}\n\n";
@@ -1949,7 +1932,6 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());\n"
      << "  SDValue Tmp2 = "
      << "CurDAG->getTargetGlobalAddress(GV, TLI.getPointerTy());\n"
-     << "  AddToISelQueue(Chain);\n"
      << "  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::DECLARE,\n"
      << "                              MVT::Other, Tmp1, Tmp2, Chain);\n"
      << "}\n\n";
@@ -1959,7 +1941,6 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  SDValue N1 = N.getOperand(1);\n"
      << "  unsigned C = cast<ConstantSDNode>(N1)->getZExtValue();\n"
      << "  SDValue Tmp = CurDAG->getTargetConstant(C, MVT::i32);\n"
-     << "  AddToISelQueue(N0);\n"
      << "  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::EXTRACT_SUBREG,\n"
      << "                              N.getValueType(), N0, Tmp);\n"
      << "}\n\n";
@@ -1970,8 +1951,6 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  SDValue N2 = N.getOperand(2);\n"
      << "  unsigned C = cast<ConstantSDNode>(N2)->getZExtValue();\n"
      << "  SDValue Tmp = CurDAG->getTargetConstant(C, MVT::i32);\n"
-     << "  AddToISelQueue(N1);\n"
-     << "  AddToISelQueue(N0);\n"
      << "  return CurDAG->SelectNodeTo(N.getNode(), TargetInstrInfo::INSERT_SUBREG,\n"
      << "                              N.getValueType(), N0, N1, Tmp);\n"
      << "}\n\n";
@@ -1985,6 +1964,7 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  switch (N.getOpcode()) {\n"
      << "  default: break;\n"
      << "  case ISD::EntryToken:       // These leaves remain the same.\n"
+     << "  case ISD::MEMOPERAND:\n"
      << "  case ISD::BasicBlock:\n"
      << "  case ISD::Register:\n"
      << "  case ISD::HANDLENODE:\n"
@@ -1995,22 +1975,17 @@ void DAGISelEmitter::EmitInstructionSelector(std::ostream &OS) {
      << "  case ISD::TargetExternalSymbol:\n"
      << "  case ISD::TargetJumpTable:\n"
      << "  case ISD::TargetGlobalTLSAddress:\n"
-     << "  case ISD::TargetGlobalAddress: {\n"
+     << "  case ISD::TargetGlobalAddress:\n"
+     << "  case ISD::TokenFactor:\n"
+     << "  case ISD::CopyFromReg:\n"
+     << "  case ISD::CopyToReg: {\n"
      << "    return NULL;\n"
      << "  }\n"
      << "  case ISD::AssertSext:\n"
      << "  case ISD::AssertZext: {\n"
-     << "    AddToISelQueue(N.getOperand(0));\n"
      << "    ReplaceUses(N, N.getOperand(0));\n"
      << "    return NULL;\n"
      << "  }\n"
-     << "  case ISD::TokenFactor:\n"
-     << "  case ISD::CopyFromReg:\n"
-     << "  case ISD::CopyToReg: {\n"
-     << "    for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)\n"
-     << "      AddToISelQueue(N.getOperand(i));\n"
-     << "    return NULL;\n"
-     << "  }\n"
      << "  case ISD::INLINEASM: return Select_INLINEASM(N);\n"
      << "  case ISD::DBG_LABEL: return Select_DBG_LABEL(N);\n"
      << "  case ISD::EH_LABEL: return Select_EH_LABEL(N);\n"