[DSE] Lift post-dominance restriction.

[fhahn]

Summary

To eliminate a store, we must ensure that it is not accessed before the
killing def on any path to a function exit. Currently we use
post-dominance to ensure that the killing def is executed on each path
from the killed def. But this excludes cases where there are no other
reads before another overwriting def on other paths. An example can be
found below. The first store (store i32 1, i32* %P) is dead, but neither
of the killing stores post-dominate it.

This patch adds support for such cases in a relatively straight-forward
way. When checking for read clobbers, we already traverse explore all
uses. If there are any reads before clobbering writes along any path to
an exit, we will check them. We can stop adding uses to the worklist for
MemoryDefs that completely overwrite the original location.

The only remaining problem is accesses after returning from the
function. But I think we can make those reads explicit in the MemorySSA
by introducing an additonal MemoryUse that clobbers all locations
visible to the caller at each exit. With those additional MemoryUses,
the existing algorithms should handle those cases naturally as well.

Currently the patch uses a hack to create those MemoryUses: it just
introduces a readonly function call at the end of each function and
treats it as clobbering all objects may visible to the caller. If the
solution makes sense, I'll find a proper solution for the hack.

define void @test4(i32* noalias %P, i1 %c1) {

store i32 1, i32* %P
br i1 %c1, label %bb1, label %bb2

bb1:

store i32 0, i32* %P
br label %bb5

bb2:

store i32 3, i32* %P
br label %bb5

bb5:

call void @use(i32* %P)
ret void

}

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

[efriedma]

Currently the patch uses a hack to create those MemoryUses: it just introduces a readonly function call at the end of each function

I'm not deeply familiar with the MemorySSA datastructures, but that makes sense. I'm trying to think if any other passes care, though. I can't come up with anything off the top of my head, but maybe I'm forgetting something.

[fhahn]

In D73763#1852269, @efriedma wrote:

Currently the patch uses a hack to create those MemoryUses: it just introduces a readonly function call at the end of each function

I'm not deeply familiar with the MemorySSA datastructures, but that makes sense. I'm trying to think if any other passes care, though. I can't come up with anything off the top of my head, but maybe I'm forgetting something.

Currently the pass cleans up the artificial uses it introduces at the end, so other passes should not be impacted, unless I am missing something. The fact that they only alias objects visible to the caller after the function returns is only modelled directly in DSE and leaving them around could potentially slightly pessimize other passes.

[fhahn]

Rebase after latest updates to earlier change.

[fhahn]

Ping. Rebased after D72700 landed.

[fhahn]

ping

[fhahn]

ping

[Tyker]

this seems like a great approach to me.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1615

the comment seems outdated.
i think that with this patch dominating will not be true anymore.
and MemoryPHI seems to not cause a bail out.

[jdoerfert]

Disclaimer: I haven't looked at the approach here.
Have you seen the MustBeExecutedContextExplorer and the path exploration it allows (D65593)?
Sounds like this might actually be applicable here. If the chosen approach is superior or more natural feel free to say so.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1510

I'm not sure this is allowed in a function pass.

[fhahn]

Rebased, update comment.

In D73763#1899610, @jdoerfert wrote:

Disclaimer: I haven't looked at the approach here.
Have you seen the MustBeExecutedContextExplorer and the path exploration it allows (D65593)?
Sounds like this might actually be applicable here. If the chosen approach is superior or more natural feel free to say so.

We use MemorySSA traversals here, which allows us to only check the relevant linked memory instructions, without needing to explore the CFG. I had a brief look at MustExecute and I think the MemorySSA traversal is better suited to the problem at hand, as MemorySSA directly links the 'interesting' instructions (although I might miss something about MustExecute).

Also, for a killing store, we need to find an overwriting store that must execute when the other store executes. But we also have to check for any aliasing reads that may execute in between.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1510

Do you mean adding a new global or adding a function attribute to the added global?

Ideally function passes would only modify things in the function scope, but I think adding a new global is quite common, as most function passes that add new calls also may need to add a declaration of the called function.

