diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/ScalarEvolution.h | 9 | ||||
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 18 | ||||
| -rw-r--r-- | llvm/lib/Transforms/Scalar/IndVarSimplify.cpp | 6 |
3 files changed, 25 insertions, 8 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index fc22680f537..5cbc4066610 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1244,13 +1244,15 @@ private: struct ExitNotTakenInfo { PoisoningVH<BasicBlock> ExitingBlock; const SCEV *ExactNotTaken; + const SCEV *MaxNotTaken; std::unique_ptr<SCEVUnionPredicate> Predicate; explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock, const SCEV *ExactNotTaken, + const SCEV *MaxNotTaken, std::unique_ptr<SCEVUnionPredicate> Predicate) - : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken), - Predicate(std::move(Predicate)) {} + : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken), + MaxNotTaken(ExactNotTaken), Predicate(std::move(Predicate)) {} bool hasAlwaysTruePredicate() const { return !Predicate || Predicate->isAlwaysTrue(); @@ -1333,6 +1335,9 @@ private: /// Get the max backedge taken count for the loop. const SCEV *getMax(ScalarEvolution *SE) const; + /// Get the max backedge taken count for the particular loop exit. + const SCEV *getMax(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; + /// Return true if the number of times this backedge is taken is either the /// value returned by getMax or zero. bool isMaxOrZero(ScalarEvolution *SE) const; diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index bfb0c0dfb60..163e1fe62d6 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -6606,7 +6606,7 @@ const SCEV *ScalarEvolution::getExitCount(const Loop *L, case Exact: return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); case ConstantMaximum: - return getCouldNotCompute(); + return getBackedgeTakenInfo(L).getMax(ExitingBlock, this); }; llvm_unreachable("Invalid ExitCountKind!"); } @@ -6934,6 +6934,16 @@ ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock, return SE->getCouldNotCompute(); } +const SCEV * +ScalarEvolution::BackedgeTakenInfo::getMax(BasicBlock *ExitingBlock, + ScalarEvolution *SE) const { + for (auto &ENT : ExitNotTaken) + if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate()) + return ENT.MaxNotTaken; + + return SE->getCouldNotCompute(); +} + /// getMax - Get the max backedge taken count for the loop. const SCEV * ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const { @@ -7025,13 +7035,15 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( BasicBlock *ExitBB = EEI.first; const ExitLimit &EL = EEI.second; if (EL.Predicates.empty()) - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, nullptr); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + nullptr); std::unique_ptr<SCEVUnionPredicate> Predicate(new SCEVUnionPredicate); for (auto *Pred : EL.Predicates) Predicate->add(Pred); - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate)); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + std::move(Predicate)); }); assert((isa<SCEVCouldNotCompute>(MaxCount) || isa<SCEVConstant>(MaxCount)) && "No point in having a non-constant max backedge taken count!"); diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp index 40cc3fc3af2..4520a468aca 100644 --- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -2662,11 +2662,11 @@ static const SCEV* getMaxBackedgeTakenCount(ScalarEvolution &SE, // merge the max and exact information to approximate a version of // getConstantMaxBackedgeTakenCount which isn't restricted to just constants. SmallVector<const SCEV*, 4> ExitCounts; - const SCEV *MaxConstEC = SE.getConstantMaxBackedgeTakenCount(L); - if (!isa<SCEVCouldNotCompute>(MaxConstEC)) - ExitCounts.push_back(MaxConstEC); for (BasicBlock *ExitingBB : ExitingBlocks) { const SCEV *ExitCount = SE.getExitCount(L, ExitingBB); + if (isa<SCEVCouldNotCompute>(ExitCount)) + ExitCount = SE.getExitCount(L, ExitingBB, + ScalarEvolution::ConstantMaximum); if (!isa<SCEVCouldNotCompute>(ExitCount)) { assert(DT.dominates(ExitingBB, L->getLoopLatch()) && "We should only have known counts for exiting blocks that " |
