[DAGCombiner] Limit number of nodes explored as store candidates.

[fhahn]

Summary

To find the candidates to merge stores we iterate over all nodes in a chain
for each store, which leads to quadratic compile times for large basic blocks
with a large number of stores.

[niravd]

This is okay modulo nits, but let's land the TokenFactor operand size limiting first as it also implicitly bounds things.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14845 ↗

(On Diff #198009)

nit: use prefix increment to be consistent with other uses.

14857 ↗

(On Diff #198009)

nit: same

[fhahn]

Updated increments.

In D61511#1491339, @niravd wrote:

This is okay modulo nits, but let's land the TokenFactor operand size limiting first as it also implicitly bounds things.

Thanks, the token factor size limiting patch is at D61397, please let me know what you think and
if there is a better place to do the limiting somewhere else.

[fhahn]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14845 ↗

(On Diff #198009)

Done,thanks!

[niravd]

LGTM.

[fhahn]

thanks!

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

void DAGCombiner::getStoreMergeCandidates(
   // |       |
   // Store1   Store2
   //
   // FIXME: We should be able to climb and
   // descend TokenFactors to find candidates as well.
 
   RootNode = St->getChain().getNode();
 
+  unsigned NumNodesExplored = 0;
   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 && NumNodesExplored < 1024; ++I, ++NumNodesExplored)
       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)
+    for (auto I = RootNode->use_begin(), E = RootNode->use_end();
+         I != E && NumNodesExplored < 1024; ++I, ++NumNodesExplored)
       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));
         }
 }