Coverage Report

Created: 2018-08-14 02:14

/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
63
{
33
63
  aff = isl_aff_neg(aff);
34
63
  aff = isl_aff_add_constant_val(aff, d);
35
63
  aff = isl_aff_add_constant_si(aff, -1);
36
63
37
63
  return aff;
38
63
}
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
16
{
78
16
  isl_aff *shifted;
79
16
  isl_val *shift;
80
16
  int is_zero;
81
16
  int non_neg;
82
16
83
16
  if (isl_val_sgn(data->cst) != isl_val_sgn(data->v))
84
12
    return 0;
85
4
86
4
  shift = isl_val_div(isl_val_copy(data->cst), isl_val_copy(data->v));
87
4
  shift = isl_val_floor(shift);
88
4
  is_zero = isl_val_is_zero(shift);
89
4
  if (is_zero < 0 || is_zero) {
90
4
    isl_val_free(shift);
91
4
    return is_zero < 0 ? 
-10
: 0;
92
4
  }
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
28
{
187
28
  isl_ctx *ctx = isl_local_space_get_ctx(ls);
188
28
  isl_aff *aff;
189
28
  isl_ast_expr *num, *den;
190
28
  isl_val *d;
191
28
  enum isl_ast_op_type type;
192
28
193
28
  aff = isl_local_space_get_div(ls, pos);
194
28
  d = isl_aff_get_denominator_val(aff);
195
28
  aff = isl_aff_scale_val(aff, isl_val_copy(d));
196
28
  den = isl_ast_expr_from_val(isl_val_copy(d));
197
28
198
28
  type = isl_ast_op_fdiv_q;
199
28
  if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
200
28
    int non_neg = isl_ast_build_aff_is_nonneg(data->build, aff);
201
28
    if (non_neg >= 0 && !non_neg) {
202
16
      isl_aff *opp = oppose_div_arg(isl_aff_copy(aff),
203
16
              isl_val_copy(d));
204
16
      non_neg = isl_ast_build_aff_is_nonneg(data->build, opp);
205
16
      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
16
        isl_aff_free(opp);
211
16
    }
212
28
    if (non_neg >= 0 && !non_neg) {
213
16
      non_neg = is_non_neg_after_stealing(aff, d, data);
214
16
      if (non_neg >= 0 && non_neg)
215
0
        aff = steal_from_cst(aff, d, data);
216
16
    }
217
28
    if (non_neg < 0)
218
0
      aff = isl_aff_free(aff);
219
28
    else if (non_neg)
220
12
      type = isl_ast_op_pdiv_q;
221
28
  }
222
28
223
28
  isl_val_free(d);
224
28
  num = isl_ast_expr_from_aff(aff, data->build);
225
28
  return isl_ast_expr_alloc_binary(type, num, den);
226
28
}
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
8.76k
{
240
8.76k
  isl_ctx *ctx = isl_local_space_get_ctx(ls);
241
8.76k
  isl_id *id;
242
8.76k
243
8.76k
  if (type == isl_dim_div)
244
28
    return var_div(data, ls, pos);
245
8.73k
246
8.73k
  if (type == isl_dim_set) {
247
7.62k
    id = isl_ast_build_get_iterator_id(data->build, pos);
248
7.62k
    return isl_ast_expr_from_id(id);
249
7.62k
  }
250
1.11k
251
1.11k
  if (!isl_local_space_has_dim_id(ls, type, pos))
252
1.11k
    
isl_die0
(ctx, isl_error_internal, "unnamed dimension",
253
1.11k
      return NULL);
254
1.11k
  id = isl_local_space_get_dim_id(ls, type, pos);
255
1.11k
  return isl_ast_expr_from_id(id);
256
1.11k
}
257
258
/* Does "expr" represent the zero integer?
259
 */
260
static int ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
261
27.4k
{
262
27.4k
  if (!expr)
263
0
    return -1;
264
27.4k
  if (expr->type != isl_ast_expr_int)
265
8.52k
    return 0;
266
18.9k
  return isl_val_is_zero(expr->u.v);
267
18.9k
}
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
12.8k
{
275
12.8k
  if (!expr1 || !expr2)
276
0
    goto error;
277
12.8k
278
12.8k
  if (ast_expr_is_zero(expr1)) {
279
7.82k
    isl_ast_expr_free(expr1);
280
7.82k
    return expr2;
281
7.82k
  }
282
5.05k
283
5.05k
  if (ast_expr_is_zero(expr2)) {
284
0
    isl_ast_expr_free(expr2);
285
0
    return expr1;
286
0
  }
287
5.05k
288
5.05k
  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
5.05k
}
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
8.22k
{
309
8.22k
  if (!expr1 || !expr2)
310
0
    goto error;
311
8.22k
312
8.22k
  if (ast_expr_is_zero(expr2)) {
313
8.06k
    isl_ast_expr_free(expr2);
314
8.06k
    return expr1;
315
8.06k
  }
316
155
317
155
  if (ast_expr_is_zero(expr1)) {
318
43
    isl_ast_expr_free(expr1);
319
43
    return isl_ast_expr_neg(expr2);
320
43
  }
321
112
322
112
  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
112
}
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
76
{
340
76
  isl_ast_expr *expr;
341
76
  isl_ast_expr *c;
342
76
343
76
  if (!aff)
344
0
    return NULL;
345
76
346
76
  expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build);
347
76
348
76
  c = isl_ast_expr_from_val(isl_val_copy(d));
349
76
  expr = isl_ast_expr_alloc_binary(isl_ast_op_pdiv_r, expr, c);
350
76
351
76
  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
76
356
76
  return expr;
