| /* |
| * 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) |
| |
| /* Compute the lexicographic minimum (or maximum if "flags" includes |
| * ISL_OPT_MAX) of "bmap" over the domain "dom" and return the result. |
| * If "empty" is not NULL, then *empty is assigned a set that |
| * contains those parts of the domain where there is no solution. |
| * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum |
| * should be computed over the domain of "bmap". "empty" is also NULL |
| * in this case. |
| * If "bmap" is marked as rational (ISL_BASIC_MAP_RATIONAL), |
| * then the rational optimum is computed. Otherwise, the integral optimum |
| * is computed. |
| */ |
| static __isl_give TYPE *SF(isl_basic_map_partial_lexopt,SUFFIX)( |
| __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, |
| __isl_give isl_set **empty, unsigned flags) |
| { |
| return SF(isl_tab_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, |
| flags); |
| } |
| |
| __isl_give TYPE *SF(isl_basic_map_partial_lexmax,SUFFIX)( |
| __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, |
| __isl_give isl_set **empty) |
| { |
| unsigned flags = ISL_OPT_MAX; |
| return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, flags); |
| } |
| |
| __isl_give TYPE *SF(isl_basic_map_partial_lexmin,SUFFIX)( |
| __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom, |
| __isl_give isl_set **empty) |
| { |
| unsigned flags = 0; |
| return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, flags); |
| } |
| |
| __isl_give TYPE *SF(isl_basic_set_partial_lexmin,SUFFIX)( |
| __isl_take isl_basic_set *bset, __isl_take isl_basic_set *dom, |
| __isl_give isl_set **empty) |
| { |
| return SF(isl_basic_map_partial_lexmin,SUFFIX)(bset, dom, empty); |
| } |
| |
| __isl_give TYPE *SF(isl_basic_set_partial_lexmax,SUFFIX)( |
| __isl_take isl_basic_set *bset, __isl_take isl_basic_set *dom, |
| __isl_give isl_set **empty) |
| { |
| return SF(isl_basic_map_partial_lexmax,SUFFIX)(bset, dom, empty); |
| } |
| |
| /* Given a basic map "bmap", compute the lexicographically minimal |
| * (or maximal) image element for each domain element in dom. |
| * If empty is not NULL, then set *empty to those elements in dom |
| * that do not have an image element. |
| * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum |
| * should be computed over the domain of "bmap". "empty" is also NULL |
| * in this case. |
| * |
| * 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. |
| * |
| * If a full optimum is being computed (i.e., "flags" includes ISL_OPT_FULL), |
| * then no domain is given and there is then also no need to consider |
| * the disjuncts of the domain. |
| */ |
| 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, unsigned flags) |
| { |
| int i; |
| TYPE *res; |
| isl_set *all_empty; |
| |
| if (ISL_FL_ISSET(flags, ISL_OPT_FULL)) |
| return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, NULL, |
| empty, flags); |
| |
| 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, flags); |
| |
| if (empty) |
| all_empty = *empty; |
| for (i = 1; i < dom->n; ++i) { |
| TYPE *res_i; |
| |
| res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)( |
| isl_basic_map_copy(bmap), |
| isl_basic_set_copy(dom->p[i]), empty, flags); |
| |
| res = ADD(res, res_i); |
| if (empty) |
| all_empty = isl_set_union_disjoint(all_empty, *empty); |
| } |
| |
| if (empty) |
| *empty = all_empty; |
| isl_set_free(dom); |
| isl_basic_map_free(bmap); |
| return res; |
| error: |
| if (empty) |
| *empty = NULL; |
| isl_set_free(dom); |
| isl_basic_map_free(bmap); |
| return NULL; |
| } |
| |
| /* Compute the lexicographic minimum (or maximum if "flags" includes |
| * ISL_OPT_MAX) of "bmap" over its domain. |
| */ |
| __isl_give TYPE *SF(isl_basic_map_lexopt,SUFFIX)( |
| __isl_take isl_basic_map *bmap, unsigned flags) |
| { |
| ISL_FL_SET(flags, ISL_OPT_FULL); |
| return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, NULL, NULL, flags); |
| } |
| |
| __isl_give TYPE *SF(isl_basic_map_lexmin,SUFFIX)(__isl_take isl_basic_map *bmap) |
| { |
| return SF(isl_basic_map_lexopt,SUFFIX)(bmap, 0); |
| } |
| |
| 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, unsigned flags); |
| /* This function is currently only used when TYPE is defined as isl_map. */ |
| 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, unsigned flags) |
| __attribute__ ((unused)); |
| |
| /* 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, unsigned flags) |
| { |
| isl_bool aligned; |
| |
| aligned = isl_map_set_has_equal_params(map, dom); |
| if (aligned < 0) |
| goto error; |
| if (aligned) |
| return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, |
| empty, flags); |
| 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, |
| flags); |
| error: |
| if (empty) |
| *empty = NULL; |
| isl_set_free(dom); |
| isl_map_free(map); |
| return NULL; |
| } |
| |
| /* Compute the lexicographic minimum (or maximum if "flags" includes |
| * ISL_OPT_MAX) of "map" over its domain. |
| */ |
| __isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map, |
| unsigned flags) |
| { |
| ISL_FL_SET(flags, ISL_OPT_FULL); |
| return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, NULL, NULL, |
| flags); |
| } |
| |
| __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, ISL_OPT_MAX); |
| } |
| |
| __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); |
| } |