2 #include <isl_set_polylib.h>
3 #include <isl/constraint.h>
4 #include <barvinok/evalue.h>
6 static __isl_give isl_qpolynomial
*extract_base(__isl_take isl_space
*dim
,
14 isl_qpolynomial
*base
, *c
;
20 if (e
->x
.p
->type
== polynomial
)
21 return isl_qpolynomial_var_on_domain(dim
, isl_dim_param
, e
->x
.p
->pos
- 1);
23 ctx
= isl_space_get_ctx(dim
);
24 nparam
= isl_space_dim(dim
, isl_dim_param
);
25 v
= Vector_Alloc(2 + nparam
);
29 for (i
= 0; i
< nparam
; ++i
)
30 value_set_si(v
->p
[2 + i
], 0);
31 evalue_extract_affine(&e
->x
.p
->arr
[0], v
->p
+ 2, &v
->p
[1], &v
->p
[0]);
33 ls
= isl_local_space_from_space(isl_space_copy(dim
));
34 aff
= isl_aff_zero_on_domain(ls
);
35 aff
= isl_aff_set_constant(aff
, v
->p
[1]);
36 aff
= isl_aff_set_denominator(aff
, v
->p
[0]);
38 for (i
= 0; i
< nparam
; ++i
)
39 aff
= isl_aff_set_coefficient(aff
, isl_dim_param
, i
,
42 aff
= isl_aff_floor(aff
);
43 base
= isl_qpolynomial_from_aff(aff
);
45 if (e
->x
.p
->type
== fractional
) {
46 base
= isl_qpolynomial_neg(base
);
48 c
= isl_qpolynomial_rat_cst_on_domain(isl_space_copy(dim
), v
->p
[1], v
->p
[0]);
49 base
= isl_qpolynomial_add(base
, c
);
51 for (i
= 0; i
< nparam
; ++i
) {
53 c
= isl_qpolynomial_rat_cst_on_domain(isl_space_copy(dim
),
54 v
->p
[2 + i
], v
->p
[0]);
55 t
= isl_qpolynomial_var_on_domain(isl_space_copy(dim
),
57 t
= isl_qpolynomial_mul(c
, t
);
58 base
= isl_qpolynomial_add(base
, t
);
71 static int type_offset(enode
*p
)
73 return p
->type
== fractional
? 1 :
74 p
->type
== flooring
? 1 : 0;
77 __isl_give isl_qpolynomial
*isl_qpolynomial_from_evalue(__isl_take isl_space
*dim
,
82 isl_qpolynomial
*base
;
85 if (EVALUE_IS_NAN(*e
))
86 return isl_qpolynomial_infty_on_domain(dim
);
87 if (value_notzero_p(e
->d
))
88 return isl_qpolynomial_rat_cst_on_domain(dim
, e
->x
.n
, e
->d
);
90 offset
= type_offset(e
->x
.p
);
92 assert(e
->x
.p
->type
== polynomial
||
93 e
->x
.p
->type
== flooring
||
94 e
->x
.p
->type
== fractional
);
95 assert(e
->x
.p
->size
>= 1 + offset
);
97 base
= extract_base(isl_space_copy(dim
), e
);
98 qp
= isl_qpolynomial_from_evalue(isl_space_copy(dim
),
99 &e
->x
.p
->arr
[e
->x
.p
->size
- 1]);
101 for (i
= e
->x
.p
->size
- 2; i
>= offset
; --i
) {
102 qp
= isl_qpolynomial_mul(qp
, isl_qpolynomial_copy(base
));
103 qp
= isl_qpolynomial_add(qp
,
104 isl_qpolynomial_from_evalue(isl_space_copy(dim
),
108 isl_qpolynomial_free(base
);
114 static __isl_give isl_pw_qpolynomial
*guarded_evalue2pwqp(__isl_take isl_set
*set
,
117 static __isl_give isl_pw_qpolynomial
*relation2pwqp(__isl_take isl_set
*set
,
125 isl_pw_qpolynomial
*pwqp
;
126 struct isl_constraint
*c
;
127 struct isl_basic_set
*bset
;
128 struct isl_set
*guard
;
134 if (e
->x
.p
->size
== 1) {
135 dim
= isl_set_get_space(set
);
137 return isl_pw_qpolynomial_zero(dim
);
140 ctx
= isl_set_get_ctx(set
);
141 isl_assert(ctx
, e
->x
.p
->size
> 0, goto error
);
142 isl_assert(ctx
, e
->x
.p
->size
<= 3, goto error
);
143 isl_assert(ctx
, value_zero_p(e
->x
.p
->arr
[0].d
), goto error
);
144 isl_assert(ctx
, e
->x
.p
->arr
[0].x
.p
->type
== fractional
, goto error
);
145 fract
= &e
->x
.p
->arr
[0];
147 nparam
= isl_set_dim(set
, isl_dim_param
);
148 vec
= Vector_Alloc(2 + nparam
+ 1);
152 for (i
= 0; i
< nparam
; ++i
)
153 value_set_si(vec
->p
[2 + i
], 0);
154 evalue_extract_affine(&fract
->x
.p
->arr
[0],
155 vec
->p
+ 2, &vec
->p
[1], &vec
->p
[0]);
157 dim
= isl_set_get_space(set
);
158 dim
= isl_space_add_dims(dim
, isl_dim_set
, 1);
160 bset
= isl_basic_set_universe(isl_space_copy(dim
));
161 c
= isl_equality_alloc(isl_local_space_from_space(dim
));
162 isl_int_neg(vec
->p
[0], vec
->p
[0]);
163 isl_constraint_set_coefficient(c
, isl_dim_set
, 0, vec
->p
[0]);
164 isl_constraint_set_constant(c
, vec
->p
[1]);
165 for (i
= 0; i
< nparam
; ++i
)
166 isl_constraint_set_coefficient(c
, isl_dim_param
, i
, vec
->p
[2+i
]);
167 bset
= isl_basic_set_add_constraint(bset
, c
);
168 bset
= isl_basic_set_params(bset
);
169 guard
= isl_set_from_basic_set(bset
);
172 pwqp
= guarded_evalue2pwqp(isl_set_intersect(isl_set_copy(set
),
173 isl_set_copy(guard
)),
176 if (e
->x
.p
->size
== 3) {
177 isl_pw_qpolynomial
*pwqpc
;
178 guard
= isl_set_complement(guard
);
179 pwqpc
= guarded_evalue2pwqp(isl_set_intersect(isl_set_copy(set
),
180 isl_set_copy(guard
)),
182 pwqp
= isl_pw_qpolynomial_add_disjoint(pwqp
, pwqpc
);
194 static __isl_give isl_pw_qpolynomial
*guarded_evalue2pwqp(__isl_take isl_set
*set
,
199 if (value_zero_p(e
->d
) && e
->x
.p
->type
== relation
)
200 return relation2pwqp(set
, e
);
202 qp
= isl_qpolynomial_from_evalue(isl_set_get_space(set
), e
);
204 return isl_pw_qpolynomial_alloc(set
, qp
);
207 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_from_evalue(__isl_take isl_space
*dim
, const evalue
*e
)
211 isl_pw_qpolynomial
*pwqp
;
215 if (EVALUE_IS_ZERO(*e
)) {
216 dim
= isl_space_from_domain(dim
);
217 dim
= isl_space_add_dims(dim
, isl_dim_out
, 1);
218 return isl_pw_qpolynomial_zero(dim
);
221 if (value_notzero_p(e
->d
)) {
222 isl_set
*set
= isl_set_universe(isl_space_copy(dim
));
223 isl_qpolynomial
*qp
= isl_qpolynomial_rat_cst_on_domain(dim
, e
->x
.n
, e
->d
);
224 return isl_pw_qpolynomial_alloc(set
, qp
);
227 assert(!EVALUE_IS_NAN(*e
));
229 assert(e
->x
.p
->type
== partition
);
231 pw_space
= isl_space_copy(dim
);
232 pw_space
= isl_space_from_domain(pw_space
);
233 pw_space
= isl_space_add_dims(pw_space
, isl_dim_out
, 1);
234 pwqp
= isl_pw_qpolynomial_zero(pw_space
);
236 for (i
= 0; i
< e
->x
.p
->size
/2; ++i
) {
237 Polyhedron
*D
= EVALUE_DOMAIN(e
->x
.p
->arr
[2 * i
]);
238 isl_set
*set
= isl_set_new_from_polylib(D
, isl_space_copy(dim
));
239 isl_pw_qpolynomial
*pwqp_i
;
241 pwqp_i
= guarded_evalue2pwqp(set
, &e
->x
.p
->arr
[2 * i
+ 1]);
243 pwqp
= isl_pw_qpolynomial_add_disjoint(pwqp
, pwqp_i
);
254 static evalue
*evalue_pow(evalue
*e
, int exp
)
270 static evalue
*div2evalue(__isl_take isl_aff
*div
)
283 if (isl_aff_dim(div
, isl_dim_div
) != 0)
284 isl_die(isl_aff_get_ctx(div
), isl_error_unsupported
,
285 "cannot handle nested divs", goto error
);
287 dim
= isl_aff_dim(div
, isl_dim_in
);
288 nparam
= isl_aff_dim(div
, isl_dim_param
);
290 ctx
= isl_aff_get_ctx(div
);
291 vec
= Vector_Alloc(1 + dim
+ nparam
+ 1);
294 for (i
= 0; i
< dim
; ++i
)
295 isl_aff_get_coefficient(div
, isl_dim_in
, i
, &vec
->p
[1 + i
]);
296 for (i
= 0; i
< nparam
; ++i
)
297 isl_aff_get_coefficient(div
, isl_dim_param
, i
,
298 &vec
->p
[1 + dim
+ i
]);
299 isl_aff_get_denominator(div
, &vec
->p
[0]);
300 isl_aff_get_constant(div
, &vec
->p
[1 + dim
+ nparam
]);
302 e
= isl_alloc_type(ctx
, evalue
);
306 value_set_si(e
->d
, 0);
307 e
->x
.p
= new_enode(flooring
, 3, -1);
308 evalue_set_si(&e
->x
.p
->arr
[1], 0, 1);
309 evalue_set_si(&e
->x
.p
->arr
[2], 1, 1);
310 value_clear(e
->x
.p
->arr
[0].d
);
311 aff
= affine2evalue(vec
->p
+ 1, vec
->p
[0], dim
+ nparam
);
312 e
->x
.p
->arr
[0] = *aff
;
323 static int add_term(__isl_take isl_term
*term
, void *user
)
326 evalue
*sum
= (evalue
*)user
;
337 nparam
= isl_term_dim(term
, isl_dim_param
);
338 dim
= isl_term_dim(term
, isl_dim_set
);
339 n_div
= isl_term_dim(term
, isl_dim_div
);
341 ctx
= isl_term_get_ctx(term
);
342 e
= isl_alloc_type(ctx
, evalue
);
349 isl_term_get_num(term
, &n
);
350 isl_term_get_den(term
, &d
);
354 for (i
= 0; i
< dim
; ++i
) {
356 int exp
= isl_term_get_exp(term
, isl_dim_set
, i
);
361 pow
= evalue_pow(evalue_var(i
), exp
);
366 for (i
= 0; i
< nparam
; ++i
) {
368 int exp
= isl_term_get_exp(term
, isl_dim_param
, i
);
373 pow
= evalue_pow(evalue_var(dim
+ i
), exp
);
378 for (i
= 0; i
< n_div
; ++i
) {
382 int exp
= isl_term_get_exp(term
, isl_dim_div
, i
);
387 div
= isl_term_get_div(term
, i
);
388 floor
= div2evalue(div
);
391 pow
= evalue_pow(floor
, exp
);
414 evalue
*isl_qpolynomial_to_evalue(__isl_keep isl_qpolynomial
*qp
)
422 if (isl_qpolynomial_foreach_term(qp
, add_term
, e
) < 0)
431 static int add_guarded_qp(__isl_take isl_set
*set
, __isl_take isl_qpolynomial
*qp
,
437 evalue
*sum
= (evalue
*)user
;
440 e
= isl_alloc_type(isl_set_get_ctx(set
), evalue
);
444 D
= isl_set_to_polylib(set
);
448 f
= isl_qpolynomial_to_evalue(qp
);
454 dim
= isl_set_dim(set
, isl_dim_param
) + isl_set_dim(set
, isl_dim_set
);
456 e
->x
.p
= new_enode(partition
, 2, D
->Dimension
);
457 EVALUE_SET_DOMAIN(e
->x
.p
->arr
[0], D
);
459 value_clear(e
->x
.p
->arr
[1].d
);
467 isl_qpolynomial_free(qp
);
473 isl_qpolynomial_free(qp
);
477 evalue
*isl_pw_qpolynomial_to_evalue(__isl_keep isl_pw_qpolynomial
*pwqp
)
485 if (isl_pw_qpolynomial_foreach_piece(pwqp
, add_guarded_qp
, e
))