[DSE] Support traversing MemoryPhis.

[fhahn]

Summary

For MemoryPhis, we have to avoid that the MemoryPhi may be executed
before before the access we are currently looking at.

To do this we do a post-order numbering of the basic blocks in the
function and bail out once we reach a MemoryPhi with a larger (or equal)
post-order block number than the current MemoryAccess.
This changes the order in which we visit stores for elimination.

This patch also adds support for exploring multiple paths. We keep a worklist (ToCheck) of memory accesses that might be eliminated by our starting MemoryDef or MemoryPhis for further exploration. For MemoryPhis, we add the incoming values to the worklist, for MemoryDefs we add the defining access.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

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

[fhahn]

Rebase

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

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

[fhahn]

Needs updating to work bottom-up.

[fhahn]

Updated to work with bottom up approach, iteratively.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

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

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[fhahn]

Rebased after updates to D72700.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

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

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[fhahn]

Rebased after latest changes to earlier patch.

[fhahn]

Ping. Rebased after D72700 landed.

[fhahn]

ping

[asbirlea]

One general comment: this seems to do more than just lifting the MemoryPhi restriction. It's adding some cases that were were not added to the initial version, and that's great, but it would be good to add this in the patch description at least.
(e.g. continue upward search in DSE.cpp:1871, adding removal of partially overlapping stores)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1539–1540

cast and remove null check below?

1551–1552

Can you clarify this?
KillingDef is a MemoryDef, UseAccess is a MemoryPhi inside this if. How can they be equal?

[fhahn]

In D72148#1885668, @asbirlea wrote:

j One general comment: this seems to do more than just lifting the MemoryPhi restriction. It's adding some cases that were were not added to the initial version, and that's great, but it would be good to add this in the patch description at least.

(e.g. continue upward search in DSE.cpp:1871, adding removal of partially overlapping stores)

It looks like the overlapping store handling slipped in at some point while rebasing the series. I've removed the changes and will update the separate patch. Sorry about that.

I've extended the description to include the change to how candidates for elimination are explored now. It's quite tied to handling MemoryPhis I think, but I can split it off, if you prefer.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1551–1552

I think this was a left-over before switching to a SetVector worklist. With the SetVector, we will never visit the node twice. I've added an assertion to be sure to check for cycles.

[asbirlea]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1551–1552

Sure, but this equality cannot happen, right? They're different types, and one if not a subtype of the other. One is a MemoryPhi and one a MemoryDef (KillingDef, the store that started the search), they cannot be equal even if you didn't check for cycles.

Sounds like you're thinking of not seeing DomAccess again as the worklist is a set, but you may see it AFAICT. If at :1617 DomAccess uses itself, it will be added to the worklist. I'm inclined to believe the change you meant is:

if (DomAccess == UseAccess)
  continue;

But just as well not having anything is fine. The PushMemUses will be a noop, as all uses have already been added.

1604–1605

Should this be Current == UseAccess ?

[fhahn]

Remove unnecessary assertion, add comment to check.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1551–1552

Sure, but this equality cannot happen, right?

Ah yes! I thought it was needed for a test case I added, but after the refactoring it is not necessary any longer. I've removed it

1604–1605

I've added a comment why this check is there. We have to make sure the KillingDef does not read the memory location. The easiest way is to just consider it as regular use, but skip the overwrite check. It probably makes more sense to just check for self reads before getDomMemoryDef. I've added a TODO.

On a related note, I've put up D75025, which should help with avoiding a number of unnecessary duplicated checks for the same killing def.

[fhahn]

Rebase after small fix in b8d638d337e76a632d07d61f4cef59e243b961a8

[fhahn]

ping

[fhahn]

ping.

Add a missing isa<MemoryPhi> check after getting walker result + test case.

[fhahn]

Ping.

@asbirlea I think all your comments should be addressed in the latest version.

Also rebased and fixed debug printing to account for MemoryPhis.

[fhahn]

ping

[asbirlea]

Thank you!

