Use modulo semantic to generate non-integer-overflow assumptions

[jdoerfert]

Summary

This will allow to generate non-wrap assumptions for integer expressions
that are part of the SCoP. We compare the common isl representation of
the expression with one computed with modulo semantic. For all parameter
combinations they are not equal we can have integer overflows.
  
The nsw flags are respected when the modulo representation is computed,
nuw and nw flags are ignored for now.
  
In order to not increase compile time to much, the non-wrap assumptions
are collected in a separate boundary context instead of the assumed
context. This helps compile time as the boundary context can become
complex and it is therefor not advised to use it in other operations
except runtime check generation. However, the assumed context is e.g.,
used to tighten dependences. While the boundary context might help to
tighten the assumed context it is doubtful that it will help in practice
(it does not effect lnt much) as the boundary (or no-wrap assumptions)
only restrict the very end of the possible value range of parameters.

[grosser]

I did not had a detailed look yet, but wondered what the LNT results for
this patch looked like? Did this pass all tests and did we see a compile
time impact?

Tobias

[jdoerfert]

In D11977#222725, @grosser wrote:

I did not had a detailed look yet, but wondered what the LNT results for
this patch looked like? Did this pass all tests and did we see a compile
time impact?

It should pass all lnt tests but I'll run lnt on this version again tonight.

The compile time impact is severe for <5 tests and "ok" for the rest. Most tests do not show worse compile time actually. However, I am still working on some simplifications that will reduce compile time as well as some exit conditions that we can place in order to bail out before we spend to much time on a benchmark.

[Meinersbur]

include/polly/Support/SCEVAffinator.h

72

Too many spaces?

85

Why the empty line 85 between @brief and @param ?

lib/Support/SCEVAffinator.cpp

118

__isl_take isl_pw_aff *PWA

[jdoerfert]

Separated assumed and boundary context and minimized the compile time overhead

[jdoerfert]

Fixed small issues raised by Michael

[grosser]

jdoerfert updated this revision to Diff 32136.
jdoerfert added a comment.

Separated assumed and boundary context and minimized the compile time overhead

Hi Johannes,

can you give more details on the current compile-time overhead? Maybe an LNT result
page, or the top-5 offenders?

Best,
Tobias

[llvm-commits]

Attached 2 json files, without_overflow_assumptions.json
and with_overflow_assumptions.json. The former is a recent upstream
commit with (I think) 4 lnt runs, the latter the current integer
wrapping patch applied to the upstream head with 2 lnt runs.

We have 5 benchmarks that have more than 15% compile time regression:

; regress ; prev   ; Current;   σ

MultiSource/Applications/SIBsim4/SIBsim4 ; 136.24% ; 2.5200 ; 5.9533 ; 0.2801
MultiSource/Benchmarks/ASC_Sequoia/IRSmk/IRSmk ; 21.86% ; 0.5334 ; 0.6500 ; 0.0016
SingleSource/Regression/C++/2003-05-14-expr_stmt ; 16.67% ; 0.1200 ; 0.1400 ; -
MultiSource/Applications/oggenc/oggenc ; 16.34% ; 7.0400 ; 8.1900 ; 0.2633
SingleSource/Regression/C++/EH/dead_try_block ; 15.38% ; 0.1300 ; 0.1500 ; 0.0016

Also the execution time regressed by more than 15% a few times:

                                                                           ;    Δ   ; Previous;  Current;   σ
SingleSource/Benchmarks/Polybench/stencils/fdtd-apml/fdtd-apml             ; 50.00% ; 0.3400  ; 0.5100  ; 0.0016
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/trisolv/trisolv   ; 35.27% ; 0.0567  ; 0.0767  ; -     
SingleSource/Benchmarks/Shootout-C++/strcat                                ; 33.33% ; 0.0300  ; 0.0400  ; -     
MultiSource/Benchmarks/Olden/treeadd/treeadd                               ; 24.01% ; 0.0833  ; 0.1033  ; 0.0050
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/bicg/bicg         ; 22.22% ; 0.0900  ; 0.1100  ; 0.0016
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/symm/symm         ; 19.73% ; 12.7233 ; 15.2333 ; 0.2967
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/cholesky/cholesky ; 18.05% ; 0.4433  ; 0.5233  ; 0.0050
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/gesummv/gesummv   ; 16.70% ; 0.1000  ; 0.1167  ; 0.0016

However I am not sure how much, especially of the runtime results, is
real or only some noise.

All in all I think this is as good as it gets for now.

• msg-3916-965.dat219 BDownload
• msg-3916-966.txt162 BDownload

[jdoerfert]

This time with attachments.

• msg-16021-79.dat219 BDownload
• without_overflow_assumptions.json729 KBDownload
• with_overflow_assumptions.json366 KBDownload

[grosser]

Hi Johannes,

I found one test case where modulo wrapping happens and where Polly currently, but also with your patch, produces incorrect results:

void __attribute__ ((noinline)) foo(float *A, long N) {
  for (long i = 0; i < N; i++)
    if ((signed char)i < 100)
      A[i] += i;
}

test-wrapping-in-condition.c370 BDownload

Compiled with polly-clang test-wrapping-in-condition.c -O3 -mllvm -polly -mllvm -polly-no-early-exit Polly derives the domain:

[ N ] -> { Stmt_if_then[i0] : i0 >= 0 and i0 <= -1 + N and N >= 1 and i0 <= 99 };

and only runs the first 99 iterations. Without Polly, we run 1000 iterations, but only for those where "i" casted to char is smaller than 99 the values of A are actually updated.

With your patch the BoundaryContext is empty, Should your patch not have a constraint N <= 128 in the BoundaryContext to prevent this miscompilation?

[jdoerfert]

Fixed the problem pointed out by Tobias and added his test case.

[grosser]

Hi Johannes,

