Coverage Report

Created: 2017-06-28 17:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
2.25k
{
32
2.25k
  isl_map *map;
33
2.25k
34
2.25k
  map = isl_map_from_domain(set);
35
2.25k
  map = isl_map_add_dims(map, isl_dim_out, 1);
36
2.25k
37
2.25k
  if (!build)
38
0
    return isl_map_free(map);
39
2.25k
40
2.25k
  map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
41
2.25k
  map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
42
2.25k
43
2.25k
  return map;
44
2.25k
}
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 || 1.03k
!build->domain1.03k
)
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 || 1.03k
!build->domain1.03k
||
!build->generated1.03k
||
78
1.03k
      
!build->pending1.03k
||
!build->values1.03k
||
!build->internal2input1.03k
||
79
1.03k
      
!build->strides1.03k
||
!build->offsets1.03k
||
!build->options1.03k
)
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
826
{
95
826
  int j;
96
826
  char name[16];
97
826
  isl_set *dom = build->domain;
98
826
99
826
  snprintf(name, sizeof(name), "c%d", i);
100
826
  j = 0;
101
826
  while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
102
826
    snprintf(name, sizeof(name), "c%d_%d", i, j++);
103
826
  return isl_id_alloc(ctx, name, NULL);
104
826
}
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
588
{
114
588
  int i, n;
115
588
  isl_ctx *ctx;
116
588
  isl_space *space;
117
588
  isl_ast_build *build;
118
588
119
588
  set = isl_set_compute_divs(set);
120
588
  if (!set)
121
0
    return NULL;
122
588
123
588
  ctx = isl_set_get_ctx(set);
124
588
125
588
  build = isl_calloc_type(ctx, isl_ast_build);
126
588
  if (!build)
127
0
    goto error;
128
588
129
588
  build->ref = 1;
130
588
  build->domain = set;
131
588
  build->generated = isl_set_copy(build->domain);
132
588
  build->pending = isl_set_universe(isl_set_get_space(build->domain));
133
588
  build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
134
588
  n = isl_set_dim(set, isl_dim_set);
135
588
  build->depth = n;
136
588
  build->iterators = isl_id_list_alloc(ctx, n);
137
588
  for (i = 0; 
i < n588
;
++i0
)
{0
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
588
  space = isl_set_get_space(set);
146
588
  if (isl_space_is_params(space))
147
588
    space = isl_space_set_from_params(space);
148
588
149
588
  return isl_ast_build_init_derived(build, space);
150
0
error:
151
0
  isl_set_free(set);
152
0
  return NULL;
153
588
}
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
29.6k
{
170
29.6k
  if (!build)
171
0
    return NULL;
172
29.6k
173
29.6k
  build->ref++;
174
29.6k
  return build;
175
29.6k
}
176
177
__isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
178
21.7k
{
179
21.7k
  isl_ctx *ctx;
180
21.7k
  isl_ast_build *dup;
181
21.7k
182
21.7k
  if (!build)
183
0
    return NULL;
184
21.7k
185
21.7k
  ctx = isl_ast_build_get_ctx(build);
186
21.7k
  dup = isl_calloc_type(ctx, isl_ast_build);
187
21.7k
  if (!dup)
188
0
    return NULL;
189
21.7k
190
21.7k
  dup->ref = 1;
191
21.7k
  dup->outer_pos = build->outer_pos;
192
21.7k
  dup->depth = build->depth;
193
21.7k
  dup->iterators = isl_id_list_copy(build->iterators);
194
21.7k
  dup->domain = isl_set_copy(build->domain);
195
21.7k
  dup->generated = isl_set_copy(build->generated);
196
21.7k
  dup->pending = isl_set_copy(build->pending);
197
21.7k
  dup->values = isl_multi_aff_copy(build->values);
198
21.7k
  dup->internal2input = isl_multi_aff_copy(build->internal2input);
199
21.7k
  dup->value = isl_pw_aff_copy(build->value);
200
21.7k
  dup->strides = isl_vec_copy(build->strides);
201
21.7k
  dup->offsets = isl_multi_aff_copy(build->offsets);
202
21.7k
  dup->executed = isl_union_map_copy(build->executed);
203
21.7k
  dup->single_valued = build->single_valued;
204
21.7k
  dup->options = isl_union_map_copy(build->options);
205
21.7k
  dup->at_each_domain = build->at_each_domain;
206
21.7k
  dup->at_each_domain_user = build->at_each_domain_user;
207
21.7k
  dup->before_each_for = build->before_each_for;
208
21.7k
  dup->before_each_for_user = build->before_each_for_user;
209
21.7k
  dup->after_each_for = build->after_each_for;
210
21.7k
  dup->after_each_for_user = build->after_each_for_user;
211
21.7k
  dup->before_each_mark = build->before_each_mark;
212
21.7k
  dup->before_each_mark_user = build->before_each_mark_user;
213
21.7k
  dup->after_each_mark = build->after_each_mark;
214
21.7k
  dup->after_each_mark_user = build->after_each_mark_user;
215
21.7k
  dup->create_leaf = build->create_leaf;
216
21.7k
  dup->create_leaf_user = build->create_leaf_user;
217
21.7k
  dup->node = isl_schedule_node_copy(build->node);
218
21.7k
  if (
build->loop_type21.7k
)
{19.2k
219
19.2k
    int i;
220
19.2k
221
19.2k
    dup->n = build->n;
222
19.2k
    dup->loop_type = isl_alloc_array(ctx,
223
19.2k
            enum isl_ast_loop_type, dup->n);
224
19.2k
    if (
dup->n && 19.2k
!dup->loop_type19.2k
)
225
0
      return isl_ast_build_free(dup);
226
64.7k
    
for (i = 0; 19.2k
i < dup->n64.7k
;
++i45.5k
)
227
45.5k
      dup->loop_type[i] = build->loop_type[i];
228
19.2k
  }
229
21.7k
230
21.7k
  
if (21.7k
!dup->iterators || 21.7k
!dup->domain21.7k
||
!dup->generated21.7k
||
231
21.7k
      
!dup->pending21.7k
||
!dup->values21.7k
||
232
21.7k
      
!dup->strides21.7k
||
!dup->offsets21.7k
||
!dup->options21.7k
||
233
21.7k
      
(build->internal2input && 21.7k
!dup->internal2input21.6k
) ||
234
21.7k
      
(build->executed && 21.7k
!dup->executed18.8k
) ||
235
21.7k
      
(build->value && 21.7k
!dup->value3.12k
) ||
236
21.7k
      
(build->node && 21.7k
!dup->node13.5k
))
237
0
    return isl_ast_build_free(dup);
238
21.7k
239
21.7k
  return dup;
240
21.7k
}
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
25
{
248
25
  build = isl_ast_build_cow(build);
249
25
  if (!build)
250
0
    goto error;
251
25
252
25
  build->domain = isl_set_align_params(build->domain,
253
25
            isl_space_copy(model));
254
25
  build->generated = isl_set_align_params(build->generated,
255
25
            isl_space_copy(model));
256
25
  build->pending = isl_set_align_params(build->pending,
257
25
            isl_space_copy(model));
258
25
  build->values = isl_multi_aff_align_params(build->values,
259
25
            isl_space_copy(model));
260
25
  build->offsets = isl_multi_aff_align_params(build->offsets,
261
25
            isl_space_copy(model));
262
25
  build->options = isl_union_map_align_params(build->options,
263
25
            isl_space_copy(model));
264
25
  if (
build->internal2input25
)
{25
265
25
    build->internal2input =
266
25
      isl_multi_aff_align_params(build->internal2input,
267
25
            model);
268
25
    if (!build->internal2input)
269
0
      return isl_ast_build_free(build);
270
0
  } else {
271
0
    isl_space_free(model);
272
0
  }
273
25
274
25
  
if (25
!build->domain || 25
!build->values25
||
!build->offsets25
||
275
25
      !build->options)
276
0
    return isl_ast_build_free(build);
277
25
278
25
  return build;
279
0
error:
280
0
  isl_space_free(model);
281
0
  return NULL;
282
25
}
283
284
__isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
285
40.9k
{
286
40.9k
  if (!build)
287
0
    return NULL;
288
40.9k
289
40.9k
  
if (40.9k
build->ref == 140.9k
)
290
19.1k
    return build;
291
21.7k
  build->ref--;
292
21.7k
  return isl_ast_build_dup(build);
293
40.9k
}
294
295
__isl_null isl_ast_build *isl_ast_build_free(
296
  __isl_take isl_ast_build *build)
297
30.2k
{
298
30.2k
  if (!build)
299
0
    return NULL;
300
30.2k
301
30.2k
  
if (30.2k
--build->ref > 030.2k
)
302
7.90k
    return NULL;
303
30.2k
304
22.3k
  isl_id_list_free(build->iterators);
305
22.3k
  isl_set_free(build->domain);
306
22.3k
  isl_set_free(build->generated);
307
22.3k
  isl_set_free(build->pending);
308
22.3k
  isl_multi_aff_free(build->values);
309
22.3k
  isl_multi_aff_free(build->internal2input);
310
22.3k
  isl_pw_aff_free(build->value);
311
22.3k
  isl_vec_free(build->strides);
312
22.3k
  isl_multi_aff_free(build->offsets);
313
22.3k
  isl_multi_aff_free(build->schedule_map);
314
22.3k
  isl_union_map_free(build->executed);
315
22.3k
  isl_union_map_free(build->options);
316
22.3k
  isl_schedule_node_free(build->node);
317
22.3k
  free(build->loop_type);
318
22.3k
  isl_set_free(build->isolated);
319
22.3k
320
22.3k
  free(build);
321
22.3k
322
22.3k
  return NULL;
323
30.2k
}
324
325
isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
326
42.9k
{
327
42.9k
  return build ? isl_set_get_ctx(build->domain) : NULL;
328
42.9k
}
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 || 3
!options3
)
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 (0
n_it > dim0
)
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
445
{
389
445
  build = isl_ast_build_cow(build);
390
445
391
445
  if (!build)
392
0
    return NULL;
393
445
394
445
  build->at_each_domain = fn;
395
445
  build->at_each_domain_user = user;
396
445
397
445
  return build;
398
445
}
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
125
{
407
125
  build = isl_ast_build_cow(build);
408
125
409
125
  if (!build)
410
0
    return NULL;
411
125
412
125
  build->before_each_for = fn;
413
125
  build->before_each_for_user = user;
414
125
415
125
  return build;
416
125
}
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
125
{
425
125
  build = isl_ast_build_cow(build);
426
125
427
125
  if (!build)
428
0
    return NULL;
429
125
430
125
  build->after_each_for = fn;
431
125
  build->after_each_for_user = user;
432
125
433
125
  return build;
434
125
}
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
124
{
443
124
  build = isl_ast_build_cow(build);
444
124
445
124
  if (!build)
446
0
    return NULL;
447
124
448
124
  build->before_each_mark = fn;
449
124
  build->before_each_mark_user = user;
450
124
451
124
  return build;
452
124
}
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
124
{
461
124
  build = isl_ast_build_cow(build);
462
124
463
124
  if (!build)
464
0
    return NULL;
465
124
466
124
  build->after_each_mark = fn;
467
124
  build->after_each_mark_user = user;
468
124
469
124
  return build;
470
124
}
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
2.54k
{
531
2.54k
  int i;
532
2.54k
533
3.15k
  for (i = 0; 
i < build->depth3.15k
;
++i608
)
534
824
    
if (824
isl_ast_build_has_affine_value(build, i)824
)
535
216
      return 1;
536
2.54k
537
2.33k
  return 0;
538
2.54k
}
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
3.80k
{
548
3.80k
  if (!build)
549
0
    return;
550
3.80k
  isl_multi_aff_free(build->schedule_map);
551
3.80k
  build->schedule_map = NULL;
552
3.80k
}
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
2.66k
{
564
2.66k
  int dim;
565
2.66k
566
2.66k
  if (!build)
567
0
    return -1;
568
2.66k
569
2.66k
  dim = isl_set_dim(build->domain, isl_dim_set);
570
2.54k
  return build->depth != dim || any_eliminated(build);
571
2.66k
}
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
177
{
594
177
  isl_space *space;
595
177
  isl_multi_aff *ma;
596
177
597
177
  if (!build)
598
0
    return NULL;
599
177
  
if (177
build->schedule_map177
)
600
72
    return isl_multi_aff_copy(build->schedule_map);
601
177
602
105
  space = isl_ast_build_get_space(build, 1);
603
105
  space = isl_space_map_from_set(space);
604
105
  ma = isl_multi_aff_identity(space);
605
105
  if (
isl_ast_build_need_schedule_map(build)105
)
{105
606
105
    int i;
607
105
    int dim = isl_set_dim(build->domain, isl_dim_set);
608
105
    ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
609
105
          build->depth, dim - build->depth);
610
390
    for (i = build->depth - 1; 
i >= 0390
;
--i285
)
611
285
      
if (285
isl_ast_build_has_affine_value(build, i)285
)
612
131
        ma = isl_multi_aff_drop_dims(ma,
613
131
              isl_dim_out, i, 1);
614
105
  }
