Line data Source code
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 0 : 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 0 : return SF(isl_tab_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty,
36 : flags);
37 : }
38 :
39 0 : __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 0 : unsigned flags = ISL_OPT_MAX;
44 0 : return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, flags);
45 : }
46 :
47 0 : __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 0 : unsigned flags = 0;
52 0 : return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, dom, empty, flags);
53 : }
54 :
55 0 : __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 0 : return SF(isl_basic_map_partial_lexmin,SUFFIX)(bset, dom, empty);
60 : }
61 :
62 0 : __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 0 : 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 0 : 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 0 : if (ISL_FL_ISSET(flags, ISL_OPT_FULL))
95 0 : return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, NULL,
96 : empty, flags);
97 :
98 0 : dom = isl_set_make_disjoint(dom);
99 0 : if (!dom)
100 0 : goto error;
101 :
102 0 : if (isl_set_plain_is_empty(dom)) {
103 0 : isl_space *space = isl_basic_map_get_space(bmap);
104 0 : if (empty)
105 0 : *empty = dom;
106 : else
107 0 : isl_set_free(dom);
108 0 : isl_basic_map_free(bmap);
109 0 : return EMPTY(space);
110 : }
111 :
112 0 : res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap),
113 0 : isl_basic_set_copy(dom->p[0]), empty, flags);
114 :
115 0 : if (empty)
116 0 : all_empty = *empty;
117 0 : for (i = 1; i < dom->n; ++i) {
118 : TYPE *res_i;
119 :
120 0 : res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)(
121 : isl_basic_map_copy(bmap),
122 0 : isl_basic_set_copy(dom->p[i]), empty, flags);
123 :
124 0 : res = ADD(res, res_i);
125 0 : if (empty)
126 0 : all_empty = isl_set_union_disjoint(all_empty, *empty);
127 : }
128 :
129 0 : if (empty)
130 0 : *empty = all_empty;
131 0 : isl_set_free(dom);
132 0 : isl_basic_map_free(bmap);
133 0 : return res;
134 : error:
135 0 : if (empty)
136 0 : *empty = NULL;
137 0 : isl_set_free(dom);
138 0 : isl_basic_map_free(bmap);
139 0 : 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 0 : __isl_give TYPE *SF(isl_basic_map_lexopt,SUFFIX)(
146 : __isl_take isl_basic_map *bmap, unsigned flags)
147 : {
148 0 : ISL_FL_SET(flags, ISL_OPT_FULL);
149 0 : return SF(isl_basic_map_partial_lexopt,SUFFIX)(bmap, NULL, NULL, flags);
150 : }
151 :
152 0 : __isl_give TYPE *SF(isl_basic_map_lexmin,SUFFIX)(__isl_take isl_basic_map *bmap)
153 : {
154 0 : 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 0 : 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 0 : aligned = isl_map_set_has_equal_params(map, dom);
179 0 : if (aligned < 0)
180 0 : goto error;
181 0 : if (aligned)
182 0 : return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom,
183 : empty, flags);
184 0 : if (!isl_space_has_named_params(map->dim) ||
185 0 : !isl_space_has_named_params(dom->dim))
186 0 : isl_die(map->ctx, isl_error_invalid,
187 : "unaligned unnamed parameters", goto error);
188 0 : map = isl_map_align_params(map, isl_map_get_space(dom));
189 0 : dom = isl_map_align_params(dom, isl_map_get_space(map));
190 0 : return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, empty,
191 : flags);
192 : error:
193 0 : if (empty)
194 0 : *empty = NULL;
195 0 : isl_set_free(dom);
196 0 : isl_map_free(map);
197 0 : 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 0 : __isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map,
204 : unsigned flags)
205 : {
206 0 : ISL_FL_SET(flags, ISL_OPT_FULL);
207 0 : return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, NULL, NULL,
208 : flags);
209 : }
210 :
211 0 : __isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map)
212 : {
213 0 : return SF(isl_map_lexopt,SUFFIX)(map, 0);
214 : }
215 :
216 0 : __isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map)
217 : {
218 0 : return SF(isl_map_lexopt,SUFFIX)(map, ISL_OPT_MAX);
219 : }
220 :
221 0 : __isl_give TYPE *SF(isl_set_lexmin,SUFFIX)(__isl_take isl_set *set)
222 : {
223 0 : return SF(isl_map_lexmin,SUFFIX)(set);
224 : }
225 :
226 0 : __isl_give TYPE *SF(isl_set_lexmax,SUFFIX)(__isl_take isl_set *set)
227 : {
228 0 : return SF(isl_map_lexmax,SUFFIX)(set);
229 : }
|
