| ; 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) |
| |