357
76
}
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
8.76k
{
373
8.76k
  isl_ast_expr *c;
374
8.76k
375
8.76k
  if (!expr || !v)
376
0
    goto error;
377
8.76k
  if (isl_val_is_one(v)) {
378
3.61k
    isl_val_free(v);
379
3.61k
    return expr;
380
3.61k
  }
381
5.14k
382
5.14k
  if (isl_val_is_negone(v)) {
383
34
    isl_val_free(v);
384
34
    expr = isl_ast_expr_neg(expr);
385
5.11k
  } else {
386
5.11k
    c = isl_ast_expr_from_val(v);
387
5.11k
    expr = isl_ast_expr_mul(c, expr);
388
5.11k
  }
389
5.14k
390
5.14k
  return expr;
391
0
error:
392
0
  isl_val_free(v);
393
0
  isl_ast_expr_free(expr);
394
0
  return NULL;
395
5.14k
}
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
8.76k
{
425
8.76k
  isl_ast_expr *term;
426
8.76k
427
8.76k
  if (!expr)
428
0
    return NULL;
429
8.76k
430
8.76k
  data->v = v;
431
8.76k
  term = var(data, ls, type, pos);
432
8.76k
  v = data->v;
433
8.76k
434
8.76k
  if (isl_val_is_neg(v) && 
!ast_expr_is_zero(expr)87
) {
435
19
    v = isl_val_neg(v);
436
19
    term = scale(term, v);
437
19
    return ast_expr_sub(expr, term);
438
8.74k
  } else {
439
8.74k
    term = scale(term, v);
440
8.74k
    return ast_expr_add(expr, term);
441
8.74k
  }
442
8.76k
}
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
8.64k
{
449
8.64k
  isl_ast_expr *expr_int;
450
8.64k
451
8.64k
  if (!expr || !v)
452
0
    goto error;
453
8.64k
454
8.64k
  if (isl_val_is_zero(v)) {
455
4.49k
    isl_val_free(v);
456
4.49k
    return expr;
457
4.49k
  }
458
4.14k
459
4.14k
  if (isl_val_is_neg(v) && 
!ast_expr_is_zero(expr)195
) {
460
93
    v = isl_val_neg(v);
461
93
    expr_int = isl_ast_expr_from_val(v);
462
93
    return ast_expr_sub(expr, expr_int);
463
4.05k
  } else {
464
4.05k
    expr_int = isl_ast_expr_from_val(v);
465
4.05k
    return ast_expr_add(expr, expr_int);
466
4.05k
  }
467
0
error:
468
0
  isl_ast_expr_free(expr);
469
0
  isl_val_free(v);
470
0
  return NULL;
471
4.14k
}
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
76
{
530
76
  isl_ast_expr *expr;
531
76
  int s;
532
76
533
76
  data->v = isl_val_div(data->v, isl_val_copy(data->d));
534
76
  s = isl_val_sgn(data->v);
535
76
  data->v = isl_val_abs(data->v);
536
76
  expr = isl_ast_expr_mod(data->v, arg, data->d, data->build);
537
76
  isl_aff_free(arg);
538
76
  if (s > 0)
539
43
    data->neg = ast_expr_add(data->neg, expr);
540
33
  else
541
33
    data->pos = ast_expr_add(data->pos, expr);
542
76
  data->aff = isl_aff_set_coefficient_si(data->aff,
543
76
            isl_dim_div, data->i, 0);
544
76
  if (s < 0)
545
33
    data->v = isl_val_neg(data->v);
546
76
  term = isl_aff_scale_val(term, isl_val_copy(data->v));
547
76
548
76
  if (!data->add)
549
76
    data->add = term;
550
0
  else
551
0
    data->add = isl_aff_add(data->add, term);
552
76
  if (!data->add)
553
0
    return -1;
554
76
555
76
  return 0;
556
76
}
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
40
{
578
40
  return extract_term_and_mod(data, isl_aff_copy(data->div),
579
40
      isl_aff_copy(data->div));
580
40
}
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
44
{
602
44
  int mod;
603
44
604
44
  mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
605
44
  if (mod < 0)
606
0
    goto error;
607
44
  if (mod)
608
24
    return extract_mod(data);
609
20
610
20
  data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
611
20
  mod = isl_ast_build_aff_is_nonneg(data->build, data->div);
612
20
  if (mod < 0)
613
0
    goto error;
614
20
  if (mod) {
615
16
    data->v = isl_val_neg(data->v);
616
16
    return extract_mod(data);
617
16
  }
618
4
619
4
  return 0;
620
0
error:
621
0
  data->aff = isl_aff_free(data->aff);
622
0
  return -1;
623
4
}
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
41
{
639
41
  isl_val *v1, *v2;
640
41
  int simpler;
641
41
642
41
  if (!data->nonneg)
643
36
    return 1;
644
5
645
5
  v1 = isl_val_abs(isl_constraint_get_constant_val(c));
646
5
  v2 = isl_val_abs(isl_aff_get_constant_val(data->nonneg));
647
5
  simpler = isl_val_lt(v1, v2);
648
5
  isl_val_free(v1);
649
5
  isl_val_free(v2);
650
5
651
5
  return simpler;
652
5
}
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
994
{
678
994
  struct isl_extract_mod_data *data = user;
679
994
  enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
680
994
  enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
681
994
  int i, t;
682
994
  int n[2];
683
994
  int parallel = 1, opposite = 1;
684
994
685
2.98k
  for (t = 0; t < 2; 
++t1.98k
) {
686
1.98k
    n[t] = isl_constraint_dim(c, c_type[t]);
687
13.2k
    for (i = 0; i < n[t]; 
++i11.2k
) {
688
11.2k
      int a, b;
689
11.2k
690
11.2k
      a = isl_constraint_involves_dims(c, c_type[t], i, 1);
691
11.2k
      b = isl_aff_involves_dims(data->div, a_type[t], i, 1);
692
11.2k
      if (a != b)
693
1.92k
        parallel = opposite = 0;
694
11.2k
    }
695
1.98k
  }
696
994
697
994
  if (parallel || 
opposite885
) {
698
109
    isl_val *v;
699
109
700
109
    v = isl_val_abs(isl_constraint_get_constant_val(c));
701
109
    if (isl_val_cmp_si(v, 1 << 15) > 0)
702
68
      parallel = opposite = 0;
703
109
    isl_val_free(v);
704
109
  }
705
994
706
2.98k
  for (t = 0; t < 2; 
++t1.98k
) {
707
2.32k
    for (i = 0; i < n[t]; 
++i336
) {
708
2.21k
      isl_val *v1, *v2;
709
2.21k
710
2.21k
      if (!parallel && 
!opposite2.13k
)
711
1.87k
        break;
712
336
      v1 = isl_constraint_get_coefficient_val(c,
713
336
                c_type[t], i);
714
336
      v2 = isl_aff_get_coefficient_val(data->div,
715
336
                a_type[t], i);
716
336
      if (parallel) {
717
83
        v1 = isl_val_sub(v1, isl_val_copy(v2));
718
83
        parallel = isl_val_is_divisible_by(v1, data->d);
719
83
        v1 = isl_val_add(v1, isl_val_copy(v2));
720
83
      }
721
336
      if (opposite) {
722
335
        v1 = isl_val_add(v1, isl_val_copy(v2));
723
335
        opposite = isl_val_is_divisible_by(v1, data->d);
724
335
      }
725
336
      isl_val_free(v1);
726
336
      isl_val_free(v2);
727
336
    }
728
1.98k
  }
729
994
730
994
  if ((parallel || 
opposite985
) &&
mod_constraint_is_simpler(data, c)41
) {
731
36
    isl_aff_free(data->nonneg);
732
36
    data->nonneg = isl_constraint_get_aff(c);
733
36
    data->sign = parallel ? 
19
:
-127
;
734
36
  }
735
994
736
994
  isl_constraint_free(c);
737
994
738
994
  if (data->sign != 0 && 
data->nonneg == NULL374
)
739
994
    
return isl_stat_error0
;
740
994
741
994
  return isl_stat_ok;
742
994
}
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
80
{
825
80
  isl_basic_set *hull;
826
80
  isl_val *v1, *v2;
827
80
  int r, n;
828
80
829
80
  if (!data->build)
830
0
    goto error;
831
80
832
80
  n = isl_aff_dim(data->div, isl_dim_div);
833
80
834
80
  if (isl_aff_involves_dims(data->div, isl_dim_div, 0, n))
835
0
    return extract_nonneg_mod(data);
836
80
837
80
  hull = isl_set_simple_hull(isl_set_copy(data->build->domain));
838
80
  hull = isl_basic_set_remove_divs(hull);
839
80
  data->sign = 0;
840
80
  data->nonneg = NULL;
841
80
  r = isl_basic_set_foreach_constraint(hull, &check_parallel_or_opposite,
842
80
          data);
843
80
  isl_basic_set_free(hull);
844
80
845
80
  if (!data->sign || 
r < 036
) {
846
44
    isl_aff_free(data->nonneg);
847
44
    if (r < 0)
848
0
      goto error;
849
44
    return extract_nonneg_mod(data);
850
44
  }
851
36
852
36
  v1 = isl_aff_get_constant_val(data->div);
853
36
  v2 = isl_aff_get_constant_val(data->nonneg);
854
36
  if (data->sign < 0) {
855
27
    v1 = isl_val_neg(v1);
856
27
    v1 = isl_val_add(v1, isl_val_copy(data->d));
857
27
    v1 = isl_val_sub_ui(v1, 1);
858
27
  }
859
36
  v1 = isl_val_sub(v1, isl_val_copy(v2));
860
36
  v1 = isl_val_mod(v1, isl_val_copy(data->d));
861
36
  v1 = isl_val_add(v1, v2);
862
36
  v2 = isl_val_div(isl_val_copy(v1), isl_val_copy(data->d));
863
36
  v2 = isl_val_ceil(v2);
864
36
  if (isl_val_is_neg(v2)) {
865
1
    v2 = isl_val_mul(v2, isl_val_copy(data->d));
866
1
    v1 = isl_val_sub(v1, isl_val_copy(v2));
867
1
  }
868
36
  data->nonneg = isl_aff_set_constant_val(data->nonneg, v1);
869
36
  isl_val_free(v2);
870
36
871
36
  if (data->sign < 0) {
872
27
    data->div = oppose_div_arg(data->div, isl_val_copy(data->d));
873
27
    data->v = isl_val_neg(data->v);
874
27
  }
875
36
876
36
  return extract_term_and_mod(data,
877
36
            isl_aff_copy(data->div), data->nonneg);
878
0
error:
879
0
  data->aff = isl_aff_free(data->aff);
880
0
  return -1;
881
36
}
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
80
{
916
80
  data->div = isl_aff_get_div(data->aff, data->i);
917
80
  data->d = isl_aff_get_denominator_val(data->div);
918
80
  if (isl_val_is_divisible_by(data->v, data->d)) {
919
80
    data->div = isl_aff_scale_val(data->div, isl_val_copy(data->d));
920
80
    if (try_extract_mod(data) < 0)
921
0
      data->aff = isl_aff_free(data->aff);
922
80
  }
923
80
  isl_aff_free(data->div);
924
80
  isl_val_free(data->d);
925
80
  return 0;
926
80
}
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
8.64k
{
955
8.64k
  struct isl_extract_mod_data data = { build, aff, *pos, *neg };
956
8.64k
  isl_ctx *ctx;
957
8.64k
  int n;
958
8.64k
959
8.64k
  if (!aff)
960
0
    return NULL;
961
8.64k
962
8.64k
  ctx = isl_aff_get_ctx(aff);
963
8.64k
  if (!isl_options_get_ast_build_prefer_pdiv(ctx))
964
0
    return aff;
965
8.64k
966
8.64k
  n = isl_aff_dim(data.aff, isl_dim_div);
967
8.89k
  for (data.i = 0; data.i < n; 
++data.i253
) {
968
253
    data.v = isl_aff_get_coefficient_val(data.aff,
969
253
              isl_dim_div, data.i);
970
253
    if (!data.v)
971
0
      return isl_aff_free(aff);
972
253
    if (isl_val_is_zero(data.v) ||
973
253
        
isl_val_is_one(data.v)104
||
isl_val_is_negone(data.v)80
) {
974
173
      isl_val_free(data.v);
975
173
      continue;
976
173
    }
977
80
    if (extract_modulo(&data) < 0)
978
0
      data.aff = isl_aff_free(data.aff);
979
80
    isl_val_free(data.v);
980
80
    if (!data.aff)
981
0
      break;
982
80
  }
983
8.64k
984
8.64k
  if (data.add)
985
76
    data.aff = isl_aff_add(data.aff, data.add);
986
8.64k
987
8.64k
  *pos = data.pos;
988
8.64k
  *neg = data.neg;
989
8.64k
  return data.aff;
990
8.64k
}
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
8.11k
{
1003
8.11k
  int i, j, n;
1004
8.11k
  isl_aff *rat = NULL;
1005
8.11k
  isl_local_space *ls = NULL;
1006
8.11k
  isl_ast_expr *rat_expr;
1007
8.11k
  isl_val *v, *d;
1008
8.11k
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1009
8.11k
  enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1010
8.11k
1011
8.11k
  if (!aff)
1012
0
    return NULL;
1013
8.11k
  d = isl_aff_get_denominator_val(aff);
1014
8.11k
  if (!d)
1015
0
    goto error;
1016
8.11k
  if (isl_val_is_one(d)) {
1017
8.10k
    isl_val_free(d);
1018
8.10k
    return aff;
1019
8.10k
  }
1020
7
1021
7
  aff = isl_aff_scale_val(aff, isl_val_copy(d));
1022
7
1023
7
  ls = isl_aff_get_domain_local_space(aff);
1024
7
  rat = isl_aff_zero_on_domain(isl_local_space_copy(ls));
1025
7
1026
28
  for (i = 0; i < 3; 
++i21
) {
1027
21
    n = isl_aff_dim(aff, t[i]);
1028
42
    for (j = 0; j < n; 
++j21
) {
1029
21
      isl_aff *rat_j;
1030
21
1031
21
      v = isl_aff_get_coefficient_val(aff, t[i], j);
1032
21
      if (!v)
1033
0
        goto error;
1034
21
      if (isl_val_is_divisible_by(v, d)) {
1035
12
        isl_val_free(v);
1036
12
        continue;
1037
12
      }
1038
9
      rat_j = isl_aff_var_on_domain(isl_local_space_copy(ls),
1039
9
              l[i], j);
1040
9
      rat_j = isl_aff_scale_val(rat_j, v);
1041
9
      rat = isl_aff_add(rat, rat_j);
1042
9
    }
1043
21
  }
1044
7
1045
7
  v = isl_aff_get_constant_val(aff);
1046
7
  if (isl_val_is_divisible_by(v, d)) {
1047
7
    isl_val_free(v);
1048
7
  } 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
7
1055
7
  isl_local_space_free(ls);
1056
7
1057
7
  aff = isl_aff_sub(aff, isl_aff_copy(rat));
1058
7
  aff = isl_aff_scale_down_val(aff, isl_val_copy(d));
1059
7
1060
7
  rat_expr = isl_ast_expr_from_aff(rat, build);
1061
7
  rat_expr = isl_ast_expr_div(rat_expr, isl_ast_expr_from_val(d));
1062
7
  *expr = ast_expr_add(*expr, rat_expr);
1063
7
1064
7
  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
7
}
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
8.11k
{
1084
8.11k
  int i, j;
1085
8.11k
  int n;
1086
8.11k
  isl_val *v;
1087
8.11k
  isl_ctx *ctx = isl_aff_get_ctx(aff);
1088
8.11k
  isl_ast_expr *expr, *expr_neg;
1089
8.11k
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1090
8.11k
  enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1091
8.11k
  isl_local_space *ls;
1092
8.11k
  struct isl_ast_add_term_data data;
1093
8.11k
1094
8.11k
  if (!aff)
1095
0
    return NULL;
1096
8.11k
1097
8.11k
  expr = isl_ast_expr_alloc_int_si(ctx, 0);
1098
8.11k
  expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1099
8.11k
1100
8.11k
  aff = extract_rational(aff, &expr, build);
1101
8.11k
1102
8.11k
  aff = extract_modulos(aff, &expr, &expr_neg, build);
1103
8.11k
  expr = ast_expr_sub(expr, expr_neg);
1104
8.11k
1105
8.11k
  ls = isl_aff_get_domain_local_space(aff);
1106
8.11k
1107
8.11k
  data.build = build;
1108
8.11k
  data.cst = isl_aff_get_constant_val(aff);
1109
32.4k
  for (i = 0; i < 3; 
++i24.3k
) {
1110
24.3k
    n = isl_aff_dim(aff, t[i]);
1111
74.7k
    for (j = 0; j < n; 
++j50.4k
) {
1112
50.4k
      v = isl_aff_get_coefficient_val(aff, t[i], j);
1113
50.4k
      if (!v)
1114
0
        expr = isl_ast_expr_free(expr);
1115
50.4k
      if (isl_val_is_zero(v)) {
1116
42.3k
        isl_val_free(v);
1117
42.3k
        continue;
1118
42.3k
      }
1119
8.09k
      expr = isl_ast_expr_add_term(expr,
1120
8.09k
              ls, l[i], j, v, &data);
1121
8.09k
    }
1122
24.3k
  }
1123
8.11k
1124
8.11k
  expr = isl_ast_expr_add_int(expr, data.cst);
1125
8.11k
1126
8.11k
  isl_local_space_free(ls);
1127
8.11k
  isl_aff_free(aff);
1128
8.11k
  return expr;
1129
8.11k
}
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
1.05k
{
1138
1.05k
  int i, j;
1139
1.05k
  isl_val *v;
1140
1.05k
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1141
1.05k
  enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1142
1.05k
  isl_local_space *ls;
1143
1.05k
1144
1.05k
  ls = isl_aff_get_domain_local_space(aff);
1145
1.05k
1146
4.22k
  for (i = 0; i < 3; 
++i3.16k
) {
1147
3.16k
    int n = isl_aff_dim(aff, t[i]);
1148
6.49k
    for (j = 0; j < n; 
++j3.33k
) {
1149
3.33k
      v = isl_aff_get_coefficient_val(aff, t[i], j);
1150
3.33k
      if (sign * isl_val_sgn(v) <= 0) {
1151
2.66k
        isl_val_free(v);
1152
2.66k
        continue;
1153
2.66k
      }
1154
663
      v = isl_val_abs(v);
1155
663
      expr = isl_ast_expr_add_term(expr,
1156
663
            ls, l[i], j, v, data);
1157
663
    }
1158
3.16k
  }
1159
1.05k
1160
1.05k
  isl_local_space_free(ls);
1161
1.05k
1162
1.05k
  return expr;
1163
1.05k
}
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
528
{
1177
528
  if (ast_expr_is_zero(pos))
1178
163
    return 1;
1179
365
  if (ast_expr_is_zero(neg))
1180
281
    return 0;
1181
84
  return isl_val_is_pos(v);
1182
84
}
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
17
{
1212
17
  isl_aff *div;
1213
17
  isl_val *c, *d;
1214
17
  int eq;
1215
17
1216
17
  div = isl_aff_get_div(aff, pos);
1217
17
  c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1218
17
  d = isl_aff_get_denominator_val(div);
1219
17
  eq = isl_val_abs_eq(c, d);
1220
17
  if (eq >= 0 && eq) {
1221
17
    aff = isl_aff_copy(aff);
1222
17
    aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1223
17
    div = isl_aff_scale_val(div, d);
1224
17
    if (isl_val_is_pos(c))
1225
17
      div = isl_aff_neg(div);
1226
17
    eq = isl_aff_plain_is_equal(div, aff);
1227
17
    isl_aff_free(aff);
1228
17
  } else
1229
0
    isl_val_free(d);
1230
17
  isl_val_free(c);
1231
17
  isl_aff_free(div);
1232
17
1233
17
  return eq;
1234
17
}
1235
1236
/* Are all coefficients of "aff" (zero or) negative?
1237
 */
