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>
17 #include <isl_lp_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>
23 #include <isl/deprecated/polynomial_int.h>
25 enum isl_fold
isl_fold_type_negate(enum isl_fold type
)
36 isl_die(NULL
, isl_error_internal
, "unhandled isl_fold type", abort());
39 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
40 enum isl_fold type
, __isl_take isl_space
*dim
, int n
)
42 isl_qpolynomial_fold
*fold
;
47 isl_assert(dim
->ctx
, n
>= 0, goto error
);
48 fold
= isl_calloc(dim
->ctx
, struct isl_qpolynomial_fold
,
49 sizeof(struct isl_qpolynomial_fold
) +
50 (n
- 1) * sizeof(struct isl_qpolynomial
*));
66 isl_ctx
*isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold
*fold
)
68 return fold
? fold
->dim
->ctx
: NULL
;
71 __isl_give isl_space
*isl_qpolynomial_fold_get_domain_space(
72 __isl_keep isl_qpolynomial_fold
*fold
)
74 return fold
? isl_space_copy(fold
->dim
) : NULL
;
77 __isl_give isl_space
*isl_qpolynomial_fold_get_space(
78 __isl_keep isl_qpolynomial_fold
*fold
)
83 space
= isl_space_copy(fold
->dim
);
84 space
= isl_space_from_domain(space
);
85 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
89 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_domain_space(
90 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*dim
)
94 fold
= isl_qpolynomial_fold_cow(fold
);
98 for (i
= 0; i
< fold
->n
; ++i
) {
99 fold
->qp
[i
] = isl_qpolynomial_reset_domain_space(fold
->qp
[i
],
100 isl_space_copy(dim
));
105 isl_space_free(fold
->dim
);
110 isl_qpolynomial_fold_free(fold
);
115 /* Reset the space of "fold". This function is called from isl_pw_templ.c
116 * and doesn't know if the space of an element object is represented
117 * directly or through its domain. It therefore passes along both.
119 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_space_and_domain(
120 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*space
,
121 __isl_take isl_space
*domain
)
123 isl_space_free(space
);
124 return isl_qpolynomial_fold_reset_domain_space(fold
, domain
);
127 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
128 enum isl_dim_type type
, unsigned first
, unsigned n
)
134 if (fold
->n
== 0 || n
== 0)
137 for (i
= 0; i
< fold
->n
; ++i
) {
138 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
140 if (involves
< 0 || involves
)
146 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_set_dim_name(
147 __isl_take isl_qpolynomial_fold
*fold
,
148 enum isl_dim_type type
, unsigned pos
, const char *s
)
152 fold
= isl_qpolynomial_fold_cow(fold
);
155 fold
->dim
= isl_space_set_dim_name(fold
->dim
, type
, pos
, s
);
159 for (i
= 0; i
< fold
->n
; ++i
) {
160 fold
->qp
[i
] = isl_qpolynomial_set_dim_name(fold
->qp
[i
],
168 isl_qpolynomial_fold_free(fold
);
172 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
173 __isl_take isl_qpolynomial_fold
*fold
,
174 enum isl_dim_type type
, unsigned first
, unsigned n
)
177 enum isl_dim_type set_type
;
184 set_type
= type
== isl_dim_in
? isl_dim_set
: type
;
186 fold
= isl_qpolynomial_fold_cow(fold
);
189 fold
->dim
= isl_space_drop_dims(fold
->dim
, set_type
, first
, n
);
193 for (i
= 0; i
< fold
->n
; ++i
) {
194 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
202 isl_qpolynomial_fold_free(fold
);
206 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
207 __isl_take isl_qpolynomial_fold
*fold
,
208 enum isl_dim_type type
, unsigned first
, unsigned n
)
214 if (n
== 0 && !isl_space_is_named_or_nested(fold
->dim
, type
))
217 fold
= isl_qpolynomial_fold_cow(fold
);
220 fold
->dim
= isl_space_insert_dims(fold
->dim
, type
, first
, n
);
224 for (i
= 0; i
< fold
->n
; ++i
) {
225 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
233 isl_qpolynomial_fold_free(fold
);
237 /* Determine the sign of the constant quasipolynomial "qp".
244 * For qp == 0, we can return either -1 or 1. In practice, we return 1.
245 * For qp == NaN, the sign is undefined, so we return 0.
247 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
249 struct isl_upoly_cst
*cst
;
251 if (isl_qpolynomial_is_nan(qp
))
254 cst
= isl_upoly_as_cst(qp
->upoly
);
258 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
261 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
262 __isl_keep isl_qpolynomial
*qp
)
264 enum isl_lp_result res
;
269 aff
= isl_qpolynomial_extract_affine(qp
);
275 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
277 if (res
== isl_lp_error
)
279 if (res
== isl_lp_empty
||
280 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
285 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
287 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
296 /* Determine, if possible, the sign of the quasipolynomial "qp" on
299 * If qp is a constant, then the problem is trivial.
300 * If qp is linear, then we check if the minimum of the corresponding
301 * affine constraint is non-negative or if the maximum is non-positive.
303 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
304 * in "set". If so, we write qp(v,v') as
306 * q(v,v') * (v - l) + r(v')
308 * if q(v,v') and r(v') have the same known sign, then the original
309 * quasipolynomial has the same sign as well.
316 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
317 __isl_keep isl_qpolynomial
*qp
)
322 struct isl_upoly_rec
*rec
;
325 enum isl_lp_result res
;
328 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
332 return isl_qpolynomial_cst_sign(qp
);
334 is
= isl_qpolynomial_is_affine(qp
);
338 return isl_qpolynomial_aff_sign(set
, qp
);
340 if (qp
->div
->n_row
> 0)
343 rec
= isl_upoly_as_rec(qp
->upoly
);
347 d
= isl_space_dim(qp
->dim
, isl_dim_all
);
348 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
352 isl_seq_clr(v
->el
+ 1, 1 + d
);
353 isl_int_set_si(v
->el
[0], 1);
354 isl_int_set_si(v
->el
[2 + qp
->upoly
->var
], 1);
358 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
359 if (res
== isl_lp_ok
) {
360 isl_qpolynomial
*min
;
361 isl_qpolynomial
*base
;
362 isl_qpolynomial
*r
, *q
;
365 min
= isl_qpolynomial_cst_on_domain(isl_space_copy(qp
->dim
), l
);
366 base
= isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp
->dim
),
369 r
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
370 isl_upoly_copy(rec
->p
[rec
->n
- 1]));
371 q
= isl_qpolynomial_copy(r
);
373 for (i
= rec
->n
- 2; i
>= 0; --i
) {
374 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
375 t
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
376 isl_upoly_copy(rec
->p
[i
]));
377 r
= isl_qpolynomial_add(r
, t
);
380 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
381 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
384 if (isl_qpolynomial_is_zero(q
))
385 sgn
= isl_qpolynomial_sign(set
, r
);
386 else if (isl_qpolynomial_is_zero(r
))
387 sgn
= isl_qpolynomial_sign(set
, q
);
390 sgn_r
= isl_qpolynomial_sign(set
, r
);
391 sgn_q
= isl_qpolynomial_sign(set
, q
);
396 isl_qpolynomial_free(min
);
397 isl_qpolynomial_free(base
);
398 isl_qpolynomial_free(q
);
399 isl_qpolynomial_free(r
);
409 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
410 __isl_keep isl_set
*set
,
411 __isl_take isl_qpolynomial_fold
*fold1
,
412 __isl_take isl_qpolynomial_fold
*fold2
)
416 struct isl_qpolynomial_fold
*res
= NULL
;
419 if (!fold1
|| !fold2
)
422 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
423 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
426 better
= fold1
->type
== isl_fold_max
? -1 : 1;
428 if (isl_qpolynomial_fold_is_empty(fold1
)) {
429 isl_qpolynomial_fold_free(fold1
);
433 if (isl_qpolynomial_fold_is_empty(fold2
)) {
434 isl_qpolynomial_fold_free(fold2
);
438 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
439 fold1
->n
+ fold2
->n
);
443 for (i
= 0; i
< fold1
->n
; ++i
) {
444 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
445 if (!res
->qp
[res
->n
])
451 for (i
= 0; i
< fold2
->n
; ++i
) {
452 for (j
= n1
- 1; j
>= 0; --j
) {
455 equal
= isl_qpolynomial_plain_is_equal(res
->qp
[j
],
461 d
= isl_qpolynomial_sub(
462 isl_qpolynomial_copy(res
->qp
[j
]),
463 isl_qpolynomial_copy(fold2
->qp
[i
]));
464 sgn
= isl_qpolynomial_sign(set
, d
);
465 isl_qpolynomial_free(d
);
470 isl_qpolynomial_free(res
->qp
[j
]);
472 res
->qp
[j
] = res
->qp
[n1
- 1];
474 if (n1
!= res
->n
- 1)
475 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
480 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
481 if (!res
->qp
[res
->n
])
486 isl_qpolynomial_fold_free(fold1
);
487 isl_qpolynomial_fold_free(fold2
);
491 isl_qpolynomial_fold_free(res
);
492 isl_qpolynomial_fold_free(fold1
);
493 isl_qpolynomial_fold_free(fold2
);
497 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
498 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
505 if (isl_qpolynomial_is_zero(qp
)) {
506 isl_qpolynomial_free(qp
);
510 fold
= isl_qpolynomial_fold_cow(fold
);
514 for (i
= 0; i
< fold
->n
; ++i
) {
515 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
516 isl_qpolynomial_copy(qp
));
521 isl_qpolynomial_free(qp
);
524 isl_qpolynomial_fold_free(fold
);
525 isl_qpolynomial_free(qp
);
529 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
530 __isl_keep isl_set
*dom
,
531 __isl_take isl_qpolynomial_fold
*fold1
,
532 __isl_take isl_qpolynomial_fold
*fold2
)
535 isl_qpolynomial_fold
*res
= NULL
;
537 if (!fold1
|| !fold2
)
540 if (isl_qpolynomial_fold_is_empty(fold1
)) {
541 isl_qpolynomial_fold_free(fold1
);
545 if (isl_qpolynomial_fold_is_empty(fold2
)) {
546 isl_qpolynomial_fold_free(fold2
);
550 if (fold1
->n
== 1 && fold2
->n
!= 1)
551 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
554 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
555 isl_qpolynomial_copy(fold2
->qp
[0]));
556 isl_qpolynomial_fold_free(fold2
);
560 res
= isl_qpolynomial_fold_add_qpolynomial(
561 isl_qpolynomial_fold_copy(fold1
),
562 isl_qpolynomial_copy(fold2
->qp
[0]));
564 for (i
= 1; i
< fold2
->n
; ++i
) {
565 isl_qpolynomial_fold
*res_i
;
566 res_i
= isl_qpolynomial_fold_add_qpolynomial(
567 isl_qpolynomial_fold_copy(fold1
),
568 isl_qpolynomial_copy(fold2
->qp
[i
]));
569 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
572 isl_qpolynomial_fold_free(fold1
);
573 isl_qpolynomial_fold_free(fold2
);
576 isl_qpolynomial_fold_free(res
);
577 isl_qpolynomial_fold_free(fold1
);
578 isl_qpolynomial_fold_free(fold2
);
582 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
583 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
590 fold
= isl_qpolynomial_fold_cow(fold
);
594 for (i
= 0; i
< fold
->n
; ++i
) {
595 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
596 isl_basic_set_copy(eq
));
601 isl_basic_set_free(eq
);
604 isl_basic_set_free(eq
);
605 isl_qpolynomial_fold_free(fold
);
609 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist(
610 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
614 if (!fold
|| !context
)
617 fold
= isl_qpolynomial_fold_cow(fold
);
621 for (i
= 0; i
< fold
->n
; ++i
) {
622 fold
->qp
[i
] = isl_qpolynomial_gist(fold
->qp
[i
],
623 isl_set_copy(context
));
628 isl_set_free(context
);
631 isl_set_free(context
);
632 isl_qpolynomial_fold_free(fold
);
636 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist_params(
637 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
639 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
640 isl_set
*dom_context
= isl_set_universe(space
);
641 dom_context
= isl_set_intersect_params(dom_context
, context
);
642 return isl_qpolynomial_fold_gist(fold
, dom_context
);
648 #define PW isl_pw_qpolynomial_fold
650 #define EL isl_qpolynomial_fold
652 #define EL_IS_ZERO is_empty
656 #define IS_ZERO is_zero
659 #undef DEFAULT_IS_ZERO
660 #define DEFAULT_IS_ZERO 1
665 #include <isl_pw_templ.c>
668 #define UNION isl_union_pw_qpolynomial_fold
670 #define PART isl_pw_qpolynomial_fold
672 #define PARTS pw_qpolynomial_fold
677 #include <isl_union_templ.c>
679 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
680 __isl_take isl_space
*dim
)
682 return qpolynomial_fold_alloc(type
, dim
, 0);
685 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
686 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
688 isl_qpolynomial_fold
*fold
;
693 fold
= qpolynomial_fold_alloc(type
, isl_space_copy(qp
->dim
), 1);
702 isl_qpolynomial_fold_free(fold
);
703 isl_qpolynomial_free(qp
);
707 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
708 __isl_keep isl_qpolynomial_fold
*fold
)
717 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
718 __isl_keep isl_qpolynomial_fold
*fold
)
721 isl_qpolynomial_fold
*dup
;
725 dup
= qpolynomial_fold_alloc(fold
->type
,
726 isl_space_copy(fold
->dim
), fold
->n
);
731 for (i
= 0; i
< fold
->n
; ++i
) {
732 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
739 isl_qpolynomial_fold_free(dup
);
743 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
744 __isl_take isl_qpolynomial_fold
*fold
)
752 return isl_qpolynomial_fold_dup(fold
);
755 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold
*fold
)
764 for (i
= 0; i
< fold
->n
; ++i
)
765 isl_qpolynomial_free(fold
->qp
[i
]);
766 isl_space_free(fold
->dim
);
770 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
778 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
779 __isl_take isl_qpolynomial_fold
*fold1
,
780 __isl_take isl_qpolynomial_fold
*fold2
)
783 struct isl_qpolynomial_fold
*res
= NULL
;
785 if (!fold1
|| !fold2
)
788 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
789 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
792 if (isl_qpolynomial_fold_is_empty(fold1
)) {
793 isl_qpolynomial_fold_free(fold1
);
797 if (isl_qpolynomial_fold_is_empty(fold2
)) {
798 isl_qpolynomial_fold_free(fold2
);
802 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
803 fold1
->n
+ fold2
->n
);
807 for (i
= 0; i
< fold1
->n
; ++i
) {
808 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
809 if (!res
->qp
[res
->n
])
814 for (i
= 0; i
< fold2
->n
; ++i
) {
815 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
816 if (!res
->qp
[res
->n
])
821 isl_qpolynomial_fold_free(fold1
);
822 isl_qpolynomial_fold_free(fold2
);
826 isl_qpolynomial_fold_free(res
);
827 isl_qpolynomial_fold_free(fold1
);
828 isl_qpolynomial_fold_free(fold2
);
832 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
833 __isl_take isl_pw_qpolynomial_fold
*pw1
,
834 __isl_take isl_pw_qpolynomial_fold
*pw2
)
837 struct isl_pw_qpolynomial_fold
*res
;
843 isl_assert(pw1
->dim
->ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
845 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
846 isl_pw_qpolynomial_fold_free(pw1
);
850 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
851 isl_pw_qpolynomial_fold_free(pw2
);
855 if (pw1
->type
!= pw2
->type
)
856 isl_die(pw1
->dim
->ctx
, isl_error_invalid
,
857 "fold types don't match", goto error
);
859 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
860 res
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1
->dim
),
863 for (i
= 0; i
< pw1
->n
; ++i
) {
864 set
= isl_set_copy(pw1
->p
[i
].set
);
865 for (j
= 0; j
< pw2
->n
; ++j
) {
866 struct isl_set
*common
;
867 isl_qpolynomial_fold
*sum
;
868 set
= isl_set_subtract(set
,
869 isl_set_copy(pw2
->p
[j
].set
));
870 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
871 isl_set_copy(pw2
->p
[j
].set
));
872 if (isl_set_plain_is_empty(common
)) {
873 isl_set_free(common
);
877 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
878 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
879 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
881 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
883 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
884 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
887 for (j
= 0; j
< pw2
->n
; ++j
) {
888 set
= isl_set_copy(pw2
->p
[j
].set
);
889 for (i
= 0; i
< pw1
->n
; ++i
)
890 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
891 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
892 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
895 isl_pw_qpolynomial_fold_free(pw1
);
896 isl_pw_qpolynomial_fold_free(pw2
);
900 isl_pw_qpolynomial_fold_free(pw1
);
901 isl_pw_qpolynomial_fold_free(pw2
);
905 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
906 __isl_take isl_union_pw_qpolynomial_fold
*u
,
907 __isl_take isl_pw_qpolynomial_fold
*part
)
910 struct isl_hash_table_entry
*entry
;
912 u
= isl_union_pw_qpolynomial_fold_cow(u
);
917 isl_assert(u
->dim
->ctx
, isl_space_match(part
->dim
, isl_dim_param
, u
->dim
,
918 isl_dim_param
), goto error
);
920 hash
= isl_space_get_hash(part
->dim
);
921 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
922 &has_dim
, part
->dim
, 1);
929 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
930 isl_pw_qpolynomial_fold_copy(part
));
933 isl_pw_qpolynomial_fold_free(part
);
938 isl_pw_qpolynomial_fold_free(part
);
939 isl_union_pw_qpolynomial_fold_free(u
);
943 static int fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
945 isl_union_pw_qpolynomial_fold
**u
;
946 u
= (isl_union_pw_qpolynomial_fold
**)user
;
948 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
953 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
954 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
955 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
957 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
962 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
963 &fold_part
, &u1
) < 0)
966 isl_union_pw_qpolynomial_fold_free(u2
);
970 isl_union_pw_qpolynomial_fold_free(u1
);
971 isl_union_pw_qpolynomial_fold_free(u2
);
975 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
976 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
979 isl_pw_qpolynomial_fold
*pwf
;
984 pwf
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp
->dim
),
987 for (i
= 0; i
< pwqp
->n
; ++i
)
988 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
989 isl_set_copy(pwqp
->p
[i
].set
),
990 isl_qpolynomial_fold_alloc(type
,
991 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
993 isl_pw_qpolynomial_free(pwqp
);
998 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_add(
999 __isl_take isl_pw_qpolynomial_fold
*pwf1
,
1000 __isl_take isl_pw_qpolynomial_fold
*pwf2
)
1002 return isl_pw_qpolynomial_fold_union_add_(pwf1
, pwf2
);
1005 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
1006 __isl_keep isl_qpolynomial_fold
*fold2
)
1010 if (!fold1
|| !fold2
)
1013 if (fold1
->n
!= fold2
->n
)
1016 /* We probably want to sort the qps first... */
1017 for (i
= 0; i
< fold1
->n
; ++i
) {
1018 int eq
= isl_qpolynomial_plain_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
1026 __isl_give isl_val
*isl_qpolynomial_fold_eval(
1027 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
1034 ctx
= isl_point_get_ctx(pnt
);
1035 isl_assert(pnt
->dim
->ctx
, isl_space_is_equal(pnt
->dim
, fold
->dim
), goto error
);
1036 isl_assert(pnt
->dim
->ctx
,
1037 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
1041 v
= isl_val_zero(ctx
);
1044 v
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
1045 isl_point_copy(pnt
));
1046 for (i
= 1; i
< fold
->n
; ++i
) {
1048 v_i
= isl_qpolynomial_eval(
1049 isl_qpolynomial_copy(fold
->qp
[i
]),
1050 isl_point_copy(pnt
));
1051 if (fold
->type
== isl_fold_max
)
1052 v
= isl_val_max(v
, v_i
);
1054 v
= isl_val_min(v
, v_i
);
1057 isl_qpolynomial_fold_free(fold
);
1058 isl_point_free(pnt
);
1062 isl_qpolynomial_fold_free(fold
);
1063 isl_point_free(pnt
);
1067 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
1072 for (i
= 0; i
< pwf
->n
; ++i
)
1073 n
+= pwf
->p
[i
].fold
->n
;
1078 __isl_give isl_val
*isl_qpolynomial_fold_opt_on_domain(
1079 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
1088 opt
= isl_val_zero(isl_set_get_ctx(set
));
1090 isl_qpolynomial_fold_free(fold
);
1094 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
1095 isl_set_copy(set
), max
);
1096 for (i
= 1; i
< fold
->n
; ++i
) {
1098 opt_i
= isl_qpolynomial_opt_on_domain(
1099 isl_qpolynomial_copy(fold
->qp
[i
]),
1100 isl_set_copy(set
), max
);
1102 opt
= isl_val_max(opt
, opt_i
);
1104 opt
= isl_val_min(opt
, opt_i
);
1108 isl_qpolynomial_fold_free(fold
);
1113 isl_qpolynomial_fold_free(fold
);
1117 /* Check whether for each quasi-polynomial in "fold2" there is
1118 * a quasi-polynomial in "fold1" that dominates it on "set".
1120 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
1121 __isl_keep isl_qpolynomial_fold
*fold1
,
1122 __isl_keep isl_qpolynomial_fold
*fold2
)
1127 if (!set
|| !fold1
|| !fold2
)
1130 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
1132 for (i
= 0; i
< fold2
->n
; ++i
) {
1133 for (j
= 0; j
< fold1
->n
; ++j
) {
1137 d
= isl_qpolynomial_sub(
1138 isl_qpolynomial_copy(fold1
->qp
[j
]),
1139 isl_qpolynomial_copy(fold2
->qp
[i
]));
1140 sgn
= isl_qpolynomial_sign(set
, d
);
1141 isl_qpolynomial_free(d
);
1152 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1153 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1156 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold
*pwf1
,
1157 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1160 isl_set
*dom1
, *dom2
;
1171 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1172 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1173 is_subset
= isl_set_is_subset(dom2
, dom1
);
1177 if (is_subset
< 0 || !is_subset
)
1180 for (i
= 0; i
< pwf2
->n
; ++i
) {
1181 for (j
= 0; j
< pwf1
->n
; ++j
) {
1186 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1187 isl_set_copy(pwf2
->p
[i
].set
));
1188 is_empty
= isl_set_is_empty(common
);
1189 if (is_empty
< 0 || is_empty
) {
1190 isl_set_free(common
);
1195 covers
= qpolynomial_fold_covers_on_domain(common
,
1196 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1197 isl_set_free(common
);
1198 if (covers
< 0 || !covers
)
1206 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph_domain(
1207 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1212 if (!fold
|| !morph
)
1215 ctx
= fold
->dim
->ctx
;
1216 isl_assert(ctx
, isl_space_is_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1218 fold
= isl_qpolynomial_fold_cow(fold
);
1222 isl_space_free(fold
->dim
);
1223 fold
->dim
= isl_space_copy(morph
->ran
->dim
);
1227 for (i
= 0; i
< fold
->n
; ++i
) {
1228 fold
->qp
[i
] = isl_qpolynomial_morph_domain(fold
->qp
[i
],
1229 isl_morph_copy(morph
));
1234 isl_morph_free(morph
);
1238 isl_qpolynomial_fold_free(fold
);
1239 isl_morph_free(morph
);
1243 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1246 return isl_fold_list
;
1250 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1251 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1254 return isl_fold_list
;
1258 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1259 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*dim
)
1266 if (isl_space_is_equal(fold
->dim
, dim
)) {
1267 isl_space_free(dim
);
1271 fold
= isl_qpolynomial_fold_cow(fold
);
1275 isl_space_free(fold
->dim
);
1276 fold
->dim
= isl_space_copy(dim
);
1280 for (i
= 0; i
< fold
->n
; ++i
) {
1281 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1282 isl_space_copy(dim
));
1287 isl_space_free(dim
);
1291 isl_qpolynomial_fold_free(fold
);
1292 isl_space_free(dim
);
1296 int isl_qpolynomial_fold_foreach_qpolynomial(
1297 __isl_keep isl_qpolynomial_fold
*fold
,
1298 int (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1305 for (i
= 0; i
< fold
->n
; ++i
)
1306 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1312 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1313 __isl_take isl_qpolynomial_fold
*fold
,
1314 enum isl_dim_type dst_type
, unsigned dst_pos
,
1315 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1322 fold
= isl_qpolynomial_fold_cow(fold
);
1326 fold
->dim
= isl_space_move_dims(fold
->dim
, dst_type
, dst_pos
,
1327 src_type
, src_pos
, n
);
1331 for (i
= 0; i
< fold
->n
; ++i
) {
1332 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1333 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1340 isl_qpolynomial_fold_free(fold
);
1344 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1345 * in fold->qp[k] by subs[i].
1347 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1348 __isl_take isl_qpolynomial_fold
*fold
,
1349 enum isl_dim_type type
, unsigned first
, unsigned n
,
1350 __isl_keep isl_qpolynomial
**subs
)
1357 fold
= isl_qpolynomial_fold_cow(fold
);
1361 for (i
= 0; i
< fold
->n
; ++i
) {
1362 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1363 type
, first
, n
, subs
);
1370 isl_qpolynomial_fold_free(fold
);
1374 static int add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1377 isl_pw_qpolynomial_fold
*pwf
;
1378 isl_union_pw_qpolynomial_fold
**upwf
;
1380 struct isl_hash_table_entry
*entry
;
1382 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1384 ctx
= pwqp
->dim
->ctx
;
1385 hash
= isl_space_get_hash(pwqp
->dim
);
1386 entry
= isl_hash_table_find(ctx
, &(*upwf
)->table
,
1387 hash
, &has_dim
, pwqp
->dim
, 1);
1391 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1395 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1398 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
)) {
1399 isl_pw_qpolynomial_fold_free(entry
->data
);
1400 isl_hash_table_remove(ctx
, &(*upwf
)->table
, entry
);
1406 isl_pw_qpolynomial_free(pwqp
);
1410 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1411 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1412 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1414 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1415 isl_union_pw_qpolynomial_get_space(upwqp
));
1416 upwqp
= isl_union_pw_qpolynomial_align_params(upwqp
,
1417 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1419 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1420 if (!upwf
|| !upwqp
)
1423 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1427 isl_union_pw_qpolynomial_free(upwqp
);
1431 isl_union_pw_qpolynomial_fold_free(upwf
);
1432 isl_union_pw_qpolynomial_free(upwqp
);
1436 static int join_compatible(__isl_keep isl_space
*dim1
, __isl_keep isl_space
*dim2
)
1439 m
= isl_space_match(dim1
, isl_dim_param
, dim2
, isl_dim_param
);
1442 return isl_space_tuple_is_equal(dim1
, isl_dim_out
, dim2
, isl_dim_in
);
1445 /* Compute the intersection of the range of the map and the domain
1446 * of the piecewise quasipolynomial reduction and then compute a bound
1447 * on the associated quasipolynomial reduction over all elements
1448 * in this intersection.
1450 * We first introduce some unconstrained dimensions in the
1451 * piecewise quasipolynomial, intersect the resulting domain
1452 * with the wrapped map and the compute the sum.
1454 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1455 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1465 ctx
= isl_map_get_ctx(map
);
1469 map_dim
= isl_map_get_space(map
);
1470 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1471 ok
= join_compatible(map_dim
, pwf_dim
);
1472 isl_space_free(map_dim
);
1473 isl_space_free(pwf_dim
);
1475 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1478 n_in
= isl_map_dim(map
, isl_dim_in
);
1479 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_in
, 0, n_in
);
1481 dom
= isl_map_wrap(map
);
1482 pwf
= isl_pw_qpolynomial_fold_reset_domain_space(pwf
,
1483 isl_set_get_space(dom
));
1485 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1486 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1491 isl_pw_qpolynomial_fold_free(pwf
);
1495 __isl_give isl_pw_qpolynomial_fold
*isl_set_apply_pw_qpolynomial_fold(
1496 __isl_take isl_set
*set
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1499 return isl_map_apply_pw_qpolynomial_fold(set
, pwf
, tight
);
1502 struct isl_apply_fold_data
{
1503 isl_union_pw_qpolynomial_fold
*upwf
;
1504 isl_union_pw_qpolynomial_fold
*res
;
1509 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold
*pwf
,
1514 struct isl_apply_fold_data
*data
= user
;
1517 map_dim
= isl_map_get_space(data
->map
);
1518 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1519 ok
= join_compatible(map_dim
, pwf_dim
);
1520 isl_space_free(map_dim
);
1521 isl_space_free(pwf_dim
);
1524 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1525 pwf
, data
->tight
? &data
->tight
: NULL
);
1526 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1529 isl_pw_qpolynomial_fold_free(pwf
);
1534 static int map_apply(__isl_take isl_map
*map
, void *user
)
1536 struct isl_apply_fold_data
*data
= user
;
1540 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1541 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1547 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1548 __isl_take isl_union_map
*umap
,
1549 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1553 struct isl_apply_fold_data data
;
1555 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1556 isl_union_map_get_space(umap
));
1557 umap
= isl_union_map_align_params(umap
,
1558 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1561 data
.tight
= tight
? 1 : 0;
1562 dim
= isl_union_pw_qpolynomial_fold_get_space(upwf
);
1563 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1564 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1565 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1568 isl_union_map_free(umap
);
1569 isl_union_pw_qpolynomial_fold_free(upwf
);
1572 *tight
= data
.tight
;
1576 isl_union_map_free(umap
);
1577 isl_union_pw_qpolynomial_fold_free(upwf
);
1578 isl_union_pw_qpolynomial_fold_free(data
.res
);
1582 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_set_apply_union_pw_qpolynomial_fold(
1583 __isl_take isl_union_set
*uset
,
1584 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, int *tight
)
1586 return isl_union_map_apply_union_pw_qpolynomial_fold(uset
, upwf
, tight
);
1589 /* Reorder the dimension of "fold" according to the given reordering.
1591 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign_domain(
1592 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1596 fold
= isl_qpolynomial_fold_cow(fold
);
1600 for (i
= 0; i
< fold
->n
; ++i
) {
1601 fold
->qp
[i
] = isl_qpolynomial_realign_domain(fold
->qp
[i
],
1602 isl_reordering_copy(r
));
1607 fold
= isl_qpolynomial_fold_reset_domain_space(fold
,
1608 isl_space_copy(r
->dim
));
1610 isl_reordering_free(r
);
1614 isl_qpolynomial_fold_free(fold
);
1615 isl_reordering_free(r
);
1619 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_mul_isl_int(
1620 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1624 if (isl_int_is_one(v
))
1626 if (fold
&& isl_int_is_zero(v
)) {
1627 isl_qpolynomial_fold
*zero
;
1628 isl_space
*dim
= isl_space_copy(fold
->dim
);
1629 zero
= isl_qpolynomial_fold_empty(fold
->type
, dim
);
1630 isl_qpolynomial_fold_free(fold
);
1634 fold
= isl_qpolynomial_fold_cow(fold
);
1638 if (isl_int_is_neg(v
))
1639 fold
->type
= isl_fold_type_negate(fold
->type
);
1640 for (i
= 0; i
< fold
->n
; ++i
) {
1641 fold
->qp
[i
] = isl_qpolynomial_mul_isl_int(fold
->qp
[i
], v
);
1648 isl_qpolynomial_fold_free(fold
);
1652 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale(
1653 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1655 return isl_qpolynomial_fold_mul_isl_int(fold
, v
);
1658 /* Multiply "fold" by "v".
1660 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale_val(
1661 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_val
*v
)
1668 if (isl_val_is_one(v
)) {
1672 if (isl_val_is_zero(v
)) {
1673 isl_qpolynomial_fold
*zero
;
1674 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
1675 zero
= isl_qpolynomial_fold_empty(fold
->type
, space
);
1676 isl_qpolynomial_fold_free(fold
);
1680 if (!isl_val_is_rat(v
))
1681 isl_die(isl_qpolynomial_fold_get_ctx(fold
), isl_error_invalid
,
1682 "expecting rational factor", goto error
);
1684 fold
= isl_qpolynomial_fold_cow(fold
);
1688 if (isl_val_is_neg(v
))
1689 fold
->type
= isl_fold_type_negate(fold
->type
);
1690 for (i
= 0; i
< fold
->n
; ++i
) {
1691 fold
->qp
[i
] = isl_qpolynomial_scale_val(fold
->qp
[i
],
1701 isl_qpolynomial_fold_free(fold
);