Coverage Report

Created: 2018-02-20 23:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2013-2014 Ecole Normale Superieure
3
 * Copyright 2014      INRIA Rocquencourt
4
 * Copyright 2016      INRIA Paris
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege,
9
 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11
 * B.P. 105 - 78153 Le Chesnay, France
12
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
13
 * CS 42112, 75589 Paris Cedex 12, France
14
 */
15
16
#include <isl/val.h>
17
#include <isl/space.h>
18
#include <isl/map.h>
19
#include <isl_schedule_band.h>
20
#include <isl_schedule_private.h>
21
22
#undef EL
23
#define EL isl_schedule_tree
24
25
#include <isl_list_templ.h>
26
27
#undef BASE
28
#define BASE schedule_tree
29
30
#include <isl_list_templ.c>
31
32
/* Is "tree" the leaf of a schedule tree?
33
 */
34
int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
35
109k
{
36
109k
  return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
37
109k
}
38
39
/* Create a new schedule tree of type "type".
40
 * The caller is responsible for filling in the type specific fields and
41
 * the children.
42
 *
43
 * By default, the single node tree does not have any anchored nodes.
44
 * The caller is responsible for updating the anchored field if needed.
45
 */
46
static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
47
  enum isl_schedule_node_type type)
48
41.1k
{
49
41.1k
  isl_schedule_tree *tree;
50
41.1k
51
41.1k
  if (type == isl_schedule_node_error)
52
0
    return NULL;
53
41.1k
54
41.1k
  tree = isl_calloc_type(ctx, isl_schedule_tree);
55
41.1k
  if (!tree)
56
0
    return NULL;
57
41.1k
58
41.1k
  tree->ref = 1;
59
41.1k
  tree->ctx = ctx;
60
41.1k
  isl_ctx_ref(ctx);
61
41.1k
  tree->type = type;
62
41.1k
  tree->anchored = 0;
63
41.1k
64
41.1k
  return tree;
65
41.1k
}
66
67
/* Return a fresh copy of "tree".
68
 */
69
__isl_take isl_schedule_tree *isl_schedule_tree_dup(
70
  __isl_keep isl_schedule_tree *tree)
71
19.9k
{
72
19.9k
  isl_ctx *ctx;
73
19.9k
  isl_schedule_tree *dup;
74
19.9k
75
19.9k
  if (!tree)
76
0
    return NULL;
77
19.9k
78
19.9k
  ctx = isl_schedule_tree_get_ctx(tree);
79
19.9k
  dup = isl_schedule_tree_alloc(ctx, tree->type);
80
19.9k
  if (!dup)
81
0
    return NULL;
82
19.9k
83
19.9k
  switch (tree->type) {
84
19.9k
  case isl_schedule_node_error:
85
0
    isl_die(ctx, isl_error_internal,
86
0
      "allocation should have failed",
87
0
      return isl_schedule_tree_free(dup));
88
3.11k
  case isl_schedule_node_band:
89
3.11k
    dup->band = isl_schedule_band_copy(tree->band);
90
3.11k
    if (!dup->band)
91
0
      return isl_schedule_tree_free(dup);
92
3.11k
    break;
93
3.11k
  case isl_schedule_node_context:
94
0
    dup->context = isl_set_copy(tree->context);
95
0
    if (!dup->context)
96
0
      return isl_schedule_tree_free(dup);
97
0
    break;
98
7.02k
  case isl_schedule_node_domain:
99
7.02k
    dup->domain = isl_union_set_copy(tree->domain);
100
7.02k
    if (!dup->domain)
101
0
      return isl_schedule_tree_free(dup);
102
7.02k
    break;
103
7.02k
  case isl_schedule_node_expansion:
104
2
    dup->contraction =
105
2
      isl_union_pw_multi_aff_copy(tree->contraction);
106
2
    dup->expansion = isl_union_map_copy(tree->expansion);
107
2
    if (!dup->contraction || !dup->expansion)
108
0
      return isl_schedule_tree_free(dup);
109
2
    break;
110
60
  case isl_schedule_node_extension:
111
60
    dup->extension = isl_union_map_copy(tree->extension);
112
60
    if (!dup->extension)
113
0
      return isl_schedule_tree_free(dup);
114
60
    break;
115
5.22k
  case isl_schedule_node_filter:
116
5.22k
    dup->filter = isl_union_set_copy(tree->filter);
117
5.22k
    if (!dup->filter)
118
0
      return isl_schedule_tree_free(dup);
119
5.22k
    break;
120
5.22k
  case isl_schedule_node_guard:
121
0
    dup->guard = isl_set_copy(tree->guard);
122
0
    if (!dup->guard)
123
0
      return isl_schedule_tree_free(dup);
124
0
    break;
125
1.21k
  case isl_schedule_node_mark:
126
1.21k
    dup->mark = isl_id_copy(tree->mark);
127
1.21k
    if (!dup->mark)
128
0
      return isl_schedule_tree_free(dup);
129
1.21k
    break;
130
3.29k
  case isl_schedule_node_leaf:
131
3.29k
  case isl_schedule_node_sequence:
132
3.29k
  case isl_schedule_node_set:
133
3.29k
    break;
134
19.9k
  }
135
19.9k
136
19.9k
  if (tree->children) {
137
14.2k
    dup->children = isl_schedule_tree_list_copy(tree->children);
138
14.2k
    if (!dup->children)
139
0
      return isl_schedule_tree_free(dup);
140
19.9k
  }
141
19.9k
  dup->anchored = tree->anchored;
142
19.9k
143
19.9k
  return dup;
144
19.9k
}
145
146
/* Return an isl_schedule_tree that is equal to "tree" and that has only
147
 * a single reference.
148
 */
149
__isl_give isl_schedule_tree *isl_schedule_tree_cow(
150
  __isl_take isl_schedule_tree *tree)
151
26.8k
{
152
26.8k
  if (!tree)
153
0
    return NULL;
154
26.8k
155
26.8k
  if (tree->ref == 1)
156
6.89k
    return tree;
157
19.9k
  tree->ref--;
158
19.9k
  return isl_schedule_tree_dup(tree);
159
19.9k
}
160
161
/* Return a new reference to "tree".
162
 */
163
__isl_give isl_schedule_tree *isl_schedule_tree_copy(
164
  __isl_keep isl_schedule_tree *tree)
165
904k
{
166
904k
  if (!tree)
167
0
    return NULL;
168
904k
169
904k
  tree->ref++;
170
904k
  return tree;
171
904k
}
172
173
/* Free "tree" and return NULL.
174
 */
175
__isl_null isl_schedule_tree *isl_schedule_tree_free(
176
  __isl_take isl_schedule_tree *tree)
177
925k
{
178
925k
  if (!tree)
179
0
    return NULL;
180
925k
  if (--tree->ref > 0)
181
884k
    return NULL;
182
41.0k
183
41.0k
  switch (tree->type) {
184
41.0k
  case isl_schedule_node_band:
185
5.06k
    isl_schedule_band_free(tree->band);
186
5.06k
    break;
187
41.0k
  case isl_schedule_node_context:
188
0
    isl_set_free(tree->context);
189
0
    break;
190
41.0k
  case isl_schedule_node_domain:
191
13.0k
    isl_union_set_free(tree->domain);
192
13.0k
    break;
193
41.0k
  case isl_schedule_node_expansion:
194
5
    isl_union_pw_multi_aff_free(tree->contraction);
195
5
    isl_union_map_free(tree->expansion);
196
5
    break;
197
41.0k
  case isl_schedule_node_extension:
198
108
    isl_union_map_free(tree->extension);
199
108
    break;
200
41.0k
  case isl_schedule_node_filter:
201
7.12k
    isl_union_set_free(tree->filter);
202
7.12k
    break;
203
41.0k
  case isl_schedule_node_guard:
204
0
    isl_set_free(tree->guard);
205
0
    break;
206
41.0k
  case isl_schedule_node_mark:
207
1.37k
    isl_id_free(tree->mark);
208
1.37k
    break;
209
41.0k
  case isl_schedule_node_sequence:
210
14.3k
  case isl_schedule_node_set:
211
14.3k
  case isl_schedule_node_error:
212
14.3k
  case isl_schedule_node_leaf:
213
14.3k
    break;
214
41.0k
  }
215
41.0k
  isl_schedule_tree_list_free(tree->children);
216
41.0k
  isl_ctx_deref(tree->ctx);
217
41.0k
  free(tree);
218
41.0k
219
41.0k
  return NULL;
220
41.0k
}
221
222
/* Create and return a new leaf schedule tree.
223
 */
224
__isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
225
9.83k
{
226
9.83k
  return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
227
9.83k
}
228
229
/* Create a new band schedule tree referring to "band"
230
 * with no children.
231
 */
232
__isl_give isl_schedule_tree *isl_schedule_tree_from_band(
233
  __isl_take isl_schedule_band *band)
234
1.98k
{
235
1.98k
  isl_ctx *ctx;
236
1.98k
  isl_schedule_tree *tree;
237
1.98k
238
1.98k
  if (!band)
239
0
    return NULL;
240
1.98k
241
1.98k
  ctx = isl_schedule_band_get_ctx(band);
242
1.98k
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
243
1.98k
  if (!tree)
244
0
    goto error;
245
1.98k
246
1.98k
  tree->band = band;
247
1.98k
  tree->anchored = isl_schedule_band_is_anchored(band);
248
1.98k
249
1.98k
  return tree;
250
0
error:
251
0
  isl_schedule_band_free(band);
252
0
  return NULL;
253
1.98k
}
254
255
/* Create a new context schedule tree with the given context and no children.
256
 * Since the context references the outer schedule dimension,
257
 * the tree is anchored.
258
 */
259
__isl_give isl_schedule_tree *isl_schedule_tree_from_context(
260
  __isl_take isl_set *context)
261
0
{
262
0
  isl_ctx *ctx;
263
0
  isl_schedule_tree *tree;
264
0
265
0
  if (!context)
266
0
    return NULL;
267
0
268
0
  ctx = isl_set_get_ctx(context);
269
0
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
270
0
  if (!tree)
271
0
    goto error;
272
0
273
0
  tree->context = context;
274
0
  tree->anchored = 1;
275
0
276
0
  return tree;
277
0
error:
278
0
  isl_set_free(context);
279
0
  return NULL;
280
0
}
281
282
/* Create a new domain schedule tree with the given domain and no children.
283
 */
284
__isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
285
  __isl_take isl_union_set *domain)
286
6.08k
{
287
6.08k
  isl_ctx *ctx;
288
6.08k
  isl_schedule_tree *tree;
289
6.08k
290
6.08k
  if (!domain)
291
0
    return NULL;
292
6.08k
293
6.08k
  ctx = isl_union_set_get_ctx(domain);
294
6.08k
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
295
6.08k
  if (!tree)
296
0
    goto error;
297
6.08k
298
6.08k
  tree->domain = domain;
299
6.08k
300
6.08k
  return tree;
301
0
error:
302
0
  isl_union_set_free(domain);
303
0
  return NULL;
304
6.08k
}
305
306
/* Create a new expansion schedule tree with the given contraction and
307
 * expansion and no children.
308
 */
309
__isl_give isl_schedule_tree *isl_schedule_tree_from_expansion(
310
  __isl_take isl_union_pw_multi_aff *contraction,
311
  __isl_take isl_union_map *expansion)
312
3
{
313
3
  isl_ctx *ctx;
314
3
  isl_schedule_tree *tree;
315
3
316
3
  if (!contraction || !expansion)
317
0
    goto error;
318
3
319
3
  ctx = isl_union_map_get_ctx(expansion);
320
3
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_expansion);
321
3
  if (!tree)
322
0
    goto error;
323
3
324
3
  tree->contraction = contraction;
325
3
  tree->expansion = expansion;
326
3
327
3
  return tree;
328
0
error:
329
0
  isl_union_pw_multi_aff_free(contraction);
330
0
  isl_union_map_free(expansion);
331
0
  return NULL;
332
3
}
333
334
/* Create a new extension schedule tree with the given extension and
335
 * no children.
336
 * Since the domain of the extension refers to the outer schedule dimension,
337
 * the tree is anchored.
338
 */
339
__isl_give isl_schedule_tree *isl_schedule_tree_from_extension(
340
  __isl_take isl_union_map *extension)
341
48
{
342
48
  isl_ctx *ctx;
343
48
  isl_schedule_tree *tree;
344
48
345
48
  if (!extension)
346
0
    return NULL;
347
48
348
48
  ctx = isl_union_map_get_ctx(extension);
349
48
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_extension);
350
48
  if (!tree)
351
0
    goto error;
352
48
353
48
  tree->extension = extension;
354
48
  tree->anchored = 1;
355
48
356
48
  return tree;
357
0
error:
358
0
  isl_union_map_free(extension);
359
0
  return NULL;
360
48
}
361
362
/* Create a new filter schedule tree with the given filter and no children.
363
 */
364
__isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
365
  __isl_take isl_union_set *filter)
366
1.92k
{
367
1.92k
  isl_ctx *ctx;
368
1.92k
  isl_schedule_tree *tree;
369
1.92k
370
1.92k
  if (!filter)
371
0
    return NULL;
372
1.92k
373
1.92k
  ctx = isl_union_set_get_ctx(filter);
374
1.92k
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
375
1.92k
  if (!tree)
376
0
    goto error;
377
1.92k
378
1.92k
  tree->filter = filter;
379
1.92k
380
1.92k
  return tree;
381
0
error:
382
0
  isl_union_set_free(filter);
383
0
  return NULL;
384
1.92k
}
385
386
/* Create a new guard schedule tree with the given guard and no children.
387
 * Since the guard references the outer schedule dimension,
388
 * the tree is anchored.
389
 */
390
__isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
391
  __isl_take isl_set *guard)
