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
)
32 return isl_fold_error
;
41 isl_die(NULL
, isl_error_internal
, "unhandled isl_fold type", abort());
44 static __isl_give isl_qpolynomial_fold
*qpolynomial_fold_alloc(
45 enum isl_fold type
, __isl_take isl_space
*space
, int n
)
47 isl_qpolynomial_fold
*fold
;
52 isl_assert(space
->ctx
, n
>= 0, goto error
);
53 fold
= isl_calloc(space
->ctx
, struct isl_qpolynomial_fold
,
54 sizeof(struct isl_qpolynomial_fold
) +
55 (n
- 1) * sizeof(struct isl_qpolynomial
*));
67 isl_space_free(space
);
71 isl_ctx
*isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold
*fold
)
73 return fold
? fold
->dim
->ctx
: NULL
;
76 __isl_give isl_space
*isl_qpolynomial_fold_get_domain_space(
77 __isl_keep isl_qpolynomial_fold
*fold
)
79 return fold
? isl_space_copy(fold
->dim
) : NULL
;
82 __isl_give isl_space
*isl_qpolynomial_fold_get_space(
83 __isl_keep isl_qpolynomial_fold
*fold
)
88 space
= isl_space_copy(fold
->dim
);
89 space
= isl_space_from_domain(space
);
90 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
94 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_domain_space(
95 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*space
)
99 fold
= isl_qpolynomial_fold_cow(fold
);
103 for (i
= 0; i
< fold
->n
; ++i
) {
104 fold
->qp
[i
] = isl_qpolynomial_reset_domain_space(fold
->qp
[i
],
105 isl_space_copy(space
));
110 isl_space_free(fold
->dim
);
115 isl_qpolynomial_fold_free(fold
);
116 isl_space_free(space
);
120 /* Reset the space of "fold". This function is called from isl_pw_templ.c
121 * and doesn't know if the space of an element object is represented
122 * directly or through its domain. It therefore passes along both.
124 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_reset_space_and_domain(
125 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*space
,
126 __isl_take isl_space
*domain
)
128 isl_space_free(space
);
129 return isl_qpolynomial_fold_reset_domain_space(fold
, domain
);
132 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold
*fold
,
133 enum isl_dim_type type
, unsigned first
, unsigned n
)
139 if (fold
->n
== 0 || n
== 0)
142 for (i
= 0; i
< fold
->n
; ++i
) {
143 int involves
= isl_qpolynomial_involves_dims(fold
->qp
[i
],
145 if (involves
< 0 || involves
)
151 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_set_dim_name(
152 __isl_take isl_qpolynomial_fold
*fold
,
153 enum isl_dim_type type
, unsigned pos
, const char *s
)
157 fold
= isl_qpolynomial_fold_cow(fold
);
160 fold
->dim
= isl_space_set_dim_name(fold
->dim
, type
, pos
, s
);
164 for (i
= 0; i
< fold
->n
; ++i
) {
165 fold
->qp
[i
] = isl_qpolynomial_set_dim_name(fold
->qp
[i
],
173 isl_qpolynomial_fold_free(fold
);
177 /* Given a dimension type for an isl_qpolynomial_fold,
178 * return the corresponding type for the domain.
180 static enum isl_dim_type
domain_type(enum isl_dim_type type
)
182 if (type
== isl_dim_in
)
187 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_drop_dims(
188 __isl_take isl_qpolynomial_fold
*fold
,
189 enum isl_dim_type type
, unsigned first
, unsigned n
)
192 enum isl_dim_type set_type
;
199 set_type
= domain_type(type
);
201 fold
= isl_qpolynomial_fold_cow(fold
);
204 fold
->dim
= isl_space_drop_dims(fold
->dim
, set_type
, first
, n
);
208 for (i
= 0; i
< fold
->n
; ++i
) {
209 fold
->qp
[i
] = isl_qpolynomial_drop_dims(fold
->qp
[i
],
217 isl_qpolynomial_fold_free(fold
);
221 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_insert_dims(
222 __isl_take isl_qpolynomial_fold
*fold
,
223 enum isl_dim_type type
, unsigned first
, unsigned n
)
229 if (n
== 0 && !isl_space_is_named_or_nested(fold
->dim
, type
))
232 fold
= isl_qpolynomial_fold_cow(fold
);
235 fold
->dim
= isl_space_insert_dims(fold
->dim
, type
, first
, n
);
239 for (i
= 0; i
< fold
->n
; ++i
) {
240 fold
->qp
[i
] = isl_qpolynomial_insert_dims(fold
->qp
[i
],
248 isl_qpolynomial_fold_free(fold
);
252 /* Determine the sign of the constant quasipolynomial "qp".
259 * For qp == 0, we can return either -1 or 1. In practice, we return 1.
260 * For qp == NaN, the sign is undefined, so we return 0.
262 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial
*qp
)
266 if (isl_qpolynomial_is_nan(qp
))
269 cst
= isl_poly_as_cst(qp
->poly
);
273 return isl_int_sgn(cst
->n
) < 0 ? -1 : 1;
276 static int isl_qpolynomial_aff_sign(__isl_keep isl_set
*set
,
277 __isl_keep isl_qpolynomial
*qp
)
279 enum isl_lp_result res
;
284 aff
= isl_qpolynomial_extract_affine(qp
);
290 res
= isl_set_solve_lp(set
, 0, aff
->el
+ 1, aff
->el
[0],
292 if (res
== isl_lp_error
)
294 if (res
== isl_lp_empty
||
295 (res
== isl_lp_ok
&& !isl_int_is_neg(opt
))) {
300 res
= isl_set_solve_lp(set
, 1, aff
->el
+ 1, aff
->el
[0],
302 if (res
== isl_lp_ok
&& !isl_int_is_pos(opt
))
311 /* Determine, if possible, the sign of the quasipolynomial "qp" on
314 * If qp is a constant, then the problem is trivial.
315 * If qp is linear, then we check if the minimum of the corresponding
316 * affine constraint is non-negative or if the maximum is non-positive.
318 * Otherwise, we check if the outermost variable "v" has a lower bound "l"
319 * in "set". If so, we write qp(v,v') as
321 * q(v,v') * (v - l) + r(v')
323 * if q(v,v') and r(v') have the same known sign, then the original
324 * quasipolynomial has the same sign as well.
331 static int isl_qpolynomial_sign(__isl_keep isl_set
*set
,
332 __isl_keep isl_qpolynomial
*qp
)
340 enum isl_lp_result res
;
343 is
= isl_qpolynomial_is_cst(qp
, NULL
, NULL
);
347 return isl_qpolynomial_cst_sign(qp
);
349 is
= isl_qpolynomial_is_affine(qp
);
353 return isl_qpolynomial_aff_sign(set
, qp
);
355 if (qp
->div
->n_row
> 0)
358 rec
= isl_poly_as_rec(qp
->poly
);
362 d
= isl_space_dim(qp
->dim
, isl_dim_all
);
365 v
= isl_vec_alloc(set
->ctx
, 2 + d
);
369 isl_seq_clr(v
->el
+ 1, 1 + d
);
370 isl_int_set_si(v
->el
[0], 1);
371 isl_int_set_si(v
->el
[2 + qp
->poly
->var
], 1);
375 res
= isl_set_solve_lp(set
, 0, v
->el
+ 1, v
->el
[0], &l
, NULL
, NULL
);
376 if (res
== isl_lp_ok
) {
377 isl_qpolynomial
*min
;
378 isl_qpolynomial
*base
;
379 isl_qpolynomial
*r
, *q
;
382 min
= isl_qpolynomial_cst_on_domain(isl_space_copy(qp
->dim
), l
);
383 base
= isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp
->dim
),
386 r
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
387 isl_poly_copy(rec
->p
[rec
->n
- 1]));
388 q
= isl_qpolynomial_copy(r
);
390 for (i
= rec
->n
- 2; i
>= 0; --i
) {
391 r
= isl_qpolynomial_mul(r
, isl_qpolynomial_copy(min
));
392 t
= isl_qpolynomial_alloc(isl_space_copy(qp
->dim
), 0,
393 isl_poly_copy(rec
->p
[i
]));
394 r
= isl_qpolynomial_add(r
, t
);
397 q
= isl_qpolynomial_mul(q
, isl_qpolynomial_copy(base
));
398 q
= isl_qpolynomial_add(q
, isl_qpolynomial_copy(r
));
401 if (isl_qpolynomial_is_zero(q
))
402 sgn
= isl_qpolynomial_sign(set
, r
);
403 else if (isl_qpolynomial_is_zero(r
))
404 sgn
= isl_qpolynomial_sign(set
, q
);
407 sgn_r
= isl_qpolynomial_sign(set
, r
);
408 sgn_q
= isl_qpolynomial_sign(set
, q
);
413 isl_qpolynomial_free(min
);
414 isl_qpolynomial_free(base
);
415 isl_qpolynomial_free(q
);
416 isl_qpolynomial_free(r
);
426 /* Combine "fold1" and "fold2" into a single reduction, eliminating
427 * those elements of one reduction that are already covered by the other
428 * reduction on "set".
430 * If "fold1" or "fold2" is an empty reduction, then return
431 * the other reduction.
432 * If "fold1" or "fold2" is a NaN, then return this NaN.
434 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold_on_domain(
435 __isl_keep isl_set
*set
,
436 __isl_take isl_qpolynomial_fold
*fold1
,
437 __isl_take isl_qpolynomial_fold
*fold2
)
441 struct isl_qpolynomial_fold
*res
= NULL
;
444 if (!fold1
|| !fold2
)
447 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
448 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
451 better
= fold1
->type
== isl_fold_max
? -1 : 1;
453 if (isl_qpolynomial_fold_is_empty(fold1
) ||
454 isl_qpolynomial_fold_is_nan(fold2
)) {
455 isl_qpolynomial_fold_free(fold1
);
459 if (isl_qpolynomial_fold_is_empty(fold2
) ||
460 isl_qpolynomial_fold_is_nan(fold1
)) {
461 isl_qpolynomial_fold_free(fold2
);
465 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
466 fold1
->n
+ fold2
->n
);
470 for (i
= 0; i
< fold1
->n
; ++i
) {
471 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
472 if (!res
->qp
[res
->n
])
478 for (i
= 0; i
< fold2
->n
; ++i
) {
479 for (j
= n1
- 1; j
>= 0; --j
) {
482 equal
= isl_qpolynomial_plain_is_equal(res
->qp
[j
],
488 d
= isl_qpolynomial_sub(
489 isl_qpolynomial_copy(res
->qp
[j
]),
490 isl_qpolynomial_copy(fold2
->qp
[i
]));
491 sgn
= isl_qpolynomial_sign(set
, d
);
492 isl_qpolynomial_free(d
);
497 isl_qpolynomial_free(res
->qp
[j
]);
499 res
->qp
[j
] = res
->qp
[n1
- 1];
501 if (n1
!= res
->n
- 1)
502 res
->qp
[n1
] = res
->qp
[res
->n
- 1];
507 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
508 if (!res
->qp
[res
->n
])
513 isl_qpolynomial_fold_free(fold1
);
514 isl_qpolynomial_fold_free(fold2
);
518 isl_qpolynomial_fold_free(res
);
519 isl_qpolynomial_fold_free(fold1
);
520 isl_qpolynomial_fold_free(fold2
);
524 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_qpolynomial(
525 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_qpolynomial
*qp
)
532 if (isl_qpolynomial_is_zero(qp
)) {
533 isl_qpolynomial_free(qp
);
537 fold
= isl_qpolynomial_fold_cow(fold
);
541 for (i
= 0; i
< fold
->n
; ++i
) {
542 fold
->qp
[i
] = isl_qpolynomial_add(fold
->qp
[i
],
543 isl_qpolynomial_copy(qp
));
548 isl_qpolynomial_free(qp
);
551 isl_qpolynomial_fold_free(fold
);
552 isl_qpolynomial_free(qp
);
556 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_add_on_domain(
557 __isl_keep isl_set
*dom
,
558 __isl_take isl_qpolynomial_fold
*fold1
,
559 __isl_take isl_qpolynomial_fold
*fold2
)
562 isl_qpolynomial_fold
*res
= NULL
;
564 if (!fold1
|| !fold2
)
567 if (isl_qpolynomial_fold_is_empty(fold1
)) {
568 isl_qpolynomial_fold_free(fold1
);
572 if (isl_qpolynomial_fold_is_empty(fold2
)) {
573 isl_qpolynomial_fold_free(fold2
);
577 if (fold1
->n
== 1 && fold2
->n
!= 1)
578 return isl_qpolynomial_fold_add_on_domain(dom
, fold2
, fold1
);
581 res
= isl_qpolynomial_fold_add_qpolynomial(fold1
,
582 isl_qpolynomial_copy(fold2
->qp
[0]));
583 isl_qpolynomial_fold_free(fold2
);
587 res
= isl_qpolynomial_fold_add_qpolynomial(
588 isl_qpolynomial_fold_copy(fold1
),
589 isl_qpolynomial_copy(fold2
->qp
[0]));
591 for (i
= 1; i
< fold2
->n
; ++i
) {
592 isl_qpolynomial_fold
*res_i
;
593 res_i
= isl_qpolynomial_fold_add_qpolynomial(
594 isl_qpolynomial_fold_copy(fold1
),
595 isl_qpolynomial_copy(fold2
->qp
[i
]));
596 res
= isl_qpolynomial_fold_fold_on_domain(dom
, res
, res_i
);
599 isl_qpolynomial_fold_free(fold1
);
600 isl_qpolynomial_fold_free(fold2
);
603 isl_qpolynomial_fold_free(res
);
604 isl_qpolynomial_fold_free(fold1
);
605 isl_qpolynomial_fold_free(fold2
);
609 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute_equalities(
610 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_basic_set
*eq
)
617 fold
= isl_qpolynomial_fold_cow(fold
);
621 for (i
= 0; i
< fold
->n
; ++i
) {
622 fold
->qp
[i
] = isl_qpolynomial_substitute_equalities(fold
->qp
[i
],
623 isl_basic_set_copy(eq
));
628 isl_basic_set_free(eq
);
631 isl_basic_set_free(eq
);
632 isl_qpolynomial_fold_free(fold
);
636 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist(
637 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
641 if (!fold
|| !context
)
644 fold
= isl_qpolynomial_fold_cow(fold
);
648 for (i
= 0; i
< fold
->n
; ++i
) {
649 fold
->qp
[i
] = isl_qpolynomial_gist(fold
->qp
[i
],
650 isl_set_copy(context
));
655 isl_set_free(context
);
658 isl_set_free(context
);
659 isl_qpolynomial_fold_free(fold
);
663 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_gist_params(
664 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*context
)
666 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
667 isl_set
*dom_context
= isl_set_universe(space
);
668 dom_context
= isl_set_intersect_params(dom_context
, context
);
669 return isl_qpolynomial_fold_gist(fold
, dom_context
);
672 /* Return a zero (i.e., empty) isl_qpolynomial_fold in the given space.
674 * This is a helper function for isl_pw_*_as_* that ensures a uniform
675 * interface over all piecewise types.
677 static __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_zero_in_space(
678 __isl_take isl_space
*space
, enum isl_fold type
)
680 return isl_qpolynomial_fold_empty(type
, isl_space_domain(space
));
683 #define isl_qpolynomial_fold_involves_nan isl_qpolynomial_fold_is_nan
688 #define PW isl_pw_qpolynomial_fold
690 #define BASE qpolynomial_fold
692 #define EL_IS_ZERO is_empty
696 #define IS_ZERO is_zero
699 #undef DEFAULT_IS_ZERO
700 #define DEFAULT_IS_ZERO 1
702 #include <isl_pw_templ.c>
703 #include <isl_pw_eval.c>
704 #include <isl_pw_insert_dims_templ.c>
705 #include <isl_pw_lift_templ.c>
706 #include <isl_pw_morph_templ.c>
707 #include <isl_pw_move_dims_templ.c>
708 #include <isl_pw_opt_templ.c>
711 #define BASE pw_qpolynomial_fold
715 #include <isl_union_single.c>
716 #include <isl_union_eval.c>
718 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_empty(enum isl_fold type
,
719 __isl_take isl_space
*space
)
721 return qpolynomial_fold_alloc(type
, space
, 0);
724 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_alloc(
725 enum isl_fold type
, __isl_take isl_qpolynomial
*qp
)
727 isl_qpolynomial_fold
*fold
;
732 fold
= qpolynomial_fold_alloc(type
, isl_space_copy(qp
->dim
), 1);
741 isl_qpolynomial_fold_free(fold
);
742 isl_qpolynomial_free(qp
);
746 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_copy(
747 __isl_keep isl_qpolynomial_fold
*fold
)
756 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_dup(
757 __isl_keep isl_qpolynomial_fold
*fold
)
760 isl_qpolynomial_fold
*dup
;
764 dup
= qpolynomial_fold_alloc(fold
->type
,
765 isl_space_copy(fold
->dim
), fold
->n
);
770 for (i
= 0; i
< fold
->n
; ++i
) {
771 dup
->qp
[i
] = isl_qpolynomial_copy(fold
->qp
[i
]);
778 isl_qpolynomial_fold_free(dup
);
782 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_cow(
783 __isl_take isl_qpolynomial_fold
*fold
)
791 return isl_qpolynomial_fold_dup(fold
);
794 __isl_null isl_qpolynomial_fold
*isl_qpolynomial_fold_free(
795 __isl_take isl_qpolynomial_fold
*fold
)
804 for (i
= 0; i
< fold
->n
; ++i
)
805 isl_qpolynomial_free(fold
->qp
[i
]);
806 isl_space_free(fold
->dim
);
812 isl_bool
isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold
*fold
)
815 return isl_bool_error
;
817 return isl_bool_ok(fold
->n
== 0);
820 /* Does "fold" represent max(NaN) or min(NaN)?
822 isl_bool
isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold
*fold
)
825 return isl_bool_error
;
827 return isl_bool_false
;
828 return isl_qpolynomial_is_nan(fold
->qp
[0]);
831 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_fold(
832 __isl_take isl_qpolynomial_fold
*fold1
,
833 __isl_take isl_qpolynomial_fold
*fold2
)
836 struct isl_qpolynomial_fold
*res
= NULL
;
838 if (!fold1
|| !fold2
)
841 isl_assert(fold1
->dim
->ctx
, fold1
->type
== fold2
->type
, goto error
);
842 isl_assert(fold1
->dim
->ctx
, isl_space_is_equal(fold1
->dim
, fold2
->dim
),
845 if (isl_qpolynomial_fold_is_empty(fold1
)) {
846 isl_qpolynomial_fold_free(fold1
);
850 if (isl_qpolynomial_fold_is_empty(fold2
)) {
851 isl_qpolynomial_fold_free(fold2
);
855 res
= qpolynomial_fold_alloc(fold1
->type
, isl_space_copy(fold1
->dim
),
856 fold1
->n
+ fold2
->n
);
860 for (i
= 0; i
< fold1
->n
; ++i
) {
861 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold1
->qp
[i
]);
862 if (!res
->qp
[res
->n
])
867 for (i
= 0; i
< fold2
->n
; ++i
) {
868 res
->qp
[res
->n
] = isl_qpolynomial_copy(fold2
->qp
[i
]);
869 if (!res
->qp
[res
->n
])
874 isl_qpolynomial_fold_free(fold1
);
875 isl_qpolynomial_fold_free(fold2
);
879 isl_qpolynomial_fold_free(res
);
880 isl_qpolynomial_fold_free(fold1
);
881 isl_qpolynomial_fold_free(fold2
);
885 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_fold(
886 __isl_take isl_pw_qpolynomial_fold
*pw1
,
887 __isl_take isl_pw_qpolynomial_fold
*pw2
)
890 struct isl_pw_qpolynomial_fold
*res
;
896 isl_assert(pw1
->dim
->ctx
, isl_space_is_equal(pw1
->dim
, pw2
->dim
), goto error
);
898 if (isl_pw_qpolynomial_fold_is_zero(pw1
)) {
899 isl_pw_qpolynomial_fold_free(pw1
);
903 if (isl_pw_qpolynomial_fold_is_zero(pw2
)) {
904 isl_pw_qpolynomial_fold_free(pw2
);
908 if (pw1
->type
!= pw2
->type
)
909 isl_die(pw1
->dim
->ctx
, isl_error_invalid
,
910 "fold types don't match", goto error
);
912 n
= (pw1
->n
+ 1) * (pw2
->n
+ 1);
913 res
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1
->dim
),
916 for (i
= 0; i
< pw1
->n
; ++i
) {
917 set
= isl_set_copy(pw1
->p
[i
].set
);
918 for (j
= 0; j
< pw2
->n
; ++j
) {
919 struct isl_set
*common
;
920 isl_qpolynomial_fold
*sum
;
921 set
= isl_set_subtract(set
,
922 isl_set_copy(pw2
->p
[j
].set
));
923 common
= isl_set_intersect(isl_set_copy(pw1
->p
[i
].set
),
924 isl_set_copy(pw2
->p
[j
].set
));
925 if (isl_set_plain_is_empty(common
)) {
926 isl_set_free(common
);
930 sum
= isl_qpolynomial_fold_fold_on_domain(common
,
931 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
),
932 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
934 res
= isl_pw_qpolynomial_fold_add_piece(res
, common
, sum
);
936 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
937 isl_qpolynomial_fold_copy(pw1
->p
[i
].fold
));
940 for (j
= 0; j
< pw2
->n
; ++j
) {
941 set
= isl_set_copy(pw2
->p
[j
].set
);
942 for (i
= 0; i
< pw1
->n
; ++i
)
943 set
= isl_set_subtract(set
, isl_set_copy(pw1
->p
[i
].set
));
944 res
= isl_pw_qpolynomial_fold_add_piece(res
, set
,
945 isl_qpolynomial_fold_copy(pw2
->p
[j
].fold
));
948 isl_pw_qpolynomial_fold_free(pw1
);
949 isl_pw_qpolynomial_fold_free(pw2
);
953 isl_pw_qpolynomial_fold_free(pw1
);
954 isl_pw_qpolynomial_fold_free(pw2
);
958 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
959 __isl_take isl_union_pw_qpolynomial_fold
*u
,
960 __isl_take isl_pw_qpolynomial_fold
*part
)
962 struct isl_hash_table_entry
*entry
;
964 u
= isl_union_pw_qpolynomial_fold_cow(u
);
968 if (isl_space_check_equal_params(part
->dim
, u
->space
) < 0)
971 entry
= isl_union_pw_qpolynomial_fold_find_part_entry(u
, part
->dim
, 1);
978 entry
->data
= isl_pw_qpolynomial_fold_fold(entry
->data
,
979 isl_pw_qpolynomial_fold_copy(part
));
982 isl_pw_qpolynomial_fold_free(part
);
987 isl_pw_qpolynomial_fold_free(part
);
988 isl_union_pw_qpolynomial_fold_free(u
);
992 static isl_stat
fold_part(__isl_take isl_pw_qpolynomial_fold
*part
, void *user
)
994 isl_union_pw_qpolynomial_fold
**u
;
995 u
= (isl_union_pw_qpolynomial_fold
**)user
;
997 *u
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u
, part
);
1002 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_fold(
1003 __isl_take isl_union_pw_qpolynomial_fold
*u1
,
1004 __isl_take isl_union_pw_qpolynomial_fold
*u2
)
1006 u1
= isl_union_pw_qpolynomial_fold_cow(u1
);
1011 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2
,
1012 &fold_part
, &u1
) < 0)
1015 isl_union_pw_qpolynomial_fold_free(u2
);
1019 isl_union_pw_qpolynomial_fold_free(u1
);
1020 isl_union_pw_qpolynomial_fold_free(u2
);
1024 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_from_pw_qpolynomial(
1025 enum isl_fold type
, __isl_take isl_pw_qpolynomial
*pwqp
)
1028 isl_pw_qpolynomial_fold
*pwf
;
1033 pwf
= isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp
->dim
),
1036 for (i
= 0; i
< pwqp
->n
; ++i
)
1037 pwf
= isl_pw_qpolynomial_fold_add_piece(pwf
,
1038 isl_set_copy(pwqp
->p
[i
].set
),
1039 isl_qpolynomial_fold_alloc(type
,
1040 isl_qpolynomial_copy(pwqp
->p
[i
].qp
)));
1042 isl_pw_qpolynomial_free(pwqp
);
1047 __isl_give isl_pw_qpolynomial_fold
*isl_pw_qpolynomial_fold_add(
1048 __isl_take isl_pw_qpolynomial_fold
*pwf1
,
1049 __isl_take isl_pw_qpolynomial_fold
*pwf2
)
1051 return isl_pw_qpolynomial_fold_union_add_(pwf1
, pwf2
);
1054 /* Compare two quasi-polynomial reductions.
1056 * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater"
1057 * than "fold2" and 0 if they are equal.
1059 int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold
*fold1
,
1060 __isl_keep isl_qpolynomial_fold
*fold2
)
1071 if (fold1
->n
!= fold2
->n
)
1072 return fold1
->n
- fold2
->n
;
1074 for (i
= 0; i
< fold1
->n
; ++i
) {
1077 cmp
= isl_qpolynomial_plain_cmp(fold1
->qp
[i
], fold2
->qp
[i
]);
1085 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold
*fold1
,
1086 __isl_keep isl_qpolynomial_fold
*fold2
)
1090 if (!fold1
|| !fold2
)
1093 if (fold1
->n
!= fold2
->n
)
1096 /* We probably want to sort the qps first... */
1097 for (i
= 0; i
< fold1
->n
; ++i
) {
1098 int eq
= isl_qpolynomial_plain_is_equal(fold1
->qp
[i
], fold2
->qp
[i
]);
1106 __isl_give isl_val
*isl_qpolynomial_fold_eval(
1107 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_point
*pnt
)
1114 ctx
= isl_point_get_ctx(pnt
);
1115 isl_assert(pnt
->dim
->ctx
, isl_space_is_equal(pnt
->dim
, fold
->dim
), goto error
);
1116 isl_assert(pnt
->dim
->ctx
,
1117 fold
->type
== isl_fold_max
|| fold
->type
== isl_fold_min
,
1121 v
= isl_val_zero(ctx
);
1124 v
= isl_qpolynomial_eval(isl_qpolynomial_copy(fold
->qp
[0]),
1125 isl_point_copy(pnt
));
1126 for (i
= 1; i
< fold
->n
; ++i
) {
1128 v_i
= isl_qpolynomial_eval(
1129 isl_qpolynomial_copy(fold
->qp
[i
]),
1130 isl_point_copy(pnt
));
1131 if (fold
->type
== isl_fold_max
)
1132 v
= isl_val_max(v
, v_i
);
1134 v
= isl_val_min(v
, v_i
);
1137 isl_qpolynomial_fold_free(fold
);
1138 isl_point_free(pnt
);
1142 isl_qpolynomial_fold_free(fold
);
1143 isl_point_free(pnt
);
1147 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold
*pwf
)
1152 for (i
= 0; i
< pwf
->n
; ++i
)
1153 n
+= pwf
->p
[i
].fold
->n
;
1158 __isl_give isl_val
*isl_qpolynomial_fold_opt_on_domain(
1159 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_set
*set
, int max
)
1168 opt
= isl_val_zero(isl_set_get_ctx(set
));
1170 isl_qpolynomial_fold_free(fold
);
1174 opt
= isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold
->qp
[0]),
1175 isl_set_copy(set
), max
);
1176 for (i
= 1; i
< fold
->n
; ++i
) {
1178 opt_i
= isl_qpolynomial_opt_on_domain(
1179 isl_qpolynomial_copy(fold
->qp
[i
]),
1180 isl_set_copy(set
), max
);
1182 opt
= isl_val_max(opt
, opt_i
);
1184 opt
= isl_val_min(opt
, opt_i
);
1188 isl_qpolynomial_fold_free(fold
);
1193 isl_qpolynomial_fold_free(fold
);
1197 /* Check whether for each quasi-polynomial in "fold2" there is
1198 * a quasi-polynomial in "fold1" that dominates it on "set".
1200 static isl_bool
qpolynomial_fold_covers_on_domain(__isl_keep isl_set
*set
,
1201 __isl_keep isl_qpolynomial_fold
*fold1
,
1202 __isl_keep isl_qpolynomial_fold
*fold2
)
1207 if (!set
|| !fold1
|| !fold2
)
1208 return isl_bool_error
;
1210 covers
= fold1
->type
== isl_fold_max
? 1 : -1;
1212 for (i
= 0; i
< fold2
->n
; ++i
) {
1213 for (j
= 0; j
< fold1
->n
; ++j
) {
1217 d
= isl_qpolynomial_sub(
1218 isl_qpolynomial_copy(fold1
->qp
[j
]),
1219 isl_qpolynomial_copy(fold2
->qp
[i
]));
1220 sgn
= isl_qpolynomial_sign(set
, d
);
1221 isl_qpolynomial_free(d
);
1226 return isl_bool_false
;
1229 return isl_bool_true
;
1232 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1233 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1236 isl_bool
isl_pw_qpolynomial_fold_covers(
1237 __isl_keep isl_pw_qpolynomial_fold
*pwf1
,
1238 __isl_keep isl_pw_qpolynomial_fold
*pwf2
)
1241 isl_set
*dom1
, *dom2
;
1245 return isl_bool_error
;
1248 return isl_bool_true
;
1250 return isl_bool_false
;
1252 dom1
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1
));
1253 dom2
= isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2
));
1254 is_subset
= isl_set_is_subset(dom2
, dom1
);
1258 if (is_subset
< 0 || !is_subset
)
1261 for (i
= 0; i
< pwf2
->n
; ++i
) {
1262 for (j
= 0; j
< pwf1
->n
; ++j
) {
1267 common
= isl_set_intersect(isl_set_copy(pwf1
->p
[j
].set
),
1268 isl_set_copy(pwf2
->p
[i
].set
));
1269 is_empty
= isl_set_is_empty(common
);
1270 if (is_empty
< 0 || is_empty
) {
1271 isl_set_free(common
);
1273 return isl_bool_error
;
1276 covers
= qpolynomial_fold_covers_on_domain(common
,
1277 pwf1
->p
[j
].fold
, pwf2
->p
[i
].fold
);
1278 isl_set_free(common
);
1279 if (covers
< 0 || !covers
)
1284 return isl_bool_true
;
1287 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_morph_domain(
1288 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_morph
*morph
)
1293 if (!fold
|| !morph
)
1296 ctx
= fold
->dim
->ctx
;
1297 isl_assert(ctx
, isl_space_is_equal(fold
->dim
, morph
->dom
->dim
), goto error
);
1299 fold
= isl_qpolynomial_fold_cow(fold
);
1303 isl_space_free(fold
->dim
);
1304 fold
->dim
= isl_space_copy(morph
->ran
->dim
);
1308 for (i
= 0; i
< fold
->n
; ++i
) {
1309 fold
->qp
[i
] = isl_qpolynomial_morph_domain(fold
->qp
[i
],
1310 isl_morph_copy(morph
));
1315 isl_morph_free(morph
);
1319 isl_qpolynomial_fold_free(fold
);
1320 isl_morph_free(morph
);
1324 enum isl_fold
isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold
*fold
)
1327 return isl_fold_error
;
1331 /* Return the type of this piecewise quasipolynomial reduction.
1333 enum isl_fold
isl_pw_qpolynomial_fold_get_type(
1334 __isl_keep isl_pw_qpolynomial_fold
*pwf
)
1337 return isl_fold_error
;
1341 enum isl_fold
isl_union_pw_qpolynomial_fold_get_type(
1342 __isl_keep isl_union_pw_qpolynomial_fold
*upwf
)
1345 return isl_fold_error
;
1349 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_lift(
1350 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_space
*space
)
1354 if (!fold
|| !space
)
1357 if (isl_space_is_equal(fold
->dim
, space
)) {
1358 isl_space_free(space
);
1362 fold
= isl_qpolynomial_fold_cow(fold
);
1366 isl_space_free(fold
->dim
);
1367 fold
->dim
= isl_space_copy(space
);
1371 for (i
= 0; i
< fold
->n
; ++i
) {
1372 fold
->qp
[i
] = isl_qpolynomial_lift(fold
->qp
[i
],
1373 isl_space_copy(space
));
1378 isl_space_free(space
);
1382 isl_qpolynomial_fold_free(fold
);
1383 isl_space_free(space
);
1387 isl_stat
isl_qpolynomial_fold_foreach_qpolynomial(
1388 __isl_keep isl_qpolynomial_fold
*fold
,
1389 isl_stat (*fn
)(__isl_take isl_qpolynomial
*qp
, void *user
), void *user
)
1394 return isl_stat_error
;
1396 for (i
= 0; i
< fold
->n
; ++i
)
1397 if (fn(isl_qpolynomial_copy(fold
->qp
[i
]), user
) < 0)
1398 return isl_stat_error
;
1403 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_move_dims(
1404 __isl_take isl_qpolynomial_fold
*fold
,
1405 enum isl_dim_type dst_type
, unsigned dst_pos
,
1406 enum isl_dim_type src_type
, unsigned src_pos
, unsigned n
)
1409 enum isl_dim_type set_src_type
, set_dst_type
;
1414 fold
= isl_qpolynomial_fold_cow(fold
);
1418 set_src_type
= domain_type(src_type
);
1419 set_dst_type
= domain_type(dst_type
);
1421 fold
->dim
= isl_space_move_dims(fold
->dim
, set_dst_type
, dst_pos
,
1422 set_src_type
, src_pos
, n
);
1426 for (i
= 0; i
< fold
->n
; ++i
) {
1427 fold
->qp
[i
] = isl_qpolynomial_move_dims(fold
->qp
[i
],
1428 dst_type
, dst_pos
, src_type
, src_pos
, n
);
1435 isl_qpolynomial_fold_free(fold
);
1439 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1440 * in fold->qp[k] by subs[i].
1442 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_substitute(
1443 __isl_take isl_qpolynomial_fold
*fold
,
1444 enum isl_dim_type type
, unsigned first
, unsigned n
,
1445 __isl_keep isl_qpolynomial
**subs
)
1452 fold
= isl_qpolynomial_fold_cow(fold
);
1456 for (i
= 0; i
< fold
->n
; ++i
) {
1457 fold
->qp
[i
] = isl_qpolynomial_substitute(fold
->qp
[i
],
1458 type
, first
, n
, subs
);
1465 isl_qpolynomial_fold_free(fold
);
1469 static isl_stat
add_pwqp(__isl_take isl_pw_qpolynomial
*pwqp
, void *user
)
1471 isl_pw_qpolynomial_fold
*pwf
;
1472 isl_union_pw_qpolynomial_fold
**upwf
;
1473 struct isl_hash_table_entry
*entry
;
1475 upwf
= (isl_union_pw_qpolynomial_fold
**)user
;
1477 entry
= isl_union_pw_qpolynomial_fold_find_part_entry(*upwf
,
1482 pwf
= isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf
)->type
, pwqp
);
1486 entry
->data
= isl_pw_qpolynomial_fold_add(entry
->data
, pwf
);
1488 return isl_stat_error
;
1489 if (isl_pw_qpolynomial_fold_is_zero(entry
->data
))
1490 *upwf
= isl_union_pw_qpolynomial_fold_remove_part_entry(
1496 isl_pw_qpolynomial_free(pwqp
);
1497 return isl_stat_error
;
1500 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1501 __isl_take isl_union_pw_qpolynomial_fold
*upwf
,
1502 __isl_take isl_union_pw_qpolynomial
*upwqp
)
1504 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1505 isl_union_pw_qpolynomial_get_space(upwqp
));
1506 upwqp
= isl_union_pw_qpolynomial_align_params(upwqp
,
1507 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1509 upwf
= isl_union_pw_qpolynomial_fold_cow(upwf
);
1510 if (!upwf
|| !upwqp
)
1513 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp
, &add_pwqp
,
1517 isl_union_pw_qpolynomial_free(upwqp
);
1521 isl_union_pw_qpolynomial_fold_free(upwf
);
1522 isl_union_pw_qpolynomial_free(upwqp
);
1526 static isl_bool
join_compatible(__isl_keep isl_space
*space1
,
1527 __isl_keep isl_space
*space2
)
1530 m
= isl_space_has_equal_params(space1
, space2
);
1533 return isl_space_tuple_is_equal(space1
, isl_dim_out
,
1534 space2
, isl_dim_in
);
1537 /* Compute the intersection of the range of the map and the domain
1538 * of the piecewise quasipolynomial reduction and then compute a bound
1539 * on the associated quasipolynomial reduction over all elements
1540 * in this intersection.
1542 * We first introduce some unconstrained dimensions in the
1543 * piecewise quasipolynomial, intersect the resulting domain
1544 * with the wrapped map and the compute the sum.
1546 __isl_give isl_pw_qpolynomial_fold
*isl_map_apply_pw_qpolynomial_fold(
1547 __isl_take isl_map
*map
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1552 isl_space
*map_space
;
1553 isl_space
*pwf_space
;
1557 ctx
= isl_map_get_ctx(map
);
1561 map_space
= isl_map_get_space(map
);
1562 pwf_space
= isl_pw_qpolynomial_fold_get_space(pwf
);
1563 ok
= join_compatible(map_space
, pwf_space
);
1564 isl_space_free(map_space
);
1565 isl_space_free(pwf_space
);
1569 isl_die(ctx
, isl_error_invalid
, "incompatible dimensions",
1572 n_in
= isl_map_dim(map
, isl_dim_in
);
1575 pwf
= isl_pw_qpolynomial_fold_insert_dims(pwf
, isl_dim_in
, 0, n_in
);
1577 dom
= isl_map_wrap(map
);
1578 pwf
= isl_pw_qpolynomial_fold_reset_domain_space(pwf
,
1579 isl_set_get_space(dom
));
1581 pwf
= isl_pw_qpolynomial_fold_intersect_domain(pwf
, dom
);
1582 pwf
= isl_pw_qpolynomial_fold_bound(pwf
, tight
);
1587 isl_pw_qpolynomial_fold_free(pwf
);
1591 __isl_give isl_pw_qpolynomial_fold
*isl_set_apply_pw_qpolynomial_fold(
1592 __isl_take isl_set
*set
, __isl_take isl_pw_qpolynomial_fold
*pwf
,
1595 return isl_map_apply_pw_qpolynomial_fold(set
, pwf
, tight
);
1598 struct isl_apply_fold_data
{
1599 isl_union_pw_qpolynomial_fold
*upwf
;
1600 isl_union_pw_qpolynomial_fold
*res
;
1605 static isl_stat
pw_qpolynomial_fold_apply(
1606 __isl_take isl_pw_qpolynomial_fold
*pwf
, void *user
)
1610 struct isl_apply_fold_data
*data
= user
;
1613 map_dim
= isl_map_get_space(data
->map
);
1614 pwf_dim
= isl_pw_qpolynomial_fold_get_space(pwf
);
1615 ok
= join_compatible(map_dim
, pwf_dim
);
1616 isl_space_free(map_dim
);
1617 isl_space_free(pwf_dim
);
1620 return isl_stat_error
;
1622 pwf
= isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data
->map
),
1623 pwf
, data
->tight
? &data
->tight
: NULL
);
1624 data
->res
= isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1627 isl_pw_qpolynomial_fold_free(pwf
);
1632 static isl_stat
map_apply(__isl_take isl_map
*map
, void *user
)
1634 struct isl_apply_fold_data
*data
= user
;
1638 r
= isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1639 data
->upwf
, &pw_qpolynomial_fold_apply
, data
);
1645 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_map_apply_union_pw_qpolynomial_fold(
1646 __isl_take isl_union_map
*umap
,
1647 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, isl_bool
*tight
)
1651 struct isl_apply_fold_data data
;
1653 upwf
= isl_union_pw_qpolynomial_fold_align_params(upwf
,
1654 isl_union_map_get_space(umap
));
1655 umap
= isl_union_map_align_params(umap
,
1656 isl_union_pw_qpolynomial_fold_get_space(upwf
));
1659 data
.tight
= tight
? isl_bool_true
: isl_bool_false
;
1660 space
= isl_union_pw_qpolynomial_fold_get_space(upwf
);
1661 type
= isl_union_pw_qpolynomial_fold_get_type(upwf
);
1662 data
.res
= isl_union_pw_qpolynomial_fold_zero(space
, type
);
1663 if (isl_union_map_foreach_map(umap
, &map_apply
, &data
) < 0)
1666 isl_union_map_free(umap
);
1667 isl_union_pw_qpolynomial_fold_free(upwf
);
1670 *tight
= data
.tight
;
1674 isl_union_map_free(umap
);
1675 isl_union_pw_qpolynomial_fold_free(upwf
);
1676 isl_union_pw_qpolynomial_fold_free(data
.res
);
1680 __isl_give isl_union_pw_qpolynomial_fold
*isl_union_set_apply_union_pw_qpolynomial_fold(
1681 __isl_take isl_union_set
*uset
,
1682 __isl_take isl_union_pw_qpolynomial_fold
*upwf
, isl_bool
*tight
)
1684 return isl_union_map_apply_union_pw_qpolynomial_fold(uset
, upwf
, tight
);
1687 /* Reorder the dimension of "fold" according to the given reordering.
1689 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_realign_domain(
1690 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_reordering
*r
)
1695 fold
= isl_qpolynomial_fold_cow(fold
);
1699 for (i
= 0; i
< fold
->n
; ++i
) {
1700 fold
->qp
[i
] = isl_qpolynomial_realign_domain(fold
->qp
[i
],
1701 isl_reordering_copy(r
));
1706 space
= isl_reordering_get_space(r
);
1707 fold
= isl_qpolynomial_fold_reset_domain_space(fold
, space
);
1709 isl_reordering_free(r
);
1713 isl_qpolynomial_fold_free(fold
);
1714 isl_reordering_free(r
);
1718 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_mul_isl_int(
1719 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1723 if (isl_int_is_one(v
))
1725 if (fold
&& isl_int_is_zero(v
)) {
1726 isl_qpolynomial_fold
*zero
;
1727 isl_space
*space
= isl_space_copy(fold
->dim
);
1728 zero
= isl_qpolynomial_fold_empty(fold
->type
, space
);
1729 isl_qpolynomial_fold_free(fold
);
1733 fold
= isl_qpolynomial_fold_cow(fold
);
1737 if (isl_int_is_neg(v
))
1738 fold
->type
= isl_fold_type_negate(fold
->type
);
1739 for (i
= 0; i
< fold
->n
; ++i
) {
1740 fold
->qp
[i
] = isl_qpolynomial_mul_isl_int(fold
->qp
[i
], v
);
1747 isl_qpolynomial_fold_free(fold
);
1751 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale(
1752 __isl_take isl_qpolynomial_fold
*fold
, isl_int v
)
1754 return isl_qpolynomial_fold_mul_isl_int(fold
, v
);
1757 /* Multiply "fold" by "v".
1759 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale_val(
1760 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_val
*v
)
1767 if (isl_val_is_one(v
)) {
1771 if (isl_val_is_zero(v
)) {
1772 isl_qpolynomial_fold
*zero
;
1773 isl_space
*space
= isl_qpolynomial_fold_get_domain_space(fold
);
1774 zero
= isl_qpolynomial_fold_empty(fold
->type
, space
);
1775 isl_qpolynomial_fold_free(fold
);
1779 if (!isl_val_is_rat(v
))
1780 isl_die(isl_qpolynomial_fold_get_ctx(fold
), isl_error_invalid
,
1781 "expecting rational factor", goto error
);
1783 fold
= isl_qpolynomial_fold_cow(fold
);
1787 if (isl_val_is_neg(v
))
1788 fold
->type
= isl_fold_type_negate(fold
->type
);
1789 for (i
= 0; i
< fold
->n
; ++i
) {
1790 fold
->qp
[i
] = isl_qpolynomial_scale_val(fold
->qp
[i
],
1800 isl_qpolynomial_fold_free(fold
);
1804 /* Divide "fold" by "v".
1806 __isl_give isl_qpolynomial_fold
*isl_qpolynomial_fold_scale_down_val(
1807 __isl_take isl_qpolynomial_fold
*fold
, __isl_take isl_val
*v
)
1812 if (isl_val_is_one(v
)) {
1816 if (!isl_val_is_rat(v
))
1817 isl_die(isl_qpolynomial_fold_get_ctx(fold
), isl_error_invalid
,
1818 "expecting rational factor", goto error
);
1819 if (isl_val_is_zero(v
))
1820 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1821 "cannot scale down by zero", goto error
);
1823 return isl_qpolynomial_fold_scale_val(fold
, isl_val_inv(v
));
1826 isl_qpolynomial_fold_free(fold
);