[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

1633

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.

1704

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

1704

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

1704

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

1705

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

1633

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

1705

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.

[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

1624

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.

1702

bb -> BB

1710

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

1624

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

1710

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

1710

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

1710

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

1710

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

1710

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

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.

1596

Remove TODO?

1714

because

1720

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

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

1434–1437

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

1610

I don't understand what this FIXME is about.

1704

nit: Space before (

1714

user -> a user

[nikic]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1722

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

1434–1437

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

1610

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.

1722

Thanks! It seems right, I added a test.

[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

Shouldn't this be I1?

[khei4]

tweak comment

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1434

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

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

620

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

1678–1730

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/lib/Transforms/Scalar/MemCpyOptimizer.cpp

 #include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.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/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
   auto *LastDef =
       cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
   auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, nullptr, LastDef);
   MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
 
   return true;
 }
 
+using InsertionPt = PointerUnion<Instruction *, BasicBlock *>;
+/// Find the nearest Instruction or BasicBlock that dominates both I1 and
+/// I2.
+static InsertionPt findNearestCommonDominator(InsertionPt I1, InsertionPt I2,
+                                              DominatorTree *DT) {
+  auto GetParent = [](InsertionPt 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) {
+    // BasicBlock InsertionPt means the terminator.
+    if (isa<BasicBlock *>(I1))
+      return I2;
+    if (isa<BasicBlock *>(I2))
+      return I1;
+    return cast<Instruction *>(I1)->comesBefore(cast<Instruction *>(I2)) ? I1
+                                                                         : I2;
+  }
+  BasicBlock *DomBB = DT->findNearestCommonDominator(BB1, BB2);
+  if (BB2 == DomBB)
+    return I2;
+  if (BB1 == DomBB)
+    return I1;
+  return DomBB;
+}
+
+/// Find the nearest Instruction or BasicBlock that post-dominates both I1 and
+/// I2.
+static InsertionPt findNearestCommonPostDominator(InsertionPt I1,
+                                                  InsertionPt I2,
+                                                  PostDominatorTree *PDT) {
+  auto GetParent = [](InsertionPt 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) {
+    // BasicBlock InsertionPt means the first non-phi instruction.
+    if (isa<BasicBlock *>(I1))
+      return I2;
+    if (isa<BasicBlock *>(I2))
+      return I1;
+    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;
+}
+
 // Attempts to optimize the pattern whereby memory is copied from an alloca to
 // another alloca, where the two allocas don't have conflicting mod/ref. If
 // successful, the two allocas can be merged into one and the transfer can be
 // deleted. This pattern is generated frequently in Rust, due to the ubiquity of
 // move operations in that language.
 //
 // Once we determine that the optimization is safe to perform, we replace all
 // uses of the destination alloca with the source alloca. We also "shrink wrap"
LLVM_DEBUG(dbgs() << "Stack Move: Attempting to optimize:\n"
                     << *Store << "\n");
 
   // Make sure the two allocas are in the same address space.
   if (SrcAlloca->getAddressSpace() != DestAlloca->getAddressSpace()) {
     LLVM_DEBUG(dbgs() << "Stack Move: Address space mismatch\n");
     return false;
   }
 
-  // 1. Check that copy is full. Calculate the static size of the allocas to be
-  // merged, bail out if we can't.
+  // Check that copy is full with static size.
   const DataLayout &DL = DestAlloca->getModule()->getDataLayout();
   std::optional<TypeSize> SrcSize = SrcAlloca->getAllocationSize(DL);
   if (!SrcSize || SrcSize->isScalable() || Size != SrcSize->getFixedValue()) {
     LLVM_DEBUG(dbgs() << "Stack Move: Source alloca size mismatch\n");
     return false;
   }
   std::optional<TypeSize> DestSize = DestAlloca->getAllocationSize(DL);
   if (!DestSize || DestSize->isScalable() ||
       Size != DestSize->getFixedValue()) {
     LLVM_DEBUG(dbgs() << "Stack Move: Destination alloca size mismatch\n");
     return false;
   }
 
-  // 2-1. Check that src and dest are static allocas, which are not affected by
-  // stacksave/stackrestore.
-  if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca() ||
-      SrcAlloca->getParent() != Load->getParent() ||
-      SrcAlloca->getParent() != Store->getParent())
+  if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca())
     return false;
 
-  // 2-2. Check that src and dest are never captured, unescaped allocas. Also
-  // collect lifetime markers first/last users in order to shrink wrap the
-  // lifetimes, and instructions with noalias metadata to remove them.
+  // Check that src and dest are never captured, unescaped allocas. Also
+  // find the nearest common dominator and postdominator for all users in
+  // order to shrink wrap the lifetimes, and instructions with noalias metadata
+  // to remove them.
 
   SmallVector<Instruction *, 4> LifetimeMarkers;
-  Instruction *FirstUser = nullptr, *LastUser = nullptr;
+  InsertionPt Dom = nullptr, PDom = nullptr;
   SmallSet<Instruction *, 4> NoAliasInstrs;
 
   // Recursively track the user and check whether modified alias exist.
   auto IsDereferenceableOrNull = [](Value *V, const DataLayout &DL) -> bool {
     bool CanBeNull, CanBeFreed;
     return V->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
   };
 
while (!Worklist.empty()) {
         case UseCaptureKind::MAY_CAPTURE:
           return false;
         case UseCaptureKind::PASSTHROUGH:
           // Instructions cannot have non-instruction users.
           Worklist.push_back(cast<Instruction>(U.getUser()));
           continue;
         case UseCaptureKind::NO_CAPTURE: {
           auto *UI = cast<Instruction>(U.getUser());
-          if (DestAlloca->getParent() != UI->getParent())
-            return false;
-          if (!FirstUser || UI->comesBefore(FirstUser))
-            FirstUser = UI;
-          if (!LastUser || LastUser->comesBefore(UI))
-            LastUser = UI;
+          if (!Dom) {
+            PDom = Dom = UI;
+          } else {
+            Dom = findNearestCommonDominator(Dom, UI, DT);
+            if (PDom)
+              PDom = findNearestCommonPostDominator(PDom, UI, PDT);
+          }
           if (UI->isLifetimeStartOrEnd()) {
             // We note the locations of these intrinsic calls so that we can
             // delete them later if the optimization succeeds, this is safe
             // since both llvm.lifetime.start and llvm.lifetime.end intrinsics
             // practically fill all the bytes of the alloca with an undefined
             // value, although conceptually marked as alive/dead.
             int64_t Size = cast<ConstantInt>(UI->getOperand(0))->getSExtValue();
             if (Size < 0 || Size == DestSize) {
               LifetimeMarkers.push_back(UI);
               continue;
             }
           }
           if (UI->hasMetadata(LLVMContext::MD_noalias))
             NoAliasInstrs.insert(UI);
           if (!ModRefCallback(UI))
             return false;
         }
         }
       }
     }
     return true;
   };
 
