Coverage Report

Created: 2019-04-21 11:35

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_ast_build_expr.c
Line
Count
Source (jump to first uncovered line)
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
static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
31
  __isl_take isl_val *d)
32
7
{
33
7
  aff = isl_aff_neg(aff);
34
7
  aff = isl_aff_add_constant_val(aff, d);
35
7
  aff = isl_aff_add_constant_si(aff, -1);
36
7
37
7
  return aff;
38
7
}
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
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
4
{
78
4
  isl_aff *shifted;
79
4
  isl_val *shift;
80
4
  int is_zero;
81
4
  int non_neg;
82
4
83
4
  if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))
84
2
    return 0;
85
2
86
2
  shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));
87
2
  shift = isl_val_floor(shift);
88
2
  is_zero = isl_val_is_zero(shift);
89
2
  if (is_zero < 0 || is_zero) {
90
2
    isl_val_free(shift);
91
2
    return is_zero < 0 ? 
-10
: 0;
92
2
  }
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
0
99
0
  return non_neg;
100
0
}
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
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
0
{
131
0
  isl_set *domain;
132
0
  isl_val *shift, *t;
133
0
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
0
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
0
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
0
146
0
  shift = isl_val_mul(shift, isl_val_copy(d));
147
0
  return isl_aff_add_constant_val(aff, shift);
148
0
}
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
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
7
{
187
7
  isl_ctx *ctx = isl_local_space_get_ctx(ls);
188
7
  isl_aff *aff;
189
7
  isl_ast_expr *num, *den;
190
7
  isl_val *d;
191
7
  enum isl_ast_op_type type;
192
7
193
7
  aff = isl_local_space_get_div(ls, pos);
194
7
  d = isl_aff_get_denominator_val(aff);
195
7
  aff = isl_aff_scale_val(aff, isl_val_copy(d));
196
7
  den = isl_ast_expr_from_val(isl_val_copy(d));
197
7
198
7
  type = isl_ast_op_fdiv_q;
199
7
  if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
200
7
    int non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);
201
7
    if (non_neg >= 0 && !non_neg) {
202
4
      isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),
203
4
              isl_val_copy(d));
204
4
      non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);
205
4
      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
0
      } else
210
4
        isl_aff_free(opp);
211
4
    }
212
7
    if (non_neg >= 0 && !non_neg) {
213
4
      non_neg = is_non_neg_after_stealing(aff, d, data);
214
4
      if (non_neg >= 0 && non_neg)
215
0
        aff = steal_from_cst(aff, d, data);
216
4
    }
217
7
    if (non_neg < 0)
218
0
      aff = isl_aff_free(aff);
219
7
    else if (non_neg)
220
3
      type = isl_ast_op_pdiv_q;
221
7
  }
222
7
223
7
  isl_val_free(d);
224
7
  num = isl_ast_expr_from_aff(aff, data->build);
225
7
  return isl_ast_expr_alloc_binary(type, num, den);
226
7
}
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
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
2.24k
{
240
2.24k
  isl_ctx *ctx = isl_local_space_get_ctx(ls);
241
2.24k
  isl_id *id;
242
2.24k
243
2.24k
  if (type == isl_dim_div)
244
7
    return var_div(data, ls, pos);
245
2.23k
246
2.23k
  if (type == isl_dim_set) {
247
1.98k
    id = isl_ast_build_get_iterator_id(data->build, pos);
248
1.98k
    return isl_ast_expr_from_id(id);
249
1.98k
  }
250
249
251
249
  if (!isl_local_space_has_dim_id(ls, type, pos))
252
249
    
isl_die0
(ctx, isl_error_internal, "unnamed dimension",
253
249
      return NULL);
254
249
  id = isl_local_space_get_dim_id(ls, type, pos);
255
249
  return isl_ast_expr_from_id(id);
256
249
}
257
258
/* Does "expr" represent the zero integer?
259
 */
260
static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
261
6.93k
{
262
6.93k
  if (!expr)
263
0
    return -1;
264
6.93k
  if (expr->type != isl_ast_expr_int)
265
2.14k
    return 0;
266
4.78k
  return isl_val_is_zero(expr->u.v);
267
4.78k
}
268
269
/* Create an expression representing the sum of "expr1" and "expr2",
270
 * provided neither of the two expressions is identically zero.
271
 */
272
static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
273
  __isl_take isl_ast_expr *expr2)
274
3.25k
{
275
3.25k
  if (!expr1 || !expr2)
276
0
    goto error;
277
3.25k
278
3.25k
  if (ast_expr_is_zero(expr1)) {
279
1.93k
    isl_ast_expr_free(expr1);
280
1.93k
    return expr2;
281
1.93k
  }
282
1.32k
283
1.32k
  if (ast_expr_is_zero(expr2)) {
284
0
    isl_ast_expr_free(expr2);
285
0
    return expr1;
286
0
  }
287
1.32k
288
1.32k
  return isl_ast_expr_add(expr1, expr2);
289
0
error:
290
0
  isl_ast_expr_free(expr1);
291
0
  isl_ast_expr_free(expr2);
292
0
  return NULL;
293
1.32k
}
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
static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
307
  __isl_take isl_ast_expr *expr2)
308
2.04k
{
309
2.04k
  if (!expr1 || !expr2)
310
0
    goto error;
311
2.04k
312
2.04k
  if (ast_expr_is_zero(expr2)) {
313
2.03k
    isl_ast_expr_free(expr2);
314
2.03k
    return expr1;
315
2.03k
  }
316
13
317
13
  if (ast_expr_is_zero(expr1)) {
318
1
    isl_ast_expr_free(expr1);
319
1
    return isl_ast_expr_neg(expr2);
320
1
  }
321
12
322
12
  return isl_ast_expr_sub(expr1, expr2);
323
0
error:
324
0
  isl_ast_expr_free(expr1);
325
0
  isl_ast_expr_free(expr2);
326
0
  return NULL;
327
12
}
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
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
6
{
340
6
  isl_ast_expr *expr;
341
6
  isl_ast_expr *c;
342
6
343
6
  if (!aff)
344
0
    return NULL;
345
6
346
6
  expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
347
6
348
6
  c = isl_ast_expr_from_val(isl_val_copy(d));
349
6
  expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
350
6
351
6
  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
0
  }
355
6
356
6
  return expr;
357
6
}
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
static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
371
  __isl_take isl_val *v)
372
2.24k
{
373
2.24k
  isl_ast_expr *c;
374
2.24k
375
2.24k
  if (!expr || !v)
376
0
    goto error;
377
2.24k
  if (isl_val_is_one(v)) {
378
865
    isl_val_free(v);
379
865
    return expr;
380
865
  }
381
1.37k
382
1.37k
  if (isl_val_is_negone(v)) {
383
11
    isl_val_free(v);
384
11
    expr = isl_ast_expr_neg(expr);
385
1.36k
  } else {
386
1.36k
    c = isl_ast_expr_from_val(v);
387
1.36k
    expr = isl_ast_expr_mul(c, expr);
388
1.36k
  }
389
1.37k
390
1.37k
  return expr;
391
0
error:
392
0
  isl_val_free(v);
393
0
  isl_ast_expr_free(expr);
394
0
  return NULL;
395
1.37k
}
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
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
2.24k
{
425
2.24k
  isl_ast_expr *term;
426
2.24k
427
2.24k
  if (!expr)
428
0
    return NULL;
429
2.24k
430
2.24k
  data->v = v;
431
2.24k
  term = var(data, ls, type, pos);
432
2.24k
  v = data->v;
433
2.24k
434
2.24k
  if (isl_val_is_neg(v) && 
!ast_expr_is_zero(expr)23
) {
435
2
    v = isl_val_neg(v);
436
2
    term = scale(term, v);
437
2
    return ast_expr_sub(expr, term);
438
2.24k
  } else {
439
2.24k
    term = scale(term, v);
440
2.24k
    return ast_expr_add(expr, term);
441
2.24k
  }
442
2.24k
}
443
444
/* Add an expression for "v" to expr.
445
 */
