llvm/test/Transforms/LoopVectorize/early_exit_legality.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
; REQUIRES: asserts
; RUN: opt -S < %s -p loop-vectorize -debug-only=loop-vectorize -force-vector-width=4 \
; RUN:   -disable-output 2>&1 | FileCheck %s --check-prefix=CHECK-DEBUG
; RUN: opt -S < %s -p loop-vectorize -pass-remarks-analysis='loop-vectorize' \
; RUN:   -force-vector-width=4 -disable-output 2>&1 | FileCheck %s --check-prefix=CHECK-REMARK

declare void @init_mem(ptr, i64) nofree

; == SOME LEGAL EXAMPLES ==

; The form of the induction variables requires SCEV predicates.
define i32 @diff_exit_block_needs_scev_check(i32 %end) {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'diff_exit_block_needs_scev_check'
; CHECK-DEBUG:       Found an early exit loop with symbolic max backedge taken count: (-1 + (1 umax (zext i10 (trunc i32 %end to i10) to i32)))<nsw>
; CHECK-DEBUG-NEXT:  LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG-NOT:   LV: Not vectorizing:
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i32]
  %p2 = alloca [1024 x i32]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  %end.clamped = and i32 %end, 1023
  br label %for.body

for.body:
  %ind = phi i8 [ %ind.next, %for.inc ], [ 0, %entry ]
  %gep.ind = phi i64 [ %gep.ind.next, %for.inc ], [ 0, %entry ]
  %arrayidx1 = getelementptr inbounds i32, ptr %p1, i64 %gep.ind
  %0 = load i32, ptr %arrayidx1, align 4
  %arrayidx2 = getelementptr inbounds i32, ptr %p2, i64 %gep.ind
  %1 = load i32, ptr %arrayidx2, align 4
  %cmp.early = icmp eq i32 %0, %1
  br i1 %cmp.early, label %found, label %for.inc

for.inc:
  %ind.next = add i8 %ind, 1
  %conv = zext i8 %ind.next to i32
  %gep.ind.next = add i64 %gep.ind, 1
  %cmp = icmp ult i32 %conv, %end.clamped
  br i1 %cmp, label %for.body, label %exit

found:
  ret i32 1

exit:
  ret i32 0
}


