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