From 43c9527cb0b0080c49781fd930a4e295c36d3de2 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 5 Apr 2012 11:40:16 +0200 Subject: [PATCH] isl_access_info: change interface for specifying restrictions The original interface would only allow the user to restrict the source iterations, while the user may also want to restrict the sink iterations. The new interface also makes it more convenient for the user to specify that no restriction should be applied and allows for a restriction on the result of the maximization problem. Signed-off-by: Sven Verdoolaege --- doc/user.pod | 68 +++++++++++++----- include/isl/flow.h | 22 ++++-- isl_flow.c | 200 +++++++++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 249 insertions(+), 41 deletions(-) diff --git a/doc/user.pod b/doc/user.pod index 8c3be1b5..048ac2c3 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -4134,7 +4134,7 @@ the following operation. Given a relation between sink iterations and potential soure iterations from a particular source domain, what is the last potential source iteration corresponding to each sink iteration. It can sometimes be convenient to adjust -the set of potential source iterations before each such operation. +the set of potential source iterations before or after each such operation. The prototypical example is fuzzy array dataflow analysis, where we need to analyze if, based on data-dependent constraints, the sink iteration can ever be executed without one or more of @@ -4146,29 +4146,63 @@ function. #include - typedef __isl_give isl_set *(*isl_access_restrict_sources)( - __isl_take isl_map *source_map, - void *sink_user, void *source_user); - __isl_give isl_access_info * - isl_access_info_set_restrict_sources( + typedef __isl_give isl_restriction *(*isl_access_restrict)( + __isl_keep isl_map *source_map, + __isl_keep isl_set *sink, void *source_user, + void *user); + __isl_give isl_access_info *isl_access_info_set_restrict( __isl_take isl_access_info *acc, - isl_access_restrict_sources fn); + isl_access_restrict fn, void *user); -The function C should be called -before C and registers a callback function +The function C should be called +before calling C and registers a callback function that will be called any time C is about to compute the last potential source. The first argument is the (reverse) proto-dependence, mapping sink iterations to potential source iterations. -The other two arguments are the tokens corresponding to the sink -and the source. The callback is expected to return a set -that restricts the source iterations. The potential source iterations -will be intersected with this set. If no restrictions are required -for a given C, then the callback should return +The second argument represents the sink iterations for which +we want to compute the last source iteration. +The third argument is the token corresponding to the source +and the final argument is the token passed to C. +The callback is expected to return a restriction on either the input or +the output of the operation computing the last potential source. +If the input needs to be restricted then restrictions are needed +for both the source and the sink iterations. The sink iterations +and the potential source iterations will be intersected with these sets. +If the output needs to be restricted then only a restriction on the source +iterations is required. +If any error occurs, the callback should return C. +An C object can be created and freed using the following +functions. - isl_set_universe( - isl_space_range(isl_map_get_space(source_map))); + #include -If any error occurs, the callback should return C. + __isl_give isl_restriction *isl_restriction_input( + __isl_take isl_set *source_restr, + __isl_take isl_set *sink_restr); + __isl_give isl_restriction *isl_restriction_output( + __isl_take isl_set *source_restr); + __isl_give isl_restriction *isl_restriction_none( + __isl_keep isl_map *source_map); + __isl_give isl_restriction *isl_restriction_empty( + __isl_keep isl_map *source_map); + void *isl_restriction_free( + __isl_take isl_restriction *restr); + +C and C are special +cases of C. C +is essentially equivalent to + + isl_restriction_input(isl_set_universe( + isl_space_range(isl_map_get_space(source_map))), + isl_set_universe( + isl_space_domain(isl_map_get_space(source_map)))); + +whereas C is essentially equivalent to + + isl_restriction_input(isl_set_empty( + isl_space_range(isl_map_get_space(source_map))), + isl_set_universe( + isl_space_domain(isl_map_get_space(source_map)))); =head2 Scheduling diff --git a/include/isl/flow.h b/include/isl/flow.h index e59bff33..3333e569 100644 --- a/include/isl/flow.h +++ b/include/isl/flow.h @@ -16,8 +16,22 @@ extern "C" { */ typedef int (*isl_access_level_before)(void *first, void *second); -typedef __isl_give isl_set *(*isl_access_restrict_sources)( - __isl_take isl_map *source_map, void *sink_user, void *source_user); +struct isl_restriction; +typedef struct isl_restriction isl_restriction; + +void *isl_restriction_free(__isl_take isl_restriction *restr); +__isl_give isl_restriction *isl_restriction_empty( + __isl_keep isl_map *source_map); +__isl_give isl_restriction *isl_restriction_none( + __isl_keep isl_map *source_map); +__isl_give isl_restriction *isl_restriction_input( + __isl_take isl_set *source_restr, __isl_take isl_set *sink_restr); +__isl_give isl_restriction *isl_restriction_output( + __isl_take isl_set *source_restr); + +typedef __isl_give isl_restriction *(*isl_access_restrict)( + __isl_keep isl_map *source_map, __isl_keep isl_set *sink, + void *source_user, void *user); struct isl_access_info; typedef struct isl_access_info isl_access_info; @@ -26,8 +40,8 @@ typedef struct isl_flow isl_flow; __isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink, void *sink_user, isl_access_level_before fn, int max_source); -__isl_give isl_access_info *isl_access_info_set_restrict_sources( - __isl_take isl_access_info *acc, isl_access_restrict_sources fn); +__isl_give isl_access_info *isl_access_info_set_restrict( + __isl_take isl_access_info *acc, isl_access_restrict fn, void *user); __isl_give isl_access_info *isl_access_info_add_source( __isl_take isl_access_info *acc, __isl_take isl_map *source, int must, void *source_user); diff --git a/isl_flow.c b/isl_flow.c index bbaee6ee..20593659 100644 --- a/isl_flow.c +++ b/isl_flow.c @@ -2,6 +2,7 @@ * Copyright 2005-2007 Universiteit Leiden * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay + * Copyright 2012 Universiteit Leiden * * Use of this software is governed by the GNU LGPLv2.1 license * @@ -18,6 +19,126 @@ #include #include +enum isl_restriction_type { + isl_restriction_type_empty, + isl_restriction_type_none, + isl_restriction_type_input, + isl_restriction_type_output +}; + +struct isl_restriction { + enum isl_restriction_type type; + + isl_set *source; + isl_set *sink; +}; + +/* Create a restriction that doesn't restrict anything. + */ +__isl_give isl_restriction *isl_restriction_none(__isl_keep isl_map *source_map) +{ + isl_ctx *ctx; + isl_restriction *restr; + + if (!source_map) + return NULL; + + ctx = isl_map_get_ctx(source_map); + restr = isl_calloc_type(ctx, struct isl_restriction); + if (!restr) + return NULL; + + restr->type = isl_restriction_type_none; + + return restr; +} + +/* Create a restriction that removes everything. + */ +__isl_give isl_restriction *isl_restriction_empty( + __isl_keep isl_map *source_map) +{ + isl_ctx *ctx; + isl_restriction *restr; + + if (!source_map) + return NULL; + + ctx = isl_map_get_ctx(source_map); + restr = isl_calloc_type(ctx, struct isl_restriction); + if (!restr) + return NULL; + + restr->type = isl_restriction_type_empty; + + return restr; +} + +/* Create a restriction on the input of the maximization problem + * based on the given source and sink restrictions. + */ +__isl_give isl_restriction *isl_restriction_input( + __isl_take isl_set *source_restr, __isl_take isl_set *sink_restr) +{ + isl_ctx *ctx; + isl_restriction *restr; + + if (!source_restr || !sink_restr) + goto error; + + ctx = isl_set_get_ctx(source_restr); + restr = isl_calloc_type(ctx, struct isl_restriction); + if (!restr) + goto error; + + restr->type = isl_restriction_type_input; + restr->source = source_restr; + restr->sink = sink_restr; + + return restr; +error: + isl_set_free(source_restr); + isl_set_free(sink_restr); + return NULL; +} + +/* Create a restriction on the output of the maximization problem + * based on the given source restriction. + */ +__isl_give isl_restriction *isl_restriction_output( + __isl_take isl_set *source_restr) +{ + isl_ctx *ctx; + isl_restriction *restr; + + if (!source_restr) + return NULL; + + ctx = isl_set_get_ctx(source_restr); + restr = isl_calloc_type(ctx, struct isl_restriction); + if (!restr) + goto error; + + restr->type = isl_restriction_type_output; + restr->source = source_restr; + + return restr; +error: + isl_set_free(source_restr); + return NULL; +} + +void *isl_restriction_free(__isl_take isl_restriction *restr) +{ + if (!restr) + return NULL; + + isl_set_free(restr->source); + isl_set_free(restr->sink); + free(restr); + return NULL; +} + /* A private structure to keep track of a mapping together with * a user-specified identifier and a boolean indicating whether * the map represents a must or may access/dependence. @@ -37,14 +158,17 @@ struct isl_labeled_map { * domain_map is an auxiliary map that maps the sink access relation * to the domain of this access relation. * - * restrict_sources is a callback that (if not NULL) will be called + * restrict_fn is a callback that (if not NULL) will be called * right before any lexicographical maximization. */ struct isl_access_info { isl_map *domain_map; struct isl_labeled_map sink; isl_access_level_before level_before; - isl_access_restrict_sources restrict_sources; + + isl_access_restrict restrict_fn; + void *restrict_user; + int max_source; int n_must; int n_may; @@ -117,12 +241,13 @@ isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc) return acc ? isl_map_get_ctx(acc->sink.map) : NULL; } -__isl_give isl_access_info *isl_access_info_set_restrict_sources( - __isl_take isl_access_info *acc, isl_access_restrict_sources fn) +__isl_give isl_access_info *isl_access_info_set_restrict( + __isl_take isl_access_info *acc, isl_access_restrict fn, void *user) { if (!acc) return NULL; - acc->restrict_sources = fn; + acc->restrict_fn = fn; + acc->restrict_user = user; return acc; } @@ -374,30 +499,67 @@ static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level) return isl_map_from_basic_map(bmap); } -/* Check if the user has set acc->restrict_sources and if so - * intersect the range of "dep" with the result of a call to this function. +/* Compute the partial lexicographic maximum of "dep" on domain "sink", + * but first check if the user has set acc->restrict_fn and if so + * update either the input or the output of the maximization problem + * with respect to the resulting restriction. * * Since the user expects a mapping from sink iterations to source iterations, * whereas the domain of "dep" is a wrapped map, mapping sink iterations * to accessed array elements, we first need to project out the accessed * sink array elements by applying acc->domain_map. + * Similarly, the sink restriction specified by the user needs to be + * converted back to the wrapped map. */ -static __isl_give isl_map *restrict_sources(__isl_take isl_map *dep, - struct isl_access_info *acc, int source) +static __isl_give isl_map *restricted_partial_lexmax( + __isl_keep isl_access_info *acc, __isl_take isl_map *dep, + int source, __isl_take isl_set *sink, __isl_give isl_set **empty) { isl_map *source_map; - isl_set *param; + isl_restriction *restr; + isl_set *sink_domain; + isl_set *sink_restr; + isl_map *res; - if (!acc->restrict_sources) - return dep; + if (!acc->restrict_fn) + return isl_map_partial_lexmax(dep, sink, empty); source_map = isl_map_copy(dep); source_map = isl_map_apply_domain(source_map, isl_map_copy(acc->domain_map)); - param = acc->restrict_sources(source_map, acc->sink.data, - acc->source[source].data); - dep = isl_map_intersect_range(dep, param); - return dep; + sink_domain = isl_set_copy(sink); + sink_domain = isl_set_apply(sink_domain, isl_map_copy(acc->domain_map)); + restr = acc->restrict_fn(source_map, sink_domain, + acc->source[source].data, acc->restrict_user); + isl_set_free(sink_domain); + isl_map_free(source_map); + + if (!restr) + goto error; + if (restr->type == isl_restriction_type_input) { + dep = isl_map_intersect_range(dep, isl_set_copy(restr->source)); + sink_restr = isl_set_copy(restr->sink); + sink_restr = isl_set_apply(sink_restr, + isl_map_reverse(isl_map_copy(acc->domain_map))); + sink = isl_set_intersect(sink, sink_restr); + } else if (restr->type == isl_restriction_type_empty) { + isl_space *space = isl_map_get_space(dep); + isl_map_free(dep); + dep = isl_map_empty(space); + } + + res = isl_map_partial_lexmax(dep, sink, empty); + + if (restr->type == isl_restriction_type_output) + res = isl_map_intersect_range(res, isl_set_copy(restr->source)); + + isl_restriction_free(restr); + return res; +error: + isl_map_free(dep); + isl_set_free(sink); + *empty = NULL; + return NULL; } /* Compute the last iteration of must source j that precedes the sink @@ -421,8 +583,7 @@ static struct isl_map *last_source(struct isl_access_info *acc, dep_map = isl_map_apply_range(read_map, write_map); after = after_at_level(isl_map_get_space(dep_map), level); dep_map = isl_map_intersect(dep_map, after); - dep_map = restrict_sources(dep_map, acc, j); - result = isl_map_partial_lexmax(dep_map, set_C, empty); + result = restricted_partial_lexmax(acc, dep_map, j, set_C, empty); result = isl_map_reverse(result); return result; @@ -463,8 +624,7 @@ static struct isl_map *last_later_source(struct isl_access_info *acc, dep_map = isl_map_intersect(dep_map, after_write); before_read = after_at_level(isl_map_get_space(dep_map), before_level); dep_map = isl_map_intersect(dep_map, before_read); - dep_map = restrict_sources(dep_map, acc, k); - result = isl_map_partial_lexmax(dep_map, set_C, empty); + result = restricted_partial_lexmax(acc, dep_map, k, set_C, empty); result = isl_map_reverse(result); return result; -- 2.11.4.GIT