isl_union_set_compute_schedule: ensure carry_dependences makes progress
[isl.git] / isl_ast_build_expr.c
blob81688dee22243ecf0037c111341382d8098ac04e
1 /*
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
8 */
10 #include <isl/ilp.h>
11 #include <isl_ast_build_expr.h>
12 #include <isl_ast_private.h>
13 #include <isl_ast_build_private.h>
15 /* Compute the minimum of the integer affine expression "obj" over the points
16 * in build->domain and put the result in *opt.
18 enum isl_lp_result isl_ast_build_min(__isl_keep isl_ast_build *build,
19 __isl_keep isl_aff *obj, isl_int *opt)
21 if (!build)
22 return isl_lp_error;
24 return isl_set_min(build->domain, obj, opt);
27 /* Compute the maximum of the integer affine expression "obj" over the points
28 * in build->domain and put the result in *opt.
30 enum isl_lp_result isl_ast_build_max(__isl_keep isl_ast_build *build,
31 __isl_keep isl_aff *obj, isl_int *opt)
33 if (!build)
34 return isl_lp_error;
36 return isl_set_max(build->domain, obj, opt);
39 /* Compute the "opposite" of the (numerator of the) argument of a div
40 * with denonimator "d".
42 * In particular, compute
44 * -aff + (d - 1)
46 static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff, isl_int d)
48 aff = isl_aff_neg(aff);
49 aff = isl_aff_add_constant(aff, d);
50 aff = isl_aff_add_constant_si(aff, -1);
52 return aff;
55 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
56 * The result is simplified in terms of build->domain.
58 * "v" points to the coefficient of the div in the expression where it
59 * appears and may be updated by this function.
60 * "ls" is known to be non-NULL.
62 * Let the div be of the form floor(e/d).
63 * If the ast_build_prefer_pdiv option is set then we check if "e"
64 * is non-negative, so that we can generate
66 * (pdiv_q, expr(e), expr(d))
68 * instead of
70 * (fdiv_q, expr(e), expr(d))
72 * If the ast_build_prefer_pdiv option is set and
73 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
74 * If so, we can rewrite
76 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
78 * and still use pdiv_q.
80 static __isl_give isl_ast_expr *var_div(isl_int *v,
81 __isl_keep isl_local_space *ls,
82 int pos, __isl_keep isl_ast_build *build)
84 isl_ctx *ctx = isl_local_space_get_ctx(ls);
85 isl_aff *aff;
86 isl_ast_expr *num, *den;
87 isl_int d;
88 enum isl_ast_op_type type;
90 aff = isl_local_space_get_div(ls, pos);
91 isl_int_init(d);
92 isl_aff_get_denominator(aff, &d);
93 aff = isl_aff_scale(aff, d);
94 den = isl_ast_expr_alloc_int(ctx, d);
96 type = isl_ast_op_fdiv_q;
97 if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
98 int non_neg = isl_ast_build_aff_is_nonneg(build, aff);
99 if (non_neg >= 0 && !non_neg) {
100 isl_aff *opp = oppose_div_arg(isl_aff_copy(aff), d);
101 non_neg = isl_ast_build_aff_is_nonneg(build, opp);
102 if (non_neg >= 0 && non_neg) {
103 isl_int_neg(*v, *v);
104 isl_aff_free(aff);
105 aff = opp;
106 } else
107 isl_aff_free(opp);
109 if (non_neg < 0)
110 aff = isl_aff_free(aff);
111 else if (non_neg)
112 type = isl_ast_op_pdiv_q;
115 isl_int_clear(d);
116 num = isl_ast_expr_from_aff(aff, build);
117 return isl_ast_expr_alloc_binary(type, num, den);
120 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
121 * The result is simplified in terms of build->domain.
123 * "v" points to the coefficient of the specified dimension
124 * in the expression where it appears and may be updated by this function.
126 * The isl_ast_expr is constructed based on the type of the dimension.
127 * - divs are constructed by var_div
128 * - set variables are constructed from the iterator isl_ids in "build"
129 * - parameters are constructed from the isl_ids in "ls"
131 static __isl_give isl_ast_expr *var(isl_int *v, __isl_keep isl_local_space *ls,
132 enum isl_dim_type type, int pos, __isl_keep isl_ast_build *build)
134 isl_ctx *ctx = isl_local_space_get_ctx(ls);
135 isl_id *id;
137 if (type == isl_dim_div)
138 return var_div(v, ls, pos, build);
140 if (type == isl_dim_set) {
141 id = isl_ast_build_get_iterator_id(build, pos);
142 return isl_ast_expr_from_id(id);
145 if (!isl_local_space_has_dim_id(ls, type, pos))
146 isl_die(ctx, isl_error_internal, "unnamed dimension",
147 return NULL);
148 id = isl_local_space_get_dim_id(ls, type, pos);
149 return isl_ast_expr_from_id(id);
152 /* Does "expr" represent the zero integer?
154 static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
156 if (!expr)
157 return -1;
158 if (expr->type != isl_ast_expr_int)
159 return 0;
160 return isl_int_is_zero(expr->u.i);
163 /* Create an expression representing the sum of "expr1" and "expr2",
164 * provided neither of the two expressions is identically zero.
166 static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
167 __isl_take isl_ast_expr *expr2)
169 if (!expr1 || !expr2)
170 goto error;
172 if (ast_expr_is_zero(expr1)) {
173 isl_ast_expr_free(expr1);
174 return expr2;
177 if (ast_expr_is_zero(expr2)) {
178 isl_ast_expr_free(expr2);
179 return expr1;
182 return isl_ast_expr_add(expr1, expr2);
183 error:
184 isl_ast_expr_free(expr1);
185 isl_ast_expr_free(expr2);
186 return NULL;
189 /* Subtract expr2 from expr1.
191 * If expr2 is zero, we simply return expr1.
192 * If expr1 is zero, we return
194 * (isl_ast_op_minus, expr2)
196 * Otherwise, we return
198 * (isl_ast_op_sub, expr1, expr2)
200 static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
201 __isl_take isl_ast_expr *expr2)
203 if (!expr1 || !expr2)
204 goto error;
206 if (ast_expr_is_zero(expr2)) {
207 isl_ast_expr_free(expr2);
208 return expr1;
211 if (ast_expr_is_zero(expr1)) {
212 isl_ast_expr_free(expr1);
213 return isl_ast_expr_neg(expr2);
216 return isl_ast_expr_sub(expr1, expr2);
217 error:
218 isl_ast_expr_free(expr1);
219 isl_ast_expr_free(expr2);
220 return NULL;
223 /* Return an isl_ast_expr that represents
225 * v * (aff mod d)
227 * v is assumed to be non-negative.
228 * The result is simplified in terms of build->domain.
230 static __isl_give isl_ast_expr *isl_ast_expr_mod(isl_int v,
231 __isl_keep isl_aff *aff, isl_int d, __isl_keep isl_ast_build *build)
233 isl_ctx *ctx;
234 isl_ast_expr *expr;
235 isl_ast_expr *c;
237 if (!aff)
238 return NULL;
240 ctx = isl_aff_get_ctx(aff);
241 expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
243 c = isl_ast_expr_alloc_int(ctx, d);
244 expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
246 if (!isl_int_is_one(v)) {
247 c = isl_ast_expr_alloc_int(ctx, v);
248 expr = isl_ast_expr_mul(c, expr);
251 return expr;
254 /* Create an isl_ast_expr that scales "expr" by "v".
256 * If v is 1, we simply return expr.
257 * If v is -1, we return
259 * (isl_ast_op_minus, expr)
261 * Otherwise, we return
263 * (isl_ast_op_mul, expr(v), expr)
265 static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr, isl_int v)
267 isl_ctx *ctx;
268 isl_ast_expr *c;
270 if (!expr)
271 return NULL;
272 if (isl_int_is_one(v))
273 return expr;
275 if (isl_int_is_negone(v)) {
276 expr = isl_ast_expr_neg(expr);
277 } else {
278 ctx = isl_ast_expr_get_ctx(expr);
279 c = isl_ast_expr_alloc_int(ctx, v);
280 expr = isl_ast_expr_mul(c, expr);
283 return expr;
286 /* Add an expression for "*v" times the specified dimension of "ls"
287 * to expr.
289 * Let e be the expression for the specified dimension,
290 * multiplied by the absolute value of "*v".
291 * If "*v" is negative, we create
293 * (isl_ast_op_sub, expr, e)
295 * except when expr is trivially zero, in which case we create
297 * (isl_ast_op_minus, e)
299 * instead.
301 * If "*v" is positive, we simply create
303 * (isl_ast_op_add, expr, e)
306 static __isl_give isl_ast_expr *isl_ast_expr_add_term(
307 __isl_take isl_ast_expr *expr,
308 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
309 isl_int *v, __isl_keep isl_ast_build *build)
311 isl_ast_expr *term;
313 if (!expr)
314 return NULL;
316 term = var(v, ls, type, pos, build);
318 if (isl_int_is_neg(*v) && !ast_expr_is_zero(expr)) {
319 isl_int_neg(*v, *v);
320 term = scale(term, *v);
321 return ast_expr_sub(expr, term);
322 } else {
323 term = scale(term, *v);
324 return ast_expr_add(expr, term);
328 /* Add an expression for "v" to expr.
330 static __isl_give isl_ast_expr *isl_ast_expr_add_int(
331 __isl_take isl_ast_expr *expr, isl_int v)
333 isl_ctx *ctx;
334 isl_ast_expr *expr_int;
336 if (!expr)
337 return NULL;
339 if (isl_int_is_zero(v))
340 return expr;
342 ctx = isl_ast_expr_get_ctx(expr);
343 if (isl_int_is_neg(v) && !ast_expr_is_zero(expr)) {
344 isl_int_neg(v, v);
345 expr_int = isl_ast_expr_alloc_int(ctx, v);
346 return ast_expr_sub(expr, expr_int);
347 } else {
348 expr_int = isl_ast_expr_alloc_int(ctx, v);
349 return ast_expr_add(expr, expr_int);
353 /* Check if "aff" involves any (implicit) modulo computations based
354 * on div "j".
355 * If so, remove them from aff and add expressions corresponding
356 * to those modulo computations to *pos and/or *neg.
357 * "v" is the coefficient of div "j".
359 * In particular, check if (v * div_j) / d is of the form
361 * (f * m * floor(a / m)) / d
363 * and, if so, rewrite it as
365 * (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d
367 * and extract out -f * (a mod m).
368 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
369 * If f < 0, we add ((-f) * (a mod m)) to *pos.
371 * Note that in order to represent "a mod m" as
373 * (isl_ast_op_pdiv_r, a, m)
375 * we need to make sure that a is non-negative.
376 * If not, we check if "-a + m - 1" is non-negative.
377 * If so, we can rewrite
379 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
381 * and still extract a modulo.
383 * The caller is responsible for dividing *neg and/or *pos by d.
385 static __isl_give isl_aff *extract_modulo(__isl_take isl_aff *aff,
386 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
387 __isl_keep isl_ast_build *build, int j, isl_int v)
389 isl_ast_expr *expr;
390 isl_aff *div;
391 int s;
392 int mod;
393 isl_int d;
395 isl_int_init(d);
396 div = isl_aff_get_div(aff, j);
397 isl_aff_get_denominator(div, &d);
398 mod = isl_int_is_divisible_by(v, d);
399 if (mod) {
400 div = isl_aff_scale(div, d);
401 mod = isl_ast_build_aff_is_nonneg(build, div);
402 if (mod >= 0 && !mod) {
403 isl_aff *opp = oppose_div_arg(isl_aff_copy(div), d);
404 mod = isl_ast_build_aff_is_nonneg(build, opp);
405 if (mod >= 0 && mod) {
406 isl_aff_free(div);
407 div = opp;
408 isl_int_neg(v, v);
409 } else
410 isl_aff_free(opp);
413 if (mod < 0) {
414 isl_aff_free(div);
415 isl_int_clear(d);
416 return isl_aff_free(aff);
417 } else if (!mod) {
418 isl_aff_free(div);
419 isl_int_clear(d);
420 return aff;
422 isl_int_divexact(v, v, d);
423 s = isl_int_sgn(v);
424 isl_int_abs(v, v);
425 expr = isl_ast_expr_mod(v, div, d, build);
426 if (s > 0)
427 *neg = ast_expr_add(*neg, expr);
428 else
429 *pos = ast_expr_add(*pos, expr);
430 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, j, 0);
431 if (s < 0)
432 isl_int_neg(v, v);
433 div = isl_aff_scale(div, v);
434 isl_aff_get_denominator(aff, &d);
435 div = isl_aff_scale_down(div, d);
436 aff = isl_aff_add(aff, div);
437 isl_int_clear(d);
439 return aff;
442 /* Check if "aff" involves any (implicit) modulo computations.
443 * If so, remove them from aff and add expressions corresponding
444 * to those modulo computations to *pos and/or *neg.
445 * We only do this if the option ast_build_prefer_pdiv is set.
447 * A modulo expression is of the form
449 * a mod m = a - m * floor(a / m)
451 * To detect them in aff, we look for terms of the form
453 * (f * m * floor(a / m)) / d
455 * rewrite them as
457 * (f * (a - (a mod m))) / d = (f * a) / d - (f * (a mod m)) / d
459 * and extract out -f * (a mod m).
460 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
461 * If f < 0, we add ((-f) * (a mod m)) to *pos.
463 * The caller is responsible for dividing *neg and/or *pos by d.
465 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
466 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
467 __isl_keep isl_ast_build *build)
469 isl_ctx *ctx;
470 int j, n;
471 isl_int v;
473 if (!aff)
474 return NULL;
476 ctx = isl_aff_get_ctx(aff);
477 if (!isl_options_get_ast_build_prefer_pdiv(ctx))
478 return aff;
480 isl_int_init(v);
482 n = isl_aff_dim(aff, isl_dim_div);
483 for (j = 0; j < n; ++j) {
484 isl_aff_get_coefficient(aff, isl_dim_div, j, &v);
485 if (isl_int_is_zero(v) ||
486 isl_int_is_one(v) || isl_int_is_negone(v))
487 continue;
488 aff = extract_modulo(aff, pos, neg, build, j, v);
489 if (!aff)
490 break;
493 isl_int_clear(v);
495 return aff;
498 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
499 * The result is simplified in terms of build->domain.
501 * We first extract hidden modulo computations from the affine expression
502 * and then add terms for each variable with a non-zero coefficient.
503 * Finally, if the affine expression has a non-trivial denominator,
504 * we divide the resulting isl_ast_expr by this denominator.
506 __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
507 __isl_keep isl_ast_build *build)
509 int i, j;
510 isl_int v;
511 int n;
512 isl_ctx *ctx = isl_aff_get_ctx(aff);
513 isl_ast_expr *expr, *expr_neg;
514 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
515 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
516 isl_local_space *ls;
518 if (!aff)
519 return NULL;
521 expr = isl_ast_expr_alloc_int_si(ctx, 0);
522 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
524 aff = extract_modulos(aff, &expr, &expr_neg, build);
525 expr = ast_expr_sub(expr, expr_neg);
527 isl_int_init(v);
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 isl_aff_get_coefficient(aff, t[i], j, &v);
534 if (isl_int_is_zero(v))
535 continue;
536 expr = isl_ast_expr_add_term(expr,
537 ls, l[i], j, &v, build);
541 isl_aff_get_constant(aff, &v);
542 expr = isl_ast_expr_add_int(expr, v);
544 isl_aff_get_denominator(aff, &v);
545 if (!isl_int_is_one(v)) {
546 isl_ast_expr *d;
547 d = isl_ast_expr_alloc_int(ctx, v);
548 expr = isl_ast_expr_div(expr, d);
551 isl_local_space_free(ls);
552 isl_int_clear(v);
553 isl_aff_free(aff);
554 return expr;
557 /* Add terms to "expr" for each variable in "aff" with a coefficient
558 * with sign equal to "sign".
559 * The result is simplified in terms of build->domain.
561 static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
562 __isl_keep isl_aff *aff, int sign, __isl_keep isl_ast_build *build)
564 int i, j;
565 isl_int v;
566 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
567 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
568 isl_local_space *ls;
570 isl_int_init(v);
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 isl_aff_get_coefficient(aff, t[i], j, &v);
577 if (sign * isl_int_sgn(v) <= 0)
578 continue;
579 isl_int_abs(v, v);
580 expr = isl_ast_expr_add_term(expr,
581 ls, l[i], j, &v, build);
585 isl_aff_get_constant(aff, &v);
586 if (sign * isl_int_sgn(v) > 0) {
587 isl_int_abs(v, v);
588 expr = isl_ast_expr_add_int(expr, v);
591 isl_local_space_free(ls);
592 isl_int_clear(v);
594 return expr;
597 /* Construct an isl_ast_expr that evaluates the condition "constraint",
598 * The result is simplified in terms of build->domain.
600 * Let the constraint by either "a >= 0" or "a == 0".
601 * We first extract hidden modulo computations from "a"
602 * and then collect all the terms with a positive coefficient in cons_pos
603 * and the terms with a negative coefficient in cons_neg.
605 * The result is then of the form
607 * (isl_ast_op_ge, expr(pos), expr(-neg)))
609 * or
611 * (isl_ast_op_eq, expr(pos), expr(-neg)))
613 * However, if the first expression is an integer constant (and the second
614 * is not), then we swap the two expressions. This ensures that we construct,
615 * e.g., "i <= 5" rather than "5 >= i".
617 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
618 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
620 isl_ctx *ctx;
621 isl_ast_expr *expr_pos;
622 isl_ast_expr *expr_neg;
623 isl_ast_expr *expr;
624 isl_aff *aff;
625 int eq;
626 enum isl_ast_op_type type;
628 if (!constraint)
629 return NULL;
631 aff = isl_constraint_get_aff(constraint);
633 ctx = isl_constraint_get_ctx(constraint);
634 expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
635 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
637 aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
639 expr_pos = add_signed_terms(expr_pos, aff, 1, build);
640 expr_neg = add_signed_terms(expr_neg, aff, -1, build);
642 eq = isl_constraint_is_equality(constraint);
644 if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
645 isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
646 type = eq ? isl_ast_op_eq : isl_ast_op_le;
647 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
648 } else {
649 type = eq ? isl_ast_op_eq : isl_ast_op_ge;
650 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
653 isl_constraint_free(constraint);
654 isl_aff_free(aff);
655 return expr;
658 struct isl_expr_from_basic_data {
659 isl_ast_build *build;
660 int first;
661 isl_ast_expr *res;
664 /* Construct an isl_ast_expr that evaluates the condition "c",
665 * except if it is a div constraint, and add it to the data->res.
666 * The result is simplified in terms of data->build->domain.
668 static int expr_from_basic_set(__isl_take isl_constraint *c, void *user)
670 struct isl_expr_from_basic_data *data = user;
671 isl_ast_expr *expr;
673 if (isl_constraint_is_div_constraint(c)) {
674 isl_constraint_free(c);
675 return 0;
678 expr = isl_ast_expr_from_constraint(c, data->build);
679 if (data->first)
680 data->res = expr;
681 else
682 data->res = isl_ast_expr_and(data->res, expr);
684 data->first = 0;
686 if (!data->res)
687 return -1;
688 return 0;
691 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
692 * The result is simplified in terms of build->domain.
694 * We filter out the div constraints during printing, so we do not know
695 * in advance how many constraints are going to be printed.
697 * If it turns out that there was no constraint, then we contruct
698 * the expression "1", i.e., "true".
700 __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
701 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
703 struct isl_expr_from_basic_data data = { build, 1, NULL };
705 if (isl_basic_set_foreach_constraint(bset,
706 &expr_from_basic_set, &data) < 0) {
707 data.res = isl_ast_expr_free(data.res);
708 } else if (data.res == NULL) {
709 isl_ctx *ctx = isl_basic_set_get_ctx(bset);
710 data.res = isl_ast_expr_alloc_int_si(ctx, 1);
713 isl_basic_set_free(bset);
714 return data.res;
717 struct isl_expr_from_set_data {
718 isl_ast_build *build;
719 int first;
720 isl_ast_expr *res;
723 /* Construct an isl_ast_expr that evaluates the conditions defining "bset"
724 * and add it to data->res.
725 * The result is simplified in terms of data->build->domain.
727 static int expr_from_set(__isl_take isl_basic_set *bset, void *user)
729 struct isl_expr_from_set_data *data = user;
730 isl_ast_expr *expr;
732 expr = isl_ast_build_expr_from_basic_set(data->build, bset);
733 if (data->first)
734 data->res = expr;
735 else
736 data->res = isl_ast_expr_or(data->res, expr);
738 data->first = 0;
740 if (!data->res)
741 return -1;
742 return 0;
745 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
746 * The result is simplified in terms of build->domain.
748 __isl_give isl_ast_expr *isl_ast_build_expr_from_set(
749 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
751 struct isl_expr_from_set_data data = { build, 1, NULL };
753 if (isl_set_foreach_basic_set(set, &expr_from_set, &data) < 0)
754 data.res = isl_ast_expr_free(data.res);
756 isl_set_free(set);
757 return data.res;
760 struct isl_from_pw_aff_data {
761 isl_ast_build *build;
762 int n;
763 isl_ast_expr **next;
764 isl_set *dom;
767 /* This function is called during the construction of an isl_ast_expr
768 * that evaluates an isl_pw_aff.
769 * Adjust data->next to take into account this piece.
771 * data->n is the number of pairs of set and aff to go.
772 * data->dom is the domain of the entire isl_pw_aff.
774 * If this is the last pair, then data->next is set to evaluate aff
775 * and the domain is ignored.
776 * Otherwise, data->next is set to a select operation that selects
777 * an isl_ast_expr correponding to "aff" on "set" and to an expression
778 * that will be filled in by later calls otherwise.
780 static int ast_expr_from_pw_aff(__isl_take isl_set *set,
781 __isl_take isl_aff *aff, void *user)
783 struct isl_from_pw_aff_data *data = user;
784 isl_ctx *ctx;
786 ctx = isl_set_get_ctx(set);
787 data->n--;
788 if (data->n == 0) {
789 *data->next = isl_ast_expr_from_aff(aff, data->build);
790 isl_set_free(set);
791 if (!*data->next)
792 return -1;
793 } else {
794 isl_ast_expr *ternary, *arg;
796 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
797 set = isl_set_gist(set, isl_set_copy(data->dom));
798 arg = isl_ast_build_expr_from_set(data->build, set);
799 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
800 arg = isl_ast_expr_from_aff(aff, data->build);
801 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
802 if (!ternary)
803 return -1;
805 *data->next = ternary;
806 data->next = &ternary->u.op.args[2];
809 return 0;
812 /* Construct an isl_ast_expr that evaluates "pa".
813 * The result is simplified in terms of build->domain.
815 * The domain of "pa" lives in the internal schedule space.
817 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
818 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
820 struct isl_from_pw_aff_data data;
821 isl_ast_expr *res = NULL;
823 if (!pa)
824 return NULL;
826 data.build = build;
827 data.n = isl_pw_aff_n_piece(pa);
828 data.next = &res;
829 data.dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
831 if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0)
832 res = isl_ast_expr_free(res);
833 else if (!res)
834 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
835 "cannot handle void expression", res = NULL);
837 isl_pw_aff_free(pa);
838 isl_set_free(data.dom);
839 return res;
842 /* Construct an isl_ast_expr that evaluates "pa".
843 * The result is simplified in terms of build->domain.
845 * The domain of "pa" lives in the external schedule space.
847 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
848 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
850 isl_ast_expr *expr;
852 if (isl_ast_build_need_schedule_map(build)) {
853 isl_multi_aff *ma;
854 ma = isl_ast_build_get_schedule_map_multi_aff(build);
855 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
857 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
858 return expr;
861 /* Set the ids of the input dimensions of "pma" to the iterator ids
862 * of "build".
864 * The domain of "pma" is assumed to live in the internal schedule domain.
866 static __isl_give isl_pw_multi_aff *set_iterator_names(
867 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
869 int i, n;
871 n = isl_pw_multi_aff_dim(pma, isl_dim_in);
872 for (i = 0; i < n; ++i) {
873 isl_id *id;
875 id = isl_ast_build_get_iterator_id(build, i);
876 pma = isl_pw_multi_aff_set_dim_id(pma, isl_dim_in, i, id);
879 return pma;
882 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
883 * The name of the function is obtained from the output tuple name.
884 * The arguments are given by the piecewise affine expressions.
886 * The domain of "pma" is assumed to live in the internal schedule domain.
888 static __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff_internal(
889 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
891 int i, n;
892 isl_ctx *ctx;
893 isl_id *id;
894 isl_ast_expr *expr;
896 pma = set_iterator_names(build, pma);
897 if (!build || !pma)
898 return isl_pw_multi_aff_free(pma);
900 ctx = isl_ast_build_get_ctx(build);
901 n = isl_pw_multi_aff_dim(pma, isl_dim_out);
902 expr = isl_ast_expr_alloc_op(ctx, isl_ast_op_call, 1 + n);
904 if (isl_pw_multi_aff_has_tuple_id(pma, isl_dim_out))
905 id = isl_pw_multi_aff_get_tuple_id(pma, isl_dim_out);
906 else
907 id = isl_id_alloc(ctx, "", NULL);
909 expr = isl_ast_expr_set_op_arg(expr, 0, isl_ast_expr_from_id(id));
910 for (i = 0; i < n; ++i) {
911 isl_pw_aff *pa;
912 isl_ast_expr *arg;
914 pa = isl_pw_multi_aff_get_pw_aff(pma, i);
915 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
916 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
919 isl_pw_multi_aff_free(pma);
920 return expr;
923 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
924 * The name of the function is obtained from the output tuple name.
925 * The arguments are given by the piecewise affine expressions.
927 * The domain of "pma" is assumed to live in the external schedule domain.
929 __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
930 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
932 int is_domain;
933 isl_ast_expr *expr;
934 isl_space *space_build, *space_pma;
936 space_build = isl_ast_build_get_space(build, 0);
937 space_pma = isl_pw_multi_aff_get_space(pma);
938 is_domain = isl_space_tuple_match(space_build, isl_dim_set,
939 space_pma, isl_dim_in);
940 isl_space_free(space_build);
941 isl_space_free(space_pma);
942 if (is_domain < 0)
943 return isl_pw_multi_aff_free(pma);
944 if (!is_domain)
945 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
946 "spaces don't match",
947 return isl_pw_multi_aff_free(pma));
949 if (isl_ast_build_need_schedule_map(build)) {
950 isl_multi_aff *ma;
951 ma = isl_ast_build_get_schedule_map_multi_aff(build);
952 pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
955 expr = isl_ast_build_call_from_pw_multi_aff_internal(build, pma);
956 return expr;
959 /* Construct an isl_ast_expr that calls the domain element
960 * specified by "executed".
962 * "executed" is assumed to be single-valued, with a domain that lives
963 * in the internal schedule space.
965 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
966 __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
968 isl_pw_multi_aff *iteration;
969 isl_ast_expr *expr;
971 iteration = isl_pw_multi_aff_from_map(executed);
972 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
973 iteration = isl_pw_multi_aff_intersect_domain(iteration,
974 isl_ast_build_get_domain(build));
975 expr = isl_ast_build_call_from_pw_multi_aff_internal(build, iteration);
976 return isl_ast_node_alloc_user(expr);