[DSE] Lift post-dominance for objs not accessible in caller.

[fhahn]

Summary

We can eliminate MemoryDefs of objects not accessible after the function
returns (e.g. alloca), if there are no reads between the MemoryDef and
any function exits. We can stop traversing paths that completely
overwrite the memory location of the MemoryDef.

This patch was split off D73763.

[asbirlea]

llvm/test/Transforms/DeadStoreElimination/MSSA/memset-missing-debugloc.ll

39

I don't fully understand the need for this test change, could you please clarify?

[fhahn]

Remove unnecessary test changes from memset-missing-debugloc.ll

[fhahn]

llvm/test/Transforms/DeadStoreElimination/MSSA/memset-missing-debugloc.ll

39

They are not required for this patch. I think they are supposed to be part of a different patch ( eliminating stores that are never read) and slipped in during a rebase.

Without changes, the function in the file never reads the stores/memset to the alloca and they can be completely removed. But that's not related to the patch and I've removed those changes.

[george.burgess.iv]

Thanks for this!

Just a few nits. Idea and implementation looks fine to me otherwise

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1488

s/the caller$/the caller after/

1539

nit: can this just be nested in the above if, rather than repeating !CapturesBeforeRet?

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-multipath.ll

139

s/because the it/because it/ (similar below)

217

world's smallest ₙᵢₜ: please remove the extra space before 'first'

[fhahn]

In D77736#1975209, @george.burgess.iv wrote:

Thanks for this!

Just a few nits. Idea and implementation looks fine to me otherwise

Should be addressed, thanks!

[george.burgess.iv]

LGTM. If no one else comments within a day or so, feel free to land.

Thanks again!

[asbirlea]

LGTM.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

struct DSEState {
   DominatorTree &DT;
   PostDominatorTree &PDT;
   const TargetLibraryInfo &TLI;
 
   // 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 until the
+  // Keep track of all of the objects that are invisible to the caller before
+  // the function returns.
+  SmallPtrSet<const Value *, 16> InvisibleToCallerBeforeRet;
+  // Keep track of all of the objects that are invisible to the caller
   // function returns.
-  SmallPtrSet<const Value *, 16> InvisibleToCaller;
+  SmallPtrSet<const Value *, 16> InvisibleToCallerAfterRet;
   // Keep track of blocks with throwing instructions not modeled in MemorySSA.
   SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
   // Post-order numbers for each basic block. Used to figure out if memory
   // accesses are executed before another access.
   DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
for (BasicBlock *BB : post_order(&F)) {
         if (I.mayThrow() && !MA)
           State.ThrowingBlocks.insert(I.getParent());
 
         auto *MD = dyn_cast_or_null<MemoryDef>(MA);
         if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
             hasAnalyzableMemoryWrite(&I, TLI) && isRemovable(&I))
           State.MemDefs.push_back(MD);
 
-        // Track alloca and alloca-like objects. Here we care about objects not
-        // visible to the caller during function execution. Alloca objects are
-        // invalid in the caller, for alloca-like objects we ensure that they
-        // are not captured throughout the function.
-        if (isa<AllocaInst>(&I) ||
-            (isAllocLikeFn(&I, &TLI) && !PointerMayBeCaptured(&I, false, true)))
-          State.InvisibleToCaller.insert(&I);
+        // Track whether alloca and alloca-like objects are visible in the
+        // caller before and after the function returns. Alloca objects are
+        // invalid in the caller, so they are neither visible before or after
+        // the function returns.
+        if (isa<AllocaInst>(&I)) {
+          State.InvisibleToCallerBeforeRet.insert(&I);
+          State.InvisibleToCallerAfterRet.insert(&I);
+        }
+
+        // For alloca-like objects we need to check if they are captured before
+        // the function returns and if the return might capture the object.
+        if (isAllocLikeFn(&I, &TLI)) {
+          bool CapturesBeforeRet = PointerMayBeCaptured(&I, false, true);
+          if (!CapturesBeforeRet)
+            State.InvisibleToCallerBeforeRet.insert(&I);
+          if (!CapturesBeforeRet && !PointerMayBeCaptured(&I, true, false))
+            State.InvisibleToCallerAfterRet.insert(&I);
+        }
       }
     }
 
     // Treat byval or inalloca arguments the same as Allocas, stores to them are
     // dead at the end of the function.
     for (Argument &AI : F.args())
       if (AI.hasByValOrInAllocaAttr())