392
0
{
393
0
  isl_ctx *ctx;
394
0
  isl_schedule_tree *tree;
395
0
396
0
  if (!guard)
397
0
    return NULL;
398
0
399
0
  ctx = isl_set_get_ctx(guard);
400
0
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
401
0
  if (!tree)
402
0
    goto error;
403
0
404
0
  tree->guard = guard;
405
0
  tree->anchored = 1;
406
0
407
0
  return tree;
408
0
error:
409
0
  isl_set_free(guard);
410
0
  return NULL;
411
0
}
412
413
/* Create a new mark schedule tree with the given mark identifier and
414
 * no children.
415
 */
416
__isl_give isl_schedule_tree *isl_schedule_tree_from_mark(
417
  __isl_take isl_id *mark)
418
158
{
419
158
  isl_ctx *ctx;
420
158
  isl_schedule_tree *tree;
421
158
422
158
  if (!mark)
423
0
    return NULL;
424
158
425
158
  ctx = isl_id_get_ctx(mark);
426
158
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark);
427
158
  if (!tree)
428
0
    goto error;
429
158
430
158
  tree->mark = mark;
431
158
432
158
  return tree;
433
0
error:
434
0
  isl_id_free(mark);
435
0
  return NULL;
436
158
}
437
438
/* Does "tree" have any node that depends on its position
439
 * in the complete schedule tree?
440
 */
441
isl_bool isl_schedule_tree_is_subtree_anchored(
442
  __isl_keep isl_schedule_tree *tree)
443
3.96k
{
444
3.96k
  return tree ? tree->anchored : 
isl_bool_error0
;
445
3.96k
}
446
447
/* Does the root node of "tree" depend on its position in the complete
448
 * schedule tree?
449
 * Band nodes may be anchored depending on the associated AST build options.
450
 * Context, extension and guard nodes are always anchored.
451
 */
452
int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
453
18.8k
{
454
18.8k
  if (!tree)
455
0
    return -1;
456
18.8k
457
18.8k
  switch (isl_schedule_tree_get_type(tree)) {
458
18.8k
  case isl_schedule_node_error:
459
0
    return -1;
460
18.8k
  case isl_schedule_node_band:
461
2.83k
    return isl_schedule_band_is_anchored(tree->band);
462
18.8k
  case isl_schedule_node_context:
463
84
  case isl_schedule_node_extension:
464
84
  case isl_schedule_node_guard:
465
84
    return 1;
466
15.9k
  case isl_schedule_node_domain:
467
15.9k
  case isl_schedule_node_expansion:
468
15.9k
  case isl_schedule_node_filter:
469
15.9k
  case isl_schedule_node_leaf:
470
15.9k
  case isl_schedule_node_mark:
471
15.9k
  case isl_schedule_node_sequence:
472
15.9k
  case isl_schedule_node_set:
473
15.9k
    return 0;
474
0
  }
475
0
476
0
  isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
477
0
    "unhandled case", return -1);
478
0
}
479
480
/* Update the anchored field of "tree" based on whether the root node
481
 * itself in anchored and the anchored fields of the children.
482
 *
483
 * This function should be called whenever the children of a tree node
484
 * are changed or the anchoredness of the tree root itself changes.
485
 */
486
__isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
487
  __isl_take isl_schedule_tree *tree)
488
18.6k
{
489
18.6k
  int i, n;
490
18.6k
  int anchored;
491
18.6k
492
18.6k
  if (!tree)
493
0
    return NULL;
494
18.6k
495
18.6k
  anchored = isl_schedule_tree_is_anchored(tree);
496
18.6k
  if (anchored < 0)
497
0
    return isl_schedule_tree_free(tree);
498
18.6k
499
18.6k
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
500
83.8k
  for (i = 0; !anchored && 
i < n82.5k
;
++i65.1k
) {
501
65.1k
    isl_schedule_tree *child;
502
65.1k
503
65.1k
    child = isl_schedule_tree_get_child(tree, i);
504
65.1k
    if (!child)
505
0
      return isl_schedule_tree_free(tree);
506
65.1k
    anchored = child->anchored;
507
65.1k
    isl_schedule_tree_free(child);
508
65.1k
  }
509
18.6k
510
18.6k
  if (anchored == tree->anchored)
511
18.3k
    return tree;
512
283
  tree = isl_schedule_tree_cow(tree);
513
283
  if (!tree)
514
0
    return NULL;
515
283
  tree->anchored = anchored;
516
283
  return tree;
517
283
}
518
519
/* Create a new tree of the given type (isl_schedule_node_sequence or
520
 * isl_schedule_node_set) with the given children.
521
 */
522
__isl_give isl_schedule_tree *isl_schedule_tree_from_children(
523
  enum isl_schedule_node_type type,
524
  __isl_take isl_schedule_tree_list *list)
525
1.21k
{
526
1.21k
  isl_ctx *ctx;
527
1.21k
  isl_schedule_tree *tree;
528
1.21k
529
1.21k
  if (!list)
530
0
    return NULL;
531
1.21k
532
1.21k
  ctx = isl_schedule_tree_list_get_ctx(list);
533
1.21k
  tree = isl_schedule_tree_alloc(ctx, type);
534
1.21k
  if (!tree)
535
0
    goto error;
536
1.21k
537
1.21k
  tree->children = list;
538
1.21k
  tree = isl_schedule_tree_update_anchored(tree);
539
1.21k
540
1.21k
  return tree;
541
0
error:
542
0
  isl_schedule_tree_list_free(list);
543
0
  return NULL;
544
1.21k
}
545
546
/* Construct a tree with a root node of type "type" and as children
547
 * "tree1" and "tree2".
548
 * If the root of one (or both) of the input trees is itself of type "type",
549
 * then the tree is replaced by its children.
550
 */
551
__isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
552
  enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
553
  __isl_take isl_schedule_tree *tree2)
554
1.14k
{
555
1.14k
  isl_ctx *ctx;
556
1.14k
  isl_schedule_tree_list *list;
557
1.14k
558
1.14k
  if (!tree1 || !tree2)
559
0
    goto error;
560
1.14k
561
1.14k
  ctx = isl_schedule_tree_get_ctx(tree1);
562
1.14k
  if (isl_schedule_tree_get_type(tree1) == type) {
563
524
    list = isl_schedule_tree_list_copy(tree1->children);
564
524
    isl_schedule_tree_free(tree1);
565
623
  } else {
566
623
    list = isl_schedule_tree_list_alloc(ctx, 2);
567
623
    list = isl_schedule_tree_list_add(list, tree1);
568
623
  }
569
1.14k
  if (isl_schedule_tree_get_type(tree2) == type) {
570
0
    isl_schedule_tree_list *children;
571
0
572
0
    children = isl_schedule_tree_list_copy(tree2->children);
573
0
    list = isl_schedule_tree_list_concat(list, children);
574
0
    isl_schedule_tree_free(tree2);
575
1.14k
  } else {
576
1.14k
    list = isl_schedule_tree_list_add(list, tree2);
577
1.14k
  }
578
1.14k
579
1.14k
  return isl_schedule_tree_from_children(type, list);
580
0
error:
581
0
  isl_schedule_tree_free(tree1);
582
0
  isl_schedule_tree_free(tree2);
583
0
  return NULL;
584
1.14k
}
585
586
/* Construct a tree with a sequence root node and as children
587
 * "tree1" and "tree2".
588
 * If the root of one (or both) of the input trees is itself a sequence,
589
 * then the tree is replaced by its children.
590
 */
591
__isl_give isl_schedule_tree *isl_schedule_tree_sequence_pair(
592
  __isl_take isl_schedule_tree *tree1,
593
  __isl_take isl_schedule_tree *tree2)
594
24
{
595
24
  return isl_schedule_tree_from_pair(isl_schedule_node_sequence,
596
24
            tree1, tree2);
597
24
}
598
599
/* Construct a tree with a set root node and as children
600
 * "tree1" and "tree2".
601
 * If the root of one (or both) of the input trees is itself a set,
602
 * then the tree is replaced by its children.
603
 */
604
__isl_give isl_schedule_tree *isl_schedule_tree_set_pair(
605
  __isl_take isl_schedule_tree *tree1,
606
  __isl_take isl_schedule_tree *tree2)
607
0
{
608
0
  return isl_schedule_tree_from_pair(isl_schedule_node_set, tree1, tree2);
609
0
}
610
611
/* Return the isl_ctx to which "tree" belongs.
612
 */
613
isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree)
614
150k
{
615
150k
  return tree ? tree->ctx : NULL;
616
150k
}
617
618
/* Return the type of the root of the tree or isl_schedule_node_error
619
 * on error.
620
 */
621
enum isl_schedule_node_type isl_schedule_tree_get_type(
622
  __isl_keep isl_schedule_tree *tree)
623
335k
{
624
335k
  return tree ? tree->type : 
isl_schedule_node_error0
;
625
335k
}
626
627
/* Are "tree1" and "tree2" obviously equal to each other?
628
 */
629
isl_bool isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1,
630
  __isl_keep isl_schedule_tree *tree2)
631
0
{
632
0
  isl_bool equal;
633
0
  int i, n;
634
0
635
0
  if (!tree1 || !tree2)
636
0
    return isl_bool_error;
637
0
  if (tree1 == tree2)
638
0
    return isl_bool_true;
639
0
  if (tree1->type != tree2->type)
640
0
    return isl_bool_false;
641
0
642
0
  switch (tree1->type) {
643
0
  case isl_schedule_node_band:
644
0
    equal = isl_schedule_band_plain_is_equal(tree1->band,
645
0
              tree2->band);
646
0
    break;
647
0
  case isl_schedule_node_context:
648
0
    equal = isl_set_is_equal(tree1->context, tree2->context);
649
0
    break;
650
0
  case isl_schedule_node_domain:
651
0
    equal = isl_union_set_is_equal(tree1->domain, tree2->domain);
652
0
    break;
653
0
  case isl_schedule_node_expansion:
654
0
    equal = isl_union_map_is_equal(tree1->expansion,
655
0
            tree2->expansion);
656
0
    if (equal >= 0 && equal)
657
0
      equal = isl_union_pw_multi_aff_plain_is_equal(
658
0
            tree1->contraction, tree2->contraction);
659
0
    break;
660
0
  case isl_schedule_node_extension:
661
0
    equal = isl_union_map_is_equal(tree1->extension,
662
0
            tree2->extension);
663
0
    break;
664
0
  case isl_schedule_node_filter:
665
0
    equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
666
0
    break;
667
0
  case isl_schedule_node_guard:
668
0
    equal = isl_set_is_equal(tree1->guard, tree2->guard);
669
0
    break;
670
0
  case isl_schedule_node_mark:
671
0
    equal = tree1->mark == tree2->mark;
672
0
    break;
673
0
  case isl_schedule_node_leaf:
674
0
  case isl_schedule_node_sequence:
675
0
  case isl_schedule_node_set:
676
0
    equal = isl_bool_true;
677
0
    break;
678
0
  case isl_schedule_node_error:
679
0
    equal = isl_bool_error;
680
0
    break;
681
0
  }
682
0
683
0
  if (equal < 0 || !equal)
684
0
    return equal;
685
0
686
0
  n = isl_schedule_tree_n_children(tree1);
687
0
  if (n != isl_schedule_tree_n_children(tree2))
688
0
    return isl_bool_false;
689
0
  for (i = 0; i < n; ++i) {
690
0
    isl_schedule_tree *child1, *child2;
691
0
692
0
    child1 = isl_schedule_tree_get_child(tree1, i);
693
0
    child2 = isl_schedule_tree_get_child(tree2, i);
694
0
    equal = isl_schedule_tree_plain_is_equal(child1, child2);
695
0
    isl_schedule_tree_free(child1);
696
0
    isl_schedule_tree_free(child2);
697
0
698
0
    if (equal < 0 || !equal)
699
0
      return equal;
700
0
  }
701
0
702
0
  return isl_bool_true;
703
0
}
704
705
/* Does "tree" have any children, other than an implicit leaf.
706
 */
707
int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree)
708
53.7k
{
709
53.7k
  if (!tree)
710
0
    return -1;
711
53.7k
712
53.7k
  return tree->children != NULL;
713
53.7k
}
714
715
/* Return the number of children of "tree", excluding implicit leaves.
716
 */
717
int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree *tree)
718
2.17k
{
719
2.17k
  if (!tree)
720
0
    return -1;
721
2.17k
722
2.17k
  return isl_schedule_tree_list_n_schedule_tree(tree->children);
723
2.17k
}
724
725
/* Return a copy of the (explicit) child at position "pos" of "tree".
726
 */
727
__isl_give isl_schedule_tree *isl_schedule_tree_get_child(
728
  __isl_keep isl_schedule_tree *tree, int pos)
729
98.9k
{
730
98.9k
  if (!tree)
731
0
    return NULL;
732
98.9k
  if (!tree->children)
733
98.9k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
734
98.9k
      "schedule tree has no explicit children", return NULL);
735
98.9k
  return isl_schedule_tree_list_get_schedule_tree(tree->children, pos);
736
98.9k
}
737
738
/* Return a copy of the (explicit) child at position "pos" of "tree" and
739
 * free "tree".
740
 */
741
__isl_give isl_schedule_tree *isl_schedule_tree_child(
742
  __isl_take isl_schedule_tree *tree, int pos)
743
1.23k
{
744
1.23k
  isl_schedule_tree *child;
745
1.23k
746
1.23k
  child = isl_schedule_tree_get_child(tree, pos);
747
1.23k
  isl_schedule_tree_free(tree);
748
1.23k
  return child;
749
1.23k
}
750
751
/* Remove all (explicit) children from "tree".
752
 */
753
__isl_give isl_schedule_tree *isl_schedule_tree_reset_children(
754
  __isl_take isl_schedule_tree *tree)
755
208
{
756
208
  tree = isl_schedule_tree_cow(tree);
757
208
  if (!tree)
758
0
    return NULL;
759
208
  tree->children = isl_schedule_tree_list_free(tree->children);
760
208
  return tree;
761
208
}
762
763
/* Remove the child at position "pos" from the children of "tree".
764
 * If there was only one child to begin with, then remove all children.
765
 */
