Coverage Report

Created: 2017-11-21 16:49

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2012-2014 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 <limits.h>
14
#include <isl/aff.h>
15
#include <isl/constraint.h>
16
#include <isl/set.h>
17
#include <isl/ilp.h>
18
#include <isl/union_set.h>
19
#include <isl/union_map.h>
20
#include <isl/schedule_node.h>
21
#include <isl_sort.h>
22
#include <isl_tarjan.h>
23
#include <isl_ast_private.h>
24
#include <isl_ast_build_expr.h>
25
#include <isl_ast_build_private.h>
26
#include <isl_ast_graft_private.h>
27
28
/* Data used in generate_domain.
29
 *
30
 * "build" is the input build.
31
 * "list" collects the results.
32
 */
33
struct isl_generate_domain_data {
34
  isl_ast_build *build;
35
36
  isl_ast_graft_list *list;
37
};
38
39
static __isl_give isl_ast_graft_list *generate_next_level(
40
  __isl_take isl_union_map *executed,
41
  __isl_take isl_ast_build *build);
42
static __isl_give isl_ast_graft_list *generate_code(
43
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
44
  int internal);
45
46
/* Generate an AST for a single domain based on
47
 * the (non single valued) inverse schedule "executed".
48
 *
49
 * We extend the schedule with the iteration domain
50
 * and continue generating through a call to generate_code.
51
 *
52
 * In particular, if executed has the form
53
 *
54
 *  S -> D
55
 *
56
 * then we continue generating code on
57
 *
58
 *  [S -> D] -> D
59
 *
60
 * The extended inverse schedule is clearly single valued
61
 * ensuring that the nested generate_code will not reach this function,
62
 * but will instead create calls to all elements of D that need
63
 * to be executed from the current schedule domain.
64
 */
65
static isl_stat generate_non_single_valued(__isl_take isl_map *executed,
66
  struct isl_generate_domain_data *data)
67
10
{
68
10
  isl_map *identity;
69
10
  isl_ast_build *build;
70
10
  isl_ast_graft_list *list;
71
10
72
10
  build = isl_ast_build_copy(data->build);
73
10
74
10
  identity = isl_set_identity(isl_map_range(isl_map_copy(executed)));
75
10
  executed = isl_map_domain_product(executed, identity);
76
10
  build = isl_ast_build_set_single_valued(build, 1);
77
10
78
10
  list = generate_code(isl_union_map_from_map(executed), build, 1);
79
10
80
10
  data->list = isl_ast_graft_list_concat(data->list, list);
81
10
82
10
  return isl_stat_ok;
83
10
}
84
85
/* Call the at_each_domain callback, if requested by the user,
86
 * after recording the current inverse schedule in the build.
87
 */
88
static __isl_give isl_ast_graft *at_each_domain(__isl_take isl_ast_graft *graft,
89
  __isl_keep isl_map *executed, __isl_keep isl_ast_build *build)
90
1.15k
{
91
1.15k
  if (!graft || !build)
92
0
    return isl_ast_graft_free(graft);
93
1.15k
  if (!build->at_each_domain)
94
0
    return graft;
95
1.15k
96
1.15k
  build = isl_ast_build_copy(build);
97
1.15k
  build = isl_ast_build_set_executed(build,
98
1.15k
      isl_union_map_from_map(isl_map_copy(executed)));
99
1.15k
  if (!build)
100
0
    return isl_ast_graft_free(graft);
101
1.15k
102
1.15k
  graft->node = build->at_each_domain(graft->node,
103
1.15k
          build, build->at_each_domain_user);
104
1.15k
  isl_ast_build_free(build);
105
1.15k
106
1.15k
  if (!graft->node)
107
0
    graft = isl_ast_graft_free(graft);
108
1.15k
109
1.15k
  return graft;
110
1.15k
}
111
112
/* Generate a call expression for the single executed
113
 * domain element "map" and put a guard around it based its (simplified)
114
 * domain.  "executed" is the original inverse schedule from which "map"
115
 * has been derived.  In particular, "map" is either identical to "executed"
116
 * or it is the result of gisting "executed" with respect to the build domain.
117
 * "executed" is only used if there is an at_each_domain callback.
118
 *
119
 * At this stage, any pending constraints in the build can no longer
120
 * be simplified with respect to any enforced constraints since
121
 * the call node does not have any enforced constraints.
122
 * Since all pending constraints not covered by any enforced constraints
123
 * will be added as a guard to the graft in create_node_scaled,
124
 * even in the eliminated case, the pending constraints
125
 * can be considered to have been generated by outer constructs.
126
 *
127
 * If the user has set an at_each_domain callback, it is called
128
 * on the constructed call expression node.
129
 */
130
static isl_stat add_domain(__isl_take isl_map *executed,
131
  __isl_take isl_map *map, struct isl_generate_domain_data *data)
132
1.15k
{
133
1.15k
  isl_ast_build *build;
134
1.15k
  isl_ast_graft *graft;
135
1.15k
  isl_ast_graft_list *list;
136
1.15k
  isl_set *guard, *pending;
137
1.15k
138
1.15k
  build = isl_ast_build_copy(data->build);
139
1.15k
  pending = isl_ast_build_get_pending(build);
140
1.15k
  build = isl_ast_build_replace_pending_by_guard(build, pending);
141
1.15k
142
1.15k
  guard = isl_map_domain(isl_map_copy(map));
143
1.15k
  guard = isl_set_compute_divs(guard);
144
1.15k
  guard = isl_set_coalesce(guard);
145
1.15k
  guard = isl_set_gist(guard, isl_ast_build_get_generated(build));
146
1.15k
  guard = isl_ast_build_specialize(build, guard);
147
1.15k
148
1.15k
  graft = isl_ast_graft_alloc_domain(map, build);
149
1.15k
  graft = at_each_domain(graft, executed, build);
150
1.15k
  isl_ast_build_free(build);
151
1.15k
  isl_map_free(executed);
152
1.15k
  graft = isl_ast_graft_add_guard(graft, guard, data->build);
153
1.15k
154
1.15k
  list = isl_ast_graft_list_from_ast_graft(graft);
155
1.15k
  data->list = isl_ast_graft_list_concat(data->list, list);
156
1.15k
157
1.15k
  return isl_stat_ok;
158
1.15k
}
159
160
/* Generate an AST for a single domain based on
161
 * the inverse schedule "executed" and add it to data->list.
162
 *
163
 * If there is more than one domain element associated to the current
164
 * schedule "time", then we need to continue the generation process
165
 * in generate_non_single_valued.
166
 * Note that the inverse schedule being single-valued may depend
167
 * on constraints that are only available in the original context
168
 * domain specified by the user.  We therefore first introduce
169
 * some of the constraints of data->build->domain.  In particular,
170
 * we intersect with a single-disjunct approximation of this set.
171
 * We perform this approximation to avoid further splitting up
172
 * the executed relation, possibly introducing a disjunctive guard
173
 * on the statement.
174
 *
175
 * On the other hand, we only perform the test after having taken the gist
176
 * of the domain as the resulting map is the one from which the call
177
 * expression is constructed.  Using this map to construct the call
178
 * expression usually yields simpler results in cases where the original
179
 * map is not obviously single-valued.
180
 * If the original map is obviously single-valued, then the gist
181
 * operation is skipped.
182
 *
183
 * Because we perform the single-valuedness test on the gisted map,
184
 * we may in rare cases fail to recognize that the inverse schedule
185
 * is single-valued.  This becomes problematic if this happens
186
 * from the recursive call through generate_non_single_valued
187
 * as we would then end up in an infinite recursion.
188
 * We therefore check if we are inside a call to generate_non_single_valued
189
 * and revert to the ungisted map if the gisted map turns out not to be
190
 * single-valued.
191
 *
192
 * Otherwise, call add_domain to generate a call expression (with guard) and
193
 * to call the at_each_domain callback, if any.
194
 */
195
static isl_stat generate_domain(__isl_take isl_map *executed, void *user)
196
1.16k
{
197
1.16k
  struct isl_generate_domain_data *data = user;
198
1.16k
  isl_set *domain;
199
1.16k
  isl_map *map = NULL;
200
1.16k
  int empty, sv;
201
1.16k
202
1.16k
  domain = isl_ast_build_get_domain(data->build);
203
1.16k
  domain = isl_set_from_basic_set(isl_set_simple_hull(domain));
204
1.16k
  executed = isl_map_intersect_domain(executed, domain);
205
1.16k
  empty = isl_map_is_empty(executed);
206
1.16k
  if (empty < 0)
207
0
    goto error;
208
1.16k
  if (empty) {
209
0
    isl_map_free(executed);
210
0
    return isl_stat_ok;
211
0
  }
212
1.16k
213
1.16k
  sv = isl_map_plain_is_single_valued(executed);
214
1.16k
  if (sv < 0)
215
0
    goto error;
216
1.16k
  if (sv)
217
1.14k
    return add_domain(executed, isl_map_copy(executed), data);
218
20
219
20
  executed = isl_map_coalesce(executed);
220
20
  map = isl_map_copy(executed);
221
20
  map = isl_ast_build_compute_gist_map_domain(data->build, map);
222
20
  sv = isl_map_is_single_valued(map);
223
20
  if (sv < 0)
224
0
    goto error;
225
20
  if (!sv) {
226
10
    isl_map_free(map);
227
10
    if (data->build->single_valued)
228
0
      map = isl_map_copy(executed);
229
10
    else
230
10
      return generate_non_single_valued(executed, data);
231
10
  }
232
10
233
10
  return add_domain(executed, map, data);
234
0
error:
235
0
  isl_map_free(map);
236
0
  isl_map_free(executed);
237
0
  return isl_stat_error;
238
1.16k
}
239
240
/* Call build->create_leaf to a create "leaf" node in the AST,
241
 * encapsulate the result in an isl_ast_graft and return the result
242
 * as a 1-element list.
243
 *
244
 * Note that the node returned by the user may be an entire tree.
245
 *
246
 * Since the node itself cannot enforce any constraints, we turn
247
 * all pending constraints into guards and add them to the resulting
248
 * graft to ensure that they will be generated.
249
 *
250
 * Before we pass control to the user, we first clear some information
251
 * from the build that is (presumbably) only meaningful
252
 * for the current code generation.
253
 * This includes the create_leaf callback itself, so we make a copy
254
 * of the build first.
255
 */