[ebrevnov]

@fhahn is this patch supposed to support the following case?

define i8* @foo(i1 %cond, i8* %p1, i8* %p2) {
entry:

%0 = icmp ne i1 %cond, 0
br i1 %0, label %dead_store, label %merge

dead_store:

store i8 1, i8* %p1
br label %merge

merge:

%p3 = phi i8* [ %p1, %dead_store ], [ %p2, %entry ]
store i8 2, i8* %p3
ret i8* %p3

}

If not, is there any plans or prototype which can handle it? Thanks.

[fhahn]

In D72148#2239379, @ebrevnov wrote:

@fhahn is this patch supposed to support the following case?

define i8* @foo(i1 %cond, i8* %p1, i8* %p2) {
entry:

%0 = icmp ne i1 %cond, 0
br i1 %0, label %dead_store, label %merge

dead_store:

store i8 1, i8* %p1
br label %merge

merge:

%p3 = phi i8* [ %p1, %dead_store ], [ %p2, %entry ]
store i8 2, i8* %p3
ret i8* %p3

}

If not, is there any plans or prototype which can handle it? Thanks.

Currently we do not phi-translate the location of the 'killing def' and hence do not eliminate the store in this case. I haven't thought too much about it so far, but I think doing the phi translation of the 'killing loc' should not be too hard. It might be as simple as adjusting the ToCheck set to contain a pair (Access to check, Phi-translated DefLoc) and do phi translation when we queue the incoming defs for MemoryPhis (https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L2284)

I won't have time to look into this in the near future unfortunately, as I am mainly focused on getting things in good shape to enable DSE & MemorySSA by default. It might be good to file a bug report so this opportunity does not drop off our radar. If anyone is interested in giving implementing it a try, even better :)

[ebrevnov]

I won't have time to look into this in the near future unfortunately, as I am mainly focused on getting things in good shape to enable DSE & MemorySSA by default. It might be good to file a bug report so this opportunity does not drop off our radar. If anyone is interested in giving implementing it a try, even better :)

Florian, thank you for quick feedback. I prototyped phi translation approach and it does work on the posted test case. Unfortunately, it fails on a bit more complicated case which I will take a look tomorrow. If I have something working reasonably well in the end I will share it.

[fhahn]

In D72148#2242301, @ebrevnov wrote:

I won't have time to look into this in the near future unfortunately, as I am mainly focused on getting things in good shape to enable DSE & MemorySSA by default. It might be good to file a bug report so this opportunity does not drop off our radar. If anyone is interested in giving implementing it a try, even better :)

Florian, thank you for quick feedback. I prototyped phi translation approach and it does work on the posted test case. Unfortunately, it fails on a bit more complicated case which I will take a look tomorrow. If I have something working reasonably well in the end I will share it.

That's great! There are some changes to how we find MemoryDefs that may be killed by a killing def, rGe717fdb0f155 and D86487. This might actually make things a bit easier, as we now fully control the traversal of the defining accesses.

[fhahn]

In D72148#2242386, @fhahn wrote:

In D72148#2242301, @ebrevnov wrote:

I won't have time to look into this in the near future unfortunately, as I am mainly focused on getting things in good shape to enable DSE & MemorySSA by default. It might be good to file a bug report so this opportunity does not drop off our radar. If anyone is interested in giving implementing it a try, even better :)

Florian, thank you for quick feedback. I prototyped phi translation approach and it does work on the posted test case. Unfortunately, it fails on a bit more complicated case which I will take a look tomorrow. If I have something working reasonably well in the end I will share it.

That's great! There are some changes to how we find MemoryDefs that may be killed by a killing def, rGe717fdb0f155 and D86487. This might actually make things a bit easier, as we now fully control the traversal of the defining accesses.

Hi @ebrevnov,

I just wanted to briefly check in to see if you made any progress on this or if you think it is worth adding a bug report to keep track of the improvement?

Cheers,
Florian

[ebrevnov]

Hi @ebrevnov,