766
__isl_give isl_schedule_tree *isl_schedule_tree_drop_child(
767
  __isl_take isl_schedule_tree *tree, int pos)
768
441
{
769
441
  int n;
770
441
771
441
  tree = isl_schedule_tree_cow(tree);
772
441
  if (!tree)
773
0
    return NULL;
774
441
775
441
  if (!isl_schedule_tree_has_children(tree))
776
441
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
777
441
      "tree does not have any explicit children",
778
441
      return isl_schedule_tree_free(tree));
779
441
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
780
441
  if (pos < 0 || pos >= n)
781
441
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
782
441
      "position out of bounds",
783
441
      return isl_schedule_tree_free(tree));
784
441
  if (n == 1)
785
0
    return isl_schedule_tree_reset_children(tree);
786
441
787
441
  tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1);
788
441
  if (!tree->children)
789
0
    return isl_schedule_tree_free(tree);
790
441
791
441
  return tree;
792
441
}
793
794
/* Replace the child at position "pos" of "tree" by "child".
795
 *
796
 * If the new child is a leaf, then it is not explicitly
797
 * recorded in the list of children.  Instead, the list of children
798
 * (which is assumed to have only one element) is removed.
799
 * Note that the children of set and sequence nodes are always
800
 * filters, so they cannot be replaced by empty trees.
801
 */
802
__isl_give isl_schedule_tree *isl_schedule_tree_replace_child(
803
  __isl_take isl_schedule_tree *tree, int pos,
804
  __isl_take isl_schedule_tree *child)
805
19.0k
{
806
19.0k
  tree = isl_schedule_tree_cow(tree);
807
19.0k
  if (!tree || !child)
808
0
    goto error;
809
19.0k
810
19.0k
  if (isl_schedule_tree_is_leaf(child)) {
811
1.63k
    isl_schedule_tree_free(child);
812
1.63k
    if (!tree->children && 
pos == 01.43k
)
813
1.43k
      return tree;
814
201
    if (isl_schedule_tree_n_children(tree) != 1)
815
201
      
isl_die0
(isl_schedule_tree_get_ctx(tree),
816
201
        isl_error_internal,
817
201
        "can only replace single child by leaf",
818
201
        goto error);
819
201
    return isl_schedule_tree_reset_children(tree);
820
17.4k
  }
821
17.4k
822
17.4k
  if (!tree->children && 
pos == 03.90k
)
823
3.90k
    tree->children =
824
3.90k
      isl_schedule_tree_list_from_schedule_tree(child);
825
13.5k
  else
826
13.5k
    tree->children = isl_schedule_tree_list_set_schedule_tree(
827
13.5k
        tree->children, pos, child);
828
17.4k
829
17.4k
  if (!tree->children)
830
0
    return isl_schedule_tree_free(tree);
831
17.4k
  tree = isl_schedule_tree_update_anchored(tree);
832
17.4k
833
17.4k
  return tree;
834
0
error:
835
0
  isl_schedule_tree_free(tree);
836
0
  isl_schedule_tree_free(child);
837
0
  return NULL;
838
17.4k
}
839
840
/* Replace the (explicit) children of "tree" by "children"?
841
 */
842
__isl_give isl_schedule_tree *isl_schedule_tree_set_children(
843
  __isl_take isl_schedule_tree *tree,
844
  __isl_take isl_schedule_tree_list *children)
845
7
{
846
7
  tree = isl_schedule_tree_cow(tree);
847
7
  if (!tree || !children)
848
0
    goto error;
849
7
  isl_schedule_tree_list_free(tree->children);
850
7
  tree->children = children;
851
7
  return tree;
852
0
error:
853
0
  isl_schedule_tree_free(tree);
854
0
  isl_schedule_tree_list_free(children);
855
0
  return NULL;
856
7
}
857
858
/* Create a new band schedule tree referring to "band"
859
 * with "tree" as single child.
860
 */
861
__isl_give isl_schedule_tree *isl_schedule_tree_insert_band(
862
  __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_band *band)
863
1.98k
{
864
1.98k
  isl_schedule_tree *res;
865
1.98k
866
1.98k
  res = isl_schedule_tree_from_band(band);
867
1.98k
  return isl_schedule_tree_replace_child(res, 0, tree);
868
1.98k
}
869
870
/* Create a new context schedule tree with the given context and
871
 * with "tree" as single child.
872
 */
873
__isl_give isl_schedule_tree *isl_schedule_tree_insert_context(
874
  __isl_take isl_schedule_tree *tree, __isl_take isl_set *context)
875
0
{
876
0
  isl_schedule_tree *res;
877
0
878
0
  res = isl_schedule_tree_from_context(context);
879
0
  return isl_schedule_tree_replace_child(res, 0, tree);
880
0
}
881
882
/* Create a new domain schedule tree with the given domain and
883
 * with "tree" as single child.
884
 */
885
__isl_give isl_schedule_tree *isl_schedule_tree_insert_domain(
886
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
887
1.12k
{
888
1.12k
  isl_schedule_tree *res;
889
1.12k
890
1.12k
  res = isl_schedule_tree_from_domain(domain);
891
1.12k
  return isl_schedule_tree_replace_child(res, 0, tree);
892
1.12k
}
893
894
/* Create a new expansion schedule tree with the given contraction and
895
 * expansion and with "tree" as single child.
896
 */
897
__isl_give isl_schedule_tree *isl_schedule_tree_insert_expansion(
898
  __isl_take isl_schedule_tree *tree,
899
  __isl_take isl_union_pw_multi_aff *contraction,
900
  __isl_take isl_union_map *expansion)
901
3
{
902
3
  isl_schedule_tree *res;
903
3
904
3
  res = isl_schedule_tree_from_expansion(contraction, expansion);
905
3
  return isl_schedule_tree_replace_child(res, 0, tree);
906
3
}
907
908
/* Create a new extension schedule tree with the given extension and
909
 * with "tree" as single child.
910
 */
911
__isl_give isl_schedule_tree *isl_schedule_tree_insert_extension(
912
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
913
24
{
914
24
  isl_schedule_tree *res;
915
24
916
24
  res = isl_schedule_tree_from_extension(extension);
917
24
  return isl_schedule_tree_replace_child(res, 0, tree);
918
24
}
919
920
/* Create a new filter schedule tree with the given filter and single child.
921
 *
922
 * If the root of "tree" is itself a filter node, then the two
923
 * filter nodes are merged into one node.
924
 */
925
__isl_give isl_schedule_tree *isl_schedule_tree_insert_filter(
926
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
927
3.33k
{
928
3.33k
  isl_schedule_tree *res;
929
3.33k
930
3.33k
  if (isl_schedule_tree_get_type(tree) == isl_schedule_node_filter) {
931
2.71k
    isl_union_set *tree_filter;
932
2.71k
933
2.71k
    tree_filter = isl_schedule_tree_filter_get_filter(tree);
934
2.71k
    tree_filter = isl_union_set_intersect(tree_filter, filter);
935
2.71k
    tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
936
2.71k
    return tree;
937
2.71k
  }
938
625
939
625
  res = isl_schedule_tree_from_filter(filter);
940
625
  return isl_schedule_tree_replace_child(res, 0, tree);
941
625
}
942
943
/* Insert a filter node with filter set "filter"
944
 * in each of the children of "tree".
945
 */
946
__isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter(
947
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
948
524
{
949
524
  int i, n;
950
524
951
524
  if (!tree || !filter)
952
0
    goto error;
953
524
954
524
  n = isl_schedule_tree_n_children(tree);
955
3.23k
  for (i = 0; i < n; 
++i2.71k
) {
956
2.71k
    isl_schedule_tree *child;
957
2.71k
958
2.71k
    child = isl_schedule_tree_get_child(tree, i);
959
2.71k
    child = isl_schedule_tree_insert_filter(child,
960
2.71k
                isl_union_set_copy(filter));
961
2.71k
    tree = isl_schedule_tree_replace_child(tree, i, child);
962
2.71k
  }
963
524
964
524
  isl_union_set_free(filter);
965
524
  return tree;
966
0
error:
967
0
  isl_union_set_free(filter);
968
0
  isl_schedule_tree_free(tree);
969
0
  return NULL;
970
524
}
971
972
/* Create a new guard schedule tree with the given guard and
973
 * with "tree" as single child.
974
 */
975
__isl_give isl_schedule_tree *isl_schedule_tree_insert_guard(
976
  __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard)
977
0
{
978
0
  isl_schedule_tree *res;
979
0
980
0
  res = isl_schedule_tree_from_guard(guard);
981
0
  return isl_schedule_tree_replace_child(res, 0, tree);
982
0
}
983
984
/* Create a new mark schedule tree with the given mark identifier and
985
 * single child.
986
 */
987
__isl_give isl_schedule_tree *isl_schedule_tree_insert_mark(
988
  __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark)
989
158
{
990
158
  isl_schedule_tree *res;
991
158
992
158
  res = isl_schedule_tree_from_mark(mark);
993
158
  return isl_schedule_tree_replace_child(res, 0, tree);
994
158
}
995
996
/* Return the number of members in the band tree root.
997
 */
998
unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree)
999
77.2k
{
1000
77.2k
  if (!tree)
1001
0
    return 0;
1002
77.2k
1003
77.2k
  if (tree->type != isl_schedule_node_band)
1004
77.2k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1005
77.2k
      "not a band node", return 0);
1006
77.2k
1007
77.2k
  return isl_schedule_band_n_member(tree->band);
1008
77.2k
}
1009
1010
/* Is the band member at position "pos" of the band tree root
1011
 * marked coincident?
1012
 */
1013
isl_bool isl_schedule_tree_band_member_get_coincident(
1014
  __isl_keep isl_schedule_tree *tree, int pos)
1015
1.00k
{
1016
1.00k
  if (!tree)
1017
0
    return isl_bool_error;
1018
1.00k
1019
1.00k
  if (tree->type != isl_schedule_node_band)
1020
1.00k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1021
1.00k
      "not a band node", return isl_bool_error);
1022
1.00k
1023
1.00k
  return isl_schedule_band_member_get_coincident(tree->band, pos);
1024
1.00k
}
1025
1026
/* Mark the given band member as being coincident or not
1027
 * according to "coincident".
1028
 */
1029
__isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_coincident(
1030
  __isl_take isl_schedule_tree *tree, int pos, int coincident)
1031
187
{
1032
187
  if (!tree)
1033
0
    return NULL;
1034
187
  if (tree->type != isl_schedule_node_band)
1035
187
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1036
187
      "not a band node", return isl_schedule_tree_free(tree));
1037
187
  if (isl_schedule_tree_band_member_get_coincident(tree, pos) ==
1038
187
                    coincident)
1039
0
    return tree;
1040
187
  tree = isl_schedule_tree_cow(tree);
1041
187
  if (!tree)
1042
0
    return NULL;
1043
187
1044
187
  tree->band = isl_schedule_band_member_set_coincident(tree->band, pos,
1045
187
              coincident);
1046
187
  if (!tree->band)
1047
0
    return isl_schedule_tree_free(tree);
1048
187
  return tree;
1049
187
}
1050
1051
/* Is the band tree root marked permutable?
1052
 */
1053
isl_bool isl_schedule_tree_band_get_permutable(
1054
  __isl_keep isl_schedule_tree *tree)
1055
798
{
1056
798
  if (!tree)
1057
0
    return isl_bool_error;
1058
798
1059
798
  if (tree->type != isl_schedule_node_band)
1060
798
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1061
798
      "not a band node", return isl_bool_error);
1062
798
1063
798
  return isl_schedule_band_get_permutable(tree->band);
1064
798
}
1065
1066
/* Mark the band tree root permutable or not according to "permutable"?
1067
 */
1068
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_permutable(
1069
  __isl_take isl_schedule_tree *tree, int permutable)
1070
142
{
1071
142
  if (!tree)
1072
0
    return NULL;
1073
142
  if (tree->type != isl_schedule_node_band)
1074
142
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1075
142
      "not a band node", return isl_schedule_tree_free(tree));
1076
142
  if (isl_schedule_tree_band_get_permutable(tree) == permutable)
1077
0
    return tree;
1078
142
  tree = isl_schedule_tree_cow(tree);
1079
142
  if (!tree)
1080
0
    return NULL;
1081
142
1082
142
  tree->band = isl_schedule_band_set_permutable(tree->band, permutable);
1083
142
  if (!tree->band)
1084
0
    return isl_schedule_tree_free(tree);
1085
142
  return tree;
1086
142
}
1087
1088
/* Return the schedule space of the band tree root.
1089
 */
1090
__isl_give isl_space *isl_schedule_tree_band_get_space(
1091
  __isl_keep isl_schedule_tree *tree)
1092
308
{
1093
308
  if (!tree)
1094
0
    return NULL;
1095
308
1096
308
  if (tree->type != isl_schedule_node_band)
1097
308
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1098
308
      "not a band node", return NULL);
1099
308
1100
308
  return isl_schedule_band_get_space(tree->band);
1101
308
}
1102
1103
/* Intersect the domain of the band schedule of the band tree root
1104
 * with "domain".
1105
 */
1106
__isl_give isl_schedule_tree *isl_schedule_tree_band_intersect_domain(
1107
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1108
2
{
1109
2
  if (!tree || !domain)
1110
0
    goto error;
1111
2
1112
2
  if (tree->type != isl_schedule_node_band)
1113
2
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1114
2
      "not a band node", goto error);
1115
2
1116
2
  tree->band = isl_schedule_band_intersect_domain(tree->band, domain);
1117
2
  if (!tree->band)
1118
0
    return isl_schedule_tree_free(tree);
1119
2
1120
2
  return tree;
1121
0
error:
1122
0
  isl_schedule_tree_free(tree);
1123
0
  isl_union_set_free(domain);
1124
0
  return NULL;
1125
2
}
1126
1127
/* Return the schedule of the band tree root in isolation.
1128
 */
