From 73836755c7c9d640a5b626387cbc5e6102c213d2 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 30 Jul 2011 14:05:15 +0200 Subject: [PATCH] avoid wrapping on some simple cases of loops with unsigned iterators Also applying wrapping even when it is not necessary always produced correct the results, the representation may be overly complicated. We need to update some of the test cases because in the case of wrapping, the schedule needs to include the constraints of the domain, while they are not included when wrapping is not applied. Signed-off-by: Sven Verdoolaege --- scan.cc | 49 ++++++++++++++++++++++++++++++++++++++--- tests/tobi2.scop | 50 +++++++++++++++++++----------------------- tests/unsigned1.scop | 62 +++++++++++++++++++++++----------------------------- 3 files changed, 96 insertions(+), 65 deletions(-) rewrite tests/tobi2.scop (63%) rewrite tests/unsigned1.scop (77%) diff --git a/scan.cc b/scan.cc index aff0db7..95d7660 100644 --- a/scan.cc +++ b/scan.cc @@ -1563,6 +1563,40 @@ static unsigned get_type_size(ValueDecl *decl) return decl->getASTContext().getIntWidth(decl->getType()); } +/* Assuming "cond" represents a simple bound on a loop where the loop + * iterator "iv" is incremented (or decremented) by one, check if wrapping + * is possible. + * + * Under the given assumptions, wrapping is only possible if "cond" allows + * for the last value before wrapping, i.e., 2^width - 1 in case of an + * increasing iterator and 0 in case of a decreasing iterator. + */ +static bool can_wrap(__isl_keep isl_set *cond, ValueDecl *iv, isl_int inc) +{ + bool cw; + isl_int limit; + isl_set *test; + + test = isl_set_copy(cond); + + isl_int_init(limit); + if (isl_int_is_neg(inc)) + isl_int_set_si(limit, 0); + else { + isl_int_set_si(limit, 1); + isl_int_mul_2exp(limit, limit, get_type_size(iv)); + isl_int_sub_ui(limit, limit, 1); + } + + test = isl_set_fix(cond, isl_dim_set, 0, limit); + cw = !isl_set_is_empty(test); + isl_set_free(test); + + isl_int_clear(limit); + + return cw; +} + /* Given a one-dimensional space, construct the following mapping on this * space * @@ -1634,6 +1668,11 @@ static __isl_give isl_map *compute_wrapping(__isl_take isl_dim *dim, * Note that there is no need to perform this final wrapping * if the loop condition (after wrapping) is simple. * + * Wrapping on unsigned iterators can be avoided entirely if + * loop condition is simple, the loop iterator is incremented + * [decremented] by one and the last value before wrapping cannot + * possibly satisfy the loop condition. + * * Before extracting a pet_scop from the body we remove all * assignments in assigned_value to variables that are assigned * somewhere in the body of the loop. @@ -1650,6 +1689,7 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) struct pet_scop *scop; assigned_value_cache cache(assigned_value); isl_int inc; + bool is_one; bool is_unsigned; bool is_simple; isl_map *wrap = NULL; @@ -1678,7 +1718,8 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) id = isl_id_alloc(ctx, iv->getName().str().c_str(), iv); - if (isl_int_is_one(inc) || isl_int_is_negone(inc)) + is_one = isl_int_is_one(inc) || isl_int_is_negone(inc); + if (is_one) domain = extract_comparison(isl_int_is_pos(inc) ? BO_GE : BO_LE, init->getLHS(), init->getRHS(), init); else { @@ -1689,11 +1730,13 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) cond = extract_condition(stmt->getCond()); cond = embed(cond, isl_id_copy(id)); domain = embed(domain, isl_id_copy(id)); - if (is_unsigned) { + is_simple = is_simple_bound(cond, inc); + if (is_unsigned && + (!is_simple || !is_one || can_wrap(cond, iv, inc))) { wrap = compute_wrapping(isl_set_get_dim(cond), iv); cond = isl_set_apply(cond, isl_map_reverse(isl_map_copy(wrap))); + is_simple = is_simple && is_simple_bound(cond, inc); } - is_simple = is_simple_bound(cond, inc); if (!is_simple) cond = valid_for_each_iteration(cond, isl_set_copy(domain), inc); diff --git a/tests/tobi2.scop b/tests/tobi2.scop dissimilarity index 63% index d2e1d61..87fdba6 100644 --- a/tests/tobi2.scop +++ b/tests/tobi2.scop @@ -1,27 +1,23 @@ -context: '{ [] }' -arrays: -- context: '{ [] }' - extent: '{ a[] }' - element_type: int -statements: -- line: 10 - domain: '[N] -> { S_0[i] : exists (e0 = [(10 + N)/4294967296], e1 = [(4294967295 - - i)/4294967296]: i >= 0 and i <= 4294967295 and 4294967296e1 >= -i and 4294967296e1 - <= 19 - i and 4294967296e0 <= 10 + N and 4294967296e0 >= -4294967285 + N and 4294967296e1 - <= 9 + N - i - 4294967296e0) }' - schedule: '[N] -> { S_0[i] -> [0, o1] : exists (e0 = [(10 + N)/4294967296], e1 = - [(-i + o1)/4294967296]: 4294967296e1 = -i + o1 and o1 >= 0 and o1 <= 19 and 4294967296e0 - <= 10 + N and 4294967296e0 >= -4294967285 + N and 4294967296e0 <= 9 + N - o1 and - i >= 0 and i <= 4294967295) }' - body: - type: binary - operation: = - arguments: - - type: access - relation: '[N] -> { S_0[i] -> a[] }' - read: 0 - write: 1 - - type: access - relation: '[N] -> { S_0[i] -> [5] }' - read: 1 - write: 0 +context: '{ [] }' +arrays: +- context: '{ [] }' + extent: '{ a[] }' + element_type: int +statements: +- line: 10 + domain: '[N] -> { S_0[i] : exists (e0 = [(10 + N)/4294967296]: i >= 0 and i <= 19 + and 4294967296e0 <= 10 + N and 4294967296e0 >= -4294967285 + N and 4294967296e0 + <= 9 + N - i) }' + schedule: '[N] -> { S_0[i] -> [0, i] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_0[i] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_0[i] -> [5] }' + read: 1 + write: 0 diff --git a/tests/unsigned1.scop b/tests/unsigned1.scop dissimilarity index 77% index 9f973ed..cb677aa 100644 --- a/tests/unsigned1.scop +++ b/tests/unsigned1.scop @@ -1,35 +1,27 @@ -context: '{ [] }' -arrays: -- context: '{ [] }' - extent: '{ a[] }' - element_type: int -statements: -- line: 10 - domain: '{ S_0[i, j, k] : (exists (e0 = [(255 - i)/256], e1 = [(255 - j)/256], e2: - i >= 0 and i <= 255 and 256e0 >= -i and 256e0 <= 199 - i and j >= 0 and j <= 255 - and 256e1 >= -j and 256e1 <= 199 - j and k >= 0 and k <= 255 and 256e2 >= -k and - 256e2 <= -1 + i + j - k)) or (exists (e0 = [(255 - i)/256], e1 = [(255 - j)/256]: - i >= 0 and i <= 255 and 256e0 >= -i and 256e0 <= 199 - i and j >= 0 and j <= 255 - and 256e1 >= -j and 256e1 <= 199 - j and k >= 0 and k <= 255 and j >= 256 - i)) - }' - schedule: '{ S_0[i, j, k] -> [0, o1, o2, o3] : (exists (e0 = [(-i + o1)/256], e1 - = [(-j + o2)/256], e2 = [(-k + o3)/256]: 256e0 = -i + o1 and 256e1 = -j + o2 and - 256e2 = -k + o3 and o1 >= 0 and o1 <= 199 and i >= 0 and i <= 255 and o2 >= 0 - and o2 <= 199 and j >= 0 and j <= 255 and o3 >= 0 and o3 <= -1 + i + j and k >= - 0 and k <= 255)) or (exists (e0 = [(-i + o1)/256], e1 = [(-j + o2)/256], e2 = - [(-k + o3)/256]: 256e0 = -i + o1 and 256e1 = -j + o2 and 256e2 = -k + o3 and o1 - >= 0 and o1 <= 199 and i >= 0 and i <= 255 and o2 >= 0 and o2 <= 199 and j >= - 0 and j <= 255 and o3 >= 0 and o3 >= i + j and j >= 256 - i and k >= 0 and k <= - 255)) }' - body: - type: binary - operation: = - arguments: - - type: access - relation: '{ S_0[i, j, k] -> a[] }' - read: 0 - write: 1 - - type: access - relation: '{ S_0[i, j, k] -> [5] }' - read: 1 - write: 0 +context: '{ [] }' +arrays: +- context: '{ [] }' + extent: '{ a[] }' + element_type: int +statements: +- line: 10 + domain: '{ S_0[i, j, k] : (exists (e0: i >= 0 and i <= 199 and j >= 0 and j <= 199 + and k >= 0 and k <= 255 and 256e0 >= -k and 256e0 <= -1 + i + j - k)) or (i >= + 0 and i <= 199 and j >= 0 and j <= 199 and k >= 0 and k <= 255 and j >= 256 - + i) }' + schedule: '{ S_0[i, j, k] -> [0, i, j, o3] : (exists (e0 = [(-k + o3)/256]: 256e0 + = -k + o3 and o3 >= 0 and o3 <= -1 + i + j and k >= 0 and k <= 255)) or (exists + (e0 = [(-k + o3)/256]: 256e0 = -k + o3 and o3 >= 0 and o3 >= i + j and j >= 256 + - i and k >= 0 and k <= 255)) }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j, k] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j, k] -> [5] }' + read: 1 + write: 0 -- 2.11.4.GIT