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 */
isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree * tree)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 */
isl_schedule_tree_alloc(isl_ctx * ctx,enum isl_schedule_node_type type)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 */
isl_schedule_tree_dup(__isl_keep isl_schedule_tree * tree)70 __isl_take 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, 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(tree->band);
91 if (!dup->band)
92 return isl_schedule_tree_free(dup);
93 break;
94 case isl_schedule_node_context:
95 dup->context = isl_set_copy(tree->context);
96 if (!dup->context)
97 return isl_schedule_tree_free(dup);
98 break;
99 case isl_schedule_node_domain:
100 dup->domain = isl_union_set_copy(tree->domain);
101 if (!dup->domain)
102 return isl_schedule_tree_free(dup);
103 break;
104 case isl_schedule_node_expansion:
105 dup->contraction =
106 isl_union_pw_multi_aff_copy(tree->contraction);
107 dup->expansion = isl_union_map_copy(tree->expansion);
108 if (!dup->contraction || !dup->expansion)
109 return isl_schedule_tree_free(dup);
110 break;
111 case isl_schedule_node_extension:
112 dup->extension = isl_union_map_copy(tree->extension);
113 if (!dup->extension)
114 return isl_schedule_tree_free(dup);
115 break;
116 case isl_schedule_node_filter:
117 dup->filter = isl_union_set_copy(tree->filter);
118 if (!dup->filter)
119 return isl_schedule_tree_free(dup);
120 break;
121 case isl_schedule_node_guard:
122 dup->guard = isl_set_copy(tree->guard);
123 if (!dup->guard)
124 return isl_schedule_tree_free(dup);
125 break;
126 case isl_schedule_node_mark:
127 dup->mark = isl_id_copy(tree->mark);
128 if (!dup->mark)
129 return isl_schedule_tree_free(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(tree->children);
139 if (!dup->children)
140 return isl_schedule_tree_free(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 */
isl_schedule_tree_cow(__isl_take isl_schedule_tree * tree)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 */
isl_schedule_tree_copy(__isl_keep isl_schedule_tree * tree)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 */
isl_schedule_tree_free(__isl_take isl_schedule_tree * tree)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(tree->band);
187 break;
188 case isl_schedule_node_context:
189 isl_set_free(tree->context);
190 break;
191 case isl_schedule_node_domain:
192 isl_union_set_free(tree->domain);
193 break;
194 case isl_schedule_node_expansion:
195 isl_union_pw_multi_aff_free(tree->contraction);
196 isl_union_map_free(tree->expansion);
197 break;
198 case isl_schedule_node_extension:
199 isl_union_map_free(tree->extension);
200 break;
201 case isl_schedule_node_filter:
202 isl_union_set_free(tree->filter);
203 break;
204 case isl_schedule_node_guard:
205 isl_set_free(tree->guard);
206 break;
207 case isl_schedule_node_mark:
208 isl_id_free(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(tree->children);
217 isl_ctx_deref(tree->ctx);
218 free(tree);
219
220 return NULL;
221 }
222
223 /* Create and return a new leaf schedule tree.
224 */
isl_schedule_tree_leaf(isl_ctx * ctx)225 __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
226 {
227 return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
228 }
229
230 /* Create a new band schedule tree referring to "band"
231 * with no children.
232 */
isl_schedule_tree_from_band(__isl_take isl_schedule_band * band)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, 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 */
isl_schedule_tree_from_context(__isl_take isl_set * context)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(context);
270 tree = isl_schedule_tree_alloc(ctx, 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(context);
280 return NULL;
281 }
282
283 /* Create a new domain schedule tree with the given domain and no children.
284 */
isl_schedule_tree_from_domain(__isl_take isl_union_set * domain)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(domain);
295 tree = isl_schedule_tree_alloc(ctx, 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(domain);
304 return NULL;
305 }
306
307 /* Create a new expansion schedule tree with the given contraction and
308 * expansion and no children.
309 */
isl_schedule_tree_from_expansion(__isl_take isl_union_pw_multi_aff * contraction,__isl_take isl_union_map * expansion)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(expansion);
321 tree = isl_schedule_tree_alloc(ctx, 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(contraction);
331 isl_union_map_free(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 */
isl_schedule_tree_from_extension(__isl_take isl_union_map * extension)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(extension);
350 tree = isl_schedule_tree_alloc(ctx, 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(extension);
360 return NULL;
361 }
362
363 /* Create a new filter schedule tree with the given filter and no children.
364 */
isl_schedule_tree_from_filter(__isl_take isl_union_set * filter)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(filter);
375 tree = isl_schedule_tree_alloc(ctx, 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(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 */
isl_schedule_tree_from_guard(__isl_take isl_set * guard)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(guard);
401 tree = isl_schedule_tree_alloc(ctx, 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(guard);
411 return NULL;
412 }
413
414 /* Create a new mark schedule tree with the given mark identifier and
415 * no children.
416 */
isl_schedule_tree_from_mark(__isl_take isl_id * mark)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(mark);
427 tree = isl_schedule_tree_alloc(ctx, 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(mark);
436 return NULL;
437 }
438
439 /* Does "tree" have any node that depends on its position
440 * in the complete schedule tree?
441 */
isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree * tree)442 isl_bool isl_schedule_tree_is_subtree_anchored(
443 __isl_keep isl_schedule_tree *tree)
444 {
445 return tree ? isl_bool_ok(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 */
isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree * tree)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(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 */
isl_schedule_tree_update_anchored(__isl_take isl_schedule_tree * tree)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, i);
503 if (!child)
504 return isl_schedule_tree_free(tree);
505 anchored = child->anchored;
506 isl_schedule_tree_free(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 */
isl_schedule_tree_from_children(enum isl_schedule_node_type type,__isl_take isl_schedule_tree_list * list)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 */
isl_schedule_tree_from_pair(enum isl_schedule_node_type type,__isl_take isl_schedule_tree * tree1,__isl_take isl_schedule_tree * tree2)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(tree1);
561 if (isl_schedule_tree_get_type(tree1) == type) {
562 list = isl_schedule_tree_list_copy(tree1->children);
563 isl_schedule_tree_free(tree1);
564 } else {
565 list = isl_schedule_tree_list_alloc(ctx, 2);
566 list = isl_schedule_tree_list_add(list, tree1);
567 }
568 if (isl_schedule_tree_get_type(tree2) == type) {
569 isl_schedule_tree_list *children;
570
571 children = isl_schedule_tree_list_copy(tree2->children);
572 list = isl_schedule_tree_list_concat(list, children);
573 isl_schedule_tree_free(tree2);
574 } else {
575 list = isl_schedule_tree_list_add(list, tree2);
576 }
577
578 return isl_schedule_tree_from_children(type, list);
579 error:
580 isl_schedule_tree_free(tree1);
581 isl_schedule_tree_free(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 */
isl_schedule_tree_sequence_pair(__isl_take isl_schedule_tree * tree1,__isl_take isl_schedule_tree * tree2)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(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 */
isl_schedule_tree_set_pair(__isl_take isl_schedule_tree * tree1,__isl_take isl_schedule_tree * tree2)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(isl_schedule_node_set, tree1, tree2);
608 }
609
610 /* Return the isl_ctx to which "tree" belongs.
611 */
isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree * tree)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 */
isl_schedule_tree_get_type(__isl_keep isl_schedule_tree * tree)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 */
isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree * tree1,__isl_keep isl_schedule_tree * tree2)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(tree1->band,
645 tree2->band);
646 break;
647 case isl_schedule_node_context:
648 equal = isl_set_is_equal(tree1->context, tree2->context);
649 break;
650 case isl_schedule_node_domain:
651 equal = isl_union_set_is_equal(tree1->domain, tree2->domain);
652 break;
653 case isl_schedule_node_expansion:
654 equal = isl_union_map_is_equal(tree1->expansion,
655 tree2->expansion);
656 if (equal >= 0 && equal)
657 equal = isl_union_pw_multi_aff_plain_is_equal(
658 tree1->contraction, tree2->contraction);
659 break;
660 case isl_schedule_node_extension:
661 equal = isl_union_map_is_equal(tree1->extension,
662 tree2->extension);
663 break;
664 case isl_schedule_node_filter:
665 equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
666 break;
667 case isl_schedule_node_guard:
668 equal = isl_set_is_equal(tree1->guard, tree2->guard);
669 break;
670 case isl_schedule_node_mark:
671 equal = isl_bool_ok(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(tree1);
687 n2 = isl_schedule_tree_n_children(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(tree1, i);
696 child2 = isl_schedule_tree_get_child(tree2, i);
697 equal = isl_schedule_tree_plain_is_equal(child1, child2);
698 isl_schedule_tree_free(child1);
699 isl_schedule_tree_free(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 */
isl_schedule_tree_has_children(__isl_keep isl_schedule_tree * tree)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 */
isl_schedule_tree_n_children(__isl_keep isl_schedule_tree * tree)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(tree->children);
730 }
731
732 /* Return a copy of the (explicit) child at position "pos" of "tree".
733 */
isl_schedule_tree_get_child(__isl_keep isl_schedule_tree * tree,int pos)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(tree->children, pos);
743 }
744
745 /* Return a copy of the (explicit) child at position "pos" of "tree" and
746 * free "tree".
747 */
isl_schedule_tree_child(__isl_take isl_schedule_tree * tree,int pos)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 */
isl_schedule_tree_reset_children(__isl_take isl_schedule_tree * tree)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(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 */
isl_schedule_tree_drop_child(__isl_take isl_schedule_tree * tree,int pos)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(tree->children, pos, 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 */
isl_schedule_tree_replace_child(__isl_take isl_schedule_tree * tree,int pos,__isl_take isl_schedule_tree * child)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(child)) {
818 isl_size n;
819
820 isl_schedule_tree_free(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(child);
837 else
838 tree->children = isl_schedule_tree_list_set_schedule_tree(
839 tree->children, pos, 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(child);
849 return NULL;
850 }
851
852 /* Replace the (explicit) children of "tree" by "children"?
853 */
isl_schedule_tree_set_children(__isl_take isl_schedule_tree * tree,__isl_take isl_schedule_tree_list * children)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(tree->children);
862 tree->children = children;
863 return tree;
864 error:
865 isl_schedule_tree_free(tree);
866 isl_schedule_tree_list_free(children);
867 return NULL;
868 }
869
870 /* Create a new band schedule tree referring to "band"
871 * with "tree" as single child.
872 */
isl_schedule_tree_insert_band(__isl_take isl_schedule_tree * tree,__isl_take isl_schedule_band * band)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(res, 0, tree);
880 }
881
882 /* Create a new context schedule tree with the given context and
883 * with "tree" as single child.
884 */
isl_schedule_tree_insert_context(__isl_take isl_schedule_tree * tree,__isl_take isl_set * context)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(res, 0, tree);
892 }
893
894 /* Create a new domain schedule tree with the given domain and
895 * with "tree" as single child.
896 */
isl_schedule_tree_insert_domain(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * domain)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(res, 0, tree);
904 }
905
906 /* Create a new expansion schedule tree with the given contraction and
907 * expansion and with "tree" as single child.
908 */
isl_schedule_tree_insert_expansion(__isl_take isl_schedule_tree * tree,__isl_take isl_union_pw_multi_aff * contraction,__isl_take isl_union_map * expansion)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(res, 0, tree);
918 }
919
920 /* Create a new extension schedule tree with the given extension and
921 * with "tree" as single child.
922 */
isl_schedule_tree_insert_extension(__isl_take isl_schedule_tree * tree,__isl_take isl_union_map * extension)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(res, 0, 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 */
isl_schedule_tree_insert_filter(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * filter)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(tree_filter, filter);
947 tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
948 return tree;
949 }
950
951 res = isl_schedule_tree_from_filter(filter);
952 return isl_schedule_tree_replace_child(res, 0, tree);
953 }
954
955 /* Insert a filter node with filter set "filter"
956 * in each of the children of "tree".
957 */
isl_schedule_tree_children_insert_filter(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * filter)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, i);
972 child = isl_schedule_tree_insert_filter(child,
973 isl_union_set_copy(filter));
974 tree = isl_schedule_tree_replace_child(tree, i, child);
975 }
976
977 isl_union_set_free(filter);
978 return tree;
979 error:
980 isl_union_set_free(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 */
isl_schedule_tree_insert_guard(__isl_take isl_schedule_tree * tree,__isl_take isl_set * guard)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(res, 0, tree);
995 }
996
997 /* Create a new mark schedule tree with the given mark identifier and
998 * single child.
999 */
isl_schedule_tree_insert_mark(__isl_take isl_schedule_tree * tree,__isl_take isl_id * mark)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(res, 0, tree);
1007 }
1008
1009 /* Return the number of members in the band tree root.
1010 */
isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree * tree)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(tree->band);
1021 }
1022
1023 /* Is the band member at position "pos" of the band tree root
1024 * marked coincident?
1025 */
isl_schedule_tree_band_member_get_coincident(__isl_keep isl_schedule_tree * tree,int pos)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(tree->band, pos);
1037 }
1038
1039 /* Mark the given band member as being coincident or not
1040 * according to "coincident".
1041 */
isl_schedule_tree_band_member_set_coincident(__isl_take isl_schedule_tree * tree,int pos,int coincident)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(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 */
isl_schedule_tree_band_get_permutable(__isl_keep isl_schedule_tree * tree)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(tree->band);
1077 }
1078
1079 /* Mark the band tree root permutable or not according to "permutable"?
1080 */
isl_schedule_tree_band_set_permutable(__isl_take isl_schedule_tree * tree,int permutable)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(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 */
isl_schedule_tree_band_get_space(__isl_keep isl_schedule_tree * tree)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(tree->band);
1114 }
1115
1116 /* Intersect the domain of the band schedule of the band tree root
1117 * with "domain".
1118 */
isl_schedule_tree_band_intersect_domain(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * domain)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(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(domain);
1137 return NULL;
1138 }
1139
1140 /* Return the schedule of the band tree root in isolation.
1141 */
isl_schedule_tree_band_get_partial_schedule(__isl_keep isl_schedule_tree * tree)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(tree->band);
1153 }
1154
1155 /* Replace the schedule of the band tree root by "schedule".
1156 */
isl_schedule_tree_band_set_partial_schedule(__isl_take isl_schedule_tree * tree,__isl_take isl_multi_union_pw_aff * schedule)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(tree->band,
1169 schedule);
1170
1171 return tree;
1172 error:
1173 isl_schedule_tree_free(tree);
1174 isl_multi_union_pw_aff_free(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 */
isl_schedule_tree_band_member_get_ast_loop_type(__isl_keep isl_schedule_tree * tree,int pos)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(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 */
isl_schedule_tree_band_member_set_ast_loop_type(__isl_take isl_schedule_tree * tree,int pos,enum isl_ast_loop_type type)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(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 */
isl_schedule_tree_band_member_get_isolate_ast_loop_type(__isl_keep isl_schedule_tree * tree,int pos)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(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 *
isl_schedule_tree_band_member_set_isolate_ast_loop_type(__isl_take isl_schedule_tree * tree,int pos,enum isl_ast_loop_type type)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 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 */
isl_schedule_tree_band_get_ast_build_options(__isl_keep isl_schedule_tree * tree)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(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 */
isl_schedule_tree_band_set_ast_build_options(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * options)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(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(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 */
isl_schedule_tree_band_get_ast_isolate_option(__isl_keep isl_schedule_tree * tree,int depth)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(tree->band, depth);
1319 }
1320
1321 /* Return the context of the context tree root.
1322 */
isl_schedule_tree_context_get_context(__isl_keep isl_schedule_tree * tree)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(tree->context);
1334 }
1335
1336 /* Return the domain of the domain tree root.
1337 */
isl_schedule_tree_domain_get_domain(__isl_keep isl_schedule_tree * tree)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(tree->domain);
1349 }
1350
1351 /* Replace the domain of domain tree root "tree" by "domain".
1352 */
isl_schedule_tree_domain_set_domain(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * domain)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(tree->domain);
1365 tree->domain = domain;
1366
1367 return tree;
1368 error:
1369 isl_schedule_tree_free(tree);
1370 isl_union_set_free(domain);
1371 return NULL;
1372 }
1373
1374 /* Return the contraction of the expansion tree root.
1375 */
isl_schedule_tree_expansion_get_contraction(__isl_keep isl_schedule_tree * tree)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(tree->contraction);
1387 }
1388
1389 /* Return the expansion of the expansion tree root.
1390 */
isl_schedule_tree_expansion_get_expansion(__isl_keep isl_schedule_tree * tree)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(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 *
isl_schedule_tree_expansion_set_contraction_and_expansion(__isl_take isl_schedule_tree * tree,__isl_take isl_union_pw_multi_aff * contraction,__isl_take isl_union_map * expansion)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(tree->contraction);
1422 tree->contraction = contraction;
1423 isl_union_map_free(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(contraction);
1430 isl_union_map_free(expansion);
1431 return NULL;
1432 }
1433
1434 /* Return the extension of the extension tree root.
1435 */
isl_schedule_tree_extension_get_extension(__isl_take isl_schedule_tree * tree)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(tree->extension);
1447 }
1448
1449 /* Replace the extension of extension tree root "tree" by "extension".
1450 */
isl_schedule_tree_extension_set_extension(__isl_take isl_schedule_tree * tree,__isl_take isl_union_map * extension)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(tree->extension);
1462 tree->extension = extension;
1463
1464 return tree;
1465 error:
1466 isl_schedule_tree_free(tree);
1467 isl_union_map_free(extension);
1468 return NULL;
1469 }
1470
1471 /* Return the filter of the filter tree root.
1472 */
isl_schedule_tree_filter_get_filter(__isl_keep isl_schedule_tree * tree)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(tree->filter);
1484 }
1485
1486 /* Replace the filter of the filter tree root by "filter".
1487 */
isl_schedule_tree_filter_set_filter(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * filter)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(tree->filter);
1500 tree->filter = filter;
1501
1502 return tree;
1503 error:
1504 isl_schedule_tree_free(tree);
1505 isl_union_set_free(filter);
1506 return NULL;
1507 }
1508
1509 /* Return the guard of the guard tree root.
1510 */
isl_schedule_tree_guard_get_guard(__isl_take isl_schedule_tree * tree)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(tree->guard);
1522 }
1523
1524 /* Return the mark identifier of the mark tree root "tree".
1525 */
isl_schedule_tree_mark_get_id(__isl_keep isl_schedule_tree * tree)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(tree->mark);
1537 }
1538
1539 /* Set dim to the range dimension of "map" and abort the search.
1540 */
set_range_dim(__isl_take isl_map * map,void * user)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, 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 */
range_dim(__isl_keep isl_union_map * umap)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, &set_range_dim, &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 */
append_range(__isl_take isl_union_map * umap,int extra)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(isl_union_map_copy(umap));
1588 dom = isl_union_map_domain(universe);
1589 space = isl_union_set_get_space(dom);
1590 space = isl_space_set_from_params(space);
1591 space = isl_space_add_dims(space, isl_dim_set, extra);
1592 mv = isl_multi_val_zero(space);
1593
1594 suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1595 suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1596 umap = isl_union_map_flat_range_product(umap, 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 */
domain_less(__isl_keep isl_schedule_tree * tree)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(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 */
isl_schedule_tree_first_schedule_descendant(__isl_take isl_schedule_tree * tree,__isl_keep isl_schedule_tree * leaf)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(leaf);
1653 }
1654 tree = isl_schedule_tree_child(tree, 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 */
subtree_schedule_extend_child(__isl_keep isl_schedule_tree * tree,__isl_take isl_union_map * outer)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(outer);
1682 if (!isl_schedule_tree_has_children(tree))
1683 return outer;
1684 child = isl_schedule_tree_get_child(tree, 0);
1685 if (!child)
1686 return isl_union_map_free(outer);
1687 res = subtree_schedule_extend(child, outer);
1688 isl_schedule_tree_free(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 */
extract_space_from_filter_child(__isl_keep isl_schedule_tree * tree)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(tree->children, 0);
1703 dom = isl_schedule_tree_filter_get_filter(child);
1704 space = isl_union_set_get_space(dom);
1705 isl_union_set_free(dom);
1706 isl_schedule_tree_free(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 */
subtree_schedule_extend_from_children(__isl_keep isl_schedule_tree * tree,__isl_take isl_union_map * outer)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(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, 0);
1756
1757 umap = isl_union_map_empty(isl_space_copy(space));
1758 space = isl_space_set_from_params(space);
1759 if (separate) {
1760 space = isl_space_add_dims(space, isl_dim_set, 1);
1761 v = isl_val_zero(ctx);
1762 }
1763 mv = isl_multi_val_zero(space);
1764
1765 dim = isl_multi_val_dim(mv, 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 tree->children, i);
1779 dom = isl_schedule_tree_filter_get_filter(child);
1780
1781 if (separate) {
1782 mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1783 v = isl_val_add_ui(v, 1);
1784 }
1785 mv_copy = isl_multi_val_copy(mv);
1786 space = isl_union_set_get_space(dom);
1787 mv_copy = isl_multi_val_align_params(mv_copy, space);
1788 upma = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv_copy);
1789 umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1790 umap_i = isl_union_map_flat_range_product(
1791 isl_union_map_copy(outer), umap_i);
1792 umap_i = subtree_schedule_extend_child(child, umap_i);
1793 isl_schedule_tree_free(child);
1794
1795 empty = isl_union_map_is_empty(umap_i);
1796 if (empty < 0)
1797 umap_i = isl_union_map_free(umap_i);
1798 else if (empty) {
1799 isl_union_map_free(umap_i);
1800 continue;
1801 }
1802
1803 dim_i = range_dim(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, dim_i - dim);
1808 dim = dim_i;
1809 } else if (dim_i < dim) {
1810 umap_i = append_range(umap_i, dim - dim_i);
1811 }
1812 umap = isl_union_map_union(umap, umap_i);
1813 }
1814
1815 isl_val_free(v);
1816 isl_multi_val_free(mv);
1817 isl_union_map_free(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 */
subtree_schedule_extend(__isl_keep isl_schedule_tree * tree,__isl_take isl_union_map * outer)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(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(outer);
1859 if (n == 0)
1860 return subtree_schedule_extend_child(tree, outer);
1861 mupa = isl_schedule_band_get_partial_schedule(tree->band);
1862 umap = isl_union_map_from_multi_union_pw_aff(mupa);
1863 outer = isl_union_map_flat_range_product(outer, 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(domain);
1869 outer = isl_union_map_flat_range_product(outer, 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(outer, 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(domain);
1880 outer = isl_union_map_flat_range_product(outer, 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 */
initial_domain_from_children(__isl_keep isl_schedule_tree * tree)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, i);
1925 domain_i = initial_domain(child);
1926 domain = isl_union_set_union(domain, domain_i);
1927 isl_schedule_tree_free(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 */
initial_domain(__isl_keep isl_schedule_tree * tree)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(tree->band);
1978 domain = isl_multi_union_pw_aff_domain(mupa);
1979 domain = isl_union_set_universe(domain);
1980 break;
1981 case isl_schedule_node_domain:
1982 domain = isl_schedule_tree_domain_get_domain(tree);
1983 domain = isl_union_set_universe(domain);
1984 break;
1985 case isl_schedule_node_expansion:
1986 exp = isl_schedule_tree_expansion_get_expansion(tree);
1987 exp = isl_union_map_universe(exp);
1988 domain = isl_union_map_domain(exp);
1989 break;
1990 case isl_schedule_node_filter:
1991 domain = isl_schedule_tree_filter_get_filter(tree);
1992 domain = isl_union_set_universe(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 */
isl_schedule_tree_get_subtree_schedule_union_map(__isl_keep isl_schedule_tree * tree)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(domain);
2026 return subtree_schedule_extend(tree, umap);
2027 }
2028
2029 /* Multiply the partial schedule of the band root node of "tree"
2030 * with the factors in "mv".
2031 */
isl_schedule_tree_band_scale(__isl_take isl_schedule_tree * tree,__isl_take isl_multi_val * mv)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(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(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 */
isl_schedule_tree_band_scale_down(__isl_take isl_schedule_tree * tree,__isl_take isl_multi_val * mv)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(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(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 */
isl_schedule_tree_band_mod(__isl_take isl_schedule_tree * tree,__isl_take isl_multi_val * mv)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(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(mv);
2107 return NULL;
2108 }
2109
2110 /* Shift the partial schedule of the band root node of "tree" by "shift".
2111 */
isl_schedule_tree_band_shift(__isl_take isl_schedule_tree * tree,__isl_take isl_multi_union_pw_aff * shift)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(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(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 */
isl_schedule_tree_sequence_splice(__isl_take isl_schedule_tree * tree,int pos,__isl_take isl_schedule_tree * child)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(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(tree->children);
2164 list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2165 list2 = isl_schedule_tree_list_copy(tree->children);
2166 list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2167 list1 = isl_schedule_tree_list_concat(list1,
2168 isl_schedule_tree_list_copy(child->children));
2169 list1 = isl_schedule_tree_list_concat(list1, list2);
2170
2171 isl_schedule_tree_free(tree);
2172 isl_schedule_tree_free(child);
2173 return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2174 list1);
2175 error:
2176 isl_schedule_tree_free(tree);
2177 isl_schedule_tree_free(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 */
isl_schedule_tree_band_tile(__isl_take isl_schedule_tree * tree,__isl_take isl_multi_val * sizes)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(child);
2201 if (!tree || !child)
2202 goto error;
2203
2204 tree->band = isl_schedule_band_tile(tree->band,
2205 isl_multi_val_copy(sizes));
2206 if (!tree->band)
2207 goto error;
2208 child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2209 if (!child->band)
2210 child = isl_schedule_tree_free(child);
2211
2212 tree = isl_schedule_tree_replace_child(tree, 0, child);
2213
2214 return tree;
2215 error:
2216 isl_schedule_tree_free(child);
2217 isl_schedule_tree_free(tree);
2218 isl_multi_val_free(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 */
isolate_initial(__isl_keep isl_set * isolate,int pos,int n)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(isolate);
2241 id = isl_set_get_tuple_id(isolate);
2242 map = isl_set_unwrap(isolate);
2243 map = isl_map_project_out(map, isl_dim_out, pos, n);
2244 isolate = isl_map_wrap(map);
2245 isolate = isl_set_set_tuple_id(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 */
isolate_final(__isl_keep isl_set * isolate,int pos,int n)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(isolate);
2282 id = isl_set_get_tuple_id(isolate);
2283 map = isl_set_unwrap(isolate);
2284 space = isl_space_range(isl_map_get_space(map));
2285 ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
2286 isl_dim_set, pos, n);
2287 ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
2288 ma1 = isl_multi_aff_range_product(ma1, ma2);
2289 map = isl_map_apply_range(map, isl_map_from_multi_aff(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(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 */
isl_schedule_tree_band_split(__isl_take isl_schedule_tree * tree,int pos,int depth)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(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 - pos);
2335 child_isolate = isolate_final(isolate, pos, n - pos);
2336 child->band = isl_schedule_band_drop(child->band, 0, pos);
2337 child->band = isl_schedule_band_replace_ast_build_option(child->band,
2338 isl_set_copy(isolate), child_isolate);
2339 tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2340 tree->band = isl_schedule_band_replace_ast_build_option(tree->band,
2341 isl_set_copy(isolate), tree_isolate);
2342 isl_set_free(isolate);
2343 if (!child->band || !tree->band)
2344 goto error;
2345
2346 tree = isl_schedule_tree_replace_child(tree, 0, child);
2347
2348 return tree;
2349 error:
2350 isl_schedule_tree_free(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 */
isl_schedule_tree_append_to_leaves(__isl_take isl_schedule_tree * tree1,__isl_take isl_schedule_tree * tree2)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(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(tree2);
2374 tree1 = isl_schedule_tree_set_children(tree1, 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(tree1, i);
2381 child = isl_schedule_tree_append_to_leaves(child,
2382 isl_schedule_tree_copy(tree2));
2383 tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2384 }
2385
2386 isl_schedule_tree_free(tree2);
2387 return tree1;
2388 error:
2389 isl_schedule_tree_free(tree1);
2390 isl_schedule_tree_free(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 */
isl_schedule_tree_reset_user(__isl_take isl_schedule_tree * tree)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(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(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(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(tree->contraction);
2428 tree->expansion = isl_union_map_reset_user(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(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(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(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 */
isl_schedule_tree_align_params(__isl_take isl_schedule_tree * tree,__isl_take isl_space * space)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(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(tree->context, 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(tree->domain, 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(tree->contraction,
2495 isl_space_copy(space));
2496 tree->expansion = isl_union_map_align_params(tree->expansion,
2497 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(tree->extension,
2503 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(tree->filter, 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(tree->guard, 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 */
involves_iteration_domain(__isl_keep isl_schedule_tree * tree)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 */
isl_schedule_tree_pullback_union_pw_multi_aff(__isl_take isl_schedule_tree * tree,__isl_take isl_union_pw_multi_aff * upma)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 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(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 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(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 */
isl_schedule_tree_band_gist(__isl_take isl_schedule_tree * tree,__isl_take isl_union_set * context)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(tree->band, context);
2643 if (!tree->band)
2644 return isl_schedule_tree_free(tree);
2645 return tree;
2646 error:
2647 isl_union_set_free(context);
2648 isl_schedule_tree_free(tree);
2649 return NULL;
2650 }
2651
2652 /* Are any members in "band" marked coincident?
2653 */
any_coincident(__isl_keep isl_schedule_band * band)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, 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 */
print_tree_band(__isl_take isl_printer * p,__isl_keep isl_schedule_band * band)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, "schedule");
2687 p = isl_printer_yaml_next(p);
2688 p = isl_printer_print_str(p, "\"");
2689 p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2690 p = isl_printer_print_str(p, "\"");
2691 if (isl_schedule_band_get_permutable(band)) {
2692 p = isl_printer_yaml_next(p);
2693 p = isl_printer_print_str(p, "permutable");
2694 p = isl_printer_yaml_next(p);
2695 p = isl_printer_print_int(p, 1);
2696 }
2697 coincident = any_coincident(band);
2698 if (coincident < 0)
2699 return isl_printer_free(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, "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(p);
2714 for (i = 0; i < n; ++i) {
2715 p = isl_printer_print_int(p,
2716 isl_schedule_band_member_get_coincident(band, 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, style);
2721 }
2722 options = isl_schedule_band_get_ast_build_options(band);
2723 empty = isl_union_set_is_empty(options);
2724 if (empty < 0)
2725 p = isl_printer_free(p);
2726 if (!empty) {
2727 p = isl_printer_yaml_next(p);
2728 p = isl_printer_print_str(p, "options");
2729 p = isl_printer_yaml_next(p);
2730 p = isl_printer_print_str(p, "\"");
2731 p = isl_printer_print_union_set(p, options);
2732 p = isl_printer_print_str(p, "\"");
2733 }
2734 isl_union_set_free(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 */
isl_printer_print_schedule_tree_mark(__isl_take isl_printer * p,__isl_keep isl_schedule_tree * tree,int n_ancestor,int * child_pos)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, "# 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, "ERROR");
2791 p = isl_printer_yaml_next(p);
2792 break;
2793 case isl_schedule_node_leaf:
2794 p = isl_printer_print_str(p, "leaf");
2795 p = isl_printer_yaml_next(p);
2796 break;
2797 case isl_schedule_node_sequence:
2798 p = isl_printer_print_str(p, "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, "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, "context", tree->context);
2809 break;
2810 case isl_schedule_node_domain:
2811 p = print_yaml_field_union_set(p, "domain", tree->domain);
2812 break;
2813 case isl_schedule_node_expansion:
2814 p = print_yaml_field_union_pw_multi_aff(p, "contraction",
2815 tree->contraction);
2816 p = print_yaml_field_union_map(p, "expansion", tree->expansion);
2817 break;
2818 case isl_schedule_node_extension:
2819 p = print_yaml_field_union_map(p, "extension", tree->extension);
2820 break;
2821 case isl_schedule_node_filter:
2822 p = print_yaml_field_union_set(p, "filter", tree->filter);
2823 break;
2824 case isl_schedule_node_guard:
2825 p = print_yaml_field_set(p, "guard", tree->guard);
2826 break;
2827 case isl_schedule_node_mark:
2828 p = print_yaml_field_str(p, "mark",
2829 isl_id_get_name(tree->mark));
2830 break;
2831 case isl_schedule_node_band:
2832 p = print_tree_band(p, 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(p);
2840 if (n == 0) {
2841 if (n_ancestor > 0 && block) {
2842 isl_schedule_tree *leaf;
2843
2844 p = isl_printer_print_str(p, "child");
2845 p = isl_printer_yaml_next(p);
2846 leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2847 p = isl_printer_print_schedule_tree_mark(p,
2848 leaf, 0, NULL);
2849 isl_schedule_tree_free(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, "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, i);
2866 if (n_ancestor > 0 && child_pos[0] == i)
2867 p = isl_printer_print_schedule_tree_mark(p, t,
2868 n_ancestor - 1, child_pos + 1);
2869 else
2870 p = isl_printer_print_schedule_tree_mark(p, t,
2871 -1, NULL);
2872 isl_schedule_tree_free(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 */
isl_printer_print_schedule_tree(__isl_take isl_printer * p,__isl_keep isl_schedule_tree * tree)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, -1, NULL);
2890 }
2891
isl_schedule_tree_dump(__isl_keep isl_schedule_tree * tree)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(printer, ISL_YAML_STYLE_BLOCK);
2903 printer = isl_printer_print_schedule_tree(printer, tree);
2904
2905 isl_printer_free(printer);
2906 }
2907