446
static __isl_give isl_ast_expr *isl_ast_expr_add_int(
447
  __isl_take isl_ast_expr *expr, __isl_take isl_val *v)
448
2.16k
{
449
2.16k
  isl_ast_expr *expr_int;
450
2.16k
451
2.16k
  if (!expr || !v)
452
0
    goto error;
453
2.16k
454
2.16k
  if (isl_val_is_zero(v)) {
455
1.15k
    isl_val_free(v);
456
1.15k
    return expr;
457
1.15k
  }
458
1.01k
459
1.01k
  if (isl_val_is_neg(v) && 
!ast_expr_is_zero(expr)42
) {
460
10
    v = isl_val_neg(v);
461
10
    expr_int = isl_ast_expr_from_val(v);
462
10
    return ast_expr_sub(expr, expr_int);
463
1.00k
  } else {
464
1.00k
    expr_int = isl_ast_expr_from_val(v);
465
1.00k
    return ast_expr_add(expr, expr_int);
466
1.00k
  }
467
0
error:
468
0
  isl_ast_expr_free(expr);
469
0
  isl_val_free(v);
470
0
  return NULL;
471
1.01k
}
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
static int extract_term_and_mod(struct isl_extract_mod_data *data,
528
  __isl_take isl_aff *term, __isl_take isl_aff *arg)
529
6
{
530
6
  isl_ast_expr *expr;
531
6
  int s;
532
6
533
6
  data->v = isl_val_div(data->v, isl_val_copy(data->d));
534
6
  s = isl_val_sgn(data->v);
535
6
  data->v = isl_val_abs(data->v);
536
6
  expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
537
6
  isl_aff_free(arg);
538
6
  if (s > 0)
539
1
    data->neg = ast_expr_add(data->neg, expr);
540
5
  else
541
5
    data->pos = ast_expr_add(data->pos, expr);
542
6
  data->aff = isl_aff_set_coefficient_si(data->aff,
543
6
            isl_dim_div, data->i, 0);
544
6
  if (s < 0)
545
5
    data->v = isl_val_neg(data->v);
546
6
  term = isl_aff_scale_val(term, isl_val_copy(data->v));
547
6
548
6
  if (!data->add)
549
6
    data->add = term;
550
0
  else
551
0
    data->add = isl_aff_add(data->add, term);
552
6
  if (!data->add)
553
0
    return -1;
554
6
555
6
  return 0;
556
6
}
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
static int extract_mod(struct isl_extract_mod_data *data)
577
0
{
578
0
  return extract_term_and_mod(data, isl_aff_copy(data->div),
579
0
      isl_aff_copy(data->div));
580
0
}
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
static int extract_nonneg_mod(struct isl_extract_mod_data *data)
601
2
{
602
2
  int mod;
603
2
604
2
  mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
605
2
  if (mod < 0)
606
0
    goto error;
607
2
  if (mod)
608
0
    return extract_mod(data);
609
2
610
2
  data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
611
2
  mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
612
2
  if (mod < 0)
613
0
    goto error;
614
2
  if (mod) {
615
0
    data->v = isl_val_neg(data->v);
616
0
    return extract_mod(data);
617
0
  }
618
2
619
2
  return 0;
620
0
error:
621
0
  data->aff = isl_aff_free(data->aff);
622
0
  return -1;
623
2
}
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
static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
637
  __isl_keep isl_constraint *c)
638
10
{
639
10
  isl_val *v1, *v2;
640
10
  int simpler;
641
10
642
10
  if (!data->nonneg)
643
6
    return 1;
644
4
645
4
  v1 = isl_val_abs(isl_constraint_get_constant_val(c));
646
4
  v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
647
4
  simpler = isl_val_lt(v1, v2);
648
4
  isl_val_free(v1);
649
4
  isl_val_free(v2);
650
4
651
4
  return simpler;
652
4
}
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
static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
676
  void *user)
677
23
{
678
23
  struct isl_extract_mod_data *data = user;
679
23
  enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
680
23
  enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
681
23
  int i, t;
682
23
  int n[2];
683
23
  int parallel = 1, opposite = 1;
684
23
685
69
  for (t = 0; t < 2; 
++t46
) {
686
46
    n[t] = isl_constraint_dim(c, c_type[t]);
687
111
    for (i = 0; i < n[t]; 
++i65
) {
688
65
      int a, b;
689
65
690
65
      a = isl_constraint_involves_dims(c, c_type[t], i, 1);
691
65
      b = isl_aff_involves_dims(data->div, a_type[t], i, 1);
692
65
      if (a != b)
693
21
        parallel = opposite = 0;
694
65
    }
695
46
  }
696
23
697
23
  if (parallel || 
opposite11
) {
698
12
    isl_val *v;
699
12
700
12
    v = isl_val_abs(isl_constraint_get_constant_val(c));
701
12
    if (isl_val_cmp_si(v, 1 << 15) > 0)
702
2
      parallel = opposite = 0;
703
12
    isl_val_free(v);
704
12
  }
705
23
706
69
  for (t = 0; t < 2; 
++t46
) {
707
62
    for (i = 0; i < n[t]; 
++i16
) {
708
33
      isl_val *v1, *v2;
709
33
710
33
      if (!parallel && 
!opposite18
)
711
17
        break;
712
16
      v1 = isl_constraint_get_coefficient_val(c,
713
16
                c_type[t], i);
714
16
      v2 = isl_aff_get_coefficient_val(data->div,
715
16
                a_type[t], i);
716
16
      if (parallel) {
717
15
        v1 = isl_val_sub(v1, isl_val_copy(v2));
718
15
        parallel = isl_val_is_divisible_by(v1, data->d);
719
15
        v1 = isl_val_add(v1, isl_val_copy(v2));
720
15
      }
721
16
      if (opposite) {
722
16
        v1 = isl_val_add(v1, isl_val_copy(v2));
723
16
        opposite = isl_val_is_divisible_by(v1, data->d);
724
16
      }
725
16
      isl_val_free(v1);
726
16
      isl_val_free(v2);
727
16
    }
728
46
  }
729
23
730
23
  if ((parallel || 
opposite18
) &&
mod_constraint_is_simpler(data, c)10
) {
731
6
    isl_aff_free(data->nonneg);
732
6
    data->nonneg = isl_constraint_get_aff(c);
733
6
    data->sign = parallel ? 
15
:
-11
;
734
6
  }
735
23
736
23
  isl_constraint_free(c);
737
23
738
23
  if (data->sign != 0 && 
data->nonneg == NULL14
)
739
23
    
return isl_stat_error0
;
740
23
741
23
  return isl_stat_ok;
742
23
}
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
static int try_extract_mod(struct isl_extract_mod_data *data)
824
8
{
825
8
  isl_basic_set *hull;
826
8
  isl_val *v1, *v2;
827
8
  int r, n;
828
8
829
8
  if (!data->build)
830
0
    goto error;
831
8
832
8
  n = isl_aff_dim(data->div, isl_dim_div);
833
8
834
8
  if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
835
0
    return extract_nonneg_mod(data);
836
8
837
8
  hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
838
8
  hull = isl_basic_set_remove_divs(hull);
839
8
  data->sign = 0;
840
8
  data->nonneg = NULL;
841
8
  r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
842
8
          data);
