diff options
author | Eli Friedman <efriedma@codeaurora.org> | 2018-06-27 20:35:02 +0000 |
---|---|---|
committer | Eli Friedman <efriedma@codeaurora.org> | 2018-06-27 20:35:02 +0000 |
commit | af8f91e9b62d6c3927552ddc329108d8390f1350 (patch) | |
tree | 913d57230d6e2ccaadebeae9836e0bf896a64950 /polly | |
parent | d251cf37a10558cc7f9ca24752a48b49c0d48e73 (diff) |
[ScopHelper] Cache ScopExpander results.
The number of SCEV expressions is usually linear in the number of IR
instructions being modeled. However, a naive SCEV visitor is not. 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.
Differential Revision: https://reviews.llvm.org/D47087
Diffstat (limited to 'polly')
-rw-r--r-- | polly/lib/Support/ScopHelper.cpp | 12 |
1 files changed, 12 insertions, 0 deletions
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp index f30e56a0442..df6731eacac 100644 --- a/polly/lib/Support/ScopHelper.cpp +++ b/polly/lib/Support/ScopHelper.cpp @@ -249,6 +249,17 @@ struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> { 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; @@ -256,6 +267,7 @@ private: const Region &R; ValueMapT *VMap; BasicBlock *RTCBB; + DenseMap<const SCEV *, const SCEV *> SCEVCache; const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst, Instruction *IP) { |