?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_basic_set_drop_constraint: add missing isl_basic_set_cow
[isl.git] / isl_constraint.c
blob3f7976b257220460b458fac3711b0d26abcb23e6
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 *
5 * Use of this software is governed by the MIT license
6 *
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
11 */
12
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>
21 #include <isl/deprecated/constraint_int.h>
22
23 #undef BASE
24 #define BASE constraint
25
26 #include <isl_list_templ.c>
27
28 isl_ctx *isl_constraint_get_ctx(__isl_keep isl_constraint *c)
29 {
30 return c ? isl_local_space_get_ctx(c->ls) : NULL;
31 }
32
33 static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
34 {
35 return isl_local_space_dim(c->ls, type);
36 }
37
38 static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
39 {
40 return isl_local_space_offset(c->ls, type);
41 }
42
43 static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
44 enum isl_dim_type type)
45 {
46 return type == isl_dim_div ? 1 + isl_space_dim(bmap->dim, isl_dim_all)
47 : 1 + isl_space_offset(bmap->dim, type);
48 }
49
50 static unsigned basic_set_offset(struct isl_basic_set *bset,
51 enum isl_dim_type type)
52 {
53 isl_space *dim = bset->dim;
54 switch (type) {
55 case isl_dim_param: return 1;
56 case isl_dim_in: return 1 + dim->nparam;
57 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
58 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
59 default: return 0;
60 }
61 }
62
63 __isl_give isl_constraint *isl_constraint_alloc_vec(int eq,
64 __isl_take isl_local_space *ls, __isl_take isl_vec *v)
65 {
66 isl_constraint *constraint;
67
68 if (!ls || !v)
69 goto error;
70
71 constraint = isl_alloc_type(isl_vec_get_ctx(v), isl_constraint);
72 if (!constraint)
73 goto error;
74
75 constraint->ref = 1;
76 constraint->eq = eq;
77 constraint->ls = ls;
78 constraint->v = v;
79
80 return constraint;
81 error:
82 isl_local_space_free(ls);
83 isl_vec_free(v);
84 return NULL;
85 }
86
87 __isl_give isl_constraint *isl_constraint_alloc(int eq,
88 __isl_take isl_local_space *ls)
89 {
90 isl_ctx *ctx;
91 isl_vec *v;
92
93 if (!ls)
94 return NULL;
95
96 ctx = isl_local_space_get_ctx(ls);
97 v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
98 v = isl_vec_clr(v);
99 return isl_constraint_alloc_vec(eq, ls, v);
100 }
101
102 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
103 isl_int **line)
104 {
105 int eq;
106 isl_ctx *ctx;
107 isl_vec *v;
108 isl_local_space *ls = NULL;
109 isl_constraint *constraint;
110
111 if (!bmap || !line)
112 goto error;
113
114 eq = line >= bmap->eq;
115
116 ctx = isl_basic_map_get_ctx(bmap);
117 ls = isl_basic_map_get_local_space(bmap);
118 v = isl_vec_alloc(ctx, 1 + isl_local_space_dim(ls, isl_dim_all));
119 if (!v)
120 goto error;
121 isl_seq_cpy(v->el, line[0], v->size);
122 constraint = isl_constraint_alloc_vec(eq, ls, v);
123
124 isl_basic_map_free(bmap);
125 return constraint;
126 error:
127 isl_local_space_free(ls);
128 isl_basic_map_free(bmap);
129 return NULL;
130 }
131
132 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
133 isl_int **line)
134 {
135 return isl_basic_map_constraint((struct isl_basic_map *)bset, line);
136 }
137
138 __isl_give isl_constraint *isl_equality_alloc(__isl_take isl_local_space *ls)
139 {
140 return isl_constraint_alloc(1, ls);
141 }
142
143 __isl_give isl_constraint *isl_inequality_alloc(__isl_take isl_local_space *ls)
144 {
145 return isl_constraint_alloc(0, ls);
146 }
147
148 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
149 {
150 if (!c)
151 return NULL;
152
153 return isl_constraint_alloc_vec(c->eq, isl_local_space_copy(c->ls),
154 isl_vec_copy(c->v));
155 }
156
157 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
158 {
159 if (!c)
160 return NULL;
161
162 if (c->ref == 1)
163 return c;
164 c->ref--;
165 return isl_constraint_dup(c);
166 }
167
168 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
169 {
170 if (!constraint)
171 return NULL;
172
173 constraint->ref++;
174 return constraint;
175 }
176
177 __isl_null isl_constraint *isl_constraint_free(__isl_take isl_constraint *c)
178 {
179 if (!c)
180 return NULL;
181
182 if (--c->ref > 0)
183 return NULL;
184
185 isl_local_space_free(c->ls);
186 isl_vec_free(c->v);
187 free(c);
188
189 return NULL;
190 }
191
192 /* Return the number of constraints in "bmap", i.e., the
193 * number of times isl_basic_map_foreach_constraint will
194 * call the callback.
195 */
196 int isl_basic_map_n_constraint(__isl_keep isl_basic_map *bmap)
197 {
198 if (!bmap)
199 return -1;
200
201 return bmap->n_eq + bmap->n_ineq;
202 }
203
204 /* Return the number of constraints in "bset", i.e., the
205 * number of times isl_basic_set_foreach_constraint will
206 * call the callback.
207 */
208 int isl_basic_set_n_constraint(__isl_keep isl_basic_set *bset)
209 {
210 return isl_basic_map_n_constraint(bset);
211 }
212
213 int isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
214 int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
215 {
216 int i;
217 struct isl_constraint *c;
218
219 if (!bmap)
220 return -1;
221
222 isl_assert(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),
223 return -1);
224
225 for (i = 0; i < bmap->n_eq; ++i) {
226 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
227 &bmap->eq[i]);
228 if (!c)
229 return -1;
230 if (fn(c, user) < 0)
231 return -1;
232 }
233
234 for (i = 0; i < bmap->n_ineq; ++i) {
235 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
236 &bmap->ineq[i]);
237 if (!c)
238 return -1;
239 if (fn(c, user) < 0)
240 return -1;
241 }
242
243 return 0;
244 }
245
246 int isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
247 int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
248 {
249 return isl_basic_map_foreach_constraint((isl_basic_map *)bset, fn, user);
250 }
251
252 /* Add the constraint to the list that "user" points to, if it is not
253 * a div constraint.
254 */
255 static int collect_constraint(__isl_take isl_constraint *constraint,
256 void *user)
257 {
258 isl_constraint_list **list = user;
259
260 if (isl_constraint_is_div_constraint(constraint))
261 isl_constraint_free(constraint);
262 else
263 *list = isl_constraint_list_add(*list, constraint);
264
265 return 0;
266 }
267
268 /* Return a list of constraints that, when combined, are equivalent
269 * to "bmap". The input is required to have only known divs.
270 *
271 * There is no need to include the div constraints as they are
272 * implied by the div expressions.
273 */
274 __isl_give isl_constraint_list *isl_basic_map_get_constraint_list(
275 __isl_keep isl_basic_map *bmap)
276 {
277 int n;
278 int known;
279 isl_ctx *ctx;
280 isl_constraint_list *list;
281
282 known = isl_basic_map_divs_known(bmap);
283 if (known < 0)
284 return NULL;
285 ctx = isl_basic_map_get_ctx(bmap);
286 if (!known)
287 isl_die(ctx, isl_error_invalid,
288 "input involves unknown divs", return NULL);
289
290 n = isl_basic_map_n_constraint(bmap);
291 list = isl_constraint_list_alloc(ctx, n);
292 if (isl_basic_map_foreach_constraint(bmap,
293 &collect_constraint, &list) < 0)
294 list = isl_constraint_list_free(list);
295
296 return list;
297 }
298
299 /* Return a list of constraints that, when combined, are equivalent
300 * to "bset". The input is required to have only known divs.
301 */
302 __isl_give isl_constraint_list *isl_basic_set_get_constraint_list(
303 __isl_keep isl_basic_set *bset)
304 {
305 return isl_basic_map_get_constraint_list(bset);
306 }
307
308 int isl_constraint_is_equal(struct isl_constraint *constraint1,
309 struct isl_constraint *constraint2)
310 {
311 int equal;
312
313 if (!constraint1 || !constraint2)
314 return 0;
315 if (constraint1->eq != constraint2->eq)
316 return 0;
317 equal = isl_local_space_is_equal(constraint1->ls, constraint2->ls);
318 if (equal < 0 || !equal)
319 return equal;
320 return isl_vec_is_equal(constraint1->v, constraint2->v);
321 }
322
323 struct isl_basic_map *isl_basic_map_add_constraint(
324 struct isl_basic_map *bmap, struct isl_constraint *constraint)
325 {
326 isl_ctx *ctx;
327 isl_space *dim;
328 int equal_space;
329
330 if (!bmap || !constraint)
331 goto error;
332
333 ctx = isl_constraint_get_ctx(constraint);
334 dim = isl_constraint_get_space(constraint);
335 equal_space = isl_space_is_equal(bmap->dim, dim);
336 isl_space_free(dim);
337 isl_assert(ctx, equal_space, goto error);
338
339 bmap = isl_basic_map_intersect(bmap,
340 isl_basic_map_from_constraint(constraint));
341 return bmap;
342 error:
343 isl_basic_map_free(bmap);
344 isl_constraint_free(constraint);
345 return NULL;
346 }
347
348 struct isl_basic_set *isl_basic_set_add_constraint(
349 struct isl_basic_set *bset, struct isl_constraint *constraint)
350 {
351 return (struct isl_basic_set *)
352 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
353 constraint);
354 }
355
356 __isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map,
357 __isl_take isl_constraint *constraint)
358 {
359 isl_basic_map *bmap;
360
361 bmap = isl_basic_map_from_constraint(constraint);
362 map = isl_map_intersect(map, isl_map_from_basic_map(bmap));
363
364 return map;
365 }
366
367 __isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set,
368 __isl_take isl_constraint *constraint)
369 {
370 return isl_map_add_constraint(set, constraint);
371 }
372
373 __isl_give isl_space *isl_constraint_get_space(
374 __isl_keep isl_constraint *constraint)
375 {
376 return constraint ? isl_local_space_get_space(constraint->ls) : NULL;
377 }
378
379 __isl_give isl_local_space *isl_constraint_get_local_space(
380 __isl_keep isl_constraint *constraint)
381 {
382 return constraint ? isl_local_space_copy(constraint->ls) : NULL;
383 }
384
385 int isl_constraint_dim(struct isl_constraint *constraint,
386 enum isl_dim_type type)
387 {
388 if (!constraint)
389 return -1;
390 return n(constraint, type);
391 }
392
393 int isl_constraint_involves_dims(__isl_keep isl_constraint *constraint,
394 enum isl_dim_type type, unsigned first, unsigned n)
395 {
396 int i;
397 isl_ctx *ctx;
398 int *active = NULL;
399 int involves = 0;
400
401 if (!constraint)
402 return -1;
403 if (n == 0)
404 return 0;
405
406 ctx = isl_constraint_get_ctx(constraint);
407 if (first + n > isl_constraint_dim(constraint, type))
408 isl_die(ctx, isl_error_invalid,
409 "range out of bounds", return -1);
410
411 active = isl_local_space_get_active(constraint->ls,
412 constraint->v->el + 1);
413 if (!active)
414 goto error;
415
416 first += isl_local_space_offset(constraint->ls, type) - 1;
417 for (i = 0; i < n; ++i)
418 if (active[first + i]) {
419 involves = 1;
420 break;
421 }
422
423 free(active);
424
425 return involves;
426 error:
427 free(active);
428 return -1;
429 }
430
431 /* Does the given constraint represent a lower bound on the given
432 * dimension?
433 */
434 int isl_constraint_is_lower_bound(__isl_keep isl_constraint *constraint,
435 enum isl_dim_type type, unsigned pos)
436 {
437 if (!constraint)
438 return -1;
439
440 if (pos >= isl_local_space_dim(constraint->ls, type))
441 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
442 "position out of bounds", return -1);
443
444 pos += isl_local_space_offset(constraint->ls, type);
445 return isl_int_is_pos(constraint->v->el[pos]);
446 }
447
448 /* Does the given constraint represent an upper bound on the given
449 * dimension?
450 */
451 int isl_constraint_is_upper_bound(__isl_keep isl_constraint *constraint,
452 enum isl_dim_type type, unsigned pos)
453 {
454 if (!constraint)
455 return -1;
456
457 if (pos >= isl_local_space_dim(constraint->ls, type))
458 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
459 "position out of bounds", return -1);
460
461 pos += isl_local_space_offset(constraint->ls, type);
462 return isl_int_is_neg(constraint->v->el[pos]);
463 }
464
465 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
466 enum isl_dim_type type, unsigned pos)
467 {
468 return constraint ?
469 isl_local_space_get_dim_name(constraint->ls, type, pos) : NULL;
470 }
471
472 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
473 {
474 if (!constraint)
475 return;
476 isl_int_set(*v, constraint->v->el[0]);
477 }
478
479 /* Return the constant term of "constraint".
480 */
481 __isl_give isl_val *isl_constraint_get_constant_val(
482 __isl_keep isl_constraint *constraint)
483 {
484 isl_ctx *ctx;
485
486 if (!constraint)
487 return NULL;
488
489 ctx = isl_constraint_get_ctx(constraint);
490 return isl_val_int_from_isl_int(ctx, constraint->v->el[0]);
491 }
492
493 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
494 enum isl_dim_type type, int pos, isl_int *v)
495 {
496 if (!constraint)
497 return;
498
499 if (pos >= isl_local_space_dim(constraint->ls, type))
500 isl_die(constraint->v->ctx, isl_error_invalid,
501 "position out of bounds", return);
502
503 pos += isl_local_space_offset(constraint->ls, type);
504 isl_int_set(*v, constraint->v->el[pos]);
505 }
506
507 /* Return the coefficient of the variable of type "type" at position "pos"
508 * of "constraint".
509 */
510 __isl_give isl_val *isl_constraint_get_coefficient_val(
511 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
512 {
513 isl_ctx *ctx;
514
515 if (!constraint)
516 return NULL;
517
518 ctx = isl_constraint_get_ctx(constraint);
519 if (pos < 0 || pos >= isl_local_space_dim(constraint->ls, type))
520 isl_die(ctx, isl_error_invalid,
521 "position out of bounds", return NULL);
522
523 pos += isl_local_space_offset(constraint->ls, type);
524 return isl_val_int_from_isl_int(ctx, constraint->v->el[pos]);
525 }
526
527 __isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint,
528 int pos)
529 {
530 if (!constraint)
531 return NULL;
532
533 return isl_local_space_get_div(constraint->ls, pos);
534 }
535
536 __isl_give isl_constraint *isl_constraint_set_constant(
537 __isl_take isl_constraint *constraint, isl_int v)
538 {
539 constraint = isl_constraint_cow(constraint);
540 if (!constraint)
541 return NULL;
542
543 constraint->v = isl_vec_cow(constraint->v);
544 if (!constraint->v)
545 return isl_constraint_free(constraint);
546
547 isl_int_set(constraint->v->el[0], v);
548 return constraint;
549 }
550
551 /* Replace the constant term of "constraint" by "v".
552 */
553 __isl_give isl_constraint *isl_constraint_set_constant_val(
554 __isl_take isl_constraint *constraint, __isl_take isl_val *v)
555 {
556 constraint = isl_constraint_cow(constraint);
557 if (!constraint || !v)
558 goto error;
559 if (!isl_val_is_int(v))
560 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
561 "expecting integer value", goto error);
562 constraint->v = isl_vec_set_element_val(constraint->v, 0, v);
563 if (!constraint->v)
564 constraint = isl_constraint_free(constraint);
565 return constraint;
566 error:
567 isl_val_free(v);
568 return isl_constraint_free(constraint);
569 }
570
571 __isl_give isl_constraint *isl_constraint_set_constant_si(
572 __isl_take isl_constraint *constraint, int v)
573 {
574 constraint = isl_constraint_cow(constraint);
575 if (!constraint)
576 return NULL;
577
578 constraint->v = isl_vec_cow(constraint->v);
579 if (!constraint->v)
580 return isl_constraint_free(constraint);
581
582 isl_int_set_si(constraint->v->el[0], v);
583 return constraint;
584 }
585
586 __isl_give isl_constraint *isl_constraint_set_coefficient(
587 __isl_take isl_constraint *constraint,
588 enum isl_dim_type type, int pos, isl_int v)
589 {
590 constraint = isl_constraint_cow(constraint);
591 if (!constraint)
592 return NULL;
593
594 if (pos >= isl_local_space_dim(constraint->ls, type))
595 isl_die(constraint->v->ctx, isl_error_invalid,
596 "position out of bounds",
597 return isl_constraint_free(constraint));
598
599 constraint = isl_constraint_cow(constraint);
600 if (!constraint)
601 return NULL;
602
603 constraint->v = isl_vec_cow(constraint->v);
604 if (!constraint->v)
605 return isl_constraint_free(constraint);
606
607 pos += isl_local_space_offset(constraint->ls, type);
608 isl_int_set(constraint->v->el[pos], v);
609
610 return constraint;
611 }
612
613 /* Replace the coefficient of the variable of type "type" at position "pos"
614 * of "constraint" by "v".
615 */
616 __isl_give isl_constraint *isl_constraint_set_coefficient_val(
617 __isl_take isl_constraint *constraint,
618 enum isl_dim_type type, int pos, __isl_take isl_val *v)
619 {
620 constraint = isl_constraint_cow(constraint);
621 if (!constraint || !v)
622 goto error;
623 if (!isl_val_is_int(v))
624 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
625 "expecting integer value", goto error);
626
627 if (pos >= isl_local_space_dim(constraint->ls, type))
628 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
629 "position out of bounds", goto error);
630
631 pos += isl_local_space_offset(constraint->ls, type);
632 constraint->v = isl_vec_set_element_val(constraint->v, pos, v);
633 if (!constraint->v)
634 constraint = isl_constraint_free(constraint);
635 return constraint;
636 error:
637 isl_val_free(v);
638 return isl_constraint_free(constraint);
639 }
640
641 __isl_give isl_constraint *isl_constraint_set_coefficient_si(
642 __isl_take isl_constraint *constraint,
643 enum isl_dim_type type, int pos, int v)
644 {
645 constraint = isl_constraint_cow(constraint);
646 if (!constraint)
647 return NULL;
648
649 if (pos >= isl_local_space_dim(constraint->ls, type))
650 isl_die(constraint->v->ctx, isl_error_invalid,
651 "position out of bounds",
652 return isl_constraint_free(constraint));
653
654 constraint = isl_constraint_cow(constraint);
655 if (!constraint)
656 return NULL;
657
658 constraint->v = isl_vec_cow(constraint->v);
659 if (!constraint->v)
660 return isl_constraint_free(constraint);
661
662 pos += isl_local_space_offset(constraint->ls, type);
663 isl_int_set_si(constraint->v->el[pos], v);
664
665 return constraint;
666 }
667
668 /* Drop any constraint from "bset" that is identical to "constraint".
669 * In particular, this means that the local spaces of "bset" and
670 * "constraint" need to be the same.
671 *
672 * Since the given constraint may actually be a pointer into the bset,
673 * we have to be careful not to reorder the constraints as the user
674 * may be holding on to other constraints from the same bset.
675 * This should be cleaned up when the internal representation of
676 * isl_constraint is changed to use isl_aff.
677 *
678 * We manually set ISL_BASIC_SET_FINAL instead of calling
679 * isl_basic_set_finalize because this function is called by CLooG,
680 * which does not expect any variables to disappear.
681 */
682 __isl_give isl_basic_set *isl_basic_set_drop_constraint(
683 __isl_take isl_basic_set *bset, __isl_take isl_constraint *constraint)
684 {
685 int i;
686 unsigned n;
687 isl_int **row;
688 unsigned total;
689 isl_local_space *ls1;
690 int equal;
691
692 if (!bset || !constraint)
693 goto error;
694
695 ls1 = isl_basic_set_get_local_space(bset);
696 equal = isl_local_space_is_equal(ls1, constraint->ls);
697 isl_local_space_free(ls1);
698 if (equal < 0)
699 goto error;
700 if (!equal) {
701 isl_constraint_free(constraint);
702 return bset;
703 }
704
705 bset = isl_basic_set_cow(bset);
706 if (!bset)
707 goto error;
708
709 if (isl_constraint_is_equality(constraint)) {
710 n = bset->n_eq;
711 row = bset->eq;
712 } else {
713 n = bset->n_ineq;
714 row = bset->ineq;
715 }
716
717 total = isl_constraint_dim(constraint, isl_dim_all);
718 for (i = 0; i < n; ++i)
719 if (isl_seq_eq(row[i], constraint->v->el, 1 + total))
720 isl_seq_clr(row[i], 1 + total);
721
722 isl_constraint_free(constraint);
723 ISL_F_SET(bset, ISL_BASIC_SET_FINAL);
724 return bset;
725 error:
726 isl_constraint_free(constraint);
727 isl_basic_set_free(bset);
728 return NULL;
729 }
730
731 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
732 {
733 isl_ctx *ctx;
734
735 constraint = isl_constraint_cow(constraint);
736 if (!constraint)
737 return NULL;
738
739 ctx = isl_constraint_get_ctx(constraint);
740 if (isl_constraint_is_equality(constraint))
741 isl_die(ctx, isl_error_invalid, "cannot negate equality",
742 return isl_constraint_free(constraint));
743 constraint->v = isl_vec_neg(constraint->v);
744 constraint->v = isl_vec_cow(constraint->v);
745 if (!constraint->v)
746 return isl_constraint_free(constraint);
747 isl_int_sub_ui(constraint->v->el[0], constraint->v->el[0], 1);
748 return constraint;
749 }
750
751 int isl_constraint_is_equality(struct isl_constraint *constraint)
752 {
753 if (!constraint)
754 return -1;
755 return constraint->eq;
756 }
757
758 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
759 {
760 int i;
761 int n_div;
762
763 if (!constraint)
764 return -1;
765 if (isl_constraint_is_equality(constraint))
766 return 0;
767 n_div = isl_constraint_dim(constraint, isl_dim_div);
768 for (i = 0; i < n_div; ++i) {
769 if (isl_local_space_is_div_constraint(constraint->ls,
770 constraint->v->el, i))
771 return 1;
772 }
773
774 return 0;
775 }
776
777 /* We manually set ISL_BASIC_SET_FINAL instead of calling
778 * isl_basic_map_finalize because we want to keep the position
779 * of the divs and we therefore do not want to throw away redundant divs.
780 * This is arguably a bit fragile.
781 */
782 __isl_give isl_basic_map *isl_basic_map_from_constraint(
783 __isl_take isl_constraint *constraint)
784 {
785 int k;
786 isl_local_space *ls;
787 struct isl_basic_map *bmap;
788 isl_int *c;
789 unsigned total;
790
791 if (!constraint)
792 return NULL;
793
794 ls = isl_local_space_copy(constraint->ls);
795 bmap = isl_basic_map_from_local_space(ls);
796 bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
797 if (isl_constraint_is_equality(constraint)) {
798 k = isl_basic_map_alloc_equality(bmap);
799 if (k < 0)
800 goto error;
801 c = bmap->eq[k];
802 }
803 else {
804 k = isl_basic_map_alloc_inequality(bmap);
805 if (k < 0)
806 goto error;
807 c = bmap->ineq[k];
808 }
809 total = isl_basic_map_total_dim(bmap);
810 isl_seq_cpy(c, constraint->v->el, 1 + total);
811 isl_constraint_free(constraint);
812 if (bmap)
813 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
814 return bmap;
815 error:
816 isl_constraint_free(constraint);
817 isl_basic_map_free(bmap);
818 return NULL;
819 }
820
821 struct isl_basic_set *isl_basic_set_from_constraint(
822 struct isl_constraint *constraint)
823 {
824 if (!constraint)
825 return NULL;
826
827 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
828 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
829 "not a set constraint", goto error);
830 return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
831 error:
832 isl_constraint_free(constraint);
833 return NULL;
834 }
835
836 /* Is the variable of "type" at position "pos" of "bmap" defined
837 * in terms of earlier dimensions through an equality?
838 *
839 * If so, and if c is not NULL, then return a copy of this equality in *c.
840 */
841 int isl_basic_map_has_defining_equality(
842 __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
843 __isl_give isl_constraint **c)
844 {
845 int i;
846 unsigned offset;
847 unsigned total;
848
849 if (!bmap)
850 return -1;
851 offset = basic_map_offset(bmap, type);
852 total = isl_basic_map_total_dim(bmap);
853 isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
854 for (i = 0; i < bmap->n_eq; ++i) {
855 if (isl_int_is_zero(bmap->eq[i][offset + pos]) ||
856 isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
857 1+total-offset-pos-1) != -1)
858 continue;
859 if (c)
860 *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
861 &bmap->eq[i]);
862 return 1;
863 }
864 return 0;
865 }
866
867 /* Is the variable of "type" at position "pos" of "bset" defined
868 * in terms of earlier dimensions through an equality?
869 *
870 * If so, and if c is not NULL, then return a copy of this equality in *c.
871 */
872 int isl_basic_set_has_defining_equality(
873 __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
874 __isl_give isl_constraint **c)
875 {
876 return isl_basic_map_has_defining_equality((isl_basic_map *)bset,
877 type, pos, c);
878 }
879
880 int isl_basic_set_has_defining_inequalities(
881 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
882 struct isl_constraint **lower,
883 struct isl_constraint **upper)
884 {
885 int i, j;
886 unsigned offset;
887 unsigned total;
888 isl_int m;
889 isl_int **lower_line, **upper_line;
890
891 if (!bset)
892 return -1;
893 offset = basic_set_offset(bset, type);
894 total = isl_basic_set_total_dim(bset);
895 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
896 isl_int_init(m);
897 for (i = 0; i < bset->n_ineq; ++i) {
898 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
899 continue;
900 if (isl_int_is_one(bset->ineq[i][offset + pos]))
901 continue;
902 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
903 continue;
904 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
905 1+total-offset-pos-1) != -1)
906 continue;
907 for (j = i + 1; j < bset->n_ineq; ++j) {
908 if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
909 total))
910 continue;
911 isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
912 if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
913 continue;
914
915 if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
916 lower_line = &bset->ineq[i];
917 upper_line = &bset->ineq[j];
918 } else {
919 lower_line = &bset->ineq[j];
920 upper_line = &bset->ineq[i];
921 }
922 *lower = isl_basic_set_constraint(
923 isl_basic_set_copy(bset), lower_line);
924 *upper = isl_basic_set_constraint(
925 isl_basic_set_copy(bset), upper_line);
926 isl_int_clear(m);
927 return 1;
928 }
929 }
930 *lower = NULL;
931 *upper = NULL;
932 isl_int_clear(m);
933 return 0;
934 }
935
936 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
937 * (in "a" and "b"), add a constraint to "bset" that ensures that the
938 * bound implied by "a" is (strictly) larger than the bound implied by "b".
939 *
940 * If both constraints imply lower bounds, then this means that "a" is
941 * active in the result.
942 * If both constraints imply upper bounds, then this means that "b" is
943 * active in the result.
944 */
945 static __isl_give isl_basic_set *add_larger_bound_constraint(
946 __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
947 unsigned abs_pos, int strict)
948 {
949 int k;
950 isl_int t;
951 unsigned total;
952
953 k = isl_basic_set_alloc_inequality(bset);
954 if (k < 0)
955 goto error;
956
957 total = isl_basic_set_dim(bset, isl_dim_all);
958
959 isl_int_init(t);
960 isl_int_neg(t, b[1 + abs_pos]);
961
962 isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
963 isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
964 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
965 total - abs_pos);
966
967 if (strict)
968 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
969
970 isl_int_clear(t);
971
972 return bset;
973 error:
974 isl_basic_set_free(bset);
975 return NULL;
976 }
977
978 /* Add constraints to "context" that ensure that "u" is the smallest
979 * (and therefore active) upper bound on "abs_pos" in "bset" and return
980 * the resulting basic set.
981 */
982 static __isl_give isl_basic_set *set_smallest_upper_bound(
983 __isl_keep isl_basic_set *context,
984 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
985 {
986 int j;
987
988 context = isl_basic_set_copy(context);
989 context = isl_basic_set_cow(context);
990
991 context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
992
993 for (j = 0; j < bset->n_ineq; ++j) {
994 if (j == u)
995 continue;
996 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
997 continue;
998 context = add_larger_bound_constraint(context,
999 bset->ineq[j], bset->ineq[u], abs_pos, j > u);
1000 }
1001
1002 context = isl_basic_set_simplify(context);
1003 context = isl_basic_set_finalize(context);
1004
1005 return context;
1006 }
1007
1008 /* Add constraints to "context" that ensure that "u" is the largest
1009 * (and therefore active) upper bound on "abs_pos" in "bset" and return
1010 * the resulting basic set.
1011 */
1012 static __isl_give isl_basic_set *set_largest_lower_bound(
1013 __isl_keep isl_basic_set *context,
1014 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
1015 {
1016 int j;
1017
1018 context = isl_basic_set_copy(context);
1019 context = isl_basic_set_cow(context);
1020
1021 context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
1022
1023 for (j = 0; j < bset->n_ineq; ++j) {
1024 if (j == l)
1025 continue;
1026 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
1027 continue;
1028 context = add_larger_bound_constraint(context,
1029 bset->ineq[l], bset->ineq[j], abs_pos, j > l);
1030 }
1031
1032 context = isl_basic_set_simplify(context);
1033 context = isl_basic_set_finalize(context);
1034
1035 return context;
1036 }
1037
1038 static int foreach_upper_bound(__isl_keep isl_basic_set *bset,
1039 enum isl_dim_type type, unsigned abs_pos,
1040 __isl_take isl_basic_set *context, int n_upper,
1041 int (*fn)(__isl_take isl_constraint *lower,
1042 __isl_take isl_constraint *upper,
1043 __isl_take isl_basic_set *bset, void *user), void *user)
1044 {
1045 isl_basic_set *context_i;
1046 isl_constraint *upper = NULL;
1047 int i;
1048
1049 for (i = 0; i < bset->n_ineq; ++i) {
1050 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1051 continue;
1052
1053 context_i = set_smallest_upper_bound(context, bset,
1054 abs_pos, n_upper, i);
1055 if (isl_basic_set_is_empty(context_i)) {
1056 isl_basic_set_free(context_i);
1057 continue;
1058 }
1059 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1060 &bset->ineq[i]);
1061 if (!upper || !context_i)
1062 goto error;
1063 if (fn(NULL, upper, context_i, user) < 0)
1064 break;
1065 }
1066
1067 isl_basic_set_free(context);
1068
1069 if (i < bset->n_ineq)
1070 return -1;
1071
1072 return 0;
1073 error:
1074 isl_constraint_free(upper);
1075 isl_basic_set_free(context_i);
1076 isl_basic_set_free(context);
1077 return -1;
1078 }
1079
1080 static int foreach_lower_bound(__isl_keep isl_basic_set *bset,
1081 enum isl_dim_type type, unsigned abs_pos,
1082 __isl_take isl_basic_set *context, int n_lower,
1083 int (*fn)(__isl_take isl_constraint *lower,
1084 __isl_take isl_constraint *upper,
1085 __isl_take isl_basic_set *bset, void *user), void *user)
1086 {
1087 isl_basic_set *context_i;
1088 isl_constraint *lower = NULL;
1089 int i;
1090
1091 for (i = 0; i < bset->n_ineq; ++i) {
1092 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1093 continue;
1094
1095 context_i = set_largest_lower_bound(context, bset,
1096 abs_pos, n_lower, i);
1097 if (isl_basic_set_is_empty(context_i)) {
1098 isl_basic_set_free(context_i);
1099 continue;
1100 }
1101 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1102 &bset->ineq[i]);
1103 if (!lower || !context_i)
1104 goto error;
1105 if (fn(lower, NULL, context_i, user) < 0)
1106 break;
1107 }
1108
1109 isl_basic_set_free(context);
1110
1111 if (i < bset->n_ineq)
1112 return -1;
1113
1114 return 0;
1115 error:
1116 isl_constraint_free(lower);
1117 isl_basic_set_free(context_i);
1118 isl_basic_set_free(context);
1119 return -1;
1120 }
1121
1122 static int foreach_bound_pair(__isl_keep isl_basic_set *bset,
1123 enum isl_dim_type type, unsigned abs_pos,
1124 __isl_take isl_basic_set *context, int n_lower, int n_upper,
1125 int (*fn)(__isl_take isl_constraint *lower,
1126 __isl_take isl_constraint *upper,
1127 __isl_take isl_basic_set *bset, void *user), void *user)
1128 {
1129 isl_basic_set *context_i, *context_j;
1130 isl_constraint *lower = NULL;
1131 isl_constraint *upper = NULL;
1132 int i, j;
1133
1134 for (i = 0; i < bset->n_ineq; ++i) {
1135 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1136 continue;
1137
1138 context_i = set_largest_lower_bound(context, bset,
1139 abs_pos, n_lower, i);
1140 if (isl_basic_set_is_empty(context_i)) {
1141 isl_basic_set_free(context_i);
1142 continue;
1143 }
1144
1145 for (j = 0; j < bset->n_ineq; ++j) {
1146 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1147 continue;
1148
1149 context_j = set_smallest_upper_bound(context_i, bset,
1150 abs_pos, n_upper, j);
1151 context_j = isl_basic_set_extend_constraints(context_j,
1152 0, 1);
1153 context_j = add_larger_bound_constraint(context_j,
1154 bset->ineq[i], bset->ineq[j], abs_pos, 0);
1155 context_j = isl_basic_set_simplify(context_j);
1156 context_j = isl_basic_set_finalize(context_j);
1157 if (isl_basic_set_is_empty(context_j)) {
1158 isl_basic_set_free(context_j);
1159 continue;
1160 }
1161 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1162 &bset->ineq[i]);
1163 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1164 &bset->ineq[j]);
1165 if (!lower || !upper || !context_j)
1166 goto error;
1167 if (fn(lower, upper, context_j, user) < 0)
1168 break;
1169 }
1170
1171 isl_basic_set_free(context_i);
1172
1173 if (j < bset->n_ineq)
1174 break;
1175 }
1176
1177 isl_basic_set_free(context);
1178
1179 if (i < bset->n_ineq)
1180 return -1;
1181
1182 return 0;
1183 error:
1184 isl_constraint_free(lower);
1185 isl_constraint_free(upper);
1186 isl_basic_set_free(context_i);
1187 isl_basic_set_free(context_j);
1188 isl_basic_set_free(context);
1189 return -1;
1190 }
1191
1192 /* For each pair of lower and upper bounds on the variable "pos"
1193 * of type "type", call "fn" with these lower and upper bounds and the
1194 * set of constraints on the remaining variables where these bounds
1195 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1196 *
1197 * If the designated variable is equal to an affine combination of the
1198 * other variables then fn is called with both lower and upper
1199 * set to the corresponding equality.
1200 *
1201 * If there is no lower (or upper) bound, then NULL is passed
1202 * as the corresponding bound.
1203 *
1204 * We first check if the variable is involved in any equality.
1205 * If not, we count the number of lower and upper bounds and
1206 * act accordingly.
1207 */
1208 int isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
1209 enum isl_dim_type type, unsigned pos,
1210 int (*fn)(__isl_take isl_constraint *lower,
1211 __isl_take isl_constraint *upper,
1212 __isl_take isl_basic_set *bset, void *user), void *user)
1213 {
1214 int i;
1215 isl_constraint *lower = NULL;
1216 isl_constraint *upper = NULL;
1217 isl_basic_set *context = NULL;
1218 unsigned abs_pos;
1219 int n_lower, n_upper;
1220
1221 if (!bset)
1222 return -1;
1223 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
1224 isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
1225 return -1);
1226
1227 abs_pos = pos;
1228 if (type == isl_dim_set)
1229 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
1230
1231 for (i = 0; i < bset->n_eq; ++i) {
1232 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
1233 continue;
1234
1235 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1236 &bset->eq[i]);
1237 upper = isl_constraint_copy(lower);
1238 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
1239 type, pos, 1);
1240 if (!lower || !upper || !context)
1241 goto error;
1242 return fn(lower, upper, context, user);
1243 }
1244
1245 n_lower = 0;
1246 n_upper = 0;
1247 for (i = 0; i < bset->n_ineq; ++i) {
1248 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1249 n_lower++;
1250 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
1251 n_upper++;
1252 }
1253
1254 context = isl_basic_set_copy(bset);
1255 context = isl_basic_set_cow(context);
1256 if (!context)
1257 goto error;
1258 for (i = context->n_ineq - 1; i >= 0; --i)
1259 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
1260 isl_basic_set_drop_inequality(context, i);
1261
1262 context = isl_basic_set_drop(context, type, pos, 1);
1263 if (!n_lower && !n_upper)
1264 return fn(NULL, NULL, context, user);
1265 if (!n_lower)
1266 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1267 fn, user);
1268 if (!n_upper)
1269 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
1270 fn, user);
1271 return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
1272 fn, user);
1273 error:
1274 isl_constraint_free(lower);
1275 isl_constraint_free(upper);
1276 isl_basic_set_free(context);
1277 return -1;
1278 }
1279
1280 __isl_give isl_aff *isl_constraint_get_bound(
1281 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1282 {
1283 isl_aff *aff;
1284 isl_ctx *ctx;
1285
1286 if (!constraint)
1287 return NULL;
1288 ctx = isl_constraint_get_ctx(constraint);
1289 if (pos >= isl_constraint_dim(constraint, type))
1290 isl_die(ctx, isl_error_invalid,
1291 "index out of bounds", return NULL);
1292 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
1293 isl_die(ctx, isl_error_invalid,
1294 "not a set constraint", return NULL);
1295
1296 pos += offset(constraint, type);
1297 if (isl_int_is_zero(constraint->v->el[pos]))
1298 isl_die(ctx, isl_error_invalid,
1299 "constraint does not define a bound on given dimension",
1300 return NULL);
1301
1302 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1303 if (!aff)
1304 return NULL;
1305
1306 if (isl_int_is_neg(constraint->v->el[pos]))
1307 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1308 else
1309 isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1310 isl_int_set_si(aff->v->el[1 + pos], 0);
1311 isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1312
1313 return aff;
1314 }
1315
1316 /* For an inequality constraint
1317 *
1318 * f >= 0
1319 *
1320 * or an equality constraint
1321 *
1322 * f = 0
1323 *
1324 * return the affine expression f.
1325 */
1326 __isl_give isl_aff *isl_constraint_get_aff(
1327 __isl_keep isl_constraint *constraint)
1328 {
1329 isl_aff *aff;
1330
1331 if (!constraint)
1332 return NULL;
1333
1334 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1335 if (!aff)
1336 return NULL;
1337
1338 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1339 isl_int_set_si(aff->v->el[0], 1);
1340
1341 return aff;
1342 }
1343
1344 /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1345 * In particular, construct aff >= 0 or aff = 0.
1346 *
1347 * The denominator of "aff" can be ignored.
1348 */
1349 static __isl_give isl_constraint *isl_constraint_alloc_aff(int eq,
1350 __isl_take isl_aff *aff)
1351 {
1352 isl_local_space *ls;
1353 isl_vec *v;
1354
1355 if (!aff)
1356 return NULL;
1357 ls = isl_aff_get_domain_local_space(aff);
1358 v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1359 isl_aff_free(aff);
1360
1361 return isl_constraint_alloc_vec(eq, ls, v);
1362 }
1363
1364 /* Construct an equality constraint equating the given affine expression
1365 * to zero.
1366 */
1367 __isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff)
1368 {
1369 return isl_constraint_alloc_aff(1, aff);
1370 }
1371
1372 /* Construct an inequality constraint enforcing the given affine expression
1373 * to be non-negative.
1374 */
1375 __isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff)
1376 {
1377 return isl_constraint_alloc_aff(0, aff);
1378 }
1379
1380 /* Compare two isl_constraints.
1381 *
1382 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1383 * than "c2" and 0 if they are equal.
1384 *
1385 * The order is fairly arbitrary. We do consider constraints that only involve
1386 * earlier dimensions as "smaller".
1387 */
1388 int isl_constraint_plain_cmp(__isl_keep isl_constraint *c1,
1389 __isl_keep isl_constraint *c2)
1390 {
1391 int cmp;
1392 int last1, last2;
1393
1394 if (c1 == c2)
1395 return 0;
1396 if (!c1)
1397 return -1;
1398 if (!c2)
1399 return 1;
1400 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1401 if (cmp != 0)
1402 return cmp;
1403
1404 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1405 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1406 if (last1 != last2)
1407 return last1 - last2;
1408
1409 return isl_seq_cmp(c1->v->el, c2->v->el, c1->v->size);
1410 }
1411
1412 /* Compare two constraints based on their final (non-zero) coefficients.
1413 * In particular, the constraint that involves later variables or
1414 * that has a larger coefficient for a shared latest variable
1415 * is considered "greater" than the other constraint.
1416 *
1417 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1418 * than "c2" and 0 if they are equal.
1419 *
1420 * If the constraints live in different local spaces, then we cannot
1421 * really compare the constraints so we compare the local spaces instead.
1422 */
1423 int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint *c1,
1424 __isl_keep isl_constraint *c2)
1425 {
1426 int cmp;
1427 int last1, last2;
1428
1429 if (c1 == c2)
1430 return 0;
1431 if (!c1)
1432 return -1;
1433 if (!c2)
1434 return 1;
1435 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1436 if (cmp != 0)
1437 return cmp;
1438
1439 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1440 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1441 if (last1 != last2)
1442 return last1 - last2;
1443 if (last1 == -1)
1444 return 0;
1445 return isl_int_abs_cmp(c1->v->el[1 + last1], c2->v->el[1 + last2]);
1446 }
Integer set library