843
8
  isl_basic_set_free(hull);
844
8
845
8
  if (!data->sign || 
r < 06
) {
846
2
    isl_aff_free(data->nonneg);
847
2
    if (r < 0)
848
0
      goto error;
849
2
    return extract_nonneg_mod(data);
850
2
  }
851
6
852
6
  v1 = isl_aff_get_constant_val(data->div);
853
6
  v2 = isl_aff_get_constant_val(data->nonneg);
854
6
  if (data->sign < 0) {
855
1
    v1 = isl_val_neg(v1);
856
1
    v1 = isl_val_add(v1, isl_val_copy(data->d));
857
1
    v1 = isl_val_sub_ui(v1, 1);
858
1
  }
859
6
  v1 = isl_val_sub(v1, isl_val_copy(v2));
860
6
  v1 = isl_val_mod(v1, isl_val_copy(data->d));
861
6
  v1 = isl_val_add(v1, v2);
862
6
  v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
863
6
  v2 = isl_val_ceil(v2);
864
6
  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
0
  }
868
6
  data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
869
6
  isl_val_free(v2);
870
6
871
6
  if (data->sign < 0) {
872
1
    data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
873
1
    data->v = isl_val_neg(data->v);
874
1
  }
875
6
876
6
  return extract_term_and_mod(data,
877
6
            isl_aff_copy(data->div), data->nonneg);
878
0
error:
879
0
  data->aff = isl_aff_free(data->aff);
880
0
  return -1;
881
6
}
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
static int extract_modulo(struct isl_extract_mod_data *data)
915
8
{
916
8
  data->div = isl_aff_get_div(data->aff, data->i);
917
8
  data->d = isl_aff_get_denominator_val(data->div);
918
8
  if (isl_val_is_divisible_by(data->v, data->d)) {
919
8
    data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
920
8
    if (try_extract_mod(data) < 0)
921
0
      data->aff = isl_aff_free(data->aff);
922
8
  }
923
8
  isl_aff_free(data->div);
924
8
  isl_val_free(data->d);
925
8
  return 0;
926
8
}
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
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
2.16k
{
955
2.16k
  struct isl_extract_mod_data data = { build, aff, *pos, *neg };
956
2.16k
  isl_ctx *ctx;
957
2.16k
  int n;
958
2.16k
959
2.16k
  if (!aff)
960
0
    return NULL;
961
2.16k
962
2.16k
  ctx = isl_aff_get_ctx(aff);
963
2.16k
  if (!isl_options_get_ast_build_prefer_pdiv(ctx))
964
0
    return aff;
965
2.16k
966
2.16k
  n = isl_aff_dim(data.aff, isl_dim_div);
967
2.19k
  for (data.i = 0; data.i < n; 
++data.i24
) {
968
24
    data.v = isl_aff_get_coefficient_val(data.aff,
969
24
              isl_dim_div, data.i);
970
24
    if (!data.v)
971
0
      return isl_aff_free(aff);
972
24
    if (isl_val_is_zero(data.v) ||
973
24
        
isl_val_is_one(data.v)13
||
isl_val_is_negone(data.v)8
) {
974
16
      isl_val_free(data.v);
975
16
      continue;
976
16
    }
977
8
    if (extract_modulo(&data) < 0)
978
0
      data.aff = isl_aff_free(data.aff);
979
8
    isl_val_free(data.v);
980
8
    if (!data.aff)
981
0
      break;
982
8
  }
983
2.16k
984
2.16k
  if (data.add)
985
6
    data.aff = isl_aff_add(data.aff, data.add);
986
2.16k
987
2.16k
  *pos = data.pos;
988
2.16k
  *neg = data.neg;
989
2.16k
  return data.aff;
990
2.16k
}
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
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
2.03k
{
1003
2.03k
  int i, j, n;
1004
2.03k
  isl_aff *rat = NULL;
1005
2.03k
  isl_local_space *ls = NULL;
1006
2.03k
  isl_ast_expr *rat_expr;
1007
2.03k
  isl_val *v, *d;
1008
2.03k
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1009
2.03k
  enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1010
2.03k
1011
2.03k
  if (!aff)
1012
0
    return NULL;
1013
2.03k
  d = isl_aff_get_denominator_val(aff);
1014
2.03k
  if (!d)
1015
0
    goto error;
1016
2.03k
  if (isl_val_is_one(d)) {
1017
2.02k
    isl_val_free(d);
1018
2.02k
    return aff;
1019
2.02k
  }
1020
2
1021
2
  aff = isl_aff_scale_val(aff, isl_val_copy(d));
1022
2
1023
2
  ls = isl_aff_get_domain_local_space(aff);
1024
2
  rat = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1025
2
1026
8
  for (i = 0; i < 3; 
++i6
) {
1027
6
    n = isl_aff_dim(aff, t[i]);
1028
10
    for (j = 0; j < n; 
++j4
) {
1029
4
      isl_aff *rat_j;
1030
4
1031
4
      v = isl_aff_get_coefficient_val(aff, t[i], j);
1032
4
      if (!v)
1033
0
        goto error;
1034
4
      if (isl_val_is_divisible_by(v, d)) {
1035
2
        isl_val_free(v);
1036
2
        continue;
1037
2
      }
1038
2
      rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls),
1039
2
              l[i], j);
1040
2
      rat_j = isl_aff_scale_val(rat_j, v);
1041
2
      rat = isl_aff_add(rat, rat_j);
1042
2
    }
1043
6
  }
1044
2
1045
2
  v = isl_aff_get_constant_val(aff);
1046
2
  if (isl_val_is_divisible_by(v, d)) {
1047
2
    isl_val_free(v);
1048
2
  } else {
1049
0
    isl_aff *rat_0;
1050
0
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
0
  }
1054
2
1055
2
  isl_local_space_free(ls);
1056
2
1057
2
  aff = isl_aff_sub(aff, isl_aff_copy(rat));
1058
2
  aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
1059
2
1060
2
  rat_expr = isl_ast_expr_from_aff(rat, build);
1061
2
  rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
1062
2
  *expr = ast_expr_add(*expr, rat_expr);
1063
2
1064
2
  return aff;
1065
0
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
2
}
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
__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
1082
  __isl_keep isl_ast_build *build)
