From c5e1132ac2ba9b2efc552d4be050c800ddcbaf72 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Sat, 21 Feb 2015 22:07:32 +0000 Subject: [PATCH] IRCE: use SCEVs instead of llvm::Value's for intermediate calculations. Semantically non-functional change. This gets rid of some of the SCEV -> Value -> SCEV round tripping and the Construct(SMin|SMax)Of and MaybeSimplify helper routines. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@230150 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Scalar/InductiveRangeCheckElimination.cpp | 76 ++++++++----------- .../IRCE/multiple-access-no-preloop.ll | 14 ++-- .../IRCE/single-access-no-preloop.ll | 8 +- .../IRCE/single-access-with-preloop.ll | 16 ++-- 4 files changed, 54 insertions(+), 60 deletions(-) diff --git a/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp index 809e9ee99c1..86a00b1590e 100644 --- a/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ b/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -143,17 +143,17 @@ public: /// R.getEnd() sle R.getBegin(), then R denotes the empty range. class Range { - Value *Begin; - Value *End; + const SCEV *Begin; + const SCEV *End; public: - Range(Value *Begin, Value *End) : Begin(Begin), End(End) { + Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) { assert(Begin->getType() == End->getType() && "ill-typed range!"); } Type *getType() const { return Begin->getType(); } - Value *getBegin() const { return Begin; } - Value *getEnd() const { return End; } + const SCEV *getBegin() const { return Begin; } + const SCEV *getEnd() const { return End; } }; typedef SpecificBumpPtrAllocator AllocatorTy; @@ -394,21 +394,6 @@ InductiveRangeCheck::create(InductiveRangeCheck::AllocatorTy &A, BranchInst *BI, return IRC; } -static Value *MaybeSimplify(Value *V) { - if (Instruction *I = dyn_cast(V)) - if (Value *Simplified = SimplifyInstruction(I)) - return Simplified; - return V; -} - -static Value *ConstructSMinOf(Value *X, Value *Y, IRBuilder<> &B) { - return MaybeSimplify(B.CreateSelect(B.CreateICmpSLT(X, Y), X, Y)); -} - -static Value *ConstructSMaxOf(Value *X, Value *Y, IRBuilder<> &B) { - return MaybeSimplify(B.CreateSelect(B.CreateICmpSGT(X, Y), X, Y)); -} - namespace { /// This class is used to constrain loops to run within a given iteration space. @@ -738,35 +723,36 @@ LoopConstrainer::calculateSubRanges(Value *&HeaderCountOut) const { SCEVExpander Expander(SE, "irce"); Instruction *InsertPt = OriginalPreheader->getTerminator(); - Value *LatchCountV = - MaybeSimplify(Expander.expandCodeFor(LatchTakenCount, Ty, InsertPt)); - - IRBuilder<> B(InsertPt); - LoopConstrainer::SubRanges Result; // I think we can be more aggressive here and make this nuw / nsw if the // addition that feeds into the icmp for the latch's terminating branch is nuw // / nsw. In any case, a wrapping 2's complement addition is safe. ConstantInt *One = ConstantInt::get(Ty, 1); - HeaderCountOut = MaybeSimplify(B.CreateAdd(LatchCountV, One, "header.count")); + const SCEV *HeaderCountSCEV = SE.getAddExpr(LatchTakenCount, SE.getSCEV(One)); + HeaderCountOut = Expander.expandCodeFor(HeaderCountSCEV, Ty, InsertPt); - const SCEV *RangeBegin = SE.getSCEV(Range.getBegin()); - const SCEV *RangeEnd = SE.getSCEV(Range.getEnd()); - const SCEV *HeaderCountSCEV = SE.getSCEV(HeaderCountOut); const SCEV *Zero = SE.getConstant(Ty, 0); // In some cases we can prove that we don't need a pre or post loop bool ProvablyNoPreloop = - SE.isKnownPredicate(ICmpInst::ICMP_SLE, RangeBegin, Zero); - if (!ProvablyNoPreloop) - Result.ExitPreLoopAt = ConstructSMinOf(HeaderCountOut, Range.getBegin(), B); + SE.isKnownPredicate(ICmpInst::ICMP_SLE, Range.getBegin(), Zero); + if (!ProvablyNoPreloop) { + const SCEV *ExitPreLoopAtSCEV = + SE.getSMinExpr(HeaderCountSCEV, Range.getBegin()); + Result.ExitPreLoopAt = + Expander.expandCodeFor(ExitPreLoopAtSCEV, Ty, InsertPt); + } bool ProvablyNoPostLoop = - SE.isKnownPredicate(ICmpInst::ICMP_SLE, HeaderCountSCEV, RangeEnd); - if (!ProvablyNoPostLoop) - Result.ExitMainLoopAt = ConstructSMinOf(HeaderCountOut, Range.getEnd(), B); + SE.isKnownPredicate(ICmpInst::ICMP_SLE, HeaderCountSCEV, Range.getEnd()); + if (!ProvablyNoPostLoop) { + const SCEV *ExitMainLoopAtSCEV = + SE.getSMinExpr(HeaderCountSCEV, Range.getEnd()); + Result.ExitMainLoopAt = + Expander.expandCodeFor(ExitMainLoopAtSCEV, Ty, InsertPt); + } return Result; } @@ -1131,18 +1117,15 @@ InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE, return None; } - Value *OffsetV = SCEVExpander(SE, "safe.itr.space").expandCodeFor( - getOffset(), getOffset()->getType(), B.GetInsertPoint()); - OffsetV = MaybeSimplify(OffsetV); - - Value *Begin = MaybeSimplify(B.CreateNeg(OffsetV)); - Value *End = MaybeSimplify(B.CreateSub(getLength(), OffsetV)); + const SCEV *Begin = SE.getNegativeSCEV(getOffset()); + const SCEV *End = SE.getMinusSCEV(SE.getSCEV(getLength()), getOffset()); return InductiveRangeCheck::Range(Begin, End); } static Optional -IntersectRange(const Optional &R1, +IntersectRange(ScalarEvolution &SE, + const Optional &R1, const InductiveRangeCheck::Range &R2, IRBuilder<> &B) { if (!R1.hasValue()) return R2; @@ -1153,9 +1136,10 @@ IntersectRange(const Optional &R1, if (R1Value.getType() != R2.getType()) return None; - Value *NewMin = ConstructSMaxOf(R1Value.getBegin(), R2.getBegin(), B); - Value *NewMax = ConstructSMinOf(R1Value.getEnd(), R2.getEnd(), B); - return InductiveRangeCheck::Range(NewMin, NewMax); + const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin()); + const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd()); + + return InductiveRangeCheck::Range(NewBegin, NewEnd); } bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) { @@ -1202,7 +1186,7 @@ bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) { auto Result = IRC->computeSafeIterationSpace(SE, B); if (Result.hasValue()) { auto MaybeSafeIterRange = - IntersectRange(SafeIterRange, Result.getValue(), B); + IntersectRange(SE, SafeIterRange, Result.getValue(), B); if (MaybeSafeIterRange.hasValue()) { RangeChecksToEliminate.push_back(IRC); SafeIterRange = MaybeSafeIterRange.getValue(); diff --git a/test/Transforms/IRCE/multiple-access-no-preloop.ll b/test/Transforms/IRCE/multiple-access-no-preloop.ll index b8d2f140bab..1dfb70fe5e7 100644 --- a/test/Transforms/IRCE/multiple-access-no-preloop.ll +++ b/test/Transforms/IRCE/multiple-access-no-preloop.ll @@ -37,10 +37,14 @@ define void @multiple_access_no_preloop( ; CHECK-LABEL: multiple_access_no_preloop ; CHECK-LABEL: loop.preheader: -; CHECK: [[smaller_len_cmp:[^ ]+]] = icmp slt i32 %len.a, %len.b -; CHECK: [[smaller_len:[^ ]+]] = select i1 [[smaller_len_cmp]], i32 %len.a, i32 %len.b -; CHECK: [[upper_bound_cmp:[^ ]+]] = icmp slt i32 %n, %3 -; CHECK: [[upper_bound:[^ ]+]] = select i1 %5, i32 %n, i32 %3 +; CHECK: [[not_len_b:[^ ]+]] = sub i32 -1, %len.b +; CHECK: [[not_len_a:[^ ]+]] = sub i32 -1, %len.a +; CHECK: [[smax_not_len_cond:[^ ]+]] = icmp sgt i32 [[not_len_b]], [[not_len_a]] +; CHECK: [[smax_not_len:[^ ]+]] = select i1 [[smax_not_len_cond]], i32 [[not_len_b]], i32 [[not_len_a]] +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_upper_limit_cond:[^ ]+]] = icmp sgt i32 [[smax_not_len]], [[not_n]] +; CHECK: [[not_upper_limit:[^ ]+]] = select i1 [[not_upper_limit_cond]], i32 [[smax_not_len]], i32 [[not_n]] +; CHECK: [[upper_limit:[^ ]+]] = sub i32 -1, [[not_upper_limit]] ; CHECK-LABEL: loop: ; CHECK: br i1 true, label %in.bounds.a, label %out.of.bounds @@ -49,7 +53,7 @@ define void @multiple_access_no_preloop( ; CHECK: br i1 true, label %in.bounds.b, label %out.of.bounds ; CHECK-LABEL: in.bounds.b: -; CHECK: [[main_loop_cond:[^ ]+]] = icmp slt i32 %idx.next, [[upper_bound]] +; CHECK: [[main_loop_cond:[^ ]+]] = icmp slt i32 %idx.next, [[upper_limit]] ; CHECK: br i1 [[main_loop_cond]], label %loop, label %main.exit.selector ; CHECK-LABEL: in.bounds.b.postloop: diff --git a/test/Transforms/IRCE/single-access-no-preloop.ll b/test/Transforms/IRCE/single-access-no-preloop.ll index 34d8cd64b1c..0252e437ee8 100644 --- a/test/Transforms/IRCE/single-access-no-preloop.ll +++ b/test/Transforms/IRCE/single-access-no-preloop.ll @@ -83,9 +83,11 @@ define void @single_access_no_preloop_with_offset(i32 *%arr, i32 *%a_len_ptr, i3 ; CHECK-LABEL: single_access_no_preloop_with_offset ; CHECK-LABEL: loop.preheader: -; CHECK: [[safe_range_end:[^ ]+]] = sub i32 %len, 4 -; CHECK: [[exit_main_loop_at_cmp:[^ ]+]] = icmp slt i32 %n, [[safe_range_end]] -; CHECK: [[exit_main_loop_at:[^ ]+]] = select i1 [[exit_main_loop_at_cmp]], i32 %n, i32 [[safe_range_end]] +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_safe_range_end:[^ ]+]] = sub i32 3, %len +; CHECK: [[not_exit_main_loop_at_cmp:[^ ]+]] = icmp sgt i32 [[not_n]], [[not_safe_range_end]] +; CHECK: [[not_exit_main_loop_at:[^ ]+]] = select i1 [[not_exit_main_loop_at_cmp]], i32 [[not_n]], i32 [[not_safe_range_end]] +; CHECK: [[exit_main_loop_at:[^ ]+]] = sub i32 -1, [[not_exit_main_loop_at]] ; CHECK: [[enter_main_loop:[^ ]+]] = icmp slt i32 0, [[exit_main_loop_at]] ; CHECK: br i1 [[enter_main_loop]], label %loop, label %main.pseudo.exit diff --git a/test/Transforms/IRCE/single-access-with-preloop.ll b/test/Transforms/IRCE/single-access-with-preloop.ll index dacf697e98a..c220efa50a6 100644 --- a/test/Transforms/IRCE/single-access-with-preloop.ll +++ b/test/Transforms/IRCE/single-access-with-preloop.ll @@ -29,12 +29,16 @@ define void @single_access_with_preloop(i32 *%arr, i32 *%a_len_ptr, i32 %n, i32 } ; CHECK-LABEL: loop.preheader: -; CHECK: [[safe_start:[^ ]+]] = sub i32 0, %offset -; CHECK: [[safe_end:[^ ]+]] = sub i32 %len, %offset -; CHECK: [[exit_preloop_at_cond:[^ ]+]] = icmp slt i32 %n, [[safe_start]] -; CHECK: [[exit_preloop_at:[^ ]+]] = select i1 [[exit_preloop_at_cond]], i32 %n, i32 [[safe_start]] -; CHECK: [[exit_mainloop_at_cond:[^ ]+]] = icmp slt i32 %n, [[safe_end]] -; CHECK: [[exit_mainloop_at:[^ ]+]] = select i1 [[exit_mainloop_at_cond]], i32 %n, i32 [[safe_end]] +; CHECK: [[not_safe_start:[^ ]+]] = add i32 %offset, -1 +; CHECK: [[not_n:[^ ]+]] = sub i32 -1, %n +; CHECK: [[not_exit_preloop_at_cond:[^ ]+]] = icmp sgt i32 [[not_safe_start]], [[not_n]] +; CHECK: [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cond]], i32 [[not_safe_start]], i32 [[not_n]] +; CHECK: [[exit_preloop_at:[^ ]+]] = sub i32 -1, [[not_exit_preloop_at]] + +; CHECK: [[not_safe_end:[^ ]+]] = sub i32 [[not_safe_start]], %len +; CHECK: [[not_exit_mainloop_at_cond:[^ ]+]] = icmp sgt i32 [[not_safe_end]], [[not_n]] +; CHECK: [[not_exit_mainloop_at:[^ ]+]] = select i1 [[not_exit_mainloop_at_cond]], i32 [[not_safe_end]], i32 [[not_n]] +; CHECK: [[exit_mainloop_at:[^ ]+]] = sub i32 -1, [[not_exit_mainloop_at]] ; CHECK-LABEL: in.bounds: ; CHECK: [[continue_mainloop_cond:[^ ]+]] = icmp slt i32 %idx.next, [[exit_mainloop_at]] -- 2.34.1