Coverage Report

Created: 2017-11-23 03:11

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