Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_ast_build.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2012-2013 Ecole Normale Superieure
3
 * Copyright 2014      INRIA Rocquencourt
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege,
8
 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10
 * B.P. 105 - 78153 Le Chesnay, France
11
 */
12
13
#include <isl/id.h>
14
#include <isl/val.h>
15
#include <isl/space.h>
16
#include <isl/map.h>
17
#include <isl/aff.h>
18
#include <isl/constraint.h>
19
#include <isl/map.h>
20
#include <isl/union_set.h>
21
#include <isl/union_map.h>
22
#include <isl_ast_build_private.h>
23
#include <isl_ast_private.h>
24
#include <isl_config.h>
25
26
/* Construct a map that isolates the current dimension.
27
 *
28
 * Essentially, the current dimension of "set" is moved to the single output
29
 * dimension in the result, with the current dimension in the domain replaced
30
 * by an unconstrained variable.
31
 */
32
__isl_give isl_map *isl_ast_build_map_to_iterator(
33
  __isl_keep isl_ast_build *build, __isl_take isl_set *set)
34
4.07k
{
35
4.07k
  isl_map *map;
36
4.07k
37
4.07k
  map = isl_map_from_domain(set);
38
4.07k
  map = isl_map_add_dims(map, isl_dim_out, 1);
39
4.07k
40
4.07k
  if (!build)
41
0
    return isl_map_free(map);
42
4.07k
43
4.07k
  map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
44
4.07k
  map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
45
4.07k
46
4.07k
  return map;
47
4.07k
}
48
49
/* Initialize the information derived during the AST generation to default
50
 * values for a schedule domain in "space".
51
 *
52
 * We also check that the remaining fields are not NULL so that
53
 * the calling functions don't have to perform this test.
54
 */
55
static __isl_give isl_ast_build *isl_ast_build_init_derived(
56
  __isl_take isl_ast_build *build, __isl_take isl_space *space)
57
1.08k
{
58
1.08k
  isl_ctx *ctx;
59
1.08k
  isl_vec *strides;
60
1.08k
61
1.08k
  build = isl_ast_build_cow(build);
62
1.08k
  if (!build || !build->domain)
63
0
    goto error;
64
1.08k
65
1.08k
  ctx = isl_ast_build_get_ctx(build);
66
1.08k
  strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
67
1.08k
  strides = isl_vec_set_si(strides, 1);
68
1.08k
69
1.08k
  isl_vec_free(build->strides);
70
1.08k
  build->strides = strides;
71
1.08k
72
1.08k
  space = isl_space_map_from_set(space);
73
1.08k
  isl_multi_aff_free(build->offsets);
74
1.08k
  build->offsets = isl_multi_aff_zero(isl_space_copy(space));
75
1.08k
  isl_multi_aff_free(build->values);
76
1.08k
  build->values = isl_multi_aff_identity(isl_space_copy(space));
77
1.08k
  isl_multi_aff_free(build->internal2input);
78
1.08k
  build->internal2input = isl_multi_aff_identity(space);
79
1.08k
80
1.08k
  if (!build->iterators || !build->domain || !build->generated ||
81
1.08k
      !build->pending || !build->values || !build->internal2input ||
82
1.08k
      !build->strides || !build->offsets || !build->options)
83
0
    return isl_ast_build_free(build);
84
1.08k
85
1.08k
  return build;
86
0
error:
87
0
  isl_space_free(space);
88
0
  return isl_ast_build_free(build);
89
1.08k
}
90
91
/* Return an isl_id called "c%d", with "%d" set to "i".
92
 * If an isl_id with such a name already appears among the parameters
93
 * in build->domain, then adjust the name to "c%d_%d".
94
 */
95
static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
96
  __isl_keep isl_ast_build *build)
97
941
{
98
941
  int j;
99
941
  char name[23];
100
941
  isl_set *dom = build->domain;
101
941
102
941
  snprintf(name, sizeof(name), "c%d", i);
103
941
  j = 0;
104
941
  while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
105
941
    snprintf(name, sizeof(name), "c%d_%d", i, j++);
106
941
  return isl_id_alloc(ctx, name, NULL);
107
941
}
108
109
/* Create an isl_ast_build with "set" as domain.
110
 *
111
 * The input set is usually a parameter domain, but we currently allow it to
112
 * be any kind of set.  We set the domain of the returned isl_ast_build
113
 * to "set" and initialize all the other fields to default values.
114
 */
115
__isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
116
617
{
117
617
  int i, n;
118
617
  isl_ctx *ctx;
119
617
  isl_space *space;
120
617
  isl_ast_build *build;
121
617
122
617
  set = isl_set_compute_divs(set);
123
617
  if (!set)
124
0
    return NULL;
125
617
126
617
  ctx = isl_set_get_ctx(set);
127
617
128
617
  build = isl_calloc_type(ctx, isl_ast_build);
129
617
  if (!build)
130
0
    goto error;
131
617
132
617
  build->ref = 1;
133
617
  build->domain = set;
134
617
  build->generated = isl_set_copy(build->domain);
135
617
  build->pending = isl_set_universe(isl_set_get_space(build->domain));
136
617
  build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
137
617
  n = isl_set_dim(set, isl_dim_set);
138
617
  build->depth = n;
139
617
  build->iterators = isl_id_list_alloc(ctx, n);
140
617
  for (i = 0; i < n; 
++i0
) {
141
0
    isl_id *id;
142
0
    if (isl_set_has_dim_id(set, isl_dim_set, i))
143
0
      id = isl_set_get_dim_id(set, isl_dim_set, i);
144
0
    else
145
0
      id = generate_name(ctx, i, build);
146
0
    build->iterators = isl_id_list_add(build->iterators, id);
147
0
  }
148
617
  space = isl_set_get_space(set);
149
617
  if (isl_space_is_params(space))
150
617
    space = isl_space_set_from_params(space);
151
617
152
617
  return isl_ast_build_init_derived(build, space);
153
0
error:
154
0
  isl_set_free(set);
155
0
  return NULL;
156
617
}
157
158
/* Create an isl_ast_build with a universe (parametric) context.
159
 */
160
__isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
161
1
{
162
1
  isl_space *space;
163
1
  isl_set *context;
164
1
165
1
  space = isl_space_params_alloc(ctx, 0);
166
1
  context = isl_set_universe(space);
167
1
168
1
  return isl_ast_build_from_context(context);
169
1
}
170
171
__isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
172
52.4k
{
173
52.4k
  if (!build)
174
0
    return NULL;
175
52.4k
176
52.4k
  build->ref++;
177
52.4k
  return build;
178
52.4k
}
179
180
__isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
181
36.5k
{
182
36.5k
  isl_ctx *ctx;
183
36.5k
  isl_ast_build *dup;
184
36.5k
185
36.5k
  if (!build)
186
0
    return NULL;
187
36.5k
188
36.5k
  ctx = isl_ast_build_get_ctx(build);
189
36.5k
  dup = isl_calloc_type(ctx, isl_ast_build);
190
36.5k
  if (!dup)
191
0
    return NULL;
192
36.5k
193
36.5k
  dup->ref = 1;
194
36.5k
  dup->outer_pos = build->outer_pos;
195
36.5k
  dup->depth = build->depth;
196
36.5k
  dup->iterators = isl_id_list_copy(build->iterators);
197
36.5k
  dup->domain = isl_set_copy(build->domain);
198
36.5k
  dup->generated = isl_set_copy(build->generated);
199
36.5k
  dup->pending = isl_set_copy(build->pending);
200
36.5k
  dup->values = isl_multi_aff_copy(build->values);
201
36.5k
  dup->internal2input = isl_multi_aff_copy(build->internal2input);
202
36.5k
  dup->value = isl_pw_aff_copy(build->value);
203
36.5k
  dup->strides = isl_vec_copy(build->strides);
204
36.5k
  dup->offsets = isl_multi_aff_copy(build->offsets);
205
36.5k
  dup->executed = isl_union_map_copy(build->executed);
206
36.5k
  dup->single_valued = build->single_valued;
207
36.5k
  dup->options = isl_union_map_copy(build->options);
208
36.5k
  dup->at_each_domain = build->at_each_domain;
209
36.5k
  dup->at_each_domain_user = build->at_each_domain_user;
210
36.5k
  dup->before_each_for = build->before_each_for;
211
36.5k
  dup->before_each_for_user = build->before_each_for_user;
212
36.5k
  dup->after_each_for = build->after_each_for;
213
36.5k
  dup->after_each_for_user = build->after_each_for_user;
214
36.5k
  dup->before_each_mark = build->before_each_mark;
215
36.5k
  dup->before_each_mark_user = build->before_each_mark_user;
216
36.5k
  dup->after_each_mark = build->after_each_mark;
217
36.5k
  dup->after_each_mark_user = build->after_each_mark_user;
218
36.5k
  dup->create_leaf = build->create_leaf;
219
36.5k
  dup->create_leaf_user = build->create_leaf_user;
220
36.5k
  dup->node = isl_schedule_node_copy(build->node);
221
36.5k
  if (build->loop_type) {
222
33.8k
    int i;
223
33.8k
224
33.8k
    dup->n = build->n;
225
33.8k
    dup->loop_type = isl_alloc_array(ctx,
226
33.8k
            enum isl_ast_loop_type, dup->n);
227
33.8k
    if (dup->n && !dup->loop_type)
228
0
      return isl_ast_build_free(dup);
229
121k
    
for (i = 0; 33.8k
i < dup->n;
++i87.1k
)
230
87.1k
      dup->loop_type[i] = build->loop_type[i];
231
33.8k
  }
232
36.5k
233
36.5k
  if (!dup->iterators || !dup->domain || !dup->generated ||
234
36.5k
      !dup->pending || !dup->values ||
235
36.5k
      !dup->strides || !dup->offsets || !dup->options ||
236
36.5k
      (build->internal2input && 
!dup->internal2input36.4k
) ||
237
36.5k
      (build->executed && 
!dup->executed33.4k
) ||
238
36.5k
      (build->value && 
!dup->value6.71k
) ||
239
36.5k
      (build->node && 
!dup->node23.1k
))
240
0
    return isl_ast_build_free(dup);
241
36.5k
242
36.5k
  return dup;
243
36.5k
}
244
245
/* Align the parameters of "build" to those of "model", introducing
246
 * additional parameters if needed.
247
 */
248
__isl_give isl_ast_build *isl_ast_build_align_params(
249
  __isl_take isl_ast_build *build, __isl_take isl_space *model)
250
31
{
251
31
  build = isl_ast_build_cow(build);
252
31
  if (!build)
253
0
    goto error;
254
31
255
31
  build->domain = isl_set_align_params(build->domain,
256
31
            isl_space_copy(model));
257
31
  build->generated = isl_set_align_params(build->generated,
258
31
            isl_space_copy(model));
259
31
  build->pending = isl_set_align_params(build->pending,
260
31
            isl_space_copy(model));
261
31
  build->values = isl_multi_aff_align_params(build->values,
262
31
            isl_space_copy(model));
263
31
  build->offsets = isl_multi_aff_align_params(build->offsets,
264
31
            isl_space_copy(model));
265
31
  build->options = isl_union_map_align_params(build->options,
266
31
            isl_space_copy(model));
267
31
  if (build->internal2input) {
268
31
    build->internal2input =
269
31
      isl_multi_aff_align_params(build->internal2input,
270
31
            model);
271
31
    if (!build->internal2input)
272
0
      return isl_ast_build_free(build);
273
0
  } else {
274
0
    isl_space_free(model);
275
0
  }
276
31
277
31
  if (!build->domain || !build->values || !build->offsets ||
278
31
      !build->options)
279
0
    return isl_ast_build_free(build);
280
31
281
31
  return build;
282
0
error:
283
0
  isl_space_free(model);
284
0
  return NULL;
285
31
}
286
287
__isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
288
65.3k
{
289
65.3k
  if (!build)
290
0
    return NULL;
291
65.3k
292
65.3k
  if (build->ref == 1)
293
28.7k
    return build;
294
36.5k
  build->ref--;
295
36.5k
  return isl_ast_build_dup(build);
296
36.5k
}
297
298
__isl_null isl_ast_build *isl_ast_build_free(
299
  __isl_take isl_ast_build *build)
