[MemCpyOpt] implement multi BB stack-move optimization

[khei4]

Summary

This patch extends https://reviews.llvm.org/D153453 to muti-BB case, aims to remove memcpy like https://internals.rust-lang.org/t/the-way-to-see-how-memcpy-and-alloca-introduced-by-move-is-optimized/19148/4

Single-BB version was like the following

(1) The src is fully copied to dest by memcpy, memmove or store&load.
(2) src and dest are 1) static alloca, which is to avoid stacksave/stackrestore handling, 2) unescaped allocas.
(3) The dest has no Mod Ref except full-sized lifetime intrinsic and copy itself, from the alloca to the store.
(4) If the dest has no Mod => src has no Ref, dest has no Ref => src has no Mod from the store to the end of BB.

This patch changes the original single-BB patch's ModRef checking conditions (3) and (4) by using reachability and dominator tree query as the following

(3) Mod/Ref for dest doesn't exist if it's reachable to full-size copy
(4) All uses not post dominated by the full-size copy satisfies (dest-Mod NAND src-Ref) AND (dest-Ref NAND src-Mod),

NOTE: For above conditions, this is more conservative than pcwalton's live analysis approach, and we can transform if all execution passes have no conflict, like cache coherency for the src and dest. It's safe for unescaped static contexts, if any ref, after the other one's mod and before the self-full-size Mod. This Mod could be called Def like the original pcwalton's patch. To do this, need a liveness analysis like the original patch or similar things. Also, unescaped alloca and byval args have almost the same semantics, so we can extend the way also.

pre-commit test: https://reviews.llvm.org/D155422
compile-time regression: https://llvm-compile-time-tracker.com/compare.php?from=2975ccb4b06b3d3aedd86ab21729146e441521d7&to=83fcffd325e79dd89e2b932b053945f868659f56&stat=instructions:u

[khei4]

add

• Dom/PDomTree branches and rebased for instruction level nearst common pdom calculation https://reviews.llvm.org/D155420
• insertion for lifetime.end/start for above dom/pdom cases
• use isPotentiallyReachable for reachable query.

TODO: seems like conditions and/or implementation isn't sufficient to reduce loop example.

[khei4]

rebase

[khei4]

• do batch reachability checks
• change pm tests
• remove TODO comments

NOTE: loop fix might be another revision, but load/store should be erased.

[nikic]

This looks okay to me as a fairly conservative extension. Does requiring PDT have any impact on compile-time?

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1568 ↗