define i64 @same_exit_block_pre_inc_use1() {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_pre_inc_use1'
; CHECK-DEBUG:       LV: Found an early exit loop with symbolic max backedge taken count: 63
; CHECK-DEBUG-NEXT:  LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG-NOT:   LV: Not vectorizing
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.inc, label %loop.end

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


define i64 @loop_contains_safe_call() {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'loop_contains_safe_call'
; CHECK-DEBUG:       LV: Found an early exit loop with symbolic max backedge taken count: 63
; CHECK-DEBUG-NEXT:  LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds float, ptr %p1, i64 %index
  %ld1 = load float, ptr %arrayidx, align 1
  %sqrt = tail call fast float @llvm.sqrt.f32(float %ld1)
  %cmp = fcmp fast ult float %sqrt, 3.0e+00
  br i1 %cmp, label %loop.inc, label %loop.end

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


define i64 @loop_contains_safe_div() {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'loop_contains_safe_div'
; CHECK-DEBUG:       LV: Found an early exit loop with symbolic max backedge taken count: 63
; CHECK-DEBUG-NEXT:  LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i32, ptr %p1, i64 %index
  %ld1 = load i32, ptr %arrayidx, align 1
  %div = udiv i32 %ld1, 20000
  %cmp = icmp eq i32 %div, 1
  br i1 %cmp, label %loop.inc, label %loop.end

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


define i64 @loop_contains_load_after_early_exit(ptr dereferenceable(1024) align(8) %p2) {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'loop_contains_load_after_early_exit'
; CHECK-DEBUG:       LV: Found an early exit loop with symbolic max backedge taken count: 63
; CHECK-DEBUG-NEXT:  LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG-NOT:   LV: Not vectorizing
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  br label %loop

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i32, ptr %p1, i64 %index
  %ld1 = load i32, ptr %arrayidx, align 1
  %cmp = icmp eq i32 %ld1, 1
  br i1 %cmp, label %loop.inc, label %loop.end

loop.inc:
  %arrayidx2 = getelementptr inbounds i64, ptr %p2, i64 %index
  %ld2 = load i64, ptr %arrayidx2, align 8
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end

loop.end:
  %retval = phi i64 [ %index, %loop ], [ %ld2, %loop.inc ]
  ret i64 %retval
}


define i64 @one_uncountable_two_countable_same_exit_phi_of_consts() !dbg !39 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'one_uncountable_two_countable_same_exit_phi_of_consts'
; CHECK-DEBUG:       LV: Found an early exit loop with symbolic max backedge taken count: 61
; CHECK-DEBUG-NEXT:  LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG-NEXT:  LV: Not vectorizing: Auto-vectorization of early exit loops requiring a scalar epilogue is unsupported.
; CHECK-REMARK:      foo.c:60:3: loop not vectorized: Auto-vectorization of early exit loops requiring a scalar epilogue is unsupported
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !40

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %cmp1 = icmp ne i64 %index, 64
  br i1 %cmp1, label %search, label %loop.end, !dbg !40

search:
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.end, label %loop.inc, !dbg !40

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 128
  br i1 %exitcond, label %loop, label %loop.end, !dbg !40

loop.end:
  %retval = phi i64 [ 0, %loop ], [ 1, %search ], [ 0, %loop.inc ]
  ret i64 %retval
}


; == SOME ILLEGAL EXAMPLES ==


define i64 @same_exit_block_pre_inc_use1_too_small_allocas() !dbg !4 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_pre_inc_use1_too_small_allocas'
; CHECK-DEBUG:       LV: Not vectorizing: Auto-vectorization of early exit loops with potentially faulting loads is not supported.
; CHECK-REMARK:      foo.c:5:3: loop not vectorized: Auto-vectorization of early exit loops with potentially faulting loads is not supported
entry:
  %p1 = alloca [42 x i8]
  %p2 = alloca [42 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !8

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1, !dbg !8
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1, !dbg !8
  %cmp3 = icmp eq i8 %ld1, %ld2, !dbg !8
  br i1 %cmp3, label %loop.inc, label %loop.end, !dbg !8

loop.inc:
  %index.next = add i64 %index, 1, !dbg !8
  %exitcond = icmp ne i64 %index.next, 67, !dbg !8
  br i1 %exitcond, label %loop, label %loop.end, !dbg !8

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


define i64 @same_exit_block_pre_inc_use1_too_small_deref_ptrs(ptr dereferenceable(42) %p1, ptr dereferenceable(42) %p2) !dbg !41 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_pre_inc_use1_too_small_deref_ptrs'
; CHECK-DEBUG:       LV: Not vectorizing: Auto-vectorization of early exit loops with potentially faulting loads is not supported.
; CHECK-REMARK:      foo.c:70:3: loop not vectorized: Auto-vectorization of early exit loops with potentially faulting loads is not supported
entry:
  br label %loop, !dbg !42

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.inc, label %loop.end, !dbg !42

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end, !dbg !42

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


define i64 @same_exit_block_pre_inc_use1_unknown_ptrs(ptr %p1, ptr %p2) !dbg !43 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_pre_inc_use1_unknown_ptrs'
; CHECK-DEBUG:       LV: Not vectorizing: Auto-vectorization of early exit loops with potentially faulting loads is not supported.
; CHECK-REMARK:      foo.c:80:3: loop not vectorized: Auto-vectorization of early exit loops with potentially faulting loads is not supported
entry:
  br label %loop, !dbg !44

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.inc, label %loop.end, !dbg !44

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end, !dbg !44

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}

define ptr @same_exit_block_strided_unknown_ptr(ptr %first, ptr %last, i32 %value) !dbg !45 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_strided_unknown_ptr'
; CHECK-DEBUG:       LV: Not vectorizing: Loop contains potentially faulting strided load.
; CHECK-REMARK:      foo.c:90:3: loop not vectorized: Cannot vectorize early exit loop with strided fault-only-first load
entry:
  %cond = icmp eq ptr %first, %last
  br i1 %cond, label %return, label %for.body, !dbg !46

for.body:
  %first.addr = phi ptr [ %first, %entry ], [ %first.next, %for.inc ]
  %1 = load i32, ptr %first.addr, align 4
  %cond2 = icmp eq i32 %1, %value
  br i1 %cond2, label %for.end, label %for.inc, !dbg !46

for.inc:
  %first.next = getelementptr inbounds i32, ptr %first.addr, i64 2
  %cond3 = icmp eq ptr %first.next, %last
  br i1 %cond3, label %for.end, label %for.body, !dbg !46

for.end:
  %retval.ph = phi ptr [ %first.addr, %for.body ], [ %last, %for.inc ]
  br label %return, !dbg !46

return:
  %retval = phi ptr [ %first, %entry ], [ %retval.ph, %for.end ]
  ret ptr %retval
}

; The early exit (i.e. unknown exit-not-taken count) is the latch - we don't
; support this yet.
define i64 @uncountable_exit_on_last_block() !dbg !47 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'uncountable_exit_on_last_block'
; CHECK-DEBUG:       LV: Not vectorizing: Cannot determine exact exit count for latch block.
; CHECK-REMARK:      foo.c:100:3: loop not vectorized: Cannot vectorize early exit loop
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !48

loop:
  %index = phi i64 [ %index.next, %search ], [ 3, %entry ]
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %search, label %loop.end, !dbg !48

search:
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.end, label %loop, !dbg !48

loop.end:
  %retval = phi i64 [ 64, %loop ], [ %index, %search ]
  ret i64 %retval
}


; Multiple uncountable early exits are now supported.
define i64 @multiple_uncountable_exits() {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'multiple_uncountable_exits'
; CHECK-DEBUG:       LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %search1

search1:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp1 = icmp eq i8 %ld1, %ld2
  br i1 %cmp1, label %loop.end, label %search2

search2:
  %cmp2 = icmp ult i8 %ld1, 34
  br i1 %cmp2, label %loop.end, label %loop.inc

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %search1, label %loop.end

loop.end:
  %retval = phi i64 [ %index, %search1 ], [ 100, %search2 ], [ 43, %loop.inc ]
  ret i64 %retval
}


define i64 @uncountable_exit_infinite_loop() !dbg !51 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'uncountable_exit_infinite_loop'
; CHECK-DEBUG:       LV: Not vectorizing: Cannot vectorize uncountable loop.
; CHECK-REMARK:      foo.c:120:3: loop not vectorized: Cannot vectorize uncountable loop
; CHECK-REMARK-NEXT: foo.c:120:3: loop not vectorized: could not determine number of loop iterations
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !52

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.inc, label %loop.end, !dbg !52

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br label %loop, !dbg !52

loop.end:
  %retval = phi i64 [ %index, %loop ]
  ret i64 %retval
}


define i64 @loop_contains_unsafe_call() !dbg !53 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'loop_contains_unsafe_call'
; CHECK-DEBUG:       LV: Not vectorizing: Early exit loop contains operations that cannot be speculatively executed.
; CHECK-REMARK:      foo.c:130:3: loop not vectorized: Early exit loop contains operations that cannot be speculatively executed
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !54

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i32, ptr %p1, i64 %index
  %ld1 = load i32, ptr %arrayidx, align 1
  %bad_call = call i32 @foo(i32 %ld1) #0
  %cmp = icmp eq i32 %bad_call, 34
  br i1 %cmp, label %loop.inc, label %loop.end, !dbg !54

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end, !dbg !54

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


define i64 @loop_contains_unsafe_div() !dbg !55 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'loop_contains_unsafe_div'
; CHECK-DEBUG:       LV: Not vectorizing: Early exit loop contains operations that cannot be speculatively executed.
; CHECK-REMARK:      foo.c:140:3: loop not vectorized: Early exit loop contains operations that cannot be speculatively executed
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !56

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i32, ptr %arrayidx, align 1
  %div = udiv i32 20000, %ld1
  %cmp = icmp eq i32 %div, 1
  br i1 %cmp, label %loop.inc, label %loop.end, !dbg !56

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end, !dbg !56

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}