256
static __isl_give isl_ast_graft_list *call_create_leaf(
257
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
258
0
{
259
0
  isl_set *guard;
260
0
  isl_ast_node *node;
261
0
  isl_ast_graft *graft;
262
0
  isl_ast_build *user_build;
263
0
264
0
  guard = isl_ast_build_get_pending(build);
265
0
  user_build = isl_ast_build_copy(build);
266
0
  user_build = isl_ast_build_replace_pending_by_guard(user_build,
267
0
              isl_set_copy(guard));
268
0
  user_build = isl_ast_build_set_executed(user_build, executed);
269
0
  user_build = isl_ast_build_clear_local_info(user_build);
270
0
  if (!user_build)
271
0
    node = NULL;
272
0
  else
273
0
    node = build->create_leaf(user_build, build->create_leaf_user);
274
0
  graft = isl_ast_graft_alloc(node, build);
275
0
  graft = isl_ast_graft_add_guard(graft, guard, build);
276
0
  isl_ast_build_free(build);
277
0
  return isl_ast_graft_list_from_ast_graft(graft);
278
0
}
279
280
static __isl_give isl_ast_graft_list *build_ast_from_child(
281
  __isl_take isl_ast_build *build, __isl_take isl_schedule_node *node,
282
  __isl_take isl_union_map *executed);
283
284
/* Generate an AST after having handled the complete schedule
285
 * of this call to the code generator or the complete band
286
 * if we are generating an AST from a schedule tree.
287
 *
288
 * If we are inside a band node, then move on to the child of the band.
289
 *
290
 * If the user has specified a create_leaf callback, control
291
 * is passed to the user in call_create_leaf.
292
 *
293
 * Otherwise, we generate one or more calls for each individual
294
 * domain in generate_domain.
295
 */
296
static __isl_give isl_ast_graft_list *generate_inner_level(
297
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
298
2.31k
{
299
2.31k
  isl_ctx *ctx;
300
2.31k
  struct isl_generate_domain_data data = { build };
301
2.31k
302
2.31k
  if (!build || !executed)
303
0
    goto error;
304
2.31k
305
2.31k
  if (isl_ast_build_has_schedule_node(build)) {
306
1.14k
    isl_schedule_node *node;
307
1.14k
    node = isl_ast_build_get_schedule_node(build);
308
1.14k
    build = isl_ast_build_reset_schedule_node(build);
309
1.14k
    return build_ast_from_child(build, node, executed);
310
1.14k
  }
311
1.16k
312
1.16k
  if (build->create_leaf)
313
0
    return call_create_leaf(executed, build);
314
1.16k
315
1.16k
  ctx = isl_union_map_get_ctx(executed);
316
1.16k
  data.list = isl_ast_graft_list_alloc(ctx, 0);
317
1.16k
  if (isl_union_map_foreach_map(executed, &generate_domain, &data) < 0)
318
0
    data.list = isl_ast_graft_list_free(data.list);
319
1.16k
320
1.16k
  if (0)
321
0
error:    data.list = NULL;
322
1.16k
  isl_ast_build_free(build);
323
1.16k
  isl_union_map_free(executed);
324
1.16k
  return data.list;
325
2.31k
}
326
327
/* Call the before_each_for callback, if requested by the user.
328
 */
329
static __isl_give isl_ast_node *before_each_for(__isl_take isl_ast_node *node,
330
  __isl_keep isl_ast_build *build)
331
222
{
332
222
  isl_id *id;
333
222
334
222
  if (!node || !build)
335
0
    return isl_ast_node_free(node);
336
222
  if (!build->before_each_for)
337
163
    return node;
338
59
  id = build->before_each_for(build, build->before_each_for_user);
339
59
  node = isl_ast_node_set_annotation(node, id);
340
59
  return node;
341
59
}
342
343
/* Call the after_each_for callback, if requested by the user.
344
 */
345
static __isl_give isl_ast_graft *after_each_for(__isl_take isl_ast_graft *graft,
346
  __isl_keep isl_ast_build *build)
347
222
{
348
222
  if (!graft || !build)
349
0
    return isl_ast_graft_free(graft);
350
222
  if (!build->after_each_for)
351
163
    return graft;
352
59
  graft->node = build->after_each_for(graft->node, build,
353
59
            build->after_each_for_user);
354
59
  if (!graft->node)
355
0
    return isl_ast_graft_free(graft);
356
59
  return graft;
357
59
}
358
359
/* Plug in all the know values of the current and outer dimensions
360
 * in the domain of "executed".  In principle, we only need to plug
361
 * in the known value of the current dimension since the values of
362
 * outer dimensions have been plugged in already.
363
 * However, it turns out to be easier to just plug in all known values.
364
 */
365
static __isl_give isl_union_map *plug_in_values(
366
  __isl_take isl_union_map *executed, __isl_keep isl_ast_build *build)
367
2.01k
{
368
2.01k
  return isl_ast_build_substitute_values_union_map_domain(build,
369
2.01k
                    executed);
370
2.01k
}
371
372
/* Check if the constraint "c" is a lower bound on dimension "pos",
373
 * an upper bound, or independent of dimension "pos".
374
 */
375
static int constraint_type(isl_constraint *c, int pos)
376
654
{
377
654
  if (isl_constraint_is_lower_bound(c, isl_dim_set, pos))
378
274
    return 1;
379
380
  if (isl_constraint_is_upper_bound(c, isl_dim_set, pos))
380
345
    return 2;
381
35
  return 0;
382
35
}
383
384
/* Compare the types of the constraints "a" and "b",
385
 * resulting in constraints that are independent of "depth"
386
 * to be sorted before the lower bounds on "depth", which in
387
 * turn are sorted before the upper bounds on "depth".
388
 */
389
static int cmp_constraint(__isl_keep isl_constraint *a,
390
  __isl_keep isl_constraint *b, void *user)
391
327
{
392
327
  int *depth = user;
393
327
  int t1 = constraint_type(a, *depth);
394
327
  int t2 = constraint_type(b, *depth);
395
327
396
327
  return t1 - t2;
397
327
}
398
399
/* Extract a lower bound on dimension "pos" from constraint "c".
400
 *
401
 * If the constraint is of the form
402
 *
403
 *  a x + f(...) >= 0
404
 *
405
 * then we essentially return
406
 *
407
 *  l = ceil(-f(...)/a)
408
 *
409
 * However, if the current dimension is strided, then we need to make
410
 * sure that the lower bound we construct is of the form
411
 *
412
 *  f + s a
413
 *
414
 * with f the offset and s the stride.
415
 * We therefore compute
416
 *
417
 *  f + s * ceil((l - f)/s)
418
 */
419
static __isl_give isl_aff *lower_bound(__isl_keep isl_constraint *c,
420
  int pos, __isl_keep isl_ast_build *build)
421
226
{
422
226
  isl_aff *aff;
423
226
424
226
  aff = isl_constraint_get_bound(c, isl_dim_set, pos);
425
226
  aff = isl_aff_ceil(aff);
426
226
427
226
  if (isl_ast_build_has_stride(build, pos)) {
428
6
    isl_aff *offset;
429
6
    isl_val *stride;
430
6
431
6
    offset = isl_ast_build_get_offset(build, pos);
432
6
    stride = isl_ast_build_get_stride(build, pos);
433
6
434
6
    aff = isl_aff_sub(aff, isl_aff_copy(offset));
435
6
    aff = isl_aff_scale_down_val(aff, isl_val_copy(stride));
436
6
    aff = isl_aff_ceil(aff);
437
6
    aff = isl_aff_scale_val(aff, stride);
438
6
    aff = isl_aff_add(aff, offset);
439
6
  }
440
226
441
226
  aff = isl_ast_build_compute_gist_aff(build, aff);
442
226
443
226
  return aff;
444
226
}
445
446
/* Return the exact lower bound (or upper bound if "upper" is set)
447
 * of "domain" as a piecewise affine expression.
448
 *
449
 * If we are computing a lower bound (of a strided dimension), then
450
 * we need to make sure it is of the form
451
 *
452
 *  f + s a
453
 *
454
 * where f is the offset and s is the stride.
455
 * We therefore need to include the stride constraint before computing
456
 * the minimum.
457
 */
458
static __isl_give isl_pw_aff *exact_bound(__isl_keep isl_set *domain,
459
  __isl_keep isl_ast_build *build, int upper)
460
0
{
461
0
  isl_set *stride;
462
0
  isl_map *it_map;
463
0
  isl_pw_aff *pa;
464
0
  isl_pw_multi_aff *pma;
465
0
466
0
  domain = isl_set_copy(domain);
467
0
  if (!upper) {
468
0
    stride = isl_ast_build_get_stride_constraint(build);
469
0
    domain = isl_set_intersect(domain, stride);
470
0
  }
471
0
  it_map = isl_ast_build_map_to_iterator(build, domain);
472
0
  if (upper)
473
0
    pma = isl_map_lexmax_pw_multi_aff(it_map);
474
0
  else
475
0
    pma = isl_map_lexmin_pw_multi_aff(it_map);
476
0
  pa = isl_pw_multi_aff_get_pw_aff(pma, 0);
477
0
  isl_pw_multi_aff_free(pma);
478
0
  pa = isl_ast_build_compute_gist_pw_aff(build, pa);
479
0
  pa = isl_pw_aff_coalesce(pa);
480
0
481
0
  return pa;
482
0
}
483
484
/* Callback for sorting the isl_pw_aff_list passed to reduce_list and
485
 * remove_redundant_lower_bounds.
486
 */
487
static int reduce_list_cmp(__isl_keep isl_pw_aff *a, __isl_keep isl_pw_aff *b,
488
  void *user)
489
43
{
490
43
  return isl_pw_aff_plain_cmp(a, b);
491
43
}
492
493
/* Given a list of lower bounds "list", remove those that are redundant
494
 * with respect to the other bounds in "list" and the domain of "build".
495
 *
496
 * We first sort the bounds in the same way as they would be sorted
497
 * by set_for_node_expressions so that we can try and remove the last
498
 * bounds first.
499
 *
500
 * For a lower bound to be effective, there needs to be at least
501
 * one domain element for which it is larger than all other lower bounds.
502
 * For each lower bound we therefore intersect the domain with
503
 * the conditions that it is larger than all other bounds and
504
 * check whether the result is empty.  If so, the bound can be removed.
505
 */
506
static __isl_give isl_pw_aff_list *remove_redundant_lower_bounds(
507
  __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
508
6
{
509
6
  int i, j, n;
510
6
  isl_set *domain;
511
6
512
6
  list = isl_pw_aff_list_sort(list, &reduce_list_cmp, NULL);
513
6
  if (!list)
514
0
    return NULL;
515
6
516
6
  n = isl_pw_aff_list_n_pw_aff(list);
517
6
  if (n <= 1)
518
6
    return list;
519
0
520
0
  domain = isl_ast_build_get_domain(build);
521
0
522
0
  for (i = n - 1; i >= 0; --i) {
523
0
    isl_pw_aff *pa_i;
524
0
    isl_set *domain_i;
525
0
    int empty;
526
0
527
0
    domain_i = isl_set_copy(domain);
528
0
    pa_i = isl_pw_aff_list_get_pw_aff(list, i);
529
0
530
0
    for (j = 0; j < n; ++j) {
531
0
      isl_pw_aff *pa_j;
532
0
      isl_set *better;
533
0
534
0
      if (j == i)
535
0
        continue;
536
0
537
0
      pa_j = isl_pw_aff_list_get_pw_aff(list, j);
538
0
      better = isl_pw_aff_gt_set(isl_pw_aff_copy(pa_i), pa_j);
539
0
      domain_i = isl_set_intersect(domain_i, better);
540
0
    }
541
0
542
0
    empty = isl_set_is_empty(domain_i);
543
0
544
0
    isl_set_free(domain_i);
545
0
    isl_pw_aff_free(pa_i);
546
0
547
0
    if (empty < 0)
548
0
      goto error;
549
0
    if (!empty)
550
0
      continue;
551
0
    list = isl_pw_aff_list_drop(list, i, 1);
552
0
    n--;
553
0
  }
554
0
555
0
  isl_set_free(domain);
556
0
557
0
  return list;
558
0
error:
559
0
  isl_set_free(domain);
560
0
  return isl_pw_aff_list_free(list);
561
6
}
562
563
/* Extract a lower bound on dimension "pos" from each constraint
564
 * in "constraints" and return the list of lower bounds.
565
 * If "constraints" has zero elements, then we extract a lower bound
566
 * from "domain" instead.
567
 *
568
 * If the current dimension is strided, then the lower bound
569
 * is adjusted by lower_bound to match the stride information.
570
 * This modification may make one or more lower bounds redundant
571
 * with respect to the other lower bounds.  We therefore check
572
 * for this condition and remove the redundant lower bounds.
573
 */
574
static __isl_give isl_pw_aff_list *lower_bounds(
575
  __isl_keep isl_constraint_list *constraints, int pos,
576
  __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
577
222
{
578
222
  isl_ctx *ctx;
579
222
  isl_pw_aff_list *list;
580
222
  int i, n;
581
222
582
222
  if (!build)
583
0
    return NULL;
584
222
585
222
  n = isl_constraint_list_n_constraint(constraints);
586
222
  if (n == 0) {
587
0
    isl_pw_aff *pa;
588
0
    pa = exact_bound(domain, build, 0);
589
0
    return isl_pw_aff_list_from_pw_aff(pa);
590
0
  }
591
222
592
222
  ctx = isl_ast_build_get_ctx(build);
593
222
  list = isl_pw_aff_list_alloc(ctx,n);
594
222
595
448
  for (i = 0; i < n; 
++i226
) {
596
226
    isl_aff *aff;
597
226
    isl_constraint *c;
598
226
599
226
    c = isl_constraint_list_get_constraint(constraints, i);
600
226
    aff = lower_bound(c, pos, build);
601
226
    isl_constraint_free(c);
602
226
    list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
603
226
  }
604
222
605
222
  if (isl_ast_build_has_stride(build, pos))
606
6
    list = remove_redundant_lower_bounds(list, build);
607
222
608
222
  return list;
609
222
}
610
611
/* Extract an upper bound on dimension "pos" from each constraint
612
 * in "constraints" and return the list of upper bounds.
613
 * If "constraints" has zero elements, then we extract an upper bound
614
 * from "domain" instead.
615
 */
616
static __isl_give isl_pw_aff_list *upper_bounds(
617
  __isl_keep isl_constraint_list *constraints, int pos,
618
  __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
619
222
{
620
222
  isl_ctx *ctx;
621
222
  isl_pw_aff_list *list;
622
222
  int i, n;
623
222
624
222
  n = isl_constraint_list_n_constraint(constraints);
625
222
  if (n == 0) {
626
0
    isl_pw_aff *pa;
627
0
    pa = exact_bound(domain, build, 1);
628
0
    return isl_pw_aff_list_from_pw_aff(pa);
629
0
  }
630
222
631
222
  ctx = isl_ast_build_get_ctx(build);
632
222
  list = isl_pw_aff_list_alloc(ctx,n);
633
222
634
481
  for (i = 0; i < n; 
++i259
) {
635
259
    isl_aff *aff;
636
259
    isl_constraint *c;
637
259
638
259
    c = isl_constraint_list_get_constraint(constraints, i);
639
259
    aff = isl_constraint_get_bound(c, isl_dim_set, pos);
640
259
    isl_constraint_free(c);
641
259
    aff = isl_aff_floor(aff);
642
259
    list = isl_pw_aff_list_add(list, isl_pw_aff_from_aff(aff));
643
259
  }
644
222
645
222
  return list;
646
222
}
647
648
/* Return an isl_ast_expr that performs the reduction of type "type"
649
 * on AST expressions corresponding to the elements in "list".
650
 *
651
 * The list is assumed to contain at least one element.
652
 * If the list contains exactly one element, then the returned isl_ast_expr
653
 * simply computes that affine expression.
654
 * If the list contains more than one element, then we sort it
655
 * using a fairly abitrary but hopefully reasonably stable order.
656
 */
657
static __isl_give isl_ast_expr *reduce_list(enum isl_ast_op_type type,
658
  __isl_keep isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
659
444
{
660
444
  int i, n;
661
444
  isl_ctx *ctx;
662
444
  isl_ast_expr *expr;
663
444
664
444
  if (!list)
665
0
    return NULL;
666
444
667
444
  n = isl_pw_aff_list_n_pw_aff(list);
668
444
669
444
  if (n == 1)
670
406
    return isl_ast_build_expr_from_pw_aff_internal(build,
671
406
        isl_pw_aff_list_get_pw_aff(list, 0));
672
38
673
38
  ctx = isl_pw_aff_list_get_ctx(list);
674
38
  expr = isl_ast_expr_alloc_op(ctx, type, n);
675
38
  if (!expr)
676
0
    return NULL;
677
38
678
38
  list = isl_pw_aff_list_copy(list);
679
38
  list = isl_pw_aff_list_sort(list, &reduce_list_cmp, NULL);
680
38
  if (!list)
681
0
    return isl_ast_expr_free(expr);
682
38
683
117
  
for (i = 0; 38
i < n;
++i79
) {
684
79
    isl_ast_expr *expr_i;
685
79
686
79
    expr_i = isl_ast_build_expr_from_pw_aff_internal(build,
687
79
        isl_pw_aff_list_get_pw_aff(list, i));
688
79
    if (!expr_i)
689
0
      goto error;
690
79
    expr->u.op.args[i] = expr_i;
691
79
  }
692
38
693
38
  isl_pw_aff_list_free(list);
694
38
  return expr;
695
0
error:
696
0
  isl_pw_aff_list_free(list);
697
0
  isl_ast_expr_free(expr);
698
0
  return NULL;
699
444
}
700
701
/* Add guards implied by the "generated constraints",
702
 * but not (necessarily) enforced by the generated AST to "guard".
703
 * In particular, if there is any stride constraints,
704
 * then add the guard implied by those constraints.
705
 * If we have generated a degenerate loop, then add the guard
706
 * implied by "bounds" on the outer dimensions, i.e., the guard
707
 * that ensures that the single value actually exists.
708
 * Since there may also be guards implied by a combination
709
 * of these constraints, we first combine them before
710
 * deriving the implied constraints.
711
 */
712
static __isl_give isl_set *add_implied_guards(__isl_take isl_set *guard,
713
  int degenerate, __isl_keep isl_basic_set *bounds,
714
  __isl_keep isl_ast_build *build)
715
222
{
716
222
  int depth, has_stride;
717
222
  isl_space *space;
718
222
  isl_set *dom, *set;
719
222
720
222
  depth = isl_ast_build_get_depth(build);
721
222
  has_stride = isl_ast_build_has_stride(build, depth);
722
222
  if (!has_stride && 
!degenerate216
)
723
216
    return guard;
724
6
725
6
  space = isl_basic_set_get_space(bounds);
726
6
  dom = isl_set_universe(space);
727
6
728
6
  if (degenerate) {
729
0
    bounds = isl_basic_set_copy(bounds);
730
0
    bounds = isl_basic_set_drop_constraints_not_involving_dims(
731
0
          bounds, isl_dim_set, depth, 1);
732
0
    set = isl_set_from_basic_set(bounds);
733
0
    dom = isl_set_intersect(dom, set);
734
0
  }
735
6
736
6
  if (has_stride) {
737
6
    set = isl_ast_build_get_stride_constraint(build);
738
6
    dom = isl_set_intersect(dom, set);
739
6
  }
740
222
741
222
  dom = isl_set_eliminate(dom, isl_dim_set, depth, 1);
742
222
  dom = isl_ast_build_compute_gist(build, dom);
743
222
  guard = isl_set_intersect(guard, dom);
744
222
745
222
  return guard;
746
222
}
747
748
/* Update "graft" based on "sub_build" for the degenerate case.
749
 *
750
 * "build" is the build in which graft->node was created
751
 * "sub_build" contains information about the current level itself,
752
 * including the single value attained.
753
 *
754
 * We set the initialization part of the for loop to the single
755
 * value attained by the current dimension.
756
 * The increment and condition are not strictly needed as the are known
757
 * to be "1" and "iterator <= value" respectively.
758
 */
759
static __isl_give isl_ast_graft *refine_degenerate(
760
  __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build,
761
  __isl_keep isl_ast_build *sub_build)
762
0
{
763
0
  isl_pw_aff *value;
764
0
765
0
  if (!graft || !sub_build)
766
0
    return isl_ast_graft_free(graft);
767
0
768
0
  value = isl_pw_aff_copy(sub_build->value);
769
0
770
0
  graft->node->u.f.init = isl_ast_build_expr_from_pw_aff_internal(build,
771
0
            value);
772
0
  if (!graft->node->u.f.init)
773
0
    return isl_ast_graft_free(graft);
774
0
775
0
  return graft;
776
0
}
777
778
/* Return the intersection of constraints in "list" as a set.
779
 */
780
static __isl_give isl_set *intersect_constraints(
781
  __isl_keep isl_constraint_list *list)
782
0
{
783
0
  int i, n;
784
0
  isl_basic_set *bset;
785
0
786
0
  n = isl_constraint_list_n_constraint(list);
787
0
  if (n < 1)
788
0
    isl_die(isl_constraint_list_get_ctx(list), isl_error_internal,
789
0
      "expecting at least one constraint", return NULL);
790
0
791
0
  bset = isl_basic_set_from_constraint(
792
0
        isl_constraint_list_get_constraint(list, 0));
793
0
  for (i = 1; i < n; ++i) {
794
0
    isl_basic_set *bset_i;
795
0
796
0
    bset_i = isl_basic_set_from_constraint(
797
0
        isl_constraint_list_get_constraint(list, i));
798
0
    bset = isl_basic_set_intersect(bset, bset_i);
799
0
  }
800
0
801
0
  return isl_set_from_basic_set(bset);
802
0
}
803
804
/* Compute the constraints on the outer dimensions enforced by
805
 * graft->node and add those constraints to graft->enforced,
806
 * in case the upper bound is expressed as a set "upper".
807
 *
808
 * In particular, if l(...) is a lower bound in "lower", and
809
 *
810
 *  -a i + f(...) >= 0    or  a i <= f(...)
811
 *
812
 * is an upper bound ocnstraint on the current dimension i,
813
 * then the for loop enforces the constraint
814
 *
815
 *  -a l(...) + f(...) >= 0   or  a l(...) <= f(...)
816
 *
817
 * We therefore simply take each lower bound in turn, plug it into
818
 * the upper bounds and compute the intersection over all lower bounds.
819
 *
820
 * If a lower bound is a rational expression, then
821
 * isl_basic_set_preimage_multi_aff will force this rational
822
 * expression to have only integer values.  However, the loop
823
 * itself does not enforce this integrality constraint.  We therefore
824
 * use the ceil of the lower bounds instead of the lower bounds themselves.
825
 * Other constraints will make sure that the for loop is only executed
826
 * when each of the lower bounds attains an integral value.
827
 * In particular, potentially rational values only occur in
828
 * lower_bound if the offset is a (seemingly) rational expression,
829
 * but then outer conditions will make sure that this rational expression
830
 * only attains integer values.
831
 */
832
static __isl_give isl_ast_graft *set_enforced_from_set(
833
  __isl_take isl_ast_graft *graft,
834
  __isl_keep isl_pw_aff_list *lower, int pos, __isl_keep isl_set *upper)
835
0
{
836
0
  isl_space *space;
837
0
  isl_basic_set *enforced;
838
0
  isl_pw_multi_aff *pma;
839
0
  int i, n;
840
0
841
0
  if (!graft || !lower)
842
0
    return isl_ast_graft_free(graft);
843
0
844
0
  space = isl_set_get_space(upper);
845
0
  enforced = isl_basic_set_universe(isl_space_copy(space));
846
0
847
0
  space = isl_space_map_from_set(space);
848
0
  pma = isl_pw_multi_aff_identity(space);
849
0
850
0
  n = isl_pw_aff_list_n_pw_aff(lower);
851
0
  for (i = 0; i < n; ++i) {
852
0
    isl_pw_aff *pa;
853
0
    isl_set *enforced_i;
854
0
    isl_basic_set *hull;
855
0
    isl_pw_multi_aff *pma_i;
856
0
857
0
    pa = isl_pw_aff_list_get_pw_aff(lower, i);
858
0
    pa = isl_pw_aff_ceil(pa);
859
0
    pma_i = isl_pw_multi_aff_copy(pma);
860
0
    pma_i = isl_pw_multi_aff_set_pw_aff(pma_i, pos, pa);
861
0
    enforced_i = isl_set_copy(upper);
862
0
    enforced_i = isl_set_preimage_pw_multi_aff(enforced_i, pma_i);
863
0
    hull = isl_set_simple_hull(enforced_i);
864
0
    enforced = isl_basic_set_intersect(enforced, hull);
865
0
  }
866
0
867
0
  isl_pw_multi_aff_free(pma);
868
0
869
0
  graft = isl_ast_graft_enforce(graft, enforced);
870
0
871
0
  return graft;
872
0
}
873
874
/* Compute the constraints on the outer dimensions enforced by
875
 * graft->node and add those constraints to graft->enforced,
876
 * in case the upper bound is expressed as
877
 * a list of affine expressions "upper".
878
 *
879
 * The enforced condition is that each lower bound expression is less
880
 * than or equal to each upper bound expression.
881
 */
882
static __isl_give isl_ast_graft *set_enforced_from_list(
883
  __isl_take isl_ast_graft *graft,
884
  __isl_keep isl_pw_aff_list *lower, __isl_keep isl_pw_aff_list *upper)
885
222
{
886
222
  isl_set *cond;
887
222
  isl_basic_set *enforced;
888
222
889
222
  lower = isl_pw_aff_list_copy(lower);
890
222
  upper = isl_pw_aff_list_copy(upper);
891
222
  cond = isl_pw_aff_list_le_set(lower, upper);
892
222
  enforced = isl_set_simple_hull(cond);
893
222
  graft = isl_ast_graft_enforce(graft, enforced);
894
222
895
222
  return graft;
896
222
}
897
898
/* Does "aff" have a negative constant term?
899
 */
900
static isl_stat aff_constant_is_negative(__isl_take isl_set *set,
901
  __isl_take isl_aff *aff, void *user)
902
228
{
903
228
  int *neg = user;
904
228
  isl_val *v;
905
228
906
228
  v = isl_aff_get_constant_val(aff);
907
228
  *neg = isl_val_is_neg(v);
908
228
  isl_val_free(v);
909
228
  isl_set_free(set);
910
228
  isl_aff_free(aff);
911
228
912
228
  return *neg ? 
isl_stat_ok48
:
isl_stat_error180
;
913
228
}
914
915
/* Does "pa" have a negative constant term over its entire domain?
916
 */
917
static isl_stat pw_aff_constant_is_negative(__isl_take isl_pw_aff *pa,
918
  void *user)
919
228
{
920
228
  isl_stat r;
921
228
  int *neg = user;
922
228
923
228
  r = isl_pw_aff_foreach_piece(pa, &aff_constant_is_negative, user);
924
228
  isl_pw_aff_free(pa);
925
228
926
228
  return (*neg && 
r >= 048
) ?
isl_stat_ok48
:
isl_stat_error180
;
927
228
}
928
929
/* Does each element in "list" have a negative constant term?
930
 *
931
 * The callback terminates the iteration as soon an element has been
932
 * found that does not have a negative constant term.
933
 */
934
static int list_constant_is_negative(__isl_keep isl_pw_aff_list *list)
935
222
{
936
222
  int neg = 1;
937
222
938
222
  if (isl_pw_aff_list_foreach(list,
939
222
        &pw_aff_constant_is_negative, &neg) < 0 && 
neg180
)
940
0
    return -1;
941
222
942
222
  return neg;
943
222
}
944
945
/* Add 1 to each of the elements in "list", where each of these elements
946
 * is defined over the internal schedule space of "build".
947
 */
948
static __isl_give isl_pw_aff_list *list_add_one(
949
  __isl_take isl_pw_aff_list *list, __isl_keep isl_ast_build *build)
950
42
{
951
42
  int i, n;
952
42
  isl_space *space;
953
42
  isl_aff *aff;
954
42
  isl_pw_aff *one;
955
42
956
42
  space = isl_ast_build_get_space(build, 1);
957
42
  aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
958
42
  aff = isl_aff_add_constant_si(aff, 1);
959
42
  one = isl_pw_aff_from_aff(aff);
960
42
961
42
  n = isl_pw_aff_list_n_pw_aff(list);
962
84
  for (i = 0; i < n; 
++i42
) {
963
42
    isl_pw_aff *pa;
964
42
    pa = isl_pw_aff_list_get_pw_aff(list, i);
965
42
    pa = isl_pw_aff_add(pa, isl_pw_aff_copy(one));
966
42
    list = isl_pw_aff_list_set_pw_aff(list, i, pa);
967
42
  }
968
42
969
42
  isl_pw_aff_free(one);
970
42
971
42
  return list;
972
42
}
973
974
/* Set the condition part of the for node graft->node in case
975
 * the upper bound is represented as a list of piecewise affine expressions.
976
 *
977
 * In particular, set the condition to
978
 *
979
 *  iterator <= min(list of upper bounds)
980
 *
981
 * If each of the upper bounds has a negative constant term, then
982
 * set the condition to
983
 *
984
 *  iterator < min(list of (upper bound + 1)s)
985
 *
986
 */
987
static __isl_give isl_ast_graft *set_for_cond_from_list(
988
  __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *list,
989
  __isl_keep isl_ast_build *build)
990
222
{
991
222
  int neg;
992
222
  isl_ast_expr *bound, *iterator, *cond;
993
222
  enum isl_ast_op_type type = isl_ast_op_le;
994
222
995
222
  if (!graft || !list)
996
0
    return isl_ast_graft_free(graft);
997
222
998
222
  neg = list_constant_is_negative(list);
999
222
  if (neg < 0)
1000
0
    return isl_ast_graft_free(graft);
1001
222
  list = isl_pw_aff_list_copy(list);
1002
222
  if (neg) {
1003
42
    list = list_add_one(list, build);
1004
42
    type = isl_ast_op_lt;
1005
42
  }
1006
222
1007
222
  bound = reduce_list(isl_ast_op_min, list, build);
1008
222
  iterator = isl_ast_expr_copy(graft->node->u.f.iterator);
1009
222
  cond = isl_ast_expr_alloc_binary(type, iterator, bound);
1010
222
  graft->node->u.f.cond = cond;
1011
222
1012
222
  isl_pw_aff_list_free(list);
1013
222
  if (!graft->node->u.f.cond)
1014
0
    return isl_ast_graft_free(graft);
1015
222
  return graft;
1016
222
}
1017
1018
/* Set the condition part of the for node graft->node in case
1019
 * the upper bound is represented as a set.
1020
 */
1021
static __isl_give isl_ast_graft *set_for_cond_from_set(
1022
  __isl_take isl_ast_graft *graft, __isl_keep isl_set *set,
1023
  __isl_keep isl_ast_build *build)
1024
0
{
1025
0
  isl_ast_expr *cond;
1026
0
1027
0
  if (!graft)
1028
0
    return NULL;
1029
0
1030
0
  cond = isl_ast_build_expr_from_set_internal(build, isl_set_copy(set));
1031
0
  graft->node->u.f.cond = cond;
1032
0
  if (!graft->node->u.f.cond)
1033
0
    return isl_ast_graft_free(graft);
1034
0
  return graft;
1035
0
}
1036
1037
/* Construct an isl_ast_expr for the increment (i.e., stride) of
1038
 * the current dimension.
1039
 */
1040
static __isl_give isl_ast_expr *for_inc(__isl_keep isl_ast_build *build)
1041
222
{
1042
222
  int depth;
1043
222
  isl_val *v;
1044
222
  isl_ctx *ctx;
1045
222
1046
222
  if (!build)
1047
0
    return NULL;
1048
222
  ctx = isl_ast_build_get_ctx(build);
1049
222
  depth = isl_ast_build_get_depth(build);
1050
222
1051
222
  if (!isl_ast_build_has_stride(build, depth))
1052
216
    return isl_ast_expr_alloc_int_si(ctx, 1);
1053
6
1054
6
  v = isl_ast_build_get_stride(build, depth);
1055
6
  return isl_ast_expr_from_val(v);
1056
6
}
1057
1058
/* Should we express the loop condition as
1059
 *
1060
 *  iterator <= min(list of upper bounds)
1061
 *
1062
 * or as a conjunction of constraints?
1063
 *
1064
 * The first is constructed from a list of upper bounds.
1065
 * The second is constructed from a set.
1066
 *
1067
 * If there are no upper bounds in "constraints", then this could mean
1068
 * that "domain" simply doesn't have an upper bound or that we didn't
1069
 * pick any upper bound.  In the first case, we want to generate the
1070
 * loop condition as a(n empty) conjunction of constraints
1071
 * In the second case, we will compute
1072
 * a single upper bound from "domain" and so we use the list form.
1073
 *
1074
 * If there are upper bounds in "constraints",
1075
 * then we use the list form iff the atomic_upper_bound option is set.
1076
 */
1077
static int use_upper_bound_list(isl_ctx *ctx, int n_upper,
1078
  __isl_keep isl_set *domain, int depth)
1079
222
{
1080
222
  if (n_upper > 0)
1081
222
    return isl_options_get_ast_build_atomic_upper_bound(ctx);
1082
0
  else
1083
0
    return isl_set_dim_has_upper_bound(domain, isl_dim_set, depth);
1084
222
}
1085
1086
/* Fill in the expressions of the for node in graft->node.
1087
 *
1088
 * In particular,
1089
 * - set the initialization part of the loop to the maximum of the lower bounds
1090
 * - extract the increment from the stride of the current dimension
1091
 * - construct the for condition either based on a list of upper bounds
1092
 *  or on a set of upper bound constraints.
1093
 */
1094
static __isl_give isl_ast_graft *set_for_node_expressions(
1095
  __isl_take isl_ast_graft *graft, __isl_keep isl_pw_aff_list *lower,
1096
  int use_list, __isl_keep isl_pw_aff_list *upper_list,
1097
  __isl_keep isl_set *upper_set, __isl_keep isl_ast_build *build)
1098
222
{
1099
222
  isl_ast_node *node;
1100
222
1101
222
  if (!graft)
1102
0
    return NULL;
1103
222
1104
222
  build = isl_ast_build_copy(build);
1105
222
1106
222
  node = graft->node;
1107
222
  node->u.f.init = reduce_list(isl_ast_op_max, lower, build);
1108
222
  node->u.f.inc = for_inc(build);
1109
222
1110
222
  if (!node->u.f.init || !node->u.f.inc)
1111
0
    graft = isl_ast_graft_free(graft);
1112
222
1113
222
  if (use_list)
1114
222
    graft = set_for_cond_from_list(graft, upper_list, build);
1115
0
  else
1116
0
    graft = set_for_cond_from_set(graft, upper_set, build);
1117
222
1118
222
  isl_ast_build_free(build);
1119
222
1120
222
  return graft;
1121
222
}
1122
1123
/* Update "graft" based on "bounds" and "domain" for the generic,
1124
 * non-degenerate, case.
1125
 *
1126
 * "c_lower" and "c_upper" contain the lower and upper bounds
1127
 * that the loop node should express.
1128
 * "domain" is the subset of the intersection of the constraints
1129
 * for which some code is executed.
1130
 *
1131
 * There may be zero lower bounds or zero upper bounds in "constraints"
1132
 * in case the list of constraints was created
1133
 * based on the atomic option or based on separation with explicit bounds.
1134
 * In that case, we use "domain" to derive lower and/or upper bounds.
1135
 *
1136
 * We first compute a list of one or more lower bounds.
1137
 *
1138
 * Then we decide if we want to express the condition as
1139
 *
1140
 *  iterator <= min(list of upper bounds)
1141
 *
1142
 * or as a conjunction of constraints.
1143
 *
1144
 * The set of enforced constraints is then computed either based on
1145
 * a list of upper bounds or on a set of upper bound constraints.
1146
 * We do not compute any enforced constraints if we were forced
1147
 * to compute a lower or upper bound using exact_bound.  The domains
1148
 * of the resulting expressions may imply some bounds on outer dimensions
1149
 * that we do not want to appear in the enforced constraints since
1150
 * they are not actually enforced by the corresponding code.
1151
 *
1152
 * Finally, we fill in the expressions of the for node.
1153
 */
1154
static __isl_give isl_ast_graft *refine_generic_bounds(
1155
  __isl_take isl_ast_graft *graft,
1156
  __isl_take isl_constraint_list *c_lower,
1157
  __isl_take isl_constraint_list *c_upper,
1158
  __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1159
222
{
1160
222
  int depth;
1161
222
  isl_ctx *ctx;
1162
222
  isl_pw_aff_list *lower;
1163
222
  int use_list;
1164
222
  isl_set *upper_set = NULL;
1165
222
  isl_pw_aff_list *upper_list = NULL;
1166
222
  int n_lower, n_upper;
1167
222
1168
222
  if (!graft || !c_lower || !c_upper || !build)
1169
0
    goto error;
1170
222
1171
222
  depth = isl_ast_build_get_depth(build);
1172
222
  ctx = isl_ast_graft_get_ctx(graft);
1173
222
1174
222
  n_lower = isl_constraint_list_n_constraint(c_lower);
1175
222
  n_upper = isl_constraint_list_n_constraint(c_upper);
1176
222
1177
222
  use_list = use_upper_bound_list(ctx, n_upper, domain, depth);
1178
222
1179
222
  lower = lower_bounds(c_lower, depth, domain, build);
1180
222
1181
222
  if (use_list)
1182
222
    upper_list = upper_bounds(c_upper, depth, domain, build);
1183
0
  else if (n_upper > 0)
1184
0
    upper_set = intersect_constraints(c_upper);
1185
0
  else
1186
0
    upper_set = isl_set_universe(isl_set_get_space(domain));
1187
222
1188
222
  if (n_lower == 0 || n_upper == 0)
1189
0
    ;
1190
222
  else if (use_list)
1191
222
    graft = set_enforced_from_list(graft, lower, upper_list);
1192
0
  else
1193
0
    graft = set_enforced_from_set(graft, lower, depth, upper_set);
1194
222
1195
222
  graft = set_for_node_expressions(graft, lower, use_list, upper_list,
1196
222
          upper_set, build);
1197
222
1198
222
  isl_pw_aff_list_free(lower);
1199
222
  isl_pw_aff_list_free(upper_list);
1200
222
  isl_set_free(upper_set);
1201
222
  isl_constraint_list_free(c_lower);
1202
222
  isl_constraint_list_free(c_upper);
1203
222
1204
222
  return graft;
1205
0
error:
1206
0
  isl_constraint_list_free(c_lower);
1207
0
  isl_constraint_list_free(c_upper);
1208
0
  return isl_ast_graft_free(graft);
1209
222
}
1210
1211
/* Internal data structure used inside count_constraints to keep
1212
 * track of the number of constraints that are independent of dimension "pos",
1213
 * the lower bounds in "pos" and the upper bounds in "pos".
1214
 */
1215
struct isl_ast_count_constraints_data {
1216
  int pos;
1217
1218
  int n_indep;
1219
  int n_lower;
1220
  int n_upper;
1221
};
1222
1223
/* Increment data->n_indep, data->lower or data->upper depending
1224
 * on whether "c" is independenct of dimensions data->pos,
1225
 * a lower bound or an upper bound.
1226
 */
1227
static isl_stat count_constraints(__isl_take isl_constraint *c, void *user)
1228
502
{
1229
502
  struct isl_ast_count_constraints_data *data = user;
1230
502
1231
502
  if (isl_constraint_is_lower_bound(c, isl_dim_set, data->pos))
1232
226
    data->n_lower++;
1233
276
  else if (isl_constraint_is_upper_bound(c, isl_dim_set, data->pos))
1234
259
    data->n_upper++;
1235
17
  else
1236
17
    data->n_indep++;
1237
502
1238
502
  isl_constraint_free(c);
1239
502
1240
502
  return isl_stat_ok;
1241
502
}
1242
1243
/* Update "graft" based on "bounds" and "domain" for the generic,
1244
 * non-degenerate, case.
1245
 *
1246
 * "list" respresent the list of bounds that need to be encoded by
1247
 * the for loop.  Only the constraints that involve the iterator
1248
 * are relevant here.  The other constraints are taken care of by
1249
 * the caller and are included in the generated constraints of "build".
1250
 * "domain" is the subset of the intersection of the constraints
1251
 * for which some code is executed.
1252
 * "build" is the build in which graft->node was created.
1253
 *
1254
 * We separate lower bounds, upper bounds and constraints that
1255
 * are independent of the loop iterator.
1256
 *
1257
 * The actual for loop bounds are generated in refine_generic_bounds.
1258
 */
1259
static __isl_give isl_ast_graft *refine_generic_split(
1260
  __isl_take isl_ast_graft *graft, __isl_take isl_constraint_list *list,
1261
  __isl_keep isl_set *domain, __isl_keep isl_ast_build *build)
1262
222
{
1263
222
  struct isl_ast_count_constraints_data data;
1264
222
  isl_constraint_list *lower;
1265
222
  isl_constraint_list *upper;
1266
222
1267
222
  if (!list)
1268
0
    return isl_ast_graft_free(graft);
1269
222
1270
222
  data.pos = isl_ast_build_get_depth(build);
1271
222
1272
222
  list = isl_constraint_list_sort(list, &cmp_constraint, &data.pos);
1273
222
  if (!list)
1274
0
    return isl_ast_graft_free(graft);
1275
222
1276
222
  data.n_indep = data.n_lower = data.n_upper = 0;
1277
222
  if (isl_constraint_list_foreach(list, &count_constraints, &data) < 0) {
1278
0
    isl_constraint_list_free(list);
1279
0
    return isl_ast_graft_free(graft);
1280
0
  }
1281
222
1282
222
  lower = isl_constraint_list_drop(list, 0, data.n_indep);
1283
222
  upper = isl_constraint_list_copy(lower);
1284
222
  lower = isl_constraint_list_drop(lower, data.n_lower, data.n_upper);
1285
222
  upper = isl_constraint_list_drop(upper, 0, data.n_lower);
1286
222
1287
222
  return refine_generic_bounds(graft, lower, upper, domain, build);
1288
222
}
1289
1290
/* Update "graft" based on "bounds" and "domain" for the generic,
1291
 * non-degenerate, case.
1292
 *
1293
 * "bounds" respresent the bounds that need to be encoded by
1294
 * the for loop (or a guard around the for loop).
1295
 * "domain" is the subset of "bounds" for which some code is executed.
1296
 * "build" is the build in which graft->node was created.
1297
 *
1298
 * We break up "bounds" into a list of constraints and continue with
1299
 * refine_generic_split.
1300
 */
1301
static __isl_give isl_ast_graft *refine_generic(
1302
  __isl_take isl_ast_graft *graft,
1303
  __isl_keep isl_basic_set *bounds, __isl_keep isl_set *domain,
1304
  __isl_keep isl_ast_build *build)
1305
222
{
1306
222
  isl_constraint_list *list;
1307
222
1308
222
  if (!build || !graft)
1309
0
    return isl_ast_graft_free(graft);
1310
222
1311
222
  list = isl_basic_set_get_constraint_list(bounds);
1312
222
1313
222
  graft = refine_generic_split(graft, list, domain, build);
1314
222
1315
222
  return graft;
1316
222
}
1317
1318
/* Create a for node for the current level.
1319
 *
1320
 * Mark the for node degenerate if "degenerate" is set.
1321
 */
1322
static __isl_give isl_ast_node *create_for(__isl_keep isl_ast_build *build,
1323
  int degenerate)
1324
222
{
1325
222
  int depth;
1326
222
  isl_id *id;
1327
222
  isl_ast_node *node;
1328
222
1329
222
  if (!build)
1330
0
    return NULL;
1331
222
1332
222
  depth = isl_ast_build_get_depth(build);
1333
222
  id = isl_ast_build_get_iterator_id(build, depth);
1334
222
  node = isl_ast_node_alloc_for(id);
1335
222
  if (degenerate)
1336
0
    node = isl_ast_node_for_mark_degenerate(node);
1337
222
1338
222
  return node;
1339
222
}
1340
1341
/* If the ast_build_exploit_nested_bounds option is set, then return
1342
 * the constraints enforced by all elements in "list".
1343
 * Otherwise, return the universe.
1344
 */
1345
static __isl_give isl_basic_set *extract_shared_enforced(
1346
  __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
1347
2.23k
{
1348
2.23k
  isl_ctx *ctx;
1349
2.23k
  isl_space *space;
1350
2.23k
1351
2.23k
  if (!list)
1352
0
    return NULL;
1353
2.23k
1354
2.23k
  ctx = isl_ast_graft_list_get_ctx(list);
1355
2.23k
  if (isl_options_get_ast_build_exploit_nested_bounds(ctx))
1356
2.23k
    return isl_ast_graft_list_extract_shared_enforced(list, build);
1357
0
1358
0
  space = isl_ast_build_get_space(build, 1);
1359
0
  return isl_basic_set_universe(space);
1360
0
}
1361
1362
/* Return the pending constraints of "build" that are not already taken
1363
 * care of (by a combination of "enforced" and the generated constraints
1364
 * of "build").
1365
 */
1366
static __isl_give isl_set *extract_pending(__isl_keep isl_ast_build *build,
1367
  __isl_keep isl_basic_set *enforced)
1368
2.23k
{
1369
2.23k
  isl_set *guard, *context;
1370
2.23k
1371
2.23k
  guard = isl_ast_build_get_pending(build);
1372
2.23k
  context = isl_set_from_basic_set(isl_basic_set_copy(enforced));
1373
2.23k
  context = isl_set_intersect(context,
1374
2.23k
          isl_ast_build_get_generated(build));
1375
2.23k
  return isl_set_gist(guard, context);
1376
2.23k
}
1377
1378
/* Create an AST node for the current dimension based on
1379
 * the schedule domain "bounds" and return the node encapsulated
1380
 * in an isl_ast_graft.
1381
 *
1382
 * "executed" is the current inverse schedule, taking into account
1383
 * the bounds in "bounds"
1384
 * "domain" is the domain of "executed", with inner dimensions projected out.
1385
 * It may be a strict subset of "bounds" in case "bounds" was created
1386
 * based on the atomic option or based on separation with explicit bounds.
1387
 *
1388
 * "domain" may satisfy additional equalities that result
1389
 * from intersecting "executed" with "bounds" in add_node.
1390
 * It may also satisfy some global constraints that were dropped out because
1391
 * we performed separation with explicit bounds.
1392
 * The very first step is then to copy these constraints to "bounds".
1393
 *
1394
 * Since we may be calling before_each_for and after_each_for
1395
 * callbacks, we record the current inverse schedule in the build.
1396
 *
1397
 * We consider three builds,
1398
 * "build" is the one in which the current level is created,
1399
 * "body_build" is the build in which the next level is created,
1400
 * "sub_build" is essentially the same as "body_build", except that
1401
 * the depth has not been increased yet.
1402
 *
1403
 * "build" already contains information (in strides and offsets)
1404
 * about the strides at the current level, but this information is not
1405
 * reflected in the build->domain.
1406
 * We first add this information and the "bounds" to the sub_build->domain.
1407
 * isl_ast_build_set_loop_bounds adds the stride information and
1408
 * checks whether the current dimension attains
1409
 * only a single value and whether this single value can be represented using
1410
 * a single affine expression.
1411
 * In the first case, the current level is considered "degenerate".
1412
 * In the second, sub-case, the current level is considered "eliminated".
1413
 * Eliminated levels don't need to be reflected in the AST since we can
1414
 * simply plug in the affine expression.  For degenerate, but non-eliminated,
1415
 * levels, we do introduce a for node, but mark is as degenerate so that
1416
 * it can be printed as an assignment of the single value to the loop
1417
 * "iterator".
1418
 *
1419
 * If the current level is eliminated, we explicitly plug in the value
1420
 * for the current level found by isl_ast_build_set_loop_bounds in the
1421
 * inverse schedule.  This ensures that if we are working on a slice
1422
 * of the domain based on information available in the inverse schedule
1423
 * and the build domain, that then this information is also reflected
1424
 * in the inverse schedule.  This operation also eliminates the current
1425
 * dimension from the inverse schedule making sure no inner dimensions depend
1426
 * on the current dimension.  Otherwise, we create a for node, marking
1427
 * it degenerate if appropriate.  The initial for node is still incomplete
1428
 * and will be completed in either refine_degenerate or refine_generic.
1429
 *
1430
 * We then generate a sequence of grafts for the next level,
1431
 * create a surrounding graft for the current level and insert
1432
 * the for node we created (if the current level is not eliminated).
1433
 * Before creating a graft for the current level, we first extract
1434
 * hoistable constraints from the child guards and combine them
1435
 * with the pending constraints in the build.  These constraints
1436
 * are used to simplify the child guards and then added to the guard
1437
 * of the current graft to ensure that they will be generated.
1438
 * If the hoisted guard is a disjunction, then we use it directly
1439
 * to gist the guards on the children before intersect it with the
1440
 * pending constraints.  We do so because this disjunction is typically
1441
 * identical to the guards on the children such that these guards
1442
 * can be effectively removed completely.  After the intersection,
1443
 * the gist operation would have a harder time figuring this out.
1444
 *
1445
 * Finally, we set the bounds of the for loop in either
1446
 * refine_degenerate or refine_generic.
1447
 * We do so in a context where the pending constraints of the build
1448
 * have been replaced by the guard of the current graft.
1449
 */
1450
static __isl_give isl_ast_graft *create_node_scaled(
1451
  __isl_take isl_union_map *executed,
1452
  __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1453
  __isl_take isl_ast_build *build)
1454
2.23k
{
1455
2.23k
  int depth;
1456
2.23k
  int degenerate, eliminated;
1457
2.23k
  isl_basic_set *hull;
1458
2.23k
  isl_basic_set *enforced;
1459
2.23k
  isl_set *guard, *hoisted;
1460
2.23k
  isl_ast_node *node = NULL;
1461
2.23k
  isl_ast_graft *graft;
1462
2.23k
  isl_ast_graft_list *children;
1463
2.23k
  isl_ast_build *sub_build;
1464
2.23k
  isl_ast_build *body_build;
1465
2.23k
1466
2.23k
  domain = isl_ast_build_eliminate_divs(build, domain);
1467
2.23k
  domain = isl_set_detect_equalities(domain);
1468
2.23k
  hull = isl_set_unshifted_simple_hull(isl_set_copy(domain));
1469
2.23k
  bounds = isl_basic_set_intersect(bounds, hull);
1470
2.23k
  build = isl_ast_build_set_executed(build, isl_union_map_copy(executed));
1471
2.23k
1472
2.23k
  depth = isl_ast_build_get_depth(build);
1473
2.23k
  sub_build = isl_ast_build_copy(build);
1474
2.23k
  bounds = isl_basic_set_remove_redundancies(bounds);
1475
2.23k
  bounds = isl_ast_build_specialize_basic_set(sub_build, bounds);
1476
2.23k
  sub_build = isl_ast_build_set_loop_bounds(sub_build,
1477
2.23k
            isl_basic_set_copy(bounds));
1478
2.23k
  degenerate = isl_ast_build_has_value(sub_build);
1479
2.23k
  eliminated = isl_ast_build_has_affine_value(sub_build, depth);
1480
2.23k
  if (degenerate < 0 || eliminated < 0)
1481
0
    executed = isl_union_map_free(executed);
1482
2.23k
  if (!degenerate)
1483
222
    bounds = isl_ast_build_compute_gist_basic_set(build, bounds);
1484
2.23k
  sub_build = isl_ast_build_set_pending_generated(sub_build,
1485
2.23k
            isl_basic_set_copy(bounds));
1486
2.23k
  if (eliminated)
1487
2.01k
    executed = plug_in_values(executed, sub_build);
1488
222
  else
1489
222
    node = create_for(build, degenerate);
1490
2.23k
1491
2.23k
  body_build = isl_ast_build_copy(sub_build);
1492
2.23k
  body_build = isl_ast_build_increase_depth(body_build);
1493
2.23k
  if (!eliminated)
1494
222
    node = before_each_for(node, body_build);
1495
2.23k
  children = generate_next_level(executed,
1496
2.23k
            isl_ast_build_copy(body_build));
1497
2.23k
1498
2.23k
  enforced = extract_shared_enforced(children, build);
1499
2.23k
  guard = extract_pending(sub_build, enforced);
1500
2.23k
  hoisted = isl_ast_graft_list_extract_hoistable_guard(children, build);
1501
2.23k
  if (isl_set_n_basic_set(hoisted) > 1)
1502
2
    children = isl_ast_graft_list_gist_guards(children,
1503
2
                isl_set_copy(hoisted));
1504
2.23k
  guard = isl_set_intersect(guard, hoisted);
1505
2.23k
  if (!eliminated)
1506
222
    guard = add_implied_guards(guard, degenerate, bounds, build);
1507
2.23k
1508
2.23k
  graft = isl_ast_graft_alloc_from_children(children,
1509
2.23k
          isl_set_copy(guard), enforced, build, sub_build);
1510
2.23k
1511
2.23k
  if (!eliminated) {
1512
222
    isl_ast_build *for_build;
1513
222
1514
222
    graft = isl_ast_graft_insert_for(graft, node);
1515
222
    for_build = isl_ast_build_copy(build);
1516
222
    for_build = isl_ast_build_replace_pending_by_guard(for_build,
1517
222
              isl_set_copy(guard));
1518
222
    if (degenerate)
1519
0
      graft = refine_degenerate(graft, for_build, sub_build);
1520
222
    else
1521
222
      graft = refine_generic(graft, bounds,
1522
222
          domain, for_build);
1523
222
    isl_ast_build_free(for_build);
1524
222
  }
1525
2.23k
  isl_set_free(guard);
1526
2.23k
  if (!eliminated)
1527
222
    graft = after_each_for(graft, body_build);
1528
2.23k
1529
2.23k
  isl_ast_build_free(body_build);
1530
2.23k
  isl_ast_build_free(sub_build);
1531
2.23k
  isl_ast_build_free(build);
1532
2.23k
  isl_basic_set_free(bounds);
1533
2.23k
  isl_set_free(domain);
1534
2.23k
1535
2.23k
  return graft;
1536
2.23k
}
1537
1538
/* Internal data structure for checking if all constraints involving
1539
 * the input dimension "depth" are such that the other coefficients
1540
 * are multiples of "m", reducing "m" if they are not.
1541
 * If "m" is reduced all the way down to "1", then the check has failed
1542
 * and we break out of the iteration.
1543
 */
1544
struct isl_check_scaled_data {
1545
  int depth;
1546
  isl_val *m;
1547
};
1548
1549
/* If constraint "c" involves the input dimension data->depth,
1550
 * then make sure that all the other coefficients are multiples of data->m,
1551
 * reducing data->m if needed.
1552
 * Break out of the iteration if data->m has become equal to "1".
1553
 */
1554
static isl_stat constraint_check_scaled(__isl_take isl_constraint *c,
1555
  void *user)
1556
10
{
1557
10
  struct isl_check_scaled_data *data = user;
1558
10
  int i, j, n;
1559
10
  enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_out,
1560
10
            isl_dim_div };
1561
10
1562
10
  if (!isl_constraint_involves_dims(c, isl_dim_in, data->depth, 1)) {
1563
6
    isl_constraint_free(c);
1564
6
    return isl_stat_ok;
1565
6
  }
1566
4
1567
14
  
for (i = 0; 4
i < 4;
++i10
) {
1568
12
    n = isl_constraint_dim(c, t[i]);
1569
22
    for (j = 0; j < n; 
++j10
) {
1570
12
      isl_val *d;
1571
12
1572
12
      if (t[i] == isl_dim_in && 
j == data->depth8
)
1573
4
        continue;
1574
8
      if (!isl_constraint_involves_dims(c, t[i], j, 1))
1575
4
        continue;
1576
4
      d = isl_constraint_get_coefficient_val(c, t[i], j);
1577
4
      data->m = isl_val_gcd(data->m, d);
1578
4
      if (isl_val_is_one(data->m))
1579
2
        break;
1580
12
    }
1581
12
    if (j < n)
1582
2
      break;
1583
12
  }
1584
4
1585
4
  isl_constraint_free(c);
1586
4
1587
4
  return i < 4 ? 
isl_stat_error2
:
isl_stat_ok2
;
1588
10
}
1589
1590
/* For each constraint of "bmap" that involves the input dimension data->depth,
1591
 * make sure that all the other coefficients are multiples of data->m,
1592
 * reducing data->m if needed.
1593
 * Break out of the iteration if data->m has become equal to "1".
1594
 */
1595
static isl_stat basic_map_check_scaled(__isl_take isl_basic_map *bmap,
1596
  void *user)
1597
2
{
1598
2
  isl_stat r;
1599
2
1600
2
  r = isl_basic_map_foreach_constraint(bmap,
1601
2
            &constraint_check_scaled, user);
1602
2
  isl_basic_map_free(bmap);
1603
2
1604
2
  return r;
1605
2
}
1606
1607
/* For each constraint of "map" that involves the input dimension data->depth,
1608
 * make sure that all the other coefficients are multiples of data->m,
1609
 * reducing data->m if needed.
1610
 * Break out of the iteration if data->m has become equal to "1".
1611
 */
1612
static isl_stat map_check_scaled(__isl_take isl_map *map, void *user)
1613
2
{
1614
2
  isl_stat r;
1615
2
1616
2
  r = isl_map_foreach_basic_map(map, &basic_map_check_scaled, user);
1617
2
  isl_map_free(map);
1618
2
1619
2
  return r;
1620
2
}
1621
1622
/* Create an AST node for the current dimension based on
1623
 * the schedule domain "bounds" and return the node encapsulated
1624
 * in an isl_ast_graft.
1625
 *
1626
 * "executed" is the current inverse schedule, taking into account
1627
 * the bounds in "bounds"
1628
 * "domain" is the domain of "executed", with inner dimensions projected out.
1629
 *
1630
 *
1631
 * Before moving on to the actual AST node construction in create_node_scaled,
1632
 * we first check if the current dimension is strided and if we can scale
1633
 * down this stride.  Note that we only do this if the ast_build_scale_strides
1634
 * option is set.
1635
 *
1636
 * In particular, let the current dimension take on values
1637
 *
1638
 *  f + s a
1639
 *
1640
 * with a an integer.  We check if we can find an integer m that (obviously)
1641
 * divides both f and s.
1642
 *
1643
 * If so, we check if the current dimension only appears in constraints
1644
 * where the coefficients of the other variables are multiples of m.
1645
 * We perform this extra check to avoid the risk of introducing
1646
 * divisions by scaling down the current dimension.
1647
 *
1648
 * If so, we scale the current dimension down by a factor of m.
1649
 * That is, we plug in
1650
 *
1651
 *  i = m i'              (1)
1652
 *
1653
 * Note that in principle we could always scale down strided loops
1654
 * by plugging in
1655
 *
1656
 *  i = f + s i'
1657
 *
1658
 * but this may result in i' taking on larger values than the original i,
1659
 * due to the shift by "f".
1660
 * By constrast, the scaling in (1) can only reduce the (absolute) value "i".
1661
 */
1662
static __isl_give isl_ast_graft *create_node(__isl_take isl_union_map *executed,
1663
  __isl_take isl_basic_set *bounds, __isl_take isl_set *domain,
1664
  __isl_take isl_ast_build *build)
1665
2.23k
{
1666
2.23k
  struct isl_check_scaled_data data;
1667
2.23k
  isl_ctx *ctx;
1668
2.23k
  isl_aff *offset;
1669
2.23k
  isl_val *d;
1670
2.23k
1671
2.23k
  ctx = isl_ast_build_get_ctx(build);
1672
2.23k
  if (!isl_options_get_ast_build_scale_strides(ctx))
1673
0
    return create_node_scaled(executed, bounds, domain, build);
1674
2.23k
1675
2.23k
  data.depth = isl_ast_build_get_depth(build);
1676
2.23k
  if (!isl_ast_build_has_stride(build, data.depth))
1677
2.22k
    return create_node_scaled(executed, bounds, domain, build);
1678
7
1679
7
  offset = isl_ast_build_get_offset(build, data.depth);
1680
7
  data.m = isl_ast_build_get_stride(build, data.depth);
1681
7
  if (!data.m)
1682
0
    offset = isl_aff_free(offset);
1683
7
  offset = isl_aff_scale_down_val(offset, isl_val_copy(data.m));
1684
7
  d = isl_aff_get_denominator_val(offset);
1685
7
  if (!d)
1686
0
    executed = isl_union_map_free(executed);
1687
7
1688
7
  if (executed && isl_val_is_divisible_by(data.m, d))
1689
5
    data.m = isl_val_div(data.m, d);
1690
2
  else {
1691
2
    data.m = isl_val_set_si(data.m, 1);
1692
2
    isl_val_free(d);
1693
2
  }
1694
7
1695
7
  if (!isl_val_is_one(data.m)) {
1696
2
    if (isl_union_map_foreach_map(executed, &map_check_scaled,
1697
2
            &data) < 0 &&
1698
2
        !isl_val_is_one(data.m))
1699
0
      executed = isl_union_map_free(executed);
1700
2
  }
1701
7
1702
7
  if (!isl_val_is_one(data.m)) {
1703
0
    isl_space *space;
1704
0
    isl_multi_aff *ma;
1705
0
    isl_aff *aff;
1706
0
    isl_map *map;
1707
0
    isl_union_map *umap;
1708
0
1709
0
    space = isl_ast_build_get_space(build, 1);
1710
0
    space = isl_space_map_from_set(space);
1711
0
    ma = isl_multi_aff_identity(space);
1712
0
    aff = isl_multi_aff_get_aff(ma, data.depth);
1713
0
    aff = isl_aff_scale_val(aff, isl_val_copy(data.m));
1714
0
    ma = isl_multi_aff_set_aff(ma, data.depth, aff);
1715
0
1716
0
    bounds = isl_basic_set_preimage_multi_aff(bounds,
1717
0
            isl_multi_aff_copy(ma));
1718
0
    domain = isl_set_preimage_multi_aff(domain,
1719
0
            isl_multi_aff_copy(ma));
1720
0
    map = isl_map_reverse(isl_map_from_multi_aff(ma));
1721
0
    umap = isl_union_map_from_map(map);
1722
0
    executed = isl_union_map_apply_domain(executed,
1723
0
            isl_union_map_copy(umap));
1724
0
    build = isl_ast_build_scale_down(build, isl_val_copy(data.m),
1725
0
            umap);
1726
0
  }
1727
2.23k
  isl_aff_free(offset);
1728
2.23k
  isl_val_free(data.m);
1729
2.23k
1730
2.23k
  return create_node_scaled(executed, bounds, domain, build);
1731
2.23k
}
1732
1733
/* Add the basic set to the list that "user" points to.
1734
 */
1735
static isl_stat collect_basic_set(__isl_take isl_basic_set *bset, void *user)
1736
304
{
1737
304
  isl_basic_set_list **list = user;
1738
304
1739
304
  *list = isl_basic_set_list_add(*list, bset);
1740
304
1741
304
  return isl_stat_ok;
1742
304
}
1743
1744
/* Extract the basic sets of "set" and collect them in an isl_basic_set_list.
1745
 */
1746
static __isl_give isl_basic_set_list *isl_basic_set_list_from_set(
1747
  __isl_take isl_set *set)
1748
289
{
1749
289
  int n;
1750
289
  isl_ctx *ctx;
1751
289
  isl_basic_set_list *list;
1752
289
1753
289
  if (!set)
1754
0
    return NULL;
1755
289
1756
289
  ctx = isl_set_get_ctx(set);
1757
289
1758
289
  n = isl_set_n_basic_set(set);
1759
289
  list = isl_basic_set_list_alloc(ctx, n);
1760
289
  if (isl_set_foreach_basic_set(set, &collect_basic_set, &list) < 0)
1761
0
    list = isl_basic_set_list_free(list);
1762
289
1763
289
  isl_set_free(set);
1764
289
  return list;
1765
289
}
1766
1767
/* Generate code for the schedule domain "bounds"
1768
 * and add the result to "list".
1769
 *
1770
 * We mainly detect strides here and check if the bounds do not
1771
 * conflict with the current build domain
1772
 * and then pass over control to create_node.
1773
 *
1774
 * "bounds" reflects the bounds on the current dimension and possibly
1775
 * some extra conditions on outer dimensions.
1776
 * It does not, however, include any divs involving the current dimension,
1777
 * so it does not capture any stride constraints.
1778
 * We therefore need to compute that part of the schedule domain that
1779
 * intersects with "bounds" and derive the strides from the result.
1780
 */
1781
static __isl_give isl_ast_graft_list *add_node(
1782
  __isl_take isl_ast_graft_list *list, __isl_take isl_union_map *executed,
1783
  __isl_take isl_basic_set *bounds, __isl_take isl_ast_build *build)
1784
2.94k
{
1785
2.94k
  isl_ast_graft *graft;
1786
2.94k
  isl_set *domain = NULL;
1787
2.94k
  isl_union_set *uset;
1788
2.94k
  int empty, disjoint;
1789
2.94k
1790
2.94k
  uset = isl_union_set_from_basic_set(isl_basic_set_copy(bounds));
1791
2.94k
  executed = isl_union_map_intersect_domain(executed, uset);
1792
2.94k
  empty = isl_union_map_is_empty(executed);
1793
2.94k
  if (empty < 0)
1794
0
    goto error;
1795
2.94k
  if (empty)
1796
0
    goto done;
1797
2.94k
1798
2.94k
  uset = isl_union_map_domain(isl_union_map_copy(executed));
1799
2.94k
  domain = isl_set_from_union_set(uset);
1800
2.94k
  domain = isl_ast_build_specialize(build, domain);
1801
2.94k
1802
2.94k
  domain = isl_set_compute_divs(domain);
1803
2.94k
  domain = isl_ast_build_eliminate_inner(build, domain);
1804
2.94k
  disjoint = isl_set_is_disjoint(domain, build->domain);
1805
2.94k
  if (disjoint < 0)
1806
0
    goto error;
1807
2.94k
  if (disjoint)
1808
712
    goto done;
1809
2.23k
1810
2.23k
  build = isl_ast_build_detect_strides(build, isl_set_copy(domain));
1811
2.23k
1812
2.23k
  graft = create_node(executed, bounds, domain,
1813
2.23k
        isl_ast_build_copy(build));
1814
2.23k
  list = isl_ast_graft_list_add(list, graft);
1815
2.23k
  isl_ast_build_free(build);
1816
2.23k
  return list;
1817
0
error:
1818
0
  list = isl_ast_graft_list_free(list);
1819
712
done:
1820
712
  isl_set_free(domain);
1821
712
  isl_basic_set_free(bounds);
1822
712
  isl_union_map_free(executed);
1823
712
  isl_ast_build_free(build);
1824
712
  return list;
1825
2.94k
}
1826
1827
/* Does any element of i follow or coincide with any element of j
1828
 * at the current depth for equal values of the outer dimensions?
1829
 */
1830
static isl_bool domain_follows_at_depth(__isl_keep isl_basic_set *i,
1831
  __isl_keep isl_basic_set *j, void *user)
1832
6
{
1833
6
  int depth = *(int *) user;
1834
6
  isl_basic_map *test;
1835
6
  isl_bool empty;
1836
6
  int l;
1837
6
1838
6
  test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
1839
6
                isl_basic_set_copy(j));
1840
6
  for (l = 0; l < depth; 
++l0
)
1841
6
    test = isl_basic_map_equate(test, isl_dim_in, l,
1842
0
            isl_dim_out, l);
1843
6
  test = isl_basic_map_order_ge(test, isl_dim_in, depth,
1844
6
          isl_dim_out, depth);
1845
6
  empty = isl_basic_map_is_empty(test);
1846
6
  isl_basic_map_free(test);
1847
6
1848
6
  return empty < 0 ? 
isl_bool_error0
: !empty;
1849
6
}
1850
1851
/* Split up each element of "list" into a part that is related to "bset"
1852
 * according to "gt" and a part that is not.
1853
 * Return a list that consist of "bset" and all the pieces.
1854
 */
1855
static __isl_give isl_basic_set_list *add_split_on(
1856
  __isl_take isl_basic_set_list *list, __isl_take isl_basic_set *bset,
1857
  __isl_keep isl_basic_map *gt)
1858
0
{
1859
0
  int i, n;
1860
0
  isl_basic_set_list *res;
1861
0
1862
0
  if (!list)
1863
0
    bset = isl_basic_set_free(bset);
1864
0
1865
0
  gt = isl_basic_map_copy(gt);
1866
0
  gt = isl_basic_map_intersect_domain(gt, isl_basic_set_copy(bset));
1867
0
  n = isl_basic_set_list_n_basic_set(list);
1868
0
  res = isl_basic_set_list_from_basic_set(bset);
1869
0
  for (i = 0; res && i < n; ++i) {
1870
0
    isl_basic_set *bset;
1871
0
    isl_set *set1, *set2;
1872
0
    isl_basic_map *bmap;
1873
0
    int empty;
1874
0
1875
0
    bset = isl_basic_set_list_get_basic_set(list, i);
1876
0
    bmap = isl_basic_map_copy(gt);
1877
0
    bmap = isl_basic_map_intersect_range(bmap, bset);
1878
0
    bset = isl_basic_map_range(bmap);
1879
0
    empty = isl_basic_set_is_empty(bset);
1880
0
    if (empty < 0)
1881
0
      res = isl_basic_set_list_free(res);
1882
0
    if (empty)  {
1883
0
      isl_basic_set_free(bset);
1884
0
      bset = isl_basic_set_list_get_basic_set(list, i);
1885
0
      res = isl_basic_set_list_add(res, bset);
1886
0
      continue;
1887
0
    }
1888
0
1889
0
    res = isl_basic_set_list_add(res, isl_basic_set_copy(bset));
1890
0
    set1 = isl_set_from_basic_set(bset);
1891
0
    bset = isl_basic_set_list_get_basic_set(list, i);
1892
0
    set2 = isl_set_from_basic_set(bset);
1893
0
    set1 = isl_set_subtract(set2, set1);
1894
0
    set1 = isl_set_make_disjoint(set1);
1895
0
1896
0
    res = isl_basic_set_list_concat(res,
1897
0
              isl_basic_set_list_from_set(set1));
1898
0
  }
1899
0
  isl_basic_map_free(gt);
1900
0
  isl_basic_set_list_free(list);
1901
0
  return res;
1902
0
}
1903
1904
static __isl_give isl_ast_graft_list *generate_sorted_domains(
1905
  __isl_keep isl_basic_set_list *domain_list,
1906
  __isl_keep isl_union_map *executed,
1907
  __isl_keep isl_ast_build *build);
1908
1909
/* Internal data structure for add_nodes.
1910
 *
1911
 * "executed" and "build" are extra arguments to be passed to add_node.
1912
 * "list" collects the results.
1913
 */
1914
struct isl_add_nodes_data {
1915
  isl_union_map *executed;
1916
  isl_ast_build *build;
1917
1918
  isl_ast_graft_list *list;
1919
};
1920
1921
/* Generate code for the schedule domains in "scc"
1922
 * and add the results to "list".
1923
 *
1924
 * The domains in "scc" form a strongly connected component in the ordering.
1925
 * If the number of domains in "scc" is larger than 1, then this means
1926
 * that we cannot determine a valid ordering for the domains in the component.
1927
 * This should be fairly rare because the individual domains
1928
 * have been made disjoint first.
1929
 * The problem is that the domains may be integrally disjoint but not
1930
 * rationally disjoint.  For example, we may have domains
1931
 *
1932
 *  { [i,i] : 0 <= i <= 1 }   and { [i,1-i] : 0 <= i <= 1 }
1933
 *
1934
 * These two domains have an empty intersection, but their rational
1935
 * relaxations do intersect.  It is impossible to order these domains
1936
 * in the second dimension because the first should be ordered before
1937
 * the second for outer dimension equal to 0, while it should be ordered
1938
 * after for outer dimension equal to 1.
1939
 *
1940
 * This may happen in particular in case of unrolling since the domain
1941
 * of each slice is replaced by its simple hull.
1942
 *
1943
 * For each basic set i in "scc" and for each of the following basic sets j,
1944
 * we split off that part of the basic set i that shares the outer dimensions
1945
 * with j and lies before j in the current dimension.
1946
 * We collect all the pieces in a new list that replaces "scc".
1947
 *
1948
 * While the elements in "scc" should be disjoint, we double-check
1949
 * this property to avoid running into an infinite recursion in case
1950
 * they intersect due to some internal error.
1951
 */
1952
static isl_stat add_nodes(__isl_take isl_basic_set_list *scc, void *user)
1953
5
{
1954
5
  struct isl_add_nodes_data *data = user;
1955
5
  int i, n, depth;
1956
5
  isl_basic_set *bset, *first;
1957
5
  isl_basic_set_list *list;
1958
5
  isl_space *space;
1959
5
  isl_basic_map *gt;
1960
5
1961
5
  n = isl_basic_set_list_n_basic_set(scc);
1962
5
  bset = isl_basic_set_list_get_basic_set(scc, 0);
1963
5
  if (n == 1) {
1964
5
    isl_basic_set_list_free(scc);
1965
5
    data->list = add_node(data->list,
1966
5
        isl_union_map_copy(data->executed), bset,
1967
5
        isl_ast_build_copy(data->build));
1968
5
    return data->list ? isl_stat_ok : 
isl_stat_error0
;
1969
5
  }
1970
0
1971
0
  depth = isl_ast_build_get_depth(data->build);
1972
0
  space = isl_basic_set_get_space(bset);
1973
0
  space = isl_space_map_from_set(space);
1974
0
  gt = isl_basic_map_universe(space);
1975
0
  for (i = 0; i < depth; ++i)
1976
0
    gt = isl_basic_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
1977
0
  gt = isl_basic_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
1978
0
1979
0
  first = isl_basic_set_copy(bset);
1980
0
  list = isl_basic_set_list_from_basic_set(bset);
1981
0
  for (i = 1; i < n; ++i) {
1982
0
    int disjoint;
1983
0
1984
0
    bset = isl_basic_set_list_get_basic_set(scc, i);
1985
0
1986
0
    disjoint = isl_basic_set_is_disjoint(bset, first);
1987
0
    if (disjoint < 0)
1988
0
      list = isl_basic_set_list_free(list);
1989
0
    else if (!disjoint)
1990
0
      isl_die(isl_basic_set_list_get_ctx(scc),
1991
0
        isl_error_internal,
1992
0
        "basic sets in scc are assumed to be disjoint",
1993
0
        list = isl_basic_set_list_free(list));
1994
0
1995
0
    list = add_split_on(list, bset, gt);
1996
0
  }
1997
0
  isl_basic_set_free(first);
1998
0
  isl_basic_map_free(gt);
1999
0
  isl_basic_set_list_free(scc);
2000
0
  scc = list;
2001
0
  data->list = isl_ast_graft_list_concat(data->list,
2002
0
        generate_sorted_domains(scc, data->executed, data->build));
2003
0
  isl_basic_set_list_free(scc);
2004
0
2005
0
  return data->list ? isl_stat_ok : isl_stat_error;
2006
5
}
2007
2008
/* Sort the domains in "domain_list" according to the execution order
2009
 * at the current depth (for equal values of the outer dimensions),
2010
 * generate code for each of them, collecting the results in a list.
2011
 * If no code is generated (because the intersection of the inverse schedule
2012
 * with the domains turns out to be empty), then an empty list is returned.
2013
 *
2014
 * The caller is responsible for ensuring that the basic sets in "domain_list"
2015
 * are pair-wise disjoint.  It can, however, in principle happen that
2016
 * two basic sets should be ordered one way for one value of the outer
2017
 * dimensions and the other way for some other value of the outer dimensions.
2018
 * We therefore play safe and look for strongly connected components.
2019
 * The function add_nodes takes care of handling non-trivial components.
2020
 */
2021
static __isl_give isl_ast_graft_list *generate_sorted_domains(
2022
  __isl_keep isl_basic_set_list *domain_list,
2023
  __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2024
307
{
2025
307
  isl_ctx *ctx;
2026
307
  struct isl_add_nodes_data data;
2027
307
  int depth;
2028
307
  int n;
2029
307
2030
307
  if (!domain_list)
2031
0
    return NULL;
2032
307
2033
307
  ctx = isl_basic_set_list_get_ctx(domain_list);
2034
307
  n = isl_basic_set_list_n_basic_set(domain_list);
2035
307
  data.list = isl_ast_graft_list_alloc(ctx, n);
2036
307
  if (n == 0)
2037
0
    return data.list;
2038
307
  if (n == 1)
2039
305
    return add_node(data.list, isl_union_map_copy(executed),
2040
305
      isl_basic_set_list_get_basic_set(domain_list, 0),
2041
305
      isl_ast_build_copy(build));
2042
2
2043
2
  depth = isl_ast_build_get_depth(build);
2044
2
  data.executed = executed;
2045
2
  data.build = build;
2046
2
  if (isl_basic_set_list_foreach_scc(domain_list,
2047
2
          &domain_follows_at_depth, &depth,
2048
2
          &add_nodes, &data) < 0)
2049
0
    data.list = isl_ast_graft_list_free(data.list);
2050
307
2051
307
  return data.list;
2052
307
}
2053
2054
/* Do i and j share any values for the outer dimensions?
2055
 */
2056
static isl_bool shared_outer(__isl_keep isl_basic_set *i,
2057
  __isl_keep isl_basic_set *j, void *user)
2058
19
{
2059
19
  int depth = *(int *) user;
2060
19
  isl_basic_map *test;
2061
19
  isl_bool empty;
2062
19
  int l;
2063
19
2064
19
  test = isl_basic_map_from_domain_and_range(isl_basic_set_copy(i),
2065
19
                isl_basic_set_copy(j));
2066
40
  for (l = 0; l < depth; 
++l21
)
2067
21
    test = isl_basic_map_equate(test, isl_dim_in, l,
2068
21
            isl_dim_out, l);
2069
19
  empty = isl_basic_map_is_empty(test);
2070
19
  isl_basic_map_free(test);
2071
19
2072
19
  return empty < 0 ? 
isl_bool_error0
: !empty;
2073
19
}
2074
2075
/* Internal data structure for generate_sorted_domains_wrap.
2076
 *
2077
 * "n" is the total number of basic sets
2078
 * "executed" and "build" are extra arguments to be passed
2079
 *  to generate_sorted_domains.
2080
 *
2081
 * "single" is set to 1 by generate_sorted_domains_wrap if there
2082
 * is only a single component.
2083
 * "list" collects the results.
2084
 */
2085
struct isl_ast_generate_parallel_domains_data {
2086
  int n;
2087
  isl_union_map *executed;
2088
  isl_ast_build *build;
2089
2090
  int single;
2091
  isl_ast_graft_list *list;
2092
};
2093
2094
/* Call generate_sorted_domains on "scc", fuse the result into a list
2095
 * with either zero or one graft and collect the these single element
2096
 * lists into data->list.
2097
 *
2098
 * If there is only one component, i.e., if the number of basic sets
2099
 * in the current component is equal to the total number of basic sets,
2100
 * then data->single is set to 1 and the result of generate_sorted_domains
2101
 * is not fused.
2102
 */
2103
static isl_stat generate_sorted_domains_wrap(__isl_take isl_basic_set_list *scc,
2104
  void *user)
2105
25
{
2106
25
  struct isl_ast_generate_parallel_domains_data *data = user;
2107
25
  isl_ast_graft_list *list;
2108
25
2109
25
  list = generate_sorted_domains(scc, data->executed, data->build);
2110
25
  data->single = isl_basic_set_list_n_basic_set(scc) == data->n;
2111
25
  if (!data->single)
2112
23
    list = isl_ast_graft_list_fuse(list, data->build);
2113
25
  if (!data->list)
2114
13
    data->list = list;
2115
12
  else
2116
12
    data->list = isl_ast_graft_list_concat(data->list, list);
2117
25
2118
25
  isl_basic_set_list_free(scc);
2119
25
  if (!data->list)
2120
0
    return isl_stat_error;
2121
25
2122
25
  return isl_stat_ok;
2123
25
}
2124
2125
/* Look for any (weakly connected) components in the "domain_list"
2126
 * of domains that share some values of the outer dimensions.
2127
 * That is, domains in different components do not share any values
2128
 * of the outer dimensions.  This means that these components
2129
 * can be freely reordered.
2130
 * Within each of the components, we sort the domains according
2131
 * to the execution order at the current depth.
2132
 *
2133
 * If there is more than one component, then generate_sorted_domains_wrap
2134
 * fuses the result of each call to generate_sorted_domains
2135
 * into a list with either zero or one graft and collects these (at most)
2136
 * single element lists into a bigger list. This means that the elements of the
2137
 * final list can be freely reordered.  In particular, we sort them
2138
 * according to an arbitrary but fixed ordering to ease merging of
2139
 * graft lists from different components.
2140
 */
2141
static __isl_give isl_ast_graft_list *generate_parallel_domains(
2142
  __isl_keep isl_basic_set_list *domain_list,
2143
  __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
2144
295
{
2145
295
  int depth;
2146
295
  struct isl_ast_generate_parallel_domains_data data;
2147
295
2148
295
  if (!domain_list)
2149
0
    return NULL;
2150
295
2151
295
  data.n = isl_basic_set_list_n_basic_set(domain_list);
2152
295
  if (data.n <= 1)
2153
282
    return generate_sorted_domains(domain_list, executed, build);
2154
13
2155
13
  depth = isl_ast_build_get_depth(build);
2156
13
  data.list = NULL;
2157
13
  data.executed = executed;
2158
13
  data.build = build;
2159
13
  data.single = 0;
2160
13
  if (isl_basic_set_list_foreach_scc(domain_list, &shared_outer, &depth,
2161
13
              &generate_sorted_domains_wrap,
2162
13
              &data) < 0)
2163
0
    data.list = isl_ast_graft_list_free(data.list);
2164
13
2165
13
  if (!data.single)
2166
11
    data.list = isl_ast_graft_list_sort_guard(data.list);
2167
295
2168
295
  return data.list;
2169
295
}
2170
2171
/* Internal data for separate_domain.
2172
 *
2173
 * "explicit" is set if we only want to use explicit bounds.
2174
 *
2175
 * "domain" collects the separated domains.
2176
 */
2177
struct isl_separate_domain_data {
2178
  isl_ast_build *build;
2179
  int explicit;
2180
  isl_set *domain;
2181
};
2182
2183
/* Extract implicit bounds on the current dimension for the executed "map".
2184
 *
2185
 * The domain of "map" may involve inner dimensions, so we
2186
 * need to eliminate them.
2187
 */
2188
static __isl_give isl_set *implicit_bounds(__isl_take isl_map *map,
2189
  __isl_keep isl_ast_build *build)
2190
0
{
2191
0
  isl_set *domain;
2192
0
2193
0
  domain = isl_map_domain(map);
2194
0
  domain = isl_ast_build_eliminate(build, domain);
2195
0
2196
0
  return domain;
2197
0
}
2198
2199
/* Extract explicit bounds on the current dimension for the executed "map".
2200
 *
2201
 * Rather than eliminating the inner dimensions as in implicit_bounds,
2202
 * we simply drop any constraints involving those inner dimensions.
2203
 * The idea is that most bounds that are implied by constraints on the
2204
 * inner dimensions will be enforced by for loops and not by explicit guards.
2205
 * There is then no need to separate along those bounds.
2206
 */
2207
static __isl_give isl_set *explicit_bounds(__isl_take isl_map *map,
2208
  __isl_keep isl_ast_build *build)
2209
15
{
2210
15
  isl_set *domain;
2211
15
  int depth, dim;
2212
15
2213
15
  dim = isl_map_dim(map, isl_dim_out);
2214
15
  map = isl_map_drop_constraints_involving_dims(map, isl_dim_out, 0, dim);
2215
15
2216
15
  domain = isl_map_domain(map);
2217
15
  depth = isl_ast_build_get_depth(build);
2218
15
  dim = isl_set_dim(domain, isl_dim_set);
2219
15
  domain = isl_set_detect_equalities(domain);
2220
15
  domain = isl_set_drop_constraints_involving_dims(domain,
2221
15
        isl_dim_set, depth + 1, dim - (depth + 1));
2222
15
  domain = isl_set_remove_divs_involving_dims(domain,
2223
15
        isl_dim_set, depth, 1);
2224
15
  domain = isl_set_remove_unknown_divs(domain);
2225
15
2226
15
  return domain;
2227
15
}
2228
2229
/* Split data->domain into pieces that intersect with the range of "map"
2230
 * and pieces that do not intersect with the range of "map"
2231
 * and then add that part of the range of "map" that does not intersect
2232
 * with data->domain.
2233
 */
2234
static isl_stat separate_domain(__isl_take isl_map *map, void *user)
2235
15
{
2236
15
  struct isl_separate_domain_data *data = user;
2237
15
  isl_set *domain;
2238
15
  isl_set *d1, *d2;
2239
15
2240
15
  if (data->explicit)
2241
15
    domain = explicit_bounds(map, data->build);
2242
0
  else
2243
0
    domain = implicit_bounds(map, data->build);
2244
15
2245
15
  domain = isl_set_coalesce(domain);
2246
15
  domain = isl_set_make_disjoint(domain);
2247
15
  d1 = isl_set_subtract(isl_set_copy(domain), isl_set_copy(data->domain));
2248
15
  d2 = isl_set_subtract(isl_set_copy(data->domain), isl_set_copy(domain));
2249
15
  data->domain = isl_set_intersect(data->domain, domain);
2250
15
  data->domain = isl_set_union(data->domain, d1);
2251
15
  data->domain = isl_set_union(data->domain, d2);
2252
15
2253
15
  return isl_stat_ok;
2254
15
}
2255
2256
/* Separate the schedule domains of "executed".
2257
 *
2258
 * That is, break up the domain of "executed" into basic sets,
2259
 * such that for each basic set S, every element in S is associated with
2260
 * the same domain spaces.
2261
 *
2262
 * "space" is the (single) domain space of "executed".
2263
 */
2264
static __isl_give isl_set *separate_schedule_domains(
2265
  __isl_take isl_space *space, __isl_take isl_union_map *executed,
2266
  __isl_keep isl_ast_build *build)
2267
15
{
2268
15
  struct isl_separate_domain_data data = { build };
2269
15
  isl_ctx *ctx;
2270
15
2271
15
  ctx = isl_ast_build_get_ctx(build);
2272
15
  data.explicit = isl_options_get_ast_build_separation_bounds(ctx) ==
2273
15
            ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT;
2274
15
  data.domain = isl_set_empty(space);
2275
15
  if (isl_union_map_foreach_map(executed, &separate_domain, &data) < 0)
2276
0
    data.domain = isl_set_free(data.domain);
2277
15
2278
15
  isl_union_map_free(executed);
2279
15
  return data.domain;
2280
15
}
2281
2282
/* Temporary data used during the search for a lower bound for unrolling.
2283
 *
2284
 * "build" is the build in which the unrolling will be performed
2285
 * "domain" is the original set for which to find a lower bound
2286
 * "depth" is the dimension for which to find a lower boudn
2287
 * "expansion" is the expansion that needs to be applied to "domain"
2288
 * in the unrolling that will be performed
2289
 *
2290
 * "lower" is the best lower bound found so far.  It is NULL if we have not
2291
 * found any yet.
2292
 * "n" is the corresponding size.  If lower is NULL, then the value of n
2293
 * is undefined.
2294
 * "n_div" is the maximal number of integer divisions in the first
2295
 * unrolled iteration (after expansion).  It is set to -1 if it hasn't
2296
 * been computed yet.
2297
 */
2298
struct isl_find_unroll_data {
2299
  isl_ast_build *build;
2300
  isl_set *domain;
2301
  int depth;
2302
  isl_basic_map *expansion;
2303
2304
  isl_aff *lower;
2305
  int *n;
2306
  int n_div;
2307
};
2308
2309
/* Return the constraint
2310
 *
2311
 *  i_"depth" = aff + offset
2312
 */
2313
static __isl_give isl_constraint *at_offset(int depth, __isl_keep isl_aff *aff,
2314
  int offset)
2315
2.63k
{
2316
2.63k
  aff = isl_aff_copy(aff);
2317
2.63k
  aff = isl_aff_add_coefficient_si(aff, isl_dim_in, depth, -1);
2318
2.63k
  aff = isl_aff_add_constant_si(aff, offset);
2319
2.63k
  return isl_equality_from_aff(aff);
2320
2.63k
}
2321
2322
/* Update *user to the number of integer divsions in the first element
2323
 * of "ma", if it is larger than the current value.
2324
 */
2325
static isl_stat update_n_div(__isl_take isl_set *set,
2326
  __isl_take isl_multi_aff *ma, void *user)
2327
0
{
2328
0
  isl_aff *aff;
2329
0
  int *n = user;
2330
0
  int n_div;
2331
0
2332
0
  aff = isl_multi_aff_get_aff(ma, 0);
2333
0
  n_div = isl_aff_dim(aff, isl_dim_div);
2334
0
  isl_aff_free(aff);
2335
0
  isl_multi_aff_free(ma);
2336
0
  isl_set_free(set);
2337
0
2338
0
  if (n_div > *n)
2339
0
    *n = n_div;
2340
0
2341
0
  return aff ? isl_stat_ok : isl_stat_error;
2342
0
}
2343
2344
/* Get the number of integer divisions in the expression for the iterator
2345
 * value at the first slice in the unrolling based on lower bound "lower",
2346
 * taking into account the expansion that needs to be performed on this slice.
2347
 */
2348
static int get_expanded_n_div(struct isl_find_unroll_data *data,
2349
  __isl_keep isl_aff *lower)
2350
0
{
2351
0
  isl_constraint *c;
2352
0
  isl_set *set;
2353
0
  isl_map *it_map, *expansion;
2354
0
  isl_pw_multi_aff *pma;
2355
0
  int n;
2356
0
2357
0
  c = at_offset(data->depth, lower, 0);
2358
0
  set = isl_set_copy(data->domain);
2359
0
  set = isl_set_add_constraint(set, c);
2360
0
  expansion = isl_map_from_basic_map(isl_basic_map_copy(data->expansion));
2361
0
  set = isl_set_apply(set, expansion);
2362
0
  it_map = isl_ast_build_map_to_iterator(data->build, set);
2363
0
  pma = isl_pw_multi_aff_from_map(it_map);
2364
0
  n = 0;
2365
0
  if (isl_pw_multi_aff_foreach_piece(pma, &update_n_div, &n) < 0)
2366
0
    n = -1;
2367
0
  isl_pw_multi_aff_free(pma);
2368
0
2369
0
  return n;
2370
0
}
2371
2372
/* Is the lower bound "lower" with corresponding iteration count "n"
2373
 * better than the one stored in "data"?
2374
 * If there is no upper bound on the iteration count ("n" is infinity) or
2375
 * if the count is too large, then we cannot use this lower bound.
2376
 * Otherwise, if there was no previous lower bound or
2377
 * if the iteration count of the new lower bound is smaller than
2378
 * the iteration count of the previous lower bound, then we consider
2379
 * the new lower bound to be better.
2380
 * If the iteration count is the same, then compare the number
2381
 * of integer divisions that would be needed to express
2382
 * the iterator value at the first slice in the unrolling
2383
 * according to the lower bound.  If we end up computing this
2384
 * number, then store the lowest value in data->n_div.
2385
 */
2386
static int is_better_lower_bound(struct isl_find_unroll_data *data,
2387
  __isl_keep isl_aff *lower, __isl_keep isl_val *n)
2388
1.43k
{
2389
1.43k
  int cmp;
2390
1.43k
  int n_div;
2391
1.43k
2392
1.43k
  if (!n)
2393
0
    return -1;
2394
1.43k
  if (isl_val_is_infty(n))
2395
0
    return 0;
2396
1.43k
  if (isl_val_cmp_si(n, INT_MAX) > 0)
2397
0
    return 0;
2398
1.43k
  if (!data->lower)
2399
1.37k
    return 1;
2400
59
  cmp = isl_val_cmp_si(n, *data->n);
2401
59
  if (cmp < 0)
2402
51
    return 1;
2403
8
  if (cmp > 0)
2404
8
    return 0;
2405
0
  if (data->n_div < 0)
2406
0
    data->n_div = get_expanded_n_div(data, data->lower);
2407
0
  if (data->n_div < 0)
2408
0
    return -1;
2409
0
  if (data->n_div == 0)
2410
0
    return 0;
2411
0
  n_div = get_expanded_n_div(data, lower);
2412
0
  if (n_div < 0)
2413
0
    return -1;
2414
0
  if (n_div >= data->n_div)
2415
0
    return 0;
2416
0
  data->n_div = n_div;
2417
0
2418
0
  return 1;
2419
0
}
2420
2421
/* Check if we can use "c" as a lower bound and if it is better than
2422
 * any previously found lower bound.
2423
 *
2424
 * If "c" does not involve the dimension at the current depth,
2425
 * then we cannot use it.
2426
 * Otherwise, let "c" be of the form
2427
 *
2428
 *  i >= f(j)/a
2429
 *
2430
 * We compute the maximal value of
2431
 *
2432
 *  -ceil(f(j)/a)) + i + 1
2433
 *
2434
 * over the domain.  If there is such a value "n", then we know
2435
 *
2436
 *  -ceil(f(j)/a)) + i + 1 <= n
2437
 *
2438
 * or
2439
 *
2440
 *  i < ceil(f(j)/a)) + n
2441
 *
2442
 * meaning that we can use ceil(f(j)/a)) as a lower bound for unrolling.
2443
 * We just need to check if we have found any lower bound before and
2444
 * if the new lower bound is better (smaller n or fewer integer divisions)
2445
 * than the previously found lower bounds.
2446
 */
2447
static isl_stat update_unrolling_lower_bound(struct isl_find_unroll_data *data,
2448
  __isl_keep isl_constraint *c)
2449
18.5k
{
2450
18.5k
  isl_aff *aff, *lower;
2451
18.5k
  isl_val *max;
2452
18.5k
  int better;
2453
18.5k
2454
18.5k
  if (!isl_constraint_is_lower_bound(c, isl_dim_set, data->depth))
2455
17.1k
    return isl_stat_ok;
2456
1.43k
2457
1.43k
  lower = isl_constraint_get_bound(c, isl_dim_set, data->depth);
2458
1.43k
  lower = isl_aff_ceil(lower);
2459
1.43k
  aff = isl_aff_copy(lower);
2460
1.43k
  aff = isl_aff_neg(aff);
2461
1.43k
  aff = isl_aff_add_coefficient_si(aff, isl_dim_in, data->depth, 1);
2462
1.43k
  aff = isl_aff_add_constant_si(aff, 1);
2463
1.43k
  max = isl_set_max_val(data->domain, aff);
2464
1.43k
  isl_aff_free(aff);
2465
1.43k
2466
1.43k
  better = is_better_lower_bound(data, lower, max);
2467
1.43k
  if (better < 0 || !better) {
2468
8
    isl_val_free(max);
2469
8
    isl_aff_free(lower);
2470
8
    return better < 0 ? 
isl_stat_error0
: isl_stat_ok;
2471
8
  }
2472
1.42k
2473
1.42k
  isl_aff_free(data->lower);
2474
1.42k
  data->lower = lower;
2475
1.42k
  *data->n = isl_val_get_num_si(max);
2476
1.42k
  isl_val_free(max);
2477
1.42k
2478
1.42k
  return isl_stat_ok;
2479
1.42k
}
2480
2481
/* Check if we can use "c" as a lower bound and if it is better than
2482
 * any previously found lower bound.
2483
 */
2484
static isl_stat constraint_find_unroll(__isl_take isl_constraint *c, void *user)
2485
18.5k
{
2486
18.5k
  struct isl_find_unroll_data *data;
2487
18.5k
  isl_stat r;
2488
18.5k
2489
18.5k
  data = (struct isl_find_unroll_data *) user;
2490
18.5k
  r = update_unrolling_lower_bound(data, c);
2491
18.5k
  isl_constraint_free(c);
2492
18.5k
2493
18.5k
  return r;
2494
18.5k
}
2495
2496
/* Look for a lower bound l(i) on the dimension at "depth"
2497
 * and a size n such that "domain" is a subset of
2498
 *
2499
 *  { [i] : l(i) <= i_d < l(i) + n }
2500
 *
2501
 * where d is "depth" and l(i) depends only on earlier dimensions.
2502
 * Furthermore, try and find a lower bound such that n is as small as possible.
2503
 * In particular, "n" needs to be finite.
2504
 * "build" is the build in which the unrolling will be performed.
2505
 * "expansion" is the expansion that needs to be applied to "domain"
2506
 * in the unrolling that will be performed.
2507
 *
2508
 * Inner dimensions have been eliminated from "domain" by the caller.
2509
 *
2510
 * We first construct a collection of lower bounds on the input set
2511
 * by computing its simple hull.  We then iterate through them,
2512
 * discarding those that we cannot use (either because they do not
2513
 * involve the dimension at "depth" or because they have no corresponding
2514
 * upper bound, meaning that "n" would be unbounded) and pick out the
2515
 * best from the remaining ones.
2516
 *
2517
 * If we cannot find a suitable lower bound, then we consider that
2518
 * to be an error.
2519
 */
2520
static __isl_give isl_aff *find_unroll_lower_bound(
2521
  __isl_keep isl_ast_build *build, __isl_keep isl_set *domain,
2522
  int depth, __isl_keep isl_basic_map *expansion, int *n)
2523
1.37k
{
2524
1.37k
  struct isl_find_unroll_data data =
2525
1.37k
      { build, domain, depth, expansion, NULL, n, -1 };
2526
1.37k
  isl_basic_set *hull;
2527
1.37k
2528
1.37k
  hull = isl_set_simple_hull(isl_set_copy(domain));
2529
1.37k
2530
1.37k
  if (isl_basic_set_foreach_constraint(hull,
2531
1.37k
              &constraint_find_unroll, &data) < 0)
2532
0
    goto error;
2533
1.37k
2534
1.37k
  isl_basic_set_free(hull);
2535
1.37k
2536
1.37k
  if (!data.lower)
2537
1.37k
    
isl_die0
(isl_set_get_ctx(domain), isl_error_invalid,
2538
1.37k
      "cannot find lower bound for unrolling", return NULL);
2539
1.37k
2540
1.37k
  return data.lower;
2541
0
error:
2542
0
  isl_basic_set_free(hull);
2543
0
  return isl_aff_free(data.lower);
2544
1.37k
}
2545
2546
/* Call "fn" on each iteration of the current dimension of "domain".
2547
 * If "init" is not NULL, then it is called with the number of
2548
 * iterations before any call to "fn".
2549
 * Return -1 on failure.
2550
 *
2551
 * Since we are going to be iterating over the individual values,
2552
 * we first check if there are any strides on the current dimension.
2553
 * If there is, we rewrite the current dimension i as
2554
 *
2555
 *    i = stride i' + offset
2556
 *
2557
 * and then iterate over individual values of i' instead.
2558
 *
2559
 * We then look for a lower bound on i' and a size such that the domain
2560
 * is a subset of
2561
 *
2562
 *  { [j,i'] : l(j) <= i' < l(j) + n }
2563
 *
2564
 * and then take slices of the domain at values of i'
2565
 * between l(j) and l(j) + n - 1.
2566
 *
2567
 * We compute the unshifted simple hull of each slice to ensure that
2568
 * we have a single basic set per offset.  The slicing constraint
2569
 * may get simplified away before the unshifted simple hull is taken
2570
 * and may therefore in some rare cases disappear from the result.
2571
 * We therefore explicitly add the constraint back after computing
2572
 * the unshifted simple hull to ensure that the basic sets
2573
 * remain disjoint.  The constraints that are dropped by taking the hull
2574
 * will be taken into account at the next level, as in the case of the
2575
 * atomic option.
2576
 *
2577
 * Finally, we map i' back to i and call "fn".
2578
 */
2579
static int foreach_iteration(__isl_take isl_set *domain,
2580
  __isl_keep isl_ast_build *build, int (*init)(int n, void *user),
2581
  int (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
2582
1.37k
{
2583
1.37k
  int i, n;
2584
1.37k
  int empty;
2585
1.37k
  int depth;
2586
1.37k
  isl_multi_aff *expansion;
2587
1.37k
  isl_basic_map *bmap;
2588
1.37k
  isl_aff *lower = NULL;
2589
1.37k
  isl_ast_build *stride_build;
2590
1.37k
2591
1.37k
  depth = isl_ast_build_get_depth(build);
2592
1.37k
2593
1.37k
  domain = isl_ast_build_eliminate_inner(build, domain);
2594
1.37k
  domain = isl_set_intersect(domain, isl_ast_build_get_domain(build));
2595
1.37k
  stride_build = isl_ast_build_copy(build);
2596
1.37k
  stride_build = isl_ast_build_detect_strides(stride_build,
2597
1.37k
              isl_set_copy(domain));
2598
1.37k
  expansion = isl_ast_build_get_stride_expansion(stride_build);
2599
1.37k
2600
1.37k
  domain = isl_set_preimage_multi_aff(domain,
2601
1.37k
              isl_multi_aff_copy(expansion));
2602
1.37k
  domain = isl_ast_build_eliminate_divs(stride_build, domain);
2603
1.37k
  isl_ast_build_free(stride_build);
2604
1.37k
2605
1.37k
  bmap = isl_basic_map_from_multi_aff(expansion);
2606
1.37k
2607
1.37k
  empty = isl_set_is_empty(domain);
2608
1.37k
  if (empty < 0) {
2609
0
    n = -1;
2610
1.37k
  } else if (empty) {
2611
0
    n = 0;
2612
1.37k
  } else {
2613
1.37k
    lower = find_unroll_lower_bound(build, domain, depth, bmap, &n);
2614
1.37k
    if (!lower)
2615
0
      n = -1;
2616
1.37k
  }
2617
1.37k
  if (n >= 0 && init && init(n, user) < 0)
2618
0
    n = -1;
2619
4.01k
  for (i = 0; i < n; 
++i2.63k
) {
2620
2.63k
    isl_set *set;
2621
2.63k
    isl_basic_set *bset;
2622
2.63k
    isl_constraint *slice;
2623
2.63k
2624
2.63k
    slice = at_offset(depth, lower, i);
2625
2.63k
    set = isl_set_copy(domain);
2626
2.63k
    set = isl_set_add_constraint(set, isl_constraint_copy(slice));
2627
2.63k
    bset = isl_set_unshifted_simple_hull(set);
2628
2.63k
    bset = isl_basic_set_add_constraint(bset, slice);
2629
2.63k
    bset = isl_basic_set_apply(bset, isl_basic_map_copy(bmap));
2630
2.63k
2631
2.63k
    if (fn(bset, user) < 0)
2632
0
      break;
2633
2.63k
  }
2634
1.37k
2635
1.37k
  isl_aff_free(lower);
2636
1.37k
  isl_set_free(domain);
2637
1.37k
  isl_basic_map_free(bmap);
2638
1.37k
2639
1.37k
  return n < 0 || i < n ? 
-10
: 0;
2640
1.37k
}
2641
2642
/* Data structure for storing the results and the intermediate objects
2643
 * of compute_domains.
2644
 *
2645
 * "list" is the main result of the function and contains a list
2646
 * of disjoint basic sets for which code should be generated.
2647
 *
2648
 * "executed" and "build" are inputs to compute_domains.
2649
 * "schedule_domain" is the domain of "executed".
2650
 *
2651
 * "option" constains the domains at the current depth that should by
2652
 * atomic, separated or unrolled.  These domains are as specified by
2653
 * the user, except that inner dimensions have been eliminated and
2654
 * that they have been made pair-wise disjoint.
2655
 *
2656
 * "sep_class" contains the user-specified split into separation classes
2657
 * specialized to the current depth.
2658
 * "done" contains the union of the separation domains that have already
2659
 * been handled.
2660
 */
2661
struct isl_codegen_domains {
2662
  isl_basic_set_list *list;
2663
2664
  isl_union_map *executed;
2665
  isl_ast_build *build;
2666
  isl_set *schedule_domain;
2667
2668
  isl_set *option[4];
2669
2670
  isl_map *sep_class;
2671
  isl_set *done;
2672
};
2673
2674
/* Internal data structure for do_unroll.
2675
 *
2676
 * "domains" stores the results of compute_domains.
2677
 * "class_domain" is the original class domain passed to do_unroll.
2678
 * "unroll_domain" collects the unrolled iterations.
2679
 */
2680
struct isl_ast_unroll_data {
2681
  struct isl_codegen_domains *domains;
2682
  isl_set *class_domain;
2683
  isl_set *unroll_domain;
2684
};
2685
2686
/* Given an iteration of an unrolled domain represented by "bset",
2687
 * add it to data->domains->list.
2688
 * Since we may have dropped some constraints, we intersect with
2689
 * the class domain again to ensure that each element in the list
2690
 * is disjoint from the other class domains.
2691
 */
2692
static int do_unroll_iteration(__isl_take isl_basic_set *bset, void *user)
2693
0
{
2694
0
  struct isl_ast_unroll_data *data = user;
2695
0
  isl_set *set;
2696
0
  isl_basic_set_list *list;
2697
0
2698
0
  set = isl_set_from_basic_set(bset);
2699
0
  data->unroll_domain = isl_set_union(data->unroll_domain,
2700
0
              isl_set_copy(set));
2701
0
  set = isl_set_intersect(set, isl_set_copy(data->class_domain));
2702
0
  set = isl_set_make_disjoint(set);
2703
0
  list = isl_basic_set_list_from_set(set);
2704
0
  data->domains->list = isl_basic_set_list_concat(data->domains->list,
2705
0
              list);
2706
0
2707
0
  return 0;
2708
0
}
2709
2710
/* Extend domains->list with a list of basic sets, one for each value
2711
 * of the current dimension in "domain" and remove the corresponding
2712
 * sets from the class domain.  Return the updated class domain.
2713
 * The divs that involve the current dimension have not been projected out
2714
 * from this domain.
2715
 *
2716
 * We call foreach_iteration to iterate over the individual values and
2717
 * in do_unroll_iteration we collect the individual basic sets in
2718
 * domains->list and their union in data->unroll_domain, which is then
2719
 * used to update the class domain.
2720
 */
2721
static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains,
2722
  __isl_take isl_set *domain, __isl_take isl_set *class_domain)
2723
0
{
2724
0
  struct isl_ast_unroll_data data;
2725
0
2726
0
  if (!domain)
2727
0
    return isl_set_free(class_domain);
2728
0
  if (!class_domain)
2729
0
    return isl_set_free(domain);
2730
0
2731
0
  data.domains = domains;
2732
0
  data.class_domain = class_domain;
2733
0
  data.unroll_domain = isl_set_empty(isl_set_get_space(domain));
2734
0
2735
0
  if (foreach_iteration(domain, domains->build, NULL,
2736
0
        &do_unroll_iteration, &data) < 0)
2737
0
    data.unroll_domain = isl_set_free(data.unroll_domain);
2738
0
2739
0
  class_domain = isl_set_subtract(class_domain, data.unroll_domain);
2740
0
2741
0
  return class_domain;
2742
0
}
2743
2744
/* Add domains to domains->list for each individual value of the current
2745
 * dimension, for that part of the schedule domain that lies in the
2746
 * intersection of the option domain and the class domain.
2747
 * Remove the corresponding sets from the class domain and
2748
 * return the updated class domain.
2749
 *
2750
 * We first break up the unroll option domain into individual pieces
2751
 * and then handle each of them separately.  The unroll option domain
2752
 * has been made disjoint in compute_domains_init_options,
2753
 *
2754
 * Note that we actively want to combine different pieces of the
2755
 * schedule domain that have the same value at the current dimension.
2756
 * We therefore need to break up the unroll option domain before
2757
 * intersecting with class and schedule domain, hoping that the
2758
 * unroll option domain specified by the user is relatively simple.
2759
 */
2760
static __isl_give isl_set *compute_unroll_domains(
2761
  struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2762
30
{
2763
30
  isl_set *unroll_domain;
2764
30
  isl_basic_set_list *unroll_list;
2765
30
  int i, n;
2766
30
  int empty;
2767
30
2768
30
  empty = isl_set_is_empty(domains->option[isl_ast_loop_unroll]);
2769
30
  if (empty < 0)
2770
0
    return isl_set_free(class_domain);
2771
30
  if (empty)
2772
30
    return class_domain;
2773
0
2774
0
  unroll_domain = isl_set_copy(domains->option[isl_ast_loop_unroll]);
2775
0
  unroll_list = isl_basic_set_list_from_set(unroll_domain);
2776
0
2777
0
  n = isl_basic_set_list_n_basic_set(unroll_list);
2778
0
  for (i = 0; i < n; ++i) {
2779
0
    isl_basic_set *bset;
2780
0
2781
0
    bset = isl_basic_set_list_get_basic_set(unroll_list, i);
2782
0
    unroll_domain = isl_set_from_basic_set(bset);
2783
0
    unroll_domain = isl_set_intersect(unroll_domain,
2784
0
                isl_set_copy(class_domain));
2785
0
    unroll_domain = isl_set_intersect(unroll_domain,
2786
0
          isl_set_copy(domains->schedule_domain));
2787
0
2788
0
    empty = isl_set_is_empty(unroll_domain);
2789
0
    if (empty >= 0 && empty) {
2790
0
      isl_set_free(unroll_domain);
2791
0
      continue;
2792
0
    }
2793
0
2794
0
    class_domain = do_unroll(domains, unroll_domain, class_domain);
2795
0
  }
2796
30
2797
30
  isl_basic_set_list_free(unroll_list);
2798
30
2799
30
  return class_domain;
2800
30
}
2801
2802
/* Try and construct a single basic set that includes the intersection of
2803
 * the schedule domain, the atomic option domain and the class domain.
2804
 * Add the resulting basic set(s) to domains->list and remove them
2805
 * from class_domain.  Return the updated class domain.
2806
 *
2807
 * We construct a single domain rather than trying to combine
2808
 * the schedule domains of individual domains because we are working
2809
 * within a single component so that non-overlapping schedule domains
2810
 * should already have been separated.
2811
 * We do however need to make sure that this single domains is a subset
2812
 * of the class domain so that it would not intersect with any other
2813
 * class domains.  This means that we may end up splitting up the atomic
2814
 * domain in case separation classes are being used.
2815
 *
2816
 * "domain" is the intersection of the schedule domain and the class domain,
2817
 * with inner dimensions projected out.
2818
 */
2819
static __isl_give isl_set *compute_atomic_domain(
2820
  struct isl_codegen_domains *domains, __isl_take isl_set *class_domain)
2821
30
{
2822
30
  isl_basic_set *bset;
2823
30
  isl_basic_set_list *list;
2824
30
  isl_set *domain, *atomic_domain;
2825
30
  int empty;
2826
30
2827
30
  domain = isl_set_copy(domains->option[isl_ast_loop_atomic]);
2828
30
  domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2829
30
  domain = isl_set_intersect(domain,
2830
30
        isl_set_copy(domains->schedule_domain));
2831
30
  empty = isl_set_is_empty(domain);
2832
30
  if (empty < 0)
2833
0
    class_domain = isl_set_free(class_domain);
2834
30
  if (empty) {
2835
30
    isl_set_free(domain);
2836
30
    return class_domain;
2837
30
  }
2838
0
2839
0
  domain = isl_ast_build_eliminate(domains->build, domain);
2840
0
  domain = isl_set_coalesce(domain);
2841
0
  bset = isl_set_unshifted_simple_hull(domain);
2842
0
  domain = isl_set_from_basic_set(bset);
2843
0
  atomic_domain = isl_set_copy(domain);
2844
0
  domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2845
0
  class_domain = isl_set_subtract(class_domain, atomic_domain);
2846
0
  domain = isl_set_make_disjoint(domain);
2847
0
  list = isl_basic_set_list_from_set(domain);
2848
0
  domains->list = isl_basic_set_list_concat(domains->list, list);
2849
0
2850
0
  return class_domain;
2851
0
}
2852
2853
/* Split up the schedule domain into uniform basic sets,
2854
 * in the sense that each element in a basic set is associated to
2855
 * elements of the same domains, and add the result to domains->list.
2856
 * Do this for that part of the schedule domain that lies in the
2857
 * intersection of "class_domain" and the separate option domain.
2858
 *
2859
 * "class_domain" may or may not include the constraints
2860
 * of the schedule domain, but this does not make a difference
2861
 * since we are going to intersect it with the domain of the inverse schedule.
2862
 * If it includes schedule domain constraints, then they may involve
2863
 * inner dimensions, but we will eliminate them in separation_domain.
2864
 */
2865
static int compute_separate_domain(struct isl_codegen_domains *domains,
2866
  __isl_keep isl_set *class_domain)
2867
30
{
2868
30
  isl_space *space;
2869
30
  isl_set *domain;
2870
30
  isl_union_map *executed;
2871
30
  isl_basic_set_list *list;
2872
30
  int empty;
2873
30
2874
30
  domain = isl_set_copy(domains->option[isl_ast_loop_separate]);
2875
30
  domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2876
30
  executed = isl_union_map_copy(domains->executed);
2877
30
  executed = isl_union_map_intersect_domain(executed,
2878
30
            isl_union_set_from_set(domain));
2879
30
  empty = isl_union_map_is_empty(executed);
2880
30
  if (empty < 0 || empty) {
2881
30
    isl_union_map_free(executed);
2882
30
    return empty < 0 ? 
-10
: 0;
2883
30
  }
2884
0
2885
0
  space = isl_set_get_space(class_domain);
2886
0
  domain = separate_schedule_domains(space, executed, domains->build);
2887
0
2888
0
  list = isl_basic_set_list_from_set(domain);
2889
0
  domains->list = isl_basic_set_list_concat(domains->list, list);
2890
0
2891
0
  return 0;
2892
0
}
2893
2894
/* Split up the domain at the current depth into disjoint
2895
 * basic sets for which code should be generated separately
2896
 * for the given separation class domain.
2897
 *
2898
 * If any separation classes have been defined, then "class_domain"
2899
 * is the domain of the current class and does not refer to inner dimensions.
2900
 * Otherwise, "class_domain" is the universe domain.
2901
 *
2902
 * We first make sure that the class domain is disjoint from
2903
 * previously considered class domains.
2904
 *
2905
 * The separate domains can be computed directly from the "class_domain".
2906
 *
2907
 * The unroll, atomic and remainder domains need the constraints
2908
 * from the schedule domain.
2909
 *
2910
 * For unrolling, the actual schedule domain is needed (with divs that
2911
 * may refer to the current dimension) so that stride detection can be
2912
 * performed.
2913
 *
2914
 * For atomic and remainder domains, inner dimensions and divs involving
2915
 * the current dimensions should be eliminated.
2916
 * In case we are working within a separation class, we need to intersect
2917
 * the result with the current "class_domain" to ensure that the domains
2918
 * are disjoint from those generated from other class domains.
2919
 *
2920
 * The domain that has been made atomic may be larger than specified
2921
 * by the user since it needs to be representable as a single basic set.
2922
 * This possibly larger domain is removed from class_domain by
2923
 * compute_atomic_domain.  It is computed first so that the extended domain
2924
 * would not overlap with any domains computed before.
2925
 * Similary, the unrolled domains may have some constraints removed and
2926
 * may therefore also be larger than specified by the user.
2927
 *
2928
 * If anything is left after handling separate, unroll and atomic,
2929
 * we split it up into basic sets and append the basic sets to domains->list.
2930
 */
2931
static isl_stat compute_partial_domains(struct isl_codegen_domains *domains,
2932
  __isl_take isl_set *class_domain)
2933
30
{
2934
30
  isl_basic_set_list *list;
2935
30
  isl_set *domain;
2936
30
2937
30
  class_domain = isl_set_subtract(class_domain,
2938
30
          isl_set_copy(domains->done));
2939
30
  domains->done = isl_set_union(domains->done,
2940
30
          isl_set_copy(class_domain));
2941
30
2942
30
  class_domain = compute_atomic_domain(domains, class_domain);
2943
30
  class_domain = compute_unroll_domains(domains, class_domain);
2944
30
2945
30
  domain = isl_set_copy(class_domain);
2946
30
2947
30
  if (compute_separate_domain(domains, domain) < 0)
2948
0
    goto error;
2949
30
  domain = isl_set_subtract(domain,
2950
30
      isl_set_copy(domains->option[isl_ast_loop_separate]));
2951
30
2952
30
  domain = isl_set_intersect(domain,
2953
30
        isl_set_copy(domains->schedule_domain));
2954
30
2955
30
  domain = isl_ast_build_eliminate(domains->build, domain);
2956
30
  domain = isl_set_intersect(domain, isl_set_copy(class_domain));
2957
30
2958
30
  domain = isl_set_coalesce(domain);
2959
30
  domain = isl_set_make_disjoint(domain);
2960
30
2961
30
  list = isl_basic_set_list_from_set(domain);
2962
30
  domains->list = isl_basic_set_list_concat(domains->list, list);
2963
30
2964
30
  isl_set_free(class_domain);
2965
30
2966
30
  return isl_stat_ok;
2967
0
error:
2968
0
  isl_set_free(domain);
2969
0
  isl_set_free(class_domain);
2970
0
  return isl_stat_error;
2971
30
}
2972
2973
/* Split up the domain at the current depth into disjoint
2974
 * basic sets for which code should be generated separately
2975
 * for the separation class identified by "pnt".
2976
 *
2977
 * We extract the corresponding class domain from domains->sep_class,
2978
 * eliminate inner dimensions and pass control to compute_partial_domains.
2979
 */
2980
static isl_stat compute_class_domains(__isl_take isl_point *pnt, void *user)
2981
0
{
2982
0
  struct isl_codegen_domains *domains = user;
2983
0
  isl_set *class_set;
2984
0
  isl_set *domain;
2985
0
  int disjoint;
2986
0
2987
0
  class_set = isl_set_from_point(pnt);
2988
0
  domain = isl_map_domain(isl_map_intersect_range(
2989
0
        isl_map_copy(domains->sep_class), class_set));
2990
0
  domain = isl_ast_build_compute_gist(domains->build, domain);
2991
0
  domain = isl_ast_build_eliminate(domains->build, domain);
2992
0
2993
0
  disjoint = isl_set_plain_is_disjoint(domain, domains->schedule_domain);
2994
0
  if (disjoint < 0)
2995
0
    return isl_stat_error;
2996
0
  if (disjoint) {
2997
0
    isl_set_free(domain);
2998
0
    return isl_stat_ok;
2999
0
  }
3000
0
3001
0
  return compute_partial_domains(domains, domain);
3002
0
}
3003
3004
/* Extract the domains at the current depth that should be atomic,
3005
 * separated or unrolled and store them in option.
3006
 *
3007
 * The domains specified by the user might overlap, so we make
3008
 * them disjoint by subtracting earlier domains from later domains.
3009
 */
3010
static void compute_domains_init_options(isl_set *option[4],
3011
  __isl_keep isl_ast_build *build)
3012
30
{
3013
30
  enum isl_ast_loop_type type, type2;
3014
30
  isl_set *unroll;
3015
30
3016
30
  for (type = isl_ast_loop_atomic;
3017
120
      type <= isl_ast_loop_separate; 
++type90
) {
3018
90
    option[type] = isl_ast_build_get_option_domain(build, type);
3019
180
    for (type2 = isl_ast_loop_atomic; type2 < type; 
++type290
)
3020
90
      option[type] = isl_set_subtract(option[type],
3021
90
            isl_set_copy(option[type2]));
3022
90
  }
3023
30
3024
30
  unroll = option[isl_ast_loop_unroll];
3025
30
  unroll = isl_set_coalesce(unroll);
3026
30
  unroll = isl_set_make_disjoint(unroll);
3027
30
  option[isl_ast_loop_unroll] = unroll;
3028
30
}
3029
3030
/* Split up the domain at the current depth into disjoint
3031
 * basic sets for which code should be generated separately,
3032
 * based on the user-specified options.
3033
 * Return the list of disjoint basic sets.
3034
 *
3035
 * There are three kinds of domains that we need to keep track of.
3036
 * - the "schedule domain" is the domain of "executed"
3037
 * - the "class domain" is the domain corresponding to the currrent
3038
 *  separation class
3039
 * - the "option domain" is the domain corresponding to one of the options
3040
 *  atomic, unroll or separate
3041
 *
3042
 * We first consider the individial values of the separation classes
3043
 * and split up the domain for each of them separately.
3044
 * Finally, we consider the remainder.  If no separation classes were
3045
 * specified, then we call compute_partial_domains with the universe
3046
 * "class_domain".  Otherwise, we take the "schedule_domain" as "class_domain",
3047
 * with inner dimensions removed.  We do this because we want to
3048
 * avoid computing the complement of the class domains (i.e., the difference
3049
 * between the universe and domains->done).
3050
 */
3051
static __isl_give isl_basic_set_list *compute_domains(
3052
  __isl_keep isl_union_map *executed, __isl_keep isl_ast_build *build)
3053
30
{
3054
30
  struct isl_codegen_domains domains;
3055
30
  isl_ctx *ctx;
3056
30
  isl_set *domain;
3057
30
  isl_union_set *schedule_domain;
3058
30
  isl_set *classes;
3059
30
  isl_space *space;
3060
30
  int n_param;
3061
30
  enum isl_ast_loop_type type;
3062
30
  int empty;
3063
30
3064
30
  if (!executed)
3065
0
    return NULL;
3066
30
3067
30
  ctx = isl_union_map_get_ctx(executed);
3068
30
  domains.list = isl_basic_set_list_alloc(ctx, 0);
3069
30
3070
30
  schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
3071
30
  domain = isl_set_from_union_set(schedule_domain);
3072
30
3073
30
  compute_domains_init_options(domains.option, build);
3074
30
3075
30
  domains.sep_class = isl_ast_build_get_separation_class(build);
3076
30
  classes = isl_map_range(isl_map_copy(domains.sep_class));
3077
30
  n_param = isl_set_dim(classes, isl_dim_param);
3078
30
  classes = isl_set_project_out(classes, isl_dim_param, 0, n_param);
3079
30
3080
30
  space = isl_set_get_space(domain);
3081
30
  domains.build = build;
3082
30
  domains.schedule_domain = isl_set_copy(domain);
3083
30
  domains.executed = executed;
3084
30
  domains.done = isl_set_empty(space);
3085
30
3086
30
  if (isl_set_foreach_point(classes, &compute_class_domains, &domains) < 0)
3087
0
    domains.list = isl_basic_set_list_free(domains.list);
3088
30
  isl_set_free(classes);
3089
30
3090
30
  empty = isl_set_is_empty(domains.done);
3091
30
  if (empty < 0) {
3092
0
    domains.list = isl_basic_set_list_free(domains.list);
3093
0
    domain = isl_set_free(domain);
3094
30
  } else if (empty) {
3095
30
    isl_set_free(domain);
3096
30
    domain = isl_set_universe(isl_set_get_space(domains.done));
3097
30
  } else {
3098
0
    domain = isl_ast_build_eliminate(build, domain);
3099
0
  }
3100
30
  if (compute_partial_domains(&domains, domain) < 0)
3101
0
    domains.list = isl_basic_set_list_free(domains.list);
3102
30
3103
30
  isl_set_free(domains.schedule_domain);
3104
30
  isl_set_free(domains.done);
3105
30
  isl_map_free(domains.sep_class);
3106
120
  for (type = isl_ast_loop_atomic; type <= isl_ast_loop_separate; 
++type90
)
3107
90
    isl_set_free(domains.option[type]);
3108
30
3109
30
  return domains.list;
3110
30
}
3111
3112
/* Generate code for a single component, after shifting (if any)
3113
 * has been applied, in case the schedule was specified as a union map.
3114
 *
3115
 * We first split up the domain at the current depth into disjoint
3116
 * basic sets based on the user-specified options.
3117
 * Then we generated code for each of them and concatenate the results.
3118
 */
3119
static __isl_give isl_ast_graft_list *generate_shifted_component_flat(
3120
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3121
30
{
3122
30
  isl_basic_set_list *domain_list;
3123
30
  isl_ast_graft_list *list = NULL;
3124
30
3125
30
  domain_list = compute_domains(executed, build);
3126
30
  list = generate_parallel_domains(domain_list, executed, build);
3127
30
3128
30
  isl_basic_set_list_free(domain_list);
3129
30
  isl_union_map_free(executed);
3130
30
  isl_ast_build_free(build);
3131
30
3132
30
  return list;
3133
30
}
3134
3135
/* Generate code for a single component, after shifting (if any)
3136
 * has been applied, in case the schedule was specified as a schedule tree
3137
 * and the separate option was specified.
3138
 *
3139
 * We perform separation on the domain of "executed" and then generate
3140
 * an AST for each of the resulting disjoint basic sets.
3141
 */
3142
static __isl_give isl_ast_graft_list *generate_shifted_component_tree_separate(
3143
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3144
15
{
3145
15
  isl_space *space;
3146
15
  isl_set *domain;
3147
15
  isl_basic_set_list *domain_list;
3148
15
  isl_ast_graft_list *list;
3149
15
3150
15
  space = isl_ast_build_get_space(build, 1);
3151
15
  domain = separate_schedule_domains(space,
3152
15
          isl_union_map_copy(executed), build);
3153
15
  domain_list = isl_basic_set_list_from_set(domain);
3154
15
3155
15
  list = generate_parallel_domains(domain_list, executed, build);
3156
15
3157
15
  isl_basic_set_list_free(domain_list);
3158
15
  isl_union_map_free(executed);
3159
15
  isl_ast_build_free(build);
3160
15
3161
15
  return list;
3162
15
}
3163
3164
/* Internal data structure for generate_shifted_component_tree_unroll.
3165
 *
3166
 * "executed" and "build" are inputs to generate_shifted_component_tree_unroll.
3167
 * "list" collects the constructs grafts.
3168
 */
3169
struct isl_ast_unroll_tree_data {
3170
  isl_union_map *executed;
3171
  isl_ast_build *build;
3172
  isl_ast_graft_list *list;
3173
};
3174
3175
/* Initialize data->list to a list of "n" elements.
3176
 */
3177
static int init_unroll_tree(int n, void *user)
3178
1.37k
{
3179
1.37k
  struct isl_ast_unroll_tree_data *data = user;
3180
1.37k
  isl_ctx *ctx;
3181
1.37k
3182
1.37k
  ctx = isl_ast_build_get_ctx(data->build);
3183
1.37k
  data->list = isl_ast_graft_list_alloc(ctx, n);
3184
1.37k
3185
1.37k
  return 0;
3186
1.37k
}
3187
3188
/* Given an iteration of an unrolled domain represented by "bset",
3189
 * generate the corresponding AST and add the result to data->list.
3190
 */
3191
static int do_unroll_tree_iteration(__isl_take isl_basic_set *bset, void *user)
3192
2.63k
{
3193
2.63k
  struct isl_ast_unroll_tree_data *data = user;
3194
2.63k
3195
2.63k
  data->list = add_node(data->list, isl_union_map_copy(data->executed),
3196
2.63k
        bset, isl_ast_build_copy(data->build));
3197
2.63k
3198
2.63k
  return 0;
3199
2.63k
}
3200
3201
/* Generate code for a single component, after shifting (if any)
3202
 * has been applied, in case the schedule was specified as a schedule tree
3203
 * and the unroll option was specified.
3204
 *
3205
 * We call foreach_iteration to iterate over the individual values and
3206
 * construct and collect the corresponding grafts in do_unroll_tree_iteration.
3207
 */
3208
static __isl_give isl_ast_graft_list *generate_shifted_component_tree_unroll(
3209
  __isl_take isl_union_map *executed, __isl_take isl_set *domain,
3210
  __isl_take isl_ast_build *build)
3211
1.37k
{
3212
1.37k
  struct isl_ast_unroll_tree_data data = { executed, build, NULL };
3213
1.37k
3214
1.37k
  if (foreach_iteration(domain, build, &init_unroll_tree,
3215
1.37k
        &do_unroll_tree_iteration, &data) < 0)
3216
0
    data.list = isl_ast_graft_list_free(data.list);
3217
1.37k
3218
1.37k
  isl_union_map_free(executed);
3219
1.37k
  isl_ast_build_free(build);
3220
1.37k
3221
1.37k
  return data.list;
3222
1.37k
}
3223
3224
/* Does "domain" involve a disjunction that is purely based on
3225
 * constraints involving only outer dimension?
3226
 *
3227
 * In particular, is there a disjunction such that the constraints
3228
 * involving the current and later dimensions are the same over
3229
 * all the disjuncts?
3230
 */
3231
static isl_bool has_pure_outer_disjunction(__isl_keep isl_set *domain,
3232
  __isl_keep isl_ast_build *build)
3233
250
{
3234
250
  isl_basic_set *hull;
3235
250
  isl_set *shared, *inner;
3236
250
  isl_bool equal;
3237
250
  int depth, dim;
3238
250
3239
250
  if (isl_set_n_basic_set(domain) <= 1)
3240
236
    return isl_bool_false;
3241
14
3242
14
  inner = isl_set_copy(domain);
3243
14
  depth = isl_ast_build_get_depth(build);
3244
14
  dim = isl_set_dim(inner, isl_dim_set);
3245
14
  inner = isl_set_drop_constraints_not_involving_dims(inner,
3246
14
              isl_dim_set, depth, dim - depth);
3247
14
  hull = isl_set_plain_unshifted_simple_hull(isl_set_copy(inner));
3248
14
  shared = isl_set_from_basic_set(hull);
3249
14
  equal = isl_set_plain_is_equal(inner, shared);
3250
14
  isl_set_free(inner);
3251
14
  isl_set_free(shared);
3252
14
3253
14
  return equal;
3254
14
}
3255
3256
/* Generate code for a single component, after shifting (if any)
3257
 * has been applied, in case the schedule was specified as a schedule tree.
3258
 * In particular, handle the base case where there is either no isolated
3259
 * set or we are within the isolated set (in which case "isolated" is set)
3260
 * or the iterations that precede or follow the isolated set.
3261
 *
3262
 * The schedule domain is broken up or combined into basic sets
3263
 * according to the AST generation option specified in the current
3264
 * schedule node, which may be either atomic, separate, unroll or
3265
 * unspecified.  If the option is unspecified, then we currently simply
3266
 * split the schedule domain into disjoint basic sets.
3267
 *
3268
 * In case the separate option is specified, the AST generation is
3269
 * handled by generate_shifted_component_tree_separate.
3270
 * In the other cases, we need the global schedule domain.
3271
 * In the unroll case, the AST generation is then handled by
3272
 * generate_shifted_component_tree_unroll which needs the actual
3273
 * schedule domain (with divs that may refer to the current dimension)
3274
 * so that stride detection can be performed.
3275
 * In the atomic or unspecified case, inner dimensions and divs involving
3276
 * the current dimensions should be eliminated.
3277
 * The result is then either combined into a single basic set or
3278
 * split up into disjoint basic sets.
3279
 * Finally an AST is generated for each basic set and the results are
3280
 * concatenated.
3281
 *
3282
 * If the schedule domain involves a disjunction that is purely based on
3283
 * constraints involving only outer dimension, then it is treated as
3284
 * if atomic was specified.  This ensures that only a single loop
3285
 * is generated instead of a sequence of identical loops with
3286
 * different guards.
3287
 */
3288
static __isl_give isl_ast_graft_list *generate_shifted_component_tree_base(
3289
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
3290
  int isolated)
3291
1.63k
{
3292
1.63k
  isl_bool outer_disjunction;
3293
1.63k
  isl_union_set *schedule_domain;
3294
1.63k
  isl_set *domain;
3295
1.63k
  isl_basic_set_list *domain_list;
3296
1.63k
  isl_ast_graft_list *list;
3297
1.63k
  enum isl_ast_loop_type type;
3298
1.63k
3299
1.63k
  type = isl_ast_build_get_loop_type(build, isolated);
3300
1.63k
  if (type < 0)
3301
0
    goto error;
3302
1.63k
3303
1.63k
  if (type == isl_ast_loop_separate)
3304
15
    return generate_shifted_component_tree_separate(executed,
3305
15
                build);
3306
1.62k
3307
1.62k
  schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
3308
1.62k
  domain = isl_set_from_union_set(schedule_domain);
3309
1.62k
3310
1.62k
  if (type == isl_ast_loop_unroll)
3311
1.37k
    return generate_shifted_component_tree_unroll(executed, domain,
3312
1.37k
                build);
3313
250
3314
250
  domain = isl_ast_build_eliminate(build, domain);
3315
250
  domain = isl_set_coalesce(domain);
3316
250
3317
250
  outer_disjunction = has_pure_outer_disjunction(domain, build);
3318
250
  if (outer_disjunction < 0)
3319
0
    domain = isl_set_free(domain);
3320
250
3321
250
  if (outer_disjunction || 
type == isl_ast_loop_atomic244
) {
3322
6
    isl_basic_set *hull;
3323
6
    hull = isl_set_unshifted_simple_hull(domain);
3324
6
    domain_list = isl_basic_set_list_from_basic_set(hull);
3325
244
  } else {
3326
244
    domain = isl_set_make_disjoint(domain);
3327
244
    domain_list = isl_basic_set_list_from_set(domain);
3328
244
  }
3329
250
3330
250
  list = generate_parallel_domains(domain_list, executed, build);
3331
250
3332
250
  isl_basic_set_list_free(domain_list);
3333
250
  isl_union_map_free(executed);
3334
250
  isl_ast_build_free(build);
3335
250
3336
250
  return list;
3337
0
error:
3338
0
  isl_union_map_free(executed);
3339
0
  isl_ast_build_free(build);
3340
0
  return NULL;
3341
1.63k
}
3342
3343
/* Extract out the disjunction imposed by "domain" on the outer
3344
 * schedule dimensions.
3345
 *
3346
 * In particular, remove all inner dimensions from "domain" (including
3347
 * the current dimension) and then remove the constraints that are shared
3348
 * by all disjuncts in the result.
3349
 */
3350
static __isl_give isl_set *extract_disjunction(__isl_take isl_set *domain,
3351
  __isl_keep isl_ast_build *build)
3352
379
{
3353
379
  isl_set *hull;
3354
379
  int depth, dim;
3355
379
3356
379
  domain = isl_ast_build_specialize(build, domain);
3357
379
  depth = isl_ast_build_get_depth(build);
3358
379
  dim = isl_set_dim(domain, isl_dim_set);
3359
379
  domain = isl_set_eliminate(domain, isl_dim_set, depth, dim - depth);
3360
379
  domain = isl_set_remove_unknown_divs(domain);
3361
379
  hull = isl_set_copy(domain);
3362
379
  hull = isl_set_from_basic_set(isl_set_unshifted_simple_hull(hull));
3363
379
  domain = isl_set_gist(domain, hull);
3364
379
3365
379
  return domain;
3366
379
}
3367
3368
/* Add "guard" to the grafts in "list".
3369
 * "build" is the outer AST build, while "sub_build" includes "guard"
3370
 * in its generated domain.
3371
 *
3372
 * First combine the grafts into a single graft and then add the guard.
3373
 * If the list is empty, or if some error occurred, then simply return
3374
 * the list.
3375
 */
3376
static __isl_give isl_ast_graft_list *list_add_guard(
3377
  __isl_take isl_ast_graft_list *list, __isl_keep isl_set *guard,
3378
  __isl_keep isl_ast_build *build, __isl_keep isl_ast_build *sub_build)
3379
379
{
3380
379
  isl_ast_graft *graft;
3381
379
3382
379
  list = isl_ast_graft_list_fuse(list, sub_build);
3383
379
3384
379
  if (isl_ast_graft_list_n_ast_graft(list) != 1)
3385
375
    return list;
3386
4
3387
4
  graft = isl_ast_graft_list_get_ast_graft(list, 0);
3388
4
  graft = isl_ast_graft_add_guard(graft, isl_set_copy(guard), build);
3389
4
  list = isl_ast_graft_list_set_ast_graft(list, 0, graft);
3390
4
3391
4
  return list;
3392
4
}
3393
3394
/* Generate code for a single component, after shifting (if any)
3395
 * has been applied, in case the schedule was specified as a schedule tree.
3396
 * In particular, do so for the specified subset of the schedule domain.
3397
 *
3398
 * If we are outside of the isolated part, then "domain" may include
3399
 * a disjunction.  Explicitly generate this disjunction at this point
3400
 * instead of relying on the disjunction getting hoisted back up
3401
 * to this level.
3402
 */
3403
static __isl_give isl_ast_graft_list *generate_shifted_component_tree_part(
3404
  __isl_keep isl_union_map *executed, __isl_take isl_set *domain,
3405
  __isl_keep isl_ast_build *build, int isolated)
3406
1.72k
{
3407
1.72k
  isl_union_set *uset;
3408
1.72k
  isl_ast_graft_list *list;
3409
1.72k
  isl_ast_build *sub_build;
3410
1.72k
  int empty;
3411
1.72k
3412
1.72k
  uset = isl_union_set_from_set(isl_set_copy(domain));
3413
1.72k
  executed = isl_union_map_copy(executed);
3414
1.72k
  executed = isl_union_map_intersect_domain(executed, uset);
3415
1.72k
  empty = isl_union_map_is_empty(executed);
3416
1.72k
  if (empty < 0)
3417
0
    goto error;
3418
1.72k
  if (empty) {
3419
914
    isl_ctx *ctx;
3420
914
    isl_union_map_free(executed);
3421
914
    isl_set_free(domain);
3422
914
    ctx = isl_ast_build_get_ctx(build);
3423
914
    return isl_ast_graft_list_alloc(ctx, 0);
3424
914
  }
3425
810
3426
810
  sub_build = isl_ast_build_copy(build);
3427
810
  if (!isolated) {
3428
379
    domain = extract_disjunction(domain, build);
3429
379
    sub_build = isl_ast_build_restrict_generated(sub_build,
3430
379
              isl_set_copy(domain));
3431
379
  }
3432
810
  list = generate_shifted_component_tree_base(executed,
3433
810
        isl_ast_build_copy(sub_build), isolated);
3434
810
  if (!isolated)
3435
379
    list = list_add_guard(list, domain, build, sub_build);
3436
810
  isl_ast_build_free(sub_build);
3437
810
  isl_set_free(domain);
3438
810
  return list;
3439
0
error:
3440
0
  isl_union_map_free(executed);
3441
0
  isl_set_free(domain);
3442
0
  return NULL;
3443
1.72k
}
3444
3445
/* Generate code for a single component, after shifting (if any)
3446
 * has been applied, in case the schedule was specified as a schedule tree.
3447
 * In particular, do so for the specified sequence of subsets
3448
 * of the schedule domain, "before", "isolated", "after" and "other",
3449
 * where only the "isolated" part is considered to be isolated.
3450
 */
3451
static __isl_give isl_ast_graft_list *generate_shifted_component_parts(
3452
  __isl_take isl_union_map *executed, __isl_take isl_set *before,
3453
  __isl_take isl_set *isolated, __isl_take isl_set *after,
3454
  __isl_take isl_set *other, __isl_take isl_ast_build *build)
3455
431
{
3456
431
  isl_ast_graft_list *list, *res;
3457
431
3458
431
  res = generate_shifted_component_tree_part(executed, before, build, 0);
3459
431
  list = generate_shifted_component_tree_part(executed, isolated,
3460
431
                build, 1);
3461
431
  res = isl_ast_graft_list_concat(res, list);
3462
431
  list = generate_shifted_component_tree_part(executed, after, build, 0);
3463
431
  res = isl_ast_graft_list_concat(res, list);
3464
431
  list = generate_shifted_component_tree_part(executed, other, build, 0);
3465
431
  res = isl_ast_graft_list_concat(res, list);
3466
431
3467
431
  isl_union_map_free(executed);
3468
431
  isl_ast_build_free(build);
3469
431
3470
431
  return res;
3471
431
}
3472
3473
/* Does "set" intersect "first", but not "second"?
3474
 */
3475
static isl_bool only_intersects_first(__isl_keep isl_set *set,
3476
  __isl_keep isl_set *first, __isl_keep isl_set *second)
3477
431
{
3478
431
  isl_bool disjoint;
3479
431
3480
431
  disjoint = isl_set_is_disjoint(set, first);
3481
431
  if (disjoint < 0)
3482
0
    return isl_bool_error;
3483
431
  if (disjoint)
3484
427
    return isl_bool_false;
3485
4
3486
4
  return isl_set_is_disjoint(set, second);
3487
4
}
3488
3489
/* Generate code for a single component, after shifting (if any)
3490
 * has been applied, in case the schedule was specified as a schedule tree.
3491
 * In particular, do so in case of isolation where there is
3492
 * only an "isolated" part and an "after" part.
3493
 * "dead1" and "dead2" are freed by this function in order to simplify
3494
 * the caller.
3495
 *
3496
 * The "before" and "other" parts are set to empty sets.
3497
 */
3498
static __isl_give isl_ast_graft_list *generate_shifted_component_only_after(
3499
  __isl_take isl_union_map *executed, __isl_take isl_set *isolated,
3500
  __isl_take isl_set *after, __isl_take isl_ast_build *build,
3501
  __isl_take isl_set *dead1, __isl_take isl_set *dead2)
3502
4
{
3503
4
  isl_set *empty;
3504
4
3505
4
  empty = isl_set_empty(isl_set_get_space(after));
3506
4
  isl_set_free(dead1);
3507
4
  isl_set_free(dead2);
3508
4
  return generate_shifted_component_parts(executed, isl_set_copy(empty),
3509
4
            isolated, after, empty, build);
3510
4
}
3511
3512
/* Generate code for a single component, after shifting (if any)
3513
 * has been applied, in case the schedule was specified as a schedule tree.
3514
 *
3515
 * We first check if the user has specified an isolated schedule domain
3516
 * and that we are not already outside of this isolated schedule domain.
3517
 * If so, we break up the schedule domain into iterations that
3518
 * precede the isolated domain, the isolated domain itself,
3519
 * the iterations that follow the isolated domain and
3520
 * the remaining iterations (those that are incomparable
3521
 * to the isolated domain).
3522
 * We generate an AST for each piece and concatenate the results.
3523
 *
3524
 * In the special case where at least one element of the schedule
3525
 * domain that does not belong to the isolated domain needs
3526
 * to be scheduled after this isolated domain, but none of those
3527
 * elements need to be scheduled before, break up the schedule domain
3528
 * in only two parts, the isolated domain, and a part that will be
3529
 * scheduled after the isolated domain.
3530
 *
3531
 * If no isolated set has been specified, then we generate an
3532
 * AST for the entire inverse schedule.
3533
 */
3534
static __isl_give isl_ast_graft_list *generate_shifted_component_tree(
3535
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3536
1.25k
{
3537
1.25k
  int i, depth;
3538
1.25k
  int empty, has_isolate;
3539
1.25k
  isl_space *space;
3540
1.25k
  isl_union_set *schedule_domain;
3541
1.25k
  isl_set *domain;
3542
1.25k
  isl_basic_set *hull;
3543
1.25k
  isl_set *isolated, *before, *after, *test;
3544
1.25k
  isl_map *gt, *lt;
3545
1.25k
  isl_bool pure;
3546
1.25k
3547
1.25k
  build = isl_ast_build_extract_isolated(build);
3548
1.25k
  has_isolate = isl_ast_build_has_isolated(build);
3549
1.25k
  if (has_isolate < 0)
3550
0
    executed = isl_union_map_free(executed);
3551
1.25k
  else if (!has_isolate)
3552
365
    return generate_shifted_component_tree_base(executed, build, 0);
3553
894
3554
894
  schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
3555
894
  domain = isl_set_from_union_set(schedule_domain);
3556
894
3557
894
  isolated = isl_ast_build_get_isolated(build);
3558
894
  isolated = isl_set_intersect(isolated, isl_set_copy(domain));
3559
894
  test = isl_ast_build_specialize(build, isl_set_copy(isolated));
3560
894
  empty = isl_set_is_empty(test);
3561
894
  isl_set_free(test);
3562
894
  if (empty < 0)
3563
0
    goto error;
3564
894
  if (empty) {
3565
463
    isl_set_free(isolated);
3566
463
    isl_set_free(domain);
3567
463
    return generate_shifted_component_tree_base(executed, build, 0);
3568
463
  }
3569
431
  isolated = isl_ast_build_eliminate(build, isolated);
3570
431
  hull = isl_set_unshifted_simple_hull(isolated);
3571
431
  isolated = isl_set_from_basic_set(hull);
3572
431
3573
431
  depth = isl_ast_build_get_depth(build);
3574
431
  space = isl_space_map_from_set(isl_set_get_space(isolated));
3575
431
  gt = isl_map_universe(space);
3576
3.77k
  for (i = 0; i < depth; 
++i3.33k
)
3577
3.33k
    gt = isl_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
3578
431
  gt = isl_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
3579
431
  lt = isl_map_reverse(isl_map_copy(gt));
3580
431
  before = isl_set_apply(isl_set_copy(isolated), gt);
3581
431
  after = isl_set_apply(isl_set_copy(isolated), lt);
3582
431
3583
431
  domain = isl_set_subtract(domain, isl_set_copy(isolated));
3584
431
  pure = only_intersects_first(domain, after, before);
3585
431
  if (pure < 0)
3586
0
    executed = isl_union_map_free(executed);
3587
431
  else if (pure)
3588
4
    return generate_shifted_component_only_after(executed, isolated,
3589
4
            domain, build, before, after);
3590
427
  domain = isl_set_subtract(domain, isl_set_copy(before));
3591
427
  domain = isl_set_subtract(domain, isl_set_copy(after));
3592
427
  after = isl_set_subtract(after, isl_set_copy(isolated));
3593
427
  after = isl_set_subtract(after, isl_set_copy(before));
3594
427
  before = isl_set_subtract(before, isl_set_copy(isolated));
3595
427
3596
427
  return generate_shifted_component_parts(executed, before, isolated,
3597
427
            after, domain, build);
3598
0
error:
3599
0
  isl_set_free(domain);
3600
0
  isl_set_free(isolated);
3601
0
  isl_union_map_free(executed);
3602
0
  isl_ast_build_free(build);
3603
0
  return NULL;
3604
1.25k
}
3605
3606
/* Generate code for a single component, after shifting (if any)
3607
 * has been applied.
3608
 *
3609
 * Call generate_shifted_component_tree or generate_shifted_component_flat
3610
 * depending on whether the schedule was specified as a schedule tree.
3611
 */
3612
static __isl_give isl_ast_graft_list *generate_shifted_component(
3613
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
3614
1.28k
{
3615
1.28k
  if (isl_ast_build_has_schedule_node(build))
3616
1.25k
    return generate_shifted_component_tree(executed, build);
3617
30
  else
3618
30
    return generate_shifted_component_flat(executed, build);
3619
1.28k
}
3620
3621
struct isl_set_map_pair {
3622
  isl_set *set;
3623
  isl_map *map;
3624
};
3625
3626
/* Given an array "domain" of isl_set_map_pairs and an array "order"
3627
 * of indices into the "domain" array,
3628
 * return the union of the "map" fields of the elements
3629
 * indexed by the first "n" elements of "order".
3630
 */
3631
static __isl_give isl_union_map *construct_component_executed(
3632
  struct isl_set_map_pair *domain, int *order, int n)
3633
48
{
3634
48
  int i;
3635
48
  isl_map *map;
3636
48
  isl_union_map *executed;
3637
48
3638
48
  map = isl_map_copy(domain[order[0]].map);
3639
48
  executed = isl_union_map_from_map(map);
3640
74
  for (i = 1; i < n; 
++i26
) {
3641
26
    map = isl_map_copy(domain[order[i]].map);
3642
26
    executed = isl_union_map_add_map(executed, map);
3643
26
  }
3644
48
3645
48
  return executed;
3646
48
}
3647
3648
/* Generate code for a single component, after shifting (if any)
3649
 * has been applied.
3650
 *
3651
 * The component inverse schedule is specified as the "map" fields
3652
 * of the elements of "domain" indexed by the first "n" elements of "order".
3653
 */
3654
static __isl_give isl_ast_graft_list *generate_shifted_component_from_list(
3655
  struct isl_set_map_pair *domain, int *order, int n,
3656
  __isl_take isl_ast_build *build)
3657
48
{
3658
48
  isl_union_map *executed;
3659
48
3660
48
  executed = construct_component_executed(domain, order, n);
3661
48
  return generate_shifted_component(executed, build);
3662
48
}
3663
3664
/* Does set dimension "pos" of "set" have an obviously fixed value?
3665
 */
3666
static int dim_is_fixed(__isl_keep isl_set *set, int pos)
3667
86
{
3668
86
  int fixed;
3669
86
  isl_val *v;
3670
86
3671
86
  v = isl_set_plain_get_val_if_fixed(set, isl_dim_set, pos);
3672
86
  if (!v)
3673
0
    return -1;
3674
86
  fixed = !isl_val_is_nan(v);
3675
86
  isl_val_free(v);
3676
86
3677
86
  return fixed;
3678
86
}
3679
3680
/* Given an array "domain" of isl_set_map_pairs and an array "order"
3681
 * of indices into the "domain" array,
3682
 * do all (except for at most one) of the "set" field of the elements
3683
 * indexed by the first "n" elements of "order" have a fixed value
3684
 * at position "depth"?
3685
 */
3686
static int at_most_one_non_fixed(struct isl_set_map_pair *domain,
3687
  int *order, int n, int depth)
3688
19
{
3689
19
  int i;
3690
19
  int non_fixed = -1;
3691
19
3692
40
  for (i = 0; i < n; 
++i21
) {
3693
38
    int f;
3694
38
3695
38
    f = dim_is_fixed(domain[order[i]].set, depth);
3696
38
    if (f < 0)
3697
0
      return -1;
3698
38
    if (f)
3699
2
      continue;
3700
36
    if (non_fixed >= 0)
3701
17
      return 0;
3702
19
    non_fixed = i;
3703
19
  }
3704
19
3705
19
  
return 12
;
3706
19
}
3707
3708
/* Given an array "domain" of isl_set_map_pairs and an array "order"
3709
 * of indices into the "domain" array,
3710
 * eliminate the inner dimensions from the "set" field of the elements
3711
 * indexed by the first "n" elements of "order", provided the current
3712
 * dimension does not have a fixed value.
3713
 *
3714
 * Return the index of the first element in "order" with a corresponding
3715
 * "set" field that does not have an (obviously) fixed value.
3716
 */
3717
static int eliminate_non_fixed(struct isl_set_map_pair *domain,
3718
  int *order, int n, int depth, __isl_keep isl_ast_build *build)
3719
17
{
3720
17
  int i;
3721
17
  int base = -1;
3722
17
3723
60
  for (i = n - 1; i >= 0; 
--i43
) {
3724
43
    int f;
3725
43
    f = dim_is_fixed(domain[order[i]].set, depth);
3726
43
    if (f < 0)
3727
0
      return -1;
3728
43
    if (f)
3729
0
      continue;
3730
43
    domain[order[i]].set = isl_ast_build_eliminate_inner(build,
3731
43
              domain[order[i]].set);
3732
43
    base = i;
3733
43
  }
3734
17
3735
17
  return base;
3736
17
}
3737
3738
/* Given an array "domain" of isl_set_map_pairs and an array "order"
3739
 * of indices into the "domain" array,
3740
 * find the element of "domain" (amongst those indexed by the first "n"
3741
 * elements of "order") with the "set" field that has the smallest
3742
 * value for the current iterator.
3743
 *
3744
 * Note that the domain with the smallest value may depend on the parameters
3745
 * and/or outer loop dimension.  Since the result of this function is only
3746
 * used as heuristic, we only make a reasonable attempt at finding the best
3747
 * domain, one that should work in case a single domain provides the smallest
3748
 * value for the current dimension over all values of the parameters
3749
 * and outer dimensions.
3750
 *
3751
 * In particular, we compute the smallest value of the first domain
3752
 * and replace it by that of any later domain if that later domain
3753
 * has a smallest value that is smaller for at least some value
3754
 * of the parameters and outer dimensions.
3755
 */
3756
static int first_offset(struct isl_set_map_pair *domain, int *order, int n,
3757
  __isl_keep isl_ast_build *build)
3758
1
{
3759
1
  int i;
3760
1
  isl_map *min_first;
3761
1
  int first = 0;
3762
1
3763
1
  min_first = isl_ast_build_map_to_iterator(build,
3764
1
          isl_set_copy(domain[order[0]].set));
3765
1
  min_first = isl_map_lexmin(min_first);
3766
1
3767
3
  for (i = 1; i < n; 
++i2
) {
3768
2
    isl_map *min, *test;
3769
2
    int empty;
3770
2
3771
2
    min = isl_ast_build_map_to_iterator(build,
3772
2
          isl_set_copy(domain[order[i]].set));
3773
2
    min = isl_map_lexmin(min);
3774
2
    test = isl_map_copy(min);
3775
2
    test = isl_map_apply_domain(isl_map_copy(min_first), test);
3776
2
    test = isl_map_order_lt(test, isl_dim_in, 0, isl_dim_out, 0);
3777
2
    empty = isl_map_is_empty(test);
3778
2
    isl_map_free(test);
3779
2
    if (empty >= 0 && !empty) {
3780
1
      isl_map_free(min_first);
3781
1
      first = i;
3782
1
      min_first = min;
3783
1
    } else
3784
1
      isl_map_free(min);
3785
2
3786
2
    if (empty < 0)
3787
0
      break;
3788
2
  }
3789
1
3790
1
  isl_map_free(min_first);
3791
1
3792
1
  return i < n ? 
-10
: first;
3793
1
}
3794
3795
/* Construct a shifted inverse schedule based on the original inverse schedule,
3796
 * the stride and the offset.
3797
 *
3798
 * The original inverse schedule is specified as the "map" fields
3799
 * of the elements of "domain" indexed by the first "n" elements of "order".
3800
 *
3801
 * "stride" and "offset" are such that the difference
3802
 * between the values of the current dimension of domain "i"
3803
 * and the values of the current dimension for some reference domain are
3804
 * equal to
3805
 *
3806
 *  stride * integer + offset[i]
3807
 *
3808
 * Moreover, 0 <= offset[i] < stride.
3809
 *
3810
 * For each domain, we create a map
3811
 *
3812
 *  { [..., j, ...] -> [..., j - offset[i], offset[i], ....] }
3813
 *
3814
 * where j refers to the current dimension and the other dimensions are
3815
 * unchanged, and apply this map to the original schedule domain.
3816
 *
3817
 * For example, for the original schedule
3818
 *
3819
 *  { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
3820
 *
3821
 * and assuming the offset is 0 for the A domain and 1 for the B domain,
3822
 * we apply the mapping
3823
 *
3824
 *  { [j] -> [j, 0] }
3825
 *
3826
 * to the schedule of the "A" domain and the mapping
3827
 *
3828
 *  { [j - 1] -> [j, 1] }
3829
 *
3830
 * to the schedule of the "B" domain.
3831
 *
3832
 *
3833
 * Note that after the transformation, the differences between pairs
3834
 * of values of the current dimension over all domains are multiples
3835
 * of stride and that we have therefore exposed the stride.
3836
 *
3837
 *
3838
 * To see that the mapping preserves the lexicographic order,
3839
 * first note that each of the individual maps above preserves the order.
3840
 * If the value of the current iterator is j1 in one domain and j2 in another,
3841
 * then if j1 = j2, we know that the same map is applied to both domains
3842
 * and the order is preserved.
3843
 * Otherwise, let us assume, without loss of generality, that j1 < j2.
3844
 * If c1 >= c2 (with c1 and c2 the corresponding offsets), then
3845
 *
3846
 *  j1 - c1 < j2 - c2
3847
 *
3848
 * and the order is preserved.
3849
 * If c1 < c2, then we know
3850
 *
3851
 *  0 <= c2 - c1 < s
3852
 *
3853
 * We also have
3854
 *
3855
 *  j2 - j1 = n * s + r
3856
 *
3857
 * with n >= 0 and 0 <= r < s.
3858
 * In other words, r = c2 - c1.
3859
 * If n > 0, then
3860
 *
3861
 *  j1 - c1 < j2 - c2
3862
 *
3863
 * If n = 0, then
3864
 *
3865
 *  j1 - c1 = j2 - c2
3866
 *
3867
 * and so
3868
 *
3869
 *  (j1 - c1, c1) << (j2 - c2, c2)
3870
 *
3871
 * with "<<" the lexicographic order, proving that the order is preserved
3872
 * in all cases.
3873
 */
3874
static __isl_give isl_union_map *contruct_shifted_executed(
3875
  struct isl_set_map_pair *domain, int *order, int n,
3876
  __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3877
  __isl_take isl_ast_build *build)
3878
1
{
3879
1
  int i;
3880
1
  isl_union_map *executed;
3881
1
  isl_space *space;
3882
1
  isl_map *map;
3883
1
  int depth;
3884
1
  isl_constraint *c;
3885
1
3886
1
  depth = isl_ast_build_get_depth(build);
3887
1
  space = isl_ast_build_get_space(build, 1);
3888
1
  executed = isl_union_map_empty(isl_space_copy(space));
3889
1
  space = isl_space_map_from_set(space);
3890
1
  map = isl_map_identity(isl_space_copy(space));
3891
1
  map = isl_map_eliminate(map, isl_dim_out, depth, 1);
3892
1
  map = isl_map_insert_dims(map, isl_dim_out, depth + 1, 1);
3893
1
  space = isl_space_insert_dims(space, isl_dim_out, depth + 1, 1);
3894
1
3895
1
  c = isl_constraint_alloc_equality(isl_local_space_from_space(space));
3896
1
  c = isl_constraint_set_coefficient_si(c, isl_dim_in, depth, 1);
3897
1
  c = isl_constraint_set_coefficient_si(c, isl_dim_out, depth, -1);
3898
1
3899
4
  for (i = 0; i < n; 
++i3
) {
3900
3
    isl_map *map_i;
3901
3
    isl_val *v;
3902
3
3903
3
    v = isl_multi_val_get_val(offset, i);
3904
3
    if (!v)
3905
0
      break;
3906
3
    map_i = isl_map_copy(map);
3907
3
    map_i = isl_map_fix_val(map_i, isl_dim_out, depth + 1,
3908
3
          isl_val_copy(v));
3909
3
    v = isl_val_neg(v);
3910
3
    c = isl_constraint_set_constant_val(c, v);
3911
3
    map_i = isl_map_add_constraint(map_i, isl_constraint_copy(c));
3912
3
3913
3
    map_i = isl_map_apply_domain(isl_map_copy(domain[order[i]].map),
3914
3
            map_i);
3915
3
    executed = isl_union_map_add_map(executed, map_i);
3916
3
  }
3917
1
3918
1
  isl_constraint_free(c);
3919
1
  isl_map_free(map);
3920
1
3921
1
  if (i < n)
3922
0
    executed = isl_union_map_free(executed);
3923
1
3924
1
  return executed;
3925
1
}
3926
3927
/* Generate code for a single component, after exposing the stride,
3928
 * given that the schedule domain is "shifted strided".
3929
 *
3930
 * The component inverse schedule is specified as the "map" fields
3931
 * of the elements of "domain" indexed by the first "n" elements of "order".
3932
 *
3933
 * The schedule domain being "shifted strided" means that the differences
3934
 * between the values of the current dimension of domain "i"
3935
 * and the values of the current dimension for some reference domain are
3936
 * equal to
3937
 *
3938
 *  stride * integer + offset[i]
3939
 *
3940
 * We first look for the domain with the "smallest" value for the current
3941
 * dimension and adjust the offsets such that the offset of the "smallest"
3942
 * domain is equal to zero.  The other offsets are reduced modulo stride.
3943
 *
3944
 * Based on this information, we construct a new inverse schedule in
3945
 * contruct_shifted_executed that exposes the stride.
3946
 * Since this involves the introduction of a new schedule dimension,
3947
 * the build needs to be changed accodingly.
3948
 * After computing the AST, the newly introduced dimension needs
3949
 * to be removed again from the list of grafts.  We do this by plugging
3950
 * in a mapping that represents the new schedule domain in terms of the
3951
 * old schedule domain.
3952
 */
3953
static __isl_give isl_ast_graft_list *generate_shift_component(
3954
  struct isl_set_map_pair *domain, int *order, int n,
3955
  __isl_keep isl_val *stride, __isl_keep isl_multi_val *offset,
3956
  __isl_take isl_ast_build *build)
3957
1
{
3958
1
  isl_ast_graft_list *list;
3959
1
  int first;
3960
1
  int depth;
3961
1
  isl_val *val;
3962
1
  isl_multi_val *mv;
3963
1
  isl_space *space;
3964
1
  isl_multi_aff *ma, *zero;
3965
1
  isl_union_map *executed;
3966
1
3967
1
  depth = isl_ast_build_get_depth(build);
3968
1
3969
1
  first = first_offset(domain, order, n, build);
3970
1
  if (first < 0)
3971
0
    goto error;
3972
1
3973
1
  mv = isl_multi_val_copy(offset);
3974
1
  val = isl_multi_val_get_val(offset, first);
3975
1
  val = isl_val_neg(val);
3976
1
  mv = isl_multi_val_add_val(mv, val);
3977
1
  mv = isl_multi_val_mod_val(mv, isl_val_copy(stride));
3978
1
3979
1
  executed = contruct_shifted_executed(domain, order, n, stride, mv,
3980
1
            build);
3981
1
  space = isl_ast_build_get_space(build, 1);
3982
1
  space = isl_space_map_from_set(space);
3983
1
  ma = isl_multi_aff_identity(isl_space_copy(space));
3984
1
  space = isl_space_from_domain(isl_space_domain(space));
3985
1
  space = isl_space_add_dims(space, isl_dim_out, 1);
3986
1
  zero = isl_multi_aff_zero(space);
3987
1
  ma = isl_multi_aff_range_splice(ma, depth + 1, zero);
3988
1
  build = isl_ast_build_insert_dim(build, depth + 1);
3989
1
  list = generate_shifted_component(executed, build);
3990
1
3991
1
  list = isl_ast_graft_list_preimage_multi_aff(list, ma);
3992
1
3993
1
  isl_multi_val_free(mv);
3994
1
3995
1
  return list;
3996
0
error:
3997
0
  isl_ast_build_free(build);
3998
0
  return NULL;
3999
1
}
4000
4001
/* Does any node in the schedule tree rooted at the current schedule node
4002
 * of "build" depend on outer schedule nodes?
4003
 */
4004
static int has_anchored_subtree(__isl_keep isl_ast_build *build)
4005
17
{
4006
17
  isl_schedule_node *node;
4007
17
  int dependent = 0;
4008
17
4009
17
  node = isl_ast_build_get_schedule_node(build);
4010
17
  dependent = isl_schedule_node_is_subtree_anchored(node);
4011
17
  isl_schedule_node_free(node);
4012
17
4013
17
  return dependent;
4014
17
}
4015
4016
/* Generate code for a single component.
4017
 *
4018
 * The component inverse schedule is specified as the "map" fields
4019
 * of the elements of "domain" indexed by the first "n" elements of "order".
4020
 *
4021
 * This function may modify the "set" fields of "domain".
4022
 *
4023
 * Before proceeding with the actual code generation for the component,
4024
 * we first check if there are any "shifted" strides, meaning that
4025
 * the schedule domains of the individual domains are all strided,
4026
 * but that they have different offsets, resulting in the union
4027
 * of schedule domains not being strided anymore.
4028
 *
4029
 * The simplest example is the schedule
4030
 *
4031
 *  { A[i] -> [2i]: 0 <= i < 10; B[i] -> [2i+1] : 0 <= i < 10 }
4032
 *
4033
 * Both schedule domains are strided, but their union is not.
4034
 * This function detects such cases and then rewrites the schedule to
4035
 *
4036
 *  { A[i] -> [2i, 0]: 0 <= i < 10; B[i] -> [2i, 1] : 0 <= i < 10 }
4037
 *
4038
 * In the new schedule, the schedule domains have the same offset (modulo
4039
 * the stride), ensuring that the union of schedule domains is also strided.
4040
 *
4041
 *
4042
 * If there is only a single domain in the component, then there is
4043
 * nothing to do.   Similarly, if the current schedule dimension has
4044
 * a fixed value for almost all domains then there is nothing to be done.
4045
 * In particular, we need at least two domains where the current schedule
4046
 * dimension does not have a fixed value.
4047
 * Finally, in case of a schedule map input,
4048
 * if any of the options refer to the current schedule dimension,
4049
 * then we bail out as well.  It would be possible to reformulate the options
4050
 * in terms of the new schedule domain, but that would introduce constraints
4051
 * that separate the domains in the options and that is something we would
4052
 * like to avoid.
4053
 * In the case of a schedule tree input, we bail out if any of
4054
 * the descendants of the current schedule node refer to outer
4055
 * schedule nodes in any way.
4056
 *
4057
 *
4058
 * To see if there is any shifted stride, we look at the differences
4059
 * between the values of the current dimension in pairs of domains
4060
 * for equal values of outer dimensions.  These differences should be
4061
 * of the form
4062
 *
4063
 *  m x + r
4064
 *
4065
 * with "m" the stride and "r" a constant.  Note that we cannot perform
4066
 * this analysis on individual domains as the lower bound in each domain
4067
 * may depend on parameters or outer dimensions and so the current dimension
4068
 * itself may not have a fixed remainder on division by the stride.
4069
 *
4070
 * In particular, we compare the first domain that does not have an
4071
 * obviously fixed value for the current dimension to itself and all
4072
 * other domains and collect the offsets and the gcd of the strides.
4073
 * If the gcd becomes one, then we failed to find shifted strides.
4074
 * If the gcd is zero, then the differences were all fixed, meaning
4075
 * that some domains had non-obviously fixed values for the current dimension.
4076
 * If all the offsets are the same (for those domains that do not have
4077
 * an obviously fixed value for the current dimension), then we do not
4078
 * apply the transformation.
4079
 * If none of the domains were skipped, then there is nothing to do.
4080
 * If some of them were skipped, then if we apply separation, the schedule
4081
 * domain should get split in pieces with a (non-shifted) stride.
4082
 *
4083
 * Otherwise, we apply a shift to expose the stride in
4084
 * generate_shift_component.
4085
 */
4086
static __isl_give isl_ast_graft_list *generate_component(
4087
  struct isl_set_map_pair *domain, int *order, int n,
4088
  __isl_take isl_ast_build *build)
4089
49
{
4090
49
  int i, d;
4091
49
  int depth;
4092
49
  isl_ctx *ctx;
4093
49
  isl_map *map;
4094
49
  isl_set *deltas;
4095
49
  isl_val *gcd = NULL;
4096
49
  isl_multi_val *mv;
4097
49
  int fixed, skip;
4098
49
  int base;
4099
49
  isl_ast_graft_list *list;
4100
49
  int res = 0;
4101
49
4102
49
  depth = isl_ast_build_get_depth(build);
4103
49
4104
49
  skip = n == 1;
4105
49
  if (skip >= 0 && !skip)
4106
19
    skip = at_most_one_non_fixed(domain, order, n, depth);
4107
49
  if (skip >= 0 && !skip) {
4108
17
    if (isl_ast_build_has_schedule_node(build))
4109
17
      skip = has_anchored_subtree(build);
4110
0
    else
4111
0
      skip = isl_ast_build_options_involve_depth(build);
4112
17
  }
4113
49
  if (skip < 0)
4114
0
    goto error;
4115
49
  if (skip)
4116
32
    return generate_shifted_component_from_list(domain,
4117
32
                  order, n, build);
4118
17
4119
17
  base = eliminate_non_fixed(domain, order, n, depth, build);
4120
17
  if (base < 0)
4121
0
    goto error;
4122
17
4123
17
  ctx = isl_ast_build_get_ctx(build);
4124
17
4125
17
  mv = isl_multi_val_zero(isl_space_set_alloc(ctx, 0, n));
4126
17
4127
17
  fixed = 1;
4128
22
  for (i = 0; i < n; 
++i5
) {
4129
21
    isl_val *r, *m;
4130
21
4131
21
    map = isl_map_from_domain_and_range(
4132
21
          isl_set_copy(domain[order[base]].set),
4133
21
          isl_set_copy(domain[order[i]].set));
4134
22
    for (d = 0; d < depth; 
++d1
)
4135
21
      map = isl_map_equate(map, isl_dim_in, d,
4136
1
                isl_dim_out, d);
4137
21
    deltas = isl_map_deltas(map);
4138
21
    res = isl_set_dim_residue_class_val(deltas, depth, &m, &r);
4139
21
    isl_set_free(deltas);
4140
21
    if (res < 0)
4141
0
      break;
4142
21
4143
21
    if (i == 0)
4144
17
      gcd = m;
4145
4
    else
4146
4
      gcd = isl_val_gcd(gcd, m);
4147
21
    if (isl_val_is_one(gcd)) {
4148
16
      isl_val_free(r);
4149
16
      break;
4150
16
    }
4151
5
    mv = isl_multi_val_set_val(mv, i, r);
4152
5
4153
5
    res = dim_is_fixed(domain[order[i]].set, depth);
4154
5
    if (res < 0)
4155
0
      break;
4156
5
    if (res)
4157
0
      continue;
4158
5
4159
5
    if (fixed && 
i > base4
) {
4160
2
      isl_val *a, *b;
4161
2
      a = isl_multi_val_get_val(mv, i);
4162
2
      b = isl_multi_val_get_val(mv, base);
4163
2
      if (isl_val_ne(a, b))
4164
2
        fixed = 0;
4165
2
      isl_val_free(a);
4166
2
      isl_val_free(b);
4167
2
    }
4168
21
  }
4169
17
4170
17
  if (res < 0 || !gcd) {
4171
0
    isl_ast_build_free(build);
4172
0
    list = NULL;
4173
17
  } else if (i < n || 
fixed1
||
isl_val_is_zero(gcd)1
) {
4174
16
    list = generate_shifted_component_from_list(domain,
4175
16
                  order, n, build);
4176
16
  } else {
4177
1
    list = generate_shift_component(domain, order, n, gcd, mv,
4178
1
            build);
4179
1
  }
4180
17
4181
17
  isl_val_free(gcd);
4182
17
  isl_multi_val_free(mv);
4183
17
4184
17
  return list;
4185
0
error:
4186
0
  isl_ast_build_free(build);
4187
0
  return NULL;
4188
49
}
4189
4190
/* Store both "map" itself and its domain in the
4191
 * structure pointed to by *next and advance to the next array element.
4192
 */
4193
static isl_stat extract_domain(__isl_take isl_map *map, void *user)
4194
77
{
4195
77
  struct isl_set_map_pair **next = user;
4196
77
4197
77
  (*next)->map = isl_map_copy(map);
4198
77
  (*next)->set = isl_map_domain(map);
4199
77
  (*next)++;
4200
77
4201
77
  return isl_stat_ok;
4202
77
}
4203
4204
static int after_in_tree(__isl_keep isl_union_map *umap,
4205
  __isl_keep isl_schedule_node *node);
4206
4207
/* Is any domain element of "umap" scheduled after any of
4208
 * the corresponding image elements by the tree rooted at
4209
 * the child of "node"?
4210
 */
4211
static int after_in_child(__isl_keep isl_union_map *umap,
4212
  __isl_keep isl_schedule_node *node)
4213
13
{
4214
13
  isl_schedule_node *child;
4215
13
  int after;
4216
13
4217
13
  child = isl_schedule_node_get_child(node, 0);
4218
13
  after = after_in_tree(umap, child);
4219
13
  isl_schedule_node_free(child);
4220
13
4221
13
  return after;
4222
13
}
4223
4224
/* Is any domain element of "umap" scheduled after any of
4225
 * the corresponding image elements by the tree rooted at
4226
 * the band node "node"?
4227
 *
4228
 * We first check if any domain element is scheduled after any
4229
 * of the corresponding image elements by the band node itself.
4230
 * If not, we restrict "map" to those pairs of element that
4231
 * are scheduled together by the band node and continue with
4232
 * the child of the band node.
4233
 * If there are no such pairs then the map passed to after_in_child
4234
 * will be empty causing it to return 0.
4235
 */
4236
static int after_in_band(__isl_keep isl_union_map *umap,
4237
  __isl_keep isl_schedule_node *node)
4238
0
{
4239
0
  isl_multi_union_pw_aff *mupa;
4240
0
  isl_union_map *partial, *test, *gt, *universe, *umap1, *umap2;
4241
0
  isl_union_set *domain, *range;
4242
0
  isl_space *space;
4243
0
  int empty;
4244
0
  int after;
4245
0
4246
0
  if (isl_schedule_node_band_n_member(node) == 0)
4247
0
    return after_in_child(umap, node);
4248
0
4249
0
  mupa = isl_schedule_node_band_get_partial_schedule(node);
4250
0
  space = isl_multi_union_pw_aff_get_space(mupa);
4251
0
  partial = isl_union_map_from_multi_union_pw_aff(mupa);
4252
0
  test = isl_union_map_copy(umap);
4253
0
  test = isl_union_map_apply_domain(test, isl_union_map_copy(partial));
4254
0
  test = isl_union_map_apply_range(test, isl_union_map_copy(partial));
4255
0
  gt = isl_union_map_from_map(isl_map_lex_gt(space));
4256
0
  test = isl_union_map_intersect(test, gt);
4257
0
  empty = isl_union_map_is_empty(test);
4258
0
  isl_union_map_free(test);
4259
0
4260
0
  if (empty < 0 || !empty) {
4261
0
    isl_union_map_free(partial);
4262
0
    return empty < 0 ? -1 : 1;
4263
0
  }
4264
0
4265
0
  universe = isl_union_map_universe(isl_union_map_copy(umap));
4266
0
  domain = isl_union_map_domain(isl_union_map_copy(universe));
4267
0
  range = isl_union_map_range(universe);
4268
0
  umap1 = isl_union_map_copy(partial);
4269
0
  umap1 = isl_union_map_intersect_domain(umap1, domain);
4270
0
  umap2 = isl_union_map_intersect_domain(partial, range);
4271
0
  test = isl_union_map_apply_range(umap1, isl_union_map_reverse(umap2));
4272
0
  test = isl_union_map_intersect(test, isl_union_map_copy(umap));
4273
0
  after = after_in_child(test, node);
4274
0
  isl_union_map_free(test);
4275
0
  return after;
4276
0
}
4277
4278
/* Is any domain element of "umap" scheduled after any of
4279
 * the corresponding image elements by the tree rooted at
4280
 * the context node "node"?
4281
 *
4282
 * The context constraints apply to the schedule domain,
4283
 * so we cannot apply them directly to "umap", which contains
4284
 * pairs of statement instances.  Instead, we add them
4285
 * to the range of the prefix schedule for both domain and
4286
 * range of "umap".
4287
 */
4288
static int after_in_context(__isl_keep isl_union_map *umap,
4289
  __isl_keep isl_schedule_node *node)
4290
0
{
4291
0
  isl_union_map *prefix, *universe, *umap1, *umap2;
4292
0
  isl_union_set *domain, *range;
4293
0
  isl_set *context;
4294
0
  int after;
4295
0
4296
0
  umap = isl_union_map_copy(umap);
4297
0
  context = isl_schedule_node_context_get_context(node);
4298
0
  prefix = isl_schedule_node_get_prefix_schedule_union_map(node);
4299
0
  universe = isl_union_map_universe(isl_union_map_copy(umap));
4300
0
  domain = isl_union_map_domain(isl_union_map_copy(universe));
4301
0
  range = isl_union_map_range(universe);
4302
0
  umap1 = isl_union_map_copy(prefix);
4303
0
  umap1 = isl_union_map_intersect_domain(umap1, domain);
4304
0
  umap2 = isl_union_map_intersect_domain(prefix, range);
4305
0
  umap1 = isl_union_map_intersect_range(umap1,
4306
0
              isl_union_set_from_set(context));
4307
0
  umap1 = isl_union_map_apply_range(umap1, isl_union_map_reverse(umap2));
4308
0
  umap = isl_union_map_intersect(umap, umap1);
4309
0
4310
0
  after = after_in_child(umap, node);
4311
0
4312
0
  isl_union_map_free(umap);
4313
0
4314
0
  return after;
4315
0
}
4316
4317
/* Is any domain element of "umap" scheduled after any of
4318
 * the corresponding image elements by the tree rooted at
4319
 * the expansion node "node"?
4320
 *
4321
 * We apply the expansion to domain and range of "umap" and
4322
 * continue with its child.
4323
 */
4324
static int after_in_expansion(__isl_keep isl_union_map *umap,
4325
  __isl_keep isl_schedule_node *node)
4326
0
{
4327
0
  isl_union_map *expansion;
4328
0
  int after;
4329
0
4330
0
  expansion = isl_schedule_node_expansion_get_expansion(node);
4331
0
  umap = isl_union_map_copy(umap);
4332
0
  umap = isl_union_map_apply_domain(umap, isl_union_map_copy(expansion));
4333
0
  umap = isl_union_map_apply_range(umap, expansion);
4334
0
4335
0
  after = after_in_child(umap, node);
4336
0
4337
0
  isl_union_map_free(umap);
4338
0
4339
0
  return after;
4340
0
}
4341
4342
/* Is any domain element of "umap" scheduled after any of
4343
 * the corresponding image elements by the tree rooted at
4344
 * the extension node "node"?
4345
 *
4346
 * Since the extension node may add statement instances before or
4347
 * after the pairs of statement instances in "umap", we return 1
4348
 * to ensure that these pairs are not broken up.
4349
 */
4350
static int after_in_extension(__isl_keep isl_union_map *umap,
4351
  __isl_keep isl_schedule_node *node)
4352
0
{
4353
0
  return 1;
4354
0
}
4355
4356
/* Is any domain element of "umap" scheduled after any of
4357
 * the corresponding image elements by the tree rooted at
4358
 * the filter node "node"?
4359
 *
4360
 * We intersect domain and range of "umap" with the filter and
4361
 * continue with its child.
4362
 */
4363
static int after_in_filter(__isl_keep isl_union_map *umap,
4364
  __isl_keep isl_schedule_node *node)
4365
13
{
4366
13
  isl_union_set *filter;
4367
13
  int after;
4368
13
4369
13
  umap = isl_union_map_copy(umap);
4370
13
  filter = isl_schedule_node_filter_get_filter(node);
4371
13
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(filter));
4372
13
  umap = isl_union_map_intersect_range(umap, filter);
4373
13
4374
13
  after = after_in_child(umap, node);
4375
13
4376
13
  isl_union_map_free(umap);
4377
13
4378
13
  return after;
4379
13
}
4380
4381
/* Is any domain element of "umap" scheduled after any of
4382
 * the corresponding image elements by the tree rooted at
4383
 * the set node "node"?
4384
 *
4385
 * This is only the case if this condition holds in any
4386
 * of the (filter) children of the set node.
4387
 * In particular, if the domain and the range of "umap"
4388
 * are contained in different children, then the condition
4389
 * does not hold.
4390
 */
4391
static int after_in_set(__isl_keep isl_union_map *umap,
4392
  __isl_keep isl_schedule_node *node)
4393
5
{
4394
5
  int i, n;
4395
5
4396
5
  n = isl_schedule_node_n_children(node);
4397
18
  for (i = 0; i < n; 
++i13
) {
4398
13
    isl_schedule_node *child;
4399
13
    int after;
4400
13
4401
13
    child = isl_schedule_node_get_child(node, i);
4402
13
    after = after_in_tree(umap, child);
4403
13
    isl_schedule_node_free(child);
4404
13
4405
13
    if (after < 0 || after)
4406
0
      return after;
4407
13
  }
4408
5
4409
5
  return 0;
4410
5
}
4411
4412
/* Return the filter of child "i" of "node".
4413
 */
4414
static __isl_give isl_union_set *child_filter(
4415
  __isl_keep isl_schedule_node *node, int i)
4416
11
{
4417
11
  isl_schedule_node *child;
4418
11
  isl_union_set *filter;
4419
11
4420
11
  child = isl_schedule_node_get_child(node, i);
4421
11
  filter = isl_schedule_node_filter_get_filter(child);
4422
11
  isl_schedule_node_free(child);
4423
11
4424
11
  return filter;
4425
11
}
4426
4427
/* Is any domain element of "umap" scheduled after any of
4428
 * the corresponding image elements by the tree rooted at
4429
 * the sequence node "node"?
4430
 *
4431
 * This happens in particular if any domain element is
4432
 * contained in a later child than one containing a range element or
4433
 * if the condition holds within a given child in the sequence.
4434
 * The later part of the condition is checked by after_in_set.
4435
 */
4436
static int after_in_sequence(__isl_keep isl_union_map *umap,
4437
  __isl_keep isl_schedule_node *node)
4438
6
{
4439
6
  int i, j, n;
4440
6
  isl_union_map *umap_i;
4441
6
  int empty, after = 0;
4442
6
4443
6
  n = isl_schedule_node_n_children(node);
4444
14
  for (i = 1; i < n; 
++i8
) {
4445
9
    isl_union_set *filter_i;
4446
9
4447
9
    umap_i = isl_union_map_copy(umap);
4448
9
    filter_i = child_filter(node, i);
4449
9
    umap_i = isl_union_map_intersect_domain(umap_i, filter_i);
4450
9
    empty = isl_union_map_is_empty(umap_i);
4451
9
    if (empty < 0)
4452
0
      goto error;
4453
9
    if (empty) {
4454
7
      isl_union_map_free(umap_i);
4455
7
      continue;
4456
7
    }
4457
2
4458
3
    
for (j = 0; 2
j < i;
++j1
) {
4459
2
      isl_union_set *filter_j;
4460
2
      isl_union_map *umap_ij;
4461
2
4462
2
      umap_ij = isl_union_map_copy(umap_i);
4463
2
      filter_j = child_filter(node, j);
4464
2
      umap_ij = isl_union_map_intersect_range(umap_ij,
4465
2
                filter_j);
4466
2
      empty = isl_union_map_is_empty(umap_ij);
4467
2
      isl_union_map_free(umap_ij);
4468
2
4469
2
      if (empty < 0)
4470
0
        goto error;
4471
2
      if (!empty)
4472
1
        after = 1;
4473
2
      if (after)
4474
1
        break;
4475
2
    }
4476
2
4477
2
    isl_union_map_free(umap_i);
4478
2
    if (after)
4479
1
      break;
4480
9
  }
4481
6
4482
6
  if (after < 0 || after)
4483
1
    return after;
4484
5
4485
5
  return after_in_set(umap, node);
4486
0
error:
4487
0
  isl_union_map_free(umap_i);
4488
0
  return -1;
4489
6
}
4490
4491
/* Is any domain element of "umap" scheduled after any of
4492
 * the corresponding image elements by the tree rooted at "node"?
4493
 *
4494
 * If "umap" is empty, then clearly there is no such element.
4495
 * Otherwise, consider the different types of nodes separately.
4496
 */
4497
static int after_in_tree(__isl_keep isl_union_map *umap,
4498
  __isl_keep isl_schedule_node *node)
4499
32
{
4500
32
  int empty;
4501
32
  enum isl_schedule_node_type type;
4502
32
4503
32
  empty = isl_union_map_is_empty(umap);
4504
32
  if (empty < 0)
4505
0
    return -1;
4506
32
  if (empty)
4507
13
    return 0;
4508
19
  if (!node)
4509
0
    return -1;
4510
19
4511
19
  type = isl_schedule_node_get_type(node);
4512
19
  switch (type) {
4513
19
  case isl_schedule_node_error:
4514
0
    return -1;
4515
19
  case isl_schedule_node_leaf:
4516
0
    return 0;
4517
19
  case isl_schedule_node_band:
4518
0
    return after_in_band(umap, node);
4519
19
  case isl_schedule_node_domain:
4520
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
4521
0
      "unexpected internal domain node", return -1);
4522
0
  case isl_schedule_node_context:
4523
0
    return after_in_context(umap, node);
4524
0
  case isl_schedule_node_expansion:
4525
0
    return after_in_expansion(umap, node);
4526
0
  case isl_schedule_node_extension:
4527
0
    return after_in_extension(umap, node);
4528
13
  case isl_schedule_node_filter:
4529
13
    return after_in_filter(umap, node);
4530
0
  case isl_schedule_node_guard:
4531
0
  case isl_schedule_node_mark:
4532
0
    return after_in_child(umap, node);
4533
0
  case isl_schedule_node_set:
4534
0
    return after_in_set(umap, node);
4535
6
  case isl_schedule_node_sequence:
4536
6
    return after_in_sequence(umap, node);
4537
0
  }
4538
0
4539
0
  return 1;
4540
0
}
4541
4542
/* Is any domain element of "map1" scheduled after any domain
4543
 * element of "map2" by the subtree underneath the current band node,
4544
 * while at the same time being scheduled together by the current
4545
 * band node, i.e., by "map1" and "map2?
4546
 *
4547
 * If the child of the current band node is a leaf, then
4548
 * no element can be scheduled after any other element.
4549
 *
4550
 * Otherwise, we construct a relation between domain elements
4551
 * of "map1" and domain elements of "map2" that are scheduled
4552
 * together and then check if the subtree underneath the current
4553
 * band node determines their relative order.
4554
 */
4555
static int after_in_subtree(__isl_keep isl_ast_build *build,
4556
  __isl_keep isl_map *map1, __isl_keep isl_map *map2)
4557
6
{
4558
6
  isl_schedule_node *node;
4559
6
  isl_map *map;
4560
6
  isl_union_map *umap;
4561
6
  int after;
4562
6
4563
6
  node = isl_ast_build_get_schedule_node(build);
4564
6
  if (!node)
4565
0
    return -1;
4566
6
  node = isl_schedule_node_child(node, 0);
4567
6
  if (isl_schedule_node_get_type(node) == isl_schedule_node_leaf) {
4568
0
    isl_schedule_node_free(node);
4569
0
    return 0;
4570
0
  }
4571
6
  map = isl_map_copy(map2);
4572
6
  map = isl_map_apply_domain(map, isl_map_copy(map1));
4573
6
  umap = isl_union_map_from_map(map);
4574
6
  after = after_in_tree(umap, node);
4575
6
  isl_union_map_free(umap);
4576
6
  isl_schedule_node_free(node);
4577
6
  return after;
4578
6
}
4579
4580
/* Internal data for any_scheduled_after.
4581
 *
4582
 * "build" is the build in which the AST is constructed.
4583
 * "depth" is the number of loops that have already been generated
4584
 * "group_coscheduled" is a local copy of options->ast_build_group_coscheduled
4585
 * "domain" is an array of set-map pairs corresponding to the different
4586
 * iteration domains.  The set is the schedule domain, i.e., the domain
4587
 * of the inverse schedule, while the map is the inverse schedule itself.
4588
 */
4589
struct isl_any_scheduled_after_data {
4590
  isl_ast_build *build;
4591
  int depth;
4592
  int group_coscheduled;
4593
  struct isl_set_map_pair *domain;
4594
};
4595
4596
/* Is any element of domain "i" scheduled after any element of domain "j"
4597
 * (for a common iteration of the first data->depth loops)?
4598
 *
4599
 * data->domain[i].set contains the domain of the inverse schedule
4600
 * for domain "i", i.e., elements in the schedule domain.
4601
 *
4602
 * If we are inside a band of a schedule tree and there is a pair
4603
 * of elements in the two domains that is schedule together by
4604
 * the current band, then we check if any element of "i" may be schedule
4605
 * after element of "j" by the descendants of the band node.
4606
 *
4607
 * If data->group_coscheduled is set, then we also return 1 if there
4608
 * is any pair of elements in the two domains that are scheduled together.
4609
 */
4610
static isl_bool any_scheduled_after(int i, int j, void *user)
4611
92
{
4612
92
  struct isl_any_scheduled_after_data *data = user;
4613
92
  int dim = isl_set_dim(data->domain[i].set, isl_dim_set);
4614
92
  int pos;
4615
92
4616
98
  for (pos = data->depth; pos < dim; 
++pos6
) {
4617
92
    int follows;
4618
92
4619
92
    follows = isl_set_follows_at(data->domain[i].set,
4620
92
            data->domain[j].set, pos);
4621
92
4622
92
    if (follows < -1)
4623
0
      return isl_bool_error;
4624
92
    if (follows > 0)
4625
65
      return isl_bool_true;
4626
27
    if (follows < 0)
4627
21
      return isl_bool_false;
4628
92
  }
4629
92
4630
92
  
if (6
isl_ast_build_has_schedule_node(data->build)6
) {
4631
6
    int after;
4632
6
4633
6
    after = after_in_subtree(data->build, data->domain[i].map,
4634
6
              data->domain[j].map);
4635
6
    if (after < 0 || after)
4636
1
      return after;
4637
5
  }
4638
5
4639
5
  return data->group_coscheduled;
4640
5
}
4641
4642
/* Look for independent components at the current depth and generate code
4643
 * for each component separately.  The resulting lists of grafts are
4644
 * merged in an attempt to combine grafts with identical guards.
4645
 *
4646
 * Code for two domains can be generated separately if all the elements
4647
 * of one domain are scheduled before (or together with) all the elements
4648
 * of the other domain.  We therefore consider the graph with as nodes
4649
 * the domains and an edge between two nodes if any element of the first
4650
 * node is scheduled after any element of the second node.
4651
 * If the ast_build_group_coscheduled is set, then we also add an edge if
4652
 * there is any pair of elements in the two domains that are scheduled
4653
 * together.
4654
 * Code is then generated (by generate_component)
4655
 * for each of the strongly connected components in this graph
4656
 * in their topological order.
4657
 *
4658
 * Since the test is performed on the domain of the inverse schedules of
4659
 * the different domains, we precompute these domains and store
4660
 * them in data.domain.
4661
 */
4662
static __isl_give isl_ast_graft_list *generate_components(
4663
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
4664
31
{
4665
31
  int i;
4666
31
  isl_ctx *ctx = isl_ast_build_get_ctx(build);
4667
31
  int n = isl_union_map_n_map(executed);
4668
31
  struct isl_any_scheduled_after_data data;
4669
31
  struct isl_set_map_pair *next;
4670
31
  struct isl_tarjan_graph *g = NULL;
4671
31
  isl_ast_graft_list *list = NULL;
4672
31
  int n_domain = 0;
4673
31
4674
31
  data.domain = isl_calloc_array(ctx, struct isl_set_map_pair, n);
4675
31
  if (!data.domain)
4676
0
    goto error;
4677
31
  n_domain = n;
4678
31
4679
31
  next = data.domain;
4680
31
  if (isl_union_map_foreach_map(executed, &extract_domain, &next) < 0)
4681
0
    goto error;
4682
31
4683
31
  if (!build)
4684
0
    goto error;
4685
31
  data.build = build;
4686
31
  data.depth = isl_ast_build_get_depth(build);
4687
31
  data.group_coscheduled = isl_options_get_ast_build_group_coscheduled(ctx);
4688
31
  g = isl_tarjan_graph_init(ctx, n, &any_scheduled_after, &data);
4689
31
  if (!g)
4690
0
    goto error;
4691
31
4692
31
  list = isl_ast_graft_list_alloc(ctx, 0);
4693
31
4694
31
  i = 0;
4695
80
  while (list && n) {
4696
49
    isl_ast_graft_list *list_c;
4697
49
    int first = i;
4698
49
4699
49
    if (g->order[i] == -1)
4700
49
      
isl_die0
(ctx, isl_error_internal, "cannot happen",
4701
49
        goto error);
4702
49
    ++i; --n;
4703
77
    while (g->order[i] != -1) {
4704
28
      ++i; --n;
4705
28
    }
4706
49
4707
49
    list_c = generate_component(data.domain,
4708
49
              g->order + first, i - first,
4709
49
              isl_ast_build_copy(build));
4710
49
    list = isl_ast_graft_list_merge(list, list_c, build);
4711
49
4712
49
    ++i;
4713
49
  }
4714
31
4715
31
  if (0)
4716
0
error:    list = isl_ast_graft_list_free(list);
4717
31
  isl_tarjan_graph_free(g);
4718
108
  for (i = 0; i < n_domain; 
++i77
) {
4719
77
    isl_map_free(data.domain[i].map);
4720
77
    isl_set_free(data.domain[i].set);
4721
77
  }
4722
31
  free(data.domain);
4723
31
  isl_union_map_free(executed);
4724
31
  isl_ast_build_free(build);
4725
31
4726
31
  return list;
4727
31
}
4728
4729
/* Generate code for the next level (and all inner levels).
4730
 *
4731
 * If "executed" is empty, i.e., no code needs to be generated,
4732
 * then we return an empty list.
4733
 *
4734
 * If we have already generated code for all loop levels, then we pass
4735
 * control to generate_inner_level.
4736
 *
4737
 * If "executed" lives in a single space, i.e., if code needs to be
4738
 * generated for a single domain, then there can only be a single
4739
 * component and we go directly to generate_shifted_component.
4740
 * Otherwise, we call generate_components to detect the components
4741
 * and to call generate_component on each of them separately.
4742
 */
4743
static __isl_give isl_ast_graft_list *generate_next_level(
4744
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
4745
2.42k
{
4746
2.42k
  int depth;
4747
2.42k
4748
2.42k
  if (!build || !executed)
4749
0
    goto error;
4750
2.42k
4751
2.42k
  if (isl_union_map_is_empty(executed)) {
4752
0
    isl_ctx *ctx = isl_ast_build_get_ctx(build);
4753
0
    isl_union_map_free(executed);
4754
0
    isl_ast_build_free(build);
4755
0
    return isl_ast_graft_list_alloc(ctx, 0);
4756
0
  }
4757
2.42k
4758
2.42k
  depth = isl_ast_build_get_depth(build);
4759
2.42k
  if (depth >= isl_ast_build_dim(build, isl_dim_set))
4760
1.15k
    return generate_inner_level(executed, build);
4761
1.27k
4762
1.27k
  if (isl_union_map_n_map(executed) == 1)
4763
1.24k
    return generate_shifted_component(executed, build);
4764
31
4765
31
  return generate_components(executed, build);
4766
0
error:
4767
0
  isl_union_map_free(executed);
4768
0
  isl_ast_build_free(build);
4769
0
  return NULL;
4770
2.42k
}
4771
4772
/* Internal data structure used by isl_ast_build_node_from_schedule_map.
4773
 * internal, executed and build are the inputs to generate_code.
4774
 * list collects the output.
4775
 */
4776
struct isl_generate_code_data {
4777
  int internal;
4778
  isl_union_map *executed;
4779
  isl_ast_build *build;
4780
4781
  isl_ast_graft_list *list;
4782
};
4783
4784
/* Given an inverse schedule in terms of the external build schedule, i.e.,
4785
 *
4786
 *  [E -> S] -> D
4787
 *
4788
 * with E the external build schedule and S the additional schedule "space",
4789
 * reformulate the inverse schedule in terms of the internal schedule domain,
4790
 * i.e., return
4791
 *
4792
 *  [I -> S] -> D
4793
 *
4794
 * We first obtain a mapping
4795
 *
4796
 *  I -> E
4797
 *
4798
 * take the inverse and the product with S -> S, resulting in
4799
 *
4800
 *  [I -> S] -> [E -> S]
4801
 *
4802
 * Applying the map to the input produces the desired result.
4803
 */
4804
static __isl_give isl_union_map *internal_executed(
4805
  __isl_take isl_union_map *executed, __isl_keep isl_space *space,
4806
  __isl_keep isl_ast_build *build)
4807
0
{
4808
0
  isl_map *id, *proj;
4809
0
4810
0
  proj = isl_ast_build_get_schedule_map(build);
4811
0
  proj = isl_map_reverse(proj);
4812
0
  space = isl_space_map_from_set(isl_space_copy(space));
4813
0
  id = isl_map_identity(space);
4814
0
  proj = isl_map_product(proj, id);
4815
0
  executed = isl_union_map_apply_domain(executed,
4816
0
            isl_union_map_from_map(proj));
4817
0
  return executed;
4818
0
}
4819
4820
/* Generate an AST that visits the elements in the range of data->executed
4821
 * in the relative order specified by the corresponding domain element(s)
4822
 * for those domain elements that belong to "set".
4823
 * Add the result to data->list.
4824
 *
4825
 * The caller ensures that "set" is a universe domain.
4826
 * "space" is the space of the additional part of the schedule.
4827
 * It is equal to the space of "set" if build->domain is parametric.
4828
 * Otherwise, it is equal to the range of the wrapped space of "set".
4829
 *
4830
 * If the build space is not parametric and
4831
 * if isl_ast_build_node_from_schedule_map
4832
 * was called from an outside user (data->internal not set), then
4833
 * the (inverse) schedule refers to the external build domain and needs to
4834
 * be transformed to refer to the internal build domain.
4835
 *
4836
 * If the build space is parametric, then we add some of the parameter
4837
 * constraints to the executed relation.  Adding these constraints
4838
 * allows for an earlier detection of conflicts in some cases.
4839
 * However, we do not want to divide the executed relation into
4840
 * more disjuncts than necessary.  We therefore approximate
4841
 * the constraints on the parameters by a single disjunct set.
4842
 *
4843
 * The build is extended to include the additional part of the schedule.
4844
 * If the original build space was not parametric, then the options
4845
 * in data->build refer only to the additional part of the schedule
4846
 * and they need to be adjusted to refer to the complete AST build
4847
 * domain.
4848
 *
4849
 * After having adjusted inverse schedule and build, we start generating
4850
 * code with the outer loop of the current code generation
4851
 * in generate_next_level.
4852
 *
4853
 * If the original build space was not parametric, we undo the embedding
4854
 * on the resulting isl_ast_node_list so that it can be used within
4855
 * the outer AST build.
4856
 */
4857
static isl_stat generate_code_in_space(struct isl_generate_code_data *data,
4858
  __isl_take isl_set *set, __isl_take isl_space *space)
4859
10
{
4860
10
  isl_union_map *executed;
4861
10
  isl_ast_build *build;
4862
10
  isl_ast_graft_list *list;
4863
10
  int embed;
4864
10
4865
10
  executed = isl_union_map_copy(data->executed);
4866
10
  executed = isl_union_map_intersect_domain(executed,
4867
10
             isl_union_set_from_set(set));
4868
10
4869
10
  embed = !isl_set_is_params(data->build->domain);
4870
10
  if (embed && !data->internal)
4871
0
    executed = internal_executed(executed, space, data->build);
4872
10
  if (!embed) {
4873
0
    isl_set *domain;
4874
0
    domain = isl_ast_build_get_domain(data->build);
4875
0
    domain = isl_set_from_basic_set(isl_set_simple_hull(domain));
4876
0
    executed = isl_union_map_intersect_params(executed, domain);
4877
0
  }
4878
10
4879
10
  build = isl_ast_build_copy(data->build);
4880
10
  build = isl_ast_build_product(build, space);
4881
10
4882
10
  list = generate_next_level(executed, build);
4883
10
4884
10
  list = isl_ast_graft_list_unembed(list, embed);
4885
10
4886
10
  data->list = isl_ast_graft_list_concat(data->list, list);
4887
10
4888
10
  return isl_stat_ok;
4889
10
}
4890
4891
/* Generate an AST that visits the elements in the range of data->executed
4892
 * in the relative order specified by the corresponding domain element(s)
4893
 * for those domain elements that belong to "set".
4894
 * Add the result to data->list.
4895
 *
4896
 * The caller ensures that "set" is a universe domain.
4897
 *
4898
 * If the build space S is not parametric, then the space of "set"
4899
 * need to be a wrapped relation with S as domain.  That is, it needs
4900
 * to be of the form
4901
 *
4902
 *  [S -> T]
4903
 *
4904
 * Check this property and pass control to generate_code_in_space
4905
 * passing along T.
4906
 * If the build space is not parametric, then T is the space of "set".
4907
 */
4908
static isl_stat generate_code_set(__isl_take isl_set *set, void *user)
4909
10
{
4910
10
  struct isl_generate_code_data *data = user;
4911
10
  isl_space *space, *build_space;
4912
10
  int is_domain;
4913
10
4914
10
  space = isl_set_get_space(set);
4915
10
4916
10
  if (isl_set_is_params(data->build->domain))
4917
0
    return generate_code_in_space(data, set, space);
4918
10
4919
10
  build_space = isl_ast_build_get_space(data->build, data->internal);
4920
10
  space = isl_space_unwrap(space);
4921
10
  is_domain = isl_space_is_domain(build_space, space);
4922
10
  isl_space_free(build_space);
4923
10
  space = isl_space_range(space);
4924
10
4925
10
  if (is_domain < 0)
4926
0
    goto error;
4927
10
  if (!is_domain)
4928
10
    
isl_die0
(isl_set_get_ctx(set), isl_error_invalid,
4929
10
      "invalid nested schedule space", goto error);
4930
10
4931
10
  return generate_code_in_space(data, set, space);
4932
0
error:
4933
0
  isl_set_free(set);
4934
0
  isl_space_free(space);
4935
0
  return isl_stat_error;
4936
10
}
4937
4938
/* Generate an AST that visits the elements in the range of "executed"
4939
 * in the relative order specified by the corresponding domain element(s).
4940
 *
4941
 * "build" is an isl_ast_build that has either been constructed by
4942
 * isl_ast_build_from_context or passed to a callback set by
4943
 * isl_ast_build_set_create_leaf.
4944
 * In the first case, the space of the isl_ast_build is typically
4945
 * a parametric space, although this is currently not enforced.
4946
 * In the second case, the space is never a parametric space.
4947
 * If the space S is not parametric, then the domain space(s) of "executed"
4948
 * need to be wrapped relations with S as domain.
4949
 *
4950
 * If the domain of "executed" consists of several spaces, then an AST
4951
 * is generated for each of them (in arbitrary order) and the results
4952
 * are concatenated.
4953
 *
4954
 * If "internal" is set, then the domain "S" above refers to the internal
4955
 * schedule domain representation.  Otherwise, it refers to the external
4956
 * representation, as returned by isl_ast_build_get_schedule_space.
4957
 *
4958
 * We essentially run over all the spaces in the domain of "executed"
4959
 * and call generate_code_set on each of them.
4960
 */
4961
static __isl_give isl_ast_graft_list *generate_code(
4962
  __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
4963
  int internal)
4964
10
{
4965
10
  isl_ctx *ctx;
4966
10
  struct isl_generate_code_data data = { 0 };
4967
10
  isl_space *space;
4968
10
  isl_union_set *schedule_domain;
4969
10
  isl_union_map *universe;
4970
10
4971
10
  if (!build)
4972
0
    goto error;
4973
10
  space = isl_ast_build_get_space(build, 1);
4974
10
  space = isl_space_align_params(space,
4975
10
            isl_union_map_get_space(executed));
4976
10
  space = isl_space_align_params(space,
4977
10
            isl_union_map_get_space(build->options));
4978
10
  build = isl_ast_build_align_params(build, isl_space_copy(space));
4979
10
  executed = isl_union_map_align_params(executed, space);
4980
10
  if (!executed || !build)
4981
0
    goto error;
4982
10
4983
10
  ctx = isl_ast_build_get_ctx(build);
4984
10
4985
10
  data.internal = internal;
4986
10
  data.executed = executed;
4987
10
  data.build = build;
4988
10
  data.list = isl_ast_graft_list_alloc(ctx, 0);
4989
10
4990
10
  universe = isl_union_map_universe(isl_union_map_copy(executed));
4991
10
  schedule_domain = isl_union_map_domain(universe);
4992
10
  if (isl_union_set_foreach_set(schedule_domain, &generate_code_set,
4993
10
          &data) < 0)
4994
0
    data.list = isl_ast_graft_list_free(data.list);
4995
10
4996
10
  isl_union_set_free(schedule_domain);
4997
10
  isl_union_map_free(executed);
4998
10
4999
10
  isl_ast_build_free(build);
5000
10
  return data.list;
5001
0
error:
5002
0
  isl_union_map_free(executed);
5003
0
  isl_ast_build_free(build);
5004
0
  return NULL;
5005
10
}
5006
5007
/* Generate an AST that visits the elements in the domain of "schedule"
5008
 * in the relative order specified by the corresponding image element(s).
5009
 *
5010
 * "build" is an isl_ast_build that has either been constructed by
5011
 * isl_ast_build_from_context or passed to a callback set by
5012
 * isl_ast_build_set_create_leaf.
5013
 * In the first case, the space of the isl_ast_build is typically
5014
 * a parametric space, although this is currently not enforced.
5015
 * In the second case, the space is never a parametric space.
5016
 * If the space S is not parametric, then the range space(s) of "schedule"
5017
 * need to be wrapped relations with S as domain.
5018
 *
5019
 * If the range of "schedule" consists of several spaces, then an AST
5020
 * is generated for each of them (in arbitrary order) and the results
5021
 * are concatenated.
5022
 *
5023
 * We first initialize the local copies of the relevant options.
5024
 * We do this here rather than when the isl_ast_build is created
5025
 * because the options may have changed between the construction
5026
 * of the isl_ast_build and the call to isl_generate_code.
5027
 *
5028
 * The main computation is performed on an inverse schedule (with
5029
 * the schedule domain in the domain and the elements to be executed
5030
 * in the range) called "executed".
5031
 */
5032
__isl_give isl_ast_node *isl_ast_build_node_from_schedule_map(
5033
  __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
5034
0
{
5035
0
  isl_ast_graft_list *list;
5036
0
  isl_ast_node *node;
5037
0
  isl_union_map *executed;
5038
0
5039
0
  build = isl_ast_build_copy(build);
5040
0
  build = isl_ast_build_set_single_valued(build, 0);
5041
0
  schedule = isl_union_map_coalesce(schedule);
5042
0
  schedule = isl_union_map_remove_redundancies(schedule);
5043
0
  executed = isl_union_map_reverse(schedule);
5044
0
  list = generate_code(executed, isl_ast_build_copy(build), 0);
5045
0
  node = isl_ast_node_from_graft_list(list, build);
5046
0
  isl_ast_build_free(build);
5047
0
5048
0
  return node;
5049
0
}
5050
5051
/* The old name for isl_ast_build_node_from_schedule_map.
5052
 * It is being kept for backward compatibility, but
5053
 * it will be removed in the future.
5054
 */
5055
__isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
5056
  __isl_keep isl_ast_build *build, __isl_take isl_union_map *schedule)
5057
0
{
5058
0
  return isl_ast_build_node_from_schedule_map(build, schedule);
5059
0
}
5060
5061
/* Generate an AST that visits the elements in the domain of "executed"
5062
 * in the relative order specified by the band node "node" and its descendants.
5063
 *
5064
 * The relation "executed" maps the outer generated loop iterators
5065
 * to the domain elements executed by those iterations.
5066
 *
5067
 * If the band is empty, we continue with its descendants.
5068
 * Otherwise, we extend the build and the inverse schedule with
5069
 * the additional space/partial schedule and continue generating
5070
 * an AST in generate_next_level.
5071
 * As soon as we have extended the inverse schedule with the additional
5072
 * partial schedule, we look for equalities that may exists between
5073
 * the old and the new part.
5074
 */
5075
static __isl_give isl_ast_graft_list *build_ast_from_band(
5076
  __isl_take isl_ast_build *build, __isl_take isl_schedule_node *node,
5077
  __isl_take isl_union_map *executed)
5078
184
{
5079
184
  isl_space *space;
5080
184
  isl_multi_union_pw_aff *extra;
5081
184
  isl_union_map *extra_umap;
5082
184
  isl_ast_graft_list *list;
5083
184
  unsigned n1, n2;
5084
184
5085
184
  if (!build || !node || !executed)
5086
0
    goto error;
5087
184
5088
184
  if (isl_schedule_node_band_n_member(node) == 0)
5089
0
    return build_ast_from_child(build, node, executed);
5090
184
5091
184
  extra = isl_schedule_node_band_get_partial_schedule(node);
5092
184
  extra = isl_multi_union_pw_aff_align_params(extra,
5093
184
        isl_ast_build_get_space(build, 1));
5094
184
  space = isl_multi_union_pw_aff_get_space(extra);
5095
184
5096
184
  extra_umap = isl_union_map_from_multi_union_pw_aff(extra);
5097
184
  extra_umap = isl_union_map_reverse(extra_umap);
5098
184
5099
184
  executed = isl_union_map_domain_product(executed, extra_umap);
5100
184
  executed = isl_union_map_detect_equalities(executed);
5101
184
5102
184
  n1 = isl_ast_build_dim(build, isl_dim_param);
5103
184
  build = isl_ast_build_product(build, space);
5104
184
  n2 = isl_ast_build_dim(build, isl_dim_param);
5105
184
  if (n2 > n1)
5106
184
    
isl_die0
(isl_ast_build_get_ctx(build), isl_error_invalid,
5107
184
      "band node is not allowed to introduce new parameters",
5108
184
      build = isl_ast_build_free(build));
5109
184
  build = isl_ast_build_set_schedule_node(build, node);
5110
184
5111
184
  list = generate_next_level(executed, build);
5112
184
5113
184
  list = isl_ast_graft_list_unembed(list, 1);
5114
184
5115
184
  return list;
5116
0
error:
5117
0
  isl_schedule_node_free(node);
5118
0
  isl_union_map_free(executed);
5119
0
  isl_ast_build_free(build);
5120
0
  return NULL;
5121
184
}
5122
5123
/* Hoist a list of grafts (in practice containing a single graft)
5124
 * from "sub_build" (which includes extra context information)
5125
 * to "build".
5126
 *
5127
 * In particular, project out all additional parameters introduced
5128
 * by the context node from the enforced constraints and the guard
5129
 * of the single graft.
5130
 */
5131
static __isl_give isl_ast_graft_list *hoist_out_of_context(
5132
  __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build,
5133
  __isl_keep isl_ast_build *sub_build)
5134
0
{
5135
0
  isl_ast_graft *graft;
5136
0
  isl_basic_set *enforced;
5137
0
  isl_set *guard;
5138
0
  unsigned n_param, extra_param;