[DSE] Extending isOverwrite to support offsetted fully overlapping stores

[fvrmatteo]

Summary

The isOverwrite function is making sure to identify if two stores are fully overlapping and ideally we would like to identify all the instances of OW_Complete as they'll yield possibly killable stores. The current implementation is incapable of spotting instances where the earlier store is offsetted compared to the later store, but still fully overlapped. The limitation seems to lie on the computation of the base pointers with the GetPointerBaseWithConstantOffset API that often yields different base pointers even if the stores are guaranteed to partially overlap (e.g. the alias analysis is returning AliasResult::PartialAlias).

The patch relies on the offsets computed and cached by BatchAAResults (available after https://reviews.llvm.org/D93529) to determine if the offsetted overlapping is OW_Complete.

Testing with ninja check-llvm didn't throw unexpected failures but I'll gladly update the patch and run more tests if this is something worth adding to the DSE pass.

[nikic]

Using scalar evolution for this purpose is definitely inappropriate. I would suggest to try basing this on D93529 instead.

[fvrmatteo]

@nikic I based it on the WIP patch you suggested and it works fine, so I updated the differential to reflect that it'll be doable without ScalarEvolution once the patch will be committed.

I noticed @dfukalov planned to fix the DSE after their patch, so I'm not sure if I should delete mine, as their fixes/improvements may be covering more cases compared to my isolated test file.

Is there official documentation on how to submit/work on a patch based on other WIP patches?

[nikic]

In D97676#2594791, @fvrmatteo wrote:

Is there official documentation on how to submit/work on a patch based on other WIP patches?

You can add dependencies by clicking on "Edit Related Revisions" on the right. I've added the parent revision for you.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

478

You are performing two queries here, one in AA.isMustAlias above and another here. While caching mitigates some of the cost, it's better to only call AA.alias() and then check if the result is MustAlias/PartialAlias.

[fvrmatteo]

Using a single AA.alias query.

[fvrmatteo]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

478

Thanks, I completely overlooked it!

[dfukalov]

In D97676#2594791, @fvrmatteo wrote:

I noticed @dfukalov planned to fix the DSE after their patch, so I'm not sure if I should delete mine, as their fixes/improvements may be covering more cases compared to my isolated test file.

I planned to work on DSE after GVN (eliminating redundant loads).
It seems these two fixes may be independent, but you can check my GVN approach in the diff: https://reviews.llvm.org/D93529?id=313082.
My test case for DSE fix is

define void @foo(float* %arg, i32 %i) {
bb:
  %i7 = add nuw nsw i32 %i, 1
  %i8 = zext i32 %i7 to i64
  %i9 = getelementptr inbounds float, float* %arg, i64 %i8
  store float undef, float* %i9, align 4

  %i2 = zext i32 %i to i64
  %i3 = getelementptr inbounds float, float* %arg, i64 %i2
  %i4 = bitcast float* %i3 to <2 x float>*
  store <2 x float> <float undef, float undef>, <2 x float>* %i4, align 16

  ret void
}

and suggest to add it to the patch since it uses vector types instead of arrays.

[fhahn]

In D97676#2593922, @nikic wrote:

Using scalar evolution for this purpose is definitely inappropriate. I would suggest to try basing this on D93529 instead.

While using scalar evolution for the problem at hand is inappropriate, it might be worth a try to use SCEV to add 'loop-aware' DSE to catch cases like https://bugs.llvm.org/show_bug.cgi?id=46460. Just some food for thought in case anyone is interested in tackling this issue :)

llvm/test/Transforms/DeadStoreElimination/MSSA/offsetted-overlapping-stores.ll

7

It would probably worth to add a few additional cases with different offsets & store types, including cases where the do not fully overlap.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

467

Why not continue using P1 and P2 here? Of course AA will also strip pointer casts, but if we already did it, we may as well pass the stripped pointers.

471

As you are performing the alias query unconditionally now, the separate P1 == P2 shortcut here isn't useful anymore, you can drop it. (I also checked whether your change may have a compile-time impact due to the unconditional query, but it does not seem so.)

1314

Is BatchAA safe to use in the non-MSSA DSE?

[fvrmatteo]

It seems these two fixes may be independent, but you can check my GVN approach in the diff: https://reviews.llvm.org/D93529?id=313082.

I'm reading the GVN source code to learn about it and understand your approach. I'll try to support the dead store example you shared. I'm probably missing something, but it seems the GVN approach is based on information deriving from the Memory Dependence Analysis (and related API), while here I'd like to find a solution suitable for both MD and MSSA in the isOverwrite function, hence I'll try to generalise the check to support the vector types.

Just some food for thought in case anyone is interested in tackling this issue :)

