[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–97

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.

278

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

296

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

22

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.

32

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

6

Missing change.

[jdoerfert]

Some comments, new version is coming soon.

lib/Analysis/ScopInfo.cpp

94–97

Done.

108

is

addModuloSemantic

fine?

131

Done.

143

Done.

144

Done.

147

Done.

278

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.

296

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

32

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

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

9

i + 30

[jdoerfert]

some comments

lib/Analysis/ScopInfo.cpp

85

done.

94

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

9

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 indicate 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 *addModuloSemantic(__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::addModuloSemantic(isl_pw_aff *PWA, const SCEV *Expr,
+                                 SCEV::NoWrapFlags Flags) {
+  // If the SCEV flags do contain NSW (no signed wrap) then PWA already
+  // represents Expr in modulo semantic (it cannot overflow), thus we are done.
+  // Otherwise, we will compute:
+  //   PWA = ((PWA + 2^(n-1)) mod (2 ^ n)) - 2^(n-1)
+  // whereas n is the number of bits of the Expr, hence:
+  //   n = bitwidth(type(Expr))
+
+  if (Flags & SCEV::FlagNSW)
+    return PWA;
+
+  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 = addModuloSemantic(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 = addModuloSemantic(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");
 
   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));
+    isl_pw_aff *PWA = isl_pw_aff_add(Start, isl_pw_aff_mul(Step, LPwAff));
+
+    if (UseModulo)
+      PWA = addModuloSemantic(PWA, Expr, Flags);
+
+    return PWA;
   }
 
   // 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_pw_aff *PWA = isl_pw_aff_add(ZeroStartResult, Start);
+
+  if (UseModulo)
+    PWA = addModuloSemantic(PWA, Expr, Flags);
+
+  return PWA;
 }
 
 __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);
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));
 }
 

test/DependenceInfo/sequential_loops.ll

 exit.2:
   ret void
 }
 
 ; VALUE: region: 'S1 => exit.2' in function 'parametric_offset':
 ; VALUE:   RAW dependences:
 ; VALUE:     [p] -> {
 ; VALUE:       Stmt_S1[i0] -> Stmt_S2[-p + i0] :
-; VALUE:           p <= 190 and i0 >= p and i0 <= 9 + p and i0 >= 0 and i0 <= 99
+; VALUE:           p <= 190 and p >= -2305843009213693952 and i0 >= p and i0 <= 9 + p and i0 <= 99 and i0 >= 0
 ; VALUE:     }
 ; VALUE:   WAR dependences:
 ; VALUE:     [p] -> {
 ; VALUE:     }
 ; VALUE:   WAW dependences:
 ; VALUE:     [p] -> {
 ; VALUE:     }
 

test/Isl/Ast/aliasing_parametric_simple_2.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-code-generator=isl -polly-ast -analyze < %s | FileCheck %s
 ;
 ;    void jd(int *A, int *B, int c) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i] = B[c - 10] + B[5];
 ;    }
 ;
