llvm/test/Transforms/LoopVectorize/early-exit-minmax-trip-count.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals none --version 6
; RUN: opt -S -passes=loop-vectorize -enable-early-exit-vectorization -force-vector-width=4 %s | FileCheck %s

; The loop should be vectorized. The vectorizer needs to prove
;   (A umin B) u<= A to establish memory safety from the dereferenceable
;   assumption.
;
; long n = umin(count, length);
; for (long i = 0; i < n; i++)
;   if (ptr[i] == 0) return null;
; ...
define ptr @deref_umin_trip_count_and_length(i32 %length, ptr %ptr, i64 %count) #0 {
; CHECK-LABEL: define ptr @deref_umin_trip_count_and_length(
; CHECK-SAME: i32 [[LENGTH:%.*]], ptr [[PTR:%.*]], i64 [[COUNT:%.*]]) #[[ATTR0:[0-9]+]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[COUNT_CHECK:%.*]] = icmp ne i64 [[COUNT]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[COUNT_CHECK]])
; CHECK-NEXT:    [[LENGTH_64:%.*]] = zext i32 [[LENGTH]] to i64
; CHECK-NEXT:    [[TRIP_COUNT:%.*]] = call i64 @llvm.umin.i64(i64 [[COUNT]], i64 [[LENGTH_64]])
; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "align"(ptr [[PTR]], i64 8), "dereferenceable"(ptr [[PTR]], i64 [[LENGTH_64]]) ]
; CHECK-NEXT:    [[LENGTH_CHECK:%.*]] = icmp ne i32 [[LENGTH]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[LENGTH_CHECK]])
; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TRIP_COUNT]], 4
; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_PH:.*]]
; CHECK:       [[VECTOR_PH]]:
; CHECK-NEXT:    [[N_MOD_VF:%.*]] = and i64 [[TRIP_COUNT]], 3
; CHECK-NEXT:    [[N_VEC:%.*]] = sub i64 [[TRIP_COUNT]], [[N_MOD_VF]]
; CHECK-NEXT:    br label %[[VECTOR_BODY:.*]]
; CHECK:       [[VECTOR_BODY]]:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY_INTERIM:.*]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[INDEX]]
; CHECK-NEXT:    [[WIDE_LOAD:%.*]] = load <4 x i8>, ptr [[TMP0]], align 1
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <4 x i8> [[WIDE_LOAD]], zeroinitializer
; CHECK-NEXT:    [[TMP2:%.*]] = freeze <4 x i1> [[TMP1]]
; CHECK-NEXT:    [[TMP3:%.*]] = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> [[TMP2]])
; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT:    br i1 [[TMP3]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM]]
; CHECK:       [[VECTOR_BODY_INTERIM]]:
; CHECK-NEXT:    br i1 [[TMP4]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
; CHECK:       [[MIDDLE_BLOCK]]:
; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 [[TRIP_COUNT]], [[N_VEC]]
; CHECK-NEXT:    br i1 [[CMP_N]], label %[[DEOPT:.*]], label %[[SCALAR_PH]]
; CHECK:       [[VECTOR_EARLY_EXIT]]:
; CHECK-NEXT:    br label %[[FOUND:.*]]
; CHECK:       [[SCALAR_PH]]:
; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ]
; CHECK-NEXT:    [[ELEMENT_GEP:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[IV]]
; CHECK-NEXT:    [[ELEMENT:%.*]] = load i8, ptr [[ELEMENT_GEP]], align 1
; CHECK-NEXT:    [[FOUND_CHECK:%.*]] = icmp eq i8 [[ELEMENT]], 0
; CHECK-NEXT:    br i1 [[FOUND_CHECK]], label %[[FOUND]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i64 [[IV_NEXT]], [[TRIP_COUNT]]
; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label %[[LOOP]], label %[[DEOPT]], !llvm.loop [[LOOP3:![0-9]+]]
; CHECK:       [[FOUND]]:
; CHECK-NEXT:    ret ptr null
; CHECK:       [[DEOPT]]:
; CHECK-NEXT:    unreachable
;
entry:
  %count_check = icmp ne i64 %count, 0
  call void @llvm.assume(i1 %count_check)
  %length.64 = zext i32 %length to i64
  %trip.count = call i64 @llvm.umin.i64(i64 %count, i64 %length.64)
  call void @llvm.assume(i1 true) [ "align"(ptr %ptr, i64 8), "dereferenceable"(ptr %ptr, i64 %length.64) ]
  %length_check = icmp ne i32 %length, 0
  call void @llvm.assume(i1 %length_check)
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
  %element_gep = getelementptr i8, ptr %ptr, i64 %iv
  %element = load i8, ptr %element_gep, align 1
  %found_check = icmp eq i8 %element, 0
  br i1 %found_check, label %found, label %latch

latch:
  %iv.next = add i64 %iv, 1
  %range_check = icmp ult i64 %iv.next, %trip.count
  br i1 %range_check, label %loop, label %deopt

found:
  ret ptr null

deopt:
  unreachable
}

; The trip count is %c and the dereferenceable region is umin(%a, %b).
define i1 @deref_umin_all_operands_bounded(ptr %ptr, i64 %a, i64 %b, i64 %c) #0 {
; CHECK-LABEL: define i1 @deref_umin_all_operands_bounded(
; CHECK-SAME: ptr [[PTR:%.*]], i64 [[A:%.*]], i64 [[B:%.*]], i64 [[C:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[GUARD_A:%.*]] = icmp ule i64 [[C]], [[A]]
; CHECK-NEXT:    call void @llvm.assume(i1 [[GUARD_A]])
; CHECK-NEXT:    [[GUARD_B:%.*]] = icmp ule i64 [[C]], [[B]]
; CHECK-NEXT:    call void @llvm.assume(i1 [[GUARD_B]])
; CHECK-NEXT:    [[GUARD_POS:%.*]] = icmp ugt i64 [[C]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[GUARD_POS]])
; CHECK-NEXT:    [[DEREF:%.*]] = call i64 @llvm.umin.i64(i64 [[A]], i64 [[B]])
; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(ptr [[PTR]], i64 [[DEREF]]) ]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ]
; CHECK-NEXT:    [[ELEMENT_GEP:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[IV]]
; CHECK-NEXT:    [[ELEMENT:%.*]] = load i8, ptr [[ELEMENT_GEP]], align 1
; CHECK-NEXT:    [[FOUND_CHECK:%.*]] = icmp eq i8 [[ELEMENT]], 0
; CHECK-NEXT:    br i1 [[FOUND_CHECK]], label %[[EXIT_0:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i64 [[IV_NEXT]], [[C]]
; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label %[[LOOP]], label %[[EXIT_1:.*]]
; CHECK:       [[EXIT_0]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT_1]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %guard.a = icmp ule i64 %c, %a
  call void @llvm.assume(i1 %guard.a)
  %guard.b = icmp ule i64 %c, %b
  call void @llvm.assume(i1 %guard.b)
  %guard.pos = icmp ugt i64 %c, 0
  call void @llvm.assume(i1 %guard.pos)
  %deref = call i64 @llvm.umin.i64(i64 %a, i64 %b)
  call void @llvm.assume(i1 true) [ "dereferenceable"(ptr %ptr, i64 %deref) ]
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
  %element_gep = getelementptr i8, ptr %ptr, i64 %iv
  %element = load i8, ptr %element_gep, align 1
  %found_check = icmp eq i8 %element, 0
  br i1 %found_check, label %exit.0, label %latch

latch:
  %iv.next = add i64 %iv, 1
  %range_check = icmp ult i64 %iv.next, %c
  br i1 %range_check, label %loop, label %exit.1

exit.0:
  ret i1 true

exit.1:
  ret i1 false
}

; Same as above, but the guards are written in swapped (uge) form.
define i1 @deref_umin_swapped_guards(ptr %ptr, i64 %a, i64 %b, i64 %c) #0 {
; CHECK-LABEL: define i1 @deref_umin_swapped_guards(
; CHECK-SAME: ptr [[PTR:%.*]], i64 [[A:%.*]], i64 [[B:%.*]], i64 [[C:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[GUARD_A:%.*]] = icmp uge i64 [[A]], [[C]]
; CHECK-NEXT:    call void @llvm.assume(i1 [[GUARD_A]])
; CHECK-NEXT:    [[GUARD_B:%.*]] = icmp uge i64 [[B]], [[C]]
; CHECK-NEXT:    call void @llvm.assume(i1 [[GUARD_B]])
; CHECK-NEXT:    [[GUARD_POS:%.*]] = icmp ugt i64 [[C]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[GUARD_POS]])
; CHECK-NEXT:    [[DEREF:%.*]] = call i64 @llvm.umin.i64(i64 [[A]], i64 [[B]])
; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "dereferenceable"(ptr [[PTR]], i64 [[DEREF]]) ]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ]
; CHECK-NEXT:    [[ELEMENT_GEP:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[IV]]
; CHECK-NEXT:    [[ELEMENT:%.*]] = load i8, ptr [[ELEMENT_GEP]], align 1
; CHECK-NEXT:    [[FOUND_CHECK:%.*]] = icmp eq i8 [[ELEMENT]], 0
; CHECK-NEXT:    br i1 [[FOUND_CHECK]], label %[[EXIT_0:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i64 [[IV_NEXT]], [[C]]
; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label %[[LOOP]], label %[[EXIT_1:.*]]
; CHECK:       [[EXIT_0]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT_1]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %guard.a = icmp uge i64 %a, %c
  call void @llvm.assume(i1 %guard.a)
  %guard.b = icmp uge i64 %b, %c
  call void @llvm.assume(i1 %guard.b)
  %guard.pos = icmp ugt i64 %c, 0
  call void @llvm.assume(i1 %guard.pos)
  %deref = call i64 @llvm.umin.i64(i64 %a, i64 %b)
  call void @llvm.assume(i1 true) [ "dereferenceable"(ptr %ptr, i64 %deref) ]
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
  %element_gep = getelementptr i8, ptr %ptr, i64 %iv
  %element = load i8, ptr %element_gep, align 1
  %found_check = icmp eq i8 %element, 0
  br i1 %found_check, label %exit.0, label %latch

latch:
  %iv.next = add i64 %iv, 1
  %range_check = icmp ult i64 %iv.next, %c
  br i1 %range_check, label %loop, label %exit.1

exit.0:
  ret i1 true

exit.1:
  ret i1 false
}

; The trip count is a signed smin of the loop count and a sext'd length. Memory
; safety needs smin(%count, %length) s<= %length, which only the signed "any_of"
; min case proves (the removed unsigned umin fast-path could not reason about a
; signed smin at all).
define i1 @smin_signed_trip_count(i32 %length, ptr %ptr, i64 %count) #0 {
; CHECK-LABEL: define i1 @smin_signed_trip_count(
; CHECK-SAME: i32 [[LENGTH:%.*]], ptr [[PTR:%.*]], i64 [[COUNT:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[POSCHECK:%.*]] = icmp sgt i64 [[COUNT]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[POSCHECK]])
; CHECK-NEXT:    [[LENGTH_64:%.*]] = sext i32 [[LENGTH]] to i64
; CHECK-NEXT:    [[EXIT:%.*]] = call i64 @llvm.smin.i64(i64 [[COUNT]], i64 [[LENGTH_64]])
; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "align"(ptr [[PTR]], i64 8), "dereferenceable"(ptr [[PTR]], i64 [[LENGTH_64]]) ]
; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp sgt i32 [[LENGTH]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[NULL_CHECK]])
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ]
; CHECK-NEXT:    [[ELEMENT_GEP:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[IV]]
; CHECK-NEXT:    [[ELEMENT:%.*]] = load i8, ptr [[ELEMENT_GEP]], align 1
; CHECK-NEXT:    [[FOUND_CHECK:%.*]] = icmp eq i8 [[ELEMENT]], 0
; CHECK-NEXT:    br i1 [[FOUND_CHECK]], label %[[EXIT_0:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp slt i64 [[IV_NEXT]], [[EXIT]]
; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label %[[LOOP]], label %[[EXIT_1:.*]]
; CHECK:       [[EXIT_0]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT_1]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %poscheck = icmp sgt i64 %count, 0
  call void @llvm.assume(i1 %poscheck)
  %length.64 = sext i32 %length to i64
  %exit = call i64 @llvm.smin.i64(i64 %count, i64 %length.64)
  call void @llvm.assume(i1 true) [ "align"(ptr %ptr, i64 8), "dereferenceable"(ptr %ptr, i64 %length.64) ]
  %null_check = icmp sgt i32 %length, 0
  call void @llvm.assume(i1 %null_check)
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
  %element_gep = getelementptr i8, ptr %ptr, i64 %iv
  %element = load i8, ptr %element_gep, align 1
  %found_check = icmp eq i8 %element, 0
  br i1 %found_check, label %exit.0, label %latch

latch:
  %iv.next = add i64 %iv, 1
  %range_check = icmp slt i64 %iv.next, %exit
  br i1 %range_check, label %loop, label %exit.1

exit.0:
  ret i1 true

exit.1:
  ret i1 false
}

; The dereferenceable size is umax(%length, %k) and the trip count is %length.
; Memory safety needs %length u<= umax(%length, %k), which only holds because
; %length is itself an operand of the umax ("any_of" max case).
define i1 @umax_deref_bound(i32 %length, ptr %ptr, i64 %k) #0 {
; CHECK-LABEL: define i1 @umax_deref_bound(
; CHECK-SAME: i32 [[LENGTH:%.*]], ptr [[PTR:%.*]], i64 [[K:%.*]]) #[[ATTR0]] {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[POSCHECK:%.*]] = icmp sgt i64 [[K]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[POSCHECK]])
; CHECK-NEXT:    [[LENGTH_64:%.*]] = zext i32 [[LENGTH]] to i64
; CHECK-NEXT:    [[DEREF:%.*]] = call i64 @llvm.umax.i64(i64 [[LENGTH_64]], i64 [[K]])
; CHECK-NEXT:    call void @llvm.assume(i1 true) [ "align"(ptr [[PTR]], i64 8), "dereferenceable"(ptr [[PTR]], i64 [[DEREF]]) ]
; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp ne i32 [[LENGTH]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[NULL_CHECK]])
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ]
; CHECK-NEXT:    [[ELEMENT_GEP:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[IV]]
; CHECK-NEXT:    [[ELEMENT:%.*]] = load i8, ptr [[ELEMENT_GEP]], align 1
; CHECK-NEXT:    [[FOUND_CHECK:%.*]] = icmp eq i8 [[ELEMENT]], 0
; CHECK-NEXT:    br i1 [[FOUND_CHECK]], label %[[EXIT_0:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT:    [[RANGE_CHECK:%.*]] = icmp ult i64 [[IV_NEXT]], [[LENGTH_64]]
; CHECK-NEXT:    br i1 [[RANGE_CHECK]], label %[[LOOP]], label %[[EXIT_1:.*]]
; CHECK:       [[EXIT_0]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT_1]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %poscheck = icmp sgt i64 %k, 0
  call void @llvm.assume(i1 %poscheck)
  %length.64 = zext i32 %length to i64
  %deref = call i64 @llvm.umax.i64(i64 %length.64, i64 %k)
  call void @llvm.assume(i1 true) [ "align"(ptr %ptr, i64 8), "dereferenceable"(ptr %ptr, i64 %deref) ]
  %null_check = icmp ne i32 %length, 0
  call void @llvm.assume(i1 %null_check)
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
  %element_gep = getelementptr i8, ptr %ptr, i64 %iv
  %element = load i8, ptr %element_gep, align 1
  %found_check = icmp eq i8 %element, 0
  br i1 %found_check, label %exit.0, label %latch

latch:
  %iv.next = add i64 %iv, 1
  %range_check = icmp ult i64 %iv.next, %length.64
  br i1 %range_check, label %loop, label %exit.1

exit.0:
  ret i1 true

exit.1:
  ret i1 false
}

attributes #0 = { nofree nosync }