I just wanted to briefly check in to see if you made any progress on this or if you think it is worth adding a bug report to keep track of the improvement?

Hi Florian,

I have a prototype which is able to handle my case. I can upload it to the phabricator for the reference. It's based on about month old sources because if I rebase to newer things stop working. Another missing piece is caching results of phi translation. In the current version phi translation is done from scratch for each new memory access. It shouldn't be hard to restructure the code to reuse phi translated address from "previous" memory access.

Thanks
Evgeniy

[fhahn]

In D72148#2286883, @ebrevnov wrote:

Hi @ebrevnov,

I just wanted to briefly check in to see if you made any progress on this or if you think it is worth adding a bug report to keep track of the improvement?

Hi Florian,

I have a prototype which is able to handle my case. I can upload it to the phabricator for the reference. It's based on about month old sources because if I rebase to newer things stop working. Another missing piece is caching results of phi translation. In the current version phi translation is done from scratch for each new memory access. It shouldn't be hard to restructure the code to reuse phi translated address from "previous" memory access.

Yeah there have been some substantial changes to the way we find the candidates to remove, but I think the same idea should still apply. It would be ideal to update & rebase the patch, but if you won't have time to do so it would be great if you could share the older version regardless.

[ebrevnov]

Yeah there have been some substantial changes to the way we find the candidates to remove, but I think the same idea should still apply. It would be ideal to update & rebase the patch, but if you won't have time to do so it would be great if you could share the older version regardless.

Rebased and uploaded here https://reviews.llvm.org/D90095

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 // traversal.  Doing so would be pretty trivial.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"

 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
