drop C++ bindings
[isl.git] / isl_constraint.c
blobf1b0b4eefc4522955423fe50bf379614ed452390
1 /*
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>
16 #include <isl_seq.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>
25 #undef BASE
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 static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
46 enum isl_dim_type type)
48 return type == isl_dim_div ? 1 + isl_space_dim(bmap->dim, isl_dim_all)
49 : 1 + isl_space_offset(bmap->dim, type);
52 static unsigned basic_set_offset(struct isl_basic_set *bset,
53 enum isl_dim_type type)
55 isl_space *dim = bset->dim;
56 switch (type) {
57 case isl_dim_param: return 1;
58 case isl_dim_in: return 1 + dim->nparam;
59 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
60 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
61 default: return 0;
65 __isl_give isl_constraint *isl_constraint_alloc_vec(int eq,
66 __isl_take isl_local_space *ls, __isl_take isl_vec *v)
68 isl_constraint *constraint;
70 if (!ls || !v)
71 goto error;
73 constraint = isl_alloc_type(isl_vec_get_ctx(v), isl_constraint);
74 if (!constraint)
75 goto error;
77 constraint->ref = 1;
78 constraint->eq = eq;
79 constraint->ls = ls;
80 constraint->v = v;
82 return constraint;
83 error:
84 isl_local_space_free(ls);
85 isl_vec_free(v);
86 return NULL;
89 __isl_give isl_constraint *isl_constraint_alloc(int eq,
90 __isl_take isl_local_space *ls)
92 isl_ctx *ctx;
93 isl_vec *v;
95 if (!ls)
96 return NULL;
98 ctx = isl_local_space_get_ctx(ls);
99 v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
100 v = isl_vec_clr(v);
101 return isl_constraint_alloc_vec(eq, ls, v);
104 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
105 isl_int **line)
107 int eq;
108 isl_ctx *ctx;
109 isl_vec *v;
110 isl_local_space *ls = NULL;
111 isl_constraint *constraint;
113 if (!bmap || !line)
114 goto error;
116 eq = line >= bmap->eq;
118 ctx = isl_basic_map_get_ctx(bmap);
119 ls = isl_basic_map_get_local_space(bmap);
120 v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
121 if (!v)
122 goto error;
123 isl_seq_cpy(v->el, line[0], v->size);
124 constraint = isl_constraint_alloc_vec(eq, ls, v);
126 isl_basic_map_free(bmap);
127 return constraint;
128 error:
129 isl_local_space_free(ls);
130 isl_basic_map_free(bmap);
131 return NULL;
134 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
135 isl_int **line)
137 return isl_basic_map_constraint(bset_to_bmap(bset), line);
140 __isl_give isl_constraint *isl_constraint_alloc_equality(
141 __isl_take isl_local_space *ls)
143 return isl_constraint_alloc(1, ls);
146 __isl_give isl_constraint *isl_constraint_alloc_inequality(
147 __isl_take isl_local_space *ls)
149 return isl_constraint_alloc(0, ls);
152 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
154 if (!c)
155 return NULL;
157 return isl_constraint_alloc_vec(c->eq, isl_local_space_copy(c->ls),
158 isl_vec_copy(c->v));
161 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
163 if (!c)
164 return NULL;
166 if (c->ref == 1)
167 return c;
168 c->ref--;
169 return isl_constraint_dup(c);
172 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
174 if (!constraint)
175 return NULL;
177 constraint->ref++;
178 return constraint;
181 __isl_null isl_constraint *isl_constraint_free(__isl_take isl_constraint *c)
183 if (!c)
184 return NULL;
186 if (--c->ref > 0)
187 return NULL;
189 isl_local_space_free(c->ls);
190 isl_vec_free(c->v);
191 free(c);
193 return NULL;
196 /* Return the number of constraints in "bmap", i.e., the
197 * number of times isl_basic_map_foreach_constraint will
198 * call the callback.
200 int isl_basic_map_n_constraint(__isl_keep isl_basic_map *bmap)
202 if (!bmap)
203 return -1;
205 return bmap->n_eq + bmap->n_ineq;
208 /* Return the number of constraints in "bset", i.e., the
209 * number of times isl_basic_set_foreach_constraint will
210 * call the callback.
212 int isl_basic_set_n_constraint(__isl_keep isl_basic_set *bset)
214 return isl_basic_map_n_constraint(bset);
217 isl_stat isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
218 isl_stat (*fn)(__isl_take isl_constraint *c, void *user), void *user)
220 int i;
221 struct isl_constraint *c;
223 if (!bmap)
224 return isl_stat_error;
226 isl_assert(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),
227 return isl_stat_error);
229 for (i = 0; i < bmap->n_eq; ++i) {
230 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
231 &bmap->eq[i]);
232 if (!c)
233 return isl_stat_error;
234 if (fn(c, user) < 0)
235 return isl_stat_error;
238 for (i = 0; i < bmap->n_ineq; ++i) {
239 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
240 &bmap->ineq[i]);
241 if (!c)
242 return isl_stat_error;
243 if (fn(c, user) < 0)
244 return isl_stat_error;
247 return isl_stat_ok;
250 isl_stat isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
251 isl_stat (*fn)(__isl_take isl_constraint *c, void *user), void *user)
253 return isl_basic_map_foreach_constraint(bset_to_bmap(bset), fn, user);
256 /* Add the constraint to the list that "user" points to, if it is not
257 * a div constraint.
259 static isl_stat collect_constraint(__isl_take isl_constraint *constraint,
260 void *user)
262 isl_constraint_list **list = user;
264 if (isl_constraint_is_div_constraint(constraint))
265 isl_constraint_free(constraint);
266 else
267 *list = isl_constraint_list_add(*list, constraint);
269 return isl_stat_ok;
272 /* Return a list of constraints that, when combined, are equivalent
273 * to "bmap". The input is required to have only known divs.
275 * There is no need to include the div constraints as they are
276 * implied by the div expressions.
278 __isl_give isl_constraint_list *isl_basic_map_get_constraint_list(
279 __isl_keep isl_basic_map *bmap)
281 int n;
282 int known;
283 isl_ctx *ctx;
284 isl_constraint_list *list;
286 known = isl_basic_map_divs_known(bmap);
287 if (known < 0)
288 return NULL;
289 ctx = isl_basic_map_get_ctx(bmap);
290 if (!known)
291 isl_die(ctx, isl_error_invalid,
292 "input involves unknown divs", return NULL);
294 n = isl_basic_map_n_constraint(bmap);
295 list = isl_constraint_list_alloc(ctx, n);
296 if (isl_basic_map_foreach_constraint(bmap,
297 &collect_constraint, &list) < 0)
298 list = isl_constraint_list_free(list);
300 return list;
303 /* Return a list of constraints that, when combined, are equivalent
304 * to "bset". The input is required to have only known divs.
306 __isl_give isl_constraint_list *isl_basic_set_get_constraint_list(
307 __isl_keep isl_basic_set *bset)
309 return isl_basic_map_get_constraint_list(bset);
312 int isl_constraint_is_equal(struct isl_constraint *constraint1,
313 struct isl_constraint *constraint2)
315 int equal;
317 if (!constraint1 || !constraint2)
318 return 0;
319 if (constraint1->eq != constraint2->eq)
320 return 0;
321 equal = isl_local_space_is_equal(constraint1->ls, constraint2->ls);
322 if (equal < 0 || !equal)
323 return equal;
324 return isl_vec_is_equal(constraint1->v, constraint2->v);
327 struct isl_basic_map *isl_basic_map_add_constraint(
328 struct isl_basic_map *bmap, struct isl_constraint *constraint)
330 isl_ctx *ctx;
331 isl_space *dim;
332 int equal_space;
334 if (!bmap || !constraint)
335 goto error;
337 ctx = isl_constraint_get_ctx(constraint);
338 dim = isl_constraint_get_space(constraint);
339 equal_space = isl_space_is_equal(bmap->dim, dim);
340 isl_space_free(dim);
341 isl_assert(ctx, equal_space, goto error);
343 bmap = isl_basic_map_intersect(bmap,
344 isl_basic_map_from_constraint(constraint));
345 return bmap;
346 error:
347 isl_basic_map_free(bmap);
348 isl_constraint_free(constraint);
349 return NULL;
352 struct isl_basic_set *isl_basic_set_add_constraint(
353 struct isl_basic_set *bset, struct isl_constraint *constraint)
355 return bset_from_bmap(isl_basic_map_add_constraint(bset_to_bmap(bset),
356 constraint));
359 __isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map,
360 __isl_take isl_constraint *constraint)
362 isl_basic_map *bmap;
364 bmap = isl_basic_map_from_constraint(constraint);
365 map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
367 return map;
370 __isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set,
371 __isl_take isl_constraint *constraint)
373 return isl_map_add_constraint(set, constraint);
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 int isl_constraint_dim(struct isl_constraint *constraint,
389 enum isl_dim_type type)
391 if (!constraint)
392 return -1;
393 return n(constraint, type);
396 isl_bool isl_constraint_involves_dims(__isl_keep isl_constraint *constraint,
397 enum isl_dim_type type, unsigned first, unsigned n)
399 int i;
400 isl_ctx *ctx;
401 int *active = NULL;
402 isl_bool involves = isl_bool_false;
404 if (!constraint)
405 return isl_bool_error;
406 if (n == 0)
407 return isl_bool_false;
409 ctx = isl_constraint_get_ctx(constraint);
410 if (first + n > isl_constraint_dim(constraint, type))
411 isl_die(ctx, isl_error_invalid,
412 "range out of bounds", return isl_bool_error);
414 active = isl_local_space_get_active(constraint->ls,
415 constraint->v->el + 1);
416 if (!active)
417 goto error;
419 first += isl_local_space_offset(constraint->ls, type) - 1;
420 for (i = 0; i < n; ++i)
421 if (active[first + i]) {
422 involves = isl_bool_true;
423 break;
426 free(active);
428 return involves;
429 error:
430 free(active);
431 return isl_bool_error;
434 /* Does the given constraint represent a lower bound on the given
435 * dimension?
437 isl_bool isl_constraint_is_lower_bound(__isl_keep isl_constraint *constraint,
438 enum isl_dim_type type, unsigned pos)
440 if (!constraint)
441 return isl_bool_error;
443 if (pos >= isl_local_space_dim(constraint->ls, type))
444 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
445 "position out of bounds", return isl_bool_error);
447 pos += isl_local_space_offset(constraint->ls, type);
448 return isl_int_is_pos(constraint->v->el[pos]);
451 /* Does the given constraint represent an upper bound on the given
452 * dimension?
454 isl_bool isl_constraint_is_upper_bound(__isl_keep isl_constraint *constraint,
455 enum isl_dim_type type, unsigned pos)
457 if (!constraint)
458 return isl_bool_error;
460 if (pos >= isl_local_space_dim(constraint->ls, type))
461 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
462 "position out of bounds", return isl_bool_error);
464 pos += isl_local_space_offset(constraint->ls, type);
465 return isl_int_is_neg(constraint->v->el[pos]);
468 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
469 enum isl_dim_type type, unsigned pos)
471 return constraint ?
472 isl_local_space_get_dim_name(constraint->ls, type, pos) : NULL;
475 void isl_constraint_get_constant(__isl_keep isl_constraint *constraint,
476 isl_int *v)
478 if (!constraint)
479 return;
480 isl_int_set(*v, constraint->v->el[0]);
483 /* Return the constant term of "constraint".
485 __isl_give isl_val *isl_constraint_get_constant_val(
486 __isl_keep isl_constraint *constraint)
488 isl_ctx *ctx;
490 if (!constraint)
491 return NULL;
493 ctx = isl_constraint_get_ctx(constraint);
494 return isl_val_int_from_isl_int(ctx, constraint->v->el[0]);
497 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
498 enum isl_dim_type type, int pos, isl_int *v)
500 if (!constraint)
501 return;
503 if (pos >= isl_local_space_dim(constraint->ls, type))
504 isl_die(constraint->v->ctx, isl_error_invalid,
505 "position out of bounds", return);
507 pos += isl_local_space_offset(constraint->ls, type);
508 isl_int_set(*v, constraint->v->el[pos]);
511 /* Return the coefficient of the variable of type "type" at position "pos"
512 * of "constraint".
514 __isl_give isl_val *isl_constraint_get_coefficient_val(
515 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
517 isl_ctx *ctx;
519 if (!constraint)
520 return NULL;
522 ctx = isl_constraint_get_ctx(constraint);
523 if (pos < 0 || pos >= isl_local_space_dim(constraint->ls, type))
524 isl_die(ctx, isl_error_invalid,
525 "position out of bounds", return NULL);
527 pos += isl_local_space_offset(constraint->ls, type);
528 return isl_val_int_from_isl_int(ctx, constraint->v->el[pos]);
531 __isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint,
532 int pos)
534 if (!constraint)
535 return NULL;
537 return isl_local_space_get_div(constraint->ls, pos);
540 __isl_give isl_constraint *isl_constraint_set_constant(
541 __isl_take isl_constraint *constraint, isl_int v)
543 constraint = isl_constraint_cow(constraint);
544 if (!constraint)
545 return NULL;
547 constraint->v = isl_vec_cow(constraint->v);
548 if (!constraint->v)
549 return isl_constraint_free(constraint);
551 isl_int_set(constraint->v->el[0], v);
552 return constraint;
555 /* Replace the constant term of "constraint" by "v".
557 __isl_give isl_constraint *isl_constraint_set_constant_val(
558 __isl_take isl_constraint *constraint, __isl_take isl_val *v)
560 constraint = isl_constraint_cow(constraint);
561 if (!constraint || !v)
562 goto error;
563 if (!isl_val_is_int(v))
564 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
565 "expecting integer value", goto error);
566 constraint->v = isl_vec_set_element_val(constraint->v, 0, v);
567 if (!constraint->v)
568 constraint = isl_constraint_free(constraint);
569 return constraint;
570 error:
571 isl_val_free(v);
572 return isl_constraint_free(constraint);
575 __isl_give isl_constraint *isl_constraint_set_constant_si(
576 __isl_take isl_constraint *constraint, int v)
578 constraint = isl_constraint_cow(constraint);
579 if (!constraint)
580 return NULL;
582 constraint->v = isl_vec_cow(constraint->v);
583 if (!constraint->v)
584 return isl_constraint_free(constraint);
586 isl_int_set_si(constraint->v->el[0], v);
587 return constraint;
590 __isl_give isl_constraint *isl_constraint_set_coefficient(
591 __isl_take isl_constraint *constraint,
592 enum isl_dim_type type, int pos, isl_int v)
594 constraint = isl_constraint_cow(constraint);
595 if (!constraint)
596 return NULL;
598 if (pos >= isl_local_space_dim(constraint->ls, type))
599 isl_die(constraint->v->ctx, isl_error_invalid,
600 "position out of bounds",
601 return isl_constraint_free(constraint));
603 constraint = isl_constraint_cow(constraint);
604 if (!constraint)
605 return NULL;
607 constraint->v = isl_vec_cow(constraint->v);
608 if (!constraint->v)
609 return isl_constraint_free(constraint);
611 pos += isl_local_space_offset(constraint->ls, type);
612 isl_int_set(constraint->v->el[pos], v);
614 return constraint;
617 /* Replace the coefficient of the variable of type "type" at position "pos"
618 * of "constraint" by "v".
620 __isl_give isl_constraint *isl_constraint_set_coefficient_val(
621 __isl_take isl_constraint *constraint,
622 enum isl_dim_type type, int pos, __isl_take isl_val *v)
624 constraint = isl_constraint_cow(constraint);
625 if (!constraint || !v)
626 goto error;
627 if (!isl_val_is_int(v))
628 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
629 "expecting integer value", goto error);
631 if (pos >= isl_local_space_dim(constraint->ls, type))
632 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
633 "position out of bounds", goto error);
635 pos += isl_local_space_offset(constraint->ls, type);
636 constraint->v = isl_vec_set_element_val(constraint->v, pos, v);
637 if (!constraint->v)
638 constraint = isl_constraint_free(constraint);
639 return constraint;
640 error:
641 isl_val_free(v);
642 return isl_constraint_free(constraint);
645 __isl_give isl_constraint *isl_constraint_set_coefficient_si(
646 __isl_take isl_constraint *constraint,
647 enum isl_dim_type type, int pos, int v)
649 constraint = isl_constraint_cow(constraint);
650 if (!constraint)
651 return NULL;
653 if (pos >= isl_local_space_dim(constraint->ls, type))
654 isl_die(constraint->v->ctx, isl_error_invalid,
655 "position out of bounds",
656 return isl_constraint_free(constraint));
658 constraint = isl_constraint_cow(constraint);
659 if (!constraint)
660 return NULL;
662 constraint->v = isl_vec_cow(constraint->v);
663 if (!constraint->v)
664 return isl_constraint_free(constraint);
666 pos += isl_local_space_offset(constraint->ls, type);
667 isl_int_set_si(constraint->v->el[pos], v);
669 return constraint;
672 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
674 isl_ctx *ctx;
676 constraint = isl_constraint_cow(constraint);
677 if (!constraint)
678 return NULL;
680 ctx = isl_constraint_get_ctx(constraint);
681 if (isl_constraint_is_equality(constraint))
682 isl_die(ctx, isl_error_invalid, "cannot negate equality",
683 return isl_constraint_free(constraint));
684 constraint->v = isl_vec_neg(constraint->v);
685 constraint->v = isl_vec_cow(constraint->v);
686 if (!constraint->v)
687 return isl_constraint_free(constraint);
688 isl_int_sub_ui(constraint->v->el[0], constraint->v->el[0], 1);
689 return constraint;
692 isl_bool isl_constraint_is_equality(struct isl_constraint *constraint)
694 if (!constraint)
695 return isl_bool_error;
696 return constraint->eq;
699 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
701 int i;
702 int n_div;
704 if (!constraint)
705 return -1;
706 if (isl_constraint_is_equality(constraint))
707 return 0;
708 n_div = isl_constraint_dim(constraint, isl_dim_div);
709 for (i = 0; i < n_div; ++i) {
710 isl_bool is_div;
711 is_div = isl_local_space_is_div_constraint(constraint->ls,
712 constraint->v->el, i);
713 if (is_div < 0 || is_div)
714 return is_div;
717 return 0;
720 /* We manually set ISL_BASIC_SET_FINAL instead of calling
721 * isl_basic_map_finalize because we want to keep the position
722 * of the divs and we therefore do not want to throw away redundant divs.
723 * This is arguably a bit fragile.
725 __isl_give isl_basic_map *isl_basic_map_from_constraint(
726 __isl_take isl_constraint *constraint)
728 int k;
729 isl_local_space *ls;
730 struct isl_basic_map *bmap;
731 isl_int *c;
732 unsigned total;
734 if (!constraint)
735 return NULL;
737 ls = isl_local_space_copy(constraint->ls);
738 bmap = isl_basic_map_from_local_space(ls);
739 bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
740 if (isl_constraint_is_equality(constraint)) {
741 k = isl_basic_map_alloc_equality(bmap);
742 if (k < 0)
743 goto error;
744 c = bmap->eq[k];
746 else {
747 k = isl_basic_map_alloc_inequality(bmap);
748 if (k < 0)
749 goto error;
750 c = bmap->ineq[k];
752 total = isl_basic_map_total_dim(bmap);
753 isl_seq_cpy(c, constraint->v->el, 1 + total);
754 isl_constraint_free(constraint);
755 if (bmap)
756 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
757 return bmap;
758 error:
759 isl_constraint_free(constraint);
760 isl_basic_map_free(bmap);
761 return NULL;
764 __isl_give isl_basic_set *isl_basic_set_from_constraint(
765 __isl_take isl_constraint *constraint)
767 if (!constraint)
768 return NULL;
770 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
771 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
772 "not a set constraint", goto error);
773 return bset_from_bmap(isl_basic_map_from_constraint(constraint));
774 error:
775 isl_constraint_free(constraint);
776 return NULL;
779 /* Is the variable of "type" at position "pos" of "bmap" defined
780 * in terms of earlier dimensions through an equality?
782 * If so, and if c is not NULL, then return a copy of this equality in *c.
784 isl_bool isl_basic_map_has_defining_equality(
785 __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
786 __isl_give isl_constraint **c)
788 int i;
789 unsigned offset;
790 unsigned total;
792 if (!bmap)
793 return isl_bool_error;
794 offset = basic_map_offset(bmap, type);
795 total = isl_basic_map_total_dim(bmap);
796 if (pos >= isl_basic_map_dim(bmap, type))
797 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
798 "invalid position", return isl_bool_error);
799 for (i = 0; i < bmap->n_eq; ++i) {
800 if (isl_int_is_zero(bmap->eq[i][offset + pos]) ||
801 isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
802 1+total-offset-pos-1) != -1)
803 continue;
804 if (c)
805 *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
806 &bmap->eq[i]);
807 return isl_bool_true;
809 return isl_bool_false;
812 /* Is the variable of "type" at position "pos" of "bset" defined
813 * in terms of earlier dimensions through an equality?
815 * If so, and if c is not NULL, then return a copy of this equality in *c.
817 isl_bool isl_basic_set_has_defining_equality(
818 __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
819 __isl_give isl_constraint **c)
821 return isl_basic_map_has_defining_equality(bset_to_bmap(bset),
822 type, pos, c);
825 isl_bool isl_basic_set_has_defining_inequalities(
826 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
827 struct isl_constraint **lower,
828 struct isl_constraint **upper)
830 int i, j;
831 unsigned offset;
832 unsigned total;
833 isl_int m;
834 isl_int **lower_line, **upper_line;
836 if (!bset)
837 return isl_bool_error;
838 offset = basic_set_offset(bset, type);
839 total = isl_basic_set_total_dim(bset);
840 if (pos >= isl_basic_set_dim(bset, type))
841 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
842 "invalid position", return isl_bool_error);
843 isl_int_init(m);
844 for (i = 0; i < bset->n_ineq; ++i) {
845 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
846 continue;
847 if (isl_int_is_one(bset->ineq[i][offset + pos]))
848 continue;
849 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
850 continue;
851 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
852 1+total-offset-pos-1) != -1)
853 continue;
854 for (j = i + 1; j < bset->n_ineq; ++j) {
855 if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
856 total))
857 continue;
858 isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
859 if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
860 continue;
862 if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
863 lower_line = &bset->ineq[i];
864 upper_line = &bset->ineq[j];
865 } else {
866 lower_line = &bset->ineq[j];
867 upper_line = &bset->ineq[i];
869 *lower = isl_basic_set_constraint(
870 isl_basic_set_copy(bset), lower_line);
871 *upper = isl_basic_set_constraint(
872 isl_basic_set_copy(bset), upper_line);
873 isl_int_clear(m);
874 return isl_bool_true;
877 *lower = NULL;
878 *upper = NULL;
879 isl_int_clear(m);
880 return isl_bool_false;
883 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
884 * (in "a" and "b"), add a constraint to "bset" that ensures that the
885 * bound implied by "a" is (strictly) larger than the bound implied by "b".
887 * If both constraints imply lower bounds, then this means that "a" is
888 * active in the result.
889 * If both constraints imply upper bounds, then this means that "b" is
890 * active in the result.
892 static __isl_give isl_basic_set *add_larger_bound_constraint(
893 __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
894 unsigned abs_pos, int strict)
896 int k;
897 isl_int t;
898 unsigned total;
900 k = isl_basic_set_alloc_inequality(bset);
901 if (k < 0)
902 goto error;
904 total = isl_basic_set_dim(bset, isl_dim_all);
906 isl_int_init(t);
907 isl_int_neg(t, b[1 + abs_pos]);
909 isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
910 isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
911 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
912 total - abs_pos);
914 if (strict)
915 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
917 isl_int_clear(t);
919 return bset;
920 error:
921 isl_basic_set_free(bset);
922 return NULL;
925 /* Add constraints to "context" that ensure that "u" is the smallest
926 * (and therefore active) upper bound on "abs_pos" in "bset" and return
927 * the resulting basic set.
929 static __isl_give isl_basic_set *set_smallest_upper_bound(
930 __isl_keep isl_basic_set *context,
931 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
933 int j;
935 context = isl_basic_set_copy(context);
936 context = isl_basic_set_cow(context);
938 context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
940 for (j = 0; j < bset->n_ineq; ++j) {
941 if (j == u)
942 continue;
943 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
944 continue;
945 context = add_larger_bound_constraint(context,
946 bset->ineq[j], bset->ineq[u], abs_pos, j > u);
949 context = isl_basic_set_simplify(context);
950 context = isl_basic_set_finalize(context);
952 return context;
955 /* Add constraints to "context" that ensure that "u" is the largest
956 * (and therefore active) upper bound on "abs_pos" in "bset" and return
957 * the resulting basic set.
959 static __isl_give isl_basic_set *set_largest_lower_bound(
960 __isl_keep isl_basic_set *context,
961 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
963 int j;
965 context = isl_basic_set_copy(context);
966 context = isl_basic_set_cow(context);
968 context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
970 for (j = 0; j < bset->n_ineq; ++j) {
971 if (j == l)
972 continue;
973 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
974 continue;
975 context = add_larger_bound_constraint(context,
976 bset->ineq[l], bset->ineq[j], abs_pos, j > l);
979 context = isl_basic_set_simplify(context);
980 context = isl_basic_set_finalize(context);
982 return context;
985 static isl_stat foreach_upper_bound(__isl_keep isl_basic_set *bset,
986 enum isl_dim_type type, unsigned abs_pos,
987 __isl_take isl_basic_set *context, int n_upper,
988 isl_stat (*fn)(__isl_take isl_constraint *lower,
989 __isl_take isl_constraint *upper,
990 __isl_take isl_basic_set *bset, void *user), void *user)
992 isl_basic_set *context_i;
993 isl_constraint *upper = NULL;
994 int i;
996 for (i = 0; i < bset->n_ineq; ++i) {
997 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
998 continue;
1000 context_i = set_smallest_upper_bound(context, bset,
1001 abs_pos, n_upper, i);
1002 if (isl_basic_set_is_empty(context_i)) {
1003 isl_basic_set_free(context_i);
1004 continue;
1006 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1007 &bset->ineq[i]);
1008 if (!upper || !context_i)
1009 goto error;
1010 if (fn(NULL, upper, context_i, user) < 0)
1011 break;
1014 isl_basic_set_free(context);
1016 if (i < bset->n_ineq)
1017 return isl_stat_error;
1019 return isl_stat_ok;
1020 error:
1021 isl_constraint_free(upper);
1022 isl_basic_set_free(context_i);
1023 isl_basic_set_free(context);
1024 return isl_stat_error;
1027 static isl_stat foreach_lower_bound(__isl_keep isl_basic_set *bset,
1028 enum isl_dim_type type, unsigned abs_pos,
1029 __isl_take isl_basic_set *context, int n_lower,
1030 isl_stat (*fn)(__isl_take isl_constraint *lower,
1031 __isl_take isl_constraint *upper,
1032 __isl_take isl_basic_set *bset, void *user), void *user)
1034 isl_basic_set *context_i;
1035 isl_constraint *lower = NULL;
1036 int i;
1038 for (i = 0; i < bset->n_ineq; ++i) {
1039 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1040 continue;
1042 context_i = set_largest_lower_bound(context, bset,
1043 abs_pos, n_lower, i);
1044 if (isl_basic_set_is_empty(context_i)) {
1045 isl_basic_set_free(context_i);
1046 continue;
1048 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1049 &bset->ineq[i]);
1050 if (!lower || !context_i)
1051 goto error;
1052 if (fn(lower, NULL, context_i, user) < 0)
1053 break;
1056 isl_basic_set_free(context);
1058 if (i < bset->n_ineq)
1059 return isl_stat_error;
1061 return isl_stat_ok;
1062 error:
1063 isl_constraint_free(lower);
1064 isl_basic_set_free(context_i);
1065 isl_basic_set_free(context);
1066 return isl_stat_error;
1069 static isl_stat foreach_bound_pair(__isl_keep isl_basic_set *bset,
1070 enum isl_dim_type type, unsigned abs_pos,
1071 __isl_take isl_basic_set *context, int n_lower, int n_upper,
1072 isl_stat (*fn)(__isl_take isl_constraint *lower,
1073 __isl_take isl_constraint *upper,
1074 __isl_take isl_basic_set *bset, void *user), void *user)
1076 isl_basic_set *context_i, *context_j;
1077 isl_constraint *lower = NULL;
1078 isl_constraint *upper = NULL;
1079 int i, j;
1081 for (i = 0; i < bset->n_ineq; ++i) {
1082 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1083 continue;
1085 context_i = set_largest_lower_bound(context, bset,
1086 abs_pos, n_lower, i);
1087 if (isl_basic_set_is_empty(context_i)) {
1088 isl_basic_set_free(context_i);
1089 continue;
1092 for (j = 0; j < bset->n_ineq; ++j) {
1093 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1094 continue;
1096 context_j = set_smallest_upper_bound(context_i, bset,
1097 abs_pos, n_upper, j);
1098 context_j = isl_basic_set_extend_constraints(context_j,
1099 0, 1);
1100 context_j = add_larger_bound_constraint(context_j,
1101 bset->ineq[i], bset->ineq[j], abs_pos, 0);
1102 context_j = isl_basic_set_simplify(context_j);
1103 context_j = isl_basic_set_finalize(context_j);
1104 if (isl_basic_set_is_empty(context_j)) {
1105 isl_basic_set_free(context_j);
1106 continue;
1108 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1109 &bset->ineq[i]);
1110 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1111 &bset->ineq[j]);
1112 if (!lower || !upper || !context_j)
1113 goto error;
1114 if (fn(lower, upper, context_j, user) < 0)
1115 break;
1118 isl_basic_set_free(context_i);
1120 if (j < bset->n_ineq)
1121 break;
1124 isl_basic_set_free(context);
1126 if (i < bset->n_ineq)
1127 return isl_stat_error;
1129 return isl_stat_ok;
1130 error:
1131 isl_constraint_free(lower);
1132 isl_constraint_free(upper);
1133 isl_basic_set_free(context_i);
1134 isl_basic_set_free(context_j);
1135 isl_basic_set_free(context);
1136 return isl_stat_error;
1139 /* For each pair of lower and upper bounds on the variable "pos"
1140 * of type "type", call "fn" with these lower and upper bounds and the
1141 * set of constraints on the remaining variables where these bounds
1142 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1144 * If the designated variable is equal to an affine combination of the
1145 * other variables then fn is called with both lower and upper
1146 * set to the corresponding equality.
1148 * If there is no lower (or upper) bound, then NULL is passed
1149 * as the corresponding bound.
1151 * We first check if the variable is involved in any equality.
1152 * If not, we count the number of lower and upper bounds and
1153 * act accordingly.
1155 isl_stat isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
1156 enum isl_dim_type type, unsigned pos,
1157 isl_stat (*fn)(__isl_take isl_constraint *lower,
1158 __isl_take isl_constraint *upper,
1159 __isl_take isl_basic_set *bset, void *user), void *user)
1161 int i;
1162 isl_constraint *lower = NULL;
1163 isl_constraint *upper = NULL;
1164 isl_basic_set *context = NULL;
1165 unsigned abs_pos;
1166 int n_lower, n_upper;
1168 if (!bset)
1169 return isl_stat_error;
1170 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type),
1171 return isl_stat_error);
1172 isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
1173 return isl_stat_error);
1175 abs_pos = pos;
1176 if (type == isl_dim_set)
1177 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
1179 for (i = 0; i < bset->n_eq; ++i) {
1180 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
1181 continue;
1183 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1184 &bset->eq[i]);
1185 upper = isl_constraint_copy(lower);
1186 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
1187 type, pos, 1);
1188 if (!lower || !upper || !context)
1189 goto error;
1190 return fn(lower, upper, context, user);
1193 n_lower = 0;
1194 n_upper = 0;
1195 for (i = 0; i < bset->n_ineq; ++i) {
1196 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1197 n_lower++;
1198 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
1199 n_upper++;
1202 context = isl_basic_set_copy(bset);
1203 context = isl_basic_set_cow(context);
1204 if (!context)
1205 goto error;
1206 for (i = context->n_ineq - 1; i >= 0; --i)
1207 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
1208 isl_basic_set_drop_inequality(context, i);
1210 context = isl_basic_set_drop(context, type, pos, 1);
1211 if (!n_lower && !n_upper)
1212 return fn(NULL, NULL, context, user);
1213 if (!n_lower)
1214 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1215 fn, user);
1216 if (!n_upper)
1217 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
1218 fn, user);
1219 return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
1220 fn, user);
1221 error:
1222 isl_constraint_free(lower);
1223 isl_constraint_free(upper);
1224 isl_basic_set_free(context);
1225 return -1;
1228 __isl_give isl_aff *isl_constraint_get_bound(
1229 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1231 isl_aff *aff;
1232 isl_ctx *ctx;
1234 if (!constraint)
1235 return NULL;
1236 ctx = isl_constraint_get_ctx(constraint);
1237 if (pos >= isl_constraint_dim(constraint, type))
1238 isl_die(ctx, isl_error_invalid,
1239 "index out of bounds", return NULL);
1240 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
1241 isl_die(ctx, isl_error_invalid,
1242 "not a set constraint", return NULL);
1244 pos += offset(constraint, type);
1245 if (isl_int_is_zero(constraint->v->el[pos]))
1246 isl_die(ctx, isl_error_invalid,
1247 "constraint does not define a bound on given dimension",
1248 return NULL);
1250 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1251 if (!aff)
1252 return NULL;
1254 if (isl_int_is_neg(constraint->v->el[pos]))
1255 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1256 else
1257 isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1258 isl_int_set_si(aff->v->el[1 + pos], 0);
1259 isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1261 return aff;
1264 /* For an inequality constraint
1266 * f >= 0
1268 * or an equality constraint
1270 * f = 0
1272 * return the affine expression f.
1274 __isl_give isl_aff *isl_constraint_get_aff(
1275 __isl_keep isl_constraint *constraint)
1277 isl_aff *aff;
1279 if (!constraint)
1280 return NULL;
1282 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1283 if (!aff)
1284 return NULL;
1286 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1287 isl_int_set_si(aff->v->el[0], 1);
1289 return aff;
1292 /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1293 * In particular, construct aff >= 0 or aff = 0.
1295 * The denominator of "aff" can be ignored.
1297 static __isl_give isl_constraint *isl_constraint_alloc_aff(int eq,
1298 __isl_take isl_aff *aff)
1300 isl_local_space *ls;
1301 isl_vec *v;
1303 if (!aff)
1304 return NULL;
1305 ls = isl_aff_get_domain_local_space(aff);
1306 v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1307 isl_aff_free(aff);
1309 return isl_constraint_alloc_vec(eq, ls, v);
1312 /* Construct an equality constraint equating the given affine expression
1313 * to zero.
1315 __isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff)
1317 return isl_constraint_alloc_aff(1, aff);
1320 /* Construct an inequality constraint enforcing the given affine expression
1321 * to be non-negative.
1323 __isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff)
1325 return isl_constraint_alloc_aff(0, aff);
1328 /* Compare two isl_constraints.
1330 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1331 * than "c2" and 0 if they are equal.
1333 * The order is fairly arbitrary. We do consider constraints that only involve
1334 * earlier dimensions as "smaller".
1336 int isl_constraint_plain_cmp(__isl_keep isl_constraint *c1,
1337 __isl_keep isl_constraint *c2)
1339 int cmp;
1340 int last1, last2;
1342 if (c1 == c2)
1343 return 0;
1344 if (!c1)
1345 return -1;
1346 if (!c2)
1347 return 1;
1348 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1349 if (cmp != 0)
1350 return cmp;
1352 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1353 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1354 if (last1 != last2)
1355 return last1 - last2;
1357 return isl_seq_cmp(c1->v->el, c2->v->el, c1->v->size);
1360 /* Compare two constraints based on their final (non-zero) coefficients.
1361 * In particular, the constraint that involves later variables or
1362 * that has a larger coefficient for a shared latest variable
1363 * is considered "greater" than the other constraint.
1365 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1366 * than "c2" and 0 if they are equal.
1368 * If the constraints live in different local spaces, then we cannot
1369 * really compare the constraints so we compare the local spaces instead.
1371 int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint *c1,
1372 __isl_keep isl_constraint *c2)
1374 int cmp;
1375 int last1, last2;
1377 if (c1 == c2)
1378 return 0;
1379 if (!c1)
1380 return -1;
1381 if (!c2)
1382 return 1;
1383 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1384 if (cmp != 0)
1385 return cmp;
1387 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1388 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1389 if (last1 != last2)
1390 return last1 - last2;
1391 if (last1 == -1)
1392 return 0;
1393 return isl_int_abs_cmp(c1->v->el[1 + last1], c2->v->el[1 + last2]);