615
105
616
105
  build->schedule_map = ma;
617
105
  return isl_multi_aff_copy(build->schedule_map);
618
177
}
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
123
{
626
123
  isl_multi_aff *ma;
627
123
628
123
  ma = isl_ast_build_get_schedule_map_multi_aff(build);
629
123
  return isl_map_from_multi_aff(ma);
630
123
}
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
21.7k
{
637
21.7k
  return build ? 
build->depth21.7k
:
-10
;
638
21.7k
}
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
2.24k
{
647
2.24k
  build = isl_ast_build_cow(build);
648
2.24k
  if (!build)
649
0
    return NULL;
650
2.24k
  build->depth++;
651
2.24k
  isl_ast_build_reset_schedule_map(build);
652
2.24k
  build->value = isl_pw_aff_free(build->value);
653
2.24k
  return build;
654
2.24k
}
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->value0
)
{0
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
450
{
691
450
  isl_set *set;
692
450
693
450
  build = isl_ast_build_cow(build);
694
450
  if (!build)
695
0
    goto error;
696
450
697
450
  set = isl_set_universe(isl_space_copy(space));
698
450
  build->domain = isl_set_intersect_params(isl_set_copy(set),
699
450
                build->domain);
700
450
  build->pending = isl_set_intersect_params(isl_set_copy(set),
701
450
                build->pending);
702
450
  build->generated = isl_set_intersect_params(set, build->generated);
703
450
704
450
  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
450
}
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
1.56k
{
718
1.56k
  isl_aff **p = user;
719
1.56k
720
1.56k
  *p = aff;
721
1.56k
  isl_set_free(set);
722
1.56k
723
1.56k
  return isl_stat_error;
724
1.56k
}
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
2.24k
{
731
2.24k
  isl_set *stride;
732
2.24k
733
2.24k
  if (!build)
734
0
    return isl_set_free(set);
735
2.24k
  
if (2.24k
!isl_ast_build_has_stride(build, build->depth)2.24k
)
736
2.23k
    return set;
737
2.24k
738
14
  stride = isl_ast_build_get_stride_constraint(build);
739
14
  return isl_set_intersect(set, stride);
740
2.24k
}
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
2.24k
{
762
2.24k
  int sv;
763
2.24k
  isl_pw_multi_aff *pma;
764
2.24k
  isl_aff *aff = NULL;
765
2.24k
  isl_map *it_map;
766
2.24k
  isl_set *set;
767
2.24k
768
2.24k
  set = isl_set_from_basic_set(bounds);
769
2.24k
  set = isl_set_intersect(set, isl_set_copy(build->domain));
770
2.24k
  set = intersect_stride_constraint(set, build);
771
2.24k
  it_map = isl_ast_build_map_to_iterator(build, set);
772
2.24k
773
2.24k
  sv = isl_map_is_single_valued(it_map);
774
2.24k
  if (sv < 0)
775
0
    build = isl_ast_build_free(build);
776
2.24k
  if (
!build || 2.24k
!sv2.24k
)
{683
777
683
    isl_map_free(it_map);
778
683
    return build;
779
683
  }
780
2.24k
781
1.56k
  pma = isl_pw_multi_aff_from_map(it_map);
782
1.56k
  build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
783
1.56k
  build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
784
1.56k
  build->value = isl_pw_aff_coalesce(build->value);
785
1.56k
  isl_pw_multi_aff_free(pma);
786
1.56k
787
1.56k
  if (!build->value)
788
0
    return isl_ast_build_free(build);
789
1.56k
790
1.56k
  
if (1.56k
isl_pw_aff_n_piece(build->value) != 11.56k
)
791
0
    return build;
792
1.56k
793
1.56k
  isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
794
1.56k
795
1.56k
  build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
796
1.56k
  if (!build->values)
797
0
    return isl_ast_build_free(build);
798
1.56k
  isl_ast_build_reset_schedule_map(build);
799
1.56k
  return build;
800
1.56k
}
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
2.24k
{
836
2.24k
  isl_set *set;
837
2.24k
838
2.24k
  build = isl_ast_build_cow(build);
839
2.24k
  if (!build)
840
0
    goto error;
841
2.24k
842
2.24k
  build = update_values(build, isl_basic_set_copy(bounds));
843
2.24k
  if (!build)
844
0
    goto error;
845
2.24k
  set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
846
2.24k
  if (
isl_ast_build_has_affine_value(build, build->depth)2.24k
)
{1.56k
847
1.56k
    set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
848
1.56k
    set = isl_set_compute_divs(set);
849
1.56k
    build->pending = isl_set_intersect(build->pending,
850
1.56k
              isl_set_copy(set));
851
1.56k
    build->domain = isl_set_intersect(build->domain, set);
852
683
  } else {
853
683
    build->domain = isl_set_intersect(build->domain, set);
854
683
    build = isl_ast_build_include_stride(build);
855
683
    if (!build)
856
0
      goto error;
857
683
  }
858
2.24k
  isl_basic_set_free(bounds);
859
2.24k
860
2.24k
  if (
!build->domain || 2.24k
!build->pending2.24k
||
!build->generated2.24k
)
861
0
    return isl_ast_build_free(build);
862
2.24k
863
2.24k
  return build;
864
0
error:
865
0
  isl_ast_build_free(build);
866
0
  isl_basic_set_free(bounds);
867
0
  return NULL;
868
2.24k
}
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
2.24k
{
878
2.24k
  isl_basic_set *generated, *pending;
879
2.24k
880
2.24k
  if (!build)
881
0
    goto error;
882
2.24k
883
2.24k
  
if (2.24k
isl_ast_build_has_affine_value(build, build->depth)2.24k
)
{1.56k
884
1.56k
    isl_basic_set_free(bounds);
885
1.56k
    return build;
886
1.56k
  }
887
2.24k
888
683
  build = isl_ast_build_cow(build);
889
683
  if (!build)
890
0
    goto error;
891
683
892
683
  pending = isl_basic_set_copy(bounds);
893
683
  pending = isl_basic_set_drop_constraints_involving_dims(pending,
894
683
        isl_dim_set, build->depth, 1);
895
683
  build->pending = isl_set_intersect(build->pending,
896
683
        isl_set_from_basic_set(pending));
897
683
  generated = bounds;
898
683
  generated = isl_basic_set_drop_constraints_not_involving_dims(
899
683
          generated, isl_dim_set, build->depth, 1);
900
683
  build->generated = isl_set_intersect(build->generated,
901
683
        isl_set_from_basic_set(generated));
902
683
903
683
  if (
!build->pending || 683
!build->generated683
)
904
0
    return isl_ast_build_free(build);
905
683
906
683
  return build;
907
0
error:
908
0
  isl_ast_build_free(build);
909
0
  isl_basic_set_free(bounds);
910
0
  return NULL;
911
683
}
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
10.4k
{
919
10.4k
  build = isl_ast_build_cow(build);
920
10.4k
  if (!build)
921
0
    goto error;
922
10.4k
923
10.4k
  set = isl_set_compute_divs(set);
924
10.4k
  build->domain = isl_set_intersect(build->domain, set);
925
10.4k
  build->domain = isl_set_coalesce(build->domain);
926
10.4k
927
10.4k
  if (!build->domain)
928
0
    return isl_ast_build_free(build);
929
10.4k
930
10.4k
  return build;
931
0
error:
932
0
  isl_ast_build_free(build);
933
0
  isl_set_free(set);
934
0
  return NULL;
935
10.4k
}
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
10.4k
{
943
10.4k
  set = isl_set_compute_divs(set);
944
10.4k
  build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
945
10.4k
  build = isl_ast_build_cow(build);
946
10.4k
  if (!build)
947
0
    goto error;
948
10.4k
949
10.4k
  build->generated = isl_set_intersect(build->generated, set);
950
10.4k
  build->generated = isl_set_coalesce(build->generated);
951
10.4k
952
10.4k
  if (!build->generated)
953
0
    return isl_ast_build_free(build);
954
10.4k
955
10.4k
  return build;
956
0
error:
957
0
  isl_ast_build_free(build);
958
0
  isl_set_free(set);
959
0
  return NULL;
960
10.4k
}
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
4.29k
{
970
4.29k
  build = isl_ast_build_restrict_generated(build, guard);
971
4.29k
  build = isl_ast_build_cow(build);
972
4.29k
  if (!build)
973
0
    return NULL;
974
4.29k
975
4.29k
  isl_set_free(build->domain);
976
4.29k
  build->domain = isl_set_copy(build->generated);
977
4.29k
  isl_set_free(build->pending);
978
4.29k
  build->pending = isl_set_universe(isl_set_get_space(build->domain));
979
4.29k
980
4.29k
  if (!build->pending)
981
0
    return isl_ast_build_free(build);
982
4.29k
983
4.29k
  return build;
984
4.29k
}
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
6
{
992
6
  if (isl_set_is_params(set))
993
0
    return isl_ast_build_restrict_generated(build, set);
994
6
995
6
  
if (6
isl_ast_build_need_schedule_map(build)6
)
{4
996
4
    isl_multi_aff *ma;
997
4
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
998
4
    set = isl_set_preimage_multi_aff(set, ma);
999
4
  }
1000
6
  return isl_ast_build_restrict_generated(build, set);
1001
6
}
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
3.68k
{
1008
3.68k
  build = isl_ast_build_cow(build);
1009
3.68k
  if (!build)
1010
0
    goto error;
1011
3.68k
1012
3.68k
  isl_union_map_free(build->executed);
1013
3.68k
  build->executed = executed;
1014
3.68k
1015
3.68k
  return build;
1016
0
error:
1017
0
  isl_ast_build_free(build);
1018
0
  isl_union_map_free(executed);
1019
0
  return NULL;
1020
3.68k
}
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
4.27k
{
1027
4.27k
  if (!build)
1028
0
    return -1;
1029
4.27k
  return build->node != NULL;
1030
4.27k
}
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
1.35k
{
1037
1.35k
  if (!build)
1038
0
    return NULL;
1039
1.35k
  return isl_schedule_node_copy(build->node);
1040
1.35k
}
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
579
{
1048
579
  int i;
1049
579
  isl_ctx *ctx;
1050
579
  isl_schedule_node *node;
1051
579
1052
579
  if (!build)
1053
0
    return NULL;
1054
579
  ctx = isl_ast_build_get_ctx(build);
1055
579
  if (!build->node)
1056
0
    isl_die(ctx, isl_error_internal, "missing AST node",
1057
579
      return isl_ast_build_free(build));
1058
579
1059
579
  free(build->loop_type);
1060
579
  build->n = isl_schedule_node_band_n_member(build->node);
1061
579
  build->loop_type = isl_alloc_array(ctx,
1062
579
              enum isl_ast_loop_type, build->n);
1063
579
  if (
build->n && 579
!build->loop_type579
)
1064
0
    return isl_ast_build_free(build);
1065
579
  node = build->node;
1066
1.34k
  for (i = 0; 
i < build->n1.34k
;
++i764
)
1067
764
    build->loop_type[i] =
1068
764
        isl_schedule_node_band_member_get_ast_loop_type(node, i);
1069
579
1070
579
  return build;
1071
579
}
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
579
{
1080
579
  build = isl_ast_build_cow(build);
1081
579
  if (
!build || 579
!node579
)
1082
0
    goto error;
1083
579
1084
579
  isl_schedule_node_free(build->node);
1085
579
  build->node = node;
1086
579
1087
579
  build = extract_loop_types(build);
1088
579
1089
579
  return build;
1090
0
error:
1091
0
  isl_ast_build_free(build);
1092
0
  isl_schedule_node_free(node);
1093
0
  return NULL;
1094
579
}
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
1.28k
{
1101
1.28k
  build = isl_ast_build_cow(build);
1102
1.28k
  if (!build)
1103
0
    return NULL;
1104
1.28k
1105
1.28k
  isl_schedule_node_free(build->node);
1106
1.28k
  build->node = NULL;
1107
1.28k
1108
1.28k
  return build;
1109
1.28k
}
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
4.91k
{
1115
4.91k
  return build ? isl_set_copy(build->domain) : NULL;
1116
4.91k
}
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
3.57k
{
1123
3.57k
  return build ? isl_set_copy(build->pending) : NULL;
1124
3.57k
}
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
3.93k
{
1131
3.93k
  return build ? isl_set_copy(build->generated) : NULL;
1132
3.93k
}
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
4.00k
{
1149
4.00k
  if (!build)
1150
0
    return 0;
1151
4.00k
  return isl_set_dim(build->domain, type);
1152
4.00k
}
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
9.77k
{
1166
9.77k
  int i;
1167
9.77k
  int dim;
1168
9.77k
  isl_space *space;
1169
9.77k
1170
9.77k
  if (!build)
1171
0
    return NULL;
1172
9.77k
1173
9.77k
  space = isl_set_get_space(build->domain);
1174
9.77k
  if (internal)
1175
8.97k
    return space;
1176
9.77k
1177
804
  
if (804
!isl_ast_build_need_schedule_map(build)804
)
1178
752
    return space;
1179
804
1180
52
  dim = isl_set_dim(build->domain, isl_dim_set);
1181
52
  space = isl_space_drop_dims(space, isl_dim_set,
1182
52
            build->depth, dim - build->depth);
1183
271
  for (i = build->depth - 1; 
i >= 0271
;
--i219
)
1184
219
    
if (219
isl_ast_build_has_affine_value(build, i)219
)
1185
104
      space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1186
52
1187
52
  return space;
1188
804
}
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->depth13
;
++i10
)
{10
1207
10
    isl_id *id;
1208
10
1209
10
    if (
isl_ast_build_has_affine_value(build, i)10
)
{5
1210
5
      skip++;
1211
5
      continue;
1212
5
    }
1213
10
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
321
{
1227
321
  isl_union_map *executed;
1228
321
  isl_union_map *schedule;
1229
321
1230
321
  if (!build)
1231
0
    return NULL;
1232
321
1233
321
  executed = isl_union_map_copy(build->executed);
1234
321
  if (
isl_ast_build_need_schedule_map(build)321
)
{120
1235
120
    isl_map *proj = isl_ast_build_get_schedule_map(build);
1236
120
    executed = isl_union_map_apply_domain(executed,
1237
120
          isl_union_map_from_map(proj));
1238
120
  }
1239
321
  schedule = isl_union_map_reverse(executed);
1240
321
1241
321
  return schedule;
1242
321
}
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
11.2k
{
1249
11.2k
  if (!build)
1250
0
    return NULL;
1251
11.2k
1252
11.2k
  return isl_id_list_get_id(build->iterators, pos);
1253
11.2k
}
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 || 14
!stride14
||
!offset14
)
1289
0
    goto error;