As for adding the attribute, this needs to definitely change before submitting! I think we can either use an intrinsic (with the right attributes) or model it directly in MemorySSA, whatever option is preferred.

1615

Yes, I've rebased the patch and updated the comment as well.

[fhahn]

ping.

updated to use an intrinsic & fix a crash where AA with the new pass manager does return ModRef for our inserted read-only functions. As mentioned earlier, alternatively it could be modeled in MemorySSA directly, if preferered.

[jdoerfert]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1510

I thought there was a new function created, sorry.

I have the feeling this "exit read" should be part of MSSAs functionality (as it seems tied to MSSA and reusable) but I don't have a strong opinion about it.

[fhahn]

Ping. @asbirlea, what do you think about modeling reads at the end of the function? Should it be done directly in MSSA?

Rebased after landing MemoryPhi support, pre-committed new tests.

[fhahn]

ping

[asbirlea]

I don't think MemorySSA should be adding that generic intrinsic. If we need such a hack at least contain it to within the pass, not an analysis used throughout the pass pipeline.
[e-mail] for his thoughts on this too.

llvm/include/llvm/IR/Intrinsics.td

1160 ↗

(On Diff #251621)

I wouldn't use this name. As far as I see, it has nothing to do with MSSA, it's just a generic intrinsic that models a read-only function call.
This looks more akin to int_donothing_mayread.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1499–1500

Cleanup PDT if it's not used anymore?

1543

If this intrinsic is read only, then assert a MemoryUse was created?

[fhahn]

Thanks for taking a look!

Renamed intrinsic, removed PDT, added comment about why calls are inserted at the end of a function.

llvm/include/llvm/IR/Intrinsics.td

1160 ↗

(On Diff #251621)

Sounds good to me.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1499–1500

Yes, it should indeed be removed!

1543

There is some weird behavior with the new pass manager, in which AA fails to infer writenone for the newly added call to the intrinsic. I am not sure exactly what is going on there, I'll take a closer look if the intrinsic approach is the way forward.

[george.burgess.iv]

Thanks for working on this!

+1 to the general idea of "adding a read-everything intrinsic doesn't smell great," and a further +1 for containing it to only this pass if we do end up needing it.

This is the first time I'm glancing at this pass, so I'm going to err a bit on the side of overcommunication in hopes of making misunderstandings on my side more obvious. :)

I gather that getDomMemoryDef, given two defs A (Current) and B (KillingDef):

• Determines some Def/Phi that dominates A, C.
• Walks all of the MemoryAccesses that're transitively users of C, stopping at full overwrites of C + B.
• If any of those MemoryAccesses is a potential read of A, gives up. Otherwise, returns A

If we remove the postdom restriction, I'm uncertain about how this algo will scale. It used to be that all paths necessarily terminated at B, but now it looks like we'll potentially walk a ton more? e.g.,

bool branch(); // inaccessiblememonly

{
  // 1 = MemoryDef(LOE) -- DomAccess
  *a = 1;
  if (branch()) {
    // 2 = MemoryDef(1) -- The thing we want to replace it with
    *a = 2;
  }
  // 3 = MemoryPhi(2, 1)
  // Every Phi|Def below here is now walked (?)
}

To be clear, I'm not saying this walking isn't necessary; just that it now happens AFAICT.

In any case, the thing I see this new intrinsic standing in for is an oracle that responds to "here's the set of blocks we've observed complete overwrites in. Is there any way for us to exit this function without going through one of those blocks, starting from A->getBlock()?" This is an expensive problem, but I think we can simplify it substantially, *if* my comment about the extra walking above is correct. I'd imagine we could do it essentially by constructing a sort-of def frontier for each ret terminator. In other words, a DenseSet<MemoryAccess *> // (MemoryDef || MemoryPhi) where membership in the set == "there exists a path where this Def/Phi is the final Def/Phi before we hit a ret." Since lifting the postdom restriction makes us explore every Def/Phi reachable from C (stopping at full overwrites, and stopping after N steps), we should hopefully be able to consult that set in the getDomMemoryDef loop to get a similar effect to the fake read-everything calls?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1615

(did this update get dropped accidentally? This comment still appears to say "Find a MemoryDef, ...")

1668

tangential to this patch: should we be ignoring Us which are MemoryDefs whose only Use of Acc is as their getOptimized() operand? Without that, it's not immediately obvious to me how we aren't overly conservative in situations like:

{
  // 1 = MemoryDef(LOE) -- this is DomAccess
  *a = 1;
  // 2 = MemoryDef(1)
  *b = 2;
  // 3 = MemoryDef(2) -- this is the obvious kill
  *a = 3;
  // 4 = MemoryDef(3) (optimized to 2)
  *c = 4;
  // MemoryUse(4) -- AA says MayAlias for `(d, a)`, so `isReadClobber()` should be `true` if we visit this?
  if (*d) {
    // ...
  }
}

[fhahn]

In D73763#1951432, @george.burgess.iv wrote:

Thanks for working on this!

+1 to the general idea of "adding a read-everything intrinsic doesn't smell great," and a further +1 for containing it to only this pass if we do end up needing it.

Regarding the intrinsic, I am not sure if it is really needed, I guess it would be enough to check if we reached the end of our walk for each path. I'll try that tomorrow.

This is the first time I'm glancing at this pass, so I'm going to err a bit on the side of overcommunication in hopes of making misunderstandings on my side more obvious. :)

