[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

477

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

477

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

469

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.

470

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.)

1332

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

469

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.

470

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

1332

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

1332

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

469

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

479

nit: Unnecessary parentheses.

1332

This code is gone now, can you please rebase?

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

48

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

 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"

 /// \p Earlier, but they both write to the same underlying object. In that
 /// case, use isPartialOverwrite to check if \p Later partially overwrites
 /// \p Earlier. Returns 'OW_Unknown' if nothing can be determined.
 template <typename AATy>
 static OverwriteResult
 isOverwrite(const Instruction *LaterI, const Instruction *EarlierI,
             const MemoryLocation &Later, const MemoryLocation &Earlier,
             const DataLayout &DL, const TargetLibraryInfo &TLI,
-            int64_t &EarlierOff, int64_t &LaterOff, AATy &AA,
-            const Function *F) {
+            int64_t &EarlierOff, int64_t &LaterOff, AATy &AA, const Function *F,
+            ScalarEvolution &SE) {
   // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
   // get imprecise values here, though (except for unknown sizes).
   if (!Later.Size.isPrecise() || !Earlier.Size.isPrecise()) {
     // Masked stores have imprecise locations, but we can reason about them
     // to some extent.
     return isMaskedStoreOverwrite(LaterI, EarlierI, AA);
   }
 
   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();
 
   // 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)) {
     // Make sure that the Later size is >= the Earlier size.
     if (LaterSize >= EarlierSize)
       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)
     return OW_Unknown;
 
   // If the "Later" store is to a recognizable object, get its size.
   uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, F);
   if (ObjectSize != MemoryLocation::UnknownSize)
     if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)
       return OW_Complete;
 
+  // If we hit a partial alias we may have a full overwrite
+  AliasResult AAR = AA.alias(Later, Earlier);
+  if (AAR == AliasResult::PartialAlias) {
+    // ScalarEvolution lets us reason in details about the pointers
+    const SCEV *EarlierSCEV = SE.getSCEV(const_cast<Value *>(P1));
+    const SCEV *LaterSCEV = SE.getSCEV(const_cast<Value *>(P2));
+    // We get the difference to know how much the stores are offsetted
+    const SCEV *Minus = SE.getMinusSCEV(EarlierSCEV, LaterSCEV);
+    // A constant difference means that the base pointer is the same
+    if (Minus->getSCEVType() == SCEVTypes::scConstant) {
+      if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Minus)) {
+        APInt Diff = SC->getAPInt();
+        // We expect a non negative size, meaning that the earlier store follows
+        // the later store in the memory layout.
+        if (Diff.isNonNegative())
+          // The later access completely overlaps the earlier store if and only
+          // if the earlier store is completely contained inside the later
+          // store. We are in the case where we know how much the earlier store
+          // if offsetted compared to the later store and we know both sizes.
+          if ((Diff.getLimitedValue() + EarlierSize) <= LaterSize)
+            return OW_Complete;
+      }
+    }
+  }
+
   // Okay, we have stores to two completely different pointers.  Try to
   // decompose the pointer into a "base + constant_offset" form.  If the base
   // pointers are equal, then we can reason about the two stores.
   EarlierOff = 0;
   LaterOff = 0;
   const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);
   const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);
 
LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n  Earlier: " << *Earlier
                       << "\n  Merged Value: " << Merged << '\n');
     return ConstantInt::get(Earlier->getValueOperand()->getType(), Merged);
   }
   return nullptr;
 }
 
 static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
-                                const TargetLibraryInfo *TLI) {
+                                const TargetLibraryInfo *TLI,
+                                ScalarEvolution *SE) {
   const DataLayout &DL = BB.getModule()->getDataLayout();
   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.
   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
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, *AA, BB.getParent(), *SE);
         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');
 
static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
   if (BB.getTerminator()->getNumSuccessors() == 0)
     MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, ThrowableInst);
 
   return MadeChange;
 }
 
 static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
                                 MemoryDependenceResults *MD, DominatorTree *DT,