1290
14
1291
14
  pos = build->depth;
1292
14
1293
14
  if (
isl_ast_build_has_stride(build, pos)14
)
{0
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 || 14
!build->offsets14
)
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
703
{
1374
703
  isl_space *space;
1375
703
  isl_multi_aff *ma;
1376
703
  int pos;
1377
703
  isl_aff *aff, *offset;
1378
703
  isl_val *stride;
1379
703
1380
703
  if (!build)
1381
0
    return NULL;
1382
703
1383
703
  pos = isl_ast_build_get_depth(build);
1384
703
  space = isl_ast_build_get_space(build, 1);
1385
703
  space = isl_space_map_from_set(space);
1386
703
  ma = isl_multi_aff_identity(space);
1387
703
1388
703
  if (!isl_ast_build_has_stride(build, pos))
1389
703
    return ma;
1390
703
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
703
}
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
683
{
1407
683
  isl_set *set;
1408
683
1409
683
  if (!build)
1410
0
    return NULL;
1411
683
  
if (683
!isl_ast_build_has_stride(build, build->depth)683
)
1412
672
    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 || 11
!build->generated11
)
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
2.79k
{
1474
2.79k
  struct isl_detect_stride_data *data = user;
1475
2.79k
  int i, n_div;
1476
2.79k
  isl_ctx *ctx;
1477
2.79k
  isl_val *v, *stride, *m;
1478
2.79k
1479
2.79k
  if (!isl_constraint_is_equality(c) ||
1480
2.77k
      
!isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)2.77k
)
{573
1481
573
    isl_constraint_free(c);
1482
573
    return isl_stat_ok;
1483
573
  }
