From f57d63f906e080417437dc42681c9e5ac02501a0 Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Sun, 3 Aug 2014 21:07:30 +0000 Subject: [PATCH] Do allow negative offsets in the outermost array dimension There is no needed for neither 1-dimensional nor higher dimensional arrays to require positive offsets in the outermost array dimension. We originally introduced this assumption with the support for delinearizing multi-dimensional arrays. llvm-svn: 214665 --- polly/lib/Analysis/ScopInfo.cpp | 35 ++++++++++------------ polly/test/Isl/Ast/simple-run-time-condition.ll | 2 +- ...o.ll => multidim_2d_outer_parametric_offset.ll} | 2 +- .../multidim_ivs_and_parameteric_offsets_3d.ll | 2 +- 4 files changed, 18 insertions(+), 23 deletions(-) rename polly/test/ScopInfo/{multidim_2d_outer_larger_than_zero.ll => multidim_2d_outer_parametric_offset.ll} (98%) diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index aa63e24..1382c1d 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -366,9 +366,9 @@ isl_basic_map *MemoryAccess::createBasicAccessMap(ScopStmt *Statement) { // expression of each array evaluates for each statement instance that is // executed to a value that is larger than zero and strictly smaller than the // size of the corresponding dimension). The only exception is the outermost -// dimension for which we do not assume any upper bound. At this point we -// formalize this assumption to ensure that at code generation time the relevant -// run-time checks can be generated. +// dimension for which we do not need to assume any upper bound. At this point +// we formalize this assumption to ensure that at code generation time the +// relevant run-time checks can be generated. // // To find the set of constraints necessary to avoid out of bound accesses, we // first build the set of data locations that are not within array bounds. We @@ -383,7 +383,7 @@ isl_basic_map *MemoryAccess::createBasicAccessMap(ScopStmt *Statement) { void MemoryAccess::assumeNoOutOfBound(const IRAccess &Access) { isl_space *Space = isl_space_range(getAccessRelationSpace()); isl_set *Outside = isl_set_empty(isl_space_copy(Space)); - for (int i = 0, Size = Access.Subscripts.size(); i < Size; ++i) { + for (int i = 1, Size = Access.Subscripts.size(); i < Size; ++i) { isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space)); isl_pw_aff *Var = isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i); @@ -391,22 +391,17 @@ void MemoryAccess::assumeNoOutOfBound(const IRAccess &Access) { isl_set *DimOutside; - if (i == 0) { - DimOutside = isl_pw_aff_lt_set(Var, Zero); - } else { - DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero); - isl_pw_aff *SizeE = - SCEVAffinator::getPwAff(Statement, Access.Sizes[i - 1]); - - SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0, - Statement->getNumIterators()); - SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in, - isl_space_dim(Space, isl_dim_set)); - SizeE = isl_pw_aff_set_tuple_id( - SizeE, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set)); - - DimOutside = isl_set_union(DimOutside, isl_pw_aff_le_set(SizeE, Var)); - } + DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero); + isl_pw_aff *SizeE = SCEVAffinator::getPwAff(Statement, Access.Sizes[i - 1]); + + SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0, + Statement->getNumIterators()); + SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in, + isl_space_dim(Space, isl_dim_set)); + SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in, + isl_space_get_tuple_id(Space, isl_dim_set)); + + DimOutside = isl_set_union(DimOutside, isl_pw_aff_le_set(SizeE, Var)); Outside = isl_set_union(Outside, DimOutside); } diff --git a/polly/test/Isl/Ast/simple-run-time-condition.ll b/polly/test/Isl/Ast/simple-run-time-condition.ll index 592a72b..8eff8be 100644 --- a/polly/test/Isl/Ast/simple-run-time-condition.ll +++ b/polly/test/Isl/Ast/simple-run-time-condition.ll @@ -18,7 +18,7 @@ target triple = "x86_64-unknown-linux-gnu" ; for the delinearization is simplified such that conditions that would not ; cause any code to be executed are not generated. -; CHECK: if ((q == 100 && o <= 0 && p >= 0) || (q == 0 && o >= 1 && p >= 0) ? 1 : 0) +; CHECK: if ((q == 100 && o <= 0) || (q == 0 && o >= 1) ? 1 : 0) ; CHECK: if (o >= 1) { ; CHECK: for (int c1 = 0; c1 < n; c1 += 1) diff --git a/polly/test/ScopInfo/multidim_2d_outer_larger_than_zero.ll b/polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll similarity index 98% rename from polly/test/ScopInfo/multidim_2d_outer_larger_than_zero.ll rename to polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll index 0735446..2c281d0 100644 --- a/polly/test/ScopInfo/multidim_2d_outer_larger_than_zero.ll +++ b/polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll @@ -11,7 +11,7 @@ target triple = "x86_64-unknown-linux-gnu" ; } ; CHECK: Assumed Context: -; CHECK: [m, p] -> { : p >= 0 } +; CHECK: [m, p] -> { : } ; CHECK: p0: %m ; CHECK: p1: %p ; CHECK: Statements { diff --git a/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll b/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll index 7acb778..d77eb9c 100644 --- a/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll +++ b/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll @@ -15,7 +15,7 @@ target triple = "x86_64-unknown-linux-gnu" ; (8 * %o)}<%for.j>,+,8}<%for.k> ; CHECK: Assumed Context: -; CHECK: [n, m, o, p, q, r] -> { : q = 0 and r = 0 and p >= 0 } +; CHECK: [n, m, o, p, q, r] -> { : q = 0 and r = 0 } ; ; CHECK: p0: %n ; CHECK: p1: %m -- 2.7.4