isl_local_space_get_space: extract out isl_local_space_peek_space
[isl.git] / isl_ilp.c
blobd517290ede606dd6c94de7b5f0b64f2992126f91
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
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>
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.
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.
34 static __isl_give isl_basic_set *unit_box_base_points(
35 __isl_take isl_basic_set *bset)
37 int i, j, k;
38 struct isl_basic_set *unit_box = NULL;
39 unsigned total;
41 if (!bset)
42 goto error;
44 if (bset->n_eq != 0) {
45 isl_space *space = isl_basic_set_get_space(bset);
46 isl_basic_set_free(bset);
47 return isl_basic_set_empty(space);
50 total = isl_basic_set_total_dim(bset);
51 unit_box = isl_basic_set_alloc_space(isl_basic_set_get_space(bset),
52 0, 0, bset->n_ineq);
54 for (i = 0; i < bset->n_ineq; ++i) {
55 k = isl_basic_set_alloc_inequality(unit_box);
56 if (k < 0)
57 goto error;
58 isl_seq_cpy(unit_box->ineq[k], bset->ineq[i], 1 + total);
59 for (j = 0; j < total; ++j) {
60 if (isl_int_is_nonneg(unit_box->ineq[k][1 + j]))
61 continue;
62 isl_int_add(unit_box->ineq[k][0],
63 unit_box->ineq[k][0], unit_box->ineq[k][1 + j]);
67 isl_basic_set_free(bset);
68 return unit_box;
69 error:
70 isl_basic_set_free(bset);
71 isl_basic_set_free(unit_box);
72 return NULL;
75 /* Find an integer point in "bset", preferably one that is
76 * close to minimizing "f".
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".
83 static __isl_give isl_vec *initial_solution(__isl_keep isl_basic_set *bset,
84 isl_int *f)
86 enum isl_lp_result res;
87 struct isl_basic_set *unit_box;
88 struct isl_vec *sol;
90 unit_box = unit_box_base_points(isl_basic_set_copy(bset));
92 res = isl_basic_set_solve_lp(unit_box, 0, f, bset->ctx->one,
93 NULL, NULL, &sol);
94 if (res == isl_lp_ok) {
95 isl_basic_set_free(unit_box);
96 return isl_vec_ceil(sol);
99 isl_basic_set_free(unit_box);
101 return isl_basic_set_sample_vec(isl_basic_set_copy(bset));
104 /* Restrict "bset" to those points with values for f in the interval [l, u].
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)
109 int k;
110 unsigned total;
112 total = isl_basic_set_total_dim(bset);
113 bset = isl_basic_set_extend_constraints(bset, 0, 2);
115 k = isl_basic_set_alloc_inequality(bset);
116 if (k < 0)
117 goto error;
118 isl_seq_cpy(bset->ineq[k], f, 1 + total);
119 isl_int_sub(bset->ineq[k][0], bset->ineq[k][0], l);
121 k = isl_basic_set_alloc_inequality(bset);
122 if (k < 0)
123 goto error;
124 isl_seq_neg(bset->ineq[k], f, 1 + total);
125 isl_int_add(bset->ineq[k][0], bset->ineq[k][0], u);
127 return bset;
128 error:
129 isl_basic_set_free(bset);
130 return NULL;
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.
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.
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)
152 isl_int tmp;
153 int divide = 1;
155 isl_int_init(tmp);
157 while (isl_int_le(l, u)) {
158 struct isl_basic_set *slice;
159 struct isl_vec *sample;
161 if (!divide)
162 isl_int_set(tmp, u);
163 else {
164 isl_int_sub(tmp, u, l);
165 isl_int_fdiv_q_ui(tmp, tmp, 2);
166 isl_int_add(tmp, tmp, l);
168 slice = add_bounds(isl_basic_set_copy(bset), f, l, tmp);
169 sample = isl_basic_set_sample_vec(slice);
170 if (!sample) {
171 isl_vec_free(sol);
172 sol = NULL;
173 break;
175 if (sample->size > 0) {
176 isl_vec_free(sol);
177 sol = sample;
178 isl_seq_inner_product(f, sol->el, sol->size, opt);
179 isl_int_sub_ui(u, *opt, 1);
180 divide = 1;
181 } else {
182 isl_vec_free(sample);
183 if (!divide)
184 break;
185 isl_int_add_ui(l, tmp, 1);
186 divide = 0;
190 isl_int_clear(tmp);
192 return sol;
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.
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.
206 * We then call solve_ilp_search to perform a binary search on the interval.
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)
211 enum isl_lp_result res;
212 isl_int l, u;
213 struct isl_vec *sol;
215 res = isl_basic_set_solve_lp(bset, 0, f, bset->ctx->one,
216 opt, NULL, &sol);
217 if (res == isl_lp_ok && isl_int_is_one(sol->el[0])) {
218 if (sol_p)
219 *sol_p = sol;
220 else
221 isl_vec_free(sol);
222 return isl_lp_ok;
224 isl_vec_free(sol);
225 if (res == isl_lp_error || res == isl_lp_empty)
226 return res;
228 sol = initial_solution(bset, f);
229 if (!sol)
230 return isl_lp_error;
231 if (sol->size == 0) {
232 isl_vec_free(sol);
233 return isl_lp_empty;
235 if (res == isl_lp_unbounded) {
236 isl_vec_free(sol);
237 return isl_lp_unbounded;
240 isl_int_init(l);
241 isl_int_init(u);
243 isl_int_set(l, *opt);
245 isl_seq_inner_product(f, sol->el, sol->size, opt);
246 isl_int_sub_ui(u, *opt, 1);
248 sol = solve_ilp_search(bset, f, opt, sol, l, u);
249 if (!sol)
250 res = isl_lp_error;
252 isl_int_clear(l);
253 isl_int_clear(u);
255 if (sol_p)
256 *sol_p = sol;
257 else
258 isl_vec_free(sol);
260 return res;
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)
266 unsigned dim;
267 enum isl_lp_result res;
268 struct isl_mat *T = NULL;
269 struct isl_vec *v;
271 bset = isl_basic_set_copy(bset);
272 dim = isl_basic_set_total_dim(bset);
273 v = isl_vec_alloc(bset->ctx, 1 + dim);
274 if (!v)
275 goto error;
276 isl_seq_cpy(v->el, f, 1 + dim);
277 bset = isl_basic_set_remove_equalities(bset, &T, NULL);
278 v = isl_vec_mat_product(v, isl_mat_copy(T));
279 if (!v)
280 goto error;
281 res = isl_basic_set_solve_ilp(bset, max, v->el, opt, sol_p);
282 isl_vec_free(v);
283 if (res == isl_lp_ok && sol_p) {
284 *sol_p = isl_mat_vec_product(T, *sol_p);
285 if (!*sol_p)
286 res = isl_lp_error;
287 } else
288 isl_mat_free(T);
289 isl_basic_set_free(bset);
290 return res;
291 error:
292 isl_mat_free(T);
293 isl_basic_set_free(bset);
294 return isl_lp_error;
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.
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.
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)
308 unsigned dim;
309 enum isl_lp_result res;
311 if (!bset)
312 return isl_lp_error;
313 if (sol_p)
314 *sol_p = NULL;
316 isl_assert(bset->ctx, isl_basic_set_n_param(bset) == 0,
317 return isl_lp_error);
319 if (isl_basic_set_plain_is_empty(bset))
320 return isl_lp_empty;
322 if (bset->n_eq)
323 return solve_ilp_with_eq(bset, max, f, opt, sol_p);
325 dim = isl_basic_set_total_dim(bset);
327 if (max)
328 isl_seq_neg(f, f, 1 + dim);
330 res = solve_ilp(bset, f, opt, sol_p);
332 if (max) {
333 isl_seq_neg(f, f, 1 + dim);
334 isl_int_neg(*opt, *opt);
337 return res;
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)
343 enum isl_lp_result res;
345 if (!obj)
346 return isl_lp_error;
347 bset = isl_basic_set_copy(bset);
348 bset = isl_basic_set_underlying_set(bset);
349 res = isl_basic_set_solve_ilp(bset, max, obj->v->el + 1, opt, NULL);
350 isl_basic_set_free(bset);
351 return res;
354 static __isl_give isl_mat *extract_divs(__isl_keep isl_basic_set *bset)
356 int i;
357 isl_ctx *ctx = isl_basic_set_get_ctx(bset);
358 isl_mat *div;
360 div = isl_mat_alloc(ctx, bset->n_div,
361 1 + 1 + isl_basic_set_total_dim(bset));
362 if (!div)
363 return NULL;
365 for (i = 0; i < bset->n_div; ++i)
366 isl_seq_cpy(div->row[i], bset->div[i], div->n_col);
368 return div;
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)
374 int *exp1 = NULL;
375 int *exp2 = NULL;
376 isl_ctx *ctx;
377 isl_mat *bset_div = NULL;
378 isl_mat *div = NULL;
379 enum isl_lp_result res;
380 int bset_n_div, obj_n_div;
382 if (!bset || !obj)
383 return isl_lp_error;
385 ctx = isl_aff_get_ctx(obj);
386 if (!isl_space_is_equal(bset->dim, obj->ls->dim))
387 isl_die(ctx, isl_error_invalid,
388 "spaces don't match", return isl_lp_error);
389 if (!isl_int_is_one(obj->v->el[0]))
390 isl_die(ctx, isl_error_unsupported,
391 "expecting integer affine expression",
392 return isl_lp_error);
394 bset_n_div = isl_basic_set_dim(bset, isl_dim_div);
395 obj_n_div = isl_aff_dim(obj, isl_dim_div);
396 if (bset_n_div == 0 && obj_n_div == 0)
397 return basic_set_opt(bset, max, obj, opt);
399 bset = isl_basic_set_copy(bset);
400 obj = isl_aff_copy(obj);
402 bset_div = extract_divs(bset);
403 exp1 = isl_alloc_array(ctx, int, bset_n_div);
404 exp2 = isl_alloc_array(ctx, int, obj_n_div);
405 if (!bset_div || (bset_n_div && !exp1) || (obj_n_div && !exp2))
406 goto error;
408 div = isl_merge_divs(bset_div, obj->ls->div, exp1, exp2);
410 bset = isl_basic_set_expand_divs(bset, isl_mat_copy(div), exp1);
411 obj = isl_aff_expand_divs(obj, isl_mat_copy(div), exp2);
413 res = basic_set_opt(bset, max, obj, opt);
415 isl_mat_free(bset_div);
416 isl_mat_free(div);
417 free(exp1);
418 free(exp2);
419 isl_basic_set_free(bset);
420 isl_aff_free(obj);
422 return res;
423 error:
424 isl_mat_free(div);
425 isl_mat_free(bset_div);
426 free(exp1);
427 free(exp2);
428 isl_basic_set_free(bset);
429 isl_aff_free(obj);
430 return isl_lp_error;
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.
436 * The parameters are assumed to have been aligned.
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)
441 int i;
442 enum isl_lp_result res;
443 int empty = 1;
444 isl_int opt_i;
446 if (!set || !obj)
447 return isl_lp_error;
448 if (set->n == 0)
449 return isl_lp_empty;
451 res = isl_basic_set_opt(set->p[0], max, obj, opt);
452 if (res == isl_lp_error || res == isl_lp_unbounded)
453 return res;
454 if (set->n == 1)
455 return res;
456 if (res == isl_lp_ok)
457 empty = 0;
459 isl_int_init(opt_i);
460 for (i = 1; i < set->n; ++i) {
461 res = isl_basic_set_opt(set->p[i], max, obj, &opt_i);
462 if (res == isl_lp_error || res == isl_lp_unbounded) {
463 isl_int_clear(opt_i);
464 return res;
466 if (res == isl_lp_empty)
467 continue;
468 empty = 0;
469 if (max ? isl_int_gt(opt_i, *opt) : isl_int_lt(opt_i, *opt))
470 isl_int_set(*opt, opt_i);
472 isl_int_clear(opt_i);
474 return empty ? isl_lp_empty : isl_lp_ok;
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.
480 enum isl_lp_result isl_set_opt(__isl_keep isl_set *set, int max,
481 __isl_keep isl_aff *obj, isl_int *opt)
483 enum isl_lp_result res;
484 isl_bool aligned;
486 if (!set || !obj)
487 return isl_lp_error;
489 aligned = isl_set_space_has_equal_params(set, obj->ls->dim);
490 if (aligned < 0)
491 return isl_lp_error;
492 if (aligned)
493 return isl_set_opt_aligned(set, max, obj, opt);
495 set = isl_set_copy(set);
496 obj = isl_aff_copy(obj);
497 set = isl_set_align_params(set, isl_aff_get_domain_space(obj));
498 obj = isl_aff_align_params(obj, isl_set_get_space(set));
500 res = isl_set_opt_aligned(set, max, obj, opt);
502 isl_set_free(set);
503 isl_aff_free(obj);
505 return res;
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.
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".
518 static __isl_give isl_val *convert_lp_result(enum isl_lp_result lp_res,
519 __isl_take isl_val *v, int max)
521 isl_ctx *ctx;
523 if (lp_res == isl_lp_ok) {
524 isl_int_set_si(v->d, 1);
525 return isl_val_normalize(v);
527 ctx = isl_val_get_ctx(v);
528 isl_val_free(v);
529 if (lp_res == isl_lp_error)
530 return NULL;
531 if (lp_res == isl_lp_empty)
532 return isl_val_nan(ctx);
533 if (max)
534 return isl_val_infty(ctx);
535 else
536 return isl_val_neginfty(ctx);
539 /* Return the minimum (maximum if max is set) of the integer affine
540 * expression "obj" over the points in "bset".
542 * Return infinity or negative infinity if the optimal value is unbounded and
543 * NaN if "bset" is empty.
545 * Call isl_basic_set_opt and translate the results.
547 __isl_give isl_val *isl_basic_set_opt_val(__isl_keep isl_basic_set *bset,
548 int max, __isl_keep isl_aff *obj)
550 isl_ctx *ctx;
551 isl_val *res;
552 enum isl_lp_result lp_res;
554 if (!bset || !obj)
555 return NULL;
557 ctx = isl_aff_get_ctx(obj);
558 res = isl_val_alloc(ctx);
559 if (!res)
560 return NULL;
561 lp_res = isl_basic_set_opt(bset, max, obj, &res->n);
562 return convert_lp_result(lp_res, res, max);
565 /* Return the maximum of the integer affine
566 * expression "obj" over the points in "bset".
568 * Return infinity or negative infinity if the optimal value is unbounded and
569 * NaN if "bset" is empty.
571 __isl_give isl_val *isl_basic_set_max_val(__isl_keep isl_basic_set *bset,
572 __isl_keep isl_aff *obj)
574 return isl_basic_set_opt_val(bset, 1, obj);
577 /* Return the minimum (maximum if max is set) of the integer affine
578 * expression "obj" over the points in "set".
580 * Return infinity or negative infinity if the optimal value is unbounded and
581 * NaN if "set" is empty.
583 * Call isl_set_opt and translate the results.
585 __isl_give isl_val *isl_set_opt_val(__isl_keep isl_set *set, int max,
586 __isl_keep isl_aff *obj)
588 isl_ctx *ctx;
589 isl_val *res;
590 enum isl_lp_result lp_res;
592 if (!set || !obj)
593 return NULL;
595 ctx = isl_aff_get_ctx(obj);
596 res = isl_val_alloc(ctx);
597 if (!res)
598 return NULL;
599 lp_res = isl_set_opt(set, max, obj, &res->n);
600 return convert_lp_result(lp_res, res, max);
603 /* Return the minimum of the integer affine
604 * expression "obj" over the points in "set".
606 * Return infinity or negative infinity if the optimal value is unbounded and
607 * NaN if "set" is empty.
609 __isl_give isl_val *isl_set_min_val(__isl_keep isl_set *set,
610 __isl_keep isl_aff *obj)
612 return isl_set_opt_val(set, 0, obj);
615 /* Return the maximum of the integer affine
616 * expression "obj" over the points in "set".
618 * Return infinity or negative infinity if the optimal value is unbounded and
619 * NaN if "set" is empty.
621 __isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set,
622 __isl_keep isl_aff *obj)
624 return isl_set_opt_val(set, 1, obj);
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.
631 static __isl_give isl_val *val_opt(__isl_take isl_val *v1,
632 __isl_take isl_val *v2, int max)
634 if (!v1 || !v2)
635 goto error;
636 if (isl_val_is_nan(v1)) {
637 isl_val_free(v1);
638 return v2;
640 if (isl_val_is_nan(v2)) {
641 isl_val_free(v2);
642 return v1;
644 if (max)
645 return isl_val_max(v1, v2);
646 else
647 return isl_val_min(v1, v2);
648 error:
649 isl_val_free(v1);
650 isl_val_free(v2);
651 return NULL;
654 /* Internal data structure for isl_set_opt_pw_aff.
656 * "max" is set if the maximum should be computed.
657 * "set" is the set over which the optimum should be computed.
658 * "res" contains the current optimum and is initialized to NaN.
660 struct isl_set_opt_data {
661 int max;
662 isl_set *set;
664 isl_val *res;
667 /* Update the optimum in data->res with respect to the affine function
668 * "aff" defined over "set".
670 static isl_stat piece_opt(__isl_take isl_set *set, __isl_take isl_aff *aff,
671 void *user)
673 struct isl_set_opt_data *data = user;
674 isl_val *opt;
676 set = isl_set_intersect(set, isl_set_copy(data->set));
677 opt = isl_set_opt_val(set, data->max, aff);
678 isl_set_free(set);
679 isl_aff_free(aff);
681 data->res = val_opt(data->res, opt, data->max);
682 if (!data->res)
683 return isl_stat_error;
685 return isl_stat_ok;
688 /* Return the minimum (maximum if "max" is set) of the integer piecewise affine
689 * expression "obj" over the points in "set".
691 * Return infinity or negative infinity if the optimal value is unbounded and
692 * NaN if the intersection of "set" with the domain of "obj" is empty.
694 * Initialize the result to NaN and then update it for each of the pieces
695 * in "obj".
697 static __isl_give isl_val *isl_set_opt_pw_aff(__isl_keep isl_set *set, int max,
698 __isl_keep isl_pw_aff *obj)
700 struct isl_set_opt_data data = { max, set };
702 data.res = isl_val_nan(isl_set_get_ctx(set));
703 if (isl_pw_aff_foreach_piece(obj, &piece_opt, &data) < 0)
704 return isl_val_free(data.res);
706 return data.res;
709 /* Internal data structure for isl_union_set_opt_union_pw_aff.
711 * "max" is set if the maximum should be computed.
712 * "obj" is the objective function that needs to be optimized.
713 * "res" contains the current optimum and is initialized to NaN.
715 struct isl_union_set_opt_data {
716 int max;
717 isl_union_pw_aff *obj;
719 isl_val *res;
722 /* Update the optimum in data->res with the optimum over "set".
723 * Do so by first extracting the matching objective function
724 * from data->obj.
726 static isl_stat set_opt(__isl_take isl_set *set, void *user)
728 struct isl_union_set_opt_data *data = user;
729 isl_space *space;
730 isl_pw_aff *pa;
731 isl_val *opt;
733 space = isl_set_get_space(set);
734 space = isl_space_from_domain(space);
735 space = isl_space_add_dims(space, isl_dim_out, 1);
736 pa = isl_union_pw_aff_extract_pw_aff(data->obj, space);
737 opt = isl_set_opt_pw_aff(set, data->max, pa);
738 isl_pw_aff_free(pa);
739 isl_set_free(set);
741 data->res = val_opt(data->res, opt, data->max);
742 if (!data->res)
743 return isl_stat_error;
745 return isl_stat_ok;
748 /* Return the minimum (maximum if "max" is set) of the integer piecewise affine
749 * expression "obj" over the points in "uset".
751 * Return infinity or negative infinity if the optimal value is unbounded and
752 * NaN if the intersection of "uset" with the domain of "obj" is empty.
754 * Initialize the result to NaN and then update it for each of the sets
755 * in "uset".
757 static __isl_give isl_val *isl_union_set_opt_union_pw_aff(
758 __isl_keep isl_union_set *uset, int max,
759 __isl_keep isl_union_pw_aff *obj)
761 struct isl_union_set_opt_data data = { max, obj };
763 data.res = isl_val_nan(isl_union_set_get_ctx(uset));
764 if (isl_union_set_foreach_set(uset, &set_opt, &data) < 0)
765 return isl_val_free(data.res);
767 return data.res;
770 /* Return a list of minima (maxima if "max" is set) over the points in "uset"
771 * for each of the expressions in "obj".
773 * An element in the list is infinity or negative infinity if the optimal
774 * value of the corresponding expression is unbounded and
775 * NaN if the intersection of "uset" with the domain of the expression
776 * is empty.
778 * Iterate over all the expressions in "obj" and collect the results.
780 static __isl_give isl_multi_val *isl_union_set_opt_multi_union_pw_aff(
781 __isl_keep isl_union_set *uset, int max,
782 __isl_keep isl_multi_union_pw_aff *obj)
784 int i, n;
785 isl_multi_val *mv;
787 if (!uset || !obj)
788 return NULL;
790 n = isl_multi_union_pw_aff_dim(obj, isl_dim_set);
791 mv = isl_multi_val_zero(isl_multi_union_pw_aff_get_space(obj));
793 for (i = 0; i < n; ++i) {
794 isl_val *v;
795 isl_union_pw_aff *upa;
797 upa = isl_multi_union_pw_aff_get_union_pw_aff(obj, i);
798 v = isl_union_set_opt_union_pw_aff(uset, max, upa);
799 isl_union_pw_aff_free(upa);
800 mv = isl_multi_val_set_val(mv, i, v);
803 return mv;
806 /* Return a list of minima over the points in "uset"
807 * for each of the expressions in "obj".
809 * An element in the list is infinity or negative infinity if the optimal
810 * value of the corresponding expression is unbounded and
811 * NaN if the intersection of "uset" with the domain of the expression
812 * is empty.
814 __isl_give isl_multi_val *isl_union_set_min_multi_union_pw_aff(
815 __isl_keep isl_union_set *uset, __isl_keep isl_multi_union_pw_aff *obj)
817 return isl_union_set_opt_multi_union_pw_aff(uset, 0, obj);
820 /* Return the maximal value attained by the given set dimension,
821 * independently of the parameter values and of any other dimensions.
823 * Return infinity if the optimal value is unbounded and
824 * NaN if "bset" is empty.
826 __isl_give isl_val *isl_basic_set_dim_max_val(__isl_take isl_basic_set *bset,
827 int pos)
829 isl_local_space *ls;
830 isl_aff *obj;
831 isl_val *v;
833 if (!bset)
834 return NULL;
835 if (pos < 0 || pos >= isl_basic_set_dim(bset, isl_dim_set))
836 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
837 "position out of bounds", goto error);
838 ls = isl_local_space_from_space(isl_basic_set_get_space(bset));
839 obj = isl_aff_var_on_domain(ls, isl_dim_set, pos);
840 v = isl_basic_set_max_val(bset, obj);
841 isl_aff_free(obj);
842 isl_basic_set_free(bset);
844 return v;
845 error:
846 isl_basic_set_free(bset);
847 return NULL;