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	*/
35	int 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	*/
47	static __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;
251	error:
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;
278	error:
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;
302	error:
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;
329	error:
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;
358	error:
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;
382	error:
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;
409	error:
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;
434	error:
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	*/
442	isl_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	*/
453	int 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;
540	error:
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);
579	error:
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	*/
612	isl_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	*/
620	enum 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	*/
628	isl_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	*/
710	int 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	*/
722	isl_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;
846	error:
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;
864	error:
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;
979	error:
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	*/
1011	isl_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	*/
1026	isl_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	*/
1066	isl_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;
1134	error:
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;
1172	error:
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	*/
1181	enum 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	*/
1220	enum 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 *
1238	isl_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;
1299	error:
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;
1368	error:
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 *
1408	isl_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;
1427	error:
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;
1465	error:
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;
1503	error:
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	*/
1541	static 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	*/
1557	static 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	*/
1577	static __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	*/
1612	static 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
1663	static __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	*/
1674	static __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	*/
1695	static __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	*/
1731	static __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	*/
1832	static __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
1895	static __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	*/
1902	static __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	*/
1938	static __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;
2050	error:
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;
2077	error:
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;
2104	error:
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;
2131	error:
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);
2175	error:
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;
2215	error:
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	*/
2234	static __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	*/
2273	static __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;
2349	error:
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;
2388	error:
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;
2526	error:
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	*/
2536	static 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;
2622	error:
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;
2646	error:
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	*/
2654	static 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	*/
2679	static __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
2892	void 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