-; CHECK: if (1 && (&MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10] || &MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0]))
+; CHECK: if (c >= -2147483638 && (&MemRef_A[1024] <= &MemRef_B[c >= 15 ? 5 : c - 10] || &MemRef_B[c <= 15 ? 6 : c - 9] <= &MemRef_A[0]))
 ; CHECK:     for (int c0 = 0; c0 <= 1023; c0 += 1)
 ; CHECK:       Stmt_for_body(c0);
 ; CHECK: else
 ; CHECK:    /* original code */
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* %A, i32* %B, i32 %c) {

test/Isl/Ast/simple-run-time-condition.ll

 ;         A[i+p][j+q-100] = 1.0;
 ;
 
 ; This test case is meant to verify that the run-time condition generated
 ; for the delinearization is simplified such that conditions that would not
 ; cause any code to be executed are not generated.
 
 ; CHECK: if (
-; CHECK: (o >= 1 && q <= 0 && m + q >= 0)
+; CHECK: (o >= 1 && n + p <= 9223372036854775808 && q <= 0 && m + q >= 0)
 ; CHECK: ||
 ; CHECK; (o <= 0 && m + q >= 100 && q <= 100)
 ; CHECK: )
 
 ; CHECK:     if (o >= 1) {
 ; CHECK:       for (int c1 = 0; c1 < n; c1 += 1)
 ; CHECK:         for (int c2 = 0; c2 < m; c2 += 1)
 ; CHECK:           Stmt_for_j(c1, c2);

test/Isl/CodeGen/aliasing_parametric_simple_2.ll

 ; CHECK:  %[[M1:[._a-zA-Z0-9]*]] = icmp sle i64 %[[M0]], 15
 ; CHECK:  %[[M2:[._a-zA-Z0-9]*]] = sext i32 %c to i64
 ; CHECK:  %[[M3:[._a-zA-Z0-9]*]] = sub nsw i64 %[[M2]], 9
 ; CHECK:  %[[M4:[._a-zA-Z0-9]*]] = select i1 %[[M1]], i64 6, i64 %[[M3]]
 ; CHECK:  %[[BMax:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %B, i64 %[[M4]]
 ; CHECK:  %[[AMin:[._a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 0
 ; CHECK:  %[[BltA:[._a-zA-Z0-9]*]] = icmp ule i32* %[[BMax]], %[[AMin]]
 ; CHECK:  %[[NoAlias:[._a-zA-Z0-9]*]] = or i1 %[[AltB]], %[[BltA]]
-; CHECK:  %[[RTC:[._a-zA-Z0-9]*]] = and i1 true, %[[NoAlias]]
+; CHECK:  %[[RTC:[._a-zA-Z0-9]*]] = and i1 %{{[0-9]*}}, %[[NoAlias]]
 ; CHECK:  br i1 %[[RTC]], label %polly.start, label %for.cond
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* %A, i32* %B, i32 %c) {
 entry:
   br label %for.cond
 

test/Isl/CodeGen/pointer-type-expressions.ll

 ; CHECK: if (P <= -1) {
 ; CHECK:   for (int c0 = 0; c0 < N; c0 += 1)
 ; CHECK:     Stmt_store(c0);
 ; CHECK: } else if (P >= 1)
 ; CHECK:   for (int c0 = 0; c0 < N; c0 += 1)
 ; CHECK:     Stmt_store(c0);
 ; CHECK: }
 
-; CODEGEN:   %0 = bitcast float* %P to i8*
-; CODEGEN:   %1 = icmp ule i8* %0, inttoptr (i64 -1 to i8*)
+; CODEGEN:   %[[BC:[0-9]*]] = bitcast float* %P to i8*
+; CODEGEN:   icmp ule i8* %[[BC]], inttoptr (i64 -1 to i8*)
 

test/ScopInfo/assume_gep_bounds.ll

 ; 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] -> {  :
 ; CHECK-DAG:                    p <= 30
 ; CHECK-DAG:                     and
 ; CHECK-DAG:                    m <= 20
+; CHECK-DAG:                     and
+; CHECK-DAG:                    p <= 2305843009213694582 - 600n - 30m
 ; CHECK:                   }
 
 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
 

test/ScopInfo/assume_gep_bounds_2.ll

 
 ; This code is within bounds either if m and p are smaller than the array sizes,
 ; but also if only p is smaller than the size of the second B dimension and n
 ; is such that the first loop is never executed and consequently A is never
 ; accessed. In this case the value of m does not matter.
 
 ; CHECK: Assumed Context:
 ; CHECK-NEXT: [n, m, p] -> { :
-; CHECK-DAG:                   (n >= 1 and m <= 20 and p <= 20)
+; CHECK-DAG:                   (n >= 1 and m <= 2305843009213693972 - 20n and m <= 20 and p <= 20)
 ; CHECK-DAG:                    or
-; CHECK-DAG:                   (n <= 0 and p <= 20)
+; CHECK-DAG:                   (n <= 0 and p <= 2305843009213693972 - 20m and p <= 20 and p >= 1)
 ; CHECK:                   }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo([20 x float]* noalias %A, [20 x float]* noalias %B, i64 %n, i64 %m, i64 %p) {
 entry:
   br label %for.cond
 

test/ScopInfo/loop_carry.ll

bb:                                               ; preds = %bb, %bb.nph
   %5 = add nsw i64 %3, %4                         ; <i64> [#uses=1]
   %exitcond = icmp eq i64 %tmp6, %tmp             ; <i1> [#uses=1]
   br i1 %exitcond, label %bb2, label %bb
 
 bb2:                                              ; preds = %bb, %entry
   ret i64 0
 }
 
-; CHECK: Context:
-; CHECK: [n] -> { : }
 ; CHECK:     Statements {
 ; CHECK:      Stmt_bb_nph
 ; CHECK:             Domain :=
 ; CHECK:                 [n] -> { Stmt_bb_nph[] : n >= 2 };
 ; CHECK:             Scattering :=
 ; CHECK:                 [n] -> { Stmt_bb_nph[] -> [0, 0] };
 ; CHECK:             ReadAccess :=
 ; CHECK:                 [n] -> { Stmt_bb_nph[] -> MemRef_a[0] };

test/ScopInfo/multidim_2d_outer_parametric_offset.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze -polly-delinearize < %s | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, long p, double A[n][m]) {
 ;   for (long i = 0; i < 100; i++)
 ;     for (long j = 0; j < m; j++)
 ;       A[i+p][j] = 1.0;
 ; }
 
 ; CHECK:  Assumed Context:
-; CHECK:  [m, p] -> {  : }
+; CHECK:  [m, p] -> {  : p <= 9223372036854775708 }
 ; CHECK:  p0: %m
 ; CHECK:  p1: %p
 ; CHECK:  Statements {
 ; CHECK:    Stmt_for_j
 ; CHECK:          Domain :=
 ; CHECK:              [m, p] -> { Stmt_for_j[i0, i1] : i0 >= 0 and i0 <= 99 and i1 >= 0 and i1 <= -1 + m };
 ; CHECK:          Scattering :=
 ; CHECK:              [m, p] -> { Stmt_for_j[i0, i1] -> [i0, i1] };

test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll

 ;         A[i+p][j+q][k+r] = 1.0;
 ; }
 ;
 ; Access function:
 ;    {{{((8 * ((((%m * %p) + %q) * %o) + %r)) + %A),+,(8 * %m * %o)}<%for.i>,+,
 ;        (8 * %o)}<%for.j>,+,8}<%for.k>
 
 ; CHECK: Assumed Context:
-; CHECK: [n, m, o, p, q, r] -> { : (q <= 0 and q >= 1 - m and r <= -1 and r >= 1 - o) or (r = 0 and q <= 0 and q >= -m) or (r = -o and q <= 1 and q >= 1 - m) }
+; CHECK: [n, m, o, p, q, r] -> { :
+; CHECK-DAG:                       (p <= 9223372036854775808 - n and q <= 0 and q >= 1 - m and r <= -1 and r >= 1 - o)
+; CHECK-DAG:                        or
+; CHECK-DAG:                       (r = 0 and p <= 9223372036854775808 - n and q <= 0 and q >= -m)
+; CHECK-DAG:                        or
+; CHECK-DAG:                       (r = -o and p <= 9223372036854775808 - n and q <= 1 and q >= 1 - m)
+; CHECK:                       }
 ;
 ; CHECK: p0: %n
 ; CHECK: p1: %m
 ; CHECK: p2: %o
 ; CHECK: p3: %p
 ; CHECK: p4: %q
 ; CHECK: p5: %r
 ; CHECK-NOT: p6

test/ScopInfo/pointer-type-expressions.ll

entry:
   br label %bb
 
 bb:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %bb.backedge ]
   %brcond = icmp ne float* %P, null
   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/ranged_parameter.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
 ;
 ; Check that the contstraints on the paramater derived from the
 ; range metadata (see bottom of the file) are present:
 ;
 ; CHECK: Context:
-; CHECK:   [p_0] -> {  : p_0 >= 0 and p_0 <= 255 }
+; CHECK:   [p_0] -> {  :
+; CHECK-DAG:             p_0 >= 0
+; CHECK-DAG:              and
+; CHECK-DAG:             p_0 <= 255
+; CHECK:            }
 ;
 ;    void jd(int *A, int *p /* in [0,256) */) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i + *p] = i;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 

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_0.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 + 3] = 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 <= 125 }
+;
+;
+; FIXME: This is a negative test as nowrap should not need an assumed context.
+;        However %tmp5 in @nowrap is translated to the SCEV <3,+,1><nw><%bb2>
+;        which lacks the <nsw> flags we would need to avoid runtime checks.
+;
+; CHECK:      Function: nowrap
+; CHECK:      Assumed Context:
+; CHECK-NOT:  [N] -> {  :  }
+;
+target datalayout = "e-m:e-i8:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i32* %A, i8 %N, i8 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i8 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i8 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add i8 %indvars.iv, 3
+  %tmp6 = getelementptr i32, i32* %A, i8 %tmp5
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nsw nuw i8 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}
+
+define void @nowrap(i32* %A, i8 %N, i8 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i8 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i8 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add nsw nuw i8 %indvars.iv, 3
+  %tmp6 = getelementptr inbounds i32, i32* %A, i8 %tmp5
+  store i32 0, i32* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nsw nuw i8 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_1.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+;    void f(long *A, long N, long p) {
+;      for (long 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.
+;
+; Note:
+;       1152921504606846975 * sizeof(long) <= 2 ^ 63 - 1
+;  and
+;       1152921504606846976 * sizeof(long) >  2 ^ 63 - 1
+; with
+;       sizeof(long) == 8
+;
+; 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.
+;
+; Note: 2147483618 + 30 == 2 ^ 31
+;
+; 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 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;
+;    }
+;
+; Note: 2147483648 == 2 ^ 31
+;
+; 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 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(char *A, char N, char p) {
+;      for (char i = 0; i < N; i++)
+;        A[p-1] = 0;
+;    }
+;
+; CHECK:    Function: wrap
+; CHECK:    Context:
+; CHECK:        [N, p] -> {  : N <= 127 and N >= -128 and p <= 127 and p >= -128 }
+; CHECK:    Assumed Context:
+; CHECK:        [N, p] -> {  : p >= -127 }
+;
+target datalayout = "e-m:e-i8:64-f80:128-n8:16:32:64-S128"
+
+define void @wrap(i8* %A, i8 %N, i8 %p) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %indvars.iv = phi i8 [ %indvars.iv.next, %bb7 ], [ 0, %bb ]
+  %tmp3 = icmp slt i8 %indvars.iv, %N
+  br i1 %tmp3, label %bb4, label %bb8
+
+bb4:                                              ; preds = %bb2
+  %tmp5 = add i8 %p, -1
+  %tmp6 = getelementptr i8, i8* %A, i8 %tmp5
+  store i8 0, i8* %tmp6, align 4
+  br label %bb7
+
+bb7:                                              ; preds = %bb4
+  %indvars.iv.next = add nuw nsw i8 %indvars.iv, 1
+  br label %bb2
+
+bb8:                                              ; preds = %bb2
+  ret void
+}

test/ScopInfo/wraping_signed_expr_5.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+; We should not generate runtime check for ((int)r1 + (int)r2) as it is known not
+; to overflow. However (p + q) can, thus checks are needed.
+;
+; CHECK: Assumed Context:
+; CHECK:     [r1, r2, q, p] -> {  : p <= 2147483647 - q and p >= -2147483648 - q }
+;
+;    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
+}

test/ScopInfo/wraping_signed_expr_slow_1.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+; This checks that the no-wraps checks will be computed fast as some example
+; already showed huge slowdowns even though the inbounds and nsw flags were
+; all in place.
+;
+;    // Inspired by itrans8x8 in transform8x8.c from the ldecode benchmark.
+;    void fast(char *A, char N, char M) {
+;      for (char i = 0; i < 8; i++) {
+;        short index0 = (short)(i + N);
+;        #ifdef fast
+;          short index1 = (index0 *  1) + (short)M;
+;        #else
+;          short index1 = (index0 * 16) + (short)M;
+;        #endif
+;        A[index1]++;
+;      }
+;    }
+;
+; CHECK: Function: fast
+; CHECK: Function: slow
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @fast(i8* %A, i8 %N, i8 %M) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i8 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i8 %indvars.iv, 8
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp3 = add nsw i8 %indvars.iv, %N
+  %tmp3ext = sext i8 %tmp3 to i16
+  ;%mul = mul nsw i16 %tmp3ext, 16
+  %Mext = sext i8 %M to i16
+  %add2 = add nsw i16 %tmp3ext, %Mext
+  %arrayidx = getelementptr inbounds i8, i8* %A, i16 %add2
+  %tmp4 = load i8, i8* %arrayidx, align 4
+  %inc = add nsw i8 %tmp4, 1
+  store i8 %inc, i8* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i8 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @slow(i8* %A, i8 %N, i8 %M) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i8 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i8 %indvars.iv, 8
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp3 = add nsw i8 %indvars.iv, %N
+  %tmp3ext = sext i8 %tmp3 to i16
+  %mul = mul nsw i16 %tmp3ext, 16
+  %Mext = sext i8 %M to i16
+  %add2 = add nsw i16 %mul, %Mext
+  %arrayidx = getelementptr inbounds i8, i8* %A, i16 %add2
+  %tmp4 = load i8, i8* %arrayidx, align 4
+  %inc = add nsw i8 %tmp4, 1
+  store i8 %inc, i8* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i8 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/wraping_signed_expr_slow_2.ll

+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+;
+; This checks that the no-wraps checks will be computed fast as some example
+; already showed huge slowdowns even though the inbounds and nsw flags were
+; all in place.
+;
+;    // Inspired by itrans8x8 in transform8x8.c from the ldecode benchmark.
+;    void fast(char *A, char N, char M) {
+;      for (char i = 0; i < 8; i++) {
+;        char  index0 = i + N;
+;        char  index1 = index0 * 16;
+;        char  index2 = index1 + M;
+;        A[(short)index2]++;
+;      }
+;    }
+;
+;    void slow(char *A, char N, char M) {
+;      for (char i = 0; i < 8; i++) {
+;        char  index0 = i + N;
+;        char  index1 = index0 * 16;
+;        short index2 = ((short)index1) + ((short)M);
+;        A[index2]++;
+;      }
+;    }
+;
+; CHECK: Function: fast
+; CHECK: Function: slow
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @fast(i8* %A, i8 %N, i8 %M) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i8 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i8 %indvars.iv, 8
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp3 = add nsw i8 %indvars.iv, %N
+  %mul = mul nsw i8 %tmp3, 16
+  %add2 = add nsw i8 %mul, %M
+  %add2ext = sext i8 %add2 to i16
+  %arrayidx = getelementptr inbounds i8, i8* %A, i16 %add2ext
+  %tmp4 = load i8, i8* %arrayidx, align 4
+  %inc = add nsw i8 %tmp4, 1
+  store i8 %inc, i8* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i8 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+define void @slow(i8* %A, i8 %N, i8 %M) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i8 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i8 %indvars.iv, 8
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %tmp3 = add nsw i8 %indvars.iv, %N
+  %mul = mul nsw i8 %tmp3, 16
+  %mulext = sext i8 %mul to i16
+  %Mext = sext i8 %M to i16
+  %add2 = add nsw i16 %mulext, %Mext
+  %arrayidx = getelementptr inbounds i8, i8* %A, i16 %add2
+  %tmp4 = load i8, i8* %arrayidx, align 4
+  %inc = add nsw i8 %tmp4, 1
+  store i8 %inc, i8* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i8 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}