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 int 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
))
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 is_zero
< 0 ? -1 : 0;
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
)) {
200 int non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, aff
);
201 if (non_neg
>= 0 && !non_neg
) {
202 isl_aff
*opp
= oppose_div_arg(isl_aff_copy(aff
),
204 non_neg
= isl_ast_build_aff_is_nonneg(data
->build
, opp
);
205 if (non_neg
>= 0 && non_neg
) {
206 data
->v
= isl_val_neg(data
->v
);
212 if (non_neg
>= 0 && !non_neg
) {
213 non_neg
= is_non_neg_after_stealing(aff
, d
, data
);
214 if (non_neg
>= 0 && non_neg
)
215 aff
= steal_from_cst(aff
, d
, data
);
218 aff
= isl_aff_free(aff
);
220 type
= isl_ast_expr_op_pdiv_q
;
224 num
= isl_ast_expr_from_aff(aff
, data
->build
);
225 return isl_ast_expr_alloc_binary(type
, num
, den
);
228 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
229 * The result is simplified in terms of data->build->domain.
230 * This function may change (the sign of) data->v.
232 * The isl_ast_expr is constructed based on the type of the dimension.
233 * - divs are constructed by var_div
234 * - set variables are constructed from the iterator isl_ids in data->build
235 * - parameters are constructed from the isl_ids in "ls"
237 static __isl_give isl_ast_expr
*var(struct isl_ast_add_term_data
*data
,
238 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
)
240 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
243 if (type
== isl_dim_div
)
244 return var_div(data
, ls
, pos
);
246 if (type
== isl_dim_set
) {
247 id
= isl_ast_build_get_iterator_id(data
->build
, pos
);
248 return isl_ast_expr_from_id(id
);
251 if (!isl_local_space_has_dim_id(ls
, type
, pos
))
252 isl_die(ctx
, isl_error_internal
, "unnamed dimension",
254 id
= isl_local_space_get_dim_id(ls
, type
, pos
);
255 return isl_ast_expr_from_id(id
);
258 /* Does "expr" represent the zero integer?
260 static int ast_expr_is_zero(__isl_keep isl_ast_expr
*expr
)
264 if (expr
->type
!= isl_ast_expr_int
)
266 return isl_val_is_zero(expr
->u
.v
);
269 /* Create an expression representing the sum of "expr1" and "expr2",
270 * provided neither of the two expressions is identically zero.
272 static __isl_give isl_ast_expr
*ast_expr_add(__isl_take isl_ast_expr
*expr1
,
273 __isl_take isl_ast_expr
*expr2
)
275 if (!expr1
|| !expr2
)
278 if (ast_expr_is_zero(expr1
)) {
279 isl_ast_expr_free(expr1
);
283 if (ast_expr_is_zero(expr2
)) {
284 isl_ast_expr_free(expr2
);
288 return isl_ast_expr_add(expr1
, expr2
);
290 isl_ast_expr_free(expr1
);
291 isl_ast_expr_free(expr2
);
295 /* Subtract expr2 from expr1.
297 * If expr2 is zero, we simply return expr1.
298 * If expr1 is zero, we return
300 * (isl_ast_expr_op_minus, expr2)
302 * Otherwise, we return
304 * (isl_ast_expr_op_sub, expr1, expr2)
306 static __isl_give isl_ast_expr
*ast_expr_sub(__isl_take isl_ast_expr
*expr1
,
307 __isl_take isl_ast_expr
*expr2
)
309 if (!expr1
|| !expr2
)
312 if (ast_expr_is_zero(expr2
)) {
313 isl_ast_expr_free(expr2
);
317 if (ast_expr_is_zero(expr1
)) {
318 isl_ast_expr_free(expr1
);
319 return isl_ast_expr_neg(expr2
);
322 return isl_ast_expr_sub(expr1
, expr2
);
324 isl_ast_expr_free(expr1
);
325 isl_ast_expr_free(expr2
);
329 /* Return an isl_ast_expr that represents
333 * v is assumed to be non-negative.
334 * The result is simplified in terms of build->domain.
336 static __isl_give isl_ast_expr
*isl_ast_expr_mod(__isl_keep isl_val
*v
,
337 __isl_keep isl_aff
*aff
, __isl_keep isl_val
*d
,
338 __isl_keep isl_ast_build
*build
)
346 expr
= isl_ast_expr_from_aff(isl_aff_copy(aff
), build
);
348 c
= isl_ast_expr_from_val(isl_val_copy(d
));
349 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_pdiv_r
, expr
, c
);
351 if (!isl_val_is_one(v
)) {
352 c
= isl_ast_expr_from_val(isl_val_copy(v
));
353 expr
= isl_ast_expr_mul(c
, expr
);
359 /* Create an isl_ast_expr that scales "expr" by "v".
361 * If v is 1, we simply return expr.
362 * If v is -1, we return
364 * (isl_ast_expr_op_minus, expr)
366 * Otherwise, we return
368 * (isl_ast_expr_op_mul, expr(v), expr)
370 static __isl_give isl_ast_expr
*scale(__isl_take isl_ast_expr
*expr
,
371 __isl_take isl_val
*v
)
377 if (isl_val_is_one(v
)) {
382 if (isl_val_is_negone(v
)) {
384 expr
= isl_ast_expr_neg(expr
);
386 c
= isl_ast_expr_from_val(v
);
387 expr
= isl_ast_expr_mul(c
, expr
);
393 isl_ast_expr_free(expr
);
397 /* Add an expression for "*v" times the specified dimension of "ls"
399 * If the dimension is an integer division, then this function
400 * may modify data->cst in order to make the numerator non-negative.
401 * The result is simplified in terms of data->build->domain.
403 * Let e be the expression for the specified dimension,
404 * multiplied by the absolute value of "*v".
405 * If "*v" is negative, we create
407 * (isl_ast_expr_op_sub, expr, e)
409 * except when expr is trivially zero, in which case we create
411 * (isl_ast_expr_op_minus, e)
415 * If "*v" is positive, we simply create
417 * (isl_ast_expr_op_add, expr, e)
420 static __isl_give isl_ast_expr
*isl_ast_expr_add_term(
421 __isl_take isl_ast_expr
*expr
,
422 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
,
423 __isl_take isl_val
*v
, struct isl_ast_add_term_data
*data
)
431 term
= var(data
, ls
, type
, pos
);
434 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
436 term
= scale(term
, v
);
437 return ast_expr_sub(expr
, term
);
439 term
= scale(term
, v
);
440 return ast_expr_add(expr
, term
);
444 /* Add an expression for "v" to expr.
446 static __isl_give isl_ast_expr
*isl_ast_expr_add_int(
447 __isl_take isl_ast_expr
*expr
, __isl_take isl_val
*v
)
449 isl_ast_expr
*expr_int
;
454 if (isl_val_is_zero(v
)) {
459 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
461 expr_int
= isl_ast_expr_from_val(v
);
462 return ast_expr_sub(expr
, expr_int
);
464 expr_int
= isl_ast_expr_from_val(v
);
465 return ast_expr_add(expr
, expr_int
);
468 isl_ast_expr_free(expr
);
473 /* Internal data structure used inside extract_modulos.
475 * If any modulo expressions are detected in "aff", then the
476 * expression is removed from "aff" and added to either "pos" or "neg"
477 * depending on the sign of the coefficient of the modulo expression
480 * "add" is an expression that needs to be added to "aff" at the end of
481 * the computation. It is NULL as long as no modulos have been extracted.
483 * "i" is the position in "aff" of the div under investigation
484 * "v" is the coefficient in "aff" of the div
485 * "div" is the argument of the div, with the denominator removed
486 * "d" is the original denominator of the argument of the div
488 * "nonneg" is an affine expression that is non-negative over "build"
489 * and that can be used to extract a modulo expression from "div".
490 * In particular, if "sign" is 1, then the coefficients of "nonneg"
491 * are equal to those of "div" modulo "d". If "sign" is -1, then
492 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
493 * If "sign" is 0, then no such affine expression has been found (yet).
495 struct isl_extract_mod_data
{
496 isl_ast_build
*build
;
513 /* Given that data->v * div_i in data->aff is equal to
515 * f * (term - (arg mod d))
517 * with data->d * f = data->v, add
523 * abs(f) * (arg mod d)
525 * to data->neg or data->pos depending on the sign of -f.
527 static int extract_term_and_mod(struct isl_extract_mod_data
*data
,
528 __isl_take isl_aff
*term
, __isl_take isl_aff
*arg
)
533 data
->v
= isl_val_div(data
->v
, isl_val_copy(data
->d
));
534 s
= isl_val_sgn(data
->v
);
535 data
->v
= isl_val_abs(data
->v
);
536 expr
= isl_ast_expr_mod(data
->v
, arg
, data
->d
, data
->build
);
539 data
->neg
= ast_expr_add(data
->neg
, expr
);
541 data
->pos
= ast_expr_add(data
->pos
, expr
);
542 data
->aff
= isl_aff_set_coefficient_si(data
->aff
,
543 isl_dim_div
, data
->i
, 0);
545 data
->v
= isl_val_neg(data
->v
);
546 term
= isl_aff_scale_val(term
, isl_val_copy(data
->v
));
551 data
->add
= isl_aff_add(data
->add
, term
);
558 /* Given that data->v * div_i in data->aff is of the form
560 * f * d * floor(div/d)
562 * with div nonnegative on data->build, rewrite it as
564 * f * (div - (div mod d)) = f * div - f * (div mod d)
572 * abs(f) * (div mod d)
574 * to data->neg or data->pos depending on the sign of -f.
576 static int extract_mod(struct isl_extract_mod_data
*data
)
578 return extract_term_and_mod(data
, isl_aff_copy(data
->div
),
579 isl_aff_copy(data
->div
));
582 /* Given that data->v * div_i in data->aff is of the form
584 * f * d * floor(div/d) (1)
586 * check if div is non-negative on data->build and, if so,
587 * extract the corresponding modulo from data->aff.
588 * If not, then check if
592 * is non-negative on data->build. If so, replace (1) by
594 * -f * d * floor((-div + d - 1)/d)
596 * and extract the corresponding modulo from data->aff.
598 * This function may modify data->div.
600 static int extract_nonneg_mod(struct isl_extract_mod_data
*data
)
604 mod
= isl_ast_build_aff_is_nonneg(data
->build
, data
->div
);
608 return extract_mod(data
);
610 data
->div
= oppose_div_arg(data
->div
, isl_val_copy(data
->d
));
611 mod
= isl_ast_build_aff_is_nonneg(data
->build
, data
->div
);
615 data
->v
= isl_val_neg(data
->v
);
616 return extract_mod(data
);
621 data
->aff
= isl_aff_free(data
->aff
);
625 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
626 * for use in extracting a modulo expression?
628 * We currently only consider the constant term of the affine expression.
629 * In particular, we prefer the affine expression with the smallest constant
631 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
632 * then we would pick x >= 0
634 * More detailed heuristics could be used if it turns out that there is a need.
636 static int mod_constraint_is_simpler(struct isl_extract_mod_data
*data
,
637 __isl_keep isl_constraint
*c
)
645 v1
= isl_val_abs(isl_constraint_get_constant_val(c
));
646 v2
= isl_val_abs(isl_aff_get_constant_val(data
->nonneg
));
647 simpler
= isl_val_lt(v1
, v2
);
654 /* Check if the coefficients of "c" are either equal or opposite to those
655 * of data->div modulo data->d. If so, and if "c" is "simpler" than
656 * data->nonneg, then replace data->nonneg by the affine expression of "c"
657 * and set data->sign accordingly.
659 * Both "c" and data->div are assumed not to involve any integer divisions.
661 * Before we start the actual comparison, we first quickly check if
662 * "c" and data->div have the same non-zero coefficients.
663 * If not, then we assume that "c" is not of the desired form.
664 * Note that while the coefficients of data->div can be reasonably expected
665 * not to involve any coefficients that are multiples of d, "c" may
666 * very well involve such coefficients. This means that we may actually
669 * If the constant term is "too large", then the constraint is rejected,
670 * where "too large" is fairly arbitrarily set to 1 << 15.
671 * We do this to avoid picking up constraints that bound a variable
672 * by a very large number, say the largest or smallest possible
673 * variable in the representation of some integer type.
675 static isl_stat
check_parallel_or_opposite(__isl_take isl_constraint
*c
,
678 struct isl_extract_mod_data
*data
= user
;
679 enum isl_dim_type c_type
[2] = { isl_dim_param
, isl_dim_set
};
680 enum isl_dim_type a_type
[2] = { isl_dim_param
, isl_dim_in
};
683 int parallel
= 1, opposite
= 1;
685 for (t
= 0; t
< 2; ++t
) {
686 n
[t
] = isl_constraint_dim(c
, c_type
[t
]);
688 return isl_stat_error
;
689 for (i
= 0; i
< n
[t
]; ++i
) {
692 a
= isl_constraint_involves_dims(c
, c_type
[t
], i
, 1);
693 b
= isl_aff_involves_dims(data
->div
, a_type
[t
], i
, 1);
695 parallel
= opposite
= 0;
699 if (parallel
|| opposite
) {
702 v
= isl_val_abs(isl_constraint_get_constant_val(c
));
703 if (isl_val_cmp_si(v
, 1 << 15) > 0)
704 parallel
= opposite
= 0;
708 for (t
= 0; t
< 2; ++t
) {
709 for (i
= 0; i
< n
[t
]; ++i
) {
712 if (!parallel
&& !opposite
)
714 v1
= isl_constraint_get_coefficient_val(c
,
716 v2
= isl_aff_get_coefficient_val(data
->div
,
719 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
720 parallel
= isl_val_is_divisible_by(v1
, data
->d
);
721 v1
= isl_val_add(v1
, isl_val_copy(v2
));
724 v1
= isl_val_add(v1
, isl_val_copy(v2
));
725 opposite
= isl_val_is_divisible_by(v1
, data
->d
);
732 if ((parallel
|| opposite
) && mod_constraint_is_simpler(data
, c
)) {
733 isl_aff_free(data
->nonneg
);
734 data
->nonneg
= isl_constraint_get_aff(c
);
735 data
->sign
= parallel
? 1 : -1;
738 isl_constraint_free(c
);
740 if (data
->sign
!= 0 && data
->nonneg
== NULL
)
741 return isl_stat_error
;
746 /* Given that data->v * div_i in data->aff is of the form
748 * f * d * floor(div/d) (1)
750 * see if we can find an expression div' that is non-negative over data->build
751 * and that is related to div through
757 * div' = -div + d - 1 + d * e
759 * with e some affine expression.
760 * If so, we write (1) as
762 * f * div + f * (div' mod d)
766 * -f * (-div + d - 1) - f * (div' mod d)
768 * exploiting (in the second case) the fact that
770 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
773 * We first try to find an appropriate expression for div'
774 * from the constraints of data->build->domain (which is therefore
775 * guaranteed to be non-negative on data->build), where we remove
776 * any integer divisions from the constraints and skip this step
777 * if "div" itself involves any integer divisions.
778 * If we cannot find an appropriate expression this way, then
779 * we pass control to extract_nonneg_mod where check
780 * if div or "-div + d -1" themselves happen to be
781 * non-negative on data->build.
783 * While looking for an appropriate constraint in data->build->domain,
784 * we ignore the constant term, so after finding such a constraint,
785 * we still need to fix up the constant term.
786 * In particular, if a is the constant term of "div"
787 * (or d - 1 - the constant term of "div" if data->sign < 0)
788 * and b is the constant term of the constraint, then we need to find
789 * a non-negative constant c such that
791 * b + c \equiv a mod d
797 * and add it to b to obtain the constant term of div'.
798 * If this constant term is "too negative", then we add an appropriate
799 * multiple of d to make it positive.
802 * Note that the above is a only a very simple heuristic for finding an
803 * appropriate expression. We could try a bit harder by also considering
804 * sums of constraints that involve disjoint sets of variables or
805 * we could consider arbitrary linear combinations of constraints,
806 * although that could potentially be much more expensive as it involves
807 * the solution of an LP problem.
809 * In particular, if v_i is a column vector representing constraint i,
810 * w represents div and e_i is the i-th unit vector, then we are looking
811 * for a solution of the constraints
813 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
815 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
816 * If we are not just interested in a non-negative expression, but
817 * also in one with a minimal range, then we don't just want
818 * c = \sum_i lambda_i v_i to be non-negative over the domain,
819 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
820 * that we want to minimize and we now also have to take into account
821 * the constant terms of the constraints.
822 * Alternatively, we could first compute the dual of the domain
823 * and plug in the constraints on the coefficients.
825 static int try_extract_mod(struct isl_extract_mod_data
*data
)
835 n
= isl_aff_dim(data
->div
, isl_dim_div
);
839 if (isl_aff_involves_dims(data
->div
, isl_dim_div
, 0, n
))
840 return extract_nonneg_mod(data
);
842 hull
= isl_set_simple_hull(isl_set_copy(data
->build
->domain
));
843 hull
= isl_basic_set_remove_divs(hull
);
846 r
= isl_basic_set_foreach_constraint(hull
, &check_parallel_or_opposite
,
848 isl_basic_set_free(hull
);
850 if (!data
->sign
|| r
< 0) {
851 isl_aff_free(data
->nonneg
);
854 return extract_nonneg_mod(data
);
857 v1
= isl_aff_get_constant_val(data
->div
);
858 v2
= isl_aff_get_constant_val(data
->nonneg
);
859 if (data
->sign
< 0) {
860 v1
= isl_val_neg(v1
);
861 v1
= isl_val_add(v1
, isl_val_copy(data
->d
));
862 v1
= isl_val_sub_ui(v1
, 1);
864 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
865 v1
= isl_val_mod(v1
, isl_val_copy(data
->d
));
866 v1
= isl_val_add(v1
, v2
);
867 v2
= isl_val_div(isl_val_copy(v1
), isl_val_copy(data
->d
));
868 v2
= isl_val_ceil(v2
);
869 if (isl_val_is_neg(v2
)) {
870 v2
= isl_val_mul(v2
, isl_val_copy(data
->d
));
871 v1
= isl_val_sub(v1
, isl_val_copy(v2
));
873 data
->nonneg
= isl_aff_set_constant_val(data
->nonneg
, v1
);
876 if (data
->sign
< 0) {
877 data
->div
= oppose_div_arg(data
->div
, isl_val_copy(data
->d
));
878 data
->v
= isl_val_neg(data
->v
);
881 return extract_term_and_mod(data
,
882 isl_aff_copy(data
->div
), data
->nonneg
);
884 data
->aff
= isl_aff_free(data
->aff
);
888 /* Check if "data->aff" involves any (implicit) modulo computations based
890 * If so, remove them from aff and add expressions corresponding
891 * to those modulo computations to data->pos and/or data->neg.
893 * "aff" is assumed to be an integer affine expression.
895 * In particular, check if (v * div_j) is of the form
897 * f * m * floor(a / m)
899 * and, if so, rewrite it as
901 * f * (a - (a mod m)) = f * a - f * (a mod m)
903 * and extract out -f * (a mod m).
904 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
905 * If f < 0, we add ((-f) * (a mod m)) to *pos.
907 * Note that in order to represent "a mod m" as
909 * (isl_ast_expr_op_pdiv_r, a, m)
911 * we need to make sure that a is non-negative.
912 * If not, we check if "-a + m - 1" is non-negative.
913 * If so, we can rewrite
915 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
917 * and still extract a modulo.
919 static int extract_modulo(struct isl_extract_mod_data
*data
)
921 data
->div
= isl_aff_get_div(data
->aff
, data
->i
);
922 data
->d
= isl_aff_get_denominator_val(data
->div
);
923 if (isl_val_is_divisible_by(data
->v
, data
->d
)) {
924 data
->div
= isl_aff_scale_val(data
->div
, isl_val_copy(data
->d
));
925 if (try_extract_mod(data
) < 0)
926 data
->aff
= isl_aff_free(data
->aff
);
928 isl_aff_free(data
->div
);
929 isl_val_free(data
->d
);
933 /* Check if "aff" involves any (implicit) modulo computations.
934 * If so, remove them from aff and add expressions corresponding
935 * to those modulo computations to *pos and/or *neg.
936 * We only do this if the option ast_build_prefer_pdiv is set.
938 * "aff" is assumed to be an integer affine expression.
940 * A modulo expression is of the form
942 * a mod m = a - m * floor(a / m)
944 * To detect them in aff, we look for terms of the form
946 * f * m * floor(a / m)
950 * f * (a - (a mod m)) = f * a - f * (a mod m)
952 * and extract out -f * (a mod m).
953 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
954 * If f < 0, we add ((-f) * (a mod m)) to *pos.
956 static __isl_give isl_aff
*extract_modulos(__isl_take isl_aff
*aff
,
957 __isl_keep isl_ast_expr
**pos
, __isl_keep isl_ast_expr
**neg
,
958 __isl_keep isl_ast_build
*build
)
960 struct isl_extract_mod_data data
= { build
, aff
, *pos
, *neg
};
967 ctx
= isl_aff_get_ctx(aff
);
968 if (!isl_options_get_ast_build_prefer_pdiv(ctx
))
971 n
= isl_aff_dim(data
.aff
, isl_dim_div
);
973 return isl_aff_free(aff
);
974 for (data
.i
= 0; data
.i
< n
; ++data
.i
) {
975 data
.v
= isl_aff_get_coefficient_val(data
.aff
,
976 isl_dim_div
, data
.i
);
978 return isl_aff_free(aff
);
979 if (isl_val_is_zero(data
.v
) ||
980 isl_val_is_one(data
.v
) || isl_val_is_negone(data
.v
)) {
981 isl_val_free(data
.v
);
984 if (extract_modulo(&data
) < 0)
985 data
.aff
= isl_aff_free(data
.aff
);
986 isl_val_free(data
.v
);
992 data
.aff
= isl_aff_add(data
.aff
, data
.add
);
999 /* Check if aff involves any non-integer coefficients.
1000 * If so, split aff into
1002 * aff = aff1 + (aff2 / d)
1004 * with both aff1 and aff2 having only integer coefficients.
1005 * Return aff1 and add (aff2 / d) to *expr.
1007 static __isl_give isl_aff
*extract_rational(__isl_take isl_aff
*aff
,
1008 __isl_keep isl_ast_expr
**expr
, __isl_keep isl_ast_build
*build
)
1012 isl_aff
*rat
= NULL
;
1013 isl_local_space
*ls
= NULL
;
1014 isl_ast_expr
*rat_expr
;
1016 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1017 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1021 d
= isl_aff_get_denominator_val(aff
);
1024 if (isl_val_is_one(d
)) {
1029 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
1031 ls
= isl_aff_get_domain_local_space(aff
);
1032 rat
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
1034 for (i
= 0; i
< 3; ++i
) {
1035 n
= isl_aff_dim(aff
, t
[i
]);
1038 for (j
= 0; j
< n
; ++j
) {
1041 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1044 if (isl_val_is_divisible_by(v
, d
)) {
1048 rat_j
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
1050 rat_j
= isl_aff_scale_val(rat_j
, v
);
1051 rat
= isl_aff_add(rat
, rat_j
);
1055 v
= isl_aff_get_constant_val(aff
);
1056 if (isl_val_is_divisible_by(v
, d
)) {
1061 rat_0
= isl_aff_val_on_domain(isl_local_space_copy(ls
), v
);
1062 rat
= isl_aff_add(rat
, rat_0
);
1065 isl_local_space_free(ls
);
1067 aff
= isl_aff_sub(aff
, isl_aff_copy(rat
));
1068 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(d
));
1070 rat_expr
= isl_ast_expr_from_aff(rat
, build
);
1071 rat_expr
= isl_ast_expr_div(rat_expr
, isl_ast_expr_from_val(d
));
1072 *expr
= ast_expr_add(*expr
, rat_expr
);
1077 isl_local_space_free(ls
);
1083 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
1084 * The result is simplified in terms of build->domain.
1086 * We first extract hidden modulo computations from the affine expression
1087 * and then add terms for each variable with a non-zero coefficient.
1088 * Finally, if the affine expression has a non-trivial denominator,
1089 * we divide the resulting isl_ast_expr by this denominator.
1091 __isl_give isl_ast_expr
*isl_ast_expr_from_aff(__isl_take isl_aff
*aff
,
1092 __isl_keep isl_ast_build
*build
)
1097 isl_ctx
*ctx
= isl_aff_get_ctx(aff
);
1098 isl_ast_expr
*expr
, *expr_neg
;
1099 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1100 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1101 isl_local_space
*ls
;
1102 struct isl_ast_add_term_data data
;
1107 expr
= isl_ast_expr_alloc_int_si(ctx
, 0);
1108 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
1110 aff
= extract_rational(aff
, &expr
, build
);
1112 aff
= extract_modulos(aff
, &expr
, &expr_neg
, build
);
1113 expr
= ast_expr_sub(expr
, expr_neg
);
1115 ls
= isl_aff_get_domain_local_space(aff
);
1118 data
.cst
= isl_aff_get_constant_val(aff
);
1119 for (i
= 0; i
< 3; ++i
) {
1120 n
= isl_aff_dim(aff
, t
[i
]);
1122 expr
= isl_ast_expr_free(expr
);
1123 for (j
= 0; j
< n
; ++j
) {
1124 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1126 expr
= isl_ast_expr_free(expr
);
1127 if (isl_val_is_zero(v
)) {
1131 expr
= isl_ast_expr_add_term(expr
,
1132 ls
, l
[i
], j
, v
, &data
);
1136 expr
= isl_ast_expr_add_int(expr
, data
.cst
);
1138 isl_local_space_free(ls
);
1143 /* Add terms to "expr" for each variable in "aff" with a coefficient
1144 * with sign equal to "sign".
1145 * The result is simplified in terms of data->build->domain.
1147 static __isl_give isl_ast_expr
*add_signed_terms(__isl_take isl_ast_expr
*expr
,
1148 __isl_keep isl_aff
*aff
, int sign
, struct isl_ast_add_term_data
*data
)
1152 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
1153 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
1154 isl_local_space
*ls
;
1156 ls
= isl_aff_get_domain_local_space(aff
);
1158 for (i
= 0; i
< 3; ++i
) {
1159 isl_size n
= isl_aff_dim(aff
, t
[i
]);
1161 expr
= isl_ast_expr_free(expr
);
1162 for (j
= 0; j
< n
; ++j
) {
1163 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
1164 if (sign
* isl_val_sgn(v
) <= 0) {
1169 expr
= isl_ast_expr_add_term(expr
,
1170 ls
, l
[i
], j
, v
, data
);
1174 isl_local_space_free(ls
);
1179 /* Should the constant term "v" be considered positive?
1181 * A positive constant will be added to "pos" by the caller,
1182 * while a negative constant will be added to "neg".
1183 * If either "pos" or "neg" is exactly zero, then we prefer
1184 * to add the constant "v" to that side, irrespective of the sign of "v".
1185 * This results in slightly shorter expressions and may reduce the risk
1188 static int constant_is_considered_positive(__isl_keep isl_val
*v
,
1189 __isl_keep isl_ast_expr
*pos
, __isl_keep isl_ast_expr
*neg
)
1191 if (ast_expr_is_zero(pos
))
1193 if (ast_expr_is_zero(neg
))
1195 return isl_val_is_pos(v
);
1198 /* Check if the equality
1202 * represents a stride constraint on the integer division "pos".
1204 * In particular, if the integer division "pos" is equal to
1208 * then check if aff is equal to
1214 * If so, the equality is exactly
1218 * Note that in principle we could also accept
1222 * where e and e' differ by a constant.
1224 static int is_stride_constraint(__isl_keep isl_aff
*aff
, int pos
)
1230 div
= isl_aff_get_div(aff
, pos
);
1231 c
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, pos
);
1232 d
= isl_aff_get_denominator_val(div
);
1233 eq
= isl_val_abs_eq(c
, d
);
1234 if (eq
>= 0 && eq
) {
1235 aff
= isl_aff_copy(aff
);
1236 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, pos
, 0);
1237 div
= isl_aff_scale_val(div
, d
);
1238 if (isl_val_is_pos(c
))
1239 div
= isl_aff_neg(div
);
1240 eq
= isl_aff_plain_is_equal(div
, aff
);
1250 /* Are all coefficients of "aff" (zero or) negative?
1252 static isl_bool
all_negative_coefficients(__isl_keep isl_aff
*aff
)
1257 n
= isl_aff_dim(aff
, isl_dim_param
);
1259 return isl_bool_error
;
1260 for (i
= 0; i
< n
; ++i
)
1261 if (isl_aff_coefficient_sgn(aff
, isl_dim_param
, i
) > 0)
1262 return isl_bool_false
;
1264 n
= isl_aff_dim(aff
, isl_dim_in
);
1266 return isl_bool_error
;
1267 for (i
= 0; i
< n
; ++i
)
1268 if (isl_aff_coefficient_sgn(aff
, isl_dim_in
, i
) > 0)
1269 return isl_bool_false
;
1271 return isl_bool_true
;
1274 /* Give an equality of the form
1276 * aff = e - d floor(e/d) = 0
1280 * aff = -e + d floor(e/d) = 0
1282 * with the integer division "pos" equal to floor(e/d),
1283 * construct the AST expression
1285 * (isl_ast_expr_op_eq,
1286 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1288 * If e only has negative coefficients, then construct
1290 * (isl_ast_expr_op_eq,
1291 * (isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))
1295 static __isl_give isl_ast_expr
*extract_stride_constraint(
1296 __isl_take isl_aff
*aff
, int pos
, __isl_keep isl_ast_build
*build
)
1301 isl_ast_expr
*expr
, *cst
;
1306 ctx
= isl_aff_get_ctx(aff
);
1308 c
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, pos
);
1309 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, pos
, 0);
1311 all_neg
= all_negative_coefficients(aff
);
1313 aff
= isl_aff_free(aff
);
1315 aff
= isl_aff_neg(aff
);
1317 cst
= isl_ast_expr_from_val(isl_val_abs(c
));
1318 expr
= isl_ast_expr_from_aff(aff
, build
);
1320 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_zdiv_r
, expr
, cst
);
1321 cst
= isl_ast_expr_alloc_int_si(ctx
, 0);
1322 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_eq
, expr
, cst
);
1327 /* Construct an isl_ast_expr that evaluates the condition "constraint",
1328 * The result is simplified in terms of build->domain.
1330 * We first check if the constraint is an equality of the form
1332 * e - d floor(e/d) = 0
1338 * If so, we convert it to
1340 * (isl_ast_expr_op_eq,
1341 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1343 * Otherwise, let the constraint by either "a >= 0" or "a == 0".
1344 * We first extract hidden modulo computations from "a"
1345 * and then collect all the terms with a positive coefficient in cons_pos
1346 * and the terms with a negative coefficient in cons_neg.
1348 * The result is then of the form
1350 * (isl_ast_expr_op_ge, expr(pos), expr(-neg)))
1354 * (isl_ast_expr_op_eq, expr(pos), expr(-neg)))
1356 * However, if the first expression is an integer constant (and the second
1357 * is not), then we swap the two expressions. This ensures that we construct,
1358 * e.g., "i <= 5" rather than "5 >= i".
1360 * Furthermore, is there are no terms with positive coefficients (or no terms
1361 * with negative coefficients), then the constant term is added to "pos"
1362 * (or "neg"), ignoring the sign of the constant term.
1364 static __isl_give isl_ast_expr
*isl_ast_expr_from_constraint(
1365 __isl_take isl_constraint
*constraint
, __isl_keep isl_ast_build
*build
)
1370 isl_ast_expr
*expr_pos
;
1371 isl_ast_expr
*expr_neg
;
1375 enum isl_ast_expr_op_type type
;
1376 struct isl_ast_add_term_data data
;
1381 aff
= isl_constraint_get_aff(constraint
);
1382 eq
= isl_constraint_is_equality(constraint
);
1383 isl_constraint_free(constraint
);
1385 n
= isl_aff_dim(aff
, isl_dim_div
);
1387 aff
= isl_aff_free(aff
);
1389 for (i
= 0; i
< n
; ++i
) {
1391 is_stride
= is_stride_constraint(aff
, i
);
1395 return extract_stride_constraint(aff
, i
, build
);
1398 ctx
= isl_aff_get_ctx(aff
);
1399 expr_pos
= isl_ast_expr_alloc_int_si(ctx
, 0);
1400 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
1402 aff
= extract_modulos(aff
, &expr_pos
, &expr_neg
, build
);
1405 data
.cst
= isl_aff_get_constant_val(aff
);
1406 expr_pos
= add_signed_terms(expr_pos
, aff
, 1, &data
);
1407 data
.cst
= isl_val_neg(data
.cst
);
1408 expr_neg
= add_signed_terms(expr_neg
, aff
, -1, &data
);
1409 data
.cst
= isl_val_neg(data
.cst
);
1411 if (constant_is_considered_positive(data
.cst
, expr_pos
, expr_neg
)) {
1412 expr_pos
= isl_ast_expr_add_int(expr_pos
, data
.cst
);
1414 data
.cst
= isl_val_neg(data
.cst
);
1415 expr_neg
= isl_ast_expr_add_int(expr_neg
, data
.cst
);
1418 if (isl_ast_expr_get_type(expr_pos
) == isl_ast_expr_int
&&
1419 isl_ast_expr_get_type(expr_neg
) != isl_ast_expr_int
) {
1420 type
= eq
? isl_ast_expr_op_eq
: isl_ast_expr_op_le
;
1421 expr
= isl_ast_expr_alloc_binary(type
, expr_neg
, expr_pos
);
1423 type
= eq
? isl_ast_expr_op_eq
: isl_ast_expr_op_ge
;
1424 expr
= isl_ast_expr_alloc_binary(type
, expr_pos
, expr_neg
);
1434 /* Wrapper around isl_constraint_cmp_last_non_zero for use
1435 * as a callback to isl_constraint_list_sort.
1436 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1437 * apart, then use isl_constraint_plain_cmp instead.
1439 static int cmp_constraint(__isl_keep isl_constraint
*a
,
1440 __isl_keep isl_constraint
*b
, void *user
)
1444 cmp
= isl_constraint_cmp_last_non_zero(a
, b
);
1447 return isl_constraint_plain_cmp(a
, b
);
1450 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1451 * The result is simplified in terms of build->domain.
1453 * If "bset" is not bounded by any constraint, then we construct
1454 * the expression "1", i.e., "true".
1456 * Otherwise, we sort the constraints, putting constraints that involve
1457 * integer divisions after those that do not, and construct an "and"
1458 * of the ast expressions of the individual constraints.
1460 * Each constraint is added to the generated constraints of the build
1461 * after it has been converted to an AST expression so that it can be used
1462 * to simplify the following constraints. This may change the truth value
1463 * of subsequent constraints that do not satisfy the earlier constraints,
1464 * but this does not affect the outcome of the conjunction as it is
1465 * only true if all the conjuncts are true (no matter in what order
1466 * they are evaluated). In particular, the constraints that do not
1467 * involve integer divisions may serve to simplify some constraints
1468 * that do involve integer divisions.
1470 __isl_give isl_ast_expr
*isl_ast_build_expr_from_basic_set(
1471 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
1476 isl_constraint_list
*list
;
1480 list
= isl_basic_set_get_constraint_list(bset
);
1481 isl_basic_set_free(bset
);
1482 list
= isl_constraint_list_sort(list
, &cmp_constraint
, NULL
);
1483 n
= isl_constraint_list_n_constraint(list
);
1487 isl_ctx
*ctx
= isl_constraint_list_get_ctx(list
);
1488 isl_constraint_list_free(list
);
1489 return isl_ast_expr_alloc_int_si(ctx
, 1);
1492 build
= isl_ast_build_copy(build
);
1494 c
= isl_constraint_list_get_constraint(list
, 0);
1495 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
1496 set
= isl_set_from_basic_set(bset
);
1497 res
= isl_ast_expr_from_constraint(c
, build
);
1498 build
= isl_ast_build_restrict_generated(build
, set
);
1500 for (i
= 1; i
< n
; ++i
) {
1503 c
= isl_constraint_list_get_constraint(list
, i
);
1504 bset
= isl_basic_set_from_constraint(isl_constraint_copy(c
));
1505 set
= isl_set_from_basic_set(bset
);
1506 expr
= isl_ast_expr_from_constraint(c
, build
);
1507 build
= isl_ast_build_restrict_generated(build
, set
);
1508 res
= isl_ast_expr_and(res
, expr
);
1511 isl_constraint_list_free(list
);
1512 isl_ast_build_free(build
);
1516 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1517 * The result is simplified in terms of build->domain.
1519 * If "set" is an (obviously) empty set, then return the expression "0".
1521 * If there are multiple disjuncts in the description of the set,
1522 * then subsequent disjuncts are simplified in a context where
1523 * the previous disjuncts have been removed from build->domain.
1524 * In particular, constraints that ensure that there is no overlap
1525 * with these previous disjuncts, can be removed.
1526 * This is mostly useful for disjuncts that are only defined by
1527 * a single constraint (relative to the build domain) as the opposite
1528 * of that single constraint can then be removed from the other disjuncts.
1529 * In order not to increase the number of disjuncts in the build domain
1530 * after subtracting the previous disjuncts of "set", the simple hull
1531 * is computed after taking the difference with each of these disjuncts.
1532 * This means that constraints that prevent overlap with a union
1533 * of multiple previous disjuncts are not removed.
1535 * "set" lives in the internal schedule space.
1537 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set_internal(
1538 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1542 isl_basic_set
*bset
;
1543 isl_basic_set_list
*list
;
1547 list
= isl_set_get_basic_set_list(set
);
1550 n
= isl_basic_set_list_n_basic_set(list
);
1554 isl_ctx
*ctx
= isl_ast_build_get_ctx(build
);
1555 isl_basic_set_list_free(list
);
1556 return isl_ast_expr_from_val(isl_val_zero(ctx
));
1559 domain
= isl_ast_build_get_domain(build
);
1561 bset
= isl_basic_set_list_get_basic_set(list
, 0);
1562 set
= isl_set_from_basic_set(isl_basic_set_copy(bset
));
1563 res
= isl_ast_build_expr_from_basic_set(build
, bset
);
1565 for (i
= 1; i
< n
; ++i
) {
1569 rest
= isl_set_subtract(isl_set_copy(domain
), set
);
1570 rest
= isl_set_from_basic_set(isl_set_simple_hull(rest
));
1571 domain
= isl_set_intersect(domain
, rest
);
1572 bset
= isl_basic_set_list_get_basic_set(list
, i
);
1573 set
= isl_set_from_basic_set(isl_basic_set_copy(bset
));
1574 bset
= isl_basic_set_gist(bset
,
1575 isl_set_simple_hull(isl_set_copy(domain
)));
1576 expr
= isl_ast_build_expr_from_basic_set(build
, bset
);
1577 res
= isl_ast_expr_or(res
, expr
);
1580 isl_set_free(domain
);
1582 isl_basic_set_list_free(list
);
1586 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1587 * The result is simplified in terms of build->domain.
1589 * If "set" is an (obviously) empty set, then return the expression "0".
1591 * "set" lives in the external schedule space.
1593 * The internal AST expression generation assumes that there are
1594 * no unknown divs, so make sure an explicit representation is available.
1595 * Since the set comes from the outside, it may have constraints that
1596 * are redundant with respect to the build domain. Remove them first.
1598 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set(
1599 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1603 needs_map
= isl_ast_build_need_schedule_map(build
);
1604 if (needs_map
< 0) {
1605 set
= isl_set_free(set
);
1606 } else if (needs_map
) {
1608 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
1609 set
= isl_set_preimage_multi_aff(set
, ma
);
1612 set
= isl_set_compute_divs(set
);
1613 set
= isl_ast_build_compute_gist(build
, set
);
1614 return isl_ast_build_expr_from_set_internal(build
, set
);
1617 /* State of data about previous pieces in
1618 * isl_ast_build_expr_from_pw_aff_internal.
1620 * isl_state_none: no data about previous pieces
1621 * isl_state_single: data about a single previous piece
1622 * isl_state_min: data represents minimum of several pieces
1623 * isl_state_max: data represents maximum of several pieces
1625 enum isl_from_pw_aff_state
{
1632 /* Internal date structure representing a single piece in the input of
1633 * isl_ast_build_expr_from_pw_aff_internal.
1635 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1636 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1637 * single previous subpiece.
1638 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
1639 * a sequence of several previous subpieces that are equal to the minimum
1640 * of the entries in "aff_list" over the union of "set_list"
1641 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
1642 * a sequence of several previous subpieces that are equal to the maximum
1643 * of the entries in "aff_list" over the union of "set_list"
1645 * During the construction of the pieces, "set" is NULL.
1646 * After the construction, "set" is set to the union of the elements
1647 * in "set_list", at which point "set_list" is set to NULL.
1649 struct isl_from_pw_aff_piece
{
1650 enum isl_from_pw_aff_state state
;
1652 isl_set_list
*set_list
;
1653 isl_aff_list
*aff_list
;
1656 /* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1658 * "build" specifies the domain against which the result is simplified.
1659 * "dom" is the domain of the entire isl_pw_aff.
1661 * "n" is the number of pieces constructed already.
1662 * In particular, during the construction of the pieces, "n" points to
1663 * the piece that is being constructed. After the construction of the
1664 * pieces, "n" is set to the total number of pieces.
1665 * "max" is the total number of allocated entries.
1666 * "p" contains the individual pieces.
1668 struct isl_from_pw_aff_data
{
1669 isl_ast_build
*build
;
1674 struct isl_from_pw_aff_piece
*p
;
1677 /* Initialize "data" based on "build" and "pa".
1679 static isl_stat
isl_from_pw_aff_data_init(struct isl_from_pw_aff_data
*data
,
1680 __isl_keep isl_ast_build
*build
, __isl_keep isl_pw_aff
*pa
)
1685 ctx
= isl_pw_aff_get_ctx(pa
);
1686 n
= isl_pw_aff_n_piece(pa
);
1688 return isl_stat_error
;
1690 isl_die(ctx
, isl_error_invalid
,
1691 "cannot handle void expression", return isl_stat_error
);
1693 data
->p
= isl_calloc_array(ctx
, struct isl_from_pw_aff_piece
, n
);
1695 return isl_stat_error
;
1696 data
->build
= build
;
1697 data
->dom
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
1703 /* Free all memory allocated for "data".
1705 static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data
*data
)
1709 isl_set_free(data
->dom
);
1713 for (i
= 0; i
< data
->max
; ++i
) {
1714 isl_set_free(data
->p
[i
].set
);
1715 isl_set_list_free(data
->p
[i
].set_list
);
1716 isl_aff_list_free(data
->p
[i
].aff_list
);
1721 /* Initialize the current entry of "data" to an unused piece.
1723 static void set_none(struct isl_from_pw_aff_data
*data
)
1725 data
->p
[data
->n
].state
= isl_state_none
;
1726 data
->p
[data
->n
].set_list
= NULL
;
1727 data
->p
[data
->n
].aff_list
= NULL
;
1730 /* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1732 static void set_single(struct isl_from_pw_aff_data
*data
,
1733 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1735 data
->p
[data
->n
].state
= isl_state_single
;
1736 data
->p
[data
->n
].set_list
= isl_set_list_from_set(set
);
1737 data
->p
[data
->n
].aff_list
= isl_aff_list_from_aff(aff
);
1740 /* Extend the current entry of "data" with "set" and "aff"
1741 * as a minimum expression.
1743 static isl_stat
extend_min(struct isl_from_pw_aff_data
*data
,
1744 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1747 data
->p
[n
].state
= isl_state_min
;
1748 data
->p
[n
].set_list
= isl_set_list_add(data
->p
[n
].set_list
, set
);
1749 data
->p
[n
].aff_list
= isl_aff_list_add(data
->p
[n
].aff_list
, aff
);
1751 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1752 return isl_stat_error
;
1756 /* Extend the current entry of "data" with "set" and "aff"
1757 * as a maximum expression.
1759 static isl_stat
extend_max(struct isl_from_pw_aff_data
*data
,
1760 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
)
1763 data
->p
[n
].state
= isl_state_max
;
1764 data
->p
[n
].set_list
= isl_set_list_add(data
->p
[n
].set_list
, set
);
1765 data
->p
[n
].aff_list
= isl_aff_list_add(data
->p
[n
].aff_list
, aff
);
1767 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1768 return isl_stat_error
;
1772 /* Extend the domain of the current entry of "data", which is assumed
1773 * to contain a single subpiece, with "set". If "replace" is set,
1774 * then also replace the affine function by "aff". Otherwise,
1775 * simply free "aff".
1777 static isl_stat
extend_domain(struct isl_from_pw_aff_data
*data
,
1778 __isl_take isl_set
*set
, __isl_take isl_aff
*aff
, int replace
)
1783 set_n
= isl_set_list_get_set(data
->p
[n
].set_list
, 0);
1784 set_n
= isl_set_union(set_n
, set
);
1785 data
->p
[n
].set_list
=
1786 isl_set_list_set_set(data
->p
[n
].set_list
, 0, set_n
);
1789 data
->p
[n
].aff_list
=
1790 isl_aff_list_set_aff(data
->p
[n
].aff_list
, 0, aff
);
1794 if (!data
->p
[n
].set_list
|| !data
->p
[n
].aff_list
)
1795 return isl_stat_error
;
1799 /* Construct an isl_ast_expr from "list" within "build".
1800 * If "state" is isl_state_single, then "list" contains a single entry and
1801 * an isl_ast_expr is constructed for that entry.
1802 * Otherwise a min or max expression is constructed from "list"
1803 * depending on "state".
1805 static __isl_give isl_ast_expr
*ast_expr_from_aff_list(
1806 __isl_take isl_aff_list
*list
, enum isl_from_pw_aff_state state
,
1807 __isl_keep isl_ast_build
*build
)
1812 isl_ast_expr
*expr
= NULL
;
1813 enum isl_ast_expr_op_type op_type
;
1815 if (state
== isl_state_single
) {
1816 aff
= isl_aff_list_get_aff(list
, 0);
1817 isl_aff_list_free(list
);
1818 return isl_ast_expr_from_aff(aff
, build
);
1820 n
= isl_aff_list_n_aff(list
);
1823 op_type
= state
== isl_state_min
? isl_ast_expr_op_min
1824 : isl_ast_expr_op_max
;
1825 expr
= isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build
), op_type
, n
);
1829 for (i
= 0; i
< n
; ++i
) {
1830 isl_ast_expr
*expr_i
;
1832 aff
= isl_aff_list_get_aff(list
, i
);
1833 expr_i
= isl_ast_expr_from_aff(aff
, build
);
1836 expr
->u
.op
.args
[i
] = expr_i
;
1839 isl_aff_list_free(list
);
1842 isl_aff_list_free(list
);
1843 isl_ast_expr_free(expr
);
1847 /* Extend the expression in "next" to take into account
1848 * the piece at position "pos" in "data", allowing for a further extension
1849 * for the next piece(s).
1850 * In particular, "next" is set to a select operation that selects
1851 * an isl_ast_expr corresponding to data->aff_list on data->set and
1852 * to an expression that will be filled in by later calls.
1853 * Return a pointer to this location.
1854 * Afterwards, the state of "data" is set to isl_state_none.
1856 * The constraints of data->set are added to the generated
1857 * constraints of the build such that they can be exploited to simplify
1858 * the AST expression constructed from data->aff_list.
1860 static isl_ast_expr
**add_intermediate_piece(struct isl_from_pw_aff_data
*data
,
1861 int pos
, isl_ast_expr
**next
)
1864 isl_ast_build
*build
;
1865 isl_ast_expr
*ternary
, *arg
;
1866 isl_set
*set
, *gist
;
1868 set
= data
->p
[pos
].set
;
1869 data
->p
[pos
].set
= NULL
;
1870 ctx
= isl_ast_build_get_ctx(data
->build
);
1871 ternary
= isl_ast_expr_alloc_op(ctx
, isl_ast_expr_op_select
, 3);
1872 gist
= isl_set_gist(isl_set_copy(set
), isl_set_copy(data
->dom
));
1873 arg
= isl_ast_build_expr_from_set_internal(data
->build
, gist
);
1874 ternary
= isl_ast_expr_set_op_arg(ternary
, 0, arg
);
1875 build
= isl_ast_build_copy(data
->build
);
1876 build
= isl_ast_build_restrict_generated(build
, set
);
1877 arg
= ast_expr_from_aff_list(data
->p
[pos
].aff_list
,
1878 data
->p
[pos
].state
, build
);
1879 data
->p
[pos
].aff_list
= NULL
;
1880 isl_ast_build_free(build
);
1881 ternary
= isl_ast_expr_set_op_arg(ternary
, 1, arg
);
1882 data
->p
[pos
].state
= isl_state_none
;
1887 return &ternary
->u
.op
.args
[2];
1890 /* Extend the expression in "next" to take into account
1891 * the final piece, located at position "pos" in "data".
1892 * In particular, "next" is set to evaluate data->aff_list
1893 * and the domain is ignored.
1894 * Return isl_stat_ok on success and isl_stat_error on failure.
1896 * The constraints of data->set are however added to the generated
1897 * constraints of the build such that they can be exploited to simplify
1898 * the AST expression constructed from data->aff_list.
1900 static isl_stat
add_last_piece(struct isl_from_pw_aff_data
*data
,
1901 int pos
, isl_ast_expr
**next
)
1903 isl_ast_build
*build
;
1905 if (data
->p
[pos
].state
== isl_state_none
)
1906 isl_die(isl_ast_build_get_ctx(data
->build
), isl_error_invalid
,
1907 "cannot handle void expression", return isl_stat_error
);
1909 build
= isl_ast_build_copy(data
->build
);
1910 build
= isl_ast_build_restrict_generated(build
, data
->p
[pos
].set
);
1911 data
->p
[pos
].set
= NULL
;
1912 *next
= ast_expr_from_aff_list(data
->p
[pos
].aff_list
,
1913 data
->p
[pos
].state
, build
);
1914 data
->p
[pos
].aff_list
= NULL
;
1915 isl_ast_build_free(build
);
1916 data
->p
[pos
].state
= isl_state_none
;
1918 return isl_stat_error
;
1923 /* Return -1 if the piece "p1" should be sorted before "p2"
1924 * and 1 if it should be sorted after "p2".
1925 * Return 0 if they do not need to be sorted in a specific order.
1927 * Pieces are sorted according to the number of disjuncts
1930 static int sort_pieces_cmp(const void *p1
, const void *p2
, void *arg
)
1932 const struct isl_from_pw_aff_piece
*piece1
= p1
;
1933 const struct isl_from_pw_aff_piece
*piece2
= p2
;
1936 n1
= isl_set_n_basic_set(piece1
->set
);
1937 n2
= isl_set_n_basic_set(piece2
->set
);
1942 /* Construct an isl_ast_expr from the pieces in "data".
1943 * Return the result or NULL on failure.
1945 * When this function is called, data->n points to the current piece.
1946 * If this is an effective piece, then first increment data->n such
1947 * that data->n contains the number of pieces.
1948 * The "set_list" fields are subsequently replaced by the corresponding
1949 * "set" fields, after which the pieces are sorted according to
1950 * the number of disjuncts in these "set" fields.
1952 * Construct intermediate AST expressions for the initial pieces and
1953 * finish off with the final pieces.
1955 static isl_ast_expr
*build_pieces(struct isl_from_pw_aff_data
*data
)
1958 isl_ast_expr
*res
= NULL
;
1959 isl_ast_expr
**next
= &res
;
1961 if (data
->p
[data
->n
].state
!= isl_state_none
)
1964 isl_die(isl_ast_build_get_ctx(data
->build
), isl_error_invalid
,
1965 "cannot handle void expression", return NULL
);
1967 for (i
= 0; i
< data
->n
; ++i
) {
1968 data
->p
[i
].set
= isl_set_list_union(data
->p
[i
].set_list
);
1969 if (data
->p
[i
].state
!= isl_state_single
)
1970 data
->p
[i
].set
= isl_set_coalesce(data
->p
[i
].set
);
1971 data
->p
[i
].set_list
= NULL
;
1974 if (isl_sort(data
->p
, data
->n
, sizeof(data
->p
[0]),
1975 &sort_pieces_cmp
, NULL
) < 0)
1976 return isl_ast_expr_free(res
);
1978 for (i
= 0; i
+ 1 < data
->n
; ++i
) {
1979 next
= add_intermediate_piece(data
, i
, next
);
1981 return isl_ast_expr_free(res
);
1984 if (add_last_piece(data
, data
->n
- 1, next
) < 0)
1985 return isl_ast_expr_free(res
);
1990 /* Is the domain of the current entry of "data", which is assumed
1991 * to contain a single subpiece, a subset of "set"?
1993 static isl_bool
single_is_subset(struct isl_from_pw_aff_data
*data
,
1994 __isl_keep isl_set
*set
)
1999 set_n
= isl_set_list_get_set(data
->p
[data
->n
].set_list
, 0);
2000 subset
= isl_set_is_subset(set_n
, set
);
2001 isl_set_free(set_n
);
2006 /* Is "aff" a rational expression, i.e., does it have a denominator
2007 * different from one?
2009 static isl_bool
aff_is_rational(__isl_keep isl_aff
*aff
)
2014 den
= isl_aff_get_denominator_val(aff
);
2015 rational
= isl_bool_not(isl_val_is_one(den
));
2021 /* Does "list" consist of a single rational affine expression?
2023 static isl_bool
is_single_rational_aff(__isl_keep isl_aff_list
*list
)
2029 n
= isl_aff_list_n_aff(list
);
2031 return isl_bool_error
;
2033 return isl_bool_false
;
2034 aff
= isl_aff_list_get_aff(list
, 0);
2035 rational
= aff_is_rational(aff
);
2041 /* Can the list of subpieces in the last piece of "data" be extended with
2042 * "set" and "aff" based on "test"?
2043 * In particular, is it the case for each entry (set_i, aff_i) that
2045 * test(aff, aff_i) holds on set_i, and
2046 * test(aff_i, aff) holds on set?
2048 * "test" returns the set of elements where the tests holds, meaning
2049 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2051 * This function is used to detect min/max expressions.
2052 * If the ast_build_detect_min_max option is turned off, then
2053 * do not even try and perform any detection and return false instead.
2055 * Rational affine expressions are not considered for min/max expressions
2056 * since the combined expression will be defined on the union of the domains,
2057 * while a rational expression may only yield integer values
2058 * on its own definition domain.
2060 static isl_bool
extends(struct isl_from_pw_aff_data
*data
,
2061 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
,
2062 __isl_give isl_basic_set
*(*test
)(__isl_take isl_aff
*aff1
,
2063 __isl_take isl_aff
*aff2
))
2067 isl_bool is_rational
;
2071 is_rational
= aff_is_rational(aff
);
2072 if (is_rational
>= 0 && !is_rational
)
2073 is_rational
= is_single_rational_aff(data
->p
[data
->n
].aff_list
);
2074 if (is_rational
< 0 || is_rational
)
2075 return isl_bool_not(is_rational
);
2077 ctx
= isl_ast_build_get_ctx(data
->build
);
2078 if (!isl_options_get_ast_build_detect_min_max(ctx
))
2079 return isl_bool_false
;
2081 n
= isl_set_list_n_set(data
->p
[data
->n
].set_list
);
2083 return isl_bool_error
;
2085 dom
= isl_ast_build_get_domain(data
->build
);
2086 set
= isl_set_intersect(dom
, isl_set_copy(set
));
2088 for (i
= 0; i
< n
; ++i
) {
2091 isl_set
*dom
, *required
;
2094 aff_i
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, i
);
2095 valid
= isl_set_from_basic_set(test(isl_aff_copy(aff
), aff_i
));
2096 required
= isl_set_list_get_set(data
->p
[data
->n
].set_list
, i
);
2097 dom
= isl_ast_build_get_domain(data
->build
);
2098 required
= isl_set_intersect(dom
, required
);
2099 is_valid
= isl_set_is_subset(required
, valid
);
2100 isl_set_free(required
);
2101 isl_set_free(valid
);
2102 if (is_valid
< 0 || !is_valid
) {
2107 aff_i
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, i
);
2108 valid
= isl_set_from_basic_set(test(aff_i
, isl_aff_copy(aff
)));
2109 is_valid
= isl_set_is_subset(set
, valid
);
2110 isl_set_free(valid
);
2111 if (is_valid
< 0 || !is_valid
) {
2118 return isl_bool_true
;
2121 /* Can the list of pieces in "data" be extended with "set" and "aff"
2122 * to form/preserve a minimum expression?
2123 * In particular, is it the case for each entry (set_i, aff_i) that
2125 * aff >= aff_i on set_i, and
2126 * aff_i >= aff on set?
2128 static isl_bool
extends_min(struct isl_from_pw_aff_data
*data
,
2129 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
)
2131 return extends(data
, set
, aff
, &isl_aff_ge_basic_set
);
2134 /* Can the list of pieces in "data" be extended with "set" and "aff"
2135 * to form/preserve a maximum expression?
2136 * In particular, is it the case for each entry (set_i, aff_i) that
2138 * aff <= aff_i on set_i, and
2139 * aff_i <= aff on set?
2141 static isl_bool
extends_max(struct isl_from_pw_aff_data
*data
,
2142 __isl_keep isl_set
*set
, __isl_keep isl_aff
*aff
)
2144 return extends(data
, set
, aff
, &isl_aff_le_basic_set
);
2147 /* This function is called during the construction of an isl_ast_expr
2148 * that evaluates an isl_pw_aff.
2149 * If the last piece of "data" contains a single subpiece and
2150 * if its affine function is equal to "aff" on a part of the domain
2151 * that includes either "set" or the domain of that single subpiece,
2152 * then extend the domain of that single subpiece with "set".
2153 * If it was the original domain of the single subpiece where
2154 * the two affine functions are equal, then also replace
2155 * the affine function of the single subpiece by "aff".
2156 * If the last piece of "data" contains either a single subpiece
2157 * or a minimum, then check if this minimum expression can be extended
2159 * If so, extend the sequence and return.
2160 * Perform the same operation for maximum expressions.
2161 * If no such extension can be performed, then move to the next piece
2162 * in "data" (if the current piece contains any data), and then store
2163 * the current subpiece in the current piece of "data" for later handling.
2165 static isl_stat
ast_expr_from_pw_aff(__isl_take isl_set
*set
,
2166 __isl_take isl_aff
*aff
, void *user
)
2168 struct isl_from_pw_aff_data
*data
= user
;
2170 enum isl_from_pw_aff_state state
;
2172 state
= data
->p
[data
->n
].state
;
2173 if (state
== isl_state_single
) {
2176 isl_bool subset1
, subset2
= isl_bool_false
;
2177 aff0
= isl_aff_list_get_aff(data
->p
[data
->n
].aff_list
, 0);
2178 eq
= isl_aff_eq_set(isl_aff_copy(aff
), aff0
);
2179 subset1
= isl_set_is_subset(set
, eq
);
2180 if (subset1
>= 0 && !subset1
)
2181 subset2
= single_is_subset(data
, eq
);
2183 if (subset1
< 0 || subset2
< 0)
2186 return extend_domain(data
, set
, aff
, 0);
2188 return extend_domain(data
, set
, aff
, 1);
2190 if (state
== isl_state_single
|| state
== isl_state_min
) {
2191 test
= extends_min(data
, set
, aff
);
2195 return extend_min(data
, set
, aff
);
2197 if (state
== isl_state_single
|| state
== isl_state_max
) {
2198 test
= extends_max(data
, set
, aff
);
2202 return extend_max(data
, set
, aff
);
2204 if (state
!= isl_state_none
)
2206 set_single(data
, set
, aff
);
2212 return isl_stat_error
;
2215 /* Construct an isl_ast_expr that evaluates "pa".
2216 * The result is simplified in terms of build->domain.
2218 * The domain of "pa" lives in the internal schedule space.
2220 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff_internal(
2221 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2223 struct isl_from_pw_aff_data data
= { NULL
};
2224 isl_ast_expr
*res
= NULL
;
2226 pa
= isl_ast_build_compute_gist_pw_aff(build
, pa
);
2227 pa
= isl_pw_aff_coalesce(pa
);
2231 if (isl_from_pw_aff_data_init(&data
, build
, pa
) < 0)
2235 if (isl_pw_aff_foreach_piece(pa
, &ast_expr_from_pw_aff
, &data
) >= 0)
2236 res
= build_pieces(&data
);
2238 isl_pw_aff_free(pa
);
2239 isl_from_pw_aff_data_clear(&data
);
2242 isl_pw_aff_free(pa
);
2243 isl_from_pw_aff_data_clear(&data
);
2247 /* Construct an isl_ast_expr that evaluates "pa".
2248 * The result is simplified in terms of build->domain.
2250 * The domain of "pa" lives in the external schedule space.
2252 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff(
2253 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2258 needs_map
= isl_ast_build_need_schedule_map(build
);
2259 if (needs_map
< 0) {
2260 pa
= isl_pw_aff_free(pa
);
2261 } else if (needs_map
) {
2263 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
2264 pa
= isl_pw_aff_pullback_multi_aff(pa
, ma
);
2266 expr
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
2270 /* Set the ids of the input dimensions of "mpa" to the iterator ids
2273 * The domain of "mpa" is assumed to live in the internal schedule domain.
2275 static __isl_give isl_multi_pw_aff
*set_iterator_names(
2276 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2281 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_in
);
2283 return isl_multi_pw_aff_free(mpa
);
2284 for (i
= 0; i
< n
; ++i
) {
2287 id
= isl_ast_build_get_iterator_id(build
, i
);
2288 mpa
= isl_multi_pw_aff_set_dim_id(mpa
, isl_dim_in
, i
, id
);
2294 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2295 * the remaining arguments derived from "mpa".
2296 * That is, construct a call or access expression that calls/accesses "arg0"
2297 * with arguments/indices specified by "mpa".
2299 static __isl_give isl_ast_expr
*isl_ast_build_with_arguments(
2300 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2301 __isl_take isl_ast_expr
*arg0
, __isl_take isl_multi_pw_aff
*mpa
)
2308 ctx
= isl_ast_build_get_ctx(build
);
2310 n
= isl_multi_pw_aff_dim(mpa
, isl_dim_out
);
2311 expr
= n
>= 0 ? isl_ast_expr_alloc_op(ctx
, type
, 1 + n
) : NULL
;
2312 expr
= isl_ast_expr_set_op_arg(expr
, 0, arg0
);
2313 for (i
= 0; i
< n
; ++i
) {
2317 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, i
);
2318 arg
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
2319 expr
= isl_ast_expr_set_op_arg(expr
, 1 + i
, arg
);
2322 isl_multi_pw_aff_free(mpa
);
2326 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_internal(
2327 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2328 __isl_take isl_multi_pw_aff
*mpa
);
2330 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
2331 * The range of "mpa" is assumed to be wrapped relation.
2332 * The domain of this wrapped relation specifies the structure being
2333 * accessed, while the range of this wrapped relation spacifies the
2334 * member of the structure being accessed.
2336 * The domain of "mpa" is assumed to live in the internal schedule domain.
2338 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_member(
2339 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2342 isl_multi_pw_aff
*domain
;
2343 isl_ast_expr
*domain_expr
, *expr
;
2344 enum isl_ast_expr_op_type type
= isl_ast_expr_op_access
;
2346 domain
= isl_multi_pw_aff_copy(mpa
);
2347 domain
= isl_multi_pw_aff_range_factor_domain(domain
);
2348 domain_expr
= isl_ast_build_from_multi_pw_aff_internal(build
,
2350 mpa
= isl_multi_pw_aff_range_factor_range(mpa
);
2351 if (!isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
))
2352 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
2353 "missing field name", goto error
);
2354 id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
2355 expr
= isl_ast_expr_from_id(id
);
2356 expr
= isl_ast_expr_alloc_binary(isl_ast_expr_op_member
,
2358 return isl_ast_build_with_arguments(build
, type
, expr
, mpa
);
2360 isl_multi_pw_aff_free(mpa
);
2364 /* Construct an isl_ast_expr of type "type" that calls or accesses
2365 * the element specified by "mpa".
2366 * The first argument is obtained from the output tuple name.
2367 * The remaining arguments are given by the piecewise affine expressions.
2369 * If the range of "mpa" is a mapped relation, then we assume it
2370 * represents an access to a member of a structure.
2372 * The domain of "mpa" is assumed to live in the internal schedule domain.
2374 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff_internal(
2375 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2376 __isl_take isl_multi_pw_aff
*mpa
)
2385 if (type
== isl_ast_expr_op_access
&&
2386 isl_multi_pw_aff_range_is_wrapping(mpa
))
2387 return isl_ast_build_from_multi_pw_aff_member(build
, mpa
);
2389 mpa
= set_iterator_names(build
, mpa
);
2393 ctx
= isl_ast_build_get_ctx(build
);
2395 if (isl_multi_pw_aff_has_tuple_id(mpa
, isl_dim_out
))
2396 id
= isl_multi_pw_aff_get_tuple_id(mpa
, isl_dim_out
);
2398 id
= isl_id_alloc(ctx
, "", NULL
);
2400 expr
= isl_ast_expr_from_id(id
);
2401 return isl_ast_build_with_arguments(build
, type
, expr
, mpa
);
2403 isl_multi_pw_aff_free(mpa
);
2407 /* Construct an isl_ast_expr of type "type" that calls or accesses
2408 * the element specified by "pma".
2409 * The first argument is obtained from the output tuple name.
2410 * The remaining arguments are given by the piecewise affine expressions.
2412 * The domain of "pma" is assumed to live in the internal schedule domain.
2414 static __isl_give isl_ast_expr
*isl_ast_build_from_pw_multi_aff_internal(
2415 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2416 __isl_take isl_pw_multi_aff
*pma
)
2418 isl_multi_pw_aff
*mpa
;
2420 mpa
= isl_multi_pw_aff_from_pw_multi_aff(pma
);
2421 return isl_ast_build_from_multi_pw_aff_internal(build
, type
, mpa
);
2424 /* Construct an isl_ast_expr of type "type" that calls or accesses
2425 * the element specified by "mpa".
2426 * The first argument is obtained from the output tuple name.
2427 * The remaining arguments are given by the piecewise affine expressions.
2429 * The domain of "mpa" is assumed to live in the external schedule domain.
2431 static __isl_give isl_ast_expr
*isl_ast_build_from_multi_pw_aff(
2432 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2433 __isl_take isl_multi_pw_aff
*mpa
)
2438 isl_space
*space_build
, *space_mpa
;
2440 space_build
= isl_ast_build_get_space(build
, 0);
2441 space_mpa
= isl_multi_pw_aff_get_space(mpa
);
2442 is_domain
= isl_space_tuple_is_equal(space_build
, isl_dim_set
,
2443 space_mpa
, isl_dim_in
);
2444 isl_space_free(space_build
);
2445 isl_space_free(space_mpa
);
2449 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
2450 "spaces don't match", goto error
);
2452 needs_map
= isl_ast_build_need_schedule_map(build
);
2457 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
2458 mpa
= isl_multi_pw_aff_pullback_multi_aff(mpa
, ma
);
2461 expr
= isl_ast_build_from_multi_pw_aff_internal(build
, type
, mpa
);
2464 isl_multi_pw_aff_free(mpa
);
2468 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2469 * The name of the function is obtained from the output tuple name.
2470 * The arguments are given by the piecewise affine expressions.
2472 * The domain of "mpa" is assumed to live in the external schedule domain.
2474 __isl_give isl_ast_expr
*isl_ast_build_call_from_multi_pw_aff(
2475 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2477 return isl_ast_build_from_multi_pw_aff(build
,
2478 isl_ast_expr_op_call
, mpa
);
2481 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2482 * The name of the array is obtained from the output tuple name.
2483 * The index expressions are given by the piecewise affine expressions.
2485 * The domain of "mpa" is assumed to live in the external schedule domain.
2487 __isl_give isl_ast_expr
*isl_ast_build_access_from_multi_pw_aff(
2488 __isl_keep isl_ast_build
*build
, __isl_take isl_multi_pw_aff
*mpa
)
2490 return isl_ast_build_from_multi_pw_aff(build
,
2491 isl_ast_expr_op_access
, mpa
);
2494 /* Construct an isl_ast_expr of type "type" that calls or accesses
2495 * the element specified by "pma".
2496 * The first argument is obtained from the output tuple name.
2497 * The remaining arguments are given by the piecewise affine expressions.
2499 * The domain of "pma" is assumed to live in the external schedule domain.
2501 static __isl_give isl_ast_expr
*isl_ast_build_from_pw_multi_aff(
2502 __isl_keep isl_ast_build
*build
, enum isl_ast_expr_op_type type
,
2503 __isl_take isl_pw_multi_aff
*pma
)
2505 isl_multi_pw_aff
*mpa
;
2507 mpa
= isl_multi_pw_aff_from_pw_multi_aff(pma
);
2508 return isl_ast_build_from_multi_pw_aff(build
, type
, mpa
);
2511 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
2512 * The name of the function is obtained from the output tuple name.
2513 * The arguments are given by the piecewise affine expressions.
2515 * The domain of "pma" is assumed to live in the external schedule domain.
2517 __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff(
2518 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2520 return isl_ast_build_from_pw_multi_aff(build
,
2521 isl_ast_expr_op_call
, pma
);
2524 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
2525 * The name of the array is obtained from the output tuple name.
2526 * The index expressions are given by the piecewise affine expressions.
2528 * The domain of "pma" is assumed to live in the external schedule domain.
2530 __isl_give isl_ast_expr
*isl_ast_build_access_from_pw_multi_aff(
2531 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2533 return isl_ast_build_from_pw_multi_aff(build
,
2534 isl_ast_expr_op_access
, pma
);
2537 /* Construct an isl_ast_expr that calls the domain element
2538 * specified by "executed".
2540 * "executed" is assumed to be single-valued, with a domain that lives
2541 * in the internal schedule space.
2543 __isl_give isl_ast_node
*isl_ast_build_call_from_executed(
2544 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*executed
)
2546 isl_pw_multi_aff
*iteration
;
2549 iteration
= isl_pw_multi_aff_from_map(executed
);
2550 iteration
= isl_ast_build_compute_gist_pw_multi_aff(build
, iteration
);
2551 iteration
= isl_pw_multi_aff_intersect_domain(iteration
,
2552 isl_ast_build_get_domain(build
));
2553 expr
= isl_ast_build_from_pw_multi_aff_internal(build
,
2554 isl_ast_expr_op_call
, iteration
);
2555 return isl_ast_node_alloc_user(expr
);