some first comments. I still need to understand the algorithm better, but probably just wait to read the writeup in the gitlab document.

include/polly/ScopInfo.h

852

measure

include/polly/Support/SCEVAffinator.h

69

happening

lib/Analysis/ScopInfo.cpp

1295

Is this valid? We are simplifying our assumption context here with the parameter constraints coming from the domain which was generated assuming the assumptions
hold. Is this not another <-> loophole? If it is not, maybe a comment would help that explains why this is correct.

2016

Maybe put this into a separate function with a comment what you are actually doing.

Also, why are you intersecting with getContext() the second time. This adds context constraints to the BoundaryContext which we know hold (and which will likely be dropped in simplifyContext().

2130

This simplification is again fishy as we use the already simplified domain to simplify
the assumptions that were used to simplify the domain.

lib/Support/SCEVAffinator.cpp

80

It seems worth describing what you are actually computing here. Also, it is unclear to me why intersecting here with the domain is save. Are you relying on the domain not
being fully built?

82

It seems you only add modulo wrapping at the very end, but not right when we construct the expressions. This makes the impression you only add modulo wrapping at the outermost level. I think you already replied that the inner levels will also be in
the cache and consequently we will actually have all the wrappings. If this is the case,
we probably want to add a comment.

[jdoerfert]

Updated version. Depends on D12499.

[jdoerfert]

Commited in r247732.

include/polly/ScopInfo.h

private:
   ///
   /// When constructing a scop sometimes the exact representation of a statement
   /// or condition would be very complex, but there is a common case which is a
   /// lot simpler, but which is only valid under certain assumptions. The
   /// assumed context records the assumptions taken during the construction of
   /// this scop and that need to be code generated as a run-time test.
   isl_set *AssumedContext;
 
+  /// @brief The boundary assumptions under which this scop was built.
+  ///
+  /// The boundary context is similar to the assumed context as it contains
+  /// constraints over the parameters we assume to be true. However, the
+  /// boundary context is less useful for dependence analysis and
+  /// simplification purposes as it contains only constraints that affect the
+  /// boundaries of the parameter ranges. As these constraints can become quite
+  /// complex, the boundary context and the assumed context are separated as a
+  /// meassure to save compile time.
+  isl_set *BoundaryContext;
+
   /// @brief The schedule of the SCoP
   ///
   /// The schedule of the SCoP describes the execution order of the statements
   /// in the scop by assigning each statement instance a possibly
   /// multi-dimensional execution time. The schedule is stored as a tree of
   /// schedule nodes.
   ///
   /// The most common nodes in a schedule tree are so-called band nodes. Band
private:
   static bool isTrivialBB(BasicBlock *BB, TempScop &tempScop);
 
   /// @brief Add parameter constraints to @p C that imply a non-empty domain.
   __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
 
   /// @brief Build the Context of the Scop.
   void buildContext();
 
+  /// @brief Build the BoundaryContext based on the wrapping of expressions.
+  void buildBoundaryContext();
+
   /// @brief Add user provided parameter constraints to context.
   void addUserContext();
 
   /// @brief Add the bounds of the parameters to the context.
   void addParameterBounds();
 
-  /// @brief Simplify the assumed context.
-  void simplifyAssumedContext();
+  /// @brief Simplify the assumed and boundary context.
+  void simplifyContexts();
 
   /// @brief Create a new SCoP statement for either @p BB or @p R.
   ///
   /// Either @p BB or @p R should be non-null. A new statement for the non-null
   /// argument will be created and added to the statement vector and map.
   ///
   /// @param BB         The basic block we build the statement for (or null)
   /// @param R          The region we build the statement for (or null).
public:
   /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
   ///          that assumptions do not change the set of statement instances
   ///          executed.
   ///
   /// @param Set A set describing relations between parameters that are assumed
   ///            to hold.
   void addAssumption(__isl_take isl_set *Set);
 
+  /// @brief Get the boundary context for this Scop.
+  ///
+  /// @return The boundary context of this Scop.
+  __isl_give isl_set *getBoundaryContext() const;
+
+  /// @brief Get the runtime context for this Scop.
+  ///
+  /// The runtime context is the intersection of the assumed and the boundary
+  /// context. It is used in the AST generation to build the runtime checks that
+  /// are used to decide if the optimized or original version of the SCoP will
+  /// be exectued.
+  ///
+  /// @return The runtime context of this Scop.
+  __isl_give isl_set *getRuntimeContext() const;
+
   /// @brief Build the alias checks for this SCoP.
   void buildAliasChecks(AliasAnalysis &AA);
 
   /// @brief Build all alias groups for this SCoP.
   ///
   /// @returns True if __no__ error occurred, false otherwise.
   bool buildAliasGroups(AliasAnalysis &AA);
 
   /// @brief Return all alias groups for this SCoP.
   const MinMaxVectorPairVectorTy &getAliasGroups() const {
     return MinMaxAliasGroups;
   }
 
   /// @brief Get an isl string representing the context.
   std::string getContextStr() const;
 
   /// @brief Get an isl string representing the assumed context.
   std::string getAssumedContextStr() const;
 
+  /// @brief Get an isl string representing the boundary context.
+  std::string getBoundaryContextStr() const;
+
   /// @brief Return the stmt for the given @p BB or nullptr if none.
   ScopStmt *getStmtForBasicBlock(BasicBlock *BB) const;
 
   /// @brief Return the number of statements in the SCoP.
   size_t getSize() const { return Stmts.size(); }
 
   /// @name Statements Iterators
   ///
public:
   /// @return The isl context of this static control part.
   isl_ctx *getIslCtx() const;
 
   /// @brief Compute the isl representation for the SCEV @p
   ///
   /// @param Domain An (optional) domain in which the isl_pw_aff is computed.
   ///               SCEVs known to not reference any loops in the SCoP can be
   ///               passed without a @p Domain.
-  __isl_give isl_pw_aff *getPwAff(const SCEV *E,
-                                  __isl_keep isl_set *Domain = nullptr);
+  __isl_give isl_pw_aff *getPwAff(const SCEV *E, BasicBlock *BB = nullptr);
 
   /// @brief Return the non-loop carried conditions on the domain of @p Stmt.
   ///
   /// @param Stmt The statement for which the conditions should be returned.
   __isl_give isl_set *getDomainConditions(ScopStmt *Stmt);
 
+  /// @brief Return the non-loop carried conditions on the domain of @p BB.
+  ///
+  /// @param BB The block for which the conditions should be returned.
+  __isl_give isl_set *getDomainConditions(BasicBlock *BB);
+
   /// @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();

include/polly/Support/SCEVAffinator.h

 struct isl_space;
 struct isl_ast_build;
 struct isl_constraint;
 struct isl_pw_aff;
 struct isl_schedule;
 
 namespace llvm {
 class Region;
+class BasicBlock;
+class DataLayout;
 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);
   ~SCEVAffinator();
 
   /// @brief Translate a SCEV to an isl_pw_aff.
   ///
-  /// @param E      The expression that is translated.
-  /// @param Domain The domain in which @p E is executed.
+  /// @param E  he expression that is translated.
+  /// @param BB The block in which @p E is executed.
   ///
   /// @returns The isl representation of the SCEV @p E in @p Domain.
   __isl_give isl_pw_aff *getPwAff(const llvm::SCEV *E,
-                                  __isl_keep isl_set *Domain = nullptr);
+                                  llvm::BasicBlock *BB = nullptr);
+
+  /// @brief Compute the context in which integer wrapping is happending.
+  ///
+  /// This context contains all parameter configurations for which we
+  /// know that the wrapping and non-wrapping expressions are different.
+  ///
+  /// @returns The context in which integer wrapping is happening.
+  __isl_give isl_set *getWrappingContext() const;
 
 private:
   /// @brief Key to identify cached expressions.
