isl_ast_build_node_from_schedule: handle basic AST build options
[isl.git] / isl_ast_build_expr.c
blob83b12a13d591b811ee66cef5bd9f8899014eb124
1 /*
2 * Copyright 2012-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
13 #include <isl/ilp.h>
14 #include <isl_ast_build_expr.h>
15 #include <isl_ast_private.h>
16 #include <isl_ast_build_private.h>
18 /* Compute the "opposite" of the (numerator of the) argument of a div
19 * with denonimator "d".
21 * In particular, compute
23 * -aff + (d - 1)
25 static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
26 __isl_take isl_val *d)
28 aff = isl_aff_neg(aff);
29 aff = isl_aff_add_constant_val(aff, d);
30 aff = isl_aff_add_constant_si(aff, -1);
32 return aff;
35 /* Internal data structure used inside isl_ast_expr_add_term.
36 * The domain of "build" is used to simplify the expressions.
37 * "build" needs to be set by the caller of isl_ast_expr_add_term.
38 * "cst" is the constant term of the expression in which the added term
39 * appears. It may be modified by isl_ast_expr_add_term.
41 * "v" is the coefficient of the term that is being constructed and
42 * is set internally by isl_ast_expr_add_term.
44 struct isl_ast_add_term_data {
45 isl_ast_build *build;
46 isl_val *cst;
47 isl_val *v;
50 /* Given the numerator "aff" of the argument of an integer division
51 * with denominator "d", check if it can be made non-negative over
52 * data->build->domain by stealing part of the constant term of
53 * the expression in which the integer division appears.
55 * In particular, the outer expression is of the form
57 * v * floor(aff/d) + cst
59 * We already know that "aff" itself may attain negative values.
60 * Here we check if aff + d*floor(cst/v) is non-negative, such
61 * that we could rewrite the expression to
63 * v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
65 * Note that aff + d*floor(cst/v) can only possibly be non-negative
66 * if data->cst and data->v have the same sign.
67 * Similarly, if floor(cst/v) is zero, then there is no point in
68 * checking again.
70 static int is_non_neg_after_stealing(__isl_keep isl_aff *aff,
71 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
73 isl_aff *shifted;
74 isl_val *shift;
75 int is_zero;
76 int non_neg;
78 if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))
79 return 0;
81 shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));
82 shift = isl_val_floor(shift);
83 is_zero = isl_val_is_zero(shift);
84 if (is_zero < 0 || is_zero) {
85 isl_val_free(shift);
86 return is_zero < 0 ? -1 : 0;
88 shift = isl_val_mul(shift, isl_val_copy(d));
89 shifted = isl_aff_copy(aff);
90 shifted = isl_aff_add_constant_val(shifted, shift);
91 non_neg = isl_ast_build_aff_is_nonneg(data->build, shifted);
92 isl_aff_free(shifted);
94 return non_neg;
97 /* Given the numerator "aff' of the argument of an integer division
98 * with denominator "d", steal part of the constant term of
99 * the expression in which the integer division appears to make it
100 * non-negative over data->build->domain.
102 * In particular, the outer expression is of the form
104 * v * floor(aff/d) + cst
106 * We know that "aff" itself may attain negative values,
107 * but that aff + d*floor(cst/v) is non-negative.
108 * Find the minimal positive value that we need to add to "aff"
109 * to make it positive and adjust data->cst accordingly.
110 * That is, compute the minimal value "m" of "aff" over
111 * data->build->domain and take
113 * s = ceil(m/d)
115 * such that
117 * aff + d * s >= 0
119 * and rewrite the expression to
121 * v * floor((aff + s*d)/d) + (cst - v*s)
123 static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
124 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
126 isl_set *domain;
127 isl_val *shift, *t;
129 domain = isl_ast_build_get_domain(data->build);
130 shift = isl_set_min_val(domain, aff);
131 isl_set_free(domain);
133 shift = isl_val_neg(shift);
134 shift = isl_val_div(shift, isl_val_copy(d));
135 shift = isl_val_ceil(shift);
137 t = isl_val_copy(shift);
138 t = isl_val_mul(t, isl_val_copy(data->v));
139 data->cst = isl_val_sub(data->cst, t);
141 shift = isl_val_mul(shift, isl_val_copy(d));
142 return isl_aff_add_constant_val(aff, shift);
145 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
146 * The result is simplified in terms of data->build->domain.
147 * This function may change (the sign of) data->v.
149 * "ls" is known to be non-NULL.
151 * Let the div be of the form floor(e/d).
152 * If the ast_build_prefer_pdiv option is set then we check if "e"
153 * is non-negative, so that we can generate
155 * (pdiv_q, expr(e), expr(d))
157 * instead of
159 * (fdiv_q, expr(e), expr(d))
161 * If the ast_build_prefer_pdiv option is set and
162 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
163 * If so, we can rewrite
165 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
167 * and still use pdiv_q, while changing the sign of data->v.
169 * Otherwise, we check if
171 * e + d*floor(cst/v)
173 * is non-negative and if so, replace floor(e/d) by
175 * floor((e + s*d)/d) - s
177 * with s the minimal shift that makes the argument non-negative.
179 static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,
180 __isl_keep isl_local_space *ls, int pos)
182 isl_ctx *ctx = isl_local_space_get_ctx(ls);
183 isl_aff *aff;
184 isl_ast_expr *num, *den;
185 isl_val *d;
186 enum isl_ast_op_type type;
188 aff = isl_local_space_get_div(ls, pos);
189 d = isl_aff_get_denominator_val(aff);
190 aff = isl_aff_scale_val(aff, isl_val_copy(d));
191 den = isl_ast_expr_from_val(isl_val_copy(d));
193 type = isl_ast_op_fdiv_q;
194 if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
195 int non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);
196 if (non_neg >= 0 && !non_neg) {
197 isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),
198 isl_val_copy(d));
199 non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);
200 if (non_neg >= 0 && non_neg) {
201 data->v = isl_val_neg(data->v);
202 isl_aff_free(aff);
203 aff = opp;
204 } else
205 isl_aff_free(opp);
207 if (non_neg >= 0 && !non_neg) {
208 non_neg = is_non_neg_after_stealing(aff, d, data);
209 if (non_neg >= 0 && non_neg)
210 aff = steal_from_cst(aff, d, data);
212 if (non_neg < 0)
213 aff = isl_aff_free(aff);
214 else if (non_neg)
215 type = isl_ast_op_pdiv_q;
218 isl_val_free(d);
219 num = isl_ast_expr_from_aff(aff, data->build);
220 return isl_ast_expr_alloc_binary(type, num, den);
223 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
224 * The result is simplified in terms of data->build->domain.
225 * This function may change (the sign of) data->v.
227 * The isl_ast_expr is constructed based on the type of the dimension.
228 * - divs are constructed by var_div
229 * - set variables are constructed from the iterator isl_ids in data->build
230 * - parameters are constructed from the isl_ids in "ls"
232 static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
233 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos)
235 isl_ctx *ctx = isl_local_space_get_ctx(ls);
236 isl_id *id;
238 if (type == isl_dim_div)
239 return var_div(data, ls, pos);
241 if (type == isl_dim_set) {
242 id = isl_ast_build_get_iterator_id(data->build, pos);
243 return isl_ast_expr_from_id(id);
246 if (!isl_local_space_has_dim_id(ls, type, pos))
247 isl_die(ctx, isl_error_internal, "unnamed dimension",
248 return NULL);
249 id = isl_local_space_get_dim_id(ls, type, pos);
250 return isl_ast_expr_from_id(id);
253 /* Does "expr" represent the zero integer?
255 static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
257 if (!expr)
258 return -1;
259 if (expr->type != isl_ast_expr_int)
260 return 0;
261 return isl_val_is_zero(expr->u.v);
264 /* Create an expression representing the sum of "expr1" and "expr2",
265 * provided neither of the two expressions is identically zero.
267 static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
268 __isl_take isl_ast_expr *expr2)
270 if (!expr1 || !expr2)
271 goto error;
273 if (ast_expr_is_zero(expr1)) {
274 isl_ast_expr_free(expr1);
275 return expr2;
278 if (ast_expr_is_zero(expr2)) {
279 isl_ast_expr_free(expr2);
280 return expr1;
283 return isl_ast_expr_add(expr1, expr2);
284 error:
285 isl_ast_expr_free(expr1);
286 isl_ast_expr_free(expr2);
287 return NULL;
290 /* Subtract expr2 from expr1.
292 * If expr2 is zero, we simply return expr1.
293 * If expr1 is zero, we return
295 * (isl_ast_op_minus, expr2)
297 * Otherwise, we return
299 * (isl_ast_op_sub, expr1, expr2)
301 static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
302 __isl_take isl_ast_expr *expr2)
304 if (!expr1 || !expr2)
305 goto error;
307 if (ast_expr_is_zero(expr2)) {
308 isl_ast_expr_free(expr2);
309 return expr1;
312 if (ast_expr_is_zero(expr1)) {
313 isl_ast_expr_free(expr1);
314 return isl_ast_expr_neg(expr2);
317 return isl_ast_expr_sub(expr1, expr2);
318 error:
319 isl_ast_expr_free(expr1);
320 isl_ast_expr_free(expr2);
321 return NULL;
324 /* Return an isl_ast_expr that represents
326 * v * (aff mod d)
328 * v is assumed to be non-negative.
329 * The result is simplified in terms of build->domain.
331 static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
332 __isl_keep isl_aff *aff, __isl_keep isl_val *d,
333 __isl_keep isl_ast_build *build)
335 isl_ast_expr *expr;
336 isl_ast_expr *c;
338 if (!aff)
339 return NULL;
341 expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
343 c = isl_ast_expr_from_val(isl_val_copy(d));
344 expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
346 if (!isl_val_is_one(v)) {
347 c = isl_ast_expr_from_val(isl_val_copy(v));
348 expr = isl_ast_expr_mul(c, expr);
351 return expr;
354 /* Create an isl_ast_expr that scales "expr" by "v".
356 * If v is 1, we simply return expr.
357 * If v is -1, we return
359 * (isl_ast_op_minus, expr)
361 * Otherwise, we return
363 * (isl_ast_op_mul, expr(v), expr)
365 static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
366 __isl_take isl_val *v)
368 isl_ast_expr *c;
370 if (!expr || !v)
371 goto error;
372 if (isl_val_is_one(v)) {
373 isl_val_free(v);
374 return expr;
377 if (isl_val_is_negone(v)) {
378 isl_val_free(v);
379 expr = isl_ast_expr_neg(expr);
380 } else {
381 c = isl_ast_expr_from_val(v);
382 expr = isl_ast_expr_mul(c, expr);
385 return expr;
386 error:
387 isl_val_free(v);
388 isl_ast_expr_free(expr);
389 return NULL;
392 /* Add an expression for "*v" times the specified dimension of "ls"
393 * to expr.
394 * If the dimension is an integer division, then this function
395 * may modify data->cst in order to make the numerator non-negative.
396 * The result is simplified in terms of data->build->domain.
398 * Let e be the expression for the specified dimension,
399 * multiplied by the absolute value of "*v".
400 * If "*v" is negative, we create
402 * (isl_ast_op_sub, expr, e)
404 * except when expr is trivially zero, in which case we create
406 * (isl_ast_op_minus, e)
408 * instead.
410 * If "*v" is positive, we simply create
412 * (isl_ast_op_add, expr, e)
415 static __isl_give isl_ast_expr *isl_ast_expr_add_term(
416 __isl_take isl_ast_expr *expr,
417 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
418 __isl_take isl_val *v, struct isl_ast_add_term_data *data)
420 isl_ast_expr *term;
422 if (!expr)
423 return NULL;
425 data->v = v;
426 term = var(data, ls, type, pos);
427 v = data->v;
429 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
430 v = isl_val_neg(v);
431 term = scale(term, v);
432 return ast_expr_sub(expr, term);
433 } else {
434 term = scale(term, v);
435 return ast_expr_add(expr, term);
439 /* Add an expression for "v" to expr.
441 static __isl_give isl_ast_expr *isl_ast_expr_add_int(
442 __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
444 isl_ast_expr *expr_int;
446 if (!expr || !v)
447 goto error;
449 if (isl_val_is_zero(v)) {
450 isl_val_free(v);
451 return expr;
454 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
455 v = isl_val_neg(v);
456 expr_int = isl_ast_expr_from_val(v);
457 return ast_expr_sub(expr, expr_int);
458 } else {
459 expr_int = isl_ast_expr_from_val(v);
460 return ast_expr_add(expr, expr_int);
462 error:
463 isl_ast_expr_free(expr);
464 isl_val_free(v);
465 return NULL;
468 /* Internal data structure used inside extract_modulos.
470 * If any modulo expressions are detected in "aff", then the
471 * expression is removed from "aff" and added to either "pos" or "neg"
472 * depending on the sign of the coefficient of the modulo expression
473 * inside "aff".
475 * "add" is an expression that needs to be added to "aff" at the end of
476 * the computation. It is NULL as long as no modulos have been extracted.
478 * "i" is the position in "aff" of the div under investigation
479 * "v" is the coefficient in "aff" of the div
480 * "div" is the argument of the div, with the denominator removed
481 * "d" is the original denominator of the argument of the div
483 * "nonneg" is an affine expression that is non-negative over "build"
484 * and that can be used to extract a modulo expression from "div".
485 * In particular, if "sign" is 1, then the coefficients of "nonneg"
486 * are equal to those of "div" modulo "d". If "sign" is -1, then
487 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
488 * If "sign" is 0, then no such affine expression has been found (yet).
490 struct isl_extract_mod_data {
491 isl_ast_build *build;
492 isl_aff *aff;
494 isl_ast_expr *pos;
495 isl_ast_expr *neg;
497 isl_aff *add;
499 int i;
500 isl_val *v;
501 isl_val *d;
502 isl_aff *div;
504 isl_aff *nonneg;
505 int sign;
508 /* Given that data->v * div_i in data->aff is equal to
510 * f * (term - (arg mod d))
512 * with data->d * f = data->v, add
514 * f * term
516 * to data->add and
518 * abs(f) * (arg mod d)
520 * to data->neg or data->pos depending on the sign of -f.
522 static int extract_term_and_mod(struct isl_extract_mod_data *data,
523 __isl_take isl_aff *term, __isl_take isl_aff *arg)
525 isl_ast_expr *expr;
526 int s;
528 data->v = isl_val_div(data->v, isl_val_copy(data->d));
529 s = isl_val_sgn(data->v);
530 data->v = isl_val_abs(data->v);
531 expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
532 isl_aff_free(arg);
533 if (s > 0)
534 data->neg = ast_expr_add(data->neg, expr);
535 else
536 data->pos = ast_expr_add(data->pos, expr);
537 data->aff = isl_aff_set_coefficient_si(data->aff,
538 isl_dim_div, data->i, 0);
539 if (s < 0)
540 data->v = isl_val_neg(data->v);
541 term = isl_aff_scale_val(data->div, isl_val_copy(data->v));
543 if (!data->add)
544 data->add = term;
545 else
546 data->add = isl_aff_add(data->add, term);
547 if (!data->add)
548 return -1;
550 return 0;
553 /* Given that data->v * div_i in data->aff is of the form
555 * f * d * floor(div/d)
557 * with div nonnegative on data->build, rewrite it as
559 * f * (div - (div mod d)) = f * div - f * (div mod d)
561 * and add
563 * f * div
565 * to data->add and
567 * abs(f) * (div mod d)
569 * to data->neg or data->pos depending on the sign of -f.
571 static int extract_mod(struct isl_extract_mod_data *data)
573 return extract_term_and_mod(data, isl_aff_copy(data->div),
574 isl_aff_copy(data->div));
577 /* Given that data->v * div_i in data->aff is of the form
579 * f * d * floor(div/d) (1)
581 * check if div is non-negative on data->build and, if so,
582 * extract the corresponding modulo from data->aff.
583 * If not, then check if
585 * -div + d - 1
587 * is non-negative on data->build. If so, replace (1) by
589 * -f * d * floor((-div + d - 1)/d)
591 * and extract the corresponding modulo from data->aff.
593 * This function may modify data->div.
595 static int extract_nonneg_mod(struct isl_extract_mod_data *data)
597 int mod;
599 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
600 if (mod < 0)
601 goto error;
602 if (mod)
603 return extract_mod(data);
605 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
606 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
607 if (mod < 0)
608 goto error;
609 if (mod) {
610 data->v = isl_val_neg(data->v);
611 return extract_mod(data);
614 return 0;
615 error:
616 data->aff = isl_aff_free(data->aff);
617 return -1;
620 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
621 * for use in extracting a modulo expression?
623 * We currently only consider the constant term of the affine expression.
624 * In particular, we prefer the affine expression with the smallest constant
625 * term.
626 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
627 * then we would pick x >= 0
629 * More detailed heuristics could be used if it turns out that there is a need.
631 static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
632 __isl_keep isl_constraint *c)
634 isl_val *v1, *v2;
635 int simpler;
637 if (!data->nonneg)
638 return 1;
640 v1 = isl_val_abs(isl_constraint_get_constant_val(c));
641 v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
642 simpler = isl_val_lt(v1, v2);
643 isl_val_free(v1);
644 isl_val_free(v2);
646 return simpler;
649 /* Check if the coefficients of "c" are either equal or opposite to those
650 * of data->div modulo data->d. If so, and if "c" is "simpler" than
651 * data->nonneg, then replace data->nonneg by the affine expression of "c"
652 * and set data->sign accordingly.
654 * Both "c" and data->div are assumed not to involve any integer divisions.
656 * Before we start the actual comparison, we first quickly check if
657 * "c" and data->div have the same non-zero coefficients.
658 * If not, then we assume that "c" is not of the desired form.
659 * Note that while the coefficients of data->div can be reasonably expected
660 * not to involve any coefficients that are multiples of d, "c" may
661 * very well involve such coefficients. This means that we may actually
662 * miss some cases.
664 static int check_parallel_or_opposite(__isl_take isl_constraint *c, void *user)
666 struct isl_extract_mod_data *data = user;
667 enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
668 enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
669 int i, t;
670 int n[2];
671 int parallel = 1, opposite = 1;
673 for (t = 0; t < 2; ++t) {
674 n[t] = isl_constraint_dim(c, c_type[t]);
675 for (i = 0; i < n[t]; ++i) {
676 int a, b;
678 a = isl_constraint_involves_dims(c, c_type[t], i, 1);
679 b = isl_aff_involves_dims(data->div, a_type[t], i, 1);
680 if (a != b)
681 parallel = opposite = 0;
685 for (t = 0; t < 2; ++t) {
686 for (i = 0; i < n[t]; ++i) {
687 isl_val *v1, *v2;
689 if (!parallel && !opposite)
690 break;
691 v1 = isl_constraint_get_coefficient_val(c,
692 c_type[t], i);
693 v2 = isl_aff_get_coefficient_val(data->div,
694 a_type[t], i);
695 if (parallel) {
696 v1 = isl_val_sub(v1, isl_val_copy(v2));
697 parallel = isl_val_is_divisible_by(v1, data->d);
698 v1 = isl_val_add(v1, isl_val_copy(v2));
700 if (opposite) {
701 v1 = isl_val_add(v1, isl_val_copy(v2));
702 opposite = isl_val_is_divisible_by(v1, data->d);
704 isl_val_free(v1);
705 isl_val_free(v2);
709 if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {
710 isl_aff_free(data->nonneg);
711 data->nonneg = isl_constraint_get_aff(c);
712 data->sign = parallel ? 1 : -1;
715 isl_constraint_free(c);
717 if (data->sign != 0 && data->nonneg == NULL)
718 return -1;
720 return 0;
723 /* Given that data->v * div_i in data->aff is of the form
725 * f * d * floor(div/d) (1)
727 * see if we can find an expression div' that is non-negative over data->build
728 * and that is related to div through
730 * div' = div + d * e
732 * or
734 * div' = -div + d - 1 + d * e
736 * with e some affine expression.
737 * If so, we write (1) as
739 * f * div + f * (div' mod d)
741 * or
743 * -f * (-div + d - 1) - f * (div' mod d)
745 * exploiting (in the second case) the fact that
747 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
750 * We first try to find an appropriate expression for div'
751 * from the constraints of data->build->domain (which is therefore
752 * guaranteed to be non-negative on data->build), where we remove
753 * any integer divisions from the constraints and skip this step
754 * if "div" itself involves any integer divisions.
755 * If we cannot find an appropriate expression this way, then
756 * we pass control to extract_nonneg_mod where check
757 * if div or "-div + d -1" themselves happen to be
758 * non-negative on data->build.
760 * While looking for an appropriate constraint in data->build->domain,
761 * we ignore the constant term, so after finding such a constraint,
762 * we still need to fix up the constant term.
763 * In particular, if a is the constant term of "div"
764 * (or d - 1 - the constant term of "div" if data->sign < 0)
765 * and b is the constant term of the constraint, then we need to find
766 * a non-negative constant c such that
768 * b + c \equiv a mod d
770 * We therefore take
772 * c = (a - b) mod d
774 * and add it to b to obtain the constant term of div'.
775 * If this constant term is "too negative", then we add an appropriate
776 * multiple of d to make it positive.
779 * Note that the above is a only a very simple heuristic for finding an
780 * appropriate expression. We could try a bit harder by also considering
781 * sums of constraints that involve disjoint sets of variables or
782 * we could consider arbitrary linear combinations of constraints,
783 * although that could potentially be much more expensive as it involves
784 * the solution of an LP problem.
786 * In particular, if v_i is a column vector representing constraint i,
787 * w represents div and e_i is the i-th unit vector, then we are looking
788 * for a solution of the constraints
790 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
792 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
793 * If we are not just interested in a non-negative expression, but
794 * also in one with a minimal range, then we don't just want
795 * c = \sum_i lambda_i v_i to be non-negative over the domain,
796 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
797 * that we want to minimize and we now also have to take into account
798 * the constant terms of the constraints.
799 * Alternatively, we could first compute the dual of the domain
800 * and plug in the constraints on the coefficients.
802 static int try_extract_mod(struct isl_extract_mod_data *data)
804 isl_basic_set *hull;
805 isl_val *v1, *v2;
806 int r, n;
808 if (!data->build)
809 goto error;
811 n = isl_aff_dim(data->div, isl_dim_div);
813 if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
814 return extract_nonneg_mod(data);
816 hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
817 hull = isl_basic_set_remove_divs(hull);
818 data->sign = 0;
819 data->nonneg = NULL;
820 r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
821 data);
822 isl_basic_set_free(hull);
824 if (!data->sign || r < 0) {
825 isl_aff_free(data->nonneg);
826 if (r < 0)
827 goto error;
828 return extract_nonneg_mod(data);
831 v1 = isl_aff_get_constant_val(data->div);
832 v2 = isl_aff_get_constant_val(data->nonneg);
833 if (data->sign < 0) {
834 v1 = isl_val_neg(v1);
835 v1 = isl_val_add(v1, isl_val_copy(data->d));
836 v1 = isl_val_sub_ui(v1, 1);
838 v1 = isl_val_sub(v1, isl_val_copy(v2));
839 v1 = isl_val_mod(v1, isl_val_copy(data->d));
840 v1 = isl_val_add(v1, v2);
841 v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
842 v2 = isl_val_ceil(v2);
843 if (isl_val_is_neg(v2)) {
844 v2 = isl_val_mul(v2, isl_val_copy(data->d));
845 v1 = isl_val_sub(v1, isl_val_copy(v2));
847 data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
848 isl_val_free(v2);
850 if (data->sign < 0) {
851 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
852 data->v = isl_val_neg(data->v);
855 return extract_term_and_mod(data,
856 isl_aff_copy(data->div), data->nonneg);
857 error:
858 data->aff = isl_aff_free(data->aff);
859 return -1;
862 /* Check if "data->aff" involves any (implicit) modulo computations based
863 * on div "data->i".
864 * If so, remove them from aff and add expressions corresponding
865 * to those modulo computations to data->pos and/or data->neg.
867 * "aff" is assumed to be an integer affine expression.
869 * In particular, check if (v * div_j) is of the form
871 * f * m * floor(a / m)
873 * and, if so, rewrite it as
875 * f * (a - (a mod m)) = f * a - f * (a mod m)
877 * and extract out -f * (a mod m).
878 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
879 * If f < 0, we add ((-f) * (a mod m)) to *pos.
881 * Note that in order to represent "a mod m" as
883 * (isl_ast_op_pdiv_r, a, m)
885 * we need to make sure that a is non-negative.
886 * If not, we check if "-a + m - 1" is non-negative.
887 * If so, we can rewrite
889 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
891 * and still extract a modulo.
893 static int extract_modulo(struct isl_extract_mod_data *data)
895 data->div = isl_aff_get_div(data->aff, data->i);
896 data->d = isl_aff_get_denominator_val(data->div);
897 if (isl_val_is_divisible_by(data->v, data->d)) {
898 data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
899 if (try_extract_mod(data) < 0)
900 data->aff = isl_aff_free(data->aff);
902 isl_aff_free(data->div);
903 isl_val_free(data->d);
904 return 0;
907 /* Check if "aff" involves any (implicit) modulo computations.
908 * If so, remove them from aff and add expressions corresponding
909 * to those modulo computations to *pos and/or *neg.
910 * We only do this if the option ast_build_prefer_pdiv is set.
912 * "aff" is assumed to be an integer affine expression.
914 * A modulo expression is of the form
916 * a mod m = a - m * floor(a / m)
918 * To detect them in aff, we look for terms of the form
920 * f * m * floor(a / m)
922 * rewrite them as
924 * f * (a - (a mod m)) = f * a - f * (a mod m)
926 * and extract out -f * (a mod m).
927 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
928 * If f < 0, we add ((-f) * (a mod m)) to *pos.
930 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
931 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
932 __isl_keep isl_ast_build *build)
934 struct isl_extract_mod_data data = { build, aff, *pos, *neg };
935 isl_ctx *ctx;
936 int n;
938 if (!aff)
939 return NULL;
941 ctx = isl_aff_get_ctx(aff);
942 if (!isl_options_get_ast_build_prefer_pdiv(ctx))
943 return aff;
945 n = isl_aff_dim(data.aff, isl_dim_div);
946 for (data.i = 0; data.i < n; ++data.i) {
947 data.v = isl_aff_get_coefficient_val(data.aff,
948 isl_dim_div, data.i);
949 if (!data.v)
950 return isl_aff_free(aff);
951 if (isl_val_is_zero(data.v) ||
952 isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {
953 isl_val_free(data.v);
954 continue;
956 if (extract_modulo(&data) < 0)
957 data.aff = isl_aff_free(data.aff);
958 isl_val_free(data.v);
959 if (!data.aff)
960 break;
963 if (data.add)
964 data.aff = isl_aff_add(data.aff, data.add);
966 *pos = data.pos;
967 *neg = data.neg;
968 return data.aff;
971 /* Check if aff involves any non-integer coefficients.
972 * If so, split aff into
974 * aff = aff1 + (aff2 / d)
976 * with both aff1 and aff2 having only integer coefficients.
977 * Return aff1 and add (aff2 / d) to *expr.
979 static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
980 __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
982 int i, j, n;
983 isl_aff *rat = NULL;
984 isl_local_space *ls = NULL;
985 isl_ast_expr *rat_expr;
986 isl_val *v, *d;
987 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
988 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
990 if (!aff)
991 return NULL;
992 d = isl_aff_get_denominator_val(aff);
993 if (!d)
994 goto error;
995 if (isl_val_is_one(d)) {
996 isl_val_free(d);
997 return aff;
1000 aff = isl_aff_scale_val(aff, isl_val_copy(d));
1002 ls = isl_aff_get_domain_local_space(aff);
1003 rat = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1005 for (i = 0; i < 3; ++i) {
1006 n = isl_aff_dim(aff, t[i]);
1007 for (j = 0; j < n; ++j) {
1008 isl_aff *rat_j;
1010 v = isl_aff_get_coefficient_val(aff, t[i], j);
1011 if (!v)
1012 goto error;
1013 if (isl_val_is_divisible_by(v, d)) {
1014 isl_val_free(v);
1015 continue;
1017 rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls),
1018 l[i], j);
1019 rat_j = isl_aff_scale_val(rat_j, v);
1020 rat = isl_aff_add(rat, rat_j);
1024 v = isl_aff_get_constant_val(aff);
1025 if (isl_val_is_divisible_by(v, d)) {
1026 isl_val_free(v);
1027 } else {
1028 isl_aff *rat_0;
1030 rat_0 = isl_aff_val_on_domain(isl_local_space_copy(ls), v);
1031 rat = isl_aff_add(rat, rat_0);
1034 isl_local_space_free(ls);
1036 aff = isl_aff_sub(aff, isl_aff_copy(rat));
1037 aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
1039 rat_expr = isl_ast_expr_from_aff(rat, build);
1040 rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
1041 *expr = ast_expr_add(*expr, rat_expr);
1043 return aff;
1044 error:
1045 isl_aff_free(rat);
1046 isl_local_space_free(ls);
1047 isl_aff_free(aff);
1048 isl_val_free(d);
1049 return NULL;
1052 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
1053 * The result is simplified in terms of build->domain.
1055 * We first extract hidden modulo computations from the affine expression
1056 * and then add terms for each variable with a non-zero coefficient.
1057 * Finally, if the affine expression has a non-trivial denominator,
1058 * we divide the resulting isl_ast_expr by this denominator.
1060 __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
1061 __isl_keep isl_ast_build *build)
1063 int i, j;
1064 int n;
1065 isl_val *v;
1066 isl_ctx *ctx = isl_aff_get_ctx(aff);
1067 isl_ast_expr *expr, *expr_neg;
1068 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1069 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1070 isl_local_space *ls;
1071 struct isl_ast_add_term_data data;
1073 if (!aff)
1074 return NULL;
1076 expr = isl_ast_expr_alloc_int_si(ctx, 0);
1077 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1079 aff = extract_rational(aff, &expr, build);
1081 aff = extract_modulos(aff, &expr, &expr_neg, build);
1082 expr = ast_expr_sub(expr, expr_neg);
1084 ls = isl_aff_get_domain_local_space(aff);
1086 data.build = build;
1087 data.cst = isl_aff_get_constant_val(aff);
1088 for (i = 0; i < 3; ++i) {
1089 n = isl_aff_dim(aff, t[i]);
1090 for (j = 0; j < n; ++j) {
1091 v = isl_aff_get_coefficient_val(aff, t[i], j);
1092 if (!v)
1093 expr = isl_ast_expr_free(expr);
1094 if (isl_val_is_zero(v)) {
1095 isl_val_free(v);
1096 continue;
1098 expr = isl_ast_expr_add_term(expr,
1099 ls, l[i], j, v, &data);
1103 expr = isl_ast_expr_add_int(expr, data.cst);
1105 isl_local_space_free(ls);
1106 isl_aff_free(aff);
1107 return expr;
1110 /* Add terms to "expr" for each variable in "aff" with a coefficient
1111 * with sign equal to "sign".
1112 * The result is simplified in terms of data->build->domain.
1114 static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
1115 __isl_keep isl_aff *aff, int sign, struct isl_ast_add_term_data *data)
1117 int i, j;
1118 isl_val *v;
1119 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1120 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1121 isl_local_space *ls;
1123 ls = isl_aff_get_domain_local_space(aff);
1125 for (i = 0; i < 3; ++i) {
1126 int n = isl_aff_dim(aff, t[i]);
1127 for (j = 0; j < n; ++j) {
1128 v = isl_aff_get_coefficient_val(aff, t[i], j);
1129 if (sign * isl_val_sgn(v) <= 0) {
1130 isl_val_free(v);
1131 continue;
1133 v = isl_val_abs(v);
1134 expr = isl_ast_expr_add_term(expr,
1135 ls, l[i], j, v, data);
1139 isl_local_space_free(ls);
1141 return expr;
1144 /* Should the constant term "v" be considered positive?
1146 * A positive constant will be added to "pos" by the caller,
1147 * while a negative constant will be added to "neg".
1148 * If either "pos" or "neg" is exactly zero, then we prefer
1149 * to add the constant "v" to that side, irrespective of the sign of "v".
1150 * This results in slightly shorter expressions and may reduce the risk
1151 * of overflows.
1153 static int constant_is_considered_positive(__isl_keep isl_val *v,
1154 __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
1156 if (ast_expr_is_zero(pos))
1157 return 1;
1158 if (ast_expr_is_zero(neg))
1159 return 0;
1160 return isl_val_is_pos(v);
1163 /* Check if the equality
1165 * aff = 0
1167 * represents a stride constraint on the integer division "pos".
1169 * In particular, if the integer division "pos" is equal to
1171 * floor(e/d)
1173 * then check if aff is equal to
1175 * e - d floor(e/d)
1177 * or its opposite.
1179 * If so, the equality is exactly
1181 * e mod d = 0
1183 * Note that in principle we could also accept
1185 * e - d floor(e'/d)
1187 * where e and e' differ by a constant.
1189 static int is_stride_constraint(__isl_keep isl_aff *aff, int pos)
1191 isl_aff *div;
1192 isl_val *c, *d;
1193 int eq;
1195 div = isl_aff_get_div(aff, pos);
1196 c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1197 d = isl_aff_get_denominator_val(div);
1198 eq = isl_val_abs_eq(c, d);
1199 if (eq >= 0 && eq) {
1200 aff = isl_aff_copy(aff);
1201 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1202 div = isl_aff_scale_val(div, d);
1203 if (isl_val_is_pos(c))
1204 div = isl_aff_neg(div);
1205 eq = isl_aff_plain_is_equal(div, aff);
1206 isl_aff_free(aff);
1207 } else
1208 isl_val_free(d);
1209 isl_val_free(c);
1210 isl_aff_free(div);
1212 return eq;
1215 /* Are all coefficients of "aff" (zero or) negative?
1217 static int all_negative_coefficients(__isl_keep isl_aff *aff)
1219 int i, n;
1221 if (!aff)
1222 return 0;
1224 n = isl_aff_dim(aff, isl_dim_param);
1225 for (i = 0; i < n; ++i)
1226 if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)
1227 return 0;
1229 n = isl_aff_dim(aff, isl_dim_in);
1230 for (i = 0; i < n; ++i)
1231 if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)
1232 return 0;
1234 return 1;
1237 /* Give an equality of the form
1239 * aff = e - d floor(e/d) = 0
1241 * or
1243 * aff = -e + d floor(e/d) = 0
1245 * with the integer division "pos" equal to floor(e/d),
1246 * construct the AST expression
1248 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0))
1250 * If e only has negative coefficients, then construct
1252 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(-e), expr(d)), expr(0))
1254 * instead.
1256 static __isl_give isl_ast_expr *extract_stride_constraint(
1257 __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
1259 isl_ctx *ctx;
1260 isl_val *c;
1261 isl_ast_expr *expr, *cst;
1263 if (!aff)
1264 return NULL;
1266 ctx = isl_aff_get_ctx(aff);
1268 c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1269 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1271 if (all_negative_coefficients(aff))
1272 aff = isl_aff_neg(aff);
1274 cst = isl_ast_expr_from_val(isl_val_abs(c));
1275 expr = isl_ast_expr_from_aff(aff, build);
1277 expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst);
1278 cst = isl_ast_expr_alloc_int_si(ctx, 0);
1279 expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst);
1281 return expr;
1284 /* Construct an isl_ast_expr that evaluates the condition "constraint",
1285 * The result is simplified in terms of build->domain.
1287 * We first check if the constraint is an equality of the form
1289 * e - d floor(e/d) = 0
1291 * i.e.,
1293 * e mod d = 0
1295 * If so, we convert it to
1297 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0))
1299 * Otherwise, let the constraint by either "a >= 0" or "a == 0".
1300 * We first extract hidden modulo computations from "a"
1301 * and then collect all the terms with a positive coefficient in cons_pos
1302 * and the terms with a negative coefficient in cons_neg.
1304 * The result is then of the form
1306 * (isl_ast_op_ge, expr(pos), expr(-neg)))
1308 * or
1310 * (isl_ast_op_eq, expr(pos), expr(-neg)))
1312 * However, if the first expression is an integer constant (and the second
1313 * is not), then we swap the two expressions. This ensures that we construct,
1314 * e.g., "i <= 5" rather than "5 >= i".
1316 * Furthermore, is there are no terms with positive coefficients (or no terms
1317 * with negative coefficients), then the constant term is added to "pos"
1318 * (or "neg"), ignoring the sign of the constant term.
1320 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1321 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1323 int i, n;
1324 isl_ctx *ctx;
1325 isl_ast_expr *expr_pos;
1326 isl_ast_expr *expr_neg;
1327 isl_ast_expr *expr;
1328 isl_aff *aff;
1329 int eq;
1330 enum isl_ast_op_type type;
1331 struct isl_ast_add_term_data data;
1333 if (!constraint)
1334 return NULL;
1336 aff = isl_constraint_get_aff(constraint);
1337 eq = isl_constraint_is_equality(constraint);
1338 isl_constraint_free(constraint);
1340 n = isl_aff_dim(aff, isl_dim_div);
1341 if (eq && n > 0)
1342 for (i = 0; i < n; ++i) {
1343 int is_stride;
1344 is_stride = is_stride_constraint(aff, i);
1345 if (is_stride < 0)
1346 goto error;
1347 if (is_stride)
1348 return extract_stride_constraint(aff, i, build);
1351 ctx = isl_aff_get_ctx(aff);
1352 expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
1353 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1355 aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
1357 data.build = build;
1358 data.cst = isl_aff_get_constant_val(aff);
1359 expr_pos = add_signed_terms(expr_pos, aff, 1, &data);
1360 data.cst = isl_val_neg(data.cst);
1361 expr_neg = add_signed_terms(expr_neg, aff, -1, &data);
1362 data.cst = isl_val_neg(data.cst);
1364 if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) {
1365 expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
1366 } else {
1367 data.cst = isl_val_neg(data.cst);
1368 expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
1371 if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
1372 isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
1373 type = eq ? isl_ast_op_eq : isl_ast_op_le;
1374 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
1375 } else {
1376 type = eq ? isl_ast_op_eq : isl_ast_op_ge;
1377 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
1380 isl_aff_free(aff);
1381 return expr;
1382 error:
1383 isl_aff_free(aff);
1384 return NULL;
1387 /* Wrapper around isl_constraint_cmp_last_non_zero for use
1388 * as a callback to isl_constraint_list_sort.
1389 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1390 * apart, then use isl_constraint_plain_cmp instead.
1392 static int cmp_constraint(__isl_keep isl_constraint *a,
1393 __isl_keep isl_constraint *b, void *user)
1395 int cmp;
1397 cmp = isl_constraint_cmp_last_non_zero(a, b);
1398 if (cmp != 0)
1399 return cmp;
1400 return isl_constraint_plain_cmp(a, b);
1403 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1404 * The result is simplified in terms of build->domain.
1406 * If "bset" is not bounded by any constraint, then we contruct
1407 * the expression "1", i.e., "true".
1409 * Otherwise, we sort the constraints, putting constraints that involve
1410 * integer divisions after those that do not, and construct an "and"
1411 * of the ast expressions of the individual constraints.
1413 * Each constraint is added to the generated constraints of the build
1414 * after it has been converted to an AST expression so that it can be used
1415 * to simplify the following constraints. This may change the truth value
1416 * of subsequent constraints that do not satisfy the earlier constraints,
1417 * but this does not affect the outcome of the conjunction as it is
1418 * only true if all the conjuncts are true (no matter in what order
1419 * they are evaluated). In particular, the constraints that do not
1420 * involve integer divisions may serve to simplify some constraints
1421 * that do involve integer divisions.
1423 __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
1424 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1426 int i, n;
1427 isl_constraint *c;
1428 isl_constraint_list *list;
1429 isl_ast_expr *res;
1430 isl_set *set;
1432 list = isl_basic_set_get_constraint_list(bset);
1433 isl_basic_set_free(bset);
1434 list = isl_constraint_list_sort(list, &cmp_constraint, NULL);
1435 if (!list)
1436 return NULL;
1437 n = isl_constraint_list_n_constraint(list);
1438 if (n == 0) {
1439 isl_ctx *ctx = isl_basic_set_get_ctx(bset);
1440 isl_constraint_list_free(list);
1441 return isl_ast_expr_alloc_int_si(ctx, 1);
1444 build = isl_ast_build_copy(build);
1446 c = isl_constraint_list_get_constraint(list, 0);
1447 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1448 set = isl_set_from_basic_set(bset);
1449 res = isl_ast_expr_from_constraint(c, build);
1450 build = isl_ast_build_restrict_generated(build, set);
1452 for (i = 1; i < n; ++i) {
1453 isl_ast_expr *expr;
1455 c = isl_constraint_list_get_constraint(list, i);
1456 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1457 set = isl_set_from_basic_set(bset);
1458 expr = isl_ast_expr_from_constraint(c, build);
1459 build = isl_ast_build_restrict_generated(build, set);
1460 res = isl_ast_expr_and(res, expr);
1463 isl_constraint_list_free(list);
1464 isl_ast_build_free(build);
1465 return res;
1468 struct isl_expr_from_set_data {
1469 isl_ast_build *build;
1470 int first;
1471 isl_ast_expr *res;
1474 /* Construct an isl_ast_expr that evaluates the conditions defining "bset"
1475 * and add it to data->res.
1476 * The result is simplified in terms of data->build->domain.
1478 static int expr_from_set(__isl_take isl_basic_set *bset, void *user)
1480 struct isl_expr_from_set_data *data = user;
1481 isl_ast_expr *expr;
1483 expr = isl_ast_build_expr_from_basic_set(data->build, bset);
1484 if (data->first)
1485 data->res = expr;
1486 else
1487 data->res = isl_ast_expr_or(data->res, expr);
1489 data->first = 0;
1491 if (!data->res)
1492 return -1;
1493 return 0;
1496 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1497 * The result is simplified in terms of build->domain.
1499 * If "set" is an (obviously) empty set, then return the expression "0".
1501 * "set" lives in the internal schedule space.
1503 __isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
1504 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1506 struct isl_expr_from_set_data data = { build, 1, NULL };
1508 if (isl_set_foreach_basic_set(set, &expr_from_set, &data) < 0)
1509 data.res = isl_ast_expr_free(data.res);
1510 else if (data.first) {
1511 isl_ctx *ctx = isl_ast_build_get_ctx(build);
1512 data.res = isl_ast_expr_from_val(isl_val_zero(ctx));
1515 isl_set_free(set);
1516 return data.res;
1519 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1520 * The result is simplified in terms of build->domain.
1522 * If "set" is an (obviously) empty set, then return the expression "0".
1524 * "set" lives in the external schedule space.
1526 * The internal AST expression generation assumes that there are
1527 * no unknown divs, so make sure an explicit representation is available.
1528 * Since the set comes from the outside, it may have constraints that
1529 * are redundant with respect to the build domain. Remove them first.
1531 __isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1532 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1534 if (isl_ast_build_need_schedule_map(build)) {
1535 isl_multi_aff *ma;
1536 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1537 set = isl_set_preimage_multi_aff(set, ma);
1540 set = isl_set_compute_divs(set);
1541 set = isl_ast_build_compute_gist(build, set);
1542 return isl_ast_build_expr_from_set_internal(build, set);
1545 struct isl_from_pw_aff_data {
1546 isl_ast_build *build;
1547 int n;
1548 isl_ast_expr **next;
1549 isl_set *dom;
1552 /* This function is called during the construction of an isl_ast_expr
1553 * that evaluates an isl_pw_aff.
1554 * Adjust data->next to take into account this piece.
1556 * data->n is the number of pairs of set and aff to go.
1557 * data->dom is the domain of the entire isl_pw_aff.
1559 * If this is the last pair, then data->next is set to evaluate aff
1560 * and the domain is ignored.
1561 * Otherwise, data->next is set to a select operation that selects
1562 * an isl_ast_expr corresponding to "aff" on "set" and to an expression
1563 * that will be filled in by later calls otherwise.
1565 * In both cases, the constraints of "set" are added to the generated
1566 * constraints of the build such that they can be exploited to simplify
1567 * the AST expression constructed from "aff".
1569 static int ast_expr_from_pw_aff(__isl_take isl_set *set,
1570 __isl_take isl_aff *aff, void *user)
1572 struct isl_from_pw_aff_data *data = user;
1573 isl_ctx *ctx;
1574 isl_ast_build *build;
1576 ctx = isl_set_get_ctx(set);
1577 data->n--;
1578 if (data->n == 0) {
1579 build = isl_ast_build_copy(data->build);
1580 build = isl_ast_build_restrict_generated(build, set);
1581 *data->next = isl_ast_expr_from_aff(aff, build);
1582 isl_ast_build_free(build);
1583 if (!*data->next)
1584 return -1;
1585 } else {
1586 isl_ast_expr *ternary, *arg;
1587 isl_set *gist;
1589 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
1590 gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));
1591 arg = isl_ast_build_expr_from_set_internal(data->build, gist);
1592 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
1593 build = isl_ast_build_copy(data->build);
1594 build = isl_ast_build_restrict_generated(build, set);
1595 arg = isl_ast_expr_from_aff(aff, build);
1596 isl_ast_build_free(build);
1597 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
1598 if (!ternary)
1599 return -1;
1601 *data->next = ternary;
1602 data->next = &ternary->u.op.args[2];
1605 return 0;
1608 /* Construct an isl_ast_expr that evaluates "pa".
1609 * The result is simplified in terms of build->domain.
1611 * The domain of "pa" lives in the internal schedule space.
1613 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
1614 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1616 struct isl_from_pw_aff_data data;
1617 isl_ast_expr *res = NULL;
1619 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
1620 pa = isl_pw_aff_coalesce(pa);
1621 if (!pa)
1622 return NULL;
1624 data.build = build;
1625 data.n = isl_pw_aff_n_piece(pa);
1626 data.next = &res;
1627 data.dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1629 if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0)
1630 res = isl_ast_expr_free(res);
1631 else if (!res)
1632 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
1633 "cannot handle void expression", res = NULL);
1635 isl_pw_aff_free(pa);
1636 isl_set_free(data.dom);
1637 return res;
1640 /* Construct an isl_ast_expr that evaluates "pa".
1641 * The result is simplified in terms of build->domain.
1643 * The domain of "pa" lives in the external schedule space.
1645 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
1646 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
1648 isl_ast_expr *expr;
1650 if (isl_ast_build_need_schedule_map(build)) {
1651 isl_multi_aff *ma;
1652 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1653 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
1655 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
1656 return expr;
1659 /* Set the ids of the input dimensions of "mpa" to the iterator ids
1660 * of "build".
1662 * The domain of "mpa" is assumed to live in the internal schedule domain.
1664 static __isl_give isl_multi_pw_aff *set_iterator_names(
1665 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1667 int i, n;
1669 n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
1670 for (i = 0; i < n; ++i) {
1671 isl_id *id;
1673 id = isl_ast_build_get_iterator_id(build, i);
1674 mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
1677 return mpa;
1680 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
1681 * the remaining arguments derived from "mpa".
1682 * That is, construct a call or access expression that calls/accesses "arg0"
1683 * with arguments/indices specified by "mpa".
1685 static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
1686 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1687 __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
1689 int i, n;
1690 isl_ctx *ctx;
1691 isl_ast_expr *expr;
1693 ctx = isl_ast_build_get_ctx(build);
1695 n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
1696 expr = isl_ast_expr_alloc_op(ctx, type, 1 + n);
1697 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
1698 for (i = 0; i < n; ++i) {
1699 isl_pw_aff *pa;
1700 isl_ast_expr *arg;
1702 pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
1703 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
1704 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
1707 isl_multi_pw_aff_free(mpa);
1708 return expr;
1711 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
1712 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1713 __isl_take isl_multi_pw_aff *mpa);
1715 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
1716 * The range of "mpa" is assumed to be wrapped relation.
1717 * The domain of this wrapped relation specifies the structure being
1718 * accessed, while the range of this wrapped relation spacifies the
1719 * member of the structure being accessed.
1721 * The domain of "mpa" is assumed to live in the internal schedule domain.
1723 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
1724 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1726 isl_id *id;
1727 isl_multi_pw_aff *domain;
1728 isl_ast_expr *domain_expr, *expr;
1729 enum isl_ast_op_type type = isl_ast_op_access;
1731 domain = isl_multi_pw_aff_copy(mpa);
1732 domain = isl_multi_pw_aff_range_factor_domain(domain);
1733 domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
1734 type, domain);
1735 mpa = isl_multi_pw_aff_range_factor_range(mpa);
1736 if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
1737 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
1738 "missing field name", goto error);
1739 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
1740 expr = isl_ast_expr_from_id(id);
1741 expr = isl_ast_expr_alloc_binary(isl_ast_op_member, domain_expr, expr);
1742 return isl_ast_build_with_arguments(build, type, expr, mpa);
1743 error:
1744 isl_multi_pw_aff_free(mpa);
1745 return NULL;
1748 /* Construct an isl_ast_expr of type "type" that calls or accesses
1749 * the element specified by "mpa".
1750 * The first argument is obtained from the output tuple name.
1751 * The remaining arguments are given by the piecewise affine expressions.
1753 * If the range of "mpa" is a mapped relation, then we assume it
1754 * represents an access to a member of a structure.
1756 * The domain of "mpa" is assumed to live in the internal schedule domain.
1758 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
1759 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1760 __isl_take isl_multi_pw_aff *mpa)
1762 isl_ctx *ctx;
1763 isl_id *id;
1764 isl_ast_expr *expr;
1766 if (!mpa)
1767 goto error;
1769 if (type == isl_ast_op_access &&
1770 isl_multi_pw_aff_range_is_wrapping(mpa))
1771 return isl_ast_build_from_multi_pw_aff_member(build, mpa);
1773 mpa = set_iterator_names(build, mpa);
1774 if (!build || !mpa)
1775 goto error;
1777 ctx = isl_ast_build_get_ctx(build);
1779 if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
1780 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
1781 else
1782 id = isl_id_alloc(ctx, "", NULL);
1784 expr = isl_ast_expr_from_id(id);
1785 return isl_ast_build_with_arguments(build, type, expr, mpa);
1786 error:
1787 isl_multi_pw_aff_free(mpa);
1788 return NULL;
1791 /* Construct an isl_ast_expr of type "type" that calls or accesses
1792 * the element specified by "pma".
1793 * The first argument is obtained from the output tuple name.
1794 * The remaining arguments are given by the piecewise affine expressions.
1796 * The domain of "pma" is assumed to live in the internal schedule domain.
1798 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
1799 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1800 __isl_take isl_pw_multi_aff *pma)
1802 isl_multi_pw_aff *mpa;
1804 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
1805 return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
1808 /* Construct an isl_ast_expr of type "type" that calls or accesses
1809 * the element specified by "mpa".
1810 * The first argument is obtained from the output tuple name.
1811 * The remaining arguments are given by the piecewise affine expressions.
1813 * The domain of "mpa" is assumed to live in the external schedule domain.
1815 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
1816 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1817 __isl_take isl_multi_pw_aff *mpa)
1819 int is_domain;
1820 isl_ast_expr *expr;
1821 isl_space *space_build, *space_mpa;
1823 space_build = isl_ast_build_get_space(build, 0);
1824 space_mpa = isl_multi_pw_aff_get_space(mpa);
1825 is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,
1826 space_mpa, isl_dim_in);
1827 isl_space_free(space_build);
1828 isl_space_free(space_mpa);
1829 if (is_domain < 0)
1830 goto error;
1831 if (!is_domain)
1832 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
1833 "spaces don't match", goto error);
1835 if (isl_ast_build_need_schedule_map(build)) {
1836 isl_multi_aff *ma;
1837 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1838 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
1841 expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
1842 return expr;
1843 error:
1844 isl_multi_pw_aff_free(mpa);
1845 return NULL;
1848 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
1849 * The name of the function is obtained from the output tuple name.
1850 * The arguments are given by the piecewise affine expressions.
1852 * The domain of "mpa" is assumed to live in the external schedule domain.
1854 __isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
1855 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1857 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_call, mpa);
1860 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
1861 * The name of the array is obtained from the output tuple name.
1862 * The index expressions are given by the piecewise affine expressions.
1864 * The domain of "mpa" is assumed to live in the external schedule domain.
1866 __isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
1867 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
1869 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_access, mpa);
1872 /* Construct an isl_ast_expr of type "type" that calls or accesses
1873 * the element specified by "pma".
1874 * The first argument is obtained from the output tuple name.
1875 * The remaining arguments are given by the piecewise affine expressions.
1877 * The domain of "pma" is assumed to live in the external schedule domain.
1879 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
1880 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
1881 __isl_take isl_pw_multi_aff *pma)
1883 isl_multi_pw_aff *mpa;
1885 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
1886 return isl_ast_build_from_multi_pw_aff(build, type, mpa);
1889 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
1890 * The name of the function is obtained from the output tuple name.
1891 * The arguments are given by the piecewise affine expressions.
1893 * The domain of "pma" is assumed to live in the external schedule domain.
1895 __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
1896 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1898 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_call, pma);
1901 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
1902 * The name of the array is obtained from the output tuple name.
1903 * The index expressions are given by the piecewise affine expressions.
1905 * The domain of "pma" is assumed to live in the external schedule domain.
1907 __isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
1908 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
1910 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma);
1913 /* Construct an isl_ast_expr that calls the domain element
1914 * specified by "executed".
1916 * "executed" is assumed to be single-valued, with a domain that lives
1917 * in the internal schedule space.
1919 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
1920 __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
1922 isl_pw_multi_aff *iteration;
1923 isl_ast_expr *expr;
1925 iteration = isl_pw_multi_aff_from_map(executed);
1926 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
1927 iteration = isl_pw_multi_aff_intersect_domain(iteration,
1928 isl_ast_build_get_domain(build));
1929 expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call,
1930 iteration);
1931 return isl_ast_node_alloc_user(expr);