isl_union_map.c: un_op: implement in terms of cond_un_op and rename to total
[isl.git] / isl_ast_build_expr.c
blob3213886ddf29d24763470c8c27ba449b42ad653c
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/constraint.h>
14 #include <isl/ilp.h>
15 #include <isl_ast_build_expr.h>
16 #include <isl_ast_private.h>
17 #include <isl_ast_build_private.h>
18 #include <isl_sort.h>
20 /* Compute the "opposite" of the (numerator of the) argument of a div
21 * with denominator "d".
23 * In particular, compute
25 * -aff + (d - 1)
27 static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
28 __isl_take isl_val *d)
30 aff = isl_aff_neg(aff);
31 aff = isl_aff_add_constant_val(aff, d);
32 aff = isl_aff_add_constant_si(aff, -1);
34 return aff;
37 /* Internal data structure used inside isl_ast_expr_add_term.
38 * The domain of "build" is used to simplify the expressions.
39 * "build" needs to be set by the caller of isl_ast_expr_add_term.
40 * "cst" is the constant term of the expression in which the added term
41 * appears. It may be modified by isl_ast_expr_add_term.
43 * "v" is the coefficient of the term that is being constructed and
44 * is set internally by isl_ast_expr_add_term.
46 struct isl_ast_add_term_data {
47 isl_ast_build *build;
48 isl_val *cst;
49 isl_val *v;
52 /* Given the numerator "aff" of the argument of an integer division
53 * with denominator "d", check if it can be made non-negative over
54 * data->build->domain by stealing part of the constant term of
55 * the expression in which the integer division appears.
57 * In particular, the outer expression is of the form
59 * v * floor(aff/d) + cst
61 * We already know that "aff" itself may attain negative values.
62 * Here we check if aff + d*floor(cst/v) is non-negative, such
63 * that we could rewrite the expression to
65 * v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
67 * Note that aff + d*floor(cst/v) can only possibly be non-negative
68 * if data->cst and data->v have the same sign.
69 * Similarly, if floor(cst/v) is zero, then there is no point in
70 * checking again.
72 static int is_non_neg_after_stealing(__isl_keep isl_aff *aff,
73 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
75 isl_aff *shifted;
76 isl_val *shift;
77 int is_zero;
78 int non_neg;
80 if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))
81 return 0;
83 shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));
84 shift = isl_val_floor(shift);
85 is_zero = isl_val_is_zero(shift);
86 if (is_zero < 0 || is_zero) {
87 isl_val_free(shift);
88 return is_zero < 0 ? -1 : 0;
90 shift = isl_val_mul(shift, isl_val_copy(d));
91 shifted = isl_aff_copy(aff);
92 shifted = isl_aff_add_constant_val(shifted, shift);
93 non_neg = isl_ast_build_aff_is_nonneg(data->build, shifted);
94 isl_aff_free(shifted);
96 return non_neg;
99 /* Given the numerator "aff' of the argument of an integer division
100 * with denominator "d", steal part of the constant term of
101 * the expression in which the integer division appears to make it
102 * non-negative over data->build->domain.
104 * In particular, the outer expression is of the form
106 * v * floor(aff/d) + cst
108 * We know that "aff" itself may attain negative values,
109 * but that aff + d*floor(cst/v) is non-negative.
110 * Find the minimal positive value that we need to add to "aff"
111 * to make it positive and adjust data->cst accordingly.
112 * That is, compute the minimal value "m" of "aff" over
113 * data->build->domain and take
115 * s = ceil(m/d)
117 * such that
119 * aff + d * s >= 0
121 * and rewrite the expression to
123 * v * floor((aff + s*d)/d) + (cst - v*s)
125 static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
126 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
128 isl_set *domain;
129 isl_val *shift, *t;
131 domain = isl_ast_build_get_domain(data->build);
132 shift = isl_set_min_val(domain, aff);
133 isl_set_free(domain);
135 shift = isl_val_neg(shift);
136 shift = isl_val_div(shift, isl_val_copy(d));
137 shift = isl_val_ceil(shift);
139 t = isl_val_copy(shift);
140 t = isl_val_mul(t, isl_val_copy(data->v));
141 data->cst = isl_val_sub(data->cst, t);
143 shift = isl_val_mul(shift, isl_val_copy(d));
144 return isl_aff_add_constant_val(aff, shift);
147 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
148 * The result is simplified in terms of data->build->domain.
149 * This function may change (the sign of) data->v.
151 * "ls" is known to be non-NULL.
153 * Let the div be of the form floor(e/d).
154 * If the ast_build_prefer_pdiv option is set then we check if "e"
155 * is non-negative, so that we can generate
157 * (pdiv_q, expr(e), expr(d))
159 * instead of
161 * (fdiv_q, expr(e), expr(d))
163 * If the ast_build_prefer_pdiv option is set and
164 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
165 * If so, we can rewrite
167 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
169 * and still use pdiv_q, while changing the sign of data->v.
171 * Otherwise, we check if
173 * e + d*floor(cst/v)
175 * is non-negative and if so, replace floor(e/d) by
177 * floor((e + s*d)/d) - s
179 * with s the minimal shift that makes the argument non-negative.
181 static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,
182 __isl_keep isl_local_space *ls, int pos)
184 isl_ctx *ctx = isl_local_space_get_ctx(ls);
185 isl_aff *aff;
186 isl_ast_expr *num, *den;
187 isl_val *d;
188 enum isl_ast_op_type type;
190 aff = isl_local_space_get_div(ls, pos);
191 d = isl_aff_get_denominator_val(aff);
192 aff = isl_aff_scale_val(aff, isl_val_copy(d));
193 den = isl_ast_expr_from_val(isl_val_copy(d));
195 type = isl_ast_op_fdiv_q;
196 if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
197 int non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);
198 if (non_neg >= 0 && !non_neg) {
199 isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),
200 isl_val_copy(d));
201 non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);
202 if (non_neg >= 0 && non_neg) {
203 data->v = isl_val_neg(data->v);
204 isl_aff_free(aff);
205 aff = opp;
206 } else
207 isl_aff_free(opp);
209 if (non_neg >= 0 && !non_neg) {
210 non_neg = is_non_neg_after_stealing(aff, d, data);
211 if (non_neg >= 0 && non_neg)
212 aff = steal_from_cst(aff, d, data);
214 if (non_neg < 0)
215 aff = isl_aff_free(aff);
216 else if (non_neg)
217 type = isl_ast_op_pdiv_q;
220 isl_val_free(d);
221 num = isl_ast_expr_from_aff(aff, data->build);
222 return isl_ast_expr_alloc_binary(type, num, den);
225 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
226 * The result is simplified in terms of data->build->domain.
227 * This function may change (the sign of) data->v.
229 * The isl_ast_expr is constructed based on the type of the dimension.
230 * - divs are constructed by var_div
231 * - set variables are constructed from the iterator isl_ids in data->build
232 * - parameters are constructed from the isl_ids in "ls"
234 static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
235 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos)
237 isl_ctx *ctx = isl_local_space_get_ctx(ls);
238 isl_id *id;
240 if (type == isl_dim_div)
241 return var_div(data, ls, pos);
243 if (type == isl_dim_set) {
244 id = isl_ast_build_get_iterator_id(data->build, pos);
245 return isl_ast_expr_from_id(id);
248 if (!isl_local_space_has_dim_id(ls, type, pos))
249 isl_die(ctx, isl_error_internal, "unnamed dimension",
250 return NULL);
251 id = isl_local_space_get_dim_id(ls, type, pos);
252 return isl_ast_expr_from_id(id);
255 /* Does "expr" represent the zero integer?
257 static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
259 if (!expr)
260 return -1;
261 if (expr->type != isl_ast_expr_int)
262 return 0;
263 return isl_val_is_zero(expr->u.v);
266 /* Create an expression representing the sum of "expr1" and "expr2",
267 * provided neither of the two expressions is identically zero.
269 static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
270 __isl_take isl_ast_expr *expr2)
272 if (!expr1 || !expr2)
273 goto error;
275 if (ast_expr_is_zero(expr1)) {
276 isl_ast_expr_free(expr1);
277 return expr2;
280 if (ast_expr_is_zero(expr2)) {
281 isl_ast_expr_free(expr2);
282 return expr1;
285 return isl_ast_expr_add(expr1, expr2);
286 error:
287 isl_ast_expr_free(expr1);
288 isl_ast_expr_free(expr2);
289 return NULL;
292 /* Subtract expr2 from expr1.
294 * If expr2 is zero, we simply return expr1.
295 * If expr1 is zero, we return
297 * (isl_ast_op_minus, expr2)
299 * Otherwise, we return
301 * (isl_ast_op_sub, expr1, expr2)
303 static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
304 __isl_take isl_ast_expr *expr2)
306 if (!expr1 || !expr2)
307 goto error;
309 if (ast_expr_is_zero(expr2)) {
310 isl_ast_expr_free(expr2);
311 return expr1;
314 if (ast_expr_is_zero(expr1)) {
315 isl_ast_expr_free(expr1);
316 return isl_ast_expr_neg(expr2);
319 return isl_ast_expr_sub(expr1, expr2);
320 error:
321 isl_ast_expr_free(expr1);
322 isl_ast_expr_free(expr2);
323 return NULL;
326 /* Return an isl_ast_expr that represents
328 * v * (aff mod d)
330 * v is assumed to be non-negative.
331 * The result is simplified in terms of build->domain.
333 static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
334 __isl_keep isl_aff *aff, __isl_keep isl_val *d,
335 __isl_keep isl_ast_build *build)
337 isl_ast_expr *expr;
338 isl_ast_expr *c;
340 if (!aff)
341 return NULL;
343 expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
345 c = isl_ast_expr_from_val(isl_val_copy(d));
346 expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
348 if (!isl_val_is_one(v)) {
349 c = isl_ast_expr_from_val(isl_val_copy(v));
350 expr = isl_ast_expr_mul(c, expr);
353 return expr;
356 /* Create an isl_ast_expr that scales "expr" by "v".
358 * If v is 1, we simply return expr.
359 * If v is -1, we return
361 * (isl_ast_op_minus, expr)
363 * Otherwise, we return
365 * (isl_ast_op_mul, expr(v), expr)
367 static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
368 __isl_take isl_val *v)
370 isl_ast_expr *c;
372 if (!expr || !v)
373 goto error;
374 if (isl_val_is_one(v)) {
375 isl_val_free(v);
376 return expr;
379 if (isl_val_is_negone(v)) {
380 isl_val_free(v);
381 expr = isl_ast_expr_neg(expr);
382 } else {
383 c = isl_ast_expr_from_val(v);
384 expr = isl_ast_expr_mul(c, expr);
387 return expr;
388 error:
389 isl_val_free(v);
390 isl_ast_expr_free(expr);
391 return NULL;
394 /* Add an expression for "*v" times the specified dimension of "ls"
395 * to expr.
396 * If the dimension is an integer division, then this function
397 * may modify data->cst in order to make the numerator non-negative.
398 * The result is simplified in terms of data->build->domain.
400 * Let e be the expression for the specified dimension,
401 * multiplied by the absolute value of "*v".
402 * If "*v" is negative, we create
404 * (isl_ast_op_sub, expr, e)
406 * except when expr is trivially zero, in which case we create
408 * (isl_ast_op_minus, e)
410 * instead.
412 * If "*v" is positive, we simply create
414 * (isl_ast_op_add, expr, e)
417 static __isl_give isl_ast_expr *isl_ast_expr_add_term(
418 __isl_take isl_ast_expr *expr,
419 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
420 __isl_take isl_val *v, struct isl_ast_add_term_data *data)
422 isl_ast_expr *term;
424 if (!expr)
425 return NULL;
427 data->v = v;
428 term = var(data, ls, type, pos);
429 v = data->v;
431 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
432 v = isl_val_neg(v);
433 term = scale(term, v);
434 return ast_expr_sub(expr, term);
435 } else {
436 term = scale(term, v);
437 return ast_expr_add(expr, term);
441 /* Add an expression for "v" to expr.
443 static __isl_give isl_ast_expr *isl_ast_expr_add_int(
444 __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
446 isl_ast_expr *expr_int;
448 if (!expr || !v)
449 goto error;
451 if (isl_val_is_zero(v)) {
452 isl_val_free(v);
453 return expr;
456 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
457 v = isl_val_neg(v);
458 expr_int = isl_ast_expr_from_val(v);
459 return ast_expr_sub(expr, expr_int);
460 } else {
461 expr_int = isl_ast_expr_from_val(v);
462 return ast_expr_add(expr, expr_int);
464 error:
465 isl_ast_expr_free(expr);
466 isl_val_free(v);
467 return NULL;
470 /* Internal data structure used inside extract_modulos.
472 * If any modulo expressions are detected in "aff", then the
473 * expression is removed from "aff" and added to either "pos" or "neg"
474 * depending on the sign of the coefficient of the modulo expression
475 * inside "aff".
477 * "add" is an expression that needs to be added to "aff" at the end of
478 * the computation. It is NULL as long as no modulos have been extracted.
480 * "i" is the position in "aff" of the div under investigation
481 * "v" is the coefficient in "aff" of the div
482 * "div" is the argument of the div, with the denominator removed
483 * "d" is the original denominator of the argument of the div
485 * "nonneg" is an affine expression that is non-negative over "build"
486 * and that can be used to extract a modulo expression from "div".
487 * In particular, if "sign" is 1, then the coefficients of "nonneg"
488 * are equal to those of "div" modulo "d". If "sign" is -1, then
489 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
490 * If "sign" is 0, then no such affine expression has been found (yet).
492 struct isl_extract_mod_data {
493 isl_ast_build *build;
494 isl_aff *aff;
496 isl_ast_expr *pos;
497 isl_ast_expr *neg;
499 isl_aff *add;
501 int i;
502 isl_val *v;
503 isl_val *d;
504 isl_aff *div;
506 isl_aff *nonneg;
507 int sign;
510 /* Given that data->v * div_i in data->aff is equal to
512 * f * (term - (arg mod d))
514 * with data->d * f = data->v, add
516 * f * term
518 * to data->add and
520 * abs(f) * (arg mod d)
522 * to data->neg or data->pos depending on the sign of -f.
524 static int extract_term_and_mod(struct isl_extract_mod_data *data,
525 __isl_take isl_aff *term, __isl_take isl_aff *arg)
527 isl_ast_expr *expr;
528 int s;
530 data->v = isl_val_div(data->v, isl_val_copy(data->d));
531 s = isl_val_sgn(data->v);
532 data->v = isl_val_abs(data->v);
533 expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
534 isl_aff_free(arg);
535 if (s > 0)
536 data->neg = ast_expr_add(data->neg, expr);
537 else
538 data->pos = ast_expr_add(data->pos, expr);
539 data->aff = isl_aff_set_coefficient_si(data->aff,
540 isl_dim_div, data->i, 0);
541 if (s < 0)
542 data->v = isl_val_neg(data->v);
543 term = isl_aff_scale_val(term, isl_val_copy(data->v));
545 if (!data->add)
546 data->add = term;
547 else
548 data->add = isl_aff_add(data->add, term);
549 if (!data->add)
550 return -1;
552 return 0;
555 /* Given that data->v * div_i in data->aff is of the form
557 * f * d * floor(div/d)
559 * with div nonnegative on data->build, rewrite it as
561 * f * (div - (div mod d)) = f * div - f * (div mod d)
563 * and add
565 * f * div
567 * to data->add and
569 * abs(f) * (div mod d)
571 * to data->neg or data->pos depending on the sign of -f.
573 static int extract_mod(struct isl_extract_mod_data *data)
575 return extract_term_and_mod(data, isl_aff_copy(data->div),
576 isl_aff_copy(data->div));
579 /* Given that data->v * div_i in data->aff is of the form
581 * f * d * floor(div/d) (1)
583 * check if div is non-negative on data->build and, if so,
584 * extract the corresponding modulo from data->aff.
585 * If not, then check if
587 * -div + d - 1
589 * is non-negative on data->build. If so, replace (1) by
591 * -f * d * floor((-div + d - 1)/d)
593 * and extract the corresponding modulo from data->aff.
595 * This function may modify data->div.
597 static int extract_nonneg_mod(struct isl_extract_mod_data *data)
599 int mod;
601 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
602 if (mod < 0)
603 goto error;
604 if (mod)
605 return extract_mod(data);
607 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
608 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
609 if (mod < 0)
610 goto error;
611 if (mod) {
612 data->v = isl_val_neg(data->v);
613 return extract_mod(data);
616 return 0;
617 error:
618 data->aff = isl_aff_free(data->aff);
619 return -1;
622 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
623 * for use in extracting a modulo expression?
625 * We currently only consider the constant term of the affine expression.
626 * In particular, we prefer the affine expression with the smallest constant
627 * term.
628 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
629 * then we would pick x >= 0
631 * More detailed heuristics could be used if it turns out that there is a need.
633 static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
634 __isl_keep isl_constraint *c)
636 isl_val *v1, *v2;
637 int simpler;
639 if (!data->nonneg)
640 return 1;
642 v1 = isl_val_abs(isl_constraint_get_constant_val(c));
643 v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
644 simpler = isl_val_lt(v1, v2);
645 isl_val_free(v1);
646 isl_val_free(v2);
648 return simpler;
651 /* Check if the coefficients of "c" are either equal or opposite to those
652 * of data->div modulo data->d. If so, and if "c" is "simpler" than
653 * data->nonneg, then replace data->nonneg by the affine expression of "c"
654 * and set data->sign accordingly.
656 * Both "c" and data->div are assumed not to involve any integer divisions.
658 * Before we start the actual comparison, we first quickly check if
659 * "c" and data->div have the same non-zero coefficients.
660 * If not, then we assume that "c" is not of the desired form.
661 * Note that while the coefficients of data->div can be reasonably expected
662 * not to involve any coefficients that are multiples of d, "c" may
663 * very well involve such coefficients. This means that we may actually
664 * miss some cases.
666 * If the constant term is "too large", then the constraint is rejected,
667 * where "too large" is fairly arbitrarily set to 1 << 15.
668 * We do this to avoid picking up constraints that bound a variable
669 * by a very large number, say the largest or smallest possible
670 * variable in the representation of some integer type.
672 static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
673 void *user)
675 struct isl_extract_mod_data *data = user;
676 enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
677 enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
678 int i, t;
679 int n[2];
680 int parallel = 1, opposite = 1;
682 for (t = 0; t < 2; ++t) {
683 n[t] = isl_constraint_dim(c, c_type[t]);
684 for (i = 0; i < n[t]; ++i) {
685 int a, b;
687 a = isl_constraint_involves_dims(c, c_type[t], i, 1);
688 b = isl_aff_involves_dims(data->div, a_type[t], i, 1);
689 if (a != b)
690 parallel = opposite = 0;
694 if (parallel || opposite) {
695 isl_val *v;
697 v = isl_val_abs(isl_constraint_get_constant_val(c));
698 if (isl_val_cmp_si(v, 1 << 15) > 0)
699 parallel = opposite = 0;
700 isl_val_free(v);
703 for (t = 0; t < 2; ++t) {
704 for (i = 0; i < n[t]; ++i) {
705 isl_val *v1, *v2;
707 if (!parallel && !opposite)
708 break;
709 v1 = isl_constraint_get_coefficient_val(c,
710 c_type[t], i);
711 v2 = isl_aff_get_coefficient_val(data->div,
712 a_type[t], i);
713 if (parallel) {
714 v1 = isl_val_sub(v1, isl_val_copy(v2));
715 parallel = isl_val_is_divisible_by(v1, data->d);
716 v1 = isl_val_add(v1, isl_val_copy(v2));
718 if (opposite) {
719 v1 = isl_val_add(v1, isl_val_copy(v2));
720 opposite = isl_val_is_divisible_by(v1, data->d);
722 isl_val_free(v1);
723 isl_val_free(v2);
727 if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {
728 isl_aff_free(data->nonneg);
729 data->nonneg = isl_constraint_get_aff(c);
730 data->sign = parallel ? 1 : -1;
733 isl_constraint_free(c);
735 if (data->sign != 0 && data->nonneg == NULL)
736 return isl_stat_error;
738 return isl_stat_ok;
741 /* Given that data->v * div_i in data->aff is of the form
743 * f * d * floor(div/d) (1)
745 * see if we can find an expression div' that is non-negative over data->build
746 * and that is related to div through
748 * div' = div + d * e
750 * or
752 * div' = -div + d - 1 + d * e
754 * with e some affine expression.
755 * If so, we write (1) as
757 * f * div + f * (div' mod d)
759 * or
761 * -f * (-div + d - 1) - f * (div' mod d)
763 * exploiting (in the second case) the fact that
765 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
768 * We first try to find an appropriate expression for div'
769 * from the constraints of data->build->domain (which is therefore
770 * guaranteed to be non-negative on data->build), where we remove
771 * any integer divisions from the constraints and skip this step
772 * if "div" itself involves any integer divisions.
773 * If we cannot find an appropriate expression this way, then
774 * we pass control to extract_nonneg_mod where check
775 * if div or "-div + d -1" themselves happen to be
776 * non-negative on data->build.
778 * While looking for an appropriate constraint in data->build->domain,
779 * we ignore the constant term, so after finding such a constraint,
780 * we still need to fix up the constant term.
781 * In particular, if a is the constant term of "div"
782 * (or d - 1 - the constant term of "div" if data->sign < 0)
783 * and b is the constant term of the constraint, then we need to find
784 * a non-negative constant c such that
786 * b + c \equiv a mod d
788 * We therefore take
790 * c = (a - b) mod d
792 * and add it to b to obtain the constant term of div'.
793 * If this constant term is "too negative", then we add an appropriate
794 * multiple of d to make it positive.
797 * Note that the above is a only a very simple heuristic for finding an
798 * appropriate expression. We could try a bit harder by also considering
799 * sums of constraints that involve disjoint sets of variables or
800 * we could consider arbitrary linear combinations of constraints,
801 * although that could potentially be much more expensive as it involves
802 * the solution of an LP problem.
804 * In particular, if v_i is a column vector representing constraint i,
805 * w represents div and e_i is the i-th unit vector, then we are looking
806 * for a solution of the constraints
808 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
810 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
811 * If we are not just interested in a non-negative expression, but
812 * also in one with a minimal range, then we don't just want
813 * c = \sum_i lambda_i v_i to be non-negative over the domain,
814 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
815 * that we want to minimize and we now also have to take into account
816 * the constant terms of the constraints.
817 * Alternatively, we could first compute the dual of the domain
818 * and plug in the constraints on the coefficients.
820 static int try_extract_mod(struct isl_extract_mod_data *data)
822 isl_basic_set *hull;
823 isl_val *v1, *v2;
824 int r, n;
826 if (!data->build)
827 goto error;
829 n = isl_aff_dim(data->div, isl_dim_div);
831 if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
832 return extract_nonneg_mod(data);
834 hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
835 hull = isl_basic_set_remove_divs(hull);
836 data->sign = 0;
837 data->nonneg = NULL;
838 r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
839 data);
840 isl_basic_set_free(hull);
842 if (!data->sign || r < 0) {
843 isl_aff_free(data->nonneg);
844 if (r < 0)
845 goto error;
846 return extract_nonneg_mod(data);
849 v1 = isl_aff_get_constant_val(data->div);
850 v2 = isl_aff_get_constant_val(data->nonneg);
851 if (data->sign < 0) {
852 v1 = isl_val_neg(v1);
853 v1 = isl_val_add(v1, isl_val_copy(data->d));
854 v1 = isl_val_sub_ui(v1, 1);
856 v1 = isl_val_sub(v1, isl_val_copy(v2));
857 v1 = isl_val_mod(v1, isl_val_copy(data->d));
858 v1 = isl_val_add(v1, v2);
859 v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
860 v2 = isl_val_ceil(v2);
861 if (isl_val_is_neg(v2)) {
862 v2 = isl_val_mul(v2, isl_val_copy(data->d));
863 v1 = isl_val_sub(v1, isl_val_copy(v2));
865 data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
866 isl_val_free(v2);
868 if (data->sign < 0) {
869 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
870 data->v = isl_val_neg(data->v);
873 return extract_term_and_mod(data,
874 isl_aff_copy(data->div), data->nonneg);
875 error:
876 data->aff = isl_aff_free(data->aff);
877 return -1;
880 /* Check if "data->aff" involves any (implicit) modulo computations based
881 * on div "data->i".
882 * If so, remove them from aff and add expressions corresponding
883 * to those modulo computations to data->pos and/or data->neg.
885 * "aff" is assumed to be an integer affine expression.
887 * In particular, check if (v * div_j) is of the form
889 * f * m * floor(a / m)
891 * and, if so, rewrite it as
893 * f * (a - (a mod m)) = f * a - f * (a mod m)
895 * and extract out -f * (a mod m).
896 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
897 * If f < 0, we add ((-f) * (a mod m)) to *pos.
899 * Note that in order to represent "a mod m" as
901 * (isl_ast_op_pdiv_r, a, m)
903 * we need to make sure that a is non-negative.
904 * If not, we check if "-a + m - 1" is non-negative.
905 * If so, we can rewrite
907 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
909 * and still extract a modulo.
911 static int extract_modulo(struct isl_extract_mod_data *data)
913 data->div = isl_aff_get_div(data->aff, data->i);
914 data->d = isl_aff_get_denominator_val(data->div);
915 if (isl_val_is_divisible_by(data->v, data->d)) {
916 data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
917 if (try_extract_mod(data) < 0)
918 data->aff = isl_aff_free(data->aff);
920 isl_aff_free(data->div);
921 isl_val_free(data->d);
922 return 0;
925 /* Check if "aff" involves any (implicit) modulo computations.
926 * If so, remove them from aff and add expressions corresponding
927 * to those modulo computations to *pos and/or *neg.
928 * We only do this if the option ast_build_prefer_pdiv is set.
930 * "aff" is assumed to be an integer affine expression.
932 * A modulo expression is of the form
934 * a mod m = a - m * floor(a / m)
936 * To detect them in aff, we look for terms of the form
938 * f * m * floor(a / m)
940 * rewrite them as
942 * f * (a - (a mod m)) = f * a - f * (a mod m)
944 * and extract out -f * (a mod m).
945 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
946 * If f < 0, we add ((-f) * (a mod m)) to *pos.
948 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
949 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
950 __isl_keep isl_ast_build *build)
952 struct isl_extract_mod_data data = { build, aff, *pos, *neg };
953 isl_ctx *ctx;
954 int n;
956 if (!aff)
957 return NULL;
959 ctx = isl_aff_get_ctx(aff);
960 if (!isl_options_get_ast_build_prefer_pdiv(ctx))
961 return aff;
963 n = isl_aff_dim(data.aff, isl_dim_div);
964 for (data.i = 0; data.i < n; ++data.i) {
965 data.v = isl_aff_get_coefficient_val(data.aff,
966 isl_dim_div, data.i);
967 if (!data.v)
968 return isl_aff_free(aff);
969 if (isl_val_is_zero(data.v) ||
970 isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {
971 isl_val_free(data.v);
972 continue;
974 if (extract_modulo(&data) < 0)
975 data.aff = isl_aff_free(data.aff);
976 isl_val_free(data.v);
977 if (!data.aff)
978 break;
981 if (data.add)
982 data.aff = isl_aff_add(data.aff, data.add);
984 *pos = data.pos;
985 *neg = data.neg;
986 return data.aff;
989 /* Check if aff involves any non-integer coefficients.
990 * If so, split aff into
992 * aff = aff1 + (aff2 / d)
994 * with both aff1 and aff2 having only integer coefficients.
995 * Return aff1 and add (aff2 / d) to *expr.
997 static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
998 __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
1000 int i, j, n;
1001 isl_aff *rat = NULL;
1002 isl_local_space *ls = NULL;
1003 isl_ast_expr *rat_expr;
1004 isl_val *v, *d;
1005 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1006 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1008 if (!aff)
1009 return NULL;
1010 d = isl_aff_get_denominator_val(aff);
1011 if (!d)
1012 goto error;
1013 if (isl_val_is_one(d)) {
1014 isl_val_free(d);
1015 return aff;
1018 aff = isl_aff_scale_val(aff, isl_val_copy(d));
1020 ls = isl_aff_get_domain_local_space(aff);
1021 rat = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1023 for (i = 0; i < 3; ++i) {
1024 n = isl_aff_dim(aff, t[i]);
1025 for (j = 0; j < n; ++j) {
1026 isl_aff *rat_j;
1028 v = isl_aff_get_coefficient_val(aff, t[i], j);
1029 if (!v)
1030 goto error;
1031 if (isl_val_is_divisible_by(v, d)) {
1032 isl_val_free(v);
1033 continue;
1035 rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls),
1036 l[i], j);
1037 rat_j = isl_aff_scale_val(rat_j, v);
1038 rat = isl_aff_add(rat, rat_j);
1042 v = isl_aff_get_constant_val(aff);
1043 if (isl_val_is_divisible_by(v, d)) {
1044 isl_val_free(v);
1045 } else {
1046 isl_aff *rat_0;
1048 rat_0 = isl_aff_val_on_domain(isl_local_space_copy(ls), v);
1049 rat = isl_aff_add(rat, rat_0);
1052 isl_local_space_free(ls);
1054 aff = isl_aff_sub(aff, isl_aff_copy(rat));
1055 aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
1057 rat_expr = isl_ast_expr_from_aff(rat, build);
1058 rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
1059 *expr = ast_expr_add(*expr, rat_expr);
1061 return aff;
1062 error:
1063 isl_aff_free(rat);
1064 isl_local_space_free(ls);
1065 isl_aff_free(aff);
1066 isl_val_free(d);
1067 return NULL;
1070 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
1071 * The result is simplified in terms of build->domain.
1073 * We first extract hidden modulo computations from the affine expression
1074 * and then add terms for each variable with a non-zero coefficient.
1075 * Finally, if the affine expression has a non-trivial denominator,
1076 * we divide the resulting isl_ast_expr by this denominator.
1078 __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
1079 __isl_keep isl_ast_build *build)
1081 int i, j;
1082 int n;
1083 isl_val *v;
1084 isl_ctx *ctx = isl_aff_get_ctx(aff);
1085 isl_ast_expr *expr, *expr_neg;
1086 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1087 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1088 isl_local_space *ls;
1089 struct isl_ast_add_term_data data;
1091 if (!aff)
1092 return NULL;
1094 expr = isl_ast_expr_alloc_int_si(ctx, 0);
1095 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1097 aff = extract_rational(aff, &expr, build);
1099 aff = extract_modulos(aff, &expr, &expr_neg, build);
1100 expr = ast_expr_sub(expr, expr_neg);
1102 ls = isl_aff_get_domain_local_space(aff);
1104 data.build = build;
1105 data.cst = isl_aff_get_constant_val(aff);
1106 for (i = 0; i < 3; ++i) {
1107 n = isl_aff_dim(aff, t[i]);
1108 for (j = 0; j < n; ++j) {
1109 v = isl_aff_get_coefficient_val(aff, t[i], j);
1110 if (!v)
1111 expr = isl_ast_expr_free(expr);
1112 if (isl_val_is_zero(v)) {
1113 isl_val_free(v);
1114 continue;
1116 expr = isl_ast_expr_add_term(expr,
1117 ls, l[i], j, v, &data);
1121 expr = isl_ast_expr_add_int(expr, data.cst);
1123 isl_local_space_free(ls);
1124 isl_aff_free(aff);
1125 return expr;
1128 /* Add terms to "expr" for each variable in "aff" with a coefficient
1129 * with sign equal to "sign".
1130 * The result is simplified in terms of data->build->domain.
1132 static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
1133 __isl_keep isl_aff *aff, int sign, struct isl_ast_add_term_data *data)
1135 int i, j;
1136 isl_val *v;
1137 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1138 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1139 isl_local_space *ls;
1141 ls = isl_aff_get_domain_local_space(aff);
1143 for (i = 0; i < 3; ++i) {
1144 int n = isl_aff_dim(aff, t[i]);
1145 for (j = 0; j < n; ++j) {
1146 v = isl_aff_get_coefficient_val(aff, t[i], j);
1147 if (sign * isl_val_sgn(v) <= 0) {
1148 isl_val_free(v);
1149 continue;
1151 v = isl_val_abs(v);
1152 expr = isl_ast_expr_add_term(expr,
1153 ls, l[i], j, v, data);
1157 isl_local_space_free(ls);
1159 return expr;
1162 /* Should the constant term "v" be considered positive?
1164 * A positive constant will be added to "pos" by the caller,
1165 * while a negative constant will be added to "neg".
1166 * If either "pos" or "neg" is exactly zero, then we prefer
1167 * to add the constant "v" to that side, irrespective of the sign of "v".
1168 * This results in slightly shorter expressions and may reduce the risk
1169 * of overflows.
1171 static int constant_is_considered_positive(__isl_keep isl_val *v,
1172 __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
1174 if (ast_expr_is_zero(pos))
1175 return 1;
1176 if (ast_expr_is_zero(neg))
1177 return 0;
1178 return isl_val_is_pos(v);
1181 /* Check if the equality
1183 * aff = 0
1185 * represents a stride constraint on the integer division "pos".
1187 * In particular, if the integer division "pos" is equal to
1189 * floor(e/d)
1191 * then check if aff is equal to
1193 * e - d floor(e/d)
1195 * or its opposite.
1197 * If so, the equality is exactly
1199 * e mod d = 0
1201 * Note that in principle we could also accept
1203 * e - d floor(e'/d)
1205 * where e and e' differ by a constant.
1207 static int is_stride_constraint(__isl_keep isl_aff *aff, int pos)
1209 isl_aff *div;
1210 isl_val *c, *d;
1211 int eq;
1213 div = isl_aff_get_div(aff, pos);
1214 c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1215 d = isl_aff_get_denominator_val(div);
1216 eq = isl_val_abs_eq(c, d);
1217 if (eq >= 0 && eq) {
1218 aff = isl_aff_copy(aff);
1219 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1220 div = isl_aff_scale_val(div, d);
1221 if (isl_val_is_pos(c))
1222 div = isl_aff_neg(div);
1223 eq = isl_aff_plain_is_equal(div, aff);
1224 isl_aff_free(aff);
1225 } else
1226 isl_val_free(d);
1227 isl_val_free(c);
1228 isl_aff_free(div);
1230 return eq;
1233 /* Are all coefficients of "aff" (zero or) negative?
1235 static int all_negative_coefficients(__isl_keep isl_aff *aff)
1237 int i, n;
1239 if (!aff)
1240 return 0;
1242 n = isl_aff_dim(aff, isl_dim_param);
1243 for (i = 0; i < n; ++i)
1244 if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)
1245 return 0;
1247 n = isl_aff_dim(aff, isl_dim_in);
1248 for (i = 0; i < n; ++i)
1249 if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)
1250 return 0;
1252 return 1;
1255 /* Give an equality of the form
1257 * aff = e - d floor(e/d) = 0
1259 * or
1261 * aff = -e + d floor(e/d) = 0
1263 * with the integer division "pos" equal to floor(e/d),
1264 * construct the AST expression
1266 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0))
1268 * If e only has negative coefficients, then construct
1270 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(-e), expr(d)), expr(0))
1272 * instead.
1274 static __isl_give isl_ast_expr *extract_stride_constraint(
1275 __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
1277 isl_ctx *ctx;
1278 isl_val *c;
1279 isl_ast_expr *expr, *cst;
1281 if (!aff)
1282 return NULL;
1284 ctx = isl_aff_get_ctx(aff);
1286 c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1287 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1289 if (all_negative_coefficients(aff))
1290 aff = isl_aff_neg(aff);
1292 cst = isl_ast_expr_from_val(isl_val_abs(c));
1293 expr = isl_ast_expr_from_aff(aff, build);
1295 expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst);
1296 cst = isl_ast_expr_alloc_int_si(ctx, 0);
1297 expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst);
1299 return expr;
1302 /* Construct an isl_ast_expr that evaluates the condition "constraint",
1303 * The result is simplified in terms of build->domain.
1305 * We first check if the constraint is an equality of the form
1307 * e - d floor(e/d) = 0
1309 * i.e.,
1311 * e mod d = 0
1313 * If so, we convert it to
1315 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0))
1317 * Otherwise, let the constraint by either "a >= 0" or "a == 0".
1318 * We first extract hidden modulo computations from "a"
1319 * and then collect all the terms with a positive coefficient in cons_pos
1320 * and the terms with a negative coefficient in cons_neg.
1322 * The result is then of the form
1324 * (isl_ast_op_ge, expr(pos), expr(-neg)))
1326 * or
1328 * (isl_ast_op_eq, expr(pos), expr(-neg)))
1330 * However, if the first expression is an integer constant (and the second
1331 * is not), then we swap the two expressions. This ensures that we construct,
1332 * e.g., "i <= 5" rather than "5 >= i".
1334 * Furthermore, is there are no terms with positive coefficients (or no terms
1335 * with negative coefficients), then the constant term is added to "pos"
1336 * (or "neg"), ignoring the sign of the constant term.
1338 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1339 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1341 int i, n;
1342 isl_ctx *ctx;
1343 isl_ast_expr *expr_pos;
1344 isl_ast_expr *expr_neg;
1345 isl_ast_expr *expr;
1346 isl_aff *aff;
1347 int eq;
1348 enum isl_ast_op_type type;
1349 struct isl_ast_add_term_data data;
1351 if (!constraint)
1352 return NULL;
1354 aff = isl_constraint_get_aff(constraint);
1355 eq = isl_constraint_is_equality(constraint);
1356 isl_constraint_free(constraint);
1358 n = isl_aff_dim(aff, isl_dim_div);
1359 if (eq && n > 0)
1360 for (i = 0; i < n; ++i) {
1361 int is_stride;
1362 is_stride = is_stride_constraint(aff, i);
1363 if (is_stride < 0)
1364 goto error;
1365 if (is_stride)
1366 return extract_stride_constraint(aff, i, build);
1369 ctx = isl_aff_get_ctx(aff);
1370 expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
1371 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1373 aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
1375 data.build = build;
1376 data.cst = isl_aff_get_constant_val(aff);
1377 expr_pos = add_signed_terms(expr_pos, aff, 1, &data);
1378 data.cst = isl_val_neg(data.cst);
1379 expr_neg = add_signed_terms(expr_neg, aff, -1, &data);
1380 data.cst = isl_val_neg(data.cst);
1382 if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) {
1383 expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
1384 } else {
1385 data.cst = isl_val_neg(data.cst);
1386 expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
1389 if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
1390 isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
1391 type = eq ? isl_ast_op_eq : isl_ast_op_le;
1392 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
1393 } else {
1394 type = eq ? isl_ast_op_eq : isl_ast_op_ge;
1395 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
1398 isl_aff_free(aff);
1399 return expr;
1400 error:
1401 isl_aff_free(aff);
1402 return NULL;
1405 /* Wrapper around isl_constraint_cmp_last_non_zero for use
1406 * as a callback to isl_constraint_list_sort.
1407 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1408 * apart, then use isl_constraint_plain_cmp instead.
1410 static int cmp_constraint(__isl_keep isl_constraint *a,
1411 __isl_keep isl_constraint *b, void *user)
1413 int cmp;
1415 cmp = isl_constraint_cmp_last_non_zero(a, b);
1416 if (cmp != 0)
1417 return cmp;
1418 return isl_constraint_plain_cmp(a, b);
1421 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1422 * The result is simplified in terms of build->domain.
1424 * If "bset" is not bounded by any constraint, then we contruct
1425 * the expression "1", i.e., "true".
1427 * Otherwise, we sort the constraints, putting constraints that involve
1428 * integer divisions after those that do not, and construct an "and"
1429 * of the ast expressions of the individual constraints.
1431 * Each constraint is added to the generated constraints of the build
1432 * after it has been converted to an AST expression so that it can be used
1433 * to simplify the following constraints. This may change the truth value
1434 * of subsequent constraints that do not satisfy the earlier constraints,
1435 * but this does not affect the outcome of the conjunction as it is
1436 * only true if all the conjuncts are true (no matter in what order
1437 * they are evaluated). In particular, the constraints that do not
1438 * involve integer divisions may serve to simplify some constraints
1439 * that do involve integer divisions.
1441 __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
1442 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1444 int i, n;
1445 isl_constraint *c;
1446 isl_constraint_list *list;
1447 isl_ast_expr *res;
1448 isl_set *set;
1450 list = isl_basic_set_get_constraint_list(bset);
1451 isl_basic_set_free(bset);
1452 list = isl_constraint_list_sort(list, &cmp_constraint, NULL);
1453 if (!list)
1454 return NULL;
1455 n = isl_constraint_list_n_constraint(list);
1456 if (n == 0) {
1457 isl_ctx *ctx = isl_constraint_list_get_ctx(list);
1458 isl_constraint_list_free(list);
1459 return isl_ast_expr_alloc_int_si(ctx, 1);
1462 build = isl_ast_build_copy(build);
1464 c = isl_constraint_list_get_constraint(list, 0);
1465 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1466 set = isl_set_from_basic_set(bset);
1467 res = isl_ast_expr_from_constraint(c, build);
1468 build = isl_ast_build_restrict_generated(build, set);
1470 for (i = 1; i < n; ++i) {
1471 isl_ast_expr *expr;
1473 c = isl_constraint_list_get_constraint(list, i);
1474 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1475 set = isl_set_from_basic_set(bset);
1476 expr = isl_ast_expr_from_constraint(c, build);
1477 build = isl_ast_build_restrict_generated(build, set);
1478 res = isl_ast_expr_and(res, expr);
1481 isl_constraint_list_free(list);
1482 isl_ast_build_free(build);
1483 return res;
1486 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1487 * The result is simplified in terms of build->domain.
1489 * If "set" is an (obviously) empty set, then return the expression "0".
1491 * If there are multiple disjuncts in the description of the set,
1492 * then subsequent disjuncts are simplified in a context where
1493 * the previous disjuncts have been removed from build->domain.
1494 * In particular, constraints that ensure that there is no overlap
1495 * with these previous disjuncts, can be removed.
1496 * This is mostly useful for disjuncts that are only defined by
1497 * a single constraint (relative to the build domain) as the opposite
1498 * of that single constraint can then be removed from the other disjuncts.
1499 * In order not to increase the number of disjuncts in the build domain
1500 * after subtracting the previous disjuncts of "set", the simple hull
1501 * is computed after taking the difference with each of these disjuncts.
1502 * This means that constraints that prevent overlap with a union
1503 * of multiple previous disjuncts are not removed.
1505 * "set" lives in the internal schedule space.
1507 __isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
1508 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1510 int i, n;
1511 isl_basic_set *bset;
1512 isl_basic_set_list *list;
1513 isl_set *domain;
1514 isl_ast_expr *res;
1516 list = isl_set_get_basic_set_list(set);
1517 isl_set_free(set);
1519 if (!list)
1520 return NULL;
1521 n = isl_basic_set_list_n_basic_set(list);
1522 if (n == 0) {
1523 isl_ctx *ctx = isl_ast_build_get_ctx(build);
1524 isl_basic_set_list_free(list);
1525 return isl_ast_expr_from_val(isl_val_zero(ctx));
1528 domain = isl_ast_build_get_domain(build);
1530 bset = isl_basic_set_list_get_basic_set(list, 0);
1531 set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1532 res = isl_ast_build_expr_from_basic_set(build, bset);
1534 for (i = 1; i < n; ++i) {
1535 isl_ast_expr *expr;
1536 isl_set *rest;
1538 rest = isl_set_subtract(isl_set_copy(domain), set);
1539 rest = isl_set_from_basic_set(isl_set_simple_hull(rest));
1540 domain = isl_set_intersect(domain, rest);
1541 bset = isl_basic_set_list_get_basic_set(list, i);
1542 set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1543 bset = isl_basic_set_gist(bset,
1544 isl_set_simple_hull(isl_set_copy(domain)));
1545 expr = isl_ast_build_expr_from_basic_set(build, bset);
1546 res = isl_ast_expr_or(res, expr);
1549 isl_set_free(domain);
1550 isl_set_free(set);
1551 isl_basic_set_list_free(list);
1552 return res;
1555 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1556 * The result is simplified in terms of build->domain.
1558 * If "set" is an (obviously) empty set, then return the expression "0".
1560 * "set" lives in the external schedule space.
1562 * The internal AST expression generation assumes that there are
1563 * no unknown divs, so make sure an explicit representation is available.
1564 * Since the set comes from the outside, it may have constraints that
1565 * are redundant with respect to the build domain. Remove them first.
1567 __isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1568 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1570 if (isl_ast_build_need_schedule_map(build)) {
1571 isl_multi_aff *ma;
1572 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1573 set = isl_set_preimage_multi_aff(set, ma);
1576 set = isl_set_compute_divs(set);
1577 set = isl_ast_build_compute_gist(build, set);
1578 return isl_ast_build_expr_from_set_internal(build, set);
1581 /* State of data about previous pieces in
1582 * isl_ast_build_expr_from_pw_aff_internal.
1584 * isl_state_none: no data about previous pieces
1585 * isl_state_single: data about a single previous piece
1586 * isl_state_min: data represents minimum of several pieces
1587 * isl_state_max: data represents maximum of several pieces
1589 enum isl_from_pw_aff_state {
1590 isl_state_none,
1591 isl_state_single,
1592 isl_state_min,
1593 isl_state_max
1596 /* Internal date structure representing a single piece in the input of
1597 * isl_ast_build_expr_from_pw_aff_internal.
1599 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1600 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1601 * single previous subpiece.
1602 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
1603 * a sequence of several previous subpieces that are equal to the minimum
1604 * of the entries in "aff_list" over the union of "set_list"
1605 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
1606 * a sequence of several previous subpieces that are equal to the maximum
1607 * of the entries in "aff_list" over the union of "set_list"
1609 * During the construction of the pieces, "set" is NULL.
1610 * After the construction, "set" is set to the union of the elements
1611 * in "set_list", at which point "set_list" is set to NULL.
1613 struct isl_from_pw_aff_piece {
1614 enum isl_from_pw_aff_state state;
1615 isl_set *set;
1616 isl_set_list *set_list;
1617 isl_aff_list *aff_list;
1620 /* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1622 * "build" specifies the domain against which the result is simplified.
1623 * "dom" is the domain of the entire isl_pw_aff.
1625 * "n" is the number of pieces constructed already.
1626 * In particular, during the construction of the pieces, "n" points to
1627 * the piece that is being constructed. After the construction of the
1628 * pieces, "n" is set to the total number of pieces.
1629 * "max" is the total number of allocated entries.
1630 * "p" contains the individual pieces.
1632 struct isl_from_pw_aff_data {
1633 isl_ast_build *build;
1634 isl_set *dom;
1636 int n;
1637 int max;
1638 struct isl_from_pw_aff_piece *p;
1641 /* Initialize "data" based on "build" and "pa".
1643 static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data,
1644 __isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa)
1646 int n;
1647 isl_ctx *ctx;
1649 ctx = isl_pw_aff_get_ctx(pa);
1650 n = isl_pw_aff_n_piece(pa);
1651 if (n == 0)
1652 isl_die(ctx, isl_error_invalid,
1653 "cannot handle void expression", return isl_stat_error);
1654 data->max = n;
1655 data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
1656 if (!data->p)
1657 return isl_stat_error;
1658 data->build = build;
1659 data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1660 data->n = 0;
1662 return isl_stat_ok;
1665 /* Free all memory allocated for "data".
1667 static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)
1669 int i;
1671 isl_set_free(data->dom);
1672 if (!data->p)
1673 return;
1675 for (i = 0; i < data->max; ++i) {
1676 isl_set_free(data->p[i].set);
1677 isl_set_list_free(data->p[i].set_list);
1678 isl_aff_list_free(data->p[i].aff_list);
1680 free(data->p);
1683 /* Initialize the current entry of "data" to an unused piece.
1685 static void set_none(struct isl_from_pw_aff_data *data)
1687 data->p[data->n].state = isl_state_none;
1688 data->p[data->n].set_list = NULL;
1689 data->p[data->n].aff_list = NULL;
1692 /* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1694 static void set_single(struct isl_from_pw_aff_data *data,
1695 __isl_take isl_set *set, __isl_take isl_aff *aff)
1697 data->p[data->n].state = isl_state_single;
1698 data->p[data->n].set_list = isl_set_list_from_set(set);
1699 data->p[data->n].aff_list = isl_aff_list_from_aff(aff);
1702 /* Extend the current entry of "data" with "set" and "aff"
1703 * as a minimum expression.
1705 static isl_stat extend_min(struct isl_from_pw_aff_data *data,
1706 __isl_take isl_set *set, __isl_take isl_aff *aff)
1708 int n = data->n;
1709 data->p[n].state = isl_state_min;
1710 data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1711 data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1713 if (!data->p[n].set_list || !data->p[n].aff_list)
1714 return isl_stat_error;
1715 return isl_stat_ok;
1718 /* Extend the current entry of "data" with "set" and "aff"
1719 * as a maximum expression.
1721 static isl_stat extend_max(struct isl_from_pw_aff_data *data,
1722 __isl_take isl_set *set, __isl_take isl_aff *aff)
1724 int n = data->n;
1725 data->p[n].state = isl_state_max;
1726 data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1727 data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1729 if (!data->p[n].set_list || !data->p[n].aff_list)
1730 return isl_stat_error;
1731 return isl_stat_ok;
1734 /* Extend the domain of the current entry of "data", which is assumed
1735 * to contain a single subpiece, with "set". If "replace" is set,
1736 * then also replace the affine function by "aff". Otherwise,
1737 * simply free "aff".
1739 static isl_stat extend_domain(struct isl_from_pw_aff_data *data,
1740 __isl_take isl_set *set, __isl_take isl_aff *aff, int replace)
1742 int n = data->n;
1743 isl_set *set_n;
1745 set_n = isl_set_list_get_set(data->p[n].set_list, 0);
1746 set_n = isl_set_union(set_n, set);
1747 data->p[n].set_list =
1748 isl_set_list_set_set(data->p[n].set_list, 0, set_n);
1750 if (replace)
1751 data->p[n].aff_list =
1752 isl_aff_list_set_aff(data->p[n].aff_list, 0, aff);
1753 else
1754 isl_aff_free(aff);
1756 if (!data->p[n].set_list || !data->p[n].aff_list)
1757 return isl_stat_error;
1758 return isl_stat_ok;
1761 /* Construct an isl_ast_expr from "list" within "build".
1762 * If "state" is isl_state_single, then "list" contains a single entry and
1763 * an isl_ast_expr is constructed for that entry.
1764 * Otherwise a min or max expression is constructed from "list"
1765 * depending on "state".
1767 static __isl_give isl_ast_expr *ast_expr_from_aff_list(
1768 __isl_take isl_aff_list *list, enum isl_from_pw_aff_state state,
1769 __isl_keep isl_ast_build *build)
1771 int i, n;
1772 isl_aff *aff;
1773 isl_ast_expr *expr;
1774 enum isl_ast_op_type op_type;
1776 if (state == isl_state_single) {
1777 aff = isl_aff_list_get_aff(list, 0);
1778 isl_aff_list_free(list);
1779 return isl_ast_expr_from_aff(aff, build);
1781 n = isl_aff_list_n_aff(list);
1782 op_type = state == isl_state_min ? isl_ast_op_min : isl_ast_op_max;
1783 expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n);
1784 if (!expr)
1785 goto error;
1787 for (i = 0; i < n; ++i) {
1788 isl_ast_expr *expr_i;
1790 aff = isl_aff_list_get_aff(list, i);
1791 expr_i = isl_ast_expr_from_aff(aff, build);
1792 if (!expr_i)
1793 goto error;
1794 expr->u.op.args[i] = expr_i;
1797 isl_aff_list_free(list);
1798 return expr;
1799 error:
1800 isl_aff_list_free(list);
1801 isl_ast_expr_free(expr);
1802 return NULL;
1805 /* Extend the expression in "next" to take into account
1806 * the piece at position "pos" in "data", allowing for a further extension
1807 * for the next piece(s).
1808 * In particular, "next" is set to a select operation that selects
1809 * an isl_ast_expr corresponding to data->aff_list on data->set and
1810 * to an expression that will be filled in by later calls.
1811 * Return a pointer to this location.
1812 * Afterwards, the state of "data" is set to isl_state_none.
1814 * The constraints of data->set are added to the generated
1815 * constraints of the build such that they can be exploited to simplify
1816 * the AST expression constructed from data->aff_list.
1818 static isl_ast_expr **add_intermediate_piece(struct isl_from_pw_aff_data *data,
1819 int pos, isl_ast_expr **next)
1821 isl_ctx *ctx;
1822 isl_ast_build *build;
1823 isl_ast_expr *ternary, *arg;
1824 isl_set *set, *gist;
1826 set = data->p[pos].set;
1827 data->p[pos].set = NULL;
1828 ctx = isl_ast_build_get_ctx(data->build);
1829 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
1830 gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));
1831 arg = isl_ast_build_expr_from_set_internal(data->build, gist);
1832 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
1833 build = isl_ast_build_copy(data->build);
1834 build = isl_ast_build_restrict_generated(build, set);
1835 arg = ast_expr_from_aff_list(data->p[pos].aff_list,
1836 data->p[pos].state, build);
1837 data->p[pos].aff_list = NULL;
1838 isl_ast_build_free(build);
1839 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
1840 data->p[pos].state = isl_state_none;
1841 if (!ternary)
1842 return NULL;
1844 *next = ternary;
1845 return &ternary->u.op.args[2];
1848 /* Extend the expression in "next" to take into account
1849 * the final piece, located at position "pos" in "data".
1850 * In particular, "next" is set to evaluate data->aff_list
1851 * and the domain is ignored.
1852 * Return isl_stat_ok on success and isl_stat_error on failure.
1854 * The constraints of data->set are however added to the generated
1855 * constraints of the build such that they can be exploited to simplify
1856 * the AST expression constructed from data->aff_list.
1858 static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,
1859 int pos, isl_ast_expr **next)
1861 isl_ast_build *build;
1863 if (data->p[pos].state == isl_state_none)
1864 isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1865 "cannot handle void expression", return isl_stat_error);
1867 build = isl_ast_build_copy(data->build);
1868 build = isl_ast_build_restrict_generated(build, data->p[pos].set);
1869 data->p[pos].set = NULL;
1870 *next = ast_expr_from_aff_list(data->p[pos].aff_list,
1871 data->p[pos].state, build);
1872 data->p[pos].aff_list = NULL;
1873 isl_ast_build_free(build);
1874 data->p[pos].state = isl_state_none;
1875 if (!*next)
1876 return isl_stat_error;
1878 return isl_stat_ok;
1881 /* Return -1 if the piece "p1" should be sorted before "p2"
1882 * and 1 if it should be sorted after "p2".
1883 * Return 0 if they do not need to be sorted in a specific order.
1885 * Pieces are sorted according to the number of disjuncts
1886 * in their domains.
1888 static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)
1890 const struct isl_from_pw_aff_piece *piece1 = p1;
1891 const struct isl_from_pw_aff_piece *piece2 = p2;
1892 int n1, n2;
1894 n1 = isl_set_n_basic_set(piece1->set);
1895 n2 = isl_set_n_basic_set(piece2->set);
1897 return n1 - n2;
1900 /* Construct an isl_ast_expr from the pieces in "data".
1901 * Return the result or NULL on failure.
1903 * When this function is called, data->n points to the current piece.
1904 * If this is an effective piece, then first increment data->n such
1905 * that data->n contains the number of pieces.
1906 * The "set_list" fields are subsequently replaced by the corresponding
1907 * "set" fields, after which the pieces are sorted according to
1908 * the number of disjuncts in these "set" fields.
1910 * Construct intermediate AST expressions for the initial pieces and
1911 * finish off with the final pieces.
1913 static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)
1915 int i;
1916 isl_ast_expr *res = NULL;
1917 isl_ast_expr **next = &res;
1919 if (data->p[data->n].state != isl_state_none)
1920 data->n++;
1921 if (data->n == 0)
1922 isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1923 "cannot handle void expression", return NULL);
1925 for (i = 0; i < data->n; ++i) {
1926 data->p[i].set = isl_set_list_union(data->p[i].set_list);
1927 if (data->p[i].state != isl_state_single)
1928 data->p[i].set = isl_set_coalesce(data->p[i].set);
1929 data->p[i].set_list = NULL;
1932 if (isl_sort(data->p, data->n, sizeof(data->p[0]),
1933 &sort_pieces_cmp, NULL) < 0)
1934 return isl_ast_expr_free(res);
1936 for (i = 0; i + 1 < data->n; ++i) {
1937 next = add_intermediate_piece(data, i, next);
1938 if (!next)
1939 return isl_ast_expr_free(res);
1942 if (add_last_piece(data, data->n - 1, next) < 0)
1943 return isl_ast_expr_free(res);
1945 return res;
1948 /* Is the domain of the current entry of "data", which is assumed
1949 * to contain a single subpiece, a subset of "set"?
1951 static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
1952 __isl_keep isl_set *set)
1954 isl_bool subset;
1955 isl_set *set_n;
1957 set_n = isl_set_list_get_set(data->p[data->n].set_list, 0);
1958 subset = isl_set_is_subset(set_n, set);
1959 isl_set_free(set_n);
1961 return subset;
1964 /* Is "aff" a rational expression, i.e., does it have a denominator
1965 * different from one?
1967 static isl_bool aff_is_rational(__isl_keep isl_aff *aff)
1969 isl_bool rational;
1970 isl_val *den;
1972 den = isl_aff_get_denominator_val(aff);
1973 rational = isl_bool_not(isl_val_is_one(den));
1974 isl_val_free(den);
1976 return rational;
1979 /* Does "list" consist of a single rational affine expression?
1981 static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)
1983 isl_bool rational;
1984 isl_aff *aff;
1986 if (isl_aff_list_n_aff(list) != 1)
1987 return isl_bool_false;
1988 aff = isl_aff_list_get_aff(list, 0);
1989 rational = aff_is_rational(aff);
1990 isl_aff_free(aff);
1992 return rational;
1995 /* Can the list of subpieces in the last piece of "data" be extended with
1996 * "set" and "aff" based on "test"?
1997 * In particular, is it the case for each entry (set_i, aff_i) that
1999 * test(aff, aff_i) holds on set_i, and
2000 * test(aff_i, aff) holds on set?
2002 * "test" returns the set of elements where the tests holds, meaning
2003 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2005 * This function is used to detect min/max expressions.
2006 * If the ast_build_detect_min_max option is turned off, then
2007 * do not even try and perform any detection and return false instead.
2009 * Rational affine expressions are not considered for min/max expressions
2010 * since the combined expression will be defined on the union of the domains,
2011 * while a rational expression may only yield integer values
2012 * on its own definition domain.
2014 static isl_bool extends(struct isl_from_pw_aff_data *data,
2015 __isl_keep isl_set *set, __isl_keep isl_aff *aff,
2016 __isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1,
2017 __isl_take isl_aff *aff2))
2019 int i, n;
2020 isl_bool is_rational;
2021 isl_ctx *ctx;
2022 isl_set *dom;
2024 is_rational = aff_is_rational(aff);
2025 if (is_rational >= 0 && !is_rational)
2026 is_rational = is_single_rational_aff(data->p[data->n].aff_list);
2027 if (is_rational < 0 || is_rational)
2028 return isl_bool_not(is_rational);
2030 ctx = isl_ast_build_get_ctx(data->build);
2031 if (!isl_options_get_ast_build_detect_min_max(ctx))
2032 return isl_bool_false;
2034 dom = isl_ast_build_get_domain(data->build);
2035 set = isl_set_intersect(dom, isl_set_copy(set));
2037 n = isl_set_list_n_set(data->p[data->n].set_list);
2038 for (i = 0; i < n ; ++i) {
2039 isl_aff *aff_i;
2040 isl_set *valid;
2041 isl_set *dom, *required;
2042 isl_bool is_valid;
2044 aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2045 valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i));
2046 required = isl_set_list_get_set(data->p[data->n].set_list, i);
2047 dom = isl_ast_build_get_domain(data->build);
2048 required = isl_set_intersect(dom, required);
2049 is_valid = isl_set_is_subset(required, valid);
2050 isl_set_free(required);
2051 isl_set_free(valid);
2052 if (is_valid < 0 || !is_valid) {
2053 isl_set_free(set);
2054 return is_valid;
2057 aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2058 valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff)));
2059 is_valid = isl_set_is_subset(set, valid);
2060 isl_set_free(valid);
2061 if (is_valid < 0 || !is_valid) {
2062 isl_set_free(set);
2063 return is_valid;
2067 isl_set_free(set);
2068 return isl_bool_true;
2071 /* Can the list of pieces in "data" be extended with "set" and "aff"
2072 * to form/preserve a minimum expression?
2073 * In particular, is it the case for each entry (set_i, aff_i) that
2075 * aff >= aff_i on set_i, and
2076 * aff_i >= aff on set?
2078 static isl_bool extends_min(struct isl_from_pw_aff_data *data,
2079 __isl_keep isl_set *set, __isl_keep isl_aff *aff)
2081 return extends(data, set, aff, &isl_aff_ge_basic_set);
2084 /* Can the list of pieces in "data" be extended with "set" and "aff"
2085 * to form/preserve a maximum expression?
2086 * In particular, is it the case for each entry (set_i, aff_i) that
2088 * aff <= aff_i on set_i, and
2089 * aff_i <= aff on set?
2091 static isl_bool extends_max(struct isl_from_pw_aff_data *data,
2092 __isl_keep isl_set *set, __isl_keep isl_aff *aff)
2094 return extends(data, set, aff, &isl_aff_le_basic_set);
2097 /* This function is called during the construction of an isl_ast_expr
2098 * that evaluates an isl_pw_aff.
2099 * If the last piece of "data" contains a single subpiece and
2100 * if its affine function is equal to "aff" on a part of the domain
2101 * that includes either "set" or the domain of that single subpiece,
2102 * then extend the domain of that single subpiece with "set".
2103 * If it was the original domain of the single subpiece where
2104 * the two affine functions are equal, then also replace
2105 * the affine function of the single subpiece by "aff".
2106 * If the last piece of "data" contains either a single subpiece
2107 * or a minimum, then check if this minimum expression can be extended
2108 * with (set, aff).
2109 * If so, extend the sequence and return.
2110 * Perform the same operation for maximum expressions.
2111 * If no such extension can be performed, then move to the next piece
2112 * in "data" (if the current piece contains any data), and then store
2113 * the current subpiece in the current piece of "data" for later handling.
2115 static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,
2116 __isl_take isl_aff *aff, void *user)
2118 struct isl_from_pw_aff_data *data = user;
2119 isl_bool test;
2120 enum isl_from_pw_aff_state state;
2122 state = data->p[data->n].state;
2123 if (state == isl_state_single) {
2124 isl_aff *aff0;
2125 isl_set *eq;
2126 isl_bool subset1, subset2 = isl_bool_false;
2127 aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0);
2128 eq = isl_aff_eq_set(isl_aff_copy(aff), aff0);
2129 subset1 = isl_set_is_subset(set, eq);
2130 if (subset1 >= 0 && !subset1)
2131 subset2 = single_is_subset(data, eq);
2132 isl_set_free(eq);
2133 if (subset1 < 0 || subset2 < 0)
2134 goto error;
2135 if (subset1)
2136 return extend_domain(data, set, aff, 0);
2137 if (subset2)
2138 return extend_domain(data, set, aff, 1);
2140 if (state == isl_state_single || state == isl_state_min) {
2141 test = extends_min(data, set, aff);
2142 if (test < 0)
2143 goto error;
2144 if (test)
2145 return extend_min(data, set, aff);
2147 if (state == isl_state_single || state == isl_state_max) {
2148 test = extends_max(data, set, aff);
2149 if (test < 0)
2150 goto error;
2151 if (test)
2152 return extend_max(data, set, aff);
2154 if (state != isl_state_none)
2155 data->n++;
2156 set_single(data, set, aff);
2158 return isl_stat_ok;
2159 error:
2160 isl_set_free(set);
2161 isl_aff_free(aff);
2162 return isl_stat_error;
2165 /* Construct an isl_ast_expr that evaluates "pa".
2166 * The result is simplified in terms of build->domain.
2168 * The domain of "pa" lives in the internal schedule space.
2170 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
2171 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2173 struct isl_from_pw_aff_data data = { NULL };
2174 isl_ast_expr *res = NULL;
2176 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
2177 pa = isl_pw_aff_coalesce(pa);
2178 if (!pa)
2179 return NULL;
2181 if (isl_from_pw_aff_data_init(&data, build, pa) < 0)
2182 goto error;
2183 set_none(&data);
2185 if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0)
2186 res = build_pieces(&data);
2188 isl_pw_aff_free(pa);
2189 isl_from_pw_aff_data_clear(&data);
2190 return res;
2191 error:
2192 isl_pw_aff_free(pa);
2193 isl_from_pw_aff_data_clear(&data);
2194 return NULL;
2197 /* Construct an isl_ast_expr that evaluates "pa".
2198 * The result is simplified in terms of build->domain.
2200 * The domain of "pa" lives in the external schedule space.
2202 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
2203 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2205 isl_ast_expr *expr;
2207 if (isl_ast_build_need_schedule_map(build)) {
2208 isl_multi_aff *ma;
2209 ma = isl_ast_build_get_schedule_map_multi_aff(build);
2210 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
2212 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2213 return expr;
2216 /* Set the ids of the input dimensions of "mpa" to the iterator ids
2217 * of "build".
2219 * The domain of "mpa" is assumed to live in the internal schedule domain.
2221 static __isl_give isl_multi_pw_aff *set_iterator_names(
2222 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2224 int i, n;
2226 n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
2227 for (i = 0; i < n; ++i) {
2228 isl_id *id;
2230 id = isl_ast_build_get_iterator_id(build, i);
2231 mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
2234 return mpa;
2237 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2238 * the remaining arguments derived from "mpa".
2239 * That is, construct a call or access expression that calls/accesses "arg0"
2240 * with arguments/indices specified by "mpa".
2242 static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
2243 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2244 __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
2246 int i, n;
2247 isl_ctx *ctx;
2248 isl_ast_expr *expr;
2250 ctx = isl_ast_build_get_ctx(build);
2252 n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
2253 expr = isl_ast_expr_alloc_op(ctx, type, 1 + n);
2254 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
2255 for (i = 0; i < n; ++i) {
2256 isl_pw_aff *pa;
2257 isl_ast_expr *arg;
2259 pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
2260 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2261 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
2264 isl_multi_pw_aff_free(mpa);
2265 return expr;
2268 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2269 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2270 __isl_take isl_multi_pw_aff *mpa);
2272 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
2273 * The range of "mpa" is assumed to be wrapped relation.
2274 * The domain of this wrapped relation specifies the structure being
2275 * accessed, while the range of this wrapped relation spacifies the
2276 * member of the structure being accessed.
2278 * The domain of "mpa" is assumed to live in the internal schedule domain.
2280 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
2281 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2283 isl_id *id;
2284 isl_multi_pw_aff *domain;
2285 isl_ast_expr *domain_expr, *expr;
2286 enum isl_ast_op_type type = isl_ast_op_access;
2288 domain = isl_multi_pw_aff_copy(mpa);
2289 domain = isl_multi_pw_aff_range_factor_domain(domain);
2290 domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
2291 type, domain);
2292 mpa = isl_multi_pw_aff_range_factor_range(mpa);
2293 if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
2294 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2295 "missing field name", goto error);
2296 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
2297 expr = isl_ast_expr_from_id(id);
2298 expr = isl_ast_expr_alloc_binary(isl_ast_op_member, domain_expr, expr);
2299 return isl_ast_build_with_arguments(build, type, expr, mpa);
2300 error:
2301 isl_multi_pw_aff_free(mpa);
2302 return NULL;
2305 /* Construct an isl_ast_expr of type "type" that calls or accesses
2306 * the element specified by "mpa".
2307 * The first argument is obtained from the output tuple name.
2308 * The remaining arguments are given by the piecewise affine expressions.
2310 * If the range of "mpa" is a mapped relation, then we assume it
2311 * represents an access to a member of a structure.
2313 * The domain of "mpa" is assumed to live in the internal schedule domain.
2315 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2316 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2317 __isl_take isl_multi_pw_aff *mpa)
2319 isl_ctx *ctx;
2320 isl_id *id;
2321 isl_ast_expr *expr;
2323 if (!mpa)
2324 goto error;
2326 if (type == isl_ast_op_access &&
2327 isl_multi_pw_aff_range_is_wrapping(mpa))
2328 return isl_ast_build_from_multi_pw_aff_member(build, mpa);
2330 mpa = set_iterator_names(build, mpa);
2331 if (!build || !mpa)
2332 goto error;
2334 ctx = isl_ast_build_get_ctx(build);
2336 if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
2337 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
2338 else
2339 id = isl_id_alloc(ctx, "", NULL);
2341 expr = isl_ast_expr_from_id(id);
2342 return isl_ast_build_with_arguments(build, type, expr, mpa);
2343 error:
2344 isl_multi_pw_aff_free(mpa);
2345 return NULL;
2348 /* Construct an isl_ast_expr of type "type" that calls or accesses
2349 * the element specified by "pma".
2350 * The first argument is obtained from the output tuple name.
2351 * The remaining arguments are given by the piecewise affine expressions.
2353 * The domain of "pma" is assumed to live in the internal schedule domain.
2355 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
2356 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2357 __isl_take isl_pw_multi_aff *pma)
2359 isl_multi_pw_aff *mpa;
2361 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2362 return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2365 /* Construct an isl_ast_expr of type "type" that calls or accesses
2366 * the element specified by "mpa".
2367 * The first argument is obtained from the output tuple name.
2368 * The remaining arguments are given by the piecewise affine expressions.
2370 * The domain of "mpa" is assumed to live in the external schedule domain.
2372 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
2373 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2374 __isl_take isl_multi_pw_aff *mpa)
2376 int is_domain;
2377 isl_ast_expr *expr;
2378 isl_space *space_build, *space_mpa;
2380 space_build = isl_ast_build_get_space(build, 0);
2381 space_mpa = isl_multi_pw_aff_get_space(mpa);
2382 is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,
2383 space_mpa, isl_dim_in);
2384 isl_space_free(space_build);
2385 isl_space_free(space_mpa);
2386 if (is_domain < 0)
2387 goto error;
2388 if (!is_domain)
2389 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2390 "spaces don't match", goto error);
2392 if (isl_ast_build_need_schedule_map(build)) {
2393 isl_multi_aff *ma;
2394 ma = isl_ast_build_get_schedule_map_multi_aff(build);
2395 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
2398 expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2399 return expr;
2400 error:
2401 isl_multi_pw_aff_free(mpa);
2402 return NULL;
2405 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2406 * The name of the function is obtained from the output tuple name.
2407 * The arguments are given by the piecewise affine expressions.
2409 * The domain of "mpa" is assumed to live in the external schedule domain.
2411 __isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
2412 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2414 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_call, mpa);
2417 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2418 * The name of the array is obtained from the output tuple name.
2419 * The index expressions are given by the piecewise affine expressions.
2421 * The domain of "mpa" is assumed to live in the external schedule domain.
2423 __isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
2424 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2426 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_access, mpa);
2429 /* Construct an isl_ast_expr of type "type" that calls or accesses
2430 * the element specified by "pma".
2431 * The first argument is obtained from the output tuple name.
2432 * The remaining arguments are given by the piecewise affine expressions.
2434 * The domain of "pma" is assumed to live in the external schedule domain.
2436 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
2437 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2438 __isl_take isl_pw_multi_aff *pma)
2440 isl_multi_pw_aff *mpa;
2442 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2443 return isl_ast_build_from_multi_pw_aff(build, type, mpa);
2446 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
2447 * The name of the function is obtained from the output tuple name.
2448 * The arguments are given by the piecewise affine expressions.
2450 * The domain of "pma" is assumed to live in the external schedule domain.
2452 __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
2453 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2455 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_call, pma);
2458 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
2459 * The name of the array is obtained from the output tuple name.
2460 * The index expressions are given by the piecewise affine expressions.
2462 * The domain of "pma" is assumed to live in the external schedule domain.
2464 __isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
2465 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2467 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma);
2470 /* Construct an isl_ast_expr that calls the domain element
2471 * specified by "executed".
2473 * "executed" is assumed to be single-valued, with a domain that lives
2474 * in the internal schedule space.
2476 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
2477 __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
2479 isl_pw_multi_aff *iteration;
2480 isl_ast_expr *expr;
2482 iteration = isl_pw_multi_aff_from_map(executed);
2483 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
2484 iteration = isl_pw_multi_aff_intersect_domain(iteration,
2485 isl_ast_build_get_domain(build));
2486 expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call,
2487 iteration);
2488 return isl_ast_node_alloc_user(expr);