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

source code of polly/lib/External/isl/isl_schedule_tree.c