[DSE] Eliminate stores at the end of the function.

[fhahn]

Summary

This patch add support for eliminating MemoryDefs that do not have any
aliasing users, which indicates that there are no reads/writes to the
memory location until the end of the function.

To eliminate such defs, we have to ensure that the underlying object is
not visible in the caller and does not escape via returning. We need a
separate check for that, as InvisibleToCaller does not consider returns.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[asbirlea]

Just a general comment here: DSE shouldn't necessarily make all optimizations possible. This one looks like it should be caught by DCE. If it's not, perhaps it would be good to improve DCE. Alternatively, if it's cheap enough, add a comment that it's still worth adding it to DSE.

[fhahn]

In D72631#1820660, @asbirlea wrote:

Just a general comment here: DSE shouldn't necessarily make all optimizations possible. This one looks like it should be caught by DCE. If it's not, perhaps it would be good to improve DCE. Alternatively, if it's cheap enough, add a comment that it's still worth adding it to DSE.

Agreed! I tried to structured the patches to match the current functionality of DSE though, to make it easier to compare statistics between both implementations to double check we get the desired results.

Currently I think neither DCE nor ADCE would eliminate the cases covered with this patch, as they don't reason about memory accesses. To eliminate a MemoryDef at 'the end of the function', we have to prove that there are no clobbering reads between the MemoryDef and the function exit. With reworking to bottom-up, I think it might make sense to restructure the code in this patch too: only collect MemoryDefs potentially at 'the end' of a function in the main elimination loop and then afterwards do a bottom-up walk starting at the end nodes, eliminating the applicable MemoryDefs.

[fhahn]

Needs to be updated after changing approach to use a bottom-up walk.

[fhahn]

Rebased after D72700 landed.

[fhahn]

rebased

[fhahn]

Ping. Rebased after D77736 landed.

[fhahn]

ping :)

[fhahn]

ping :)

[fhahn]

Rebased on top of latest changes. Ping :)

[fhahn]

Ping :)

Rebased, added a few comments, moved additional tests from todo, improve naming.

[asbirlea]

Thank you for the patch!

Minor comments on the tests for keeping the patch clean, but otherwise lgtm.

Please consider the performance comments for future improvements.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1658

FWIW, this call will add up a lot on compile-time. Those AA calls are very expensive, and the MemorySSAScanLimit is per call, so dependent on the number of MemoryDefs in MemDefs when called in the eliminateDeadWritesAtEndOfFunction.
In the worst case, you'd hit something like:

;a, b, c, d noalias
store to a
store to b
store to c
store to d
load/use d
; repeat read/write to d until MemorySSAScanLimit is hit

The store to a,b,c cannot be eliminated because they each hit the limit, but the work is done towards checking all accesses to d.
A potential helper would be a caching mechanism similar to what MemorySSA does internally. Along the lines of: if the first store to d is found as NoAlias and subsequent access is a load to the same MemoryLocation, this is known NoAlias.
Also worth considering for reducing compile-time, if it's not a pattern as straight-forward as store/load/mem_cpy to a precise locations to just bail-out and not do the AA call.

This comment is solely focused on performance when trying to turn this on.

1989

Also for performance, it would be great to have some metrics into what's more expensive to perform first: isWriteAtEndOfFunction or GetUnderlyingObjects+searching the map InvisibleToCallerAfterRet.

llvm/test/Transforms/DeadStoreElimination/MSSA/combined-partial-overwrites.ll

255 ↗

