From 77c215ac323d6de4884f10b4c9d43f2af4f1fd6a Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 17 Feb 2014 17:30:43 +0100 Subject: [PATCH] PetScan::extract_scop: populate pet_context with parameter assignments We currently create a new parameter inside pet_expr_extract_affine whenever we come across a read on an integer variable that has not been written to anywhere in the tree. To be able to distinguish variables that have been not been assigned any value and those that have been assigned a (known or unknown) value, we have to keep track of not only the known affine values, but also "unknown" values. Now that we construct a pet_scop from the top down, we know in advance which variables should be considered as parameters. We add them directly to the pet_context before extracting the pet_scop and its arrays. In subsequent commits, we can then remove the creation of parameters on-the-fly and the special treatment of "unknown" values. This in turn will then allow us to reuse pet_expr_extract_affine from pet_check_code. Signed-off-by: Sven Verdoolaege --- context.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ context.h | 4 +++ scan.cc | 27 +++++++++++++++++- 3 files changed, 124 insertions(+), 1 deletion(-) diff --git a/context.c b/context.c index 5406b07..1c90ca4 100644 --- a/context.c +++ b/context.c @@ -402,6 +402,100 @@ __isl_give pet_context *pet_context_clear_writes_in_tree( return pc; } +/* Internal data structure for pet_context_add_parameters. + * + * "pc" is the context that is being updated. + * "get_array_size" is a callback function that can be used to determine + * the size of the array that is accessed by a given access expression. + * "user" is the user data for this callback. + */ +struct pet_context_add_parameter_data { + pet_context *pc; + __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access, + void *user); + void *user; +}; + +/* Given an access expression "expr", add a parameter assignment to data->pc + * to the variable being accessed, provided it is a read from an integer + * scalar variable. + * If an array is being accesed, then recursively call the function + * on each of the access expressions in the size expression of the array. + */ +static int add_parameter(__isl_keep pet_expr *expr, void *user) +{ + struct pet_context_add_parameter_data *data = user; + int pos; + isl_id *id; + isl_space *space; + isl_local_space *ls; + isl_aff *aff; + isl_pw_aff *pa; + + if (!pet_expr_is_scalar_access(expr)) { + pet_expr *size = data->get_array_size(expr, data->user); + if (pet_expr_foreach_access_expr(size, + &add_parameter, data) < 0) + data->pc = pet_context_free(data->pc); + pet_expr_free(size); + return 0; + } + if (!pet_expr_access_is_read(expr)) + return 0; + if (pet_expr_get_type_size(expr) == 0) + return 0; + + id = pet_expr_access_get_id(expr); + if (pet_context_is_assigned(data->pc, id)) { + isl_id_free(id); + return 0; + } + + space = pet_context_get_space(data->pc); + pos = isl_space_find_dim_by_id(space, isl_dim_param, id); + if (pos < 0) { + pos = isl_space_dim(space, isl_dim_param); + space = isl_space_add_dims(space, isl_dim_param, 1); + space = isl_space_set_dim_id(space, isl_dim_param, pos, + isl_id_copy(id)); + } + + ls = isl_local_space_from_space(space); + aff = isl_aff_var_on_domain(ls, isl_dim_param, pos); + pa = isl_pw_aff_from_aff(aff); + data->pc = pet_context_set_value(data->pc, id, pa); + + return 0; +} + +/* Add an assignment to "pc" for each parameter in "tree". + * "get_array_size" is a callback function that can be used to determine + * the size of the array that is accessed by a given access expression. + * + * We initially treat as parameters any integer variable that is read + * anywhere in "tree" or in any of the size expressions for any of + * the arrays accessed in "tree". + * Then we remove from those variables that are written anywhere + * inside "tree". + */ +__isl_give pet_context *pet_context_add_parameters(__isl_take pet_context *pc, + __isl_keep pet_tree *tree, + __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access, + void *user), void *user) +{ + struct pet_context_add_parameter_data data; + + data.pc = pc; + data.get_array_size = get_array_size; + data.user = user; + if (pet_tree_foreach_access_expr(tree, &add_parameter, &data) < 0) + data.pc = pet_context_free(data.pc); + + data.pc = pet_context_clear_writes_in_tree(data.pc, tree); + + return data.pc; +} + /* Given an access expression, check if it reads a scalar variable * that has a known value in "pc". * If so, then replace the access by an access to that value. diff --git a/context.h b/context.h index 44ef40e..4693d09 100644 --- a/context.h +++ b/context.h @@ -43,6 +43,10 @@ __isl_give pet_context *pet_context_clear_writes_in_expr( __isl_take pet_context *pc, __isl_keep pet_expr *expr); __isl_give pet_context *pet_context_clear_writes_in_tree( __isl_take pet_context *pc, __isl_keep pet_tree *tree); +__isl_give pet_context *pet_context_add_parameters(__isl_take pet_context *pc, + __isl_keep pet_tree *tree, + __isl_give pet_expr *(*get_array_size)(__isl_keep pet_expr *access, + void *user), void *user); __isl_give pet_expr *pet_context_evaluate_expr(__isl_keep pet_context *pc, __isl_take pet_expr *expr); diff --git a/scan.cc b/scan.cc index 72ad0f6..0e23be8 100644 --- a/scan.cc +++ b/scan.cc @@ -1588,10 +1588,32 @@ static QualType get_array_type(ValueDecl *decl) } extern "C" { + static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access, + void *user); static struct pet_array *extract_array(__isl_keep pet_expr *access, __isl_keep pet_context *pc, void *user); } +/* Construct a pet_expr that holds the sizes of the array accessed + * by "access". + * This function is used as a callback to pet_context_add_parameters, + * which is also passed a pointer to the PetScan object. + */ +static __isl_give pet_expr *get_array_size(__isl_keep pet_expr *access, + void *user) +{ + PetScan *ps = (PetScan *) user; + isl_id *id; + ValueDecl *decl; + const Type *type; + + id = pet_expr_access_get_id(access); + decl = (ValueDecl *) isl_id_get_user(id); + isl_id_free(id); + type = get_array_type(decl).getTypePtr(); + return ps->get_array_size(type); +} + /* Construct and return a pet_array corresponding to the variable * accessed by "access". * This function is used as a callback to pet_scop_from_pet_tree, @@ -1616,6 +1638,9 @@ static struct pet_array *extract_array(__isl_keep pet_expr *access, * * We simply call pet_scop_from_pet_tree with the appropriate arguments and * then add pet_arrays for all accessed arrays. + * We populate the pet_context with assignments for all parameters used + * inside "tree" or any of the size expressions for the arrays accessed + * by "tree" so that they can be used in affine expressions. */ struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree) { @@ -1628,7 +1653,7 @@ struct pet_scop *PetScan::extract_scop(__isl_take pet_tree *tree) domain = isl_set_universe(isl_space_set_alloc(ctx, 0, 0)); pc = pet_context_alloc(domain); - pc = pet_context_clear_writes_in_tree(pc, tree); + pc = pet_context_add_parameters(pc, tree, &::get_array_size, this); scop = pet_scop_from_pet_tree(tree, int_size, &::extract_array, this, pc); scop = scan_arrays(scop, pc); -- 2.11.4.GIT