define void @exit_conditions_combined_in_single_branch(ptr noalias dereferenceable(40) %array, ptr readonly align 2 dereferenceable(40) %pred) !dbg !57 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'exit_conditions_combined_in_single_branch'
; CHECK-DEBUG:       LV: Not vectorizing: Cannot vectorize uncountable loop.
; CHECK-REMARK:      foo.c:150:3: loop not vectorized: Cannot vectorize uncountable loop
entry:
  br label %for.body, !dbg !58

for.body:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
  %st.addr = getelementptr inbounds nuw i16, ptr %array, i64 %iv
  %data = load i16, ptr %st.addr, align 2
  %inc = add nsw i16 %data, 1
  store i16 %inc, ptr %st.addr, align 2
  %ee.addr = getelementptr inbounds nuw i16, ptr %pred, i64 %iv
  %ee.val = load i16, ptr %ee.addr, align 2
  %ee.cond = icmp sgt i16 %ee.val, 500
  %iv.next = add nuw nsw i64 %iv, 1
  %counted.cond = icmp eq i64 %iv.next, 20
  %or.cond = select i1 %ee.cond, i1 true, i1 %counted.cond
  br i1 %or.cond, label %exit, label %for.body, !dbg !58

exit:
  ret void
}

; %prev is a fixed-order recurrence and, under a SCEV predicate, also the only
; canonical {0,+,1} induction candidate.
; the early-exit loop is still rejected here.
define i64 @same_exit_block_with_recurrence_that_is_also_an_induction() !dbg !59 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_with_recurrence_that_is_also_an_induction'
; CHECK-DEBUG:       LV: Not vectorizing: Found reductions or recurrences in early-exit loop.
; CHECK-REMARK:      foo.c:160:3: loop not vectorized: Cannot vectorize early exit loop with reductions or recurrences
entry:
  %p1 = alloca [4096 x i8]
  call void @init_mem(ptr %p1, i64 4096)
  br label %loop, !dbg !60

loop:
  %prev = phi i64 [ %ext, %loop.inc ], [ 0, %entry ]
  %narrow = phi i8 [ %inc, %loop.inc ], [ 0, %entry ]
  %index = phi i32 [ %index.next, %loop.inc ], [ 1, %entry ]
  %inc = add i8 %narrow, 1
  %ext = zext i8 %inc to i64
  %arrayidx = getelementptr inbounds i8, ptr %p1, i32 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %prev.trunc = trunc i64 %prev to i8
  %cmp3 = icmp eq i8 %ld1, %prev.trunc
  br i1 %cmp3, label %loop.inc, label %loop.end, !dbg !60

loop.inc:
  %index.next = add i32 %index, 1
  %exitcond = icmp ne i32 %index.next, 4000
  br i1 %exitcond, label %loop, label %loop.end, !dbg !60

loop.end:
  %retval = phi i64 [ %ext, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}

define i64 @same_exit_block_pre_inc_use1_with_reduction() !dbg !61 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'same_exit_block_pre_inc_use1_with_reduction'
; CHECK-DEBUG:       LV: Not vectorizing: Found reductions or recurrences in early-exit loop.
; CHECK-REMARK:      foo.c:170:3: loop not vectorized: Cannot vectorize early exit loop with reductions or recurrences
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %loop, !dbg !62

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %red = phi i64 [ %red.next, %loop.inc ], [ 0, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld2 = load i8, ptr %arrayidx1, align 1
  %ld2.zext = zext i8 %ld2 to i64
  %red.next = add i64 %red, %ld2.zext
  %cmp3 = icmp eq i8 %ld1, %ld2
  br i1 %cmp3, label %loop.inc, label %loop.end, !dbg !62

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end, !dbg !62

loop.end:
  %final.ind = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  %retval = add i64 %red.next, %final.ind
  ret i64 %retval
}


define i64 @uncountable_exit_has_multiple_outside_successors() !dbg !63 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'uncountable_exit_has_multiple_outside_successors'
; CHECK-DEBUG:       LV: Not vectorizing: Loop contains an unsupported switch
; CHECK-REMARK:      foo.c:180:3: loop not vectorized: Loop contains an unsupported switch
; CHECK-REMARK-NEXT: foo.c:180:3: loop not vectorized: Incorrect number of successors from early exiting block
entry:
  %p1 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  br label %loop, !dbg !64

