isl_aff_project_domain_on_params: extract out drop_domain
[isl.git] / isl_ast_build_expr.c
blobddac02146843f7b5ff02e3a6645d8e90d59727d1
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/id.h>
14 #include <isl/space.h>
15 #include <isl/constraint.h>
16 #include <isl/ilp.h>
17 #include <isl/val.h>
18 #include <isl_ast_build_expr.h>
19 #include <isl_ast_private.h>
20 #include <isl_ast_build_private.h>
21 #include <isl_sort.h>
23 /* Compute the "opposite" of the (numerator of the) argument of a div
24 * with denominator "d".
26 * In particular, compute
28 * -aff + (d - 1)
30 static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
31 __isl_take isl_val *d)
33 aff = isl_aff_neg(aff);
34 aff = isl_aff_add_constant_val(aff, d);
35 aff = isl_aff_add_constant_si(aff, -1);
37 return aff;
40 /* Internal data structure used inside isl_ast_expr_add_term.
41 * The domain of "build" is used to simplify the expressions.
42 * "build" needs to be set by the caller of isl_ast_expr_add_term.
43 * "cst" is the constant term of the expression in which the added term
44 * appears. It may be modified by isl_ast_expr_add_term.
46 * "v" is the coefficient of the term that is being constructed and
47 * is set internally by isl_ast_expr_add_term.
49 struct isl_ast_add_term_data {
50 isl_ast_build *build;
51 isl_val *cst;
52 isl_val *v;
55 /* Given the numerator "aff" of the argument of an integer division
56 * with denominator "d", check if it can be made non-negative over
57 * data->build->domain by stealing part of the constant term of
58 * the expression in which the integer division appears.
60 * In particular, the outer expression is of the form
62 * v * floor(aff/d) + cst
64 * We already know that "aff" itself may attain negative values.
65 * Here we check if aff + d*floor(cst/v) is non-negative, such
66 * that we could rewrite the expression to
68 * v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
70 * Note that aff + d*floor(cst/v) can only possibly be non-negative
71 * if data->cst and data->v have the same sign.
72 * Similarly, if floor(cst/v) is zero, then there is no point in
73 * checking again.
75 static int is_non_neg_after_stealing(__isl_keep isl_aff *aff,
76 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
78 isl_aff *shifted;
79 isl_val *shift;
80 int is_zero;
81 int non_neg;
83 if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))
84 return 0;
86 shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));
87 shift = isl_val_floor(shift);
88 is_zero = isl_val_is_zero(shift);
89 if (is_zero < 0 || is_zero) {
90 isl_val_free(shift);
91 return is_zero < 0 ? -1 : 0;
93 shift = isl_val_mul(shift, isl_val_copy(d));
94 shifted = isl_aff_copy(aff);
95 shifted = isl_aff_add_constant_val(shifted, shift);
96 non_neg = isl_ast_build_aff_is_nonneg(data->build, shifted);
97 isl_aff_free(shifted);
99 return non_neg;
102 /* Given the numerator "aff' of the argument of an integer division
103 * with denominator "d", steal part of the constant term of
104 * the expression in which the integer division appears to make it
105 * non-negative over data->build->domain.
107 * In particular, the outer expression is of the form
109 * v * floor(aff/d) + cst
111 * We know that "aff" itself may attain negative values,
112 * but that aff + d*floor(cst/v) is non-negative.
113 * Find the minimal positive value that we need to add to "aff"
114 * to make it positive and adjust data->cst accordingly.
115 * That is, compute the minimal value "m" of "aff" over
116 * data->build->domain and take
118 * s = ceil(m/d)
120 * such that
122 * aff + d * s >= 0
124 * and rewrite the expression to
126 * v * floor((aff + s*d)/d) + (cst - v*s)
128 static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
129 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
131 isl_set *domain;
132 isl_val *shift, *t;
134 domain = isl_ast_build_get_domain(data->build);
135 shift = isl_set_min_val(domain, aff);
136 isl_set_free(domain);
138 shift = isl_val_neg(shift);
139 shift = isl_val_div(shift, isl_val_copy(d));
140 shift = isl_val_ceil(shift);
142 t = isl_val_copy(shift);
143 t = isl_val_mul(t, isl_val_copy(data->v));
144 data->cst = isl_val_sub(data->cst, t);
146 shift = isl_val_mul(shift, isl_val_copy(d));
147 return isl_aff_add_constant_val(aff, shift);
150 /* Create an isl_ast_expr evaluating the div at position "pos" in "ls".
151 * The result is simplified in terms of data->build->domain.
152 * This function may change (the sign of) data->v.
154 * "ls" is known to be non-NULL.
156 * Let the div be of the form floor(e/d).
157 * If the ast_build_prefer_pdiv option is set then we check if "e"
158 * is non-negative, so that we can generate
160 * (pdiv_q, expr(e), expr(d))
162 * instead of
164 * (fdiv_q, expr(e), expr(d))
166 * If the ast_build_prefer_pdiv option is set and
167 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
168 * If so, we can rewrite
170 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
172 * and still use pdiv_q, while changing the sign of data->v.
174 * Otherwise, we check if
176 * e + d*floor(cst/v)
178 * is non-negative and if so, replace floor(e/d) by
180 * floor((e + s*d)/d) - s
182 * with s the minimal shift that makes the argument non-negative.
184 static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,
185 __isl_keep isl_local_space *ls, int pos)
187 isl_ctx *ctx = isl_local_space_get_ctx(ls);
188 isl_aff *aff;
189 isl_ast_expr *num, *den;
190 isl_val *d;
191 enum isl_ast_op_type type;
193 aff = isl_local_space_get_div(ls, pos);
194 d = isl_aff_get_denominator_val(aff);
195 aff = isl_aff_scale_val(aff, isl_val_copy(d));
196 den = isl_ast_expr_from_val(isl_val_copy(d));
198 type = isl_ast_op_fdiv_q;
199 if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
200 int non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);
201 if (non_neg >= 0 && !non_neg) {
202 isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),
203 isl_val_copy(d));
204 non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);
205 if (non_neg >= 0 && non_neg) {
206 data->v = isl_val_neg(data->v);
207 isl_aff_free(aff);
208 aff = opp;
209 } else
210 isl_aff_free(opp);
212 if (non_neg >= 0 && !non_neg) {
213 non_neg = is_non_neg_after_stealing(aff, d, data);
214 if (non_neg >= 0 && non_neg)
215 aff = steal_from_cst(aff, d, data);
217 if (non_neg < 0)
218 aff = isl_aff_free(aff);
219 else if (non_neg)
220 type = isl_ast_op_pdiv_q;
223 isl_val_free(d);
224 num = isl_ast_expr_from_aff(aff, data->build);
225 return isl_ast_expr_alloc_binary(type, num, den);
228 /* Create an isl_ast_expr evaluating the specified dimension of "ls".
229 * The result is simplified in terms of data->build->domain.
230 * This function may change (the sign of) data->v.
232 * The isl_ast_expr is constructed based on the type of the dimension.
233 * - divs are constructed by var_div
234 * - set variables are constructed from the iterator isl_ids in data->build
235 * - parameters are constructed from the isl_ids in "ls"
237 static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
238 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos)
240 isl_ctx *ctx = isl_local_space_get_ctx(ls);
241 isl_id *id;
243 if (type == isl_dim_div)
244 return var_div(data, ls, pos);
246 if (type == isl_dim_set) {
247 id = isl_ast_build_get_iterator_id(data->build, pos);
248 return isl_ast_expr_from_id(id);
251 if (!isl_local_space_has_dim_id(ls, type, pos))
252 isl_die(ctx, isl_error_internal, "unnamed dimension",
253 return NULL);
254 id = isl_local_space_get_dim_id(ls, type, pos);
255 return isl_ast_expr_from_id(id);
258 /* Does "expr" represent the zero integer?
260 static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
262 if (!expr)
263 return -1;
264 if (expr->type != isl_ast_expr_int)
265 return 0;
266 return isl_val_is_zero(expr->u.v);
269 /* Create an expression representing the sum of "expr1" and "expr2",
270 * provided neither of the two expressions is identically zero.
272 static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
273 __isl_take isl_ast_expr *expr2)
275 if (!expr1 || !expr2)
276 goto error;
278 if (ast_expr_is_zero(expr1)) {
279 isl_ast_expr_free(expr1);
280 return expr2;
283 if (ast_expr_is_zero(expr2)) {
284 isl_ast_expr_free(expr2);
285 return expr1;
288 return isl_ast_expr_add(expr1, expr2);
289 error:
290 isl_ast_expr_free(expr1);
291 isl_ast_expr_free(expr2);
292 return NULL;
295 /* Subtract expr2 from expr1.
297 * If expr2 is zero, we simply return expr1.
298 * If expr1 is zero, we return
300 * (isl_ast_op_minus, expr2)
302 * Otherwise, we return
304 * (isl_ast_op_sub, expr1, expr2)
306 static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
307 __isl_take isl_ast_expr *expr2)
309 if (!expr1 || !expr2)
310 goto error;
312 if (ast_expr_is_zero(expr2)) {
313 isl_ast_expr_free(expr2);
314 return expr1;
317 if (ast_expr_is_zero(expr1)) {
318 isl_ast_expr_free(expr1);
319 return isl_ast_expr_neg(expr2);
322 return isl_ast_expr_sub(expr1, expr2);
323 error:
324 isl_ast_expr_free(expr1);
325 isl_ast_expr_free(expr2);
326 return NULL;
329 /* Return an isl_ast_expr that represents
331 * v * (aff mod d)
333 * v is assumed to be non-negative.
334 * The result is simplified in terms of build->domain.
336 static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
337 __isl_keep isl_aff *aff, __isl_keep isl_val *d,
338 __isl_keep isl_ast_build *build)
340 isl_ast_expr *expr;
341 isl_ast_expr *c;
343 if (!aff)
344 return NULL;
346 expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
348 c = isl_ast_expr_from_val(isl_val_copy(d));
349 expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
351 if (!isl_val_is_one(v)) {
352 c = isl_ast_expr_from_val(isl_val_copy(v));
353 expr = isl_ast_expr_mul(c, expr);
356 return expr;
359 /* Create an isl_ast_expr that scales "expr" by "v".
361 * If v is 1, we simply return expr.
362 * If v is -1, we return
364 * (isl_ast_op_minus, expr)
366 * Otherwise, we return
368 * (isl_ast_op_mul, expr(v), expr)
370 static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
371 __isl_take isl_val *v)
373 isl_ast_expr *c;
375 if (!expr || !v)
376 goto error;
377 if (isl_val_is_one(v)) {
378 isl_val_free(v);
379 return expr;
382 if (isl_val_is_negone(v)) {
383 isl_val_free(v);
384 expr = isl_ast_expr_neg(expr);
385 } else {
386 c = isl_ast_expr_from_val(v);
387 expr = isl_ast_expr_mul(c, expr);
390 return expr;
391 error:
392 isl_val_free(v);
393 isl_ast_expr_free(expr);
394 return NULL;
397 /* Add an expression for "*v" times the specified dimension of "ls"
398 * to expr.
399 * If the dimension is an integer division, then this function
400 * may modify data->cst in order to make the numerator non-negative.
401 * The result is simplified in terms of data->build->domain.
403 * Let e be the expression for the specified dimension,
404 * multiplied by the absolute value of "*v".
405 * If "*v" is negative, we create
407 * (isl_ast_op_sub, expr, e)
409 * except when expr is trivially zero, in which case we create
411 * (isl_ast_op_minus, e)
413 * instead.
415 * If "*v" is positive, we simply create
417 * (isl_ast_op_add, expr, e)
420 static __isl_give isl_ast_expr *isl_ast_expr_add_term(
421 __isl_take isl_ast_expr *expr,
422 __isl_keep isl_local_space *ls, enum isl_dim_type type, int pos,
423 __isl_take isl_val *v, struct isl_ast_add_term_data *data)
425 isl_ast_expr *term;
427 if (!expr)
428 return NULL;
430 data->v = v;
431 term = var(data, ls, type, pos);
432 v = data->v;
434 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
435 v = isl_val_neg(v);
436 term = scale(term, v);
437 return ast_expr_sub(expr, term);
438 } else {
439 term = scale(term, v);
440 return ast_expr_add(expr, term);
444 /* Add an expression for "v" to expr.
446 static __isl_give isl_ast_expr *isl_ast_expr_add_int(
447 __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
449 isl_ast_expr *expr_int;
451 if (!expr || !v)
452 goto error;
454 if (isl_val_is_zero(v)) {
455 isl_val_free(v);
456 return expr;
459 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
460 v = isl_val_neg(v);
461 expr_int = isl_ast_expr_from_val(v);
462 return ast_expr_sub(expr, expr_int);
463 } else {
464 expr_int = isl_ast_expr_from_val(v);
465 return ast_expr_add(expr, expr_int);
467 error:
468 isl_ast_expr_free(expr);
469 isl_val_free(v);
470 return NULL;
473 /* Internal data structure used inside extract_modulos.
475 * If any modulo expressions are detected in "aff", then the
476 * expression is removed from "aff" and added to either "pos" or "neg"
477 * depending on the sign of the coefficient of the modulo expression
478 * inside "aff".
480 * "add" is an expression that needs to be added to "aff" at the end of
481 * the computation. It is NULL as long as no modulos have been extracted.
483 * "i" is the position in "aff" of the div under investigation
484 * "v" is the coefficient in "aff" of the div
485 * "div" is the argument of the div, with the denominator removed
486 * "d" is the original denominator of the argument of the div
488 * "nonneg" is an affine expression that is non-negative over "build"
489 * and that can be used to extract a modulo expression from "div".
490 * In particular, if "sign" is 1, then the coefficients of "nonneg"
491 * are equal to those of "div" modulo "d". If "sign" is -1, then
492 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
493 * If "sign" is 0, then no such affine expression has been found (yet).
495 struct isl_extract_mod_data {
496 isl_ast_build *build;
497 isl_aff *aff;
499 isl_ast_expr *pos;
500 isl_ast_expr *neg;
502 isl_aff *add;
504 int i;
505 isl_val *v;
506 isl_val *d;
507 isl_aff *div;
509 isl_aff *nonneg;
510 int sign;
513 /* Given that data->v * div_i in data->aff is equal to
515 * f * (term - (arg mod d))
517 * with data->d * f = data->v, add
519 * f * term
521 * to data->add and
523 * abs(f) * (arg mod d)
525 * to data->neg or data->pos depending on the sign of -f.
527 static int extract_term_and_mod(struct isl_extract_mod_data *data,
528 __isl_take isl_aff *term, __isl_take isl_aff *arg)
530 isl_ast_expr *expr;
531 int s;
533 data->v = isl_val_div(data->v, isl_val_copy(data->d));
534 s = isl_val_sgn(data->v);
535 data->v = isl_val_abs(data->v);
536 expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
537 isl_aff_free(arg);
538 if (s > 0)
539 data->neg = ast_expr_add(data->neg, expr);
540 else
541 data->pos = ast_expr_add(data->pos, expr);
542 data->aff = isl_aff_set_coefficient_si(data->aff,
543 isl_dim_div, data->i, 0);
544 if (s < 0)
545 data->v = isl_val_neg(data->v);
546 term = isl_aff_scale_val(term, isl_val_copy(data->v));
548 if (!data->add)
549 data->add = term;
550 else
551 data->add = isl_aff_add(data->add, term);
552 if (!data->add)
553 return -1;
555 return 0;
558 /* Given that data->v * div_i in data->aff is of the form
560 * f * d * floor(div/d)
562 * with div nonnegative on data->build, rewrite it as
564 * f * (div - (div mod d)) = f * div - f * (div mod d)
566 * and add
568 * f * div
570 * to data->add and
572 * abs(f) * (div mod d)
574 * to data->neg or data->pos depending on the sign of -f.
576 static int extract_mod(struct isl_extract_mod_data *data)
578 return extract_term_and_mod(data, isl_aff_copy(data->div),
579 isl_aff_copy(data->div));
582 /* Given that data->v * div_i in data->aff is of the form
584 * f * d * floor(div/d) (1)
586 * check if div is non-negative on data->build and, if so,
587 * extract the corresponding modulo from data->aff.
588 * If not, then check if
590 * -div + d - 1
592 * is non-negative on data->build. If so, replace (1) by
594 * -f * d * floor((-div + d - 1)/d)
596 * and extract the corresponding modulo from data->aff.
598 * This function may modify data->div.
600 static int extract_nonneg_mod(struct isl_extract_mod_data *data)
602 int mod;
604 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
605 if (mod < 0)
606 goto error;
607 if (mod)
608 return extract_mod(data);
610 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
611 mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
612 if (mod < 0)
613 goto error;
614 if (mod) {
615 data->v = isl_val_neg(data->v);
616 return extract_mod(data);
619 return 0;
620 error:
621 data->aff = isl_aff_free(data->aff);
622 return -1;
625 /* Is the affine expression of constraint "c" "simpler" than data->nonneg
626 * for use in extracting a modulo expression?
628 * We currently only consider the constant term of the affine expression.
629 * In particular, we prefer the affine expression with the smallest constant
630 * term.
631 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
632 * then we would pick x >= 0
634 * More detailed heuristics could be used if it turns out that there is a need.
636 static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
637 __isl_keep isl_constraint *c)
639 isl_val *v1, *v2;
640 int simpler;
642 if (!data->nonneg)
643 return 1;
645 v1 = isl_val_abs(isl_constraint_get_constant_val(c));
646 v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
647 simpler = isl_val_lt(v1, v2);
648 isl_val_free(v1);
649 isl_val_free(v2);
651 return simpler;
654 /* Check if the coefficients of "c" are either equal or opposite to those
655 * of data->div modulo data->d. If so, and if "c" is "simpler" than
656 * data->nonneg, then replace data->nonneg by the affine expression of "c"
657 * and set data->sign accordingly.
659 * Both "c" and data->div are assumed not to involve any integer divisions.
661 * Before we start the actual comparison, we first quickly check if
662 * "c" and data->div have the same non-zero coefficients.
663 * If not, then we assume that "c" is not of the desired form.
664 * Note that while the coefficients of data->div can be reasonably expected
665 * not to involve any coefficients that are multiples of d, "c" may
666 * very well involve such coefficients. This means that we may actually
667 * miss some cases.
669 * If the constant term is "too large", then the constraint is rejected,
670 * where "too large" is fairly arbitrarily set to 1 << 15.
671 * We do this to avoid picking up constraints that bound a variable
672 * by a very large number, say the largest or smallest possible
673 * variable in the representation of some integer type.
675 static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
676 void *user)
678 struct isl_extract_mod_data *data = user;
679 enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
680 enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
681 int i, t;
682 int n[2];
683 int parallel = 1, opposite = 1;
685 for (t = 0; t < 2; ++t) {
686 n[t] = isl_constraint_dim(c, c_type[t]);
687 for (i = 0; i < n[t]; ++i) {
688 int a, b;
690 a = isl_constraint_involves_dims(c, c_type[t], i, 1);
691 b = isl_aff_involves_dims(data->div, a_type[t], i, 1);
692 if (a != b)
693 parallel = opposite = 0;
697 if (parallel || opposite) {
698 isl_val *v;
700 v = isl_val_abs(isl_constraint_get_constant_val(c));
701 if (isl_val_cmp_si(v, 1 << 15) > 0)
702 parallel = opposite = 0;
703 isl_val_free(v);
706 for (t = 0; t < 2; ++t) {
707 for (i = 0; i < n[t]; ++i) {
708 isl_val *v1, *v2;
710 if (!parallel && !opposite)
711 break;
712 v1 = isl_constraint_get_coefficient_val(c,
713 c_type[t], i);
714 v2 = isl_aff_get_coefficient_val(data->div,
715 a_type[t], i);
716 if (parallel) {
717 v1 = isl_val_sub(v1, isl_val_copy(v2));
718 parallel = isl_val_is_divisible_by(v1, data->d);
719 v1 = isl_val_add(v1, isl_val_copy(v2));
721 if (opposite) {
722 v1 = isl_val_add(v1, isl_val_copy(v2));
723 opposite = isl_val_is_divisible_by(v1, data->d);
725 isl_val_free(v1);
726 isl_val_free(v2);
730 if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {
731 isl_aff_free(data->nonneg);
732 data->nonneg = isl_constraint_get_aff(c);
733 data->sign = parallel ? 1 : -1;
736 isl_constraint_free(c);
738 if (data->sign != 0 && data->nonneg == NULL)
739 return isl_stat_error;
741 return isl_stat_ok;
744 /* Given that data->v * div_i in data->aff is of the form
746 * f * d * floor(div/d) (1)
748 * see if we can find an expression div' that is non-negative over data->build
749 * and that is related to div through
751 * div' = div + d * e
753 * or
755 * div' = -div + d - 1 + d * e
757 * with e some affine expression.
758 * If so, we write (1) as
760 * f * div + f * (div' mod d)
762 * or
764 * -f * (-div + d - 1) - f * (div' mod d)
766 * exploiting (in the second case) the fact that
768 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
771 * We first try to find an appropriate expression for div'
772 * from the constraints of data->build->domain (which is therefore
773 * guaranteed to be non-negative on data->build), where we remove
774 * any integer divisions from the constraints and skip this step
775 * if "div" itself involves any integer divisions.
776 * If we cannot find an appropriate expression this way, then
777 * we pass control to extract_nonneg_mod where check
778 * if div or "-div + d -1" themselves happen to be
779 * non-negative on data->build.
781 * While looking for an appropriate constraint in data->build->domain,
782 * we ignore the constant term, so after finding such a constraint,
783 * we still need to fix up the constant term.
784 * In particular, if a is the constant term of "div"
785 * (or d - 1 - the constant term of "div" if data->sign < 0)
786 * and b is the constant term of the constraint, then we need to find
787 * a non-negative constant c such that
789 * b + c \equiv a mod d
791 * We therefore take
793 * c = (a - b) mod d
795 * and add it to b to obtain the constant term of div'.
796 * If this constant term is "too negative", then we add an appropriate
797 * multiple of d to make it positive.
800 * Note that the above is a only a very simple heuristic for finding an
801 * appropriate expression. We could try a bit harder by also considering
802 * sums of constraints that involve disjoint sets of variables or
803 * we could consider arbitrary linear combinations of constraints,
804 * although that could potentially be much more expensive as it involves
805 * the solution of an LP problem.
807 * In particular, if v_i is a column vector representing constraint i,
808 * w represents div and e_i is the i-th unit vector, then we are looking
809 * for a solution of the constraints
811 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
813 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
814 * If we are not just interested in a non-negative expression, but
815 * also in one with a minimal range, then we don't just want
816 * c = \sum_i lambda_i v_i to be non-negative over the domain,
817 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
818 * that we want to minimize and we now also have to take into account
819 * the constant terms of the constraints.
820 * Alternatively, we could first compute the dual of the domain
821 * and plug in the constraints on the coefficients.
823 static int try_extract_mod(struct isl_extract_mod_data *data)
825 isl_basic_set *hull;
826 isl_val *v1, *v2;
827 int r, n;
829 if (!data->build)
830 goto error;
832 n = isl_aff_dim(data->div, isl_dim_div);
834 if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
835 return extract_nonneg_mod(data);
837 hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
838 hull = isl_basic_set_remove_divs(hull);
839 data->sign = 0;
840 data->nonneg = NULL;
841 r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
842 data);
843 isl_basic_set_free(hull);
845 if (!data->sign || r < 0) {
846 isl_aff_free(data->nonneg);
847 if (r < 0)
848 goto error;
849 return extract_nonneg_mod(data);
852 v1 = isl_aff_get_constant_val(data->div);
853 v2 = isl_aff_get_constant_val(data->nonneg);
854 if (data->sign < 0) {
855 v1 = isl_val_neg(v1);
856 v1 = isl_val_add(v1, isl_val_copy(data->d));
857 v1 = isl_val_sub_ui(v1, 1);
859 v1 = isl_val_sub(v1, isl_val_copy(v2));
860 v1 = isl_val_mod(v1, isl_val_copy(data->d));
861 v1 = isl_val_add(v1, v2);
862 v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
863 v2 = isl_val_ceil(v2);
864 if (isl_val_is_neg(v2)) {
865 v2 = isl_val_mul(v2, isl_val_copy(data->d));
866 v1 = isl_val_sub(v1, isl_val_copy(v2));
868 data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
869 isl_val_free(v2);
871 if (data->sign < 0) {
872 data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
873 data->v = isl_val_neg(data->v);
876 return extract_term_and_mod(data,
877 isl_aff_copy(data->div), data->nonneg);
878 error:
879 data->aff = isl_aff_free(data->aff);
880 return -1;
883 /* Check if "data->aff" involves any (implicit) modulo computations based
884 * on div "data->i".
885 * If so, remove them from aff and add expressions corresponding
886 * to those modulo computations to data->pos and/or data->neg.
888 * "aff" is assumed to be an integer affine expression.
890 * In particular, check if (v * div_j) is of the form
892 * f * m * floor(a / m)
894 * and, if so, rewrite it as
896 * f * (a - (a mod m)) = f * a - f * (a mod m)
898 * and extract out -f * (a mod m).
899 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
900 * If f < 0, we add ((-f) * (a mod m)) to *pos.
902 * Note that in order to represent "a mod m" as
904 * (isl_ast_op_pdiv_r, a, m)
906 * we need to make sure that a is non-negative.
907 * If not, we check if "-a + m - 1" is non-negative.
908 * If so, we can rewrite
910 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
912 * and still extract a modulo.
914 static int extract_modulo(struct isl_extract_mod_data *data)
916 data->div = isl_aff_get_div(data->aff, data->i);
917 data->d = isl_aff_get_denominator_val(data->div);
918 if (isl_val_is_divisible_by(data->v, data->d)) {
919 data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
920 if (try_extract_mod(data) < 0)
921 data->aff = isl_aff_free(data->aff);
923 isl_aff_free(data->div);
924 isl_val_free(data->d);
925 return 0;
928 /* Check if "aff" involves any (implicit) modulo computations.
929 * If so, remove them from aff and add expressions corresponding
930 * to those modulo computations to *pos and/or *neg.
931 * We only do this if the option ast_build_prefer_pdiv is set.
933 * "aff" is assumed to be an integer affine expression.
935 * A modulo expression is of the form
937 * a mod m = a - m * floor(a / m)
939 * To detect them in aff, we look for terms of the form
941 * f * m * floor(a / m)
943 * rewrite them as
945 * f * (a - (a mod m)) = f * a - f * (a mod m)
947 * and extract out -f * (a mod m).
948 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
949 * If f < 0, we add ((-f) * (a mod m)) to *pos.
951 static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
952 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
953 __isl_keep isl_ast_build *build)
955 struct isl_extract_mod_data data = { build, aff, *pos, *neg };
956 isl_ctx *ctx;
957 int n;
959 if (!aff)
960 return NULL;
962 ctx = isl_aff_get_ctx(aff);
963 if (!isl_options_get_ast_build_prefer_pdiv(ctx))
964 return aff;
966 n = isl_aff_dim(data.aff, isl_dim_div);
967 for (data.i = 0; data.i < n; ++data.i) {
968 data.v = isl_aff_get_coefficient_val(data.aff,
969 isl_dim_div, data.i);
970 if (!data.v)
971 return isl_aff_free(aff);
972 if (isl_val_is_zero(data.v) ||
973 isl_val_is_one(data.v) || isl_val_is_negone(data.v)) {
974 isl_val_free(data.v);
975 continue;
977 if (extract_modulo(&data) < 0)
978 data.aff = isl_aff_free(data.aff);
979 isl_val_free(data.v);
980 if (!data.aff)
981 break;
984 if (data.add)
985 data.aff = isl_aff_add(data.aff, data.add);
987 *pos = data.pos;
988 *neg = data.neg;
989 return data.aff;
992 /* Check if aff involves any non-integer coefficients.
993 * If so, split aff into
995 * aff = aff1 + (aff2 / d)
997 * with both aff1 and aff2 having only integer coefficients.
998 * Return aff1 and add (aff2 / d) to *expr.
1000 static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
1001 __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
1003 int i, j, n;
1004 isl_aff *rat = NULL;
1005 isl_local_space *ls = NULL;
1006 isl_ast_expr *rat_expr;
1007 isl_val *v, *d;
1008 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1009 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1011 if (!aff)
1012 return NULL;
1013 d = isl_aff_get_denominator_val(aff);
1014 if (!d)
1015 goto error;
1016 if (isl_val_is_one(d)) {
1017 isl_val_free(d);
1018 return aff;
1021 aff = isl_aff_scale_val(aff, isl_val_copy(d));
1023 ls = isl_aff_get_domain_local_space(aff);
1024 rat = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1026 for (i = 0; i < 3; ++i) {
1027 n = isl_aff_dim(aff, t[i]);
1028 for (j = 0; j < n; ++j) {
1029 isl_aff *rat_j;
1031 v = isl_aff_get_coefficient_val(aff, t[i], j);
1032 if (!v)
1033 goto error;
1034 if (isl_val_is_divisible_by(v, d)) {
1035 isl_val_free(v);
1036 continue;
1038 rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls),
1039 l[i], j);
1040 rat_j = isl_aff_scale_val(rat_j, v);
1041 rat = isl_aff_add(rat, rat_j);
1045 v = isl_aff_get_constant_val(aff);
1046 if (isl_val_is_divisible_by(v, d)) {
1047 isl_val_free(v);
1048 } else {
1049 isl_aff *rat_0;
1051 rat_0 = isl_aff_val_on_domain(isl_local_space_copy(ls), v);
1052 rat = isl_aff_add(rat, rat_0);
1055 isl_local_space_free(ls);
1057 aff = isl_aff_sub(aff, isl_aff_copy(rat));
1058 aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
1060 rat_expr = isl_ast_expr_from_aff(rat, build);
1061 rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
1062 *expr = ast_expr_add(*expr, rat_expr);
1064 return aff;
1065 error:
1066 isl_aff_free(rat);
1067 isl_local_space_free(ls);
1068 isl_aff_free(aff);
1069 isl_val_free(d);
1070 return NULL;
1073 /* Construct an isl_ast_expr that evaluates the affine expression "aff",
1074 * The result is simplified in terms of build->domain.
1076 * We first extract hidden modulo computations from the affine expression
1077 * and then add terms for each variable with a non-zero coefficient.
1078 * Finally, if the affine expression has a non-trivial denominator,
1079 * we divide the resulting isl_ast_expr by this denominator.
1081 __isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
1082 __isl_keep isl_ast_build *build)
1084 int i, j;
1085 int n;
1086 isl_val *v;
1087 isl_ctx *ctx = isl_aff_get_ctx(aff);
1088 isl_ast_expr *expr, *expr_neg;
1089 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1090 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1091 isl_local_space *ls;
1092 struct isl_ast_add_term_data data;
1094 if (!aff)
1095 return NULL;
1097 expr = isl_ast_expr_alloc_int_si(ctx, 0);
1098 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1100 aff = extract_rational(aff, &expr, build);
1102 aff = extract_modulos(aff, &expr, &expr_neg, build);
1103 expr = ast_expr_sub(expr, expr_neg);
1105 ls = isl_aff_get_domain_local_space(aff);
1107 data.build = build;
1108 data.cst = isl_aff_get_constant_val(aff);
1109 for (i = 0; i < 3; ++i) {
1110 n = isl_aff_dim(aff, t[i]);
1111 for (j = 0; j < n; ++j) {
1112 v = isl_aff_get_coefficient_val(aff, t[i], j);
1113 if (!v)
1114 expr = isl_ast_expr_free(expr);
1115 if (isl_val_is_zero(v)) {
1116 isl_val_free(v);
1117 continue;
1119 expr = isl_ast_expr_add_term(expr,
1120 ls, l[i], j, v, &data);
1124 expr = isl_ast_expr_add_int(expr, data.cst);
1126 isl_local_space_free(ls);
1127 isl_aff_free(aff);
1128 return expr;
1131 /* Add terms to "expr" for each variable in "aff" with a coefficient
1132 * with sign equal to "sign".
1133 * The result is simplified in terms of data->build->domain.
1135 static __isl_give isl_ast_expr *add_signed_terms(__isl_take isl_ast_expr *expr,
1136 __isl_keep isl_aff *aff, int sign, struct isl_ast_add_term_data *data)
1138 int i, j;
1139 isl_val *v;
1140 enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1141 enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1142 isl_local_space *ls;
1144 ls = isl_aff_get_domain_local_space(aff);
1146 for (i = 0; i < 3; ++i) {
1147 int n = isl_aff_dim(aff, t[i]);
1148 for (j = 0; j < n; ++j) {
1149 v = isl_aff_get_coefficient_val(aff, t[i], j);
1150 if (sign * isl_val_sgn(v) <= 0) {
1151 isl_val_free(v);
1152 continue;
1154 v = isl_val_abs(v);
1155 expr = isl_ast_expr_add_term(expr,
1156 ls, l[i], j, v, data);
1160 isl_local_space_free(ls);
1162 return expr;
1165 /* Should the constant term "v" be considered positive?
1167 * A positive constant will be added to "pos" by the caller,
1168 * while a negative constant will be added to "neg".
1169 * If either "pos" or "neg" is exactly zero, then we prefer
1170 * to add the constant "v" to that side, irrespective of the sign of "v".
1171 * This results in slightly shorter expressions and may reduce the risk
1172 * of overflows.
1174 static int constant_is_considered_positive(__isl_keep isl_val *v,
1175 __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
1177 if (ast_expr_is_zero(pos))
1178 return 1;
1179 if (ast_expr_is_zero(neg))
1180 return 0;
1181 return isl_val_is_pos(v);
1184 /* Check if the equality
1186 * aff = 0
1188 * represents a stride constraint on the integer division "pos".
1190 * In particular, if the integer division "pos" is equal to
1192 * floor(e/d)
1194 * then check if aff is equal to
1196 * e - d floor(e/d)
1198 * or its opposite.
1200 * If so, the equality is exactly
1202 * e mod d = 0
1204 * Note that in principle we could also accept
1206 * e - d floor(e'/d)
1208 * where e and e' differ by a constant.
1210 static int is_stride_constraint(__isl_keep isl_aff *aff, int pos)
1212 isl_aff *div;
1213 isl_val *c, *d;
1214 int eq;
1216 div = isl_aff_get_div(aff, pos);
1217 c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1218 d = isl_aff_get_denominator_val(div);
1219 eq = isl_val_abs_eq(c, d);
1220 if (eq >= 0 && eq) {
1221 aff = isl_aff_copy(aff);
1222 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1223 div = isl_aff_scale_val(div, d);
1224 if (isl_val_is_pos(c))
1225 div = isl_aff_neg(div);
1226 eq = isl_aff_plain_is_equal(div, aff);
1227 isl_aff_free(aff);
1228 } else
1229 isl_val_free(d);
1230 isl_val_free(c);
1231 isl_aff_free(div);
1233 return eq;
1236 /* Are all coefficients of "aff" (zero or) negative?
1238 static int all_negative_coefficients(__isl_keep isl_aff *aff)
1240 int i, n;
1242 if (!aff)
1243 return 0;
1245 n = isl_aff_dim(aff, isl_dim_param);
1246 for (i = 0; i < n; ++i)
1247 if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)
1248 return 0;
1250 n = isl_aff_dim(aff, isl_dim_in);
1251 for (i = 0; i < n; ++i)
1252 if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)
1253 return 0;
1255 return 1;
1258 /* Give an equality of the form
1260 * aff = e - d floor(e/d) = 0
1262 * or
1264 * aff = -e + d floor(e/d) = 0
1266 * with the integer division "pos" equal to floor(e/d),
1267 * construct the AST expression
1269 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0))
1271 * If e only has negative coefficients, then construct
1273 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(-e), expr(d)), expr(0))
1275 * instead.
1277 static __isl_give isl_ast_expr *extract_stride_constraint(
1278 __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
1280 isl_ctx *ctx;
1281 isl_val *c;
1282 isl_ast_expr *expr, *cst;
1284 if (!aff)
1285 return NULL;
1287 ctx = isl_aff_get_ctx(aff);
1289 c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1290 aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1292 if (all_negative_coefficients(aff))
1293 aff = isl_aff_neg(aff);
1295 cst = isl_ast_expr_from_val(isl_val_abs(c));
1296 expr = isl_ast_expr_from_aff(aff, build);
1298 expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst);
1299 cst = isl_ast_expr_alloc_int_si(ctx, 0);
1300 expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst);
1302 return expr;
1305 /* Construct an isl_ast_expr that evaluates the condition "constraint",
1306 * The result is simplified in terms of build->domain.
1308 * We first check if the constraint is an equality of the form
1310 * e - d floor(e/d) = 0
1312 * i.e.,
1314 * e mod d = 0
1316 * If so, we convert it to
1318 * (isl_ast_op_eq, (isl_ast_op_zdiv_r, expr(e), expr(d)), expr(0))
1320 * Otherwise, let the constraint by either "a >= 0" or "a == 0".
1321 * We first extract hidden modulo computations from "a"
1322 * and then collect all the terms with a positive coefficient in cons_pos
1323 * and the terms with a negative coefficient in cons_neg.
1325 * The result is then of the form
1327 * (isl_ast_op_ge, expr(pos), expr(-neg)))
1329 * or
1331 * (isl_ast_op_eq, expr(pos), expr(-neg)))
1333 * However, if the first expression is an integer constant (and the second
1334 * is not), then we swap the two expressions. This ensures that we construct,
1335 * e.g., "i <= 5" rather than "5 >= i".
1337 * Furthermore, is there are no terms with positive coefficients (or no terms
1338 * with negative coefficients), then the constant term is added to "pos"
1339 * (or "neg"), ignoring the sign of the constant term.
1341 static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1342 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1344 int i, n;
1345 isl_ctx *ctx;
1346 isl_ast_expr *expr_pos;
1347 isl_ast_expr *expr_neg;
1348 isl_ast_expr *expr;
1349 isl_aff *aff;
1350 int eq;
1351 enum isl_ast_op_type type;
1352 struct isl_ast_add_term_data data;
1354 if (!constraint)
1355 return NULL;
1357 aff = isl_constraint_get_aff(constraint);
1358 eq = isl_constraint_is_equality(constraint);
1359 isl_constraint_free(constraint);
1361 n = isl_aff_dim(aff, isl_dim_div);
1362 if (eq && n > 0)
1363 for (i = 0; i < n; ++i) {
1364 int is_stride;
1365 is_stride = is_stride_constraint(aff, i);
1366 if (is_stride < 0)
1367 goto error;
1368 if (is_stride)
1369 return extract_stride_constraint(aff, i, build);
1372 ctx = isl_aff_get_ctx(aff);
1373 expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
1374 expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1376 aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
1378 data.build = build;
1379 data.cst = isl_aff_get_constant_val(aff);
1380 expr_pos = add_signed_terms(expr_pos, aff, 1, &data);
1381 data.cst = isl_val_neg(data.cst);
1382 expr_neg = add_signed_terms(expr_neg, aff, -1, &data);
1383 data.cst = isl_val_neg(data.cst);
1385 if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) {
1386 expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
1387 } else {
1388 data.cst = isl_val_neg(data.cst);
1389 expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
1392 if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
1393 isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int) {
1394 type = eq ? isl_ast_op_eq : isl_ast_op_le;
1395 expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
1396 } else {
1397 type = eq ? isl_ast_op_eq : isl_ast_op_ge;
1398 expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
1401 isl_aff_free(aff);
1402 return expr;
1403 error:
1404 isl_aff_free(aff);
1405 return NULL;
1408 /* Wrapper around isl_constraint_cmp_last_non_zero for use
1409 * as a callback to isl_constraint_list_sort.
1410 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1411 * apart, then use isl_constraint_plain_cmp instead.
1413 static int cmp_constraint(__isl_keep isl_constraint *a,
1414 __isl_keep isl_constraint *b, void *user)
1416 int cmp;
1418 cmp = isl_constraint_cmp_last_non_zero(a, b);
1419 if (cmp != 0)
1420 return cmp;
1421 return isl_constraint_plain_cmp(a, b);
1424 /* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1425 * The result is simplified in terms of build->domain.
1427 * If "bset" is not bounded by any constraint, then we construct
1428 * the expression "1", i.e., "true".
1430 * Otherwise, we sort the constraints, putting constraints that involve
1431 * integer divisions after those that do not, and construct an "and"
1432 * of the ast expressions of the individual constraints.
1434 * Each constraint is added to the generated constraints of the build
1435 * after it has been converted to an AST expression so that it can be used
1436 * to simplify the following constraints. This may change the truth value
1437 * of subsequent constraints that do not satisfy the earlier constraints,
1438 * but this does not affect the outcome of the conjunction as it is
1439 * only true if all the conjuncts are true (no matter in what order
1440 * they are evaluated). In particular, the constraints that do not
1441 * involve integer divisions may serve to simplify some constraints
1442 * that do involve integer divisions.
1444 __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
1445 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1447 int i, n;
1448 isl_constraint *c;
1449 isl_constraint_list *list;
1450 isl_ast_expr *res;
1451 isl_set *set;
1453 list = isl_basic_set_get_constraint_list(bset);
1454 isl_basic_set_free(bset);
1455 list = isl_constraint_list_sort(list, &cmp_constraint, NULL);
1456 if (!list)
1457 return NULL;
1458 n = isl_constraint_list_n_constraint(list);
1459 if (n == 0) {
1460 isl_ctx *ctx = isl_constraint_list_get_ctx(list);
1461 isl_constraint_list_free(list);
1462 return isl_ast_expr_alloc_int_si(ctx, 1);
1465 build = isl_ast_build_copy(build);
1467 c = isl_constraint_list_get_constraint(list, 0);
1468 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1469 set = isl_set_from_basic_set(bset);
1470 res = isl_ast_expr_from_constraint(c, build);
1471 build = isl_ast_build_restrict_generated(build, set);
1473 for (i = 1; i < n; ++i) {
1474 isl_ast_expr *expr;
1476 c = isl_constraint_list_get_constraint(list, i);
1477 bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1478 set = isl_set_from_basic_set(bset);
1479 expr = isl_ast_expr_from_constraint(c, build);
1480 build = isl_ast_build_restrict_generated(build, set);
1481 res = isl_ast_expr_and(res, expr);
1484 isl_constraint_list_free(list);
1485 isl_ast_build_free(build);
1486 return res;
1489 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1490 * The result is simplified in terms of build->domain.
1492 * If "set" is an (obviously) empty set, then return the expression "0".
1494 * If there are multiple disjuncts in the description of the set,
1495 * then subsequent disjuncts are simplified in a context where
1496 * the previous disjuncts have been removed from build->domain.
1497 * In particular, constraints that ensure that there is no overlap
1498 * with these previous disjuncts, can be removed.
1499 * This is mostly useful for disjuncts that are only defined by
1500 * a single constraint (relative to the build domain) as the opposite
1501 * of that single constraint can then be removed from the other disjuncts.
1502 * In order not to increase the number of disjuncts in the build domain
1503 * after subtracting the previous disjuncts of "set", the simple hull
1504 * is computed after taking the difference with each of these disjuncts.
1505 * This means that constraints that prevent overlap with a union
1506 * of multiple previous disjuncts are not removed.
1508 * "set" lives in the internal schedule space.
1510 __isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
1511 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1513 int i, n;
1514 isl_basic_set *bset;
1515 isl_basic_set_list *list;
1516 isl_set *domain;
1517 isl_ast_expr *res;
1519 list = isl_set_get_basic_set_list(set);
1520 isl_set_free(set);
1522 if (!list)
1523 return NULL;
1524 n = isl_basic_set_list_n_basic_set(list);
1525 if (n == 0) {
1526 isl_ctx *ctx = isl_ast_build_get_ctx(build);
1527 isl_basic_set_list_free(list);
1528 return isl_ast_expr_from_val(isl_val_zero(ctx));
1531 domain = isl_ast_build_get_domain(build);
1533 bset = isl_basic_set_list_get_basic_set(list, 0);
1534 set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1535 res = isl_ast_build_expr_from_basic_set(build, bset);
1537 for (i = 1; i < n; ++i) {
1538 isl_ast_expr *expr;
1539 isl_set *rest;
1541 rest = isl_set_subtract(isl_set_copy(domain), set);
1542 rest = isl_set_from_basic_set(isl_set_simple_hull(rest));
1543 domain = isl_set_intersect(domain, rest);
1544 bset = isl_basic_set_list_get_basic_set(list, i);
1545 set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1546 bset = isl_basic_set_gist(bset,
1547 isl_set_simple_hull(isl_set_copy(domain)));
1548 expr = isl_ast_build_expr_from_basic_set(build, bset);
1549 res = isl_ast_expr_or(res, expr);
1552 isl_set_free(domain);
1553 isl_set_free(set);
1554 isl_basic_set_list_free(list);
1555 return res;
1558 /* Construct an isl_ast_expr that evaluates the conditions defining "set".
1559 * The result is simplified in terms of build->domain.
1561 * If "set" is an (obviously) empty set, then return the expression "0".
1563 * "set" lives in the external schedule space.
1565 * The internal AST expression generation assumes that there are
1566 * no unknown divs, so make sure an explicit representation is available.
1567 * Since the set comes from the outside, it may have constraints that
1568 * are redundant with respect to the build domain. Remove them first.
1570 __isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1571 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1573 if (isl_ast_build_need_schedule_map(build)) {
1574 isl_multi_aff *ma;
1575 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1576 set = isl_set_preimage_multi_aff(set, ma);
1579 set = isl_set_compute_divs(set);
1580 set = isl_ast_build_compute_gist(build, set);
1581 return isl_ast_build_expr_from_set_internal(build, set);
1584 /* State of data about previous pieces in
1585 * isl_ast_build_expr_from_pw_aff_internal.
1587 * isl_state_none: no data about previous pieces
1588 * isl_state_single: data about a single previous piece
1589 * isl_state_min: data represents minimum of several pieces
1590 * isl_state_max: data represents maximum of several pieces
1592 enum isl_from_pw_aff_state {
1593 isl_state_none,
1594 isl_state_single,
1595 isl_state_min,
1596 isl_state_max
1599 /* Internal date structure representing a single piece in the input of
1600 * isl_ast_build_expr_from_pw_aff_internal.
1602 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1603 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1604 * single previous subpiece.
1605 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
1606 * a sequence of several previous subpieces that are equal to the minimum
1607 * of the entries in "aff_list" over the union of "set_list"
1608 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
1609 * a sequence of several previous subpieces that are equal to the maximum
1610 * of the entries in "aff_list" over the union of "set_list"
1612 * During the construction of the pieces, "set" is NULL.
1613 * After the construction, "set" is set to the union of the elements
1614 * in "set_list", at which point "set_list" is set to NULL.
1616 struct isl_from_pw_aff_piece {
1617 enum isl_from_pw_aff_state state;
1618 isl_set *set;
1619 isl_set_list *set_list;
1620 isl_aff_list *aff_list;
1623 /* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1625 * "build" specifies the domain against which the result is simplified.
1626 * "dom" is the domain of the entire isl_pw_aff.
1628 * "n" is the number of pieces constructed already.
1629 * In particular, during the construction of the pieces, "n" points to
1630 * the piece that is being constructed. After the construction of the
1631 * pieces, "n" is set to the total number of pieces.
1632 * "max" is the total number of allocated entries.
1633 * "p" contains the individual pieces.
1635 struct isl_from_pw_aff_data {
1636 isl_ast_build *build;
1637 isl_set *dom;
1639 int n;
1640 int max;
1641 struct isl_from_pw_aff_piece *p;
1644 /* Initialize "data" based on "build" and "pa".
1646 static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data,
1647 __isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa)
1649 int n;
1650 isl_ctx *ctx;
1652 ctx = isl_pw_aff_get_ctx(pa);
1653 n = isl_pw_aff_n_piece(pa);
1654 if (n == 0)
1655 isl_die(ctx, isl_error_invalid,
1656 "cannot handle void expression", return isl_stat_error);
1657 data->max = n;
1658 data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
1659 if (!data->p)
1660 return isl_stat_error;
1661 data->build = build;
1662 data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1663 data->n = 0;
1665 return isl_stat_ok;
1668 /* Free all memory allocated for "data".
1670 static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)
1672 int i;
1674 isl_set_free(data->dom);
1675 if (!data->p)
1676 return;
1678 for (i = 0; i < data->max; ++i) {
1679 isl_set_free(data->p[i].set);
1680 isl_set_list_free(data->p[i].set_list);
1681 isl_aff_list_free(data->p[i].aff_list);
1683 free(data->p);
1686 /* Initialize the current entry of "data" to an unused piece.
1688 static void set_none(struct isl_from_pw_aff_data *data)
1690 data->p[data->n].state = isl_state_none;
1691 data->p[data->n].set_list = NULL;
1692 data->p[data->n].aff_list = NULL;
1695 /* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1697 static void set_single(struct isl_from_pw_aff_data *data,
1698 __isl_take isl_set *set, __isl_take isl_aff *aff)
1700 data->p[data->n].state = isl_state_single;
1701 data->p[data->n].set_list = isl_set_list_from_set(set);
1702 data->p[data->n].aff_list = isl_aff_list_from_aff(aff);
1705 /* Extend the current entry of "data" with "set" and "aff"
1706 * as a minimum expression.
1708 static isl_stat extend_min(struct isl_from_pw_aff_data *data,
1709 __isl_take isl_set *set, __isl_take isl_aff *aff)
1711 int n = data->n;
1712 data->p[n].state = isl_state_min;
1713 data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1714 data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1716 if (!data->p[n].set_list || !data->p[n].aff_list)
1717 return isl_stat_error;
1718 return isl_stat_ok;
1721 /* Extend the current entry of "data" with "set" and "aff"
1722 * as a maximum expression.
1724 static isl_stat extend_max(struct isl_from_pw_aff_data *data,
1725 __isl_take isl_set *set, __isl_take isl_aff *aff)
1727 int n = data->n;
1728 data->p[n].state = isl_state_max;
1729 data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1730 data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1732 if (!data->p[n].set_list || !data->p[n].aff_list)
1733 return isl_stat_error;
1734 return isl_stat_ok;
1737 /* Extend the domain of the current entry of "data", which is assumed
1738 * to contain a single subpiece, with "set". If "replace" is set,
1739 * then also replace the affine function by "aff". Otherwise,
1740 * simply free "aff".
1742 static isl_stat extend_domain(struct isl_from_pw_aff_data *data,
1743 __isl_take isl_set *set, __isl_take isl_aff *aff, int replace)
1745 int n = data->n;
1746 isl_set *set_n;
1748 set_n = isl_set_list_get_set(data->p[n].set_list, 0);
1749 set_n = isl_set_union(set_n, set);
1750 data->p[n].set_list =
1751 isl_set_list_set_set(data->p[n].set_list, 0, set_n);
1753 if (replace)
1754 data->p[n].aff_list =
1755 isl_aff_list_set_aff(data->p[n].aff_list, 0, aff);
1756 else
1757 isl_aff_free(aff);
1759 if (!data->p[n].set_list || !data->p[n].aff_list)
1760 return isl_stat_error;
1761 return isl_stat_ok;
1764 /* Construct an isl_ast_expr from "list" within "build".
1765 * If "state" is isl_state_single, then "list" contains a single entry and
1766 * an isl_ast_expr is constructed for that entry.
1767 * Otherwise a min or max expression is constructed from "list"
1768 * depending on "state".
1770 static __isl_give isl_ast_expr *ast_expr_from_aff_list(
1771 __isl_take isl_aff_list *list, enum isl_from_pw_aff_state state,
1772 __isl_keep isl_ast_build *build)
1774 int i, n;
1775 isl_aff *aff;
1776 isl_ast_expr *expr;
1777 enum isl_ast_op_type op_type;
1779 if (state == isl_state_single) {
1780 aff = isl_aff_list_get_aff(list, 0);
1781 isl_aff_list_free(list);
1782 return isl_ast_expr_from_aff(aff, build);
1784 n = isl_aff_list_n_aff(list);
1785 op_type = state == isl_state_min ? isl_ast_op_min : isl_ast_op_max;
1786 expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n);
1787 if (!expr)
1788 goto error;
1790 for (i = 0; i < n; ++i) {
1791 isl_ast_expr *expr_i;
1793 aff = isl_aff_list_get_aff(list, i);
1794 expr_i = isl_ast_expr_from_aff(aff, build);
1795 if (!expr_i)
1796 goto error;
1797 expr->u.op.args[i] = expr_i;
1800 isl_aff_list_free(list);
1801 return expr;
1802 error:
1803 isl_aff_list_free(list);
1804 isl_ast_expr_free(expr);
1805 return NULL;
1808 /* Extend the expression in "next" to take into account
1809 * the piece at position "pos" in "data", allowing for a further extension
1810 * for the next piece(s).
1811 * In particular, "next" is set to a select operation that selects
1812 * an isl_ast_expr corresponding to data->aff_list on data->set and
1813 * to an expression that will be filled in by later calls.
1814 * Return a pointer to this location.
1815 * Afterwards, the state of "data" is set to isl_state_none.
1817 * The constraints of data->set are added to the generated
1818 * constraints of the build such that they can be exploited to simplify
1819 * the AST expression constructed from data->aff_list.
1821 static isl_ast_expr **add_intermediate_piece(struct isl_from_pw_aff_data *data,
1822 int pos, isl_ast_expr **next)
1824 isl_ctx *ctx;
1825 isl_ast_build *build;
1826 isl_ast_expr *ternary, *arg;
1827 isl_set *set, *gist;
1829 set = data->p[pos].set;
1830 data->p[pos].set = NULL;
1831 ctx = isl_ast_build_get_ctx(data->build);
1832 ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
1833 gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));
1834 arg = isl_ast_build_expr_from_set_internal(data->build, gist);
1835 ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
1836 build = isl_ast_build_copy(data->build);
1837 build = isl_ast_build_restrict_generated(build, set);
1838 arg = ast_expr_from_aff_list(data->p[pos].aff_list,
1839 data->p[pos].state, build);
1840 data->p[pos].aff_list = NULL;
1841 isl_ast_build_free(build);
1842 ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
1843 data->p[pos].state = isl_state_none;
1844 if (!ternary)
1845 return NULL;
1847 *next = ternary;
1848 return &ternary->u.op.args[2];
1851 /* Extend the expression in "next" to take into account
1852 * the final piece, located at position "pos" in "data".
1853 * In particular, "next" is set to evaluate data->aff_list
1854 * and the domain is ignored.
1855 * Return isl_stat_ok on success and isl_stat_error on failure.
1857 * The constraints of data->set are however added to the generated
1858 * constraints of the build such that they can be exploited to simplify
1859 * the AST expression constructed from data->aff_list.
1861 static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,
1862 int pos, isl_ast_expr **next)
1864 isl_ast_build *build;
1866 if (data->p[pos].state == isl_state_none)
1867 isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1868 "cannot handle void expression", return isl_stat_error);
1870 build = isl_ast_build_copy(data->build);
1871 build = isl_ast_build_restrict_generated(build, data->p[pos].set);
1872 data->p[pos].set = NULL;
1873 *next = ast_expr_from_aff_list(data->p[pos].aff_list,
1874 data->p[pos].state, build);
1875 data->p[pos].aff_list = NULL;
1876 isl_ast_build_free(build);
1877 data->p[pos].state = isl_state_none;
1878 if (!*next)
1879 return isl_stat_error;
1881 return isl_stat_ok;
1884 /* Return -1 if the piece "p1" should be sorted before "p2"
1885 * and 1 if it should be sorted after "p2".
1886 * Return 0 if they do not need to be sorted in a specific order.
1888 * Pieces are sorted according to the number of disjuncts
1889 * in their domains.
1891 static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)
1893 const struct isl_from_pw_aff_piece *piece1 = p1;
1894 const struct isl_from_pw_aff_piece *piece2 = p2;
1895 int n1, n2;
1897 n1 = isl_set_n_basic_set(piece1->set);
1898 n2 = isl_set_n_basic_set(piece2->set);
1900 return n1 - n2;
1903 /* Construct an isl_ast_expr from the pieces in "data".
1904 * Return the result or NULL on failure.
1906 * When this function is called, data->n points to the current piece.
1907 * If this is an effective piece, then first increment data->n such
1908 * that data->n contains the number of pieces.
1909 * The "set_list" fields are subsequently replaced by the corresponding
1910 * "set" fields, after which the pieces are sorted according to
1911 * the number of disjuncts in these "set" fields.
1913 * Construct intermediate AST expressions for the initial pieces and
1914 * finish off with the final pieces.
1916 static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)
1918 int i;
1919 isl_ast_expr *res = NULL;
1920 isl_ast_expr **next = &res;
1922 if (data->p[data->n].state != isl_state_none)
1923 data->n++;
1924 if (data->n == 0)
1925 isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1926 "cannot handle void expression", return NULL);
1928 for (i = 0; i < data->n; ++i) {
1929 data->p[i].set = isl_set_list_union(data->p[i].set_list);
1930 if (data->p[i].state != isl_state_single)
1931 data->p[i].set = isl_set_coalesce(data->p[i].set);
1932 data->p[i].set_list = NULL;
1935 if (isl_sort(data->p, data->n, sizeof(data->p[0]),
1936 &sort_pieces_cmp, NULL) < 0)
1937 return isl_ast_expr_free(res);
1939 for (i = 0; i + 1 < data->n; ++i) {
1940 next = add_intermediate_piece(data, i, next);
1941 if (!next)
1942 return isl_ast_expr_free(res);
1945 if (add_last_piece(data, data->n - 1, next) < 0)
1946 return isl_ast_expr_free(res);
1948 return res;
1951 /* Is the domain of the current entry of "data", which is assumed
1952 * to contain a single subpiece, a subset of "set"?
1954 static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
1955 __isl_keep isl_set *set)
1957 isl_bool subset;
1958 isl_set *set_n;
1960 set_n = isl_set_list_get_set(data->p[data->n].set_list, 0);
1961 subset = isl_set_is_subset(set_n, set);
1962 isl_set_free(set_n);
1964 return subset;
1967 /* Is "aff" a rational expression, i.e., does it have a denominator
1968 * different from one?
1970 static isl_bool aff_is_rational(__isl_keep isl_aff *aff)
1972 isl_bool rational;
1973 isl_val *den;
1975 den = isl_aff_get_denominator_val(aff);
1976 rational = isl_bool_not(isl_val_is_one(den));
1977 isl_val_free(den);
1979 return rational;
1982 /* Does "list" consist of a single rational affine expression?
1984 static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)
1986 isl_bool rational;
1987 isl_aff *aff;
1989 if (isl_aff_list_n_aff(list) != 1)
1990 return isl_bool_false;
1991 aff = isl_aff_list_get_aff(list, 0);
1992 rational = aff_is_rational(aff);
1993 isl_aff_free(aff);
1995 return rational;
1998 /* Can the list of subpieces in the last piece of "data" be extended with
1999 * "set" and "aff" based on "test"?
2000 * In particular, is it the case for each entry (set_i, aff_i) that
2002 * test(aff, aff_i) holds on set_i, and
2003 * test(aff_i, aff) holds on set?
2005 * "test" returns the set of elements where the tests holds, meaning
2006 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2008 * This function is used to detect min/max expressions.
2009 * If the ast_build_detect_min_max option is turned off, then
2010 * do not even try and perform any detection and return false instead.
2012 * Rational affine expressions are not considered for min/max expressions
2013 * since the combined expression will be defined on the union of the domains,
2014 * while a rational expression may only yield integer values
2015 * on its own definition domain.
2017 static isl_bool extends(struct isl_from_pw_aff_data *data,
2018 __isl_keep isl_set *set, __isl_keep isl_aff *aff,
2019 __isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1,
2020 __isl_take isl_aff *aff2))
2022 int i, n;
2023 isl_bool is_rational;
2024 isl_ctx *ctx;
2025 isl_set *dom;
2027 is_rational = aff_is_rational(aff);
2028 if (is_rational >= 0 && !is_rational)
2029 is_rational = is_single_rational_aff(data->p[data->n].aff_list);
2030 if (is_rational < 0 || is_rational)
2031 return isl_bool_not(is_rational);
2033 ctx = isl_ast_build_get_ctx(data->build);
2034 if (!isl_options_get_ast_build_detect_min_max(ctx))
2035 return isl_bool_false;
2037 dom = isl_ast_build_get_domain(data->build);
2038 set = isl_set_intersect(dom, isl_set_copy(set));
2040 n = isl_set_list_n_set(data->p[data->n].set_list);
2041 for (i = 0; i < n ; ++i) {
2042 isl_aff *aff_i;
2043 isl_set *valid;
2044 isl_set *dom, *required;
2045 isl_bool is_valid;
2047 aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2048 valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i));
2049 required = isl_set_list_get_set(data->p[data->n].set_list, i);
2050 dom = isl_ast_build_get_domain(data->build);
2051 required = isl_set_intersect(dom, required);
2052 is_valid = isl_set_is_subset(required, valid);
2053 isl_set_free(required);
2054 isl_set_free(valid);
2055 if (is_valid < 0 || !is_valid) {
2056 isl_set_free(set);
2057 return is_valid;
2060 aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2061 valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff)));
2062 is_valid = isl_set_is_subset(set, valid);
2063 isl_set_free(valid);
2064 if (is_valid < 0 || !is_valid) {
2065 isl_set_free(set);
2066 return is_valid;
2070 isl_set_free(set);
2071 return isl_bool_true;
2074 /* Can the list of pieces in "data" be extended with "set" and "aff"
2075 * to form/preserve a minimum expression?
2076 * In particular, is it the case for each entry (set_i, aff_i) that
2078 * aff >= aff_i on set_i, and
2079 * aff_i >= aff on set?
2081 static isl_bool extends_min(struct isl_from_pw_aff_data *data,
2082 __isl_keep isl_set *set, __isl_keep isl_aff *aff)
2084 return extends(data, set, aff, &isl_aff_ge_basic_set);
2087 /* Can the list of pieces in "data" be extended with "set" and "aff"
2088 * to form/preserve a maximum expression?
2089 * In particular, is it the case for each entry (set_i, aff_i) that
2091 * aff <= aff_i on set_i, and
2092 * aff_i <= aff on set?
2094 static isl_bool extends_max(struct isl_from_pw_aff_data *data,
2095 __isl_keep isl_set *set, __isl_keep isl_aff *aff)
2097 return extends(data, set, aff, &isl_aff_le_basic_set);
2100 /* This function is called during the construction of an isl_ast_expr
2101 * that evaluates an isl_pw_aff.
2102 * If the last piece of "data" contains a single subpiece and
2103 * if its affine function is equal to "aff" on a part of the domain
2104 * that includes either "set" or the domain of that single subpiece,
2105 * then extend the domain of that single subpiece with "set".
2106 * If it was the original domain of the single subpiece where
2107 * the two affine functions are equal, then also replace
2108 * the affine function of the single subpiece by "aff".
2109 * If the last piece of "data" contains either a single subpiece
2110 * or a minimum, then check if this minimum expression can be extended
2111 * with (set, aff).
2112 * If so, extend the sequence and return.
2113 * Perform the same operation for maximum expressions.
2114 * If no such extension can be performed, then move to the next piece
2115 * in "data" (if the current piece contains any data), and then store
2116 * the current subpiece in the current piece of "data" for later handling.
2118 static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,
2119 __isl_take isl_aff *aff, void *user)
2121 struct isl_from_pw_aff_data *data = user;
2122 isl_bool test;
2123 enum isl_from_pw_aff_state state;
2125 state = data->p[data->n].state;
2126 if (state == isl_state_single) {
2127 isl_aff *aff0;
2128 isl_set *eq;
2129 isl_bool subset1, subset2 = isl_bool_false;
2130 aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0);
2131 eq = isl_aff_eq_set(isl_aff_copy(aff), aff0);
2132 subset1 = isl_set_is_subset(set, eq);
2133 if (subset1 >= 0 && !subset1)
2134 subset2 = single_is_subset(data, eq);
2135 isl_set_free(eq);
2136 if (subset1 < 0 || subset2 < 0)
2137 goto error;
2138 if (subset1)
2139 return extend_domain(data, set, aff, 0);
2140 if (subset2)
2141 return extend_domain(data, set, aff, 1);
2143 if (state == isl_state_single || state == isl_state_min) {
2144 test = extends_min(data, set, aff);
2145 if (test < 0)
2146 goto error;
2147 if (test)
2148 return extend_min(data, set, aff);
2150 if (state == isl_state_single || state == isl_state_max) {
2151 test = extends_max(data, set, aff);
2152 if (test < 0)
2153 goto error;
2154 if (test)
2155 return extend_max(data, set, aff);
2157 if (state != isl_state_none)
2158 data->n++;
2159 set_single(data, set, aff);
2161 return isl_stat_ok;
2162 error:
2163 isl_set_free(set);
2164 isl_aff_free(aff);
2165 return isl_stat_error;
2168 /* Construct an isl_ast_expr that evaluates "pa".
2169 * The result is simplified in terms of build->domain.
2171 * The domain of "pa" lives in the internal schedule space.
2173 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
2174 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2176 struct isl_from_pw_aff_data data = { NULL };
2177 isl_ast_expr *res = NULL;
2179 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
2180 pa = isl_pw_aff_coalesce(pa);
2181 if (!pa)
2182 return NULL;
2184 if (isl_from_pw_aff_data_init(&data, build, pa) < 0)
2185 goto error;
2186 set_none(&data);
2188 if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0)
2189 res = build_pieces(&data);
2191 isl_pw_aff_free(pa);
2192 isl_from_pw_aff_data_clear(&data);
2193 return res;
2194 error:
2195 isl_pw_aff_free(pa);
2196 isl_from_pw_aff_data_clear(&data);
2197 return NULL;
2200 /* Construct an isl_ast_expr that evaluates "pa".
2201 * The result is simplified in terms of build->domain.
2203 * The domain of "pa" lives in the external schedule space.
2205 __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
2206 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2208 isl_ast_expr *expr;
2210 if (isl_ast_build_need_schedule_map(build)) {
2211 isl_multi_aff *ma;
2212 ma = isl_ast_build_get_schedule_map_multi_aff(build);
2213 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
2215 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2216 return expr;
2219 /* Set the ids of the input dimensions of "mpa" to the iterator ids
2220 * of "build".
2222 * The domain of "mpa" is assumed to live in the internal schedule domain.
2224 static __isl_give isl_multi_pw_aff *set_iterator_names(
2225 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2227 int i, n;
2229 n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
2230 for (i = 0; i < n; ++i) {
2231 isl_id *id;
2233 id = isl_ast_build_get_iterator_id(build, i);
2234 mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
2237 return mpa;
2240 /* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2241 * the remaining arguments derived from "mpa".
2242 * That is, construct a call or access expression that calls/accesses "arg0"
2243 * with arguments/indices specified by "mpa".
2245 static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
2246 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2247 __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
2249 int i, n;
2250 isl_ctx *ctx;
2251 isl_ast_expr *expr;
2253 ctx = isl_ast_build_get_ctx(build);
2255 n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
2256 expr = isl_ast_expr_alloc_op(ctx, type, 1 + n);
2257 expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
2258 for (i = 0; i < n; ++i) {
2259 isl_pw_aff *pa;
2260 isl_ast_expr *arg;
2262 pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
2263 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2264 expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
2267 isl_multi_pw_aff_free(mpa);
2268 return expr;
2271 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2272 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2273 __isl_take isl_multi_pw_aff *mpa);
2275 /* Construct an isl_ast_expr that accesses the member specified by "mpa".
2276 * The range of "mpa" is assumed to be wrapped relation.
2277 * The domain of this wrapped relation specifies the structure being
2278 * accessed, while the range of this wrapped relation spacifies the
2279 * member of the structure being accessed.
2281 * The domain of "mpa" is assumed to live in the internal schedule domain.
2283 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
2284 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2286 isl_id *id;
2287 isl_multi_pw_aff *domain;
2288 isl_ast_expr *domain_expr, *expr;
2289 enum isl_ast_op_type type = isl_ast_op_access;
2291 domain = isl_multi_pw_aff_copy(mpa);
2292 domain = isl_multi_pw_aff_range_factor_domain(domain);
2293 domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
2294 type, domain);
2295 mpa = isl_multi_pw_aff_range_factor_range(mpa);
2296 if (!isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
2297 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2298 "missing field name", goto error);
2299 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
2300 expr = isl_ast_expr_from_id(id);
2301 expr = isl_ast_expr_alloc_binary(isl_ast_op_member, domain_expr, expr);
2302 return isl_ast_build_with_arguments(build, type, expr, mpa);
2303 error:
2304 isl_multi_pw_aff_free(mpa);
2305 return NULL;
2308 /* Construct an isl_ast_expr of type "type" that calls or accesses
2309 * the element specified by "mpa".
2310 * The first argument is obtained from the output tuple name.
2311 * The remaining arguments are given by the piecewise affine expressions.
2313 * If the range of "mpa" is a mapped relation, then we assume it
2314 * represents an access to a member of a structure.
2316 * The domain of "mpa" is assumed to live in the internal schedule domain.
2318 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2319 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2320 __isl_take isl_multi_pw_aff *mpa)
2322 isl_ctx *ctx;
2323 isl_id *id;
2324 isl_ast_expr *expr;
2326 if (!mpa)
2327 goto error;
2329 if (type == isl_ast_op_access &&
2330 isl_multi_pw_aff_range_is_wrapping(mpa))
2331 return isl_ast_build_from_multi_pw_aff_member(build, mpa);
2333 mpa = set_iterator_names(build, mpa);
2334 if (!build || !mpa)
2335 goto error;
2337 ctx = isl_ast_build_get_ctx(build);
2339 if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
2340 id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
2341 else
2342 id = isl_id_alloc(ctx, "", NULL);
2344 expr = isl_ast_expr_from_id(id);
2345 return isl_ast_build_with_arguments(build, type, expr, mpa);
2346 error:
2347 isl_multi_pw_aff_free(mpa);
2348 return NULL;
2351 /* Construct an isl_ast_expr of type "type" that calls or accesses
2352 * the element specified by "pma".
2353 * The first argument is obtained from the output tuple name.
2354 * The remaining arguments are given by the piecewise affine expressions.
2356 * The domain of "pma" is assumed to live in the internal schedule domain.
2358 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
2359 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2360 __isl_take isl_pw_multi_aff *pma)
2362 isl_multi_pw_aff *mpa;
2364 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2365 return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2368 /* Construct an isl_ast_expr of type "type" that calls or accesses
2369 * the element specified by "mpa".
2370 * The first argument is obtained from the output tuple name.
2371 * The remaining arguments are given by the piecewise affine expressions.
2373 * The domain of "mpa" is assumed to live in the external schedule domain.
2375 static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
2376 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2377 __isl_take isl_multi_pw_aff *mpa)
2379 int is_domain;
2380 isl_ast_expr *expr;
2381 isl_space *space_build, *space_mpa;
2383 space_build = isl_ast_build_get_space(build, 0);
2384 space_mpa = isl_multi_pw_aff_get_space(mpa);
2385 is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,
2386 space_mpa, isl_dim_in);
2387 isl_space_free(space_build);
2388 isl_space_free(space_mpa);
2389 if (is_domain < 0)
2390 goto error;
2391 if (!is_domain)
2392 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2393 "spaces don't match", goto error);
2395 if (isl_ast_build_need_schedule_map(build)) {
2396 isl_multi_aff *ma;
2397 ma = isl_ast_build_get_schedule_map_multi_aff(build);
2398 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
2401 expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2402 return expr;
2403 error:
2404 isl_multi_pw_aff_free(mpa);
2405 return NULL;
2408 /* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2409 * The name of the function is obtained from the output tuple name.
2410 * The arguments are given by the piecewise affine expressions.
2412 * The domain of "mpa" is assumed to live in the external schedule domain.
2414 __isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
2415 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2417 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_call, mpa);
2420 /* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2421 * The name of the array is obtained from the output tuple name.
2422 * The index expressions are given by the piecewise affine expressions.
2424 * The domain of "mpa" is assumed to live in the external schedule domain.
2426 __isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
2427 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2429 return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_access, mpa);
2432 /* Construct an isl_ast_expr of type "type" that calls or accesses
2433 * the element specified by "pma".
2434 * The first argument is obtained from the output tuple name.
2435 * The remaining arguments are given by the piecewise affine expressions.
2437 * The domain of "pma" is assumed to live in the external schedule domain.
2439 static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
2440 __isl_keep isl_ast_build *build, enum isl_ast_op_type type,
2441 __isl_take isl_pw_multi_aff *pma)
2443 isl_multi_pw_aff *mpa;
2445 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2446 return isl_ast_build_from_multi_pw_aff(build, type, mpa);
2449 /* Construct an isl_ast_expr that calls the domain element specified by "pma".
2450 * The name of the function is obtained from the output tuple name.
2451 * The arguments are given by the piecewise affine expressions.
2453 * The domain of "pma" is assumed to live in the external schedule domain.
2455 __isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
2456 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2458 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_call, pma);
2461 /* Construct an isl_ast_expr that accesses the array element specified by "pma".
2462 * The name of the array is obtained from the output tuple name.
2463 * The index expressions are given by the piecewise affine expressions.
2465 * The domain of "pma" is assumed to live in the external schedule domain.
2467 __isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
2468 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2470 return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma);
2473 /* Construct an isl_ast_expr that calls the domain element
2474 * specified by "executed".
2476 * "executed" is assumed to be single-valued, with a domain that lives
2477 * in the internal schedule space.
2479 __isl_give isl_ast_node *isl_ast_build_call_from_executed(
2480 __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
2482 isl_pw_multi_aff *iteration;
2483 isl_ast_expr *expr;
2485 iteration = isl_pw_multi_aff_from_map(executed);
2486 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
2487 iteration = isl_pw_multi_aff_intersect_domain(iteration,
2488 isl_ast_build_get_domain(build));
2489 expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call,
2490 iteration);
2491 return isl_ast_node_alloc_user(expr);