300
53.0k
{
301
53.0k
  if (!build)
302
0
    return NULL;
303
53.0k
304
53.0k
  if (--build->ref > 0)
305
15.8k
    return NULL;
306
37.1k
307
37.1k
  isl_id_list_free(build->iterators);
308
37.1k
  isl_set_free(build->domain);
309
37.1k
  isl_set_free(build->generated);
310
37.1k
  isl_set_free(build->pending);
311
37.1k
  isl_multi_aff_free(build->values);
312
37.1k
  isl_multi_aff_free(build->internal2input);
313
37.1k
  isl_pw_aff_free(build->value);
314
37.1k
  isl_vec_free(build->strides);
315
37.1k
  isl_multi_aff_free(build->offsets);
316
37.1k
  isl_multi_aff_free(build->schedule_map);
317
37.1k
  isl_union_map_free(build->executed);
318
37.1k
  isl_union_map_free(build->options);
319
37.1k
  isl_schedule_node_free(build->node);
320
37.1k
  free(build->loop_type);
321
37.1k
  isl_set_free(build->isolated);
322
37.1k
323
37.1k
  free(build);
324
37.1k
325
37.1k
  return NULL;
326
37.1k
}
327
328
isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
329
69.3k
{
330
69.3k
  return build ? isl_set_get_ctx(build->domain) : NULL;
331
69.3k
}
332
333
/* Replace build->options by "options".
334
 */
335
__isl_give isl_ast_build *isl_ast_build_set_options(
336
  __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
337
3
{
338
3
  build = isl_ast_build_cow(build);
339
3
340
3
  if (!build || !options)
341
0
    goto error;
342
3
343
3
  isl_union_map_free(build->options);
344
3
  build->options = options;
345
3
346
3
  return build;
347
0
error:
348
0
  isl_union_map_free(options);
349
0
  return isl_ast_build_free(build);
350
3
}
351
352
/* Set the iterators for the next code generation.
353
 *
354
 * If we still have some iterators left from the previous code generation
355
 * (if any) or if iterators have already been set by a previous
356
 * call to this function, then we remove them first.
357
 */
358
__isl_give isl_ast_build *isl_ast_build_set_iterators(
359
  __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
360
0
{
361
0
  int dim, n_it;
362
0
363
0
  build = isl_ast_build_cow(build);
364
0
  if (!build)
365
0
    goto error;
366
0
367
0
  dim = isl_set_dim(build->domain, isl_dim_set);
368
0
  n_it = isl_id_list_n_id(build->iterators);
369
0
  if (n_it < dim)
370
0
    isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
371
0
      "isl_ast_build in inconsistent state", goto error);
372
0
  if (n_it > dim)
373
0
    build->iterators = isl_id_list_drop(build->iterators,
374
0
              dim, n_it - dim);
375
0
  build->iterators = isl_id_list_concat(build->iterators, iterators);
376
0
  if (!build->iterators)
377
0
    return isl_ast_build_free(build);
378
0
379
0
  return build;
380
0
error:
381
0
  isl_id_list_free(iterators);
382
0
  return isl_ast_build_free(build);
383
0
}
384
385
/* Set the "at_each_domain" callback of "build" to "fn".
386
 */
387
__isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
388
  __isl_take isl_ast_build *build,
389
  __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
390
    __isl_keep isl_ast_build *build, void *user), void *user)
391
459
{
392
459
  build = isl_ast_build_cow(build);
393
459
394
459
  if (!build)
395
0
    return NULL;
396
459
397
459
  build->at_each_domain = fn;
398
459
  build->at_each_domain_user = user;
399
459
400
459
  return build;
401
459
}
402
403
/* Set the "before_each_for" callback of "build" to "fn".
404
 */
405
__isl_give isl_ast_build *isl_ast_build_set_before_each_for(
406
  __isl_take isl_ast_build *build,
407
  __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
408
    void *user), void *user)
409
124
{
410
124
  build = isl_ast_build_cow(build);
411
124
412
124
  if (!build)
413
0
    return NULL;
414
124
415
124
  build->before_each_for = fn;
416
124
  build->before_each_for_user = user;
417
124
418
124
  return build;
419
124
}
420
421
/* Set the "after_each_for" callback of "build" to "fn".
422
 */
423
__isl_give isl_ast_build *isl_ast_build_set_after_each_for(
424
  __isl_take isl_ast_build *build,
425
  __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
426
    __isl_keep isl_ast_build *build, void *user), void *user)
427
124
{
428
124
  build = isl_ast_build_cow(build);
429
124
430
124
  if (!build)
431
0
    return NULL;
432
124
433
124
  build->after_each_for = fn;
434
124
  build->after_each_for_user = user;
435
124
436
124
  return build;
437
124
}
438
439
/* Set the "before_each_mark" callback of "build" to "fn".
440
 */
441
__isl_give isl_ast_build *isl_ast_build_set_before_each_mark(
442
  __isl_take isl_ast_build *build,
443
  isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,
444
    void *user), void *user)
445
123
{
446
123
  build = isl_ast_build_cow(build);
447
123
448
123
  if (!build)
449
0
    return NULL;
450
123
451
123
  build->before_each_mark = fn;
452
123
  build->before_each_mark_user = user;
453
123
454
123
  return build;
455
123
}
456
457
/* Set the "after_each_mark" callback of "build" to "fn".
458
 */
459
__isl_give isl_ast_build *isl_ast_build_set_after_each_mark(
460
  __isl_take isl_ast_build *build,
461
  __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
462
    __isl_keep isl_ast_build *build, void *user), void *user)
463
123
{
464
123
  build = isl_ast_build_cow(build);
465
123
466
123
  if (!build)
467
0
    return NULL;
468
123
469
123
  build->after_each_mark = fn;
470
123
  build->after_each_mark_user = user;
471
123
472
123
  return build;
473
123
}
474
475
/* Set the "create_leaf" callback of "build" to "fn".
476
 */
477
__isl_give isl_ast_build *isl_ast_build_set_create_leaf(
478
  __isl_take isl_ast_build *build,
479
  __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
480
    void *user), void *user)
481
1
{
482
1
  build = isl_ast_build_cow(build);
483
1
484
1
  if (!build)
485
0
    return NULL;
486
1
487
1
  build->create_leaf = fn;
488
1
  build->create_leaf_user = user;
489
1
490
1
  return build;
491
1
}
492
493
/* Clear all information that is specific to this code generation
494
 * and that is (probably) not meaningful to any nested code generation.
495
 */
496
__isl_give isl_ast_build *isl_ast_build_clear_local_info(
497
  __isl_take isl_ast_build *build)
498
3
{
499
3
  isl_space *space;
500
3
501
3
  build = isl_ast_build_cow(build);
502
3
  if (!build)
503
0
    return NULL;
504
3
505
3
  space = isl_union_map_get_space(build->options);
506
3
  isl_union_map_free(build->options);
507
3
  build->options = isl_union_map_empty(space);
508
3
509
3
  build->at_each_domain = NULL;
510
3
  build->at_each_domain_user = NULL;
511
3
  build->before_each_for = NULL;
512
3
  build->before_each_for_user = NULL;
513
3
  build->after_each_for = NULL;
514
3
  build->after_each_for_user = NULL;
515
3
  build->before_each_mark = NULL;
516
3
  build->before_each_mark_user = NULL;
517
3
  build->after_each_mark = NULL;
518
3
  build->after_each_mark_user = NULL;
519
3
  build->create_leaf = NULL;
520
3
  build->create_leaf_user = NULL;
521
3
522
3
  if (!build->options)
523
0
    return isl_ast_build_free(build);
524
3
525
3
  return build;
526
3
}
527
528
/* Have any loops been eliminated?
529
 * That is, do any of the original schedule dimensions have a fixed
530
 * value that has been substituted?
531
 */
532
static int any_eliminated(isl_ast_build *build)
533
3.33k
{
534
3.33k
  int i;
535
3.33k
536
4.38k
  for (i = 0; i < build->depth; 
++i1.05k
)
537
1.81k
    if (isl_ast_build_has_affine_value(build, i))
538
758
      return 1;
539
3.33k
540
3.33k
  
return 02.57k
;
541
3.33k
}
542
543
/* Clear build->schedule_map.
544
 * This function should be called whenever anything that might affect
545
 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
546
 * In particular, it should be called when the depth is changed or
547
 * when an iterator is determined to have a fixed value.
548
 */
549
static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
550
7.38k
{
551
7.38k
  if (!build)
552
0
    return;
553
7.38k
  isl_multi_aff_free(build->schedule_map);
554
7.38k
  build->schedule_map = NULL;
555
7.38k
}
556
557
/* Do we need a (non-trivial) schedule map?
558
 * That is, is the internal schedule space different from
559
 * the external schedule space?
560
 *
561
 * The internal and external schedule spaces are only the same
562
 * if code has been generated for the entire schedule and if none
563
 * of the loops have been eliminated.
564
 */
565
__isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
566
3.45k
{
567
3.45k
  int dim;
568
3.45k
569
3.45k
  if (!build)
570
0
    return -1;
571
3.45k
572
3.45k
  dim = isl_set_dim(build->domain, isl_dim_set);
573
3.45k
  return build->depth != dim || 
any_eliminated(build)3.33k
;
574
3.45k
}
575
576
/* Return a mapping from the internal schedule space to the external
577
 * schedule space in the form of an isl_multi_aff.
578
 * The internal schedule space originally corresponds to that of the
579
 * input schedule.  This may change during the code generation if
580
 * if isl_ast_build_insert_dim is ever called.
581
 * The external schedule space corresponds to the
582
 * loops that have been generated.
583
 *
584
 * Currently, the only difference between the internal schedule domain
585
 * and the external schedule domain is that some dimensions are projected
586
 * out in the external schedule domain.  In particular, the dimensions
587
 * for which no code has been generated yet and the dimensions that correspond
588
 * to eliminated loops.
589
 *
590
 * We cache a copy of the schedule_map in build->schedule_map.
591
 * The cache is cleared through isl_ast_build_reset_schedule_map
592
 * whenever anything changes that might affect the result of this function.
593
 */
594
__isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
595
  __isl_keep isl_ast_build *build)
596
503
{
597
503
  isl_space *space;
598
503
  isl_multi_aff *ma;
599
503
600
503
  if (!build)
601
0
    return NULL;
602
503
  if (build->schedule_map)
603
325
    return isl_multi_aff_copy(build->schedule_map);
604
178
605
178
  space = isl_ast_build_get_space(build, 1);
606
178
  space = isl_space_map_from_set(space);
607
178
  ma = isl_multi_aff_identity(space);
608
178
  if (isl_ast_build_need_schedule_map(build)) {
609
178
    int i;
610
178
    int dim = isl_set_dim(build->domain, isl_dim_set);
611
178
    ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
612
178
          build->depth, dim - build->depth);
613
938
    for (i = build->depth - 1; i >= 0; 
--i760
)
614
760
      if (isl_ast_build_has_affine_value(build, i))
615
326
        ma = isl_multi_aff_drop_dims(ma,
616
326
              isl_dim_out, i, 1);
617
178
  }
618
178
619
178
  build->schedule_map = ma;
