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 */
SF(isl_basic_map_partial_lexopt,SUFFIX)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
SF(isl_basic_map_partial_lexmax,SUFFIX)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
SF(isl_basic_map_partial_lexmin,SUFFIX)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
SF(isl_basic_set_partial_lexmin,SUFFIX)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
SF(isl_basic_set_partial_lexmax,SUFFIX)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 */
SF(basic_map_partial_lexopt,SUFFIX)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 */
SF(isl_basic_map_lexopt,SUFFIX)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
SF(isl_basic_map_lexmin,SUFFIX)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 */
SF(isl_map_partial_lexopt,SUFFIX)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 */
SF(isl_map_lexopt,SUFFIX)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
SF(isl_map_lexmin,SUFFIX)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
SF(isl_map_lexmax,SUFFIX)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
SF(isl_set_lexmin,SUFFIX)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
SF(isl_set_lexmax,SUFFIX)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