test/Transforms/LoopVectorize/VPlan/cse-loads.ll

; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --filter-out-after "middle.block" --version 6
; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 \
; RUN:     -disable-output -vplan-print-after="printFinalVPlan$" %s 2>&1 | FileCheck %s
; REQUIRES: asserts

; Tests CSE of duplicate widened loads.

; Two identical loads from the same address are CSE'd into one.
define void @cse_duplicate_load(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'cse_duplicate_load'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep.a> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep.a>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%x>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep.a = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep.a, align 4
  %y = load i32, ptr %gep.a, align 4
  %sum = add i32 %x, %y
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; Three identical loads from the same address collapse to a single load.
define void @cse_three_duplicate_loads(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'cse_three_duplicate_loads'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep.a> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep.a>
; CHECK-NEXT:    WIDEN ir<%t> = add ir<%x>, ir<%x>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%t>, ir<%x>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep.a = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep.a, align 4
  %y = load i32, ptr %gep.a, align 4
  %z = load i32, ptr %gep.a, align 4
  %t = add i32 %x, %y
  %sum = add i32 %t, %z
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; Two independent groups of duplicate loads are each CSE'd.
define void @two_dup_groups(ptr noalias %a, ptr noalias %b, ptr noalias %out) {
; CHECK-LABEL: VPlan for loop in 'two_dup_groups'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%pa> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%a1> = load ir<%pa>
; CHECK-NEXT:    CLONE ir<%pb> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%b1> = load ir<%pb>
; CHECK-NEXT:    WIDEN ir<%sa> = add ir<%a1>, ir<%a1>
; CHECK-NEXT:    WIDEN ir<%sb> = add ir<%b1>, ir<%b1>
; CHECK-NEXT:    WIDEN ir<%s> = add ir<%sa>, ir<%sb>
; CHECK-NEXT:    CLONE ir<%po> = getelementptr inbounds ir<%out>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%po>, ir<%s>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %pa = getelementptr inbounds i32, ptr %a, i64 %iv
  %a1 = load i32, ptr %pa, align 4
  %a2 = load i32, ptr %pa, align 4
  %pb = getelementptr inbounds i32, ptr %b, i64 %iv
  %b1 = load i32, ptr %pb, align 4
  %b2 = load i32, ptr %pb, align 4
  %sa = add i32 %a1, %a2
  %sb = add i32 %b1, %b2
  %s = add i32 %sa, %sb
  %po = getelementptr inbounds i32, ptr %out, i64 %iv
  store i32 %s, ptr %po, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; A duplicate load and the duplicate add depending on it are both CSE'd.
define void @load_then_dup_add(ptr noalias %a, ptr noalias %out) {
; CHECK-LABEL: VPlan for loop in 'load_then_dup_add'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%p> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%p>
; CHECK-NEXT:    WIDEN ir<%ax> = add ir<%x>, ir<7>
; CHECK-NEXT:    WIDEN ir<%m> = mul ir<%ax>, ir<%ax>
; CHECK-NEXT:    CLONE ir<%po> = getelementptr inbounds ir<%out>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%po>, ir<%m>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %p = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %p, align 4
  %y = load i32, ptr %p, align 4
  %ax = add i32 %x, 7
  %ay = add i32 %y, 7
  %m = mul i32 %ax, %ay
  %po = getelementptr inbounds i32, ptr %out, i64 %iv
  store i32 %m, ptr %po, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; A store between two loads prevents CSE of the second load.
define void @no_cse_across_store(ptr %a) {
; CHECK-LABEL: VPlan for loop in 'no_cse_across_store'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%inc> = add ir<%x>, ir<1>
; CHECK-NEXT:    WIDEN store ir<%gep>, ir<%inc>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%sink> = add ir<%y>, ir<2>
; CHECK-NEXT:    WIDEN store ir<%gep>, ir<%sink>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep, align 4
  %inc = add i32 %x, 1
  store i32 %inc, ptr %gep, align 4
  %y = load i32, ptr %gep, align 4
  %sink = add i32 %y, 2
  %gep.s = getelementptr inbounds i32, ptr %a, i64 %iv
  store i32 %sink, ptr %gep.s, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; The store clobbers the first load, but the two loads after it are duplicates
; of each other and are still CSE'd.
define void @cse_duplicate_loads_after_store(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'cse_duplicate_loads_after_store'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%inc> = add ir<%x>, ir<1>
; CHECK-NEXT:    WIDEN store ir<%gep>, ir<%inc>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%y>, ir<%y>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep, align 4
  %inc = add i32 %x, 1
  store i32 %inc, ptr %gep, align 4
  %y = load i32, ptr %gep, align 4
  %z = load i32, ptr %gep, align 4
  %sum = add i32 %y, %z
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; Loads from different addresses are not CSE'd.
define void @no_cse_different_address(ptr noalias %a, ptr noalias %b, ptr noalias %c) {
; CHECK-LABEL: VPlan for loop in 'no_cse_different_address'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep.a> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep.a>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep.b>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%y>
; CHECK-NEXT:    CLONE ir<%gep.c> = getelementptr inbounds ir<%c>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.c>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep.a = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep.a, align 4
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  %y = load i32, ptr %gep.b, align 4
  %sum = add i32 %x, %y
  %gep.c = getelementptr inbounds i32, ptr %c, i64 %iv
  store i32 %sum, ptr %gep.c, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; Loads of different scalar types are not CSE'd.
define void @no_cse_different_type(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'no_cse_different_type'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    vp<[[VP1:%[0-9]+]]> = SCALAR-STEPS vp<%index>, ir<1>, ir<4>, ir<1>
; CHECK-NEXT:    vp<[[VP2:%[0-9]+]]> = SCALAR-STEPS vp<%index>, ir<1>, ir<4>, ir<2>
; CHECK-NEXT:    vp<[[VP3:%[0-9]+]]> = SCALAR-STEPS vp<%index>, ir<1>, ir<4>, ir<3>
; CHECK-NEXT:    CLONE ir<%gep> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    CLONE ir<%gep>.1 = getelementptr inbounds ir<%a>, vp<[[VP1]]>
; CHECK-NEXT:    CLONE ir<%gep>.2 = getelementptr inbounds ir<%a>, vp<[[VP2]]>
; CHECK-NEXT:    CLONE ir<%gep>.3 = getelementptr inbounds ir<%a>, vp<[[VP3]]>
; CHECK-NEXT:    CLONE ir<%x> = load ir<%gep>
; CHECK-NEXT:    CLONE ir<%x>.1 = load ir<%gep>.1
; CHECK-NEXT:    CLONE ir<%x>.2 = load ir<%gep>.2
; CHECK-NEXT:    CLONE ir<%x>.3 = load ir<%gep>.3
; CHECK-NEXT:    EMIT vp<[[VP4:%[0-9]+]]> = buildvector ir<%x>, ir<%x>.1, ir<%x>.2, ir<%x>.3
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep>
; CHECK-NEXT:    WIDEN-CAST ir<%xe> = zext vp<[[VP4]]> to i64
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%xe>, ir<%y>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP5:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP5]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i64, ptr %a, i64 %iv
  %x = load i32, ptr %gep, align 8
  %y = load i64, ptr %gep, align 8
  %xe = zext i32 %x to i64
  %sum = add i64 %xe, %y
  %gep.b = getelementptr inbounds i64, ptr %b, i64 %iv
  store i64 %sum, ptr %gep.b, align 8
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; The earlier load has the stronger alignment, so the later load reuses it and
; no alignment information is lost.
define void @cse_stronger_align_first(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'cse_stronger_align_first'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%x>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep, align 8
  %y = load i32, ptr %gep, align 4
  %sum = add i32 %x, %y
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; The earlier load is weaker aligned, so reusing it would drop the stronger
; alignment of the second load and CSE is skipped.
define void @no_cse_weaker_align_first(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'no_cse_weaker_align_first'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%y>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep, align 4
  %y = load i32, ptr %gep, align 8
  %sum = add i32 %x, %y
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; Two identical loads with different TBAA are CSE'd, keeping only common
; metadata.
define void @dup_load_diff_tbaa(ptr noalias %a, ptr noalias %out) {
; CHECK-LABEL: VPlan for loop in 'dup_load_diff_tbaa'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%p> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%p>{{$}}
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%x>
; CHECK-NEXT:    CLONE ir<%po> = getelementptr inbounds ir<%out>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%po>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %p = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %p, align 4, !tbaa !5
  %y = load i32, ptr %p, align 4, !tbaa !9
  %sum = add i32 %x, %y
  %po = getelementptr inbounds i32, ptr %out, i64 %iv
  store i32 %sum, ptr %po, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; A store between two loads prevents CSE of the second load.
; TODO: The store is proven not to alias the loaded address via scoped-noalias
; metadata, so the second load could be CSE'd here.
define void @no_cse_across_noalias_store(ptr %a, ptr %b) {
; CHECK-LABEL: VPlan for loop in 'no_cse_across_noalias_store'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep.a> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep.a> (!alias.scope ![[SCOPE:[0-9]+]], !noalias ![[NOALIAS:[0-9]+]])
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%x> (!alias.scope ![[NOALIAS]], !noalias ![[SCOPE]])
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep.a> (!alias.scope ![[SCOPE]], !noalias ![[NOALIAS]])
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%y>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum> (!alias.scope ![[NOALIAS]], !noalias ![[SCOPE]])
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep.a = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep.a, align 4, !alias.scope !0, !noalias !3
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %x, ptr %gep.b, align 4, !alias.scope !3, !noalias !0
  %y = load i32, ptr %gep.a, align 4, !alias.scope !0, !noalias !3
  %sum = add i32 %x, %y
  store i32 %sum, ptr %gep.b, align 4, !alias.scope !3, !noalias !0
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; A store without alias metadata cannot be proven not to alias the loaded
; address, so the second load is not CSE'd.
define void @no_cse_across_store_without_scopes(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'no_cse_across_store_without_scopes'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep.a> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep.a> (!alias.scope ![[SCOPE2:[0-9]+]], !noalias ![[NOALIAS2:[0-9]+]])
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%x>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep.a> (!alias.scope ![[SCOPE2]], !noalias ![[NOALIAS2]])
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%x>, ir<%y>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep.a = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep.a, align 4, !alias.scope !0, !noalias !3
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %x, ptr %gep.b, align 4
  %y = load i32, ptr %gep.a, align 4, !alias.scope !0, !noalias !3
  %sum = add i32 %x, %y
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; Loads separated by a replicate region are not CSE'd.
define void @dup_load_across_replicate_region(ptr noalias %a, ptr noalias %b, ptr noalias %out) {
; CHECK-LABEL: VPlan for loop in 'dup_load_across_replicate_region'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, pred.load.continue ]
; CHECK-NEXT:    CLONE ir<%p> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%p>
; CHECK-NEXT:    WIDEN ir<%c> = icmp sgt ir<%x>, ir<0>
; CHECK-NEXT:    WIDEN-CAST ir<%idx> = sext ir<%x> to i64
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = extractelement ir<%c>, ir<0>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): pred.load.if, pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.if:
; CHECK-NEXT:    EMIT vp<[[VP3:%[0-9]+]]> = extractelement ir<%idx>, ir<0>
; CHECK-NEXT:    CLONE ir<%gep2> = getelementptr inbounds ir<%b>, vp<[[VP3]]>
; CHECK-NEXT:    CLONE ir<%ld> = load ir<%gep2>
; CHECK-NEXT:    EMIT vp<[[VP4:%[0-9]+]]> = insertelement ir<poison>, ir<%ld>, ir<0>
; CHECK-NEXT:  Successor(s): pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.continue:
; CHECK-NEXT:    WIDEN-PHI vp<[[VP5:%[0-9]+]]> = phi [ ir<poison>, vector.body ], [ vp<[[VP4]]>, pred.load.if ]
; CHECK-NEXT:    EMIT vp<[[VP6:%[0-9]+]]> = extractelement ir<%c>, ir<1>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP6]]>
; CHECK-NEXT:  Successor(s): pred.load.if, pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.if:
; CHECK-NEXT:    EMIT vp<[[VP8:%[0-9]+]]> = extractelement ir<%idx>, ir<1>
; CHECK-NEXT:    CLONE ir<%gep2>.1 = getelementptr inbounds ir<%b>, vp<[[VP8]]>
; CHECK-NEXT:    CLONE ir<%ld>.1 = load ir<%gep2>.1
; CHECK-NEXT:    EMIT vp<[[VP9:%[0-9]+]]> = insertelement vp<[[VP5]]>, ir<%ld>.1, ir<1>
; CHECK-NEXT:  Successor(s): pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.continue:
; CHECK-NEXT:    WIDEN-PHI vp<[[VP10:%[0-9]+]]> = phi [ vp<[[VP5]]>, pred.load.continue ], [ vp<[[VP9]]>, pred.load.if ]
; CHECK-NEXT:    EMIT vp<[[VP11:%[0-9]+]]> = extractelement ir<%c>, ir<2>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP11]]>
; CHECK-NEXT:  Successor(s): pred.load.if, pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.if:
; CHECK-NEXT:    EMIT vp<[[VP13:%[0-9]+]]> = extractelement ir<%idx>, ir<2>
; CHECK-NEXT:    CLONE ir<%gep2>.2 = getelementptr inbounds ir<%b>, vp<[[VP13]]>
; CHECK-NEXT:    CLONE ir<%ld>.2 = load ir<%gep2>.2
; CHECK-NEXT:    EMIT vp<[[VP14:%[0-9]+]]> = insertelement vp<[[VP10]]>, ir<%ld>.2, ir<2>
; CHECK-NEXT:  Successor(s): pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.continue:
; CHECK-NEXT:    WIDEN-PHI vp<[[VP15:%[0-9]+]]> = phi [ vp<[[VP10]]>, pred.load.continue ], [ vp<[[VP14]]>, pred.load.if ]
; CHECK-NEXT:    EMIT vp<[[VP16:%[0-9]+]]> = extractelement ir<%c>, ir<3>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP16]]>
; CHECK-NEXT:  Successor(s): pred.load.if, pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.if:
; CHECK-NEXT:    EMIT vp<[[VP18:%[0-9]+]]> = extractelement ir<%idx>, ir<3>
; CHECK-NEXT:    CLONE ir<%gep2>.3 = getelementptr inbounds ir<%b>, vp<[[VP18]]>
; CHECK-NEXT:    CLONE ir<%ld>.3 = load ir<%gep2>.3
; CHECK-NEXT:    EMIT vp<[[VP19:%[0-9]+]]> = insertelement vp<[[VP15]]>, ir<%ld>.3, ir<3>
; CHECK-NEXT:  Successor(s): pred.load.continue
; CHECK-EMPTY:
; CHECK-NEXT:  pred.load.continue:
; CHECK-NEXT:    WIDEN-PHI vp<[[VP20:%[0-9]+]]> = phi [ vp<[[VP15]]>, pred.load.continue ], [ vp<[[VP19]]>, pred.load.if ]
; CHECK-NEXT:    EMIT vp<%predphi> = select ir<%c>, vp<[[VP20]]>, ir<0>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%p>
; CHECK-NEXT:    WIDEN ir<%sum> = add vp<%predphi>, ir<%y>
; CHECK-NEXT:    CLONE ir<%po> = getelementptr inbounds ir<%out>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%po>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP21:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP21]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %cont ]
  %p = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %p, align 4
  %c = icmp sgt i32 %x, 0
  br i1 %c, label %then, label %cont

then:
  %idx = sext i32 %x to i64
  %gep2 = getelementptr inbounds i32, ptr %b, i64 %idx
  %ld = load i32, ptr %gep2, align 4
  br label %cont

cont:
  %v = phi i32 [ %ld, %then ], [ 0, %loop ]
  %y = load i32, ptr %p, align 4
  %sum = add i32 %v, %y
  %po = getelementptr inbounds i32, ptr %out, i64 %iv
  store i32 %sum, ptr %po, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

; The first load cannot be reused by the stronger aligned second load, but the
; second one becomes the candidate for the third load, which reuses it.
define void @cse_after_weaker_align_first(ptr noalias %a, ptr noalias %b) {
; CHECK-LABEL: VPlan for loop in 'cse_after_weaker_align_first'
; CHECK:  VPlan 'Final VPlan for VF={4},UF={1}' {
; CHECK-NEXT:  Live-in ir<1024> = vector-trip-count
; CHECK-EMPTY:
; CHECK-NEXT:  ir-bb<entry>:
; CHECK-NEXT:  Successor(s): vector.ph
; CHECK-EMPTY:
; CHECK-NEXT:  vector.ph:
; CHECK-NEXT:  Successor(s): vector.body
; CHECK-EMPTY:
; CHECK-NEXT:  vector.body:
; CHECK-NEXT:    EMIT-SCALAR vp<%index> = phi [ ir<0>, vector.ph ], [ vp<%index.next>, vector.body ]
; CHECK-NEXT:    CLONE ir<%gep> = getelementptr inbounds ir<%a>, vp<%index>
; CHECK-NEXT:    WIDEN ir<%x> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%y> = load ir<%gep>
; CHECK-NEXT:    WIDEN ir<%s1> = add ir<%x>, ir<%y>
; CHECK-NEXT:    WIDEN ir<%sum> = add ir<%s1>, ir<%y>
; CHECK-NEXT:    CLONE ir<%gep.b> = getelementptr inbounds ir<%b>, vp<%index>
; CHECK-NEXT:    WIDEN store ir<%gep.b>, ir<%sum>
; CHECK-NEXT:    EMIT vp<%index.next> = add nuw vp<%index>, ir<4>
; CHECK-NEXT:    EMIT vp<[[VP1:%[0-9]+]]> = icmp eq vp<%index.next>, ir<1024>
; CHECK-NEXT:    EMIT branch-on-cond vp<[[VP1]]>
; CHECK-NEXT:  Successor(s): middle.block, vector.body
;
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i32, ptr %a, i64 %iv
  %x = load i32, ptr %gep, align 4
  %y = load i32, ptr %gep, align 8
  %z = load i32, ptr %gep, align 8
  %s1 = add i32 %x, %y
  %sum = add i32 %s1, %z
  %gep.b = getelementptr inbounds i32, ptr %b, i64 %iv
  store i32 %sum, ptr %gep.b, align 4
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

!0 = !{!1}
!1 = distinct !{!1, !2, !"scope_a"}
!2 = distinct !{!2, !"domain"}
!3 = !{!4}
!4 = distinct !{!4, !2, !"scope_b"}
!5 = !{!6, !6, i64 0}
!6 = !{!"int", !7, i64 0}
!7 = !{!"omnipotent char", !8, i64 0}
!8 = !{!"Simple C/C++ TBAA"}
!9 = !{!10, !10, i64 0}
!10 = !{!"float", !7, i64 0}