Add caching to the SCEVAffinator

[grosser]

The patch itself is also reasonable, but it would probably be good to
give some motivation in the commit message why we need this cache.

Does this already improve compile time for cases we see today? Or
is this only an improvement if/when we add more complexity to the
SCEVAffinator e.g. to model modulo wrapping?

+ /// @brief Map to rememember cached expressions.

remembered

Tobias

[Meinersbur]

There might be also some saving in memory since the isl_pw_aff can be reused.

It might be interesting how many instances are reused. I think ratio cache hits to lookups might be more meaningful then a speed difference which may disappear in noise.

lib/Support/SCEVAffinator.cpp

50 ↗

(On Diff #31912)

Taking a reference s.t. there is no second lookup required when the value is set afterwards?

isl_pw_aff &*PWA = CachedExpressions[Key];
PWA = ...

[jdoerfert]

In D11975#222568, @Meinersbur wrote:

There might be also some saving in memory since the isl_pw_aff can be reused.

It might be interesting how many instances are reused. I think ratio cache hits to lookups might be more meaningful then a speed difference which may disappear in noise.

I haven't profiled reuse. Speed difference looked like noise to me (no meaningful difference in either direction).

[jdoerfert]

In D11975#222559, @grosser wrote:

The patch itself is also reasonable, but it would probably be good to
give some motivation in the commit message why we need this cache.

I will add the same as given below to the commit message. Is that enough?

Does this already improve compile time for cases we see today? Or
is this only an improvement if/when we add more complexity to the
SCEVAffinator e.g. to model modulo wrapping?

There is no difference in compile time today, however, with bigger SCoPs there might be.
Additionally, the cache will allow us to build all modulo wrapping constraints after we crreated the SCoP (before or during is not possible as the domains might not be ready).

+ /// @brief Map to rememember cached expressions.

remembered

Thx

lib/Support/SCEVAffinator.cpp

50 ↗

(On Diff #31912)

That doesn't work (it was my intitial approach) as the visit function is recursive. Hence, we modify the map and invalidate old iterators (or references to members).

[Meinersbur]

In D11975#222573, @jdoerfert wrote:

It might be interesting how many instances are reused. I think ratio cache hits to lookups might be more meaningful then a speed difference which may disappear in noise.

I haven't profiled reuse. Speed difference looked like noise to me (no meaningful difference in either direction).

That's why I suggested a hit ratio.

lib/Support/SCEVAffinator.cpp

50 ↗

(On Diff #31912)

Uhhh, thanks.

Then maybe using DenseMap::lookup() to avoid creating an empty key? Yes, it will be overwritten again eventually, but until then there are no empty values in the map.

[grosser]

jdoerfert marked an inline comment as done.
jdoerfert added a comment.

In http://reviews.llvm.org/D11975#222559, @grosser wrote:

The patch itself is also reasonable, but it would probably be good to

give some motivation in the commit message why we need this cache.

I will add the same as given below to the commit message. Is that enough?

Adding a cache that does not give speedup seems like a bad idea, but as
the code is rather simple we can probably justify this if this simplifies
the development of the modulo wrapping.

However, I did not yet understand how you will use this cache precisely.
The relevant patches (and some speedupdata) would be interesting to see,
(but not required for this patch to go in).

I personally would probably just discuss the modulo wrapping all together.
This would make it easier to understand how you use this cache?

Does this already improve compile time for cases we see today? Or

is this only an improvement if/when we add more complexity to the

SCEVAffinator e.g. to model modulo wrapping?

There is no difference in compile time today, however, with bigger SCoPs there might be.
Additionally, the cache will allow us to build all modulo wrapping constraints after we crreated the SCoP (before or during is not possible as the domains might not be ready).

I am not sure how this will work in the end. If we build the wrappings later,
I see two issues

1. Besides the SCEV's we probably also want to context in which they were built/used

to simplify them, right?

2. Do we simplify with context constraints that are only valid after simplification (and get a causality loop)

I mean, if we construct the context with the non-wrapping domains, and then use this
to simplify our non-wrapping constraints that we add in the assumed context, does this
not mean, that we used information in this simplification that we only had due to us
assuming the simplification to be valid in the first place? This could possibly
eliminate important constraints/restrictions, no?

Tobias

[jdoerfert]

final comment.

lib/Support/SCEVAffinator.cpp

50 ↗

(On Diff #31912)

I was hopeing to get better cache behaviour this way but I don't know. I'll commit it now but feel free to change it. (should not make a difference anyway).

[grosser]

I also just realized this patch did not have llvm-commits or polly-dev copied.

It would be good to add them for the next patches.

Best,
Tobias

jdoerfert marked an inline comment as done.
jdoerfert added a comment.

final comment.

Comment at: lib/Support/SCEVAffinator.cpp:50
@@ +49,3 @@
+ auto Key = std::make_pair(Expr, Stmt);
+ isl_pw_aff *PWA = CachedExpressions[Key];

+

Meinersbur wrote:

jdoerfert wrote:

Meinersbur wrote:

Taking a reference s.t. there is no second lookup required when the value is set afterwards?

isl_pw_aff &*PWA = CachedExpressions[Key];
PWA = ...

That doesn't work (it was my intitial approach) as the visit function is recursive. Hence, we modify the map and invalidate old iterators (or references to members).

Uhhh, thanks.

Then maybe using DenseMap::lookup() to avoid creating an empty key? Yes, it will be overwritten again eventually, but until then there are no empty values in the map.

I was hopeing to get better cache behaviour this way but I don't know. I'll commit it now but feel free to change it. (should not make a difference anyway).

http://reviews.llvm.org/D11975

[jdoerfert]

Could you add the pollydev Phabricator user to the polly group? That way
adding the polly group will suffice :)

• msg-15916-404.dat219 BDownload

[grosser]

jdoerfert added a subscriber: jdoerfert.
jdoerfert added a comment.

Could you add the pollydev Phabricator user to the polly group? That way
adding the polly group will suffice :)

Done. Thanks for the idea.

Tobias

polly/trunk/include/polly/Support/SCEVAffinator.h

 //===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Create a polyhedral description for a SCEV value.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCEV_AFFINATOR_H
 #define POLLY_SCEV_AFFINATOR_H
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
 #include "isl/ctx.h"
 
 struct isl_ctx;
 struct isl_map;
 struct isl_basic_map;
 struct isl_id;

 namespace polly {
 class Scop;
 class ScopStmt;
 
 /// Translate a SCEV to an isl_pw_aff.
 struct SCEVAffinator : public llvm::SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
 public:
   SCEVAffinator(Scop *S);
+  ~SCEVAffinator();
 
   /// @brief Translate a SCEV to an isl_pw_aff.
   ///
   /// @param E    The expression that is translated.
   /// @param Stmt The SCoP statement surrounding @p E.
   ///
   /// @returns The isl representation of the SCEV @p E in @p Stmt.
   __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);
 
   __isl_give isl_pw_aff *visit(const llvm::SCEV *E);
   __isl_give isl_pw_aff *visitConstant(const llvm::SCEVConstant *E);
   __isl_give isl_pw_aff *visitTruncateExpr(const llvm::SCEVTruncateExpr *E);
   __isl_give isl_pw_aff *visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E);
   __isl_give isl_pw_aff *visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E);

polly/trunk/lib/Support/SCEVAffinator.cpp

 #include "isl/local_space.h"
 
 using namespace llvm;
 using namespace polly;
 
 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));
 
   return visit(Expr);
 }
 
 __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
   // expression, as constant parameters of the piecewise affine expression.
   if (isl_id *Id = S->getIdForParam(Expr)) {
     isl_space *Space = isl_space_set_alloc(Ctx, 1, NumIterators);
     Space = isl_space_set_dim_id(Space, isl_dim_param, 0, Id);
 
     isl_set *Domain = isl_set_universe(isl_space_copy(Space));
     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) {
   ConstantInt *Value = Expr->getValue();
   isl_val *v;
 
   // LLVM does not define if an integer value is interpreted as a signed or
   // unsigned value. Hence, without further information, it is unknown how