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_map_private.h>
12 #include <isl_union_map_private.h>
13 #include <isl_polynomial_private.h>
14 #include <isl_point_private.h>
15 #include <isl_dim_private.h>
18 #include <isl_mat_private.h>
19 #include <isl_config.h>
21 enum isl_fold
isl_fold_type_negate(enum isl_fold type
)
32 isl_die(NULL
, isl_error_internal
, "unhandled isl_fold type", abort());
35 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
36 enum isl_fold type
, __isl_take isl_dim
*dim
, int n
)
38 isl_qpolynomial_fold
*fold
;
43 isl_assert(dim
->ctx
, n
>= 0, goto error
);
44 fold
= isl_calloc(dim
->ctx
, struct isl_qpolynomial_fold
,
45 sizeof(struct isl_qpolynomial_fold
) +
46 (n
- 1) * sizeof(struct isl_qpolynomial
*));
62 isl_ctx
*isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold
*fold
)
64 return fold
? fold
->dim
->ctx
: NULL
;
67 __isl_give isl_dim
*isl_qpolynomial_fold_get_dim(
68 __isl_keep isl_qpolynomial_fold
*fold
)
70 return fold
? isl_dim_copy(fold
->dim
) : NULL
;
73 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_dim(
74 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
78 fold
= isl_qpolynomial_fold_cow(fold
);
82 for (i
= 0; i
< fold
->n
; ++i
) {
83 fold
->qp
[i
] = isl_qpolynomial_reset_dim(fold
->qp
[i
],
89 isl_dim_free(fold
->dim
);
94 isl_qpolynomial_fold_free(fold
);
99 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
100 enum isl_dim_type type
, unsigned first
, unsigned n
)
106 if (fold
->n
== 0 || n
== 0)
109 for (i
= 0; i
< fold
->n
; ++i
) {
110 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
112 if (involves
< 0 || involves
)
118 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_set_dim_name(
119 __isl_take isl_qpolynomial_fold
*fold
,
120 enum isl_dim_type type
, unsigned pos
, const char *s
)
124 fold
= isl_qpolynomial_fold_cow(fold
);
127 fold
->dim
= isl_dim_set_name(fold
->dim
, type
, pos
, s
);
131 for (i
= 0; i
< fold
->n
; ++i
) {
132 fold
->qp
[i
] = isl_qpolynomial_set_dim_name(fold
->qp
[i
],
140 isl_qpolynomial_fold_free(fold
);
144 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
145 __isl_take isl_qpolynomial_fold
*fold
,
146 enum isl_dim_type type
, unsigned first
, unsigned n
)
155 fold
= isl_qpolynomial_fold_cow(fold
);
158 fold
->dim
= isl_dim_drop(fold
->dim
, type
, first
, n
);
162 for (i
= 0; i
< fold
->n
; ++i
) {
163 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
171 isl_qpolynomial_fold_free(fold
);
175 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
176 __isl_take isl_qpolynomial_fold
*fold
,
177 enum isl_dim_type type
, unsigned first
, unsigned n
)
183 if (n
== 0 && !isl_dim_is_named_or_nested(fold
->dim
, type
))
186 fold
= isl_qpolynomial_fold_cow(fold
);
189 fold
->dim
= isl_dim_insert(fold
->dim
, type
, first
, n
);
193 for (i
= 0; i
< fold
->n
; ++i
) {
194 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
202 isl_qpolynomial_fold_free(fold
);
206 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
208 struct isl_upoly_cst
*cst
;
210 cst
= isl_upoly_as_cst(qp
->upoly
);
214 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
217 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
218 __isl_keep isl_qpolynomial
*qp
)
220 enum isl_lp_result res
;
225 aff
= isl_qpolynomial_extract_affine(qp
);
231 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
233 if (res
== isl_lp_error
)
235 if (res
== isl_lp_empty
||
236 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
241 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
243 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
252 /* Determine, if possible, the sign of the quasipolynomial "qp" on
255 * If qp is a constant, then the problem is trivial.
256 * If qp is linear, then we check if the minimum of the corresponding
257 * affine constraint is non-negative or if the maximum is non-positive.
259 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
260 * in "set". If so, we write qp(v,v') as
262 * q(v,v') * (v - l) + r(v')
264 * if q(v,v') and r(v') have the same known sign, then the original
265 * quasipolynomial has the same sign as well.
272 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
273 __isl_keep isl_qpolynomial
*qp
)
278 struct isl_upoly_rec
*rec
;
281 enum isl_lp_result res
;
284 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
288 return isl_qpolynomial_cst_sign(qp
);
290 is
= isl_qpolynomial_is_affine(qp
);
294 return isl_qpolynomial_aff_sign(set
, qp
);
296 if (qp
->div
->n_row
> 0)
299 rec
= isl_upoly_as_rec(qp
->upoly
);
303 d
= isl_dim_total(qp
->dim
);
304 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
308 isl_seq_clr(v
->el
+ 1, 1 + d
);
309 isl_int_set_si(v
->el
[0], 1);
310 isl_int_set_si(v
->el
[2 + qp
->upoly
->var
], 1);
314 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
315 if (res
== isl_lp_ok
) {
316 isl_qpolynomial
*min
;
317 isl_qpolynomial
*base
;
318 isl_qpolynomial
*r
, *q
;
321 min
= isl_qpolynomial_cst(isl_dim_copy(qp
->dim
), l
);
322 base
= isl_qpolynomial_var_pow(isl_dim_copy(qp
->dim
),
325 r
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
326 isl_upoly_copy(rec
->p
[rec
->n
- 1]));
327 q
= isl_qpolynomial_copy(r
);
329 for (i
= rec
->n
- 2; i
>= 0; --i
) {
330 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
331 t
= isl_qpolynomial_alloc(isl_dim_copy(qp
->dim
), 0,
332 isl_upoly_copy(rec
->p
[i
]));
333 r
= isl_qpolynomial_add(r
, t
);
336 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
337 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
340 if (isl_qpolynomial_is_zero(q
))
341 sgn
= isl_qpolynomial_sign(set
, r
);
342 else if (isl_qpolynomial_is_zero(r
))
343 sgn
= isl_qpolynomial_sign(set
, q
);
346 sgn_r
= isl_qpolynomial_sign(set
, r
);
347 sgn_q
= isl_qpolynomial_sign(set
, q
);
352 isl_qpolynomial_free(min
);
353 isl_qpolynomial_free(base
);
354 isl_qpolynomial_free(q
);
355 isl_qpolynomial_free(r
);
365 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
366 __isl_keep isl_set
*set
,
367 __isl_take isl_qpolynomial_fold
*fold1
,
368 __isl_take isl_qpolynomial_fold
*fold2
)
372 struct isl_qpolynomial_fold
*res
= NULL
;
375 if (!fold1
|| !fold2
)
378 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
379 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
382 better
= fold1
->type
== isl_fold_max
? -1 : 1;
384 if (isl_qpolynomial_fold_is_empty(fold1
)) {
385 isl_qpolynomial_fold_free(fold1
);
389 if (isl_qpolynomial_fold_is_empty(fold2
)) {
390 isl_qpolynomial_fold_free(fold2
);
394 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
395 fold1
->n
+ fold2
->n
);
399 for (i
= 0; i
< fold1
->n
; ++i
) {
400 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
401 if (!res
->qp
[res
->n
])
407 for (i
= 0; i
< fold2
->n
; ++i
) {
408 for (j
= n1
- 1; j
>= 0; --j
) {
411 d
= isl_qpolynomial_sub(
412 isl_qpolynomial_copy(res
->qp
[j
]),
413 isl_qpolynomial_copy(fold2
->qp
[i
]));
414 sgn
= isl_qpolynomial_sign(set
, d
);
415 isl_qpolynomial_free(d
);
420 isl_qpolynomial_free(res
->qp
[j
]);
422 res
->qp
[j
] = res
->qp
[n1
- 1];
424 if (n1
!= res
->n
- 1)
425 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
430 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
431 if (!res
->qp
[res
->n
])
436 isl_qpolynomial_fold_free(fold1
);
437 isl_qpolynomial_fold_free(fold2
);
441 isl_qpolynomial_fold_free(res
);
442 isl_qpolynomial_fold_free(fold1
);
443 isl_qpolynomial_fold_free(fold2
);
447 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
448 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
455 if (isl_qpolynomial_is_zero(qp
)) {
456 isl_qpolynomial_free(qp
);
460 fold
= isl_qpolynomial_fold_cow(fold
);
464 for (i
= 0; i
< fold
->n
; ++i
) {
465 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
466 isl_qpolynomial_copy(qp
));
471 isl_qpolynomial_free(qp
);
474 isl_qpolynomial_fold_free(fold
);
475 isl_qpolynomial_free(qp
);
479 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
480 __isl_keep isl_set
*dom
,
481 __isl_take isl_qpolynomial_fold
*fold1
,
482 __isl_take isl_qpolynomial_fold
*fold2
)
485 isl_qpolynomial_fold
*res
= NULL
;
487 if (!fold1
|| !fold2
)
490 if (isl_qpolynomial_fold_is_empty(fold1
)) {
491 isl_qpolynomial_fold_free(fold1
);
495 if (isl_qpolynomial_fold_is_empty(fold2
)) {
496 isl_qpolynomial_fold_free(fold2
);
500 if (fold1
->n
== 1 && fold2
->n
!= 1)
501 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
504 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
505 isl_qpolynomial_copy(fold2
->qp
[0]));
506 isl_qpolynomial_fold_free(fold2
);
510 res
= isl_qpolynomial_fold_add_qpolynomial(
511 isl_qpolynomial_fold_copy(fold1
),
512 isl_qpolynomial_copy(fold2
->qp
[0]));
514 for (i
= 1; i
< fold2
->n
; ++i
) {
515 isl_qpolynomial_fold
*res_i
;
516 res_i
= isl_qpolynomial_fold_add_qpolynomial(
517 isl_qpolynomial_fold_copy(fold1
),
518 isl_qpolynomial_copy(fold2
->qp
[i
]));
519 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
522 isl_qpolynomial_fold_free(fold1
);
523 isl_qpolynomial_fold_free(fold2
);
526 isl_qpolynomial_fold_free(res
);
527 isl_qpolynomial_fold_free(fold1
);
528 isl_qpolynomial_fold_free(fold2
);
532 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
533 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
540 fold
= isl_qpolynomial_fold_cow(fold
);
544 for (i
= 0; i
< fold
->n
; ++i
) {
545 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
546 isl_basic_set_copy(eq
));
551 isl_basic_set_free(eq
);
554 isl_basic_set_free(eq
);
555 isl_qpolynomial_fold_free(fold
);
559 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist(
560 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
564 if (!fold
|| !context
)
567 fold
= isl_qpolynomial_fold_cow(fold
);
571 for (i
= 0; i
< fold
->n
; ++i
) {
572 fold
->qp
[i
] = isl_qpolynomial_gist(fold
->qp
[i
],
573 isl_set_copy(context
));
578 isl_set_free(context
);
581 isl_set_free(context
);
582 isl_qpolynomial_fold_free(fold
);
589 #define PW isl_pw_qpolynomial_fold
591 #define EL isl_qpolynomial_fold
593 #define IS_ZERO is_empty
597 #include <isl_pw_templ.c>
600 #define UNION isl_union_pw_qpolynomial_fold
602 #define PART isl_pw_qpolynomial_fold
604 #define PARTS pw_qpolynomial_fold
606 #include <isl_union_templ.c>
608 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
609 __isl_take isl_dim
*dim
)
611 return qpolynomial_fold_alloc(type
, dim
, 0);
614 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
615 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
617 isl_qpolynomial_fold
*fold
;
622 fold
= qpolynomial_fold_alloc(type
, isl_dim_copy(qp
->dim
), 1);
631 isl_qpolynomial_fold_free(fold
);
632 isl_qpolynomial_free(qp
);
636 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
637 __isl_keep isl_qpolynomial_fold
*fold
)
646 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
647 __isl_keep isl_qpolynomial_fold
*fold
)
650 isl_qpolynomial_fold
*dup
;
654 dup
= qpolynomial_fold_alloc(fold
->type
,
655 isl_dim_copy(fold
->dim
), fold
->n
);
660 for (i
= 0; i
< fold
->n
; ++i
) {
661 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
668 isl_qpolynomial_fold_free(dup
);
672 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
673 __isl_take isl_qpolynomial_fold
*fold
)
681 return isl_qpolynomial_fold_dup(fold
);
684 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold
*fold
)
693 for (i
= 0; i
< fold
->n
; ++i
)
694 isl_qpolynomial_free(fold
->qp
[i
]);
695 isl_dim_free(fold
->dim
);
699 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
707 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
708 __isl_take isl_qpolynomial_fold
*fold1
,
709 __isl_take isl_qpolynomial_fold
*fold2
)
712 struct isl_qpolynomial_fold
*res
= NULL
;
714 if (!fold1
|| !fold2
)
717 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
718 isl_assert(fold1
->dim
->ctx
, isl_dim_equal(fold1
->dim
, fold2
->dim
),
721 if (isl_qpolynomial_fold_is_empty(fold1
)) {
722 isl_qpolynomial_fold_free(fold1
);
726 if (isl_qpolynomial_fold_is_empty(fold2
)) {
727 isl_qpolynomial_fold_free(fold2
);
731 res
= qpolynomial_fold_alloc(fold1
->type
, isl_dim_copy(fold1
->dim
),
732 fold1
->n
+ fold2
->n
);
736 for (i
= 0; i
< fold1
->n
; ++i
) {
737 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
738 if (!res
->qp
[res
->n
])
743 for (i
= 0; i
< fold2
->n
; ++i
) {
744 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
745 if (!res
->qp
[res
->n
])
750 isl_qpolynomial_fold_free(fold1
);
751 isl_qpolynomial_fold_free(fold2
);
755 isl_qpolynomial_fold_free(res
);
756 isl_qpolynomial_fold_free(fold1
);
757 isl_qpolynomial_fold_free(fold2
);
761 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
762 __isl_take isl_pw_qpolynomial_fold
*pw1
,
763 __isl_take isl_pw_qpolynomial_fold
*pw2
)
766 struct isl_pw_qpolynomial_fold
*res
;
772 isl_assert(pw1
->dim
->ctx
, isl_dim_equal(pw1
->dim
, pw2
->dim
), goto error
);
774 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
775 isl_pw_qpolynomial_fold_free(pw1
);
779 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
780 isl_pw_qpolynomial_fold_free(pw2
);
784 if (pw1
->type
!= pw2
->type
)
785 isl_die(pw1
->dim
->ctx
, isl_error_invalid
,
786 "fold types don't match", goto error
);
788 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
789 res
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1
->dim
),
792 for (i
= 0; i
< pw1
->n
; ++i
) {
793 set
= isl_set_copy(pw1
->p
[i
].set
);
794 for (j
= 0; j
< pw2
->n
; ++j
) {
795 struct isl_set
*common
;
796 isl_qpolynomial_fold
*sum
;
797 set
= isl_set_subtract(set
,
798 isl_set_copy(pw2
->p
[j
].set
));
799 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
800 isl_set_copy(pw2
->p
[j
].set
));
801 if (isl_set_plain_is_empty(common
)) {
802 isl_set_free(common
);
806 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
807 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
808 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
810 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
812 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
813 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
816 for (j
= 0; j
< pw2
->n
; ++j
) {
817 set
= isl_set_copy(pw2
->p
[j
].set
);
818 for (i
= 0; i
< pw1
->n
; ++i
)
819 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
820 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
821 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
824 isl_pw_qpolynomial_fold_free(pw1
);
825 isl_pw_qpolynomial_fold_free(pw2
);
829 isl_pw_qpolynomial_fold_free(pw1
);
830 isl_pw_qpolynomial_fold_free(pw2
);
834 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
835 __isl_take isl_union_pw_qpolynomial_fold
*u
,
836 __isl_take isl_pw_qpolynomial_fold
*part
)
839 struct isl_hash_table_entry
*entry
;
841 u
= isl_union_pw_qpolynomial_fold_cow(u
);
846 isl_assert(u
->dim
->ctx
, isl_dim_match(part
->dim
, isl_dim_param
, u
->dim
,
847 isl_dim_param
), goto error
);
849 hash
= isl_dim_get_hash(part
->dim
);
850 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
851 &has_dim
, part
->dim
, 1);
858 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
859 isl_pw_qpolynomial_fold_copy(part
));
862 isl_pw_qpolynomial_fold_free(part
);
867 isl_pw_qpolynomial_fold_free(part
);
868 isl_union_pw_qpolynomial_fold_free(u
);
872 static int fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
874 isl_union_pw_qpolynomial_fold
**u
;
875 u
= (isl_union_pw_qpolynomial_fold
**)user
;
877 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
882 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
883 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
884 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
886 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
891 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
892 &fold_part
, &u1
) < 0)
895 isl_union_pw_qpolynomial_fold_free(u2
);
899 isl_union_pw_qpolynomial_fold_free(u1
);
900 isl_union_pw_qpolynomial_fold_free(u2
);
904 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
905 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
908 isl_pw_qpolynomial_fold
*pwf
;
913 pwf
= isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp
->dim
), type
,
916 for (i
= 0; i
< pwqp
->n
; ++i
)
917 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
918 isl_set_copy(pwqp
->p
[i
].set
),
919 isl_qpolynomial_fold_alloc(type
,
920 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
922 isl_pw_qpolynomial_free(pwqp
);
927 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
928 __isl_keep isl_qpolynomial_fold
*fold2
)
932 if (!fold1
|| !fold2
)
935 if (fold1
->n
!= fold2
->n
)
938 /* We probably want to sort the qps first... */
939 for (i
= 0; i
< fold1
->n
; ++i
) {
940 int eq
= isl_qpolynomial_plain_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
948 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_eval(
949 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
955 isl_assert(pnt
->dim
->ctx
, isl_dim_equal(pnt
->dim
, fold
->dim
), goto error
);
956 isl_assert(pnt
->dim
->ctx
,
957 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
961 qp
= isl_qpolynomial_zero(isl_dim_copy(fold
->dim
));
964 qp
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
965 isl_point_copy(pnt
));
966 for (i
= 1; i
< fold
->n
; ++i
) {
967 isl_qpolynomial
*qp_i
;
968 qp_i
= isl_qpolynomial_eval(
969 isl_qpolynomial_copy(fold
->qp
[i
]),
970 isl_point_copy(pnt
));
971 if (fold
->type
== isl_fold_max
)
972 qp
= isl_qpolynomial_max_cst(qp
, qp_i
);
974 qp
= isl_qpolynomial_min_cst(qp
, qp_i
);
977 isl_qpolynomial_fold_free(fold
);
982 isl_qpolynomial_fold_free(fold
);
987 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
992 for (i
= 0; i
< pwf
->n
; ++i
)
993 n
+= pwf
->p
[i
].fold
->n
;
998 __isl_give isl_qpolynomial
*isl_qpolynomial_fold_opt_on_domain(
999 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
1002 isl_qpolynomial
*opt
;
1008 isl_dim
*dim
= isl_dim_copy(fold
->dim
);
1010 isl_qpolynomial_fold_free(fold
);
1011 return isl_qpolynomial_zero(dim
);
1014 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
1015 isl_set_copy(set
), max
);
1016 for (i
= 1; i
< fold
->n
; ++i
) {
1017 isl_qpolynomial
*opt_i
;
1018 opt_i
= isl_qpolynomial_opt_on_domain(
1019 isl_qpolynomial_copy(fold
->qp
[i
]),
1020 isl_set_copy(set
), max
);
1022 opt
= isl_qpolynomial_max_cst(opt
, opt_i
);
1024 opt
= isl_qpolynomial_min_cst(opt
, opt_i
);
1028 isl_qpolynomial_fold_free(fold
);
1033 isl_qpolynomial_fold_free(fold
);
1037 /* Check whether for each quasi-polynomial in "fold2" there is
1038 * a quasi-polynomial in "fold1" that dominates it on "set".
1040 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
1041 __isl_keep isl_qpolynomial_fold
*fold1
,
1042 __isl_keep isl_qpolynomial_fold
*fold2
)
1047 if (!set
|| !fold1
|| !fold2
)
1050 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
1052 for (i
= 0; i
< fold2
->n
; ++i
) {
1053 for (j
= 0; j
< fold1
->n
; ++j
) {
1057 d
= isl_qpolynomial_sub(
1058 isl_qpolynomial_copy(fold1
->qp
[j
]),
1059 isl_qpolynomial_copy(fold2
->qp
[i
]));
1060 sgn
= isl_qpolynomial_sign(set
, d
);
1061 isl_qpolynomial_free(d
);
1072 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1073 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1076 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold
*pwf1
,
1077 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1080 isl_set
*dom1
, *dom2
;
1091 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1092 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1093 is_subset
= isl_set_is_subset(dom2
, dom1
);
1097 if (is_subset
< 0 || !is_subset
)
1100 for (i
= 0; i
< pwf2
->n
; ++i
) {
1101 for (j
= 0; j
< pwf1
->n
; ++j
) {
1106 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1107 isl_set_copy(pwf2
->p
[i
].set
));
1108 is_empty
= isl_set_is_empty(common
);
1109 if (is_empty
< 0 || is_empty
) {
1110 isl_set_free(common
);
1115 covers
= qpolynomial_fold_covers_on_domain(common
,
1116 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1117 isl_set_free(common
);
1118 if (covers
< 0 || !covers
)
1126 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph(
1127 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1132 if (!fold
|| !morph
)
1135 ctx
= fold
->dim
->ctx
;
1136 isl_assert(ctx
, isl_dim_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1138 fold
= isl_qpolynomial_fold_cow(fold
);
1142 isl_dim_free(fold
->dim
);
1143 fold
->dim
= isl_dim_copy(morph
->ran
->dim
);
1147 for (i
= 0; i
< fold
->n
; ++i
) {
1148 fold
->qp
[i
] = isl_qpolynomial_morph(fold
->qp
[i
],
1149 isl_morph_copy(morph
));
1154 isl_morph_free(morph
);
1158 isl_qpolynomial_fold_free(fold
);
1159 isl_morph_free(morph
);
1163 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1166 return isl_fold_list
;
1170 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1171 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1174 return isl_fold_list
;
1178 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1179 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_dim
*dim
)
1186 if (isl_dim_equal(fold
->dim
, dim
)) {
1191 fold
= isl_qpolynomial_fold_cow(fold
);
1195 isl_dim_free(fold
->dim
);
1196 fold
->dim
= isl_dim_copy(dim
);
1200 for (i
= 0; i
< fold
->n
; ++i
) {
1201 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1211 isl_qpolynomial_fold_free(fold
);
1216 int isl_qpolynomial_fold_foreach_qpolynomial(
1217 __isl_keep isl_qpolynomial_fold
*fold
,
1218 int (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1225 for (i
= 0; i
< fold
->n
; ++i
)
1226 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1232 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1233 __isl_take isl_qpolynomial_fold
*fold
,
1234 enum isl_dim_type dst_type
, unsigned dst_pos
,
1235 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1242 fold
= isl_qpolynomial_fold_cow(fold
);
1246 fold
->dim
= isl_dim_move(fold
->dim
, dst_type
, dst_pos
,
1247 src_type
, src_pos
, n
);
1251 for (i
= 0; i
< fold
->n
; ++i
) {
1252 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1253 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1260 isl_qpolynomial_fold_free(fold
);
1264 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1265 * in fold->qp[k] by subs[i].
1267 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1268 __isl_take isl_qpolynomial_fold
*fold
,
1269 enum isl_dim_type type
, unsigned first
, unsigned n
,
1270 __isl_keep isl_qpolynomial
**subs
)
1277 fold
= isl_qpolynomial_fold_cow(fold
);
1281 for (i
= 0; i
< fold
->n
; ++i
) {
1282 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1283 type
, first
, n
, subs
);
1290 isl_qpolynomial_fold_free(fold
);
1294 static int add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1297 isl_pw_qpolynomial_fold
*pwf
;
1298 isl_union_pw_qpolynomial_fold
**upwf
;
1300 struct isl_hash_table_entry
*entry
;
1302 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1304 ctx
= pwqp
->dim
->ctx
;
1305 hash
= isl_dim_get_hash(pwqp
->dim
);
1306 entry
= isl_hash_table_find(ctx
, &(*upwf
)->table
,
1307 hash
, &has_dim
, pwqp
->dim
, 1);
1311 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1315 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1318 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
)) {
1319 isl_pw_qpolynomial_fold_free(entry
->data
);
1320 isl_hash_table_remove(ctx
, &(*upwf
)->table
, entry
);
1326 isl_pw_qpolynomial_free(pwqp
);
1330 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1331 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1332 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1334 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1335 isl_union_pw_qpolynomial_get_dim(upwqp
));
1336 upwqp
= isl_union_pw_qpolynomial_align_params(upwqp
,
1337 isl_union_pw_qpolynomial_fold_get_dim(upwf
));
1339 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1340 if (!upwf
|| !upwqp
)
1343 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1347 isl_union_pw_qpolynomial_free(upwqp
);
1351 isl_union_pw_qpolynomial_fold_free(upwf
);
1352 isl_union_pw_qpolynomial_free(upwqp
);
1356 static int compatible_range(__isl_keep isl_dim
*dim1
, __isl_keep isl_dim
*dim2
)
1359 m
= isl_dim_match(dim1
, isl_dim_param
, dim2
, isl_dim_param
);
1362 return isl_dim_tuple_match(dim1
, isl_dim_out
, dim2
, isl_dim_set
);
1365 /* Compute the intersection of the range of the map and the domain
1366 * of the piecewise quasipolynomial reduction and then compute a bound
1367 * on the associated quasipolynomial reduction over all elements
1368 * in this intersection.
1370 * We first introduce some unconstrained dimensions in the
1371 * piecewise quasipolynomial, intersect the resulting domain
1372 * with the wrapped map and the compute the sum.
1374 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1375 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1385 ctx
= isl_map_get_ctx(map
);
1389 map_dim
= isl_map_get_dim(map
);
1390 pwf_dim
= isl_pw_qpolynomial_fold_get_dim(pwf
);
1391 ok
= compatible_range(map_dim
, pwf_dim
);
1392 isl_dim_free(map_dim
);
1393 isl_dim_free(pwf_dim
);
1395 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1398 n_in
= isl_map_dim(map
, isl_dim_in
);
1399 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_set
, 0, n_in
);
1401 dom
= isl_map_wrap(map
);
1402 pwf
= isl_pw_qpolynomial_fold_reset_dim(pwf
, isl_set_get_dim(dom
));
1404 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1405 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1410 isl_pw_qpolynomial_fold_free(pwf
);
1414 __isl_give isl_pw_qpolynomial_fold
*isl_set_apply_pw_qpolynomial_fold(
1415 __isl_take isl_set
*set
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1420 map
= isl_map_from_range(set
);
1421 return isl_map_apply_pw_qpolynomial_fold(map
, pwf
, tight
);
1424 struct isl_apply_fold_data
{
1425 isl_union_pw_qpolynomial_fold
*upwf
;
1426 isl_union_pw_qpolynomial_fold
*res
;
1431 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold
*pwf
,
1436 struct isl_apply_fold_data
*data
= user
;
1439 map_dim
= isl_map_get_dim(data
->map
);
1440 pwf_dim
= isl_pw_qpolynomial_fold_get_dim(pwf
);
1441 ok
= compatible_range(map_dim
, pwf_dim
);
1442 isl_dim_free(map_dim
);
1443 isl_dim_free(pwf_dim
);
1446 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1447 pwf
, data
->tight
? &data
->tight
: NULL
);
1448 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1451 isl_pw_qpolynomial_fold_free(pwf
);
1456 static int map_apply(__isl_take isl_map
*map
, void *user
)
1458 struct isl_apply_fold_data
*data
= user
;
1462 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1463 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1469 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1470 __isl_take isl_union_map
*umap
,
1471 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1475 struct isl_apply_fold_data data
;
1477 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1478 isl_union_map_get_dim(umap
));
1479 umap
= isl_union_map_align_params(umap
,
1480 isl_union_pw_qpolynomial_fold_get_dim(upwf
));
1483 data
.tight
= tight
? 1 : 0;
1484 dim
= isl_union_pw_qpolynomial_fold_get_dim(upwf
);
1485 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1486 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1487 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1490 isl_union_map_free(umap
);
1491 isl_union_pw_qpolynomial_fold_free(upwf
);
1494 *tight
= data
.tight
;
1498 isl_union_map_free(umap
);
1499 isl_union_pw_qpolynomial_fold_free(upwf
);
1500 isl_union_pw_qpolynomial_fold_free(data
.res
);
1504 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_set_apply_union_pw_qpolynomial_fold(
1505 __isl_take isl_union_set
*uset
,
1506 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1508 return isl_union_map_apply_union_pw_qpolynomial_fold(uset
, upwf
, tight
);
1511 /* Reorder the dimension of "fold" according to the given reordering.
1513 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign(
1514 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1518 fold
= isl_qpolynomial_fold_cow(fold
);
1522 for (i
= 0; i
< fold
->n
; ++i
) {
1523 fold
->qp
[i
] = isl_qpolynomial_realign(fold
->qp
[i
],
1524 isl_reordering_copy(r
));
1529 fold
= isl_qpolynomial_fold_reset_dim(fold
, isl_dim_copy(r
->dim
));
1531 isl_reordering_free(r
);
1535 isl_qpolynomial_fold_free(fold
);
1536 isl_reordering_free(r
);
1540 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_mul_isl_int(
1541 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1545 if (isl_int_is_one(v
))
1547 if (fold
&& isl_int_is_zero(v
)) {
1548 isl_qpolynomial_fold
*zero
;
1549 isl_dim
*dim
= isl_dim_copy(fold
->dim
);
1550 zero
= isl_qpolynomial_fold_empty(fold
->type
, dim
);
1551 isl_qpolynomial_fold_free(fold
);
1555 fold
= isl_qpolynomial_fold_cow(fold
);
1559 if (isl_int_is_neg(v
))
1560 fold
->type
= isl_fold_type_negate(fold
->type
);
1561 for (i
= 0; i
< fold
->n
; ++i
) {
1562 fold
->qp
[i
] = isl_qpolynomial_mul_isl_int(fold
->qp
[i
], v
);
1569 isl_qpolynomial_fold_free(fold
);