1238
static int all_negative_coefficients(__isl_keep isl_aff *aff)
1239
17
{
1240
17
  int i, n;
1241
17
1242
17
  if (!aff)
1243
0
    return 0;
1244
17
1245
17
  n = isl_aff_dim(aff, isl_dim_param);
1246
38
  for (i = 0; i < n; 
++i21
)
1247
23
    if (isl_aff_coefficient_sgn(aff, isl_dim_param, i) > 0)
1248
2
      return 0;
1249
17
1250
17
  n = isl_aff_dim(aff, isl_dim_in);
1251
78
  for (i = 0; i < n; 
++i63
)
1252
63
    if (isl_aff_coefficient_sgn(aff, isl_dim_in, i) > 0)
1253
0
      return 0;
1254
15
1255
15
  return 1;
1256
15
}
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
17
{
1280
17
  isl_ctx *ctx;
1281
17
  isl_val *c;
1282
17
  isl_ast_expr *expr, *cst;
1283
17
1284
17
  if (!aff)
1285
0
    return NULL;
1286
17
1287
17
  ctx = isl_aff_get_ctx(aff);
1288
17
1289
17
  c = isl_aff_get_coefficient_val(aff, isl_dim_div, pos);
1290
17
  aff = isl_aff_set_coefficient_si(aff, isl_dim_div, pos, 0);
1291
17
1292
17
  if (all_negative_coefficients(aff))
1293
15
    aff = isl_aff_neg(aff);
1294
17
1295
17
  cst = isl_ast_expr_from_val(isl_val_abs(c));
1296
17
  expr = isl_ast_expr_from_aff(aff, build);
1297
17
1298
17
  expr = isl_ast_expr_alloc_binary(isl_ast_op_zdiv_r, expr, cst);
1299
17
  cst = isl_ast_expr_alloc_int_si(ctx, 0);
1300
17
  expr = isl_ast_expr_alloc_binary(isl_ast_op_eq, expr, cst);
1301
17
1302
17
  return expr;
1303
17
}
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
545
{
1344
545
  int i, n;
1345
545
  isl_ctx *ctx;
1346
545
  isl_ast_expr *expr_pos;
1347
545
  isl_ast_expr *expr_neg;
1348
545
  isl_ast_expr *expr;
1349
545
  isl_aff *aff;
1350
545
  int eq;
1351
545
  enum isl_ast_op_type type;
1352
545
  struct isl_ast_add_term_data data;
1353
545
1354
545
  if (!constraint)
1355
0
    return NULL;
1356
545
1357
545
  aff = isl_constraint_get_aff(constraint);
1358
545
  eq = isl_constraint_is_equality(constraint);
1359
545
  isl_constraint_free(constraint);
1360
545
1361
545
  n = isl_aff_dim(aff, isl_dim_div);
1362
545
  if (eq && 
n > 070
)
1363
17
    for (i = 0; i < n; 
++i0
) {
1364
17
      int is_stride;
1365
17
      is_stride = is_stride_constraint(aff, i);
1366
17
      if (is_stride < 0)
1367
0
        goto error;
1368
17
      if (is_stride)
1369
17
        return extract_stride_constraint(aff, i, build);
1370
17
    }
1371
545
1372
545
  ctx = isl_aff_get_ctx(aff);
1373
528
  expr_pos = isl_ast_expr_alloc_int_si(ctx, 0);
1374
528
  expr_neg = isl_ast_expr_alloc_int_si(ctx, 0);
1375
528
1376
528
  aff = extract_modulos(aff, &expr_pos, &expr_neg, build);
1377
528
1378
528
  data.build = build;
1379
528
  data.cst = isl_aff_get_constant_val(aff);
1380
528
  expr_pos = add_signed_terms(expr_pos, aff, 1, &data);
1381
528
  data.cst = isl_val_neg(data.cst);
1382
528
  expr_neg = add_signed_terms(expr_neg, aff, -1, &data);
1383
528
  data.cst = isl_val_neg(data.cst);
1384
528
1385
528
  if (constant_is_considered_positive(data.cst, expr_pos, expr_neg)) {
1386
171
    expr_pos = isl_ast_expr_add_int(expr_pos, data.cst);
1387
357
  } else {
1388
357
    data.cst = isl_val_neg(data.cst);
1389
357
    expr_neg = isl_ast_expr_add_int(expr_neg, data.cst);
1390
357
  }
1391
528
1392
528
  if (isl_ast_expr_get_type(expr_pos) == isl_ast_expr_int &&
1393
528
      
isl_ast_expr_get_type(expr_neg) != isl_ast_expr_int163
) {
1394
161
    type = eq ? 
isl_ast_op_eq0
: isl_ast_op_le;
1395
161
    expr = isl_ast_expr_alloc_binary(type, expr_neg, expr_pos);
1396
367
  } else {
1397
367
    type = eq ? 
isl_ast_op_eq53
:
isl_ast_op_ge314
;
1398
367
    expr = isl_ast_expr_alloc_binary(type, expr_pos, expr_neg);
1399
367
  }
1400
528
1401
528
  isl_aff_free(aff);
1402
528
  return expr;
1403
0
error:
1404
0
  isl_aff_free(aff);
1405
0
  return NULL;
1406
545
}
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
100
{
1416
100
  int cmp;
1417
100
1418
100
  cmp = isl_constraint_cmp_last_non_zero(a, b);
1419
100
  if (cmp != 0)
1420
81
    return cmp;
1421
19
  return isl_constraint_plain_cmp(a, b);
1422
19
}
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
889
{
1447
889
  int i, n;
1448
889
  isl_constraint *c;
1449
889
  isl_constraint_list *list;
1450
889
  isl_ast_expr *res;
1451
889
  isl_set *set;
1452
889
1453
889
  list = isl_basic_set_get_constraint_list(bset);
1454
889
  isl_basic_set_free(bset);
1455
889
  list = isl_constraint_list_sort(list, &cmp_constraint, NULL);
1456
889
  if (!list)
1457
0
    return NULL;
1458
889
  n = isl_constraint_list_n_constraint(list);
1459
889
  if (n == 0) {
1460
428
    isl_ctx *ctx = isl_constraint_list_get_ctx(list);
1461
428
    isl_constraint_list_free(list);
1462
428
    return isl_ast_expr_alloc_int_si(ctx, 1);
1463
428
  }
1464
461
1465
461
  build = isl_ast_build_copy(build);
1466
461
1467
461
  c = isl_constraint_list_get_constraint(list, 0);
1468
461
  bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1469
461
  set = isl_set_from_basic_set(bset);
1470
461
  res = isl_ast_expr_from_constraint(c, build);
1471
461
  build = isl_ast_build_restrict_generated(build, set);
1472
461
1473
545
  for (i = 1; i < n; 
++i84
) {
1474
84
    isl_ast_expr *expr;
1475
84
1476
84
    c = isl_constraint_list_get_constraint(list, i);
1477
84
    bset = isl_basic_set_from_constraint(isl_constraint_copy(c));
1478
84
    set = isl_set_from_basic_set(bset);
1479
84
    expr = isl_ast_expr_from_constraint(c, build);
1480
84
    build = isl_ast_build_restrict_generated(build, set);
1481
84
    res = isl_ast_expr_and(res, expr);
1482
84
  }
1483
461
1484
461
  isl_constraint_list_free(list);
1485
461
  isl_ast_build_free(build);
1486
461
  return res;
1487
461
}
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
797
{
1513
797
  int i, n;
1514
797
  isl_basic_set *bset;
1515
797
  isl_basic_set_list *list;
1516
797
  isl_set *domain;
1517
797
  isl_ast_expr *res;
1518
797
1519
797
  list = isl_set_get_basic_set_list(set);
1520
797
  isl_set_free(set);
1521
797
1522
797
  if (!list)
1523
0
    return NULL;
1524
797
  n = isl_basic_set_list_n_basic_set(list);
1525
797
  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
794
1531
794
  domain = isl_ast_build_get_domain(build);
1532
794
1533
794
  bset = isl_basic_set_list_get_basic_set(list, 0);
1534
794
  set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1535
794
  res = isl_ast_build_expr_from_basic_set(build, bset);
1536
794
1537
889
  for (i = 1; i < n; 
++i95
) {
1538
95
    isl_ast_expr *expr;
1539
95
    isl_set *rest;
1540
95
1541
95
    rest = isl_set_subtract(isl_set_copy(domain), set);
1542
95
    rest = isl_set_from_basic_set(isl_set_simple_hull(rest));
1543
95
    domain = isl_set_intersect(domain, rest);
1544
95
    bset = isl_basic_set_list_get_basic_set(list, i);
1545
95
    set = isl_set_from_basic_set(isl_basic_set_copy(bset));
1546
95
    bset = isl_basic_set_gist(bset,
1547
95
        isl_set_simple_hull(isl_set_copy(domain)));
1548
95
    expr = isl_ast_build_expr_from_basic_set(build, bset);
1549
95
    res = isl_ast_expr_or(res, expr);
1550
95
  }
1551
794
1552
794
  isl_set_free(domain);
1553
794
  isl_set_free(set);
1554
794
  isl_basic_set_list_free(list);
1555
794
  return res;
1556
794
}
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
592
{
1573
592
  if (isl_ast_build_need_schedule_map(build)) {
1574
6
    isl_multi_aff *ma;
1575
6
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
1576
6
    set = isl_set_preimage_multi_aff(set, ma);
1577
6
  }
1578
592
1579
592
  set = isl_set_compute_divs(set);
1580
592
  set = isl_ast_build_compute_gist(build, set);
1581
592
  return isl_ast_build_expr_from_set_internal(build, set);
1582
592
}
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
7.95k
{
1649
7.95k
  int n;
1650
7.95k
  isl_ctx *ctx;
1651
7.95k
1652
7.95k
  ctx = isl_pw_aff_get_ctx(pa);
1653
7.95k
  n = isl_pw_aff_n_piece(pa);
1654
7.95k
  if (n == 0)
1655
7.95k
    
isl_die0
(ctx, isl_error_invalid,
1656
7.95k
      "cannot handle void expression", return isl_stat_error);
1657
7.95k
  data->max = n;
1658
7.95k
  data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
1659
7.95k
  if (!data->p)
1660
0
    return isl_stat_error;
1661
7.95k
  data->build = build;
1662
7.95k
  data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
1663
7.95k
  data->n = 0;
1664
7.95k
1665
7.95k
  return isl_stat_ok;
1666
7.95k
}
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
7.95k
{
1672
7.95k
  int i;
1673
7.95k
1674
7.95k
  isl_set_free(data->dom);
1675
7.95k
  if (!data->p)
1676
0
    return;
1677
7.95k
1678
15.9k
  
for (i = 0; 7.95k
i < data->max;
++i7.98k
) {
1679
7.98k
    isl_set_free(data->p[i].set);
1680
7.98k
    isl_set_list_free(data->p[i].set_list);
1681
7.98k
    isl_aff_list_free(data->p[i].aff_list);
1682
7.98k
  }
1683
7.95k
  free(data->p);
1684
7.95k
}
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
7.95k
{
1690
7.95k
  data->p[data->n].state = isl_state_none;
1691
7.95k
  data->p[data->n].set_list = NULL;
1692
7.95k
  data->p[data->n].aff_list = NULL;
1693
7.95k
}
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
7.96k
{
1700
7.96k
  data->p[data->n].state = isl_state_single;
1701
7.96k
  data->p[data->n].set_list = isl_set_list_from_set(set);
1702
7.96k
  data->p[data->n].aff_list = isl_aff_list_from_aff(aff);
1703
7.96k
}
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
9
{
1711
9
  int n = data->n;
1712
9
  data->p[n].state = isl_state_min;
1713
9
  data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1714
9
  data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1715
9
1716
9
  if (!data->p[n].set_list || !data->p[n].aff_list)
1717
0
    return isl_stat_error;
1718
9
  return isl_stat_ok;
1719
9
}
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
11
{
1727
11
  int n = data->n;
1728
11
  data->p[n].state = isl_state_max;
1729
11
  data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set);
