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