diff options
3 files changed, 149 insertions, 15 deletions
diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp index 68abd8e..330a2c2 100644 --- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -312,13 +312,8 @@ InductiveRangeCheck::RangeCheckKind InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI, ScalarEvolution &SE, Value *&Index, Value *&Length, bool &IsSigned) { - auto IsNonNegativeAndNotLoopVarying = [&SE, L](Value *V) { - const SCEV *S = SE.getSCEV(V); - if (isa<SCEVCouldNotCompute>(S)) - return false; - - return SE.getLoopDisposition(S, L) == ScalarEvolution::LoopInvariant && - SE.isKnownNonNegative(S); + auto IsLoopInvariant = [&SE, L](Value *V) { + return SE.isLoopInvariant(SE.getSCEV(V), L); }; ICmpInst::Predicate Pred = ICI->getPredicate(); @@ -350,7 +345,7 @@ InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI, return RANGE_CHECK_LOWER; } - if (IsNonNegativeAndNotLoopVarying(LHS)) { + if (IsLoopInvariant(LHS)) { Index = RHS; Length = LHS; return RANGE_CHECK_UPPER; @@ -362,7 +357,7 @@ InductiveRangeCheck::parseRangeCheckICmp(Loop *L, ICmpInst *ICI, LLVM_FALLTHROUGH; case ICmpInst::ICMP_UGT: IsSigned = false; - if (IsNonNegativeAndNotLoopVarying(LHS)) { + if (IsLoopInvariant(LHS)) { Index = RHS; Length = LHS; return RANGE_CHECK_BOTH; diff --git a/llvm/test/Transforms/IRCE/non_known_positive_end.ll b/llvm/test/Transforms/IRCE/non_known_positive_end.ll new file mode 100644 index 0000000..135e446 --- /dev/null +++ b/llvm/test/Transforms/IRCE/non_known_positive_end.ll @@ -0,0 +1,139 @@ +; RUN: opt -verify-loop-info -irce -irce-print-range-checks -irce-print-changed-loops %s -S 2>&1 | FileCheck %s +; RUN: opt -verify-loop-info -passes='require<branch-prob>,loop(irce)' -irce-print-range-checks -irce-print-changed-loops %s -S 2>&1 | FileCheck %s + +; Make sure that we can pick up both range checks. +define void @test_01(i32 *%arr, i32* %a_len_ptr, i32* %size_ptr) { + +; CHECK-LABEL: @test_01( + +entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %size = load i32, i32* %size_ptr + %first_iter_check = icmp sle i32 %size, 0 + br i1 %first_iter_check, label %exit, label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %rc1 = icmp slt i32 %iv, %len + %rc2 = icmp slt i32 %iv, %size + ; CHECK: %rc = and i1 true, true + %rc = and i1 %rc1, %rc2 + br i1 %rc, label %backedge, label %out_of_bounds + + +backedge: + %iv.next = add i32 %iv, 1 + %arr_el_ptr = getelementptr i32, i32* %arr, i32 %iv + %el = load i32, i32* %arr_el_ptr + %loopcond = icmp ne i32 %iv, %size + br i1 %loopcond, label %loop, label %exit + +exit: + ret void + +out_of_bounds: + ret void +} + +; Same as test_01, unsigned predicates. +define void @test_02(i32 *%arr, i32* %a_len_ptr, i32* %size_ptr) { + +; CHECK-LABEL: @test_02( + +entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %size = load i32, i32* %size_ptr + %first_iter_check = icmp sle i32 %size, 0 + br i1 %first_iter_check, label %exit, label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %rc1 = icmp ult i32 %iv, %len + %rc2 = icmp ult i32 %iv, %size + ; CHECK: %rc = and i1 true, true + %rc = and i1 %rc1, %rc2 + br i1 %rc, label %backedge, label %out_of_bounds + + +backedge: + %iv.next = add i32 %iv, 1 + %arr_el_ptr = getelementptr i32, i32* %arr, i32 %iv + %el = load i32, i32* %arr_el_ptr + %loopcond = icmp ne i32 %iv, %size + br i1 %loopcond, label %loop, label %exit + +exit: + ret void + +out_of_bounds: + ret void +} + +define void @test_03(i32 *%arr, i32* %a_len_ptr, i32* %size_ptr) { + +; CHECK-LABEL: @test_03( + +entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %size = load i32, i32* %size_ptr + %first_iter_check = icmp eq i32 %size, 0 + br i1 %first_iter_check, label %exit, label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %rc1 = icmp slt i32 %iv, %len + %rc2 = icmp slt i32 %iv, %size + ; CHECK: %rc = and i1 true, true + %rc = and i1 %rc1, %rc2 + br i1 %rc, label %backedge, label %out_of_bounds + + +backedge: + %iv.next = add i32 %iv, 1 + %arr_el_ptr = getelementptr i32, i32* %arr, i32 %iv + %el = load i32, i32* %arr_el_ptr + %loopcond = icmp ne i32 %iv, %len + br i1 %loopcond, label %loop, label %exit + +exit: + ret void + +out_of_bounds: + ret void +} + +define void @test_04(i32 *%arr, i32* %a_len_ptr, i32* %size_ptr) { + +; CHECK-LABEL: @test_04( + +entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %size = load i32, i32* %size_ptr + %first_iter_check = icmp eq i32 %size, 0 + br i1 %first_iter_check, label %exit, label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] + %rc1 = icmp ult i32 %iv, %len + %rc2 = icmp ult i32 %iv, %size + ; CHECK: %rc = and i1 true, true + %rc = and i1 %rc1, %rc2 + br i1 %rc, label %backedge, label %out_of_bounds + + +backedge: + %iv.next = add i32 %iv, 1 + %arr_el_ptr = getelementptr i32, i32* %arr, i32 %iv + %el = load i32, i32* %arr_el_ptr + %loopcond = icmp ne i32 %iv, %len + br i1 %loopcond, label %loop, label %exit + +exit: + ret void + +out_of_bounds: + ret void +} + +!0 = !{i32 0, i32 2147483647} +!1 = !{!"branch_weights", i32 64, i32 4} diff --git a/llvm/test/Transforms/IRCE/range_intersect_miscompile.ll b/llvm/test/Transforms/IRCE/range_intersect_miscompile.ll index cd4a52b..489f34f 100644 --- a/llvm/test/Transforms/IRCE/range_intersect_miscompile.ll +++ b/llvm/test/Transforms/IRCE/range_intersect_miscompile.ll @@ -168,20 +168,20 @@ deopt: ; preds = %range_check_block ret void } -; We do not know whether %n is positive or negative, so we prohibit IRCE in -; order to avoid incorrect intersection of signed and unsigned ranges. -; The condition %tmp2 can be eliminated. +; We can also properly eliminate range check against %n which is not always +; known positive. define void @test_04(i32* %p) { ; CHECK-LABEL: test_04 +; CHECK: entry ; CHECK-NOT: preloop -; CHECK-NOT: postloop ; CHECK: %tmp2 = icmp sgt i32 %iv.prev, -1 ; CHECK-NEXT: br i1 true, label %loop_header.split.us, label %exit ; CHECK: range_check_block: ; CHECK-NEXT: %range_check = icmp slt i32 %iv, %n -; CHECK-NEXT: br i1 %range_check, label %loop_latch, label %deopt +; CHECK-NEXT: br i1 true, label %loop_latch, label %deopt +; CHECK: postloop: entry: %n = load i32, i32* %p @@ -226,7 +226,7 @@ define void @test_05(i32* %p) { ; CHECK-LABEL: test_05 ; CHECK-NOT: preloop ; CHECK: entry: -; CHECK-NEXT: %n = load i32, i32* %p, !range !6 +; CHECK-NEXT: %n = load i32, i32* %p, !range ! ; CHECK-NEXT: [[CMP_1:%[^ ]+]] = icmp ugt i32 %n, 2 ; CHECK-NEXT: %exit.mainloop.at = select i1 [[CMP_1]], i32 %n, i32 2 ; CHECK-NEXT: [[CMP_2:%[^ ]+]] = icmp ult i32 2, %exit.mainloop.at |