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 /* Given a basic map "bmap", compute the lexicographically minimal
  21  * (or maximal) image element for each domain element in dom.
  22  * If empty is not NULL, then set *empty to those elements in dom
  23  * that do not have an image element.
  24  *
  25  * We first make sure the basic sets in dom are disjoint and then
  26  * simply collect the results over each of the basic sets separately.
  27  * We could probably improve the efficiency a bit by moving the union
  28  * domain down into the parametric integer programming.
  29  */
  30 static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)(
  31         __isl_take isl_basic_map *bmap, __isl_take isl_set *dom,
  32         __isl_give isl_set **empty, int max)
  33 {
  34         int i;
  35         TYPE *res;
  36         isl_set *all_empty;
  37
  38         dom = isl_set_make_disjoint(dom);
  39         if (!dom)
  40                 goto error;
  41
  42         if (isl_set_plain_is_empty(dom)) {
  43                 isl_space *space = isl_basic_map_get_space(bmap);
  44                 if (empty)
  45                         *empty = dom;
  46                 else
  47                         isl_set_free(dom);
  48                 isl_basic_map_free(bmap);
  49                 return EMPTY(space);
  50         }
  51
  52         res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap),
  53                         isl_basic_set_copy(dom->p[0]), empty, max);
  54
  55         if (empty)
  56                 all_empty = *empty;
  57         for (i = 1; i < dom->n; ++i) {
  58                 TYPE *res_i;
  59
  60                 res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)(
  61                                 isl_basic_map_copy(bmap),
  62                                 isl_basic_set_copy(dom->p[i]), empty, max);
  63
  64                 res = ADD(res, res_i);
  65                 if (empty)
  66                         all_empty = isl_set_union_disjoint(all_empty, *empty);
  67         }
  68
  69         if (empty)
  70                 *empty = all_empty;
  71         isl_set_free(dom);
  72         isl_basic_map_free(bmap);
  73         return res;
  74 error:
  75         if (empty)
  76                 *empty = NULL;
  77         isl_set_free(dom);
  78         isl_basic_map_free(bmap);
  79         return NULL;
  80 }
  81
  82 static __isl_give TYPE *SF(isl_map_partial_lexopt_aligned,SUFFIX)(
  83         __isl_take isl_map *map, __isl_take isl_set *dom,
  84         __isl_give isl_set **empty, int max);
  85
  86 /* Given a map "map", compute the lexicographically minimal
  87  * (or maximal) image element for each domain element in dom.
  88  * Set *empty to those elements in dom that do not have an image element.
  89  *
  90  * Align parameters if needed and then call isl_map_partial_lexopt_aligned.
  91  */
  92 static __isl_give TYPE *SF(isl_map_partial_lexopt,SUFFIX)(
  93         __isl_take isl_map *map, __isl_take isl_set *dom,
  94         __isl_give isl_set **empty, int max)
  95 {
  96         if (!map || !dom)
  97                 goto error;
  98         if (isl_space_match(map->dim, isl_dim_param, dom->dim, isl_dim_param))
  99                 return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom,
 100                                                                 empty, max);
 101         if (!isl_space_has_named_params(map->dim) ||
 102             !isl_space_has_named_params(dom->dim))
 103                 isl_die(map->ctx, isl_error_invalid,
 104                         "unaligned unnamed parameters", goto error);
 105         map = isl_map_align_params(map, isl_map_get_space(dom));
 106         dom = isl_map_align_params(dom, isl_map_get_space(map));
 107         return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, empty, max);
 108 error:
 109         if (empty)
 110                 *empty = NULL;
 111         isl_set_free(dom);
 112         isl_map_free(map);
 113         return NULL;
 114 }
 115
 116 __isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map, int max)
 117 {
 118         isl_set *dom = NULL;
 119         isl_space *dom_space;
 120
 121         if (!map)
 122                 goto error;
 123         dom_space = isl_space_domain(isl_space_copy(map->dim));
 124         dom = isl_set_universe(dom_space);
 125         return SF(isl_map_partial_lexopt,SUFFIX)(map, dom, NULL, max);
 126 error:
 127         isl_map_free(map);
 128         return NULL;
 129 }
 130
 131 __isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map)
 132 {
 133         return SF(isl_map_lexopt,SUFFIX)(map, 0);
 134 }
 135
 136 __isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map)
 137 {
 138         return SF(isl_map_lexopt,SUFFIX)(map, 1);
 139 }
 140
 141 __isl_give TYPE *SF(isl_set_lexmin,SUFFIX)(__isl_take isl_set *set)
 142 {
 143         return SF(isl_map_lexmin,SUFFIX)(set);
 144 }
 145
 146 __isl_give TYPE *SF(isl_set_lexmax,SUFFIX)(__isl_take isl_set *set)
 147 {
 148         return SF(isl_map_lexmax,SUFFIX)(set);
 149 }