From e395da7986c486a638caee1b55e70acf165ae3b0 Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Wed, 25 Feb 2015 19:34:52 +0000 Subject: [PATCH] Update isl to 0980603 'isl_tab_pip.c: parallel_constraints: drop useless assignment' This update contains: - Fixes of minor issues detected by clang's scan_build - More schedule tree infrastructure additions This update slightly changes the output of our dependence analysis, but these changes are purely syntactially. llvm-svn: 230528 --- polly/lib/External/isl/doc/user.pod | 393 +++++--- polly/lib/External/isl/include/isl/flow.h | 36 + polly/lib/External/isl/include/isl/schedule.h | 21 + polly/lib/External/isl/include/isl/schedule_node.h | 27 + polly/lib/External/isl/isl_aff.c | 7 +- polly/lib/External/isl/isl_arg.c | 2 - polly/lib/External/isl/isl_ast.c | 1 - polly/lib/External/isl/isl_ast_build_expr.c | 4 - polly/lib/External/isl/isl_ast_codegen.c | 6 +- polly/lib/External/isl/isl_constraint.c | 29 +- polly/lib/External/isl/isl_convex_hull.c | 6 +- polly/lib/External/isl/isl_equalities.c | 8 +- polly/lib/External/isl/isl_flow.c | 1064 ++++++++++++++++++-- polly/lib/External/isl/isl_id.c | 4 +- polly/lib/External/isl/isl_input.c | 5 - polly/lib/External/isl/isl_local_space.c | 2 +- polly/lib/External/isl/isl_map_simplify.c | 14 +- polly/lib/External/isl/isl_mat.c | 2 - polly/lib/External/isl/isl_output.c | 18 +- polly/lib/External/isl/isl_range.c | 2 - polly/lib/External/isl/isl_sample.c | 9 +- polly/lib/External/isl/isl_schedule.c | 252 +++++ polly/lib/External/isl/isl_schedule_band.c | 112 +++ polly/lib/External/isl/isl_schedule_band.h | 13 + polly/lib/External/isl/isl_schedule_node.c | 619 +++++++++++- polly/lib/External/isl/isl_schedule_node_private.h | 7 + polly/lib/External/isl/isl_schedule_tree.c | 354 ++++++- polly/lib/External/isl/isl_schedule_tree.h | 20 + polly/lib/External/isl/isl_scheduler.c | 3 +- polly/lib/External/isl/isl_space.c | 8 +- polly/lib/External/isl/isl_tab_pip.c | 10 +- polly/lib/External/isl/isl_test.c | 17 +- polly/lib/External/isl/isl_transitive_closure.c | 2 - polly/lib/External/isl/isl_vertices.c | 8 - polly/test/Dependences/do_pluto_matmult.ll | 7 +- .../Dependences/reduction_multiple_reductions_2.ll | 4 +- .../Dependences/reduction_privatization_deps_2.ll | 4 +- .../Dependences/reduction_privatization_deps_3.ll | 4 +- .../Dependences/reduction_privatization_deps_4.ll | 8 +- .../Dependences/reduction_privatization_deps_5.ll | 8 +- ...eduction_simple_iv_debug_wrapped_dependences.ll | 4 +- .../reduction_simple_privatization_deps_2.ll | 4 +- polly/test/Dependences/sequential_loops.ll | 2 +- 43 files changed, 2786 insertions(+), 344 deletions(-) diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod index 84fd469..e4287ba 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -222,6 +222,20 @@ to compute the sum on the union of definition domains. The original behavior of C was confused and is no longer available. +=item * Band forests have been replaced by schedule trees. + +=item * The function C has been +replaced by the function C. +Note that the may dependence relation returned by +C is the union of +the two dependence relations returned by +C. Similarly for the no source relations. +The function C is still available +for backward compatibility, but it will be removed in the future. + +=item * The function C has been +deprecated. + =back =head1 License @@ -1873,9 +1887,6 @@ using the following functions. __isl_give isl_set *isl_set_add_constraint( __isl_take isl_set *set, __isl_take isl_constraint *constraint); - __isl_give isl_basic_set *isl_basic_set_drop_constraint( - __isl_take isl_basic_set *bset, - __isl_take isl_constraint *constraint); For example, to create a set containing the even integers between 10 and 42, you would use the following code. @@ -7283,6 +7294,14 @@ C objects may be copied and freed using the following functions. __isl_null isl_schedule *isl_schedule_free( __isl_take isl_schedule *sched); +The following functions checks whether two C objects +are obviously the same. + + #include + int isl_schedule_plain_is_equal( + __isl_keep isl_schedule *schedule1, + __isl_keep isl_schedule *schedule2); + The domain of the schedule, i.e., the domain described by the root node, can be obtained using the following function. @@ -7290,6 +7309,64 @@ can be obtained using the following function. __isl_give isl_union_set *isl_schedule_get_domain( __isl_keep isl_schedule *schedule); +An extra top-level band node (right underneath the domain node) can +be introduced into the schedule using the following function. + + #include + __isl_give isl_schedule * + isl_schedule_insert_partial_schedule( + __isl_take isl_schedule *schedule, + __isl_take isl_multi_union_pw_aff *partial); + +A schedule that combines two schedules either in the given +order or in an arbitrary order, i.e., with an C +or an C node, +can be created using the following functions. + + #include + __isl_give isl_schedule *isl_schedule_sequence( + __isl_take isl_schedule *schedule1, + __isl_take isl_schedule *schedule2); + __isl_give isl_schedule *isl_schedule_set( + __isl_take isl_schedule *schedule1, + __isl_take isl_schedule *schedule2); + +The domains of the two input schedules need to be disjoint. + +The following function can be used to restrict the domain +of a schedule to be a subset of the given union set. +This operation may remove nodes in the tree that have become +redundant. + + #include + __isl_give isl_schedule *isl_schedule_intersect_domain( + __isl_take isl_schedule *schedule, + __isl_take isl_union_set *domain); + +The following function resets the user pointers on all parameter +and tuple identifiers referenced by the nodes of the given schedule. + + #include + __isl_give isl_schedule *isl_schedule_reset_user( + __isl_take isl_schedule *schedule); + +The following function aligns the parameters of all nodes +in the given schedule to the given space. + + #include + __isl_give isl_schedule *isl_schedule_align_params( + __isl_take isl_schedule *schedule, + __isl_take isl_space *space); + +The following function allows the user to plug in a given function +in the iteration domains. + + #include + __isl_give isl_schedule * + isl_schedule_pullback_union_pw_multi_aff( + __isl_take isl_schedule *schedule, + __isl_take isl_union_pw_multi_aff *upma); + An C representation of the schedule can be obtained from an C using the following function. @@ -7347,6 +7424,14 @@ Schedule nodes can be copied and freed using the following functions. __isl_null isl_schedule_node *isl_schedule_node_free( __isl_take isl_schedule_node *node); +The following functions can be used to check if two schedule +nodes point to the same position in the same schedule. + + #include + int isl_schedule_node_is_equal( + __isl_keep isl_schedule_node *node1, + __isl_keep isl_schedule_node *node2); + The following properties can be obtained from a schedule node. #include @@ -7373,6 +7458,11 @@ exists. __isl_keep isl_schedule_node *node); __isl_give isl_schedule_node *isl_schedule_node_parent( __isl_take isl_schedule_node *node); + __isl_give isl_schedule_node *isl_schedule_node_root( + __isl_take isl_schedule_node *node); + __isl_give isl_schedule_node *isl_schedule_node_ancestor( + __isl_take isl_schedule_node *node, + int generation); int isl_schedule_node_n_children( __isl_keep isl_schedule_node *node); __isl_give isl_schedule_node *isl_schedule_node_child( @@ -7392,18 +7482,33 @@ exists. isl_schedule_node_next_sibling( __isl_take isl_schedule_node *node); +For C, the ancestor of generation 0 +is the node itself, the ancestor of generation 1 is its parent and so on. + It is also possible to query the number of ancestors of a node, the position of the current node -within the children of its parent or to obtain a copy of a given +within the children of its parent, the position of the subtree +containing a node within the children of an ancestor +or to obtain a copy of a given child without destroying the current node. +Given two nodes that point to the same schedule, their closest +shared ancestor can be obtained using +C. #include int isl_schedule_node_get_tree_depth( __isl_keep isl_schedule_node *node); int isl_schedule_node_get_child_position( __isl_keep isl_schedule_node *node); + int isl_schedule_node_get_ancestor_child_position( + __isl_keep isl_schedule_node *node, + __isl_keep isl_schedule_node *ancestor); __isl_give isl_schedule_node *isl_schedule_node_get_child( __isl_keep isl_schedule_node *node, int pos); + __isl_give isl_schedule_node * + isl_schedule_node_get_shared_ancestor( + __isl_keep isl_schedule_node *node1, + __isl_keep isl_schedule_node *node2); All nodes in a schedule tree or all descendants of a specific node (including the node) can be visited @@ -7428,6 +7533,16 @@ of the given node should be visited. In particular, if the callback returns a positive value, then the children are visited, but if the callback returns zero, then the children are not visited. +The ancestors of a node in a schedule tree can be visited from +the root down to and including the parent of the node using +the following function. + + #include + int isl_schedule_node_foreach_ancestor_top_down( + __isl_keep isl_schedule_node *node, + int (*fn)(__isl_keep isl_schedule_node *node, + void *user), void *user); + The following functions allows for a depth-first post-order traversal of the nodes in a schedule tree or of the descendants of a specific node (including the node @@ -7454,6 +7569,43 @@ It is the responsibility of the user to ensure that this does not lead to an infinite loop. It is safest to always return a pointer to the same position (same ancestors and child positions) as the input node. +The following function removes a node (along with its descendants) +from a schedule tree and returns a pointer to the leaf at the +same position in the updated tree. +It is not allowed to remove the root of a schedule tree or +a child of a set or sequence node. + + #include + __isl_give isl_schedule_node *isl_schedule_node_cut( + __isl_take isl_schedule_node *node); + +The following function removes a single node +from a schedule tree and returns a pointer to the child +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. + + #include + __isl_give isl_schedule_node *isl_schedule_node_delete( + __isl_take isl_schedule_node *node); + +The following function resets the user pointers on all parameter +and tuple identifiers referenced by the given schedule node. + + #include + __isl_give isl_schedule_node *isl_schedule_node_reset_user( + __isl_take isl_schedule_node *node); + +The following function aligns the parameters of the given schedule +node to the given space. + + #include + __isl_give isl_schedule_node * + isl_schedule_node_align_params( + __isl_take isl_schedule_node *node, + __isl_take isl_space *space); + Several node types have their own functions for querying (and in some cases setting) some node type specific properties. @@ -7530,6 +7682,15 @@ The function C returns a representation of the partial schedule defined by the subtree rooted at the given node. +The total number of outer band members of given node, i.e., +the shared output dimension of the maps in the result +of C can be obtained +using the following function. + + #include + int isl_schedule_node_get_schedule_depth( + __isl_keep isl_schedule_node *node); + The following function returns the union of universes in the spaces that contain elements that reach the given node. @@ -7666,6 +7827,96 @@ then memory based dependence analysis is performed. If, on the other hand, all sources are I accesses, then value based dependence analysis is performed. +=head3 High-level Interface + +A high-level interface to dependence analysis is provided +by the following function. + + #include + __isl_give isl_union_flow * + isl_union_access_info_compute_flow( + __isl_take isl_union_access_info *access); + +The input C object describes the sink +access relations, the source access relations and a schedule, +while the output C object describes +the resulting dependence relations and the subsets of the +sink relations for which no source was found. + +An C is created, modified and freed using +the following functions. + + #include + __isl_give isl_union_access_info * + isl_union_access_info_from_sink( + __isl_take isl_union_map *sink); + __isl_give isl_union_access_info * + isl_union_access_info_set_must_source( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *must_source); + __isl_give isl_union_access_info * + isl_union_access_info_set_may_source( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *may_source); + __isl_give isl_union_access_info * + isl_union_access_info_set_schedule( + __isl_take isl_union_access_info *access, + __isl_take isl_schedule *schedule); + __isl_give isl_union_access_info * + isl_union_access_info_set_schedule_map( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *schedule_map); + __isl_null isl_union_access_info * + isl_union_access_info_free( + __isl_take isl_union_access_info *access); + +The may sources set by C +do not need to include the must sources set by +C as a subset. +The user is free not to call one (or both) of these functions, +in which case the corresponding set is kept to its empty default. +Similarly, the default schedule initialized by +C is empty. +The current schedule is determined by the last call to either +C or +C. +The domain of the schedule corresponds to the domains of +the access relations. In particular, the domains of the access +relations are effectively intersected with the domain of the schedule +and only the resulting accesses are considered by the dependence analysis. + +The output of C can be examined +and freed using the following functions. + + #include + __isl_give isl_union_map *isl_union_flow_get_must_dependence( + __isl_keep isl_union_flow *flow); + __isl_give isl_union_map *isl_union_flow_get_may_dependence( + __isl_keep isl_union_flow *flow); + __isl_give isl_union_map *isl_union_flow_get_must_no_source( + __isl_keep isl_union_flow *flow); + __isl_give isl_union_map *isl_union_flow_get_may_no_source( + __isl_keep isl_union_flow *flow); + __isl_null isl_union_flow *isl_union_flow_free( + __isl_take isl_union_flow *flow); + +The relation returned by C +relates domain elements of must sources to domain elements of the sink. +The relation returned by C +relates domain elements of must or may sources to domain elements of the sink +and includes the previous relation as a subset. +The relation returned by C is the subset +of the sink relation for which no dependences have been found. +The relation returned by C is the subset +of the sink relation for which no definite dependences have been found. +That is, it contains those sink access that do not contribute to any +of the elements in the relation returned +by C. + +=head3 Low-level Interface + +A lower-level interface is provided by the following functions. + #include typedef int (*isl_access_level_before)(void *first, void *second); @@ -7751,31 +8002,7 @@ source and if it is not followed by any I sources. After finishing with an C, the user should call C to free all associated memory. -A higher-level interface to dependence analysis is provided -by the following function. - - #include - - int isl_union_map_compute_flow(__isl_take isl_union_map *sink, - __isl_take isl_union_map *must_source, - __isl_take isl_union_map *may_source, - __isl_take isl_union_map *schedule, - __isl_give isl_union_map **must_dep, - __isl_give isl_union_map **may_dep, - __isl_give isl_union_map **must_no_source, - __isl_give isl_union_map **may_no_source); - -The arrays are identified by the tuple names of the ranges -of the accesses. The iteration domains by the tuple names -of the domains of the accesses and of the schedule. -The relative order of the iteration domains is given by the -schedule. The relations returned through C -and C are subsets of C. -Any of C, C, C -or C may be C, but a C value for -any of the other arguments is treated as an error. - -=head3 Interaction with Dependence Analysis +=head3 Interaction with the Low-level Interface During the dependence analysis, we frequently need to perform the following operation. Given a relation between sink iterations @@ -7976,114 +8203,6 @@ The generated schedule represents a schedule tree. For more information on schedule trees, see L. -A representation of the schedule as a forest of bands can be obtained -using the following function. - - __isl_give isl_band_list *isl_schedule_get_band_forest( - __isl_keep isl_schedule *schedule); - -If the input schedule is represented by a schedule tree, then a call -to C replaces the internal schedule tree -representation by a band forest representation. - -The individual bands can be visited in depth-first post-order -using the following function. - - #include - int isl_schedule_foreach_band( - __isl_keep isl_schedule *sched, - int (*fn)(__isl_keep isl_band *band, void *user), - void *user); - -The list can be manipulated as explained in L<"Lists">. -The bands inside the list can be copied and freed using the following -functions. - - #include - __isl_give isl_band *isl_band_copy( - __isl_keep isl_band *band); - __isl_null isl_band *isl_band_free( - __isl_take isl_band *band); - -Each band contains zero or more scheduling dimensions. -These are referred to as the members of the band. -The section of the schedule that corresponds to the band is -referred to as the partial schedule of the band. -For those nodes that participate in a band, the outer scheduling -dimensions form the prefix schedule, while the inner scheduling -dimensions form the suffix schedule. -That is, if we take a cut of the band forest, then the union of -the concatenations of the prefix, partial and suffix schedules of -each band in the cut is equal to the entire schedule (modulo -some possible padding at the end with zero scheduling dimensions). -The properties of a band can be inspected using the following functions. - - #include - int isl_band_has_children(__isl_keep isl_band *band); - __isl_give isl_band_list *isl_band_get_children( - __isl_keep isl_band *band); - - __isl_give isl_union_map *isl_band_get_prefix_schedule( - __isl_keep isl_band *band); - __isl_give isl_union_map *isl_band_get_partial_schedule( - __isl_keep isl_band *band); - __isl_give isl_union_map *isl_band_get_suffix_schedule( - __isl_keep isl_band *band); - - int isl_band_n_member(__isl_keep isl_band *band); - int isl_band_member_is_coincident( - __isl_keep isl_band *band, int pos); - - int isl_band_list_foreach_band( - __isl_keep isl_band_list *list, - int (*fn)(__isl_keep isl_band *band, void *user), - void *user); - -Note that a scheduling dimension is considered to be ``coincident'' -if it satisfies the coincidence constraints within its band. -That is, if the dependence distances of the coincidence -constraints are all zero in that direction (for fixed -iterations of outer bands). -Like C, -the function C calls C on the bands -in depth-first post-order. - -A band can be tiled using the following function. - - #include - int isl_band_tile(__isl_keep isl_band *band, - __isl_take isl_vec *sizes); - - int isl_options_set_tile_scale_tile_loops(isl_ctx *ctx, - int val); - int isl_options_get_tile_scale_tile_loops(isl_ctx *ctx); - int isl_options_set_tile_shift_point_loops(isl_ctx *ctx, - int val); - int isl_options_get_tile_shift_point_loops(isl_ctx *ctx); - -The C function tiles the band using the given tile sizes -inside its schedule. -A new child band is created to represent the point loops and it is -inserted between the modified band and its children. -The C option specifies whether the tile -loops iterators should be scaled by the tile sizes. -If the C option is set, then the point loops -are shifted to start at zero. - -A band can be split into two nested bands using the following function. - - int isl_band_split(__isl_keep isl_band *band, int pos); - -The resulting outer band contains the first C dimensions of C -while the inner band contains the remaining dimensions. - -A representation of the band can be printed using - - #include - __isl_give isl_printer *isl_printer_print_band( - __isl_take isl_printer *p, - __isl_keep isl_band *band); - =head3 Options #include diff --git a/polly/lib/External/isl/include/isl/flow.h b/polly/lib/External/isl/include/isl/flow.h index 2aee194..5e04421 100644 --- a/polly/lib/External/isl/include/isl/flow.h +++ b/polly/lib/External/isl/include/isl/flow.h @@ -5,6 +5,7 @@ #include #include #include +#include #if defined(__cplusplus) extern "C" { @@ -62,6 +63,41 @@ void isl_flow_free(__isl_take isl_flow *deps); isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps); +struct isl_union_access_info; +typedef struct isl_union_access_info isl_union_access_info; +struct isl_union_flow; +typedef struct isl_union_flow isl_union_flow; + +__isl_give isl_union_access_info *isl_union_access_info_from_sink( + __isl_take isl_union_map *sink); +__isl_give isl_union_access_info *isl_union_access_info_set_must_source( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *must_source); +__isl_give isl_union_access_info *isl_union_access_info_set_may_source( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *may_source); +__isl_give isl_union_access_info *isl_union_access_info_set_schedule( + __isl_take isl_union_access_info *access, + __isl_take isl_schedule *schedule); +__isl_give isl_union_access_info *isl_union_access_info_set_schedule_map( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *schedule_map); +__isl_null isl_union_access_info *isl_union_access_info_free( + __isl_take isl_union_access_info *access); + +__isl_give isl_union_flow *isl_union_access_info_compute_flow( + __isl_take isl_union_access_info *access); + +__isl_give isl_union_map *isl_union_flow_get_must_dependence( + __isl_keep isl_union_flow *flow); +__isl_give isl_union_map *isl_union_flow_get_may_dependence( + __isl_keep isl_union_flow *flow); +__isl_give isl_union_map *isl_union_flow_get_must_no_source( + __isl_keep isl_union_flow *flow); +__isl_give isl_union_map *isl_union_flow_get_may_no_source( + __isl_keep isl_union_flow *flow); +__isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow); + int isl_union_map_compute_flow(__isl_take isl_union_map *sink, __isl_take isl_union_map *must_source, __isl_take isl_union_map *may_source, diff --git a/polly/lib/External/isl/include/isl/schedule.h b/polly/lib/External/isl/include/isl/schedule.h index 045c5f8..cc4cacd 100644 --- a/polly/lib/External/isl/include/isl/schedule.h +++ b/polly/lib/External/isl/include/isl/schedule.h @@ -4,6 +4,7 @@ #include #include #include +#include #include #include #include @@ -82,6 +83,8 @@ __isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched); __isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched); isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *sched); +int isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1, + __isl_keep isl_schedule *schedule2); __isl_give isl_schedule_node *isl_schedule_get_root( __isl_keep isl_schedule *schedule); @@ -95,6 +98,24 @@ __isl_give isl_schedule *isl_schedule_map_schedule_node( __isl_give isl_schedule_node *(*fn)( __isl_take isl_schedule_node *node, void *user), void *user); +__isl_give isl_schedule *isl_schedule_insert_partial_schedule( + __isl_take isl_schedule *schedule, + __isl_take isl_multi_union_pw_aff *partial); +__isl_give isl_schedule *isl_schedule_sequence( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2); +__isl_give isl_schedule *isl_schedule_set( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2); +__isl_give isl_schedule *isl_schedule_intersect_domain( + __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain); + +__isl_give isl_schedule *isl_schedule_reset_user( + __isl_take isl_schedule *schedule); +__isl_give isl_schedule *isl_schedule_align_params( + __isl_take isl_schedule *schedule, __isl_take isl_space *space); +__isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff( + __isl_take isl_schedule *schedule, + __isl_take isl_union_pw_multi_aff *upma); + __isl_give isl_band_list *isl_schedule_get_band_forest( __isl_keep isl_schedule *schedule); diff --git a/polly/lib/External/isl/include/isl/schedule_node.h b/polly/lib/External/isl/include/isl/schedule_node.h index 531314f..f9f82a3 100644 --- a/polly/lib/External/isl/include/isl/schedule_node.h +++ b/polly/lib/External/isl/include/isl/schedule_node.h @@ -18,6 +18,9 @@ __isl_give isl_schedule_node *isl_schedule_node_copy( __isl_null isl_schedule_node *isl_schedule_node_free( __isl_take isl_schedule_node *node); +int isl_schedule_node_is_equal(__isl_keep isl_schedule_node *node1, + __isl_keep isl_schedule_node *node2); + isl_ctx *isl_schedule_node_get_ctx(__isl_keep isl_schedule_node *node); enum isl_schedule_node_type isl_schedule_node_get_type( __isl_keep isl_schedule_node *node); @@ -28,6 +31,9 @@ __isl_give isl_schedule *isl_schedule_node_get_schedule( int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node *node, int (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user); +int isl_schedule_node_foreach_ancestor_top_down( + __isl_keep isl_schedule_node *node, + int (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user); __isl_give isl_schedule_node *isl_schedule_node_map_descendant( __isl_take isl_schedule_node *node, __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node, @@ -40,11 +46,21 @@ int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node *node); int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node *node); int isl_schedule_node_n_children(__isl_keep isl_schedule_node *node); int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node *node); +int isl_schedule_node_get_ancestor_child_position( + __isl_keep isl_schedule_node *node, + __isl_keep isl_schedule_node *ancestor); __isl_give isl_schedule_node *isl_schedule_node_get_child( __isl_keep isl_schedule_node *node, int pos); +__isl_give isl_schedule_node *isl_schedule_node_get_shared_ancestor( + __isl_keep isl_schedule_node *node1, + __isl_keep isl_schedule_node *node2); +__isl_give isl_schedule_node *isl_schedule_node_root( + __isl_take isl_schedule_node *node); __isl_give isl_schedule_node *isl_schedule_node_parent( __isl_take isl_schedule_node *node); +__isl_give isl_schedule_node *isl_schedule_node_ancestor( + __isl_take isl_schedule_node *node, int generation); __isl_give isl_schedule_node *isl_schedule_node_child( __isl_take isl_schedule_node *node, int pos); __isl_give isl_schedule_node *isl_schedule_node_first_child( @@ -90,6 +106,7 @@ __isl_give isl_union_set *isl_schedule_node_domain_get_domain( __isl_give isl_union_set *isl_schedule_node_filter_get_filter( __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_universe_domain( __isl_keep isl_schedule_node *node); __isl_give isl_union_pw_multi_aff * @@ -112,6 +129,16 @@ __isl_give isl_schedule_node *isl_schedule_node_insert_set( __isl_take isl_schedule_node *node, __isl_take isl_union_set_list *filters); +__isl_give isl_schedule_node *isl_schedule_node_cut( + __isl_take isl_schedule_node *node); +__isl_give isl_schedule_node *isl_schedule_node_delete( + __isl_take isl_schedule_node *node); + +__isl_give isl_schedule_node *isl_schedule_node_reset_user( + __isl_take isl_schedule_node *node); +__isl_give isl_schedule_node *isl_schedule_node_align_params( + __isl_take isl_schedule_node *node, __isl_take isl_space *space); + __isl_give isl_printer *isl_printer_print_schedule_node( __isl_take isl_printer *p, __isl_keep isl_schedule_node *node); void isl_schedule_node_dump(__isl_keep isl_schedule_node *node); diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c index ad3c529..28cd157 100644 --- a/polly/lib/External/isl/isl_aff.c +++ b/polly/lib/External/isl/isl_aff.c @@ -1459,12 +1459,10 @@ static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b) static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff) { int i, j, n; - unsigned off; if (!aff) return NULL; - off = isl_local_space_offset(aff->ls, isl_dim_div); n = isl_aff_dim(aff, isl_dim_div); for (i = 1; i < n; ++i) { for (j = i - 1; j >= 0; --j) { @@ -4908,7 +4906,7 @@ static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride( map = set; else map = isl_set_unwrap(set); - pma = isl_pw_multi_aff_from_map(set); + pma = isl_pw_multi_aff_from_map(map); if (!is_set) { space = isl_pw_multi_aff_get_domain_space(pma); @@ -6569,13 +6567,12 @@ error: static __isl_give isl_pw_aff *isl_multi_pw_aff_apply_aff_aligned( __isl_take isl_multi_pw_aff *mpa, __isl_take isl_aff *aff) { - int i, n_param, n_in, n_div; + int i, n_in, n_div; isl_space *space; isl_val *v; isl_pw_aff *pa; isl_aff *tmp; - n_param = isl_aff_dim(aff, isl_dim_param); n_in = isl_aff_dim(aff, isl_dim_in); n_div = isl_aff_dim(aff, isl_dim_div); diff --git a/polly/lib/External/isl/isl_arg.c b/polly/lib/External/isl/isl_arg.c index fefb67d..e23911a 100644 --- a/polly/lib/External/isl/isl_arg.c +++ b/polly/lib/External/isl/isl_arg.c @@ -386,7 +386,6 @@ static void print_default(struct isl_arg *decl, const char *def, int pos) printf("\n%30s", ""); else printf("%*s", 30 - pos, ""); - pos = 0; } else { if (pos + len >= 48) printf("\n%30s", ""); @@ -456,7 +455,6 @@ static void print_default_flags(struct isl_arg *decl, void *opt, int pos) printf("\n%30s", ""); else printf("%*s", 30 - pos, ""); - pos = 0; } else { if (pos + len >= 48) printf("\n%30s", ""); diff --git a/polly/lib/External/isl/isl_ast.c b/polly/lib/External/isl/isl_ast.c index 0d77162..e701f1e 100644 --- a/polly/lib/External/isl/isl_ast.c +++ b/polly/lib/External/isl/isl_ast.c @@ -351,7 +351,6 @@ int isl_ast_expr_is_equal(__isl_keep isl_ast_expr *expr1, int equal; equal = isl_ast_expr_is_equal(expr1->u.op.args[i], expr2->u.op.args[i]); - return 0; if (equal < 0 || !equal) return equal; } diff --git a/polly/lib/External/isl/isl_ast_build_expr.c b/polly/lib/External/isl/isl_ast_build_expr.c index 2042ac8..3669252 100644 --- a/polly/lib/External/isl/isl_ast_build_expr.c +++ b/polly/lib/External/isl/isl_ast_build_expr.c @@ -332,14 +332,12 @@ static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v, __isl_keep isl_aff *aff, __isl_keep isl_val *d, __isl_keep isl_ast_build *build) { - isl_ctx *ctx; isl_ast_expr *expr; isl_ast_expr *c; if (!aff) return NULL; - ctx = isl_aff_get_ctx(aff); expr = isl_ast_expr_from_aff(isl_aff_copy(aff), build); c = isl_ast_expr_from_val(isl_val_copy(d)); @@ -443,7 +441,6 @@ static __isl_give isl_ast_expr *isl_ast_expr_add_term( static __isl_give isl_ast_expr *isl_ast_expr_add_int( __isl_take isl_ast_expr *expr, __isl_take isl_val *v) { - isl_ctx *ctx; isl_ast_expr *expr_int; if (!expr || !v) @@ -454,7 +451,6 @@ static __isl_give isl_ast_expr *isl_ast_expr_add_int( return expr; } - ctx = isl_ast_expr_get_ctx(expr); if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) { v = isl_val_neg(v); expr_int = isl_ast_expr_from_val(v); diff --git a/polly/lib/External/isl/isl_ast_codegen.c b/polly/lib/External/isl/isl_ast_codegen.c index 7159d7a..05e0501 100644 --- a/polly/lib/External/isl/isl_ast_codegen.c +++ b/polly/lib/External/isl/isl_ast_codegen.c @@ -882,7 +882,7 @@ static int pw_aff_constant_is_negative(__isl_take isl_pw_aff *pa, void *user) r = isl_pw_aff_foreach_piece(pa, &aff_constant_is_negative, user); isl_pw_aff_free(pa); - return *neg ? 0 : -1; + return (*neg && r >= 0) ? 0 : -1; } /* Does each element in "list" have a negative constant term? @@ -2571,7 +2571,6 @@ static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains, { int i, n; int depth; - isl_ctx *ctx; isl_aff *lower; isl_multi_aff *expansion; isl_basic_map *bmap; @@ -2581,7 +2580,6 @@ static __isl_give isl_set *do_unroll(struct isl_codegen_domains *domains, if (!domain) return isl_set_free(class_domain); - ctx = isl_set_get_ctx(domain); depth = isl_ast_build_get_depth(domains->build); build = isl_ast_build_copy(domains->build); domain = isl_ast_build_eliminate_inner(build, domain); @@ -3360,14 +3358,12 @@ static __isl_give isl_ast_graft_list *generate_shift_component( isl_ast_graft_list *list; int first; int depth; - isl_ctx *ctx; isl_val *val; isl_multi_val *mv; isl_space *space; isl_multi_aff *ma, *zero; isl_union_map *executed; - ctx = isl_ast_build_get_ctx(build); depth = isl_ast_build_get_depth(build); first = first_offset(domain, order, n, build); diff --git a/polly/lib/External/isl/isl_constraint.c b/polly/lib/External/isl/isl_constraint.c index 049175b..a6e6add 100644 --- a/polly/lib/External/isl/isl_constraint.c +++ b/polly/lib/External/isl/isl_constraint.c @@ -669,11 +669,9 @@ __isl_give isl_constraint *isl_constraint_set_coefficient_si( * In particular, this means that the local spaces of "bset" and * "constraint" need to be the same. * - * Since the given constraint may actually be a pointer into the bset, - * we have to be careful not to reorder the constraints as the user - * may be holding on to other constraints from the same bset. - * This should be cleaned up when the internal representation of - * isl_constraint is changed to use isl_aff. + * We manually set ISL_BASIC_SET_FINAL instead of calling + * isl_basic_set_finalize because this function is called by CLooG, + * which does not expect any variables to disappear. */ __isl_give isl_basic_set *isl_basic_set_drop_constraint( __isl_take isl_basic_set *bset, __isl_take isl_constraint *constraint) @@ -684,6 +682,7 @@ __isl_give isl_basic_set *isl_basic_set_drop_constraint( unsigned total; isl_local_space *ls1; int equal; + int equality; if (!bset || !constraint) goto error; @@ -698,7 +697,12 @@ __isl_give isl_basic_set *isl_basic_set_drop_constraint( return bset; } - if (isl_constraint_is_equality(constraint)) { + bset = isl_basic_set_cow(bset); + if (!bset) + goto error; + + equality = isl_constraint_is_equality(constraint); + if (equality) { n = bset->n_eq; row = bset->eq; } else { @@ -707,11 +711,18 @@ __isl_give isl_basic_set *isl_basic_set_drop_constraint( } total = isl_constraint_dim(constraint, isl_dim_all); - for (i = 0; i < n; ++i) - if (isl_seq_eq(row[i], constraint->v->el, 1 + total)) - isl_seq_clr(row[i], 1 + total); + for (i = 0; i < n; ++i) { + if (!isl_seq_eq(row[i], constraint->v->el, 1 + total)) + continue; + if (equality && isl_basic_set_drop_equality(bset, i) < 0) + goto error; + if (!equality && isl_basic_set_drop_inequality(bset, i) < 0) + goto error; + break; + } isl_constraint_free(constraint); + ISL_F_SET(bset, ISL_BASIC_SET_FINAL); return bset; error: isl_constraint_free(constraint); diff --git a/polly/lib/External/isl/isl_convex_hull.c b/polly/lib/External/isl/isl_convex_hull.c index 419c22e8..62d1b29 100644 --- a/polly/lib/External/isl/isl_convex_hull.c +++ b/polly/lib/External/isl/isl_convex_hull.c @@ -1315,12 +1315,12 @@ static struct isl_basic_set *convex_hull_pair_pointed( if (!bset1 || !bset2) goto error; - ctx = bset1->ctx; + ctx = isl_basic_set_get_ctx(bset1); dir = valid_direction(isl_basic_set_copy(bset1), isl_basic_set_copy(bset2)); if (!dir) goto error; - T = isl_mat_alloc(bset1->ctx, dir->size, dir->size); + T = isl_mat_alloc(ctx, dir->size, dir->size); if (!T) goto error; isl_seq_cpy(T->row[0], dir->block.data, dir->size); @@ -1926,14 +1926,12 @@ struct isl_basic_map *isl_map_convex_hull(struct isl_map *map) struct isl_basic_set *affine_hull = NULL; struct isl_basic_map *convex_hull = NULL; struct isl_set *set = NULL; - struct isl_ctx *ctx; map = isl_map_detect_equalities(map); map = isl_map_align_divs(map); if (!map) goto error; - ctx = map->ctx; if (map->n == 0) { convex_hull = isl_basic_map_empty_like_map(map); isl_map_free(map); diff --git a/polly/lib/External/isl/isl_equalities.c b/polly/lib/External/isl/isl_equalities.c index e257f70..6256faa 100644 --- a/polly/lib/External/isl/isl_equalities.c +++ b/polly/lib/External/isl/isl_equalities.c @@ -638,10 +638,10 @@ int isl_basic_set_dim_residue_class(struct isl_basic_set *bset, return 0; } - ctx = bset->ctx; + ctx = isl_basic_set_get_ctx(bset); total = isl_basic_set_total_dim(bset); nparam = isl_basic_set_n_param(bset); - H = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq, 1, total); + H = isl_mat_sub_alloc6(ctx, bset->eq, 0, bset->n_eq, 1, total); H = isl_mat_left_hermite(H, 0, &U, NULL); if (!H) return -1; @@ -657,11 +657,11 @@ int isl_basic_set_dim_residue_class(struct isl_basic_set *bset, return 0; } - C = isl_mat_alloc(bset->ctx, 1+bset->n_eq, 1); + C = isl_mat_alloc(ctx, 1 + bset->n_eq, 1); if (!C) goto error; isl_int_set_si(C->row[0][0], 1); - isl_mat_sub_neg(C->ctx, C->row+1, bset->eq, bset->n_eq, 0, 0, 1); + isl_mat_sub_neg(ctx, C->row + 1, bset->eq, bset->n_eq, 0, 0, 1); H1 = isl_mat_sub_alloc(H, 0, H->n_row, 0, H->n_row); H1 = isl_mat_lin_to_aff(H1); C = isl_mat_inverse_product(H1, C); diff --git a/polly/lib/External/isl/isl_flow.c b/polly/lib/External/isl/isl_flow.c index 36ba0ed..80f20fe 100644 --- a/polly/lib/External/isl/isl_flow.c +++ b/polly/lib/External/isl/isl_flow.c @@ -3,6 +3,7 @@ * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * Copyright 2012 Universiteit Leiden + * Copyright 2014 Ecole Normale Superieure * * Use of this software is governed by the MIT license * @@ -12,11 +13,13 @@ * B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ #include #include #include +#include #include enum isl_restriction_type { @@ -1167,13 +1170,440 @@ error: return NULL; } -struct isl_compute_flow_data { +/* This structure represents the input for a dependence analysis computation. + * + * "sink" represents the sink accesses. + * "must_source" represents the definite source accesses. + * "may_source" represents the possible source accesses. + * + * "schedule" or "schedule_map" represents the execution order. + * Exactly one of these fields should be NULL. The other field + * determines the execution order. + * + * The domains of these four maps refer to the same iteration spaces(s). + * The ranges of the first three maps also refer to the same data space(s). + * + * After a call to isl_union_access_info_introduce_schedule, + * the "schedule_map" field no longer contains useful information. + */ +struct isl_union_access_info { + isl_union_map *sink; isl_union_map *must_source; isl_union_map *may_source; + + isl_schedule *schedule; + isl_union_map *schedule_map; +}; + +/* Free "access" and return NULL. + */ +__isl_null isl_union_access_info *isl_union_access_info_free( + __isl_take isl_union_access_info *access) +{ + if (!access) + return NULL; + + isl_union_map_free(access->sink); + isl_union_map_free(access->must_source); + isl_union_map_free(access->may_source); + isl_schedule_free(access->schedule); + isl_union_map_free(access->schedule_map); + free(access); + + return NULL; +} + +/* Return the isl_ctx to which "access" belongs. + */ +isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access) +{ + return access ? isl_union_map_get_ctx(access->sink) : NULL; +} + +/* Create a new isl_union_access_info with the given sink accesses and + * and no source accesses or schedule information. + * + * By default, we use the schedule field of the isl_union_access_info, + * but this may be overridden by a call + * to isl_union_access_info_set_schedule_map. + */ +__isl_give isl_union_access_info *isl_union_access_info_from_sink( + __isl_take isl_union_map *sink) +{ + isl_ctx *ctx; + isl_space *space; + isl_union_map *empty; + isl_union_access_info *access; + + if (!sink) + return NULL; + ctx = isl_union_map_get_ctx(sink); + access = isl_alloc_type(ctx, isl_union_access_info); + if (!access) + goto error; + + space = isl_union_map_get_space(sink); + empty = isl_union_map_empty(isl_space_copy(space)); + access->sink = sink; + access->must_source = isl_union_map_copy(empty); + access->may_source = empty; + access->schedule = isl_schedule_empty(space); + access->schedule_map = NULL; + + if (!access->sink || !access->must_source || + !access->may_source || !access->schedule) + return isl_union_access_info_free(access); + + return access; +error: + isl_union_map_free(sink); + return NULL; +} + +/* Replace the definite source accesses of "access" by "must_source". + */ +__isl_give isl_union_access_info *isl_union_access_info_set_must_source( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *must_source) +{ + if (!access || !must_source) + goto error; + + isl_union_map_free(access->must_source); + access->must_source = must_source; + + return access; +error: + isl_union_access_info_free(access); + isl_union_map_free(must_source); + return NULL; +} + +/* Replace the possible source accesses of "access" by "may_source". + */ +__isl_give isl_union_access_info *isl_union_access_info_set_may_source( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *may_source) +{ + if (!access || !may_source) + goto error; + + isl_union_map_free(access->may_source); + access->may_source = may_source; + + return access; +error: + isl_union_access_info_free(access); + isl_union_map_free(may_source); + return NULL; +} + +/* Replace the schedule of "access" by "schedule". + * Also free the schedule_map in case it was set last. + */ +__isl_give isl_union_access_info *isl_union_access_info_set_schedule( + __isl_take isl_union_access_info *access, + __isl_take isl_schedule *schedule) +{ + if (!access || !schedule) + goto error; + + access->schedule_map = isl_union_map_free(access->schedule_map); + isl_schedule_free(access->schedule); + access->schedule = schedule; + + return access; +error: + isl_union_access_info_free(access); + isl_schedule_free(schedule); + return NULL; +} + +/* Replace the schedule map of "access" by "schedule_map". + * Also free the schedule in case it was set last. + */ +__isl_give isl_union_access_info *isl_union_access_info_set_schedule_map( + __isl_take isl_union_access_info *access, + __isl_take isl_union_map *schedule_map) +{ + if (!access || !schedule_map) + goto error; + + isl_union_map_free(access->schedule_map); + access->schedule = isl_schedule_free(access->schedule); + access->schedule_map = schedule_map; + + return access; +error: + isl_union_access_info_free(access); + isl_union_map_free(schedule_map); + return NULL; +} + +/* Update the fields of "access" such that they all have the same parameters, + * keeping in mind that the schedule_map field may be NULL and ignoring + * the schedule field. + */ +static __isl_give isl_union_access_info *isl_union_access_info_align_params( + __isl_take isl_union_access_info *access) +{ + isl_space *space; + + if (!access) + return NULL; + + space = isl_union_map_get_space(access->sink); + space = isl_space_align_params(space, + isl_union_map_get_space(access->must_source)); + space = isl_space_align_params(space, + isl_union_map_get_space(access->may_source)); + if (access->schedule_map) + space = isl_space_align_params(space, + isl_union_map_get_space(access->schedule_map)); + access->sink = isl_union_map_align_params(access->sink, + isl_space_copy(space)); + access->must_source = isl_union_map_align_params(access->must_source, + isl_space_copy(space)); + access->may_source = isl_union_map_align_params(access->may_source, + isl_space_copy(space)); + if (!access->schedule_map) { + isl_space_free(space); + } else { + access->schedule_map = + isl_union_map_align_params(access->schedule_map, space); + if (!access->schedule_map) + return isl_union_access_info_free(access); + } + + if (!access->sink || !access->must_source || !access->may_source) + return isl_union_access_info_free(access); + + return access; +} + +/* Prepend the schedule dimensions to the iteration domains. + * + * That is, if the schedule is of the form + * + * D -> S + * + * while the access relations are of the form + * + * D -> A + * + * then the updated access relations are of the form + * + * [S -> D] -> A + * + * The schedule map is also replaced by the map + * + * [S -> D] -> D + * + * that is used during the internal computation. + * Neither the original schedule map nor this updated schedule map + * are used after the call to this function. + */ +static __isl_give isl_union_access_info * +isl_union_access_info_introduce_schedule( + __isl_take isl_union_access_info *access) +{ + isl_union_map *sm; + + if (!access) + return NULL; + + sm = isl_union_map_reverse(access->schedule_map); + sm = isl_union_map_range_map(sm); + access->sink = isl_union_map_apply_range(isl_union_map_copy(sm), + access->sink); + access->may_source = isl_union_map_apply_range(isl_union_map_copy(sm), + access->may_source); + access->must_source = isl_union_map_apply_range(isl_union_map_copy(sm), + access->must_source); + access->schedule_map = sm; + + if (!access->sink || !access->must_source || + !access->may_source || !access->schedule_map) + return isl_union_access_info_free(access); + + return access; +} + +/* This structure epresents the result of a dependence analysis computation. + * + * "must_dep" represents the definite dependences. + * "may_dep" represents the non-definite dependences. + * "must_no_source" represents the subset of the sink accesses for which + * definitely no source was found. + * "may_no_source" represents the subset of the sink accesses for which + * possibly, but not definitely, no source was found. + */ +struct isl_union_flow { isl_union_map *must_dep; isl_union_map *may_dep; isl_union_map *must_no_source; isl_union_map *may_no_source; +}; + +/* Free "flow" and return NULL. + */ +__isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow) +{ + if (!flow) + return NULL; + isl_union_map_free(flow->must_dep); + isl_union_map_free(flow->may_dep); + isl_union_map_free(flow->must_no_source); + isl_union_map_free(flow->may_no_source); + free(flow); + return NULL; +} + +void isl_union_flow_dump(__isl_keep isl_union_flow *flow) +{ + if (!flow) + return; + + fprintf(stderr, "must dependences: "); + isl_union_map_dump(flow->must_dep); + fprintf(stderr, "may dependences: "); + isl_union_map_dump(flow->may_dep); + fprintf(stderr, "must no source: "); + isl_union_map_dump(flow->must_no_source); + fprintf(stderr, "may no source: "); + isl_union_map_dump(flow->may_no_source); +} + +/* Return the definite dependences in "flow". + */ +__isl_give isl_union_map *isl_union_flow_get_must_dependence( + __isl_keep isl_union_flow *flow) +{ + if (!flow) + return NULL; + return isl_union_map_copy(flow->must_dep); +} + +/* Return the possible dependences in "flow", including the definite + * dependences. + */ +__isl_give isl_union_map *isl_union_flow_get_may_dependence( + __isl_keep isl_union_flow *flow) +{ + if (!flow) + return NULL; + return isl_union_map_union(isl_union_map_copy(flow->must_dep), + isl_union_map_copy(flow->may_dep)); +} + +/* Return the non-definite dependences in "flow". + */ +static __isl_give isl_union_map *isl_union_flow_get_non_must_dependence( + __isl_keep isl_union_flow *flow) +{ + if (!flow) + return NULL; + return isl_union_map_copy(flow->may_dep); +} + +/* Return the subset of the sink accesses for which definitely + * no source was found. + */ +__isl_give isl_union_map *isl_union_flow_get_must_no_source( + __isl_keep isl_union_flow *flow) +{ + if (!flow) + return NULL; + return isl_union_map_copy(flow->must_no_source); +} + +/* Return the subset of the sink accesses for which possibly + * no source was found, including those for which definitely + * no source was found. + */ +__isl_give isl_union_map *isl_union_flow_get_may_no_source( + __isl_keep isl_union_flow *flow) +{ + if (!flow) + return NULL; + return isl_union_map_union(isl_union_map_copy(flow->must_no_source), + isl_union_map_copy(flow->may_no_source)); +} + +/* Return the subset of the sink accesses for which possibly, but not + * definitely, no source was found. + */ +static __isl_give isl_union_map *isl_union_flow_get_non_must_no_source( + __isl_keep isl_union_flow *flow) +{ + if (!flow) + return NULL; + return isl_union_map_copy(flow->may_no_source); +} + +/* Create a new isl_union_flow object, initialized with empty + * dependence relations and sink subsets. + */ +static __isl_give isl_union_flow *isl_union_flow_alloc( + __isl_take isl_space *space) +{ + isl_ctx *ctx; + isl_union_map *empty; + isl_union_flow *flow; + + if (!space) + return NULL; + ctx = isl_space_get_ctx(space); + flow = isl_alloc_type(ctx, isl_union_flow); + if (!flow) + goto error; + + empty = isl_union_map_empty(space); + flow->must_dep = isl_union_map_copy(empty); + flow->may_dep = isl_union_map_copy(empty); + flow->must_no_source = isl_union_map_copy(empty); + flow->may_no_source = empty; + + if (!flow->must_dep || !flow->may_dep || + !flow->must_no_source || !flow->may_no_source) + return isl_union_flow_free(flow); + + return flow; +error: + isl_space_free(space); + return NULL; +} + +/* Drop the schedule dimensions from the iteration domains in "flow". + * In particular, the schedule dimensions have been prepended + * to the iteration domains prior to the dependence analysis by + * replacing the iteration domain D, by the wrapped map [S -> D]. + * Replace these wrapped maps by the original D. + */ +static __isl_give isl_union_flow *isl_union_flow_drop_schedule( + __isl_take isl_union_flow *flow) +{ + if (!flow) + return NULL; + + flow->must_dep = isl_union_map_factor_range(flow->must_dep); + flow->may_dep = isl_union_map_factor_range(flow->may_dep); + flow->must_no_source = + isl_union_map_domain_factor_range(flow->must_no_source); + flow->may_no_source = + isl_union_map_domain_factor_range(flow->may_no_source); + + if (!flow->must_dep || !flow->may_dep || + !flow->must_no_source || !flow->may_no_source) + return isl_union_flow_free(flow); + + return flow; +} + +struct isl_compute_flow_data { + isl_union_map *must_source; + isl_union_map *may_source; + isl_union_flow *flow; int count; int must; @@ -1297,8 +1727,10 @@ static int compute_flow(__isl_take isl_map *map, void *user) isl_ctx *ctx; struct isl_compute_flow_data *data; isl_flow *flow; + isl_union_flow *df; data = (struct isl_compute_flow_data *)user; + df = data->flow; ctx = isl_map_get_ctx(map); @@ -1340,18 +1772,18 @@ static int compute_flow(__isl_take isl_map *map, void *user) if (!flow) goto error; - data->must_no_source = isl_union_map_union(data->must_no_source, + df->must_no_source = isl_union_map_union(df->must_no_source, isl_union_map_from_map(isl_flow_get_no_source(flow, 1))); - data->may_no_source = isl_union_map_union(data->may_no_source, + df->may_no_source = isl_union_map_union(df->may_no_source, isl_union_map_from_map(isl_flow_get_no_source(flow, 0))); for (i = 0; i < flow->n_source; ++i) { isl_union_map *dep; dep = isl_union_map_from_map(isl_map_copy(flow->dep[i].map)); if (flow->dep[i].must) - data->must_dep = isl_union_map_union(data->must_dep, dep); + df->must_dep = isl_union_map_union(df->must_dep, dep); else - data->may_dep = isl_union_map_union(data->may_dep, dep); + df->may_dep = isl_union_map_union(df->may_dep, dep); } isl_flow_free(flow); @@ -1380,6 +1812,521 @@ error: return -1; } +/* Remove the must accesses from the may accesses. + * + * A must access always trumps a may access, so there is no need + * for a must access to also be considered as a may access. Doing so + * would only cost extra computations only to find out that + * the duplicated may access does not make any difference. + */ +static __isl_give isl_union_access_info *isl_union_access_info_normalize( + __isl_take isl_union_access_info *access) +{ + if (!access) + return NULL; + access->may_source = isl_union_map_subtract(access->may_source, + isl_union_map_copy(access->must_source)); + if (!access->may_source) + return isl_union_access_info_free(access); + + return access; +} + +/* Given a description of the "sink" accesses, the "source" accesses and + * a schedule, compute for each instance of a sink access + * and for each element accessed by that instance, + * the possible or definite source accesses that last accessed the + * element accessed by the sink access before this sink access + * in the sense that there is no intermediate definite source access. + * + * The must_no_source and may_no_source elements of the result + * are subsets of access->sink. The elements must_dep and may_dep + * map domain elements of access->{may,must)_source to + * domain elements of access->sink. + * + * This function is used when only the schedule map representation + * is available. + * + * We first prepend the schedule dimensions to the domain + * of the accesses so that we can easily compare their relative order. + * Then we consider each sink access individually in compute_flow. + */ +static __isl_give isl_union_flow *compute_flow_union_map( + __isl_take isl_union_access_info *access) +{ + struct isl_compute_flow_data data; + + access = isl_union_access_info_align_params(access); + access = isl_union_access_info_introduce_schedule(access); + if (!access) + return NULL; + + data.must_source = access->must_source; + data.may_source = access->may_source; + + data.flow = isl_union_flow_alloc(isl_union_map_get_space(access->sink)); + + if (isl_union_map_foreach_map(access->sink, &compute_flow, &data) < 0) + goto error; + + data.flow = isl_union_flow_drop_schedule(data.flow); + + isl_union_access_info_free(access); + return data.flow; +error: + isl_union_access_info_free(access); + isl_union_flow_free(data.flow); + return NULL; +} + +/* A schedule access relation. + * + * The access relation "access" is of the form [S -> D] -> A, + * where S corresponds to the prefix schedule at "node". + * "must" is only relevant for source accesses and indicates + * whether the access is a must source or a may source. + */ +struct isl_scheduled_access { + isl_map *access; + int must; + isl_schedule_node *node; +}; + +/* Data structure for keeping track of individual scheduled sink and source + * accesses when computing dependence analysis based on a schedule tree. + * + * "n_sink" is the number of used entries in "sink" + * "n_source" is the number of used entries in "source" + * + * "set_sink", "must" and "node" are only used inside collect_sink_source, + * to keep track of the current node and + * of what extract_sink_source needs to do. + */ +struct isl_compute_flow_schedule_data { + isl_union_access_info *access; + + int n_sink; + int n_source; + + struct isl_scheduled_access *sink; + struct isl_scheduled_access *source; + + int set_sink; + int must; + isl_schedule_node *node; +}; + +/* Align the parameters of all sinks with all sources. + * + * If there are no sinks or no sources, then no alignment is needed. + */ +static void isl_compute_flow_schedule_data_align_params( + struct isl_compute_flow_schedule_data *data) +{ + int i; + isl_space *space; + + if (data->n_sink == 0 || data->n_source == 0) + return; + + space = isl_map_get_space(data->sink[0].access); + + for (i = 1; i < data->n_sink; ++i) + space = isl_space_align_params(space, + isl_map_get_space(data->sink[i].access)); + for (i = 0; i < data->n_source; ++i) + space = isl_space_align_params(space, + isl_map_get_space(data->source[i].access)); + + for (i = 0; i < data->n_sink; ++i) + data->sink[i].access = + isl_map_align_params(data->sink[i].access, + isl_space_copy(space)); + for (i = 0; i < data->n_source; ++i) + data->source[i].access = + isl_map_align_params(data->source[i].access, + isl_space_copy(space)); + + isl_space_free(space); +} + +/* Free all the memory referenced from "data". + * Do not free "data" itself as it may be allocated on the stack. + */ +static void isl_compute_flow_schedule_data_clear( + struct isl_compute_flow_schedule_data *data) +{ + int i; + + for (i = 0; i < data->n_sink; ++i) { + isl_map_free(data->sink[i].access); + isl_schedule_node_free(data->sink[i].node); + } + + for (i = 0; i < data->n_source; ++i) { + isl_map_free(data->source[i].access); + isl_schedule_node_free(data->source[i].node); + } + + free(data->sink); +} + +/* isl_schedule_foreach_schedule_node callback for counting + * (an upper bound on) the number of sinks and sources. + * + * Sinks and sources are only extracted at leaves of the tree, + * so we skip the node if it is not a leaf. + * Otherwise we increment data->n_sink and data->n_source with + * the number of spaces in the sink and source access domains + * that reach this node. + */ +static int count_sink_source(__isl_keep isl_schedule_node *node, void *user) +{ + struct isl_compute_flow_schedule_data *data = user; + isl_union_set *domain; + isl_union_map *umap; + int r = 0; + + if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf) + return 1; + + domain = isl_schedule_node_get_universe_domain(node); + + umap = isl_union_map_copy(data->access->sink); + umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain)); + data->n_sink += isl_union_map_n_map(umap); + isl_union_map_free(umap); + if (!umap) + r = -1; + + umap = isl_union_map_copy(data->access->must_source); + umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain)); + data->n_source += isl_union_map_n_map(umap); + isl_union_map_free(umap); + if (!umap) + r = -1; + + umap = isl_union_map_copy(data->access->may_source); + umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain)); + data->n_source += isl_union_map_n_map(umap); + isl_union_map_free(umap); + if (!umap) + r = -1; + + isl_union_set_free(domain); + + return r; +} + +/* Add a single scheduled sink or source (depending on data->set_sink) + * with scheduled access relation "map", must property data->must and + * schedule node data->node to the list of sinks or sources. + */ +static int extract_sink_source(__isl_take isl_map *map, void *user) +{ + struct isl_compute_flow_schedule_data *data = user; + struct isl_scheduled_access *access; + + if (data->set_sink) + access = data->sink + data->n_sink++; + else + access = data->source + data->n_source++; + + access->access = map; + access->must = data->must; + access->node = isl_schedule_node_copy(data->node); + + return 0; +} + +/* isl_schedule_foreach_schedule_node callback for collecting + * individual scheduled source and sink accesses. + * + * We only collect accesses at the leaves of the schedule tree. + * We prepend the schedule dimensions at the leaf to the iteration + * domains of the source and sink accesses and then extract + * the individual accesses (per space). + * + * In particular, if the prefix schedule at the node is of the form + * + * D -> S + * + * while the access relations are of the form + * + * D -> A + * + * then the updated access relations are of the form + * + * [S -> D] -> A + * + * Note that S consists of a single space such that introducing S + * in the access relations does not increase the number of spaces. + */ +static int collect_sink_source(__isl_keep isl_schedule_node *node, void *user) +{ + struct isl_compute_flow_schedule_data *data = user; + isl_union_map *prefix; + isl_union_map *umap; + int r = 0; + + if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf) + return 1; + + data->node = node; + + prefix = isl_schedule_node_get_prefix_schedule_union_map(node); + prefix = isl_union_map_reverse(prefix); + prefix = isl_union_map_range_map(prefix); + + data->set_sink = 1; + umap = isl_union_map_copy(data->access->sink); + umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap); + if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0) + r = -1; + isl_union_map_free(umap); + + data->set_sink = 0; + data->must = 1; + umap = isl_union_map_copy(data->access->must_source); + umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap); + if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0) + r = -1; + isl_union_map_free(umap); + + data->set_sink = 0; + data->must = 0; + umap = isl_union_map_copy(data->access->may_source); + umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap); + if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0) + r = -1; + isl_union_map_free(umap); + + isl_union_map_free(prefix); + + return r; +} + +/* isl_access_info_compute_flow callback for determining whether + * the shared nesting level and the ordering within that level + * for two scheduled accesses for use in compute_single_flow. + * + * The tokens passed to this function refer to the leaves + * in the schedule tree where the accesses take place. + * + * If n is the shared number of loops, then we need to return + * "2 * n + 1" if "first" precedes "second" inside the innermost + * shared loop and "2 * n" otherwise. + * + * The innermost shared ancestor may be the leaves themselves + * if the accesses take place in the same leaf. Otherwise, + * it is either a set node or a sequence node. Only in the case + * of a sequence node do we consider one access to precede the other. + */ +static int before_node(void *first, void *second) +{ + isl_schedule_node *node1 = first; + isl_schedule_node *node2 = second; + isl_schedule_node *shared; + int depth; + int before = 0; + + shared = isl_schedule_node_get_shared_ancestor(node1, node2); + if (!shared) + return -1; + + depth = isl_schedule_node_get_schedule_depth(shared); + if (isl_schedule_node_get_type(shared) == isl_schedule_node_sequence) { + int pos1, pos2; + + pos1 = isl_schedule_node_get_ancestor_child_position(node1, + shared); + pos2 = isl_schedule_node_get_ancestor_child_position(node2, + shared); + before = pos1 < pos2; + } + + isl_schedule_node_free(shared); + + return 2 * depth + before; +} + +/* Add the scheduled sources from "data" that access + * the same data space as "sink" to "access". + */ +static __isl_give isl_access_info *add_matching_sources( + __isl_take isl_access_info *access, struct isl_scheduled_access *sink, + struct isl_compute_flow_schedule_data *data) +{ + int i; + isl_space *space; + + space = isl_space_range(isl_map_get_space(sink->access)); + for (i = 0; i < data->n_source; ++i) { + struct isl_scheduled_access *source; + isl_space *source_space; + int eq; + + source = &data->source[i]; + source_space = isl_map_get_space(source->access); + source_space = isl_space_range(source_space); + eq = isl_space_is_equal(space, source_space); + isl_space_free(source_space); + + if (!eq) + continue; + if (eq < 0) + goto error; + + access = isl_access_info_add_source(access, + isl_map_copy(source->access), source->must, source->node); + } + + isl_space_free(space); + return access; +error: + isl_space_free(space); + isl_access_info_free(access); + return NULL; +} + +/* Given a scheduled sink access relation "sink", compute the corresponding + * dependences on the sources in "data" and add the computed dependences + * to "uf". + */ +static __isl_give isl_union_flow *compute_single_flow( + __isl_take isl_union_flow *uf, struct isl_scheduled_access *sink, + struct isl_compute_flow_schedule_data *data) +{ + int i; + isl_access_info *access; + isl_flow *flow; + isl_map *map; + + if (!uf) + return NULL; + + access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node, + &before_node, data->n_source); + access = add_matching_sources(access, sink, data); + + flow = isl_access_info_compute_flow(access); + if (!flow) + return isl_union_flow_free(uf); + + map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 1)); + uf->must_no_source = isl_union_map_union(uf->must_no_source, + isl_union_map_from_map(map)); + map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 0)); + uf->may_no_source = isl_union_map_union(uf->may_no_source, + isl_union_map_from_map(map)); + + for (i = 0; i < flow->n_source; ++i) { + isl_union_map *dep; + + map = isl_map_factor_range(isl_map_copy(flow->dep[i].map)); + dep = isl_union_map_from_map(map); + if (flow->dep[i].must) + uf->must_dep = isl_union_map_union(uf->must_dep, dep); + else + uf->may_dep = isl_union_map_union(uf->may_dep, dep); + } + + isl_flow_free(flow); + + return uf; +} + +/* Given a description of the "sink" accesses, the "source" accesses and + * a schedule, compute for each instance of a sink access + * and for each element accessed by that instance, + * the possible or definite source accesses that last accessed the + * element accessed by the sink access before this sink access + * in the sense that there is no intermediate definite source access. + * + * The must_no_source and may_no_source elements of the result + * are subsets of access->sink. The elements must_dep and may_dep + * map domain elements of access->{may,must)_source to + * domain elements of access->sink. + * + * This function is used when a schedule tree representation + * is available. + * + * We extract the individual scheduled source and sink access relations and + * then compute dependences for each scheduled sink individually. + */ +static __isl_give isl_union_flow *compute_flow_schedule( + __isl_take isl_union_access_info *access) +{ + struct isl_compute_flow_schedule_data data = { access }; + int i, n; + isl_ctx *ctx; + isl_union_flow *flow; + + ctx = isl_union_access_info_get_ctx(access); + + data.n_sink = 0; + data.n_source = 0; + if (isl_schedule_foreach_schedule_node(access->schedule, + &count_sink_source, &data) < 0) + goto error; + + n = data.n_sink + data.n_source; + data.sink = isl_calloc_array(ctx, struct isl_scheduled_access, n); + if (n && !data.sink) + goto error; + data.source = data.sink + data.n_sink; + + data.n_sink = 0; + data.n_source = 0; + if (isl_schedule_foreach_schedule_node(access->schedule, + &collect_sink_source, &data) < 0) + goto error; + + flow = isl_union_flow_alloc(isl_union_map_get_space(access->sink)); + + isl_compute_flow_schedule_data_align_params(&data); + + for (i = 0; i < data.n_sink; ++i) + flow = compute_single_flow(flow, &data.sink[i], &data); + + isl_compute_flow_schedule_data_clear(&data); + + isl_union_access_info_free(access); + return flow; +error: + isl_union_access_info_free(access); + isl_compute_flow_schedule_data_clear(&data); + return NULL; +} + +/* Given a description of the "sink" accesses, the "source" accesses and + * a schedule, compute for each instance of a sink access + * and for each element accessed by that instance, + * the possible or definite source accesses that last accessed the + * element accessed by the sink access before this sink access + * in the sense that there is no intermediate definite source access. + * + * The must_no_source and may_no_source elements of the result + * are subsets of access->sink. The elements must_dep and may_dep + * map domain elements of access->{may,must)_source to + * domain elements of access->sink. + * + * We check whether the schedule is available as a schedule tree + * or a schedule map and call the correpsonding function to perform + * the analysis. + */ +__isl_give isl_union_flow *isl_union_access_info_compute_flow( + __isl_take isl_union_access_info *access) +{ + access = isl_union_access_info_normalize(access); + if (!access) + return NULL; + if (access->schedule) + return compute_flow_schedule(access); + else + return compute_flow_union_map(access); +} + /* Given a collection of "sink" and "source" accesses, * compute for each iteration of a sink access * and for each element accessed by that iteration, @@ -1392,9 +2339,9 @@ error: * corresponding to those iterations that access an element * not previously accessed. * - * We first prepend the schedule dimensions to the domain - * of the accesses so that we can easily compare their relative order. - * Then we consider each sink access individually in compute_flow. + * We collect the inputs in an isl_union_access_info object, + * call isl_union_access_info_compute_flow and extract + * the outputs from the result. */ int isl_union_map_compute_flow(__isl_take isl_union_map *sink, __isl_take isl_union_map *must_source, @@ -1404,93 +2351,40 @@ int isl_union_map_compute_flow(__isl_take isl_union_map *sink, __isl_give isl_union_map **must_no_source, __isl_give isl_union_map **may_no_source) { - isl_space *dim; - isl_union_map *range_map = NULL; - struct isl_compute_flow_data data; - - sink = isl_union_map_align_params(sink, - isl_union_map_get_space(must_source)); - sink = isl_union_map_align_params(sink, - isl_union_map_get_space(may_source)); - sink = isl_union_map_align_params(sink, - isl_union_map_get_space(schedule)); - dim = isl_union_map_get_space(sink); - must_source = isl_union_map_align_params(must_source, isl_space_copy(dim)); - may_source = isl_union_map_align_params(may_source, isl_space_copy(dim)); - schedule = isl_union_map_align_params(schedule, isl_space_copy(dim)); - - schedule = isl_union_map_reverse(schedule); - range_map = isl_union_map_range_map(schedule); - schedule = isl_union_map_reverse(isl_union_map_copy(range_map)); - sink = isl_union_map_apply_domain(sink, isl_union_map_copy(schedule)); - must_source = isl_union_map_apply_domain(must_source, - isl_union_map_copy(schedule)); - may_source = isl_union_map_apply_domain(may_source, schedule); - - data.must_source = must_source; - data.may_source = may_source; - data.must_dep = must_dep ? - isl_union_map_empty(isl_space_copy(dim)) : NULL; - data.may_dep = may_dep ? isl_union_map_empty(isl_space_copy(dim)) : NULL; - data.must_no_source = must_no_source ? - isl_union_map_empty(isl_space_copy(dim)) : NULL; - data.may_no_source = may_no_source ? - isl_union_map_empty(isl_space_copy(dim)) : NULL; - - isl_space_free(dim); + isl_union_access_info *access; + isl_union_flow *flow; - if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0) - goto error; + access = isl_union_access_info_from_sink(sink); + access = isl_union_access_info_set_must_source(access, must_source); + access = isl_union_access_info_set_may_source(access, may_source); + access = isl_union_access_info_set_schedule_map(access, schedule); + flow = isl_union_access_info_compute_flow(access); - isl_union_map_free(sink); - isl_union_map_free(must_source); - isl_union_map_free(may_source); + if (must_dep) + *must_dep = isl_union_flow_get_must_dependence(flow); + if (may_dep) + *may_dep = isl_union_flow_get_non_must_dependence(flow); + if (must_no_source) + *must_no_source = isl_union_flow_get_must_no_source(flow); + if (may_no_source) + *may_no_source = isl_union_flow_get_non_must_no_source(flow); - if (must_dep) { - data.must_dep = isl_union_map_apply_domain(data.must_dep, - isl_union_map_copy(range_map)); - data.must_dep = isl_union_map_apply_range(data.must_dep, - isl_union_map_copy(range_map)); - *must_dep = data.must_dep; - } - if (may_dep) { - data.may_dep = isl_union_map_apply_domain(data.may_dep, - isl_union_map_copy(range_map)); - data.may_dep = isl_union_map_apply_range(data.may_dep, - isl_union_map_copy(range_map)); - *may_dep = data.may_dep; - } - if (must_no_source) { - data.must_no_source = isl_union_map_apply_domain( - data.must_no_source, isl_union_map_copy(range_map)); - *must_no_source = data.must_no_source; - } - if (may_no_source) { - data.may_no_source = isl_union_map_apply_domain( - data.may_no_source, isl_union_map_copy(range_map)); - *may_no_source = data.may_no_source; - } + isl_union_flow_free(flow); - isl_union_map_free(range_map); + if ((must_dep && !*must_dep) || (may_dep && !*may_dep) || + (must_no_source && !*must_no_source) || + (may_no_source && !*may_no_source)) + goto error; return 0; error: - isl_union_map_free(range_map); - isl_union_map_free(sink); - isl_union_map_free(must_source); - isl_union_map_free(may_source); - isl_union_map_free(data.must_dep); - isl_union_map_free(data.may_dep); - isl_union_map_free(data.must_no_source); - isl_union_map_free(data.may_no_source); - if (must_dep) - *must_dep = NULL; + *must_dep = isl_union_map_free(*must_dep); if (may_dep) - *may_dep = NULL; + *may_dep = isl_union_map_free(*may_dep); if (must_no_source) - *must_no_source = NULL; + *must_no_source = isl_union_map_free(*must_no_source); if (may_no_source) - *may_no_source = NULL; + *may_no_source = isl_union_map_free(*may_no_source); return -1; } diff --git a/polly/lib/External/isl/isl_id.c b/polly/lib/External/isl/isl_id.c index 6895570..37ba6db 100644 --- a/polly/lib/External/isl/isl_id.c +++ b/polly/lib/External/isl/isl_id.c @@ -88,8 +88,10 @@ static int isl_id_has_name_and_user(const void *entry, const void *val) if (id->user != nu->user) return 0; - if (!id->name && !nu->name) + if (id->name == nu->name) return 1; + if (!id->name || !nu->name) + return 0; return !strcmp(id->name, nu->name); } diff --git a/polly/lib/External/isl/isl_input.c b/polly/lib/External/isl/isl_input.c index b6073de..7cc603c 100644 --- a/polly/lib/External/isl/isl_input.c +++ b/polly/lib/External/isl/isl_input.c @@ -1771,15 +1771,10 @@ static __isl_give isl_basic_map *basic_map_read_polylib_constraint( int type; int k; isl_int *c; - unsigned nparam; - unsigned dim; if (!bmap) return NULL; - nparam = isl_basic_map_dim(bmap, isl_dim_param); - dim = isl_basic_map_dim(bmap, isl_dim_out); - tok = isl_stream_next_token(s); if (!tok || tok->type != ISL_TOKEN_VALUE) { isl_stream_error(s, tok, "expecting coefficient"); diff --git a/polly/lib/External/isl/isl_local_space.c b/polly/lib/External/isl/isl_local_space.c index 7b1f09d..1890838 100644 --- a/polly/lib/External/isl/isl_local_space.c +++ b/polly/lib/External/isl/isl_local_space.c @@ -919,7 +919,7 @@ __isl_give isl_local_space *isl_local_space_substitute_seq( pos += isl_local_space_offset(ls, type); isl_int_init(v); - for (i = first; i < ls->div->n_row; ++i) { + for (i = first; i < first + n; ++i) { if (isl_int_is_zero(ls->div->row[i][1 + pos])) continue; isl_seq_substitute(ls->div->row[i], pos, subs, diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c index fdde730..dd75abc 100644 --- a/polly/lib/External/isl/isl_map_simplify.c +++ b/polly/lib/External/isl/isl_map_simplify.c @@ -735,12 +735,14 @@ static struct isl_basic_map *remove_duplicate_divs( if (k <= 0) return bmap; - elim_for = isl_calloc_array(ctx, int, bmap->n_div); size = round_up(4 * bmap->n_div / 3 - 1); + if (size == 0) + return bmap; + elim_for = isl_calloc_array(ctx, int, bmap->n_div); bits = ffs(size) - 1; index = isl_calloc_array(ctx, int, size); - if (!index) - return bmap; + if (!elim_for || !index) + goto out; eq = isl_blk_alloc(ctx, 1+total); if (isl_blk_is_error(eq)) goto out; @@ -1128,6 +1130,8 @@ __isl_give isl_basic_map *isl_basic_map_remove_duplicate_constraints( return bmap; size = round_up(4 * (bmap->n_ineq+1) / 3 - 1); + if (size == 0) + return bmap; bits = ffs(size) - 1; ctx = isl_basic_map_get_ctx(bmap); index = isl_calloc_array(ctx, isl_int **, size); @@ -1758,6 +1762,8 @@ static struct isl_basic_set *remove_shifted_constraints( return NULL; size = round_up(4 * (context->n_ineq+1) / 3 - 1); + if (size == 0) + return bset; bits = ffs(size) - 1; ctx = isl_basic_set_get_ctx(bset); index = isl_calloc_array(ctx, isl_int **, size); @@ -2298,7 +2304,7 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap, n_eq = bset->n_eq; n_ineq = bset->n_ineq; eq = isl_basic_set_copy(bset); - eq = isl_basic_set_cow(bset); + eq = isl_basic_set_cow(eq); if (isl_basic_set_free_inequality(eq, n_ineq) < 0) eq = isl_basic_set_free(eq); if (isl_basic_set_free_equality(bset, n_eq) < 0) diff --git a/polly/lib/External/isl/isl_mat.c b/polly/lib/External/isl/isl_mat.c index 3a8d310..f4ed370 100644 --- a/polly/lib/External/isl/isl_mat.c +++ b/polly/lib/External/isl/isl_mat.c @@ -1179,14 +1179,12 @@ error2: struct isl_set *isl_set_preimage(struct isl_set *set, struct isl_mat *mat) { - struct isl_ctx *ctx; int i; set = isl_set_cow(set); if (!set) return NULL; - ctx = set->ctx; for (i = 0; i < set->n; ++i) { set->p[i] = isl_basic_set_preimage(set->p[i], isl_mat_copy(mat)); diff --git a/polly/lib/External/isl/isl_output.c b/polly/lib/External/isl/isl_output.c index 58f8241..aa96b9d 100644 --- a/polly/lib/External/isl/isl_output.c +++ b/polly/lib/External/isl/isl_output.c @@ -1096,7 +1096,7 @@ static int print_map_body(__isl_take isl_map *map, void *user) static __isl_give isl_printer *isl_union_map_print_isl( __isl_keep isl_union_map *umap, __isl_take isl_printer *p) { - struct isl_union_print_data data = { p, 1 }; + struct isl_union_print_data data; struct isl_print_space_data space_data = { 0 }; isl_space *dim; @@ -1107,6 +1107,8 @@ static __isl_give isl_printer *isl_union_map_print_isl( } isl_space_free(dim); p = isl_printer_print_str(p, s_open_set[0]); + data.p = p; + data.first = 1; isl_union_map_foreach_map(umap, &print_map_body, &data); p = data.p; p = isl_printer_print_str(p, s_close_set[0]); @@ -1766,7 +1768,7 @@ static int print_pwqp_body(__isl_take isl_pw_qpolynomial *pwqp, void *user) static __isl_give isl_printer *print_union_pw_qpolynomial_isl( __isl_take isl_printer *p, __isl_keep isl_union_pw_qpolynomial *upwqp) { - struct isl_union_print_data data = { p, 1 }; + struct isl_union_print_data data; struct isl_print_space_data space_data = { 0 }; isl_space *dim; @@ -1777,6 +1779,8 @@ static __isl_give isl_printer *print_union_pw_qpolynomial_isl( } isl_space_free(dim); p = isl_printer_print_str(p, "{ "); + data.p = p; + data.first = 1; isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &print_pwqp_body, &data); p = data.p; @@ -1908,7 +1912,7 @@ static __isl_give isl_printer *print_union_pw_qpolynomial_fold_isl( __isl_take isl_printer *p, __isl_keep isl_union_pw_qpolynomial_fold *upwf) { - struct isl_union_print_data data = { p, 1 }; + struct isl_union_print_data data; struct isl_print_space_data space_data = { 0 }; isl_space *dim; @@ -1919,6 +1923,8 @@ static __isl_give isl_printer *print_union_pw_qpolynomial_fold_isl( } isl_space_free(dim); p = isl_printer_print_str(p, "{ "); + data.p = p; + data.first = 1; isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(upwf, &print_pwf_body, &data); p = data.p; @@ -2005,13 +2011,11 @@ __isl_give isl_printer *isl_printer_print_local_space(__isl_take isl_printer *p, __isl_keep isl_local_space *ls) { struct isl_print_space_data data = { 0 }; - unsigned total; unsigned n_div; if (!ls) goto error; - total = isl_local_space_dim(ls, isl_dim_all); if (isl_local_space_dim(ls, isl_dim_param) > 0) { p = print_tuple(ls->dim, p, isl_dim_param, &data); p = isl_printer_print_str(p, " -> "); @@ -2561,7 +2565,7 @@ static int print_pw_multi_aff_body_wrap(__isl_take isl_pw_multi_aff *pma, static __isl_give isl_printer *print_union_pw_multi_aff_isl( __isl_take isl_printer *p, __isl_keep isl_union_pw_multi_aff *upma) { - struct isl_union_print_data data = { p, 1 }; + struct isl_union_print_data data; struct isl_print_space_data space_data = { 0 }; isl_space *space; @@ -2572,6 +2576,8 @@ static __isl_give isl_printer *print_union_pw_multi_aff_isl( } isl_space_free(space); p = isl_printer_print_str(p, s_open_set[0]); + data.p = p; + data.first = 1; isl_union_pw_multi_aff_foreach_pw_multi_aff(upma, &print_pw_multi_aff_body_wrap, &data); p = data.p; diff --git a/polly/lib/External/isl/isl_range.c b/polly/lib/External/isl/isl_range.c index 5599582..517db03 100644 --- a/polly/lib/External/isl/isl_range.c +++ b/polly/lib/External/isl/isl_range.c @@ -29,7 +29,6 @@ static int has_sign(__isl_keep isl_basic_set *bset, __isl_keep isl_qpolynomial *poly, int sign, int *signs) { struct range_data data_m; - unsigned nvar; unsigned nparam; isl_space *dim; isl_val *opt; @@ -37,7 +36,6 @@ static int has_sign(__isl_keep isl_basic_set *bset, enum isl_fold type; nparam = isl_basic_set_dim(bset, isl_dim_param); - nvar = isl_basic_set_dim(bset, isl_dim_set); bset = isl_basic_set_copy(bset); poly = isl_qpolynomial_copy(poly); diff --git a/polly/lib/External/isl/isl_sample.c b/polly/lib/External/isl/isl_sample.c index eaa0754..7dcd53f 100644 --- a/polly/lib/External/isl/isl_sample.c +++ b/polly/lib/External/isl/isl_sample.c @@ -595,7 +595,6 @@ error: static struct isl_vec *sample_bounded(struct isl_basic_set *bset) { unsigned dim; - struct isl_ctx *ctx; struct isl_vec *sample; struct isl_tab *tab = NULL; isl_factorizer *f; @@ -620,14 +619,12 @@ static struct isl_vec *sample_bounded(struct isl_basic_set *bset) if (f->n_group != 0) return factored_sample(bset, f); isl_factorizer_free(f); - - ctx = bset->ctx; tab = isl_tab_from_basic_set(bset, 1); if (tab && tab->empty) { isl_tab_free(tab); ISL_F_SET(bset, ISL_BASIC_SET_EMPTY); - sample = isl_vec_alloc(bset->ctx, 0); + sample = isl_vec_alloc(isl_basic_set_get_ctx(bset), 0); isl_basic_set_free(bset); return sample; } @@ -924,11 +921,11 @@ __isl_give isl_vec *isl_basic_set_sample_with_cone( if (!bset || !cone) goto error; - ctx = bset->ctx; + ctx = isl_basic_set_get_ctx(bset); total = isl_basic_set_total_dim(cone); cone_dim = total - cone->n_eq; - M = isl_mat_sub_alloc6(bset->ctx, cone->eq, 0, cone->n_eq, 1, total); + M = isl_mat_sub_alloc6(ctx, cone->eq, 0, cone->n_eq, 1, total); M = isl_mat_left_hermite(M, 0, &U, NULL); if (!M) goto error; diff --git a/polly/lib/External/isl/isl_schedule.c b/polly/lib/External/isl/isl_schedule.c index 85a8e7c..41abeea 100644 --- a/polly/lib/External/isl/isl_schedule.c +++ b/polly/lib/External/isl/isl_schedule.c @@ -177,6 +177,19 @@ __isl_keep isl_schedule_tree *isl_schedule_peek_leaf( return schedule ? &schedule->leaf : NULL; } +/* Are "schedule1" and "schedule2" obviously equal to each other? + */ +int isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1, + __isl_keep isl_schedule *schedule2) +{ + if (!schedule1 || !schedule2) + return -1; + if (schedule1 == schedule2) + return 1; + return isl_schedule_tree_plain_is_equal(schedule1->root, + schedule2->root); +} + /* Return the (parameter) space of the schedule, i.e., the space * of the root domain. */ @@ -361,6 +374,101 @@ __isl_give isl_schedule *isl_schedule_map_schedule_node( return schedule; } +/* Wrapper around isl_schedule_node_reset_user for use as + * an isl_schedule_map_schedule_node callback. + */ +static __isl_give isl_schedule_node *reset_user( + __isl_take isl_schedule_node *node, void *user) +{ + return isl_schedule_node_reset_user(node); +} + +/* Reset the user pointer on all identifiers of parameters and tuples + * in the schedule "schedule". + */ +__isl_give isl_schedule *isl_schedule_reset_user( + __isl_take isl_schedule *schedule) +{ + return isl_schedule_map_schedule_node(schedule, &reset_user, NULL); +} + +/* Wrapper around isl_schedule_node_align_params for use as + * an isl_schedule_map_schedule_node callback. + */ +static __isl_give isl_schedule_node *align_params( + __isl_take isl_schedule_node *node, void *user) +{ + isl_space *space = user; + + return isl_schedule_node_align_params(node, isl_space_copy(space)); +} + +/* Align the parameters of all nodes in schedule "schedule" + * to those of "space". + */ +__isl_give isl_schedule *isl_schedule_align_params( + __isl_take isl_schedule *schedule, __isl_take isl_space *space) +{ + schedule = isl_schedule_map_schedule_node(schedule, + &align_params, space); + isl_space_free(space); + return schedule; +} + +/* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as + * an isl_schedule_map_schedule_node callback. + */ +static __isl_give isl_schedule_node *pullback_upma( + __isl_take isl_schedule_node *node, void *user) +{ + isl_union_pw_multi_aff *upma = user; + + return isl_schedule_node_pullback_union_pw_multi_aff(node, + isl_union_pw_multi_aff_copy(upma)); +} + +/* Compute the pullback of "schedule" by the function represented by "upma". + * In other words, plug in "upma" in the iteration domains of "schedule". + */ +__isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff( + __isl_take isl_schedule *schedule, + __isl_take isl_union_pw_multi_aff *upma) +{ + schedule = isl_schedule_map_schedule_node(schedule, + &pullback_upma, upma); + isl_union_pw_multi_aff_free(upma); + return schedule; +} + +/* Intersect the domain of the schedule "schedule" with "domain". + */ +__isl_give isl_schedule *isl_schedule_intersect_domain( + __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain) +{ + enum isl_schedule_node_type root_type; + isl_schedule_node *node; + + if (!schedule || !domain) + goto error; + + root_type = isl_schedule_tree_get_type(schedule->root); + if (root_type != isl_schedule_node_domain) + isl_die(isl_schedule_get_ctx(schedule), isl_error_internal, + "root node not a domain node", goto error); + + node = isl_schedule_get_root(schedule); + isl_schedule_free(schedule); + node = isl_schedule_node_domain_intersect_domain(node, domain); + schedule = isl_schedule_node_get_schedule(node); + isl_schedule_node_free(node); + + return schedule; +error: + isl_schedule_free(schedule); + isl_union_set_free(domain); + return NULL; +} + /* Return an isl_union_map representation of the schedule. * If we still have access to the schedule tree, then we return * an isl_union_map corresponding to the subtree schedule of the child @@ -738,6 +846,150 @@ static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p, return p; } +/* 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. + */ +__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; + + node = isl_schedule_get_root(schedule); + isl_schedule_free(schedule); + if (!node) + goto error; + if (isl_schedule_node_get_type(node) != isl_schedule_node_domain) + isl_die(isl_schedule_node_get_ctx(node), isl_error_internal, + "root node not a domain node", goto error); + + node = isl_schedule_node_child(node, 0); + node = isl_schedule_node_insert_partial_schedule(node, partial); + + schedule = isl_schedule_node_get_schedule(node); + isl_schedule_node_free(node); + + return schedule; +error: + isl_schedule_node_free(node); + isl_multi_union_pw_aff_free(partial); + return NULL; +} + +/* Return a tree with as top-level node a filter corresponding to "filter" and + * as child, the (single) child of "tree". + * However, if this single child is of type "type", then the filter is inserted + * in the children of this single child instead. + */ +static __isl_give isl_schedule_tree *insert_filter_in_child_of_type( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter, + enum isl_schedule_node_type type) +{ + if (!isl_schedule_tree_has_children(tree)) { + isl_schedule_tree_free(tree); + return isl_schedule_tree_from_filter(filter); + } else { + tree = isl_schedule_tree_child(tree, 0); + } + + if (isl_schedule_tree_get_type(tree) == type) + tree = isl_schedule_tree_children_insert_filter(tree, filter); + else + tree = isl_schedule_tree_insert_filter(tree, filter); + + return tree; +} + +/* Construct a schedule that combines the schedules "schedule1" and "schedule2" + * with a top-level node (underneath the domain node) of type "type", + * either isl_schedule_node_sequence or isl_schedule_node_set. + * The domains of the two schedules are assumed to be disjoint. + * + * The new schedule has as domain the union of the domains of the two + * schedules. The child of the domain node is a node of type "type" + * with two filters corresponding to the domains of the input schedules. + * If one (or both) of the top-level nodes of the two schedules is itself + * of type "type", then the filter is pushed into the children of that + * node and the sequence of set is flattened. + */ +__isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type, + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) +{ + int disjoint; + isl_ctx *ctx; + enum isl_schedule_node_type root_type; + isl_schedule_tree *tree1, *tree2; + isl_union_set *filter1, *filter2, *domain; + + if (!schedule1 || !schedule2) + goto error; + + root_type = isl_schedule_tree_get_type(schedule1->root); + if (root_type != isl_schedule_node_domain) + isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal, + "root node not a domain node", goto error); + root_type = isl_schedule_tree_get_type(schedule2->root); + if (root_type != isl_schedule_node_domain) + isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal, + "root node not a domain node", goto error); + + ctx = isl_schedule_get_ctx(schedule1); + tree1 = isl_schedule_tree_copy(schedule1->root); + filter1 = isl_schedule_tree_domain_get_domain(tree1); + tree2 = isl_schedule_tree_copy(schedule2->root); + filter2 = isl_schedule_tree_domain_get_domain(tree2); + + isl_schedule_free(schedule1); + isl_schedule_free(schedule2); + + disjoint = isl_union_set_is_disjoint(filter1, filter2); + if (disjoint < 0) + filter1 = isl_union_set_free(filter1); + if (!disjoint) + isl_die(ctx, isl_error_invalid, + "schedule domains not disjoint", + filter1 = isl_union_set_free(filter1)); + + domain = isl_union_set_union(isl_union_set_copy(filter1), + isl_union_set_copy(filter2)); + filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain)); + filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain)); + + tree1 = insert_filter_in_child_of_type(tree1, filter1, type); + tree2 = insert_filter_in_child_of_type(tree2, filter2, type); + + tree1 = isl_schedule_tree_from_pair(type, tree1, tree2); + tree1 = isl_schedule_tree_insert_domain(tree1, domain); + + return isl_schedule_from_schedule_tree(ctx, tree1); +error: + isl_schedule_free(schedule1); + isl_schedule_free(schedule2); + return NULL; +} + +/* Construct a schedule that combines the schedules "schedule1" and "schedule2" + * through a sequence node. + * The domains of the input schedules are assumed to be disjoint. + */ +__isl_give isl_schedule *isl_schedule_sequence( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) +{ + return isl_schedule_pair(isl_schedule_node_sequence, + schedule1, schedule2); +} + +/* Construct a schedule that combines the schedules "schedule1" and "schedule2" + * through a set node. + * The domains of the input schedules are assumed to be disjoint. + */ +__isl_give isl_schedule *isl_schedule_set( + __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2) +{ + return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2); +} + /* Print "schedule" to "p". * * If "schedule" was created from a schedule tree, then we print diff --git a/polly/lib/External/isl/isl_schedule_band.c b/polly/lib/External/isl/isl_schedule_band.c index aae32f3..6c0b391 100644 --- a/polly/lib/External/isl/isl_schedule_band.c +++ b/polly/lib/External/isl/isl_schedule_band.c @@ -1,10 +1,13 @@ /* * Copyright 2013-2014 Ecole Normale Superieure + * Copyright 2014 INRIA Rocquencourt * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, + * B.P. 105 - 78153 Le Chesnay, France */ #include @@ -142,6 +145,29 @@ __isl_null isl_schedule_band *isl_schedule_band_free( return NULL; } +/* Are "band1" and "band2" obviously equal? + */ +int isl_schedule_band_plain_is_equal(__isl_keep isl_schedule_band *band1, + __isl_keep isl_schedule_band *band2) +{ + int i; + + if (!band1 || !band2) + return -1; + if (band1 == band2) + return 1; + + if (band1->n != band2->n) + return 0; + for (i = 0; i < band1->n; ++i) + if (band1->coincident[i] != band2->coincident[i]) + return 0; + if (band1->permutable != band2->permutable) + return 0; + + return isl_multi_union_pw_aff_plain_is_equal(band1->mupa, band2->mupa); +} + /* Return the number of scheduling dimensions in the band. */ int isl_schedule_band_n_member(__isl_keep isl_schedule_band *band) @@ -415,3 +441,89 @@ __isl_give isl_schedule_band *isl_schedule_band_drop( return band; } + +/* Reset the user pointer on all identifiers of parameters and tuples + * in "band". + */ +__isl_give isl_schedule_band *isl_schedule_band_reset_user( + __isl_take isl_schedule_band *band) +{ + band = isl_schedule_band_cow(band); + if (!band) + return NULL; + + band->mupa = isl_multi_union_pw_aff_reset_user(band->mupa); + if (!band->mupa) + return isl_schedule_band_free(band); + + return band; +} + +/* Align the parameters of "band" to those of "space". + */ +__isl_give isl_schedule_band *isl_schedule_band_align_params( + __isl_take isl_schedule_band *band, __isl_take isl_space *space) +{ + band = isl_schedule_band_cow(band); + if (!band || !space) + goto error; + + band->mupa = isl_multi_union_pw_aff_align_params(band->mupa, space); + if (!band->mupa) + return isl_schedule_band_free(band); + + return band; +error: + isl_space_free(space); + isl_schedule_band_free(band); + return NULL; +} + +/* Compute the pullback of "band" by the function represented by "upma". + * In other words, plug in "upma" in the iteration domains of "band". + */ +__isl_give isl_schedule_band *isl_schedule_band_pullback_union_pw_multi_aff( + __isl_take isl_schedule_band *band, + __isl_take isl_union_pw_multi_aff *upma) +{ + band = isl_schedule_band_cow(band); + if (!band || !upma) + goto error; + + band->mupa = + isl_multi_union_pw_aff_pullback_union_pw_multi_aff(band->mupa, + upma); + if (!band->mupa) + return isl_schedule_band_free(band); + + return band; +error: + isl_union_pw_multi_aff_free(upma); + isl_schedule_band_free(band); + return NULL; +} + +/* Compute the gist of "band" with respect to "context". + * In particular, compute the gist of the associated partial schedule. + */ +__isl_give isl_schedule_band *isl_schedule_band_gist( + __isl_take isl_schedule_band *band, __isl_take isl_union_set *context) +{ + if (!band || !context) + goto error; + if (band->n == 0) { + isl_union_set_free(context); + return band; + } + band = isl_schedule_band_cow(band); + if (!band) + goto error; + band->mupa = isl_multi_union_pw_aff_gist(band->mupa, context); + if (!band->mupa) + return isl_schedule_band_free(band); + return band; +error: + isl_union_set_free(context); + isl_schedule_band_free(band); + return NULL; +} diff --git a/polly/lib/External/isl/isl_schedule_band.h b/polly/lib/External/isl/isl_schedule_band.h index 1a476e3..5cf30d4 100644 --- a/polly/lib/External/isl/isl_schedule_band.h +++ b/polly/lib/External/isl/isl_schedule_band.h @@ -34,6 +34,9 @@ __isl_null isl_schedule_band *isl_schedule_band_free( isl_ctx *isl_schedule_band_get_ctx(__isl_keep isl_schedule_band *band); +int isl_schedule_band_plain_is_equal(__isl_keep isl_schedule_band *band1, + __isl_keep isl_schedule_band *band2); + __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( @@ -59,5 +62,15 @@ __isl_give isl_schedule_band *isl_schedule_band_point( __isl_take isl_multi_val *sizes); __isl_give isl_schedule_band *isl_schedule_band_drop( __isl_take isl_schedule_band *band, int pos, int n); +__isl_give isl_schedule_band *isl_schedule_band_gist( + __isl_take isl_schedule_band *band, __isl_take isl_union_set *context); + +__isl_give isl_schedule_band *isl_schedule_band_reset_user( + __isl_take isl_schedule_band *band); +__isl_give isl_schedule_band *isl_schedule_band_align_params( + __isl_take isl_schedule_band *band, __isl_take isl_space *space); +__isl_give isl_schedule_band *isl_schedule_band_pullback_union_pw_multi_aff( + __isl_take isl_schedule_band *band, + __isl_take isl_union_pw_multi_aff *upma); #endif diff --git a/polly/lib/External/isl/isl_schedule_node.c b/polly/lib/External/isl/isl_schedule_node.c index 253221b..38f65be 100644 --- a/polly/lib/External/isl/isl_schedule_node.c +++ b/polly/lib/External/isl/isl_schedule_node.c @@ -1,10 +1,13 @@ /* - * Copyright 2013 Ecole Normale Superieure + * Copyright 2013-2014 Ecole Normale Superieure + * Copyright 2014 INRIA Rocquencourt * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, + * B.P. 105 - 78153 Le Chesnay, France */ #include @@ -218,6 +221,61 @@ __isl_null isl_schedule_node *isl_schedule_node_free( return NULL; } +/* Do "node1" and "node2" point to the same position in the same + * schedule? + */ +int isl_schedule_node_is_equal(__isl_keep isl_schedule_node *node1, + __isl_keep isl_schedule_node *node2) +{ + int i, n1, n2; + + if (!node1 || !node2) + return -1; + if (node1 == node2) + return 1; + if (node1->schedule != node2->schedule) + return 0; + + n1 = isl_schedule_node_get_tree_depth(node1); + n2 = isl_schedule_node_get_tree_depth(node2); + if (n1 != n2) + return 0; + for (i = 0; i < n1; ++i) + if (node1->child_pos[i] != node2->child_pos[i]) + return 0; + + return 1; +} + +/* Return the number of outer schedule dimensions of "node" + * in its schedule tree. + * + * Return -1 on error. + */ +int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node *node) +{ + int i, n; + int depth = 0; + + if (!node) + return -1; + + n = isl_schedule_tree_list_n_schedule_tree(node->ancestors); + for (i = n - 1; i >= 0; --i) { + isl_schedule_tree *tree; + + tree = isl_schedule_tree_list_get_schedule_tree( + node->ancestors, i); + if (!tree) + return -1; + if (tree->type == isl_schedule_node_band) + depth += isl_schedule_tree_band_n_member(tree); + isl_schedule_tree_free(tree); + } + + return depth; +} + /* Internal data structure for * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff * @@ -651,33 +709,72 @@ int isl_schedule_node_n_children(__isl_keep isl_schedule_node *node) return n; } -/* Move the "node" pointer to the parent of the node it currently points to. +/* Move the "node" pointer to the ancestor of the given generation + * of the node it currently points to, where generation 0 is the node + * itself and generation 1 is its parent. */ -__isl_give isl_schedule_node *isl_schedule_node_parent( - __isl_take isl_schedule_node *node) +__isl_give isl_schedule_node *isl_schedule_node_ancestor( + __isl_take isl_schedule_node *node, int generation) { int n; isl_schedule_tree *tree; - node = isl_schedule_node_cow(node); if (!node) return NULL; - if (!isl_schedule_node_has_parent(node)) + if (generation == 0) + return node; + n = isl_schedule_node_get_tree_depth(node); + if (n < 0) + return isl_schedule_node_free(node); + if (generation < 0 || generation > n) isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, - "node has no parent", + "generation out of bounds", return isl_schedule_node_free(node)); - n = isl_schedule_tree_list_n_schedule_tree(node->ancestors); - tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n - 1); + node = isl_schedule_node_cow(node); + if (!node) + return NULL; + + tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, + n - generation); isl_schedule_tree_free(node->tree); node->tree = tree; node->ancestors = isl_schedule_tree_list_drop(node->ancestors, - n - 1, 1); + n - generation, generation); if (!node->ancestors || !node->tree) return isl_schedule_node_free(node); return node; } +/* Move the "node" pointer to the parent of the node it currently points to. + */ +__isl_give isl_schedule_node *isl_schedule_node_parent( + __isl_take isl_schedule_node *node) +{ + if (!node) + return NULL; + if (!isl_schedule_node_has_parent(node)) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "node has no parent", + return isl_schedule_node_free(node)); + return isl_schedule_node_ancestor(node, 1); +} + +/* Move the "node" pointer to the root of its schedule tree. + */ +__isl_give isl_schedule_node *isl_schedule_node_root( + __isl_take isl_schedule_node *node) +{ + int n; + + if (!node) + return NULL; + n = isl_schedule_node_get_tree_depth(node); + if (n < 0) + return isl_schedule_node_free(node); + return isl_schedule_node_ancestor(node, n); +} + /* Move the "node" pointer to the child at position "pos" of the node * it currently points to. */ @@ -973,6 +1070,38 @@ __isl_give isl_schedule_node *isl_schedule_node_map_descendant( return traverse(node, &postorder_enter, &postorder_leave, &data); } +/* Traverse the ancestors of "node" from the root down to and including + * the parent of "node", calling "fn" on each of them. + * + * If "fn" returns -1 on any of the nodes, then the traversal is aborted. + * + * Return 0 on success and -1 on failure. + */ +int isl_schedule_node_foreach_ancestor_top_down( + __isl_keep isl_schedule_node *node, + int (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user) +{ + int i, n; + + if (!node) + return -1; + + n = isl_schedule_node_get_tree_depth(node); + for (i = 0; i < n; ++i) { + isl_schedule_node *ancestor; + int r; + + ancestor = isl_schedule_node_copy(node); + ancestor = isl_schedule_node_ancestor(ancestor, n - i); + r = fn(ancestor, user); + isl_schedule_node_free(ancestor); + if (r < 0) + return -1; + } + + return 0; +} + /* Return the number of members in the given band node. */ unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node *node) @@ -1506,6 +1635,476 @@ __isl_give isl_schedule_node *isl_schedule_node_insert_set( isl_schedule_node_set, filters); } +/* Remove "node" from its schedule tree and return a pointer + * to the leaf at the same position in the updated schedule tree. + * + * It is not allowed to remove the root of a schedule tree or + * a child of a set or sequence node. + */ +__isl_give isl_schedule_node *isl_schedule_node_cut( + __isl_take isl_schedule_node *node) +{ + isl_schedule_tree *leaf; + enum isl_schedule_node_type parent_type; + + if (!node) + return NULL; + if (!isl_schedule_node_has_parent(node)) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "cannot cut root", return isl_schedule_node_free(node)); + + parent_type = isl_schedule_node_get_parent_type(node); + if (parent_type == isl_schedule_node_set || + parent_type == isl_schedule_node_sequence) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "cannot cut child of set or sequence", + return isl_schedule_node_free(node)); + + leaf = isl_schedule_node_get_leaf(node); + return isl_schedule_node_graft_tree(node, leaf); +} + +/* Remove a single node from the schedule tree, attaching the child + * of "node" directly to 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. + */ +__isl_give isl_schedule_node *isl_schedule_node_delete( + __isl_take isl_schedule_node *node) +{ + int n; + isl_schedule_tree *tree; + enum isl_schedule_node_type type; + + if (!node) + return NULL; + + if (isl_schedule_node_get_tree_depth(node) == 0) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "cannot delete root node", + return isl_schedule_node_free(node)); + n = isl_schedule_node_n_children(node); + if (n != 1) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "can only delete node with a single child", + return isl_schedule_node_free(node)); + type = isl_schedule_node_get_parent_type(node); + if (type == isl_schedule_node_sequence || type == isl_schedule_node_set) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "cannot delete child of set or sequence", + return isl_schedule_node_free(node)); + + tree = isl_schedule_node_get_tree(node); + if (!tree || isl_schedule_tree_has_children(tree)) { + tree = isl_schedule_tree_child(tree, 0); + } else { + isl_schedule_tree_free(tree); + tree = isl_schedule_node_get_leaf(node); + } + node = isl_schedule_node_graft_tree(node, tree); + + return node; +} + +/* Compute the gist of the given band node with respect to "context". + */ +__isl_give isl_schedule_node *isl_schedule_node_band_gist( + __isl_take isl_schedule_node *node, __isl_take isl_union_set *context) +{ + isl_schedule_tree *tree; + + tree = isl_schedule_node_get_tree(node); + tree = isl_schedule_tree_band_gist(tree, context); + return isl_schedule_node_graft_tree(node, tree); +} + +/* Internal data structure for isl_schedule_node_gist. + * "filters" contains an element for each outer filter node + * with respect to the current position, each representing + * the intersection of the previous element and the filter on the filter node. + * The first element in the original context passed to isl_schedule_node_gist. + */ +struct isl_node_gist_data { + isl_union_set_list *filters; +}; + +/* Can we finish gisting at this node? + * That is, is the filter on the current filter node a subset of + * the original context passed to isl_schedule_node_gist? + */ +static int gist_done(__isl_keep isl_schedule_node *node, + struct isl_node_gist_data *data) +{ + isl_union_set *filter, *outer; + int subset; + + filter = isl_schedule_node_filter_get_filter(node); + outer = isl_union_set_list_get_union_set(data->filters, 0); + subset = isl_union_set_is_subset(filter, outer); + isl_union_set_free(outer); + isl_union_set_free(filter); + + return subset; +} + +/* Callback for "traverse" to enter a node and to move + * to the deepest initial subtree that should be traversed + * by isl_schedule_node_gist. + * + * The "filters" list is extended by one element each time + * we come across a filter node by the result of intersecting + * the last element in the list with the filter on the filter node. + * + * If the filter on the current filter node is a subset of + * the original context passed to isl_schedule_node_gist, + * then there is no need to go into its subtree since it cannot + * be further simplified by the context. The "filters" list is + * still extended for consistency, but the actual value of the + * added element is immaterial since it will not be used. + * + * Otherwise, the filter on the current filter node is replaced by + * the gist of the original filter with respect to the intersection + * of the original context with the intermediate filters. + * + * If the new element in the "filters" list is empty, then no elements + * can reach the descendants of the current filter node. The subtree + * underneath the filter node is therefore removed. + */ +static __isl_give isl_schedule_node *gist_enter( + __isl_take isl_schedule_node *node, void *user) +{ + struct isl_node_gist_data *data = user; + + do { + isl_union_set *filter, *inner; + int done, empty; + int n; + + switch (isl_schedule_node_get_type(node)) { + case isl_schedule_node_error: + return isl_schedule_node_free(node); + case isl_schedule_node_band: + case isl_schedule_node_domain: + case isl_schedule_node_leaf: + case isl_schedule_node_sequence: + case isl_schedule_node_set: + continue; + case isl_schedule_node_filter: + break; + } + done = gist_done(node, data); + filter = isl_schedule_node_filter_get_filter(node); + if (done < 0 || done) { + data->filters = isl_union_set_list_add(data->filters, + filter); + if (done < 0) + return isl_schedule_node_free(node); + return node; + } + n = isl_union_set_list_n_union_set(data->filters); + inner = isl_union_set_list_get_union_set(data->filters, n - 1); + filter = isl_union_set_gist(filter, isl_union_set_copy(inner)); + node = isl_schedule_node_filter_set_filter(node, + isl_union_set_copy(filter)); + filter = isl_union_set_intersect(filter, inner); + empty = isl_union_set_is_empty(filter); + data->filters = isl_union_set_list_add(data->filters, filter); + if (empty < 0) + return isl_schedule_node_free(node); + if (!empty) + continue; + node = isl_schedule_node_child(node, 0); + node = isl_schedule_node_cut(node); + node = isl_schedule_node_parent(node); + return node; + } while (isl_schedule_node_has_children(node) && + (node = isl_schedule_node_first_child(node)) != NULL); + + return node; +} + +/* Callback for "traverse" to leave a node for isl_schedule_node_gist. + * + * In particular, if the current node is a filter node, then we remove + * the element on the "filters" list that was added when we entered + * the node. There is no need to compute any gist here, since we + * already did that when we entered the node. + * + * If the current node is a band node, then we compute the gist of + * the band node with respect to the intersection of the original context + * and the intermediate filters. + * + * If the current node is a sequence or set node, then some of + * the filter children may have become empty and so they are removed. + * If only one child is left, then the set or sequence node along with + * the single remaining child filter is removed. The filter can be + * removed because the filters on a sequence or set node are supposed + * to partition the incoming domain instances. + * In principle, it should then be impossible for there to be zero + * remaining children, but should this happen, we replace the entire + * subtree with an empty filter. + */ +static __isl_give isl_schedule_node *gist_leave( + __isl_take isl_schedule_node *node, void *user) +{ + struct isl_node_gist_data *data = user; + isl_schedule_tree *tree; + int i, n; + isl_union_set *filter; + + switch (isl_schedule_node_get_type(node)) { + case isl_schedule_node_error: + return isl_schedule_node_free(node); + case isl_schedule_node_filter: + n = isl_union_set_list_n_union_set(data->filters); + data->filters = isl_union_set_list_drop(data->filters, + n - 1, 1); + break; + case isl_schedule_node_band: + n = isl_union_set_list_n_union_set(data->filters); + filter = isl_union_set_list_get_union_set(data->filters, n - 1); + node = isl_schedule_node_band_gist(node, filter); + break; + case isl_schedule_node_set: + case isl_schedule_node_sequence: + tree = isl_schedule_node_get_tree(node); + n = isl_schedule_tree_n_children(tree); + for (i = n - 1; i >= 0; --i) { + isl_schedule_tree *child; + isl_union_set *filter; + int empty; + + child = isl_schedule_tree_get_child(tree, i); + filter = isl_schedule_tree_filter_get_filter(child); + empty = isl_union_set_is_empty(filter); + isl_union_set_free(filter); + isl_schedule_tree_free(child); + if (empty < 0) + tree = isl_schedule_tree_free(tree); + else if (empty) + tree = isl_schedule_tree_drop_child(tree, i); + } + n = isl_schedule_tree_n_children(tree); + node = isl_schedule_node_graft_tree(node, tree); + if (n == 1) { + node = isl_schedule_node_delete(node); + node = isl_schedule_node_delete(node); + } else if (n == 0) { + isl_space *space; + + filter = + isl_union_set_list_get_union_set(data->filters, 0); + space = isl_union_set_get_space(filter); + isl_union_set_free(filter); + filter = isl_union_set_empty(space); + node = isl_schedule_node_cut(node); + node = isl_schedule_node_insert_filter(node, filter); + } + break; + case isl_schedule_node_domain: + case isl_schedule_node_leaf: + break; + } + + return node; +} + +/* Compute the gist of the subtree at "node" with respect to + * the reaching domain elements in "context". + * In particular, compute the gist of all band and filter nodes + * in the subtree with respect to "context". Children of set or sequence + * nodes that end up with an empty filter are removed completely. + * + * We keep track of the intersection of "context" with all outer filters + * of the current node within the subtree in the final element of "filters". + * Initially, this list contains the single element "context" and it is + * extended or shortened each time we enter or leave a filter node. + */ +__isl_give isl_schedule_node *isl_schedule_node_gist( + __isl_take isl_schedule_node *node, __isl_take isl_union_set *context) +{ + struct isl_node_gist_data data; + + data.filters = isl_union_set_list_from_union_set(context); + node = traverse(node, &gist_enter, &gist_leave, &data); + isl_union_set_list_free(data.filters); + return node; +} + +/* Intersect the domain of domain node "node" with "domain". + * + * If the domain of "node" is already a subset of "domain", + * then nothing needs to be changed. + * + * Otherwise, we replace the domain of the domain node by the intersection + * and simplify the subtree rooted at "node" with respect to this intersection. + */ +__isl_give isl_schedule_node *isl_schedule_node_domain_intersect_domain( + __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain) +{ + isl_schedule_tree *tree; + isl_union_set *uset; + int is_subset; + + if (!node || !domain) + goto error; + + uset = isl_schedule_tree_domain_get_domain(node->tree); + is_subset = isl_union_set_is_subset(uset, domain); + isl_union_set_free(uset); + if (is_subset < 0) + goto error; + if (is_subset) { + isl_union_set_free(domain); + return node; + } + + tree = isl_schedule_tree_copy(node->tree); + uset = isl_schedule_tree_domain_get_domain(tree); + uset = isl_union_set_intersect(uset, domain); + tree = isl_schedule_tree_domain_set_domain(tree, + isl_union_set_copy(uset)); + node = isl_schedule_node_graft_tree(node, tree); + + node = isl_schedule_node_child(node, 0); + node = isl_schedule_node_gist(node, uset); + node = isl_schedule_node_parent(node); + + return node; +error: + isl_schedule_node_free(node); + isl_union_set_free(domain); + return NULL; +} + +/* Reset the user pointer on all identifiers of parameters and tuples + * in the schedule node "node". + */ +__isl_give isl_schedule_node *isl_schedule_node_reset_user( + __isl_take isl_schedule_node *node) +{ + isl_schedule_tree *tree; + + tree = isl_schedule_node_get_tree(node); + tree = isl_schedule_tree_reset_user(tree); + node = isl_schedule_node_graft_tree(node, tree); + + return node; +} + +/* Align the parameters of the schedule node "node" to those of "space". + */ +__isl_give isl_schedule_node *isl_schedule_node_align_params( + __isl_take isl_schedule_node *node, __isl_take isl_space *space) +{ + isl_schedule_tree *tree; + + tree = isl_schedule_node_get_tree(node); + tree = isl_schedule_tree_align_params(tree, space); + node = isl_schedule_node_graft_tree(node, tree); + + return node; +} + +/* Compute the pullback of schedule node "node" + * by the function represented by "upma". + * In other words, plug in "upma" in the iteration domains + * of schedule node "node". + * + * Note that this is only a helper function for + * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency, + * this function should not be called on a single node without also + * calling it on all the other nodes. + */ +__isl_give isl_schedule_node *isl_schedule_node_pullback_union_pw_multi_aff( + __isl_take isl_schedule_node *node, + __isl_take isl_union_pw_multi_aff *upma) +{ + isl_schedule_tree *tree; + + tree = isl_schedule_node_get_tree(node); + tree = isl_schedule_tree_pullback_union_pw_multi_aff(tree, upma); + node = isl_schedule_node_graft_tree(node, tree); + + return node; +} + +/* Return the position of the subtree containing "node" among the children + * of "ancestor". "node" is assumed to be a descendant of "ancestor". + * In particular, both nodes should point to the same schedule tree. + * + * Return -1 on error. + */ +int isl_schedule_node_get_ancestor_child_position( + __isl_keep isl_schedule_node *node, + __isl_keep isl_schedule_node *ancestor) +{ + int n1, n2; + isl_schedule_tree *tree; + + if (!node || !ancestor) + return -1; + + if (node->schedule != ancestor->schedule) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "not a descendant", return -1); + + n1 = isl_schedule_node_get_tree_depth(ancestor); + n2 = isl_schedule_node_get_tree_depth(node); + + if (n1 >= n2) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "not a descendant", return -1); + tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n1); + isl_schedule_tree_free(tree); + if (tree != ancestor->tree) + isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid, + "not a descendant", return -1); + + return node->child_pos[n1]; +} + +/* Given two nodes that point to the same schedule tree, return their + * closest shared ancestor. + * + * Since the two nodes point to the same schedule, they share at least + * one ancestor, the root of the schedule. We move down from the root + * to the first ancestor where the respective children have a different + * child position. This is the requested ancestor. + * If there is no ancestor where the children have a different position, + * then one node is an ancestor of the other and then this node is + * the requested ancestor. + */ +__isl_give isl_schedule_node *isl_schedule_node_get_shared_ancestor( + __isl_keep isl_schedule_node *node1, + __isl_keep isl_schedule_node *node2) +{ + int i, n1, n2; + + if (!node1 || !node2) + return NULL; + if (node1->schedule != node2->schedule) + isl_die(isl_schedule_node_get_ctx(node1), isl_error_invalid, + "not part of same schedule", return NULL); + n1 = isl_schedule_node_get_tree_depth(node1); + n2 = isl_schedule_node_get_tree_depth(node2); + if (n2 < n1) + return isl_schedule_node_get_shared_ancestor(node2, node1); + if (n1 == 0) + return isl_schedule_node_copy(node1); + if (isl_schedule_node_is_equal(node1, node2)) + return isl_schedule_node_copy(node1); + + for (i = 0; i < n1; ++i) + if (node1->child_pos[i] != node2->child_pos[i]) + break; + + node1 = isl_schedule_node_copy(node1); + return isl_schedule_node_ancestor(node1, n1 - i); +} + /* Print "node" to "p". */ __isl_give isl_printer *isl_printer_print_schedule_node( diff --git a/polly/lib/External/isl/isl_schedule_node_private.h b/polly/lib/External/isl/isl_schedule_node_private.h index e8df4ac..f207291 100644 --- a/polly/lib/External/isl/isl_schedule_node_private.h +++ b/polly/lib/External/isl/isl_schedule_node_private.h @@ -38,4 +38,11 @@ __isl_give isl_schedule_node *isl_schedule_node_graft_tree( __isl_give isl_schedule_tree *isl_schedule_node_get_tree( __isl_keep isl_schedule_node *node); +__isl_give isl_schedule_node *isl_schedule_node_pullback_union_pw_multi_aff( + __isl_take isl_schedule_node *node, + __isl_take isl_union_pw_multi_aff *upma); + +__isl_give isl_schedule_node *isl_schedule_node_domain_intersect_domain( + __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain); + #endif diff --git a/polly/lib/External/isl/isl_schedule_tree.c b/polly/lib/External/isl/isl_schedule_tree.c index fffcd30..f675f64 100644 --- a/polly/lib/External/isl/isl_schedule_tree.c +++ b/polly/lib/External/isl/isl_schedule_tree.c @@ -1,10 +1,13 @@ /* - * Copyright 2013 Ecole Normale Superieure + * Copyright 2013-2014 Ecole Normale Superieure + * Copyright 2014 INRIA Rocquencourt * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, + * B.P. 105 - 78153 Le Chesnay, France */ #include @@ -286,6 +289,46 @@ error: return NULL; } +/* Construct a tree with a root node of type "type" and as children + * "tree1" and "tree2". + * If the root of one (or both) of the input trees is itself of type "type", + * then the tree is replaced by its children. + */ +__isl_give isl_schedule_tree *isl_schedule_tree_from_pair( + enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1, + __isl_take isl_schedule_tree *tree2) +{ + isl_ctx *ctx; + isl_schedule_tree_list *list; + + if (!tree1 || !tree2) + goto error; + + ctx = isl_schedule_tree_get_ctx(tree1); + if (isl_schedule_tree_get_type(tree1) == type) { + list = isl_schedule_tree_list_copy(tree1->children); + isl_schedule_tree_free(tree1); + } else { + list = isl_schedule_tree_list_alloc(ctx, 2); + list = isl_schedule_tree_list_add(list, tree1); + } + if (isl_schedule_tree_get_type(tree2) == type) { + isl_schedule_tree_list *children; + + children = isl_schedule_tree_list_copy(tree2->children); + list = isl_schedule_tree_list_concat(list, children); + isl_schedule_tree_free(tree2); + } else { + list = isl_schedule_tree_list_add(list, tree2); + } + + return isl_schedule_tree_from_children(type, list); +error: + isl_schedule_tree_free(tree1); + isl_schedule_tree_free(tree2); + return NULL; +} + /* Return the isl_ctx to which "tree" belongs. */ isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree) @@ -302,6 +345,64 @@ enum isl_schedule_node_type isl_schedule_tree_get_type( return tree ? tree->type : isl_schedule_node_error; } +/* Are "tree1" and "tree2" obviously equal to each other? + */ +int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1, + __isl_keep isl_schedule_tree *tree2) +{ + int equal; + int i, n; + + if (!tree1 || !tree2) + return -1; + if (tree1 == tree2) + return 1; + if (tree1->type != tree2->type) + return 0; + + switch (tree1->type) { + case isl_schedule_node_band: + equal = isl_schedule_band_plain_is_equal(tree1->band, + tree2->band); + break; + case isl_schedule_node_domain: + equal = isl_union_set_is_equal(tree1->domain, tree2->domain); + break; + case isl_schedule_node_filter: + equal = isl_union_set_is_equal(tree1->filter, tree2->filter); + break; + case isl_schedule_node_leaf: + case isl_schedule_node_sequence: + case isl_schedule_node_set: + equal = 1; + break; + case isl_schedule_node_error: + equal = -1; + break; + } + + if (equal < 0 || !equal) + return equal; + + n = isl_schedule_tree_n_children(tree1); + if (n != isl_schedule_tree_n_children(tree2)) + return 0; + for (i = 0; i < n; ++i) { + isl_schedule_tree *child1, *child2; + + child1 = isl_schedule_tree_get_child(tree1, i); + child2 = isl_schedule_tree_get_child(tree2, i); + equal = isl_schedule_tree_plain_is_equal(child1, child2); + isl_schedule_tree_free(child1); + isl_schedule_tree_free(child2); + + if (equal < 0 || !equal) + return equal; + } + + return 1; +} + /* Does "tree" have any children, other than an implicit leaf. */ int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree) @@ -360,6 +461,37 @@ __isl_give isl_schedule_tree *isl_schedule_tree_reset_children( return tree; } +/* Remove the child at position "pos" from the children of "tree". + * If there was only one child to begin with, then remove all children. + */ +__isl_give isl_schedule_tree *isl_schedule_tree_drop_child( + __isl_take isl_schedule_tree *tree, int pos) +{ + int n; + + tree = isl_schedule_tree_cow(tree); + if (!tree) + return NULL; + + if (!isl_schedule_tree_has_children(tree)) + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid, + "tree does not have any explicit children", + return isl_schedule_tree_free(tree)); + n = isl_schedule_tree_list_n_schedule_tree(tree->children); + if (pos < 0 || pos >= n) + isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid, + "position out of bounds", + return isl_schedule_tree_free(tree)); + if (n == 1) + return isl_schedule_tree_reset_children(tree); + + tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1); + if (!tree->children) + return isl_schedule_tree_free(tree); + + return tree; +} + /* Replace the child at position "pos" of "tree" by "child". * * If the new child is a leaf, then it is not explicitly @@ -470,6 +602,35 @@ __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter( return isl_schedule_tree_replace_child(res, 0, tree); } +/* Insert a filter node with filter set "filter" + * in each of the children of "tree". + */ +__isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter) +{ + int i, n; + + if (!tree || !filter) + goto error; + + n = isl_schedule_tree_n_children(tree); + for (i = 0; i < n; ++i) { + isl_schedule_tree *child; + + child = isl_schedule_tree_get_child(tree, i); + child = isl_schedule_tree_insert_filter(child, + isl_union_set_copy(filter)); + tree = isl_schedule_tree_replace_child(tree, i, child); + } + + isl_union_set_free(filter); + return tree; +error: + isl_union_set_free(filter); + isl_schedule_tree_free(tree); + return NULL; +} + /* Return the number of members in the band tree root. */ unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree) @@ -1234,6 +1395,197 @@ error: return NULL; } +/* Reset the user pointer on all identifiers of parameters and tuples + * in the root of "tree". + */ +__isl_give isl_schedule_tree *isl_schedule_tree_reset_user( + __isl_take isl_schedule_tree *tree) +{ + if (isl_schedule_tree_is_leaf(tree)) + return tree; + + tree = isl_schedule_tree_cow(tree); + if (!tree) + return NULL; + + switch (tree->type) { + case isl_schedule_node_error: + return isl_schedule_tree_free(tree); + case isl_schedule_node_band: + tree->band = isl_schedule_band_reset_user(tree->band); + if (!tree->band) + return isl_schedule_tree_free(tree); + break; + case isl_schedule_node_domain: + tree->domain = isl_union_set_reset_user(tree->domain); + if (!tree->domain) + return isl_schedule_tree_free(tree); + break; + case isl_schedule_node_filter: + tree->filter = isl_union_set_reset_user(tree->filter); + if (!tree->filter) + return isl_schedule_tree_free(tree); + break; + case isl_schedule_node_leaf: + case isl_schedule_node_sequence: + case isl_schedule_node_set: + break; + } + + return tree; +} + +/* Align the parameters of the root of "tree" to those of "space". + */ +__isl_give isl_schedule_tree *isl_schedule_tree_align_params( + __isl_take isl_schedule_tree *tree, __isl_take isl_space *space) +{ + if (!space) + goto error; + + if (isl_schedule_tree_is_leaf(tree)) { + isl_space_free(space); + return tree; + } + + tree = isl_schedule_tree_cow(tree); + if (!tree) + goto error; + + switch (tree->type) { + case isl_schedule_node_error: + goto error; + case isl_schedule_node_band: + tree->band = isl_schedule_band_align_params(tree->band, space); + if (!tree->band) + return isl_schedule_tree_free(tree); + break; + case isl_schedule_node_domain: + tree->domain = isl_union_set_align_params(tree->domain, space); + if (!tree->domain) + return isl_schedule_tree_free(tree); + break; + case isl_schedule_node_filter: + tree->filter = isl_union_set_align_params(tree->filter, space); + if (!tree->filter) + return isl_schedule_tree_free(tree); + break; + case isl_schedule_node_leaf: + case isl_schedule_node_sequence: + case isl_schedule_node_set: + isl_space_free(space); + break; + } + + return tree; +error: + isl_space_free(space); + isl_schedule_tree_free(tree); + return NULL; +} + +/* Does "tree" involve the iteration domain? + * That is, does it need to be modified + * by isl_schedule_tree_pullback_union_pw_multi_aff? + */ +static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree) +{ + if (!tree) + return -1; + + switch (tree->type) { + case isl_schedule_node_error: + return -1; + case isl_schedule_node_band: + case isl_schedule_node_domain: + case isl_schedule_node_filter: + return 1; + case isl_schedule_node_leaf: + case isl_schedule_node_sequence: + case isl_schedule_node_set: + return 0; + } +} + +/* Compute the pullback of the root node of "tree" by the function + * represented by "upma". + * In other words, plug in "upma" in the iteration domains of + * the root node of "tree". + * + * We first check if the root node involves any iteration domains. + * If so, we handle the specific cases. + */ +__isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff( + __isl_take isl_schedule_tree *tree, + __isl_take isl_union_pw_multi_aff *upma) +{ + int involves; + + if (!tree || !upma) + goto error; + + involves = involves_iteration_domain(tree); + if (involves < 0) + goto error; + if (!involves) { + isl_union_pw_multi_aff_free(upma); + return tree; + } + + tree = isl_schedule_tree_cow(tree); + if (!tree) + goto error; + + if (tree->type == isl_schedule_node_band) { + tree->band = isl_schedule_band_pullback_union_pw_multi_aff( + tree->band, upma); + if (!tree->band) + return isl_schedule_tree_free(tree); + } else if (tree->type == isl_schedule_node_domain) { + tree->domain = + isl_union_set_preimage_union_pw_multi_aff(tree->domain, + upma); + if (!tree->domain) + return isl_schedule_tree_free(tree); + } else if (tree->type == isl_schedule_node_filter) { + tree->filter = + isl_union_set_preimage_union_pw_multi_aff(tree->filter, + upma); + if (!tree->filter) + return isl_schedule_tree_free(tree); + } + + return tree; +error: + isl_union_pw_multi_aff_free(upma); + isl_schedule_tree_free(tree); + return NULL; +} + +/* Compute the gist of the band tree root with respect to "context". + */ +__isl_give isl_schedule_tree *isl_schedule_tree_band_gist( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context) +{ + 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", goto error); + tree = isl_schedule_tree_cow(tree); + if (!tree) + goto error; + + tree->band = isl_schedule_band_gist(tree->band, context); + if (!tree->band) + return isl_schedule_tree_free(tree); + return tree; +error: + isl_union_set_free(context); + isl_schedule_tree_free(tree); + return NULL; +} + /* Are any members in "band" marked coincident? */ static int any_coincident(__isl_keep isl_schedule_band *band) diff --git a/polly/lib/External/isl/isl_schedule_tree.h b/polly/lib/External/isl/isl_schedule_tree.h index 34a439b..a5c5486 100644 --- a/polly/lib/External/isl/isl_schedule_tree.h +++ b/polly/lib/External/isl/isl_schedule_tree.h @@ -49,6 +49,9 @@ enum isl_schedule_node_type isl_schedule_tree_get_type( __isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx); int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree); +int isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1, + __isl_keep isl_schedule_tree *tree2); + __isl_give isl_schedule_tree *isl_schedule_tree_copy( __isl_keep isl_schedule_tree *tree); __isl_null isl_schedule_tree *isl_schedule_tree_free( @@ -63,6 +66,9 @@ __isl_give isl_schedule_tree *isl_schedule_tree_from_filter( __isl_give isl_schedule_tree *isl_schedule_tree_from_children( enum isl_schedule_node_type type, __isl_take isl_schedule_tree_list *list); +__isl_give isl_schedule_tree *isl_schedule_tree_from_pair( + enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1, + __isl_take isl_schedule_tree *tree2); __isl_give isl_space *isl_schedule_tree_band_get_space( __isl_keep isl_schedule_tree *tree); @@ -103,6 +109,8 @@ __isl_give isl_schedule_tree *isl_schedule_tree_insert_domain( __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain); __isl_give isl_schedule_tree *isl_schedule_tree_insert_filter( __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter); +__isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter); __isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves( __isl_take isl_schedule_tree *tree1, @@ -116,15 +124,27 @@ __isl_give isl_schedule_tree *isl_schedule_tree_band_tile( __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes); __isl_give isl_schedule_tree *isl_schedule_tree_band_split( __isl_take isl_schedule_tree *tree, int pos); +__isl_give isl_schedule_tree *isl_schedule_tree_band_gist( + __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context); __isl_give isl_schedule_tree *isl_schedule_tree_child( __isl_take isl_schedule_tree *tree, int pos); __isl_give isl_schedule_tree *isl_schedule_tree_reset_children( __isl_take isl_schedule_tree *tree); +__isl_give isl_schedule_tree *isl_schedule_tree_drop_child( + __isl_take isl_schedule_tree *tree, int pos); __isl_give isl_schedule_tree *isl_schedule_tree_replace_child( __isl_take isl_schedule_tree *tree, int pos, __isl_take isl_schedule_tree *new_child); +__isl_give isl_schedule_tree *isl_schedule_tree_reset_user( + __isl_take isl_schedule_tree *tree); +__isl_give isl_schedule_tree *isl_schedule_tree_align_params( + __isl_take isl_schedule_tree *tree, __isl_take isl_space *space); +__isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff( + __isl_take isl_schedule_tree *tree, + __isl_take isl_union_pw_multi_aff *upma); + __isl_give isl_printer *isl_printer_print_schedule_tree( __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree); __isl_give isl_printer *isl_printer_print_schedule_tree_mark( diff --git a/polly/lib/External/isl/isl_scheduler.c b/polly/lib/External/isl/isl_scheduler.c index c552f51..705eada 100644 --- a/polly/lib/External/isl/isl_scheduler.c +++ b/polly/lib/External/isl/isl_scheduler.c @@ -2363,10 +2363,9 @@ static __isl_give isl_multi_aff *node_extract_partial_schedule_multi_aff( isl_local_space *ls; isl_aff *aff; isl_multi_aff *ma; - int nrow, ncol; + int nrow; nrow = isl_mat_rows(node->sched); - ncol = isl_mat_cols(node->sched) - 1; if (node->compressed) space = isl_multi_aff_get_domain_space(node->decompress); else diff --git a/polly/lib/External/isl/isl_space.c b/polly/lib/External/isl/isl_space.c index 1a5d6d3..952e5b5 100644 --- a/polly/lib/External/isl/isl_space.c +++ b/polly/lib/External/isl/isl_space.c @@ -1305,7 +1305,7 @@ __isl_give isl_space *isl_space_domain_factor_domain( nested = space->nested[0]; domain = isl_space_copy(space); - domain = isl_space_drop_dims(space, isl_dim_in, + domain = isl_space_drop_dims(domain, isl_dim_in, nested->n_in, nested->n_out); if (!domain) return isl_space_free(space); @@ -1344,7 +1344,7 @@ __isl_give isl_space *isl_space_domain_factor_range( nested = space->nested[0]; range = isl_space_copy(space); - range = isl_space_drop_dims(space, isl_dim_in, 0, nested->n_in); + range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in); if (!range) return isl_space_free(space); if (nested->tuple_id[1]) { @@ -1382,7 +1382,7 @@ __isl_give isl_space *isl_space_range_factor_domain( nested = space->nested[1]; domain = isl_space_copy(space); - domain = isl_space_drop_dims(space, isl_dim_out, + domain = isl_space_drop_dims(domain, isl_dim_out, nested->n_in, nested->n_out); if (!domain) return isl_space_free(space); @@ -1421,7 +1421,7 @@ __isl_give isl_space *isl_space_range_factor_range( nested = space->nested[1]; range = isl_space_copy(space); - range = isl_space_drop_dims(space, isl_dim_out, 0, nested->n_in); + range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in); if (!range) return isl_space_free(space); if (nested->tuple_id[1]) { diff --git a/polly/lib/External/isl/isl_tab_pip.c b/polly/lib/External/isl/isl_tab_pip.c index 2a4a4f7..49ede65 100644 --- a/polly/lib/External/isl/isl_tab_pip.c +++ b/polly/lib/External/isl/isl_tab_pip.c @@ -3137,11 +3137,8 @@ static int context_gbr_detect_equalities(struct isl_context *context, struct isl_tab *tab) { struct isl_context_gbr *cgbr = (struct isl_context_gbr *)context; - struct isl_ctx *ctx; unsigned n_ineq; - ctx = cgbr->tab->mat->ctx; - if (!cgbr->cone) { struct isl_basic_set *bset = isl_tab_peek_bset(cgbr->tab); cgbr->cone = isl_tab_from_recession_cone(bset, 0); @@ -3833,7 +3830,6 @@ static void find_solutions(struct isl_sol *sol, struct isl_tab *tab) sol_inc_level(sol); find_in_pos(sol, tab, ineq->el); tab->row_sign[split] = isl_tab_row_neg; - row = split; isl_seq_neg(ineq->el, ineq->el, ineq->size); isl_int_sub_ui(ineq->el[0], ineq->el[0], 1); if (!sol->error) @@ -4191,7 +4187,7 @@ static int parallel_constraints(__isl_keep isl_basic_map *bmap, int *first, int *second) { int i; - isl_ctx *ctx = isl_basic_map_get_ctx(bmap); + isl_ctx *ctx; struct isl_hash_table *table = NULL; struct isl_hash_table_entry *entry; struct isl_constraint_equal_info info; @@ -4295,13 +4291,11 @@ static __isl_give isl_set *set_minimum(__isl_take isl_space *dim, { int i, k; isl_basic_set *bset = NULL; - isl_ctx *ctx; isl_set *set = NULL; if (!dim || !var) goto error; - ctx = isl_space_get_ctx(dim); set = isl_set_alloc_space(isl_space_copy(dim), var->n_row, ISL_SET_DISJOINT); @@ -5447,7 +5441,6 @@ static __isl_give isl_pw_aff *set_minimum_pa(__isl_take isl_space *space, int i; isl_aff *aff = NULL; isl_basic_set *bset = NULL; - isl_ctx *ctx; isl_pw_aff *paff = NULL; isl_space *pw_space; isl_local_space *ls = NULL; @@ -5455,7 +5448,6 @@ static __isl_give isl_pw_aff *set_minimum_pa(__isl_take isl_space *space, if (!space || !var) goto error; - ctx = isl_space_get_ctx(space); ls = isl_local_space_from_space(isl_space_copy(space)); pw_space = isl_space_copy(space); pw_space = isl_space_from_domain(pw_space); diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index 1a4b7b0..ea8311d 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -4546,6 +4546,9 @@ struct { { "{ B[i] -> C[([i/2])] }", "{ B[5] }", "{ C[2] }" }, { "[n] -> { B[i,j] -> C[([i/2]) + 2j] }", "[n] -> { B[n,[n/3]] }", "[n] -> { C[([n/2]) + 2*[n/3]] }", }, + { "{ [i, j] -> [floor((i)/4) + floor((2*i+j)/5)] }", + "{ [i, j] -> [floor((i)/3), j] }", + "{ [i, j] -> [(floor((i)/12) + floor((j + 2*floor((i)/3))/5))] }" }, }; static int test_pullback(isl_ctx *ctx) @@ -4573,25 +4576,33 @@ static int test_pullback(isl_ctx *ctx) return 0; } -/* Check that negation is printed correctly. +/* Check that negation is printed correctly and that equal expressions + * are correctly identified. */ static int test_ast(isl_ctx *ctx) { isl_ast_expr *expr, *expr1, *expr2, *expr3; char *str; - int ok; + int ok, equal; expr1 = isl_ast_expr_from_id(isl_id_alloc(ctx, "A", NULL)); expr2 = isl_ast_expr_from_id(isl_id_alloc(ctx, "B", NULL)); expr = isl_ast_expr_add(expr1, expr2); + expr2 = isl_ast_expr_copy(expr); expr = isl_ast_expr_neg(expr); + expr2 = isl_ast_expr_neg(expr2); + equal = isl_ast_expr_is_equal(expr, expr2); str = isl_ast_expr_to_str(expr); ok = str ? !strcmp(str, "-(A + B)") : -1; free(str); isl_ast_expr_free(expr); + isl_ast_expr_free(expr2); - if (ok < 0) + if (ok < 0 || equal < 0) return -1; + if (!equal) + isl_die(ctx, isl_error_unknown, + "equal expressions not considered equal", return -1); if (!ok) isl_die(ctx, isl_error_unknown, "isl_ast_expr printed incorrectly", return -1); diff --git a/polly/lib/External/isl/isl_transitive_closure.c b/polly/lib/External/isl/isl_transitive_closure.c index d91a58f..e14987c 100644 --- a/polly/lib/External/isl/isl_transitive_closure.c +++ b/polly/lib/External/isl/isl_transitive_closure.c @@ -1948,14 +1948,12 @@ static __isl_give isl_map *construct_power(__isl_keep isl_map *map, { struct isl_map *app = NULL; isl_space *dim = NULL; - unsigned d; if (!map) return NULL; dim = isl_map_get_space(map); - d = isl_space_dim(dim, isl_dim_in); dim = isl_space_add_dims(dim, isl_dim_in, 1); dim = isl_space_add_dims(dim, isl_dim_out, 1); diff --git a/polly/lib/External/isl/isl_vertices.c b/polly/lib/External/isl/isl_vertices.c index c17224d..4e17b11 100644 --- a/polly/lib/External/isl/isl_vertices.c +++ b/polly/lib/External/isl/isl_vertices.c @@ -114,14 +114,12 @@ static int add_vertex(struct isl_vertex_list **list, __isl_keep isl_basic_set *bset, struct isl_tab *tab) { unsigned nvar; - unsigned nparam; struct isl_vertex_list *v = NULL; if (isl_tab_detect_implicit_equalities(tab) < 0) return -1; nvar = isl_basic_set_dim(bset, isl_dim_set); - nparam = isl_basic_set_dim(bset, isl_dim_param); v = isl_calloc_type(tab->mat->ctx, struct isl_vertex_list); if (!v) @@ -155,13 +153,10 @@ error: static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset) { isl_vertices *vertices; - unsigned nparam; if (!bset) return NULL; - nparam = isl_basic_set_dim(bset, isl_dim_param); - vertices = isl_calloc_type(bset->ctx, isl_vertices); if (!vertices) return NULL; @@ -183,13 +178,10 @@ static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset) static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset) { isl_vertices *vertices; - unsigned nparam; if (!bset) return NULL; - nparam = isl_basic_set_dim(bset, isl_dim_param); - vertices = isl_calloc_type(bset->ctx, isl_vertices); if (!vertices) return NULL; diff --git a/polly/test/Dependences/do_pluto_matmult.ll b/polly/test/Dependences/do_pluto_matmult.ll index 74484a2..bfad357 100644 --- a/polly/test/Dependences/do_pluto_matmult.ll +++ b/polly/test/Dependences/do_pluto_matmult.ll @@ -66,11 +66,12 @@ do.end45: ; preds = %do.cond42 } ; VALUE: RAW dependences: -; VALUE: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : i0 >= 0 and i0 <= 35 and i1 >= 0 and i1 <= 35 and i2 >= 0 and i2 <= 34 } +; VALUE: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : i0 >= 0 and i0 <= 35 and i1 >= 0 and i1 <= 35 and i2 >= 0 and i2 <= 34 } ; VALUE: WAR dependences: -; VALUE: { } +; VALUE: { } ; VALUE: WAW dependences: -; VALUE: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : i0 >= 0 and i0 <= 35 and i1 >= 0 and i1 <= 35 and i2 >= 0 and i2 <= 34 } +; VALUE: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, 1 + i2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 <= 34 and i2 >= 0 } + ; MEMORY: RAW dependences: ; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 } diff --git a/polly/test/Dependences/reduction_multiple_reductions_2.ll b/polly/test/Dependences/reduction_multiple_reductions_2.ll index 68a1e25..1cc4caf 100644 --- a/polly/test/Dependences/reduction_multiple_reductions_2.ll +++ b/polly/test/Dependences/reduction_multiple_reductions_2.ll @@ -2,7 +2,7 @@ ; ; CHECK: RAW dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S3[i0] : i0 <= 1023 and i0 >= 0 and i1 <= 1023 and i1 >= 0 -; CHECK-DAG: Stmt_S3[i0] -> Stmt_S0[1 + i0] : i0 >= 0 and i0 <= 1022 +; CHECK-DAG: Stmt_S3[i0] -> Stmt_S0[1 + i0] : i0 <= 1022 and i0 >= 0 ; CHECK-DAG: Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0 ; These are the important RAW dependences, as they need to originate/end in only one iteration: ; CHECK-DAG: Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0 @@ -11,7 +11,7 @@ ; CHECK: { } ; CHECK: WAW dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S3[i0] : i0 <= 1023 and i0 >= 0 and i1 <= 1023 and i1 >= 0 -; CHECK-DAG: Stmt_S3[i0] -> Stmt_S0[1 + i0] : i0 >= 0 and i0 <= 1022 +; CHECK-DAG: Stmt_S3[i0] -> Stmt_S0[1 + i0] : i0 <= 1022 and i0 >= 0 ; CHECK-DAG: Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0 ; These are the important WAW dependences, as they need to originate/end in only one iteration: ; CHECK-DAG: Stmt_S1[i0, 1023] -> Stmt_S2[i0, o1] : i0 <= 1023 and i0 >= 0 and o1 <= 1023 and o1 >= 0 diff --git a/polly/test/Dependences/reduction_privatization_deps_2.ll b/polly/test/Dependences/reduction_privatization_deps_2.ll index 96411a2..bf2b9c5 100644 --- a/polly/test/Dependences/reduction_privatization_deps_2.ll +++ b/polly/test/Dependences/reduction_privatization_deps_2.ll @@ -5,12 +5,12 @@ ; ; CHECK: RAW dependences: ; CHECK-DAG: Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : i0 <= 97 and i0 >= 0 and o1 <= 99 and o1 >= 0 -; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[i0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0 ; CHECK: WAR dependences: ; CHECK: { } ; CHECK: WAW dependences: ; CHECK-DAG: Stmt_S3[i0] -> Stmt_S2[1 + i0, o1] : i0 <= 97 and i0 >= 0 and o1 <= 99 and o1 >= 0 -; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[i0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0 ; CHECK: Reduction dependences: ; CHECK: { Stmt_S2[i0, i1] -> Stmt_S2[i0, 1 + i1] : i0 <= 98 and i0 >= 0 and i1 <= 98 and i1 >= 0 } ; diff --git a/polly/test/Dependences/reduction_privatization_deps_3.ll b/polly/test/Dependences/reduction_privatization_deps_3.ll index 8727c72..66b9ccd 100644 --- a/polly/test/Dependences/reduction_privatization_deps_3.ll +++ b/polly/test/Dependences/reduction_privatization_deps_3.ll @@ -3,13 +3,13 @@ ; CHECK: RAW dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S3[o0] : o0 <= 1 and i1 <= 1 - i0 and o0 <= 1 + i0 - i1 and o0 >= 1 - i1 ; CHECK-DAG: Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : i0 <= 1 and i0 >= 0 and o0 >= 1 + i0 and o0 <= 98 -; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[2 + i0] : i0 >= 0 and i0 <= 96 +; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[2 + i0] : i0 <= 96 and i0 >= 0 ; CHECK: WAR dependences: ; CHECK: { } ; CHECK: WAW dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S3[o0] : o0 <= 1 and i1 <= 1 - i0 and o0 <= 1 + i0 - i1 and o0 >= 1 - i1 ; CHECK-DAG: Stmt_S3[i0] -> Stmt_S2[o0, 1 - i0] : i0 <= 1 and i0 >= 0 and o0 >= 1 + i0 and o0 <= 98 -; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[2 + i0] : i0 >= 0 and i0 <= 96 +; CHECK-DAG: Stmt_S1[i0] -> Stmt_S3[2 + i0] : i0 <= 96 and i0 >= 0 ; CHECK: Reduction dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : i0 <= 97 and i0 >= 0 and i1 <= 98 - i0 and i1 >= 0 and i1 >= 2 - i0 ; CHECK-DAG: Stmt_S2[0, 0] -> Stmt_S2[1, 0] diff --git a/polly/test/Dependences/reduction_privatization_deps_4.ll b/polly/test/Dependences/reduction_privatization_deps_4.ll index c8f5546..bfececb 100644 --- a/polly/test/Dependences/reduction_privatization_deps_4.ll +++ b/polly/test/Dependences/reduction_privatization_deps_4.ll @@ -2,15 +2,15 @@ ; ; CHECK: RAW dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i1 >= 1 + i0 and i1 <= 98 -; CHECK-DAG: Stmt_S1[i0] -> Stmt_S2[i0, i0] : i0 >= 0 and i0 <= 98 -; CHECK-DAG: Stmt_S2[i0, i0] -> Stmt_S3[i0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S1[i0] -> Stmt_S2[i0, i0] : i0 <= 98 and i0 >= 0 +; CHECK-DAG: Stmt_S2[i0, i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0 ; CHECK-DAG: Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and o0 >= 1 + i0 and o0 <= 98 ; CHECK: WAR dependences: ; CHECK-DAG: { } ; CHECK: WAW dependences: ; CHECK-DAG: Stmt_S2[i0, i1] -> Stmt_S1[i1] : i0 >= 0 and i1 >= 1 + i0 and i1 <= 98 -; CHECK-DAG: Stmt_S1[i0] -> Stmt_S2[i0, i0] : i0 >= 0 and i0 <= 98 -; CHECK-DAG: Stmt_S2[i0, i0] -> Stmt_S3[i0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S1[i0] -> Stmt_S2[i0, i0] : i0 <= 98 and i0 >= 0 +; CHECK-DAG: Stmt_S2[i0, i0] -> Stmt_S3[i0] : i0 <= 98 and i0 >= 0 ; CHECK-DAG: Stmt_S3[i0] -> Stmt_S2[o0, i0] : i0 >= 0 and o0 >= 1 + i0 and o0 <= 98 ; CHECK: Reduction dependences: ; CHECK-DAG: { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : (i0 >= 0 and i1 >= 2 + i0 and i1 <= 99) or (i0 <= 97 and i1 >= 0 and i1 <= -1 + i0) } diff --git a/polly/test/Dependences/reduction_privatization_deps_5.ll b/polly/test/Dependences/reduction_privatization_deps_5.ll index b879b05..eb4e4fb 100644 --- a/polly/test/Dependences/reduction_privatization_deps_5.ll +++ b/polly/test/Dependences/reduction_privatization_deps_5.ll @@ -1,13 +1,13 @@ ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-dependences -analyze < %s | FileCheck %s ; ; CHECK: RAW dependences: -; CHECK-DAG: Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : i0 >= 0 and i0 <= 97 -; CHECK-DAG: Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : i0 <= 97 and i0 >= 0 +; CHECK-DAG: Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : i0 <= 98 and i0 >= 0 ; CHECK: WAR dependences: ; CHECK-DAG: { } ; CHECK: WAW dependences: -; CHECK-DAG: Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : i0 >= 0 and i0 <= 97 -; CHECK-DAG: Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S2[i0, 0] -> Stmt_S1[1 + i0, 0] : i0 <= 97 and i0 >= 0 +; CHECK-DAG: Stmt_S1[i0, 0] -> Stmt_S2[i0, 0] : i0 <= 98 and i0 >= 0 ; CHECK: Reduction dependences: ; CHECK-DAG: { Stmt_S2[i0, i1] -> Stmt_S2[1 + i0, i1] : i0 <= 97 and i0 >= 0 and i1 <= 99 and i1 >= 1 } ; diff --git a/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll b/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll index fa8c438..678d633 100644 --- a/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll +++ b/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll @@ -10,11 +10,11 @@ ; CHECK: } ; CHECK: Wrapped Dependences: ; CHECK: RAW dependences: -; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } +; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 } ; CHECK: WAR dependences: ; CHECK: { } ; CHECK: WAW dependences: -; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 } +; CHECK: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 } ; CHECK: Reduction dependences: ; CHECK: n/a ; CHECK: Final Wrapped Dependences: diff --git a/polly/test/Dependences/reduction_simple_privatization_deps_2.ll b/polly/test/Dependences/reduction_simple_privatization_deps_2.ll index 736b4611..6783da1 100644 --- a/polly/test/Dependences/reduction_simple_privatization_deps_2.ll +++ b/polly/test/Dependences/reduction_simple_privatization_deps_2.ll @@ -3,13 +3,13 @@ ; CHECK: RAW dependences: ; CHECK-DAG: Stmt_S1[i0, i1] -> Stmt_S2[i0] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0 ; CHECK-DAG: Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 99 and i0 >= 0 and o1 <= 99 and o1 >= 0 -; CHECK-DAG: Stmt_S2[i0] -> Stmt_S0[1 + i0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S2[i0] -> Stmt_S0[1 + i0] : i0 <= 98 and i0 >= 0 ; CHECK: WAR dependences: ; CHECK-DAG: { } ; CHECK: WAW dependences: ; CHECK-DAG: Stmt_S1[i0, i1] -> Stmt_S2[i0] : i0 <= 99 and i0 >= 0 and i1 <= 99 and i1 >= 0 ; CHECK-DAG: Stmt_S0[i0] -> Stmt_S1[i0, o1] : i0 <= 99 and i0 >= 0 and o1 <= 99 and o1 >= 0 -; CHECK-DAG: Stmt_S2[i0] -> Stmt_S0[1 + i0] : i0 >= 0 and i0 <= 98 +; CHECK-DAG: Stmt_S2[i0] -> Stmt_S0[1 + i0] : i0 <= 98 and i0 >= 0 ; CHECK: Reduction dependences: ; CHECK-DAG: Stmt_S1[i0, i1] -> Stmt_S1[i0, 1 + i1] : i0 <= 99 and i0 >= 0 and i1 <= 98 and i1 >= 0 ; diff --git a/polly/test/Dependences/sequential_loops.ll b/polly/test/Dependences/sequential_loops.ll index f478aaf..e4d5353 100644 --- a/polly/test/Dependences/sequential_loops.ll +++ b/polly/test/Dependences/sequential_loops.ll @@ -273,7 +273,7 @@ exit.2: ; VALUE: RAW dependences: ; VALUE: [p] -> { ; VALUE: Stmt_S1[i0] -> Stmt_S2[-p + i0] : -; VALUE: i0 >= p and i0 <= 9 + p and p <= 190 and i0 <= 99 and i0 >= 0 +; VALUE: p <= 190 and i0 >= p and i0 <= 9 + p and i0 >= 0 and i0 <= 99 ; VALUE: } ; VALUE: WAR dependences: ; VALUE: [p] -> { -- 2.7.4