-  // 3. Check that dest has no Mod/Ref, except full size lifetime intrinsics,
-  // from the alloca to the Store.
+  // Check that dest has no Mod/Ref, from the alloca to the Store, except full
+  // size lifetime intrinsics. And collect modref inst for the reachability
+  // check.
   ModRefInfo DestModRef = ModRefInfo::NoModRef;
   MemoryLocation DestLoc(DestAlloca, LocationSize::precise(Size));
+  SmallVector<BasicBlock *, 8> ReachabilityWorklist;
   auto DestModRefCallback = [&](Instruction *UI) -> bool {
     // We don't care about the store itself.
     if (UI == Store)
       return true;
     ModRefInfo Res = BAA.getModRefInfo(UI, DestLoc);
-    // FIXME: For multi-BB cases, we need to see reachability from it to
-    // store.
-    // Bailout if Dest may have any ModRef before Store.
-    if (UI->comesBefore(Store) && isModOrRefSet(Res))
+    DestModRef |= Res;
+    if (isModOrRefSet(Res)) {
+      // Instructions reachability checks.
+      // FIXME: adding the Instruction version isPotentiallyReachableFromMany on
+      // lib/Analysis/CFG.cpp (currently only for BasicBlocks) might be helpful.
+      if (UI->getParent() == Store->getParent()) {
+        // The same block case is special because it's the only time we're
+        // looking within a single block to see which instruction comes first.
+        // Once we start looking at multiple blocks, the first instruction of
+        // the block is reachable, so we only need to determine reachability
+        // between whole blocks.
+        BasicBlock *BB = UI->getParent();
+
+        // If A comes before B, then B is definitively reachable from A.
+        if (UI->comesBefore(Store))
           return false;
-    DestModRef |= BAA.getModRefInfo(UI, DestLoc);
 
+        // If the user's parent block is entry, no predecessor exists.
+        if (BB->isEntryBlock())
+          return true;
+
+        // Otherwise, continue doing the normal per-BB CFG walk.
+        ReachabilityWorklist.append(succ_begin(BB), succ_end(BB));
+      } else {
+        ReachabilityWorklist.push_back(UI->getParent());
+      }
+    }
     return true;
   };
 
   if (!CaptureTrackingWithModRef(DestAlloca, DestModRefCallback))
     return false;
