Revert: r327172 "Correct load-op-store cycle detection analysis"

        r327171 "Improve Dependency analysis when doing multi-node Instruction Selection"
        r328170 "[DAG] Enforce stricter NodeId invariant during Instruction selection"

Reverting patch as NodeId invariant change is causing pathological
increases in compile time on PPC

llvm-svn: 327197

6 files changed, 52 insertions, 81 deletions

diff --git a/llvm/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp b/llvm/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp
index 6a47a5ba50c..90cd4ffaf0b 100644
--- a/llvm/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp
+++ b/llvm/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp
@@ -766,11 +766,12 @@ void AMDGPUDAGToDAGISel::SelectADD_SUB_I64(SDNode *N) {
 
   if (ProduceCarry) {
     // Replace the carry-use
-    ReplaceUses(SDValue(N, 1), SDValue(AddHi, 1));
+    CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 1), SDValue(AddHi, 1));
   }
 
   // Replace the remaining uses.
-  ReplaceNode(N, RegSequence);
+  CurDAG->ReplaceAllUsesWith(N, RegSequence);
+  CurDAG->RemoveDeadNode(N);
 }
 
 void AMDGPUDAGToDAGISel::SelectUADDO_USUBO(SDNode *N) {
diff --git a/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp b/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
index 0063303ac48..94fe84c8751 100644
--- a/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
+++ b/llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp
@@ -500,7 +500,7 @@ bool ARMDAGToDAGISel::canExtractShiftFromMul(const SDValue &N,
 
 void ARMDAGToDAGISel::replaceDAGValue(const SDValue &N, SDValue M) {
   CurDAG->RepositionNode(N.getNode()->getIterator(), M.getNode());
-  ReplaceUses(N, M);
+  CurDAG->ReplaceAllUsesWith(N, M);
 }
 
 bool ARMDAGToDAGISel::SelectImmShifterOperand(SDValue N,
diff --git a/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp b/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp
index fa992490f5d..3540cf06b9c 100644
--- a/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp
@@ -662,7 +662,7 @@ void HexagonDAGToDAGISel::SelectBitcast(SDNode *N) {
     return;
   }
 
-  ReplaceUses(SDValue(N, 0), N->getOperand(0));
+  CurDAG->ReplaceAllUsesOfValueWith(SDValue(N,0), N->getOperand(0));
   CurDAG->RemoveDeadNode(N);
 }
 
@@ -726,6 +726,7 @@ void HexagonDAGToDAGISel::SelectTypecast(SDNode *N) {
   SDNode *T = CurDAG->MorphNodeTo(N, N->getOpcode(),
                                   CurDAG->getVTList(OpTy), {Op});
   ReplaceNode(T, Op.getNode());
+  CurDAG->RemoveDeadNode(T);
 }
 
 void HexagonDAGToDAGISel::SelectP2D(SDNode *N) {
@@ -2184,3 +2185,4 @@ void HexagonDAGToDAGISel::rebalanceAddressTrees() {
   RootHeights.clear();
   RootWeights.clear();
 }
+
diff --git a/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp b/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp
index 285197a909e..46f5bb4de8a 100644
--- a/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp
@@ -1953,6 +1953,7 @@ void HvxSelector::selectShuffle(SDNode *N) {
   // If the mask is all -1's, generate "undef".
   if (!UseLeft && !UseRight) {
     ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode());
+    DAG.RemoveDeadNode(N);
     return;
   }
 
@@ -2008,6 +2009,7 @@ void HvxSelector::selectRor(SDNode *N) {
     NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV});
 
   ISel.ReplaceNode(N, NewN);
+  DAG.RemoveDeadNode(N);
 }
 
 void HvxSelector::selectVAlign(SDNode *N) {
@@ -2068,7 +2070,8 @@ void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) {
   MemOp[0] = cast<MemIntrinsicSDNode>(N)->getMemOperand();
   cast<MachineSDNode>(Result)->setMemRefs(MemOp, MemOp + 1);
 
-  ReplaceNode(N, Result);
+  ReplaceUses(N, Result);
+  CurDAG->RemoveDeadNode(N);
 }
 
 void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) {
@@ -2106,7 +2109,8 @@ void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) {
   MemOp[0] = cast<MemIntrinsicSDNode>(N)->getMemOperand();
   cast<MachineSDNode>(Result)->setMemRefs(MemOp, MemOp + 1);
 
-  ReplaceNode(N, Result);
+  ReplaceUses(N, Result);
+  CurDAG->RemoveDeadNode(N);
 }
 
 void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) {
@@ -2149,3 +2153,5 @@ void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) {
   ReplaceUses(SDValue(N, 1), SDValue(Result, 1));
   CurDAG->RemoveDeadNode(N);
 }
