Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -744,6 +744,8 @@ Exact, /// A constant which provides an upper bound on the exact trip count. ConstantMaximum, + /// A constant which provides an upper bound on the exact trip count. + SymbolicMaximum, }; /// Return the number of times the backedge executes before the given exit @@ -780,12 +782,15 @@ /// SCEVCouldNotCompute object. const SCEV *getConstantMaxBackedgeTakenCount(const Loop *L) { return getBackedgeTakenCount(L, ConstantMaximum); - } + } - /// Return a symbolic upper bound for the backedge taken count of the loop. - /// This is more general than getConstantMaxBackedgeTakenCount as it returns - /// an arbitrary expression as opposed to only constants. - const SCEV* computeMaxBackedgeTakenCount(const Loop *L); + /// When successful, this returns a SCEV that is greater than or equal + /// to (i.e. a "conservative over-approximation") of the value returend by + /// getBackedgeTakenCount. If such a value cannot be computed, it returns the + /// SCEVCouldNotCompute object. + const SCEV *getSymbolicMaxBackedgeTakenCount(const Loop *L) { + return getBackedgeTakenCount(L, SymbolicMaximum); + } /// Return true if the backedge taken count is either the value returned by /// getConstantMaxBackedgeTakenCount or zero. @@ -1317,15 +1322,19 @@ /// never have more than one computable exit. SmallVector ExitNotTaken; - /// Expression indicating the least maximum backedge-taken count of the loop - /// that is known, or a SCEVCouldNotCompute. This expression is only valid - /// if the redicates associated with all loop exits are true. + /// Expression indicating the least constant maximum backedge-taken count of + /// the loop that is known, or a SCEVCouldNotCompute. This expression is + /// only valid if the redicates associated with all loop exits are true. const SCEV *ConstantMax; /// Indicating if \c ExitNotTaken has an element for every exiting block in /// the loop. bool IsComplete; + /// Expression indicating the least maximum backedge-taken count of the loop + /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query. + const SCEV *SymbolicMax = nullptr; + /// True iff the backedge is taken either exactly Max or zero times. bool MaxOrZero = false; @@ -1391,6 +1400,9 @@ const SCEV *getConstantMax(const BasicBlock *ExitingBlock, ScalarEvolution *SE) const; + /// Get the symbolic max backedge taken count for the loop. + const SCEV *getSymbolicMax(const Loop *L, ScalarEvolution *SE); + /// Return true if the number of times this backedge is taken is either the /// value returned by getConstantMax or zero. bool isConstantMaxOrZero(ScalarEvolution *SE) const; @@ -1543,7 +1555,7 @@ /// Return the BackedgeTakenInfo for the given loop, lazily computing new /// values if the loop hasn't been analyzed yet. The returned result is /// guaranteed not to be predicated. - const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); + BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); /// Similar to getBackedgeTakenInfo, but will add predicates as required /// with the purpose of returning complete information. @@ -1576,6 +1588,11 @@ bool ExitIfTrue, bool ControlsExit, bool AllowPredicates = false); + /// Return a symbolic upper bound for the backedge taken count of the loop. + /// This is more general than getConstantMaxBackedgeTakenCount as it returns + /// an arbitrary expression as opposed to only constants. + const SCEV *computeSymbolicMaxBackedgeTakenCount(const Loop *L); + // Helper functions for computeExitLimitFromCond to avoid exponential time // complexity. Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -6508,6 +6508,7 @@ ExitCountKind Kind) { switch (Kind) { case Exact: + case SymbolicMaximum: return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); case ConstantMaximum: return getBackedgeTakenInfo(L).getConstantMax(ExitingBlock, this); @@ -6528,6 +6529,8 @@ return getBackedgeTakenInfo(L).getExact(L, this); case ConstantMaximum: return getBackedgeTakenInfo(L).getConstantMax(this); + case SymbolicMaximum: + return getBackedgeTakenInfo(L).getSymbolicMax(L, this); }; llvm_unreachable("Invalid ExitCountKind!"); } @@ -6563,7 +6566,7 @@ return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result); } -const ScalarEvolution::BackedgeTakenInfo & +ScalarEvolution::BackedgeTakenInfo & ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // Initially insert an invalid entry for this loop. If the insertion // succeeds, proceed to actually compute a backedge-taken count and @@ -6850,7 +6853,7 @@ return SE->getCouldNotCompute(); } -/// getMax - Get the max backedge taken count for the loop. +/// getConstantMax - Get the constant max backedge taken count for the loop. const SCEV * ScalarEvolution::BackedgeTakenInfo::getConstantMax(ScalarEvolution *SE) const { auto PredicateNotAlwaysTrue = [](const ExitNotTakenInfo &ENT) { @@ -6866,6 +6869,14 @@ return getConstantMax(); } +const SCEV * +ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(const Loop *L, + ScalarEvolution *SE) { + if (!SymbolicMax) + SymbolicMax = SE->computeSymbolicMaxBackedgeTakenCount(L); + return SymbolicMax; +} + bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero( ScalarEvolution *SE) const { auto PredicateNotAlwaysTrue = [](const ExitNotTakenInfo &ENT) { @@ -12714,7 +12725,8 @@ return false; } -const SCEV* ScalarEvolution::computeMaxBackedgeTakenCount(const Loop *L) { +const SCEV * +ScalarEvolution::computeSymbolicMaxBackedgeTakenCount(const Loop *L) { SmallVector ExitingBlocks; L->getExitingBlocks(ExitingBlocks); Index: llvm/lib/Transforms/Scalar/IndVarSimplify.cpp =================================================================== --- llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -2372,7 +2372,7 @@ return false; // Get a symbolic upper bound on the loop backedge taken count. - const SCEV *MaxExitCount = SE->computeMaxBackedgeTakenCount(L); + const SCEV *MaxExitCount = SE->getSymbolicMaxBackedgeTakenCount(L); if (isa(MaxExitCount)) return false;