-        State.InvisibleToCaller.insert(&AI);
+        State.InvisibleToCallerBeforeRet.insert(&AI);
     return State;
   }
 
   Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
     if (!I->mayWriteToMemory())
       return None;
 
     if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
     ModRefInfo MR = AA.getModRefInfo(UseInst, DefLoc);
     // If necessary, perform additional analysis.
     if (isRefSet(MR))
       MR = AA.callCapturesBefore(UseInst, DefLoc, &DT);
     return isRefSet(MR);
   }
 
   // Find a MemoryDef writing to \p DefLoc and dominating \p Current, with no
-  // read access in between or return None otherwise. The returned value may not
-  // (completely) overwrite \p DefLoc. Currently we bail out when we encounter
-  // an aliasing MemoryUse (read).
-  Optional<MemoryAccess *> getDomMemoryDef(MemoryDef *KillingDef,
-                                           MemoryAccess *Current,
-                                           MemoryLocation DefLoc,
-                                           bool DefVisibleToCaller,
-                                           int &ScanLimit) const {
+  // read access between them or on any other path to a function exit block if
+  // \p DefLoc is not accessible after the function returns. If there is no such
+  // MemoryDef, return None. The returned value may not (completely) overwrite
+  // \p DefLoc. Currently we bail out when we encounter an aliasing MemoryUse
+  // (read).
+  Optional<MemoryAccess *>
+  getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *Current,
+                  MemoryLocation DefLoc, bool DefVisibleToCallerBeforeRet,
+                  bool DefVisibleToCallerAfterRet, int &ScanLimit) const {
     MemoryAccess *DomAccess;
     bool StepAgain;
     LLVM_DEBUG(dbgs() << "  trying to get dominating access for " << *Current
                       << "\n");
     // Find the next clobbering Mod access for DefLoc, starting at Current.
     do {
       StepAgain = false;
       // Reached TOP.
do {
       DomAccess = MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(CurrentUD,
                                                                       DefLoc);
       if (MSSA.isLiveOnEntryDef(DomAccess))
         return None;
 
       if (isa<MemoryPhi>(DomAccess))
         break;
 
-      // Check if we can skip DomDef for DSE. We also require the KillingDef
-      // execute whenever DomDef executes and use post-dominance to ensure that.
-
+      // Check if we can skip DomDef for DSE. For accesses to objects that are
+      // accessible after the function returns, KillingDef must execute whenever
+      // DomDef executes and use post-dominance to ensure that.
       MemoryDef *DomDef = dyn_cast<MemoryDef>(DomAccess);
-      if ((DomDef && canSkipDef(DomDef, DefVisibleToCaller)) ||
-          !PDT.dominates(KillingDef->getBlock(), DomDef->getBlock())) {
+      if ((DomDef && canSkipDef(DomDef, DefVisibleToCallerBeforeRet)) ||
+          (DefVisibleToCallerAfterRet &&
+           !PDT.dominates(KillingDef->getBlock(), DomDef->getBlock()))) {
         StepAgain = true;
         Current = DomDef->getDefiningAccess();
       }
 
     } while (StepAgain);
 
     LLVM_DEBUG({
       dbgs() << "  Checking for reads of " << *DomAccess;
struct DSEState {
   // Check for any extra throws between SI and NI that block DSE.  This only
   // checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
   // throw are handled during the walk from one def to the next.
   bool mayThrowBetween(Instruction *SI, Instruction *NI,
                        const Value *SILocUnd) const {
     // First see if we can ignore it by using the fact that SI is an
     // alloca/alloca like object that is not visible to the caller during
     // execution of the function.
-    if (SILocUnd && InvisibleToCaller.count(SILocUnd))
+    if (SILocUnd && InvisibleToCallerBeforeRet.count(SILocUnd))
       return false;
 
     if (SI->getParent() == NI->getParent())
       return ThrowingBlocks.find(SI->getParent()) != ThrowingBlocks.end();
     return !ThrowingBlocks.empty();
   }
 
   // Check if \p NI acts as a DSE barrier for \p SI. The following instructions
   // act as barriers:
   //  * A memory instruction that may throw and \p SI accesses a non-stack
   //  object.
   //  * Atomic stores stronger that monotonic.
   bool isDSEBarrier(Instruction *SI, MemoryLocation &SILoc,
                     const Value *SILocUnd, Instruction *NI,
                     MemoryLocation &NILoc) const {
     // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
     // like object that does not escape.
-    if (NI->mayThrow() && !InvisibleToCaller.count(SILocUnd))
+    if (NI->mayThrow() && !InvisibleToCallerBeforeRet.count(SILocUnd))
       return true;
 
     if (NI->isAtomic()) {
       if (auto *NSI = dyn_cast<StoreInst>(NI)) {
         if (isStrongerThanMonotonic(NSI->getOrdering()))
           return true;
       } else
         llvm_unreachable(
if (!MaybeSILoc) {
                         << *SI << "\n");
       continue;
     }
     MemoryLocation SILoc = *MaybeSILoc;
     assert(SILoc.Ptr && "SILoc should not be null");
     const Value *SILocUnd = GetUnderlyingObject(SILoc.Ptr, DL);
     Instruction *DefObj =
         const_cast<Instruction *>(dyn_cast<Instruction>(SILocUnd));
-    bool DefVisibleToCaller = !State.InvisibleToCaller.count(SILocUnd);
-    if (DefObj && ((isAllocLikeFn(DefObj, &TLI) &&
-                    !PointerMayBeCapturedBefore(DefObj, false, true, SI, &DT))))
-      DefVisibleToCaller = false;
+    bool DefVisibleToCallerBeforeRet =
+        !State.InvisibleToCallerBeforeRet.count(SILocUnd);
+    bool DefVisibleToCallerAfterRet =
+        !State.InvisibleToCallerAfterRet.count(SILocUnd);
+    if (DefObj && isAllocLikeFn(DefObj, &TLI)) {
+      if (DefVisibleToCallerBeforeRet)
+        DefVisibleToCallerBeforeRet =
+            PointerMayBeCapturedBefore(DefObj, false, true, SI, &DT);
+    }
 
     MemoryAccess *Current = KillingDef;
     LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
                       << *KillingDef << " (" << *SI << ")\n");
 
     int ScanLimit = MemorySSAScanLimit;
     // Worklist of MemoryAccesses that may be killed by KillingDef.
     SetVector<MemoryAccess *> ToCheck;
     ToCheck.insert(KillingDef->getDefiningAccess());
 
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
       Current = ToCheck[I];
       if (State.SkipStores.count(Current))
         continue;
 
       Optional<MemoryAccess *> Next = State.getDomMemoryDef(
-          KillingDef, Current, SILoc, DefVisibleToCaller, ScanLimit);
+          KillingDef, Current, SILoc, DefVisibleToCallerBeforeRet,
+          DefVisibleToCallerAfterRet, ScanLimit);
 
       if (!Next) {
         LLVM_DEBUG(dbgs() << "  finished walk\n");
         continue;
       }
 
       MemoryAccess *DomAccess = *Next;
       LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DomAccess << "\n");

llvm/test/Transforms/DeadStoreElimination/MSSA/memset-missing-debugloc.ll

 ;
 ; int a() {
 ;   long b[]{2, 2, 2, 2, 0};
 ;   if (a())
 ;     ;
 ; }
 
 
-define dso_local i32 @_Z1av() !dbg !7 {
+define dso_local i32 @_Z1av([5 x i64]* %b) !dbg !7 {
 entry:
   %retval = alloca i32, align 4
-  %b = alloca [5 x i64], align 16
   call void @llvm.dbg.declare(metadata [5 x i64]* %b, metadata !11, metadata !DIExpression()), !dbg !16
   %0 = bitcast [5 x i64]* %b to i8*, !dbg !16
   call void @llvm.memset.p0i8.i64(i8* align 16 %0, i8 0, i64 40, i1 false), !dbg !16
   %1 = bitcast i8* %0 to [5 x i64]*, !dbg !16
   %2 = getelementptr inbounds [5 x i64], [5 x i64]* %1, i32 0, i32 0, !dbg !16
   store i64 2, i64* %2, align 16, !dbg !16
   %3 = getelementptr inbounds [5 x i64], [5 x i64]* %1, i32 0, i32 1, !dbg !16
   store i64 2, i64* %3, align 8, !dbg !16
   %4 = getelementptr inbounds [5 x i64], [5 x i64]* %1, i32 0, i32 2, !dbg !16
   store i64 2, i64* %4, align 16, !dbg !16
   %5 = getelementptr inbounds [5 x i64], [5 x i64]* %1, i32 0, i32 3, !dbg !16
   store i64 2, i64* %5, align 8, !dbg !16
-  %call = call i32 @_Z1av(), !dbg !17
+  %call = call i32 @_Z1av([5 x i64]* %b), !dbg !17
   %tobool = icmp ne i32 %call, 0, !dbg !17
   br i1 %tobool, label %if.then, label %if.end, !dbg !19
 
 if.then:                                          ; preds = %entry
   br label %if.end, !dbg !19
 
 if.end:                                           ; preds = %if.then, %entry
   call void @llvm.trap(), !dbg !20

llvm/test/Transforms/DeadStoreElimination/MSSA/memset-unknown-sizes.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -dse -enable-dse-memoryssa -S %s | FileCheck %s
 
 declare i8* @_Znwm() local_unnamed_addr #0
 
 ; Function Attrs: argmemonly nounwind willreturn writeonly
 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg) #1
 
 define void @test1(i1 %c) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[COND_TRUE_I_I_I:%.*]], label [[COND_END_I_I_I:%.*]]
 ; CHECK:       cond.true.i.i.i:
 ; CHECK-NEXT:    ret void
 ; CHECK:       cond.end.i.i.i:
-; CHECK-NEXT:    [[CALL_I_I_I_I_I:%.*]] = tail call noalias nonnull i8* @_Znam() #2
+; CHECK-NEXT:    [[CALL_I_I_I_I_I:%.*]] = tail call noalias nonnull i8* @_Znam()
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[CALL_I_I_I_I_I]] to i64*
 ; CHECK-NEXT:    tail call void @llvm.memset.p0i8.i64(i8* nonnull align 8 [[CALL_I_I_I_I_I]], i8 0, i64 undef, i1 false)
 ; CHECK-NEXT:    store i64 0, i64* [[TMP0]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %c, label %cond.true.i.i.i, label %cond.end.i.i.i
 

 
 
 define void @test2(i1 %c) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CLEANUP_CONT104:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[MUL_I_I_I_I:%.*]] = shl nuw nsw i64 undef, 3
-; CHECK-NEXT:    [[CALL_I_I_I_I_I_I131:%.*]] = call noalias nonnull i8* @_Znwm() #2
+; CHECK-NEXT:    [[CALL_I_I_I_I_I_I131:%.*]] = call noalias nonnull i8* @_Znwm()
 ; CHECK-NEXT:    [[DOTCAST_I_I:%.*]] = bitcast i8* [[CALL_I_I_I_I_I_I131]] to i64*
 ; CHECK-NEXT:    store i64 0, i64* [[DOTCAST_I_I]], align 8
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 [[CALL_I_I_I_I_I_I131]], i8 0, i64 [[MUL_I_I_I_I]], i1 false)
 ; CHECK-NEXT:    ret void
 ; CHECK:       cleanup.cont104:
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-malloc-free.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 
-; XFAIL: *
-; TODO: Handling of free not implemented yet.
-
 ; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 declare void @unknown_func()
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) nounwind
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind

 %struct.EdgeListStruct = type { i32, %struct.NodeStruct*, %struct.EdgeListStruct* }
 %struct.SystemCallMapStruct = type { i32, i32, %struct.SystemCallMapElementStruct** }
 
 declare %struct.NodePtrVecStruct* @NodePtrVec_new(i32)
 
 define noalias %struct.SystemCallMapElementStruct* @SystemCallMapElement_new(i8* nocapture readonly %label, i32 %initialSize) {
 ; CHECK-LABEL: @SystemCallMapElement_new(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CALL:%.*]] = tail call dereferenceable_or_null(24) i8* @malloc(i64 24) #7
+; CHECK-NEXT:    [[CALL:%.*]] = tail call dereferenceable_or_null(24) i8* @malloc(i64 24) #6
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[CALL]] to %struct.SystemCallMapElementStruct*
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[CALL]], null
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[CALL1:%.*]] = tail call i8* @strdup(i8* [[LABEL:%.*]])
 ; CHECK-NEXT:    [[LABEL2:%.*]] = bitcast i8* [[CALL]] to i8**
 ; CHECK-NEXT:    store i8* [[CALL1]], i8** [[LABEL2]], align 8
 ; CHECK-NEXT:    [[INDEX:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 8
cleanup:                                          ; preds = %entry, %if.end, %if.then9, %if.then5
   ret %struct.SystemCallMapElementStruct* %retval.0
 }
 
 %struct.BitfieldStruct = type { i32, i8* }
 
 define noalias %struct.BitfieldStruct* @Bitfield_new(i32 %bitsNeeded) {
 ; CHECK-LABEL: @Bitfield_new(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CALL:%.*]] = tail call dereferenceable_or_null(16) i8* @malloc(i64 16) #7
+; CHECK-NEXT:    [[CALL:%.*]] = tail call dereferenceable_or_null(16) i8* @malloc(i64 16) #6
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i8* [[CALL]] to %struct.BitfieldStruct*
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[CALL]], null
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[BITSNEEDED:%.*]], 7
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[ADD]], 8
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[DIV]] to i64
-; CHECK-NEXT:    [[CALL1:%.*]] = tail call i8* @calloc(i64 [[CONV]], i64 1) #8
+; CHECK-NEXT:    [[CALL1:%.*]] = tail call i8* @calloc(i64 [[CONV]], i64 1) #7
 ; CHECK-NEXT:    [[BITFIELD:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 8
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i8* [[BITFIELD]] to i8**
 ; CHECK-NEXT:    store i8* [[CALL1]], i8** [[TMP1]], align 8
 ; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp eq i8* [[CALL1]], null
 ; CHECK-NEXT:    br i1 [[TOBOOL3]], label [[IF_THEN4:%.*]], label [[IF_END5:%.*]]
 ; CHECK:       if.then4:
 ; CHECK-NEXT:    tail call void @free(i8* nonnull [[CALL]])
 ; CHECK-NEXT:    br label [[CLEANUP]]

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memintrinsics.ll

 ; Overwriting store along one path to the exit.
 define void @alloca_1(i1 %c) {
 ; CHECK-LABEL: @alloca_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[P_ALLOCA:%.*]] = alloca [32 x i32]
 ; CHECK-NEXT:    [[P:%.*]] = bitcast [32 x i32]* [[P_ALLOCA]] to i32*
 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i8, i8* [[P3]], i64 4
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 24, i1 false)
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:

 ; Post-dominating store.
 define void @alloca_2(i1 %c) {
 ; CHECK-LABEL: @alloca_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[P_ALLOCA:%.*]] = alloca [32 x i32]
 ; CHECK-NEXT:    [[P:%.*]] = bitcast [32 x i32]* [[P_ALLOCA]] to i32*
 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i8, i8* [[P3]], i64 4
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 24, i1 false)
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX2]], align 4

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-multipath.ll

 
 bb5:
   ret void
 }
 
 
 ; Tests where the pointer/object is *NOT* accessible after the function returns.
 
