[Unfinished] Use modulo semantic to generate non-wrap assumptions

[jdoerfert]

Summary

This will allow to generate non-wrap assumptions for memory accesess.
We compare the old isl representation of the access functions with
the one computed with modulo semantic.

Notes:

• We will use all range information for parameters (even full ranges) to simplify the assumptions.
• We will respect the nsw flags when computing the modulo representation.

Some but not all test cases have been adjusted.

[grosser]

Hi Johannes,

this patch looks already great. I its overall structure and only have a couple of minor comments (see below).

We may also want to add a test case A[128 * p] to test the modulo path.

Best,
Tobias

lib/Analysis/ScopInfo.cpp

94 ↗

(On Diff #23995)

indicate

108 ↗

(On Diff #23995)

Why do you call this function 'NonWrap'? Is the point of this function not to add the integer wrapping? Could a name like 'addIntegerWrapping()' be a better fit?

131 ↗

(On Diff #23995)

UseModulo (start with uppercase)

143 ↗

(On Diff #23995)

A comment explaining how we implement the modulo of signed types might be helpful.

res = ((res + 2^7) mod (2 ^ 8)) - 2^7

144 ↗

(On Diff #23995)

Leftover.

147 ↗

(On Diff #23995)

Leftover.

268 ↗

(On Diff #23995)

This assert now fires for a couple of test cases, e.g. :
test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll

281 ↗

(On Diff #23995)

It seems you used this change remove the special case of isZero(). This special-case-removal seems partially unrelated. Maybe you want to commit this cleanup ahead of time (no review needed).

test/ScopInfo/simple_loop_1.ll

18 ↗

(On Diff #23995)

Not necessary, but if you commit these changes separately (no review required), we can see that most of the time we have indeed sufficient nsw information.

test/ScopInfo/wraping_signed_expr_1.ll

21 ↗

(On Diff #23995)

The C code uses chars, but here %N and %p are i64. Is this intended? I would actually prefer a version using 'char' to see bounds that are easier to understand.

31 ↗

(On Diff #23995)

Would it make sense to add a version that lacks the 'nsw' flag here?

test/ScopInfo/wraping_signed_expr_1_long.ll

21 ↗

(On Diff #23995)

char <> i64 mismatch

test/ScopInfo/wraping_signed_expr_5.ll

5 ↗

(On Diff #23995)

Missing change.

[jdoerfert]

Some comments, new version is coming soon.

lib/Analysis/ScopInfo.cpp

94 ↗

(On Diff #23995)

Done.

108 ↗

(On Diff #23995)

is

addModuloSemantic

fine?

131 ↗

(On Diff #23995)

Done.

143 ↗

(On Diff #23995)

Done.

144 ↗

(On Diff #23995)

Done.

147 ↗

(On Diff #23995)

Done.

268 ↗

(On Diff #23995)

I haven't looked at all the testcases yet but I am aware that some fail (hence the [Unfinished] part).
I'll check what happens here.

281 ↗

(On Diff #23995)

I will split it into a separate patch. It is needed as the new SCEV we introduced doesn't have to original flags and I don't see how we can keep them with the transformation we apply.

test/ScopInfo/wraping_signed_expr_1.ll

31 ↗

(On Diff #23995)

I have to check.

[jdoerfert]

I commited first parts of this patch already, however there are still two problems I wanted to discuss before we move forward.

1. A few (~8) tests in lnt fail, at least one of them times out when the complement of the isl_set is computed as the set has multiple existentially quantified variables. I tried to use the domain on which both functions are equal to avoid the complement but I cannot get the constraints on the parameters that way.
2. We currently assume parameters to be signed (e.g., use the signed range information about them) but this will use unsigned modulo semantic (e.g., mod bitwidth) to compute valid parameter combinations. First, this makes it hard to generate tests with small bounds and it additionally makes it hard to argue about the test cases we can generate. I am currently not even sure this is safe. An example for this clash of interpretation below:

// Let T be an integer type of width W
char *A = ...
T N = ...                   //   N    is in [-2^(W-1) : 2^(W-1) - 1]
for (T i = 0; i <= N; i++)  //   i    is in [     0   : 2^(W-1) - 1]
  A[i + 43] = ...           // i + 43 is in [    43   : 2^(W-1) + 42] which is non-wrapping modulo 2^W

[grosser]

In D9099#162193, @jdoerfert wrote:

I commited first parts of this patch already, however there are still two problems I wanted to discuss before we move forward.

I followed this. Nice.

1. A few (~8) tests in lnt fail, at least one of them times out when the complement of the isl_set is computed as the set has multiple existentially quantified variables. I tried to use the domain on which both functions are equal to avoid the complement but I cannot get the constraints on the parameters that way.

You do not happen to have a (minimal?) test case that shows this behavior?

2. We currently assume parameters to be signed (e.g., use the signed range information about them) but this will use unsigned modulo semantic (e.g., mod bitwidth) to compute valid parameter combinations.

What do you mean by "this"?

The 'res = ((res + 2^7) mod (2 ^ 8)) - 2^7' models wrapping of signed types, which
is what we want for signed types. Can you point me to where exactly we use 'signed modulo semantic'?

First, this makes it hard to generate tests with small bounds and it additionally makes it hard to argue about the test cases we can generate. I am currently not even sure this is safe. An example for this clash of interpretation below:

// Let T be an integer type of width W
char *A = ...
T N = ...                   //   N    is in [-2^(W-1) : 2^(W-1) - 1]
for (T i = 0; i <= N; i++)  //   i    is in [     0   : 2^(W-1) - 1]
  A[i + 43] = ...           // i + 43 is in [    43   : 2^(W-1) + 42] which is non-wrapping modulo 2^W

Should the expression i + 43 not also be modeled with signed arithmetic? Which means it is expected to be smaller than 2^(W-1)?

Best,
Tobias

[jdoerfert]

Modified tests and added wrapping tests including two that show huge slowdowns

[jdoerfert]

@Tobias You were right about the modulo thing... I was confused and mixed things up.

I also attaced to test cases that show fast and slow behaviour depending on the position of the sext or the presence of a multiplication.

[grosser]

Thanks for the update.

The patch looks good indeed.

I unfortunately I don't have a solution handy for the modulo issue. In the worst case we just put a compute-out here, but first we should understand why this complement is so expensive for isl (complements and subtracts sometimes are) and possibly run it through Sven to see if there is something we can optimize? We could also extract this as a 5 line isl test case and give it to Sven.

Best,
Tobias

lib/Analysis/ScopInfo.cpp

85 ↗

(On Diff #24503)

semantics

94 ↗

(On Diff #24503)

semantics

145 ↗

(On Diff #24503)

"represents Expr in modulo semantic"

What do you mean here? As you state right after, overflow is known to never happen. Hence, I don't see how this expression
defines overflow semantics. Maybe just say that we know overflow is undefined and are free to choose the definition to
use in our model. As wrapping is computationally more difficult to model we avoid it when allowed.

test/ScopInfo/wraping_signed_expr_2.ll

9 ↗

(On Diff #24503)

i + 30

[jdoerfert]

some comments

lib/Analysis/ScopInfo.cpp

85 ↗

(On Diff #24503)

done.

94 ↗

(On Diff #24503)

done.

145 ↗

(On Diff #24503)

It depends on the interpretation of the nsw flag. I assumed it is a certificate/proof that no overflow can happen, thus the expression is equal to the expression with modulo semantics. You say it is only well defined if this is the case, thus it is not always equal but we can ignore the cases it is not.

test/ScopInfo/wraping_signed_expr_2.ll

9 ↗

(On Diff #24503)

done.

polly/trunk/include/polly/ScopInfo.h

 // community, which are e.g. CLooG, Pluto, Loopo, Graphite.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOP_INFO_H
 #define POLLY_SCOP_INFO_H
 
 #include "polly/ScopDetection.h"
+#include "polly/Support/SCEVAffinator.h"
+
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/RegionPass.h"
 #include "isl/ctx.h"
 
 #include <list>
 #include <forward_list>
 #include <deque>
 

 struct isl_basic_map;
 struct isl_id;
 struct isl_set;
 struct isl_union_set;
 struct isl_union_map;
 struct isl_space;
 struct isl_ast_build;
 struct isl_constraint;
+struct isl_pw_aff;
 struct isl_pw_multi_aff;
 struct isl_schedule;
 
 namespace polly {
 
 class IRAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 class TempScop;
-class SCEVAffFunc;
 class Comparison;
+class SCEVAffFunc;
 
 /// @brief A class to store information about arrays in the SCoP.
 ///
 /// Objects are accessible via the ScoP, MemoryAccess or the id associated with
 /// the MemoryAccess access function.
 ///
 class ScopArrayInfo {
 public:
public:
   /// @brief Get the isl AST build.
   __isl_keep isl_ast_build *getAstBuild() const { return Build; }
 
   /// @brief Restrict the domain of the statement.
   ///
   /// @param NewDomain The new statement domain.
   void restrictDomain(__isl_take isl_set *NewDomain);
 
+  /// @brief Compute the isl representation for the SCEV @p E in this stmt.
+  __isl_give isl_pw_aff *getPwAff(const SCEV *E);
+
   /// @brief Get the loop for a dimension.
   ///
   /// @param Dimension The dimension of the induction variable
   /// @return The loop at a certain dimension.
   const Loop *getLoopForDimension(unsigned Dimension) const;
 
   /// @brief Align the parameters in the statement to the scop context
   void realignParams();
private:
   isl_ctx *IslCtx;
 
   /// @brief A map from basic blocks to SCoP statements.
   DenseMap<BasicBlock *, ScopStmt *> StmtMap;
 
   /// Constraints on parameters.
   isl_set *Context;
 
+  /// @brief The affinator used to translate SCEVs to isl expressions.
+  SCEVAffinator Affinator;
+
   typedef MapVector<std::pair<const Value *, int>,
                     std::unique_ptr<ScopArrayInfo>> ArrayInfoMapTy;
   /// @brief A map to remember ScopArrayInfo objects for all base pointers.
   ///
   /// As PHI nodes may have two array info objects associated, we add a flag
   /// that distinguishes between the PHI node specific ArrayInfo object
   /// and the normal one.
   ArrayInfoMapTy ScopArrayInfoMap;
public:
   /// @brief Print the ScopStmt to stderr.
   void dump() const;
 
   /// @brief Get the isl context of this static control part.
   ///
   /// @return The isl context of this static control part.
   isl_ctx *getIslCtx() const;
 
+  /// @brief Compute the isl representation for the SCEV @p E in @p Stmt.
+  __isl_give isl_pw_aff *getPwAff(const SCEV *E, ScopStmt *Stmt);
+
   /// @brief Get a union set containing the iteration domains of all statements.
   __isl_give isl_union_set *getDomains() const;
 
   /// @brief Get a union map of all may-writes performed in the SCoP.
   __isl_give isl_union_map *getMayWrites();
 
   /// @brief Get a union map of all must-writes performed in the SCoP.
   __isl_give isl_union_map *getMustWrites();

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/Analysis/ScalarEvolutionExpressions.h"
+
+#include "isl/ctx.h"
+
+struct isl_ctx;
+struct isl_map;
+struct isl_basic_map;
+struct isl_id;
+struct isl_set;
+struct isl_union_set;
+struct isl_union_map;
+struct isl_space;
+struct isl_ast_build;
+struct isl_constraint;
+struct isl_pw_aff;
+struct isl_schedule;
+
+namespace llvm {
+class Region;
+class ScalarEvolution;
+}
+
+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);
+
+  /// @brief Translate a SCEV to an isl_pw_aff.
+  ///
+  /// @param E    The expression that is translated.
+  /// @param Stmt The SCoP statment surrounding @p E.
+  __isl_give isl_pw_aff *getPwAff(const llvm::SCEV *E, const ScopStmt *Stmt);
+
+private:
+  Scop *S;
+  isl_ctx *Ctx;
+  unsigned NumIterators;
+  const llvm::Region &R;
+  llvm::ScalarEvolution &SE;
+
+  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);
+  __isl_give isl_pw_aff *visitAddExpr(const llvm::SCEVAddExpr *E);
+  __isl_give isl_pw_aff *visitMulExpr(const llvm::SCEVMulExpr *E);
+  __isl_give isl_pw_aff *visitUDivExpr(const llvm::SCEVUDivExpr *E);
+  __isl_give isl_pw_aff *visitAddRecExpr(const llvm::SCEVAddRecExpr *E);
+  __isl_give isl_pw_aff *visitSMaxExpr(const llvm::SCEVSMaxExpr *E);
+  __isl_give isl_pw_aff *visitUMaxExpr(const llvm::SCEVUMaxExpr *E);
+  __isl_give isl_pw_aff *visitUnknown(const llvm::SCEVUnknown *E);
+  __isl_give isl_pw_aff *visitSDivInstruction(llvm::Instruction *SDiv);
+  __isl_give isl_pw_aff *visitSRemInstruction(llvm::Instruction *SRem);
+
+  friend struct llvm::SCEVVisitor<SCEVAffinator, isl_pw_aff *>;
+};
+}
+
+#endif

polly/trunk/lib/Analysis/ScopInfo.cpp

combineInSequence(__isl_take isl_schedule *Prev,
   if (!Prev)
     return Succ;
   if (!Succ)
     return Prev;
 
   return isl_schedule_sequence(Prev, Succ);
 }
 
-/// Translate a 'const SCEV *' expression in an isl_pw_aff.
-struct SCEVAffinator : public SCEVVisitor<SCEVAffinator, isl_pw_aff *> {
-public:
-  /// @brief Translate a 'const SCEV *' to an isl_pw_aff.
-  ///
-  /// @param Stmt The location at which the scalar evolution expression
-  ///             is evaluated.
-  /// @param Expr The expression that is translated.
-  static __isl_give isl_pw_aff *getPwAff(ScopStmt *Stmt, const SCEV *Expr);
-
-private:
-  isl_ctx *Ctx;
-  int NbLoopSpaces;
-  const Scop *S;
-
-  SCEVAffinator(const ScopStmt *Stmt);
-  int getLoopDepth(const Loop *L);
-
-  __isl_give isl_pw_aff *visit(const SCEV *Expr);
-  __isl_give isl_pw_aff *visitConstant(const SCEVConstant *Expr);
-  __isl_give isl_pw_aff *visitTruncateExpr(const SCEVTruncateExpr *Expr);
-  __isl_give isl_pw_aff *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr);
-  __isl_give isl_pw_aff *visitSignExtendExpr(const SCEVSignExtendExpr *Expr);
-  __isl_give isl_pw_aff *visitAddExpr(const SCEVAddExpr *Expr);
-  __isl_give isl_pw_aff *visitMulExpr(const SCEVMulExpr *Expr);
-  __isl_give isl_pw_aff *visitUDivExpr(const SCEVUDivExpr *Expr);
-  __isl_give isl_pw_aff *visitAddRecExpr(const SCEVAddRecExpr *Expr);
-  __isl_give isl_pw_aff *visitSMaxExpr(const SCEVSMaxExpr *Expr);
-  __isl_give isl_pw_aff *visitUMaxExpr(const SCEVUMaxExpr *Expr);
-  __isl_give isl_pw_aff *visitUnknown(const SCEVUnknown *Expr);
-  __isl_give isl_pw_aff *visitSDivInstruction(Instruction *SDiv);
-  __isl_give isl_pw_aff *visitSRemInstruction(Instruction *SDiv);
-
-  friend struct SCEVVisitor<SCEVAffinator, isl_pw_aff *>;
-};
-
-SCEVAffinator::SCEVAffinator(const ScopStmt *Stmt)
-    : Ctx(Stmt->getIslCtx()), NbLoopSpaces(Stmt->getNumIterators()),
-      S(Stmt->getParent()) {}
-
-__isl_give isl_pw_aff *SCEVAffinator::getPwAff(ScopStmt *Stmt,
-                                               const SCEV *Scev) {
-  Scop *S = Stmt->getParent();
-  const Region *Reg = &S->getRegion();
-
-  S->addParams(getParamsInAffineExpr(Reg, Scev, *S->getSE()));
-
-  SCEVAffinator Affinator(Stmt);
-  return Affinator.visit(Scev);
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visit(const SCEV *Expr) {
-  // 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, NbLoopSpaces);
-    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);
-  }
-
-  return SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
-}
-
-__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
-  // this value needs to be converted to GMP. At the moment, we only support
-  // signed operations. So we just interpret it as signed. Later, there are
-  // two options:
-  //
-  // 1. We always interpret any value as signed and convert the values on
-  //    demand.
-  // 2. We pass down the signedness of the calculation and use it to interpret
-  //    this constant correctly.
-  v = isl_valFromAPInt(Ctx, Value->getValue(), /* isSigned */ true);
-
-  isl_space *Space = isl_space_set_alloc(Ctx, 0, NbLoopSpaces);
-  isl_local_space *ls = isl_local_space_from_space(Space);
-  return isl_pw_aff_from_aff(isl_aff_val_on_domain(ls, v));
-}
-
-__isl_give isl_pw_aff *
-SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
-  llvm_unreachable("SCEVTruncateExpr not yet supported");
-}
-
-__isl_give isl_pw_aff *
-SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
-  llvm_unreachable("SCEVZeroExtendExpr not yet supported");
-}
-
-__isl_give isl_pw_aff *
-SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
-  // Assuming the value is signed, a sign extension is basically a noop.
-  // TODO: Reconsider this as soon as we support unsigned values.
-  return visit(Expr->getOperand());
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
-  isl_pw_aff *Sum = visit(Expr->getOperand(0));
-
-  for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
-    isl_pw_aff *NextSummand = visit(Expr->getOperand(i));
-    Sum = isl_pw_aff_add(Sum, NextSummand);
-  }
-
-  // TODO: Check for NSW and NUW.
-
-  return Sum;
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) {
-  // Divide Expr into a constant part and the rest. Then visit both and multiply
-  // the result to obtain the representation for Expr. While the second part of
-  // ConstantAndLeftOverPair might still be a SCEVMulExpr we will not get to
-  // this point again. The reason is that if it is a multiplication it consists
-  // only of parameters and we will stop in the visit(const SCEV *) function and
-  // return the isl_pw_aff for that parameter.
-  auto ConstantAndLeftOverPair = extractConstantFactor(Expr, *S->getSE());
-  return isl_pw_aff_mul(visit(ConstantAndLeftOverPair.first),
-                        visit(ConstantAndLeftOverPair.second));
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
-  llvm_unreachable("SCEVUDivExpr not yet supported");
-}
-
-__isl_give isl_pw_aff *
-SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) {
-  assert(Expr->isAffine() && "Only affine AddRecurrences allowed");
-
-  auto Flags = Expr->getNoWrapFlags();
-
-  // Directly generate isl_pw_aff for Expr if 'start' is zero.
-  if (Expr->getStart()->isZero()) {
-    assert(S->getRegion().contains(Expr->getLoop()) &&
-           "Scop does not contain the loop referenced in this AddRec");
-
-    isl_pw_aff *Start = visit(Expr->getStart());
-    isl_pw_aff *Step = visit(Expr->getOperand(1));
-    isl_space *Space = isl_space_set_alloc(Ctx, 0, NbLoopSpaces);
-    isl_local_space *LocalSpace = isl_local_space_from_space(Space);
-
-    int loopDimension = getLoopDepth(Expr->getLoop());
-
-    isl_aff *LAff = isl_aff_set_coefficient_si(
-        isl_aff_zero_on_domain(LocalSpace), isl_dim_in, loopDimension, 1);
-    isl_pw_aff *LPwAff = isl_pw_aff_from_aff(LAff);
-
-    // TODO: Do we need to check for NSW and NUW?
-    return isl_pw_aff_add(Start, isl_pw_aff_mul(Step, LPwAff));
-  }
-
-  // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
-  // if 'start' is not zero.
-  // TODO: Using the original SCEV no-wrap flags is not always safe, however
-  //       as our code generation is reordering the expression anyway it doesn't
-  //       really matter.
-  ScalarEvolution &SE = *S->getSE();
-  const SCEV *ZeroStartExpr =
-      SE.getAddRecExpr(SE.getConstant(Expr->getStart()->getType(), 0),
-                       Expr->getStepRecurrence(SE), Expr->getLoop(), Flags);
-
-  isl_pw_aff *ZeroStartResult = visit(ZeroStartExpr);
-  isl_pw_aff *Start = visit(Expr->getStart());
-
-  return isl_pw_aff_add(ZeroStartResult, Start);
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
-  isl_pw_aff *Max = visit(Expr->getOperand(0));
-
-  for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
-    isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
-    Max = isl_pw_aff_max(Max, NextOperand);
-  }
-
-  return Max;
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
-  llvm_unreachable("SCEVUMaxExpr not yet supported");
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {
-  assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!");
-  auto *SE = S->getSE();
-
-  auto *Divisor = SDiv->getOperand(1);
-  auto *DivisorSCEV = SE->getSCEV(Divisor);
-  auto *DivisorPWA = visit(DivisorSCEV);
-  assert(isa<ConstantInt>(Divisor) &&
-         "SDiv is no parameter but has a non-constant RHS.");
-
-  auto *Dividend = SDiv->getOperand(0);
-  auto *DividendSCEV = SE->getSCEV(Dividend);
-  auto *DividendPWA = visit(DividendSCEV);
-  return isl_pw_aff_tdiv_q(DividendPWA, DivisorPWA);
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitSRemInstruction(Instruction *SRem) {
-  assert(SRem->getOpcode() == Instruction::SRem && "Assumed SRem instruction!");
-  auto *SE = S->getSE();
-
-  auto *Divisor = dyn_cast<ConstantInt>(SRem->getOperand(1));
-  assert(Divisor && "SRem is no parameter but has a non-constant RHS.");
-  auto *DivisorVal = isl_valFromAPInt(Ctx, Divisor->getValue(),
-                                      /* isSigned */ true);
-
-  auto *Dividend = SRem->getOperand(0);
-  auto *DividendSCEV = SE->getSCEV(Dividend);
-  auto *DividendPWA = visit(DividendSCEV);
-
-  return isl_pw_aff_mod_val(DividendPWA, isl_val_abs(DivisorVal));
-}
-
-__isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
-  if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
-    switch (I->getOpcode()) {
-    case Instruction::SDiv:
-      return visitSDivInstruction(I);
-    case Instruction::SRem:
-      return visitSRemInstruction(I);
-    default:
-      break; // Fall through.
-    }
-  }
-
-  llvm_unreachable(
-      "Unknowns SCEV was neither parameter nor a valid instruction.");
-}
-
-int SCEVAffinator::getLoopDepth(const Loop *L) {
-  Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
-  assert(outerLoop && "Scop does not contain this loop");
-  return L->getLoopDepth() - outerLoop->getLoopDepth();
-}
-
-/// @brief Add the bounds of @p Range to the set @p S for dimension @p dim.
 static __isl_give isl_set *addRangeBoundsToSet(__isl_take isl_set *S,
                                                const ConstantRange &Range,
                                                int dim,
                                                enum isl_dim_type type) {
   isl_val *V;
   isl_ctx *ctx = isl_set_get_ctx(S);
 
   bool useLowerUpperBound = Range.isSignWrappedSet() && !Range.isFullSet();
for (int i = 1, Size = Access.Subscripts.size(); i < Size; ++i) {
     isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space));
     isl_pw_aff *Var =
         isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i);
     isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS);
 
     isl_set *DimOutside;
 
     DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero);
-    isl_pw_aff *SizeE = SCEVAffinator::getPwAff(Statement, Access.Sizes[i - 1]);
+    isl_pw_aff *SizeE = Statement->getPwAff(Access.Sizes[i - 1]);
 
     SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0,
                                  Statement->getNumIterators());
     SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in,
                                 isl_space_dim(Space, isl_dim_set));
     SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in,
                                     isl_space_get_tuple_id(Space, isl_dim_set));
 

 __isl_give isl_map *MemoryAccess::foldAccess(const IRAccess &Access,
                                              __isl_take isl_map *AccessRelation,
                                              ScopStmt *Statement) {
   int Size = Access.Subscripts.size();
 
   for (int i = Size - 2; i >= 0; --i) {
     isl_space *Space;
     isl_map *MapOne, *MapTwo;
-    isl_pw_aff *DimSize = SCEVAffinator::getPwAff(Statement, Access.Sizes[i]);
+    isl_pw_aff *DimSize = Statement->getPwAff(Access.Sizes[i]);
 
     isl_space *SpaceSize = isl_pw_aff_get_space(DimSize);
     isl_pw_aff_free(DimSize);
     isl_id *ParamId = isl_space_get_dim_id(SpaceSize, isl_dim_param, 0);
 
     Space = isl_map_get_space(AccessRelation);
     Space = isl_space_map_from_set(isl_space_range(Space));
     Space = isl_space_align_params(Space, SpaceSize);
if (!Access.isAffine()) {
     computeBoundsOnAccessRelation(Access.getElemSizeInBytes());
     return;
   }
 
   isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
   AccessRelation = isl_map_universe(Space);
 
   for (int i = 0, Size = Access.Subscripts.size(); i < Size; ++i) {
-    isl_pw_aff *Affine =
-        SCEVAffinator::getPwAff(Statement, Access.Subscripts[i]);
+    isl_pw_aff *Affine = Statement->getPwAff(Access.Subscripts[i]);
 
     if (Size == 1) {
       // For the non delinearized arrays, divide the access function of the last
       // subscript by the size of the elements in the array.
       //
       // A stride one array access in C expressed as A[i] is expressed in
       // LLVM-IR as something like A[i * elementsize]. This hides the fact that
       // two subsequent values of 'i' index two values that are stored next to
isl_map *ScopStmt::getSchedule() const {
   }
   auto *M = isl_map_from_union_map(Schedule);
   M = isl_map_coalesce(M);
   M = isl_map_gist_domain(M, Domain);
   M = isl_map_coalesce(M);
   return M;
 }
 
+__isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *E) {
+  return getParent()->getPwAff(E, this);
+}
+
 void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
   assert(isl_set_is_subset(NewDomain, Domain) &&
          "New domain is not a subset of old domain!");
   isl_set_free(Domain);
   Domain = NewDomain;
 }
 
 // @brief Get the data-type of the elements accessed

 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
 }
 
 __isl_give isl_set *ScopStmt::buildConditionSet(const Comparison &Comp) {
-  isl_pw_aff *L = SCEVAffinator::getPwAff(this, Comp.getLHS());
-  isl_pw_aff *R = SCEVAffinator::getPwAff(this, Comp.getRHS());
+  isl_pw_aff *L = getPwAff(Comp.getLHS());
+  isl_pw_aff *R = getPwAff(Comp.getRHS());
 
   switch (Comp.getPred()) {
   case ICmpInst::ICMP_EQ:
     return isl_pw_aff_eq_set(L, R);
   case ICmpInst::ICMP_NE:
     return isl_pw_aff_ne_set(L, R);
   case ICmpInst::ICMP_SLT:
     return isl_pw_aff_lt_set(L, R);
for (int i = 0, e = getNumIterators(); i != e; ++i) {
 
     // 0 <= IV.
     isl_set *LowerBound = isl_pw_aff_nonneg_set(isl_pw_aff_copy(IV));
     Domain = isl_set_intersect(Domain, LowerBound);
 
     // IV <= LatchExecutions.
     const Loop *L = getLoopForDimension(i);
     const SCEV *LatchExecutions = SE->getBackedgeTakenCount(L);
-    isl_pw_aff *UpperBound = SCEVAffinator::getPwAff(this, LatchExecutions);
+    isl_pw_aff *UpperBound = getPwAff(LatchExecutions);
     isl_set *UpperBoundSet = isl_pw_aff_le_set(IV, UpperBound);
     Domain = isl_set_intersect(Domain, UpperBoundSet);
   }
 
   isl_local_space_free(LocalSpace);
   return Domain;
 }
 
while (auto ArrayTy = dyn_cast<ArrayType>(Ty)) {
     unsigned int Operand = 1 + Dimension;
 
     if (GEP->getNumOperands() <= Operand)
       break;
 
     const SCEV *Expr = SE.getSCEV(GEP->getOperand(Operand));
 
     if (isAffineExpr(&Parent.getRegion(), Expr, SE)) {
-      isl_pw_aff *AccessOffset = SCEVAffinator::getPwAff(this, Expr);
+      isl_pw_aff *AccessOffset = getPwAff(Expr);
       AccessOffset =
           isl_pw_aff_set_tuple_id(AccessOffset, isl_dim_in, getDomainId());
 
       isl_pw_aff *DimSize = isl_pw_aff_from_aff(isl_aff_val_on_domain(
           isl_local_space_copy(LSpace),
           isl_val_int_from_si(Ctx, ArrayTy->getNumElements())));
 
       isl_set *OutOfBound = isl_pw_aff_ge_set(AccessOffset, DimSize);
static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, isl_ctx *Context,
            unsigned MaxLoopDepth)
     : SE(&ScalarEvolution), R(R), IsOptimized(false),
-      MaxLoopDepth(MaxLoopDepth), IslCtx(Context) {}
+      MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this) {}
 
 void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI,
                             ScopDetection &SD) {
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
 
   // Build the iteration domain, access functions and schedule functions
void Scop::print(raw_ostream &OS) const {
   printAliasAssumptions(OS);
   printStatements(OS.indent(4));
 }
 
 void Scop::dump() const { print(dbgs()); }
 
 isl_ctx *Scop::getIslCtx() const { return IslCtx; }
 
+__isl_give isl_pw_aff *Scop::getPwAff(const SCEV *E, ScopStmt *Stmt) {
+  return Affinator.getPwAff(E, Stmt);
+}
+
 __isl_give isl_union_set *Scop::getDomains() const {
   isl_union_set *Domain = isl_union_set_empty(getParamSpace());
 
   for (const ScopStmt &Stmt : *this)
     Domain = isl_union_set_add_set(Domain, Stmt.getDomain());
 
   return Domain;
 }

polly/trunk/lib/CMakeLists.txt

add_polly_library(Polly
   ${ISL_CODEGEN_FILES}
   CodeGen/LoopGenerators.cpp
   CodeGen/IRBuilder.cpp
   CodeGen/Utils.cpp
   CodeGen/RuntimeDebugBuilder.cpp
   ${GPGPU_CODEGEN_FILES}
   Exchange/JSONExporter.cpp
   Support/GICHelper.cpp
+  Support/SCEVAffinator.cpp
   Support/SCEVValidator.cpp
   Support/RegisterPasses.cpp
   Support/ScopHelper.cpp
   Support/ScopLocation.cpp
   ${POLLY_JSON_FILES}
   Transform/Canonicalization.cpp
   Transform/CodePreparation.cpp
   Transform/DeadCodeElimination.cpp

polly/trunk/lib/Makefile

ISL_FILES= External/isl/basis_reduction_tab.c \
            External/isl/print.c \
            External/isl/imath/gmp_compat.c \
            External/isl/imath/imath.c \
            External/isl/imath/imrat.c
 
 SOURCES= Polly.cpp \
          Support/GICHelper.cpp \
          Support/SCEVValidator.cpp \
+         Support/SCEVAffinator.cpp \
          Support/RegisterPasses.cpp \
          Support/ScopHelper.cpp \
          Support/ScopLocation.cpp \
          Analysis/DependenceInfo.cpp \
          Analysis/ScopDetection.cpp \
          Analysis/ScopDetectionDiagnostic.cpp \
          Analysis/ScopInfo.cpp \
          Analysis/ScopGraphPrinter.cpp \

polly/trunk/lib/Support/SCEVAffinator.cpp

+//===--------- SCEVAffinator.cpp  - Create Scops from LLVM IR -------------===//
+//
+//                     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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/Support/SCEVAffinator.h"
+
+#include "polly/ScopInfo.h"
+#include "polly/Support/GICHelper.h"
+#include "polly/Support/ScopHelper.h"
+#include "polly/Support/SCEVValidator.h"
+
+#include "isl/aff.h"
+#include "isl/set.h"
+#include "isl/val.h"
+#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()) {}
+
+__isl_give isl_pw_aff *SCEVAffinator::getPwAff(const SCEV *Expr,
+                                               const ScopStmt *Stmt) {
+  NumIterators = Stmt->getNumIterators();
+
+  S->addParams(getParamsInAffineExpr(&R, Expr, SE));
+
+  return visit(Expr);
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visit(const SCEV *Expr) {
+  // 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);
+  }
+
+  return SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
+}
+
+__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
+  // this value needs to be converted to GMP. At the moment, we only support
+  // signed operations. So we just interpret it as signed. Later, there are
+  // two options:
+  //
+  // 1. We always interpret any value as signed and convert the values on
+  //    demand.
+  // 2. We pass down the signedness of the calculation and use it to interpret
+  //    this constant correctly.
+  v = isl_valFromAPInt(Ctx, Value->getValue(), /* isSigned */ true);
+
+  isl_space *Space = isl_space_set_alloc(Ctx, 0, NumIterators);
+  isl_local_space *ls = isl_local_space_from_space(Space);
+  return isl_pw_aff_from_aff(isl_aff_val_on_domain(ls, v));
+}
+
+__isl_give isl_pw_aff *
+SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
+  llvm_unreachable("SCEVTruncateExpr not yet supported");
+}
+
+__isl_give isl_pw_aff *
+SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+  llvm_unreachable("SCEVZeroExtendExpr not yet supported");
+}
+
+__isl_give isl_pw_aff *
+SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
+  // Assuming the value is signed, a sign extension is basically a noop.
+  // TODO: Reconsider this as soon as we support unsigned values.
+  return visit(Expr->getOperand());
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) {
+  isl_pw_aff *Sum = visit(Expr->getOperand(0));
+
+  for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
+    isl_pw_aff *NextSummand = visit(Expr->getOperand(i));
+    Sum = isl_pw_aff_add(Sum, NextSummand);
+  }
+
+  // TODO: Check for NSW and NUW.
+
+  return Sum;
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) {
+  // Divide Expr into a constant part and the rest. Then visit both and multiply
+  // the result to obtain the representation for Expr. While the second part of
+  // ConstantAndLeftOverPair might still be a SCEVMulExpr we will not get to
+  // this point again. The reason is that if it is a multiplication it consists
+  // only of parameters and we will stop in the visit(const SCEV *) function and
+  // return the isl_pw_aff for that parameter.
+  auto ConstantAndLeftOverPair = extractConstantFactor(Expr, *S->getSE());
+  return isl_pw_aff_mul(visit(ConstantAndLeftOverPair.first),
+                        visit(ConstantAndLeftOverPair.second));
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) {
+  llvm_unreachable("SCEVUDivExpr not yet supported");
+}
+
+__isl_give isl_pw_aff *
+SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) {
+  assert(Expr->isAffine() && "Only affine AddRecurrences allowed");
+
+  auto Flags = Expr->getNoWrapFlags();
+
+  // Directly generate isl_pw_aff for Expr if 'start' is zero.
+  if (Expr->getStart()->isZero()) {
+    assert(S->getRegion().contains(Expr->getLoop()) &&
+           "Scop does not contain the loop referenced in this AddRec");
+
+    isl_pw_aff *Start = visit(Expr->getStart());
+    isl_pw_aff *Step = visit(Expr->getOperand(1));
+    isl_space *Space = isl_space_set_alloc(Ctx, 0, NumIterators);
+    isl_local_space *LocalSpace = isl_local_space_from_space(Space);
+
+    int loopDimension = getLoopDepth(Expr->getLoop());
+
+    isl_aff *LAff = isl_aff_set_coefficient_si(
+        isl_aff_zero_on_domain(LocalSpace), isl_dim_in, loopDimension, 1);
+    isl_pw_aff *LPwAff = isl_pw_aff_from_aff(LAff);
+
+    // TODO: Do we need to check for NSW and NUW?
+    return isl_pw_aff_add(Start, isl_pw_aff_mul(Step, LPwAff));
+  }
+
+  // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}'
+  // if 'start' is not zero.
+  // TODO: Using the original SCEV no-wrap flags is not always safe, however
+  //       as our code generation is reordering the expression anyway it doesn't
+  //       really matter.
+  ScalarEvolution &SE = *S->getSE();
+  const SCEV *ZeroStartExpr =
+      SE.getAddRecExpr(SE.getConstant(Expr->getStart()->getType(), 0),
+                       Expr->getStepRecurrence(SE), Expr->getLoop(), Flags);
+
+  isl_pw_aff *ZeroStartResult = visit(ZeroStartExpr);
+  isl_pw_aff *Start = visit(Expr->getStart());
+
+  return isl_pw_aff_add(ZeroStartResult, Start);
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) {
+  isl_pw_aff *Max = visit(Expr->getOperand(0));
+
+  for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) {
+    isl_pw_aff *NextOperand = visit(Expr->getOperand(i));
+    Max = isl_pw_aff_max(Max, NextOperand);
+  }
+
+  return Max;
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) {
+  llvm_unreachable("SCEVUMaxExpr not yet supported");
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {
+  assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!");
+  auto *SE = S->getSE();
+
+  auto *Divisor = SDiv->getOperand(1);
+  auto *DivisorSCEV = SE->getSCEV(Divisor);
+  auto *DivisorPWA = visit(DivisorSCEV);
+  assert(isa<ConstantInt>(Divisor) &&
+         "SDiv is no parameter but has a non-constant RHS.");
+
+  auto *Dividend = SDiv->getOperand(0);
+  auto *DividendSCEV = SE->getSCEV(Dividend);
+  auto *DividendPWA = visit(DividendSCEV);
+  return isl_pw_aff_tdiv_q(DividendPWA, DivisorPWA);
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitSRemInstruction(Instruction *SRem) {
+  assert(SRem->getOpcode() == Instruction::SRem && "Assumed SRem instruction!");
+  auto *SE = S->getSE();
+
+  auto *Divisor = dyn_cast<ConstantInt>(SRem->getOperand(1));
+  assert(Divisor && "SRem is no parameter but has a non-constant RHS.");
+  auto *DivisorVal = isl_valFromAPInt(Ctx, Divisor->getValue(),
+                                      /* isSigned */ true);
+
+  auto *Dividend = SRem->getOperand(0);
+  auto *DividendSCEV = SE->getSCEV(Dividend);
+  auto *DividendPWA = visit(DividendSCEV);
+
+  return isl_pw_aff_mod_val(DividendPWA, isl_val_abs(DivisorVal));
+}
+
+__isl_give isl_pw_aff *SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) {
+  if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
+    switch (I->getOpcode()) {
+    case Instruction::SDiv:
+      return visitSDivInstruction(I);
+    case Instruction::SRem:
+      return visitSRemInstruction(I);
+    default:
+      break; // Fall through.
+    }
+  }
+
+  llvm_unreachable(
+      "Unknowns SCEV was neither parameter nor a valid instruction.");
+}
+
+int SCEVAffinator::getLoopDepth(const Loop *L) {
+  Loop *outerLoop = S->getRegion().outermostLoopInRegion(const_cast<Loop *>(L));
+  assert(outerLoop && "Scop does not contain this loop");
+  return L->getLoopDepth() - outerLoop->getLoopDepth();
+}