+  // Bailout if Dest may have any ModRef before Store.
+  if (!ReachabilityWorklist.empty() &&
+      isPotentiallyReachableFromMany(ReachabilityWorklist, Store->getParent(),
+                                     nullptr, DT, nullptr))
+    return false;
 
-  // 3. Check that, from after the Load to the end of the BB,
-  // 3-1. if the dest has any Mod, src has no Ref, and
-  // 3-2. if the dest has any Ref, src has no Mod except full-sized lifetimes.
+  // Check that, from after the Load to the end of the BB,
+  //   - if the dest has any Mod, src has no Ref, and
+  //   - if the dest has any Ref, src has no Mod except full-sized lifetimes.
   MemoryLocation SrcLoc(SrcAlloca, LocationSize::precise(Size));
 
   auto SrcModRefCallback = [&](Instruction *UI) -> bool {
-    // Any ModRef before Load doesn't matter, also Load and Store can be
-    // ignored.
-    if (UI->comesBefore(Load) || UI == Load || UI == Store)
+    // Any ModRef post-dominated by Load doesn't matter, also Load and Store
+    // themselves can be ignored.
+    if (PDT->dominates(Load, UI) || UI == Load || UI == Store)
       return true;
     ModRefInfo Res = BAA.getModRefInfo(UI, SrcLoc);
     if ((isModSet(DestModRef) && isRefSet(Res)) ||
         (isRefSet(DestModRef) && isModSet(Res)))
       return false;
 
     return true;
   };
 
   if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback))
     return false;
 
   // We can do the transformation. First, align the allocas appropriately.
   SrcAlloca->setAlignment(
       std::max(SrcAlloca->getAlign(), DestAlloca->getAlign()));
 
   // Merge the two allocas.
   DestAlloca->replaceAllUsesWith(SrcAlloca);
   eraseInstruction(DestAlloca);
 
   // Drop metadata on the source alloca.
   SrcAlloca->dropUnknownNonDebugMetadata();
 
   // Do "shrink wrap" the lifetimes, if the original lifetime intrinsics exists.
   if (!LifetimeMarkers.empty()) {
     LLVMContext &C = SrcAlloca->getContext();
     IRBuilder<> Builder(C);
 
     ConstantInt *AllocaSize = ConstantInt::get(Type::getInt64Ty(C), Size);
     // Create a new lifetime start marker before the first user of src or alloca
     // users.
-    Builder.SetInsertPoint(FirstUser->getParent(), FirstUser->getIterator());
+    MemoryAccess *StartMA;
+    if (auto *DomI = dyn_cast_if_present<Instruction *>(Dom)) {
+      Builder.SetInsertPoint(DomI->getParent(), DomI->getIterator());
+      auto *Start = Builder.CreateLifetimeStart(SrcAlloca, AllocaSize);
+      StartMA = MSSAU->createMemoryAccessBefore(Start, nullptr,
+                                                MSSA->getMemoryAccess(DomI));
+    } else {
+      auto *DomB = cast<BasicBlock *>(Dom);
+      Builder.SetInsertPoint(DomB->getTerminator());
       auto *Start = Builder.CreateLifetimeStart(SrcAlloca, AllocaSize);
-    auto *FirstMA = MSSA->getMemoryAccess(FirstUser);
-    auto *StartMA = MSSAU->createMemoryAccessBefore(Start, nullptr, FirstMA);
+      StartMA = MSSAU->createMemoryAccessInBB(
+          Start, nullptr, Start->getParent(), MemorySSA::BeforeTerminator);
+    }
     MSSAU->insertDef(cast<MemoryDef>(StartMA), /*RenameUses=*/true);
 
     // Create a new lifetime end marker after the last user of src or alloca
-    // users.
-    // FIXME: If the last user is the terminator for the bb, we can insert
-    // lifetime.end marker to the immidiate post-dominator, but currently do
-    // nothing.
-    if (!LastUser->isTerminator()) {
-      Builder.SetInsertPoint(LastUser->getParent(), ++LastUser->getIterator());
+    // users. If there's no such postdominator, just don't bother; we could
+    // create one at each exit block, but that'd be essentially semantically
+    // meaningless.
+    // If the PDom is the terminator (e.g. invoke), see the next immediate post
+    // dominator.
+    if (auto *PDomI = dyn_cast_if_present<Instruction *>(PDom);
+        PDomI && PDomI->isTerminator()) {
+      auto *IPDomNode = (*PDT)[PDomI->getParent()]->getIDom();
+      PDom = IPDomNode ? IPDomNode->getBlock() : nullptr;
+    }
+    if (PDom) {
+      MemoryAccess *EndMA;
+      if (auto *PDomI = dyn_cast<Instruction *>(PDom)) {
+        // If PDom is Instruction ptr, insert after it, because it's a user of
+        // SrcAlloca.
+        Builder.SetInsertPoint(PDomI->getParent(), ++PDomI->getIterator());
         auto *End = Builder.CreateLifetimeEnd(SrcAlloca, AllocaSize);
-      auto *LastMA = MSSA->getMemoryAccess(LastUser);
-      auto *EndMA = MSSAU->createMemoryAccessAfter(End, nullptr, LastMA);
+        EndMA = MSSAU->createMemoryAccessAfter(End, nullptr,
+                                               MSSA->getMemoryAccess(PDomI));
+      } else {
+        auto *PDomB = cast<BasicBlock *>(PDom);
+        Builder.SetInsertPoint(PDomB, PDomB->getFirstInsertionPt());
+        auto *End = Builder.CreateLifetimeEnd(SrcAlloca, AllocaSize);
+        EndMA = MSSAU->createMemoryAccessInBB(End, nullptr, End->getParent(),
+                                              MemorySSA::Beginning);
+      }
       MSSAU->insertDef(cast<MemoryDef>(EndMA), /*RenameUses=*/true);
     }
 
     // Remove all other lifetime markers.
     for (Instruction *I : LifetimeMarkers)
       eraseInstruction(I);
   }
 
   // As this transformation can cause memory accesses that didn't previously
   // alias to begin to alias one another, we remove !noalias metadata from any
   // uses of either alloca. This is conservative, but more precision doesn't
   // seem worthwhile right now.
bool MemCpyOptPass::iterateOnFunction(Function &F) {
   return MadeChange;
 }
 
 PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto *AA = &AM.getResult<AAManager>(F);
   auto *AC = &AM.getResult<AssumptionAnalysis>(F);
   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
+  auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
   auto *MSSA = &AM.getResult<MemorySSAAnalysis>(F);
 
-  bool MadeChange = runImpl(F, &TLI, AA, AC, DT, &MSSA->getMSSA());
+  bool MadeChange = runImpl(F, &TLI, AA, AC, DT, PDT, &MSSA->getMSSA());
   if (!MadeChange)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
 bool MemCpyOptPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
                             AliasAnalysis *AA_, AssumptionCache *AC_,
-                            DominatorTree *DT_, MemorySSA *MSSA_) {
+                            DominatorTree *DT_, PostDominatorTree *PDT_,
+                            MemorySSA *MSSA_) {
   bool MadeChange = false;
   TLI = TLI_;
   AA = AA_;
   AC = AC_;
   DT = DT_;
+  PDT = PDT_;
   MSSA = MSSA_;
   MemorySSAUpdater MSSAU_(MSSA_);
   MSSAU = &MSSAU_;
 
   while (true) {
     if (!iterateOnFunction(F))
       break;
     MadeChange = true;
   }
 
   if (VerifyMemorySSA)
     MSSA_->verifyMemorySSA();
 
   return MadeChange;
 }

