isl_pw_*_eval: rename "pnt_dim" variable to "pnt_space"
[isl.git] / isl_schedule.c
blobddf0832550159184ba6ead0473427ecf77fe4023
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012-2014 Ecole Normale Superieure
4 * Copyright 2016 Sven Verdoolaege
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
14 #include <isl/ctx.h>
15 #include <isl/val.h>
16 #include <isl_aff_private.h>
17 #include <isl/map.h>
18 #include <isl/set.h>
19 #include <isl/schedule.h>
20 #include <isl/schedule_node.h>
21 #include <isl_sort.h>
22 #include <isl/printer.h>
23 #include <isl_schedule_private.h>
24 #include <isl_schedule_tree.h>
25 #include <isl_schedule_node_private.h>
27 /* Return a schedule encapsulating the given schedule tree.
29 * We currently only allow schedule trees with a domain or extension as root.
31 * The leaf field is initialized as a leaf node so that it can be
32 * used to represent leaves in the constructed schedule.
33 * The reference count is set to -1 since the isl_schedule_tree
34 * should never be freed. It is up to the (internal) users of
35 * these leaves to ensure that they are only used while the schedule
36 * is still alive.
38 __isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx,
39 __isl_take isl_schedule_tree *tree)
41 enum isl_schedule_node_type type;
42 isl_schedule *schedule;
44 if (!tree)
45 return NULL;
46 type = isl_schedule_tree_get_type(tree);
47 if (type != isl_schedule_node_domain &&
48 type != isl_schedule_node_extension)
49 isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
50 "root of schedule tree should be a domain or extension",
51 goto error);
53 schedule = isl_calloc_type(ctx, isl_schedule);
54 if (!schedule)
55 goto error;
57 schedule->ref = 1;
58 schedule->root = tree;
59 schedule->leaf = isl_schedule_tree_leaf(ctx);
61 if (!schedule->leaf)
62 return isl_schedule_free(schedule);
63 return schedule;
64 error:
65 isl_schedule_tree_free(tree);
66 return NULL;
69 /* Return a pointer to a schedule with as single node
70 * a domain node with the given domain.
72 __isl_give isl_schedule *isl_schedule_from_domain(
73 __isl_take isl_union_set *domain)
75 isl_ctx *ctx;
76 isl_schedule_tree *tree;
78 ctx = isl_union_set_get_ctx(domain);
79 tree = isl_schedule_tree_from_domain(domain);
80 return isl_schedule_from_schedule_tree(ctx, tree);
83 /* Return a pointer to a schedule with as single node
84 * a domain node with an empty domain.
86 __isl_give isl_schedule *isl_schedule_empty(__isl_take isl_space *space)
88 return isl_schedule_from_domain(isl_union_set_empty(space));
91 /* Return a new reference to "sched".
93 __isl_give isl_schedule *isl_schedule_copy(__isl_keep isl_schedule *sched)
95 if (!sched)
96 return NULL;
98 sched->ref++;
99 return sched;
102 /* Return an isl_schedule that is equal to "schedule" and that has only
103 * a single reference.
105 __isl_give isl_schedule *isl_schedule_cow(__isl_take isl_schedule *schedule)
107 isl_ctx *ctx;
108 isl_schedule_tree *tree;
110 if (!schedule)
111 return NULL;
112 if (schedule->ref == 1)
113 return schedule;
115 ctx = isl_schedule_get_ctx(schedule);
116 schedule->ref--;
117 tree = isl_schedule_tree_copy(schedule->root);
118 return isl_schedule_from_schedule_tree(ctx, tree);
121 __isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched)
123 if (!sched)
124 return NULL;
126 if (--sched->ref > 0)
127 return NULL;
129 isl_schedule_tree_free(sched->root);
130 isl_schedule_tree_free(sched->leaf);
131 free(sched);
132 return NULL;
135 /* Replace the root of "schedule" by "tree".
137 __isl_give isl_schedule *isl_schedule_set_root(
138 __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree)
140 if (!schedule || !tree)
141 goto error;
142 if (schedule->root == tree) {
143 isl_schedule_tree_free(tree);
144 return schedule;
147 schedule = isl_schedule_cow(schedule);
148 if (!schedule)
149 goto error;
150 isl_schedule_tree_free(schedule->root);
151 schedule->root = tree;
153 return schedule;
154 error:
155 isl_schedule_free(schedule);
156 isl_schedule_tree_free(tree);
157 return NULL;
160 isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
162 return schedule ? isl_schedule_tree_get_ctx(schedule->leaf) : NULL;
165 /* Return a pointer to the leaf of "schedule".
167 __isl_keep isl_schedule_tree *isl_schedule_peek_leaf(
168 __isl_keep isl_schedule *schedule)
170 return schedule ? schedule->leaf : NULL;
173 /* Are "schedule1" and "schedule2" obviously equal to each other?
175 isl_bool isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1,
176 __isl_keep isl_schedule *schedule2)
178 if (!schedule1 || !schedule2)
179 return isl_bool_error;
180 if (schedule1 == schedule2)
181 return isl_bool_true;
182 return isl_schedule_tree_plain_is_equal(schedule1->root,
183 schedule2->root);
186 /* Return the (parameter) space of the schedule, i.e., the space
187 * of the root domain.
189 __isl_give isl_space *isl_schedule_get_space(
190 __isl_keep isl_schedule *schedule)
192 enum isl_schedule_node_type type;
193 isl_space *space;
194 isl_union_set *domain;
196 if (!schedule)
197 return NULL;
198 type = isl_schedule_tree_get_type(schedule->root);
199 if (type != isl_schedule_node_domain)
200 isl_die(isl_schedule_get_ctx(schedule), isl_error_internal,
201 "root node not a domain node", return NULL);
203 domain = isl_schedule_tree_domain_get_domain(schedule->root);
204 space = isl_union_set_get_space(domain);
205 isl_union_set_free(domain);
207 return space;
210 /* Return a pointer to the root of "schedule".
212 __isl_give isl_schedule_node *isl_schedule_get_root(
213 __isl_keep isl_schedule *schedule)
215 isl_ctx *ctx;
216 isl_schedule_tree *tree;
217 isl_schedule_tree_list *ancestors;
219 if (!schedule)
220 return NULL;
222 ctx = isl_schedule_get_ctx(schedule);
223 tree = isl_schedule_tree_copy(schedule->root);
224 schedule = isl_schedule_copy(schedule);
225 ancestors = isl_schedule_tree_list_alloc(ctx, 0);
226 return isl_schedule_node_alloc(schedule, tree, ancestors, NULL);
229 /* Return the domain of the root domain node of "schedule".
231 __isl_give isl_union_set *isl_schedule_get_domain(
232 __isl_keep isl_schedule *schedule)
234 if (!schedule)
235 return NULL;
236 return isl_schedule_tree_domain_get_domain(schedule->root);
239 /* Traverse all nodes of "sched" in depth first preorder.
241 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
242 * If "fn" returns 0 on any of the nodes, then the subtree rooted
243 * at that node is skipped.
245 * Return 0 on success and -1 on failure.
247 isl_stat isl_schedule_foreach_schedule_node_top_down(
248 __isl_keep isl_schedule *sched,
249 isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user),
250 void *user)
252 isl_schedule_node *node;
253 isl_stat r;
255 if (!sched)
256 return isl_stat_error;
258 node = isl_schedule_get_root(sched);
259 r = isl_schedule_node_foreach_descendant_top_down(node, fn, user);
260 isl_schedule_node_free(node);
262 return r;
265 /* Traverse the node of "sched" in depth first postorder,
266 * allowing the user to modify the visited node.
267 * The traversal continues from the node returned by the callback function.
268 * It is the responsibility of the user to ensure that this does not
269 * lead to an infinite loop. It is safest to always return a pointer
270 * to the same position (same ancestors and child positions) as the input node.
272 __isl_give isl_schedule *isl_schedule_map_schedule_node_bottom_up(
273 __isl_take isl_schedule *schedule,
274 __isl_give isl_schedule_node *(*fn)(
275 __isl_take isl_schedule_node *node, void *user), void *user)
277 isl_schedule_node *node;
279 node = isl_schedule_get_root(schedule);
280 isl_schedule_free(schedule);
282 node = isl_schedule_node_map_descendant_bottom_up(node, fn, user);
283 schedule = isl_schedule_node_get_schedule(node);
284 isl_schedule_node_free(node);
286 return schedule;
289 /* Wrapper around isl_schedule_node_reset_user for use as
290 * an isl_schedule_map_schedule_node_bottom_up callback.
292 static __isl_give isl_schedule_node *reset_user(
293 __isl_take isl_schedule_node *node, void *user)
295 return isl_schedule_node_reset_user(node);
298 /* Reset the user pointer on all identifiers of parameters and tuples
299 * in the schedule "schedule".
301 __isl_give isl_schedule *isl_schedule_reset_user(
302 __isl_take isl_schedule *schedule)
304 return isl_schedule_map_schedule_node_bottom_up(schedule, &reset_user,
305 NULL);
308 /* Wrapper around isl_schedule_node_align_params for use as
309 * an isl_schedule_map_schedule_node_bottom_up callback.
311 static __isl_give isl_schedule_node *align_params(
312 __isl_take isl_schedule_node *node, void *user)
314 isl_space *space = user;
316 return isl_schedule_node_align_params(node, isl_space_copy(space));
319 /* Align the parameters of all nodes in schedule "schedule"
320 * to those of "space".
322 __isl_give isl_schedule *isl_schedule_align_params(
323 __isl_take isl_schedule *schedule, __isl_take isl_space *space)
325 schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
326 &align_params, space);
327 isl_space_free(space);
328 return schedule;
331 /* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as
332 * an isl_schedule_map_schedule_node_bottom_up callback.
334 static __isl_give isl_schedule_node *pullback_upma(
335 __isl_take isl_schedule_node *node, void *user)
337 isl_union_pw_multi_aff *upma = user;
339 return isl_schedule_node_pullback_union_pw_multi_aff(node,
340 isl_union_pw_multi_aff_copy(upma));
343 /* Compute the pullback of "schedule" by the function represented by "upma".
344 * In other words, plug in "upma" in the iteration domains of "schedule".
346 * The schedule tree is not allowed to contain any expansion nodes.
348 __isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff(
349 __isl_take isl_schedule *schedule,
350 __isl_take isl_union_pw_multi_aff *upma)
352 schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
353 &pullback_upma, upma);
354 isl_union_pw_multi_aff_free(upma);
355 return schedule;
358 /* Expand the schedule "schedule" by extending all leaves
359 * with an expansion node with as subtree the tree of "expansion".
360 * The expansion of the expansion node is determined by "contraction"
361 * and the domain of "expansion". That is, the domain of "expansion"
362 * is contracted according to "contraction".
364 * Call isl_schedule_node_expand after extracting the required
365 * information from "expansion".
367 __isl_give isl_schedule *isl_schedule_expand(__isl_take isl_schedule *schedule,
368 __isl_take isl_union_pw_multi_aff *contraction,
369 __isl_take isl_schedule *expansion)
371 isl_union_set *domain;
372 isl_schedule_node *node;
373 isl_schedule_tree *tree;
375 domain = isl_schedule_get_domain(expansion);
377 node = isl_schedule_get_root(expansion);
378 node = isl_schedule_node_child(node, 0);
379 tree = isl_schedule_node_get_tree(node);
380 isl_schedule_node_free(node);
381 isl_schedule_free(expansion);
383 node = isl_schedule_get_root(schedule);
384 isl_schedule_free(schedule);
385 node = isl_schedule_node_expand(node, contraction, domain, tree);
386 schedule = isl_schedule_node_get_schedule(node);
387 isl_schedule_node_free(node);
389 return schedule;
392 /* Intersect the domain of the schedule "schedule" with "domain".
393 * The root of "schedule" is required to be a domain node.
395 __isl_give isl_schedule *isl_schedule_intersect_domain(
396 __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain)
398 enum isl_schedule_node_type root_type;
399 isl_schedule_node *node;
401 if (!schedule || !domain)
402 goto error;
404 root_type = isl_schedule_tree_get_type(schedule->root);
405 if (root_type != isl_schedule_node_domain)
406 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
407 "root node must be a domain node", goto error);
409 node = isl_schedule_get_root(schedule);
410 isl_schedule_free(schedule);
411 node = isl_schedule_node_domain_intersect_domain(node, domain);
412 schedule = isl_schedule_node_get_schedule(node);
413 isl_schedule_node_free(node);
415 return schedule;
416 error:
417 isl_schedule_free(schedule);
418 isl_union_set_free(domain);
419 return NULL;
422 /* Replace the domain of the schedule "schedule" with the gist
423 * of the original domain with respect to the parameter domain "context".
425 __isl_give isl_schedule *isl_schedule_gist_domain_params(
426 __isl_take isl_schedule *schedule, __isl_take isl_set *context)
428 enum isl_schedule_node_type root_type;
429 isl_schedule_node *node;
431 if (!schedule || !context)
432 goto error;
434 root_type = isl_schedule_tree_get_type(schedule->root);
435 if (root_type != isl_schedule_node_domain)
436 isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
437 "root node must be a domain node", goto error);
439 node = isl_schedule_get_root(schedule);
440 isl_schedule_free(schedule);
441 node = isl_schedule_node_domain_gist_params(node, context);
442 schedule = isl_schedule_node_get_schedule(node);
443 isl_schedule_node_free(node);
445 return schedule;
446 error:
447 isl_schedule_free(schedule);
448 isl_set_free(context);
449 return NULL;
452 /* Return an isl_union_map representation of the schedule. In particular,
453 * return an isl_union_map corresponding to the subtree schedule of the child
454 * of the root domain node. That is, we do not intersect the domain
455 * of the returned isl_union_map with the domain constraints.
457 __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
459 enum isl_schedule_node_type type;
460 isl_schedule_node *node;
461 isl_union_map *umap;
463 if (!sched)
464 return NULL;
465 type = isl_schedule_tree_get_type(sched->root);
466 if (type != isl_schedule_node_domain)
467 isl_die(isl_schedule_get_ctx(sched), isl_error_internal,
468 "root node not a domain node", return NULL);
470 node = isl_schedule_get_root(sched);
471 node = isl_schedule_node_child(node, 0);
472 umap = isl_schedule_node_get_subtree_schedule_union_map(node);
473 isl_schedule_node_free(node);
475 return umap;
478 /* Insert a band node with partial schedule "partial" between the domain
479 * root node of "schedule" and its single child.
480 * Return a pointer to the updated schedule.
482 * If any of the nodes in the tree depend on the set of outer band nodes
483 * then we refuse to insert the band node.
485 __isl_give isl_schedule *isl_schedule_insert_partial_schedule(
486 __isl_take isl_schedule *schedule,
487 __isl_take isl_multi_union_pw_aff *partial)
489 isl_schedule_node *node;
490 int anchored;
492 node = isl_schedule_get_root(schedule);
493 isl_schedule_free(schedule);
494 if (!node)
495 goto error;
496 if (isl_schedule_node_get_type(node) != isl_schedule_node_domain)
497 isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
498 "root node not a domain node", goto error);
500 node = isl_schedule_node_child(node, 0);
501 anchored = isl_schedule_node_is_subtree_anchored(node);
502 if (anchored < 0)
503 goto error;
504 if (anchored)
505 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
506 "cannot insert band node in anchored subtree",
507 goto error);
508 node = isl_schedule_node_insert_partial_schedule(node, partial);
510 schedule = isl_schedule_node_get_schedule(node);
511 isl_schedule_node_free(node);
513 return schedule;
514 error:
515 isl_schedule_node_free(node);
516 isl_multi_union_pw_aff_free(partial);
517 return NULL;
520 /* Insert a context node with constraints "context" between the domain
521 * root node of "schedule" and its single child.
522 * Return a pointer to the updated schedule.
524 __isl_give isl_schedule *isl_schedule_insert_context(
525 __isl_take isl_schedule *schedule, __isl_take isl_set *context)
527 isl_schedule_node *node;
529 node = isl_schedule_get_root(schedule);
530 isl_schedule_free(schedule);
531 node = isl_schedule_node_child(node, 0);
532 node = isl_schedule_node_insert_context(node, context);
533 schedule = isl_schedule_node_get_schedule(node);
534 isl_schedule_node_free(node);
536 return schedule;
539 /* Insert a guard node with constraints "guard" between the domain
540 * root node of "schedule" and its single child.
541 * Return a pointer to the updated schedule.
543 __isl_give isl_schedule *isl_schedule_insert_guard(
544 __isl_take isl_schedule *schedule, __isl_take isl_set *guard)
546 isl_schedule_node *node;
548 node = isl_schedule_get_root(schedule);
549 isl_schedule_free(schedule);
550 node = isl_schedule_node_child(node, 0);
551 node = isl_schedule_node_insert_guard(node, guard);
552 schedule = isl_schedule_node_get_schedule(node);
553 isl_schedule_node_free(node);
555 return schedule;
558 /* Return a tree with as top-level node a filter corresponding to "filter" and
559 * as child, the (single) child of "tree".
560 * However, if this single child is of type "type", then the filter is inserted
561 * in the children of this single child instead.
563 static __isl_give isl_schedule_tree *insert_filter_in_child_of_type(
564 __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter,
565 enum isl_schedule_node_type type)
567 if (!isl_schedule_tree_has_children(tree)) {
568 isl_schedule_tree_free(tree);
569 return isl_schedule_tree_from_filter(filter);
570 } else {
571 tree = isl_schedule_tree_child(tree, 0);
574 if (isl_schedule_tree_get_type(tree) == type)
575 tree = isl_schedule_tree_children_insert_filter(tree, filter);
576 else
577 tree = isl_schedule_tree_insert_filter(tree, filter);
579 return tree;
582 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
583 * with a top-level node (underneath the domain node) of type "type",
584 * either isl_schedule_node_sequence or isl_schedule_node_set.
585 * The domains of the two schedules are assumed to be disjoint.
587 * The new schedule has as domain the union of the domains of the two
588 * schedules. The child of the domain node is a node of type "type"
589 * with two filters corresponding to the domains of the input schedules.
590 * If one (or both) of the top-level nodes of the two schedules is itself
591 * of type "type", then the filter is pushed into the children of that
592 * node and the sequence of set is flattened.
594 __isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type,
595 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
597 int disjoint;
598 isl_ctx *ctx;
599 enum isl_schedule_node_type root_type;
600 isl_schedule_tree *tree1, *tree2;
601 isl_union_set *filter1, *filter2, *domain;
603 if (!schedule1 || !schedule2)
604 goto error;
606 root_type = isl_schedule_tree_get_type(schedule1->root);
607 if (root_type != isl_schedule_node_domain)
608 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
609 "root node not a domain node", goto error);
610 root_type = isl_schedule_tree_get_type(schedule2->root);
611 if (root_type != isl_schedule_node_domain)
612 isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
613 "root node not a domain node", goto error);
615 ctx = isl_schedule_get_ctx(schedule1);
616 tree1 = isl_schedule_tree_copy(schedule1->root);
617 filter1 = isl_schedule_tree_domain_get_domain(tree1);
618 tree2 = isl_schedule_tree_copy(schedule2->root);
619 filter2 = isl_schedule_tree_domain_get_domain(tree2);
621 isl_schedule_free(schedule1);
622 isl_schedule_free(schedule2);
624 disjoint = isl_union_set_is_disjoint(filter1, filter2);
625 if (disjoint < 0)
626 filter1 = isl_union_set_free(filter1);
627 if (!disjoint)
628 isl_die(ctx, isl_error_invalid,
629 "schedule domains not disjoint",
630 filter1 = isl_union_set_free(filter1));
632 domain = isl_union_set_union(isl_union_set_copy(filter1),
633 isl_union_set_copy(filter2));
634 filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain));
635 filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain));
637 tree1 = insert_filter_in_child_of_type(tree1, filter1, type);
638 tree2 = insert_filter_in_child_of_type(tree2, filter2, type);
640 tree1 = isl_schedule_tree_from_pair(type, tree1, tree2);
641 tree1 = isl_schedule_tree_insert_domain(tree1, domain);
643 return isl_schedule_from_schedule_tree(ctx, tree1);
644 error:
645 isl_schedule_free(schedule1);
646 isl_schedule_free(schedule2);
647 return NULL;
650 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
651 * through a sequence node.
652 * The domains of the input schedules are assumed to be disjoint.
654 __isl_give isl_schedule *isl_schedule_sequence(
655 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
657 return isl_schedule_pair(isl_schedule_node_sequence,
658 schedule1, schedule2);
661 /* Construct a schedule that combines the schedules "schedule1" and "schedule2"
662 * through a set node.
663 * The domains of the input schedules are assumed to be disjoint.
665 __isl_give isl_schedule *isl_schedule_set(
666 __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
668 return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2);
671 /* Print "schedule" to "p".
673 __isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
674 __isl_keep isl_schedule *schedule)
676 if (!schedule)
677 return isl_printer_free(p);
679 return isl_printer_print_schedule_tree(p, schedule->root);
682 #undef BASE
683 #define BASE schedule
684 #include <print_templ_yaml.c>