1484
2.79k
1485
2.21k
  ctx = isl_constraint_get_ctx(c);
1486
2.21k
  stride = isl_val_zero(ctx);
1487
2.21k
  n_div = isl_constraint_dim(c, isl_dim_div);
1488
2.25k
  for (i = 0; 
i < n_div2.25k
;
++i38
)
{38
1489
38
    v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
1490
38
    stride = isl_val_gcd(stride, v);
1491
38
  }
1492
2.21k
1493
2.21k
  v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
1494
2.21k
  m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
1495
2.21k
  stride = isl_val_div(stride, isl_val_copy(m));
1496
2.21k
  v = isl_val_div(v, isl_val_copy(m));
1497
2.21k
1498
2.21k
  if (
!isl_val_is_zero(stride) && 2.21k
!isl_val_is_one(stride)14
)
{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_div30
;
++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
2.20k
  } else {
1516
2.20k
    isl_val_free(stride);
1517
2.20k
    isl_val_free(m);
1518
2.20k
    isl_val_free(v);
1519
2.20k
  }
1520
2.21k
1521
2.21k
  isl_constraint_free(c);
1522
2.21k
  return isl_stat_ok;
1523
2.79k
}
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
2.94k
{
1540
2.94k
  isl_basic_set *hull;
1541
2.94k
  struct isl_detect_stride_data data;
1542
2.94k
1543
2.94k
  if (!build)
1544
0
    goto error;
1545
2.94k
1546
2.94k
  data.build = build;
1547
2.94k
  data.pos = isl_ast_build_get_depth(build);
1548
2.94k
  hull = isl_set_affine_hull(set);
1549
2.94k
1550
2.94k
  if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1551
0
    data.build = isl_ast_build_free(data.build);
1552
2.94k
1553
2.94k
  isl_basic_set_free(hull);
1554
2.94k
  return data.build;
1555
0
error:
1556
0
  isl_set_free(set);
1557
0
  return NULL;
1558
2.94k
}
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 || 0
data->involves0
)
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
0
          &involves_depth, &data) < 0) {
1593
0
    if (
data.involves < 0 || 0
!data.involves0
)
1594
0
      return -1;
1595
0
  }
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_separate0
;
++type0
)
{0
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 (3
!build->node3
)
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_pos3
;
--i0
)
1724
0
    loop_type[i + 1] = loop_type[i];
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 || 3
!build->domain3
||
!build->generated3
||
1787
3
      
