[WIP][MemCpyOpt] implement liveness analysis based stack-move optimization

[khei4]

Summary

This is WIP
This patch extends multi-BB stack-move optimization using a liveness analysis framework as pcwalton does.
only focused on unescaped static allocas as the previous patch does,

This patch introduce BB/Instruction-level Liveness Analysis, basically with the same terminology with Modern Compiler Implementation book

1. capture check by CaptureTracker, collect whether all SSA uses are 1) LiveDef, which writes full size data to alloca (e.g. full-sized lifetime.start/end, memcpy/memset/memmove, store/load or 2) LiveUse, otherwise.
2. Compute the src/dest alloca Liveness, by LiveUse based backward approach.
   • If the BB's first SSA use is LiveUse of src/dest, this BB is LiveIn for src/dest.
   • The LiveIn BB's predecessors are LiveOut for the allocas.
     • The LiveIn BB's predecessors, which don't contain any LiveUse or LiveDef, are also LiveIn.

3. Check the BB-level liveness conflict; if it fails, check User-level liveness conflicts
   • BB-level
     • If the BB is also LiveIn or is LiveOut or contains LiveUse for src and dest simultaneously, then it conflict.
   • User-level
     • From the end of BB, propagate src and dest liveness (If met LiveUse, then live, otherwise LiveDef make it not live) (TODO: more proper explanation).

So basically above procedure is pcwalton's liveness analysis, but it miscompile and missed some opportunities as followings

