[IRCE] Parse range checks in the form of 'LHS - RHS vs Limit'

Introduced the following range checks forms parsing:
* IV - Offset vs Limit
* Offset - IV vs Limit

Range's end boundary is computed as (Offset +/- Limit ).

If it's not possible to prove at compile time that computed upper bound
will not overflow, then scale boundary computation to a wider type to
perform overflow check at runtime.

Runtime overflow will be implemented in the next patch. In the meantime
safe range for such kind of checks isn't computed.

Reviewed By: skatkov

Differential Revision: https://reviews.llvm.org/D154069

1 files changed, 270 insertions, 14 deletions

diff --git a/llvm/test/Transforms/IRCE/iv-plus-offset-range-check.ll b/llvm/test/Transforms/IRCE/iv-plus-offset-range-check.ll
index fbab857..f1d645f 100644
--- a/llvm/test/Transforms/IRCE/iv-plus-offset-range-check.ll
+++ b/llvm/test/Transforms/IRCE/iv-plus-offset-range-check.ll
@@ -1,5 +1,24 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
-; RUN: opt -verify-loop-info -passes=irce -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -passes=irce -irce-print-scaled-boundary-range-checks -S < %s 2>&1 | FileCheck %s
+
+
+; CHECK: irce: in function test1, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting>
+; CHECK-NEXT: there is range check with scaled boundary:
+; CHECK-NEXT: InductiveRangeCheck:
+; CHECK-NEXT:   Begin: 0  Step: 1  End: (-1 + (sext i8 %n to i16))<nsw>
+; CHECK-NEXT:   CheckUse:   br i1 %check, label %inbounds, label %out_of_bounds Operand: 0
+;
+; CHECK-NEXT: irce: in function test4, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting>
+; CHECK-NEXT: there is range check with scaled boundary:
+; CHECK-NEXT: InductiveRangeCheck:
+; CHECK-NEXT:   Begin: 0  Step: 1  End: (-2 + (sext i8 %n to i16))<nsw>
+; CHECK-NEXT:   CheckUse:   br i1 %check, label %inbounds, label %out_of_bounds Operand: 0
+;
+; CHECK-NEXT: irce: in function test_overflow_check_runtime, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting>
+; CHECK-NEXT: there is range check with scaled boundary:
+; CHECK-NEXT: InductiveRangeCheck:
+; CHECK-NEXT:   Begin: 0  Step: 1  End: (3 + (zext i8 %n to i16))<nuw><nsw>
+; CHECK-NEXT:   CheckUse:   br i1 %check, label %inbounds, label %out_of_bounds Operand: 0
 
 ; IV = 0; IV <s limit; IV += 1;
 ;   Check(N - IV >= 2)
@@ -66,25 +85,64 @@ define i8 @test1a(i8 %limit, ptr %p) {
 ; CHECK-NEXT:    [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
 ; CHECK-NEXT:    br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i8 [[N]], -1
+; CHECK-NEXT:    [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP0]], i8 0)
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[SMIN]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i8 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    [[SMIN2:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP2]])
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN2]], i8 0)
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader4:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp sge i8 [[SUB]], 2
-; CHECK-NEXT:    br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]]
 ; CHECK:       inbounds:
 ; CHECK-NEXT:    [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK:       main.exit.selector:
+; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA3:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       main.pseudo.exit:
+; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
+; CHECK:       exit.loopexit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA3]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK:       out_of_bounds.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
+; CHECK:       out_of_bounds.loopexit5:
+; CHECK-NEXT:    [[IDX_LCSSA_PH6:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out_of_bounds:
-; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH6]], [[OUT_OF_BOUNDS_LOOPEXIT5]] ]
 ; CHECK-NEXT:    ret i8 [[IDX_LCSSA]]
+; CHECK:       postloop:
+; CHECK-NEXT:    br label [[LOOP_POSTLOOP]]
+; CHECK:       loop.postloop:
+; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
+; CHECK-NEXT:    [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
+; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp sge i8 [[SUB_POSTLOOP]], 2
+; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
+; CHECK:       inbounds.postloop:
+; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
+; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP1:![0-9]+]], !irce.loop.clone [[META6:![0-9]+]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
@@ -338,7 +396,7 @@ define i8 @test3a(i8 %limit, ptr %p) {
 ; CHECK:       inbounds.postloop:
 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
 ; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP1:![0-9]+]], !irce.loop.clone !6
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP7:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
@@ -429,25 +487,69 @@ define i8 @test4a(i8 %limit, ptr %p) {
 ; CHECK-NEXT:    [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
 ; CHECK-NEXT:    br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[N]], -2
+; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i8 [[N]], 127
+; CHECK-NEXT:    [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0)
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]]
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i8 [[N]], -2
+; CHECK-NEXT:    [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP3]], i8 0)
+; CHECK-NEXT:    [[SMAX2:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 -1)
+; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i8 [[SMAX2]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul i8 [[TMP2]], [[TMP4]]
+; CHECK-NEXT:    [[SMIN3:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP5]])
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN3]], i8 0)
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[LOOP_PREHEADER6:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader6:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER6]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp sgt i8 [[SUB]], 2
-; CHECK-NEXT:    br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT7:%.*]]
 ; CHECK:       inbounds:
 ; CHECK-NEXT:    [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK:       main.exit.selector:
+; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA5:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[TMP8]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       main.pseudo.exit:
+; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
+; CHECK:       exit.loopexit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA5]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK:       out_of_bounds.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
+; CHECK:       out_of_bounds.loopexit7:
+; CHECK-NEXT:    [[IDX_LCSSA_PH8:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out_of_bounds:
-; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH8]], [[OUT_OF_BOUNDS_LOOPEXIT7]] ]
 ; CHECK-NEXT:    ret i8 [[IDX_LCSSA]]