(On Diff #540931)

Hm, this return true doesn't seem right to me if it the instruction is inside a loop. I think we still need to perform the reachability check in this case.

1631 ↗

(On Diff #540931)

A possible issue here is that PDom could be a terminator, e.g. an invoke. In that case ++ will go past the end of the block. I think it would be fine to treat this case as if there is no PDom, as it's unlikely to occur in practice (generally, the pdom use will be in a lifetime intrinsic, which can't be a terminator).

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1631 ↗

(On Diff #540931)

Heh, looks like exactly this issue got reported here: https://reviews.llvm.org/D153453#inline-1503870 I failed to realize that this can already be an issue with the initial patch, not just this extension...

[khei4]

@nikic Thank you for the review! I'll handle the teminator problem on the single-BB first! I'll add tests and reopen it;)

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1631 ↗

(On Diff #540931)

Thank you! As you said exactly, I have forgotten to see it, implemented on pcwalton's patch.

[khei4]

address feedback

• terminator PostDominator handling
• PostDominator utility moving from https://reviews.llvm.org/D155420

TODO

• batch reachability checks for instructions
• more negative cases

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1650 ↗

(On Diff #542302)

This looks suspicious to me. Would getBlock() return nullptr, or already getIDom()?

[khei4]

apply feedback

• fix wrong handling for post-dominator insertion
• Instruction-level reachability checking
  • maybe better to implement a method in CFG analysis
• add LoopInfo Analysis to handle loop mod-ref reachability
  • I believe almost not so much regression for compile time. https://llvm-compile-time-tracker.com/compare.php?from=2975ccb4b06b3d3aedd86ab21729146e441521d7&to=83fcffd325e79dd89e2b932b053945f868659f56&stat=instructions:u
• rebased on added test for https://reviews.llvm.org/D155422

The primary unfinished case is the original pcwalton's _is_def suffix cases, which fully overwrite src/def after the copy. This inherently requires liveness-analysis kind things, but I think for safe Rust move cases, Rust reference property aliasing xor mutability doesn't allow so much case for that (maybe?). So I hope this might have a slight effect on Rust programs :) (Theoretically, I didn't see rustc-codegen so much...)

[khei4]

@nikic
Thank you for the review!

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1650 ↗

(On Diff #542302)

Hmm, certainly. So far, I'm also not sure about this behavior, for the current invoke example.
when PDom = %rv = invoke i32 @use_nocapture(ptr %src) to label %suc unwind label %unw

((*PDT)[PDom->getParent()]->getIDom() == nullptr) => 0
((*PDT)[PDom->getParent()]->getIDom()->getBlock() == nullptr) => 1

Something wrong might be on PDom. Anyway, I could handle both nullptr conservatively.

1568 ↗

(On Diff #540931)

Right! We need to use the batch BB reachability for instructions!

[khei4]

rebase for https://reviews.llvm.org/D153453 crash fix

[khei4]

rebase and a bailout for MemoryAccess creation on lifetime.end inserting for non-user post dominator.

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1598 ↗

(On Diff #548450)

Is this check needed? I would expect that this is covered by adding the successors to the reachability worklist. Then we shouldn't need LoopInfo.

1674 ↗

(On Diff #548450)

bb -> BB

1682 ↗

(On Diff #548450)

I don't get what you're doing here with AA. Why is this necessary now and wasn't needed in the single BB case?

[khei4]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1598 ↗

(On Diff #548450)

Hmm, you seem right. At least the current test results don't change. I could erase the LoopInfo!

1682 ↗

(On Diff #548450)

This was to know whether the post dominator has MemoryAccess on SrcAlloca.
If it has MemoryAccess, check whether it's terminator or not, and find the place to insert MemoryAccess.
If it's not, currently skipped because I can't know how to insert MemoryDef or MemoryPhi consistently with any post dominators.

[khei4]

apply feedback

• Remove LoopInfo
• fix comments

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1682 ↗

(On Diff #548450)

Based on D157979, you can pass nullptr as the defining access and use createMemoryAccessInBB with Begin insertion place (when inserting at start of block).

[khei4]

rebase for https://reviews.llvm.org/D153453 and https://reviews.llvm.org/D157979

[nikic]

It looks like a clang-format of the whole file snuck in.

[khei4]

It looks like a clang-format of the whole file snuck in.

Ah, ... sorry for the noise.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1682 ↗

(On Diff #548450)

Sounds great! Thank you! I'll handle it.

[khei4]

• remove unrelated clang-format things
• handle post dominator for each case 1) invoke, 2) user of SrcAlloca, 3) other.

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1682 ↗

(On Diff #548450)

Hm, I really don't like how we distinguish between pdom being a user and the start of a block here. I think it may be better if we explicitly distinguish these two cases during the analysis.

I had something like this in mind:

/// PDom is either an Instruction, or the start of a BasicBlock.
using PDom = PointerUnion<Instruction *, BasicBlock *>;
static PDom findNearestCommonPostDominator(PDom I1, PDom I2,
                                           PostDominatorTree *PDT) {
  auto GetParent = [](PDom I) {
    if (auto *BB = dyn_cast<BasicBlock *>(I))
      return BB;
    return cast<Instruction *>(I)->getParent();
  };
  BasicBlock *BB1 = GetParent(I1);
  BasicBlock *BB2 = GetParent(I2);
  if (BB1 == BB2) {
    if (isa<BasicBlock *>(I1))
      return I1;
    if (isa<BasicBlock *>(I2))
      return I2;
    return cast<Instruction *>(I1)->comesBefore(cast<Instruction *>(I2)) ? I2
                                                                         : I1;
  }
  BasicBlock *PDomBB = PDT->findNearestCommonDominator(BB1, BB2);
  if (!PDomBB)
    return nullptr;
  if (BB2 == PDomBB)
    return I2;
  if (BB1 == PDomBB)
    return I1;
  return PDomBB;
}

For Instruction * PDom you would use createMemoryAccesAfter, for BasicBlock * you would use createMemoryAccessInBB.

[khei4]

Thank you for the review!

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1682 ↗

(On Diff #548450)

Yeah, I agree, it seems better to define the insertion point type as you gave. Moreover, checking BB or not could erase the ModRef check!

[khei4]

Use UnionPointer for post-dominator finding and erase ModRefCheck after that.

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1434–1437 ↗

(On Diff #551153)

I think I got these the wrong way around.

If I1 is the start of the block, then I2 is either also the start of the block or comes later in it, so it post-dominates.

1571 ↗

(On Diff #551153)

Remove TODO?

1681 ↗

(On Diff #551153)

because

1687 ↗

(On Diff #551153)

And drop the else below.

[khei4]

• modify description, fix typo
• fix post-dominator
• rebase for tests

[khei4]

Thanks!

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1434–1437 ↗

(On Diff #551153)

Ah, thanks! This part only seems wrong(normal dominator rather than post). I added the test to check this, also.

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1582 ↗

(On Diff #551407)

I don't understand what this FIXME is about.

1667 ↗

(On Diff #551407)

nit: Space before (

1677 ↗

(On Diff #551407)

user -> a user

1434–1437 ↗

(On Diff #551153)

This is still the wrong way around (and your new test multi_bb_pdom_test0 does show it: The lifetime.end is before the final use).

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1685 ↗

(On Diff #551407)

This should use PDomB->getFirstInsertionPoint(). Can you add a test where we need to insert in a block with phi nodes? In that case, the insertion has to be after the phi nodes, not before.

[khei4]

apply feedbacks

• refine comments
• use getFirstInsertionPt

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1582 ↗

(On Diff #551407)

This meant adding the Instruction version isPotentiallyReachableFromMany (currently only for BasicBlocks) might be helpful. I copied the code from CFG.h. Although even for the BasicBlocks version, a user is only a few cases.

1685 ↗

(On Diff #551407)

Thanks! It seems right, I added a test.

1434–1437 ↗

(On Diff #551153)

Thanks! Sorry, I didn't notice the reverted change...

[nikic]

LGTM

[khei4]

rebased for test update

[nikic]

I think the patch description could use an update to focus more on what this patch changes (e.g. the static alloca condition is not new, and just one of many old conditions).

[khei4]

@nikic Thanks! I'll reduce the descriptions!

It seems like a sanitizer crash happened on the createMemoryAccessBefore again. https://lab.llvm.org/buildbot/#/builders/37/builds/24650 I'll revert first!

#4 0x000055b2d243cc22 llvm::MemorySSAUpdater::createMemoryAccessBefore(llvm::Instruction*, llvm::MemoryAccess*, llvm::MemoryUseOrDef*) (/b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang+++0x5d80c22)
#5 0x000055b2d4bb8be6 llvm::MemCpyOptPass::performStackMoveOptzn(llvm::Instruction*, llvm::Instruction*, llvm::AllocaInst*, llvm::AllocaInst*, unsigned long, llvm::BatchAAResults&) (/b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang+++0x84fcbe6)
#6 0x000055b2d4bb9714 llvm::MemCpyOptPass::processMemCpy(llvm::MemCpyInst*, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, false, false, void>, false, false>&) (.part.0) MemCpyOptimizer.cpp:0:0
#7 0x000055b2d4bbe301 llvm::MemCpyOptPass::iterateOnFunction(llvm::Function&) (/b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang+++0x8502301)

Edit) I'm now searching the failure, I also believe this is similar to the last user insertion patterns.

The reproducer is the case dominator doesn't have any memory access for src. As the following

define void @multi_bb_dom_test0(i1 %b) {
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  br i1 %b, label %bb0, label %bb1

bb0:
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  br label %bb2

bb1:
  store %struct.Foo { i32 40, i32 50, i32 60 }, ptr %src
  br label %bb2

bb2:
  call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %dest)
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false); 1
  %1 = call i32 @use_nocapture(ptr noundef nocapture %dest)

  ret void
}

I'll add a few tests and fix it.

[khei4]

implement and use findNearestCommonDominator for InsertionPt

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1434 ↗

(On Diff #553150)

Shouldn't this be I1?

[khei4]

tweak comment

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1434 ↗

(On Diff #553150)

In this case, I use BasicBlock to represent the terminator of the block, while it's first non-phi in the PDom. This might be confusing, so I commented on it just in time.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1434 ↗

(On Diff #553150)

Oh yeah, that makes sense.

[khei4]

https://lab.llvm.org/buildbot/#/builders/36/builds/37042

Hmm, seems like the assertion failed somehow. (Is this due to the DominatorTree update being forgotten somewhere?)
https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Support/GenericDomTree.h#L500

 gh -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG  -fno-exceptions -funwind-tables -fno-rtti -UNDEBUG -std=c++17 -MD -MT lib/Object/CMakeFiles/LLVMObject.dir/MachOObjectFile.cpp.o -MF lib/Object/CMakeFiles/LLVMObject.dir/MachOObjectFile.cpp.o.d -o lib/Object/CMakeFiles/LLVMObject.dir/MachOObjectFile.cpp.o -c /home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/llvm-project/llvm/lib/Object/MachOObjectFile.cpp
clang++: /home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:500: NodeT* llvm::DominatorTreeBase<NodeT, IsPostDom>::findNearestCommonDominator(NodeT*, NodeT*) const [with NodeT = llvm::BasicBlock; bool IsPostDom = false]: Assertion `NodeA && "A must be in the tree"' failed.
...
 #6 0x00007fffbaeddc90 __assert_fail_base (/lib64/libc.so.6+0x3dc90)
 #7 0x00007fffbaeddd34 __assert_fail (/lib64/libc.so.6+0x3dd34)
 #8 0x00000000131ae08c llvm::DominatorTreeBase<llvm::BasicBlock, false>::findNearestCommonDominator(llvm::BasicBlock*, llvm::BasicBlock*) const (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/clang+++0x131ae08c)
 #9 0x0000000017b08920 llvm::MemCpyOptPass::performStackMoveOptzn(llvm::Instruction*, llvm::Instruction*, llvm::AllocaInst*, llvm::AllocaInst*, unsigned long, llvm::BatchAAResults&)::'lambda0'(llvm::Instruction*, llvm::function_ref<bool (llvm::Instruction*)>)::operator()(llvm::Instruction*, llvm::function_ref<bool (llvm::Instruction*)>) const MemCpyOptimizer.cpp:0:0
#10 0x0000000017b09308 llvm::MemCpyOptPass::performStackMoveOptzn(llvm::Instruction*, llvm::Instruction*, llvm::AllocaInst*, llvm::AllocaInst*, unsigned long,

[nikic]

@khei4 This happens when one of the instructions is in an unreachable block (disconnected from the CFG and not part of the DT). Missing the special cases here: https://github.com/llvm/llvm-project/blob/e41d383440883fa2f87012b765fcc2d450f6fd55/llvm/lib/IR/Dominators.cpp#L350-L353

[khei4]

@nikic Thanks! fixed.

[nikic]

Is it necessary to handle this for the PDT case as well, or can it not happen there? (Maybe all blocks get connected to the virtual exit block there?)

[khei4]

Is it necessary to handle this for the PDT case, or can it not happen there? (Maybe all blocks get connected to the virtual exit block there?)

@nikic Thanks! It sounds like a good point! I couldn't follow completely, but I do believe so; DT's entry is PDT's leaves, so I guess we can calculate PDom if it's unreachable from entry, but I'll add the test for the case that contains a cycle unreachable from entry.

[khei4]

rebase for the test

[nikic]

LGTM

llvm/test/Transforms/MemCpyOpt/stack-move.ll

454–456

There are these weird ; 1 comments in some of the tests.

[khei4]

remove test noises

[bgraur]

@khei4 the last commit is causing again lots of false positive for tests executed under asan.

We (the google compilers team) got several tests with no asan findings when built before rG3a1409f93da32bf626f76257e0aac71716f2f67e that trigger stack-use-after-scope when built with this commit.

Coming up with a reproducer is pretty time consuming, could you please revert this until one is available?

[vitalybuka]

In D155406#4640773, @bgraur wrote:

@khei4 the last commit is causing again lots of false positive for tests executed under asan.

We (the google compilers team) got several tests with no asan findings when built before rG3a1409f93da32bf626f76257e0aac71716f2f67e that trigger stack-use-after-scope when built with this commit.

Coming up with a reproducer is pretty time consuming, could you please revert this until one is available?

reverted in efe8aa2e618122e8050af10cc5d6ad83f24ef557

If this optimization is critical, maybe you can split this patch in two?

1. BB stack-move optimization which strips all lifetime markers from src alloca
2. insert alloca on dst

Then we can continue related/revert patch 2 as needed.

[nikic]

Conceptually, this optimization can only cause false negatives with asan, not false positives. We'll need a reproducer to understand what's going wrong.

[vitalybuka]

In D155406#4641708, @nikic wrote:

Conceptually, this optimization can only cause false negatives with asan, not false positives. We'll need a reproducer to understand what's going wrong.

Yes, that's why I think that something is definitely wrong with lifetimes, so better to revert ASAP.

And I believe @joanahalili is working on reproducer. Let me know if I can help.

[khei4]

@vitalybuka @bgraur @joanahalili
Thank you for reporting this!

FWIW, this transformation itself ensures 

1. allocas are never captured on IR level. (This is the requirements for this transformation.)
2. newly inserted lifetime.start dominates all use of memory location, and inserted end post-dominates those.

So, at least on the IR level, I believe this doesn't introduce any problematic use for the memory location, but certainly, this changes the memory use of the original source code, and it may introduce the unexpected use of the address, out of the scope that original source code had, by inserting (post)dominating lifetime intrinsics. I assumed lifetime markers are just overwriting the memory location by undef values, and the original lifetime ranges (scope?) for the memory location could be changed by the optimization if we correctly attach lifetime intrinsics, but I think it was wrong for the asan, right? (I'm not sure about the actual false positive case, any concrete counter-example will be appreciated.)
I should have cared about the original lifetime to kindly introduce this optimization, as vitaly says https://reviews.llvm.org/D153453#4556386. I believe this optimization is effective practically e.g. for the Rust programs that introduce memcpy for move, so splitting the patch sounds reasonable.

Assuming that inserting the new lifetime marker(or use) for an address out of the original scope would be problematic for asan, I want to try to use the single range lifetime completely covered other one, as vitaly suggested, for the first step!

[khei4]

strip the src lifetime if the transform suceed

[khei4]

@vitalybuka Ah, sorry, I was confused and not sure what you said. Did you mean just stripping the src lifetime work?

In D155406#4641099, @vitalybuka wrote:

In D155406#4640773, @bgraur wrote:

@khei4 the last commit is causing again lots of false positive for tests executed under asan.

We (the google compilers team) got several tests with no asan findings when built before rG3a1409f93da32bf626f76257e0aac71716f2f67e that trigger stack-use-after-scope when built with this commit.

Coming up with a reproducer is pretty time consuming, could you please revert this until one is available?

reverted in efe8aa2e618122e8050af10cc5d6ad83f24ef557

If this optimization is critical, maybe you can split this patch in two?

1. BB stack-move optimization which strips all lifetime markers from src alloca
2. insert alloca on dst

Then we can continue related/revert patch 2 as needed.

[vitalybuka]

In D155406#4643864, @khei4 wrote:

@vitalybuka Ah, sorry, I was confused and not sure what you said. Did you mean just stripping the src lifetime work?

Yes.

1. First you land the MemCpyOpt patch which remove lifetime from the preserved alloca. (assuming perf improvement from lifetime markers is smaller then from MemCpyOpt)
2. Then you land another patch with "correct" lifetimes. Looks like this is most tricky part so we can iterate here.

We have preliminary repro, which I will share by tomorrow.

But I still recommend to split the patch as above. Even with repro, I would not be surprised we hit another case and have to revert.

In D155406#4641099, @vitalybuka wrote:

In D155406#4640773, @bgraur wrote:

@khei4 the last commit is causing again lots of false positive for tests executed under asan.

We (the google compilers team) got several tests with no asan findings when built before rG3a1409f93da32bf626f76257e0aac71716f2f67e that trigger stack-use-after-scope when built with this commit.

Coming up with a reproducer is pretty time consuming, could you please revert this until one is available?

reverted in efe8aa2e618122e8050af10cc5d6ad83f24ef557

If this optimization is critical, maybe you can split this patch in two?

1. BB stack-move optimization which strips all lifetime markers from src alloca
2. insert alloca on dst

Then we can continue related/revert patch 2 as needed.

[vitalybuka]

Yes, like this.

LGTM,

If you can wait a few hours I try the patch on our internal code.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1611 ↗

(On Diff #556518)

Please drop TODO: Reconstruct merged lifetime markers.

[vitalybuka]

Please update llvm/test/Transforms/MemCpyOpt/lifetime-missing.ll

[khei4]

• update lifetime-missing.ll
• drop TODO comment.

[khei4]

@vitalybuka Thank you a lot! I'll try to land this in a day!

[vitalybuka]

If you can wait a few hours I try the patch on our internal code.

I don't see any regressions.

[vitalybuka]

Here is the issue on github with details: https://github.com/llvm/llvm-project/issues/66403

llvm/include/llvm/Transforms/Scalar/MemCpyOptimizer.h

 class Function;
 class Instruction;
 class LoadInst;
 class MemCpyInst;
 class MemMoveInst;
 class MemorySSA;
 class MemorySSAUpdater;
 class MemSetInst;
+class PostDominatorTree;
 class StoreInst;
 class TargetLibraryInfo;
 class Value;
 
 class MemCpyOptPass : public PassInfoMixin<MemCpyOptPass> {
   TargetLibraryInfo *TLI = nullptr;
   AAResults *AA = nullptr;
   AssumptionCache *AC = nullptr;
   DominatorTree *DT = nullptr;
+  PostDominatorTree *PDT = nullptr;
   MemorySSA *MSSA = nullptr;
   MemorySSAUpdater *MSSAU = nullptr;
 
 public:
   MemCpyOptPass() = default;
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for the old PM.
   bool runImpl(Function &F, TargetLibraryInfo *TLI, AAResults *AA,
-               AssumptionCache *AC, DominatorTree *DT, MemorySSA *MSSA);
+               AssumptionCache *AC, DominatorTree *DT, PostDominatorTree *PDT,
+               MemorySSA *MSSA);
 
 private:
   // Helper functions
   bool processStore(StoreInst *SI, BasicBlock::iterator &BBI);
   bool processStoreOfLoad(StoreInst *SI, LoadInst *LI, const DataLayout &DL,
                           BasicBlock::iterator &BBI);
   bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
   bool processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI);

llvm/test/Transforms/MemCpyOpt/stack-move.ll

bb1:
   %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   br label %bb2
 
 bb2:
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
   ret void
 }
 
+; TODO: merge allocas for multi basicblocks, s.t. all copy-dominated
 define ptr @multi_bb_loop(i32 %n) {
 ; CHECK-LABEL: define ptr @multi_bb_loop
 ; CHECK-SAME: (i32 [[N:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[NLT1:%.*]] = icmp slt i32 [[N]], 1
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 8
 ; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 8
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[SRC]])
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[DEST]])
loop_body:
   store i32 %new_i, ptr %dest
   %igtn = icmp sgt i32 %new_i, %n
   br i1 %igtn, label %loop_exit, label %loop_body
 
 loop_exit:
   ret ptr %dest
 }
 
+
+; TODO: merge allocas for multi basicblocks s.t. copy unreachable 
+define void @multi_bb_unreachable_modref(i1 %b0) {
+; CHECK-LABEL: define void @multi_bb_simple_br
+; CHECK-SAME: (i1 [[B:%.*]]) {
+; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
+; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[DEST]])
+; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
+; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
+; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
+; CHECK:       bb0:
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr nocapture [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr nocapture [[DEST]])
+; CHECK-NEXT:    ret void
+;
+  %src = alloca %struct.Foo, align 4
+  %dest = alloca %struct.Foo, align 4
+  call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %src)
+  call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %dest)
+  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
+  %1 = call i32 @use_nocapture(ptr noundef nocapture %src)
+  br i1 %b0, label %bb0, label %exit
+
+exit:
+  %3 = call i32 @use_nocapture(ptr noundef nocapture %src)
+  ret void
+
+bb0:
+  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)
+  call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
+  call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
+  ret void
+}
+
+
+; TODO: merge allocas for multi basicblocks s.t. copy unreachable 
+; the case copy isn't dominate
+define void @multi_bb_non_dominated(i1 %b0, i1 %b1) {
+; CHECK-LABEL: define void @multi_bb_simple_br
+; CHECK-SAME: (i1 [[B:%.*]]) {
+; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
+; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[DEST]])
+; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
+; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
+; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
+; CHECK:       bb0:
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr nocapture [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr nocapture [[DEST]])
+; CHECK-NEXT:    ret void
+;
+  %src = alloca %struct.Foo, align 4
+  %dest = alloca %struct.Foo, align 4
+  call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %src)
+  call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %dest)
+  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
+  %1 = call i32 @use_nocapture(ptr noundef nocapture %src)
+  br i1 %b0, label %bb0, label %bb1
+
+bb0:
+  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)
+  br %bb2
+
+bb1:
+  %3 = call i32 @use_nocapture(ptr noundef nocapture %src)
+  %4 = call i32 @use_writeonly(ptr noundef nocapture %dest)
+  br %bb2
+
+bb2:
+  %5 = call i32 @use_nocapture(ptr noundef nocapture %src)
+  call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
+  call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
+  ret void
+}
+
 ; Optimization failures follow:
 
 ; Tests that dynamically-sized allocas are never merged.
 define void @dynamically_sized_alloca(i64 %i) {
 ; CHECK-LABEL: define void @dynamically_sized_alloca
 ; CHECK-SAME: (i64 [[I:%.*]]) {
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca i8, i64 [[I]], align 4
 ; CHECK-NEXT:    [[DEST:%.*]] = alloca i8, i64 [[I]], align 4