From 168a8230000ecfefaba6511adea04f1c3eacfc8a Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Wed, 11 Oct 2017 06:53:07 +0000 Subject: [PATCH] [IRCE] Do not process empty safe ranges IRCE should not apply when the safe iteration range is proved to be empty. In this case we do unneeded job creating pre/post loops and then never go to the main loop. This patch makes IRCE not apply to empty safe ranges, adds test for this situation and also modifies one of existing tests where it used to happen slightly. Reviewed By: anna Differential Revision: https://reviews.llvm.org/D38577 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@315437 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Scalar/InductiveRangeCheckElimination.cpp | 16 ++++- test/Transforms/IRCE/correct-loop-info.ll | 12 ++-- .../IRCE/single-access-no-preloop.ll | 66 +++++++++++++++++++ 3 files changed, 85 insertions(+), 9 deletions(-) diff --git a/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp index cc0f2c5bb48..9cdc1d18963 100644 --- a/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ b/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -176,6 +176,7 @@ public: Type *getType() const { return Begin->getType(); } const SCEV *getBegin() const { return Begin; } const SCEV *getEnd() const { return End; } + bool isEmpty() const { return Begin == End; } }; /// This is the value the condition of the branch needs to evaluate to for the @@ -1654,8 +1655,11 @@ static Optional IntersectRange(ScalarEvolution &SE, const Optional &R1, const InductiveRangeCheck::Range &R2) { - if (!R1.hasValue()) - return R2; + if (!R1.hasValue()) { + if (!R2.isEmpty()) + return R2; + return None; + } auto &R1Value = R1.getValue(); // TODO: we could widen the smaller range and have this work; but for now we @@ -1666,7 +1670,11 @@ IntersectRange(ScalarEvolution &SE, const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin()); const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd()); - return InductiveRangeCheck::Range(NewBegin, NewEnd); + // If the resulting range is empty, just return None. + auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd); + if (Ret.isEmpty()) + return None; + return Ret; } bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) { @@ -1735,6 +1743,8 @@ bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) { auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, Result.getValue()); if (MaybeSafeIterRange.hasValue()) { + assert(!MaybeSafeIterRange.getValue().isEmpty() && + "We should never return empty ranges!"); RangeChecksToEliminate.push_back(IRC); SafeIterRange = MaybeSafeIterRange.getValue(); } diff --git a/test/Transforms/IRCE/correct-loop-info.ll b/test/Transforms/IRCE/correct-loop-info.ll index 3c26b47f154..328557045db 100644 --- a/test/Transforms/IRCE/correct-loop-info.ll +++ b/test/Transforms/IRCE/correct-loop-info.ll @@ -21,7 +21,7 @@ define void @baz() personality i32* ()* @ham { ; CHECK: innerheader.preloop.preheader: ; CHECK-NEXT: br label [[INNERHEADER_PRELOOP:%.*]] ; CHECK: mainloop: -; CHECK-NEXT: [[TMP0:%.*]] = icmp slt i32 [[INDVAR_END:%.*]], -1 +; CHECK-NEXT: [[TMP0:%.*]] = icmp slt i32 [[INDVAR_END:%.*]], 0 ; CHECK-NEXT: br i1 [[TMP0]], label [[INNERHEADER_PREHEADER:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] ; CHECK: innerheader.preheader: ; CHECK-NEXT: br label [[INNERHEADER:%.*]] @@ -31,11 +31,11 @@ define void @baz() personality i32* ()* @ham { ; CHECK-NEXT: to label [[BB5:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit.split-lp ; CHECK: bb5: ; CHECK-NEXT: [[TMP6]] = add i32 [[TMP4]], 1 -; CHECK-NEXT: [[TMP7:%.*]] = icmp ult i32 [[TMP6]], 0 +; CHECK-NEXT: [[TMP7:%.*]] = icmp ult i32 [[TMP6]], 1 ; CHECK-NEXT: br i1 true, label [[BB8]], label [[EXIT3_LOOPEXIT5:%.*]] ; CHECK: bb8: ; CHECK-NEXT: [[TMP9:%.*]] = icmp slt i32 [[TMP6]], 84 -; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[TMP6]], -1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[TMP6]], 0 ; CHECK-NEXT: br i1 [[TMP1]], label [[INNERHEADER]], label [[MAIN_EXIT_SELECTOR:%.*]] ; CHECK: main.exit.selector: ; CHECK-NEXT: [[TMP6_LCSSA:%.*]] = phi i32 [ [[TMP6]], [[BB8]] ] @@ -90,7 +90,7 @@ define void @baz() personality i32* ()* @ham { ; CHECK-NEXT: to label [[BB5_PRELOOP:%.*]] unwind label [[OUTER_EXITING_LOOPEXIT:%.*]] ; CHECK: bb5.preloop: ; CHECK-NEXT: [[TMP6_PRELOOP]] = add i32 [[TMP4_PRELOOP]], 1 -; CHECK-NEXT: [[TMP7_PRELOOP:%.*]] = icmp ult i32 [[TMP6_PRELOOP]], 0 +; CHECK-NEXT: [[TMP7_PRELOOP:%.*]] = icmp ult i32 [[TMP6_PRELOOP]], 1 ; CHECK-NEXT: br i1 [[TMP7_PRELOOP]], label [[BB8_PRELOOP]], label [[EXIT3_LOOPEXIT:%.*]] ; CHECK: bb8.preloop: ; CHECK-NEXT: [[TMP9_PRELOOP:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 84 @@ -112,7 +112,7 @@ define void @baz() personality i32* ()* @ham { ; CHECK-NEXT: to label [[BB5_POSTLOOP:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit ; CHECK: bb5.postloop: ; CHECK-NEXT: [[TMP6_POSTLOOP]] = add i32 [[TMP4_POSTLOOP]], 1 -; CHECK-NEXT: [[TMP7_POSTLOOP:%.*]] = icmp ult i32 [[TMP6_POSTLOOP]], 0 +; CHECK-NEXT: [[TMP7_POSTLOOP:%.*]] = icmp ult i32 [[TMP6_POSTLOOP]], 1 ; CHECK-NEXT: br i1 [[TMP7_POSTLOOP]], label [[BB8_POSTLOOP]], label [[EXIT3_LOOPEXIT4:%.*]] ; CHECK: bb8.postloop: ; CHECK-NEXT: [[TMP9_POSTLOOP:%.*]] = icmp slt i32 [[TMP6_POSTLOOP]], 84 @@ -135,7 +135,7 @@ innerheader: ; preds = %bb8, %bb2 bb5: ; preds = %innerheader %tmp6 = add i32 %tmp4, 1 - %tmp7 = icmp ult i32 %tmp6, 0 + %tmp7 = icmp ult i32 %tmp6, 1 br i1 %tmp7, label %bb8, label %exit3 bb8: ; preds = %bb5 diff --git a/test/Transforms/IRCE/single-access-no-preloop.ll b/test/Transforms/IRCE/single-access-no-preloop.ll index b61a1c3b0c8..53f430d0ba3 100644 --- a/test/Transforms/IRCE/single-access-no-preloop.ll +++ b/test/Transforms/IRCE/single-access-no-preloop.ll @@ -113,5 +113,71 @@ define void @single_access_no_preloop_with_offset(i32 *%arr, i32 *%a_len_ptr, i3 ; CHECK: %next.postloop = icmp slt i32 %idx.next.postloop, %n ; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit +; Make sure that we do not do IRCE if we know that the safe iteration range of +; the main loop is empty. + +define void @single_access_empty_range(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, 0 + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32, i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: @single_access_empty_range( +; CHECK-NOT: br i1 false +; CHECK-NOT: preloop +; CHECK-NOT: postloop + +define void @single_access_empty_range_2(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds2 ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, 60 + br i1 %abc, label %in.bounds1, label %out.of.bounds, !prof !1 + + in.bounds1: + %def = icmp slt i32 %idx, 0 + br i1 %def, label %in.bounds2, label %out.of.bounds, !prof !1 + +in.bounds2: + %addr = getelementptr i32, i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: @single_access_empty_range_2( +; CHECK-NOT: br i1 false +; CHECK-NOT: preloop + !0 = !{i32 0, i32 2147483647} !1 = !{!"branch_weights", i32 64, i32 4} -- 2.40.0