[DAG, X86] Improve Dependency analysis when doing multi-node

Instruction Selection

Cleanup cycle/validity checks in ISel (IsLegalToFold,
HandleMergeInputChains) and X86 (isFusableLoadOpStore). Now do a full
search for cycles / dependencies pruning the search when topological
property of NodeId allows.

As part of this propogate the NodeId-based cutoffs to narrow
hasPreprocessorHelper searches.

Reviewers: craig.topper, bogner

Subscribers: llvm-commits, hiraditya

Differential Revision: https://reviews.llvm.org/D41293

llvm-svn: 324359

1 files changed, 39 insertions, 26 deletions

diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
index d932b57f244..975e8c5e3c2 100644
--- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -2104,47 +2104,58 @@ static bool isFusableLoadOpStorePattern(StoreSDNode *StoreNode,
   // the load output chain as an operand. Return InputChain by reference.
   SDValue Chain = StoreNode->getChain();
 
-  bool ChainCheck = false;
   if (Chain == Load.getValue(1)) {
-    ChainCheck = true;
     InputChain = LoadNode->getChain();
-  } else if (Chain.getOpcode() == ISD::TokenFactor) {
+    return true;
+  }
+
+  if (Chain.getOpcode() == ISD::TokenFactor) {
+    // Fusing Load-Op-Store requires predecessors of store must also
+    // be predecessors of the load. This addition may cause a loop. We
+    // can check this by doing a search for Load in the new
+    // dependencies. As this can be expensive, heuristically prune
+    // this search by visiting the uses and make sure they all have
+    // smaller node id than the load.
+
+    bool FoundLoad = false;
     SmallVector<SDValue, 4> ChainOps;
+    SmallVector<const SDNode *, 4> LoopWorklist;
+    SmallPtrSet<const SDNode *, 16> Visited;
     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) {
       SDValue Op = Chain.getOperand(i);
       if (Op == Load.getValue(1)) {
-        ChainCheck = true;
+        FoundLoad = 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);
+    }
 
-      // 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;
-      }
+    if (!FoundLoad)
+      return false;
 
-      ChainOps.push_back(Op);
+    // If Loop Worklist is not empty. Check if we would make a loop.
+    if (!LoopWorklist.empty()) {
+      const unsigned int Max = 8192;
+      // if Load is predecessor to potentially loop inducing chain
+      // dependencies.
+      if (SDNode::hasPredecessorHelper(Load.getNode(), Visited, LoopWorklist,
+                                       Max, true))
+        return false;
+      // Fail conservatively if we ended loop search early.
+      if (Visited.size() >= Max)
+        return false;
     }
 
-    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);
+    // Make a new TokenFactor with all the other input chains except
+    // for the load.
+    InputChain =
+        CurDAG->getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ChainOps);
+    return true;
   }
-  if (!ChainCheck)
-    return false;
-
-  return true;
+  return false;
 }
 
 // Change a chain of {load; op; store} of the same value into a simple op
@@ -2374,6 +2385,8 @@ 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);