summaryloggraphiclog1graphiclog2commitcommitdifftreerefseditfork
rawpatchinlineside by side (parent: 4a30976)
rawpatchinlineside by side (parent: 4a30976)
| author | Sven Verdoolaege <skimo@kotnet.org> | |
| Fri, 27 Sep 2013 14:06:27 +0000 (27 16:06 +0200) | ||
| committer | Sven Verdoolaege <skimo@kotnet.org> | |
| Thu, 26 Feb 2015 09:14:15 +0000 (26 10:14 +0100) |
This option is similar to the separation_class option in the case
of schedules represented by a flat schedule map.
The main purpose of this option was the same as that of the new
isolate option, i.e., to be able to separate full tiles from partial
tiles. It was however more general in that it allowed more than
two classes and that it allowed (and required) the user to define
the classes at every level. These extra capabilities are however
more confusing than useful. In the typical use case, each level
separates those iterations that contain any of the special ones
at inner levels from those that contain none of the special ones
at inner levels and this does not generalizes in any obvious way
to more than two classes. The separation_class option would then
allow inconsistent specifications that are resolved in an
undeterministic way. Furthermore, even though the option was
documented as only allowing constraints in terms of earlier
schedule dimension, the implementation would not prevent the
user from specifying constraints involving subsequent dimensions,
instead resolving such constraints in some unspecified way.
Since it is not clear how these issues could be fixed and
since we now have a better alternative, we deprecate
the old separation_class option.
In contrast to other options, the isolate option references
the schedule dimensions of outer band nodes, making it depend
on the position of the band node in the schedule tree.
We therefore refuse to perform some operations on the schedule
tree if they may affect the validity of isolate options.
The user should perform these operations first before applying
an isolate option. In future we may consider updating the isolate
option when these operations are performed.
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
of schedules represented by a flat schedule map.
The main purpose of this option was the same as that of the new
isolate option, i.e., to be able to separate full tiles from partial
tiles. It was however more general in that it allowed more than
two classes and that it allowed (and required) the user to define
the classes at every level. These extra capabilities are however
more confusing than useful. In the typical use case, each level
separates those iterations that contain any of the special ones
at inner levels from those that contain none of the special ones
at inner levels and this does not generalizes in any obvious way
to more than two classes. The separation_class option would then
allow inconsistent specifications that are resolved in an
undeterministic way. Furthermore, even though the option was
documented as only allowing constraints in terms of earlier
schedule dimension, the implementation would not prevent the
user from specifying constraints involving subsequent dimensions,
instead resolving such constraints in some unspecified way.
Since it is not clear how these issues could be fixed and
since we now have a better alternative, we deprecate
the old separation_class option.
In contrast to other options, the isolate option references
the schedule dimensions of outer band nodes, making it depend
on the position of the band node in the schedule tree.
We therefore refuse to perform some operations on the schedule
tree if they may affect the validity of isolate options.
The user should perform these operations first before applying
an isolate option. In future we may consider updating the isolate
option when these operations are performed.
Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
23 files changed:
diff --git a/doc/user.pod b/doc/user.pod
--- a/doc/user.pod
+++ b/doc/user.pod
The original name is still available
for backward compatibility, but it will be removed in the future.
+=item * The C<separation_class> AST generation option has been
+deprecated.
+
=back
=head1 License
An extra top-level band node (right underneath the domain node) can
be introduced into the schedule using the following function.
+The schedule tree is assumed not to have any anchored nodes.
#include <isl/schedule.h>
__isl_give isl_schedule *
of the node, now located at the position of the original node
or to a leaf node at that position if there was no child.
It is not allowed to remove the root of a schedule tree,
-a set or sequence node or a child of a set or sequence node.
+a set or sequence node, a child of a set or sequence node or
+a band node with an anchored subtree.
#include <isl/schedule_node.h>
__isl_give isl_schedule_node *isl_schedule_node_delete(
__isl_take isl_schedule_node *node);
+Most nodes in a schedule tree only contain local information.
+In some cases, however, a node may also refer to outer band nodes.
+This means that the position of the node within the tree should
+not be changed, or at least that no changes are performed to the
+outer band nodes. The following function can be used to test
+whether the subtree rooted at a given node contains any such nodes.
+
+ #include <isl/schedule_node.h>
+ int isl_schedule_node_is_subtree_anchored(
+ __isl_keep isl_schedule_node *node);
+
The following function resets the user pointers on all parameter
and tuple identifiers referenced by the given schedule node.
__isl_take isl_schedule_node *node, int pos,
enum isl_ast_loop_type type);
__isl_give isl_union_set *
+ enum isl_ast_loop_type
+ isl_schedule_node_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_node *node, int pos);
+ __isl_give isl_schedule_node *
+ isl_schedule_node_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_node *node, int pos,
+ enum isl_ast_loop_type type);
isl_schedule_node_band_get_ast_build_options(
__isl_keep isl_schedule_node *node);
__isl_give isl_schedule_node *
step even if the default scheduler is used.
An C<isl_ast_loop_type> is one of C<isl_ast_loop_default>,
C<isl_ast_loop_atomic>, C<isl_ast_loop_unroll> or C<isl_ast_loop_separate>.
-For the meaning of these loop AST generation types, see
-L</"AST Generation Options (Schedule Tree)">.
-The function C<isl_schedule_node_band_member_get_ast_loop_type>
+For the meaning of these loop AST generation types and the difference
+between the regular loop AST generation type and the isolate
+loop AST generation type, see L</"AST Generation Options (Schedule Tree)">.
+The functions C<isl_schedule_node_band_member_get_ast_loop_type>
+and C<isl_schedule_node_band_member_get_isolate_ast_loop_type>
may return C<isl_ast_loop_error> if an error occurs.
The AST build options govern how an AST is generated for
the individual schedule dimensions during AST generation.
This function inserts a new band node with (the greatest integer
part of) the given partial schedule.
+The subtree rooted at the given node is assumed not to have
+any anchored nodes.
#include <isl/schedule_node.h>
__isl_give isl_schedule_node *
the band using the given tile sizes inside its schedule.
A new child band node is created to represent the point loops and it is
inserted between the modified band and its children.
+The subtree rooted at the given node is assumed not to have
+any anchored nodes.
The C<tile_scale_tile_loops> option specifies whether the tile
loops iterators should be scaled by the tile sizes.
If the C<tile_shift_point_loops> option is set, then the point loops
__isl_give isl_schedule_node *isl_schedule_node_band_sink(
__isl_take isl_schedule_node *node);
+The subtree rooted at the given node is assumed not to have
+any anchored nodes.
The result points to the node in the resulting tree that is in the same
position as the node pointed to by C<node> in the original tree.
=back
+The C<isolate> option is a bit more involved. It allows the user
+to isolate a range of schedule dimension values from smaller and
+greater values. Additionally, the user may specify a different
+atomic/separate/unroll choice for the isolated part and the remaining
+parts. The typical use case of the C<isolate> option is to isolate
+full tiles from partial tiles.
+The part that needs to be isolated may depend on outer schedule dimensions.
+The option therefore needs to be able to reference those outer schedule
+dimensions. In particular, the space of the C<isolate> option is that
+of a wrapped map with as domain the flat product of all outer band nodes
+and as range the space of the current band node.
+The atomic/separate/unroll choice for the isolated part is determined
+by an option that lives in an unnamed wrapped space with as domain
+a zero-dimensional C<isolate> space and as range the regular
+C<atomic>, C<separate> or C<unroll> space.
+This option may also be set directly using
+C<isl_schedule_node_band_member_set_isolate_ast_loop_type>.
+The atomic/separate/unroll choice for the remaining part is determined
+by the regular C<atomic>, C<separate> or C<unroll> option.
+The use of the C<isolate> option causes any tree containing the node
+to be considered anchored.
+
+As an example, consider the isolation of full tiles from partial tiles
+in a tiling of a triangular domain. The original schedule is as follows.
+
+ domain: "{ A[i,j] : 0 <= i,j and i + j <= 100 }"
+ child:
+ schedule: "[{ A[i,j] -> [floor(i/10)] }, \
+ { A[i,j] -> [floor(j/10)] }, \
+ { A[i,j] -> [i] }, { A[i,j] -> [j] }]"
+
+The output is
+
+ for (int c0 = 0; c0 <= 10; c0 += 1)
+ for (int c1 = 0; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+
+Isolating the full tiles, we have the following input
+
+ domain: "{ A[i,j] : 0 <= i,j and i + j <= 100 }"
+ child:
+ schedule: "[{ A[i,j] -> [floor(i/10)] }, \
+ { A[i,j] -> [floor(j/10)] }, \
+ { A[i,j] -> [i] }, { A[i,j] -> [j] }]"
+ options: "{ isolate[[] -> [a,b,c,d]] : 0 <= 10a,10b and \
+ 10a+9+10b+9 <= 100 }"
+
+and output
+
+ {
+ for (int c0 = 0; c0 <= 8; c0 += 1) {
+ for (int c1 = 0; c1 <= -c0 + 8; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= 10 * c0 + 9; c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= 10 * c1 + 9; c3 += 1)
+ A(c2, c3);
+ for (int c1 = -c0 + 9; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+ }
+ for (int c0 = 9; c0 <= 10; c0 += 1)
+ for (int c1 = 0; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+ }
+
+We may then additionally unroll the innermost loop of the isolated part
+
+ domain: "{ A[i,j] : 0 <= i,j and i + j <= 100 }"
+ child:
+ schedule: "[{ A[i,j] -> [floor(i/10)] }, \
+ { A[i,j] -> [floor(j/10)] }, \
+ { A[i,j] -> [i] }, { A[i,j] -> [j] }]"
+ options: "{ isolate[[] -> [a,b,c,d]] : 0 <= 10a,10b and \
+ 10a+9+10b+9 <= 100; [isolate[] -> unroll[3]] }"
+
+to obtain
+
+ {
+ for (int c0 = 0; c0 <= 8; c0 += 1) {
+ for (int c1 = 0; c1 <= -c0 + 8; c1 += 1)
+ for (int c2 = 10 * c0; c2 <= 10 * c0 + 9; c2 += 1) {
+ A(c2, 10 * c1);
+ A(c2, 10 * c1 + 1);
+ A(c2, 10 * c1 + 2);
+ A(c2, 10 * c1 + 3);
+ A(c2, 10 * c1 + 4);
+ A(c2, 10 * c1 + 5);
+ A(c2, 10 * c1 + 6);
+ A(c2, 10 * c1 + 7);
+ A(c2, 10 * c1 + 8);
+ A(c2, 10 * c1 + 9);
+ }
+ for (int c1 = -c0 + 9; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+ }
+ for (int c0 = 9; c0 <= 10; c0 += 1)
+ for (int c1 = 0; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+ }
+
+
=head3 AST Generation Options (Schedule Map)
In case of AST construction using
=item C<separation_class>
+B<This option has been deprecated. Use the isolate option on
+schedule trees instead.>
+
This space is a wrapped relation between two one dimensional spaces.
The input space represents the schedule dimension to which the option
applies and the output space represents the separation class.
__isl_give isl_schedule_node *isl_schedule_node_next_sibling(
__isl_take isl_schedule_node *node);
+int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node *node);
+
__isl_give isl_space *isl_schedule_node_band_get_space(
__isl_keep isl_schedule_node *node);
__isl_give isl_multi_union_pw_aff *isl_schedule_node_band_get_partial_schedule(
__isl_give isl_schedule_node *isl_schedule_node_band_member_set_ast_loop_type(
__isl_take isl_schedule_node *node, int pos,
enum isl_ast_loop_type type);
+enum isl_ast_loop_type isl_schedule_node_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_node *node, int pos);
+__isl_give isl_schedule_node *
+isl_schedule_node_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_node *node, int pos,
+ enum isl_ast_loop_type type);
__isl_give isl_union_set *isl_schedule_node_band_get_ast_build_options(
__isl_keep isl_schedule_node *node);
__isl_give isl_schedule_node *isl_schedule_node_band_set_ast_build_options(
diff --git a/isl_ast_build.c b/isl_ast_build.c
--- a/isl_ast_build.c
+++ b/isl_ast_build.c
isl_union_map_free(build->options);
isl_schedule_node_free(build->node);
free(build->loop_type);
+ isl_set_free(build->isolated);
free(build);
* then update the loop AST generation types
* to reflect the insertion of a dimension at (global) position "pos"
* in the schedule domain space.
+ * We do not need to adjust any isolate option since we would not be inserting
+ * any dimensions if there were any isolate option.
*/
static __isl_give isl_ast_build *node_insert_dim(
__isl_take isl_ast_build *build, int pos)
* They have been updated to reflect any dimension insertion in
* node_insert_dim.
* Return isl_ast_domain_error on error.
+ *
+ * If "isolated" is set, then we get the loop AST generation type
+ * directly from the band node since node_insert_dim cannot have been
+ * called on a band with the isolate option.
*/
enum isl_ast_loop_type isl_ast_build_get_loop_type(
- __isl_keep isl_ast_build *build)
+ __isl_keep isl_ast_build *build, int isolated)
{
int local_pos;
isl_ctx *ctx;
return isl_ast_loop_error);
local_pos = build->depth - build->outer_pos;
- return build->loop_type[local_pos];
+ if (!isolated)
+ return build->loop_type[local_pos];
+ return isl_schedule_node_band_member_get_isolate_ast_loop_type(
+ build->node, local_pos);
+}
+
+/* Extract the isolated set from the isolate option, if any,
+ * and store in the build.
+ * If there is no isolate option, then the isolated set is
+ * set to the empty set.
+ *
+ * The isolate option is of the form
+ *
+ * isolate[[outer bands] -> current_band]
+ *
+ * We flatten this set and then map it back to the internal
+ * schedule space.
+ *
+ * If we have already extracted the isolated set
+ * or if internal2input is no longer set, then we do not
+ * need to do anything. In the latter case, we know
+ * that the current band cannot have any isolate option.
+ */
+__isl_give isl_ast_build *isl_ast_build_extract_isolated(
+ __isl_take isl_ast_build *build)
+{
+ isl_space *space, *space2;
+ isl_union_set *options;
+ int n, n2;
+ isl_set *isolated;
+
+ if (!build)
+ return NULL;
+ if (!build->internal2input)
+ return build;
+ if (build->isolated)
+ return build;
+
+ build = isl_ast_build_cow(build);
+ if (!build)
+ return NULL;
+
+ options = isl_schedule_node_band_get_ast_build_options(build->node);
+
+ space = isl_multi_aff_get_space(build->internal2input);
+ space = isl_space_range(space);
+ space2 = isl_set_get_space(build->domain);
+ if (isl_space_is_wrapping(space2))
+ space2 = isl_space_range(isl_space_unwrap(space2));
+ n2 = isl_space_dim(space2, isl_dim_set);
+ n = isl_space_dim(space, isl_dim_set);
+ if (n < n2)
+ isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+ "total input space dimension cannot be smaller "
+ "than dimension of innermost band",
+ space = isl_space_free(space));
+ space = isl_space_drop_dims(space, isl_dim_set, n - n2, n2);
+ space = isl_space_map_from_domain_and_range(space, space2);
+ space = isl_space_wrap(space);
+ space = isl_space_set_tuple_name(space, isl_dim_set, "isolate");
+ isolated = isl_union_set_extract_set(options, space);
+ isl_union_set_free(options);
+
+ isolated = isl_set_flatten(isolated);
+ isolated = isl_set_preimage_multi_aff(isolated,
+ isl_multi_aff_copy(build->internal2input));
+
+ build->isolated = isolated;
+ if (!build->isolated)
+ return isl_ast_build_free(build);
+
+ return build;
+}
+
+/* Does "build" have a non-empty isolated set?
+ *
+ * The caller is assumed to have called isl_ast_build_extract_isolated first.
+ */
+int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
+{
+ int empty;
+
+ if (!build)
+ return -1;
+ if (!build->internal2input)
+ return 0;
+ if (!build->isolated)
+ isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+ "isolated set not extracted yet", return -1);
+
+ empty = isl_set_plain_is_empty(build->isolated);
+ return empty < 0 ? -1 : !empty;
+}
+
+/* Return a copy of the isolated set of "build".
+ *
+ * The caller is assume to have called isl_ast_build_has_isolated first,
+ * with this function returning true.
+ * In particular, this function should not be called if we are no
+ * longer keeping track of internal2input (and there therefore could
+ * not possibly be any isolated set).
+ */
+__isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
+{
+ if (!build)
+ return NULL;
+ if (!build->internal2input)
+ isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
+ "build cannot have isolated set", return NULL);
+
+ return isl_set_copy(build->isolated);
}
/* Extract the separation class mapping at the current depth.
--- a/isl_ast_build_private.h
+++ b/isl_ast_build_private.h
* the "n" members of "node" and it is updated (along with "n") when
* a schedule dimension is inserted.
* It is NULL if "node" is NULL.
+ *
+ * "isolated" is the piece of the schedule domain isolated by the isolate
+ * option on the current band. This set may be NULL if we have not checked
+ * for the isolate option yet.
*/
struct isl_ast_build {
int ref;
isl_schedule_node *node;
int n;
enum isl_ast_loop_type *loop_type;
+ isl_set *isolated;
};
__isl_give isl_ast_build *isl_ast_build_clear_local_info(
__isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
__isl_take isl_ast_build *build);
+__isl_give isl_ast_build *isl_ast_build_extract_isolated(
+ __isl_take isl_ast_build *build);
+int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build);
+__isl_give isl_set *isl_ast_build_get_isolated(
+ __isl_keep isl_ast_build *build);
+
__isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
__isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset);
__isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
__isl_keep isl_ast_build *build, __isl_take isl_set *set);
enum isl_ast_loop_type isl_ast_build_get_loop_type(
- __isl_keep isl_ast_build *build);
+ __isl_keep isl_ast_build *build, int isolated);
__isl_give isl_map *isl_ast_build_map_to_iterator(
__isl_keep isl_ast_build *build, __isl_take isl_set *set);
diff --git a/isl_ast_codegen.c b/isl_ast_codegen.c
--- a/isl_ast_codegen.c
+++ b/isl_ast_codegen.c
* B.P. 105 - 78153 Le Chesnay, France
*/
-#include <string.h>
#include <limits.h>
#include <isl/aff.h>
#include <isl/set.h>
/* Generate code for a single component, after shifting (if any)
* has been applied, in case the schedule was specified as a schedule tree.
+ * In particular, handle the base case where there is either no isolated
+ * set or we are within the isolated set (in which case "isolated" is set)
+ * or the iterations that precede or follow the isolated set.
*
* The schedule domain is broken up or combined into basic sets
* according to the AST generation option specified in the current
* Finally an AST is generated for each basic set and the results are
* concatenated.
*/
-static __isl_give isl_ast_graft_list *generate_shifted_component_tree(
- __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
+static __isl_give isl_ast_graft_list *generate_shifted_component_tree_base(
+ __isl_take isl_union_map *executed, __isl_take isl_ast_build *build,
+ int isolated)
{
isl_union_set *schedule_domain;
isl_set *domain;
isl_ast_graft_list *list;
enum isl_ast_loop_type type;
- type = isl_ast_build_get_loop_type(build);
+ type = isl_ast_build_get_loop_type(build, isolated);
if (type < 0)
goto error;
}
/* Generate code for a single component, after shifting (if any)
+ * has been applied, in case the schedule was specified as a schedule tree.
+ * In particular, do so for the specified subset of the schedule domsain.
+ */
+static __isl_give isl_ast_graft_list *generate_shifted_component_tree_part(
+ __isl_keep isl_union_map *executed, __isl_take isl_set *domain,
+ __isl_keep isl_ast_build *build, int isolated)
+{
+ isl_union_set *uset;
+ int empty;
+
+ uset = isl_union_set_from_set(domain);
+ executed = isl_union_map_copy(executed);
+ executed = isl_union_map_intersect_domain(executed, uset);
+ empty = isl_union_map_is_empty(executed);
+ if (empty < 0)
+ goto error;
+ if (empty) {
+ isl_ctx *ctx;
+ isl_union_map_free(executed);
+ ctx = isl_ast_build_get_ctx(build);
+ return isl_ast_graft_list_alloc(ctx, 0);
+ }
+
+ build = isl_ast_build_copy(build);
+ return generate_shifted_component_tree_base(executed, build, isolated);
+error:
+ isl_union_map_free(executed);
+ return NULL;
+}
+
+/* Generate code for a single component, after shifting (if any)
+ * has been applied, in case the schedule was specified as a schedule tree.
+ *
+ * We first check if the user has specified a (non-empty) isolated
+ * schedule domain.
+ * If so, we break up the schedule domain into iterations that
+ * precede the isolated domain, the isolated domain itself,
+ * the iterations that follow the isolated domain and
+ * the remaining iterations (those that are incomparable
+ * to the isolated domain).
+ * We generate an AST for each piece and concatenate the results.
+ * If no isolated set has been specified, then we generate an
+ * AST for the entire inverse schedule.
+ */
+static __isl_give isl_ast_graft_list *generate_shifted_component_tree(
+ __isl_take isl_union_map *executed, __isl_take isl_ast_build *build)
+{
+ int i, depth;
+ int empty, has_isolate;
+ isl_space *space;
+ isl_union_set *schedule_domain;
+ isl_set *domain;
+ isl_basic_set *hull;
+ isl_set *isolated, *before, *after;
+ isl_map *gt, *lt;
+ isl_ast_graft_list *list, *res;
+
+ build = isl_ast_build_extract_isolated(build);
+ has_isolate = isl_ast_build_has_isolated(build);
+ if (has_isolate < 0)
+ executed = isl_union_map_free(executed);
+ else if (!has_isolate)
+ return generate_shifted_component_tree_base(executed, build, 0);
+
+ schedule_domain = isl_union_map_domain(isl_union_map_copy(executed));
+ domain = isl_set_from_union_set(schedule_domain);
+
+ isolated = isl_ast_build_get_isolated(build);
+ isolated = isl_set_intersect(isolated, isl_set_copy(domain));
+ empty = isl_set_is_empty(isolated);
+ if (empty < 0)
+ goto error;
+ if (empty) {
+ isl_set_free(isolated);
+ isl_set_free(domain);
+ return generate_shifted_component_tree_base(executed, build, 0);
+ }
+ isolated = isl_ast_build_eliminate(build, isolated);
+ hull = isl_set_unshifted_simple_hull(isolated);
+ isolated = isl_set_from_basic_set(hull);
+
+ depth = isl_ast_build_get_depth(build);
+ space = isl_space_map_from_set(isl_set_get_space(isolated));
+ gt = isl_map_universe(space);
+ for (i = 0; i < depth; ++i)
+ gt = isl_map_equate(gt, isl_dim_in, i, isl_dim_out, i);
+ gt = isl_map_order_gt(gt, isl_dim_in, depth, isl_dim_out, depth);
+ lt = isl_map_reverse(isl_map_copy(gt));
+ before = isl_set_apply(isl_set_copy(isolated), gt);
+ after = isl_set_apply(isl_set_copy(isolated), lt);
+
+ domain = isl_set_subtract(domain, isl_set_copy(isolated));
+ domain = isl_set_subtract(domain, isl_set_copy(before));
+ domain = isl_set_subtract(domain, isl_set_copy(after));
+ after = isl_set_subtract(after, isl_set_copy(isolated));
+ after = isl_set_subtract(after, isl_set_copy(before));
+ before = isl_set_subtract(before, isl_set_copy(isolated));
+
+ res = generate_shifted_component_tree_part(executed, before, build, 0);
+ list = generate_shifted_component_tree_part(executed, isolated,
+ build, 1);
+ res = isl_ast_graft_list_concat(res, list);
+ list = generate_shifted_component_tree_part(executed, after, build, 0);
+ res = isl_ast_graft_list_concat(res, list);
+ list = generate_shifted_component_tree_part(executed, domain, build, 0);
+ res = isl_ast_graft_list_concat(res, list);
+
+ isl_union_map_free(executed);
+ isl_ast_build_free(build);
+
+ return res;
+error:
+ isl_set_free(domain);
+ isl_set_free(isolated);
+ isl_union_map_free(executed);
+ isl_ast_build_free(build);
+ return NULL;
+}
+
+/* Generate code for a single component, after shifting (if any)
* has been applied.
*
* Call generate_shifted_component_tree or generate_shifted_component_flat
return NULL;
}
+/* Does any node in the schedule tree rooted at the current schedule node
+ * of "build" depend on outer schedule nodes?
+ */
+static int has_anchored_subtree(__isl_keep isl_ast_build *build)
+{
+ isl_schedule_node *node;
+ int dependent = 0;
+
+ node = isl_ast_build_get_schedule_node(build);
+ dependent = isl_schedule_node_is_subtree_anchored(node);
+ isl_schedule_node_free(node);
+
+ return dependent;
+}
+
/* Generate code for a single component.
*
* The component inverse schedule is specified as the "map" fields
* in terms of the new schedule domain, but that would introduce constraints
* that separate the domains in the options and that is something we would
* like to avoid.
+ * In the case of a schedule tree input, we bail out if any of
+ * the descendants of the current schedule node refer to outer
+ * schedule nodes in any way.
*
*
* To see if there is any shifted stride, we look at the differences
if (skip >= 0 && !skip)
skip = at_most_one_non_fixed(domain, order, n, depth);
if (skip >= 0 && !skip) {
- if (!isl_ast_build_has_schedule_node(build))
+ if (isl_ast_build_has_schedule_node(build))
+ skip = has_anchored_subtree(build);
+ else
skip = isl_ast_build_options_involve_depth(build);
}
if (skip < 0)
diff --git a/isl_schedule.c b/isl_schedule.c
--- a/isl_schedule.c
+++ b/isl_schedule.c
/* Insert a band node with partial schedule "partial" between the domain
* root node of "schedule" and its single child.
* Return a pointer to the updated schedule.
+ *
+ * If any of the nodes in the tree depend on the set of outer band nodes
+ * then we refuse to insert the band node.
*/
__isl_give isl_schedule *isl_schedule_insert_partial_schedule(
__isl_take isl_schedule *schedule,
__isl_take isl_multi_union_pw_aff *partial)
{
isl_schedule_node *node;
+ int anchored;
node = isl_schedule_get_root(schedule);
isl_schedule_free(schedule);
"root node not a domain node", goto error);
node = isl_schedule_node_child(node, 0);
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ goto error;
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+ "cannot insert band node in anchored subtree",
+ goto error);
node = isl_schedule_node_insert_partial_schedule(node, partial);
schedule = isl_schedule_node_get_schedule(node);
diff --git a/isl_schedule_band.c b/isl_schedule_band.c
--- a/isl_schedule_band.c
+++ b/isl_schedule_band.c
*/
#include <string.h>
+#include <isl/map.h>
#include <isl/schedule_node.h>
#include <isl_schedule_band.h>
#include <isl_schedule_private.h>
* that the schedule is always integral.
* The band is not marked permutable, the dimensions are not
* marked coincident and the AST build options are empty.
+ * Since there are no build options, the node is not anchored.
*/
__isl_give isl_schedule_band *isl_schedule_band_from_multi_union_pw_aff(
__isl_take isl_multi_union_pw_aff *mupa)
band->mupa = mupa;
space = isl_space_params_alloc(ctx, 0);
band->ast_build_options = isl_union_set_empty(space);
+ band->anchored = 0;
if ((band->n && !band->coincident) || !band->ast_build_options)
return isl_schedule_band_free(band);
for (i = 0; i < band->n; ++i)
dup->loop_type[i] = band->loop_type[i];
}
+ if (band->isolate_loop_type) {
+ dup->isolate_loop_type = isl_alloc_array(ctx,
+ enum isl_ast_loop_type, band->n);
+ if (band->n && !dup->isolate_loop_type)
+ return isl_schedule_band_free(dup);
+ for (i = 0; i < band->n; ++i)
+ dup->isolate_loop_type[i] = band->isolate_loop_type[i];
+ }
return dup;
}
isl_multi_union_pw_aff_free(band->mupa);
isl_union_set_free(band->ast_build_options);
free(band->loop_type);
+ free(band->isolate_loop_type);
free(band->coincident);
free(band);
if (band1->loop_type[i] != band2->loop_type[i])
return 0;
+ if (!band1->isolate_loop_type != !band2->isolate_loop_type)
+ return 0;
+ if (band1->isolate_loop_type)
+ for (i = 0; i < band1->n; ++i)
+ if (band1->isolate_loop_type[i] !=
+ band2->isolate_loop_type[i])
+ return 0;
+
return isl_union_set_is_equal(band1->ast_build_options,
band2->ast_build_options);
}
return band;
}
+/* Is the band node "node" anchored? That is, does it reference
+ * the outer band nodes?
+ */
+int isl_schedule_band_is_anchored(__isl_keep isl_schedule_band *band)
+{
+ return band ? band->anchored : -1;
+}
+
/* Return the schedule space of the band.
*/
__isl_give isl_space *isl_schedule_band_get_space(
return band;
}
+/* Return the loop AST generation type for the band member of "band"
+ * at position "pos" for the part that has been isolated by the isolate option.
+ */
+enum isl_ast_loop_type isl_schedule_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_band *band, int pos)
+{
+ if (!band)
+ return isl_ast_loop_error;
+
+ if (pos < 0 || pos >= band->n)
+ isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
+ "invalid member position", return -1);
+
+ if (!band->isolate_loop_type)
+ return isl_ast_loop_default;
+
+ return band->isolate_loop_type[pos];
+}
+
+/* Set the loop AST generation type for the band member of "band"
+ * at position "pos" to "type" for the part that has been isolated
+ * by the isolate option.
+ */
+__isl_give isl_schedule_band *
+isl_schedule_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_band *band, int pos,
+ enum isl_ast_loop_type type)
+{
+ if (!band)
+ return NULL;
+ if (isl_schedule_band_member_get_isolate_ast_loop_type(band, pos) ==
+ type)
+ return band;
+
+ if (pos < 0 || pos >= band->n)
+ isl_die(isl_schedule_band_get_ctx(band), isl_error_invalid,
+ "invalid member position",
+ isl_schedule_band_free(band));
+
+ band = isl_schedule_band_cow(band);
+ if (!band)
+ return isl_schedule_band_free(band);
+
+ if (!band->isolate_loop_type) {
+ isl_ctx *ctx;
+
+ ctx = isl_schedule_band_get_ctx(band);
+ band->isolate_loop_type = isl_calloc_array(ctx,
+ enum isl_ast_loop_type, band->n);
+ if (band->n && !band->isolate_loop_type)
+ return isl_schedule_band_free(band);
+ }
+
+ band->isolate_loop_type[pos] = type;
+
+ return band;
+}
+
static const char *option_str[] = {
[isl_ast_loop_atomic] = "atomic",
[isl_ast_loop_unroll] = "unroll",
*
* { type[x] }
*
- * which can be used to encode loop AST generation options of the given type.
+ * or
+ *
+ * { [isolate[] -> type[x]] }
+ *
+ * depending on whether "isolate" is set.
+ * These can be used to encode loop AST generation options of the given type.
*/
static __isl_give isl_space *loop_type_space(__isl_take isl_space *space,
- enum isl_ast_loop_type type)
+ enum isl_ast_loop_type type, int isolate)
{
const char *name;
space = isl_space_set_from_params(space);
space = isl_space_add_dims(space, isl_dim_set, 1);
space = isl_space_set_tuple_name(space, isl_dim_set, name);
+ if (!isolate)
+ return space;
+ space = isl_space_from_range(space);
+ space = isl_space_set_tuple_name(space, isl_dim_in, "isolate");
+ space = isl_space_wrap(space);
return space;
}
/* Add encodings of the "n" loop AST generation options "type" to "options".
+ * If "isolate" is set, then these options refer to the isolated part.
*
* In particular, for each sequence of consecutive identical types "t",
* different from the default, add an option
*
* { t[x] : first <= x <= last }
+ *
+ * or
+ *
+ * { [isolate[] -> t[x]] : first <= x <= last }
*/
static __isl_give isl_union_set *add_loop_types(
- __isl_take isl_union_set *options, int n, enum isl_ast_loop_type *type)
+ __isl_take isl_union_set *options, int n, enum isl_ast_loop_type *type,
+ int isolate)
{
int i;
isl_ctx *ctx;
++i;
space = isl_union_set_get_space(options);
- space = loop_type_space(space, type[i]);
+ space = loop_type_space(space, type[i], isolate);
option = isl_set_universe(space);
option = isl_set_lower_bound_si(option, isl_dim_set, 0, first);
option = isl_set_upper_bound_si(option, isl_dim_set, 0, i);
return NULL;
options = isl_union_set_copy(band->ast_build_options);
- options = add_loop_types(options, band->n, band->loop_type);
+ options = add_loop_types(options, band->n, band->loop_type, 0);
+ options = add_loop_types(options, band->n, band->isolate_loop_type, 1);
return options;
}
return found;
}
+/* Does "set" live in a space of the form
+ *
+ * isolate[[...] -> [...]]
+ *
+ * ?
+ *
+ * If so, set *found and abort the search.
+ */
+static int is_isolate(__isl_take isl_set *set, void *user)
+{
+ int *found = user;
+
+ if (isl_set_has_tuple_name(set)) {
+ const char *name;
+ name = isl_set_get_tuple_name(set);
+ if (isl_set_is_wrapping(set) && !strcmp(name, "isolate"))
+ *found = 1;
+ }
+ isl_set_free(set);
+
+ return *found ? -1 : 0;
+}
+
+/* Does "options" include an option of the ofrm
+ *
+ * isolate[[...] -> [...]]
+ *
+ * ?
+ */
+static int has_isolate_option(__isl_keep isl_union_set *options)
+{
+ return has_any(options, &is_isolate);
+}
+
/* Does "set" encode a loop AST generation option?
*/
static int is_loop_type_option(__isl_take isl_set *set, void *user)
return *found ? -1 : 0;
}
+/* Does "set" encode a loop AST generation option for the isolated part?
+ * That is, is of the form
+ *
+ * { [isolate[] -> t[x]] }
+ *
+ * with t equal to "atomic", "unroll" or "separate"?
+ */
+static int is_isolate_loop_type_option(__isl_take isl_set *set, void *user)
+{
+ int *found = user;
+ const char *name;
+ enum isl_ast_loop_type type;
+ isl_map *map;
+
+ if (!isl_set_is_wrapping(set)) {
+ isl_set_free(set);
+ return 0;
+ }
+ map = isl_set_unwrap(set);
+ if (!isl_map_has_tuple_name(map, isl_dim_in) ||
+ !isl_map_has_tuple_name(map, isl_dim_out)) {
+ isl_map_free(map);
+ return 0;
+ }
+ name = isl_map_get_tuple_name(map, isl_dim_in);
+ if (!strcmp(name, "isolate")) {
+ name = isl_map_get_tuple_name(map, isl_dim_out);
+ for (type = isl_ast_loop_atomic;
+ type <= isl_ast_loop_separate; ++type) {
+ if (strcmp(name, option_str[type]))
+ continue;
+ *found = 1;
+ break;
+ }
+ }
+ isl_map_free(map);
+
+ return *found ? -1 : 0;
+}
+
+/* Does "options" encode any loop AST generation options
+ * for the isolated part?
+ */
+static int has_isolate_loop_type_options(__isl_keep isl_union_set *options)
+{
+ return has_any(options, &is_isolate_loop_type_option);
+}
+
/* Does "options" encode any loop AST generation options?
*/
static int has_loop_type_options(__isl_keep isl_union_set *options)
/* Extract the loop AST generation type for the band member
* at position "pos" from "options".
+ * If "isolate" is set, then extract the loop types for the isolated part.
*/
static enum isl_ast_loop_type extract_loop_type(
- __isl_keep isl_union_set *options, int pos)
+ __isl_keep isl_union_set *options, int pos, int isolate)
{
isl_ctx *ctx;
enum isl_ast_loop_type type, res = isl_ast_loop_default;
int empty;
space = isl_union_set_get_space(options);
- space = loop_type_space(space, type);
+ space = loop_type_space(space, type, isolate);
option = isl_union_set_extract_set(options, space);
option = isl_set_fix_si(option, isl_dim_set, 0, pos);
empty = isl_set_is_empty(option);
return -1;
}
for (i = 0; i < band->n; ++i) {
- band->loop_type[i] = extract_loop_type(options, i);
+ band->loop_type[i] = extract_loop_type(options, i, 0);
if (band->loop_type[i] == isl_ast_loop_error)
return -1;
}
return 0;
}
+/* Extract the loop AST generation types for the members of "band"
+ * from "options" for the isolated part and
+ * store them in band->isolate_loop_type.
+ * Return -1 on error.
+ */
+static int extract_isolate_loop_types(__isl_keep isl_schedule_band *band,
+ __isl_keep isl_union_set *options)
+{
+ int i;
+
+ if (!band->isolate_loop_type) {
+ isl_ctx *ctx = isl_schedule_band_get_ctx(band);
+ band->isolate_loop_type = isl_alloc_array(ctx,
+ enum isl_ast_loop_type, band->n);
+ if (band->n && !band->isolate_loop_type)
+ return -1;
+ }
+ for (i = 0; i < band->n; ++i) {
+ band->isolate_loop_type[i] = extract_loop_type(options, i, 1);
+ if (band->isolate_loop_type[i] == isl_ast_loop_error)
+ return -1;
+ }
+
+ return 0;
+}
+
/* Construct universe sets of the spaces that encode loop AST generation
- * types. That is, construct
+ * types (for the isolated part if "isolate" is set). That is, construct
*
* { atomic[x]; separate[x]; unroll[x] }
+ *
+ * or
+ *
+ * { [isolate[] -> atomic[x]]; [isolate[] -> separate[x]];
+ * [isolate[] -> unroll[x]] }
*/
-static __isl_give isl_union_set *loop_types(__isl_take isl_space *space)
+static __isl_give isl_union_set *loop_types(__isl_take isl_space *space,
+ int isolate)
{
enum isl_ast_loop_type type;
isl_union_set *types;
isl_set *set;
space = isl_union_set_get_space(types);
- space = loop_type_space(space, type);
+ space = loop_type_space(space, type, isolate);
set = isl_set_universe(space);
types = isl_union_set_add_set(types, set);
}
{
isl_union_set *types;
- types = loop_types(isl_union_set_get_space(options));
+ types = loop_types(isl_union_set_get_space(options), 0);
+ options = isl_union_set_subtract(options, types);
+
+ return options;
+}
+
+/* Remove all elements from spaces that encode loop AST generation types
+ * for the isolated part from "options".
+ */
+static __isl_give isl_union_set *clear_isolate_loop_types(
+ __isl_take isl_union_set *options)
+{
+ isl_union_set *types;
+
+ types = loop_types(isl_union_set_get_space(options), 1);
options = isl_union_set_subtract(options, types);
return options;
* If there are any loop AST generation type options, then they
* are extracted and stored in band->loop_type. Otherwise,
* band->loop_type is removed to indicate that the default applies
- * to all members.
+ * to all members. Similarly for the loop AST generation type options
+ * for the isolated part, which are stored in band->isolate_loop_type.
* The remaining options are stored in band->ast_build_options.
+ *
+ * Set anchored if the options include an isolate option since the
+ * domain of the wrapped map references the outer band node schedules.
*/
__isl_give isl_schedule_band *isl_schedule_band_set_ast_build_options(
__isl_take isl_schedule_band *band, __isl_take isl_union_set *options)
{
- int has_loop_type;
+ int has_isolate, has_loop_type, has_isolate_loop_type;
band = isl_schedule_band_cow(band);
if (!band || !options)
goto error;
+ has_isolate = has_isolate_option(options);
+ if (has_isolate < 0)
+ goto error;
has_loop_type = has_loop_type_options(options);
if (has_loop_type < 0)
goto error;
+ has_isolate_loop_type = has_isolate_loop_type_options(options);
+ if (has_isolate_loop_type < 0)
+ goto error;
if (!has_loop_type) {
free(band->loop_type);
goto error;
}
+ if (!has_isolate_loop_type) {
+ free(band->isolate_loop_type);
+ band->isolate_loop_type = NULL;
+ } else {
+ if (extract_isolate_loop_types(band, options) < 0)
+ goto error;
+ options = clear_isolate_loop_types(options);
+ if (!options)
+ goto error;
+ }
+
isl_union_set_free(band->ast_build_options);
band->ast_build_options = options;
+ band->anchored = has_isolate;
return band;
error:
*
* We apply the transformation even if "n" is zero to ensure consistent
* behavior with respect to changes in the schedule space.
+ *
+ * The loop AST generation types for the isolated part become
+ * meaningless after dropping dimensions, so we remove them.
*/
__isl_give isl_schedule_band *isl_schedule_band_drop(
__isl_take isl_schedule_band *band, int pos, int n)
if (band->loop_type)
for (i = pos + n; i < band->n; ++i)
band->loop_type[i - n] = band->loop_type[i];
+ free(band->isolate_loop_type);
+ band->isolate_loop_type = NULL;
band->n -= n;
diff --git a/isl_schedule_band.h b/isl_schedule_band.h
--- a/isl_schedule_band.h
+++ b/isl_schedule_band.h
* loop_type contains the loop AST generation types for the members
* in the band. It may be NULL, if all members are
* of type isl_ast_loop_default.
+ * isolate_loop_type contains the loop AST generation types for the members
+ * in the band for the isolated part. It may be NULL, if all members are
+ * of type isl_ast_loop_default.
* ast_build_options are the remaining AST build options associated
* to the band.
+ * anchored is set if the node depends on its position in the schedule tree.
+ * In particular, it is set if the AST build options include
+ * an isolate option.
*/
struct isl_schedule_band {
int ref;
isl_multi_union_pw_aff *mupa;
+ int anchored;
isl_union_set *ast_build_options;
enum isl_ast_loop_type *loop_type;
+ enum isl_ast_loop_type *isolate_loop_type;
};
typedef struct isl_schedule_band isl_schedule_band;
int isl_schedule_band_plain_is_equal(__isl_keep isl_schedule_band *band1,
__isl_keep isl_schedule_band *band2);
+int isl_schedule_band_is_anchored(__isl_keep isl_schedule_band *band);
+
__isl_give isl_space *isl_schedule_band_get_space(
__isl_keep isl_schedule_band *band);
__isl_give isl_multi_union_pw_aff *isl_schedule_band_get_partial_schedule(
__isl_give isl_schedule_band *isl_schedule_band_member_set_ast_loop_type(
__isl_take isl_schedule_band *band, int pos,
enum isl_ast_loop_type type);
+enum isl_ast_loop_type isl_schedule_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_band *band, int pos);
+__isl_give isl_schedule_band *
+isl_schedule_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_band *band, int pos,
+ enum isl_ast_loop_type type);
__isl_give isl_union_set *isl_schedule_band_get_ast_build_options(
__isl_keep isl_schedule_band *band);
__isl_give isl_schedule_band *isl_schedule_band_set_ast_build_options(
diff --git a/isl_schedule_node.c b/isl_schedule_node.c
--- a/isl_schedule_node.c
+++ b/isl_schedule_node.c
return 0;
}
+/* Is any node in the subtree rooted at "node" anchored?
+ * That is, do any of these nodes reference the outer band nodes?
+ */
+int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node *node)
+{
+ if (!node)
+ return -1;
+ return isl_schedule_tree_is_subtree_anchored(node->tree);
+}
+
/* Return the number of members in the given band node.
*/
unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node *node)
@@ -1253,6 +1263,38 @@ __isl_give isl_schedule_node *isl_schedule_node_band_member_set_ast_loop_type(
return isl_schedule_node_graft_tree(node, tree);
}
+/* Return the loop AST generation type for the band member of band node "node"
+ * at position "pos" for the isolated part.
+ */
+enum isl_ast_loop_type isl_schedule_node_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_node *node, int pos)
+{
+ if (!node)
+ return isl_ast_loop_error;
+
+ return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
+ node->tree, pos);
+}
+
+/* Set the loop AST generation type for the band member of band node "node"
+ * at position "pos" for the isolated part to "type".
+ */
+__isl_give isl_schedule_node *
+isl_schedule_node_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_node *node, int pos,
+ enum isl_ast_loop_type type)
+{
+ isl_schedule_tree *tree;
+
+ if (!node)
+ return NULL;
+
+ tree = isl_schedule_tree_copy(node->tree);
+ tree = isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree,
+ pos, type);
+ return isl_schedule_node_graft_tree(node, tree);
+}
+
/* Return the AST build options associated to band node "node".
*/
__isl_give isl_union_set *isl_schedule_node_band_get_ast_build_options(
__isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
{
isl_schedule_tree *tree;
+ int anchored;
if (!node || !mv)
goto error;
if (check_space_multi_val(node, mv) < 0)
goto error;
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ goto error;
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+ "cannot scale band node with anchored subtree",
+ goto error);
tree = isl_schedule_node_get_tree(node);
tree = isl_schedule_tree_band_scale(tree, mv);
__isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
{
isl_schedule_tree *tree;
+ int anchored;
if (!node || !mv)
goto error;
if (check_space_multi_val(node, mv) < 0)
goto error;
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ goto error;
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+ "cannot scale down band node with anchored subtree",
+ goto error);
tree = isl_schedule_node_get_tree(node);
tree = isl_schedule_tree_band_scale_down(tree, mv);
*
* Return a pointer to the outer (tile) node.
*
+ * If any of the descendants of "node" depend on the set of outer band nodes,
+ * then we refuse to tile the node.
+ *
* If the scale tile loops option is set, then the tile loops
* are scaled by the tile sizes. If the shift point loops option is set,
* then the point loops are shifted to start at zero.
__isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes)
{
isl_schedule_tree *tree;
+ int anchored;
if (!node || !sizes)
goto error;
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ goto error;
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+ "cannot tile band node with anchored subtree",
+ goto error);
if (check_space_multi_val(node, sizes) < 0)
goto error;
* Otherwise, the child of the node is removed and the result is
* appended to all the leaves in the subtree rooted at the original child.
* The original node is then replaced by the result of this operation.
+ *
+ * If any of the nodes in the subtree rooted at "node" depend on
+ * the set of outer band nodes then we refuse to sink the band node.
*/
__isl_give isl_schedule_node *isl_schedule_node_band_sink(
__isl_take isl_schedule_node *node)
{
enum isl_schedule_node_type type;
isl_schedule_tree *tree, *child;
+ int anchored;
if (!node)
return NULL;
if (type != isl_schedule_node_band)
isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
"not a band node", isl_schedule_node_free(node));
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ return isl_schedule_node_free(node);
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+ "cannot sink band node in anchored subtree",
+ isl_schedule_node_free(node));
if (isl_schedule_tree_n_children(node->tree) == 0)
return node;
/* Insert a band node with partial schedule "mupa" between "node" and
* its parent.
* Return a pointer to the new band node.
+ *
+ * If any of the nodes in the subtree rooted at "node" depend on
+ * the set of outer band nodes then we refuse to insert the band node.
*/
__isl_give isl_schedule_node *isl_schedule_node_insert_partial_schedule(
__isl_take isl_schedule_node *node,
__isl_take isl_multi_union_pw_aff *mupa)
{
+ int anchored;
isl_schedule_band *band;
isl_schedule_tree *tree;
if (check_insert(node) < 0)
node = isl_schedule_node_free(node);
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ goto error;
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
+ "cannot insert band node in anchored subtree",
+ goto error);
tree = isl_schedule_node_get_tree(node);
band = isl_schedule_band_from_multi_union_pw_aff(mupa);
node = isl_schedule_node_graft_tree(node, tree);
return node;
+error:
+ isl_schedule_node_free(node);
+ isl_multi_union_pw_aff_free(mupa);
+ return NULL;
}
/* Insert a filter node with filter "filter" between "node" and its parent.
* Return a pointer to this former child or to the leaf the position
* of the original node if there was no child.
* It is not allowed to remove the root of a schedule tree,
- * a set or sequence node or a child of a set or sequence node.
+ * a set or sequence node, a child of a set or sequence node or
+ * a band node with an anchored subtree.
*/
__isl_give isl_schedule_node *isl_schedule_node_delete(
__isl_take isl_schedule_node *node)
isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
"cannot delete child of set or sequence",
return isl_schedule_node_free(node));
+ if (isl_schedule_node_get_type(node) == isl_schedule_node_band) {
+ int anchored;
+
+ anchored = isl_schedule_node_is_subtree_anchored(node);
+ if (anchored < 0)
+ return isl_schedule_node_free(node);
+ if (anchored)
+ isl_die(isl_schedule_node_get_ctx(node),
+ isl_error_invalid,
+ "cannot delete band node with anchored subtree",
+ return isl_schedule_node_free(node));
+ }
tree = isl_schedule_node_get_tree(node);
if (!tree || isl_schedule_tree_has_children(tree)) {
diff --git a/isl_schedule_tree.c b/isl_schedule_tree.c
--- a/isl_schedule_tree.c
+++ b/isl_schedule_tree.c
/* Create a new schedule tree of type "type".
* The caller is responsible for filling in the type specific fields and
* the children.
+ *
+ * By default, the single node tree does not have any anchored nodes.
+ * The caller is responsible for updating the anchored field if needed.
*/
static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
enum isl_schedule_node_type type)
tree->ctx = ctx;
isl_ctx_ref(ctx);
tree->type = type;
+ tree->anchored = 0;
return tree;
}
if (!dup->children)
return isl_schedule_tree_free(dup);
}
+ dup->anchored = tree->anchored;
return dup;
}
goto error;
tree->band = band;
+ tree->anchored = isl_schedule_band_is_anchored(band);
return tree;
error:
return NULL;
}
+/* Does "tree" have any node that depends on its position
+ * in the complete schedule tree?
+ */
+int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree *tree)
+{
+ return tree ? tree->anchored : -1;
+}
+
+/* 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.
+ */
+int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
+{
+ if (!tree)
+ return -1;
+
+ switch (isl_schedule_tree_get_type(tree)) {
+ case isl_schedule_node_error:
+ return -1;
+ case isl_schedule_node_band:
+ return isl_schedule_band_is_anchored(tree->band);
+ case isl_schedule_node_domain:
+ case isl_schedule_node_filter:
+ case isl_schedule_node_leaf:
+ case isl_schedule_node_sequence:
+ case isl_schedule_node_set:
+ return 0;
+ }
+}
+
+/* Update the anchored field of "tree" based on whether the root node
+ * itself in anchored and the anchored fields of the children.
+ *
+ * This function should be called whenever the children of a tree node
+ * are changed or the anchoredness of the tree root itself changes.
+ */
+__isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
+ __isl_take isl_schedule_tree *tree)
+{
+ int i, n;
+ int anchored;
+
+ if (!tree)
+ return NULL;
+
+ anchored = isl_schedule_tree_is_anchored(tree);
+ if (anchored < 0)
+ return isl_schedule_tree_free(tree);
+
+ n = isl_schedule_tree_list_n_schedule_tree(tree->children);
+ for (i = 0; !anchored && i < n; ++i) {
+ isl_schedule_tree *child;
+
+ child = isl_schedule_tree_get_child(tree, i);
+ if (!child)
+ return isl_schedule_tree_free(tree);
+ anchored = child->anchored;
+ isl_schedule_tree_free(child);
+ }
+
+ if (anchored == tree->anchored)
+ return tree;
+ tree = isl_schedule_tree_cow(tree);
+ if (!tree)
+ return NULL;
+ tree->anchored = anchored;
+ return tree;
+}
+
/* Create a new tree of the given type (isl_schedule_node_sequence or
* isl_schedule_node_set) with the given children.
*/
goto error;
tree->children = list;
+ tree = isl_schedule_tree_update_anchored(tree);
return tree;
error:
if (!tree->children)
return isl_schedule_tree_free(tree);
+ tree = isl_schedule_tree_update_anchored(tree);
return tree;
error:
return tree;
}
+/* Return the loop AST generation type for the band member
+ * of the band tree root at position "pos" for the isolated part.
+ */
+enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_tree *tree, int pos)
+{
+ if (!tree)
+ return isl_ast_loop_error;
+
+ if (tree->type != isl_schedule_node_band)
+ isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
+ "not a band node", return isl_ast_loop_error);
+
+ return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
+ pos);
+}
+
+/* Set the loop AST generation type for the band member of the band tree root
+ * at position "pos" for the isolated part to "type".
+ */
+__isl_give isl_schedule_tree *
+isl_schedule_tree_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_tree *tree, int pos,
+ enum isl_ast_loop_type type)
+{
+ tree = isl_schedule_tree_cow(tree);
+ if (!tree)
+ return NULL;
+
+ if (tree->type != isl_schedule_node_band)
+ isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
+ "not a band node", return isl_schedule_tree_free(tree));
+
+ tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
+ tree->band, pos, type);
+ if (!tree->band)
+ return isl_schedule_tree_free(tree);
+
+ return tree;
+}
+
/* Return the AST build options associated to the band tree root.
*/
__isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
}
/* Replace the AST build options associated to band tree root by "options".
+ * Updated the anchored field if the anchoredness of the root node itself
+ * changes.
*/
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
__isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
{
+ int was_anchored;
+
tree = isl_schedule_tree_cow(tree);
if (!tree || !options)
goto error;
isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
"not a band node", goto error);
+ was_anchored = isl_schedule_tree_is_anchored(tree);
tree->band = isl_schedule_band_set_ast_build_options(tree->band,
options);
if (!tree->band)
return isl_schedule_tree_free(tree);
+ if (isl_schedule_tree_is_anchored(tree) != was_anchored)
+ tree = isl_schedule_tree_update_anchored(tree);
return tree;
error:
diff --git a/isl_schedule_tree.h b/isl_schedule_tree.h
--- a/isl_schedule_tree.h
+++ b/isl_schedule_tree.h
* 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).
+ *
+ * anchored is set if the node or any of its descendants depends
+ * on its position in the schedule tree.
*/
struct isl_schedule_tree {
int ref;
isl_ctx *ctx;
+ int anchored;
enum isl_schedule_node_type type;
union {
isl_schedule_band *band;
enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
__isl_take isl_schedule_tree *tree2);
+int isl_schedule_tree_is_subtree_anchored(__isl_keep isl_schedule_tree *tree);
+
__isl_give isl_space *isl_schedule_tree_band_get_space(
__isl_keep isl_schedule_tree *tree);
__isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
__isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
__isl_take isl_schedule_tree *tree, int pos,
enum isl_ast_loop_type type);
+enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
+ __isl_keep isl_schedule_tree *tree, int pos);
+__isl_give isl_schedule_tree *
+isl_schedule_tree_band_member_set_isolate_ast_loop_type(
+ __isl_take isl_schedule_tree *tree, int pos,
+ enum isl_ast_loop_type type);
__isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
__isl_keep isl_schedule_tree *tree);
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
diff --git a/test_inputs/codegen/isolate1.c b/test_inputs/codegen/isolate1.c
--- /dev/null
@@ -0,0 +1,8 @@
+{
+ for (int c0 = 0; c0 <= 3; c0 += 1)
+ A(c0);
+ for (int c0 = 4; c0 <= 6; c0 += 1)
+ A(c0);
+ for (int c0 = 7; c0 <= 99; c0 += 1)
+ A(c0);
+}
diff --git a/test_inputs/codegen/isolate1.st b/test_inputs/codegen/isolate1.st
--- /dev/null
@@ -0,0 +1,5 @@
+# Check that the isolate option is adjusted by schedule space scaling
+domain: "{ A[i] : 0 <= i < 100 }"
+child:
+ schedule: "[{ A[i] -> [3i] }]"
+ options: "{ isolate[[] -> [x]] : 10 <= x <= 20 }"
diff --git a/test_inputs/codegen/isolate2.c b/test_inputs/codegen/isolate2.c
--- /dev/null
@@ -0,0 +1,11 @@
+for (int c0 = 0; c0 <= 99; c0 += 1) {
+ if (c0 >= 4 && c0 <= 6) {
+ for (int c1 = 0; c1 <= 99; c1 += 1)
+ A(c0, c1);
+ } else if (c0 >= 7) {
+ for (int c1 = 0; c1 <= 99; c1 += 1)
+ A(c0, c1);
+ } else
+ for (int c1 = 0; c1 <= 99; c1 += 1)
+ A(c0, c1);
+}
diff --git a/test_inputs/codegen/isolate2.st b/test_inputs/codegen/isolate2.st
--- /dev/null
@@ -0,0 +1,7 @@
+# Check that the isolate option is adjusted by schedule space scaling
+domain: "{ A[i,j] : 0 <= i,j < 100 }"
+child:
+ schedule: "[{ A[i,j] -> [3i] }]"
+ child:
+ schedule: "[{ A[i,j] -> [3j] }]"
+ options: "{ isolate[[x] -> [y]] : 10 <= x <= 20 }"
diff --git a/test_inputs/codegen/isolate3.c b/test_inputs/codegen/isolate3.c
--- /dev/null
@@ -0,0 +1,17 @@
+{
+ for (int c0 = 0; c0 <= 9; c0 += 1)
+ A(c0);
+ A(10);
+ A(11);
+ A(12);
+ A(13);
+ A(14);
+ A(15);
+ A(16);
+ A(17);
+ A(18);
+ A(19);
+ A(20);
+ for (int c0 = 21; c0 <= 99; c0 += 1)
+ A(c0);
+}
diff --git a/test_inputs/codegen/isolate3.st b/test_inputs/codegen/isolate3.st
--- /dev/null
@@ -0,0 +1,5 @@
+# Check use of options specific to isolated part
+domain: "{ A[i] : 0 <= i < 100 }"
+child:
+ schedule: "[{ A[i] -> [i] }]"
+ options: "{ isolate[[] -> [x]] : 10 <= x <= 20; [isolate[] -> unroll[x]] }"
diff --git a/test_inputs/codegen/isolate4.c b/test_inputs/codegen/isolate4.c
--- /dev/null
@@ -0,0 +1,13 @@
+{
+ A(0);
+ A(1);
+ A(2);
+ A(3);
+ A(4);
+ for (int c0 = 5; c0 <= 15; c0 += 1)
+ A(c0);
+ A(16);
+ A(17);
+ A(18);
+ A(19);
+}
diff --git a/test_inputs/codegen/isolate4.st b/test_inputs/codegen/isolate4.st
--- /dev/null
@@ -0,0 +1,5 @@
+# Check that generic options are not applied to isolated part
+domain: "{ A[i] : 0 <= i < 20 }"
+child:
+ schedule: "[{ A[i] -> [i] }]"
+ options: "{ isolate[[] -> [x]] : 5 <= x <= 15; unroll[x] }"
diff --git a/test_inputs/codegen/isolate5.c b/test_inputs/codegen/isolate5.c
--- /dev/null
@@ -0,0 +1,23 @@
+{
+ for (int c0 = 0; c0 <= 9; c0 += 1)
+ for (int c1 = 0; c1 <= 1; c1 += 1) {
+ if (c0 % 2 == 0) {
+ A(c0 / 2, c1);
+ } else
+ B((c0 - 1) / 2, c1);
+ }
+ for (int c0 = 10; c0 <= 89; c0 += 1)
+ for (int c1 = 0; c1 <= 1; c1 += 1) {
+ if (c0 % 2 == 0) {
+ A(c0 / 2, c1);
+ } else
+ B((c0 - 1) / 2, c1);
+ }
+ for (int c0 = 90; c0 <= 199; c0 += 1)
+ for (int c1 = 0; c1 <= 1; c1 += 1) {
+ if (c0 % 2 == 0) {
+ A(c0 / 2, c1);
+ } else
+ B((c0 - 1) / 2, c1);
+ }
+}
diff --git a/test_inputs/codegen/isolate5.st b/test_inputs/codegen/isolate5.st
--- /dev/null
@@ -0,0 +1,5 @@
+# Check that use of isolate option prevents shifted stride detection
+domain: "{ A[i,j] : 0 <= i < 100 and 0 <= j < 2; B[i,j] : 0 <= i < 100 and 0 <= j < 2 }"
+child:
+ schedule: "[{ A[i,j] -> [2i]; B[i,j] -> [2i+1] }, { A[i,j] -> [j]; B[i,j] -> [j]}]"
+ options: "{ isolate[[] -> [x, y]] : 10 <= x < 90 }"
diff --git a/test_inputs/codegen/isolate6.c b/test_inputs/codegen/isolate6.c
--- /dev/null
@@ -0,0 +1,26 @@
+{
+ for (int c0 = 0; c0 <= 8; c0 += 1) {
+ for (int c1 = 0; c1 <= -c0 + 8; c1 += 1)
+ for (int c2 = 10 * c0; c2 <= 10 * c0 + 9; c2 += 1) {
+ A(c2, 10 * c1);
+ A(c2, 10 * c1 + 1);
+ A(c2, 10 * c1 + 2);
+ A(c2, 10 * c1 + 3);
+ A(c2, 10 * c1 + 4);
+ A(c2, 10 * c1 + 5);
+ A(c2, 10 * c1 + 6);
+ A(c2, 10 * c1 + 7);
+ A(c2, 10 * c1 + 8);
+ A(c2, 10 * c1 + 9);
+ }
+ for (int c1 = -c0 + 9; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0; c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1; c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+ }
+ for (int c0 = 9; c0 <= 10; c0 += 1)
+ for (int c1 = 0; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0; c2 <= min(10 * c0 + 9, -10 * c1 + 100); c2 += 1)
+ for (int c3 = 10 * c1; c3 <= min(10 * c1 + 9, -c2 + 100); c3 += 1)
+ A(c2, c3);
+}
diff --git a/test_inputs/codegen/isolate6.st b/test_inputs/codegen/isolate6.st
--- /dev/null
@@ -0,0 +1,8 @@
+# Example from the manual
+domain: "{ A[i,j] : 0 <= i,j and i + j <= 100 }"
+child:
+ schedule: "[{ A[i,j] -> [floor(i/10)] }, \
+ { A[i,j] -> [floor(j/10)] }, \
+ { A[i,j] -> [i] }, { A[i,j] -> [j] }]"
+ options: "{ isolate[[] -> [a,b,c,d]] : 0 <= 10a,10b and \
+ 10a+9+10b+9 <= 100; [isolate[] -> unroll[3]] }"