Thank you very much for taking a look!

I gather that getDomMemoryDef, given two defs A (Current) and B (KillingDef):

• Determines some Def/Phi that dominates A, C.
• Walks all of the MemoryAccesses that're transitively users of C, stopping at full overwrites of C + B.
• If any of those MemoryAccesses is a potential read of A, gives up. Otherwise, returns A

If we remove the postdom restriction, I'm uncertain about how this algo will scale. It used to be that all paths necessarily terminated at B, but now it looks like we'll potentially walk a ton more? e.g.,

bool branch(); // inaccessiblememonly

{
  // 1 = MemoryDef(LOE) -- DomAccess
  *a = 1;
  if (branch()) {
    // 2 = MemoryDef(1) -- The thing we want to replace it with
    *a = 2;
  }
  // 3 = MemoryPhi(2, 1)
  // Every Phi|Def below here is now walked (?)
}

To be clear, I'm not saying this walking isn't necessary; just that it now happens AFAICT.

Yes the summary above is correct. Removing the post-dominance restriction requires us to explore potentially much further unfortunately.

The main property we need to check is the following: given MemoryDefs A and B, where A dominates B and B completely overwrites A. We can eliminate A, if there are no access that may read A before B overwrites it. Only considering defs where B post-dominates A restricts the paths we have to check to the paths 'between' A and B. Without requiring post-dominance we have to check the property along all paths from A to the exit. In particular, the new case this allows to eliminate is when A is not read on any paths that do not go through B.

In any case, the thing I see this new intrinsic standing in for is an oracle that responds to "here's the set of blocks we've observed complete overwrites in. Is there any way for us to exit this function without going through one of those blocks, starting from A->getBlock()?" This is an expensive problem, but I think we can simplify it substantially, *if* my comment about the extra walking above is correct.

I think there are 2 cases to distinguish:

1. For accesses to non-alloca objects, this matches what the intrinsic achieves I think. We can only eliminate stores to objects that are visible after the function returns, if they are overwritten along all paths to the exit. So if we have determined a set of blocks that overwrite A (and there are no reads in between), we could check if all paths to the exit from A must go through one of the overwriting blocks. I think that matches your suggestion.
2. For objects that are not visible to the caller (e.g. alloca), the intrinsic achieves something slightly different: Given A and B as above, we can eliminate A, if there are no reads of A between A and any of the exits from A. We can stop walking any paths that contain overwrites of A.

I think 1. could be improved as you suggested. If we want to cover 2. I think we have to check all potentially aliasing access along all paths to the exit.

