diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/ScalarEvolution.h | 11 | ||||
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 55 |
2 files changed, 28 insertions, 38 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index 96309debd84..d60c16158fd 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1272,9 +1272,6 @@ private: /// function as they are computed. DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts; - // Cache the calculated exit limits for the loops. - DenseMap<ExitLimitQuery, ExitLimit> ExitLimits; - /// This map contains entries for all of the PHI instructions that we /// attempt to compute constant evolutions for. This allows us to avoid /// potentially expensive recomputation of these properties. An instruction @@ -1426,9 +1423,6 @@ private: ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates = false); - ExitLimit computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock, - bool AllowPredicates = false); - /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of ExitCond, /// TBB, and FBB. @@ -1668,9 +1662,8 @@ private: /// to be a constant. Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS); - /// Drop memoized information computed for S. Only erase Exit Limits info if - /// we expect that the operation we have made is going to change it. - void forgetMemoizedResults(const SCEV *S, bool EraseExitLimit = true); + /// Drop memoized information computed for S. + void forgetMemoizedResults(const SCEV *S); /// Return an existing SCEV for V if there is one, otherwise return nullptr. const SCEV *getExistingSCEV(Value *V); diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index e598f2005c3..98c2845c1e6 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -6433,13 +6433,36 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // own when it gets to that point. if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) { eraseValueFromMap(It->first); - forgetMemoizedResults(Old, false); + forgetMemoizedResults(Old); } if (PHINode *PN = dyn_cast<PHINode>(I)) ConstantEvolutionLoopExitValue.erase(PN); } - PushDefUseChildren(I, Worklist); + // Since we don't need to invalidate anything for correctness and we're + // only invalidating to make SCEV's results more precise, we get to stop + // early to avoid invalidating too much. This is especially important in + // cases like: + // + // %v = f(pn0, pn1) // pn0 and pn1 used through some other phi node + // loop0: + // %pn0 = phi + // ... + // loop1: + // %pn1 = phi + // ... + // + // where both loop0 and loop1's backedge taken count uses the SCEV + // expression for %v. If we don't have the early stop below then in cases + // like the above, getBackedgeTakenInfo(loop1) will clear out the trip + // count for loop0 and getBackedgeTakenInfo(loop0) will clear out the trip + // count for loop1, effectively nullifying SCEV's trip count cache. + for (auto *U : I->users()) + if (auto *I = dyn_cast<Instruction>(U)) { + auto *LoopForUser = LI.getLoopFor(I->getParent()); + if (LoopForUser && L->contains(LoopForUser)) + Worklist.push_back(I); + } } } @@ -6510,12 +6533,6 @@ void ScalarEvolution::forgetLoop(const Loop *L) { PushDefUseChildren(I, Worklist); } - for (auto I = ExitLimits.begin(); I != ExitLimits.end(); ++I) { - auto &Query = I->first; - if (Query.L == CurrL) - ExitLimits.erase(I); - } - LoopPropertiesCache.erase(CurrL); // Forget all contained loops too, to avoid dangling entries in the // ValuesAtScopes map. @@ -6777,18 +6794,6 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L, ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, - bool AllowPredicates) { - ExitLimitQuery Query(L, ExitingBlock, AllowPredicates); - auto MaybeEL = ExitLimits.find(Query); - if (MaybeEL != ExitLimits.end()) - return MaybeEL->second; - ExitLimit EL = computeExitLimitImpl(L, ExitingBlock, AllowPredicates); - ExitLimits.insert({Query, EL}); - return EL; -} - -ScalarEvolution::ExitLimit -ScalarEvolution::computeExitLimitImpl(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates) { // Okay, we've chosen an exiting block. See what condition causes us to exit // at this block and remember the exit block and whether all other targets @@ -10682,7 +10687,6 @@ ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg) BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)), PredicatedBackedgeTakenCounts( std::move(Arg.PredicatedBackedgeTakenCounts)), - ExitLimits(std::move(Arg.ExitLimits)), ConstantEvolutionLoopExitValue( std::move(Arg.ConstantEvolutionLoopExitValue)), ValuesAtScopes(std::move(Arg.ValuesAtScopes)), @@ -11097,7 +11101,7 @@ bool ScalarEvolution::ExitLimit::hasOperand(const SCEV *S) const { } void -ScalarEvolution::forgetMemoizedResults(const SCEV *S, bool EraseExitLimit) { +ScalarEvolution::forgetMemoizedResults(const SCEV *S) { ValuesAtScopes.erase(S); LoopDispositions.erase(S); BlockDispositions.erase(S); @@ -11130,13 +11134,6 @@ ScalarEvolution::forgetMemoizedResults(const SCEV *S, bool EraseExitLimit) { RemoveSCEVFromBackedgeMap(BackedgeTakenCounts); RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts); - - // TODO: There is a suspicion that we only need to do it when there is a - // SCEVUnknown somewhere inside S. Need to check this. - if (EraseExitLimit) - for (auto I = ExitLimits.begin(), E = ExitLimits.end(); I != E; ++I) - if (I->second.hasOperand(S)) - ExitLimits.erase(I); } void ScalarEvolution::addToLoopUseLists(const SCEV *S) { |
