[ScopHelper] Cache ScopExpander results.

[efriedma]

Summary

A naive SCEV visitor not linear in the number of SCEV expressions. For an expression like x*x, "x" will be visited twice. If x is itself an expression like x*x, that will be visited twice, etc, and the overall runtime is O(2^N) in the number of SCEV expressions.

To prevent this from happening, add a cache, so we only visit each SCEV expression once.

Not sure this is the best solution. Maybe we can instead check whether the SCEV is scop-invariant (in which case we never need to map the value). But we don't have a utility for that at the moment.

[Meinersbur]

SCEVExpander itself already has a cache. For some reason (I don't understand myself) ScopExpander recursively visits the SCEV before calling into SCEVExpander (and in the process expands subelements itself, then converts it back using getSCEV?!!!?). The SCEV has already been visited even before polly::expandCodeFor is called in trySynthesizeNewValue to replace original (non-SCEV) values by generated ones.

Usually, it's SCEVRewriteVisitor's job to do the cached, which the pre-process pass of SCEVExpander does not use.

Ideally, the caching (e.g. by SCEVExpander) should happen on BB-level. That is, BlockGenerator should hold the ScopExpander, such that expandCodeFor does not start with a clear cache every time it is called.

I know this is a lot of work, so I am fine with this as a quick fix.

polly/trunk/lib/Support/ScopHelper.cpp

Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
     // If we generate code in the region we will immediately fall back to the
     // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
     // needed replace them by copies computed in the entering block.
     if (!R.contains(I))
       E = visit(E);
     return Expander.expandCodeFor(E, Ty, I);
   }
 
+  const SCEV *visit(const SCEV *E) {
+    // Cache the expansion results for intermediate SCEV expressions. A SCEV
+    // expression can refer to an operand multiple times (e.g. "x*x), so
+    // a naive visitor takes exponential time.
+    if (SCEVCache.count(E))
+      return SCEVCache[E];
+    const SCEV *Result = SCEVVisitor::visit(E);
+    SCEVCache[E] = Result;
+    return Result;
+  }
+
 private:
   SCEVExpander Expander;
   ScalarEvolution &SE;
   const char *Name;
   const Region &R;
   ValueMapT *VMap;
   BasicBlock *RTCBB;
+  DenseMap<const SCEV *, const SCEV *> SCEVCache;
 
   const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
                                Instruction *IP) {
     if (!Inst || !R.contains(Inst))
       return E;
 
     assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
            !isa<PHINode>(Inst));