loop:
  %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  switch i8 %ld1, label %loop.inc [
  i8 2, label %loop.end
  i8 3, label %loop.surprise
  ], !dbg !64

loop.inc:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %loop, label %loop.end, !dbg !64

loop.surprise:
  ret i64 3

loop.end:
  %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
  ret i64 %retval
}


; Two early exits on parallel branches (neither dominates the other).
; This is now supported with predicated early exits.
define i64 @uncountable_exits_on_parallel_branches() {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'uncountable_exits_on_parallel_branches'
; CHECK-DEBUG:       LV: Loop passed LoopVectorizationLegality checks!
; CHECK-DEBUG:       LV: VPlan created successfully. Loop can be vectorized.
entry:
  %p1 = alloca [1024 x i8]
  %p2 = alloca [1024 x i8]
  call void @init_mem(ptr %p1, i64 1024)
  call void @init_mem(ptr %p2, i64 1024)
  br label %header

header:
  %index = phi i64 [ %index.next, %latch ], [ 3, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
  %ld1 = load i8, ptr %arrayidx, align 1
  %branch.cond = icmp sgt i8 %ld1, 0
  br i1 %branch.cond, label %left, label %right

left:
  %arrayidx.left = getelementptr inbounds i8, ptr %p2, i64 %index
  %ld.left = load i8, ptr %arrayidx.left, align 1
  %cmp.left = icmp eq i8 %ld1, %ld.left
  br i1 %cmp.left, label %loop.end, label %latch

right:
  %cmp.right = icmp ult i8 %ld1, 34
  br i1 %cmp.right, label %loop.end, label %latch

latch:
  %index.next = add i64 %index, 1
  %exitcond = icmp ne i64 %index.next, 67
  br i1 %exitcond, label %header, label %loop.end

loop.end:
  %retval = phi i64 [ %index, %left ], [ 100, %right ], [ 43, %latch ]
  ret i64 %retval
}


; Parallel uncountable exits with loop-invariant conditions.
; Note: This loop cannot be vectorized because the latch has no determinate
; exit count (loop is infinite without early exits).
define void @uncountable_exits_invariant_conditions(ptr %p, i1 %cond1, i1 %cond2, i1 %cond3) !dbg !67 {
; CHECK-DEBUG-LABEL: LV: Checking a loop in 'uncountable_exits_invariant_conditions'
; CHECK-DEBUG:       LV: Not vectorizing: Cannot determine exact exit count for latch block.
; CHECK-REMARK:      foo.c:200:3: loop not vectorized: Cannot vectorize early exit loop
; CHECK-REMARK-NEXT: foo.c:200:3: loop not vectorized: could not determine number of loop iterations
entry:
  br label %loop.header, !dbg !68

loop.header:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  br i1 %cond1, label %then.1, label %else.1, !dbg !68

else.1:
  br i1 %cond2, label %then.2, label %exit, !dbg !68

then.2:
  %getelementptr.i = getelementptr i16, ptr %p, i64 %iv
  %l = load i16, ptr %getelementptr.i, align 2
  %ec  = icmp ugt i16 %l, -25
  br i1 %ec, label %exit, label %loop.latch, !dbg !68

then.1:
  br i1 %cond3, label %exit, label %loop.latch, !dbg !68

loop.latch:
  %iv.next = add i64 %iv, 1
  br label %loop.header, !dbg !68

exit:
  ret void
}

declare i32 @foo(i32) readonly
declare <vscale x 4 x i32> @foo_vec(<vscale x 4 x i32>)

attributes #0 = { "vector-function-abi-variant"="_ZGVsNxv_foo(foo_vec)" }

!llvm.dbg.cu = !{!28}
!llvm.module.flags = !{!0, !1}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = !{i32 1, !"PIC Level", i32 2}
!3 = !DILocation(line: 5, column: 20, scope: !4)
!4 = distinct !DISubprogram(name: "foo", scope: !5, file: !5, line: 1, type: !6, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!5 = !DIFile(filename: "foo.c", directory: "")
!6 = !DISubroutineType(types: !7)
!7 = !{}
!8 = !DILocation(line: 5, column: 3, scope: !4)
!9 = !DILocation(line: 6, column: 14, scope: !4)
!10 = !DILocation(line: 9, column: 3, scope: !4)
!15 = !DILocation(line: 6, column: 19, scope: !4)
!16 = !DILocation(line: 6, column: 11, scope: !4)
!39 = distinct !DISubprogram(name: "one_uncountable_two_countable_same_exit_phi_of_consts", scope: !5, file: !5, line: 60, type: !6, isLocal: false, isDefinition: true, scopeLine: 60, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!40 = !DILocation(line: 60, column: 3, scope: !39)
!41 = distinct !DISubprogram(name: "same_exit_block_pre_inc_use1_too_small_deref_ptrs", scope: !5, file: !5, line: 70, type: !6, isLocal: false, isDefinition: true, scopeLine: 70, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!42 = !DILocation(line: 70, column: 3, scope: !41)
!43 = distinct !DISubprogram(name: "same_exit_block_pre_inc_use1_unknown_ptrs", scope: !5, file: !5, line: 80, type: !6, isLocal: false, isDefinition: true, scopeLine: 80, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!44 = !DILocation(line: 80, column: 3, scope: !43)
!45 = distinct !DISubprogram(name: "same_exit_block_strided_unknown_ptr", scope: !5, file: !5, line: 90, type: !6, isLocal: false, isDefinition: true, scopeLine: 90, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!46 = !DILocation(line: 90, column: 3, scope: !45)
!47 = distinct !DISubprogram(name: "uncountable_exit_on_last_block", scope: !5, file: !5, line: 100, type: !6, isLocal: false, isDefinition: true, scopeLine: 100, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!48 = !DILocation(line: 100, column: 3, scope: !47)
!51 = distinct !DISubprogram(name: "uncountable_exit_infinite_loop", scope: !5, file: !5, line: 120, type: !6, isLocal: false, isDefinition: true, scopeLine: 120, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!52 = !DILocation(line: 120, column: 3, scope: !51)
!53 = distinct !DISubprogram(name: "loop_contains_unsafe_call", scope: !5, file: !5, line: 130, type: !6, isLocal: false, isDefinition: true, scopeLine: 130, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!54 = !DILocation(line: 130, column: 3, scope: !53)
!55 = distinct !DISubprogram(name: "loop_contains_unsafe_div", scope: !5, file: !5, line: 140, type: !6, isLocal: false, isDefinition: true, scopeLine: 140, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!56 = !DILocation(line: 140, column: 3, scope: !55)
!57 = distinct !DISubprogram(name: "exit_conditions_combined_in_single_branch", scope: !5, file: !5, line: 150, type: !6, isLocal: false, isDefinition: true, scopeLine: 150, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!58 = !DILocation(line: 150, column: 3, scope: !57)
!59 = distinct !DISubprogram(name: "same_exit_block_with_recurrence_that_is_also_an_induction", scope: !5, file: !5, line: 160, type: !6, isLocal: false, isDefinition: true, scopeLine: 160, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!60 = !DILocation(line: 160, column: 3, scope: !59)
!61 = distinct !DISubprogram(name: "same_exit_block_pre_inc_use1_with_reduction", scope: !5, file: !5, line: 170, type: !6, isLocal: false, isDefinition: true, scopeLine: 170, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!62 = !DILocation(line: 170, column: 3, scope: !61)
!63 = distinct !DISubprogram(name: "uncountable_exit_has_multiple_outside_successors", scope: !5, file: !5, line: 180, type: !6, isLocal: false, isDefinition: true, scopeLine: 180, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!64 = !DILocation(line: 180, column: 3, scope: !63)
!67 = distinct !DISubprogram(name: "uncountable_exits_invariant_conditions", scope: !5, file: !5, line: 200, type: !6, isLocal: false, isDefinition: true, scopeLine: 200, flags: DIFlagPrototyped, isOptimized: true, unit: !28, retainedNodes: !7)
!68 = !DILocation(line: 200, column: 3, scope: !67)
!28 = distinct !DICompileUnit(language: DW_LANG_C99, producer: "clang", file: !5, isOptimized: true, flags: "-O2", splitDebugFilename: "abc.debug", emissionKind: 2)