620
178
  return isl_multi_aff_copy(build->schedule_map);
621
178
}
622
623
/* Return a mapping from the internal schedule space to the external
624
 * schedule space in the form of an isl_map.
625
 */
626
__isl_give isl_map *isl_ast_build_get_schedule_map(
627
  __isl_keep isl_ast_build *build)
628
299
{
629
299
  isl_multi_aff *ma;
630
299
631
299
  ma = isl_ast_build_get_schedule_map_multi_aff(build);
632
299
  return isl_map_from_multi_aff(ma);
633
299
}
634
635
/* Return the position of the dimension in build->domain for which
636
 * an AST node is currently being generated.
637
 */
638
int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
639
38.6k
{
640
38.6k
  return build ? build->depth : 
-10
;
641
38.6k
}
642
643
/* Prepare for generating code for the next level.
644
 * In particular, increase the depth and reset any information
645
 * that is local to the current depth.
646
 */
647
__isl_give isl_ast_build *isl_ast_build_increase_depth(
648
  __isl_take isl_ast_build *build)
649
4.06k
{
650
4.06k
  build = isl_ast_build_cow(build);
651
4.06k
  if (!build)
652
0
    return NULL;
653
4.06k
  build->depth++;
654
4.06k
  isl_ast_build_reset_schedule_map(build);
655
4.06k
  build->value = isl_pw_aff_free(build->value);
656
4.06k
  return build;
657
4.06k
}
658
659
void isl_ast_build_dump(__isl_keep isl_ast_build *build)
660
0
{
661
0
  if (!build)
662
0
    return;
663
0
664
0
  fprintf(stderr, "domain: ");
665
0
  isl_set_dump(build->domain);
666
0
  fprintf(stderr, "generated: ");
667
0
  isl_set_dump(build->generated);
668
0
  fprintf(stderr, "pending: ");
669
0
  isl_set_dump(build->pending);
670
0
  fprintf(stderr, "iterators: ");
671
0
  isl_id_list_dump(build->iterators);
672
0
  fprintf(stderr, "values: ");
673
0
  isl_multi_aff_dump(build->values);
674
0
  if (build->value) {
675
0
    fprintf(stderr, "value: ");
676
0
    isl_pw_aff_dump(build->value);
677
0
  }
678
0
  fprintf(stderr, "strides: ");
679
0
  isl_vec_dump(build->strides);
680
0
  fprintf(stderr, "offsets: ");
681
0
  isl_multi_aff_dump(build->offsets);
682
0
  fprintf(stderr, "internal2input: ");
683
0
  isl_multi_aff_dump(build->internal2input);
684
0
}
685
686
/* Initialize "build" for AST construction in schedule space "space"
687
 * in the case that build->domain is a parameter set.
688
 *
689
 * build->iterators is assumed to have been updated already.
690
 */
691
static __isl_give isl_ast_build *isl_ast_build_init(
692
  __isl_take isl_ast_build *build, __isl_take isl_space *space)
693
464
{
694
464
  isl_set *set;
695
464
696
464
  build = isl_ast_build_cow(build);
697
464
  if (!build)
698
0
    goto error;
699
464
700
464
  set = isl_set_universe(isl_space_copy(space));
701
464
  build->domain = isl_set_intersect_params(isl_set_copy(set),
702
464
                build->domain);
703
464
  build->pending = isl_set_intersect_params(isl_set_copy(set),
704
464
                build->pending);
705
464
  build->generated = isl_set_intersect_params(set, build->generated);
706
464
707
464
  return isl_ast_build_init_derived(build, space);
708
0
error:
709
0
  isl_ast_build_free(build);
710
0
  isl_space_free(space);
711
0
  return NULL;
712
464
}
713
714
/* Assign "aff" to *user and return -1, effectively extracting
715
 * the first (and presumably only) affine expression in the isl_pw_aff
716
 * on which this function is used.
717
 */
718
static isl_stat extract_single_piece(__isl_take isl_set *set,
719
  __isl_take isl_aff *aff, void *user)
720
3.31k
{
721
3.31k
  isl_aff **p = user;
722
3.31k
723
3.31k
  *p = aff;
724
3.31k
  isl_set_free(set);
725
3.31k
726
3.31k
  return isl_stat_error;
727
3.31k
}
728
729
/* Intersect "set" with the stride constraint of "build", if any.
730
 */
731
static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
732
  __isl_keep isl_ast_build *build)
733
4.06k
{
734
4.06k
  isl_set *stride;
735
4.06k
736
4.06k
  if (!build)
737
0
    return isl_set_free(set);
738
4.06k
  if (!isl_ast_build_has_stride(build, build->depth))
739
4.05k
    return set;
740
15
741
15
  stride = isl_ast_build_get_stride_constraint(build);
742
15
  return isl_set_intersect(set, stride);
743
15
}
744
745
/* Check if the given bounds on the current dimension (together with
746
 * the stride constraint, if any) imply that
747
 * this current dimension attains only a single value (in terms of
748
 * parameters and outer dimensions).
749
 * If so, we record it in build->value.
750
 * If, moreover, this value can be represented as a single affine expression,
751
 * then we also update build->values, effectively marking the current
752
 * dimension as "eliminated".
753
 *
754
 * When computing the gist of the fixed value that can be represented
755
 * as a single affine expression, it is important to only take into
756
 * account the domain constraints in the original AST build and
757
 * not the domain of the affine expression itself.
758
 * Otherwise, a [i/3] is changed into a i/3 because we know that i
759
 * is a multiple of 3, but then we end up not expressing anywhere
760
 * in the context that i is a multiple of 3.
761
 */
