[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

indicate

108

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

UseModulo (start with uppercase)

143

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

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

144

Leftover.

147

Leftover.

268

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

281

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

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

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

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

test/ScopInfo/wraping_signed_expr_1_long.ll

21

char <> i64 mismatch

test/ScopInfo/wraping_signed_expr_5.ll

5

Missing change.

[jdoerfert]

Some comments, new version is coming soon.

lib/Analysis/ScopInfo.cpp

94

Done.

108

is

addModuloSemantic

fine?

131

Done.

143

Done.

144

Done.

147

Done.

268

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

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

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

semantics

94–97

semantics

145

"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

10

i + 30

[jdoerfert]

some comments

lib/Analysis/ScopInfo.cpp

85

done.

94–97

done.

145

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

10

done.

include/polly/ScopInfo.h

 class Type;
 }
 
 struct isl_ctx;
 struct isl_map;
 struct isl_basic_map;
 struct isl_id;
 struct isl_set;
+struct isl_pw_aff;
 struct isl_union_set;
 struct isl_union_map;
 struct isl_space;
 struct isl_ast_build;
 struct isl_constraint;
 struct isl_pw_multi_aff;
 
 namespace polly {
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 @p S.
+  ///
+  /// This will compute the isl representation for @p S and also restrict the
+  /// context of the SCoP accordingly if a computation in @p S could wrap.
+  __isl_give isl_pw_aff *getPwAff(const SCEV *S);
+
   /// @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();

lib/Analysis/ScopInfo.cpp

static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
     cl::desc("The maximal number of arrays to compare in each alias group."),
     cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
 
 /// 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);
+  /// @param Stmt      The location at which the scalar evolution expression
+  ///                  is evaluated.
+  /// @param Expr      The expression that is translated.
+  /// @param useModulo Flag to indicate that modulo semantic should be used.
+  static __isl_give isl_pw_aff *getPwAff(ScopStmt *Stmt, const SCEV *Expr,
+                                         bool useModulo = false);
 
 private:
   isl_ctx *Ctx;
   int NbLoopSpaces;
   const Scop *S;
 
-  SCEVAffinator(const ScopStmt *Stmt);
+  /// @brief Flag to inidicate that modulo semantic should be used.
+  const bool useModulo;
+
+  SCEVAffinator(const ScopStmt *Stmt, bool useModulo);
   int getLoopDepth(const Loop *L);
 
+  /// @brief Compute the non-wrapping version of @p PWA for the type of @p Expr.
+  ///
+  /// @param PWA   The piece-wise affine function that might wrap.
+  /// @param Expr  The SCEV that was translated to @p PWA.
+  /// @param Flags The nsw/nuw flags of the operation.
+  __isl_give isl_pw_aff *computeNonWrap(__isl_take isl_pw_aff *PWA,
+                                        const SCEV *Expr,
+                                        SCEV::NoWrapFlags Flags);
+
   __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);
 
   friend struct SCEVVisitor<SCEVAffinator, isl_pw_aff *>;
 };
 
-SCEVAffinator::SCEVAffinator(const ScopStmt *Stmt)
+SCEVAffinator::SCEVAffinator(const ScopStmt *Stmt, bool useModulo)
     : Ctx(Stmt->getIslCtx()), NbLoopSpaces(Stmt->getNumIterators()),
-      S(Stmt->getParent()) {}
+      S(Stmt->getParent()), useModulo(useModulo) {}
 