!build->pending3
||
!build->values3
||
1788
3
      
!build->strides3
||
!build->offsets3
||
!build->options3
)
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 || 0
!umap0
||
!m0
)
1821
0
    goto error;
1822
0
1823
0
  depth = build->depth;
1824
0
1825
0
  if (
build->internal2input0
)
{0
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 || 0
!build->offsets0
||
!build->options0
)
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
601
{
1867
601
  int i;
1868
601
  isl_id_list *names;
1869
601
1870
601
  names = isl_id_list_alloc(ctx, n);
1871
1.42k
  for (i = 0; 
i < n1.42k
;
++i826
)
{826
1872
826
    isl_id *id;
1873
826
1874
826
    id = generate_name(ctx, first + i, build);
1875
826
    names = isl_id_list_add(names, id);
1876
826
  }
1877
601
1878
601
  return names;
1879
601
}
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
598
{
1908
598
  isl_map *map;
1909
598
1910
598
  map = isl_map_universe(isl_space_unwrap(space));
1911
598
  map = isl_map_range_map(map);
1912
598
1913
598
  options = isl_union_map_apply_range(
1914
598
        isl_union_map_from_map(map), options);
1915
598
1916
598
  return options;
1917
598
}
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.04k
{
1944
1.04k
  isl_ctx *ctx;
1945
1.04k
  isl_vec *strides;
1946
1.04k
  isl_set *set;
1947
1.04k
  isl_multi_aff *embedding;
1948
1.04k
  int dim, n_it;
1949
1.04k
1950
1.04k
  build = isl_ast_build_cow(build);
1951
1.04k
  if (!build)
1952
0
    goto error;
1953
1.04k
1954
1.04k
  build->outer_pos = build->depth;
1955
1.04k
1956
1.04k
  ctx = isl_ast_build_get_ctx(build);
1957
1.04k
  dim = isl_set_dim(build->domain, isl_dim_set);
1958
1.04k
  dim += isl_space_dim(space, isl_dim_set);
1959
1.04k
  n_it = isl_id_list_n_id(build->iterators);
1960
1.04k
  if (
n_it < dim1.04k
)
{601
1961
601
    isl_id_list *l;
1962
601
    l = generate_names(ctx, dim - n_it, n_it, build);
1963
601
    build->iterators = isl_id_list_concat(build->iterators, l);
1964
601
  }
1965
1.04k
1966
1.04k
  if (isl_set_is_params(build->domain))
1967
450
    return isl_ast_build_init(build, space);
1968
1.04k
1969
598
  set = isl_set_universe(isl_space_copy(space));
1970
598
  build->domain = isl_set_product(build->domain, isl_set_copy(set));
1971
598
  build->pending = isl_set_product(build->pending, isl_set_copy(set));
1972
598
  build->generated = isl_set_product(build->generated, set);
1973
598
1974
598
  strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1975
598
  strides = isl_vec_set_si(strides, 1);
1976
598
  build->strides = isl_vec_concat(build->strides, strides);
1977
598
1978
598
  space = isl_space_map_from_set(space);
1979
598
  build->offsets = isl_multi_aff_align_params(build->offsets,
1980
598
                isl_space_copy(space));
1981
598
  build->offsets = isl_multi_aff_product(build->offsets,
1982
598
        isl_multi_aff_zero(isl_space_copy(space)));
1983
598
  build->values = isl_multi_aff_align_params(build->values,
1984
598
                isl_space_copy(space));
1985
598
  embedding = isl_multi_aff_identity(space);
1986
598
  build->values = isl_multi_aff_product(build->values,
1987
598
          isl_multi_aff_copy(embedding));
1988
598
  if (
build->internal2input598
)
{598
1989
598
    build->internal2input =
1990
598
      isl_multi_aff_product(build->internal2input, embedding);
1991
598
    build->internal2input =
1992
598
      isl_multi_aff_flatten_range(build->internal2input);
1993
598
    if (!build->internal2input)
1994
0
      return isl_ast_build_free(build);
1995
0
  } else {
1996
0
    isl_multi_aff_free(embedding);
1997
0
  }
1998
598
1999
598
  space = isl_ast_build_get_space(build, 1);
2000
598
  build->options = embed_options(build->options, space);
2001
598
2002
598
  if (
!build->iterators || 598
!build->domain598
||
!build->generated598
||
2003
598
      
!build->pending598
||
!build->values598
||
2004
598
      
!build->strides598
||
!build->offsets598
||
!build->options598
)
2005
0
    return isl_ast_build_free(build);
2006
598
2007
598
  return build;
2008
0
error:
2009
0
  isl_ast_build_free(build);
2010
0
  isl_space_free(space);
2011
0
  return NULL;
2012
598
}
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
61
{
2020
61
  isl_set *test;
2021
61
  int empty;
2022
61
2023
61
  if (!build)
2024
0
    return -1;
2025
61
2026
61
  aff = isl_aff_copy(aff);
2027
61
  test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
2028
61
  test = isl_set_intersect(test, isl_set_copy(build->domain));
2029
61
  empty = isl_set_is_empty(test);
2030
61
  isl_set_free(test);
2031
61
2032
61
  return empty;
2033
61
}
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
8.66k
{
2039
8.66k
  isl_val *v;
2040
8.66k
  isl_bool has_stride;
2041
8.66k
2042
8.66k
  if (!build)
2043
0
    return isl_bool_error;
2044
8.66k
2045
8.66k
  v = isl_vec_get_element_val(build->strides, pos);
2046
8.66k
  has_stride = isl_bool_not(isl_val_is_one(v));
2047
8.66k
  isl_val_free(v);
2048
8.66k
2049
8.66k
  return has_stride;
2050
8.66k
}
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
8.07k
{
2094
8.07k
  isl_aff *aff;
2095
8.07k
  int involves;
2096
8.07k
2097
8.07k
  if (!build)
2098
0
    return -1;
2099
8.07k
2100
8.07k
  aff = isl_multi_aff_get_aff(build->values, pos);
2101
8.07k
  involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
2102
8.07k
  isl_aff_free(aff);
2103
8.07k
2104
8.07k
  if (involves < 0)
2105
0
    return -1;
2106
8.07k
2107
8.07k
  return !involves;
2108
8.07k
}
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
1.57k
{
2119
1.57k
  isl_multi_aff *values;
2120
1.57k
2121
1.57k
  if (!build)
2122
0
    return isl_union_map_free(umap);
2123
1.57k
2124
1.57k
  values = isl_multi_aff_copy(build->values);
2125
1.57k
  umap = isl_union_map_preimage_domain_multi_aff(umap, values);
2126
1.57k
2127
1.57k
  return umap;
2128
1.57k
}
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
2.24k
{
2134
2.24k
  if (!build)
2135
0
    return -1;
2136
2.24k
2137
2.24k
  return build->value != NULL;
2138
2.24k
}
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
683
{
2148
683
  if (!build)
2149
0
    goto error;
2150
683
2151
683
  bset = isl_basic_set_preimage_multi_aff(bset,
2152
683
          isl_multi_aff_copy(build->values));
2153
683
  bset = isl_basic_set_gist(bset,
2154
683
      isl_set_simple_hull(isl_set_copy(build->domain)));
2155
683
2156
683
  return bset;
2157
0
error:
2158
0
  isl_basic_set_free(bset);
2159
0
  return NULL;
2160
683
}
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
617
{
2170
617
  if (!build)
2171
0
    goto error;
2172
617
2173
617
  
if (617
!isl_set_is_params(set)617
)
2174
17
    set = isl_set_preimage_multi_aff(set,
2175
17
          isl_multi_aff_copy(build->values));
2176
617
  set = isl_set_gist(set, isl_set_copy(build->domain));
2177
617
2178
617
  return set;
2179
0
error:
2180
0
  isl_set_free(set);
2181
0
  return NULL;
2182
617
}
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
5.13k
{
2195
5.13k
  if (!build)
2196
0
    return isl_set_free(set);
2197
5.13k
2198
5.13k
  return isl_set_preimage_multi_aff(set,
2199
5.13k
          isl_multi_aff_copy(build->values));
2200
5.13k
}
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
2.24k
{
2207
2.24k
  if (!build)
2208
0
    return isl_basic_set_free(bset);
2209
2.24k
2210
2.24k
  return isl_basic_set_preimage_multi_aff(bset,
2211
2.24k
          isl_multi_aff_copy(build->values));
2212
2.24k
}
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
42
{
2222
42
  if (!build)
2223
0
    goto error;
2224
42
2225
42
  map = isl_map_gist_domain(map, isl_set_copy(build->domain));
2226
42
2227
42
  return map;
2228
0
error:
2229
0
  isl_map_free(map);
2230
0
  return NULL;
2231
42
}
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
691
{
2241
691
  if (!build)
2242
0
    goto error;
2243
691
2244
691
  aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2245
691
2246
691
  return aff;
2247
0
error:
2248
0
  isl_aff_free(aff);
2249
0
  return NULL;
2250
691
}
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
6.67k
{
2260
6.67k
  if (!build)
2261
0
    goto error;
2262
6.67k
2263
6.67k
  
if (6.67k
!isl_set_is_params(build->domain)6.67k
)
2264
5.77k
    pa = isl_pw_aff_pullback_multi_aff(pa,
2265
5.77k
          isl_multi_aff_copy(build->values));
2266
6.67k
  pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2267
6.67k
2268
6.67k
  return pa;
2269
0
error:
2270
0
  isl_pw_aff_free(pa);
2271
0
  return NULL;
2272
6.67k
}
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
1.32k
{
2282
1.32k
  if (!build)
2283
0
    goto error;
2284
1.32k
2285
1.32k
  pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2286
1.32k
          isl_multi_aff_copy(build->values));
