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

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
; RUN: opt < %s -passes=memcpyopt -verify-memoryssa -S | FileCheck %s

%struct.Foo = type { i32, i32, i32 }

declare void @llvm.memcpy.p0.p0.i64(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg)
declare void @llvm.memcpy.p1.p0.i64(ptr addrspace(1) noalias nocapture writeonly, ptr noalias nocapture readonly, i64, i1 immarg)
declare void @llvm.memcpy.p2.p1.i64(ptr addrspace(2) noalias nocapture writeonly, ptr addrspace(1) noalias nocapture readonly, i64, i1 immarg)
declare void @llvm.memmove.p0.p0.i64(ptr nocapture writeonly, ptr nocapture readonly, i64, i1 immarg)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg)

declare void @llvm.lifetime.start.p0(ptr nocapture)
declare void @llvm.lifetime.end.p0(ptr nocapture)
declare void @llvm.lifetime.start.p1(ptr addrspace(1) nocapture)
declare void @llvm.lifetime.end.p1(ptr addrspace(1) nocapture)
declare void @llvm.lifetime.start.p2(ptr addrspace(2) nocapture)
declare void @llvm.lifetime.end.p2(ptr addrspace(2) nocapture)

declare i32 @use_nocapture(ptr nocapture)
declare i32 @use_maycapture(ptr noundef)
declare i32 @use_readonly(ptr readonly)
declare i32 @use_writeonly(ptr noundef) memory(write)