1730
11
  data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff);
1731
11
1732
11
  if (!data->p[n].set_list || !data->p[n].aff_list)
1733
0
    return isl_stat_error;
1734
11
  return isl_stat_ok;
1735
11
}
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
2
{
1745
2
  int n = data->n;
1746
2
  isl_set *set_n;
1747
2
1748
2
  set_n = isl_set_list_get_set(data->p[n].set_list, 0);
1749
2
  set_n = isl_set_union(set_n, set);
1750
2
  data->p[n].set_list =
1751
2
    isl_set_list_set_set(data->p[n].set_list, 0, set_n);
1752
2
1753
2
  if (replace)
1754
2
    data->p[n].aff_list =
1755
2
      isl_aff_list_set_aff(data->p[n].aff_list, 0, aff);
1756
0
  else
1757
0
    isl_aff_free(aff);
1758
2
1759
2
  if (!data->p[n].set_list || !data->p[n].aff_list)
1760
0
    return isl_stat_error;
1761
2
  return isl_stat_ok;
1762
2
}
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
7.96k
{
1774
7.96k
  int i, n;
1775
7.96k
  isl_aff *aff;
1776
7.96k
  isl_ast_expr *expr;
1777
7.96k
  enum isl_ast_op_type op_type;
1778
7.96k
1779
7.96k
  if (state == isl_state_single) {
1780
7.94k
    aff = isl_aff_list_get_aff(list, 0);
1781
7.94k
    isl_aff_list_free(list);
1782
7.94k
    return isl_ast_expr_from_aff(aff, build);
1783
7.94k
  }
1784
20
  n = isl_aff_list_n_aff(list);
1785
20
  op_type = state == isl_state_min ? 
isl_ast_op_min9
:
isl_ast_op_max11
;
1786
20
  expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n);
