| ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py |
| ; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s |
| |
| ; Test cases that require rewriting zext SCEV expression with infomration from |
| ; the loop guards. |
| |
| define void @rewrite_zext(i32 %n) { |
| ; CHECK-LABEL: 'rewrite_zext' |
| ; CHECK-NEXT: Classifying expressions for: @rewrite_zext |
| ; CHECK-NEXT: %ext = zext i32 %n to i64 |
| ; CHECK-NEXT: --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296) |
| ; CHECK-NEXT: %n.vec = and i64 %ext, -8 |
| ; CHECK-NEXT: --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289) |
| ; CHECK-NEXT: %index = phi i64 [ 0, %check ], [ %index.next, %loop ] |
| ; CHECK-NEXT: --> {0,+,8}<nuw><nsw><%loop> U: [0,17) S: [0,17) Exits: (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw> LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %index.next = add nuw nsw i64 %index, 8 |
| ; CHECK-NEXT: --> {8,+,8}<nuw><nsw><%loop> U: [8,25) S: [8,25) Exits: (8 + (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw>) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8) |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 2 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8) |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %ext = zext i32 %n to i64 |
| %cmp5 = icmp ule i64 %ext, 24 |
| br i1 %cmp5, label %check, label %exit |
| |
| check: ; preds = %entry |
| %min.iters.check = icmp ult i64 %ext, 8 |
| %n.vec = and i64 %ext, -8 |
| br i1 %min.iters.check, label %exit, label %loop |
| |
| loop: |
| %index = phi i64 [ 0, %check ], [ %index.next, %loop ] |
| %index.next = add nuw nsw i64 %index, 8 |
| %ec = icmp eq i64 %index.next, %n.vec |
| br i1 %ec, label %exit, label %loop |
| |
| exit: |
| ret void |
| } |
| |
| ; Test case from PR40961. |
| define i32 @rewrite_zext_min_max(i32 %N, i32* %arr) { |
| ; CHECK-LABEL: 'rewrite_zext_min_max' |
| ; CHECK-NEXT: Classifying expressions for: @rewrite_zext_min_max |
| ; CHECK-NEXT: %umin = call i32 @llvm.umin.i32(i32 %N, i32 16) |
| ; CHECK-NEXT: --> (16 umin %N) U: [0,17) S: [0,17) |
| ; CHECK-NEXT: %ext = zext i32 %umin to i64 |
| ; CHECK-NEXT: --> (zext i32 (16 umin %N) to i64) U: [0,17) S: [0,17) |
| ; CHECK-NEXT: %n.vec = and i64 %ext, 28 |
| ; CHECK-NEXT: --> (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw> U: [0,17) S: [0,17) |
| ; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] |
| ; CHECK-NEXT: --> {0,+,4}<nuw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %gep = getelementptr inbounds i32, i32* %arr, i64 %index |
| ; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %index.next = add nuw i64 %index, 4 |
| ; CHECK-NEXT: --> {4,+,4}<nuw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_min_max |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4) |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 3 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4) |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %umin = call i32 @llvm.umin.i32(i32 %N, i32 16) |
| %ext = zext i32 %umin to i64 |
| %min.iters.check = icmp ult i64 %ext, 4 |
| br i1 %min.iters.check, label %exit, label %loop.ph |
| |
| loop.ph: |
| %n.vec = and i64 %ext, 28 |
| br label %loop |
| |
| ; %n.vec is [4, 16) and a multiple of 4. |
| loop: |
| %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ] |
| %gep = getelementptr inbounds i32, i32* %arr, i64 %index |
| store i32 0, i32* %gep |
| %index.next = add nuw i64 %index, 4 |
| %ec = icmp eq i64 %index.next, %n.vec |
| br i1 %ec, label %exit, label %loop |
| |
| exit: |
| ret i32 0 |
| } |
| |
| ; Test case from PR52464. applyLoopGuards needs to apply information about %and |
| ; to %ext, which requires rewriting the zext. |
| define i32 @rewrite_zext_with_info_from_icmp_ne(i32 %N) { |
| ; CHECK-LABEL: 'rewrite_zext_with_info_from_icmp_ne' |
| ; CHECK-NEXT: Classifying expressions for: @rewrite_zext_with_info_from_icmp_ne |
| ; CHECK-NEXT: %and = and i32 %N, 3 |
| ; CHECK-NEXT: --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4) |
| ; CHECK-NEXT: %and.sub.1 = add nsw i32 %and, -1 |
| ; CHECK-NEXT: --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3) |
| ; CHECK-NEXT: %ext = zext i32 %and.sub.1 to i64 |
| ; CHECK-NEXT: --> (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296) |
| ; CHECK-NEXT: %n.rnd.up = add nuw nsw i64 %ext, 4 |
| ; CHECK-NEXT: --> (4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> U: [4,4294967300) S: [4,4294967300) |
| ; CHECK-NEXT: %n.vec = and i64 %n.rnd.up, 8589934588 |
| ; CHECK-NEXT: --> (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> U: [4,4294967297) S: [4,4294967297) |
| ; CHECK-NEXT: %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ] |
| ; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %iv.next = add i64 %iv, 4 |
| ; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,5) S: [4,5) Exits: 4 LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_with_info_from_icmp_ne |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is 0 |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 0 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 0 |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %and = and i32 %N, 3 |
| %cmp6.not = icmp eq i32 %and, 0 |
| br i1 %cmp6.not, label %exit, label %loop.ph |
| |
| loop.ph: |
| %and.sub.1 = add nsw i32 %and, -1 |
| %ext = zext i32 %and.sub.1 to i64 |
| %n.rnd.up = add nuw nsw i64 %ext, 4 |
| %n.vec = and i64 %n.rnd.up, 8589934588 |
| br label %loop |
| |
| loop: |
| %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ] |
| %iv.next = add i64 %iv, 4 |
| call void @use(i64 %iv.next) |
| %ec = icmp eq i64 %iv.next, %n.vec |
| br i1 %ec, label %exit, label %loop |
| |
| exit: |
| ret i32 0 |
| } |
| |
| ; Similar to @rewrite_zext_with_info_from_icmp_ne, but the loop is not guarded by %and != 0, |
| ; hence the subsequent subtraction may yield a negative number. |
| define i32 @rewrite_zext_no_icmp_ne(i32 %N) { |
| ; CHECK-LABEL: 'rewrite_zext_no_icmp_ne' |
| ; CHECK-NEXT: Classifying expressions for: @rewrite_zext_no_icmp_ne |
| ; CHECK-NEXT: %and = and i32 %N, 3 |
| ; CHECK-NEXT: --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4) |
| ; CHECK-NEXT: %and.sub.1 = add nsw i32 %and, -1 |
| ; CHECK-NEXT: --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3) |
| ; CHECK-NEXT: %ext = zext i32 %and.sub.1 to i64 |
| ; CHECK-NEXT: --> (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296) |
| ; CHECK-NEXT: %n.rnd.up = add nuw nsw i64 %ext, 4 |
| ; CHECK-NEXT: --> (4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> U: [4,4294967300) S: [4,4294967300) |
| ; CHECK-NEXT: %n.vec = and i64 %n.rnd.up, 8589934588 |
| ; CHECK-NEXT: --> (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> U: [4,4294967297) S: [4,4294967297) |
| ; CHECK-NEXT: %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ] |
| ; CHECK-NEXT: --> {0,+,4}<%loop> U: [0,4294967293) S: [0,4294967293) Exits: (4 * ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4))<nuw><nsw> LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %iv.next = add i64 %iv, 4 |
| ; CHECK-NEXT: --> {4,+,4}<%loop> U: [4,4294967297) S: [4,4294967297) Exits: (4 + (4 * ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4))<nuw><nsw>)<nuw><nsw> LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_no_icmp_ne |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4) |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 1073741823 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4) |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %and = and i32 %N, 3 |
| br label %loop.ph |
| |
| loop.ph: |
| %and.sub.1 = add nsw i32 %and, -1 |
| %ext = zext i32 %and.sub.1 to i64 |
| %n.rnd.up = add nuw nsw i64 %ext, 4 |
| %n.vec = and i64 %n.rnd.up, 8589934588 |
| br label %loop |
| |
| loop: |
| %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ] |
| %iv.next = add i64 %iv, 4 |
| call void @use(i64 %iv.next) |
| %ec = icmp eq i64 %iv.next, %n.vec |
| br i1 %ec, label %exit, label %loop |
| |
| exit: |
| ret i32 0 |
| } |
| |
| ; Make sure no information is lost for conditions on both %n and (zext %n). |
| define void @rewrite_zext_and_base_1(i32 %n) { |
| ; CHECK-LABEL: 'rewrite_zext_and_base_1' |
| ; CHECK-NEXT: Classifying expressions for: @rewrite_zext_and_base_1 |
| ; CHECK-NEXT: %ext = zext i32 %n to i64 |
| ; CHECK-NEXT: --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296) |
| ; CHECK-NEXT: %n.vec = and i64 %ext, -8 |
| ; CHECK-NEXT: --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289) |
| ; CHECK-NEXT: %index = phi i64 [ 0, %check ], [ %index.next, %loop ] |
| ; CHECK-NEXT: --> {0,+,8}<nuw><nsw><%loop> U: [0,25) S: [0,25) Exits: (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw> LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %index.next = add nuw nsw i64 %index, 8 |
| ; CHECK-NEXT: --> {8,+,8}<nuw><nsw><%loop> U: [8,33) S: [8,33) Exits: (8 + (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw>) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_and_base_1 |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8) |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 3 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8) |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %ext = zext i32 %n to i64 |
| %cmp5 = icmp ule i64 %ext, 48 |
| br i1 %cmp5, label %check.1, label %exit |
| |
| check.1: |
| %cmp.2 = icmp ule i32 %n, 32 |
| br i1 %cmp.2, label %check, label %exit |
| |
| |
| check: ; preds = %entry |
| %min.iters.check = icmp ult i64 %ext, 8 |
| %n.vec = and i64 %ext, -8 |
| br i1 %min.iters.check, label %exit, label %loop |
| |
| loop: |
| %index = phi i64 [ 0, %check ], [ %index.next, %loop ] |
| %index.next = add nuw nsw i64 %index, 8 |
| %ec = icmp eq i64 %index.next, %n.vec |
| br i1 %ec, label %exit, label %loop |
| |
| exit: |
| ret void |
| } |
| |
| ; Make sure no information is lost for conditions on both %n and (zext %n). |
| define void @rewrite_zext_and_base_2(i32 %n) { |
| ; CHECK-LABEL: 'rewrite_zext_and_base_2' |
| ; CHECK-NEXT: Classifying expressions for: @rewrite_zext_and_base_2 |
| ; CHECK-NEXT: %ext = zext i32 %n to i64 |
| ; CHECK-NEXT: --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296) |
| ; CHECK-NEXT: %n.vec = and i64 %ext, -8 |
| ; CHECK-NEXT: --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289) |
| ; CHECK-NEXT: %index = phi i64 [ 0, %check ], [ %index.next, %loop ] |
| ; CHECK-NEXT: --> {0,+,8}<nuw><nsw><%loop> U: [0,25) S: [0,25) Exits: (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw> LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %index.next = add nuw nsw i64 %index, 8 |
| ; CHECK-NEXT: --> {8,+,8}<nuw><nsw><%loop> U: [8,33) S: [8,33) Exits: (8 + (8 * ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8))<nuw>) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_and_base_2 |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8) |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 3 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8) |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %ext = zext i32 %n to i64 |
| %cmp5 = icmp ule i64 %ext, 32 |
| br i1 %cmp5, label %check.1, label %exit |
| |
| check.1: |
| %cmp.2 = icmp ule i32 %n, 48 |
| br i1 %cmp.2, label %check, label %exit |
| |
| check: ; preds = %entry |
| %min.iters.check = icmp ult i64 %ext, 8 |
| %n.vec = and i64 %ext, -8 |
| br i1 %min.iters.check, label %exit, label %loop |
| |
| loop: |
| %index = phi i64 [ 0, %check ], [ %index.next, %loop ] |
| %index.next = add nuw nsw i64 %index, 8 |
| %ec = icmp eq i64 %index.next, %n.vec |
| br i1 %ec, label %exit, label %loop |
| |
| exit: |
| ret void |
| } |
| |
| define void @guard_pessimizes_analysis_step2(i1 %c, i32 %N) { |
| ; CHECK-LABEL: 'guard_pessimizes_analysis_step2' |
| ; CHECK-NEXT: Classifying expressions for: @guard_pessimizes_analysis_step2 |
| ; CHECK-NEXT: %N.ext = zext i32 %N to i64 |
| ; CHECK-NEXT: --> (zext i32 %N to i64) U: [0,4294967296) S: [0,4294967296) |
| ; CHECK-NEXT: %init = phi i64 [ 2, %entry ], [ 4, %bb1 ] |
| ; CHECK-NEXT: --> %init U: [2,5) S: [2,5) |
| ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ] |
| ; CHECK-NEXT: --> {%init,+,2}<%loop> U: [2,17) S: [2,17) Exits: ((2 * ((14 + (-1 * %init)<nsw>)<nsw> /u 2))<nuw><nsw> + %init) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: %iv.next = add i64 %iv, 2 |
| ; CHECK-NEXT: --> {(2 + %init)<nuw><nsw>,+,2}<%loop> U: [4,19) S: [4,19) Exits: (2 + (2 * ((14 + (-1 * %init)<nsw>)<nsw> /u 2))<nuw><nsw> + %init) LoopDispositions: { %loop: Computable } |
| ; CHECK-NEXT: Determining loop execution counts for: @guard_pessimizes_analysis_step2 |
| ; CHECK-NEXT: Loop %loop: backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2) |
| ; CHECK-NEXT: Loop %loop: max backedge-taken count is 6 |
| ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2) |
| ; CHECK-NEXT: Predicates: |
| ; CHECK: Loop %loop: Trip multiple is 1 |
| ; |
| entry: |
| %N.ext = zext i32 %N to i64 |
| br i1 %c, label %bb1, label %guard |
| |
| bb1: |
| br label %guard |
| |
| guard: |
| %init = phi i64 [ 2, %entry ], [ 4, %bb1 ] |
| %c.1 = icmp ult i64 %init, %N.ext |
| br i1 %c.1, label %loop.ph, label %exit |
| |
| loop.ph: |
| br label %loop |
| |
| loop: |
| %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ] |
| %iv.next = add i64 %iv, 2 |
| %exitcond = icmp eq i64 %iv.next, 16 |
| br i1 %exitcond, label %exit, label %loop |
| |
| exit: |
| ret void |
| } |
| declare void @use(i64) |
| |
| declare i32 @llvm.umin.i32(i32, i32) |