-__isl_give isl_pw_aff *SCEVAffinator::getPwAff(ScopStmt *Stmt,
-                                               const SCEV *Scev) {
+__isl_give isl_pw_aff *SCEVAffinator::getPwAff(ScopStmt *Stmt, const SCEV *Scev,
+                                               bool useModulo) {
   Scop *S = Stmt->getParent();
   const Region *Reg = &S->getRegion();
 
   S->addParams(getParamsInAffineExpr(Reg, Scev, *S->getSE()));
 
-  SCEVAffinator Affinator(Stmt);
+  SCEVAffinator Affinator(Stmt, useModulo);
   return Affinator.visit(Scev);
 }
 
+__isl_give isl_pw_aff *SCEVAffinator::computeNonWrap(isl_pw_aff *PWA,
+                                                     const SCEV *Expr,
+                                                     SCEV::NoWrapFlags Flags) {
+  Expr->dump();
+  if (Flags & SCEV::FlagNSW)
+    return PWA;
+  errs() << " No nsw!\n";
+
+  assert(Expr->getType()->isIntegerTy() && "SCEV did not have integer type");
+
+  unsigned Width = Expr->getType()->getIntegerBitWidth();
+  isl_ctx *Ctx = isl_pw_aff_get_ctx(PWA);
+
+  isl_set *Domain = isl_pw_aff_domain(isl_pw_aff_copy(PWA));
+
+  isl_val *ModVal = isl_val_int_from_ui(Ctx, Width);
+  ModVal = isl_val_2exp(ModVal);
+
+  isl_val *AddVal = isl_val_int_from_ui(Ctx, Width - 1);
+  AddVal = isl_val_2exp(AddVal);
+
+  isl_pw_aff *AddPW = isl_pw_aff_val_on_domain(Domain, AddVal);
+
+  PWA = isl_pw_aff_add(PWA, isl_pw_aff_copy(AddPW));
+  PWA = isl_pw_aff_mod_val(PWA, ModVal);
+  PWA = isl_pw_aff_sub(PWA, AddPW);
+
+  return PWA;
+}
+
 __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_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.
+  if (useModulo)
+    Sum = computeNonWrap(Sum, Expr, Expr->getNoWrapFlags());
 
   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),
+  isl_pw_aff *MulPWA = isl_pw_aff_mul(visit(ConstantAndLeftOverPair.first),
                                       visit(ConstantAndLeftOverPair.second));
+
+  if (useModulo)
+    MulPWA = computeNonWrap(MulPWA, Expr, Expr->getNoWrapFlags());
+
+  return MulPWA;
 }
 
 __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");
 
-  // 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);
+  isl_aff *LAff = isl_aff_set_coefficient_si(isl_aff_zero_on_domain(LocalSpace),
+                                             isl_dim_in, loopDimension, 1);
 
-    // 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.
-  ScalarEvolution &SE = *S->getSE();
-  const SCEV *ZeroStartExpr = SE.getAddRecExpr(
-      SE.getConstant(Expr->getStart()->getType(), 0),
-      Expr->getStepRecurrence(SE), Expr->getLoop(), SCEV::FlagAnyWrap);
+  isl_pw_aff *AddRecPWA = isl_pw_aff_add(Start, isl_pw_aff_mul(Step, LPwAff));
 
-  isl_pw_aff *ZeroStartResult = visit(ZeroStartExpr);
-  isl_pw_aff *Start = visit(Expr->getStart());
+  if (useModulo)
+    AddRecPWA = computeNonWrap(AddRecPWA, Expr, Expr->getNoWrapFlags());
 
-  return isl_pw_aff_add(ZeroStartResult, Start);
+  return AddRecPWA;
 }
 
 __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);

 /// @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 isWrapping = Range.isSignWrappedSet();
+  bool isWrapping = Range.isSignWrappedSet() && !Range.isFullSet();
   const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();
   V = isl_valFromAPInt(ctx, LB, true);
   isl_set *SLB = isl_set_lower_bound_val(isl_set_copy(S), type, dim, V);
 
   const auto UB = isWrapping ? Range.getUpper() : Range.getSignedMax();
   V = isl_valFromAPInt(ctx, UB, true);
   if (isWrapping)
     V = isl_val_sub_ui(V, 1);
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
void MemoryAccess::setNewAccessRelation(isl_map *newAccess) {
   isl_map_free(newAccessRelation);
   newAccessRelation = newAccess;
 }
 
 //===----------------------------------------------------------------------===//
 
 isl_map *ScopStmt::getScattering() const { return isl_map_copy(Scattering); }
 
