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