-  using CacheKey = std::pair<const llvm::SCEV *, isl_set *>;
+  using CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>;
 
   /// @brief Map to remembered cached expressions.
   llvm::DenseMap<CacheKey, isl_pw_aff *> CachedExpressions;
 
   Scop *S;
   isl_ctx *Ctx;
   unsigned NumIterators;
   const llvm::Region &R;
   llvm::ScalarEvolution &SE;
-  isl_set *Domain;
+  llvm::BasicBlock *BB;
+
+  /// @brief Target data for element size computing.
+  const llvm::DataLayout &TD;
+
+  /// @brief Compute the non-wrapping version of @p PWA for type @p ExprType.
+  ///
+  /// @param PWA  The piece-wise affine function that might wrap.
+  /// @param Type The type of the SCEV that was translated to @p PWA.
+  ///
+  /// @returns The expr @p PWA modulo the size constraints of @p ExprType.
+  __isl_give isl_pw_aff *addModuloSemantic(__isl_take isl_pw_aff *PWA,
+                                           llvm::Type *ExprType) const;
+
+  /// @brief Compute the context in which integer wrapping for @p PWA happens.
+  ///
+  /// @returns The context in which integer wrapping happens or nullptr if
+  /// empty.
+  __isl_give isl_set *getWrappingContext(llvm::SCEV::NoWrapFlags Flags,
+                                         llvm::Type *ExprType,
+                                         __isl_keep isl_pw_aff *PWA,
+                                         __isl_keep isl_set *ExprDomain) const;
+
+  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);

lib/Analysis/ScopInfo.cpp

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, Domain);
+  return getParent()->getPwAff(E, isBlockStmt() ? getBasicBlock()
+                                                : getRegion()->getEntry());
 }
 
 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;
 }
