[DAG] Bound loop dependence check in merge optimization.

[niravd]

Summary

The loop dependence check looks for dependencies between store merge
candidates not captured by the chain sub-DAG doing a check of
predecessors which may be very large. Conservatively bound number of
nodes checked for compilation time. (Resolves PR34326).

[efriedma]

I guess this is okay...? Adding arbitrary limits isn't nice, but I don't know what a nice solution looks like here. (Probably we should be using a different algorithm to find stores to merge; maybe something more like a DAG scheduling algorithm.)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12795 ↗

(On Diff #112912)

This helps in cases where there's a common ancestor nearby... but does that actually cover all interesting cases?

[hans]

Based on Dimitry's comment in https://bugs.llvm.org/show_bug.cgi?id=34326#c13 this seems to solve the problem. Can we get it landed so it can be part of 5.0.0?

[hans]

I'm not sure if Nirav is around.

Eli: do you think this is ok for landing? It seems to fix the issue in the PR and is probably the final thing we need for 5.0.0.

[hans]

I've gone ahead and committed this to unblock the release.

llvm/trunk/include/llvm/CodeGen/SelectionDAGNodes.h

public:
   /// Returns true if N is a predecessor of any node in Worklist. This
   /// helper keeps Visited and Worklist sets externally to allow unions
   /// searches to be performed in parallel, caching of results across
   /// queries and incremental addition to Worklist. Stops early if N is
   /// found but will resume. Remember to clear Visited and Worklists
   /// if DAG changes.
   static bool hasPredecessorHelper(const SDNode *N,
                                    SmallPtrSetImpl<const SDNode *> &Visited,
-                                   SmallVectorImpl<const SDNode *> &Worklist) {
+                                   SmallVectorImpl<const SDNode *> &Worklist,
+                                   unsigned int MaxSteps = 0) {
     if (Visited.count(N))
       return true;
     while (!Worklist.empty()) {
       const SDNode *M = Worklist.pop_back_val();
       bool Found = false;
       for (const SDValue &OpV : M->op_values()) {
         SDNode *Op = OpV.getNode();
         if (Visited.insert(Op).second)
           Worklist.push_back(Op);
         if (Op == N)
           Found = true;
       }
       if (Found)
         return true;
+      if (MaxSteps != 0 && Visited.size() >= MaxSteps)
+        return false;
     }
     return false;
   }
 
   /// Return true if all the users of N are contained in Nodes.
   /// NOTE: Requires at least one match, but doesn't require them all.
   static bool areOnlyUsersOf(ArrayRef<const SDNode *> Nodes, const SDNode *N);
 

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I)
         if (StoreSDNode *OtherST = dyn_cast<StoreSDNode>(*I)) {
           BaseIndexOffset Ptr;
           int64_t PtrDiff;
           if (CandidateMatch(OtherST, Ptr, PtrDiff))
             StoreNodes.push_back(MemOpLink(OtherST, PtrDiff));
         }
 }
 
-// We need to check that merging these stores does not cause a loop
-// in the DAG. Any store candidate may depend on another candidate
+// We need to check that merging these stores does not cause a loop in
+// the DAG. Any store candidate may depend on another candidate
 // indirectly through its operand (we already consider dependencies
 // through the chain). Check in parallel by searching up from
 // non-chain operands of candidates.
+
 bool DAGCombiner::checkMergeStoreCandidatesForDependencies(
     SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumStores) {
+
+  // FIXME: We should be able to truncate a full search of
+  // predecessors by doing a BFS and keeping tabs the originating
+  // stores from which worklist nodes come from in a similar way to
+  // TokenFactor simplfication.
+
   SmallPtrSet<const SDNode *, 16> Visited;
   SmallVector<const SDNode *, 8> Worklist;
-  // search ops of store candidates
+  unsigned int Max = 8192;
+  // Search Ops of store candidates.
   for (unsigned i = 0; i < NumStores; ++i) {
     SDNode *n = StoreNodes[i].MemNode;
     // Potential loops may happen only through non-chain operands
     for (unsigned j = 1; j < n->getNumOperands(); ++j)
       Worklist.push_back(n->getOperand(j).getNode());
   }
-  // search through DAG. We can stop early if we find a storenode
+  // Search through DAG. We can stop early if we find a store node.
   for (unsigned i = 0; i < NumStores; ++i) {
-    if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist))
+    if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist,
+                                     Max))
+      return false;
+    // Check if we ended early, failing conservatively if so.
+    if (Visited.size() >= Max)
       return false;
   }
   return true;
 }
 
 bool DAGCombiner::MergeConsecutiveStores(StoreSDNode *St) {
   if (OptLevel == CodeGenOpt::None)
     return false;