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