1787
20
  if (!expr)
1788
0
    goto error;
1789
20
1790
60
  
for (i = 0; 20
i < n;
++i40
) {
1791
40
    isl_ast_expr *expr_i;
1792
40
1793
40
    aff = isl_aff_list_get_aff(list, i);
1794
40
    expr_i = isl_ast_expr_from_aff(aff, build);
1795
40
    if (!expr_i)
1796
0
      goto error;
1797
40
    expr->u.op.args[i] = expr_i;
1798
40
  }
1799
20
1800
20
  isl_aff_list_free(list);
1801
20
  return expr;
1802
0
error:
1803
0
  isl_aff_list_free(list);
1804
0
  isl_ast_expr_free(expr);
1805
0
  return NULL;
1806
20
}
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
13
{
1824
13
  isl_ctx *ctx;
1825
13
  isl_ast_build *build;
1826
13
  isl_ast_expr *ternary, *arg;
1827
13
  isl_set *set, *gist;
1828
13
1829
13
  set = data->p[pos].set;
1830
13
  data->p[pos].set = NULL;
1831
13
  ctx = isl_ast_build_get_ctx(data->build);
1832
13
  ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3);
1833
13
  gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom));
1834
13
  arg = isl_ast_build_expr_from_set_internal(data->build, gist);