1083
2.03k
{
1084
2.03k
  int i, j;
1085
2.03k
  int n;
1086
2.03k
  isl_val *v;
1087
2.03k
  isl_ctx *ctx = isl_aff_get_ctx(aff);
1088
2.03k
  isl_ast_expr *expr, *expr_neg;
1089
2.03k
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1090
2.03k
  enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1091
2.03k
  isl_local_space *ls;
1092
2.03k
  struct isl_ast_add_term_data data;
1093
2.03k
1094
2.03k
  if (!aff)
1095
0
    return NULL;
1096
2.03k
1097
2.03k
  expr = isl_ast_expr_alloc_int_si(ctx, 0);
1098
2.03k
  expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1099
2.03k
1100
2.03k
  aff = extract_rational(aff, &expr, build);
1101
2.03k
1102
2.03k
  aff = extract_modulos(aff, &expr, &expr_neg, build);
1103
2.03k
  expr = ast_expr_sub(expr, expr_neg);
1104
2.03k
1105
2.03k
  ls = isl_aff_get_domain_local_space(aff);
1106
2.03k
1107
2.03k
  data.build = build;
1108
2.03k
  data.cst = isl_aff_get_constant_val(aff);
1109
8.12k
  for (i = 0; i < 3; 
++i6.09k
) {
1110
6.09k
    n = isl_aff_dim(aff, t[i]);
1111
17.3k
    for (j = 0; j < n; 
++j11.2k
) {
1112
11.2k
      v = isl_aff_get_coefficient_val(aff, t[i], j);
1113
11.2k
      if (!v)
1114
0
        expr = isl_ast_expr_free(expr);
1115
11.2k
      if (isl_val_is_zero(v)) {
1116
9.16k
        isl_val_free(v);
1117
9.16k
        continue;
1118
9.16k
      }
1119
2.09k
      expr = isl_ast_expr_add_term(expr,
1120
2.09k
              ls, l[i], j, v, &data);
1121
2.09k
    }
1122
6.09k
  }
1123
2.03k
1124
2.03k
  expr = isl_ast_expr_add_int(expr, data.cst);
1125
2.03k
1126
2.03k
  isl_local_space_free(ls);
1127
2.03k
  isl_aff_free(aff);
1128
2.03k
  return expr;
1129
2.03k
}
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
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
274
{
1138
274
  int i, j;
1139
274
  isl_val *v;
1140
274
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1141
274
  enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1142
274
  isl_local_space *ls;
1143
274
1144
274
  ls = isl_aff_get_domain_local_space(aff);
1145
274
1146
1.09k
  for (i = 0; i < 3; 
++i822
) {
1147
822
    int n = isl_aff_dim(aff, t[i]);
1148
1.31k
    for (j = 0; j < n; 
++j496
) {
1149
496
      v = isl_aff_get_coefficient_val(aff, t[i], j);
1150
496
      if (sign * isl_val_sgn(v) <= 0) {
1151
343
        isl_val_free(v);
1152
343
        continue;
1153
343
      }
1154
153
      v = isl_val_abs(v);
1155
153
      expr = isl_ast_expr_add_term(expr,
1156
153
            ls, l[i], j, v, data);
1157
153
    }
1158
822
  }
1159
274
1160
274
  isl_local_space_free(ls);
1161
274
1162
274
  return expr;
1163
274
}
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
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
137
{
1177
137
  if (ast_expr_is_zero(pos))
1178
47
    return 1;
1179
90
  if (ast_expr_is_zero(neg))
1180
78
    return 0;
1181
12
  return isl_val_is_pos(v);
1182
12
}
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
static int is_stride_constraint(__isl_keep isl_aff *aff, int pos)
1211
3
{
1212
3
  isl_aff *div;
1213
3
  isl_val *c, *d;
1214
3
  int eq;
1215
3
1216
3
  div = isl_aff_get_div(aff, pos);
1217
3
  c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1218
3
  d = isl_aff_get_denominator_val(div);
1219
3
  eq = isl_val_abs_eq(c, d);
1220
3
  if (eq >= 0 && eq) {
1221
3
    aff = isl_aff_copy(aff);
1222
3
    aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1223
3
    div = isl_aff_scale_val(div, d);
1224
3
    if (isl_val_is_pos(c))
1225
3
      div = isl_aff_neg(div);
1226
3
    eq = isl_aff_plain_is_equal(div, aff);
1227
3
    isl_aff_free(aff);
1228
3
  } else
1229
0
    isl_val_free(d);
1230
3
  isl_val_free(c);
1231
3
  isl_aff_free(div);
1232
3
1233
3
  return eq;
1234
3
}
1235
1236
/* Are all coefficients of "aff" (zero or) negative?
1237
 */
1238
static int all_negative_coefficients(__isl_keep isl_aff *aff)
1239
3
{
1240
3
  int i, n;
1241
3
1242
3
  if (!aff)
1243
0
    return 0;
1244
3
1245
3
  n = isl_aff_dim(aff, isl_dim_param);
1246
4
  for (i = 0; i < n; 
++i1
)
1247
1
    if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)
1248
0
      return 0;
1249
3
1250
3
  n = isl_aff_dim(aff, isl_dim_in);
1251
5
  for (i = 0; i < n; 
++i2
)
1252
2
    if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)
1253
0
      return 0;
1254
3
1255
3
  return 1;
1256
3
}
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
static __isl_give isl_ast_expr *extract_stride_constraint(
1278
  __isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
1279
3
{
1280
3
  isl_ctx *ctx;
1281
3
  isl_val *c;
1282
3
  isl_ast_expr *expr, *cst;
1283
3
1284
3
  if (!aff)
1285
0
    return NULL;
1286
3
1287
3
  ctx = isl_aff_get_ctx(aff);
1288
3
1289
3
  c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1290
3
  aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1291
3
1292
3
  if (all_negative_coefficients(aff))
1293
3
    aff = isl_aff_neg(aff);
1294
3
1295
3
  cst = isl_ast_expr_from_val(isl_val_abs(c));
1296
3
  expr = isl_ast_expr_from_aff(aff, build);
1297
3
1298
3
  expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst);
1299
3
  cst = isl_ast_expr_alloc_int_si(ctx, 0);
1300
3
  expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst);
1301
3
1302
3
  return expr;
1303
3
}
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
static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1342
  __isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1343
140
{
1344
140
  int i, n;
1345
140
  isl_ctx *ctx;
1346
140
  isl_ast_expr *expr_pos;
1347
140
  isl_ast_expr *expr_neg;
1348
140
  isl_ast_expr *expr;
1349
140
  isl_aff *aff;
1350
140
  int eq;
1351
140
  enum isl_ast_op_type type;
1352
140
  struct isl_ast_add_term_data data;
1353
140
1354
140
  if (!constraint)
1355
0
    return NULL;
1356
140
1357
140
  aff = isl_constraint_get_aff(constraint);
1358
140
  eq = isl_constraint_is_equality(constraint);
1359
140
  isl_constraint_free(constraint);
1360
140
1361
140
  n = isl_aff_dim(aff, isl_dim_div);
1362
140
  if (eq && 
n > 022
)
1363
3
    for (i = 0; i < n; 
++i0
) {
1364
3
      int is_stride;
1365
3
      is_stride = is_stride_constraint(aff, i);
1366
3
      if (is_stride < 0)
1367
0
        goto error;
1368
3
      if (is_stride)
1369
3
        return extract_stride_constraint(aff, i, build);
1370
3
    }
1371
140
1372
140
  ctx = isl_aff_get_ctx(aff);
1373
137
  expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
1374
137
  expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1375
137
1376
137
  aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
1377
137
1378
137
  data.build = build;
1379
137
  data.cst = isl_aff_get_constant_val(aff);
1380
137
  expr_pos = add_signed_terms(expr_pos, aff, 1, &data);
1381
137
  data.cst = isl_val_neg(data.cst);
1382
137
  expr_neg = add_signed_terms(expr_neg, aff, -1, &data);
1383
137
  data.cst = isl_val_neg(data.cst);
1384
137
1385
137
  if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) {
1386
49
    expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
1387
88
  } else {
1388
88
    data.cst = isl_val_neg(data.cst);
1389
88
    expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
1390
88
  }