Assuming I'll be able to come up with a proper solution to this issue, that surely would be another occasion to learn something more about LLVM.

I'll update the patch as soon as I can figure out a reasonable way to support the different types and will update the test files accordingly.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

467

I agree I should avoid doing the same action multiple times, although I used Later and Earlier because BatchAAResults is proving an alias() function expecting MemoryLocation arguments.

471

Indeed, thanks for pointing it out. Glad that for now the compile-time impact is negligible.

1314

I'm not sure it's safe because on the MD-based DSE I see that the IR is modified and the BatchAAResults should be used when there are no IR changes in between queries. At the same time plain AliasAnalysis is not providing the offset information, so I guess I should be dropping BatchAA here for now, even though the isOverwrite will try to call getClobberOffset on the AA reference.

[fvrmatteo]

The new diff just adds some additional tests, one showing that the DSE vector test proposed by @dfukalov is properly handled and two showing that non-fully overlapping stores are kept untouched. The unneeded short-circuit condition is also removed.

@fhahn Do you think it's worth to add other specific tests not involving plain integers, vectors and arrays? Do the non-overlapping tests show what you expected?

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1314

Some types of IR modifications (removing instructions if no new ones are added) can be okay, and the MSSA-based implementation uses that. I'm just not familiar with the old one. Maybe we can avoid the question altogether though, by just deleting this code? D97877

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

467

Oh right, that makes sense. You might want to move the P1/P2 declarations lower in the code, where they are needed.

480

nit: Unnecessary parentheses.

1314

This code is gone now, can you please rebase?

llvm/test/Transforms/DeadStoreElimination/MSSA/offsetted-overlapping-stores.ll

47

Please store something other than undef here and below (0.0 is fine).

[nikic]

Could you please also update the patch summary, as this is no longer using SCEV?

[fvrmatteo]

Updated patch to reflect the requested changes. Updated the revision description too.

[fvrmatteo]

In D97676#2609966, @nikic wrote:

Could you please also update the patch summary, as this is no longer using SCEV?

Updated the patch summary, converted undef to 0.0, rebased to remove the MemDep DSE changes, removed the unnecessary parentheses and moved P1/P2 right before the first usage.

[nikic]

LGTM

[fvrmatteo]

Thanks for guiding me on this patch. I can't commit the patch myself as I don't have commit access.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
   }
 
   const uint64_t LaterSize = Later.Size.getValue();
   const uint64_t EarlierSize = Earlier.Size.getValue();
 
   const Value *P1 = Earlier.Ptr->stripPointerCasts();
   const Value *P2 = Later.Ptr->stripPointerCasts();
 
+  // Query the alias information
+  AliasResult AAR = AA.alias(Later, Earlier);
+
   // If the start pointers are the same, we just have to compare sizes to see if
   // the later store was larger than the earlier store.
-  if (P1 == P2 || AA.isMustAlias(P1, P2)) {
+  if (AAR == AliasResult::MustAlias) {
     // Make sure that the Later size is >= the Earlier size.
     if (LaterSize >= EarlierSize)
       return OW_Complete;
   }
 
+  // If we hit a partial alias we may have a full overwrite
+  if (AAR == AliasResult::PartialAlias) {
+    int64_t Off = AA.getClobberOffset(Later, Earlier).getValueOr(0);
+    if ((Off > 0) && (((uint64_t)Off + EarlierSize) <= LaterSize))
+      return OW_Complete;
+  }
+
   // Check to see if the later store is to the entire object (either a global,
   // an alloca, or a byval/inalloca argument).  If so, then it clearly
   // overwrites any other store to the same object.
   const Value *UO1 = getUnderlyingObject(P1), *UO2 = getUnderlyingObject(P2);
 
   // If we can't resolve the same pointers to the same object, then we can't
   // analyze them at all.
   if (UO1 != UO2)
static Constant *tryToMergePartialOverlappingStores(
   }
   return nullptr;
 }
 
 static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
                                 const TargetLibraryInfo *TLI) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