The approach I tried to follow to bring up MemoySSA-backed DSE is to add support for additional cases in smallish steps to have a baseline (and compile-time is controlled by cut-offs) and subsequently improve the parts that case issues in practice. For example, lift the post-dominance restriction with potentially excessive walking, followed by patches to implement the special handling for the non-alloca case as suggested and future performance improvements (e.g. there is plenty of potential for caching, like in D75025)? That would also allow to quantify the impact of improvements. What do you think?

[fhahn]

Avoid inserting calls by pre-computing set of the last memorydefs or phis before a function exit.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1668

Oh, the optimized access is also added to the uses of 2 = MemoryDef here? Yes that would be overly conservative. Is there a way to force MemorySSA to be optimized before we run DSE, for testing? I'll put up a separate fix.

[george.burgess.iv]

I think there are 2 cases to distinguish:

1. For accesses to non-alloca objects, this matches what the intrinsic achieves I think. We can only eliminate stores to objects that are visible after the function returns, if they are overwritten along all paths to the exit. So if we have determined a set of blocks that overwrite A (and there are no reads in between), we could check if all paths to the exit from A must go through one of the overwriting blocks. I think that matches your suggestion.

Sounds like what I was thinking, yeah.

For objects that are not visible to the caller (e.g. alloca), the intrinsic achieves something slightly different: Given A and B as above, we can eliminate A, if there are no reads of A between A and any of the exits from A. We can stop walking any paths that contain overwrites of A.

I'm confused about why allocas need special treatment. This new set that we're building is essentially a fast way to answer the question "are there potentially unknowable reads after this Def/Phi?" If we know memory (e.g., from an alloca) is unreadable outside of the function, I'd hope we can ignore the set entirely, like this patch is doing now? Baked into my suggestion was the assumption that we were already:

check[ing] all potentially aliasing access along all paths to the exit

...since I think the transitive User walking we're doing inside of getDomMemoryDef should accomplish that?

In any case, if you're confident that this works for #1, I'm content to move discussion about "why don't things work as they are now," to a patch that doesn't block this one.

The approach I tried to follow to bring up MemoySSA-backed DSE is to add support for additional cases in smallish steps to have a baseline (and compile-time is controlled by cut-offs) and subsequently improve the parts that case issues in practice. For example, lift the post-dominance restriction with potentially excessive walking, followed by patches to implement the special handling for the non-alloca case as suggested and future performance improvements (e.g. there is plenty of potential for caching, like in D75025)? That would also allow to quantify the impact of improvements. What do you think?

I like incremental approaches when they're possible, so I'm happy with this. :)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1492

that is defs or phis without any users that are defs or phis.

This isn't quite complete; consider:

void bar(); // inaccessiblememonly
void foo(int *a) {
  // 1 = MemoryDef(LOE)
  *a = 1;
  if (bar())
    return;
  // 2 = MemoryDef(1)
  *a = 2;
}

Despite having 2 as a User, we'd still want 1 to be in this set, since depending on the way the if goes, it's the last Def/Phi before the function ends

1668

Is there a way to force MemorySSA to be optimized before we run DSE, for testing?

I'm unsure offhand. @asbirlea would likely know if there is.

If there's not and you'd find it useful, a debugging-only pass that boils down to for (MemoryAccess *MA : Fn) { MSSA->getWalker()->getClobberingMemoryAccess(MA, {}); } should force that. We preoptimize Uses, but not Defs.

[fhahn]

In D73763#1956347, @george.burgess.iv wrote:

I think there are 2 cases to distinguish:

1. For accesses to non-alloca objects, this matches what the intrinsic achieves I think. We can only eliminate stores to objects that are visible after the function returns, if they are overwritten along all paths to the exit. So if we have determined a set of blocks that overwrite A (and there are no reads in between), we could check if all paths to the exit from A must go through one of the overwriting blocks. I think that matches your suggestion.

Sounds like what I was thinking, yeah.

