[MemCpyOpt] implement forward dataflow sensitive stack-move optimization

[khei4]

Summary

This extends stack-move optimization https://reviews.llvm.org/D155406 in a more forward dataflow-sensitive way. This patch enables the merging of the following cases.

• Memory locations are fully overwritten(called a Def) and read from the same alias.
• Conflicts never happen for any execution path, although both the src and dest are used after the copy.

The implementation difference from https://reviews.llvm.org/D155406 is

• Add ModState, which represents which of src or dest finally modify the memory location in the dataflow.
  • Propagate it on the CFG, only seeing the same memory location users collected by User tracking on CaptureTracking.
• Remove reachability or Dominator relations checks on the ModRef checks.

This patch is expected to cover all stack move cases originally covered by pcwalton's patch.

There seem to be almost no compile-time regressions. https://llvm-compile-time-tracker.com/compare.php?from=f61ed5180ebb0dfe840722c6c99244f90d3183f9&to=c0c251970ef118ce15b012ea3d45deab862396c9&stat=instructions:u

[khei4]

Update comments and debug macros

[khei4]

Rebase for test fix

[arsenm]

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1435

Early return and reduce indent

1445

I think these are supposed to just be unsigned, no < 0 check?

1455

Don't need the .getFixedValue()?

1584–1588

This is redundant with getAllocationSize being nullopt

[khei4]

• return early
• remove .getFixedValue for optional TypeSize comparison
• add comments

[khei4]

Thank you for the review!

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1445

It seems like there exist negative args. https://github.com/llvm/llvm-project/blob/b86d3cbc1288b4d0799746c82611d17888413aec/llvm/test/Analysis/StackSafetyAnalysis/lifetime.ll#L14 For variable length?

1455

No. Thanks!

1584–1588

This might not be very clear(I added comment), but this was to bail out for inalloca(stacksave/stackrestore) cases like
https://github.com/llvm/llvm-project/blob/b86d3cbc1288b4d0799746c82611d17888413aec/llvm/test/Transforms/MemCpyOpt/stack-move.ll#L1134-L1139
It seems like the size nullopt check isn't sufficient to bail out for this...

[nikic]

Just some style notes, I haven't tried to understand the algorithm yet.

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1425

This should be in an anonymous namespace.

1433

Should be static.

1433

We shouldn't need std::optional here, at this point we know the alloca is sized.

1454

Does this actually do anything? It seems like the lifetime handling in CheckModRefConflict will skip this code path already.

1481

Could use BitmaskEnum.h here instead?

1501

static

Is passing the map by value here intentional?

[khei4]

• use BitMaskEnum
• pass by-ref for mistakenly passed by-val
• unwrap optional on CheckModRefConflict

[khei4]

Thank you for the review!

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1454

Does this actually do anything? It seems like the lifetime handling in CheckModRefConflict will skip this code path already.

No for current cases, as you see! We can erase this for now. Although conceptually current handling for lifetime intrinsic(completely ignore it and shrinkwrap after that) in CheckModRefConflict seems unique, this IsDef concept is not a general method or framework now.

1501

Is passing the map by value here intentional?

No. Thanks for good catch!

[khei4]

rebase for main and the parent revision change

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

 //===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass performs various transformations related to eliminating memcpy
 // calls, or transforming sets of stores into memset's.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
+#include "llvm/ADT/BitmaskEnum.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/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 <map>
 #include <optional>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "memcpyopt"
 
 static cl::opt<bool> EnableMemCpyOptWithoutLibcalls(
     "enable-memcpyopt-without-libcalls", cl::Hidden,
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;
 }
 