1835
13
  ternary = isl_ast_expr_set_op_arg(ternary, 0, arg);
1836
13
  build = isl_ast_build_copy(data->build);
1837
13
  build = isl_ast_build_restrict_generated(build, set);
1838
13
  arg = ast_expr_from_aff_list(data->p[pos].aff_list,
1839
13
          data->p[pos].state, build);
1840
13
  data->p[pos].aff_list = NULL;
1841
13
  isl_ast_build_free(build);
1842
13
  ternary = isl_ast_expr_set_op_arg(ternary, 1, arg);
1843
13
  data->p[pos].state = isl_state_none;
1844
13
  if (!ternary)
1845
0
    return NULL;
1846
13
1847
13
  *next = ternary;
1848
13
  return &ternary->u.op.args[2];
1849
13
}
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
7.95k
{
1864
7.95k
  isl_ast_build *build;
1865
7.95k
1866
7.95k
  if (data->p[pos].state == isl_state_none)
1867
7.95k
    
isl_die0
(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1868
7.95k
      "cannot handle void expression", return isl_stat_error);
1869
7.95k
1870
7.95k
  build = isl_ast_build_copy(data->build);
1871
7.95k
  build = isl_ast_build_restrict_generated(build, data->p[pos].set);
1872
7.95k
  data->p[pos].set = NULL;
1873
7.95k
  *next = ast_expr_from_aff_list(data->p[pos].aff_list,
1874
7.95k
            data->p[pos].state, build);
1875
7.95k
  data->p[pos].aff_list = NULL;
1876
7.95k
  isl_ast_build_free(build);
1877
7.95k
  data->p[pos].state = isl_state_none;
1878
7.95k
  if (!*next)
1879
0
    return isl_stat_error;
1880
7.95k
1881
7.95k
  return isl_stat_ok;
1882
7.95k
}
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
16
{
1893
16
  const struct isl_from_pw_aff_piece *piece1 = p1;
1894
16
  const struct isl_from_pw_aff_piece *piece2 = p2;
1895
16
  int n1, n2;
1896
16
1897
16
  n1 = isl_set_n_basic_set(piece1->set);
1898
16
  n2 = isl_set_n_basic_set(piece2->set);
1899
16
1900
16
  return n1 - n2;
1901
16
}
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
7.95k
{
1918
7.95k
  int i;
1919
7.95k
  isl_ast_expr *res = NULL;
1920
7.95k
  isl_ast_expr **next = &res;
1921
7.95k
1922
7.95k
  if (data->p[data->n].state != isl_state_none)
1923
7.95k
    data->n++;
1924
7.95k
  if (data->n == 0)
1925
7.95k
    
isl_die0
(isl_ast_build_get_ctx(data->build), isl_error_invalid,
1926
7.95k
      "cannot handle void expression", return NULL);
1927
7.95k
1928
15.9k
  
for (i = 0; 7.95k
i < data->n;
++i7.96k
) {
1929
7.96k
    data->p[i].set = isl_set_list_union(data->p[i].set_list);
1930
7.96k
    if (data->p[i].state != isl_state_single)
1931
20
      data->p[i].set = isl_set_coalesce(data->p[i].set);
1932
7.96k
    data->p[i].set_list = NULL;
1933
7.96k
  }
1934
7.95k
1935
7.95k
  if (isl_sort(data->p, data->n, sizeof(data->p[0]),
1936
7.95k
      &sort_pieces_cmp, NULL) < 0)
1937
0
    return isl_ast_expr_free(res);
1938
7.95k
1939
7.96k
  
for (i = 0; 7.95k
i + 1 < data->n;
++i13
) {
1940
13
    next = add_intermediate_piece(data, i, next);
1941
13
    if (!next)
1942
0
      return isl_ast_expr_free(res);
1943
13
  }
1944
7.95k
1945
7.95k
  if (add_last_piece(data, data->n - 1, next) < 0)
1946
0
    return isl_ast_expr_free(res);
1947
7.95k
1948
7.95k
  return res;
1949
7.95k
}
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
34
{
1957
34
  isl_bool subset;
1958
34
  isl_set *set_n;
1959
34
1960
34
  set_n = isl_set_list_get_set(data->p[data->n].set_list, 0);
1961
34
  subset = isl_set_is_subset(set_n, set);
1962
34
  isl_set_free(set_n);
1963
34
1964
34
  return subset;
1965
34
}
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
109
{
1972
109
  isl_bool rational;
1973
109
  isl_val *den;
1974
109
1975
109
  den = isl_aff_get_denominator_val(aff);
1976
109
  rational = isl_bool_not(isl_val_is_one(den));
1977
109
  isl_val_free(den);
1978
109
1979
109
  return rational;
1980
109
}
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
54
{
1986
54
  isl_bool rational;
1987
54
  isl_aff *aff;
1988
54
1989
54
  if (isl_aff_list_n_aff(list) != 1)
1990
1
    return isl_bool_false;
1991
53
  aff = isl_aff_list_get_aff(list, 0);
1992
53
  rational = aff_is_rational(aff);
1993
53
  isl_aff_free(aff);
1994
53
1995
53
  return rational;
1996
53
}
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
56
{
2022
56
  int i, n;
2023
56
  isl_bool is_rational;
2024
56
  isl_ctx *ctx;
2025
56
  isl_set *dom;
2026
56
2027
56
  is_rational = aff_is_rational(aff);
2028
56
  if (is_rational >= 0 && !is_rational)
2029
54
    is_rational = is_single_rational_aff(data->p[data->n].aff_list);
2030
56
  if (is_rational < 0 || is_rational)
2031
2
    return isl_bool_not(is_rational);
2032
54
2033
54
  ctx = isl_ast_build_get_ctx(data->build);
2034
54
  if (!isl_options_get_ast_build_detect_min_max(ctx))
2035
2
    return isl_bool_false;
2036
52
2037
52
  dom = isl_ast_build_get_domain(data->build);
2038
52
  set = isl_set_intersect(dom, isl_set_copy(set));
2039
52
2040
52
  n = isl_set_list_n_set(data->p[data->n].set_list);
2041
72
  for (i = 0; i < n ; 
++i20
) {
2042
52
    isl_aff *aff_i;
2043
52
    isl_set *valid;
2044
52
    isl_set *dom, *required;
2045
52
    isl_bool is_valid;
2046
52
2047
52
    aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2048
52
    valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i));