(On Diff #272756)

Look unrelated to the patch? Perhaps commit separately as NFC?

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

38

Commit first as NFC?
Same for below?

[Whitney]

llvm/test/Transforms/DeadStoreElimination/MSSA/mda-with-dbg-values.ll

72–73

update comment.

[Whitney]

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

210

Some of the TODO comments can also be removed.

[fhahn]

In D72631#2109804, @asbirlea wrote:

Thank you for the patch!

Minor comments on the tests for keeping the patch clean, but otherwise lgtm.

Please consider the performance comments for future improvements.

Thanks, I added TODO comments and plan to follow up to them soon. I'll try to collect a few cases with compile-time outliers for further analysis/tuning and share them.

llvm/test/Transforms/DeadStoreElimination/MSSA/combined-partial-overwrites.ll

255 ↗

(On Diff #272756)

Done, thanks!

llvm/test/Transforms/DeadStoreElimination/MSSA/mda-with-dbg-values.ll

72–73

Done, thanks!

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

38

Done, thanks!

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

210

Done, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

for (BasicBlock *BB : post_order(&F)) {
       State.PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
         MemoryAccess *MA = MSSA.getMemoryAccess(&I);
         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.getLocForWriteEx(&I) && isRemovable(&I))
           State.MemDefs.push_back(MD);
 
         // 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);
bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *UseInst) const {
 
     const DataLayout &DL = F.getParent()->getDataLayout();
 
     return CC &&
            isOverwrite(*CC, DefLoc, DL, TLI, DepWriteOffset, InstWriteOffset,
                        UseInst, IOL, AA, &F) == OW_Complete;
   }
 
-  /// Returns true if \p Use may read from \p DefLoc.
+  /// 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");
+
+    auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
+    if (!MaybeLoc) {
+      LLVM_DEBUG(dbgs() << "  ... could not get location for write.\n");
+      return false;
+    }
+
+    SmallVector<MemoryAccess *, 4> WorkList;
+    SmallPtrSet<MemoryAccess *, 8> Visited;
+    auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
+      if (!Visited.insert(Acc).second)
+        return;
+      for (Use &U : Acc->uses())
+        WorkList.push_back(cast<MemoryAccess>(U.getUser()));
+    };
+    PushMemUses(Def);
+    for (unsigned I = 0; I < WorkList.size(); I++) {
+      if (WorkList.size() >= MemorySSAScanLimit) {
+        LLVM_DEBUG(dbgs() << "  ... hit exploration limit.\n");
+        return false;
+      }
+
+      MemoryAccess *UseAccess = WorkList[I];
+      if (isa<MemoryPhi>(UseAccess)) {
+        PushMemUses(UseAccess);
+        continue;
+      }
+
+      // TODO: Checking for aliasing is expensive. Consider reducing the amount
+      // of times this is called and/or caching it.
+      Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
+      if (isReadClobber(*MaybeLoc, UseInst)) {
+        LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");
+        return false;
+      }
+
+      if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
+        PushMemUses(UseDef);
+    }
+    return true;
+  }
+
+  // Returns true if \p Use may read from \p DefLoc.
   bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
     if (!UseInst->mayReadFromMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
if (NI->isAtomic()) {
         return isStrongerThanMonotonic(LI->getOrdering());
       if (auto *SI = dyn_cast<StoreInst>(NI))
         return isStrongerThanMonotonic(SI->getOrdering());
       llvm_unreachable("other instructions should be skipped in MemorySSA");
     }
     return false;
   }
 
+  /// Eliminate writes to objects that are not visible in the caller and are not
+  /// accessed before returning from the function.
+  bool eliminateDeadWritesAtEndOfFunction() {
+    const DataLayout &DL = F.getParent()->getDataLayout();
+    bool MadeChange = false;
+    LLVM_DEBUG(
+        dbgs()
+        << "Trying to eliminate MemoryDefs at the end of the function\n");
+    for (int I = MemDefs.size() - 1; I >= 0; I--) {
+      MemoryDef *Def = MemDefs[I];
+      if (SkipStores.find(Def) != SkipStores.end())
+        continue;
+
+      // TODO: Consider doing the underlying object check first, if it is
+      // beneficial compile-time wise.
+      if (isWriteAtEndOfFunction(Def)) {
+        Instruction *DefI = Def->getMemoryInst();
+        // See through pointer-to-pointer bitcasts
+        SmallVector<const Value *, 4> Pointers;
+        GetUnderlyingObjects(getLocForWriteEx(DefI)->Ptr, Pointers, DL);
+
+        LLVM_DEBUG(dbgs() << "   ... MemoryDef is not accessed until the end "
+                             "of the function\n");
+        bool CanKill = true;
+        for (const Value *Pointer : Pointers) {
+          if (!InvisibleToCallerAfterRet.count(Pointer)) {
+            CanKill = false;
+            break;
+          }
+        }
+
+        if (CanKill) {
+          deleteDeadInstruction(DefI);
+          ++NumFastStores;
+          MadeChange = true;
+        }
+      }
+    }
+    return MadeChange;
+  }
+
   /// \returns true if \p Def is a no-op store, either because it
   /// directly stores back a loaded value or stores zero to a calloced object.
   bool storeIsNoop(MemoryDef *Def, MemoryLocation DefLoc, const Value *DefUO) {
     StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
     if (!Store)
       return false;
 
     if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
for (unsigned I = 0; I < ToCheck.size(); I++) {
       }
     }
   }
 
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(&AA, DL, KV.second);
 
