?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_vec_sort
[isl.git] / isl_constraint.c
blobf936e253003438711b24b2da399249e77a2ee50b
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 *
5 * Use of this software is governed by the GNU LGPLv2.1 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.h>
15 #include <isl_dim_private.h>
16 #include <isl/seq.h>
17
18 isl_ctx *isl_constraint_get_ctx(__isl_keep isl_constraint *c)
19 {
20 return c ? c->ctx : NULL;
21 }
22
23 static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
24 {
25 return isl_basic_map_dim(c->bmap, type);
26 }
27
28 static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
29 {
30 struct isl_dim *dim = c->bmap->dim;
31 switch (type) {
32 case isl_dim_param: return 1;
33 case isl_dim_in: return 1 + dim->nparam;
34 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
35 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
36 default: return 0;
37 }
38 }
39
40 static unsigned basic_map_offset(__isl_keep isl_basic_map *bmap,
41 enum isl_dim_type type)
42 {
43 return type == isl_dim_div ? 1 + isl_dim_total(bmap->dim)
44 : 1 + isl_dim_offset(bmap->dim, type);
45 }
46
47 static unsigned basic_set_offset(struct isl_basic_set *bset,
48 enum isl_dim_type type)
49 {
50 struct isl_dim *dim = bset->dim;
51 switch (type) {
52 case isl_dim_param: return 1;
53 case isl_dim_in: return 1 + dim->nparam;
54 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
55 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
56 default: return 0;
57 }
58 }
59
60 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
61 isl_int **line)
62 {
63 struct isl_constraint *constraint;
64
65 if (!bmap || !line)
66 goto error;
67
68 constraint = isl_alloc_type(bmap->ctx, struct isl_constraint);
69 if (!constraint)
70 goto error;
71
72 constraint->ctx = bmap->ctx;
73 isl_ctx_ref(constraint->ctx);
74 constraint->ref = 1;
75 constraint->bmap = bmap;
76 constraint->line = line;
77
78 return constraint;
79 error:
80 isl_basic_map_free(bmap);
81 return NULL;
82 }
83
84 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
85 isl_int **line)
86 {
87 return isl_basic_map_constraint((struct isl_basic_map *)bset, line);
88 }
89
90 struct isl_constraint *isl_equality_alloc(struct isl_dim *dim)
91 {
92 struct isl_basic_map *bmap;
93
94 if (!dim)
95 return NULL;
96
97 bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
98 if (!bmap)
99 return NULL;
100
101 isl_basic_map_alloc_equality(bmap);
102 isl_seq_clr(bmap->eq[0], 1 + isl_basic_map_total_dim(bmap));
103 return isl_basic_map_constraint(bmap, &bmap->eq[0]);
104 }
105
106 struct isl_constraint *isl_inequality_alloc(struct isl_dim *dim)
107 {
108 struct isl_basic_map *bmap;
109
110 if (!dim)
111 return NULL;
112
113 bmap = isl_basic_map_alloc_dim(dim, 0, 0, 1);
114 if (!bmap)
115 return NULL;
116
117 isl_basic_map_alloc_inequality(bmap);
118 isl_seq_clr(bmap->ineq[0], 1 + isl_basic_map_total_dim(bmap));
119 return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
120 }
121
122 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
123 {
124 struct isl_basic_map *bmap;
125 int i;
126 int eq;
127
128 if (!c)
129 return NULL;
130
131 eq = c->line < c->bmap->eq + c->bmap->n_eq;
132 i = eq ? c->line - c->bmap->eq : c->line - c->bmap->ineq;
133 bmap = isl_basic_map_copy(c->bmap);
134 if (!bmap)
135 return NULL;
136 return isl_basic_map_constraint(bmap, eq ? bmap->eq + i : bmap->ineq + i);
137 }
138
139 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
140 {
141 if (!c)
142 return NULL;
143
144 if (c->ref == 1)
145 return c;
146 c->ref--;
147 return isl_constraint_dup(c);
148 }
149
150 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
151 {
152 if (!constraint)
153 return NULL;
154
155 constraint->ref++;
156 return constraint;
157 }
158
159 void isl_constraint_free(struct isl_constraint *c)
160 {
161 if (!c)
162 return;
163
164 if (--c->ref > 0)
165 return;
166
167 isl_basic_map_free(c->bmap);
168 isl_ctx_deref(c->ctx);
169 free(c);
170 }
171
172 __isl_give isl_constraint *isl_basic_map_first_constraint(
173 __isl_take isl_basic_map *bmap)
174 {
175 if (!bmap)
176 return NULL;
177
178 if (bmap->n_eq > 0)
179 return isl_basic_map_constraint(bmap, &bmap->eq[0]);
180
181 if (bmap->n_ineq > 0)
182 return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
183
184 isl_basic_map_free(bmap);
185 return NULL;
186 }
187
188 __isl_give isl_constraint *isl_basic_set_first_constraint(
189 __isl_take isl_basic_set *bset)
190 {
191 return isl_basic_map_first_constraint((struct isl_basic_map *)bset);
192 }
193
194 struct isl_constraint *isl_constraint_next(struct isl_constraint *c)
195 {
196 c = isl_constraint_cow(c);
197 if (c->line >= c->bmap->eq) {
198 c->line++;
199 if (c->line < c->bmap->eq + c->bmap->n_eq)
200 return c;
201 c->line = c->bmap->ineq;
202 } else
203 c->line++;
204 if (c->line < c->bmap->ineq + c->bmap->n_ineq)
205 return c;
206 isl_constraint_free(c);
207 return NULL;
208 }
209
210 int isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
211 int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
212 {
213 int i;
214 struct isl_constraint *c;
215
216 if (!bmap)
217 return -1;
218
219 isl_assert(bmap->ctx, ISL_F_ISSET(bmap, ISL_BASIC_MAP_FINAL),
220 return -1);
221
222 for (i = 0; i < bmap->n_eq; ++i) {
223 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
224 &bmap->eq[i]);
225 if (!c)
226 return -1;
227 if (fn(c, user) < 0)
228 return -1;
229 }
230
231 for (i = 0; i < bmap->n_ineq; ++i) {
232 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
233 &bmap->ineq[i]);
234 if (!c)
235 return -1;
236 if (fn(c, user) < 0)
237 return -1;
238 }
239
240 return 0;
241 }
242
243 int isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
244 int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
245 {
246 return isl_basic_map_foreach_constraint((isl_basic_map *)bset, fn, user);
247 }
248
249 int isl_constraint_is_equal(struct isl_constraint *constraint1,
250 struct isl_constraint *constraint2)
251 {
252 if (!constraint1 || !constraint2)
253 return 0;
254 return constraint1->bmap == constraint2->bmap &&
255 constraint1->line == constraint2->line;
256 }
257
258 struct isl_basic_map *isl_basic_map_add_constraint(
259 struct isl_basic_map *bmap, struct isl_constraint *constraint)
260 {
261 if (!bmap || !constraint)
262 goto error;
263
264 isl_assert(constraint->ctx,
265 isl_dim_equal(bmap->dim, constraint->bmap->dim), goto error);
266
267 bmap = isl_basic_map_intersect(bmap,
268 isl_basic_map_from_constraint(constraint));
269 return bmap;
270 error:
271 isl_basic_map_free(bmap);
272 isl_constraint_free(constraint);
273 return NULL;
274 }
275
276 struct isl_basic_set *isl_basic_set_add_constraint(
277 struct isl_basic_set *bset, struct isl_constraint *constraint)
278 {
279 return (struct isl_basic_set *)
280 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
281 constraint);
282 }
283
284 struct isl_constraint *isl_constraint_add_div(struct isl_constraint *constraint,
285 struct isl_div *div, int *pos)
286 {
287 if (!constraint || !div)
288 goto error;
289
290 isl_assert(constraint->ctx,
291 isl_dim_equal(div->bmap->dim, constraint->bmap->dim), goto error);
292 isl_assert(constraint->ctx,
293 constraint->bmap->n_eq + constraint->bmap->n_ineq == 1, goto error);
294
295 constraint->bmap = isl_basic_map_cow(constraint->bmap);
296 constraint->bmap = isl_basic_map_extend_dim(constraint->bmap,
297 isl_dim_copy(constraint->bmap->dim), 1, 0, 0);
298 if (!constraint->bmap)
299 goto error;
300 constraint->line = &constraint->bmap->ineq[0];
301 *pos = isl_basic_map_alloc_div(constraint->bmap);
302 if (*pos < 0)
303 goto error;
304 isl_seq_cpy(constraint->bmap->div[*pos], div->line[0],
305 1 + 1 + isl_basic_map_total_dim(constraint->bmap));
306 isl_div_free(div);
307 return constraint;
308 error:
309 isl_constraint_free(constraint);
310 isl_div_free(div);
311 return NULL;
312 }
313
314 __isl_give isl_dim *isl_constraint_get_dim(
315 __isl_keep isl_constraint *constraint)
316 {
317 return constraint ? isl_basic_map_get_dim(constraint->bmap) : NULL;
318 }
319
320 int isl_constraint_dim(struct isl_constraint *constraint,
321 enum isl_dim_type type)
322 {
323 if (!constraint)
324 return -1;
325 return n(constraint, type);
326 }
327
328 const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint,
329 enum isl_dim_type type, unsigned pos)
330 {
331 return constraint ?
332 isl_basic_map_get_dim_name(constraint->bmap, type, pos) : NULL;
333 }
334
335 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
336 {
337 if (!constraint)
338 return;
339 isl_int_set(*v, constraint->line[0][0]);
340 }
341
342 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
343 enum isl_dim_type type, int pos, isl_int *v)
344 {
345 if (!constraint)
346 return;
347
348 isl_assert(constraint->ctx, pos < n(constraint, type), return);
349 isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
350 }
351
352 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
353 {
354 if (!constraint)
355 return NULL;
356
357 isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
358 return NULL);
359 isl_assert(constraint->ctx,
360 !isl_int_is_zero(constraint->bmap->div[pos][0]), return NULL);
361 return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
362 }
363
364 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
365 {
366 if (!constraint)
367 return;
368 isl_int_set(constraint->line[0][0], v);
369 }
370
371 void isl_constraint_set_constant_si(__isl_keep isl_constraint *constraint,
372 int v)
373 {
374 if (!constraint)
375 return;
376 isl_int_set_si(constraint->line[0][0], v);
377 }
378
379 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
380 enum isl_dim_type type, int pos, isl_int v)
381 {
382 if (!constraint)
383 return;
384
385 isl_assert(constraint->ctx, pos < n(constraint, type), return);
386 isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
387 }
388
389 void isl_constraint_set_coefficient_si(__isl_keep isl_constraint *constraint,
390 enum isl_dim_type type, int pos, int v)
391 {
392 if (!constraint)
393 return;
394
395 isl_assert(constraint->ctx, pos < n(constraint, type), return);
396 isl_int_set_si(constraint->line[0][offset(constraint, type) + pos], v);
397 }
398
399 void isl_constraint_clear(struct isl_constraint *constraint)
400 {
401 unsigned total;
402
403 if (!constraint)
404 return;
405 total = isl_basic_map_total_dim(constraint->bmap);
406 isl_seq_clr(constraint->line[0], 1 + total);
407 }
408
409 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
410 {
411 unsigned total;
412
413 if (!constraint)
414 return NULL;
415
416 isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
417 goto error);
418 isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
419 total = isl_basic_map_total_dim(constraint->bmap);
420 isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
421 isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
422 ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
423 return constraint;
424 error:
425 isl_constraint_free(constraint);
426 return NULL;
427 }
428
429 int isl_constraint_is_equality(struct isl_constraint *constraint)
430 {
431 if (!constraint)
432 return -1;
433 return constraint->line >= constraint->bmap->eq;
434 }
435
436 int isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint)
437 {
438 int i;
439
440 if (!constraint)
441 return -1;
442 if (isl_constraint_is_equality(constraint))
443 return 0;
444 for (i = 0; i < constraint->bmap->n_div; ++i) {
445 if (isl_int_is_zero(constraint->bmap->div[i][0]))
446 continue;
447 if (isl_basic_map_is_div_constraint(constraint->bmap,
448 constraint->line[0], i))
449 return 1;
450 }
451
452 return 0;
453 }
454
455 /* We manually set ISL_BASIC_SET_FINAL instead of calling
456 * isl_basic_map_finalize because we want to keep the position
457 * of the divs and we therefore do not want to throw away redundant divs.
458 * This is arguably a bit fragile.
459 */
460 __isl_give isl_basic_map *isl_basic_map_from_constraint(
461 __isl_take isl_constraint *constraint)
462 {
463 int k;
464 struct isl_basic_map *bmap;
465 isl_int *c;
466 unsigned total;
467
468 if (!constraint)
469 return NULL;
470
471 if (constraint->bmap->n_eq == 1 && constraint->bmap->n_ineq == 0) {
472 bmap = isl_basic_map_copy(constraint->bmap);
473 isl_constraint_free(constraint);
474 return bmap;
475 }
476
477 bmap = isl_basic_map_universe_like(constraint->bmap);
478 bmap = isl_basic_map_align_divs(bmap, constraint->bmap);
479 bmap = isl_basic_map_cow(bmap);
480 bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
481 if (isl_constraint_is_equality(constraint)) {
482 k = isl_basic_map_alloc_equality(bmap);
483 if (k < 0)
484 goto error;
485 c = bmap->eq[k];
486 }
487 else {
488 k = isl_basic_map_alloc_inequality(bmap);
489 if (k < 0)
490 goto error;
491 c = bmap->ineq[k];
492 }
493 total = isl_basic_map_total_dim(bmap);
494 isl_seq_cpy(c, constraint->line[0], 1 + total);
495 isl_constraint_free(constraint);
496 if (bmap)
497 ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
498 return bmap;
499 error:
500 isl_constraint_free(constraint);
501 isl_basic_map_free(bmap);
502 return NULL;
503 }
504
505 struct isl_basic_set *isl_basic_set_from_constraint(
506 struct isl_constraint *constraint)
507 {
508 if (!constraint)
509 return NULL;
510
511 isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
512 return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
513 error:
514 isl_constraint_free(constraint);
515 return NULL;
516 }
517
518 int isl_basic_map_has_defining_equality(
519 __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos,
520 __isl_give isl_constraint **c)
521 {
522 int i;
523 unsigned offset;
524 unsigned total;
525
526 if (!bmap)
527 return -1;
528 offset = basic_map_offset(bmap, type);
529 total = isl_basic_map_total_dim(bmap);
530 isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
531 for (i = 0; i < bmap->n_eq; ++i)
532 if (!isl_int_is_zero(bmap->eq[i][offset + pos]) &&
533 isl_seq_first_non_zero(bmap->eq[i]+offset+pos+1,
534 1+total-offset-pos-1) == -1) {
535 *c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
536 &bmap->eq[i]);
537 return 1;
538 }
539 return 0;
540 }
541
542 int isl_basic_set_has_defining_equality(
543 __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos,
544 __isl_give isl_constraint **c)
545 {
546 return isl_basic_map_has_defining_equality((isl_basic_map *)bset,
547 type, pos, c);
548 }
549
550 int isl_basic_set_has_defining_inequalities(
551 struct isl_basic_set *bset, enum isl_dim_type type, int pos,
552 struct isl_constraint **lower,
553 struct isl_constraint **upper)
554 {
555 int i, j;
556 unsigned offset;
557 unsigned total;
558 isl_int m;
559 isl_int **lower_line, **upper_line;
560
561 if (!bset)
562 return -1;
563 offset = basic_set_offset(bset, type);
564 total = isl_basic_set_total_dim(bset);
565 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
566 isl_int_init(m);
567 for (i = 0; i < bset->n_ineq; ++i) {
568 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
569 continue;
570 if (isl_int_is_one(bset->ineq[i][offset + pos]))
571 continue;
572 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
573 continue;
574 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
575 1+total-offset-pos-1) != -1)
576 continue;
577 for (j = i + 1; j < bset->n_ineq; ++j) {
578 if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
579 total))
580 continue;
581 isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
582 if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
583 continue;
584
585 if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
586 lower_line = &bset->ineq[i];
587 upper_line = &bset->ineq[j];
588 } else {
589 lower_line = &bset->ineq[j];
590 upper_line = &bset->ineq[i];
591 }
592 *lower = isl_basic_set_constraint(
593 isl_basic_set_copy(bset), lower_line);
594 *upper = isl_basic_set_constraint(
595 isl_basic_set_copy(bset), upper_line);
596 isl_int_clear(m);
597 return 1;
598 }
599 }
600 *lower = NULL;
601 *upper = NULL;
602 isl_int_clear(m);
603 return 0;
604 }
605
606 /* Given two constraints "a" and "b" on the variable at position "abs_pos"
607 * (in "a" and "b"), add a constraint to "bset" that ensures that the
608 * bound implied by "a" is (strictly) larger than the bound implied by "b".
609 *
610 * If both constraints imply lower bounds, then this means that "a" is
611 * active in the result.
612 * If both constraints imply upper bounds, then this means that "b" is
613 * active in the result.
614 */
615 static __isl_give isl_basic_set *add_larger_bound_constraint(
616 __isl_take isl_basic_set *bset, isl_int *a, isl_int *b,
617 unsigned abs_pos, int strict)
618 {
619 int k;
620 isl_int t;
621 unsigned total;
622
623 k = isl_basic_set_alloc_inequality(bset);
624 if (k < 0)
625 goto error;
626
627 total = isl_basic_set_dim(bset, isl_dim_all);
628
629 isl_int_init(t);
630 isl_int_neg(t, b[1 + abs_pos]);
631
632 isl_seq_combine(bset->ineq[k], t, a, a[1 + abs_pos], b, 1 + abs_pos);
633 isl_seq_combine(bset->ineq[k] + 1 + abs_pos,
634 t, a + 1 + abs_pos + 1, a[1 + abs_pos], b + 1 + abs_pos + 1,
635 total - abs_pos);
636
637 if (strict)
638 isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
639
640 isl_int_clear(t);
641
642 return bset;
643 error:
644 isl_basic_set_free(bset);
645 return NULL;
646 }
647
648 /* Add constraints to "context" that ensure that "u" is the smallest
649 * (and therefore active) upper bound on "abs_pos" in "bset" and return
650 * the resulting basic set.
651 */
652 static __isl_give isl_basic_set *set_smallest_upper_bound(
653 __isl_keep isl_basic_set *context,
654 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u)
655 {
656 int j;
657
658 context = isl_basic_set_copy(context);
659 context = isl_basic_set_cow(context);
660
661 context = isl_basic_set_extend_constraints(context, 0, n_upper - 1);
662
663 for (j = 0; j < bset->n_ineq; ++j) {
664 if (j == u)
665 continue;
666 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
667 continue;
668 context = add_larger_bound_constraint(context,
669 bset->ineq[j], bset->ineq[u], abs_pos, j > u);
670 }
671
672 context = isl_basic_set_simplify(context);
673 context = isl_basic_set_finalize(context);
674
675 return context;
676 }
677
678 /* Add constraints to "context" that ensure that "u" is the largest
679 * (and therefore active) upper bound on "abs_pos" in "bset" and return
680 * the resulting basic set.
681 */
682 static __isl_give isl_basic_set *set_largest_lower_bound(
683 __isl_keep isl_basic_set *context,
684 __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l)
685 {
686 int j;
687
688 context = isl_basic_set_copy(context);
689 context = isl_basic_set_cow(context);
690
691 context = isl_basic_set_extend_constraints(context, 0, n_lower - 1);
692
693 for (j = 0; j < bset->n_ineq; ++j) {
694 if (j == l)
695 continue;
696 if (!isl_int_is_pos(bset->ineq[j][1 + abs_pos]))
697 continue;
698 context = add_larger_bound_constraint(context,
699 bset->ineq[l], bset->ineq[j], abs_pos, j > l);
700 }
701
702 context = isl_basic_set_simplify(context);
703 context = isl_basic_set_finalize(context);
704
705 return context;
706 }
707
708 static int foreach_upper_bound(__isl_keep isl_basic_set *bset,
709 enum isl_dim_type type, unsigned abs_pos,
710 __isl_take isl_basic_set *context, int n_upper,
711 int (*fn)(__isl_take isl_constraint *lower,
712 __isl_take isl_constraint *upper,
713 __isl_take isl_basic_set *bset, void *user), void *user)
714 {
715 isl_basic_set *context_i;
716 isl_constraint *upper = NULL;
717 int i;
718
719 for (i = 0; i < bset->n_ineq; ++i) {
720 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
721 continue;
722
723 context_i = set_smallest_upper_bound(context, bset,
724 abs_pos, n_upper, i);
725 if (isl_basic_set_is_empty(context_i)) {
726 isl_basic_set_free(context_i);
727 continue;
728 }
729 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
730 &bset->ineq[i]);
731 if (!upper || !context_i)
732 goto error;
733 if (fn(NULL, upper, context_i, user) < 0)
734 break;
735 }
736
737 isl_basic_set_free(context);
738
739 if (i < bset->n_ineq)
740 return -1;
741
742 return 0;
743 error:
744 isl_constraint_free(upper);
745 isl_basic_set_free(context_i);
746 isl_basic_set_free(context);
747 return -1;
748 }
749
750 static int foreach_lower_bound(__isl_keep isl_basic_set *bset,
751 enum isl_dim_type type, unsigned abs_pos,
752 __isl_take isl_basic_set *context, int n_lower,
753 int (*fn)(__isl_take isl_constraint *lower,
754 __isl_take isl_constraint *upper,
755 __isl_take isl_basic_set *bset, void *user), void *user)
756 {
757 isl_basic_set *context_i;
758 isl_constraint *lower = NULL;
759 int i;
760
761 for (i = 0; i < bset->n_ineq; ++i) {
762 if (isl_int_is_zero(bset->ineq[i][1 + abs_pos]))
763 continue;
764
765 context_i = set_largest_lower_bound(context, bset,
766 abs_pos, n_lower, i);
767 if (isl_basic_set_is_empty(context_i)) {
768 isl_basic_set_free(context_i);
769 continue;
770 }
771 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
772 &bset->ineq[i]);
773 if (!lower || !context_i)
774 goto error;
775 if (fn(lower, NULL, context_i, user) < 0)
776 break;
777 }
778
779 isl_basic_set_free(context);
780
781 if (i < bset->n_ineq)
782 return -1;
783
784 return 0;
785 error:
786 isl_constraint_free(lower);
787 isl_basic_set_free(context_i);
788 isl_basic_set_free(context);
789 return -1;
790 }
791
792 static int foreach_bound_pair(__isl_keep isl_basic_set *bset,
793 enum isl_dim_type type, unsigned abs_pos,
794 __isl_take isl_basic_set *context, int n_lower, int n_upper,
795 int (*fn)(__isl_take isl_constraint *lower,
796 __isl_take isl_constraint *upper,
797 __isl_take isl_basic_set *bset, void *user), void *user)
798 {
799 isl_basic_set *context_i, *context_j;
800 isl_constraint *lower = NULL;
801 isl_constraint *upper = NULL;
802 int i, j;
803
804 for (i = 0; i < bset->n_ineq; ++i) {
805 if (!isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
806 continue;
807
808 context_i = set_largest_lower_bound(context, bset,
809 abs_pos, n_lower, i);
810 if (isl_basic_set_is_empty(context_i)) {
811 isl_basic_set_free(context_i);
812 continue;
813 }
814
815 for (j = 0; j < bset->n_ineq; ++j) {
816 if (!isl_int_is_neg(bset->ineq[j][1 + abs_pos]))
817 continue;
818
819 context_j = set_smallest_upper_bound(context_i, bset,
820 abs_pos, n_upper, j);
821 context_j = isl_basic_set_extend_constraints(context_j,
822 0, 1);
823 context_j = add_larger_bound_constraint(context_j,
824 bset->ineq[i], bset->ineq[j], abs_pos, 0);
825 context_j = isl_basic_set_simplify(context_j);
826 context_j = isl_basic_set_finalize(context_j);
827 if (isl_basic_set_is_empty(context_j)) {
828 isl_basic_set_free(context_j);
829 continue;
830 }
831 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
832 &bset->ineq[i]);
833 upper = isl_basic_set_constraint(isl_basic_set_copy(bset),
834 &bset->ineq[j]);
835 if (!lower || !upper || !context_j)
836 goto error;
837 if (fn(lower, upper, context_j, user) < 0)
838 break;
839 }
840
841 isl_basic_set_free(context_i);
842
843 if (j < bset->n_ineq)
844 break;
845 }
846
847 isl_basic_set_free(context);
848
849 if (i < bset->n_ineq)
850 return -1;
851
852 return 0;
853 error:
854 isl_constraint_free(lower);
855 isl_constraint_free(upper);
856 isl_basic_set_free(context_i);
857 isl_basic_set_free(context_j);
858 isl_basic_set_free(context);
859 return -1;
860 }
861
862 /* For each pair of lower and upper bounds on the variable "pos"
863 * of type "type", call "fn" with these lower and upper bounds and the
864 * set of constraints on the remaining variables where these bounds
865 * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds.
866 *
867 * If the designated variable is equal to an affine combination of the
868 * other variables then fn is called with both lower and upper
869 * set to the corresponding equality.
870 *
871 * If there is no lower (or upper) bound, then NULL is passed
872 * as the corresponding bound.
873 *
874 * We first check if the variable is involved in any equality.
875 * If not, we count the number of lower and upper bounds and
876 * act accordingly.
877 */
878 int isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset,
879 enum isl_dim_type type, unsigned pos,
880 int (*fn)(__isl_take isl_constraint *lower,
881 __isl_take isl_constraint *upper,
882 __isl_take isl_basic_set *bset, void *user), void *user)
883 {
884 int i;
885 isl_constraint *lower = NULL;
886 isl_constraint *upper = NULL;
887 isl_basic_set *context = NULL;
888 unsigned abs_pos;
889 int n_lower, n_upper;
890
891 if (!bset)
892 return -1;
893 isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
894 isl_assert(bset->ctx, type == isl_dim_param || type == isl_dim_set,
895 return -1);
896
897 abs_pos = pos;
898 if (type == isl_dim_set)
899 abs_pos += isl_basic_set_dim(bset, isl_dim_param);
900
901 for (i = 0; i < bset->n_eq; ++i) {
902 if (isl_int_is_zero(bset->eq[i][1 + abs_pos]))
903 continue;
904
905 lower = isl_basic_set_constraint(isl_basic_set_copy(bset),
906 &bset->eq[i]);
907 upper = isl_constraint_copy(lower);
908 context = isl_basic_set_remove_dims(isl_basic_set_copy(bset),
909 type, pos, 1);
910 if (!lower || !upper || !context)
911 goto error;
912 return fn(lower, upper, context, user);
913 }
914
915 n_lower = 0;
916 n_upper = 0;
917 for (i = 0; i < bset->n_ineq; ++i) {
918 if (isl_int_is_pos(bset->ineq[i][1 + abs_pos]))
919 n_lower++;
920 else if (isl_int_is_neg(bset->ineq[i][1 + abs_pos]))
921 n_upper++;
922 }
923
924 context = isl_basic_set_copy(bset);
925 context = isl_basic_set_cow(context);
926 if (!context)
927 goto error;
928 for (i = context->n_ineq - 1; i >= 0; --i)
929 if (!isl_int_is_zero(context->ineq[i][1 + abs_pos]))
930 isl_basic_set_drop_inequality(context, i);
931
932 context = isl_basic_set_drop(context, type, pos, 1);
933 if (!n_lower && !n_upper)
934 return fn(NULL, NULL, context, user);
935 if (!n_lower)
936 return foreach_upper_bound(bset, type, abs_pos, context, n_upper,
937 fn, user);
938 if (!n_upper)
939 return foreach_lower_bound(bset, type, abs_pos, context, n_lower,
940 fn, user);
941 return foreach_bound_pair(bset, type, abs_pos, context, n_lower, n_upper,
942 fn, user);
943 error:
944 isl_constraint_free(lower);
945 isl_constraint_free(upper);
946 isl_basic_set_free(context);
947 return -1;
948 }
Integer set library