For objects that are not visible to the caller (e.g. alloca), the intrinsic achieves something slightly different: Given A and B as above, we can eliminate A, if there are no reads of A between A and any of the exits from A. We can stop walking any paths that contain overwrites of A.

I'm confused about why allocas need special treatment. This new set that we're building is essentially a fast way to answer the question "are there potentially unknowable reads after this Def/Phi?" If we know memory (e.g., from an alloca) is unreadable outside of the function, I'd hope we can ignore the set entirely, like this patch is doing now? Baked into my suggestion was the assumption that we were already:

Ah right, I think I was not sure if your suggestion also applied to the alloca case in the previous comment.

IIUC, the additional set would be used for the non-alloca cases, as we have to ensure that there are overwrites along all paths to the exit. For allocas, we have to explore all access along all paths to function exits, as this patch currently does. What I meant to say in my previous comment was that I think we have to stick to the walking as in the patch, which is also what your last comment said, unless I am missing something :)

In any case, if you're confident that this works for #1, I'm content to move discussion about "why don't things work as they are now," to a patch that doesn't block this one.

The discussion so far has been extremely helpful, thanks! I think it would make sense to address the alloca/non-alloca separately. If you are happy with the direction, I would update this patch to only handle the alloca case (basically this patch modulo the intrinsic/LastDefOrPhi) and address the non-alloca in a subsequent patch.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1492

Of course, I remember why the intrinsic was so convenient to start with again! Anyways, I plan to split up the patch and probably look into using the suggested set straight away instead for the cases that required LastPhiOrDef.

[george.burgess.iv]

IIUC, the additional set would be used for the non-alloca cases, as we have to ensure that there are overwrites along all paths to the exit.

Yup!

For allocas, we have to explore all access along all paths to function exits, as this patch currently does. What I meant to say in my previous comment was that I think we have to stick to the walking as in the patch, which is also what your last comment said, unless I am missing something :)

Ah, I see. Yeah, agreed :)

If you are happy with the direction, I would update this patch to only handle the alloca case

SGTM

[fhahn]

In D73763#1964635, @george.burgess.iv wrote:

If you are happy with the direction, I would update this patch to only handle the alloca case

SGTM

I put up a patch that only handles the alloca (and alloca like non-escaping) case: D77736

I'll try to get an update on the second case as well soonish.

[vsapsai]

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

18

It would be great to update the comment to match the new IR, i.e., make b a function parameter instead of a local variable.

[fhahn]

I've put up D78932 which implements eliminating stores to objects that are visible to the caller along the lines of @george.burgess.iv's suggestion

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

18

Thanks will do when I submit the test change!

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
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
-#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.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"
bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
   return false;
 }
 
 struct DSEState {
   Function &F;
   AliasAnalysis &AA;
   MemorySSA &MSSA;
   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
   // function returns.
   SmallPtrSet<const Value *, 16> InvisibleToCaller;
   // 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;
+  // Set of the last MemoryDefs or MemoryPhis before a function exit, that is
+  // defs or phis without any users that are defs or phis.
+  SmallPtrSet<MemoryAccess *, 8> LastDefOrPhi;
 
   /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
   /// basic block.
   DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
 
   DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
-           PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
-      : F(F), AA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI) {}
+           const TargetLibraryInfo &TLI)
+      : F(F), AA(AA), MSSA(MSSA), DT(DT), TLI(TLI) {}
 
   static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
