Index: polly/trunk/include/polly/Support/SCEVAffinator.h
===================================================================
--- polly/trunk/include/polly/Support/SCEVAffinator.h
+++ polly/trunk/include/polly/Support/SCEVAffinator.h
@@ -14,6 +14,7 @@
 #ifndef POLLY_SCEV_AFFINATOR_H
 #define POLLY_SCEV_AFFINATOR_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
 #include "isl/ctx.h"
@@ -44,6 +45,7 @@
 struct SCEVAffinator : public llvm::SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
 public:
   SCEVAffinator(Scop *S);
+  ~SCEVAffinator();
 
   /// @brief Translate a SCEV to an isl_pw_aff.
   ///
@@ -54,11 +56,18 @@
   __isl_give isl_pw_aff *getPwAff(const llvm::SCEV *E, const ScopStmt *Stmt);
 
 private:
+  /// @brief Key to identify cached expressions.
+  using CacheKey = std::pair<const llvm::SCEV *, const ScopStmt *>;
+
+  /// @brief Map to remembered cached expressions.
+  llvm::DenseMap<CacheKey, isl_pw_aff *> CachedExpressions;
+
   Scop *S;
   isl_ctx *Ctx;
   unsigned NumIterators;
   const llvm::Region &R;
   llvm::ScalarEvolution &SE;
+  const ScopStmt *Stmt;
 
   int getLoopDepth(const llvm::Loop *L);
 
Index: polly/trunk/lib/Support/SCEVAffinator.cpp
===================================================================
--- polly/trunk/lib/Support/SCEVAffinator.cpp
+++ polly/trunk/lib/Support/SCEVAffinator.cpp
@@ -29,8 +29,14 @@
 SCEVAffinator::SCEVAffinator(Scop *S)
     : S(S), Ctx(S->getIslCtx()), R(S->getRegion()), SE(*S->getSE()) {}
 
+SCEVAffinator::~SCEVAffinator() {
+  for (const auto &CachedPair : CachedExpressions)
+    isl_pw_aff_free(CachedPair.second);
+}
+
 __isl_give isl_pw_aff *SCEVAffinator::getPwAff(const SCEV *Expr,
                                                const ScopStmt *Stmt) {
+  this->Stmt = Stmt;
   NumIterators = Stmt->getNumIterators();
 
   S->addParams(getParamsInAffineExpr(&R, Expr, SE));
@@ -39,6 +45,13 @@
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visit(const SCEV *Expr) {
+
+  auto Key = std::make_pair(Expr, Stmt);
+  isl_pw_aff *PWA = CachedExpressions[Key];
+
+  if (PWA)
+    return isl_pw_aff_copy(PWA);
+
   // In case the scev is a valid parameter, we do not further analyze this
   // expression, but create a new parameter in the isl_pw_aff. This allows us
   // to treat subexpressions that we cannot translate into an piecewise affine
@@ -51,10 +64,14 @@
     isl_aff *Affine = isl_aff_zero_on_domain(isl_local_space_from_space(Space));
     Affine = isl_aff_add_coefficient_si(Affine, isl_dim_param, 0, 1);
 
-    return isl_pw_aff_alloc(Domain, Affine);
+    PWA = isl_pw_aff_alloc(Domain, Affine);
+    CachedExpressions[Key] = PWA;
+    return isl_pw_aff_copy(PWA);
   }
 
-  return SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
+  PWA = SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
+  CachedExpressions[Key] = PWA;
+  return isl_pw_aff_copy(PWA);
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitConstant(const SCEVConstant *Expr) {