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
)
51 fold
= isl_qpolynomial_fold_cow(fold
);
55 for (i
= 0; i
< fold
->n
; ++i
) {
56 fold
->qp
[i
] = isl_qpolynomial_reset_dim(fold
->qp
[i
],
62 isl_dim_free(fold
->dim
);
67 isl_qpolynomial_fold_free(fold
);
72 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
73 enum isl_dim_type type
, unsigned first
, unsigned n
)
79 if (fold
->n
== 0 || n
== 0)
82 for (i
= 0; i
< fold
->n
; ++i
) {
83 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
85 if (involves
< 0 || involves
)
91 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
92 __isl_take isl_qpolynomial_fold
*fold
,
93 enum isl_dim_type type
, unsigned first
, unsigned n
)
102 fold
= isl_qpolynomial_fold_cow(fold
);
105 fold
->dim
= isl_dim_drop(fold
->dim
, type
, first
, n
);
109 for (i
= 0; i
< fold
->n
; ++i
) {
110 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
118 isl_qpolynomial_fold_free(fold
);
122 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
123 __isl_take isl_qpolynomial_fold
*fold
,
124 enum isl_dim_type type
, unsigned first
, unsigned n
)
130 if (n
== 0 && !isl_dim_is_named_or_nested(fold
->dim
, type
))
133 fold
= isl_qpolynomial_fold_cow(fold
);
136 fold
->dim
= isl_dim_insert(fold
->dim
, type
, first
, n
);
140 for (i
= 0; i
< fold
->n
; ++i
) {
141 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
149 isl_qpolynomial_fold_free(fold
);
153 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
155 struct isl_upoly_cst
*cst
;
157 cst
= isl_upoly_as_cst(qp
->upoly
);
161 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
164 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
165 __isl_keep isl_qpolynomial
*qp
)
167 enum isl_lp_result res
;
172 aff
= isl_qpolynomial_extract_affine(qp
);
178 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
180 if (res
== isl_lp_error
)
182 if (res
== isl_lp_empty
||
183 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
188 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
190 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
199 /* Determine, if possible, the sign of the quasipolynomial "qp" on
202 * If qp is a constant, then the problem is trivial.
203 * If qp is linear, then we check if the minimum of the corresponding
204 * affine constraint is non-negative or if the maximum is non-positive.
206 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
207 * in "set". If so, we write qp(v,v') as
209 * q(v,v') * (v - l) + r(v')
211 * if q(v,v') and r(v') have the same known sign, then the original
212 * quasipolynomial has the same sign as well.
219 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
220 __isl_keep isl_qpolynomial
*qp
)
225 struct isl_upoly_rec
*rec
;
228 enum isl_lp_result res
;
231 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
235 return isl_qpolynomial_cst_sign(qp
);
237 is
= isl_qpolynomial_is_affine(qp
);
241 return isl_qpolynomial_aff_sign(set
, qp
);
243 if (qp
->div
->n_row
> 0)
246 rec
= isl_upoly_as_rec(qp
->upoly
);
250 d
= isl_dim_total(qp
->dim
);
251 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
255 isl_seq_clr(v
->el
+ 1, 1 + d
);
256 isl_int_set_si(v
->el
[0], 1);
257 isl_int_set_si(v
->el
[2 + qp
->upoly
->var
], 1);
261 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
262 if (res
== isl_lp_ok
) {
263 isl_qpolynomial
*min
;
264 isl_qpolynomial
*base
;
265 isl_qpolynomial
*r
, *q
;
268 min
= isl_qpolynomial_cst(isl_dim_copy(qp
->dim
), l
);
269 base
= isl_qpolynomial_pow(isl_dim_copy(qp
->dim
),
272 r
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
273 isl_upoly_copy(rec
->p
[rec
->n
- 1]));
274 q
= isl_qpolynomial_copy(r
);
276 for (i
= rec
->n
- 2; i
>= 0; --i
) {
277 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
278 t
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
279 isl_upoly_copy(rec
->p
[i
]));
280 r
= isl_qpolynomial_add(r
, t
);
283 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
284 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
287 if (isl_qpolynomial_is_zero(q
))
288 sgn
= isl_qpolynomial_sign(set
, r
);
289 else if (isl_qpolynomial_is_zero(r
))
290 sgn
= isl_qpolynomial_sign(set
, q
);
293 sgn_r
= isl_qpolynomial_sign(set
, r
);
294 sgn_q
= isl_qpolynomial_sign(set
, q
);
299 isl_qpolynomial_free(min
);
300 isl_qpolynomial_free(base
);
301 isl_qpolynomial_free(q
);
302 isl_qpolynomial_free(r
);
312 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
313 __isl_keep isl_set
*set
,
314 __isl_take isl_qpolynomial_fold
*fold1
,
315 __isl_take isl_qpolynomial_fold
*fold2
)
319 struct isl_qpolynomial_fold
*res
= NULL
;
322 if (!fold1
|| !fold2
)
325 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
326 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
329 better
= fold1
->type
== isl_fold_max
? -1 : 1;
331 if (isl_qpolynomial_fold_is_empty(fold1
)) {
332 isl_qpolynomial_fold_free(fold1
);
336 if (isl_qpolynomial_fold_is_empty(fold2
)) {
337 isl_qpolynomial_fold_free(fold2
);
341 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
342 fold1
->n
+ fold2
->n
);
346 for (i
= 0; i
< fold1
->n
; ++i
) {
347 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
348 if (!res
->qp
[res
->n
])
354 for (i
= 0; i
< fold2
->n
; ++i
) {
355 for (j
= n1
- 1; j
>= 0; --j
) {
358 d
= isl_qpolynomial_sub(
359 isl_qpolynomial_copy(res
->qp
[j
]),
360 isl_qpolynomial_copy(fold2
->qp
[i
]));
361 sgn
= isl_qpolynomial_sign(set
, d
);
362 isl_qpolynomial_free(d
);
367 isl_qpolynomial_free(res
->qp
[j
]);
369 res
->qp
[j
] = res
->qp
[n1
- 1];
371 if (n1
!= res
->n
- 1)
372 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
377 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
378 if (!res
->qp
[res
->n
])
383 isl_qpolynomial_fold_free(fold1
);
384 isl_qpolynomial_fold_free(fold2
);
388 isl_qpolynomial_fold_free(res
);
389 isl_qpolynomial_fold_free(fold1
);
390 isl_qpolynomial_fold_free(fold2
);
394 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
395 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
402 if (isl_qpolynomial_is_zero(qp
)) {
403 isl_qpolynomial_free(qp
);
407 fold
= isl_qpolynomial_fold_cow(fold
);
411 for (i
= 0; i
< fold
->n
; ++i
) {
412 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
413 isl_qpolynomial_copy(qp
));
418 isl_qpolynomial_free(qp
);
421 isl_qpolynomial_fold_free(fold
);
422 isl_qpolynomial_free(qp
);
426 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
427 __isl_keep isl_set
*dom
,
428 __isl_take isl_qpolynomial_fold
*fold1
,
429 __isl_take isl_qpolynomial_fold
*fold2
)
432 isl_qpolynomial_fold
*res
= NULL
;
434 if (!fold1
|| !fold2
)
437 if (isl_qpolynomial_fold_is_empty(fold1
)) {
438 isl_qpolynomial_fold_free(fold1
);
442 if (isl_qpolynomial_fold_is_empty(fold2
)) {
443 isl_qpolynomial_fold_free(fold2
);
447 if (fold1
->n
== 1 && fold2
->n
!= 1)
448 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
451 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
452 isl_qpolynomial_copy(fold2
->qp
[0]));
453 isl_qpolynomial_fold_free(fold2
);
457 res
= isl_qpolynomial_fold_add_qpolynomial(
458 isl_qpolynomial_fold_copy(fold1
),
459 isl_qpolynomial_copy(fold2
->qp
[0]));
461 for (i
= 1; i
< fold2
->n
; ++i
) {
462 isl_qpolynomial_fold
*res_i
;
463 res_i
= isl_qpolynomial_fold_add_qpolynomial(
464 isl_qpolynomial_fold_copy(fold1
),
465 isl_qpolynomial_copy(fold2
->qp
[i
]));
466 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
469 isl_qpolynomial_fold_free(fold1
);
470 isl_qpolynomial_fold_free(fold2
);
473 isl_qpolynomial_fold_free(res
);
474 isl_qpolynomial_fold_free(fold1
);
475 isl_qpolynomial_fold_free(fold2
);
479 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
480 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
487 fold
= isl_qpolynomial_fold_cow(fold
);
491 for (i
= 0; i
< fold
->n
; ++i
) {
492 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
493 isl_basic_set_copy(eq
));
498 isl_basic_set_free(eq
);
501 isl_basic_set_free(eq
);
502 isl_qpolynomial_fold_free(fold
);
509 #define PW isl_pw_qpolynomial_fold
511 #define EL isl_qpolynomial_fold
513 #define IS_ZERO is_empty
517 #include <isl_pw_templ.c>
520 #define UNION isl_union_pw_qpolynomial_fold
522 #define PART isl_pw_qpolynomial_fold
524 #define PARTS pw_qpolynomial_fold
526 #include <isl_union_templ.c>
528 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
529 __isl_take isl_dim
*dim
)
531 return qpolynomial_fold_alloc(type
, dim
, 0);
534 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
535 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
537 isl_qpolynomial_fold
*fold
;
542 fold
= qpolynomial_fold_alloc(type
, isl_dim_copy(qp
->dim
), 1);
551 isl_qpolynomial_fold_free(fold
);
552 isl_qpolynomial_free(qp
);
556 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
557 __isl_keep isl_qpolynomial_fold
*fold
)
566 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
567 __isl_keep isl_qpolynomial_fold
*fold
)
570 isl_qpolynomial_fold
*dup
;
574 dup
= qpolynomial_fold_alloc(fold
->type
,
575 isl_dim_copy(fold
->dim
), fold
->n
);
580 for (i
= 0; i
< fold
->n
; ++i
) {
581 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
588 isl_qpolynomial_fold_free(dup
);
592 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
593 __isl_take isl_qpolynomial_fold
*fold
)
601 return isl_qpolynomial_fold_dup(fold
);
604 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold
*fold
)
613 for (i
= 0; i
< fold
->n
; ++i
)
614 isl_qpolynomial_free(fold
->qp
[i
]);
615 isl_dim_free(fold
->dim
);
619 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
627 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
628 __isl_take isl_qpolynomial_fold
*fold1
,
629 __isl_take isl_qpolynomial_fold
*fold2
)
632 struct isl_qpolynomial_fold
*res
= NULL
;
634 if (!fold1
|| !fold2
)
637 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
638 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
641 if (isl_qpolynomial_fold_is_empty(fold1
)) {
642 isl_qpolynomial_fold_free(fold1
);
646 if (isl_qpolynomial_fold_is_empty(fold2
)) {
647 isl_qpolynomial_fold_free(fold2
);
651 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
652 fold1
->n
+ fold2
->n
);
656 for (i
= 0; i
< fold1
->n
; ++i
) {
657 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
658 if (!res
->qp
[res
->n
])
663 for (i
= 0; i
< fold2
->n
; ++i
) {
664 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
665 if (!res
->qp
[res
->n
])
670 isl_qpolynomial_fold_free(fold1
);
671 isl_qpolynomial_fold_free(fold2
);
675 isl_qpolynomial_fold_free(res
);
676 isl_qpolynomial_fold_free(fold1
);
677 isl_qpolynomial_fold_free(fold2
);
681 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
682 __isl_take isl_pw_qpolynomial_fold
*pw1
,
683 __isl_take isl_pw_qpolynomial_fold
*pw2
)
686 struct isl_pw_qpolynomial_fold
*res
;
692 isl_assert(pw1
->dim
->ctx
, isl_dim_equal(pw1
->dim
, pw2
->dim
), goto error
);
694 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
695 isl_pw_qpolynomial_fold_free(pw1
);
699 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
700 isl_pw_qpolynomial_fold_free(pw2
);
704 if (pw1
->type
!= pw2
->type
)
705 isl_die(set
->ctx
, isl_error_invalid
, "fold types don't match",
708 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
709 res
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1
->dim
),
712 for (i
= 0; i
< pw1
->n
; ++i
) {
713 set
= isl_set_copy(pw1
->p
[i
].set
);
714 for (j
= 0; j
< pw2
->n
; ++j
) {
715 struct isl_set
*common
;
716 isl_qpolynomial_fold
*sum
;
717 set
= isl_set_subtract(set
,
718 isl_set_copy(pw2
->p
[j
].set
));
719 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
720 isl_set_copy(pw2
->p
[j
].set
));
721 if (isl_set_fast_is_empty(common
)) {
722 isl_set_free(common
);
726 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
727 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
728 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
730 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
732 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
733 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
736 for (j
= 0; j
< pw2
->n
; ++j
) {
737 set
= isl_set_copy(pw2
->p
[j
].set
);
738 for (i
= 0; i
< pw1
->n
; ++i
)
739 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
740 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
741 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
744 isl_pw_qpolynomial_fold_free(pw1
);
745 isl_pw_qpolynomial_fold_free(pw2
);
749 isl_pw_qpolynomial_fold_free(pw1
);
750 isl_pw_qpolynomial_fold_free(pw2
);
754 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
755 __isl_take isl_union_pw_qpolynomial_fold
*u
,
756 __isl_take isl_pw_qpolynomial_fold
*part
)
759 struct isl_hash_table_entry
*entry
;
761 u
= isl_union_pw_qpolynomial_fold_cow(u
);
766 isl_assert(u
->dim
->ctx
, isl_dim_match(part
->dim
, isl_dim_param
, u
->dim
,
767 isl_dim_param
), goto error
);
769 hash
= isl_dim_get_hash(part
->dim
);
770 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
771 &has_dim
, part
->dim
, 1);
778 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
779 isl_pw_qpolynomial_fold_copy(part
));
782 isl_pw_qpolynomial_fold_free(part
);
787 isl_pw_qpolynomial_fold_free(part
);
788 isl_union_pw_qpolynomial_fold_free(u
);
792 static int fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
794 isl_union_pw_qpolynomial_fold
**u
;
795 u
= (isl_union_pw_qpolynomial_fold
**)user
;
797 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
802 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
803 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
804 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
806 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
811 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
812 &fold_part
, &u1
) < 0)
815 isl_union_pw_qpolynomial_fold_free(u2
);
819 isl_union_pw_qpolynomial_fold_free(u1
);
820 isl_union_pw_qpolynomial_fold_free(u2
);
824 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
825 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
828 isl_pw_qpolynomial_fold
*pwf
;
833 pwf
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp
->dim
), type
,
836 for (i
= 0; i
< pwqp
->n
; ++i
)
837 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
838 isl_set_copy(pwqp
->p
[i
].set
),
839 isl_qpolynomial_fold_alloc(type
,
840 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
842 isl_pw_qpolynomial_free(pwqp
);
847 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
848 __isl_keep isl_qpolynomial_fold
*fold2
)
852 if (!fold1
|| !fold2
)
855 if (fold1
->n
!= fold2
->n
)
858 /* We probably want to sort the qps first... */
859 for (i
= 0; i
< fold1
->n
; ++i
) {
860 int eq
= isl_qpolynomial_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
868 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_eval(
869 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
875 isl_assert(pnt
->dim
->ctx
, isl_dim_equal(pnt
->dim
, fold
->dim
), goto error
);
876 isl_assert(pnt
->dim
->ctx
,
877 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
881 qp
= isl_qpolynomial_zero(isl_dim_copy(fold
->dim
));
884 qp
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
885 isl_point_copy(pnt
));
886 for (i
= 1; i
< fold
->n
; ++i
) {
887 isl_qpolynomial
*qp_i
;
888 qp_i
= isl_qpolynomial_eval(
889 isl_qpolynomial_copy(fold
->qp
[i
]),
890 isl_point_copy(pnt
));
891 if (fold
->type
== isl_fold_max
)
892 qp
= isl_qpolynomial_max_cst(qp
, qp_i
);
894 qp
= isl_qpolynomial_min_cst(qp
, qp_i
);
897 isl_qpolynomial_fold_free(fold
);
902 isl_qpolynomial_fold_free(fold
);
907 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
912 for (i
= 0; i
< pwf
->n
; ++i
)
913 n
+= pwf
->p
[i
].fold
->n
;
918 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_opt_on_domain(
919 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
922 isl_qpolynomial
*opt
;
928 isl_dim
*dim
= isl_dim_copy(fold
->dim
);
930 isl_qpolynomial_fold_free(fold
);
931 return isl_qpolynomial_zero(dim
);
934 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
935 isl_set_copy(set
), max
);
936 for (i
= 1; i
< fold
->n
; ++i
) {
937 isl_qpolynomial
*opt_i
;
938 opt_i
= isl_qpolynomial_opt_on_domain(
939 isl_qpolynomial_copy(fold
->qp
[i
]),
940 isl_set_copy(set
), max
);
942 opt
= isl_qpolynomial_max_cst(opt
, opt_i
);
944 opt
= isl_qpolynomial_min_cst(opt
, opt_i
);
948 isl_qpolynomial_fold_free(fold
);
953 isl_qpolynomial_fold_free(fold
);
957 /* Check whether for each quasi-polynomial in "fold2" there is
958 * a quasi-polynomial in "fold1" that dominates it on "set".
960 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
961 __isl_keep isl_qpolynomial_fold
*fold1
,
962 __isl_keep isl_qpolynomial_fold
*fold2
)
967 if (!set
|| !fold1
|| !fold2
)
970 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
972 for (i
= 0; i
< fold2
->n
; ++i
) {
973 for (j
= 0; j
< fold1
->n
; ++j
) {
977 d
= isl_qpolynomial_sub(
978 isl_qpolynomial_copy(fold1
->qp
[j
]),
979 isl_qpolynomial_copy(fold2
->qp
[i
]));
980 sgn
= isl_qpolynomial_sign(set
, d
);
981 isl_qpolynomial_free(d
);
992 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
993 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
996 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold
*pwf1
,
997 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1000 isl_set
*dom1
, *dom2
;
1011 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1012 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1013 is_subset
= isl_set_is_subset(dom2
, dom1
);
1017 if (is_subset
< 0 || !is_subset
)
1020 for (i
= 0; i
< pwf2
->n
; ++i
) {
1021 for (j
= 0; j
< pwf1
->n
; ++j
) {
1026 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1027 isl_set_copy(pwf2
->p
[i
].set
));
1028 is_empty
= isl_set_is_empty(common
);
1029 if (is_empty
< 0 || is_empty
) {
1030 isl_set_free(common
);
1035 covers
= qpolynomial_fold_covers_on_domain(common
,
1036 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1037 isl_set_free(common
);
1038 if (covers
< 0 || !covers
)
1046 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph(
1047 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1052 if (!fold
|| !morph
)
1055 ctx
= fold
->dim
->ctx
;
1056 isl_assert(ctx
, isl_dim_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1058 fold
= isl_qpolynomial_fold_cow(fold
);
1062 isl_dim_free(fold
->dim
);
1063 fold
->dim
= isl_dim_copy(morph
->ran
->dim
);
1067 for (i
= 0; i
< fold
->n
; ++i
) {
1068 fold
->qp
[i
] = isl_qpolynomial_morph(fold
->qp
[i
],
1069 isl_morph_copy(morph
));
1074 isl_morph_free(morph
);
1078 isl_qpolynomial_fold_free(fold
);
1079 isl_morph_free(morph
);
1083 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1086 return isl_fold_list
;
1090 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1091 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1094 return isl_fold_list
;
1098 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1099 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
1107 if (isl_dim_equal(fold
->dim
, dim
)) {
1112 fold
= isl_qpolynomial_fold_cow(fold
);
1116 isl_dim_free(fold
->dim
);
1117 fold
->dim
= isl_dim_copy(dim
);
1121 for (i
= 0; i
< fold
->n
; ++i
) {
1122 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1132 isl_qpolynomial_fold_free(fold
);
1137 int isl_qpolynomial_fold_foreach_qpolynomial(
1138 __isl_keep isl_qpolynomial_fold
*fold
,
1139 int (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1146 for (i
= 0; i
< fold
->n
; ++i
)
1147 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1153 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1154 __isl_take isl_qpolynomial_fold
*fold
,
1155 enum isl_dim_type dst_type
, unsigned dst_pos
,
1156 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1163 fold
= isl_qpolynomial_fold_cow(fold
);
1167 fold
->dim
= isl_dim_move(fold
->dim
, dst_type
, dst_pos
,
1168 src_type
, src_pos
, n
);
1172 for (i
= 0; i
< fold
->n
; ++i
) {
1173 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1174 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1181 isl_qpolynomial_fold_free(fold
);
1185 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1186 * in fold->qp[k] by subs[i].
1188 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1189 __isl_take isl_qpolynomial_fold
*fold
,
1190 enum isl_dim_type type
, unsigned first
, unsigned n
,
1191 __isl_keep isl_qpolynomial
**subs
)
1198 fold
= isl_qpolynomial_fold_cow(fold
);
1202 for (i
= 0; i
< fold
->n
; ++i
) {
1203 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1204 type
, first
, n
, subs
);
1211 isl_qpolynomial_fold_free(fold
);
1215 static int add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1218 isl_pw_qpolynomial_fold
*pwf
;
1219 isl_union_pw_qpolynomial_fold
**upwf
;
1221 struct isl_hash_table_entry
*entry
;
1223 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1225 ctx
= pwqp
->dim
->ctx
;
1226 hash
= isl_dim_get_hash(pwqp
->dim
);
1227 entry
= isl_hash_table_find(ctx
, &(*upwf
)->table
,
1228 hash
, &has_dim
, pwqp
->dim
, 1);
1232 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1236 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1239 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
)) {
1240 isl_pw_qpolynomial_fold_free(entry
->data
);
1241 isl_hash_table_remove(ctx
, &(*upwf
)->table
, entry
);
1247 isl_pw_qpolynomial_free(pwqp
);
1251 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1252 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1253 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1255 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1256 if (!upwf
|| !upwqp
)
1259 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1263 isl_union_pw_qpolynomial_free(upwqp
);
1267 isl_union_pw_qpolynomial_fold_free(upwf
);
1268 isl_union_pw_qpolynomial_free(upwqp
);
1272 static int compatible_range(__isl_keep isl_dim
*dim1
, __isl_keep isl_dim
*dim2
)
1275 m
= isl_dim_match(dim1
, isl_dim_param
, dim2
, isl_dim_param
);
1278 return isl_dim_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_set
);
1281 /* Compute the intersection of the range of the map and the domain
1282 * of the piecewise quasipolynomial reduction and then compute a bound
1283 * on the associated quasipolynomial reduction over all elements
1284 * in this intersection.
1286 * We first introduce some unconstrained dimensions in the
1287 * piecewise quasipolynomial, intersect the resulting domain
1288 * with the wrapped map and the compute the sum.
1290 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1291 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1301 ctx
= isl_map_get_ctx(map
);
1305 map_dim
= isl_map_get_dim(map
);
1306 pwf_dim
= isl_pw_qpolynomial_fold_get_dim(pwf
);
1307 ok
= compatible_range(map_dim
, pwf_dim
);
1308 isl_dim_free(map_dim
);
1309 isl_dim_free(pwf_dim
);
1311 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1314 n_in
= isl_map_dim(map
, isl_dim_in
);
1315 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_set
, 0, n_in
);
1317 dom
= isl_map_wrap(map
);
1318 pwf
= isl_pw_qpolynomial_fold_reset_dim(pwf
, isl_set_get_dim(dom
));
1320 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1321 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1326 isl_pw_qpolynomial_fold_free(pwf
);
1330 struct isl_apply_fold_data
{
1331 isl_union_pw_qpolynomial_fold
*upwf
;
1332 isl_union_pw_qpolynomial_fold
*res
;
1337 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold
*pwf
,
1342 struct isl_apply_fold_data
*data
= user
;
1345 map_dim
= isl_map_get_dim(data
->map
);
1346 pwf_dim
= isl_pw_qpolynomial_fold_get_dim(pwf
);
1347 ok
= compatible_range(map_dim
, pwf_dim
);
1348 isl_dim_free(map_dim
);
1349 isl_dim_free(pwf_dim
);
1352 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1353 pwf
, data
->tight
? &data
->tight
: NULL
);
1354 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1357 isl_pw_qpolynomial_fold_free(pwf
);
1362 static int map_apply(__isl_take isl_map
*map
, void *user
)
1364 struct isl_apply_fold_data
*data
= user
;
1368 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1369 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1375 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1376 __isl_take isl_union_map
*umap
,
1377 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1381 struct isl_apply_fold_data data
;
1384 data
.tight
= tight
? 1 : 0;
1385 dim
= isl_union_pw_qpolynomial_fold_get_dim(upwf
);
1386 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1387 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1388 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1391 isl_union_map_free(umap
);
1392 isl_union_pw_qpolynomial_fold_free(upwf
);
1395 *tight
= data
.tight
;
1399 isl_union_map_free(umap
);
1400 isl_union_pw_qpolynomial_fold_free(upwf
);
1401 isl_union_pw_qpolynomial_fold_free(data
.res
);