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
);