+  BatchAAResults BatchAA(*AA, /*CacheOffsets =*/true);
   bool MadeChange = false;
 
   MapVector<Instruction *, bool> ThrowableInst;
 
   // A map of interval maps representing partially-overwritten value parts.
   InstOverlapIntervalsTy IOL;
 
   // Do a top-down walk on the BB.
while (InstDep.isDef() || InstDep.isClobber()) {
       // If we find a write that is a) removable (i.e., non-volatile), b) is
       // completely obliterated by the store to 'Loc', and c) which we know that
       // 'Inst' doesn't load from, then we can remove it.
       // Also try to merge two stores if a later one only touches memory written
       // to by the earlier one.
       if (isRemovable(DepWrite) &&
           !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
         int64_t InstWriteOffset, DepWriteOffset;
-        OverwriteResult OR = isOverwrite(Inst, DepWrite, Loc, DepLoc, DL, *TLI,
-                                         DepWriteOffset, InstWriteOffset, *AA,
-                                         BB.getParent());
+        OverwriteResult OR =
+            isOverwrite(Inst, DepWrite, Loc, DepLoc, DL, *TLI, DepWriteOffset,
+                        InstWriteOffset, BatchAA, BB.getParent());
         if (OR == OW_MaybePartial)
           OR = isPartialOverwrite(Loc, DepLoc, DepWriteOffset, InstWriteOffset,
                                   DepWrite, IOL);
 
         if (OR == OW_Complete) {
           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DepWrite
                             << "\n  KILLER: " << *Inst << '\n');
 
struct DSEState {
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
            PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
-      : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
-        DL(F.getParent()->getDataLayout()) {}
+      : F(F), AA(AA), BatchAA(AA, /*CacheOffsets =*/true), MSSA(MSSA), DT(DT),
+        PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
                       DominatorTree &DT, PostDominatorTree &PDT,
                       const TargetLibraryInfo &TLI) {
     DSEState State(F, AA, MSSA, DT, PDT, TLI);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;

llvm/test/Transforms/DeadStoreElimination/MSSA/offsetted-overlapping-stores.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -dse -S | FileCheck %s
+
+@BUFFER = external local_unnamed_addr global [0 x i8], align 1
+
+define void @ArrayTestFullyOverlapping(i64 %0) {
+;
+; The DSE pass will try to kill the store of size i32 using the store of
+; size i64 because they fully overlap, in fact:
+;
+; - they use the same base pointer (in SCEV style '@BUFFER + %0')
+; - the offset between the two stores is 32 bits
+; - the size of the earlier store is 32 bits
+; - the size of the later store is 64 bits
+;
+; CHECK-LABEL: @ArrayTestFullyOverlapping(
+; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[TMP0:%.*]], -8
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i8* [[TMP3]] to i64*
+; CHECK-NEXT:    store i64 0, i64* [[TMP4]], align 4
+; CHECK-NEXT:    ret void
+;
+  %2 = add i64 %0, -8
+  %3 = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 %2
+  %4 = bitcast i8* %3 to i64*
+  %5 = add i64 %0, -4
+  %6 = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 %5
+  %7 = bitcast i8* %6 to i32*
+  store i32 1, i32* %7
+  store i64 0, i64* %4
+  ret void
+}
+
+define void @VectorTestFullyOverlapping(float* %arg, i32 %i) {
+; CHECK-LABEL: @VectorTestFullyOverlapping(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[I2:%.*]] = zext i32 [[I:%.*]] to i64
+; CHECK-NEXT:    [[I3:%.*]] = getelementptr inbounds float, float* [[ARG:%.*]], i64 [[I2]]
+; CHECK-NEXT:    [[I4:%.*]] = bitcast float* [[I3]] to <2 x float>*
+; CHECK-NEXT:    store <2 x float> undef, <2 x float>* [[I4]], align 16
+; CHECK-NEXT:    ret void
+;
+bb:
+  %i7 = add nuw nsw i32 %i, 1
+  %i8 = zext i32 %i7 to i64
+  %i9 = getelementptr inbounds float, float* %arg, i64 %i8
+  store float undef, float* %i9, align 4
+  %i2 = zext i32 %i to i64
+  %i3 = getelementptr inbounds float, float* %arg, i64 %i2
+  %i4 = bitcast float* %i3 to <2 x float>*
+  store <2 x float> <float undef, float undef>, <2 x float>* %i4, align 16
+  ret void
+}
+
+define void @ArrayTestPartiallyOverlapping(i64 %0) {
+;
+; The DSE pass will not kill the store because the overlap is partial
+; and won't fully clobber the i32 store.
+;
+; CHECK-LABEL: @ArrayTestPartiallyOverlapping(
+; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[TMP0:%.*]], 10
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i8* [[TMP3]] to i64*
+; CHECK-NEXT:    [[TMP5:%.*]] = add i64 [[TMP0]], 15
+; CHECK-NEXT:    [[TMP6:%.*]] = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast i8* [[TMP6]] to i32*
+; CHECK-NEXT:    store i32 1, i32* [[TMP7]], align 4
+; CHECK-NEXT:    store i64 0, i64* [[TMP4]], align 4
+; CHECK-NEXT:    ret void
+;
+  %2 = add i64 %0, 10
+  %3 = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 %2
+  %4 = bitcast i8* %3 to i64*
+  %5 = add i64 %0, 15
+  %6 = getelementptr inbounds [0 x i8], [0 x i8]* @BUFFER, i64 0, i64 %5
+  %7 = bitcast i8* %6 to i32*
+  store i32 1, i32* %7
+  store i64 0, i64* %4
+  ret void
+}
+
+define void @VectorTestPartiallyOverlapping(float* %arg, i32 %i) {
+;
+; The DSE pass will not kill the store because the overlap is partial
+; and won't fully clobber the original store.
+;
+; CHECK-LABEL: @VectorTestPartiallyOverlapping(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[I2:%.*]] = zext i32 [[I:%.*]] to i64
+; CHECK-NEXT:    [[I3:%.*]] = getelementptr inbounds float, float* [[ARG:%.*]], i64 [[I2]]
+; CHECK-NEXT:    [[I4:%.*]] = bitcast float* [[I3]] to <2 x float>*
+; CHECK-NEXT:    store <2 x float> <float 1.000000e+00, float 1.000000e+00>, <2 x float>* [[I4]], align 16
+; CHECK-NEXT:    [[I5:%.*]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    [[I6:%.*]] = zext i32 [[I5]] to i64
+; CHECK-NEXT:    [[I7:%.*]] = getelementptr inbounds float, float* [[ARG]], i64 [[I6]]
+; CHECK-NEXT:    [[I8:%.*]] = bitcast float* [[I7]] to <2 x float>*
+; CHECK-NEXT:    store <2 x float> undef, <2 x float>* [[I8]], align 16
+; CHECK-NEXT:    ret void
+;
+bb:
+  %i2 = zext i32 %i to i64
+  %i3 = getelementptr inbounds float, float* %arg, i64 %i2
+  %i4 = bitcast float* %i3 to <2 x float>*
+  store <2 x float> <float 1.000000e+00, float 1.000000e+00>, <2 x float>* %i4, align 16
+  %i5 = add nuw nsw i32 %i, 1
+  %i6 = zext i32 %i5 to i64
+  %i7 = getelementptr inbounds float, float* %arg, i64 %i6
+  %i8 = bitcast float* %i7 to <2 x float>*
+  store <2 x float> <float undef, float undef>, <2 x float>* %i8, align 16
+  ret void
+}