1129
__isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
1130
  __isl_keep isl_schedule_tree *tree)
1131
7.79k
{
1132
7.79k
  if (!tree)
1133
0
    return NULL;
1134
7.79k
1135
7.79k
  if (tree->type != isl_schedule_node_band)
1136
7.79k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1137
7.79k
      "not a band node", return NULL);
1138
7.79k
1139
7.79k
  return isl_schedule_band_get_partial_schedule(tree->band);
1140
7.79k
}
1141
1142
/* Replace the schedule of the band tree root by "schedule".
1143
 */
1144
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_partial_schedule(
1145
  __isl_take isl_schedule_tree *tree,
1146
  __isl_take isl_multi_union_pw_aff *schedule)
1147
2
{
1148
2
  tree = isl_schedule_tree_cow(tree);
1149
2
  if (!tree || !schedule)
1150
0
    goto error;
1151
2
1152
2
  if (tree->type != isl_schedule_node_band)
1153
2
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1154
2
      "not a band node", return NULL);
1155
2
  tree->band = isl_schedule_band_set_partial_schedule(tree->band,
1156
2
                schedule);
1157
2
1158
2
  return tree;
1159
0
error:
1160
0
  isl_schedule_tree_free(tree);
1161
0
  isl_multi_union_pw_aff_free(schedule);
1162
0
  return NULL;
1163
2
}
1164
1165
/* Return the loop AST generation type for the band member
1166
 * of the band tree root at position "pos".
1167
 */
1168
enum isl_ast_loop_type isl_schedule_tree_band_member_get_ast_loop_type(
1169
  __isl_keep isl_schedule_tree *tree, int pos)
1170
791
{
1171
791
  if (!tree)
1172
0
    return isl_ast_loop_error;
1173
791
1174
791
  if (tree->type != isl_schedule_node_band)
1175
791
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1176
791
      "not a band node", return isl_ast_loop_error);
1177
791
1178
791
  return isl_schedule_band_member_get_ast_loop_type(tree->band, pos);
1179
791
}
1180
1181
/* Set the loop AST generation type for the band member of the band tree root
1182
 * at position "pos" to "type".
1183
 */
1184
__isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
1185
  __isl_take isl_schedule_tree *tree, int pos,
1186
  enum isl_ast_loop_type type)
1187
0
{
1188
0
  tree = isl_schedule_tree_cow(tree);
1189
0
  if (!tree)
1190
0
    return NULL;
1191
0
1192
0
  if (tree->type != isl_schedule_node_band)
1193
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1194
0
      "not a band node", return isl_schedule_tree_free(tree));
1195
0
1196
0
  tree->band = isl_schedule_band_member_set_ast_loop_type(tree->band,
1197
0
                pos, type);
1198
0
  if (!tree->band)
1199
0
    return isl_schedule_tree_free(tree);
1200
0
1201
0
  return tree;
1202
0
}
1203
1204
/* Return the loop AST generation type for the band member
1205
 * of the band tree root at position "pos" for the isolated part.
1206
 */
1207
enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1208
  __isl_keep isl_schedule_tree *tree, int pos)
1209
913
{
1210
913
  if (!tree)
1211
0
    return isl_ast_loop_error;
1212
913
1213
913
  if (tree->type != isl_schedule_node_band)
1214
913
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1215
913
      "not a band node", return isl_ast_loop_error);
1216
913
1217
913
  return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
1218
913
                  pos);
1219
913
}
1220
1221
/* Set the loop AST generation type for the band member of the band tree root
1222
 * at position "pos" for the isolated part to "type".
1223
 */
1224
__isl_give isl_schedule_tree *
1225
isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1226
  __isl_take isl_schedule_tree *tree, int pos,
1227
  enum isl_ast_loop_type type)
1228
0
{
1229
0
  tree = isl_schedule_tree_cow(tree);
1230
0
  if (!tree)
1231
0
    return NULL;
1232
0
1233
0
  if (tree->type != isl_schedule_node_band)
1234
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1235
0
      "not a band node", return isl_schedule_tree_free(tree));
1236
0
1237
0
  tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
1238
0
              tree->band, pos, type);
1239
0
  if (!tree->band)
1240
0
    return isl_schedule_tree_free(tree);
1241
0
1242
0
  return tree;
1243
0
}
1244
1245
/* Return the AST build options associated to the band tree root.
1246
 */
1247
__isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
1248
  __isl_keep isl_schedule_tree *tree)
1249
0
{
1250
0
  if (!tree)
1251
0
    return NULL;
1252
0
1253
0
  if (tree->type != isl_schedule_node_band)
1254
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1255
0
      "not a band node", return NULL);
1256
0
1257
0
  return isl_schedule_band_get_ast_build_options(tree->band);
1258
0
}
1259
1260
/* Replace the AST build options associated to band tree root by "options".
1261
 * Updated the anchored field if the anchoredness of the root node itself
1262
 * changes.
1263
 */
1264
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
1265
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
1266
72
{
1267
72
  int was_anchored;
1268
72
1269
72
  tree = isl_schedule_tree_cow(tree);
1270
72
  if (!tree || !options)
1271
0
    goto error;
1272
72
1273
72
  if (tree->type != isl_schedule_node_band)
1274
72
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1275
72
      "not a band node", goto error);
1276
72
1277
72
  was_anchored = isl_schedule_tree_is_anchored(tree);
1278
72
  tree->band = isl_schedule_band_set_ast_build_options(tree->band,
1279
72
                options);
1280
72
  if (!tree->band)
1281
0
    return isl_schedule_tree_free(tree);
1282
72
  if (isl_schedule_tree_is_anchored(tree) != was_anchored)
1283
40
    tree = isl_schedule_tree_update_anchored(tree);
1284
72
1285
72
  return tree;
1286
0
error:
1287
0
  isl_schedule_tree_free(tree);
1288
0
  isl_union_set_free(options);
1289
0
  return NULL;
1290
72
}
1291
1292
/* Return the "isolate" option associated to the band tree root of "tree",
1293
 * which is assumed to appear at schedule depth "depth".
1294
 */
1295
__isl_give isl_set *isl_schedule_tree_band_get_ast_isolate_option(
1296
  __isl_keep isl_schedule_tree *tree, int depth)
1297
2.35k
{
1298
2.35k
  if (!tree)
1299
0
    return NULL;
1300
2.35k
1301
2.35k
  if (tree->type != isl_schedule_node_band)
1302
2.35k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1303
2.35k
      "not a band node", return NULL);
1304
2.35k
1305
2.35k
  return isl_schedule_band_get_ast_isolate_option(tree->band, depth);
1306
2.35k
}
1307
1308
/* Return the context of the context tree root.
1309
 */
1310
__isl_give isl_set *isl_schedule_tree_context_get_context(
1311
  __isl_keep isl_schedule_tree *tree)
1312
0
{
1313
0
  if (!tree)
1314
0
    return NULL;
1315
0
1316
0
  if (tree->type != isl_schedule_node_context)
1317
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1318
0
      "not a context node", return NULL);
1319
0
1320
0
  return isl_set_copy(tree->context);
1321
0
}
1322
1323
/* Return the domain of the domain tree root.
1324
 */
1325
__isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1326
  __isl_keep isl_schedule_tree *tree)
1327
17.0k
{
1328
17.0k
  if (!tree)
1329
0
    return NULL;
1330
17.0k
1331
17.0k
  if (tree->type != isl_schedule_node_domain)
1332
17.0k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1333
17.0k
      "not a domain node", return NULL);
1334
17.0k
1335
17.0k
  return isl_union_set_copy(tree->domain);
1336
17.0k
}
1337
1338
/* Replace the domain of domain tree root "tree" by "domain".
1339
 */
1340
__isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1341
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1342
1.39k
{
1343
1.39k
  tree = isl_schedule_tree_cow(tree);
1344
1.39k
  if (!tree || !domain)
1345
0
    goto error;
1346
1.39k
1347
1.39k
  if (tree->type != isl_schedule_node_domain)
1348
1.39k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1349
1.39k
      "not a domain node", goto error);
1350
1.39k
1351
1.39k
  isl_union_set_free(tree->domain);
1352
1.39k
  tree->domain = domain;
1353
1.39k
1354
1.39k
  return tree;
1355
0
error:
1356
0
  isl_schedule_tree_free(tree);
1357
0
  isl_union_set_free(domain);
1358
0
  return NULL;
1359
1.39k
}
1360
1361
/* Return the contraction of the expansion tree root.
1362
 */
1363
__isl_give isl_union_pw_multi_aff *isl_schedule_tree_expansion_get_contraction(
1364
  __isl_keep isl_schedule_tree *tree)
1365
8
{
1366
8
  if (!tree)
1367
0
    return NULL;
1368
8
1369
8
  if (tree->type != isl_schedule_node_expansion)
1370
8
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1371
8
      "not an expansion node", return NULL);
1372
8
1373
8
  return isl_union_pw_multi_aff_copy(tree->contraction);
1374
8
}
1375
1376
/* Return the expansion of the expansion tree root.
1377
 */
1378
__isl_give isl_union_map *isl_schedule_tree_expansion_get_expansion(
1379
  __isl_keep isl_schedule_tree *tree)
1380
13
{
1381
13
  if (!tree)
1382
0
    return NULL;
1383
13
1384
13
  if (tree->type != isl_schedule_node_expansion)
1385
13
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1386
13
      "not an expansion node", return NULL);
1387
13
1388
13
  return isl_union_map_copy(tree->expansion);
1389
13
}
1390
1391
/* Replace the contraction and the expansion of the expansion tree root "tree"
1392
 * by "contraction" and "expansion".
1393
 */
1394
__isl_give isl_schedule_tree *
1395
isl_schedule_tree_expansion_set_contraction_and_expansion(
1396
  __isl_take isl_schedule_tree *tree,
1397
  __isl_take isl_union_pw_multi_aff *contraction,
1398
  __isl_take isl_union_map *expansion)
1399
1
{
1400
1
  tree = isl_schedule_tree_cow(tree);
1401
1
  if (!tree || !contraction || !expansion)
1402
0
    goto error;
1403
1
1404
1
  if (tree->type != isl_schedule_node_expansion)
1405
1
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1406
1
      "not an expansion node", return NULL);
1407
1
1408
1
  isl_union_pw_multi_aff_free(tree->contraction);
1409
1
  tree->contraction = contraction;
1410
1
  isl_union_map_free(tree->expansion);
1411
1
  tree->expansion = expansion;
1412
1
1413
1
  return tree;
1414
0
error:
1415
0
  isl_schedule_tree_free(tree);
1416
0
  isl_union_pw_multi_aff_free(contraction);
1417
0
  isl_union_map_free(expansion);
1418
0
  return NULL;
1419
1
}
1420
1421
/* Return the extension of the extension tree root.
1422
 */
1423
__isl_give isl_union_map *isl_schedule_tree_extension_get_extension(
1424
  __isl_take isl_schedule_tree *tree)
1425
70
{
1426
70
  if (!tree)
1427
0
    return NULL;
1428
70
1429
70
  if (tree->type != isl_schedule_node_extension)
1430
70
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1431
70
      "not an extension node", return NULL);
1432
70
1433
70
  return isl_union_map_copy(tree->extension);
1434
70
}
1435
1436
/* Replace the extension of extension tree root "tree" by "extension".
1437
 */
1438
__isl_give isl_schedule_tree *isl_schedule_tree_extension_set_extension(
1439
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
1440
0
{
1441
0
  tree = isl_schedule_tree_cow(tree);
1442
0
  if (!tree || !extension)
1443
0
    goto error;
1444
0
1445
0
  if (tree->type != isl_schedule_node_extension)
1446
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1447
0
      "not an extension node", return NULL);
1448
0
  isl_union_map_free(tree->extension);
1449
0
  tree->extension = extension;
1450
0
1451
0
  return tree;
1452
0
error:
1453
0
  isl_schedule_tree_free(tree);
1454
0
  isl_union_map_free(extension);
1455
0
  return NULL;
1456
0
}
1457
1458
/* Return the filter of the filter tree root.
1459
 */
1460
__isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1461
  __isl_keep isl_schedule_tree *tree)
1462
21.7k
{
1463
21.7k
  if (!tree)
1464
0
    return NULL;
1465
21.7k
1466
21.7k
  if (tree->type != isl_schedule_node_filter)
1467
21.7k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1468
21.7k
      "not a filter node", return NULL);
1469
21.7k
1470
21.7k
  return isl_union_set_copy(tree->filter);
1471
21.7k
}
1472
1473
/* Replace the filter of the filter tree root by "filter".
1474
 */
1475
__isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1476
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1477
3.81k
{
1478
3.81k
  tree = isl_schedule_tree_cow(tree);
1479
3.81k
  if (!tree || !filter)
1480
0
    goto error;
1481
3.81k
1482
3.81k
  if (tree->type != isl_schedule_node_filter)
1483
3.81k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1484
3.81k
      "not a filter node", return NULL);
1485
3.81k
1486
3.81k
  isl_union_set_free(tree->filter);
1487
3.81k
  tree->filter = filter;
1488
3.81k
1489
3.81k
  return tree;
1490
0
error:
1491
0
  isl_schedule_tree_free(tree);
1492
0
  isl_union_set_free(filter);
1493
0
  return NULL;
1494
3.81k
}
1495
1496
/* Return the guard of the guard tree root.
1497
 */
1498
__isl_give isl_set *isl_schedule_tree_guard_get_guard(
1499
  __isl_take isl_schedule_tree *tree)
1500
0
{
1501
0
  if (!tree)
1502
0
    return NULL;
1503
0
1504
0
  if (tree->type != isl_schedule_node_guard)
1505
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1506
0
      "not a guard node", return NULL);
1507
0
1508
0
  return isl_set_copy(tree->guard);
1509
0
}
1510
1511
/* Return the mark identifier of the mark tree root "tree".
1512
 */
1513
__isl_give isl_id *isl_schedule_tree_mark_get_id(
1514
  __isl_keep isl_schedule_tree *tree)
