/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_ilp.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 2008-2009 Katholieke Universiteit Leuven |
3 | | * |
4 | | * Use of this software is governed by the MIT license |
5 | | * |
6 | | * Written by Sven Verdoolaege, K.U.Leuven, Departement |
7 | | * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium |
8 | | */ |
9 | | |
10 | | #include <isl_ctx_private.h> |
11 | | #include <isl_map_private.h> |
12 | | #include <isl/ilp.h> |
13 | | #include <isl/union_set.h> |
14 | | #include "isl_sample.h" |
15 | | #include <isl_seq.h> |
16 | | #include "isl_equalities.h" |
17 | | #include <isl_aff_private.h> |
18 | | #include <isl_local_space_private.h> |
19 | | #include <isl_mat_private.h> |
20 | | #include <isl_val_private.h> |
21 | | #include <isl_vec_private.h> |
22 | | #include <isl_lp_private.h> |
23 | | #include <isl_ilp_private.h> |
24 | | |
25 | | /* Given a basic set "bset", construct a basic set U such that for |
26 | | * each element x in U, the whole unit box positioned at x is inside |
27 | | * the given basic set. |
28 | | * Note that U may not contain all points that satisfy this property. |
29 | | * |
30 | | * We simply add the sum of all negative coefficients to the constant |
31 | | * term. This ensures that if x satisfies the resulting constraints, |
32 | | * then x plus any sum of unit vectors satisfies the original constraints. |
33 | | */ |
34 | | static __isl_give isl_basic_set *unit_box_base_points( |
35 | | __isl_take isl_basic_set *bset) |
36 | 347 | { |
37 | 347 | int i, j, k; |
38 | 347 | struct isl_basic_set *unit_box = NULL; |
39 | 347 | unsigned total; |
40 | 347 | |
41 | 347 | if (!bset) |
42 | 0 | goto error; |
43 | 347 | |
44 | 347 | if (bset->n_eq != 0) { |
45 | 0 | isl_space *space = isl_basic_set_get_space(bset); |
46 | 0 | isl_basic_set_free(bset); |
47 | 0 | return isl_basic_set_empty(space); |
48 | 0 | } |
49 | 347 | |
50 | 347 | total = isl_basic_set_total_dim(bset); |
51 | 347 | unit_box = isl_basic_set_alloc_space(isl_basic_set_get_space(bset), |
52 | 347 | 0, 0, bset->n_ineq); |
53 | 347 | |
54 | 2.85k | for (i = 0; i < bset->n_ineq; ++i2.50k ) { |
55 | 2.50k | k = isl_basic_set_alloc_inequality(unit_box); |
56 | 2.50k | if (k < 0) |
57 | 0 | goto error; |
58 | 2.50k | isl_seq_cpy(unit_box->ineq[k], bset->ineq[i], 1 + total); |
59 | 28.7k | for (j = 0; j < total; ++j26.2k ) { |
60 | 26.2k | if (isl_int_is_nonneg(unit_box->ineq[k][1 + j])) |
61 | 26.2k | continue24.3k ; |
62 | 1.91k | isl_int_add(unit_box->ineq[k][0], |
63 | 1.91k | unit_box->ineq[k][0], unit_box->ineq[k][1 + j]); |
64 | 1.91k | } |
65 | 2.50k | } |
66 | 347 | |
67 | 347 | isl_basic_set_free(bset); |
68 | 347 | return unit_box; |
69 | 0 | error: |
70 | 0 | isl_basic_set_free(bset); |
71 | 0 | isl_basic_set_free(unit_box); |
72 | 0 | return NULL; |
73 | 347 | } |
74 | | |
75 | | /* Find an integer point in "bset", preferably one that is |
76 | | * close to minimizing "f". |
77 | | * |
78 | | * We first check if we can easily put unit boxes inside bset. |
79 | | * If so, we take the best base point of any of the unit boxes we can find |
80 | | * and round it up to the nearest integer. |
81 | | * If not, we simply pick any integer point in "bset". |
82 | | */ |
83 | | static __isl_give isl_vec *initial_solution(__isl_keep isl_basic_set *bset, |
84 | | isl_int *f) |
85 | 347 | { |
86 | 347 | enum isl_lp_result res; |
87 | 347 | struct isl_basic_set *unit_box; |
88 | 347 | struct isl_vec *sol; |
89 | 347 | |
90 | 347 | unit_box = unit_box_base_points(isl_basic_set_copy(bset)); |
91 | 347 | |
92 | 347 | res = isl_basic_set_solve_lp(unit_box, 0, f, bset->ctx->one, |
93 | 347 | NULL, NULL, &sol); |
94 | 347 | if (res == isl_lp_ok) { |
95 | 0 | isl_basic_set_free(unit_box); |
96 | 0 | return isl_vec_ceil(sol); |
97 | 0 | } |
98 | 347 | |
99 | 347 | isl_basic_set_free(unit_box); |
100 | 347 | |
101 | 347 | return isl_basic_set_sample_vec(isl_basic_set_copy(bset)); |
102 | 347 | } |
103 | | |
104 | | /* Restrict "bset" to those points with values for f in the interval [l, u]. |
105 | | */ |
106 | | static __isl_give isl_basic_set *add_bounds(__isl_take isl_basic_set *bset, |
107 | | isl_int *f, isl_int l, isl_int u) |
108 | 30 | { |
109 | 30 | int k; |
110 | 30 | unsigned total; |
111 | 30 | |
112 | 30 | total = isl_basic_set_total_dim(bset); |
113 | 30 | bset = isl_basic_set_extend_constraints(bset, 0, 2); |
114 | 30 | |
115 | 30 | k = isl_basic_set_alloc_inequality(bset); |
116 | 30 | if (k < 0) |
117 | 0 | goto error; |
118 | 30 | isl_seq_cpy(bset->ineq[k], f, 1 + total); |
119 | 30 | isl_int_sub(bset->ineq[k][0], bset->ineq[k][0], l); |
120 | 30 | |
121 | 30 | k = isl_basic_set_alloc_inequality(bset); |
122 | 30 | if (k < 0) |
123 | 0 | goto error; |
124 | 30 | isl_seq_neg(bset->ineq[k], f, 1 + total); |
125 | 30 | isl_int_add(bset->ineq[k][0], bset->ineq[k][0], u); |
126 | 30 | |
127 | 30 | return bset; |
128 | 0 | error: |
129 | 0 | isl_basic_set_free(bset); |
130 | 0 | return NULL; |
131 | 30 | } |
132 | | |
133 | | /* Find an integer point in "bset" that minimizes f (in any) such that |
134 | | * the value of f lies inside the interval [l, u]. |
135 | | * Return this integer point if it can be found. |
136 | | * Otherwise, return sol. |
137 | | * |
138 | | * We perform a number of steps until l > u. |
139 | | * In each step, we look for an integer point with value in either |
140 | | * the whole interval [l, u] or half of the interval [l, l+floor(u-l-1/2)]. |
141 | | * The choice depends on whether we have found an integer point in the |
142 | | * previous step. If so, we look for the next point in half of the remaining |
143 | | * interval. |
144 | | * If we find a point, the current solution is updated and u is set |
145 | | * to its value minus 1. |
146 | | * If no point can be found, we update l to the upper bound of the interval |
147 | | * we checked (u or l+floor(u-l-1/2)) plus 1. |
148 | | */ |
149 | | static __isl_give isl_vec *solve_ilp_search(__isl_keep isl_basic_set *bset, |
150 | | isl_int *f, isl_int *opt, __isl_take isl_vec *sol, isl_int l, isl_int u) |
151 | 140 | { |
152 | 140 | isl_int tmp; |
153 | 140 | int divide = 1; |
154 | 140 | |
155 | 140 | isl_int_init(tmp); |
156 | 140 | |
157 | 170 | while (isl_int_le(l, u)) { |
158 | 30 | struct isl_basic_set *slice; |
159 | 30 | struct isl_vec *sample; |
160 | 30 | |
161 | 30 | if (!divide) |
162 | 30 | isl_int_set0 (tmp, u); |
163 | 30 | else { |
164 | 30 | isl_int_sub(tmp, u, l); |
165 | 30 | isl_int_fdiv_q_ui(tmp, tmp, 2); |
166 | 30 | isl_int_add(tmp, tmp, l); |
167 | 30 | } |
168 | 30 | slice = add_bounds(isl_basic_set_copy(bset), f, l, tmp); |
169 | 30 | sample = isl_basic_set_sample_vec(slice); |
170 | 30 | if (!sample) { |
171 | 0 | isl_vec_free(sol); |
172 | 0 | sol = NULL; |
173 | 0 | break; |
174 | 0 | } |
175 | 30 | if (sample->size > 0) { |
176 | 30 | isl_vec_free(sol); |
177 | 30 | sol = sample; |
178 | 30 | isl_seq_inner_product(f, sol->el, sol->size, opt); |
179 | 30 | isl_int_sub_ui(u, *opt, 1); |
180 | 30 | divide = 1; |
181 | 30 | } else { |
182 | 0 | isl_vec_free(sample); |
183 | 0 | if (!divide) |
184 | 0 | break; |
185 | 0 | isl_int_add_ui(l, tmp, 1); |
186 | 0 | divide = 0; |
187 | 0 | } |
188 | 30 | } |
189 | 140 | |
190 | 140 | isl_int_clear(tmp); |
191 | 140 | |
192 | 140 | return sol; |
193 | 140 | } |
194 | | |
195 | | /* Find an integer point in "bset" that minimizes f (if any). |
196 | | * If sol_p is not NULL then the integer point is returned in *sol_p. |
197 | | * The optimal value of f is returned in *opt. |
198 | | * |
199 | | * The algorithm maintains a currently best solution and an interval [l, u] |
200 | | * of values of f for which integer solutions could potentially still be found. |
201 | | * The initial value of the best solution so far is any solution. |
202 | | * The initial value of l is minimal value of f over the rationals |
203 | | * (rounded up to the nearest integer). |
204 | | * The initial value of u is the value of f at the initial solution minus 1. |
205 | | * |
206 | | * We then call solve_ilp_search to perform a binary search on the interval. |
207 | | */ |
208 | | static enum isl_lp_result solve_ilp(__isl_keep isl_basic_set *bset, |
209 | | isl_int *f, isl_int *opt, __isl_give isl_vec **sol_p) |
210 | 16.5k | { |
211 | 16.5k | enum isl_lp_result res; |
212 | 16.5k | isl_int l, u; |
213 | 16.5k | struct isl_vec *sol; |
214 | 16.5k | |
215 | 16.5k | res = isl_basic_set_solve_lp(bset, 0, f, bset->ctx->one, |
216 | 16.5k | opt, NULL, &sol); |
217 | 16.5k | if (res == isl_lp_ok && isl_int_is_one16.3k (sol->el[0])) { |
218 | 16.2k | if (sol_p) |
219 | 0 | *sol_p = sol; |
220 | 16.2k | else |
221 | 16.2k | isl_vec_free(sol); |
222 | 16.2k | return isl_lp_ok; |
223 | 16.2k | } |
224 | 348 | isl_vec_free(sol); |
225 | 348 | if (res == isl_lp_error || res == isl_lp_empty) |
226 | 1 | return res; |
227 | 347 | |
228 | 347 | sol = initial_solution(bset, f); |
229 | 347 | if (!sol) |
230 | 0 | return isl_lp_error; |
231 | 347 | if (sol->size == 0) { |
232 | 0 | isl_vec_free(sol); |
233 | 0 | return isl_lp_empty; |
234 | 0 | } |
235 | 347 | if (res == isl_lp_unbounded) { |
236 | 207 | isl_vec_free(sol); |
237 | 207 | return isl_lp_unbounded; |
238 | 207 | } |
239 | 140 | |
240 | 140 | isl_int_init(l); |
241 | 140 | isl_int_init(u); |
242 | 140 | |
243 | 140 | isl_int_set(l, *opt); |
244 | 140 | |
245 | 140 | isl_seq_inner_product(f, sol->el, sol->size, opt); |
246 | 140 | isl_int_sub_ui(u, *opt, 1); |
247 | 140 | |
248 | 140 | sol = solve_ilp_search(bset, f, opt, sol, l, u); |
249 | 140 | if (!sol) |
250 | 0 | res = isl_lp_error; |
251 | 140 | |
252 | 140 | isl_int_clear(l); |
253 | 140 | isl_int_clear(u); |
254 | 140 | |
255 | 140 | if (sol_p) |
256 | 0 | *sol_p = sol; |
257 | 140 | else |
258 | 140 | isl_vec_free(sol); |
259 | 140 | |
260 | 140 | return res; |
261 | 140 | } |
262 | | |
263 | | static enum isl_lp_result solve_ilp_with_eq(__isl_keep isl_basic_set *bset, |
264 | | int max, isl_int *f, isl_int *opt, __isl_give isl_vec **sol_p) |
265 | 16.0k | { |
266 | 16.0k | unsigned dim; |
267 | 16.0k | enum isl_lp_result res; |
268 | 16.0k | struct isl_mat *T = NULL; |
269 | 16.0k | struct isl_vec *v; |
270 | 16.0k | |
271 | 16.0k | bset = isl_basic_set_copy(bset); |
272 | 16.0k | dim = isl_basic_set_total_dim(bset); |
273 | 16.0k | v = isl_vec_alloc(bset->ctx, 1 + dim); |
274 | 16.0k | if (!v) |
275 | 0 | goto error; |
276 | 16.0k | isl_seq_cpy(v->el, f, 1 + dim); |
277 | 16.0k | bset = isl_basic_set_remove_equalities(bset, &T, NULL); |
278 | 16.0k | v = isl_vec_mat_product(v, isl_mat_copy(T)); |
279 | 16.0k | if (!v) |
280 | 0 | goto error; |
281 | 16.0k | res = isl_basic_set_solve_ilp(bset, max, v->el, opt, sol_p); |
282 | 16.0k | isl_vec_free(v); |
283 | 16.0k | if (res == isl_lp_ok && sol_p16.0k ) { |
284 | 0 | *sol_p = isl_mat_vec_product(T, *sol_p); |
285 | 0 | if (!*sol_p) |
286 | 0 | res = isl_lp_error; |
287 | 0 | } else |
288 | 16.0k | isl_mat_free(T); |
289 | 16.0k | isl_basic_set_free(bset); |
290 | 16.0k | return res; |
291 | 0 | error: |
292 | 0 | isl_mat_free(T); |
293 | 0 | isl_basic_set_free(bset); |
294 | 0 | return isl_lp_error; |
295 | 16.0k | } |
296 | | |
297 | | /* Find an integer point in "bset" that minimizes (or maximizes if max is set) |
298 | | * f (if any). |
299 | | * If sol_p is not NULL then the integer point is returned in *sol_p. |
300 | | * The optimal value of f is returned in *opt. |
301 | | * |
302 | | * If there is any equality among the points in "bset", then we first |
303 | | * project it out. Otherwise, we continue with solve_ilp above. |
304 | | */ |
305 | | enum isl_lp_result isl_basic_set_solve_ilp(__isl_keep isl_basic_set *bset, |
306 | | int max, isl_int *f, isl_int *opt, __isl_give isl_vec **sol_p) |
307 | 32.6k | { |
308 | 32.6k | unsigned dim; |
309 | 32.6k | enum isl_lp_result res; |
310 | 32.6k | |
311 | 32.6k | if (!bset) |
312 | 0 | return isl_lp_error; |
313 | 32.6k | if (sol_p) |
314 | 0 | *sol_p = NULL; |
315 | 32.6k | |
316 | 32.6k | isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0, |
317 | 32.6k | return isl_lp_error); |
318 | 32.6k | |
319 | 32.6k | if (isl_basic_set_plain_is_empty(bset)) |
320 | 1 | return isl_lp_empty; |
321 | 32.6k | |
322 | 32.6k | if (bset->n_eq) |
323 | 16.0k | return solve_ilp_with_eq(bset, max, f, opt, sol_p); |
324 | 16.5k | |
325 | 16.5k | dim = isl_basic_set_total_dim(bset); |
326 | 16.5k | |
327 | 16.5k | if (max) |
328 | 16.5k | isl_seq_neg(f, f, 1 + dim); |
329 | 16.5k | |
330 | 16.5k | res = solve_ilp(bset, f, opt, sol_p); |
331 | 16.5k | |
332 | 16.5k | if (max) { |
333 | 16.5k | isl_seq_neg(f, f, 1 + dim); |
334 | 16.5k | isl_int_neg(*opt, *opt); |
335 | 16.5k | } |
336 | 16.5k | |
337 | 16.5k | return res; |
338 | 16.5k | } |
339 | | |
340 | | static enum isl_lp_result basic_set_opt(__isl_keep isl_basic_set *bset, int max, |
341 | | __isl_keep isl_aff *obj, isl_int *opt) |
342 | 16.5k | { |
343 | 16.5k | enum isl_lp_result res; |
344 | 16.5k | |
345 | 16.5k | if (!obj) |
346 | 0 | return isl_lp_error; |
347 | 16.5k | bset = isl_basic_set_copy(bset); |
348 | 16.5k | bset = isl_basic_set_underlying_set(bset); |
349 | 16.5k | res = isl_basic_set_solve_ilp(bset, max, obj->v->el + 1, opt, NULL); |
350 | 16.5k | isl_basic_set_free(bset); |
351 | 16.5k | return res; |
352 | 16.5k | } |
353 | | |
354 | | static __isl_give isl_mat *extract_divs(__isl_keep isl_basic_set *bset) |
355 | 174 | { |
356 | 174 | int i; |
357 | 174 | isl_ctx *ctx = isl_basic_set_get_ctx(bset); |
358 | 174 | isl_mat *div; |
359 | 174 | |
360 | 174 | div = isl_mat_alloc(ctx, bset->n_div, |
361 | 174 | 1 + 1 + isl_basic_set_total_dim(bset)); |
362 | 174 | if (!div) |
363 | 0 | return NULL; |
364 | 174 | |
365 | 348 | for (i = 0; 174 i < bset->n_div; ++i174 ) |
366 | 174 | isl_seq_cpy(div->row[i], bset->div[i], div->n_col); |
367 | 174 | |
368 | 174 | return div; |
369 | 174 | } |
370 | | |
371 | | enum isl_lp_result isl_basic_set_opt(__isl_keep isl_basic_set *bset, int max, |
372 | | __isl_keep isl_aff *obj, isl_int *opt) |
373 | 16.5k | { |
374 | 16.5k | int *exp1 = NULL; |
375 | 16.5k | int *exp2 = NULL; |
376 | 16.5k | isl_ctx *ctx; |
377 | 16.5k | isl_mat *bset_div = NULL; |
378 | 16.5k | isl_mat *div = NULL; |
379 | 16.5k | enum isl_lp_result res; |
380 | 16.5k | int bset_n_div, obj_n_div; |
381 | 16.5k | |
382 | 16.5k | if (!bset || !obj) |
383 | 0 | return isl_lp_error; |
384 | 16.5k | |
385 | 16.5k | ctx = isl_aff_get_ctx(obj); |
386 | 16.5k | if (!isl_space_is_equal(bset->dim, obj->ls->dim)) |
387 | 16.5k | isl_die0 (ctx, isl_error_invalid, |
388 | 16.5k | "spaces don't match", return isl_lp_error); |
389 | 16.5k | if (!isl_int_is_one(obj->v->el[0])) |
390 | 16.5k | isl_die0 (ctx, isl_error_unsupported, |
391 | 16.5k | "expecting integer affine expression", |
392 | 16.5k | return isl_lp_error); |
393 | 16.5k | |
394 | 16.5k | bset_n_div = isl_basic_set_dim(bset, isl_dim_div); |
395 | 16.5k | obj_n_div = isl_aff_dim(obj, isl_dim_div); |
396 | 16.5k | if (bset_n_div == 0 && obj_n_div == 016.3k ) |
397 | 16.3k | return basic_set_opt(bset, max, obj, opt); |
398 | 174 | |
399 | 174 | bset = isl_basic_set_copy(bset); |
400 | 174 | obj = isl_aff_copy(obj); |
401 | 174 | |
402 | 174 | bset_div = extract_divs(bset); |
403 | 174 | exp1 = isl_alloc_array(ctx, int, bset_n_div); |
404 | 174 | exp2 = isl_alloc_array(ctx, int, obj_n_div); |
405 | 174 | if (!bset_div || (bset_n_div && !exp1) || (obj_n_div && !exp2)) |
406 | 0 | goto error; |
407 | 174 | |
408 | 174 | div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2); |
409 | 174 | |
410 | 174 | bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1); |
411 | 174 | obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2); |
412 | 174 | |
413 | 174 | res = basic_set_opt(bset, max, obj, opt); |
414 | 174 | |
415 | 174 | isl_mat_free(bset_div); |
416 | 174 | isl_mat_free(div); |
417 | 174 | free(exp1); |
418 | 174 | free(exp2); |
419 | 174 | isl_basic_set_free(bset); |
420 | 174 | isl_aff_free(obj); |
421 | 174 | |
422 | 174 | return res; |
423 | 0 | error: |
424 | 0 | isl_mat_free(div); |
425 | 0 | isl_mat_free(bset_div); |
426 | 0 | free(exp1); |
427 | 0 | free(exp2); |
428 | 0 | isl_basic_set_free(bset); |
429 | 0 | isl_aff_free(obj); |
430 | 0 | return isl_lp_error; |
431 | 174 | } |
432 | | |
433 | | /* Compute the minimum (maximum if max is set) of the integer affine |
434 | | * expression obj over the points in set and put the result in *opt. |
435 | | * |
436 | | * The parameters are assumed to have been aligned. |
437 | | */ |
438 | | static enum isl_lp_result isl_set_opt_aligned(__isl_keep isl_set *set, int max, |
439 | | __isl_keep isl_aff *obj, isl_int *opt) |
440 | 2.74k | { |
441 | 2.74k | int i; |
442 | 2.74k | enum isl_lp_result res; |
443 | 2.74k | int empty = 1; |
444 | 2.74k | isl_int opt_i; |
445 | 2.74k | |
446 | 2.74k | if (!set || !obj) |
447 | 0 | return isl_lp_error; |
448 | 2.74k | if (set->n == 0) |
449 | 0 | return isl_lp_empty; |
450 | 2.74k | |
451 | 2.74k | res = isl_basic_set_opt(set->p[0], max, obj, opt); |
452 | 2.74k | if (res == isl_lp_error || res == isl_lp_unbounded) |
453 | 207 | return res; |
454 | 2.54k | if (set->n == 1) |
455 | 330 | return res; |
456 | 2.21k | if (res == isl_lp_ok) |
457 | 2.21k | empty = 0; |
458 | 2.21k | |
459 | 2.21k | isl_int_init(opt_i); |
460 | 16.0k | for (i = 1; i < set->n; ++i13.8k ) { |
461 | 13.8k | res = isl_basic_set_opt(set->p[i], max, obj, &opt_i); |
462 | 13.8k | if (res == isl_lp_error || res == isl_lp_unbounded) { |
463 | 0 | isl_int_clear(opt_i); |
464 | 0 | return res; |
465 | 0 | } |
466 | 13.8k | if (res == isl_lp_empty) |
467 | 1 | continue; |
468 | 13.8k | empty = 0; |
469 | 13.8k | if (max ? isl_int_gt13.8k (opt_i, *opt) : isl_int_lt1 (opt_i, *opt)) |
470 | 13.8k | isl_int_set1 (*opt, opt_i); |
471 | 13.8k | } |
472 | 2.21k | isl_int_clear(opt_i); |
473 | 2.21k | |
474 | 2.21k | return empty ? isl_lp_empty0 : isl_lp_ok; |
475 | 2.21k | } |
476 | | |
477 | | /* Compute the minimum (maximum if max is set) of the integer affine |
478 | | * expression obj over the points in set and put the result in *opt. |
479 | | */ |
480 | | enum isl_lp_result isl_set_opt(__isl_keep isl_set *set, int max, |
481 | | __isl_keep isl_aff *obj, isl_int *opt) |
482 | 2.74k | { |
483 | 2.74k | enum isl_lp_result res; |
484 | 2.74k | isl_bool aligned; |
485 | 2.74k | |
486 | 2.74k | if (!set || !obj) |
487 | 0 | return isl_lp_error; |
488 | 2.74k | |
489 | 2.74k | aligned = isl_set_space_has_equal_params(set, obj->ls->dim); |
490 | 2.74k | if (aligned < 0) |
491 | 0 | return isl_lp_error; |
492 | 2.74k | if (aligned) |
493 | 2.74k | return isl_set_opt_aligned(set, max, obj, opt); |
494 | 0 | |
495 | 0 | set = isl_set_copy(set); |
496 | 0 | obj = isl_aff_copy(obj); |
497 | 0 | set = isl_set_align_params(set, isl_aff_get_domain_space(obj)); |
498 | 0 | obj = isl_aff_align_params(obj, isl_set_get_space(set)); |
499 | 0 |
|
500 | 0 | res = isl_set_opt_aligned(set, max, obj, opt); |
501 | 0 |
|
502 | 0 | isl_set_free(set); |
503 | 0 | isl_aff_free(obj); |
504 | 0 |
|
505 | 0 | return res; |
506 | 0 | } |
507 | | |
508 | | /* Convert the result of a function that returns an isl_lp_result |
509 | | * to an isl_val. The numerator of "v" is set to the optimal value |
510 | | * if lp_res is isl_lp_ok. "max" is set if a maximum was computed. |
511 | | * |
512 | | * Return "v" with denominator set to 1 if lp_res is isl_lp_ok. |
513 | | * Return NULL on error. |
514 | | * Return a NaN if lp_res is isl_lp_empty. |
515 | | * Return infinity or negative infinity if lp_res is isl_lp_unbounded, |
516 | | * depending on "max". |
517 | | */ |
518 | | static __isl_give isl_val *convert_lp_result(enum isl_lp_result lp_res, |
519 | | __isl_take isl_val *v, int max) |
520 | 2.74k | { |
521 | 2.74k | isl_ctx *ctx; |
522 | 2.74k | |
523 | 2.74k | if (lp_res == isl_lp_ok) { |
524 | 2.54k | isl_int_set_si(v->d, 1); |
525 | 2.54k | return isl_val_normalize(v); |
526 | 2.54k | } |
527 | 208 | ctx = isl_val_get_ctx(v); |
528 | 208 | isl_val_free(v); |
529 | 208 | if (lp_res == isl_lp_error) |
530 | 0 | return NULL; |
531 | 208 | if (lp_res == isl_lp_empty) |
532 | 1 | return isl_val_nan(ctx); |
533 | 207 | if (max) |
534 | 207 | return isl_val_infty(ctx); |
535 | 0 | else |
536 | 0 | return isl_val_neginfty(ctx); |
537 | 207 | } |
538 | | |
539 | | /* Return the minimum (maximum if max is set) of the integer affine |
540 | | * expression "obj" over the points in "bset". |
541 | | * |
542 | | * Return infinity or negative infinity if the optimal value is unbounded and |
543 | | * NaN if "bset" is empty. |
544 | | * |
545 | | * Call isl_basic_set_opt and translate the results. |
546 | | */ |
547 | | __isl_give isl_val *isl_basic_set_opt_val(__isl_keep isl_basic_set *bset, |
548 | | int max, __isl_keep isl_aff *obj) |
549 | 1 | { |
550 | 1 | isl_ctx *ctx; |
551 | 1 | isl_val *res; |
552 | 1 | enum isl_lp_result lp_res; |
553 | 1 | |
554 | 1 | if (!bset || !obj) |
555 | 0 | return NULL; |
556 | 1 | |
557 | 1 | ctx = isl_aff_get_ctx(obj); |
558 | 1 | res = isl_val_alloc(ctx); |
559 | 1 | if (!res) |
560 | 0 | return NULL; |
561 | 1 | lp_res = isl_basic_set_opt(bset, max, obj, &res->n); |
562 | 1 | return convert_lp_result(lp_res, res, max); |
563 | 1 | } |
564 | | |
565 | | /* Return the maximum of the integer affine |
566 | | * expression "obj" over the points in "bset". |
567 | | * |
568 | | * Return infinity or negative infinity if the optimal value is unbounded and |
569 | | * NaN if "bset" is empty. |
570 | | */ |
571 | | __isl_give isl_val *isl_basic_set_max_val(__isl_keep isl_basic_set *bset, |
572 | | __isl_keep isl_aff *obj) |
573 | 1 | { |
574 | 1 | return isl_basic_set_opt_val(bset, 1, obj); |
575 | 1 | } |
576 | | |
577 | | /* Return the minimum (maximum if max is set) of the integer affine |
578 | | * expression "obj" over the points in "set". |
579 | | * |
580 | | * Return infinity or negative infinity if the optimal value is unbounded and |
581 | | * NaN if "set" is empty. |
582 | | * |
583 | | * Call isl_set_opt and translate the results. |
584 | | */ |
585 | | __isl_give isl_val *isl_set_opt_val(__isl_keep isl_set *set, int max, |
586 | | __isl_keep isl_aff *obj) |
587 | 2.74k | { |
588 | 2.74k | isl_ctx *ctx; |
589 | 2.74k | isl_val *res; |
590 | 2.74k | enum isl_lp_result lp_res; |
591 | 2.74k | |
592 | 2.74k | if (!set || !obj) |
593 | 0 | return NULL; |
594 | 2.74k | |
595 | 2.74k | ctx = isl_aff_get_ctx(obj); |
596 | 2.74k | res = isl_val_alloc(ctx); |
597 | 2.74k | if (!res) |
598 | 0 | return NULL; |
599 | 2.74k | lp_res = isl_set_opt(set, max, obj, &res->n); |
600 | 2.74k | return convert_lp_result(lp_res, res, max); |
601 | 2.74k | } |
602 | | |
603 | | /* Return the minimum of the integer affine |
604 | | * expression "obj" over the points in "set". |
605 | | * |
606 | | * Return infinity or negative infinity if the optimal value is unbounded and |
607 | | * NaN if "set" is empty. |
608 | | */ |
609 | | __isl_give isl_val *isl_set_min_val(__isl_keep isl_set *set, |
610 | | __isl_keep isl_aff *obj) |
611 | 2 | { |
612 | 2 | return isl_set_opt_val(set, 0, obj); |
613 | 2 | } |
614 | | |
615 | | /* Return the maximum of the integer affine |
616 | | * expression "obj" over the points in "set". |
617 | | * |
618 | | * Return infinity or negative infinity if the optimal value is unbounded and |
619 | | * NaN if "set" is empty. |
620 | | */ |
621 | | __isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set, |
622 | | __isl_keep isl_aff *obj) |
623 | 2.74k | { |
624 | 2.74k | return isl_set_opt_val(set, 1, obj); |
625 | 2.74k | } |
626 | | |
627 | | /* Return the optimum (min or max depending on "max") of "v1" and "v2", |
628 | | * where either may be NaN, signifying an uninitialized value. |
629 | | * That is, if either is NaN, then return the other one. |
630 | | */ |
631 | | static __isl_give isl_val *val_opt(__isl_take isl_val *v1, |
632 | | __isl_take isl_val *v2, int max) |
633 | 0 | { |
634 | 0 | if (!v1 || !v2) |
635 | 0 | goto error; |
636 | 0 | if (isl_val_is_nan(v1)) { |
637 | 0 | isl_val_free(v1); |
638 | 0 | return v2; |
639 | 0 | } |
640 | 0 | if (isl_val_is_nan(v2)) { |
641 | 0 | isl_val_free(v2); |
642 | 0 | return v1; |
643 | 0 | } |
644 | 0 | if (max) |
645 | 0 | return isl_val_max(v1, v2); |
646 | 0 | else |
647 | 0 | return isl_val_min(v1, v2); |
648 | 0 | error: |
649 | 0 | isl_val_free(v1); |
650 | 0 | isl_val_free(v2); |
651 | 0 | return NULL; |
652 | 0 | } |
653 | | |
654 | | /* Internal data structure for isl_pw_aff_opt_val. |
655 | | * |
656 | | * "max" is set if the maximum should be computed. |
657 | | * "res" contains the current optimum and is initialized to NaN. |
658 | | */ |
659 | | struct isl_pw_aff_opt_data { |
660 | | int max; |
661 | | |
662 | | isl_val *res; |
663 | | }; |
664 | | |
665 | | /* Update the optimum in data->res with respect to the affine function |
666 | | * "aff" defined over "set". |
667 | | */ |
668 | | static isl_stat piece_opt(__isl_take isl_set *set, __isl_take isl_aff *aff, |
669 | | void *user) |
670 | 0 | { |
671 | 0 | struct isl_pw_aff_opt_data *data = user; |
672 | 0 | isl_val *opt; |
673 | 0 |
|
674 | 0 | opt = isl_set_opt_val(set, data->max, aff); |
675 | 0 | isl_set_free(set); |
676 | 0 | isl_aff_free(aff); |
677 | 0 |
|
678 | 0 | data->res = val_opt(data->res, opt, data->max); |
679 | 0 | if (!data->res) |
680 | 0 | return isl_stat_error; |
681 | 0 | |
682 | 0 | return isl_stat_ok; |
683 | 0 | } |
684 | | |
685 | | /* Return the minimum (maximum if "max" is set) of the integer piecewise affine |
686 | | * expression "pa" over its definition domain. |
687 | | * |
688 | | * Return infinity or negative infinity if the optimal value is unbounded and |
689 | | * NaN if the domain of "pa" is empty. |
690 | | * |
691 | | * Initialize the result to NaN and then update it for each of the pieces |
692 | | * in "pa". |
693 | | */ |
694 | | static __isl_give isl_val *isl_pw_aff_opt_val(__isl_take isl_pw_aff *pa, |
695 | | int max) |
696 | 0 | { |
697 | 0 | struct isl_pw_aff_opt_data data = { max }; |
698 | 0 |
|
699 | 0 | data.res = isl_val_nan(isl_pw_aff_get_ctx(pa)); |
700 | 0 | if (isl_pw_aff_foreach_piece(pa, &piece_opt, &data) < 0) |
701 | 0 | data.res = isl_val_free(data.res); |
702 | 0 |
|
703 | 0 | isl_pw_aff_free(pa); |
704 | 0 | return data.res; |
705 | 0 | } |
706 | | |
707 | | /* Internal data structure for isl_union_pw_aff_opt_val. |
708 | | * |
709 | | * "max" is set if the maximum should be computed. |
710 | | * "res" contains the current optimum and is initialized to NaN. |
711 | | */ |
712 | | struct isl_union_pw_aff_opt_data { |
713 | | int max; |
714 | | |
715 | | isl_val *res; |
716 | | }; |
717 | | |
718 | | /* Update the optimum in data->res with the optimum of "pa". |
719 | | */ |
720 | | static isl_stat pw_aff_opt(__isl_take isl_pw_aff *pa, void *user) |
721 | 0 | { |
722 | 0 | struct isl_union_pw_aff_opt_data *data = user; |
723 | 0 | isl_val *opt; |
724 | 0 |
|
725 | 0 | opt = isl_pw_aff_opt_val(pa, data->max); |
726 | 0 |
|
727 | 0 | data->res = val_opt(data->res, opt, data->max); |
728 | 0 | if (!data->res) |
729 | 0 | return isl_stat_error; |
730 | 0 | |
731 | 0 | return isl_stat_ok; |
732 | 0 | } |
733 | | |
734 | | /* Return the minimum (maximum if "max" is set) of the integer piecewise affine |
735 | | * expression "upa" over its definition domain. |
736 | | * |
737 | | * Return infinity or negative infinity if the optimal value is unbounded and |
738 | | * NaN if the domain of the expression is empty. |
739 | | * |
740 | | * Initialize the result to NaN and then update it |
741 | | * for each of the piecewise affine expressions in "upa". |
742 | | */ |
743 | | static __isl_give isl_val *isl_union_pw_aff_opt_val( |
744 | | __isl_take isl_union_pw_aff *upa, int max) |
745 | 0 | { |
746 | 0 | struct isl_union_pw_aff_opt_data data = { max }; |
747 | 0 |
|
748 | 0 | data.res = isl_val_nan(isl_union_pw_aff_get_ctx(upa)); |
749 | 0 | if (isl_union_pw_aff_foreach_pw_aff(upa, &pw_aff_opt, &data) < 0) |
750 | 0 | data.res = isl_val_free(data.res); |
751 | 0 | isl_union_pw_aff_free(upa); |
752 | 0 |
|
753 | 0 | return data.res; |
754 | 0 | } |
755 | | |
756 | | /* Return the minimum of the integer piecewise affine |
757 | | * expression "upa" over its definition domain. |
758 | | * |
759 | | * Return negative infinity if the optimal value is unbounded and |
760 | | * NaN if the domain of the expression is empty. |
761 | | */ |
762 | | __isl_give isl_val *isl_union_pw_aff_min_val(__isl_take isl_union_pw_aff *upa) |
763 | 0 | { |
764 | 0 | return isl_union_pw_aff_opt_val(upa, 0); |
765 | 0 | } |
766 | | |
767 | | /* Return the maximum of the integer piecewise affine |
768 | | * expression "upa" over its definition domain. |
769 | | * |
770 | | * Return infinity if the optimal value is unbounded and |
771 | | * NaN if the domain of the expression is empty. |
772 | | */ |
773 | | __isl_give isl_val *isl_union_pw_aff_max_val(__isl_take isl_union_pw_aff *upa) |
774 | 0 | { |
775 | 0 | return isl_union_pw_aff_opt_val(upa, 1); |
776 | 0 | } |
777 | | |
778 | | /* Return a list of minima (maxima if "max" is set) |
779 | | * for each of the expressions in "mupa" over their domains. |
780 | | * |
781 | | * An element in the list is infinity or negative infinity if the optimal |
782 | | * value of the corresponding expression is unbounded and |
783 | | * NaN if the domain of the expression is empty. |
784 | | * |
785 | | * Iterate over all the expressions in "mupa" and collect the results. |
786 | | */ |
787 | | static __isl_give isl_multi_val *isl_multi_union_pw_aff_opt_multi_val( |
788 | | __isl_take isl_multi_union_pw_aff *mupa, int max) |
789 | 0 | { |
790 | 0 | int i, n; |
791 | 0 | isl_multi_val *mv; |
792 | 0 |
|
793 | 0 | if (!mupa) |
794 | 0 | return NULL; |
795 | 0 | |
796 | 0 | n = isl_multi_union_pw_aff_dim(mupa, isl_dim_set); |
797 | 0 | mv = isl_multi_val_zero(isl_multi_union_pw_aff_get_space(mupa)); |
798 | 0 |
|
799 | 0 | for (i = 0; i < n; ++i) { |
800 | 0 | isl_val *v; |
801 | 0 | isl_union_pw_aff *upa; |
802 | 0 |
|
803 | 0 | upa = isl_multi_union_pw_aff_get_union_pw_aff(mupa, i); |
804 | 0 | v = isl_union_pw_aff_opt_val(upa, max); |
805 | 0 | mv = isl_multi_val_set_val(mv, i, v); |
806 | 0 | } |
807 | 0 |
|
808 | 0 | isl_multi_union_pw_aff_free(mupa); |
809 | 0 | return mv; |
810 | 0 | } |
811 | | |
812 | | /* Return a list of minima (maxima if "max" is set) over the points in "uset" |
813 | | * for each of the expressions in "obj". |
814 | | * |
815 | | * An element in the list is infinity or negative infinity if the optimal |
816 | | * value of the corresponding expression is unbounded and |
817 | | * NaN if the intersection of "uset" with the domain of the expression |
818 | | * is empty. |
819 | | */ |
820 | | static __isl_give isl_multi_val *isl_union_set_opt_multi_union_pw_aff( |
821 | | __isl_keep isl_union_set *uset, int max, |
822 | | __isl_keep isl_multi_union_pw_aff *obj) |
823 | 0 | { |
824 | 0 | uset = isl_union_set_copy(uset); |
825 | 0 | obj = isl_multi_union_pw_aff_copy(obj); |
826 | 0 | obj = isl_multi_union_pw_aff_intersect_domain(obj, uset); |
827 | 0 | return isl_multi_union_pw_aff_opt_multi_val(obj, max); |
828 | 0 | } |
829 | | |
830 | | /* Return a list of minima over the points in "uset" |
831 | | * for each of the expressions in "obj". |
832 | | * |
833 | | * An element in the list is infinity or negative infinity if the optimal |
834 | | * value of the corresponding expression is unbounded and |
835 | | * NaN if the intersection of "uset" with the domain of the expression |
836 | | * is empty. |
837 | | */ |
838 | | __isl_give isl_multi_val *isl_union_set_min_multi_union_pw_aff( |
839 | | __isl_keep isl_union_set *uset, __isl_keep isl_multi_union_pw_aff *obj) |
840 | 0 | { |
841 | 0 | return isl_union_set_opt_multi_union_pw_aff(uset, 0, obj); |
842 | 0 | } |
843 | | |
844 | | /* Return a list of minima |
845 | | * for each of the expressions in "mupa" over their domains. |
846 | | * |
847 | | * An element in the list is negative infinity if the optimal |
848 | | * value of the corresponding expression is unbounded and |
849 | | * NaN if the domain of the expression is empty. |
850 | | */ |
851 | | __isl_give isl_multi_val *isl_multi_union_pw_aff_min_multi_val( |
852 | | __isl_take isl_multi_union_pw_aff *mupa) |
853 | 0 | { |
854 | 0 | return isl_multi_union_pw_aff_opt_multi_val(mupa, 0); |
855 | 0 | } |
856 | | |
857 | | /* Return a list of maxima |
858 | | * for each of the expressions in "mupa" over their domains. |
859 | | * |
860 | | * An element in the list is infinity if the optimal |
861 | | * value of the corresponding expression is unbounded and |
862 | | * NaN if the domain of the expression is empty. |
863 | | */ |
864 | | __isl_give isl_multi_val *isl_multi_union_pw_aff_max_multi_val( |
865 | | __isl_take isl_multi_union_pw_aff *mupa) |
866 | 0 | { |
867 | 0 | return isl_multi_union_pw_aff_opt_multi_val(mupa, 1); |
868 | 0 | } |
869 | | |
870 | | /* Return the maximal value attained by the given set dimension, |
871 | | * independently of the parameter values and of any other dimensions. |
872 | | * |
873 | | * Return infinity if the optimal value is unbounded and |
874 | | * NaN if "bset" is empty. |
875 | | */ |
876 | | __isl_give isl_val *isl_basic_set_dim_max_val(__isl_take isl_basic_set *bset, |
877 | | int pos) |
878 | 0 | { |
879 | 0 | isl_local_space *ls; |
880 | 0 | isl_aff *obj; |
881 | 0 | isl_val *v; |
882 | 0 |
|
883 | 0 | if (!bset) |
884 | 0 | return NULL; |
885 | 0 | if (pos < 0 || pos >= isl_basic_set_dim(bset, isl_dim_set)) |
886 | 0 | isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid, |
887 | 0 | "position out of bounds", goto error); |
888 | 0 | ls = isl_local_space_from_space(isl_basic_set_get_space(bset)); |
889 | 0 | obj = isl_aff_var_on_domain(ls, isl_dim_set, pos); |
890 | 0 | v = isl_basic_set_max_val(bset, obj); |
891 | 0 | isl_aff_free(obj); |
892 | 0 | isl_basic_set_free(bset); |
893 | 0 |
|
894 | 0 | return v; |
895 | 0 | error: |
896 | 0 | isl_basic_set_free(bset); |
897 | 0 | return NULL; |
898 | 0 | } |