2 * Copyright 2012-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
14 #include <isl/space.h>
15 #include <isl/constraint.h>
18 #include <isl_ast_build_expr.h>
19 #include <isl_ast_private.h>
20 #include <isl_ast_build_private.h>
23 /* Compute the "opposite" of the (numerator of the) argument of a div
24 * with denominator "d".
26 * In particular, compute
30 static __isl_give isl_aff
*oppose_div_arg(__isl_take isl_aff
*aff
,
31 __isl_take isl_val
*d
)
33 aff
= isl_aff_neg(aff
);
34 aff
= isl_aff_add_constant_val(aff
, d
);
35 aff
= isl_aff_add_constant_si(aff
, -1);
40 /* Internal data structure used inside isl_ast_expr_add_term.
41 * The domain of "build" is used to simplify the expressions.
42 * "build" needs to be set by the caller of isl_ast_expr_add_term.
43 * "cst" is the constant term of the expression in which the added term
44 * appears. It may be modified by isl_ast_expr_add_term.
46 * "v" is the coefficient of the term that is being constructed and
47 * is set internally by isl_ast_expr_add_term.
49 struct isl_ast_add_term_data
{
55 /* Given the numerator "aff" of the argument of an integer division
56 * with denominator "d", check if it can be made non-negative over
57 * data->build->domain by stealing part of the constant term of
58 * the expression in which the integer division appears.
60 * In particular, the outer expression is of the form
62 * v * floor(aff/d) + cst
64 * We already know that "aff" itself may attain negative values.
65 * Here we check if aff + d*floor(cst/v) is non-negative, such
66 * that we could rewrite the expression to
68 * v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
70 * Note that aff + d*floor(cst/v) can only possibly be non-negative
71 * if data->cst and data->v have the same sign.
72 * Similarly, if floor(cst/v) is zero, then there is no point in
75 static isl_bool
is_non_neg_after_stealing(__isl_keep isl_aff
*aff
,
76 __isl_keep isl_val
*d
, struct isl_ast_add_term_data
*data
)
83 if (isl_val_sgn(data
->cst
) != isl_val_sgn(data
->v
))
84 return isl_bool_false
;
86 shift
= isl_val_div(isl_val_copy(data
->cst
), isl_val_copy(data
->v
));
87 shift
= isl_val_floor(shift
);
88 is_zero
= isl_val_is_zero(shift
);
89 if (is_zero
< 0 || is_zero
) {
91 return isl_bool_not(is_zero
);
93 shift
= isl_val_mul(shift
, isl_val_copy(d
));
94 shifted
= isl_aff_copy(aff
);
95 shifted
= isl_aff_add_constant_val(shifted
, shift
);
96 non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, shifted
);
97 isl_aff_free(shifted
);
102 /* Given the numerator "aff" of the argument of an integer division
103 * with denominator "d", steal part of the constant term of
104 * the expression in which the integer division appears to make it
105 * non-negative over data->build->domain.
107 * In particular, the outer expression is of the form
109 * v * floor(aff/d) + cst
111 * We know that "aff" itself may attain negative values,
112 * but that aff + d*floor(cst/v) is non-negative.
113 * Find the minimal positive value that we need to add to "aff"
114 * to make it positive and adjust data->cst accordingly.
115 * That is, compute the minimal value "m" of "aff" over
116 * data->build->domain and take
124 * and rewrite the expression to
126 * v * floor((aff + s*d)/d) + (cst - v*s)
128 static __isl_give isl_aff
*steal_from_cst(__isl_take isl_aff
*aff
,
129 __isl_keep isl_val
*d
, struct isl_ast_add_term_data
*data
)
134 domain
= isl_ast_build_get_domain(data
->build
);
135 shift
= isl_set_min_val(domain
, aff
);
136 isl_set_free(domain
);
138 shift
= isl_val_neg(shift
);
139 shift
= isl_val_div(shift
, isl_val_copy(d
));
140 shift
= isl_val_ceil(shift
);
142 t
= isl_val_copy(shift
);
143 t
= isl_val_mul(t
, isl_val_copy(data
->v
));
144 data
->cst
= isl_val_sub(data
->cst
, t
);
146 shift
= isl_val_mul(shift
, isl_val_copy(d
));
147 return isl_aff_add_constant_val(aff
, shift
);
150 /* Construct an expression representing the binary operation "type"
151 * (some division or modulo) applied to the expressions
152 * constructed from "aff" and "v".
154 static __isl_give isl_ast_expr
*div_mod(enum isl_ast_expr_op_type type
,
155 __isl_take isl_aff
*aff
, __isl_take isl_val
*v
,
156 __isl_keep isl_ast_build
*build
)
158 isl_ast_expr
*expr1
, *expr2
;
160 expr1
= isl_ast_expr_from_aff(aff
, build
);
161 expr2
= isl_ast_expr_from_val(v
);
162 return isl_ast_expr_alloc_binary(type
, expr1
, expr2
);
165 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
166 * The result is simplified in terms of data->build->domain.
167 * This function may change (the sign of) data->v.
169 * "ls" is known to be non-NULL.
171 * Let the div be of the form floor(e/d).
172 * If the ast_build_prefer_pdiv option is set then we check if "e"
173 * is non-negative, so that we can generate
175 * (pdiv_q, expr(e), expr(d))
179 * (fdiv_q, expr(e), expr(d))
181 * If the ast_build_prefer_pdiv option is set and
182 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
183 * If so, we can rewrite
185 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
187 * and still use pdiv_q, while changing the sign of data->v.
189 * Otherwise, we check if
193 * is non-negative and if so, replace floor(e/d) by
195 * floor((e + s*d)/d) - s
197 * with s the minimal shift that makes the argument non-negative.
199 static __isl_give isl_ast_expr
*var_div(struct isl_ast_add_term_data
*data
,
200 __isl_keep isl_local_space
*ls
, int pos
)
202 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
205 enum isl_ast_expr_op_type type
;
207 aff
= isl_local_space_get_div(ls
, pos
);
208 d
= isl_aff_get_denominator_val(aff
);
209 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
211 type
= isl_ast_expr_op_fdiv_q
;
212 if (isl_options_get_ast_build_prefer_pdiv(ctx
)) {
214 non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, aff
);
215 if (non_neg
>= 0 && !non_neg
) {
216 isl_aff
*opp
= oppose_div_arg(isl_aff_copy(aff
),
218 non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, opp
);
219 if (non_neg
>= 0 && non_neg
) {
220 data
->v
= isl_val_neg(data
->v
);
226 if (non_neg
>= 0 && !non_neg
) {
227 non_neg
= is_non_neg_after_stealing(aff
, d
, data
);
228 if (non_neg
>= 0 && non_neg
)
229 aff
= steal_from_cst(aff
, d
, data
);
232 aff
= isl_aff_free(aff
);
234 type
= isl_ast_expr_op_pdiv_q
;
237 return div_mod(type
, aff
, d
, data
->build
);
240 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
241 * The result is simplified in terms of data->build->domain.
242 * This function may change (the sign of) data->v.
244 * The isl_ast_expr is constructed based on the type of the dimension.
245 * - divs are constructed by var_div
246 * - set variables are constructed from the iterator isl_ids in data->build
247 * - parameters are constructed from the isl_ids in "ls"
249 static __isl_give isl_ast_expr
*var(struct isl_ast_add_term_data
*data
,
250 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
)
252 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
255 if (type
== isl_dim_div
)
256 return var_div(data
, ls
, pos
);
258 if (type
== isl_dim_set
) {
259 id
= isl_ast_build_get_iterator_id(data
->build
, pos
);
260 return isl_ast_expr_from_id(id
);
263 if (!isl_local_space_has_dim_id(ls
, type
, pos
))
264 isl_die(ctx
, isl_error_internal
, "unnamed dimension",
266 id
= isl_local_space_get_dim_id(ls
, type
, pos
);
267 return isl_ast_expr_from_id(id
);
270 /* Does "expr" represent the zero integer?
272 static isl_bool
ast_expr_is_zero(__isl_keep isl_ast_expr
*expr
)
275 return isl_bool_error
;
276 if (expr
->type
!= isl_ast_expr_int
)
277 return isl_bool_false
;
278 return isl_val_is_zero(expr
->u
.v
);
281 /* Create an expression representing the sum of "expr1" and "expr2",
282 * provided neither of the two expressions is identically zero.
284 static __isl_give isl_ast_expr
*ast_expr_add(__isl_take isl_ast_expr
*expr1
,
285 __isl_take isl_ast_expr
*expr2
)
287 if (!expr1
|| !expr2
)
290 if (ast_expr_is_zero(expr1
)) {
291 isl_ast_expr_free(expr1
);
295 if (ast_expr_is_zero(expr2
)) {
296 isl_ast_expr_free(expr2
);
300 return isl_ast_expr_add(expr1
, expr2
);
302 isl_ast_expr_free(expr1
);
303 isl_ast_expr_free(expr2
);
307 /* Subtract expr2 from expr1.
309 * If expr2 is zero, we simply return expr1.
310 * If expr1 is zero, we return
312 * (isl_ast_expr_op_minus, expr2)
314 * Otherwise, we return
316 * (isl_ast_expr_op_sub, expr1, expr2)
318 static __isl_give isl_ast_expr
*ast_expr_sub(__isl_take isl_ast_expr
*expr1
,
319 __isl_take isl_ast_expr
*expr2
)
321 if (!expr1
|| !expr2
)
324 if (ast_expr_is_zero(expr2
)) {
325 isl_ast_expr_free(expr2
);
329 if (ast_expr_is_zero(expr1
)) {
330 isl_ast_expr_free(expr1
);
331 return isl_ast_expr_neg(expr2
);
334 return isl_ast_expr_sub(expr1
, expr2
);
336 isl_ast_expr_free(expr1
);
337 isl_ast_expr_free(expr2
);
341 /* Return an isl_ast_expr that represents
345 * v is assumed to be non-negative.
346 * The result is simplified in terms of build->domain.
348 static __isl_give isl_ast_expr
*isl_ast_expr_mod(__isl_keep isl_val
*v
,
349 __isl_keep isl_aff
*aff
, __isl_keep isl_val
*d
,
350 __isl_keep isl_ast_build
*build
)
358 expr
= div_mod(isl_ast_expr_op_pdiv_r
,
359 isl_aff_copy(aff
), isl_val_copy(d
), build
);
361 if (!isl_val_is_one(v
)) {
362 c
= isl_ast_expr_from_val(isl_val_copy(v
));
363 expr
= isl_ast_expr_mul(c
, expr
);
369 /* Create an isl_ast_expr that scales "expr" by "v".
371 * If v is 1, we simply return expr.
372 * If v is -1, we return
374 * (isl_ast_expr_op_minus, expr)
376 * Otherwise, we return
378 * (isl_ast_expr_op_mul, expr(v), expr)
380 static __isl_give isl_ast_expr
*scale(__isl_take isl_ast_expr
*expr
,
381 __isl_take isl_val
*v
)
387 if (isl_val_is_one(v
)) {
392 if (isl_val_is_negone(v
)) {
394 expr
= isl_ast_expr_neg(expr
);
396 c
= isl_ast_expr_from_val(v
);
397 expr
= isl_ast_expr_mul(c
, expr
);
403 isl_ast_expr_free(expr
);
407 /* Add an expression for "*v" times the specified dimension of "ls"
409 * If the dimension is an integer division, then this function
410 * may modify data->cst in order to make the numerator non-negative.
411 * The result is simplified in terms of data->build->domain.
413 * Let e be the expression for the specified dimension,
414 * multiplied by the absolute value of "*v".
415 * If "*v" is negative, we create
417 * (isl_ast_expr_op_sub, expr, e)
419 * except when expr is trivially zero, in which case we create
421 * (isl_ast_expr_op_minus, e)
425 * If "*v" is positive, we simply create
427 * (isl_ast_expr_op_add, expr, e)
430 static __isl_give isl_ast_expr
*isl_ast_expr_add_term(
431 __isl_take isl_ast_expr
*expr
,
432 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
,
433 __isl_take isl_val
*v
, struct isl_ast_add_term_data
*data
)
441 term
= var(data
, ls
, type
, pos
);
444 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
446 term
= scale(term
, v
);
447 return ast_expr_sub(expr
, term
);
449 term
= scale(term
, v
);
450 return ast_expr_add(expr
, term
);
454 /* Add an expression for "v" to expr.
456 static __isl_give isl_ast_expr
*isl_ast_expr_add_int(
457 __isl_take isl_ast_expr
*expr
, __isl_take isl_val
*v
)
459 isl_ast_expr
*expr_int
;
464 if (isl_val_is_zero(v
)) {
469 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
471 expr_int
= isl_ast_expr_from_val(v
);
472 return ast_expr_sub(expr
, expr_int
);
474 expr_int
= isl_ast_expr_from_val(v
);
475 return ast_expr_add(expr
, expr_int
);
478 isl_ast_expr_free(expr
);
483 /* Internal data structure used inside extract_modulos.
485 * If any modulo expressions are detected in "aff", then the
486 * expression is removed from "aff" and added to either "pos" or "neg"
487 * depending on the sign of the coefficient of the modulo expression
490 * "add" is an expression that needs to be added to "aff" at the end of
491 * the computation. It is NULL as long as no modulos have been extracted.
493 * "i" is the position in "aff" of the div under investigation
494 * "v" is the coefficient in "aff" of the div
495 * "div" is the argument of the div, with the denominator removed
496 * "d" is the original denominator of the argument of the div
498 * "nonneg" is an affine expression that is non-negative over "build"
499 * and that can be used to extract a modulo expression from "div".
500 * In particular, if "sign" is 1, then the coefficients of "nonneg"
501 * are equal to those of "div" modulo "d". If "sign" is -1, then
502 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
503 * If "sign" is 0, then no such affine expression has been found (yet).
505 struct isl_extract_mod_data
{
506 isl_ast_build
*build
;
527 * represent (a special case of) a test for some linear expression
530 * In particular, is it of the form
536 static isl_bool
is_even_test(struct isl_extract_mod_data
*data
,
537 __isl_keep isl_aff
*arg
)
542 res
= isl_val_eq_si(data
->d
, 2);
546 cst
= isl_aff_get_constant_val(arg
);
547 res
= isl_val_eq_si(cst
, -1);
553 /* Given that data->v * div_i in data->aff is equal to
555 * f * (term - (arg mod d))
557 * with data->d * f = data->v and "arg" non-negative on data->build, add
563 * abs(f) * (arg mod d)
565 * to data->neg or data->pos depending on the sign of -f.
567 * In the special case that "arg mod d" is of the form "(lin - 1) mod 2",
568 * with "lin" some linear expression, first replace
570 * f * (term - ((lin - 1) mod 2))
574 * -f * (1 - term - (lin mod 2))
576 * These two are equal because
578 * ((lin - 1) mod 2) + (lin mod 2) = 1
580 * Also, if "lin - 1" is non-negative, then "lin" is non-negative too.
582 static isl_stat
extract_term_and_mod(struct isl_extract_mod_data
*data
,
583 __isl_take isl_aff
*term
, __isl_take isl_aff
*arg
)
589 even
= is_even_test(data
, arg
);
591 arg
= isl_aff_free(arg
);
593 term
= oppose_div_arg(term
, isl_val_copy(data
->d
));
594 data
->v
= isl_val_neg(data
->v
);
595 arg
= isl_aff_set_constant_si(arg
, 0);
598 data
->v
= isl_val_div(data
->v
, isl_val_copy(data
->d
));
599 s
= isl_val_sgn(data
->v
);
600 data
->v
= isl_val_abs(data
->v
);
601 expr
= isl_ast_expr_mod(data
->v
, arg
, data
->d
, data
->build
);
604 data
->neg
= ast_expr_add(data
->neg
, expr
);
606 data
->pos
= ast_expr_add(data
->pos
, expr
);
607 data
->aff
= isl_aff_set_coefficient_si(data
->aff
,
608 isl_dim_div
, data
->i
, 0);
610 data
->v
= isl_val_neg(data
->v
);
611 term
= isl_aff_scale_val(term
, isl_val_copy(data
->v
));
616 data
->add
= isl_aff_add(data
->add
, term
);
618 return isl_stat_error
;
623 /* Given that data->v * div_i in data->aff is of the form
625 * f * d * floor(div/d)
627 * with div nonnegative on data->build, rewrite it as
629 * f * (div - (div mod d)) = f * div - f * (div mod d)
637 * abs(f) * (div mod d)
639 * to data->neg or data->pos depending on the sign of -f.
641 static isl_stat
extract_mod(struct isl_extract_mod_data
*data
)
643 return extract_term_and_mod(data
, isl_aff_copy(data
->div
),
644 isl_aff_copy(data
->div
));
647 /* Given that data->v * div_i in data->aff is of the form
649 * f * d * floor(div/d) (1)
651 * check if div is non-negative on data->build and, if so,
652 * extract the corresponding modulo from data->aff.
653 * If not, then check if
657 * is non-negative on data->build. If so, replace (1) by
659 * -f * d * floor((-div + d - 1)/d)
661 * and extract the corresponding modulo from data->aff.
663 * This function may modify data->div.
665 static isl_stat
extract_nonneg_mod(struct isl_extract_mod_data
*data
)
669 mod
= isl_ast_build_aff_is_nonneg(data
->build
, data
->div
);
673 return extract_mod(data
);
675 data
->div
= oppose_div_arg(data
->div
, isl_val_copy(data
->d
));
676 mod
= isl_ast_build_aff_is_nonneg(data
->build
, data
->div
);
680 data
->v
= isl_val_neg(data
->v
);
681 return extract_mod(data
);
686 data
->aff
= isl_aff_free(data
->aff
);
687 return isl_stat_error
;
690 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
691 * for use in extracting a modulo expression?
693 * We currently only consider the constant term of the affine expression.
694 * In particular, we prefer the affine expression with the smallest constant
696 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
697 * then we would pick x >= 0
699 * More detailed heuristics could be used if it turns out that there is a need.
701 static int mod_constraint_is_simpler(struct isl_extract_mod_data
*data
,
702 __isl_keep isl_constraint
*c
)
710 v1
= isl_val_abs(isl_constraint_get_constant_val(c
));
711 v2
= isl_val_abs(isl_aff_get_constant_val(data
->nonneg
));
712 simpler
= isl_val_lt(v1
, v2
);
719 /* Check if the coefficients of "c" are either equal or opposite to those
720 * of data->div modulo data->d. If so, and if "c" is "simpler" than
721 * data->nonneg, then replace data->nonneg by the affine expression of "c"
722 * and set data->sign accordingly.
724 * Both "c" and data->div are assumed not to involve any integer divisions.
726 * Before we start the actual comparison, we first quickly check if
727 * "c" and data->div have the same non-zero coefficients.
728 * If not, then we assume that "c" is not of the desired form.
729 * Note that while the coefficients of data->div can be reasonably expected
730 * not to involve any coefficients that are multiples of d, "c" may
731 * very well involve such coefficients. This means that we may actually
734 * If the constant term is "too large", then the constraint is rejected,
735 * where "too large" is fairly arbitrarily set to 1 << 15.
736 * We do this to avoid picking up constraints that bound a variable
737 * by a very large number, say the largest or smallest possible
738 * variable in the representation of some integer type.
740 static isl_stat
check_parallel_or_opposite(__isl_take isl_constraint
*c
,
743 struct isl_extract_mod_data
*data
= user
;
744 enum isl_dim_type c_type
[2] = { isl_dim_param
, isl_dim_set
};
745 enum isl_dim_type a_type
[2] = { isl_dim_param
, isl_dim_in
};
748 isl_bool parallel
= isl_bool_true
, opposite
= isl_bool_true
;
750 for (t
= 0; t
< 2; ++t
) {
751 n
[t
] = isl_constraint_dim(c
, c_type
[t
]);
754 for (i
= 0; i
< n
[t
]; ++i
) {
757 a
= isl_constraint_involves_dims(c
, c_type
[t
], i
, 1);
758 b
= isl_aff_involves_dims(data
->div
, a_type
[t
], i
, 1);
762 parallel
= opposite
= isl_bool_false
;
766 if (parallel
|| opposite
) {
769 v
= isl_val_abs(isl_constraint_get_constant_val(c
));
770 if (isl_val_cmp_si(v
, 1 << 15) > 0)
771 parallel
= opposite
= isl_bool_false
;
775 for (t
= 0; t
< 2; ++t
) {
776 for (i
= 0; i
< n
[t
]; ++i
) {
779 if (!parallel
&& !opposite
)
781 v1
= isl_constraint_get_coefficient_val(c
,
783 v2
= isl_aff_get_coefficient_val(data
->div
,
786 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
787 parallel
= isl_val_is_divisible_by(v1
, data
->d
);
788 v1
= isl_val_add(v1
, isl_val_copy(v2
));
791 v1
= isl_val_add(v1
, isl_val_copy(v2
));
792 opposite
= isl_val_is_divisible_by(v1
, data
->d
);
796 if (parallel
< 0 || opposite
< 0)
801 if ((parallel
|| opposite
) && mod_constraint_is_simpler(data
, c
)) {
802 isl_aff_free(data
->nonneg
);
803 data
->nonneg
= isl_constraint_get_aff(c
);
804 data
->sign
= parallel
? 1 : -1;
807 isl_constraint_free(c
);
809 if (data
->sign
!= 0 && data
->nonneg
== NULL
)
810 return isl_stat_error
;
814 isl_constraint_free(c
);
815 return isl_stat_error
;
818 /* Given that data->v * div_i in data->aff is of the form
820 * f * d * floor(div/d) (1)
822 * see if we can find an expression div' that is non-negative over data->build
823 * and that is related to div through
829 * div' = -div + d - 1 + d * e
831 * with e some affine expression.
832 * If so, we write (1) as
834 * f * div + f * (div' mod d)
838 * -f * (-div + d - 1) - f * (div' mod d)
840 * exploiting (in the second case) the fact that
842 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
845 * We first try to find an appropriate expression for div'
846 * from the constraints of data->build->domain (which is therefore
847 * guaranteed to be non-negative on data->build), where we remove
848 * any integer divisions from the constraints and skip this step
849 * if "div" itself involves any integer divisions.
850 * If we cannot find an appropriate expression this way, then
851 * we pass control to extract_nonneg_mod where check
852 * if div or "-div + d -1" themselves happen to be
853 * non-negative on data->build.
855 * While looking for an appropriate constraint in data->build->domain,
856 * we ignore the constant term, so after finding such a constraint,
857 * we still need to fix up the constant term.
858 * In particular, if a is the constant term of "div"
859 * (or d - 1 - the constant term of "div" if data->sign < 0)
860 * and b is the constant term of the constraint, then we need to find
861 * a non-negative constant c such that
863 * b + c \equiv a mod d
869 * and add it to b to obtain the constant term of div'.
870 * If this constant term is "too negative", then we add an appropriate
871 * multiple of d to make it positive.
874 * Note that the above is only a very simple heuristic for finding an
875 * appropriate expression. We could try a bit harder by also considering
876 * sums of constraints that involve disjoint sets of variables or
877 * we could consider arbitrary linear combinations of constraints,
878 * although that could potentially be much more expensive as it involves
879 * the solution of an LP problem.
881 * In particular, if v_i is a column vector representing constraint i,
882 * w represents div and e_i is the i-th unit vector, then we are looking
883 * for a solution of the constraints
885 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
887 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
888 * If we are not just interested in a non-negative expression, but
889 * also in one with a minimal range, then we don't just want
890 * c = \sum_i lambda_i v_i to be non-negative over the domain,
891 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
892 * that we want to minimize and we now also have to take into account
893 * the constant terms of the constraints.
894 * Alternatively, we could first compute the dual of the domain
895 * and plug in the constraints on the coefficients.
897 static isl_stat
try_extract_mod(struct isl_extract_mod_data
*data
)
907 n
= isl_aff_dim(data
->div
, isl_dim_div
);
911 if (isl_aff_involves_dims(data
->div
, isl_dim_div
, 0, n
))
912 return extract_nonneg_mod(data
);
914 hull
= isl_set_simple_hull(isl_set_copy(data
->build
->domain
));
915 hull
= isl_basic_set_remove_divs(hull
);
918 r
= isl_basic_set_foreach_constraint(hull
, &check_parallel_or_opposite
,
920 isl_basic_set_free(hull
);
922 if (!data
->sign
|| r
< 0) {
923 isl_aff_free(data
->nonneg
);
926 return extract_nonneg_mod(data
);
929 v1
= isl_aff_get_constant_val(data
->div
);
930 v2
= isl_aff_get_constant_val(data
->nonneg
);
931 if (data
->sign
< 0) {
932 v1
= isl_val_neg(v1
);
933 v1
= isl_val_add(v1
, isl_val_copy(data
->d
));
934 v1
= isl_val_sub_ui(v1
, 1);
936 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
937 v1
= isl_val_mod(v1
, isl_val_copy(data
->d
));
938 v1
= isl_val_add(v1
, v2
);
939 v2
= isl_val_div(isl_val_copy(v1
), isl_val_copy(data
->d
));
940 v2
= isl_val_ceil(v2
);
941 if (isl_val_is_neg(v2
)) {
942 v2
= isl_val_mul(v2
, isl_val_copy(data
->d
));
943 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
945 data
->nonneg
= isl_aff_set_constant_val(data
->nonneg
, v1
);
948 if (data
->sign
< 0) {
949 data
->div
= oppose_div_arg(data
->div
, isl_val_copy(data
->d
));
950 data
->v
= isl_val_neg(data
->v
);
953 return extract_term_and_mod(data
,
954 isl_aff_copy(data
->div
), data
->nonneg
);
956 data
->aff
= isl_aff_free(data
->aff
);
957 return isl_stat_error
;
960 /* Check if "data->aff" involves any (implicit) modulo computations based
962 * If so, remove them from aff and add expressions corresponding
963 * to those modulo computations to data->pos and/or data->neg.
965 * "aff" is assumed to be an integer affine expression.
967 * In particular, check if (v * div_j) is of the form
969 * f * m * floor(a / m)
971 * and, if so, rewrite it as
973 * f * (a - (a mod m)) = f * a - f * (a mod m)
975 * and extract out -f * (a mod m).
976 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
977 * If f < 0, we add ((-f) * (a mod m)) to *pos.
979 * Note that in order to represent "a mod m" as
981 * (isl_ast_expr_op_pdiv_r, a, m)
983 * we need to make sure that a is non-negative.
984 * If not, we check if "-a + m - 1" is non-negative.
985 * If so, we can rewrite
987 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
989 * and still extract a modulo.
991 static int extract_modulo(struct isl_extract_mod_data
*data
)
993 data
->div
= isl_aff_get_div(data
->aff
, data
->i
);
994 data
->d
= isl_aff_get_denominator_val(data
->div
);
995 if (isl_val_is_divisible_by(data
->v
, data
->d
)) {
996 data
->div
= isl_aff_scale_val(data
->div
, isl_val_copy(data
->d
));
997 if (try_extract_mod(data
) < 0)
998 data
->aff
= isl_aff_free(data
->aff
);
1000 isl_aff_free(data
->div
);
1001 isl_val_free(data
->d
);
1005 /* Check if "aff" involves any (implicit) modulo computations.
1006 * If so, remove them from aff and add expressions corresponding
1007 * to those modulo computations to *pos and/or *neg.
1008 * We only do this if the option ast_build_prefer_pdiv is set.
1010 * "aff" is assumed to be an integer affine expression.
1012 * A modulo expression is of the form
1014 * a mod m = a - m * floor(a / m)
1016 * To detect them in aff, we look for terms of the form
1018 * f * m * floor(a / m)
1022 * f * (a - (a mod m)) = f * a - f * (a mod m)
1024 * and extract out -f * (a mod m).
1025 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
1026 * If f < 0, we add ((-f) * (a mod m)) to *pos.
1028 static __isl_give isl_aff
*extract_modulos(__isl_take isl_aff
*aff
,
1029 __isl_keep isl_ast_expr
**pos
, __isl_keep isl_ast_expr
**neg
,
1030 __isl_keep isl_ast_build
*build
)
1032 struct isl_extract_mod_data data
= { build
, aff
, *pos
, *neg
};
1039 ctx
= isl_aff_get_ctx(aff
);
1040 if (!isl_options_get_ast_build_prefer_pdiv(ctx
))
1043 n
= isl_aff_dim(data
.aff
, isl_dim_div
);
1045 return isl_aff_free(aff
);
1046 for (data
.i
= 0; data
.i
< n
; ++data
.i
) {
1047 data
.v
= isl_aff_get_coefficient_val(data
.aff
,
1048 isl_dim_div
, data
.i
);
1050 return isl_aff_free(aff
);
1051 if (isl_val_is_zero(data
.v
) ||
1052 isl_val_is_one(data
.v
) || isl_val_is_negone(data
.v
)) {
1053 isl_val_free(data
.v
);
1056 if (extract_modulo(&data
) < 0)
1057 data
.aff
= isl_aff_free(data
.aff
);
1058 isl_val_free(data
.v
);
1064 data
.aff
= isl_aff_add(data
.aff
, data
.add
);
1071 /* Check if aff involves any non-integer coefficients.
1072 * If so, split aff into
1074 * aff = aff1 + (aff2 / d)
1076 * with both aff1 and aff2 having only integer coefficients.
1077 * Return aff1 and add (aff2 / d) to *expr.
1079 static __isl_give isl_aff
*extract_rational(__isl_take isl_aff
*aff
,
1080 __isl_keep isl_ast_expr
**expr
, __isl_keep isl_ast_build
*build
)
1084 isl_aff
*rat
= NULL
;
1085 isl_local_space
*ls
= NULL
;
1086 isl_ast_expr
*rat_expr
;
1088 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1089 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1093 d
= isl_aff_get_denominator_val(aff
);
1096 if (isl_val_is_one(d
)) {
1101 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
1103 ls
= isl_aff_get_domain_local_space(aff
);
1104 rat
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1106 for (i
= 0; i
< 3; ++i
) {
1107 n
= isl_aff_dim(aff
, t
[i
]);
1110 for (j
= 0; j
< n
; ++j
) {
1113 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1116 if (isl_val_is_divisible_by(v
, d
)) {
1120 rat_j
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1122 rat_j
= isl_aff_scale_val(rat_j
, v
);
1123 rat
= isl_aff_add(rat
, rat_j
);
1127 v
= isl_aff_get_constant_val(aff
);
1128 if (isl_val_is_divisible_by(v
, d
)) {
1133 rat_0
= isl_aff_val_on_domain(isl_local_space_copy(ls
), v
);
1134 rat
= isl_aff_add(rat
, rat_0
);
1137 isl_local_space_free(ls
);
1139 aff
= isl_aff_sub(aff
, isl_aff_copy(rat
));
1140 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(d
));
1142 rat_expr
= div_mod(isl_ast_expr_op_div
, rat
, d
, build
);
1143 *expr
= ast_expr_add(*expr
, rat_expr
);
1148 isl_local_space_free(ls
);
1154 /* Construct an isl_ast_expr that evaluates the affine expression "aff".
1155 * The result is simplified in terms of build->domain.
1157 * We first extract hidden modulo computations from the affine expression
1158 * and then add terms for each variable with a non-zero coefficient.
1159 * Finally, if the affine expression has a non-trivial denominator,
1160 * we divide the resulting isl_ast_expr by this denominator.
1162 __isl_give isl_ast_expr
*isl_ast_expr_from_aff(__isl_take isl_aff
*aff
,
1163 __isl_keep isl_ast_build
*build
)
1168 isl_ctx
*ctx
= isl_aff_get_ctx(aff
);
1169 isl_ast_expr
*expr
, *expr_neg
;
1170 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1171 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1172 isl_local_space
*ls
;
1173 struct isl_ast_add_term_data data
;
1178 expr
= isl_ast_expr_alloc_int_si(ctx
, 0);
1179 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
1181 aff
= extract_rational(aff
, &expr
, build
);
1183 aff
= extract_modulos(aff
, &expr
, &expr_neg
, build
);
1184 expr
= ast_expr_sub(expr
, expr_neg
);
1186 ls
= isl_aff_get_domain_local_space(aff
);
1189 data
.cst
= isl_aff_get_constant_val(aff
);
1190 for (i
= 0; i
< 3; ++i
) {
1191 n
= isl_aff_dim(aff
, t
[i
]);
1193 expr
= isl_ast_expr_free(expr
);
1194 for (j
= 0; j
< n
; ++j
) {
1195 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1197 expr
= isl_ast_expr_free(expr
);
1198 if (isl_val_is_zero(v
)) {
1202 expr
= isl_ast_expr_add_term(expr
,
1203 ls
, l
[i
], j
, v
, &data
);
1207 expr
= isl_ast_expr_add_int(expr
, data
.cst
);
1209 isl_local_space_free(ls
);
1214 /* Add terms to "expr" for each variable in "aff" with a coefficient
1215 * with sign equal to "sign".
1216 * The result is simplified in terms of data->build->domain.
1218 static __isl_give isl_ast_expr
*add_signed_terms(__isl_take isl_ast_expr
*expr
,
1219 __isl_keep isl_aff
*aff
, int sign
, struct isl_ast_add_term_data
*data
)
1223 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1224 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1225 isl_local_space
*ls
;
1227 ls
= isl_aff_get_domain_local_space(aff
);
1229 for (i
= 0; i
< 3; ++i
) {
1230 isl_size n
= isl_aff_dim(aff
, t
[i
]);
1232 expr
= isl_ast_expr_free(expr
);
1233 for (j
= 0; j
< n
; ++j
) {
1234 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1235 if (sign
* isl_val_sgn(v
) <= 0) {
1240 expr
= isl_ast_expr_add_term(expr
,
1241 ls
, l
[i
], j
, v
, data
);
1245 isl_local_space_free(ls
);
1250 /* Should the constant term "v" be considered positive?
1252 * A positive constant will be added to "pos" by the caller,
1253 * while a negative constant will be added to "neg".
1254 * If either "pos" or "neg" is exactly zero, then we prefer
1255 * to add the constant "v" to that side, irrespective of the sign of "v".
1256 * This results in slightly shorter expressions and may reduce the risk
1259 static isl_bool
constant_is_considered_positive(__isl_keep isl_val
*v
,
1260 __isl_keep isl_ast_expr
*pos
, __isl_keep isl_ast_expr
*neg
)
1264 zero
= ast_expr_is_zero(pos
);
1265 if (zero
< 0 || zero
)
1267 zero
= ast_expr_is_zero(neg
);
1268 if (zero
< 0 || zero
)
1269 return isl_bool_not(zero
);
1270 return isl_val_is_pos(v
);
1273 /* Check if the equality
1277 * represents a stride constraint on the integer division "pos".
1279 * In particular, if the integer division "pos" is equal to
1283 * then check if aff is equal to
1289 * If so, the equality is exactly
1293 * Note that in principle we could also accept
1297 * where e and e' differ by a constant.
1299 static isl_bool
is_stride_constraint(__isl_keep isl_aff
*aff
, int pos
)
1305 div
= isl_aff_get_div(aff
, pos
);
1306 c
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, pos
);
1307 d
= isl_aff_get_denominator_val(div
);
1308 eq
= isl_val_abs_eq(c
, d
);
1309 if (eq
>= 0 && eq
) {
1310 aff
= isl_aff_copy(aff
);
1311 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, pos
, 0);
1312 div
= isl_aff_scale_val(div
, d
);
1313 if (isl_val_is_pos(c
))
1314 div
= isl_aff_neg(div
);
1315 eq
= isl_aff_plain_is_equal(div
, aff
);
1325 /* Are all coefficients of "aff" (zero or) negative?
1327 static isl_bool
all_negative_coefficients(__isl_keep isl_aff
*aff
)
1332 n
= isl_aff_dim(aff
, isl_dim_param
);
1334 return isl_bool_error
;
1335 for (i
= 0; i
< n
; ++i
)
1336 if (isl_aff_coefficient_sgn(aff
, isl_dim_param
, i
) > 0)
1337 return isl_bool_false
;
1339 n
= isl_aff_dim(aff
, isl_dim_in
);
1341 return isl_bool_error
;
1342 for (i
= 0; i
< n
; ++i
)
1343 if (isl_aff_coefficient_sgn(aff
, isl_dim_in
, i
) > 0)
1344 return isl_bool_false
;
1346 return isl_bool_true
;
1349 /* Give an equality of the form
1351 * aff = e - d floor(e/d) = 0
1355 * aff = -e + d floor(e/d) = 0
1357 * with the integer division "pos" equal to floor(e/d),
1358 * construct the AST expression
1360 * (isl_ast_expr_op_eq,
1361 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1363 * If e only has negative coefficients, then construct
1365 * (isl_ast_expr_op_eq,
1366 * (isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))
1370 static __isl_give isl_ast_expr
*extract_stride_constraint(
1371 __isl_take isl_aff
*aff
, int pos
, __isl_keep isl_ast_build
*build
)
1376 isl_ast_expr
*expr
, *cst
;
1381 ctx
= isl_aff_get_ctx(aff
);
1383 c
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, pos
);
1384 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, pos
, 0);
1386 all_neg
= all_negative_coefficients(aff
);
1388 aff
= isl_aff_free(aff
);
1390 aff
= isl_aff_neg(aff
);
1392 cst
= isl_ast_expr_from_val(isl_val_abs(c
));
1393 expr
= isl_ast_expr_from_aff(aff
, build
);
1395 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_zdiv_r
, expr
, cst
);
1396 cst
= isl_ast_expr_alloc_int_si(ctx
, 0);
1397 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_eq
, expr
, cst
);
1402 /* Construct an isl_ast_expr evaluating
1404 * "expr_pos" == "expr_neg", if "eq" is set, or
1405 * "expr_pos" >= "expr_neg", if "eq" is not set
1407 * However, if "expr_pos" is an integer constant (and "expr_neg" is not),
1408 * then the two expressions are interchanged. This ensures that,
1409 * e.g., "i <= 5" is constructed rather than "5 >= i".
1411 static __isl_give isl_ast_expr
*construct_constraint_expr(int eq
,
1412 __isl_take isl_ast_expr
*expr_pos
, __isl_take isl_ast_expr
*expr_neg
)
1415 enum isl_ast_expr_op_type type
;
1416 int pos_is_cst
, neg_is_cst
;
1418 pos_is_cst
= isl_ast_expr_get_type(expr_pos
) == isl_ast_expr_int
;
1419 neg_is_cst
= isl_ast_expr_get_type(expr_neg
) == isl_ast_expr_int
;
1420 if (pos_is_cst
&& !neg_is_cst
) {
1421 type
= eq
? isl_ast_expr_op_eq
: isl_ast_expr_op_le
;
1422 expr
= isl_ast_expr_alloc_binary(type
, expr_neg
, expr_pos
);
1424 type
= eq
? isl_ast_expr_op_eq
: isl_ast_expr_op_ge
;
1425 expr
= isl_ast_expr_alloc_binary(type
, expr_pos
, expr_neg
);
1431 /* Construct an isl_ast_expr that evaluates the condition "aff" == 0
1432 * (if "eq" is set) or "aff" >= 0 (otherwise).
1433 * The result is simplified in terms of build->domain.
1435 * We first extract hidden modulo computations from "aff"
1436 * and then collect all the terms with a positive coefficient in cons_pos
1437 * and the terms with a negative coefficient in cons_neg.
1439 * The result is then essentially of the form
1441 * (isl_ast_expr_op_ge, expr(pos), expr(-neg)))
1445 * (isl_ast_expr_op_eq, expr(pos), expr(-neg)))
1447 * However, if there are no terms with positive coefficients (or no terms
1448 * with negative coefficients), then the constant term is added to "pos"
1449 * (or "neg"), ignoring the sign of the constant term.
1451 static __isl_give isl_ast_expr
*isl_ast_expr_from_constraint_no_stride(
1452 int eq
, __isl_take isl_aff
*aff
, __isl_keep isl_ast_build
*build
)
1454 isl_bool cst_is_pos
;
1456 isl_ast_expr
*expr_pos
;
1457 isl_ast_expr
*expr_neg
;
1458 struct isl_ast_add_term_data data
;
1460 ctx
= isl_aff_get_ctx(aff
);
1461 expr_pos
= isl_ast_expr_alloc_int_si(ctx
, 0);
1462 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
1464 aff
= extract_modulos(aff
, &expr_pos
, &expr_neg
, build
);
1467 data
.cst
= isl_aff_get_constant_val(aff
);
1468 expr_pos
= add_signed_terms(expr_pos
, aff
, 1, &data
);
1469 data
.cst
= isl_val_neg(data
.cst
);
1470 expr_neg
= add_signed_terms(expr_neg
, aff
, -1, &data
);
1471 data
.cst
= isl_val_neg(data
.cst
);
1474 constant_is_considered_positive(data
.cst
, expr_pos
, expr_neg
);
1476 expr_pos
= isl_ast_expr_free(expr_pos
);
1479 expr_pos
= isl_ast_expr_add_int(expr_pos
, data
.cst
);
1481 data
.cst
= isl_val_neg(data
.cst
);
1482 expr_neg
= isl_ast_expr_add_int(expr_neg
, data
.cst
);
1486 return construct_constraint_expr(eq
, expr_pos
, expr_neg
);
1489 /* Construct an isl_ast_expr that evaluates the condition "constraint".
1490 * The result is simplified in terms of build->domain.
1492 * We first check if the constraint is an equality of the form
1494 * e - d floor(e/d) = 0
1500 * If so, we convert it to
1502 * (isl_ast_expr_op_eq,
1503 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1505 static __isl_give isl_ast_expr
*isl_ast_expr_from_constraint(
1506 __isl_take isl_constraint
*constraint
, __isl_keep isl_ast_build
*build
)
1513 aff
= isl_constraint_get_aff(constraint
);
1514 eq
= isl_constraint_is_equality(constraint
);
1515 isl_constraint_free(constraint
);
1519 n
= isl_aff_dim(aff
, isl_dim_div
);
1521 aff
= isl_aff_free(aff
);
1523 for (i
= 0; i
< n
; ++i
) {
1525 is_stride
= is_stride_constraint(aff
, i
);
1529 return extract_stride_constraint(aff
, i
, build
);
1532 return isl_ast_expr_from_constraint_no_stride(eq
, aff
, build
);
1538 /* Wrapper around isl_constraint_cmp_last_non_zero for use
1539 * as a callback to isl_constraint_list_sort.
1540 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1541 * apart, then use isl_constraint_plain_cmp instead.
1543 static int cmp_constraint(__isl_keep isl_constraint
*a
,
1544 __isl_keep isl_constraint
*b
, void *user
)
1548 cmp
= isl_constraint_cmp_last_non_zero(a
, b
);
1551 return isl_constraint_plain_cmp(a
, b
);
1554 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1555 * The result is simplified in terms of build->domain.
1557 * If "bset" is not bounded by any constraint, then we construct
1558 * the expression "1", i.e., "true".
1560 * Otherwise, we sort the constraints, putting constraints that involve
1561 * integer divisions after those that do not, and construct an "and"
1562 * of the ast expressions of the individual constraints.
1564 * Each constraint is added to the generated constraints of the build
1565 * after it has been converted to an AST expression so that it can be used
1566 * to simplify the following constraints. This may change the truth value
1567 * of subsequent constraints that do not satisfy the earlier constraints,
1568 * but this does not affect the outcome of the conjunction as it is
1569 * only true if all the conjuncts are true (no matter in what order
1570 * they are evaluated). In particular, the constraints that do not
1571 * involve integer divisions may serve to simplify some constraints
1572 * that do involve integer divisions.
1574 __isl_give isl_ast_expr
*isl_ast_build_expr_from_basic_set(
1575 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
1580 isl_constraint_list
*list
;
1584 list
= isl_basic_set_get_constraint_list(bset
);
1585 isl_basic_set_free(bset
);
1586 list
= isl_constraint_list_sort(list
, &cmp_constraint
, NULL
);
1587 n
= isl_constraint_list_n_constraint(list
);
1591 isl_ctx
*ctx
= isl_constraint_list_get_ctx(list
);
1592 isl_constraint_list_free(list
);
1593 return isl_ast_expr_alloc_int_si(ctx
, 1);
1596 build
= isl_ast_build_copy(build
);
1598 c
= isl_constraint_list_get_constraint(list
, 0);
1599 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
1600 set
= isl_set_from_basic_set(bset
);
1601 res
= isl_ast_expr_from_constraint(c
, build
);
1602 build
= isl_ast_build_restrict_generated(build
, set
);
1604 for (i
= 1; i
< n
; ++i
) {
1607 c
= isl_constraint_list_get_constraint(list
, i
);
1608 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
1609 set
= isl_set_from_basic_set(bset
);
1610 expr
= isl_ast_expr_from_constraint(c
, build
);
1611 build
= isl_ast_build_restrict_generated(build
, set
);
1612 res
= isl_ast_expr_and(res
, expr
);
1615 isl_constraint_list_free(list
);
1616 isl_ast_build_free(build
);
1620 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1621 * The result is simplified in terms of build->domain.
1623 * If "set" is an (obviously) empty set, then return the expression "0".
1625 * If there are multiple disjuncts in the description of the set,
1626 * then subsequent disjuncts are simplified in a context where
1627 * the previous disjuncts have been removed from build->domain.
1628 * In particular, constraints that ensure that there is no overlap
1629 * with these previous disjuncts, can be removed.
1630 * This is mostly useful for disjuncts that are only defined by
1631 * a single constraint (relative to the build domain) as the opposite
1632 * of that single constraint can then be removed from the other disjuncts.
1633 * In order not to increase the number of disjuncts in the build domain
1634 * after subtracting the previous disjuncts of "set", the simple hull
1635 * is computed after taking the difference with each of these disjuncts.
1636 * This means that constraints that prevent overlap with a union
1637 * of multiple previous disjuncts are not removed.
1639 * "set" lives in the internal schedule space.
1641 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set_internal(
1642 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1646 isl_basic_set
*bset
;
1647 isl_basic_set_list
*list
;
1651 list
= isl_set_get_basic_set_list(set
);
1654 n
= isl_basic_set_list_n_basic_set(list
);
1658 isl_ctx
*ctx
= isl_ast_build_get_ctx(build
);
1659 isl_basic_set_list_free(list
);
1660 return isl_ast_expr_from_val(isl_val_zero(ctx
));
1663 domain
= isl_ast_build_get_domain(build
);
1665 bset
= isl_basic_set_list_get_basic_set(list
, 0);
1666 set
= isl_set_from_basic_set(isl_basic_set_copy(bset
));
1667 res
= isl_ast_build_expr_from_basic_set(build
, bset
);
1669 for (i
= 1; i
< n
; ++i
) {
1673 rest
= isl_set_subtract(isl_set_copy(domain
), set
);
1674 rest
= isl_set_from_basic_set(isl_set_simple_hull(rest
));
1675 domain
= isl_set_intersect(domain
, rest
);
1676 bset
= isl_basic_set_list_get_basic_set(list
, i
);
1677 set
= isl_set_from_basic_set(isl_basic_set_copy(bset
));
1678 bset
= isl_basic_set_gist(bset
,
1679 isl_set_simple_hull(isl_set_copy(domain
)));
1680 expr
= isl_ast_build_expr_from_basic_set(build
, bset
);
1681 res
= isl_ast_expr_or(res
, expr
);
1684 isl_set_free(domain
);
1686 isl_basic_set_list_free(list
);
1690 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1691 * The result is simplified in terms of build->domain.
1693 * If "set" is an (obviously) empty set, then return the expression "0".
1695 * "set" lives in the external schedule space.
1697 * The internal AST expression generation assumes that there are
1698 * no unknown divs, so make sure an explicit representation is available.
1699 * Since the set comes from the outside, it may have constraints that
1700 * are redundant with respect to the build domain. Remove them first.
1702 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set(
1703 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1707 needs_map
= isl_ast_build_need_schedule_map(build
);
1708 if (needs_map
< 0) {
1709 set
= isl_set_free(set
);
1710 } else if (needs_map
) {
1712 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
1713 set
= isl_set_preimage_multi_aff(set
, ma
);
1716 set
= isl_set_compute_divs(set
);
1717 set
= isl_ast_build_compute_gist(build
, set
);
1718 return isl_ast_build_expr_from_set_internal(build
, set
);
1721 /* State of data about previous pieces in
1722 * isl_ast_build_expr_from_pw_aff_internal.
1724 * isl_state_none: no data about previous pieces
1725 * isl_state_single: data about a single previous piece
1726 * isl_state_min: data represents minimum of several pieces
1727 * isl_state_max: data represents maximum of several pieces
1729 enum isl_from_pw_aff_state
{
1736 /* Internal date structure representing a single piece in the input of
1737 * isl_ast_build_expr_from_pw_aff_internal.
1739 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1740 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1741 * single previous subpiece.
1742 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
1743 * a sequence of several previous subpieces that are equal to the minimum
1744 * of the entries in "aff_list" over the union of "set_list"
1745 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
1746 * a sequence of several previous subpieces that are equal to the maximum
1747 * of the entries in "aff_list" over the union of "set_list"
1749 * During the construction of the pieces, "set" is NULL.
1750 * After the construction, "set" is set to the union of the elements
1751 * in "set_list", at which point "set_list" is set to NULL.
1753 struct isl_from_pw_aff_piece
{
1754 enum isl_from_pw_aff_state state
;
1756 isl_set_list
*set_list
;
1757 isl_aff_list
*aff_list
;
1760 /* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1762 * "build" specifies the domain against which the result is simplified.
1763 * "dom" is the domain of the entire isl_pw_aff.
1765 * "n" is the number of pieces constructed already.
1766 * In particular, during the construction of the pieces, "n" points to
1767 * the piece that is being constructed. After the construction of the
1768 * pieces, "n" is set to the total number of pieces.
1769 * "max" is the total number of allocated entries.
1770 * "p" contains the individual pieces.
1772 struct isl_from_pw_aff_data
{
1773 isl_ast_build
*build
;
1778 struct isl_from_pw_aff_piece
*p
;
1781 /* Initialize "data" based on "build" and "pa".
1783 static isl_stat
isl_from_pw_aff_data_init(struct isl_from_pw_aff_data
*data
,
1784 __isl_keep isl_ast_build
*build
, __isl_keep isl_pw_aff
*pa
)
1789 ctx
= isl_pw_aff_get_ctx(pa
);
1790 n
= isl_pw_aff_n_piece(pa
);
1792 return isl_stat_error
;
1794 isl_die(ctx
, isl_error_invalid
,
1795 "cannot handle void expression", return isl_stat_error
);
1797 data
->p
= isl_calloc_array(ctx
, struct isl_from_pw_aff_piece
, n
);
1799 return isl_stat_error
;
1800 data
->build
= build
;
1801 data
->dom
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1807 /* Free all memory allocated for "data".
1809 static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data
*data
)
1813 isl_set_free(data
->dom
);
1817 for (i
= 0; i
< data
->max
; ++i
) {
1818 isl_set_free(data
->p
[i
].set
);
1819 isl_set_list_free(data
->p
[i
].set_list
);
1820 isl_aff_list_free(data
->p
[i
].aff_list
);
1825 /* Initialize the current entry of "data" to an unused piece.
1827 static void set_none(struct isl_from_pw_aff_data
*data
)
1829 data
->p
[data
->n
].state
= isl_state_none
;
1830 data
->p
[data
->n
].set_list
= NULL
;
1831 data
->p
[data
->n
].aff_list
= NULL
;
1834 /* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1836 static void set_single(struct isl_from_pw_aff_data
*data
,
1837 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1839 data
->p
[data
->n
].state
= isl_state_single
;
1840 data
->p
[data
->n
].set_list
= isl_set_list_from_set(set
);
1841 data
->p
[data
->n
].aff_list
= isl_aff_list_from_aff(aff
);
1844 /* Extend the current entry of "data" with "set" and "aff"
1845 * as a minimum expression.
1847 static isl_stat
extend_min(struct isl_from_pw_aff_data
*data
,
1848 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1851 data
->p
[n
].state
= isl_state_min
;
1852 data
->p
[n
].set_list
= isl_set_list_add(data
->p
[n
].set_list
, set
);
1853 data
->p
[n
].aff_list
= isl_aff_list_add(data
->p
[n
].aff_list
, aff
);
1855 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1856 return isl_stat_error
;
1860 /* Extend the current entry of "data" with "set" and "aff"
1861 * as a maximum expression.
1863 static isl_stat
extend_max(struct isl_from_pw_aff_data
*data
,
1864 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1867 data
->p
[n
].state
= isl_state_max
;
1868 data
->p
[n
].set_list
= isl_set_list_add(data
->p
[n
].set_list
, set
);
1869 data
->p
[n
].aff_list
= isl_aff_list_add(data
->p
[n
].aff_list
, aff
);
1871 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1872 return isl_stat_error
;
1876 /* Extend the domain of the current entry of "data", which is assumed
1877 * to contain a single subpiece, with "set". If "replace" is set,
1878 * then also replace the affine function by "aff". Otherwise,
1879 * simply free "aff".
1881 static isl_stat
extend_domain(struct isl_from_pw_aff_data
*data
,
1882 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
, int replace
)
1887 set_n
= isl_set_list_get_set(data
->p
[n
].set_list
, 0);
1888 set_n
= isl_set_union(set_n
, set
);
1889 data
->p
[n
].set_list
=
1890 isl_set_list_set_set(data
->p
[n
].set_list
, 0, set_n
);
1893 data
->p
[n
].aff_list
=
1894 isl_aff_list_set_aff(data
->p
[n
].aff_list
, 0, aff
);
1898 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1899 return isl_stat_error
;
1903 /* Construct an isl_ast_expr from "list" within "build".
1904 * If "state" is isl_state_single, then "list" contains a single entry and
1905 * an isl_ast_expr is constructed for that entry.
1906 * Otherwise a min or max expression is constructed from "list"
1907 * depending on "state".
1909 static __isl_give isl_ast_expr
*ast_expr_from_aff_list(
1910 __isl_take isl_aff_list
*list
, enum isl_from_pw_aff_state state
,
1911 __isl_keep isl_ast_build
*build
)
1916 isl_ast_expr
*expr
= NULL
;
1917 enum isl_ast_expr_op_type op_type
;
1919 if (state
== isl_state_single
) {
1920 aff
= isl_aff_list_get_aff(list
, 0);
1921 isl_aff_list_free(list
);
1922 return isl_ast_expr_from_aff(aff
, build
);
1924 n
= isl_aff_list_n_aff(list
);
1927 op_type
= state
== isl_state_min
? isl_ast_expr_op_min
1928 : isl_ast_expr_op_max
;
1929 expr
= isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build
), op_type
, n
);
1933 for (i
= 0; i
< n
; ++i
) {
1934 isl_ast_expr
*expr_i
;
1936 aff
= isl_aff_list_get_aff(list
, i
);
1937 expr_i
= isl_ast_expr_from_aff(aff
, build
);
1940 expr
->u
.op
.args
[i
] = expr_i
;
1943 isl_aff_list_free(list
);
1946 isl_aff_list_free(list
);
1947 isl_ast_expr_free(expr
);
1951 /* Extend the expression in "next" to take into account
1952 * the piece at position "pos" in "data", allowing for a further extension
1953 * for the next piece(s).
1954 * In particular, "next" is set to a select operation that selects
1955 * an isl_ast_expr corresponding to data->aff_list on data->set and
1956 * to an expression that will be filled in by later calls.
1957 * Return a pointer to this location.
1958 * Afterwards, the state of "data" is set to isl_state_none.
1960 * The constraints of data->set are added to the generated
1961 * constraints of the build such that they can be exploited to simplify
1962 * the AST expression constructed from data->aff_list.
1964 static isl_ast_expr
**add_intermediate_piece(struct isl_from_pw_aff_data
*data
,
1965 int pos
, isl_ast_expr
**next
)
1968 isl_ast_build
*build
;
1969 isl_ast_expr
*ternary
, *arg
;
1970 isl_set
*set
, *gist
;
1972 set
= data
->p
[pos
].set
;
1973 data
->p
[pos
].set
= NULL
;
1974 ctx
= isl_ast_build_get_ctx(data
->build
);
1975 ternary
= isl_ast_expr_alloc_op(ctx
, isl_ast_expr_op_select
, 3);
1976 gist
= isl_set_gist(isl_set_copy(set
), isl_set_copy(data
->dom
));
1977 arg
= isl_ast_build_expr_from_set_internal(data
->build
, gist
);
1978 ternary
= isl_ast_expr_set_op_arg(ternary
, 0, arg
);
1979 build
= isl_ast_build_copy(data
->build
);
1980 build
= isl_ast_build_restrict_generated(build
, set
);
1981 arg
= ast_expr_from_aff_list(data
->p
[pos
].aff_list
,
1982 data
->p
[pos
].state
, build
);
1983 data
->p
[pos
].aff_list
= NULL
;
1984 isl_ast_build_free(build
);
1985 ternary
= isl_ast_expr_set_op_arg(ternary
, 1, arg
);
1986 data
->p
[pos
].state
= isl_state_none
;
1991 return &ternary
->u
.op
.args
[2];
1994 /* Extend the expression in "next" to take into account
1995 * the final piece, located at position "pos" in "data".
1996 * In particular, "next" is set to evaluate data->aff_list
1997 * and the domain is ignored.
1998 * Return isl_stat_ok on success and isl_stat_error on failure.
2000 * The constraints of data->set are however added to the generated
2001 * constraints of the build such that they can be exploited to simplify
2002 * the AST expression constructed from data->aff_list.
2004 static isl_stat
add_last_piece(struct isl_from_pw_aff_data
*data
,
2005 int pos
, isl_ast_expr
**next
)
2007 isl_ast_build
*build
;
2009 if (data
->p
[pos
].state
== isl_state_none
)
2010 isl_die(isl_ast_build_get_ctx(data
->build
), isl_error_invalid
,
2011 "cannot handle void expression", return isl_stat_error
);
2013 build
= isl_ast_build_copy(data
->build
);
2014 build
= isl_ast_build_restrict_generated(build
, data
->p
[pos
].set
);
2015 data
->p
[pos
].set
= NULL
;
2016 *next
= ast_expr_from_aff_list(data
->p
[pos
].aff_list
,
2017 data
->p
[pos
].state
, build
);
2018 data
->p
[pos
].aff_list
= NULL
;
2019 isl_ast_build_free(build
);
2020 data
->p
[pos
].state
= isl_state_none
;
2022 return isl_stat_error
;
2027 /* Return -1 if the piece "p1" should be sorted before "p2"
2028 * and 1 if it should be sorted after "p2".
2029 * Return 0 if they do not need to be sorted in a specific order.
2031 * Pieces are sorted according to the number of disjuncts
2034 static int sort_pieces_cmp(const void *p1
, const void *p2
, void *arg
)
2036 const struct isl_from_pw_aff_piece
*piece1
= p1
;
2037 const struct isl_from_pw_aff_piece
*piece2
= p2
;
2040 n1
= isl_set_n_basic_set(piece1
->set
);
2041 n2
= isl_set_n_basic_set(piece2
->set
);
2046 /* Construct an isl_ast_expr from the pieces in "data".
2047 * Return the result or NULL on failure.
2049 * When this function is called, data->n points to the current piece.
2050 * If this is an effective piece, then first increment data->n such
2051 * that data->n contains the number of pieces.
2052 * The "set_list" fields are subsequently replaced by the corresponding
2053 * "set" fields, after which the pieces are sorted according to
2054 * the number of disjuncts in these "set" fields.
2056 * Construct intermediate AST expressions for the initial pieces and
2057 * finish off with the final pieces.
2059 static isl_ast_expr
*build_pieces(struct isl_from_pw_aff_data
*data
)
2062 isl_ast_expr
*res
= NULL
;
2063 isl_ast_expr
**next
= &res
;
2065 if (data
->p
[data
->n
].state
!= isl_state_none
)
2068 isl_die(isl_ast_build_get_ctx(data
->build
), isl_error_invalid
,
2069 "cannot handle void expression", return NULL
);
2071 for (i
= 0; i
< data
->n
; ++i
) {
2072 data
->p
[i
].set
= isl_set_list_union(data
->p
[i
].set_list
);
2073 if (data
->p
[i
].state
!= isl_state_single
)
2074 data
->p
[i
].set
= isl_set_coalesce(data
->p
[i
].set
);
2075 data
->p
[i
].set_list
= NULL
;
2078 if (isl_sort(data
->p
, data
->n
, sizeof(data
->p
[0]),
2079 &sort_pieces_cmp
, NULL
) < 0)
2080 return isl_ast_expr_free(res
);
2082 for (i
= 0; i
+ 1 < data
->n
; ++i
) {
2083 next
= add_intermediate_piece(data
, i
, next
);
2085 return isl_ast_expr_free(res
);
2088 if (add_last_piece(data
, data
->n
- 1, next
) < 0)
2089 return isl_ast_expr_free(res
);
2094 /* Is the domain of the current entry of "data", which is assumed
2095 * to contain a single subpiece, a subset of "set"?
2097 static isl_bool
single_is_subset(struct isl_from_pw_aff_data
*data
,
2098 __isl_keep isl_set
*set
)
2103 set_n
= isl_set_list_get_set(data
->p
[data
->n
].set_list
, 0);
2104 subset
= isl_set_is_subset(set_n
, set
);
2105 isl_set_free(set_n
);
2110 /* Is "aff" a rational expression, i.e., does it have a denominator
2111 * different from one?
2113 static isl_bool
aff_is_rational(__isl_keep isl_aff
*aff
)
2118 den
= isl_aff_get_denominator_val(aff
);
2119 rational
= isl_bool_not(isl_val_is_one(den
));
2125 /* Does "list" consist of a single rational affine expression?
2127 static isl_bool
is_single_rational_aff(__isl_keep isl_aff_list
*list
)
2133 n
= isl_aff_list_n_aff(list
);
2135 return isl_bool_error
;
2137 return isl_bool_false
;
2138 aff
= isl_aff_list_get_aff(list
, 0);
2139 rational
= aff_is_rational(aff
);
2145 /* Can the list of subpieces in the last piece of "data" be extended with
2146 * "set" and "aff" based on "test"?
2147 * In particular, is it the case for each entry (set_i, aff_i) that
2149 * test(aff, aff_i) holds on set_i, and
2150 * test(aff_i, aff) holds on set?
2152 * "test" returns the set of elements where the tests holds, meaning
2153 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2155 * This function is used to detect min/max expressions.
2156 * If the ast_build_detect_min_max option is turned off, then
2157 * do not even try and perform any detection and return false instead.
2159 * Rational affine expressions are not considered for min/max expressions
2160 * since the combined expression will be defined on the union of the domains,
2161 * while a rational expression may only yield integer values
2162 * on its own definition domain.
2164 static isl_bool
extends(struct isl_from_pw_aff_data
*data
,
2165 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
,
2166 __isl_give isl_basic_set
*(*test
)(__isl_take isl_aff
*aff1
,
2167 __isl_take isl_aff
*aff2
))
2171 isl_bool is_rational
;
2175 is_rational
= aff_is_rational(aff
);
2176 if (is_rational
>= 0 && !is_rational
)
2177 is_rational
= is_single_rational_aff(data
->p
[data
->n
].aff_list
);
2178 if (is_rational
< 0 || is_rational
)
2179 return isl_bool_not(is_rational
);
2181 ctx
= isl_ast_build_get_ctx(data
->build
);
2182 if (!isl_options_get_ast_build_detect_min_max(ctx
))
2183 return isl_bool_false
;
2185 n
= isl_set_list_n_set(data
->p
[data
->n
].set_list
);
2187 return isl_bool_error
;
2189 dom
= isl_ast_build_get_domain(data
->build
);
2190 set
= isl_set_intersect(dom
, isl_set_copy(set
));
2192 for (i
= 0; i
< n
; ++i
) {
2195 isl_set
*dom
, *required
;
2198 aff_i
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, i
);
2199 valid
= isl_set_from_basic_set(test(isl_aff_copy(aff
), aff_i
));
2200 required
= isl_set_list_get_set(data
->p
[data
->n
].set_list
, i
);
2201 dom
= isl_ast_build_get_domain(data
->build
);
2202 required
= isl_set_intersect(dom
, required
);
2203 is_valid
= isl_set_is_subset(required
, valid
);
2204 isl_set_free(required
);
2205 isl_set_free(valid
);
2206 if (is_valid
< 0 || !is_valid
) {
2211 aff_i
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, i
);
2212 valid
= isl_set_from_basic_set(test(aff_i
, isl_aff_copy(aff
)));
2213 is_valid
= isl_set_is_subset(set
, valid
);
2214 isl_set_free(valid
);
2215 if (is_valid
< 0 || !is_valid
) {
2222 return isl_bool_true
;
2225 /* Can the list of pieces in "data" be extended with "set" and "aff"
2226 * to form/preserve a minimum expression?
2227 * In particular, is it the case for each entry (set_i, aff_i) that
2229 * aff >= aff_i on set_i, and
2230 * aff_i >= aff on set?
2232 static isl_bool
extends_min(struct isl_from_pw_aff_data
*data
,
2233 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
)
2235 return extends(data
, set
, aff
, &isl_aff_ge_basic_set
);
2238 /* Can the list of pieces in "data" be extended with "set" and "aff"
2239 * to form/preserve a maximum expression?
2240 * In particular, is it the case for each entry (set_i, aff_i) that
2242 * aff <= aff_i on set_i, and
2243 * aff_i <= aff on set?
2245 static isl_bool
extends_max(struct isl_from_pw_aff_data
*data
,
2246 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
)
2248 return extends(data
, set
, aff
, &isl_aff_le_basic_set
);
2251 /* This function is called during the construction of an isl_ast_expr
2252 * that evaluates an isl_pw_aff.
2253 * If the last piece of "data" contains a single subpiece and
2254 * if its affine function is equal to "aff" on a part of the domain
2255 * that includes either "set" or the domain of that single subpiece,
2256 * then extend the domain of that single subpiece with "set".
2257 * If it was the original domain of the single subpiece where
2258 * the two affine functions are equal, then also replace
2259 * the affine function of the single subpiece by "aff".
2260 * If the last piece of "data" contains either a single subpiece
2261 * or a minimum, then check if this minimum expression can be extended
2263 * If so, extend the sequence and return.
2264 * Perform the same operation for maximum expressions.
2265 * If no such extension can be performed, then move to the next piece
2266 * in "data" (if the current piece contains any data), and then store
2267 * the current subpiece in the current piece of "data" for later handling.
2269 static isl_stat
ast_expr_from_pw_aff(__isl_take isl_set
*set
,
2270 __isl_take isl_aff
*aff
, void *user
)
2272 struct isl_from_pw_aff_data
*data
= user
;
2274 enum isl_from_pw_aff_state state
;
2276 state
= data
->p
[data
->n
].state
;
2277 if (state
== isl_state_single
) {
2280 isl_bool subset1
, subset2
= isl_bool_false
;
2281 aff0
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, 0);
2282 eq
= isl_aff_eq_set(isl_aff_copy(aff
), aff0
);
2283 subset1
= isl_set_is_subset(set
, eq
);
2284 if (subset1
>= 0 && !subset1
)
2285 subset2
= single_is_subset(data
, eq
);
2287 if (subset1
< 0 || subset2
< 0)
2290 return extend_domain(data
, set
, aff
, 0);
2292 return extend_domain(data
, set
, aff
, 1);
2294 if (state
== isl_state_single
|| state
== isl_state_min
) {
2295 test
= extends_min(data
, set
, aff
);
2299 return extend_min(data
, set
, aff
);
2301 if (state
== isl_state_single
|| state
== isl_state_max
) {
2302 test
= extends_max(data
, set
, aff
);
2306 return extend_max(data
, set
, aff
);
2308 if (state
!= isl_state_none
)
2310 set_single(data
, set
, aff
);
2316 return isl_stat_error
;
2319 /* Construct an isl_ast_expr that evaluates "pa".
2320 * The result is simplified in terms of build->domain.
2322 * The domain of "pa" lives in the internal schedule space.
2324 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff_internal(
2325 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2327 struct isl_from_pw_aff_data data
= { NULL
};
2328 isl_ast_expr
*res
= NULL
;
2330 pa
= isl_ast_build_compute_gist_pw_aff(build
, pa
);
2331 pa
= isl_pw_aff_coalesce(pa
);
2335 if (isl_from_pw_aff_data_init(&data
, build
, pa
) < 0)
2339 if (isl_pw_aff_foreach_piece(pa
, &ast_expr_from_pw_aff
, &data
) >= 0)
2340 res
= build_pieces(&data
);
2342 isl_pw_aff_free(pa
);
2343 isl_from_pw_aff_data_clear(&data
);
2346 isl_pw_aff_free(pa
);
2347 isl_from_pw_aff_data_clear(&data
);
2351 /* Construct an isl_ast_expr that evaluates "pa".
2352 * The result is simplified in terms of build->domain.
2354 * The domain of "pa" lives in the external schedule space.
2356 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff(
2357 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2362 needs_map
= isl_ast_build_need_schedule_map(build
);
2363 if (needs_map
< 0) {
2364 pa
= isl_pw_aff_free(pa
);
2365 } else if (needs_map
) {
2367 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
2368 pa
= isl_pw_aff_pullback_multi_aff(pa
, ma
);
2370 expr
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
2374 /* Set the ids of the input dimensions of "mpa" to the iterator ids
2377 * The domain of "mpa" is assumed to live in the internal schedule domain.
2379 static __isl_give isl_multi_pw_aff
*set_iterator_names(
2380 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2385 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_in
);
2387 return isl_multi_pw_aff_free(mpa
);
2388 for (i
= 0; i
< n
; ++i
) {
2391 id
= isl_ast_build_get_iterator_id(build
, i
);
2392 mpa
= isl_multi_pw_aff_set_dim_id(mpa
, isl_dim_in
, i
, id
);
2398 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2399 * the remaining arguments derived from "mpa".
2400 * That is, construct a call or access expression that calls/accesses "arg0"
2401 * with arguments/indices specified by "mpa".
2403 static __isl_give isl_ast_expr
*isl_ast_build_with_arguments(
2404 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2405 __isl_take isl_ast_expr
*arg0
, __isl_take isl_multi_pw_aff
*mpa
)
2412 ctx
= isl_ast_build_get_ctx(build
);
2414 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_out
);
2415 expr
= n
>= 0 ? isl_ast_expr_alloc_op(ctx
, type
, 1 + n
) : NULL
;
2416 expr
= isl_ast_expr_set_op_arg(expr
, 0, arg0
);
2417 for (i
= 0; i
< n
; ++i
) {
2421 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
2422 arg
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
2423 expr
= isl_ast_expr_set_op_arg(expr
, 1 + i
, arg
);
2426 isl_multi_pw_aff_free(mpa
);
2430 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_internal(
2431 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2432 __isl_take isl_multi_pw_aff
*mpa
);
2434 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
2435 * The range of "mpa" is assumed to be wrapped relation.
2436 * The domain of this wrapped relation specifies the structure being
2437 * accessed, while the range of this wrapped relation spacifies the
2438 * member of the structure being accessed.
2440 * The domain of "mpa" is assumed to live in the internal schedule domain.
2442 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_member(
2443 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2446 isl_multi_pw_aff
*domain
;
2447 isl_ast_expr
*domain_expr
, *expr
;
2448 enum isl_ast_expr_op_type type
= isl_ast_expr_op_access
;
2450 domain
= isl_multi_pw_aff_copy(mpa
);
2451 domain
= isl_multi_pw_aff_range_factor_domain(domain
);
2452 domain_expr
= isl_ast_build_from_multi_pw_aff_internal(build
,
2454 mpa
= isl_multi_pw_aff_range_factor_range(mpa
);
2455 if (!isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
))
2456 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
2457 "missing field name", goto error
);
2458 id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
2459 expr
= isl_ast_expr_from_id(id
);
2460 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_member
,
2462 return isl_ast_build_with_arguments(build
, type
, expr
, mpa
);
2464 isl_multi_pw_aff_free(mpa
);
2468 /* Construct an isl_ast_expr of type "type" that calls or accesses
2469 * the element specified by "mpa".
2470 * The first argument is obtained from the output tuple name.
2471 * The remaining arguments are given by the piecewise affine expressions.
2473 * If the range of "mpa" is a mapped relation, then we assume it
2474 * represents an access to a member of a structure.
2476 * The domain of "mpa" is assumed to live in the internal schedule domain.
2478 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_internal(
2479 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2480 __isl_take isl_multi_pw_aff
*mpa
)
2489 if (type
== isl_ast_expr_op_access
&&
2490 isl_multi_pw_aff_range_is_wrapping(mpa
))
2491 return isl_ast_build_from_multi_pw_aff_member(build
, mpa
);
2493 mpa
= set_iterator_names(build
, mpa
);
2497 ctx
= isl_ast_build_get_ctx(build
);
2499 if (isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
))
2500 id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
2502 id
= isl_id_alloc(ctx
, "", NULL
);
2504 expr
= isl_ast_expr_from_id(id
);
2505 return isl_ast_build_with_arguments(build
, type
, expr
, mpa
);
2507 isl_multi_pw_aff_free(mpa
);
2511 /* Construct an isl_ast_expr of type "type" that calls or accesses
2512 * the element specified by "pma".
2513 * The first argument is obtained from the output tuple name.
2514 * The remaining arguments are given by the piecewise affine expressions.
2516 * The domain of "pma" is assumed to live in the internal schedule domain.
2518 static __isl_give isl_ast_expr
*isl_ast_build_from_pw_multi_aff_internal(
2519 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2520 __isl_take isl_pw_multi_aff
*pma
)
2522 isl_multi_pw_aff
*mpa
;
2524 mpa
= isl_multi_pw_aff_from_pw_multi_aff(pma
);
2525 return isl_ast_build_from_multi_pw_aff_internal(build
, type
, mpa
);
2528 /* Construct an isl_ast_expr of type "type" that calls or accesses
2529 * the element specified by "mpa".
2530 * The first argument is obtained from the output tuple name.
2531 * The remaining arguments are given by the piecewise affine expressions.
2533 * The domain of "mpa" is assumed to live in the external schedule domain.
2535 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff(
2536 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2537 __isl_take isl_multi_pw_aff
*mpa
)
2542 isl_space
*space_build
, *space_mpa
;
2544 space_build
= isl_ast_build_get_space(build
, 0);
2545 space_mpa
= isl_multi_pw_aff_get_space(mpa
);
2546 is_domain
= isl_space_tuple_is_equal(space_build
, isl_dim_set
,
2547 space_mpa
, isl_dim_in
);
2548 isl_space_free(space_build
);
2549 isl_space_free(space_mpa
);
2553 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
2554 "spaces don't match", goto error
);
2556 needs_map
= isl_ast_build_need_schedule_map(build
);
2561 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
2562 mpa
= isl_multi_pw_aff_pullback_multi_aff(mpa
, ma
);
2565 expr
= isl_ast_build_from_multi_pw_aff_internal(build
, type
, mpa
);
2568 isl_multi_pw_aff_free(mpa
);
2572 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2573 * The name of the function is obtained from the output tuple name.
2574 * The arguments are given by the piecewise affine expressions.
2576 * The domain of "mpa" is assumed to live in the external schedule domain.
2578 __isl_give isl_ast_expr
*isl_ast_build_call_from_multi_pw_aff(
2579 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2581 return isl_ast_build_from_multi_pw_aff(build
,
2582 isl_ast_expr_op_call
, mpa
);
2585 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2586 * The name of the array is obtained from the output tuple name.
2587 * The index expressions are given by the piecewise affine expressions.
2589 * The domain of "mpa" is assumed to live in the external schedule domain.
2591 __isl_give isl_ast_expr
*isl_ast_build_access_from_multi_pw_aff(
2592 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2594 return isl_ast_build_from_multi_pw_aff(build
,
2595 isl_ast_expr_op_access
, mpa
);
2598 /* Construct an isl_ast_expr of type "type" that calls or accesses
2599 * the element specified by "pma".
2600 * The first argument is obtained from the output tuple name.
2601 * The remaining arguments are given by the piecewise affine expressions.
2603 * The domain of "pma" is assumed to live in the external schedule domain.
2605 static __isl_give isl_ast_expr
*isl_ast_build_from_pw_multi_aff(
2606 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2607 __isl_take isl_pw_multi_aff
*pma
)
2609 isl_multi_pw_aff
*mpa
;
2611 mpa
= isl_multi_pw_aff_from_pw_multi_aff(pma
);
2612 return isl_ast_build_from_multi_pw_aff(build
, type
, mpa
);
2615 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
2616 * The name of the function is obtained from the output tuple name.
2617 * The arguments are given by the piecewise affine expressions.
2619 * The domain of "pma" is assumed to live in the external schedule domain.
2621 __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff(
2622 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2624 return isl_ast_build_from_pw_multi_aff(build
,
2625 isl_ast_expr_op_call
, pma
);
2628 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
2629 * The name of the array is obtained from the output tuple name.
2630 * The index expressions are given by the piecewise affine expressions.
2632 * The domain of "pma" is assumed to live in the external schedule domain.
2634 __isl_give isl_ast_expr
*isl_ast_build_access_from_pw_multi_aff(
2635 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2637 return isl_ast_build_from_pw_multi_aff(build
,
2638 isl_ast_expr_op_access
, pma
);
2641 /* Construct an isl_ast_expr that calls the domain element
2642 * specified by "executed".
2644 * "executed" is assumed to be single-valued, with a domain that lives
2645 * in the internal schedule space.
2647 __isl_give isl_ast_node
*isl_ast_build_call_from_executed(
2648 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*executed
)
2650 isl_pw_multi_aff
*iteration
;
2653 iteration
= isl_pw_multi_aff_from_map(executed
);
2654 iteration
= isl_ast_build_compute_gist_pw_multi_aff(build
, iteration
);
2655 iteration
= isl_pw_multi_aff_intersect_domain(iteration
,
2656 isl_ast_build_get_domain(build
));
2657 expr
= isl_ast_build_from_pw_multi_aff_internal(build
,
2658 isl_ast_expr_op_call
, iteration
);
2659 return isl_ast_node_alloc_user(expr
);