From 036dda25a5b125c88e9d2fd8d63b8120842eeb51 Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Mon, 22 May 2017 06:46:04 +0000 Subject: [SCEV] Clarify behavior around max backedge taken count This is a re-application of a r303497 that was reverted in r303498. I thought it had broken a bot when it had not (the breakage did not go away with the revert). This change makes the split between the "exact" backedge taken count and the "maximum" backedge taken count a bit more obvious. Both of these are upper bounds on the number of times the loop header executes (since SCEV does not account for most kinds of abnormal control flow), but the latter is guaranteed to be a constant. There were a few places where the max backedge taken count *was* a non-constant; I've changed those to compute constants instead. At this point, I'm not sure if the constant max backedge count can be computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without losing precision. If it can, we can simplify even further by making `getMaxBackedgeTakenCount` a thin wrapper around `getBackedgeTakenCount` and `getUnsignedRange`. llvm-svn: 303531 --- llvm/lib/Analysis/ScalarEvolution.cpp | 47 +++++++++++++++++++++++++++-------- 1 file changed, 37 insertions(+), 10 deletions(-) (limited to 'llvm/lib') diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 3f3e8cebb24..78ded8141c0 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5947,6 +5947,8 @@ ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const { if (any_of(ExitNotTaken, PredicateNotAlwaysTrue) || !getMax()) return SE->getCouldNotCompute(); + assert((isa(getMax()) || isa(getMax())) && + "No point in having a non-constant max backedge taken count!"); return getMax(); } @@ -5972,7 +5974,11 @@ bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S, } ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E) - : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) {} + : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) { + assert((isa(MaxNotTaken) || + isa(MaxNotTaken)) && + "No point in having a non-constant max backedge taken count!"); +} ScalarEvolution::ExitLimit::ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, @@ -5981,6 +5987,9 @@ ScalarEvolution::ExitLimit::ExitLimit( assert((isa(ExactNotTaken) || !isa(MaxNotTaken)) && "Exact is not allowed to be less precise than Max"); + assert((isa(MaxNotTaken) || + isa(MaxNotTaken)) && + "No point in having a non-constant max backedge taken count!"); for (auto *PredSet : PredSetList) for (auto *P : *PredSet) addPredicate(P); @@ -5989,11 +5998,19 @@ ScalarEvolution::ExitLimit::ExitLimit( ScalarEvolution::ExitLimit::ExitLimit( const SCEV *E, const SCEV *M, bool MaxOrZero, const SmallPtrSetImpl &PredSet) - : ExitLimit(E, M, MaxOrZero, {&PredSet}) {} + : ExitLimit(E, M, MaxOrZero, {&PredSet}) { + assert((isa(MaxNotTaken) || + isa(MaxNotTaken)) && + "No point in having a non-constant max backedge taken count!"); +} ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero) - : ExitLimit(E, M, MaxOrZero, None) {} + : ExitLimit(E, M, MaxOrZero, None) { + assert((isa(MaxNotTaken) || + isa(MaxNotTaken)) && + "No point in having a non-constant max backedge taken count!"); +} /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each /// computable exit into a persistent ExitNotTakenInfo array. @@ -6018,6 +6035,8 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate)); }); + assert((isa(MaxCount) || isa(MaxCount)) && + "No point in having a non-constant max backedge taken count!"); } /// Invalidate this result and free the ExitNotTakenInfo array. @@ -6279,7 +6298,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( // to not. if (isa(MaxBECount) && !isa(BECount)) - MaxBECount = BECount; + MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax()); return ExitLimit(BECount, MaxBECount, false, {&EL0.Predicates, &EL1.Predicates}); @@ -7583,13 +7602,20 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, loopHasNoAbnormalExits(AddRec->getLoop())) { const SCEV *Exact = getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step); - return ExitLimit(Exact, Exact, false, Predicates); + const SCEV *Max = + Exact == getCouldNotCompute() + ? Exact + : getConstant(getUnsignedRange(Exact).getUnsignedMax()); + return ExitLimit(Exact, Max, false, Predicates); } // Solve the general equation. - const SCEV *E = SolveLinEquationWithOverflow( - StepC->getAPInt(), getNegativeSCEV(Start), *this); - return ExitLimit(E, E, false, Predicates); + const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(), + getNegativeSCEV(Start), *this); + const SCEV *M = E == getCouldNotCompute() + ? E + : getConstant(getUnsignedRange(E).getUnsignedMax()); + return ExitLimit(E, M, false, Predicates); } ScalarEvolution::ExitLimit @@ -9218,8 +9244,9 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, getConstant(StrideForMaxBECount), false); } - if (isa(MaxBECount)) - MaxBECount = BECount; + if (isa(MaxBECount) && + !isa(BECount)) + MaxBECount = getConstant(getUnsignedRange(BECount).getUnsignedMax()); return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates); } -- cgit v1.2.3