From 1eef3e6ef68283f8cae64cb3e69d4bd817696b1e Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 16 Jul 2014 19:06:48 +0200 Subject: [PATCH] add isl_schedule_node_mark This allows the user to attach arbitrary information to a subtree of a schedule tree. Signed-off-by: Sven Verdoolaege --- doc/user.pod | 17 ++++++++++ include/isl/schedule_node.h | 4 +++ include/isl/schedule_type.h | 1 + isl_ast_codegen.c | 42 ++++++++++++++++++++++++ isl_ast_graft.c | 19 +++++++++++ isl_ast_graft_private.h | 3 ++ isl_schedule.c | 3 ++ isl_schedule_node.c | 39 ++++++++++++++++++++++ isl_schedule_read.c | 58 ++++++++++++++++++++++++++++++++ isl_schedule_tree.c | 80 +++++++++++++++++++++++++++++++++++++++++++++ isl_schedule_tree.h | 8 +++++ 11 files changed, 274 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index a3ff4f85..aace48eb 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -7271,6 +7271,11 @@ set node. A leaf of the schedule tree. Leaf nodes do not impose any ordering. +=item C + +A mark node can be used to attach any kind of information to a subtree +of the schedule tree. + =item C A sequence node has one or more children, each of which is a filter node. @@ -7767,6 +7772,10 @@ See L. isl_schedule_node_filter_get_filter( __isl_keep isl_schedule_node *node); + #include + __isl_give isl_id *isl_schedule_node_mark_get_id( + __isl_keep isl_schedule_node *node); + The following functions can be used to obtain an C, an C or C representation of partial schedules related to the node. @@ -7866,6 +7875,14 @@ two filter nodes are merged into one. #include __isl_give isl_schedule_node * + isl_schedule_node_insert_mark( + __isl_take isl_schedule_node *node, + __isl_take isl_id *mark); + +This function inserts a new mark node with the give mark identifier. + + #include + __isl_give isl_schedule_node * isl_schedule_node_insert_sequence( __isl_take isl_schedule_node *node, __isl_take isl_union_set_list *filters); diff --git a/include/isl/schedule_node.h b/include/isl/schedule_node.h index 4fa354fc..7d0842c8 100644 --- a/include/isl/schedule_node.h +++ b/include/isl/schedule_node.h @@ -132,6 +132,8 @@ __isl_give isl_union_pw_multi_aff *isl_schedule_node_expansion_get_contraction( __isl_keep isl_schedule_node *node); __isl_give isl_union_set *isl_schedule_node_filter_get_filter( __isl_keep isl_schedule_node *node); +__isl_give isl_id *isl_schedule_node_mark_get_id( + __isl_keep isl_schedule_node *node); int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node *node); __isl_give isl_union_set *isl_schedule_node_get_domain( @@ -160,6 +162,8 @@ __isl_give isl_schedule_node *isl_schedule_node_insert_partial_schedule( __isl_take isl_multi_union_pw_aff *schedule); __isl_give isl_schedule_node *isl_schedule_node_insert_filter( __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter); +__isl_give isl_schedule_node *isl_schedule_node_insert_mark( + __isl_take isl_schedule_node *node, __isl_take isl_id *mark); __isl_give isl_schedule_node *isl_schedule_node_insert_sequence( __isl_take isl_schedule_node *node, __isl_take isl_union_set_list *filters); diff --git a/include/isl/schedule_type.h b/include/isl/schedule_type.h index 1c90f806..26c38258 100644 --- a/include/isl/schedule_type.h +++ b/include/isl/schedule_type.h @@ -13,6 +13,7 @@ enum isl_schedule_node_type { isl_schedule_node_expansion, isl_schedule_node_filter, isl_schedule_node_leaf, + isl_schedule_node_mark, isl_schedule_node_sequence, isl_schedule_node_set }; diff --git a/isl_ast_codegen.c b/isl_ast_codegen.c index 09ebe7d2..ae089dee 100644 --- a/isl_ast_codegen.c +++ b/isl_ast_codegen.c @@ -4287,6 +4287,8 @@ static int after_in_tree(__isl_keep isl_union_map *umap, return after_in_expansion(umap, node); case isl_schedule_node_filter: return after_in_filter(umap, node); + case isl_schedule_node_mark: + return after_in_child(umap, node); case isl_schedule_node_set: return after_in_set(umap, node); case isl_schedule_node_sequence: @@ -5089,6 +5091,44 @@ error: return NULL; } +/* Generate an AST that visits the elements in the domain of "executed" + * in the relative order specified by the mark node "node" and + * its descendants. + * + * The relation "executed" maps the outer generated loop iterators + * to the domain elements executed by those iterations. + * + * We generate an AST for the child of the mark node, combine + * the graft list into a single graft and then insert the mark + * in the AST of that single graft. + */ +static __isl_give isl_ast_graft_list *build_ast_from_mark( + __isl_take isl_ast_build *build, __isl_take isl_schedule_node *node, + __isl_take isl_union_map *executed) +{ + isl_id *mark; + isl_ast_graft *graft; + isl_ast_graft_list *list; + int n; + + mark = isl_schedule_node_mark_get_id(node); + list = build_ast_from_child(isl_ast_build_copy(build), node, executed); + list = isl_ast_graft_list_fuse(list, build); + isl_ast_build_free(build); + n = isl_ast_graft_list_n_ast_graft(list); + if (n < 0) + list = isl_ast_graft_list_free(list); + if (n == 0) { + isl_id_free(mark); + } else { + graft = isl_ast_graft_list_get_ast_graft(list, 0); + graft = isl_ast_graft_insert_mark(graft, mark); + list = isl_ast_graft_list_set_ast_graft(list, 0, graft); + } + + return list; +} + static __isl_give isl_ast_graft_list *build_ast_from_schedule_node( __isl_take isl_ast_build *build, __isl_take isl_schedule_node *node, __isl_take isl_union_map *executed); @@ -5172,6 +5212,8 @@ static __isl_give isl_ast_graft_list *build_ast_from_schedule_node( return build_ast_from_expansion(build, node, executed); case isl_schedule_node_filter: return build_ast_from_filter(build, node, executed); + case isl_schedule_node_mark: + return build_ast_from_mark(build, node, executed); case isl_schedule_node_sequence: case isl_schedule_node_set: return build_ast_from_sequence(build, node, executed); diff --git a/isl_ast_graft.c b/isl_ast_graft.c index 4b3bd111..e7367295 100644 --- a/isl_ast_graft.c +++ b/isl_ast_graft.c @@ -960,6 +960,25 @@ error: return NULL; } +/* Insert a mark governing the current graft->node. + */ +__isl_give isl_ast_graft *isl_ast_graft_insert_mark( + __isl_take isl_ast_graft *graft, __isl_take isl_id *mark) +{ + if (!graft) + goto error; + + graft->node = isl_ast_node_alloc_mark(mark, graft->node); + if (!graft->node) + return isl_ast_graft_free(graft); + + return graft; +error: + isl_id_free(mark); + isl_ast_graft_free(graft); + return NULL; +} + /* Represent the graft list as an AST node. * This operation drops the information about guards in the grafts, so * if there are any pending guards, then they are materialized as if nodes. diff --git a/isl_ast_graft_private.h b/isl_ast_graft_private.h index 5dc141e2..400b9a88 100644 --- a/isl_ast_graft_private.h +++ b/isl_ast_graft_private.h @@ -76,6 +76,9 @@ __isl_give isl_ast_graft *isl_ast_graft_add_guard( __isl_give isl_ast_graft *isl_ast_graft_enforce( __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced); +__isl_give isl_ast_graft *isl_ast_graft_insert_mark( + __isl_take isl_ast_graft *graft, __isl_take isl_id *mark); + __isl_give isl_ast_graft_list *isl_ast_graft_list_unembed( __isl_take isl_ast_graft_list *list, int product); __isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff( diff --git a/isl_schedule.c b/isl_schedule.c index 3581a4a2..5e3f71c6 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -744,6 +744,9 @@ static __isl_give isl_band_list *construct_band_list( domain = isl_union_set_intersect(domain, filter); node = isl_schedule_node_child(node, 0); return construct_band_list(node, domain, parent); + case isl_schedule_node_mark: + isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported, + "mark nodes not supported", goto error); case isl_schedule_node_set: ctx = isl_schedule_node_get_ctx(node); if (isl_options_get_schedule_separate_components(ctx)) diff --git a/isl_schedule_node.c b/isl_schedule_node.c index ddb3f65f..871b98aa 100644 --- a/isl_schedule_node.c +++ b/isl_schedule_node.c @@ -396,6 +396,7 @@ static int collect_filter_prefix_init(__isl_keep isl_schedule_tree *tree, "should be handled by caller", return -1); case isl_schedule_node_context: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: return 0; @@ -463,6 +464,7 @@ static int collect_filter_prefix_update(__isl_keep isl_schedule_tree *tree, "should be handled by caller", return -1); case isl_schedule_node_context: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; @@ -1807,6 +1809,17 @@ error: return NULL; } +/* Return the mark identifier of the mark node "node". + */ +__isl_give isl_id *isl_schedule_node_mark_get_id( + __isl_keep isl_schedule_node *node) +{ + if (!node) + return NULL; + + return isl_schedule_tree_mark_get_id(node->tree); +} + /* Update the ancestors of "node" to point to the tree that "node" * now points to. * That is, replace the child in the original parent that corresponds @@ -2029,6 +2042,25 @@ __isl_give isl_schedule_node *isl_schedule_node_insert_filter( return node; } +/* Insert a mark node with mark identifier "mark" between "node" and + * its parent. + * Return a pointer to the new mark node. + */ +__isl_give isl_schedule_node *isl_schedule_node_insert_mark( + __isl_take isl_schedule_node *node, __isl_take isl_id *mark) +{ + isl_schedule_tree *tree; + + if (check_insert(node) < 0) + node = isl_schedule_node_free(node); + + tree = isl_schedule_node_get_tree(node); + tree = isl_schedule_tree_insert_mark(tree, mark); + node = isl_schedule_node_graft_tree(node, tree); + + return node; +} + /* Attach the current subtree of "node" to a sequence of filter tree nodes * with filters described by "filters", attach this sequence * of filter tree nodes as children to a new tree of type "type" and @@ -2535,6 +2567,7 @@ static __isl_give isl_schedule_tree *group_ancestor( data->finished = 1; break; case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; @@ -2789,6 +2822,7 @@ static __isl_give isl_schedule_node *gist_enter( case isl_schedule_node_context: case isl_schedule_node_domain: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: continue; @@ -2913,6 +2947,7 @@ static __isl_give isl_schedule_node *gist_leave( case isl_schedule_node_context: case isl_schedule_node_domain: case isl_schedule_node_leaf: + case isl_schedule_node_mark: break; } @@ -3057,6 +3092,7 @@ static __isl_give isl_schedule_node *subtree_expansion_enter( case isl_schedule_node_context: case isl_schedule_node_domain: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; @@ -3107,6 +3143,7 @@ static __isl_give isl_schedule_node *subtree_expansion_leave( case isl_schedule_node_context: case isl_schedule_node_domain: case isl_schedule_node_expansion: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; @@ -3230,6 +3267,7 @@ static __isl_give isl_schedule_node *subtree_contraction_enter( case isl_schedule_node_context: case isl_schedule_node_domain: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; @@ -3283,6 +3321,7 @@ static __isl_give isl_schedule_node *subtree_contraction_leave( case isl_schedule_node_context: case isl_schedule_node_domain: case isl_schedule_node_expansion: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; diff --git a/isl_schedule_read.c b/isl_schedule_read.c index ff51d83a..be939cff 100644 --- a/isl_schedule_read.c +++ b/isl_schedule_read.c @@ -18,6 +18,7 @@ enum isl_schedule_key { isl_schedule_key_expansion, isl_schedule_key_filter, isl_schedule_key_leaf, + isl_schedule_key_mark, isl_schedule_key_options, isl_schedule_key_permutable, isl_schedule_key_schedule, @@ -60,6 +61,8 @@ static enum isl_schedule_key extract_key(__isl_keep isl_stream *s, key = isl_schedule_key_filter; else if (!strcmp(name, "leaf")) key = isl_schedule_key_leaf; + else if (!strcmp(name, "mark")) + key = isl_schedule_key_mark; else if (!strcmp(name, "options")) key = isl_schedule_key_options; else if (!strcmp(name, "schedule")) @@ -324,6 +327,58 @@ error: return NULL; } +/* Read a subtree with mark root node from "s". + */ +static __isl_give isl_schedule_tree *read_mark(isl_stream *s) +{ + isl_id *mark; + isl_schedule_tree *tree; + isl_ctx *ctx; + struct isl_token *tok; + enum isl_schedule_key key; + char *str; + int more; + + ctx = isl_stream_get_ctx(s); + + key = get_key(s); + + if (isl_stream_yaml_next(s) < 0) + return NULL; + + tok = isl_stream_next_token(s); + if (!tok) { + isl_stream_error(s, NULL, "unexpected EOF"); + return NULL; + } + str = isl_token_get_str(ctx, tok); + mark = isl_id_alloc(ctx, str, NULL); + free(str); + isl_token_free(tok); + + more = isl_stream_yaml_next(s); + if (more < 0) + goto error; + if (!more) { + isl_die(ctx, isl_error_invalid, "expecting child", + goto error); + } else { + key = get_key(s); + if (key != isl_schedule_key_child) + isl_die(ctx, isl_error_invalid, "expecting child", + goto error); + if (isl_stream_yaml_next(s) < 0) + goto error; + tree = isl_stream_read_schedule_tree(s); + tree = isl_schedule_tree_insert_mark(tree, mark); + } + + return tree; +error: + isl_id_free(mark); + return NULL; +} + /* Read a sequence of integers from "s" (representing the coincident * property of a band node). */ @@ -572,6 +627,9 @@ static __isl_give isl_schedule_tree *isl_stream_read_schedule_tree( isl_token_free(isl_stream_next_token(s)); tree = isl_schedule_tree_leaf(isl_stream_get_ctx(s)); break; + case isl_schedule_key_mark: + tree = read_mark(s); + break; case isl_schedule_key_sequence: tree = read_sequence(s); break; diff --git a/isl_schedule_tree.c b/isl_schedule_tree.c index 9849b61f..8f547556 100644 --- a/isl_schedule_tree.c +++ b/isl_schedule_tree.c @@ -107,6 +107,11 @@ __isl_take isl_schedule_tree *isl_schedule_tree_dup( if (!dup->filter) return isl_schedule_tree_free(dup); break; + case isl_schedule_node_mark: + dup->mark = isl_id_copy(tree->mark); + if (!dup->mark) + return isl_schedule_tree_free(dup); + break; case isl_schedule_node_leaf: case isl_schedule_node_sequence: case isl_schedule_node_set: @@ -194,6 +199,9 @@ __isl_null isl_schedule_tree *isl_schedule_tree_free( case isl_schedule_node_filter: isl_union_set_free(tree->filter); break; + case isl_schedule_node_mark: + isl_id_free(tree->mark); + break; case isl_schedule_node_sequence: case isl_schedule_node_set: case isl_schedule_node_error: @@ -343,6 +351,31 @@ error: return NULL; } +/* Create a new mark schedule tree with the given mark identifier and + * no children. + */ +__isl_give isl_schedule_tree *isl_schedule_tree_from_mark( + __isl_take isl_id *mark) +{ + isl_ctx *ctx; + isl_schedule_tree *tree; + + if (!mark) + return NULL; + + ctx = isl_id_get_ctx(mark); + tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark); + if (!tree) + goto error; + + tree->mark = mark; + + return tree; +error: + isl_id_free(mark); + return NULL; +} + /* Does "tree" have any node that depends on its position * in the complete schedule tree? */ @@ -372,6 +405,7 @@ int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree) case isl_schedule_node_expansion: case isl_schedule_node_filter: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: return 0; @@ -536,6 +570,9 @@ int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1, case isl_schedule_node_filter: equal = isl_union_set_is_equal(tree1->filter, tree2->filter); break; + case isl_schedule_node_mark: + equal = tree1->mark == tree2->mark; + break; case isl_schedule_node_leaf: case isl_schedule_node_sequence: case isl_schedule_node_set: @@ -823,6 +860,18 @@ error: return NULL; } +/* Create a new mark schedule tree with the given mark identifier and + * single child. + */ +__isl_give isl_schedule_tree *isl_schedule_tree_insert_mark( + __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark) +{ + isl_schedule_tree *res; + + res = isl_schedule_tree_from_mark(mark); + return isl_schedule_tree_replace_child(res, 0, tree); +} + /* Return the number of members in the band tree root. */ unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree) @@ -1269,6 +1318,21 @@ error: return NULL; } +/* Return the mark identifier of the mark tree root "tree". + */ +__isl_give isl_id *isl_schedule_tree_mark_get_id( + __isl_keep isl_schedule_tree *tree) +{ + if (!tree) + return NULL; + + if (tree->type != isl_schedule_node_mark) + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid, + "not a mark node", return NULL); + + return isl_id_copy(tree->mark); +} + /* Set dim to the range dimension of "map" and abort the search. */ static int set_range_dim(__isl_take isl_map *map, void *user) @@ -1346,6 +1410,7 @@ static int domain_less(__isl_keep isl_schedule_tree *tree) case isl_schedule_node_band: return isl_schedule_tree_band_n_member(tree) == 0; case isl_schedule_node_context: + case isl_schedule_node_mark: return 1; case isl_schedule_node_leaf: case isl_schedule_node_error: @@ -1556,6 +1621,7 @@ static __isl_give isl_union_map *subtree_schedule_extend( case isl_schedule_node_error: return isl_union_map_free(outer); case isl_schedule_node_context: + case isl_schedule_node_mark: return subtree_schedule_extend_child(tree, outer); case isl_schedule_node_band: if (isl_schedule_tree_band_n_member(tree) == 0) @@ -1654,6 +1720,10 @@ static __isl_give isl_union_set *initial_domain( isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal, "context node should be handled by caller", return NULL); + case isl_schedule_node_mark: + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal, + "mark node should be handled by caller", + return NULL); case isl_schedule_node_band: if (isl_schedule_tree_band_n_member(tree) == 0) isl_die(isl_schedule_tree_get_ctx(tree), @@ -1930,6 +2000,7 @@ __isl_give isl_schedule_tree *isl_schedule_tree_reset_user( return isl_schedule_tree_free(tree); break; case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: break; @@ -1988,6 +2059,7 @@ __isl_give isl_schedule_tree *isl_schedule_tree_align_params( return isl_schedule_tree_free(tree); break; case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: isl_space_free(space); @@ -2020,6 +2092,7 @@ static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree) return 1; case isl_schedule_node_context: case isl_schedule_node_leaf: + case isl_schedule_node_mark: case isl_schedule_node_sequence: case isl_schedule_node_set: return 0; @@ -2258,6 +2331,13 @@ __isl_give isl_printer *isl_printer_print_schedule_tree_mark( p = isl_printer_print_union_set(p, tree->filter); p = isl_printer_print_str(p, "\""); break; + case isl_schedule_node_mark: + p = isl_printer_print_str(p, "mark"); + p = isl_printer_yaml_next(p); + p = isl_printer_print_str(p, "\""); + p = isl_printer_print_str(p, isl_id_get_name(tree->mark)); + p = isl_printer_print_str(p, "\""); + break; case isl_schedule_node_band: p = print_tree_band(p, tree->band); break; diff --git a/isl_schedule_tree.h b/isl_schedule_tree.h index ac1254f4..a20ae9bd 100644 --- a/isl_schedule_tree.h +++ b/isl_schedule_tree.h @@ -37,6 +37,9 @@ ISL_DECLARE_LIST(schedule_tree) * The "filter" field is valid when type is isl_schedule_node_filter * and represents the statement instances selected by the node. * + * The "mark" field is valid when type is isl_schedule_node_mark and + * identifies the mark. + * * The "children" field is valid for all types except * isl_schedule_node_leaf. This field is NULL if there are * no children (except for the implicit leaves). @@ -58,6 +61,7 @@ struct isl_schedule_tree { isl_union_map *expansion; }; isl_union_set *filter; + isl_id *mark; }; isl_schedule_tree_list *children; }; @@ -140,6 +144,8 @@ __isl_give isl_union_set *isl_schedule_tree_filter_get_filter( __isl_keep isl_schedule_tree *tree); __isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter( __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter); +__isl_give isl_id *isl_schedule_tree_mark_get_id( + __isl_keep isl_schedule_tree *tree); __isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant( __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf); @@ -175,6 +181,8 @@ __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_insert_mark( + __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark); __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves( __isl_take isl_schedule_tree *tree1, -- 2.11.4.GIT