isl_map_lexopt_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  * Copyright 2012      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   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, France
  10  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  11  */
  12
  13 /* Function for computing the lexicographic optimum of a map
  14  * in the form of either an isl_map or an isl_pw_multi_aff.
  15  */
  16
  17 #define xSF(TYPE,SUFFIX) TYPE ## SUFFIX
  18 #define SF(TYPE,SUFFIX) xSF(TYPE,SUFFIX)
  19
  20 /* Compute the lexicographic minimum (or maximum if "flags" includes
  21  * 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 that
  23  * contains those parts of the domain where there is no solution.
  24  * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum
  25  * should be computed over the domain of "bmap".  "empty" is also NULL
  26  * in this case.
  27  * If "bmap" is marked as rational (ISL_BASIC_MAP_RATIONAL),
  28  * then the rational optimum is computed.  Otherwise, the integral optimum
  29  * is computed.
  30  */
  31 static __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 minimal
  70  * (or maximal) image element for each domain element in dom.
  71  * If empty is not NULL, then set *empty to those elements in dom
  72  * that do not have an image element.
  73  * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum
  74  * should be computed over the domain of "bmap".  "empty" is also NULL
  75  * in this case.
  76  *
  77  * We first make sure the basic sets in dom are disjoint and then
  78  * simply collect the results over each of the basic sets separately.
  79  * We could probably improve the efficiency a bit by moving the union
  80  * 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 consider
  84  * the disjuncts of the domain.
  85  */
  86 static __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                 else
 107                         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;
 134 error:
 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" includes
 143  * 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
 157 static __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. */
 161 static __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 minimal
 167  * (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  */
 172 static __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);
 192 error:
 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" includes
 201  * 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 }