Add memoization for getSCEVAtScope results for instructions

which are not analyzed with SCEV techniques, which can require
brute-forcing through a large number of instructions. This
fixes a massive compile-time issue on 400.perlbench (in
particular, the loop in MD5Transform).

llvm-svn: 71259

1 files changed, 15 insertions, 0 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 8b48b78da41..4ddde5db5ed 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -2766,6 +2766,13 @@ SCEVHandle 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<const Loop *, Constant *> &Values = ValuesAtScopes[I];
+        std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
+          Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
+        if (!Pair.second)
+          return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
+
         std::vector<Constant*> Operands;
         Operands.reserve(I->getNumOperands());
         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
@@ -2812,6 +2819,7 @@ SCEVHandle ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
         else
           C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
                                        &Operands[0], Operands.size());
+        Pair.first->second = C;
         return getUnknown(C);
       }
     }
@@ -3473,6 +3481,8 @@ void SCEVCallbackVH::deleted() {
   assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
   if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
     SE->ConstantEvolutionLoopExitValue.erase(PN);
+  if (Instruction *I = dyn_cast<Instruction>(getValPtr()))
+    SE->ValuesAtScopes.erase(I);
   SE->Scalars.erase(getValPtr());
   // this now dangles!
 }
@@ -3499,6 +3509,8 @@ void SCEVCallbackVH::allUsesReplacedWith(Value *) {
     }
     if (PHINode *PN = dyn_cast<PHINode>(U))
       SE->ConstantEvolutionLoopExitValue.erase(PN);
+    if (Instruction *I = dyn_cast<Instruction>(U))
+      SE->ValuesAtScopes.erase(I);
     if (SE->Scalars.erase(U))
       for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
            UI != UE; ++UI)
@@ -3507,6 +3519,8 @@ void SCEVCallbackVH::allUsesReplacedWith(Value *) {
   if (DeleteOld) {
     if (PHINode *PN = dyn_cast<PHINode>(Old))
       SE->ConstantEvolutionLoopExitValue.erase(PN);
+    if (Instruction *I = dyn_cast<Instruction>(Old))
+      SE->ValuesAtScopes.erase(I);
     SE->Scalars.erase(Old);
     // this now dangles!
   }
@@ -3535,6 +3549,7 @@ void ScalarEvolution::releaseMemory() {
   Scalars.clear();
   BackedgeTakenCounts.clear();
   ConstantEvolutionLoopExitValue.clear();
+  ValuesAtScopes.clear();
 }
 
 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {