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
10 #include <isl_ctx_private.h>
11 #include <isl_map_private.h>
13 #include <isl/union_set.h>
14 #include "isl_sample.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
)
38 struct isl_basic_set
*unit_box
= NULL
;
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
),
54 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
55 k
= isl_basic_set_alloc_inequality(unit_box
);
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
]))
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
);
70 isl_basic_set_free(bset
);
71 isl_basic_set_free(unit_box
);
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
,
86 enum isl_lp_result res
;
87 struct isl_basic_set
*unit_box
;
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
,
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
)
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
);
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
);
124 isl_seq_neg(bset
->ineq
[k
], f
, 1 + total
);
125 isl_int_add(bset
->ineq
[k
][0], bset
->ineq
[k
][0], u
);
129 isl_basic_set_free(bset
);
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
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
)
157 while (isl_int_le(l
, u
)) {
158 struct isl_basic_set
*slice
;
159 struct isl_vec
*sample
;
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
);
175 if (sample
->size
> 0) {
178 isl_seq_inner_product(f
, sol
->el
, sol
->size
, opt
);
179 isl_int_sub_ui(u
, *opt
, 1);
182 isl_vec_free(sample
);
185 isl_int_add_ui(l
, tmp
, 1);
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
;
215 res
= isl_basic_set_solve_lp(bset
, 0, f
, bset
->ctx
->one
,
217 if (res
== isl_lp_ok
&& isl_int_is_one(sol
->el
[0])) {
225 if (res
== isl_lp_error
|| res
== isl_lp_empty
)
228 sol
= initial_solution(bset
, f
);
231 if (sol
->size
== 0) {
235 if (res
== isl_lp_unbounded
) {
237 return isl_lp_unbounded
;
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
);
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
)
267 enum isl_lp_result res
;
268 struct isl_mat
*T
= NULL
;
271 bset
= isl_basic_set_copy(bset
);
272 dim
= isl_basic_set_total_dim(bset
);
273 v
= isl_vec_alloc(bset
->ctx
, 1 + dim
);
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
));
281 res
= isl_basic_set_solve_ilp(bset
, max
, v
->el
, opt
, sol_p
);
283 if (res
== isl_lp_ok
&& sol_p
) {
284 *sol_p
= isl_mat_vec_product(T
, *sol_p
);
289 isl_basic_set_free(bset
);
293 isl_basic_set_free(bset
);
297 /* Find an integer point in "bset" that minimizes (or maximizes if max is set)
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
)
309 enum isl_lp_result res
;
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
))
323 return solve_ilp_with_eq(bset
, max
, f
, opt
, sol_p
);
325 dim
= isl_basic_set_total_dim(bset
);
328 isl_seq_neg(f
, f
, 1 + dim
);
330 res
= solve_ilp(bset
, f
, opt
, sol_p
);
333 isl_seq_neg(f
, f
, 1 + dim
);
334 isl_int_neg(*opt
, *opt
);
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
;
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
);
354 enum isl_lp_result
isl_basic_set_opt(__isl_keep isl_basic_set
*bset
, int max
,
355 __isl_keep isl_aff
*obj
, isl_int
*opt
)
360 isl_mat
*bset_div
= NULL
;
362 enum isl_lp_result res
;
363 int bset_n_div
, obj_n_div
;
368 ctx
= isl_aff_get_ctx(obj
);
369 if (!isl_space_is_equal(bset
->dim
, obj
->ls
->dim
))
370 isl_die(ctx
, isl_error_invalid
,
371 "spaces don't match", return isl_lp_error
);
372 if (!isl_int_is_one(obj
->v
->el
[0]))
373 isl_die(ctx
, isl_error_unsupported
,
374 "expecting integer affine expression",
375 return isl_lp_error
);
377 bset_n_div
= isl_basic_set_dim(bset
, isl_dim_div
);
378 obj_n_div
= isl_aff_dim(obj
, isl_dim_div
);
379 if (bset_n_div
== 0 && obj_n_div
== 0)
380 return basic_set_opt(bset
, max
, obj
, opt
);
382 bset
= isl_basic_set_copy(bset
);
383 obj
= isl_aff_copy(obj
);
385 bset_div
= isl_basic_set_get_divs(bset
);
386 exp1
= isl_alloc_array(ctx
, int, bset_n_div
);
387 exp2
= isl_alloc_array(ctx
, int, obj_n_div
);
388 if (!bset_div
|| (bset_n_div
&& !exp1
) || (obj_n_div
&& !exp2
))
391 div
= isl_merge_divs(bset_div
, obj
->ls
->div
, exp1
, exp2
);
393 bset
= isl_basic_set_expand_divs(bset
, isl_mat_copy(div
), exp1
);
394 obj
= isl_aff_expand_divs(obj
, isl_mat_copy(div
), exp2
);
396 res
= basic_set_opt(bset
, max
, obj
, opt
);
398 isl_mat_free(bset_div
);
402 isl_basic_set_free(bset
);
408 isl_mat_free(bset_div
);
411 isl_basic_set_free(bset
);
416 /* Compute the minimum (maximum if max is set) of the integer affine
417 * expression obj over the points in set and put the result in *opt.
419 * The parameters are assumed to have been aligned.
421 static enum isl_lp_result
isl_set_opt_aligned(__isl_keep isl_set
*set
, int max
,
422 __isl_keep isl_aff
*obj
, isl_int
*opt
)
425 enum isl_lp_result res
;
434 res
= isl_basic_set_opt(set
->p
[0], max
, obj
, opt
);
435 if (res
== isl_lp_error
|| res
== isl_lp_unbounded
)
439 if (res
== isl_lp_ok
)
443 for (i
= 1; i
< set
->n
; ++i
) {
444 res
= isl_basic_set_opt(set
->p
[i
], max
, obj
, &opt_i
);
445 if (res
== isl_lp_error
|| res
== isl_lp_unbounded
) {
446 isl_int_clear(opt_i
);
449 if (res
== isl_lp_empty
)
452 if (max
? isl_int_gt(opt_i
, *opt
) : isl_int_lt(opt_i
, *opt
))
453 isl_int_set(*opt
, opt_i
);
455 isl_int_clear(opt_i
);
457 return empty
? isl_lp_empty
: isl_lp_ok
;
460 /* Compute the minimum (maximum if max is set) of the integer affine
461 * expression obj over the points in set and put the result in *opt.
463 enum isl_lp_result
isl_set_opt(__isl_keep isl_set
*set
, int max
,
464 __isl_keep isl_aff
*obj
, isl_int
*opt
)
466 enum isl_lp_result res
;
472 aligned
= isl_set_space_has_equal_params(set
, obj
->ls
->dim
);
476 return isl_set_opt_aligned(set
, max
, obj
, opt
);
478 set
= isl_set_copy(set
);
479 obj
= isl_aff_copy(obj
);
480 set
= isl_set_align_params(set
, isl_aff_get_domain_space(obj
));
481 obj
= isl_aff_align_params(obj
, isl_set_get_space(set
));
483 res
= isl_set_opt_aligned(set
, max
, obj
, opt
);
491 /* Convert the result of a function that returns an isl_lp_result
492 * to an isl_val. The numerator of "v" is set to the optimal value
493 * if lp_res is isl_lp_ok. "max" is set if a maximum was computed.
495 * Return "v" with denominator set to 1 if lp_res is isl_lp_ok.
496 * Return NULL on error.
497 * Return a NaN if lp_res is isl_lp_empty.
498 * Return infinity or negative infinity if lp_res is isl_lp_unbounded,
499 * depending on "max".
501 static __isl_give isl_val
*convert_lp_result(enum isl_lp_result lp_res
,
502 __isl_take isl_val
*v
, int max
)
506 if (lp_res
== isl_lp_ok
) {
507 isl_int_set_si(v
->d
, 1);
508 return isl_val_normalize(v
);
510 ctx
= isl_val_get_ctx(v
);
512 if (lp_res
== isl_lp_error
)
514 if (lp_res
== isl_lp_empty
)
515 return isl_val_nan(ctx
);
517 return isl_val_infty(ctx
);
519 return isl_val_neginfty(ctx
);
522 /* Return the minimum (maximum if max is set) of the integer affine
523 * expression "obj" over the points in "bset".
525 * Return infinity or negative infinity if the optimal value is unbounded and
526 * NaN if "bset" is empty.
528 * Call isl_basic_set_opt and translate the results.
530 __isl_give isl_val
*isl_basic_set_opt_val(__isl_keep isl_basic_set
*bset
,
531 int max
, __isl_keep isl_aff
*obj
)
535 enum isl_lp_result lp_res
;
540 ctx
= isl_aff_get_ctx(obj
);
541 res
= isl_val_alloc(ctx
);
544 lp_res
= isl_basic_set_opt(bset
, max
, obj
, &res
->n
);
545 return convert_lp_result(lp_res
, res
, max
);
548 /* Return the maximum of the integer affine
549 * expression "obj" over the points in "bset".
551 * Return infinity or negative infinity if the optimal value is unbounded and
552 * NaN if "bset" is empty.
554 __isl_give isl_val
*isl_basic_set_max_val(__isl_keep isl_basic_set
*bset
,
555 __isl_keep isl_aff
*obj
)
557 return isl_basic_set_opt_val(bset
, 1, obj
);
560 /* Return the minimum (maximum if max is set) of the integer affine
561 * expression "obj" over the points in "set".
563 * Return infinity or negative infinity if the optimal value is unbounded and
564 * NaN if "set" is empty.
566 * Call isl_set_opt and translate the results.
568 __isl_give isl_val
*isl_set_opt_val(__isl_keep isl_set
*set
, int max
,
569 __isl_keep isl_aff
*obj
)
573 enum isl_lp_result lp_res
;
578 ctx
= isl_aff_get_ctx(obj
);
579 res
= isl_val_alloc(ctx
);
582 lp_res
= isl_set_opt(set
, max
, obj
, &res
->n
);
583 return convert_lp_result(lp_res
, res
, max
);
586 /* Return the minimum of the integer affine
587 * expression "obj" over the points in "set".
589 * Return infinity or negative infinity if the optimal value is unbounded and
590 * NaN if "set" is empty.
592 __isl_give isl_val
*isl_set_min_val(__isl_keep isl_set
*set
,
593 __isl_keep isl_aff
*obj
)
595 return isl_set_opt_val(set
, 0, obj
);
598 /* Return the maximum of the integer affine
599 * expression "obj" over the points in "set".
601 * Return infinity or negative infinity if the optimal value is unbounded and
602 * NaN if "set" is empty.
604 __isl_give isl_val
*isl_set_max_val(__isl_keep isl_set
*set
,
605 __isl_keep isl_aff
*obj
)
607 return isl_set_opt_val(set
, 1, obj
);
610 /* Return the optimum (min or max depending on "max") of "v1" and "v2",
611 * where either may be NaN, signifying an uninitialized value.
612 * That is, if either is NaN, then return the other one.
614 static __isl_give isl_val
*val_opt(__isl_take isl_val
*v1
,
615 __isl_take isl_val
*v2
, int max
)
619 if (isl_val_is_nan(v1
)) {
623 if (isl_val_is_nan(v2
)) {
628 return isl_val_max(v1
, v2
);
630 return isl_val_min(v1
, v2
);
637 /* Internal data structure for isl_pw_aff_opt_val.
639 * "max" is set if the maximum should be computed.
640 * "res" contains the current optimum and is initialized to NaN.
642 struct isl_pw_aff_opt_data
{
648 /* Update the optimum in data->res with respect to the affine function
649 * "aff" defined over "set".
651 static isl_stat
piece_opt(__isl_take isl_set
*set
, __isl_take isl_aff
*aff
,
654 struct isl_pw_aff_opt_data
*data
= user
;
657 opt
= isl_set_opt_val(set
, data
->max
, aff
);
661 data
->res
= val_opt(data
->res
, opt
, data
->max
);
663 return isl_stat_error
;
668 /* Return the minimum (maximum if "max" is set) of the integer piecewise affine
669 * expression "pa" over its definition domain.
671 * Return infinity or negative infinity if the optimal value is unbounded and
672 * NaN if the domain of "pa" is empty.
674 * Initialize the result to NaN and then update it for each of the pieces
677 static __isl_give isl_val
*isl_pw_aff_opt_val(__isl_take isl_pw_aff
*pa
,
680 struct isl_pw_aff_opt_data data
= { max
};
682 data
.res
= isl_val_nan(isl_pw_aff_get_ctx(pa
));
683 if (isl_pw_aff_foreach_piece(pa
, &piece_opt
, &data
) < 0)
684 data
.res
= isl_val_free(data
.res
);
690 /* Internal data structure for isl_union_pw_aff_opt_val.
692 * "max" is set if the maximum should be computed.
693 * "res" contains the current optimum and is initialized to NaN.
695 struct isl_union_pw_aff_opt_data
{
701 /* Update the optimum in data->res with the optimum of "pa".
703 static isl_stat
pw_aff_opt(__isl_take isl_pw_aff
*pa
, void *user
)
705 struct isl_union_pw_aff_opt_data
*data
= user
;
708 opt
= isl_pw_aff_opt_val(pa
, data
->max
);
710 data
->res
= val_opt(data
->res
, opt
, data
->max
);
712 return isl_stat_error
;
717 /* Return the minimum (maximum if "max" is set) of the integer piecewise affine
718 * expression "upa" over its definition domain.
720 * Return infinity or negative infinity if the optimal value is unbounded and
721 * NaN if the domain of the expression is empty.
723 * Initialize the result to NaN and then update it
724 * for each of the piecewise affine expressions in "upa".
726 static __isl_give isl_val
*isl_union_pw_aff_opt_val(
727 __isl_take isl_union_pw_aff
*upa
, int max
)
729 struct isl_union_pw_aff_opt_data data
= { max
};
731 data
.res
= isl_val_nan(isl_union_pw_aff_get_ctx(upa
));
732 if (isl_union_pw_aff_foreach_pw_aff(upa
, &pw_aff_opt
, &data
) < 0)
733 data
.res
= isl_val_free(data
.res
);
734 isl_union_pw_aff_free(upa
);
739 /* Return the minimum of the integer piecewise affine
740 * expression "upa" over its definition domain.
742 * Return negative infinity if the optimal value is unbounded and
743 * NaN if the domain of the expression is empty.
745 __isl_give isl_val
*isl_union_pw_aff_min_val(__isl_take isl_union_pw_aff
*upa
)
747 return isl_union_pw_aff_opt_val(upa
, 0);
750 /* Return the maximum of the integer piecewise affine
751 * expression "upa" over its definition domain.
753 * Return infinity if the optimal value is unbounded and
754 * NaN if the domain of the expression is empty.
756 __isl_give isl_val
*isl_union_pw_aff_max_val(__isl_take isl_union_pw_aff
*upa
)
758 return isl_union_pw_aff_opt_val(upa
, 1);
761 /* Return a list of minima (maxima if "max" is set)
762 * for each of the expressions in "mupa" over their domains.
764 * An element in the list is infinity or negative infinity if the optimal
765 * value of the corresponding expression is unbounded and
766 * NaN if the domain of the expression is empty.
768 * Iterate over all the expressions in "mupa" and collect the results.
770 static __isl_give isl_multi_val
*isl_multi_union_pw_aff_opt_multi_val(
771 __isl_take isl_multi_union_pw_aff
*mupa
, int max
)
779 n
= isl_multi_union_pw_aff_dim(mupa
, isl_dim_set
);
780 mv
= isl_multi_val_zero(isl_multi_union_pw_aff_get_space(mupa
));
782 for (i
= 0; i
< n
; ++i
) {
784 isl_union_pw_aff
*upa
;
786 upa
= isl_multi_union_pw_aff_get_union_pw_aff(mupa
, i
);
787 v
= isl_union_pw_aff_opt_val(upa
, max
);
788 mv
= isl_multi_val_set_val(mv
, i
, v
);
791 isl_multi_union_pw_aff_free(mupa
);
795 /* Return a list of minima (maxima if "max" is set) over the points in "uset"
796 * for each of the expressions in "obj".
798 * An element in the list is infinity or negative infinity if the optimal
799 * value of the corresponding expression is unbounded and
800 * NaN if the intersection of "uset" with the domain of the expression
803 static __isl_give isl_multi_val
*isl_union_set_opt_multi_union_pw_aff(
804 __isl_keep isl_union_set
*uset
, int max
,
805 __isl_keep isl_multi_union_pw_aff
*obj
)
807 uset
= isl_union_set_copy(uset
);
808 obj
= isl_multi_union_pw_aff_copy(obj
);
809 obj
= isl_multi_union_pw_aff_intersect_domain(obj
, uset
);
810 return isl_multi_union_pw_aff_opt_multi_val(obj
, max
);
813 /* Return a list of minima over the points in "uset"
814 * for each of the expressions in "obj".
816 * An element in the list is infinity or negative infinity if the optimal
817 * value of the corresponding expression is unbounded and
818 * NaN if the intersection of "uset" with the domain of the expression
821 __isl_give isl_multi_val
*isl_union_set_min_multi_union_pw_aff(
822 __isl_keep isl_union_set
*uset
, __isl_keep isl_multi_union_pw_aff
*obj
)
824 return isl_union_set_opt_multi_union_pw_aff(uset
, 0, obj
);
827 /* Return a list of minima
828 * for each of the expressions in "mupa" over their domains.
830 * An element in the list is negative infinity if the optimal
831 * value of the corresponding expression is unbounded and
832 * NaN if the domain of the expression is empty.
834 __isl_give isl_multi_val
*isl_multi_union_pw_aff_min_multi_val(
835 __isl_take isl_multi_union_pw_aff
*mupa
)
837 return isl_multi_union_pw_aff_opt_multi_val(mupa
, 0);
840 /* Return a list of maxima
841 * for each of the expressions in "mupa" over their domains.
843 * An element in the list is infinity if the optimal
844 * value of the corresponding expression is unbounded and
845 * NaN if the domain of the expression is empty.
847 __isl_give isl_multi_val
*isl_multi_union_pw_aff_max_multi_val(
848 __isl_take isl_multi_union_pw_aff
*mupa
)
850 return isl_multi_union_pw_aff_opt_multi_val(mupa
, 1);
853 /* Return the maximal value attained by the given set dimension,
854 * independently of the parameter values and of any other dimensions.
856 * Return infinity if the optimal value is unbounded and
857 * NaN if "bset" is empty.
859 __isl_give isl_val
*isl_basic_set_dim_max_val(__isl_take isl_basic_set
*bset
,
866 if (isl_basic_set_check_range(bset
, isl_dim_set
, pos
, 1) < 0)
868 ls
= isl_local_space_from_space(isl_basic_set_get_space(bset
));
869 obj
= isl_aff_var_on_domain(ls
, isl_dim_set
, pos
);
870 v
= isl_basic_set_max_val(bset
, obj
);
872 isl_basic_set_free(bset
);
876 isl_basic_set_free(bset
);