[DAGCombine] Limit the number of times for a store being considered for merging

[wmi]

Summary

Recently we run into a case with compile time problem (27 mins in O3 but a few seconds in O0). In that case, we have a huge block containing many stores. Each time a store is visited, dagcombiner will find a candidate set all chained by the same root node for the store, then try to merge the nodes in the candidate set into a wider store. This is a quadratic algorithm, because for the same candidate set, everytime a store inside of the set is visited, the same set will be considered for merging. 

In this patch, we add a map to record how many times the pair of root node and the store node is seen before a store node is added into candidate set. If the count is above a threshold (set to 10 by default now), the store node won't be added to candidate set again. With the patch, the compile time drops to 20 seconds.

I verify that the patch won't miss store merging opportunities in most cases in the way that by building a large internal server application and bootstrapping clang w/wo the patch, I find no difference for the binaries.

[niravd]

This has come up a few times before (https://reviews.llvm.org/D60133 is the most recent instance). So far it's either been deemed not important enough or there was a way to limit the candidate search to limit the search to the correct size (e.g. checking the in context max valid store size and making sure there was a valid non-trivial store merge).

It would be good to understand why we're finding candidates that cannot be merged and see if the search can be tightened. I vaguely recall that the underlying cause in D60133 could be solved by replacing the canMergeStoresTo's method with something expressing maximum mergable size with this store in the current context and that that would also remove a large number of these fruitless merge searches. I suspect this may work for your case as well.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15461 ↗

(On Diff #211379)

nit: Hoist this and the equal check in the else clause out of the if.

[wmi]

Thanks for pointing me to D60133.

I check and the reason the candidates cannot be merged isn't because of the legal size. It is that checkMergeStoreCandidatesForDependencies always returns false so https://reviews.llvm.org/D60133 doesn't help.

For the case addressed in https://reviews.llvm.org/D60133, limiting the search to the correct size is definitely a good way to solve it. But I think it can cause compile time problem likely also because the same store and root pair appearing repeatedly, so the patch here may also help for the case in D60133.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15461 ↗

(On Diff #211379)

The RootNode is updated inside of then branch so it wasn't hoisted above.

[niravd]

I check and the reason the candidates cannot be merged isn't because of the legal size. It is that checkMergeStoreCandidatesForDependencies always returns false so https://reviews.llvm.org/D60133 doesn't help.

Ah! Interesting. I've only seen that dependence triggered from inlined memcpy.

What's the shape of the DAG here? There must be some non-standard data dependence between stores, which is not being checked. Maybe we can change the candidate search to avoid such candidates.

[fhahn]

Recently we run into a case with compile time problem (27 mins in O3 but a few seconds in O0). In that case, we have a huge block containing many stores. Each time a store is visited, dagcombiner will find a candidate set all chained by the same root node for the store, then try to merge the nodes in the candidate set into a wider store. This is a quadratic algorithm, because for the same candidate set, everytime a store inside of the set is visited, the same set will be considered for merging.

Could you share the test case? I looked into a similar issue and came up with some sort of caching for the lookup. I never shared the patch, because we addressed the issue with a limit. But it might be helpful for your case.

[wmi]

In D65174#1604955, @niravd wrote:

I check and the reason the candidates cannot be merged isn't because of the legal size. It is that checkMergeStoreCandidatesForDependencies always returns false so https://reviews.llvm.org/D60133 doesn't help.

Ah! Interesting. I've only seen that dependence triggered from inlined memcpy.

What's the shape of the DAG here? There must be some non-standard data dependence between stores, which is not being checked. Maybe we can change the candidate search to avoid such candidates.

The DAG is huge and I havn't seen any speciality. About the dependence between stores, I look into it and checkMergeStoreCandidatesForDependencies always returns false because llvm::SDNode::hasPredecessorHelper visits too many nodes in the worklist which exceeds the MaxSteps and the function bails out. That is also the reason the compile time increases so much.

[wmi]

In D65174#1604984, @fhahn wrote:

Recently we run into a case with compile time problem (27 mins in O3 but a few seconds in O0). In that case, we have a huge block containing many stores. Each time a store is visited, dagcombiner will find a candidate set all chained by the same root node for the store, then try to merge the nodes in the candidate set into a wider store. This is a quadratic algorithm, because for the same candidate set, everytime a store inside of the set is visited, the same set will be considered for merging.

Could you share the test case? I looked into a similar issue and came up with some sort of caching for the lookup. I never shared the patch, because we addressed the issue with a limit. But it might be helpful for your case.

Good to know that. It is an internal source and I don't have tool to do obfuscation. Could you share your patch? I can try it out and see if it helps.

[niravd]

Ah. That's a tricky one. It sounds like this isn't a case of the candidate stores not being mergable, but rather us giving up before we completely verify that.

I don't suppose the values in the indirect value operands to the candidate stores have a relatively short dependence on a node not too far from the RootNode. Right now, we only prune at the root node (and components through the TokenFactors). but we could also just mark further predecessors of the RootNode as not needing to be searched.

[wmi]

In D65174#1605103, @niravd wrote:

Ah. That's a tricky one. It sounds like this isn't a case of the candidate stores not being mergable, but rather us giving up before we completely verify that.

I don't suppose the values in the indirect value operands to the candidate stores have a relatively short dependence on a node not too far from the RootNode. Right now, we only prune at the root node (and components through the TokenFactors). but we could also just mark further predecessors of the RootNode as not needing to be searched.

It may not be easy for us to prune the searching space without missing some merging opportunity. I feel it is easier to achieve that goal by controlling how many times a {RootNode, StoreNode} pair appear in candidate set repeatedly. With the patch, no bit change in the binaries were found for clang and some large application. So the current patch is a safe change.

[niravd]

It may not be easy for us to prune the searching space without missing some merging opportunity. I feel it is easier to achieve that goal by controlling how many times a {RootNode, StoreNode} pair appear in candidate set repeatedly. With the patch, no bit change in the binaries were found for clang and some large application. So the current patch is a safe change.

True. But my concern is that as we prune the search space, we will introduce burrs in the which will be extremely hard to find and notice. I agree that its' not worth it to solve it the ideal way, but if a quick to write but safe pruning of the search space happens to work we should go with that. If not, it's likely it'll be too hard to resolve better than a heuristics. The scheme here is fine modulo the following concerns:

1. If it's really an issue with the candidate dependence check, we should move the RootStoreCountMap update be modified in the dependency search, not the candidate check. This shouldn't dramatically change the run time

2. The RootNode is effectively a function of the candidate store. We really should only have a single RootNode so it'd be better as a map from SDNode* to (SDNode*, int).

3. The RootStoreCountMap ends up with stale information as we replace nodes, which may cause unexpected failures. Can you modify the node listeners to trim the map.

[wmi]

In D65174#1606368, @niravd wrote:

It may not be easy for us to prune the searching space without missing some merging opportunity. I feel it is easier to achieve that goal by controlling how many times a {RootNode, StoreNode} pair appear in candidate set repeatedly. With the patch, no bit change in the binaries were found for clang and some large application. So the current patch is a safe change.

True. But my concern is that as we prune the search space, we will introduce burrs in the which will be extremely hard to find and notice. I agree that its' not worth it to solve it the ideal way, but if a quick to write but safe pruning of the search space happens to work we should go with that. If not, it's likely it'll be too hard to resolve better than a heuristics. The scheme here is fine modulo the following concerns:

1. If it's really an issue with the candidate dependence check, we should move the RootStoreCountMap update be modified in the dependency search, not the candidate check. This shouldn't dramatically change the run time.

2. The RootNode is effectively a function of the candidate store. We really should only have a single RootNode so it'd be better as a map from SDNode* to (SDNode*, int).

I havn't got the idea. Could you please elaborate what is the "SDNode *" in the key and what is the "SDNode *" in the value? And how it helps the early return in the dependence check?

3. The RootStoreCountMap ends up with stale information as we replace nodes, which may cause unexpected failures. Can you modify the node listeners to trim the map.

Good point. I will update it.

[niravd]

I havn't got the idea. Could you please elaborate what is the "SDNode *" in the key and what is the "SDNode *" in the value? And how it helps the early return in the dependence check?

Not sure if you mean the first or second point, but here's both:

1. The issue with having the values incremented in the candidate search is that we'll be much more aggressive about marking things non-mergable. There are a number of cases where we need to visit each store in the merge set once before it can be merged as part dag combining the last store. Also, by deferring the increment to when checkMergeStoreCandidatesForDependencies fails, store merge slowdowns unrelated to this will continue to appear as compile time issues not performance degradations which means are much more likely to consider them when they come up.

2. Write the map as Candidate Store to (RootNode, count) where the root node acts as "a checksum". So the dependence check is lookup and match checksum and the update is lookup, increment on checksum match and reset to 1 on mismatch.

3. The RootStoreCountMap ends up with stale information as we replace nodes, which may cause unexpected failures. Can you modify the node listeners to trim the map.

Good point. I will update it.

[wmi]

Thanks Nirav. I update the patch. Please take a look.

[wmi]

Address Nirav's comment.

[niravd]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

118 ↗

(On Diff #212498)

the command flag name is a bit unclear and should have the "combiner-" prefix. Maybe "combiner-store-merge-dependence-limit"?

15481 ↗

(On Diff #212498)

No sense in considering stores that won't merge. Filter candidates on StoreRootCountMap before we add to StoreNodes here.

15491 ↗

(On Diff #212498)

If we're going to fail from dependences for an N store merge, we encounter it for a merge starting from each of the N candidates. We should
mark each of the "NumStores" candidate stores we have when we fail. Also, you shouldn't bother updating unless the dependence check failed from timeout.

[wmi]

Thanks for the suggestions. I will update patch immediately. Please see if it matches what is in your mind.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

118 ↗

(On Diff #212498)

Done.

15481 ↗

(On Diff #212498)

Done.

15491 ↗

(On Diff #212498)

Good point. Done.

[wmi]

Address Nirav's comment.

[niravd]

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

869 ↗

(On Diff #212623)

Visited.size() and maxsteps are in scope for any call of the help. Just do the comparision at the call point instead of adding an argument.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15446 ↗

(On Diff #212623)

Extraneous return false here.

15560 ↗

(On Diff #212623)

Shouldn't you be checking that RootNode matches before you increment the count?

[wmi]

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

869 ↗

(On Diff #212623)

Ah, I didn't notice that. Will change.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15446 ↗

(On Diff #212623)

Thanks for spotting it. I add it for experiment but forget to remove it when generating the patch.

15560 ↗

(On Diff #212623)

Yes, I should. Done.

[wmi]

Address Nirav's comment.

[niravd]

LGTM. Thanks!

[wmi]

Nirav, thanks for all the suggestions and quick responses!

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

static cl::opt<bool>
     EnableStoreMerging("combiner-store-merging", cl::Hidden, cl::init(true),
                        cl::desc("DAG combiner enable merging multiple stores "
                                 "into a wider store"));
 
 static cl::opt<unsigned> TokenFactorInlineLimit(
     "combiner-tokenfactor-inline-limit", cl::Hidden, cl::init(2048),
     cl::desc("Limit the number of operands to inline for Token Factors"));
 
+static cl::opt<unsigned> StoreMergeDependenceLimit(
+    "combiner-store-merge-dependence-limit", cl::Hidden, cl::init(10),
+    cl::desc("Limit the number of times for the same StoreNode and RootNode "
+             "to bail out in store merging dependence check"));
+
 namespace {
 
   class DAGCombiner {
     SelectionDAG &DAG;
     const TargetLowering &TLI;
     CombineLevel Level;
     CodeGenOpt::Level OptLevel;
     bool LegalOperations = false;
class DAGCombiner {
     SmallSetVector<SDNode *, 32> PruningList;
 
     /// Set of nodes which have been combined (at least once).
     ///
     /// This is used to allow us to reliably add any operands of a DAG node
     /// which have not yet been combined to the worklist.
     SmallPtrSet<SDNode *, 32> CombinedNodes;
 
+    /// Map from candidate StoreNode to the pair of RootNode and count.
+    /// The count is used to track how many times we have seen the StoreNode
+    /// with the same RootNode bail out in dependence check. If we have seen
+    /// the bail out for the same pair many times over a limit, we won't
+    /// consider the StoreNode with the same RootNode as store merging
+    /// candidate again.
+    DenseMap<SDNode *, std::pair<SDNode *, unsigned>> StoreRootCountMap;
+
     // AA - Used for DAG load/store alias analysis.
     AliasAnalysis *AA;
 
     /// When an instruction is simplified, add all users of the instruction to
     /// the work lists because they might get more simplified now.
     void AddUsersToWorklist(SDNode *N) {
       for (SDNode *Node : N->uses())
         AddToWorklist(Node);
void AddToWorklist(SDNode *N) {
       if (WorklistMap.insert(std::make_pair(N, Worklist.size())).second)
         Worklist.push_back(N);
     }
 
     /// Remove all instances of N from the worklist.
     void removeFromWorklist(SDNode *N) {
       CombinedNodes.erase(N);
       PruningList.remove(N);
+      StoreRootCountMap.erase(N);
 
       auto It = WorklistMap.find(N);
       if (It == WorklistMap.end())
         return; // Not in the worklist.
 
       // Null out the entry rather than erasing it to avoid a linear operation.
       Worklist[It->second] = nullptr;
       WorklistMap.erase(It);
if (IsExtractVecSrc) {
       if (OtherBC.getOpcode() != ISD::EXTRACT_VECTOR_ELT &&
           OtherBC.getOpcode() != ISD::EXTRACT_SUBVECTOR)
         return false;
     }
     Ptr = BaseIndexOffset::match(Other, DAG);
     return (BasePtr.equalBaseIndex(Ptr, DAG, Offset));
   };
 
+  // Check if the pair of StoreNode and the RootNode already bail out many
+  // times which is over the limit in dependence check.
+  auto OverLimitInDependenceCheck = [&](SDNode *StoreNode,
+                                        SDNode *RootNode) -> bool {
+    auto RootCount = StoreRootCountMap.find(StoreNode);
+    if (RootCount != StoreRootCountMap.end() &&
+        RootCount->second.first == RootNode &&
+        RootCount->second.second > StoreMergeDependenceLimit)
+      return true;
+    return false;
+  };
+
   // We looking for a root node which is an ancestor to all mergable
   // stores. We search up through a load, to our root and then down
   // through all children. For instance we will find Store{1,2,3} if
   // St is Store1, Store2. or Store3 where the root is not a load
   // which always true for nonvolatile ops. TODO: Expand
   // the search to find all valid candidates through multiple layers of loads.
   //
   // Root
if (LoadSDNode *Ldn = dyn_cast<LoadSDNode>(RootNode)) {
     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))
+              if (CandidateMatch(OtherST, Ptr, PtrDiff) &&
+                  !OverLimitInDependenceCheck(OtherST, RootNode))
                 StoreNodes.push_back(MemOpLink(OtherST, PtrDiff));
             }
   } else
     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))
+          if (CandidateMatch(OtherST, Ptr, PtrDiff) &&
+              !OverLimitInDependenceCheck(OtherST, RootNode))
             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
for (unsigned i = 0; i < NumStores; ++i) {
     //               non-indexed stores). Not constant on all targets (e.g. ARM)
     //               and so can participate in a cycle.
     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 store node.
   for (unsigned i = 0; i < NumStores; ++i)
     if (SDNode::hasPredecessorHelper(StoreNodes[i].MemNode, Visited, Worklist,
-                                     Max))
+                                     Max)) {
+      // If the searching bail out, record the StoreNode and RootNode in the
+      // StoreRootCountMap. If we have seen the pair many times over a limit,
+      // we won't add the StoreNode into StoreNodes set again.
+      if (Visited.size() >= Max) {
+        auto &RootCount = StoreRootCountMap[StoreNodes[i].MemNode];
+        if (RootCount.first == RootNode)
+          RootCount.second++;
+        else
+          RootCount = {RootNode, 1};
+      }
       return false;
+    }
   return true;
 }
 
 bool DAGCombiner::MergeConsecutiveStores(StoreSDNode *St) {
   if (OptLevel == CodeGenOpt::None || !EnableStoreMerging)
     return false;
 
   EVT MemVT = St->getMemoryVT();