1391
137
1392
137
  if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
1393
137
      
isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int47
) {
1394
45
    type = eq ? 
isl_ast_op_eq0
: isl_ast_op_le;
1395
45
    expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
1396
92
  } else {
1397
92
    type = eq ? 
isl_ast_op_eq19
:
isl_ast_op_ge73
;
1398
92
    expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
1399
92
  }
1400
137
1401
137
  isl_aff_free(aff);
1402
137
  return expr;
1403
0
error:
1404
0
  isl_aff_free(aff);
1405
0
  return NULL;
1406
140
}
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
static int cmp_constraint(__isl_keep isl_constraint *a,
1414
  __isl_keep isl_constraint *b, void *user)
1415
20
{
1416
20
  int cmp;
1417
20
1418
20
  cmp = isl_constraint_cmp_last_non_zero(a, b);
1419
20
  if (cmp != 0)
1420
14
    return cmp;
1421
6
  return isl_constraint_plain_cmp(a, b);
1422
6
}
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
__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
252
{
1447
252
  int i, n;
1448
252
  isl_constraint *c;
1449
252
  isl_constraint_list *list;
1450
252
  isl_ast_expr *res;
1451
252
  isl_set *set;
1452
252
1453
252
  list = isl_basic_set_get_constraint_list(bset);
1454
252
  isl_basic_set_free(bset);
1455
252
  list = isl_constraint_list_sort(list, &cmp_constraint, NULL);
1456
252
  if (!list)
1457
0
    return NULL;
1458
252
  n = isl_constraint_list_n_constraint(list);
1459
252
  if (n == 0) {
1460
130
    isl_ctx *ctx = isl_constraint_list_get_ctx(list);
1461
130
    isl_constraint_list_free(list);
1462
130
    return isl_ast_expr_alloc_int_si(ctx, 1);
1463
130
  }
1464
122
1465
122
  build = isl_ast_build_copy(build);
1466
122
1467
122
  c = isl_constraint_list_get_constraint(list, 0);
1468
122
  bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1469
122
  set = isl_set_from_basic_set(bset);
1470
122
  res = isl_ast_expr_from_constraint(c, build);
1471
122
  build = isl_ast_build_restrict_generated(build, set);
1472
122
1473
140
  for (i = 1; i < n; 
++i18
) {
1474
18
    isl_ast_expr *expr;
1475
18
1476
18
    c = isl_constraint_list_get_constraint(list, i);
1477
18
    bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1478
18
    set = isl_set_from_basic_set(bset);
1479
18
    expr = isl_ast_expr_from_constraint(c, build);
1480
18
    build = isl_ast_build_restrict_generated(build, set);
1481
18
    res = isl_ast_expr_and(res, expr);
1482
18
  }
1483
122
1484
122
  isl_constraint_list_free(list);
1485
122
  isl_ast_build_free(build);
1486
122
  return res;
1487
122
}
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
__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
236
{
1513
236
  int i, n;
1514
236
  isl_basic_set *bset;
1515
236
  isl_basic_set_list *list;
1516
236
  isl_set *domain;
1517
236
  isl_ast_expr *res;
1518
236
1519
236
  list = isl_set_get_basic_set_list(set);
1520
236
  isl_set_free(set);
1521
236
1522
236
  if (!list)
1523
0
    return NULL;
1524
236
  n = isl_basic_set_list_n_basic_set(list);
1525
236
  if (n == 0) {
1526
3
    isl_ctx *ctx = isl_ast_build_get_ctx(build);
1527
3
    isl_basic_set_list_free(list);
1528
3
    return isl_ast_expr_from_val(isl_val_zero(ctx));
1529
3
  }
1530
233
1531
233
  domain = isl_ast_build_get_domain(build);
1532
233
1533
233
  bset = isl_basic_set_list_get_basic_set(list, 0);
1534
233
  set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1535
233
  res = isl_ast_build_expr_from_basic_set(build, bset);
1536
233
1537
252
  for (i = 1; i < n; 
++i19
) {
1538
19
    isl_ast_expr *expr;
1539
19
    isl_set *rest;
1540
19
1541
19
    rest = isl_set_subtract(isl_set_copy(domain), set);
1542
19
    rest = isl_set_from_basic_set(isl_set_simple_hull(rest));
1543
19
    domain = isl_set_intersect(domain, rest);
1544
19
    bset = isl_basic_set_list_get_basic_set(list, i);
1545
19
    set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1546
19
    bset = isl_basic_set_gist(bset,
1547
19
        isl_set_simple_hull(isl_set_copy(domain)));
1548
19
    expr = isl_ast_build_expr_from_basic_set(build, bset);
1549
19
    res = isl_ast_expr_or(res, expr);
1550
19
  }
1551
233
1552
233
  isl_set_free(domain);
1553
233
  isl_set_free(set);
1554
233
  isl_basic_set_list_free(list);
1555
233
  return res;
1556
233
}
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
__isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1571
  __isl_keep isl_ast_build *build, __isl_take isl_set *set)
1572
186
{
1573
186
  if (isl_ast_build_need_schedule_map(build)) {
1574
3
    isl_multi_aff *ma;
1575
3
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
1576
3
    set = isl_set_preimage_multi_aff(set, ma);
1577
3
  }
1578
186
1579
186
  set = isl_set_compute_divs(set);
1580
186
  set = isl_ast_build_compute_gist(build, set);
1581
186
  return isl_ast_build_expr_from_set_internal(build, set);
1582
186
}
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
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
2.00k
{
1649
2.00k
  int n;
1650
2.00k
  isl_ctx *ctx;
1651
2.00k
1652
2.00k
  ctx = isl_pw_aff_get_ctx(pa);
1653
2.00k
  n = isl_pw_aff_n_piece(pa);
1654
2.00k
  if (n == 0)
1655
2.00k
    
isl_die0
(ctx, isl_error_invalid,
1656
2.00k
      "cannot handle void expression", return isl_stat_error);
1657
2.00k
  data->max = n;
1658
2.00k
  data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
1659
2.00k
  if (!data->p)
1660
0
    return isl_stat_error;
1661
2.00k
  data->build = build;
1662
2.00k
  data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1663
2.00k
  data->n = 0;
1664
2.00k
1665
2.00k
  return isl_stat_ok;
1666
2.00k
}
1667
1668
/* Free all memory allocated for "data".
1669
 */
