2 * Copyright 2012 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 * A modulo expression is of the form
446 * a mod m = a - m * floor(a / m)
448 * To detect them in aff, we look for terms of the form
450 * (f * m * floor(a / m)) / d
454 * (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d
456 * and extract out -f * (a mod m).
457 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
458 * If f < 0, we add ((-f) * (a mod m)) to *pos.
460 * The caller is responsible for dividing *neg and/or *pos by d.
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 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
497 * The result is simplified in terms of build->domain.
499 * We first extract hidden modulo computations from the affine expression
500 * and then add terms for each variable with a non-zero coefficient.
501 * Finally, if the affine expression has a non-trivial denominator,
502 * we divide the resulting isl_ast_expr by this denominator.
504 __isl_give isl_ast_expr
*isl_ast_expr_from_aff(__isl_take isl_aff
*aff
,
505 __isl_keep isl_ast_build
*build
)
510 isl_ctx
*ctx
= isl_aff_get_ctx(aff
);
511 isl_ast_expr
*expr
, *expr_neg
;
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
};
519 expr
= isl_ast_expr_alloc_int_si(ctx
, 0);
520 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
522 aff
= extract_modulos(aff
, &expr
, &expr_neg
, build
);
523 expr
= ast_expr_sub(expr
, expr_neg
);
525 d
= isl_aff_get_denominator_val(aff
);
526 aff
= isl_aff_scale_val(aff
, isl_val_copy(d
));
528 ls
= isl_aff_get_domain_local_space(aff
);
530 for (i
= 0; i
< 3; ++i
) {
531 n
= isl_aff_dim(aff
, t
[i
]);
532 for (j
= 0; j
< n
; ++j
) {
533 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
535 expr
= isl_ast_expr_free(expr
);
536 if (isl_val_is_zero(v
)) {
540 expr
= isl_ast_expr_add_term(expr
,
541 ls
, l
[i
], j
, v
, build
);
545 v
= isl_aff_get_constant_val(aff
);
546 expr
= isl_ast_expr_add_int(expr
, v
);
548 if (!isl_val_is_one(d
))
549 expr
= isl_ast_expr_div(expr
, isl_ast_expr_from_val(d
));
553 isl_local_space_free(ls
);
558 /* Add terms to "expr" for each variable in "aff" with a coefficient
559 * with sign equal to "sign".
560 * The result is simplified in terms of build->domain.
562 static __isl_give isl_ast_expr
*add_signed_terms(__isl_take isl_ast_expr
*expr
,
563 __isl_keep isl_aff
*aff
, int sign
, __isl_keep isl_ast_build
*build
)
567 enum isl_dim_type t
[] = { isl_dim_param
, isl_dim_in
, isl_dim_div
};
568 enum isl_dim_type l
[] = { isl_dim_param
, isl_dim_set
, isl_dim_div
};
571 ls
= isl_aff_get_domain_local_space(aff
);
573 for (i
= 0; i
< 3; ++i
) {
574 int n
= isl_aff_dim(aff
, t
[i
]);
575 for (j
= 0; j
< n
; ++j
) {
576 v
= isl_aff_get_coefficient_val(aff
, t
[i
], j
);
577 if (sign
* isl_val_sgn(v
) <= 0) {
582 expr
= isl_ast_expr_add_term(expr
,
583 ls
, l
[i
], j
, v
, build
);
587 isl_local_space_free(ls
);
592 /* Should the constant term "v" be considered positive?
594 * A positive constant will be added to "pos" by the caller,
595 * while a negative constant will be added to "neg".
596 * If either "pos" or "neg" is exactly zero, then we prefer
597 * to add the constant "v" to that side, irrespective of the sign of "v".
598 * This results in slightly shorter expressions and may reduce the risk
601 static int constant_is_considered_positive(__isl_keep isl_val
*v
,
602 __isl_keep isl_ast_expr
*pos
, __isl_keep isl_ast_expr
*neg
)
604 if (ast_expr_is_zero(pos
))
606 if (ast_expr_is_zero(neg
))
608 return isl_val_is_pos(v
);
611 /* Construct an isl_ast_expr that evaluates the condition "constraint",
612 * The result is simplified in terms of build->domain.
614 * Let the constraint by either "a >= 0" or "a == 0".
615 * We first extract hidden modulo computations from "a"
616 * and then collect all the terms with a positive coefficient in cons_pos
617 * and the terms with a negative coefficient in cons_neg.
619 * The result is then of the form
621 * (isl_ast_op_ge, expr(pos), expr(-neg)))
625 * (isl_ast_op_eq, expr(pos), expr(-neg)))
627 * However, if the first expression is an integer constant (and the second
628 * is not), then we swap the two expressions. This ensures that we construct,
629 * e.g., "i <= 5" rather than "5 >= i".
631 * Furthermore, is there are no terms with positive coefficients (or no terms
632 * with negative coefficients), then the constant term is added to "pos"
633 * (or "neg"), ignoring the sign of the constant term.
635 static __isl_give isl_ast_expr
*isl_ast_expr_from_constraint(
636 __isl_take isl_constraint
*constraint
, __isl_keep isl_ast_build
*build
)
639 isl_ast_expr
*expr_pos
;
640 isl_ast_expr
*expr_neg
;
645 enum isl_ast_op_type type
;
650 aff
= isl_constraint_get_aff(constraint
);
652 ctx
= isl_constraint_get_ctx(constraint
);
653 expr_pos
= isl_ast_expr_alloc_int_si(ctx
, 0);
654 expr_neg
= isl_ast_expr_alloc_int_si(ctx
, 0);
656 aff
= extract_modulos(aff
, &expr_pos
, &expr_neg
, build
);
658 expr_pos
= add_signed_terms(expr_pos
, aff
, 1, build
);
659 expr_neg
= add_signed_terms(expr_neg
, aff
, -1, build
);
661 v
= isl_aff_get_constant_val(aff
);
662 if (constant_is_considered_positive(v
, expr_pos
, expr_neg
)) {
663 expr_pos
= isl_ast_expr_add_int(expr_pos
, v
);
666 expr_neg
= isl_ast_expr_add_int(expr_neg
, v
);
669 eq
= isl_constraint_is_equality(constraint
);
671 if (isl_ast_expr_get_type(expr_pos
) == isl_ast_expr_int
&&
672 isl_ast_expr_get_type(expr_neg
) != isl_ast_expr_int
) {
673 type
= eq
? isl_ast_op_eq
: isl_ast_op_le
;
674 expr
= isl_ast_expr_alloc_binary(type
, expr_neg
, expr_pos
);
676 type
= eq
? isl_ast_op_eq
: isl_ast_op_ge
;
677 expr
= isl_ast_expr_alloc_binary(type
, expr_pos
, expr_neg
);
680 isl_constraint_free(constraint
);
685 struct isl_expr_from_basic_data
{
686 isl_ast_build
*build
;
691 /* Construct an isl_ast_expr that evaluates the condition "c",
692 * except if it is a div constraint, and add it to the data->res.
693 * The result is simplified in terms of data->build->domain.
695 static int expr_from_basic_set(__isl_take isl_constraint
*c
, void *user
)
697 struct isl_expr_from_basic_data
*data
= user
;
700 if (isl_constraint_is_div_constraint(c
)) {
701 isl_constraint_free(c
);
705 expr
= isl_ast_expr_from_constraint(c
, data
->build
);
709 data
->res
= isl_ast_expr_and(data
->res
, expr
);
718 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
719 * The result is simplified in terms of build->domain.
721 * We filter out the div constraints during printing, so we do not know
722 * in advance how many constraints are going to be printed.
724 * If it turns out that there was no constraint, then we contruct
725 * the expression "1", i.e., "true".
727 __isl_give isl_ast_expr
*isl_ast_build_expr_from_basic_set(
728 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
730 struct isl_expr_from_basic_data data
= { build
, 1, NULL
};
732 if (isl_basic_set_foreach_constraint(bset
,
733 &expr_from_basic_set
, &data
) < 0) {
734 data
.res
= isl_ast_expr_free(data
.res
);
735 } else if (data
.res
== NULL
) {
736 isl_ctx
*ctx
= isl_basic_set_get_ctx(bset
);
737 data
.res
= isl_ast_expr_alloc_int_si(ctx
, 1);
740 isl_basic_set_free(bset
);
744 struct isl_expr_from_set_data
{
745 isl_ast_build
*build
;
750 /* Construct an isl_ast_expr that evaluates the conditions defining "bset"
751 * and add it to data->res.
752 * The result is simplified in terms of data->build->domain.
754 static int expr_from_set(__isl_take isl_basic_set
*bset
, void *user
)
756 struct isl_expr_from_set_data
*data
= user
;
759 expr
= isl_ast_build_expr_from_basic_set(data
->build
, bset
);
763 data
->res
= isl_ast_expr_or(data
->res
, expr
);
772 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
773 * The result is simplified in terms of build->domain.
775 __isl_give isl_ast_expr
*isl_ast_build_expr_from_set(
776 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
778 struct isl_expr_from_set_data data
= { build
, 1, NULL
};
780 if (isl_set_foreach_basic_set(set
, &expr_from_set
, &data
) < 0)
781 data
.res
= isl_ast_expr_free(data
.res
);
787 struct isl_from_pw_aff_data
{
788 isl_ast_build
*build
;
794 /* This function is called during the construction of an isl_ast_expr
795 * that evaluates an isl_pw_aff.
796 * Adjust data->next to take into account this piece.
798 * data->n is the number of pairs of set and aff to go.
799 * data->dom is the domain of the entire isl_pw_aff.
801 * If this is the last pair, then data->next is set to evaluate aff
802 * and the domain is ignored.
803 * Otherwise, data->next is set to a select operation that selects
804 * an isl_ast_expr correponding to "aff" on "set" and to an expression
805 * that will be filled in by later calls otherwise.
807 static int ast_expr_from_pw_aff(__isl_take isl_set
*set
,
808 __isl_take isl_aff
*aff
, void *user
)
810 struct isl_from_pw_aff_data
*data
= user
;
813 ctx
= isl_set_get_ctx(set
);
816 *data
->next
= isl_ast_expr_from_aff(aff
, data
->build
);
821 isl_ast_expr
*ternary
, *arg
;
823 ternary
= isl_ast_expr_alloc_op(ctx
, isl_ast_op_select
, 3);
824 set
= isl_set_gist(set
, isl_set_copy(data
->dom
));
825 arg
= isl_ast_build_expr_from_set(data
->build
, set
);
826 ternary
= isl_ast_expr_set_op_arg(ternary
, 0, arg
);
827 arg
= isl_ast_expr_from_aff(aff
, data
->build
);
828 ternary
= isl_ast_expr_set_op_arg(ternary
, 1, arg
);
832 *data
->next
= ternary
;
833 data
->next
= &ternary
->u
.op
.args
[2];
839 /* Construct an isl_ast_expr that evaluates "pa".
840 * The result is simplified in terms of build->domain.
842 * The domain of "pa" lives in the internal schedule space.
844 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff_internal(
845 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
847 struct isl_from_pw_aff_data data
;
848 isl_ast_expr
*res
= NULL
;
854 data
.n
= isl_pw_aff_n_piece(pa
);
856 data
.dom
= isl_pw_aff_domain(isl_pw_aff_copy(pa
));
858 if (isl_pw_aff_foreach_piece(pa
, &ast_expr_from_pw_aff
, &data
) < 0)
859 res
= isl_ast_expr_free(res
);
861 isl_die(isl_pw_aff_get_ctx(pa
), isl_error_invalid
,
862 "cannot handle void expression", res
= NULL
);
865 isl_set_free(data
.dom
);
869 /* Construct an isl_ast_expr that evaluates "pa".
870 * The result is simplified in terms of build->domain.
872 * The domain of "pa" lives in the external schedule space.
874 __isl_give isl_ast_expr
*isl_ast_build_expr_from_pw_aff(
875 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
879 if (isl_ast_build_need_schedule_map(build
)) {
881 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
882 pa
= isl_pw_aff_pullback_multi_aff(pa
, ma
);
884 expr
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
888 /* Set the ids of the input dimensions of "pma" to the iterator ids
891 * The domain of "pma" is assumed to live in the internal schedule domain.
893 static __isl_give isl_pw_multi_aff
*set_iterator_names(
894 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
898 n
= isl_pw_multi_aff_dim(pma
, isl_dim_in
);
899 for (i
= 0; i
< n
; ++i
) {
902 id
= isl_ast_build_get_iterator_id(build
, i
);
903 pma
= isl_pw_multi_aff_set_dim_id(pma
, isl_dim_in
, i
, id
);
909 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
910 * The name of the function is obtained from the output tuple name.
911 * The arguments are given by the piecewise affine expressions.
913 * The domain of "pma" is assumed to live in the internal schedule domain.
915 static __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff_internal(
916 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
923 pma
= set_iterator_names(build
, pma
);
925 return isl_pw_multi_aff_free(pma
);
927 ctx
= isl_ast_build_get_ctx(build
);
928 n
= isl_pw_multi_aff_dim(pma
, isl_dim_out
);
929 expr
= isl_ast_expr_alloc_op(ctx
, isl_ast_op_call
, 1 + n
);
931 if (isl_pw_multi_aff_has_tuple_id(pma
, isl_dim_out
))
932 id
= isl_pw_multi_aff_get_tuple_id(pma
, isl_dim_out
);
934 id
= isl_id_alloc(ctx
, "", NULL
);
936 expr
= isl_ast_expr_set_op_arg(expr
, 0, isl_ast_expr_from_id(id
));
937 for (i
= 0; i
< n
; ++i
) {
941 pa
= isl_pw_multi_aff_get_pw_aff(pma
, i
);
942 arg
= isl_ast_build_expr_from_pw_aff_internal(build
, pa
);
943 expr
= isl_ast_expr_set_op_arg(expr
, 1 + i
, arg
);
946 isl_pw_multi_aff_free(pma
);
950 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
951 * The name of the function is obtained from the output tuple name.
952 * The arguments are given by the piecewise affine expressions.
954 * The domain of "pma" is assumed to live in the external schedule domain.
956 __isl_give isl_ast_expr
*isl_ast_build_call_from_pw_multi_aff(
957 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
961 isl_space
*space_build
, *space_pma
;
963 space_build
= isl_ast_build_get_space(build
, 0);
964 space_pma
= isl_pw_multi_aff_get_space(pma
);
965 is_domain
= isl_space_tuple_match(space_build
, isl_dim_set
,
966 space_pma
, isl_dim_in
);
967 isl_space_free(space_build
);
968 isl_space_free(space_pma
);
970 return isl_pw_multi_aff_free(pma
);
972 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
973 "spaces don't match",
974 return isl_pw_multi_aff_free(pma
));
976 if (isl_ast_build_need_schedule_map(build
)) {
978 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
979 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
, ma
);
982 expr
= isl_ast_build_call_from_pw_multi_aff_internal(build
, pma
);
986 /* Construct an isl_ast_expr that calls the domain element
987 * specified by "executed".
989 * "executed" is assumed to be single-valued, with a domain that lives
990 * in the internal schedule space.
992 __isl_give isl_ast_node
*isl_ast_build_call_from_executed(
993 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*executed
)
995 isl_pw_multi_aff
*iteration
;
998 iteration
= isl_pw_multi_aff_from_map(executed
);
999 iteration
= isl_ast_build_compute_gist_pw_multi_aff(build
, iteration
);
1000 iteration
= isl_pw_multi_aff_intersect_domain(iteration
,
1001 isl_ast_build_get_domain(build
));
1002 expr
= isl_ast_build_call_from_pw_multi_aff_internal(build
, iteration
);
1003 return isl_ast_node_alloc_user(expr
);