summaryloggraphiclog1graphiclog2commitcommitdifftreerefseditfork
rawpatchinlineside by side (parent: a6d1ff0)
rawpatchinlineside by side (parent: a6d1ff0)
| author | Sven Verdoolaege <skimo@kotnet.org> | |
| Mon, 2 Jun 2014 11:11:07 +0000 (2 13:11 +0200) | ||
| committer | Sven Verdoolaege <skimo@kotnet.org> | |
| Mon, 16 Mar 2015 09:47:28 +0000 (16 10:47 +0100) |
This new node type allows the user to express constraints that need
to be enforced by outer AST nodes at a given point in the schedule tree,
ensuring that the AST corresponding to the descendants in the schedule tree
is never executed if the constraints are not satisfied.
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
to be enforced by outer AST nodes at a given point in the schedule tree,
ensuring that the AST corresponding to the descendants in the schedule tree
is never executed if the constraints are not satisfied.
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
diff --git a/doc/user.pod b/doc/user.pod
--- a/doc/user.pod
+++ b/doc/user.pod
=back
-The following node type is only supported by the AST generator.
+The following node types are only supported by the AST generator.
=over
Since a context node references the outer band nodes, any tree
containing a context node is considered to be anchored.
+=item C<isl_schedule_node_guard>
+
+The guard describes constraints on the parameters and
+the schedule dimensions of outer
+bands that need to be enforced by the outer nodes
+in the generated AST.
+The space of the guard is that of the flat product of the outer
+band nodes. In particular, if there are no outer band nodes, then
+this space is the unnamed zero-dimensional space.
+Since a guard node references the outer band nodes, any tree
+containing a guard node is considered to be anchored.
+
=back
Except for the C<isl_schedule_node_context> nodes,
__isl_keep isl_schedule_node *node);
#include <isl/schedule_node.h>
+ __isl_give isl_set *isl_schedule_node_guard_get_guard(
+ __isl_keep isl_schedule_node *node);
+
+ #include <isl/schedule_node.h>
__isl_give isl_id *isl_schedule_node_mark_get_id(
__isl_keep isl_schedule_node *node);
#include <isl/schedule_node.h>
__isl_give isl_schedule_node *
+ isl_schedule_node_insert_guard(
+ __isl_take isl_schedule_node *node,
+ __isl_take isl_set *guard);
+
+This function inserts a new guard node with the given guard constraints.
+
+ #include <isl/schedule_node.h>
+ __isl_give isl_schedule_node *
isl_schedule_node_insert_mark(
__isl_take isl_schedule_node *node,
__isl_take isl_id *mark);
__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_set *isl_schedule_node_guard_get_guard(
+ __isl_keep isl_schedule_node *node);
__isl_give isl_id *isl_schedule_node_mark_get_id(
__isl_keep isl_schedule_node *node);
__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_guard(
+ __isl_take isl_schedule_node *node, __isl_take isl_set *context);
__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_schedule_node_expansion,
isl_schedule_node_filter,
isl_schedule_node_leaf,
+ isl_schedule_node_guard,
isl_schedule_node_mark,
isl_schedule_node_sequence,
isl_schedule_node_set
diff --git a/isl_ast_codegen.c b/isl_ast_codegen.c
--- a/isl_ast_codegen.c
+++ b/isl_ast_codegen.c
return after_in_expansion(umap, node);
case isl_schedule_node_filter:
return after_in_filter(umap, node);
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
return after_in_child(umap, node);
case isl_schedule_node_set:
return NULL;
}
+/* Generate an AST that visits the elements in the domain of "executed"
+ * in the relative order specified by the guard node "node" and
+ * its descendants.
+ *
+ * The relation "executed" maps the outer generated loop iterators
+ * to the domain elements executed by those iterations.
+ *
+ * Ensure that the associated guard is enforced by the outer AST
+ * constructs by adding it to the guard of the graft.
+ * Since we know that we will enforce the guard, we can also include it
+ * in the generated constraints used to construct an AST for
+ * the descendant nodes.
+ */
+static __isl_give isl_ast_graft_list *build_ast_from_guard(
+ __isl_take isl_ast_build *build, __isl_take isl_schedule_node *node,
+ __isl_take isl_union_map *executed)
+{
+ isl_space *space;
+ isl_set *guard, *hoisted;
+ isl_basic_set *enforced;
+ isl_ast_build *sub_build;
+ isl_ast_graft *graft;
+ isl_ast_graft_list *list;
+ unsigned n1, n2;
+
+ space = isl_ast_build_get_space(build, 1);
+ guard = isl_schedule_node_guard_get_guard(node);
+ n1 = isl_space_dim(space, isl_dim_param);
+ guard = isl_set_align_params(guard, space);
+ n2 = isl_set_dim(guard, isl_dim_param);
+ if (n2 > n1)
+ isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
+ "guard node is not allowed to introduce "
+ "new parameters", guard = isl_set_free(guard));
+ guard = isl_set_preimage_multi_aff(guard,
+ isl_multi_aff_copy(build->internal2input));
+ guard = isl_ast_build_specialize(build, guard);
+ guard = isl_set_gist(guard, isl_set_copy(build->generated));
+
+ sub_build = isl_ast_build_copy(build);
+ sub_build = isl_ast_build_restrict_generated(sub_build,
+ isl_set_copy(guard));
+
+ list = build_ast_from_child(isl_ast_build_copy(sub_build),
+ node, executed);
+
+ hoisted = isl_ast_graft_list_extract_hoistable_guard(list, sub_build);
+ if (isl_set_n_basic_set(hoisted) > 1)
+ list = isl_ast_graft_list_gist_guards(list,
+ isl_set_copy(hoisted));
+ guard = isl_set_intersect(guard, hoisted);
+ enforced = extract_shared_enforced(list, build);
+ graft = isl_ast_graft_alloc_from_children(list, guard, enforced,
+ build, sub_build);
+
+ isl_ast_build_free(sub_build);
+ isl_ast_build_free(build);
+ return isl_ast_graft_list_from_ast_graft(graft);
+}
+
/* Call the before_each_mark callback, if requested by the user.
*
* Return 0 on success and -1 on error.
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_guard:
+ return build_ast_from_guard(build, node, executed);
case isl_schedule_node_mark:
return build_ast_from_mark(build, node, executed);
case isl_schedule_node_sequence:
diff --git a/isl_schedule.c b/isl_schedule.c
--- a/isl_schedule.c
+++ b/isl_schedule.c
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_guard:
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
+ "guard nodes not supported", goto error);
case isl_schedule_node_mark:
isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
"mark nodes not supported", goto error);
diff --git a/isl_schedule_node.c b/isl_schedule_node.c
--- a/isl_schedule_node.c
+++ b/isl_schedule_node.c
"should be handled by caller", return -1);
case isl_schedule_node_context:
case isl_schedule_node_leaf:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_set:
"should be handled by caller", return -1);
case isl_schedule_node_context:
case isl_schedule_node_leaf:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_set:
return NULL;
}
+/* Return the guard of the guard node "node".
+ */
+__isl_give isl_set *isl_schedule_node_guard_get_guard(
+ __isl_keep isl_schedule_node *node)
+{
+ if (!node)
+ return NULL;
+
+ return isl_schedule_tree_guard_get_guard(node->tree);
+}
+
/* Return the mark identifier of the mark node "node".
*/
__isl_give isl_id *isl_schedule_node_mark_get_id(
return node;
}
+/* Insert a guard node with guard "guard" between "node" and its parent.
+ * Return a pointer to the new guard node.
+ */
+__isl_give isl_schedule_node *isl_schedule_node_insert_guard(
+ __isl_take isl_schedule_node *node, __isl_take isl_set *guard)
+{
+ 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_guard(tree, guard);
+ node = isl_schedule_node_graft_tree(node, tree);
+
+ return node;
+}
+
/* Insert a mark node with mark identifier "mark" between "node" and
* its parent.
* Return a pointer to the new mark node.
data->finished = 1;
break;
case isl_schedule_node_leaf:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_set:
case isl_schedule_node_band:
case isl_schedule_node_context:
case isl_schedule_node_domain:
+ case isl_schedule_node_guard:
case isl_schedule_node_leaf:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
break;
case isl_schedule_node_context:
case isl_schedule_node_domain:
+ case isl_schedule_node_guard:
case isl_schedule_node_leaf:
case isl_schedule_node_mark:
break;
case isl_schedule_node_band:
case isl_schedule_node_context:
case isl_schedule_node_domain:
+ case isl_schedule_node_guard:
case isl_schedule_node_leaf:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_context:
case isl_schedule_node_domain:
case isl_schedule_node_expansion:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_set:
case isl_schedule_node_band:
case isl_schedule_node_context:
case isl_schedule_node_domain:
+ case isl_schedule_node_guard:
case isl_schedule_node_leaf:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_context:
case isl_schedule_node_domain:
case isl_schedule_node_expansion:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_set:
diff --git a/isl_schedule_read.c b/isl_schedule_read.c
--- a/isl_schedule_read.c
+++ b/isl_schedule_read.c
isl_schedule_key_domain,
isl_schedule_key_expansion,
isl_schedule_key_filter,
+ isl_schedule_key_guard,
isl_schedule_key_leaf,
isl_schedule_key_mark,
isl_schedule_key_options,
key = isl_schedule_key_expansion;
else if (!strcmp(name, "filter"))
key = isl_schedule_key_filter;
+ else if (!strcmp(name, "guard"))
+ key = isl_schedule_key_guard;
else if (!strcmp(name, "leaf"))
key = isl_schedule_key_leaf;
else if (!strcmp(name, "mark"))
return NULL;
}
+/* Read a subtree with guard root node from "s".
+ */
+static __isl_give isl_schedule_tree *read_guard(isl_stream *s)
+{
+ isl_set *guard = NULL;
+ 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);
+ guard = isl_set_read_from_str(ctx, str);
+ free(str);
+ isl_token_free(tok);
+
+ more = isl_stream_yaml_next(s);
+ if (more < 0)
+ goto error;
+ if (!more) {
+ tree = isl_schedule_tree_from_guard(guard);
+ } 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_guard(tree, guard);
+ }
+
+ return tree;
+error:
+ isl_set_free(guard);
+ return NULL;
+}
+
/* Read a subtree with mark root node from "s".
*/
static __isl_give isl_schedule_tree *read_mark(isl_stream *s)
case isl_schedule_key_filter:
tree = read_filter(s);
break;
+ case isl_schedule_key_guard:
+ tree = read_guard(s);
+ break;
case isl_schedule_key_leaf:
isl_token_free(isl_stream_next_token(s));
tree = isl_schedule_tree_leaf(isl_stream_get_ctx(s));
diff --git a/isl_schedule_tree.c b/isl_schedule_tree.c
--- a/isl_schedule_tree.c
+++ b/isl_schedule_tree.c
if (!dup->filter)
return isl_schedule_tree_free(dup);
break;
+ case isl_schedule_node_guard:
+ dup->guard = isl_set_copy(tree->guard);
+ if (!dup->guard)
+ return isl_schedule_tree_free(dup);
+ break;
case isl_schedule_node_mark:
dup->mark = isl_id_copy(tree->mark);
if (!dup->mark)
case isl_schedule_node_filter:
isl_union_set_free(tree->filter);
break;
+ case isl_schedule_node_guard:
+ isl_set_free(tree->guard);
+ break;
case isl_schedule_node_mark:
isl_id_free(tree->mark);
break;
return NULL;
}
+/* Create a new guard schedule tree with the given guard and no children.
+ * Since the guard references the outer schedule dimension,
+ * the tree is anchored.
+ */
+__isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
+ __isl_take isl_set *guard)
+{
+ isl_ctx *ctx;
+ isl_schedule_tree *tree;
+
+ if (!guard)
+ return NULL;
+
+ ctx = isl_set_get_ctx(guard);
+ tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
+ if (!tree)
+ goto error;
+
+ tree->guard = guard;
+ tree->anchored = 1;
+
+ return tree;
+error:
+ isl_set_free(guard);
+ return NULL;
+}
+
/* Create a new mark schedule tree with the given mark identifier and
* no children.
*/
/* Does the root node of "tree" depend on its position in the complete
* schedule tree?
* Band nodes may be anchored depending on the associated AST build options.
- * Context nodes are always anchored.
+ * Context and guard nodes are always anchored.
*/
int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
{
case isl_schedule_node_band:
return isl_schedule_band_is_anchored(tree->band);
case isl_schedule_node_context:
+ case isl_schedule_node_guard:
return 1;
case isl_schedule_node_domain:
case isl_schedule_node_expansion:
case isl_schedule_node_filter:
equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
break;
+ case isl_schedule_node_guard:
+ equal = isl_set_is_equal(tree1->guard, tree2->guard);
+ break;
case isl_schedule_node_mark:
equal = tree1->mark == tree2->mark;
break;
return NULL;
}
+/* Create a new guard schedule tree with the given guard and
+ * with "tree" as single child.
+ */
+__isl_give isl_schedule_tree *isl_schedule_tree_insert_guard(
+ __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard)
+{
+ isl_schedule_tree *res;
+
+ res = isl_schedule_tree_from_guard(guard);
+ return isl_schedule_tree_replace_child(res, 0, tree);
+}
+
/* Create a new mark schedule tree with the given mark identifier and
* single child.
*/
return NULL;
}
+/* Return the guard of the guard tree root.
+ */
+__isl_give isl_set *isl_schedule_tree_guard_get_guard(
+ __isl_take isl_schedule_tree *tree)
+{
+ if (!tree)
+ return NULL;
+
+ if (tree->type != isl_schedule_node_guard)
+ isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
+ "not a guard node", return NULL);
+
+ return isl_set_copy(tree->guard);
+}
+
/* Return the mark identifier of the mark tree root "tree".
*/
__isl_give isl_id *isl_schedule_tree_mark_get_id(
case isl_schedule_node_band:
return isl_schedule_tree_band_n_member(tree) == 0;
case isl_schedule_node_context:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
return 1;
case isl_schedule_node_leaf:
case isl_schedule_node_error:
return isl_union_map_free(outer);
case isl_schedule_node_context:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
return subtree_schedule_extend_child(tree, outer);
case isl_schedule_node_band:
isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
"context node should be handled by caller",
return NULL);
+ case isl_schedule_node_guard:
+ isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
+ "guard 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",
if (!tree->filter)
return isl_schedule_tree_free(tree);
break;
+ case isl_schedule_node_guard:
+ tree->guard = isl_set_reset_user(tree->guard);
+ if (!tree->guard)
+ return isl_schedule_tree_free(tree);
+ break;
case isl_schedule_node_leaf:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
if (!tree->filter)
return isl_schedule_tree_free(tree);
break;
+ case isl_schedule_node_guard:
+ tree->guard = isl_set_align_params(tree->guard, space);
+ if (!tree->guard)
+ return isl_schedule_tree_free(tree);
+ break;
case isl_schedule_node_leaf:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
return 1;
case isl_schedule_node_context:
case isl_schedule_node_leaf:
+ case isl_schedule_node_guard:
case isl_schedule_node_mark:
case isl_schedule_node_sequence:
case isl_schedule_node_set:
p = isl_printer_print_union_set(p, tree->filter);
p = isl_printer_print_str(p, "\"");
break;
+ case isl_schedule_node_guard:
+ p = isl_printer_print_str(p, "guard");
+ p = isl_printer_yaml_next(p);
+ p = isl_printer_print_str(p, "\"");
+ p = isl_printer_print_set(p, tree->guard);
+ 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);
diff --git a/isl_schedule_tree.h b/isl_schedule_tree.h
--- a/isl_schedule_tree.h
+++ b/isl_schedule_tree.h
* The "filter" field is valid when type is isl_schedule_node_filter
* and represents the statement instances selected by the node.
*
+ * The "guard" field is valid when type is isl_schedule_node_guard
+ * and represents constraints on the flat product of the outer band nodes
+ * that need to be enforced by the outer nodes in the generated AST.
+ *
* The "mark" field is valid when type is isl_schedule_node_mark and
* identifies the mark.
*
isl_union_map *expansion;
};
isl_union_set *filter;
+ isl_set *guard;
isl_id *mark;
};
isl_schedule_tree_list *children;
__isl_take isl_union_map *expansion);
__isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
__isl_take isl_union_set *filter);
+__isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
+ __isl_take isl_set *guard);
__isl_give isl_schedule_tree *isl_schedule_tree_from_children(
enum isl_schedule_node_type type,
__isl_take isl_schedule_tree_list *list);
__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_set *isl_schedule_tree_guard_get_guard(
+ __isl_keep isl_schedule_tree *tree);
__isl_give isl_id *isl_schedule_tree_mark_get_id(
__isl_keep isl_schedule_tree *tree);
__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_guard(
+ __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard);
__isl_give isl_schedule_tree *isl_schedule_tree_insert_mark(
__isl_take isl_schedule_tree *tree, __isl_take isl_id *mark);