?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_basic_set_solve_ilp: avoid double free on error path
[isl.git] / isl_constraint.c
blob490b191dcee462545a68a1389a325524b8d4a641
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(struct isl_constraint *constraint, isl_int *v)
477 {
478 if (!constraint)
479 return;
480 isl_int_set(*v, constraint->v->el[0]);
481 }
482
483 /* Return the constant term of "constraint".
484 */
485 __isl_give isl_val *isl_constraint_get_constant_val(
486 __isl_keep isl_constraint *constraint)
487 {
488 isl_ctx *ctx;
489
490 if (!constraint)
491 return NULL;
492
493 ctx = isl_constraint_get_ctx(constraint);
494 return isl_val_int_from_isl_int(ctx, constraint->v->el[0]);
495 }
496
497 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
498 enum isl_dim_type type, int pos, isl_int *v)
499 {
500 if (!constraint)
501 return;
502
503 if (pos >= isl_local_space_dim(constraint->ls, type))
504 isl_die(constraint->v->ctx, isl_error_invalid,
505 "position out of bounds", return);
506
507 pos += isl_local_space_offset(constraint->ls, type);
508 isl_int_set(*v, constraint->v->el[pos]);
509 }
510
511 /* Return the coefficient of the variable of type "type" at position "pos"
512 * of "constraint".
513 */
514 __isl_give isl_val *isl_constraint_get_coefficient_val(
515 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
516 {
517 isl_ctx *ctx;
518
519 if (!constraint)
520 return NULL;
521
522 ctx = isl_constraint_get_ctx(constraint);
523 if (pos < 0 || pos >= isl_local_space_dim(constraint->ls, type))
524 isl_die(ctx, isl_error_invalid,
525 "position out of bounds", return NULL);
526
527 pos += isl_local_space_offset(constraint->ls, type);
528 return isl_val_int_from_isl_int(ctx, constraint->v->el[pos]);
529 }
530
531 __isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint,
532 int pos)
533 {
534 if (!constraint)
535 return NULL;
536
537 return isl_local_space_get_div(constraint->ls, pos);
538 }
539
540 __isl_give isl_constraint *isl_constraint_set_constant(
541 __isl_take isl_constraint *constraint, isl_int v)
542 {
543 constraint = isl_constraint_cow(constraint);
544 if (!constraint)
545 return NULL;
546
547 constraint->v = isl_vec_cow(constraint->v);
548 if (!constraint->v)
549 return isl_constraint_free(constraint);
550
551 isl_int_set(constraint->v->el[0], v);
552 return constraint;
553 }
554
555 /* Replace the constant term of "constraint" by "v".
556 */
557 __isl_give isl_constraint *isl_constraint_set_constant_val(
558 __isl_take isl_constraint *constraint, __isl_take isl_val *v)
559 {
560 constraint = isl_constraint_cow(constraint);
561 if (!constraint || !v)
562 goto error;
563 if (!isl_val_is_int(v))
564 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
565 "expecting integer value", goto error);
566 constraint->v = isl_vec_set_element_val(constraint->v, 0, v);
567 if (!constraint->v)
568 constraint = isl_constraint_free(constraint);
569 return constraint;
570 error:
571 isl_val_free(v);
572 return isl_constraint_free(constraint);
573 }
574
575 __isl_give isl_constraint *isl_constraint_set_constant_si(
576 __isl_take isl_constraint *constraint, int v)
577 {
578 constraint = isl_constraint_cow(constraint);
579 if (!constraint)
580 return NULL;
581
582 constraint->v = isl_vec_cow(constraint->v);
583 if (!constraint->v)
584 return isl_constraint_free(constraint);
585
586 isl_int_set_si(constraint->v->el[0], v);
587 return constraint;
588 }
589
590 __isl_give isl_constraint *isl_constraint_set_coefficient(
591 __isl_take isl_constraint *constraint,
592 enum isl_dim_type type, int pos, isl_int v)
593 {
594 constraint = isl_constraint_cow(constraint);
595 if (!constraint)
596 return NULL;
597
598 if (pos >= isl_local_space_dim(constraint->ls, type))
599 isl_die(constraint->v->ctx, isl_error_invalid,
600 "position out of bounds",
601 return isl_constraint_free(constraint));
602
603 constraint = isl_constraint_cow(constraint);
604 if (!constraint)
605 return NULL;
606
607 constraint->v = isl_vec_cow(constraint->v);
608 if (!constraint->v)
609 return isl_constraint_free(constraint);
610
611 pos += isl_local_space_offset(constraint->ls, type);
612 isl_int_set(constraint->v->el[pos], v);
613
614 return constraint;
615 }
616
617 /* Replace the coefficient of the variable of type "type" at position "pos"
618 * of "constraint" by "v".
619 */
620 __isl_give isl_constraint *isl_constraint_set_coefficient_val(
621 __isl_take isl_constraint *constraint,
622 enum isl_dim_type type, int pos, __isl_take isl_val *v)
623 {
624 constraint = isl_constraint_cow(constraint);
625 if (!constraint || !v)
626 goto error;
627 if (!isl_val_is_int(v))
628 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
629 "expecting integer value", goto error);
630
631 if (pos >= isl_local_space_dim(constraint->ls, type))
632 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
633 "position out of bounds", goto error);
634
635 pos += isl_local_space_offset(constraint->ls, type);
636 constraint->v = isl_vec_set_element_val(constraint->v, pos, v);
637 if (!constraint->v)
638 constraint = isl_constraint_free(constraint);
639 return constraint;
640 error:
641 isl_val_free(v);
642 return isl_constraint_free(constraint);
643 }
644
645 __isl_give isl_constraint *isl_constraint_set_coefficient_si(
646 __isl_take isl_constraint *constraint,
647 enum isl_dim_type type, int pos, int v)
648 {
649 constraint = isl_constraint_cow(constraint);
650 if (!constraint)
651 return NULL;
652
653 if (pos >= isl_local_space_dim(constraint->ls, type))
654 isl_die(constraint->v->ctx, isl_error_invalid,
655 "position out of bounds",
656 return isl_constraint_free(constraint));
657
658 constraint = isl_constraint_cow(constraint);
659 if (!constraint)
660 return NULL;
661
662 constraint->v = isl_vec_cow(constraint->v);
663 if (!constraint->v)
664 return isl_constraint_free(constraint);
665
666 pos += isl_local_space_offset(constraint->ls, type);
667 isl_int_set_si(constraint->v->el[pos], v);
668
669 return constraint;
670 }
671
672 /* Drop any constraint from "bset" that is identical to "constraint".
673 * In particular, this means that the local spaces of "bset" and
674 * "constraint" need to be the same.
675 *
676 * We manually set ISL_BASIC_SET_FINAL instead of calling
677 * isl_basic_set_finalize because this function is called by CLooG,
678 * which does not expect any variables to disappear.
679 */
680 __isl_give isl_basic_set *isl_basic_set_drop_constraint(
681 __isl_take isl_basic_set *bset, __isl_take isl_constraint *constraint)
682 {
683 int i;
684 unsigned n;
685 isl_int **row;
686 unsigned total;
687 isl_local_space *ls1;
688 int equal;
689 int equality;
690
691 if (!bset || !constraint)
692 goto error;
693
694 ls1 = isl_basic_set_get_local_space(bset);
695 equal = isl_local_space_is_equal(ls1, constraint->ls);
696 isl_local_space_free(ls1);
697 if (equal < 0)
698 goto error;
699 if (!equal) {
700 isl_constraint_free(constraint);
701 return bset;
702 }
703
704 bset = isl_basic_set_cow(bset);
705 if (!bset)
706 goto error;
707
708 equality = isl_constraint_is_equality(constraint);
709 if (equality) {
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 continue;
721 if (equality && isl_basic_set_drop_equality(bset, i) < 0)
722 goto error;
723 if (!equality && isl_basic_set_drop_inequality(bset, i) < 0)
724 goto error;
725 break;
726 }
727
728 isl_constraint_free(constraint);
729 ISL_F_SET(bset, ISL_BASIC_SET_FINAL);
730 return bset;
731 error:
732 isl_constraint_free(constraint);
733 isl_basic_set_free(bset);
734 return NULL;
735 }
736
737 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
738 {
739 isl_ctx *ctx;
740
741 constraint = isl_constraint_cow(constraint);
742 if (!constraint)
743 return NULL;
744
745 ctx = isl_constraint_get_ctx(constraint);
746 if (isl_constraint_is_equality(constraint))
747 isl_die(ctx, isl_error_invalid, "cannot negate equality",
748 return isl_constraint_free(constraint));
749 constraint->v = isl_vec_neg(constraint->v);
750 constraint->v = isl_vec_cow(constraint->v);
751 if (!constraint->v)
752 return isl_constraint_free(constraint);
753 isl_int_sub_ui(constraint->v->el[0], constraint->v->el[0], 1);
754 return constraint;
755 }
756
757 isl_bool isl_constraint_is_equality(struct isl_constraint *constraint)
758 {
759 if (!constraint)
760 return isl_bool_error;
761 return constraint->eq;
762 }
763
764 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
765 {
766 int i;
767 int n_div;
768
769 if (!constraint)
770 return -1;
771 if (isl_constraint_is_equality(constraint))
772 return 0;
773 n_div = isl_constraint_dim(constraint, isl_dim_div);
774 for (i = 0; i < n_div; ++i) {
775 if (isl_local_space_is_div_constraint(constraint->ls,
776 constraint->v->el, i))
777 return 1;
778 }
779
780 return 0;
781 }
782
783 /* We manually set ISL_BASIC_SET_FINAL instead of calling
784 * isl_basic_map_finalize because we want to keep the position
785 * of the divs and we therefore do not want to throw away redundant divs.
786 * This is arguably a bit fragile.
787 */
788 __isl_give isl_basic_map *isl_basic_map_from_constraint(
789 __isl_take isl_constraint *constraint)
790 {
791 int k;
792 isl_local_space *ls;
793 struct isl_basic_map *bmap;
794 isl_int *c;
795 unsigned total;
796
797 if (!constraint)
798 return NULL;
799
800 ls = isl_local_space_copy(constraint->ls);
801 bmap = isl_basic_map_from_local_space(ls);
802 bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
803 if (isl_constraint_is_equality(constraint)) {
804 k = isl_basic_map_alloc_equality(bmap);
805 if (k < 0)
806 goto error;
807 c = bmap->eq[k];
808 }
809 else {
810 k = isl_basic_map_alloc_inequality(bmap);
811 if (k < 0)
812 goto error;
813 c = bmap->ineq[k];
814 }
815 total = isl_basic_map_total_dim(bmap);
816 isl_seq_cpy(c, constraint->v->el, 1 + total);
817 isl_constraint_free(constraint);
818 if (bmap)
819 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
820 return bmap;
821 error:
822 isl_constraint_free(constraint);
823 isl_basic_map_free(bmap);
824 return NULL;
825 }
826
827 struct isl_basic_set *isl_basic_set_from_constraint(
828 struct isl_constraint *constraint)
829 {
830 if (!constraint)
831 return NULL;
832
833 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
834 isl_die(isl_constraint_get_ctx(constraint), isl_error_invalid,
835 "not a set constraint", goto error);
836 return bset_from_bmap(isl_basic_map_from_constraint(constraint));
837 error:
838 isl_constraint_free(constraint);
839 return NULL;
840 }
841
842 /* Is the variable of "type" at position "pos" of "bmap" defined
843 * in terms of earlier dimensions through an equality?
844 *
845 * If so, and if c is not NULL, then return a copy of this equality in *c.
846 */
847 int isl_basic_map_has_defining_equality(
848 __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
849 __isl_give isl_constraint **c)
850 {
851 int i;
852 unsigned offset;
853 unsigned total;
854
855 if (!bmap)
856 return -1;
857 offset = basic_map_offset(bmap, type);
858 total = isl_basic_map_total_dim(bmap);
859 isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
860 for (i = 0; i < bmap->n_eq; ++i) {
861 if (isl_int_is_zero(bmap->eq[i][offset + pos]) ||
862 isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
863 1+total-offset-pos-1) != -1)
864 continue;
865 if (c)
866 *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
867 &bmap->eq[i]);
868 return 1;
869 }
870 return 0;
871 }
872
873 /* Is the variable of "type" at position "pos" of "bset" defined
874 * in terms of earlier dimensions through an equality?
875 *
876 * If so, and if c is not NULL, then return a copy of this equality in *c.
877 */
878 int isl_basic_set_has_defining_equality(
879 __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
880 __isl_give isl_constraint **c)
881 {
882 return isl_basic_map_has_defining_equality(bset_to_bmap(bset),
883 type, pos, c);
884 }
885
886 int isl_basic_set_has_defining_inequalities(
887 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
888 struct isl_constraint **lower,
889 struct isl_constraint **upper)
890 {
891 int i, j;
892 unsigned offset;
893 unsigned total;
894 isl_int m;
895 isl_int **lower_line, **upper_line;
896
897 if (!bset)
898 return -1;
899 offset = basic_set_offset(bset, type);
900 total = isl_basic_set_total_dim(bset);
901 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
902 isl_int_init(m);
903 for (i = 0; i < bset->n_ineq; ++i) {
904 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
905 continue;
906 if (isl_int_is_one(bset->ineq[i][offset + pos]))
907 continue;
908 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
909 continue;
910 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
911 1+total-offset-pos-1) != -1)
912 continue;
913 for (j = i + 1; j < bset->n_ineq; ++j) {
914 if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
915 total))
916 continue;
917 isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
918 if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
919 continue;
920
921 if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
922 lower_line = &bset->ineq[i];
923 upper_line = &bset->ineq[j];
924 } else {
925 lower_line = &bset->ineq[j];
926 upper_line = &bset->ineq[i];
927 }
928 *lower = isl_basic_set_constraint(
929 isl_basic_set_copy(bset), lower_line);
930 *upper = isl_basic_set_constraint(
931 isl_basic_set_copy(bset), upper_line);
932 isl_int_clear(m);
933 return 1;
934 }
935 }
936 *lower = NULL;
937 *upper = NULL;
938 isl_int_clear(m);
939 return 0;
940 }
941
942 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
943 * (in "a" and "b"), add a constraint to "bset" that ensures that the
944 * bound implied by "a" is (strictly) larger than the bound implied by "b".
945 *
946 * If both constraints imply lower bounds, then this means that "a" is
947 * active in the result.
948 * If both constraints imply upper bounds, then this means that "b" is
949 * active in the result.
950 */
951 static __isl_give isl_basic_set *add_larger_bound_constraint(
952 __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
953 unsigned abs_pos, int strict)
954 {
955 int k;
956 isl_int t;
957 unsigned total;
958
959 k = isl_basic_set_alloc_inequality(bset);
960 if (k < 0)
961 goto error;
962
963 total = isl_basic_set_dim(bset, isl_dim_all);
964
965 isl_int_init(t);
966 isl_int_neg(t, b[1 + abs_pos]);
967
968 isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
969 isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
970 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
971 total - abs_pos);
972
973 if (strict)
974 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
975
976 isl_int_clear(t);
977
978 return bset;
979 error:
980 isl_basic_set_free(bset);
981 return NULL;
982 }
983
984 /* Add constraints to "context" that ensure that "u" is the smallest
985 * (and therefore active) upper bound on "abs_pos" in "bset" and return
986 * the resulting basic set.
987 */
988 static __isl_give isl_basic_set *set_smallest_upper_bound(
989 __isl_keep isl_basic_set *context,
990 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
991 {
992 int j;
993
994 context = isl_basic_set_copy(context);
995 context = isl_basic_set_cow(context);
996
997 context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
998
999 for (j = 0; j < bset->n_ineq; ++j) {
1000 if (j == u)
1001 continue;
1002 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1003 continue;
1004 context = add_larger_bound_constraint(context,
1005 bset->ineq[j], bset->ineq[u], abs_pos, j > u);
1006 }
1007
1008 context = isl_basic_set_simplify(context);
1009 context = isl_basic_set_finalize(context);
1010
1011 return context;
1012 }
1013
1014 /* Add constraints to "context" that ensure that "u" is the largest
1015 * (and therefore active) upper bound on "abs_pos" in "bset" and return
1016 * the resulting basic set.
1017 */
1018 static __isl_give isl_basic_set *set_largest_lower_bound(
1019 __isl_keep isl_basic_set *context,
1020 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
1021 {
1022 int j;
1023
1024 context = isl_basic_set_copy(context);
1025 context = isl_basic_set_cow(context);
1026
1027 context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
1028
1029 for (j = 0; j < bset->n_ineq; ++j) {
1030 if (j == l)
1031 continue;
1032 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
1033 continue;
1034 context = add_larger_bound_constraint(context,
1035 bset->ineq[l], bset->ineq[j], abs_pos, j > l);
1036 }
1037
1038 context = isl_basic_set_simplify(context);
1039 context = isl_basic_set_finalize(context);
1040
1041 return context;
1042 }
1043
1044 static isl_stat foreach_upper_bound(__isl_keep isl_basic_set *bset,
1045 enum isl_dim_type type, unsigned abs_pos,
1046 __isl_take isl_basic_set *context, int n_upper,
1047 isl_stat (*fn)(__isl_take isl_constraint *lower,
1048 __isl_take isl_constraint *upper,
1049 __isl_take isl_basic_set *bset, void *user), void *user)
1050 {
1051 isl_basic_set *context_i;
1052 isl_constraint *upper = NULL;
1053 int i;
1054
1055 for (i = 0; i < bset->n_ineq; ++i) {
1056 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1057 continue;
1058
1059 context_i = set_smallest_upper_bound(context, bset,
1060 abs_pos, n_upper, i);
1061 if (isl_basic_set_is_empty(context_i)) {
1062 isl_basic_set_free(context_i);
1063 continue;
1064 }
1065 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1066 &bset->ineq[i]);
1067 if (!upper || !context_i)
1068 goto error;
1069 if (fn(NULL, upper, context_i, user) < 0)
1070 break;
1071 }
1072
1073 isl_basic_set_free(context);
1074
1075 if (i < bset->n_ineq)
1076 return isl_stat_error;
1077
1078 return isl_stat_ok;
1079 error:
1080 isl_constraint_free(upper);
1081 isl_basic_set_free(context_i);
1082 isl_basic_set_free(context);
1083 return isl_stat_error;
1084 }
1085
1086 static isl_stat foreach_lower_bound(__isl_keep isl_basic_set *bset,
1087 enum isl_dim_type type, unsigned abs_pos,
1088 __isl_take isl_basic_set *context, int n_lower,
1089 isl_stat (*fn)(__isl_take isl_constraint *lower,
1090 __isl_take isl_constraint *upper,
1091 __isl_take isl_basic_set *bset, void *user), void *user)
1092 {
1093 isl_basic_set *context_i;
1094 isl_constraint *lower = NULL;
1095 int i;
1096
1097 for (i = 0; i < bset->n_ineq; ++i) {
1098 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
1099 continue;
1100
1101 context_i = set_largest_lower_bound(context, bset,
1102 abs_pos, n_lower, i);
1103 if (isl_basic_set_is_empty(context_i)) {
1104 isl_basic_set_free(context_i);
1105 continue;
1106 }
1107 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1108 &bset->ineq[i]);
1109 if (!lower || !context_i)
1110 goto error;
1111 if (fn(lower, NULL, context_i, user) < 0)
1112 break;
1113 }
1114
1115 isl_basic_set_free(context);
1116
1117 if (i < bset->n_ineq)
1118 return isl_stat_error;
1119
1120 return isl_stat_ok;
1121 error:
1122 isl_constraint_free(lower);
1123 isl_basic_set_free(context_i);
1124 isl_basic_set_free(context);
1125 return isl_stat_error;
1126 }
1127
1128 static isl_stat foreach_bound_pair(__isl_keep isl_basic_set *bset,
1129 enum isl_dim_type type, unsigned abs_pos,
1130 __isl_take isl_basic_set *context, int n_lower, int n_upper,
1131 isl_stat (*fn)(__isl_take isl_constraint *lower,
1132 __isl_take isl_constraint *upper,
1133 __isl_take isl_basic_set *bset, void *user), void *user)
1134 {
1135 isl_basic_set *context_i, *context_j;
1136 isl_constraint *lower = NULL;
1137 isl_constraint *upper = NULL;
1138 int i, j;
1139
1140 for (i = 0; i < bset->n_ineq; ++i) {
1141 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1142 continue;
1143
1144 context_i = set_largest_lower_bound(context, bset,
1145 abs_pos, n_lower, i);
1146 if (isl_basic_set_is_empty(context_i)) {
1147 isl_basic_set_free(context_i);
1148 continue;
1149 }
1150
1151 for (j = 0; j < bset->n_ineq; ++j) {
1152 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
1153 continue;
1154
1155 context_j = set_smallest_upper_bound(context_i, bset,
1156 abs_pos, n_upper, j);
1157 context_j = isl_basic_set_extend_constraints(context_j,
1158 0, 1);
1159 context_j = add_larger_bound_constraint(context_j,
1160 bset->ineq[i], bset->ineq[j], abs_pos, 0);
1161 context_j = isl_basic_set_simplify(context_j);
1162 context_j = isl_basic_set_finalize(context_j);
1163 if (isl_basic_set_is_empty(context_j)) {
1164 isl_basic_set_free(context_j);
1165 continue;
1166 }
1167 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1168 &bset->ineq[i]);
1169 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
1170 &bset->ineq[j]);
1171 if (!lower || !upper || !context_j)
1172 goto error;
1173 if (fn(lower, upper, context_j, user) < 0)
1174 break;
1175 }
1176
1177 isl_basic_set_free(context_i);
1178
1179 if (j < bset->n_ineq)
1180 break;
1181 }
1182
1183 isl_basic_set_free(context);
1184
1185 if (i < bset->n_ineq)
1186 return isl_stat_error;
1187
1188 return isl_stat_ok;
1189 error:
1190 isl_constraint_free(lower);
1191 isl_constraint_free(upper);
1192 isl_basic_set_free(context_i);
1193 isl_basic_set_free(context_j);
1194 isl_basic_set_free(context);
1195 return isl_stat_error;
1196 }
1197
1198 /* For each pair of lower and upper bounds on the variable "pos"
1199 * of type "type", call "fn" with these lower and upper bounds and the
1200 * set of constraints on the remaining variables where these bounds
1201 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
1202 *
1203 * If the designated variable is equal to an affine combination of the
1204 * other variables then fn is called with both lower and upper
1205 * set to the corresponding equality.
1206 *
1207 * If there is no lower (or upper) bound, then NULL is passed
1208 * as the corresponding bound.
1209 *
1210 * We first check if the variable is involved in any equality.
1211 * If not, we count the number of lower and upper bounds and
1212 * act accordingly.
1213 */
1214 isl_stat isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
1215 enum isl_dim_type type, unsigned pos,
1216 isl_stat (*fn)(__isl_take isl_constraint *lower,
1217 __isl_take isl_constraint *upper,
1218 __isl_take isl_basic_set *bset, void *user), void *user)
1219 {
1220 int i;
1221 isl_constraint *lower = NULL;
1222 isl_constraint *upper = NULL;
1223 isl_basic_set *context = NULL;
1224 unsigned abs_pos;
1225 int n_lower, n_upper;
1226
1227 if (!bset)
1228 return isl_stat_error;
1229 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type),
1230 return isl_stat_error);
1231 isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
1232 return isl_stat_error);
1233
1234 abs_pos = pos;
1235 if (type == isl_dim_set)
1236 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
1237
1238 for (i = 0; i < bset->n_eq; ++i) {
1239 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
1240 continue;
1241
1242 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
1243 &bset->eq[i]);
1244 upper = isl_constraint_copy(lower);
1245 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
1246 type, pos, 1);
1247 if (!lower || !upper || !context)
1248 goto error;
1249 return fn(lower, upper, context, user);
1250 }
1251
1252 n_lower = 0;
1253 n_upper = 0;
1254 for (i = 0; i < bset->n_ineq; ++i) {
1255 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
1256 n_lower++;
1257 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
1258 n_upper++;
1259 }
1260
1261 context = isl_basic_set_copy(bset);
1262 context = isl_basic_set_cow(context);
1263 if (!context)
1264 goto error;
1265 for (i = context->n_ineq - 1; i >= 0; --i)
1266 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
1267 isl_basic_set_drop_inequality(context, i);
1268
1269 context = isl_basic_set_drop(context, type, pos, 1);
1270 if (!n_lower && !n_upper)
1271 return fn(NULL, NULL, context, user);
1272 if (!n_lower)
1273 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
1274 fn, user);
1275 if (!n_upper)
1276 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
1277 fn, user);
1278 return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
1279 fn, user);
1280 error:
1281 isl_constraint_free(lower);
1282 isl_constraint_free(upper);
1283 isl_basic_set_free(context);
1284 return -1;
1285 }
1286
1287 __isl_give isl_aff *isl_constraint_get_bound(
1288 __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos)
1289 {
1290 isl_aff *aff;
1291 isl_ctx *ctx;
1292
1293 if (!constraint)
1294 return NULL;
1295 ctx = isl_constraint_get_ctx(constraint);
1296 if (pos >= isl_constraint_dim(constraint, type))
1297 isl_die(ctx, isl_error_invalid,
1298 "index out of bounds", return NULL);
1299 if (isl_constraint_dim(constraint, isl_dim_in) != 0)
1300 isl_die(ctx, isl_error_invalid,
1301 "not a set constraint", return NULL);
1302
1303 pos += offset(constraint, type);
1304 if (isl_int_is_zero(constraint->v->el[pos]))
1305 isl_die(ctx, isl_error_invalid,
1306 "constraint does not define a bound on given dimension",
1307 return NULL);
1308
1309 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1310 if (!aff)
1311 return NULL;
1312
1313 if (isl_int_is_neg(constraint->v->el[pos]))
1314 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1315 else
1316 isl_seq_neg(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1317 isl_int_set_si(aff->v->el[1 + pos], 0);
1318 isl_int_abs(aff->v->el[0], constraint->v->el[pos]);
1319
1320 return aff;
1321 }
1322
1323 /* For an inequality constraint
1324 *
1325 * f >= 0
1326 *
1327 * or an equality constraint
1328 *
1329 * f = 0
1330 *
1331 * return the affine expression f.
1332 */
1333 __isl_give isl_aff *isl_constraint_get_aff(
1334 __isl_keep isl_constraint *constraint)
1335 {
1336 isl_aff *aff;
1337
1338 if (!constraint)
1339 return NULL;
1340
1341 aff = isl_aff_alloc(isl_local_space_copy(constraint->ls));
1342 if (!aff)
1343 return NULL;
1344
1345 isl_seq_cpy(aff->v->el + 1, constraint->v->el, aff->v->size - 1);
1346 isl_int_set_si(aff->v->el[0], 1);
1347
1348 return aff;
1349 }
1350
1351 /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff".
1352 * In particular, construct aff >= 0 or aff = 0.
1353 *
1354 * The denominator of "aff" can be ignored.
1355 */
1356 static __isl_give isl_constraint *isl_constraint_alloc_aff(int eq,
1357 __isl_take isl_aff *aff)
1358 {
1359 isl_local_space *ls;
1360 isl_vec *v;
1361
1362 if (!aff)
1363 return NULL;
1364 ls = isl_aff_get_domain_local_space(aff);
1365 v = isl_vec_drop_els(isl_vec_copy(aff->v), 0, 1);
1366 isl_aff_free(aff);
1367
1368 return isl_constraint_alloc_vec(eq, ls, v);
1369 }
1370
1371 /* Construct an equality constraint equating the given affine expression
1372 * to zero.
1373 */
1374 __isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff)
1375 {
1376 return isl_constraint_alloc_aff(1, aff);
1377 }
1378
1379 /* Construct an inequality constraint enforcing the given affine expression
1380 * to be non-negative.
1381 */
1382 __isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff)
1383 {
1384 return isl_constraint_alloc_aff(0, aff);
1385 }
1386
1387 /* Compare two isl_constraints.
1388 *
1389 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1390 * than "c2" and 0 if they are equal.
1391 *
1392 * The order is fairly arbitrary. We do consider constraints that only involve
1393 * earlier dimensions as "smaller".
1394 */
1395 int isl_constraint_plain_cmp(__isl_keep isl_constraint *c1,
1396 __isl_keep isl_constraint *c2)
1397 {
1398 int cmp;
1399 int last1, last2;
1400
1401 if (c1 == c2)
1402 return 0;
1403 if (!c1)
1404 return -1;
1405 if (!c2)
1406 return 1;
1407 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1408 if (cmp != 0)
1409 return cmp;
1410
1411 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1412 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1413 if (last1 != last2)
1414 return last1 - last2;
1415
1416 return isl_seq_cmp(c1->v->el, c2->v->el, c1->v->size);
1417 }
1418
1419 /* Compare two constraints based on their final (non-zero) coefficients.
1420 * In particular, the constraint that involves later variables or
1421 * that has a larger coefficient for a shared latest variable
1422 * is considered "greater" than the other constraint.
1423 *
1424 * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater"
1425 * than "c2" and 0 if they are equal.
1426 *
1427 * If the constraints live in different local spaces, then we cannot
1428 * really compare the constraints so we compare the local spaces instead.
1429 */
1430 int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint *c1,
1431 __isl_keep isl_constraint *c2)
1432 {
1433 int cmp;
1434 int last1, last2;
1435
1436 if (c1 == c2)
1437 return 0;
1438 if (!c1)
1439 return -1;
1440 if (!c2)
1441 return 1;
1442 cmp = isl_local_space_cmp(c1->ls, c2->ls);
1443 if (cmp != 0)
1444 return cmp;
1445
1446 last1 = isl_seq_last_non_zero(c1->v->el + 1, c1->v->size - 1);
1447 last2 = isl_seq_last_non_zero(c2->v->el + 1, c1->v->size - 1);
1448 if (last1 != last2)
1449 return last1 - last2;
1450 if (last1 == -1)
1451 return 0;
1452 return isl_int_abs_cmp(c1->v->el[1 + last1], c2->v->el[1 + last2]);
1453 }
Integer set library