[DAGCombiner] Limit the number of chains in findBetterChains().

[courbet]

Summary

Enabling -combiner-global-alias-analysis does find better chains and
therefore can result in prohibitively large compile times for very large
blocks.

This patch protects against large blocks without hurting the expected behaviour
for reasonable sizes. The typical use case for merging is when the stores to be
merged are reasonably local (e.g. when merging 4 stores, these 4 stores can be
found within a window of not much more than 4 unrelated store instructions).

[courbet]

revert formatting changes

[niravd]

Oh good catch. This is O(N^3) for long chains because we try every prefix of the chain, and because the chain is so long our chain improvements gives up and noops, so we just redo the same computation over and over. Cutting the length to any reasonable size makes it O(N^2). I suspect your observed merge size requirement is to deal with our incomplete handling of chain SubDAG in store merge (just a children of a single TF potentially skipping some loads), because it shouldn't matter otherwise (See (1)).

Although, maybe what we should actually do is just run up the chain and mark make sure each store is to a disjoint part of memory (which should be just a range check as they all had related pointers) and then just directly rewrite them into as fully parallel structure chained to a TokenFactor. That should be O(N) with a much smaller constant than this.

(1) I wrote a cleanup patch D31068 some time ago that never got around to chasing down the reviewers to care. It lets us merge stores from a chain of stores where we gave up on better aliasing. That should remove any burrs from giving up merges too soon. I've added you as a reviewer.

include/llvm/CodeGen/TargetLowering.h

2598

I wrote some a cleanup patch some time ago that never got around to chasing down the reviewers to care. It incrementally allows us to deal with chains of stores in which should remove any burrs from giving up merges too soon, so we shouldn't need to have a target-dependenct depth check.

[niravd]

This comment was removed by niravd.

[courbet]

In D53289#1265550, @niravd wrote:

Oh good catch. This is O(N^3) for long chains because we try every prefix of the chain, and because the chain is so long our chain improvements gives up and noops, so we just redo the same computation over and over. Cutting the length to any reasonable size makes it O(N^2). I suspect your observed merge size requirement is to deal with our incomplete handling of chain SubDAG in store merge (just a children of a single TF potentially skipping some loads), because it shouldn't matter otherwise (See (1)).

I'm not sure I understand what (1) would change to the situation ?

Although, maybe what we should actually do is just run up the chain and mark make sure each store is to a disjoint part of memory (which should be just a range check as they all had related pointers) and then just directly rewrite them into as fully parallel structure chained to a TokenFactor. That should be O(N) with a much smaller constant than this.

Note that this patch fixes a pathological case which is quite theoretical; the limit is never hit on any of the test-suite basic blocks.
Actually with this change it takes a basic block of more than ten thousand stores to reach the current compile time with hundreds of blocks, even with -combiner-global-alias-analysis.

(1) I wrote a cleanup patch D31068 some time ago that never got around to chasing down the reviewers to care. It lets us merge stores from a chain of stores where we gave up on better aliasing. That should remove any burrs from giving up merges too soon. I've added you as a reviewer.

[courbet]

For reference: compile times for insane block sizes with and without this patch. Y is seconds, X is #stores/3.

[niravd]

We've superceded this patch.

[courbet]

Dropping this.

include/llvm/CodeGen/TargetLowering.h

bool hasTargetDAGCombine(ISD::NodeType NT) const {
     assert(unsigned(NT >> 3) < array_lengthof(TargetDAGCombineArray));
     return TargetDAGCombineArray[NT >> 3] & (1 << (NT&7));
   }
 
   unsigned getGatherAllAliasesMaxDepth() const {
     return GatherAllAliasesMaxDepth;
   }
 
+  unsigned getFindBetterChainsMaxChains() const {
+    return FindBetterChainsMaxChains;
+  }
+
   /// Returns the size of the platform's va_list object.
   virtual unsigned getVaListSizeInBits(const DataLayout &DL) const {
     return getPointerTy(DL).getSizeInBits();
   }
 
   /// Get maximum # of store operations permitted for llvm.memset
   ///
   /// This function returns the maximum number of store operations permitted
protected:
   virtual bool isExtFreeImpl(const Instruction *I) const { return false; }
 
   /// Depth that GatherAllAliases should should continue looking for chain
   /// dependencies when trying to find a more preferable chain. As an
   /// approximation, this should be more than the number of consecutive stores
   /// expected to be merged.
   unsigned GatherAllAliasesMaxDepth;
 
+  // Number of chains that are considered when looking back for mergeable stores
+  // in DAGCombiner::findBetterNeighborChains. This should be larger than the
+  // maximum number of stores to be merged for a target (e.g. setting this to
+  // 8 will allow merging 8 consecutive i8 stores to one i64). Increasing this
+  // value further will allow discovering and merging potentially
+  // non-consecutive stores to be merged.
+  unsigned FindBetterChainsMaxChains;
+
   /// Specify maximum number of store instructions per memset call.
   ///
   /// When lowering \@llvm.memset this field specifies the maximum number of
   /// store operations that may be substituted for the call to memset. Targets
   /// must set this value based on the cost threshold for that target. Targets
   /// should assume that the memset will be done using as many of the largest
   /// store operations first, followed by smaller ones, if necessary, per
   /// alignment restrictions. For example, storing 9 bytes on a 32-bit machine

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