-                                const TargetLibraryInfo *TLI) {
+                                const TargetLibraryInfo *TLI,
+                                ScalarEvolution *SE) {
   bool MadeChange = false;
   for (BasicBlock &BB : F)
     // Only check non-dead blocks.  Dead blocks may have strange pointer
     // cycles that will confuse alias analysis.
     if (DT->isReachableFromEntry(&BB))
-      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
+      MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI, SE);
 
   return MadeChange;
 }
 
 namespace {
 //=============================================================================
 // MemorySSA backed dead store elimination.
 //
struct DSEState {
   /// 2. No new instructions are added (only instructions removed), so cached
   ///    information for a deleted value cannot be accessed by a re-used new
   ///    value pointer.
   BatchAAResults BatchAA;
 
   MemorySSA &MSSA;
   DominatorTree &DT;
   PostDominatorTree &PDT;
+  ScalarEvolution &SE;
   const TargetLibraryInfo &TLI;
   const DataLayout &DL;
 
   // All MemoryDefs that potentially could kill other MemDefs.
   SmallVector<MemoryDef *, 64> MemDefs;
   // Any that should be skipped as they are already deleted
   SmallPtrSet<MemoryAccess *, 4> SkipStores;
   // Keep track of all of the objects that are invisible to the caller before
struct DSEState {
   // accesses are executed before another access.
   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()) {}
+           PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
+           ScalarEvolution &SE)
+      : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), SE(SE),
+        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);
+                      const TargetLibraryInfo &TLI, ScalarEvolution &SE) {
+    DSEState State(F, AA, MSSA, DT, PDT, TLI, SE);
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
     for (BasicBlock *BB : post_order(&F)) {
       State.PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
         if (I.mayThrow() && !MA)
bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
     int64_t InstWriteOffset, DepWriteOffset;
     if (auto CC = getLocForWriteEx(UseInst))
       return isOverwrite(UseInst, DefInst, *CC, DefLoc, DL, TLI, DepWriteOffset,
-                         InstWriteOffset, BatchAA, &F) == OW_Complete;
+                         InstWriteOffset, BatchAA, &F, SE) == OW_Complete;
     return false;
   }
 
   /// Returns true if \p Def is not read before returning from the function.
   bool isWriteAtEndOfFunction(MemoryDef *Def) {
     LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("
                       << *Def->getMemoryInst()
                       << ") is at the end the function \n");
bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
 
     auto TermLoc = MaybeTermLoc->first;
     if (MaybeTermLoc->second) {
       const Value *LocUO = getUnderlyingObject(Loc.Ptr);
       return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
     }
     int64_t InstWriteOffset, DepWriteOffset;
     return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DL, TLI,
-                       DepWriteOffset, InstWriteOffset, BatchAA,
-                       &F) == OW_Complete;
+                       DepWriteOffset, InstWriteOffset, BatchAA, &F,
+                       SE) == OW_Complete;
   }
 
   // Returns true if \p Use may read from \p DefLoc.
   bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
     if (isNoopIntrinsic(UseInst))
       return false;
 
     // Monotonic or weaker atomic stores can be re-ordered and do not need to be
do {
         if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
           StepAgain = true;
           Current = CurrentDef->getDefiningAccess();
         }
         continue;
       } else {
         int64_t InstWriteOffset, DepWriteOffset;
         auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc, DL, TLI,
-                              DepWriteOffset, InstWriteOffset, BatchAA, &F);
+                              DepWriteOffset, InstWriteOffset, BatchAA, &F, SE);
         // If Current does not write to the same object as KillingDef, check
         // the next candidate.
         if (OR == OW_Unknown) {
           StepAgain = true;
           Current = CurrentDef->getDefiningAccess();
         } else if (OR == OW_MaybePartial) {
           // If KillingDef only partially overwrites Current, check the next
           // candidate if the partial step limit is exceeded. This aggressively
bool storeIsNoop(MemoryDef *Def, const MemoryLocation &DefLoc,
     }
     return false;
   }
 };
 
 bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
                                   MemorySSA &MSSA, DominatorTree &DT,
                                   PostDominatorTree &PDT,
-                                  const TargetLibraryInfo &TLI) {
+                                  const TargetLibraryInfo &TLI,
+                                  ScalarEvolution &SE) {
   bool MadeChange = false;
 
-  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
+  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, SE);
   // For each store:
   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     MemoryDef *KillingDef = State.MemDefs[I];
     if (State.SkipStores.count(KillingDef))
       continue;
     Instruction *SI = KillingDef->getMemoryInst();
 
     Optional<MemoryLocation> MaybeSILoc;
for (unsigned I = 0; I < ToCheck.size(); I++) {
         State.deleteDeadInstruction(NI);
         ++NumFastStores;
         MadeChange = true;
       } else {
         // Check if NI overwrites SI.
         int64_t InstWriteOffset, DepWriteOffset;
         OverwriteResult OR =
             isOverwrite(SI, NI, SILoc, NILoc, State.DL, TLI, DepWriteOffset,
-                        InstWriteOffset, State.BatchAA, &F);
+                        InstWriteOffset, State.BatchAA, &F, SE);
         if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   NI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;
           OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
                                   NI, IOL);
         }

 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
 
   bool Changed = false;
   if (EnableMemorySSA) {
     MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
     PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
 
-    Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
+    Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI, SE);
   } else {
     MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
 
-    Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
+    Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI, &SE);
   }
 
 #ifdef LLVM_ENABLE_STATS
   if (AreStatisticsEnabled())
     for (auto &I : instructions(F))
       NumRemainingStores += isa<StoreInst>(&I);
 #endif
 
public:
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     const TargetLibraryInfo &TLI =
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
-
     bool Changed = false;
     if (EnableMemorySSA) {
+
       MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
       PostDominatorTree &PDT =
           getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 
-      Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
+      Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI, SE);
     } else {
       MemoryDependenceResults &MD =
           getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
 
-      Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
+      Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI, &SE);
     }
 
 #ifdef LLVM_ENABLE_STATS
     if (AreStatisticsEnabled())
       for (auto &I : instructions(F))
         NumRemainingStores += isa<StoreInst>(&I);
 #endif
 
if (EnableMemorySSA) {
       AU.addRequired<PostDominatorTreeWrapperPass>();
       AU.addRequired<MemorySSAWrapperPass>();
       AU.addPreserved<PostDominatorTreeWrapperPass>();
       AU.addPreserved<MemorySSAWrapperPass>();
     } else {
       AU.addRequired<MemoryDependenceWrapperPass>();
       AU.addPreserved<MemoryDependenceWrapperPass>();
     }
+
+    AU.addRequired<ScalarEvolutionWrapperPass>();
+    AU.addPreserved<ScalarEvolutionWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char DSELegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
                     false)
 
 FunctionPass *llvm::createDeadStoreEliminationPass() {
   return new DSELegacyPass();
 }

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 @MissedDSEOpportunity2(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: @MissedDSEOpportunity2(
+; 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
+}