-#include "llvm/IR/InstIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"

 // that do not alias. WalkType::Bad indiciates that the walk hit one of the
 // following:
 //  * An aliasing MemoryUse (read).
 //  * A MemoryPHI that comes before Current.
 //  * Multiple MemoryDefs, which indicates a split in the control flow.
 WalkResult getNextMemoryDef(MemoryAccess *Current, MemoryLocation DefLoc,
                             Instruction *DefObj, bool DefVisibleToCaller,
                             int ScanLimit, AliasAnalysis &AA,
-                            const TargetLibraryInfo &TLI, DominatorTree &DT) {
+                            const TargetLibraryInfo &TLI, DominatorTree &DT,
+                            DenseMap<BasicBlock *, unsigned> &PostOrderMap) {
   if (--ScanLimit < 0)
     return {WalkType::Bad, nullptr};
 
   MemoryAccess *NextAccess = nullptr;
   // Scan the uses to see if we have a single interesting MemoryAccess.
   for (Use &U : Current->uses()) {
     MemoryAccess *UseAccess = cast<MemoryAccess>(U.getUser());
-    // Bail out on MemoryPhis for now.
-    if (isa<MemoryPhi>(UseAccess))
+
+    // For MemoryPhis, bail out if we already found a NextAccess or if the
+    // post-order number of the MemoryPhi's block is greater or equal than the
+    // number of the current access. This ensures we do not visit accesses that
+    // may be executed before the current access.
+    if (isa<MemoryPhi>(UseAccess)) {
+      if (NextAccess || PostOrderMap[UseAccess->getBlock()] >=
+                            PostOrderMap[Current->getBlock()])
         return {WalkType::Bad, nullptr};
+      NextAccess = UseAccess;
+      continue;
+    }
 
     Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
     LLVM_DEBUG(dbgs() << "   Checking use " << *UseInst << "\n");
     // We can remove the dead stores, irrespective of the fence and its ordering
     // (release/acquire/seq_cst). Fences only constraints the ordering of
     // already visible stores, it does not make a store visible to other
     // threads. So, skipping over a fence does not change a store from being
     // dead.
     if (isa<FenceInst>(UseInst))
       continue;
 
     // We cannot eliminate stores to locations visible to the caller across
     // throwing instructions. We can also eliminate stores across throwing calls
     // for alloc-like objects that do not escape before the current access.
     if (UseInst->mayThrow() && DefVisibleToCaller) {
       if (!DefObj ||
           (!isAllocLikeFn(DefObj, &TLI) ||
            PointerMayBeCapturedBefore(DefObj, false, true, UseInst, &DT)))
         return {WalkType::Bad, nullptr};
     }
 
     // Skip intrinsics that do not really read or modify memory.
     if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess))) {
       if (isa<MemoryDef>(UseAccess))
         NextAccess = UseAccess;
       continue;
     }
 
     // Uses which may read the original MemoryDef mean we cannot eliminate the
     // original MD. Stop walk.
     if (isReadClobber(DefLoc, UseInst, AA, TLI, DT))
       return {WalkType::Bad, nullptr};
 
     if (isa<MemoryUse>(UseAccess)) {
       // Skip non-aliasing MemoryUses.
       continue;
     }
 
     // Multiple definitions, bail out.
     if (NextAccess)
       return {WalkType::Bad, nullptr};
     NextAccess = UseAccess;
   }
 
   // If we found a next MemoryAccess, we are done if it clobbers the original
   // def or it is an unrelated MemoryAccess and we continue the walk starting at
   // NextAccess.
   if (NextAccess) {
-    assert(isa<MemoryDef>(NextAccess) && "Only MemoryDefs supported for now");
-
-    if (!isNoopIntrinsic(cast<MemoryUseOrDef>(NextAccess))) {
-      if (isWriteClobber(DefLoc,
-                         cast<MemoryUseOrDef>(NextAccess)->getMemoryInst(), AA,
-                         TLI, DT))
-        return {WalkType::Next, cast<MemoryDef>(NextAccess)};
+    if (auto *NextDef = dyn_cast<MemoryDef>(NextAccess)) {
+      if (!isNoopIntrinsic(NextDef)) {
+        if (isWriteClobber(DefLoc, NextDef->getMemoryInst(), AA, TLI, DT)) {
+          return {WalkType::Next, NextDef};
+        }
       }
+    }
+    assert(isa<MemoryDef>(NextAccess) || isa<MemoryPhi>(NextAccess));
     return getNextMemoryDef(NextAccess, DefLoc, DefObj, DefVisibleToCaller,
-                            ScanLimit, AA, TLI, DT);
+                            ScanLimit, AA, TLI, DT, PostOrderMap);
   }
 
   // No aliasing definition found, bail out.
   return {WalkType::Bad, nullptr};
 }
 
 // Delete dead memory defs
 void deleteDeadInstruction(Instruction *SI, InstOverlapIntervalsTy &IOL,
while (!NowDeadInsts.empty()) {
     // Remove the Instruction from MSSA and IOL
     if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
       Updater.removeMemoryAccess(MA);
       if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
         SkipStores.insert(MD);
       }
     }
     IOL.erase(DeadInst);
 
     // Remove it's operands
     for (Use &O : DeadInst->operands())
       if (Instruction *OpI = dyn_cast<Instruction>(O)) {
         O = nullptr;
         if (isInstructionTriviallyDead(OpI, &TLI))
           NowDeadInsts.push_back(OpI);
       }
 
     DeadInst->eraseFromParent();
bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
   // A map of interval maps representing partially-overwritten value parts
   InstOverlapIntervalsTy IOL;
   // Keep track of all of the objects that are invisible to the caller until the
   // function returns.
   SmallSetVector<const Value *, 16> InvisibleToCaller;
   // Keep track of blocks with throwing instructions not modeled in MemorySSA.
   SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
 