+
+
diff --git a/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp b/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
index 6e2130828bb..9bf2474915c 100644
--- a/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
+++ b/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
@@ -596,13 +596,7 @@ static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
   if (N.getNode()->getNodeId() == -1 ||
       N.getNode()->getNodeId() > Pos->getNodeId()) {
     DAG->RepositionNode(Pos->getIterator(), N.getNode());
-    // Mark Node as invalid for pruning as after this it may be a successor to a
-    // selected node but otherwise be in the same position of Pos.
-    // Conservatively mark it with the same -abs(Id) to assure node id
-    // invariant is preserved.
-    int PId = Pos->getNodeId();
-    int InvalidatedPId = -(PId + 1);
-    N->setNodeId((PId > 0) ? InvalidatedPId : PId);
+    N.getNode()->setNodeId(Pos->getNodeId());
   }
 }
 
@@ -1033,7 +1027,8 @@ bool SystemZDAGToDAGISel::tryRISBGZero(SDNode *N) {
   };
   SDValue New = convertTo(
       DL, VT, SDValue(CurDAG->getMachineNode(Opcode, DL, OpcodeVT, Ops), 0));
-  ReplaceNode(N, New.getNode());
+  ReplaceUses(N, New.getNode());
+  CurDAG->RemoveDeadNode(N);
   return true;
 }
 
@@ -1124,7 +1119,8 @@ void SystemZDAGToDAGISel::splitLargeImmediate(unsigned Opcode, SDNode *Node,
   SDValue Lower = CurDAG->getConstant(LowerVal, DL, VT);
   SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower);
 
-  ReplaceNode(Node, Or.getNode());
+  ReplaceUses(Node, Or.getNode());
+  CurDAG->RemoveDeadNode(Node);
 
   SelectCode(Or.getNode());
 }
@@ -1622,3 +1618,4 @@ void SystemZDAGToDAGISel::PreprocessISelDAG() {
   if (MadeChange)
     CurDAG->RemoveDeadNodes();
 }
+
diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
index ebcd15230b9..bcac241bb3a 100644
--- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -2109,86 +2109,52 @@ static bool isFusableLoadOpStorePattern(StoreSDNode *StoreNode,
       LoadNode->getOffset() != StoreNode->getOffset())
     return false;
 
-  bool FoundLoad = false;
-  SmallVector<SDValue, 4> ChainOps;
-  SmallVector<const SDNode *, 4> LoopWorklist;
-  SmallPtrSet<const SDNode *, 16> Visited;
-  const unsigned int Max = 1024;
-
-  //  Visualization of Load-Op-Store fusion:
-  // -------------------------
-  // Legend:
-  //    *-lines = Chain operand dependencies.
-  //    |-lines = Normal operand dependencies.
-  //    Dependencies flow down and right. n-suffix references multiple nodes.
-  //
-  //        C                        Xn  C
-  //        *                         *  *
-  //        *                          * *
-  //  Xn  A-LD    Yn                    TF         Yn
-  //   *    * \   |                       *        |
-  //    *   *  \  |                        *       |
-  //     *  *   \ |             =>       A--LD_OP_ST
-  //      * *    \|                                 \
-  //       TF    OP                                  \
-  //         *   | \                                  Zn
-  //          *  |  \
-  //         A-ST    Zn
-  //
-
-  // This merge induced dependences from: #1: Xn -> LD, OP, Zn
-  //                                      #2: Yn -> LD
-  //                                      #3: ST -> Zn
-
-  // Ensure the transform is safe by checking for the dual
-  // dependencies to make sure we do not induce a loop.
-
-  // As LD is a predecessor to both OP and ST we can do this by checking:
-  //  a). if LD is a predecessor to a member of Xn or Yn.
-  //  b). if a Zn is a predecessor to ST.
-
-  // However, (b) can only occur through being a chain predecessor to
-  // ST, which is the same as Zn being a member or predecessor of Xn,
-  // which is a subset of LD being a predecessor of Xn. So it's
-  // subsumed by check (a).
-
+  // Check if the chain is produced by the load or is a TokenFactor with
+  // the load output chain as an operand. Return InputChain by reference.
   SDValue Chain = StoreNode->getChain();
 