762
static __isl_give isl_ast_build *update_values(
763
  __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
764
4.06k
{
765
4.06k
  int sv;
766
4.06k
  isl_pw_multi_aff *pma;
767
4.06k
  isl_aff *aff = NULL;
768
4.06k
  isl_map *it_map;
769
4.06k
  isl_set *set;
770
4.06k
771
4.06k
  set = isl_set_from_basic_set(bounds);
772
4.06k
  set = isl_set_intersect(set, isl_set_copy(build->domain));
773
4.06k
  set = intersect_stride_constraint(set, build);
774
4.06k
  it_map = isl_ast_build_map_to_iterator(build, set);
775
4.06k
776
4.06k
  sv = isl_map_is_single_valued(it_map);
777
4.06k
  if (sv < 0)
778
0
    build = isl_ast_build_free(build);
779
4.06k
  if (!build || !sv) {
780
749
    isl_map_free(it_map);
781
749
    return build;
782
749
  }
783
3.31k
784
3.31k
  pma = isl_pw_multi_aff_from_map(it_map);
785
3.31k
  build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
786
3.31k
  build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
787
3.31k
  build->value = isl_pw_aff_coalesce(build->value);
788
3.31k
  isl_pw_multi_aff_free(pma);
789
3.31k
790
3.31k
  if (!build->value)
791
0
    return isl_ast_build_free(build);
792
3.31k
793
3.31k
  if (isl_pw_aff_n_piece(build->value) != 1)
794
0
    return build;
795
3.31k
796
3.31k
  isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
797
3.31k
798
3.31k
  build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
799
3.31k
  if (!build->values)
800
0
    return isl_ast_build_free(build);
801
3.31k
  isl_ast_build_reset_schedule_map(build);
802
3.31k
  return build;
803
3.31k
}
804
805
/* Update the AST build based on the given loop bounds for
806
 * the current dimension and the stride information available in the build.
807
 *
808
 * We first make sure that the bounds do not refer to any iterators
809
 * that have already been eliminated.
810
 * Then, we check if the bounds imply that the current iterator
811
 * has a fixed value.
812
 * If they do and if this fixed value can be expressed as a single
813
 * affine expression, we eliminate the iterators from the bounds.
814
 * Note that we cannot simply plug in this single value using
815
 * isl_basic_set_preimage_multi_aff as the single value may only
816
 * be defined on a subset of the domain.  Plugging in the value
817
 * would restrict the build domain to this subset, while this
818
 * restriction may not be reflected in the generated code.
819
 * Finally, we intersect build->domain with the updated bounds.
820
 * We also add the stride constraint unless we have been able
821
 * to find a fixed value expressed as a single affine expression.
822
 *
823
 * Note that the check for a fixed value in update_values requires
824
 * us to intersect the bounds with the current build domain.
825
 * When we intersect build->domain with the updated bounds in
826
 * the final step, we make sure that these updated bounds have
827
 * not been intersected with the old build->domain.
828
 * Otherwise, we would indirectly intersect the build domain with itself,
829
 * which can lead to inefficiencies, in particular if the build domain
830
 * contains any unknown divs.
831
 *
832
 * The pending and generated sets are not updated by this function to
833
 * match the updated domain.
834
 * The caller still needs to call isl_ast_build_set_pending_generated.
835
 */
836
__isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
837
  __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
838
4.06k
{
839
4.06k
  isl_set *set;
840
4.06k
841
4.06k
  build = isl_ast_build_cow(build);
842
4.06k
  if (!build)
843
0
    goto error;
844
4.06k
845
4.06k
  build = update_values(build, isl_basic_set_copy(bounds));
846
4.06k
  if (!build)
847
0
    goto error;
848
4.06k
  set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
849
4.06k
  if (isl_ast_build_has_affine_value(build, build->depth)) {
850
3.31k
    set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
851
3.31k
    set = isl_set_compute_divs(set);
852
3.31k
    build->pending = isl_set_intersect(build->pending,
853
3.31k
              isl_set_copy(set));
854
3.31k
    build->domain = isl_set_intersect(build->domain, set);
855
3.31k
  } else {
856
749
    build->domain = isl_set_intersect(build->domain, set);
857
749
    build = isl_ast_build_include_stride(build);
858
749
    if (!build)
859
0
      goto error;
860
4.06k
  }
861
4.06k
  isl_basic_set_free(bounds);
862
4.06k
863
4.06k
  if (!build->domain || !build->pending || !build->generated)
864
0
    return isl_ast_build_free(build);
865
4.06k
866
4.06k
  return build;
867
0
error:
868
0
  isl_ast_build_free(build);
869
0
  isl_basic_set_free(bounds);
870
0
  return NULL;
871
4.06k
}
872
873
/* Update the pending and generated sets of "build" according to "bounds".
874
 * If the build has an affine value at the current depth,
875
 * then isl_ast_build_set_loop_bounds has already set the pending set.
876
 * Otherwise, do it here.
877
 */
878
__isl_give isl_ast_build *isl_ast_build_set_pending_generated(
879
  __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
880
4.06k
{
881
4.06k
  isl_basic_set *generated, *pending;
882
4.06k
883
4.06k
  if (!build)
884
0
    goto error;
885
4.06k
886
4.06k
  if (isl_ast_build_has_affine_value(build, build->depth)) {
887
3.31k
    isl_basic_set_free(bounds);
888
3.31k
    return build;
889
3.31k
  }
890
749
891
749
  build = isl_ast_build_cow(build);
892
749
  if (!build)
893
0
    goto error;
894
749
895
749
  pending = isl_basic_set_copy(bounds);
896
749
  pending = isl_basic_set_drop_constraints_involving_dims(pending,
897
749
        isl_dim_set, build->depth, 1);
898
749
  build->pending = isl_set_intersect(build->pending,
899
749
        isl_set_from_basic_set(pending));
900
749
  generated = bounds;
901
749
  generated = isl_basic_set_drop_constraints_not_involving_dims(
902
749
          generated, isl_dim_set, build->depth, 1);
903
749
  build->generated = isl_set_intersect(build->generated,
904
749
        isl_set_from_basic_set(generated));
905
749
906
749
  if (!build->pending || !build->generated)
907
0
    return isl_ast_build_free(build);
908
749
909
749
  return build;
910
0
error:
911
0
  isl_ast_build_free(build);
912
0
  isl_basic_set_free(bounds);
913
0
  return NULL;
914
749
}
915
916
/* Intersect build->domain with "set", where "set" is specified
917
 * in terms of the internal schedule domain.
918
 */
919
static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
920
  __isl_take isl_ast_build *build, __isl_take isl_set *set)
921
16.8k
{
922
16.8k
  build = isl_ast_build_cow(build);
923
16.8k
  if (!build)
924
0
    goto error;
925
16.8k
926
16.8k
  set = isl_set_compute_divs(set);
927
16.8k
  build->domain = isl_set_intersect(build->domain, set);
928
16.8k
  build->domain = isl_set_coalesce(build->domain);
929
16.8k
930
16.8k
  if (!build->domain)
931
0
    return isl_ast_build_free(build);
932
16.8k
933
16.8k
  return build;
934
0
error:
935
0
  isl_ast_build_free(build);
936
0
  isl_set_free(set);
937
0
  return NULL;
938
16.8k
}
939
940
/* Intersect build->generated and build->domain with "set",
941
 * where "set" is specified in terms of the internal schedule domain.
942
 */
943
__isl_give isl_ast_build *isl_ast_build_restrict_generated(
944
  __isl_take isl_ast_build *build, __isl_take isl_set *set)
945
16.8k
{
946
16.8k
  set = isl_set_compute_divs(set);
947
16.8k
  build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
948
16.8k
  build = isl_ast_build_cow(build);
949
16.8k
  if (!build)
950
0
    goto error;
951
16.8k
952
16.8k
  build->generated = isl_set_intersect(build->generated, set);
953
16.8k
  build->generated = isl_set_coalesce(build->generated);
954
16.8k
955
16.8k
  if (!build->generated)
956
0
    return isl_ast_build_free(build);
957
16.8k
958
16.8k
  return build;
959
0
error:
960
0
  isl_ast_build_free(build);
961
0
  isl_set_free(set);
962
0
  return NULL;
963
16.8k
}
964
965
/* Replace the set of pending constraints by "guard", which is then
966
 * no longer considered as pending.
967
 * That is, add "guard" to the generated constraints and clear all pending
968
 * constraints, making the domain equal to the generated constraints.
969
 */
970
__isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(
971
  __isl_take isl_ast_build *build, __isl_take isl_set *guard)
972
7.11k
{
973
7.11k
  build = isl_ast_build_restrict_generated(build, guard);
974
7.11k
  build = isl_ast_build_cow(build);
975
7.11k
  if (!build)
976
0
    return NULL;
977
7.11k
978
7.11k
  isl_set_free(build->domain);
979
7.11k
  build->domain = isl_set_copy(build->generated);
980
7.11k
  isl_set_free(build->pending);
981
7.11k
  build->pending = isl_set_universe(isl_set_get_space(build->domain));
982
7.11k
983
7.11k
  if (!build->pending)
984
0
    return isl_ast_build_free(build);
985
7.11k
986
7.11k
  return build;
987
7.11k
}
988
989
/* Intersect build->domain with "set", where "set" is specified
990
 * in terms of the external schedule domain.
991
 */
992
__isl_give isl_ast_build *isl_ast_build_restrict(
993
  __isl_take isl_ast_build *build, __isl_take isl_set *set)
994
12
{
995
12
  if (isl_set_is_params(set))
996
0
    return isl_ast_build_restrict_generated(build, set);
997
12
998
12
  if (isl_ast_build_need_schedule_map(build)) {
999
7
    isl_multi_aff *ma;
1000
7
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
1001
7
    set = isl_set_preimage_multi_aff(set, ma);
1002
7
  }
1003
12
  return isl_ast_build_restrict_generated(build, set);
1004
12
}
1005
1006
/* Replace build->executed by "executed".
1007
 */
1008
__isl_give isl_ast_build *isl_ast_build_set_executed(
1009
  __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
1010
6.47k
{
1011
6.47k
  build = isl_ast_build_cow(build);
1012
6.47k
  if (!build)
1013
0
    goto error;
1014
6.47k
1015
6.47k
  isl_union_map_free(build->executed);
1016
6.47k
  build->executed = executed;
1017
6.47k
1018
6.47k
  return build;
1019
0
error:
1020
0
  isl_ast_build_free(build);
1021
0
  isl_union_map_free(executed);
1022
0
  return NULL;
1023
6.47k
}
1024
1025
/* Does "build" point to a band node?
1026
 * That is, are we currently handling a band node inside a schedule tree?
1027
 */
1028
int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
1029
7.14k
{
1030
7.14k
  if (!build)
1031
0
    return -1;
1032
7.14k
  return build->node != NULL;
1033
7.14k
}
1034
1035
/* Return a copy of the band node that "build" refers to.
1036
 */
1037
__isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1038
  __isl_keep isl_ast_build *build)
1039
2.33k
{
1040
2.33k
  if (!build)
1041
0
    return NULL;
1042
2.33k
  return isl_schedule_node_copy(build->node);
1043
2.33k
}
1044
1045
/* Extract the loop AST generation types for the members of build->node
1046
 * and store them in build->loop_type.
1047
 */
1048
static __isl_give isl_ast_build *extract_loop_types(
1049
  __isl_take isl_ast_build *build)
1050
653
{
1051
653
  int i;
1052
653
  isl_ctx *ctx;
1053
653
  isl_schedule_node *node;
1054
653
1055
653
  if (!build)
1056
0
    return NULL;
1057
653
  ctx = isl_ast_build_get_ctx(build);
1058
653
  if (!build->node)
1059
653
    
isl_die0
(ctx, isl_error_internal, "missing AST node",
1060
653
      return isl_ast_build_free(build));
1061
653
1062
653
  free(build->loop_type);
1063
653
  build->n = isl_schedule_node_band_n_member(build->node);
1064
653
  build->loop_type = isl_alloc_array(ctx,
1065
653
              enum isl_ast_loop_type, build->n);
1066
653
  if (build->n && !build->loop_type)
1067
0
    return isl_ast_build_free(build);
1068
653
  node = build->node;
1069
1.51k
  for (i = 0; i < build->n; 
++i861
)
1070
861
    build->loop_type[i] =
1071
861
        isl_schedule_node_band_member_get_ast_loop_type(node, i);
1072
653
1073
653
  return build;
1074
653
}
1075
1076
/* Replace the band node that "build" refers to by "node" and
1077
 * extract the corresponding loop AST generation types.
1078
 */
1079
__isl_give isl_ast_build *isl_ast_build_set_schedule_node(
1080
  __isl_take isl_ast_build *build,
1081
  __isl_take isl_schedule_node *node)
1082
653
{
1083
653
  build = isl_ast_build_cow(build);
1084
653
  if (!build || !node)
1085
0
    goto error;
1086
653
1087
653
  isl_schedule_node_free(build->node);
1088
653
  build->node = node;
1089
653
1090
653
  build = extract_loop_types(build);
1091
653
1092
653
  return build;
1093
0
error:
1094
0
  isl_ast_build_free(build);
1095
0
  isl_schedule_node_free(node);
1096
0
  return NULL;
1097
653
}
1098
1099
/* Remove any reference to a band node from "build".
1100
 */
1101
__isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
1102
  __isl_take isl_ast_build *build)
1103
2.20k
{
1104
2.20k
  build = isl_ast_build_cow(build);
1105
2.20k
  if (!build)
1106
0
    return NULL;
1107
2.20k
1108
2.20k
  isl_schedule_node_free(build->node);
1109
2.20k
  build->node = NULL;
1110
2.20k
1111
2.20k
  return build;
1112
2.20k
}
1113
1114
/* Return a copy of the current schedule domain.
1115
 */
1116
__isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
1117
8.70k
{
1118
8.70k
  return build ? isl_set_copy(build->domain) : NULL;
1119
8.70k
}
1120
1121
/* Return a copy of the set of pending constraints.
1122
 */
1123
__isl_give isl_set *isl_ast_build_get_pending(
1124
  __isl_keep isl_ast_build *build)
1125
6.30k
{
1126
6.30k
  return build ? isl_set_copy(build->pending) : NULL;
1127
6.30k
}
1128
1129
/* Return a copy of the set of generated constraints.
1130
 */
1131
__isl_give isl_set *isl_ast_build_get_generated(
1132
  __isl_keep isl_ast_build *build)
1133
7.54k
{
1134
7.54k
  return build ? isl_set_copy(build->generated) : NULL;
1135
7.54k
}
1136
1137
/* Return a copy of the map from the internal schedule domain
1138
 * to the original input schedule domain.
1139
 */
1140
__isl_give isl_multi_aff *isl_ast_build_get_internal2input(
1141
  __isl_keep isl_ast_build *build)
1142
0
{
1143
0
  return build ? isl_multi_aff_copy(build->internal2input) : NULL;
1144
0
}
1145
1146
/* Return the number of variables of the given type
1147
 * in the (internal) schedule space.
1148
 */
1149
unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build,
1150
  enum isl_dim_type type)
1151
6.05k
{
1152
6.05k
  if (!build)
1153
0
    return 0;
1154
6.05k
  return isl_set_dim(build->domain, type);
1155
6.05k
}
1156
1157
/* Return the (schedule) space of "build".
1158
 *
1159
 * If "internal" is set, then this space is the space of the internal
1160
 * representation of the entire schedule, including those parts for
1161
 * which no code has been generated yet.
1162
 *
1163
 * If "internal" is not set, then this space is the external representation
1164
 * of the loops generated so far.
1165
 */
1166
__isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
1167
  int internal)
1168
16.7k
{
1169
16.7k
  int i;
1170
16.7k
  int dim;
1171
16.7k
  isl_space *space;
1172
16.7k
1173
16.7k
  if (!build)
1174
0
    return NULL;
1175
16.7k
1176
16.7k
  space = isl_set_get_space(build->domain);
1177
16.7k
  if (internal)
1178
15.7k
    return space;
1179
1.01k
1180
1.01k
  if (!isl_ast_build_need_schedule_map(build))
1181
822
    return space;
1182
196
1183
196
  dim = isl_set_dim(build->domain, isl_dim_set);
1184
196
  space = isl_space_drop_dims(space, isl_dim_set,
1185
196
            build->depth, dim - build->depth);
1186
1.61k
  for (i = build->depth - 1; i >= 0; 
--i1.41k
) {
1187
1.41k
    isl_bool affine = isl_ast_build_has_affine_value(build, i);
1188
1.41k
1189
1.41k
    if (affine < 0)
1190
0
      return isl_space_free(space);
1191
1.41k
    if (affine)
1192
638
      space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1193
1.41k
  }
1194
196
1195
196
  return space;
1196
196
}
1197
1198
/* Return the external representation of the schedule space of "build",
1199
 * i.e., a space with a dimension for each loop generated so far,
1200
 * with the names of the dimensions set to the loop iterators.
1201
 */
1202
__isl_give isl_space *isl_ast_build_get_schedule_space(
1203
  __isl_keep isl_ast_build *build)
1204
3
{
1205
3
  isl_space *space;
1206
3
  int i, skip;
1207
3
1208
3
  if (!build)
1209
0
    return NULL;
1210
3
1211
3
  space = isl_ast_build_get_space(build, 0);
1212
3
1213
3
  skip = 0;
1214
13
  for (i = 0; i < build->depth; 
++i10
) {
1215
10
    isl_id *id;
1216
10
1217
10
    if (isl_ast_build_has_affine_value(build, i)) {
1218
5
      skip++;
1219
5
      continue;
1220
5
    }
1221
5
1222
5
    id = isl_ast_build_get_iterator_id(build, i);
1223
5
    space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
1224
5
  }
1225
3
1226
3
  return space;
1227
3
}
1228
1229
/* Return the current schedule, as stored in build->executed, in terms
1230
 * of the external schedule domain.
1231
 */
