[SCEV] NFC. Extract caching logic from the SCEVRewriteVisitor into the CachingSCEVVisitor

[igor-laevsky]

Summary

Sometimes SCEV caching logic is required for the non-rewriting visitors (https://reviews.llvm.org/D29759) . I've extracted it into single abstract place in order to not duplicate it multiple times.

include/llvm/Analysis/ScalarEvolutionExpressions.h

RetVal visit(const SCEV *S) {
       }
     }
 
     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
     }
   };
 
+  template <typename SC, typename RetVal = void>
+  class CachingSCEVVisitor : public SCEVVisitor<SC, RetVal> {
+  private:
+    // Memoize the result of each visit so that we only compute once for
+    // the same input SCEV. This is to avoid redundant computations when
+    // a SCEV is referenced by multiple SCEVs. Without memoization, this
+    // visit algorithm would have exponential time complexity in the worst
+    // case, causing the compiler to hang on certain tests.
+    DenseMap<const SCEV *, RetVal> Results;
+
+  public:
+    RetVal visit(const SCEV *S) {
+      auto It = Results.find(S);
+      if (It != Results.end())
+        return It->second;
+
+      RetVal Visited = SCEVVisitor<SC, RetVal>::visit(S);
+      auto Result = Results.try_emplace(S, Visited);
+      assert(Result.second && "Should insert a new entry");
+      return Result.first->second;
+    }
+  };
+
   /// Visit all nodes in the expression tree using worklist traversal.
   ///
   /// Visitor implements:
   ///   // return true to follow this node.
   ///   bool follow(const SCEV *S);
   ///   // return true to terminate the search.
   ///   bool isDone();
   template<typename SV>
bool SCEVExprContains(const SCEV *Root, PredTy Pred) {
     visitAll(Root, FC);
     return FC.Found;
   }
 
   /// This visitor recursively visits a SCEV expression and re-writes it.
   /// The result from each visit is cached, so it will return the same
   /// SCEV for the same input.
   template<typename SC>
-  class SCEVRewriteVisitor : public SCEVVisitor<SC, const SCEV *> {
+  class SCEVRewriteVisitor : public CachingSCEVVisitor<SC, const SCEV *> {
   protected:
     ScalarEvolution &SE;
-    // Memoize the result of each visit so that we only compute once for
-    // the same input SCEV. This is to avoid redundant computations when
-    // a SCEV is referenced by multiple SCEVs. Without memoization, this
-    // visit algorithm would have exponential time complexity in the worst
-    // case, causing the compiler to hang on certain tests.
-    DenseMap<const SCEV *, const SCEV *> RewriteResults;
 
   public:
     SCEVRewriteVisitor(ScalarEvolution &SE) : SE(SE) {}
 
-    const SCEV *visit(const SCEV *S) {
-      auto It = RewriteResults.find(S);
-      if (It != RewriteResults.end())
-        return It->second;
-      auto* Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
-      auto Result = RewriteResults.try_emplace(S, Visited);
-      assert(Result.second && "Should insert a new entry");
-      return Result.first->second;
-    }
-
     const SCEV *visitConstant(const SCEVConstant *Constant) {
       return Constant;
     }
 
     const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
       const SCEV *Operand = ((SC*)this)->visit(Expr->getOperand());
       return SE.getTruncateExpr(Operand, Expr->getType());
     }