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