From 8dc329ec88a67ed3f81d0b30dbbf3cca7eafeedc Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 7 Mar 2014 11:40:00 +0100 Subject: [PATCH] move pet_scop_extract_nested to nest.c All functionality related to parameters with nested accesses should end up in nest.c. We will also be able to reuse this function when we move to extracting a pet_scop from an intermediate pet_tree structure. Signed-off-by: Sven Verdoolaege --- nest.c | 216 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ nest.h | 1 + scan.cc | 219 +--------------------------------------------------------------- scan.h | 4 -- 4 files changed, 219 insertions(+), 221 deletions(-) diff --git a/nest.c b/nest.c index f73ba6c..2cc975c 100644 --- a/nest.c +++ b/nest.c @@ -653,3 +653,219 @@ error: free(param2pos); return pet_expr_free(expr); } + +/* Precompose the access relation and the index expression associated + * to "expr" with the function pointed to by "user", + * thereby embedding the access relation in the domain of this function. + * The initial domain of the access relation and the index expression + * is the zero-dimensional domain. + */ +static __isl_give pet_expr *embed_access(__isl_take pet_expr *expr, void *user) +{ + isl_multi_aff *ma = (isl_multi_aff *) user; + + return pet_expr_access_pullback_multi_aff(expr, isl_multi_aff_copy(ma)); +} + +/* Precompose all access relations in "expr" with "ma", thereby + * embedding them in the domain of "ma". + */ +static __isl_give pet_expr *embed(__isl_take pet_expr *expr, + __isl_keep isl_multi_aff *ma) +{ + return pet_expr_map_access(expr, &embed_access, ma); +} + +/* For each nested access parameter in the domain of "stmt", + * construct a corresponding pet_expr, place it before the original + * elements in stmt->args and record its position in "param2pos". + * n is the number of nested access parameters. + */ +struct pet_stmt *pet_stmt_extract_nested(struct pet_stmt *stmt, int n, + int *param2pos) +{ + int i; + isl_ctx *ctx; + isl_space *space; + int n_arg; + pet_expr **args; + + ctx = isl_set_get_ctx(stmt->domain); + + n_arg = stmt->n_arg; + args = isl_calloc_array(ctx, pet_expr *, n + n_arg); + if (!args) + goto error; + + space = isl_set_get_space(stmt->domain); + n_arg = pet_extract_nested_from_space(space, 0, args, param2pos); + isl_space_free(space); + + if (n_arg < 0) + goto error; + + for (i = 0; i < stmt->n_arg; ++i) + args[n_arg + i] = stmt->args[i]; + free(stmt->args); + stmt->args = args; + stmt->n_arg += n_arg; + + return stmt; +error: + if (args) { + for (i = 0; i < n; ++i) + pet_expr_free(args[i]); + free(args); + } + pet_stmt_free(stmt); + return NULL; +} + +/* Check whether any of the arguments i of "stmt" starting at position "n" + * is equal to one of the first "n" arguments j. + * If so, combine the constraints on arguments i and j and remove + * argument i. + */ +static struct pet_stmt *remove_duplicate_arguments(struct pet_stmt *stmt, int n) +{ + int i, j; + isl_map *map; + + if (!stmt) + return NULL; + if (n == 0) + return stmt; + if (n == stmt->n_arg) + return stmt; + + map = isl_set_unwrap(stmt->domain); + + for (i = stmt->n_arg - 1; i >= n; --i) { + for (j = 0; j < n; ++j) + if (pet_expr_is_equal(stmt->args[i], stmt->args[j])) + break; + if (j >= n) + continue; + + map = isl_map_equate(map, isl_dim_out, i, isl_dim_out, j); + map = isl_map_project_out(map, isl_dim_out, i, 1); + + pet_expr_free(stmt->args[i]); + for (j = i; j + 1 < stmt->n_arg; ++j) + stmt->args[j] = stmt->args[j + 1]; + stmt->n_arg--; + } + + stmt->domain = isl_map_wrap(map); + if (!stmt->domain) + goto error; + return stmt; +error: + pet_stmt_free(stmt); + return NULL; +} + +/* Look for parameters in the iteration domain of "stmt" that + * refer to nested accesses. In particular, these are + * parameters with name "__pet_expr". + * + * If there are any such parameters, then as many extra variables + * (after identifying identical nested accesses) are inserted in the + * range of the map wrapped inside the domain, before the original variables. + * If the original domain is not a wrapped map, then a new wrapped + * map is created with zero output dimensions. + * The parameters are then equated to the corresponding output dimensions + * and subsequently projected out, from the iteration domain, + * the schedule and the access relations. + * For each of the output dimensions, a corresponding argument + * expression is inserted. Initially they are created with + * a zero-dimensional domain, so they have to be embedded + * in the current iteration domain. + * param2pos maps the position of the parameter to the position + * of the corresponding output dimension in the wrapped map. + */ +struct pet_stmt *pet_stmt_resolve_nested(struct pet_stmt *stmt) +{ + int i, n; + int pos; + int nparam; + unsigned n_arg; + isl_ctx *ctx; + isl_map *map; + isl_space *space; + isl_multi_aff *ma; + int *param2pos; + + if (!stmt) + return NULL; + + n = pet_nested_n_in_set(stmt->domain); + if (n == 0) + return stmt; + + ctx = isl_set_get_ctx(stmt->domain); + + n_arg = stmt->n_arg; + nparam = isl_set_dim(stmt->domain, isl_dim_param); + param2pos = isl_alloc_array(ctx, int, nparam); + stmt = pet_stmt_extract_nested(stmt, n, param2pos); + if (!stmt) { + free(param2pos); + return NULL; + } + + n = stmt->n_arg - n_arg; + if (isl_set_is_wrapping(stmt->domain)) + map = isl_set_unwrap(stmt->domain); + else + map = isl_map_from_domain(stmt->domain); + map = isl_map_insert_dims(map, isl_dim_out, 0, n); + + for (i = nparam - 1; i >= 0; --i) { + isl_id *id; + + if (!pet_nested_in_map(map, i)) + continue; + + id = pet_expr_access_get_id(stmt->args[param2pos[i]]); + map = isl_map_set_dim_id(map, isl_dim_out, param2pos[i], id); + map = isl_map_equate(map, isl_dim_param, i, isl_dim_out, + param2pos[i]); + map = isl_map_project_out(map, isl_dim_param, i, 1); + } + + stmt->domain = isl_map_wrap(map); + + space = isl_space_unwrap(isl_set_get_space(stmt->domain)); + space = isl_space_from_domain(isl_space_domain(space)); + ma = isl_multi_aff_zero(space); + for (pos = 0; pos < n; ++pos) + stmt->args[pos] = embed(stmt->args[pos], ma); + isl_multi_aff_free(ma); + + stmt = pet_stmt_remove_nested_parameters(stmt); + stmt = remove_duplicate_arguments(stmt, n); + + free(param2pos); + return stmt; +} + +/* For each statement in "scop", move the parameters that correspond + * to nested access into the ranges of the domains and create + * corresponding argument expressions. + */ +struct pet_scop *pet_scop_resolve_nested(struct pet_scop *scop) +{ + int i; + + if (!scop) + return NULL; + + for (i = 0; i < scop->n_stmt; ++i) { + scop->stmts[i] = pet_stmt_resolve_nested(scop->stmts[i]); + if (!scop->stmts[i]) + return pet_scop_free(scop); + } + + return scop; +} diff --git a/nest.h b/nest.h index dccd82c..01de94d 100644 --- a/nest.h +++ b/nest.h @@ -32,6 +32,7 @@ int pet_extract_nested_from_space(__isl_keep isl_space *space, int n_arg, __isl_give pet_expr **args, int *param2pos); __isl_give pet_expr *pet_expr_resolve_nested(__isl_take pet_expr *expr); +struct pet_scop *pet_scop_resolve_nested(struct pet_scop *scop); #if defined(__cplusplus) } diff --git a/scan.cc b/scan.cc index c8d9d70..2652175 100644 --- a/scan.cc +++ b/scan.cc @@ -2448,7 +2448,7 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt, __isl_keep pet_context *pc) scop_cond = pet_scop_embed(scop_cond, isl_set_copy(domain), isl_aff_copy(sched), isl_aff_copy(wrap), isl_id_copy(id)); scop = pet_scop_embed(scop, isl_set_copy(domain), sched, wrap, id); - scop = resolve_nested(scop); + scop = pet_scop_resolve_nested(scop); if (has_var_break) scop = scop_add_break(scop, id_break_test, isl_set_copy(domain), isl_val_copy(inc)); @@ -2773,221 +2773,6 @@ struct pet_scop *PetScan::extract_non_affine_condition(Expr *cond, int stmt_nr, return pet_scop_from_pet_stmt(ctx, ps); } -extern "C" { - static __isl_give pet_expr *embed_access(__isl_take pet_expr *expr, - void *user); -} - -/* Precompose the access relation and the index expression associated - * to "expr" with the function pointed to by "user", - * thereby embedding the access relation in the domain of this function. - * The initial domain of the access relation and the index expression - * is the zero-dimensional domain. - */ -static __isl_give pet_expr *embed_access(__isl_take pet_expr *expr, void *user) -{ - isl_multi_aff *ma = (isl_multi_aff *) user; - - return pet_expr_access_pullback_multi_aff(expr, isl_multi_aff_copy(ma)); -} - -/* Precompose all access relations in "expr" with "ma", thereby - * embedding them in the domain of "ma". - */ -static __isl_give pet_expr *embed(__isl_take pet_expr *expr, - __isl_keep isl_multi_aff *ma) -{ - return pet_expr_map_access(expr, &embed_access, ma); -} - -/* For each nested access parameter in the domain of "stmt", - * construct a corresponding pet_expr, place it before the original - * elements in stmt->args and record its position in "param2pos". - * n is the number of nested access parameters. - */ -struct pet_stmt *PetScan::extract_nested(struct pet_stmt *stmt, int n, - int *param2pos) -{ - int i; - isl_space *space; - int n_arg; - pet_expr **args; - - n_arg = stmt->n_arg; - args = isl_calloc_array(ctx, pet_expr *, n + n_arg); - if (!args) - goto error; - - space = isl_set_get_space(stmt->domain); - n_arg = pet_extract_nested_from_space(space, 0, args, param2pos); - isl_space_free(space); - - if (n_arg < 0) - goto error; - - for (i = 0; i < stmt->n_arg; ++i) - args[n_arg + i] = stmt->args[i]; - free(stmt->args); - stmt->args = args; - stmt->n_arg += n_arg; - - return stmt; -error: - if (args) { - for (i = 0; i < n; ++i) - pet_expr_free(args[i]); - free(args); - } - pet_stmt_free(stmt); - return NULL; -} - -/* Check whether any of the arguments i of "stmt" starting at position "n" - * is equal to one of the first "n" arguments j. - * If so, combine the constraints on arguments i and j and remove - * argument i. - */ -static struct pet_stmt *remove_duplicate_arguments(struct pet_stmt *stmt, int n) -{ - int i, j; - isl_map *map; - - if (!stmt) - return NULL; - if (n == 0) - return stmt; - if (n == stmt->n_arg) - return stmt; - - map = isl_set_unwrap(stmt->domain); - - for (i = stmt->n_arg - 1; i >= n; --i) { - for (j = 0; j < n; ++j) - if (pet_expr_is_equal(stmt->args[i], stmt->args[j])) - break; - if (j >= n) - continue; - - map = isl_map_equate(map, isl_dim_out, i, isl_dim_out, j); - map = isl_map_project_out(map, isl_dim_out, i, 1); - - pet_expr_free(stmt->args[i]); - for (j = i; j + 1 < stmt->n_arg; ++j) - stmt->args[j] = stmt->args[j + 1]; - stmt->n_arg--; - } - - stmt->domain = isl_map_wrap(map); - if (!stmt->domain) - goto error; - return stmt; -error: - pet_stmt_free(stmt); - return NULL; -} - -/* Look for parameters in the iteration domain of "stmt" that - * refer to nested accesses. In particular, these are - * parameters with name "__pet_expr". - * - * If there are any such parameters, then as many extra variables - * (after identifying identical nested accesses) are inserted in the - * range of the map wrapped inside the domain, before the original variables. - * If the original domain is not a wrapped map, then a new wrapped - * map is created with zero output dimensions. - * The parameters are then equated to the corresponding output dimensions - * and subsequently projected out, from the iteration domain, - * the schedule and the access relations. - * For each of the output dimensions, a corresponding argument - * expression is inserted. Initially they are created with - * a zero-dimensional domain, so they have to be embedded - * in the current iteration domain. - * param2pos maps the position of the parameter to the position - * of the corresponding output dimension in the wrapped map. - */ -struct pet_stmt *PetScan::resolve_nested(struct pet_stmt *stmt) -{ - int n; - int nparam; - unsigned n_arg; - isl_map *map; - isl_space *space; - isl_multi_aff *ma; - int *param2pos; - - if (!stmt) - return NULL; - - n = pet_nested_n_in_set(stmt->domain); - if (n == 0) - return stmt; - - n_arg = stmt->n_arg; - nparam = isl_set_dim(stmt->domain, isl_dim_param); - param2pos = isl_alloc_array(ctx, int, nparam); - stmt = extract_nested(stmt, n, param2pos); - if (!stmt) { - free(param2pos); - return NULL; - } - - n = stmt->n_arg - n_arg; - if (isl_set_is_wrapping(stmt->domain)) - map = isl_set_unwrap(stmt->domain); - else - map = isl_map_from_domain(stmt->domain); - map = isl_map_insert_dims(map, isl_dim_out, 0, n); - - for (int i = nparam - 1; i >= 0; --i) { - isl_id *id; - - if (!pet_nested_in_map(map, i)) - continue; - - id = pet_expr_access_get_id(stmt->args[param2pos[i]]); - map = isl_map_set_dim_id(map, isl_dim_out, param2pos[i], id); - map = isl_map_equate(map, isl_dim_param, i, isl_dim_out, - param2pos[i]); - map = isl_map_project_out(map, isl_dim_param, i, 1); - } - - stmt->domain = isl_map_wrap(map); - - space = isl_space_unwrap(isl_set_get_space(stmt->domain)); - space = isl_space_from_domain(isl_space_domain(space)); - ma = isl_multi_aff_zero(space); - for (int pos = 0; pos < n; ++pos) - stmt->args[pos] = embed(stmt->args[pos], ma); - isl_multi_aff_free(ma); - - stmt = pet_stmt_remove_nested_parameters(stmt); - stmt = remove_duplicate_arguments(stmt, n); - - free(param2pos); - return stmt; -} - -/* For each statement in "scop", move the parameters that correspond - * to nested access into the ranges of the domains and create - * corresponding argument expressions. - */ -struct pet_scop *PetScan::resolve_nested(struct pet_scop *scop) -{ - if (!scop) - return NULL; - - for (int i = 0; i < scop->n_stmt; ++i) { - scop->stmts[i] = resolve_nested(scop->stmts[i]); - if (!scop->stmts[i]) - goto error; - } - - return scop; -error: - pet_scop_free(scop); - return NULL; -} - /* Given an access expression "expr", is the variable accessed by * "expr" assigned anywhere inside "scop"? */ @@ -3217,7 +3002,7 @@ struct pet_scop *PetScan::extract(IfStmt *stmt, __isl_keep pet_context *pc) scop = pet_scop_add_par(ctx, scop, scop_else); } else isl_set_free(set); - scop = resolve_nested(scop); + scop = pet_scop_resolve_nested(scop); scop = pet_scop_restrict_context(scop, isl_set_params(valid)); if (pet_skip_info_has_skip(&skip)) diff --git a/scan.h b/scan.h index 47639a2..65a3723 100644 --- a/scan.h +++ b/scan.h @@ -182,10 +182,6 @@ private: __isl_give pet_expr *extract_expr(clang::CallExpr *expr); __isl_give pet_expr *extract_expr(clang::CStyleCastExpr *expr); - struct pet_stmt *extract_nested(struct pet_stmt *stmt, int n, - int *param2pos); - struct pet_scop *resolve_nested(struct pet_scop *scop); - struct pet_stmt *resolve_nested(struct pet_stmt *stmt); __isl_give pet_expr *extract_access_expr(clang::QualType qt, __isl_take pet_expr *index); __isl_give pet_expr *extract_access_expr(clang::Expr *expr); -- 2.11.4.GIT