+  MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // DSE Pass
 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {

llvm/test/Transforms/DeadStoreElimination/MSSA/2011-09-06-EndOfFunction.ll

-; XFAIL: *
 ; RUN: opt -dse -enable-dse-memoryssa -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin"
 
 %"class.std::auto_ptr" = type { i32* }
 
 ; CHECK-LABEL: @_Z3foov(

llvm/test/Transforms/DeadStoreElimination/MSSA/libcalls.ll

-; XFAIL: *
 ; RUN: opt -S -basicaa -dse -enable-dse-memoryssa < %s | FileCheck %s
 
 declare i8* @strcpy(i8* %dest, i8* %src) nounwind
 define void @test1(i8* %src) {
 ; CHECK-LABEL: @test1(
   %B = alloca [16 x i8]
   %dest = getelementptr inbounds [16 x i8], [16 x i8]* %B, i64 0, i64 0
 ; CHECK-NOT: @strcpy

llvm/test/Transforms/DeadStoreElimination/MSSA/mda-with-dbg-values.ll

 !15 = !DISubroutineType(types: !16)
 !16 = !{null}
 !17 = !DILocalVariable(name: "i", scope: !14, file: !3, line: 7, type: !7)
 !18 = !DILocation(line: 7, column: 10, scope: !14)
 !19 = !DILocation(line: 8, column: 7, scope: !14)
 !20 = !DILocation(line: 9, column: 5, scope: !14)
 !21 = !DILocation(line: 10, column: 1, scope: !14)
 
-; Check that the store is removed and that the memcpy is still there
+; Check that the both the store and memcpy are removed because they both access
+; an alloca that is not read.
 ; CHECK-LABEL: foo
 ; CHECK-NOT:   store i8
-; CHECK:       call void @llvm.memcpy
+; CHECK-NOT:   call void @llvm.memcpy
 ; CHECK:       ret void

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; XFAIL: *
 ; RUN: opt -S -dse -enable-dse-memoryssa < %s | FileCheck %s
 
 declare void @llvm.memcpy.p0i8.p0i8.i8(i8* nocapture, i8* nocapture, i8, i1) nounwind
 declare void @llvm.memmove.p0i8.p0i8.i8(i8* nocapture, i8* nocapture, i8, i1) nounwind
 declare void @llvm.memset.p0i8.i8(i8* nocapture, i8, i8, i1) nounwind
 
 define void @test1() {
 ; CHECK-LABEL: @test1(
;
 
   call void @llvm.memmove.p0i8.p0i8.i8(i8* %A, i8* %B, i8 -1, i1 false)
 
   ret void
 }
 
 define void @test3() {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[B:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    ret void
 ;
   %A = alloca i8
   %B = alloca i8
 
   store i8 0, i8* %A  ;; Written to by memset
 
   call void @llvm.memset.p0i8.i8(i8* %A, i8 0, i8 -1, i1 false)

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

;
   call void @may_throw()
   br label %exit
 
 exit:
   store i8 1, i8* %m
   call void @capture(i8* %m)
   ret i8* %m
 }
-; TODO: Remove store in exit.
 ; Stores to stack objects can be eliminated if they are not captured inside the function.
 define void @test_alloca_nocapture_1() {
 ; CHECK-LABEL: @test_alloca_nocapture_1(
-; CHECK-NEXT:    [[M:%.*]] = alloca i8
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    store i8 1, i8* [[M]]
 ; CHECK-NEXT:    ret void
 ;
   %m = alloca i8
   store i8 0, i8* %m
   call void @foo()
   br label %exit
 
 exit:
   store i8 1, i8* %m
   ret void
 }
 
-; TODO: Remove store in exit.
 ; Cannot remove first store i8 0, i8* %m, as the call to @capture captures the object.
 define void @test_alloca_capture_1() {
 ; CHECK-LABEL: @test_alloca_capture_1(
 ; CHECK-NEXT:    [[M:%.*]] = alloca i8
 ; CHECK-NEXT:    store i8 0, i8* [[M]]
 ; CHECK-NEXT:    call void @capture(i8* [[M]])
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    store i8 1, i8* [[M]]
 ; CHECK-NEXT:    ret void
 ;
   %m = alloca i8
   store i8 0, i8* %m
   call void @capture(i8* %m)
   br label %exit
 
 exit:
   store i8 1, i8* %m
   ret void
 }
 
-; TODO: Remove store at exit.
 ; We can remove the last store to %m, even though it escapes because the alloca
 ; becomes invalid after the function returns.
 define void @test_alloca_capture_2(%S1* %E) {
 ; CHECK-LABEL: @test_alloca_capture_2(
 ; CHECK-NEXT:    [[M:%.*]] = alloca i8
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[F_PTR:%.*]] = getelementptr [[S1:%.*]], %S1* [[E:%.*]], i32 0, i32 0
 ; CHECK-NEXT:    store i8* [[M]], i8** [[F_PTR]]
-; CHECK-NEXT:    store i8 1, i8* [[M]]
 ; CHECK-NEXT:    ret void
 ;
   %m = alloca i8
   br label %exit
 
 exit:
   %f.ptr = getelementptr %S1, %S1* %E, i32 0, i32 0
   store i8* %m, i8** %f.ptr

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

 ; CHECK:       catch:
 ; CHECK-NEXT:    [[C:%.*]] = catchpad within [[CS1]] []
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[SV]]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       cleanup:
 ; CHECK-NEXT:    [[C1:%.*]] = cleanuppad within none []
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    store i32 40, i32* [[SV]]
 ; CHECK-NEXT:    ret void
 ;
 block1:
   %sv = alloca i32
   br label %block2
 
 block2:
   store i32 20, i32* %sv

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

 
 
 define void @test27() {
 ; CHECK-LABEL: @test27(
 ; CHECK-NEXT:  bb1:
 ; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[M:%.*]] = call noalias i8* @malloc(i64 10)
-; CHECK-NEXT:    store i8 1, i8* [[M]]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[R:%.*]] = phi i8* [ null, [[BB1:%.*]] ], [ [[M]], [[BB2]] ]
 ; CHECK-NEXT:    ret void
 ;
 bb1:
   br i1 true, label %bb2, label %bb3
 bb2:

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

 
 
 ; Tests where the pointer/object is *NOT* accessible after the function returns.
 
 ; 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:    [[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:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %P.alloca = alloca [32 x i32]
   %P = bitcast [32 x i32]* %P.alloca to i32*
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1

 bb3:
   ret void
 }
 
 ; 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:    [[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
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %P.alloca = alloca [32 x i32]
   %P = bitcast [32 x i32]* %P.alloca to i32*
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1

 bb3:
   ret void
 }
 
 ; Stores along  both exit paths.
 define void @alloca_3(i1 %c) {
 ; CHECK-LABEL: @alloca_3(
 ; 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:    [[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:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
-; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %P.alloca = alloca [32 x i32]
   %P = bitcast [32 x i32]* %P.alloca to i32*
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
   %p3 = bitcast i32* %arrayidx0 to i8*
   call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)

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

 %struct.blam.4 = type { %struct.bar.5, [4 x i8] }
 %struct.bar.5 = type <{ i64, i64*, i32, i64 }>
 
 ; Make sure we do not eliminate the store in %bb.
 define void @alloca_5(i1 %c) {
 ; CHECK-LABEL: @alloca_5(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP:%.*]] = alloca [[STRUCT_BLAM_4:%.*]], align 8
-; CHECK-NEXT:    [[TMP36:%.*]] = getelementptr inbounds [[STRUCT_BLAM_4]], %struct.blam.4* [[TMP]], i64 0, i32 0, i32 1
-; CHECK-NEXT:    [[TMP37:%.*]] = bitcast i64** [[TMP36]] to i8*
 ; CHECK-NEXT:    [[TMP38:%.*]] = getelementptr inbounds [[STRUCT_BLAM_4]], %struct.blam.4* [[TMP]], i64 0, i32 0, i32 3
 ; CHECK-NEXT:    [[TMP39:%.*]] = bitcast i64* [[TMP38]] to i64*
 ; CHECK-NEXT:    store i64 0, i64* [[TMP39]], align 4
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB46:%.*]], label [[BB47:%.*]]
 ; CHECK:       bb46:
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 dereferenceable(20) [[TMP37]], i8 0, i64 26, i1 false)
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb47:
 ; CHECK-NEXT:    [[TMP48:%.*]] = getelementptr inbounds [[STRUCT_BLAM_4]], %struct.blam.4* [[TMP]], i64 0, i32 0, i32 2
 ; CHECK-NEXT:    store i32 20, i32* [[TMP48]], align 8
 ; CHECK-NEXT:    br label [[BB52:%.*]]
 ; CHECK:       bb52:
 ; CHECK-NEXT:    br i1 [[C]], label [[BB68:%.*]], label [[BB59:%.*]]
 ; CHECK:       bb59:

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

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

llvm/test/Transforms/DeadStoreElimination/MSSA/operand-bundles.ll

-; XFAIL: *
 ; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 
 declare noalias i8* @malloc(i64) "malloc-like"
 
 declare void @foo()
 declare void @bar(i8*)
 
 define void @test() {

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; XFAIL: *
 ; RUN: opt < %s -basicaa -dse -enable-dse-memoryssa -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -enable-dse-memoryssa -S | FileCheck %s
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) nounwind
 declare void @llvm.memset.element.unordered.atomic.p0i8.i64(i8* nocapture, i8, i64, i32) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
 declare void @llvm.memcpy.element.unordered.atomic.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32) nounwind
 declare void @llvm.init.trampoline(i8*, i8*, i8*)
 
-; Test for byval handling.
-%struct.x = type { i32, i32, i32, i32 }
-define void @test9(%struct.x* byval  %a) nounwind  {
-; CHECK-LABEL: @test9(
-; CHECK-NEXT:    ret void
-;
-  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
-  store i32 1, i32* %tmp2, align 4
-  ret void
-}
-
-; Test for inalloca handling.
-define void @test9_2(%struct.x* inalloca  %a) nounwind  {
-; CHECK-LABEL: @test9_2(
-; CHECK-NEXT:    ret void
-;
-  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
-  store i32 1, i32* %tmp2, align 4
-  ret void
-}
-
-; Test for preallocated handling.
-define void @test9_3(%struct.x* preallocated(%struct.x)  %a) nounwind  {
-; CHECK-LABEL: @test9_3(
-; CHECK-NEXT:    ret void
-;
-  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
-  store i32 1, i32* %tmp2, align 4
-  ret void
-}
-
 ; DSE should delete the dead trampoline.
 declare void @test11f()
 define void @test11() {
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:    ret void
 ;
   %storage = alloca [10 x i8], align 16    ; <[10 x i8]*> [#uses=1]
   %cast = getelementptr [10 x i8], [10 x i8]* %storage, i32 0, i32 0    ; <i8*> [#uses=1]
   call void @llvm.init.trampoline( i8* %cast, i8* bitcast (void ()* @test11f to i8*), i8* null )    ; <i8*> [#uses=1]
   ret void
 }
 
 
 declare noalias i8* @malloc(i32)
 
-define void @test14(i32* %Q) {
-; CHECK-LABEL: @test14(
-; CHECK-NEXT:    ret void
-;
-  %P = alloca i32
-  %DEAD = load i32, i32* %Q
-  store i32 %DEAD, i32* %P
-  ret void
-
-}
-
-define void @test20() {
-; CHECK-LABEL: @test20(
-; CHECK-NEXT:    ret void
-;
-  %m = call i8* @malloc(i32 24)
-  store i8 0, i8* %m
-  ret void
-}
-
-define void @test22(i1 %i, i32 %k, i32 %m) nounwind {
-; CHECK-LABEL: @test22(
-; CHECK-NEXT:    ret void
-;
-  %k.addr = alloca i32
-  %m.addr = alloca i32
-  %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
-  store i32 0, i32* %k.addr.m.addr, align 4
-  ret void
-}
-
 declare void @unknown_func()
 
 ; Remove redundant store if loaded value is in another block inside a loop.
 define i32 @test31(i1 %c, i32* %p, i32 %i) {
 ; CHECK-LABEL: @test31(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:

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

;
   store i32 1234567, i32* %V
   %V2 = bitcast i32* %V to i8*
   store i8 0, i8* %V2
   %X = load i32, i32* %V
   ret i32 %X
 
 }
 
+; Test for byval handling.
+%struct.x = type { i32, i32, i32, i32 }
+define void @test9(%struct.x* byval  %a) nounwind  {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:    ret void
+;
+  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+}
+
+; Test for inalloca handling.
+define void @test9_2(%struct.x* inalloca  %a) nounwind  {
+; CHECK-LABEL: @test9_2(
+; CHECK-NEXT:    ret void
+;
+  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+}
+
+; Test for preallocated handling.
+define void @test9_3(%struct.x* preallocated(%struct.x)  %a) nounwind  {
+; CHECK-LABEL: @test9_3(
+; CHECK-NEXT:    ret void
+;
+  %tmp2 = getelementptr %struct.x, %struct.x* %a, i32 0, i32 0
+  store i32 1, i32* %tmp2, align 4
+  ret void
+}
+
 ; va_arg has fuzzy dependence, the store shouldn't be zapped.
 define double @test10(i8* %X) {
 ; CHECK-LABEL: @test10(
 ; CHECK-NEXT:    [[X_ADDR:%.*]] = alloca i8*, align 8
 ; CHECK-NEXT:    store i8* [[X:%.*]], i8** [[X_ADDR]], align 8
 ; CHECK-NEXT:    [[TMP_0:%.*]] = va_arg i8** [[X_ADDR]], double
 ; CHECK-NEXT:    ret double [[TMP_0]]
 ;
;
   store i32 0, i32 addrspace(1)* %P
   ret i32 addrspace(1)* %P
 }
 
 
 declare noalias i8* @malloc(i32)
 declare noalias i8* @calloc(i32, i32)
 
+define void @test14(i32* %Q) {
+; CHECK-LABEL: @test14(
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32
+  %DEAD = load i32, i32* %Q
+  store i32 %DEAD, i32* %P
+  ret void
+
+}
+
 ; The store here is not dead because the byval call reads it.
 declare void @test19f({i32}* byval align 4 %P)
 
 define void @test19({i32} * nocapture byval align 4 %arg5) nounwind ssp {
 ; CHECK-LABEL: @test19(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds { i32 }, { i32 }* [[ARG5:%.*]], i32 0, i32 0
 ; CHECK-NEXT:    store i32 912, i32* [[TMP7]], align 4
 ; CHECK-NEXT:    call void @test19f({ i32 }* byval align 4 [[ARG5]])
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %tmp7 = getelementptr inbounds {i32}, {i32}* %arg5, i32 0, i32 0
   store i32 912, i32* %tmp7
   call void @test19f({i32}* byval align 4 %arg5)
   ret void
 
 }
 
+define void @test20() {
+; CHECK-LABEL: @test20(
+; CHECK-NEXT:    ret void
+;
+  %m = call i8* @malloc(i32 24)
+  store i8 0, i8* %m
+  ret void
+}
+
 define void @test21() {
 ; CHECK-LABEL: @test21(
 ; CHECK-NEXT:    ret void
 ;
   %m = call i8* @calloc(i32 9, i32 7)
   store i8 0, i8* %m
   ret void
 }
 
+define void @test22(i1 %i, i32 %k, i32 %m) nounwind {
+; CHECK-LABEL: @test22(
+; CHECK-NEXT:    ret void
+;
+  %k.addr = alloca i32
+  %m.addr = alloca i32
+  %k.addr.m.addr = select i1 %i, i32* %k.addr, i32* %m.addr
+  store i32 0, i32* %k.addr.m.addr, align 4
+  ret void
+}
+
 ; PR13547
 declare noalias i8* @strdup(i8* nocapture) nounwind
 define noalias i8* @test23() nounwind uwtable ssp {
 ; CHECK-LABEL: @test23(
 ; CHECK-NEXT:    [[X:%.*]] = alloca [2 x i8], align 1
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [2 x i8], [2 x i8]* [[X]], i64 0, i64 0
 ; CHECK-NEXT:    store i8 97, i8* [[ARRAYIDX]], align 1
 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds [2 x i8], [2 x i8]* [[X]], i64 0, i64 1