diff options
43 files changed, 1668 insertions, 258 deletions
diff --git a/polly/lib/External/CMakeLists.txt b/polly/lib/External/CMakeLists.txt index d83be0cafc7..77cc28c70c0 100644 --- a/polly/lib/External/CMakeLists.txt +++ b/polly/lib/External/CMakeLists.txt @@ -203,6 +203,7 @@ set (ISL_FILES isl/isl_hash.c isl/isl_id.c isl/isl_id_to_ast_expr.c + isl/isl_id_to_id.c isl/isl_id_to_pw_aff.c isl/isl_ilp.c isl/isl_imath.c diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID index a33d8b7db60..7169df5d106 100644 --- a/polly/lib/External/isl/GIT_HEAD_ID +++ b/polly/lib/External/isl/GIT_HEAD_ID @@ -1 +1 @@ -isl-0.16.1-20-gee54b48 +isl-0.16.1-68-g8fad211 diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am index 887d2c2ff54..81bc9a0fb03 100644 --- a/polly/lib/External/isl/Makefile.am +++ b/polly/lib/External/isl/Makefile.am @@ -108,6 +108,7 @@ libisl_la_SOURCES = \ isl_hash.c \ isl_hash_private.h \ isl_id_to_ast_expr.c \ + isl_id_to_id.c \ isl_id_to_pw_aff.c \ isl_ilp.c \ isl_ilp_private.h \ @@ -255,6 +256,7 @@ pkginclude_HEADERS = \ include/isl/flow.h \ include/isl/id.h \ include/isl/id_to_ast_expr.h \ + include/isl/id_to_id.h \ include/isl/id_to_pw_aff.h \ include/isl/ilp.h \ include/isl/hash.h \ @@ -273,6 +275,7 @@ pkginclude_HEADERS = \ include/isl/polynomial.h \ include/isl/polynomial_type.h \ include/isl/printer.h \ + include/isl/printer_type.h \ include/isl/schedule.h \ include/isl/schedule_node.h \ include/isl/schedule_type.h \ diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in index ff6125f5eed..3ab5117ebe3 100644 --- a/polly/lib/External/isl/Makefile.in +++ b/polly/lib/External/isl/Makefile.in @@ -186,8 +186,8 @@ am__libisl_la_SOURCES_DIST = mp_get_memory_functions.c isl_int_gmp.h \ isl_dim_map.h isl_dim_map.c isl_equalities.c isl_equalities.h \ isl_factorization.c isl_factorization.h isl_farkas.c isl_ffs.c \ isl_flow.c isl_fold.c isl_hash.c isl_hash_private.h \ - isl_id_to_ast_expr.c isl_id_to_pw_aff.c isl_ilp.c \ - isl_ilp_private.h isl_input.c isl_int.h \ + isl_id_to_ast_expr.c isl_id_to_id.c isl_id_to_pw_aff.c \ + isl_ilp.c isl_ilp_private.h isl_input.c isl_int.h \ isl_local_space_private.h isl_local_space.c isl_lp.c \ isl_lp_private.h isl_map.c isl_map_list.c isl_map_simplify.c \ isl_map_subtract.c isl_map_private.h isl_map_to_basic_set.c \ @@ -233,19 +233,19 @@ am_libisl_la_OBJECTS = $(am__objects_4) $(am__objects_5) isl_aff.lo \ isl_convex_hull.lo isl_ctx.lo isl_deprecated.lo isl_dim_map.lo \ isl_equalities.lo isl_factorization.lo isl_farkas.lo \ isl_ffs.lo isl_flow.lo isl_fold.lo isl_hash.lo \ - isl_id_to_ast_expr.lo isl_id_to_pw_aff.lo isl_ilp.lo \ - isl_input.lo isl_local_space.lo isl_lp.lo isl_map.lo \ - isl_map_list.lo isl_map_simplify.lo isl_map_subtract.lo \ - isl_map_to_basic_set.lo isl_mat.lo isl_morph.lo isl_id.lo \ - isl_obj.lo isl_options.lo isl_output.lo isl_point.lo \ - isl_polynomial.lo isl_printer.lo print.lo isl_range.lo \ - isl_reordering.lo isl_sample.lo isl_scan.lo isl_schedule.lo \ - isl_schedule_band.lo isl_schedule_node.lo isl_schedule_read.lo \ - isl_schedule_tree.lo isl_scheduler.lo isl_set_list.lo \ - isl_sort.lo isl_space.lo isl_stream.lo isl_seq.lo isl_tab.lo \ - isl_tab_pip.lo isl_tarjan.lo isl_transitive_closure.lo \ - isl_union_map.lo isl_val.lo isl_vec.lo isl_version.lo \ - isl_vertices.lo + isl_id_to_ast_expr.lo isl_id_to_id.lo isl_id_to_pw_aff.lo \ + isl_ilp.lo isl_input.lo isl_local_space.lo isl_lp.lo \ + isl_map.lo isl_map_list.lo isl_map_simplify.lo \ + isl_map_subtract.lo isl_map_to_basic_set.lo isl_mat.lo \ + isl_morph.lo isl_id.lo isl_obj.lo isl_options.lo isl_output.lo \ + isl_point.lo isl_polynomial.lo isl_printer.lo print.lo \ + isl_range.lo isl_reordering.lo isl_sample.lo isl_scan.lo \ + isl_schedule.lo isl_schedule_band.lo isl_schedule_node.lo \ + isl_schedule_read.lo isl_schedule_tree.lo isl_scheduler.lo \ + isl_set_list.lo isl_sort.lo isl_space.lo isl_stream.lo \ + isl_seq.lo isl_tab.lo isl_tab_pip.lo isl_tarjan.lo \ + isl_transitive_closure.lo isl_union_map.lo isl_val.lo \ + isl_vec.lo isl_version.lo isl_vertices.lo libisl_la_OBJECTS = $(am_libisl_la_OBJECTS) AM_V_lt = $(am__v_lt_@AM_V@) am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@) @@ -384,14 +384,15 @@ am__pkginclude_HEADERS_DIST = include/isl/val_gmp.h include/isl/aff.h \ include/isl/ast_type.h include/isl/ast_build.h \ include/isl/band.h include/isl/constraint.h include/isl/ctx.h \ include/isl/flow.h include/isl/id.h \ - include/isl/id_to_ast_expr.h include/isl/id_to_pw_aff.h \ - include/isl/ilp.h include/isl/hash.h include/isl/hmap.h \ - include/isl/list.h include/isl/local_space.h include/isl/lp.h \ - include/isl/mat.h include/isl/map.h \ - include/isl/map_to_basic_set.h include/isl/map_type.h \ - include/isl/multi.h include/isl/obj.h include/isl/options.h \ - include/isl/point.h include/isl/polynomial.h \ - include/isl/polynomial_type.h include/isl/printer.h \ + include/isl/id_to_ast_expr.h include/isl/id_to_id.h \ + include/isl/id_to_pw_aff.h include/isl/ilp.h \ + include/isl/hash.h include/isl/hmap.h include/isl/list.h \ + include/isl/local_space.h include/isl/lp.h include/isl/mat.h \ + include/isl/map.h include/isl/map_to_basic_set.h \ + include/isl/map_type.h include/isl/multi.h include/isl/obj.h \ + include/isl/options.h include/isl/point.h \ + include/isl/polynomial.h include/isl/polynomial_type.h \ + include/isl/printer.h include/isl/printer_type.h \ include/isl/schedule.h include/isl/schedule_node.h \ include/isl/schedule_type.h include/isl/set.h \ include/isl/set_type.h include/isl/space.h \ @@ -863,6 +864,7 @@ libisl_la_SOURCES = \ isl_hash.c \ isl_hash_private.h \ isl_id_to_ast_expr.c \ + isl_id_to_id.c \ isl_id_to_pw_aff.c \ isl_ilp.c \ isl_ilp_private.h \ @@ -1007,6 +1009,7 @@ pkginclude_HEADERS = \ include/isl/flow.h \ include/isl/id.h \ include/isl/id_to_ast_expr.h \ + include/isl/id_to_id.h \ include/isl/id_to_pw_aff.h \ include/isl/ilp.h \ include/isl/hash.h \ @@ -1025,6 +1028,7 @@ pkginclude_HEADERS = \ include/isl/polynomial.h \ include/isl/polynomial_type.h \ include/isl/printer.h \ + include/isl/printer_type.h \ include/isl/schedule.h \ include/isl/schedule_node.h \ include/isl/schedule_type.h \ @@ -1326,6 +1330,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_hash.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_id.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_id_to_ast_expr.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_id_to_id.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_id_to_pw_aff.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_ilp.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_imath.Plo@am__quote@ diff --git a/polly/lib/External/isl/codegen.c b/polly/lib/External/isl/codegen.c index b2227aaf417..835b51d5b7b 100644 --- a/polly/lib/External/isl/codegen.c +++ b/polly/lib/External/isl/codegen.c @@ -208,9 +208,9 @@ int main(int argc, char **argv) options = cg_options_new_with_defaults(); assert(options); - argc = cg_options_parse(options, argc, argv, ISL_ARG_ALL); - ctx = isl_ctx_alloc_with_options(&options_args, options); + isl_options_set_ast_build_detect_min_max(ctx, 1); + argc = cg_options_parse(options, argc, argv, ISL_ARG_ALL); s = isl_stream_new_file(ctx, stdin); obj = isl_stream_read_obj(s); diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf Binary files differindex cbeba086f7a..7dac86b2b3c 100644 --- a/polly/lib/External/isl/doc/manual.pdf +++ b/polly/lib/External/isl/doc/manual.pdf diff --git a/polly/lib/External/isl/doc/user.pod b/polly/lib/External/isl/doc/user.pod index d006f325d7a..6bfc318f1bb 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -869,7 +869,7 @@ using the following functions. __isl_keep const char *name, void *user); __isl_give isl_id *isl_id_set_free_user( __isl_take isl_id *id, - __isl_give void (*free_user)(void *user)); + void (*free_user)(void *user)); __isl_give isl_id *isl_id_copy(isl_id *id); __isl_null isl_id *isl_id_free(__isl_take isl_id *id); @@ -3627,6 +3627,25 @@ the file. When called on a string printer, the buffer is cleared. __isl_give isl_printer *isl_printer_flush( __isl_take isl_printer *p); +The following functions allow the user to attach +notes to a printer in order to keep track of additional state. + + #include <isl/printer.h> + isl_bool isl_printer_has_note(__isl_keep isl_printer *p, + __isl_keep isl_id *id); + __isl_give isl_id *isl_printer_get_note( + __isl_keep isl_printer *p, __isl_take isl_id *id); + __isl_give isl_printer *isl_printer_set_note( + __isl_take isl_printer *p, + __isl_take isl_id *id, __isl_take isl_id *note); + +C<isl_printer_set_note> associates the given note to the given +identifier in the printer. +C<isl_printer_get_note> retrieves a note associated to an +identifier, while +C<isl_printer_has_note> checks if there is such a note. +C<isl_printer_get_note> fails if the requested note does not exist. + Alternatively, a string representation can be obtained directly using the following functions, which always print in isl format. @@ -3700,8 +3719,12 @@ is already known to be empty. =item * Universality + isl_bool isl_basic_set_plain_is_universe( + __isl_keep isl_basic_set *bset); isl_bool isl_basic_set_is_universe( __isl_keep isl_basic_set *bset); + isl_bool isl_basic_map_plain_is_universe( + __isl_keep isl_basic_map *bmap); isl_bool isl_basic_map_is_universe( __isl_keep isl_basic_map *bmap); isl_bool isl_set_plain_is_universe( @@ -3946,6 +3969,8 @@ the input is itself a wrapped relation. #include <isl/aff.h> isl_bool isl_aff_is_cst(__isl_keep isl_aff *aff); isl_bool isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff); + isl_bool isl_multi_pw_aff_is_cst( + __isl_keep isl_multi_pw_aff *mpa); Check whether the given expression is a constant. @@ -5732,6 +5757,8 @@ that map to the specified range. __isl_give isl_set *isl_set_union( __isl_take isl_set *set1, __isl_take isl_set *set2); + __isl_give isl_set *isl_set_list_union( + __isl_take isl_set_list *list); #include <isl/map.h> __isl_give isl_map *isl_basic_map_union( @@ -5753,6 +5780,9 @@ that map to the specified range. __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2); +The list passed to C<isl_set_list_union> needs to have +at least one element and all elements need to live in the same space. + =item * Set difference #include <isl/set.h> @@ -7253,7 +7283,8 @@ Lists can be printed using Associative arrays map isl objects of a specific type to isl objects of some (other) specific type. They are defined for several pairs of types, including (C<isl_map>, C<isl_basic_set>), -(C<isl_id>, C<isl_ast_expr>) and. +(C<isl_id>, C<isl_ast_expr>), +(C<isl_id>, C<isl_id>) and (C<isl_id>, C<isl_pw_aff>). Here, we take associative arrays that map C<isl_id>s to C<isl_ast_expr>s as an example. @@ -9141,6 +9172,21 @@ C<isl_ast_node_mark_get_node> returns the child node that is being marked. __isl_give isl_ast_expr *isl_ast_node_user_get_expr( __isl_keep isl_ast_node *node); +All descendants of a specific node in the AST (including the node itself) +can be visited +in depth-first pre-order using the following function. + + #include <isl/ast.h> + isl_stat isl_ast_node_foreach_descendant_top_down( + __isl_keep isl_ast_node *node, + isl_bool (*fn)(__isl_keep isl_ast_node *node, + void *user), void *user); + +The callback function should return C<isl_bool_true> if the children +of the given node should be visited and C<isl_bool_false> if they should not. +It should return C<isl_bool_error> in case of failure, in which case +the entire traversal is aborted. + Each of the returned C<isl_ast_expr>s can in turn be inspected using the following functions. @@ -9164,6 +9210,10 @@ Each type of expression has its own additional properties. int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr); __isl_give isl_ast_expr *isl_ast_expr_get_op_arg( __isl_keep isl_ast_expr *expr, int pos); + isl_stat isl_ast_expr_foreach_ast_op_type( + __isl_keep isl_ast_expr *expr, + isl_stat (*fn)(enum isl_ast_op_type type, + void *user), void *user); isl_stat isl_ast_node_foreach_ast_op_type( __isl_keep isl_ast_node *node, isl_stat (*fn)(enum isl_ast_op_type type, @@ -9173,7 +9223,9 @@ C<isl_ast_expr_get_op_type> returns the type of the operation performed. C<isl_ast_expr_get_op_n_arg> returns the number of arguments. C<isl_ast_expr_get_op_arg> returns the specified argument. -C<isl_ast_node_foreach_ast_op_type> calls C<fn> for each distinct +C<isl_ast_expr_foreach_ast_op_type> calls C<fn> for each distinct +C<isl_ast_op_type> that appears in C<expr>. +C<isl_ast_node_foreach_ast_op_type> does the same for each distinct C<isl_ast_op_type> that appears in C<node>. The operation type is one of the following. @@ -9493,9 +9545,19 @@ Basic printing can be performed using the following functions. More advanced printing can be performed using the following functions. #include <isl/ast.h> + __isl_give isl_printer *isl_ast_op_type_set_print_name( + __isl_take isl_printer *p, + enum isl_ast_op_type type, + __isl_keep const char *name); + isl_stat isl_options_set_ast_print_macro_once( + isl_ctx *ctx, int val); + int isl_options_get_ast_print_macro_once(isl_ctx *ctx); __isl_give isl_printer *isl_ast_op_type_print_macro( enum isl_ast_op_type type, __isl_take isl_printer *p); + __isl_give isl_printer *isl_ast_expr_print_macros( + __isl_keep isl_ast_expr *expr, + __isl_take isl_printer *p); __isl_give isl_printer *isl_ast_node_print_macros( __isl_keep isl_ast_node *node, __isl_take isl_printer *p); @@ -9515,14 +9577,21 @@ More advanced printing can be performed using the following functions. While printing an C<isl_ast_node> in C<ISL_FORMAT_C>, C<isl> may print out an AST that makes use of macros such as C<floord>, C<min> and C<max>. +The names of these macros may be modified by a call +to C<isl_ast_op_type_set_print_name>. The user-specified +names are associated to the printer object. C<isl_ast_op_type_print_macro> prints out the macro corresponding to a specific C<isl_ast_op_type>. -C<isl_ast_node_print_macros> scans the C<isl_ast_node> -for expressions where these macros would be used and prints +If the print-macro-once option is set, then a given macro definition +is only printed once to any given printer object. +C<isl_ast_expr_print_macros> scans the C<isl_ast_expr> +for subexpressions where these macros would be used and prints out the required macro definitions. -Essentially, C<isl_ast_node_print_macros> calls -C<isl_ast_node_foreach_ast_op_type> with C<isl_ast_op_type_print_macro> +Essentially, C<isl_ast_expr_print_macros> calls +C<isl_ast_expr_foreach_ast_op_type> with C<isl_ast_op_type_print_macro> as function argument. +C<isl_ast_node_print_macros> does the same +for expressions in its C<isl_ast_node> argument. C<isl_ast_node_print>, C<isl_ast_node_for_print> and C<isl_ast_node_if_print> print an C<isl_ast_node> in C<ISL_FORMAT_C>, but allow for some extra control @@ -9597,6 +9666,10 @@ A block will always be printed by setting the following option. isl_stat isl_options_set_ast_build_prefer_pdiv(isl_ctx *ctx, int val); int isl_options_get_ast_build_prefer_pdiv(isl_ctx *ctx); + isl_stat isl_options_set_ast_build_detect_min_max( + isl_ctx *ctx, int val); + int isl_options_get_ast_build_detect_min_max( + isl_ctx *ctx); isl_stat isl_options_set_ast_build_exploit_nested_bounds( isl_ctx *ctx, int val); int isl_options_get_ast_build_exploit_nested_bounds( @@ -9645,10 +9718,16 @@ If this option is turned off, then the AST generation will produce ASTs that may only contain C<isl_ast_op_fdiv_q> operators, but no C<isl_ast_op_pdiv_q> or C<isl_ast_op_pdiv_r> operators. -If this options is turned on, then C<isl> will try to convert +If this option is turned on, then C<isl> will try to convert some of the C<isl_ast_op_fdiv_q> operators to (expressions containing) C<isl_ast_op_pdiv_q> or C<isl_ast_op_pdiv_r> operators. +=item * ast_build_detect_min_max + +If this option is turned on, then C<isl> will try and detect +min or max-expressions when building AST expressions from +piecewise affine expressions. + =item * ast_build_exploit_nested_bounds Simplify conditions based on bounds of nested for loops. diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h index 8c54c9cdcf4..a2cac451a52 100644 --- a/polly/lib/External/isl/include/isl/aff.h +++ b/polly/lib/External/isl/include/isl/aff.h @@ -711,6 +711,7 @@ __isl_give isl_multi_pw_aff *isl_multi_pw_aff_gist( __isl_give isl_multi_pw_aff *isl_multi_pw_aff_gist_params( __isl_take isl_multi_pw_aff *mpa, __isl_take isl_set *set); +isl_bool isl_multi_pw_aff_is_cst(__isl_keep isl_multi_pw_aff *mpa); isl_bool isl_multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff *mpa1, __isl_keep isl_multi_pw_aff *mpa2); diff --git a/polly/lib/External/isl/include/isl/ast.h b/polly/lib/External/isl/include/isl/ast.h index e0917970935..8eca398a83c 100644 --- a/polly/lib/External/isl/include/isl/ast.h +++ b/polly/lib/External/isl/include/isl/ast.h @@ -125,6 +125,10 @@ __isl_give isl_ast_node *isl_ast_node_mark_get_node( __isl_give isl_ast_expr *isl_ast_node_user_get_expr( __isl_keep isl_ast_node *node); +isl_stat isl_ast_node_foreach_descendant_top_down( + __isl_keep isl_ast_node *node, + isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user), void *user); + __isl_give isl_printer *isl_printer_print_ast_node(__isl_take isl_printer *p, __isl_keep isl_ast_node *node); void isl_ast_node_dump(__isl_keep isl_ast_node *node); @@ -150,10 +154,20 @@ __isl_give isl_ast_print_options *isl_ast_print_options_set_print_for( __isl_keep isl_ast_node *node, void *user), void *user); +isl_stat isl_options_set_ast_print_macro_once(isl_ctx *ctx, int val); +int isl_options_get_ast_print_macro_once(isl_ctx *ctx); + +isl_stat isl_ast_expr_foreach_ast_op_type(__isl_keep isl_ast_expr *expr, + isl_stat (*fn)(enum isl_ast_op_type type, void *user), void *user); isl_stat isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node, isl_stat (*fn)(enum isl_ast_op_type type, void *user), void *user); +__isl_give isl_printer *isl_ast_op_type_set_print_name( + __isl_take isl_printer *p, enum isl_ast_op_type type, + __isl_keep const char *name); __isl_give isl_printer *isl_ast_op_type_print_macro( enum isl_ast_op_type type, __isl_take isl_printer *p); +__isl_give isl_printer *isl_ast_expr_print_macros( + __isl_keep isl_ast_expr *expr, __isl_take isl_printer *p); __isl_give isl_printer *isl_ast_node_print_macros( __isl_keep isl_ast_node *node, __isl_take isl_printer *p); __isl_give isl_printer *isl_ast_node_print(__isl_keep isl_ast_node *node, diff --git a/polly/lib/External/isl/include/isl/ast_build.h b/polly/lib/External/isl/include/isl/ast_build.h index 0971a049151..fa51873b489 100644 --- a/polly/lib/External/isl/include/isl/ast_build.h +++ b/polly/lib/External/isl/include/isl/ast_build.h @@ -20,6 +20,9 @@ int isl_options_get_ast_build_atomic_upper_bound(isl_ctx *ctx); isl_stat isl_options_set_ast_build_prefer_pdiv(isl_ctx *ctx, int val); int isl_options_get_ast_build_prefer_pdiv(isl_ctx *ctx); +isl_stat isl_options_set_ast_build_detect_min_max(isl_ctx *ctx, int val); +int isl_options_get_ast_build_detect_min_max(isl_ctx *ctx); + isl_stat isl_options_set_ast_build_exploit_nested_bounds(isl_ctx *ctx, int val); int isl_options_get_ast_build_exploit_nested_bounds(isl_ctx *ctx); diff --git a/polly/lib/External/isl/include/isl/id.h b/polly/lib/External/isl/include/isl/id.h index 093dd44c3e0..fa018463920 100644 --- a/polly/lib/External/isl/include/isl/id.h +++ b/polly/lib/External/isl/include/isl/id.h @@ -3,7 +3,7 @@ #include <isl/ctx.h> #include <isl/list.h> -#include <isl/printer.h> +#include <isl/printer_type.h> #include <isl/stdint.h> #if defined(__cplusplus) @@ -27,7 +27,7 @@ void *isl_id_get_user(__isl_keep isl_id *id); __isl_keep const char *isl_id_get_name(__isl_keep isl_id *id); __isl_give isl_id *isl_id_set_free_user(__isl_take isl_id *id, - __isl_give void (*free_user)(void *user)); + void (*free_user)(void *user)); __isl_give isl_printer *isl_printer_print_id(__isl_take isl_printer *p, __isl_keep isl_id *id); diff --git a/polly/lib/External/isl/include/isl/id_to_id.h b/polly/lib/External/isl/include/isl/id_to_id.h new file mode 100644 index 00000000000..8e763de6ffd --- /dev/null +++ b/polly/lib/External/isl/include/isl/id_to_id.h @@ -0,0 +1,12 @@ +#ifndef ISL_ID_TO_ID_H +#define ISL_ID_TO_ID_H + +#include <isl/id.h> + +#define ISL_KEY_BASE id +#define ISL_VAL_BASE id +#include <isl/hmap.h> +#undef ISL_KEY_BASE +#undef ISL_VAL_BASE + +#endif diff --git a/polly/lib/External/isl/include/isl/list.h b/polly/lib/External/isl/include/isl/list.h index 616d8dc39ce..948e565427b 100644 --- a/polly/lib/External/isl/include/isl/list.h +++ b/polly/lib/External/isl/include/isl/list.h @@ -11,7 +11,7 @@ #define ISL_LIST_H #include <isl/ctx.h> -#include <isl/printer.h> +#include <isl/printer_type.h> #if defined(__cplusplus) extern "C" { diff --git a/polly/lib/External/isl/include/isl/map.h b/polly/lib/External/isl/include/isl/map.h index 619a9ce133f..edcb021aa44 100644 --- a/polly/lib/External/isl/include/isl/map.h +++ b/polly/lib/External/isl/include/isl/map.h @@ -279,6 +279,7 @@ __isl_give isl_val *isl_basic_map_plain_get_val_if_fixed( enum isl_dim_type type, unsigned pos); int isl_basic_map_image_is_bounded(__isl_keep isl_basic_map *bmap); +isl_bool isl_basic_map_plain_is_universe(__isl_keep isl_basic_map *bmap); isl_bool isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap); isl_bool isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap); __isl_export diff --git a/polly/lib/External/isl/include/isl/printer.h b/polly/lib/External/isl/include/isl/printer.h index f5b2f43ca5e..dd50e917610 100644 --- a/polly/lib/External/isl/include/isl/printer.h +++ b/polly/lib/External/isl/include/isl/printer.h @@ -3,14 +3,13 @@ #include <stdio.h> #include <isl/ctx.h> +#include <isl/printer_type.h> +#include <isl/id.h> #if defined(__cplusplus) extern "C" { #endif -struct isl_printer; -typedef struct isl_printer isl_printer; - __isl_give isl_printer *isl_printer_to_file(isl_ctx *ctx, FILE *file); __isl_give isl_printer *isl_printer_to_str(isl_ctx *ctx); __isl_null isl_printer *isl_printer_free(__isl_take isl_printer *printer); @@ -51,6 +50,13 @@ __isl_give isl_printer *isl_printer_set_suffix(__isl_take isl_printer *p, __isl_give isl_printer *isl_printer_set_isl_int_width(__isl_take isl_printer *p, int width); +isl_bool isl_printer_has_note(__isl_keep isl_printer *p, + __isl_keep isl_id *id); +__isl_give isl_id *isl_printer_get_note(__isl_keep isl_printer *p, + __isl_take isl_id *id); +__isl_give isl_printer *isl_printer_set_note(__isl_take isl_printer *p, + __isl_take isl_id *id, __isl_take isl_id *note); + __isl_give isl_printer *isl_printer_start_line(__isl_take isl_printer *p); __isl_give isl_printer *isl_printer_end_line(__isl_take isl_printer *p); __isl_give isl_printer *isl_printer_print_double(__isl_take isl_printer *p, diff --git a/polly/lib/External/isl/include/isl/printer_type.h b/polly/lib/External/isl/include/isl/printer_type.h new file mode 100644 index 00000000000..985f8ca7fa4 --- /dev/null +++ b/polly/lib/External/isl/include/isl/printer_type.h @@ -0,0 +1,15 @@ +#ifndef ISL_PRINTER_TYPE_H +#define ISL_PRINTER_TYPE_H + +#if defined(__cplusplus) +extern "C" { +#endif + +struct isl_printer; +typedef struct isl_printer isl_printer; + +#if defined(__cplusplus) +} +#endif + +#endif diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h index e855de13bc3..6f9d2c7fdf7 100644 --- a/polly/lib/External/isl/include/isl/set.h +++ b/polly/lib/External/isl/include/isl/set.h @@ -130,6 +130,8 @@ __isl_give isl_basic_set *isl_basic_set_list_intersect( __isl_give isl_basic_set *isl_basic_set_list_product( __isl_take struct isl_basic_set_list *list); +__isl_give isl_set *isl_set_list_union(__isl_take isl_set_list *list); + __isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx, FILE *input); __isl_constructor @@ -218,6 +220,7 @@ __isl_give isl_set *isl_set_from_params(__isl_take isl_set *set); int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset, enum isl_dim_type type, unsigned pos, unsigned n, int *signs); +isl_bool isl_basic_set_plain_is_universe(__isl_keep isl_basic_set *bset); isl_bool isl_basic_set_is_universe(__isl_keep isl_basic_set *bset); isl_bool isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset); __isl_export diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c index b072b956e6a..a060e3d3e75 100644 --- a/polly/lib/External/isl/isl_aff.c +++ b/polly/lib/External/isl/isl_aff.c @@ -3326,6 +3326,24 @@ isl_bool isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff) return isl_bool_true; } +/* Are all elements of "mpa" piecewise constants? + */ +isl_bool isl_multi_pw_aff_is_cst(__isl_keep isl_multi_pw_aff *mpa) +{ + int i; + + if (!mpa) + return isl_bool_error; + + for (i = 0; i < mpa->n; ++i) { + isl_bool is_cst = isl_pw_aff_is_cst(mpa->p[i]); + if (is_cst < 0 || !is_cst) + return is_cst; + } + + return isl_bool_true; +} + /* Return the product of "aff1" and "aff2". * * If either of the two is NaN, then the result is NaN. diff --git a/polly/lib/External/isl/isl_ast.c b/polly/lib/External/isl/isl_ast.c index 4aff82e71cb..be802a3af32 100644 --- a/polly/lib/External/isl/isl_ast.c +++ b/polly/lib/External/isl/isl_ast.c @@ -7,6 +7,8 @@ * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ +#include <string.h> + #include <isl_ast_private.h> #undef BASE @@ -1319,6 +1321,84 @@ error: return isl_ast_node_free(node); } +/* Traverse the elements of "list" and all their descendants + * in depth first preorder. + * + * Return isl_stat_ok on success and isl_stat_error on failure. + */ +static isl_stat nodelist_foreach(__isl_keep isl_ast_node_list *list, + isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user), void *user) +{ + int i; + + if (!list) + return isl_stat_error; + + for (i = 0; i < list->n; ++i) { + isl_stat ok; + isl_ast_node *node = list->p[i]; + + ok = isl_ast_node_foreach_descendant_top_down(node, fn, user); + if (ok < 0) + return isl_stat_error; + } + + return isl_stat_ok; +} + +/* Traverse the descendants of "node" (including the node itself) + * in depth first preorder. + * + * If "fn" returns isl_bool_error on any of the nodes, then the traversal + * is aborted. + * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted + * at that node is skipped. + * + * Return isl_stat_ok on success and isl_stat_error on failure. + */ +isl_stat isl_ast_node_foreach_descendant_top_down( + __isl_keep isl_ast_node *node, + isl_bool (*fn)(__isl_keep isl_ast_node *node, void *user), void *user) +{ + isl_bool more; + isl_stat ok; + + if (!node) + return isl_stat_error; + + more = fn(node, user); + if (more < 0) + return isl_stat_error; + if (!more) + return isl_stat_ok; + + switch (node->type) { + case isl_ast_node_for: + node = node->u.f.body; + return isl_ast_node_foreach_descendant_top_down(node, fn, user); + case isl_ast_node_if: + ok = isl_ast_node_foreach_descendant_top_down(node->u.i.then, + fn, user); + if (ok < 0) + return isl_stat_error; + if (!node->u.i.else_node) + return isl_stat_ok; + node = node->u.i.else_node; + return isl_ast_node_foreach_descendant_top_down(node, fn, user); + case isl_ast_node_block: + return nodelist_foreach(node->u.b.children, fn, user); + case isl_ast_node_mark: + node = node->u.m.node; + return isl_ast_node_foreach_descendant_top_down(node, fn, user); + case isl_ast_node_user: + break; + case isl_ast_node_error: + return isl_stat_error; + } + + return isl_stat_ok; +} + /* Textual C representation of the various operators. */ static char *op_str[] = { @@ -1332,6 +1412,7 @@ static char *op_str[] = { [isl_ast_op_add] = "+", [isl_ast_op_sub] = "-", [isl_ast_op_mul] = "*", + [isl_ast_op_fdiv_q] = "floord", [isl_ast_op_pdiv_q] = "/", [isl_ast_op_pdiv_r] = "%", [isl_ast_op_zdiv_r] = "%", @@ -1489,6 +1570,157 @@ static __isl_give isl_printer *print_sub_expr(__isl_take isl_printer *p, return p; } +#define isl_ast_op_last isl_ast_op_address_of + +/* Data structure that holds the user-specified textual + * representations for the operators. + * The entries are either NULL or copies of strings. + * A NULL entry means that the default name should be used. + */ +struct isl_ast_op_names { + char *op_str[isl_ast_op_last + 1]; +}; + +/* Create an empty struct isl_ast_op_names. + */ +static void *create_names(isl_ctx *ctx) +{ + return isl_calloc_type(ctx, struct isl_ast_op_names); +} + +/* Free a struct isl_ast_op_names along with all memory + * owned by the struct. + */ +static void free_names(void *user) +{ + int i; + struct isl_ast_op_names *names = user; + + if (!user) + return; + + for (i = 0; i <= isl_ast_op_last; ++i) + free(names->op_str[i]); + free(user); +} + +/* Create an identifier that is used to store + * an isl_ast_op_names note. + */ +static __isl_give isl_id *names_id(isl_ctx *ctx) +{ + return isl_id_alloc(ctx, "isl_ast_op_type_names", NULL); +} + +/* Ensure that "p" has a note identified by "id". + * If there is no such note yet, then it is created by "note_create" and + * scheduled do be freed by "note_free". + */ +static __isl_give isl_printer *alloc_note(__isl_take isl_printer *p, + __isl_keep isl_id *id, void *(*note_create)(isl_ctx *), + void (*note_free)(void *)) +{ + isl_ctx *ctx; + isl_id *note_id; + isl_bool has_note; + void *note; + + has_note = isl_printer_has_note(p, id); + if (has_note < 0) + return isl_printer_free(p); + if (has_note) + return p; + + ctx = isl_printer_get_ctx(p); + note = note_create(ctx); + if (!note) + return isl_printer_free(p); + note_id = isl_id_alloc(ctx, NULL, note); + if (!note_id) + note_free(note); + else + note_id = isl_id_set_free_user(note_id, note_free); + + p = isl_printer_set_note(p, isl_id_copy(id), note_id); + + return p; +} + +/* Ensure that "p" has an isl_ast_op_names note identified by "id". + */ +static __isl_give isl_printer *alloc_names(__isl_take isl_printer *p, + __isl_keep isl_id *id) +{ + return alloc_note(p, id, &create_names, &free_names); +} + +/* Retrieve the note identified by "id" from "p". + * The note is assumed to exist. + */ +static void *get_note(__isl_keep isl_printer *p, __isl_keep isl_id *id) +{ + void *note; + + id = isl_printer_get_note(p, isl_id_copy(id)); + note = isl_id_get_user(id); + isl_id_free(id); + + return note; +} + +/* Use "name" to print operations of type "type" to "p". + * + * Store the name in an isl_ast_op_names note attached to "p", such that + * it can be retrieved by get_op_str. + */ +__isl_give isl_printer *isl_ast_op_type_set_print_name( + __isl_take isl_printer *p, enum isl_ast_op_type type, + __isl_keep const char *name) +{ + isl_id *id; + struct isl_ast_op_names *names; + + if (!p) + return NULL; + if (type > isl_ast_op_last) + isl_die(isl_printer_get_ctx(p), isl_error_invalid, + "invalid type", return isl_printer_free(p)); + + id = names_id(isl_printer_get_ctx(p)); + p = alloc_names(p, id); + names = get_note(p, id); + isl_id_free(id); + if (!names) + return isl_printer_free(p); + free(names->op_str[type]); + names->op_str[type] = strdup(name); + + return p; +} + +/* Return the textual representation of "type". + * + * If there is a user-specified name in an isl_ast_op_names note + * associated to "p", then return that. + * Otherwise, return the default name in op_str. + */ +static const char *get_op_str(__isl_keep isl_printer *p, + enum isl_ast_op_type type) +{ + isl_id *id; + isl_bool has_names; + struct isl_ast_op_names *names = NULL; + + id = names_id(isl_printer_get_ctx(p)); + has_names = isl_printer_has_note(p, id); + if (has_names >= 0 && has_names) + names = get_note(p, id); + isl_id_free(id); + if (names && names->op_str[type]) + return names->op_str[type]; + return op_str[type]; +} + /* Print a min or max reduction "expr". */ static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p, @@ -1497,7 +1729,7 @@ static __isl_give isl_printer *print_min_max(__isl_take isl_printer *p, int i = 0; for (i = 1; i < expr->u.op.n_arg; ++i) { - p = isl_printer_print_str(p, op_str[expr->u.op.op]); + p = isl_printer_print_str(p, get_op_str(p, expr->u.op.op)); p = isl_printer_print_str(p, "("); } p = isl_printer_print_ast_expr(p, expr->u.op.args[0]); @@ -1574,13 +1806,16 @@ __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p, break; } if (expr->u.op.n_arg == 1) { - p = isl_printer_print_str(p, op_str[expr->u.op.op]); + p = isl_printer_print_str(p, + get_op_str(p, expr->u.op.op)); p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 0); break; } if (expr->u.op.op == isl_ast_op_fdiv_q) { - p = isl_printer_print_str(p, "floord("); + const char *name = get_op_str(p, isl_ast_op_fdiv_q); + p = isl_printer_print_str(p, name); + p = isl_printer_print_str(p, "("); p = isl_printer_print_ast_expr(p, expr->u.op.args[0]); p = isl_printer_print_str(p, ", "); p = isl_printer_print_ast_expr(p, expr->u.op.args[1]); @@ -1608,7 +1843,7 @@ __isl_give isl_printer *isl_printer_print_ast_expr(__isl_take isl_printer *p, p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[0], 1); if (expr->u.op.op != isl_ast_op_member) p = isl_printer_print_str(p, " "); - p = isl_printer_print_str(p, op_str[expr->u.op.op]); + p = isl_printer_print_str(p, get_op_str(p, expr->u.op.op)); if (expr->u.op.op != isl_ast_op_member) p = isl_printer_print_str(p, " "); p = print_sub_expr(p, expr->u.op.op, expr->u.op.args[1], 0); @@ -2136,28 +2371,124 @@ static int ast_node_list_required_macros(__isl_keep isl_ast_node_list *list, return macros; } +/* Data structure for keeping track of whether a macro definition + * for a given type has already been printed. + * The value is zero if no definition has been printed and non-zero otherwise. + */ +struct isl_ast_op_printed { + char printed[isl_ast_op_last + 1]; +}; + +/* Create an empty struct isl_ast_op_printed. + */ +static void *create_printed(isl_ctx *ctx) +{ + return isl_calloc_type(ctx, struct isl_ast_op_printed); +} + +/* Free a struct isl_ast_op_printed. + */ +static void free_printed(void *user) +{ + free(user); +} + +/* Ensure that "p" has an isl_ast_op_printed note identified by "id". + */ +static __isl_give isl_printer *alloc_printed(__isl_take isl_printer *p, + __isl_keep isl_id *id) +{ + return alloc_note(p, id, &create_printed, &free_printed); +} + +/* Create an identifier that is used to store + * an isl_ast_op_printed note. + */ +static __isl_give isl_id *printed_id(isl_ctx *ctx) +{ + return isl_id_alloc(ctx, "isl_ast_op_type_printed", NULL); +} + +/* Did the user specify that a macro definition should only be + * printed once and has a macro definition for "type" already + * been printed to "p"? + * If definitions should only be printed once, but a definition + * for "p" has not yet been printed, then mark it as having been + * printed so that it will not printed again. + * The actual printing is taken care of by the caller. + */ +static isl_bool already_printed_once(__isl_keep isl_printer *p, + enum isl_ast_op_type type) +{ + isl_ctx *ctx; + isl_id *id; + struct isl_ast_op_printed *printed; + + if (!p) + return isl_bool_error; + + ctx = isl_printer_get_ctx(p); + if (!isl_options_get_ast_print_macro_once(ctx)) + return isl_bool_false; + + if (type > isl_ast_op_last) + isl_die(isl_printer_get_ctx(p), isl_error_invalid, + "invalid type", return isl_bool_error); + + id = printed_id(isl_printer_get_ctx(p)); + p = alloc_printed(p, id); + printed = get_note(p, id); + isl_id_free(id); + if (!printed) + return isl_bool_error; + + if (printed->printed[type]) + return isl_bool_true; + + printed->printed[type] = 1; + return isl_bool_false; +} + /* Print a macro definition for the operator "type". + * + * If the user has specified that a macro definition should + * only be printed once to any given printer and if the macro definition + * has already been printed to "p", then do not print the definition. */ __isl_give isl_printer *isl_ast_op_type_print_macro( enum isl_ast_op_type type, __isl_take isl_printer *p) { + isl_bool skip; + + skip = already_printed_once(p, type); + if (skip < 0) + return isl_printer_free(p); + if (skip) + return p; + switch (type) { case isl_ast_op_min: p = isl_printer_start_line(p); + p = isl_printer_print_str(p, "#define "); + p = isl_printer_print_str(p, get_op_str(p, type)); p = isl_printer_print_str(p, - "#define min(x,y) ((x) < (y) ? (x) : (y))"); + "(x,y) ((x) < (y) ? (x) : (y))"); p = isl_printer_end_line(p); break; case isl_ast_op_max: p = isl_printer_start_line(p); + p = isl_printer_print_str(p, "#define "); + p = isl_printer_print_str(p, get_op_str(p, type)); p = isl_printer_print_str(p, - "#define max(x,y) ((x) > (y) ? (x) : (y))"); + "(x,y) ((x) > (y) ? (x) : (y))"); p = isl_printer_end_line(p); break; case isl_ast_op_fdiv_q: p = isl_printer_start_line(p); + p = isl_printer_print_str(p, "#define "); + p = isl_printer_print_str(p, get_op_str(p, type)); p = isl_printer_print_str(p, - "#define floord(n,d) " + "(n,d) " "(((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))"); p = isl_printer_end_line(p); break; @@ -2168,6 +2499,37 @@ __isl_give isl_printer *isl_ast_op_type_print_macro( return p; } +/* Call "fn" for each type of operation represented in the "macros" + * bit vector. + */ +static isl_stat foreach_ast_op_type(int macros, + isl_stat (*fn)(enum isl_ast_op_type type, void *user), void *user) +{ + if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0) + return isl_stat_error; + if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0) + return isl_stat_error; + if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0) + return isl_stat_error; + + return isl_stat_ok; +} + +/* Call "fn" for each type of operation that appears in "expr" + * and that requires a macro definition. + */ +isl_stat isl_ast_expr_foreach_ast_op_type(__isl_keep isl_ast_expr *expr, + isl_stat (*fn)(enum isl_ast_op_type type, void *user), void *user) +{ + int macros; + + if (!expr) + return isl_stat_error; + + macros = ast_expr_required_macros(expr, 0); + return foreach_ast_op_type(macros, fn, user); +} + /* Call "fn" for each type of operation that appears in "node" * and that requires a macro definition. */ @@ -2180,15 +2542,7 @@ isl_stat isl_ast_node_foreach_ast_op_type(__isl_keep isl_ast_node *node, return isl_stat_error; macros = ast_node_required_macros(node, 0); - - if (macros & ISL_AST_MACRO_MIN && fn(isl_ast_op_min, user) < 0) - return isl_stat_error; - if (macros & ISL_AST_MACRO_MAX && fn(isl_ast_op_max, user) < 0) - return isl_stat_error; - if (macros & ISL_AST_MACRO_FLOORD && fn(isl_ast_op_fdiv_q, user) < 0) - return isl_stat_error; - - return isl_stat_ok; + return foreach_ast_op_type(macros, fn, user); } static isl_stat ast_op_type_print_macro(enum isl_ast_op_type type, void *user) @@ -2201,7 +2555,19 @@ static isl_stat ast_op_type_print_macro(enum isl_ast_op_type type, void *user) } /* Print macro definitions for all the macros used in the result - * of printing "node. + * of printing "expr". + */ +__isl_give isl_printer *isl_ast_expr_print_macros( + __isl_keep isl_ast_expr *expr, __isl_take isl_printer *p) +{ + if (isl_ast_expr_foreach_ast_op_type(expr, + &ast_op_type_print_macro, &p) < 0) + return isl_printer_free(p); + return p; +} + +/* Print macro definitions for all the macros used in the result + * of printing "node". */ __isl_give isl_printer *isl_ast_node_print_macros( __isl_keep isl_ast_node *node, __isl_take isl_printer *p) diff --git a/polly/lib/External/isl/isl_ast_build_expr.c b/polly/lib/External/isl/isl_ast_build_expr.c index f0dd22df2dc..6445074be4a 100644 --- a/polly/lib/External/isl/isl_ast_build_expr.c +++ b/polly/lib/External/isl/isl_ast_build_expr.c @@ -1577,67 +1577,341 @@ __isl_give isl_ast_expr *isl_ast_build_expr_from_set( return isl_ast_build_expr_from_set_internal(build, set); } +/* State of data about previous pieces in + * isl_ast_build_expr_from_pw_aff_internal. + * + * isl_state_none: no data about previous pieces + * isl_state_single: data about a single previous piece + * isl_state_min: data represents minimum of several pieces + * isl_state_max: data represents maximum of several pieces + */ +enum isl_from_pw_aff_state { + isl_state_none, + isl_state_single, + isl_state_min, + isl_state_max +}; + +/* Internal data structure for isl_ast_build_expr_from_pw_aff_internal. + * + * "build" specifies the domain against which the result is simplified. + * "next" points to where the next part of the constructed expression + * should be stored. + * "dom" is the domain of the entire isl_pw_aff. + * + * If "state" is isl_state_none, then "set_list" and "aff_list" are not used. + * If "state" is isl_state_single, then "set_list" and "aff_list" contain the + * single previous piece. + * If "state" is isl_state_min, then "set_list" and "aff_list" contain + * a sequence of several previous pieces that are equal to the minimum + * of the entries in "aff_list" over the union of "set_list" + * If "state" is isl_state_max, then "set_list" and "aff_list" contain + * a sequence of several previous pieces that are equal to the maximum + * of the entries in "aff_list" over the union of "set_list" + */ struct isl_from_pw_aff_data { isl_ast_build *build; - int n; isl_ast_expr **next; isl_set *dom; + + enum isl_from_pw_aff_state state; + isl_set_list *set_list; + isl_aff_list *aff_list; }; -/* This function is called during the construction of an isl_ast_expr - * that evaluates an isl_pw_aff. - * Adjust data->next to take into account this piece. - * - * data->n is the number of pairs of set and aff to go. - * data->dom is the domain of the entire isl_pw_aff. +/* Store "set" and "aff" in "data" as a single piece. + */ +static void set_single(struct isl_from_pw_aff_data *data, + __isl_take isl_set *set, __isl_take isl_aff *aff) +{ + data->state = isl_state_single; + data->set_list = isl_set_list_from_set(set); + data->aff_list = isl_aff_list_from_aff(aff); +} + +/* Extend "data" with "set" and "aff" as a minimum expression. + */ +static isl_stat extend_min(struct isl_from_pw_aff_data *data, + __isl_take isl_set *set, __isl_take isl_aff *aff) +{ + data->state = isl_state_min; + data->set_list = isl_set_list_add(data->set_list, set); + data->aff_list = isl_aff_list_add(data->aff_list, aff); + + if (!data->set_list || !data->aff_list) + return isl_stat_error; + return isl_stat_ok; +} + +/* Extend "data" with "set" and "aff" as a maximum expression. + */ +static isl_stat extend_max(struct isl_from_pw_aff_data *data, + __isl_take isl_set *set, __isl_take isl_aff *aff) +{ + data->state = isl_state_max; + data->set_list = isl_set_list_add(data->set_list, set); + data->aff_list = isl_aff_list_add(data->aff_list, aff); + + if (!data->set_list || !data->aff_list) + return isl_stat_error; + return isl_stat_ok; +} + +/* Construct an isl_ast_expr from "list" within "build". + * If "state" is isl_state_single, then "list" contains a single entry and + * an isl_ast_expr is constructed for that entry. + * Otherwise a min or max expression is constructed from "list" + * depending on "state". + */ +static __isl_give isl_ast_expr *ast_expr_from_aff_list( + __isl_take isl_aff_list *list, enum isl_from_pw_aff_state state, + __isl_keep isl_ast_build *build) +{ + int i, n; + isl_aff *aff; + isl_ast_expr *expr; + enum isl_ast_op_type op_type; + + if (state == isl_state_single) { + aff = isl_aff_list_get_aff(list, 0); + isl_aff_list_free(list); + return isl_ast_expr_from_aff(aff, build); + } + n = isl_aff_list_n_aff(list); + op_type = state == isl_state_min ? isl_ast_op_min : isl_ast_op_max; + expr = isl_ast_expr_alloc_op(isl_ast_build_get_ctx(build), op_type, n); + if (!expr) + goto error; + + for (i = 0; i < n; ++i) { + isl_ast_expr *expr_i; + + aff = isl_aff_list_get_aff(list, i); + expr_i = isl_ast_expr_from_aff(aff, build); + if (!expr_i) + goto error; + expr->u.op.args[i] = expr_i; + } + + isl_aff_list_free(list); + return expr; +error: + isl_aff_list_free(list); + isl_ast_expr_free(expr); + return NULL; +} + +/* Extend the expression in data->next to take into account + * the piece in "data", allowing for a further extension + * for the next piece(s). + * In particular, data->next is set to a select operation that selects + * an isl_ast_expr corresponding to data->aff_list on data->set_list and + * to an expression that will be filled in by later calls otherwise. + * Afterwards, the state of "data" is set to isl_state_none. * - * If this is the last pair, then data->next is set to evaluate aff + * The constraints of data->set_list are added to the generated + * constraints of the build such that they can be exploited to simplify + * the AST expression constructed from data->aff_list. + */ +static isl_stat build_intermediate_piece(struct isl_from_pw_aff_data *data) +{ + isl_ctx *ctx; + isl_ast_build *build; + isl_ast_expr *ternary, *arg; + isl_set *set, *gist; + + set = isl_set_list_union(data->set_list); + if (data->state != isl_state_single) + set = isl_set_coalesce(set); + data->set_list = NULL; + ctx = isl_ast_build_get_ctx(data->build); + ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3); + gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom)); + arg = isl_ast_build_expr_from_set_internal(data->build, gist); + ternary = isl_ast_expr_set_op_arg(ternary, 0, arg); + build = isl_ast_build_copy(data->build); + build = isl_ast_build_restrict_generated(build, set); + arg = ast_expr_from_aff_list(data->aff_list, data->state, build); + data->aff_list = NULL; + isl_ast_build_free(build); + ternary = isl_ast_expr_set_op_arg(ternary, 1, arg); + data->state = isl_state_none; + if (!ternary) + return isl_stat_error; + + *data->next = ternary; + data->next = &ternary->u.op.args[2]; + + return isl_stat_ok; +} + +/* Extend the expression in data->next to take into account + * the final piece in "data". + * In particular, data->next is set to evaluate data->aff_list * and the domain is ignored. - * Otherwise, data->next is set to a select operation that selects - * an isl_ast_expr corresponding to "aff" on "set" and to an expression - * that will be filled in by later calls otherwise. * - * In both cases, the constraints of "set" are added to the generated + * The constraints of data->set_list are however added to the generated * constraints of the build such that they can be exploited to simplify - * the AST expression constructed from "aff". + * the AST expression constructed from data->aff_list. + */ +static isl_stat build_last_piece(struct isl_from_pw_aff_data *data) +{ + isl_ast_build *build; + isl_set *set; + + if (data->state == isl_state_none) + isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid, + "cannot handle void expression", return isl_stat_error); + + set = isl_set_list_union(data->set_list); + if (data->state != isl_state_single) + set = isl_set_coalesce(set); + data->set_list = NULL; + build = isl_ast_build_copy(data->build); + build = isl_ast_build_restrict_generated(build, set); + *data->next = ast_expr_from_aff_list(data->aff_list, + data->state, build); + data->aff_list = NULL; + isl_ast_build_free(build); + data->state = isl_state_none; + if (!*data->next) + return isl_stat_error; + + return isl_stat_ok; +} + +/* Can the list of pieces in "data" be extended with "set" and "aff" + * based on "test"? + * In particular, is it the case for each entry (set_i, aff_i) that + * + * test(aff, aff_i) holds on set_i, and + * test(aff_i, aff) holds on set? + * + * "test" returns the set of elements where the tests holds, meaning + * that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff). + * + * This function is used to detect min/max expressions. + * If the ast_build_detect_min_max option is turned off, then + * do not even try and perform any detection and return false instead. + */ +static isl_bool extends(struct isl_from_pw_aff_data *data, + __isl_keep isl_set *set, __isl_keep isl_aff *aff, + __isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1, + __isl_take isl_aff *aff2)) +{ + int i, n; + isl_ctx *ctx; + isl_set *dom; + + ctx = isl_ast_build_get_ctx(data->build); + if (!isl_options_get_ast_build_detect_min_max(ctx)) + return isl_bool_false; + + dom = isl_ast_build_get_domain(data->build); + set = isl_set_intersect(dom, isl_set_copy(set)); + + n = isl_set_list_n_set(data->set_list); + for (i = 0; i < n ; ++i) { + isl_aff *aff_i; + isl_set *valid; + isl_set *dom, *required; + isl_bool is_valid; + + aff_i = isl_aff_list_get_aff(data->aff_list, i); + valid = isl_set_from_basic_set(test(isl_aff_copy(aff), aff_i)); + required = isl_set_list_get_set(data->set_list, i); + dom = isl_ast_build_get_domain(data->build); + required = isl_set_intersect(dom, required); + is_valid = isl_set_is_subset(required, valid); + isl_set_free(required); + isl_set_free(valid); + if (is_valid < 0 || !is_valid) { + isl_set_free(set); + return is_valid; + } + + aff_i = isl_aff_list_get_aff(data->aff_list, i); + valid = isl_set_from_basic_set(test(aff_i, isl_aff_copy(aff))); + is_valid = isl_set_is_subset(set, valid); + isl_set_free(valid); + if (is_valid < 0 || !is_valid) { + isl_set_free(set); + return is_valid; + } + } + + isl_set_free(set); + return isl_bool_true; +} + +/* Can the list of pieces in "data" be extended with "set" and "aff" + * to form/preserve a minimum expression? + * In particular, is it the case for each entry (set_i, aff_i) that + * + * aff >= aff_i on set_i, and + * aff_i >= aff on set? + */ +static isl_bool extends_min(struct isl_from_pw_aff_data *data, + __isl_keep isl_set *set, __isl_keep isl_aff *aff) +{ + return extends(data, set, aff, &isl_aff_ge_basic_set); +} + +/* Can the list of pieces in "data" be extended with "set" and "aff" + * to form/preserve a maximum expression? + * In particular, is it the case for each entry (set_i, aff_i) that + * + * aff <= aff_i on set_i, and + * aff_i <= aff on set? + */ +static isl_bool extends_max(struct isl_from_pw_aff_data *data, + __isl_keep isl_set *set, __isl_keep isl_aff *aff) +{ + return extends(data, set, aff, &isl_aff_le_basic_set); +} + +/* This function is called during the construction of an isl_ast_expr + * that evaluates an isl_pw_aff. + * If "data" contains either a single piece or a minimum, then check + * if this minimum expression can be extended with (set, aff). + * If so, extend the sequence and return. + * Perform the same operation for maximum expressions. + * If no such extension can be performed, then + * adjust data->next to take into account the previous pieces, if any, + * by calling build_intermediate_piece and then store the current piece + * in "data" for later handling. */ static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set, __isl_take isl_aff *aff, void *user) { struct isl_from_pw_aff_data *data = user; - isl_ctx *ctx; - isl_ast_build *build; + isl_bool test; - ctx = isl_set_get_ctx(set); - data->n--; - if (data->n == 0) { - build = isl_ast_build_copy(data->build); - build = isl_ast_build_restrict_generated(build, set); - *data->next = isl_ast_expr_from_aff(aff, build); - isl_ast_build_free(build); - if (!*data->next) - return isl_stat_error; - } else { - isl_ast_expr *ternary, *arg; - isl_set *gist; - - ternary = isl_ast_expr_alloc_op(ctx, isl_ast_op_select, 3); - gist = isl_set_gist(isl_set_copy(set), isl_set_copy(data->dom)); - arg = isl_ast_build_expr_from_set_internal(data->build, gist); - ternary = isl_ast_expr_set_op_arg(ternary, 0, arg); - build = isl_ast_build_copy(data->build); - build = isl_ast_build_restrict_generated(build, set); - arg = isl_ast_expr_from_aff(aff, build); - isl_ast_build_free(build); - ternary = isl_ast_expr_set_op_arg(ternary, 1, arg); - if (!ternary) - return isl_stat_error; - - *data->next = ternary; - data->next = &ternary->u.op.args[2]; + if (data->state == isl_state_single || data->state == isl_state_min) { + test = extends_min(data, set, aff); + if (test < 0) + goto error; + if (test) + return extend_min(data, set, aff); } + if (data->state == isl_state_single || data->state == isl_state_max) { + test = extends_max(data, set, aff); + if (test < 0) + goto error; + if (test) + return extend_max(data, set, aff); + } + if (data->state != isl_state_none) { + if (build_intermediate_piece(data) < 0) + goto error; + } + set_single(data, set, aff); return isl_stat_ok; +error: + isl_set_free(set); + isl_aff_free(aff); + return isl_stat_error; } /* Construct an isl_ast_expr that evaluates "pa". @@ -1657,17 +1931,19 @@ __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal( return NULL; data.build = build; - data.n = isl_pw_aff_n_piece(pa); data.next = &res; data.dom = isl_pw_aff_domain(isl_pw_aff_copy(pa)); + data.state = isl_state_none; + data.aff_list = NULL; + data.set_list = NULL; - if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0) + if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) < 0 || + build_last_piece(&data) < 0) res = isl_ast_expr_free(res); - else if (!res) - isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid, - "cannot handle void expression", res = NULL); isl_pw_aff_free(pa); + isl_set_list_free(data.set_list); + isl_aff_list_free(data.aff_list); isl_set_free(data.dom); return res; } diff --git a/polly/lib/External/isl/isl_convex_hull.c b/polly/lib/External/isl/isl_convex_hull.c index fbd40dc2040..e169a630877 100644 --- a/polly/lib/External/isl/isl_convex_hull.c +++ b/polly/lib/External/isl/isl_convex_hull.c @@ -1395,7 +1395,7 @@ static struct isl_basic_set *convex_hull_pair(struct isl_basic_set *bset1, isl_basic_set_copy(bset2)); if (!lin) goto error; - if (isl_basic_set_is_universe(lin)) { + if (isl_basic_set_plain_is_universe(lin)) { isl_basic_set_free(bset1); isl_basic_set_free(bset2); return lin; @@ -1517,7 +1517,7 @@ static struct isl_basic_set *uset_convex_hull_unbounded(struct isl_set *set) t = isl_basic_set_lineality_space(isl_basic_set_copy(convex_hull)); if (!t) goto error; - if (isl_basic_set_is_universe(t)) { + if (isl_basic_set_plain_is_universe(t)) { isl_basic_set_free(convex_hull); convex_hull = t; break; @@ -1833,7 +1833,7 @@ static struct isl_basic_set *uset_convex_hull(struct isl_set *set) lin = uset_combined_lineality_space(isl_set_copy(set)); if (!lin) goto error; - if (isl_basic_set_is_universe(lin)) { + if (isl_basic_set_plain_is_universe(lin)) { isl_set_free(set); return lin; } diff --git a/polly/lib/External/isl/isl_id.c b/polly/lib/External/isl/isl_id.c index 37ba6db877d..d5c7c711579 100644 --- a/polly/lib/External/isl/isl_id.c +++ b/polly/lib/External/isl/isl_id.c @@ -180,7 +180,7 @@ uint32_t isl_hash_id(uint32_t hash, __isl_keep isl_id *id) /* Replace the free_user callback by "free_user". */ __isl_give isl_id *isl_id_set_free_user(__isl_take isl_id *id, - __isl_give void (*free_user)(void *user)) + void (*free_user)(void *user)) { if (!id) return NULL; diff --git a/polly/lib/External/isl/isl_id_to_id.c b/polly/lib/External/isl/isl_id_to_id.c new file mode 100644 index 00000000000..91f28d13698 --- /dev/null +++ b/polly/lib/External/isl/isl_id_to_id.c @@ -0,0 +1,10 @@ +#include <isl/id_to_id.h> + +#define isl_id_is_equal(id1,id2) id1 == id2 + +#define KEY_BASE id +#define KEY_EQUAL isl_id_is_equal +#define VAL_BASE id +#define VAL_EQUAL isl_id_is_equal + +#include <isl_hmap_templ.c> diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c index 0532bb1eeba..16cc3c24575 100644 --- a/polly/lib/External/isl/isl_map.c +++ b/polly/lib/External/isl/isl_map.c @@ -2802,7 +2802,7 @@ struct isl_basic_map *isl_basic_map_intersect_range( isl_assert(bset->ctx, isl_basic_map_compatible_range(bmap, bset), goto error); - if (isl_basic_set_is_universe(bset)) { + if (isl_basic_set_plain_is_universe(bset)) { isl_basic_set_free(bset); return bmap; } @@ -3534,8 +3534,50 @@ static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap, return bmap; } +/* Drop constraints from "bmap" that only involve the variables + * of "type" in the range [first, first + n] that are not related + * to any of the variables outside that interval. + * These constraints cannot influence the values for the variables + * outside the interval, except in case they cause "bmap" to be empty. + * Only drop the constraints if "bmap" is known to be non-empty. + */ +static __isl_give isl_basic_map *drop_irrelevant_constraints( + __isl_take isl_basic_map *bmap, enum isl_dim_type type, + unsigned first, unsigned n) +{ + int i; + int *groups; + unsigned dim, n_div; + isl_bool non_empty; + + non_empty = isl_basic_map_plain_is_non_empty(bmap); + if (non_empty < 0) + return isl_basic_map_free(bmap); + if (!non_empty) + return bmap; + + dim = isl_basic_map_dim(bmap, isl_dim_all); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + groups = isl_calloc_array(isl_basic_map_get_ctx(bmap), int, dim); + if (!groups) + return isl_basic_map_free(bmap); + first += isl_basic_map_offset(bmap, type) - 1; + for (i = 0; i < first; ++i) + groups[i] = -1; + for (i = first + n; i < dim - n_div; ++i) + groups[i] = -1; + + bmap = isl_basic_map_drop_unrelated_constraints(bmap, groups); + + return bmap; +} + /* Turn the n dimensions of type type, starting at first * into existentially quantified variables. + * + * If a subset of the projected out variables are unrelated + * to any of the variables that remain, then the constraints + * involving this subset are simply dropped first. */ __isl_give isl_basic_map *isl_basic_map_project_out( __isl_take isl_basic_map *bmap, @@ -3543,7 +3585,12 @@ __isl_give isl_basic_map *isl_basic_map_project_out( { if (n == 0) return basic_map_space_reset(bmap, type); + if (type == isl_dim_div) + isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid, + "cannot project out existentially quantified variables", + return isl_basic_map_free(bmap)); + bmap = drop_irrelevant_constraints(bmap, type, first, n); if (!bmap) return NULL; @@ -7915,18 +7962,75 @@ isl_bool isl_set_is_strict_subset(__isl_keep isl_set *set1, return isl_map_is_strict_subset((isl_map *)set1, (isl_map *)set2); } -isl_bool isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap) +/* Is "bmap" obviously equal to the universe with the same space? + * + * That is, does it not have any constraints? + */ +isl_bool isl_basic_map_plain_is_universe(__isl_keep isl_basic_map *bmap) { if (!bmap) return isl_bool_error; return bmap->n_eq == 0 && bmap->n_ineq == 0; } -isl_bool isl_basic_set_is_universe(__isl_keep isl_basic_set *bset) +/* Is "bset" obviously equal to the universe with the same space? + */ +isl_bool isl_basic_set_plain_is_universe(__isl_keep isl_basic_set *bset) { - if (!bset) + return isl_basic_map_plain_is_universe(bset); +} + +/* If "c" does not involve any existentially quantified variables, + * then set *univ to false and abort + */ +static isl_stat involves_divs(__isl_take isl_constraint *c, void *user) +{ + isl_bool *univ = user; + unsigned n; + + n = isl_constraint_dim(c, isl_dim_div); + *univ = isl_constraint_involves_dims(c, isl_dim_div, 0, n); + isl_constraint_free(c); + if (*univ < 0 || !*univ) + return isl_stat_error; + return isl_stat_ok; +} + +/* Is "bmap" equal to the universe with the same space? + * + * First check if it is obviously equal to the universe. + * If not and if there are any constraints not involving + * existentially quantified variables, then it is certainly + * not equal to the universe. + * Otherwise, check if the universe is a subset of "bmap". + */ +isl_bool isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap) +{ + isl_bool univ; + isl_basic_map *test; + + univ = isl_basic_map_plain_is_universe(bmap); + if (univ < 0 || univ) + return univ; + if (isl_basic_map_dim(bmap, isl_dim_div) == 0) + return isl_bool_false; + univ = isl_bool_true; + if (isl_basic_map_foreach_constraint(bmap, &involves_divs, &univ) < 0 && + univ) return isl_bool_error; - return bset->n_eq == 0 && bset->n_ineq == 0; + if (univ < 0 || !univ) + return univ; + test = isl_basic_map_universe(isl_basic_map_get_space(bmap)); + univ = isl_basic_map_is_subset(test, bmap); + isl_basic_map_free(test); + return univ; +} + +/* Is "bset" equal to the universe with the same space? + */ +isl_bool isl_basic_set_is_universe(__isl_keep isl_basic_set *bset) +{ + return isl_basic_map_is_universe(bset); } isl_bool isl_map_plain_is_universe(__isl_keep isl_map *map) @@ -7937,7 +8041,7 @@ isl_bool isl_map_plain_is_universe(__isl_keep isl_map *map) return isl_bool_error; for (i = 0; i < map->n; ++i) { - isl_bool r = isl_basic_map_is_universe(map->p[i]); + isl_bool r = isl_basic_map_plain_is_universe(map->p[i]); if (r < 0 || r) return r; } @@ -7954,8 +8058,7 @@ isl_bool isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap) { struct isl_basic_set *bset = NULL; struct isl_vec *sample = NULL; - isl_bool empty; - unsigned total; + isl_bool empty, non_empty; if (!bmap) return isl_bool_error; @@ -7963,7 +8066,7 @@ isl_bool isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap) if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY)) return isl_bool_true; - if (isl_basic_map_is_universe(bmap)) + if (isl_basic_map_plain_is_universe(bmap)) return isl_bool_false; if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) { @@ -7974,14 +8077,11 @@ isl_bool isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap) return empty; } - total = 1 + isl_basic_map_total_dim(bmap); - if (bmap->sample && bmap->sample->size == total) { - int contains = isl_basic_map_contains(bmap, bmap->sample); - if (contains < 0) - return isl_bool_error; - if (contains) - return isl_bool_false; - } + non_empty = isl_basic_map_plain_is_non_empty(bmap); + if (non_empty < 0) + return isl_bool_error; + if (non_empty) + return isl_bool_false; isl_vec_free(bmap->sample); bmap->sample = NULL; bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap)); @@ -8013,6 +8113,24 @@ isl_bool isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset) return ISL_F_ISSET(bset, ISL_BASIC_SET_EMPTY); } +/* Is "bmap" known to be non-empty? + * + * That is, is the cached sample still valid? + */ +isl_bool isl_basic_map_plain_is_non_empty(__isl_keep isl_basic_map *bmap) +{ + unsigned total; + + if (!bmap) + return isl_bool_error; + if (!bmap->sample) + return isl_bool_false; + total = 1 + isl_basic_map_total_dim(bmap); + if (bmap->sample->size != total) + return isl_bool_false; + return isl_basic_map_contains(bmap, bmap->sample); +} + isl_bool isl_basic_set_is_empty(__isl_keep isl_basic_set *bset) { return isl_basic_map_is_empty((struct isl_basic_map *)bset); @@ -8100,6 +8218,12 @@ error: /* Apply the expansion computed by isl_merge_divs. * The expansion itself is given by "exp" while the resulting * list of divs is given by "div". + * + * Move the integer divisions of "bset" into the right position + * according to "exp" and then introduce the additional integer + * divisions, adding div constraints. + * The moving should be done first to avoid moving coefficients + * in the definitions of the extra integer divisions. */ __isl_give isl_basic_set *isl_basic_set_expand_divs( __isl_take isl_basic_set *bset, __isl_take isl_mat *div, int *exp) @@ -8124,12 +8248,15 @@ __isl_give isl_basic_set *isl_basic_set_expand_divs( if (isl_basic_set_alloc_div(bset) < 0) goto error; - j = n_div - 1; - for (i = div->n_row - 1; i >= 0; --i) { - if (j >= 0 && exp[j] == i) { - if (i != j) - isl_basic_map_swap_div(bset, i, j); - j--; + for (j = n_div - 1; j >= 0; --j) { + if (exp[j] == j) + break; + isl_basic_map_swap_div(bset, j, exp[j]); + } + j = 0; + for (i = 0; i < div->n_row; ++i) { + if (j < n_div && exp[j] == i) { + j++; } else { isl_seq_cpy(bset->div[i], div->row[i], div->n_col); if (isl_basic_map_add_div_constraints(bset, i) < 0) @@ -9271,6 +9398,36 @@ __isl_give isl_basic_set *isl_basic_set_list_intersect( return isl_basic_map_list_intersect(list); } +/* Return the union of the elements in the non-empty list "list". + * All elements are assumed to live in the same space. + */ +__isl_give isl_set *isl_set_list_union(__isl_take isl_set_list *list) +{ + int i, n; + isl_set *set; + + if (!list) + return NULL; + n = isl_set_list_n_set(list); + if (n < 1) + isl_die(isl_set_list_get_ctx(list), isl_error_invalid, + "expecting non-empty list", goto error); + + set = isl_set_list_get_set(list, 0); + for (i = 1; i < n; ++i) { + isl_set *set_i; + + set_i = isl_set_list_get_set(list, i); + set = isl_set_union(set, set_i); + } + + isl_set_list_free(list); + return set; +error: + isl_set_list_free(list); + return NULL; +} + /* Return the Cartesian product of the basic sets in list (in the given order). */ __isl_give isl_basic_set *isl_basic_set_list_product( @@ -12293,22 +12450,27 @@ static int multi_aff_strides(__isl_keep isl_multi_aff *ma) * f_i y + h_i = m_i alpha_i * * with alpha_i an additional existentially quantified variable. + * + * The input variables of "ma" correspond to a subset of the variables + * of "bmap". There are "n_before" variables in "bmap" before this + * subset and "n_after" variables after this subset. + * The integer divisions of the affine expressions in "ma" are assumed + * to have been aligned. There are "n_div_ma" of them and + * they appear first in "bmap", straight after the "n_after" variables. */ static __isl_give isl_basic_map *add_ma_strides( __isl_take isl_basic_map *bmap, __isl_keep isl_multi_aff *ma, - int n_before, int n_after) + int n_before, int n_after, int n_div_ma) { int i, k; int div; int total; int n_param; int n_in; - int n_div; total = isl_basic_map_total_dim(bmap); n_param = isl_multi_aff_dim(ma, isl_dim_param); n_in = isl_multi_aff_dim(ma, isl_dim_in); - n_div = isl_multi_aff_dim(ma, isl_dim_div); for (i = 0; i < ma->n; ++i) { int o_bmap = 0, o_ma = 1; @@ -12332,9 +12494,9 @@ static __isl_give isl_basic_map *add_ma_strides( isl_seq_clr(bmap->eq[k] + o_bmap, n_after); o_bmap += n_after; isl_seq_cpy(bmap->eq[k] + o_bmap, - ma->p[i]->v->el + o_ma, n_div); - o_bmap += n_div; - o_ma += n_div; + ma->p[i]->v->el + o_ma, n_div_ma); + o_bmap += n_div_ma; + o_ma += n_div_ma; isl_seq_clr(bmap->eq[k] + o_bmap, 1 + total - o_bmap); isl_int_neg(bmap->eq[k][1 + total], ma->p[i]->v->el[0]); total++; @@ -12483,7 +12645,7 @@ __isl_give isl_basic_map *isl_basic_map_preimage_multi_aff( } if (strides) - res = add_ma_strides(res, ma, n_before, n_after); + res = add_ma_strides(res, ma, n_before, n_after, n_div_ma); isl_int_clear(f); isl_int_clear(c1); diff --git a/polly/lib/External/isl/isl_map_private.h b/polly/lib/External/isl/isl_map_private.h index d9be851a5d1..705b2814c5d 100644 --- a/polly/lib/External/isl/isl_map_private.h +++ b/polly/lib/External/isl/isl_map_private.h @@ -317,6 +317,8 @@ struct isl_map *isl_map_drop_inputs( struct isl_map *map, unsigned first, unsigned n); struct isl_map *isl_map_drop(struct isl_map *map, enum isl_dim_type type, unsigned first, unsigned n); +__isl_give isl_basic_map *isl_basic_map_drop_unrelated_constraints( + __isl_take isl_basic_map *bmap, __isl_take int *group); __isl_give isl_basic_map *isl_basic_map_remove_duplicate_constraints( __isl_take isl_basic_map *bmap, int *progress, int detect_divs); @@ -444,6 +446,7 @@ __isl_give isl_set *isl_set_gist_params_basic_set(__isl_take isl_set *set, int isl_map_compatible_range(__isl_keep isl_map *map, __isl_keep isl_set *set); +isl_bool isl_basic_map_plain_is_non_empty(__isl_keep isl_basic_map *bmap); isl_bool isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap); int isl_map_is_set(__isl_keep isl_map *map); @@ -468,6 +471,8 @@ int isl_set_dim_residue_class(struct isl_set *set, __isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned pos, isl_int value); +__isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap, + enum isl_dim_type type, unsigned pos, isl_int value); __isl_give isl_set *isl_set_fix(__isl_take isl_set *set, enum isl_dim_type type, unsigned pos, isl_int value); int isl_map_plain_is_fixed(__isl_keep isl_map *map, diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c index e44b0323331..15d5c20d539 100644 --- a/polly/lib/External/isl/isl_map_simplify.c +++ b/polly/lib/External/isl/isl_map_simplify.c @@ -2,6 +2,7 @@ * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2012-2013 Ecole Normale Superieure * Copyright 2014-2015 INRIA Rocquencourt + * Copyright 2016 Sven Verdoolaege * * Use of this software is governed by the MIT license * @@ -2151,30 +2152,36 @@ static int is_related(isl_int *c, int len, int *relevant) return 0; } -/* Drop constraints from "bset" that do not involve any of +/* Drop constraints from "bmap" that do not involve any of * the dimensions marked "relevant". */ -static __isl_give isl_basic_set *drop_unrelated_constraints( - __isl_take isl_basic_set *bset, int *relevant) +static __isl_give isl_basic_map *drop_unrelated_constraints( + __isl_take isl_basic_map *bmap, int *relevant) { int i, dim; - dim = isl_basic_set_dim(bset, isl_dim_set); + dim = isl_basic_map_dim(bmap, isl_dim_all); for (i = 0; i < dim; ++i) if (!relevant[i]) break; if (i >= dim) - return bset; + return bmap; - for (i = bset->n_eq - 1; i >= 0; --i) - if (!is_related(bset->eq[i] + 1, dim, relevant)) - isl_basic_set_drop_equality(bset, i); + for (i = bmap->n_eq - 1; i >= 0; --i) + if (!is_related(bmap->eq[i] + 1, dim, relevant)) { + bmap = isl_basic_map_cow(bmap); + if (isl_basic_map_drop_equality(bmap, i) < 0) + return isl_basic_map_free(bmap); + } - for (i = bset->n_ineq - 1; i >= 0; --i) - if (!is_related(bset->ineq[i] + 1, dim, relevant)) - isl_basic_set_drop_inequality(bset, i); + for (i = bmap->n_ineq - 1; i >= 0; --i) + if (!is_related(bmap->ineq[i] + 1, dim, relevant)) { + bmap = isl_basic_map_cow(bmap); + if (isl_basic_map_drop_inequality(bmap, i) < 0) + return isl_basic_map_free(bmap); + } - return bset; + return bmap; } /* Update the groups in "group" based on the (linear part of a) constraint "c". @@ -2223,11 +2230,11 @@ static int *alloc_groups(__isl_keep isl_basic_set *context) return isl_calloc_array(ctx, int, dim); } -/* Drop constraints from "context" that only involve variables that are +/* Drop constraints from "bmap" that only involve variables that are * not related to any of the variables marked with a "-1" in "group". * * We construct groups of variables that collect variables that - * (indirectly) appear in some common constraint of "context". + * (indirectly) appear in some common constraint of "bmap". * Each group is identified by the first variable in the group, * except for the special group of variables that was already identified * in the input as -1 (or are related to those variables). @@ -2235,7 +2242,7 @@ static int *alloc_groups(__isl_keep isl_basic_set *context) * otherwise the group of i is the group of group[i]. * * We first initialize groups for the remaining variables. - * Then we iterate over the constraints of "context" and update the + * Then we iterate over the constraints of "bmap" and update the * group of the variables in the constraint by the smallest group. * Finally, we resolve indirect references to groups by running over * the variables. @@ -2243,14 +2250,17 @@ static int *alloc_groups(__isl_keep isl_basic_set *context) * After computing the groups, we drop constraints that do not involve * any variables in the -1 group. */ -static __isl_give isl_basic_set *group_and_drop_irrelevant_constraints( - __isl_take isl_basic_set *context, __isl_take int *group) +__isl_give isl_basic_map *isl_basic_map_drop_unrelated_constraints( + __isl_take isl_basic_map *bmap, __isl_take int *group) { int dim; int i; int last; - dim = isl_basic_set_dim(context, isl_dim_set); + if (!bmap) + return NULL; + + dim = isl_basic_map_dim(bmap, isl_dim_all); last = -1; for (i = 0; i < dim; ++i) @@ -2258,13 +2268,13 @@ static __isl_give isl_basic_set *group_and_drop_irrelevant_constraints( last = group[i] = i; if (last < 0) { free(group); - return context; + return bmap; } - for (i = 0; i < context->n_eq; ++i) - update_groups(dim, group, context->eq[i] + 1); - for (i = 0; i < context->n_ineq; ++i) - update_groups(dim, group, context->ineq[i] + 1); + for (i = 0; i < bmap->n_eq; ++i) + update_groups(dim, group, bmap->eq[i] + 1); + for (i = 0; i < bmap->n_ineq; ++i) + update_groups(dim, group, bmap->ineq[i] + 1); for (i = 0; i < dim; ++i) if (group[i] >= 0) @@ -2273,10 +2283,10 @@ static __isl_give isl_basic_set *group_and_drop_irrelevant_constraints( for (i = 0; i < dim; ++i) group[i] = group[i] == -1; - context = drop_unrelated_constraints(context, group); + bmap = drop_unrelated_constraints(bmap, group); free(group); - return context; + return bmap; } /* Drop constraints from "context" that are irrelevant for computing @@ -2320,7 +2330,7 @@ static __isl_give isl_basic_set *drop_irrelevant_constraints( group[i] = -1; } - return group_and_drop_irrelevant_constraints(context, group); + return isl_basic_map_drop_unrelated_constraints(context, group); } /* Drop constraints from "context" that are irrelevant for computing @@ -2363,7 +2373,7 @@ static __isl_give isl_basic_set *drop_irrelevant_constraints_marked( group[i] = -1; } - return group_and_drop_irrelevant_constraints(context, group); + return isl_basic_map_drop_unrelated_constraints(context, group); } /* Do all "n" entries of "row" contain a negative value? @@ -2494,7 +2504,7 @@ static __isl_give isl_basic_set *uset_gist_full(__isl_take isl_basic_set *bset, if (!bset || !ineq || !context) goto error; - if (bset->n_ineq == 0 || isl_basic_set_is_universe(context)) { + if (bset->n_ineq == 0 || isl_basic_set_plain_is_universe(context)) { isl_basic_set_free(context); isl_mat_free(ineq); return bset; @@ -2513,7 +2523,7 @@ static __isl_give isl_basic_set *uset_gist_full(__isl_take isl_basic_set *bset, context = drop_irrelevant_constraints_marked(context, ineq, row); if (!context) goto error; - if (isl_basic_set_is_universe(context)) + if (isl_basic_set_plain_is_universe(context)) return update_ineq_free(bset, ineq, context, row, NULL); n_eq = context->n_eq; @@ -2829,7 +2839,7 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap, if (!bmap || !context) goto error; - if (isl_basic_map_is_universe(bmap)) { + if (isl_basic_map_plain_is_universe(bmap)) { isl_basic_map_free(context); return bmap; } @@ -3059,9 +3069,9 @@ __isl_give isl_basic_map *isl_basic_map_plain_gist( { isl_bool done, known; - done = isl_basic_map_is_universe(context); + done = isl_basic_map_plain_is_universe(context); if (done == isl_bool_false) - done = isl_basic_map_is_universe(bmap); + done = isl_basic_map_plain_is_universe(bmap); if (done == isl_bool_false) done = isl_basic_map_plain_is_empty(context); if (done == isl_bool_false) @@ -3121,7 +3131,7 @@ __isl_give isl_map *isl_map_plain_gist_basic_map(__isl_take isl_map *map, int i; isl_bool univ, known; - univ = isl_basic_map_is_universe(context); + univ = isl_basic_map_plain_is_universe(context); if (univ < 0) goto error; if (univ) { @@ -3141,7 +3151,7 @@ __isl_give isl_map *isl_map_plain_gist_basic_map(__isl_take isl_map *map, for (i = 0; i < map->n; ++i) { map->p[i] = isl_basic_map_plain_gist(map->p[i], isl_basic_map_copy(context)); - univ = isl_basic_map_is_universe(map->p[i]); + univ = isl_basic_map_plain_is_universe(map->p[i]); if (univ < 0) goto error; if (univ && map->n > 1) @@ -3512,11 +3522,11 @@ isl_bool isl_basic_map_is_disjoint(__isl_keep isl_basic_map *bmap1, if (disjoint < 0 || disjoint) return disjoint; - intersect = isl_basic_map_is_universe(bmap1); + intersect = isl_basic_map_plain_is_universe(bmap1); if (intersect < 0 || intersect) return intersect < 0 ? isl_bool_error : isl_bool_false; - intersect = isl_basic_map_is_universe(bmap2); + intersect = isl_basic_map_plain_is_universe(bmap2); if (intersect < 0 || intersect) return intersect < 0 ? isl_bool_error : isl_bool_false; @@ -3952,6 +3962,283 @@ static struct isl_basic_map *coalesce_or_drop_more_redundant_divs( return drop_more_redundant_divs(bmap, pairs, n); } +/* Are the "n" coefficients starting at "first" of inequality constraints + * "i" and "j" of "bmap" equal to each other? + */ +static int is_parallel_part(__isl_keep isl_basic_map *bmap, int i, int j, + int first, int n) +{ + return isl_seq_eq(bmap->ineq[i] + first, bmap->ineq[j] + first, n); +} + +/* Are the "n" coefficients starting at "first" of inequality constraints + * "i" and "j" of "bmap" opposite to each other? + */ +static int is_opposite_part(__isl_keep isl_basic_map *bmap, int i, int j, + int first, int n) +{ + return isl_seq_is_neg(bmap->ineq[i] + first, bmap->ineq[j] + first, n); +} + +/* Are inequality constraints "i" and "j" of "bmap" opposite to each other, + * apart from the constant term? + */ +static int is_opposite(__isl_keep isl_basic_map *bmap, int i, int j) +{ + unsigned total; + + total = isl_basic_map_dim(bmap, isl_dim_all); + return is_opposite_part(bmap, i, j, 1, total); +} + +/* Are inequality constraints "i" and "j" of "bmap" equal to each other, + * apart from the constant term and the coefficient at position "pos"? + */ +static int is_parallel_except(__isl_keep isl_basic_map *bmap, int i, int j, + int pos) +{ + unsigned total; + + total = isl_basic_map_dim(bmap, isl_dim_all); + return is_parallel_part(bmap, i, j, 1, pos - 1) && + is_parallel_part(bmap, i, j, pos + 1, total - pos); +} + +/* Are inequality constraints "i" and "j" of "bmap" opposite to each other, + * apart from the constant term and the coefficient at position "pos"? + */ +static int is_opposite_except(__isl_keep isl_basic_map *bmap, int i, int j, + int pos) +{ + unsigned total; + + total = isl_basic_map_dim(bmap, isl_dim_all); + return is_opposite_part(bmap, i, j, 1, pos - 1) && + is_opposite_part(bmap, i, j, pos + 1, total - pos); +} + +/* Restart isl_basic_map_drop_redundant_divs after "bmap" has + * been modified, simplying it if "simplify" is set. + * Free the temporary data structure "pairs" that was associated + * to the old version of "bmap". + */ +static __isl_give isl_basic_map *drop_redundant_divs_again( + __isl_take isl_basic_map *bmap, __isl_take int *pairs, int simplify) +{ + if (simplify) + bmap = isl_basic_map_simplify(bmap); + free(pairs); + return isl_basic_map_drop_redundant_divs(bmap); +} + +/* Is "div" the single unknown existentially quantified variable + * in inequality constraint "ineq" of "bmap"? + * "div" is known to have a non-zero coefficient in "ineq". + */ +static int single_unknown(__isl_keep isl_basic_map *bmap, int ineq, int div) +{ + int i; + unsigned n_div, o_div; + + if (isl_basic_map_div_is_known(bmap, div)) + return 0; + n_div = isl_basic_map_dim(bmap, isl_dim_div); + if (n_div == 1) + return 1; + o_div = isl_basic_map_offset(bmap, isl_dim_div); + for (i = 0; i < n_div; ++i) { + if (i == div) + continue; + if (isl_int_is_zero(bmap->ineq[ineq][o_div + i])) + continue; + if (!isl_basic_map_div_is_known(bmap, i)) + return 0; + } + + return 1; +} + +/* Does integer division "div" have coefficient 1 in inequality constraint + * "ineq" of "map"? + */ +static int has_coef_one(__isl_keep isl_basic_map *bmap, int div, int ineq) +{ + unsigned o_div; + + o_div = isl_basic_map_offset(bmap, isl_dim_div); + if (isl_int_is_one(bmap->ineq[ineq][o_div + div])) + return 1; + + return 0; +} + +/* Turn inequality constraint "ineq" of "bmap" into an equality and + * then try and drop redundant divs again, + * freeing the temporary data structure "pairs" that was associated + * to the old version of "bmap". + */ +static __isl_give isl_basic_map *set_eq_and_try_again( + __isl_take isl_basic_map *bmap, int ineq, __isl_take int *pairs) +{ + bmap = isl_basic_map_cow(bmap); + isl_basic_map_inequality_to_equality(bmap, ineq); + return drop_redundant_divs_again(bmap, pairs, 1); +} + +/* Given two inequality constraints + * + * f(x) + n d + c >= 0, (ineq) + * + * with d the variable at position "pos", and + * + * f(x) + c0 >= 0, (lower) + * + * compute the maximal value of the lower bound ceil((-f(x) - c)/n) + * determined by the first constraint. + * That is, store + * + * ceil((c0 - c)/n) + * + * in *l. + */ +static void lower_bound_from_parallel(__isl_keep isl_basic_map *bmap, + int ineq, int lower, int pos, isl_int *l) +{ + isl_int_neg(*l, bmap->ineq[ineq][0]); + isl_int_add(*l, *l, bmap->ineq[lower][0]); + isl_int_cdiv_q(*l, *l, bmap->ineq[ineq][pos]); +} + +/* Given two inequality constraints + * + * f(x) + n d + c >= 0, (ineq) + * + * with d the variable at position "pos", and + * + * -f(x) - c0 >= 0, (upper) + * + * compute the minimal value of the lower bound ceil((-f(x) - c)/n) + * determined by the first constraint. + * That is, store + * + * ceil((-c1 - c)/n) + * + * in *u. + */ +static void lower_bound_from_opposite(__isl_keep isl_basic_map *bmap, + int ineq, int upper, int pos, isl_int *u) +{ + isl_int_neg(*u, bmap->ineq[ineq][0]); + isl_int_sub(*u, *u, bmap->ineq[upper][0]); + isl_int_cdiv_q(*u, *u, bmap->ineq[ineq][pos]); +} + +/* Given a lower bound constraint "ineq" on "div" in "bmap", + * does the corresponding lower bound have a fixed value in "bmap"? + * + * In particular, "ineq" is of the form + * + * f(x) + n d + c >= 0 + * + * with n > 0, c the constant term and + * d the existentially quantified variable "div". + * That is, the lower bound is + * + * ceil((-f(x) - c)/n) + * + * Look for a pair of constraints + * + * f(x) + c0 >= 0 + * -f(x) + c1 >= 0 + * + * i.e., -c1 <= -f(x) <= c0, that fix ceil((-f(x) - c)/n) to a constant value. + * That is, check that + * + * ceil((-c1 - c)/n) = ceil((c0 - c)/n) + * + * If so, return the index of inequality f(x) + c0 >= 0. + * Otherwise, return -1. + */ +static int lower_bound_is_cst(__isl_keep isl_basic_map *bmap, int div, int ineq) +{ + int i; + int lower = -1, upper = -1; + unsigned o_div, n_div; + isl_int l, u; + int equal; + + n_div = isl_basic_map_dim(bmap, isl_dim_div); + o_div = isl_basic_map_offset(bmap, isl_dim_div); + for (i = 0; i < bmap->n_ineq && (lower < 0 || upper < 0); ++i) { + if (i == ineq) + continue; + if (!isl_int_is_zero(bmap->ineq[i][o_div + div])) + continue; + if (lower < 0 && + is_parallel_except(bmap, ineq, i, o_div + div)) { + lower = i; + continue; + } + if (upper < 0 && + is_opposite_except(bmap, ineq, i, o_div + div)) { + upper = i; + } + } + + if (lower < 0 || upper < 0) + return -1; + + isl_int_init(l); + isl_int_init(u); + + lower_bound_from_parallel(bmap, ineq, lower, o_div + div, &l); + lower_bound_from_opposite(bmap, ineq, upper, o_div + div, &u); + + equal = isl_int_eq(l, u); + + isl_int_clear(l); + isl_int_clear(u); + + return equal ? lower : -1; +} + +/* Given a lower bound constraint "ineq" on the existentially quantified + * variable "div", such that the corresponding lower bound has + * a fixed value in "bmap", assign this fixed value to the variable and + * then try and drop redundant divs again, + * freeing the temporary data structure "pairs" that was associated + * to the old version of "bmap". + * "lower" determines the constant value for the lower bound. + * + * In particular, "ineq" is of the form + * + * f(x) + n d + c >= 0, + * + * while "lower" is of the form + * + * f(x) + c0 >= 0 + * + * The lower bound is ceil((-f(x) - c)/n) and its constant value + * is ceil((c0 - c)/n). + */ +static __isl_give isl_basic_map *fix_cst_lower(__isl_take isl_basic_map *bmap, + int div, int ineq, int lower, int *pairs) +{ + isl_int c; + unsigned o_div; + + isl_int_init(c); + + o_div = isl_basic_map_offset(bmap, isl_dim_div); + lower_bound_from_parallel(bmap, ineq, lower, o_div + div, &c); + bmap = isl_basic_map_fix(bmap, isl_dim_div, div, c); + free(pairs); + + isl_int_clear(c); + + return isl_basic_map_drop_redundant_divs(bmap); +} + /* Remove divs that are not strictly needed. * In particular, if a div only occurs positively (or negatively) * in constraints, then it can simply be dropped. @@ -3960,9 +4247,32 @@ static struct isl_basic_map *coalesce_or_drop_more_redundant_divs( * term and if the sum of the constant terms is such that for any value * of the other values, there is always at least one integer value of the * div, i.e., if one plus this sum is greater than or equal to - * the (absolute value) of the coefficent of the div in the constraints, + * the (absolute value) of the coefficient of the div in the constraints, * then we can also simply drop the div. * + * If an existentially quantified variable does not have an explicit + * representation, appears in only a single lower bound that does not + * involve any other such existentially quantified variables and appears + * in this lower bound with coefficient 1, + * then fix the variable to the value of the lower bound. That is, + * turn the inequality into an equality. + * If for any value of the other variables, there is any value + * for the existentially quantified variable satisfying the constraints, + * then this lower bound also satisfies the constraints. + * It is therefore safe to pick this lower bound. + * + * The same reasoning holds even if the coefficient is not one. + * However, fixing the variable to the value of the lower bound may + * in general introduce an extra integer division, in which case + * it may be better to pick another value. + * If this integer division has a known constant value, then plugging + * in this constant value removes the existentially quantified variable + * completely. In particular, if the lower bound is of the form + * ceil((-f(x) - c)/n) and there are two constraints, f(x) + c0 >= 0 and + * -f(x) + c1 >= 0 such that ceil((-c1 - c)/n) = ceil((c0 - c)/n), + * then the existentially quantified variable can be assigned this + * shared value. + * * We skip divs that appear in equalities or in the definition of other divs. * Divs that appear in the definition of other divs usually occur in at least * 4 constraints, but the constraints may have been simplified. @@ -4023,15 +4333,24 @@ struct isl_basic_map *isl_basic_map_drop_redundant_divs( if (!isl_int_is_zero(bmap->ineq[j][1+off+i])) isl_basic_map_drop_inequality(bmap, j); bmap = isl_basic_map_drop_div(bmap, i); - free(pairs); - return isl_basic_map_drop_redundant_divs(bmap); + return drop_redundant_divs_again(bmap, pairs, 0); } - if (pairs[i] != 1) - continue; - if (!isl_seq_is_neg(bmap->ineq[last_pos] + 1, - bmap->ineq[last_neg] + 1, - off + bmap->n_div)) + if (pairs[i] != 1 || !is_opposite(bmap, last_pos, last_neg)) { + int single, lower; + if (pos != 1) + continue; + single = single_unknown(bmap, last_pos, i); + if (!single) + continue; + if (has_coef_one(bmap, i, last_pos)) + return set_eq_and_try_again(bmap, last_pos, + pairs); + lower = lower_bound_is_cst(bmap, i, last_pos); + if (lower >= 0) + return fix_cst_lower(bmap, i, last_pos, lower, + pairs); continue; + } isl_int_add(bmap->ineq[last_pos][0], bmap->ineq[last_pos][0], bmap->ineq[last_neg][0]); @@ -4051,9 +4370,7 @@ struct isl_basic_map *isl_basic_map_drop_redundant_divs( continue; } bmap = set_div_from_lower_bound(bmap, i, last_pos); - bmap = isl_basic_map_simplify(bmap); - free(pairs); - return isl_basic_map_drop_redundant_divs(bmap); + return drop_redundant_divs_again(bmap, pairs, 1); } if (last_pos > last_neg) { isl_basic_map_drop_inequality(bmap, last_pos); @@ -4063,8 +4380,7 @@ struct isl_basic_map *isl_basic_map_drop_redundant_divs( isl_basic_map_drop_inequality(bmap, last_pos); } bmap = isl_basic_map_drop_div(bmap, i); - free(pairs); - return isl_basic_map_drop_redundant_divs(bmap); + return drop_redundant_divs_again(bmap, pairs, 0); } if (n > 0) diff --git a/polly/lib/External/isl/isl_mat.c b/polly/lib/External/isl/isl_mat.c index 483eaf078e9..efb22310e55 100644 --- a/polly/lib/External/isl/isl_mat.c +++ b/polly/lib/External/isl/isl_mat.c @@ -1191,7 +1191,7 @@ struct isl_set *isl_set_preimage(struct isl_set *set, struct isl_mat *mat) set = isl_set_cow(set); if (!set) - return NULL; + goto error; for (i = 0; i < set->n; ++i) { set->p[i] = isl_basic_set_preimage(set->p[i], diff --git a/polly/lib/External/isl/isl_options.c b/polly/lib/External/isl/isl_options.c index bbf5a5989a8..f9a1837f713 100644 --- a/polly/lib/External/isl/isl_options.c +++ b/polly/lib/External/isl/isl_options.c @@ -182,10 +182,14 @@ ISL_ARG_STR(struct isl_options, ast_iterator_type, 0, ISL_ARG_BOOL(struct isl_options, ast_always_print_block, 0, "ast-always-print-block", 0, "print for and if bodies as a block " "regardless of the number of statements in the body") +ISL_ARG_BOOL(struct isl_options, ast_print_macro_once, 0, + "ast-print-macro-once", 0, "only print macro definitions once") ISL_ARG_BOOL(struct isl_options, ast_build_atomic_upper_bound, 0, "ast-build-atomic-upper-bound", 1, "generate atomic upper bounds") ISL_ARG_BOOL(struct isl_options, ast_build_prefer_pdiv, 0, "ast-build-prefer-pdiv", 1, "prefer pdiv operation over fdiv") +ISL_ARG_BOOL(struct isl_options, ast_build_detect_min_max, 0, + "ast-build-detect-min-max", 0, "detect min/max expressions") ISL_ARG_BOOL(struct isl_options, ast_build_exploit_nested_bounds, 0, "ast-build-exploit-nested-bounds", 1, "simplify conditions based on bounds of nested for loops") @@ -303,6 +307,11 @@ ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ast_build_prefer_pdiv) ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_detect_min_max) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_build_detect_min_max) + +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ast_build_exploit_nested_bounds) ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ast_build_exploit_nested_bounds) @@ -322,6 +331,11 @@ ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ast_always_print_block) +ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_print_macro_once) +ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, + ast_print_macro_once) + ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, ast_build_separation_bounds) ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, diff --git a/polly/lib/External/isl/isl_options_private.h b/polly/lib/External/isl/isl_options_private.h index f3119516306..b4bb272531c 100644 --- a/polly/lib/External/isl/isl_options_private.h +++ b/polly/lib/External/isl/isl_options_private.h @@ -52,9 +52,11 @@ struct isl_options { char *ast_iterator_type; int ast_always_print_block; + int ast_print_macro_once; int ast_build_atomic_upper_bound; int ast_build_prefer_pdiv; + int ast_build_detect_min_max; int ast_build_exploit_nested_bounds; int ast_build_group_coscheduled; int ast_build_separation_bounds; diff --git a/polly/lib/External/isl/isl_output.c b/polly/lib/External/isl/isl_output.c index a0a578779bc..aeb7a98ebac 100644 --- a/polly/lib/External/isl/isl_output.c +++ b/polly/lib/External/isl/isl_output.c @@ -780,7 +780,7 @@ static __isl_give isl_printer *print_optional_disjunct( __isl_keep isl_basic_map *bmap, __isl_keep isl_space *space, __isl_take isl_printer *p, int latex) { - if (isl_basic_map_is_universe(bmap)) + if (isl_basic_map_plain_is_universe(bmap)) return p; p = isl_printer_print_str(p, ": "); @@ -937,7 +937,7 @@ static __isl_give isl_printer *print_disjuncts(__isl_keep isl_map *map, isl_bool is_universe; hull = isl_map_plain_unshifted_simple_hull(isl_map_copy(map)); - is_universe = isl_basic_map_is_universe(hull); + is_universe = isl_basic_map_plain_is_universe(hull); if (is_universe < 0) p = isl_printer_free(p); else if (!is_universe) diff --git a/polly/lib/External/isl/isl_printer.c b/polly/lib/External/isl/isl_printer.c index 0c9b75ae2e4..6b76390be0e 100644 --- a/polly/lib/External/isl/isl_printer.c +++ b/polly/lib/External/isl/isl_printer.c @@ -272,6 +272,7 @@ __isl_null isl_printer *isl_printer_free(__isl_take isl_printer *p) free(p->prefix); free(p->suffix); free(p->yaml_state); + isl_id_to_id_free(p->notes); isl_ctx_deref(p->ctx); free(p); @@ -384,6 +385,63 @@ int isl_printer_get_output_format(__isl_keep isl_printer *p) return p->output_format; } +/* Does "p" have a note with identifier "id"? + */ +isl_bool isl_printer_has_note(__isl_keep isl_printer *p, + __isl_keep isl_id *id) +{ + if (!p || !id) + return isl_bool_error; + if (!p->notes) + return isl_bool_false; + return isl_id_to_id_has(p->notes, id); +} + +/* Retrieve the note identified by "id" from "p". + * The note is assumed to exist. + */ +__isl_give isl_id *isl_printer_get_note(__isl_keep isl_printer *p, + __isl_take isl_id *id) +{ + isl_bool has_note; + + has_note = isl_printer_has_note(p, id); + if (has_note < 0) + goto error; + if (!has_note) + isl_die(isl_printer_get_ctx(p), isl_error_invalid, + "no such note", goto error); + + return isl_id_to_id_get(p->notes, id); +error: + isl_id_free(id); + return NULL; +} + +/* Associate "note" to the identifier "id" in "p", + * replacing the previous note associated to the identifier, if any. + */ +__isl_give isl_printer *isl_printer_set_note(__isl_take isl_printer *p, + __isl_take isl_id *id, __isl_take isl_id *note) +{ + if (!p || !id || !note) + goto error; + if (!p->notes) { + p->notes = isl_id_to_id_alloc(isl_printer_get_ctx(p), 1); + if (!p->notes) + goto error; + } + p->notes = isl_id_to_id_set(p->notes, id, note); + if (!p->notes) + return isl_printer_free(p); + return p; +error: + isl_printer_free(p); + isl_id_free(id); + isl_id_free(note); + return NULL; +} + /* Keep track of whether the printing to "p" is being performed from * an isl_*_dump function as specified by "dump". */ diff --git a/polly/lib/External/isl/isl_printer_private.h b/polly/lib/External/isl/isl_printer_private.h index 7af8aae65da..6b852e8bc47 100644 --- a/polly/lib/External/isl/isl_printer_private.h +++ b/polly/lib/External/isl/isl_printer_private.h @@ -3,6 +3,7 @@ #include <isl/printer.h> #include <isl_yaml.h> +#include <isl/id_to_id.h> struct isl_printer_ops; @@ -17,6 +18,10 @@ struct isl_printer_ops; * yaml_size is the size of this arrays, while yaml_depth * is the number of elements currently in use. * yaml_state may be NULL if no YAML printing is being performed. + * + * notes keeps track of arbitrary notes as a mapping between + * name identifiers and note identifiers. It may be NULL + * if there are no notes yet. */ struct isl_printer { struct isl_ctx *ctx; @@ -37,6 +42,8 @@ struct isl_printer { int yaml_depth; int yaml_size; enum isl_yaml_state *yaml_state; + + isl_id_to_id *notes; }; __isl_give isl_printer *isl_printer_set_dump(__isl_take isl_printer *p, diff --git a/polly/lib/External/isl/isl_schedule.c b/polly/lib/External/isl/isl_schedule.c index 6d98af37785..3db1760126a 100644 --- a/polly/lib/External/isl/isl_schedule.c +++ b/polly/lib/External/isl/isl_schedule.c @@ -52,13 +52,12 @@ __isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx, if (!schedule) goto error; - schedule->leaf.ctx = ctx; - isl_ctx_ref(ctx); schedule->ref = 1; schedule->root = tree; - schedule->leaf.ref = -1; - schedule->leaf.type = isl_schedule_node_leaf; + schedule->leaf = isl_schedule_tree_leaf(ctx); + if (!schedule->leaf) + return isl_schedule_free(schedule); return schedule; error: isl_schedule_tree_free(tree); @@ -134,7 +133,7 @@ __isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched) isl_band_list_free(sched->band_forest); isl_schedule_tree_free(sched->root); - isl_ctx_deref(sched->leaf.ctx); + isl_schedule_tree_free(sched->leaf); free(sched); return NULL; } @@ -166,7 +165,7 @@ error: isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule) { - return schedule ? schedule->leaf.ctx : NULL; + return schedule ? isl_schedule_tree_get_ctx(schedule->leaf) : NULL; } /* Return a pointer to the leaf of "schedule". @@ -177,7 +176,7 @@ isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule) __isl_keep isl_schedule_tree *isl_schedule_peek_leaf( __isl_keep isl_schedule *schedule) { - return schedule ? &schedule->leaf : NULL; + return schedule ? schedule->leaf : NULL; } /* Are "schedule1" and "schedule2" obviously equal to each other? diff --git a/polly/lib/External/isl/isl_schedule_node.c b/polly/lib/External/isl/isl_schedule_node.c index 7c369e774d2..49c739e3d14 100644 --- a/polly/lib/External/isl/isl_schedule_node.c +++ b/polly/lib/External/isl/isl_schedule_node.c @@ -4308,7 +4308,7 @@ static __isl_give isl_schedule_node *isl_schedule_node_order_before_or_after( { enum isl_schedule_node_type ancestors[] = { isl_schedule_node_filter, isl_schedule_node_sequence }; - isl_union_set *node_domain, *node_filter = NULL; + isl_union_set *node_domain, *node_filter = NULL, *parent_filter; isl_schedule_node *node2; isl_schedule_tree *tree1, *tree2; int empty1, empty2; @@ -4322,8 +4322,6 @@ static __isl_give isl_schedule_node *isl_schedule_node_order_before_or_after( in_seq = has_ancestors(node, 2, ancestors); if (in_seq < 0) goto error; - if (in_seq) - node = isl_schedule_node_parent(node); node_domain = isl_schedule_node_get_domain(node); filter = isl_union_set_gist(filter, isl_union_set_copy(node_domain)); node_filter = isl_union_set_copy(node_domain); @@ -4340,14 +4338,22 @@ static __isl_give isl_schedule_node *isl_schedule_node_order_before_or_after( return node; } + if (in_seq) { + node = isl_schedule_node_parent(node); + parent_filter = isl_schedule_node_filter_get_filter(node); + node_filter = isl_union_set_intersect(node_filter, + isl_union_set_copy(parent_filter)); + filter = isl_union_set_intersect(filter, parent_filter); + } + node2 = isl_schedule_node_copy(node); node = isl_schedule_node_gist(node, isl_union_set_copy(node_filter)); node2 = isl_schedule_node_gist(node2, isl_union_set_copy(filter)); tree1 = isl_schedule_node_get_tree(node); tree2 = isl_schedule_node_get_tree(node2); - isl_schedule_node_free(node2); tree1 = isl_schedule_tree_insert_filter(tree1, node_filter); tree2 = isl_schedule_tree_insert_filter(tree2, filter); + isl_schedule_node_free(node2); if (before) { tree1 = isl_schedule_tree_sequence_pair(tree2, tree1); diff --git a/polly/lib/External/isl/isl_schedule_private.h b/polly/lib/External/isl/isl_schedule_private.h index fd5c979a226..9ae4047c41c 100644 --- a/polly/lib/External/isl/isl_schedule_private.h +++ b/polly/lib/External/isl/isl_schedule_private.h @@ -13,9 +13,9 @@ * "root" is the root of the schedule tree and may be NULL if we * have created a band forest corresponding to the schedule. * - * A pointer to "leaf" may be used to represent a leaf of the schedule. + * "leaf" may be used to represent a leaf of the schedule. * It should not appear as a child to any other isl_schedule_tree objects, - * but an isl_schedule_node may point to "leaf" if it refers to + * but an isl_schedule_node may have "leaf" as its tree if it refers to * a leaf of this schedule tree. */ struct isl_schedule { @@ -24,7 +24,7 @@ struct isl_schedule { isl_band_list *band_forest; isl_schedule_tree *root; - struct isl_schedule_tree leaf; + struct isl_schedule_tree *leaf; }; __isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx, diff --git a/polly/lib/External/isl/isl_schedule_tree.c b/polly/lib/External/isl/isl_schedule_tree.c index b6214fdeb92..f832b8701ff 100644 --- a/polly/lib/External/isl/isl_schedule_tree.c +++ b/polly/lib/External/isl/isl_schedule_tree.c @@ -140,10 +140,6 @@ __isl_take isl_schedule_tree *isl_schedule_tree_dup( /* Return an isl_schedule_tree that is equal to "tree" and that has only * a single reference. - * - * This function is called before a tree is modified. - * A static tree (with negative reference count) should never be modified, - * so it is not allowed to call this function on a static tree. */ __isl_give isl_schedule_tree *isl_schedule_tree_cow( __isl_take isl_schedule_tree *tree) @@ -151,11 +147,6 @@ __isl_give isl_schedule_tree *isl_schedule_tree_cow( if (!tree) return NULL; - if (tree->ref < 0) - isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal, - "static trees cannot be modified", - return isl_schedule_tree_free(tree)); - if (tree->ref == 1) return tree; tree->ref--; @@ -163,9 +154,6 @@ __isl_give isl_schedule_tree *isl_schedule_tree_cow( } /* Return a new reference to "tree". - * - * A static tree (with negative reference count) does not keep track - * of the number of references and should not be modified. */ __isl_give isl_schedule_tree *isl_schedule_tree_copy( __isl_keep isl_schedule_tree *tree) @@ -173,9 +161,6 @@ __isl_give isl_schedule_tree *isl_schedule_tree_copy( if (!tree) return NULL; - if (tree->ref < 0) - return tree; - tree->ref++; return tree; } @@ -187,8 +172,6 @@ __isl_null isl_schedule_tree *isl_schedule_tree_free( { if (!tree) return NULL; - if (tree->ref < 0) - return NULL; if (--tree->ref > 0) return NULL; diff --git a/polly/lib/External/isl/isl_schedule_tree.h b/polly/lib/External/isl/isl_schedule_tree.h index 2ae2f0f594b..fecf9ccf212 100644 --- a/polly/lib/External/isl/isl_schedule_tree.h +++ b/polly/lib/External/isl/isl_schedule_tree.h @@ -14,11 +14,7 @@ ISL_DECLARE_LIST(schedule_tree) /* A schedule (sub)tree. * * The leaves of a tree are not explicitly represented inside - * the isl_schedule_tree. If a tree consists of only a leaf, - * then it is equal to the static object isl_schedule_tree_empty. - * - * ctx may be NULL if type is isl_schedule_node_leaf. - * In this case, ref has a negative value. + * the isl_schedule_tree, except when the tree consists of only a leaf. * * The "band" field is valid when type is isl_schedule_node_band. * The "context" field is valid when type is isl_schedule_node_context diff --git a/polly/lib/External/isl/isl_tab_pip.c b/polly/lib/External/isl/isl_tab_pip.c index 84e85ffa5d3..a221eeffe06 100644 --- a/polly/lib/External/isl/isl_tab_pip.c +++ b/polly/lib/External/isl/isl_tab_pip.c @@ -284,6 +284,8 @@ static int same_solution(struct isl_partial_sol *s1, struct isl_partial_sol *s2, * and represent the same solution, then their domains are combined. * This combined domain is the same as the current context domain * as sol_pop is called each time we move back to a higher level. + * If the outer level (0) has been reached, then all partial solutions + * at the current level are also popped off. */ static void sol_pop(struct isl_sol *sol) { @@ -293,16 +295,16 @@ static void sol_pop(struct isl_sol *sol) if (sol->error) return; - if (sol->level == 0) { + partial = sol->partial; + if (!partial) + return; + + if (partial->level == 0 && sol->level == 0) { for (partial = sol->partial; partial; partial = sol->partial) sol_pop_one(sol); return; } - partial = sol->partial; - if (!partial) - return; - if (partial->level <= sol->level) return; @@ -344,6 +346,12 @@ static void sol_pop(struct isl_sol *sol) } else sol_pop_one(sol); + if (sol->level == 0) { + for (partial = sol->partial; partial; partial = sol->partial) + sol_pop_one(sol); + return; + } + if (0) error: sol->error = 1; } diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index e791fa27ac0..e6bbace3d3d 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -2219,35 +2219,49 @@ static int test_lexmin(struct isl_ctx *ctx) return 0; } -/* Check that isl_set_min_val and isl_set_max_val compute the correct - * result on non-convex inputs. +struct { + const char *set; + const char *obj; + __isl_give isl_val *(*fn)(__isl_keep isl_set *set, + __isl_keep isl_aff *obj); + const char *res; +} opt_tests[] = { + { "{ [-1]; [1] }", "{ [x] -> [x] }", &isl_set_min_val, "-1" }, + { "{ [-1]; [1] }", "{ [x] -> [x] }", &isl_set_max_val, "1" }, + { "{ [a, b] : 0 <= a, b <= 100 and b mod 2 = 0}", + "{ [a, b] -> [floor((b - 2*floor((-a)/4))/5)] }", + &isl_set_max_val, "30" }, + +}; + +/* Perform basic isl_set_min_val and isl_set_max_val tests. + * In particular, check the results on non-convex inputs. */ static int test_min(struct isl_ctx *ctx) { + int i; isl_set *set; - isl_aff *aff; - isl_val *val; - int min_ok, max_ok; - - set = isl_set_read_from_str(ctx, "{ [-1]; [1] }"); - aff = isl_aff_read_from_str(ctx, "{ [x] -> [x] }"); - val = isl_set_min_val(set, aff); - min_ok = isl_val_is_negone(val); - isl_val_free(val); - val = isl_set_max_val(set, aff); - max_ok = isl_val_is_one(val); - isl_val_free(val); - isl_aff_free(aff); - isl_set_free(set); + isl_aff *obj; + isl_val *val, *res; + isl_bool ok; + + for (i = 0; i < ARRAY_SIZE(opt_tests); ++i) { + set = isl_set_read_from_str(ctx, opt_tests[i].set); + obj = isl_aff_read_from_str(ctx, opt_tests[i].obj); + res = isl_val_read_from_str(ctx, opt_tests[i].res); + val = opt_tests[i].fn(set, obj); + ok = isl_val_eq(res, val); + isl_val_free(res); + isl_val_free(val); + isl_aff_free(obj); + isl_set_free(set); - if (min_ok < 0 || max_ok < 0) - return -1; - if (!min_ok) - isl_die(ctx, isl_error_unknown, - "unexpected minimum", return -1); - if (!max_ok) - isl_die(ctx, isl_error_unknown, - "unexpected maximum", return -1); + if (ok < 0) + return -1; + if (!ok) + isl_die(ctx, isl_error_unknown, + "unexpected optimum", return -1); + } return 0; } @@ -5181,6 +5195,8 @@ struct { "B[i] -> D[i] : exists a : i = 2 a + 1 }", "{ A[i] -> B[2i] }", "{ A[i] -> C[2i] }" }, + { "{ A[i] -> B[i] }", "{ C[i] -> A[(i + floor(i/3))/2] }", + "{ C[i] -> B[j] : 2j = i + floor(i/3) }" }, }; static int test_preimage_union_map(isl_ctx *ctx) @@ -6246,10 +6262,34 @@ static int test_domain_hash(isl_ctx *ctx) return 0; } +/* Check that a universe basic set that is not obviously equal to the universe + * is still recognized as being equal to the universe. + */ +static int test_universe(isl_ctx *ctx) +{ + const char *s; + isl_basic_set *bset; + isl_bool is_univ; + + s = "{ [] : exists x, y : 3y <= 2x and y >= -3 + 2x and 2y >= 2 - x }"; + bset = isl_basic_set_read_from_str(ctx, s); + is_univ = isl_basic_set_is_universe(bset); + isl_basic_set_free(bset); + + if (is_univ < 0) + return -1; + if (!is_univ) + isl_die(ctx, isl_error_unknown, + "not recognized as universe set", return -1); + + return 0; +} + struct { const char *name; int (*fn)(isl_ctx *ctx); } tests [] = { + { "universe", &test_universe }, { "domain hash", &test_domain_hash }, { "dual", &test_dual }, { "dependence analysis", &test_flow }, diff --git a/polly/lib/External/isl/isl_transitive_closure.c b/polly/lib/External/isl/isl_transitive_closure.c index 7ef84d48716..a03df7cda1d 100644 --- a/polly/lib/External/isl/isl_transitive_closure.c +++ b/polly/lib/External/isl/isl_transitive_closure.c @@ -435,6 +435,7 @@ static int empty_path_is_identity(__isl_keep isl_basic_map *path, unsigned pos) goto error; isl_seq_clr(test->eq[k], 1 + isl_basic_map_total_dim(test)); isl_int_set_si(test->eq[k][pos], 1); + test = isl_basic_map_gauss(test, NULL); id = isl_basic_map_identity(isl_basic_map_get_space(path)); is_id = isl_basic_map_is_equal(test, id); isl_basic_map_free(test); diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/equality.c b/polly/lib/External/isl/test_inputs/codegen/cloog/equality.c index 2535b8b975e..5fd62076ccc 100644 --- a/polly/lib/External/isl/test_inputs/codegen/cloog/equality.c +++ b/polly/lib/External/isl/test_inputs/codegen/cloog/equality.c @@ -1,5 +1,5 @@ for (int c0 = 0; c0 <= 5; c0 += 1) - for (int c1 = c0 <= 2 ? 2 * c0 : 4; c1 <= (c0 >= 2 ? 2 * c0 : 4); c1 += 1) { + for (int c1 = min(2 * c0, 4); c1 <= max(2 * c0, 4); c1 += 1) { if (c1 == 2 * c0) S1(c0, 2 * c0); if (c1 == 4) diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/param-split.c b/polly/lib/External/isl/test_inputs/codegen/cloog/param-split.c index e7774d55d1e..a9d97124b52 100644 --- a/polly/lib/External/isl/test_inputs/codegen/cloog/param-split.c +++ b/polly/lib/External/isl/test_inputs/codegen/cloog/param-split.c @@ -1,4 +1,4 @@ -for (int c0 = 0; c0 <= (M <= 0 ? 0 : M); c0 += 1) { +for (int c0 = 0; c0 <= max(0, M); c0 += 1) { if (M >= c0) S1(c0); if (c0 == 0) diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/m11-0.c b/polly/lib/External/isl/test_inputs/codegen/omega/m11-0.c index 1ecb4a53289..bf727b35395 100644 --- a/polly/lib/External/isl/test_inputs/codegen/omega/m11-0.c +++ b/polly/lib/External/isl/test_inputs/codegen/omega/m11-0.c @@ -1,5 +1,5 @@ for (int c0 = 1; c0 <= min(4, floord(2 * m - 1, 17) + 1); c0 += 1) - for (int c1 = 1; c1 <= 2; c1 += 1) + for (int c1 = 1; c1 <= min(2, -2 * c0 + (2 * m + 3 * c0 - 4) / 10 + 3); c1 += 1) for (int c2 = 0; c2 <= min(2, -c0 - c1 + (2 * m + 3 * c0 + 10 * c1 + 6) / 20 + 1); c2 += 1) for (int c3 = 8 * c0 + (c0 + 1) / 2 - 8; c3 <= min(min(30, m - 5 * c1 - 10 * c2 + 5), 8 * c0 + c0 / 2); c3 += 1) for (int c4 = 5 * c1 + 10 * c2 - 4; c4 <= min(5 * c1 + 10 * c2, m - c3 + 1); c4 += 1) |