2287
1.32k
  pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2288
1.32k
2289
1.32k
  return pma;
2290
0
error:
2291
0
  isl_pw_multi_aff_free(pma);
2292
0
  return NULL;
2293
1.32k
}
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
198
{
2313
198
  const char *name;
2314
198
  isl_space *space;
2315
198
  isl_map *option;
2316
198
  isl_set *domain;
2317
198
  int local_pos;
2318
198
2319
198
  if (!build)
2320
0
    return NULL;
2321
198
2322
198
  name = option_str[type];
2323
198
  local_pos = build->depth - build->outer_pos;
2324
198
2325
198
  space = isl_ast_build_get_space(build, 1);
2326
198
  space = isl_space_from_domain(space);
2327
198
  space = isl_space_add_dims(space, isl_dim_out, 1);
2328
198
  space = isl_space_set_tuple_name(space, isl_dim_out, name);
2329
198
2330
198
  option = isl_union_map_extract_map(build->options, space);
2331
198
  option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2332
198
2333
198
  domain = isl_map_domain(option);
2334
198
  domain = isl_ast_build_eliminate(build, domain);
2335
198
2336
198
  return domain;
2337
198
}
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
1.99k
{
2353
1.99k
  int local_pos;
2354
1.99k
  isl_ctx *ctx;
2355
1.99k
2356
1.99k
  if (!build)
2357
0
    return isl_ast_loop_error;
2358
1.99k
  ctx = isl_ast_build_get_ctx(build);
2359
1.99k
  if (!build->node)
2360
0
    isl_die(ctx, isl_error_internal,
2361
1.99k
      "only works for schedule tree based AST generation",
2362
1.99k
      return isl_ast_loop_error);
2363
1.99k
2364
1.99k
  local_pos = build->depth - build->outer_pos;
2365
1.99k
  if (!isolated)
2366
1.43k
    return build->loop_type[local_pos];
2367
566
  return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2368
566
              build->node, local_pos);
