From edd0bdf642328843e2b2121a4d052ee9c0564bbe Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 2 Aug 2014 17:23:25 +0200 Subject: [PATCH] isl_ast_codegen.c: do_unroll: extract out foreach_iteration We will be able to reuse this function when we handle unrolling in schedules represented by schedule trees. Signed-off-by: Sven Verdoolaege --- isl_ast_codegen.c | 193 ++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 123 insertions(+), 70 deletions(-) diff --git a/isl_ast_codegen.c b/isl_ast_codegen.c index 3ccd3fbf..39a95f32 100644 --- a/isl_ast_codegen.c +++ b/isl_ast_codegen.c @@ -2512,43 +2512,8 @@ error: return isl_aff_free(data.lower); } -/* Data structure for storing the results and the intermediate objects - * of compute_domains. - * - * "list" is the main result of the function and contains a list - * of disjoint basic sets for which code should be generated. - * - * "executed" and "build" are inputs to compute_domains. - * "schedule_domain" is the domain of "executed". - * - * "option" constains the domains at the current depth that should by - * atomic, separated or unrolled. These domains are as specified by - * the user, except that inner dimensions have been eliminated and - * that they have been made pair-wise disjoint. - * - * "sep_class" contains the user-specified split into separation classes - * specialized to the current depth. - * "done" contains the union of the separation domains that have already - * been handled. - */ -struct isl_codegen_domains { - isl_basic_set_list *list; - - isl_union_map *executed; - isl_ast_build *build; - isl_set *schedule_domain; - - isl_set *option[3]; - - isl_map *sep_class; - isl_set *done; -}; - -/* Extend domains->list with a list of basic sets, one for each value - * of the current dimension in "domain" and remove the corresponding - * sets from the class domain. Return the updated class domain. - * The divs that involve the current dimension have not been projected out - * from this domain. +/* Call "fn" on each iteration of the current dimension of "domain". + * Return -1 on failure. * * Since we are going to be iterating over the individual values, * we first check if there are any strides on the current dimension. @@ -2576,52 +2541,43 @@ struct isl_codegen_domains { * will be taken into account at the next level, as in the case of the * atomic option. * - * Finally, we map i' back to i and add each basic set to the list. - * Since we may have dropped some constraints, we intersect with - * the class domain again to ensure that each element in the list - * is disjoint from the other class domains. + * Finally, we map i' back to i and call "fn". */ -static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains, - __isl_take isl_set *domain, __isl_take isl_set *class_domain) +static int foreach_iteration(__isl_take isl_set *domain, + __isl_keep isl_ast_build *build, + int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user) { int i, n; int depth; - isl_aff *lower; isl_multi_aff *expansion; isl_basic_map *bmap; - isl_set *unroll_domain; - isl_ast_build *build; + isl_aff *lower; + isl_ast_build *stride_build; - if (!domain) - return isl_set_free(class_domain); + depth = isl_ast_build_get_depth(build); - depth = isl_ast_build_get_depth(domains->build); - build = isl_ast_build_copy(domains->build); domain = isl_ast_build_eliminate_inner(build, domain); domain = isl_set_intersect(domain, isl_ast_build_get_domain(build)); - build = isl_ast_build_detect_strides(build, isl_set_copy(domain)); - expansion = isl_ast_build_get_stride_expansion(build); + stride_build = isl_ast_build_copy(build); + stride_build = isl_ast_build_detect_strides(stride_build, + isl_set_copy(domain)); + expansion = isl_ast_build_get_stride_expansion(stride_build); domain = isl_set_preimage_multi_aff(domain, isl_multi_aff_copy(expansion)); - domain = isl_ast_build_eliminate_divs(build, domain); - - isl_ast_build_free(build); + domain = isl_ast_build_eliminate_divs(stride_build, domain); + isl_ast_build_free(stride_build); bmap = isl_basic_map_from_multi_aff(expansion); - lower = find_unroll_lower_bound(domains->build, domain, depth, bmap, - &n); + lower = find_unroll_lower_bound(build, domain, depth, bmap, &n); if (!lower) - class_domain = isl_set_free(class_domain); - - unroll_domain = isl_set_empty(isl_set_get_space(domain)); + domain = isl_set_free(domain); - for (i = 0; class_domain && i < n; ++i) { + for (i = 0; i < n; ++i) { isl_set *set; isl_basic_set *bset; isl_constraint *slice; - isl_basic_set_list *list; slice = at_offset(depth, lower, i); set = isl_set_copy(domain); @@ -2629,20 +2585,117 @@ static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains, bset = isl_set_unshifted_simple_hull(set); bset = isl_basic_set_add_constraint(bset, slice); bset = isl_basic_set_apply(bset, isl_basic_map_copy(bmap)); - set = isl_set_from_basic_set(bset); - unroll_domain = isl_set_union(unroll_domain, isl_set_copy(set)); - set = isl_set_intersect(set, isl_set_copy(class_domain)); - set = isl_set_make_disjoint(set); - list = isl_basic_set_list_from_set(set); - domains->list = isl_basic_set_list_concat(domains->list, list); - } - class_domain = isl_set_subtract(class_domain, unroll_domain); + if (fn(bset, user) < 0) + break; + } isl_aff_free(lower); isl_set_free(domain); isl_basic_map_free(bmap); + return i < n ? -1 : 0; +} + +/* Data structure for storing the results and the intermediate objects + * of compute_domains. + * + * "list" is the main result of the function and contains a list + * of disjoint basic sets for which code should be generated. + * + * "executed" and "build" are inputs to compute_domains. + * "schedule_domain" is the domain of "executed". + * + * "option" constains the domains at the current depth that should by + * atomic, separated or unrolled. These domains are as specified by + * the user, except that inner dimensions have been eliminated and + * that they have been made pair-wise disjoint. + * + * "sep_class" contains the user-specified split into separation classes + * specialized to the current depth. + * "done" contains the union of the separation domains that have already + * been handled. + */ +struct isl_codegen_domains { + isl_basic_set_list *list; + + isl_union_map *executed; + isl_ast_build *build; + isl_set *schedule_domain; + + isl_set *option[3]; + + isl_map *sep_class; + isl_set *done; +}; + +/* Internal data structure for do_unroll. + * + * "domains" stores the results of compute_domains. + * "class_domain" is the original class domain passed to do_unroll. + * "unroll_domain" collects the unrolled iterations. + */ +struct isl_ast_unroll_data { + struct isl_codegen_domains *domains; + isl_set *class_domain; + isl_set *unroll_domain; +}; + +/* Given an iteration of an unrolled domain represented by "bset", + * add it to data->domains->list. + * Since we may have dropped some constraints, we intersect with + * the class domain again to ensure that each element in the list + * is disjoint from the other class domains. + */ +static int do_unroll_iteration(__isl_take isl_basic_set *bset, void *user) +{ + struct isl_ast_unroll_data *data = user; + isl_set *set; + isl_basic_set_list *list; + + set = isl_set_from_basic_set(bset); + data->unroll_domain = isl_set_union(data->unroll_domain, + isl_set_copy(set)); + set = isl_set_intersect(set, isl_set_copy(data->class_domain)); + set = isl_set_make_disjoint(set); + list = isl_basic_set_list_from_set(set); + data->domains->list = isl_basic_set_list_concat(data->domains->list, + list); + + return 0; +} + +/* Extend domains->list with a list of basic sets, one for each value + * of the current dimension in "domain" and remove the corresponding + * sets from the class domain. Return the updated class domain. + * The divs that involve the current dimension have not been projected out + * from this domain. + * + * We call foreach_iteration to iterate over the individual values and + * in do_unroll_iteration we collect the individual basic sets in + * domains->list and their union in data->unroll_domain, which is then + * used to update the class domain. + */ +static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains, + __isl_take isl_set *domain, __isl_take isl_set *class_domain) +{ + struct isl_ast_unroll_data data; + + if (!domain) + return isl_set_free(class_domain); + if (!class_domain) + return isl_set_free(domain); + + data.domains = domains; + data.class_domain = class_domain; + data.unroll_domain = isl_set_empty(isl_set_get_space(domain)); + + if (foreach_iteration(domain, domains->build, + &do_unroll_iteration, &data) < 0) + data.unroll_domain = isl_set_free(data.unroll_domain); + + class_domain = isl_set_subtract(class_domain, data.unroll_domain); + return class_domain; } -- 2.11.4.GIT