1515
154
{
1516
154
  if (!tree)
1517
0
    return NULL;
1518
154
1519
154
  if (tree->type != isl_schedule_node_mark)
1520
154
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1521
154
      "not a mark node", return NULL);
1522
154
1523
154
  return isl_id_copy(tree->mark);
1524
154
}
1525
1526
/* Set dim to the range dimension of "map" and abort the search.
1527
 */
1528
static isl_stat set_range_dim(__isl_take isl_map *map, void *user)
1529
5.30k
{
1530
5.30k
  int *dim = user;
1531
5.30k
1532
5.30k
  *dim = isl_map_dim(map, isl_dim_out);
1533
5.30k
  isl_map_free(map);
1534
5.30k
1535
5.30k
  return isl_stat_error;
1536
5.30k
}
1537
1538
/* Return the dimension of the range of "umap".
1539
 * "umap" is assumed not to be empty and
1540
 * all maps inside "umap" are assumed to have the same range.
1541
 *
1542
 * We extract the range dimension from the first map in "umap".
1543
 */
1544
static int range_dim(__isl_keep isl_union_map *umap)
1545
5.30k
{
1546
5.30k
  int dim = -1;
1547
5.30k
1548
5.30k
  if (!umap)
1549
0
    return -1;
1550
5.30k
  if (isl_union_map_n_map(umap) == 0)
1551
5.30k
    
isl_die0
(isl_union_map_get_ctx(umap), isl_error_internal,
1552
5.30k
      "unexpected empty input", return -1);
1553
5.30k
1554
5.30k
  isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1555
5.30k
1556
5.30k
  return dim;
1557
5.30k
}
1558
1559
/* Append an "extra" number of zeros to the range of "umap" and
1560
 * return the result.
1561
 */
1562
static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1563
  int extra)
1564
2.01k
{
1565
2.01k
  isl_union_set *dom;
1566
2.01k
  isl_space *space;
1567
2.01k
  isl_multi_val *mv;
1568
2.01k
  isl_union_pw_multi_aff *suffix;
1569
2.01k
  isl_union_map *universe;
1570
2.01k
  isl_union_map *suffix_umap;
1571
2.01k
1572
2.01k
  universe = isl_union_map_universe(isl_union_map_copy(umap));
1573
2.01k
  dom = isl_union_map_domain(universe);
1574
2.01k
  space = isl_union_set_get_space(dom);
1575
2.01k
  space = isl_space_set_from_params(space);
1576
2.01k
  space = isl_space_add_dims(space, isl_dim_set, extra);
1577
2.01k
  mv = isl_multi_val_zero(space);
1578
2.01k
1579
2.01k
  suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1580
2.01k
  suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1581
2.01k
  umap = isl_union_map_flat_range_product(umap, suffix_umap);
1582
2.01k
1583
2.01k
  return umap;
1584
2.01k
}
1585
1586
/* Should we skip the root of "tree" while looking for the first
1587
 * descendant with schedule information?
1588
 * That is, is it impossible to derive any information about
1589
 * the iteration domain from this node?
1590
 *
1591
 * We do not want to skip leaf or error nodes because there is
1592
 * no point in looking any deeper from these nodes.
1593
 * We can only extract partial iteration domain information
1594
 * from an extension node, but extension nodes are not supported
1595
 * by the caller and it will error out on them.
1596
 */
1597
static int domain_less(__isl_keep isl_schedule_tree *tree)
1598
1.52k
{
1599
1.52k
  enum isl_schedule_node_type type;
1600
1.52k
1601
1.52k
  type = isl_schedule_tree_get_type(tree);
1602
1.52k
  switch (type) {
1603
1.52k
  case isl_schedule_node_band:
1604
1.14k
    return isl_schedule_tree_band_n_member(tree) == 0;
1605
1.52k
  case isl_schedule_node_context:
1606
11
  case isl_schedule_node_guard:
1607
11
  case isl_schedule_node_mark:
1608
11
    return 1;
1609
376
  case isl_schedule_node_leaf:
1610
376
  case isl_schedule_node_error:
1611
376
  case isl_schedule_node_domain:
1612
376
  case isl_schedule_node_expansion:
1613
376
  case isl_schedule_node_extension:
1614
376
  case isl_schedule_node_filter:
1615
376
  case isl_schedule_node_set:
1616
376
  case isl_schedule_node_sequence:
1617
376
    return 0;
1618
0
  }
1619
0
1620
0
  isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1621
0
    "unhandled case", return 0);
1622
0
}
1623
1624
/* Move down to the first descendant of "tree" that contains any schedule
1625
 * information or return "leaf" if there is no such descendant.
1626
 */
1627
__isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1628
  __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1629
1.51k
{
1630
1.52k
  while (domain_less(tree)) {
1631
11
    if (!isl_schedule_tree_has_children(tree)) {
1632
0
      isl_schedule_tree_free(tree);
1633
0
      return isl_schedule_tree_copy(leaf);
1634
0
    }
1635
11
    tree = isl_schedule_tree_child(tree, 0);
1636
11
  }
1637
1.51k
1638
1.51k
  return tree;
1639
1.51k
}
1640
1641
static __isl_give isl_union_map *subtree_schedule_extend(
1642
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1643
1644
/* Extend the schedule map "outer" with the subtree schedule
1645
 * of the (single) child of "tree", if any.
1646
 *
1647
 * If "tree" does not have any descendants (apart from those that
1648
 * do not carry any schedule information), then we simply return "outer".
1649
 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1650
 * of the single child.
1651
 */
1652
static __isl_give isl_union_map *subtree_schedule_extend_child(
1653
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1654
8.50k
{
1655
8.50k
  isl_schedule_tree *child;
1656
8.50k
  isl_union_map *res;
1657
8.50k
1658
8.50k
  if (!tree)
1659
0
    return isl_union_map_free(outer);
1660
8.50k
  if (!isl_schedule_tree_has_children(tree))
1661
5.65k
    return outer;
1662
2.84k
  child = isl_schedule_tree_get_child(tree, 0);
1663
2.84k
  if (!child)
1664
0
    return isl_union_map_free(outer);
1665
2.84k
  res = subtree_schedule_extend(child, outer);
1666
2.84k
  isl_schedule_tree_free(child);
1667
2.84k
  return res;
1668
2.84k
}
1669
1670
/* Extract the parameter space from one of the children of "tree",
1671
 * which are assumed to be filters.
1672
 */
1673
static __isl_give isl_space *extract_space_from_filter_child(
1674
  __isl_keep isl_schedule_tree *tree)
1675
1.48k
{
1676
1.48k
  isl_space *space;
1677
1.48k
  isl_union_set *dom;
1678
1.48k
  isl_schedule_tree *child;
1679
1.48k
1680
1.48k
  child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1681
1.48k
  dom = isl_schedule_tree_filter_get_filter(child);
1682
1.48k
  space = isl_union_set_get_space(dom);
1683
1.48k
  isl_union_set_free(dom);
1684
1.48k
  isl_schedule_tree_free(child);
1685
1.48k
1686
1.48k
  return space;
1687
1.48k
}
1688
1689
/* Extend the schedule map "outer" with the subtree schedule
1690
 * of a set or sequence node.
1691
 *
1692
 * The schedule for the set or sequence node itself is composed of
1693
 * pieces of the form
1694
 *
1695
 *  filter -> []
1696
 *
1697
 * or
1698
 *
1699
 *  filter -> [index]
1700
 *
1701
 * The first form is used if there is only a single child or
1702
 * if the current node is a set node and the schedule_separate_components
1703
 * option is not set.
1704
 *
1705
 * Each of the pieces above is extended with the subtree schedule of
1706
 * the child of the corresponding filter, if any, padded with zeros
1707
 * to ensure that all pieces have the same range dimension.
1708
 */
1709
static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1710
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1711
1.13k
{
1712
1.13k
  int i, n;
1713
1.13k
  int dim;
1714
1.13k
  int separate;
1715
1.13k
  isl_ctx *ctx;
1716
1.13k
  isl_val *v = NULL;
1717
1.13k
  isl_multi_val *mv;
1718
1.13k
  isl_space *space;
1719
1.13k
  isl_union_map *umap;
1720
1.13k
1721
1.13k
  if (!tree)
1722
0
    return NULL;
1723
1.13k
1724
1.13k
  ctx = isl_schedule_tree_get_ctx(tree);
1725
1.13k
  if (!tree->children)
1726
1.13k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1727
1.13k
      "missing children", return NULL);
1728
1.13k
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1729
1.13k
  if (n == 0)
1730
1.13k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1731
1.13k
      "missing children", return NULL);
1732
1.13k
1733
1.13k
  separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1734
1.13k
          
isl_options_get_schedule_separate_components(ctx)10
);
1735
1.13k
1736
1.13k
  space = extract_space_from_filter_child(tree);
1737
1.13k
1738
1.13k
  umap = isl_union_map_empty(isl_space_copy(space));
1739
1.13k
  space = isl_space_set_from_params(space);
1740
1.13k
  if (separate) {
1741
1.13k
    space = isl_space_add_dims(space, isl_dim_set, 1);
1742
1.13k
    v = isl_val_zero(ctx);
1743
1.13k
  }
1744
1.13k
  mv = isl_multi_val_zero(space);
1745
1.13k
1746
1.13k
  dim = isl_multi_val_dim(mv, isl_dim_set);
1747
6.44k
  for (i = 0; i < n; 
++i5.30k
) {
1748
5.30k
    isl_union_pw_multi_aff *upma;
1749
5.30k
    isl_union_map *umap_i;
1750
5.30k
    isl_union_set *dom;
1751
5.30k
    isl_schedule_tree *child;
1752
5.30k
    int dim_i;
1753
5.30k
    int empty;
1754
5.30k
1755
5.30k
    child = isl_schedule_tree_list_get_schedule_tree(
1756
5.30k
              tree->children, i);
1757
5.30k
    dom = isl_schedule_tree_filter_get_filter(child);
1758
5.30k
1759
5.30k
    if (separate) {
1760
5.30k
      mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1761
5.30k
      v = isl_val_add_ui(v, 1);
1762
5.30k
    }
1763
5.30k
    upma = isl_union_pw_multi_aff_multi_val_on_domain(dom,
1764
5.30k
              isl_multi_val_copy(mv));
1765
5.30k
    umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1766
5.30k
    umap_i = isl_union_map_flat_range_product(
1767
5.30k
              isl_union_map_copy(outer), umap_i);
1768
5.30k
    umap_i = subtree_schedule_extend_child(child, umap_i);
1769
5.30k
    isl_schedule_tree_free(child);
1770
5.30k
1771
5.30k
    empty = isl_union_map_is_empty(umap_i);
1772
5.30k
    if (empty < 0)
1773
0
      umap_i = isl_union_map_free(umap_i);
1774
5.30k
    else if (empty) {
1775
0
      isl_union_map_free(umap_i);
1776
0
      continue;
1777
0
    }
1778
5.30k
1779
5.30k
    dim_i = range_dim(umap_i);
1780
5.30k
    if (dim_i < 0) {
1781
0
      umap = isl_union_map_free(umap);
1782
5.30k
    } else if (dim < dim_i) {
1783
1.46k
      umap = append_range(umap, dim_i - dim);
1784
1.46k
      dim = dim_i;
1785
3.83k
    } else if (dim_i < dim) {
1786
543
      umap_i = append_range(umap_i, dim - dim_i);
1787
543
    }
1788
5.30k
    umap = isl_union_map_union(umap, umap_i);
1789
5.30k
  }
1790
1.13k
1791
1.13k
  isl_val_free(v);
1792
1.13k
  isl_multi_val_free(mv);
1793
1.13k
  isl_union_map_free(outer);
1794
1.13k
1795
1.13k
  return umap;
1796
1.13k
}
1797
1798
/* Extend the schedule map "outer" with the subtree schedule of "tree".
1799
 *
1800
 * If the root of the tree is a set or a sequence, then we extend
1801
 * the schedule map in subtree_schedule_extend_from_children.
1802
 * Otherwise, we extend the schedule map with the partial schedule
1803
 * corresponding to the root of the tree and then continue with
1804
 * the single child of this root.
1805
 * In the special case of an expansion, the schedule map is "extended"
1806
 * by applying the expansion to the domain of the schedule map.
1807
 */
1808
static __isl_give isl_union_map *subtree_schedule_extend(
1809
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1810
4.33k
{
1811
4.33k
  isl_multi_union_pw_aff *mupa;
1812
4.33k
  isl_union_map *umap;
1813
4.33k
  isl_union_set *domain;
1814
4.33k
1815
4.33k
  if (!tree)
1816
0
    return NULL;
1817
4.33k
1818
4.33k
  switch (tree->type) {
1819
4.33k
  case isl_schedule_node_error:
1820
0
    return isl_union_map_free(outer);
1821
4.33k
  case isl_schedule_node_extension:
1822
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1823
0
      "cannot construct subtree schedule of tree "
1824
0
      "with extension nodes",
1825
0
      return isl_union_map_free(outer));
1826
67
  case isl_schedule_node_context:
1827
67
  case isl_schedule_node_guard:
1828
67
  case isl_schedule_node_mark:
1829
67
    return subtree_schedule_extend_child(tree, outer);
1830
3.13k
  case isl_schedule_node_band:
1831
3.13k
    if (isl_schedule_tree_band_n_member(tree) == 0)
1832
0
      return subtree_schedule_extend_child(tree, outer);
1833
3.13k
    mupa = isl_schedule_band_get_partial_schedule(tree->band);
1834
3.13k
    umap = isl_union_map_from_multi_union_pw_aff(mupa);
1835
3.13k
    outer = isl_union_map_flat_range_product(outer, umap);
1836
3.13k
    umap = subtree_schedule_extend_child(tree, outer);
1837
3.13k
    break;
1838
3.13k
  case isl_schedule_node_domain:
1839
0
    domain = isl_schedule_tree_domain_get_domain(tree);
1840
0
    umap = isl_union_map_from_domain(domain);
1841
0
    outer = isl_union_map_flat_range_product(outer, umap);
1842
0
    umap = subtree_schedule_extend_child(tree, outer);
1843
0
    break;
1844
3.13k
  case isl_schedule_node_expansion:
1845
2
    umap = isl_schedule_tree_expansion_get_expansion(tree);
1846
2
    outer = isl_union_map_apply_domain(outer, umap);
1847
2
    umap = subtree_schedule_extend_child(tree, outer);
1848
2
    break;
1849
3.13k
  case isl_schedule_node_filter:
1850
0
    domain = isl_schedule_tree_filter_get_filter(tree);
1851
0
    umap = isl_union_map_from_domain(domain);
1852
0
    outer = isl_union_map_flat_range_product(outer, umap);
1853
0
    umap = subtree_schedule_extend_child(tree, outer);
1854
0
    break;
1855
3.13k
  case isl_schedule_node_leaf:
1856
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1857
0
      "leaf node should be handled by caller", return NULL);
1858
1.13k
  case isl_schedule_node_set:
1859
1.13k
  case isl_schedule_node_sequence:
1860
1.13k
    umap = subtree_schedule_extend_from_children(tree, outer);
1861
1.13k
    break;
1862
4.27k
  }
