blob 0c41702ffac31af11cb4af5d86965a315f6b8a5e
1 /*
2 * Copyright 2010 INRIA Saclay
3 * Copyright 2012 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
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
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.
17 #define xSF(TYPE,SUFFIX) TYPE ## SUFFIX
18 #define SF(TYPE,SUFFIX) xSF(TYPE,SUFFIX)
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.
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.
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)
33 int i;
34 TYPE *res;
36 dom = isl_set_make_disjoint(dom);
37 if (!dom)
38 goto error;
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);
50 res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap),
51 isl_basic_set_copy(dom->p[0]), empty, max);
53 for (i = 1; i < dom->n; ++i) {
54 TYPE *res_i;
55 isl_set *empty_i;
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);
62 *empty = isl_set_union_disjoint(*empty, empty_i);
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;
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);
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.
83 * Align parameters if needed and then call isl_map_partial_lexopt_aligned.
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)
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;
109 __isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map, int max)
111 isl_set *dom = NULL;
112 isl_space *dom_space;
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;
124 __isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map)
126 return SF(isl_map_lexopt,SUFFIX)(map, 0);
129 __isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map)
131 return SF(isl_map_lexopt,SUFFIX)(map, 1);