?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_tab_pip.c: set free callback before any other fields
[isl.git] / isl_constraint.c
blob3d4391a793857fc86a425fb55742cb71d97f8b98
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 if (isl_local_space_is_div_constraint(constraint->ls,
777 constraint->v->el, i))
778 return 1;
779 }
780
781 return 0;
782 }
783
784 /* We manually set ISL_BASIC_SET_FINAL instead of calling
785 * isl_basic_map_finalize because we want to keep the position
786 * of the divs and we therefore do not want to throw away redundant divs.
787 * This is arguably a bit fragile.
788 */
789 __isl_give isl_basic_map *isl_basic_map_from_constraint(
790 __isl_take isl_constraint *constraint)
791 {
792 int k;
793 isl_local_space *ls;
794 struct isl_basic_map *bmap;
795 isl_int *c;
796 unsigned total;
797
798 if (!constraint)
799 return NULL;
800
801 ls = isl_local_space_copy(constraint->ls);
802 bmap = isl_basic_map_from_local_space(ls);
803 bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
804 if (isl_constraint_is_equality(constraint)) {
805 k = isl_basic_map_alloc_equality(bmap);
806 if (k < 0)
807 goto error;
808 c = bmap->eq[k];
809 }
810 else {
811 k = isl_basic_map_alloc_inequality(bmap);
812 if (k < 0)
813 goto error;
814 c = bmap->ineq[k];
815 }
816 total = isl_basic_map_total_dim(bmap);
817 isl_seq_cpy(c, constraint->v->el, 1 + total);
818 isl_constraint_free(constraint);
819 if (bmap)
820 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
821 return bmap;
822 error:
823 isl_constraint_free(constraint);
824 isl_basic_map_free(bmap);
825 return NULL;
826 }
827
828 struct isl_basic_set *isl_basic_set_from_constraint(
829 struct isl_constraint *constraint)
830 {
831 if (!constraint)
832 return NULL;
833
834 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
835 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
836 "not a set constraint", goto error);
837 return bset_from_bmap(isl_basic_map_from_constraint(constraint));
838 error:
839 isl_constraint_free(constraint);
840 return NULL;
841 }
842
843 /* Is the variable of "type" at position "pos" of "bmap" defined
844 * in terms of earlier dimensions through an equality?
845 *
846 * If so, and if c is not NULL, then return a copy of this equality in *c.
847 */
848 int isl_basic_map_has_defining_equality(
849 __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
850 __isl_give isl_constraint **c)
851 {
852 int i;
853 unsigned offset;
854 unsigned total;
855
856 if (!bmap)
857 return -1;
858 offset = basic_map_offset(bmap, type);
859 total = isl_basic_map_total_dim(bmap);
860 isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
861 for (i = 0; i < bmap->n_eq; ++i) {
862 if (isl_int_is_zero(bmap->eq[i][offset + pos]) ||
863 isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
864 1+total-offset-pos-1) != -1)
865 continue;
866 if (c)
867 *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
868 &bmap->eq[i]);
869 return 1;
870 }
871 return 0;
872 }
873
874 /* Is the variable of "type" at position "pos" of "bset" defined
875 * in terms of earlier dimensions through an equality?
876 *
877 * If so, and if c is not NULL, then return a copy of this equality in *c.
878 */
879 int isl_basic_set_has_defining_equality(
880 __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
881 __isl_give isl_constraint **c)
882 {
883 return isl_basic_map_has_defining_equality(bset_to_bmap(bset),
884 type, pos, c);
885 }
886
887 int isl_basic_set_has_defining_inequalities(
888 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
889 struct isl_constraint **lower,
890 struct isl_constraint **upper)
891 {
892 int i, j;
893 unsigned offset;
894 unsigned total;
895 isl_int m;
896 isl_int **lower_line, **upper_line;
897
898 if (!bset)
899 return -1;
900 offset = basic_set_offset(bset, type);
901 total = isl_basic_set_total_dim(bset);
902 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
903 isl_int_init(m);
904 for (i = 0; i < bset->n_ineq; ++i) {
905 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
906 continue;
907 if (isl_int_is_one(bset->ineq[i][offset + pos]))
908 continue;
909 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
910 continue;
911 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
912 1+total-offset-pos-1) != -1)
913 continue;
914 for (j = i + 1; j < bset->n_ineq; ++j) {
915 if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
916 total))
917 continue;
918 isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
919 if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
920 continue;
921
922 if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
923 lower_line = &bset->ineq[i];
924 upper_line = &bset->ineq[j];
925 } else {
926 lower_line = &bset->ineq[j];
927 upper_line = &bset->ineq[i];
928 }
929 *lower = isl_basic_set_constraint(
930 isl_basic_set_copy(bset), lower_line);
931 *upper = isl_basic_set_constraint(
932 isl_basic_set_copy(bset), upper_line);
933 isl_int_clear(m);
934 return 1;
935 }
936 }
937 *lower = NULL;
938 *upper = NULL;
939 isl_int_clear(m);
940 return 0;
941 }
942
943 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
944 * (in "a" and "b"), add a constraint to "bset" that ensures that the
945 * bound implied by "a" is (strictly) larger than the bound implied by "b".
946 *
947 * If both constraints imply lower bounds, then this means that "a" is
948 * active in the result.
949 * If both constraints imply upper bounds, then this means that "b" is
950 * active in the result.
951 */
952 static __isl_give isl_basic_set *add_larger_bound_constraint(
953 __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
954 unsigned abs_pos, int strict)
955 {
956 int k;
957 isl_int t;
958 unsigned total;
959
960 k = isl_basic_set_alloc_inequality(bset);
961 if (k < 0)
962 goto error;
963
964 total = isl_basic_set_dim(bset, isl_dim_all);
965
966 isl_int_init(t);
967 isl_int_neg(t, b[1 + abs_pos]);
968
969 isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
970 isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
971 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
972 total - abs_pos);
973
974 if (strict)
975 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
976
977 isl_int_clear(t);
978
979 return bset;
980 error:
981 isl_basic_set_free(bset);
982 return NULL;
983 }
984
985 /* Add constraints to "context" that ensure that "u" is the smallest
986 * (and therefore active) upper bound on "abs_pos" in "bset" and return
987 * the resulting basic set.
988 */
989 static __isl_give isl_basic_set *set_smallest_upper_bound(
990 __isl_keep isl_basic_set *context,
991 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
992 {
993 int j;
994
995 context = isl_basic_set_copy(context);
996 context = isl_basic_set_cow(context);
997
998 context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
999
1000 for (j = 0; j < bset->n_ineq; ++j) {
1001 if (j == u)
1002 continue;
1003 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1004 continue;
1005 context = add_larger_bound_constraint(context,
1006 bset->ineq[j], bset->ineq[u], abs_pos, j > u);
1007 }
1008
1009 context = isl_basic_set_simplify(context);
1010 context = isl_basic_set_finalize(context);
1011
1012 return context;
1013 }
1014
1015 /* Add constraints to "context" that ensure that "u" is the largest
1016 * (and therefore active) upper bound on "abs_pos" in "bset" and return
1017 * the resulting basic set.
1018 */
1019 static __isl_give isl_basic_set *set_largest_lower_bound(
1020 __isl_keep isl_basic_set *context,
1021 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
1022 {
1023 int j;
1024
1025 context = isl_basic_set_copy(context);
1026 context = isl_basic_set_cow(context);
1027
1028 context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
1029
1030 for (j = 0; j < bset->n_ineq; ++j) {
1031 if (j == l)
1032 continue;
1033 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
1034 continue;
1035 context = add_larger_bound_constraint(context,
1036 bset->ineq[l], bset->ineq[j], abs_pos, j > l);
1037 }
1038
1039 context = isl_basic_set_simplify(context);
1040 context = isl_basic_set_finalize(context);
1041
1042 return context;
1043 }
1044
1045 static isl_stat foreach_upper_bound(__isl_keep isl_basic_set *bset,
1046 enum isl_dim_type type, unsigned abs_pos,
1047 __isl_take isl_basic_set *context, int n_upper,
1048 isl_stat (*fn)(__isl_take isl_constraint *lower,
1049 __isl_take isl_constraint *upper,
1050 __isl_take isl_basic_set *bset, void *user), void *user)
1051 {
1052 isl_basic_set *context_i;
1053 isl_constraint *upper = NULL;
1054 int i;
1055
1056 for (i = 0; i < bset->n_ineq; ++i) {
1057 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1058 continue;
1059
1060 context_i = set_smallest_upper_bound(context, bset,
1061 abs_pos, n_upper, i);
1062 if (isl_basic_set_is_empty(context_i)) {
1063 isl_basic_set_free(context_i);
1064 continue;
1065 }
1066 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1067 &bset->ineq[i]);
1068 if (!upper || !context_i)
1069 goto error;
1070 if (fn(NULL, upper, context_i, user) < 0)
1071 break;
1072 }
1073
1074 isl_basic_set_free(context);
1075
1076 if (i < bset->n_ineq)
1077 return isl_stat_error;
1078
1079 return isl_stat_ok;
1080 error:
1081 isl_constraint_free(upper);
1082 isl_basic_set_free(context_i);
1083 isl_basic_set_free(context);
1084 return isl_stat_error;
1085 }
1086
1087 static isl_stat foreach_lower_bound(__isl_keep isl_basic_set *bset,
1088 enum isl_dim_type type, unsigned abs_pos,
1089 __isl_take isl_basic_set *context, int n_lower,
1090 isl_stat (*fn)(__isl_take isl_constraint *lower,
1091 __isl_take isl_constraint *upper,
1092 __isl_take isl_basic_set *bset, void *user), void *user)
1093 {
1094 isl_basic_set *context_i;
1095 isl_constraint *lower = NULL;
1096 int i;
1097
1098 for (i = 0; i < bset->n_ineq; ++i) {
1099 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1100 continue;
1101
1102 context_i = set_largest_lower_bound(context, bset,
1103 abs_pos, n_lower, i);
1104 if (isl_basic_set_is_empty(context_i)) {
1105 isl_basic_set_free(context_i);
1106 continue;
1107 }
1108 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1109 &bset->ineq[i]);
1110 if (!lower || !context_i)
1111 goto error;
1112 if (fn(lower, NULL, context_i, user) < 0)
1113 break;
1114 }
1115
1116 isl_basic_set_free(context);
1117
1118 if (i < bset->n_ineq)
1119 return isl_stat_error;
1120
1121 return isl_stat_ok;
1122 error:
1123 isl_constraint_free(lower);
1124 isl_basic_set_free(context_i);
1125 isl_basic_set_free(context);
1126 return isl_stat_error;
1127 }
1128
1129 static isl_stat foreach_bound_pair(__isl_keep isl_basic_set *bset,
1130 enum isl_dim_type type, unsigned abs_pos,
1131 __isl_take isl_basic_set *context, int n_lower, int n_upper,
1132 isl_stat (*fn)(__isl_take isl_constraint *lower,
1133 __isl_take isl_constraint *upper,
1134 __isl_take isl_basic_set *bset, void *user), void *user)
1135 {
1136 isl_basic_set *context_i, *context_j;
1137 isl_constraint *lower = NULL;
1138 isl_constraint *upper = NULL;
1139 int i, j;
1140
1141 for (i = 0; i < bset->n_ineq; ++i) {
1142 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1143 continue;
1144
1145 context_i = set_largest_lower_bound(context, bset,
1146 abs_pos, n_lower, i);
1147 if (isl_basic_set_is_empty(context_i)) {
1148 isl_basic_set_free(context_i);
1149 continue;
1150 }
1151
1152 for (j = 0; j < bset->n_ineq; ++j) {
1153 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1154 continue;
1155
1156 context_j = set_smallest_upper_bound(context_i, bset,
1157 abs_pos, n_upper, j);
1158 context_j = isl_basic_set_extend_constraints(context_j,
1159 0, 1);
1160 context_j = add_larger_bound_constraint(context_j,
1161 bset->ineq[i], bset->ineq[j], abs_pos, 0);
1162 context_j = isl_basic_set_simplify(context_j);
1163 context_j = isl_basic_set_finalize(context_j);
1164 if (isl_basic_set_is_empty(context_j)) {
1165 isl_basic_set_free(context_j);
1166 continue;
1167 }
1168 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1169 &bset->ineq[i]);
1170 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1171 &bset->ineq[j]);
1172 if (!lower || !upper || !context_j)
1173 goto error;
1174 if (fn(lower, upper, context_j, user) < 0)
1175 break;
1176 }
1177
1178 isl_basic_set_free(context_i);
1179
1180 if (j < bset->n_ineq)
1181 break;
1182 }
1183
1184 isl_basic_set_free(context);
1185
1186 if (i < bset->n_ineq)
1187 return isl_stat_error;
1188
1189 return isl_stat_ok;
1190 error:
1191 isl_constraint_free(lower);
1192 isl_constraint_free(upper);
1193 isl_basic_set_free(context_i);
1194 isl_basic_set_free(context_j);
1195 isl_basic_set_free(context);
1196 return isl_stat_error;
1197 }
1198
1199 /* For each pair of lower and upper bounds on the variable "pos"
1200 * of type "type", call "fn" with these lower and upper bounds and the
1201 * set of constraints on the remaining variables where these bounds
1202 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1203 *
1204 * If the designated variable is equal to an affine combination of the
1205 * other variables then fn is called with both lower and upper
1206 * set to the corresponding equality.
1207 *
1208 * If there is no lower (or upper) bound, then NULL is passed
1209 * as the corresponding bound.
1210 *
1211 * We first check if the variable is involved in any equality.
1212 * If not, we count the number of lower and upper bounds and
1213 * act accordingly.
1214 */
1215 isl_stat isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
1216 enum isl_dim_type type, unsigned pos,
1217 isl_stat (*fn)(__isl_take isl_constraint *lower,
1218 __isl_take isl_constraint *upper,
1219 __isl_take isl_basic_set *bset, void *user), void *user)
1220 {
1221 int i;
1222 isl_constraint *lower = NULL;
1223 isl_constraint *upper = NULL;
1224 isl_basic_set *context = NULL;
1225 unsigned abs_pos;
1226 int n_lower, n_upper;
1227
1228 if (!bset)
1229 return isl_stat_error;
1230 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type),
1231 return isl_stat_error);
1232 isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
1233 return isl_stat_error);
1234
1235 abs_pos = pos;
1236 if (type == isl_dim_set)
1237 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
1238
1239 for (i = 0; i < bset->n_eq; ++i) {
1240 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
1241 continue;
1242
1243 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1244 &bset->eq[i]);
1245 upper = isl_constraint_copy(lower);
1246 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
1247 type, pos, 1);
1248 if (!lower || !upper || !context)
1249 goto error;
1250 return fn(lower, upper, context, user);
1251 }
1252
1253 n_lower = 0;
1254 n_upper = 0;
1255 for (i = 0; i < bset->n_ineq; ++i) {
1256 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1257 n_lower++;
1258 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
1259 n_upper++;
1260 }
1261
1262 context = isl_basic_set_copy(bset);
1263 context = isl_basic_set_cow(context);
1264 if (!context)
1265 goto error;
1266 for (i = context->n_ineq - 1; i >= 0; --i)
1267 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
1268 isl_basic_set_drop_inequality(context, i);
1269
1270 context = isl_basic_set_drop(context, type, pos, 1);
1271 if (!n_lower && !n_upper)
1272 return fn(NULL, NULL, context, user);
1273 if (!n_lower)
1274 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1275 fn, user);
1276 if (!n_upper)
1277 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
1278 fn, user);
1279 return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
1280 fn, user);
1281 error:
1282 isl_constraint_free(lower);
1283 isl_constraint_free(upper);
1284 isl_basic_set_free(context);
1285 return -1;
1286 }
1287
1288 __isl_give isl_aff *isl_constraint_get_bound(
1289 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1290 {
1291 isl_aff *aff;
1292 isl_ctx *ctx;
1293
1294 if (!constraint)
1295 return NULL;
1296 ctx = isl_constraint_get_ctx(constraint);
1297 if (pos >= isl_constraint_dim(constraint, type))
1298 isl_die(ctx, isl_error_invalid,
1299 "index out of bounds", return NULL);
1300 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
1301 isl_die(ctx, isl_error_invalid,
1302 "not a set constraint", return NULL);
1303
1304 pos += offset(constraint, type);
1305 if (isl_int_is_zero(constraint->v->el[pos]))
1306 isl_die(ctx, isl_error_invalid,
1307 "constraint does not define a bound on given dimension",
1308 return NULL);
1309
1310 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1311 if (!aff)
1312 return NULL;
1313
1314 if (isl_int_is_neg(constraint->v->el[pos]))
1315 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1316 else
1317 isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1318 isl_int_set_si(aff->v->el[1 + pos], 0);
1319 isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1320
1321 return aff;
1322 }
1323
1324 /* For an inequality constraint
1325 *
1326 * f >= 0
1327 *
1328 * or an equality constraint
1329 *
1330 * f = 0
1331 *
1332 * return the affine expression f.
1333 */
1334 __isl_give isl_aff *isl_constraint_get_aff(
1335 __isl_keep isl_constraint *constraint)
1336 {
1337 isl_aff *aff;
1338
1339 if (!constraint)
1340 return NULL;
1341
1342 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1343 if (!aff)
1344 return NULL;
1345
1346 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1347 isl_int_set_si(aff->v->el[0], 1);
1348
1349 return aff;
1350 }
1351
1352 /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1353 * In particular, construct aff >= 0 or aff = 0.
1354 *
1355 * The denominator of "aff" can be ignored.
1356 */
1357 static __isl_give isl_constraint *isl_constraint_alloc_aff(int eq,
1358 __isl_take isl_aff *aff)
1359 {
1360 isl_local_space *ls;
1361 isl_vec *v;
1362
1363 if (!aff)
1364 return NULL;
1365 ls = isl_aff_get_domain_local_space(aff);
1366 v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1367 isl_aff_free(aff);
1368
1369 return isl_constraint_alloc_vec(eq, ls, v);
1370 }
1371
1372 /* Construct an equality constraint equating the given affine expression
1373 * to zero.
1374 */
1375 __isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff)
1376 {
1377 return isl_constraint_alloc_aff(1, aff);
1378 }
1379
1380 /* Construct an inequality constraint enforcing the given affine expression
1381 * to be non-negative.
1382 */
1383 __isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff)
1384 {
1385 return isl_constraint_alloc_aff(0, aff);
1386 }
1387
1388 /* Compare two isl_constraints.
1389 *
1390 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1391 * than "c2" and 0 if they are equal.
1392 *
1393 * The order is fairly arbitrary. We do consider constraints that only involve
1394 * earlier dimensions as "smaller".
1395 */
1396 int isl_constraint_plain_cmp(__isl_keep isl_constraint *c1,
1397 __isl_keep isl_constraint *c2)
1398 {
1399 int cmp;
1400 int last1, last2;
1401
1402 if (c1 == c2)
1403 return 0;
1404 if (!c1)
1405 return -1;
1406 if (!c2)
1407 return 1;
1408 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1409 if (cmp != 0)
1410 return cmp;
1411
1412 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1413 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1414 if (last1 != last2)
1415 return last1 - last2;
1416
1417 return isl_seq_cmp(c1->v->el, c2->v->el, c1->v->size);
1418 }
1419
1420 /* Compare two constraints based on their final (non-zero) coefficients.
1421 * In particular, the constraint that involves later variables or
1422 * that has a larger coefficient for a shared latest variable
1423 * is considered "greater" than the other constraint.
1424 *
1425 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1426 * than "c2" and 0 if they are equal.
1427 *
1428 * If the constraints live in different local spaces, then we cannot
1429 * really compare the constraints so we compare the local spaces instead.
1430 */
1431 int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint *c1,
1432 __isl_keep isl_constraint *c2)
1433 {
1434 int cmp;
1435 int last1, last2;
1436
1437 if (c1 == c2)
1438 return 0;
1439 if (!c1)
1440 return -1;
1441 if (!c2)
1442 return 1;
1443 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1444 if (cmp != 0)
1445 return cmp;
1446
1447 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1448 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1449 if (last1 != last2)
1450 return last1 - last2;
1451 if (last1 == -1)
1452 return 0;
1453 return isl_int_abs_cmp(c1->v->el[1 + last1], c2->v->el[1 + last2]);
1454 }
Integer set library