From 79ccc22fa3e46e26d9dcd842b40bb7eb233e3e6f Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 25 Mar 2014 22:40:45 +0100 Subject: [PATCH] break up access relations into may_read/may_write/must_write Internally, we currently only make a distinction between may accesses and must accesses. At the level of an individual access expression, we even only have a single (possibly argument dependent) access relation. If we want to keep track of the accesses performed by a function called from a function call, we will need to make a further distinction between reads and writes. Furthermore, if member accesses are involved, then a function may access elements from different spaces through the same argument. The access relations therefore need to be changed into union maps. We already changed the ouside interface with respect to these changes. Now we make the internal represenation follow suit. Signed-off-by: Sven Verdoolaege --- emit.c | 25 +- expr.c | 573 +++++++++++++++++++++--------------- expr.h | 22 +- expr_access_type.h | 3 + expr_arg.c | 25 +- nest.c | 51 +++- parse.c | 21 +- scop.c | 34 ++- tests/autodetect/decl.scop | 2 +- tests/break4.scop | 16 +- tests/break6.scop | 2 +- tests/conditional_assignment.scop | 4 +- tests/conditional_assignment2.scop | 4 +- tests/continue2.scop | 4 +- tests/continue3.scop | 2 +- tests/continue4.scop | 2 +- tests/continue5.scop | 2 +- tests/decl.scop | 4 +- tests/decl2.scop | 2 +- tests/decl3.scop | 2 +- tests/encapsulate/for_while.scop | 4 +- tests/encapsulate/independent5.scop | 4 +- tests/encapsulate/inf_break.scop | 4 +- tests/for_while_inc2.scop | 4 +- tests/for_while_inc3.scop | 4 +- tests/for_while_init.scop | 4 +- tests/for_while_init2.scop | 4 +- tests/for_while_init3.scop | 4 +- tests/forward_substitution3.scop | 4 +- tests/independent3.scop | 4 +- 30 files changed, 513 insertions(+), 327 deletions(-) diff --git a/emit.c b/emit.c index c80a51d..63f7a17 100644 --- a/emit.c +++ b/emit.c @@ -471,6 +471,9 @@ static int emit_expr_type(yaml_emitter_t *emitter, enum pet_expr_type type) /* Print the fields of the access expression "expr" to "emitter". * + * Only print the access relations that are present and relevant + * for the type of access. + * * If the depth of the access is equal to the depth that can be derived from * the index expression, then there is no need to print it. */ @@ -478,12 +481,22 @@ static int emit_access_expr(yaml_emitter_t *emitter, __isl_keep pet_expr *expr) { int depth; - if (expr->acc.access) { - if (emit_string(emitter, "relation") < 0) - return -1; - if (emit_map(emitter, expr->acc.access) < 0) - return -1; - } + if (expr->acc.kill && expr->acc.access[pet_expr_access_fake_killed] && + emit_named_union_map(emitter, "killed", + expr->acc.access[pet_expr_access_fake_killed]) < 0) + return -1; + if (expr->acc.read && expr->acc.access[pet_expr_access_may_read] && + emit_named_union_map(emitter, "may_read", + expr->acc.access[pet_expr_access_may_read]) < 0) + return -1; + if (expr->acc.write && expr->acc.access[pet_expr_access_may_write] && + emit_named_union_map(emitter, "may_write", + expr->acc.access[pet_expr_access_may_write]) < 0) + return -1; + if (expr->acc.write && expr->acc.access[pet_expr_access_must_write] && + emit_named_union_map(emitter, "must_write", + expr->acc.access[pet_expr_access_must_write]) < 0) + return -1; if (emit_named_multi_pw_aff(emitter, "index", expr->acc.index) < 0) return -1; depth = isl_multi_pw_aff_dim(expr->acc.index, isl_dim_out); diff --git a/expr.c b/expr.c index ea3fc9e..f0cb344 100644 --- a/expr.c +++ b/expr.c @@ -205,19 +205,43 @@ static __isl_give isl_map *extend_range(__isl_take isl_map *access, int n) return access; } -/* Does the access expression "expr" have an explicit access relation? +/* Does the access expression "expr" have any explicit access relation? */ -static int has_access_relation(__isl_keep pet_expr *expr) +static int has_any_access_relation(__isl_keep pet_expr *expr) { + enum pet_expr_access_type type; + if (!expr) return -1; - if (expr->acc.access) - return 1; + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) + if (expr->acc.access[type]) + return 1; return 0; } +/* Are all relevant access relations explicitly available in "expr"? + */ +static int has_relevant_access_relations(__isl_keep pet_expr *expr) +{ + enum pet_expr_access_type type; + + if (!expr) + return -1; + + if (expr->acc.kill && !expr->acc.access[pet_expr_access_fake_killed]) + return 0; + if (expr->acc.read && !expr->acc.access[pet_expr_access_may_read]) + return 0; + if (expr->acc.write && + (!expr->acc.access[pet_expr_access_may_write] || + !expr->acc.access[pet_expr_access_must_write])) + return 0; + + return 1; +} + /* Replace the depth of the access expr "expr" by "depth". * * To avoid inconsistencies between the depth and the access relation, @@ -234,7 +258,7 @@ __isl_give pet_expr *pet_expr_access_set_depth(__isl_take pet_expr *expr, return NULL; if (expr->acc.depth == depth) return expr; - if (has_access_relation(expr)) + if (has_any_access_relation(expr)) isl_die(pet_expr_get_ctx(expr), isl_error_unsupported, "depth cannot be changed after access relation " "has been set or computed", return pet_expr_free(expr)); @@ -264,7 +288,8 @@ __isl_give pet_expr *pet_expr_kill_from_access_and_index( expr = pet_expr_access_set_kill(expr, 1); depth = isl_map_dim(access, isl_dim_out); expr = pet_expr_access_set_depth(expr, depth); - expr = pet_expr_access_set_access(expr, access); + expr = pet_expr_access_set_access(expr, pet_expr_access_killed, + isl_union_map_from_map(access)); return pet_expr_new_unary(pet_op_kill, expr); error: isl_map_free(access); @@ -458,6 +483,7 @@ static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr) { int i; pet_expr *dup; + enum pet_expr_access_type type; if (!expr) return NULL; @@ -476,9 +502,13 @@ static __isl_give pet_expr *pet_expr_dup(__isl_keep pet_expr *expr) dup = pet_expr_access_set_index(dup, isl_multi_pw_aff_copy(expr->acc.index)); dup = pet_expr_access_set_depth(dup, expr->acc.depth); - if (expr->acc.access) - dup = pet_expr_access_set_access(dup, - isl_map_copy(expr->acc.access)); + for (type = pet_expr_access_begin; + type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + dup = pet_expr_access_set_access(dup, type, + isl_union_map_copy(expr->acc.access[type])); + } dup = pet_expr_access_set_read(dup, expr->acc.read); dup = pet_expr_access_set_write(dup, expr->acc.write); dup = pet_expr_access_set_kill(dup, expr->acc.kill); @@ -519,6 +549,7 @@ __isl_give pet_expr *pet_expr_cow(__isl_take pet_expr *expr) __isl_null pet_expr *pet_expr_free(__isl_take pet_expr *expr) { + enum pet_expr_access_type type; int i; if (!expr) @@ -533,7 +564,9 @@ __isl_null pet_expr *pet_expr_free(__isl_take pet_expr *expr) switch (expr->type) { case pet_expr_access: isl_id_free(expr->acc.ref_id); - isl_map_free(expr->acc.access); + for (type = pet_expr_access_begin; + type < pet_expr_access_end; ++type) + isl_union_map_free(expr->acc.access[type]); isl_multi_pw_aff_free(expr->acc.index); break; case pet_expr_call: @@ -815,7 +848,8 @@ static int multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff *mpa1, * then we assume that all elements of the remaining dimensions * are accessed. */ -static __isl_give isl_map *construct_access_relation(__isl_keep pet_expr *expr) +static __isl_give isl_union_map *construct_access_relation( + __isl_keep pet_expr *expr) { isl_map *access; int dim; @@ -837,33 +871,55 @@ static __isl_give isl_map *construct_access_relation(__isl_keep pet_expr *expr) if (dim != expr->acc.depth) access = extend_range(access, expr->acc.depth - dim); - return access; + return isl_union_map_from_map(access); } -/* Ensure that "expr" has an explicit access relation. +/* Ensure that all relevant access relations are explicitly + * available in "expr". * - * If "expr" does not already have an access relation, then create - * one based on the index expression and the array depth. + * If "expr" does not already have the relevant access relations, then create + * them based on the index expression and the array depth. * * We do not cow since adding an explicit access relation * does not change the meaning of the expression. */ -static __isl_give pet_expr *introduce_access_relation( +static __isl_give pet_expr *introduce_access_relations( __isl_take pet_expr *expr) { - isl_map *access; + enum pet_expr_access_type type; + isl_union_map *access; int dim; + int kill, read, write; if (!expr) return NULL; - if (has_access_relation(expr)) + if (has_relevant_access_relations(expr)) return expr; access = construct_access_relation(expr); if (!access) return pet_expr_free(expr); - expr->acc.access = access; + kill = expr->acc.kill; + read = expr->acc.read; + write = expr->acc.write; + if (kill && !expr->acc.access[pet_expr_access_fake_killed]) + expr->acc.access[pet_expr_access_fake_killed] = + isl_union_map_copy(access); + if (read && !expr->acc.access[pet_expr_access_may_read]) + expr->acc.access[pet_expr_access_may_read] = + isl_union_map_copy(access); + if (write && !expr->acc.access[pet_expr_access_may_write]) + expr->acc.access[pet_expr_access_may_write] = + isl_union_map_copy(access); + if (write && !expr->acc.access[pet_expr_access_must_write]) + expr->acc.access[pet_expr_access_must_write] = + isl_union_map_copy(access); + + isl_union_map_free(access); + + if (!has_relevant_access_relations(expr)) + return pet_expr_free(expr); return expr; } @@ -873,6 +929,7 @@ static __isl_give pet_expr *introduce_access_relation( int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2) { int i; + enum pet_expr_access_type type; if (!expr1 || !expr2) return 0; @@ -912,20 +969,29 @@ int pet_expr_is_equal(__isl_keep pet_expr *expr1, __isl_keep pet_expr *expr2) return 0; if (expr1->acc.depth != expr2->acc.depth) return 0; - if (has_access_relation(expr1) != has_access_relation(expr2)) { + if (has_relevant_access_relations(expr1) != + has_relevant_access_relations(expr2)) { int equal; expr1 = pet_expr_copy(expr1); expr2 = pet_expr_copy(expr2); - expr1 = introduce_access_relation(expr1); - expr2 = introduce_access_relation(expr2); + expr1 = introduce_access_relations(expr1); + expr2 = introduce_access_relations(expr2); equal = pet_expr_is_equal(expr1, expr2); pet_expr_free(expr1); pet_expr_free(expr2); return equal; } - if (expr1->acc.access && - !isl_map_is_equal(expr1->acc.access, expr2->acc.access)) - return 0; + for (type = pet_expr_access_begin; + type < pet_expr_access_end; ++type) { + if (!expr1->acc.access[type] != + !expr2->acc.access[type]) + return 0; + if (!expr1->acc.access[type]) + continue; + if (!isl_union_map_is_equal(expr1->acc.access[type], + expr2->acc.access[type])) + return 0; + } break; case pet_expr_op: if (expr1->op != expr2->op) @@ -1184,13 +1250,15 @@ int pet_expr_writes(__isl_keep pet_expr *expr, __isl_keep isl_id *id) } /* Move the "n" dimensions of "src_type" starting at "src_pos" of - * index expression and access relation of "expr" (if any) + * index expression and access relations of "expr" (if any) * to dimensions of "dst_type" at "dst_pos". */ __isl_give pet_expr *pet_expr_access_move_dims(__isl_take pet_expr *expr, enum isl_dim_type dst_type, unsigned dst_pos, enum isl_dim_type src_type, unsigned src_pos, unsigned n) { + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr) return NULL; @@ -1198,27 +1266,31 @@ __isl_give pet_expr *pet_expr_access_move_dims(__isl_take pet_expr *expr, isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access pet_expr", return pet_expr_free(expr)); - if (expr->acc.access) { - expr->acc.access = isl_map_move_dims(expr->acc.access, + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + pet_union_map_move_dims(expr->acc.access[type], dst_type, dst_pos, src_type, src_pos, n); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + if (!expr->acc.access[type]) + break; } expr->acc.index = isl_multi_pw_aff_move_dims(expr->acc.index, dst_type, dst_pos, src_type, src_pos, n); - if (!expr->acc.index) + if (!expr->acc.index || type < pet_expr_access_end) return pet_expr_free(expr); return expr; } -/* Replace the index expression and access relation (if any) of "expr" +/* Replace the index expression and access relations (if any) of "expr" * by their preimages under the function represented by "ma". */ __isl_give pet_expr *pet_expr_access_pullback_multi_aff( __isl_take pet_expr *expr, __isl_take isl_multi_aff *ma) { + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr || !ma) goto error; @@ -1226,16 +1298,18 @@ __isl_give pet_expr *pet_expr_access_pullback_multi_aff( isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access pet_expr", goto error); - if (expr->acc.access) { - expr->acc.access = isl_map_preimage_domain_multi_aff( - expr->acc.access, isl_multi_aff_copy(ma)); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_preimage_domain_multi_aff( + expr->acc.access[type], isl_multi_aff_copy(ma)); + if (!expr->acc.access[type]) + break; } expr->acc.index = isl_multi_pw_aff_pullback_multi_aff(expr->acc.index, ma); - if (!expr->acc.index) + if (!expr->acc.index || type < pet_expr_access_end) return pet_expr_free(expr); return expr; @@ -1245,12 +1319,14 @@ error: return NULL; } -/* Replace the index expression and access relation (if any) of "expr" +/* Replace the index expression and access relations (if any) of "expr" * by their preimages under the function represented by "mpa". */ __isl_give pet_expr *pet_expr_access_pullback_multi_pw_aff( __isl_take pet_expr *expr, __isl_take isl_multi_pw_aff *mpa) { + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr || !mpa) goto error; @@ -1258,16 +1334,18 @@ __isl_give pet_expr *pet_expr_access_pullback_multi_pw_aff( isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access pet_expr", goto error); - if (expr->acc.access) { - expr->acc.access = isl_map_preimage_domain_multi_pw_aff( - expr->acc.access, isl_multi_pw_aff_copy(mpa)); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_preimage_domain_multi_pw_aff( + expr->acc.access[type], isl_multi_pw_aff_copy(mpa)); + if (!expr->acc.access[type]) + break; } expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff( expr->acc.index, mpa); - if (!expr->acc.index) + if (!expr->acc.index || type < pet_expr_access_end) return pet_expr_free(expr); return expr; @@ -1291,10 +1369,13 @@ __isl_give isl_multi_pw_aff *pet_expr_access_get_index( return isl_multi_pw_aff_copy(expr->acc.index); } -/* Align the parameters of expr->acc.index and expr->acc.access (if set). +/* Align the parameters of expr->acc.index and expr->acc.access[*] (if set). */ __isl_give pet_expr *pet_expr_access_align_params(__isl_take pet_expr *expr) { + isl_space *space; + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr) return NULL; @@ -1302,14 +1383,29 @@ __isl_give pet_expr *pet_expr_access_align_params(__isl_take pet_expr *expr) isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access expression", return pet_expr_free(expr)); - if (!has_access_relation(expr)) + if (!has_any_access_relation(expr)) return expr; - expr->acc.access = isl_map_align_params(expr->acc.access, - isl_multi_pw_aff_get_space(expr->acc.index)); + space = isl_multi_pw_aff_get_space(expr->acc.index); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + space = isl_space_align_params(space, + isl_union_map_get_space(expr->acc.access[type])); + } expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index, - isl_map_get_space(expr->acc.access)); - if (!expr->acc.access || !expr->acc.index) + isl_space_copy(space)); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_align_params(expr->acc.access[type], + isl_space_copy(space)); + if (!expr->acc.access[type]) + break; + } + isl_space_free(space); + if (!expr->acc.index || type < pet_expr_access_end) return pet_expr_free(expr); return expr; @@ -1366,12 +1462,14 @@ int pet_expr_is_sub_access(__isl_keep pet_expr *expr1, expr1 = pet_expr_copy(expr1); expr2 = pet_expr_copy(expr2); - expr1 = introduce_access_relation(expr1); - expr2 = introduce_access_relation(expr2); + expr1 = introduce_access_relations(expr1); + expr2 = introduce_access_relations(expr2); if (!expr1 || !expr2) goto error; - is_subset = isl_map_is_subset(expr1->acc.access, expr2->acc.access); + is_subset = isl_union_map_is_subset( + expr1->acc.access[pet_expr_access_may_read], + expr2->acc.access[pet_expr_access_may_read]); pet_expr_free(expr1); pet_expr_free(expr2); @@ -1411,6 +1509,8 @@ __isl_give pet_expr *pet_expr_restrict(__isl_take pet_expr *expr, __isl_take isl_set *cond) { int i; + isl_union_set *uset; + enum pet_expr_access_type type; expr = pet_expr_cow(expr); if (!expr) @@ -1428,15 +1528,24 @@ __isl_give pet_expr *pet_expr_restrict(__isl_take pet_expr *expr, return expr; } - expr = introduce_access_relation(expr); + expr = introduce_access_relations(expr); if (!expr) goto error; cond = add_arguments(cond, expr->n_arg); - expr->acc.access = isl_map_intersect_domain(expr->acc.access, - isl_set_copy(cond)); + uset = isl_union_set_from_set(isl_set_copy(cond)); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_intersect_domain(expr->acc.access[type], + isl_union_set_copy(uset)); + if (!expr->acc.access[type]) + break; + } + isl_union_set_free(uset); expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, cond); - if (!expr->acc.access || !expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) return pet_expr_free(expr); return expr; @@ -1445,7 +1554,7 @@ error: return pet_expr_free(expr); } -/* Modify the access relation (if any) and index expression +/* Modify the access relations (if any) and index expression * of the given access expression * based on the given iteration space transformation. * In particular, precompose the access relation and index expression @@ -1460,6 +1569,8 @@ error: __isl_give pet_expr *pet_expr_access_update_domain(__isl_take pet_expr *expr, __isl_keep isl_multi_pw_aff *update) { + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr) return NULL; @@ -1482,17 +1593,19 @@ __isl_give pet_expr *pet_expr_access_update_domain(__isl_take pet_expr *expr, update = isl_multi_pw_aff_product(update, id); } - if (expr->acc.access) { - expr->acc.access = isl_map_preimage_domain_multi_pw_aff( - expr->acc.access, + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_preimage_domain_multi_pw_aff( + expr->acc.access[type], isl_multi_pw_aff_copy(update)); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + if (!expr->acc.access[type]) + break; } expr->acc.index = isl_multi_pw_aff_pullback_multi_pw_aff( expr->acc.index, update); - if (!expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) return pet_expr_free(expr); return expr; @@ -1529,12 +1642,13 @@ __isl_give pet_expr *pet_expr_insert_domain(__isl_take pet_expr *expr, return pet_expr_update_domain(expr, mpa); } -/* Add all parameters in "space" to the access relation (if any) +/* Add all parameters in "space" to the access relations (if any) * and index expression of "expr". */ static __isl_give pet_expr *align_params(__isl_take pet_expr *expr, void *user) { isl_space *space = user; + enum pet_expr_access_type type; expr = pet_expr_cow(expr); if (!expr) @@ -1543,16 +1657,18 @@ static __isl_give pet_expr *align_params(__isl_take pet_expr *expr, void *user) isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access expression", return pet_expr_free(expr)); - if (expr->acc.access) { - expr->acc.access = isl_map_align_params(expr->acc.access, + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_align_params(expr->acc.access[type], isl_space_copy(space)); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + if (!expr->acc.access[type]) + break; } expr->acc.index = isl_multi_pw_aff_align_params(expr->acc.index, isl_space_copy(space)); - if (!expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) return pet_expr_free(expr); return expr; @@ -1623,6 +1739,7 @@ __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr, isl_ctx *ctx; isl_space *space; isl_pw_multi_aff *pma; + enum pet_expr_access_type type; expr = pet_expr_cow(expr); if (!expr || !test) @@ -1646,7 +1763,7 @@ __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr, isl_die(ctx, isl_error_invalid, "can only filter access expressions", goto error); - expr = introduce_access_relation(expr); + expr = introduce_access_relations(expr); if (!expr) goto error; @@ -1654,14 +1771,21 @@ __isl_give pet_expr *pet_expr_filter(__isl_take pet_expr *expr, id = isl_multi_pw_aff_get_tuple_id(test, isl_dim_out); pma = pet_filter_insert_pma(space, id, satisfied); - expr->acc.access = isl_map_preimage_domain_pw_multi_aff( - expr->acc.access, + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_preimage_domain_pw_multi_aff( + expr->acc.access[type], isl_pw_multi_aff_copy(pma)); + if (!expr->acc.access[type]) + break; + } pma = isl_pw_multi_aff_gist(pma, isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(pma))); expr->acc.index = isl_multi_pw_aff_pullback_pw_multi_aff( expr->acc.index, pma); - if (!expr->acc.access || !expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) goto error; expr = insert_access_arg(expr, test); @@ -1706,12 +1830,14 @@ __isl_give pet_expr *pet_expr_add_ref_ids(__isl_take pet_expr *expr, int *n_ref) } /* Reset the user pointer on all parameter and tuple ids in - * the access relation (if any) and the index expression + * the access relations (if any) and the index expression * of the access expression "expr". */ static __isl_give pet_expr *access_anonymize(__isl_take pet_expr *expr, void *user) { + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr) return expr; @@ -1719,14 +1845,16 @@ static __isl_give pet_expr *access_anonymize(__isl_take pet_expr *expr, isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access expression", return pet_expr_free(expr)); - if (expr->acc.access) { - expr->acc.access = isl_map_reset_user(expr->acc.access); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_reset_user(expr->acc.access[type]); + if (!expr->acc.access[type]) + break; } expr->acc.index = isl_multi_pw_aff_reset_user(expr->acc.index); - if (!expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) return pet_expr_free(expr); return expr; @@ -1745,7 +1873,7 @@ struct pet_access_gist_data { }; /* Given an expression "expr" of type pet_expr_access, compute - * the gist of the associated access relation (if any) and index expression + * the gist of the associated access relations (if any) and index expression * with respect to data->domain and the bounds on the values of the arguments * of the expression. * @@ -1758,6 +1886,8 @@ static __isl_give pet_expr *access_gist(__isl_take pet_expr *expr, void *user) { struct pet_access_gist_data *data = user; isl_set *domain; + isl_union_set *uset; + enum pet_expr_access_type type; expr = pet_expr_remove_duplicate_args(expr); expr = pet_expr_cow(expr); @@ -1772,15 +1902,19 @@ static __isl_give pet_expr *access_gist(__isl_take pet_expr *expr, void *user) domain = pet_value_bounds_apply(domain, expr->n_arg, expr->args, data->value_bounds); - if (expr->acc.access) { - expr->acc.access = isl_map_gist_domain(expr->acc.access, - isl_set_copy(domain)); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + uset = isl_union_set_from_set(isl_set_copy(domain)); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_gist_domain(expr->acc.access[type], + isl_union_set_copy(uset)); + if (!expr->acc.access[type]) + break; } + isl_union_set_free(uset); expr->acc.index = isl_multi_pw_aff_gist(expr->acc.index, domain); - if (!expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) return pet_expr_free(expr); return expr; @@ -1854,10 +1988,23 @@ __isl_give pet_expr *pet_expr_access_set_kill(__isl_take pet_expr *expr, return expr; } -/* Replace the access relation of "expr" by "access". +/* Map the access type "type" to the corresponding location + * in the access array. + * In particular, the access relation of type pet_expr_access_killed is + * stored in the element at position pet_expr_access_fake_killed. + */ +static enum pet_expr_access_type internalize_type( + enum pet_expr_access_type type) +{ + if (type == pet_expr_access_killed) + return pet_expr_access_fake_killed; + return type; +} + +/* Replace the access relation of the given "type" of "expr" by "access". */ __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr, - __isl_take isl_map *access) + enum pet_expr_access_type type, __isl_take isl_union_map *access) { expr = pet_expr_cow(expr); if (!expr || !access) @@ -1865,12 +2012,13 @@ __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr, if (expr->type != pet_expr_access) isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access expression", goto error); - isl_map_free(expr->acc.access); - expr->acc.access = access; + type = internalize_type(type); + isl_union_map_free(expr->acc.access[type]); + expr->acc.access[type] = access; return expr; error: - isl_map_free(access); + isl_union_map_free(access); pet_expr_free(expr); return NULL; } @@ -1966,13 +2114,21 @@ __isl_give isl_union_map *pet_expr_tag_access(__isl_keep pet_expr *expr, return access; } -/* Return the relation mapping pairs of domain iterations and argument - * values to the corresponding accessed data elements. +/* Return the access relation of the given "type" associated to "expr" + * that maps pairs of domain iterations and argument values + * to the corresponding accessed data elements. + * + * If the requested access relation is explicitly available, + * then return a copy. Otherwise, check if it is irrelevant for + * the access expression and return an empty relation if this is the case. + * Otherwise, introduce the requested access relation in "expr" and + * return a copy. */ -static __isl_give isl_map *pet_expr_access_get_dependent_access( - __isl_keep pet_expr *expr) +__isl_give isl_union_map *pet_expr_access_get_dependent_access( + __isl_keep pet_expr *expr, enum pet_expr_access_type type) { - isl_map *access; + isl_union_map *access; + int empty; if (!expr) return NULL; @@ -1980,97 +2136,73 @@ static __isl_give isl_map *pet_expr_access_get_dependent_access( isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access expression", return NULL); - if (expr->acc.access) - return isl_map_copy(expr->acc.access); + type = internalize_type(type); + if (expr->acc.access[type]) + return isl_union_map_copy(expr->acc.access[type]); - expr = pet_expr_copy(expr); - expr = introduce_access_relation(expr); - if (!expr) - return NULL; - access = isl_map_copy(expr->acc.access); - pet_expr_free(expr); + if (type == pet_expr_access_may_read) + empty = !expr->acc.read; + else + empty = !expr->acc.write; - return access; -} + if (!empty) { + expr = pet_expr_copy(expr); + expr = introduce_access_relations(expr); + if (!expr) + return NULL; + access = isl_union_map_copy(expr->acc.access[type]); + pet_expr_free(expr); + + return access; + } -/* Return an empty access relation for access expression "expr". - */ -static __isl_give isl_union_map *empty_access_relation( - __isl_keep pet_expr *expr) -{ return isl_union_map_empty(pet_expr_access_get_parameter_space(expr)); } /* Return the may read access relation associated to "expr" * that maps pairs of domain iterations and argument values * to the corresponding accessed data elements. - * - * Since the accesses are currently represented by a single access relation, - * we return the entire access relation if "expr" is a read and - * an empty relation if it is not. */ __isl_give isl_union_map *pet_expr_access_get_dependent_may_read( __isl_keep pet_expr *expr) { - isl_map *access; - - if (!expr) - return NULL; - if (!pet_expr_access_is_read(expr)) - return empty_access_relation(expr); - access = pet_expr_access_get_dependent_access(expr); - return isl_union_map_from_map(access); + return pet_expr_access_get_dependent_access(expr, + pet_expr_access_may_read); } /* Return the may write access relation associated to "expr" * that maps pairs of domain iterations and argument values * to the corresponding accessed data elements. - * - * Since the accesses are currently represented by a single access relation, - * we return the entire access relation if "expr" is a write and - * an empty relation if it is not. */ __isl_give isl_union_map *pet_expr_access_get_dependent_may_write( __isl_keep pet_expr *expr) { - isl_map *access; - - if (!expr) - return NULL; - if (!pet_expr_access_is_write(expr)) - return empty_access_relation(expr); - access = pet_expr_access_get_dependent_access(expr); - return isl_union_map_from_map(access); + return pet_expr_access_get_dependent_access(expr, + pet_expr_access_may_write); } /* Return the must write access relation associated to "expr" * that maps pairs of domain iterations and argument values * to the corresponding accessed data elements. - * - * Since the accesses are currently represented by a single access relation, - * we return the entire access relation when "expr" is a write. */ __isl_give isl_union_map *pet_expr_access_get_dependent_must_write( __isl_keep pet_expr *expr) { - isl_map *access; - - if (!expr) - return NULL; - if (!pet_expr_access_is_write(expr)) - return empty_access_relation(expr); - access = pet_expr_access_get_dependent_access(expr); - return isl_union_map_from_map(access); + return pet_expr_access_get_dependent_access(expr, + pet_expr_access_must_write); } -/* Return the relation mapping domain iterations to all possibly - * accessed data elements. - * In particular, take the access relation and project out the values - * of the arguments, if any. +/* Return the relation of the given "type" mapping domain iterations + * to the accessed data elements. + * In particular, take the access relation and, in case of may_read + * or may_write, project out the values of the arguments, if any. + * In case of must_write, return the empty relation if there are + * any arguments. */ -__isl_give isl_map *pet_expr_access_get_may_access(__isl_keep pet_expr *expr) +__isl_give isl_union_map *pet_expr_access_get_access(__isl_keep pet_expr *expr, + enum pet_expr_access_type type) { - isl_map *access; + isl_union_map *access; isl_space *space; isl_map *map; @@ -2080,131 +2212,91 @@ __isl_give isl_map *pet_expr_access_get_may_access(__isl_keep pet_expr *expr) isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "not an access expression", return NULL); - access = pet_expr_access_get_dependent_access(expr); + if (expr->n_arg != 0 && type == pet_expr_access_must_write) { + space = pet_expr_access_get_parameter_space(expr); + return isl_union_map_empty(space); + } + + access = pet_expr_access_get_dependent_access(expr, type); if (expr->n_arg == 0) return access; - space = isl_space_domain(isl_map_get_space(access)); + space = isl_multi_pw_aff_get_space(expr->acc.index); + space = isl_space_domain(space); map = isl_map_universe(isl_space_unwrap(space)); map = isl_map_domain_map(map); - access = isl_map_apply_domain(access, map); + access = isl_union_map_apply_domain(access, + isl_union_map_from_map(map)); return access; } /* Return the relation mapping domain iterations to all possibly * read data elements. - * - * Since the accesses are currently represented by a single access relation, - * we return the may access relation if "expr" is a read and - * an empty relation if it is not. */ __isl_give isl_union_map *pet_expr_access_get_may_read( __isl_keep pet_expr *expr) { - if (!expr) - return NULL; - if (!pet_expr_access_is_read(expr)) - return empty_access_relation(expr); - return isl_union_map_from_map(pet_expr_access_get_may_access(expr)); + return pet_expr_access_get_access(expr, pet_expr_access_may_read); } /* Return the relation mapping domain iterations to all possibly * written data elements. - * - * Since the accesses are currently represented by a single access relation, - * we return the may access relation if "expr" is a write and - * an empty relation if it is not. */ __isl_give isl_union_map *pet_expr_access_get_may_write( __isl_keep pet_expr *expr) { - if (!expr) - return NULL; - if (!pet_expr_access_is_write(expr)) - return empty_access_relation(expr); - return isl_union_map_from_map(pet_expr_access_get_may_access(expr)); -} - -/* Return a relation mapping domain iterations to definitely - * accessed data elements, assuming the statement containing - * the expression is executed. - * - * If there are no arguments, then all elements are accessed. - * Otherwise, we conservatively return an empty relation. - */ -static __isl_give isl_map *pet_expr_access_get_must_access( - __isl_keep pet_expr *expr) -{ - isl_space *space; - - if (!expr) - return NULL; - if (expr->type != pet_expr_access) - isl_die(pet_expr_get_ctx(expr), isl_error_invalid, - "not an access expression", return NULL); - - if (expr->n_arg == 0) - return pet_expr_access_get_dependent_access(expr); - - space = isl_multi_pw_aff_get_space(expr->acc.index); - space = isl_space_domain_factor_domain(space); - - return isl_map_empty(space); + return pet_expr_access_get_access(expr, pet_expr_access_may_write); } /* Return a relation mapping domain iterations to definitely * written data elements, assuming the statement containing * the expression is executed. - * - * Since the accesses are currently represented by a single access relation, - * we return the must access relation if "expr" is a write and - * an empty relation if it is not. */ __isl_give isl_union_map *pet_expr_access_get_must_write( __isl_keep pet_expr *expr) { - if (!expr) - return NULL; - if (!pet_expr_access_is_write(expr)) - return empty_access_relation(expr); - return isl_union_map_from_map(pet_expr_access_get_must_access(expr)); + return pet_expr_access_get_access(expr, pet_expr_access_must_write); } -/* Return the relation mapping domain iterations to all possibly - * read data elements, with its domain tagged with the reference +/* Return the relation of the given "type" mapping domain iterations to + * accessed data elements, with its domain tagged with the reference * identifier. */ -__isl_give isl_union_map *pet_expr_access_get_tagged_may_read( - __isl_keep pet_expr *expr) +static __isl_give isl_union_map *pet_expr_access_get_tagged_access( + __isl_keep pet_expr *expr, enum pet_expr_access_type type) { isl_union_map *access; if (!expr) return NULL; - access = pet_expr_access_get_may_read(expr); + access = pet_expr_access_get_access(expr, type); access = pet_expr_tag_access(expr, access); return access; } /* Return the relation mapping domain iterations to all possibly + * read data elements, with its domain tagged with the reference + * identifier. + */ +__isl_give isl_union_map *pet_expr_access_get_tagged_may_read( + __isl_keep pet_expr *expr) +{ + return pet_expr_access_get_tagged_access(expr, + pet_expr_access_may_read); +} + +/* Return the relation mapping domain iterations to all possibly * written data elements, with its domain tagged with the reference * identifier. */ __isl_give isl_union_map *pet_expr_access_get_tagged_may_write( __isl_keep pet_expr *expr) { - isl_union_map *access; - - if (!expr) - return NULL; - - access = pet_expr_access_get_may_write(expr); - access = pet_expr_tag_access(expr, access); - - return access; + return pet_expr_access_get_tagged_access(expr, + pet_expr_access_may_write); } /* Return the operation type of operation expression "expr". @@ -3176,9 +3268,20 @@ void pet_expr_dump_with_indent(__isl_keep pet_expr *expr, int indent) fprintf(stderr, "%*swrite: %d\n", indent + 2, "", expr->acc.write); } - if (expr->acc.access) { - fprintf(stderr, "%*saccess: ", indent + 2, ""); - isl_map_dump(expr->acc.access); + if (expr->acc.access[pet_expr_access_may_read]) { + fprintf(stderr, "%*smay_read: ", indent + 2, ""); + isl_union_map_dump( + expr->acc.access[pet_expr_access_may_read]); + } + if (expr->acc.access[pet_expr_access_may_write]) { + fprintf(stderr, "%*smay_write: ", indent + 2, ""); + isl_union_map_dump( + expr->acc.access[pet_expr_access_may_write]); + } + if (expr->acc.access[pet_expr_access_must_write]) { + fprintf(stderr, "%*smust_write: ", indent + 2, ""); + isl_union_map_dump( + expr->acc.access[pet_expr_access_must_write]); } for (i = 0; i < expr->n_arg; ++i) pet_expr_dump_with_indent(expr->args[i], indent + 2); diff --git a/expr.h b/expr.h index 5ad5858..14dc0bb 100644 --- a/expr.h +++ b/expr.h @@ -4,6 +4,7 @@ #include #include "context.h" +#include "expr_access_type.h" #if defined(__cplusplus) extern "C" { @@ -27,17 +28,18 @@ extern "C" { * For each access expression inside the body of a statement, acc.ref_id * is a unique reference identifier. * acc.index represents the index expression, while acc.access - * represents the corresponding access relation. + * represents the corresponding access relations. * The output dimension of the index expression may be smaller * than the number of dimensions of the accessed array (recorded * in acc.depth). * The target space of the access relation, on the other hand, * is equal to the array space. - * acc.access may be NULL if it can be derived directly from - * acc.index and acc.depth in construct_access_relation. - * That is, acc.access may be NULL if there are no additional - * constraints on the access relations. - * Both acc.index and acc.access usually map an iteration space + * The entries in acc.access may be NULL if they can be derived directly from + * acc.index and acc.depth in construct_access_relation or if they are + * irrelevant for the given type of access. + * In particular, the entries of acc.access may be NULL if there are + * no additional constraints on the access relations. + * Both acc.index and the acc.access entries usually map an iteration space * to a (partial) data space. * If the access has arguments, however, then the domain of the * mapping is a wrapped mapping from the iteration space @@ -62,6 +64,8 @@ extern "C" { * Alternatively, the expression may be marked "kill", in which case it * is the argument of a kill operation and represents the set of * killed array elements. Such accesses are marked neither read nor write. + * Since a kill can never be a read (or a write), the killed access + * relation is stored in the same location as the may read access relation. * * A double is represented as both an (approximate) value "val" and * a string representation "s". @@ -80,12 +84,12 @@ struct pet_expr { union { struct { isl_id *ref_id; - isl_map *access; isl_multi_pw_aff *index; int depth; unsigned read : 1; unsigned write : 1; unsigned kill : 1; + isl_union_map *access[pet_expr_access_end]; } acc; enum pet_op_type op; char *name; @@ -149,8 +153,10 @@ __isl_give pet_expr *pet_expr_map_access(__isl_take pet_expr *expr, __isl_give pet_expr *(*fn)(__isl_take pet_expr *expr, void *user), void *user); +__isl_give isl_union_map *pet_expr_access_get_access(__isl_keep pet_expr *expr, + enum pet_expr_access_type type); __isl_give pet_expr *pet_expr_access_set_access(__isl_take pet_expr *expr, - __isl_take isl_map *access); + enum pet_expr_access_type type, __isl_take isl_union_map *access); __isl_give pet_expr *pet_expr_access_set_index(__isl_take pet_expr *expr, __isl_take isl_multi_pw_aff *index); diff --git a/expr_access_type.h b/expr_access_type.h index db5b6bf..bbac51d 100644 --- a/expr_access_type.h +++ b/expr_access_type.h @@ -7,8 +7,11 @@ extern "C" { enum pet_expr_access_type { pet_expr_access_may_read, + pet_expr_access_begin = pet_expr_access_may_read, + pet_expr_access_fake_killed = pet_expr_access_may_read, pet_expr_access_may_write, pet_expr_access_must_write, + pet_expr_access_end, pet_expr_access_killed }; diff --git a/expr_arg.c b/expr_arg.c index af8ab99..ebea83b 100644 --- a/expr_arg.c +++ b/expr_arg.c @@ -200,6 +200,9 @@ __isl_give pet_expr *pet_expr_access_project_out_arg(__isl_take pet_expr *expr, int i, n; isl_space *space, *dom, *ran; isl_multi_aff *ma1, *ma2; + enum pet_expr_access_type type; + isl_map *map; + isl_union_map *umap; expr = pet_expr_cow(expr); if (!expr) @@ -216,15 +219,21 @@ __isl_give pet_expr *pet_expr_access_project_out_arg(__isl_take pet_expr *expr, isl_dim_in, dim + pos, 1)) isl_die(pet_expr_get_ctx(expr), isl_error_invalid, "cannot project out", return pet_expr_free(expr)); - if (expr->acc.access) { - expr->acc.access = - isl_map_eliminate(expr->acc.access, - isl_dim_in, dim + pos, 1); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + space = isl_multi_pw_aff_get_domain_space(expr->acc.index); + map = isl_map_identity(isl_space_map_from_set(space)); + map = isl_map_eliminate(map, isl_dim_out, dim + pos, 1); + umap = isl_union_map_from_map(map); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + isl_union_map_apply_domain(expr->acc.access[type], + isl_union_map_copy(umap)); + if (!expr->acc.access[type]) + break; } - if (!expr->acc.index) + isl_union_map_free(umap); + if (!expr->acc.index || type < pet_expr_access_end) return pet_expr_free(expr); space = isl_multi_pw_aff_get_domain_space(expr->acc.index); diff --git a/nest.c b/nest.c index 9459a40..45ca267 100644 --- a/nest.c +++ b/nest.c @@ -126,6 +126,20 @@ int pet_nested_in_map(__isl_keep isl_map *map, int pos) return nested; } +/* Does parameter "pos" of "umap" refer to a nested access? + */ +static int pet_nested_in_union_map(__isl_keep isl_union_map *umap, int pos) +{ + int nested; + isl_id *id; + + id = isl_union_map_get_dim_id(umap, isl_dim_param, pos); + nested = pet_nested_in_id(id); + isl_id_free(id); + + return nested; +} + /* Does "space" involve any parameters that refer to nested accesses? */ int pet_nested_any_in_space(__isl_keep isl_space *space) @@ -243,6 +257,23 @@ static __isl_give isl_map *pet_nested_remove_from_map(__isl_take isl_map *map) return map; } +/* Remove all parameters from "umap" that refer to nested accesses. + */ +static __isl_give isl_union_map *pet_nested_remove_from_union_map( + __isl_take isl_union_map *umap) +{ + int i; + int nparam; + + nparam = isl_union_map_dim(umap, isl_dim_param); + for (i = nparam - 1; i >= 0; --i) + if (pet_nested_in_union_map(umap, i)) + umap = isl_union_map_project_out(umap, + isl_dim_param, i, 1); + + return umap; +} + /* Remove all parameters from "mpa" that refer to nested accesses. */ static __isl_give isl_multi_pw_aff *pet_nested_remove_from_multi_pw_aff( @@ -264,24 +295,28 @@ static __isl_give isl_multi_pw_aff *pet_nested_remove_from_multi_pw_aff( return mpa; } -/* Remove all parameters from the index expression and access relation of "expr" - * that refer to nested accesses. +/* Remove all parameters from the index expression and + * access relations of "expr" that refer to nested accesses. */ static __isl_give pet_expr *expr_remove_nested_parameters( __isl_take pet_expr *expr, void *user) { + enum pet_expr_access_type type; + expr = pet_expr_cow(expr); if (!expr) return NULL; - if (expr->acc.access) { - expr->acc.access = pet_nested_remove_from_map(expr->acc.access); - if (!expr->acc.access) - expr->acc.index = - isl_multi_pw_aff_free(expr->acc.index); + for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) { + if (!expr->acc.access[type]) + continue; + expr->acc.access[type] = + pet_nested_remove_from_union_map(expr->acc.access[type]); + if (!expr->acc.access[type]) + break; } expr->acc.index = pet_nested_remove_from_multi_pw_aff(expr->acc.index); - if (!expr->acc.index) + if (type < pet_expr_access_end || !expr->acc.index) return pet_expr_free(expr); return expr; diff --git a/parse.c b/parse.c index 35f8039..200b6ec 100644 --- a/parse.c +++ b/parse.c @@ -390,8 +390,8 @@ static __isl_give pet_expr *extract_expr_double(isl_ctx *ctx, * * The depth of the access is initialized by pet_expr_access_set_index. * Any explicitly specified depth therefore needs to be set after - * setting the index expression. Similiarly, the access relation (if any) - * needs to be set after setting the depth. + * setting the index expression. Similiarly, the access relations (if any) + * need to be set after setting the depth. */ static __isl_give pet_expr *extract_expr_access(isl_ctx *ctx, yaml_document_t *document, yaml_node_t *node, __isl_take pet_expr *expr) @@ -432,9 +432,22 @@ static __isl_give pet_expr *extract_expr_access(isl_ctx *ctx, isl_die(ctx, isl_error_invalid, "expecting scalar key", return pet_expr_free(expr)); - if (!strcmp((char *) key->data.scalar.value, "relation")) + if (!strcmp((char *) key->data.scalar.value, "may_read")) expr = pet_expr_access_set_access(expr, - extract_map(ctx, document, value)); + pet_expr_access_may_read, + extract_union_map(ctx, document, value)); + if (!strcmp((char *) key->data.scalar.value, "may_write")) + expr = pet_expr_access_set_access(expr, + pet_expr_access_may_write, + extract_union_map(ctx, document, value)); + if (!strcmp((char *) key->data.scalar.value, "must_write")) + expr = pet_expr_access_set_access(expr, + pet_expr_access_must_write, + extract_union_map(ctx, document, value)); + if (!strcmp((char *) key->data.scalar.value, "killed")) + expr = pet_expr_access_set_access(expr, + pet_expr_access_killed, + extract_union_map(ctx, document, value)); if (!strcmp((char *) key->data.scalar.value, "reference")) expr = pet_expr_access_set_ref_id(expr, extract_id(ctx, document, value)); diff --git a/scop.c b/scop.c index 280d9d7..72beacb 100644 --- a/scop.c +++ b/scop.c @@ -2343,24 +2343,24 @@ struct pet_scop *pet_scop_align_params(struct pet_scop *scop) return scop; } -/* Add the access relation of the access expression "expr" to "accesses" and - * return the result. +/* Add the access relation of the give "type" of the access expression "expr" + * to "accesses" and return the result. * The domain of the access relation is intersected with "domain". * If "tag" is set, then the access relation is tagged with * the corresponding reference identifier. */ static __isl_give isl_union_map *expr_collect_access(__isl_keep pet_expr *expr, - int tag, __isl_take isl_union_map *accesses, __isl_keep isl_set *domain) + enum pet_expr_access_type type, int tag, + __isl_take isl_union_map *accesses, __isl_keep isl_union_set *domain) { - isl_map *access; - isl_union_map *umap; + isl_union_map *access; - access = pet_expr_access_get_may_access(expr); - access = isl_map_intersect_domain(access, isl_set_copy(domain)); - umap = isl_union_map_from_map(access); + access = pet_expr_access_get_access(expr, type); + access = isl_union_map_intersect_domain(access, + isl_union_set_copy(domain)); if (tag) - umap = pet_expr_tag_access(expr, umap); - return isl_union_map_union(accesses, umap); + access = pet_expr_tag_access(expr, access); + return isl_union_map_union(accesses, access); } /* Internal data structure for expr_collect_accesses. @@ -2374,7 +2374,7 @@ static __isl_give isl_union_map *expr_collect_access(__isl_keep pet_expr *expr, struct pet_expr_collect_accesses_data { enum pet_expr_access_type type; int tag; - isl_set *domain; + isl_union_set *domain; isl_union_map *accesses; }; @@ -2411,7 +2411,8 @@ static int expr_collect_accesses(__isl_keep pet_expr *expr, void *user) if ((data->type == pet_expr_access_may_read && expr->acc.read) || ((data->type == pet_expr_access_may_write || data->type == pet_expr_access_must_write) && expr->acc.write)) - data->accesses = expr_collect_access(expr, data->tag, + data->accesses = expr_collect_access(expr, + data->type, data->tag, data->accesses, data->domain); return data->accesses ? 0 : -1; @@ -2439,6 +2440,7 @@ static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt, { struct pet_expr_collect_accesses_data data = { type, tag }; int must; + isl_set *domain; if (!stmt) return NULL; @@ -2456,14 +2458,16 @@ static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt, if (must && pet_tree_get_type(stmt->body) != pet_tree_expr) return data.accesses; - data.domain = drop_arguments(isl_set_copy(stmt->domain)); + domain = drop_arguments(isl_set_copy(stmt->domain)); + data.domain = isl_union_set_from_set(domain); if (type == pet_expr_access_killed) { pet_expr *body, *arg; body = pet_tree_expr_get_expr(stmt->body); arg = pet_expr_get_arg(body, 0); - data.accesses = expr_collect_access(arg, tag, + data.accesses = expr_collect_access(arg, + pet_expr_access_killed, tag, data.accesses, data.domain); pet_expr_free(arg); pet_expr_free(body); @@ -2471,7 +2475,7 @@ static __isl_give isl_union_map *stmt_collect_accesses(struct pet_stmt *stmt, &expr_collect_accesses, &data) < 0) data.accesses = isl_union_map_free(data.accesses); - isl_set_free(data.domain); + isl_union_set_free(data.domain); return data.accesses; } diff --git a/tests/autodetect/decl.scop b/tests/autodetect/decl.scop index e114551..7c69329 100644 --- a/tests/autodetect/decl.scop +++ b/tests/autodetect/decl.scop @@ -44,7 +44,7 @@ statements: operation: kill arguments: - type: access - relation: '{ S_1[] -> c[] }' + killed: '{ S_1[] -> c[] }' index: '{ S_1[] -> c[] }' reference: __pet_ref_1 kill: 1 diff --git a/tests/break4.scop b/tests/break4.scop index cd64391..ff9d222 100644 --- a/tests/break4.scop +++ b/tests/break4.scop @@ -153,7 +153,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ S_2[i, j] -> __pet_test_0[i, j] : j >= 81 }' + may_read: '{ S_2[i, j] -> __pet_test_0[i, j] : j >= 81 }' index: '{ S_2[i, j] -> __pet_test_0[(i), (j)] }' reference: __pet_ref_7 read: 1 @@ -377,7 +377,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_8[i, j] -> [0]] -> __pet_test_4[i, j] }' + may_read: '{ [S_8[i, j] -> [0]] -> __pet_test_4[i, j] }' index: '{ [S_8[i, j] -> [__pet_test_3]] -> __pet_test_4[(i), (j)] }' reference: __pet_ref_39 read: 1 @@ -465,7 +465,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_10[i, j] -> [1]] -> __pet_test_5[i, j] }' + may_read: '{ [S_10[i, j] -> [1]] -> __pet_test_5[i, j] }' index: '{ [S_10[i, j] -> [__pet_test_2]] -> __pet_test_5[(i), (j)] }' reference: __pet_ref_50 read: 1 @@ -515,7 +515,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_11[i, j] -> [1]] -> __pet_test_3[i, j] }' + may_read: '{ [S_11[i, j] -> [1]] -> __pet_test_3[i, j] }' index: '{ [S_11[i, j] -> [__pet_test_2]] -> __pet_test_3[(i), (j)] }' reference: __pet_ref_57 read: 1 @@ -570,7 +570,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_12[i, j] -> [0]] -> __pet_test_6[i, j] }' + may_read: '{ [S_12[i, j] -> [0]] -> __pet_test_6[i, j] }' index: '{ [S_12[i, j] -> [__pet_test_1]] -> __pet_test_6[(i), (j)] }' reference: __pet_ref_64 read: 1 @@ -615,7 +615,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_13[i, j] -> [0]] -> __pet_test_7[i, j] }' + may_read: '{ [S_13[i, j] -> [0]] -> __pet_test_7[i, j] }' index: '{ [S_13[i, j] -> [__pet_test_1]] -> __pet_test_7[(i), (j)] }' reference: __pet_ref_70 read: 1 @@ -687,7 +687,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_15[i, j] -> [0]] -> __pet_test_10[i, j] }' + may_read: '{ [S_15[i, j] -> [0]] -> __pet_test_10[i, j] }' index: '{ [S_15[i, j] -> [__pet_test_8]] -> __pet_test_10[(i), (j)] }' reference: __pet_ref_79 read: 1 @@ -732,7 +732,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_16[i, j] -> [0]] -> __pet_test_10[i, j] }' + may_read: '{ [S_16[i, j] -> [0]] -> __pet_test_10[i, j] }' index: '{ [S_16[i, j] -> [__pet_test_9]] -> __pet_test_10[(i), (j)] }' reference: __pet_ref_85 read: 1 diff --git a/tests/break6.scop b/tests/break6.scop index 93f9fbc..b8d6862 100644 --- a/tests/break6.scop +++ b/tests/break6.scop @@ -235,7 +235,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_6[t] -> [0]] -> __pet_test_2[t] }' + may_read: '{ [S_6[t] -> [0]] -> __pet_test_2[t] }' index: '{ [S_6[t] -> [__pet_test_1]] -> __pet_test_2[(t)] }' reference: __pet_ref_25 read: 1 diff --git a/tests/conditional_assignment.scop b/tests/conditional_assignment.scop index 875cce2..682b4c5 100644 --- a/tests/conditional_assignment.scop +++ b/tests/conditional_assignment.scop @@ -155,7 +155,7 @@ statements: name: f arguments: - type: access - relation: '[N, M] -> { [S_4[i] -> [i1]] -> A[i + i1, o1] : i1 >= -i and + may_read: '[N, M] -> { [S_4[i] -> [i1]] -> A[i + i1, o1] : i1 >= -i and i1 <= -1 + N - i }' index: '[N, M] -> { [S_4[i] -> [i1]] -> A[((i + i1) : i1 >= -i)] }' depth: 2 @@ -164,7 +164,7 @@ statements: write: 0 arguments: - type: access - relation: '[N, M] -> { S_4[i] -> in2[i] }' + may_read: '[N, M] -> { S_4[i] -> in2[i] }' index: '[N, M] -> { S_4[i] -> in2[(i)] }' reference: __pet_ref_11 read: 1 diff --git a/tests/conditional_assignment2.scop b/tests/conditional_assignment2.scop index a56e874..6ed6ca2 100644 --- a/tests/conditional_assignment2.scop +++ b/tests/conditional_assignment2.scop @@ -171,7 +171,7 @@ statements: name: f arguments: - type: access - relation: '[M, N] -> { [S_5[i] -> [i1]] -> A[i + i1, o1] : i1 >= -i and + may_read: '[M, N] -> { [S_5[i] -> [i1]] -> A[i + i1, o1] : i1 >= -i and i1 <= -1 + N - i }' index: '[M, N] -> { [S_5[i] -> [i1]] -> A[((i + i1) : i1 >= -i)] }' depth: 2 @@ -180,7 +180,7 @@ statements: write: 0 arguments: - type: access - relation: '[M, N] -> { S_5[i] -> in2[] }' + may_read: '[M, N] -> { S_5[i] -> in2[] }' index: '[M, N] -> { S_5[i] -> in2[] }' reference: __pet_ref_12 read: 1 diff --git a/tests/continue2.scop b/tests/continue2.scop index a33d57a..67dd046 100644 --- a/tests/continue2.scop +++ b/tests/continue2.scop @@ -187,7 +187,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_5[i] -> [1]] -> __pet_test_1[i] }' + may_read: '{ [S_5[i] -> [1]] -> __pet_test_1[i] }' index: '{ [S_5[i] -> [__pet_test_0]] -> __pet_test_1[(i)] }' reference: __pet_ref_16 read: 1 @@ -267,7 +267,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ S_8[i] -> __pet_test_2[i] : i <= 59 }' + may_read: '{ S_8[i] -> __pet_test_2[i] : i <= 59 }' index: '{ S_8[i] -> __pet_test_2[(i)] }' reference: __pet_ref_24 read: 1 diff --git a/tests/continue3.scop b/tests/continue3.scop index 041752c..bdf718e 100644 --- a/tests/continue3.scop +++ b/tests/continue3.scop @@ -175,7 +175,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_5[i] -> [0]] -> __pet_test_1[i] }' + may_read: '{ [S_5[i] -> [0]] -> __pet_test_1[i] }' index: '{ [S_5[i] -> [__pet_test_0]] -> __pet_test_1[(i)] }' reference: __pet_ref_15 read: 1 diff --git a/tests/continue4.scop b/tests/continue4.scop index f5ba320..2b0990d 100644 --- a/tests/continue4.scop +++ b/tests/continue4.scop @@ -139,7 +139,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ [S_4[i] -> [0]] -> [0] : i >= 58 or i <= 56; [S_4[57] -> [0]] + may_read: '{ [S_4[i] -> [0]] -> [0] : i >= 58 or i <= 56; [S_4[57] -> [0]] -> [1] }' index: '{ [S_4[i] -> [__pet_test_0]] -> [((1) : i = 57; (0) : i <= 56 or i >= 58)] }' diff --git a/tests/continue5.scop b/tests/continue5.scop index 1b8b29e..105e177 100644 --- a/tests/continue5.scop +++ b/tests/continue5.scop @@ -127,7 +127,7 @@ statements: read: 1 write: 0 - type: access - relation: '{ S_4[i] -> __pet_test_0[i] : i >= 58 or i <= 56 }' + may_read: '{ S_4[i] -> __pet_test_0[i] : i >= 58 or i <= 56 }' index: '{ S_4[i] -> __pet_test_0[(i)] }' reference: __pet_ref_9 read: 1 diff --git a/tests/decl.scop b/tests/decl.scop index adf675e..9d6c640 100644 --- a/tests/decl.scop +++ b/tests/decl.scop @@ -50,7 +50,7 @@ statements: operation: kill arguments: - type: access - relation: '[N, K, M] -> { S_1[i, j, k] -> t[] }' + killed: '[N, K, M] -> { S_1[i, j, k] -> t[] }' index: '[N, K, M] -> { S_1[i, j, k] -> t[] }' reference: __pet_ref_1 kill: 1 @@ -113,7 +113,7 @@ statements: operation: kill arguments: - type: access - relation: '[N, K, M] -> { S_3[i, j, k] -> t[] }' + killed: '[N, K, M] -> { S_3[i, j, k] -> t[] }' index: '[N, K, M] -> { S_3[i, j, k] -> t[] }' reference: __pet_ref_7 kill: 1 diff --git a/tests/decl2.scop b/tests/decl2.scop index a285c88..432ad5f 100644 --- a/tests/decl2.scop +++ b/tests/decl2.scop @@ -20,7 +20,7 @@ statements: operation: kill arguments: - type: access - relation: '[N] -> { S_0[] -> A[o0] : o0 >= 0 and o0 <= -1 + N }' + killed: '[N] -> { S_0[] -> A[o0] : o0 >= 0 and o0 <= -1 + N }' index: '{ S_0[] -> A[] }' depth: 1 reference: __pet_ref_0 diff --git a/tests/decl3.scop b/tests/decl3.scop index 521cb46..a24b4f7 100644 --- a/tests/decl3.scop +++ b/tests/decl3.scop @@ -40,7 +40,7 @@ statements: operation: kill arguments: - type: access - relation: '{ S_1[] -> A[o0] : o0 >= 0 and o0 <= 4 }' + killed: '{ S_1[] -> A[o0] : o0 >= 0 and o0 <= 4 }' index: '{ S_1[] -> A[] }' depth: 1 reference: __pet_ref_1 diff --git a/tests/encapsulate/for_while.scop b/tests/encapsulate/for_while.scop index 9642e34..a6af3f6 100644 --- a/tests/encapsulate/for_while.scop +++ b/tests/encapsulate/for_while.scop @@ -39,7 +39,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_4[x1] -> x2[] }' + killed: '[n] -> { S_4[x1] -> x2[] }' index: '[n] -> { S_4[x1] -> x2[] }' reference: __pet_ref_1 kill: 1 @@ -107,7 +107,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_5[x1] -> x2[] }' + killed: '[n] -> { S_5[x1] -> x2[] }' index: '[n] -> { S_5[x1] -> x2[] }' reference: __pet_ref_7 kill: 1 diff --git a/tests/encapsulate/independent5.scop b/tests/encapsulate/independent5.scop index 99b7dae..1abc143 100644 --- a/tests/encapsulate/independent5.scop +++ b/tests/encapsulate/independent5.scop @@ -31,7 +31,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_7[i] -> j[] }' + killed: '[n] -> { S_7[i] -> j[] }' index: '[n] -> { S_7[i] -> j[] }' reference: __pet_ref_0 kill: 1 @@ -102,7 +102,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_8[i] -> j[] }' + killed: '[n] -> { S_8[i] -> j[] }' index: '[n] -> { S_8[i] -> j[] }' reference: __pet_ref_8 kill: 1 diff --git a/tests/encapsulate/inf_break.scop b/tests/encapsulate/inf_break.scop index 34408f3..417c9a3 100644 --- a/tests/encapsulate/inf_break.scop +++ b/tests/encapsulate/inf_break.scop @@ -23,7 +23,7 @@ statements: operation: kill arguments: - type: access - relation: '{ S_5[] -> s[] }' + killed: '{ S_5[] -> s[] }' index: '{ S_5[] -> s[] }' reference: __pet_ref_0 kill: 1 @@ -74,7 +74,7 @@ statements: operation: kill arguments: - type: access - relation: '{ S_6[] -> s[] }' + killed: '{ S_6[] -> s[] }' index: '{ S_6[] -> s[] }' reference: __pet_ref_4 kill: 1 diff --git a/tests/for_while_inc2.scop b/tests/for_while_inc2.scop index bbc8b9d..928efe7 100644 --- a/tests/for_while_inc2.scop +++ b/tests/for_while_inc2.scop @@ -45,7 +45,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_5[x1] -> x2[] }' + killed: '[n] -> { S_5[x1] -> x2[] }' index: '[n] -> { S_5[x1] -> x2[] }' reference: __pet_ref_1 kill: 1 @@ -161,7 +161,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_6[x1] -> x2[] }' + killed: '[n] -> { S_6[x1] -> x2[] }' index: '[n] -> { S_6[x1] -> x2[] }' reference: __pet_ref_13 kill: 1 diff --git a/tests/for_while_inc3.scop b/tests/for_while_inc3.scop index 913ff23..39af9b6 100644 --- a/tests/for_while_inc3.scop +++ b/tests/for_while_inc3.scop @@ -45,7 +45,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_5[x1] -> x2[] }' + killed: '[n] -> { S_5[x1] -> x2[] }' index: '[n] -> { S_5[x1] -> x2[] }' reference: __pet_ref_1 kill: 1 @@ -161,7 +161,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_6[x1] -> x2[] }' + killed: '[n] -> { S_6[x1] -> x2[] }' index: '[n] -> { S_6[x1] -> x2[] }' reference: __pet_ref_13 kill: 1 diff --git a/tests/for_while_init.scop b/tests/for_while_init.scop index 74abaee..2fcdc8b 100644 --- a/tests/for_while_init.scop +++ b/tests/for_while_init.scop @@ -45,7 +45,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_5[x1] -> x2[] }' + killed: '[n] -> { S_5[x1] -> x2[] }' index: '[n] -> { S_5[x1] -> x2[] }' reference: __pet_ref_1 kill: 1 @@ -161,7 +161,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_6[x1] -> x2[] }' + killed: '[n] -> { S_6[x1] -> x2[] }' index: '[n] -> { S_6[x1] -> x2[] }' reference: __pet_ref_13 kill: 1 diff --git a/tests/for_while_init2.scop b/tests/for_while_init2.scop index 0703fd8..718229b 100644 --- a/tests/for_while_init2.scop +++ b/tests/for_while_init2.scop @@ -45,7 +45,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_5[x1] -> x2[] }' + killed: '[n] -> { S_5[x1] -> x2[] }' index: '[n] -> { S_5[x1] -> x2[] }' reference: __pet_ref_1 kill: 1 @@ -164,7 +164,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_6[x1] -> x2[] }' + killed: '[n] -> { S_6[x1] -> x2[] }' index: '[n] -> { S_6[x1] -> x2[] }' reference: __pet_ref_14 kill: 1 diff --git a/tests/for_while_init3.scop b/tests/for_while_init3.scop index 20d51ef..2ac4453 100644 --- a/tests/for_while_init3.scop +++ b/tests/for_while_init3.scop @@ -49,7 +49,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_5[i] -> j[] }' + killed: '[n] -> { S_5[i] -> j[] }' index: '[n] -> { S_5[i] -> j[] }' reference: __pet_ref_1 kill: 1 @@ -154,7 +154,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_6[i] -> j[] }' + killed: '[n] -> { S_6[i] -> j[] }' index: '[n] -> { S_6[i] -> j[] }' reference: __pet_ref_11 kill: 1 diff --git a/tests/forward_substitution3.scop b/tests/forward_substitution3.scop index 0a7329e..ba2d209 100644 --- a/tests/forward_substitution3.scop +++ b/tests/forward_substitution3.scop @@ -30,7 +30,7 @@ statements: operation: kill arguments: - type: access - relation: '{ S_0[] -> b[] }' + killed: '{ S_0[] -> b[] }' index: '{ S_0[] -> b[] }' reference: __pet_ref_0 kill: 1 @@ -60,7 +60,7 @@ statements: operation: kill arguments: - type: access - relation: '{ S_2[] -> c[] }' + killed: '{ S_2[] -> c[] }' index: '{ S_2[] -> c[] }' reference: __pet_ref_2 kill: 1 diff --git a/tests/independent3.scop b/tests/independent3.scop index f182446..3f045a1 100644 --- a/tests/independent3.scop +++ b/tests/independent3.scop @@ -28,7 +28,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_0[i, j] -> t[] }' + killed: '[n] -> { S_0[i, j] -> t[] }' index: '[n] -> { S_0[i, j] -> t[] }' reference: __pet_ref_0 kill: 1 @@ -97,7 +97,7 @@ statements: operation: kill arguments: - type: access - relation: '[n] -> { S_2[i, j] -> t[] }' + killed: '[n] -> { S_2[i, j] -> t[] }' index: '[n] -> { S_2[i, j] -> t[] }' reference: __pet_ref_7 kill: 1 -- 2.11.4.GIT