isl_map_union_disjoint: check spaces before handling special cases
[isl.git] / isl_ast_build_expr.c
blobb0fdbb9d8822eb1884cfd3b70d9b488651adfad3
1 /*
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
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 "opposite" of the (numerator of the) argument of a div
16 * with denonimator "d".
18 * In particular, compute
20 * -aff + (d - 1)
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);
29 return aff;
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))
45 * instead of
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);
62 isl_aff *aff;
63 isl_ast_expr *num, *den;
64 isl_val *d;
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),
77 isl_val_copy(d));
78 non_neg = isl_ast_build_aff_is_nonneg(build, opp);
79 if (non_neg >= 0 && non_neg) {
80 *change_sign = 1;
81 isl_aff_free(aff);
82 aff = opp;
83 } else
84 isl_aff_free(opp);
86 if (non_neg < 0)
87 aff = isl_aff_free(aff);
88 else if (non_neg)
89 type = isl_ast_op_pdiv_q;
92 isl_val_free(d);
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);
113 isl_id *id;
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",
125 return NULL);
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)
134 if (!expr)
135 return -1;
136 if (expr->type != isl_ast_expr_int)
137 return 0;
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)
148 goto error;
150 if (ast_expr_is_zero(expr1)) {
151 isl_ast_expr_free(expr1);
152 return expr2;
155 if (ast_expr_is_zero(expr2)) {
156 isl_ast_expr_free(expr2);
157 return expr1;
160 return isl_ast_expr_add(expr1, expr2);
161 error:
162 isl_ast_expr_free(expr1);
163 isl_ast_expr_free(expr2);
164 return NULL;
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)
182 goto error;
184 if (ast_expr_is_zero(expr2)) {
185 isl_ast_expr_free(expr2);
186 return expr1;
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);
195 error:
196 isl_ast_expr_free(expr1);
197 isl_ast_expr_free(expr2);
198 return NULL;
201 /* Return an isl_ast_expr that represents
203 * v * (aff mod d)
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)
212 isl_ctx *ctx;
213 isl_ast_expr *expr;
214 isl_ast_expr *c;
216 if (!aff)
217 return NULL;
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);
230 return 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)
247 isl_ast_expr *c;
249 if (!expr || !v)
250 goto error;
251 if (isl_val_is_one(v)) {
252 isl_val_free(v);
253 return expr;
256 if (isl_val_is_negone(v)) {
257 isl_val_free(v);
258 expr = isl_ast_expr_neg(expr);
259 } else {
260 c = isl_ast_expr_from_val(v);
261 expr = isl_ast_expr_mul(c, expr);
264 return expr;
265 error:
266 isl_val_free(v);
267 isl_ast_expr_free(expr);
268 return NULL;
271 /* Add an expression for "*v" times the specified dimension of "ls"
272 * to expr.
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)
284 * instead.
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)
296 isl_ast_expr *term;
297 int change_sign;
299 if (!expr)
300 return NULL;
302 change_sign = 0;
303 term = var(&change_sign, ls, type, pos, build);
304 if (change_sign)
305 v = isl_val_neg(v);
307 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
308 v = isl_val_neg(v);
309 term = scale(term, v);
310 return ast_expr_sub(expr, term);
311 } else {
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)
322 isl_ctx *ctx;
323 isl_ast_expr *expr_int;
325 if (!expr || !v)
326 goto error;
328 if (isl_val_is_zero(v)) {
329 isl_val_free(v);
330 return expr;
333 ctx = isl_ast_expr_get_ctx(expr);
334 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
335 v = isl_val_neg(v);
336 expr_int = isl_ast_expr_from_val(v);
337 return ast_expr_sub(expr, expr_int);
338 } else {
339 expr_int = isl_ast_expr_from_val(v);
340 return ast_expr_add(expr, expr_int);
342 error:
343 isl_ast_expr_free(expr);
344 isl_val_free(v);
345 return NULL;
348 /* Internal data structure used inside extract_modulos.
350 * If any modulo expressions are detected in "aff", then the
351 * expression is removed from "aff" and added to either "pos" or "neg"
352 * depending on the sign of the coefficient of the modulo expression
353 * inside "aff".
355 * "add" is an expression that needs to be added to "aff" at the end of
356 * the computation. It is NULL as long as no modulos have been extracted.
358 * "i" is the position in "aff" of the div under investigation
359 * "v" is the coefficient in "aff" of the div
360 * "div" is the argument of the div, with the denominator removed
361 * "d" is the original denominator of the argument of the div
363 * "nonneg" is an affine expression that is non-negative over "build"
364 * and that can be used to extract a modulo expression from "div".
365 * In particular, if "sign" is 1, then the coefficients of "nonneg"
366 * are equal to those of "div" modulo "d". If "sign" is -1, then
367 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
368 * If "sign" is 0, then no such affine expression has been found (yet).
370 struct isl_extract_mod_data {
371 isl_ast_build *build;
372 isl_aff *aff;
374 isl_ast_expr *pos;
375 isl_ast_expr *neg;
377 isl_aff *add;
379 int i;
380 isl_val *v;
381 isl_val *d;
382 isl_aff *div;
384 isl_aff *nonneg;
385 int sign;
388 /* Given that data->v * div_i in data->aff is equal to
390 * f * (term - (arg mod d))
392 * with data->d * f = data->v, add
394 * f * term
396 * to data->add and
398 * abs(f) * (arg mod d)
400 * to data->neg or data->pos depending on the sign of -f.
402 static int extract_term_and_mod(struct isl_extract_mod_data *data,
403 __isl_take isl_aff *term, __isl_take isl_aff *arg)
405 isl_ast_expr *expr;
406 int s;
408 data->v = isl_val_div(data->v, isl_val_copy(data->d));
409 s = isl_val_sgn(data->v);
410 data->v = isl_val_abs(data->v);
411 expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
412 isl_aff_free(arg);
413 if (s > 0)
414 data->neg = ast_expr_add(data->neg, expr);
415 else
416 data->pos = ast_expr_add(data->pos, expr);
417 data->aff = isl_aff_set_coefficient_si(data->aff,
418 isl_dim_div, data->i, 0);
419 if (s < 0)
420 data->v = isl_val_neg(data->v);
421 term = isl_aff_scale_val(data->div, isl_val_copy(data->v));
423 if (!data->add)
424 data->add = term;
425 else
426 data->add = isl_aff_add(data->add, term);
427 if (!data->add)
428 return -1;
430 return 0;
433 /* Given that data->v * div_i in data->aff is of the form
435 * f * d * floor(div/d)
437 * with div nonnegative on data->build, rewrite it as
439 * f * (div - (div mod d)) = f * div - f * (div mod d)
441 * and add
443 * f * div
445 * to data->add and
447 * abs(f) * (div mod d)
449 * to data->neg or data->pos depending on the sign of -f.
451 static int extract_mod(struct isl_extract_mod_data *data)
453 return extract_term_and_mod(data, isl_aff_copy(data->div),
454 isl_aff_copy(data->div));
457 /* Given that data->v * div_i in data->aff is of the form
459 * f * d * floor(div/d) (1)
461 * check if div is non-negative on data->build and, if so,
462 * extract the corresponding modulo from data->aff.
463 * If not, then check if
465 * -div + d - 1
467 * is non-negative on data->build. If so, replace (1) by
469 * -f * d * floor((-div + d - 1)/d)
471 * and extract the corresponding modulo from data->aff.
473 * This function may modify data->div.
475 static int extract_nonneg_mod(struct isl_extract_mod_data *data)
477 int mod;
479 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
480 if (mod < 0)
481 goto error;
482 if (mod)
483 return extract_mod(data);
485 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
486 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
487 if (mod < 0)
488 goto error;
489 if (mod) {
490 data->v = isl_val_neg(data->v);
491 return extract_mod(data);
494 return 0;
495 error:
496 data->aff = isl_aff_free(data->aff);
497 return -1;
500 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
501 * for use in extracting a modulo expression?
503 * We currently only consider the constant term of the affine expression.
504 * In particular, we prefer the affine expression with the smallest constant
505 * term.
506 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
507 * then we would pick x >= 0
509 * More detailed heuristics could be used if it turns out that there is a need.
511 static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
512 __isl_keep isl_constraint *c)
514 isl_val *v1, *v2;
515 int simpler;
517 if (!data->nonneg)
518 return 1;
520 v1 = isl_val_abs(isl_constraint_get_constant_val(c));
521 v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
522 simpler = isl_val_lt(v1, v2);
523 isl_val_free(v1);
524 isl_val_free(v2);
526 return simpler;
529 /* Check if the coefficients of "c" are either equal or opposite to those
530 * of data->div modulo data->d. If so, and if "c" is "simpler" than
531 * data->nonneg, then replace data->nonneg by the affine expression of "c"
532 * and set data->sign accordingly.
534 * Both "c" and data->div are assumed not to involve any integer divisions.
536 * Before we start the actual comparison, we first quickly check if
537 * "c" and data->div have the same non-zero coefficients.
538 * If not, then we assume that "c" is not of the desired form.
539 * Note that while the coefficients of data->div can be reasonably expected
540 * not to involve any coefficients that are multiples of d, "c" may
541 * very well involve such coefficients. This means that we may actually
542 * miss some cases.
544 static int check_parallel_or_opposite(__isl_take isl_constraint *c, void *user)
546 struct isl_extract_mod_data *data = user;
547 enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
548 enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
549 int i, t;
550 int n[2];
551 int parallel = 1, opposite = 1;
553 for (t = 0; t < 2; ++t) {
554 n[t] = isl_constraint_dim(c, c_type[t]);
555 for (i = 0; i < n[t]; ++i) {
556 int a, b;
558 a = isl_constraint_involves_dims(c, c_type[t], i, 1);
559 b = isl_aff_involves_dims(data->div, a_type[t], i, 1);
560 if (a != b)
561 parallel = opposite = 0;
565 for (t = 0; t < 2; ++t) {
566 for (i = 0; i < n[t]; ++i) {
567 isl_val *v1, *v2;
569 if (!parallel && !opposite)
570 break;
571 v1 = isl_constraint_get_coefficient_val(c,
572 c_type[t], i);
573 v2 = isl_aff_get_coefficient_val(data->div,
574 a_type[t], i);
575 if (parallel) {
576 v1 = isl_val_sub(v1, isl_val_copy(v2));
577 parallel = isl_val_is_divisible_by(v1, data->d);
578 v1 = isl_val_add(v1, isl_val_copy(v2));
580 if (opposite) {
581 v1 = isl_val_add(v1, isl_val_copy(v2));
582 opposite = isl_val_is_divisible_by(v1, data->d);
584 isl_val_free(v1);
585 isl_val_free(v2);
589 if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {
590 isl_aff_free(data->nonneg);
591 data->nonneg = isl_constraint_get_aff(c);
592 data->sign = parallel ? 1 : -1;
595 isl_constraint_free(c);
597 if (data->sign != 0 && data->nonneg == NULL)
598 return -1;
600 return 0;
603 /* Given that data->v * div_i in data->aff is of the form
605 * f * d * floor(div/d) (1)
607 * see if we can find an expression div' that is non-negative over data->build
608 * and that is related to div through
610 * div' = div + d * e
612 * or
614 * div' = -div + d - 1 + d * e
616 * with e some affine expression.
617 * If so, we write (1) as
619 * f * div + f * (div' mod d)
621 * or
623 * -f * (-div + d - 1) - f * (div' mod d)
625 * exploiting (in the second case) the fact that
627 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
630 * We first try to find an appropriate expression for div'
631 * from the constraints of data->build->domain (which is therefore
632 * guaranteed to be non-negative on data->build), where we remove
633 * any integer divisions from the constraints and skip this step
634 * if "div" itself involves any integer divisions.
635 * If we cannot find an appropriate expression this way, then
636 * we pass control to extract_nonneg_mod where check
637 * if div or "-div + d -1" themselves happen to be
638 * non-negative on data->build.
640 * While looking for an appropriate constraint in data->build->domain,
641 * we ignore the constant term, so after finding such a constraint,
642 * we still need to fix up the constant term.
643 * In particular, if a is the constant term of "div"
644 * (or d - 1 - the constant term of "div" if data->sign < 0)
645 * and b is the constant term of the constraint, then we need to find
646 * a non-negative constant c such that
648 * b + c \equiv a mod d
650 * We therefore take
652 * c = (a - b) mod d
654 * and add it to b to obtain the constant term of div'.
655 * If this constant term is "too negative", then we add an appropriate
656 * multiple of d to make it positive.
659 * Note that the above is a only a very simple heuristic for find an
660 * appropriate expression. We could try a bit harder by also considering
661 * sums of constraints that involve disjoint sets of variables or
662 * we could consider arbitrary linear combinations of constraints,
663 * although that could potentially be much more expensive as it involves
664 * the solution of an LP problem.
666 * In particular, if v_i is a column vector representing constraint i,
667 * w represents div and e_i is the i-th unit vector, then we are looking
668 * for a solution of the constraints
670 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
672 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
673 * If we are not just interested in a non-negative expression, but
674 * also in one with a minimal range, then we don't just want
675 * c = \sum_i lambda_i v_i to be non-negative over the domain,
676 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
677 * that we want to minimize and we now also have to take into account
678 * the constant terms of the constraints.
679 * Alternatively, we could first compute the dual of the domain
680 * and plug in the constraints on the coefficients.
682 static int try_extract_mod(struct isl_extract_mod_data *data)
684 isl_basic_set *hull;
685 isl_val *v1, *v2;
686 int r;
688 if (!data->build)
689 goto error;
691 int n = isl_aff_dim(data->div, isl_dim_div);
693 if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
694 return extract_nonneg_mod(data);
696 hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
697 hull = isl_basic_set_remove_divs(hull);
698 data->sign = 0;
699 data->nonneg = NULL;
700 r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
701 data);
702 isl_basic_set_free(hull);
704 if (!data->sign || r < 0) {
705 isl_aff_free(data->nonneg);
706 if (r < 0)
707 goto error;
708 return extract_nonneg_mod(data);
711 v1 = isl_aff_get_constant_val(data->div);
712 v2 = isl_aff_get_constant_val(data->nonneg);
713 if (data->sign < 0) {
714 v1 = isl_val_neg(v1);
715 v1 = isl_val_add(v1, isl_val_copy(data->d));
716 v1 = isl_val_sub_ui(v1, 1);
718 v1 = isl_val_sub(v1, isl_val_copy(v2));
719 v1 = isl_val_mod(v1, isl_val_copy(data->d));
720 v1 = isl_val_add(v1, v2);
721 v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
722 v2 = isl_val_ceil(v2);
723 if (isl_val_is_neg(v2)) {
724 v2 = isl_val_mul(v2, isl_val_copy(data->d));
725 v1 = isl_val_sub(v1, isl_val_copy(v2));
727 data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
728 isl_val_free(v2);
730 if (data->sign < 0) {
731 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
732 data->v = isl_val_neg(data->v);
735 return extract_term_and_mod(data,
736 isl_aff_copy(data->div), data->nonneg);
737 error:
738 data->aff = isl_aff_free(data->aff);
739 return -1;
742 /* Check if "data->aff" involves any (implicit) modulo computations based
743 * on div "data->i".
744 * If so, remove them from aff and add expressions corresponding
745 * to those modulo computations to data->pos and/or data->neg.
747 * "aff" is assumed to be an integer affine expression.
749 * In particular, check if (v * div_j) is of the form
751 * f * m * floor(a / m)
753 * and, if so, rewrite it as
755 * f * (a - (a mod m)) = f * a - f * (a mod m)
757 * and extract out -f * (a mod m).
758 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
759 * If f < 0, we add ((-f) * (a mod m)) to *pos.
761 * Note that in order to represent "a mod m" as
763 * (isl_ast_op_pdiv_r, a, m)
765 * we need to make sure that a is non-negative.
766 * If not, we check if "-a + m - 1" is non-negative.
767 * If so, we can rewrite
769 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
771 * and still extract a modulo.
773 static int extract_modulo(struct isl_extract_mod_data *data)
775 data->div = isl_aff_get_div(data->aff, data->i);
776 data->d = isl_aff_get_denominator_val(data->div);
777 if (isl_val_is_divisible_by(data->v, data->d)) {
778 data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
779 if (try_extract_mod(data) < 0)
780 data->aff = isl_aff_free(data->aff);
782 isl_aff_free(data->div);
783 isl_val_free(data->d);
784 return 0;
787 /* Check if "aff" involves any (implicit) modulo computations.
788 * If so, remove them from aff and add expressions corresponding
789 * to those modulo computations to *pos and/or *neg.
790 * We only do this if the option ast_build_prefer_pdiv is set.
792 * "aff" is assumed to be an integer affine expression.
794 * A modulo expression is of the form
796 * a mod m = a - m * floor(a / m)
798 * To detect them in aff, we look for terms of the form
800 * f * m * floor(a / m)
802 * rewrite them as
804 * f * (a - (a mod m)) = f * a - f * (a mod m)
806 * and extract out -f * (a mod m).
807 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
808 * If f < 0, we add ((-f) * (a mod m)) to *pos.
810 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
811 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
812 __isl_keep isl_ast_build *build)
814 struct isl_extract_mod_data data = { build, aff, *pos, *neg };
815 isl_ctx *ctx;
816 int n;
818 if (!aff)
819 return NULL;
821 ctx = isl_aff_get_ctx(aff);
822 if (!isl_options_get_ast_build_prefer_pdiv(ctx))
823 return aff;
825 n = isl_aff_dim(data.aff, isl_dim_div);
826 for (data.i = 0; data.i < n; ++data.i) {
827 data.v = isl_aff_get_coefficient_val(data.aff,
828 isl_dim_div, data.i);
829 if (!data.v)
830 return isl_aff_free(aff);
831 if (isl_val_is_zero(data.v) ||
832 isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {
833 isl_val_free(data.v);
834 continue;
836 if (extract_modulo(&data) < 0)
837 data.aff = isl_aff_free(data.aff);
838 isl_val_free(data.v);
839 if (!data.aff)
840 break;
843 if (data.add)
844 data.aff = isl_aff_add(data.aff, data.add);
846 *pos = data.pos;
847 *neg = data.neg;
848 return data.aff;
851 /* Check if aff involves any non-integer coefficients.
852 * If so, split aff into
854 * aff = aff1 + (aff2 / d)
856 * with both aff1 and aff2 having only integer coefficients.
857 * Return aff1 and add (aff2 / d) to *expr.
859 static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
860 __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
862 int i, j, n;
863 isl_aff *rat = NULL;
864 isl_local_space *ls = NULL;
865 isl_ast_expr *rat_expr;
866 isl_val *v, *d;
867 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
868 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
870 if (!aff)
871 return NULL;
872 d = isl_aff_get_denominator_val(aff);
873 if (!d)
874 goto error;
875 if (isl_val_is_one(d)) {
876 isl_val_free(d);
877 return aff;
880 aff = isl_aff_scale_val(aff, isl_val_copy(d));
882 ls = isl_aff_get_domain_local_space(aff);
883 rat = isl_aff_zero_on_domain(isl_local_space_copy(ls));
885 for (i = 0; i < 3; ++i) {
886 n = isl_aff_dim(aff, t[i]);
887 for (j = 0; j < n; ++j) {
888 isl_aff *rat_j;
890 v = isl_aff_get_coefficient_val(aff, t[i], j);
891 if (!v)
892 goto error;
893 if (isl_val_is_divisible_by(v, d)) {
894 isl_val_free(v);
895 continue;
897 rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls),
898 l[i], j);
899 rat_j = isl_aff_scale_val(rat_j, v);
900 rat = isl_aff_add(rat, rat_j);
904 v = isl_aff_get_constant_val(aff);
905 if (isl_val_is_divisible_by(v, d)) {
906 isl_val_free(v);
907 } else {
908 isl_aff *rat_0;
910 rat_0 = isl_aff_val_on_domain(isl_local_space_copy(ls), v);
911 rat = isl_aff_add(rat, rat_0);
914 isl_local_space_free(ls);
916 aff = isl_aff_sub(aff, isl_aff_copy(rat));
917 aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
919 rat_expr = isl_ast_expr_from_aff(rat, build);
920 rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
921 *expr = ast_expr_add(*expr, rat_expr);
923 return aff;
924 error:
925 isl_aff_free(rat);
926 isl_local_space_free(ls);
927 isl_aff_free(aff);
928 isl_val_free(d);
929 return NULL;
932 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
933 * The result is simplified in terms of build->domain.
935 * We first extract hidden modulo computations from the affine expression
936 * and then add terms for each variable with a non-zero coefficient.
937 * Finally, if the affine expression has a non-trivial denominator,
938 * we divide the resulting isl_ast_expr by this denominator.
940 __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
941 __isl_keep isl_ast_build *build)
943 int i, j;
944 int n;
945 isl_val *v;
946 isl_ctx *ctx = isl_aff_get_ctx(aff);
947 isl_ast_expr *expr, *expr_neg;
948 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
949 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
950 isl_local_space *ls;
952 if (!aff)
953 return NULL;
955 expr = isl_ast_expr_alloc_int_si(ctx, 0);
956 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
958 aff = extract_rational(aff, &expr, build);
960 aff = extract_modulos(aff, &expr, &expr_neg, build);
961 expr = ast_expr_sub(expr, expr_neg);
963 ls = isl_aff_get_domain_local_space(aff);
965 for (i = 0; i < 3; ++i) {
966 n = isl_aff_dim(aff, t[i]);
967 for (j = 0; j < n; ++j) {
968 v = isl_aff_get_coefficient_val(aff, t[i], j);
969 if (!v)
970 expr = isl_ast_expr_free(expr);
971 if (isl_val_is_zero(v)) {
972 isl_val_free(v);
973 continue;
975 expr = isl_ast_expr_add_term(expr,
976 ls, l[i], j, v, build);
980 v = isl_aff_get_constant_val(aff);
981 expr = isl_ast_expr_add_int(expr, v);
983 isl_local_space_free(ls);
984 isl_aff_free(aff);
985 return expr;
988 /* Add terms to "expr" for each variable in "aff" with a coefficient
989 * with sign equal to "sign".
990 * The result is simplified in terms of build->domain.
992 static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
993 __isl_keep isl_aff *aff, int sign, __isl_keep isl_ast_build *build)
995 int i, j;
996 isl_val *v;
997 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
998 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
999 isl_local_space *ls;
1001 ls = isl_aff_get_domain_local_space(aff);
1003 for (i = 0; i < 3; ++i) {
1004 int n = isl_aff_dim(aff, t[i]);
1005 for (j = 0; j < n; ++j) {
1006 v = isl_aff_get_coefficient_val(aff, t[i], j);
1007 if (sign * isl_val_sgn(v) <= 0) {
1008 isl_val_free(v);
1009 continue;
1011 v = isl_val_abs(v);
1012 expr = isl_ast_expr_add_term(expr,
1013 ls, l[i], j, v, build);
1017 isl_local_space_free(ls);
1019 return expr;
1022 /* Should the constant term "v" be considered positive?
1024 * A positive constant will be added to "pos" by the caller,
1025 * while a negative constant will be added to "neg".
1026 * If either "pos" or "neg" is exactly zero, then we prefer
1027 * to add the constant "v" to that side, irrespective of the sign of "v".
1028 * This results in slightly shorter expressions and may reduce the risk
1029 * of overflows.
1031 static int constant_is_considered_positive(__isl_keep isl_val *v,
1032 __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
1034 if (ast_expr_is_zero(pos))
1035 return 1;
1036 if (ast_expr_is_zero(neg))
1037 return 0;
1038 return isl_val_is_pos(v);
1041 /* Construct an isl_ast_expr that evaluates the condition "constraint",
1042 * The result is simplified in terms of build->domain.
1044 * Let the constraint by either "a >= 0" or "a == 0".
1045 * We first extract hidden modulo computations from "a"
1046 * and then collect all the terms with a positive coefficient in cons_pos
1047 * and the terms with a negative coefficient in cons_neg.
1049 * The result is then of the form
1051 * (isl_ast_op_ge, expr(pos), expr(-neg)))
1053 * or
1055 * (isl_ast_op_eq, expr(pos), expr(-neg)))
1057 * However, if the first expression is an integer constant (and the second
1058 * is not), then we swap the two expressions. This ensures that we construct,
1059 * e.g., "i <= 5" rather than "5 >= i".
1061 * Furthermore, is there are no terms with positive coefficients (or no terms
1062 * with negative coefficients), then the constant term is added to "pos"
1063 * (or "neg"), ignoring the sign of the constant term.
1065 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1066 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1068 isl_ctx *ctx;
1069 isl_ast_expr *expr_pos;
1070 isl_ast_expr *expr_neg;
1071 isl_ast_expr *expr;
1072 isl_aff *aff;
1073 isl_val *v;
1074 int eq;
1075 enum isl_ast_op_type type;
1077 if (!constraint)
1078 return NULL;
1080 aff = isl_constraint_get_aff(constraint);
1082 ctx = isl_constraint_get_ctx(constraint);
1083 expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
1084 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1086 aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
1088 expr_pos = add_signed_terms(expr_pos, aff, 1, build);
1089 expr_neg = add_signed_terms(expr_neg, aff, -1, build);
1091 v = isl_aff_get_constant_val(aff);
1092 if (constant_is_considered_positive(v, expr_pos, expr_neg)) {
1093 expr_pos = isl_ast_expr_add_int(expr_pos, v);
1094 } else {
1095 v = isl_val_neg(v);
1096 expr_neg = isl_ast_expr_add_int(expr_neg, v);
1099 eq = isl_constraint_is_equality(constraint);
1101 if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
1102 isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
1103 type = eq ? isl_ast_op_eq : isl_ast_op_le;
1104 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
1105 } else {
1106 type = eq ? isl_ast_op_eq : isl_ast_op_ge;
1107 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
1110 isl_constraint_free(constraint);
1111 isl_aff_free(aff);
1112 return expr;
1115 struct isl_expr_from_basic_data {
1116 isl_ast_build *build;
1117 int first;
1118 isl_ast_expr *res;
1121 /* Construct an isl_ast_expr that evaluates the condition "c",
1122 * except if it is a div constraint, and add it to the data->res.
1123 * The result is simplified in terms of data->build->domain.
1125 static int expr_from_basic_set(__isl_take isl_constraint *c, void *user)
1127 struct isl_expr_from_basic_data *data = user;
1128 isl_ast_expr *expr;
1130 if (isl_constraint_is_div_constraint(c)) {
1131 isl_constraint_free(c);
1132 return 0;
1135 expr = isl_ast_expr_from_constraint(c, data->build);
1136 if (data->first)
1137 data->res = expr;
1138 else
1139 data->res = isl_ast_expr_and(data->res, expr);
1141 data->first = 0;
1143 if (!data->res)
1144 return -1;
1145 return 0;
1148 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1149 * The result is simplified in terms of build->domain.
1151 * We filter out the div constraints during printing, so we do not know
1152 * in advance how many constraints are going to be printed.
1154 * If it turns out that there was no constraint, then we contruct
1155 * the expression "1", i.e., "true".
1157 __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
1158 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1160 struct isl_expr_from_basic_data data = { build, 1, NULL };
1162 if (isl_basic_set_foreach_constraint(bset,
1163 &expr_from_basic_set, &data) < 0) {
1164 data.res = isl_ast_expr_free(data.res);
1165 } else if (data.res == NULL) {
1166 isl_ctx *ctx = isl_basic_set_get_ctx(bset);
1167 data.res = isl_ast_expr_alloc_int_si(ctx, 1);
1170 isl_basic_set_free(bset);
1171 return data.res;
1174 struct isl_expr_from_set_data {
1175 isl_ast_build *build;
1176 int first;
1177 isl_ast_expr *res;
1180 /* Construct an isl_ast_expr that evaluates the conditions defining "bset"
1181 * and add it to data->res.
1182 * The result is simplified in terms of data->build->domain.
1184 static int expr_from_set(__isl_take isl_basic_set *bset, void *user)
1186 struct isl_expr_from_set_data *data = user;
1187 isl_ast_expr *expr;
1189 expr = isl_ast_build_expr_from_basic_set(data->build, bset);
1190 if (data->first)
1191 data->res = expr;
1192 else
1193 data->res = isl_ast_expr_or(data->res, expr);
1195 data->first = 0;
1197 if (!data->res)
1198 return -1;
1199 return 0;
1202 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1203 * The result is simplified in terms of build->domain.
1205 __isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1206 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1208 struct isl_expr_from_set_data data = { build, 1, NULL };
1210 if (isl_set_foreach_basic_set(set, &expr_from_set, &data) < 0)
1211 data.res = isl_ast_expr_free(data.res);
1213 isl_set_free(set);
1214 return data.res;
1217 struct isl_from_pw_aff_data {
1218 isl_ast_build *build;
1219 int n;
1220 isl_ast_expr **next;
1221 isl_set *dom;
1224 /* This function is called during the construction of an isl_ast_expr
1225 * that evaluates an isl_pw_aff.
1226 * Adjust data->next to take into account this piece.
1228 * data->n is the number of pairs of set and aff to go.
1229 * data->dom is the domain of the entire isl_pw_aff.
1231 * If this is the last pair, then data->next is set to evaluate aff
1232 * and the domain is ignored.
1233 * Otherwise, data->next is set to a select operation that selects
1234 * an isl_ast_expr correponding to "aff" on "set" and to an expression
1235 * that will be filled in by later calls otherwise.
1237 static int ast_expr_from_pw_aff(__isl_take isl_set *set,
1238 __isl_take isl_aff *aff, void *user)
1240 struct isl_from_pw_aff_data *data = user;
1241 isl_ctx *ctx;
1243 ctx = isl_set_get_ctx(set);
1244 data->n--;
1245 if (data->n == 0) {
1246 *data->next = isl_ast_expr_from_aff(aff, data->build);
1247 isl_set_free(set);
1248 if (!*data->next)
1249 return -1;
1250 } else {
1251 isl_ast_expr *ternary, *arg;
1253 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
1254 set = isl_set_gist(set, isl_set_copy(data->dom));
1255 arg = isl_ast_build_expr_from_set(data->build, set);
1256 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
1257 arg = isl_ast_expr_from_aff(aff, data->build);
1258 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
1259 if (!ternary)
1260 return -1;
1262 *data->next = ternary;
1263 data->next = &ternary->u.op.args[2];
1266 return 0;
1269 /* Construct an isl_ast_expr that evaluates "pa".
1270 * The result is simplified in terms of build->domain.
1272 * The domain of "pa" lives in the internal schedule space.
1274 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
1275 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1277 struct isl_from_pw_aff_data data;
1278 isl_ast_expr *res = NULL;
1280 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
1281 pa = isl_pw_aff_coalesce(pa);
1282 if (!pa)
1283 return NULL;
1285 data.build = build;
1286 data.n = isl_pw_aff_n_piece(pa);
1287 data.next = &res;
1288 data.dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1290 if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0)
1291 res = isl_ast_expr_free(res);
1292 else if (!res)
1293 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
1294 "cannot handle void expression", res = NULL);
1296 isl_pw_aff_free(pa);
1297 isl_set_free(data.dom);
1298 return res;
1301 /* Construct an isl_ast_expr that evaluates "pa".
1302 * The result is simplified in terms of build->domain.
1304 * The domain of "pa" lives in the external schedule space.
1306 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
1307 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1309 isl_ast_expr *expr;
1311 if (isl_ast_build_need_schedule_map(build)) {
1312 isl_multi_aff *ma;
1313 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1314 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
1316 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
1317 return expr;
1320 /* Set the ids of the input dimensions of "mpa" to the iterator ids
1321 * of "build".
1323 * The domain of "mpa" is assumed to live in the internal schedule domain.
1325 static __isl_give isl_multi_pw_aff *set_iterator_names(
1326 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1328 int i, n;
1330 n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
1331 for (i = 0; i < n; ++i) {
1332 isl_id *id;
1334 id = isl_ast_build_get_iterator_id(build, i);
1335 mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
1338 return mpa;
1341 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
1342 * the remaining arguments derived from "mpa".
1343 * That is, construct a call or access expression that calls/accesses "arg0"
1344 * with arguments/indices specified by "mpa".
1346 static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
1347 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1348 __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
1350 int i, n;
1351 isl_ctx *ctx;
1352 isl_ast_expr *expr;
1354 ctx = isl_ast_build_get_ctx(build);
1356 n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
1357 expr = isl_ast_expr_alloc_op(ctx, type, 1 + n);
1358 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
1359 for (i = 0; i < n; ++i) {
1360 isl_pw_aff *pa;
1361 isl_ast_expr *arg;
1363 pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
1364 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
1365 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
1368 isl_multi_pw_aff_free(mpa);
1369 return expr;
1372 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
1373 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1374 __isl_take isl_multi_pw_aff *mpa);
1376 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
1377 * The range of "mpa" is assumed to be wrapped relation.
1378 * The domain of this wrapped relation specifies the structure being
1379 * accessed, while the range of this wrapped relation spacifies the
1380 * member of the structure being accessed.
1382 * The domain of "mpa" is assumed to live in the internal schedule domain.
1384 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
1385 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1387 isl_id *id;
1388 isl_multi_pw_aff *domain;
1389 isl_ast_expr *domain_expr, *expr;
1390 enum isl_ast_op_type type = isl_ast_op_access;
1392 domain = isl_multi_pw_aff_copy(mpa);
1393 domain = isl_multi_pw_aff_range_factor_domain(domain);
1394 domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
1395 type, domain);
1396 mpa = isl_multi_pw_aff_range_factor_range(mpa);
1397 if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
1398 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
1399 "missing field name", goto error);
1400 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
1401 expr = isl_ast_expr_from_id(id);
1402 expr = isl_ast_expr_alloc_binary(isl_ast_op_member, domain_expr, expr);
1403 return isl_ast_build_with_arguments(build, type, expr, mpa);
1404 error:
1405 isl_multi_pw_aff_free(mpa);
1406 return NULL;
1409 /* Construct an isl_ast_expr of type "type" that calls or accesses
1410 * the element specified by "mpa".
1411 * The first argument is obtained from the output tuple name.
1412 * The remaining arguments are given by the piecewise affine expressions.
1414 * If the range of "mpa" is a mapped relation, then we assume it
1415 * represents an access to a member of a structure.
1417 * The domain of "mpa" is assumed to live in the internal schedule domain.
1419 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
1420 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1421 __isl_take isl_multi_pw_aff *mpa)
1423 isl_ctx *ctx;
1424 isl_id *id;
1425 isl_ast_expr *expr;
1427 if (!mpa)
1428 goto error;
1430 if (type == isl_ast_op_access &&
1431 isl_multi_pw_aff_range_is_wrapping(mpa))
1432 return isl_ast_build_from_multi_pw_aff_member(build, mpa);
1434 mpa = set_iterator_names(build, mpa);
1435 if (!build || !mpa)
1436 goto error;
1438 ctx = isl_ast_build_get_ctx(build);
1440 if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
1441 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
1442 else
1443 id = isl_id_alloc(ctx, "", NULL);
1445 expr = isl_ast_expr_from_id(id);
1446 return isl_ast_build_with_arguments(build, type, expr, mpa);
1447 error:
1448 isl_multi_pw_aff_free(mpa);
1449 return NULL;
1452 /* Construct an isl_ast_expr of type "type" that calls or accesses
1453 * the element specified by "pma".
1454 * The first argument is obtained from the output tuple name.
1455 * The remaining arguments are given by the piecewise affine expressions.
1457 * The domain of "pma" is assumed to live in the internal schedule domain.
1459 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
1460 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1461 __isl_take isl_pw_multi_aff *pma)
1463 isl_multi_pw_aff *mpa;
1465 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
1466 return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
1469 /* Construct an isl_ast_expr of type "type" that calls or accesses
1470 * the element specified by "mpa".
1471 * The first argument is obtained from the output tuple name.
1472 * The remaining arguments are given by the piecewise affine expressions.
1474 * The domain of "mpa" is assumed to live in the external schedule domain.
1476 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
1477 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1478 __isl_take isl_multi_pw_aff *mpa)
1480 int is_domain;
1481 isl_ast_expr *expr;
1482 isl_space *space_build, *space_mpa;
1484 space_build = isl_ast_build_get_space(build, 0);
1485 space_mpa = isl_multi_pw_aff_get_space(mpa);
1486 is_domain = isl_space_tuple_match(space_build, isl_dim_set,
1487 space_mpa, isl_dim_in);
1488 isl_space_free(space_build);
1489 isl_space_free(space_mpa);
1490 if (is_domain < 0)
1491 goto error;
1492 if (!is_domain)
1493 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
1494 "spaces don't match", goto error);
1496 if (isl_ast_build_need_schedule_map(build)) {
1497 isl_multi_aff *ma;
1498 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1499 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
1502 expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
1503 return expr;
1504 error:
1505 isl_multi_pw_aff_free(mpa);
1506 return NULL;
1509 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
1510 * The name of the function is obtained from the output tuple name.
1511 * The arguments are given by the piecewise affine expressions.
1513 * The domain of "mpa" is assumed to live in the external schedule domain.
1515 __isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
1516 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1518 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_call, mpa);
1521 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
1522 * The name of the array is obtained from the output tuple name.
1523 * The index expressions are given by the piecewise affine expressions.
1525 * The domain of "mpa" is assumed to live in the external schedule domain.
1527 __isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
1528 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1530 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_access, mpa);
1533 /* Construct an isl_ast_expr of type "type" that calls or accesses
1534 * the element specified by "pma".
1535 * The first argument is obtained from the output tuple name.
1536 * The remaining arguments are given by the piecewise affine expressions.
1538 * The domain of "pma" is assumed to live in the external schedule domain.
1540 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
1541 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1542 __isl_take isl_pw_multi_aff *pma)
1544 isl_multi_pw_aff *mpa;
1546 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
1547 return isl_ast_build_from_multi_pw_aff(build, type, mpa);
1550 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
1551 * The name of the function is obtained from the output tuple name.
1552 * The arguments are given by the piecewise affine expressions.
1554 * The domain of "pma" is assumed to live in the external schedule domain.
1556 __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
1557 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1559 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_call, pma);
1562 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
1563 * The name of the array is obtained from the output tuple name.
1564 * The index expressions are given by the piecewise affine expressions.
1566 * The domain of "pma" is assumed to live in the external schedule domain.
1568 __isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
1569 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1571 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma);
1574 /* Construct an isl_ast_expr that calls the domain element
1575 * specified by "executed".
1577 * "executed" is assumed to be single-valued, with a domain that lives
1578 * in the internal schedule space.
1580 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
1581 __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
1583 isl_pw_multi_aff *iteration;
1584 isl_ast_expr *expr;
1586 iteration = isl_pw_multi_aff_from_map(executed);
1587 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
1588 iteration = isl_pw_multi_aff_intersect_domain(iteration,
1589 isl_ast_build_get_domain(build));
1590 expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call,
1591 iteration);
1592 return isl_ast_node_alloc_user(expr);