llvm/test/Transforms/IndVarSimplify/exit-value-nowrap-flags.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt -passes=indvars -S %s | FileCheck %s

target datalayout = "n8:16:32:64"

define i32 @nuw_kept(i32 %start, i32 %step, i32 %n) {
; CHECK-LABEL: define i32 @nuw_kept(
; CHECK-SAME: i32 [[START:%.*]], i32 [[STEP:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT:.*]], label %[[LATCH:.*]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    br label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw i32 [[N]], [[STEP]]
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[START]], [[TMP0]]
; CHECK-NEXT:    ret i32 [[TMP1]]
;
entry:
  br label %loop

loop:
  %v = phi i32 [ %start, %entry ], [ %v.next, %latch ]
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %done = icmp eq i32 %i, %n
  br i1 %done, label %exit, label %latch

latch:
  %v.next = add nuw i32 %v, %step
  %i.next = add i32 %i, 1
  br label %loop

exit:
  ret i32 %v
}

; Signed recurrence with %start and %step are both known non-negative.
define i32 @nsw_kept_same_sign(i32 %start.in, i32 %step.in, i32 %n) {
; CHECK-LABEL: define i32 @nsw_kept_same_sign(
; CHECK-SAME: i32 [[START_IN:%.*]], i32 [[STEP_IN:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[START:%.*]] = and i32 [[START_IN]], 1023
; CHECK-NEXT:    [[STEP:%.*]] = and i32 [[STEP_IN]], 1023
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT:.*]], label %[[LATCH:.*]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    br label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw i32 [[N]], [[STEP]]
; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i32 [[TMP0]], [[START]]
; CHECK-NEXT:    ret i32 [[TMP1]]
;
entry:
  %start = and i32 %start.in, 1023
  %step = and i32 %step.in, 1023
  br label %loop

loop:
  %v = phi i32 [ %start, %entry ], [ %v.next, %latch ]
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %done = icmp eq i32 %i, %n
  br i1 %done, label %exit, label %latch

latch:
  %v.next = add nsw i32 %v, %step
  %i.next = add i32 %i, 1
  br label %loop

exit:
  ret i32 %v
}

; Start is non-negative but Step is negative.
define i32 @nsw_dropped_mixed_signs(i32 %start.in, i32 %step.in, i32 %n) {
; CHECK-LABEL: define i32 @nsw_dropped_mixed_signs(
; CHECK-SAME: i32 [[START_IN:%.*]], i32 [[STEP_IN:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[START:%.*]] = and i32 [[START_IN]], 1023
; CHECK-NEXT:    [[STEP_POS:%.*]] = and i32 [[STEP_IN]], 1023
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT:.*]], label %[[LATCH:.*]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    br label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[N]], [[STEP_POS]]
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[START]], [[TMP0]]
; CHECK-NEXT:    ret i32 [[TMP1]]
;
entry:
  %start = and i32 %start.in, 1023
  %step.pos = and i32 %step.in, 1023
  %step = sub nsw i32 0, %step.pos
  br label %loop

loop:
  %v = phi i32 [ %start, %entry ], [ %v.next, %latch ]
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %done = icmp eq i32 %i, %n
  br i1 %done, label %exit, label %latch

latch:
  %v.next = add nsw i32 %v, %step
  %i.next = add i32 %i, 1
  br label %loop

exit:
  ret i32 %v
}

; The exit count is (-1 + %n) and Start is 0, so the sum folds away completely.
define i32 @nuw_dropped_sum_folded_away(i32 %n) {
; CHECK-LABEL: define i32 @nuw_dropped_sum_folded_away(
; CHECK-SAME: i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT:.*]], label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], -1
; CHECK-NEXT:    ret i32 [[TMP0]]
;
entry:
  br label %loop

loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  %i.next = add nuw i32 %i, 1
  %c = icmp eq i32 %i.next, %n
  br i1 %c, label %exit, label %loop

exit:
  ret i32 %i
}

