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,
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_space_private.h>
16 #include <isl_lp_private.h>
18 #include <isl_mat_private.h>
19 #include <isl_val_private.h>
20 #include <isl_vec_private.h>
21 #include <isl_config.h>
24 #define EL_BASE pw_qpolynomial_fold
26 #include <isl_list_templ.c>
28 enum isl_fold
isl_fold_type_negate(enum isl_fold type
)
39 isl_die(NULL
, isl_error_internal
, "unhandled isl_fold type", abort());
42 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
43 enum isl_fold type
, __isl_take isl_space
*space
, int n
)
45 isl_qpolynomial_fold
*fold
;
50 isl_assert(space
->ctx
, n
>= 0, goto error
);
51 fold
= isl_calloc(space
->ctx
, struct isl_qpolynomial_fold
,
52 sizeof(struct isl_qpolynomial_fold
) +
53 (n
- 1) * sizeof(struct isl_qpolynomial
*));
65 isl_space_free(space
);
69 isl_ctx
*isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold
*fold
)
71 return fold
? fold
->dim
->ctx
: NULL
;
74 __isl_give isl_space
*isl_qpolynomial_fold_get_domain_space(
75 __isl_keep isl_qpolynomial_fold
*fold
)
77 return fold
? isl_space_copy(fold
->dim
) : NULL
;
80 __isl_give isl_space
*isl_qpolynomial_fold_get_space(
81 __isl_keep isl_qpolynomial_fold
*fold
)
86 space
= isl_space_copy(fold
->dim
);
87 space
= isl_space_from_domain(space
);
88 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
92 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_domain_space(
93 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*dim
)
97 fold
= isl_qpolynomial_fold_cow(fold
);
101 for (i
= 0; i
< fold
->n
; ++i
) {
102 fold
->qp
[i
] = isl_qpolynomial_reset_domain_space(fold
->qp
[i
],
103 isl_space_copy(dim
));
108 isl_space_free(fold
->dim
);
113 isl_qpolynomial_fold_free(fold
);
118 /* Reset the space of "fold". This function is called from isl_pw_templ.c
119 * and doesn't know if the space of an element object is represented
120 * directly or through its domain. It therefore passes along both.
122 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_space_and_domain(
123 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*space
,
124 __isl_take isl_space
*domain
)
126 isl_space_free(space
);
127 return isl_qpolynomial_fold_reset_domain_space(fold
, domain
);
130 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
131 enum isl_dim_type type
, unsigned first
, unsigned n
)
137 if (fold
->n
== 0 || n
== 0)
140 for (i
= 0; i
< fold
->n
; ++i
) {
141 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
143 if (involves
< 0 || involves
)
149 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_set_dim_name(
150 __isl_take isl_qpolynomial_fold
*fold
,
151 enum isl_dim_type type
, unsigned pos
, const char *s
)
155 fold
= isl_qpolynomial_fold_cow(fold
);
158 fold
->dim
= isl_space_set_dim_name(fold
->dim
, type
, pos
, s
);
162 for (i
= 0; i
< fold
->n
; ++i
) {
163 fold
->qp
[i
] = isl_qpolynomial_set_dim_name(fold
->qp
[i
],
171 isl_qpolynomial_fold_free(fold
);
175 /* Given a dimension type for an isl_qpolynomial_fold,
176 * return the corresponding type for the domain.
178 static enum isl_dim_type
domain_type(enum isl_dim_type type
)
180 if (type
== isl_dim_in
)
185 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
186 __isl_take isl_qpolynomial_fold
*fold
,
187 enum isl_dim_type type
, unsigned first
, unsigned n
)
190 enum isl_dim_type set_type
;
197 set_type
= domain_type(type
);
199 fold
= isl_qpolynomial_fold_cow(fold
);
202 fold
->dim
= isl_space_drop_dims(fold
->dim
, set_type
, first
, n
);
206 for (i
= 0; i
< fold
->n
; ++i
) {
207 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
215 isl_qpolynomial_fold_free(fold
);
219 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
220 __isl_take isl_qpolynomial_fold
*fold
,
221 enum isl_dim_type type
, unsigned first
, unsigned n
)
227 if (n
== 0 && !isl_space_is_named_or_nested(fold
->dim
, type
))
230 fold
= isl_qpolynomial_fold_cow(fold
);
233 fold
->dim
= isl_space_insert_dims(fold
->dim
, type
, first
, n
);
237 for (i
= 0; i
< fold
->n
; ++i
) {
238 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
246 isl_qpolynomial_fold_free(fold
);
250 /* Determine the sign of the constant quasipolynomial "qp".
257 * For qp == 0, we can return either -1 or 1. In practice, we return 1.
258 * For qp == NaN, the sign is undefined, so we return 0.
260 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
264 if (isl_qpolynomial_is_nan(qp
))
267 cst
= isl_poly_as_cst(qp
->poly
);
271 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
274 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
275 __isl_keep isl_qpolynomial
*qp
)
277 enum isl_lp_result res
;
282 aff
= isl_qpolynomial_extract_affine(qp
);
288 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
290 if (res
== isl_lp_error
)
292 if (res
== isl_lp_empty
||
293 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
298 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
300 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
309 /* Determine, if possible, the sign of the quasipolynomial "qp" on
312 * If qp is a constant, then the problem is trivial.
313 * If qp is linear, then we check if the minimum of the corresponding
314 * affine constraint is non-negative or if the maximum is non-positive.
316 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
317 * in "set". If so, we write qp(v,v') as
319 * q(v,v') * (v - l) + r(v')
321 * if q(v,v') and r(v') have the same known sign, then the original
322 * quasipolynomial has the same sign as well.
329 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
330 __isl_keep isl_qpolynomial
*qp
)
338 enum isl_lp_result res
;
341 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
345 return isl_qpolynomial_cst_sign(qp
);
347 is
= isl_qpolynomial_is_affine(qp
);
351 return isl_qpolynomial_aff_sign(set
, qp
);
353 if (qp
->div
->n_row
> 0)
356 rec
= isl_poly_as_rec(qp
->poly
);
360 d
= isl_space_dim(qp
->dim
, isl_dim_all
);
363 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
367 isl_seq_clr(v
->el
+ 1, 1 + d
);
368 isl_int_set_si(v
->el
[0], 1);
369 isl_int_set_si(v
->el
[2 + qp
->poly
->var
], 1);
373 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
374 if (res
== isl_lp_ok
) {
375 isl_qpolynomial
*min
;
376 isl_qpolynomial
*base
;
377 isl_qpolynomial
*r
, *q
;
380 min
= isl_qpolynomial_cst_on_domain(isl_space_copy(qp
->dim
), l
);
381 base
= isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp
->dim
),
384 r
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
385 isl_poly_copy(rec
->p
[rec
->n
- 1]));
386 q
= isl_qpolynomial_copy(r
);
388 for (i
= rec
->n
- 2; i
>= 0; --i
) {
389 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
390 t
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
391 isl_poly_copy(rec
->p
[i
]));
392 r
= isl_qpolynomial_add(r
, t
);
395 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
396 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
399 if (isl_qpolynomial_is_zero(q
))
400 sgn
= isl_qpolynomial_sign(set
, r
);
401 else if (isl_qpolynomial_is_zero(r
))
402 sgn
= isl_qpolynomial_sign(set
, q
);
405 sgn_r
= isl_qpolynomial_sign(set
, r
);
406 sgn_q
= isl_qpolynomial_sign(set
, q
);
411 isl_qpolynomial_free(min
);
412 isl_qpolynomial_free(base
);
413 isl_qpolynomial_free(q
);
414 isl_qpolynomial_free(r
);
424 /* Combine "fold1" and "fold2" into a single reduction, eliminating
425 * those elements of one reduction that are already covered by the other
426 * reduction on "set".
428 * If "fold1" or "fold2" is an empty reduction, then return
429 * the other reduction.
430 * If "fold1" or "fold2" is a NaN, then return this NaN.
432 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
433 __isl_keep isl_set
*set
,
434 __isl_take isl_qpolynomial_fold
*fold1
,
435 __isl_take isl_qpolynomial_fold
*fold2
)
439 struct isl_qpolynomial_fold
*res
= NULL
;
442 if (!fold1
|| !fold2
)
445 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
446 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
449 better
= fold1
->type
== isl_fold_max
? -1 : 1;
451 if (isl_qpolynomial_fold_is_empty(fold1
) ||
452 isl_qpolynomial_fold_is_nan(fold2
)) {
453 isl_qpolynomial_fold_free(fold1
);
457 if (isl_qpolynomial_fold_is_empty(fold2
) ||
458 isl_qpolynomial_fold_is_nan(fold1
)) {
459 isl_qpolynomial_fold_free(fold2
);
463 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
464 fold1
->n
+ fold2
->n
);
468 for (i
= 0; i
< fold1
->n
; ++i
) {
469 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
470 if (!res
->qp
[res
->n
])
476 for (i
= 0; i
< fold2
->n
; ++i
) {
477 for (j
= n1
- 1; j
>= 0; --j
) {
480 equal
= isl_qpolynomial_plain_is_equal(res
->qp
[j
],
486 d
= isl_qpolynomial_sub(
487 isl_qpolynomial_copy(res
->qp
[j
]),
488 isl_qpolynomial_copy(fold2
->qp
[i
]));
489 sgn
= isl_qpolynomial_sign(set
, d
);
490 isl_qpolynomial_free(d
);
495 isl_qpolynomial_free(res
->qp
[j
]);
497 res
->qp
[j
] = res
->qp
[n1
- 1];
499 if (n1
!= res
->n
- 1)
500 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
505 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
506 if (!res
->qp
[res
->n
])
511 isl_qpolynomial_fold_free(fold1
);
512 isl_qpolynomial_fold_free(fold2
);
516 isl_qpolynomial_fold_free(res
);
517 isl_qpolynomial_fold_free(fold1
);
518 isl_qpolynomial_fold_free(fold2
);
522 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
523 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
530 if (isl_qpolynomial_is_zero(qp
)) {
531 isl_qpolynomial_free(qp
);
535 fold
= isl_qpolynomial_fold_cow(fold
);
539 for (i
= 0; i
< fold
->n
; ++i
) {
540 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
541 isl_qpolynomial_copy(qp
));
546 isl_qpolynomial_free(qp
);
549 isl_qpolynomial_fold_free(fold
);
550 isl_qpolynomial_free(qp
);
554 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
555 __isl_keep isl_set
*dom
,
556 __isl_take isl_qpolynomial_fold
*fold1
,
557 __isl_take isl_qpolynomial_fold
*fold2
)
560 isl_qpolynomial_fold
*res
= NULL
;
562 if (!fold1
|| !fold2
)
565 if (isl_qpolynomial_fold_is_empty(fold1
)) {
566 isl_qpolynomial_fold_free(fold1
);
570 if (isl_qpolynomial_fold_is_empty(fold2
)) {
571 isl_qpolynomial_fold_free(fold2
);
575 if (fold1
->n
== 1 && fold2
->n
!= 1)
576 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
579 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
580 isl_qpolynomial_copy(fold2
->qp
[0]));
581 isl_qpolynomial_fold_free(fold2
);
585 res
= isl_qpolynomial_fold_add_qpolynomial(
586 isl_qpolynomial_fold_copy(fold1
),
587 isl_qpolynomial_copy(fold2
->qp
[0]));
589 for (i
= 1; i
< fold2
->n
; ++i
) {
590 isl_qpolynomial_fold
*res_i
;
591 res_i
= isl_qpolynomial_fold_add_qpolynomial(
592 isl_qpolynomial_fold_copy(fold1
),
593 isl_qpolynomial_copy(fold2
->qp
[i
]));
594 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
597 isl_qpolynomial_fold_free(fold1
);
598 isl_qpolynomial_fold_free(fold2
);
601 isl_qpolynomial_fold_free(res
);
602 isl_qpolynomial_fold_free(fold1
);
603 isl_qpolynomial_fold_free(fold2
);
607 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
608 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
615 fold
= isl_qpolynomial_fold_cow(fold
);
619 for (i
= 0; i
< fold
->n
; ++i
) {
620 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
621 isl_basic_set_copy(eq
));
626 isl_basic_set_free(eq
);
629 isl_basic_set_free(eq
);
630 isl_qpolynomial_fold_free(fold
);
634 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist(
635 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
639 if (!fold
|| !context
)
642 fold
= isl_qpolynomial_fold_cow(fold
);
646 for (i
= 0; i
< fold
->n
; ++i
) {
647 fold
->qp
[i
] = isl_qpolynomial_gist(fold
->qp
[i
],
648 isl_set_copy(context
));
653 isl_set_free(context
);
656 isl_set_free(context
);
657 isl_qpolynomial_fold_free(fold
);
661 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist_params(
662 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
664 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
665 isl_set
*dom_context
= isl_set_universe(space
);
666 dom_context
= isl_set_intersect_params(dom_context
, context
);
667 return isl_qpolynomial_fold_gist(fold
, dom_context
);
670 #define isl_qpolynomial_fold_involves_nan isl_qpolynomial_fold_is_nan
675 #define PW isl_pw_qpolynomial_fold
677 #define EL isl_qpolynomial_fold
679 #define EL_IS_ZERO is_empty
683 #define IS_ZERO is_zero
686 #undef DEFAULT_IS_ZERO
687 #define DEFAULT_IS_ZERO 1
693 #include <isl_pw_templ.c>
694 #include <isl_pw_eval.c>
697 #define BASE pw_qpolynomial_fold
701 #include <isl_union_single.c>
702 #include <isl_union_eval.c>
704 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
705 __isl_take isl_space
*dim
)
707 return qpolynomial_fold_alloc(type
, dim
, 0);
710 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
711 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
713 isl_qpolynomial_fold
*fold
;
718 fold
= qpolynomial_fold_alloc(type
, isl_space_copy(qp
->dim
), 1);
727 isl_qpolynomial_fold_free(fold
);
728 isl_qpolynomial_free(qp
);
732 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
733 __isl_keep isl_qpolynomial_fold
*fold
)
742 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
743 __isl_keep isl_qpolynomial_fold
*fold
)
746 isl_qpolynomial_fold
*dup
;
750 dup
= qpolynomial_fold_alloc(fold
->type
,
751 isl_space_copy(fold
->dim
), fold
->n
);
756 for (i
= 0; i
< fold
->n
; ++i
) {
757 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
764 isl_qpolynomial_fold_free(dup
);
768 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
769 __isl_take isl_qpolynomial_fold
*fold
)
777 return isl_qpolynomial_fold_dup(fold
);
780 __isl_null isl_qpolynomial_fold
*isl_qpolynomial_fold_free(
781 __isl_take isl_qpolynomial_fold
*fold
)
790 for (i
= 0; i
< fold
->n
; ++i
)
791 isl_qpolynomial_free(fold
->qp
[i
]);
792 isl_space_free(fold
->dim
);
798 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
806 /* Does "fold" represent max(NaN) or min(NaN)?
808 isl_bool
isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold
*fold
)
811 return isl_bool_error
;
813 return isl_bool_false
;
814 return isl_qpolynomial_is_nan(fold
->qp
[0]);
817 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
818 __isl_take isl_qpolynomial_fold
*fold1
,
819 __isl_take isl_qpolynomial_fold
*fold2
)
822 struct isl_qpolynomial_fold
*res
= NULL
;
824 if (!fold1
|| !fold2
)
827 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
828 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
831 if (isl_qpolynomial_fold_is_empty(fold1
)) {
832 isl_qpolynomial_fold_free(fold1
);
836 if (isl_qpolynomial_fold_is_empty(fold2
)) {
837 isl_qpolynomial_fold_free(fold2
);
841 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
842 fold1
->n
+ fold2
->n
);
846 for (i
= 0; i
< fold1
->n
; ++i
) {
847 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
848 if (!res
->qp
[res
->n
])
853 for (i
= 0; i
< fold2
->n
; ++i
) {
854 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
855 if (!res
->qp
[res
->n
])
860 isl_qpolynomial_fold_free(fold1
);
861 isl_qpolynomial_fold_free(fold2
);
865 isl_qpolynomial_fold_free(res
);
866 isl_qpolynomial_fold_free(fold1
);
867 isl_qpolynomial_fold_free(fold2
);
871 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
872 __isl_take isl_pw_qpolynomial_fold
*pw1
,
873 __isl_take isl_pw_qpolynomial_fold
*pw2
)
876 struct isl_pw_qpolynomial_fold
*res
;
882 isl_assert(pw1
->dim
->ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
884 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
885 isl_pw_qpolynomial_fold_free(pw1
);
889 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
890 isl_pw_qpolynomial_fold_free(pw2
);
894 if (pw1
->type
!= pw2
->type
)
895 isl_die(pw1
->dim
->ctx
, isl_error_invalid
,
896 "fold types don't match", goto error
);
898 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
899 res
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1
->dim
),
902 for (i
= 0; i
< pw1
->n
; ++i
) {
903 set
= isl_set_copy(pw1
->p
[i
].set
);
904 for (j
= 0; j
< pw2
->n
; ++j
) {
905 struct isl_set
*common
;
906 isl_qpolynomial_fold
*sum
;
907 set
= isl_set_subtract(set
,
908 isl_set_copy(pw2
->p
[j
].set
));
909 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
910 isl_set_copy(pw2
->p
[j
].set
));
911 if (isl_set_plain_is_empty(common
)) {
912 isl_set_free(common
);
916 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
917 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
918 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
920 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
922 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
923 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
926 for (j
= 0; j
< pw2
->n
; ++j
) {
927 set
= isl_set_copy(pw2
->p
[j
].set
);
928 for (i
= 0; i
< pw1
->n
; ++i
)
929 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
930 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
931 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
934 isl_pw_qpolynomial_fold_free(pw1
);
935 isl_pw_qpolynomial_fold_free(pw2
);
939 isl_pw_qpolynomial_fold_free(pw1
);
940 isl_pw_qpolynomial_fold_free(pw2
);
944 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
945 __isl_take isl_union_pw_qpolynomial_fold
*u
,
946 __isl_take isl_pw_qpolynomial_fold
*part
)
948 struct isl_hash_table_entry
*entry
;
950 u
= isl_union_pw_qpolynomial_fold_cow(u
);
954 if (isl_space_check_equal_params(part
->dim
, u
->space
) < 0)
957 entry
= isl_union_pw_qpolynomial_fold_find_part_entry(u
, part
->dim
, 1);
964 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
965 isl_pw_qpolynomial_fold_copy(part
));
968 isl_pw_qpolynomial_fold_free(part
);
973 isl_pw_qpolynomial_fold_free(part
);
974 isl_union_pw_qpolynomial_fold_free(u
);
978 static isl_stat
fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
980 isl_union_pw_qpolynomial_fold
**u
;
981 u
= (isl_union_pw_qpolynomial_fold
**)user
;
983 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
988 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
989 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
990 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
992 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
997 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
998 &fold_part
, &u1
) < 0)
1001 isl_union_pw_qpolynomial_fold_free(u2
);
1005 isl_union_pw_qpolynomial_fold_free(u1
);
1006 isl_union_pw_qpolynomial_fold_free(u2
);
1010 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
1011 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
1014 isl_pw_qpolynomial_fold
*pwf
;
1019 pwf
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp
->dim
),
1022 for (i
= 0; i
< pwqp
->n
; ++i
)
1023 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
1024 isl_set_copy(pwqp
->p
[i
].set
),
1025 isl_qpolynomial_fold_alloc(type
,
1026 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
1028 isl_pw_qpolynomial_free(pwqp
);
1033 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_add(
1034 __isl_take isl_pw_qpolynomial_fold
*pwf1
,
1035 __isl_take isl_pw_qpolynomial_fold
*pwf2
)
1037 return isl_pw_qpolynomial_fold_union_add_(pwf1
, pwf2
);
1040 /* Compare two quasi-polynomial reductions.
1042 * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater"
1043 * than "fold2" and 0 if they are equal.
1045 int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold
*fold1
,
1046 __isl_keep isl_qpolynomial_fold
*fold2
)
1057 if (fold1
->n
!= fold2
->n
)
1058 return fold1
->n
- fold2
->n
;
1060 for (i
= 0; i
< fold1
->n
; ++i
) {
1063 cmp
= isl_qpolynomial_plain_cmp(fold1
->qp
[i
], fold2
->qp
[i
]);
1071 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
1072 __isl_keep isl_qpolynomial_fold
*fold2
)
1076 if (!fold1
|| !fold2
)
1079 if (fold1
->n
!= fold2
->n
)
1082 /* We probably want to sort the qps first... */
1083 for (i
= 0; i
< fold1
->n
; ++i
) {
1084 int eq
= isl_qpolynomial_plain_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
1092 __isl_give isl_val
*isl_qpolynomial_fold_eval(
1093 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
1100 ctx
= isl_point_get_ctx(pnt
);
1101 isl_assert(pnt
->dim
->ctx
, isl_space_is_equal(pnt
->dim
, fold
->dim
), goto error
);
1102 isl_assert(pnt
->dim
->ctx
,
1103 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
1107 v
= isl_val_zero(ctx
);
1110 v
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
1111 isl_point_copy(pnt
));
1112 for (i
= 1; i
< fold
->n
; ++i
) {
1114 v_i
= isl_qpolynomial_eval(
1115 isl_qpolynomial_copy(fold
->qp
[i
]),
1116 isl_point_copy(pnt
));
1117 if (fold
->type
== isl_fold_max
)
1118 v
= isl_val_max(v
, v_i
);
1120 v
= isl_val_min(v
, v_i
);
1123 isl_qpolynomial_fold_free(fold
);
1124 isl_point_free(pnt
);
1128 isl_qpolynomial_fold_free(fold
);
1129 isl_point_free(pnt
);
1133 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
1138 for (i
= 0; i
< pwf
->n
; ++i
)
1139 n
+= pwf
->p
[i
].fold
->n
;
1144 __isl_give isl_val
*isl_qpolynomial_fold_opt_on_domain(
1145 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
1154 opt
= isl_val_zero(isl_set_get_ctx(set
));
1156 isl_qpolynomial_fold_free(fold
);
1160 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
1161 isl_set_copy(set
), max
);
1162 for (i
= 1; i
< fold
->n
; ++i
) {
1164 opt_i
= isl_qpolynomial_opt_on_domain(
1165 isl_qpolynomial_copy(fold
->qp
[i
]),
1166 isl_set_copy(set
), max
);
1168 opt
= isl_val_max(opt
, opt_i
);
1170 opt
= isl_val_min(opt
, opt_i
);
1174 isl_qpolynomial_fold_free(fold
);
1179 isl_qpolynomial_fold_free(fold
);
1183 /* Check whether for each quasi-polynomial in "fold2" there is
1184 * a quasi-polynomial in "fold1" that dominates it on "set".
1186 static isl_bool
qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
1187 __isl_keep isl_qpolynomial_fold
*fold1
,
1188 __isl_keep isl_qpolynomial_fold
*fold2
)
1193 if (!set
|| !fold1
|| !fold2
)
1194 return isl_bool_error
;
1196 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
1198 for (i
= 0; i
< fold2
->n
; ++i
) {
1199 for (j
= 0; j
< fold1
->n
; ++j
) {
1203 d
= isl_qpolynomial_sub(
1204 isl_qpolynomial_copy(fold1
->qp
[j
]),
1205 isl_qpolynomial_copy(fold2
->qp
[i
]));
1206 sgn
= isl_qpolynomial_sign(set
, d
);
1207 isl_qpolynomial_free(d
);
1212 return isl_bool_false
;
1215 return isl_bool_true
;
1218 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1219 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1222 isl_bool
isl_pw_qpolynomial_fold_covers(
1223 __isl_keep isl_pw_qpolynomial_fold
*pwf1
,
1224 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1227 isl_set
*dom1
, *dom2
;
1231 return isl_bool_error
;
1234 return isl_bool_true
;
1236 return isl_bool_false
;
1238 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1239 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1240 is_subset
= isl_set_is_subset(dom2
, dom1
);
1244 if (is_subset
< 0 || !is_subset
)
1247 for (i
= 0; i
< pwf2
->n
; ++i
) {
1248 for (j
= 0; j
< pwf1
->n
; ++j
) {
1253 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1254 isl_set_copy(pwf2
->p
[i
].set
));
1255 is_empty
= isl_set_is_empty(common
);
1256 if (is_empty
< 0 || is_empty
) {
1257 isl_set_free(common
);
1259 return isl_bool_error
;
1262 covers
= qpolynomial_fold_covers_on_domain(common
,
1263 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1264 isl_set_free(common
);
1265 if (covers
< 0 || !covers
)
1270 return isl_bool_true
;
1273 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph_domain(
1274 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1279 if (!fold
|| !morph
)
1282 ctx
= fold
->dim
->ctx
;
1283 isl_assert(ctx
, isl_space_is_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1285 fold
= isl_qpolynomial_fold_cow(fold
);
1289 isl_space_free(fold
->dim
);
1290 fold
->dim
= isl_space_copy(morph
->ran
->dim
);
1294 for (i
= 0; i
< fold
->n
; ++i
) {
1295 fold
->qp
[i
] = isl_qpolynomial_morph_domain(fold
->qp
[i
],
1296 isl_morph_copy(morph
));
1301 isl_morph_free(morph
);
1305 isl_qpolynomial_fold_free(fold
);
1306 isl_morph_free(morph
);
1310 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1313 return isl_fold_list
;
1317 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1318 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1321 return isl_fold_list
;
1325 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1326 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*dim
)
1333 if (isl_space_is_equal(fold
->dim
, dim
)) {
1334 isl_space_free(dim
);
1338 fold
= isl_qpolynomial_fold_cow(fold
);
1342 isl_space_free(fold
->dim
);
1343 fold
->dim
= isl_space_copy(dim
);
1347 for (i
= 0; i
< fold
->n
; ++i
) {
1348 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1349 isl_space_copy(dim
));
1354 isl_space_free(dim
);
1358 isl_qpolynomial_fold_free(fold
);
1359 isl_space_free(dim
);
1363 isl_stat
isl_qpolynomial_fold_foreach_qpolynomial(
1364 __isl_keep isl_qpolynomial_fold
*fold
,
1365 isl_stat (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1370 return isl_stat_error
;
1372 for (i
= 0; i
< fold
->n
; ++i
)
1373 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1374 return isl_stat_error
;
1379 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1380 __isl_take isl_qpolynomial_fold
*fold
,
1381 enum isl_dim_type dst_type
, unsigned dst_pos
,
1382 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1385 enum isl_dim_type set_src_type
, set_dst_type
;
1390 fold
= isl_qpolynomial_fold_cow(fold
);
1394 set_src_type
= domain_type(src_type
);
1395 set_dst_type
= domain_type(dst_type
);
1397 fold
->dim
= isl_space_move_dims(fold
->dim
, set_dst_type
, dst_pos
,
1398 set_src_type
, src_pos
, n
);
1402 for (i
= 0; i
< fold
->n
; ++i
) {
1403 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1404 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1411 isl_qpolynomial_fold_free(fold
);
1415 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1416 * in fold->qp[k] by subs[i].
1418 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1419 __isl_take isl_qpolynomial_fold
*fold
,
1420 enum isl_dim_type type
, unsigned first
, unsigned n
,
1421 __isl_keep isl_qpolynomial
**subs
)
1428 fold
= isl_qpolynomial_fold_cow(fold
);
1432 for (i
= 0; i
< fold
->n
; ++i
) {
1433 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1434 type
, first
, n
, subs
);
1441 isl_qpolynomial_fold_free(fold
);
1445 static isl_stat
add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1447 isl_pw_qpolynomial_fold
*pwf
;
1448 isl_union_pw_qpolynomial_fold
**upwf
;
1449 struct isl_hash_table_entry
*entry
;
1451 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1453 entry
= isl_union_pw_qpolynomial_fold_find_part_entry(*upwf
,
1458 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1462 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1464 return isl_stat_error
;
1465 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
))
1466 *upwf
= isl_union_pw_qpolynomial_fold_remove_part_entry(
1472 isl_pw_qpolynomial_free(pwqp
);
1473 return isl_stat_error
;
1476 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1477 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1478 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1480 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1481 isl_union_pw_qpolynomial_get_space(upwqp
));
1482 upwqp
= isl_union_pw_qpolynomial_align_params(upwqp
,
1483 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1485 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1486 if (!upwf
|| !upwqp
)
1489 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1493 isl_union_pw_qpolynomial_free(upwqp
);
1497 isl_union_pw_qpolynomial_fold_free(upwf
);
1498 isl_union_pw_qpolynomial_free(upwqp
);
1502 static isl_bool
join_compatible(__isl_keep isl_space
*space1
,
1503 __isl_keep isl_space
*space2
)
1506 m
= isl_space_has_equal_params(space1
, space2
);
1509 return isl_space_tuple_is_equal(space1
, isl_dim_out
,
1510 space2
, isl_dim_in
);
1513 /* Compute the intersection of the range of the map and the domain
1514 * of the piecewise quasipolynomial reduction and then compute a bound
1515 * on the associated quasipolynomial reduction over all elements
1516 * in this intersection.
1518 * We first introduce some unconstrained dimensions in the
1519 * piecewise quasipolynomial, intersect the resulting domain
1520 * with the wrapped map and the compute the sum.
1522 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1523 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1528 isl_space
*map_space
;
1529 isl_space
*pwf_space
;
1533 ctx
= isl_map_get_ctx(map
);
1537 map_space
= isl_map_get_space(map
);
1538 pwf_space
= isl_pw_qpolynomial_fold_get_space(pwf
);
1539 ok
= join_compatible(map_space
, pwf_space
);
1540 isl_space_free(map_space
);
1541 isl_space_free(pwf_space
);
1545 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1548 n_in
= isl_map_dim(map
, isl_dim_in
);
1551 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_in
, 0, n_in
);
1553 dom
= isl_map_wrap(map
);
1554 pwf
= isl_pw_qpolynomial_fold_reset_domain_space(pwf
,
1555 isl_set_get_space(dom
));
1557 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1558 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1563 isl_pw_qpolynomial_fold_free(pwf
);
1567 __isl_give isl_pw_qpolynomial_fold
*isl_set_apply_pw_qpolynomial_fold(
1568 __isl_take isl_set
*set
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1571 return isl_map_apply_pw_qpolynomial_fold(set
, pwf
, tight
);
1574 struct isl_apply_fold_data
{
1575 isl_union_pw_qpolynomial_fold
*upwf
;
1576 isl_union_pw_qpolynomial_fold
*res
;
1581 static isl_stat
pw_qpolynomial_fold_apply(
1582 __isl_take isl_pw_qpolynomial_fold
*pwf
, void *user
)
1586 struct isl_apply_fold_data
*data
= user
;
1589 map_dim
= isl_map_get_space(data
->map
);
1590 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1591 ok
= join_compatible(map_dim
, pwf_dim
);
1592 isl_space_free(map_dim
);
1593 isl_space_free(pwf_dim
);
1596 return isl_stat_error
;
1598 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1599 pwf
, data
->tight
? &data
->tight
: NULL
);
1600 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1603 isl_pw_qpolynomial_fold_free(pwf
);
1608 static isl_stat
map_apply(__isl_take isl_map
*map
, void *user
)
1610 struct isl_apply_fold_data
*data
= user
;
1614 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1615 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1621 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1622 __isl_take isl_union_map
*umap
,
1623 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, isl_bool
*tight
)
1627 struct isl_apply_fold_data data
;
1629 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1630 isl_union_map_get_space(umap
));
1631 umap
= isl_union_map_align_params(umap
,
1632 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1635 data
.tight
= tight
? isl_bool_true
: isl_bool_false
;
1636 dim
= isl_union_pw_qpolynomial_fold_get_space(upwf
);
1637 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1638 data
.res
= isl_union_pw_qpolynomial_fold_zero(dim
, type
);
1639 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1642 isl_union_map_free(umap
);
1643 isl_union_pw_qpolynomial_fold_free(upwf
);
1646 *tight
= data
.tight
;
1650 isl_union_map_free(umap
);
1651 isl_union_pw_qpolynomial_fold_free(upwf
);
1652 isl_union_pw_qpolynomial_fold_free(data
.res
);
1656 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_set_apply_union_pw_qpolynomial_fold(
1657 __isl_take isl_union_set
*uset
,
1658 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, isl_bool
*tight
)
1660 return isl_union_map_apply_union_pw_qpolynomial_fold(uset
, upwf
, tight
);
1663 /* Reorder the dimension of "fold" according to the given reordering.
1665 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign_domain(
1666 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1671 fold
= isl_qpolynomial_fold_cow(fold
);
1675 for (i
= 0; i
< fold
->n
; ++i
) {
1676 fold
->qp
[i
] = isl_qpolynomial_realign_domain(fold
->qp
[i
],
1677 isl_reordering_copy(r
));
1682 space
= isl_reordering_get_space(r
);
1683 fold
= isl_qpolynomial_fold_reset_domain_space(fold
, space
);
1685 isl_reordering_free(r
);
1689 isl_qpolynomial_fold_free(fold
);
1690 isl_reordering_free(r
);
1694 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_mul_isl_int(
1695 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1699 if (isl_int_is_one(v
))
1701 if (fold
&& isl_int_is_zero(v
)) {
1702 isl_qpolynomial_fold
*zero
;
1703 isl_space
*dim
= isl_space_copy(fold
->dim
);
1704 zero
= isl_qpolynomial_fold_empty(fold
->type
, dim
);
1705 isl_qpolynomial_fold_free(fold
);
1709 fold
= isl_qpolynomial_fold_cow(fold
);
1713 if (isl_int_is_neg(v
))
1714 fold
->type
= isl_fold_type_negate(fold
->type
);
1715 for (i
= 0; i
< fold
->n
; ++i
) {
1716 fold
->qp
[i
] = isl_qpolynomial_mul_isl_int(fold
->qp
[i
], v
);
1723 isl_qpolynomial_fold_free(fold
);
1727 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale(
1728 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1730 return isl_qpolynomial_fold_mul_isl_int(fold
, v
);
1733 /* Multiply "fold" by "v".
1735 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale_val(
1736 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_val
*v
)
1743 if (isl_val_is_one(v
)) {
1747 if (isl_val_is_zero(v
)) {
1748 isl_qpolynomial_fold
*zero
;
1749 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
1750 zero
= isl_qpolynomial_fold_empty(fold
->type
, space
);
1751 isl_qpolynomial_fold_free(fold
);
1755 if (!isl_val_is_rat(v
))
1756 isl_die(isl_qpolynomial_fold_get_ctx(fold
), isl_error_invalid
,
1757 "expecting rational factor", goto error
);
1759 fold
= isl_qpolynomial_fold_cow(fold
);
1763 if (isl_val_is_neg(v
))
1764 fold
->type
= isl_fold_type_negate(fold
->type
);
1765 for (i
= 0; i
< fold
->n
; ++i
) {
1766 fold
->qp
[i
] = isl_qpolynomial_scale_val(fold
->qp
[i
],
1776 isl_qpolynomial_fold_free(fold
);
1780 /* Divide "fold" by "v".
1782 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale_down_val(
1783 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_val
*v
)
1788 if (isl_val_is_one(v
)) {
1792 if (!isl_val_is_rat(v
))
1793 isl_die(isl_qpolynomial_fold_get_ctx(fold
), isl_error_invalid
,
1794 "expecting rational factor", goto error
);
1795 if (isl_val_is_zero(v
))
1796 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1797 "cannot scale down by zero", goto error
);
1799 return isl_qpolynomial_fold_scale_val(fold
, isl_val_inv(v
));
1802 isl_qpolynomial_fold_free(fold
);