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 unsigned 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
)
78 ctx
= isl_local_space_get_ctx(ls
);
79 v
= isl_vec_alloc(ctx
, 1 + isl_local_space_dim(ls
, isl_dim_all
));
81 return isl_constraint_alloc_vec(eq
, ls
, v
);
84 struct isl_constraint
*isl_basic_map_constraint(struct isl_basic_map
*bmap
,
90 isl_local_space
*ls
= NULL
;
91 isl_constraint
*constraint
;
96 eq
= line
>= bmap
->eq
;
98 ctx
= isl_basic_map_get_ctx(bmap
);
99 ls
= isl_basic_map_get_local_space(bmap
);
100 v
= isl_vec_alloc(ctx
, 1 + isl_local_space_dim(ls
, isl_dim_all
));
103 isl_seq_cpy(v
->el
, line
[0], v
->size
);
104 constraint
= isl_constraint_alloc_vec(eq
, ls
, v
);
106 isl_basic_map_free(bmap
);
109 isl_local_space_free(ls
);
110 isl_basic_map_free(bmap
);
114 struct isl_constraint
*isl_basic_set_constraint(struct isl_basic_set
*bset
,
117 return isl_basic_map_constraint(bset_to_bmap(bset
), line
);
120 __isl_give isl_constraint
*isl_constraint_alloc_equality(
121 __isl_take isl_local_space
*ls
)
123 return isl_constraint_alloc(1, ls
);
126 __isl_give isl_constraint
*isl_constraint_alloc_inequality(
127 __isl_take isl_local_space
*ls
)
129 return isl_constraint_alloc(0, ls
);
132 struct isl_constraint
*isl_constraint_dup(struct isl_constraint
*c
)
137 return isl_constraint_alloc_vec(c
->eq
, isl_local_space_copy(c
->ls
),
141 struct isl_constraint
*isl_constraint_cow(struct isl_constraint
*c
)
149 return isl_constraint_dup(c
);
152 struct isl_constraint
*isl_constraint_copy(struct isl_constraint
*constraint
)
161 __isl_null isl_constraint
*isl_constraint_free(__isl_take isl_constraint
*c
)
169 isl_local_space_free(c
->ls
);
176 /* Return the number of constraints in "bmap", i.e., the
177 * number of times isl_basic_map_foreach_constraint will
180 int isl_basic_map_n_constraint(__isl_keep isl_basic_map
*bmap
)
185 return bmap
->n_eq
+ bmap
->n_ineq
;
188 /* Return the number of constraints in "bset", i.e., the
189 * number of times isl_basic_set_foreach_constraint will
192 int isl_basic_set_n_constraint(__isl_keep isl_basic_set
*bset
)
194 return isl_basic_map_n_constraint(bset
);
197 isl_stat
isl_basic_map_foreach_constraint(__isl_keep isl_basic_map
*bmap
,
198 isl_stat (*fn
)(__isl_take isl_constraint
*c
, void *user
), void *user
)
201 struct isl_constraint
*c
;
204 return isl_stat_error
;
206 isl_assert(bmap
->ctx
, ISL_F_ISSET(bmap
, ISL_BASIC_MAP_FINAL
),
207 return isl_stat_error
);
209 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
210 c
= isl_basic_map_constraint(isl_basic_map_copy(bmap
),
213 return isl_stat_error
;
215 return isl_stat_error
;
218 for (i
= 0; i
< bmap
->n_ineq
; ++i
) {
219 c
= isl_basic_map_constraint(isl_basic_map_copy(bmap
),
222 return isl_stat_error
;
224 return isl_stat_error
;
230 isl_stat
isl_basic_set_foreach_constraint(__isl_keep isl_basic_set
*bset
,
231 isl_stat (*fn
)(__isl_take isl_constraint
*c
, void *user
), void *user
)
233 return isl_basic_map_foreach_constraint(bset_to_bmap(bset
), fn
, user
);
236 /* Add the constraint to the list that "user" points to, if it is not
239 static isl_stat
collect_constraint(__isl_take isl_constraint
*constraint
,
242 isl_constraint_list
**list
= user
;
244 if (isl_constraint_is_div_constraint(constraint
))
245 isl_constraint_free(constraint
);
247 *list
= isl_constraint_list_add(*list
, constraint
);
252 /* Return a list of constraints that, when combined, are equivalent
253 * to "bmap". The input is required to have only known divs.
255 * There is no need to include the div constraints as they are
256 * implied by the div expressions.
258 __isl_give isl_constraint_list
*isl_basic_map_get_constraint_list(
259 __isl_keep isl_basic_map
*bmap
)
264 isl_constraint_list
*list
;
266 known
= isl_basic_map_divs_known(bmap
);
269 ctx
= isl_basic_map_get_ctx(bmap
);
271 isl_die(ctx
, isl_error_invalid
,
272 "input involves unknown divs", return NULL
);
274 n
= isl_basic_map_n_constraint(bmap
);
275 list
= isl_constraint_list_alloc(ctx
, n
);
276 if (isl_basic_map_foreach_constraint(bmap
,
277 &collect_constraint
, &list
) < 0)
278 list
= isl_constraint_list_free(list
);
283 /* Return a list of constraints that, when combined, are equivalent
284 * to "bset". The input is required to have only known divs.
286 __isl_give isl_constraint_list
*isl_basic_set_get_constraint_list(
287 __isl_keep isl_basic_set
*bset
)
289 return isl_basic_map_get_constraint_list(bset
);
292 int isl_constraint_is_equal(struct isl_constraint
*constraint1
,
293 struct isl_constraint
*constraint2
)
297 if (!constraint1
|| !constraint2
)
299 if (constraint1
->eq
!= constraint2
->eq
)
301 equal
= isl_local_space_is_equal(constraint1
->ls
, constraint2
->ls
);
302 if (equal
< 0 || !equal
)
304 return isl_vec_is_equal(constraint1
->v
, constraint2
->v
);
307 struct isl_basic_map
*isl_basic_map_add_constraint(
308 struct isl_basic_map
*bmap
, struct isl_constraint
*constraint
)
314 if (!bmap
|| !constraint
)
317 ctx
= isl_constraint_get_ctx(constraint
);
318 space
= isl_constraint_get_space(constraint
);
319 equal_space
= isl_space_is_equal(bmap
->dim
, space
);
320 isl_space_free(space
);
321 isl_assert(ctx
, equal_space
, goto error
);
323 bmap
= isl_basic_map_intersect(bmap
,
324 isl_basic_map_from_constraint(constraint
));
327 isl_basic_map_free(bmap
);
328 isl_constraint_free(constraint
);
332 struct isl_basic_set
*isl_basic_set_add_constraint(
333 struct isl_basic_set
*bset
, struct isl_constraint
*constraint
)
335 return bset_from_bmap(isl_basic_map_add_constraint(bset_to_bmap(bset
),
339 __isl_give isl_map
*isl_map_add_constraint(__isl_take isl_map
*map
,
340 __isl_take isl_constraint
*constraint
)
344 bmap
= isl_basic_map_from_constraint(constraint
);
345 map
= isl_map_intersect(map
, isl_map_from_basic_map(bmap
));
350 __isl_give isl_set
*isl_set_add_constraint(__isl_take isl_set
*set
,
351 __isl_take isl_constraint
*constraint
)
353 return isl_map_add_constraint(set
, constraint
);
356 /* Return the space of "constraint".
358 static __isl_keep isl_space
*isl_constraint_peek_space(
359 __isl_keep isl_constraint
*constraint
)
361 return constraint
? isl_local_space_peek_space(constraint
->ls
) : NULL
;
364 __isl_give isl_space
*isl_constraint_get_space(
365 __isl_keep isl_constraint
*constraint
)
367 return constraint
? isl_local_space_get_space(constraint
->ls
) : NULL
;
370 __isl_give isl_local_space
*isl_constraint_get_local_space(
371 __isl_keep isl_constraint
*constraint
)
373 return constraint
? isl_local_space_copy(constraint
->ls
) : NULL
;
376 int isl_constraint_dim(__isl_keep isl_constraint
*constraint
,
377 enum isl_dim_type type
)
381 return n(constraint
, type
);
384 isl_bool
isl_constraint_involves_dims(__isl_keep isl_constraint
*constraint
,
385 enum isl_dim_type type
, unsigned first
, unsigned n
)
390 isl_bool involves
= isl_bool_false
;
393 return isl_bool_error
;
395 return isl_bool_false
;
397 ctx
= isl_constraint_get_ctx(constraint
);
398 if (first
+ n
> isl_constraint_dim(constraint
, type
))
399 isl_die(ctx
, isl_error_invalid
,
400 "range out of bounds", return isl_bool_error
);
402 active
= isl_local_space_get_active(constraint
->ls
,
403 constraint
->v
->el
+ 1);
407 first
+= isl_local_space_offset(constraint
->ls
, type
) - 1;
408 for (i
= 0; i
< n
; ++i
)
409 if (active
[first
+ i
]) {
410 involves
= isl_bool_true
;
419 return isl_bool_error
;
422 /* Does the given constraint represent a lower bound on the given
425 isl_bool
isl_constraint_is_lower_bound(__isl_keep isl_constraint
*constraint
,
426 enum isl_dim_type type
, unsigned pos
)
429 return isl_bool_error
;
431 if (pos
>= isl_local_space_dim(constraint
->ls
, type
))
432 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
433 "position out of bounds", return isl_bool_error
);
435 pos
+= isl_local_space_offset(constraint
->ls
, type
);
436 return isl_int_is_pos(constraint
->v
->el
[pos
]);
439 /* Does the given constraint represent an upper bound on the given
442 isl_bool
isl_constraint_is_upper_bound(__isl_keep isl_constraint
*constraint
,
443 enum isl_dim_type type
, unsigned pos
)
446 return isl_bool_error
;
448 if (pos
>= isl_local_space_dim(constraint
->ls
, type
))
449 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
450 "position out of bounds", return isl_bool_error
);
452 pos
+= isl_local_space_offset(constraint
->ls
, type
);
453 return isl_int_is_neg(constraint
->v
->el
[pos
]);
456 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint
*constraint
,
457 enum isl_dim_type type
, unsigned pos
)
460 isl_local_space_get_dim_name(constraint
->ls
, type
, pos
) : NULL
;
463 void isl_constraint_get_constant(__isl_keep isl_constraint
*constraint
,
468 isl_int_set(*v
, constraint
->v
->el
[0]);
471 /* Return the constant term of "constraint".
473 __isl_give isl_val
*isl_constraint_get_constant_val(
474 __isl_keep isl_constraint
*constraint
)
481 ctx
= isl_constraint_get_ctx(constraint
);
482 return isl_val_int_from_isl_int(ctx
, constraint
->v
->el
[0]);
485 void isl_constraint_get_coefficient(struct isl_constraint
*constraint
,
486 enum isl_dim_type type
, int pos
, isl_int
*v
)
491 if (pos
>= isl_local_space_dim(constraint
->ls
, type
))
492 isl_die(constraint
->v
->ctx
, isl_error_invalid
,
493 "position out of bounds", return);
495 pos
+= isl_local_space_offset(constraint
->ls
, type
);
496 isl_int_set(*v
, constraint
->v
->el
[pos
]);
499 /* Return the coefficient of the variable of type "type" at position "pos"
502 __isl_give isl_val
*isl_constraint_get_coefficient_val(
503 __isl_keep isl_constraint
*constraint
, enum isl_dim_type type
, int pos
)
510 ctx
= isl_constraint_get_ctx(constraint
);
511 if (pos
< 0 || pos
>= isl_local_space_dim(constraint
->ls
, type
))
512 isl_die(ctx
, isl_error_invalid
,
513 "position out of bounds", return NULL
);
515 pos
+= isl_local_space_offset(constraint
->ls
, type
);
516 return isl_val_int_from_isl_int(ctx
, constraint
->v
->el
[pos
]);
519 __isl_give isl_aff
*isl_constraint_get_div(__isl_keep isl_constraint
*constraint
,
525 return isl_local_space_get_div(constraint
->ls
, pos
);
528 __isl_give isl_constraint
*isl_constraint_set_constant(
529 __isl_take isl_constraint
*constraint
, isl_int v
)
531 constraint
= isl_constraint_cow(constraint
);
535 constraint
->v
= isl_vec_cow(constraint
->v
);
537 return isl_constraint_free(constraint
);
539 isl_int_set(constraint
->v
->el
[0], v
);
543 /* Replace the constant term of "constraint" by "v".
545 __isl_give isl_constraint
*isl_constraint_set_constant_val(
546 __isl_take isl_constraint
*constraint
, __isl_take isl_val
*v
)
548 constraint
= isl_constraint_cow(constraint
);
549 if (!constraint
|| !v
)
551 if (!isl_val_is_int(v
))
552 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
553 "expecting integer value", goto error
);
554 constraint
->v
= isl_vec_set_element_val(constraint
->v
, 0, v
);
556 constraint
= isl_constraint_free(constraint
);
560 return isl_constraint_free(constraint
);
563 __isl_give isl_constraint
*isl_constraint_set_constant_si(
564 __isl_take isl_constraint
*constraint
, int v
)
566 constraint
= isl_constraint_cow(constraint
);
570 constraint
->v
= isl_vec_cow(constraint
->v
);
572 return isl_constraint_free(constraint
);
574 isl_int_set_si(constraint
->v
->el
[0], v
);
578 __isl_give isl_constraint
*isl_constraint_set_coefficient(
579 __isl_take isl_constraint
*constraint
,
580 enum isl_dim_type type
, int pos
, isl_int v
)
582 constraint
= isl_constraint_cow(constraint
);
586 if (pos
>= isl_local_space_dim(constraint
->ls
, type
))
587 isl_die(constraint
->v
->ctx
, isl_error_invalid
,
588 "position out of bounds",
589 return isl_constraint_free(constraint
));
591 constraint
->v
= isl_vec_cow(constraint
->v
);
593 return isl_constraint_free(constraint
);
595 pos
+= isl_local_space_offset(constraint
->ls
, type
);
596 isl_int_set(constraint
->v
->el
[pos
], v
);
601 /* Replace the coefficient of the variable of type "type" at position "pos"
602 * of "constraint" by "v".
604 __isl_give isl_constraint
*isl_constraint_set_coefficient_val(
605 __isl_take isl_constraint
*constraint
,
606 enum isl_dim_type type
, int pos
, __isl_take isl_val
*v
)
608 constraint
= isl_constraint_cow(constraint
);
609 if (!constraint
|| !v
)
611 if (!isl_val_is_int(v
))
612 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
613 "expecting integer value", goto error
);
615 if (pos
>= isl_local_space_dim(constraint
->ls
, type
))
616 isl_die(isl_constraint_get_ctx(constraint
), isl_error_invalid
,
617 "position out of bounds", goto error
);
619 pos
+= isl_local_space_offset(constraint
->ls
, type
);
620 constraint
->v
= isl_vec_set_element_val(constraint
->v
, pos
, v
);
622 constraint
= isl_constraint_free(constraint
);
626 return isl_constraint_free(constraint
);
629 __isl_give isl_constraint
*isl_constraint_set_coefficient_si(
630 __isl_take isl_constraint
*constraint
,
631 enum isl_dim_type type
, int pos
, int v
)
633 constraint
= isl_constraint_cow(constraint
);
637 if (pos
>= isl_local_space_dim(constraint
->ls
, type
))
638 isl_die(constraint
->v
->ctx
, isl_error_invalid
,
639 "position out of bounds",
640 return isl_constraint_free(constraint
));
642 constraint
->v
= isl_vec_cow(constraint
->v
);
644 return isl_constraint_free(constraint
);
646 pos
+= isl_local_space_offset(constraint
->ls
, type
);
647 isl_int_set_si(constraint
->v
->el
[pos
], v
);
652 struct isl_constraint
*isl_constraint_negate(struct isl_constraint
*constraint
)
656 constraint
= isl_constraint_cow(constraint
);
660 ctx
= isl_constraint_get_ctx(constraint
);
661 if (isl_constraint_is_equality(constraint
))
662 isl_die(ctx
, isl_error_invalid
, "cannot negate equality",
663 return isl_constraint_free(constraint
));
664 constraint
->v
= isl_vec_neg(constraint
->v
);
665 constraint
->v
= isl_vec_cow(constraint
->v
);
667 return isl_constraint_free(constraint
);
668 isl_int_sub_ui(constraint
->v
->el
[0], constraint
->v
->el
[0], 1);
672 isl_bool
isl_constraint_is_equality(struct isl_constraint
*constraint
)
675 return isl_bool_error
;
676 return constraint
->eq
;
679 int isl_constraint_is_div_constraint(__isl_keep isl_constraint
*constraint
)
686 if (isl_constraint_is_equality(constraint
))
688 n_div
= isl_constraint_dim(constraint
, isl_dim_div
);
689 for (i
= 0; i
< n_div
; ++i
) {
691 is_div
= isl_local_space_is_div_constraint(constraint
->ls
,
692 constraint
->v
->el
, i
);
693 if (is_div
< 0 || is_div
)
700 /* Is "constraint" an equality that corresponds to integer division "div"?
702 * That is, given an integer division of the form
704 * a = floor((f + c)/m)
706 * is the equality of the form
710 * Note that the constant term is not checked explicitly, but given
711 * that this is a valid equality constraint, the constant c' necessarily
712 * has a value close to -c.
714 isl_bool
isl_constraint_is_div_equality(__isl_keep isl_constraint
*constraint
,
719 equality
= isl_constraint_is_equality(constraint
);
720 if (equality
< 0 || !equality
)
722 return isl_local_space_is_div_equality(constraint
->ls
,
723 constraint
->v
->el
, div
);
726 /* We manually set ISL_BASIC_SET_FINAL instead of calling
727 * isl_basic_map_finalize because we want to keep the position
728 * of the divs and we therefore do not want to throw away redundant divs.
729 * This is arguably a bit fragile.
731 __isl_give isl_basic_map
*isl_basic_map_from_constraint(
732 __isl_take isl_constraint
*constraint
)
736 struct isl_basic_map
*bmap
;
743 ls
= isl_local_space_copy(constraint
->ls
);
744 bmap
= isl_basic_map_from_local_space(ls
);
745 bmap
= isl_basic_map_extend_constraints(bmap
, 1, 1);
746 if (isl_constraint_is_equality(constraint
)) {
747 k
= isl_basic_map_alloc_equality(bmap
);
753 k
= isl_basic_map_alloc_inequality(bmap
);
758 total
= isl_basic_map_total_dim(bmap
);
759 isl_seq_cpy(c
, constraint
->v
->el
, 1 + total
);
760 isl_constraint_free(constraint
);
762 ISL_F_SET(bmap
, ISL_BASIC_SET_FINAL
);
765 isl_constraint_free(constraint
);
766 isl_basic_map_free(bmap
);
770 __isl_give isl_basic_set
*isl_basic_set_from_constraint(
771 __isl_take isl_constraint
*constraint
)
775 space
= isl_constraint_peek_space(constraint
);
776 if (isl_space_check_is_set(space
) < 0)
778 return bset_from_bmap(isl_basic_map_from_constraint(constraint
));
780 isl_constraint_free(constraint
);
784 /* Is the variable of "type" at position "pos" of "bmap" defined
785 * in terms of earlier dimensions through an equality?
787 * If so, and if c is not NULL, then return a copy of this equality in *c.
789 isl_bool
isl_basic_map_has_defining_equality(
790 __isl_keep isl_basic_map
*bmap
, enum isl_dim_type type
, int pos
,
791 __isl_give isl_constraint
**c
)
797 if (isl_basic_map_check_range(bmap
, type
, pos
, 1) < 0)
798 return isl_bool_error
;
799 offset
= isl_basic_map_offset(bmap
, type
);
800 total
= isl_basic_map_total_dim(bmap
);
801 for (i
= 0; i
< bmap
->n_eq
; ++i
) {
802 if (isl_int_is_zero(bmap
->eq
[i
][offset
+ pos
]) ||
803 isl_seq_first_non_zero(bmap
->eq
[i
]+offset
+pos
+1,
804 1+total
-offset
-pos
-1) != -1)
807 *c
= isl_basic_map_constraint(isl_basic_map_copy(bmap
),
809 return isl_bool_true
;
811 return isl_bool_false
;
814 /* Is the variable of "type" at position "pos" of "bset" defined
815 * in terms of earlier dimensions through an equality?
817 * If so, and if c is not NULL, then return a copy of this equality in *c.
819 isl_bool
isl_basic_set_has_defining_equality(
820 __isl_keep isl_basic_set
*bset
, enum isl_dim_type type
, int pos
,
821 __isl_give isl_constraint
**c
)
823 return isl_basic_map_has_defining_equality(bset_to_bmap(bset
),
827 isl_bool
isl_basic_set_has_defining_inequalities(
828 struct isl_basic_set
*bset
, enum isl_dim_type type
, int pos
,
829 struct isl_constraint
**lower
,
830 struct isl_constraint
**upper
)
836 isl_int
**lower_line
, **upper_line
;
839 return isl_bool_error
;
840 offset
= isl_basic_set_offset(bset
, type
);
841 total
= isl_basic_set_total_dim(bset
);
842 if (pos
>= isl_basic_set_dim(bset
, type
))
843 isl_die(isl_basic_set_get_ctx(bset
), isl_error_invalid
,
844 "invalid position", return isl_bool_error
);
846 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
847 if (isl_int_is_zero(bset
->ineq
[i
][offset
+ pos
]))
849 if (isl_int_is_one(bset
->ineq
[i
][offset
+ pos
]))
851 if (isl_int_is_negone(bset
->ineq
[i
][offset
+ pos
]))
853 if (isl_seq_first_non_zero(bset
->ineq
[i
]+offset
+pos
+1,
854 1+total
-offset
-pos
-1) != -1)
856 for (j
= i
+ 1; j
< bset
->n_ineq
; ++j
) {
857 if (!isl_seq_is_neg(bset
->ineq
[i
]+1, bset
->ineq
[j
]+1,
860 isl_int_add(m
, bset
->ineq
[i
][0], bset
->ineq
[j
][0]);
861 if (isl_int_abs_ge(m
, bset
->ineq
[i
][offset
+pos
]))
864 if (isl_int_is_pos(bset
->ineq
[i
][offset
+pos
])) {
865 lower_line
= &bset
->ineq
[i
];
866 upper_line
= &bset
->ineq
[j
];
868 lower_line
= &bset
->ineq
[j
];
869 upper_line
= &bset
->ineq
[i
];
871 *lower
= isl_basic_set_constraint(
872 isl_basic_set_copy(bset
), lower_line
);
873 *upper
= isl_basic_set_constraint(
874 isl_basic_set_copy(bset
), upper_line
);
876 return isl_bool_true
;
882 return isl_bool_false
;
885 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
886 * (in "a" and "b"), add a constraint to "bset" that ensures that the
887 * bound implied by "a" is (strictly) larger than the bound implied by "b".
889 * If both constraints imply lower bounds, then this means that "a" is
890 * active in the result.
891 * If both constraints imply upper bounds, then this means that "b" is
892 * active in the result.
894 static __isl_give isl_basic_set
*add_larger_bound_constraint(
895 __isl_take isl_basic_set
*bset
, isl_int
*a
, isl_int
*b
,
896 unsigned abs_pos
, int strict
)
902 k
= isl_basic_set_alloc_inequality(bset
);
906 total
= isl_basic_set_dim(bset
, isl_dim_all
);
909 isl_int_neg(t
, b
[1 + abs_pos
]);
911 isl_seq_combine(bset
->ineq
[k
], t
, a
, a
[1 + abs_pos
], b
, 1 + abs_pos
);
912 isl_seq_combine(bset
->ineq
[k
] + 1 + abs_pos
,
913 t
, a
+ 1 + abs_pos
+ 1, a
[1 + abs_pos
], b
+ 1 + abs_pos
+ 1,
917 isl_int_sub_ui(bset
->ineq
[k
][0], bset
->ineq
[k
][0], 1);
923 isl_basic_set_free(bset
);
927 /* Add constraints to "context" that ensure that "u" is the smallest
928 * (and therefore active) upper bound on "abs_pos" in "bset" and return
929 * the resulting basic set.
931 static __isl_give isl_basic_set
*set_smallest_upper_bound(
932 __isl_keep isl_basic_set
*context
,
933 __isl_keep isl_basic_set
*bset
, unsigned abs_pos
, int n_upper
, int u
)
937 context
= isl_basic_set_copy(context
);
938 context
= isl_basic_set_cow(context
);
940 context
= isl_basic_set_extend_constraints(context
, 0, n_upper
- 1);
942 for (j
= 0; j
< bset
->n_ineq
; ++j
) {
945 if (!isl_int_is_neg(bset
->ineq
[j
][1 + abs_pos
]))
947 context
= add_larger_bound_constraint(context
,
948 bset
->ineq
[j
], bset
->ineq
[u
], abs_pos
, j
> u
);
951 context
= isl_basic_set_simplify(context
);
952 context
= isl_basic_set_finalize(context
);
957 /* Add constraints to "context" that ensure that "u" is the largest
958 * (and therefore active) upper bound on "abs_pos" in "bset" and return
959 * the resulting basic set.
961 static __isl_give isl_basic_set
*set_largest_lower_bound(
962 __isl_keep isl_basic_set
*context
,
963 __isl_keep isl_basic_set
*bset
, unsigned abs_pos
, int n_lower
, int l
)
967 context
= isl_basic_set_copy(context
);
968 context
= isl_basic_set_cow(context
);
970 context
= isl_basic_set_extend_constraints(context
, 0, n_lower
- 1);
972 for (j
= 0; j
< bset
->n_ineq
; ++j
) {
975 if (!isl_int_is_pos(bset
->ineq
[j
][1 + abs_pos
]))
977 context
= add_larger_bound_constraint(context
,
978 bset
->ineq
[l
], bset
->ineq
[j
], abs_pos
, j
> l
);
981 context
= isl_basic_set_simplify(context
);
982 context
= isl_basic_set_finalize(context
);
987 static isl_stat
foreach_upper_bound(__isl_keep isl_basic_set
*bset
,
988 enum isl_dim_type type
, unsigned abs_pos
,
989 __isl_take isl_basic_set
*context
, int n_upper
,
990 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
991 __isl_take isl_constraint
*upper
,
992 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
994 isl_basic_set
*context_i
;
995 isl_constraint
*upper
= NULL
;
998 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
999 if (isl_int_is_zero(bset
->ineq
[i
][1 + abs_pos
]))
1002 context_i
= set_smallest_upper_bound(context
, bset
,
1003 abs_pos
, n_upper
, i
);
1004 if (isl_basic_set_is_empty(context_i
)) {
1005 isl_basic_set_free(context_i
);
1008 upper
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1010 if (!upper
|| !context_i
)
1012 if (fn(NULL
, upper
, context_i
, user
) < 0)
1016 isl_basic_set_free(context
);
1018 if (i
< bset
->n_ineq
)
1019 return isl_stat_error
;
1023 isl_constraint_free(upper
);
1024 isl_basic_set_free(context_i
);
1025 isl_basic_set_free(context
);
1026 return isl_stat_error
;
1029 static isl_stat
foreach_lower_bound(__isl_keep isl_basic_set
*bset
,
1030 enum isl_dim_type type
, unsigned abs_pos
,
1031 __isl_take isl_basic_set
*context
, int n_lower
,
1032 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
1033 __isl_take isl_constraint
*upper
,
1034 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
1036 isl_basic_set
*context_i
;
1037 isl_constraint
*lower
= NULL
;
1040 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1041 if (isl_int_is_zero(bset
->ineq
[i
][1 + abs_pos
]))
1044 context_i
= set_largest_lower_bound(context
, bset
,
1045 abs_pos
, n_lower
, i
);
1046 if (isl_basic_set_is_empty(context_i
)) {
1047 isl_basic_set_free(context_i
);
1050 lower
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1052 if (!lower
|| !context_i
)
1054 if (fn(lower
, NULL
, context_i
, user
) < 0)
1058 isl_basic_set_free(context
);
1060 if (i
< bset
->n_ineq
)
1061 return isl_stat_error
;
1065 isl_constraint_free(lower
);
1066 isl_basic_set_free(context_i
);
1067 isl_basic_set_free(context
);
1068 return isl_stat_error
;
1071 static isl_stat
foreach_bound_pair(__isl_keep isl_basic_set
*bset
,
1072 enum isl_dim_type type
, unsigned abs_pos
,
1073 __isl_take isl_basic_set
*context
, int n_lower
, int n_upper
,
1074 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
1075 __isl_take isl_constraint
*upper
,
1076 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
1078 isl_basic_set
*context_i
, *context_j
;
1079 isl_constraint
*lower
= NULL
;
1080 isl_constraint
*upper
= NULL
;
1083 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1084 if (!isl_int_is_pos(bset
->ineq
[i
][1 + abs_pos
]))
1087 context_i
= set_largest_lower_bound(context
, bset
,
1088 abs_pos
, n_lower
, i
);
1089 if (isl_basic_set_is_empty(context_i
)) {
1090 isl_basic_set_free(context_i
);
1094 for (j
= 0; j
< bset
->n_ineq
; ++j
) {
1095 if (!isl_int_is_neg(bset
->ineq
[j
][1 + abs_pos
]))
1098 context_j
= set_smallest_upper_bound(context_i
, bset
,
1099 abs_pos
, n_upper
, j
);
1100 context_j
= isl_basic_set_extend_constraints(context_j
,
1102 context_j
= add_larger_bound_constraint(context_j
,
1103 bset
->ineq
[i
], bset
->ineq
[j
], abs_pos
, 0);
1104 context_j
= isl_basic_set_simplify(context_j
);
1105 context_j
= isl_basic_set_finalize(context_j
);
1106 if (isl_basic_set_is_empty(context_j
)) {
1107 isl_basic_set_free(context_j
);
1110 lower
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1112 upper
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1114 if (!lower
|| !upper
|| !context_j
)
1116 if (fn(lower
, upper
, context_j
, user
) < 0)
1120 isl_basic_set_free(context_i
);
1122 if (j
< bset
->n_ineq
)
1126 isl_basic_set_free(context
);
1128 if (i
< bset
->n_ineq
)
1129 return isl_stat_error
;
1133 isl_constraint_free(lower
);
1134 isl_constraint_free(upper
);
1135 isl_basic_set_free(context_i
);
1136 isl_basic_set_free(context_j
);
1137 isl_basic_set_free(context
);
1138 return isl_stat_error
;
1141 /* For each pair of lower and upper bounds on the variable "pos"
1142 * of type "type", call "fn" with these lower and upper bounds and the
1143 * set of constraints on the remaining variables where these bounds
1144 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1146 * If the designated variable is equal to an affine combination of the
1147 * other variables then fn is called with both lower and upper
1148 * set to the corresponding equality.
1150 * If there is no lower (or upper) bound, then NULL is passed
1151 * as the corresponding bound.
1153 * We first check if the variable is involved in any equality.
1154 * If not, we count the number of lower and upper bounds and
1157 isl_stat
isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set
*bset
,
1158 enum isl_dim_type type
, unsigned pos
,
1159 isl_stat (*fn
)(__isl_take isl_constraint
*lower
,
1160 __isl_take isl_constraint
*upper
,
1161 __isl_take isl_basic_set
*bset
, void *user
), void *user
)
1164 isl_constraint
*lower
= NULL
;
1165 isl_constraint
*upper
= NULL
;
1166 isl_basic_set
*context
= NULL
;
1168 int n_lower
, n_upper
;
1171 return isl_stat_error
;
1172 isl_assert(bset
->ctx
, pos
< isl_basic_set_dim(bset
, type
),
1173 return isl_stat_error
);
1174 isl_assert(bset
->ctx
, type
== isl_dim_param
|| type
== isl_dim_set
,
1175 return isl_stat_error
);
1178 if (type
== isl_dim_set
)
1179 abs_pos
+= isl_basic_set_dim(bset
, isl_dim_param
);
1181 for (i
= 0; i
< bset
->n_eq
; ++i
) {
1182 if (isl_int_is_zero(bset
->eq
[i
][1 + abs_pos
]))
1185 lower
= isl_basic_set_constraint(isl_basic_set_copy(bset
),
1187 upper
= isl_constraint_copy(lower
);
1188 context
= isl_basic_set_remove_dims(isl_basic_set_copy(bset
),
1190 if (!lower
|| !upper
|| !context
)
1192 return fn(lower
, upper
, context
, user
);
1197 for (i
= 0; i
< bset
->n_ineq
; ++i
) {
1198 if (isl_int_is_pos(bset
->ineq
[i
][1 + abs_pos
]))
1200 else if (isl_int_is_neg(bset
->ineq
[i
][1 + abs_pos
]))
1204 context
= isl_basic_set_copy(bset
);
1205 context
= isl_basic_set_cow(context
);
1208 for (i
= context
->n_ineq
- 1; i
>= 0; --i
)
1209 if (!isl_int_is_zero(context
->ineq
[i
][1 + abs_pos
]))
1210 isl_basic_set_drop_inequality(context
, i
);
1212 context
= isl_basic_set_drop(context
, type
, pos
, 1);
1213 if (!n_lower
&& !n_upper
)
1214 return fn(NULL
, NULL
, context
, user
);
1216 return foreach_upper_bound(bset
, type
, abs_pos
, context
, n_upper
,
1219 return foreach_lower_bound(bset
, type
, abs_pos
, context
, n_lower
,
1221 return foreach_bound_pair(bset
, type
, abs_pos
, context
, n_lower
, n_upper
,
1224 isl_constraint_free(lower
);
1225 isl_constraint_free(upper
);
1226 isl_basic_set_free(context
);
1227 return isl_stat_error
;
1230 __isl_give isl_aff
*isl_constraint_get_bound(
1231 __isl_keep isl_constraint
*constraint
, enum isl_dim_type type
, int pos
)
1239 ctx
= isl_constraint_get_ctx(constraint
);
1240 if (pos
>= isl_constraint_dim(constraint
, type
))
1241 isl_die(ctx
, isl_error_invalid
,
1242 "index out of bounds", return NULL
);
1243 space
= isl_constraint_peek_space(constraint
);
1244 if (isl_space_check_is_set(space
) < 0)
1247 pos
+= offset(constraint
, type
);
1248 if (isl_int_is_zero(constraint
->v
->el
[pos
]))
1249 isl_die(ctx
, isl_error_invalid
,
1250 "constraint does not define a bound on given dimension",
1253 aff
= isl_aff_alloc(isl_local_space_copy(constraint
->ls
));
1257 if (isl_int_is_neg(constraint
->v
->el
[pos
]))
1258 isl_seq_cpy(aff
->v
->el
+ 1, constraint
->v
->el
, aff
->v
->size
- 1);
1260 isl_seq_neg(aff
->v
->el
+ 1, constraint
->v
->el
, aff
->v
->size
- 1);
1261 isl_int_set_si(aff
->v
->el
[1 + pos
], 0);
1262 isl_int_abs(aff
->v
->el
[0], constraint
->v
->el
[pos
]);
1267 /* For an inequality constraint
1271 * or an equality constraint
1275 * return the affine expression f.
1277 __isl_give isl_aff
*isl_constraint_get_aff(
1278 __isl_keep isl_constraint
*constraint
)
1285 aff
= isl_aff_alloc(isl_local_space_copy(constraint
->ls
));
1289 isl_seq_cpy(aff
->v
->el
+ 1, constraint
->v
->el
, aff
->v
->size
- 1);
1290 isl_int_set_si(aff
->v
->el
[0], 1);
1295 /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1296 * In particular, construct aff >= 0 or aff = 0.
1298 * The denominator of "aff" can be ignored.
1300 static __isl_give isl_constraint
*isl_constraint_alloc_aff(int eq
,
1301 __isl_take isl_aff
*aff
)
1303 isl_local_space
*ls
;
1308 ls
= isl_aff_get_domain_local_space(aff
);
1309 v
= isl_vec_drop_els(isl_vec_copy(aff
->v
), 0, 1);
1312 return isl_constraint_alloc_vec(eq
, ls
, v
);
1315 /* Construct an equality constraint equating the given affine expression
1318 __isl_give isl_constraint
*isl_equality_from_aff(__isl_take isl_aff
*aff
)
1320 return isl_constraint_alloc_aff(1, aff
);
1323 /* Construct an inequality constraint enforcing the given affine expression
1324 * to be non-negative.
1326 __isl_give isl_constraint
*isl_inequality_from_aff(__isl_take isl_aff
*aff
)
1328 return isl_constraint_alloc_aff(0, aff
);
1331 /* Compare two isl_constraints.
1333 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1334 * than "c2" and 0 if they are equal.
1336 * The order is fairly arbitrary. We do consider constraints that only involve
1337 * earlier dimensions as "smaller".
1339 int isl_constraint_plain_cmp(__isl_keep isl_constraint
*c1
,
1340 __isl_keep isl_constraint
*c2
)
1351 cmp
= isl_local_space_cmp(c1
->ls
, c2
->ls
);
1355 last1
= isl_seq_last_non_zero(c1
->v
->el
+ 1, c1
->v
->size
- 1);
1356 last2
= isl_seq_last_non_zero(c2
->v
->el
+ 1, c1
->v
->size
- 1);
1358 return last1
- last2
;
1360 return isl_seq_cmp(c1
->v
->el
, c2
->v
->el
, c1
->v
->size
);
1363 /* Compare two constraints based on their final (non-zero) coefficients.
1364 * In particular, the constraint that involves later variables or
1365 * that has a larger coefficient for a shared latest variable
1366 * is considered "greater" than the other constraint.
1368 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1369 * than "c2" and 0 if they are equal.
1371 * If the constraints live in different local spaces, then we cannot
1372 * really compare the constraints so we compare the local spaces instead.
1374 int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint
*c1
,
1375 __isl_keep isl_constraint
*c2
)
1386 cmp
= isl_local_space_cmp(c1
->ls
, c2
->ls
);
1390 last1
= isl_seq_last_non_zero(c1
->v
->el
+ 1, c1
->v
->size
- 1);
1391 last2
= isl_seq_last_non_zero(c2
->v
->el
+ 1, c1
->v
->size
- 1);
1393 return last1
- last2
;
1396 return isl_int_abs_cmp(c1
->v
->el
[1 + last1
], c2
->v
->el
[1 + last2
]);