[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

1638

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.

1868

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 ↗

(On Diff #272756)

Commit first as NFC?
Same for below?

[Whitney]

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

72

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

Done, thanks!

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

38 ↗

(On Diff #272756)

Done, thanks!

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

210

Done, thanks!

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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 {
 
     Optional<MemoryLocation> UseLoc = getLocForWriteEx(UseInst);
     return isModSet(MR) && isMustSet(MR) &&
            (UseLoc->Size.hasValue() && DefLoc.Size.hasValue() &&
             UseLoc->Size.getValue() >= DefLoc.Size.getValue());
   }
 
   /// Returns true if \p Use may read from \p DefLoc.
+
+  bool isEnd(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() >= 100) {
+        LLVM_DEBUG(dbgs() << "  ... hit exploration limit.\n");
+        return false;
+      }
+
+      MemoryAccess *UseAccess = WorkList[I];
+      if (isa<MemoryPhi>(UseAccess)) {
+        PushMemUses(UseAccess);
+        continue;
+      }
+
+      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 CS = CallSite(UseInst))
       if (CS.onlyAccessesInaccessibleMemory())
         return false;
 
if (NI->isAtomic()) {
           return true;
       } else
         llvm_unreachable(
             "Other instructions should be modeled/skipped in MemorySSA");
     }
 
     return false;
   }
+
+  bool eliminateEnds() {
+    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;
+      if (isEnd(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;
+  }
 };
 
 bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
                                   MemorySSA &MSSA, DominatorTree &DT,
                                   PostDominatorTree &PDT,
                                   const TargetLibraryInfo &TLI) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   bool MadeChange = false;
for (unsigned I = 0; I < ToCheck.size(); I++) {
       }
     }
   }
 
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(&AA, DL, KV.second);
 
+  MadeChange |= State.eliminateEnds();
   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-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/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-simple.ll

bb2:
   ret void
 bb3:
   ret void
 }
 
 
 define void @test11() {
 ; CHECK-LABEL: @test11(
-; CHECK-NEXT:    [[P:%.*]] = alloca i32
 ; 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
 ;
   %P = alloca i32
   store i32 0, i32* %P

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

;
   store i32 %tmp17, i32* %tmp7, align 4
   ret void
 }
 
 
 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
-
-}
-
-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

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

;
   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
+
+}
+
+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
+}
+
 ; 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]]