Merge branch 'maint'
[isl.git] / isl_fold.c
blob57e7af5a5d84dcdbab8d519ed7519327a0404578
1 /*
2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
11 #include <isl_union_map_private.h>
12 #include <isl_polynomial_private.h>
13 #include <isl_point_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_map_private.h>
16 #include <isl/lp.h>
17 #include <isl/seq.h>
18 #include <isl_mat_private.h>
20 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
21 enum isl_fold type, __isl_take isl_dim *dim, int n)
23 isl_qpolynomial_fold *fold;
25 if (!dim)
26 goto error;
28 isl_assert(dim->ctx, n >= 0, goto error);
29 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
30 sizeof(struct isl_qpolynomial_fold) +
31 (n - 1) * sizeof(struct isl_qpolynomial *));
32 if (!fold)
33 goto error;
35 fold->ref = 1;
36 fold->size = n;
37 fold->n = 0;
38 fold->type = type;
39 fold->dim = dim;
41 return fold;
42 error:
43 isl_dim_free(dim);
44 return NULL;
47 isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold)
49 return fold ? fold->dim->ctx : NULL;
52 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_dim(
53 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
55 int i;
57 fold = isl_qpolynomial_fold_cow(fold);
58 if (!fold || !dim)
59 goto error;
61 for (i = 0; i < fold->n; ++i) {
62 fold->qp[i] = isl_qpolynomial_reset_dim(fold->qp[i],
63 isl_dim_copy(dim));
64 if (!fold->qp[i])
65 goto error;
68 isl_dim_free(fold->dim);
69 fold->dim = dim;
71 return fold;
72 error:
73 isl_qpolynomial_fold_free(fold);
74 isl_dim_free(dim);
75 return NULL;
78 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
79 enum isl_dim_type type, unsigned first, unsigned n)
81 int i;
83 if (!fold)
84 return -1;
85 if (fold->n == 0 || n == 0)
86 return 0;
88 for (i = 0; i < fold->n; ++i) {
89 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
90 type, first, n);
91 if (involves < 0 || involves)
92 return involves;
94 return 0;
97 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name(
98 __isl_take isl_qpolynomial_fold *fold,
99 enum isl_dim_type type, unsigned pos, const char *s)
101 int i;
103 fold = isl_qpolynomial_fold_cow(fold);
104 if (!fold)
105 return NULL;
106 fold->dim = isl_dim_set_name(fold->dim, type, pos, s);
107 if (!fold->dim)
108 goto error;
110 for (i = 0; i < fold->n; ++i) {
111 fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i],
112 type, pos, s);
113 if (!fold->qp[i])
114 goto error;
117 return fold;
118 error:
119 isl_qpolynomial_fold_free(fold);
120 return NULL;
123 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
124 __isl_take isl_qpolynomial_fold *fold,
125 enum isl_dim_type type, unsigned first, unsigned n)
127 int i;
129 if (!fold)
130 return NULL;
131 if (n == 0)
132 return fold;
134 fold = isl_qpolynomial_fold_cow(fold);
135 if (!fold)
136 return NULL;
137 fold->dim = isl_dim_drop(fold->dim, type, first, n);
138 if (!fold->dim)
139 goto error;
141 for (i = 0; i < fold->n; ++i) {
142 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
143 type, first, n);
144 if (!fold->qp[i])
145 goto error;
148 return fold;
149 error:
150 isl_qpolynomial_fold_free(fold);
151 return NULL;
154 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims(
155 __isl_take isl_qpolynomial_fold *fold,
156 enum isl_dim_type type, unsigned first, unsigned n)
158 int i;
160 if (!fold)
161 return NULL;
162 if (n == 0 && !isl_dim_is_named_or_nested(fold->dim, type))
163 return fold;
165 fold = isl_qpolynomial_fold_cow(fold);
166 if (!fold)
167 return NULL;
168 fold->dim = isl_dim_insert(fold->dim, type, first, n);
169 if (!fold->dim)
170 goto error;
172 for (i = 0; i < fold->n; ++i) {
173 fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i],
174 type, first, n);
175 if (!fold->qp[i])
176 goto error;
179 return fold;
180 error:
181 isl_qpolynomial_fold_free(fold);
182 return NULL;
185 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
187 struct isl_upoly_cst *cst;
189 cst = isl_upoly_as_cst(qp->upoly);
190 if (!cst)
191 return 0;
193 return isl_int_sgn(cst->n) < 0 ? -1 : 1;
196 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
197 __isl_keep isl_qpolynomial *qp)
199 enum isl_lp_result res;
200 isl_vec *aff;
201 isl_int opt;
202 int sgn = 0;
204 aff = isl_qpolynomial_extract_affine(qp);
205 if (!aff)
206 return 0;
208 isl_int_init(opt);
210 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
211 &opt, NULL, NULL);
212 if (res == isl_lp_error)
213 goto done;
214 if (res == isl_lp_empty ||
215 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
216 sgn = 1;
217 goto done;
220 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
221 &opt, NULL, NULL);
222 if (res == isl_lp_ok && !isl_int_is_pos(opt))
223 sgn = -1;
225 done:
226 isl_int_clear(opt);
227 isl_vec_free(aff);
228 return sgn;
231 /* Determine, if possible, the sign of the quasipolynomial "qp" on
232 * the domain "set".
234 * If qp is a constant, then the problem is trivial.
235 * If qp is linear, then we check if the minimum of the corresponding
236 * affine constraint is non-negative or if the maximum is non-positive.
238 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
239 * in "set". If so, we write qp(v,v') as
241 * q(v,v') * (v - l) + r(v')
243 * if q(v,v') and r(v') have the same known sign, then the original
244 * quasipolynomial has the same sign as well.
246 * Return
247 * -1 if qp <= 0
248 * 1 if qp >= 0
249 * 0 if unknown
251 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
252 __isl_keep isl_qpolynomial *qp)
254 int d;
255 int i;
256 int is;
257 struct isl_upoly_rec *rec;
258 isl_vec *v;
259 isl_int l;
260 enum isl_lp_result res;
261 int sgn = 0;
263 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
264 if (is < 0)
265 return 0;
266 if (is)
267 return isl_qpolynomial_cst_sign(qp);
269 is = isl_qpolynomial_is_affine(qp);
270 if (is < 0)
271 return 0;
272 if (is)
273 return isl_qpolynomial_aff_sign(set, qp);
275 if (qp->div->n_row > 0)
276 return 0;
278 rec = isl_upoly_as_rec(qp->upoly);
279 if (!rec)
280 return 0;
282 d = isl_dim_total(qp->dim);
283 v = isl_vec_alloc(set->ctx, 2 + d);
284 if (!v)
285 return 0;
287 isl_seq_clr(v->el + 1, 1 + d);
288 isl_int_set_si(v->el[0], 1);
289 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
291 isl_int_init(l);
293 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
294 if (res == isl_lp_ok) {
295 isl_qpolynomial *min;
296 isl_qpolynomial *base;
297 isl_qpolynomial *r, *q;
298 isl_qpolynomial *t;
300 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
301 base = isl_qpolynomial_var_pow(isl_dim_copy(qp->dim),
302 qp->upoly->var, 1);
304 r = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
305 isl_upoly_copy(rec->p[rec->n - 1]));
306 q = isl_qpolynomial_copy(r);
308 for (i = rec->n - 2; i >= 0; --i) {
309 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
310 t = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
311 isl_upoly_copy(rec->p[i]));
312 r = isl_qpolynomial_add(r, t);
313 if (i == 0)
314 break;
315 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
316 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
319 if (isl_qpolynomial_is_zero(q))
320 sgn = isl_qpolynomial_sign(set, r);
321 else if (isl_qpolynomial_is_zero(r))
322 sgn = isl_qpolynomial_sign(set, q);
323 else {
324 int sgn_q, sgn_r;
325 sgn_r = isl_qpolynomial_sign(set, r);
326 sgn_q = isl_qpolynomial_sign(set, q);
327 if (sgn_r == sgn_q)
328 sgn = sgn_r;
331 isl_qpolynomial_free(min);
332 isl_qpolynomial_free(base);
333 isl_qpolynomial_free(q);
334 isl_qpolynomial_free(r);
337 isl_int_clear(l);
339 isl_vec_free(v);
341 return sgn;
344 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
345 __isl_keep isl_set *set,
346 __isl_take isl_qpolynomial_fold *fold1,
347 __isl_take isl_qpolynomial_fold *fold2)
349 int i, j;
350 int n1;
351 struct isl_qpolynomial_fold *res = NULL;
352 int better;
354 if (!fold1 || !fold2)
355 goto error;
357 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
358 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
359 goto error);
361 better = fold1->type == isl_fold_max ? -1 : 1;
363 if (isl_qpolynomial_fold_is_empty(fold1)) {
364 isl_qpolynomial_fold_free(fold1);
365 return fold2;
368 if (isl_qpolynomial_fold_is_empty(fold2)) {
369 isl_qpolynomial_fold_free(fold2);
370 return fold1;
373 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
374 fold1->n + fold2->n);
375 if (!res)
376 goto error;
378 for (i = 0; i < fold1->n; ++i) {
379 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
380 if (!res->qp[res->n])
381 goto error;
382 res->n++;
384 n1 = res->n;
386 for (i = 0; i < fold2->n; ++i) {
387 for (j = n1 - 1; j >= 0; --j) {
388 isl_qpolynomial *d;
389 int sgn;
390 d = isl_qpolynomial_sub(
391 isl_qpolynomial_copy(res->qp[j]),
392 isl_qpolynomial_copy(fold2->qp[i]));
393 sgn = isl_qpolynomial_sign(set, d);
394 isl_qpolynomial_free(d);
395 if (sgn == 0)
396 continue;
397 if (sgn != better)
398 break;
399 isl_qpolynomial_free(res->qp[j]);
400 if (j != n1 - 1)
401 res->qp[j] = res->qp[n1 - 1];
402 n1--;
403 if (n1 != res->n - 1)
404 res->qp[n1] = res->qp[res->n - 1];
405 res->n--;
407 if (j >= 0)
408 continue;
409 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
410 if (!res->qp[res->n])
411 goto error;
412 res->n++;
415 isl_qpolynomial_fold_free(fold1);
416 isl_qpolynomial_fold_free(fold2);
418 return res;
419 error:
420 isl_qpolynomial_fold_free(res);
421 isl_qpolynomial_fold_free(fold1);
422 isl_qpolynomial_fold_free(fold2);
423 return NULL;
426 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
427 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
429 int i;
431 if (!fold || !qp)
432 goto error;
434 if (isl_qpolynomial_is_zero(qp)) {
435 isl_qpolynomial_free(qp);
436 return fold;
439 fold = isl_qpolynomial_fold_cow(fold);
440 if (!fold)
441 goto error;
443 for (i = 0; i < fold->n; ++i) {
444 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
445 isl_qpolynomial_copy(qp));
446 if (!fold->qp[i])
447 goto error;
450 isl_qpolynomial_free(qp);
451 return fold;
452 error:
453 isl_qpolynomial_fold_free(fold);
454 isl_qpolynomial_free(qp);
455 return NULL;
458 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
459 __isl_keep isl_set *dom,
460 __isl_take isl_qpolynomial_fold *fold1,
461 __isl_take isl_qpolynomial_fold *fold2)
463 int i;
464 isl_qpolynomial_fold *res = NULL;
466 if (!fold1 || !fold2)
467 goto error;
469 if (isl_qpolynomial_fold_is_empty(fold1)) {
470 isl_qpolynomial_fold_free(fold1);
471 return fold2;
474 if (isl_qpolynomial_fold_is_empty(fold2)) {
475 isl_qpolynomial_fold_free(fold2);
476 return fold1;
479 if (fold1->n == 1 && fold2->n != 1)
480 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
482 if (fold2->n == 1) {
483 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
484 isl_qpolynomial_copy(fold2->qp[0]));
485 isl_qpolynomial_fold_free(fold2);
486 return res;
489 res = isl_qpolynomial_fold_add_qpolynomial(
490 isl_qpolynomial_fold_copy(fold1),
491 isl_qpolynomial_copy(fold2->qp[0]));
493 for (i = 1; i < fold2->n; ++i) {
494 isl_qpolynomial_fold *res_i;
495 res_i = isl_qpolynomial_fold_add_qpolynomial(
496 isl_qpolynomial_fold_copy(fold1),
497 isl_qpolynomial_copy(fold2->qp[i]));
498 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
501 isl_qpolynomial_fold_free(fold1);
502 isl_qpolynomial_fold_free(fold2);
503 return res;
504 error:
505 isl_qpolynomial_fold_free(res);
506 isl_qpolynomial_fold_free(fold1);
507 isl_qpolynomial_fold_free(fold2);
508 return NULL;
511 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
512 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
514 int i;
516 if (!fold || !eq)
517 goto error;
519 fold = isl_qpolynomial_fold_cow(fold);
520 if (!fold)
521 return NULL;
523 for (i = 0; i < fold->n; ++i) {
524 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
525 isl_basic_set_copy(eq));
526 if (!fold->qp[i])
527 goto error;
530 isl_basic_set_free(eq);
531 return fold;
532 error:
533 isl_basic_set_free(eq);
534 isl_qpolynomial_fold_free(fold);
535 return NULL;
538 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
539 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
541 int i;
543 if (!fold || !context)
544 goto error;
546 fold = isl_qpolynomial_fold_cow(fold);
547 if (!fold)
548 return NULL;
550 for (i = 0; i < fold->n; ++i) {
551 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
552 isl_set_copy(context));
553 if (!fold->qp[i])
554 goto error;
557 isl_set_free(context);
558 return fold;
559 error:
560 isl_set_free(context);
561 isl_qpolynomial_fold_free(fold);
562 return NULL;
565 #define HAS_TYPE
567 #undef PW
568 #define PW isl_pw_qpolynomial_fold
569 #undef EL
570 #define EL isl_qpolynomial_fold
571 #undef IS_ZERO
572 #define IS_ZERO is_empty
573 #undef FIELD
574 #define FIELD fold
576 #include <isl_pw_templ.c>
578 #undef UNION
579 #define UNION isl_union_pw_qpolynomial_fold
580 #undef PART
581 #define PART isl_pw_qpolynomial_fold
582 #undef PARTS
583 #define PARTS pw_qpolynomial_fold
585 #include <isl_union_templ.c>
587 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
588 __isl_take isl_dim *dim)
590 return qpolynomial_fold_alloc(type, dim, 0);
593 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
594 enum isl_fold type, __isl_take isl_qpolynomial *qp)
596 isl_qpolynomial_fold *fold;
598 if (!qp)
599 return NULL;
601 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
602 if (!fold)
603 goto error;
605 fold->qp[0] = qp;
606 fold->n++;
608 return fold;
609 error:
610 isl_qpolynomial_fold_free(fold);
611 isl_qpolynomial_free(qp);
612 return NULL;
615 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
616 __isl_keep isl_qpolynomial_fold *fold)
618 if (!fold)
619 return NULL;
621 fold->ref++;
622 return fold;
625 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
626 __isl_keep isl_qpolynomial_fold *fold)
628 int i;
629 isl_qpolynomial_fold *dup;
631 if (!fold)
632 return NULL;
633 dup = qpolynomial_fold_alloc(fold->type,
634 isl_dim_copy(fold->dim), fold->n);
635 if (!dup)
636 return NULL;
638 dup->n = fold->n;
639 for (i = 0; i < fold->n; ++i) {
640 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
641 if (!dup->qp[i])
642 goto error;
645 return dup;
646 error:
647 isl_qpolynomial_fold_free(dup);
648 return NULL;
651 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
652 __isl_take isl_qpolynomial_fold *fold)
654 if (!fold)
655 return NULL;
657 if (fold->ref == 1)
658 return fold;
659 fold->ref--;
660 return isl_qpolynomial_fold_dup(fold);
663 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
665 int i;
667 if (!fold)
668 return;
669 if (--fold->ref > 0)
670 return;
672 for (i = 0; i < fold->n; ++i)
673 isl_qpolynomial_free(fold->qp[i]);
674 isl_dim_free(fold->dim);
675 free(fold);
678 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
680 if (!fold)
681 return -1;
683 return fold->n == 0;
686 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
687 __isl_take isl_qpolynomial_fold *fold1,
688 __isl_take isl_qpolynomial_fold *fold2)
690 int i;
691 struct isl_qpolynomial_fold *res = NULL;
693 if (!fold1 || !fold2)
694 goto error;
696 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
697 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
698 goto error);
700 if (isl_qpolynomial_fold_is_empty(fold1)) {
701 isl_qpolynomial_fold_free(fold1);
702 return fold2;
705 if (isl_qpolynomial_fold_is_empty(fold2)) {
706 isl_qpolynomial_fold_free(fold2);
707 return fold1;
710 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
711 fold1->n + fold2->n);
712 if (!res)
713 goto error;
715 for (i = 0; i < fold1->n; ++i) {
716 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
717 if (!res->qp[res->n])
718 goto error;
719 res->n++;
722 for (i = 0; i < fold2->n; ++i) {
723 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
724 if (!res->qp[res->n])
725 goto error;
726 res->n++;
729 isl_qpolynomial_fold_free(fold1);
730 isl_qpolynomial_fold_free(fold2);
732 return res;
733 error:
734 isl_qpolynomial_fold_free(res);
735 isl_qpolynomial_fold_free(fold1);
736 isl_qpolynomial_fold_free(fold2);
737 return NULL;
740 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
741 __isl_take isl_pw_qpolynomial_fold *pw1,
742 __isl_take isl_pw_qpolynomial_fold *pw2)
744 int i, j, n;
745 struct isl_pw_qpolynomial_fold *res;
746 isl_set *set;
748 if (!pw1 || !pw2)
749 goto error;
751 isl_assert(pw1->dim->ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
753 if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
754 isl_pw_qpolynomial_fold_free(pw1);
755 return pw2;
758 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
759 isl_pw_qpolynomial_fold_free(pw2);
760 return pw1;
763 if (pw1->type != pw2->type)
764 isl_die(set->ctx, isl_error_invalid, "fold types don't match",
765 goto error);
767 n = (pw1->n + 1) * (pw2->n + 1);
768 res = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1->dim),
769 pw1->type, n);
771 for (i = 0; i < pw1->n; ++i) {
772 set = isl_set_copy(pw1->p[i].set);
773 for (j = 0; j < pw2->n; ++j) {
774 struct isl_set *common;
775 isl_qpolynomial_fold *sum;
776 set = isl_set_subtract(set,
777 isl_set_copy(pw2->p[j].set));
778 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
779 isl_set_copy(pw2->p[j].set));
780 if (isl_set_fast_is_empty(common)) {
781 isl_set_free(common);
782 continue;
785 sum = isl_qpolynomial_fold_fold_on_domain(common,
786 isl_qpolynomial_fold_copy(pw1->p[i].fold),
787 isl_qpolynomial_fold_copy(pw2->p[j].fold));
789 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
791 res = isl_pw_qpolynomial_fold_add_piece(res, set,
792 isl_qpolynomial_fold_copy(pw1->p[i].fold));
795 for (j = 0; j < pw2->n; ++j) {
796 set = isl_set_copy(pw2->p[j].set);
797 for (i = 0; i < pw1->n; ++i)
798 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
799 res = isl_pw_qpolynomial_fold_add_piece(res, set,
800 isl_qpolynomial_fold_copy(pw2->p[j].fold));
803 isl_pw_qpolynomial_fold_free(pw1);
804 isl_pw_qpolynomial_fold_free(pw2);
806 return res;
807 error:
808 isl_pw_qpolynomial_fold_free(pw1);
809 isl_pw_qpolynomial_fold_free(pw2);
810 return NULL;
813 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
814 __isl_take isl_union_pw_qpolynomial_fold *u,
815 __isl_take isl_pw_qpolynomial_fold *part)
817 uint32_t hash;
818 struct isl_hash_table_entry *entry;
820 u = isl_union_pw_qpolynomial_fold_cow(u);
822 if (!part || !u)
823 goto error;
825 isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
826 isl_dim_param), goto error);
828 hash = isl_dim_get_hash(part->dim);
829 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
830 &has_dim, part->dim, 1);
831 if (!entry)
832 goto error;
834 if (!entry->data)
835 entry->data = part;
836 else {
837 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
838 isl_pw_qpolynomial_fold_copy(part));
839 if (!entry->data)
840 goto error;
841 isl_pw_qpolynomial_fold_free(part);
844 return u;
845 error:
846 isl_pw_qpolynomial_fold_free(part);
847 isl_union_pw_qpolynomial_fold_free(u);
848 return NULL;
851 static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
853 isl_union_pw_qpolynomial_fold **u;
854 u = (isl_union_pw_qpolynomial_fold **)user;
856 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
858 return 0;
861 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
862 __isl_take isl_union_pw_qpolynomial_fold *u1,
863 __isl_take isl_union_pw_qpolynomial_fold *u2)
865 u1 = isl_union_pw_qpolynomial_fold_cow(u1);
867 if (!u1 || !u2)
868 goto error;
870 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
871 &fold_part, &u1) < 0)
872 goto error;
874 isl_union_pw_qpolynomial_fold_free(u2);
876 return u1;
877 error:
878 isl_union_pw_qpolynomial_fold_free(u1);
879 isl_union_pw_qpolynomial_fold_free(u2);
880 return NULL;
883 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
884 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
886 int i;
887 isl_pw_qpolynomial_fold *pwf;
889 if (!pwqp)
890 return NULL;
892 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), type,
893 pwqp->n);
895 for (i = 0; i < pwqp->n; ++i)
896 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
897 isl_set_copy(pwqp->p[i].set),
898 isl_qpolynomial_fold_alloc(type,
899 isl_qpolynomial_copy(pwqp->p[i].qp)));
901 isl_pw_qpolynomial_free(pwqp);
903 return pwf;
906 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
907 __isl_keep isl_qpolynomial_fold *fold2)
909 int i;
911 if (!fold1 || !fold2)
912 return -1;
914 if (fold1->n != fold2->n)
915 return 0;
917 /* We probably want to sort the qps first... */
918 for (i = 0; i < fold1->n; ++i) {
919 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
920 if (eq < 0 || !eq)
921 return eq;
924 return 1;
927 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
928 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
930 isl_qpolynomial *qp;
932 if (!fold || !pnt)
933 goto error;
934 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
935 isl_assert(pnt->dim->ctx,
936 fold->type == isl_fold_max || fold->type == isl_fold_min,
937 goto error);
939 if (fold->n == 0)
940 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
941 else {
942 int i;
943 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
944 isl_point_copy(pnt));
945 for (i = 1; i < fold->n; ++i) {
946 isl_qpolynomial *qp_i;
947 qp_i = isl_qpolynomial_eval(
948 isl_qpolynomial_copy(fold->qp[i]),
949 isl_point_copy(pnt));
950 if (fold->type == isl_fold_max)
951 qp = isl_qpolynomial_max_cst(qp, qp_i);
952 else
953 qp = isl_qpolynomial_min_cst(qp, qp_i);
956 isl_qpolynomial_fold_free(fold);
957 isl_point_free(pnt);
959 return qp;
960 error:
961 isl_qpolynomial_fold_free(fold);
962 isl_point_free(pnt);
963 return NULL;
966 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
968 int i;
969 size_t n = 0;
971 for (i = 0; i < pwf->n; ++i)
972 n += pwf->p[i].fold->n;
974 return n;
977 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
978 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
980 int i;
981 isl_qpolynomial *opt;
983 if (!set || !fold)
984 goto error;
986 if (fold->n == 0) {
987 isl_dim *dim = isl_dim_copy(fold->dim);
988 isl_set_free(set);
989 isl_qpolynomial_fold_free(fold);
990 return isl_qpolynomial_zero(dim);
993 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
994 isl_set_copy(set), max);
995 for (i = 1; i < fold->n; ++i) {
996 isl_qpolynomial *opt_i;
997 opt_i = isl_qpolynomial_opt_on_domain(
998 isl_qpolynomial_copy(fold->qp[i]),
999 isl_set_copy(set), max);
1000 if (max)
1001 opt = isl_qpolynomial_max_cst(opt, opt_i);
1002 else
1003 opt = isl_qpolynomial_min_cst(opt, opt_i);
1006 isl_set_free(set);
1007 isl_qpolynomial_fold_free(fold);
1009 return opt;
1010 error:
1011 isl_set_free(set);
1012 isl_qpolynomial_fold_free(fold);
1013 return NULL;
1016 /* Check whether for each quasi-polynomial in "fold2" there is
1017 * a quasi-polynomial in "fold1" that dominates it on "set".
1019 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1020 __isl_keep isl_qpolynomial_fold *fold1,
1021 __isl_keep isl_qpolynomial_fold *fold2)
1023 int i, j;
1024 int covers;
1026 if (!set || !fold1 || !fold2)
1027 return -1;
1029 covers = fold1->type == isl_fold_max ? 1 : -1;
1031 for (i = 0; i < fold2->n; ++i) {
1032 for (j = 0; j < fold1->n; ++j) {
1033 isl_qpolynomial *d;
1034 int sgn;
1036 d = isl_qpolynomial_sub(
1037 isl_qpolynomial_copy(fold1->qp[j]),
1038 isl_qpolynomial_copy(fold2->qp[i]));
1039 sgn = isl_qpolynomial_sign(set, d);
1040 isl_qpolynomial_free(d);
1041 if (sgn == covers)
1042 break;
1044 if (j >= fold1->n)
1045 return 0;
1048 return 1;
1051 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1052 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1053 * that of pwf2.
1055 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1056 __isl_keep isl_pw_qpolynomial_fold *pwf2)
1058 int i, j;
1059 isl_set *dom1, *dom2;
1060 int is_subset;
1062 if (!pwf1 || !pwf2)
1063 return -1;
1065 if (pwf2->n == 0)
1066 return 1;
1067 if (pwf1->n == 0)
1068 return 0;
1070 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1071 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1072 is_subset = isl_set_is_subset(dom2, dom1);
1073 isl_set_free(dom1);
1074 isl_set_free(dom2);
1076 if (is_subset < 0 || !is_subset)
1077 return is_subset;
1079 for (i = 0; i < pwf2->n; ++i) {
1080 for (j = 0; j < pwf1->n; ++j) {
1081 int is_empty;
1082 isl_set *common;
1083 int covers;
1085 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1086 isl_set_copy(pwf2->p[i].set));
1087 is_empty = isl_set_is_empty(common);
1088 if (is_empty < 0 || is_empty) {
1089 isl_set_free(common);
1090 if (is_empty < 0)
1091 return -1;
1092 continue;
1094 covers = qpolynomial_fold_covers_on_domain(common,
1095 pwf1->p[j].fold, pwf2->p[i].fold);
1096 isl_set_free(common);
1097 if (covers < 0 || !covers)
1098 return covers;
1102 return 1;
1105 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
1106 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1108 int i;
1109 isl_ctx *ctx;
1111 if (!fold || !morph)
1112 goto error;
1114 ctx = fold->dim->ctx;
1115 isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
1117 fold = isl_qpolynomial_fold_cow(fold);
1118 if (!fold)
1119 goto error;
1121 isl_dim_free(fold->dim);
1122 fold->dim = isl_dim_copy(morph->ran->dim);
1123 if (!fold->dim)
1124 goto error;
1126 for (i = 0; i < fold->n; ++i) {
1127 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
1128 isl_morph_copy(morph));
1129 if (!fold->qp[i])
1130 goto error;
1133 isl_morph_free(morph);
1135 return fold;
1136 error:
1137 isl_qpolynomial_fold_free(fold);
1138 isl_morph_free(morph);
1139 return NULL;
1142 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1144 if (!fold)
1145 return isl_fold_list;
1146 return fold->type;
1149 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1150 __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1152 if (!upwf)
1153 return isl_fold_list;
1154 return upwf->type;
1157 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1158 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
1160 int i;
1161 isl_ctx *ctx;
1163 if (!fold || !dim)
1164 goto error;
1166 if (isl_dim_equal(fold->dim, dim)) {
1167 isl_dim_free(dim);
1168 return fold;
1171 fold = isl_qpolynomial_fold_cow(fold);
1172 if (!fold)
1173 goto error;
1175 isl_dim_free(fold->dim);
1176 fold->dim = isl_dim_copy(dim);
1177 if (!fold->dim)
1178 goto error;
1180 for (i = 0; i < fold->n; ++i) {
1181 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1182 isl_dim_copy(dim));
1183 if (!fold->qp[i])
1184 goto error;
1187 isl_dim_free(dim);
1189 return fold;
1190 error:
1191 isl_qpolynomial_fold_free(fold);
1192 isl_dim_free(dim);
1193 return NULL;
1196 int isl_qpolynomial_fold_foreach_qpolynomial(
1197 __isl_keep isl_qpolynomial_fold *fold,
1198 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1200 int i;
1202 if (!fold)
1203 return -1;
1205 for (i = 0; i < fold->n; ++i)
1206 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1207 return -1;
1209 return 0;
1212 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1213 __isl_take isl_qpolynomial_fold *fold,
1214 enum isl_dim_type dst_type, unsigned dst_pos,
1215 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1217 int i;
1219 if (n == 0)
1220 return fold;
1222 fold = isl_qpolynomial_fold_cow(fold);
1223 if (!fold)
1224 return NULL;
1226 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
1227 src_type, src_pos, n);
1228 if (!fold->dim)
1229 goto error;
1231 for (i = 0; i < fold->n; ++i) {
1232 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1233 dst_type, dst_pos, src_type, src_pos, n);
1234 if (!fold->qp[i])
1235 goto error;
1238 return fold;
1239 error:
1240 isl_qpolynomial_fold_free(fold);
1241 return NULL;
1244 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1245 * in fold->qp[k] by subs[i].
1247 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1248 __isl_take isl_qpolynomial_fold *fold,
1249 enum isl_dim_type type, unsigned first, unsigned n,
1250 __isl_keep isl_qpolynomial **subs)
1252 int i;
1254 if (n == 0)
1255 return fold;
1257 fold = isl_qpolynomial_fold_cow(fold);
1258 if (!fold)
1259 return NULL;
1261 for (i = 0; i < fold->n; ++i) {
1262 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1263 type, first, n, subs);
1264 if (!fold->qp[i])
1265 goto error;
1268 return fold;
1269 error:
1270 isl_qpolynomial_fold_free(fold);
1271 return NULL;
1274 static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1276 isl_ctx *ctx;
1277 isl_pw_qpolynomial_fold *pwf;
1278 isl_union_pw_qpolynomial_fold **upwf;
1279 uint32_t hash;
1280 struct isl_hash_table_entry *entry;
1282 upwf = (isl_union_pw_qpolynomial_fold **)user;
1284 ctx = pwqp->dim->ctx;
1285 hash = isl_dim_get_hash(pwqp->dim);
1286 entry = isl_hash_table_find(ctx, &(*upwf)->table,
1287 hash, &has_dim, pwqp->dim, 1);
1288 if (!entry)
1289 goto error;
1291 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1292 if (!entry->data)
1293 entry->data = pwf;
1294 else {
1295 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1296 if (!entry->data)
1297 return -1;
1298 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) {
1299 isl_pw_qpolynomial_fold_free(entry->data);
1300 isl_hash_table_remove(ctx, &(*upwf)->table, entry);
1304 return 0;
1305 error:
1306 isl_pw_qpolynomial_free(pwqp);
1307 return -1;
1310 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1311 __isl_take isl_union_pw_qpolynomial_fold *upwf,
1312 __isl_take isl_union_pw_qpolynomial *upwqp)
1314 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1315 isl_union_pw_qpolynomial_get_dim(upwqp));
1316 upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1317 isl_union_pw_qpolynomial_fold_get_dim(upwf));
1319 upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1320 if (!upwf || !upwqp)
1321 goto error;
1323 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1324 &upwf) < 0)
1325 goto error;
1327 isl_union_pw_qpolynomial_free(upwqp);
1329 return upwf;
1330 error:
1331 isl_union_pw_qpolynomial_fold_free(upwf);
1332 isl_union_pw_qpolynomial_free(upwqp);
1333 return NULL;
1336 static int compatible_range(__isl_keep isl_dim *dim1, __isl_keep isl_dim *dim2)
1338 int m;
1339 m = isl_dim_match(dim1, isl_dim_param, dim2, isl_dim_param);
1340 if (m < 0 || !m)
1341 return m;
1342 return isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_set);
1345 /* Compute the intersection of the range of the map and the domain
1346 * of the piecewise quasipolynomial reduction and then compute a bound
1347 * on the associated quasipolynomial reduction over all elements
1348 * in this intersection.
1350 * We first introduce some unconstrained dimensions in the
1351 * piecewise quasipolynomial, intersect the resulting domain
1352 * with the wrapped map and the compute the sum.
1354 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1355 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1356 int *tight)
1358 isl_ctx *ctx;
1359 isl_set *dom;
1360 isl_dim *map_dim;
1361 isl_dim *pwf_dim;
1362 unsigned n_in;
1363 int ok;
1365 ctx = isl_map_get_ctx(map);
1366 if (!ctx)
1367 goto error;
1369 map_dim = isl_map_get_dim(map);
1370 pwf_dim = isl_pw_qpolynomial_fold_get_dim(pwf);
1371 ok = compatible_range(map_dim, pwf_dim);
1372 isl_dim_free(map_dim);
1373 isl_dim_free(pwf_dim);
1374 if (!ok)
1375 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1376 goto error);
1378 n_in = isl_map_dim(map, isl_dim_in);
1379 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_set, 0, n_in);
1381 dom = isl_map_wrap(map);
1382 pwf = isl_pw_qpolynomial_fold_reset_dim(pwf, isl_set_get_dim(dom));
1384 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1385 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1387 return pwf;
1388 error:
1389 isl_map_free(map);
1390 isl_pw_qpolynomial_fold_free(pwf);
1391 return NULL;
1394 struct isl_apply_fold_data {
1395 isl_union_pw_qpolynomial_fold *upwf;
1396 isl_union_pw_qpolynomial_fold *res;
1397 isl_map *map;
1398 int tight;
1401 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf,
1402 void *user)
1404 isl_dim *map_dim;
1405 isl_dim *pwf_dim;
1406 struct isl_apply_fold_data *data = user;
1407 int ok;
1409 map_dim = isl_map_get_dim(data->map);
1410 pwf_dim = isl_pw_qpolynomial_fold_get_dim(pwf);
1411 ok = compatible_range(map_dim, pwf_dim);
1412 isl_dim_free(map_dim);
1413 isl_dim_free(pwf_dim);
1415 if (ok) {
1416 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1417 pwf, data->tight ? &data->tight : NULL);
1418 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1419 data->res, pwf);
1420 } else
1421 isl_pw_qpolynomial_fold_free(pwf);
1423 return 0;
1426 static int map_apply(__isl_take isl_map *map, void *user)
1428 struct isl_apply_fold_data *data = user;
1429 int r;
1431 data->map = map;
1432 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1433 data->upwf, &pw_qpolynomial_fold_apply, data);
1435 isl_map_free(map);
1436 return r;
1439 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1440 __isl_take isl_union_map *umap,
1441 __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1443 isl_dim *dim;
1444 enum isl_fold type;
1445 struct isl_apply_fold_data data;
1447 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1448 isl_union_map_get_dim(umap));
1449 umap = isl_union_map_align_params(umap,
1450 isl_union_pw_qpolynomial_fold_get_dim(upwf));
1452 data.upwf = upwf;
1453 data.tight = tight ? 1 : 0;
1454 dim = isl_union_pw_qpolynomial_fold_get_dim(upwf);
1455 type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1456 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1457 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1458 goto error;
1460 isl_union_map_free(umap);
1461 isl_union_pw_qpolynomial_fold_free(upwf);
1463 if (tight)
1464 *tight = data.tight;
1466 return data.res;
1467 error:
1468 isl_union_map_free(umap);
1469 isl_union_pw_qpolynomial_fold_free(upwf);
1470 isl_union_pw_qpolynomial_fold_free(data.res);
1471 return NULL;
1474 /* Reorder the dimension of "fold" according to the given reordering.
1476 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign(
1477 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1479 int i;
1481 fold = isl_qpolynomial_fold_cow(fold);
1482 if (!fold || !r)
1483 goto error;
1485 for (i = 0; i < fold->n; ++i) {
1486 fold->qp[i] = isl_qpolynomial_realign(fold->qp[i],
1487 isl_reordering_copy(r));
1488 if (!fold->qp[i])
1489 goto error;
1492 fold = isl_qpolynomial_fold_reset_dim(fold, isl_dim_copy(r->dim));
1494 isl_reordering_free(r);
1496 return fold;
1497 error:
1498 isl_qpolynomial_fold_free(fold);
1499 isl_reordering_free(r);
1500 return NULL;