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.


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

1 files changed, 1 insertions, 27 deletions

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);