From: Dan Gohman Date: Mon, 31 Aug 2009 21:15:23 +0000 (+0000) Subject: Extend the ValuesAtScope cache to cover all expressions, not just X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=42214899082bfb5b6f8c6a09d355fec9ef4a0e82 Extend the ValuesAtScope cache to cover all expressions, not just SCEVUnknowns, as the non-SCEVUnknown cases in the getSCEVAtScope code can also end up repeatedly climing through the same expression trees, which can be unusably slow when the trees are very tall. Also, add a quick check for SCEV pointer equality to the main SCEV comparison routine, as the full comparison code can be expensive in the case of large expression trees. These fix compile-time problems in some pathlogical cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80623 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 8e5f540c5e9..67e26597fce 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -219,10 +219,11 @@ namespace llvm { /// exit value. std::map ConstantEvolutionLoopExitValue; - /// ValuesAtScopes - This map contains entries for all the instructions - /// that we attempt to compute getSCEVAtScope information for without - /// using SCEV techniques, which can be expensive. - std::map > ValuesAtScopes; + /// ValuesAtScopes - This map contains entries for all the expressions + /// that we attempt to compute getSCEVAtScope information for, which can + /// be expensive in extreme cases. + std::map > ValuesAtScopes; /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. @@ -236,6 +237,11 @@ namespace llvm { /// SCEVs. const SCEV *createNodeForGEP(Operator *GEP); + /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called + /// at most once for each SCEV+Loop pair. + /// + const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); + /// ForgetSymbolicValue - This looks up computed SCEV values for all /// instructions that depend on the given instruction and removes them from /// the Scalars map if they reference SymName. This is used during PHI diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index d639aee7099..3b7e4387508 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -385,6 +385,10 @@ namespace { explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {} bool operator()(const SCEV *LHS, const SCEV *RHS) const { + // Fast-path: SCEVs are uniqued so we can do a quick equality check. + if (LHS == RHS) + return false; + // Primarily, sort the SCEVs by their getSCEVType(). if (LHS->getSCEVType() != RHS->getSCEVType()) return LHS->getSCEVType() < RHS->getSCEVType(); @@ -2420,9 +2424,10 @@ ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { // count information isn't going to change anything. In the later // case, createNodeForPHI will perform the necessary updates on its // own when it gets to that point. - if (!isa(I) || !isa(It->second)) + if (!isa(I) || !isa(It->second)) { + ValuesAtScopes.erase(It->second); Scalars.erase(It); - ValuesAtScopes.erase(I); + } } PushDefUseChildren(I, Worklist); @@ -3232,9 +3237,10 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // count information isn't going to change anything. In the later // case, createNodeForPHI will perform the necessary updates on its // own when it gets to that point. - if (!isa(I) || !isa(It->second)) + if (!isa(I) || !isa(It->second)) { + ValuesAtScopes.erase(It->second); Scalars.erase(It); - ValuesAtScopes.erase(I); + } if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); } @@ -3264,8 +3270,8 @@ void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { std::map::iterator It = Scalars.find(static_cast(I)); if (It != Scalars.end()) { + ValuesAtScopes.erase(It->second); Scalars.erase(It); - ValuesAtScopes.erase(I); if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); } @@ -3897,8 +3903,20 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, /// In the case that a relevant loop exit value cannot be computed, the /// original value V is returned. const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { - // FIXME: this should be turned into a virtual method on SCEV! + // Check to see if we've folded this expression at this loop before. + std::map &Values = ValuesAtScopes[V]; + std::pair::iterator, bool> Pair = + Values.insert(std::make_pair(L, static_cast(0))); + if (!Pair.second) + return Pair.first->second ? Pair.first->second : V; + // Otherwise compute it. + const SCEV *C = computeSCEVAtScope(V, L); + Pair.first->second = C; + return C; +} + +const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { if (isa(V)) return V; // If this instruction is evolved from a constant-evolving PHI, compute the @@ -3931,13 +3949,6 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { - // Check to see if we've folded this instruction at this loop before. - std::map &Values = ValuesAtScopes[I]; - std::pair::iterator, bool> Pair = - Values.insert(std::make_pair(L, static_cast(0))); - if (!Pair.second) - return Pair.first->second ? &*getSCEV(Pair.first->second) : V; - std::vector Operands; Operands.reserve(I->getNumOperands()); for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { @@ -3986,7 +3997,6 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), &Operands[0], Operands.size(), getContext()); - Pair.first->second = C; return getSCEV(C); } } @@ -5031,8 +5041,6 @@ void ScalarEvolution::SCEVCallbackVH::deleted() { assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!"); if (PHINode *PN = dyn_cast(getValPtr())) SE->ConstantEvolutionLoopExitValue.erase(PN); - if (Instruction *I = dyn_cast(getValPtr())) - SE->ValuesAtScopes.erase(I); SE->Scalars.erase(getValPtr()); // this now dangles! } @@ -5062,8 +5070,6 @@ void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) { continue; if (PHINode *PN = dyn_cast(U)) SE->ConstantEvolutionLoopExitValue.erase(PN); - if (Instruction *I = dyn_cast(U)) - SE->ValuesAtScopes.erase(I); SE->Scalars.erase(U); for (Value::use_iterator UI = U->use_begin(), UE = U->use_end(); UI != UE; ++UI) @@ -5073,8 +5079,6 @@ void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) { if (DeleteOld) { if (PHINode *PN = dyn_cast(Old)) SE->ConstantEvolutionLoopExitValue.erase(PN); - if (Instruction *I = dyn_cast(Old)) - SE->ValuesAtScopes.erase(I); SE->Scalars.erase(Old); // this now dangles! }