+// Helper for stack-move optimization,
+namespace {
+
+// Comparator and maps for stack move optimization's forward dataflow analysis
+// in each BB.
+struct InstCmp {
+  bool operator()(const Instruction *L, const Instruction *R) const {
+    return L->comesBefore(R);
+  };
+};
+using InstModRefMap =
+    std::map<Instruction *, std::pair<ModRefInfo, ModRefInfo>, InstCmp>;
+using BasicBlockInstModRefMap = DenseMap<BasicBlock *, InstModRefMap>;
+
+// We treat full-sized overwrite for alloca as a Def instruction on stack-move
+// optimization, it ensures later read from same alias cause no conflicts, even
+// if it's modified by others before Def.
+static bool IsDef(Instruction *UI, TypeSize AllocaSize, const DataLayout &DL) {
+
+  // Stores that overwrite all bytes of the alloca are definitions.
+  if (auto *SI = dyn_cast<StoreInst>(UI);
+      SI && DL.getTypeStoreSize(SI->getValueOperand()->getType()) == AllocaSize)
+    return true;
+  auto *II = dyn_cast<IntrinsicInst>(UI);
+  if (!II)
+    return false;
+
+  // We don't need to handle lifetime intrinsics for now because lifetime
+  // intrinsic calls are deleted and shrinkwrapped if the optimization succeeds.
+  // We can 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.
+  if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(II)) {
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getLength()))
+      if (CI->getZExtValue() == AllocaSize)
+        return true;
+  }
+  return false;
+}
+
+// States to represent the alias which modified memory locatoin on the forward
+// dataflow ModRef analysis.
+enum ModState {
+  NoMod = 0,
+  SrcMod = 1,
+  DestMod = 2,
+  // BothMod = SrcMod | DestMod
+  LLVM_MARK_AS_BITMASK_ENUM(DestMod)
+};
+
+} // namespace
+// Represent the ModState change before and after the BB. We should only see
+// possible comobination for pairs of BasicBlcok and ModState on BB's entry.
+using BasicBlockModSet = std::set<std::pair<BasicBlock *, ModState>>;
+
+// Performs dataflow analysis for an alloca at the basic block level as
+// part of the stack-move optimization.
+
+// This checks the consistency; there is no existence for read for write from
+// other alias, assuming src and dest alloca is merged, propagating ModState
+// information forward from alloca. This algorithm has O(Number for src or dest
+// users) complexity.
+bool CheckModRefConflict(BasicBlockInstModRefMap BBInstModRefMap,
+                         AllocaInst *AI, Instruction *Store,
+                         const DataLayout &DL) {
+  // We can guarantee this Alloca is sized, if already here.
+  TypeSize AllocaSize = AI->getAllocationSize(DL).value();
+  BasicBlock *AllocaBB = AI->getParent();
+  SmallVector<std::pair<BasicBlock *, ModState>, 8> Worklist;
+  BasicBlockModSet BBModSet;
+  Worklist.push_back({AllocaBB, ModState::NoMod});
+
+  while (!Worklist.empty()) {
+    auto &[BB, BeforeMS] = Worklist.back();
+    Worklist.pop_back();
+    ModState AfterMS = BeforeMS;
+
+    // Compute the modref effect for this BB start with BeforeMS.
+    for (auto &[I, MR] : BBInstModRefMap[BB]) {
+      auto &[DestMR, SrcMR] = MR;
+      // Just ignore full-sized lifetime intrinsics because, we would remove
+      // those if we have no conflict except those.
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
+          II && II->isLifetimeStartOrEnd()) {
+        int64_t Size = cast<ConstantInt>(II->getArgOperand(0))->getSExtValue();
+        if (Size < 0 || uint64_t(Size) == AllocaSize)
+          continue;
+      }
+
+      // FIXME: lifetime intrinsics is both ModRef by ModRefInfo, but this
+      // should be only Mod.
+      if (((AfterMS & ModState::SrcMod) && isRefSet(DestMR)) ||
+          ((AfterMS & ModState::DestMod) && isRefSet(SrcMR))) {
+        LLVM_DEBUG(dbgs() << "Stack Move: Detected ModRef conflict,"
+                             "\n  Basic Block: "
+                          << BB->getNameOrAsOperand() << "\n"
+                          << "\n  Instruction: " << I << "\n");
+        return false;
+      }
+
+      // For the Store, we can see the mod state is renewed.TODO: more
+      // generally, full-sizeed  copy between src and dest would be this.
+      if (I == Store) {
+        AfterMS = ModState::NoMod;
+      } else if (IsDef(I, AllocaSize, DL)) { // if the instruction is Def, other one's mod is erased
+        if (isModSet(DestMR))
+          AfterMS = ModState::DestMod;
+        else if (isModSet(SrcMR))
+          AfterMS = ModState::SrcMod;
+      } else if (isModSet(DestMR))
+        AfterMS |= ModState::DestMod;
+      else if (isModSet(SrcMR))
+        AfterMS |= ModState::SrcMod;
+    }
+    BBModSet.insert({BB, BeforeMS});
+
+    for (BasicBlock *Succ : successors(BB)) {
+      if (BBModSet.find({Succ, AfterMS}) != BBModSet.end())
+        continue;
+      Worklist.push_back({Succ, AfterMS});
+    }
+  }
+  return true;
+}
+
 // 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"
