From 80aae0b3a178cfe759777a7b9294800bee49a16a Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 19 Oct 2011 15:08:53 +0200 Subject: [PATCH] turn virtual scalars into virtual arrays There is no point in requiring a dependence analysis to find out which statement instance wrote the value of the virtual scalar for a given iteration of a depending statement. During construction, we know which statement instance is involved, so we may just as well use that instance as the index into the virtual array. Note that this makes the virtual arrays single assignment. Signed-off-by: Sven Verdoolaege --- scan.cc | 8 +++++--- scop.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++---- tests/wdp.scop | 14 +++++++------- 3 files changed, 62 insertions(+), 14 deletions(-) diff --git a/scan.cc b/scan.cc index 5f16739..b93c5dc 100644 --- a/scan.cc +++ b/scan.cc @@ -2220,11 +2220,13 @@ struct pet_scop *PetScan::extract_conditional_assignment(IfStmt *stmt) return extract(stmt, pe); } -/* Create an access to a virtual scalar representing the result +/* Create an access to a virtual array representing the result * of a condition. - * Unlike other accessed data, the id of the scalar is NULL as + * Unlike other accessed data, the id of the array is NULL as * there is no ValueDecl in the program corresponding to the virtual - * scalar. + * array. + * The array starts out as a scalar, but grows along with the + * statement writing to the array in pet_scop_embed. */ static __isl_give isl_map *create_test_access(isl_ctx *ctx, int test_nr) { diff --git a/scop.c b/scop.c index bd12ada..75e355d 100644 --- a/scop.c +++ b/scop.c @@ -866,6 +866,10 @@ struct pet_embed_access { * If the induction variable appears in the constraints (as a parameter), * then the parameter is equated to the newly introduced iteration * domain dimension and subsequently projected out. + * + * Similarly, if the accessed array is a virtual array (with user + * pointer equal to NULL), as created by create_test_access, + * then it is extende along with the domain of the access. */ static __isl_give isl_map *embed_access(__isl_take isl_map *access, void *user) @@ -878,10 +882,14 @@ static __isl_give isl_map *embed_access(__isl_take isl_map *access, if (isl_map_has_tuple_id(access, isl_dim_out)) array_id = isl_map_get_tuple_id(access, isl_dim_out); - if (array_id == data->var_id) { + if (array_id == data->var_id || + (array_id && !isl_id_get_user(array_id))) { access = isl_map_insert_dims(access, isl_dim_out, 0, 1); access = isl_map_equate(access, isl_dim_in, 0, isl_dim_out, 0); + if (array_id != data->var_id) + access = isl_map_set_tuple_id(access, isl_dim_out, + isl_id_copy(array_id)); } isl_id_free(array_id); @@ -1010,9 +1018,40 @@ error: return NULL; } -/* Embed all statements in "scop" in an extra outer loop with iteration domain - * "dom" and schedule "sched". "var_id" represents the induction variable - * of the loop. +/* Embed the given pet_array in an extra outer loop with iteration domain + * "dom". + * This embedding only has an effect on virtual arrays (those with + * user pointer equal to NULL), which need to be extended along with + * the iteration domain. + */ +static struct pet_array *pet_array_embed(struct pet_array *array, + __isl_take isl_set *dom) +{ + isl_id *array_id = NULL; + + if (!array) + goto error; + + if (isl_set_has_tuple_id(array->extent)) + array_id = isl_set_get_tuple_id(array->extent); + + if (array_id && !isl_id_get_user(array_id)) { + array->extent = isl_set_flat_product(dom, array->extent); + array->extent = isl_set_set_tuple_id(array->extent, array_id); + } else { + isl_set_free(dom); + isl_id_free(array_id); + } + + return array; +error: + isl_set_free(dom); + return NULL; +} + +/* Embed all statements and arrays in "scop" in an extra outer loop + * with iteration domain "dom" and schedule "sched". + * "var_id" represents the induction variable of the loop. */ struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom, __isl_take isl_map *sched, __isl_take isl_id *id) @@ -1030,6 +1069,13 @@ struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom, goto error; } + for (i = 0; i < scop->n_array; ++i) { + scop->arrays[i] = pet_array_embed(scop->arrays[i], + isl_set_copy(dom)); + if (!scop->arrays[i]) + goto error; + } + isl_set_free(dom); isl_map_free(sched); isl_id_free(id); diff --git a/tests/wdp.scop b/tests/wdp.scop index cad896d..a8c8804 100644 --- a/tests/wdp.scop +++ b/tests/wdp.scop @@ -1,11 +1,11 @@ context: '[N] -> { : N >= 8 and N <= 16 }' arrays: - context: '{ : }' - extent: '{ __pet_test_0[] }' + extent: '[N] -> { __pet_test_0[i] : i >= 0 and i <= -1 + N }' value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' element_type: int - context: '{ : }' - extent: '{ __pet_test_1[] }' + extent: '[N] -> { __pet_test_1[i] : i >= 0 and i <= -1 + N }' value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' element_type: int - context: '[N] -> { : N >= 0 }' @@ -70,7 +70,7 @@ statements: operation: = arguments: - type: access - relation: '[N] -> { S_3[i] -> __pet_test_0[] }' + relation: '[N] -> { S_3[i] -> __pet_test_0[i] }' read: 0 write: 1 - type: binary @@ -104,7 +104,7 @@ statements: write: 0 arguments: - type: access - relation: '[N] -> { S_4[i] -> __pet_test_0[] }' + relation: '[N] -> { S_4[i] -> __pet_test_0[i] }' read: 1 write: 0 - line: 30 @@ -115,7 +115,7 @@ statements: operation: = arguments: - type: access - relation: '[N] -> { S_5[i] -> __pet_test_1[] }' + relation: '[N] -> { S_5[i] -> __pet_test_1[i] }' read: 0 write: 1 - type: binary @@ -156,7 +156,7 @@ statements: write: 0 arguments: - type: access - relation: '[N] -> { S_6[i] -> __pet_test_1[] }' + relation: '[N] -> { S_6[i] -> __pet_test_1[i] }' read: 1 write: 0 - line: 32 @@ -179,7 +179,7 @@ statements: write: 0 arguments: - type: access - relation: '[N] -> { S_7[i] -> __pet_test_1[] }' + relation: '[N] -> { S_7[i] -> __pet_test_1[i] }' read: 1 write: 0 - line: 34 -- 2.11.4.GIT