1232
__isl_give isl_union_map *isl_ast_build_get_schedule(
1233
  __isl_keep isl_ast_build *build)
1234
581
{
1235
581
  isl_union_map *executed;
1236
581
  isl_union_map *schedule;
1237
581
1238
581
  if (!build)
1239
0
    return NULL;
1240
581
1241
581
  executed = isl_union_map_copy(build->executed);
1242
581
  if (isl_ast_build_need_schedule_map(build)) {
1243
296
    isl_map *proj = isl_ast_build_get_schedule_map(build);
1244
296
    executed = isl_union_map_apply_domain(executed,
1245
296
          isl_union_map_from_map(proj));
1246
296
  }
1247
581
  schedule = isl_union_map_reverse(executed);
1248
581
1249
581
  return schedule;
1250
581
}
1251
1252
/* Return the iterator attached to the internal schedule dimension "pos".
1253
 */
1254
__isl_give isl_id *isl_ast_build_get_iterator_id(
1255
  __isl_keep isl_ast_build *build, int pos)
1256
24.2k
{
1257
24.2k
  if (!build)
1258
0
    return NULL;
1259
24.2k
1260
24.2k
  return isl_id_list_get_id(build->iterators, pos);
1261
24.2k
}
1262
1263
/* Set the stride and offset of the current dimension to the given
1264
 * value and expression.
1265
 */
1266
static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1267
  __isl_take isl_val *stride, __isl_take isl_aff *offset)
1268
15
{
1269
15
  int pos;
1270
15
1271
15
  build = isl_ast_build_cow(build);
1272
15
  if (!build || !stride || !offset)
1273
0
    goto error;
1274
15
1275
15
  pos = build->depth;
1276
15
1277
15
  build->strides = isl_vec_set_element_val(build->strides, pos, stride);
1278
15
  build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1279
15
  if (!build->strides || !build->offsets)
1280
0
    return isl_ast_build_free(build);
1281
15
1282
15
  return build;
1283
0
error:
1284
0
  isl_val_free(stride);
1285
0
  isl_aff_free(offset);
1286
0
  return isl_ast_build_free(build);
1287
15
}
1288
1289
/* Return a set expressing the stride constraint at the current depth.
1290
 *
1291
 * In particular, if the current iterator (i) is known to attain values
1292
 *
1293
 *  f + s a
1294
 *
1295
 * where f is the offset and s is the stride, then the returned set
1296
 * expresses the constraint
1297
 *
1298
 *  (f - i) mod s = 0
1299
 */
1300
__isl_give isl_set *isl_ast_build_get_stride_constraint(
1301
  __isl_keep isl_ast_build *build)
1302
39
{
1303
39
  isl_aff *aff;
1304
39
  isl_set *set;
1305
39
  isl_val *stride;
1306
39
  int pos;
1307
39
1308
39
  if (!build)
1309
0
    return NULL;
1310
39
1311
39
  pos = build->depth;
1312
39
1313
39
  if (!isl_ast_build_has_stride(build, pos))
1314
0
    return isl_set_universe(isl_ast_build_get_space(build, 1));
1315
39
1316
39
  stride = isl_ast_build_get_stride(build, pos);
1317
39
  aff = isl_ast_build_get_offset(build, pos);
1318
39
  aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1319
39
  aff = isl_aff_mod_val(aff, stride);
1320
39
  set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1321
39
1322
39
  return set;
1323
39
}
1324
1325
/* Return the expansion implied by the stride and offset at the current
1326
 * depth.
1327
 *
1328
 * That is, return the mapping
1329
 *
1330
 *  [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1331
 *    -> [i_0, ..., i_{d-1}, s * i_d + offset(i),  i_{d+1}, ...]
1332
 *
1333
 * where s is the stride at the current depth d and offset(i) is
1334
 * the corresponding offset.
1335
 */
1336
__isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1337
  __isl_keep isl_ast_build *build)
1338
2.37k
{
1339
2.37k
  isl_space *space;
1340
2.37k
  isl_multi_aff *ma;
1341
2.37k
  int pos;
1342
2.37k
  isl_aff *aff, *offset;
1343
2.37k
  isl_val *stride;
1344
2.37k
1345
2.37k
  if (!build)
1346
0
    return NULL;
1347
2.37k
1348
2.37k
  pos = isl_ast_build_get_depth(build);
1349
2.37k
  space = isl_ast_build_get_space(build, 1);
1350
2.37k
  space = isl_space_map_from_set(space);
1351
2.37k
  ma = isl_multi_aff_identity(space);
1352
2.37k
1353
2.37k
  if (!isl_ast_build_has_stride(build, pos))
1354
2.37k
    return ma;
1355
0
1356
0
  offset = isl_ast_build_get_offset(build, pos);
1357
0
  stride = isl_ast_build_get_stride(build, pos);
1358
0
  aff = isl_multi_aff_get_aff(ma, pos);
1359
0
  aff = isl_aff_scale_val(aff, stride);
1360
0
  aff = isl_aff_add(aff, offset);
1361
0
  ma = isl_multi_aff_set_aff(ma, pos, aff);
1362
0
1363
0
  return ma;
1364
0
}
1365
1366
/* Add constraints corresponding to any previously detected
1367
 * stride on the current dimension to build->domain.
1368
 */
1369
__isl_give isl_ast_build *isl_ast_build_include_stride(
1370
  __isl_take isl_ast_build *build)
1371
749
{
1372
749
  isl_set *set;
1373
749
1374
749
  if (!build)
1375
0
    return NULL;
1376
749
  if (!isl_ast_build_has_stride(build, build->depth))
1377
737
    return build;
1378
12
  build = isl_ast_build_cow(build);
1379
12
  if (!build)
1380
0
    return NULL;
1381
12
1382
12
  set = isl_ast_build_get_stride_constraint(build);
1383
12
1384
12
  build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1385
12
  build->generated = isl_set_intersect(build->generated, set);
1386
12
  if (!build->domain || !build->generated)
1387
0
    return isl_ast_build_free(build);
1388
12
1389
12
  return build;
1390
12
}
1391
1392
/* Check if the constraints in "set" imply any stride on the current
1393
 * dimension and, if so, record the stride information in "build"
1394
 * and return the updated "build".
1395
 *
1396
 * We assume that inner dimensions have been eliminated from "set"
1397
 * by the caller.  This is needed because the common stride
1398
 * may be imposed by different inner dimensions on different parts of
1399
 * the domain.
1400
 * The assumption ensures that the lower bound does not depend
1401
 * on inner dimensions.
1402
 */
1403
__isl_give isl_ast_build *isl_ast_build_detect_strides(
1404
  __isl_take isl_ast_build *build, __isl_take isl_set *set)
1405
6.43k
{
1406
6.43k
  int pos;
1407
6.43k
  isl_bool no_stride;
1408
6.43k
  isl_val *stride;
1409
6.43k
  isl_aff *offset;
1410
6.43k
  isl_stride_info *si;
1411
6.43k
1412
6.43k
  if (!build)
1413
0
    goto error;
1414
6.43k
1415
6.43k
  pos = isl_ast_build_get_depth(build);
1416
6.43k
  si = isl_set_get_stride_info(set, pos);
1417
6.43k
  stride = isl_stride_info_get_stride(si);
1418
6.43k
  offset = isl_stride_info_get_offset(si);
1419
6.43k
  isl_stride_info_free(si);
1420
6.43k
  isl_set_free(set);
1421
6.43k
1422
6.43k
  no_stride = isl_val_is_one(stride);
1423
6.43k
  if (no_stride >= 0 && !no_stride)
1424
15
    return set_stride(build, stride, offset);
1425
6.42k
  isl_val_free(stride);
1426
6.42k
  isl_aff_free(offset);
1427
6.42k
  if (no_stride < 0)
1428
0
    return isl_ast_build_free(build);
1429
6.42k
  return build;
1430
0
error:
1431
0
  isl_set_free(set);
1432
0
  return NULL;
1433
6.42k
}
1434
1435
struct isl_ast_build_involves_data {
1436
  int depth;
1437
  int involves;
1438
};
1439
1440
/* Check if "map" involves the input dimension data->depth.
1441
 */
1442
static isl_stat involves_depth(__isl_take isl_map *map, void *user)
1443
0
{
1444
0
  struct isl_ast_build_involves_data *data = user;
1445
0
1446
0
  data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1447
0
  isl_map_free(map);
1448
0
1449
0
  if (data->involves < 0 || data->involves)
1450
0
    return isl_stat_error;
1451
0
  return isl_stat_ok;
1452
0
}
1453
1454
/* Do any options depend on the value of the dimension at the current depth?
1455
 */
1456
int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1457
1
{
1458
1
  struct isl_ast_build_involves_data data;
1459
1
1460
1
  if (!build)
1461
0
    return -1;
1462
1
1463
1
  data.depth = build->depth;
1464
1
  data.involves = 0;
1465
1
1466
1
  if (isl_union_map_foreach_map(build->options,
1467
1
          &involves_depth, &data) < 0) {
1468
0
    if (data.involves < 0 || !data.involves)
1469
0
      return -1;
1470
1
  }
1471
1
1472
1
  return data.involves;
1473
1
}
1474
1475
/* Construct the map
1476
 *
1477
 *  { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1478
 *
1479
 * with "space" the parameter space of the constructed map.
1480
 */
1481
static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1482
  int pos)
1483
0
{
1484
0
  isl_constraint *c;
1485
0
  isl_basic_map *bmap1, *bmap2;
1486
0
1487
0
  space = isl_space_set_from_params(space);
1488
0
  space = isl_space_add_dims(space, isl_dim_set, 1);
1489
0
  space = isl_space_map_from_set(space);
1490
0
  c = isl_constraint_alloc_equality(isl_local_space_from_space(space));
1491
0
  c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1492
0
  c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1493
0
  bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1494
0
  c = isl_constraint_set_constant_si(c, 1);
1495
0
  bmap2 = isl_basic_map_from_constraint(c);
1496
0
1497
0
  bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1498
0
  bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1499
0
1500
0
  return isl_basic_map_union(bmap1, bmap2);
1501
0
}
1502
1503
static const char *option_str[] = {
1504
  [isl_ast_loop_atomic] = "atomic",
1505
  [isl_ast_loop_unroll] = "unroll",
1506
  [isl_ast_loop_separate] = "separate"
1507
};
1508
1509
/* Update the "options" to reflect the insertion of a dimension
1510
 * at position "pos" in the schedule domain space.
1511
 * "space" is the original domain space before the insertion and
1512
 * may be named and/or structured.
1513
 *
1514
 * The (relevant) input options all have "space" as domain, which
1515
 * has to be mapped to the extended space.
1516
 * The values of the ranges also refer to the schedule domain positions
1517
 * and they therefore also need to be adjusted.  In particular, values
1518
 * smaller than pos do not need to change, while values greater than or
1519
 * equal to pos need to be incremented.
1520
 * That is, we need to apply the following map.
1521
 *
1522
 *  { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1523
 *    unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1524
 *    separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1525
 *    separation_class[[i] -> [c]]
1526
 *    -> separation_class[[i] -> [c]] : i < pos;
1527
 *    separation_class[[i] -> [c]]
1528
 *    -> separation_class[[i + 1] -> [c]] : i >= pos }
1529
 */
