From 8c0c4322ddf0a4e77689a0d19c1604daa60cd442 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Fri, 2 Oct 2015 18:50:30 +0000 Subject: [PATCH] [SCEV] Try to prove predicates by splitting them Summary: This change teaches SCEV that to prove `A u< B` it is sufficient to prove each of these facts individually: - B >= 0 - A s< B - A >= 0 In practice, SCEV sometimes finds it easier to prove these facts individually than to prove `A u< B` as one atomic step. Reviewers: reames, atrick, nlewycky, hfinkel Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13042 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@249168 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ScalarEvolution.h | 9 +++ lib/Analysis/ScalarEvolution.cpp | 36 +++++++++- .../IndVarSimplify/eliminate-comparison.ll | 83 ++++++++++++++++++++++ 3 files changed, 125 insertions(+), 3 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 62d66c246d7..e853d2ad63c 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -253,6 +253,10 @@ namespace llvm { /// conditions dominating the backedge of a loop. bool WalkingBEDominatingConds; + /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a + /// predicate by splitting it into a set of independent predicates. + bool ProvingSplitPredicate; + /// Information about the number of loop iterations for which a loop exit's /// branch condition evaluates to the not-taken path. This is a temporary /// pair of exact and max expressions that are eventually summarized in @@ -559,6 +563,11 @@ namespace llvm { bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to + /// prove them individually. + bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS, + const SCEV *RHS); + /// Drop memoized information computed for S. void forgetMemoizedResults(const SCEV *S); diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index c86c011aaf1..0d56183c258 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -6764,6 +6764,9 @@ bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred, if (LeftGuarded && RightGuarded) return true; + if (isKnownPredicateViaSplitting(Pred, LHS, RHS)) + return true; + // Otherwise see what can be done with known constant ranges. return isKnownPredicateWithRanges(Pred, LHS, RHS); } @@ -6969,6 +6972,31 @@ ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred, return false; } +bool ScalarEvolution::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, + const SCEV *LHS, + const SCEV *RHS) { + if (ProvingSplitPredicate) + return false; + + // Allowing arbitrary number of activations of isKnownPredicateViaSplitting on + // the stack can result in exponential time complexity. + SaveAndRestore Restore(ProvingSplitPredicate, true); + + // If L >= 0 then I `ult` L <=> I >= 0 && I `slt` L + // + // To prove L >= 0 we use isKnownNonNegative whereas to prove I >= 0 we use + // isKnownPredicate. isKnownPredicate is more powerful, but also more + // expensive; and using isKnownNonNegative(RHS) is sufficient for most of the + // interesting cases seen in practice. We can consider "upgrading" L >= 0 to + // use isKnownPredicate later if needed. + if (Pred == ICmpInst::ICMP_ULT && isKnownNonNegative(RHS) && + isKnownPredicate(CmpInst::ICMP_SGE, LHS, getZero(LHS->getType())) && + isKnownPredicate(CmpInst::ICMP_SLT, LHS, RHS)) + return true; + + return false; +} + /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is /// protected by a conditional between LHS and RHS. This is used to /// to eliminate casts. @@ -8529,14 +8557,15 @@ ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI, LoopInfo &LI) : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), CouldNotCompute(new SCEVCouldNotCompute()), - WalkingBEDominatingConds(false), ValuesAtScopes(64), LoopDispositions(64), - BlockDispositions(64), FirstUnknown(nullptr) {} + WalkingBEDominatingConds(false), ProvingSplitPredicate(false), + ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64), + FirstUnknown(nullptr) {} ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg) : F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)), ValueExprMap(std::move(Arg.ValueExprMap)), - WalkingBEDominatingConds(false), + WalkingBEDominatingConds(false), ProvingSplitPredicate(false), BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)), ConstantEvolutionLoopExitValue( std::move(Arg.ConstantEvolutionLoopExitValue)), @@ -8573,6 +8602,7 @@ ScalarEvolution::~ScalarEvolution() { assert(PendingLoopPredicates.empty() && "isImpliedCond garbage"); assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!"); + assert(!ProvingSplitPredicate && "ProvingSplitPredicate garbage!"); } bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) { diff --git a/test/Transforms/IndVarSimplify/eliminate-comparison.ll b/test/Transforms/IndVarSimplify/eliminate-comparison.ll index 957ebb7cfbf..177e0f74da6 100644 --- a/test/Transforms/IndVarSimplify/eliminate-comparison.ll +++ b/test/Transforms/IndVarSimplify/eliminate-comparison.ll @@ -394,4 +394,87 @@ bb3: ret i1 true } +define void @func_19(i32* %length.ptr) { +; CHECK-LABEL: @func_19( + entry: + %length = load i32, i32* %length.ptr, !range !0 + %length.is.nonzero = icmp ne i32 %length, 0 + br i1 %length.is.nonzero, label %loop, label %leave + + loop: +; CHECK: loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] + %iv.inc = add i32 %iv, 1 + %range.check = icmp ult i32 %iv, %length + br i1 %range.check, label %be, label %leave +; CHECK: br i1 true, label %be, label %leave.loopexit +; CHECK: be: + + be: + call void @side_effect() + %be.cond = icmp slt i32 %iv.inc, %length + br i1 %be.cond, label %loop, label %leave + + leave: + ret void +} + +define void @func_20(i32* %length.ptr) { +; Like @func_19, but %length is no longer provably positive, so +; %range.check cannot be proved to be always true. + +; CHECK-LABEL: @func_20( + entry: + %length = load i32, i32* %length.ptr + %length.is.nonzero = icmp ne i32 %length, 0 + br i1 %length.is.nonzero, label %loop, label %leave + + loop: +; CHECK: loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] + %iv.inc = add i32 %iv, 1 + %range.check = icmp ult i32 %iv, %length + br i1 %range.check, label %be, label %leave +; CHECK: br i1 %range.check, label %be, label %leave.loopexit +; CHECK: be: + + be: + call void @side_effect() + %be.cond = icmp slt i32 %iv.inc, %length + br i1 %be.cond, label %loop, label %leave + + leave: + ret void +} + +define void @func_21(i32* %length.ptr, i32 %init) { +; Like @func_19, but it is no longer possible to prove %iv's start +; value is positive without doing some control flow analysis. + +; CHECK-LABEL: @func_21( + entry: + %length = load i32, i32* %length.ptr, !range !0 + %length.is.nonzero = icmp ne i32 %length, 0 + %init.is.positive = icmp sgt i32 %init, 0 + %entry.cond = and i1 %length.is.nonzero, %init.is.positive + br i1 %length.is.nonzero, label %loop, label %leave + + loop: +; CHECK: loop: + %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ] + %iv.inc = add i32 %iv, 1 + %range.check = icmp ult i32 %iv, %length + br i1 %range.check, label %be, label %leave +; CHECK: br i1 true, label %be, label %leave.loopexit +; CHECK: be: + + be: + call void @side_effect() + %be.cond = icmp slt i32 %iv.inc, %length + br i1 %be.cond, label %loop, label %leave + + leave: + ret void +} + !0 = !{i32 0, i32 2147483647} -- 2.11.0