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