Coverage Report

Created: 2018-04-23 18:20

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