; Start is a sum, so computing the exit value inlines it into %start + BTC.
define i32 @nuw_dropped_sum_flattened(i32 %a, i32 %b, i32 %n) {
; CHECK-LABEL: define i32 @nuw_dropped_sum_flattened(
; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT:.*]], label %[[LATCH:.*]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    br label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], [[B]]
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[TMP0]], [[A]]
; CHECK-NEXT:    ret i32 [[TMP1]]
;
entry:
  %start = add i32 %a, %b
  br label %loop

loop:
  %v = phi i32 [ %start, %entry ], [ %v.next, %latch ]
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %done = icmp eq i32 %i, %n
  br i1 %done, label %exit, label %latch

latch:
  %v.next = add nuw i32 %v, 1
  %i.next = add i32 %i, 1
  br label %loop

exit:
  ret i32 %v
}

; Step is a product, so computing the exit value inlines it into BTC * Step.
define i32 @nuw_dropped_product_flattened(i32 %s1, i32 %s2, i32 %n) {
; CHECK-LABEL: define i32 @nuw_dropped_product_flattened(
; CHECK-SAME: i32 [[S1:%.*]], i32 [[S2:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT:.*]], label %[[LATCH:.*]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    br label %[[LOOP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[N]], [[S2]]
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[TMP0]], [[S1]]
; CHECK-NEXT:    ret i32 [[TMP1]]
;
entry:
  %step = mul i32 %s1, %s2
  br label %loop

loop:
  %v = phi i32 [ 0, %entry ], [ %v.next, %latch ]
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %done = icmp eq i32 %i, %n
  br i1 %done, label %exit, label %latch

latch:
  %v.next = add nuw i32 %v, %step
  %i.next = add i32 %i, 1
  br label %loop

exit:
  ret i32 %v
}

@A = external global i32

; LFTR computes the limit for one exit of a multi-exit loop. %n is the count for
; the latch exit alone; the loop can leave through the %iv2 == 20 exit first, so
; that iteration is not necessarily reached.
define void @lftr_limit_multi_exit(i32 %n) {
; CHECK-LABEL: define void @lftr_limit_multi_exit(
; CHECK-SAME: i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], 1
; CHECK-NEXT:    br label %[[OUTER:.*]]
; CHECK:       [[OUTER]]:
; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[IV1_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    store volatile i32 [[IV1]], ptr @A, align 4
; CHECK-NEXT:    [[IV1_NEXT]] = add nuw nsw i32 [[IV1]], 1
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, %[[OUTER]] ], [ [[IV2_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT:    store volatile i32 [[IV2]], ptr @A, align 4
; CHECK-NEXT:    [[IV2_NEXT]] = add nuw nsw i32 [[IV2]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV2]], 20
; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[INNER_LATCH]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK:       [[INNER_LATCH]]:
; CHECK-NEXT:    [[EXITCOND2:%.*]] = icmp ne i32 [[IV2_NEXT]], [[TMP0]]
; CHECK-NEXT:    br i1 [[EXITCOND2]], label %[[INNER_HEADER]], label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[EXITCOND3:%.*]] = icmp ne i32 [[IV1_NEXT]], 21
; CHECK-NEXT:    br i1 [[EXITCOND3]], label %[[OUTER]], label %[[EXIT_LOOPEXIT1:.*]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT:.*]]
; CHECK:       [[EXIT_LOOPEXIT1]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %outer.header

outer.header:
  %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %outer.latch ]
  store volatile i32 %iv1, ptr @A
  %iv1.next = add i32 %iv1, 1
  br label %inner.header

inner.header:
  %iv2 = phi i32 [ 0, %outer.header ], [ %iv2.next, %inner.latch ]
  store volatile i32 %iv2, ptr @A
  %iv2.next = add i32 %iv2, 1
  %inner.ec.1 = icmp ult i32 %iv2, 20
  br i1 %inner.ec.1, label %inner.latch, label %exit

inner.latch:
  %inner.ec.2 = icmp ult i32 %iv2, %n
  br i1 %inner.ec.2, label %inner.header, label %outer.latch

outer.latch:
  %outertest = icmp ult i32 %iv1, 20
  br i1 %outertest, label %outer.header, label %exit

exit:
  ret void
}

define i32 @no_flag_leak_through_shared_udiv(i32 %start, i32 %n, i1 %c) {
; CHECK-LABEL: define i32 @no_flag_leak_through_shared_udiv(
; CHECK-SAME: i32 [[START:%.*]], i32 [[N:%.*]], i1 [[C:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br i1 [[C]], label %[[PH_1:.*]], label %[[PH_2:.*]]
; CHECK:       [[PH_1]]:
; CHECK-NEXT:    br label %[[LOOP_1_HEADER:.*]]
; CHECK:       [[LOOP_1_HEADER]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT_1:.*]], label %[[LOOP_1_LATCH:.*]]
; CHECK:       [[LOOP_1_LATCH]]:
; CHECK-NEXT:    br label %[[LOOP_1_HEADER]]
; CHECK:       [[EXIT_1]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], [[START]]
; CHECK-NEXT:    [[TMP1:%.*]] = udiv i32 [[TMP0]], 3
; CHECK-NEXT:    ret i32 [[TMP1]]
; CHECK:       [[PH_2]]:
; CHECK-NEXT:    br label %[[LOOP_2_HEADER:.*]]
; CHECK:       [[LOOP_2_HEADER]]:
; CHECK-NEXT:    br i1 true, label %[[EXIT_2:.*]], label %[[LOOP_2_LATCH:.*]]
; CHECK:       [[LOOP_2_LATCH]]:
; CHECK-NEXT:    br label %[[LOOP_2_HEADER]]
; CHECK:       [[EXIT_2]]:
; CHECK-NEXT:    [[TMP2:%.*]] = add nuw i32 [[N]], [[START]]
; CHECK-NEXT:    [[TMP3:%.*]] = udiv i32 [[TMP2]], 3
; CHECK-NEXT:    ret i32 [[TMP3]]
;
entry:
  br i1 %c, label %ph.1, label %ph.2

ph.1:
  br label %loop.1.header

loop.1.header:
  %v = phi i32 [ %start, %ph.1 ], [ %v.next, %loop.1.latch ]
  %i = phi i32 [ 0, %ph.1 ], [ %i.next, %loop.1.latch ]
  %dv = udiv i32 %v, 3
  %done = icmp eq i32 %i, %n
  br i1 %done, label %exit.1, label %loop.1.latch

loop.1.latch:
  %v.next = add i32 %v, 1
  %i.next = add i32 %i, 1
  br label %loop.1.header

exit.1:
  ret i32 %dv

ph.2:
  br label %loop.2.header

loop.2.header:
  %v2 = phi i32 [ %start, %ph.2 ], [ %v2.next, %loop.2.latch ]
  %i2 = phi i32 [ 0, %ph.2 ], [ %i2.next, %loop.2.latch ]
  %dv2 = udiv i32 %v2, 3
  %done2 = icmp eq i32 %i2, %n
  br i1 %done2, label %exit.2, label %loop.2.latch

loop.2.latch:
  %v2.next = add nuw i32 %v2, 1
  %i2.next = add i32 %i2, 1
  br label %loop.2.header

exit.2:
  ret i32 %dv2
}

define ptr @ptr_step_mul_nuw(ptr %first, ptr %last) {
; CHECK-LABEL: define ptr @ptr_step_mul_nuw(
; CHECK-SAME: ptr [[FIRST:%.*]], ptr [[LAST:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[FIRST2:%.*]] = ptrtoaddr ptr [[FIRST]] to i64
; CHECK-NEXT:    [[LAST1:%.*]] = ptrtoaddr ptr [[LAST]] to i64
; CHECK-NEXT:    [[C0:%.*]] = icmp ult ptr [[FIRST]], [[LAST]]
; CHECK-NEXT:    br i1 [[C0]], label %[[LOOP_PREHEADER:.*]], label %[[DONE:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    br i1 false, label %[[LOOP]], label %[[EXIT:.*]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[FIRST2]], 24
; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[LAST1]], i64 [[TMP0]])
; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[UMAX]], -24
; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[TMP1]], [[FIRST2]]
; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP2]], i64 1)
; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2]], [[UMIN]]
; CHECK-NEXT:    [[TMP4:%.*]] = udiv i64 [[TMP3]], 24
; CHECK-NEXT:    [[TMP5:%.*]] = add i64 [[UMIN]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = mul nuw i64 [[TMP5]], 24
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr nuw i8, ptr [[FIRST]], i64 [[TMP6]]
; CHECK-NEXT:    ret ptr [[SCEVGEP]]
; CHECK:       [[DONE]]:
; CHECK-NEXT:    ret ptr [[FIRST]]
;
entry:
  %c0 = icmp ult ptr %first, %last
  br i1 %c0, label %loop, label %done

loop:
  %p = phi ptr [ %first, %entry ], [ %p.next, %loop ]
  %p.next = getelementptr inbounds nuw i8, ptr %p, i64 24
  %c = icmp ult ptr %p.next, %last
  br i1 %c, label %loop, label %exit

exit:
  %lc = phi ptr [ %p, %loop ]
  ret ptr %lc

done:
  ret ptr %first
}

