From e0c7347d2812659a4beaf746d2ab5a995634db17 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 29 Nov 2013 19:03:22 +0100 Subject: [PATCH] add isl_schedule_sequence and isl_schedule_set Signed-off-by: Sven Verdoolaege --- doc/user.pod | 15 +++++++ include/isl/schedule.h | 4 ++ isl_schedule.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++ isl_schedule_tree.c | 69 ++++++++++++++++++++++++++++++ isl_schedule_tree.h | 5 +++ 5 files changed, 206 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index c9031286..9293acca 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -7309,6 +7309,21 @@ be introduced into the schedule using the following function. __isl_take isl_schedule *schedule, __isl_take isl_multi_union_pw_aff *partial); +A schedule that combines two schedules either in the given +order or in an arbitrary order, i.e., with an C +or an C node, +can be created using the following functions. + + #include + __isl_give isl_schedule *isl_schedule_sequence( + __isl_take isl_schedule *schedule1, + __isl_take isl_schedule *schedule2); + __isl_give isl_schedule *isl_schedule_set( + __isl_take isl_schedule *schedule1, + __isl_take isl_schedule *schedule2); + +The domains of the two input schedules need to be disjoint. + An C representation of the schedule can be obtained from an C using the following function. diff --git a/include/isl/schedule.h b/include/isl/schedule.h index 86cbc6c0..e9257671 100644 --- a/include/isl/schedule.h +++ b/include/isl/schedule.h @@ -101,6 +101,10 @@ __isl_give isl_schedule *isl_schedule_map_schedule_node( __isl_give isl_schedule *isl_schedule_insert_partial_schedule( __isl_take isl_schedule *schedule, __isl_take isl_multi_union_pw_aff *partial); +__isl_give isl_schedule *isl_schedule_sequence( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2); +__isl_give isl_schedule *isl_schedule_set( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2); __isl_give isl_band_list *isl_schedule_get_band_forest( __isl_keep isl_schedule *schedule); diff --git a/isl_schedule.c b/isl_schedule.c index 8eae0d18..21abc85e 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -782,6 +782,119 @@ error: return NULL; } +/* Return a tree with as top-level node a filter corresponding to "filter" and + * as child, the (single) child of "tree". + * However, if this single child is of type "type", then the filter is inserted + * in the children of this single child instead. + */ +static __isl_give isl_schedule_tree *insert_filter_in_child_of_type( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter, + enum isl_schedule_node_type type) +{ + if (!isl_schedule_tree_has_children(tree)) { + isl_schedule_tree_free(tree); + return isl_schedule_tree_from_filter(filter); + } else { + tree = isl_schedule_tree_child(tree, 0); + } + + if (isl_schedule_tree_get_type(tree) == type) + tree = isl_schedule_tree_children_insert_filter(tree, filter); + else + tree = isl_schedule_tree_insert_filter(tree, filter); + + return tree; +} + +/* Construct a schedule that combines the schedules "schedule1" and "schedule2" + * with a top-level node (underneath the domain node) of type "type", + * either isl_schedule_node_sequence or isl_schedule_node_set. + * The domains of the two schedules are assumed to be disjoint. + * + * The new schedule has as domain the union of the domains of the two + * schedules. The child of the domain node is a node of type "type" + * with two filters corresponding to the domains of the input schedules. + * If one (or both) of the top-level nodes of the two schedules is itself + * of type "type", then the filter is pushed into the children of that + * node and the sequence of set is flattened. + */ +__isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type, + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) +{ + int disjoint; + isl_ctx *ctx; + enum isl_schedule_node_type root_type; + isl_schedule_tree *tree1, *tree2; + isl_union_set *filter1, *filter2, *domain; + + if (!schedule1 || !schedule2) + goto error; + + root_type = isl_schedule_tree_get_type(schedule1->root); + if (root_type != isl_schedule_node_domain) + isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal, + "root node not a domain node", goto error); + root_type = isl_schedule_tree_get_type(schedule2->root); + if (root_type != isl_schedule_node_domain) + isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal, + "root node not a domain node", goto error); + + ctx = isl_schedule_get_ctx(schedule1); + tree1 = isl_schedule_tree_copy(schedule1->root); + filter1 = isl_schedule_tree_domain_get_domain(tree1); + tree2 = isl_schedule_tree_copy(schedule2->root); + filter2 = isl_schedule_tree_domain_get_domain(tree2); + + isl_schedule_free(schedule1); + isl_schedule_free(schedule2); + + disjoint = isl_union_set_is_disjoint(filter1, filter2); + if (disjoint < 0) + filter1 = isl_union_set_free(filter1); + if (!disjoint) + isl_die(ctx, isl_error_invalid, + "schedule domains not disjoint", + filter1 = isl_union_set_free(filter1)); + + domain = isl_union_set_union(isl_union_set_copy(filter1), + isl_union_set_copy(filter2)); + filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain)); + filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain)); + + tree1 = insert_filter_in_child_of_type(tree1, filter1, type); + tree2 = insert_filter_in_child_of_type(tree2, filter2, type); + + tree1 = isl_schedule_tree_from_pair(type, tree1, tree2); + tree1 = isl_schedule_tree_insert_domain(tree1, domain); + + return isl_schedule_from_schedule_tree(ctx, tree1); +error: + isl_schedule_free(schedule1); + isl_schedule_free(schedule2); + return NULL; +} + +/* Construct a schedule that combines the schedules "schedule1" and "schedule2" + * through a sequence node. + * The domains of the input schedules are assumed to be disjoint. + */ +__isl_give isl_schedule *isl_schedule_sequence( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) +{ + return isl_schedule_pair(isl_schedule_node_sequence, + schedule1, schedule2); +} + +/* Construct a schedule that combines the schedules "schedule1" and "schedule2" + * through a set node. + * The domains of the input schedules are assumed to be disjoint. + */ +__isl_give isl_schedule *isl_schedule_set( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) +{ + return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2); +} + /* Print "schedule" to "p". * * If "schedule" was created from a schedule tree, then we print diff --git a/isl_schedule_tree.c b/isl_schedule_tree.c index a12f4699..36de3c3a 100644 --- a/isl_schedule_tree.c +++ b/isl_schedule_tree.c @@ -286,6 +286,46 @@ error: return NULL; } +/* Construct a tree with a root node of type "type" and as children + * "tree1" and "tree2". + * If the root of one (or both) of the input trees is itself of type "type", + * then the tree is replaced by its children. + */ +__isl_give isl_schedule_tree *isl_schedule_tree_from_pair( + enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1, + __isl_take isl_schedule_tree *tree2) +{ + isl_ctx *ctx; + isl_schedule_tree_list *list; + + if (!tree1 || !tree2) + goto error; + + ctx = isl_schedule_tree_get_ctx(tree1); + if (isl_schedule_tree_get_type(tree1) == type) { + list = isl_schedule_tree_list_copy(tree1->children); + isl_schedule_tree_free(tree1); + } else { + list = isl_schedule_tree_list_alloc(ctx, 2); + list = isl_schedule_tree_list_add(list, tree1); + } + if (isl_schedule_tree_get_type(tree2) == type) { + isl_schedule_tree_list *children; + + children = isl_schedule_tree_list_copy(tree2->children); + list = isl_schedule_tree_list_concat(list, children); + isl_schedule_tree_free(tree2); + } else { + list = isl_schedule_tree_list_add(list, tree2); + } + + return isl_schedule_tree_from_children(type, list); +error: + isl_schedule_tree_free(tree1); + isl_schedule_tree_free(tree2); + return NULL; +} + /* Return the isl_ctx to which "tree" belongs. */ isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree) @@ -528,6 +568,35 @@ __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter( return isl_schedule_tree_replace_child(res, 0, tree); } +/* Insert a filter node with filter set "filter" + * in each of the children of "tree". + */ +__isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter) +{ + int i, n; + + if (!tree || !filter) + goto error; + + n = isl_schedule_tree_n_children(tree); + for (i = 0; i < n; ++i) { + isl_schedule_tree *child; + + child = isl_schedule_tree_get_child(tree, i); + child = isl_schedule_tree_insert_filter(child, + isl_union_set_copy(filter)); + tree = isl_schedule_tree_replace_child(tree, i, child); + } + + isl_union_set_free(filter); + return tree; +error: + isl_union_set_free(filter); + isl_schedule_tree_free(tree); + return NULL; +} + /* Return the number of members in the band tree root. */ unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree) diff --git a/isl_schedule_tree.h b/isl_schedule_tree.h index 8eed4e65..6f176917 100644 --- a/isl_schedule_tree.h +++ b/isl_schedule_tree.h @@ -66,6 +66,9 @@ __isl_give isl_schedule_tree *isl_schedule_tree_from_filter( __isl_give isl_schedule_tree *isl_schedule_tree_from_children( enum isl_schedule_node_type type, __isl_take isl_schedule_tree_list *list); +__isl_give isl_schedule_tree *isl_schedule_tree_from_pair( + enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1, + __isl_take isl_schedule_tree *tree2); __isl_give isl_space *isl_schedule_tree_band_get_space( __isl_keep isl_schedule_tree *tree); @@ -106,6 +109,8 @@ __isl_give isl_schedule_tree *isl_schedule_tree_insert_domain( __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain); __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter( __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter); +__isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter); __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves( __isl_take isl_schedule_tree *tree1, -- 2.11.4.GIT