| /* |
| * Copyright 2010 INRIA Saclay |
| * Copyright 2012 Ecole Normale Superieure |
| * |
| * Use of this software is governed by the MIT license |
| * |
| * Written by Sven Verdoolaege, |
| * INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, |
| * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France |
| * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France |
| */ |
| |
| /* Function for computing the lexicographic optimum of a map |
| * in the form of either an isl_map or an isl_pw_multi_aff. |
| */ |
| |
| #define xSF(TYPE,SUFFIX) TYPE ## SUFFIX |
| #define SF(TYPE,SUFFIX) xSF(TYPE,SUFFIX) |
| |
| /* Given a basic map "bmap", compute the lexicographically 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 TYPE *SF(basic_map_partial_lexopt,SUFFIX)( |
| __isl_take isl_basic_map *bmap, __isl_take isl_set *dom, |
| __isl_give isl_set **empty, int max) |
| { |
| int i; |
| TYPE *res; |
| |
| dom = isl_set_make_disjoint(dom); |
| if (!dom) |
| goto error; |
| |
| if (isl_set_plain_is_empty(dom)) { |
| isl_space *space = isl_basic_map_get_space(bmap); |
| if (empty) |
| *empty = dom; |
| else |
| isl_set_free(dom); |
| isl_basic_map_free(bmap); |
| return EMPTY(space); |
| } |
| |
| res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap), |
| isl_basic_set_copy(dom->p[0]), empty, max); |
| |
| for (i = 1; i < dom->n; ++i) { |
| TYPE *res_i; |
| isl_set *empty_i; |
| |
| res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)( |
| isl_basic_map_copy(bmap), |
| isl_basic_set_copy(dom->p[i]), &empty_i, max); |
| |
| res = ADD(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; |
| } |
| |
| static __isl_give TYPE *SF(isl_map_partial_lexopt_aligned,SUFFIX)( |
| __isl_take isl_map *map, __isl_take isl_set *dom, |
| __isl_give isl_set **empty, int max); |
| |
| /* Given a map "map", compute the lexicographically 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. |
| * |
| * Align parameters if needed and then call isl_map_partial_lexopt_aligned. |
| */ |
| static __isl_give TYPE *SF(isl_map_partial_lexopt,SUFFIX)( |
| __isl_take isl_map *map, __isl_take isl_set *dom, |
| __isl_give isl_set **empty, int max) |
| { |
| if (!map || !dom) |
| goto error; |
| if (isl_space_match(map->dim, isl_dim_param, dom->dim, isl_dim_param)) |
| return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, |
| empty, max); |
| if (!isl_space_has_named_params(map->dim) || |
| !isl_space_has_named_params(dom->dim)) |
| isl_die(map->ctx, isl_error_invalid, |
| "unaligned unnamed parameters", goto error); |
| map = isl_map_align_params(map, isl_map_get_space(dom)); |
| dom = isl_map_align_params(dom, isl_map_get_space(map)); |
| return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, empty, max); |
| error: |
| if (empty) |
| *empty = NULL; |
| isl_set_free(dom); |
| isl_map_free(map); |
| return NULL; |
| } |
| |
| __isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map, int max) |
| { |
| isl_set *dom = NULL; |
| isl_space *dom_space; |
| |
| if (!map) |
| goto error; |
| dom_space = isl_space_domain(isl_space_copy(map->dim)); |
| dom = isl_set_universe(dom_space); |
| return SF(isl_map_partial_lexopt,SUFFIX)(map, dom, NULL, max); |
| error: |
| isl_map_free(map); |
| return NULL; |
| } |
| |
| __isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map) |
| { |
| return SF(isl_map_lexopt,SUFFIX)(map, 0); |
| } |
| |
| __isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map) |
| { |
| return SF(isl_map_lexopt,SUFFIX)(map, 1); |
| } |
| |
| __isl_give TYPE *SF(isl_set_lexmin,SUFFIX)(__isl_take isl_set *set) |
| { |
| return SF(isl_map_lexmin,SUFFIX)(set); |
| } |
| |
| __isl_give TYPE *SF(isl_set_lexmax,SUFFIX)(__isl_take isl_set *set) |
| { |
| return SF(isl_map_lexmax,SUFFIX)(set); |
| } |