[DAG] Elide overlapping stores

[niravd]

Summary

Extend overlapping store elision to handle overwrites of stores by
larger stores.

[niravd]

Rebase past updated nontemporal tests.

[niravd]

Ping.

[hfinkel]

LGTM

[chandlerc]

There was a comment by @nemanjai on the submitted revision in phab that I think got lost:

In rL321089#229740, @nemanjai wrote:

This has broken all the PowerPC buildbots. I'll pull this patch to get the bots back to green unless you have a fix available. The smallest failing benchmark from the test-suite is sieve.c.
This patch removes half of the pre-inc stores that are actually needed. I imagine that the DAGCombiner is getting rid of these stores before they become pre-inc stores since there's a check for unindexed stores as part of this patch, but I haven't spent the time to really understand what this patch does.
I'm attaching both the IR generated for sieve.c as well as a bugpoint-reduced version of it (the reduction was done by comparing the number of pre-inc stores emitted before the patch and after it).

sieve.ll9 KBDownload

reduced.ll2 KBDownload

Notably, all PPC bots were broken by this, and it has stayed in tree for a long time. we should get it reverted.

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

if (Ld->getBasePtr() == Ptr && ST->getMemoryVT() == Ld->getMemoryVT() &&
         // There can't be any side effects between the load and store, such as
         // a call or store.
         Chain.reachesChainWithoutSideEffects(SDValue(Ld, 1))) {
       // The store is dead, remove it.
       return Chain;
     }
   }
 
-  if (StoreSDNode *ST1 = dyn_cast<StoreSDNode>(Chain)) {
-    if (ST->isUnindexed() && !ST->isVolatile() && ST1->isUnindexed() &&
-        !ST1->isVolatile() && ST1->getBasePtr() == Ptr &&
-        ST->getMemoryVT() == ST1->getMemoryVT()) {
-      // If this is a store followed by a store with the same value to the same
-      // location, then the store is dead/noop.
-      if (ST1->getValue() == Value) {
-        // The store is dead, remove it.
-        return Chain;
-      }
-
-      // If this is a store who's preceeding store to the same location
-      // and no one other node is chained to that store we can effectively
-      // drop the store. Do not remove stores to undef as they may be used as
-      // data sinks.
-      if (OptLevel != CodeGenOpt::None && ST1->hasOneUse() &&
-          !ST1->getBasePtr().isUndef()) {
-        // ST1 is fully overwritten and can be elided. Combine with it's chain
-        // value.
+  // Deal with elidable overlapping chained stores.
+  if (StoreSDNode *ST1 = dyn_cast<StoreSDNode>(Chain))
+    if (OptLevel != CodeGenOpt::None && ST1->isUnindexed() &&
+        !ST1->isVolatile() && ST1->hasOneUse() &&
+        !ST1->getBasePtr().isUndef() && !ST->isVolatile()) {
+      BaseIndexOffset STBasePtr = BaseIndexOffset::match(ST->getBasePtr(), DAG);
+      BaseIndexOffset ST1BasePtr =
+          BaseIndexOffset::match(ST1->getBasePtr(), DAG);
+      unsigned STBytes = ST->getMemoryVT().getStoreSize();
+      unsigned ST1Bytes = ST1->getMemoryVT().getStoreSize();
+      int64_t PtrDiff;
+      // If this is a store who's preceeding store to a subset of the same
+      // memory and no one other node is chained to that store we can
+      // effectively drop the store. Do not remove stores to undef as they may
+      // be used as data sinks.
+
+      if (((ST->getBasePtr() == ST1->getBasePtr()) &&
+           (ST->getValue() == ST1->getValue())) ||
+          (STBasePtr.equalBaseIndex(ST1BasePtr, DAG, PtrDiff) &&
+           (0 <= PtrDiff) && (PtrDiff + ST1Bytes <= STBytes))) {
         CombineTo(ST1, ST1->getChain());
-        return SDValue();
-      }
+        return SDValue(N, 0);
       }
     }
 
   // If this is an FP_ROUND or TRUNC followed by a store, fold this into a
   // truncating store.  We can do this even if this is already a truncstore.
   if ((Value.getOpcode() == ISD::FP_ROUND || Value.getOpcode() == ISD::TRUNCATE)
       && Value.getNode()->hasOneUse() && ST->isUnindexed() &&
       TLI.isTruncStoreLegal(Value.getOperand(0).getValueType(),
                             ST->getMemoryVT())) {
     return DAG.getTruncStore(Chain, SDLoc(N), Value.getOperand(0),

llvm/trunk/test/CodeGen/AArch64/ldst-paired-aliasing.ll

 ; RUN: llc -mcpu cortex-a53 < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-i128:128-n8:16:32:64-S128"
 target triple = "aarch64--linux-gnu"
 
 declare void @f(i8*, i8*)
 declare void @f2(i8*, i8*)
 declare void @_Z5setupv()
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #3
 
 define i32 @main() local_unnamed_addr #1 {
 ; Make sure the stores happen in the correct order (the exact instructions could change).
 ; CHECK-LABEL: main:
-; CHECK: stp xzr, xzr, [sp, #72]
+; CHECK: str xzr, [sp, #80]
 ; CHECK: str w9, [sp, #80]
-; CHECK: str q0, [sp, #48]
+; CHECK: stp q0, q0, [sp, #48]
 ; CHECK: ldr w8, [sp, #48]
-; CHECK: str q0, [sp, #64]
 
 for.body.lr.ph.i.i.i.i.i.i63:
   %b1 = alloca [10 x i32], align 16
   %x0 = bitcast [10 x i32]* %b1 to i8*
   %b2 = alloca [10 x i32], align 16
   %x1 = bitcast [10 x i32]* %b2 to i8*
   tail call void @_Z5setupv()
   %x2 = getelementptr inbounds [10 x i32], [10 x i32]* %b1, i64 0, i64 6