misscompile (or miss opportunity, we can merge if we remove meaning less store %struct.Foo { i32 13, i32 13, i32 13 }, ptr %dest. These can be characterized by mergeable if we remove no Use, no LiveOut LiveDef `. But it requires more User-level checks if we try to merge them.

%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

call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)
store %struct.Foo { i32 13, i32 13, i32 13 }, ptr %dest
%1 = call i32 @use_nocapture(ptr 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

missed opportunity (if the Use is only read, no conflict happens.)

%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

call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)

%1 = call i32 @use_readonly(ptr nocapture %src)
%2 = call i32 @use_readonly(ptr nocapture %src)
%3 = call i32 @use_readonly(ptr nocapture %dest)
call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
ret void

Both cases can be covered by making LiveUse have ModRef information but balancing with compile time regressions.

TODO: Currently, the following will be miscompiled (src and dest would be merged)

%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

call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)

%1 = call i32 @use_nocapture(ptr nocapture %src)
%2 = call i32 @use_nocapture(ptr nocapture %dest)
call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
ret void

[nikic]

It looks like this is a diff against some intermediate version, rather than the full patch.

[khei4]

fix wrong diff

[khei4]

It looks like this is a diff against some intermediate version, rather than the full patch.

@nikic Thanks! I fixed and updated the description, although still WIP!

[khei4]

If I used the backward approach like this, I couldn't handle cleanly some cases that we could merge in the multi-BB case (for example, src and dest are read-only together; I believe it's a sufficiently familiar case for Rust). Still, I now noticed extending the ModRef analysis in a more forward flow-sensitive way could cover the use after def cases as complex as this patch is. So a change is planned.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
+#include <functional>
+#include <map>
 #include <optional>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "memcpyopt"
 
 static cl::opt<bool> EnableMemCpyOptWithoutLibcalls(
     "enable-memcpyopt-without-libcalls", cl::Hidden,
     cl::desc("Enable memcpyopt even when libcalls are disabled"));
+static cl::opt<unsigned>
+    MemCpyOptStackMoveThreshold("memcpyopt-stack-move-threshold", cl::Hidden,
+                                cl::desc("Maximum number of basic blocks the "
+                                         "stack-move optimization may examine"),
+                                cl::init(16));
 
 STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
 STATISTIC(NumMemSetInfer, "Number of memsets inferred");
 STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy");
 STATISTIC(NumCpyToSet, "Number of memcpys converted to memset");
 STATISTIC(NumCallSlot, "Number of call slot optimizations performed");
 STATISTIC(NumStackMove, "Number of stack-move optimizations performed");
 
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;
 }
 
+// These helper classes are used for the stack-move optimization. See the
+// comments above performStackMoveOptzn() for more details.
+
+namespace {
+
+enum Liveness { LiveUse, LiveDef };
+struct InstCmp {
+  bool operator()(const Instruction *L, const Instruction *R) const {
+    return R->comesBefore(L);
+  };
+};
+
+using LiveDefOrUseInst = PointerIntPair<Instruction *, 1, Liveness>;
+
+// Tracks liveness on the basic block level. This is conservative; see the
+// comments above performStackMoveOptzn() for justification.
+class BasicBlockLiveness {
+
+  // Whether the alloca is live-in to the block (from predecessor basic blocks).
+  bool LiveIn = false;
+  // Whether the alloca is live-out from the block (to successor basic blocks).
+  bool LiveOut = false;
+  // Whether there's at least one use of the alloca in this basic block. This
+  // flag is important for detecting liveness conflicts, since the other
+  // information stored here isn't sufficient to determine that a use is present
+  // if a definition precedes it.
+  bool HasUse = false;
+
+  // Type for the Instruction and LiveUse or LiveDef. if true, then LiveDef
+  // The earliest definition or use we've seen, combined with the three bits
+  // below.
+  LiveDefOrUseInst FirstLiveUseOrDefInst;
+
+  // All LiveUse or LiveDef Instructions on this block.
+  std::map<Instruction *, Liveness, InstCmp> UseOrDefs;
+
+  // Records a first def or use instruction.
+  void setFirstLiveDefOrUseInst(Instruction *I, Liveness L) {
+    assert((!hasDefUseInst() ||
+            I->comesBefore(getFirstLiveUseOrDefInst().getPointer())) &&
+           "Tried to overwrite an earlier def or use with a later one!");
+    FirstLiveUseOrDefInst.setPointer(I);
+    FirstLiveUseOrDefInst.setInt(L);
+  }
+
+  void addLiveDefOrUseInst(Instruction *I, Liveness L) {
+    UseOrDefs.insert({I, L});
+  }
+
+  // Sets the flag which determines whether this block has a use.
+  void setHasUse(bool On) { HasUse = On; }
+
+public:
+  BasicBlockLiveness() : FirstLiveUseOrDefInst(nullptr) {}
+
+  // Returns the earliest definition or use we've seen in this block.
+  const LiveDefOrUseInst &getFirstLiveUseOrDefInst() const {
+    return FirstLiveUseOrDefInst;
+  }
+
+  // Returns the all LiveUses and LiveDefs.
+  std::map<Instruction *, Liveness, InstCmp> &getUseOrDefs() {
+    return UseOrDefs;
+  }
+
+  // Returns true if there's a definition or use of the memory in this block.
+  bool hasDefUseInst() const {
+    return FirstLiveUseOrDefInst.getPointer() != nullptr;
+  }
+  // Returns true if the memory is live-in to this block (i.e. live-out of a
+  // predecessor).
+  bool isLiveIn() const { return LiveIn; }
+  // Returns true if the memory is live-out of this block (i.e. live-in to a
+  // successor).
+  bool isLiveOut() const { return LiveOut; }
+  // Returns true if there is at least one use of the memory in this block.
+  bool hasUse() const { return HasUse; }
+  // Returns true if this alloca is live anywhere in this block or has
+  // at least one use in it. If this returns false, the alloca is
+  // guaranteed to be completely dead within this basic block.
+  bool isLiveAnywhereOrHasUses() const {
+    return isLiveIn() || isLiveOut() || hasUse();
+  }
+  // Adjusts the live-in flag for this block.
+  void setLiveIn(bool On) { LiveIn = On; }
+
+  // Adjusts the live-out flag for this block.
+  void setLiveOut(bool On) { LiveOut = On; }
+
+  // Records a new definition or use of the alloca being tracked within this
+  // basic block.
+  void update(Instruction *I, Liveness L) {
+    // Set use or def for the first instruction, BB is LiveIn if the first user
+    // is use.
+    if (!hasDefUseInst() ||
+        I->comesBefore(getFirstLiveUseOrDefInst().getPointer())) {
+      setFirstLiveDefOrUseInst(I, L);
+      setLiveIn(L == LiveUse);
+    }
+    if (L == LiveUse)
+      setHasUse(true);
+
+    addLiveDefOrUseInst(I, L);
+  }
+};
+
+} // namespace
+using BasicBlockLivenessMap = DenseMap<BasicBlock *, BasicBlockLiveness>;
+
+// Performs liveness dataflow analysis for an alloca at the basic block level as
+// part of the stack-move optimization.
+//
+// This implements the "backwards variable-at-a-time" variant of liveness
+// analysis, propagating liveness information backwards from uses until it sees
+// a basic block with a definition or one in which the variable is already
+// live-out. As implemented, this is a linear-time algorithm, because it only
+// visits every basic block at most once and the number of tracked variables is
+// constant (two--the source and destination of the memcpy).
+//
+// In order to avoid spending too much compile time, this operates on the level
+// of basic blocks instead of instructions, making it a conservative
+// analysis. See the comments in performStackMoveOptzn() for more details.
+//
+// Returns true if the analysis succeeded or false if it failed due to examining
+// too many basic blocks.
+static bool computeLiveness(BasicBlockLivenessMap &BBLivenessMap) {
+  // Start by initializing a worklist with all basic blocks that are live-in
+  // (i.e. they potentially need to propagate liveness to their predecessors).
+  SmallVector<BasicBlock *, 8> Worklist;
+  for (auto &[BB, BBLiveness] : BBLivenessMap) {
+    if (BBLiveness.getFirstLiveUseOrDefInst().getInt() == Liveness::LiveUse) {
+      BBLiveness.setLiveIn(true);
+      Worklist.push_back(BB);
+    }
+  }
+
+  // Iterate until we have no more blocks to process.
+  unsigned Count = 0;
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.back();
+    Worklist.pop_back();
+
+    // Cap the number of basic blocks we examine in order to avoid blowing up
+    // compile time. The default threshold was empirically determined to be
+    // sufficient 90% of the time in the Rust compiler.
+    ++Count;
+    if (Count >= MemCpyOptStackMoveThreshold) {
+      LLVM_DEBUG(
+          dbgs()
+          << "Stack Move: Exceeded max basic block threshold, bailing\n");
+      return false;
+    }
+
+    // We know that the alloca must be live-in to this basic block, or else we
+    // wouldn't have added the block to the worklist in the first place.
+    assert(BBLivenessMap.lookup(BB).isLiveIn() &&
+           "Shouldn't have added a BB that wasn't live-in to the worklist!");
+
+    // Propagate liveness back to predecessors.
+    for (BasicBlock *Pred : predecessors(BB)) {
+      BasicBlockLiveness PredLiveness = BBLivenessMap.lookup(Pred);
+
+      // Skip predecessors in which the variable is already known to be
+      // live-out.
+      if (PredLiveness.isLiveOut())
+        continue;
+      PredLiveness.setLiveOut(true);
+
+      // Don't enqueue predecessors if they contain direct defs or uses of the
+      // variable. If a predecessor contains a use of the variable that
+      // dominates all the other uses or defs of the variable within that
+      // block, then we already added that predecessor to the worklist at the
+      // beginning of this procedure, so we don't need to add it again. If, on
+      // the other hand, the predecessor contains a definition of the variable
+      // that dominates all the other uses or defs of the variable within the
+      // block, then the predecessor won't propagate any liveness to *its*
+      // predecessors, so we don't need to enqueue it either.
+      if (!PredLiveness.hasDefUseInst()) {
+        // We know that this predecessor is a basic block that contains
+        // neither defs nor uses of the variable and in which the variable is
+        // live-out. So the variable must be live-in to this predecessor too.
+        PredLiveness.setLiveIn(true);
+        Worklist.push_back(Pred);
+      }
+
+      BBLivenessMap[Pred] = PredLiveness;
+    }
+  }
+
+  return true;
+}
+
+bool checkInstructionLevelLivenessConflict(
+    BasicBlockLivenessMap &DestLivenessMap,
+    BasicBlockLivenessMap &SrcLivenessMap, BasicBlock *BB, Instruction *Load,
+    Instruction *Store) {
+  // Check liveness inside the BB, check the uses in the order of appearance.
+  auto SrcBBLiveness = SrcLivenessMap.lookup(BB);
+  auto DestBBLiveness = DestLivenessMap.lookup(BB);
+  bool SrcLive = SrcBBLiveness.isLiveOut();
+  bool DestLive = DestBBLiveness.isLiveOut();
+
+  auto &SrcUseOrDefs = SrcBBLiveness.getUseOrDefs();
+  auto &DestUseOrDefs = DestBBLiveness.getUseOrDefs();
+
+  auto AllUseOrDefs = SrcUseOrDefs;
+  // FIXME: memcpy (Store, Load) is duplicated, so sorting is UB.
+  AllUseOrDefs.insert(DestUseOrDefs.begin(), DestUseOrDefs.end());
+  dbgs() << "user from reverse\n";
+  // TODO: to merge safely we need to mark and erase DestDef during Src is
+  // alive.
+  for (const auto &[I, L] : AllUseOrDefs) {
+    dbgs() << "Liveness Inst = :";
+    I->print(dbgs());
+    dbgs() << "\n is " << (L == Liveness::LiveDef ? "Def" : "Use") << "\n";
+
+    // FIXME: is this OK to exclude Load and store?
+    if (DestLive && SrcLive && I != Load && I != Store) {
+      LLVM_DEBUG(
+          dbgs() << "Stack Move: Detected liveness conflict inside the basic "
+                    "block \n  Instruction: "
+                 << I << "\n");
+      return false;
+    }
+    // FIXME: these equality check takes linear time, also failed because IL is
+    // not instruction but with LivenessInfo
+    if (SrcUseOrDefs.count(I))
+      SrcLive = SrcUseOrDefs[I] == Liveness::LiveUse;
+
+    if (DestUseOrDefs.count(I))
+      DestLive = DestUseOrDefs[I] == Liveness::LiveUse;
+    dbgs() << "after that SrcLive=" << SrcLive << " DestLive=" << DestLive
+           << "\n";
+  }
+  return true;
+}
+
+bool checkBBLevelLivenessConflict(BasicBlockLivenessMap &DestLivenessMap,
+                                  BasicBlockLivenessMap &SrcLivenessMap,
+                                  Instruction *Load, Instruction *Store) {
+  // Check for liveness conflicts on the basic block level (with the exception
+  // of the basic block containing the memcpy).
+  for (const auto &[BB, DestLiveness] : DestLivenessMap) {
+    if (DestLiveness.isLiveAnywhereOrHasUses() &&
+        SrcLivenessMap.lookup(BB).isLiveAnywhereOrHasUses()) {
+      LLVM_DEBUG(
+          dbgs() << "Stack Move: Detected Basic Block liveness conflict, "
+                    "\n  Basic Block: "
+                 << BB->getNameOrAsOperand() << "\n");
+      if (!checkInstructionLevelLivenessConflict(
+              DestLivenessMap, SrcLivenessMap, BB, Load, Store))
+        return false;
+    }
+  }
+  return true;
+}
+
 using InsertionPt = PointerUnion<Instruction *, BasicBlock *>;
 /// 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))
bool MemCpyOptPass::performStackMoveOptzn(Instruction *Load, Instruction *Store,
   // 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 *DomI = nullptr;
   InsertionPt PDom = nullptr;
   SmallSet<Instruction *, 4> NoAliasInstrs;
+  BasicBlockLivenessMap SrcLivenessMap, DestLivenessMap;
 
   // 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);
   };
 
-  auto CaptureTrackingWithModRef =
-      [&](Instruction *AI,
-          function_ref<bool(Instruction *)> ModRefCallback) -> bool {
+  auto CaptureTrackingWithLivenessAnalysis =
+      [&](Instruction *AI, BasicBlockLivenessMap &BBLivenessMap) -> bool {
     SmallVector<Instruction *, 8> Worklist;
     Worklist.push_back(AI);
     unsigned MaxUsesToExplore = getDefaultMaxUsesToExploreForCaptureTracking();
     Worklist.reserve(MaxUsesToExplore);
     SmallSet<const Use *, 20> Visited;
     while (!Worklist.empty()) {
       Instruction *I = Worklist.back();
       Worklist.pop_back();
       for (const Use &U : I->uses()) {
         if (Visited.size() >= MaxUsesToExplore) {
           LLVM_DEBUG(
               dbgs()
               << "Stack Move: Exceeded max uses to see ModRef, bailing\n");
           return false;
         }
         if (!Visited.insert(&U).second)
           continue;
         switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) {
         case UseCaptureKind::MAY_CAPTURE:
+          LLVM_DEBUG({
+            dbgs() << "Stack Move: Alloca may be captured:";
+            dbgs() << "\n" << U;
+            dbgs() << "\n";
+          });
           return false;
         case UseCaptureKind::PASSTHROUGH:
+          // FIXME: should we check liveness on this? I guess not, because these
+          // are generally ignorable like gep.
           // 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 (!DomI) {
             PDom = DomI = UI;
           } else {
             DomI = DT->findNearestCommonDominator(DomI, UI);
             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);
+
+          // If an instruction overwrites all bytes of the alloca, it's a
+          // definition, not a use. Detect those cases here.
+          if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(UI)) {
+            if (II->isLifetimeStartOrEnd()) {
+              // We treat a call to a lifetime intrinsic that covers the entire
+              // alloca as a definition, since both llvm.lifetime.start and
+              // llvm.lifetime.end intrinsics conceptually fill all the bytes of
+              // the alloca with an undefined value. We also note these
+              // locations of these intrinsic calls so that we can delete them
+              // later if the optimization succeeds.
+              int64_t Size =
+                  cast<ConstantInt>(II->getArgOperand(0))->getSExtValue();
+
+              if (Size < 0 || uint64_t(Size) == SrcSize) {
+                BBLivenessMap[II->getParent()].update(II, Liveness::LiveDef);
+                LifetimeMarkers.push_back(II);
                 continue;
               }
+            } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(II)) {
+              if (MI->getArgOperandNo(&U) == 0) {
+                if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getLength())) {
+                  if (CI->getZExtValue() == (*SrcSize).getFixedValue()) {
+
+                    // Memcpy, memmove, and memset instructions that fill every
+                    // byte of the alloca are definitions.
+                    BBLivenessMap[MI->getParent()].update(MI,
+                                                          Liveness::LiveDef);
+                    // TODO: remove dupulication of the noalias insertion
+                    if (MI->hasMetadata(LLVMContext::MD_noalias))
+                      NoAliasInstrs.insert(MI);
+                    continue;
                   }
+                }
+              }
+            }
+          } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
+            // Stores that overwrite all bytes of the alloca are definitions.
+            if (U.getOperandNo() == 1 &&
+                DL.getTypeStoreSize(SI->getValueOperand()->getType()) ==
+                    (*SrcSize).getFixedValue()) {
+              BBLivenessMap[SI->getParent()].update(SI, Liveness::LiveDef);
+              if (SI->hasMetadata(LLVMContext::MD_noalias))
+                NoAliasInstrs.insert(SI);
+              continue;
+            }
+          }
+          BBLivenessMap[UI->getParent()].update(UI, Liveness::LiveUse);
           if (UI->hasMetadata(LLVMContext::MD_noalias))
             NoAliasInstrs.insert(UI);
-          if (!ModRefCallback(UI))
-            return false;
         }
         }
       }
     }
     return true;
   };
 
-  // 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);
-    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;
+  if (!CaptureTrackingWithLivenessAnalysis(DestAlloca, DestLivenessMap) ||
+      !CaptureTrackingWithLivenessAnalysis(SrcAlloca, SrcLivenessMap))
 
-        // If the user's parent block is entry, no predecessor exists.
-        if (BB->isEntryBlock())
-          return true;
+  if (!computeLiveness(DestLivenessMap) || !computeLiveness(SrcLivenessMap))
+    return false;
 
-        // 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;
-  };
+  dbgs() << "Liveness LiveUse = :" << Liveness::LiveUse << '\n';
+  dbgs() << "Liveness LiveDef = :" << Liveness::LiveDef << '\n';
+  for (auto &[BB, DestLiveness] : DestLivenessMap) {
+    for (const auto &[I, L] : DestLiveness.getUseOrDefs()) {
+      dbgs() << "Dest Liveness Inst = :";
+      I->print(dbgs());
+      dbgs() << "\n is " << (L ? "Def" : "Use") << "\n";
 
-  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;
-
-  // 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 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;
+  for (auto &[BB, SrcLiveness] : SrcLivenessMap) {
+    for (const auto &[I, L] : SrcLiveness.getUseOrDefs()) {
+      dbgs() << "Src Liveness Inst = :";
+      I->print(dbgs());
+      dbgs() << "\n is " << (L ? "Def" : "Use") << "\n";
+    }
+  }
+  if (!checkBBLevelLivenessConflict(DestLivenessMap, SrcLivenessMap, Load,
+                                    Store)) {
+    dbgs() << "bail out because of conflict\n";
+  }
 
-    return true;
-  };
-
-  if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback))
-    return false;
+  // remove no liveout def of dest,
+  // TOOD: but we need to care about post dominator
+  // for (auto &[BB, DestLiveness] : DestLivenessMap) {
+  //   if (DestLiveness.isLiveOut())
+  //     continue;
+  //   for (auto LI : DestLiveness.getBBUsesOrDefs()) {
+  //     if (LI.getInt() == Liveness::LiveDef)
+  //       eraseInstruction(LI.getPointer());
+  //   }
+  // }
 
   // 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);

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

bb1:
   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: 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
 ; for the purposes of liveness analysis.
 define void @memcpy_is_def() {
 ; CHECK-LABEL: define void @memcpy_is_def() {
 ; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[SRC]], ptr align 4 [[DEST]], i64 12, i1 false)
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
-; 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)
   call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)
   %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   call void @llvm.memcpy.p0.p0.i64(ptr align 4 %src, ptr align 4 %dest, i64 12, i1 false)
   %3 = 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: merge allocas
 ; Tests that a memset that completely overwrites a stack value is a definition
 ; for the purposes of liveness analysis.
 define void @memset_is_def() {
 ; CHECK-LABEL: define void @memset_is_def() {
 ; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    call void @llvm.memset.p0.i64(ptr align 4 [[SRC]], i8 42, i64 12, i1 false)
 ; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
-; 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)
   call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)
   %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   call void @llvm.memset.p0.i64(ptr align 4 %src, i8 42, i64 12, i1 false)
   %3 = 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: merge allocas
 ; Tests that a store that completely overwrites a stack value is a definition
 ; for the purposes of liveness analysis.
 define void @store_is_def() {
 ; CHECK-LABEL: define void @store_is_def() {
 ; 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 noundef [[SRC]])
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[SRC]], align 4
-; CHECK-NEXT:    store i32 [[TMP2]], ptr [[DEST]], align 4
-; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    store i32 64, ptr [[SRC]], align 4
-; CHECK-NEXT:    [[TMP4:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
-; 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:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[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 noundef nocapture %src)
;
   ret void
 }
 
 ; Tests that the optimization isn't performed,
 ; when the source may have mod and dest may have ref after the full copy.
 define void @src_mod_dest_ref_after_copy() {
 ; CHECK-LABEL: define void @src_mod_dest_ref_after_copy() {
 ; 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:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 13, i32 13, i32 13 }, ptr [[SRC]], align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture [[DEST]])
-; 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:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture [[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 %src)
   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)
 
   store %struct.Foo { i32 13, i32 13, i32 13 }, ptr %src
   %1 = call i32 @use_nocapture(ptr nocapture %dest)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
   ret void
 }
 
+; FIXME: this is corner case for liveness analysis
 ; Tests that the optimization isn't performed.
 ; Merging dest to src is no longer valid if conflicting Mod/Ref exist.
 define void @src_ref_dest_mod_after_copy() {
 ; CHECK-LABEL: define void @src_ref_dest_mod_after_copy() {
 ; 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:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
-; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 13, i32 13, i32 13 }, ptr [[DEST]], align 4
+; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 13, i32 13, i32 13 }, ptr [[SRC]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture [[SRC]])
-; 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
 
;
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
   ret void
 }
 
 ; Tests that failure because alloca is modified through aliases, which requires recursive user ModRefChecks
 define void @alias_src_ref_dest_mod_after_copy() {
 ; CHECK-LABEL: define void @alias_src_ref_dest_mod_after_copy() {
 ; 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 [[SRC]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
-; CHECK-NEXT:    [[DEST_ALIAS:%.*]] = getelementptr inbounds [[STRUCT_FOO]], ptr [[DEST]], i64 0, i32 1
+; CHECK-NEXT:    [[DEST_ALIAS:%.*]] = getelementptr inbounds [[STRUCT_FOO]], ptr [[SRC]], i64 0, i32 1
 ; CHECK-NEXT:    store i32 13, ptr [[DEST_ALIAS]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[SRC]])
-; 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 nocapture %src)

 }
 
 ; Tests that the optimization isn't performed when the source and destination
 ; have mod ref conflict.
 define void @multi_bb_mod_ref_conflict(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_mod_ref_conflict
 ; 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 [[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
 }
 
 ; Tests that failure because after copy mod could be before copy on branch.
 define void @multi_bb_branch_dest_mod_before_copy(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_branch_dest_mod_before_copy
 ; 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:    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:    br label [[BB2]]
 ; CHECK:       bb2:
 ; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
-; 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:    [[TMP2:%.*]] = 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 %src)
   call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %dest)
   br i1 %b, label %bb0, label %bb1
 bb0:

 
 ; Tests that failure because after copy mod could be before copy on loop.
 define void @multi_bb_loop_dest_mod_before_copy(i32 %n) {
 ; CHECK-LABEL: define void @multi_bb_loop_dest_mod_before_copy
 ; 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 [[DEST]], align 4
+; 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)

 loop_exit:
   ret void
 }
 
 ; Tests that failure because partial-sized lifetimes are counted as mod.
 define void @partial_lifetime() {
 ; CHECK-LABEL: define void @partial_lifetime() {
 ; 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 3, ptr nocapture [[DEST]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr [[SRC]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 3, ptr nocapture [[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 [[SRC]])
-; 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 3, ptr nocapture [[SRC]])
-; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[DEST]])
-; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture [[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 %src)
   call void @llvm.lifetime.start.p0(i64 3, ptr nocapture %dest)
   store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
   %1 = call i32 @use_nocapture(ptr nocapture %src)
 
   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 3, ptr nocapture %src)
   %2 = call i32 @use_nocapture(ptr nocapture %dest)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %dest)
   ret void
 }
 
 ; Do not merge or crash if the different block user comes first.
 define void @crash_store63851(i1 %b) {
 ; CHECK-LABEL: define void @crash_store63851
 ; CHECK-SAME: (i1 [[B:%.*]]) {
-; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO:%.*]], align 8
-; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO]], align 8
-; CHECK-NEXT:    store i32 0, ptr [[DEST]], align 4
+; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 8
+; CHECK-NEXT:    store i32 0, ptr [[SRC]], align 4
 ; CHECK-NEXT:    br i1 [[B]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[T:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr [[DEST]], ptr [[SRC]], i64 12, i1 false)
 ; CHECK-NEXT:    [[T3:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
-; CHECK-NEXT:    [[T4:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[DEST]])
+; CHECK-NEXT:    [[T4:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
 ; CHECK-NEXT:    br label [[ELSE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    ret void
 ;
   %dest = alloca %struct.Foo, align 8
   %src = alloca %struct.Foo, align 8
   store i32 0, ptr %dest, align 4
   br i1 %b, label %then, label %else