2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 #include <isl_map_private.h>
14 #include <isl_constraint_private.h>
15 #include <isl_space_private.h>
17 #include <isl_aff_private.h>
18 #include <isl_local_space_private.h>
19 #include <isl_val_private.h>
20 #include <isl_vec_private.h>
22 #include <bset_to_bmap.c>
23 #include <bset_from_bmap.c>
26 #define BASE constraint
28 #include <isl_list_templ.c>
30 isl_ctx
*isl_constraint_get_ctx(__isl_keep isl_constraint
*c
)
32 return c
? isl_local_space_get_ctx(c
->ls
) : NULL
;
35 static isl_size
n(struct isl_constraint
*c
, enum isl_dim_type type
)
37 return isl_local_space_dim(c
->ls
, type
);
40 static unsigned offset(struct isl_constraint
*c
, enum isl_dim_type type
)
42 return isl_local_space_offset(c
->ls
, type
);
45 __isl_give isl_constraint
*isl_constraint_alloc_vec(int eq
,
46 __isl_take isl_local_space
*ls
, __isl_take isl_vec
*v
)
48 isl_constraint
*constraint
;
53 constraint
= isl_alloc_type(isl_vec_get_ctx(v
), isl_constraint
);
64 isl_local_space_free(ls
);
69 __isl_give isl_constraint
*isl_constraint_alloc(int eq
,
70 __isl_take isl_local_space
*ls
)
76 dim
= isl_local_space_dim(ls
, isl_dim_all
);
78 ls
= isl_local_space_free(ls
);
82 ctx
= isl_local_space_get_ctx(ls
);
83 v
= isl_vec_alloc(ctx
, 1 + dim
);
85 return isl_constraint_alloc_vec(eq
, ls
, v
);
88 struct isl_constraint
*isl_basic_map_constraint(struct isl_basic_map
*bmap
,
95 isl_local_space
*ls
= NULL
;
96 isl_constraint
*constraint
;
101 eq
= line
>= bmap
->eq
;
103 ctx
= isl_basic_map_get_ctx(bmap
);
104 ls
= isl_basic_map_get_local_space(bmap
);
105 dim
= isl_local_space_dim(ls
, isl_dim_all
);
108 v
= isl_vec_alloc(ctx
, 1 + dim
);
111 isl_seq_cpy(v
->el
, line
[0], v
->size
);
112 constraint
= isl_constraint_alloc_vec(eq
, ls
, v
);
114 isl_basic_map_free(bmap
);
117 isl_local_space_free(ls
);
118 isl_basic_map_free(bmap
);
122 struct isl_constraint
*isl_basic_set_constraint(struct isl_basic_set
*bset
,
125 return isl_basic_map_constraint(bset_to_bmap(bset
), line
);
128 __isl_give isl_constraint
*isl_constraint_alloc_equality(
129 __isl_take isl_local_space
*ls
)
131 return isl_constraint_alloc(1, ls
);
134 __isl_give isl_constraint
*isl_constraint_alloc_inequality(
135 __isl_take isl_local_space
*ls
)
137 return isl_constraint_alloc(0, ls
);
140 struct isl_constraint
*isl_constraint_dup(struct isl_constraint
*c
)
145 return isl_constraint_alloc_vec(c
->eq
, isl_local_space_copy(c
->ls
),
149 struct isl_constraint
*isl_constraint_cow(struct isl_constraint
*c
)
157 return isl_constraint_dup(c
);
160 struct isl_constraint
*isl_constraint_copy(struct isl_constraint
*constraint
)
169 __isl_null isl_constraint
*isl_constraint_free(__isl_take isl_constraint
*c
)
177 isl_local_space_free(c
->ls
);
184 /* Return the number of constraints in "bmap", i.e., the
185 * number of times isl_basic_map_foreach_constraint will
188 isl_size
isl_basic_map_n_constraint(__isl_keep isl_basic_map
*bmap
)
191 return isl_size_error
;
193 return bmap
->n_eq
+ bmap
->n_ineq
;
196 /* Return the number of constraints in "bset", i.e., the
197 * number of times isl_basic_set_foreach_constraint will
200 isl_size
isl_basic_set_n_constraint(__isl_keep isl_basic_set
*bset
)
202 return isl_basic_map_n_constraint(bset
);
205 isl_stat
isl_basic_map_foreach_constraint(__isl_keep isl_basic_map
*bmap
,
206 isl_stat (*fn
)(__isl_take isl_constraint
*c
, void *user
), void *user
)
209 struct isl_constraint
*c
;
212 return isl_stat_error
;
214 isl_assert(bmap
->ctx
, ISL_F_ISSET(bmap
, ISL_BASIC_MAP_FINAL
),
215 return isl_stat_error
);
217 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
218 c
= isl_basic_map_constraint(isl_basic_map_copy(bmap
),
221 return isl_stat_error
;
223 return isl_stat_error
;
226 for (i
= 0; i
< bmap
->n_ineq
; ++i
) {
227 c
= isl_basic_map_constraint(isl_basic_map_copy(bmap
),
230 return isl_stat_error
;
232 return isl_stat_error
;
238 isl_stat
isl_basic_set_foreach_constraint(__isl_keep isl_basic_set
*bset
,
239 isl_stat (*fn
)(__isl_take isl_constraint
*c
, void *user
), void *user
)
241 return isl_basic_map_foreach_constraint(bset_to_bmap(bset
), fn
, user
);
244 /* Add the constraint to the list that "user" points to, if it is not
247 static isl_stat
collect_constraint(__isl_take isl_constraint
*constraint
,
250 isl_constraint_list
**list
= user
;
253 is_div
= isl_constraint_is_div_constraint(constraint
);
254 if (is_div
< 0 || is_div
)
255 isl_constraint_free(constraint
);
257 *list
= isl_constraint_list_add(*list
, constraint
);
259 return is_div
< 0 ? isl_stat_error
: isl_stat_ok
;
262 /* Return a list of constraints that, when combined, are equivalent
263 * to "bmap". The input is required to have only known divs.
265 * There is no need to include the div constraints as they are
266 * implied by the div expressions.
268 __isl_give isl_constraint_list
*isl_basic_map_get_constraint_list(
269 __isl_keep isl_basic_map
*bmap
)
274 isl_constraint_list
*list
;
276 known
= isl_basic_map_divs_known(bmap
);
279 ctx
= isl_basic_map_get_ctx(bmap
);
281 isl_die(ctx
, isl_error_invalid
,
282 "input involves unknown divs", return NULL
);
284 n
= isl_basic_map_n_constraint(bmap
);
287 list
= isl_constraint_list_alloc(ctx
, n
);
288 if (isl_basic_map_foreach_constraint(bmap
,
289 &collect_constraint
, &list
) < 0)
290 list
= isl_constraint_list_free(list
);
295 /* Return a list of constraints that, when combined, are equivalent
296 * to "bset". The input is required to have only known divs.
298 __isl_give isl_constraint_list
*isl_basic_set_get_constraint_list(
299 __isl_keep isl_basic_set
*bset
)
301 return isl_basic_map_get_constraint_list(bset
);
304 int isl_constraint_is_equal(struct isl_constraint
*constraint1
,
305 struct isl_constraint
*constraint2
)
309 if (!constraint1
|| !constraint2
)
311 if (constraint1
->eq
!= constraint2
->eq
)
313 equal
= isl_local_space_is_equal(constraint1
->ls
, constraint2
->ls
);
314 if (equal
< 0 || !equal
)
316 return isl_vec_is_equal(constraint1
->v
, constraint2
->v
);
319 struct isl_basic_map
*isl_basic_map_add_constraint(
320 struct isl_basic_map
*bmap
, struct isl_constraint
*constraint
)
326 if (!bmap
|| !constraint
)
329 ctx
= isl_constraint_get_ctx(constraint
);
330 space
= isl_constraint_get_space(constraint
);
331 equal_space
= isl_space_is_equal(bmap
->dim
, space
);
332 isl_space_free(space
);
333 isl_assert(ctx
, equal_space
, goto error
);
335 bmap
= isl_basic_map_intersect(bmap
,
336 isl_basic_map_from_constraint(constraint
));
339 isl_basic_map_free(bmap
);
340 isl_constraint_free(constraint
);
344 struct isl_basic_set
*isl_basic_set_add_constraint(
345 struct isl_basic_set
*bset
, struct isl_constraint
*constraint
)
347 return bset_from_bmap(isl_basic_map_add_constraint(bset_to_bmap(bset
),
351 __isl_give isl_map
*isl_map_add_constraint(__isl_take isl_map
*map
,
352 __isl_take isl_constraint
*constraint
)
356 bmap
= isl_basic_map_from_constraint(constraint
);
357 map
= isl_map_intersect(map
, isl_map_from_basic_map(bmap
));
362 __isl_give isl_set
*isl_set_add_constraint(__isl_take isl_set
*set
,
363 __isl_take isl_constraint
*constraint
)
365 return isl_map_add_constraint(set
, constraint
);
368 /* Return the space of "constraint".
370 static __isl_keep isl_space
*isl_constraint_peek_space(
371 __isl_keep isl_constraint
*constraint
)
373 return constraint
? isl_local_space_peek_space(constraint
->ls
) : NULL
;
376 __isl_give isl_space
*isl_constraint_get_space(
377 __isl_keep isl_constraint
*constraint
)
379 return constraint
? isl_local_space_get_space(constraint
->ls
) : NULL
;
382 __isl_give isl_local_space
*isl_constraint_get_local_space(
383 __isl_keep isl_constraint
*constraint
)
385 return constraint
? isl_local_space_copy(constraint
->ls
) : NULL
;
388 isl_size
isl_constraint_dim(__isl_keep isl_constraint
*constraint
,
389 enum isl_dim_type type
)
392 return isl_size_error
;
393 return n(constraint
, type
);
397 #define TYPE isl_constraint
399 #include "check_type_range_templ.c"
401 isl_bool
isl_constraint_involves_dims(__isl_keep isl_constraint
*constraint
,
402 enum isl_dim_type type
, unsigned first
, unsigned n
)
406 isl_bool involves
= isl_bool_false
;
409 return isl_bool_error
;
411 return isl_bool_false
;
413 if (isl_constraint_check_range(constraint
, type
, first
, n
) < 0)
414 return isl_bool_error
;
416 active
= isl_local_space_get_active(constraint
->ls
,
417 constraint
->v
->el
+ 1);
421 first
+= isl_local_space_offset(constraint
->ls
, type
) - 1;
422 for (i
= 0; i
< n
; ++i
)
423 if (active
[first
+ i
]) {
424 involves
= isl_bool_true
;
433 return isl_bool_error
;
436 /* Does the given constraint represent a lower bound on the given
439 isl_bool
isl_constraint_is_lower_bound(__isl_keep isl_constraint
*constraint
,
440 enum isl_dim_type type
, unsigned pos
)
442 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
443 return isl_bool_error
;
445 pos
+= isl_local_space_offset(constraint
->ls
, type
);
446 return isl_bool_ok(isl_int_is_pos(constraint
->v
->el
[pos
]));
449 /* Does the given constraint represent an upper bound on the given
452 isl_bool
isl_constraint_is_upper_bound(__isl_keep isl_constraint
*constraint
,
453 enum isl_dim_type type
, unsigned pos
)
455 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
456 return isl_bool_error
;
458 pos
+= isl_local_space_offset(constraint
->ls
, type
);
459 return isl_bool_ok(isl_int_is_neg(constraint
->v
->el
[pos
]));
462 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint
*constraint
,
463 enum isl_dim_type type
, unsigned pos
)
466 isl_local_space_get_dim_name(constraint
->ls
, type
, pos
) : NULL
;
469 void isl_constraint_get_constant(__isl_keep isl_constraint
*constraint
,
474 isl_int_set(*v
, constraint
->v
->el
[0]);
477 /* Return the constant term of "constraint".
479 __isl_give isl_val
*isl_constraint_get_constant_val(
480 __isl_keep isl_constraint
*constraint
)
487 ctx
= isl_constraint_get_ctx(constraint
);
488 return isl_val_int_from_isl_int(ctx
, constraint
->v
->el
[0]);
491 void isl_constraint_get_coefficient(struct isl_constraint
*constraint
,
492 enum isl_dim_type type
, int pos
, isl_int
*v
)
494 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
497 pos
+= isl_local_space_offset(constraint
->ls
, type
);
498 isl_int_set(*v
, constraint
->v
->el
[pos
]);
501 /* Return the coefficient of the variable of type "type" at position "pos"
504 __isl_give isl_val
*isl_constraint_get_coefficient_val(
505 __isl_keep isl_constraint
*constraint
, enum isl_dim_type type
, int pos
)
509 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
512 ctx
= isl_constraint_get_ctx(constraint
);
513 pos
+= isl_local_space_offset(constraint
->ls
, type
);
514 return isl_val_int_from_isl_int(ctx
, constraint
->v
->el
[pos
]);
517 __isl_give isl_aff
*isl_constraint_get_div(__isl_keep isl_constraint
*constraint
,
523 return isl_local_space_get_div(constraint
->ls
, pos
);
526 __isl_give isl_constraint
*isl_constraint_set_constant(
527 __isl_take isl_constraint
*constraint
, isl_int v
)
529 constraint
= isl_constraint_cow(constraint
);
533 constraint
->v
= isl_vec_cow(constraint
->v
);
535 return isl_constraint_free(constraint
);
537 isl_int_set(constraint
->v
->el
[0], v
);
541 /* Replace the constant term of "constraint" by "v".
543 __isl_give isl_constraint
*isl_constraint_set_constant_val(
544 __isl_take isl_constraint
*constraint
, __isl_take isl_val
*v
)
546 constraint
= isl_constraint_cow(constraint
);
547 if (!constraint
|| !v
)
549 if (!isl_val_is_int(v
))
550 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
551 "expecting integer value", goto error
);
552 constraint
->v
= isl_vec_set_element_val(constraint
->v
, 0, v
);
554 constraint
= isl_constraint_free(constraint
);
558 return isl_constraint_free(constraint
);
561 __isl_give isl_constraint
*isl_constraint_set_constant_si(
562 __isl_take isl_constraint
*constraint
, int v
)
564 constraint
= isl_constraint_cow(constraint
);
568 constraint
->v
= isl_vec_cow(constraint
->v
);
570 return isl_constraint_free(constraint
);
572 isl_int_set_si(constraint
->v
->el
[0], v
);
576 __isl_give isl_constraint
*isl_constraint_set_coefficient(
577 __isl_take isl_constraint
*constraint
,
578 enum isl_dim_type type
, int pos
, isl_int v
)
580 constraint
= isl_constraint_cow(constraint
);
581 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
582 return isl_constraint_free(constraint
);
584 constraint
->v
= isl_vec_cow(constraint
->v
);
586 return isl_constraint_free(constraint
);
588 pos
+= isl_local_space_offset(constraint
->ls
, type
);
589 isl_int_set(constraint
->v
->el
[pos
], v
);
594 /* Replace the coefficient of the variable of type "type" at position "pos"
595 * of "constraint" by "v".
597 __isl_give isl_constraint
*isl_constraint_set_coefficient_val(
598 __isl_take isl_constraint
*constraint
,
599 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
601 constraint
= isl_constraint_cow(constraint
);
602 if (!constraint
|| !v
)
604 if (!isl_val_is_int(v
))
605 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
606 "expecting integer value", goto error
);
607 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
610 pos
+= isl_local_space_offset(constraint
->ls
, type
);
611 constraint
->v
= isl_vec_set_element_val(constraint
->v
, pos
, v
);
613 constraint
= isl_constraint_free(constraint
);
617 return isl_constraint_free(constraint
);
620 __isl_give isl_constraint
*isl_constraint_set_coefficient_si(
621 __isl_take isl_constraint
*constraint
,
622 enum isl_dim_type type
, int pos
, int v
)
624 constraint
= isl_constraint_cow(constraint
);
625 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
626 return isl_constraint_free(constraint
);
628 constraint
->v
= isl_vec_cow(constraint
->v
);
630 return isl_constraint_free(constraint
);
632 pos
+= isl_local_space_offset(constraint
->ls
, type
);
633 isl_int_set_si(constraint
->v
->el
[pos
], v
);
638 struct isl_constraint
*isl_constraint_negate(struct isl_constraint
*constraint
)
642 constraint
= isl_constraint_cow(constraint
);
646 ctx
= isl_constraint_get_ctx(constraint
);
647 if (isl_constraint_is_equality(constraint
))
648 isl_die(ctx
, isl_error_invalid
, "cannot negate equality",
649 return isl_constraint_free(constraint
));
650 constraint
->v
= isl_vec_neg(constraint
->v
);
651 constraint
->v
= isl_vec_cow(constraint
->v
);
653 return isl_constraint_free(constraint
);
654 isl_int_sub_ui(constraint
->v
->el
[0], constraint
->v
->el
[0], 1);
658 isl_bool
isl_constraint_is_equality(struct isl_constraint
*constraint
)
661 return isl_bool_error
;
662 return isl_bool_ok(constraint
->eq
);
665 isl_bool
isl_constraint_is_div_constraint(__isl_keep isl_constraint
*constraint
)
671 return isl_bool_error
;
672 if (isl_constraint_is_equality(constraint
))
673 return isl_bool_false
;
674 n_div
= isl_constraint_dim(constraint
, isl_dim_div
);
676 return isl_bool_error
;
677 for (i
= 0; i
< n_div
; ++i
) {
679 is_div
= isl_local_space_is_div_constraint(constraint
->ls
,
680 constraint
->v
->el
, i
);
681 if (is_div
< 0 || is_div
)
685 return isl_bool_false
;
688 /* Is "constraint" an equality that corresponds to integer division "div"?
690 * That is, given an integer division of the form
692 * a = floor((f + c)/m)
694 * is the equality of the form
698 * Note that the constant term is not checked explicitly, but given
699 * that this is a valid equality constraint, the constant c' necessarily
700 * has a value close to -c.
702 isl_bool
isl_constraint_is_div_equality(__isl_keep isl_constraint
*constraint
,
707 equality
= isl_constraint_is_equality(constraint
);
708 if (equality
< 0 || !equality
)
710 return isl_local_space_is_div_equality(constraint
->ls
,
711 constraint
->v
->el
, div
);
714 /* We manually set ISL_BASIC_SET_FINAL instead of calling
715 * isl_basic_map_finalize because we want to keep the position
716 * of the divs and we therefore do not want to throw away redundant divs.
717 * This is arguably a bit fragile.
719 __isl_give isl_basic_map
*isl_basic_map_from_constraint(
720 __isl_take isl_constraint
*constraint
)
724 struct isl_basic_map
*bmap
;
731 ls
= isl_local_space_copy(constraint
->ls
);
732 bmap
= isl_basic_map_from_local_space(ls
);
733 bmap
= isl_basic_map_extend_constraints(bmap
, 1, 1);
734 if (isl_constraint_is_equality(constraint
)) {
735 k
= isl_basic_map_alloc_equality(bmap
);
741 k
= isl_basic_map_alloc_inequality(bmap
);
746 total
= isl_basic_map_dim(bmap
, isl_dim_all
);
749 isl_seq_cpy(c
, constraint
->v
->el
, 1 + total
);
750 isl_constraint_free(constraint
);
752 ISL_F_SET(bmap
, ISL_BASIC_SET_FINAL
);
755 isl_constraint_free(constraint
);
756 isl_basic_map_free(bmap
);
760 __isl_give isl_basic_set
*isl_basic_set_from_constraint(
761 __isl_take isl_constraint
*constraint
)
765 space
= isl_constraint_peek_space(constraint
);
766 if (isl_space_check_is_set(space
) < 0)
768 return bset_from_bmap(isl_basic_map_from_constraint(constraint
));
770 isl_constraint_free(constraint
);
774 /* Is the variable of "type" at position "pos" of "bmap" defined
775 * in terms of earlier dimensions through an equality?
777 * If so, and if c is not NULL, then return a copy of this equality in *c.
779 isl_bool
isl_basic_map_has_defining_equality(
780 __isl_keep isl_basic_map
*bmap
, enum isl_dim_type type
, int pos
,
781 __isl_give isl_constraint
**c
)
787 if (isl_basic_map_check_range(bmap
, type
, pos
, 1) < 0)
788 return isl_bool_error
;
789 offset
= isl_basic_map_offset(bmap
, type
);
790 total
= isl_basic_map_dim(bmap
, isl_dim_all
);
792 return isl_bool_error
;
793 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
794 if (isl_int_is_zero(bmap
->eq
[i
][offset
+ pos
]) ||
795 isl_seq_first_non_zero(bmap
->eq
[i
]+offset
+pos
+1,
796 1+total
-offset
-pos
-1) != -1)
799 *c
= isl_basic_map_constraint(isl_basic_map_copy(bmap
),
801 return isl_bool_true
;
803 return isl_bool_false
;
806 /* Is the variable of "type" at position "pos" of "bset" defined
807 * in terms of earlier dimensions through an equality?
809 * If so, and if c is not NULL, then return a copy of this equality in *c.
811 isl_bool
isl_basic_set_has_defining_equality(
812 __isl_keep isl_basic_set
*bset
, enum isl_dim_type type
, int pos
,
813 __isl_give isl_constraint
**c
)
815 return isl_basic_map_has_defining_equality(bset_to_bmap(bset
),
819 isl_bool
isl_basic_set_has_defining_inequalities(
820 struct isl_basic_set
*bset
, enum isl_dim_type type
, int pos
,
821 struct isl_constraint
**lower
,
822 struct isl_constraint
**upper
)
828 isl_int
**lower_line
, **upper_line
;
830 if (isl_basic_set_check_range(bset
, type
, pos
, 1) < 0)
831 return isl_bool_error
;
832 offset
= isl_basic_set_offset(bset
, type
);
833 total
= isl_basic_set_dim(bset
, isl_dim_all
);
835 return isl_bool_error
;
837 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
838 if (isl_int_is_zero(bset
->ineq
[i
][offset
+ pos
]))
840 if (isl_int_is_one(bset
->ineq
[i
][offset
+ pos
]))
842 if (isl_int_is_negone(bset
->ineq
[i
][offset
+ pos
]))
844 if (isl_seq_first_non_zero(bset
->ineq
[i
]+offset
+pos
+1,
845 1+total
-offset
-pos
-1) != -1)
847 for (j
= i
+ 1; j
< bset
->n_ineq
; ++j
) {
848 if (!isl_seq_is_neg(bset
->ineq
[i
]+1, bset
->ineq
[j
]+1,
851 isl_int_add(m
, bset
->ineq
[i
][0], bset
->ineq
[j
][0]);
852 if (isl_int_abs_ge(m
, bset
->ineq
[i
][offset
+pos
]))
855 if (isl_int_is_pos(bset
->ineq
[i
][offset
+pos
])) {
856 lower_line
= &bset
->ineq
[i
];
857 upper_line
= &bset
->ineq
[j
];
859 lower_line
= &bset
->ineq
[j
];
860 upper_line
= &bset
->ineq
[i
];
862 *lower
= isl_basic_set_constraint(
863 isl_basic_set_copy(bset
), lower_line
);
864 *upper
= isl_basic_set_constraint(
865 isl_basic_set_copy(bset
), upper_line
);
867 return isl_bool_true
;
873 return isl_bool_false
;
876 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
877 * (in "a" and "b"), add a constraint to "bset" that ensures that the
878 * bound implied by "a" is (strictly) larger than the bound implied by "b".
880 * If both constraints imply lower bounds, then this means that "a" is
881 * active in the result.
882 * If both constraints imply upper bounds, then this means that "b" is
883 * active in the result.
885 static __isl_give isl_basic_set
*add_larger_bound_constraint(
886 __isl_take isl_basic_set
*bset
, isl_int
*a
, isl_int
*b
,
887 unsigned abs_pos
, int strict
)
893 total
= isl_basic_set_dim(bset
, isl_dim_all
);
895 return isl_basic_set_free(bset
);
896 k
= isl_basic_set_alloc_inequality(bset
);
901 isl_int_neg(t
, b
[1 + abs_pos
]);
903 isl_seq_combine(bset
->ineq
[k
], t
, a
, a
[1 + abs_pos
], b
, 1 + abs_pos
);
904 isl_seq_combine(bset
->ineq
[k
] + 1 + abs_pos
,
905 t
, a
+ 1 + abs_pos
+ 1, a
[1 + abs_pos
], b
+ 1 + abs_pos
+ 1,
909 isl_int_sub_ui(bset
->ineq
[k
][0], bset
->ineq
[k
][0], 1);
915 isl_basic_set_free(bset
);
919 /* Add constraints to "context" that ensure that "u" is the smallest
920 * (and therefore active) upper bound on "abs_pos" in "bset" and return
921 * the resulting basic set.
923 static __isl_give isl_basic_set
*set_smallest_upper_bound(
924 __isl_keep isl_basic_set
*context
,
925 __isl_keep isl_basic_set
*bset
, unsigned abs_pos
, int n_upper
, int u
)
929 context
= isl_basic_set_copy(context
);
930 context
= isl_basic_set_cow(context
);
932 context
= isl_basic_set_extend_constraints(context
, 0, n_upper
- 1);
934 for (j
= 0; j
< bset
->n_ineq
; ++j
) {
937 if (!isl_int_is_neg(bset
->ineq
[j
][1 + abs_pos
]))
939 context
= add_larger_bound_constraint(context
,
940 bset
->ineq
[j
], bset
->ineq
[u
], abs_pos
, j
> u
);
943 context
= isl_basic_set_simplify(context
);
944 context
= isl_basic_set_finalize(context
);
949 /* Add constraints to "context" that ensure that "u" is the largest
950 * (and therefore active) upper bound on "abs_pos" in "bset" and return
951 * the resulting basic set.
953 static __isl_give isl_basic_set
*set_largest_lower_bound(
954 __isl_keep isl_basic_set
*context
,
955 __isl_keep isl_basic_set
*bset
, unsigned abs_pos
, int n_lower
, int l
)
959 context
= isl_basic_set_copy(context
);
960 context
= isl_basic_set_cow(context
);
962 context
= isl_basic_set_extend_constraints(context
, 0, n_lower
- 1);
964 for (j
= 0; j
< bset
->n_ineq
; ++j
) {
967 if (!isl_int_is_pos(bset
->ineq
[j
][1 + abs_pos
]))
969 context
= add_larger_bound_constraint(context
,
970 bset
->ineq
[l
], bset
->ineq
[j
], abs_pos
, j
> l
);
973 context
= isl_basic_set_simplify(context
);
974 context
= isl_basic_set_finalize(context
);
979 static isl_stat
foreach_upper_bound(__isl_keep isl_basic_set
*bset
,
980 enum isl_dim_type type
, unsigned abs_pos
,
981 __isl_take isl_basic_set
*context
, int n_upper
,
982 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
983 __isl_take isl_constraint
*upper
,
984 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
986 isl_basic_set
*context_i
;
987 isl_constraint
*upper
= NULL
;
990 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
991 if (isl_int_is_zero(bset
->ineq
[i
][1 + abs_pos
]))
994 context_i
= set_smallest_upper_bound(context
, bset
,
995 abs_pos
, n_upper
, i
);
996 if (isl_basic_set_is_empty(context_i
)) {
997 isl_basic_set_free(context_i
);
1000 upper
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1002 if (!upper
|| !context_i
)
1004 if (fn(NULL
, upper
, context_i
, user
) < 0)
1008 isl_basic_set_free(context
);
1010 if (i
< bset
->n_ineq
)
1011 return isl_stat_error
;
1015 isl_constraint_free(upper
);
1016 isl_basic_set_free(context_i
);
1017 isl_basic_set_free(context
);
1018 return isl_stat_error
;
1021 static isl_stat
foreach_lower_bound(__isl_keep isl_basic_set
*bset
,
1022 enum isl_dim_type type
, unsigned abs_pos
,
1023 __isl_take isl_basic_set
*context
, int n_lower
,
1024 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
1025 __isl_take isl_constraint
*upper
,
1026 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
1028 isl_basic_set
*context_i
;
1029 isl_constraint
*lower
= NULL
;
1032 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1033 if (isl_int_is_zero(bset
->ineq
[i
][1 + abs_pos
]))
1036 context_i
= set_largest_lower_bound(context
, bset
,
1037 abs_pos
, n_lower
, i
);
1038 if (isl_basic_set_is_empty(context_i
)) {
1039 isl_basic_set_free(context_i
);
1042 lower
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1044 if (!lower
|| !context_i
)
1046 if (fn(lower
, NULL
, context_i
, user
) < 0)
1050 isl_basic_set_free(context
);
1052 if (i
< bset
->n_ineq
)
1053 return isl_stat_error
;
1057 isl_constraint_free(lower
);
1058 isl_basic_set_free(context_i
);
1059 isl_basic_set_free(context
);
1060 return isl_stat_error
;
1063 static isl_stat
foreach_bound_pair(__isl_keep isl_basic_set
*bset
,
1064 enum isl_dim_type type
, unsigned abs_pos
,
1065 __isl_take isl_basic_set
*context
, int n_lower
, int n_upper
,
1066 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
1067 __isl_take isl_constraint
*upper
,
1068 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
1070 isl_basic_set
*context_i
, *context_j
;
1071 isl_constraint
*lower
= NULL
;
1072 isl_constraint
*upper
= NULL
;
1075 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1076 if (!isl_int_is_pos(bset
->ineq
[i
][1 + abs_pos
]))
1079 context_i
= set_largest_lower_bound(context
, bset
,
1080 abs_pos
, n_lower
, i
);
1081 if (isl_basic_set_is_empty(context_i
)) {
1082 isl_basic_set_free(context_i
);
1086 for (j
= 0; j
< bset
->n_ineq
; ++j
) {
1087 if (!isl_int_is_neg(bset
->ineq
[j
][1 + abs_pos
]))
1090 context_j
= set_smallest_upper_bound(context_i
, bset
,
1091 abs_pos
, n_upper
, j
);
1092 context_j
= isl_basic_set_extend_constraints(context_j
,
1094 context_j
= add_larger_bound_constraint(context_j
,
1095 bset
->ineq
[i
], bset
->ineq
[j
], abs_pos
, 0);
1096 context_j
= isl_basic_set_simplify(context_j
);
1097 context_j
= isl_basic_set_finalize(context_j
);
1098 if (isl_basic_set_is_empty(context_j
)) {
1099 isl_basic_set_free(context_j
);
1102 lower
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1104 upper
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1106 if (!lower
|| !upper
|| !context_j
)
1108 if (fn(lower
, upper
, context_j
, user
) < 0)
1112 isl_basic_set_free(context_i
);
1114 if (j
< bset
->n_ineq
)
1118 isl_basic_set_free(context
);
1120 if (i
< bset
->n_ineq
)
1121 return isl_stat_error
;
1125 isl_constraint_free(lower
);
1126 isl_constraint_free(upper
);
1127 isl_basic_set_free(context_i
);
1128 isl_basic_set_free(context_j
);
1129 isl_basic_set_free(context
);
1130 return isl_stat_error
;
1133 /* For each pair of lower and upper bounds on the variable "pos"
1134 * of type "type", call "fn" with these lower and upper bounds and the
1135 * set of constraints on the remaining variables where these bounds
1136 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1138 * If the designated variable is equal to an affine combination of the
1139 * other variables then fn is called with both lower and upper
1140 * set to the corresponding equality.
1142 * If there is no lower (or upper) bound, then NULL is passed
1143 * as the corresponding bound.
1145 * We first check if the variable is involved in any equality.
1146 * If not, we count the number of lower and upper bounds and
1149 isl_stat
isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set
*bset
,
1150 enum isl_dim_type type
, unsigned pos
,
1151 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
1152 __isl_take isl_constraint
*upper
,
1153 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
1156 isl_constraint
*lower
= NULL
;
1157 isl_constraint
*upper
= NULL
;
1158 isl_basic_set
*context
= NULL
;
1160 int n_lower
, n_upper
;
1163 if (isl_basic_set_check_range(bset
, type
, pos
, 1) < 0)
1164 return isl_stat_error
;
1165 isl_assert(bset
->ctx
, type
== isl_dim_param
|| type
== isl_dim_set
,
1166 return isl_stat_error
);
1168 off
= isl_basic_set_var_offset(bset
, type
);
1170 return isl_stat_error
;
1171 abs_pos
= off
+ pos
;
1173 for (i
= 0; i
< bset
->n_eq
; ++i
) {
1174 if (isl_int_is_zero(bset
->eq
[i
][1 + abs_pos
]))
1177 lower
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1179 upper
= isl_constraint_copy(lower
);
1180 context
= isl_basic_set_remove_dims(isl_basic_set_copy(bset
),
1182 if (!lower
|| !upper
|| !context
)
1184 return fn(lower
, upper
, context
, user
);
1189 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1190 if (isl_int_is_pos(bset
->ineq
[i
][1 + abs_pos
]))
1192 else if (isl_int_is_neg(bset
->ineq
[i
][1 + abs_pos
]))
1196 context
= isl_basic_set_copy(bset
);
1197 context
= isl_basic_set_cow(context
);
1200 for (i
= context
->n_ineq
- 1; i
>= 0; --i
)
1201 if (!isl_int_is_zero(context
->ineq
[i
][1 + abs_pos
]))
1202 isl_basic_set_drop_inequality(context
, i
);
1204 context
= isl_basic_set_drop(context
, type
, pos
, 1);
1205 if (!n_lower
&& !n_upper
)
1206 return fn(NULL
, NULL
, context
, user
);
1208 return foreach_upper_bound(bset
, type
, abs_pos
, context
, n_upper
,
1211 return foreach_lower_bound(bset
, type
, abs_pos
, context
, n_lower
,
1213 return foreach_bound_pair(bset
, type
, abs_pos
, context
, n_lower
, n_upper
,
1216 isl_constraint_free(lower
);
1217 isl_constraint_free(upper
);
1218 isl_basic_set_free(context
);
1219 return isl_stat_error
;
1222 __isl_give isl_aff
*isl_constraint_get_bound(
1223 __isl_keep isl_constraint
*constraint
, enum isl_dim_type type
, int pos
)
1229 if (isl_constraint_check_range(constraint
, type
, pos
, 1) < 0)
1231 space
= isl_constraint_peek_space(constraint
);
1232 if (isl_space_check_is_set(space
) < 0)
1235 ctx
= isl_constraint_get_ctx(constraint
);
1236 pos
+= offset(constraint
, type
);
1237 if (isl_int_is_zero(constraint
->v
->el
[pos
]))
1238 isl_die(ctx
, isl_error_invalid
,
1239 "constraint does not define a bound on given dimension",
1242 aff
= isl_aff_alloc(isl_local_space_copy(constraint
->ls
));
1246 if (isl_int_is_neg(constraint
->v
->el
[pos
]))
1247 isl_seq_cpy(aff
->v
->el
+ 1, constraint
->v
->el
, aff
->v
->size
- 1);
1249 isl_seq_neg(aff
->v
->el
+ 1, constraint
->v
->el
, aff
->v
->size
- 1);
1250 isl_int_set_si(aff
->v
->el
[1 + pos
], 0);
1251 isl_int_abs(aff
->v
->el
[0], constraint
->v
->el
[pos
]);
1256 /* For an inequality constraint
1260 * or an equality constraint
1264 * return the affine expression f.
1266 __isl_give isl_aff
*isl_constraint_get_aff(
1267 __isl_keep isl_constraint
*constraint
)
1274 aff
= isl_aff_alloc(isl_local_space_copy(constraint
->ls
));
1278 isl_seq_cpy(aff
->v
->el
+ 1, constraint
->v
->el
, aff
->v
->size
- 1);
1279 isl_int_set_si(aff
->v
->el
[0], 1);
1284 /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1285 * In particular, construct aff >= 0 or aff = 0.
1287 * The denominator of "aff" can be ignored.
1289 static __isl_give isl_constraint
*isl_constraint_alloc_aff(int eq
,
1290 __isl_take isl_aff
*aff
)
1292 isl_local_space
*ls
;
1297 ls
= isl_aff_get_domain_local_space(aff
);
1298 v
= isl_vec_drop_els(isl_vec_copy(aff
->v
), 0, 1);
1301 return isl_constraint_alloc_vec(eq
, ls
, v
);
1304 /* Construct an equality constraint equating the given affine expression
1307 __isl_give isl_constraint
*isl_equality_from_aff(__isl_take isl_aff
*aff
)
1309 return isl_constraint_alloc_aff(1, aff
);
1312 /* Construct an inequality constraint enforcing the given affine expression
1313 * to be non-negative.
1315 __isl_give isl_constraint
*isl_inequality_from_aff(__isl_take isl_aff
*aff
)
1317 return isl_constraint_alloc_aff(0, aff
);
1320 /* Compare two isl_constraints.
1322 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1323 * than "c2" and 0 if they are equal.
1325 * The order is fairly arbitrary. We do consider constraints that only involve
1326 * earlier dimensions as "smaller".
1328 int isl_constraint_plain_cmp(__isl_keep isl_constraint
*c1
,
1329 __isl_keep isl_constraint
*c2
)
1340 cmp
= isl_local_space_cmp(c1
->ls
, c2
->ls
);
1344 last1
= isl_seq_last_non_zero(c1
->v
->el
+ 1, c1
->v
->size
- 1);
1345 last2
= isl_seq_last_non_zero(c2
->v
->el
+ 1, c1
->v
->size
- 1);
1347 return last1
- last2
;
1349 return isl_seq_cmp(c1
->v
->el
, c2
->v
->el
, c1
->v
->size
);
1352 /* Compare two constraints based on their final (non-zero) coefficients.
1353 * In particular, the constraint that involves later variables or
1354 * that has a larger coefficient for a shared latest variable
1355 * is considered "greater" than the other constraint.
1357 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1358 * than "c2" and 0 if they are equal.
1360 * If the constraints live in different local spaces, then we cannot
1361 * really compare the constraints so we compare the local spaces instead.
1363 int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint
*c1
,
1364 __isl_keep isl_constraint
*c2
)
1375 cmp
= isl_local_space_cmp(c1
->ls
, c2
->ls
);
1379 last1
= isl_seq_last_non_zero(c1
->v
->el
+ 1, c1
->v
->size
- 1);
1380 last2
= isl_seq_last_non_zero(c2
->v
->el
+ 1, c1
->v
->size
- 1);
1382 return last1
- last2
;
1385 return isl_int_abs_cmp(c1
->v
->el
[1 + last1
], c2
->v
->el
[1 + last2
]);