llvm/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopFullUnrollPass
 ; CHECK-EP-LOOP-END-NEXT: Running pass: NoOpLoopPass
 ; CHECK-O-NEXT: Running pass: SROAPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: VectorCombinePass
 ; CHECK-O23SZ-NEXT: Running pass: MergedLoadStoreMotionPass
 ; CHECK-O23SZ-NEXT: Running pass: GVNPass
 ; CHECK-O23SZ-NEXT: Running analysis: MemoryDependenceAnalysis
 ; CHECK-O1-NEXT: Running pass: MemCpyOptPass
+; CHECK-O1-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SCCPPass
 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-EP-PEEPHOLE-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O1-NEXT: Running pass: CoroElidePass
 ; CHECK-O-NEXT: Running pass: ADCEPass
-; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
+; CHECK-O23SZ-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: MemCpyOptPass
 ; CHECK-O23SZ-NEXT: Running pass: DSEPass
 ; CHECK-O23SZ-NEXT: Running pass: MoveAutoInitPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O23SZ-NEXT: Running pass: LCSSAPass
 ; CHECK-O23SZ-NEXT: Running pass: LICMPass
 ; CHECK-O23SZ-NEXT: Running pass: CoroElidePass
 ; CHECK-EP-SCALAR-LATE-NEXT: Running pass: NoOpFunctionPass