1530
static __isl_give isl_union_map *options_insert_dim(
1531
  __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1532
0
{
1533
0
  isl_map *map;
1534
0
  isl_union_map *insertion;
1535
0
  enum isl_ast_loop_type type;
1536
0
  const char *name = "separation_class";
1537
0
1538
0
  space = isl_space_map_from_set(space);
1539
0
  map = isl_map_identity(space);
1540
0
  map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1541
0
  options = isl_union_map_apply_domain(options,
1542
0
            isl_union_map_from_map(map));
1543
0
1544
0
  if (!options)
1545
0
    return NULL;
1546
0
1547
0
  map = construct_insertion_map(isl_union_map_get_space(options), pos);
1548
0
1549
0
  insertion = isl_union_map_empty(isl_union_map_get_space(options));
1550
0
1551
0
  for (type = isl_ast_loop_atomic;
1552
0
      type <= isl_ast_loop_separate; ++type) {
1553
0
    isl_map *map_type = isl_map_copy(map);
1554
0
    const char *name = option_str[type];
1555
0
    map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1556
0
    map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1557
0
    insertion = isl_union_map_add_map(insertion, map_type);
1558
0
  }
1559
0
1560
0
  map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1561
0
  map = isl_map_set_tuple_name(map, isl_dim_in, name);
1562
0
  map = isl_map_set_tuple_name(map, isl_dim_out, name);
1563
0
  insertion = isl_union_map_add_map(insertion, map);
1564
0
1565
0
  options = isl_union_map_apply_range(options, insertion);
1566
0
1567
0
  return options;
1568
0
}
1569
1570
/* If we are generating an AST from a schedule tree (build->node is set),
1571
 * then update the loop AST generation types
1572
 * to reflect the insertion of a dimension at (global) position "pos"
1573
 * in the schedule domain space.
1574
 * We do not need to adjust any isolate option since we would not be inserting
1575
 * any dimensions if there were any isolate option.
1576
 */
1577
static __isl_give isl_ast_build *node_insert_dim(
1578
  __isl_take isl_ast_build *build, int pos)
1579
3
{
1580
3
  int i;
1581
3
  int local_pos;
1582
3
  enum isl_ast_loop_type *loop_type;
1583
3
  isl_ctx *ctx;
1584
3
1585
3
  build = isl_ast_build_cow(build);
1586
3
  if (!build)
1587
0
    return NULL;
1588
3
  if (!build->node)
1589
0
    return build;
1590
3
1591
3
  ctx = isl_ast_build_get_ctx(build);
1592
3
  local_pos = pos - build->outer_pos;
1593
3
  loop_type = isl_realloc_array(ctx, build->loop_type,
1594
3
          enum isl_ast_loop_type, build->n + 1);
1595
3
  if (!loop_type)
1596
0
    return isl_ast_build_free(build);
1597
3
  build->loop_type = loop_type;
1598
3
  for (i = build->n - 1; i >= local_pos; 
--i0
)
1599
0
    loop_type[i + 1] = loop_type[i];
1600
3
  loop_type[local_pos] = isl_ast_loop_default;
1601
3
  build->n++;
1602
3
1603
3
  return build;
1604
3
}
1605
1606
/* Insert a single dimension in the schedule domain at position "pos".
1607
 * The new dimension is given an isl_id with the empty string as name.
1608
 *
1609
 * The main difficulty is updating build->options to reflect the
1610
 * extra dimension.  This is handled in options_insert_dim.
1611
 *
1612
 * Note that because of the dimension manipulations, the resulting
1613
 * schedule domain space will always be unnamed and unstructured.
1614
 * However, the original schedule domain space may be named and/or
1615
 * structured, so we have to take this possibility into account
1616
 * while performing the transformations.
1617
 *
1618
 * Since the inserted schedule dimension is used by the caller
1619
 * to differentiate between different domain spaces, there is
1620
 * no longer a uniform mapping from the internal schedule space
1621
 * to the input schedule space.  The internal2input mapping is
1622
 * therefore removed.
1623
 */
1624
__isl_give isl_ast_build *isl_ast_build_insert_dim(
1625
  __isl_take isl_ast_build *build, int pos)
1626
3
{
1627
3
  isl_ctx *ctx;
1628
3
  isl_space *space, *ma_space;
1629
3
  isl_id *id;
1630
3
  isl_multi_aff *ma;
1631
3
1632
3
  build = isl_ast_build_cow(build);
1633
3
  if (!build)
1634
0
    return NULL;
1635
3
1636
3
  ctx = isl_ast_build_get_ctx(build);
1637
3
  id = isl_id_alloc(ctx, "", NULL);
1638
3
  if (!build->node)
1639
0
    space = isl_ast_build_get_space(build, 1);
1640
3
  build->iterators = isl_id_list_insert(build->iterators, pos, id);
1641
3
  build->domain = isl_set_insert_dims(build->domain,
1642
3
            isl_dim_set, pos, 1);
1643
3
  build->generated = isl_set_insert_dims(build->generated,
1644
3
            isl_dim_set, pos, 1);
1645
3
  build->pending = isl_set_insert_dims(build->pending,
1646
3
            isl_dim_set, pos, 1);
1647
3
  build->strides = isl_vec_insert_els(build->strides, pos, 1);
1648
3
  build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1649
3
  ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1650
3
  ma_space = isl_space_set_from_params(ma_space);
1651
3
  ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1652
3
  ma_space = isl_space_map_from_set(ma_space);
1653
3
  ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1654
3
  build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1655
3
  ma = isl_multi_aff_identity(ma_space);
1656
3
  build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1657
3
  if (!build->node)
1658
0
    build->options = options_insert_dim(build->options, space, pos);
1659
3
  build->internal2input = isl_multi_aff_free(build->internal2input);
1660
3
1661
3
  if (!build->iterators || !build->domain || !build->generated ||
1662
3
      !build->pending || !build->values ||
1663
3
      !build->strides || !build->offsets || !build->options)
1664
0
    return isl_ast_build_free(build);
1665
3
1666
3
  build = node_insert_dim(build, pos);
1667
3
1668
3
  return build;
1669
3
}
1670
1671
/* Scale down the current dimension by a factor of "m".
1672
 * "umap" is an isl_union_map that implements the scaling down.
1673
 * That is, it is of the form
1674
 *
1675
 *  { [.... i ....] -> [.... i' ....] : i = m i' }
1676
 *
1677
 * This function is called right after the strides have been
1678
 * detected, but before any constraints on the current dimension
1679
 * have been included in build->domain.
1680
 * We therefore only need to update stride, offset, the options and
1681
 * the mapping from internal schedule space to the original schedule
1682
 * space, if we are still keeping track of such a mapping.
1683
 * The latter mapping is updated by plugging in
1684
 * { [... i ...] -> [... m i ... ] }.
1685
 */
1686
__isl_give isl_ast_build *isl_ast_build_scale_down(
1687
  __isl_take isl_ast_build *build, __isl_take isl_val *m,
1688
  __isl_take isl_union_map *umap)
1689
0
{
1690
0
  isl_aff *aff;
1691
0
  isl_val *v;
1692
0
  int depth;
1693
0
1694
0
  build = isl_ast_build_cow(build);
1695
0
  if (!build || !umap || !m)
1696
0
    goto error;
1697
0
1698
0
  depth = build->depth;
1699
0
1700
0
  if (build->internal2input) {
1701
0
    isl_space *space;
1702
0
    isl_multi_aff *ma;
1703
0
    isl_aff *aff;
1704
0
1705
0
    space = isl_multi_aff_get_space(build->internal2input);
1706
0
    space = isl_space_map_from_set(isl_space_domain(space));
1707
0
    ma = isl_multi_aff_identity(space);
1708
0
    aff = isl_multi_aff_get_aff(ma, depth);
1709
0
    aff = isl_aff_scale_val(aff, isl_val_copy(m));
1710
0
    ma = isl_multi_aff_set_aff(ma, depth, aff);
1711
0
    build->internal2input =
1712
0
        isl_multi_aff_pullback_multi_aff(build->internal2input, ma);
1713
0
    if (!build->internal2input)
1714
0
      goto error;
1715
0
  }
1716
0
1717
0
  v = isl_vec_get_element_val(build->strides, depth);
1718
0
  v = isl_val_div(v, isl_val_copy(m));
1719
0
  build->strides = isl_vec_set_element_val(build->strides, depth, v);
1720
0
1721
0
  aff = isl_multi_aff_get_aff(build->offsets, depth);
1722
0
  aff = isl_aff_scale_down_val(aff, m);
1723
0
  build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1724
0
  build->options = isl_union_map_apply_domain(build->options, umap);
1725
0
  if (!build->strides || !build->offsets || !build->options)
1726
0
    return isl_ast_build_free(build);
1727
0
1728
0
  return build;
1729
0
error:
1730
0
  isl_val_free(m);
1731
0
  isl_union_map_free(umap);
1732
0
  return isl_ast_build_free(build);
1733
0
}
1734
1735
/* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1736
 * If an isl_id with such a name already appears among the parameters
1737
 * in build->domain, then adjust the name to "c%d_%d".
1738
 */
1739
static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1740
  __isl_keep isl_ast_build *build)
1741
681
{
1742
681
  int i;
1743
681
  isl_id_list *names;
1744
681
1745
681
  names = isl_id_list_alloc(ctx, n);
1746
1.62k
  for (i = 0; i < n; 
++i941
) {
1747
941
    isl_id *id;
1748
941
1749
941
    id = generate_name(ctx, first + i, build);
1750
941
    names = isl_id_list_add(names, id);
1751
941
  }
1752
681
1753
681
  return names;
1754
681
}
1755
1756
/* Embed "options" into the given isl_ast_build space.
1757
 *
1758
 * This function is called from within a nested call to
1759
 * isl_ast_build_node_from_schedule_map.
1760
 * "options" refers to the additional schedule,
1761
 * while space refers to both the space of the outer isl_ast_build and
1762
 * that of the additional schedule.
1763
 * Specifically, space is of the form
1764
 *
1765
 *  [I -> S]
1766
 *
1767
 * while options lives in the space(s)
1768
 *
1769
 *  S -> *
1770
 *
1771
 * We compute
1772
 *
1773
 *  [I -> S] -> S
1774
 *
1775
 * and compose this with options, to obtain the new options
1776
 * living in the space(s)
1777
 *
1778
 *  [I -> S] -> *
1779
 */
1780
static __isl_give isl_union_map *embed_options(
1781
  __isl_take isl_union_map *options, __isl_take isl_space *space)
1782
678
{
1783
678
  isl_map *map;
1784
678
1785
678
  map = isl_map_universe(isl_space_unwrap(space));
1786
678
  map = isl_map_range_map(map);
1787
678
1788
678
  options = isl_union_map_apply_range(
1789
678
        isl_union_map_from_map(map), options);
1790
678
1791
678
  return options;
1792
678
}
1793
1794
/* Update "build" for use in a (possibly nested) code generation.  That is,
1795
 * extend "build" from an AST build on some domain O to an AST build
1796
 * on domain [O -> S], with S corresponding to "space".
1797
 * If the original domain is a parameter domain, then the new domain is
1798
 * simply S.
1799
 * "iterators" is a list of iterators for S, but the number of elements
1800
 * may be smaller or greater than the number of set dimensions of S.
1801
 * If "keep_iterators" is set, then any extra ids in build->iterators
1802
 * are reused for S.  Otherwise, these extra ids are dropped.
1803
 *
1804
 * We first update build->outer_pos to the current depth.
1805
 * This depth is zero in case this is the outermost code generation.
1806
 *
1807
 * We then add additional ids such that the number of iterators is at least
1808
 * equal to the dimension of the new build domain.
1809
 *
1810
 * If the original domain is parametric, then we are constructing
1811
 * an isl_ast_build for the outer code generation and we pass control
1812
 * to isl_ast_build_init.
1813
 *
1814
 * Otherwise, we adjust the fields of "build" to include "space".
1815
 */
