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);
354 #define PW isl_pw_qpolynomial_fold
356 #define EL isl_qpolynomial_fold
358 #define IS_ZERO is_empty
362 #define ADD(d,e1,e2) isl_qpolynomial_fold_fold_on_domain(d,e1,e2)
364 #include <isl_pw_templ.c>
367 #define UNION isl_union_pw_qpolynomial_fold
369 #define PART isl_pw_qpolynomial_fold
371 #define PARTS pw_qpolynomial_fold
373 #include <isl_union_templ.c>
375 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
376 __isl_take isl_dim *dim)
378 return qpolynomial_fold_alloc(type, dim, 0);
381 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
382 enum isl_fold type, __isl_take isl_qpolynomial *qp)
384 isl_qpolynomial_fold *fold;
389 fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
398 isl_qpolynomial_fold_free(fold);
399 isl_qpolynomial_free(qp);
403 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
404 __isl_keep isl_qpolynomial_fold *fold)
413 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
414 __isl_keep isl_qpolynomial_fold *fold)
417 isl_qpolynomial_fold *dup;
421 dup = qpolynomial_fold_alloc(fold->type,
422 isl_dim_copy(fold->dim), fold->n);
427 for (i = 0; i < fold->n; ++i) {
428 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
435 isl_qpolynomial_fold_free(dup);
439 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
440 __isl_take isl_qpolynomial_fold *fold)
448 return isl_qpolynomial_fold_dup(fold);
451 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
460 for (i = 0; i < fold->n; ++i)
461 isl_qpolynomial_free(fold->qp[i]);
462 isl_dim_free(fold->dim);
466 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
474 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
475 __isl_take isl_qpolynomial_fold *fold1,
476 __isl_take isl_qpolynomial_fold *fold2)
479 struct isl_qpolynomial_fold *res = NULL;
481 if (!fold1 || !fold2)
484 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
485 isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
488 if (isl_qpolynomial_fold_is_empty(fold1)) {
489 isl_qpolynomial_fold_free(fold1);
493 if (isl_qpolynomial_fold_is_empty(fold2)) {
494 isl_qpolynomial_fold_free(fold2);
498 res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
499 fold1->n + fold2->n);
503 for (i = 0; i < fold1->n; ++i) {
504 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
505 if (!res->qp[res->n])
510 for (i = 0; i < fold2->n; ++i) {
511 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
512 if (!res->qp[res->n])
517 isl_qpolynomial_fold_free(fold1);
518 isl_qpolynomial_fold_free(fold2);
522 isl_qpolynomial_fold_free(res);
523 isl_qpolynomial_fold_free(fold1);
524 isl_qpolynomial_fold_free(fold2);
528 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
529 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
532 isl_pw_qpolynomial_fold *pwf;
537 pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
539 for (i = 0; i < pwqp->n; ++i)
540 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
541 isl_set_copy(pwqp->p[i].set),
542 isl_qpolynomial_fold_alloc(type,
543 isl_qpolynomial_copy(pwqp->p[i].qp)));
545 isl_pw_qpolynomial_free(pwqp);
550 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
551 __isl_keep isl_qpolynomial_fold *fold2)
555 if (!fold1 || !fold2)
558 if (fold1->n != fold2->n)
561 /* We probably want to sort the qps first... */
562 for (i = 0; i < fold1->n; ++i) {
563 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
571 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
572 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
578 isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
579 isl_assert(pnt->dim->ctx,
580 fold->type == isl_fold_max || fold->type == isl_fold_min,
584 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
587 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
588 isl_point_copy(pnt));
589 for (i = 1; i < fold->n; ++i) {
590 isl_qpolynomial *qp_i;
591 qp_i = isl_qpolynomial_eval(
592 isl_qpolynomial_copy(fold->qp[i]),
593 isl_point_copy(pnt));
594 if (fold->type == isl_fold_max)
595 qp = isl_qpolynomial_max_cst(qp, qp_i);
597 qp = isl_qpolynomial_min_cst(qp, qp_i);
600 isl_qpolynomial_fold_free(fold);
605 isl_qpolynomial_fold_free(fold);
610 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
615 for (i = 0; i < pwf->n; ++i)
616 n += pwf->p[i].fold->n;
621 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
622 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
625 isl_qpolynomial *opt;
631 isl_dim *dim = isl_dim_copy(fold->dim);
633 isl_qpolynomial_fold_free(fold);
634 return isl_qpolynomial_zero(dim);
637 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
638 isl_set_copy(set), max);
639 for (i = 1; i < fold->n; ++i) {
640 isl_qpolynomial *opt_i;
641 opt_i = isl_qpolynomial_opt_on_domain(
642 isl_qpolynomial_copy(fold->qp[i]),
643 isl_set_copy(set), max);
645 opt = isl_qpolynomial_max_cst(opt, opt_i);
647 opt = isl_qpolynomial_min_cst(opt, opt_i);
651 isl_qpolynomial_fold_free(fold);
656 isl_qpolynomial_fold_free(fold);
660 /* Check whether for each quasi-polynomial in "fold2" there is
661 * a quasi-polynomial in "fold1" that dominates it on "set".
663 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
664 __isl_keep isl_qpolynomial_fold *fold1,
665 __isl_keep isl_qpolynomial_fold *fold2)
670 if (!set || !fold1 || !fold2)
673 covers = fold1->type == isl_fold_max ? 1 : -1;
675 for (i = 0; i < fold2->n; ++i) {
676 for (j = 0; j < fold1->n; ++j) {
680 d = isl_qpolynomial_sub(
681 isl_qpolynomial_copy(fold1->qp[j]),
682 isl_qpolynomial_copy(fold2->qp[i]));
683 sgn = isl_qpolynomial_sign(set, d);
684 isl_qpolynomial_free(d);
695 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
696 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
699 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
700 __isl_keep isl_pw_qpolynomial_fold *pwf2)
703 isl_set *dom1, *dom2;
714 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
715 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
716 is_subset = isl_set_is_subset(dom2, dom1);
720 if (is_subset < 0 || !is_subset)
723 for (i = 0; i < pwf2->n; ++i) {
724 for (j = 0; j < pwf1->n; ++j) {
729 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
730 isl_set_copy(pwf2->p[i].set));
731 is_empty = isl_set_is_empty(common);
732 if (is_empty < 0 || is_empty) {
733 isl_set_free(common);
738 covers = qpolynomial_fold_covers_on_domain(common,
739 pwf1->p[j].fold, pwf2->p[i].fold);
740 isl_set_free(common);
741 if (covers < 0 || !covers)
749 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
750 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
758 ctx = fold->dim->ctx;
759 isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
761 fold = isl_qpolynomial_fold_cow(fold);
765 isl_dim_free(fold->dim);
766 fold->dim = isl_dim_copy(morph->ran->dim);
770 for (i = 0; i < fold->n; ++i) {
771 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
772 isl_morph_copy(morph));
777 isl_morph_free(morph);
781 isl_qpolynomial_fold_free(fold);
782 isl_morph_free(morph);
786 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
789 return isl_fold_list;
793 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
794 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
802 if (isl_dim_equal(fold->dim, dim)) {
807 fold = isl_qpolynomial_fold_cow(fold);
811 isl_dim_free(fold->dim);
812 fold->dim = isl_dim_copy(dim);
816 for (i = 0; i < fold->n; ++i) {
817 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
827 isl_qpolynomial_fold_free(fold);
832 int isl_qpolynomial_fold_foreach_qpolynomial(
833 __isl_keep isl_qpolynomial_fold *fold,
834 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
841 for (i = 0; i < fold->n; ++i)
842 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
848 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
849 __isl_take isl_qpolynomial_fold *fold,
850 enum isl_dim_type dst_type, unsigned dst_pos,
851 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
858 fold = isl_qpolynomial_fold_cow(fold);
862 fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
863 src_type, src_pos, n);
867 for (i = 0; i < fold->n; ++i) {
868 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
869 dst_type, dst_pos, src_type, src_pos, n);
876 isl_qpolynomial_fold_free(fold);