2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the MIT 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_val_private.h>
21 #include <isl_vec_private.h>
22 #include <isl_config.h>
24 enum isl_fold
isl_fold_type_negate(enum isl_fold type
)
35 isl_die(NULL
, isl_error_internal
, "unhandled isl_fold type", abort());
38 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
39 enum isl_fold type
, __isl_take isl_space
*dim
, int n
)
41 isl_qpolynomial_fold
*fold
;
46 isl_assert(dim
->ctx
, n
>= 0, goto error
);
47 fold
= isl_calloc(dim
->ctx
, struct isl_qpolynomial_fold
,
48 sizeof(struct isl_qpolynomial_fold
) +
49 (n
- 1) * sizeof(struct isl_qpolynomial
*));
65 isl_ctx
*isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold
*fold
)
67 return fold
? fold
->dim
->ctx
: NULL
;
70 __isl_give isl_space
*isl_qpolynomial_fold_get_domain_space(
71 __isl_keep isl_qpolynomial_fold
*fold
)
73 return fold
? isl_space_copy(fold
->dim
) : NULL
;
76 __isl_give isl_space
*isl_qpolynomial_fold_get_space(
77 __isl_keep isl_qpolynomial_fold
*fold
)
82 space
= isl_space_copy(fold
->dim
);
83 space
= isl_space_from_domain(space
);
84 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
88 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_domain_space(
89 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*dim
)
93 fold
= isl_qpolynomial_fold_cow(fold
);
97 for (i
= 0; i
< fold
->n
; ++i
) {
98 fold
->qp
[i
] = isl_qpolynomial_reset_domain_space(fold
->qp
[i
],
104 isl_space_free(fold
->dim
);
109 isl_qpolynomial_fold_free(fold
);
114 /* Reset the space of "fold". This function is called from isl_pw_templ.c
115 * and doesn't know if the space of an element object is represented
116 * directly or through its domain. It therefore passes along both.
118 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_space_and_domain(
119 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*space
,
120 __isl_take isl_space
*domain
)
122 isl_space_free(space
);
123 return isl_qpolynomial_fold_reset_domain_space(fold
, domain
);
126 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
127 enum isl_dim_type type
, unsigned first
, unsigned n
)
133 if (fold
->n
== 0 || n
== 0)
136 for (i
= 0; i
< fold
->n
; ++i
) {
137 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
139 if (involves
< 0 || involves
)
145 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_set_dim_name(
146 __isl_take isl_qpolynomial_fold
*fold
,
147 enum isl_dim_type type
, unsigned pos
, const char *s
)
151 fold
= isl_qpolynomial_fold_cow(fold
);
154 fold
->dim
= isl_space_set_dim_name(fold
->dim
, type
, pos
, s
);
158 for (i
= 0; i
< fold
->n
; ++i
) {
159 fold
->qp
[i
] = isl_qpolynomial_set_dim_name(fold
->qp
[i
],
167 isl_qpolynomial_fold_free(fold
);
171 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
172 __isl_take isl_qpolynomial_fold
*fold
,
173 enum isl_dim_type type
, unsigned first
, unsigned n
)
176 enum isl_dim_type set_type
;
183 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
185 fold
= isl_qpolynomial_fold_cow(fold
);
188 fold
->dim
= isl_space_drop_dims(fold
->dim
, set_type
, first
, n
);
192 for (i
= 0; i
< fold
->n
; ++i
) {
193 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
201 isl_qpolynomial_fold_free(fold
);
205 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
206 __isl_take isl_qpolynomial_fold
*fold
,
207 enum isl_dim_type type
, unsigned first
, unsigned n
)
213 if (n
== 0 && !isl_space_is_named_or_nested(fold
->dim
, type
))
216 fold
= isl_qpolynomial_fold_cow(fold
);
219 fold
->dim
= isl_space_insert_dims(fold
->dim
, type
, first
, n
);
223 for (i
= 0; i
< fold
->n
; ++i
) {
224 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
232 isl_qpolynomial_fold_free(fold
);
236 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
238 struct isl_upoly_cst
*cst
;
240 cst
= isl_upoly_as_cst(qp
->upoly
);
244 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
247 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
248 __isl_keep isl_qpolynomial
*qp
)
250 enum isl_lp_result res
;
255 aff
= isl_qpolynomial_extract_affine(qp
);
261 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
263 if (res
== isl_lp_error
)
265 if (res
== isl_lp_empty
||
266 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
271 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
273 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
282 /* Determine, if possible, the sign of the quasipolynomial "qp" on
285 * If qp is a constant, then the problem is trivial.
286 * If qp is linear, then we check if the minimum of the corresponding
287 * affine constraint is non-negative or if the maximum is non-positive.
289 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
290 * in "set". If so, we write qp(v,v') as
292 * q(v,v') * (v - l) + r(v')
294 * if q(v,v') and r(v') have the same known sign, then the original
295 * quasipolynomial has the same sign as well.
302 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
303 __isl_keep isl_qpolynomial
*qp
)
308 struct isl_upoly_rec
*rec
;
311 enum isl_lp_result res
;
314 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
318 return isl_qpolynomial_cst_sign(qp
);
320 is
= isl_qpolynomial_is_affine(qp
);
324 return isl_qpolynomial_aff_sign(set
, qp
);
326 if (qp
->div
->n_row
> 0)
329 rec
= isl_upoly_as_rec(qp
->upoly
);
333 d
= isl_space_dim(qp
->dim
, isl_dim_all
);
334 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
338 isl_seq_clr(v
->el
+ 1, 1 + d
);
339 isl_int_set_si(v
->el
[0], 1);
340 isl_int_set_si(v
->el
[2 + qp
->upoly
->var
], 1);
344 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
345 if (res
== isl_lp_ok
) {
346 isl_qpolynomial
*min
;
347 isl_qpolynomial
*base
;
348 isl_qpolynomial
*r
, *q
;
351 min
= isl_qpolynomial_cst_on_domain(isl_space_copy(qp
->dim
), l
);
352 base
= isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp
->dim
),
355 r
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
356 isl_upoly_copy(rec
->p
[rec
->n
- 1]));
357 q
= isl_qpolynomial_copy(r
);
359 for (i
= rec
->n
- 2; i
>= 0; --i
) {
360 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
361 t
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
362 isl_upoly_copy(rec
->p
[i
]));
363 r
= isl_qpolynomial_add(r
, t
);
366 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
367 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
370 if (isl_qpolynomial_is_zero(q
))
371 sgn
= isl_qpolynomial_sign(set
, r
);
372 else if (isl_qpolynomial_is_zero(r
))
373 sgn
= isl_qpolynomial_sign(set
, q
);
376 sgn_r
= isl_qpolynomial_sign(set
, r
);
377 sgn_q
= isl_qpolynomial_sign(set
, q
);
382 isl_qpolynomial_free(min
);
383 isl_qpolynomial_free(base
);
384 isl_qpolynomial_free(q
);
385 isl_qpolynomial_free(r
);
395 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
396 __isl_keep isl_set
*set
,
397 __isl_take isl_qpolynomial_fold
*fold1
,
398 __isl_take isl_qpolynomial_fold
*fold2
)
402 struct isl_qpolynomial_fold
*res
= NULL
;
405 if (!fold1
|| !fold2
)
408 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
409 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
412 better
= fold1
->type
== isl_fold_max
? -1 : 1;
414 if (isl_qpolynomial_fold_is_empty(fold1
)) {
415 isl_qpolynomial_fold_free(fold1
);
419 if (isl_qpolynomial_fold_is_empty(fold2
)) {
420 isl_qpolynomial_fold_free(fold2
);
424 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
425 fold1
->n
+ fold2
->n
);
429 for (i
= 0; i
< fold1
->n
; ++i
) {
430 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
431 if (!res
->qp
[res
->n
])
437 for (i
= 0; i
< fold2
->n
; ++i
) {
438 for (j
= n1
- 1; j
>= 0; --j
) {
441 d
= isl_qpolynomial_sub(
442 isl_qpolynomial_copy(res
->qp
[j
]),
443 isl_qpolynomial_copy(fold2
->qp
[i
]));
444 sgn
= isl_qpolynomial_sign(set
, d
);
445 isl_qpolynomial_free(d
);
450 isl_qpolynomial_free(res
->qp
[j
]);
452 res
->qp
[j
] = res
->qp
[n1
- 1];
454 if (n1
!= res
->n
- 1)
455 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
460 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
461 if (!res
->qp
[res
->n
])
466 isl_qpolynomial_fold_free(fold1
);
467 isl_qpolynomial_fold_free(fold2
);
471 isl_qpolynomial_fold_free(res
);
472 isl_qpolynomial_fold_free(fold1
);
473 isl_qpolynomial_fold_free(fold2
);
477 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
478 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
485 if (isl_qpolynomial_is_zero(qp
)) {
486 isl_qpolynomial_free(qp
);
490 fold
= isl_qpolynomial_fold_cow(fold
);
494 for (i
= 0; i
< fold
->n
; ++i
) {
495 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
496 isl_qpolynomial_copy(qp
));
501 isl_qpolynomial_free(qp
);
504 isl_qpolynomial_fold_free(fold
);
505 isl_qpolynomial_free(qp
);
509 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
510 __isl_keep isl_set
*dom
,
511 __isl_take isl_qpolynomial_fold
*fold1
,
512 __isl_take isl_qpolynomial_fold
*fold2
)
515 isl_qpolynomial_fold
*res
= NULL
;
517 if (!fold1
|| !fold2
)
520 if (isl_qpolynomial_fold_is_empty(fold1
)) {
521 isl_qpolynomial_fold_free(fold1
);
525 if (isl_qpolynomial_fold_is_empty(fold2
)) {
526 isl_qpolynomial_fold_free(fold2
);
530 if (fold1
->n
== 1 && fold2
->n
!= 1)
531 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
534 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
535 isl_qpolynomial_copy(fold2
->qp
[0]));
536 isl_qpolynomial_fold_free(fold2
);
540 res
= isl_qpolynomial_fold_add_qpolynomial(
541 isl_qpolynomial_fold_copy(fold1
),
542 isl_qpolynomial_copy(fold2
->qp
[0]));
544 for (i
= 1; i
< fold2
->n
; ++i
) {
545 isl_qpolynomial_fold
*res_i
;
546 res_i
= isl_qpolynomial_fold_add_qpolynomial(
547 isl_qpolynomial_fold_copy(fold1
),
548 isl_qpolynomial_copy(fold2
->qp
[i
]));
549 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
552 isl_qpolynomial_fold_free(fold1
);
553 isl_qpolynomial_fold_free(fold2
);
556 isl_qpolynomial_fold_free(res
);
557 isl_qpolynomial_fold_free(fold1
);
558 isl_qpolynomial_fold_free(fold2
);
562 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
563 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
570 fold
= isl_qpolynomial_fold_cow(fold
);
574 for (i
= 0; i
< fold
->n
; ++i
) {
575 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
576 isl_basic_set_copy(eq
));
581 isl_basic_set_free(eq
);
584 isl_basic_set_free(eq
);
585 isl_qpolynomial_fold_free(fold
);
589 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist(
590 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
594 if (!fold
|| !context
)
597 fold
= isl_qpolynomial_fold_cow(fold
);
601 for (i
= 0; i
< fold
->n
; ++i
) {
602 fold
->qp
[i
] = isl_qpolynomial_gist(fold
->qp
[i
],
603 isl_set_copy(context
));
608 isl_set_free(context
);
611 isl_set_free(context
);
612 isl_qpolynomial_fold_free(fold
);
616 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist_params(
617 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
619 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
620 isl_set
*dom_context
= isl_set_universe(space
);
621 dom_context
= isl_set_intersect_params(dom_context
, context
);
622 return isl_qpolynomial_fold_gist(fold
, dom_context
);
628 #define PW isl_pw_qpolynomial_fold
630 #define EL isl_qpolynomial_fold
632 #define EL_IS_ZERO is_empty
636 #define IS_ZERO is_zero
639 #undef DEFAULT_IS_ZERO
640 #define DEFAULT_IS_ZERO 1
645 #include <isl_pw_templ.c>
648 #define UNION isl_union_pw_qpolynomial_fold
650 #define PART isl_pw_qpolynomial_fold
652 #define PARTS pw_qpolynomial_fold
657 #include <isl_union_templ.c>
659 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
660 __isl_take isl_space
*dim
)
662 return qpolynomial_fold_alloc(type
, dim
, 0);
665 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
666 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
668 isl_qpolynomial_fold
*fold
;
673 fold
= qpolynomial_fold_alloc(type
, isl_space_copy(qp
->dim
), 1);
682 isl_qpolynomial_fold_free(fold
);
683 isl_qpolynomial_free(qp
);
687 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
688 __isl_keep isl_qpolynomial_fold
*fold
)
697 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
698 __isl_keep isl_qpolynomial_fold
*fold
)
701 isl_qpolynomial_fold
*dup
;
705 dup
= qpolynomial_fold_alloc(fold
->type
,
706 isl_space_copy(fold
->dim
), fold
->n
);
711 for (i
= 0; i
< fold
->n
; ++i
) {
712 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
719 isl_qpolynomial_fold_free(dup
);
723 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
724 __isl_take isl_qpolynomial_fold
*fold
)
732 return isl_qpolynomial_fold_dup(fold
);
735 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold
*fold
)
744 for (i
= 0; i
< fold
->n
; ++i
)
745 isl_qpolynomial_free(fold
->qp
[i
]);
746 isl_space_free(fold
->dim
);
750 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
758 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
759 __isl_take isl_qpolynomial_fold
*fold1
,
760 __isl_take isl_qpolynomial_fold
*fold2
)
763 struct isl_qpolynomial_fold
*res
= NULL
;
765 if (!fold1
|| !fold2
)
768 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
769 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
772 if (isl_qpolynomial_fold_is_empty(fold1
)) {
773 isl_qpolynomial_fold_free(fold1
);
777 if (isl_qpolynomial_fold_is_empty(fold2
)) {
778 isl_qpolynomial_fold_free(fold2
);
782 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
783 fold1
->n
+ fold2
->n
);
787 for (i
= 0; i
< fold1
->n
; ++i
) {
788 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
789 if (!res
->qp
[res
->n
])
794 for (i
= 0; i
< fold2
->n
; ++i
) {
795 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
796 if (!res
->qp
[res
->n
])
801 isl_qpolynomial_fold_free(fold1
);
802 isl_qpolynomial_fold_free(fold2
);
806 isl_qpolynomial_fold_free(res
);
807 isl_qpolynomial_fold_free(fold1
);
808 isl_qpolynomial_fold_free(fold2
);
812 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
813 __isl_take isl_pw_qpolynomial_fold
*pw1
,
814 __isl_take isl_pw_qpolynomial_fold
*pw2
)
817 struct isl_pw_qpolynomial_fold
*res
;
823 isl_assert(pw1
->dim
->ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
825 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
826 isl_pw_qpolynomial_fold_free(pw1
);
830 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
831 isl_pw_qpolynomial_fold_free(pw2
);
835 if (pw1
->type
!= pw2
->type
)
836 isl_die(pw1
->dim
->ctx
, isl_error_invalid
,
837 "fold types don't match", goto error
);
839 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
840 res
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1
->dim
),
843 for (i
= 0; i
< pw1
->n
; ++i
) {
844 set
= isl_set_copy(pw1
->p
[i
].set
);
845 for (j
= 0; j
< pw2
->n
; ++j
) {
846 struct isl_set
*common
;
847 isl_qpolynomial_fold
*sum
;
848 set
= isl_set_subtract(set
,
849 isl_set_copy(pw2
->p
[j
].set
));
850 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
851 isl_set_copy(pw2
->p
[j
].set
));
852 if (isl_set_plain_is_empty(common
)) {
853 isl_set_free(common
);
857 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
858 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
859 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
861 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
863 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
864 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
867 for (j
= 0; j
< pw2
->n
; ++j
) {
868 set
= isl_set_copy(pw2
->p
[j
].set
);
869 for (i
= 0; i
< pw1
->n
; ++i
)
870 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
871 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
872 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
875 isl_pw_qpolynomial_fold_free(pw1
);
876 isl_pw_qpolynomial_fold_free(pw2
);
880 isl_pw_qpolynomial_fold_free(pw1
);
881 isl_pw_qpolynomial_fold_free(pw2
);
885 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
886 __isl_take isl_union_pw_qpolynomial_fold
*u
,
887 __isl_take isl_pw_qpolynomial_fold
*part
)
890 struct isl_hash_table_entry
*entry
;
892 u
= isl_union_pw_qpolynomial_fold_cow(u
);
897 isl_assert(u
->dim
->ctx
, isl_space_match(part
->dim
, isl_dim_param
, u
->dim
,
898 isl_dim_param
), goto error
);
900 hash
= isl_space_get_hash(part
->dim
);
901 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
902 &has_dim
, part
->dim
, 1);
909 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
910 isl_pw_qpolynomial_fold_copy(part
));
913 isl_pw_qpolynomial_fold_free(part
);
918 isl_pw_qpolynomial_fold_free(part
);
919 isl_union_pw_qpolynomial_fold_free(u
);
923 static int fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
925 isl_union_pw_qpolynomial_fold
**u
;
926 u
= (isl_union_pw_qpolynomial_fold
**)user
;
928 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
933 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
934 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
935 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
937 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
942 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
943 &fold_part
, &u1
) < 0)
946 isl_union_pw_qpolynomial_fold_free(u2
);
950 isl_union_pw_qpolynomial_fold_free(u1
);
951 isl_union_pw_qpolynomial_fold_free(u2
);
955 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
956 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
959 isl_pw_qpolynomial_fold
*pwf
;
964 pwf
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp
->dim
),
967 for (i
= 0; i
< pwqp
->n
; ++i
)
968 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
969 isl_set_copy(pwqp
->p
[i
].set
),
970 isl_qpolynomial_fold_alloc(type
,
971 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
973 isl_pw_qpolynomial_free(pwqp
);
978 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_add(
979 __isl_take isl_pw_qpolynomial_fold
*pwf1
,
980 __isl_take isl_pw_qpolynomial_fold
*pwf2
)
982 return isl_pw_qpolynomial_fold_union_add_(pwf1
, pwf2
);
985 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
986 __isl_keep isl_qpolynomial_fold
*fold2
)
990 if (!fold1
|| !fold2
)
993 if (fold1
->n
!= fold2
->n
)
996 /* We probably want to sort the qps first... */
997 for (i
= 0; i
< fold1
->n
; ++i
) {
998 int eq
= isl_qpolynomial_plain_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
1006 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_eval(
1007 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
1009 isl_qpolynomial
*qp
;
1013 isl_assert(pnt
->dim
->ctx
, isl_space_is_equal(pnt
->dim
, fold
->dim
), goto error
);
1014 isl_assert(pnt
->dim
->ctx
,
1015 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
1019 qp
= isl_qpolynomial_zero_on_domain(isl_space_copy(fold
->dim
));
1022 qp
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
1023 isl_point_copy(pnt
));
1024 for (i
= 1; i
< fold
->n
; ++i
) {
1025 isl_qpolynomial
*qp_i
;
1026 qp_i
= isl_qpolynomial_eval(
1027 isl_qpolynomial_copy(fold
->qp
[i
]),
1028 isl_point_copy(pnt
));
1029 if (fold
->type
== isl_fold_max
)
1030 qp
= isl_qpolynomial_max_cst(qp
, qp_i
);
1032 qp
= isl_qpolynomial_min_cst(qp
, qp_i
);
1035 isl_qpolynomial_fold_free(fold
);
1036 isl_point_free(pnt
);
1040 isl_qpolynomial_fold_free(fold
);
1041 isl_point_free(pnt
);
1045 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
1050 for (i
= 0; i
< pwf
->n
; ++i
)
1051 n
+= pwf
->p
[i
].fold
->n
;
1056 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_opt_on_domain(
1057 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
1060 isl_qpolynomial
*opt
;
1066 isl_space
*dim
= isl_space_copy(fold
->dim
);
1068 isl_qpolynomial_fold_free(fold
);
1069 return isl_qpolynomial_zero_on_domain(dim
);
1072 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
1073 isl_set_copy(set
), max
);
1074 for (i
= 1; i
< fold
->n
; ++i
) {
1075 isl_qpolynomial
*opt_i
;
1076 opt_i
= isl_qpolynomial_opt_on_domain(
1077 isl_qpolynomial_copy(fold
->qp
[i
]),
1078 isl_set_copy(set
), max
);
1080 opt
= isl_qpolynomial_max_cst(opt
, opt_i
);
1082 opt
= isl_qpolynomial_min_cst(opt
, opt_i
);
1086 isl_qpolynomial_fold_free(fold
);
1091 isl_qpolynomial_fold_free(fold
);
1095 /* Check whether for each quasi-polynomial in "fold2" there is
1096 * a quasi-polynomial in "fold1" that dominates it on "set".
1098 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
1099 __isl_keep isl_qpolynomial_fold
*fold1
,
1100 __isl_keep isl_qpolynomial_fold
*fold2
)
1105 if (!set
|| !fold1
|| !fold2
)
1108 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
1110 for (i
= 0; i
< fold2
->n
; ++i
) {
1111 for (j
= 0; j
< fold1
->n
; ++j
) {
1115 d
= isl_qpolynomial_sub(
1116 isl_qpolynomial_copy(fold1
->qp
[j
]),
1117 isl_qpolynomial_copy(fold2
->qp
[i
]));
1118 sgn
= isl_qpolynomial_sign(set
, d
);
1119 isl_qpolynomial_free(d
);
1130 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1131 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1134 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold
*pwf1
,
1135 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1138 isl_set
*dom1
, *dom2
;
1149 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1150 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1151 is_subset
= isl_set_is_subset(dom2
, dom1
);
1155 if (is_subset
< 0 || !is_subset
)
1158 for (i
= 0; i
< pwf2
->n
; ++i
) {
1159 for (j
= 0; j
< pwf1
->n
; ++j
) {
1164 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1165 isl_set_copy(pwf2
->p
[i
].set
));
1166 is_empty
= isl_set_is_empty(common
);
1167 if (is_empty
< 0 || is_empty
) {
1168 isl_set_free(common
);
1173 covers
= qpolynomial_fold_covers_on_domain(common
,
1174 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1175 isl_set_free(common
);
1176 if (covers
< 0 || !covers
)
1184 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph_domain(
1185 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1190 if (!fold
|| !morph
)
1193 ctx
= fold
->dim
->ctx
;
1194 isl_assert(ctx
, isl_space_is_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1196 fold
= isl_qpolynomial_fold_cow(fold
);
1200 isl_space_free(fold
->dim
);
1201 fold
->dim
= isl_space_copy(morph
->ran
->dim
);
1205 for (i
= 0; i
< fold
->n
; ++i
) {
1206 fold
->qp
[i
] = isl_qpolynomial_morph_domain(fold
->qp
[i
],
1207 isl_morph_copy(morph
));
1212 isl_morph_free(morph
);
1216 isl_qpolynomial_fold_free(fold
);
1217 isl_morph_free(morph
);
1221 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1224 return isl_fold_list
;
1228 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1229 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1232 return isl_fold_list
;
1236 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1237 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*dim
)
1244 if (isl_space_is_equal(fold
->dim
, dim
)) {
1245 isl_space_free(dim
);
1249 fold
= isl_qpolynomial_fold_cow(fold
);
1253 isl_space_free(fold
->dim
);
1254 fold
->dim
= isl_space_copy(dim
);
1258 for (i
= 0; i
< fold
->n
; ++i
) {
1259 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1260 isl_space_copy(dim
));
1265 isl_space_free(dim
);
1269 isl_qpolynomial_fold_free(fold
);
1270 isl_space_free(dim
);
1274 int isl_qpolynomial_fold_foreach_qpolynomial(
1275 __isl_keep isl_qpolynomial_fold
*fold
,
1276 int (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1283 for (i
= 0; i
< fold
->n
; ++i
)
1284 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1290 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1291 __isl_take isl_qpolynomial_fold
*fold
,
1292 enum isl_dim_type dst_type
, unsigned dst_pos
,
1293 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1300 fold
= isl_qpolynomial_fold_cow(fold
);
1304 fold
->dim
= isl_space_move_dims(fold
->dim
, dst_type
, dst_pos
,
1305 src_type
, src_pos
, n
);
1309 for (i
= 0; i
< fold
->n
; ++i
) {
1310 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1311 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1318 isl_qpolynomial_fold_free(fold
);
1322 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1323 * in fold->qp[k] by subs[i].
1325 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1326 __isl_take isl_qpolynomial_fold
*fold
,
1327 enum isl_dim_type type
, unsigned first
, unsigned n
,
1328 __isl_keep isl_qpolynomial
**subs
)
1335 fold
= isl_qpolynomial_fold_cow(fold
);
1339 for (i
= 0; i
< fold
->n
; ++i
) {
1340 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1341 type
, first
, n
, subs
);
1348 isl_qpolynomial_fold_free(fold
);
1352 static int add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1355 isl_pw_qpolynomial_fold
*pwf
;
1356 isl_union_pw_qpolynomial_fold
**upwf
;
1358 struct isl_hash_table_entry
*entry
;
1360 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1362 ctx
= pwqp
->dim
->ctx
;
1363 hash
= isl_space_get_hash(pwqp
->dim
);
1364 entry
= isl_hash_table_find(ctx
, &(*upwf
)->table
,
1365 hash
, &has_dim
, pwqp
->dim
, 1);
1369 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1373 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1376 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
)) {
1377 isl_pw_qpolynomial_fold_free(entry
->data
);
1378 isl_hash_table_remove(ctx
, &(*upwf
)->table
, entry
);
1384 isl_pw_qpolynomial_free(pwqp
);
1388 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1389 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1390 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1392 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1393 isl_union_pw_qpolynomial_get_space(upwqp
));
1394 upwqp
= isl_union_pw_qpolynomial_align_params(upwqp
,
1395 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1397 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1398 if (!upwf
|| !upwqp
)
1401 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1405 isl_union_pw_qpolynomial_free(upwqp
);
1409 isl_union_pw_qpolynomial_fold_free(upwf
);
1410 isl_union_pw_qpolynomial_free(upwqp
);
1414 static int join_compatible(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1417 m
= isl_space_match(dim1
, isl_dim_param
, dim2
, isl_dim_param
);
1420 return isl_space_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_in
);
1423 /* Compute the intersection of the range of the map and the domain
1424 * of the piecewise quasipolynomial reduction and then compute a bound
1425 * on the associated quasipolynomial reduction over all elements
1426 * in this intersection.
1428 * We first introduce some unconstrained dimensions in the
1429 * piecewise quasipolynomial, intersect the resulting domain
1430 * with the wrapped map and the compute the sum.
1432 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1433 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1443 ctx
= isl_map_get_ctx(map
);
1447 map_dim
= isl_map_get_space(map
);
1448 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1449 ok
= join_compatible(map_dim
, pwf_dim
);
1450 isl_space_free(map_dim
);
1451 isl_space_free(pwf_dim
);
1453 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1456 n_in
= isl_map_dim(map
, isl_dim_in
);
1457 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_in
, 0, n_in
);
1459 dom
= isl_map_wrap(map
);
1460 pwf
= isl_pw_qpolynomial_fold_reset_domain_space(pwf
,
1461 isl_set_get_space(dom
));
1463 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1464 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1469 isl_pw_qpolynomial_fold_free(pwf
);
1473 __isl_give isl_pw_qpolynomial_fold
*isl_set_apply_pw_qpolynomial_fold(
1474 __isl_take isl_set
*set
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1477 return isl_map_apply_pw_qpolynomial_fold(set
, pwf
, tight
);
1480 struct isl_apply_fold_data
{
1481 isl_union_pw_qpolynomial_fold
*upwf
;
1482 isl_union_pw_qpolynomial_fold
*res
;
1487 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold
*pwf
,
1492 struct isl_apply_fold_data
*data
= user
;
1495 map_dim
= isl_map_get_space(data
->map
);
1496 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1497 ok
= join_compatible(map_dim
, pwf_dim
);
1498 isl_space_free(map_dim
);
1499 isl_space_free(pwf_dim
);
1502 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1503 pwf
, data
->tight
? &data
->tight
: NULL
);
1504 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1507 isl_pw_qpolynomial_fold_free(pwf
);
1512 static int map_apply(__isl_take isl_map
*map
, void *user
)
1514 struct isl_apply_fold_data
*data
= user
;
1518 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1519 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1525 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1526 __isl_take isl_union_map
*umap
,
1527 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1531 struct isl_apply_fold_data data
;
1533 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1534 isl_union_map_get_space(umap
));
1535 umap
= isl_union_map_align_params(umap
,
1536 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1539 data
.tight
= tight
? 1 : 0;
1540 dim
= isl_union_pw_qpolynomial_fold_get_space(upwf
);
1541 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1542 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1543 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1546 isl_union_map_free(umap
);
1547 isl_union_pw_qpolynomial_fold_free(upwf
);
1550 *tight
= data
.tight
;
1554 isl_union_map_free(umap
);
1555 isl_union_pw_qpolynomial_fold_free(upwf
);
1556 isl_union_pw_qpolynomial_fold_free(data
.res
);
1560 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_set_apply_union_pw_qpolynomial_fold(
1561 __isl_take isl_union_set
*uset
,
1562 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1564 return isl_union_map_apply_union_pw_qpolynomial_fold(uset
, upwf
, tight
);
1567 /* Reorder the dimension of "fold" according to the given reordering.
1569 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign_domain(
1570 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1574 fold
= isl_qpolynomial_fold_cow(fold
);
1578 for (i
= 0; i
< fold
->n
; ++i
) {
1579 fold
->qp
[i
] = isl_qpolynomial_realign_domain(fold
->qp
[i
],
1580 isl_reordering_copy(r
));
1585 fold
= isl_qpolynomial_fold_reset_domain_space(fold
,
1586 isl_space_copy(r
->dim
));
1588 isl_reordering_free(r
);
1592 isl_qpolynomial_fold_free(fold
);
1593 isl_reordering_free(r
);
1597 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_mul_isl_int(
1598 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1602 if (isl_int_is_one(v
))
1604 if (fold
&& isl_int_is_zero(v
)) {
1605 isl_qpolynomial_fold
*zero
;
1606 isl_space
*dim
= isl_space_copy(fold
->dim
);
1607 zero
= isl_qpolynomial_fold_empty(fold
->type
, dim
);
1608 isl_qpolynomial_fold_free(fold
);
1612 fold
= isl_qpolynomial_fold_cow(fold
);
1616 if (isl_int_is_neg(v
))
1617 fold
->type
= isl_fold_type_negate(fold
->type
);
1618 for (i
= 0; i
< fold
->n
; ++i
) {
1619 fold
->qp
[i
] = isl_qpolynomial_mul_isl_int(fold
->qp
[i
], v
);
1626 isl_qpolynomial_fold_free(fold
);
1630 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale(
1631 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1633 return isl_qpolynomial_fold_mul_isl_int(fold
, v
);
1636 /* Multiply "fold" by "v".
1638 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale_val(
1639 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_val
*v
)
1646 if (isl_val_is_one(v
)) {
1650 if (isl_val_is_zero(v
)) {
1651 isl_qpolynomial_fold
*zero
;
1652 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
1653 zero
= isl_qpolynomial_fold_empty(fold
->type
, space
);
1654 isl_qpolynomial_fold_free(fold
);
1658 if (!isl_val_is_rat(v
))
1659 isl_die(isl_qpolynomial_fold_get_ctx(fold
), isl_error_invalid
,
1660 "expecting rational factor", goto error
);
1662 fold
= isl_qpolynomial_fold_cow(fold
);
1666 if (isl_val_is_neg(v
))
1667 fold
->type
= isl_fold_type_negate(fold
->type
);
1668 for (i
= 0; i
< fold
->n
; ++i
) {
1669 fold
->qp
[i
] = isl_qpolynomial_scale_val(fold
->qp
[i
],
1679 isl_qpolynomial_fold_free(fold
);