llvm/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O23SZ-NEXT: Running analysis: MemorySSAAnalysis on foo
 ; CHECK-O23SZ-NEXT: Running analysis: AAManager on foo
 ; CHECK-O23SZ-NEXT: Running analysis: ScalarEvolutionAnalysis on foo
 ; CHECK-O23SZ-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O23SZ-NEXT: Running pass: LICMPass on loop
 ; CHECK-O23SZ-NEXT: Running pass: GVNPass on foo
 ; CHECK-O23SZ-NEXT: Running analysis: MemoryDependenceAnalysis on foo
 ; CHECK-O23SZ-NEXT: Running pass: MemCpyOptPass on foo
-; CHECK-O23SZ-NEXT: Running pass: DSEPass on foo
 ; CHECK-O23SZ-NEXT: Running analysis: PostDominatorTreeAnalysis on foo
+; CHECK-O23SZ-NEXT: Running pass: DSEPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: MoveAutoInitPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: MergedLoadStoreMotionPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: LoopSimplifyPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: LCSSAPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: IndVarSimplifyPass on loop
 ; CHECK-O23SZ-NEXT: Running pass: LoopDeletionPass on loop
 ; CHECK-O23SZ-NEXT: Running pass: LoopFullUnrollPass on loop
 ; CHECK-O23SZ-NEXT: Running pass: LoopDistributePass on foo

llvm/test/Other/new-pm-thinlto-postlink-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopDeletionPass
 ; CHECK-O-NEXT: Running pass: LoopFullUnrollPass
 ; CHECK-O-NEXT: Running pass: SROAPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: VectorCombinePass
 ; CHECK-O23SZ-NEXT: Running pass: MergedLoadStoreMotionPass
 ; CHECK-O23SZ-NEXT: Running pass: GVNPass
 ; CHECK-O23SZ-NEXT: Running analysis: MemoryDependenceAnalysis
 ; CHECK-O1-NEXT: Running pass: MemCpyOptPass
+; CHECK-O1-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SCCPPass
 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O1-NEXT: Running pass: CoroElidePass
 ; CHECK-O-NEXT: Running pass: ADCEPass
-; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
+; CHECK-O23SZ-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: MemCpyOptPass
 ; CHECK-O23SZ-NEXT: Running pass: DSEPass
 ; CHECK-O23SZ-NEXT: Running pass: MoveAutoInitPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O23SZ-NEXT: Running pass: LCSSAPass
 ; CHECK-O23SZ-NEXT: Running pass: LICMPass on loop
 ; CHECK-O23SZ-NEXT: Running pass: CoroElidePass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass

llvm/test/Other/new-pm-thinlto-prelink-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopDeletionPass
 ; CHECK-O-NEXT: Running pass: LoopFullUnrollPass
 ; CHECK-O-NEXT: Running pass: SROAPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: VectorCombinePass
 ; CHECK-O23SZ-NEXT: Running pass: MergedLoadStoreMotionPass
 ; CHECK-O23SZ-NEXT: Running pass: GVNPass
 ; CHECK-O23SZ-NEXT: Running analysis: MemoryDependenceAnalysis
 ; CHECK-O1-NEXT: Running pass: MemCpyOptPass
+; CHECK-O1-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SCCPPass
 ; CHECK-O-NEXT: Running pass: BDCEPass
 ; CHECK-O-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O1-NEXT: Running pass: CoroElidePass
 ; CHECK-O-NEXT: Running pass: ADCEPass
-; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
+; CHECK-O23SZ-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: MemCpyOptPass
 ; CHECK-O23SZ-NEXT: Running pass: DSEPass
 ; CHECK-O23SZ-NEXT: Running pass: MoveAutoInitPass
 ; CHECK-O23SZ-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O23SZ-NEXT: Running pass: LCSSAPass
 ; CHECK-O23SZ-NEXT: Running pass: LICMPass on loop
 ; CHECK-O23SZ-NEXT: Running pass: CoroElidePass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass

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

;
   to label %suc unwind label %unw
 unw:
   %lp = landingpad i32 cleanup
   resume i32 0
 suc:
   ret void
 }
 
-; TODO: merge allocas for bb-separated, but logically straight
 define void @multi_bb_memcpy(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_memcpy
 ; CHECK-SAME: (i1 [[B:%.*]]) {
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[DEST:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 4, ptr nocapture [[SRC]])
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 4, ptr nocapture [[DEST]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 4, ptr [[SRC]])
 ; CHECK-NEXT:    store i32 42, ptr [[SRC]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture [[SRC]])
 ; CHECK-NEXT:    br label [[BB0:%.*]]
 ; CHECK:       bb0:
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 4, i1 false)
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[DEST]])
-; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 4, ptr nocapture [[SRC]])
-; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 4, ptr nocapture [[DEST]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 4, ptr [[SRC]])
 ; CHECK-NEXT:    ret void
 ;
   %src = alloca i32, align 4
   %dest = alloca i32, align 4
   call void @llvm.lifetime.start.p0(i64 4, ptr nocapture %src)
   call void @llvm.lifetime.start.p0(i64 4, ptr nocapture %dest)
   store i32 42, ptr %src
   %1 = call i32 @use_nocapture(ptr nocapture %src)
   br label %bb0
 
 bb0:
   call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 4, i1 false)
   br label %bb1
 
 bb1:
   %2 = call i32 @use_nocapture(ptr nocapture %dest)
   call void @llvm.lifetime.end.p0(i64 4, ptr nocapture %src)
   call void @llvm.lifetime.end.p0(i64 4, ptr nocapture %dest)
   ret void
 }
 
-; TODO: Merge alloca
 define void @multi_bb_load_store(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_load_store
 ; CHECK-SAME: (i1 [[B:%.*]]) {
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[DEST:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 4, ptr nocapture [[SRC]])
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 4, ptr nocapture [[DEST]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 4, ptr [[SRC]])
 ; CHECK-NEXT:    store i32 42, ptr [[SRC]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture [[SRC]])
-; CHECK-NEXT:    [[SRC_VAL:%.*]] = load i32, ptr [[SRC]], align 4
-; CHECK-NEXT:    store i32 [[SRC_VAL]], ptr [[DEST]], align 4
 ; CHECK-NEXT:    br label [[BB0:%.*]]
 ; CHECK:       bb0:
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[DEST]])
-; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 4, ptr nocapture [[SRC]])
-; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 4, ptr nocapture [[DEST]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 4, ptr [[SRC]])
 ; CHECK-NEXT:    ret void
 ;
   %src = alloca i32, align 4
   %dest = alloca i32, align 4
   call void @llvm.lifetime.start.p0(i64 4, ptr nocapture %src)
   call void @llvm.lifetime.start.p0(i64 4, ptr nocapture %dest)
   store i32 42, ptr %src
   %1 = call i32 @use_nocapture(ptr nocapture %src)

 
 bb1:
   %2 = call i32 @use_nocapture(ptr nocapture %dest)
   call void @llvm.lifetime.end.p0(i64 4, ptr nocapture %src)
   call void @llvm.lifetime.end.p0(i64 4, ptr nocapture %dest)
   ret void
 }
 
-; TODO: merge allocas for multi basicblocks, s.t. all copy-dominated
-; uses are satisfy the condition.
 define void @multi_bb_simple_br(i1 %b) {
 ; 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:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
 ; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; 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:    call void @llvm.lifetime.end.p0(i64 12, ptr [[SRC]])
 ; 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)