auto ScaleShuffleMask = [](ArrayRef<int> Mask, int Scale) {
         return SmallVector<int, 8>(Mask.begin(), Mask.end());
 
       SmallVector<int, 8> NewMask;
       for (int M : Mask)
         for (int s = 0; s != Scale; ++s)
           NewMask.push_back(M < 0 ? -1 : Scale * M + s);
       return NewMask;
     };
-    
     SDValue BC0 = peekThroughOneUseBitcasts(N0);
     if (BC0.getOpcode() == ISD::VECTOR_SHUFFLE && BC0.hasOneUse()) {
       EVT SVT = VT.getScalarType();
       EVT InnerVT = BC0->getValueType(0);
       EVT InnerSVT = InnerVT.getScalarType();
 
       // Determine which shuffle works with the smaller scalar type.
       EVT ScaleVT = SVT.bitsLT(InnerSVT) ? VT : InnerVT;
bool DAGCombiner::findBetterNeighborChains(StoreSDNode *St) {
   if (BasePtr.getBase().isUndef())
     return false;
 
   SmallVector<StoreSDNode *, 8> ChainedStores;
   ChainedStores.push_back(St);
 
   // Walk up the chain and look for nodes with offsets from the same
   // base pointer. Stop when reaching an instruction with a different kind
-  // or instruction which has a different base pointer.
+  // or instruction or a different base pointer.
   StoreSDNode *Index = St;
+  const unsigned MaxChains = TLI.getFindBetterChainsMaxChains();
   while (Index) {
     // If the chain has more than one use, then we can't reorder the mem ops.
     if (Index != St && !SDValue(Index, 0)->hasOneUse())
       break;
 
     if (Index->isVolatile() || Index->isIndexed())
       break;
 
while (Index) {
     while (true) {
       if (StoreSDNode *STn = dyn_cast<StoreSDNode>(NextInChain)) {
         // We found a store node. Use it for the next iteration.
         if (STn->isVolatile() || STn->isIndexed()) {
           Index = nullptr;
           break;
         }
         ChainedStores.push_back(STn);
-        Index = STn;
+        // Stop if we have too many chains.
+        Index = ChainedStores.size() >= MaxChains ? nullptr : STn;
         break;
       } else if (LoadSDNode *Ldn = dyn_cast<LoadSDNode>(NextInChain)) {
         NextInChain = Ldn->getChain().getNode();
         continue;
       } else {
         Index = nullptr;
         break;
       }
     }// end while
   }
 
   // At this point, ChainedStores lists all of the Store nodes
   // reachable by iterating up through chain nodes matching the above
   // conditions.  For each such store identified, try to find an
   // earlier chain to attach the store to which won't violate the
   // required ordering.
   bool MadeChangeToSt = false;
   SmallVector<std::pair<StoreSDNode *, SDValue>, 8> BetterChains;
-
   for (StoreSDNode *ChainedStore : ChainedStores) {
     SDValue Chain = ChainedStore->getChain();
     SDValue BetterChain = FindBetterChain(ChainedStore, Chain);
 
     if (Chain != BetterChain) {
       if (ChainedStore == St)
         MadeChangeToSt = true;
       BetterChains.push_back(std::make_pair(ChainedStore, BetterChain));
     }
   }
-
   // Do all replacements after finding the replacements to make to avoid making
   // the chains more complicated by introducing new TokenFactors.
   for (auto Replacement : BetterChains)
     replaceStoreChain(Replacement.first, Replacement.second);
 
   return MadeChangeToSt;
 }
 
 /// This is the entry point for the file.
 void SelectionDAG::Combine(CombineLevel Level, AliasAnalysis *AA,
                            CodeGenOpt::Level OptLevel) {
   /// This is the main entry point to this class.
   DAGCombiner(*this, AA, OptLevel).Run(Level);
 }

lib/CodeGen/TargetLoweringBase.cpp

TargetLoweringBase::TargetLoweringBase(const TargetMachine &tm) : TM(tm) {
   BooleanVectorContents = UndefinedBooleanContent;
   SchedPreferenceInfo = Sched::ILP;
   JumpBufSize = 0;
   JumpBufAlignment = 0;
   MinFunctionAlignment = 0;
   PrefFunctionAlignment = 0;
   PrefLoopAlignment = 0;
   GatherAllAliasesMaxDepth = 18;
+  FindBetterChainsMaxChains = 32;
   MinStackArgumentAlignment = 1;
   // TODO: the default will be switched to 0 in the next commit, along
   // with the Target-specific changes necessary.
   MaxAtomicSizeInBitsSupported = 1024;
 
   MinCmpXchgSizeInBits = 0;
   SupportsUnalignedAtomics = false;