X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_flow.c;h=8dca5c44e8729641a47bf1e530ebb12406c760af;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=fd9754ee6f718b5ea0a344c806e599b5397f71e6;hpb=757a9321c189e9a13bbe012c5af17423d3773cad;p=platform%2Fupstream%2Fisl.git diff --git a/isl_flow.c b/isl_flow.c index fd9754e..8dca5c4 100644 --- a/isl_flow.c +++ b/isl_flow.c @@ -2,8 +2,9 @@ * 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 + * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science, * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands @@ -13,7 +14,134 @@ * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France */ +#include +#include #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 of the given type. + */ +static __isl_give isl_restriction *isl_restriction_alloc( + __isl_take isl_map *source_map, enum isl_restriction_type type) +{ + 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) + goto error; + + restr->type = type; + + isl_map_free(source_map); + return restr; +error: + isl_map_free(source_map); + return NULL; +} + +/* Create a restriction that doesn't restrict anything. + */ +__isl_give isl_restriction *isl_restriction_none(__isl_take isl_map *source_map) +{ + return isl_restriction_alloc(source_map, isl_restriction_type_none); +} + +/* Create a restriction that removes everything. + */ +__isl_give isl_restriction *isl_restriction_empty( + __isl_take isl_map *source_map) +{ + return isl_restriction_alloc(source_map, isl_restriction_type_empty); +} + +/* 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; +} + +isl_ctx *isl_restriction_get_ctx(__isl_keep isl_restriction *restr) +{ + return restr ? isl_set_get_ctx(restr->source) : NULL; +} /* A private structure to keep track of a mapping together with * a user-specified identifier and a boolean indicating whether @@ -30,20 +158,31 @@ struct isl_labeled_map { * - n_must + n_may (<= max_source) sources * - a function for determining the relative order of sources and sink * The must sources are placed before the may sources. + * + * domain_map is an auxiliary map that maps the sink access relation + * to the domain of this access relation. + * + * restrict_fn is a callback that (if not NULL) will be called + * right before any lexicographical maximization. */ struct isl_access_info { - struct isl_labeled_map sink; - isl_access_level_before level_before; - int max_source; - int n_must; - int n_may; - struct isl_labeled_map source[1]; + isl_map *domain_map; + struct isl_labeled_map sink; + isl_access_level_before level_before; + + isl_access_restrict restrict_fn; + void *restrict_user; + + int max_source; + int n_must; + int n_may; + struct isl_labeled_map source[1]; }; /* A structure containing the output of dependence analysis: * - n_source dependences - * - a subset of the sink for which definitely no source could be found - * - a subset of the sink for which possibly no source could be found + * - a wrapped subset of the sink for which definitely no source could be found + * - a wrapped subset of the sink for which possibly no source could be found */ struct isl_flow { isl_set *must_no_source; @@ -67,7 +206,7 @@ __isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink, ctx = isl_map_get_ctx(sink); isl_assert(ctx, max_source >= 0, goto error); - acc = isl_alloc(ctx, struct isl_access_info, + acc = isl_calloc(ctx, struct isl_access_info, sizeof(struct isl_access_info) + (max_source - 1) * sizeof(struct isl_labeled_map)); if (!acc) @@ -88,16 +227,33 @@ error: /* Free the given isl_access_info structure. */ -void isl_access_info_free(__isl_take isl_access_info *acc) +void *isl_access_info_free(__isl_take isl_access_info *acc) { int i; if (!acc) - return; + return NULL; + isl_map_free(acc->domain_map); isl_map_free(acc->sink.map); for (i = 0; i < acc->n_must + acc->n_may; ++i) isl_map_free(acc->source[i].map); free(acc); + return NULL; +} + +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( + __isl_take isl_access_info *acc, isl_access_restrict fn, void *user) +{ + if (!acc) + return NULL; + acc->restrict_fn = fn; + acc->restrict_user = user; + return acc; } /* Add another source to an isl_access_info structure, making @@ -113,7 +269,7 @@ __isl_give isl_access_info *isl_access_info_add_source( isl_ctx *ctx; if (!acc) - return NULL; + goto error; ctx = isl_map_get_ctx(acc->sink.map); isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error); @@ -139,23 +295,11 @@ error: return NULL; } -/* A temporary structure used while sorting the accesses in an isl_access_info. - */ -struct isl_access_sort_info { - struct isl_map *source_map; - void *source_data; - struct isl_access_info *acc; -}; - /* Return -n, 0 or n (with n a positive value), depending on whether * the source access identified by p1 should be sorted before, together * or after that identified by p2. * - * If p1 and p2 share a different number of levels with the sink, - * then the one with the lowest number of shared levels should be - * sorted first. - * If they both share no levels, then the order is irrelevant. - * Otherwise, if p1 appears before p2, then it should be sorted first. + * If p1 appears before p2, then it should be sorted first. * For more generic initial schedules, it is possible that neither * p1 nor p2 appears before the other, or at least not in any obvious way. * We therefore also check if p2 appears before p1, in which case p2 @@ -164,75 +308,57 @@ struct isl_access_sort_info { * of the iteration domains. This results in an arbitrary, but fairly * stable ordering. */ -static int access_sort_cmp(const void *p1, const void *p2) +static int access_sort_cmp(const void *p1, const void *p2, void *user) { - const struct isl_access_sort_info *i1, *i2; + isl_access_info *acc = user; + const struct isl_labeled_map *i1, *i2; int level1, level2; uint32_t h1, h2; - i1 = (const struct isl_access_sort_info *) p1; - i2 = (const struct isl_access_sort_info *) p2; + i1 = (const struct isl_labeled_map *) p1; + i2 = (const struct isl_labeled_map *) p2; - level1 = i1->acc->level_before(i1->source_data, i1->acc->sink.data); - level2 = i2->acc->level_before(i2->source_data, i2->acc->sink.data); - - if (level1 != level2 || !level1) - return level1 - level2; - - level1 = i1->acc->level_before(i1->source_data, i2->source_data); + level1 = acc->level_before(i1->data, i2->data); if (level1 % 2) return -1; - level2 = i1->acc->level_before(i2->source_data, i1->source_data); + level2 = acc->level_before(i2->data, i1->data); if (level2 % 2) return 1; - h1 = isl_map_get_hash(i1->source_map); - h2 = isl_map_get_hash(i2->source_map); - return h1 - h2; + h1 = isl_map_get_hash(i1->map); + h2 = isl_map_get_hash(i2->map); + return h1 > h2 ? 1 : h1 < h2 ? -1 : 0; } -/* Sort the must source accesses in order of increasing number of shared - * levels with the sink access. - * Source accesses with the same number of shared levels are sorted - * in their textual order. +/* Sort the must source accesses in their textual order. */ static __isl_give isl_access_info *isl_access_info_sort_sources( __isl_take isl_access_info *acc) { - int i; - isl_ctx *ctx; - struct isl_access_sort_info *array; - if (!acc) return NULL; if (acc->n_must <= 1) return acc; - ctx = isl_map_get_ctx(acc->sink.map); - array = isl_alloc_array(ctx, struct isl_access_sort_info, acc->n_must); - if (!array) - goto error; - - for (i = 0; i < acc->n_must; ++i) { - array[i].source_map = acc->source[i].map; - array[i].source_data = acc->source[i].data; - array[i].acc = acc; - } - - qsort(array, acc->n_must, sizeof(struct isl_access_sort_info), - access_sort_cmp); + if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map), + access_sort_cmp, acc) < 0) + return isl_access_info_free(acc); - for (i = 0; i < acc->n_must; ++i) { - acc->source[i].map = array[i].source_map; - acc->source[i].data = array[i].source_data; - } + return acc; +} - free(array); +/* Align the parameters of the two spaces if needed and then call + * isl_space_join. + */ +static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left, + __isl_take isl_space *right) +{ + if (isl_space_match(left, isl_dim_param, right, isl_dim_param)) + return isl_space_join(left, right); - return acc; -error: - isl_access_info_free(acc); - return NULL; + left = isl_space_align_params(left, isl_space_copy(right)); + right = isl_space_align_params(right, isl_space_copy(left)); + return isl_space_join(left, right); } /* Initialize an empty isl_flow structure corresponding to a given @@ -266,9 +392,10 @@ static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc) dep->n_source = 2 * acc->n_must + acc->n_may; for (i = 0; i < acc->n_must; ++i) { - struct isl_dim *dim; - dim = isl_dim_join(isl_map_get_dim(acc->source[i].map), - isl_dim_reverse(isl_map_get_dim(acc->sink.map))); + isl_space *dim; + dim = space_align_and_join( + isl_map_get_space(acc->source[i].map), + isl_space_reverse(isl_map_get_space(acc->sink.map))); dep->dep[2 * i].map = isl_map_empty(dim); dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map); dep->dep[2 * i].data = acc->source[i].data; @@ -279,9 +406,10 @@ static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc) goto error; } for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) { - struct isl_dim *dim; - dim = isl_dim_join(isl_map_get_dim(acc->source[i].map), - isl_dim_reverse(isl_map_get_dim(acc->sink.map))); + isl_space *dim; + dim = space_align_and_join( + isl_map_get_space(acc->source[i].map), + isl_space_reverse(isl_map_get_space(acc->sink.map))); dep->dep[acc->n_must + i].map = isl_map_empty(dim); dep->dep[acc->n_must + i].data = acc->source[i].data; dep->dep[acc->n_must + i].must = 0; @@ -311,7 +439,7 @@ int isl_flow_foreach(__isl_keep isl_flow *deps, return -1; for (i = 0; i < deps->n_source; ++i) { - if (isl_map_fast_is_empty(deps->dep[i].map)) + if (isl_map_plain_is_empty(deps->dep[i].map)) continue; if (fn(isl_map_copy(deps->dep[i].map), deps->dep[i].must, deps->dep[i].data, user) < 0) @@ -323,15 +451,15 @@ int isl_flow_foreach(__isl_keep isl_flow *deps, /* Return a copy of the subset of the sink for which no source could be found. */ -__isl_give isl_set *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must) +__isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must) { if (!deps) return NULL; if (must) - return isl_set_copy(deps->must_no_source); + return isl_set_unwrap(isl_set_copy(deps->must_no_source)); else - return isl_set_copy(deps->may_no_source); + return isl_set_unwrap(isl_set_copy(deps->may_no_source)); } void isl_flow_free(__isl_take isl_flow *deps) @@ -350,6 +478,11 @@ void isl_flow_free(__isl_take isl_flow *deps) free(deps); } +isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps) +{ + return deps ? isl_set_get_ctx(deps->must_no_source) : NULL; +} + /* Return a map that enforces that the domain iteration occurs after * the range iteration at the given level. * If level is odd, then the domain iteration should occur after @@ -360,7 +493,7 @@ void isl_flow_free(__isl_take isl_flow *deps) * be greater than the loop iterator of the range at the last * of the level/2 shared loops, i.e., loop level/2 - 1. */ -static __isl_give isl_map *after_at_level(struct isl_dim *dim, int level) +static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level) { struct isl_basic_map *bmap; @@ -372,6 +505,69 @@ static __isl_give isl_map *after_at_level(struct isl_dim *dim, int level) return isl_map_from_basic_map(bmap); } +/* 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 *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_restriction *restr; + isl_set *sink_domain; + isl_set *sink_restr; + isl_map *res; + + 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)); + 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 * at the given level for sink iterations in set_C. * The subset of set_C for which no such iteration can be found is returned @@ -391,9 +587,9 @@ static struct isl_map *last_source(struct isl_access_info *acc, write_map = isl_map_copy(acc->source[j].map); write_map = isl_map_reverse(write_map); dep_map = isl_map_apply_range(read_map, write_map); - after = after_at_level(isl_map_get_dim(dep_map), level); + after = after_at_level(isl_map_get_space(dep_map), level); dep_map = isl_map_intersect(dep_map, after); - 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; @@ -411,7 +607,7 @@ static struct isl_map *last_later_source(struct isl_access_info *acc, int k, int after_level, struct isl_set **empty) { - struct isl_dim *dim; + isl_space *dim; struct isl_set *set_C; struct isl_map *read_map; struct isl_map *write_map; @@ -426,15 +622,15 @@ static struct isl_map *last_later_source(struct isl_access_info *acc, write_map = isl_map_reverse(write_map); dep_map = isl_map_apply_range(read_map, write_map); - dim = isl_dim_join(isl_map_get_dim(acc->source[k].map), - isl_dim_reverse(isl_map_get_dim(acc->source[j].map))); + dim = space_align_and_join(isl_map_get_space(acc->source[k].map), + isl_space_reverse(isl_map_get_space(acc->source[j].map))); after_write = after_at_level(dim, after_level); after_write = isl_map_apply_range(after_write, old_map); after_write = isl_map_reverse(after_write); dep_map = isl_map_intersect(dep_map, after_write); - before_read = after_at_level(isl_map_get_dim(dep_map), before_level); + before_read = after_at_level(isl_map_get_space(dep_map), before_level); dep_map = isl_map_intersect(dep_map, before_read); - 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; @@ -475,7 +671,7 @@ static int intermediate_sources(__isl_keep isl_access_info *acc, int k, level; int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1; - if (isl_map_fast_is_empty(temp_rel[j])) + if (isl_map_plain_is_empty(temp_rel[j])) return 0; for (k = j - 1; k >= 0; --k) { @@ -498,7 +694,7 @@ static int intermediate_sources(__isl_keep isl_access_info *acc, copy = isl_map_copy(temp_rel[j]); T = last_later_source(acc, copy, j, sink_level, k, level, &trest); - if (isl_map_fast_is_empty(T)) { + if (isl_map_plain_is_empty(T)) { isl_set_free(trest); isl_map_free(T); continue; @@ -527,7 +723,7 @@ static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc, write_map = isl_map_copy(acc->source[acc->n_must + j].map); write_map = isl_map_reverse(write_map); dep_map = isl_map_apply_range(read_map, write_map); - after = after_at_level(isl_map_get_dim(dep_map), level); + after = after_at_level(isl_map_get_space(dep_map), level); dep_map = isl_map_intersect(dep_map, after); return isl_map_reverse(dep_map); @@ -543,7 +739,7 @@ static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc, __isl_keep isl_map *old_map, int j, int before_level, int k, int after_level) { - isl_dim *dim; + isl_space *dim; isl_set *set_C; isl_map *read_map; isl_map *write_map; @@ -558,13 +754,13 @@ static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc, write_map = isl_map_reverse(write_map); dep_map = isl_map_apply_range(read_map, write_map); - dim = isl_dim_join(isl_map_get_dim(acc->source[acc->n_must + j].map), - isl_dim_reverse(isl_map_get_dim(acc->source[k].map))); + dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map), + isl_space_reverse(isl_map_get_space(acc->source[k].map))); after_write = after_at_level(dim, after_level); after_write = isl_map_apply_range(after_write, old_map); after_write = isl_map_reverse(after_write); dep_map = isl_map_intersect(dep_map, after_write); - before_read = after_at_level(isl_map_get_dim(dep_map), before_level); + before_read = after_at_level(isl_map_get_space(dep_map), before_level); dep_map = isl_map_intersect(dep_map, before_read); return isl_map_reverse(dep_map); } @@ -588,8 +784,8 @@ static __isl_give isl_map *all_intermediate_sources( for (k = 0; k < acc->n_must; ++k) { int plevel; - if (isl_map_fast_is_empty(may_rel[k]) && - isl_map_fast_is_empty(must_rel[k])) + if (isl_map_plain_is_empty(may_rel[k]) && + isl_map_plain_is_empty(must_rel[k])) continue; plevel = acc->level_before(acc->source[k].data, @@ -616,7 +812,7 @@ static __isl_give isl_map *all_intermediate_sources( isl_set_copy(ran))); T = isl_map_from_domain_and_range( isl_set_universe( - isl_dim_domain(isl_map_get_dim(must_rel[k]))), + isl_space_domain(isl_map_get_space(must_rel[k]))), ran); must_rel[k] = isl_map_subtract(must_rel[k], T); } @@ -631,7 +827,7 @@ static __isl_give isl_map *all_intermediate_sources( * be overkill to use it. */ static __isl_give isl_flow *compute_mem_based_dependences( - __isl_take isl_access_info *acc) + __isl_keep isl_access_info *acc) { int i; isl_set *mustdo; @@ -640,7 +836,7 @@ static __isl_give isl_flow *compute_mem_based_dependences( res = isl_flow_alloc(acc); if (!res) - goto error; + return NULL; mustdo = isl_map_domain(isl_map_copy(acc->sink.map)); maydo = isl_set_copy(mustdo); @@ -648,7 +844,7 @@ static __isl_give isl_flow *compute_mem_based_dependences( for (i = 0; i < acc->n_may; ++i) { int plevel; int is_before; - isl_dim *dim; + isl_space *dim; isl_map *before; isl_map *dep; @@ -656,7 +852,7 @@ static __isl_give isl_flow *compute_mem_based_dependences( is_before = plevel & 1; plevel >>= 1; - dim = isl_map_get_dim(res->dep[i].map); + dim = isl_map_get_space(res->dep[i].map); if (is_before) before = isl_map_lex_le_first(dim, plevel); else @@ -672,12 +868,7 @@ static __isl_give isl_flow *compute_mem_based_dependences( res->may_no_source = isl_set_subtract(maydo, isl_set_copy(mustdo)); res->must_no_source = mustdo; - isl_access_info_free(acc); - return res; -error: - isl_access_info_free(acc); - return NULL; } /* Compute dependences for the case where there is at least one @@ -716,7 +907,7 @@ error: * */ static __isl_give isl_flow *compute_val_based_dependences( - __isl_take isl_access_info *acc) + __isl_keep isl_access_info *acc) { isl_ctx *ctx; isl_flow *res; @@ -727,7 +918,6 @@ static __isl_give isl_flow *compute_val_based_dependences( isl_map **must_rel = NULL; isl_map **may_rel = NULL; - acc = isl_access_info_sort_sources(acc); if (!acc) return NULL; @@ -741,7 +931,7 @@ static __isl_give isl_flow *compute_val_based_dependences( maydo = isl_set_empty_like(mustdo); if (!mustdo || !maydo) goto error; - if (isl_set_fast_is_empty(mustdo)) + if (isl_set_plain_is_empty(mustdo)) goto done; must_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must); @@ -777,8 +967,8 @@ static __isl_give isl_flow *compute_val_based_dependences( intermediate_sources(acc, may_rel, j, level); - if (isl_set_fast_is_empty(mustdo) && - isl_set_fast_is_empty(maydo)) + if (isl_set_plain_is_empty(mustdo) && + isl_set_plain_is_empty(maydo)) break; } for (j = j - 1; j >= 0; --j) { @@ -828,8 +1018,8 @@ static __isl_give isl_flow *compute_val_based_dependences( may_rel[j]); } - if (isl_set_fast_is_empty(mustdo) && - isl_set_fast_is_empty(maydo)) + if (isl_set_plain_is_empty(mustdo) && + isl_set_plain_is_empty(maydo)) break; } @@ -838,10 +1028,8 @@ static __isl_give isl_flow *compute_val_based_dependences( done: res->must_no_source = mustdo; res->may_no_source = maydo; - isl_access_info_free(acc); return res; error: - isl_access_info_free(acc); isl_flow_free(res); isl_set_free(mustdo); isl_set_free(maydo); @@ -870,79 +1058,138 @@ error: __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc) { int j; - struct isl_flow *res; - isl_map *domain_map = NULL; + struct isl_flow *res = NULL; if (!acc) return NULL; - domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map)); + acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map)); acc->sink.map = isl_map_range_map(acc->sink.map); if (!acc->sink.map) goto error; if (acc->n_must == 0) res = compute_mem_based_dependences(acc); - else + else { + acc = isl_access_info_sort_sources(acc); res = compute_val_based_dependences(acc); + } if (!res) - return NULL; + goto error; for (j = 0; j < res->n_source; ++j) { res->dep[j].map = isl_map_apply_range(res->dep[j].map, - isl_map_copy(domain_map)); + isl_map_copy(acc->domain_map)); if (!res->dep[j].map) - goto error2; + goto error; } - res->must_no_source = isl_set_apply(res->must_no_source, - isl_map_copy(domain_map)); - res->may_no_source = isl_set_apply(res->may_no_source, - isl_map_copy(domain_map)); if (!res->must_no_source || !res->may_no_source) - goto error2; + goto error; - isl_map_free(domain_map); + isl_access_info_free(acc); return res; error: - isl_map_free(domain_map); isl_access_info_free(acc); - return NULL; -error2: - isl_map_free(domain_map); isl_flow_free(res); return NULL; } +/* Keep track of some information about a schedule for a given + * access. In particular, keep track of which dimensions + * have a constant value and of the actual constant values. + */ +struct isl_sched_info { + int *is_cst; + isl_vec *cst; +}; + +static void sched_info_free(__isl_take struct isl_sched_info *info) +{ + if (!info) + return; + isl_vec_free(info->cst); + free(info->is_cst); + free(info); +} + +/* Extract information on the constant dimensions of the schedule + * for a given access. The "map" is of the form + * + * [S -> D] -> A + * + * with S the schedule domain, D the iteration domain and A the data domain. + */ +static __isl_give struct isl_sched_info *sched_info_alloc( + __isl_keep isl_map *map) +{ + isl_ctx *ctx; + isl_space *dim; + struct isl_sched_info *info; + int i, n; + isl_int v; + + if (!map) + return NULL; + + dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map))); + if (!dim) + return NULL; + n = isl_space_dim(dim, isl_dim_in); + isl_space_free(dim); + + ctx = isl_map_get_ctx(map); + info = isl_alloc_type(ctx, struct isl_sched_info); + if (!info) + return NULL; + info->is_cst = isl_alloc_array(ctx, int, n); + info->cst = isl_vec_alloc(ctx, n); + if (!info->is_cst || !info->cst) + goto error; + + isl_int_init(v); + for (i = 0; i < n; ++i) { + info->is_cst[i] = isl_map_plain_is_fixed(map, isl_dim_in, i, + &v); + info->cst = isl_vec_set_element(info->cst, i, v); + } + isl_int_clear(v); + + return info; +error: + sched_info_free(info); + return NULL; +} + struct isl_compute_flow_data { isl_union_map *must_source; isl_union_map *may_source; isl_union_map *must_dep; isl_union_map *may_dep; - isl_union_set *must_no_source; - isl_union_set *may_no_source; + isl_union_map *must_no_source; + isl_union_map *may_no_source; int count; int must; - isl_dim *dim; - isl_dim *sink_dim; - isl_dim **source_dim; + isl_space *dim; + struct isl_sched_info *sink_info; + struct isl_sched_info **source_info; isl_access_info *accesses; }; static int count_matching_array(__isl_take isl_map *map, void *user) { int eq; - isl_dim *dim; + isl_space *dim; struct isl_compute_flow_data *data; data = (struct isl_compute_flow_data *)user; - dim = isl_dim_range(isl_map_get_dim(map)); + dim = isl_space_range(isl_map_get_space(map)); - eq = isl_dim_equal(dim, data->dim); + eq = isl_space_is_equal(dim, data->dim); - isl_dim_free(dim); + isl_space_free(dim); isl_map_free(map); if (eq < 0) @@ -956,16 +1203,17 @@ static int count_matching_array(__isl_take isl_map *map, void *user) static int collect_matching_array(__isl_take isl_map *map, void *user) { int eq; - isl_dim *dim; + isl_space *dim; + struct isl_sched_info *info; struct isl_compute_flow_data *data; data = (struct isl_compute_flow_data *)user; - dim = isl_dim_range(isl_map_get_dim(map)); + dim = isl_space_range(isl_map_get_space(map)); - eq = isl_dim_equal(dim, data->dim); + eq = isl_space_is_equal(dim, data->dim); - isl_dim_free(dim); + isl_space_free(dim); if (eq < 0) goto error; @@ -974,11 +1222,11 @@ static int collect_matching_array(__isl_take isl_map *map, void *user) return 0; } - dim = isl_dim_unwrap(isl_dim_domain(isl_map_get_dim(map))); - data->source_dim[data->count] = dim; + info = sched_info_alloc(map); + data->source_info[data->count] = info; data->accesses = isl_access_info_add_source(data->accesses, - map, data->must, dim); + map, data->must, info); data->count++; @@ -988,19 +1236,56 @@ error: return -1; } +/* Determine the shared nesting level and the "textual order" of + * the given accesses. + * + * We first determine the minimal schedule dimension for both accesses. + * + * If among those dimensions, we can find one where both have a fixed + * value and if moreover those values are different, then the previous + * dimension is the last shared nesting level and the textual order + * is determined based on the order of the fixed values. + * If no such fixed values can be found, then we set the shared + * nesting level to the minimal schedule dimension, with no textual ordering. + */ static int before(void *first, void *second) { - isl_dim *dim1 = first; - isl_dim *dim2 = second; + struct isl_sched_info *info1 = first; + struct isl_sched_info *info2 = second; int n1, n2; + int i; + isl_int v1, v2; - n1 = isl_dim_size(dim1, isl_dim_in); - n2 = isl_dim_size(dim2, isl_dim_in); + n1 = isl_vec_size(info1->cst); + n2 = isl_vec_size(info2->cst); if (n2 < n1) n1 = n2; - return 2 * n1 + (dim1 < dim2); + isl_int_init(v1); + isl_int_init(v2); + for (i = 0; i < n1; ++i) { + int r; + + if (!info1->is_cst[i]) + continue; + if (!info2->is_cst[i]) + continue; + isl_vec_get_element(info1->cst, i, &v1); + isl_vec_get_element(info2->cst, i, &v2); + if (isl_int_eq(v1, v2)) + continue; + + r = 2 * i + isl_int_lt(v1, v2); + + isl_int_clear(v1); + isl_int_clear(v2); + return r; + } + isl_int_clear(v1); + isl_int_clear(v2); + + return 2 * n1; } /* Given a sink access, look for all the source accesses that access @@ -1019,10 +1304,10 @@ static int compute_flow(__isl_take isl_map *map, void *user) ctx = isl_map_get_ctx(map); data->accesses = NULL; - data->sink_dim = NULL; - data->source_dim = NULL; + data->sink_info = NULL; + data->source_info = NULL; data->count = 0; - data->dim = isl_dim_range(isl_map_get_dim(map)); + data->dim = isl_space_range(isl_map_get_space(map)); if (isl_union_map_foreach_map(data->must_source, &count_matching_array, data) < 0) @@ -1031,11 +1316,14 @@ static int compute_flow(__isl_take isl_map *map, void *user) &count_matching_array, data) < 0) goto error; - data->sink_dim = isl_dim_unwrap(isl_dim_domain(isl_map_get_dim(map))); - data->source_dim = isl_calloc_array(ctx, isl_dim *, data->count); + data->sink_info = sched_info_alloc(map); + data->source_info = isl_calloc_array(ctx, struct isl_sched_info *, + data->count); data->accesses = isl_access_info_alloc(isl_map_copy(map), - data->sink_dim, &before, data->count); + data->sink_info, &before, data->count); + if (!data->sink_info || !data->source_info || !data->accesses) + goto error; data->count = 0; data->must = 1; if (isl_union_map_foreach_map(data->must_source, @@ -1052,10 +1340,10 @@ static int compute_flow(__isl_take isl_map *map, void *user) if (!flow) goto error; - data->must_no_source = isl_union_set_union(data->must_no_source, - isl_union_set_from_set(isl_set_copy(flow->must_no_source))); - data->may_no_source = isl_union_set_union(data->may_no_source, - isl_union_set_from_set(isl_set_copy(flow->may_no_source))); + data->must_no_source = isl_union_map_union(data->must_no_source, + isl_union_map_from_map(isl_flow_get_no_source(flow, 1))); + data->may_no_source = isl_union_map_union(data->may_no_source, + isl_union_map_from_map(isl_flow_get_no_source(flow, 0))); for (i = 0; i < flow->n_source; ++i) { isl_union_map *dep; @@ -1068,25 +1356,25 @@ static int compute_flow(__isl_take isl_map *map, void *user) isl_flow_free(flow); - isl_dim_free(data->sink_dim); - if (data->source_dim) { + sched_info_free(data->sink_info); + if (data->source_info) { for (i = 0; i < data->count; ++i) - isl_dim_free(data->source_dim[i]); - free(data->source_dim); + sched_info_free(data->source_info[i]); + free(data->source_info); } - isl_dim_free(data->dim); + isl_space_free(data->dim); isl_map_free(map); return 0; error: isl_access_info_free(data->accesses); - isl_dim_free(data->sink_dim); - if (data->source_dim) { + sched_info_free(data->sink_info); + if (data->source_info) { for (i = 0; i < data->count; ++i) - isl_dim_free(data->source_dim[i]); - free(data->source_dim); + sched_info_free(data->source_info[i]); + free(data->source_info); } - isl_dim_free(data->dim); + isl_space_free(data->dim); isl_map_free(map); return -1; @@ -1113,23 +1401,23 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink, __isl_take isl_union_map *may_source, __isl_take isl_union_map *schedule, __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep, - __isl_give isl_union_set **must_no_source, - __isl_give isl_union_set **may_no_source) + __isl_give isl_union_map **must_no_source, + __isl_give isl_union_map **may_no_source) { - isl_dim *dim; + isl_space *dim; isl_union_map *range_map = NULL; struct isl_compute_flow_data data; sink = isl_union_map_align_params(sink, - isl_union_map_get_dim(must_source)); + isl_union_map_get_space(must_source)); sink = isl_union_map_align_params(sink, - isl_union_map_get_dim(may_source)); + isl_union_map_get_space(may_source)); sink = isl_union_map_align_params(sink, - isl_union_map_get_dim(schedule)); - dim = isl_union_map_get_dim(sink); - must_source = isl_union_map_align_params(must_source, isl_dim_copy(dim)); - may_source = isl_union_map_align_params(may_source, isl_dim_copy(dim)); - schedule = isl_union_map_align_params(schedule, isl_dim_copy(dim)); + isl_union_map_get_space(schedule)); + dim = isl_union_map_get_space(sink); + must_source = isl_union_map_align_params(must_source, isl_space_copy(dim)); + may_source = isl_union_map_align_params(may_source, isl_space_copy(dim)); + schedule = isl_union_map_align_params(schedule, isl_space_copy(dim)); schedule = isl_union_map_reverse(schedule); range_map = isl_union_map_range_map(schedule); @@ -1142,14 +1430,14 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink, data.must_source = must_source; data.may_source = may_source; data.must_dep = must_dep ? - isl_union_map_empty(isl_dim_copy(dim)) : NULL; - data.may_dep = may_dep ? isl_union_map_empty(isl_dim_copy(dim)) : NULL; + isl_union_map_empty(isl_space_copy(dim)) : NULL; + data.may_dep = may_dep ? isl_union_map_empty(isl_space_copy(dim)) : NULL; data.must_no_source = must_no_source ? - isl_union_set_empty(isl_dim_copy(dim)) : NULL; + isl_union_map_empty(isl_space_copy(dim)) : NULL; data.may_no_source = may_no_source ? - isl_union_set_empty(isl_dim_copy(dim)) : NULL; + isl_union_map_empty(isl_space_copy(dim)) : NULL; - isl_dim_free(dim); + isl_space_free(dim); if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0) goto error; @@ -1173,13 +1461,13 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink, *may_dep = data.may_dep; } if (must_no_source) { - data.must_no_source = isl_union_set_apply(data.must_no_source, - isl_union_map_copy(range_map)); + data.must_no_source = isl_union_map_apply_domain( + data.must_no_source, isl_union_map_copy(range_map)); *must_no_source = data.must_no_source; } if (may_no_source) { - data.may_no_source = isl_union_set_apply(data.may_no_source, - isl_union_map_copy(range_map)); + data.may_no_source = isl_union_map_apply_domain( + data.may_no_source, isl_union_map_copy(range_map)); *may_no_source = data.may_no_source; } @@ -1193,8 +1481,8 @@ error: isl_union_map_free(may_source); isl_union_map_free(data.must_dep); isl_union_map_free(data.may_dep); - isl_union_set_free(data.must_no_source); - isl_union_set_free(data.may_no_source); + isl_union_map_free(data.must_no_source); + isl_union_map_free(data.may_no_source); if (must_dep) *must_dep = NULL;