define void @basic_memcpy() {
; CHECK-LABEL: define void @basic_memcpy() {
; 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

  %2 = call i32 @use_nocapture(ptr nocapture %dest)

  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

define i32 @use_not_dominated_by_src_alloca() {
; CHECK-LABEL: define i32 @use_not_dominated_by_src_alloca() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i8, align 4
; CHECK-NEXT:    [[DEST_GEP:%.*]] = getelementptr i64, ptr [[SRC]], i64 -1
; CHECK-NEXT:    [[DEST_USE:%.*]] = load i8, ptr [[DEST_GEP]], align 1
; CHECK-NEXT:    ret i32 0
;
  %dest = alloca i1, align 1
  ; Replacing the use of dest with src causes no domination uses.
  %dest.gep = getelementptr i64, ptr %dest, i64 -1
  %dest.use = load i8, ptr %dest.gep, align 1
  %src = alloca i8, align 4
  %src.val = load i1, ptr %src, align 4

  store i1 %src.val, ptr %dest, align 1

  ret i32 0
}

define void @basic_memmove() {
; CHECK-LABEL: define void @basic_memmove() {
; 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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.memmove.p0.p0.i64(ptr align 4 %dest, ptr align 4 %src, i64 12, i1 false)

  %2 = call i32 @use_nocapture(ptr nocapture %dest)

  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that the optimization succeeds with a load/store pair.
define void @load_store() {
; CHECK-LABEL: define void @load_store() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i32, align 4
; CHECK-NEXT:    store i32 42, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca i32, align 4
  %dest = alloca i32, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store i32 42, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src)

  %src.val = load i32, ptr %src
  store i32 %src.val, ptr %dest

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

; Test scalable vectors.
define void @load_store_scalable(<vscale x 4 x i32> %x) {
; CHECK-LABEL: define void @load_store_scalable
; CHECK-SAME: (<vscale x 4 x i32> [[X:%.*]]) {
; CHECK-NEXT:    [[SRC:%.*]] = alloca <vscale x 4 x i32>, align 16
; CHECK-NEXT:    store <vscale x 4 x i32> [[X]], ptr [[SRC]], align 16
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca <vscale x 4 x i32>
  %dest = alloca <vscale x 4 x i32>
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store <vscale x 4 x i32> %x, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src)

  %src.val = load <vscale x 4 x i32>, ptr %src
  store <vscale x 4 x i32> %src.val, ptr %dest

  %2 = call i32 @use_nocapture(ptr nocapture %dest)

  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that merging two allocas shouldn't be more poisonous, smaller aligned src is valid.
define void @align_up() {
; CHECK-LABEL: define void @align_up() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 8
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 8
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

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

; Tests that we correctly remove extra lifetime intrinsics when performing the
; optimization.
define void @remove_extra_lifetime_intrinsics() {
; CHECK-LABEL: define void @remove_extra_lifetime_intrinsics() {
; 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  %3 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that we won't insert lifetime markers if they don't exist originally.
define void @no_lifetime() {
; CHECK-LABEL: define void @no_lifetime() {
; 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  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)

  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  %3 = call i32 @use_nocapture(ptr nocapture %dest)
  ret void
}

; Tests that aliasing src or dest but no modification desn't prevent transformations.
define void @alias_no_mod() {
; CHECK-LABEL: define void @alias_no_mod() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST_ALIAS:%.*]] = getelementptr [[STRUCT_FOO]], ptr [[SRC]], i32 0, i32 0
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[SRC_ALIAS:%.*]] = getelementptr [[STRUCT_FOO]], ptr [[SRC]], i32 0, i32 0
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  %dest.alias = getelementptr %struct.Foo, ptr %dest, i32 0, i32 0
  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)

  %src.alias = getelementptr %struct.Foo, ptr %src, i32 0, i32 0
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Scope domain
!0 = !{!0, i1 false}
; Scope in that domain
!1 = !{!1, !0}
; Scope list
!2 = !{!1}

!3 = !{!"Whatever"}

; Tests that we remove scoped noalias metadata from a call.
define void @remove_scoped_noalias() {
; CHECK-LABEL: define void @remove_scoped_noalias() {
; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src), !alias.scope !2

  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(ptr nocapture %src)
  %2 = call i32 @use_nocapture(ptr nocapture %dest), !noalias !2
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that we remove metadata on the merged alloca.
define void @remove_alloca_metadata() {
; CHECK-LABEL: define void @remove_alloca_metadata() {
; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4, !annotation !3
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src), !alias.scope !2

  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 nocapture %dest), !noalias !2
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that we remove scoped noalias metadata from a call.
; And confirm that don't crash on noalias metadata on lifetime markers.
define void @noalias_on_lifetime() {
; CHECK-LABEL: define void @noalias_on_lifetime() {
; 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:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src), !alias.scope !2

  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(ptr nocapture %src), !alias.scope !2
  %2 = call i32 @use_nocapture(ptr nocapture %dest), !noalias !2
  call void @llvm.lifetime.end.p0(ptr nocapture %dest), !noalias !2
  ret void
}

; Tests that we can merge alloca if the dest and src has only refs except lifetime intrinsics.
define void @src_ref_dest_ref_after_copy() {
; CHECK-LABEL: define void @src_ref_dest_ref_after_copy() {
; 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_readonly(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_readonly(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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 %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that we can merge alloca if the dest and src has only mods.
define void @src_mod_dest_mod_after_copy() {
; CHECK-LABEL: define void @src_mod_dest_mod_after_copy() {
; 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_writeonly(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_writeonly(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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_writeonly(ptr nocapture %src)
  %2 = call i32 @use_writeonly(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

define void @avoid_memory_use_last_user_crash() {
; CHECK-LABEL: define void @avoid_memory_use_last_user_crash() {
; 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:    [[V:%.*]] = load i32, ptr [[SRC]], align 4
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  %v = load i32, ptr %dest
  ret void
}

; 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[RV:%.*]] = invoke i32 @use_nocapture(ptr [[SRC]])
; CHECK-NEXT:            to label [[SUC:%.*]] unwind label [[UNW:%.*]]
; CHECK:       unw:
; CHECK-NEXT:    [[LP:%.*]] = landingpad i32
; CHECK-NEXT:            cleanup
; CHECK-NEXT:    resume i32 0
; CHECK:       suc:
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr %src)
  %rv = invoke i32 @use_nocapture(ptr %dest)
  to label %suc unwind label %unw
unw:
  %lp = landingpad i32 cleanup
  resume i32 0
suc:
  ret void
}

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:    store i32 42, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB0:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    br label [[BB1:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca i32, align 4
  %dest = alloca i32, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

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:    store i32 42, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB0:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca i32, align 4
  %dest = alloca i32, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store i32 42, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src)

  %src.val = load i32, ptr %src
  store i32 %src.val, ptr %dest
  br label %bb0

bb0:
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; FIXME: merge allocas for bb-separated, but logically straight.
; We might be handle those load/store MemCpyOpt totally
define void @multi_bb_separated_load_store(i1 %b) {
; CHECK-LABEL: define void @multi_bb_separated_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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store i32 42, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[SRC_VAL:%.*]] = load i32, ptr [[SRC]], align 4
; CHECK-NEXT:    br label [[BB0:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    store i32 [[SRC_VAL]], ptr [[DEST]], align 4
; CHECK-NEXT:    br label [[BB1:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca i32, align 4
  %dest = alloca i32, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store i32 42, ptr %src
  %1 = call i32 @use_nocapture(ptr nocapture %src)

  %src.val = load i32, ptr %src
  br label %bb0

bb0:
  store i32 %src.val, ptr %dest
  br label %bb1

bb1:
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

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:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)
  br i1 %b, label %bb0, label %bb1

bb0:
  %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %bb2

bb1:
  %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %bb2

bb2:
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  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:    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:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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
  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(ptr nocapture %dest)
  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 noundef nocapture %dest)

  ret void

}

; 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(ptr captures(none) [[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 noundef captures(none) [[DEST]])
; CHECK-NEXT:    ret void
; CHECK:       unr:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[DEST]])
; 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
  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(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

unr:
  %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %bb2
}

; 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:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(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(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:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    br i1 [[B]], label [[BB0:%.*]], label [[BB1:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 42, [[BB0]] ], [ 41, [[BB1]] ]
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(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

}

; Test for existing unreachable cycle
define void @multi_bb_pdom_test2(i1 %b) {
; CHECK-LABEL: define void @multi_bb_pdom_test2
; CHECK-SAME: (i1 [[B:%.*]]) {
; 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 noundef captures(none) [[SRC]])
; CHECK-NEXT:    ret void
; CHECK:       unr1:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[UNR2:%.*]]
; CHECK:       unr2:
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[UNR1:%.*]]
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(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
  %1 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  ret void

unr1:
  %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %unr2

unr2:
  %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %unr1

}

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:%.*]]
; CHECK:       loop_body:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[NEW_I:%.*]], [[LOOP_BODY]] ], [ 1, [[ENTRY:%.*]] ]
; 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:    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(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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
}

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:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br i1 [[B0]], label [[BB0:%.*]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    ret void
; CHECK:       bb0:
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

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:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br i1 [[B0]], label [[BB0:%.*]], label [[BB1:%.*]]
; CHECK:       bb0:
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)
  br label %bb2

bb2:
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[SRC]], ptr align 4 [[DEST]], i64 12, i1 false)
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[DEST]])
; 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 noundef captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store i32 42, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[DEST]])
; CHECK-NEXT:    store i32 64, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP4:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca i32, align 4
  %dest = alloca i32, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[DEST]])
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)
  br i1 %b, label %bb0, label %bb1

bb0:
  %2 = call i32 @use_nocapture(ptr noundef nocapture %src)
  br label %bb2

bb1:
  %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %bb2

bb2:
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests merging allocas with different sizes
define void @mismatched_alloca_size() {
; CHECK-LABEL: define void @mismatched_alloca_size() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i8, i64 24, 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca i8, i64 24, align 4
  %dest = alloca i8, i64 12, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

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


; Optimization failures follow:

; Tests that a memcpy that doesn't completely overwrite a stack value is a use
; for the purposes of liveness analysis, not a definition.
define void @incomplete_memcpy() {
; CHECK-LABEL: define void @incomplete_memcpy() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 11, i1 false)
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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 11, i1 false)
  %2 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that a store that doesn't completely overwrite a stack value is a use
; for the purposes of liveness analysis, not a definition.
define void @incomplete_store() {
; CHECK-LABEL: define void @incomplete_store() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, 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)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests merging allocas with different types
define void @mismatched_alloca_type() {
; CHECK-LABEL: define void @mismatched_alloca_type() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i16, i64 6, 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca i16, i64 6, align 4
  %dest = alloca i8, i64 12, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

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

; Tests merging allocas with different types and sizes
define void @mismatched_alloca_type_size() {
; CHECK-LABEL: define void @mismatched_alloca_type_size() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i16, i64 12, 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 captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca i16, i64 12, align 4
  %dest = alloca i8, i64 12, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

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

; Tests that dynamically-sized allocas are never merged.
define void @dynamically_sized_alloca(i64 %i) {
; CHECK-LABEL: define void @dynamically_sized_alloca
; CHECK-SAME: (i64 [[I:%.*]]) {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i8, i64 [[I]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca i8, i64 [[I]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO:%.*]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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 captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca i8, i64 %i, align 4
  %dest = alloca i8, i64 %i, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

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


; Tests that inalloca attributed allocas are never merged, to prevent stacksave/stackrestore handling.
define void @inalloca() {
; CHECK-LABEL: define void @inalloca() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca inalloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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 captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca inalloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

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

; Tests that a memcpy with a dynamic size is never optimized.
define void @dynamically_sized_memcpy(i64 %size) {
; CHECK-LABEL: define void @dynamically_sized_memcpy
; CHECK-SAME: (i64 [[SIZE:%.*]]) {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 [[SIZE]], i1 false)
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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 %size, i1 false)

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


; Tests that allocas with mismatched address spaces aren't combined.
define void @mismatched_alloca_addrspace() {
; CHECK-LABEL: define void @mismatched_alloca_addrspace() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca i8, i64 24, align 4, addrspace(1)
; CHECK-NEXT:    [[DEST:%.*]] = alloca i8, i64 12, align 4, addrspace(2)
; CHECK-NEXT:    call void @llvm.lifetime.start.p1(ptr addrspace(1) captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p2(ptr addrspace(2) captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO:%.*]] { i32 10, i32 20, i32 30 }, ptr addrspace(1) [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr addrspace(1) captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.memcpy.p2.p1.i64(ptr addrspace(2) align 4 [[DEST]], ptr addrspace(1) align 4 [[SRC]], i64 12, i1 false)
; CHECK-NEXT:    call void @llvm.lifetime.end.p1(ptr addrspace(1) captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr addrspace(2) captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p2(ptr addrspace(2) captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca i8, i64 24, align 4, addrspace(1)
  %dest = alloca i8, i64 12, align 4, addrspace(2)
  call void @llvm.lifetime.start.p1(ptr addrspace(1) nocapture %src)
  call void @llvm.lifetime.start.p2(ptr addrspace(2) nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr addrspace(1) %src
  %1 = call i32 @use_nocapture(ptr addrspace(1) nocapture %src)

  call void @llvm.memcpy.p2.p1.i64(ptr addrspace(2) align 4 %dest, ptr addrspace(1) align 4 %src, i64 12, i1 false)

  call void @llvm.lifetime.end.p1(ptr addrspace(1) nocapture %src)
  %2 = call i32 @use_nocapture(ptr addrspace(2) nocapture %dest)
  call void @llvm.lifetime.end.p2(ptr addrspace(2) nocapture %dest)
  ret void
}

; Tests that volatile memcpys aren't removed.
define void @volatile_memcpy() {
; CHECK-LABEL: define void @volatile_memcpy() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DEST]], ptr align 4 [[SRC]], i64 12, i1 true)
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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 true)

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

; Tests that the optimization isn't performed when the destination is captured.
define void @dest_captured() {
; CHECK-LABEL: define void @dest_captured() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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_maycapture(ptr [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)
  %2 = call i32 @use_maycapture(ptr %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that the optimization isn't performed when the source is captured.
define void @src_captured() {
; CHECK-LABEL: define void @src_captured() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_maycapture(ptr [[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 captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  %1 = call i32 @use_maycapture(ptr %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 nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that failure if any modref exists before the copy,
; Exactly ref seems safe because no mod say ref would be always undefined, but to make simple and conservative.
define void @mod_ref_before_copy() {
; CHECK-LABEL: define void @mod_ref_before_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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[R:%.*]] = call i32 @use_readonly(ptr captures(none) [[DEST]])
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  %r = call i32 @use_readonly(ptr nocapture %dest)
  %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(ptr nocapture %src)
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that failure because copy semantics will change if dest is replaced with src.
define void @mod_dest_before_copy() {
; CHECK-LABEL: define void @mod_dest_before_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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    store i32 13, ptr [[DEST]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  store i32 13, ptr %dest
  %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(ptr nocapture %src)
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

define void @mod_src_before_store_after_load() {
; CHECK-LABEL: define void @mod_src_before_store_after_load() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    store i32 13, ptr [[DEST]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; 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:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  store i32 13, ptr %dest
  %1 = call i32 @use_nocapture(ptr nocapture %src)

  %src.val = load %struct.Foo, ptr %src
  store %struct.Foo { i32 13, i32 13, i32 13 }, ptr %src
  store %struct.Foo %src.val, ptr %dest

  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; 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 captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; 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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; 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:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that failure because alloca is modified through aliases, which requires recursive user ModRefChecks
define void @dest_alias_mod_before_copy() {
; CHECK-LABEL: define void @dest_alias_mod_before_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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[DEST_ALIAS:%.*]] = getelementptr inbounds [[STRUCT_FOO]], ptr [[DEST]], i64 0, i32 1
; CHECK-NEXT:    store i32 13, ptr [[DEST_ALIAS]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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 captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(ptr nocapture %dest)
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  %dest.alias = getelementptr inbounds %struct.Foo, ptr %dest, i64 0, i32 1
  store i32 13, ptr %dest.alias
  %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)

  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[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:    store i32 13, ptr [[DEST_ALIAS]], align 4
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)

  %dest.alias = getelementptr inbounds %struct.Foo, ptr %dest, i64 0, i32 1
  store i32 13, ptr %dest.alias
  %2 = call i32 @use_nocapture(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; Tests that the optimization isn't performed when the source and destination
; have mod ref conflict on bb2.
define void @multi_bb_dataflow_conflict(i1 %b) {
; CHECK-LABEL: define void @multi_bb_dataflow_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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[SRC]])
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[DEST]])
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    [[TMP4:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[DEST]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.end.p0(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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)
  br i1 %b, label %bb0, label %bb1

bb0:
  %2 = call i32 @use_nocapture(ptr noundef nocapture %src)
  br label %bb2

bb1:
  %3 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  br label %bb2

bb2:
  %4 = call i32 @use_nocapture(ptr noundef nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(ptr nocapture %dest)
  ret void
}

; 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(ptr captures(none) [[SRC]])
; CHECK-NEXT:    call void @llvm.lifetime.start.p0(ptr captures(none) [[DEST]])
; 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:    [[IGTN:%.*]] = icmp sgt i32 [[NEW_I]], [[N]]
; CHECK-NEXT:    br i1 [[IGTN]], label [[LOOP_EXIT]], label [[LOOP_BODY]]
; CHECK:       loop_exit:
; 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(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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 %dest
  %igtn = icmp sgt i32 %new_i, %n
  br i1 %igtn, label %loop_exit, label %loop_body

loop_exit:
  ret void
}

; Tests that partial-sized lifetimes are not inhibiting the optimizer
define void @partial_lifetime() {
; CHECK-LABEL: define void @partial_lifetime() {
; CHECK-NEXT:    [[DEST:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[DEST]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @use_nocapture(ptr captures(none) [[DEST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dest = alloca %struct.Foo, align 4
  call void @llvm.lifetime.start.p0(ptr nocapture %src)
  call void @llvm.lifetime.start.p0(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(ptr nocapture %src)
  %2 = call i32 @use_nocapture(ptr nocapture %dest)
  call void @llvm.lifetime.end.p0(ptr nocapture %src)
  call void @llvm.lifetime.end.p0(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:    br i1 [[B]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    [[T:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[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 noundef captures(none) [[SRC]])
; CHECK-NEXT:    [[T4:%.*]] = call i32 @use_nocapture(ptr noundef captures(none) [[DEST]])
; 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

then:                                             ; preds = %entry
  %t = call i32 @use_nocapture(ptr nocapture noundef %src)
  call void @llvm.memcpy.p0.p0.i64(ptr %dest, ptr %src, i64 12, i1 false)
  %t3 = call i32 @use_nocapture(ptr nocapture noundef %src)
  %t4 = call i32 @use_nocapture(ptr nocapture noundef %dest)
  br label %else

else:                                             ; preds = %then, %entry
  ret void

  uselistorder ptr %dest, { 1, 2, 0 }
}

declare ptr @captures_ret_only(ptr captures(ret: address, provenance))

define i32 @test_ret_only_capture() {
; CHECK-LABEL: define i32 @test_ret_only_capture() {
; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
; CHECK-NEXT:    store i32 0, ptr [[A]], align 4
; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr [[B]], ptr [[A]], i64 4, i1 false)
; CHECK-NEXT:    call void @captures_ret_only(ptr [[B]])
; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    ret i32 [[V]]
;
  %a = alloca i32
  %b = alloca i32
  store i32 0, ptr %a
  call void @llvm.memcpy(ptr %b, ptr %a, i64 4, i1 false)
  call void @captures_ret_only(ptr %b)
  %v = load i32, ptr %a
  ret i32 %v
}

declare ptr @captures_address_only(ptr captures(address))

; Can transform: Only one address captured.
define void @test_captures_address_captures_none() {
; CHECK-LABEL: define void @test_captures_address_captures_none() {
; 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:    call void @captures_address_only(ptr [[SRC]])
; CHECK-NEXT:    call void @use_nocapture(ptr [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dst = alloca %struct.Foo, align 4
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  call void @captures_address_only(ptr %src)
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dst, ptr align 4 %src, i64 12, i1 false)
  call void @use_nocapture(ptr %dst)
  ret void
}

; Can transform: Only one address captured.
define void @test_captures_none_and_captures_address() {
; CHECK-LABEL: define void @test_captures_none_and_captures_address() {
; 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:    call void @use_nocapture(ptr [[SRC]])
; CHECK-NEXT:    call void @captures_address_only(ptr [[SRC]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dst = alloca %struct.Foo, align 4
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  call void @use_nocapture(ptr %src)
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dst, ptr align 4 %src, i64 12, i1 false)
  call void @captures_address_only(ptr %dst)
  ret void
}

; Cannot transform: Both addresses captured.
define void @test_captures_address_and_captures_address() {
; CHECK-LABEL: define void @test_captures_address_and_captures_address() {
; CHECK-NEXT:    [[SRC:%.*]] = alloca [[STRUCT_FOO:%.*]], align 4
; CHECK-NEXT:    [[DST:%.*]] = alloca [[STRUCT_FOO]], align 4
; CHECK-NEXT:    store [[STRUCT_FOO]] { i32 10, i32 20, i32 30 }, ptr [[SRC]], align 4
; CHECK-NEXT:    call void @captures_address_only(ptr [[SRC]])
; CHECK-NEXT:    call void @llvm.memcpy.p0.p0.i64(ptr align 4 [[DST]], ptr align 4 [[SRC]], i64 12, i1 false)
; CHECK-NEXT:    call void @captures_address_only(ptr [[DST]])
; CHECK-NEXT:    ret void
;
  %src = alloca %struct.Foo, align 4
  %dst = alloca %struct.Foo, align 4
  store %struct.Foo { i32 10, i32 20, i32 30 }, ptr %src
  call void @captures_address_only(ptr %src)
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %dst, ptr align 4 %src, i64 12, i1 false)
  call void @captures_address_only(ptr %dst)
  ret void
}