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

1 files changed, 10 insertions, 4 deletions

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 8e5f540..67e2659 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -219,10 +219,11 @@ namespace llvm {
     /// exit value.
     std::map<PHINode*, Constant*> 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<Instruction *, std::map<const Loop *, Constant *> > 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<const SCEV *,
+             std::map<const Loop *, const SCEV *> > 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