; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>"  -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s

; A collection of tests that show we can use facts about an exit test to
; infer tighter bounds on an IV, and thus refine an IV into an addrec. The
; basic tactic being used is proving NW from exit structure and then
; implying NUW/NSW.  Once NSW/NUW is inferred, we can derive addrecs from
; the zext/sext cases that we couldn't at initial SCEV construction.

@G = external global i8

define void @nw_implies_nuw(i16 %n) mustprogress {
; CHECK-LABEL: 'nw_implies_nuw'
; CHECK-NEXT:  Determining loop execution counts for: @nw_implies_nuw
; CHECK-NEXT:  Loop %for.body: backedge-taken count is %n
; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is %n
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %for.body: Trip multiple is 1
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 1
  %zext = zext i8 %iv to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @neg_nw_nuw(i16 %n) mustprogress {
; CHECK-LABEL: 'neg_nw_nuw'
; CHECK-NEXT:  Determining loop execution counts for: @neg_nw_nuw
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, -1
  %zext = zext i8 %iv to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @nw_implies_nsw(i16 %n) mustprogress {
; CHECK-LABEL: 'nw_implies_nsw'
; CHECK-NEXT:  Determining loop execution counts for: @nw_implies_nsw
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (128 + (-128 smax %n))
; CHECK-NEXT:   Predicates:
; CHECK-NEXT:    {-128,+,1}<%for.body> Added Flags: <nssw>
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ -128, %entry ]
  %iv.next = add i8 %iv, 1
  %zext = sext i8 %iv to i16
  %cmp = icmp slt i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @neg_nw_nsw(i16 %n) mustprogress {
; CHECK-LABEL: 'neg_nw_nsw'
; CHECK-NEXT:  Determining loop execution counts for: @neg_nw_nsw
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ -128, %entry ]
  %iv.next = add i8 %iv, -1
  %zext = sext i8 %iv to i16
  %cmp = icmp slt i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}


define void @actually_infinite() {
; CHECK-LABEL: 'actually_infinite'
; CHECK-NEXT:  Determining loop execution counts for: @actually_infinite
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 257
; CHECK-NEXT:   Predicates:
; CHECK-NEXT:    {0,+,1}<%for.body> Added Flags: <nusw>
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  store volatile i8 %iv, i8* @G
  %iv.next = add i8 %iv, 1
  %zext = zext i8 %iv to i16
  %cmp = icmp ult i16 %zext, 257
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @rhs_mustexit_1(i16 %n.raw) mustprogress {
; CHECK-LABEL: 'rhs_mustexit_1'
; CHECK-NEXT:  Determining loop execution counts for: @rhs_mustexit_1
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>))
; CHECK-NEXT:   Predicates:
; CHECK-NEXT:    {1,+,1}<nw><%for.body> Added Flags: <nusw>
;
entry:
  %n.and = and i16 %n.raw, 255
  %n = add nsw i16 %n.and, -1
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 1
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @rhs_mustexit_3(i16 %n.raw) mustprogress {
; CHECK-LABEL: 'rhs_mustexit_3'
; CHECK-NEXT:  Determining loop execution counts for: @rhs_mustexit_3
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
;
entry:
  %n.and = and i16 %n.raw, 255
  %n = add nsw i16 %n.and, -3
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 3
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

; Unknown, but non-zero step
define void @rhs_mustexit_nonzero_step(i16 %n.raw, i8 %step.raw) mustprogress {
; CHECK-LABEL: 'rhs_mustexit_nonzero_step'
; CHECK-NEXT:  Determining loop execution counts for: @rhs_mustexit_nonzero_step
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
;
entry:
  %n.and = and i16 %n.raw, 255
  %n = add nsw i16 %n.and, -3
  %step = add nuw i8 %step.raw, 1
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, %step
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @neg_maybe_zero_step(i16 %n.raw, i8 %step) mustprogress {
; CHECK-LABEL: 'neg_maybe_zero_step'
; CHECK-NEXT:  Determining loop execution counts for: @neg_maybe_zero_step
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
;
entry:
  %n.and = and i16 %n.raw, 255
  %n = add nsw i16 %n.and, -3
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, %step
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @neg_rhs_wrong_range(i16 %n.raw) mustprogress {
; CHECK-LABEL: 'neg_rhs_wrong_range'
; CHECK-NEXT:  Determining loop execution counts for: @neg_rhs_wrong_range
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-1 + (2 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>)) /u 2)
; CHECK-NEXT:   Predicates:
; CHECK-NEXT:    {2,+,2}<nw><%for.body> Added Flags: <nusw>
;
entry:
  %n.and = and i16 %n.raw, 255
  %n = add nsw i16 %n.and, -1
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 2
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @neg_rhs_maybe_infinite(i16 %n.raw) {
; CHECK-LABEL: 'neg_rhs_maybe_infinite'
; CHECK-NEXT:  Determining loop execution counts for: @neg_rhs_maybe_infinite
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>))
; CHECK-NEXT:   Predicates:
; CHECK-NEXT:    {1,+,1}<%for.body> Added Flags: <nusw>
;
entry:
  %n.and = and i16 %n.raw, 255
  %n = add nsw i16 %n.and, -1
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 1
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

; Because of the range on RHS including only values within i8, we don't need
; the must exit property
define void @rhs_narrow_range(i16 %n.raw) {
; CHECK-LABEL: 'rhs_narrow_range'
; CHECK-NEXT:  Determining loop execution counts for: @rhs_narrow_range
; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 umax (2 * (zext i7 (trunc i16 (%n.raw /u 2) to i7) to i16))<nuw><nsw>))<nsw>
; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 253
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (2 * (zext i7 (trunc i16 (%n.raw /u 2) to i7) to i16))<nuw><nsw>))<nsw>
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %for.body: Trip multiple is 1
;
entry:
  %n = and i16 %n.raw, 254
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 1
  store i8 %iv, i8* @G
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @ugt_constant_rhs(i16 %n.raw, i8 %start) mustprogress {
;
; CHECK-LABEL: 'ugt_constant_rhs'
; CHECK-NEXT:  Determining loop execution counts for: @ugt_constant_rhs
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]
  %iv.next = add i8 %iv, 1
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ugt i16 %zext, 254
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @ult_constant_rhs(i16 %n.raw, i8 %start) {
;
; CHECK-LABEL: 'ult_constant_rhs'
; CHECK-NEXT:  Determining loop execution counts for: @ult_constant_rhs
; CHECK-NEXT:  Loop %for.body: backedge-taken count is (255 + (-1 * (zext i8 (1 + %start) to i16))<nsw>)<nsw>
; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 255
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (255 + (-1 * (zext i8 (1 + %start) to i16))<nsw>)<nsw>
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %for.body: Trip multiple is 1
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]
  %iv.next = add i8 %iv, 1
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, 255
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @ult_constant_rhs_stride2(i16 %n.raw, i8 %start) {
;
; CHECK-LABEL: 'ult_constant_rhs_stride2'
; CHECK-NEXT:  Determining loop execution counts for: @ult_constant_rhs_stride2
; CHECK-NEXT:  Loop %for.body: backedge-taken count is ((1 + (-1 * (zext i8 (2 + %start) to i16))<nsw> + (254 umax (zext i8 (2 + %start) to i16))) /u 2)
; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 127
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((1 + (-1 * (zext i8 (2 + %start) to i16))<nsw> + (254 umax (zext i8 (2 + %start) to i16))) /u 2)
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %for.body: Trip multiple is 1
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]
  %iv.next = add i8 %iv, 2
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, 254
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @ult_constant_rhs_stride2_neg(i16 %n.raw, i8 %start) {
;
; CHECK-LABEL: 'ult_constant_rhs_stride2_neg'
; CHECK-NEXT:  Determining loop execution counts for: @ult_constant_rhs_stride2_neg
; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((256 + (-1 * (zext i8 (2 + %start) to i16))<nsw>)<nsw> /u 2)
; CHECK-NEXT:   Predicates:
; CHECK-NEXT:    {(2 + %start),+,2}<%for.body> Added Flags: <nusw>
;
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ]
  %iv.next = add i8 %iv, 2
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, 255
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}


define void @ult_restricted_rhs(i16 %n.raw) {
; CHECK-LABEL: 'ult_restricted_rhs'
; CHECK-NEXT:  Determining loop execution counts for: @ult_restricted_rhs
; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 umax (zext i8 (trunc i16 %n.raw to i8) to i16)))<nsw>
; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 254
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (zext i8 (trunc i16 %n.raw to i8) to i16)))<nsw>
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %for.body: Trip multiple is 1
;
entry:
  %n = and i16 %n.raw, 255
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 1
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}

define void @ult_guarded_rhs(i16 %n) {;
; CHECK-LABEL: 'ult_guarded_rhs'
; CHECK-NEXT:  Determining loop execution counts for: @ult_guarded_rhs
; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + (1 umax %n))
; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -2
; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax %n))
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %for.body: Trip multiple is 1
;
entry:
  %in_range = icmp ult i16 %n, 256
  br i1 %in_range, label %for.body, label %for.end

for.body:                                         ; preds = %entry, %for.body
  %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ]
  %iv.next = add i8 %iv, 1
  %zext = zext i8 %iv.next to i16
  %cmp = icmp ult i16 %zext, %n
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body, %entry
  ret void
}


declare void @llvm.assume(i1)