Coverage Report

Created: 2017-03-24 03:18

/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
1.91k
{
32
1.91k
  isl_map *map;
33
1.91k
34
1.91k
  map = isl_map_from_domain(set);
35
1.91k
  map = isl_map_add_dims(map, isl_dim_out, 1);
36
1.91k
37
1.91k
  if (!build)
38
0
    return isl_map_free(map);
39
1.91k
40
1.91k
  map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
41
1.91k
  map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
42
1.91k
43
1.91k
  return map;
44
1.91k
}
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
960
{
55
960
  isl_ctx *ctx;
56
960
  isl_vec *strides;
57
960
58
960
  build = isl_ast_build_cow(build);
59
960
  if (
!build || 960
!build->domain960
)
60
0
    goto error;
61
960
62
960
  ctx = isl_ast_build_get_ctx(build);
63
960
  strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
64
960
  strides = isl_vec_set_si(strides, 1);
65
960
66
960
  isl_vec_free(build->strides);
67
960
  build->strides = strides;
68
960
69
960
  space = isl_space_map_from_set(space);
70
960
  isl_multi_aff_free(build->offsets);
71
960
  build->offsets = isl_multi_aff_zero(isl_space_copy(space));
72
960
  isl_multi_aff_free(build->values);
73
960
  build->values = isl_multi_aff_identity(isl_space_copy(space));
74
960
  isl_multi_aff_free(build->internal2input);
75
960
  build->internal2input = isl_multi_aff_identity(space);
76
960
77
960
  if (
!build->iterators || 960
!build->domain960
||
!build->generated960
||
78
960
      
!build->pending960
||
!build->values960
||
!build->internal2input960
||
79
960
      
!build->strides960
||
!build->offsets960
||
!build->options960
)
80
0
    return isl_ast_build_free(build);
81
960
82
960
  return build;
83
0
error:
84
0
  isl_space_free(space);
85
0
  return isl_ast_build_free(build);
86
960
}
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
756
{
95
756
  int j;
96
756
  char name[16];
97
756
  isl_set *dom = build->domain;
98
756
99
756
  snprintf(name, sizeof(name), "c%d", i);
100
756
  j = 0;
101
756
  while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
102
756
    snprintf(name, sizeof(name), "c%d_%d", i, j++);
103
756
  return isl_id_alloc(ctx, name, NULL);
104
756
}
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
548
{
114
548
  int i, n;
115
548
  isl_ctx *ctx;
116
548
  isl_space *space;
117
548
  isl_ast_build *build;
118
548
119
548
  set = isl_set_compute_divs(set);
120
548
  if (!set)
121
0
    return NULL;
122
548
123
548
  ctx = isl_set_get_ctx(set);
124
548
125
548
  build = isl_calloc_type(ctx, isl_ast_build);
126
548
  if (!build)
127
0
    goto error;
128
548
129
548
  build->ref = 1;
130
548
  build->domain = set;
131
548
  build->generated = isl_set_copy(build->domain);
132
548
  build->pending = isl_set_universe(isl_set_get_space(build->domain));
133
548
  build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
134
548
  n = isl_set_dim(set, isl_dim_set);
135
548
  build->depth = n;
136
548
  build->iterators = isl_id_list_alloc(ctx, n);
137
548
  for (i = 0; 
i < n548
;
++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
548
  space = isl_set_get_space(set);
146
548
  if (isl_space_is_params(space))
147
548
    space = isl_space_set_from_params(space);
148
548
149
548
  return isl_ast_build_init_derived(build, space);
150
0
error:
151
0
  isl_set_free(set);
152
0
  return NULL;
153
548
}
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
25.9k
{
170
25.9k
  if (!build)
171
0
    return NULL;
172
25.9k
173
25.9k
  build->ref++;
174
25.9k
  return build;
175
25.9k
}
176
177
__isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
178
18.7k
{
179
18.7k
  isl_ctx *ctx;
180
18.7k
  isl_ast_build *dup;
181
18.7k
182
18.7k
  if (!build)
183
0
    return NULL;
184
18.7k
185
18.7k
  ctx = isl_ast_build_get_ctx(build);
186
18.7k
  dup = isl_calloc_type(ctx, isl_ast_build);
187
18.7k
  if (!dup)
188
0
    return NULL;
189
18.7k
190
18.7k
  dup->ref = 1;
191
18.7k
  dup->outer_pos = build->outer_pos;
192
18.7k
  dup->depth = build->depth;
193
18.7k
  dup->iterators = isl_id_list_copy(build->iterators);
194
18.7k
  dup->domain = isl_set_copy(build->domain);
195
18.7k
  dup->generated = isl_set_copy(build->generated);
196
18.7k
  dup->pending = isl_set_copy(build->pending);
197
18.7k
  dup->values = isl_multi_aff_copy(build->values);
198
18.7k
  dup->internal2input = isl_multi_aff_copy(build->internal2input);
199
18.7k
  dup->value = isl_pw_aff_copy(build->value);
200
18.7k
  dup->strides = isl_vec_copy(build->strides);
201
18.7k
  dup->offsets = isl_multi_aff_copy(build->offsets);
202
18.7k
  dup->executed = isl_union_map_copy(build->executed);
203
18.7k
  dup->single_valued = build->single_valued;
204
18.7k
  dup->options = isl_union_map_copy(build->options);
205
18.7k
  dup->at_each_domain = build->at_each_domain;
206
18.7k
  dup->at_each_domain_user = build->at_each_domain_user;
207
18.7k
  dup->before_each_for = build->before_each_for;
208
18.7k
  dup->before_each_for_user = build->before_each_for_user;
209
18.7k
  dup->after_each_for = build->after_each_for;
210
18.7k
  dup->after_each_for_user = build->after_each_for_user;
211
18.7k
  dup->before_each_mark = build->before_each_mark;
212
18.7k
  dup->before_each_mark_user = build->before_each_mark_user;
213
18.7k
  dup->after_each_mark = build->after_each_mark;
214
18.7k
  dup->after_each_mark_user = build->after_each_mark_user;
215
18.7k
  dup->create_leaf = build->create_leaf;
216
18.7k
  dup->create_leaf_user = build->create_leaf_user;
217
18.7k
  dup->node = isl_schedule_node_copy(build->node);
218
18.7k
  if (
build->loop_type18.7k
)
{16.4k
219
16.4k
    int i;
220
16.4k
221
16.4k
    dup->n = build->n;
222
16.4k
    dup->loop_type = isl_alloc_array(ctx,
223
16.4k
            enum isl_ast_loop_type, dup->n);
224
16.4k
    if (
dup->n && 16.4k
!dup->loop_type16.4k
)
225
0
      return isl_ast_build_free(dup);
226
54.6k
    
for (i = 0; 16.4k
i < dup->n54.6k
;
++i38.1k
)
227
38.1k
      dup->loop_type[i] = build->loop_type[i];
228
16.4k
  }
229
18.7k
230
18.7k
  
if (18.7k
!dup->iterators || 18.7k
!dup->domain18.7k
||
!dup->generated18.7k
||
231
18.7k
      
!dup->pending18.7k
||
!dup->values18.7k
||
232
18.7k
      
!dup->strides18.7k
||
!dup->offsets18.7k
||
!dup->options18.7k
||
233
18.7k
      
(build->internal2input && 18.7k
!dup->internal2input18.6k
) ||
234
18.7k
      
(build->executed && 18.7k
!dup->executed16.1k
) ||
235
18.7k
      
(build->value && 18.7k
!dup->value2.54k
) ||
236
18.7k
      
(build->node && 18.7k
!dup->node11.6k
))
237
0
    return isl_ast_build_free(dup);
238
18.7k
239
18.7k
  return dup;
240
18.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
35.7k
{
286
35.7k
  if (!build)
287
0
    return NULL;
288
35.7k
289
35.7k
  
if (35.7k
build->ref == 135.7k
)
290
16.9k
    return build;
291
18.7k
  build->ref--;
292
18.7k
  return isl_ast_build_dup(build);
293
35.7k
}
294
295
__isl_null isl_ast_build *isl_ast_build_free(
296
  __isl_take isl_ast_build *build)
297
26.4k
{
298
26.4k
  if (!build)
299
0
    return NULL;
300
26.4k
301
26.4k
  
if (26.4k
--build->ref > 026.4k
)
302
7.11k
    return NULL;
303
26.4k
304
19.3k
  isl_id_list_free(build->iterators);
305
19.3k
  isl_set_free(build->domain);
306
19.3k
  isl_set_free(build->generated);
307
19.3k
  isl_set_free(build->pending);
308
19.3k
  isl_multi_aff_free(build->values);
309
19.3k
  isl_multi_aff_free(build->internal2input);
310
19.3k
  isl_pw_aff_free(build->value);
311
19.3k
  isl_vec_free(build->strides);
312
19.3k
  isl_multi_aff_free(build->offsets);
313
19.3k
  isl_multi_aff_free(build->schedule_map);
314
19.3k
  isl_union_map_free(build->executed);
315
19.3k
  isl_union_map_free(build->options);
316
19.3k
  isl_schedule_node_free(build->node);
317
19.3k
  free(build->loop_type);
318
19.3k
  isl_set_free(build->isolated);
319
19.3k
320
19.3k
  free(build);
321
19.3k
322
19.3k
  return NULL;
323
26.4k
}
324
325
isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
326
37.6k
{
327
37.6k
  return build ? isl_set_get_ctx(build->domain) : NULL;
328
37.6k
}
329
330
/* Replace build->options by "options".
331
 */
332
__isl_give isl_ast_build *isl_ast_build_set_options(
333
  __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
334
3
{
335
3
  build = isl_ast_build_cow(build);
336
3
337
3
  if (
!build || 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
407
{
389
407
  build = isl_ast_build_cow(build);
390
407
391
407
  if (!build)
392
0
    return NULL;
393
407
394
407
  build->at_each_domain = fn;
395
407
  build->at_each_domain_user = user;
396
407
397
407
  return build;
398
407
}
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
108
{
407
108
  build = isl_ast_build_cow(build);
408
108
409
108
  if (!build)
410
0
    return NULL;
411
108
412
108
  build->before_each_for = fn;
413
108
  build->before_each_for_user = user;
414
108
415
108
  return build;
416
108
}
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
108
{
425
108
  build = isl_ast_build_cow(build);
426
108
427
108
  if (!build)
428
0
    return NULL;
429
108
430
108
  build->after_each_for = fn;
431
108
  build->after_each_for_user = user;
432
108
433
108
  return build;
434
108
}
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
107
{
443
107
  build = isl_ast_build_cow(build);
444
107
445
107
  if (!build)
446
0
    return NULL;
447
107
448
107
  build->before_each_mark = fn;
449
107
  build->before_each_mark_user = user;
450
107
451
107
  return build;
452
107
}
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
107
{
461
107
  build = isl_ast_build_cow(build);
462
107
463
107
  if (!build)
464
0
    return NULL;
465
107
466
107
  build->after_each_mark = fn;
467
107
  build->after_each_mark_user = user;
468
107
469
107
  return build;
470
107
}
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.31k
{
531
2.31k
  int i;
532
2.31k
533
2.85k
  for (i = 0; 
i < build->depth2.85k
;
++i531
)
534
703
    
if (703
isl_ast_build_has_affine_value(build, i)703
)
535
172
      return 1;
536
2.31k
537
2.14k
  return 0;
538
2.31k
}
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.17k
{
548
3.17k
  if (!build)
549
0
    return;
550
3.17k
  isl_multi_aff_free(build->schedule_map);
551
3.17k
  build->schedule_map = NULL;
552
3.17k
}
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.40k
{
564
2.40k
  int dim;
565
2.40k
566
2.40k
  if (!build)
567
0
    return -1;
568
2.40k
569
2.40k
  dim = isl_set_dim(build->domain, isl_dim_set);
570
2.31k
  return build->depth != dim || any_eliminated(build);
571
2.40k
}
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
138
{
594
138
  isl_space *space;
595
138
  isl_multi_aff *ma;
596
138
597
138
  if (!build)
598
0
    return NULL;
599
138
  
if (138
build->schedule_map138
)
600
57
    return isl_multi_aff_copy(build->schedule_map);
601
138
602
81
  space = isl_ast_build_get_space(build, 1);
603
81
  space = isl_space_map_from_set(space);
604
81
  ma = isl_multi_aff_identity(space);
605
81
  if (
isl_ast_build_need_schedule_map(build)81
)
{81
606
81
    int i;
607
81
    int dim = isl_set_dim(build->domain, isl_dim_set);
608
81
    ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
609
81
          build->depth, dim - build->depth);
610
319
    for (i = build->depth - 1; 
i >= 0319
;
--i238
)
611
238
      
if (238
isl_ast_build_has_affine_value(build, i)238
)
612
108
        ma = isl_multi_aff_drop_dims(ma,
613
108
              isl_dim_out, i, 1);
614
81
  }
615
81
616
81
  build->schedule_map = ma;
617
81
  return isl_multi_aff_copy(build->schedule_map);
618
138
}
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
99
{
626
99
  isl_multi_aff *ma;
627
99
628
99
  ma = isl_ast_build_get_schedule_map_multi_aff(build);
629
99
  return isl_map_from_multi_aff(ma);
630
99
}
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
18.7k
{
637
18.7k
  return build ? 
build->depth18.7k
:
-10
;
638
18.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
1.90k
{
647
1.90k
  build = isl_ast_build_cow(build);
648
1.90k
  if (!build)
649
0
    return NULL;
650
1.90k
  build->depth++;
651
1.90k
  isl_ast_build_reset_schedule_map(build);
652
1.90k
  build->value = isl_pw_aff_free(build->value);
653
1.90k
  return build;
654
1.90k
}
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
412
{
691
412
  isl_set *set;
692
412
693
412
  build = isl_ast_build_cow(build);
694
412
  if (!build)
695
0
    goto error;
696
412
697
412
  set = isl_set_universe(isl_space_copy(space));
698
412
  build->domain = isl_set_intersect_params(isl_set_copy(set),
699
412
                build->domain);
700
412
  build->pending = isl_set_intersect_params(isl_set_copy(set),
701
412
                build->pending);
702
412
  build->generated = isl_set_intersect_params(set, build->generated);
703
412
704
412
  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
412
}
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.27k
{
718
1.27k
  isl_aff **p = user;
719
1.27k
720
1.27k
  *p = aff;
721
1.27k
  isl_set_free(set);
722
1.27k
723
1.27k
  return isl_stat_error;
724
1.27k
}
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
1.90k
{
731
1.90k
  isl_set *stride;
732
1.90k
733
1.90k
  if (!build)
734
0
    return isl_set_free(set);
735
1.90k
  
if (1.90k
!isl_ast_build_has_stride(build, build->depth)1.90k
)
736
1.88k
    return set;
737
1.90k
738
14
  stride = isl_ast_build_get_stride_constraint(build);
739
14
  return isl_set_intersect(set, stride);
740
1.90k
}
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
1.90k
{
762
1.90k
  int sv;
763
1.90k
  isl_pw_multi_aff *pma;
764
1.90k
  isl_aff *aff = NULL;
765
1.90k
  isl_map *it_map;
766
1.90k
  isl_set *set;
767
1.90k
768
1.90k
  set = isl_set_from_basic_set(bounds);
769
1.90k
  set = isl_set_intersect(set, isl_set_copy(build->domain));
770
1.90k
  set = intersect_stride_constraint(set, build);
771
1.90k
  it_map = isl_ast_build_map_to_iterator(build, set);
772
1.90k
773
1.90k
  sv = isl_map_is_single_valued(it_map);
774
1.90k
  if (sv < 0)
775
0
    build = isl_ast_build_free(build);
776
1.90k
  if (
!build || 1.90k
!sv1.90k
)
{627
777
627
    isl_map_free(it_map);
778
627
    return build;
779
627
  }
780
1.90k
781
1.27k
  pma = isl_pw_multi_aff_from_map(it_map);
782
1.27k
  build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
783
1.27k
  build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
784
1.27k
  build->value = isl_pw_aff_coalesce(build->value);
785
1.27k
  isl_pw_multi_aff_free(pma);
786
1.27k
787
1.27k
  if (!build->value)
788
0
    return isl_ast_build_free(build);
789
1.27k
790
1.27k
  
if (1.27k
isl_pw_aff_n_piece(build->value) != 11.27k
)
791
0
    return build;
792
1.27k
793
1.27k
  isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
794
1.27k
795
1.27k
  build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
796
1.27k
  if (!build->values)
797
0
    return isl_ast_build_free(build);
798
1.27k
  isl_ast_build_reset_schedule_map(build);
799
1.27k
  return build;
800
1.27k
}
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
1.90k
{
836
1.90k
  isl_set *set;
837
1.90k
838
1.90k
  build = isl_ast_build_cow(build);
839
1.90k
  if (!build)
840
0
    goto error;
841
1.90k
842
1.90k
  build = update_values(build, isl_basic_set_copy(bounds));
843
1.90k
  if (!build)
844
0
    goto error;
845
1.90k
  set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
846
1.90k
  if (
isl_ast_build_has_affine_value(build, build->depth)1.90k
)
{1.27k
847
1.27k
    set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
848
1.27k
    set = isl_set_compute_divs(set);
849
1.27k
    build->pending = isl_set_intersect(build->pending,
850
1.27k
              isl_set_copy(set));
851
1.27k
    build->domain = isl_set_intersect(build->domain, set);
852
627
  } else {
853
627
    build->domain = isl_set_intersect(build->domain, set);
854
627
    build = isl_ast_build_include_stride(build);
855
627
    if (!build)
856
0
      goto error;
857
627
  }
858
1.90k
  isl_basic_set_free(bounds);
859
1.90k
860
1.90k
  if (
!build->domain || 1.90k
!build->pending1.90k
||
!build->generated1.90k
)
861
0
    return isl_ast_build_free(build);
862
1.90k
863
1.90k
  return build;
864
0
error:
865
0
  isl_ast_build_free(build);
866
0
  isl_basic_set_free(bounds);
867
0
  return NULL;
868
1.90k
}
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
1.90k
{
878
1.90k
  isl_basic_set *generated, *pending;
879
1.90k
880
1.90k
  if (!build)
881
0
    goto error;
882
1.90k
883
1.90k
  
if (1.90k
isl_ast_build_has_affine_value(build, build->depth)1.90k
)
{1.27k
884
1.27k
    isl_basic_set_free(bounds);
885
1.27k
    return build;
886
1.27k
  }
887
1.90k
888
627
  build = isl_ast_build_cow(build);
889
627
  if (!build)
890
0
    goto error;
891
627
892
627
  pending = isl_basic_set_copy(bounds);
893
627
  pending = isl_basic_set_drop_constraints_involving_dims(pending,
894
627
        isl_dim_set, build->depth, 1);
895
627
  build->pending = isl_set_intersect(build->pending,
896
627
        isl_set_from_basic_set(pending));
897
627
  generated = bounds;
898
627
  generated = isl_basic_set_drop_constraints_not_involving_dims(
899
627
          generated, isl_dim_set, build->depth, 1);
900
627
  build->generated = isl_set_intersect(build->generated,
901
627
        isl_set_from_basic_set(generated));
902
627
903
627
  if (
!build->pending || 627
!build->generated627
)
904
0
    return isl_ast_build_free(build);
905
627
906
627
  return build;
907
0
error:
908
0
  isl_ast_build_free(build);
909
0
  isl_basic_set_free(bounds);
910
0
  return NULL;
911
627
}
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
9.14k
{
919
9.14k
  build = isl_ast_build_cow(build);
920
9.14k
  if (!build)
921
0
    goto error;
922
9.14k
923
9.14k
  set = isl_set_compute_divs(set);
924
9.14k
  build->domain = isl_set_intersect(build->domain, set);
925
9.14k
  build->domain = isl_set_coalesce(build->domain);
926
9.14k
927
9.14k
  if (!build->domain)
928
0
    return isl_ast_build_free(build);
929
9.14k
930
9.14k
  return build;
931
0
error:
932
0
  isl_ast_build_free(build);
933
0
  isl_set_free(set);
934
0
  return NULL;
935
9.14k
}
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
9.14k
{
943
9.14k
  set = isl_set_compute_divs(set);
944
9.14k
  build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
945
9.14k
  build = isl_ast_build_cow(build);
946
9.14k
  if (!build)
947
0
    goto error;
948
9.14k
949
9.14k
  build->generated = isl_set_intersect(build->generated, set);
950
9.14k
  build->generated = isl_set_coalesce(build->generated);
951
9.14k
952
9.14k
  if (!build->generated)
953
0
    return isl_ast_build_free(build);
954
9.14k
955
9.14k
  return build;
956
0
error:
957
0
  isl_ast_build_free(build);
958
0
  isl_set_free(set);
959
0
  return NULL;
960
9.14k
}
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
3.69k
{
970
3.69k
  build = isl_ast_build_restrict_generated(build, guard);
971
3.69k
  build = isl_ast_build_cow(build);
972
3.69k
  if (!build)
973
0
    return NULL;
974
3.69k
975
3.69k
  isl_set_free(build->domain);
976
3.69k
  build->domain = isl_set_copy(build->generated);
977
3.69k
  isl_set_free(build->pending);
978
3.69k
  build->pending = isl_set_universe(isl_set_get_space(build->domain));
979
3.69k
980
3.69k
  if (!build->pending)
981
0
    return isl_ast_build_free(build);
982
3.69k
983
3.69k
  return build;
984
3.69k
}
985
986
/* Intersect build->domain with "set", where "set" is specified
987
 * in terms of the external schedule domain.
988
 */
989
__isl_give isl_ast_build *isl_ast_build_restrict(
990
  __isl_take isl_ast_build *build, __isl_take isl_set *set)
991
0
{
992
0
  if (isl_set_is_params(set))
993
0
    return isl_ast_build_restrict_generated(build, set);
994
0
995
0
  
if (0
isl_ast_build_need_schedule_map(build)0
)
{0
996
0
    isl_multi_aff *ma;
997
0
    ma = isl_ast_build_get_schedule_map_multi_aff(build);
998
0
    set = isl_set_preimage_multi_aff(set, ma);
999
0
  }
1000
0
  return isl_ast_build_restrict_generated(build, set);
1001
0
}
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.14k
{
1008
3.14k
  build = isl_ast_build_cow(build);
1009
3.14k
  if (!build)
1010
0
    goto error;
1011
3.14k
1012
3.14k
  isl_union_map_free(build->executed);
1013
3.14k
  build->executed = executed;
1014
3.14k
1015
3.14k
  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.14k
}
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
3.67k
{
1027
3.67k
  if (!build)
1028
0
    return -1;
1029
3.67k
  return build->node != NULL;
1030
3.67k
}
1031
1032
/* Return a copy of the band node that "build" refers to.
1033
 */
1034
__isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1035
  __isl_keep isl_ast_build *build)
1036
1.16k
{
1037
1.16k
  if (!build)
1038
0
    return NULL;
1039
1.16k
  return isl_schedule_node_copy(build->node);
1040
1.16k
}
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
531
{
1048
531
  int i;
1049
531
  isl_ctx *ctx;
1050
531
  isl_schedule_node *node;
1051
531
1052
531
  if (!build)
1053
0
    return NULL;
1054
531
  ctx = isl_ast_build_get_ctx(build);
1055
531
  if (!build->node)
1056
0
    isl_die(ctx, isl_error_internal, "missing AST node",
1057
531
      return isl_ast_build_free(build));
1058
531
1059
531
  free(build->loop_type);
1060
531
  build->n = isl_schedule_node_band_n_member(build->node);
1061
531
  build->loop_type = isl_alloc_array(ctx,
1062
531
              enum isl_ast_loop_type, build->n);
1063
531
  if (
build->n && 531
!build->loop_type531
)
1064
0
    return isl_ast_build_free(build);
1065
531
  node = build->node;
1066
1.22k
  for (i = 0; 
i < build->n1.22k
;
++i694
)
1067
694
    build->loop_type[i] =
1068
694
        isl_schedule_node_band_member_get_ast_loop_type(node, i);
1069
531
1070
531
  return build;
1071
531
}
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
531
{
1080
531
  build = isl_ast_build_cow(build);
1081
531
  if (
!build || 531
!node531
)
1082
0
    goto error;
1083
531
1084
531
  isl_schedule_node_free(build->node);
1085
531
  build->node = node;
1086
531
1087
531
  build = extract_loop_types(build);
1088
531
1089
531
  return build;
1090
0
error:
1091
0
  isl_ast_build_free(build);
1092
0
  isl_schedule_node_free(node);
1093
0
  return NULL;
1094
531
}
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.10k
{
1101
1.10k
  build = isl_ast_build_cow(build);
1102
1.10k
  if (!build)
1103
0
    return NULL;
1104
1.10k
1105
1.10k
  isl_schedule_node_free(build->node);
1106
1.10k
  build->node = NULL;
1107
1.10k
1108
1.10k
  return build;
1109
1.10k
}
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.16k
{
1115
4.16k
  return build ? isl_set_copy(build->domain) : NULL;
1116
4.16k
}
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.03k
{
1123
3.03k
  return build ? isl_set_copy(build->pending) : NULL;
1124
3.03k
}
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.25k
{
1131
3.25k
  return build ? isl_set_copy(build->generated) : NULL;
1132
3.25k
}
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
3.51k
{
1149
3.51k
  if (!build)
1150
0
    return 0;
1151
3.51k
  return isl_set_dim(build->domain, type);
1152
3.51k
}
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
8.43k
{
1166
8.43k
  int i;
1167
8.43k
  int dim;
1168
8.43k
  isl_space *space;
1169
8.43k
1170
8.43k
  if (!build)
1171
0
    return NULL;
1172
8.43k
1173
8.43k
  space = isl_set_get_space(build->domain);
1174
8.43k
  if (internal)
1175
7.68k
    return space;
1176
8.43k
1177
749
  
if (749
!isl_ast_build_need_schedule_map(build)749
)
1178
704
    return space;
1179
749
1180
45
  dim = isl_set_dim(build->domain, isl_dim_set);
1181
45
  space = isl_space_drop_dims(space, isl_dim_set,
1182
45
            build->depth, dim - build->depth);
1183
250
  for (i = build->depth - 1; 
i >= 0250
;
--i205
)
1184
205
    
if (205
isl_ast_build_has_affine_value(build, i)205
)
1185
97
      space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1186
45
1187
45
  return space;
1188
749
}
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
272
{
1227
272
  isl_union_map *executed;
1228
272
  isl_union_map *schedule;
1229
272
1230
272
  if (!build)
1231
0
    return NULL;
1232
272
1233
272
  executed = isl_union_map_copy(build->executed);
1234
272
  if (
isl_ast_build_need_schedule_map(build)272
)
{96
1235
96
    isl_map *proj = isl_ast_build_get_schedule_map(build);
1236
96
    executed = isl_union_map_apply_domain(executed,
1237
96
          isl_union_map_from_map(proj));
1238
96
  }
1239
272
  schedule = isl_union_map_reverse(executed);
1240
272
1241
272
  return schedule;
1242
272
}
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
9.83k
{
1249
9.83k
  if (!build)
1250
0
    return NULL;
1251
9.83k
1252
9.83k
  return isl_id_list_get_id(build->iterators, pos);
1253
9.83k
}
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
573
{
1374
573
  isl_space *space;
1375
573
  isl_multi_aff *ma;
1376
573
  int pos;
1377
573
  isl_aff *aff, *offset;
1378
573
  isl_val *stride;
1379
573
1380
573
  if (!build)
1381
0
    return NULL;
1382
573
1383
573
  pos = isl_ast_build_get_depth(build);
1384
573
  space = isl_ast_build_get_space(build, 1);
1385
573
  space = isl_space_map_from_set(space);
1386
573
  ma = isl_multi_aff_identity(space);
1387
573
1388
573
  if (!isl_ast_build_has_stride(build, pos))
1389
573
    return ma;
1390
573
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
573
}
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
627
{
1407
627
  isl_set *set;
1408
627
1409
627
  if (!build)
1410
0
    return NULL;
1411
627
  
if (627
!isl_ast_build_has_stride(build, build->depth)627
)
1412
616
    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.37k
{
1474
2.37k
  struct isl_detect_stride_data *data = user;
1475
2.37k
  int i, n_div;
1476
2.37k
  isl_ctx *ctx;
1477
2.37k
  isl_val *v, *stride, *m;
1478
2.37k
1479
2.37k
  if (!isl_constraint_is_equality(c) ||
1480
2.35k
      
!isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)2.35k
)
{573
1481
573
    isl_constraint_free(c);
1482
573
    return isl_stat_ok;
1483
573
  }
1484
2.37k
1485
1.80k
  ctx = isl_constraint_get_ctx(c);
1486
1.80k
  stride = isl_val_zero(ctx);
1487
1.80k
  n_div = isl_constraint_dim(c, isl_dim_div);
1488
1.83k
  for (i = 0; 
i < n_div1.83k
;
++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
1.80k
1493
1.80k
  v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
1494
1.80k
  m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
1495
1.80k
  stride = isl_val_div(stride, isl_val_copy(m));
1496
1.80k
  v = isl_val_div(v, isl_val_copy(m));
1497
1.80k
1498
1.80k
  if (
!isl_val_is_zero(stride) && 1.80k
!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
1.78k
  } else {
1516
1.78k
    isl_val_free(stride);
1517
1.78k
    isl_val_free(m);
1518
1.78k
    isl_val_free(v);
1519
1.78k
  }
1520
1.80k
1521
1.80k
  isl_constraint_free(c);
1522
1.80k
  return isl_stat_ok;
1523
2.37k
}
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.47k
{
1540
2.47k
  isl_basic_set *hull;
1541
2.47k
  struct isl_detect_stride_data data;
1542
2.47k
1543
2.47k
  if (!build)
1544
0
    goto error;
1545
2.47k
1546
2.47k
  data.build = build;
1547
2.47k
  data.pos = isl_ast_build_get_depth(build);
1548
2.47k
  hull = isl_set_affine_hull(set);
1549
2.47k
1550
2.47k
  if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1551
0
    data.build = isl_ast_build_free(data.build);
1552
2.47k
1553
2.47k
  isl_basic_set_free(hull);
1554
2.47k
  return data.build;
1555
0
error:
1556
0
  isl_set_free(set);
1557
0
  return NULL;
1558
2.47k
}
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
553
{
1867
553
  int i;
1868
553
  isl_id_list *names;
1869
553
1870
553
  names = isl_id_list_alloc(ctx, n);
1871
1.30k
  for (i = 0; 
i < n1.30k
;
++i756
)
{756
1872
756
    isl_id *id;
1873
756
1874
756
    id = generate_name(ctx, first + i, build);
1875
756
    names = isl_id_list_add(names, id);
1876
756
  }
1877
553
1878
553
  return names;
1879
553
}
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
550
{
1908
550
  isl_map *map;
1909
550
1910
550
  map = isl_map_universe(isl_space_unwrap(space));
1911
550
  map = isl_map_range_map(map);
1912
550
1913
550
  options = isl_union_map_apply_range(
1914
550
        isl_union_map_from_map(map), options);
1915
550
1916
550
  return options;
1917
550
}
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
962
{
1944
962
  isl_ctx *ctx;
1945
962
  isl_vec *strides;
1946
962
  isl_set *set;
1947
962
  isl_multi_aff *embedding;
1948
962
  int dim, n_it;
1949
962
1950
962
  build = isl_ast_build_cow(build);
1951
962
  if (!build)
1952
0
    goto error;
1953
962
1954
962
  build->outer_pos = build->depth;
1955
962
1956
962
  ctx = isl_ast_build_get_ctx(build);
1957
962
  dim = isl_set_dim(build->domain, isl_dim_set);
1958
962
  dim += isl_space_dim(space, isl_dim_set);
1959
962
  n_it = isl_id_list_n_id(build->iterators);
1960
962
  if (
n_it < dim962
)
{553
1961
553
    isl_id_list *l;
1962
553
    l = generate_names(ctx, dim - n_it, n_it, build);
1963
553
    build->iterators = isl_id_list_concat(build->iterators, l);
1964
553
  }
1965
962
1966
962
  if (isl_set_is_params(build->domain))
1967
412
    return isl_ast_build_init(build, space);
1968
962
1969
550
  set = isl_set_universe(isl_space_copy(space));
1970
550
  build->domain = isl_set_product(build->domain, isl_set_copy(set));
1971
550
  build->pending = isl_set_product(build->pending, isl_set_copy(set));
1972
550
  build->generated = isl_set_product(build->generated, set);
1973
550
1974
550
  strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1975
550
  strides = isl_vec_set_si(strides, 1);
1976
550
  build->strides = isl_vec_concat(build->strides, strides);
1977
550
1978
550
  space = isl_space_map_from_set(space);
1979
550
  build->offsets = isl_multi_aff_align_params(build->offsets,
1980
550
                isl_space_copy(space));
1981
550
  build->offsets = isl_multi_aff_product(build->offsets,
1982
550
        isl_multi_aff_zero(isl_space_copy(space)));
1983
550
  build->values = isl_multi_aff_align_params(build->values,
1984
550
                isl_space_copy(space));
1985
550
  embedding = isl_multi_aff_identity(space);
1986
550
  build->values = isl_multi_aff_product(build->values,
1987
550
          isl_multi_aff_copy(embedding));
1988
550
  if (
build->internal2input550
)
{550
1989
550
    build->internal2input =
1990
550
      isl_multi_aff_product(build->internal2input, embedding);
1991
550
    build->internal2input =
1992
550
      isl_multi_aff_flatten_range(build->internal2input);
1993
550
    if (!build->internal2input)
1994
0
      return isl_ast_build_free(build);
1995
0
  } else {
1996
0
    isl_multi_aff_free(embedding);
1997
0
  }
1998
550
1999
550
  space = isl_ast_build_get_space(build, 1);
2000
550
  build->options = embed_options(build->options, space);
2001
550
2002
550
  if (
!build->iterators || 550
!build->domain550
||
!build->generated550
||
2003
550
      
!build->pending550
||
!build->values550
||
2004
550
      
!build->strides550
||
!build->offsets550
||
!build->options550
)
2005
0
    return isl_ast_build_free(build);
2006
550
2007
550
  return build;
2008
0
error:
2009
0
  isl_ast_build_free(build);
2010
0
  isl_space_free(space);
2011
0
  return NULL;
2012
550
}
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
7.56k
{
2039
7.56k
  isl_val *v;
2040
7.56k
  isl_bool has_stride;
2041
7.56k
2042
7.56k
  if (!build)
2043
0
    return isl_bool_error;
2044
7.56k
2045
7.56k
  v = isl_vec_get_element_val(build->strides, pos);
2046
7.56k
  has_stride = isl_bool_not(isl_val_is_one(v));
2047
7.56k
  isl_val_free(v);
2048
7.56k
2049
7.56k
  return has_stride;
2050
7.56k
}
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
6.85k
{
2094
6.85k
  isl_aff *aff;
2095
6.85k
  int involves;
2096
6.85k
2097
6.85k
  if (!build)
2098
0
    return -1;
2099
6.85k
2100
6.85k
  aff = isl_multi_aff_get_aff(build->values, pos);
2101
6.85k
  involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
2102
6.85k
  isl_aff_free(aff);
2103
6.85k
2104
6.85k
  if (involves < 0)
2105
0
    return -1;
2106
6.85k
2107
6.85k
  return !involves;
2108
6.85k
}
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.28k
{
2119
1.28k
  isl_multi_aff *values;
2120
1.28k
2121
1.28k
  if (!build)
2122
0
    return isl_union_map_free(umap);
2123
1.28k
2124
1.28k
  values = isl_multi_aff_copy(build->values);
2125
1.28k
  umap = isl_union_map_preimage_domain_multi_aff(umap, values);
2126
1.28k
2127
1.28k
  return umap;
2128
1.28k
}
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
1.90k
{
2134
1.90k
  if (!build)
2135
0
    return -1;
2136
1.90k
2137
1.90k
  return build->value != NULL;
2138
1.90k
}
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
627
{
2148
627
  if (!build)
2149
0
    goto error;
2150
627
2151
627
  bset = isl_basic_set_preimage_multi_aff(bset,
2152
627
          isl_multi_aff_copy(build->values));
2153
627
  bset = isl_basic_set_gist(bset,
2154
627
      isl_set_simple_hull(isl_set_copy(build->domain)));
2155
627
2156
627
  return bset;
2157
0
error:
2158
0
  isl_basic_set_free(bset);
2159
0
  return NULL;
2160
627
}
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
551
{
2170
551
  if (!build)
2171
0
    goto error;
2172
551
2173
551
  
if (551
!isl_set_is_params(set)551
)
2174
11
    set = isl_set_preimage_multi_aff(set,
2175
11
          isl_multi_aff_copy(build->values));
2176
551
  set = isl_set_gist(set, isl_set_copy(build->domain));
2177
551
2178
551
  return set;
2179
0
error:
2180
0
  isl_set_free(set);
2181
0
  return NULL;
2182
551
}
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
4.59k
{
2195
4.59k
  if (!build)
2196
0
    return isl_set_free(set);
2197
4.59k
2198
4.59k
  return isl_set_preimage_multi_aff(set,
2199
4.59k
          isl_multi_aff_copy(build->values));
2200
4.59k
}
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
1.90k
{
2207
1.90k
  if (!build)
2208
0
    return isl_basic_set_free(bset);
2209
1.90k
2210
1.90k
  return isl_basic_set_preimage_multi_aff(bset,
2211
1.90k
          isl_multi_aff_copy(build->values));
2212
1.90k
}
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
635
{
2241
635
  if (!build)
2242
0
    goto error;
2243
635
2244
635
  aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2245
635
2246
635
  return aff;
2247
0
error:
2248
0
  isl_aff_free(aff);
2249
0
  return NULL;
2250
635
}
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
5.76k
{
2260
5.76k
  if (!build)
2261
0
    goto error;
2262
5.76k
2263
5.76k
  
if (5.76k
!isl_set_is_params(build->domain)5.76k
)
2264
4.91k
    pa = isl_pw_aff_pullback_multi_aff(pa,
2265
4.91k
          isl_multi_aff_copy(build->values));
2266
5.76k
  pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2267
5.76k
2268
5.76k
  return pa;
2269
0
error:
2270
0
  isl_pw_aff_free(pa);
2271
0
  return NULL;
2272
5.76k
}
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.13k
{
2282
1.13k
  if (!build)
2283
0
    goto error;
2284
1.13k
2285
1.13k
  pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2286
1.13k
          isl_multi_aff_copy(build->values));
2287
1.13k
  pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2288
1.13k
2289
1.13k
  return pma;
2290
0
error:
2291
0
  isl_pw_multi_aff_free(pma);
2292
0
  return NULL;
2293
1.13k
}
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.77k
{
2353
1.77k
  int local_pos;
2354
1.77k
  isl_ctx *ctx;
2355
1.77k
2356
1.77k
  if (!build)
2357
0
    return isl_ast_loop_error;
2358
1.77k
  ctx = isl_ast_build_get_ctx(build);
2359
1.77k
  if (!build->node)
2360
0
    isl_die(ctx, isl_error_internal,
2361
1.77k
      "only works for schedule tree based AST generation",
2362
1.77k
      return isl_ast_loop_error);
2363
1.77k
2364
1.77k
  local_pos = build->depth - build->outer_pos;
2365
1.77k
  if (!isolated)
2366
1.21k
    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.77k
}
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.28k
{
2391
1.28k
  isl_set *isolated;
2392
1.28k
2393
1.28k
  if (!build)
2394
0
    return NULL;
2395
1.28k
  
if (1.28k
!build->internal2input1.28k
)
2396
12
    return build;
2397
1.27k
  
if (1.27k
build->isolated1.27k
)
2398
0
    return build;
2399
1.27k
2400
1.27k
  build = isl_ast_build_cow(build);
2401
1.27k
  if (!build)
2402
0
    return NULL;
2403
1.27k
2404
1.27k
  isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);
2405
1.27k
  isolated = isl_set_flatten(isolated);
2406
1.27k
  isolated = isl_set_preimage_multi_aff(isolated,
2407
1.27k
            isl_multi_aff_copy(build->internal2input));
2408
1.27k
2409
1.27k
  build->isolated = isolated;
2410
1.27k
  if (!build->isolated)
2411
0
    return isl_ast_build_free(build);
2412
1.27k
2413
1.27k
  return build;
2414
1.27k
}
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.28k
{
2422
1.28k
  int empty;
2423
1.28k
2424
1.28k
  if (!build)
2425
0
    return -1;
2426
1.28k
  
if (1.28k
!build->internal2input1.28k
)
2427
12
    return 0;
2428
1.27k
  
if (1.27k
!build->isolated1.27k
)
2429
0
    isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2430
1.27k
      "isolated set not extracted yet", return -1);
2431
1.27k
2432
1.27k
  empty = isl_set_plain_is_empty(build->isolated);
2433
1.27k
  return empty < 0 ? 
-10
:
!empty1.27k
;
2434
1.27k
}
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.13k
{
2501
5.13k
  int dim;
2502
5.13k
  int depth;
2503
5.13k
2504
5.13k
  if (!build)
2505
0
    return isl_set_free(set);
2506
5.13k
2507
5.13k
  dim = isl_set_dim(set, isl_dim_set);
2508
5.13k
  depth = build->depth;
2509
5.13k
  set = isl_set_detect_equalities(set);
2510
5.13k
  set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2511
5.13k
2512
5.13k
  return set;
2513
5.13k
}
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
4.51k
{
2525
4.51k
  int depth;
2526
4.51k
2527
4.51k
  if (!build)
2528
0
    return isl_set_free(set);
2529
4.51k
2530
4.51k
  set = isl_set_remove_unknown_divs(set);
2531
4.51k
  depth = build->depth;
2532
4.51k
  set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2533
4.51k
2534
4.51k
  return set;
2535
4.51k
}
2536
2537
/* Eliminate dimensions inner to the current dimension as well as
2538
 * unknown divs and divs that depend on the current dimension.
2539
 * The result then consists only of constraints that are independent
2540
 * of the current dimension and upper and lower bounds on the current
2541
 * dimension.
2542
 */
2543
__isl_give isl_set *isl_ast_build_eliminate(
2544
  __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2545
2.03k
{
2546
2.03k
  domain = isl_ast_build_eliminate_inner(build, domain);
2547
2.03k
  domain = isl_ast_build_eliminate_divs(build, domain);
2548
2.03k
  return domain;
2549
2.03k
}
2550
2551
/* Replace build->single_valued by "sv".
2552
 */
2553
__isl_give isl_ast_build *isl_ast_build_set_single_valued(
2554
  __isl_take isl_ast_build *build, int sv)
2555
431
{
2556
431
  if (!build)
2557
0
    return build;
2558
431
  
if (431
build->single_valued == sv431
)
2559
415
    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
}