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
,
1427 map
= isl_map_from_range(set
);
1428 return isl_map_apply_pw_qpolynomial_fold(map
, pwf
, tight
);
1431 struct isl_apply_fold_data
{
1432 isl_union_pw_qpolynomial_fold
*upwf
;
1433 isl_union_pw_qpolynomial_fold
*res
;
1438 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold
*pwf
,
1443 struct isl_apply_fold_data
*data
= user
;
1446 map_dim
= isl_map_get_space(data
->map
);
1447 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1448 ok
= compatible_range(map_dim
, pwf_dim
);
1449 isl_space_free(map_dim
);
1450 isl_space_free(pwf_dim
);
1453 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1454 pwf
, data
->tight
? &data
->tight
: NULL
);
1455 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1458 isl_pw_qpolynomial_fold_free(pwf
);
1463 static int map_apply(__isl_take isl_map
*map
, void *user
)
1465 struct isl_apply_fold_data
*data
= user
;
1469 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1470 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1476 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1477 __isl_take isl_union_map
*umap
,
1478 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1482 struct isl_apply_fold_data data
;
1484 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1485 isl_union_map_get_space(umap
));
1486 umap
= isl_union_map_align_params(umap
,
1487 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1490 data
.tight
= tight
? 1 : 0;
1491 dim
= isl_union_pw_qpolynomial_fold_get_space(upwf
);
1492 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1493 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1494 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1497 isl_union_map_free(umap
);
1498 isl_union_pw_qpolynomial_fold_free(upwf
);
1501 *tight
= data
.tight
;
1505 isl_union_map_free(umap
);
1506 isl_union_pw_qpolynomial_fold_free(upwf
);
1507 isl_union_pw_qpolynomial_fold_free(data
.res
);
1511 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_set_apply_union_pw_qpolynomial_fold(
1512 __isl_take isl_union_set
*uset
,
1513 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1515 return isl_union_map_apply_union_pw_qpolynomial_fold(uset
, upwf
, tight
);
1518 /* Reorder the dimension of "fold" according to the given reordering.
1520 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign(
1521 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1525 fold
= isl_qpolynomial_fold_cow(fold
);
1529 for (i
= 0; i
< fold
->n
; ++i
) {
1530 fold
->qp
[i
] = isl_qpolynomial_realign(fold
->qp
[i
],
1531 isl_reordering_copy(r
));
1536 fold
= isl_qpolynomial_fold_reset_space(fold
, isl_space_copy(r
->dim
));
1538 isl_reordering_free(r
);
1542 isl_qpolynomial_fold_free(fold
);
1543 isl_reordering_free(r
);
1547 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_mul_isl_int(
1548 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1552 if (isl_int_is_one(v
))
1554 if (fold
&& isl_int_is_zero(v
)) {
1555 isl_qpolynomial_fold
*zero
;
1556 isl_space
*dim
= isl_space_copy(fold
->dim
);
1557 zero
= isl_qpolynomial_fold_empty(fold
->type
, dim
);
1558 isl_qpolynomial_fold_free(fold
);
1562 fold
= isl_qpolynomial_fold_cow(fold
);
1566 if (isl_int_is_neg(v
))
1567 fold
->type
= isl_fold_type_negate(fold
->type
);
1568 for (i
= 0; i
< fold
->n
; ++i
) {
1569 fold
->qp
[i
] = isl_qpolynomial_mul_isl_int(fold
->qp
[i
], v
);
1576 isl_qpolynomial_fold_free(fold
);
1580 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale(
1581 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1583 return isl_qpolynomial_fold_mul_isl_int(fold
, v
);