-                      DominatorTree &DT, PostDominatorTree &PDT,
-                      const TargetLibraryInfo &TLI) {
-    DSEState State(F, AA, MSSA, DT, PDT, TLI);
+                      DominatorTree &DT, const TargetLibraryInfo &TLI) {
+    DSEState State(F, AA, MSSA, DT, TLI);
+
     // Collect blocks with throwing instructions not modeled in MemorySSA and
     // alloc-like objects.
     unsigned PO = 0;
     for (BasicBlock *BB : post_order(&F)) {
       State.PostOrderNumbers[BB] = PO++;
       for (Instruction &I : *BB) {
-        if (I.mayThrow() && !MSSA.getMemoryAccess(&I))
+        MemoryAccess *MA = MSSA.getMemoryAccess(&I);
+        if (I.mayThrow() && !MA)
           State.ThrowingBlocks.insert(I.getParent());
 
-        auto *MD = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(&I));
+        auto *MD = dyn_cast_or_null<MemoryDef>(MA);
         if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
             hasAnalyzableMemoryWrite(&I, TLI) && isRemovable(&I))
           State.MemDefs.push_back(MD);
 
+        if (MA && (MD || isa<MemoryPhi>(MA)) && !any_of(MA->uses(), [](Use &U) {
+              User *Acc = U.getUser();
+              return isa<MemoryPhi>(Acc) || isa<MemoryDef>(Acc);
+            }))
+          State.LastDefOrPhi.insert(MA);
+
         // 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);
       }
     }
 
     // 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);
     return State;
   }
 
   Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
     if (!I->mayWriteToMemory())
       return None;
 
     if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
       return {MemoryLocation::getForDest(MTI)};
if (auto CS = CallSite(I)) {
       }
       return None;
     }
 
     return MemoryLocation::getOrNone(I);
   }
 
   /// Returns true if \p Use completely overwrites \p DefLoc.
-  bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *UseInst) const {
+  bool isMustWriteClobber(MemoryLocation DefLoc, Instruction *UseInst) const {
     // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
     // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
     // MemoryDef.
     if (!UseInst->mayWriteToMemory())
       return false;
 
     if (auto CS = CallSite(UseInst))
       if (CS.onlyAccessesInaccessibleMemory())
         return false;
 
     ModRefInfo MR = AA.getModRefInfo(UseInst, DefLoc);
-    // If necessary, perform additional analysis.
-    if (isModSet(MR))
-      MR = AA.callCapturesBefore(UseInst, DefLoc, &DT);
-
     Optional<MemoryLocation> UseLoc = getLocForWriteEx(UseInst);
     return isModSet(MR) && isMustSet(MR) &&
-           UseLoc->Size.getValue() >= DefLoc.Size.getValue();
+           (UseLoc->Size.hasValue() && DefLoc.Size.hasValue() &&
+            UseLoc->Size.getValue() >= DefLoc.Size.getValue());
+  }
+
+  bool isAccessibleAfterReturn(MemoryLocation Loc) const {
+    DataLayout DL = F.getParent()->getDataLayout();
+    const Value *UO = GetUnderlyingObject(Loc.Ptr, DL);
+    /// Maybe pre-compute
+    return !UO || InvisibleToCaller.find(UO) == InvisibleToCaller.end() ||
+           (!isa<AllocaInst>(UO) && PointerMayBeCaptured(UO, true, false));
   }
 
   /// 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 (auto CS = CallSite(UseInst)) {
       if (CS.onlyAccessesInaccessibleMemory())
         return false;
+    }
 
     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
+  // read access between them or on any other path to a function exit block. 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 DefVisibleToCaller,
                                            int &ScanLimit) const {
     MemoryAccess *DomAccess;
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.
       MemoryDef *DomDef = dyn_cast<MemoryDef>(DomAccess);
-      if ((DomDef && canSkipDef(DomDef, DefVisibleToCaller)) ||
-          !PDT.dominates(KillingDef->getBlock(), DomDef->getBlock())) {
+      if ((DomDef && canSkipDef(DomDef, DefVisibleToCaller))) {
         StepAgain = true;
         Current = DomDef->getDefiningAccess();
       }
 
     } while (StepAgain);
 
     LLVM_DEBUG({
       dbgs() << "  Checking for reads of " << *DomAccess;
       if (isa<MemoryDef>(DomAccess))
         dbgs() << " (" << *cast<MemoryDef>(DomAccess)->getMemoryInst() << ")\n";
     });
 
     SmallSetVector<MemoryAccess *, 32> WorkList;
     auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
       for (Use &U : Acc->uses())
         WorkList.insert(cast<MemoryAccess>(U.getUser()));
     };
     PushMemUses(DomAccess);
 