2369
1.99k
}
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
1.50k
{
2391
1.50k
  isl_set *isolated;
2392
1.50k
2393
1.50k
  if (!build)
2394
0
    return NULL;
2395
1.50k
  
if (1.50k
!build->internal2input1.50k
)
2396
12
    return build;
2397
1.49k
  
if (1.49k
build->isolated1.49k
)
2398
0
    return build;
2399
1.49k
2400
1.49k
  build = isl_ast_build_cow(build);
2401
1.49k
  if (!build)
2402
0
    return NULL;
2403
1.49k
2404
1.49k
  isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);
2405
1.49k
  isolated = isl_set_flatten(isolated);
2406
1.49k
  isolated = isl_set_preimage_multi_aff(isolated,
2407
1.49k
            isl_multi_aff_copy(build->internal2input));
2408
1.49k
2409
1.49k
  build->isolated = isolated;
2410
1.49k
  if (!build->isolated)
2411
0
    return isl_ast_build_free(build);
2412
1.49k
2413
1.49k
  return build;
2414
1.49k
}
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
1.50k
{
2422
1.50k
  int empty;
2423
1.50k
2424
1.50k
  if (!build)
2425
0
    return -1;
2426
1.50k
  
if (1.50k
!build->internal2input1.50k
)
2427
12
    return 0;
2428
1.49k
  
if (1.49k
!build->isolated1.49k
)
2429
0
    isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2430
1.49k
      "isolated set not extracted yet", return -1);
