Coverage Report

Created: 2018-02-20 23:11

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