1816
__isl_give isl_ast_build *isl_ast_build_product(
1817
  __isl_take isl_ast_build *build, __isl_take isl_space *space)
1818
1.14k
{
1819
1.14k
  isl_ctx *ctx;
1820
1.14k
  isl_vec *strides;
1821
1.14k
  isl_set *set;
1822
1.14k
  isl_multi_aff *embedding;
1823
1.14k
  int dim, n_it;
1824
1.14k
1825
1.14k
  build = isl_ast_build_cow(build);
1826
1.14k
  if (!build)
1827
0
    goto error;
1828
1.14k
1829
1.14k
  build->outer_pos = build->depth;
1830
1.14k
1831
1.14k
  ctx = isl_ast_build_get_ctx(build);
1832
1.14k
  dim = isl_set_dim(build->domain, isl_dim_set);
1833
1.14k
  dim += isl_space_dim(space, isl_dim_set);
1834
1.14k
  n_it = isl_id_list_n_id(build->iterators);
1835
1.14k
  if (n_it < dim) {
1836
681
    isl_id_list *l;
1837
681
    l = generate_names(ctx, dim - n_it, n_it, build);
1838
681
    build->iterators = isl_id_list_concat(build->iterators, l);
1839
681
  }
1840
1.14k
1841
1.14k
  if (isl_set_is_params(build->domain))
1842
464
    return isl_ast_build_init(build, space);
1843
678
1844
678
  set = isl_set_universe(isl_space_copy(space));
1845
678
  build->domain = isl_set_product(build->domain, isl_set_copy(set));
1846
678
  build->pending = isl_set_product(build->pending, isl_set_copy(set));
1847
678
  build->generated = isl_set_product(build->generated, set);
1848
678
1849
678
  strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1850
678
  strides = isl_vec_set_si(strides, 1);
1851
678
  build->strides = isl_vec_concat(build->strides, strides);
1852
678
1853
678
  space = isl_space_map_from_set(space);
1854
678
  build->offsets = isl_multi_aff_align_params(build->offsets,
1855
678
                isl_space_copy(space));
1856
678
  build->offsets = isl_multi_aff_product(build->offsets,
1857
678
        isl_multi_aff_zero(isl_space_copy(space)));
1858
678
  build->values = isl_multi_aff_align_params(build->values,
1859
678
                isl_space_copy(space));
1860
678
  embedding = isl_multi_aff_identity(space);
1861
678
  build->values = isl_multi_aff_product(build->values,
1862
678
          isl_multi_aff_copy(embedding));
1863
678
  if (build->internal2input) {
1864
678
    build->internal2input =
1865
678
      isl_multi_aff_product(build->internal2input, embedding);
1866
678
    build->internal2input =
1867
678
      isl_multi_aff_flatten_range(build->internal2input);
1868
678
    if (!build->internal2input)
1869
0
      return isl_ast_build_free(build);
1870
0
  } else {
1871
0
    isl_multi_aff_free(embedding);
1872
0
  }
1873
678
1874
678
  space = isl_ast_build_get_space(build, 1);
1875
678
  build->options = embed_options(build->options, space);
1876
678
1877
678
  if (!build->iterators || !build->domain || !build->generated ||
1878
678
      !build->pending || !build->values ||
1879
678
      !build->strides || !build->offsets || !build->options)
1880
0
    return isl_ast_build_free(build);
1881
678
1882
678
  return build;
1883
0
error:
1884
0
  isl_ast_build_free(build);
1885
0
  isl_space_free(space);
1886
0
  return NULL;
1887
678
}
1888
1889
/* Does "aff" only attain non-negative values over build->domain?
1890
 * That is, does it not attain any negative values?
1891
 */
1892
int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
1893
  __isl_keep isl_aff *aff)
1894
153
{
1895
153
  isl_set *test;
1896
153
  int empty;
1897
153
1898
153
  if (!build)
1899
0
    return -1;
1900
153
1901
153
  aff = isl_aff_copy(aff);
1902
153
  test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
1903
153
  test = isl_set_intersect(test, isl_set_copy(build->domain));
1904
153
  empty = isl_set_is_empty(test);
1905
153
  isl_set_free(test);
1906
153
1907
153
  return empty;
1908
153
}
1909
1910
/* Does the dimension at (internal) position "pos" have a non-trivial stride?
1911
 */
1912
isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
1913
14.3k
{
1914
14.3k
  isl_val *v;
1915
14.3k
  isl_bool has_stride;
1916
14.3k
1917
14.3k
  if (!build)
1918
0
    return isl_bool_error;
1919
14.3k
1920
14.3k
  v = isl_vec_get_element_val(build->strides, pos);
1921
14.3k
  has_stride = isl_bool_not(isl_val_is_one(v));
1922
14.3k
  isl_val_free(v);
1923
14.3k
1924
14.3k
  return has_stride;
1925
14.3k
}
1926
1927
/* Given that the dimension at position "pos" takes on values
1928
 *
1929
 *  f + s a
1930
 *
1931
 * with a an integer, return s through *stride.
1932
 */
1933
__isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
1934
  int pos)
1935
78
{
1936
78
  if (!build)
1937
0
    return NULL;
1938
78
1939
78
  return isl_vec_get_element_val(build->strides, pos);
1940
78
}
1941
1942
/* Given that the dimension at position "pos" takes on values
1943
 *
1944
 *  f + s a
1945
 *
1946
 * with a an integer, return f.
1947
 */
1948
__isl_give isl_aff *isl_ast_build_get_offset(
1949
  __isl_keep isl_ast_build *build, int pos)
1950
66
{
1951
66
  if (!build)
1952
0
    return NULL;
1953
66
1954
66
  return isl_multi_aff_get_aff(build->offsets, pos);
1955
66
}
1956
1957
/* Is the dimension at position "pos" known to attain only a single
1958
 * value that, moreover, can be described by a single affine expression
1959
 * in terms of the outer dimensions and parameters?
1960
 *
1961
 * If not, then the corresponding affine expression in build->values
1962
 * is set to be equal to the same input dimension.
1963
 * Otherwise, it is set to the requested expression in terms of
1964
 * outer dimensions and parameters.
1965
 */
1966
isl_bool isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
1967
  int pos)
1968
16.1k
{
1969
16.1k
  isl_aff *aff;
1970
16.1k
  isl_bool involves;
1971
16.1k
1972
16.1k
  if (!build)
1973
0
    return isl_bool_error;
1974
16.1k
1975
16.1k
  aff = isl_multi_aff_get_aff(build->values, pos);
1976
16.1k
  involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
1977
16.1k
  isl_aff_free(aff);
1978
16.1k
1979
16.1k
  return isl_bool_not(involves);
1980
16.1k
}
1981
1982
/* Plug in the known values (fixed affine expressions in terms of
1983
 * parameters and outer loop iterators) of all loop iterators
1984
 * in the domain of "umap".
1985
 *
1986
 * We simply precompose "umap" with build->values.
1987
 */
1988
__isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
1989
  __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
1990
3.31k
{
1991
3.31k
  isl_multi_aff *values;
1992
3.31k
1993
3.31k
  if (!build)
1994
0
    return isl_union_map_free(umap);
1995
3.31k
1996
3.31k
  values = isl_multi_aff_copy(build->values);
1997
3.31k
  umap = isl_union_map_preimage_domain_multi_aff(umap, values);
1998
3.31k
1999
3.31k
  return umap;
2000
3.31k
}
2001
2002
/* Is the current dimension known to attain only a single value?
2003
 */
2004
int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
2005
4.06k
{
2006
4.06k
  if (!build)
2007
0
    return -1;
2008
4.06k
2009
4.06k
  return build->value != NULL;
2010
4.06k
}
2011
2012
/* Simplify the basic set "bset" based on what we know about
2013
 * the iterators of already generated loops.
2014
 *
2015
 * "bset" is assumed to live in the (internal) schedule domain.
2016
 */
2017
__isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
2018
  __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2019
749
{
2020
749
  if (!build)
2021
0
    goto error;
2022
749
2023
749
  bset = isl_basic_set_preimage_multi_aff(bset,
2024
749
          isl_multi_aff_copy(build->values));
2025
749
  bset = isl_basic_set_gist(bset,
2026
749
      isl_set_simple_hull(isl_set_copy(build->domain)));
2027
749
2028
749
  return bset;
2029
0
error:
2030
0
  isl_basic_set_free(bset);
2031
0
  return NULL;
2032
749
}
2033
2034
/* Simplify the set "set" based on what we know about
2035
 * the iterators of already generated loops.
2036
 *
2037
 * "set" is assumed to live in the (internal) schedule domain.
2038
 */
2039
__isl_give isl_set *isl_ast_build_compute_gist(
2040
  __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2041
617
{
2042
617
  if (!build)
2043
0
    goto error;
2044
617
2045
617
  if (!isl_set_is_params(set))
2046
23
    set = isl_set_preimage_multi_aff(set,
2047
23
          isl_multi_aff_copy(build->values));
2048
617
  set = isl_set_gist(set, isl_set_copy(build->domain));
2049
617
2050
617
  return set;
2051
0
error:
2052
0
  isl_set_free(set);
2053
0
  return NULL;
2054
617
}
2055
2056
/* Include information about what we know about the iterators of
2057
 * already generated loops to "set".
2058
 *
2059
 * We currently only plug in the known affine values of outer loop
2060
 * iterators.
2061
 * In principle we could also introduce equalities or even other
2062
 * constraints implied by the intersection of "set" and build->domain.
2063
 */
2064
__isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
2065
  __isl_take isl_set *set)
2066
10.0k
{
2067
10.0k
  if (!build)
2068
0
    return isl_set_free(set);
2069
10.0k
2070
10.0k
  return isl_set_preimage_multi_aff(set,
2071
10.0k
          isl_multi_aff_copy(build->values));
2072
10.0k
}
2073
2074
/* Plug in the known affine values of outer loop iterators in "bset".
2075
 */