1863
4.27k
1864
4.27k
  return umap;
1865
4.27k
}
1866
1867
static __isl_give isl_union_set *initial_domain(
1868
  __isl_keep isl_schedule_tree *tree);
1869
1870
/* Extract a universe domain from the children of the tree root "tree",
1871
 * which is a set or sequence, meaning that its children are filters.
1872
 * In particular, return the union of the universes of the filters.
1873
 */
1874
static __isl_give isl_union_set *initial_domain_from_children(
1875
  __isl_keep isl_schedule_tree *tree)
1876
351
{
1877
351
  int i, n;
1878
351
  isl_space *space;
1879
351
  isl_union_set *domain;
1880
351
1881
351
  if (!tree->children)
1882
351
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1883
351
      "missing children", return NULL);
1884
351
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1885
351
  if (n == 0)
1886
351
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1887
351
      "missing children", return NULL);
1888
351
1889
351
  space = extract_space_from_filter_child(tree);
1890
351
  domain = isl_union_set_empty(space);
1891
351
1892
3.04k
  for (i = 0; i < n; 
++i2.69k
) {
1893
2.69k
    isl_schedule_tree *child;
1894
2.69k
    isl_union_set *domain_i;
1895
2.69k
1896
2.69k
    child = isl_schedule_tree_get_child(tree, i);
1897
2.69k
    domain_i = initial_domain(child);
1898
2.69k
    domain = isl_union_set_union(domain, domain_i);
1899
2.69k
    isl_schedule_tree_free(child);
1900
2.69k
  }
1901
351
1902
351
  return domain;
1903
351
}
1904
1905
/* Extract a universe domain from the tree root "tree".
1906
 * The caller is responsible for making sure that this node
1907
 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1908
 * and that it is not a leaf node.
1909
 */
1910
static __isl_give isl_union_set *initial_domain(
1911
  __isl_keep isl_schedule_tree *tree)
1912
4.18k
{
1913
4.18k
  isl_multi_union_pw_aff *mupa;
1914
4.18k
  isl_union_set *domain;
1915
4.18k
  isl_union_map *exp;
1916
4.18k
1917
4.18k
  if (!tree)
1918
0
    return NULL;
1919
4.18k
1920
4.18k
  switch (tree->type) {
1921
4.18k
  case isl_schedule_node_error:
1922
0
    return NULL;
1923
4.18k
  case isl_schedule_node_context:
1924
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1925
0
      "context node should be handled by caller",
1926
0
      return NULL);
1927
0
  case isl_schedule_node_guard:
1928
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1929
0
      "guard node should be handled by caller",
1930
0
      return NULL);
1931
0
  case isl_schedule_node_mark:
1932
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1933
0
      "mark node should be handled by caller",
1934
0
      return NULL);
1935
0
  case isl_schedule_node_extension:
1936
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1937
0
      "cannot construct subtree schedule of tree "
1938
0
      "with extension nodes", return NULL);
1939
1.14k
  case isl_schedule_node_band:
1940
1.14k
    if (isl_schedule_tree_band_n_member(tree) == 0)
1941
1.14k
      
isl_die0
(isl_schedule_tree_get_ctx(tree),
1942
1.14k
        isl_error_internal,
1943
1.14k
        "0D band should be handled by caller",
1944
1.14k
        return NULL);
1945
1.14k
    mupa = isl_schedule_band_get_partial_schedule(tree->band);
1946
1.14k
    domain = isl_multi_union_pw_aff_domain(mupa);
1947
1.14k
    domain = isl_union_set_universe(domain);
1948
1.14k
    break;
1949
1.14k
  case isl_schedule_node_domain:
1950
0
    domain = isl_schedule_tree_domain_get_domain(tree);
1951
0
    domain = isl_union_set_universe(domain);
1952
0
    break;
1953
1.14k
  case isl_schedule_node_expansion:
1954
0
    exp = isl_schedule_tree_expansion_get_expansion(tree);
1955
0
    exp = isl_union_map_universe(exp);
1956
0
    domain = isl_union_map_domain(exp);
1957
0
    break;
1958
2.69k
  case isl_schedule_node_filter:
1959
2.69k
    domain = isl_schedule_tree_filter_get_filter(tree);
1960
2.69k
    domain = isl_union_set_universe(domain);
1961
2.69k
    break;
1962
1.14k
  case isl_schedule_node_leaf:
1963
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1964
0
      "leaf node should be handled by caller", return NULL);
1965
351
  case isl_schedule_node_set:
1966
351
  case isl_schedule_node_sequence:
1967
351
    domain = initial_domain_from_children(tree);
1968
351
    break;
1969
4.18k
  }
1970
4.18k
1971
4.18k
  return domain;
1972
4.18k
}
1973
1974
/* Return the subtree schedule of a node that contains some schedule
1975
 * information, i.e., a node that would not be skipped by
1976
 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1977
 *
1978
 * If the tree contains any expansions, then the returned subtree
1979
 * schedule is formulated in terms of the expanded domains.
1980
 * The tree is not allowed to contain any extension nodes.
1981
 *
1982
 * We start with an initial zero-dimensional subtree schedule based
1983
 * on the domain information in the root node and then extend it
1984
 * based on the schedule information in the root node and its descendants.
1985
 */
1986
__isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
1987
  __isl_keep isl_schedule_tree *tree)
1988
1.49k
{
1989
1.49k
  isl_union_set *domain;
1990
1.49k
  isl_union_map *umap;
1991
1.49k
1992
1.49k
  domain = initial_domain(tree);
1993
1.49k
  umap = isl_union_map_from_domain(domain);
1994
1.49k
  return subtree_schedule_extend(tree, umap);
1995
1.49k
}
1996
1997
/* Multiply the partial schedule of the band root node of "tree"
1998
 * with the factors in "mv".
1999
 */
2000
__isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
2001
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2002
0
{
2003
0
  if (!tree || !mv)
2004
0
    goto error;
2005
0
  if (tree->type != isl_schedule_node_band)
2006
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2007
0
      "not a band node", goto error);
2008
0
2009
0
  tree = isl_schedule_tree_cow(tree);
2010
0
  if (!tree)
2011
0
    goto error;
2012
0
2013
0
  tree->band = isl_schedule_band_scale(tree->band, mv);
2014
0
  if (!tree->band)
2015
0
    return isl_schedule_tree_free(tree);
2016
0
2017
0
  return tree;
2018
0
error:
2019
0
  isl_schedule_tree_free(tree);
2020
0
  isl_multi_val_free(mv);
2021
0
  return NULL;
2022
0
}
2023
2024
/* Divide the partial schedule of the band root node of "tree"
2025
 * by the factors in "mv".
2026
 */
2027
__isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
2028
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2029
0
{
2030
0
  if (!tree || !mv)
2031
0
    goto error;
2032
0
  if (tree->type != isl_schedule_node_band)
2033
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2034
0
      "not a band node", goto error);
2035
0
2036
0
  tree = isl_schedule_tree_cow(tree);
2037
0
  if (!tree)
2038
0
    goto error;
2039
0
2040
0
  tree->band = isl_schedule_band_scale_down(tree->band, mv);
2041
0
  if (!tree->band)
2042
0
    return isl_schedule_tree_free(tree);
2043
0
2044
0
  return tree;
2045
0
error:
2046
0
  isl_schedule_tree_free(tree);
2047
0
  isl_multi_val_free(mv);
2048
0
  return NULL;
2049
0
}
2050
2051
/* Reduce the partial schedule of the band root node of "tree"
2052
 * modulo the factors in "mv".
2053
 */
2054
__isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
2055
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2056
0
{
2057
0
  if (!tree || !mv)
2058
0
    goto error;
2059
0
  if (tree->type != isl_schedule_node_band)
2060
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2061
0
      "not a band node", goto error);
2062
0
2063
0
  tree = isl_schedule_tree_cow(tree);
2064
0
  if (!tree)
2065
0
    goto error;
2066
0
2067
0
  tree->band = isl_schedule_band_mod(tree->band, mv);
2068
0
  if (!tree->band)
2069
0
    return isl_schedule_tree_free(tree);
2070
0
2071
0
  return tree;
2072
0
error:
2073
0
  isl_schedule_tree_free(tree);
2074
0
  isl_multi_val_free(mv);
2075
0
  return NULL;
2076
0
}
2077
2078
/* Shift the partial schedule of the band root node of "tree" by "shift".
2079
 */
2080
__isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
2081
  __isl_take isl_schedule_tree *tree,
2082
  __isl_take isl_multi_union_pw_aff *shift)
2083
0
{
2084
0
  if (!tree || !shift)
2085
0
    goto error;
2086
0
  if (tree->type != isl_schedule_node_band)
2087
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2088
0
      "not a band node", goto error);
2089
0
2090
0
  tree = isl_schedule_tree_cow(tree);
2091
0
  if (!tree)
2092
0
    goto error;
2093
0
2094
0
  tree->band = isl_schedule_band_shift(tree->band, shift);
2095
0
  if (!tree->band)
2096
0
    return isl_schedule_tree_free(tree);
2097
0
2098
0
  return tree;
2099
0
error:
2100
0
  isl_schedule_tree_free(tree);
2101
0
  isl_multi_union_pw_aff_free(shift);
2102
0
  return NULL;
2103
0
}
2104
2105
/* Given two trees with sequence roots, replace the child at position
2106
 * "pos" of "tree" with the children of "child".
2107
 */
2108
__isl_give isl_schedule_tree *isl_schedule_tree_sequence_splice(
2109
  __isl_take isl_schedule_tree *tree, int pos,
2110
  __isl_take isl_schedule_tree *child)
2111
0
{
2112
0
  int n;
2113
0
  isl_schedule_tree_list *list1, *list2;
2114
0
2115
0
  tree = isl_schedule_tree_cow(tree);
2116
0
  if (!tree || !child)
2117
0
    goto error;
2118
0
  if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2119
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2120
0
      "not a sequence node", goto error);
2121
0
  n = isl_schedule_tree_n_children(tree);
2122
0
  if (pos < 0 || pos >= n)
2123
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2124
0
      "position out of bounds", goto error);
2125
0
  if (isl_schedule_tree_get_type(child) != isl_schedule_node_sequence)
2126
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2127
0
      "not a sequence node", goto error);
2128
0
2129
0
  list1 = isl_schedule_tree_list_copy(tree->children);
2130
0
  list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2131
0
  list2 = isl_schedule_tree_list_copy(tree->children);
2132
0
  list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2133
0
  list1 = isl_schedule_tree_list_concat(list1,
2134
0
        isl_schedule_tree_list_copy(child->children));
2135
0
  list1 = isl_schedule_tree_list_concat(list1, list2);
2136
0
2137
0
  isl_schedule_tree_free(tree);
2138
0
  isl_schedule_tree_free(child);
2139
0
  return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2140
0
            list1);
2141
0
error:
2142
0
  isl_schedule_tree_free(tree);
2143
0
  isl_schedule_tree_free(child);
2144
0
  return NULL;
2145
0
}
2146
2147
/* Tile the band root node of "tree" with tile sizes "sizes".
2148
 *
2149
 * We duplicate the band node, change the schedule of one of them
2150
 * to the tile schedule and the other to the point schedule and then
2151
 * attach the point band as a child to the tile band.
2152
 */
2153
__isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
2154
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
2155
78
{
2156
78
  isl_schedule_tree *child = NULL;
2157
78
2158
78
  if (!tree || !sizes)
2159
0
    goto error;
2160
78
  if (tree->type != isl_schedule_node_band)
2161
78
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2162
78
      "not a band node", goto error);
2163
78
2164
78
  child = isl_schedule_tree_copy(tree);
2165
78
  tree = isl_schedule_tree_cow(tree);
2166
78
  child = isl_schedule_tree_cow(child);
2167
78
  if (!tree || !child)
2168
0
    goto error;
2169
78
2170
78
  tree->band = isl_schedule_band_tile(tree->band,
2171
78
              isl_multi_val_copy(sizes));
2172
78
  if (!tree->band)
2173
0
    goto error;
2174
78
  child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2175
78
  if (!child->band)
2176
0
    child = isl_schedule_tree_free(child);
2177
78
2178
78
  tree = isl_schedule_tree_replace_child(tree, 0, child);
2179
78
2180
78
  return tree;
2181
0
error:
2182
0
  isl_schedule_tree_free(child);
2183
0
  isl_schedule_tree_free(tree);
2184
0
  isl_multi_val_free(sizes);
2185
0
  return NULL;
