[DAGCombiner] Avoid creating large tokenfactors in visitTokenFactor

[fhahn]

Summary

When simplifying TokenFactors, we potentially iterate over all
operands of a large number of TokenFactors. This causes quadratic
compile times in some cases and the large token factors cause additional
scalability problems elsewhere.

This patch adds some limits to the number of nodes explored for the
cases mentioned above.

[fhahn]

Relax limits to 1000 nodes to explore. Further experimenting showed that those
bigger limits are still sufficient to ensure limiting quadratic compile time.

[niravd]

Notes inline, but I think the majority of the compile time improvements come from keepign TokenFactor operand counts bounded. This should be changed to do reflect that.

That said, I think rewriting the "CanMergeStoresTo" to "GetMaximumMergedStoreSize" and using that as a first-order filter on nodes to consider like was discussed in D60133 should be done before any heuristic restrictions (including TokenFactor operand count limits) should be considered as it causes no code generation degradation, only compile time improvements.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1767

I this that this is too restrictive. This check effectively curtails the second and third passes (The first being the quick two operand check).

The third pass is a fairly expensive chain predecessor search to see if there are redundancies in the operands (if A and its chain predecessor B are both in the list, you can drop B) but already has a cutoff of 1024 steps.

The second pass is a linear pass to weed out trivial redundancies in the list. Due to the way that chain replacements happen, it's extremely common for TokenFactors to have redundant operands in them and I worry that curtialing this will have nontrivial degradation for relatively little compile time improvement.

If this is making a notable difference, I suspect we should change the second pass to not inline a TokenFactor if the number of operands in the new TokenFactor would be too large.

14852–14854

nit: fold this into the loop test and increment (MaxNumberOfNodesToCheck> 0 , --MaxNumberOfNodesToCheck)

nit: Since we merge mainly powers of two, the limit should one or slightly higher (1025?)

19999

It seems like the underlying problem you're trying to avoid is having a TokenFactor with too many operands. That's definitely an issue. We do try to avoid it in the SelectionDAGBuilder, but not consisently elsewhere.

This is indirectly doing this by forcing us to only consider a smaller set of chains. Given that this catches mostly long chains of independant chains with mostly the same real dependences, it would probably be much better to do the calculation here as is, but instead of making larger tokenfactors, split them into a hierarchy of some sort. Maybe this should be folded into the TokenFactor case of getNode smart constructor.

[fhahn]

In D61397#1487955, @niravd wrote:

Notes inline, but I think the majority of the compile time improvements come from keepign TokenFactor operand counts bounded. This should be changed to do reflect that.

Thanks for taking a look. Yep I think that might be the case. I'll verify that tomorrow.

That said, I think rewriting the "CanMergeStoresTo" to "GetMaximumMergedStoreSize" and using that as a first-order filter on nodes to consider like was discussed in D60133 should be done before any heuristic restrictions (including TokenFactor operand count limits) should be considered as it causes no code generation degradation, only compile time improvements.

I will get back to D60133 soon as well! Unfortunately it did not yield any improvements for the case I am looking at.

[fhahn]

Limit this patch to visitTokenFactor, limiting the number of operands to inline to 2048 nodes.

[fhahn]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1767

Thanks! I've limited the number of Ops to collect for inlining in the second pass. Is that along the lines you were thinking? I will also check if it helps to skip tokefactors that will get us to exceed a limit here.

[fhahn]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14852–14854

Thanks, moved to a separate patch: D61511

[niravd]

LGTM.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (unsigned NumOps = N->getNumOperands()) {
     for (unsigned i = 1; i < NumOps-1; ++i)
       if (N->getOperand(i).getValueType() == MVT::Other)
         return N->getOperand(i);
   }
   return SDValue();
 }
 
 SDValue DAGCombiner::visitTokenFactor(SDNode *N) {
+  // Limit the number of nodes to explore, to avoid quadratic compile times.
+  // The limit helps to limit compile time for basic blocks with a large number
+  // of stores.
+  if (N->getNumOperands() > 1000)
+    return SDValue();
+
   // If N has two operands, where one has an input chain equal to the other,
   // the 'other' chain is redundant.
   if (N->getNumOperands() == 2) {
     if (getInputChainForNode(N->getOperand(0).getNode()) == N->getOperand(1))
       return N->getOperand(0);
     if (getInputChainForNode(N->getOperand(1).getNode()) == N->getOperand(0))
       return N->getOperand(1);
   }
void DAGCombiner::getStoreMergeCandidates(
   // |       |
   // Store1   Store2
   //
   // FIXME: We should be able to climb and
   // descend TokenFactors to find candidates as well.
 
   RootNode = St->getChain().getNode();
 
+  // Limit the number of nodes to explore, to avoid quadratic compile times.
+  // The limit helps to limit compile time for basic blocks with a large number
+  // of stores.
+  unsigned MaxNumberOfNodesToCheck = 200;
   if (LoadSDNode *Ldn = dyn_cast<LoadSDNode>(RootNode)) {
     RootNode = Ldn->getChain().getNode();
-    for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I)
+    for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I) {
+      if (!MaxNumberOfNodesToCheck--)
+        break;
       if (I.getOperandNo() == 0 && isa<LoadSDNode>(*I)) // walk down chain
         for (auto I2 = (*I)->use_begin(), E2 = (*I)->use_end(); I2 != E2; ++I2)
           if (I2.getOperandNo() == 0)
             if (StoreSDNode *OtherST = dyn_cast<StoreSDNode>(*I2)) {
               BaseIndexOffset Ptr;
               int64_t PtrDiff;
               if (CandidateMatch(OtherST, Ptr, PtrDiff))
                 StoreNodes.push_back(MemOpLink(OtherST, PtrDiff));
             }
-  } else
-    for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I)
-      if (I.getOperandNo() == 0)
+    }
+  } else {
+    for (auto I = RootNode->use_begin(), E = RootNode->use_end(); I != E; ++I) {
+      if (!MaxNumberOfNodesToCheck--)
+        break;
+      if (I.getOperandNo() == 0) {
         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
 // 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,
bool DAGCombiner::parallelizeChainedStores(StoreSDNode *St) {
 
   // Do not handle stores to undef base pointers.
   if (BasePtr.getBase().isUndef())
     return false;
 
   // Add ST's interval.
   Intervals.insert(0, (St->getMemoryVT().getSizeInBits() + 7) / 8, Unit);
 
+  // Limit the number of chains to explore, to avoid quadratic compile times.
+  // The limit helps to limit compile time for basic blocks with a large number
+  // of stores.
+  unsigned MaxNumberOfChains = 200;
   while (StoreSDNode *Chain = dyn_cast<StoreSDNode>(STChain->getChain())) {
+    if (!MaxNumberOfChains--)
+      break;
     // If the chain has more than one use, then we can't reorder the mem ops.
     if (!SDValue(Chain, 0)->hasOneUse())
       break;
     if (Chain->isVolatile() || Chain->isIndexed())
       break;
 
     // Find the base pointer and offset for this memory node.
     const BaseIndexOffset Ptr = BaseIndexOffset::match(Chain, DAG);