+    // TODO: Ideally we only compute it once, but only when required.
+    bool AccessibleAfterReturn = isAccessibleAfterReturn(DefLoc);
     // Check if DomDef may be read.
     for (unsigned I = 0; I < WorkList.size(); I++) {
       MemoryAccess *UseAccess = WorkList[I];
 
       LLVM_DEBUG(dbgs() << "   Checking use " << *UseAccess);
       if (--ScanLimit == 0) {
         LLVM_DEBUG(dbgs() << "  ...  hit scan limit\n");
         return None;
       }
 
       if (isa<MemoryPhi>(UseAccess)) {
+        if (LastDefOrPhi.find(UseAccess) != LastDefOrPhi.end() &&
+            AccessibleAfterReturn) {
+          LLVM_DEBUG(dbgs() << "  ... object accessible after return is not "
+                               "overwritten on a path to a function exit\n");
+          return None;
+        }
         PushMemUses(UseAccess);
         continue;
       }
 
       Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
       LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n");
 
       if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess))) {
for (unsigned I = 0; I < WorkList.size(); I++) {
       // miss cases like the following
       //   1 = Def(LoE) ; <----- DomDef stores [0,1]
       //   2 = Def(1)   ; (2, 1) = NoAlias,   stores [2,3]
       //   Use(2)       ; MayAlias 2 *and* 1, loads [0, 3].
       //                  (The Use points to the *first* Def it may alias)
       //   3 = Def(1)   ; <---- Current  (3, 2) = NoAlias, (3,1) = MayAlias,
       //                  stores [0,1]
       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
-        if (!isCompleteOverwrite(DefLoc, UseInst))
+        int64_t InstWriteOffset, DepWriteOffset;
+        auto CC = getLocForWriteEx(UseInst);
+        InstOverlapIntervalsTy IOL;
+
+        const DataLayout &DL = F.getParent()->getDataLayout();
+
+        if (!isMustWriteClobber(DefLoc, UseInst) ||
+            (CC &&
+             isOverwrite(DefLoc, *CC, DL, TLI, DepWriteOffset, InstWriteOffset,
+                         UseInst, IOL, AA, &F) != OW_Complete)) {
+          LLVM_DEBUG(dbgs() << "  ... found non-aliasing MemoryDef\n");
+          if (LastDefOrPhi.find(UseAccess) != LastDefOrPhi.end() &&
+              AccessibleAfterReturn) {
+            LLVM_DEBUG(dbgs() << "  ... object accessible after return is not "
+                                 "overwritten on a path to a function exit\n");
+            return None;
+          }
+
           PushMemUses(UseDef);
         }
       }
+    }
 
     // No aliasing MemoryUses of DomAccess found, DomAccess is potentially dead.
     return {DomAccess};
   }
 
   // Delete dead memory defs
   void deleteDeadInstruction(Instruction *SI) {
     MemorySSAUpdater Updater(&MSSA);
bool isDSEBarrier(Instruction *SI, MemoryLocation &SILoc,
     }
 
     return false;
   }
 };
 
 bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
                                   MemorySSA &MSSA, DominatorTree &DT,
