[DAGCombiner] Limit graph traversal to cap compile times

[pranavk]

Summary

hasPredecessorHelper method, that is used by DAGCombiner to combine to pre-indexed and post-indexed load/stores, is a major source of slowdown while compiling a large function with MSan enabled on Arm. This patch caps the DFS-graph traversal for this method to 8192 which cuts compile time by 50% (4m -> 2m compile time) at the cost of less overall nodes combined.

Here's the summary of pre-index DAG nodes created and time it took to compile the pathological case with different MaxDepth limit:

1. With MaxDepth = 0 (unlimited): 1800, took 4m
2. With MaxDepth = 32k, 560, took 2m31s
3. With MaxDepth = 8k, 139, took 2m.

[MaskRay]

(We use a MaxDepth pattern in many places, e.g., llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp, several *ISelLowering.cpp files, and SelectionDAG::copyExtraInfo.)

It seems that most hasPredecessorHelper callers don't set Max, and only a few set Max.

I am curious whether you can come up a pathological case to demonstrate the issue, even if crafting a test is not so practical. Without more information future refactors cannot know how they can be certain this problem has been fixed in the root cause (if there is a way...).

[rnk]

I think Alina had some context with previous DAG combine compile time problems.

[MaskRay]

I think this is reasonable. We also use a threshold argument in some other places where hasPredecessorHelper is used, e.g. SelectionDAGISel.cpp 8192.

[dblaikie]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

17669

17888

[pranavk]

clang-format and reviewer suggestions

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

17669

Thanks. I made it a constexpr. I think I made it 'const unsigned' after looking at similar code in this file or directory.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) {
   SmallPtrSet<const SDNode *, 32> Visited;
   SmallVector<const SDNode *, 16> Worklist;
   Worklist.push_back(N);
 
   // If the offset is a constant, there may be other adds of constants that
   // can be folded with this one. We should do this to avoid having to keep
   // a copy of the original base pointer.
   SmallVector<SDNode *, 16> OtherUses;
+  constexpr unsigned int MaxSteps = 8192;
   if (isa<ConstantSDNode>(Offset))
     for (SDNode::use_iterator UI = BasePtr->use_begin(),
                               UE = BasePtr->use_end();
          UI != UE; ++UI) {
       SDUse &Use = UI.getUse();
       // Skip the use that is Ptr and uses of other results from BasePtr's
       // node (important for nodes that return multiple results).
       if (Use.getUser() == Ptr.getNode() || Use != BasePtr)
         continue;
 
-      if (SDNode::hasPredecessorHelper(Use.getUser(), Visited, Worklist))
+      if (SDNode::hasPredecessorHelper(Use.getUser(), Visited, Worklist,
+                                       MaxSteps))
         continue;
 
       if (Use.getUser()->getOpcode() != ISD::ADD &&
           Use.getUser()->getOpcode() != ISD::SUB) {
         OtherUses.clear();
         break;
       }
 
if (Swapped)
     std::swap(BasePtr, Offset);
 
   // Now check for #3 and #4.
   bool RealUse = false;
 
   for (SDNode *Use : Ptr->uses()) {
     if (Use == N)
       continue;
-    if (SDNode::hasPredecessorHelper(Use, Visited, Worklist))
+    if (SDNode::hasPredecessorHelper(Use, Visited, Worklist, MaxSteps))
       return false;
 
     // If Ptr may be folded in addressing mode of other use, then it's
     // not profitable to do this transformation.
     if (!canFoldInAddressingMode(Ptr.getNode(), Use, DAG, TLI))
       RealUse = true;
   }
 
static SDNode *getPostIndexedLoadStoreOp(SDNode *N, bool &IsLoad,
   for (SDNode *Op : Ptr->uses()) {
     // Check for #1.
     if (!shouldCombineToPostInc(N, Ptr, Op, BasePtr, Offset, AM, DAG, TLI))
       continue;
 
     // Check for #2.
     SmallPtrSet<const SDNode *, 32> Visited;
     SmallVector<const SDNode *, 8> Worklist;
+    constexpr unsigned int MaxSteps = 8192;
     // Ptr is predecessor to both N and Op.
     Visited.insert(Ptr.getNode());
     Worklist.push_back(N);
     Worklist.push_back(Op);
-    if (!SDNode::hasPredecessorHelper(N, Visited, Worklist) &&
-        !SDNode::hasPredecessorHelper(Op, Visited, Worklist))
+    if (!SDNode::hasPredecessorHelper(N, Visited, Worklist, MaxSteps) &&
+        !SDNode::hasPredecessorHelper(Op, Visited, Worklist, MaxSteps))
       return Op;
   }
   return nullptr;
 }
 
 /// Try to combine a load/store with a add/sub of the base pointer node into a
 /// post-indexed load/store. The transformation folded the add/subtract into the
 /// new indexed load/store effectively and all of its uses are redirected to the