define i32 @exit_value_of_scaled_add_with_use_flags(ptr %p, i64 %n) {
; CHECK-LABEL: define i32 @exit_value_of_scaled_add_with_use_flags(
; CHECK-SAME: ptr [[P:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[N_PLUS_1:%.*]] = add i64 [[N]], 1
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    br label %[[INNER_HEADER:.*]]
; CHECK:       [[INNER_HEADER]]:
; CHECK-NEXT:    [[INNER_COUNT:%.*]] = phi i64 [ [[N_PLUS_1]], %[[OUTER_HEADER]] ], [ [[INNER_COUNT_DEC:%.*]], %[[INNER_HEADER]] ]
; CHECK-NEXT:    [[INNER_IV:%.*]] = phi i64 [ 0, %[[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER_HEADER]] ]
; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i64 [[OUTER_IV]], [[N_PLUS_1]]
; CHECK-NEXT:    [[GEP_ROW:%.*]] = getelementptr nuw i32, ptr [[P]], i64 [[MUL]]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr [[GEP_ROW]], i64 [[INNER_IV]]
; CHECK-NEXT:    [[L:%.*]] = load i32, ptr [[GEP]], align 4
; CHECK-NEXT:    [[INNER_IV_NEXT]] = add nuw i64 [[INNER_IV]], 1
; CHECK-NEXT:    [[INNER_COUNT_DEC]] = add i64 [[INNER_COUNT]], -1
; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp sgt i64 [[INNER_COUNT]], 0
; CHECK-NEXT:    br i1 [[INNER_COND]], label %[[INNER_HEADER]], label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[L_LCSSA:%.*]] = phi i32 [ [[L]], %[[INNER_HEADER]] ]
; CHECK-NEXT:    [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT:    [[OUTER_COND:%.*]] = icmp ne i64 [[OUTER_IV_NEXT]], [[N]]
; CHECK-NEXT:    br i1 [[OUTER_COND]], label %[[OUTER_HEADER]], label %[[EXIT:.*]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[L_LCSSA_LCSSA:%.*]] = phi i32 [ [[L_LCSSA]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    ret i32 [[L_LCSSA_LCSSA]]
;
entry:
  %n.plus.1 = add i64 %n, 1
  br label %outer.header

outer.header:
  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
  br label %inner.header

inner.header:
  %inner.count = phi i64 [ %n.plus.1, %outer.header ], [ %inner.count.dec, %inner.header ]
  %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner.header ]
  %mul = mul nuw i64 %outer.iv, %n.plus.1
  %gep.row = getelementptr nuw i32, ptr %p, i64 %mul
  %gep = getelementptr i32, ptr %gep.row, i64 %inner.iv
  %l = load i32, ptr %gep, align 4
  %inner.iv.next = add i64 %inner.iv, 1
  %inner.count.dec = add i64 %inner.count, -1
  %inner.cond = icmp sgt i64 %inner.count, 0
  br i1 %inner.cond, label %inner.header, label %outer.latch

outer.latch:
  %outer.iv.next = add i64 %outer.iv, 1
  %outer.cond = icmp ne i64 %outer.iv.next, %n
  br i1 %outer.cond, label %outer.header, label %exit

exit:
  ret i32 %l
}