2 * Copyright 2012-2013 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11 #include <isl_ast_build_expr.h>
12 #include <isl_ast_private.h>
13 #include <isl_ast_build_private.h>
15 /* Compute the "opposite" of the (numerator of the) argument of a div
16 * with denonimator "d".
18 * In particular, compute
22 static __isl_give isl_aff
*oppose_div_arg(__isl_take isl_aff
*aff
,
23 __isl_take isl_val
*d
)
25 aff
= isl_aff_neg(aff
);
26 aff
= isl_aff_add_constant_val(aff
, d
);
27 aff
= isl_aff_add_constant_si(aff
, -1);
32 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
33 * The result is simplified in terms of build->domain.
35 * *change_sign is set by this function if the sign of
36 * the expression has changed.
37 * "ls" is known to be non-NULL.
39 * Let the div be of the form floor(e/d).
40 * If the ast_build_prefer_pdiv option is set then we check if "e"
41 * is non-negative, so that we can generate
43 * (pdiv_q, expr(e), expr(d))
47 * (fdiv_q, expr(e), expr(d))
49 * If the ast_build_prefer_pdiv option is set and
50 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
51 * If so, we can rewrite
53 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
55 * and still use pdiv_q.
57 static __isl_give isl_ast_expr
*var_div(int *change_sign
,
58 __isl_keep isl_local_space
*ls
,
59 int pos
, __isl_keep isl_ast_build
*build
)
61 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
63 isl_ast_expr
*num
, *den
;
65 enum isl_ast_op_type type
;
67 aff
= isl_local_space_get_div(ls
, pos
);
68 d
= isl_aff_get_denominator_val(aff
);
69 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
70 den
= isl_ast_expr_from_val(isl_val_copy(d
));
72 type
= isl_ast_op_fdiv_q
;
73 if (isl_options_get_ast_build_prefer_pdiv(ctx
)) {
74 int non_neg
= isl_ast_build_aff_is_nonneg(build
, aff
);
75 if (non_neg
>= 0 && !non_neg
) {
76 isl_aff
*opp
= oppose_div_arg(isl_aff_copy(aff
),
78 non_neg
= isl_ast_build_aff_is_nonneg(build
, opp
);
79 if (non_neg
>= 0 && non_neg
) {
87 aff
= isl_aff_free(aff
);
89 type
= isl_ast_op_pdiv_q
;
93 num
= isl_ast_expr_from_aff(aff
, build
);
94 return isl_ast_expr_alloc_binary(type
, num
, den
);
97 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
98 * The result is simplified in terms of build->domain.
100 * *change_sign is set by this function if the sign of
101 * the expression has changed.
103 * The isl_ast_expr is constructed based on the type of the dimension.
104 * - divs are constructed by var_div
105 * - set variables are constructed from the iterator isl_ids in "build"
106 * - parameters are constructed from the isl_ids in "ls"
108 static __isl_give isl_ast_expr
*var(int *change_sign
,
109 __isl_keep isl_local_space
*ls
,
110 enum isl_dim_type type
, int pos
, __isl_keep isl_ast_build
*build
)
112 isl_ctx
*ctx
= isl_local_space_get_ctx(ls
);
115 if (type
== isl_dim_div
)
116 return var_div(change_sign
, ls
, pos
, build
);
118 if (type
== isl_dim_set
) {
119 id
= isl_ast_build_get_iterator_id(build
, pos
);
120 return isl_ast_expr_from_id(id
);
123 if (!isl_local_space_has_dim_id(ls
, type
, pos
))
124 isl_die(ctx
, isl_error_internal
, "unnamed dimension",
126 id
= isl_local_space_get_dim_id(ls
, type
, pos
);
127 return isl_ast_expr_from_id(id
);
130 /* Does "expr" represent the zero integer?
132 static int ast_expr_is_zero(__isl_keep isl_ast_expr
*expr
)
136 if (expr
->type
!= isl_ast_expr_int
)
138 return isl_val_is_zero(expr
->u
.v
);
141 /* Create an expression representing the sum of "expr1" and "expr2",
142 * provided neither of the two expressions is identically zero.
144 static __isl_give isl_ast_expr
*ast_expr_add(__isl_take isl_ast_expr
*expr1
,
145 __isl_take isl_ast_expr
*expr2
)
147 if (!expr1
|| !expr2
)
150 if (ast_expr_is_zero(expr1
)) {
151 isl_ast_expr_free(expr1
);
155 if (ast_expr_is_zero(expr2
)) {
156 isl_ast_expr_free(expr2
);
160 return isl_ast_expr_add(expr1
, expr2
);
162 isl_ast_expr_free(expr1
);
163 isl_ast_expr_free(expr2
);
167 /* Subtract expr2 from expr1.
169 * If expr2 is zero, we simply return expr1.
170 * If expr1 is zero, we return
172 * (isl_ast_op_minus, expr2)
174 * Otherwise, we return
176 * (isl_ast_op_sub, expr1, expr2)
178 static __isl_give isl_ast_expr
*ast_expr_sub(__isl_take isl_ast_expr
*expr1
,
179 __isl_take isl_ast_expr
*expr2
)
181 if (!expr1
|| !expr2
)
184 if (ast_expr_is_zero(expr2
)) {
185 isl_ast_expr_free(expr2
);
189 if (ast_expr_is_zero(expr1
)) {
190 isl_ast_expr_free(expr1
);
191 return isl_ast_expr_neg(expr2
);
194 return isl_ast_expr_sub(expr1
, expr2
);
196 isl_ast_expr_free(expr1
);
197 isl_ast_expr_free(expr2
);
201 /* Return an isl_ast_expr that represents
205 * v is assumed to be non-negative.
206 * The result is simplified in terms of build->domain.
208 static __isl_give isl_ast_expr
*isl_ast_expr_mod(__isl_keep isl_val
*v
,
209 __isl_keep isl_aff
*aff
, __isl_keep isl_val
*d
,
210 __isl_keep isl_ast_build
*build
)
219 ctx
= isl_aff_get_ctx(aff
);
220 expr
= isl_ast_expr_from_aff(isl_aff_copy(aff
), build
);
222 c
= isl_ast_expr_from_val(isl_val_copy(d
));
223 expr
= isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r
, expr
, c
);
225 if (!isl_val_is_one(v
)) {
226 c
= isl_ast_expr_from_val(isl_val_copy(v
));
227 expr
= isl_ast_expr_mul(c
, expr
);
233 /* Create an isl_ast_expr that scales "expr" by "v".
235 * If v is 1, we simply return expr.
236 * If v is -1, we return
238 * (isl_ast_op_minus, expr)
240 * Otherwise, we return
242 * (isl_ast_op_mul, expr(v), expr)
244 static __isl_give isl_ast_expr
*scale(__isl_take isl_ast_expr
*expr
,
245 __isl_take isl_val
*v
)
251 if (isl_val_is_one(v
)) {
256 if (isl_val_is_negone(v
)) {
258 expr
= isl_ast_expr_neg(expr
);
260 c
= isl_ast_expr_from_val(v
);
261 expr
= isl_ast_expr_mul(c
, expr
);
267 isl_ast_expr_free(expr
);
271 /* Add an expression for "*v" times the specified dimension of "ls"
274 * Let e be the expression for the specified dimension,
275 * multiplied by the absolute value of "*v".
276 * If "*v" is negative, we create
278 * (isl_ast_op_sub, expr, e)
280 * except when expr is trivially zero, in which case we create
282 * (isl_ast_op_minus, e)
286 * If "*v" is positive, we simply create
288 * (isl_ast_op_add, expr, e)
291 static __isl_give isl_ast_expr
*isl_ast_expr_add_term(
292 __isl_take isl_ast_expr
*expr
,
293 __isl_keep isl_local_space
*ls
, enum isl_dim_type type
, int pos
,
294 __isl_take isl_val
*v
, __isl_keep isl_ast_build
*build
)
303 term
= var(&change_sign
, ls
, type
, pos
, build
);
307 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
309 term
= scale(term
, v
);
310 return ast_expr_sub(expr
, term
);
312 term
= scale(term
, v
);
313 return ast_expr_add(expr
, term
);
317 /* Add an expression for "v" to expr.
319 static __isl_give isl_ast_expr
*isl_ast_expr_add_int(
320 __isl_take isl_ast_expr
*expr
, __isl_take isl_val
*v
)
323 isl_ast_expr
*expr_int
;
328 if (isl_val_is_zero(v
)) {
333 ctx
= isl_ast_expr_get_ctx(expr
);
334 if (isl_val_is_neg(v
) && !ast_expr_is_zero(expr
)) {
336 expr_int
= isl_ast_expr_from_val(v
);
337 return ast_expr_sub(expr
, expr_int
);
339 expr_int
= isl_ast_expr_from_val(v
);
340 return ast_expr_add(expr
, expr_int
);
343 isl_ast_expr_free(expr
);
348 /* Check if "aff" involves any (implicit) modulo computations based
350 * If so, remove them from aff and add expressions corresponding
351 * to those modulo computations to *pos and/or *neg.
352 * "v" is the coefficient of div "j".
354 * In particular, check if (v * div_j) / d is of the form
356 * (f * m * floor(a / m)) / d
358 * and, if so, rewrite it as
360 * (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d
362 * and extract out -f * (a mod m).
363 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
364 * If f < 0, we add ((-f) * (a mod m)) to *pos.
366 * Note that in order to represent "a mod m" as
368 * (isl_ast_op_pdiv_r, a, m)
370 * we need to make sure that a is non-negative.
371 * If not, we check if "-a + m - 1" is non-negative.
372 * If so, we can rewrite
374 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
376 * and still extract a modulo.
378 * The caller is responsible for dividing *neg and/or *pos by d.
380 static __isl_give isl_aff
*extract_modulo(__isl_take isl_aff
*aff
,
381 __isl_keep isl_ast_expr
**pos
, __isl_keep isl_ast_expr
**neg
,
382 __isl_keep isl_ast_build
*build
, int j
, __isl_take isl_val
*v
)
390 div
= isl_aff_get_div(aff
, j
);
391 d
= isl_aff_get_denominator_val(div
);
392 mod
= isl_val_is_divisible_by(v
, d
);
394 div
= isl_aff_scale_val(div
, isl_val_copy(d
));
395 mod
= isl_ast_build_aff_is_nonneg(build
, div
);
396 if (mod
>= 0 && !mod
) {
397 isl_aff
*opp
= oppose_div_arg(isl_aff_copy(div
),
399 mod
= isl_ast_build_aff_is_nonneg(build
, opp
);
400 if (mod
>= 0 && mod
) {
412 return isl_aff_free(aff
);
419 v
= isl_val_div(v
, isl_val_copy(d
));
422 expr
= isl_ast_expr_mod(v
, div
, d
, build
);
425 *neg
= ast_expr_add(*neg
, expr
);
427 *pos
= ast_expr_add(*pos
, expr
);
428 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_div
, j
, 0);
431 div
= isl_aff_scale_val(div
, v
);
432 d
= isl_aff_get_denominator_val(aff
);
433 div
= isl_aff_scale_down_val(div
, d
);
434 aff
= isl_aff_add(aff
, div
);
439 /* Check if "aff" involves any (implicit) modulo computations.
440 * If so, remove them from aff and add expressions corresponding
441 * to those modulo computations to *pos and/or *neg.
442 * We only do this if the option ast_build_prefer_pdiv is set.
444 * "aff" is assumed to be an integer affine expression.
446 * A modulo expression is of the form
448 * a mod m = a - m * floor(a / m)
450 * To detect them in aff, we look for terms of the form
452 * f * m * floor(a / m)
456 * f * (a - (a mod m)) = f * a - f * (a mod m)
458 * and extract out -f * (a mod m).
459 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
460 * If f < 0, we add ((-f) * (a mod m)) to *pos.
462 static __isl_give isl_aff
*extract_modulos(__isl_take isl_aff
*aff
,
463 __isl_keep isl_ast_expr
**pos
, __isl_keep isl_ast_expr
**neg
,
464 __isl_keep isl_ast_build
*build
)
472 ctx
= isl_aff_get_ctx(aff
);
473 if (!isl_options_get_ast_build_prefer_pdiv(ctx
))
476 n
= isl_aff_dim(aff
, isl_dim_div
);
477 for (j
= 0; j
< n
; ++j
) {
480 v
= isl_aff_get_coefficient_val(aff
, isl_dim_div
, j
);
482 return isl_aff_free(aff
);
483 if (isl_val_is_zero(v
) ||
484 isl_val_is_one(v
) || isl_val_is_negone(v
)) {
488 aff
= extract_modulo(aff
, pos
, neg
, build
, j
, v
);
496 /* Check if aff involves any non-integer coefficients.
497 * If so, split aff into
499 * aff = aff1 + (aff2 / d)
501 * with both aff1 and aff2 having only integer coefficients.
502 * Return aff1 and add (aff2 / d) to *expr.
504 static __isl_give isl_aff
*extract_rational(__isl_take isl_aff
*aff
,
505 __isl_keep isl_ast_expr
**expr
, __isl_keep isl_ast_build
*build
)
509 isl_local_space
*ls
= NULL
;
510 isl_ast_expr
*rat_expr
;
512 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
513 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
517 d
= isl_aff_get_denominator_val(aff
);
520 if (isl_val_is_one(d
)) {
525 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
527 ls
= isl_aff_get_domain_local_space(aff
);
528 rat
= isl_aff_zero_on_domain(isl_local_space_copy(ls
));
530 for (i
= 0; i
< 3; ++i
) {
531 n
= isl_aff_dim(aff
, t
[i
]);
532 for (j
= 0; j
< n
; ++j
) {
535 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
538 if (isl_val_is_divisible_by(v
, d
)) {
542 rat_j
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
544 rat_j
= isl_aff_scale_val(rat_j
, v
);
545 rat
= isl_aff_add(rat
, rat_j
);
549 v
= isl_aff_get_constant_val(aff
);
550 if (isl_val_is_divisible_by(v
, d
)) {
555 rat_0
= isl_aff_val_on_domain(isl_local_space_copy(ls
), v
);
556 rat
= isl_aff_add(rat
, rat_0
);
559 isl_local_space_free(ls
);
561 aff
= isl_aff_sub(aff
, isl_aff_copy(rat
));
562 aff
= isl_aff_scale_down_val(aff
, isl_val_copy(d
));
564 rat_expr
= isl_ast_expr_from_aff(rat
, build
);
565 rat_expr
= isl_ast_expr_div(rat_expr
, isl_ast_expr_from_val(d
));
566 *expr
= ast_expr_add(*expr
, rat_expr
);
571 isl_local_space_free(ls
);
577 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
578 * The result is simplified in terms of build->domain.
580 * We first extract hidden modulo computations from the affine expression
581 * and then add terms for each variable with a non-zero coefficient.
582 * Finally, if the affine expression has a non-trivial denominator,
583 * we divide the resulting isl_ast_expr by this denominator.
585 __isl_give isl_ast_expr
*isl_ast_expr_from_aff(__isl_take isl_aff
*aff
,
586 __isl_keep isl_ast_build
*build
)
591 isl_ctx
*ctx
= isl_aff_get_ctx(aff
);
592 isl_ast_expr
*expr
, *expr_neg
;
593 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
594 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
600 expr
= isl_ast_expr_alloc_int_si(ctx
, 0);
601 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
603 aff
= extract_rational(aff
, &expr
, build
);
605 aff
= extract_modulos(aff
, &expr
, &expr_neg
, build
);
606 expr
= ast_expr_sub(expr
, expr_neg
);
608 ls
= isl_aff_get_domain_local_space(aff
);
610 for (i
= 0; i
< 3; ++i
) {
611 n
= isl_aff_dim(aff
, t
[i
]);
612 for (j
= 0; j
< n
; ++j
) {
613 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
615 expr
= isl_ast_expr_free(expr
);
616 if (isl_val_is_zero(v
)) {
620 expr
= isl_ast_expr_add_term(expr
,
621 ls
, l
[i
], j
, v
, build
);
625 v
= isl_aff_get_constant_val(aff
);
626 expr
= isl_ast_expr_add_int(expr
, v
);
628 isl_local_space_free(ls
);
633 /* Add terms to "expr" for each variable in "aff" with a coefficient
634 * with sign equal to "sign".
635 * The result is simplified in terms of build->domain.
637 static __isl_give isl_ast_expr
*add_signed_terms(__isl_take isl_ast_expr
*expr
,
638 __isl_keep isl_aff
*aff
, int sign
, __isl_keep isl_ast_build
*build
)
642 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
643 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
646 ls
= isl_aff_get_domain_local_space(aff
);
648 for (i
= 0; i
< 3; ++i
) {
649 int n
= isl_aff_dim(aff
, t
[i
]);
650 for (j
= 0; j
< n
; ++j
) {
651 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
652 if (sign
* isl_val_sgn(v
) <= 0) {
657 expr
= isl_ast_expr_add_term(expr
,
658 ls
, l
[i
], j
, v
, build
);
662 isl_local_space_free(ls
);
667 /* Should the constant term "v" be considered positive?
669 * A positive constant will be added to "pos" by the caller,
670 * while a negative constant will be added to "neg".
671 * If either "pos" or "neg" is exactly zero, then we prefer
672 * to add the constant "v" to that side, irrespective of the sign of "v".
673 * This results in slightly shorter expressions and may reduce the risk
676 static int constant_is_considered_positive(__isl_keep isl_val
*v
,
677 __isl_keep isl_ast_expr
*pos
, __isl_keep isl_ast_expr
*neg
)
679 if (ast_expr_is_zero(pos
))
681 if (ast_expr_is_zero(neg
))
683 return isl_val_is_pos(v
);
686 /* Construct an isl_ast_expr that evaluates the condition "constraint",
687 * The result is simplified in terms of build->domain.
689 * Let the constraint by either "a >= 0" or "a == 0".
690 * We first extract hidden modulo computations from "a"
691 * and then collect all the terms with a positive coefficient in cons_pos
692 * and the terms with a negative coefficient in cons_neg.
694 * The result is then of the form
696 * (isl_ast_op_ge, expr(pos), expr(-neg)))
700 * (isl_ast_op_eq, expr(pos), expr(-neg)))
702 * However, if the first expression is an integer constant (and the second
703 * is not), then we swap the two expressions. This ensures that we construct,
704 * e.g., "i <= 5" rather than "5 >= i".
706 * Furthermore, is there are no terms with positive coefficients (or no terms
707 * with negative coefficients), then the constant term is added to "pos"
708 * (or "neg"), ignoring the sign of the constant term.
710 static __isl_give isl_ast_expr
*isl_ast_expr_from_constraint(
711 __isl_take isl_constraint
*constraint
, __isl_keep isl_ast_build
*build
)
714 isl_ast_expr
*expr_pos
;
715 isl_ast_expr
*expr_neg
;
720 enum isl_ast_op_type type
;
725 aff
= isl_constraint_get_aff(constraint
);
727 ctx
= isl_constraint_get_ctx(constraint
);
728 expr_pos
= isl_ast_expr_alloc_int_si(ctx
, 0);
729 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
731 aff
= extract_modulos(aff
, &expr_pos
, &expr_neg
, build
);
733 expr_pos
= add_signed_terms(expr_pos
, aff
, 1, build
);
734 expr_neg
= add_signed_terms(expr_neg
, aff
, -1, build
);
736 v
= isl_aff_get_constant_val(aff
);
737 if (constant_is_considered_positive(v
, expr_pos
, expr_neg
)) {
738 expr_pos
= isl_ast_expr_add_int(expr_pos
, v
);
741 expr_neg
= isl_ast_expr_add_int(expr_neg
, v
);
744 eq
= isl_constraint_is_equality(constraint
);
746 if (isl_ast_expr_get_type(expr_pos
) == isl_ast_expr_int
&&
747 isl_ast_expr_get_type(expr_neg
) != isl_ast_expr_int
) {
748 type
= eq
? isl_ast_op_eq
: isl_ast_op_le
;
749 expr
= isl_ast_expr_alloc_binary(type
, expr_neg
, expr_pos
);
751 type
= eq
? isl_ast_op_eq
: isl_ast_op_ge
;
752 expr
= isl_ast_expr_alloc_binary(type
, expr_pos
, expr_neg
);
755 isl_constraint_free(constraint
);
760 struct isl_expr_from_basic_data
{
761 isl_ast_build
*build
;
766 /* Construct an isl_ast_expr that evaluates the condition "c",
767 * except if it is a div constraint, and add it to the data->res.
768 * The result is simplified in terms of data->build->domain.
770 static int expr_from_basic_set(__isl_take isl_constraint
*c
, void *user
)
772 struct isl_expr_from_basic_data
*data
= user
;
775 if (isl_constraint_is_div_constraint(c
)) {
776 isl_constraint_free(c
);
780 expr
= isl_ast_expr_from_constraint(c
, data
->build
);
784 data
->res
= isl_ast_expr_and(data
->res
, expr
);
793 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
794 * The result is simplified in terms of build->domain.
796 * We filter out the div constraints during printing, so we do not know
797 * in advance how many constraints are going to be printed.
799 * If it turns out that there was no constraint, then we contruct
800 * the expression "1", i.e., "true".
802 __isl_give isl_ast_expr
*isl_ast_build_expr_from_basic_set(
803 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
805 struct isl_expr_from_basic_data data
= { build
, 1, NULL
};
807 if (isl_basic_set_foreach_constraint(bset
,
808 &expr_from_basic_set
, &data
) < 0) {
809 data
.res
= isl_ast_expr_free(data
.res
);
810 } else if (data
.res
== NULL
) {
811 isl_ctx
*ctx
= isl_basic_set_get_ctx(bset
);
812 data
.res
= isl_ast_expr_alloc_int_si(ctx
, 1);
815 isl_basic_set_free(bset
);
819 struct isl_expr_from_set_data
{
820 isl_ast_build
*build
;
825 /* Construct an isl_ast_expr that evaluates the conditions defining "bset"
826 * and add it to data->res.
827 * The result is simplified in terms of data->build->domain.
829 static int expr_from_set(__isl_take isl_basic_set
*bset
, void *user
)
831 struct isl_expr_from_set_data
*data
= user
;
834 expr
= isl_ast_build_expr_from_basic_set(data
->build
, bset
);
838 data
->res
= isl_ast_expr_or(data
->res
, expr
);
847 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
848 * The result is simplified in terms of build->domain.
850 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set(
851 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
853 struct isl_expr_from_set_data data
= { build
, 1, NULL
};
855 if (isl_set_foreach_basic_set(set
, &expr_from_set
, &data
) < 0)
856 data
.res
= isl_ast_expr_free(data
.res
);
862 struct isl_from_pw_aff_data
{
863 isl_ast_build
*build
;
869 /* This function is called during the construction of an isl_ast_expr
870 * that evaluates an isl_pw_aff.
871 * Adjust data->next to take into account this piece.
873 * data->n is the number of pairs of set and aff to go.
874 * data->dom is the domain of the entire isl_pw_aff.
876 * If this is the last pair, then data->next is set to evaluate aff
877 * and the domain is ignored.
878 * Otherwise, data->next is set to a select operation that selects
879 * an isl_ast_expr correponding to "aff" on "set" and to an expression
880 * that will be filled in by later calls otherwise.
882 static int ast_expr_from_pw_aff(__isl_take isl_set
*set
,
883 __isl_take isl_aff
*aff
, void *user
)
885 struct isl_from_pw_aff_data
*data
= user
;
888 ctx
= isl_set_get_ctx(set
);
891 *data
->next
= isl_ast_expr_from_aff(aff
, data
->build
);
896 isl_ast_expr
*ternary
, *arg
;
898 ternary
= isl_ast_expr_alloc_op(ctx
, isl_ast_op_select
, 3);
899 set
= isl_set_gist(set
, isl_set_copy(data
->dom
));
900 arg
= isl_ast_build_expr_from_set(data
->build
, set
);
901 ternary
= isl_ast_expr_set_op_arg(ternary
, 0, arg
);
902 arg
= isl_ast_expr_from_aff(aff
, data
->build
);
903 ternary
= isl_ast_expr_set_op_arg(ternary
, 1, arg
);
907 *data
->next
= ternary
;
908 data
->next
= &ternary
->u
.op
.args
[2];
914 /* Construct an isl_ast_expr that evaluates "pa".
915 * The result is simplified in terms of build->domain.
917 * The domain of "pa" lives in the internal schedule space.
919 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff_internal(
920 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
922 struct isl_from_pw_aff_data data
;
923 isl_ast_expr
*res
= NULL
;
925 pa
= isl_ast_build_compute_gist_pw_aff(build
, pa
);
926 pa
= isl_pw_aff_coalesce(pa
);
931 data
.n
= isl_pw_aff_n_piece(pa
);
933 data
.dom
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
935 if (isl_pw_aff_foreach_piece(pa
, &ast_expr_from_pw_aff
, &data
) < 0)
936 res
= isl_ast_expr_free(res
);
938 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
939 "cannot handle void expression", res
= NULL
);
942 isl_set_free(data
.dom
);
946 /* Construct an isl_ast_expr that evaluates "pa".
947 * The result is simplified in terms of build->domain.
949 * The domain of "pa" lives in the external schedule space.
951 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff(
952 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
956 if (isl_ast_build_need_schedule_map(build
)) {
958 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
959 pa
= isl_pw_aff_pullback_multi_aff(pa
, ma
);
961 expr
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
965 /* Set the ids of the input dimensions of "pma" to the iterator ids
968 * The domain of "pma" is assumed to live in the internal schedule domain.
970 static __isl_give isl_pw_multi_aff
*set_iterator_names(
971 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
975 n
= isl_pw_multi_aff_dim(pma
, isl_dim_in
);
976 for (i
= 0; i
< n
; ++i
) {
979 id
= isl_ast_build_get_iterator_id(build
, i
);
980 pma
= isl_pw_multi_aff_set_dim_id(pma
, isl_dim_in
, i
, id
);
986 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
987 * The name of the function is obtained from the output tuple name.
988 * The arguments are given by the piecewise affine expressions.
990 * The domain of "pma" is assumed to live in the internal schedule domain.
992 static __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff_internal(
993 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
1000 pma
= set_iterator_names(build
, pma
);
1002 return isl_pw_multi_aff_free(pma
);
1004 ctx
= isl_ast_build_get_ctx(build
);
1005 n
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
1006 expr
= isl_ast_expr_alloc_op(ctx
, isl_ast_op_call
, 1 + n
);
1008 if (isl_pw_multi_aff_has_tuple_id(pma
, isl_dim_out
))
1009 id
= isl_pw_multi_aff_get_tuple_id(pma
, isl_dim_out
);
1011 id
= isl_id_alloc(ctx
, "", NULL
);
1013 expr
= isl_ast_expr_set_op_arg(expr
, 0, isl_ast_expr_from_id(id
));
1014 for (i
= 0; i
< n
; ++i
) {
1018 pa
= isl_pw_multi_aff_get_pw_aff(pma
, i
);
1019 arg
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
1020 expr
= isl_ast_expr_set_op_arg(expr
, 1 + i
, arg
);
1023 isl_pw_multi_aff_free(pma
);
1027 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
1028 * The name of the function is obtained from the output tuple name.
1029 * The arguments are given by the piecewise affine expressions.
1031 * The domain of "pma" is assumed to live in the external schedule domain.
1033 __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff(
1034 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
1038 isl_space
*space_build
, *space_pma
;
1040 space_build
= isl_ast_build_get_space(build
, 0);
1041 space_pma
= isl_pw_multi_aff_get_space(pma
);
1042 is_domain
= isl_space_tuple_match(space_build
, isl_dim_set
,
1043 space_pma
, isl_dim_in
);
1044 isl_space_free(space_build
);
1045 isl_space_free(space_pma
);
1047 return isl_pw_multi_aff_free(pma
);
1049 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
1050 "spaces don't match",
1051 return isl_pw_multi_aff_free(pma
));
1053 if (isl_ast_build_need_schedule_map(build
)) {
1055 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
1056 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
1059 expr
= isl_ast_build_call_from_pw_multi_aff_internal(build
, pma
);
1063 /* Construct an isl_ast_expr that calls the domain element
1064 * specified by "executed".
1066 * "executed" is assumed to be single-valued, with a domain that lives
1067 * in the internal schedule space.
1069 __isl_give isl_ast_node
*isl_ast_build_call_from_executed(
1070 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*executed
)
1072 isl_pw_multi_aff
*iteration
;
1075 iteration
= isl_pw_multi_aff_from_map(executed
);
1076 iteration
= isl_ast_build_compute_gist_pw_multi_aff(build
, iteration
);
1077 iteration
= isl_pw_multi_aff_intersect_domain(iteration
,
1078 isl_ast_build_get_domain(build
));
1079 expr
= isl_ast_build_call_from_pw_multi_aff_internal(build
, iteration
);
1080 return isl_ast_node_alloc_user(expr
);