-  // Gather X elements in ChainOps.
+  bool ChainCheck = false;
   if (Chain == Load.getValue(1)) {
-    FoundLoad = true;
-    ChainOps.push_back(Load.getOperand(0));
+    ChainCheck = true;
+    InputChain = LoadNode->getChain();
   } else if (Chain.getOpcode() == ISD::TokenFactor) {
+    SmallVector<SDValue, 4> ChainOps;
     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) {
       SDValue Op = Chain.getOperand(i);
       if (Op == Load.getValue(1)) {
-        FoundLoad = true;
+        ChainCheck = true;
         // Drop Load, but keep its chain. No cycle check necessary.
         ChainOps.push_back(Load.getOperand(0));
         continue;
       }
-      LoopWorklist.push_back(Op.getNode());
-      ChainOps.push_back(Op);
-    }
-  }
 
-  if (!FoundLoad)
-    return false;
+      // Make sure using Op as part of the chain would not cause a cycle here.
+      // In theory, we could check whether the chain node is a predecessor of
+      // the load. But that can be very expensive. Instead visit the uses and
+      // make sure they all have smaller node id than the load.
+      int LoadId = LoadNode->getNodeId();
+      for (SDNode::use_iterator UI = Op.getNode()->use_begin(),
+             UE = UI->use_end(); UI != UE; ++UI) {
+        if (UI.getUse().getResNo() != 0)
+          continue;
+        if (UI->getNodeId() > LoadId)
+          return false;
+      }
 
-  // Worklist is currently Xn. Add Yn to worklist.
-  for (SDValue Op : StoredVal->ops())
-    if (Op.getNode() != LoadNode)
-      LoopWorklist.push_back(Op.getNode());
+      ChainOps.push_back(Op);
+    }
 
-  // Check (a) if Load is a predecessor to Xn + Yn
-  if (SDNode::hasPredecessorHelper(Load.getNode(), Visited, LoopWorklist, Max,
-                                   true))
+    if (ChainCheck)
+      // Make a new TokenFactor with all the other input chains except
+      // for the load.
+      InputChain = CurDAG->getNode(ISD::TokenFactor, SDLoc(Chain),
+                                   MVT::Other, ChainOps);
+  }
+  if (!ChainCheck)
     return false;
 
-  InputChain =
-      CurDAG->getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ChainOps);
   return true;
-  }
+}
 
 // Change a chain of {load; op; store} of the same value into a simple op
 // through memory of that value, if the uses of the modified value and its
@@ -2417,8 +2383,6 @@ bool X86DAGToDAGISel::foldLoadStoreIntoMemOperand(SDNode *Node) {
   MemOp[1] = LoadNode->getMemOperand();
   Result->setMemRefs(MemOp, MemOp + 2);
 
-  // Update Load Chain uses as well.
-  ReplaceUses(SDValue(LoadNode, 1), SDValue(Result, 1));
   ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
   ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
   CurDAG->RemoveDeadNode(Node);
@@ -3130,7 +3094,8 @@ void X86DAGToDAGISel::Select(SDNode *Node) {
       // Emit a testl or testw.
       SDNode *NewNode = CurDAG->getMachineNode(Op, dl, MVT::i32, Reg, Imm);
       // Replace CMP with TEST.
-      ReplaceNode(Node, NewNode);
+      CurDAG->ReplaceAllUsesWith(Node, NewNode);
+      CurDAG->RemoveDeadNode(Node);
       return;
     }
     break;