+; The store in the entry block can be eliminated, because the it is overwritten
+; on all paths to the exit.
 define void @alloca_1(i1 %c1) {
 ; CHECK-LABEL: @alloca_1(
 ; CHECK-NEXT:    [[P:%.*]] = alloca i32
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 3, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb5:
bb2:
   store i32 3, i32* %P
   br label %bb5
 
 bb5:
   call void @use(i32* %P)
   ret void
 }
 
+; The store in the entry block can be eliminated, because the it is overwritten
+; on all paths to the exit.
 define void @alloca_2(i1 %c.1, i1 %c.2) {
 ; CHECK-LABEL: @alloca_2(
 ; CHECK-NEXT:    [[P:%.*]] = alloca i32
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    store i32 3, i32* [[P]]
bb4:
   store i32 5, i32* %P
   br label %bb5
 
 bb5:
   call void @use(i32* %P)
   ret void
 }
 
+; The store in the entry block cannot be eliminated. There's a path from the
+;  first store to the read in bb5, where the location is not overwritten.
 define void @alloca_3(i1 %c1) {
 ; CHECK-LABEL: @alloca_3(
 ; CHECK-NEXT:    [[P:%.*]] = alloca i32
 ; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5:%.*]]

 bb2:
   br label %bb5
 
 bb5:
   call void @use(i32* %P)
   ret void
 }
 
+; The store in the entry block can be eliminated, because the it is overwritten
+; before the use in bb1 and not read on other paths to the function exit. The
+; object cannot be accessed by the caller.
 define void @alloca_4(i1 %c1) {
 ; CHECK-LABEL: @alloca_4(
 ; CHECK-NEXT:    [[P:%.*]] = alloca i32
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    call void @use(i32* [[P]])
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb5:

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-simple.ll

 bb3:
   ret void
 }
 
 
 define void @test11() {
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:    [[P:%.*]] = alloca i32
-; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void