-                                  PostDominatorTree &PDT,
                                   const TargetLibraryInfo &TLI) {
   const DataLayout &DL = F.getParent()->getDataLayout();
   bool MadeChange = false;
 
-  DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
+  DSEState State = DSEState::get(F, AA, MSSA, DT, TLI);
   // For each store:
   for (unsigned I = 0; I < State.MemDefs.size(); I++) {
     MemoryDef *KillingDef = State.MemDefs[I];
     if (State.SkipStores.count(KillingDef))
       continue;
     Instruction *SI = KillingDef->getMemoryInst();
     auto MaybeSILoc = State.getLocForWriteEx(SI);
     if (!MaybeSILoc) {

 //===----------------------------------------------------------------------===//
 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
 
   if (EnableMemorySSA) {
     MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
-    PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
-
-    if (!eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI))
+    if (!eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, TLI))
       return PreservedAnalyses::all();
   } else {
     MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
 
     if (!eliminateDeadStores(F, &AA, &MD, &DT, &TLI))
       return PreservedAnalyses::all();
   }
 
bool runOnFunction(Function &F) override {
 
     AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     const TargetLibraryInfo &TLI =
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
 
     if (EnableMemorySSA) {
       MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
-      PostDominatorTree &PDT =
-          getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
-
-      return eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
+      return eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, TLI);
     } else {
       MemoryDependenceResults &MD =
           getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
 
       return eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
     }
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
 
     if (EnableMemorySSA) {
-      AU.addRequired<PostDominatorTreeWrapperPass>();
       AU.addRequired<MemorySSAWrapperPass>();
-      AU.addPreserved<PostDominatorTreeWrapperPass>();
       AU.addPreserved<MemorySSAWrapperPass>();
     } else {
       AU.addRequired<MemoryDependenceWrapperPass>();
       AU.addPreserved<MemoryDependenceWrapperPass>();
     }
   }
 };
 
 } // end anonymous namespace
 
 char DSELegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false,
                     false)
 
 FunctionPass *llvm::createDeadStoreEliminationPass() {
   return new DSELegacyPass();
 }

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

 ;
 ; clang Debugify_Dead_Store_Elimination.cpp -Wno-c++11-narrowing -S \
 ;   -emit-llvm -O0 -w -Xclang -disable-O0-optnone -march=native -fdeclspec \
 ;   --target=x86_64-gnu-linux-unknown -Werror=unreachable-code -o -
 ;
 ; Where Debugify_Dead_Store_Elimination.cpp contains:
 ;
 ; 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
bb3:
   ret void
 }
 
 define void @test19(i32* noalias %P) {
 ; CHECK-LABEL: @test19(
 ; CHECK-NEXT:  entry:
 ; 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 true, 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:

 %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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; 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.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 define void @test19(i32* noalias %P) {
 ; CHECK-LABEL: @test19(
 ; CHECK-NEXT:  entry:
 ; 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 true, 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:

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; 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 @use(i32 *)
 
 define void @test4(i32* noalias %P, i1 %c1) {
 ; CHECK-LABEL: @test4(
-; 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:    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:
 ; CHECK-NEXT:    call void @use(i32* [[P]])
 ; CHECK-NEXT:    ret void
 ;

 
 bb5:
   call void @use(i32* %P)
   ret void
 }
 
 define void @test5(i32* noalias %P) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br i1 undef, label [[BB3:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    store i32 3, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    store i32 5, i32* [[P]]

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

bb2:
   br label %bb3
 bb3:
   store i32 0, i32* %P
   ret void
 }
 
 define void @test3(i32* noalias %P) {
 ; CHECK-LABEL: @test3(
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
;
   store i32 2, i32* %P
   store i32 3, i32* %Q
   %l = load i32, i32* %R
   ret i32 %l
 }
 
 define void @test9(i32* noalias %P) {
 ; CHECK-LABEL: @test9(
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   ret void
bb2:
   br label %bb3
 bb3:
   store i32 2, i32* %P
   ret void
 }
 
 define void @test10(i32* %P) {
 ; CHECK-LABEL: @test10(
-; 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:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   store i32 0, i32* %P
   br label %bb3
 bb2:
   ret void
 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
 ;
   %P = alloca i32
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   store i32 0, i32* %P
   br label %bb3
 bb2:
   ret void
 bb3:
   ret void
 }
 
 
 define void @test12(i32* %P) {
 ; CHECK-LABEL: @test12(
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    store i32 1, i32* [[P]]
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   store i32 1, i32* %P
   br label %bb3
 bb2:
   store i32 1, i32* %P
   ret void
 bb3:
   ret void
 }
 
 
 define void @test13(i32* %P) {
 ; CHECK-LABEL: @test13(
-; CHECK-NEXT:    store i32 0, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    store i32 1, i32* [[P]]
+; 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:    ret void
 ;
   store i32 0, i32* %P