From: Dan Gohman Date: Wed, 17 Nov 2010 23:21:44 +0000 (+0000) Subject: Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, and X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=714b5290b04e08570dae4304c1c92d30c06d3c99 Merge the implementations of isLoopInvariant and hasComputableLoopEvolution, and memoize the results. This improves compile time in code which highly complex expressions which get queried many times. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119584 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 750a090fe78..26eceba8152 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -142,6 +142,16 @@ namespace llvm { /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { + public: + /// LoopDisposition - An enum describing the relationship between a + /// SCEV and a loop. + enum LoopDisposition { + LoopVariant, ///< The SCEV is loop-variant (unknown). + LoopInvariant, ///< The SCEV is loop-invariant. + LoopComputable ///< The SCEV varies predictably with the loop. + }; + + private: /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be /// notified whenever a Value is deleted. class SCEVCallbackVH : public CallbackVH { @@ -229,6 +239,13 @@ namespace llvm { std::map > ValuesAtScopes; + /// LoopDispositions - Memoized computeLoopDisposition results. + std::map > LoopDispositions; + + /// computeLoopDisposition - Compute a LoopDisposition value. + LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); + /// UnsignedRanges - Memoized results from getUnsignedRange DenseMap UnsignedRanges; @@ -663,6 +680,10 @@ namespace llvm { const SCEV *&LHS, const SCEV *&RHS); + /// getLoopDisposition - Return the "disposition" of the given SCEV with + /// respect to the given loop. + LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); + /// isLoopInvariant - Return true if the value of the given SCEV is /// unchanging in the specified loop. bool isLoopInvariant(const SCEV *S, const Loop *L); diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 99ab84dc0c2..b734d00f7fe 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -326,6 +326,7 @@ SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, void SCEVUnknown::deleted() { // Clear this SCEVUnknown from various maps. SE->ValuesAtScopes.erase(this); + SE->LoopDispositions.erase(this); SE->UnsignedRanges.erase(this); SE->SignedRanges.erase(this); @@ -339,6 +340,7 @@ void SCEVUnknown::deleted() { void SCEVUnknown::allUsesReplacedWith(Value *New) { // Clear this SCEVUnknown from various maps. SE->ValuesAtScopes.erase(this); + SE->LoopDispositions.erase(this); SE->UnsignedRanges.erase(this); SE->SignedRanges.erase(this); @@ -2635,6 +2637,7 @@ ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) { !isa(Old) || (I != PN && Old == SymName)) { ValuesAtScopes.erase(Old); + LoopDispositions.erase(Old); UnsignedRanges.erase(Old); SignedRanges.erase(Old); ValueExprMap.erase(It); @@ -3675,6 +3678,7 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // own when it gets to that point. if (!isa(I) || !isa(Old)) { ValuesAtScopes.erase(Old); + LoopDispositions.erase(Old); UnsignedRanges.erase(Old); SignedRanges.erase(Old); ValueExprMap.erase(It); @@ -3710,6 +3714,7 @@ void ScalarEvolution::forgetLoop(const Loop *L) { if (It != ValueExprMap.end()) { const SCEV *Old = It->second; ValuesAtScopes.erase(Old); + LoopDispositions.erase(Old); UnsignedRanges.erase(Old); SignedRanges.erase(Old); ValueExprMap.erase(It); @@ -3746,6 +3751,7 @@ void ScalarEvolution::forgetValue(Value *V) { if (It != ValueExprMap.end()) { const SCEV *Old = It->second; ValuesAtScopes.erase(Old); + LoopDispositions.erase(Old); UnsignedRanges.erase(Old); SignedRanges.erase(Old); ValueExprMap.erase(It); @@ -5803,6 +5809,7 @@ void ScalarEvolution::releaseMemory() { BackedgeTakenCounts.clear(); ConstantEvolutionLoopExitValue.clear(); ValuesAtScopes.clear(); + LoopDispositions.clear(); UnsignedRanges.clear(); SignedRanges.clear(); UniqueSCEVs.clear(); @@ -5901,54 +5908,82 @@ void ScalarEvolution::print(raw_ostream &OS, const Module *) const { PrintLoopInfo(OS, &SE, *I); } -bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { +ScalarEvolution::LoopDisposition +ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { + std::map &Values = LoopDispositions[S]; + std::pair::iterator, bool> Pair = + Values.insert(std::make_pair(L, LoopVariant)); + if (!Pair.second) + return Pair.first->second; + + LoopDisposition D = computeLoopDisposition(S, L); + return LoopDispositions[S][L] = D; +} + +ScalarEvolution::LoopDisposition +ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { switch (S->getSCEVType()) { case scConstant: - return true; + return LoopInvariant; case scTruncate: case scZeroExtend: case scSignExtend: - return isLoopInvariant(cast(S)->getOperand(), L); + return getLoopDisposition(cast(S)->getOperand(), L); case scAddRecExpr: { const SCEVAddRecExpr *AR = cast(S); + // If L is the addrec's loop, it's computable. + if (AR->getLoop() == L) + return LoopComputable; + // Add recurrences are never invariant in the function-body (null loop). if (!L) - return false; + return LoopVariant; // This recurrence is variant w.r.t. L if L contains AR's loop. if (L->contains(AR->getLoop())) - return false; + return LoopVariant; // This recurrence is invariant w.r.t. L if AR's loop contains L. if (AR->getLoop()->contains(L)) - return true; + return LoopInvariant; // This recurrence is variant w.r.t. L if any of its operands // are variant. for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end(); I != E; ++I) if (!isLoopInvariant(*I, L)) - return false; + return LoopVariant; // Otherwise it's loop-invariant. - return true; + return LoopInvariant; } case scAddExpr: case scMulExpr: case scUMaxExpr: case scSMaxExpr: { const SCEVNAryExpr *NAry = cast(S); + bool HasVarying = false; for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); - I != E; ++I) - if (!isLoopInvariant(*I, L)) - return false; - return true; + I != E; ++I) { + LoopDisposition D = getLoopDisposition(*I, L); + if (D == LoopVariant) + return LoopVariant; + if (D == LoopComputable) + HasVarying = true; + } + return HasVarying ? LoopComputable : LoopInvariant; } case scUDivExpr: { const SCEVUDivExpr *UDiv = cast(S); - return isLoopInvariant(UDiv->getLHS(), L) && - isLoopInvariant(UDiv->getRHS(), L); + LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L); + if (LD == LoopVariant) + return LoopVariant; + LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L); + if (RD == LoopVariant) + return LoopVariant; + return (LD == LoopInvariant && RD == LoopInvariant) ? + LoopInvariant : LoopComputable; } case scUnknown: // All non-instruction values are loop invariant. All instructions are loop @@ -5956,71 +5991,23 @@ bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { // Instructions are never considered invariant in the function body // (null loop) because they are defined within the "loop". if (Instruction *I = dyn_cast(cast(S)->getValue())) - return L && !L->contains(I); - return true; + return (L && !L->contains(I)) ? LoopInvariant : LoopVariant; + return LoopInvariant; case scCouldNotCompute: llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - return false; + return LoopVariant; default: break; } llvm_unreachable("Unknown SCEV kind!"); - return false; + return LoopVariant; +} + +bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { + return getLoopDisposition(S, L) == LoopInvariant; } bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { - switch (S->getSCEVType()) { - case scConstant: - return false; - case scTruncate: - case scZeroExtend: - case scSignExtend: - return hasComputableLoopEvolution(cast(S)->getOperand(), L); - case scAddRecExpr: - return cast(S)->getLoop() == L; - case scAddExpr: - case scMulExpr: - case scUMaxExpr: - case scSMaxExpr: { - const SCEVNAryExpr *NAry = cast(S); - bool HasVarying = false; - for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); - I != E; ++I) { - const SCEV *Op = *I; - if (!isLoopInvariant(Op, L)) { - if (hasComputableLoopEvolution(Op, L)) - HasVarying = true; - else - return false; - } - } - return HasVarying; - } - case scUDivExpr: { - const SCEVUDivExpr *UDiv = cast(S); - bool HasVarying = false; - if (!isLoopInvariant(UDiv->getLHS(), L)) { - if (hasComputableLoopEvolution(UDiv->getLHS(), L)) - HasVarying = true; - else - return false; - } - if (!isLoopInvariant(UDiv->getRHS(), L)) { - if (hasComputableLoopEvolution(UDiv->getRHS(), L)) - HasVarying = true; - else - return false; - } - return HasVarying; - } - case scUnknown: - return false; - case scCouldNotCompute: - llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - return false; - default: break; - } - llvm_unreachable("Unknown SCEV kind!"); - return false; + return getLoopDisposition(S, L) == LoopComputable; } bool ScalarEvolution::dominates(const SCEV *S, BasicBlock *BB) const {