1670
static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)
1671
2.00k
{
1672
2.00k
  int i;
1673
2.00k
1674
2.00k
  isl_set_free(data->dom);
1675
2.00k
  if (!data->p)
1676
0
    return;
1677
2.00k
1678
4.01k
  
for (i = 0; 2.00k
i < data->max;
++i2.01k
) {
1679
2.01k
    isl_set_free(data->p[i].set);
1680
2.01k
    isl_set_list_free(data->p[i].set_list);
1681
2.01k
    isl_aff_list_free(data->p[i].aff_list);
1682
2.01k
  }
1683
2.00k
  free(data->p);
1684
2.00k
}
1685
1686
/* Initialize the current entry of "data" to an unused piece.
1687
 */
1688
static void set_none(struct isl_from_pw_aff_data *data)
1689
2.00k
{
1690
2.00k
  data->p[data->n].state = isl_state_none;
1691
2.00k
  data->p[data->n].set_list = NULL;
1692
2.00k
  data->p[data->n].aff_list = NULL;
1693
2.00k
}
1694
1695
/* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1696
 */
1697
static void set_single(struct isl_from_pw_aff_data *data,
1698
  __isl_take isl_set *set, __isl_take isl_aff *aff)
1699
2.00k
{
1700
2.00k
  data->p[data->n].state = isl_state_single;
1701
2.00k
  data->p[data->n].set_list = isl_set_list_from_set(set);
1702
2.00k
  data->p[data->n].aff_list = isl_aff_list_from_aff(aff);
1703
2.00k
}
1704
1705
/* Extend the current entry of "data" with "set" and "aff"
1706
 * as a minimum expression.
1707
 */
1708
static isl_stat extend_min(struct isl_from_pw_aff_data *data,
1709
  __isl_take isl_set *set, __isl_take isl_aff *aff)
1710
4
{
1711
4
  int n = data->n;
1712
4
  data->p[n].state = isl_state_min;
1713
4
  data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1714
4
  data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1715
4
1716
4
  if (!data->p[n].set_list || !data->p[n].aff_list)
1717
0
    return isl_stat_error;
1718
4
  return isl_stat_ok;
1719
4
}
1720
1721
/* Extend the current entry of "data" with "set" and "aff"
1722
 * as a maximum expression.
1723
 */
1724
static isl_stat extend_max(struct isl_from_pw_aff_data *data,
1725
  __isl_take isl_set *set, __isl_take isl_aff *aff)
1726
3
{
1727
3
  int n = data->n;
1728
3
  data->p[n].state = isl_state_max;
1729
3
  data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1730
3
  data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1731
3
1732
3
  if (!data->p[n].set_list || !data->p[n].aff_list)
1733
0
    return isl_stat_error;
1734
3
  return isl_stat_ok;
1735
3
}
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
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
0
{
1745
0
  int n = data->n;
1746
0
  isl_set *set_n;
1747
0
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
0
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
0
  else
1757
0
    isl_aff_free(aff);
1758
0
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
0
}
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
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
2.00k
{
1774
2.00k
  int i, n;
1775
2.00k
  isl_aff *aff;
1776
2.00k
  isl_ast_expr *expr;
1777
2.00k
  enum isl_ast_op_type op_type;
1778
2.00k
1779
2.00k
  if (state == isl_state_single) {
1780
1.99k
    aff = isl_aff_list_get_aff(list, 0);
1781
1.99k
    isl_aff_list_free(list);
1782
1.99k
    return isl_ast_expr_from_aff(aff, build);
1783
1.99k
  }
1784
7
  n = isl_aff_list_n_aff(list);
1785
7
  op_type = state == isl_state_min ? 
isl_ast_op_min4
:
isl_ast_op_max3
;
1786
7
  expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n);
1787
7
  if (!expr)
1788
0
    goto error;
1789
7
1790
21
  
for (i = 0; 7
i < n;
++i14
) {
1791
14
    isl_ast_expr *expr_i;
1792
14
1793
14
    aff = isl_aff_list_get_aff(list, i);
1794
14
    expr_i = isl_ast_expr_from_aff(aff, build);
1795
14
    if (!expr_i)
1796
0
      goto error;
1797
14
    expr->u.op.args[i] = expr_i;
1798
14
  }
1799
7
1800
7
  isl_aff_list_free(list);
1801
7
  return expr;
1802
0
error:
1803
0
  isl_aff_list_free(list);
1804
0
  isl_ast_expr_free(expr);
1805
0
  return NULL;
1806
7
}
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
static isl_ast_expr **add_intermediate_piece(struct isl_from_pw_aff_data *data,
1822
  int pos, isl_ast_expr **next)
1823
4
{
1824
4
  isl_ctx *ctx;
1825
4
  isl_ast_build *build;
1826
4
  isl_ast_expr *ternary, *arg;
1827
4
  isl_set *set, *gist;
1828
4
1829
4
  set = data->p[pos].set;
1830
4
  data->p[pos].set = NULL;
1831
4
  ctx = isl_ast_build_get_ctx(data->build);
1832
4
  ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
1833
4
  gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));
1834
4
  arg = isl_ast_build_expr_from_set_internal(data->build, gist);
1835
4
  ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
1836
4
  build = isl_ast_build_copy(data->build);
1837
4
  build = isl_ast_build_restrict_generated(build, set);
1838
4
  arg = ast_expr_from_aff_list(data->p[pos].aff_list,
1839
4
          data->p[pos].state, build);
1840
4
  data->p[pos].aff_list = NULL;
1841
4
  isl_ast_build_free(build);
1842
4
  ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
1843
4
  data->p[pos].state = isl_state_none;
1844
4
  if (!ternary)
1845
0
    return NULL;
1846
4
1847
4
  *next = ternary;
1848
4
  return &ternary->u.op.args[2];
1849
4
}
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
static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,
1862
  int pos, isl_ast_expr **next)
1863
2.00k
{
1864
2.00k
  isl_ast_build *build;
1865
2.00k
1866
2.00k
  if (data->p[pos].state == isl_state_none)
1867
2.00k
    
isl_die0
(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1868
2.00k
      "cannot handle void expression", return isl_stat_error);
1869
2.00k
1870
2.00k
  build = isl_ast_build_copy(data->build);
1871
2.00k
  build = isl_ast_build_restrict_generated(build, data->p[pos].set);
1872
2.00k
  data->p[pos].set = NULL;
1873
2.00k
  *next = ast_expr_from_aff_list(data->p[pos].aff_list,
1874
2.00k
            data->p[pos].state, build);
1875
2.00k
  data->p[pos].aff_list = NULL;
1876
2.00k
  isl_ast_build_free(build);
1877
2.00k
  data->p[pos].state = isl_state_none;
1878
2.00k
  if (!*next)
1879
0
    return isl_stat_error;
1880
2.00k
1881
2.00k
  return isl_stat_ok;
1882
2.00k
}
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
static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)
1892
4
{
1893
4
  const struct isl_from_pw_aff_piece *piece1 = p1;
1894
4
  const struct isl_from_pw_aff_piece *piece2 = p2;
1895
4
  int n1, n2;
1896
4
1897
4
  n1 = isl_set_n_basic_set(piece1->set);
1898
4
  n2 = isl_set_n_basic_set(piece2->set);
1899
4
1900
4
  return n1 - n2;
1901
4
}
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
static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)
1917
2.00k
{
1918
2.00k
  int i;
1919
2.00k
  isl_ast_expr *res = NULL;
1920
2.00k
  isl_ast_expr **next = &res;
1921
2.00k
1922
2.00k
  if (data->p[data->n].state != isl_state_none)
1923
2.00k
    data->n++;
1924
2.00k
  if (data->n == 0)
1925
2.00k
    
isl_die0
(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1926
2.00k
      "cannot handle void expression", return NULL);
1927
2.00k
1928
4.00k
  
for (i = 0; 2.00k
i < data->n;
++i2.00k
) {
1929
2.00k
    data->p[i].set = isl_set_list_union(data->p[i].set_list);
1930
2.00k
    if (data->p[i].state != isl_state_single)
1931
7
      data->p[i].set = isl_set_coalesce(data->p[i].set);
1932
2.00k
    data->p[i].set_list = NULL;
1933
2.00k
  }
1934
2.00k
1935
2.00k
  if (isl_sort(data->p, data->n, sizeof(data->p[0]),
1936
2.00k
      &sort_pieces_cmp, NULL) < 0)
1937
0
    return isl_ast_expr_free(res);
1938
2.00k
1939
2.00k
  
for (i = 0; 2.00k
i + 1 < data->n;
++i4
) {
1940
4
    next = add_intermediate_piece(data, i, next);
1941
4
    if (!next)
1942
0
      return isl_ast_expr_free(res);
1943
4
  }
1944
2.00k
1945
2.00k
  if (add_last_piece(data, data->n - 1, next) < 0)
1946
0
    return isl_ast_expr_free(res);
1947
2.00k
1948
2.00k
  return res;
1949
2.00k
}
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
static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
1955
  __isl_keep isl_set *set)
