Coverage Report

Created: 2017-08-18 19:41

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