+__isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *S) {
+  isl_pw_aff *Expr = SCEVAffinator::getPwAff(this, S, false);
+  isl_pw_aff *ModExpr = SCEVAffinator::getPwAff(this, S, true);
+
+  isl_set *Domain = isl_set_reset_tuple_id(getDomain());
+  isl_pw_aff *DomExpr =
+      isl_pw_aff_intersect_domain(isl_pw_aff_copy(Expr), isl_set_copy(Domain));
+  isl_pw_aff *DomModExpr = isl_pw_aff_intersect_domain(ModExpr, Domain);
+
+  isl_set *NonWrappingDom = isl_pw_aff_ne_set(DomExpr, DomModExpr);
+  NonWrappingDom = isl_set_params(NonWrappingDom);
+  NonWrappingDom = isl_set_complement(NonWrappingDom);
+
+  getParent()->addAssumption(NonWrappingDom);
+
+  return Expr;
+}
+
 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;
   Scattering = isl_map_intersect_domain(Scattering, isl_set_copy(Domain));
 }
 

 }
 
 void Scop::addParameterBounds() {
   for (const auto &ParamID : ParameterIds) {
     int dim = ParamID.second;
 
     ConstantRange SRange = SE->getSignedRange(ParamID.first);
 
-    // TODO: Find a case where the full set is actually helpful.
-    if (SRange.isFullSet())
-      continue;
-
     Context = addRangeBoundsToSet(Context, SRange, dim, isl_dim_param);
   }
 }
 
 void Scop::realignParams() {
   // Add all parameters into a common model.
   isl_space *Space = isl_space_params_alloc(IslCtx, ParameterIds.size());
 

test/ScopInfo/assume_gep_bounds.ll

 ; bounds of the array A. In C (and LLVM-IR) this is not required, such that out
 ; of bounds accesses are valid. However, as such accesses are uncommon, cause
 ; complicated dependence pattern and as a result make dependence analysis more
 ; costly and may prevent or hinder useful program transformations, we assume
 ; absence of out-of-bound accesses. To do so we derive the set of parameter
 ; values for which our assumption holds.
 
 ; CHECK: Assumed Context
-; CHECK-NEXT: [n, m, p] -> {  : p <= 30 and m <= 20 }
+; CHECK-NEXT: [n, m, p] -> {  : p <= 30 and m <= 20 and p <= 2305843009213694582 - 600n - 30m }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo([20 x [30 x float]]* %A, i64 %n, i64 %m, i64 %p) {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc13, %entry

test/ScopInfo/simple_loop_1.ll

 target triple = "x86_64-unknown-linux-gnu"
 
 define void @f(i64* nocapture %a, i64 %N) nounwind {
 entry:
   br label %bb
 
 bb:                                               ; preds = %bb, %entry
   %i = phi i64 [ 0, %entry ], [ %i.inc, %bb ]
-  %scevgep = getelementptr i64, i64* %a, i64 %i
+  %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
   store i64 %i, i64* %scevgep
   %i.inc = add nsw i64 %i, 1
   %exitcond = icmp eq i64 %i.inc, %N
   br i1 %exitcond, label %return, label %bb
 
 return:                                           ; preds = %bb, %entry
   ret void
 }

test/ScopInfo/unsigned-condition.ll

entry:
   br label %bb
 
 bb:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %bb.backedge ]
   %brcond = icmp uge i64 %P, 42
   br i1 %brcond, label %store, label %bb.backedge
 
 store:
-  %scevgep = getelementptr i64, i64* %a, i64 %i
+  %scevgep = getelementptr inbounds i64, i64* %a, i64 %i
   store i64 %i, i64* %scevgep
   br label %bb.backedge
 
 bb.backedge:
   %i.inc = add nsw i64 %i, 1
   %exitcond = icmp eq i64 %i.inc, %N
   br i1 %exitcond, label %return, label %bb
 

test/ScopInfo/wraping_signed_expr_1.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+;    void f(int *A, char N, char p) {
+;      for (char i = 0; i < N; i++)
+;        A[i + 1] = 0;
+;    }
+;
+; The wrap function has no inbounds GEP but the nowrap function has. Therefore,
+; we will add the assumption that i+1 won't overflow only to the former.
+;
+; CHECK:      Function: wrap
+; CHECK:      Assumed Context:
+; CHECK:      [N] -> {  : N <= 2305843009213693951 }
+;
+; CHECK:      Function: nowrap
+; CHECK:      Assumed Context:
+; CHECK:      [N] -> {  :  }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i32* %A, i64 %N, i64 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw nuw i64 %indvars.iv, 1
+  %tmp6 = getelementptr i32, i32* %A, i64 %tmp5
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nsw nuw i64 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}
+
+define void @nowrap(i32* %A, i64 %N, i64 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw nuw i64 %indvars.iv, 1
+  %tmp6 = getelementptr inbounds i32, i32* %A, i64 %tmp5
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nsw nuw i64 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_1_long.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+;    void f(long *A, char N, char p) {
+;      for (char i = 0; i < N; i++)
+;        A[i + 1] = 0;
+;    }
+;
+; The wrap function has no inbounds GEP but the nowrap function has. Therefore,
+; we will add the assumption that i+1 won't overflow only to the former.
+;
+; CHECK:      Function: wrap
+; CHECK:      Assumed Context:
+; CHECK:      [N] -> {  : N <= 1152921504606846975 }
+;
+; CHECK:      Function: nowrap
+; CHECK:      Assumed Context:
+; CHECK:      [N] -> {  :  }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i64* %A, i64 %N, i64 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw nuw i64 %indvars.iv, 1
+  %tmp6 = getelementptr i64, i64* %A, i64 %tmp5
+  store i64 0, i64* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nsw nuw i64 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}
+
+define void @nowrap(i64* %A, i64 %N, i64 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw nuw i64 %indvars.iv, 1
+  %tmp6 = getelementptr inbounds i64, i64* %A, i64 %tmp5
+  store i64 0, i64* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nsw nuw i64 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_2.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+;    void f(int *A, int N, int p) {
+;      for (int i = 0; i < N; i++)
+;        A[i + 30] = 0;
+;    }
+;
+; The wrap function has no inbounds GEP but the nowrap function has. Therefore,
+; we will add the assumption that i+1 won't overflow only to the former.
+;
+; CHECK:      Function: wrap
+; CHECK:      Context:
+; CHECK:        [N] -> {  : N <= 2147483647 and N >= -2147483648 }
+; CHECK:      Assumed Context:
+; CHECK:        [N] -> {  : N <= 2147483618 }
+;
+target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i32* %A, i32 %N, i32 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i32 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i32 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw i32 %indvars.iv, 30
+  %tmp6 = getelementptr i32, i32* %A, i32 %tmp5
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_3.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+;    void f(int *A, int N, int p) {
+;      for (int i = 0; i < N; i++)
+;        A[i + p] = 0;
+;    }
+;
+; CHECK:      Function: wrap
+; CHECK:      Assumed Context:
+; CHECK:      [N, p] -> {  : p <= 2147483648 - N }
+;
+target datalayout = "e-m:e-i32:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i32* %A, i32 %N, i32 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i32 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i32 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw i32 %indvars.iv, %p
+  %tmp6 = getelementptr inbounds i32, i32* %A, i32 %tmp5
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_4.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+;    void f(int *A, int N, int p) {
+;      for (int i = 0; i < N; i++)
+;        A[p-1] = 0;
+;    }
+;
+; CHECK:    Function: wrap
+; CHECK:    Assumed Context:
+; CHECK:    [N, p] -> {  : 
+; CHECK-DAG: p >= -1152921504606846975
+; CHECK-DAG: p <= 1152921504606846976
+; CHECK:              }
+;
+target datalayout = "e-m:e-i8:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i64* %A, i64 %N, i64 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i64 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add i64 %p, -1
+  %tmp6 = getelementptr i64, i64* %A, i64 %tmp5
+  store i64 0, i64* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_5.ll

+; RUN: opt %loadPolly -analyze < %s | FileCheck %s
+;
+; FIXME: Edit the run line and add checks!
+;
+; XFAIL: *
+;
+;    void wraps(int *A, int p, short q, char r1, char r2) {
+;      for (char i = r1; i < r2; i++)
+;        A[p + q] = A[(int)r1 + (int)r2];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @wraps(i32* %A, i32 %p, i16 signext %q, i8 signext %r1, i8 signext %r2) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i8 [ %r1, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i8 %i.0, %r2
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %conv3 = sext i8 %r1 to i64
+  %conv4 = sext i8 %r2 to i64
+  %add = add nsw i64 %conv3, %conv4
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %add
+  %tmp = load i32, i32* %arrayidx, align 4
+  %conv5 = sext i16 %q to i32
+  %add6 = add nsw i32 %conv5, %p
+  %idxprom7 = sext i32 %add6 to i64
+  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %idxprom7
+  store i32 %tmp, i32* %arrayidx8, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add i8 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}