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>
19 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
20 enum isl_fold type, __isl_take isl_dim *dim, int n)
22 isl_qpolynomial_fold *fold;
27 isl_assert(dim->ctx, n >= 0, goto error);
28 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
29 sizeof(struct isl_qpolynomial_fold) +
30 (n - 1) * sizeof(struct isl_qpolynomial *));
46 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_dim(
47 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
52 isl_dim_free(fold->dim);
57 isl_qpolynomial_fold_free(fold);
62 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
63 enum isl_dim_type type, unsigned first, unsigned n)
69 if (fold->n == 0 || n == 0)
72 for (i = 0; i < fold->n; ++i) {
73 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
75 if (involves < 0 || involves)
81 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
82 __isl_take isl_qpolynomial_fold *fold,
83 enum isl_dim_type type, unsigned first, unsigned n)
92 fold = isl_qpolynomial_fold_cow(fold);
95 fold->dim = isl_dim_drop(fold->dim, type, first, n);
99 for (i = 0; i < fold->n; ++i) {
100 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
108 isl_qpolynomial_fold_free(fold);
112 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
114 struct isl_upoly_cst *cst;
116 cst = isl_upoly_as_cst(qp->upoly);
120 return isl_int_sgn(cst->n) < 0 ? -1 : 1;
123 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
124 __isl_keep isl_qpolynomial *qp)
126 enum isl_lp_result res;
131 aff = isl_qpolynomial_extract_affine(qp);
137 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
139 if (res == isl_lp_error)
141 if (res == isl_lp_empty ||
142 (res == isl_lp_ok && !isl_int_is_neg(opt))) {
147 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
149 if (res == isl_lp_ok && !isl_int_is_pos(opt))
158 /* Determine, if possible, the sign of the quasipolynomial "qp" on
161 * If qp is a constant, then the problem is trivial.
162 * If qp is linear, then we check if the minimum of the corresponding
163 * affine constraint is non-negative or if the maximum is non-positive.
165 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
166 * in "set". If so, we write qp(v,v') as
168 * q(v,v') * (v - l) + r(v')
170 * if q(v,v') and r(v') have the same known sign, then the original
171 * quasipolynomial has the same sign as well.
178 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
179 __isl_keep isl_qpolynomial *qp)
184 struct isl_upoly_rec *rec;
187 enum isl_lp_result res;
190 is = isl_qpolynomial_is_cst(qp, NULL, NULL);
194 return isl_qpolynomial_cst_sign(qp);
196 is = isl_qpolynomial_is_affine(qp);
200 return isl_qpolynomial_aff_sign(set, qp);
202 if (qp->div->n_row > 0)
205 rec = isl_upoly_as_rec(qp->upoly);
209 d = isl_dim_total(qp->dim);
210 v = isl_vec_alloc(set->ctx, 2 + d);
214 isl_seq_clr(v->el + 1, 1 + d);
215 isl_int_set_si(v->el[0], 1);
216 isl_int_set_si(v->el[2 + qp->upoly->var], 1);
220 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
221 if (res == isl_lp_ok) {
222 isl_qpolynomial *min;
223 isl_qpolynomial *base;
224 isl_qpolynomial *r, *q;
227 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
228 base = isl_qpolynomial_pow(isl_dim_copy(qp->dim),
231 r = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
232 isl_upoly_copy(rec->p[rec->n - 1]));
233 q = isl_qpolynomial_copy(r);
235 for (i = rec->n - 2; i >= 0; --i) {
236 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
237 t = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
238 isl_upoly_copy(rec->p[i]));
239 r = isl_qpolynomial_add(r, t);
242 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
243 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
246 if (isl_qpolynomial_is_zero(q))
247 sgn = isl_qpolynomial_sign(set, r);
248 else if (isl_qpolynomial_is_zero(r))
249 sgn = isl_qpolynomial_sign(set, q);
252 sgn_r = isl_qpolynomial_sign(set, r);
253 sgn_q = isl_qpolynomial_sign(set, q);
258 isl_qpolynomial_free(min);
259 isl_qpolynomial_free(base);
260 isl_qpolynomial_free(q);
261 isl_qpolynomial_free(r);
271 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
272 __isl_keep isl_set *set,
273 __isl_take isl_qpolynomial_fold *fold1,
274 __isl_take isl_qpolynomial_fold *fold2)
278 struct isl_qpolynomial_fold *res = NULL;
281 if (!fold1 || !fold2)
284 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
285 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
288 better = fold1->type == isl_fold_max ? -1 : 1;
290 if (isl_qpolynomial_fold_is_empty(fold1)) {
291 isl_qpolynomial_fold_free(fold1);
295 if (isl_qpolynomial_fold_is_empty(fold2)) {
296 isl_qpolynomial_fold_free(fold2);
300 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
301 fold1->n + fold2->n);
305 for (i = 0; i < fold1->n; ++i) {
306 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
307 if (!res->qp[res->n])
313 for (i = 0; i < fold2->n; ++i) {
314 for (j = n1 - 1; j >= 0; --j) {
317 d = isl_qpolynomial_sub(
318 isl_qpolynomial_copy(res->qp[j]),
319 isl_qpolynomial_copy(fold2->qp[i]));
320 sgn = isl_qpolynomial_sign(set, d);
321 isl_qpolynomial_free(d);
326 isl_qpolynomial_free(res->qp[j]);
328 res->qp[j] = res->qp[n1 - 1];
330 if (n1 != res->n - 1)
331 res->qp[n1] = res->qp[res->n - 1];
336 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
337 if (!res->qp[res->n])
342 isl_qpolynomial_fold_free(fold1);
343 isl_qpolynomial_fold_free(fold2);
347 isl_qpolynomial_fold_free(res);
348 isl_qpolynomial_fold_free(fold1);
349 isl_qpolynomial_fold_free(fold2);
353 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
354 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
361 fold = isl_qpolynomial_fold_cow(fold);
365 for (i = 0; i < fold->n; ++i) {
366 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
367 isl_basic_set_copy(eq));
372 isl_basic_set_free(eq);
375 isl_basic_set_free(eq);
376 isl_qpolynomial_fold_free(fold);
381 #define PW isl_pw_qpolynomial_fold
383 #define EL isl_qpolynomial_fold
385 #define IS_ZERO is_empty
389 #define ADD(d,e1,e2) isl_qpolynomial_fold_fold_on_domain(d,e1,e2)
391 #include <isl_pw_templ.c>
394 #define UNION isl_union_pw_qpolynomial_fold
396 #define PART isl_pw_qpolynomial_fold
398 #define PARTS pw_qpolynomial_fold
400 #include <isl_union_templ.c>
402 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
403 __isl_take isl_dim *dim)
405 return qpolynomial_fold_alloc(type, dim, 0);
408 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
409 enum isl_fold type, __isl_take isl_qpolynomial *qp)
411 isl_qpolynomial_fold *fold;
416 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
425 isl_qpolynomial_fold_free(fold);
426 isl_qpolynomial_free(qp);
430 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
431 __isl_keep isl_qpolynomial_fold *fold)
440 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
441 __isl_keep isl_qpolynomial_fold *fold)
444 isl_qpolynomial_fold *dup;
448 dup = qpolynomial_fold_alloc(fold->type,
449 isl_dim_copy(fold->dim), fold->n);
454 for (i = 0; i < fold->n; ++i) {
455 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
462 isl_qpolynomial_fold_free(dup);
466 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
467 __isl_take isl_qpolynomial_fold *fold)
475 return isl_qpolynomial_fold_dup(fold);
478 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
487 for (i = 0; i < fold->n; ++i)
488 isl_qpolynomial_free(fold->qp[i]);
489 isl_dim_free(fold->dim);
493 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
501 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
502 __isl_take isl_qpolynomial_fold *fold1,
503 __isl_take isl_qpolynomial_fold *fold2)
506 struct isl_qpolynomial_fold *res = NULL;
508 if (!fold1 || !fold2)
511 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
512 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
515 if (isl_qpolynomial_fold_is_empty(fold1)) {
516 isl_qpolynomial_fold_free(fold1);
520 if (isl_qpolynomial_fold_is_empty(fold2)) {
521 isl_qpolynomial_fold_free(fold2);
525 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
526 fold1->n + fold2->n);
530 for (i = 0; i < fold1->n; ++i) {
531 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
532 if (!res->qp[res->n])
537 for (i = 0; i < fold2->n; ++i) {
538 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
539 if (!res->qp[res->n])
544 isl_qpolynomial_fold_free(fold1);
545 isl_qpolynomial_fold_free(fold2);
549 isl_qpolynomial_fold_free(res);
550 isl_qpolynomial_fold_free(fold1);
551 isl_qpolynomial_fold_free(fold2);
555 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
556 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
559 isl_pw_qpolynomial_fold *pwf;
564 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
566 for (i = 0; i < pwqp->n; ++i)
567 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
568 isl_set_copy(pwqp->p[i].set),
569 isl_qpolynomial_fold_alloc(type,
570 isl_qpolynomial_copy(pwqp->p[i].qp)));
572 isl_pw_qpolynomial_free(pwqp);
577 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
578 __isl_keep isl_qpolynomial_fold *fold2)
582 if (!fold1 || !fold2)
585 if (fold1->n != fold2->n)
588 /* We probably want to sort the qps first... */
589 for (i = 0; i < fold1->n; ++i) {
590 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
598 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
599 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
605 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
606 isl_assert(pnt->dim->ctx,
607 fold->type == isl_fold_max || fold->type == isl_fold_min,
611 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
614 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
615 isl_point_copy(pnt));
616 for (i = 1; i < fold->n; ++i) {
617 isl_qpolynomial *qp_i;
618 qp_i = isl_qpolynomial_eval(
619 isl_qpolynomial_copy(fold->qp[i]),
620 isl_point_copy(pnt));
621 if (fold->type == isl_fold_max)
622 qp = isl_qpolynomial_max_cst(qp, qp_i);
624 qp = isl_qpolynomial_min_cst(qp, qp_i);
627 isl_qpolynomial_fold_free(fold);
632 isl_qpolynomial_fold_free(fold);
637 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
642 for (i = 0; i < pwf->n; ++i)
643 n += pwf->p[i].fold->n;
648 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
649 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
652 isl_qpolynomial *opt;
658 isl_dim *dim = isl_dim_copy(fold->dim);
660 isl_qpolynomial_fold_free(fold);
661 return isl_qpolynomial_zero(dim);
664 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
665 isl_set_copy(set), max);
666 for (i = 1; i < fold->n; ++i) {
667 isl_qpolynomial *opt_i;
668 opt_i = isl_qpolynomial_opt_on_domain(
669 isl_qpolynomial_copy(fold->qp[i]),
670 isl_set_copy(set), max);
672 opt = isl_qpolynomial_max_cst(opt, opt_i);
674 opt = isl_qpolynomial_min_cst(opt, opt_i);
678 isl_qpolynomial_fold_free(fold);
683 isl_qpolynomial_fold_free(fold);
687 /* Check whether for each quasi-polynomial in "fold2" there is
688 * a quasi-polynomial in "fold1" that dominates it on "set".
690 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
691 __isl_keep isl_qpolynomial_fold *fold1,
692 __isl_keep isl_qpolynomial_fold *fold2)
697 if (!set || !fold1 || !fold2)
700 covers = fold1->type == isl_fold_max ? 1 : -1;
702 for (i = 0; i < fold2->n; ++i) {
703 for (j = 0; j < fold1->n; ++j) {
707 d = isl_qpolynomial_sub(
708 isl_qpolynomial_copy(fold1->qp[j]),
709 isl_qpolynomial_copy(fold2->qp[i]));
710 sgn = isl_qpolynomial_sign(set, d);
711 isl_qpolynomial_free(d);
722 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
723 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
726 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
727 __isl_keep isl_pw_qpolynomial_fold *pwf2)
730 isl_set *dom1, *dom2;
741 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
742 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
743 is_subset = isl_set_is_subset(dom2, dom1);
747 if (is_subset < 0 || !is_subset)
750 for (i = 0; i < pwf2->n; ++i) {
751 for (j = 0; j < pwf1->n; ++j) {
756 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
757 isl_set_copy(pwf2->p[i].set));
758 is_empty = isl_set_is_empty(common);
759 if (is_empty < 0 || is_empty) {
760 isl_set_free(common);
765 covers = qpolynomial_fold_covers_on_domain(common,
766 pwf1->p[j].fold, pwf2->p[i].fold);
767 isl_set_free(common);
768 if (covers < 0 || !covers)
776 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
777 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
785 ctx = fold->dim->ctx;
786 isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
788 fold = isl_qpolynomial_fold_cow(fold);
792 isl_dim_free(fold->dim);
793 fold->dim = isl_dim_copy(morph->ran->dim);
797 for (i = 0; i < fold->n; ++i) {
798 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
799 isl_morph_copy(morph));
804 isl_morph_free(morph);
808 isl_qpolynomial_fold_free(fold);
809 isl_morph_free(morph);
813 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
816 return isl_fold_list;
820 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
821 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
829 if (isl_dim_equal(fold->dim, dim)) {
834 fold = isl_qpolynomial_fold_cow(fold);
838 isl_dim_free(fold->dim);
839 fold->dim = isl_dim_copy(dim);
843 for (i = 0; i < fold->n; ++i) {
844 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
854 isl_qpolynomial_fold_free(fold);
859 int isl_qpolynomial_fold_foreach_qpolynomial(
860 __isl_keep isl_qpolynomial_fold *fold,
861 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
868 for (i = 0; i < fold->n; ++i)
869 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
875 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
876 __isl_take isl_qpolynomial_fold *fold,
877 enum isl_dim_type dst_type, unsigned dst_pos,
878 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
885 fold = isl_qpolynomial_fold_cow(fold);
889 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
890 src_type, src_pos, n);
894 for (i = 0; i < fold->n; ++i) {
895 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
896 dst_type, dst_pos, src_type, src_pos, n);
903 isl_qpolynomial_fold_free(fold);
907 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
908 * in fold->qp[k] by subs[i].
910 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
911 __isl_take isl_qpolynomial_fold *fold,
912 enum isl_dim_type type, unsigned first, unsigned n,
913 __isl_keep isl_qpolynomial **subs)
920 fold = isl_qpolynomial_fold_cow(fold);
924 for (i = 0; i < fold->n; ++i) {
925 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
926 type, first, n, subs);
933 isl_qpolynomial_fold_free(fold);