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