-  // Collect blocks with throwing instructions not modeled in MemroySSA and
-  // alloc-like objects.
-  for (Instruction &I : instructions(F)) {
+  // Post-order numbers for basic blocks in the function.
+  DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
+  unsigned PO = 0;
+  // Collect blocks with throwing instructions, alloc-like objects and
+  // post-order numbers for basic blocks.
+  for (BasicBlock *BB : post_order(&F)) {
+    PostOrderNumbers[BB] = PO++;
+    for (Instruction &I : *BB) {
       if (I.mayThrow() && !MSSA.getMemoryAccess(&I))
         ThrowingBlocks.insert(I.getParent());
 
       auto *MD = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(&I));
       if (MD && hasAnalyzableMemoryWrite(&I, TLI) && isRemovable(&I))
         Stores.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)))
         InvisibleToCaller.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())
       InvisibleToCaller.insert(&AI);
 
   // For each store:
   while (!Stores.empty()) {
Instruction *DefObj =
         const_cast<Instruction *>(dyn_cast<Instruction>(SILocUnd));
     bool LocVisibleToCaller = !InvisibleToCaller.count(SILocUnd);
 
     LLVM_DEBUG(dbgs() << "Trying to eliminate " << *SI << "\n");
 
     // Walk MemorySSA forward to find a MemoryDef that kills SI.
     WalkResult Next;
     while ((Next = getNextMemoryDef(SIMD, SILoc, DefObj, LocVisibleToCaller,
-                                    MemorySSAScanLimit, AA, TLI, DT))) {
+                                    MemorySSAScanLimit, AA, TLI, DT,
+                                    PostOrderNumbers))) {
       MemoryAccess *NextAccess = Next.Next;
       LLVM_DEBUG(dbgs() << " Checking " << *NextAccess << "\n");
       MemoryDef *ND = dyn_cast<MemoryDef>(NextAccess);
       Instruction *NI = ND->getMemoryInst();
       LLVM_DEBUG(dbgs() << "  def " << *NI << "\n");
 
       if (!hasAnalyzableMemoryWrite(NI, TLI))
         break;

llvm/test/Transforms/DeadStoreElimination/MSSA/memoryssa-debugcounter.ll

 ; SKIP-2-NEXT:    br label [[BB3]]
 ; SKIP-2:       bb3:
 ; SKIP-2-NEXT:    store i32 0, i32* [[Q:%.*]]
 ; SKIP-2-NEXT:    store i32 0, i32* [[Q]]
 ; SKIP-2-NEXT:    store i32 0, i32* [[P]]
 ; SKIP-2-NEXT:    ret void
 ;
 ; COUNT-1-LABEL: @test2(
-; COUNT-1-NEXT:    store i32 1, i32* [[P:%.*]]
 ; COUNT-1-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; COUNT-1:       bb1:
 ; COUNT-1-NEXT:    br label [[BB3:%.*]]
 ; COUNT-1:       bb2:
 ; COUNT-1-NEXT:    br label [[BB3]]
 ; COUNT-1:       bb3:
 ; COUNT-1-NEXT:    store i32 0, i32* [[Q:%.*]]
-; COUNT-1-NEXT:    store i32 0, i32* [[P]]
+; COUNT-1-NEXT:    store i32 0, i32* [[Q]]
+; COUNT-1-NEXT:    store i32 0, i32* [[P:%.*]]
 ; COUNT-1-NEXT:    ret void
 ;
 ; COUNT-0-LABEL: @test2(
 ; COUNT-0-NEXT:    store i32 1, i32* [[P:%.*]]
 ; COUNT-0-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; COUNT-0:       bb1:
 ; COUNT-0-NEXT:    br label [[BB3:%.*]]
 ; COUNT-0:       bb2:
 ; COUNT-0-NEXT:    br label [[BB3]]
 ; COUNT-0:       bb3:
 ; COUNT-0-NEXT:    store i32 0, i32* [[Q:%.*]]
 ; COUNT-0-NEXT:    store i32 0, i32* [[Q]]
 ; COUNT-0-NEXT:    store i32 0, i32* [[P]]
 ; COUNT-0-NEXT:    ret void
 ;
 ; SKIP-1-COUNT-1-LABEL: @test2(
+; SKIP-1-COUNT-1-NEXT:    store i32 1, i32* [[P:%.*]]
 ; SKIP-1-COUNT-1-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; SKIP-1-COUNT-1:       bb1:
 ; SKIP-1-COUNT-1-NEXT:    br label [[BB3:%.*]]
 ; SKIP-1-COUNT-1:       bb2:
 ; SKIP-1-COUNT-1-NEXT:    br label [[BB3]]
 ; SKIP-1-COUNT-1:       bb3:
 ; SKIP-1-COUNT-1-NEXT:    store i32 0, i32* [[Q:%.*]]
-; SKIP-1-COUNT-1-NEXT:    store i32 0, i32* [[Q]]
-; SKIP-1-COUNT-1-NEXT:    store i32 0, i32* [[P:%.*]]
+; SKIP-1-COUNT-1-NEXT:    store i32 0, i32* [[P]]
 ; SKIP-1-COUNT-1-NEXT:    ret void
 ;
   store i32 1, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   br label %bb3
 bb3:
   store i32 0, i32* %Q
   store i32 0, i32* %Q
   store i32 0, i32* %P
   ret void
 }

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

 ; CHECK-NEXT:  block1:
 ; CHECK-NEXT:    [[SV:%.*]] = alloca i32
 ; CHECK-NEXT:    br label [[BLOCK2:%.*]]
 ; CHECK:       block2:
 ; CHECK-NEXT:    store i32 20, i32* [[SV]]
 ; CHECK-NEXT:    invoke void @f()
 ; CHECK-NEXT:    to label [[BLOCK3:%.*]] unwind label [[CATCH_DISPATCH:%.*]]
 ; CHECK:       block3:
-; CHECK-NEXT:    store i32 30, i32* [[SV]]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       catch.dispatch:
 ; CHECK-NEXT:    [[CS1:%.*]] = catchswitch within none [label %catch] unwind label [[CLEANUP:%.*]]
 ; CHECK:       catch:
 ; CHECK-NEXT:    [[C:%.*]] = catchpad within [[CS1]] []
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[SV]]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       cleanup:

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

 end:
   ret void
 }
 
 
 define void @test14(i32* noalias %P) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[FOR:%.*]]
 ; CHECK:       for:
-; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i32 1, i32* %P
   br label %for
 for:
   store i32 0, i32* %P
   br i1 false, label %for, label %end
 end:
   ret void
 }
 
 define void @test18(i32* noalias %P) {
 ; CHECK-LABEL: @test18(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR:%.*]]
+; CHECK:       for:
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
+; CHECK-NEXT:    store i32 2, i32* [[P]]
+; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  store i32 0, i32* %P
+  br label %for
+for:
+  store i32 1, i32* %P
+  %x = load i32, i32* %P
+  store i32 2, i32* %P
+  br i1 false, label %for, label %end
+end:
+  ret void
+}
+
+
+define void @test18_partial(i32* noalias %P) {
+; CHECK-LABEL: @test18_partial(
+; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[P2:%.*]] = bitcast i32* [[P:%.*]] to i8*
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br label [[FOR:%.*]]
 ; CHECK:       for:
 ; CHECK-NEXT:    store i8 1, i8* [[P2]]
 ; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P]]
 ; CHECK-NEXT:    store i8 2, i8* [[P2]]
 ; CHECK-NEXT:    br i1 false, label [[FOR]], label [[END:%.*]]

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

bb3:
   store i32 0, i32* %P
   ret void
 }
 
 define void @test5(i32* noalias %P) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    ret void
 ;
   br i1 true, label %bb1, label %bb2
 bb1:
   store i32 1, i32* %P
   br label %bb3
 bb2:
   store i32 1, i32* %P
   br label %bb3
 bb3:
   store i32 0, i32* %P
   ret void
 }
 
 define void @test8(i32* %P, i32* %Q) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 1, i32* [[Q:%.*]]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    ret void
 ;
   br i1 true, label %bb1, label %bb2
 bb1:
   store i32 1, i32* %P
   br label %bb3
 bb2:
   store i32 1, i32* %Q

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; XFAIL: *
 ; 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()
 
 define void @test6(i32* noalias %P) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]