2049
52
    required = isl_set_list_get_set(data->p[data->n].set_list, i);
2050
52
    dom = isl_ast_build_get_domain(data->build);
2051
52
    required = isl_set_intersect(dom, required);
2052
52
    is_valid = isl_set_is_subset(required, valid);
2053
52
    isl_set_free(required);
2054
52
    isl_set_free(valid);
2055
52
    if (is_valid < 0 || !is_valid) {
2056
24
      isl_set_free(set);
2057
24
      return is_valid;
2058
24
    }
2059
28
2060
28
    aff_i = isl_aff_list_get_aff(data->p[data->n].aff_list, i);
2061
28
    valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff)));
2062
28
    is_valid = isl_set_is_subset(set, valid);
2063
28
    isl_set_free(valid);
2064
28
    if (is_valid < 0 || !is_valid) {
2065
8
      isl_set_free(set);
2066
8
      return is_valid;
2067
8
    }
2068
28
  }
2069
52
2070
52
  isl_set_free(set);
2071
20
  return isl_bool_true;
2072
52
}
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
32
{
2084
32
  return extends(data, set, aff, &isl_aff_ge_basic_set);
2085
32
}
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
24
{
2097
24
  return extends(data, set, aff, &isl_aff_le_basic_set);
2098
24
}
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
7.98k
{
2121
7.98k
  struct isl_from_pw_aff_data *data = user;
2122
7.98k
  isl_bool test;
2123
7.98k
  enum isl_from_pw_aff_state state;
2124
7.98k
2125
7.98k
  state = data->p[data->n].state;
2126
7.98k
  if (state == isl_state_single) {
2127
34
    isl_aff *aff0;
2128
34
    isl_set *eq;
2129
34
    isl_bool subset1, subset2 = isl_bool_false;
2130
34
    aff0 = isl_aff_list_get_aff(data->p[data->n].aff_list, 0);
2131
34
    eq = isl_aff_eq_set(isl_aff_copy(aff), aff0);
2132
34
    subset1 = isl_set_is_subset(set, eq);
2133
34
    if (subset1 >= 0 && !subset1)
2134
34
      subset2 = single_is_subset(data, eq);
2135
34
    isl_set_free(eq);
2136
34
    if (subset1 < 0 || subset2 < 0)
2137
0
      goto error;
2138
34
    if (subset1)
2139
0
      return extend_domain(data, set, aff, 0);
2140
34
    if (subset2)
2141
2
      return extend_domain(data, set, aff, 1);
2142
7.98k
  }
2143
7.98k
  if (state == isl_state_single || 
state == isl_state_min7.95k
) {
2144
32
    test = extends_min(data, set, aff);
2145
32
    if (test < 0)
2146
0
      goto error;
2147
32
    if (test)
2148
9
      return extend_min(data, set, aff);
2149
7.97k
  }
2150
7.97k
  if (state == isl_state_single || 
state == isl_state_max7.95k
) {
2151
24
    test = extends_max(data, set, aff);
2152
24
    if (test < 0)
2153
0
      goto error;
2154
24
    if (test)
2155
11
      return extend_max(data, set, aff);
2156
7.96k
  }
2157
7.96k
  if (state != isl_state_none)
2158
13
    data->n++;
2159
7.96k
  set_single(data, set, aff);
2160
7.96k
2161
7.96k
  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
7.96k
}
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
7.95k
{
2176
7.95k
  struct isl_from_pw_aff_data data = { NULL };
2177
7.95k
  isl_ast_expr *res = NULL;
2178
7.95k
2179
7.95k
  pa = isl_ast_build_compute_gist_pw_aff(build, pa);
2180
7.95k
  pa = isl_pw_aff_coalesce(pa);
2181
7.95k
  if (!pa)
2182
0
    return NULL;
2183
7.95k
2184
7.95k
  if (isl_from_pw_aff_data_init(&data, build, pa) < 0)
2185
0
    goto error;
2186
7.95k
  set_none(&data);
2187
7.95k
2188
7.95k
  if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0)
