1/*
2 * Copyright 2012-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 *
5 * Use of this software is governed by the MIT license
6 *
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
11 */
12
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>
22
23/* Compute the "opposite" of the (numerator of the) argument of a div
24 * with denominator "d".
25 *
26 * In particular, compute
27 *
28 * -aff + (d - 1)
29 */
30static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
31 __isl_take isl_val *d)
32{
33 aff = isl_aff_neg(aff);
34 aff = isl_aff_add_constant_val(aff, v: d);
35 aff = isl_aff_add_constant_si(aff, v: -1);
36
37 return aff;
38}
39
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 * "ls" is the domain local space of the affine expression
44 * of which a term is being added.
45 * "cst" is the constant term of the expression in which the added term
46 * appears. It may be modified by isl_ast_expr_add_term.
47 *
48 * "v" is the coefficient of the term that is being constructed and
49 * is set internally by isl_ast_expr_add_term.
50 */
51struct isl_ast_add_term_data {
52 isl_ast_build *build;
53 isl_local_space *ls;
54 isl_val *cst;
55 isl_val *v;
56};
57
58/* Given the numerator "aff" of the argument of an integer division
59 * with denominator "d", check if it can be made non-negative over
60 * data->build->domain by stealing part of the constant term of
61 * the expression in which the integer division appears.
62 *
63 * In particular, the outer expression is of the form
64 *
65 * v * floor(aff/d) + cst
66 *
67 * We already know that "aff" itself may attain negative values.
68 * Here we check if aff + d*floor(cst/v) is non-negative, such
69 * that we could rewrite the expression to
70 *
71 * v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
72 *
73 * Note that aff + d*floor(cst/v) can only possibly be non-negative
74 * if data->cst and data->v have the same sign.
75 * Similarly, if floor(cst/v) is zero, then there is no point in
76 * checking again.
77 */
78static isl_bool is_non_neg_after_stealing(__isl_keep isl_aff *aff,
79 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
80{
81 isl_aff *shifted;
82 isl_val *shift;
83 isl_bool is_zero;
84 isl_bool non_neg;
85
86 if (isl_val_sgn(v: data->cst) != isl_val_sgn(v: data->v))
87 return isl_bool_false;
88
89 shift = isl_val_div(v1: isl_val_copy(v: data->cst), v2: isl_val_copy(v: data->v));
90 shift = isl_val_floor(v: shift);
91 is_zero = isl_val_is_zero(v: shift);
92 if (is_zero < 0 || is_zero) {
93 isl_val_free(v: shift);
94 return isl_bool_not(b: is_zero);
95 }
96 shift = isl_val_mul(v1: shift, v2: isl_val_copy(v: d));
97 shifted = isl_aff_copy(aff);
98 shifted = isl_aff_add_constant_val(aff: shifted, v: shift);
99 non_neg = isl_ast_build_aff_is_nonneg(build: data->build, aff: shifted);
100 isl_aff_free(aff: shifted);
101
102 return non_neg;
103}
104
105/* Given the numerator "aff" of the argument of an integer division
106 * with denominator "d", steal part of the constant term of
107 * the expression in which the integer division appears to make it
108 * non-negative over data->build->domain.
109 *
110 * In particular, the outer expression is of the form
111 *
112 * v * floor(aff/d) + cst
113 *
114 * We know that "aff" itself may attain negative values,
115 * but that aff + d*floor(cst/v) is non-negative.
116 * Find the minimal positive value that we need to add to "aff"
117 * to make it positive and adjust data->cst accordingly.
118 * That is, compute the minimal value "m" of "aff" over
119 * data->build->domain and take
120 *
121 * s = ceil(-m/d)
122 *
123 * such that
124 *
125 * aff + d * s >= 0
126 *
127 * and rewrite the expression to
128 *
129 * v * floor((aff + s*d)/d) + (cst - v*s)
130 */
131static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
132 __isl_keep isl_val *d, struct isl_ast_add_term_data *data)
133{
134 isl_set *domain;
135 isl_val *shift, *t;
136
137 domain = isl_ast_build_get_domain(build: data->build);
138 shift = isl_set_min_val(set: domain, obj: aff);
139 isl_set_free(set: domain);
140
141 shift = isl_val_neg(v: shift);
142 shift = isl_val_div(v1: shift, v2: isl_val_copy(v: d));
143 shift = isl_val_ceil(v: shift);
144
145 t = isl_val_copy(v: shift);
146 t = isl_val_mul(v1: t, v2: isl_val_copy(v: data->v));
147 data->cst = isl_val_sub(v1: data->cst, v2: t);
148
149 shift = isl_val_mul(v1: shift, v2: isl_val_copy(v: d));
150 return isl_aff_add_constant_val(aff, v: shift);
151}
152
153/* Construct an expression representing the binary operation "type"
154 * (some division or modulo) applied to the expressions
155 * constructed from "aff" and "v".
156 */
157static __isl_give isl_ast_expr *div_mod(enum isl_ast_expr_op_type type,
158 __isl_take isl_aff *aff, __isl_take isl_val *v,
159 __isl_keep isl_ast_build *build)
160{
161 isl_ast_expr *expr1, *expr2;
162
163 expr1 = isl_ast_expr_from_aff(aff, build);
164 expr2 = isl_ast_expr_from_val(v);
165 return isl_ast_expr_alloc_binary(type, expr1, expr2);
166}
167
168/* Create an isl_ast_expr evaluating the div at position "pos" in data->ls.
169 * The result is simplified in terms of data->build->domain.
170 * This function may change (the sign of) data->v.
171 *
172 * data->ls is known to be non-NULL.
173 *
174 * Let the div be of the form floor(e/d).
175 * If the ast_build_prefer_pdiv option is set then we check if "e"
176 * is non-negative, so that we can generate
177 *
178 * (pdiv_q, expr(e), expr(d))
179 *
180 * instead of
181 *
182 * (fdiv_q, expr(e), expr(d))
183 *
184 * If the ast_build_prefer_pdiv option is set and
185 * if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
186 * If so, we can rewrite
187 *
188 * floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
189 *
190 * and still use pdiv_q, while changing the sign of data->v.
191 *
192 * Otherwise, we check if
193 *
194 * e + d*floor(cst/v)
195 *
196 * is non-negative and if so, replace floor(e/d) by
197 *
198 * floor((e + s*d)/d) - s
199 *
200 * with s the minimal shift that makes the argument non-negative.
201 */
202static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,
203 int pos)
204{
205 isl_ctx *ctx = isl_local_space_get_ctx(ls: data->ls);
206 isl_aff *aff;
207 isl_val *d;
208 enum isl_ast_expr_op_type type;
209
210 aff = isl_local_space_get_div(ls: data->ls, pos);
211 d = isl_aff_get_denominator_val(aff);
212 aff = isl_aff_scale_val(aff, v: isl_val_copy(v: d));
213
214 type = isl_ast_expr_op_fdiv_q;
215 if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
216 isl_bool non_neg;
217 non_neg = isl_ast_build_aff_is_nonneg(build: data->build, aff);
218 if (non_neg >= 0 && !non_neg) {
219 isl_aff *opp = oppose_div_arg(aff: isl_aff_copy(aff),
220 d: isl_val_copy(v: d));
221 non_neg = isl_ast_build_aff_is_nonneg(build: data->build, aff: opp);
222 if (non_neg >= 0 && non_neg) {
223 data->v = isl_val_neg(v: data->v);
224 isl_aff_free(aff);
225 aff = opp;
226 } else
227 isl_aff_free(aff: opp);
228 }
229 if (non_neg >= 0 && !non_neg) {
230 non_neg = is_non_neg_after_stealing(aff, d, data);
231 if (non_neg >= 0 && non_neg)
232 aff = steal_from_cst(aff, d, data);
233 }
234 if (non_neg < 0)
235 aff = isl_aff_free(aff);
236 else if (non_neg)
237 type = isl_ast_expr_op_pdiv_q;
238 }
239
240 return div_mod(type, aff, v: d, build: data->build);
241}
242
243/* Create an isl_ast_expr evaluating the specified dimension of data->ls.
244 * The result is simplified in terms of data->build->domain.
245 * This function may change (the sign of) data->v.
246 *
247 * The isl_ast_expr is constructed based on the type of the dimension.
248 * - divs are constructed by var_div
249 * - set variables are constructed from the iterator isl_ids in data->build
250 * - parameters are constructed from the isl_ids in data->ls
251 */
252static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
253 enum isl_dim_type type, int pos)
254{
255 isl_ctx *ctx = isl_local_space_get_ctx(ls: data->ls);
256 isl_id *id;
257
258 if (type == isl_dim_div)
259 return var_div(data, pos);
260
261 if (type == isl_dim_set) {
262 id = isl_ast_build_get_iterator_id(build: data->build, pos);
263 return isl_ast_expr_from_id(id);
264 }
265
266 if (!isl_local_space_has_dim_id(ls: data->ls, type, pos))
267 isl_die(ctx, isl_error_internal, "unnamed dimension",
268 return NULL);
269 id = isl_local_space_get_dim_id(ls: data->ls, type, pos);
270 return isl_ast_expr_from_id(id);
271}
272
273/* Does "expr" represent the zero integer?
274 */
275static isl_bool ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
276{
277 if (!expr)
278 return isl_bool_error;
279 if (expr->type != isl_ast_expr_int)
280 return isl_bool_false;
281 return isl_val_is_zero(v: expr->u.v);
282}
283
284/* Create an expression representing the sum of "expr1" and "expr2",
285 * provided neither of the two expressions is identically zero.
286 */
287static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
288 __isl_take isl_ast_expr *expr2)
289{
290 if (!expr1 || !expr2)
291 goto error;
292
293 if (ast_expr_is_zero(expr: expr1)) {
294 isl_ast_expr_free(expr: expr1);
295 return expr2;
296 }
297
298 if (ast_expr_is_zero(expr: expr2)) {
299 isl_ast_expr_free(expr: expr2);
300 return expr1;
301 }
302
303 return isl_ast_expr_add(expr1, expr2);
304error:
305 isl_ast_expr_free(expr: expr1);
306 isl_ast_expr_free(expr: expr2);
307 return NULL;
308}
309
310/* Subtract expr2 from expr1.
311 *
312 * If expr2 is zero, we simply return expr1.
313 * If expr1 is zero, we return
314 *
315 * (isl_ast_expr_op_minus, expr2)
316 *
317 * Otherwise, we return
318 *
319 * (isl_ast_expr_op_sub, expr1, expr2)
320 */
321static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
322 __isl_take isl_ast_expr *expr2)
323{
324 if (!expr1 || !expr2)
325 goto error;
326
327 if (ast_expr_is_zero(expr: expr2)) {
328 isl_ast_expr_free(expr: expr2);
329 return expr1;
330 }
331
332 if (ast_expr_is_zero(expr: expr1)) {
333 isl_ast_expr_free(expr: expr1);
334 return isl_ast_expr_neg(expr: expr2);
335 }
336
337 return isl_ast_expr_sub(expr1, expr2);
338error:
339 isl_ast_expr_free(expr: expr1);
340 isl_ast_expr_free(expr: expr2);
341 return NULL;
342}
343
344/* Return an isl_ast_expr that represents
345 *
346 * v * (aff mod d)
347 *
348 * v is assumed to be non-negative.
349 * The result is simplified in terms of build->domain.
350 */
351static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
352 __isl_keep isl_aff *aff, __isl_keep isl_val *d,
353 __isl_keep isl_ast_build *build)
354{
355 isl_ast_expr *expr;
356 isl_ast_expr *c;
357
358 if (!aff)
359 return NULL;
360
361 expr = div_mod(type: isl_ast_expr_op_pdiv_r,
362 aff: isl_aff_copy(aff), v: isl_val_copy(v: d), build);
363
364 if (!isl_val_is_one(v)) {
365 c = isl_ast_expr_from_val(v: isl_val_copy(v));
366 expr = isl_ast_expr_mul(expr1: c, expr2: expr);
367 }
368
369 return expr;
370}
371
372/* Create an isl_ast_expr that scales "expr" by "v".
373 *
374 * If v is 1, we simply return expr.
375 * If v is -1, we return
376 *
377 * (isl_ast_expr_op_minus, expr)
378 *
379 * Otherwise, we return
380 *
381 * (isl_ast_expr_op_mul, expr(v), expr)
382 */
383static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
384 __isl_take isl_val *v)
385{
386 isl_ast_expr *c;
387
388 if (!expr || !v)
389 goto error;
390 if (isl_val_is_one(v)) {
391 isl_val_free(v);
392 return expr;
393 }
394
395 if (isl_val_is_negone(v)) {
396 isl_val_free(v);
397 expr = isl_ast_expr_neg(expr);
398 } else {
399 c = isl_ast_expr_from_val(v);
400 expr = isl_ast_expr_mul(expr1: c, expr2: expr);
401 }
402
403 return expr;
404error:
405 isl_val_free(v);
406 isl_ast_expr_free(expr);
407 return NULL;
408}
409
410/* Add an expression for "*v" times the specified dimension of data->ls
411 * to expr.
412 * If the dimension is an integer division, then this function
413 * may modify data->cst in order to make the numerator non-negative.
414 * The result is simplified in terms of data->build->domain.
415 *
416 * Let e be the expression for the specified dimension,
417 * multiplied by the absolute value of "*v".
418 * If "*v" is negative, we create
419 *
420 * (isl_ast_expr_op_sub, expr, e)
421 *
422 * except when expr is trivially zero, in which case we create
423 *
424 * (isl_ast_expr_op_minus, e)
425 *
426 * instead.
427 *
428 * If "*v" is positive, we simply create
429 *
430 * (isl_ast_expr_op_add, expr, e)
431 *
432 */
433static __isl_give isl_ast_expr *isl_ast_expr_add_term(
434 __isl_take isl_ast_expr *expr, enum isl_dim_type type, int pos,
435 __isl_take isl_val *v, struct isl_ast_add_term_data *data)
436{
437 isl_ast_expr *term;
438
439 if (!expr)
440 return NULL;
441
442 data->v = v;
443 term = var(data, type, pos);
444 v = data->v;
445
446 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
447 v = isl_val_neg(v);
448 term = scale(expr: term, v);
449 return ast_expr_sub(expr1: expr, expr2: term);
450 } else {
451 term = scale(expr: term, v);
452 return ast_expr_add(expr1: expr, expr2: term);
453 }
454}
455
456/* Add an expression for "v" to expr.
457 */
458static __isl_give isl_ast_expr *isl_ast_expr_add_int(
459 __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
460{
461 isl_ast_expr *expr_int;
462
463 if (!expr || !v)
464 goto error;
465
466 if (isl_val_is_zero(v)) {
467 isl_val_free(v);
468 return expr;
469 }
470
471 if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
472 v = isl_val_neg(v);
473 expr_int = isl_ast_expr_from_val(v);
474 return ast_expr_sub(expr1: expr, expr2: expr_int);
475 } else {
476 expr_int = isl_ast_expr_from_val(v);
477 return ast_expr_add(expr1: expr, expr2: expr_int);
478 }
479error:
480 isl_ast_expr_free(expr);
481 isl_val_free(v);
482 return NULL;
483}
484
485/* Internal data structure used inside extract_modulos.
486 *
487 * If any modulo expressions are detected in "aff", then the
488 * expression is removed from "aff" and added to either "pos" or "neg"
489 * depending on the sign of the coefficient of the modulo expression
490 * inside "aff".
491 *
492 * "add" is an expression that needs to be added to "aff" at the end of
493 * the computation. It is NULL as long as no modulos have been extracted.
494 *
495 * "i" is the position in "aff" of the div under investigation
496 * "v" is the coefficient in "aff" of the div
497 * "div" is the argument of the div, with the denominator removed
498 * "d" is the original denominator of the argument of the div
499 *
500 * "nonneg" is an affine expression that is non-negative over "build"
501 * and that can be used to extract a modulo expression from "div".
502 * In particular, if "sign" is 1, then the coefficients of "nonneg"
503 * are equal to those of "div" modulo "d". If "sign" is -1, then
504 * the coefficients of "nonneg" are opposite to those of "div" modulo "d".
505 * If "sign" is 0, then no such affine expression has been found (yet).
506 */
507struct isl_extract_mod_data {
508 isl_ast_build *build;
509 isl_aff *aff;
510
511 isl_ast_expr *pos;
512 isl_ast_expr *neg;
513
514 isl_aff *add;
515
516 int i;
517 isl_val *v;
518 isl_val *d;
519 isl_aff *div;
520
521 isl_aff *nonneg;
522 int sign;
523};
524
525/* Does
526 *
527 * arg mod data->d
528 *
529 * represent (a special case of) a test for some linear expression
530 * being even?
531 *
532 * In particular, is it of the form
533 *
534 * (lin - 1) mod 2
535 *
536 * ?
537 */
538static isl_bool is_even_test(struct isl_extract_mod_data *data,
539 __isl_keep isl_aff *arg)
540{
541 isl_bool res;
542 isl_val *cst;
543
544 res = isl_val_eq_si(v: data->d, i: 2);
545 if (res < 0 || !res)
546 return res;
547
548 cst = isl_aff_get_constant_val(aff: arg);
549 res = isl_val_eq_si(v: cst, i: -1);
550 isl_val_free(v: cst);
551
552 return res;
553}
554
555/* Given that data->v * div_i in data->aff is equal to
556 *
557 * f * (term - (arg mod d))
558 *
559 * with data->d * f = data->v and "arg" non-negative on data->build, add
560 *
561 * f * term
562 *
563 * to data->add and
564 *
565 * abs(f) * (arg mod d)
566 *
567 * to data->neg or data->pos depending on the sign of -f.
568 *
569 * In the special case that "arg mod d" is of the form "(lin - 1) mod 2",
570 * with "lin" some linear expression, first replace
571 *
572 * f * (term - ((lin - 1) mod 2))
573 *
574 * by
575 *
576 * -f * (1 - term - (lin mod 2))
577 *
578 * These two are equal because
579 *
580 * ((lin - 1) mod 2) + (lin mod 2) = 1
581 *
582 * Also, if "lin - 1" is non-negative, then "lin" is non-negative too.
583 */
584static isl_stat extract_term_and_mod(struct isl_extract_mod_data *data,
585 __isl_take isl_aff *term, __isl_take isl_aff *arg)
586{
587 isl_bool even;
588 isl_ast_expr *expr;
589 int s;
590
591 even = is_even_test(data, arg);
592 if (even < 0) {
593 arg = isl_aff_free(aff: arg);
594 } else if (even) {
595 term = oppose_div_arg(aff: term, d: isl_val_copy(v: data->d));
596 data->v = isl_val_neg(v: data->v);
597 arg = isl_aff_set_constant_si(aff: arg, v: 0);
598 }
599
600 data->v = isl_val_div(v1: data->v, v2: isl_val_copy(v: data->d));
601 s = isl_val_sgn(v: data->v);
602 data->v = isl_val_abs(v: data->v);
603 expr = isl_ast_expr_mod(v: data->v, aff: arg, d: data->d, build: data->build);
604 isl_aff_free(aff: arg);
605 if (s > 0)
606 data->neg = ast_expr_add(expr1: data->neg, expr2: expr);
607 else
608 data->pos = ast_expr_add(expr1: data->pos, expr2: expr);
609 data->aff = isl_aff_set_coefficient_si(aff: data->aff,
610 type: isl_dim_div, pos: data->i, v: 0);
611 if (s < 0)
612 data->v = isl_val_neg(v: data->v);
613 term = isl_aff_scale_val(aff: term, v: isl_val_copy(v: data->v));
614
615 if (!data->add)
616 data->add = term;
617 else
618 data->add = isl_aff_add(aff1: data->add, aff2: term);
619 if (!data->add)
620 return isl_stat_error;
621
622 return isl_stat_ok;
623}
624
625/* Given that data->v * div_i in data->aff is of the form
626 *
627 * f * d * floor(div/d)
628 *
629 * with div nonnegative on data->build, rewrite it as
630 *
631 * f * (div - (div mod d)) = f * div - f * (div mod d)
632 *
633 * and add
634 *
635 * f * div
636 *
637 * to data->add and
638 *
639 * abs(f) * (div mod d)
640 *
641 * to data->neg or data->pos depending on the sign of -f.
642 */
643static isl_stat extract_mod(struct isl_extract_mod_data *data)
644{
645 return extract_term_and_mod(data, term: isl_aff_copy(aff: data->div),
646 arg: isl_aff_copy(aff: data->div));
647}
648
649/* Given that data->v * div_i in data->aff is of the form
650 *
651 * f * d * floor(div/d) (1)
652 *
653 * check if div is non-negative on data->build and, if so,
654 * extract the corresponding modulo from data->aff.
655 * If not, then check if
656 *
657 * -div + d - 1
658 *
659 * is non-negative on data->build. If so, replace (1) by
660 *
661 * -f * d * floor((-div + d - 1)/d)
662 *
663 * and extract the corresponding modulo from data->aff.
664 *
665 * This function may modify data->div.
666 */
667static isl_stat extract_nonneg_mod(struct isl_extract_mod_data *data)
668{
669 isl_bool mod;
670
671 mod = isl_ast_build_aff_is_nonneg(build: data->build, aff: data->div);
672 if (mod < 0)
673 goto error;
674 if (mod)
675 return extract_mod(data);
676
677 data->div = oppose_div_arg(aff: data->div, d: isl_val_copy(v: data->d));
678 mod = isl_ast_build_aff_is_nonneg(build: data->build, aff: data->div);
679 if (mod < 0)
680 goto error;
681 if (mod) {
682 data->v = isl_val_neg(v: data->v);
683 return extract_mod(data);
684 }
685
686 return isl_stat_ok;
687error:
688 data->aff = isl_aff_free(aff: data->aff);
689 return isl_stat_error;
690}
691
692/* Is the affine expression of constraint "c" "simpler" than data->nonneg
693 * for use in extracting a modulo expression?
694 *
695 * We currently only consider the constant term of the affine expression.
696 * In particular, we prefer the affine expression with the smallest constant
697 * term.
698 * This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
699 * then we would pick x >= 0
700 *
701 * More detailed heuristics could be used if it turns out that there is a need.
702 */
703static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
704 __isl_keep isl_constraint *c)
705{
706 isl_val *v1, *v2;
707 int simpler;
708
709 if (!data->nonneg)
710 return 1;
711
712 v1 = isl_val_abs(v: isl_constraint_get_constant_val(constraint: c));
713 v2 = isl_val_abs(v: isl_aff_get_constant_val(aff: data->nonneg));
714 simpler = isl_val_lt(v1, v2);
715 isl_val_free(v: v1);
716 isl_val_free(v: v2);
717
718 return simpler;
719}
720
721/* Check if the coefficients of "c" are either equal or opposite to those
722 * of data->div modulo data->d. If so, and if "c" is "simpler" than
723 * data->nonneg, then replace data->nonneg by the affine expression of "c"
724 * and set data->sign accordingly.
725 *
726 * Both "c" and data->div are assumed not to involve any integer divisions.
727 *
728 * Before we start the actual comparison, we first quickly check if
729 * "c" and data->div have the same non-zero coefficients.
730 * If not, then we assume that "c" is not of the desired form.
731 * Note that while the coefficients of data->div can be reasonably expected
732 * not to involve any coefficients that are multiples of d, "c" may
733 * very well involve such coefficients. This means that we may actually
734 * miss some cases.
735 *
736 * If the constant term is "too large", then the constraint is rejected,
737 * where "too large" is fairly arbitrarily set to 1 << 15.
738 * We do this to avoid picking up constraints that bound a variable
739 * by a very large number, say the largest or smallest possible
740 * variable in the representation of some integer type.
741 */
742static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
743 void *user)
744{
745 struct isl_extract_mod_data *data = user;
746 enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
747 enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
748 int i, t;
749 isl_size n[2];
750 isl_bool parallel = isl_bool_true, opposite = isl_bool_true;
751
752 for (t = 0; t < 2; ++t) {
753 n[t] = isl_constraint_dim(constraint: c, type: c_type[t]);
754 if (n[t] < 0)
755 goto error;
756 for (i = 0; i < n[t]; ++i) {
757 isl_bool a, b;
758
759 a = isl_constraint_involves_dims(constraint: c, type: c_type[t], first: i, n: 1);
760 b = isl_aff_involves_dims(aff: data->div, type: a_type[t], first: i, n: 1);
761 if (a < 0 || b < 0)
762 goto error;
763 if (a != b)
764 parallel = opposite = isl_bool_false;
765 }
766 }
767
768 if (parallel || opposite) {
769 isl_val *v;
770
771 v = isl_val_abs(v: isl_constraint_get_constant_val(constraint: c));
772 if (isl_val_cmp_si(v, i: 1 << 15) > 0)
773 parallel = opposite = isl_bool_false;
774 isl_val_free(v);
775 }
776
777 for (t = 0; t < 2; ++t) {
778 for (i = 0; i < n[t]; ++i) {
779 isl_val *v1, *v2;
780
781 if (!parallel && !opposite)
782 break;
783 v1 = isl_constraint_get_coefficient_val(constraint: c,
784 type: c_type[t], pos: i);
785 v2 = isl_aff_get_coefficient_val(aff: data->div,
786 type: a_type[t], pos: i);
787 if (parallel) {
788 v1 = isl_val_sub(v1, v2: isl_val_copy(v: v2));
789 parallel = isl_val_is_divisible_by(v1, v2: data->d);
790 v1 = isl_val_add(v1, v2: isl_val_copy(v: v2));
791 }
792 if (opposite) {
793 v1 = isl_val_add(v1, v2: isl_val_copy(v: v2));
794 opposite = isl_val_is_divisible_by(v1, v2: data->d);
795 }
796 isl_val_free(v: v1);
797 isl_val_free(v: v2);
798 if (parallel < 0 || opposite < 0)
799 goto error;
800 }
801 }
802
803 if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {
804 isl_aff_free(aff: data->nonneg);
805 data->nonneg = isl_constraint_get_aff(constraint: c);
806 data->sign = parallel ? 1 : -1;
807 }
808
809 isl_constraint_free(c);
810
811 if (data->sign != 0 && data->nonneg == NULL)
812 return isl_stat_error;
813
814 return isl_stat_ok;
815error:
816 isl_constraint_free(c);
817 return isl_stat_error;
818}
819
820/* Given that data->v * div_i in data->aff is of the form
821 *
822 * f * d * floor(div/d) (1)
823 *
824 * see if we can find an expression div' that is non-negative over data->build
825 * and that is related to div through
826 *
827 * div' = div + d * e
828 *
829 * or
830 *
831 * div' = -div + d - 1 + d * e
832 *
833 * with e some affine expression.
834 * If so, we write (1) as
835 *
836 * f * div + f * (div' mod d)
837 *
838 * or
839 *
840 * -f * (-div + d - 1) - f * (div' mod d)
841 *
842 * exploiting (in the second case) the fact that
843 *
844 * f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
845 *
846 *
847 * We first try to find an appropriate expression for div'
848 * from the constraints of data->build->domain (which is therefore
849 * guaranteed to be non-negative on data->build), where we remove
850 * any integer divisions from the constraints and skip this step
851 * if "div" itself involves any integer divisions.
852 * If we cannot find an appropriate expression this way, then
853 * we pass control to extract_nonneg_mod where check
854 * if div or "-div + d -1" themselves happen to be
855 * non-negative on data->build.
856 *
857 * While looking for an appropriate constraint in data->build->domain,
858 * we ignore the constant term, so after finding such a constraint,
859 * we still need to fix up the constant term.
860 * In particular, if a is the constant term of "div"
861 * (or d - 1 - the constant term of "div" if data->sign < 0)
862 * and b is the constant term of the constraint, then we need to find
863 * a non-negative constant c such that
864 *
865 * b + c \equiv a mod d
866 *
867 * We therefore take
868 *
869 * c = (a - b) mod d
870 *
871 * and add it to b to obtain the constant term of div'.
872 * If this constant term is "too negative", then we add an appropriate
873 * multiple of d to make it positive.
874 *
875 *
876 * Note that the above is only a very simple heuristic for finding an
877 * appropriate expression. We could try a bit harder by also considering
878 * sums of constraints that involve disjoint sets of variables or
879 * we could consider arbitrary linear combinations of constraints,
880 * although that could potentially be much more expensive as it involves
881 * the solution of an LP problem.
882 *
883 * In particular, if v_i is a column vector representing constraint i,
884 * w represents div and e_i is the i-th unit vector, then we are looking
885 * for a solution of the constraints
886 *
887 * \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
888 *
889 * with \lambda_i >= 0 and alpha_i of unrestricted sign.
890 * If we are not just interested in a non-negative expression, but
891 * also in one with a minimal range, then we don't just want
892 * c = \sum_i lambda_i v_i to be non-negative over the domain,
893 * but also beta - c = \sum_i mu_i v_i, where beta is a scalar
894 * that we want to minimize and we now also have to take into account
895 * the constant terms of the constraints.
896 * Alternatively, we could first compute the dual of the domain
897 * and plug in the constraints on the coefficients.
898 */
899static isl_stat try_extract_mod(struct isl_extract_mod_data *data)
900{
901 isl_basic_set *hull;
902 isl_val *v1, *v2;
903 isl_stat r;
904 isl_size n;
905
906 if (!data->build)
907 goto error;
908
909 n = isl_aff_dim(aff: data->div, type: isl_dim_div);
910 if (n < 0)
911 goto error;
912
913 if (isl_aff_involves_dims(aff: data->div, type: isl_dim_div, first: 0, n))
914 return extract_nonneg_mod(data);
915
916 hull = isl_set_simple_hull(set: isl_set_copy(set: data->build->domain));
917 hull = isl_basic_set_remove_divs(bset: hull);
918 data->sign = 0;
919 data->nonneg = NULL;
920 r = isl_basic_set_foreach_constraint(bset: hull, fn: &check_parallel_or_opposite,
921 user: data);
922 isl_basic_set_free(bset: hull);
923
924 if (!data->sign || r < 0) {
925 isl_aff_free(aff: data->nonneg);
926 if (r < 0)
927 goto error;
928 return extract_nonneg_mod(data);
929 }
930
931 v1 = isl_aff_get_constant_val(aff: data->div);
932 v2 = isl_aff_get_constant_val(aff: data->nonneg);
933 if (data->sign < 0) {
934 v1 = isl_val_neg(v: v1);
935 v1 = isl_val_add(v1, v2: isl_val_copy(v: data->d));
936 v1 = isl_val_sub_ui(v1, v2: 1);
937 }
938 v1 = isl_val_sub(v1, v2: isl_val_copy(v: v2));
939 v1 = isl_val_mod(v1, v2: isl_val_copy(v: data->d));
940 v1 = isl_val_add(v1, v2);
941 v2 = isl_val_div(v1: isl_val_copy(v: v1), v2: isl_val_copy(v: data->d));
942 v2 = isl_val_ceil(v: v2);
943 if (isl_val_is_neg(v: v2)) {
944 v2 = isl_val_mul(v1: v2, v2: isl_val_copy(v: data->d));
945 v1 = isl_val_sub(v1, v2: isl_val_copy(v: v2));
946 }
947 data->nonneg = isl_aff_set_constant_val(aff: data->nonneg, v: v1);
948 isl_val_free(v: v2);
949
950 if (data->sign < 0) {
951 data->div = oppose_div_arg(aff: data->div, d: isl_val_copy(v: data->d));
952 data->v = isl_val_neg(v: data->v);
953 }
954
955 return extract_term_and_mod(data,
956 term: isl_aff_copy(aff: data->div), arg: data->nonneg);
957error:
958 data->aff = isl_aff_free(aff: data->aff);
959 return isl_stat_error;
960}
961
962/* Check if "data->aff" involves any (implicit) modulo computations based
963 * on div "data->i".
964 * If so, remove them from aff and add expressions corresponding
965 * to those modulo computations to data->pos and/or data->neg.
966 *
967 * "aff" is assumed to be an integer affine expression.
968 *
969 * In particular, check if (v * div_j) is of the form
970 *
971 * f * m * floor(a / m)
972 *
973 * and, if so, rewrite it as
974 *
975 * f * (a - (a mod m)) = f * a - f * (a mod m)
976 *
977 * and extract out -f * (a mod m).
978 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
979 * If f < 0, we add ((-f) * (a mod m)) to *pos.
980 *
981 * Note that in order to represent "a mod m" as
982 *
983 * (isl_ast_expr_op_pdiv_r, a, m)
984 *
985 * we need to make sure that a is non-negative.
986 * If not, we check if "-a + m - 1" is non-negative.
987 * If so, we can rewrite
988 *
989 * floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
990 *
991 * and still extract a modulo.
992 */
993static int extract_modulo(struct isl_extract_mod_data *data)
994{
995 data->div = isl_aff_get_div(aff: data->aff, pos: data->i);
996 data->d = isl_aff_get_denominator_val(aff: data->div);
997 if (isl_val_is_divisible_by(v1: data->v, v2: data->d)) {
998 data->div = isl_aff_scale_val(aff: data->div, v: isl_val_copy(v: data->d));
999 if (try_extract_mod(data) < 0)
1000 data->aff = isl_aff_free(aff: data->aff);
1001 }
1002 isl_aff_free(aff: data->div);
1003 isl_val_free(v: data->d);
1004 return 0;
1005}
1006
1007/* Check if "aff" involves any (implicit) modulo computations.
1008 * If so, remove them from aff and add expressions corresponding
1009 * to those modulo computations to *pos and/or *neg.
1010 * We only do this if the option ast_build_prefer_pdiv is set.
1011 *
1012 * "aff" is assumed to be an integer affine expression.
1013 *
1014 * A modulo expression is of the form
1015 *
1016 * a mod m = a - m * floor(a / m)
1017 *
1018 * To detect them in aff, we look for terms of the form
1019 *
1020 * f * m * floor(a / m)
1021 *
1022 * rewrite them as
1023 *
1024 * f * (a - (a mod m)) = f * a - f * (a mod m)
1025 *
1026 * and extract out -f * (a mod m).
1027 * In particular, if f > 0, we add (f * (a mod m)) to *neg.
1028 * If f < 0, we add ((-f) * (a mod m)) to *pos.
1029 */
1030static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
1031 __isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
1032 __isl_keep isl_ast_build *build)
1033{
1034 struct isl_extract_mod_data data = { build, aff, *pos, *neg };
1035 isl_ctx *ctx;
1036 isl_size n;
1037
1038 if (!aff)
1039 return NULL;
1040
1041 ctx = isl_aff_get_ctx(aff);
1042 if (!isl_options_get_ast_build_prefer_pdiv(ctx))
1043 return aff;
1044
1045 n = isl_aff_dim(aff: data.aff, type: isl_dim_div);
1046 if (n < 0)
1047 return isl_aff_free(aff);
1048 for (data.i = 0; data.i < n; ++data.i) {
1049 data.v = isl_aff_get_coefficient_val(aff: data.aff,
1050 type: isl_dim_div, pos: data.i);
1051 if (!data.v)
1052 return isl_aff_free(aff);
1053 if (isl_val_is_zero(v: data.v) ||
1054 isl_val_is_one(v: data.v) || isl_val_is_negone(v: data.v)) {
1055 isl_val_free(v: data.v);
1056 continue;
1057 }
1058 if (extract_modulo(data: &data) < 0)
1059 data.aff = isl_aff_free(aff: data.aff);
1060 isl_val_free(v: data.v);
1061 if (!data.aff)
1062 break;
1063 }
1064
1065 if (data.add)
1066 data.aff = isl_aff_add(aff1: data.aff, aff2: data.add);
1067
1068 *pos = data.pos;
1069 *neg = data.neg;
1070 return data.aff;
1071}
1072
1073/* Call "fn" on every non-zero coefficient of "aff",
1074 * passing it in the type of dimension (in terms of the domain),
1075 * the position and the value, as long as "fn" returns isl_bool_true.
1076 * If "reverse" is set, then the coefficients are considered in reverse order
1077 * within each type.
1078 */
1079static isl_bool every_non_zero_coefficient(__isl_keep isl_aff *aff,
1080 int reverse,
1081 isl_bool (*fn)(enum isl_dim_type type, int pos, __isl_take isl_val *v,
1082 void *user),
1083 void *user)
1084{
1085 int i, j;
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_val *v;
1089
1090 for (i = 0; i < 3; ++i) {
1091 isl_size n;
1092
1093 n = isl_aff_dim(aff, type: t[i]);
1094 if (n < 0)
1095 return isl_bool_error;
1096 for (j = 0; j < n; ++j) {
1097 isl_bool ok;
1098 int pos;
1099
1100 pos = reverse ? n - 1 - j : j;
1101 v = isl_aff_get_coefficient_val(aff, type: t[i], pos);
1102 ok = isl_val_is_zero(v);
1103 if (ok >= 0 && !ok)
1104 ok = fn(l[i], pos, v, user);
1105 else
1106 isl_val_free(v);
1107 if (ok < 0 || !ok)
1108 return ok;
1109 }
1110 }
1111
1112 return isl_bool_true;
1113}
1114
1115/* Internal data structure for extract_rational.
1116 *
1117 * "d" is the denominator of the original affine expression.
1118 * "ls" is its domain local space.
1119 * "rat" collects the rational part.
1120 */
1121struct isl_ast_extract_rational_data {
1122 isl_val *d;
1123 isl_local_space *ls;
1124
1125 isl_aff *rat;
1126};
1127
1128/* Given a non-zero term in an affine expression equal to "v" times
1129 * the variable of type "type" at position "pos",
1130 * add it to data->rat if "v" is not a multiple of data->d.
1131 */
1132static isl_bool add_rational(enum isl_dim_type type, int pos,
1133 __isl_take isl_val *v, void *user)
1134{
1135 struct isl_ast_extract_rational_data *data = user;
1136 isl_aff *rat;
1137
1138 if (isl_val_is_divisible_by(v1: v, v2: data->d)) {
1139 isl_val_free(v);
1140 return isl_bool_true;
1141 }
1142 rat = isl_aff_var_on_domain(ls: isl_local_space_copy(ls: data->ls), type, pos);
1143 rat = isl_aff_scale_val(aff: rat, v);
1144 data->rat = isl_aff_add(aff1: data->rat, aff2: rat);
1145 return isl_bool_true;
1146}
1147
1148/* Check if aff involves any non-integer coefficients.
1149 * If so, split aff into
1150 *
1151 * aff = aff1 + (aff2 / d)
1152 *
1153 * with both aff1 and aff2 having only integer coefficients.
1154 * Return aff1 and add (aff2 / d) to *expr.
1155 */
1156static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
1157 __isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
1158{
1159 struct isl_ast_extract_rational_data data = { NULL };
1160 isl_ast_expr *rat_expr;
1161 isl_val *v;
1162
1163 if (!aff)
1164 return NULL;
1165 data.d = isl_aff_get_denominator_val(aff);
1166 if (!data.d)
1167 goto error;
1168 if (isl_val_is_one(v: data.d)) {
1169 isl_val_free(v: data.d);
1170 return aff;
1171 }
1172
1173 aff = isl_aff_scale_val(aff, v: isl_val_copy(v: data.d));
1174
1175 data.ls = isl_aff_get_domain_local_space(aff);
1176 data.rat = isl_aff_zero_on_domain(ls: isl_local_space_copy(ls: data.ls));
1177
1178 if (every_non_zero_coefficient(aff, reverse: 0, fn: &add_rational, user: &data) < 0)
1179 goto error;
1180
1181 v = isl_aff_get_constant_val(aff);
1182 if (isl_val_is_divisible_by(v1: v, v2: data.d)) {
1183 isl_val_free(v);
1184 } else {
1185 isl_aff *rat_0;
1186
1187 rat_0 = isl_aff_val_on_domain(ls: isl_local_space_copy(ls: data.ls), val: v);
1188 data.rat = isl_aff_add(aff1: data.rat, aff2: rat_0);
1189 }
1190
1191 isl_local_space_free(ls: data.ls);
1192
1193 aff = isl_aff_sub(aff1: aff, aff2: isl_aff_copy(aff: data.rat));
1194 aff = isl_aff_scale_down_val(aff, v: isl_val_copy(v: data.d));
1195
1196 rat_expr = div_mod(type: isl_ast_expr_op_div, aff: data.rat, v: data.d, build);
1197 *expr = ast_expr_add(expr1: *expr, expr2: rat_expr);
1198
1199 return aff;
1200error:
1201 isl_aff_free(aff: data.rat);
1202 isl_local_space_free(ls: data.ls);
1203 isl_aff_free(aff);
1204 isl_val_free(v: data.d);
1205 return NULL;
1206}
1207
1208/* Internal data structure for isl_ast_expr_from_aff.
1209 *
1210 * "term" contains the information for adding a term.
1211 * "expr" collects the results.
1212 */
1213struct isl_ast_add_terms_data {
1214 struct isl_ast_add_term_data *term;
1215 isl_ast_expr *expr;
1216};
1217
1218/* Given a non-zero term in an affine expression equal to "v" times
1219 * the variable of type "type" at position "pos",
1220 * add the corresponding AST expression to data->expr.
1221 */
1222static isl_bool add_term(enum isl_dim_type type, int pos,
1223 __isl_take isl_val *v, void *user)
1224{
1225 struct isl_ast_add_terms_data *data = user;
1226
1227 data->expr =
1228 isl_ast_expr_add_term(expr: data->expr, type, pos, v, data: data->term);
1229
1230 return isl_bool_true;
1231}
1232
1233/* Add terms to "expr" for each variable in "aff".
1234 * The result is simplified in terms of data->build->domain.
1235 */
1236static __isl_give isl_ast_expr *add_terms(__isl_take isl_ast_expr *expr,
1237 __isl_keep isl_aff *aff, struct isl_ast_add_term_data *data)
1238{
1239 struct isl_ast_add_terms_data terms_data = { data, expr };
1240
1241 if (every_non_zero_coefficient(aff, reverse: 0, fn: &add_term, user: &terms_data) < 0)
1242 return isl_ast_expr_free(expr: terms_data.expr);
1243
1244 return terms_data.expr;
1245}
1246
1247/* Construct an isl_ast_expr that evaluates the affine expression "aff".
1248 * The result is simplified in terms of build->domain.
1249 *
1250 * We first extract hidden modulo computations from the affine expression
1251 * and then add terms for each variable with a non-zero coefficient.
1252 * Finally, if the affine expression has a non-trivial denominator,
1253 * we divide the resulting isl_ast_expr by this denominator.
1254 */
1255__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
1256 __isl_keep isl_ast_build *build)
1257{
1258 isl_ctx *ctx = isl_aff_get_ctx(aff);
1259 isl_ast_expr *expr, *expr_neg;
1260 struct isl_ast_add_term_data term_data;
1261
1262 if (!aff)
1263 return NULL;
1264
1265 expr = isl_ast_expr_alloc_int_si(ctx, i: 0);
1266 expr_neg = isl_ast_expr_alloc_int_si(ctx, i: 0);
1267
1268 aff = extract_rational(aff, expr: &expr, build);
1269
1270 aff = extract_modulos(aff, pos: &expr, neg: &expr_neg, build);
1271 expr = ast_expr_sub(expr1: expr, expr2: expr_neg);
1272
1273 term_data.build = build;
1274 term_data.ls = isl_aff_get_domain_local_space(aff);
1275 term_data.cst = isl_aff_get_constant_val(aff);
1276 expr = add_terms(expr, aff, data: &term_data);
1277
1278 expr = isl_ast_expr_add_int(expr, v: term_data.cst);
1279 isl_local_space_free(ls: term_data.ls);
1280
1281 isl_aff_free(aff);
1282 return expr;
1283}
1284
1285/* Internal data structure for coefficients_of_sign.
1286 *
1287 * "sign" is the sign of the coefficients that should be retained.
1288 * "aff" is the affine expression of which some coefficients are zeroed out.
1289 */
1290struct isl_ast_coefficients_of_sign_data {
1291 int sign;
1292 isl_aff *aff;
1293};
1294
1295/* Clear the specified coefficient of data->aff if the value "v"
1296 * does not have the required sign.
1297 */
1298static isl_bool clear_opposite_sign(enum isl_dim_type type, int pos,
1299 __isl_take isl_val *v, void *user)
1300{
1301 struct isl_ast_coefficients_of_sign_data *data = user;
1302
1303 if (type == isl_dim_set)
1304 type = isl_dim_in;
1305 if (data->sign * isl_val_sgn(v) < 0)
1306 data->aff = isl_aff_set_coefficient_si(aff: data->aff, type, pos, v: 0);
1307 isl_val_free(v);
1308
1309 return isl_bool_true;
1310}
1311
1312/* Extract the coefficients of "aff" (excluding the constant term)
1313 * that have the given sign.
1314 *
1315 * Take a copy of "aff" and clear the coefficients that do not have
1316 * the required sign.
1317 * Consider the coefficients in reverse order since clearing
1318 * the coefficient of an integer division in data.aff
1319 * could result in the removal of that integer division from data.aff,
1320 * changing the positions of all subsequent integer divisions of data.aff,
1321 * while those of "aff" remain the same.
1322 */
1323static __isl_give isl_aff *coefficients_of_sign(__isl_take isl_aff *aff,
1324 int sign)
1325{
1326 struct isl_ast_coefficients_of_sign_data data;
1327
1328 data.sign = sign;
1329 data.aff = isl_aff_copy(aff);
1330 if (every_non_zero_coefficient(aff, reverse: 1, fn: &clear_opposite_sign, user: &data) < 0)
1331 data.aff = isl_aff_free(aff: data.aff);
1332 isl_aff_free(aff);
1333
1334 data.aff = isl_aff_set_constant_si(aff: data.aff, v: 0);
1335
1336 return data.aff;
1337}
1338
1339/* Should the constant term "v" be considered positive?
1340 *
1341 * A positive constant will be added to "pos" by the caller,
1342 * while a negative constant will be added to "neg".
1343 * If either "pos" or "neg" is exactly zero, then we prefer
1344 * to add the constant "v" to that side, irrespective of the sign of "v".
1345 * This results in slightly shorter expressions and may reduce the risk
1346 * of overflows.
1347 */
1348static isl_bool constant_is_considered_positive(__isl_keep isl_val *v,
1349 __isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
1350{
1351 isl_bool zero;
1352
1353 zero = ast_expr_is_zero(expr: pos);
1354 if (zero < 0 || zero)
1355 return zero;
1356 zero = ast_expr_is_zero(expr: neg);
1357 if (zero < 0 || zero)
1358 return isl_bool_not(b: zero);
1359 return isl_val_is_pos(v);
1360}
1361
1362/* Check if the equality
1363 *
1364 * aff = 0
1365 *
1366 * represents a stride constraint on the integer division "pos".
1367 *
1368 * In particular, if the integer division "pos" is equal to
1369 *
1370 * floor(e/d)
1371 *
1372 * then check if aff is equal to
1373 *
1374 * e - d floor(e/d)
1375 *
1376 * or its opposite.
1377 *
1378 * If so, the equality is exactly
1379 *
1380 * e mod d = 0
1381 *
1382 * Note that in principle we could also accept
1383 *
1384 * e - d floor(e'/d)
1385 *
1386 * where e and e' differ by a constant.
1387 */
1388static isl_bool is_stride_constraint(__isl_keep isl_aff *aff, int pos)
1389{
1390 isl_aff *div;
1391 isl_val *c, *d;
1392 isl_bool eq;
1393
1394 div = isl_aff_get_div(aff, pos);
1395 c = isl_aff_get_coefficient_val(aff, type: isl_dim_div, pos);
1396 d = isl_aff_get_denominator_val(aff: div);
1397 eq = isl_val_abs_eq(v1: c, v2: d);
1398 if (eq >= 0 && eq) {
1399 aff = isl_aff_copy(aff);
1400 aff = isl_aff_set_coefficient_si(aff, type: isl_dim_div, pos, v: 0);
1401 div = isl_aff_scale_val(aff: div, v: d);
1402 if (isl_val_is_pos(v: c))
1403 div = isl_aff_neg(aff: div);
1404 eq = isl_aff_plain_is_equal(aff1: div, aff2: aff);
1405 isl_aff_free(aff);
1406 } else
1407 isl_val_free(v: d);
1408 isl_val_free(v: c);
1409 isl_aff_free(aff: div);
1410
1411 return eq;
1412}
1413
1414/* Are all coefficients of "aff" (zero or) negative?
1415 */
1416static isl_bool all_negative_coefficients(__isl_keep isl_aff *aff)
1417{
1418 int i;
1419 isl_size n;
1420
1421 n = isl_aff_dim(aff, type: isl_dim_param);
1422 if (n < 0)
1423 return isl_bool_error;
1424 for (i = 0; i < n; ++i)
1425 if (isl_aff_coefficient_sgn(aff, type: isl_dim_param, pos: i) > 0)
1426 return isl_bool_false;
1427
1428 n = isl_aff_dim(aff, type: isl_dim_in);
1429 if (n < 0)
1430 return isl_bool_error;
1431 for (i = 0; i < n; ++i)
1432 if (isl_aff_coefficient_sgn(aff, type: isl_dim_in, pos: i) > 0)
1433 return isl_bool_false;
1434
1435 return isl_bool_true;
1436}
1437
1438/* Give an equality of the form
1439 *
1440 * aff = e - d floor(e/d) = 0
1441 *
1442 * or
1443 *
1444 * aff = -e + d floor(e/d) = 0
1445 *
1446 * with the integer division "pos" equal to floor(e/d),
1447 * construct the AST expression
1448 *
1449 * (isl_ast_expr_op_eq,
1450 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1451 *
1452 * If e only has negative coefficients, then construct
1453 *
1454 * (isl_ast_expr_op_eq,
1455 * (isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))
1456 *
1457 * instead.
1458 */
1459static __isl_give isl_ast_expr *extract_stride_constraint(
1460 __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
1461{
1462 isl_bool all_neg;
1463 isl_ctx *ctx;
1464 isl_val *c;
1465 isl_ast_expr *expr, *cst;
1466
1467 if (!aff)
1468 return NULL;
1469
1470 ctx = isl_aff_get_ctx(aff);
1471
1472 c = isl_aff_get_coefficient_val(aff, type: isl_dim_div, pos);
1473 aff = isl_aff_set_coefficient_si(aff, type: isl_dim_div, pos, v: 0);
1474
1475 all_neg = all_negative_coefficients(aff);
1476 if (all_neg < 0)
1477 aff = isl_aff_free(aff);
1478 else if (all_neg)
1479 aff = isl_aff_neg(aff);
1480
1481 cst = isl_ast_expr_from_val(v: isl_val_abs(v: c));
1482 expr = isl_ast_expr_from_aff(aff, build);
1483
1484 expr = isl_ast_expr_alloc_binary(type: isl_ast_expr_op_zdiv_r, expr1: expr, expr2: cst);
1485 cst = isl_ast_expr_alloc_int_si(ctx, i: 0);
1486 expr = isl_ast_expr_alloc_binary(type: isl_ast_expr_op_eq, expr1: expr, expr2: cst);
1487
1488 return expr;
1489}
1490
1491/* Construct an isl_ast_expr evaluating
1492 *
1493 * "expr_pos" == "expr_neg", if "eq" is set, or
1494 * "expr_pos" >= "expr_neg", if "eq" is not set
1495 *
1496 * However, if "expr_pos" is an integer constant (and "expr_neg" is not),
1497 * then the two expressions are interchanged. This ensures that,
1498 * e.g., "i <= 5" is constructed rather than "5 >= i".
1499 */
1500static __isl_give isl_ast_expr *construct_constraint_expr(int eq,
1501 __isl_take isl_ast_expr *expr_pos, __isl_take isl_ast_expr *expr_neg)
1502{
1503 isl_ast_expr *expr;
1504 enum isl_ast_expr_op_type type;
1505 int pos_is_cst, neg_is_cst;
1506
1507 pos_is_cst = isl_ast_expr_get_type(expr: expr_pos) == isl_ast_expr_int;
1508 neg_is_cst = isl_ast_expr_get_type(expr: expr_neg) == isl_ast_expr_int;
1509 if (pos_is_cst && !neg_is_cst) {
1510 type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_le;
1511 expr = isl_ast_expr_alloc_binary(type, expr1: expr_neg, expr2: expr_pos);
1512 } else {
1513 type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_ge;
1514 expr = isl_ast_expr_alloc_binary(type, expr1: expr_pos, expr2: expr_neg);
1515 }
1516
1517 return expr;
1518}
1519
1520/* Construct an isl_ast_expr that evaluates the condition "aff" == 0
1521 * (if "eq" is set) or "aff" >= 0 (otherwise).
1522 * The result is simplified in terms of build->domain.
1523 *
1524 * We first extract hidden modulo computations from "aff"
1525 * and then collect all the terms with a positive coefficient in cons_pos
1526 * and the terms with a negative coefficient in cons_neg.
1527 *
1528 * The result is then essentially of the form
1529 *
1530 * (isl_ast_expr_op_ge, expr(pos), expr(-neg)))
1531 *
1532 * or
1533 *
1534 * (isl_ast_expr_op_eq, expr(pos), expr(-neg)))
1535 *
1536 * However, if there are no terms with positive coefficients (or no terms
1537 * with negative coefficients), then the constant term is added to "pos"
1538 * (or "neg"), ignoring the sign of the constant term.
1539 */
1540static __isl_give isl_ast_expr *isl_ast_expr_from_constraint_no_stride(
1541 int eq, __isl_take isl_aff *aff, __isl_keep isl_ast_build *build)
1542{
1543 isl_bool cst_is_pos;
1544 isl_ctx *ctx;
1545 isl_ast_expr *expr_pos;
1546 isl_ast_expr *expr_neg;
1547 isl_aff *aff_pos, *aff_neg;
1548 struct isl_ast_add_term_data data;
1549
1550 ctx = isl_aff_get_ctx(aff);
1551 expr_pos = isl_ast_expr_alloc_int_si(ctx, i: 0);
1552 expr_neg = isl_ast_expr_alloc_int_si(ctx, i: 0);
1553
1554 aff = extract_modulos(aff, pos: &expr_pos, neg: &expr_neg, build);
1555
1556 data.build = build;
1557 data.ls = isl_aff_get_domain_local_space(aff);
1558 data.cst = isl_aff_get_constant_val(aff);
1559
1560 aff_pos = coefficients_of_sign(aff: isl_aff_copy(aff), sign: 1);
1561 aff_neg = isl_aff_neg(aff: coefficients_of_sign(aff, sign: -1));
1562
1563 expr_pos = add_terms(expr: expr_pos, aff: aff_pos, data: &data);
1564 data.cst = isl_val_neg(v: data.cst);
1565 expr_neg = add_terms(expr: expr_neg, aff: aff_neg, data: &data);
1566 data.cst = isl_val_neg(v: data.cst);
1567 isl_local_space_free(ls: data.ls);
1568
1569 cst_is_pos =
1570 constant_is_considered_positive(v: data.cst, pos: expr_pos, neg: expr_neg);
1571 if (cst_is_pos < 0)
1572 expr_pos = isl_ast_expr_free(expr: expr_pos);
1573
1574 if (cst_is_pos) {
1575 expr_pos = isl_ast_expr_add_int(expr: expr_pos, v: data.cst);
1576 } else {
1577 data.cst = isl_val_neg(v: data.cst);
1578 expr_neg = isl_ast_expr_add_int(expr: expr_neg, v: data.cst);
1579 }
1580
1581 isl_aff_free(aff: aff_pos);
1582 isl_aff_free(aff: aff_neg);
1583 return construct_constraint_expr(eq, expr_pos, expr_neg);
1584}
1585
1586/* Construct an isl_ast_expr that evaluates the condition "constraint".
1587 * The result is simplified in terms of build->domain.
1588 *
1589 * We first check if the constraint is an equality of the form
1590 *
1591 * e - d floor(e/d) = 0
1592 *
1593 * i.e.,
1594 *
1595 * e mod d = 0
1596 *
1597 * If so, we convert it to
1598 *
1599 * (isl_ast_expr_op_eq,
1600 * (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1601 */
1602static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1603 __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1604{
1605 int i;
1606 isl_size n;
1607 isl_aff *aff;
1608 isl_bool eq;
1609
1610 aff = isl_constraint_get_aff(constraint);
1611 eq = isl_constraint_is_equality(constraint);
1612 isl_constraint_free(c: constraint);
1613 if (eq < 0)
1614 goto error;
1615
1616 n = isl_aff_dim(aff, type: isl_dim_div);
1617 if (n < 0)
1618 aff = isl_aff_free(aff);
1619 if (eq && n > 0)
1620 for (i = 0; i < n; ++i) {
1621 isl_bool is_stride;
1622 is_stride = is_stride_constraint(aff, pos: i);
1623 if (is_stride < 0)
1624 goto error;
1625 if (is_stride)
1626 return extract_stride_constraint(aff, pos: i, build);
1627 }
1628
1629 return isl_ast_expr_from_constraint_no_stride(eq, aff, build);
1630error:
1631 isl_aff_free(aff);
1632 return NULL;
1633}
1634
1635/* Wrapper around isl_constraint_cmp_last_non_zero for use
1636 * as a callback to isl_constraint_list_sort.
1637 * If isl_constraint_cmp_last_non_zero cannot tell the constraints
1638 * apart, then use isl_constraint_plain_cmp instead.
1639 */
1640static int cmp_constraint(__isl_keep isl_constraint *a,
1641 __isl_keep isl_constraint *b, void *user)
1642{
1643 int cmp;
1644
1645 cmp = isl_constraint_cmp_last_non_zero(c1: a, c2: b);
1646 if (cmp != 0)
1647 return cmp;
1648 return isl_constraint_plain_cmp(c1: a, c2: b);
1649}
1650
1651/* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1652 * The result is simplified in terms of build->domain.
1653 *
1654 * If "bset" is not bounded by any constraint, then we construct
1655 * the expression "1", i.e., "true".
1656 *
1657 * Otherwise, we sort the constraints, putting constraints that involve
1658 * integer divisions after those that do not, and construct an "and"
1659 * of the ast expressions of the individual constraints.
1660 *
1661 * Each constraint is added to the generated constraints of the build
1662 * after it has been converted to an AST expression so that it can be used
1663 * to simplify the following constraints. This may change the truth value
1664 * of subsequent constraints that do not satisfy the earlier constraints,
1665 * but this does not affect the outcome of the conjunction as it is
1666 * only true if all the conjuncts are true (no matter in what order
1667 * they are evaluated). In particular, the constraints that do not
1668 * involve integer divisions may serve to simplify some constraints
1669 * that do involve integer divisions.
1670 */
1671__isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
1672 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1673{
1674 int i;
1675 isl_size n;
1676 isl_constraint *c;
1677 isl_constraint_list *list;
1678 isl_ast_expr *res;
1679 isl_set *set;
1680
1681 list = isl_basic_set_get_constraint_list(bset);
1682 isl_basic_set_free(bset);
1683 list = isl_constraint_list_sort(list, cmp: &cmp_constraint, NULL);
1684 n = isl_constraint_list_n_constraint(list);
1685 if (n < 0)
1686 build = NULL;
1687 if (n == 0) {
1688 isl_ctx *ctx = isl_constraint_list_get_ctx(list);
1689 isl_constraint_list_free(list);
1690 return isl_ast_expr_alloc_int_si(ctx, i: 1);
1691 }
1692
1693 build = isl_ast_build_copy(build);
1694
1695 c = isl_constraint_list_get_constraint(list, index: 0);
1696 bset = isl_basic_set_from_constraint(constraint: isl_constraint_copy(c));
1697 set = isl_set_from_basic_set(bset);
1698 res = isl_ast_expr_from_constraint(constraint: c, build);
1699 build = isl_ast_build_restrict_generated(build, set);
1700
1701 for (i = 1; i < n; ++i) {
1702 isl_ast_expr *expr;
1703
1704 c = isl_constraint_list_get_constraint(list, index: i);
1705 bset = isl_basic_set_from_constraint(constraint: isl_constraint_copy(c));
1706 set = isl_set_from_basic_set(bset);
1707 expr = isl_ast_expr_from_constraint(constraint: c, build);
1708 build = isl_ast_build_restrict_generated(build, set);
1709 res = isl_ast_expr_and(expr1: res, expr2: expr);
1710 }
1711
1712 isl_constraint_list_free(list);
1713 isl_ast_build_free(build);
1714 return res;
1715}
1716
1717/* Construct an isl_ast_expr that evaluates the conditions defining "set".
1718 * The result is simplified in terms of build->domain.
1719 *
1720 * If "set" is an (obviously) empty set, then return the expression "0".
1721 *
1722 * If there are multiple disjuncts in the description of the set,
1723 * then subsequent disjuncts are simplified in a context where
1724 * the previous disjuncts have been removed from build->domain.
1725 * In particular, constraints that ensure that there is no overlap
1726 * with these previous disjuncts, can be removed.
1727 * This is mostly useful for disjuncts that are only defined by
1728 * a single constraint (relative to the build domain) as the opposite
1729 * of that single constraint can then be removed from the other disjuncts.
1730 * In order not to increase the number of disjuncts in the build domain
1731 * after subtracting the previous disjuncts of "set", the simple hull
1732 * is computed after taking the difference with each of these disjuncts.
1733 * This means that constraints that prevent overlap with a union
1734 * of multiple previous disjuncts are not removed.
1735 *
1736 * "set" lives in the internal schedule space.
1737 */
1738__isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
1739 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1740{
1741 int i;
1742 isl_size n;
1743 isl_basic_set *bset;
1744 isl_basic_set_list *list;
1745 isl_set *domain;
1746 isl_ast_expr *res;
1747
1748 list = isl_set_get_basic_set_list(set);
1749 isl_set_free(set);
1750
1751 n = isl_basic_set_list_n_basic_set(list);
1752 if (n < 0)
1753 build = NULL;
1754 if (n == 0) {
1755 isl_ctx *ctx = isl_ast_build_get_ctx(build);
1756 isl_basic_set_list_free(list);
1757 return isl_ast_expr_from_val(v: isl_val_zero(ctx));
1758 }
1759
1760 domain = isl_ast_build_get_domain(build);
1761
1762 bset = isl_basic_set_list_get_basic_set(list, index: 0);
1763 set = isl_set_from_basic_set(bset: isl_basic_set_copy(bset));
1764 res = isl_ast_build_expr_from_basic_set(build, bset);
1765
1766 for (i = 1; i < n; ++i) {
1767 isl_ast_expr *expr;
1768 isl_set *rest;
1769
1770 rest = isl_set_subtract(set1: isl_set_copy(set: domain), set2: set);
1771 rest = isl_set_from_basic_set(bset: isl_set_simple_hull(set: rest));
1772 domain = isl_set_intersect(set1: domain, set2: rest);
1773 bset = isl_basic_set_list_get_basic_set(list, index: i);
1774 set = isl_set_from_basic_set(bset: isl_basic_set_copy(bset));
1775 bset = isl_basic_set_gist(bset,
1776 context: isl_set_simple_hull(set: isl_set_copy(set: domain)));
1777 expr = isl_ast_build_expr_from_basic_set(build, bset);
1778 res = isl_ast_expr_or(expr1: res, expr2: expr);
1779 }
1780
1781 isl_set_free(set: domain);
1782 isl_set_free(set);
1783 isl_basic_set_list_free(list);
1784 return res;
1785}
1786
1787/* Construct an isl_ast_expr that evaluates the conditions defining "set".
1788 * The result is simplified in terms of build->domain.
1789 *
1790 * If "set" is an (obviously) empty set, then return the expression "0".
1791 *
1792 * "set" lives in the external schedule space.
1793 *
1794 * The internal AST expression generation assumes that there are
1795 * no unknown divs, so make sure an explicit representation is available.
1796 * Since the set comes from the outside, it may have constraints that
1797 * are redundant with respect to the build domain. Remove them first.
1798 */
1799__isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1800 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1801{
1802 isl_bool needs_map;
1803
1804 needs_map = isl_ast_build_need_schedule_map(build);
1805 if (needs_map < 0) {
1806 set = isl_set_free(set);
1807 } else if (needs_map) {
1808 isl_multi_aff *ma;
1809 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1810 set = isl_set_preimage_multi_aff(set, ma);
1811 }
1812
1813 set = isl_set_compute_divs(set);
1814 set = isl_ast_build_compute_gist(build, set);
1815 return isl_ast_build_expr_from_set_internal(build, set);
1816}
1817
1818/* State of data about previous pieces in
1819 * isl_ast_build_expr_from_pw_aff_internal.
1820 *
1821 * isl_state_none: no data about previous pieces
1822 * isl_state_single: data about a single previous piece
1823 * isl_state_min: data represents minimum of several pieces
1824 * isl_state_max: data represents maximum of several pieces
1825 */
1826enum isl_from_pw_aff_state {
1827 isl_state_none,
1828 isl_state_single,
1829 isl_state_min,
1830 isl_state_max
1831};
1832
1833/* Internal date structure representing a single piece in the input of
1834 * isl_ast_build_expr_from_pw_aff_internal.
1835 *
1836 * If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1837 * If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1838 * single previous subpiece.
1839 * If "state" is isl_state_min, then "set_list" and "aff_list" contain
1840 * a sequence of several previous subpieces that are equal to the minimum
1841 * of the entries in "aff_list" over the union of "set_list"
1842 * If "state" is isl_state_max, then "set_list" and "aff_list" contain
1843 * a sequence of several previous subpieces that are equal to the maximum
1844 * of the entries in "aff_list" over the union of "set_list"
1845 *
1846 * During the construction of the pieces, "set" is NULL.
1847 * After the construction, "set" is set to the union of the elements
1848 * in "set_list", at which point "set_list" is set to NULL.
1849 */
1850struct isl_from_pw_aff_piece {
1851 enum isl_from_pw_aff_state state;
1852 isl_set *set;
1853 isl_set_list *set_list;
1854 isl_aff_list *aff_list;
1855};
1856
1857/* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1858 *
1859 * "build" specifies the domain against which the result is simplified.
1860 * "dom" is the domain of the entire isl_pw_aff.
1861 *
1862 * "n" is the number of pieces constructed already.
1863 * In particular, during the construction of the pieces, "n" points to
1864 * the piece that is being constructed. After the construction of the
1865 * pieces, "n" is set to the total number of pieces.
1866 * "max" is the total number of allocated entries.
1867 * "p" contains the individual pieces.
1868 */
1869struct isl_from_pw_aff_data {
1870 isl_ast_build *build;
1871 isl_set *dom;
1872
1873 int n;
1874 int max;
1875 struct isl_from_pw_aff_piece *p;
1876};
1877
1878/* Initialize "data" based on "build" and "pa".
1879 */
1880static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data,
1881 __isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa)
1882{
1883 isl_size n;
1884 isl_ctx *ctx;
1885
1886 ctx = isl_pw_aff_get_ctx(pwaff: pa);
1887 n = isl_pw_aff_n_piece(pwaff: pa);
1888 if (n < 0)
1889 return isl_stat_error;
1890 if (n == 0)
1891 isl_die(ctx, isl_error_invalid,
1892 "cannot handle void expression", return isl_stat_error);
1893 data->max = n;
1894 data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
1895 if (!data->p)
1896 return isl_stat_error;
1897 data->build = build;
1898 data->dom = isl_pw_aff_domain(pwaff: isl_pw_aff_copy(pwaff: pa));
1899 data->n = 0;
1900
1901 return isl_stat_ok;
1902}
1903
1904/* Free all memory allocated for "data".
1905 */
1906static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)
1907{
1908 int i;
1909
1910 isl_set_free(set: data->dom);
1911 if (!data->p)
1912 return;
1913
1914 for (i = 0; i < data->max; ++i) {
1915 isl_set_free(set: data->p[i].set);
1916 isl_set_list_free(list: data->p[i].set_list);
1917 isl_aff_list_free(list: data->p[i].aff_list);
1918 }
1919 free(ptr: data->p);
1920}
1921
1922/* Initialize the current entry of "data" to an unused piece.
1923 */
1924static void set_none(struct isl_from_pw_aff_data *data)
1925{
1926 data->p[data->n].state = isl_state_none;
1927 data->p[data->n].set_list = NULL;
1928 data->p[data->n].aff_list = NULL;
1929}
1930
1931/* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1932 */
1933static void set_single(struct isl_from_pw_aff_data *data,
1934 __isl_take isl_set *set, __isl_take isl_aff *aff)
1935{
1936 data->p[data->n].state = isl_state_single;
1937 data->p[data->n].set_list = isl_set_list_from_set(el: set);
1938 data->p[data->n].aff_list = isl_aff_list_from_aff(el: aff);
1939}
1940
1941/* Extend the current entry of "data" with "set" and "aff"
1942 * as a minimum expression.
1943 */
1944static isl_stat extend_min(struct isl_from_pw_aff_data *data,
1945 __isl_take isl_set *set, __isl_take isl_aff *aff)
1946{
1947 int n = data->n;
1948 data->p[n].state = isl_state_min;
1949 data->p[n].set_list = isl_set_list_add(list: data->p[n].set_list, el: set);
1950 data->p[n].aff_list = isl_aff_list_add(list: data->p[n].aff_list, el: aff);
1951
1952 if (!data->p[n].set_list || !data->p[n].aff_list)
1953 return isl_stat_error;
1954 return isl_stat_ok;
1955}
1956
1957/* Extend the current entry of "data" with "set" and "aff"
1958 * as a maximum expression.
1959 */
1960static isl_stat extend_max(struct isl_from_pw_aff_data *data,
1961 __isl_take isl_set *set, __isl_take isl_aff *aff)
1962{
1963 int n = data->n;
1964 data->p[n].state = isl_state_max;
1965 data->p[n].set_list = isl_set_list_add(list: data->p[n].set_list, el: set);
1966 data->p[n].aff_list = isl_aff_list_add(list: data->p[n].aff_list, el: aff);
1967
1968 if (!data->p[n].set_list || !data->p[n].aff_list)
1969 return isl_stat_error;
1970 return isl_stat_ok;
1971}
1972
1973/* Extend the domain of the current entry of "data", which is assumed
1974 * to contain a single subpiece, with "set". If "replace" is set,
1975 * then also replace the affine function by "aff". Otherwise,
1976 * simply free "aff".
1977 */
1978static isl_stat extend_domain(struct isl_from_pw_aff_data *data,
1979 __isl_take isl_set *set, __isl_take isl_aff *aff, int replace)
1980{
1981 int n = data->n;
1982 isl_set *set_n;
1983
1984 set_n = isl_set_list_get_set(list: data->p[n].set_list, index: 0);
1985 set_n = isl_set_union(set1: set_n, set2: set);
1986 data->p[n].set_list =
1987 isl_set_list_set_set(list: data->p[n].set_list, index: 0, el: set_n);
1988
1989 if (replace)
1990 data->p[n].aff_list =
1991 isl_aff_list_set_aff(list: data->p[n].aff_list, index: 0, el: aff);
1992 else
1993 isl_aff_free(aff);
1994
1995 if (!data->p[n].set_list || !data->p[n].aff_list)
1996 return isl_stat_error;
1997 return isl_stat_ok;
1998}
1999
2000/* Construct an isl_ast_expr from "list" within "build".
2001 * If "state" is isl_state_single, then "list" contains a single entry and
2002 * an isl_ast_expr is constructed for that entry.
2003 * Otherwise a min or max expression is constructed from "list"
2004 * depending on "state".
2005 */
2006static __isl_give isl_ast_expr *ast_expr_from_aff_list(
2007 __isl_take isl_aff_list *list, enum isl_from_pw_aff_state state,
2008 __isl_keep isl_ast_build *build)
2009{
2010 int i;
2011 isl_size n;
2012 isl_aff *aff;
2013 isl_ast_expr *expr = NULL;
2014 enum isl_ast_expr_op_type op_type;
2015
2016 if (state == isl_state_single) {
2017 aff = isl_aff_list_get_aff(list, index: 0);
2018 isl_aff_list_free(list);
2019 return isl_ast_expr_from_aff(aff, build);
2020 }
2021 n = isl_aff_list_n_aff(list);
2022 if (n < 0)
2023 goto error;
2024 op_type = state == isl_state_min ? isl_ast_expr_op_min
2025 : isl_ast_expr_op_max;
2026 expr = isl_ast_expr_alloc_op(ctx: isl_ast_build_get_ctx(build), op: op_type, n_arg: n);
2027
2028 for (i = 0; i < n; ++i) {
2029 isl_ast_expr *expr_i;
2030
2031 aff = isl_aff_list_get_aff(list, index: i);
2032 expr_i = isl_ast_expr_from_aff(aff, build);
2033 expr = isl_ast_expr_op_add_arg(expr, arg: expr_i);
2034 }
2035
2036 isl_aff_list_free(list);
2037 return expr;
2038error:
2039 isl_aff_list_free(list);
2040 isl_ast_expr_free(expr);
2041 return NULL;
2042}
2043
2044/* Extend the list of expressions in "next" to take into account
2045 * the piece at position "pos" in "data", allowing for a further extension
2046 * for the next piece(s).
2047 * In particular, "next" is extended with a select operation that selects
2048 * an isl_ast_expr corresponding to data->aff_list on data->set and
2049 * to an expression that will be filled in by later calls.
2050 * Return a pointer to the arguments of this select operation.
2051 * Afterwards, the state of "data" is set to isl_state_none.
2052 *
2053 * The constraints of data->set are added to the generated
2054 * constraints of the build such that they can be exploited to simplify
2055 * the AST expression constructed from data->aff_list.
2056 */
2057static isl_ast_expr_list **add_intermediate_piece(
2058 struct isl_from_pw_aff_data *data,
2059 int pos, isl_ast_expr_list **next)
2060{
2061 isl_ctx *ctx;
2062 isl_ast_build *build;
2063 isl_ast_expr *ternary, *arg;
2064 isl_set *set, *gist;
2065
2066 set = data->p[pos].set;
2067 data->p[pos].set = NULL;
2068 ctx = isl_ast_build_get_ctx(build: data->build);
2069 ternary = isl_ast_expr_alloc_op(ctx, op: isl_ast_expr_op_select, n_arg: 3);
2070 gist = isl_set_gist(set: isl_set_copy(set), context: isl_set_copy(set: data->dom));
2071 arg = isl_ast_build_expr_from_set_internal(build: data->build, set: gist);
2072 ternary = isl_ast_expr_op_add_arg(expr: ternary, arg);
2073 build = isl_ast_build_copy(build: data->build);
2074 build = isl_ast_build_restrict_generated(build, set);
2075 arg = ast_expr_from_aff_list(list: data->p[pos].aff_list,
2076 state: data->p[pos].state, build);
2077 data->p[pos].aff_list = NULL;
2078 isl_ast_build_free(build);
2079 ternary = isl_ast_expr_op_add_arg(expr: ternary, arg);
2080 data->p[pos].state = isl_state_none;
2081 if (!ternary)
2082 return NULL;
2083
2084 *next = isl_ast_expr_list_add(list: *next, el: ternary);
2085 return &ternary->u.op.args;
2086}
2087
2088/* Extend the list of expressions in "next" to take into account
2089 * the final piece, located at position "pos" in "data".
2090 * In particular, "next" is extended with an expression
2091 * to evaluate data->aff_list and the domain is ignored.
2092 * Return isl_stat_ok on success and isl_stat_error on failure.
2093 *
2094 * The constraints of data->set are however added to the generated
2095 * constraints of the build such that they can be exploited to simplify
2096 * the AST expression constructed from data->aff_list.
2097 */
2098static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,
2099 int pos, isl_ast_expr_list **next)
2100{
2101 isl_ast_build *build;
2102 isl_ast_expr *last;
2103
2104 if (data->p[pos].state == isl_state_none)
2105 isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
2106 "cannot handle void expression", return isl_stat_error);
2107
2108 build = isl_ast_build_copy(build: data->build);
2109 build = isl_ast_build_restrict_generated(build, set: data->p[pos].set);
2110 data->p[pos].set = NULL;
2111 last = ast_expr_from_aff_list(list: data->p[pos].aff_list,
2112 state: data->p[pos].state, build);
2113 *next = isl_ast_expr_list_add(list: *next, el: last);
2114 data->p[pos].aff_list = NULL;
2115 isl_ast_build_free(build);
2116 data->p[pos].state = isl_state_none;
2117 if (!*next)
2118 return isl_stat_error;
2119
2120 return isl_stat_ok;
2121}
2122
2123/* Return -1 if the piece "p1" should be sorted before "p2"
2124 * and 1 if it should be sorted after "p2".
2125 * Return 0 if they do not need to be sorted in a specific order.
2126 *
2127 * Pieces are sorted according to the number of disjuncts
2128 * in their domains.
2129 */
2130static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)
2131{
2132 const struct isl_from_pw_aff_piece *piece1 = p1;
2133 const struct isl_from_pw_aff_piece *piece2 = p2;
2134 isl_size n1, n2;
2135
2136 n1 = isl_set_n_basic_set(set: piece1->set);
2137 n2 = isl_set_n_basic_set(set: piece2->set);
2138
2139 return n1 - n2;
2140}
2141
2142/* Construct an isl_ast_expr from the pieces in "data".
2143 * Return the result or NULL on failure.
2144 *
2145 * When this function is called, data->n points to the current piece.
2146 * If this is an effective piece, then first increment data->n such
2147 * that data->n contains the number of pieces.
2148 * The "set_list" fields are subsequently replaced by the corresponding
2149 * "set" fields, after which the pieces are sorted according to
2150 * the number of disjuncts in these "set" fields.
2151 *
2152 * Construct intermediate AST expressions for the initial pieces and
2153 * finish off with the final pieces.
2154 *
2155 * Any piece that is not the very first is added to the list of arguments
2156 * of the previously constructed piece.
2157 * In order not to have to special case the first piece,
2158 * an extra list is created to hold the final result.
2159 */
2160static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)
2161{
2162 int i;
2163 isl_ctx *ctx;
2164 isl_ast_expr_list *res_list;
2165 isl_ast_expr_list **next = &res_list;
2166 isl_ast_expr *res;
2167
2168 if (data->p[data->n].state != isl_state_none)
2169 data->n++;
2170 ctx = isl_ast_build_get_ctx(build: data->build);
2171 if (data->n == 0)
2172 isl_die(ctx, isl_error_invalid,
2173 "cannot handle void expression", return NULL);
2174
2175 for (i = 0; i < data->n; ++i) {
2176 data->p[i].set = isl_set_list_union(list: data->p[i].set_list);
2177 if (data->p[i].state != isl_state_single)
2178 data->p[i].set = isl_set_coalesce(set: data->p[i].set);
2179 data->p[i].set_list = NULL;
2180 }
2181
2182 if (isl_sort(pbase: data->p, total_elems: data->n, size: sizeof(data->p[0]),
2183 cmp: &sort_pieces_cmp, NULL) < 0)
2184 return NULL;
2185
2186 res_list = isl_ast_expr_list_alloc(ctx, n: 1);
2187 if (!res_list)
2188 return NULL;
2189 for (i = 0; i + 1 < data->n; ++i) {
2190 next = add_intermediate_piece(data, pos: i, next);
2191 if (!next)
2192 goto error;
2193 }
2194
2195 if (add_last_piece(data, pos: data->n - 1, next) < 0)
2196 goto error;
2197
2198 res = isl_ast_expr_list_get_at(list: res_list, index: 0);
2199 isl_ast_expr_list_free(list: res_list);
2200 return res;
2201error:
2202 isl_ast_expr_list_free(list: res_list);
2203 return NULL;
2204}
2205
2206/* Is the domain of the current entry of "data", which is assumed
2207 * to contain a single subpiece, a subset of "set"?
2208 */
2209static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
2210 __isl_keep isl_set *set)
2211{
2212 isl_bool subset;
2213 isl_set *set_n;
2214
2215 set_n = isl_set_list_get_set(list: data->p[data->n].set_list, index: 0);
2216 subset = isl_set_is_subset(set1: set_n, set2: set);
2217 isl_set_free(set: set_n);
2218
2219 return subset;
2220}
2221
2222/* Is "aff" a rational expression, i.e., does it have a denominator
2223 * different from one?
2224 */
2225static isl_bool aff_is_rational(__isl_keep isl_aff *aff)
2226{
2227 isl_bool rational;
2228 isl_val *den;
2229
2230 den = isl_aff_get_denominator_val(aff);
2231 rational = isl_bool_not(b: isl_val_is_one(v: den));
2232 isl_val_free(v: den);
2233
2234 return rational;
2235}
2236
2237/* Does "list" consist of a single rational affine expression?
2238 */
2239static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)
2240{
2241 isl_size n;
2242 isl_bool rational;
2243 isl_aff *aff;
2244
2245 n = isl_aff_list_n_aff(list);
2246 if (n < 0)
2247 return isl_bool_error;
2248 if (n != 1)
2249 return isl_bool_false;
2250 aff = isl_aff_list_get_aff(list, index: 0);
2251 rational = aff_is_rational(aff);
2252 isl_aff_free(aff);
2253
2254 return rational;
2255}
2256
2257/* Can the list of subpieces in the last piece of "data" be extended with
2258 * "set" and "aff" based on "test"?
2259 * In particular, is it the case for each entry (set_i, aff_i) that
2260 *
2261 * test(aff, aff_i) holds on set_i, and
2262 * test(aff_i, aff) holds on set?
2263 *
2264 * "test" returns the set of elements where the tests holds, meaning
2265 * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2266 *
2267 * This function is used to detect min/max expressions.
2268 * If the ast_build_detect_min_max option is turned off, then
2269 * do not even try and perform any detection and return false instead.
2270 *
2271 * Rational affine expressions are not considered for min/max expressions
2272 * since the combined expression will be defined on the union of the domains,
2273 * while a rational expression may only yield integer values
2274 * on its own definition domain.
2275 */
2276static isl_bool extends(struct isl_from_pw_aff_data *data,
2277 __isl_keep isl_set *set, __isl_keep isl_aff *aff,
2278 __isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1,
2279 __isl_take isl_aff *aff2))
2280{
2281 int i;
2282 isl_size n;
2283 isl_bool is_rational;
2284 isl_ctx *ctx;
2285 isl_set *dom;
2286
2287 is_rational = aff_is_rational(aff);
2288 if (is_rational >= 0 && !is_rational)
2289 is_rational = is_single_rational_aff(list: data->p[data->n].aff_list);
2290 if (is_rational < 0 || is_rational)
2291 return isl_bool_not(b: is_rational);
2292
2293 ctx = isl_ast_build_get_ctx(build: data->build);
2294 if (!isl_options_get_ast_build_detect_min_max(ctx))
2295 return isl_bool_false;
2296
2297 n = isl_set_list_n_set(list: data->p[data->n].set_list);
2298 if (n < 0)
2299 return isl_bool_error;
2300
2301 dom = isl_ast_build_get_domain(build: data->build);
2302 set = isl_set_intersect(set1: dom, set2: isl_set_copy(set));
2303
2304 for (i = 0; i < n ; ++i) {
2305 isl_aff *aff_i;
2306 isl_set *valid;
2307 isl_set *dom, *required;
2308 isl_bool is_valid;
2309
2310 aff_i = isl_aff_list_get_aff(list: data->p[data->n].aff_list, index: i);
2311 valid = isl_set_from_basic_set(bset: test(isl_aff_copy(aff), aff_i));
2312 required = isl_set_list_get_set(list: data->p[data->n].set_list, index: i);
2313 dom = isl_ast_build_get_domain(build: data->build);
2314 required = isl_set_intersect(set1: dom, set2: required);
2315 is_valid = isl_set_is_subset(set1: required, set2: valid);
2316 isl_set_free(set: required);
2317 isl_set_free(set: valid);
2318 if (is_valid < 0 || !is_valid) {
2319 isl_set_free(set);
2320 return is_valid;
2321 }
2322
2323 aff_i = isl_aff_list_get_aff(list: data->p[data->n].aff_list, index: i);
2324 valid = isl_set_from_basic_set(bset: test(aff_i, isl_aff_copy(aff)));
2325 is_valid = isl_set_is_subset(set1: set, set2: valid);
2326 isl_set_free(set: valid);
2327 if (is_valid < 0 || !is_valid) {
2328 isl_set_free(set);
2329 return is_valid;
2330 }
2331 }
2332
2333 isl_set_free(set);
2334 return isl_bool_true;
2335}
2336
2337/* Can the list of pieces in "data" be extended with "set" and "aff"
2338 * to form/preserve a minimum expression?
2339 * In particular, is it the case for each entry (set_i, aff_i) that
2340 *
2341 * aff >= aff_i on set_i, and
2342 * aff_i >= aff on set?
2343 */
2344static isl_bool extends_min(struct isl_from_pw_aff_data *data,
2345 __isl_keep isl_set *set, __isl_keep isl_aff *aff)
2346{
2347 return extends(data, set, aff, test: &isl_aff_ge_basic_set);
2348}
2349
2350/* Can the list of pieces in "data" be extended with "set" and "aff"
2351 * to form/preserve a maximum expression?
2352 * In particular, is it the case for each entry (set_i, aff_i) that
2353 *
2354 * aff <= aff_i on set_i, and
2355 * aff_i <= aff on set?
2356 */
2357static isl_bool extends_max(struct isl_from_pw_aff_data *data,
2358 __isl_keep isl_set *set, __isl_keep isl_aff *aff)
2359{
2360 return extends(data, set, aff, test: &isl_aff_le_basic_set);
2361}
2362
2363/* This function is called during the construction of an isl_ast_expr
2364 * that evaluates an isl_pw_aff.
2365 * If the last piece of "data" contains a single subpiece and
2366 * if its affine function is equal to "aff" on a part of the domain
2367 * that includes either "set" or the domain of that single subpiece,
2368 * then extend the domain of that single subpiece with "set".
2369 * If it was the original domain of the single subpiece where
2370 * the two affine functions are equal, then also replace
2371 * the affine function of the single subpiece by "aff".
2372 * If the last piece of "data" contains either a single subpiece
2373 * or a minimum, then check if this minimum expression can be extended
2374 * with (set, aff).
2375 * If so, extend the sequence and return.
2376 * Perform the same operation for maximum expressions.
2377 * If no such extension can be performed, then move to the next piece
2378 * in "data" (if the current piece contains any data), and then store
2379 * the current subpiece in the current piece of "data" for later handling.
2380 */
2381static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,
2382 __isl_take isl_aff *aff, void *user)
2383{
2384 struct isl_from_pw_aff_data *data = user;
2385 isl_bool test;
2386 enum isl_from_pw_aff_state state;
2387
2388 state = data->p[data->n].state;
2389 if (state == isl_state_single) {
2390 isl_aff *aff0;
2391 isl_set *eq;
2392 isl_bool subset1, subset2 = isl_bool_false;
2393 aff0 = isl_aff_list_get_aff(list: data->p[data->n].aff_list, index: 0);
2394 eq = isl_aff_eq_set(aff1: isl_aff_copy(aff), aff2: aff0);
2395 subset1 = isl_set_is_subset(set1: set, set2: eq);
2396 if (subset1 >= 0 && !subset1)
2397 subset2 = single_is_subset(data, set: eq);
2398 isl_set_free(set: eq);
2399 if (subset1 < 0 || subset2 < 0)
2400 goto error;
2401 if (subset1)
2402 return extend_domain(data, set, aff, replace: 0);
2403 if (subset2)
2404 return extend_domain(data, set, aff, replace: 1);
2405 }
2406 if (state == isl_state_single || state == isl_state_min) {
2407 test = extends_min(data, set, aff);
2408 if (test < 0)
2409 goto error;
2410 if (test)
2411 return extend_min(data, set, aff);
2412 }
2413 if (state == isl_state_single || state == isl_state_max) {
2414 test = extends_max(data, set, aff);
2415 if (test < 0)
2416 goto error;
2417 if (test)
2418 return extend_max(data, set, aff);
2419 }
2420 if (state != isl_state_none)
2421 data->n++;
2422 set_single(data, set, aff);
2423
2424 return isl_stat_ok;
2425error:
2426 isl_set_free(set);
2427 isl_aff_free(aff);
2428 return isl_stat_error;
2429}
2430
2431/* Construct an isl_ast_expr that evaluates "pa".
2432 * The result is simplified in terms of build->domain.
2433 *
2434 * The domain of "pa" lives in the internal schedule space.
2435 */
2436__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
2437 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2438{
2439 struct isl_from_pw_aff_data data = { NULL };
2440 isl_ast_expr *res = NULL;
2441
2442 pa = isl_ast_build_compute_gist_pw_aff(build, pa);
2443 pa = isl_pw_aff_coalesce(pa);
2444 if (!pa)
2445 return NULL;
2446
2447 if (isl_from_pw_aff_data_init(data: &data, build, pa) < 0)
2448 goto error;
2449 set_none(&data);
2450
2451 if (isl_pw_aff_foreach_piece(pwaff: pa, fn: &ast_expr_from_pw_aff, user: &data) >= 0)
2452 res = build_pieces(data: &data);
2453
2454 isl_pw_aff_free(pwaff: pa);
2455 isl_from_pw_aff_data_clear(data: &data);
2456 return res;
2457error:
2458 isl_pw_aff_free(pwaff: pa);
2459 isl_from_pw_aff_data_clear(data: &data);
2460 return NULL;
2461}
2462
2463/* Construct an isl_ast_expr that evaluates "pa".
2464 * The result is simplified in terms of build->domain.
2465 *
2466 * The domain of "pa" lives in the external schedule space.
2467 */
2468__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
2469 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2470{
2471 isl_ast_expr *expr;
2472 isl_bool needs_map;
2473
2474 needs_map = isl_ast_build_need_schedule_map(build);
2475 if (needs_map < 0) {
2476 pa = isl_pw_aff_free(pwaff: pa);
2477 } else if (needs_map) {
2478 isl_multi_aff *ma;
2479 ma = isl_ast_build_get_schedule_map_multi_aff(build);
2480 pa = isl_pw_aff_pullback_multi_aff(pa, ma);
2481 }
2482 expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2483 return expr;
2484}
2485
2486/* Set the ids of the input dimensions of "mpa" to the iterator ids
2487 * of "build".
2488 *
2489 * The domain of "mpa" is assumed to live in the internal schedule domain.
2490 */
2491static __isl_give isl_multi_pw_aff *set_iterator_names(
2492 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2493{
2494 int i;
2495 isl_size n;
2496
2497 n = isl_multi_pw_aff_dim(multi: mpa, type: isl_dim_in);
2498 if (n < 0)
2499 return isl_multi_pw_aff_free(multi: mpa);
2500 for (i = 0; i < n; ++i) {
2501 isl_id *id;
2502
2503 id = isl_ast_build_get_iterator_id(build, pos: i);
2504 mpa = isl_multi_pw_aff_set_dim_id(multi: mpa, type: isl_dim_in, pos: i, id);
2505 }
2506
2507 return mpa;
2508}
2509
2510/* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2511 * the remaining arguments derived from "mpa".
2512 * That is, construct a call or access expression that calls/accesses "arg0"
2513 * with arguments/indices specified by "mpa".
2514 */
2515static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
2516 __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2517 __isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
2518{
2519 int i;
2520 isl_size n;
2521 isl_ctx *ctx;
2522 isl_ast_expr *expr;
2523
2524 ctx = isl_ast_build_get_ctx(build);
2525
2526 n = isl_multi_pw_aff_dim(multi: mpa, type: isl_dim_out);
2527 expr = n >= 0 ? isl_ast_expr_alloc_op(ctx, op: type, n_arg: 1 + n) : NULL;
2528 expr = isl_ast_expr_op_add_arg(expr, arg: arg0);
2529 for (i = 0; i < n; ++i) {
2530 isl_pw_aff *pa;
2531 isl_ast_expr *arg;
2532
2533 pa = isl_multi_pw_aff_get_pw_aff(multi: mpa, pos: i);
2534 arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2535 expr = isl_ast_expr_op_add_arg(expr, arg);
2536 }
2537
2538 isl_multi_pw_aff_free(multi: mpa);
2539 return expr;
2540}
2541
2542static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2543 __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2544 __isl_take isl_multi_pw_aff *mpa);
2545
2546/* Construct an isl_ast_expr that accesses the member specified by "mpa".
2547 * The range of "mpa" is assumed to be wrapped relation.
2548 * The domain of this wrapped relation specifies the structure being
2549 * accessed, while the range of this wrapped relation spacifies the
2550 * member of the structure being accessed.
2551 *
2552 * The domain of "mpa" is assumed to live in the internal schedule domain.
2553 */
2554static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
2555 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2556{
2557 isl_id *id;
2558 isl_multi_pw_aff *domain;
2559 isl_ast_expr *domain_expr, *expr;
2560 enum isl_ast_expr_op_type type = isl_ast_expr_op_access;
2561
2562 domain = isl_multi_pw_aff_copy(multi: mpa);
2563 domain = isl_multi_pw_aff_range_factor_domain(multi: domain);
2564 domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
2565 type, mpa: domain);
2566 mpa = isl_multi_pw_aff_range_factor_range(multi: mpa);
2567 if (!isl_multi_pw_aff_has_tuple_id(multi: mpa, type: isl_dim_out))
2568 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2569 "missing field name", goto error);
2570 id = isl_multi_pw_aff_get_tuple_id(multi: mpa, type: isl_dim_out);
2571 expr = isl_ast_expr_from_id(id);
2572 expr = isl_ast_expr_alloc_binary(type: isl_ast_expr_op_member,
2573 expr1: domain_expr, expr2: expr);
2574 return isl_ast_build_with_arguments(build, type, arg0: expr, mpa);
2575error:
2576 isl_multi_pw_aff_free(multi: mpa);
2577 return NULL;
2578}
2579
2580/* Construct an isl_ast_expr of type "type" that calls or accesses
2581 * the element specified by "mpa".
2582 * The first argument is obtained from the output tuple name.
2583 * The remaining arguments are given by the piecewise affine expressions.
2584 *
2585 * If the range of "mpa" is a mapped relation, then we assume it
2586 * represents an access to a member of a structure.
2587 *
2588 * The domain of "mpa" is assumed to live in the internal schedule domain.
2589 */
2590static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2591 __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2592 __isl_take isl_multi_pw_aff *mpa)
2593{
2594 isl_ctx *ctx;
2595 isl_id *id;
2596 isl_ast_expr *expr;
2597
2598 if (!mpa)
2599 goto error;
2600
2601 if (type == isl_ast_expr_op_access &&
2602 isl_multi_pw_aff_range_is_wrapping(multi: mpa))
2603 return isl_ast_build_from_multi_pw_aff_member(build, mpa);
2604
2605 mpa = set_iterator_names(build, mpa);
2606 if (!build || !mpa)
2607 goto error;
2608
2609 ctx = isl_ast_build_get_ctx(build);
2610
2611 if (isl_multi_pw_aff_has_tuple_id(multi: mpa, type: isl_dim_out))
2612 id = isl_multi_pw_aff_get_tuple_id(multi: mpa, type: isl_dim_out);
2613 else
2614 id = isl_id_alloc(ctx, name: "", NULL);
2615
2616 expr = isl_ast_expr_from_id(id);
2617 return isl_ast_build_with_arguments(build, type, arg0: expr, mpa);
2618error:
2619 isl_multi_pw_aff_free(multi: mpa);
2620 return NULL;
2621}
2622
2623/* Construct an isl_ast_expr of type "type" that calls or accesses
2624 * the element specified by "pma".
2625 * The first argument is obtained from the output tuple name.
2626 * The remaining arguments are given by the piecewise affine expressions.
2627 *
2628 * The domain of "pma" is assumed to live in the internal schedule domain.
2629 */
2630static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
2631 __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2632 __isl_take isl_pw_multi_aff *pma)
2633{
2634 isl_multi_pw_aff *mpa;
2635
2636 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2637 return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2638}
2639
2640/* Construct an isl_ast_expr of type "type" that calls or accesses
2641 * the element specified by "mpa".
2642 * The first argument is obtained from the output tuple name.
2643 * The remaining arguments are given by the piecewise affine expressions.
2644 *
2645 * The domain of "mpa" is assumed to live in the external schedule domain.
2646 */
2647static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
2648 __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2649 __isl_take isl_multi_pw_aff *mpa)
2650{
2651 isl_bool is_domain;
2652 isl_bool needs_map;
2653 isl_ast_expr *expr;
2654 isl_space *space_build, *space_mpa;
2655
2656 space_build = isl_ast_build_get_space(build, internal: 0);
2657 space_mpa = isl_multi_pw_aff_get_space(multi: mpa);
2658 is_domain = isl_space_tuple_is_equal(space1: space_build, type1: isl_dim_set,
2659 space2: space_mpa, type2: isl_dim_in);
2660 isl_space_free(space: space_build);
2661 isl_space_free(space: space_mpa);
2662 if (is_domain < 0)
2663 goto error;
2664 if (!is_domain)
2665 isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2666 "spaces don't match", goto error);
2667
2668 needs_map = isl_ast_build_need_schedule_map(build);
2669 if (needs_map < 0)
2670 goto error;
2671 if (needs_map) {
2672 isl_multi_aff *ma;
2673 ma = isl_ast_build_get_schedule_map_multi_aff(build);
2674 mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
2675 }
2676
2677 expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2678 return expr;
2679error:
2680 isl_multi_pw_aff_free(multi: mpa);
2681 return NULL;
2682}
2683
2684/* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2685 * The name of the function is obtained from the output tuple name.
2686 * The arguments are given by the piecewise affine expressions.
2687 *
2688 * The domain of "mpa" is assumed to live in the external schedule domain.
2689 */
2690__isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
2691 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2692{
2693 return isl_ast_build_from_multi_pw_aff(build,
2694 type: isl_ast_expr_op_call, mpa);
2695}
2696
2697/* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2698 * The name of the array is obtained from the output tuple name.
2699 * The index expressions are given by the piecewise affine expressions.
2700 *
2701 * The domain of "mpa" is assumed to live in the external schedule domain.
2702 */
2703__isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
2704 __isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2705{
2706 return isl_ast_build_from_multi_pw_aff(build,
2707 type: isl_ast_expr_op_access, mpa);
2708}
2709
2710/* Construct an isl_ast_expr of type "type" that calls or accesses
2711 * the element specified by "pma".
2712 * The first argument is obtained from the output tuple name.
2713 * The remaining arguments are given by the piecewise affine expressions.
2714 *
2715 * The domain of "pma" is assumed to live in the external schedule domain.
2716 */
2717static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
2718 __isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2719 __isl_take isl_pw_multi_aff *pma)
2720{
2721 isl_multi_pw_aff *mpa;
2722
2723 mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2724 return isl_ast_build_from_multi_pw_aff(build, type, mpa);
2725}
2726
2727/* Construct an isl_ast_expr that calls the domain element specified by "pma".
2728 * The name of the function is obtained from the output tuple name.
2729 * The arguments are given by the piecewise affine expressions.
2730 *
2731 * The domain of "pma" is assumed to live in the external schedule domain.
2732 */
2733__isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
2734 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2735{
2736 return isl_ast_build_from_pw_multi_aff(build,
2737 type: isl_ast_expr_op_call, pma);
2738}
2739
2740/* Construct an isl_ast_expr that accesses the array element specified by "pma".
2741 * The name of the array is obtained from the output tuple name.
2742 * The index expressions are given by the piecewise affine expressions.
2743 *
2744 * The domain of "pma" is assumed to live in the external schedule domain.
2745 */
2746__isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
2747 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2748{
2749 return isl_ast_build_from_pw_multi_aff(build,
2750 type: isl_ast_expr_op_access, pma);
2751}
2752
2753/* Construct an isl_ast_expr that calls the domain element
2754 * specified by "executed".
2755 *
2756 * "executed" is assumed to be single-valued, with a domain that lives
2757 * in the internal schedule space.
2758 */
2759__isl_give isl_ast_node *isl_ast_build_call_from_executed(
2760 __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
2761{
2762 isl_pw_multi_aff *iteration;
2763 isl_ast_expr *expr;
2764
2765 iteration = isl_pw_multi_aff_from_map(map: executed);
2766 iteration = isl_ast_build_compute_gist_pw_multi_aff(build, pma: iteration);
2767 iteration = isl_pw_multi_aff_intersect_domain(pma: iteration,
2768 set: isl_ast_build_get_domain(build));
2769 expr = isl_ast_build_from_pw_multi_aff_internal(build,
2770 type: isl_ast_expr_op_call, pma: iteration);
2771 return isl_ast_node_alloc_user(expr);
2772}
2773

source code of polly/lib/External/isl/isl_ast_build_expr.c