From 5494a21bf94a821dd43a4e519b31b3ad3b73325f Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sun, 31 Jan 2010 22:01:41 +0100 Subject: [PATCH] add isl_map_{partial_,}lexopt --- doc/user.pod | 40 ++++++++--- include/isl_map.h | 8 +++ include/isl_set.h | 8 +++ isl_map.c | 210 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 256 insertions(+), 10 deletions(-) diff --git a/doc/user.pod b/doc/user.pod index e0d98c7..fbeceb3 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -853,13 +853,13 @@ the same (number of) parameters. =head3 Lexicographic Optimization -Given a basic set C and a zero-dimensional domain C, +Given a (basic) set C (or C) and a zero-dimensional domain C, the following functions compute a set that contains the lexicographic minimum or maximum -of the elements in C for those values of the parameters +of the elements in C (or C) for those values of the parameters that satisfy C. If C is not C, then C<*empty> is assigned a set -that contains the parameter values in C for which C +that contains the parameter values in C for which C (or C) has no elements. In other words, the union of the parameter values for which the result is non-empty and of C<*empty> @@ -873,25 +873,35 @@ is equal to C. __isl_take isl_basic_set *bset, __isl_take isl_basic_set *dom, __isl_give isl_set **empty); + __isl_give isl_set *isl_set_partial_lexmin( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty); + __isl_give isl_set *isl_set_partial_lexmax( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty); -Given a basic set C, the following functions simply +Given a (basic) set C (or C), the following functions simply return a set containing the lexicographic minimum or maximum -of the elements in C. +of the elements in C (or C). __isl_give isl_set *isl_basic_set_lexmin( __isl_take isl_basic_set *bset); __isl_give isl_set *isl_basic_set_lexmax( __isl_take isl_basic_set *bset); + __isl_give isl_set *isl_set_lexmin( + __isl_take isl_set *set); + __isl_give isl_set *isl_set_lexmax( + __isl_take isl_set *set); -Given a basic relation C and a domain C, +Given a (basic) relation C (or C) and a domain C, the following functions compute a relation that maps each element of C to the single lexicographic minimum or maximum of the elements that are associated to that same -element in C. +element in C (or C). If C is not C, then C<*empty> is assigned a set that contains the elements in C that do not map -to any elements in C. +to any elements in C (or C). In other words, the union of the domain of the result and of C<*empty> is equal to C. @@ -903,16 +913,26 @@ is equal to C. __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, __isl_give isl_set **empty); + __isl_give isl_map *isl_map_partial_lexmax( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty); + __isl_give isl_map *isl_map_partial_lexmin( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty); -Given a basic map C, the following functions simply +Given a (basic) map C (or C), the following functions simply return a map mapping each element in the domain of -C to the lexicographic minimum or maximum +C (or C) to the lexicographic minimum or maximum of all elements associated to that element. __isl_give isl_map *isl_basic_map_lexmin( __isl_take isl_basic_map *bmap); __isl_give isl_map *isl_basic_map_lexmax( __isl_take isl_basic_map *bmap); + __isl_give isl_map *isl_map_lexmin( + __isl_take isl_map *map); + __isl_give isl_map *isl_map_lexmax( + __isl_take isl_map *map); =head1 Applications diff --git a/include/isl_map.h b/include/isl_map.h index ced6a17..06719be 100644 --- a/include/isl_map.h +++ b/include/isl_map.h @@ -219,8 +219,16 @@ __isl_give isl_map *isl_basic_map_partial_lexmax( __isl_give isl_map *isl_basic_map_partial_lexmin( __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, __isl_give isl_set **empty); +__isl_give isl_map *isl_map_partial_lexmax( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty); +__isl_give isl_map *isl_map_partial_lexmin( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty); __isl_give isl_map *isl_basic_map_lexmin(__isl_take isl_basic_map *bmap); __isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap); +__isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map); +__isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map); int isl_basic_map_foreach_lexmin(__isl_keep isl_basic_map *bmap, int (*fn)(__isl_take isl_basic_set *dom, __isl_take isl_mat *map, void *user), diff --git a/include/isl_set.h b/include/isl_set.h index abf16c7..16d78cb 100644 --- a/include/isl_set.h +++ b/include/isl_set.h @@ -162,8 +162,16 @@ __isl_give isl_set *isl_basic_set_partial_lexmin( __isl_give isl_set *isl_basic_set_partial_lexmax( __isl_take isl_basic_set *bset, __isl_take isl_basic_set *dom, __isl_give isl_set **empty); +__isl_give isl_set *isl_set_partial_lexmin( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty); +__isl_give isl_set *isl_set_partial_lexmax( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty); __isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset); __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset); +__isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set); +__isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set); __isl_give isl_set *isl_basic_set_union( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2); diff --git a/isl_map.c b/isl_map.c index d0009de..bf4c81f 100644 --- a/isl_map.c +++ b/isl_map.c @@ -3431,6 +3431,181 @@ struct isl_set *isl_basic_set_partial_lexmax( dom, empty); } +/* Given a basic map "bmap", compute the lexicograhically minimal + * (or maximal) image element for each domain element in dom. + * Set *empty to those elements in dom that do not have an image element. + * + * We first make sure the basic sets in dom are disjoint and then + * simply collect the results over each of the basic sets separately. + * We could probably improve the efficiency a bit by moving the union + * domain down into the parametric integer programming. + */ +static __isl_give isl_map *basic_map_partial_lexopt( + __isl_take isl_basic_map *bmap, __isl_take isl_set *dom, + __isl_give isl_set **empty, int max) +{ + int i; + struct isl_map *res; + + dom = isl_set_make_disjoint(dom); + if (!dom) + goto error; + + if (isl_set_fast_is_empty(dom)) { + res = isl_map_empty_like_basic_map(bmap); + *empty = isl_set_empty_like(dom); + isl_set_free(dom); + isl_basic_map_free(bmap); + return res; + } + + res = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap), + isl_basic_set_copy(dom->p[0]), empty, max); + + for (i = 1; i < dom->n; ++i) { + struct isl_map *res_i; + struct isl_set *empty_i; + + res_i = isl_basic_map_partial_lexopt(isl_basic_map_copy(bmap), + isl_basic_set_copy(dom->p[i]), &empty_i, max); + + res = isl_map_union_disjoint(res, res_i); + *empty = isl_set_union_disjoint(*empty, empty_i); + } + + isl_set_free(dom); + isl_basic_map_free(bmap); + return res; +error: + *empty = NULL; + isl_set_free(dom); + isl_basic_map_free(bmap); + return NULL; +} + +/* Given a map "map", compute the lexicograhically minimal + * (or maximal) image element for each domain element in dom. + * Set *empty to those elements in dom that do not have an image element. + * + * We first compute the lexicographically minimal or maximal element + * in the first basic map. This results in a partial solution "res" + * and a subset "todo" of dom that still need to be handled. + * We then consider each of the remaining maps in "map" and successively + * improve both "res" and "todo". + * + * Let res^k and todo^k be the results after k steps and let i = k + 1. + * Assume we are computing the lexicographical maximum. + * We first intersect basic map i with a relation that maps elements + * to elements that are lexicographically larger than the image elements + * in res^k and the compute the maximum image element of this intersection. + * The result ("better") corresponds to those image elements in basic map i + * that are better than what we had before. The remainder ("keep") are the + * domain elements for which the image element in res_k was better. + * We also compute the lexicographical maximum of basic map i in todo^k. + * res^i is the result of the operation + better + those elements in + * res^k that we should keep + * todo^i is the remainder of the maximum operation on todo^k. + */ +static __isl_give isl_map *isl_map_partial_lexopt( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty, int max) +{ + int i; + struct isl_map *res; + struct isl_set *todo; + + if (!map || !dom) + goto error; + + if (isl_map_fast_is_empty(map)) { + if (empty) + *empty = dom; + else + isl_set_free(dom); + return map; + } + + res = basic_map_partial_lexopt(isl_basic_map_copy(map->p[0]), + isl_set_copy(dom), &todo, max); + + for (i = 1; i < map->n; ++i) { + struct isl_map *lt; + struct isl_map *better; + struct isl_set *keep; + struct isl_map *res_i; + struct isl_set *todo_i; + struct isl_dim *dim = isl_map_get_dim(res); + + dim = isl_dim_range(dim); + if (max) + lt = isl_map_lex_lt(dim); + else + lt = isl_map_lex_gt(dim); + lt = isl_map_apply_range(isl_map_copy(res), lt); + lt = isl_map_intersect(lt, + isl_map_from_basic_map(isl_basic_map_copy(map->p[i]))); + better = isl_map_partial_lexopt(lt, + isl_map_domain(isl_map_copy(res)), + &keep, max); + + res_i = basic_map_partial_lexopt(isl_basic_map_copy(map->p[i]), + todo, &todo_i, max); + + res = isl_map_intersect_domain(res, keep); + res = isl_map_union_disjoint(res, res_i); + res = isl_map_union_disjoint(res, better); + todo = todo_i; + } + + isl_set_free(dom); + isl_map_free(map); + + if (empty) + *empty = todo; + else + isl_set_free(todo); + + return res; +error: + if (empty) + *empty = NULL; + isl_set_free(dom); + isl_map_free(map); + return NULL; +} + +__isl_give isl_map *isl_map_partial_lexmax( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty) +{ + return isl_map_partial_lexopt(map, dom, empty, 1); +} + +__isl_give isl_map *isl_map_partial_lexmin( + __isl_take isl_map *map, __isl_take isl_set *dom, + __isl_give isl_set **empty) +{ + return isl_map_partial_lexopt(map, dom, empty, 0); +} + +__isl_give isl_set *isl_set_partial_lexmin( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty) +{ + return (struct isl_set *) + isl_map_partial_lexmin((struct isl_map *)set, + dom, empty); +} + +__isl_give isl_set *isl_set_partial_lexmax( + __isl_take isl_set *set, __isl_take isl_set *dom, + __isl_give isl_set **empty) +{ + return (struct isl_set *) + isl_map_partial_lexmax((struct isl_map *)set, + dom, empty); +} + __isl_give isl_map *isl_basic_map_lexopt(__isl_take isl_basic_map *bmap, int max) { struct isl_basic_set *dom = NULL; @@ -3466,6 +3641,41 @@ __isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset) return (isl_set *)isl_basic_map_lexmax((isl_basic_map *)bset); } +__isl_give isl_map *isl_map_lexopt(__isl_take isl_map *map, int max) +{ + struct isl_set *dom = NULL; + struct isl_dim *dom_dim; + + if (!map) + goto error; + dom_dim = isl_dim_domain(isl_dim_copy(map->dim)); + dom = isl_set_universe(dom_dim); + return isl_map_partial_lexopt(map, dom, NULL, max); +error: + isl_map_free(map); + return NULL; +} + +__isl_give isl_map *isl_map_lexmin(__isl_take isl_map *map) +{ + return isl_map_lexopt(map, 0); +} + +__isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map) +{ + return isl_map_lexopt(map, 1); +} + +__isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set) +{ + return (isl_set *)isl_map_lexmin((isl_map *)set); +} + +__isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set) +{ + return (isl_set *)isl_map_lexmax((isl_map *)set); +} + static struct isl_map *isl_map_reset_dim(struct isl_map *map, struct isl_dim *dim) { -- 2.7.4