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 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
151 * The result is simplified in terms of data->build->domain.
152 * This function may change (the sign of) data->v.
154 * "ls" is known to be non-NULL.
156 * Let the div be of the form floor(e/d).
157 * If the ast_build_prefer_pdiv option is set then we check if "e"
158 * is non-negative, so that we can generate
160 * (pdiv_q, expr(e), expr(d))
164 * (fdiv_q, expr(e), expr(d))
166 * If the ast_build_prefer_pdiv option is set and
167 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
168 * If so, we can rewrite
170 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
172 * and still use pdiv_q, while changing the sign of data->v.
174 * Otherwise, we check if
178 * is non-negative and if so, replace floor(e/d) by
180 * floor((e + s*d)/d) - s
182 * with s the minimal shift that makes the argument non-negative.
184 static __isl_give isl_ast_expr
*var_div(struct isl_ast_add_term_data
*data
,
185 __isl_keep isl_local_space
*ls
, int pos
)
187 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
189 isl_ast_expr
*num
, *den
;
191 enum isl_ast_expr_op_type type
;
193 aff
= isl_local_space_get_div(ls
, pos
);
194 d
= isl_aff_get_denominator_val(aff
);
195 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
196 den
= isl_ast_expr_from_val(isl_val_copy(d
));
198 type
= isl_ast_expr_op_fdiv_q
;
199 if (isl_options_get_ast_build_prefer_pdiv(ctx
)) {
201 non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, aff
);
202 if (non_neg
>= 0 && !non_neg
) {
203 isl_aff
*opp
= oppose_div_arg(isl_aff_copy(aff
),
205 non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, opp
);
206 if (non_neg
>= 0 && non_neg
) {
207 data
->v
= isl_val_neg(data
->v
);
213 if (non_neg
>= 0 && !non_neg
) {
214 non_neg
= is_non_neg_after_stealing(aff
, d
, data
);
215 if (non_neg
>= 0 && non_neg
)
216 aff
= steal_from_cst(aff
, d
, data
);
219 aff
= isl_aff_free(aff
);
221 type
= isl_ast_expr_op_pdiv_q
;
225 num
= isl_ast_expr_from_aff(aff
, data
->build
);
226 return isl_ast_expr_alloc_binary(type
, num
, den
);
229 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
230 * The result is simplified in terms of data->build->domain.
231 * This function may change (the sign of) data->v.
233 * The isl_ast_expr is constructed based on the type of the dimension.
234 * - divs are constructed by var_div
235 * - set variables are constructed from the iterator isl_ids in data->build
236 * - parameters are constructed from the isl_ids in "ls"
238 static __isl_give isl_ast_expr
*var(struct isl_ast_add_term_data
*data
,
239 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
)
241 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
244 if (type
== isl_dim_div
)
245 return var_div(data
, ls
, pos
);
247 if (type
== isl_dim_set
) {
248 id
= isl_ast_build_get_iterator_id(data
->build
, pos
);
249 return isl_ast_expr_from_id(id
);
252 if (!isl_local_space_has_dim_id(ls
, type
, pos
))
253 isl_die(ctx
, isl_error_internal
, "unnamed dimension",
255 id
= isl_local_space_get_dim_id(ls
, type
, pos
);
256 return isl_ast_expr_from_id(id
);
259 /* Does "expr" represent the zero integer?
261 static int ast_expr_is_zero(__isl_keep isl_ast_expr
*expr
)
265 if (expr
->type
!= isl_ast_expr_int
)
267 return isl_val_is_zero(expr
->u
.v
);
270 /* Create an expression representing the sum of "expr1" and "expr2",
271 * provided neither of the two expressions is identically zero.
273 static __isl_give isl_ast_expr
*ast_expr_add(__isl_take isl_ast_expr
*expr1
,
274 __isl_take isl_ast_expr
*expr2
)
276 if (!expr1
|| !expr2
)
279 if (ast_expr_is_zero(expr1
)) {
280 isl_ast_expr_free(expr1
);
284 if (ast_expr_is_zero(expr2
)) {
285 isl_ast_expr_free(expr2
);
289 return isl_ast_expr_add(expr1
, expr2
);
291 isl_ast_expr_free(expr1
);
292 isl_ast_expr_free(expr2
);
296 /* Subtract expr2 from expr1.
298 * If expr2 is zero, we simply return expr1.
299 * If expr1 is zero, we return
301 * (isl_ast_expr_op_minus, expr2)
303 * Otherwise, we return
305 * (isl_ast_expr_op_sub, expr1, expr2)
307 static __isl_give isl_ast_expr
*ast_expr_sub(__isl_take isl_ast_expr
*expr1
,
308 __isl_take isl_ast_expr
*expr2
)
310 if (!expr1
|| !expr2
)
313 if (ast_expr_is_zero(expr2
)) {
314 isl_ast_expr_free(expr2
);
318 if (ast_expr_is_zero(expr1
)) {
319 isl_ast_expr_free(expr1
);
320 return isl_ast_expr_neg(expr2
);
323 return isl_ast_expr_sub(expr1
, expr2
);
325 isl_ast_expr_free(expr1
);
326 isl_ast_expr_free(expr2
);
330 /* Return an isl_ast_expr that represents
334 * v is assumed to be non-negative.
335 * The result is simplified in terms of build->domain.
337 static __isl_give isl_ast_expr
*isl_ast_expr_mod(__isl_keep isl_val
*v
,
338 __isl_keep isl_aff
*aff
, __isl_keep isl_val
*d
,
339 __isl_keep isl_ast_build
*build
)
347 expr
= isl_ast_expr_from_aff(isl_aff_copy(aff
), build
);
349 c
= isl_ast_expr_from_val(isl_val_copy(d
));
350 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_r
, expr
, c
);
352 if (!isl_val_is_one(v
)) {
353 c
= isl_ast_expr_from_val(isl_val_copy(v
));
354 expr
= isl_ast_expr_mul(c
, expr
);
360 /* Create an isl_ast_expr that scales "expr" by "v".
362 * If v is 1, we simply return expr.
363 * If v is -1, we return
365 * (isl_ast_expr_op_minus, expr)
367 * Otherwise, we return
369 * (isl_ast_expr_op_mul, expr(v), expr)
371 static __isl_give isl_ast_expr
*scale(__isl_take isl_ast_expr
*expr
,
372 __isl_take isl_val
*v
)
378 if (isl_val_is_one(v
)) {
383 if (isl_val_is_negone(v
)) {
385 expr
= isl_ast_expr_neg(expr
);
387 c
= isl_ast_expr_from_val(v
);
388 expr
= isl_ast_expr_mul(c
, expr
);
394 isl_ast_expr_free(expr
);
398 /* Add an expression for "*v" times the specified dimension of "ls"
400 * If the dimension is an integer division, then this function
401 * may modify data->cst in order to make the numerator non-negative.
402 * The result is simplified in terms of data->build->domain.
404 * Let e be the expression for the specified dimension,
405 * multiplied by the absolute value of "*v".
406 * If "*v" is negative, we create
408 * (isl_ast_expr_op_sub, expr, e)
410 * except when expr is trivially zero, in which case we create
412 * (isl_ast_expr_op_minus, e)
416 * If "*v" is positive, we simply create
418 * (isl_ast_expr_op_add, expr, e)
421 static __isl_give isl_ast_expr
*isl_ast_expr_add_term(
422 __isl_take isl_ast_expr
*expr
,
423 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
,
424 __isl_take isl_val
*v
, struct isl_ast_add_term_data
*data
)
432 term
= var(data
, ls
, type
, pos
);
435 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
437 term
= scale(term
, v
);
438 return ast_expr_sub(expr
, term
);
440 term
= scale(term
, v
);
441 return ast_expr_add(expr
, term
);
445 /* Add an expression for "v" to expr.
447 static __isl_give isl_ast_expr
*isl_ast_expr_add_int(
448 __isl_take isl_ast_expr
*expr
, __isl_take isl_val
*v
)
450 isl_ast_expr
*expr_int
;
455 if (isl_val_is_zero(v
)) {
460 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
462 expr_int
= isl_ast_expr_from_val(v
);
463 return ast_expr_sub(expr
, expr_int
);
465 expr_int
= isl_ast_expr_from_val(v
);
466 return ast_expr_add(expr
, expr_int
);
469 isl_ast_expr_free(expr
);
474 /* Internal data structure used inside extract_modulos.
476 * If any modulo expressions are detected in "aff", then the
477 * expression is removed from "aff" and added to either "pos" or "neg"
478 * depending on the sign of the coefficient of the modulo expression
481 * "add" is an expression that needs to be added to "aff" at the end of
482 * the computation. It is NULL as long as no modulos have been extracted.
484 * "i" is the position in "aff" of the div under investigation
485 * "v" is the coefficient in "aff" of the div
486 * "div" is the argument of the div, with the denominator removed
487 * "d" is the original denominator of the argument of the div
489 * "nonneg" is an affine expression that is non-negative over "build"
490 * and that can be used to extract a modulo expression from "div".
491 * In particular, if "sign" is 1, then the coefficients of "nonneg"
492 * are equal to those of "div" modulo "d". If "sign" is -1, then
493 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
494 * If "sign" is 0, then no such affine expression has been found (yet).
496 struct isl_extract_mod_data
{
497 isl_ast_build
*build
;
518 * represent (a special case of) a test for some linear expression
521 * In particular, is it of the form
527 static isl_bool
is_even_test(struct isl_extract_mod_data
*data
,
528 __isl_keep isl_aff
*arg
)
533 res
= isl_val_eq_si(data
->d
, 2);
537 cst
= isl_aff_get_constant_val(arg
);
538 res
= isl_val_eq_si(cst
, -1);
544 /* Given that data->v * div_i in data->aff is equal to
546 * f * (term - (arg mod d))
548 * with data->d * f = data->v and "arg" non-negative on data->build, add
554 * abs(f) * (arg mod d)
556 * to data->neg or data->pos depending on the sign of -f.
558 * In the special case that "arg mod d" is of the form "(lin - 1) mod 2",
559 * with "lin" some linear expression, first replace
561 * f * (term - ((lin - 1) mod 2))
565 * -f * (1 - term - (lin mod 2))
567 * These two are equal because
569 * ((lin - 1) mod 2) + (lin mod 2) = 1
571 * Also, if "lin - 1" is non-negative, then "lin" is non-negative too.
573 static isl_stat
extract_term_and_mod(struct isl_extract_mod_data
*data
,
574 __isl_take isl_aff
*term
, __isl_take isl_aff
*arg
)
580 even
= is_even_test(data
, arg
);
582 arg
= isl_aff_free(arg
);
584 term
= oppose_div_arg(term
, isl_val_copy(data
->d
));
585 data
->v
= isl_val_neg(data
->v
);
586 arg
= isl_aff_set_constant_si(arg
, 0);
589 data
->v
= isl_val_div(data
->v
, isl_val_copy(data
->d
));
590 s
= isl_val_sgn(data
->v
);
591 data
->v
= isl_val_abs(data
->v
);
592 expr
= isl_ast_expr_mod(data
->v
, arg
, data
->d
, data
->build
);
595 data
->neg
= ast_expr_add(data
->neg
, expr
);
597 data
->pos
= ast_expr_add(data
->pos
, expr
);
598 data
->aff
= isl_aff_set_coefficient_si(data
->aff
,
599 isl_dim_div
, data
->i
, 0);
601 data
->v
= isl_val_neg(data
->v
);
602 term
= isl_aff_scale_val(term
, isl_val_copy(data
->v
));
607 data
->add
= isl_aff_add(data
->add
, term
);
609 return isl_stat_error
;
614 /* Given that data->v * div_i in data->aff is of the form
616 * f * d * floor(div/d)
618 * with div nonnegative on data->build, rewrite it as
620 * f * (div - (div mod d)) = f * div - f * (div mod d)
628 * abs(f) * (div mod d)
630 * to data->neg or data->pos depending on the sign of -f.
632 static isl_stat
extract_mod(struct isl_extract_mod_data
*data
)
634 return extract_term_and_mod(data
, isl_aff_copy(data
->div
),
635 isl_aff_copy(data
->div
));
638 /* Given that data->v * div_i in data->aff is of the form
640 * f * d * floor(div/d) (1)
642 * check if div is non-negative on data->build and, if so,
643 * extract the corresponding modulo from data->aff.
644 * If not, then check if
648 * is non-negative on data->build. If so, replace (1) by
650 * -f * d * floor((-div + d - 1)/d)
652 * and extract the corresponding modulo from data->aff.
654 * This function may modify data->div.
656 static isl_stat
extract_nonneg_mod(struct isl_extract_mod_data
*data
)
660 mod
= isl_ast_build_aff_is_nonneg(data
->build
, data
->div
);
664 return extract_mod(data
);
666 data
->div
= oppose_div_arg(data
->div
, isl_val_copy(data
->d
));
667 mod
= isl_ast_build_aff_is_nonneg(data
->build
, data
->div
);
671 data
->v
= isl_val_neg(data
->v
);
672 return extract_mod(data
);
677 data
->aff
= isl_aff_free(data
->aff
);
678 return isl_stat_error
;
681 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
682 * for use in extracting a modulo expression?
684 * We currently only consider the constant term of the affine expression.
685 * In particular, we prefer the affine expression with the smallest constant
687 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
688 * then we would pick x >= 0
690 * More detailed heuristics could be used if it turns out that there is a need.
692 static int mod_constraint_is_simpler(struct isl_extract_mod_data
*data
,
693 __isl_keep isl_constraint
*c
)
701 v1
= isl_val_abs(isl_constraint_get_constant_val(c
));
702 v2
= isl_val_abs(isl_aff_get_constant_val(data
->nonneg
));
703 simpler
= isl_val_lt(v1
, v2
);
710 /* Check if the coefficients of "c" are either equal or opposite to those
711 * of data->div modulo data->d. If so, and if "c" is "simpler" than
712 * data->nonneg, then replace data->nonneg by the affine expression of "c"
713 * and set data->sign accordingly.
715 * Both "c" and data->div are assumed not to involve any integer divisions.
717 * Before we start the actual comparison, we first quickly check if
718 * "c" and data->div have the same non-zero coefficients.
719 * If not, then we assume that "c" is not of the desired form.
720 * Note that while the coefficients of data->div can be reasonably expected
721 * not to involve any coefficients that are multiples of d, "c" may
722 * very well involve such coefficients. This means that we may actually
725 * If the constant term is "too large", then the constraint is rejected,
726 * where "too large" is fairly arbitrarily set to 1 << 15.
727 * We do this to avoid picking up constraints that bound a variable
728 * by a very large number, say the largest or smallest possible
729 * variable in the representation of some integer type.
731 static isl_stat
check_parallel_or_opposite(__isl_take isl_constraint
*c
,
734 struct isl_extract_mod_data
*data
= user
;
735 enum isl_dim_type c_type
[2] = { isl_dim_param
, isl_dim_set
};
736 enum isl_dim_type a_type
[2] = { isl_dim_param
, isl_dim_in
};
739 int parallel
= 1, opposite
= 1;
741 for (t
= 0; t
< 2; ++t
) {
742 n
[t
] = isl_constraint_dim(c
, c_type
[t
]);
745 for (i
= 0; i
< n
[t
]; ++i
) {
748 a
= isl_constraint_involves_dims(c
, c_type
[t
], i
, 1);
749 b
= isl_aff_involves_dims(data
->div
, a_type
[t
], i
, 1);
751 parallel
= opposite
= 0;
755 if (parallel
|| opposite
) {
758 v
= isl_val_abs(isl_constraint_get_constant_val(c
));
759 if (isl_val_cmp_si(v
, 1 << 15) > 0)
760 parallel
= opposite
= 0;
764 for (t
= 0; t
< 2; ++t
) {
765 for (i
= 0; i
< n
[t
]; ++i
) {
768 if (!parallel
&& !opposite
)
770 v1
= isl_constraint_get_coefficient_val(c
,
772 v2
= isl_aff_get_coefficient_val(data
->div
,
775 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
776 parallel
= isl_val_is_divisible_by(v1
, data
->d
);
777 v1
= isl_val_add(v1
, isl_val_copy(v2
));
780 v1
= isl_val_add(v1
, isl_val_copy(v2
));
781 opposite
= isl_val_is_divisible_by(v1
, data
->d
);
788 if ((parallel
|| opposite
) && mod_constraint_is_simpler(data
, c
)) {
789 isl_aff_free(data
->nonneg
);
790 data
->nonneg
= isl_constraint_get_aff(c
);
791 data
->sign
= parallel
? 1 : -1;
794 isl_constraint_free(c
);
796 if (data
->sign
!= 0 && data
->nonneg
== NULL
)
797 return isl_stat_error
;
801 isl_constraint_free(c
);
802 return isl_stat_error
;
805 /* Given that data->v * div_i in data->aff is of the form
807 * f * d * floor(div/d) (1)
809 * see if we can find an expression div' that is non-negative over data->build
810 * and that is related to div through
816 * div' = -div + d - 1 + d * e
818 * with e some affine expression.
819 * If so, we write (1) as
821 * f * div + f * (div' mod d)
825 * -f * (-div + d - 1) - f * (div' mod d)
827 * exploiting (in the second case) the fact that
829 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
832 * We first try to find an appropriate expression for div'
833 * from the constraints of data->build->domain (which is therefore
834 * guaranteed to be non-negative on data->build), where we remove
835 * any integer divisions from the constraints and skip this step
836 * if "div" itself involves any integer divisions.
837 * If we cannot find an appropriate expression this way, then
838 * we pass control to extract_nonneg_mod where check
839 * if div or "-div + d -1" themselves happen to be
840 * non-negative on data->build.
842 * While looking for an appropriate constraint in data->build->domain,
843 * we ignore the constant term, so after finding such a constraint,
844 * we still need to fix up the constant term.
845 * In particular, if a is the constant term of "div"
846 * (or d - 1 - the constant term of "div" if data->sign < 0)
847 * and b is the constant term of the constraint, then we need to find
848 * a non-negative constant c such that
850 * b + c \equiv a mod d
856 * and add it to b to obtain the constant term of div'.
857 * If this constant term is "too negative", then we add an appropriate
858 * multiple of d to make it positive.
861 * Note that the above is only a very simple heuristic for finding an
862 * appropriate expression. We could try a bit harder by also considering
863 * sums of constraints that involve disjoint sets of variables or
864 * we could consider arbitrary linear combinations of constraints,
865 * although that could potentially be much more expensive as it involves
866 * the solution of an LP problem.
868 * In particular, if v_i is a column vector representing constraint i,
869 * w represents div and e_i is the i-th unit vector, then we are looking
870 * for a solution of the constraints
872 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
874 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
875 * If we are not just interested in a non-negative expression, but
876 * also in one with a minimal range, then we don't just want
877 * c = \sum_i lambda_i v_i to be non-negative over the domain,
878 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
879 * that we want to minimize and we now also have to take into account
880 * the constant terms of the constraints.
881 * Alternatively, we could first compute the dual of the domain
882 * and plug in the constraints on the coefficients.
884 static isl_stat
try_extract_mod(struct isl_extract_mod_data
*data
)
894 n
= isl_aff_dim(data
->div
, isl_dim_div
);
898 if (isl_aff_involves_dims(data
->div
, isl_dim_div
, 0, n
))
899 return extract_nonneg_mod(data
);
901 hull
= isl_set_simple_hull(isl_set_copy(data
->build
->domain
));
902 hull
= isl_basic_set_remove_divs(hull
);
905 r
= isl_basic_set_foreach_constraint(hull
, &check_parallel_or_opposite
,
907 isl_basic_set_free(hull
);
909 if (!data
->sign
|| r
< 0) {
910 isl_aff_free(data
->nonneg
);
913 return extract_nonneg_mod(data
);
916 v1
= isl_aff_get_constant_val(data
->div
);
917 v2
= isl_aff_get_constant_val(data
->nonneg
);
918 if (data
->sign
< 0) {
919 v1
= isl_val_neg(v1
);
920 v1
= isl_val_add(v1
, isl_val_copy(data
->d
));
921 v1
= isl_val_sub_ui(v1
, 1);
923 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
924 v1
= isl_val_mod(v1
, isl_val_copy(data
->d
));
925 v1
= isl_val_add(v1
, v2
);
926 v2
= isl_val_div(isl_val_copy(v1
), isl_val_copy(data
->d
));
927 v2
= isl_val_ceil(v2
);
928 if (isl_val_is_neg(v2
)) {
929 v2
= isl_val_mul(v2
, isl_val_copy(data
->d
));
930 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
932 data
->nonneg
= isl_aff_set_constant_val(data
->nonneg
, v1
);
935 if (data
->sign
< 0) {
936 data
->div
= oppose_div_arg(data
->div
, isl_val_copy(data
->d
));
937 data
->v
= isl_val_neg(data
->v
);
940 return extract_term_and_mod(data
,
941 isl_aff_copy(data
->div
), data
->nonneg
);
943 data
->aff
= isl_aff_free(data
->aff
);
944 return isl_stat_error
;
947 /* Check if "data->aff" involves any (implicit) modulo computations based
949 * If so, remove them from aff and add expressions corresponding
950 * to those modulo computations to data->pos and/or data->neg.
952 * "aff" is assumed to be an integer affine expression.
954 * In particular, check if (v * div_j) is of the form
956 * f * m * floor(a / m)
958 * and, if so, rewrite it as
960 * f * (a - (a mod m)) = f * a - f * (a mod m)
962 * and extract out -f * (a mod m).
963 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
964 * If f < 0, we add ((-f) * (a mod m)) to *pos.
966 * Note that in order to represent "a mod m" as
968 * (isl_ast_expr_op_pdiv_r, a, m)
970 * we need to make sure that a is non-negative.
971 * If not, we check if "-a + m - 1" is non-negative.
972 * If so, we can rewrite
974 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
976 * and still extract a modulo.
978 static int extract_modulo(struct isl_extract_mod_data
*data
)
980 data
->div
= isl_aff_get_div(data
->aff
, data
->i
);
981 data
->d
= isl_aff_get_denominator_val(data
->div
);
982 if (isl_val_is_divisible_by(data
->v
, data
->d
)) {
983 data
->div
= isl_aff_scale_val(data
->div
, isl_val_copy(data
->d
));
984 if (try_extract_mod(data
) < 0)
985 data
->aff
= isl_aff_free(data
->aff
);
987 isl_aff_free(data
->div
);
988 isl_val_free(data
->d
);
992 /* Check if "aff" involves any (implicit) modulo computations.
993 * If so, remove them from aff and add expressions corresponding
994 * to those modulo computations to *pos and/or *neg.
995 * We only do this if the option ast_build_prefer_pdiv is set.
997 * "aff" is assumed to be an integer affine expression.
999 * A modulo expression is of the form
1001 * a mod m = a - m * floor(a / m)
1003 * To detect them in aff, we look for terms of the form
1005 * f * m * floor(a / m)
1009 * f * (a - (a mod m)) = f * a - f * (a mod m)
1011 * and extract out -f * (a mod m).
1012 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
1013 * If f < 0, we add ((-f) * (a mod m)) to *pos.
1015 static __isl_give isl_aff
*extract_modulos(__isl_take isl_aff
*aff
,
1016 __isl_keep isl_ast_expr
**pos
, __isl_keep isl_ast_expr
**neg
,
1017 __isl_keep isl_ast_build
*build
)
1019 struct isl_extract_mod_data data
= { build
, aff
, *pos
, *neg
};
1026 ctx
= isl_aff_get_ctx(aff
);
1027 if (!isl_options_get_ast_build_prefer_pdiv(ctx
))
1030 n
= isl_aff_dim(data
.aff
, isl_dim_div
);
1032 return isl_aff_free(aff
);
1033 for (data
.i
= 0; data
.i
< n
; ++data
.i
) {
1034 data
.v
= isl_aff_get_coefficient_val(data
.aff
,
1035 isl_dim_div
, data
.i
);
1037 return isl_aff_free(aff
);
1038 if (isl_val_is_zero(data
.v
) ||
1039 isl_val_is_one(data
.v
) || isl_val_is_negone(data
.v
)) {
1040 isl_val_free(data
.v
);
1043 if (extract_modulo(&data
) < 0)
1044 data
.aff
= isl_aff_free(data
.aff
);
1045 isl_val_free(data
.v
);
1051 data
.aff
= isl_aff_add(data
.aff
, data
.add
);
1058 /* Check if aff involves any non-integer coefficients.
1059 * If so, split aff into
1061 * aff = aff1 + (aff2 / d)
1063 * with both aff1 and aff2 having only integer coefficients.
1064 * Return aff1 and add (aff2 / d) to *expr.
1066 static __isl_give isl_aff
*extract_rational(__isl_take isl_aff
*aff
,
1067 __isl_keep isl_ast_expr
**expr
, __isl_keep isl_ast_build
*build
)
1071 isl_aff
*rat
= NULL
;
1072 isl_local_space
*ls
= NULL
;
1073 isl_ast_expr
*rat_expr
;
1075 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1076 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1080 d
= isl_aff_get_denominator_val(aff
);
1083 if (isl_val_is_one(d
)) {
1088 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
1090 ls
= isl_aff_get_domain_local_space(aff
);
1091 rat
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1093 for (i
= 0; i
< 3; ++i
) {
1094 n
= isl_aff_dim(aff
, t
[i
]);
1097 for (j
= 0; j
< n
; ++j
) {
1100 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1103 if (isl_val_is_divisible_by(v
, d
)) {
1107 rat_j
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1109 rat_j
= isl_aff_scale_val(rat_j
, v
);
1110 rat
= isl_aff_add(rat
, rat_j
);
1114 v
= isl_aff_get_constant_val(aff
);
1115 if (isl_val_is_divisible_by(v
, d
)) {
1120 rat_0
= isl_aff_val_on_domain(isl_local_space_copy(ls
), v
);
1121 rat
= isl_aff_add(rat
, rat_0
);
1124 isl_local_space_free(ls
);
1126 aff
= isl_aff_sub(aff
, isl_aff_copy(rat
));
1127 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(d
));
1129 rat_expr
= isl_ast_expr_from_aff(rat
, build
);
1130 rat_expr
= isl_ast_expr_div(rat_expr
, isl_ast_expr_from_val(d
));
1131 *expr
= ast_expr_add(*expr
, rat_expr
);
1136 isl_local_space_free(ls
);
1142 /* Construct an isl_ast_expr that evaluates the affine expression "aff".
1143 * The result is simplified in terms of build->domain.
1145 * We first extract hidden modulo computations from the affine expression
1146 * and then add terms for each variable with a non-zero coefficient.
1147 * Finally, if the affine expression has a non-trivial denominator,
1148 * we divide the resulting isl_ast_expr by this denominator.
1150 __isl_give isl_ast_expr
*isl_ast_expr_from_aff(__isl_take isl_aff
*aff
,
1151 __isl_keep isl_ast_build
*build
)
1156 isl_ctx
*ctx
= isl_aff_get_ctx(aff
);
1157 isl_ast_expr
*expr
, *expr_neg
;
1158 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1159 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1160 isl_local_space
*ls
;
1161 struct isl_ast_add_term_data data
;
1166 expr
= isl_ast_expr_alloc_int_si(ctx
, 0);
1167 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
1169 aff
= extract_rational(aff
, &expr
, build
);
1171 aff
= extract_modulos(aff
, &expr
, &expr_neg
, build
);
1172 expr
= ast_expr_sub(expr
, expr_neg
);
1174 ls
= isl_aff_get_domain_local_space(aff
);
1177 data
.cst
= isl_aff_get_constant_val(aff
);
1178 for (i
= 0; i
< 3; ++i
) {
1179 n
= isl_aff_dim(aff
, t
[i
]);
1181 expr
= isl_ast_expr_free(expr
);
1182 for (j
= 0; j
< n
; ++j
) {
1183 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1185 expr
= isl_ast_expr_free(expr
);
1186 if (isl_val_is_zero(v
)) {
1190 expr
= isl_ast_expr_add_term(expr
,
1191 ls
, l
[i
], j
, v
, &data
);
1195 expr
= isl_ast_expr_add_int(expr
, data
.cst
);
1197 isl_local_space_free(ls
);
1202 /* Add terms to "expr" for each variable in "aff" with a coefficient
1203 * with sign equal to "sign".
1204 * The result is simplified in terms of data->build->domain.
1206 static __isl_give isl_ast_expr
*add_signed_terms(__isl_take isl_ast_expr
*expr
,
1207 __isl_keep isl_aff
*aff
, int sign
, struct isl_ast_add_term_data
*data
)
1211 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1212 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1213 isl_local_space
*ls
;
1215 ls
= isl_aff_get_domain_local_space(aff
);
1217 for (i
= 0; i
< 3; ++i
) {
1218 isl_size n
= isl_aff_dim(aff
, t
[i
]);
1220 expr
= isl_ast_expr_free(expr
);
1221 for (j
= 0; j
< n
; ++j
) {
1222 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1223 if (sign
* isl_val_sgn(v
) <= 0) {
1228 expr
= isl_ast_expr_add_term(expr
,
1229 ls
, l
[i
], j
, v
, data
);
1233 isl_local_space_free(ls
);
1238 /* Should the constant term "v" be considered positive?
1240 * A positive constant will be added to "pos" by the caller,
1241 * while a negative constant will be added to "neg".
1242 * If either "pos" or "neg" is exactly zero, then we prefer
1243 * to add the constant "v" to that side, irrespective of the sign of "v".
1244 * This results in slightly shorter expressions and may reduce the risk
1247 static int constant_is_considered_positive(__isl_keep isl_val
*v
,
1248 __isl_keep isl_ast_expr
*pos
, __isl_keep isl_ast_expr
*neg
)
1250 if (ast_expr_is_zero(pos
))
1252 if (ast_expr_is_zero(neg
))
1254 return isl_val_is_pos(v
);
1257 /* Check if the equality
1261 * represents a stride constraint on the integer division "pos".
1263 * In particular, if the integer division "pos" is equal to
1267 * then check if aff is equal to
1273 * If so, the equality is exactly
1277 * Note that in principle we could also accept
1281 * where e and e' differ by a constant.
1283 static int is_stride_constraint(__isl_keep isl_aff
*aff
, int pos
)
1289 div
= isl_aff_get_div(aff
, pos
);
1290 c
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, pos
);
1291 d
= isl_aff_get_denominator_val(div
);
1292 eq
= isl_val_abs_eq(c
, d
);
1293 if (eq
>= 0 && eq
) {
1294 aff
= isl_aff_copy(aff
);
1295 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, pos
, 0);
1296 div
= isl_aff_scale_val(div
, d
);
1297 if (isl_val_is_pos(c
))
1298 div
= isl_aff_neg(div
);
1299 eq
= isl_aff_plain_is_equal(div
, aff
);
1309 /* Are all coefficients of "aff" (zero or) negative?
1311 static isl_bool
all_negative_coefficients(__isl_keep isl_aff
*aff
)
1316 n
= isl_aff_dim(aff
, isl_dim_param
);
1318 return isl_bool_error
;
1319 for (i
= 0; i
< n
; ++i
)
1320 if (isl_aff_coefficient_sgn(aff
, isl_dim_param
, i
) > 0)
1321 return isl_bool_false
;
1323 n
= isl_aff_dim(aff
, isl_dim_in
);
1325 return isl_bool_error
;
1326 for (i
= 0; i
< n
; ++i
)
1327 if (isl_aff_coefficient_sgn(aff
, isl_dim_in
, i
) > 0)
1328 return isl_bool_false
;
1330 return isl_bool_true
;
1333 /* Give an equality of the form
1335 * aff = e - d floor(e/d) = 0
1339 * aff = -e + d floor(e/d) = 0
1341 * with the integer division "pos" equal to floor(e/d),
1342 * construct the AST expression
1344 * (isl_ast_expr_op_eq,
1345 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1347 * If e only has negative coefficients, then construct
1349 * (isl_ast_expr_op_eq,
1350 * (isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))
1354 static __isl_give isl_ast_expr
*extract_stride_constraint(
1355 __isl_take isl_aff
*aff
, int pos
, __isl_keep isl_ast_build
*build
)
1360 isl_ast_expr
*expr
, *cst
;
1365 ctx
= isl_aff_get_ctx(aff
);
1367 c
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, pos
);
1368 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, pos
, 0);
1370 all_neg
= all_negative_coefficients(aff
);
1372 aff
= isl_aff_free(aff
);
1374 aff
= isl_aff_neg(aff
);
1376 cst
= isl_ast_expr_from_val(isl_val_abs(c
));
1377 expr
= isl_ast_expr_from_aff(aff
, build
);
1379 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_zdiv_r
, expr
, cst
);
1380 cst
= isl_ast_expr_alloc_int_si(ctx
, 0);
1381 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_eq
, expr
, cst
);
1386 /* Construct an isl_ast_expr that evaluates the condition "constraint".
1387 * The result is simplified in terms of build->domain.
1389 * We first check if the constraint is an equality of the form
1391 * e - d floor(e/d) = 0
1397 * If so, we convert it to
1399 * (isl_ast_expr_op_eq,
1400 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1402 * Otherwise, let the constraint by either "a >= 0" or "a == 0".
1403 * We first extract hidden modulo computations from "a"
1404 * and then collect all the terms with a positive coefficient in cons_pos
1405 * and the terms with a negative coefficient in cons_neg.
1407 * The result is then of the form
1409 * (isl_ast_expr_op_ge, expr(pos), expr(-neg)))
1413 * (isl_ast_expr_op_eq, expr(pos), expr(-neg)))
1415 * However, if the first expression is an integer constant (and the second
1416 * is not), then we swap the two expressions. This ensures that we construct,
1417 * e.g., "i <= 5" rather than "5 >= i".
1419 * Furthermore, if there are no terms with positive coefficients (or no terms
1420 * with negative coefficients), then the constant term is added to "pos"
1421 * (or "neg"), ignoring the sign of the constant term.
1423 static __isl_give isl_ast_expr
*isl_ast_expr_from_constraint(
1424 __isl_take isl_constraint
*constraint
, __isl_keep isl_ast_build
*build
)
1429 isl_ast_expr
*expr_pos
;
1430 isl_ast_expr
*expr_neg
;
1434 enum isl_ast_expr_op_type type
;
1435 struct isl_ast_add_term_data data
;
1440 aff
= isl_constraint_get_aff(constraint
);
1441 eq
= isl_constraint_is_equality(constraint
);
1442 isl_constraint_free(constraint
);
1444 n
= isl_aff_dim(aff
, isl_dim_div
);
1446 aff
= isl_aff_free(aff
);
1448 for (i
= 0; i
< n
; ++i
) {
1450 is_stride
= is_stride_constraint(aff
, i
);
1454 return extract_stride_constraint(aff
, i
, build
);
1457 ctx
= isl_aff_get_ctx(aff
);
1458 expr_pos
= isl_ast_expr_alloc_int_si(ctx
, 0);
1459 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
1461 aff
= extract_modulos(aff
, &expr_pos
, &expr_neg
, build
);
1464 data
.cst
= isl_aff_get_constant_val(aff
);
1465 expr_pos
= add_signed_terms(expr_pos
, aff
, 1, &data
);
1466 data
.cst
= isl_val_neg(data
.cst
);
1467 expr_neg
= add_signed_terms(expr_neg
, aff
, -1, &data
);
1468 data
.cst
= isl_val_neg(data
.cst
);
1470 if (constant_is_considered_positive(data
.cst
, expr_pos
, expr_neg
)) {
1471 expr_pos
= isl_ast_expr_add_int(expr_pos
, data
.cst
);
1473 data
.cst
= isl_val_neg(data
.cst
);
1474 expr_neg
= isl_ast_expr_add_int(expr_neg
, data
.cst
);
1477 if (isl_ast_expr_get_type(expr_pos
) == isl_ast_expr_int
&&
1478 isl_ast_expr_get_type(expr_neg
) != isl_ast_expr_int
) {
1479 type
= eq
? isl_ast_expr_op_eq
: isl_ast_expr_op_le
;
1480 expr
= isl_ast_expr_alloc_binary(type
, expr_neg
, expr_pos
);
1482 type
= eq
? isl_ast_expr_op_eq
: isl_ast_expr_op_ge
;
1483 expr
= isl_ast_expr_alloc_binary(type
, expr_pos
, expr_neg
);
1493 /* Wrapper around isl_constraint_cmp_last_non_zero for use
1494 * as a callback to isl_constraint_list_sort.
1495 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1496 * apart, then use isl_constraint_plain_cmp instead.
1498 static int cmp_constraint(__isl_keep isl_constraint
*a
,
1499 __isl_keep isl_constraint
*b
, void *user
)
1503 cmp
= isl_constraint_cmp_last_non_zero(a
, b
);
1506 return isl_constraint_plain_cmp(a
, b
);
1509 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1510 * The result is simplified in terms of build->domain.
1512 * If "bset" is not bounded by any constraint, then we construct
1513 * the expression "1", i.e., "true".
1515 * Otherwise, we sort the constraints, putting constraints that involve
1516 * integer divisions after those that do not, and construct an "and"
1517 * of the ast expressions of the individual constraints.
1519 * Each constraint is added to the generated constraints of the build
1520 * after it has been converted to an AST expression so that it can be used
1521 * to simplify the following constraints. This may change the truth value
1522 * of subsequent constraints that do not satisfy the earlier constraints,
1523 * but this does not affect the outcome of the conjunction as it is
1524 * only true if all the conjuncts are true (no matter in what order
1525 * they are evaluated). In particular, the constraints that do not
1526 * involve integer divisions may serve to simplify some constraints
1527 * that do involve integer divisions.
1529 __isl_give isl_ast_expr
*isl_ast_build_expr_from_basic_set(
1530 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
1535 isl_constraint_list
*list
;
1539 list
= isl_basic_set_get_constraint_list(bset
);
1540 isl_basic_set_free(bset
);
1541 list
= isl_constraint_list_sort(list
, &cmp_constraint
, NULL
);
1542 n
= isl_constraint_list_n_constraint(list
);
1546 isl_ctx
*ctx
= isl_constraint_list_get_ctx(list
);
1547 isl_constraint_list_free(list
);
1548 return isl_ast_expr_alloc_int_si(ctx
, 1);
1551 build
= isl_ast_build_copy(build
);
1553 c
= isl_constraint_list_get_constraint(list
, 0);
1554 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
1555 set
= isl_set_from_basic_set(bset
);
1556 res
= isl_ast_expr_from_constraint(c
, build
);
1557 build
= isl_ast_build_restrict_generated(build
, set
);
1559 for (i
= 1; i
< n
; ++i
) {
1562 c
= isl_constraint_list_get_constraint(list
, i
);
1563 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
1564 set
= isl_set_from_basic_set(bset
);
1565 expr
= isl_ast_expr_from_constraint(c
, build
);
1566 build
= isl_ast_build_restrict_generated(build
, set
);
1567 res
= isl_ast_expr_and(res
, expr
);
1570 isl_constraint_list_free(list
);
1571 isl_ast_build_free(build
);
1575 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1576 * The result is simplified in terms of build->domain.
1578 * If "set" is an (obviously) empty set, then return the expression "0".
1580 * If there are multiple disjuncts in the description of the set,
1581 * then subsequent disjuncts are simplified in a context where
1582 * the previous disjuncts have been removed from build->domain.
1583 * In particular, constraints that ensure that there is no overlap
1584 * with these previous disjuncts, can be removed.
1585 * This is mostly useful for disjuncts that are only defined by
1586 * a single constraint (relative to the build domain) as the opposite
1587 * of that single constraint can then be removed from the other disjuncts.
1588 * In order not to increase the number of disjuncts in the build domain
1589 * after subtracting the previous disjuncts of "set", the simple hull
1590 * is computed after taking the difference with each of these disjuncts.
1591 * This means that constraints that prevent overlap with a union
1592 * of multiple previous disjuncts are not removed.
1594 * "set" lives in the internal schedule space.
1596 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set_internal(
1597 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1601 isl_basic_set
*bset
;
1602 isl_basic_set_list
*list
;
1606 list
= isl_set_get_basic_set_list(set
);
1609 n
= isl_basic_set_list_n_basic_set(list
);
1613 isl_ctx
*ctx
= isl_ast_build_get_ctx(build
);
1614 isl_basic_set_list_free(list
);
1615 return isl_ast_expr_from_val(isl_val_zero(ctx
));
1618 domain
= isl_ast_build_get_domain(build
);
1620 bset
= isl_basic_set_list_get_basic_set(list
, 0);
1621 set
= isl_set_from_basic_set(isl_basic_set_copy(bset
));
1622 res
= isl_ast_build_expr_from_basic_set(build
, bset
);
1624 for (i
= 1; i
< n
; ++i
) {
1628 rest
= isl_set_subtract(isl_set_copy(domain
), set
);
1629 rest
= isl_set_from_basic_set(isl_set_simple_hull(rest
));
1630 domain
= isl_set_intersect(domain
, rest
);
1631 bset
= isl_basic_set_list_get_basic_set(list
, i
);
1632 set
= isl_set_from_basic_set(isl_basic_set_copy(bset
));
1633 bset
= isl_basic_set_gist(bset
,
1634 isl_set_simple_hull(isl_set_copy(domain
)));
1635 expr
= isl_ast_build_expr_from_basic_set(build
, bset
);
1636 res
= isl_ast_expr_or(res
, expr
);
1639 isl_set_free(domain
);
1641 isl_basic_set_list_free(list
);
1645 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1646 * The result is simplified in terms of build->domain.
1648 * If "set" is an (obviously) empty set, then return the expression "0".
1650 * "set" lives in the external schedule space.
1652 * The internal AST expression generation assumes that there are
1653 * no unknown divs, so make sure an explicit representation is available.
1654 * Since the set comes from the outside, it may have constraints that
1655 * are redundant with respect to the build domain. Remove them first.
1657 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set(
1658 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1662 needs_map
= isl_ast_build_need_schedule_map(build
);
1663 if (needs_map
< 0) {
1664 set
= isl_set_free(set
);
1665 } else if (needs_map
) {
1667 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
1668 set
= isl_set_preimage_multi_aff(set
, ma
);
1671 set
= isl_set_compute_divs(set
);
1672 set
= isl_ast_build_compute_gist(build
, set
);
1673 return isl_ast_build_expr_from_set_internal(build
, set
);
1676 /* State of data about previous pieces in
1677 * isl_ast_build_expr_from_pw_aff_internal.
1679 * isl_state_none: no data about previous pieces
1680 * isl_state_single: data about a single previous piece
1681 * isl_state_min: data represents minimum of several pieces
1682 * isl_state_max: data represents maximum of several pieces
1684 enum isl_from_pw_aff_state
{
1691 /* Internal date structure representing a single piece in the input of
1692 * isl_ast_build_expr_from_pw_aff_internal.
1694 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1695 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1696 * single previous subpiece.
1697 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
1698 * a sequence of several previous subpieces that are equal to the minimum
1699 * of the entries in "aff_list" over the union of "set_list"
1700 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
1701 * a sequence of several previous subpieces that are equal to the maximum
1702 * of the entries in "aff_list" over the union of "set_list"
1704 * During the construction of the pieces, "set" is NULL.
1705 * After the construction, "set" is set to the union of the elements
1706 * in "set_list", at which point "set_list" is set to NULL.
1708 struct isl_from_pw_aff_piece
{
1709 enum isl_from_pw_aff_state state
;
1711 isl_set_list
*set_list
;
1712 isl_aff_list
*aff_list
;
1715 /* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1717 * "build" specifies the domain against which the result is simplified.
1718 * "dom" is the domain of the entire isl_pw_aff.
1720 * "n" is the number of pieces constructed already.
1721 * In particular, during the construction of the pieces, "n" points to
1722 * the piece that is being constructed. After the construction of the
1723 * pieces, "n" is set to the total number of pieces.
1724 * "max" is the total number of allocated entries.
1725 * "p" contains the individual pieces.
1727 struct isl_from_pw_aff_data
{
1728 isl_ast_build
*build
;
1733 struct isl_from_pw_aff_piece
*p
;
1736 /* Initialize "data" based on "build" and "pa".
1738 static isl_stat
isl_from_pw_aff_data_init(struct isl_from_pw_aff_data
*data
,
1739 __isl_keep isl_ast_build
*build
, __isl_keep isl_pw_aff
*pa
)
1744 ctx
= isl_pw_aff_get_ctx(pa
);
1745 n
= isl_pw_aff_n_piece(pa
);
1747 return isl_stat_error
;
1749 isl_die(ctx
, isl_error_invalid
,
1750 "cannot handle void expression", return isl_stat_error
);
1752 data
->p
= isl_calloc_array(ctx
, struct isl_from_pw_aff_piece
, n
);
1754 return isl_stat_error
;
1755 data
->build
= build
;
1756 data
->dom
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1762 /* Free all memory allocated for "data".
1764 static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data
*data
)
1768 isl_set_free(data
->dom
);
1772 for (i
= 0; i
< data
->max
; ++i
) {
1773 isl_set_free(data
->p
[i
].set
);
1774 isl_set_list_free(data
->p
[i
].set_list
);
1775 isl_aff_list_free(data
->p
[i
].aff_list
);
1780 /* Initialize the current entry of "data" to an unused piece.
1782 static void set_none(struct isl_from_pw_aff_data
*data
)
1784 data
->p
[data
->n
].state
= isl_state_none
;
1785 data
->p
[data
->n
].set_list
= NULL
;
1786 data
->p
[data
->n
].aff_list
= NULL
;
1789 /* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1791 static void set_single(struct isl_from_pw_aff_data
*data
,
1792 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1794 data
->p
[data
->n
].state
= isl_state_single
;
1795 data
->p
[data
->n
].set_list
= isl_set_list_from_set(set
);
1796 data
->p
[data
->n
].aff_list
= isl_aff_list_from_aff(aff
);
1799 /* Extend the current entry of "data" with "set" and "aff"
1800 * as a minimum expression.
1802 static isl_stat
extend_min(struct isl_from_pw_aff_data
*data
,
1803 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1806 data
->p
[n
].state
= isl_state_min
;
1807 data
->p
[n
].set_list
= isl_set_list_add(data
->p
[n
].set_list
, set
);
1808 data
->p
[n
].aff_list
= isl_aff_list_add(data
->p
[n
].aff_list
, aff
);
1810 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1811 return isl_stat_error
;
1815 /* Extend the current entry of "data" with "set" and "aff"
1816 * as a maximum expression.
1818 static isl_stat
extend_max(struct isl_from_pw_aff_data
*data
,
1819 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1822 data
->p
[n
].state
= isl_state_max
;
1823 data
->p
[n
].set_list
= isl_set_list_add(data
->p
[n
].set_list
, set
);
1824 data
->p
[n
].aff_list
= isl_aff_list_add(data
->p
[n
].aff_list
, aff
);
1826 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1827 return isl_stat_error
;
1831 /* Extend the domain of the current entry of "data", which is assumed
1832 * to contain a single subpiece, with "set". If "replace" is set,
1833 * then also replace the affine function by "aff". Otherwise,
1834 * simply free "aff".
1836 static isl_stat
extend_domain(struct isl_from_pw_aff_data
*data
,
1837 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
, int replace
)
1842 set_n
= isl_set_list_get_set(data
->p
[n
].set_list
, 0);
1843 set_n
= isl_set_union(set_n
, set
);
1844 data
->p
[n
].set_list
=
1845 isl_set_list_set_set(data
->p
[n
].set_list
, 0, set_n
);
1848 data
->p
[n
].aff_list
=
1849 isl_aff_list_set_aff(data
->p
[n
].aff_list
, 0, aff
);
1853 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1854 return isl_stat_error
;
1858 /* Construct an isl_ast_expr from "list" within "build".
1859 * If "state" is isl_state_single, then "list" contains a single entry and
1860 * an isl_ast_expr is constructed for that entry.
1861 * Otherwise a min or max expression is constructed from "list"
1862 * depending on "state".
1864 static __isl_give isl_ast_expr
*ast_expr_from_aff_list(
1865 __isl_take isl_aff_list
*list
, enum isl_from_pw_aff_state state
,
1866 __isl_keep isl_ast_build
*build
)
1871 isl_ast_expr
*expr
= NULL
;
1872 enum isl_ast_expr_op_type op_type
;
1874 if (state
== isl_state_single
) {
1875 aff
= isl_aff_list_get_aff(list
, 0);
1876 isl_aff_list_free(list
);
1877 return isl_ast_expr_from_aff(aff
, build
);
1879 n
= isl_aff_list_n_aff(list
);
1882 op_type
= state
== isl_state_min
? isl_ast_expr_op_min
1883 : isl_ast_expr_op_max
;
1884 expr
= isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build
), op_type
, n
);
1888 for (i
= 0; i
< n
; ++i
) {
1889 isl_ast_expr
*expr_i
;
1891 aff
= isl_aff_list_get_aff(list
, i
);
1892 expr_i
= isl_ast_expr_from_aff(aff
, build
);
1895 expr
->u
.op
.args
[i
] = expr_i
;
1898 isl_aff_list_free(list
);
1901 isl_aff_list_free(list
);
1902 isl_ast_expr_free(expr
);
1906 /* Extend the expression in "next" to take into account
1907 * the piece at position "pos" in "data", allowing for a further extension
1908 * for the next piece(s).
1909 * In particular, "next" is set to a select operation that selects
1910 * an isl_ast_expr corresponding to data->aff_list on data->set and
1911 * to an expression that will be filled in by later calls.
1912 * Return a pointer to this location.
1913 * Afterwards, the state of "data" is set to isl_state_none.
1915 * The constraints of data->set are added to the generated
1916 * constraints of the build such that they can be exploited to simplify
1917 * the AST expression constructed from data->aff_list.
1919 static isl_ast_expr
**add_intermediate_piece(struct isl_from_pw_aff_data
*data
,
1920 int pos
, isl_ast_expr
**next
)
1923 isl_ast_build
*build
;
1924 isl_ast_expr
*ternary
, *arg
;
1925 isl_set
*set
, *gist
;
1927 set
= data
->p
[pos
].set
;
1928 data
->p
[pos
].set
= NULL
;
1929 ctx
= isl_ast_build_get_ctx(data
->build
);
1930 ternary
= isl_ast_expr_alloc_op(ctx
, isl_ast_expr_op_select
, 3);
1931 gist
= isl_set_gist(isl_set_copy(set
), isl_set_copy(data
->dom
));
1932 arg
= isl_ast_build_expr_from_set_internal(data
->build
, gist
);
1933 ternary
= isl_ast_expr_set_op_arg(ternary
, 0, arg
);
1934 build
= isl_ast_build_copy(data
->build
);
1935 build
= isl_ast_build_restrict_generated(build
, set
);
1936 arg
= ast_expr_from_aff_list(data
->p
[pos
].aff_list
,
1937 data
->p
[pos
].state
, build
);
1938 data
->p
[pos
].aff_list
= NULL
;
1939 isl_ast_build_free(build
);
1940 ternary
= isl_ast_expr_set_op_arg(ternary
, 1, arg
);
1941 data
->p
[pos
].state
= isl_state_none
;
1946 return &ternary
->u
.op
.args
[2];
1949 /* Extend the expression in "next" to take into account
1950 * the final piece, located at position "pos" in "data".
1951 * In particular, "next" is set to evaluate data->aff_list
1952 * and the domain is ignored.
1953 * Return isl_stat_ok on success and isl_stat_error on failure.
1955 * The constraints of data->set are however added to the generated
1956 * constraints of the build such that they can be exploited to simplify
1957 * the AST expression constructed from data->aff_list.
1959 static isl_stat
add_last_piece(struct isl_from_pw_aff_data
*data
,
1960 int pos
, isl_ast_expr
**next
)
1962 isl_ast_build
*build
;
1964 if (data
->p
[pos
].state
== isl_state_none
)
1965 isl_die(isl_ast_build_get_ctx(data
->build
), isl_error_invalid
,
1966 "cannot handle void expression", return isl_stat_error
);
1968 build
= isl_ast_build_copy(data
->build
);
1969 build
= isl_ast_build_restrict_generated(build
, data
->p
[pos
].set
);
1970 data
->p
[pos
].set
= NULL
;
1971 *next
= ast_expr_from_aff_list(data
->p
[pos
].aff_list
,
1972 data
->p
[pos
].state
, build
);
1973 data
->p
[pos
].aff_list
= NULL
;
1974 isl_ast_build_free(build
);
1975 data
->p
[pos
].state
= isl_state_none
;
1977 return isl_stat_error
;
1982 /* Return -1 if the piece "p1" should be sorted before "p2"
1983 * and 1 if it should be sorted after "p2".
1984 * Return 0 if they do not need to be sorted in a specific order.
1986 * Pieces are sorted according to the number of disjuncts
1989 static int sort_pieces_cmp(const void *p1
, const void *p2
, void *arg
)
1991 const struct isl_from_pw_aff_piece
*piece1
= p1
;
1992 const struct isl_from_pw_aff_piece
*piece2
= p2
;
1995 n1
= isl_set_n_basic_set(piece1
->set
);
1996 n2
= isl_set_n_basic_set(piece2
->set
);
2001 /* Construct an isl_ast_expr from the pieces in "data".
2002 * Return the result or NULL on failure.
2004 * When this function is called, data->n points to the current piece.
2005 * If this is an effective piece, then first increment data->n such
2006 * that data->n contains the number of pieces.
2007 * The "set_list" fields are subsequently replaced by the corresponding
2008 * "set" fields, after which the pieces are sorted according to
2009 * the number of disjuncts in these "set" fields.
2011 * Construct intermediate AST expressions for the initial pieces and
2012 * finish off with the final pieces.
2014 static isl_ast_expr
*build_pieces(struct isl_from_pw_aff_data
*data
)
2017 isl_ast_expr
*res
= NULL
;
2018 isl_ast_expr
**next
= &res
;
2020 if (data
->p
[data
->n
].state
!= isl_state_none
)
2023 isl_die(isl_ast_build_get_ctx(data
->build
), isl_error_invalid
,
2024 "cannot handle void expression", return NULL
);
2026 for (i
= 0; i
< data
->n
; ++i
) {
2027 data
->p
[i
].set
= isl_set_list_union(data
->p
[i
].set_list
);
2028 if (data
->p
[i
].state
!= isl_state_single
)
2029 data
->p
[i
].set
= isl_set_coalesce(data
->p
[i
].set
);
2030 data
->p
[i
].set_list
= NULL
;
2033 if (isl_sort(data
->p
, data
->n
, sizeof(data
->p
[0]),
2034 &sort_pieces_cmp
, NULL
) < 0)
2035 return isl_ast_expr_free(res
);
2037 for (i
= 0; i
+ 1 < data
->n
; ++i
) {
2038 next
= add_intermediate_piece(data
, i
, next
);
2040 return isl_ast_expr_free(res
);
2043 if (add_last_piece(data
, data
->n
- 1, next
) < 0)
2044 return isl_ast_expr_free(res
);
2049 /* Is the domain of the current entry of "data", which is assumed
2050 * to contain a single subpiece, a subset of "set"?
2052 static isl_bool
single_is_subset(struct isl_from_pw_aff_data
*data
,
2053 __isl_keep isl_set
*set
)
2058 set_n
= isl_set_list_get_set(data
->p
[data
->n
].set_list
, 0);
2059 subset
= isl_set_is_subset(set_n
, set
);
2060 isl_set_free(set_n
);
2065 /* Is "aff" a rational expression, i.e., does it have a denominator
2066 * different from one?
2068 static isl_bool
aff_is_rational(__isl_keep isl_aff
*aff
)
2073 den
= isl_aff_get_denominator_val(aff
);
2074 rational
= isl_bool_not(isl_val_is_one(den
));
2080 /* Does "list" consist of a single rational affine expression?
2082 static isl_bool
is_single_rational_aff(__isl_keep isl_aff_list
*list
)
2088 n
= isl_aff_list_n_aff(list
);
2090 return isl_bool_error
;
2092 return isl_bool_false
;
2093 aff
= isl_aff_list_get_aff(list
, 0);
2094 rational
= aff_is_rational(aff
);
2100 /* Can the list of subpieces in the last piece of "data" be extended with
2101 * "set" and "aff" based on "test"?
2102 * In particular, is it the case for each entry (set_i, aff_i) that
2104 * test(aff, aff_i) holds on set_i, and
2105 * test(aff_i, aff) holds on set?
2107 * "test" returns the set of elements where the tests holds, meaning
2108 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2110 * This function is used to detect min/max expressions.
2111 * If the ast_build_detect_min_max option is turned off, then
2112 * do not even try and perform any detection and return false instead.
2114 * Rational affine expressions are not considered for min/max expressions
2115 * since the combined expression will be defined on the union of the domains,
2116 * while a rational expression may only yield integer values
2117 * on its own definition domain.
2119 static isl_bool
extends(struct isl_from_pw_aff_data
*data
,
2120 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
,
2121 __isl_give isl_basic_set
*(*test
)(__isl_take isl_aff
*aff1
,
2122 __isl_take isl_aff
*aff2
))
2126 isl_bool is_rational
;
2130 is_rational
= aff_is_rational(aff
);
2131 if (is_rational
>= 0 && !is_rational
)
2132 is_rational
= is_single_rational_aff(data
->p
[data
->n
].aff_list
);
2133 if (is_rational
< 0 || is_rational
)
2134 return isl_bool_not(is_rational
);
2136 ctx
= isl_ast_build_get_ctx(data
->build
);
2137 if (!isl_options_get_ast_build_detect_min_max(ctx
))
2138 return isl_bool_false
;
2140 n
= isl_set_list_n_set(data
->p
[data
->n
].set_list
);
2142 return isl_bool_error
;
2144 dom
= isl_ast_build_get_domain(data
->build
);
2145 set
= isl_set_intersect(dom
, isl_set_copy(set
));
2147 for (i
= 0; i
< n
; ++i
) {
2150 isl_set
*dom
, *required
;
2153 aff_i
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, i
);
2154 valid
= isl_set_from_basic_set(test(isl_aff_copy(aff
), aff_i
));
2155 required
= isl_set_list_get_set(data
->p
[data
->n
].set_list
, i
);
2156 dom
= isl_ast_build_get_domain(data
->build
);
2157 required
= isl_set_intersect(dom
, required
);
2158 is_valid
= isl_set_is_subset(required
, valid
);
2159 isl_set_free(required
);
2160 isl_set_free(valid
);
2161 if (is_valid
< 0 || !is_valid
) {
2166 aff_i
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, i
);
2167 valid
= isl_set_from_basic_set(test(aff_i
, isl_aff_copy(aff
)));
2168 is_valid
= isl_set_is_subset(set
, valid
);
2169 isl_set_free(valid
);
2170 if (is_valid
< 0 || !is_valid
) {
2177 return isl_bool_true
;
2180 /* Can the list of pieces in "data" be extended with "set" and "aff"
2181 * to form/preserve a minimum expression?
2182 * In particular, is it the case for each entry (set_i, aff_i) that
2184 * aff >= aff_i on set_i, and
2185 * aff_i >= aff on set?
2187 static isl_bool
extends_min(struct isl_from_pw_aff_data
*data
,
2188 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
)
2190 return extends(data
, set
, aff
, &isl_aff_ge_basic_set
);
2193 /* Can the list of pieces in "data" be extended with "set" and "aff"
2194 * to form/preserve a maximum expression?
2195 * In particular, is it the case for each entry (set_i, aff_i) that
2197 * aff <= aff_i on set_i, and
2198 * aff_i <= aff on set?
2200 static isl_bool
extends_max(struct isl_from_pw_aff_data
*data
,
2201 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
)
2203 return extends(data
, set
, aff
, &isl_aff_le_basic_set
);
2206 /* This function is called during the construction of an isl_ast_expr
2207 * that evaluates an isl_pw_aff.
2208 * If the last piece of "data" contains a single subpiece and
2209 * if its affine function is equal to "aff" on a part of the domain
2210 * that includes either "set" or the domain of that single subpiece,
2211 * then extend the domain of that single subpiece with "set".
2212 * If it was the original domain of the single subpiece where
2213 * the two affine functions are equal, then also replace
2214 * the affine function of the single subpiece by "aff".
2215 * If the last piece of "data" contains either a single subpiece
2216 * or a minimum, then check if this minimum expression can be extended
2218 * If so, extend the sequence and return.
2219 * Perform the same operation for maximum expressions.
2220 * If no such extension can be performed, then move to the next piece
2221 * in "data" (if the current piece contains any data), and then store
2222 * the current subpiece in the current piece of "data" for later handling.
2224 static isl_stat
ast_expr_from_pw_aff(__isl_take isl_set
*set
,
2225 __isl_take isl_aff
*aff
, void *user
)
2227 struct isl_from_pw_aff_data
*data
= user
;
2229 enum isl_from_pw_aff_state state
;
2231 state
= data
->p
[data
->n
].state
;
2232 if (state
== isl_state_single
) {
2235 isl_bool subset1
, subset2
= isl_bool_false
;
2236 aff0
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, 0);
2237 eq
= isl_aff_eq_set(isl_aff_copy(aff
), aff0
);
2238 subset1
= isl_set_is_subset(set
, eq
);
2239 if (subset1
>= 0 && !subset1
)
2240 subset2
= single_is_subset(data
, eq
);
2242 if (subset1
< 0 || subset2
< 0)
2245 return extend_domain(data
, set
, aff
, 0);
2247 return extend_domain(data
, set
, aff
, 1);
2249 if (state
== isl_state_single
|| state
== isl_state_min
) {
2250 test
= extends_min(data
, set
, aff
);
2254 return extend_min(data
, set
, aff
);
2256 if (state
== isl_state_single
|| state
== isl_state_max
) {
2257 test
= extends_max(data
, set
, aff
);
2261 return extend_max(data
, set
, aff
);
2263 if (state
!= isl_state_none
)
2265 set_single(data
, set
, aff
);
2271 return isl_stat_error
;
2274 /* Construct an isl_ast_expr that evaluates "pa".
2275 * The result is simplified in terms of build->domain.
2277 * The domain of "pa" lives in the internal schedule space.
2279 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff_internal(
2280 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2282 struct isl_from_pw_aff_data data
= { NULL
};
2283 isl_ast_expr
*res
= NULL
;
2285 pa
= isl_ast_build_compute_gist_pw_aff(build
, pa
);
2286 pa
= isl_pw_aff_coalesce(pa
);
2290 if (isl_from_pw_aff_data_init(&data
, build
, pa
) < 0)
2294 if (isl_pw_aff_foreach_piece(pa
, &ast_expr_from_pw_aff
, &data
) >= 0)
2295 res
= build_pieces(&data
);
2297 isl_pw_aff_free(pa
);
2298 isl_from_pw_aff_data_clear(&data
);
2301 isl_pw_aff_free(pa
);
2302 isl_from_pw_aff_data_clear(&data
);
2306 /* Construct an isl_ast_expr that evaluates "pa".
2307 * The result is simplified in terms of build->domain.
2309 * The domain of "pa" lives in the external schedule space.
2311 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff(
2312 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2317 needs_map
= isl_ast_build_need_schedule_map(build
);
2318 if (needs_map
< 0) {
2319 pa
= isl_pw_aff_free(pa
);
2320 } else if (needs_map
) {
2322 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
2323 pa
= isl_pw_aff_pullback_multi_aff(pa
, ma
);
2325 expr
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
2329 /* Set the ids of the input dimensions of "mpa" to the iterator ids
2332 * The domain of "mpa" is assumed to live in the internal schedule domain.
2334 static __isl_give isl_multi_pw_aff
*set_iterator_names(
2335 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2340 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_in
);
2342 return isl_multi_pw_aff_free(mpa
);
2343 for (i
= 0; i
< n
; ++i
) {
2346 id
= isl_ast_build_get_iterator_id(build
, i
);
2347 mpa
= isl_multi_pw_aff_set_dim_id(mpa
, isl_dim_in
, i
, id
);
2353 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2354 * the remaining arguments derived from "mpa".
2355 * That is, construct a call or access expression that calls/accesses "arg0"
2356 * with arguments/indices specified by "mpa".
2358 static __isl_give isl_ast_expr
*isl_ast_build_with_arguments(
2359 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2360 __isl_take isl_ast_expr
*arg0
, __isl_take isl_multi_pw_aff
*mpa
)
2367 ctx
= isl_ast_build_get_ctx(build
);
2369 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_out
);
2370 expr
= n
>= 0 ? isl_ast_expr_alloc_op(ctx
, type
, 1 + n
) : NULL
;
2371 expr
= isl_ast_expr_set_op_arg(expr
, 0, arg0
);
2372 for (i
= 0; i
< n
; ++i
) {
2376 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
2377 arg
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
2378 expr
= isl_ast_expr_set_op_arg(expr
, 1 + i
, arg
);
2381 isl_multi_pw_aff_free(mpa
);
2385 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_internal(
2386 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2387 __isl_take isl_multi_pw_aff
*mpa
);
2389 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
2390 * The range of "mpa" is assumed to be wrapped relation.
2391 * The domain of this wrapped relation specifies the structure being
2392 * accessed, while the range of this wrapped relation spacifies the
2393 * member of the structure being accessed.
2395 * The domain of "mpa" is assumed to live in the internal schedule domain.
2397 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_member(
2398 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2401 isl_multi_pw_aff
*domain
;
2402 isl_ast_expr
*domain_expr
, *expr
;
2403 enum isl_ast_expr_op_type type
= isl_ast_expr_op_access
;
2405 domain
= isl_multi_pw_aff_copy(mpa
);
2406 domain
= isl_multi_pw_aff_range_factor_domain(domain
);
2407 domain_expr
= isl_ast_build_from_multi_pw_aff_internal(build
,
2409 mpa
= isl_multi_pw_aff_range_factor_range(mpa
);
2410 if (!isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
))
2411 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
2412 "missing field name", goto error
);
2413 id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
2414 expr
= isl_ast_expr_from_id(id
);
2415 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_member
,
2417 return isl_ast_build_with_arguments(build
, type
, expr
, mpa
);
2419 isl_multi_pw_aff_free(mpa
);
2423 /* Construct an isl_ast_expr of type "type" that calls or accesses
2424 * the element specified by "mpa".
2425 * The first argument is obtained from the output tuple name.
2426 * The remaining arguments are given by the piecewise affine expressions.
2428 * If the range of "mpa" is a mapped relation, then we assume it
2429 * represents an access to a member of a structure.
2431 * The domain of "mpa" is assumed to live in the internal schedule domain.
2433 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_internal(
2434 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2435 __isl_take isl_multi_pw_aff
*mpa
)
2444 if (type
== isl_ast_expr_op_access
&&
2445 isl_multi_pw_aff_range_is_wrapping(mpa
))
2446 return isl_ast_build_from_multi_pw_aff_member(build
, mpa
);
2448 mpa
= set_iterator_names(build
, mpa
);
2452 ctx
= isl_ast_build_get_ctx(build
);
2454 if (isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
))
2455 id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
2457 id
= isl_id_alloc(ctx
, "", NULL
);
2459 expr
= isl_ast_expr_from_id(id
);
2460 return isl_ast_build_with_arguments(build
, type
, expr
, mpa
);
2462 isl_multi_pw_aff_free(mpa
);
2466 /* Construct an isl_ast_expr of type "type" that calls or accesses
2467 * the element specified by "pma".
2468 * The first argument is obtained from the output tuple name.
2469 * The remaining arguments are given by the piecewise affine expressions.
2471 * The domain of "pma" is assumed to live in the internal schedule domain.
2473 static __isl_give isl_ast_expr
*isl_ast_build_from_pw_multi_aff_internal(
2474 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2475 __isl_take isl_pw_multi_aff
*pma
)
2477 isl_multi_pw_aff
*mpa
;
2479 mpa
= isl_multi_pw_aff_from_pw_multi_aff(pma
);
2480 return isl_ast_build_from_multi_pw_aff_internal(build
, type
, mpa
);
2483 /* Construct an isl_ast_expr of type "type" that calls or accesses
2484 * the element specified by "mpa".
2485 * The first argument is obtained from the output tuple name.
2486 * The remaining arguments are given by the piecewise affine expressions.
2488 * The domain of "mpa" is assumed to live in the external schedule domain.
2490 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff(
2491 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2492 __isl_take isl_multi_pw_aff
*mpa
)
2497 isl_space
*space_build
, *space_mpa
;
2499 space_build
= isl_ast_build_get_space(build
, 0);
2500 space_mpa
= isl_multi_pw_aff_get_space(mpa
);
2501 is_domain
= isl_space_tuple_is_equal(space_build
, isl_dim_set
,
2502 space_mpa
, isl_dim_in
);
2503 isl_space_free(space_build
);
2504 isl_space_free(space_mpa
);
2508 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
2509 "spaces don't match", goto error
);
2511 needs_map
= isl_ast_build_need_schedule_map(build
);
2516 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
2517 mpa
= isl_multi_pw_aff_pullback_multi_aff(mpa
, ma
);
2520 expr
= isl_ast_build_from_multi_pw_aff_internal(build
, type
, mpa
);
2523 isl_multi_pw_aff_free(mpa
);
2527 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2528 * The name of the function is obtained from the output tuple name.
2529 * The arguments are given by the piecewise affine expressions.
2531 * The domain of "mpa" is assumed to live in the external schedule domain.
2533 __isl_give isl_ast_expr
*isl_ast_build_call_from_multi_pw_aff(
2534 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2536 return isl_ast_build_from_multi_pw_aff(build
,
2537 isl_ast_expr_op_call
, mpa
);
2540 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2541 * The name of the array is obtained from the output tuple name.
2542 * The index expressions are given by the piecewise affine expressions.
2544 * The domain of "mpa" is assumed to live in the external schedule domain.
2546 __isl_give isl_ast_expr
*isl_ast_build_access_from_multi_pw_aff(
2547 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2549 return isl_ast_build_from_multi_pw_aff(build
,
2550 isl_ast_expr_op_access
, mpa
);
2553 /* Construct an isl_ast_expr of type "type" that calls or accesses
2554 * the element specified by "pma".
2555 * The first argument is obtained from the output tuple name.
2556 * The remaining arguments are given by the piecewise affine expressions.
2558 * The domain of "pma" is assumed to live in the external schedule domain.
2560 static __isl_give isl_ast_expr
*isl_ast_build_from_pw_multi_aff(
2561 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2562 __isl_take isl_pw_multi_aff
*pma
)
2564 isl_multi_pw_aff
*mpa
;
2566 mpa
= isl_multi_pw_aff_from_pw_multi_aff(pma
);
2567 return isl_ast_build_from_multi_pw_aff(build
, type
, mpa
);
2570 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
2571 * The name of the function is obtained from the output tuple name.
2572 * The arguments are given by the piecewise affine expressions.
2574 * The domain of "pma" is assumed to live in the external schedule domain.
2576 __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff(
2577 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2579 return isl_ast_build_from_pw_multi_aff(build
,
2580 isl_ast_expr_op_call
, pma
);
2583 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
2584 * The name of the array is obtained from the output tuple name.
2585 * The index expressions are given by the piecewise affine expressions.
2587 * The domain of "pma" is assumed to live in the external schedule domain.
2589 __isl_give isl_ast_expr
*isl_ast_build_access_from_pw_multi_aff(
2590 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2592 return isl_ast_build_from_pw_multi_aff(build
,
2593 isl_ast_expr_op_access
, pma
);
2596 /* Construct an isl_ast_expr that calls the domain element
2597 * specified by "executed".
2599 * "executed" is assumed to be single-valued, with a domain that lives
2600 * in the internal schedule space.
2602 __isl_give isl_ast_node
*isl_ast_build_call_from_executed(
2603 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*executed
)
2605 isl_pw_multi_aff
*iteration
;
2608 iteration
= isl_pw_multi_aff_from_map(executed
);
2609 iteration
= isl_ast_build_compute_gist_pw_multi_aff(build
, iteration
);
2610 iteration
= isl_pw_multi_aff_intersect_domain(iteration
,
2611 isl_ast_build_get_domain(build
));
2612 expr
= isl_ast_build_from_pw_multi_aff_internal(build
,
2613 isl_ast_expr_op_call
, iteration
);
2614 return isl_ast_node_alloc_user(expr
);