2431
1.49k
2432
1.49k
  empty = isl_set_plain_is_empty(build->isolated);
2433
1.49k
  return empty < 0 ? 
-10
:
!empty1.49k
;
2434
1.49k
}
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
580
{
2446
580
  if (!build)
2447
0
    return NULL;
2448
580
  
if (580
!build->internal2input580
)
2449
0
    isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2450
580
      "build cannot have isolated set", return NULL);
2451
580
2452
580
  return isl_set_copy(build->isolated);
2453
580
}
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
66
{
2471
66
  isl_ctx *ctx;
2472
66
  isl_space *space_sep, *space;
2473
66
  isl_map *res;
2474
66
  int local_pos;
2475
66
2476
66
  if (!build)
2477
0
    return NULL;
2478
66
2479
66
  local_pos = build->depth - build->outer_pos;
2480
66
  ctx = isl_ast_build_get_ctx(build);
2481
66
  space_sep = isl_space_alloc(ctx, 0, 1, 1);
2482
66
  space_sep = isl_space_wrap(space_sep);
2483
66
  space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2484
66
            "separation_class");
2485
66
  space = isl_ast_build_get_space(build, 1);
2486
66
  space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2487
66
  space = isl_space_map_from_domain_and_range(space, space_sep);
2488
66
2489
66
  res = isl_union_map_extract_map(build->options, space);
2490
66
  res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2491
66
  res = isl_map_coalesce(res);
2492
66
2493
66
  return res;
2494
66
}
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
5.71k
{
2501
5.71k
  int dim;
2502
5.71k
  int depth;
2503
5.71k
2504
5.71k
  if (!build)
2505
0
    return isl_set_free(set);
2506
5.71k
2507
5.71k
  dim = isl_set_dim(set, isl_dim_set);
2508
5.71k
  depth = build->depth;
2509
5.71k
  set = isl_set_detect_equalities(set);
2510
5.71k
  set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2511
5.71k
2512
5.71k
  return set;
2513
5.71k
}
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
5.07k
{
2525
5.07k
  int depth;
2526
5.07k
2527
5.07k
  if (!build)
2528
0
    return isl_set_free(set);
2529
5.07k
2530
5.07k
  set = isl_set_remove_unknown_divs(set);
2531
5.07k
  depth = build->depth;
2532
5.07k
  set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2533
5.07k
2534
5.07k
  return set;
2535
5.07k
}
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.12k
{
2546
2.12k
  domain = isl_ast_build_eliminate_inner(build, domain);
2547
2.12k
  domain = isl_ast_build_eliminate_divs(build, domain);
2548
2.12k
  return domain;
2549
2.12k
}
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
469
{
2556
469
  if (!build)
2557
0
    return build;
2558
469
  
if (469
build->single_valued == sv469
)
2559
453
    return build;
2560
16
  build = isl_ast_build_cow(build);
2561
16
  if (!build)
2562
0
    return build;
2563
16
  build->single_valued = sv;
2564
16
2565
16
  return build;
2566
16
}