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,
12 #include <isl_map_private.h>
13 #include <isl_union_map_private.h>
14 #include <isl_polynomial_private.h>
15 #include <isl_point_private.h>
16 #include <isl_space_private.h>
19 #include <isl_mat_private.h>
20 #include <isl_config.h>
22 enum isl_fold isl_fold_type_negate(enum isl_fold type)
33 isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort());
36 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
37 enum isl_fold type, __isl_take isl_space *dim, int n)
39 isl_qpolynomial_fold *fold;
44 isl_assert(dim->ctx, n >= 0, goto error);
45 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
46 sizeof(struct isl_qpolynomial_fold) +
47 (n - 1) * sizeof(struct isl_qpolynomial *));
63 isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold)
65 return fold ? fold->dim->ctx : NULL;
68 __isl_give isl_space *isl_qpolynomial_fold_get_space(
69 __isl_keep isl_qpolynomial_fold *fold)
71 return fold ? isl_space_copy(fold->dim) : NULL;
74 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space(
75 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim)
79 fold = isl_qpolynomial_fold_cow(fold);
83 for (i = 0; i < fold->n; ++i) {
84 fold->qp[i] = isl_qpolynomial_reset_space(fold->qp[i],
90 isl_space_free(fold->dim);
95 isl_qpolynomial_fold_free(fold);
100 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
101 enum isl_dim_type type, unsigned first, unsigned n)
107 if (fold->n == 0 || n == 0)
110 for (i = 0; i < fold->n; ++i) {
111 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
113 if (involves < 0 || involves)
119 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name(
120 __isl_take isl_qpolynomial_fold *fold,
121 enum isl_dim_type type, unsigned pos, const char *s)
125 fold = isl_qpolynomial_fold_cow(fold);
128 fold->dim = isl_space_set_dim_name(fold->dim, type, pos, s);
132 for (i = 0; i < fold->n; ++i) {
133 fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i],
141 isl_qpolynomial_fold_free(fold);
145 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
146 __isl_take isl_qpolynomial_fold *fold,
147 enum isl_dim_type type, unsigned first, unsigned n)
156 fold = isl_qpolynomial_fold_cow(fold);
159 fold->dim = isl_space_drop_dims(fold->dim, type, first, n);
163 for (i = 0; i < fold->n; ++i) {
164 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
172 isl_qpolynomial_fold_free(fold);
176 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims(
177 __isl_take isl_qpolynomial_fold *fold,
178 enum isl_dim_type type, unsigned first, unsigned n)
184 if (n == 0 && !isl_space_is_named_or_nested(fold->dim, type))
187 fold = isl_qpolynomial_fold_cow(fold);
190 fold->dim = isl_space_insert_dims(fold->dim, type, first, n);
194 for (i = 0; i < fold->n; ++i) {
195 fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i],
203 isl_qpolynomial_fold_free(fold);
207 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
209 struct isl_upoly_cst *cst;
211 cst = isl_upoly_as_cst(qp->upoly);
215 return isl_int_sgn(cst->n) < 0 ? -1 : 1;
218 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
219 __isl_keep isl_qpolynomial *qp)
221 enum isl_lp_result res;
226 aff = isl_qpolynomial_extract_affine(qp);
232 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
234 if (res == isl_lp_error)
236 if (res == isl_lp_empty ||
237 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
242 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
244 if (res == isl_lp_ok && !isl_int_is_pos(opt))
253 /* Determine, if possible, the sign of the quasipolynomial "qp" on
256 * If qp is a constant, then the problem is trivial.
257 * If qp is linear, then we check if the minimum of the corresponding
258 * affine constraint is non-negative or if the maximum is non-positive.
260 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
261 * in "set". If so, we write qp(v,v') as
263 * q(v,v') * (v - l) + r(v')
265 * if q(v,v') and r(v') have the same known sign, then the original
266 * quasipolynomial has the same sign as well.
273 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
274 __isl_keep isl_qpolynomial *qp)
279 struct isl_upoly_rec *rec;
282 enum isl_lp_result res;
285 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
289 return isl_qpolynomial_cst_sign(qp);
291 is = isl_qpolynomial_is_affine(qp);
295 return isl_qpolynomial_aff_sign(set, qp);
297 if (qp->div->n_row > 0)
300 rec = isl_upoly_as_rec(qp->upoly);
304 d = isl_space_dim(qp->dim, isl_dim_all);
305 v = isl_vec_alloc(set->ctx, 2 + d);
309 isl_seq_clr(v->el + 1, 1 + d);
310 isl_int_set_si(v->el[0], 1);
311 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
315 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
316 if (res == isl_lp_ok) {
317 isl_qpolynomial *min;
318 isl_qpolynomial *base;
319 isl_qpolynomial *r, *q;
322 min = isl_qpolynomial_cst(isl_space_copy(qp->dim), l);
323 base = isl_qpolynomial_var_pow(isl_space_copy(qp->dim),
326 r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
327 isl_upoly_copy(rec->p[rec->n - 1]));
328 q = isl_qpolynomial_copy(r);
330 for (i = rec->n - 2; i >= 0; --i) {
331 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
332 t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0,
333 isl_upoly_copy(rec->p[i]));
334 r = isl_qpolynomial_add(r, t);
337 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
338 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
341 if (isl_qpolynomial_is_zero(q))
342 sgn = isl_qpolynomial_sign(set, r);
343 else if (isl_qpolynomial_is_zero(r))
344 sgn = isl_qpolynomial_sign(set, q);
347 sgn_r = isl_qpolynomial_sign(set, r);
348 sgn_q = isl_qpolynomial_sign(set, q);
353 isl_qpolynomial_free(min);
354 isl_qpolynomial_free(base);
355 isl_qpolynomial_free(q);
356 isl_qpolynomial_free(r);
366 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
367 __isl_keep isl_set *set,
368 __isl_take isl_qpolynomial_fold *fold1,
369 __isl_take isl_qpolynomial_fold *fold2)
373 struct isl_qpolynomial_fold *res = NULL;
376 if (!fold1 || !fold2)
379 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
380 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
383 better = fold1->type == isl_fold_max ? -1 : 1;
385 if (isl_qpolynomial_fold_is_empty(fold1)) {
386 isl_qpolynomial_fold_free(fold1);
390 if (isl_qpolynomial_fold_is_empty(fold2)) {
391 isl_qpolynomial_fold_free(fold2);
395 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
396 fold1->n + fold2->n);
400 for (i = 0; i < fold1->n; ++i) {
401 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
402 if (!res->qp[res->n])
408 for (i = 0; i < fold2->n; ++i) {
409 for (j = n1 - 1; j >= 0; --j) {
412 d = isl_qpolynomial_sub(
413 isl_qpolynomial_copy(res->qp[j]),
414 isl_qpolynomial_copy(fold2->qp[i]));
415 sgn = isl_qpolynomial_sign(set, d);
416 isl_qpolynomial_free(d);
421 isl_qpolynomial_free(res->qp[j]);
423 res->qp[j] = res->qp[n1 - 1];
425 if (n1 != res->n - 1)
426 res->qp[n1] = res->qp[res->n - 1];
431 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
432 if (!res->qp[res->n])
437 isl_qpolynomial_fold_free(fold1);
438 isl_qpolynomial_fold_free(fold2);
442 isl_qpolynomial_fold_free(res);
443 isl_qpolynomial_fold_free(fold1);
444 isl_qpolynomial_fold_free(fold2);
448 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial(
449 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp)
456 if (isl_qpolynomial_is_zero(qp)) {
457 isl_qpolynomial_free(qp);
461 fold = isl_qpolynomial_fold_cow(fold);
465 for (i = 0; i < fold->n; ++i) {
466 fold->qp[i] = isl_qpolynomial_add(fold->qp[i],
467 isl_qpolynomial_copy(qp));
472 isl_qpolynomial_free(qp);
475 isl_qpolynomial_fold_free(fold);
476 isl_qpolynomial_free(qp);
480 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain(
481 __isl_keep isl_set *dom,
482 __isl_take isl_qpolynomial_fold *fold1,
483 __isl_take isl_qpolynomial_fold *fold2)
486 isl_qpolynomial_fold *res = NULL;
488 if (!fold1 || !fold2)
491 if (isl_qpolynomial_fold_is_empty(fold1)) {
492 isl_qpolynomial_fold_free(fold1);
496 if (isl_qpolynomial_fold_is_empty(fold2)) {
497 isl_qpolynomial_fold_free(fold2);
501 if (fold1->n == 1 && fold2->n != 1)
502 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1);
505 res = isl_qpolynomial_fold_add_qpolynomial(fold1,
506 isl_qpolynomial_copy(fold2->qp[0]));
507 isl_qpolynomial_fold_free(fold2);
511 res = isl_qpolynomial_fold_add_qpolynomial(
512 isl_qpolynomial_fold_copy(fold1),
513 isl_qpolynomial_copy(fold2->qp[0]));
515 for (i = 1; i < fold2->n; ++i) {
516 isl_qpolynomial_fold *res_i;
517 res_i = isl_qpolynomial_fold_add_qpolynomial(
518 isl_qpolynomial_fold_copy(fold1),
519 isl_qpolynomial_copy(fold2->qp[i]));
520 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i);
523 isl_qpolynomial_fold_free(fold1);
524 isl_qpolynomial_fold_free(fold2);
527 isl_qpolynomial_fold_free(res);
528 isl_qpolynomial_fold_free(fold1);
529 isl_qpolynomial_fold_free(fold2);
533 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
534 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
541 fold = isl_qpolynomial_fold_cow(fold);
545 for (i = 0; i < fold->n; ++i) {
546 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
547 isl_basic_set_copy(eq));
552 isl_basic_set_free(eq);
555 isl_basic_set_free(eq);
556 isl_qpolynomial_fold_free(fold);
560 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist(
561 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context)
565 if (!fold || !context)
568 fold = isl_qpolynomial_fold_cow(fold);
572 for (i = 0; i < fold->n; ++i) {
573 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i],
574 isl_set_copy(context));
579 isl_set_free(context);
582 isl_set_free(context);
583 isl_qpolynomial_fold_free(fold);
590 #define PW isl_pw_qpolynomial_fold
592 #define EL isl_qpolynomial_fold
594 #define EL_IS_ZERO is_empty
598 #define IS_ZERO is_zero
604 #include <isl_pw_templ.c>
607 #define UNION isl_union_pw_qpolynomial_fold
609 #define PART isl_pw_qpolynomial_fold
611 #define PARTS pw_qpolynomial_fold
613 #include <isl_union_templ.c>
615 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
616 __isl_take isl_space *dim)
618 return qpolynomial_fold_alloc(type, dim, 0);
621 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
622 enum isl_fold type, __isl_take isl_qpolynomial *qp)
624 isl_qpolynomial_fold *fold;
629 fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1);
638 isl_qpolynomial_fold_free(fold);
639 isl_qpolynomial_free(qp);
643 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
644 __isl_keep isl_qpolynomial_fold *fold)
653 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
654 __isl_keep isl_qpolynomial_fold *fold)
657 isl_qpolynomial_fold *dup;
661 dup = qpolynomial_fold_alloc(fold->type,
662 isl_space_copy(fold->dim), fold->n);
667 for (i = 0; i < fold->n; ++i) {
668 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
675 isl_qpolynomial_fold_free(dup);
679 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
680 __isl_take isl_qpolynomial_fold *fold)
688 return isl_qpolynomial_fold_dup(fold);
691 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
700 for (i = 0; i < fold->n; ++i)
701 isl_qpolynomial_free(fold->qp[i]);
702 isl_space_free(fold->dim);
706 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
714 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
715 __isl_take isl_qpolynomial_fold *fold1,
716 __isl_take isl_qpolynomial_fold *fold2)
719 struct isl_qpolynomial_fold *res = NULL;
721 if (!fold1 || !fold2)
724 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
725 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim),
728 if (isl_qpolynomial_fold_is_empty(fold1)) {
729 isl_qpolynomial_fold_free(fold1);
733 if (isl_qpolynomial_fold_is_empty(fold2)) {
734 isl_qpolynomial_fold_free(fold2);
738 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim),
739 fold1->n + fold2->n);
743 for (i = 0; i < fold1->n; ++i) {
744 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
745 if (!res->qp[res->n])
750 for (i = 0; i < fold2->n; ++i) {
751 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
752 if (!res->qp[res->n])
757 isl_qpolynomial_fold_free(fold1);
758 isl_qpolynomial_fold_free(fold2);
762 isl_qpolynomial_fold_free(res);
763 isl_qpolynomial_fold_free(fold1);
764 isl_qpolynomial_fold_free(fold2);
768 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
769 __isl_take isl_pw_qpolynomial_fold *pw1,
770 __isl_take isl_pw_qpolynomial_fold *pw2)
773 struct isl_pw_qpolynomial_fold *res;
779 isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
781 if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
782 isl_pw_qpolynomial_fold_free(pw1);
786 if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
787 isl_pw_qpolynomial_fold_free(pw2);
791 if (pw1->type != pw2->type)
792 isl_die(pw1->dim->ctx, isl_error_invalid,
793 "fold types don't match", goto error);
795 n = (pw1->n + 1) * (pw2->n + 1);
796 res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim),
799 for (i = 0; i < pw1->n; ++i) {
800 set = isl_set_copy(pw1->p[i].set);
801 for (j = 0; j < pw2->n; ++j) {
802 struct isl_set *common;
803 isl_qpolynomial_fold *sum;
804 set = isl_set_subtract(set,
805 isl_set_copy(pw2->p[j].set));
806 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
807 isl_set_copy(pw2->p[j].set));
808 if (isl_set_plain_is_empty(common)) {
809 isl_set_free(common);
813 sum = isl_qpolynomial_fold_fold_on_domain(common,
814 isl_qpolynomial_fold_copy(pw1->p[i].fold),
815 isl_qpolynomial_fold_copy(pw2->p[j].fold));
817 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
819 res = isl_pw_qpolynomial_fold_add_piece(res, set,
820 isl_qpolynomial_fold_copy(pw1->p[i].fold));
823 for (j = 0; j < pw2->n; ++j) {
824 set = isl_set_copy(pw2->p[j].set);
825 for (i = 0; i < pw1->n; ++i)
826 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
827 res = isl_pw_qpolynomial_fold_add_piece(res, set,
828 isl_qpolynomial_fold_copy(pw2->p[j].fold));
831 isl_pw_qpolynomial_fold_free(pw1);
832 isl_pw_qpolynomial_fold_free(pw2);
836 isl_pw_qpolynomial_fold_free(pw1);
837 isl_pw_qpolynomial_fold_free(pw2);
841 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
842 __isl_take isl_union_pw_qpolynomial_fold *u,
843 __isl_take isl_pw_qpolynomial_fold *part)
846 struct isl_hash_table_entry *entry;
848 u = isl_union_pw_qpolynomial_fold_cow(u);
853 isl_assert(u->dim->ctx, isl_space_match(part->dim, isl_dim_param, u->dim,
854 isl_dim_param), goto error);
856 hash = isl_space_get_hash(part->dim);
857 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
858 &has_dim, part->dim, 1);
865 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
866 isl_pw_qpolynomial_fold_copy(part));
869 isl_pw_qpolynomial_fold_free(part);
874 isl_pw_qpolynomial_fold_free(part);
875 isl_union_pw_qpolynomial_fold_free(u);
879 static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
881 isl_union_pw_qpolynomial_fold **u;
882 u = (isl_union_pw_qpolynomial_fold **)user;
884 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
889 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
890 __isl_take isl_union_pw_qpolynomial_fold *u1,
891 __isl_take isl_union_pw_qpolynomial_fold *u2)
893 u1 = isl_union_pw_qpolynomial_fold_cow(u1);
898 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
899 &fold_part, &u1) < 0)
902 isl_union_pw_qpolynomial_fold_free(u2);
906 isl_union_pw_qpolynomial_fold_free(u1);
907 isl_union_pw_qpolynomial_fold_free(u2);
911 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
912 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
915 isl_pw_qpolynomial_fold *pwf;
920 pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim),
923 for (i = 0; i < pwqp->n; ++i)
924 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
925 isl_set_copy(pwqp->p[i].set),
926 isl_qpolynomial_fold_alloc(type,
927 isl_qpolynomial_copy(pwqp->p[i].qp)));
929 isl_pw_qpolynomial_free(pwqp);
934 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
935 __isl_keep isl_qpolynomial_fold *fold2)
939 if (!fold1 || !fold2)
942 if (fold1->n != fold2->n)
945 /* We probably want to sort the qps first... */
946 for (i = 0; i < fold1->n; ++i) {
947 int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]);
955 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
956 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
962 isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error);
963 isl_assert(pnt->dim->ctx,
964 fold->type == isl_fold_max || fold->type == isl_fold_min,
968 qp = isl_qpolynomial_zero(isl_space_copy(fold->dim));
971 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
972 isl_point_copy(pnt));
973 for (i = 1; i < fold->n; ++i) {
974 isl_qpolynomial *qp_i;
975 qp_i = isl_qpolynomial_eval(
976 isl_qpolynomial_copy(fold->qp[i]),
977 isl_point_copy(pnt));
978 if (fold->type == isl_fold_max)
979 qp = isl_qpolynomial_max_cst(qp, qp_i);
981 qp = isl_qpolynomial_min_cst(qp, qp_i);
984 isl_qpolynomial_fold_free(fold);
989 isl_qpolynomial_fold_free(fold);
994 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
999 for (i = 0; i < pwf->n; ++i)
1000 n += pwf->p[i].fold->n;
1005 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
1006 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
1009 isl_qpolynomial *opt;
1015 isl_space *dim = isl_space_copy(fold->dim);
1017 isl_qpolynomial_fold_free(fold);
1018 return isl_qpolynomial_zero(dim);
1021 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
1022 isl_set_copy(set), max);
1023 for (i = 1; i < fold->n; ++i) {
1024 isl_qpolynomial *opt_i;
1025 opt_i = isl_qpolynomial_opt_on_domain(
1026 isl_qpolynomial_copy(fold->qp[i]),
1027 isl_set_copy(set), max);
1029 opt = isl_qpolynomial_max_cst(opt, opt_i);
1031 opt = isl_qpolynomial_min_cst(opt, opt_i);
1035 isl_qpolynomial_fold_free(fold);
1040 isl_qpolynomial_fold_free(fold);
1044 /* Check whether for each quasi-polynomial in "fold2" there is
1045 * a quasi-polynomial in "fold1" that dominates it on "set".
1047 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1048 __isl_keep isl_qpolynomial_fold *fold1,
1049 __isl_keep isl_qpolynomial_fold *fold2)
1054 if (!set || !fold1 || !fold2)
1057 covers = fold1->type == isl_fold_max ? 1 : -1;
1059 for (i = 0; i < fold2->n; ++i) {
1060 for (j = 0; j < fold1->n; ++j) {
1064 d = isl_qpolynomial_sub(
1065 isl_qpolynomial_copy(fold1->qp[j]),
1066 isl_qpolynomial_copy(fold2->qp[i]));
1067 sgn = isl_qpolynomial_sign(set, d);
1068 isl_qpolynomial_free(d);
1079 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1080 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1083 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1084 __isl_keep isl_pw_qpolynomial_fold *pwf2)
1087 isl_set *dom1, *dom2;
1098 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1099 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1100 is_subset = isl_set_is_subset(dom2, dom1);
1104 if (is_subset < 0 || !is_subset)
1107 for (i = 0; i < pwf2->n; ++i) {
1108 for (j = 0; j < pwf1->n; ++j) {
1113 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1114 isl_set_copy(pwf2->p[i].set));
1115 is_empty = isl_set_is_empty(common);
1116 if (is_empty < 0 || is_empty) {
1117 isl_set_free(common);
1122 covers = qpolynomial_fold_covers_on_domain(common,
1123 pwf1->p[j].fold, pwf2->p[i].fold);
1124 isl_set_free(common);
1125 if (covers < 0 || !covers)
1133 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
1134 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1139 if (!fold || !morph)
1142 ctx = fold->dim->ctx;
1143 isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error);
1145 fold = isl_qpolynomial_fold_cow(fold);
1149 isl_space_free(fold->dim);
1150 fold->dim = isl_space_copy(morph->ran->dim);
1154 for (i = 0; i < fold->n; ++i) {
1155 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
1156 isl_morph_copy(morph));
1161 isl_morph_free(morph);
1165 isl_qpolynomial_fold_free(fold);
1166 isl_morph_free(morph);
1170 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1173 return isl_fold_list;
1177 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1178 __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1181 return isl_fold_list;
1185 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1186 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim)
1193 if (isl_space_is_equal(fold->dim, dim)) {
1194 isl_space_free(dim);
1198 fold = isl_qpolynomial_fold_cow(fold);
1202 isl_space_free(fold->dim);
1203 fold->dim = isl_space_copy(dim);
1207 for (i = 0; i < fold->n; ++i) {
1208 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1209 isl_space_copy(dim));
1214 isl_space_free(dim);
1218 isl_qpolynomial_fold_free(fold);
1219 isl_space_free(dim);
1223 int isl_qpolynomial_fold_foreach_qpolynomial(
1224 __isl_keep isl_qpolynomial_fold *fold,
1225 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1232 for (i = 0; i < fold->n; ++i)
1233 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1239 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1240 __isl_take isl_qpolynomial_fold *fold,
1241 enum isl_dim_type dst_type, unsigned dst_pos,
1242 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1249 fold = isl_qpolynomial_fold_cow(fold);
1253 fold->dim = isl_space_move_dims(fold->dim, dst_type, dst_pos,
1254 src_type, src_pos, n);
1258 for (i = 0; i < fold->n; ++i) {
1259 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1260 dst_type, dst_pos, src_type, src_pos, n);
1267 isl_qpolynomial_fold_free(fold);
1271 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1272 * in fold->qp[k] by subs[i].
1274 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1275 __isl_take isl_qpolynomial_fold *fold,
1276 enum isl_dim_type type, unsigned first, unsigned n,
1277 __isl_keep isl_qpolynomial **subs)
1284 fold = isl_qpolynomial_fold_cow(fold);
1288 for (i = 0; i < fold->n; ++i) {
1289 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1290 type, first, n, subs);
1297 isl_qpolynomial_fold_free(fold);
1301 static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1304 isl_pw_qpolynomial_fold *pwf;
1305 isl_union_pw_qpolynomial_fold **upwf;
1307 struct isl_hash_table_entry *entry;
1309 upwf = (isl_union_pw_qpolynomial_fold **)user;
1311 ctx = pwqp->dim->ctx;
1312 hash = isl_space_get_hash(pwqp->dim);
1313 entry = isl_hash_table_find(ctx, &(*upwf)->table,
1314 hash, &has_dim, pwqp->dim, 1);
1318 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1322 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1325 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) {
1326 isl_pw_qpolynomial_fold_free(entry->data);
1327 isl_hash_table_remove(ctx, &(*upwf)->table, entry);
1333 isl_pw_qpolynomial_free(pwqp);
1337 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1338 __isl_take isl_union_pw_qpolynomial_fold *upwf,
1339 __isl_take isl_union_pw_qpolynomial *upwqp)
1341 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1342 isl_union_pw_qpolynomial_get_space(upwqp));
1343 upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1344 isl_union_pw_qpolynomial_fold_get_space(upwf));
1346 upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1347 if (!upwf || !upwqp)
1350 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1354 isl_union_pw_qpolynomial_free(upwqp);
1358 isl_union_pw_qpolynomial_fold_free(upwf);
1359 isl_union_pw_qpolynomial_free(upwqp);
1363 static int compatible_range(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2)
1366 m = isl_space_match(dim1, isl_dim_param, dim2, isl_dim_param);
1369 return isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_set);
1372 /* Compute the intersection of the range of the map and the domain
1373 * of the piecewise quasipolynomial reduction and then compute a bound
1374 * on the associated quasipolynomial reduction over all elements
1375 * in this intersection.
1377 * We first introduce some unconstrained dimensions in the
1378 * piecewise quasipolynomial, intersect the resulting domain
1379 * with the wrapped map and the compute the sum.
1381 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1382 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1392 ctx = isl_map_get_ctx(map);
1396 map_dim = isl_map_get_space(map);
1397 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1398 ok = compatible_range(map_dim, pwf_dim);
1399 isl_space_free(map_dim);
1400 isl_space_free(pwf_dim);
1402 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1405 n_in = isl_map_dim(map, isl_dim_in);
1406 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_set, 0, n_in);
1408 dom = isl_map_wrap(map);
1409 pwf = isl_pw_qpolynomial_fold_reset_space(pwf, isl_set_get_space(dom));
1411 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1412 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1417 isl_pw_qpolynomial_fold_free(pwf);
1421 __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold(
1422 __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf,
1425 return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight);
1428 struct isl_apply_fold_data {
1429 isl_union_pw_qpolynomial_fold *upwf;
1430 isl_union_pw_qpolynomial_fold *res;
1435 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf,
1440 struct isl_apply_fold_data *data = user;
1443 map_dim = isl_map_get_space(data->map);
1444 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf);
1445 ok = compatible_range(map_dim, pwf_dim);
1446 isl_space_free(map_dim);
1447 isl_space_free(pwf_dim);
1450 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1451 pwf, data->tight ? &data->tight : NULL);
1452 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1455 isl_pw_qpolynomial_fold_free(pwf);
1460 static int map_apply(__isl_take isl_map *map, void *user)
1462 struct isl_apply_fold_data *data = user;
1466 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1467 data->upwf, &pw_qpolynomial_fold_apply, data);
1473 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1474 __isl_take isl_union_map *umap,
1475 __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1479 struct isl_apply_fold_data data;
1481 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1482 isl_union_map_get_space(umap));
1483 umap = isl_union_map_align_params(umap,
1484 isl_union_pw_qpolynomial_fold_get_space(upwf));
1487 data.tight = tight ? 1 : 0;
1488 dim = isl_union_pw_qpolynomial_fold_get_space(upwf);
1489 type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1490 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1491 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1494 isl_union_map_free(umap);
1495 isl_union_pw_qpolynomial_fold_free(upwf);
1498 *tight = data.tight;
1502 isl_union_map_free(umap);
1503 isl_union_pw_qpolynomial_fold_free(upwf);
1504 isl_union_pw_qpolynomial_fold_free(data.res);
1508 __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold(
1509 __isl_take isl_union_set *uset,
1510 __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1512 return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight);
1515 /* Reorder the dimension of "fold" according to the given reordering.
1517 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign(
1518 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1522 fold = isl_qpolynomial_fold_cow(fold);
1526 for (i = 0; i < fold->n; ++i) {
1527 fold->qp[i] = isl_qpolynomial_realign(fold->qp[i],
1528 isl_reordering_copy(r));
1533 fold = isl_qpolynomial_fold_reset_space(fold, isl_space_copy(r->dim));
1535 isl_reordering_free(r);
1539 isl_qpolynomial_fold_free(fold);
1540 isl_reordering_free(r);
1544 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int(
1545 __isl_take isl_qpolynomial_fold *fold, isl_int v)
1549 if (isl_int_is_one(v))
1551 if (fold && isl_int_is_zero(v)) {
1552 isl_qpolynomial_fold *zero;
1553 isl_space *dim = isl_space_copy(fold->dim);
1554 zero = isl_qpolynomial_fold_empty(fold->type, dim);
1555 isl_qpolynomial_fold_free(fold);
1559 fold = isl_qpolynomial_fold_cow(fold);
1563 if (isl_int_is_neg(v))
1564 fold->type = isl_fold_type_negate(fold->type);
1565 for (i = 0; i < fold->n; ++i) {
1566 fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v);
1573 isl_qpolynomial_fold_free(fold);
1577 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
1578 __isl_take isl_qpolynomial_fold *fold, isl_int v)
1580 return isl_qpolynomial_fold_mul_isl_int(fold, v);