bb2:
   ret void
 }
 
 ; Test for BasicBlock and Instruction mixed dominator finding.
 define void @multi_bb_dom_test0(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_dom_test0
 ; 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 [[SRC]])
 ; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb0:
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 40, i32 50, i32 60 }, ptr [[SRC]], align 4
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[DEST]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr [[SRC]])
 ; CHECK-NEXT:    ret void
 ;
   %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

 
 }
 
 ; Test for BasicBlock and Instruction mixed post-dominator finding.
 define void @multi_bb_pdom_test0(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_pdom_test0
 ; 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 [[DEST]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
-; 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:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
-; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr nocapture [[DEST]])
+; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr [[SRC]])
 ; 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 %dest)
   store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
   call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false); 1
   br i1 %b, label %bb0, label %bb1
 
 bb0:
   %1 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   br label %bb2
 
 bb1:
   %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   br label %bb2
 
 bb2:
   %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
   ret void
 
   uselistorder ptr %dest, {  2, 3, 0, 1, 4, 5 }
 }
 
 ; Test for inserting lifetime.end after the phi-node
 define void @multi_bb_pdom_test1(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_pdom_test1
 ; 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 [[DEST]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
-; 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:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 42, [[BB0]] ], [ 41, [[BB1]] ]
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr [[SRC]])
 ; 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 %dest)
   store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
   call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false); 1
   br i1 %b, label %bb0, label %bb1
 
 bb0:
   %1 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   br label %bb2
 
 bb1:
   %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   br label %bb2
 
 bb2:
   %i = phi i32 [ 42, %bb0 ], [ 41, %bb1 ]
   ret void
 
 }
 
-; TODO: merge allocas for multi basicblock loop case.
 define void @multi_bb_loop(i32 %n) {
 ; CHECK-LABEL: define void @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]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 0, i32 1, i32 42 }, ptr [[SRC]], align 4
 ; CHECK-NEXT:    br i1 [[NLT1]], label [[LOOP_EXIT:%.*]], label [[LOOP_BODY:%.*]]
 ; CHECK:       loop_body:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[NEW_I:%.*]], [[LOOP_BODY]] ], [ 1, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 8 [[DEST]], ptr align 8 [[SRC]], i64 12, i1 false)
 ; CHECK-NEXT:    [[NEW_I]] = add i32 [[I]], 1
 ; CHECK-NEXT:    store i32 [[NEW_I]], ptr [[SRC]], align 4
 ; CHECK-NEXT:    [[IGTN:%.*]] = icmp sgt i32 [[NEW_I]], [[N]]
 ; CHECK-NEXT:    br i1 [[IGTN]], label [[LOOP_EXIT]], label [[LOOP_BODY]]
 ; CHECK:       loop_exit:
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 12, ptr [[SRC]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %nlt1 = icmp slt i32 %n, 1
   %src = alloca %struct.Foo, align 8
   %dest = alloca %struct.Foo, align 8
   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 0, i32 1, i32 42 }, ptr %src
   br i1 %nlt1, label %loop_exit, label %loop_body
 
 loop_body:
   %i = phi i32 [ %new_i, %loop_body ], [ 1, %entry ]
   call void @llvm.memcpy.p0.p0.i64(ptr align 8 %dest, ptr align 8 %src, i64 12, i1 false)
   %new_i = add i32 %i, 1
   store i32 %new_i, ptr %src
   %igtn = icmp sgt i32 %new_i, %n
   br i1 %igtn, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
-; TODO: merge allocas for multi basicblocks, s.t. some modref which is unreachable from copy exists.
 define void @multi_bb_unreachable_modref(i1 %b0) {
 ; CHECK-LABEL: define void @multi_bb_unreachable_modref
 ; CHECK-SAME: (i1 [[B0:%.*]]) {
 ; 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:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
 ; 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:    br i1 [[B0]], label [[BB0:%.*]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb0:
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
-; 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:
   %2 = 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. memcpy doesn't dominate the uses.
 define void @multi_bb_non_dominated(i1 %b0, i1 %b1) {
 ; CHECK-LABEL: define void @multi_bb_non_dominated
 ; CHECK-SAME: (i1 [[B0:%.*]], i1 [[B1:%.*]]) {
 ; 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:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
 ; 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:    br i1 [[B0]], label [[BB0:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb0:
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; 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:    call void @llvm.lifetime.end.p0(i64 12, ptr [[SRC]])
 ; 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 label %bb2
 
 bb1:
   %2 = call i32 @use_nocapture(ptr noundef nocapture %src)
-  ; %3 = call i32 @use_writeonly(ptr noundef nocapture %dest)
   br label %bb2
 
 bb2:
-  ; %4 = 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
 }
 
 ; TODO: to merge following `is_def` cases, we need to do liveness analysis
 ; or something that distinguish the full-size-Mod as a Def.
 ; Tests that a memcpy that completely overwrites a stack value is a definition