bool MemCpyOptPass::performStackMoveOptzn(Instruction *Load, Instruction *Store,
   }
   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;
   }
 
-  if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca())
+  // Check that allocas are not static alloca (e.g. inalloca) to avoid
+  // stacksave/stackrestore.
+  if (!SrcAlloca->isStaticAlloca() || !DestAlloca->isStaticAlloca()) {
+    LLVM_DEBUG(
+        dbgs() << "Stack Move: Non static allocas couldn't be handled.\n");
     return false;
+  }
 
   // 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;
   SmallSet<Instruction *, 4> NoAliasInstrs;
while (!Worklist.empty()) {
               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:
           // Instructions cannot have non-instruction users.
           Worklist.push_back(UI);
           continue;
         case UseCaptureKind::NO_CAPTURE: {
           if (UI->isLifetimeStartOrEnd()) {
             // We note the locations of these intrinsic calls so that we can
while (!Worklist.empty()) {
             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;
+  BasicBlockInstModRefMap BBInstModRefMap;
+
   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 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());
-      }
-    }
+    BBInstModRefMap[UI->getParent()].insert({UI, {Res, ModRefInfo::NoModRef}});
     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;
 
-  // 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;
+    if (BBInstModRefMap.count(UI->getParent()))
+      BBInstModRefMap[UI->getParent()][UI].second = Res;
+    else
+      BBInstModRefMap[UI->getParent()].insert(
+          {UI, {ModRefInfo::NoModRef, Res}});
 
     return true;
   };
 
   if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback))
     return false;
 
+  if (!CheckModRefConflict(BBInstModRefMap, SrcAlloca, Store, DL))
+    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);
 

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

;
   call void @llvm.lifetime.start.p0(i64 12, ptr nocapture %src)
   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)
   call void @llvm.lifetime.end.p0(i64 12, ptr nocapture %src)
   %v = load i32, ptr %dest
   ret void
 }
 
-; TODO: if the last user is terminator, we won't insert lifetime.end.
 ; For multi-bb patch, we will insert it for next immediate post dominator block.
 define void @terminator_lastuse() personality i32 0 {
 ; CHECK-LABEL: define void @terminator_lastuse() personality i32 0 {
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
 ; 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:    [[RV:%.*]] = invoke i32 @use_nocapture(ptr [[SRC]])
 ; CHECK-NEXT:    to label [[SUC:%.*]] unwind label [[UNW:%.*]]

 
 }
 
 ; Test for BasicBlock and Instruction mixed dominator finding.
 define void @multi_bb_dom_test1(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_dom_test1
 ; CHECK-SAME: (i1 [[B:%.*]]) {
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
-; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
 ; 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:    ret void
 ; CHECK:       unr:
-; 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]]
 ;
   %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
unr1:
   br label %unr2
 
 unr2:
   %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   br label %unr1
 
 }
 
-; 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:    store [[STRUCT_FOO]] { i32 0, i32 1, i32 42 }, ptr [[SRC]], align 4
 ; CHECK-NEXT:    br i1 [[NLT1]], label [[LOOP_EXIT:%.*]], label [[LOOP_BODY:%.*]]
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:    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:    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:    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:    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:    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:    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)
   %2 = load i32, ptr %src
   store i32 %2, ptr %dest
   %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
   store i32 64, ptr %src
   %4 = call i32 @use_nocapture(ptr noundef nocapture %src)
   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 src and dest, because any execution path doesn't cause conflicts.
 ; Tests that exists modref for both src/dest, but it never conflict on the execution.
 define void @multi_bb_dataflow(i1 %b) {
 ; CHECK-LABEL: define void @multi_bb_dataflow
 ; CHECK-SAME: (i1 [[B:%.*]]) {
 ; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
-; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[SRC]])
-; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 12, ptr nocapture [[DEST]])
 ; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[SRC]])
-; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 false)
 ; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb0:
 ; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr nocapture noundef [[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:    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)