[DAG] Improve candidate pruning in store merge failure case. NFCI

[niravd]

Summary

During store merge we construct a sorted list of consecutive store candidates and consider
subsequences for merging into a single store. For each subsequence we check if the stored
value type is legal the merged store would have valid and fast and if the constructed value
to be stored is valid. The only properties that affect this check between subsequences is the
size of the subsequence, the alignment of the first store, the alignment of the stored load
value (when merging stores-of-loads), and whether the merged value is a constant zero.

If we do not find a viable mergeable subsequence starting from the first store of length N,
we know that a subsequence starting at a later store of length N will also fail unless the
new store's alignment, the new load's alignment (if we're merging store-of-loads), or we've
dropped stores of nonzero value and could construct a merged stores of zero (for merging
constants).

As a result if we fail to find a valid subsequence starting from the first store we can safely
skip considering subsequences that start with subsequent stores unless one of the above
properties is true. This significantly (2x) improves compile time in some pathological cases.

[niravd]

In addition to alignment, we less restrictive of const zero stores over other constant stores. Add logic to prevent skipping zero cases.

[grandinj]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12853

beggining -> beginning

12855

another of the same size would not have does not is if the
->
another of the same size would not have, is if the

12927

ditto x 2

[niravd]

Comment cleanup and apply same logic to final leg of store merge reasoning.

[niravd]

Cleanup FirstZeroAfterNonZero calc.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

while (StoreNodes.size() > 1) {
     if (IsConstantSrc) {
       LSBaseSDNode *FirstInChain = StoreNodes[0].MemNode;
       unsigned FirstStoreAS = FirstInChain->getAddressSpace();
       unsigned FirstStoreAlign = FirstInChain->getAlignment();
       unsigned LastLegalType = 1;
       unsigned LastLegalVectorType = 1;
       bool LastIntegerTrunc = false;
       bool NonZero = false;
+      unsigned FirstZeroAfterNonZero = NumConsecutiveStores;
       for (unsigned i = 0; i < NumConsecutiveStores; ++i) {
         StoreSDNode *ST = cast<StoreSDNode>(StoreNodes[i].MemNode);
         SDValue StoredVal = ST->getValue();
-
-        if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(StoredVal)) {
-          NonZero |= !C->isNullValue();
-        } else if (ConstantFPSDNode *C =
-                       dyn_cast<ConstantFPSDNode>(StoredVal)) {
-          NonZero |= !C->getConstantFPValue()->isNullValue();
+        bool IsElementZero = false;
+        if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(StoredVal))
+          IsElementZero = C->isNullValue();
+        else if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(StoredVal))
+          IsElementZero = C->getConstantFPValue()->isNullValue();
+        if (IsElementZero) {
+          if (NonZero && FirstZeroAfterNonZero == NumConsecutiveStores)
+            FirstZeroAfterNonZero = i;
         } else {
-          // Non-constant.
-          break;
+          if (NonZero)
+            FirstZeroAfterNonZero = i;
+          NonZero = true;
         }
 
         // Find a legal type for the constant store.
         unsigned SizeInBits = (i + 1) * ElementSizeBytes * 8;
         EVT StoreTy = EVT::getIntegerVT(Context, SizeInBits);
         bool IsFast = false;
         if (TLI.isTypeLegal(StoreTy) &&
             TLI.canMergeStoresTo(FirstStoreAS, StoreTy, DAG) &&
if (IsConstantSrc) {
                                      FirstStoreAlign, &IsFast) &&
               IsFast)
             LastLegalVectorType = i + 1;
         }
       }
 
       // Check if we found a legal integer type that creates a meaningful merge.
       if (LastLegalType < 2 && LastLegalVectorType < 2) {
-        StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + 1);
+        // We have already checked that candidate stores are in order
+        // and of correct shape. While there is no mergable sequence
+        // from the beggining one may start later in the sequence. The
+        // only reason a merge of size N could have failed where
+        // another of the same size would not have does not is if the
+        // alignment has improved or we've dropped a non-zero
+        // value. Drop as many candidates as we can here.
+        unsigned NumSkip = 1;
+        while (
+            (NumSkip < NumConsecutiveStores) &&
+            (NumSkip < FirstZeroAfterNonZero) &&
+            (StoreNodes[NumSkip].MemNode->getAlignment() <= FirstStoreAlign)) {
+          NumSkip++;
+        }
+        StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + NumSkip);
         continue;
       }
 
       bool UseVector = (LastLegalVectorType > LastLegalType) && !NoVectors;
       unsigned NumElem = (UseVector) ? LastLegalVectorType : LastLegalType;
 
       bool Merged = MergeStoresOfConstantsOrVecElts(
           StoreNodes, MemVT, NumElem, true, UseVector, LastIntegerTrunc);
if (IsExtractVecSrc) {
         if (TLI.isTypeLegal(Ty) &&
             TLI.canMergeStoresTo(FirstStoreAS, Ty, DAG) &&
             TLI.allowsMemoryAccess(Context, DL, Ty, FirstStoreAS,
                                    FirstStoreAlign, &IsFast) &&
             IsFast)
           NumStoresToMerge = i + 1;
       }
 
+      // Check if we found a legal integer type that creates a meaningful merge.
+      if (NumStoresToMerge < 2) {
+        // We have already checked that candidate stores are in order
+        // and of correct shape. While there is no mergable sequence
+        // from the beggining one may start later in the sequence. The
+        // only reason a merge of size N could have failed where
+        // another of the same size would not have does not is if the
+        // alignment has improved. Drop as many candidates as we can here.
+        unsigned NumSkip = 1;
+        while ((NumSkip < NumConsecutiveStores) &&
+               (StoreNodes[NumSkip].MemNode->getAlignment() <= FirstStoreAlign))
+          NumSkip++;
+
+        StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + NumSkip);
+        continue;
+      }
+
       bool Merged = MergeStoresOfConstantsOrVecElts(
           StoreNodes, MemVT, NumStoresToMerge, false, true, false);
       if (!Merged) {
         StoreNodes.erase(StoreNodes.begin(),
                          StoreNodes.begin() + NumStoresToMerge);
         continue;
       }
       // Remove merged stores for next iteration.