1956
11
{
1957
11
  isl_bool subset;
1958
11
  isl_set *set_n;
1959
11
1960
11
  set_n = isl_set_list_get_set(data->p[data->n].set_list, 0);
1961
11
  subset = isl_set_is_subset(set_n, set);
1962
11
  isl_set_free(set_n);
1963
11
1964
11
  return subset;
1965
11
}
1966
1967
/* Is "aff" a rational expression, i.e., does it have a denominator
1968
 * different from one?
1969
 */
1970
static isl_bool aff_is_rational(__isl_keep isl_aff *aff)
1971
34
{
1972
34
  isl_bool rational;
1973
34
  isl_val *den;
1974
34
1975
34
  den = isl_aff_get_denominator_val(aff);
1976
34
  rational = isl_bool_not(isl_val_is_one(den));
1977
34
  isl_val_free(den);
1978
34
1979
34
  return rational;
1980
34
}
1981
1982
/* Does "list" consist of a single rational affine expression?
1983
 */
1984
static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)
1985
16
{
1986
16
  isl_bool rational;
1987
16
  isl_aff *aff;
1988
16
1989
16
  if (isl_aff_list_n_aff(list) != 1)
1990
0
    return isl_bool_false;
1991
16
  aff = isl_aff_list_get_aff(list, 0);
1992
16
  rational = aff_is_rational(aff);
1993
16
  isl_aff_free(aff);
1994
16
1995
16
  return rational;
1996
16
}
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
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
18
{
2022
18
  int i, n;
2023
18
  isl_bool is_rational;
2024
18
  isl_ctx *ctx;
2025
18
  isl_set *dom;
2026
18
2027
18
  is_rational = aff_is_rational(aff);
2028
18
  if (is_rational >= 0 && !is_rational)
2029
16
    is_rational = is_single_rational_aff(data->p[data->n].aff_list);
2030
18
  if (is_rational < 0 || is_rational)
2031
2
    return isl_bool_not(is_rational);
2032
16
2033
16
  ctx = isl_ast_build_get_ctx(data->build);
2034
16
  if (!isl_options_get_ast_build_detect_min_max(ctx))
2035
2
    return isl_bool_false;
2036
14
2037
14
  dom = isl_ast_build_get_domain(data->build);
2038
14
  set = isl_set_intersect(dom, isl_set_copy(set));
2039
14
2040
14
  n = isl_set_list_n_set(data->p[data->n].set_list);
2041
21
  for (i = 0; i < n ; 
++i7
) {
2042
14
    isl_aff *aff_i;
2043
14
    isl_set *valid;
2044
14
    isl_set *dom, *required;
2045
14
    isl_bool is_valid;
2046
14
2047
14
    aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2048
14
    valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i));
2049
14
    required = isl_set_list_get_set(data->p[data->n].set_list, i);
2050
14
    dom = isl_ast_build_get_domain(data->build);
2051
14
    required = isl_set_intersect(dom, required);
2052
14
    is_valid = isl_set_is_subset(required, valid);
2053
14
    isl_set_free(required);
2054
14
    isl_set_free(valid);
2055
14
    if (is_valid < 0 || !is_valid) {
2056
5
      isl_set_free(set);
2057
5
      return is_valid;
2058
5
    }
2059
9
2060
9
    aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2061
9
    valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff)));
2062
9
    is_valid = isl_set_is_subset(set, valid);
2063
9
    isl_set_free(valid);
2064
9
    if (is_valid < 0 || !is_valid) {
2065
2
      isl_set_free(set);
2066
2
      return is_valid;
2067
2
    }
2068
9
  }
2069
14
2070
14
  isl_set_free(set);
2071
7
  return isl_bool_true;
2072
14
}
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
static isl_bool extends_min(struct isl_from_pw_aff_data *data,
2082
  __isl_keep isl_set *set,  __isl_keep isl_aff *aff)
2083
11
{
2084
11
  return extends(data, set, aff, &isl_aff_ge_basic_set);
2085
11
}
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
static isl_bool extends_max(struct isl_from_pw_aff_data *data,
2095
  __isl_keep isl_set *set,  __isl_keep isl_aff *aff)
2096
7
{
2097
7
  return extends(data, set, aff, &isl_aff_le_basic_set);
2098
7
}
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
static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,
2119
  __isl_take isl_aff *aff, void *user)
2120
2.01k
{
2121
2.01k
  struct isl_from_pw_aff_data *data = user;
2122
2.01k
  isl_bool test;
2123
2.01k
  enum isl_from_pw_aff_state state;
2124
2.01k
2125
2.01k
  state = data->p[data->n].state;
2126
2.01k
  if (state == isl_state_single) {
2127
11
    isl_aff *aff0;
2128
11
    isl_set *eq;
2129
11
    isl_bool subset1, subset2 = isl_bool_false;
2130
11
    aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0);
2131
11
    eq = isl_aff_eq_set(isl_aff_copy(aff), aff0);
2132
11
    subset1 = isl_set_is_subset(set, eq);
2133
11
    if (subset1 >= 0 && !subset1)
2134
11
      subset2 = single_is_subset(data, eq);
2135
11
    isl_set_free(eq);
2136
11
    if (subset1 < 0 || subset2 < 0)
2137
0
      goto error;
2138
11
    if (subset1)
2139
0
      return extend_domain(data, set, aff, 0);
2140
11
    if (subset2)
2141
0
      return extend_domain(data, set, aff, 1);
2142
2.01k
  }
2143
2.01k
  if (state == isl_state_single || 
state == isl_state_min2.00k
) {
2144
11
    test = extends_min(data, set, aff);
2145
11
    if (test < 0)
2146
0
      goto error;
2147
11
    if (test)
2148
4
      return extend_min(data, set, aff);
2149
2.00k
  }