2186
78
}
2187
2188
/* Given an isolate AST generation option "isolate" for a band of size pos + n,
2189
 * return the corresponding option for a band covering the first "pos"
2190
 * members.
2191
 *
2192
 * The input isolate option is of the form
2193
 *
2194
 *  isolate[[flattened outer bands] -> [pos; n]]
2195
 *
2196
 * The output isolate option is of the form
2197
 *
2198
 *  isolate[[flattened outer bands] -> [pos]]
2199
 */
2200
static __isl_give isl_set *isolate_initial(__isl_keep isl_set *isolate,
2201
  int pos, int n)
2202
34
{
2203
34
  isl_id *id;
2204
34
  isl_map *map;
2205
34
2206
34
  isolate = isl_set_copy(isolate);
2207
34
  id = isl_set_get_tuple_id(isolate);
2208
34
  map = isl_set_unwrap(isolate);
2209
34
  map = isl_map_project_out(map, isl_dim_out, pos, n);
2210
34
  isolate = isl_map_wrap(map);
2211
34
  isolate = isl_set_set_tuple_id(isolate, id);
2212
34
2213
34
  return isolate;
2214
34
}
2215
2216
/* Given an isolate AST generation option "isolate" for a band of size pos + n,
2217
 * return the corresponding option for a band covering the final "n"
2218
 * members within a band covering the first "pos" members.
2219
 *
2220
 * The input isolate option is of the form
2221
 *
2222
 *  isolate[[flattened outer bands] -> [pos; n]]
2223
 *
2224
 * The output isolate option is of the form
2225
 *
2226
 *  isolate[[flattened outer bands; pos] -> [n]]
2227
 *
2228
 *
2229
 * The range is first split into
2230
 *
2231
 *  isolate[[flattened outer bands] -> [[pos] -> [n]]]
2232
 *
2233
 * and then the first pos members are moved to the domain
2234
 *
2235
 *  isolate[[[flattened outer bands] -> [pos]] -> [n]]
2236
 *
2237
 * after which the domain is flattened to obtain the desired output.
2238
 */
2239
static __isl_give isl_set *isolate_final(__isl_keep isl_set *isolate,
2240
  int pos, int n)
2241
34
{
2242
34
  isl_id *id;
2243
34
  isl_space *space;
2244
34
  isl_multi_aff *ma1, *ma2;
2245
34
  isl_map *map;
2246
34
2247
34
  isolate = isl_set_copy(isolate);
2248
34
  id = isl_set_get_tuple_id(isolate);
2249
34
  map = isl_set_unwrap(isolate);
2250
34
  space = isl_space_range(isl_map_get_space(map));
2251
34
  ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
2252
34
               isl_dim_set, pos, n);
2253
34
  ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
2254
34
  ma1 = isl_multi_aff_range_product(ma1, ma2);
2255
34
  map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1));
2256
34
  map = isl_map_uncurry(map);
2257
34
  map = isl_map_flatten_domain(map);
2258
34
  isolate = isl_map_wrap(map);
2259
34
  isolate = isl_set_set_tuple_id(isolate, id);
2260
34
2261
34
  return isolate;
2262
34
}
2263
2264
/* Split the band root node of "tree" into two nested band nodes,
2265
 * one with the first "pos" dimensions and
2266
 * one with the remaining dimensions.
2267
 * The tree is itself positioned at schedule depth "depth".
2268
 *
2269
 * The loop AST generation type options and the isolate option
2270
 * are split over the two band nodes.
2271
 */
2272
__isl_give isl_schedule_tree *isl_schedule_tree_band_split(
2273
  __isl_take isl_schedule_tree *tree, int pos, int depth)
2274
34
{
2275
34
  int n;
2276
34
  isl_set *isolate, *tree_isolate, *child_isolate;
2277
34
  isl_schedule_tree *child;
2278
34
2279
34
  if (!tree)
2280
0
    return NULL;
2281
34
  if (tree->type != isl_schedule_node_band)
2282
34
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2283
34
      "not a band node", return isl_schedule_tree_free(tree));
2284
34
2285
34
  n = isl_schedule_tree_band_n_member(tree);
2286
34
  if (pos < 0 || pos > n)
2287
34
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2288
34
      "position out of bounds",
2289
34
      return isl_schedule_tree_free(tree));
2290
34
2291
34
  child = isl_schedule_tree_copy(tree);
2292
34
  tree = isl_schedule_tree_cow(tree);
2293
34
  child = isl_schedule_tree_cow(child);
2294
34
  if (!tree || !child)
2295
0
    goto error;
2296
34
2297
34
  isolate = isl_schedule_tree_band_get_ast_isolate_option(tree, depth);
2298
34
  tree_isolate = isolate_initial(isolate, pos, n - pos);
2299
34
  child_isolate = isolate_final(isolate, pos, n - pos);
2300
34
  child->band = isl_schedule_band_drop(child->band, 0, pos);
2301
34
  child->band = isl_schedule_band_replace_ast_build_option(child->band,
2302
34
          isl_set_copy(isolate), child_isolate);
2303
34
  tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2304
34
  tree->band = isl_schedule_band_replace_ast_build_option(tree->band,
2305
34
          isl_set_copy(isolate), tree_isolate);
2306
34
  isl_set_free(isolate);
2307
34
  if (!child->band || !tree->band)
2308
0
    goto error;
2309
34
2310
34
  tree = isl_schedule_tree_replace_child(tree, 0, child);
2311
34
2312
34
  return tree;
2313
0
error:
2314
0
  isl_schedule_tree_free(child);
2315
0
  isl_schedule_tree_free(tree);
2316
0
  return NULL;
2317
34
}
2318
2319
/* Attach "tree2" at each of the leaves of "tree1".
2320
 *
2321
 * If "tree1" does not have any explicit children, then make "tree2"
2322
 * its single child.  Otherwise, attach "tree2" to the leaves of
2323
 * each of the children of "tree1".
2324
 */
2325
__isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
2326
  __isl_take isl_schedule_tree *tree1,
2327
  __isl_take isl_schedule_tree *tree2)
2328
7
{
2329
7
  int i, n;
2330
7
2331
7
  if (!tree1 || !tree2)
2332
0
    goto error;
2333
7
  n = isl_schedule_tree_n_children(tree1);
2334
7
  if (n == 0) {
2335
7
    isl_schedule_tree_list *list;
2336
7
    list = isl_schedule_tree_list_from_schedule_tree(tree2);
2337
7
    tree1 = isl_schedule_tree_set_children(tree1, list);
2338
7
    return tree1;
2339
7
  }
2340
0
  for (i = 0; i < n; ++i) {
2341
0
    isl_schedule_tree *child;
2342
0
2343
0
    child = isl_schedule_tree_get_child(tree1, i);
2344
0
    child = isl_schedule_tree_append_to_leaves(child,
2345
0
          isl_schedule_tree_copy(tree2));
2346
0
    tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2347
0
  }
2348
0
2349
0
  isl_schedule_tree_free(tree2);
2350
0
  return tree1;
2351
0
error:
2352
0
  isl_schedule_tree_free(tree1);
2353
0
  isl_schedule_tree_free(tree2);
2354
0
  return NULL;
2355
0
}
2356
2357
/* Reset the user pointer on all identifiers of parameters and tuples
2358
 * in the root of "tree".
2359
 */
2360
__isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
2361
  __isl_take isl_schedule_tree *tree)
2362
0
{
2363
0
  if (isl_schedule_tree_is_leaf(tree))
2364
0
    return tree;
2365
0
2366
0
  tree = isl_schedule_tree_cow(tree);
2367
0
  if (!tree)
2368
0
    return NULL;
2369
0
2370
0
  switch (tree->type) {
2371
0
  case isl_schedule_node_error:
2372
0
    return isl_schedule_tree_free(tree);
2373
0
  case isl_schedule_node_band:
2374
0
    tree->band = isl_schedule_band_reset_user(tree->band);
2375
0
    if (!tree->band)
2376
0
      return isl_schedule_tree_free(tree);
2377
0
    break;
2378
0
  case isl_schedule_node_context:
2379
0
    tree->context = isl_set_reset_user(tree->context);
2380
0
    if (!tree->context)
2381
0
      return isl_schedule_tree_free(tree);
2382
0
    break;
2383
0
  case isl_schedule_node_domain:
2384
0
    tree->domain = isl_union_set_reset_user(tree->domain);
2385
0
    if (!tree->domain)
2386
0
      return isl_schedule_tree_free(tree);
2387
0
    break;
2388
0
  case isl_schedule_node_expansion:
2389
0
    tree->contraction =
2390
0
      isl_union_pw_multi_aff_reset_user(tree->contraction);
2391
0
    tree->expansion = isl_union_map_reset_user(tree->expansion);
2392
0
    if (!tree->contraction || !tree->expansion)
2393
0
      return isl_schedule_tree_free(tree);
2394
0
    break;
2395
0
  case isl_schedule_node_extension:
2396
0
    tree->extension = isl_union_map_reset_user(tree->extension);
2397
0
    if (!tree->extension)
2398
0
      return isl_schedule_tree_free(tree);
2399
0
    break;
2400
0
  case isl_schedule_node_filter:
2401
0
    tree->filter = isl_union_set_reset_user(tree->filter);
2402
0
    if (!tree->filter)
2403
0
      return isl_schedule_tree_free(tree);
2404
0
    break;
2405
0
  case isl_schedule_node_guard:
2406
0
    tree->guard = isl_set_reset_user(tree->guard);
2407
0
    if (!tree->guard)
2408
0
      return isl_schedule_tree_free(tree);
2409
0
    break;
2410
0
  case isl_schedule_node_leaf:
2411
0
  case isl_schedule_node_mark:
2412
0
  case isl_schedule_node_sequence:
2413
0
  case isl_schedule_node_set:
2414
0
    break;
2415
0
  }
2416
0
2417
0
  return tree;
2418
0
}
2419
2420
/* Align the parameters of the root of "tree" to those of "space".
2421
 */
2422
__isl_give isl_schedule_tree *isl_schedule_tree_align_params(
2423
  __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
2424
0
{
2425
0
  if (!space)
2426
0
    goto error;
2427
0
2428
0
  if (isl_schedule_tree_is_leaf(tree)) {
2429
0
    isl_space_free(space);
2430
0
    return tree;
2431
0
  }
2432
0
2433
0
  tree = isl_schedule_tree_cow(tree);
2434
0
  if (!tree)
2435
0
    goto error;
2436
0
2437
0
  switch (tree->type) {
2438
0
  case isl_schedule_node_error:
2439
0
    goto error;
2440
0
  case isl_schedule_node_band:
2441
0
    tree->band = isl_schedule_band_align_params(tree->band, space);
2442
0
    if (!tree->band)
2443
0
      return isl_schedule_tree_free(tree);
2444
0
    break;
2445
0
  case isl_schedule_node_context:
2446
0
    tree->context = isl_set_align_params(tree->context, space);
2447
0
    if (!tree->context)
2448
0
      return isl_schedule_tree_free(tree);
2449
0
    break;
2450
0
  case isl_schedule_node_domain:
2451
0
    tree->domain = isl_union_set_align_params(tree->domain, space);
2452
0
    if (!tree->domain)
2453
0
      return isl_schedule_tree_free(tree);
2454
0
    break;
2455
0
  case isl_schedule_node_expansion:
2456
0
    tree->contraction =
2457
0
      isl_union_pw_multi_aff_align_params(tree->contraction,
2458
0
              isl_space_copy(space));
2459
0
    tree->expansion = isl_union_map_align_params(tree->expansion,
2460
0
                space);
2461
0
    if (!tree->contraction || !tree->expansion)
2462
0
      return isl_schedule_tree_free(tree);
2463
0
    break;
2464
0
  case isl_schedule_node_extension:
2465
0
    tree->extension = isl_union_map_align_params(tree->extension,
2466
0
                space);
2467
0
    if (!tree->extension)
2468
0
      return isl_schedule_tree_free(tree);
2469
0
    break;
2470
0
  case isl_schedule_node_filter:
2471
0
    tree->filter = isl_union_set_align_params(tree->filter, space);
2472
0
    if (!tree->filter)
2473
0
      return isl_schedule_tree_free(tree);
2474
0
    break;
2475
0
  case isl_schedule_node_guard:
2476
0
    tree->guard = isl_set_align_params(tree->guard, space);
2477
0
    if (!tree->guard)
2478
0
      return isl_schedule_tree_free(tree);
2479
0
    break;
2480
0
  case isl_schedule_node_leaf:
2481
0
  case isl_schedule_node_mark:
2482
0
  case isl_schedule_node_sequence:
2483
0
  case isl_schedule_node_set:
2484
0
    isl_space_free(space);
2485
0
    break;
2486
0
  }
2487
0
2488
0
  return tree;
2489
0
error:
2490
0
  isl_space_free(space);
2491
0
  isl_schedule_tree_free(tree);
2492
0
  return NULL;
2493
0
}
2494
2495
/* Does "tree" involve the iteration domain?
2496
 * That is, does it need to be modified
2497
 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2498
 */
2499
static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
2500
1.07k
{
2501
1.07k
  if (!tree)
2502
0
    return -1;
2503
1.07k
2504
1.07k
  switch (tree->type) {
2505
1.07k
  case isl_schedule_node_error:
2506
0
    return -1;
2507
1.07k
  case isl_schedule_node_band:
2508
695
  case isl_schedule_node_domain:
2509
695
  case isl_schedule_node_expansion:
2510
695
  case isl_schedule_node_extension:
2511
695
  case isl_schedule_node_filter:
2512
695
    return 1;
2513
695
  case isl_schedule_node_context:
2514
375
  case isl_schedule_node_leaf:
2515
375
  case isl_schedule_node_guard:
2516
375
  case isl_schedule_node_mark:
2517
375
  case isl_schedule_node_sequence:
2518
375
  case isl_schedule_node_set:
2519
375
    return 0;
2520
0
  }
2521
0
2522
0
  isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2523
0
    "unhandled case", return -1);
2524
0
}
2525
2526
/* Compute the pullback of the root node of "tree" by the function
2527
 * represented by "upma".
2528
 * In other words, plug in "upma" in the iteration domains of
2529
 * the root node of "tree".
2530
 * We currently do not handle expansion nodes.
2531
 *
2532
 * We first check if the root node involves any iteration domains.
2533
 * If so, we handle the specific cases.
2534
 */
