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,
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>
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;
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 *));
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)
57 fold = isl_qpolynomial_fold_cow(fold);
61 for (i = 0; i < fold->n; ++i) {
62 fold->qp[i] = isl_qpolynomial_reset_dim(fold->qp[i],
68 isl_dim_free(fold->dim);
73 isl_qpolynomial_fold_free(fold);
78 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
79 enum isl_dim_type type, unsigned first, unsigned n)
85 if (fold->n == 0 || n == 0)
88 for (i = 0; i < fold->n; ++i) {
89 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
91 if (involves < 0 || involves)
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)
103 fold = isl_qpolynomial_fold_cow(fold);
106 fold->dim = isl_dim_set_name(fold->dim, type, pos, s);
110 for (i = 0; i < fold->n; ++i) {
111 fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i],
119 isl_qpolynomial_fold_free(fold);
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)
134 fold = isl_qpolynomial_fold_cow(fold);
137 fold->dim = isl_dim_drop(fold->dim, type, first, n);
141 for (i = 0; i < fold->n; ++i) {
142 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
150 isl_qpolynomial_fold_free(fold);
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)
162 if (n == 0 && !isl_dim_is_named_or_nested(fold->dim, type))
165 fold = isl_qpolynomial_fold_cow(fold);
168 fold->dim = isl_dim_insert(fold->dim, type, first, n);
172 for (i = 0; i < fold->n; ++i) {
173 fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i],
181 isl_qpolynomial_fold_free(fold);
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);
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;
204 aff = isl_qpolynomial_extract_affine(qp);
210 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
212 if (res == isl_lp_error)
214 if (res == isl_lp_empty ||
215 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
220 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
222 if (res == isl_lp_ok && !isl_int_is_pos(opt))
231 /* Determine, if possible, the sign of the quasipolynomial "qp" on
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.
251 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
252 __isl_keep isl_qpolynomial *qp)
257 struct isl_upoly_rec *rec;
260 enum isl_lp_result res;
263 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
267 return isl_qpolynomial_cst_sign(qp);
269 is = isl_qpolynomial_is_affine(qp);
273 return isl_qpolynomial_aff_sign(set, qp);
275 if (qp->div->n_row > 0)
278 rec = isl_upoly_as_rec(qp->upoly);
282 d = isl_dim_total(qp->dim);
283 v = isl_vec_alloc(set->ctx, 2 + d);
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);
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;
300 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
301 base = isl_qpolynomial_var_pow(isl_dim_copy(qp->dim),
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);
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);
325 sgn_r = isl_qpolynomial_sign(set, r);
326 sgn_q = isl_qpolynomial_sign(set, q);
331 isl_qpolynomial_free(min);
332 isl_qpolynomial_free(base);
333 isl_qpolynomial_free(q);
334 isl_qpolynomial_free(r);
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)
351 struct isl_qpolynomial_fold *res = NULL;
354 if (!fold1 || !fold2)
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),
361 better = fold1->type == isl_fold_max ? -1 : 1;
363 if (isl_qpolynomial_fold_is_empty(fold1)) {
364 isl_qpolynomial_fold_free(fold1);
368 if (isl_qpolynomial_fold_is_empty(fold2)) {
369 isl_qpolynomial_fold_free(fold2);
373 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
374 fold1->n + fold2->n);
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])
386 for (i = 0; i < fold2->n; ++i) {
387 for (j = n1 - 1; j >= 0; --j) {
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);
399 isl_qpolynomial_free(res->qp[j]);
401 res->qp[j] = res->qp[n1 - 1];
403 if (n1 != res->n - 1)
404 res->qp[n1] = res->qp[res->n - 1];
409 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
410 if (!res->qp[res->n])
415 isl_qpolynomial_fold_free(fold1);
416 isl_qpolynomial_fold_free(fold2);
420 isl_qpolynomial_fold_free(res);
421 isl_qpolynomial_fold_free(fold1);
422 isl_qpolynomial_fold_free(fold2);
426 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
427 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
434 if (isl_qpolynomial_is_zero(qp)) {
435 isl_qpolynomial_free(qp);
439 fold = isl_qpolynomial_fold_cow(fold);
443 for (i = 0; i < fold->n; ++i) {
444 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
445 isl_qpolynomial_copy(qp));
450 isl_qpolynomial_free(qp);
453 isl_qpolynomial_fold_free(fold);
454 isl_qpolynomial_free(qp);
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)
464 isl_qpolynomial_fold *res = NULL;
466 if (!fold1 || !fold2)
469 if (isl_qpolynomial_fold_is_empty(fold1)) {
470 isl_qpolynomial_fold_free(fold1);
474 if (isl_qpolynomial_fold_is_empty(fold2)) {
475 isl_qpolynomial_fold_free(fold2);
479 if (fold1->n == 1 && fold2->n != 1)
480 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
483 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
484 isl_qpolynomial_copy(fold2->qp[0]));
485 isl_qpolynomial_fold_free(fold2);
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);
505 isl_qpolynomial_fold_free(res);
506 isl_qpolynomial_fold_free(fold1);
507 isl_qpolynomial_fold_free(fold2);
511 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
512 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
519 fold = isl_qpolynomial_fold_cow(fold);
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));
530 isl_basic_set_free(eq);
533 isl_basic_set_free(eq);
534 isl_qpolynomial_fold_free(fold);
538 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
539 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
543 if (!fold || !context)
546 fold = isl_qpolynomial_fold_cow(fold);
550 for (i = 0; i < fold->n; ++i) {
551 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
552 isl_set_copy(context));
557 isl_set_free(context);
560 isl_set_free(context);
561 isl_qpolynomial_fold_free(fold);
568 #define PW isl_pw_qpolynomial_fold
570 #define EL isl_qpolynomial_fold
572 #define IS_ZERO is_empty
576 #include <isl_pw_templ.c>
579 #define UNION isl_union_pw_qpolynomial_fold
581 #define PART isl_pw_qpolynomial_fold
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;
601 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
610 isl_qpolynomial_fold_free(fold);
611 isl_qpolynomial_free(qp);
615 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
616 __isl_keep isl_qpolynomial_fold *fold)
625 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
626 __isl_keep isl_qpolynomial_fold *fold)
629 isl_qpolynomial_fold *dup;
633 dup = qpolynomial_fold_alloc(fold->type,
634 isl_dim_copy(fold->dim), fold->n);
639 for (i = 0; i < fold->n; ++i) {
640 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
647 isl_qpolynomial_fold_free(dup);
651 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
652 __isl_take isl_qpolynomial_fold *fold)
660 return isl_qpolynomial_fold_dup(fold);
663 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
672 for (i = 0; i < fold->n; ++i)
673 isl_qpolynomial_free(fold->qp[i]);
674 isl_dim_free(fold->dim);
678 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
686 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
687 __isl_take isl_qpolynomial_fold *fold1,
688 __isl_take isl_qpolynomial_fold *fold2)
691 struct isl_qpolynomial_fold *res = NULL;
693 if (!fold1 || !fold2)
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),
700 if (isl_qpolynomial_fold_is_empty(fold1)) {
701 isl_qpolynomial_fold_free(fold1);
705 if (isl_qpolynomial_fold_is_empty(fold2)) {
706 isl_qpolynomial_fold_free(fold2);
710 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
711 fold1->n + fold2->n);
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])
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])
729 isl_qpolynomial_fold_free(fold1);
730 isl_qpolynomial_fold_free(fold2);
734 isl_qpolynomial_fold_free(res);
735 isl_qpolynomial_fold_free(fold1);
736 isl_qpolynomial_fold_free(fold2);
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)
745 struct isl_pw_qpolynomial_fold *res;
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);
758 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
759 isl_pw_qpolynomial_fold_free(pw2);
763 if (pw1->type != pw2->type)
764 isl_die(set->ctx, isl_error_invalid, "fold types don't match",
767 n = (pw1->n + 1) * (pw2->n + 1);
768 res = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1->dim),
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);
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);
808 isl_pw_qpolynomial_fold_free(pw1);
809 isl_pw_qpolynomial_fold_free(pw2);
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)
818 struct isl_hash_table_entry *entry;
820 u = isl_union_pw_qpolynomial_fold_cow(u);
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);
837 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
838 isl_pw_qpolynomial_fold_copy(part));
841 isl_pw_qpolynomial_fold_free(part);
846 isl_pw_qpolynomial_fold_free(part);
847 isl_union_pw_qpolynomial_fold_free(u);
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);
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);
870 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
871 &fold_part, &u1) < 0)
874 isl_union_pw_qpolynomial_fold_free(u2);
878 isl_union_pw_qpolynomial_fold_free(u1);
879 isl_union_pw_qpolynomial_fold_free(u2);
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)
887 isl_pw_qpolynomial_fold *pwf;
892 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), type,
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);
906 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
907 __isl_keep isl_qpolynomial_fold *fold2)
911 if (!fold1 || !fold2)
914 if (fold1->n != fold2->n)
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]);
927 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
928 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
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,
940 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
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);
953 qp = isl_qpolynomial_min_cst(qp, qp_i);
956 isl_qpolynomial_fold_free(fold);
961 isl_qpolynomial_fold_free(fold);
966 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
971 for (i = 0; i < pwf->n; ++i)
972 n += pwf->p[i].fold->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)
981 isl_qpolynomial *opt;
987 isl_dim *dim = isl_dim_copy(fold->dim);
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);
1001 opt = isl_qpolynomial_max_cst(opt, opt_i);
1003 opt = isl_qpolynomial_min_cst(opt, opt_i);
1007 isl_qpolynomial_fold_free(fold);
1012 isl_qpolynomial_fold_free(fold);
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)
1026 if (!set || !fold1 || !fold2)
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) {
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);
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
1055 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1056 __isl_keep isl_pw_qpolynomial_fold *pwf2)
1059 isl_set *dom1, *dom2;
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);
1076 if (is_subset < 0 || !is_subset)
1079 for (i = 0; i < pwf2->n; ++i) {
1080 for (j = 0; j < pwf1->n; ++j) {
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);
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)
1105 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
1106 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1111 if (!fold || !morph)
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);
1121 isl_dim_free(fold->dim);
1122 fold->dim = isl_dim_copy(morph->ran->dim);
1126 for (i = 0; i < fold->n; ++i) {
1127 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
1128 isl_morph_copy(morph));
1133 isl_morph_free(morph);
1137 isl_qpolynomial_fold_free(fold);
1138 isl_morph_free(morph);
1142 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1145 return isl_fold_list;
1149 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1150 __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1153 return isl_fold_list;
1157 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1158 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
1166 if (isl_dim_equal(fold->dim, dim)) {
1171 fold = isl_qpolynomial_fold_cow(fold);
1175 isl_dim_free(fold->dim);
1176 fold->dim = isl_dim_copy(dim);
1180 for (i = 0; i < fold->n; ++i) {
1181 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1191 isl_qpolynomial_fold_free(fold);
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)
1205 for (i = 0; i < fold->n; ++i)
1206 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 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)
1222 fold = isl_qpolynomial_fold_cow(fold);
1226 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
1227 src_type, src_pos, n);
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);
1240 isl_qpolynomial_fold_free(fold);
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)
1257 fold = isl_qpolynomial_fold_cow(fold);
1261 for (i = 0; i < fold->n; ++i) {
1262 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1263 type, first, n, subs);
1270 isl_qpolynomial_fold_free(fold);
1274 static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1277 isl_pw_qpolynomial_fold *pwf;
1278 isl_union_pw_qpolynomial_fold **upwf;
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);
1291 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1295 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
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);
1306 isl_pw_qpolynomial_free(pwqp);
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)
1323 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1327 isl_union_pw_qpolynomial_free(upwqp);
1331 isl_union_pw_qpolynomial_fold_free(upwf);
1332 isl_union_pw_qpolynomial_free(upwqp);
1336 static int compatible_range(__isl_keep isl_dim *dim1, __isl_keep isl_dim *dim2)
1339 m = isl_dim_match(dim1, isl_dim_param, dim2, isl_dim_param);
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,
1365 ctx = isl_map_get_ctx(map);
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);
1375 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
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);
1390 isl_pw_qpolynomial_fold_free(pwf);
1394 struct isl_apply_fold_data {
1395 isl_union_pw_qpolynomial_fold *upwf;
1396 isl_union_pw_qpolynomial_fold *res;
1401 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf,
1406 struct isl_apply_fold_data *data = user;
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);
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(
1421 isl_pw_qpolynomial_fold_free(pwf);
1426 static int map_apply(__isl_take isl_map *map, void *user)
1428 struct isl_apply_fold_data *data = user;
1432 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1433 data->upwf, &pw_qpolynomial_fold_apply, data);
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)
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));
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)
1460 isl_union_map_free(umap);
1461 isl_union_pw_qpolynomial_fold_free(upwf);
1464 *tight = data.tight;
1468 isl_union_map_free(umap);
1469 isl_union_pw_qpolynomial_fold_free(upwf);
1470 isl_union_pw_qpolynomial_fold_free(data.res);
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)
1481 fold = isl_qpolynomial_fold_cow(fold);
1485 for (i = 0; i < fold->n; ++i) {
1486 fold->qp[i] = isl_qpolynomial_realign(fold->qp[i],
1487 isl_reordering_copy(r));
1492 fold = isl_qpolynomial_fold_reset_dim(fold, isl_dim_copy(r->dim));
1494 isl_reordering_free(r);
1498 isl_qpolynomial_fold_free(fold);
1499 isl_reordering_free(r);