| ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py |
| ; RUN: opt -indvars -S < %s | FileCheck %s |
| ; RUN: opt -passes=indvars -S < %s | FileCheck %s |
| |
| ; Monotonic decrementing iv. we should be able to prove that %iv.next <s len |
| ; basing on its nsw and the fact that its starting value <s len. |
| define i32 @test_01(i32* %p) { |
| ; CHECK-LABEL: @test_01( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG0:!range !.*]] |
| ; CHECK-NEXT: br label [[LOOP:%.*]] |
| ; CHECK: loop: |
| ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] |
| ; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], -1 |
| ; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] |
| ; CHECK: backedge: |
| ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0 |
| ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] |
| ; CHECK: fail: |
| ; CHECK-NEXT: ret i32 -1 |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret i32 0 |
| ; |
| entry: |
| %len = load i32, i32* %p, !range !0 |
| br label %loop |
| |
| loop: |
| %iv = phi i32 [%len, %entry], [%iv.next, %backedge] |
| %iv.next = add i32 %iv, -1 |
| %rc = icmp slt i32 %iv.next, %len |
| br i1 %rc, label %backedge, label %fail |
| |
| backedge: |
| %loop.cond = icmp ne i32 %iv, 0 |
| br i1 %loop.cond, label %loop, label %exit |
| |
| fail: |
| ret i32 -1 |
| |
| exit: |
| ret i32 0 |
| } |
| |
| ; We should not remove this range check because signed overflow is possible here (start at len = 0). |
| define i32 @test_01_neg(i32* %p) { |
| ; CHECK-LABEL: @test_01_neg( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG0]] |
| ; CHECK-NEXT: br label [[LOOP:%.*]] |
| ; CHECK: loop: |
| ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] |
| ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 |
| ; CHECK-NEXT: [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]] |
| ; CHECK-NEXT: br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]] |
| ; CHECK: backedge: |
| ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1 |
| ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] |
| ; CHECK: fail: |
| ; CHECK-NEXT: ret i32 -1 |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret i32 0 |
| ; |
| entry: |
| %len = load i32, i32* %p, !range !0 |
| br label %loop |
| |
| loop: |
| %iv = phi i32 [%len, %entry], [%iv.next, %backedge] |
| %iv.next = add i32 %iv, -1 |
| %rc = icmp slt i32 %iv.next, %len |
| br i1 %rc, label %backedge, label %fail |
| |
| backedge: |
| %loop.cond = icmp ne i32 %iv, 1 |
| br i1 %loop.cond, label %loop, label %exit |
| |
| fail: |
| ret i32 -1 |
| |
| exit: |
| ret i32 0 |
| } |
| |
| ; Monotonic incrementing iv. we should be able to prove that %iv.next >s len |
| ; basing on its nsw and the fact that its starting value >s len. |
| define i32 @test_02(i32* %p) { |
| ; CHECK-LABEL: @test_02( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG1:!range !.*]] |
| ; CHECK-NEXT: br label [[LOOP:%.*]] |
| ; CHECK: loop: |
| ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] |
| ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 |
| ; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] |
| ; CHECK: backedge: |
| ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0 |
| ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] |
| ; CHECK: fail: |
| ; CHECK-NEXT: ret i32 -1 |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret i32 0 |
| ; |
| entry: |
| %len = load i32, i32* %p, !range !1 |
| br label %loop |
| |
| loop: |
| %iv = phi i32 [%len, %entry], [%iv.next, %backedge] |
| %iv.next = add i32 %iv, 1 |
| %rc = icmp sgt i32 %iv.next, %len |
| br i1 %rc, label %backedge, label %fail |
| |
| backedge: |
| %loop.cond = icmp ne i32 %iv, 0 |
| br i1 %loop.cond, label %loop, label %exit |
| |
| fail: |
| ret i32 -1 |
| |
| exit: |
| ret i32 0 |
| } |
| |
| ; We should not remove this range check because signed overflow is possible here (start at len = -1). |
| define i32 @test_02_neg(i32* %p) { |
| ; CHECK-LABEL: @test_02_neg( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG1]] |
| ; CHECK-NEXT: br label [[LOOP:%.*]] |
| ; CHECK: loop: |
| ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] |
| ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 |
| ; CHECK-NEXT: [[RC:%.*]] = icmp sgt i32 [[IV_NEXT]], [[LEN]] |
| ; CHECK-NEXT: br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]] |
| ; CHECK: backedge: |
| ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], -2 |
| ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] |
| ; CHECK: fail: |
| ; CHECK-NEXT: ret i32 -1 |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret i32 0 |
| ; |
| entry: |
| %len = load i32, i32* %p, !range !1 |
| br label %loop |
| |
| loop: |
| %iv = phi i32 [%len, %entry], [%iv.next, %backedge] |
| %iv.next = add i32 %iv, 1 |
| %rc = icmp sgt i32 %iv.next, %len |
| br i1 %rc, label %backedge, label %fail |
| |
| backedge: |
| %loop.cond = icmp ne i32 %iv, -2 |
| br i1 %loop.cond, label %loop, label %exit |
| |
| fail: |
| ret i32 -1 |
| |
| exit: |
| ret i32 0 |
| } |
| |
| define i32 @test_03(i32* %p) { |
| ; CHECK-LABEL: @test_03( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG2:!range !.*]] |
| ; CHECK-NEXT: br label [[LOOP:%.*]] |
| ; CHECK: loop: |
| ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] |
| ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 |
| ; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] |
| ; CHECK: backedge: |
| ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1000 |
| ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] |
| ; CHECK: fail: |
| ; CHECK-NEXT: ret i32 -1 |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret i32 0 |
| ; |
| entry: |
| %len = load i32, i32* %p, !range !2 |
| br label %loop |
| |
| loop: |
| %iv = phi i32 [%len, %entry], [%iv.next, %backedge] |
| %iv.next = add i32 %iv, 1 |
| %rc = icmp sgt i32 %iv.next, %len |
| br i1 %rc, label %backedge, label %fail |
| |
| backedge: |
| %loop.cond = icmp ne i32 %iv, 1000 |
| br i1 %loop.cond, label %loop, label %exit |
| |
| fail: |
| ret i32 -1 |
| |
| exit: |
| ret i32 0 |
| } |
| |
| define i32 @test_04(i32* %p) { |
| ; CHECK-LABEL: @test_04( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG2]] |
| ; CHECK-NEXT: br label [[LOOP:%.*]] |
| ; CHECK: loop: |
| ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] |
| ; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], -1 |
| ; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] |
| ; CHECK: backedge: |
| ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0 |
| ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]] |
| ; CHECK: fail: |
| ; CHECK-NEXT: ret i32 -1 |
| ; CHECK: exit: |
| ; CHECK-NEXT: ret i32 0 |
| ; |
| entry: |
| %len = load i32, i32* %p, !range !2 |
| br label %loop |
| |
| loop: |
| %iv = phi i32 [%len, %entry], [%iv.next, %backedge] |
| %iv.next = add i32 %iv, -1 |
| %rc = icmp slt i32 %iv.next, %len |
| br i1 %rc, label %backedge, label %fail |
| |
| backedge: |
| %loop.cond = icmp ne i32 %iv, 0 |
| br i1 %loop.cond, label %loop, label %exit |
| |
| fail: |
| ret i32 -1 |
| |
| exit: |
| ret i32 0 |
| } |
| |
| !0 = !{i32 0, i32 2147483647} |
| !1 = !{i32 -2147483648, i32 0} |
| !2 = !{i32 0, i32 1000} |