+; CHECK:       postloop:
+; CHECK-NEXT:    br label [[LOOP_POSTLOOP]]
+; CHECK:       loop.postloop:
+; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
+; CHECK-NEXT:    [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
+; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], 2
+; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
+; CHECK:       inbounds.postloop:
+; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
+; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP8:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
@@ -652,7 +754,7 @@ define i8 @test6(i8 %limit, i8 %n) {
 ; CHECK:       inbounds.postloop:
 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
 ; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP7:![0-9]+]], !irce.loop.clone !6
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP9:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %precheck = icmp sgt i8 %limit, 0
@@ -743,7 +845,7 @@ define i8 @test6a(i8 %limit, ptr %p) {
 ; CHECK:       inbounds.postloop:
 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
 ; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP8:![0-9]+]], !irce.loop.clone !6
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP10:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
@@ -769,4 +871,158 @@ out_of_bounds:
   ret i8 %idx;
 }
 
+; IV = 0; IV <s limit; IV += 1;
+;   Check(N - IV > -2)
+;
+; IRCE is allowed.
+; IRCE will reassociate this range check to the 'IV < N + 2',
+; since N < 126 no-overflow fact is provable at compile time.
+define i8 @test_overflow_check_compile_time(i8 %limit, ptr %p) {
+; CHECK-LABEL: define i8 @test_overflow_check_compile_time
+; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG11:![0-9]+]]
+; CHECK-NEXT:    [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
+; CHECK-NEXT:    br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = add nuw nsw i8 [[N]], 2
+; CHECK-NEXT:    [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]])
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0)
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader3:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER3]] ]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
+; CHECK-NEXT:    [[CHECK:%.*]] = icmp sgt i8 [[SUB]], -2
+; CHECK-NEXT:    br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT4:%.*]]
+; CHECK:       inbounds:
+; CHECK-NEXT:    [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK:       main.exit.selector:
+; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA2:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       main.pseudo.exit:
+; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
+; CHECK:       exit.loopexit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA2]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK:       out_of_bounds.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
+; CHECK:       out_of_bounds.loopexit4:
+; CHECK-NEXT:    [[IDX_LCSSA_PH5:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
+; CHECK:       out_of_bounds:
+; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH5]], [[OUT_OF_BOUNDS_LOOPEXIT4]] ]
+; CHECK-NEXT:    ret i8 [[IDX_LCSSA]]
+; CHECK:       postloop:
+; CHECK-NEXT:    br label [[LOOP_POSTLOOP]]
+; CHECK:       loop.postloop:
+; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
+; CHECK-NEXT:    [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
+; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], -2
+; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
+; CHECK:       inbounds.postloop:
+; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
+; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP12:![0-9]+]], !irce.loop.clone [[META6]]
+;
+entry:
+  %n = load i8, ptr %p, !range !1
+  %precheck = icmp sgt i8 %limit, 0
+  br i1 %precheck, label %loop, label %exit
+
+loop:
+  %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
+  %sub = sub i8 %n, %idx
+  %check = icmp sgt i8 %sub, -2
+  br i1 %check, label %inbounds, label %out_of_bounds
+
+inbounds:
+  %idx.next = add nuw i8 %idx, 1
+  %cmp = icmp slt i8 %idx.next, %limit
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  %res = phi i8 [ 0, %entry ], [ %idx, %inbounds ]
+  ret i8 %res
+
+out_of_bounds:
+  ret i8 %idx;
+}
+
+; IV = 0; IV <s limit; IV += 1;
+;   Check(N - IV >= -2)
+;
+; TODO: IRCE is allowed.
+; IRCE will reassociate this range check to the 'IV < (N + 2) + 1',
+; since N < 126 no-overflow fact is NOT provable at compile time and
+; runtime overflow check is required.
+define i8 @test_overflow_check_runtime(i8 %limit, ptr %p) {
+; CHECK-LABEL: define i8 @test_overflow_check_runtime
+; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG11]]
+; CHECK-NEXT:    [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
+; CHECK-NEXT:    br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.preheader:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
+; CHECK-NEXT:    [[CHECK:%.*]] = icmp sge i8 [[SUB]], -2
+; CHECK-NEXT:    br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]]
+; CHECK:       inbounds:
+; CHECK-NEXT:    [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK:       out_of_bounds:
+; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    ret i8 [[IDX_LCSSA]]
+;
+entry:
+  %n = load i8, ptr %p, !range !1
+  %precheck = icmp sgt i8 %limit, 0
+  br i1 %precheck, label %loop, label %exit
+
+loop:
+  %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
+  %sub = sub i8 %n, %idx
+  %check = icmp sge i8 %sub, -2
+  br i1 %check, label %inbounds, label %out_of_bounds
+
+inbounds:
+  %idx.next = add nuw i8 %idx, 1
+  %cmp = icmp slt i8 %idx.next, %limit
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  %res = phi i8 [ 0, %entry ], [ %idx, %inbounds ]
+  ret i8 %res
+
+out_of_bounds:
+  ret i8 %idx;
+}
+
 !0 = !{i8 0, i8 127}
+!1 = !{i8 0, i8 126}