if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
     else
       ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
   } else {
     auto *ICond = dyn_cast<ICmpInst>(Condition);
     assert(ICond &&
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
+    BasicBlock *BB = BI->getParent();
     isl_pw_aff *LHS, *RHS;
-    LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), Domain);
-    RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), Domain);
+    LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB);
+    RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB);
     ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), LHS, RHS);
   }
 
   assert(ConsequenceCondSet);
   isl_set *AlternativeCondSet =
       isl_set_complement(isl_set_copy(ConsequenceCondSet));
 
   ConditionSets.push_back(isl_set_coalesce(
return isl_id_alloc(getIslCtx(), ParameterName.c_str(),
                       const_cast<void *>((const void *)Parameter));
 }
 
 isl_set *Scop::addNonEmptyDomainConstraints(isl_set *C) const {
   isl_set *DomainContext = isl_union_set_params(getDomains());
   return isl_set_intersect_params(C, DomainContext);
 }
 
+void Scop::buildBoundaryContext() {
+  BoundaryContext = Affinator.getWrappingContext();
+  BoundaryContext = isl_set_complement(BoundaryContext);
+  BoundaryContext = isl_set_gist_params(BoundaryContext, getContext());
+}
+
 void Scop::addUserContext() {
   if (UserContextStr.empty())
     return;
 
   isl_set *UserContext = isl_set_read_from_str(IslCtx, UserContextStr.c_str());
   isl_space *Space = getParamSpace();
   if (isl_space_dim(Space, isl_dim_param) !=
       isl_set_dim(UserContext, isl_dim_param)) {
void Scop::realignParams() {
 
   // Align the parameters of all data structures to the model.
   Context = isl_set_align_params(Context, Space);
 
   for (ScopStmt &Stmt : *this)
     Stmt.realignParams();
 }
 
-void Scop::simplifyAssumedContext() {
+static __isl_give isl_set *
+simplifyAssumptionContext(__isl_take isl_set *AssumptionContext,
+                          const Scop &S) {
+  isl_set *DomainParameters = isl_union_set_params(S.getDomains());
+  AssumptionContext = isl_set_gist_params(AssumptionContext, DomainParameters);
+  AssumptionContext = isl_set_gist_params(AssumptionContext, S.getContext());
+  return AssumptionContext;
+}
+
+void Scop::simplifyContexts() {
   // The parameter constraints of the iteration domains give us a set of
   // constraints that need to hold for all cases where at least a single
   // statement iteration is executed in the whole scop. We now simplify the
   // assumed context under the assumption that such constraints hold and at
   // least a single statement iteration is executed. For cases where no
   // statement instances are executed, the assumptions we have taken about
   // the executed code do not matter and can be changed.
   //
void Scop::simplifyContexts() {
   //
   //     for (long i = 0; i < 100; i++)
   //       for (long j = 0; j < m; j++)
   //         A[i+p][j] = 1.0;
   //
   //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
   //   otherwise we would access out of bound data. Now, knowing that code is
   //   only executed for the case m >= 0, it is sufficient to assume p >= 0.
-  AssumedContext =
-      isl_set_gist_params(AssumedContext, isl_union_set_params(getDomains()));
-  AssumedContext = isl_set_gist_params(AssumedContext, getContext());
+  AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
+  BoundaryContext = simplifyAssumptionContext(BoundaryContext, *this);
 }
 
 /// @brief Add the minimal/maximal access in @p Set to @p User.
 static isl_stat buildMinMaxAccess(__isl_take isl_set *Set, void *User) {
   Scop::MinMaxVectorTy *MinMaxAccesses = (Scop::MinMaxVectorTy *)User;
   isl_pw_multi_aff *MinPMA, *MaxPMA;
   isl_pw_aff *LastDimAff;
   isl_aff *OneAff;
createFirstIterationDomain(__isl_take isl_space *Space, int Dim) {
   if (Dim >= 0)
     Domain = isl_set_fix_si(Domain, isl_dim_set, Dim, 0);
   return Domain;
 }
 
 isl_set *Scop::getDomainConditions(ScopStmt *Stmt) {
   BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock()
                                        : Stmt->getRegion()->getEntry();
+  return getDomainConditions(BB);
+}
+
+isl_set *Scop::getDomainConditions(BasicBlock *BB) {
+  assert(DomainMap.count(BB) && "Requested BB did not have a domain");
   return isl_set_copy(DomainMap[BB]);
 }
 
 void Scop::buildDomains(Region *R, LoopInfo &LI, ScopDetection &SD,
                         DominatorTree &DT) {
 
   auto *EntryBB = R->getEntry();
   int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB));
if (RN->isSubRegion()) {
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
         buildDomainsWithBranchConstraints(SubRegion, LI, SD, DT);
         continue;
       }
     }
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     isl_set *Domain = DomainMap[BB];
-    DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
+    DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : ";
+          isl_set_dump(Domain));
     assert(Domain && "Due to reverse post order traversal of the region all "
                      "predecessor of the current region node should have been "
                      "visited and a domain for this region node should have "
                      "been set.");
 
     Loop *BBLoop = getRegionNodeLoop(RN, LI);
     int BBLoopDepth = getRelativeLoopDepth(BBLoop);
 
for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
       // successor block.
       isl_set *&SuccDomain = DomainMap[SuccBB];
       if (!SuccDomain)
         SuccDomain = CondSet;
       else
         SuccDomain = isl_set_union(SuccDomain, CondSet);
 
       SuccDomain = isl_set_coalesce(SuccDomain);
-      DEBUG(dbgs() << "\tSet SuccBB: " << SuccBB->getName() << " : " << Domain
-                   << "\n");
+      DEBUG(dbgs() << "\tSet SuccBB: " << SuccBB->getName() << " : ";
+            isl_set_dump(SuccDomain));
     }
   }
 }
 
 static __isl_give isl_set *
 getDomainForBlock(BasicBlock *BB, DenseMap<BasicBlock *, isl_set *> &DomainMap,
                   RegionInfo &RI) {
   auto DIt = DomainMap.find(BB);
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, DominatorTree &DT,
            isl_ctx *Context, unsigned MaxLoopDepth)
     : DT(DT), SE(&ScalarEvolution), R(R), IsOptimized(false),
-      MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this) {}
+      MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this),
+      BoundaryContext(nullptr) {}
 
 void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
                             AliasAnalysis &AA) {
   buildContext();
 
   buildDomains(&R, LI, SD, DT);
 
   SmallVector<Loop *, 8> NestLoops;
 
   // Build the iteration domain, access functions and schedule functions
   // traversing the region tree.
   Schedule = buildScop(TempScop, getRegion(), NestLoops, LI, SD);
   if (!Schedule)
     Schedule = isl_schedule_empty(getParamSpace());
 
   realignParams();
   addParameterBounds();
   addUserContext();
-  simplifyAssumedContext();
+  buildBoundaryContext();
+  simplifyContexts();
   buildAliasChecks(AA);
 
   assert(NestLoops.empty() && "NestLoops not empty at top level!");
 }
 
 Scop *Scop::createFromTempScop(TempScop &TempScop, LoopInfo &LI,
                                ScalarEvolution &SE, ScopDetection &SD,
                                AliasAnalysis &AA, DominatorTree &DT,
                                isl_ctx *ctx) {
   auto &R = TempScop.getMaxRegion();
   auto MaxLoopDepth = getMaxLoopDepthInRegion(R, LI, SD);
   auto S = new Scop(R, SE, DT, ctx, MaxLoopDepth);
   S->initFromTempScop(TempScop, LI, SD, AA);
 
   return S;
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
+  isl_set_free(BoundaryContext);
   isl_schedule_free(Schedule);
 
   for (auto It : DomainMap)
     isl_set_free(It.second);
 
   // Free the alias groups
   for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
     for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, bool IsPHI) {
   assert(SAI && "No ScopArrayInfo available for this base pointer");
   return SAI;
 }
 
 std::string Scop::getContextStr() const { return stringFromIslObj(Context); }
 std::string Scop::getAssumedContextStr() const {
   return stringFromIslObj(AssumedContext);
 }
