230 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 * Copyright 2012 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege,8 * INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,9 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France11 */12 13/* Function for computing the lexicographic optimum of a map14 * in the form of either an isl_map or an isl_pw_multi_aff.15 */16 17#define xSF(TYPE,SUFFIX) TYPE ## SUFFIX18#define SF(TYPE,SUFFIX) xSF(TYPE,SUFFIX)19 20/* Compute the lexicographic minimum (or maximum if "flags" includes21 * ISL_OPT_MAX) of "bmap" over the domain "dom" and return the result.22 * If "empty" is not NULL, then *empty is assigned a set that23 * contains those parts of the domain where there is no solution.24 * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum25 * should be computed over the domain of "bmap". "empty" is also NULL26 * in this case.27 * If "bmap" is marked as rational (ISL_BASIC_MAP_RATIONAL),28 * then the rational optimum is computed. Otherwise, the integral optimum29 * is computed.30 */31static __isl_give TYPE *SF(isl_basic_map_partial_lexopt,SUFFIX)(32 __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,33 __isl_give isl_set **empty, unsigned flags)34{35 return SF(isl_tab_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty,36 flags);37}38 39__isl_give TYPE *SF(isl_basic_map_partial_lexmax,SUFFIX)(40 __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,41 __isl_give isl_set **empty)42{43 unsigned flags = ISL_OPT_MAX;44 return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, flags);45}46 47__isl_give TYPE *SF(isl_basic_map_partial_lexmin,SUFFIX)(48 __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *dom,49 __isl_give isl_set **empty)50{51 unsigned flags = 0;52 return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, flags);53}54 55__isl_give TYPE *SF(isl_basic_set_partial_lexmin,SUFFIX)(56 __isl_take isl_basic_set *bset, __isl_take isl_basic_set *dom,57 __isl_give isl_set **empty)58{59 return SF(isl_basic_map_partial_lexmin,SUFFIX)(bset, dom, empty);60}61 62__isl_give TYPE *SF(isl_basic_set_partial_lexmax,SUFFIX)(63 __isl_take isl_basic_set *bset, __isl_take isl_basic_set *dom,64 __isl_give isl_set **empty)65{66 return SF(isl_basic_map_partial_lexmax,SUFFIX)(bset, dom, empty);67}68 69/* Given a basic map "bmap", compute the lexicographically minimal70 * (or maximal) image element for each domain element in dom.71 * If empty is not NULL, then set *empty to those elements in dom72 * that do not have an image element.73 * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum74 * should be computed over the domain of "bmap". "empty" is also NULL75 * in this case.76 *77 * We first make sure the basic sets in dom are disjoint and then78 * simply collect the results over each of the basic sets separately.79 * We could probably improve the efficiency a bit by moving the union80 * domain down into the parametric integer programming.81 *82 * If a full optimum is being computed (i.e., "flags" includes ISL_OPT_FULL),83 * then no domain is given and there is then also no need to consider84 * the disjuncts of the domain.85 */86static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)(87 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,88 __isl_give isl_set **empty, unsigned flags)89{90 int i;91 TYPE *res;92 isl_set *all_empty;93 94 if (ISL_FL_ISSET(flags, ISL_OPT_FULL))95 return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, NULL,96 empty, flags);97 98 dom = isl_set_make_disjoint(dom);99 if (!dom)100 goto error;101 102 if (isl_set_plain_is_empty(dom)) {103 isl_space *space = isl_basic_map_get_space(bmap);104 if (empty)105 *empty = dom;106 else107 isl_set_free(dom);108 isl_basic_map_free(bmap);109 return EMPTY(space);110 }111 112 res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap),113 isl_basic_set_copy(dom->p[0]), empty, flags);114 115 if (empty)116 all_empty = *empty;117 for (i = 1; i < dom->n; ++i) {118 TYPE *res_i;119 120 res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)(121 isl_basic_map_copy(bmap),122 isl_basic_set_copy(dom->p[i]), empty, flags);123 124 res = ADD(res, res_i);125 if (empty)126 all_empty = isl_set_union_disjoint(all_empty, *empty);127 }128 129 if (empty)130 *empty = all_empty;131 isl_set_free(dom);132 isl_basic_map_free(bmap);133 return res;134error:135 if (empty)136 *empty = NULL;137 isl_set_free(dom);138 isl_basic_map_free(bmap);139 return NULL;140}141 142/* Compute the lexicographic minimum (or maximum if "flags" includes143 * ISL_OPT_MAX) of "bmap" over its domain.144 */145__isl_give TYPE *SF(isl_basic_map_lexopt,SUFFIX)(146 __isl_take isl_basic_map *bmap, unsigned flags)147{148 ISL_FL_SET(flags, ISL_OPT_FULL);149 return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, NULL, NULL, flags);150}151 152__isl_give TYPE *SF(isl_basic_map_lexmin,SUFFIX)(__isl_take isl_basic_map *bmap)153{154 return SF(isl_basic_map_lexopt,SUFFIX)(bmap, 0);155}156 157static __isl_give TYPE *SF(isl_map_partial_lexopt_aligned,SUFFIX)(158 __isl_take isl_map *map, __isl_take isl_set *dom,159 __isl_give isl_set **empty, unsigned flags);160/* This function is currently only used when TYPE is defined as isl_map. */161static __isl_give TYPE *SF(isl_map_partial_lexopt,SUFFIX)(162 __isl_take isl_map *map, __isl_take isl_set *dom,163 __isl_give isl_set **empty, unsigned flags)164 __attribute__ ((unused));165 166/* Given a map "map", compute the lexicographically minimal167 * (or maximal) image element for each domain element in dom.168 * Set *empty to those elements in dom that do not have an image element.169 *170 * Align parameters if needed and then call isl_map_partial_lexopt_aligned.171 */172static __isl_give TYPE *SF(isl_map_partial_lexopt,SUFFIX)(173 __isl_take isl_map *map, __isl_take isl_set *dom,174 __isl_give isl_set **empty, unsigned flags)175{176 isl_bool aligned;177 178 aligned = isl_map_set_has_equal_params(map, dom);179 if (aligned < 0)180 goto error;181 if (aligned)182 return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom,183 empty, flags);184 if (!isl_space_has_named_params(map->dim) ||185 !isl_space_has_named_params(dom->dim))186 isl_die(map->ctx, isl_error_invalid,187 "unaligned unnamed parameters", goto error);188 map = isl_map_align_params(map, isl_map_get_space(dom));189 dom = isl_map_align_params(dom, isl_map_get_space(map));190 return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, empty,191 flags);192error:193 if (empty)194 *empty = NULL;195 isl_set_free(dom);196 isl_map_free(map);197 return NULL;198}199 200/* Compute the lexicographic minimum (or maximum if "flags" includes201 * ISL_OPT_MAX) of "map" over its domain.202 */203__isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map,204 unsigned flags)205{206 ISL_FL_SET(flags, ISL_OPT_FULL);207 return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, NULL, NULL,208 flags);209}210 211__isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map)212{213 return SF(isl_map_lexopt,SUFFIX)(map, 0);214}215 216__isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map)217{218 return SF(isl_map_lexopt,SUFFIX)(map, ISL_OPT_MAX);219}220 221__isl_give TYPE *SF(isl_set_lexmin,SUFFIX)(__isl_take isl_set *set)222{223 return SF(isl_map_lexmin,SUFFIX)(set);224}225 226__isl_give TYPE *SF(isl_set_lexmax,SUFFIX)(__isl_take isl_set *set)227{228 return SF(isl_map_lexmax,SUFFIX)(set);229}230