2189
7.95k
    res = build_pieces(&data);
2190
7.95k
2191
7.95k
  isl_pw_aff_free(pa);
2192
7.95k
  isl_from_pw_aff_data_clear(&data);
2193
7.95k
  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
7.95k
}
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
26
{
2208
26
  isl_ast_expr *expr;
2209
26
2210
26
  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
26
  expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2216
26
  return expr;
2217
26
}
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
3.15k
{
2227
3.15k
  int i, n;
2228
3.15k
2229
3.15k
  n = isl_multi_pw_aff_dim(mpa, isl_dim_in);
2230
17.9k
  for (i = 0; i < n; 
++i14.8k
) {
2231
14.8k
    isl_id *id;
2232
14.8k
2233
14.8k
    id = isl_ast_build_get_iterator_id(build, i);
2234
14.8k
    mpa = isl_multi_pw_aff_set_dim_id(mpa, isl_dim_in, i, id);
2235
14.8k
  }
2236
3.15k
2237
3.15k
  return mpa;
2238
3.15k
}
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
3.15k
{
2249
3.15k
  int i, n;
2250
3.15k
  isl_ctx *ctx;
2251
3.15k
  isl_ast_expr *expr;
2252
3.15k
2253
3.15k
  ctx = isl_ast_build_get_ctx(build);
2254
3.15k
2255
3.15k
  n = isl_multi_pw_aff_dim(mpa, isl_dim_out);
2256
3.15k
  expr = isl_ast_expr_alloc_op(ctx, type, 1 + n);
2257
3.15k
  expr = isl_ast_expr_set_op_arg(expr, 0, arg0);
2258
9.60k
  for (i = 0; i < n; 
++i6.45k
) {
2259
6.45k
    isl_pw_aff *pa;
2260
6.45k
    isl_ast_expr *arg;
2261
6.45k
2262
6.45k
    pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
2263
6.45k
    arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2264
6.45k
    expr = isl_ast_expr_set_op_arg(expr, 1 + i, arg);
2265
6.45k
  }
2266
3.15k
2267
3.15k
  isl_multi_pw_aff_free(mpa);
2268
3.15k
  return expr;
2269
3.15k
}
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
3.15k
{
2322
3.15k
  isl_ctx *ctx;
2323
3.15k
  isl_id *id;
2324
3.15k
  isl_ast_expr *expr;
2325
3.15k
2326
3.15k
  if (!mpa)
2327
0
    goto error;
2328
3.15k
2329
3.15k
  if (type == isl_ast_op_access &&
2330
3.15k
      
isl_multi_pw_aff_range_is_wrapping(mpa)1.00k
)
2331
0
    return isl_ast_build_from_multi_pw_aff_member(build, mpa);
2332
3.15k
2333
3.15k
  mpa = set_iterator_names(build, mpa);
2334
3.15k
  if (!build || !mpa)
2335
0
    goto error;
2336
3.15k
2337
3.15k
  ctx = isl_ast_build_get_ctx(build);
2338
3.15k
2339
3.15k
  if (isl_multi_pw_aff_has_tuple_id(mpa, isl_dim_out))
2340
3.15k
    id = isl_multi_pw_aff_get_tuple_id(mpa, isl_dim_out);
2341
0
  else
2342
0
    id = isl_id_alloc(ctx, "", NULL);
2343
3.15k
2344
3.15k
  expr = isl_ast_expr_from_id(id);
2345
3.15k
  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
3.15k
}
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
2.15k
{
2362
2.15k
  isl_multi_pw_aff *mpa;
2363
2.15k
2364
2.15k
  mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2365
2.15k
  return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2366
2.15k
}
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
1.00k
{
2379
1.00k
  int is_domain;
2380
1.00k
  isl_ast_expr *expr;
2381
1.00k
  isl_space *space_build, *space_mpa;
2382
1.00k
2383
1.00k
  space_build = isl_ast_build_get_space(build, 0);
2384
1.00k
  space_mpa = isl_multi_pw_aff_get_space(mpa);
2385
1.00k
  is_domain = isl_space_tuple_is_equal(space_build, isl_dim_set,
2386
1.00k
          space_mpa, isl_dim_in);
2387
1.00k
  isl_space_free(space_build);
2388
1.00k
  isl_space_free(space_mpa);
2389
1.00k
  if (is_domain < 0)
2390
0
    goto error;
2391
1.00k
  if (!is_domain)
2392
1.00k
    
isl_die0
(isl_ast_build_get_ctx(build), isl_error_invalid,
2393
1.00k
      "spaces don't match", goto error);
2394
1.00k
2395
1.00k
  if (isl_ast_build_need_schedule_map(build)) {
2396
188
    isl_multi_aff *ma;
2397
188
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
2398
188
    mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
2399
188
  }
2400
1.00k
2401
1.00k
  expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2402
1.00k
  return expr;
2403
0
error:
2404
0
  isl_multi_pw_aff_free(mpa);
2405
0
  return NULL;
2406
1.00k
}
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
1.00k
{
2443
1.00k
  isl_multi_pw_aff *mpa;
2444
1.00k
2445
1.00k
  mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2446
1.00k
  return isl_ast_build_from_multi_pw_aff(build, type, mpa);
2447
1.00k
}
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
1.00k
{
2470
1.00k
  return isl_ast_build_from_pw_multi_aff(build, isl_ast_op_access, pma);
2471
1.00k
}
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
2.15k
{
2482
2.15k
  isl_pw_multi_aff *iteration;
2483
2.15k
  isl_ast_expr *expr;
2484
2.15k
2485
2.15k
  iteration = isl_pw_multi_aff_from_map(executed);
2486
2.15k
  iteration = isl_ast_build_compute_gist_pw_multi_aff(build, iteration);
2487
2.15k
  iteration = isl_pw_multi_aff_intersect_domain(iteration,
2488
2.15k
          isl_ast_build_get_domain(build));
2489
2.15k
  expr = isl_ast_build_from_pw_multi_aff_internal(build, isl_ast_op_call,
2490
2.15k
              iteration);
2491
2.15k
  return isl_ast_node_alloc_user(expr);
2492
2.15k
}