From 2868def6e6ceddf4c5c67f899d5bd414fff1cc71 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 30 Jul 2011 12:24:38 +0200 Subject: [PATCH] take into account that unsigned iterators may wrap Signed-off-by: Sven Verdoolaege --- scan.cc | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++- tests/tobi1.c | 11 +++++++++ tests/tobi1.scop | 23 ++++++++++++++++++ tests/unsigned1.c | 12 +++++++++ tests/unsigned1.scop | 35 ++++++++++++++++++++++++++ tests/unsigned2.c | 10 ++++++++ tests/unsigned2.scop | 23 ++++++++++++++++++ 7 files changed, 182 insertions(+), 1 deletion(-) create mode 100644 tests/tobi1.c create mode 100644 tests/tobi1.scop create mode 100644 tests/unsigned1.c create mode 100644 tests/unsigned1.scop create mode 100644 tests/unsigned2.c create mode 100644 tests/unsigned2.scop diff --git a/scan.cc b/scan.cc index dc9f630..4efe3b5 100644 --- a/scan.cc +++ b/scan.cc @@ -1522,6 +1522,40 @@ static __isl_give isl_set *strided_domain(__isl_take isl_id *id, return isl_set_project_out(set, isl_dim_set, 0, 1); } +static unsigned get_type_size(ValueDecl *decl) +{ + return decl->getASTContext().getIntWidth(decl->getType()); +} + +/* Given a one-dimensional space, construct the following mapping on this + * space + * + * { [v] -> [v mod 2^width] } + * + * where width is the number of bits used to represent the values + * of the unsigned variable "iv". + */ +static __isl_give isl_map *compute_wrapping(__isl_take isl_dim *dim, + ValueDecl *iv) +{ + isl_int mod; + isl_aff *aff; + isl_map *map; + + isl_int_init(mod); + isl_int_set_si(mod, 1); + isl_int_mul_2exp(mod, mod, get_type_size(iv)); + + aff = isl_aff_zero(isl_local_space_from_dim(dim)); + aff = isl_aff_add_coefficient_si(aff, isl_dim_set, 0, 1); + aff = isl_aff_mod(aff, mod); + + isl_int_clear(mod); + + return isl_map_from_basic_map(isl_basic_map_from_aff(aff)); + map = isl_map_reverse(map); +} + /* Construct a pet_scop for a for statement. * The for loop is required to be of the form * @@ -1550,6 +1584,20 @@ static __isl_give isl_set *strided_domain(__isl_take isl_id *id, * * (exists a: i = init + stride * a and a >= 0) * + * If the loop iterator i is unsigned, then wrapping may occur. + * During the computation, we work with a virtual iterator that + * does not wrap. However, the condition in the code applies + * to the wrapped value, so we need to change condition(i) + * into condition([i % 2^width]). + * After computing the virtual domain and schedule, we apply + * the function { [v] -> [v % 2^width] } to the domain and the domain + * of the schedule. In order not to lose any information, we also + * need to intersect the domain of the schedule with the virtual domain + * first, since some iterations in the wrapped domain may be scheduled + * several times, typically an infinite number of times. + * Note that there is no need to perform this final wrapping + * if the loop condition (after wrapping) is simple. + * * 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. @@ -1566,6 +1614,9 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) struct pet_scop *scop; assigned_value_cache cache(assigned_value); isl_int inc; + bool is_unsigned; + bool is_simple; + isl_map *wrap = NULL; if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) return extract_infinite_for(stmt); @@ -1583,6 +1634,8 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) return NULL; } + is_unsigned = iv->getType()->isUnsignedIntegerType(); + assigned_value[iv] = NULL; clear_assignments clear(assigned_value); clear.TraverseStmt(stmt->getBody()); @@ -1600,7 +1653,12 @@ 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_simple_bound(cond, inc)) + if (is_unsigned) { + 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_bound(cond, inc); + if (!is_simple) cond = valid_for_each_iteration(cond, isl_set_copy(domain), inc); domain = isl_set_intersect(domain, cond); @@ -1613,6 +1671,15 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) else sched = isl_map_oppose(sched, isl_dim_in, 0, isl_dim_out, 0); + if (is_unsigned && !is_simple) { + wrap = isl_map_set_dim_id(wrap, + isl_dim_out, 0, isl_id_copy(id)); + sched = isl_map_intersect_domain(sched, isl_set_copy(domain)); + domain = isl_set_apply(domain, isl_map_copy(wrap)); + sched = isl_map_apply_domain(sched, wrap); + } else + isl_map_free(wrap); + scop = extract(stmt->getBody()); scop = pet_scop_embed(scop, domain, sched, id); diff --git a/tests/tobi1.c b/tests/tobi1.c new file mode 100644 index 0000000..95b653c --- /dev/null +++ b/tests/tobi1.c @@ -0,0 +1,11 @@ +void foo() +{ + unsigned char i; + int a; + +#pragma scop + for (i = 0; i != 16 ; i += 65) + a = 5; +#pragma endscop +} + diff --git a/tests/tobi1.scop b/tests/tobi1.scop new file mode 100644 index 0000000..9c27292 --- /dev/null +++ b/tests/tobi1.scop @@ -0,0 +1,23 @@ +context: '{ [] }' +arrays: +- context: '{ [] }' + extent: '{ a[] }' + element_type: int +statements: +- line: 8 + domain: '{ S_0[i] : exists (e0 = [(255 - 193i)/256]: i >= 0 and i <= 255 and 256e0 + >= -193i and 256e0 <= 15 - 193i) }' + schedule: '{ S_0[i] -> [0, o1] : exists (e0 = [(-12545i + o1)/16640]: 16640e0 = + -12545i + o1 and o1 >= 0 and o1 <= 1039 and i >= 0 and i <= 255) }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i] -> [5] }' + read: 1 + write: 0 diff --git a/tests/unsigned1.c b/tests/unsigned1.c new file mode 100644 index 0000000..6a9071d --- /dev/null +++ b/tests/unsigned1.c @@ -0,0 +1,12 @@ +void foo() +{ + unsigned char i, j, k; + int a; + +#pragma scop + for (i = 0; i < 200; ++i) + for (j = 0; j < 200; ++j) + for (k = 0; k < i + j; ++k) + a = 5; +#pragma endscop +} diff --git a/tests/unsigned1.scop b/tests/unsigned1.scop new file mode 100644 index 0000000..9f973ed --- /dev/null +++ b/tests/unsigned1.scop @@ -0,0 +1,35 @@ +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 diff --git a/tests/unsigned2.c b/tests/unsigned2.c new file mode 100644 index 0000000..bde2ac3 --- /dev/null +++ b/tests/unsigned2.c @@ -0,0 +1,10 @@ +int main() +{ + unsigned char k; + int a; + +#pragma scop + for (k = 252; (k % 9) <= 5; ++k) + a = 5; +#pragma endscop +} diff --git a/tests/unsigned2.scop b/tests/unsigned2.scop new file mode 100644 index 0000000..f42ee5b --- /dev/null +++ b/tests/unsigned2.scop @@ -0,0 +1,23 @@ +context: '{ [] }' +arrays: +- context: '{ [] }' + extent: '{ a[] }' + element_type: int +statements: +- line: 8 + domain: '{ S_0[k] : exists (e0 = [(507 - k)/256]: k >= 0 and k <= 255 and 256e0 + >= 252 - k and 256e0 <= 261 - k) }' + schedule: '{ S_0[k] -> [0, o1] : exists (e0 = [(-k + o1)/256]: 256e0 = -k + o1 and + o1 >= 252 and k <= 255 and k >= 0 and o1 <= 261) }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[k] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[k] -> [5] }' + read: 1 + write: 0 -- 2.11.4.GIT