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>
18 #include <isl_mat_private.h>
20 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
21 enum isl_fold type
, __isl_take isl_dim
*dim
, int n
)
23 isl_qpolynomial_fold
*fold
;
28 isl_assert(dim
->ctx
, n
>= 0, goto error
);
29 fold
= isl_calloc(dim
->ctx
, struct isl_qpolynomial_fold
,
30 sizeof(struct isl_qpolynomial_fold
) +
31 (n
- 1) * sizeof(struct isl_qpolynomial
*));
47 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_dim(
48 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
52 fold
= isl_qpolynomial_fold_cow(fold
);
56 for (i
= 0; i
< fold
->n
; ++i
) {
57 fold
->qp
[i
] = isl_qpolynomial_reset_dim(fold
->qp
[i
],
63 isl_dim_free(fold
->dim
);
68 isl_qpolynomial_fold_free(fold
);
73 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
74 enum isl_dim_type type
, unsigned first
, unsigned n
)
80 if (fold
->n
== 0 || n
== 0)
83 for (i
= 0; i
< fold
->n
; ++i
) {
84 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
86 if (involves
< 0 || involves
)
92 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_set_dim_name(
93 __isl_take isl_qpolynomial_fold
*fold
,
94 enum isl_dim_type type
, unsigned pos
, const char *s
)
98 fold
= isl_qpolynomial_fold_cow(fold
);
101 fold
->dim
= isl_dim_set_name(fold
->dim
, type
, pos
, s
);
105 for (i
= 0; i
< fold
->n
; ++i
) {
106 fold
->qp
[i
] = isl_qpolynomial_set_dim_name(fold
->qp
[i
],
114 isl_qpolynomial_fold_free(fold
);
118 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
119 __isl_take isl_qpolynomial_fold
*fold
,
120 enum isl_dim_type type
, unsigned first
, unsigned n
)
129 fold
= isl_qpolynomial_fold_cow(fold
);
132 fold
->dim
= isl_dim_drop(fold
->dim
, type
, first
, n
);
136 for (i
= 0; i
< fold
->n
; ++i
) {
137 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
145 isl_qpolynomial_fold_free(fold
);
149 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
150 __isl_take isl_qpolynomial_fold
*fold
,
151 enum isl_dim_type type
, unsigned first
, unsigned n
)
157 if (n
== 0 && !isl_dim_is_named_or_nested(fold
->dim
, type
))
160 fold
= isl_qpolynomial_fold_cow(fold
);
163 fold
->dim
= isl_dim_insert(fold
->dim
, type
, first
, n
);
167 for (i
= 0; i
< fold
->n
; ++i
) {
168 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
176 isl_qpolynomial_fold_free(fold
);
180 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
182 struct isl_upoly_cst
*cst
;
184 cst
= isl_upoly_as_cst(qp
->upoly
);
188 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
191 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
192 __isl_keep isl_qpolynomial
*qp
)
194 enum isl_lp_result res
;
199 aff
= isl_qpolynomial_extract_affine(qp
);
205 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
207 if (res
== isl_lp_error
)
209 if (res
== isl_lp_empty
||
210 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
215 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
217 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
226 /* Determine, if possible, the sign of the quasipolynomial "qp" on
229 * If qp is a constant, then the problem is trivial.
230 * If qp is linear, then we check if the minimum of the corresponding
231 * affine constraint is non-negative or if the maximum is non-positive.
233 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
234 * in "set". If so, we write qp(v,v') as
236 * q(v,v') * (v - l) + r(v')
238 * if q(v,v') and r(v') have the same known sign, then the original
239 * quasipolynomial has the same sign as well.
246 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
247 __isl_keep isl_qpolynomial
*qp
)
252 struct isl_upoly_rec
*rec
;
255 enum isl_lp_result res
;
258 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
262 return isl_qpolynomial_cst_sign(qp
);
264 is
= isl_qpolynomial_is_affine(qp
);
268 return isl_qpolynomial_aff_sign(set
, qp
);
270 if (qp
->div
->n_row
> 0)
273 rec
= isl_upoly_as_rec(qp
->upoly
);
277 d
= isl_dim_total(qp
->dim
);
278 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
282 isl_seq_clr(v
->el
+ 1, 1 + d
);
283 isl_int_set_si(v
->el
[0], 1);
284 isl_int_set_si(v
->el
[2 + qp
->upoly
->var
], 1);
288 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
289 if (res
== isl_lp_ok
) {
290 isl_qpolynomial
*min
;
291 isl_qpolynomial
*base
;
292 isl_qpolynomial
*r
, *q
;
295 min
= isl_qpolynomial_cst(isl_dim_copy(qp
->dim
), l
);
296 base
= isl_qpolynomial_pow(isl_dim_copy(qp
->dim
),
299 r
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
300 isl_upoly_copy(rec
->p
[rec
->n
- 1]));
301 q
= isl_qpolynomial_copy(r
);
303 for (i
= rec
->n
- 2; i
>= 0; --i
) {
304 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
305 t
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
306 isl_upoly_copy(rec
->p
[i
]));
307 r
= isl_qpolynomial_add(r
, t
);
310 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
311 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
314 if (isl_qpolynomial_is_zero(q
))
315 sgn
= isl_qpolynomial_sign(set
, r
);
316 else if (isl_qpolynomial_is_zero(r
))
317 sgn
= isl_qpolynomial_sign(set
, q
);
320 sgn_r
= isl_qpolynomial_sign(set
, r
);
321 sgn_q
= isl_qpolynomial_sign(set
, q
);
326 isl_qpolynomial_free(min
);
327 isl_qpolynomial_free(base
);
328 isl_qpolynomial_free(q
);
329 isl_qpolynomial_free(r
);
339 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
340 __isl_keep isl_set
*set
,
341 __isl_take isl_qpolynomial_fold
*fold1
,
342 __isl_take isl_qpolynomial_fold
*fold2
)
346 struct isl_qpolynomial_fold
*res
= NULL
;
349 if (!fold1
|| !fold2
)
352 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
353 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
356 better
= fold1
->type
== isl_fold_max
? -1 : 1;
358 if (isl_qpolynomial_fold_is_empty(fold1
)) {
359 isl_qpolynomial_fold_free(fold1
);
363 if (isl_qpolynomial_fold_is_empty(fold2
)) {
364 isl_qpolynomial_fold_free(fold2
);
368 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
369 fold1
->n
+ fold2
->n
);
373 for (i
= 0; i
< fold1
->n
; ++i
) {
374 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
375 if (!res
->qp
[res
->n
])
381 for (i
= 0; i
< fold2
->n
; ++i
) {
382 for (j
= n1
- 1; j
>= 0; --j
) {
385 d
= isl_qpolynomial_sub(
386 isl_qpolynomial_copy(res
->qp
[j
]),
387 isl_qpolynomial_copy(fold2
->qp
[i
]));
388 sgn
= isl_qpolynomial_sign(set
, d
);
389 isl_qpolynomial_free(d
);
394 isl_qpolynomial_free(res
->qp
[j
]);
396 res
->qp
[j
] = res
->qp
[n1
- 1];
398 if (n1
!= res
->n
- 1)
399 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
404 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
405 if (!res
->qp
[res
->n
])
410 isl_qpolynomial_fold_free(fold1
);
411 isl_qpolynomial_fold_free(fold2
);
415 isl_qpolynomial_fold_free(res
);
416 isl_qpolynomial_fold_free(fold1
);
417 isl_qpolynomial_fold_free(fold2
);
421 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
422 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
429 if (isl_qpolynomial_is_zero(qp
)) {
430 isl_qpolynomial_free(qp
);
434 fold
= isl_qpolynomial_fold_cow(fold
);
438 for (i
= 0; i
< fold
->n
; ++i
) {
439 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
440 isl_qpolynomial_copy(qp
));
445 isl_qpolynomial_free(qp
);
448 isl_qpolynomial_fold_free(fold
);
449 isl_qpolynomial_free(qp
);
453 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
454 __isl_keep isl_set
*dom
,
455 __isl_take isl_qpolynomial_fold
*fold1
,
456 __isl_take isl_qpolynomial_fold
*fold2
)
459 isl_qpolynomial_fold
*res
= NULL
;
461 if (!fold1
|| !fold2
)
464 if (isl_qpolynomial_fold_is_empty(fold1
)) {
465 isl_qpolynomial_fold_free(fold1
);
469 if (isl_qpolynomial_fold_is_empty(fold2
)) {
470 isl_qpolynomial_fold_free(fold2
);
474 if (fold1
->n
== 1 && fold2
->n
!= 1)
475 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
478 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
479 isl_qpolynomial_copy(fold2
->qp
[0]));
480 isl_qpolynomial_fold_free(fold2
);
484 res
= isl_qpolynomial_fold_add_qpolynomial(
485 isl_qpolynomial_fold_copy(fold1
),
486 isl_qpolynomial_copy(fold2
->qp
[0]));
488 for (i
= 1; i
< fold2
->n
; ++i
) {
489 isl_qpolynomial_fold
*res_i
;
490 res_i
= isl_qpolynomial_fold_add_qpolynomial(
491 isl_qpolynomial_fold_copy(fold1
),
492 isl_qpolynomial_copy(fold2
->qp
[i
]));
493 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
496 isl_qpolynomial_fold_free(fold1
);
497 isl_qpolynomial_fold_free(fold2
);
500 isl_qpolynomial_fold_free(res
);
501 isl_qpolynomial_fold_free(fold1
);
502 isl_qpolynomial_fold_free(fold2
);
506 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
507 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
514 fold
= isl_qpolynomial_fold_cow(fold
);
518 for (i
= 0; i
< fold
->n
; ++i
) {
519 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
520 isl_basic_set_copy(eq
));
525 isl_basic_set_free(eq
);
528 isl_basic_set_free(eq
);
529 isl_qpolynomial_fold_free(fold
);
533 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist(
534 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
538 if (!fold
|| !context
)
541 fold
= isl_qpolynomial_fold_cow(fold
);
545 for (i
= 0; i
< fold
->n
; ++i
) {
546 fold
->qp
[i
] = isl_qpolynomial_gist(fold
->qp
[i
],
547 isl_set_copy(context
));
552 isl_set_free(context
);
555 isl_set_free(context
);
556 isl_qpolynomial_fold_free(fold
);
563 #define PW isl_pw_qpolynomial_fold
565 #define EL isl_qpolynomial_fold
567 #define IS_ZERO is_empty
571 #include <isl_pw_templ.c>
574 #define UNION isl_union_pw_qpolynomial_fold
576 #define PART isl_pw_qpolynomial_fold
578 #define PARTS pw_qpolynomial_fold
580 #include <isl_union_templ.c>
582 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
583 __isl_take isl_dim
*dim
)
585 return qpolynomial_fold_alloc(type
, dim
, 0);
588 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
589 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
591 isl_qpolynomial_fold
*fold
;
596 fold
= qpolynomial_fold_alloc(type
, isl_dim_copy(qp
->dim
), 1);
605 isl_qpolynomial_fold_free(fold
);
606 isl_qpolynomial_free(qp
);
610 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
611 __isl_keep isl_qpolynomial_fold
*fold
)
620 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
621 __isl_keep isl_qpolynomial_fold
*fold
)
624 isl_qpolynomial_fold
*dup
;
628 dup
= qpolynomial_fold_alloc(fold
->type
,
629 isl_dim_copy(fold
->dim
), fold
->n
);
634 for (i
= 0; i
< fold
->n
; ++i
) {
635 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
642 isl_qpolynomial_fold_free(dup
);
646 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
647 __isl_take isl_qpolynomial_fold
*fold
)
655 return isl_qpolynomial_fold_dup(fold
);
658 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold
*fold
)
667 for (i
= 0; i
< fold
->n
; ++i
)
668 isl_qpolynomial_free(fold
->qp
[i
]);
669 isl_dim_free(fold
->dim
);
673 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
681 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
682 __isl_take isl_qpolynomial_fold
*fold1
,
683 __isl_take isl_qpolynomial_fold
*fold2
)
686 struct isl_qpolynomial_fold
*res
= NULL
;
688 if (!fold1
|| !fold2
)
691 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
692 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
695 if (isl_qpolynomial_fold_is_empty(fold1
)) {
696 isl_qpolynomial_fold_free(fold1
);
700 if (isl_qpolynomial_fold_is_empty(fold2
)) {
701 isl_qpolynomial_fold_free(fold2
);
705 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
706 fold1
->n
+ fold2
->n
);
710 for (i
= 0; i
< fold1
->n
; ++i
) {
711 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
712 if (!res
->qp
[res
->n
])
717 for (i
= 0; i
< fold2
->n
; ++i
) {
718 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
719 if (!res
->qp
[res
->n
])
724 isl_qpolynomial_fold_free(fold1
);
725 isl_qpolynomial_fold_free(fold2
);
729 isl_qpolynomial_fold_free(res
);
730 isl_qpolynomial_fold_free(fold1
);
731 isl_qpolynomial_fold_free(fold2
);
735 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
736 __isl_take isl_pw_qpolynomial_fold
*pw1
,
737 __isl_take isl_pw_qpolynomial_fold
*pw2
)
740 struct isl_pw_qpolynomial_fold
*res
;
746 isl_assert(pw1
->dim
->ctx
, isl_dim_equal(pw1
->dim
, pw2
->dim
), goto error
);
748 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
749 isl_pw_qpolynomial_fold_free(pw1
);
753 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
754 isl_pw_qpolynomial_fold_free(pw2
);
758 if (pw1
->type
!= pw2
->type
)
759 isl_die(set
->ctx
, isl_error_invalid
, "fold types don't match",
762 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
763 res
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1
->dim
),
766 for (i
= 0; i
< pw1
->n
; ++i
) {
767 set
= isl_set_copy(pw1
->p
[i
].set
);
768 for (j
= 0; j
< pw2
->n
; ++j
) {
769 struct isl_set
*common
;
770 isl_qpolynomial_fold
*sum
;
771 set
= isl_set_subtract(set
,
772 isl_set_copy(pw2
->p
[j
].set
));
773 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
774 isl_set_copy(pw2
->p
[j
].set
));
775 if (isl_set_fast_is_empty(common
)) {
776 isl_set_free(common
);
780 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
781 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
782 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
784 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
786 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
787 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
790 for (j
= 0; j
< pw2
->n
; ++j
) {
791 set
= isl_set_copy(pw2
->p
[j
].set
);
792 for (i
= 0; i
< pw1
->n
; ++i
)
793 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
794 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
795 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
798 isl_pw_qpolynomial_fold_free(pw1
);
799 isl_pw_qpolynomial_fold_free(pw2
);
803 isl_pw_qpolynomial_fold_free(pw1
);
804 isl_pw_qpolynomial_fold_free(pw2
);
808 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
809 __isl_take isl_union_pw_qpolynomial_fold
*u
,
810 __isl_take isl_pw_qpolynomial_fold
*part
)
813 struct isl_hash_table_entry
*entry
;
815 u
= isl_union_pw_qpolynomial_fold_cow(u
);
820 isl_assert(u
->dim
->ctx
, isl_dim_match(part
->dim
, isl_dim_param
, u
->dim
,
821 isl_dim_param
), goto error
);
823 hash
= isl_dim_get_hash(part
->dim
);
824 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
825 &has_dim
, part
->dim
, 1);
832 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
833 isl_pw_qpolynomial_fold_copy(part
));
836 isl_pw_qpolynomial_fold_free(part
);
841 isl_pw_qpolynomial_fold_free(part
);
842 isl_union_pw_qpolynomial_fold_free(u
);
846 static int fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
848 isl_union_pw_qpolynomial_fold
**u
;
849 u
= (isl_union_pw_qpolynomial_fold
**)user
;
851 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
856 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
857 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
858 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
860 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
865 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
866 &fold_part
, &u1
) < 0)
869 isl_union_pw_qpolynomial_fold_free(u2
);
873 isl_union_pw_qpolynomial_fold_free(u1
);
874 isl_union_pw_qpolynomial_fold_free(u2
);
878 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
879 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
882 isl_pw_qpolynomial_fold
*pwf
;
887 pwf
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp
->dim
), type
,
890 for (i
= 0; i
< pwqp
->n
; ++i
)
891 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
892 isl_set_copy(pwqp
->p
[i
].set
),
893 isl_qpolynomial_fold_alloc(type
,
894 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
896 isl_pw_qpolynomial_free(pwqp
);
901 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
902 __isl_keep isl_qpolynomial_fold
*fold2
)
906 if (!fold1
|| !fold2
)
909 if (fold1
->n
!= fold2
->n
)
912 /* We probably want to sort the qps first... */
913 for (i
= 0; i
< fold1
->n
; ++i
) {
914 int eq
= isl_qpolynomial_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
922 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_eval(
923 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
929 isl_assert(pnt
->dim
->ctx
, isl_dim_equal(pnt
->dim
, fold
->dim
), goto error
);
930 isl_assert(pnt
->dim
->ctx
,
931 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
935 qp
= isl_qpolynomial_zero(isl_dim_copy(fold
->dim
));
938 qp
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
939 isl_point_copy(pnt
));
940 for (i
= 1; i
< fold
->n
; ++i
) {
941 isl_qpolynomial
*qp_i
;
942 qp_i
= isl_qpolynomial_eval(
943 isl_qpolynomial_copy(fold
->qp
[i
]),
944 isl_point_copy(pnt
));
945 if (fold
->type
== isl_fold_max
)
946 qp
= isl_qpolynomial_max_cst(qp
, qp_i
);
948 qp
= isl_qpolynomial_min_cst(qp
, qp_i
);
951 isl_qpolynomial_fold_free(fold
);
956 isl_qpolynomial_fold_free(fold
);
961 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
966 for (i
= 0; i
< pwf
->n
; ++i
)
967 n
+= pwf
->p
[i
].fold
->n
;
972 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_opt_on_domain(
973 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
976 isl_qpolynomial
*opt
;
982 isl_dim
*dim
= isl_dim_copy(fold
->dim
);
984 isl_qpolynomial_fold_free(fold
);
985 return isl_qpolynomial_zero(dim
);
988 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
989 isl_set_copy(set
), max
);
990 for (i
= 1; i
< fold
->n
; ++i
) {
991 isl_qpolynomial
*opt_i
;
992 opt_i
= isl_qpolynomial_opt_on_domain(
993 isl_qpolynomial_copy(fold
->qp
[i
]),
994 isl_set_copy(set
), max
);
996 opt
= isl_qpolynomial_max_cst(opt
, opt_i
);
998 opt
= isl_qpolynomial_min_cst(opt
, opt_i
);
1002 isl_qpolynomial_fold_free(fold
);
1007 isl_qpolynomial_fold_free(fold
);
1011 /* Check whether for each quasi-polynomial in "fold2" there is
1012 * a quasi-polynomial in "fold1" that dominates it on "set".
1014 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
1015 __isl_keep isl_qpolynomial_fold
*fold1
,
1016 __isl_keep isl_qpolynomial_fold
*fold2
)
1021 if (!set
|| !fold1
|| !fold2
)
1024 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
1026 for (i
= 0; i
< fold2
->n
; ++i
) {
1027 for (j
= 0; j
< fold1
->n
; ++j
) {
1031 d
= isl_qpolynomial_sub(
1032 isl_qpolynomial_copy(fold1
->qp
[j
]),
1033 isl_qpolynomial_copy(fold2
->qp
[i
]));
1034 sgn
= isl_qpolynomial_sign(set
, d
);
1035 isl_qpolynomial_free(d
);
1046 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1047 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1050 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold
*pwf1
,
1051 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1054 isl_set
*dom1
, *dom2
;
1065 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1066 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1067 is_subset
= isl_set_is_subset(dom2
, dom1
);
1071 if (is_subset
< 0 || !is_subset
)
1074 for (i
= 0; i
< pwf2
->n
; ++i
) {
1075 for (j
= 0; j
< pwf1
->n
; ++j
) {
1080 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1081 isl_set_copy(pwf2
->p
[i
].set
));
1082 is_empty
= isl_set_is_empty(common
);
1083 if (is_empty
< 0 || is_empty
) {
1084 isl_set_free(common
);
1089 covers
= qpolynomial_fold_covers_on_domain(common
,
1090 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1091 isl_set_free(common
);
1092 if (covers
< 0 || !covers
)
1100 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph(
1101 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1106 if (!fold
|| !morph
)
1109 ctx
= fold
->dim
->ctx
;
1110 isl_assert(ctx
, isl_dim_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1112 fold
= isl_qpolynomial_fold_cow(fold
);
1116 isl_dim_free(fold
->dim
);
1117 fold
->dim
= isl_dim_copy(morph
->ran
->dim
);
1121 for (i
= 0; i
< fold
->n
; ++i
) {
1122 fold
->qp
[i
] = isl_qpolynomial_morph(fold
->qp
[i
],
1123 isl_morph_copy(morph
));
1128 isl_morph_free(morph
);
1132 isl_qpolynomial_fold_free(fold
);
1133 isl_morph_free(morph
);
1137 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1140 return isl_fold_list
;
1144 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1145 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1148 return isl_fold_list
;
1152 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1153 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
1161 if (isl_dim_equal(fold
->dim
, dim
)) {
1166 fold
= isl_qpolynomial_fold_cow(fold
);
1170 isl_dim_free(fold
->dim
);
1171 fold
->dim
= isl_dim_copy(dim
);
1175 for (i
= 0; i
< fold
->n
; ++i
) {
1176 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1186 isl_qpolynomial_fold_free(fold
);
1191 int isl_qpolynomial_fold_foreach_qpolynomial(
1192 __isl_keep isl_qpolynomial_fold
*fold
,
1193 int (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1200 for (i
= 0; i
< fold
->n
; ++i
)
1201 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1207 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1208 __isl_take isl_qpolynomial_fold
*fold
,
1209 enum isl_dim_type dst_type
, unsigned dst_pos
,
1210 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1217 fold
= isl_qpolynomial_fold_cow(fold
);
1221 fold
->dim
= isl_dim_move(fold
->dim
, dst_type
, dst_pos
,
1222 src_type
, src_pos
, n
);
1226 for (i
= 0; i
< fold
->n
; ++i
) {
1227 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1228 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1235 isl_qpolynomial_fold_free(fold
);
1239 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1240 * in fold->qp[k] by subs[i].
1242 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1243 __isl_take isl_qpolynomial_fold
*fold
,
1244 enum isl_dim_type type
, unsigned first
, unsigned n
,
1245 __isl_keep isl_qpolynomial
**subs
)
1252 fold
= isl_qpolynomial_fold_cow(fold
);
1256 for (i
= 0; i
< fold
->n
; ++i
) {
1257 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1258 type
, first
, n
, subs
);
1265 isl_qpolynomial_fold_free(fold
);
1269 static int add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1272 isl_pw_qpolynomial_fold
*pwf
;
1273 isl_union_pw_qpolynomial_fold
**upwf
;
1275 struct isl_hash_table_entry
*entry
;
1277 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1279 ctx
= pwqp
->dim
->ctx
;
1280 hash
= isl_dim_get_hash(pwqp
->dim
);
1281 entry
= isl_hash_table_find(ctx
, &(*upwf
)->table
,
1282 hash
, &has_dim
, pwqp
->dim
, 1);
1286 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1290 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1293 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
)) {
1294 isl_pw_qpolynomial_fold_free(entry
->data
);
1295 isl_hash_table_remove(ctx
, &(*upwf
)->table
, entry
);
1301 isl_pw_qpolynomial_free(pwqp
);
1305 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1306 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1307 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1309 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1310 isl_union_pw_qpolynomial_get_dim(upwqp
));
1311 upwqp
= isl_union_pw_qpolynomial_align_params(upwqp
,
1312 isl_union_pw_qpolynomial_fold_get_dim(upwf
));
1314 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1315 if (!upwf
|| !upwqp
)
1318 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1322 isl_union_pw_qpolynomial_free(upwqp
);
1326 isl_union_pw_qpolynomial_fold_free(upwf
);
1327 isl_union_pw_qpolynomial_free(upwqp
);
1331 static int compatible_range(__isl_keep isl_dim
*dim1
, __isl_keep isl_dim
*dim2
)
1334 m
= isl_dim_match(dim1
, isl_dim_param
, dim2
, isl_dim_param
);
1337 return isl_dim_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_set
);
1340 /* Compute the intersection of the range of the map and the domain
1341 * of the piecewise quasipolynomial reduction and then compute a bound
1342 * on the associated quasipolynomial reduction over all elements
1343 * in this intersection.
1345 * We first introduce some unconstrained dimensions in the
1346 * piecewise quasipolynomial, intersect the resulting domain
1347 * with the wrapped map and the compute the sum.
1349 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1350 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1360 ctx
= isl_map_get_ctx(map
);
1364 map_dim
= isl_map_get_dim(map
);
1365 pwf_dim
= isl_pw_qpolynomial_fold_get_dim(pwf
);
1366 ok
= compatible_range(map_dim
, pwf_dim
);
1367 isl_dim_free(map_dim
);
1368 isl_dim_free(pwf_dim
);
1370 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1373 n_in
= isl_map_dim(map
, isl_dim_in
);
1374 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_set
, 0, n_in
);
1376 dom
= isl_map_wrap(map
);
1377 pwf
= isl_pw_qpolynomial_fold_reset_dim(pwf
, isl_set_get_dim(dom
));
1379 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1380 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1385 isl_pw_qpolynomial_fold_free(pwf
);
1389 struct isl_apply_fold_data
{
1390 isl_union_pw_qpolynomial_fold
*upwf
;
1391 isl_union_pw_qpolynomial_fold
*res
;
1396 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold
*pwf
,
1401 struct isl_apply_fold_data
*data
= user
;
1404 map_dim
= isl_map_get_dim(data
->map
);
1405 pwf_dim
= isl_pw_qpolynomial_fold_get_dim(pwf
);
1406 ok
= compatible_range(map_dim
, pwf_dim
);
1407 isl_dim_free(map_dim
);
1408 isl_dim_free(pwf_dim
);
1411 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1412 pwf
, data
->tight
? &data
->tight
: NULL
);
1413 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1416 isl_pw_qpolynomial_fold_free(pwf
);
1421 static int map_apply(__isl_take isl_map
*map
, void *user
)
1423 struct isl_apply_fold_data
*data
= user
;
1427 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1428 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1434 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1435 __isl_take isl_union_map
*umap
,
1436 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1440 struct isl_apply_fold_data data
;
1442 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1443 isl_union_map_get_dim(umap
));
1444 umap
= isl_union_map_align_params(umap
,
1445 isl_union_pw_qpolynomial_fold_get_dim(upwf
));
1448 data
.tight
= tight
? 1 : 0;
1449 dim
= isl_union_pw_qpolynomial_fold_get_dim(upwf
);
1450 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1451 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1452 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1455 isl_union_map_free(umap
);
1456 isl_union_pw_qpolynomial_fold_free(upwf
);
1459 *tight
= data
.tight
;
1463 isl_union_map_free(umap
);
1464 isl_union_pw_qpolynomial_fold_free(upwf
);
1465 isl_union_pw_qpolynomial_fold_free(data
.res
);
1469 /* Reorder the dimension of "fold" according to the given reordering.
1471 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign(
1472 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1476 fold
= isl_qpolynomial_fold_cow(fold
);
1480 for (i
= 0; i
< fold
->n
; ++i
) {
1481 fold
->qp
[i
] = isl_qpolynomial_realign(fold
->qp
[i
],
1482 isl_reordering_copy(r
));
1487 fold
= isl_qpolynomial_fold_reset_dim(fold
, isl_dim_copy(r
->dim
));
1489 isl_reordering_free(r
);
1493 isl_qpolynomial_fold_free(fold
);
1494 isl_reordering_free(r
);