2150
2.00k
  if (state == isl_state_single || 
state == isl_state_max2.00k
) {
2151
7
    test = extends_max(data, set, aff);
2152
7
    if (test < 0)
2153
0
      goto error;
2154
7
    if (test)
2155
3
      return extend_max(data, set, aff);
2156
2.00k
  }
2157
2.00k
  if (state != isl_state_none)
2158
4
    data->n++;
2159
2.00k
  set_single(data, set, aff);
2160
2.00k
2161
2.00k
  return isl_stat_ok;
2162
0
error:
2163
0
  isl_set_free(set);
2164
0
  isl_aff_free(aff);
2165
0
  return isl_stat_error;
2166
2.00k
}
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
__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
2.00k
{
2176
2.00k
  struct isl_from_pw_aff_data data = { NULL };
2177
2.00k
  isl_ast_expr *res = NULL;
2178
2.00k
2179
2.00k
  pa = isl_ast_build_compute_gist_pw_aff(build, pa);
2180
2.00k
  pa = isl_pw_aff_coalesce(pa);
2181
2.00k
  if (!pa)
2182
0
    return NULL;
2183
2.00k
2184
2.00k
  if (isl_from_pw_aff_data_init(&data, build, pa) < 0)
2185
0
    goto error;
2186
2.00k
  set_none(&data);
2187
2.00k
2188
2.00k
  if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0)
2189
2.00k
    res = build_pieces(&data);
2190
2.00k
2191
2.00k
  isl_pw_aff_free(pa);
2192
2.00k
  isl_from_pw_aff_data_clear(&data);
2193
2.00k
  return res;
2194
0
error:
2195
0
  isl_pw_aff_free(pa);
2196
0
  isl_from_pw_aff_data_clear(&data);
2197
0
  return NULL;
2198
2.00k
}
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
__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
5
{
2208
5
  isl_ast_expr *expr;
2209
5
2210
5
  if (isl_ast_build_need_schedule_map(build)) {
2211
0
    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
0
  }
2215
5
  expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2216
5
  return expr;
2217
5
}
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
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
812
{
2227
812
  int i, n;
2228
812
2229
812
  n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
2230
4.23k
  for (i = 0; i < n; 
++i3.42k
) {
2231
3.42k
    isl_id *id;
2232
3.42k
2233
3.42k
    id = isl_ast_build_get_iterator_id(build, i);
2234
3.42k
    mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
2235
3.42k
  }
2236
812
2237
812
  return mpa;
2238
812
}
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
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
812
{
2249
812
  int i, n;
2250
812
  isl_ctx *ctx;
2251
812
  isl_ast_expr *expr;
2252
812
2253
812
  ctx = isl_ast_build_get_ctx(build);
2254
812
2255
812
  n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
2256
812
  expr = isl_ast_expr_alloc_op(ctx, type, 1 + n);
2257
812
  expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
2258
2.37k
  for (i = 0; i < n; 
++i1.56k
) {
2259
1.56k
    isl_pw_aff *pa;
2260
1.56k
    isl_ast_expr *arg;
2261
1.56k
2262
1.56k
    pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
2263
1.56k
    arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2264
1.56k
    expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
2265
1.56k
  }
2266
812
2267
812
  isl_multi_pw_aff_free(mpa);
2268
812
  return expr;
2269
812
}
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
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
0
{
2286
0
  isl_id *id;
2287
0
  isl_multi_pw_aff *domain;
2288
0
  isl_ast_expr *domain_expr, *expr;
2289
0
  enum isl_ast_op_type type = isl_ast_op_access;
2290
0
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
0
                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
0
      "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
0
error:
2304
0
  isl_multi_pw_aff_free(mpa);
2305
0
  return NULL;
2306
0
}
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
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
812
{
2322
812
  isl_ctx *ctx;
2323
812
  isl_id *id;
2324
812
  isl_ast_expr *expr;
2325
812
2326
812
  if (!mpa)
2327
0
    goto error;
2328
812
2329
812
  if (type == isl_ast_op_access &&
2330
812
      
isl_multi_pw_aff_range_is_wrapping(mpa)222
)
2331
0
    return isl_ast_build_from_multi_pw_aff_member(build, mpa);
2332
812
2333
812
  mpa = set_iterator_names(build, mpa);
2334
812
  if (!build || !mpa)
2335
0
    goto error;
2336
812
2337
812
  ctx = isl_ast_build_get_ctx(build);
2338
812
2339
812
  if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
2340
812
    id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
2341
0
  else
2342
0
    id = isl_id_alloc(ctx, "", NULL);
2343
812
2344
812
  expr = isl_ast_expr_from_id(id);
2345
812
  return isl_ast_build_with_arguments(build, type, expr, mpa);
2346
0
error:
2347
0
  isl_multi_pw_aff_free(mpa);
2348
0
  return NULL;
2349
812
}
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
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
590
{
2362
590
  isl_multi_pw_aff *mpa;
2363
590
2364
590
  mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2365
590
  return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2366
590
}
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
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
222
{
2379
222
  int is_domain;
2380
222
  isl_ast_expr *expr;
2381
222
  isl_space *space_build, *space_mpa;
2382
222
2383
222
  space_build = isl_ast_build_get_space(build, 0);
2384
222
  space_mpa = isl_multi_pw_aff_get_space(mpa);
2385
222
  is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,
2386
222
          space_mpa, isl_dim_in);
2387
222
  isl_space_free(space_build);
2388
222
  isl_space_free(space_mpa);
2389
222
  if (is_domain < 0)
2390
0
    goto error;
2391
222
  if (!is_domain)
2392
222
    
isl_die0
(isl_ast_build_get_ctx(build), isl_error_invalid,
2393
222
      "spaces don't match", goto error);
2394
222
2395
222
  if (isl_ast_build_need_schedule_map(build)) {
2396
25
    isl_multi_aff *ma;
2397
25
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
2398
25
    mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
2399
25
  }
2400
222
2401
222
  expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2402
222
  return expr;
2403
0
error:
2404
0
  isl_multi_pw_aff_free(mpa);
2405
0
  return NULL;
2406
222
}
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
__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
0
{
2417
0
  return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_call, mpa);
2418
0
}
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
__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
0
{
2429
0
  return isl_ast_build_from_multi_pw_aff(build, isl_ast_op_access, mpa);
2430
0
}
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
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
222
{
2443
222
  isl_multi_pw_aff *mpa;
2444
222
2445
222
  mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2446
222
  return isl_ast_build_from_multi_pw_aff(build, type, mpa);
2447
222
}
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
__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
0
{
2458
0
  return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_call, pma);
2459
0
}
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
__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
222
{
2470
222
  return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma);
2471
222
}
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
__isl_give isl_ast_node *isl_ast_build_call_from_executed(
2480
  __isl_keep isl_ast_build *build, __isl_take isl_map *executed)
2481
590
{
2482
590
  isl_pw_multi_aff *iteration;
2483
590
  isl_ast_expr *expr;
2484
590
2485
590
  iteration = isl_pw_multi_aff_from_map(executed);
2486
590
  iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
2487
590
  iteration = isl_pw_multi_aff_intersect_domain(iteration,
2488
590
          isl_ast_build_get_domain(build));
2489
590
  expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call,
2490
590
              iteration);
2491
590
  return isl_ast_node_alloc_user(expr);
2492
590
}