2076
__isl_give isl_basic_set *isl_ast_build_specialize_basic_set(
2077
  __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2078
4.06k
{
2079
4.06k
  if (!build)
2080
0
    return isl_basic_set_free(bset);
2081
4.06k
2082
4.06k
  return isl_basic_set_preimage_multi_aff(bset,
2083
4.06k
          isl_multi_aff_copy(build->values));
2084
4.06k
}
2085
2086
/* Simplify the map "map" based on what we know about
2087
 * the iterators of already generated loops.
2088
 *
2089
 * The domain of "map" is assumed to live in the (internal) schedule domain.
2090
 */
2091
__isl_give isl_map *isl_ast_build_compute_gist_map_domain(
2092
  __isl_keep isl_ast_build *build, __isl_take isl_map *map)
2093
1.36k
{
2094
1.36k
  if (!build)
2095
0
    goto error;
2096
1.36k
2097
1.36k
  map = isl_map_gist_domain(map, isl_set_copy(build->domain));
2098
1.36k
2099
1.36k
  return map;
2100
0
error:
2101
0
  isl_map_free(map);
2102
0
  return NULL;
2103
1.36k
}
2104
2105
/* Simplify the affine expression "aff" based on what we know about
2106
 * the iterators of already generated loops.
2107
 *
2108
 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2109
 */
2110
__isl_give isl_aff *isl_ast_build_compute_gist_aff(
2111
  __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
2112
764
{
2113
764
  if (!build)
2114
0
    goto error;
2115
764
2116
764
  aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2117
764
2118
764
  return aff;
2119
0
error:
2120
0
  isl_aff_free(aff);
2121
0
  return NULL;
2122
764
}
2123
2124
/* Simplify the piecewise affine expression "aff" based on what we know about
2125
 * the iterators of already generated loops.
2126
 *
2127
 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2128
 */
2129
__isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
2130
  __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2131
11.6k
{
2132
11.6k
  if (!build)
2133
0
    goto error;
2134
11.6k
2135
11.6k
  if (!isl_set_is_params(build->domain))
2136
10.6k
    pa = isl_pw_aff_pullback_multi_aff(pa,
2137
10.6k
          isl_multi_aff_copy(build->values));
2138
11.6k
  pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2139
11.6k
2140
11.6k
  return pa;
2141
0
error:
2142
0
  isl_pw_aff_free(pa);
2143
0
  return NULL;
2144
11.6k
}
2145
2146
/* Simplify the piecewise multi-affine expression "aff" based on what
2147
 * we know about the iterators of already generated loops.
2148
 *
2149
 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2150
 */
2151
__isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
2152
  __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2153
2.23k
{
2154
2.23k
  if (!build)
2155
0
    goto error;
2156
2.23k
2157
2.23k
  pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2158
2.23k
          isl_multi_aff_copy(build->values));
2159
2.23k
  pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2160
2.23k
2161
2.23k
  return pma;
2162
0
error:
2163
0
  isl_pw_multi_aff_free(pma);
2164
0
  return NULL;
2165
2.23k
}
2166
2167
/* Extract the schedule domain of the given type from build->options
2168
 * at the current depth.
2169
 *
2170
 * In particular, find the subset of build->options that is of
2171
 * the following form
2172
 *
2173
 *  schedule_domain -> type[depth]
2174
 *
2175
 * and return the corresponding domain, after eliminating inner dimensions
2176
 * and divs that depend on the current dimension.
2177
 *
2178
 * Note that the domain of build->options has been reformulated
2179
 * in terms of the internal build space in embed_options,
2180
 * but the position is still that within the current code generation.
2181
 */
2182
__isl_give isl_set *isl_ast_build_get_option_domain(
2183
  __isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
2184
252
{
2185
252
  const char *name;
2186
252
  isl_space *space;
2187
252
  isl_map *option;
2188
252
  isl_set *domain;
2189
252
  int local_pos;
2190
252
2191
252
  if (!build)
2192
0
    return NULL;
2193
252
2194
252
  name = option_str[type];
2195
252
  local_pos = build->depth - build->outer_pos;
2196
252
2197
252
  space = isl_ast_build_get_space(build, 1);
2198
252
  space = isl_space_from_domain(space);
2199
252
  space = isl_space_add_dims(space, isl_dim_out, 1);
2200
252
  space = isl_space_set_tuple_name(space, isl_dim_out, name);
2201
252
2202
252
  option = isl_union_map_extract_map(build->options, space);
2203
252
  option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2204
252
2205
252
  domain = isl_map_domain(option);
2206
252
  domain = isl_ast_build_eliminate(build, domain);
2207
252
2208
252
  return domain;
2209
252
}
2210
2211
/* How does the user want the current schedule dimension to be generated?
2212
 * These choices have been extracted from the schedule node
2213
 * in extract_loop_types and stored in build->loop_type.
2214
 * They have been updated to reflect any dimension insertion in
2215
 * node_insert_dim.
2216
 * Return isl_ast_domain_error on error.
2217
 *
2218
 * If "isolated" is set, then we get the loop AST generation type
2219
 * directly from the band node since node_insert_dim cannot have been
2220
 * called on a band with the isolate option.
2221
 */
2222
enum isl_ast_loop_type isl_ast_build_get_loop_type(
2223
  __isl_keep isl_ast_build *build, int isolated)
2224
3.26k
{
2225
3.26k
  int local_pos;
2226
3.26k
  isl_ctx *ctx;
2227
3.26k
2228
3.26k
  if (!build)
2229
0
    return isl_ast_loop_error;
2230
3.26k
  ctx = isl_ast_build_get_ctx(build);
2231
3.26k
  if (!build->node)
2232
3.26k
    
isl_die0
(ctx, isl_error_internal,
2233
3.26k
      "only works for schedule tree based AST generation",
2234
3.26k
      return isl_ast_loop_error);
2235
3.26k
2236
3.26k
  local_pos = build->depth - build->outer_pos;
2237
3.26k
  if (!isolated)
2238
2.35k
    return build->loop_type[local_pos];
2239
917
  return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2240
917
              build->node, local_pos);
2241
917
}
2242
2243
/* Extract the isolated set from the isolate option, if any,
2244
 * and store in the build.
2245
 * If there is no isolate option, then the isolated set is
2246
 * set to the empty set.
2247
 *
2248
 * The isolate option is of the form
2249
 *
2250
 *  isolate[[outer bands] -> current_band]
2251
 *
2252
 * We flatten this set and then map it back to the internal
2253
 * schedule space.
2254
 *
2255
 * If we have already extracted the isolated set
2256
 * or if internal2input is no longer set, then we do not
2257
 * need to do anything.  In the latter case, we know
2258
 * that the current band cannot have any isolate option.
2259
 */
2260
__isl_give isl_ast_build *isl_ast_build_extract_isolated(
2261
  __isl_take isl_ast_build *build)
2262
2.46k
{
2263
2.46k
  isl_set *isolated;
2264
2.46k
2265
2.46k
  if (!build)
2266
0
    return NULL;
2267
2.46k
  if (!build->internal2input)
2268
12
    return build;
2269
2.45k
  if (build->isolated)
2270
0
    return build;
2271
2.45k
2272
2.45k
  build = isl_ast_build_cow(build);
2273
2.45k
  if (!build)
2274
0
    return NULL;
2275
2.45k
2276
2.45k
  isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);
2277
2.45k
  isolated = isl_set_flatten(isolated);
2278
2.45k
  isolated = isl_set_preimage_multi_aff(isolated,
2279
2.45k
            isl_multi_aff_copy(build->internal2input));
2280
2.45k
2281
2.45k
  build->isolated = isolated;
2282
2.45k
  if (!build->isolated)
2283
0
    return isl_ast_build_free(build);
2284
2.45k
2285
2.45k
  return build;
2286
2.45k
}
2287
2288
/* Does "build" have a non-empty isolated set?
2289
 *
2290
 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2291
 */
2292
int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
2293
2.46k
{
2294
2.46k
  int empty;
2295
2.46k
2296
2.46k
  if (!build)
2297
0
    return -1;
2298
2.46k
  if (!build->internal2input)
2299
12
    return 0;
2300
2.45k
  if (!build->isolated)
2301
2.45k
    
isl_die0
(isl_ast_build_get_ctx(build), isl_error_internal,
2302
2.45k
      "isolated set not extracted yet", return -1);
2303
2.45k
2304
2.45k
  empty = isl_set_plain_is_empty(build->isolated);
2305
2.45k
  return empty < 0 ? 
-10
: !empty;
2306
2.45k
}
2307
2308
/* Return a copy of the isolated set of "build".
2309
 *
2310
 * The caller is assume to have called isl_ast_build_has_isolated first,
2311
 * with this function returning true.
2312
 * In particular, this function should not be called if we are no
2313
 * longer keeping track of internal2input (and there therefore could
2314
 * not possibly be any isolated set).
2315
 */
2316
__isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
2317
1.48k
{
2318
1.48k
  if (!build)
2319
0
    return NULL;
2320
1.48k
  if (!build->internal2input)
2321
1.48k
    
isl_die0
(isl_ast_build_get_ctx(build), isl_error_internal,
2322
1.48k
      "build cannot have isolated set", return NULL);
2323
1.48k
2324
1.48k
  return isl_set_copy(build->isolated);
2325
1.48k
}
2326
2327
/* Extract the separation class mapping at the current depth.
2328
 *
2329
 * In particular, find and return the subset of build->options that is of
2330
 * the following form
2331
 *
2332
 *  schedule_domain -> separation_class[[depth] -> [class]]
2333
 *
2334
 * The caller is expected to eliminate inner dimensions from the domain.
2335
 *
2336
 * Note that the domain of build->options has been reformulated
2337
 * in terms of the internal build space in embed_options,
2338
 * but the position is still that within the current code generation.
2339
 */
2340
__isl_give isl_map *isl_ast_build_get_separation_class(
2341
  __isl_keep isl_ast_build *build)
2342
84
{
2343
84
  isl_ctx *ctx;
2344
84
  isl_space *space_sep, *space;
2345
84
  isl_map *res;
2346
84
  int local_pos;
2347
84
2348
84
  if (!build)
2349
0
    return NULL;
2350
84
2351
84
  local_pos = build->depth - build->outer_pos;
2352
84
  ctx = isl_ast_build_get_ctx(build);
2353
84
  space_sep = isl_space_alloc(ctx, 0, 1, 1);
2354
84
  space_sep = isl_space_wrap(space_sep);
2355
84
  space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2356
84
            "separation_class");
2357
84
  space = isl_ast_build_get_space(build, 1);
2358
84
  space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2359
84
  space = isl_space_map_from_domain_and_range(space, space_sep);
2360
84
2361
84
  res = isl_union_map_extract_map(build->options, space);
2362
84
  res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2363
84
  res = isl_map_coalesce(res);
2364
84
2365
84
  return res;
2366
84
}
2367
2368
/* Eliminate dimensions inner to the current dimension.
2369
 */
2370
__isl_give isl_set *isl_ast_build_eliminate_inner(
2371
  __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2372
10.2k
{
2373
10.2k
  int dim;
2374
10.2k
  int depth;
2375
10.2k
2376
10.2k
  if (!build)
2377
0
    return isl_set_free(set);
2378
10.2k
2379
10.2k
  dim = isl_set_dim(set, isl_dim_set);
2380
10.2k
  depth = build->depth;
2381
10.2k
  set = isl_set_detect_equalities(set);
2382
10.2k
  set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2383
10.2k
2384
10.2k
  return set;
2385
10.2k
}
2386
2387
/* Eliminate unknown divs and divs that depend on the current dimension.
2388
 *
2389
 * Note that during the elimination of unknown divs, we may discover
2390
 * an explicit representation of some other unknown divs, which may
2391
 * depend on the current dimension.  We therefore need to eliminate
2392
 * unknown divs first.
2393
 */
2394
__isl_give isl_set *isl_ast_build_eliminate_divs(
2395
  __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2396
8.56k
{
2397
8.56k
  int depth;
2398
8.56k
2399
8.56k
  if (!build)
2400
0
    return isl_set_free(set);
2401
8.56k
2402
8.56k
  set = isl_set_remove_unknown_divs(set);
2403
8.56k
  depth = build->depth;
2404
8.56k
  set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2405
8.56k
2406
8.56k
  return set;
2407
8.56k
}
2408
2409
/* Eliminate dimensions inner to the current dimension as well as
2410
 * unknown divs and divs that depend on the current dimension.
2411
 * The result then consists only of constraints that are independent
2412
 * of the current dimension and upper and lower bounds on the current
2413
 * dimension.
2414
 */
2415
__isl_give isl_set *isl_ast_build_eliminate(
2416
  __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2417
2.12k
{
2418
2.12k
  domain = isl_ast_build_eliminate_inner(build, domain);
2419
2.12k
  domain = isl_ast_build_eliminate_divs(build, domain);
2420
2.12k
  return domain;
2421
2.12k
}
2422
2423
/* Replace build->single_valued by "sv".
2424
 */
2425
__isl_give isl_ast_build *isl_ast_build_set_single_valued(
2426
  __isl_take isl_ast_build *build, int sv)
2427
489
{
2428
489
  if (!build)
2429
0
    return build;
2430
489
  if (build->single_valued == sv)
2431
467
    return build;
2432
22
  build = isl_ast_build_cow(build);
2433
22
  if (!build)
2434
0
    return build;
2435
22
  build->single_valued = sv;
2436
22
2437
22
  return build;
2438
22
}