2 #include <isl_set_polylib.h>
3 #include <isl/constraint.h>
4 #include <isl/val_gmp.h>
5 #include <barvinok/evalue.h>
7 static __isl_give isl_qpolynomial
*extract_base(__isl_take isl_space
*dim
,
16 isl_qpolynomial
*base
, *c
;
22 if (e
->x
.p
->type
== polynomial
)
23 return isl_qpolynomial_var_on_domain(dim
, isl_dim_param
, e
->x
.p
->pos
- 1);
25 ctx
= isl_space_get_ctx(dim
);
26 nparam
= isl_space_dim(dim
, isl_dim_param
);
27 v
= Vector_Alloc(2 + nparam
);
31 for (i
= 0; i
< nparam
; ++i
)
32 value_set_si(v
->p
[2 + i
], 0);
33 evalue_extract_affine(&e
->x
.p
->arr
[0], v
->p
+ 2, &v
->p
[1], &v
->p
[0]);
35 ls
= isl_local_space_from_space(isl_space_copy(dim
));
36 aff
= isl_aff_zero_on_domain(ls
);
37 val
= isl_val_int_from_gmp(ctx
, v
->p
[1]);
38 aff
= isl_aff_set_constant_val(aff
, val
);
40 for (i
= 0; i
< nparam
; ++i
) {
41 val
= isl_val_int_from_gmp(ctx
, v
->p
[2 + i
]);
42 aff
= isl_aff_set_coefficient_val(aff
, isl_dim_param
, i
, val
);
45 val
= isl_val_int_from_gmp(ctx
, v
->p
[0]);
46 aff
= isl_aff_scale_down_val(aff
, val
);
48 aff
= isl_aff_floor(aff
);
49 base
= isl_qpolynomial_from_aff(aff
);
51 if (e
->x
.p
->type
== fractional
) {
52 base
= isl_qpolynomial_neg(base
);
54 val
= isl_val_from_gmp(ctx
, v
->p
[1], v
->p
[0]);
55 c
= isl_qpolynomial_val_on_domain(isl_space_copy(dim
), val
);
56 base
= isl_qpolynomial_add(base
, c
);
58 for (i
= 0; i
< nparam
; ++i
) {
60 val
= isl_val_from_gmp(ctx
, v
->p
[2 + i
], v
->p
[0]);
61 c
= isl_qpolynomial_val_on_domain(isl_space_copy(dim
),
63 t
= isl_qpolynomial_var_on_domain(isl_space_copy(dim
),
65 t
= isl_qpolynomial_mul(c
, t
);
66 base
= isl_qpolynomial_add(base
, t
);
79 static int type_offset(enode
*p
)
81 return p
->type
== fractional
? 1 :
82 p
->type
== flooring
? 1 : 0;
85 __isl_give isl_qpolynomial
*isl_qpolynomial_from_evalue(__isl_take isl_space
*dim
,
90 isl_qpolynomial
*base
;
93 if (EVALUE_IS_NAN(*e
))
94 return isl_qpolynomial_infty_on_domain(dim
);
95 if (value_notzero_p(e
->d
)) {
96 isl_ctx
*ctx
= isl_space_get_ctx(dim
);
97 isl_val
*val
= isl_val_from_gmp(ctx
, e
->x
.n
, e
->d
);
98 return isl_qpolynomial_val_on_domain(dim
, val
);
101 offset
= type_offset(e
->x
.p
);
103 assert(e
->x
.p
->type
== polynomial
||
104 e
->x
.p
->type
== flooring
||
105 e
->x
.p
->type
== fractional
);
106 assert(e
->x
.p
->size
>= 1 + offset
);
108 base
= extract_base(isl_space_copy(dim
), e
);
109 qp
= isl_qpolynomial_from_evalue(isl_space_copy(dim
),
110 &e
->x
.p
->arr
[e
->x
.p
->size
- 1]);
112 for (i
= e
->x
.p
->size
- 2; i
>= offset
; --i
) {
113 qp
= isl_qpolynomial_mul(qp
, isl_qpolynomial_copy(base
));
114 qp
= isl_qpolynomial_add(qp
,
115 isl_qpolynomial_from_evalue(isl_space_copy(dim
),
119 isl_qpolynomial_free(base
);
125 static __isl_give isl_pw_qpolynomial
*guarded_evalue2pwqp(__isl_take isl_set
*set
,
128 static __isl_give isl_pw_qpolynomial
*relation2pwqp(__isl_take isl_set
*set
,
137 isl_pw_qpolynomial
*pwqp
;
138 struct isl_constraint
*c
;
139 struct isl_basic_set
*bset
;
140 struct isl_set
*guard
;
146 if (e
->x
.p
->size
== 1) {
147 dim
= isl_set_get_space(set
);
149 return isl_pw_qpolynomial_zero(dim
);
152 ctx
= isl_set_get_ctx(set
);
153 isl_assert(ctx
, e
->x
.p
->size
> 0, goto error
);
154 isl_assert(ctx
, e
->x
.p
->size
<= 3, goto error
);
155 isl_assert(ctx
, value_zero_p(e
->x
.p
->arr
[0].d
), goto error
);
156 isl_assert(ctx
, e
->x
.p
->arr
[0].x
.p
->type
== fractional
, goto error
);
157 fract
= &e
->x
.p
->arr
[0];
159 nparam
= isl_set_dim(set
, isl_dim_param
);
160 vec
= Vector_Alloc(2 + nparam
+ 1);
164 for (i
= 0; i
< nparam
; ++i
)
165 value_set_si(vec
->p
[2 + i
], 0);
166 evalue_extract_affine(&fract
->x
.p
->arr
[0],
167 vec
->p
+ 2, &vec
->p
[1], &vec
->p
[0]);
169 dim
= isl_set_get_space(set
);
170 dim
= isl_space_add_dims(dim
, isl_dim_set
, 1);
172 bset
= isl_basic_set_universe(isl_space_copy(dim
));
173 c
= isl_equality_alloc(isl_local_space_from_space(dim
));
174 v
= isl_val_int_from_gmp(ctx
, vec
->p
[0]);
176 c
= isl_constraint_set_coefficient_val(c
, isl_dim_set
, 0, v
);
177 v
= isl_val_int_from_gmp(ctx
, vec
->p
[1]);
178 c
= isl_constraint_set_constant_val(c
, v
);
179 for (i
= 0; i
< nparam
; ++i
) {
180 v
= isl_val_int_from_gmp(ctx
, vec
->p
[2 + i
]);
181 c
= isl_constraint_set_coefficient_val(c
, isl_dim_param
, i
, v
);
183 bset
= isl_basic_set_add_constraint(bset
, c
);
184 bset
= isl_basic_set_params(bset
);
185 guard
= isl_set_from_basic_set(bset
);
188 pwqp
= guarded_evalue2pwqp(isl_set_intersect(isl_set_copy(set
),
189 isl_set_copy(guard
)),
192 if (e
->x
.p
->size
== 3) {
193 isl_pw_qpolynomial
*pwqpc
;
194 guard
= isl_set_complement(guard
);
195 pwqpc
= guarded_evalue2pwqp(isl_set_intersect(isl_set_copy(set
),
196 isl_set_copy(guard
)),
198 pwqp
= isl_pw_qpolynomial_add_disjoint(pwqp
, pwqpc
);
210 static __isl_give isl_pw_qpolynomial
*guarded_evalue2pwqp(__isl_take isl_set
*set
,
215 if (value_zero_p(e
->d
) && e
->x
.p
->type
== relation
)
216 return relation2pwqp(set
, e
);
218 qp
= isl_qpolynomial_from_evalue(isl_set_get_space(set
), e
);
220 return isl_pw_qpolynomial_alloc(set
, qp
);
223 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_from_evalue(__isl_take isl_space
*dim
, const evalue
*e
)
227 isl_pw_qpolynomial
*pwqp
;
231 if (EVALUE_IS_ZERO(*e
)) {
232 dim
= isl_space_from_domain(dim
);
233 dim
= isl_space_add_dims(dim
, isl_dim_out
, 1);
234 return isl_pw_qpolynomial_zero(dim
);
237 if (value_notzero_p(e
->d
)) {
238 isl_set
*set
= isl_set_universe(isl_space_copy(dim
));
239 isl_qpolynomial
*qp
= isl_qpolynomial_rat_cst_on_domain(dim
, e
->x
.n
, e
->d
);
240 return isl_pw_qpolynomial_alloc(set
, qp
);
243 assert(!EVALUE_IS_NAN(*e
));
245 assert(e
->x
.p
->type
== partition
);
247 pw_space
= isl_space_copy(dim
);
248 pw_space
= isl_space_from_domain(pw_space
);
249 pw_space
= isl_space_add_dims(pw_space
, isl_dim_out
, 1);
250 pwqp
= isl_pw_qpolynomial_zero(pw_space
);
252 for (i
= 0; i
< e
->x
.p
->size
/2; ++i
) {
253 Polyhedron
*D
= EVALUE_DOMAIN(e
->x
.p
->arr
[2 * i
]);
254 isl_set
*set
= isl_set_new_from_polylib(D
, isl_space_copy(dim
));
255 isl_pw_qpolynomial
*pwqp_i
;
257 pwqp_i
= guarded_evalue2pwqp(set
, &e
->x
.p
->arr
[2 * i
+ 1]);
259 pwqp
= isl_pw_qpolynomial_add_disjoint(pwqp
, pwqp_i
);
270 static evalue
*evalue_pow(evalue
*e
, int exp
)
286 static evalue
*div2evalue(__isl_take isl_aff
*div
)
299 if (isl_aff_dim(div
, isl_dim_div
) != 0)
300 isl_die(isl_aff_get_ctx(div
), isl_error_unsupported
,
301 "cannot handle nested divs", goto error
);
303 dim
= isl_aff_dim(div
, isl_dim_in
);
304 nparam
= isl_aff_dim(div
, isl_dim_param
);
306 ctx
= isl_aff_get_ctx(div
);
307 vec
= Vector_Alloc(1 + dim
+ nparam
+ 1);
310 for (i
= 0; i
< dim
; ++i
)
311 isl_aff_get_coefficient(div
, isl_dim_in
, i
, &vec
->p
[1 + i
]);
312 for (i
= 0; i
< nparam
; ++i
)
313 isl_aff_get_coefficient(div
, isl_dim_param
, i
,
314 &vec
->p
[1 + dim
+ i
]);
315 isl_aff_get_denominator(div
, &vec
->p
[0]);
316 isl_aff_get_constant(div
, &vec
->p
[1 + dim
+ nparam
]);
318 e
= isl_alloc_type(ctx
, evalue
);
322 value_set_si(e
->d
, 0);
323 e
->x
.p
= new_enode(flooring
, 3, -1);
324 evalue_set_si(&e
->x
.p
->arr
[1], 0, 1);
325 evalue_set_si(&e
->x
.p
->arr
[2], 1, 1);
326 value_clear(e
->x
.p
->arr
[0].d
);
327 aff
= affine2evalue(vec
->p
+ 1, vec
->p
[0], dim
+ nparam
);
328 e
->x
.p
->arr
[0] = *aff
;
339 static int add_term(__isl_take isl_term
*term
, void *user
)
342 evalue
*sum
= (evalue
*)user
;
354 nparam
= isl_term_dim(term
, isl_dim_param
);
355 dim
= isl_term_dim(term
, isl_dim_set
);
356 n_div
= isl_term_dim(term
, isl_dim_div
);
358 ctx
= isl_term_get_ctx(term
);
359 e
= isl_alloc_type(ctx
, evalue
);
366 v
= isl_term_get_coefficient_val(term
);
367 isl_val_get_num_gmp(v
, n
);
368 isl_val_get_den_gmp(v
, d
);
375 for (i
= 0; i
< dim
; ++i
) {
377 int exp
= isl_term_get_exp(term
, isl_dim_set
, i
);
382 pow
= evalue_pow(evalue_var(i
), exp
);
387 for (i
= 0; i
< nparam
; ++i
) {
389 int exp
= isl_term_get_exp(term
, isl_dim_param
, i
);
394 pow
= evalue_pow(evalue_var(dim
+ i
), exp
);
399 for (i
= 0; i
< n_div
; ++i
) {
403 int exp
= isl_term_get_exp(term
, isl_dim_div
, i
);
408 div
= isl_term_get_div(term
, i
);
409 floor
= div2evalue(div
);
412 pow
= evalue_pow(floor
, exp
);
435 evalue
*isl_qpolynomial_to_evalue(__isl_keep isl_qpolynomial
*qp
)
443 if (isl_qpolynomial_foreach_term(qp
, add_term
, e
) < 0)
452 static int add_guarded_qp(__isl_take isl_set
*set
, __isl_take isl_qpolynomial
*qp
,
458 evalue
*sum
= (evalue
*)user
;
461 e
= isl_alloc_type(isl_set_get_ctx(set
), evalue
);
465 D
= isl_set_to_polylib(set
);
469 f
= isl_qpolynomial_to_evalue(qp
);
475 dim
= isl_set_dim(set
, isl_dim_param
) + isl_set_dim(set
, isl_dim_set
);
477 e
->x
.p
= new_enode(partition
, 2, D
->Dimension
);
478 EVALUE_SET_DOMAIN(e
->x
.p
->arr
[0], D
);
480 value_clear(e
->x
.p
->arr
[1].d
);
488 isl_qpolynomial_free(qp
);
494 isl_qpolynomial_free(qp
);
498 evalue
*isl_pw_qpolynomial_to_evalue(__isl_keep isl_pw_qpolynomial
*pwqp
)
506 if (isl_pw_qpolynomial_foreach_piece(pwqp
, add_guarded_qp
, e
))