Coverage Report

Created: 2018-02-20 12:54

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