+std::string Scop::getBoundaryContextStr() const {
+  return stringFromIslObj(BoundaryContext);
+}
 
 std::string Scop::getNameStr() const {
   std::string ExitName, EntryName;
   raw_string_ostream ExitStr(ExitName);
   raw_string_ostream EntryStr(EntryName);
 
   R.getEntry()->printAsOperand(EntryStr, false);
   EntryStr.str();
bool Scop::hasFeasibleRuntimeContext() const {
   return IsFeasible;
 }
 
 void Scop::addAssumption(__isl_take isl_set *Set) {
   AssumedContext = isl_set_intersect(AssumedContext, Set);
   AssumedContext = isl_set_coalesce(AssumedContext);
 }
 
+__isl_give isl_set *Scop::getBoundaryContext() const {
+  return isl_set_copy(BoundaryContext);
+}
+
+__isl_give isl_set *Scop::getRuntimeContext() const {
+  isl_set *RTContext = getAssumedContext();
+  RTContext = isl_set_intersect(RTContext, getBoundaryContext());
+  RTContext = simplifyAssumptionContext(RTContext, *this);
+  return RTContext;
+}
+
 void Scop::printContext(raw_ostream &OS) const {
   OS << "Context:\n";
 
   if (!Context) {
     OS.indent(4) << "n/a\n\n";
     return;
   }
 
   OS.indent(4) << getContextStr() << "\n";
 
   OS.indent(4) << "Assumed Context:\n";
   if (!AssumedContext) {
     OS.indent(4) << "n/a\n\n";
     return;
   }
 
   OS.indent(4) << getAssumedContextStr() << "\n";
 
+  OS.indent(4) << "Boundary Context:\n";
+  if (!BoundaryContext) {
+    OS.indent(4) << "n/a\n\n";
+    return;
+  }
+
+  OS.indent(4) << getBoundaryContextStr() << "\n";
+
   for (const SCEV *Parameter : Parameters) {
     int Dim = ParameterIds.find(Parameter)->second;
     OS.indent(4) << "p" << Dim << ": " << *Parameter << "\n";
   }
 }
 
 void Scop::printAliasAssumptions(raw_ostream &OS) const {
   int noOfGroups = 0;
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, isl_set *Domain) {
-  return Affinator.getPwAff(E, Domain);
+__isl_give isl_pw_aff *Scop::getPwAff(const SCEV *E, BasicBlock *BB) {
+  return Affinator.getPwAff(E, BB);
 }
 
 __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());
 

lib/Support/SCEVAffinator.cpp

 #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()) {}
+    : S(S), Ctx(S->getIslCtx()), R(S->getRegion()), SE(*S->getSE()),
+      TD(R.getEntry()->getParent()->getParent()->getDataLayout()) {}
 
 SCEVAffinator::~SCEVAffinator() {
-  for (const auto &CachedPair : CachedExpressions) {
+  for (const auto &CachedPair : CachedExpressions)
     isl_pw_aff_free(CachedPair.second);
-    isl_set_free(CachedPair.first.second);
-  }
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::getPwAff(const SCEV *Expr,
-                                               isl_set *Domain) {
-  this->Domain = Domain;
+                                               BasicBlock *BB) {
+  this->BB = BB;
 
-  if (Domain)
-    NumIterators = isl_set_n_dim(Domain);
-  else
+  if (BB) {
+    auto *DC = S->getDomainConditions(BB);
+    NumIterators = isl_set_n_dim(DC);
+    isl_set_free(DC);
+  } else
     NumIterators = 0;
 
   S->addParams(getParamsInAffineExpr(&R, Expr, SE));
 
   return visit(Expr);
 }
 
+__isl_give isl_set *
+SCEVAffinator::getWrappingContext(SCEV::NoWrapFlags Flags, Type *ExprType,
+                                  __isl_keep isl_pw_aff *PWA,
+                                  __isl_take isl_set *ExprDomain) const {
+  // If the SCEV flags do contain NSW (no signed wrap) then PWA already
+  // represents Expr in modulo semantic (it is not allowed to 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(ExprType)
+
+  if (Flags & SCEV::FlagNSW)
+    return nullptr;
+
+  isl_pw_aff *PWAMod = addModuloSemantic(isl_pw_aff_copy(PWA), ExprType);
+  if (isl_pw_aff_is_equal(PWA, PWAMod)) {
+    isl_pw_aff_free(PWAMod);
+    return nullptr;
+  }
+
+  PWA = isl_pw_aff_copy(PWA);
+
+  if (ExprDomain) {
+    isl_set_dump(ExprDomain);
+    ExprDomain = isl_set_reset_tuple_id(isl_set_copy(ExprDomain));
+    isl_pw_aff_dump(PWA);
+    isl_pw_aff_dump(PWAMod);
+    PWA = isl_pw_aff_intersect_domain(PWA, isl_set_copy(ExprDomain));
+    PWAMod = isl_pw_aff_intersect_domain(PWAMod, ExprDomain);
+  }
+
+  auto *NotEqualSet = isl_pw_aff_ne_set(PWA, PWAMod);
+  NotEqualSet = isl_set_gist_params(NotEqualSet, S->getContext());
+  NotEqualSet = isl_set_params(NotEqualSet);
+  return NotEqualSet;
+}
+
+__isl_give isl_set *SCEVAffinator::getWrappingContext() const {
+
+  isl_set *WrappingCtx = isl_set_empty(S->getParamSpace());
+
+  for (const auto &CachedPair : CachedExpressions) {
+    const SCEV *Expr = CachedPair.first.first;
+    SCEV::NoWrapFlags Flags;
+
+    switch (Expr->getSCEVType()) {
+    case scAddExpr:
+      Flags = cast<SCEVAddExpr>(Expr)->getNoWrapFlags();
+      break;
+    case scMulExpr:
+      Flags = cast<SCEVMulExpr>(Expr)->getNoWrapFlags();
+      break;
+    case scAddRecExpr:
+      Flags = cast<SCEVAddRecExpr>(Expr)->getNoWrapFlags();
+      break;
+    default:
+      continue;
+    }
+
+    isl_pw_aff *PWA = CachedPair.second;
+    BasicBlock *BB = CachedPair.first.second;
+    isl_set *ExprDomain = BB ? S->getDomainConditions(BB) : nullptr;
+
+    isl_set *WPWACtx =
+        getWrappingContext(Flags, Expr->getType(), PWA, ExprDomain);
+    isl_set_free(ExprDomain);
+
+    WrappingCtx = WPWACtx ? isl_set_union(WrappingCtx, WPWACtx) : WrappingCtx;
+  }
+
+  return WrappingCtx;
+}
+
+__isl_give isl_pw_aff *
+SCEVAffinator::addModuloSemantic(__isl_take isl_pw_aff *PWA,
+                                 Type *ExprType) const {
+  unsigned Width = TD.getTypeStoreSizeInBits(ExprType);
+  isl_ctx *Ctx = isl_pw_aff_get_ctx(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_set *Domain = isl_pw_aff_domain(isl_pw_aff_copy(PWA));
+
+  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) {
 
-  auto Key = std::make_pair(Expr, isl_set_copy(Domain));
+  auto Key = std::make_pair(Expr, BB);
   isl_pw_aff *PWA = CachedExpressions[Key];
   if (PWA) {
-    isl_set_free(Domain);
     return isl_pw_aff_copy(PWA);
   }
 
   // In case the scev is a valid parameter, we do not further analyze this
   // expression, but create a new parameter in the isl_pw_aff. This allows us
   // to treat subexpressions that we cannot translate into an piecewise affine
   // expression, as constant parameters of the piecewise affine expression.
   if (isl_id *Id = S->getIdForParam(Expr)) {
     isl_space *Space = isl_space_set_alloc(Ctx, 1, NumIterators);
     Space = isl_space_set_dim_id(Space, isl_dim_param, 0, Id);
 
     isl_set *Domain = isl_set_universe(isl_space_copy(Space));
     isl_aff *Affine = isl_aff_zero_on_domain(isl_local_space_from_space(Space));
     Affine = isl_aff_add_coefficient_si(Affine, isl_dim_param, 0, 1);
 
     PWA = isl_pw_aff_alloc(Domain, Affine);
     CachedExpressions[Key] = PWA;
     return isl_pw_aff_copy(PWA);
   }
 
   PWA = SCEVVisitor<SCEVAffinator, isl_pw_aff *>::visit(Expr);
+
+  // For compile time reasons we need to simplify the PWA before we cache and
+  // return it.
+  PWA = isl_pw_aff_coalesce(PWA);
+
   CachedExpressions[Key] = PWA;
   return isl_pw_aff_copy(PWA);
 }
 
 __isl_give isl_pw_aff *SCEVAffinator::visitConstant(const SCEVConstant *Expr) {
   ConstantInt *Value = Expr->getValue();
   isl_val *v;
 

 __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
if (Expr->getStart()->isZero()) {
     isl_local_space *LocalSpace = isl_local_space_from_space(Space);
 
     unsigned loopDimension = S->getRelativeLoopDepth(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_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.

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:           i0 >= 0 and i0 <= 9 + p and i0 >= p and i0 <= 99 and p <= 190
+; VALUE-DAG:           p <= 190
+; VALUE-DAG:           i0 >= p
+; VALUE-DAG:           i0 <= 9 + p
+; VALUE-DAG:           i0 <= 99
+; VALUE-DAG:           i0 >= 0
 ; VALUE:     }
 ; VALUE:   WAR dependences:
 ; VALUE:     [p] -> {
 ; VALUE:     }
 ; VALUE:   WAW dependences:
 ; VALUE:     [p] -> {
 ; VALUE:     }
 

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

exit:
   ret void
 }
 
 ; CHECK: for (int c0 = 0; c0 < -start + end; c0 += 1)
 ; CHECK:   Stmt_body(c0);
 
 ; Check that we transform this into a pointer difference.
 
-; CODEGEN: %0 = ptrtoint i8* %end to i64
-; CODEGEN: %1 = ptrtoint i8* %start to i64
-; CODEGEN: %2 = sub i64 %0, %1
+; CODEGEN: %[[r0:[._a-zA-Z0-9]]] = ptrtoint i8* %end to i64
+; CODEGEN: %[[r1:[._a-zA-Z0-9]]] = ptrtoint i8* %start to i64
+; CODEGEN: %[[r2:[._a-zA-Z0-9]]] = sub i64 %[[r0]], %[[r1]]
 

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:   %[[R0:[0-9]*]] = bitcast float* %P to i8*
+; CODEGEN:   %[[R1:[0-9]*]] = bitcast float* %P to i8*
+; CODEGEN-NEXT:   icmp ule i8* %[[R1]], inttoptr (i64 -1 to i8*)
 

test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll

 ; innermost loop as a SCoP of depth 1, we can overapproximate the
 ; innermost loop in the whole loop nest and model A[k] as a non-affine
 ; access.
 ;
 ; INNERMOST:    Function: f
 ; INNERMOST:    Region: %bb15---%bb26
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    Context:
-; INNERMOST:      [p_0, p_1, p_2] -> {  : p_0 >= 0 and p_0 <= 2147483647 and p_1 >= 0 and p_1 <= 4096 and p_2 >= 0 and p_2 <= 4096 }
+; INNERMOST:      [p_0, p_1, p_2] -> {  :
+; INNERMOST-DAG:    p_0 >= 0
+; INNERMOST-DAG:      and
+; INNERMOST-DAG:    p_0 <= 2147483647
+; INNERMOST-DAG:      and
+; INNERMOST-DAG:    p_1 >= 0
+; INNERMOST-DAG:      and
+; INNERMOST-DAG:     p_1 <= 4096
+; INNERMOST-DAG:      and
+; INNERMOST-DAG:    p_2 >= 0
+; INNERMOST-DAG:      and
+; INNERMOST-DAG:     p_2 <= 4096
+; INNERMOST:                         }
 ; INNERMOST:    Assumed Context:
 ; INNERMOST:      [p_0, p_1, p_2] -> {  :  }
 ; INNERMOST:    p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
 ; INNERMOST:    p1: {0,+,4}<nuw><nsw><%bb11>
 ; INNERMOST:    p2: {0,+,4}<nuw><nsw><%bb13>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {

test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll

 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=true -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine \
 ; RUN:     -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \
 ; RUN:     -polly-detect-unprofitable -analyze < %s | FileCheck %s \
 ; RUN:     --check-prefix=ALL
 ;
 ; INNERMOST:    Function: f
 ; INNERMOST:    Region: %bb9---%bb17
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    Context:
-; INNERMOST:    [N] -> {  : N >= -2147483648 and N <= 2147483647 }
+; INNERMOST:    [N] -> {  :
+; INNERMOST-DAG:          N >= -2147483648
+; INNERMOST-DAG:       and
+; INNERMOST-DAG:          N <= 2147483647
+; INNERMOST            }
 ; INNERMOST:    Assumed Context:
 ; INNERMOST:    [N] -> {  :  }
 ; INNERMOST:    p0: %N
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb11
 ; INNERMOST:            Domain :=

test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll

 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine-branches \
 ; RUN:     -polly-allow-nonaffine-loops=true -polly-detect-unprofitable \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=INNERMOST
 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine \
 ; RUN:     -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops=true \
 ; RUN:     -analyze < %s | FileCheck %s --check-prefix=ALL
 ;
 ; INNERMOST:    Function: f
 ; INNERMOST:    Region: %bb9---%bb18
 ; INNERMOST:    Max Loop Depth:  1
 ; INNERMOST:    Context:
-; INNERMOST:    [p_0] -> {  : p_0 >= -2199023255552 and p_0 <= 2199023254528 }
+; INNERMOST:    [p_0] -> {  :
+; INNERMOST-DAG:   p_0 >= -2199023255552
+; INNERMOST-DAG:    and 
+; INNERMOST-DAG:   p_0 <= 2199023254528
+; INNERMOST:             }
 ; INNERMOST:    Assumed Context:
 ; INNERMOST:    [p_0] -> {  :  }
 ; INNERMOST:    p0: {0,+,(sext i32 %N to i64)}<%bb3>
 ; INNERMOST:    Alias Groups (0):
 ; INNERMOST:        n/a
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb12
 ; INNERMOST:            Domain :=

test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

 ; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine -polly-allow-nonaffine-branches -polly-allow-nonaffine-loops -analyze < %s | FileCheck %s
 ;
 ; Verify that we over approximate the read acces of A[j] in the last statement as j is
 ; computed in a non-affine loop we do not model.
 ;
 ; CHECK:    Function: f
 ; CHECK:    Region: %bb2---%bb24
 ; CHECK:    Max Loop Depth:  1
 ; CHECK:    Context:
-; CHECK:    [N] -> {  : N >= -2147483648 and N <= 2147483647 }
+; CHECK:    [N] -> {  :
+; CHECK-DAG:         N >= -2147483648
+; CHECK-DAG:       and
+; CHECK-DAG:         N <= 2147483647
+; CHECK:           }
 ; CHECK:    Assumed Context:
 ; CHECK:    [N] -> {  :  }
 ; CHECK:    p0: %N
 ; CHECK:    Alias Groups (0):
 ; CHECK:        n/a
 ; CHECK:    Statements {
 ; CHECK:      Stmt_bb2
 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0__phi[] };

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-NEXT: [n, m, p] -> {  : (n <= 0 and p <= 20) or (n >= 1 and m <= 20 and p <= 20) }
+; CHECK: Boundary Context:
+; CHECK-NEXT: [n, m, p] -> {  :
+; CHECK-DAG:                   (n <= 0 and m >= 115292150460684699 and p <= 0)
 ; CHECK-DAG:                    or
-; CHECK-DAG:                   (n <= 0 and p <= 20)
+; CHECK-DAG:                   (n >= 1 and m <= 2305843009213693972 - 20n and m >= 115292150460684699 and p <= 0)
+; CHECK-DAG:                    or
+; CHECK-DAG:                   (m <= 2305843009213693972 - 20n and m <= 115292150460684698 and p <= 2305843009213693972 - 20m)
 ; 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
 ; CHECK:             Domain :=
 ; CHECK:                 [n] -> { Stmt_bb[i0] : i0 >= 0 and i0 <= -2 + n };
 ; CHECK:             Schedule :=
 ; CHECK:                 [n] -> { Stmt_bb[i0] -> [i0] };
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                 [n] -> { Stmt_bb[i0] -> MemRef_1__phi[] };

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"
 
 ; 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] :
 ; CHECK-DAG:             i0 >= 0
 ; CHECK-DAG:          and

test/ScopInfo/multidim_srem.ll

 ; RUN: opt %loadPolly -analyze -polly-scops -S < %s | FileCheck %s
 ;
 ;    void foo(long n, float A[][n][n]) {
 ;      for (long i = 0; i < 200; i++)
 ;        for (long j = 0; j < n; j++)
 ;          for (long k = 0; k < n; k++)
 ;            A[i % 2][j][k] += 10;
 ;    }
 ;
 ; CHECK: ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
-; CHECK:     [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 <= 1 and o0 >= 0) };
+; CHECK:     [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2):
+; CHECK-DAG:    2e0 = -i0 + o0
+; CHECK-DAG:  and
+; CHECK-DAG:    o0 <= 1
+; CHECK-DAG:  and
+; CHECK-DAG:    o0 >= 0
+; CHECK:      };
 ; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
-; CHECK:     [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2): 2e0 = -i0 + o0 and o0 <= 1 and o0 >= 0) };
+; CHECK:     [n] -> { Stmt_for_body_8[i0, i1, i2] -> MemRef_A[o0, i1, i2] : exists (e0 = floor((-i0 + o0)/2):
+; CHECK-DAG:    2e0 = -i0 + o0
+; CHECK-DAG:  and
+; CHECK-DAG:    o0 <= 1
+; CHECK-DAG:  and
+; CHECK-DAG:    o0 >= 0
+; CHECK:      };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 
 define void @foo(i64 %n, float* %A) #0 {
 entry:
   br label %entry.split
 

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

 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
 
 ; void f(int a[], int N) {
 ;   int i;
 ;   for (i = 0; i < N; ++i)
 ;     a[i] = i;
 ; }
 
 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"
 
 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/test-wrapping-in-condition.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK:    Boundary Context:
+; CHECK:        [N] -> {  : N <= 128 }
+;
+;    #include <stdlib.h>
+;    #include <stdio.h>
+;
+;    void __attribute__((noinline)) foo(float *A, long N) {
+;      for (long i = 0; i < N; i++)
+;        if ((signed char)i < 100)
+;          A[i] += i;
+;    }
+define void @foo(float* %A, i64 %N) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
+  %tmp = icmp slt i64 %i.0, %N
+  br i1 %tmp, label %bb2, label %bb13
+
+bb2:                                              ; preds = %bb1
+  %tmp3 = trunc i64 %i.0 to i8
+  %tmp4 = icmp slt i8 %tmp3, 100
+  br i1 %tmp4, label %bb5, label %bb10
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = sitofp i64 %i.0 to float
+  %tmp7 = getelementptr inbounds float, float* %A, i64 %i.0
+  %tmp8 = load float, float* %tmp7, align 4
+  %tmp9 = fadd float %tmp8, %tmp6
+  store float %tmp9, float* %tmp7, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb5, %bb2
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  %tmp12 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb13:                                             ; preds = %bb1
+  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:      Boundary 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:      Boundary 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:      Boundary Context:
+; CHECK:      [N] -> {  : N <= 1152921504606846975 }
+;
+; CHECK:      Function: nowrap
+; CHECK:      Boundary 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:      Boundary 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:      Boundary 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:    Boundary 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:     Boundary Context:
+; CHECK:     [r1, r2, q, p] -> {
+; CHECK-DAG:      p <= 2147483647 - q
+; CHECK-DAG:        and
+; CHECK-DAG:      p >= -2147483648 - q
+; CHECK:     }
+;
+;    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_6.ll

+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK:    Boundary Context:
+; CHECK:        [N] -> {  : N <= 128 }
+;
+;    void foo(float *A, long N) {
+;      for (long i = 0; i < N; i++)
+;        if ((signed char)i < 100)
+;          A[i] += i;
+;    }
+define void @foo(float* %A, i64 %N) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
+  %tmp = icmp slt i64 %i.0, %N
+  br i1 %tmp, label %bb2, label %bb13
+
+bb2:                                              ; preds = %bb1
+  %tmp3 = trunc i64 %i.0 to i8
+  %tmp4 = icmp slt i8 %tmp3, 100
+  br i1 %tmp4, label %bb5, label %bb10
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = sitofp i64 %i.0 to float
+  %tmp7 = getelementptr inbounds float, float* %A, i64 %i.0
+  %tmp8 = load float, float* %tmp7, align 4
+  %tmp9 = fadd float %tmp8, %tmp6
+  store float %tmp9, float* %tmp7, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb5, %bb2
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  %tmp12 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb13:                                             ; preds = %bb1
+  ret void
+}

test/ScopInfo/wraping_signed_expr_7.ll

+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK:    Boundary Context:
+; CHECK:        [N] -> {  : N <= 128 }
+;
+;    void foo(float *A, long N) {
+;      for (long i = 0; i < N;)
+;        if ((signed char)i++ < 100)
+;          A[i] += i;
+;    }
+define void @foo(float* %A, i64 %N) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb11, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
+  %tmp = icmp slt i64 %i.0, %N
+  br i1 %tmp, label %bb2, label %bb13
+
+bb2:                                              ; preds = %bb1
+  %tmp12 = add nuw nsw i64 %i.0, 1
+  %tmp3 = trunc i64 %i.0 to i8
+  %tmp4 = icmp slt i8 %tmp3, 100
+  br i1 %tmp4, label %bb5, label %bb10
+
+bb5:                                              ; preds = %bb2
+  %tmp6 = sitofp i64 %i.0 to float
+  %tmp7 = getelementptr inbounds float, float* %A, i64 %i.0
+  %tmp8 = load float, float* %tmp7, align 4
+  %tmp9 = fadd float %tmp8, %tmp6
+  store float %tmp9, float* %tmp7, align 4
+  br label %bb10
+
+bb10:                                             ; preds = %bb5, %bb2
+  br label %bb11
+
+bb11:                                             ; preds = %bb10
+  br label %bb1
+
+bb13:                                             ; preds = %bb1
+  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
+}