2535
__isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
2536
  __isl_take isl_schedule_tree *tree,
2537
  __isl_take isl_union_pw_multi_aff *upma)
2538
1.07k
{
2539
1.07k
  int involves;
2540
1.07k
2541
1.07k
  if (!tree || !upma)
2542
0
    goto error;
2543
1.07k
2544
1.07k
  involves = involves_iteration_domain(tree);
2545
1.07k
  if (involves < 0)
2546
0
    goto error;
2547
1.07k
  if (!involves) {
2548
375
    isl_union_pw_multi_aff_free(upma);
2549
375
    return tree;
2550
375
  }
2551
695
2552
695
  tree = isl_schedule_tree_cow(tree);
2553
695
  if (!tree)
2554
0
    goto error;
2555
695
2556
695
  if (tree->type == isl_schedule_node_band) {
2557
320
    tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
2558
320
                  tree->band, upma);
2559
320
    if (!tree->band)
2560
0
      return isl_schedule_tree_free(tree);
2561
375
  } else if (tree->type == isl_schedule_node_domain) {
2562
147
    tree->domain =
2563
147
      isl_union_set_preimage_union_pw_multi_aff(tree->domain,
2564
147
                  upma);
2565
147
    if (!tree->domain)
2566
0
      return isl_schedule_tree_free(tree);
2567
228
  } else if (tree->type == isl_schedule_node_expansion) {
2568
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
2569
0
      "cannot pullback expansion node", goto error);
2570
228
  } else if (tree->type == isl_schedule_node_extension) {
2571
0
    tree->extension =
2572
0
      isl_union_map_preimage_range_union_pw_multi_aff(
2573
0
          tree->extension, upma);
2574
0
    if (!tree->extension)
2575
0
      return isl_schedule_tree_free(tree);
2576
228
  } else if (tree->type == isl_schedule_node_filter) {
2577
228
    tree->filter =
2578
228
      isl_union_set_preimage_union_pw_multi_aff(tree->filter,
2579
228
                  upma);
2580
228
    if (!tree->filter)
2581
0
      return isl_schedule_tree_free(tree);
2582
695
  }
2583
695
2584
695
  return tree;
2585
0
error:
2586
0
  isl_union_pw_multi_aff_free(upma);
2587
0
  isl_schedule_tree_free(tree);
2588
0
  return NULL;
2589
695
}
2590
2591
/* Compute the gist of the band tree root with respect to "context".
2592
 */
2593
__isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
2594
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
2595
291
{
2596
291
  if (!tree)
2597
0
    return NULL;
2598
291
  if (tree->type != isl_schedule_node_band)
2599
291
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2600
291
      "not a band node", goto error);
2601
291
  tree = isl_schedule_tree_cow(tree);
2602
291
  if (!tree)
2603
0
    goto error;
2604
291
2605
291
  tree->band = isl_schedule_band_gist(tree->band, context);
2606
291
  if (!tree->band)
2607
0
    return isl_schedule_tree_free(tree);
2608
291
  return tree;
2609
0
error:
2610
0
  isl_union_set_free(context);
2611
0
  isl_schedule_tree_free(tree);
2612
0
  return NULL;
2613
291
}
2614
2615
/* Are any members in "band" marked coincident?
2616
 */
2617
static int any_coincident(__isl_keep isl_schedule_band *band)
2618
0
{
2619
0
  int i, n;
2620
0
2621
0
  n = isl_schedule_band_n_member(band);
2622
0
  for (i = 0; i < n; ++i)
2623
0
    if (isl_schedule_band_member_get_coincident(band, i))
2624
0
      return 1;
2625
0
2626
0
  return 0;
2627
0
}
2628
2629
/* Print the band node "band" to "p".
2630
 *
2631
 * The permutable and coincident properties are only printed if they
2632
 * are different from the defaults.
2633
 * The coincident property is always printed in YAML flow style.
2634
 */
2635
static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
2636
  __isl_keep isl_schedule_band *band)
2637
0
{
2638
0
  isl_union_set *options;
2639
0
  int empty;
2640
0
2641
0
  p = isl_printer_print_str(p, "schedule");
2642
0
  p = isl_printer_yaml_next(p);
2643
0
  p = isl_printer_print_str(p, "\"");
2644
0
  p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2645
0
  p = isl_printer_print_str(p, "\"");
2646
0
  if (isl_schedule_band_get_permutable(band)) {
2647
0
    p = isl_printer_yaml_next(p);
2648
0
    p = isl_printer_print_str(p, "permutable");
2649
0
    p = isl_printer_yaml_next(p);
2650
0
    p = isl_printer_print_int(p, 1);
2651
0
  }
2652
0
  if (any_coincident(band)) {
2653
0
    int i, n;
2654
0
    int style;
2655
0
2656
0
    p = isl_printer_yaml_next(p);
2657
0
    p = isl_printer_print_str(p, "coincident");
2658
0
    p = isl_printer_yaml_next(p);
2659
0
    style = isl_printer_get_yaml_style(p);
2660
0
    p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
2661
0
    p = isl_printer_yaml_start_sequence(p);
2662
0
    n = isl_schedule_band_n_member(band);
2663
0
    for (i = 0; i < n; ++i) {
2664
0
      p = isl_printer_print_int(p,
2665
0
          isl_schedule_band_member_get_coincident(band, i));
2666
0
      p = isl_printer_yaml_next(p);
2667
0
    }
2668
0
    p = isl_printer_yaml_end_sequence(p);
2669
0
    p = isl_printer_set_yaml_style(p, style);
2670
0
  }
2671
0
  options = isl_schedule_band_get_ast_build_options(band);
2672
0
  empty = isl_union_set_is_empty(options);
2673
0
  if (empty < 0)
2674
0
    p = isl_printer_free(p);
2675
0
  if (!empty) {
2676
0
    p = isl_printer_yaml_next(p);
2677
0
    p = isl_printer_print_str(p, "options");
2678
0
    p = isl_printer_yaml_next(p);
2679
0
    p = isl_printer_print_str(p, "\"");
2680
0
    p = isl_printer_print_union_set(p, options);
2681
0
    p = isl_printer_print_str(p, "\"");
2682
0
  }
2683
0
  isl_union_set_free(options);
2684
0
2685
0
  return p;
2686
0
}
2687
2688
/* Print "tree" to "p".
2689
 *
2690
 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2691
 * positions of a descendant of the current node that should be marked
2692
 * (by the comment "YOU ARE HERE").  In particular, if "n_ancestor"
2693
 * is zero, then the current node should be marked.
2694
 * The marking is only printed in YAML block format.
2695
 *
2696
 * Implicit leaf nodes are not printed, except if they correspond
2697
 * to the node that should be marked.
2698
 */
2699
__isl_give isl_printer *isl_printer_print_schedule_tree_mark(
2700
  __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
2701
  int n_ancestor, int *child_pos)
2702
0
{
2703
0
  int i, n;
2704
0
  int sequence = 0;
2705
0
  int block;
2706
0
2707
0
  block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
2708
0
2709
0
  p = isl_printer_yaml_start_mapping(p);
2710
0
  if (n_ancestor == 0 && block) {
2711
0
    p = isl_printer_print_str(p, "# YOU ARE HERE");
2712
0
    p = isl_printer_end_line(p);
2713
0
    p = isl_printer_start_line(p);
2714
0
  }
2715
0
  switch (tree->type) {
2716
0
  case isl_schedule_node_error:
2717
0
    p = isl_printer_print_str(p, "ERROR");
2718
0
    break;
2719
0
  case isl_schedule_node_leaf:
2720
0
    p = isl_printer_print_str(p, "leaf");
2721
0
    break;
2722
0
  case isl_schedule_node_sequence:
2723
0
    p = isl_printer_print_str(p, "sequence");
2724
0
    sequence = 1;
2725
0
    break;
2726
0
  case isl_schedule_node_set:
2727
0
    p = isl_printer_print_str(p, "set");
2728
0
    sequence = 1;
2729
0
    break;
2730
0
  case isl_schedule_node_context:
2731
0
    p = isl_printer_print_str(p, "context");
2732
0
    p = isl_printer_yaml_next(p);
2733
0
    p = isl_printer_print_str(p, "\"");
2734
0
    p = isl_printer_print_set(p, tree->context);
2735
0
    p = isl_printer_print_str(p, "\"");
2736
0
    break;
2737
0
  case isl_schedule_node_domain:
2738
0
    p = isl_printer_print_str(p, "domain");
2739
0
    p = isl_printer_yaml_next(p);
2740
0
    p = isl_printer_print_str(p, "\"");
2741
0
    p = isl_printer_print_union_set(p, tree->domain);
2742
0
    p = isl_printer_print_str(p, "\"");
2743
0
    break;
2744
0
  case isl_schedule_node_expansion:
2745
0
    p = isl_printer_print_str(p, "contraction");
2746
0
    p = isl_printer_yaml_next(p);
2747
0
    p = isl_printer_print_str(p, "\"");
2748
0
    p = isl_printer_print_union_pw_multi_aff(p, tree->contraction);
2749
0
    p = isl_printer_print_str(p, "\"");
2750
0
    p = isl_printer_yaml_next(p);
2751
0
    p = isl_printer_print_str(p, "expansion");
2752
0
    p = isl_printer_yaml_next(p);
2753
0
    p = isl_printer_print_str(p, "\"");
2754
0
    p = isl_printer_print_union_map(p, tree->expansion);
2755
0
    p = isl_printer_print_str(p, "\"");
2756
0
    break;
2757
0
  case isl_schedule_node_extension:
2758
0
    p = isl_printer_print_str(p, "extension");
2759
0
    p = isl_printer_yaml_next(p);
2760
0
    p = isl_printer_print_str(p, "\"");
2761
0
    p = isl_printer_print_union_map(p, tree->extension);
2762
0
    p = isl_printer_print_str(p, "\"");
2763
0
    break;
2764
0
  case isl_schedule_node_filter:
2765
0
    p = isl_printer_print_str(p, "filter");
2766
0
    p = isl_printer_yaml_next(p);
2767
0
    p = isl_printer_print_str(p, "\"");
2768
0
    p = isl_printer_print_union_set(p, tree->filter);
2769
0
    p = isl_printer_print_str(p, "\"");
2770
0
    break;
2771
0
  case isl_schedule_node_guard:
2772
0
    p = isl_printer_print_str(p, "guard");
2773
0
    p = isl_printer_yaml_next(p);
2774
0
    p = isl_printer_print_str(p, "\"");
2775
0
    p = isl_printer_print_set(p, tree->guard);
2776
0
    p = isl_printer_print_str(p, "\"");
2777
0
    break;
2778
0
  case isl_schedule_node_mark:
2779
0
    p = isl_printer_print_str(p, "mark");
2780
0
    p = isl_printer_yaml_next(p);
2781
0
    p = isl_printer_print_str(p, "\"");
2782
0
    p = isl_printer_print_str(p, isl_id_get_name(tree->mark));
2783
0
    p = isl_printer_print_str(p, "\"");
2784
0
    break;
2785
0
  case isl_schedule_node_band:
2786
0
    p = print_tree_band(p, tree->band);
2787
0
    break;
2788
0
  }
2789
0
  p = isl_printer_yaml_next(p);
2790
0
2791
0
  if (!tree->children) {
2792
0
    if (n_ancestor > 0 && block) {
2793
0
      isl_schedule_tree *leaf;
2794
0
2795
0
      p = isl_printer_print_str(p, "child");
2796
0
      p = isl_printer_yaml_next(p);
2797
0
      leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2798
0
      p = isl_printer_print_schedule_tree_mark(p,
2799
0
          leaf, 0, NULL);
2800
0
      isl_schedule_tree_free(leaf);
2801
0
      p = isl_printer_yaml_next(p);
2802
0
    }
2803
0
    return isl_printer_yaml_end_mapping(p);
2804
0
  }
2805
0
2806
0
  if (sequence) {
2807
0
    p = isl_printer_yaml_start_sequence(p);
2808
0
  } else {
2809
0
    p = isl_printer_print_str(p, "child");
2810
0
    p = isl_printer_yaml_next(p);
2811
0
  }
2812
0
2813
0
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
2814
0
  for (i = 0; i < n; ++i) {
2815
0
    isl_schedule_tree *t;
2816
0
2817
0
    t = isl_schedule_tree_get_child(tree, i);
2818
0
    if (n_ancestor > 0 && child_pos[0] == i)
2819
0
      p = isl_printer_print_schedule_tree_mark(p, t,
2820
0
            n_ancestor - 1, child_pos + 1);
2821
0
    else
2822
0
      p = isl_printer_print_schedule_tree_mark(p, t,
2823
0
            -1, NULL);
2824
0
    isl_schedule_tree_free(t);
2825
0
2826
0
    p = isl_printer_yaml_next(p);
2827
0
  }
2828
0
2829
0
  if (sequence)
2830
0
    p = isl_printer_yaml_end_sequence(p);
2831
0
  p = isl_printer_yaml_end_mapping(p);
2832
0
2833
0
  return p;
2834
0
}
2835
2836
/* Print "tree" to "p".
2837
 */
2838
__isl_give isl_printer *isl_printer_print_schedule_tree(
2839
  __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2840
0
{
2841
0
  return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2842
0
}
2843
2844
void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2845
0
{
2846
0
  isl_ctx *ctx;
2847
0
  isl_printer *printer;
2848
0
2849
0
  if (!tree)
2850
0
    return;
2851
0
2852
0
  ctx = isl_schedule_tree_get_ctx(tree);
2853
0
  printer = isl_printer_to_file(ctx, stderr);
2854
0
  printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2855
0
  printer = isl_printer_print_schedule_tree(printer, tree);
2856
0
2857
0
  isl_printer_free(printer);
2858
0
}