diff options
71 files changed, 2766 insertions, 1115 deletions
diff --git a/polly/lib/External/CMakeLists.txt b/polly/lib/External/CMakeLists.txt index 77cc28c70c0..5345a06270c 100644 --- a/polly/lib/External/CMakeLists.txt +++ b/polly/lib/External/CMakeLists.txt @@ -209,6 +209,7 @@ set (ISL_FILES isl/isl_imath.c isl/isl_input.c isl/isl_int_sioimath.c + isl/isl_local.c isl/isl_local_space.c isl/isl_lp.c isl/isl_map.c diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID index 7169df5d106..cabdbedc0e8 100644 --- a/polly/lib/External/isl/GIT_HEAD_ID +++ b/polly/lib/External/isl/GIT_HEAD_ID @@ -1 +1 @@ -isl-0.16.1-68-g8fad211 +isl-0.16.1-145-g243bf7c diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am index 81bc9a0fb03..a3b58297cec 100644 --- a/polly/lib/External/isl/Makefile.am +++ b/polly/lib/External/isl/Makefile.am @@ -114,6 +114,8 @@ libisl_la_SOURCES = \ isl_ilp_private.h \ isl_input.c \ isl_int.h \ + isl_local.h \ + isl_local.c \ isl_local_space_private.h \ isl_local_space.c \ isl_lp.c \ @@ -261,6 +263,7 @@ pkginclude_HEADERS = \ include/isl/ilp.h \ include/isl/hash.h \ include/isl/hmap.h \ + include/isl/hmap_templ.c \ include/isl/list.h \ include/isl/local_space.h \ include/isl/lp.h \ @@ -268,6 +271,12 @@ pkginclude_HEADERS = \ include/isl/map.h \ include/isl/map_to_basic_set.h \ include/isl/map_type.h \ + include/isl/maybe.h \ + include/isl/maybe_ast_expr.h \ + include/isl/maybe_basic_set.h \ + include/isl/maybe_id.h \ + include/isl/maybe_pw_aff.h \ + include/isl/maybe_templ.h \ include/isl/multi.h \ include/isl/obj.h \ include/isl/options.h \ @@ -323,7 +332,6 @@ EXTRA_DIST = \ LICENSE \ isl_config_post.h \ basis_reduction_templ.c \ - isl_hmap_templ.c \ isl_list_templ.c \ isl_list_templ.h \ isl_map_lexopt_templ.c \ @@ -333,13 +341,18 @@ EXTRA_DIST = \ isl_multi_apply_templ.c \ isl_multi_apply_set.c \ isl_multi_apply_union_set.c \ + isl_multi_cmp.c \ isl_multi_coalesce.c \ isl_multi_floor.c \ isl_multi_gist.c \ + isl_multi_hash.c \ isl_multi_intersect.c \ print_templ.c \ isl_power_templ.c \ + isl_pw_macro.h \ isl_pw_templ.c \ + isl_pw_hash.c \ + isl_pw_union_opt.c \ isl_union_macro.h \ isl_union_templ.c \ isl_union_single.c \ diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in index 3ab5117ebe3..87402a4c965 100644 --- a/polly/lib/External/isl/Makefile.in +++ b/polly/lib/External/isl/Makefile.in @@ -187,17 +187,17 @@ am__libisl_la_SOURCES_DIST = mp_get_memory_functions.c isl_int_gmp.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_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 \ - isl_mat.c isl_mat_private.h isl_morph.c isl_morph.h isl_id.c \ - isl_id_private.h isl_obj.c isl_options.c isl_options_private.h \ - isl_output.c isl_output_private.h isl_point_private.h \ - isl_point.c isl_polynomial_private.h isl_polynomial.c \ - isl_printer_private.h isl_printer.c print.c isl_range.c \ - isl_range.h isl_reordering.c isl_reordering.h isl_sample.h \ - isl_sample.c isl_scan.c isl_scan.h isl_schedule.c \ + isl_ilp.c isl_ilp_private.h isl_input.c isl_int.h isl_local.h \ + isl_local.c 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 isl_mat.c isl_mat_private.h isl_morph.c \ + isl_morph.h isl_id.c isl_id_private.h isl_obj.c isl_options.c \ + isl_options_private.h isl_output.c isl_output_private.h \ + isl_point_private.h isl_point.c isl_polynomial_private.h \ + isl_polynomial.c isl_printer_private.h isl_printer.c print.c \ + isl_range.c isl_range.h isl_reordering.c isl_reordering.h \ + isl_sample.h isl_sample.c isl_scan.c isl_scan.h isl_schedule.c \ isl_schedule_band.c isl_schedule_band.h isl_schedule_node.c \ isl_schedule_node_private.h isl_schedule_read.c \ isl_schedule_tree.c isl_schedule_tree.h isl_schedule_private.h \ @@ -234,8 +234,8 @@ am_libisl_la_OBJECTS = $(am__objects_4) $(am__objects_5) isl_aff.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_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_ilp.lo isl_input.lo isl_local.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 \ @@ -386,16 +386,19 @@ am__pkginclude_HEADERS_DIST = include/isl/val_gmp.h include/isl/aff.h \ 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 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 \ + include/isl/hash.h include/isl/hmap.h include/isl/hmap_templ.c \ + 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/maybe.h include/isl/maybe_ast_expr.h \ + include/isl/maybe_basic_set.h include/isl/maybe_id.h \ + include/isl/maybe_pw_aff.h include/isl/maybe_templ.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 \ include/isl/stream.h include/isl/union_map.h \ include/isl/union_map_type.h include/isl/union_set.h \ include/isl/union_set_type.h include/isl/val.h \ @@ -870,6 +873,8 @@ libisl_la_SOURCES = \ isl_ilp_private.h \ isl_input.c \ isl_int.h \ + isl_local.h \ + isl_local.c \ isl_local_space_private.h \ isl_local_space.c \ isl_lp.c \ @@ -1014,6 +1019,7 @@ pkginclude_HEADERS = \ include/isl/ilp.h \ include/isl/hash.h \ include/isl/hmap.h \ + include/isl/hmap_templ.c \ include/isl/list.h \ include/isl/local_space.h \ include/isl/lp.h \ @@ -1021,6 +1027,12 @@ pkginclude_HEADERS = \ include/isl/map.h \ include/isl/map_to_basic_set.h \ include/isl/map_type.h \ + include/isl/maybe.h \ + include/isl/maybe_ast_expr.h \ + include/isl/maybe_basic_set.h \ + include/isl/maybe_id.h \ + include/isl/maybe_pw_aff.h \ + include/isl/maybe_templ.h \ include/isl/multi.h \ include/isl/obj.h \ include/isl/options.h \ @@ -1076,7 +1088,6 @@ EXTRA_DIST = \ LICENSE \ isl_config_post.h \ basis_reduction_templ.c \ - isl_hmap_templ.c \ isl_list_templ.c \ isl_list_templ.h \ isl_map_lexopt_templ.c \ @@ -1086,13 +1097,18 @@ EXTRA_DIST = \ isl_multi_apply_templ.c \ isl_multi_apply_set.c \ isl_multi_apply_union_set.c \ + isl_multi_cmp.c \ isl_multi_coalesce.c \ isl_multi_floor.c \ isl_multi_gist.c \ + isl_multi_hash.c \ isl_multi_intersect.c \ print_templ.c \ isl_power_templ.c \ + isl_pw_macro.h \ isl_pw_templ.c \ + isl_pw_hash.c \ + isl_pw_union_opt.c \ isl_union_macro.h \ isl_union_templ.c \ isl_union_single.c \ @@ -1336,6 +1352,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_imath.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_input.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_int_sioimath.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_local.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_local_space.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_lp.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/isl_map.Plo@am__quote@ diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf Binary files differindex 7dac86b2b3c..3ab0447bd62 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 6bfc318f1bb..c5e23797c4a 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -590,7 +590,12 @@ In particular, the C<isl_bool> type has three possible values: C<isl_bool_true> (a positive integer value), indicating I<true> or I<yes>; C<isl_bool_false> (the integer value zero), indicating I<false> or I<no>; and C<isl_bool_error> (a negative integer value), indicating that something -went wrong. +went wrong. The following function can be used to negate an C<isl_bool>, +where the negation of C<isl_bool_error> is C<isl_bool_error> again. + + #include <isl/val.h> + isl_bool isl_bool_not(isl_bool b); + The C<isl_stat> type has two possible values: C<isl_stat_ok> (the integer value zero), indicating a successful operation; and @@ -2004,7 +2009,8 @@ C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div> for relations. A (basic or union) set or relation can also be constructed from a (union) (piecewise) (multiple) affine expression or a list of affine expressions -(See L</"Functions">). +(See L</"Functions">), provided these affine expressions do not +involve any NaN. __isl_give isl_basic_map *isl_basic_map_from_aff( __isl_take isl_aff *aff); @@ -6102,9 +6108,15 @@ into the first expression. __isl_give isl_basic_set *isl_aff_le_basic_set( __isl_take isl_aff *aff1, __isl_take isl_aff *aff2); + __isl_give isl_set *isl_aff_le_set( + __isl_take isl_aff *aff1, + __isl_take isl_aff *aff2); __isl_give isl_basic_set *isl_aff_ge_basic_set( __isl_take isl_aff *aff1, __isl_take isl_aff *aff2); + __isl_give isl_set *isl_aff_ge_set( + __isl_take isl_aff *aff1, + __isl_take isl_aff *aff2); __isl_give isl_set *isl_pw_aff_eq_set( __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2); @@ -6127,9 +6139,15 @@ into the first expression. __isl_give isl_set *isl_multi_aff_lex_le_set( __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2); + __isl_give isl_set *isl_multi_aff_lex_lt_set( + __isl_take isl_multi_aff *ma1, + __isl_take isl_multi_aff *ma2); __isl_give isl_set *isl_multi_aff_lex_ge_set( __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2); + __isl_give isl_set *isl_multi_aff_lex_gt_set( + __isl_take isl_multi_aff *ma1, + __isl_take isl_multi_aff *ma2); __isl_give isl_set *isl_pw_aff_list_eq_set( __isl_take isl_pw_aff_list *list1, @@ -7307,6 +7325,10 @@ The associative array will be grown automatically as needed. Associative arrays can be inspected using the following functions. #include <isl/id_to_ast_expr.h> + __isl_give isl_maybe_isl_ast_expr + isl_id_to_ast_expr_try_get( + __isl_keep isl_id_to_ast_expr *id2expr, + __isl_keep isl_id *key); isl_bool isl_id_to_ast_expr_has( __isl_keep isl_id_to_ast_expr *id2expr, __isl_keep isl_id *key); @@ -7319,7 +7341,18 @@ Associative arrays can be inspected using the following functions. __isl_take isl_ast_expr *val, void *user), void *user); -They can be modified using the following function. +The function C<isl_id_to_ast_expr_try_get> returns a structure +containing two elements, C<valid> and C<value>. +If there is a value associated to the key, then C<valid> +is set to C<isl_bool_true> and C<value> contains a copy of +the associated value. Otherwise C<value> is C<NULL> and +C<valid> may be C<isl_bool_error> or C<isl_bool_false> depending +on whether some error has occurred or there simply is no associated value. +The function C<isl_id_to_ast_expr_has> returns the C<valid> field +in the structure and +the function C<isl_id_to_ast_expr_get> returns the C<value> field. + +Associative arrays can be modified using the following functions. #include <isl/id_to_ast_expr.h> __isl_give isl_id_to_ast_expr *isl_id_to_ast_expr_set( diff --git a/polly/lib/External/isl/include/isl/aff.h b/polly/lib/External/isl/include/isl/aff.h index a2cac451a52..d2c729766bc 100644 --- a/polly/lib/External/isl/include/isl/aff.h +++ b/polly/lib/External/isl/include/isl/aff.h @@ -25,6 +25,7 @@ __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff); __isl_null isl_aff *isl_aff_free(__isl_take isl_aff *aff); isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff); +uint32_t isl_aff_get_hash(__isl_keep isl_aff *aff); int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type); isl_bool isl_aff_involves_dims(__isl_keep isl_aff *aff, @@ -131,8 +132,12 @@ __isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff); __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1, __isl_take isl_aff *aff2); +__isl_give isl_set *isl_aff_le_set(__isl_take isl_aff *aff1, + __isl_take isl_aff *aff2); __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1, __isl_take isl_aff *aff2); +__isl_give isl_set *isl_aff_ge_set(__isl_take isl_aff *aff1, + __isl_take isl_aff *aff2); __isl_constructor __isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str); @@ -141,6 +146,7 @@ __isl_give isl_printer *isl_printer_print_aff(__isl_take isl_printer *p, void isl_aff_dump(__isl_keep isl_aff *aff); isl_ctx *isl_pw_aff_get_ctx(__isl_keep isl_pw_aff *pwaff); +uint32_t isl_pw_aff_get_hash(__isl_keep isl_pw_aff *pa); __isl_give isl_space *isl_pw_aff_get_domain_space(__isl_keep isl_pw_aff *pwaff); __isl_give isl_space *isl_pw_aff_get_space(__isl_keep isl_pw_aff *pwaff); @@ -367,8 +373,12 @@ __isl_give isl_multi_aff *isl_multi_aff_move_dims(__isl_take isl_multi_aff *ma, enum isl_dim_type dst_type, unsigned dst_pos, enum isl_dim_type src_type, unsigned src_pos, unsigned n); +__isl_give isl_set *isl_multi_aff_lex_lt_set(__isl_take isl_multi_aff *ma1, + __isl_take isl_multi_aff *ma2); __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2); +__isl_give isl_set *isl_multi_aff_lex_gt_set(__isl_take isl_multi_aff *ma1, + __isl_take isl_multi_aff *ma2); __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2); @@ -690,6 +700,8 @@ void isl_union_pw_multi_aff_dump(__isl_keep isl_union_pw_multi_aff *upma); __isl_give char *isl_union_pw_multi_aff_to_str( __isl_keep isl_union_pw_multi_aff *upma); +uint32_t isl_multi_pw_aff_get_hash(__isl_keep isl_multi_pw_aff *mpa); + __isl_give isl_multi_pw_aff *isl_multi_pw_aff_identity( __isl_take isl_space *space); __isl_constructor diff --git a/polly/lib/External/isl/include/isl/ctx.h b/polly/lib/External/isl/include/isl/ctx.h index bd1f00fdaeb..7c925233952 100644 --- a/polly/lib/External/isl/include/isl/ctx.h +++ b/polly/lib/External/isl/include/isl/ctx.h @@ -90,6 +90,7 @@ typedef enum { isl_bool_false = 0, isl_bool_true = 1 } isl_bool; +isl_bool isl_bool_not(isl_bool b); struct isl_ctx; typedef struct isl_ctx isl_ctx; diff --git a/polly/lib/External/isl/include/isl/hmap.h b/polly/lib/External/isl/include/isl/hmap.h index eceee488134..21612217032 100644 --- a/polly/lib/External/isl/include/isl/hmap.h +++ b/polly/lib/External/isl/include/isl/hmap.h @@ -1,4 +1,5 @@ #include <isl/ctx.h> +#include <isl/maybe.h> #include <isl/printer.h> #if defined(__cplusplus) @@ -7,14 +8,8 @@ extern "C" { #define ISL_xCAT(A,B) A ## B #define ISL_CAT(A,B) ISL_xCAT(A,B) -#define ISL_KEY ISL_CAT(isl_,ISL_KEY_BASE) -#define ISL_VAL ISL_CAT(isl_,ISL_VAL_BASE) #define ISL_xFN(TYPE,NAME) TYPE ## _ ## NAME #define ISL_FN(TYPE,NAME) ISL_xFN(TYPE,NAME) -#define ISL_xHMAP(KEY,VAL_BASE) KEY ## _to_ ## VAL_BASE -#define ISL_yHMAP(KEY,VAL_BASE) ISL_xHMAP(KEY,VAL_BASE) -#define ISL_HMAP ISL_yHMAP(ISL_KEY,ISL_VAL_BASE) -#define ISL_HMAP_BASE ISL_yHMAP(ISL_KEY_BASE,ISL_VAL_BASE) struct ISL_HMAP; typedef struct ISL_HMAP ISL_HMAP; @@ -25,6 +20,8 @@ __isl_null ISL_HMAP *ISL_FN(ISL_HMAP,free)(__isl_take ISL_HMAP *hmap); isl_ctx *ISL_FN(ISL_HMAP,get_ctx)(__isl_keep ISL_HMAP *hmap); +__isl_give ISL_MAYBE(ISL_VAL) ISL_FN(ISL_HMAP,try_get)( + __isl_keep ISL_HMAP *hmap, __isl_keep ISL_KEY *key); isl_bool ISL_FN(ISL_HMAP,has)(__isl_keep ISL_HMAP *hmap, __isl_keep ISL_KEY *key); __isl_give ISL_VAL *ISL_FN(ISL_HMAP,get)(__isl_keep ISL_HMAP *hmap, @@ -39,7 +36,7 @@ isl_stat ISL_FN(ISL_HMAP,foreach)(__isl_keep ISL_HMAP *hmap, void *user), void *user); -__isl_give isl_printer *ISL_FN(isl_printer_print,ISL_HMAP_BASE)( +__isl_give isl_printer *ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)( __isl_take isl_printer *p, __isl_keep ISL_HMAP *hmap); void ISL_FN(ISL_HMAP,dump)(__isl_keep ISL_HMAP *hmap); diff --git a/polly/lib/External/isl/include/isl/hmap_templ.c b/polly/lib/External/isl/include/isl/hmap_templ.c new file mode 100644 index 00000000000..3519a8d8dec --- /dev/null +++ b/polly/lib/External/isl/include/isl/hmap_templ.c @@ -0,0 +1,417 @@ +/* + * Copyright 2011 INRIA Saclay + * Copyright 2013 Ecole Normale Superieure + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, + * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, + * 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France + */ + +#include <isl/ctx.h> +#include <isl/hash.h> + +#define ISL_xCAT(A,B) A ## B +#define ISL_CAT(A,B) ISL_xCAT(A,B) +#define ISL_xFN(TYPE,NAME) TYPE ## _ ## NAME +#define ISL_FN(TYPE,NAME) ISL_xFN(TYPE,NAME) +#define ISL_xS(TYPE1,TYPE2,NAME) struct isl_ ## TYPE1 ## _ ## TYPE2 ## _ ## NAME +#define ISL_yS(TYPE1,TYPE2,NAME) ISL_xS(TYPE1,TYPE2,NAME) +#define ISL_S(NAME) ISL_yS(ISL_KEY,ISL_VAL,NAME) + +struct ISL_HMAP { + int ref; + isl_ctx *ctx; + struct isl_hash_table table; +}; + +ISL_S(pair) { + ISL_KEY *key; + ISL_VAL *val; +}; + +__isl_give ISL_HMAP *ISL_FN(ISL_HMAP,alloc)(isl_ctx *ctx, int min_size) +{ + ISL_HMAP *hmap; + + hmap = isl_calloc_type(ctx, ISL_HMAP); + if (!hmap) + return NULL; + + hmap->ctx = ctx; + isl_ctx_ref(ctx); + hmap->ref = 1; + + if (isl_hash_table_init(ctx, &hmap->table, min_size) < 0) + return ISL_FN(ISL_HMAP,free)(hmap); + + return hmap; +} + +static isl_stat free_pair(void **entry, void *user) +{ + ISL_S(pair) *pair = *entry; + ISL_FN(ISL_KEY,free)(pair->key); + ISL_FN(ISL_VAL,free)(pair->val); + free(pair); + *entry = NULL; + return isl_stat_ok; +} + +__isl_null ISL_HMAP *ISL_FN(ISL_HMAP,free)(__isl_take ISL_HMAP *hmap) +{ + if (!hmap) + return NULL; + if (--hmap->ref > 0) + return NULL; + isl_hash_table_foreach(hmap->ctx, &hmap->table, &free_pair, NULL); + isl_hash_table_clear(&hmap->table); + isl_ctx_deref(hmap->ctx); + free(hmap); + return NULL; +} + +isl_ctx *ISL_FN(ISL_HMAP,get_ctx)(__isl_keep ISL_HMAP *hmap) +{ + return hmap ? hmap->ctx : NULL; +} + +/* Add a mapping from "key" to "val" to the associative array + * pointed to by user. + */ +static isl_stat add_key_val(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val, + void *user) +{ + ISL_HMAP **hmap = (ISL_HMAP **) user; + + *hmap = ISL_FN(ISL_HMAP,set)(*hmap, key, val); + + if (!*hmap) + return isl_stat_error; + + return isl_stat_ok; +} + +__isl_give ISL_HMAP *ISL_FN(ISL_HMAP,dup)(__isl_keep ISL_HMAP *hmap) +{ + ISL_HMAP *dup; + + if (!hmap) + return NULL; + + dup = ISL_FN(ISL_HMAP,alloc)(hmap->ctx, hmap->table.n); + if (ISL_FN(ISL_HMAP,foreach)(hmap, &add_key_val, &dup) < 0) + return ISL_FN(ISL_HMAP,free)(dup); + + return dup; +} + +__isl_give ISL_HMAP *ISL_FN(ISL_HMAP,cow)(__isl_take ISL_HMAP *hmap) +{ + if (!hmap) + return NULL; + + if (hmap->ref == 1) + return hmap; + hmap->ref--; + return ISL_FN(ISL_HMAP,dup)(hmap); +} + +__isl_give ISL_HMAP *ISL_FN(ISL_HMAP,copy)(__isl_keep ISL_HMAP *hmap) +{ + if (!hmap) + return NULL; + + hmap->ref++; + return hmap; +} + +static int has_key(const void *entry, const void *c_key) +{ + const ISL_S(pair) *pair = entry; + ISL_KEY *key = (ISL_KEY *) c_key; + + return ISL_KEY_IS_EQUAL(pair->key, key); +} + +/* If "hmap" contains a value associated to "key", then return + * (isl_bool_true, copy of value). + * Otherwise, return + * (isl_bool_false, NULL). + * If an error occurs, then return + * (isl_bool_error, NULL). + */ +__isl_give ISL_MAYBE(ISL_VAL) ISL_FN(ISL_HMAP,try_get)( + __isl_keep ISL_HMAP *hmap, __isl_keep ISL_KEY *key) +{ + struct isl_hash_table_entry *entry; + ISL_S(pair) *pair; + uint32_t hash; + ISL_MAYBE(ISL_VAL) res = { isl_bool_false, NULL }; + + if (!hmap || !key) + goto error; + + hash = ISL_FN(ISL_KEY,get_hash)(key); + entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, + &has_key, key, 0); + + if (!entry) + return res; + + pair = entry->data; + + res.valid = isl_bool_true; + res.value = ISL_FN(ISL_VAL,copy)(pair->val); + if (!res.value) + res.valid = isl_bool_error; + return res; +error: + res.valid = isl_bool_error; + res.value = NULL; + return res; +} + +/* If "hmap" contains a value associated to "key", then return + * isl_bool_true. Otherwise, return isl_bool_false. + * Return isl_bool_error on error. + */ +isl_bool ISL_FN(ISL_HMAP,has)(__isl_keep ISL_HMAP *hmap, + __isl_keep ISL_KEY *key) +{ + ISL_MAYBE(ISL_VAL) res; + + res = ISL_FN(ISL_HMAP,try_get)(hmap, key); + ISL_FN(ISL_VAL,free)(res.value); + + return res.valid; +} + +/* If "hmap" contains a value associated to "key", then return + * a copy of that value. Otherwise, return NULL. + * Return NULL on error. + */ +__isl_give ISL_VAL *ISL_FN(ISL_HMAP,get)(__isl_keep ISL_HMAP *hmap, + __isl_take ISL_KEY *key) +{ + ISL_VAL *res; + + res = ISL_FN(ISL_HMAP,try_get)(hmap, key).value; + ISL_FN(ISL_KEY,free)(key); + return res; +} + +/* Remove the mapping between "key" and its associated value (if any) + * from "hmap". + * + * If "key" is not mapped to anything, then we leave "hmap" untouched" + */ +__isl_give ISL_HMAP *ISL_FN(ISL_HMAP,drop)(__isl_take ISL_HMAP *hmap, + __isl_take ISL_KEY *key) +{ + struct isl_hash_table_entry *entry; + ISL_S(pair) *pair; + uint32_t hash; + + if (!hmap || !key) + goto error; + + hash = ISL_FN(ISL_KEY,get_hash)(key); + entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, + &has_key, key, 0); + if (!entry) { + ISL_FN(ISL_KEY,free)(key); + return hmap; + } + + hmap = ISL_FN(ISL_HMAP,cow)(hmap); + if (!hmap) + goto error; + entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, + &has_key, key, 0); + ISL_FN(ISL_KEY,free)(key); + + if (!entry) + isl_die(hmap->ctx, isl_error_internal, + "missing entry" , goto error); + + pair = entry->data; + isl_hash_table_remove(hmap->ctx, &hmap->table, entry); + ISL_FN(ISL_KEY,free)(pair->key); + ISL_FN(ISL_VAL,free)(pair->val); + free(pair); + + return hmap; +error: + ISL_FN(ISL_KEY,free)(key); + ISL_FN(ISL_HMAP,free)(hmap); + return NULL; +} + +/* Add a mapping from "key" to "val" to "hmap". + * If "key" was already mapped to something else, then that mapping + * is replaced. + * If key happened to be mapped to "val" already, then we leave + * "hmap" untouched. + */ +__isl_give ISL_HMAP *ISL_FN(ISL_HMAP,set)(__isl_take ISL_HMAP *hmap, + __isl_take ISL_KEY *key, __isl_take ISL_VAL *val) +{ + struct isl_hash_table_entry *entry; + ISL_S(pair) *pair; + uint32_t hash; + + if (!hmap || !key || !val) + goto error; + + hash = ISL_FN(ISL_KEY,get_hash)(key); + entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, + &has_key, key, 0); + if (entry) { + int equal; + pair = entry->data; + equal = ISL_VAL_IS_EQUAL(pair->val, val); + if (equal < 0) + goto error; + if (equal) { + ISL_FN(ISL_KEY,free)(key); + ISL_FN(ISL_VAL,free)(val); + return hmap; + } + } + + hmap = ISL_FN(ISL_HMAP,cow)(hmap); + if (!hmap) + goto error; + + entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, + &has_key, key, 1); + + if (!entry) + goto error; + + if (entry->data) { + pair = entry->data; + ISL_FN(ISL_VAL,free)(pair->val); + pair->val = val; + ISL_FN(ISL_KEY,free)(key); + return hmap; + } + + pair = isl_alloc_type(hmap->ctx, ISL_S(pair)); + if (!pair) + goto error; + + entry->data = pair; + pair->key = key; + pair->val = val; + return hmap; +error: + ISL_FN(ISL_KEY,free)(key); + ISL_FN(ISL_VAL,free)(val); + return ISL_FN(ISL_HMAP,free)(hmap); +} + +/* Internal data structure for isl_map_to_basic_set_foreach. + * + * fn is the function that should be called on each entry. + * user is the user-specified final argument to fn. + */ +ISL_S(foreach_data) { + isl_stat (*fn)(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val, + void *user); + void *user; +}; + +/* Call data->fn on a copy of the key and value in *entry. + */ +static isl_stat call_on_copy(void **entry, void *user) +{ + ISL_S(pair) *pair = *entry; + ISL_S(foreach_data) *data = (ISL_S(foreach_data) *) user; + + return data->fn(ISL_FN(ISL_KEY,copy)(pair->key), + ISL_FN(ISL_VAL,copy)(pair->val), data->user); +} + +/* Call "fn" on each pair of key and value in "hmap". + */ +isl_stat ISL_FN(ISL_HMAP,foreach)(__isl_keep ISL_HMAP *hmap, + isl_stat (*fn)(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val, + void *user), + void *user) +{ + ISL_S(foreach_data) data = { fn, user }; + + if (!hmap) + return isl_stat_error; + + return isl_hash_table_foreach(hmap->ctx, &hmap->table, + &call_on_copy, &data); +} + +/* Internal data structure for print_pair. + * + * p is the printer on which the associative array is being printed. + * first is set if the current key-value pair is the first to be printed. + */ +ISL_S(print_data) { + isl_printer *p; + int first; +}; + +/* Print the given key-value pair to data->p. + */ +static isl_stat print_pair(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val, + void *user) +{ + ISL_S(print_data) *data = user; + + if (!data->first) + data->p = isl_printer_print_str(data->p, ", "); + data->p = ISL_KEY_PRINT(data->p, key); + data->p = isl_printer_print_str(data->p, ": "); + data->p = ISL_VAL_PRINT(data->p, val); + data->first = 0; + + ISL_FN(ISL_KEY,free)(key); + ISL_FN(ISL_VAL,free)(val); + return isl_stat_ok; +} + +/* Print the associative array to "p". + */ +__isl_give isl_printer *ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)( + __isl_take isl_printer *p, __isl_keep ISL_HMAP *hmap) +{ + ISL_S(print_data) data; + + if (!p || !hmap) + return isl_printer_free(p); + + p = isl_printer_print_str(p, "{"); + data.p = p; + data.first = 1; + if (ISL_FN(ISL_HMAP,foreach)(hmap, &print_pair, &data) < 0) + data.p = isl_printer_free(data.p); + p = data.p; + p = isl_printer_print_str(p, "}"); + + return p; +} + +void ISL_FN(ISL_HMAP,dump)(__isl_keep ISL_HMAP *hmap) +{ + isl_printer *printer; + + if (!hmap) + return; + + printer = isl_printer_to_file(ISL_FN(ISL_HMAP,get_ctx)(hmap), stderr); + printer = ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(printer, hmap); + printer = isl_printer_end_line(printer); + + isl_printer_free(printer); +} diff --git a/polly/lib/External/isl/include/isl/id_to_ast_expr.h b/polly/lib/External/isl/include/isl/id_to_ast_expr.h index 958360c3b63..a160a9fc968 100644 --- a/polly/lib/External/isl/include/isl/id_to_ast_expr.h +++ b/polly/lib/External/isl/include/isl/id_to_ast_expr.h @@ -3,11 +3,16 @@ #include <isl/id.h> #include <isl/ast_type.h> +#include <isl/maybe_ast_expr.h> -#define ISL_KEY_BASE id -#define ISL_VAL_BASE ast_expr +#define ISL_KEY isl_id +#define ISL_VAL isl_ast_expr +#define ISL_HMAP_SUFFIX id_to_ast_expr +#define ISL_HMAP isl_id_to_ast_expr #include <isl/hmap.h> -#undef ISL_KEY_BASE -#undef ISL_VAL_BASE +#undef ISL_KEY +#undef ISL_VAL +#undef ISL_HMAP_SUFFIX +#undef ISL_HMAP #endif diff --git a/polly/lib/External/isl/include/isl/id_to_id.h b/polly/lib/External/isl/include/isl/id_to_id.h index 8e763de6ffd..26bbc598f43 100644 --- a/polly/lib/External/isl/include/isl/id_to_id.h +++ b/polly/lib/External/isl/include/isl/id_to_id.h @@ -2,11 +2,16 @@ #define ISL_ID_TO_ID_H #include <isl/id.h> +#include <isl/maybe_id.h> -#define ISL_KEY_BASE id -#define ISL_VAL_BASE id +#define ISL_KEY isl_id +#define ISL_VAL isl_id +#define ISL_HMAP_SUFFIX id_to_id +#define ISL_HMAP isl_id_to_id #include <isl/hmap.h> -#undef ISL_KEY_BASE -#undef ISL_VAL_BASE +#undef ISL_KEY +#undef ISL_VAL +#undef ISL_HMAP_SUFFIX +#undef ISL_HMAP #endif diff --git a/polly/lib/External/isl/include/isl/id_to_pw_aff.h b/polly/lib/External/isl/include/isl/id_to_pw_aff.h index e54fefb50b8..081cc843419 100644 --- a/polly/lib/External/isl/include/isl/id_to_pw_aff.h +++ b/polly/lib/External/isl/include/isl/id_to_pw_aff.h @@ -3,11 +3,16 @@ #include <isl/id.h> #include <isl/aff_type.h> +#include <isl/maybe_pw_aff.h> -#define ISL_KEY_BASE id -#define ISL_VAL_BASE pw_aff +#define ISL_KEY isl_id +#define ISL_VAL isl_pw_aff +#define ISL_HMAP_SUFFIX id_to_pw_aff +#define ISL_HMAP isl_id_to_pw_aff #include <isl/hmap.h> -#undef ISL_KEY_BASE -#undef ISL_VAL_BASE +#undef ISL_KEY +#undef ISL_VAL +#undef ISL_HMAP_SUFFIX +#undef ISL_HMAP #endif diff --git a/polly/lib/External/isl/include/isl/ilp.h b/polly/lib/External/isl/include/isl/ilp.h index c177014fda5..dcda1dcb17c 100644 --- a/polly/lib/External/isl/include/isl/ilp.h +++ b/polly/lib/External/isl/include/isl/ilp.h @@ -21,8 +21,10 @@ extern "C" { __isl_give isl_val *isl_basic_set_max_val(__isl_keep isl_basic_set *bset, __isl_keep isl_aff *obj); +__isl_export __isl_give isl_val *isl_set_min_val(__isl_keep isl_set *set, __isl_keep isl_aff *obj); +__isl_export __isl_give isl_val *isl_set_max_val(__isl_keep isl_set *set, __isl_keep isl_aff *obj); diff --git a/polly/lib/External/isl/include/isl/map.h b/polly/lib/External/isl/include/isl/map.h index edcb021aa44..fdbac8ccfee 100644 --- a/polly/lib/External/isl/include/isl/map.h +++ b/polly/lib/External/isl/include/isl/map.h @@ -133,6 +133,7 @@ __isl_give isl_basic_map *isl_basic_map_remove_redundancies( __isl_take isl_basic_map *bmap); __isl_give isl_map *isl_map_remove_redundancies(__isl_take isl_map *map); __isl_give isl_basic_map *isl_map_simple_hull(__isl_take isl_map *map); +__isl_export __isl_give isl_basic_map *isl_map_unshifted_simple_hull( __isl_take isl_map *map); __isl_give isl_basic_map *isl_map_unshifted_simple_hull_from_map_list( diff --git a/polly/lib/External/isl/include/isl/map_to_basic_set.h b/polly/lib/External/isl/include/isl/map_to_basic_set.h index 7df8ee3e0a9..80e9ab5bed2 100644 --- a/polly/lib/External/isl/include/isl/map_to_basic_set.h +++ b/polly/lib/External/isl/include/isl/map_to_basic_set.h @@ -3,11 +3,16 @@ #include <isl/set_type.h> #include <isl/map_type.h> +#include <isl/maybe_basic_set.h> -#define ISL_KEY_BASE map -#define ISL_VAL_BASE basic_set +#define ISL_KEY isl_map +#define ISL_VAL isl_basic_set +#define ISL_HMAP_SUFFIX map_to_basic_set +#define ISL_HMAP isl_map_to_basic_set #include <isl/hmap.h> -#undef ISL_KEY_BASE -#undef ISL_VAL_BASE +#undef ISL_KEY +#undef ISL_VAL +#undef ISL_HMAP_SUFFIX +#undef ISL_HMAP #endif diff --git a/polly/lib/External/isl/include/isl/set.h b/polly/lib/External/isl/include/isl/set.h index 6f9d2c7fdf7..20fb904ae26 100644 --- a/polly/lib/External/isl/include/isl/set.h +++ b/polly/lib/External/isl/include/isl/set.h @@ -251,6 +251,7 @@ __isl_give isl_basic_set *isl_set_convex_hull(__isl_take isl_set *set); __isl_export __isl_give isl_basic_set *isl_set_polyhedral_hull(__isl_take isl_set *set); __isl_give isl_basic_set *isl_set_simple_hull(__isl_take isl_set *set); +__isl_export __isl_give isl_basic_set *isl_set_unshifted_simple_hull( __isl_take isl_set *set); __isl_give isl_basic_set *isl_set_unshifted_simple_hull_from_set_list( diff --git a/polly/lib/External/isl/include/isl/union_map.h b/polly/lib/External/isl/include/isl/union_map.h index b81caef83b9..fc867a4f4f9 100644 --- a/polly/lib/External/isl/include/isl/union_map.h +++ b/polly/lib/External/isl/include/isl/union_map.h @@ -217,6 +217,8 @@ __isl_export isl_bool isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1, __isl_keep isl_union_map *umap2); +uint32_t isl_union_map_get_hash(__isl_keep isl_union_map *umap); + int isl_union_map_n_map(__isl_keep isl_union_map *umap); __isl_export isl_stat isl_union_map_foreach_map(__isl_keep isl_union_map *umap, diff --git a/polly/lib/External/isl/include/isl/union_set.h b/polly/lib/External/isl/include/isl/union_set.h index 65b3a0926c6..b0694799811 100644 --- a/polly/lib/External/isl/include/isl/union_set.h +++ b/polly/lib/External/isl/include/isl/union_set.h @@ -108,6 +108,8 @@ __isl_export isl_bool isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1, __isl_keep isl_union_set *uset2); +uint32_t isl_union_set_get_hash(__isl_keep isl_union_set *uset); + int isl_union_set_n_set(__isl_keep isl_union_set *uset); __isl_export isl_stat isl_union_set_foreach_set(__isl_keep isl_union_set *uset, diff --git a/polly/lib/External/isl/include/isl/val.h b/polly/lib/External/isl/include/isl/val.h index 5595989ac11..f41226ffe0a 100644 --- a/polly/lib/External/isl/include/isl/val.h +++ b/polly/lib/External/isl/include/isl/val.h @@ -45,6 +45,7 @@ __isl_give isl_val *isl_val_copy(__isl_keep isl_val *v); __isl_null isl_val *isl_val_free(__isl_take isl_val *v); isl_ctx *isl_val_get_ctx(__isl_keep isl_val *val); +uint32_t isl_val_get_hash(__isl_keep isl_val *val); long isl_val_get_num_si(__isl_keep isl_val *v); long isl_val_get_den_si(__isl_keep isl_val *v); __isl_give isl_val *isl_val_get_den_val(__isl_keep isl_val *v); diff --git a/polly/lib/External/isl/interface/all.h b/polly/lib/External/isl/interface/all.h index 1c7d1064cee..ebd2a5471aa 100644 --- a/polly/lib/External/isl/interface/all.h +++ b/polly/lib/External/isl/interface/all.h @@ -2,6 +2,7 @@ #include <isl/aff.h> #include <isl/set.h> #include <isl/map.h> +#include <isl/ilp.h> #include <isl/union_set.h> #include <isl/union_map.h> #include <isl/flow.h> diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c index a060e3d3e75..4523b4c0107 100644 --- a/polly/lib/External/isl/isl_aff.c +++ b/polly/lib/External/isl/isl_aff.c @@ -275,6 +275,24 @@ isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff) return aff ? isl_local_space_get_ctx(aff->ls) : NULL; } +/* Return a hash value that digests "aff". + */ +uint32_t isl_aff_get_hash(__isl_keep isl_aff *aff) +{ + uint32_t hash, ls_hash, v_hash; + + if (!aff) + return 0; + + hash = isl_hash_init(); + ls_hash = isl_local_space_get_hash(aff->ls); + isl_hash_hash(hash, ls_hash); + v_hash = isl_vec_get_hash(aff->v); + isl_hash_hash(hash, v_hash); + + return hash; +} + /* Externally, an isl_aff has a map space, but internally, the * ls field corresponds to the domain of that space. */ @@ -2299,6 +2317,15 @@ __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1, return isl_aff_nonneg_basic_set(aff1); } +/* Return a set containing those elements in the shared space + * of aff1 and aff2 where aff1 is greater than or equal to aff2. + */ +__isl_give isl_set *isl_aff_ge_set(__isl_take isl_aff *aff1, + __isl_take isl_aff *aff2) +{ + return isl_set_from_basic_set(isl_aff_ge_basic_set(aff1, aff2)); +} + /* Return a basic set containing those elements in the shared space * of aff1 and aff2 where aff1 is smaller than or equal to aff2. */ @@ -2308,6 +2335,15 @@ __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1, return isl_aff_ge_basic_set(aff2, aff1); } +/* Return a set containing those elements in the shared space + * of aff1 and aff2 where aff1 is smaller than or equal to aff2. + */ +__isl_give isl_set *isl_aff_le_set(__isl_take isl_aff *aff1, + __isl_take isl_aff *aff2) +{ + return isl_aff_ge_set(aff2, aff1); +} + __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom, __isl_take isl_aff *aff1, __isl_take isl_aff *aff2) { @@ -2570,6 +2606,8 @@ __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff) #define NO_MORPH #include <isl_pw_templ.c> +#include <isl_pw_hash.c> +#include <isl_pw_union_opt.c> #undef UNION #define UNION isl_union_pw_aff @@ -2631,89 +2669,6 @@ error: /* Compute a piecewise quasi-affine expression with a domain that * is the union of those of pwaff1 and pwaff2 and such that on each - * cell, the quasi-affine expression is the better (according to cmp) - * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2 - * is defined on a given cell, then the associated expression - * is the defined one. - */ -static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1, - __isl_take isl_pw_aff *pwaff2, - __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1, - __isl_take isl_aff *aff2)) -{ - int i, j, n; - isl_pw_aff *res; - isl_ctx *ctx; - isl_set *set; - - if (!pwaff1 || !pwaff2) - goto error; - - ctx = isl_space_get_ctx(pwaff1->dim); - if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim)) - isl_die(ctx, isl_error_invalid, - "arguments should live in same space", goto error); - - if (isl_pw_aff_is_empty(pwaff1)) { - isl_pw_aff_free(pwaff1); - return pwaff2; - } - - if (isl_pw_aff_is_empty(pwaff2)) { - isl_pw_aff_free(pwaff2); - return pwaff1; - } - - n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1); - res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n); - - for (i = 0; i < pwaff1->n; ++i) { - set = isl_set_copy(pwaff1->p[i].set); - for (j = 0; j < pwaff2->n; ++j) { - struct isl_set *common; - isl_set *better; - - common = isl_set_intersect( - isl_set_copy(pwaff1->p[i].set), - isl_set_copy(pwaff2->p[j].set)); - better = isl_set_from_basic_set(cmp( - isl_aff_copy(pwaff2->p[j].aff), - isl_aff_copy(pwaff1->p[i].aff))); - better = isl_set_intersect(common, better); - if (isl_set_plain_is_empty(better)) { - isl_set_free(better); - continue; - } - set = isl_set_subtract(set, isl_set_copy(better)); - - res = isl_pw_aff_add_piece(res, better, - isl_aff_copy(pwaff2->p[j].aff)); - } - res = isl_pw_aff_add_piece(res, set, - isl_aff_copy(pwaff1->p[i].aff)); - } - - for (j = 0; j < pwaff2->n; ++j) { - set = isl_set_copy(pwaff2->p[j].set); - for (i = 0; i < pwaff1->n; ++i) - set = isl_set_subtract(set, - isl_set_copy(pwaff1->p[i].set)); - res = isl_pw_aff_add_piece(res, set, - isl_aff_copy(pwaff2->p[j].aff)); - } - - isl_pw_aff_free(pwaff1); - isl_pw_aff_free(pwaff2); - - return res; -error: - isl_pw_aff_free(pwaff1); - isl_pw_aff_free(pwaff2); - return NULL; -} - -/* Compute a piecewise quasi-affine expression with a domain that - * is the union of those of pwaff1 and pwaff2 and such that on each * cell, the quasi-affine expression is the maximum of those of pwaff1 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given * cell, then the associated expression is the defined one. @@ -2721,7 +2676,7 @@ error: static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2) { - return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set); + return isl_pw_aff_union_opt_cmp(pwaff1, pwaff2, &isl_aff_ge_set); } __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1, @@ -2740,7 +2695,7 @@ __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1, static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2) { - return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set); + return isl_pw_aff_union_opt_cmp(pwaff1, pwaff2, &isl_aff_le_set); } __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1, @@ -3272,11 +3227,15 @@ static __isl_give isl_pw_aff *isl_pw_aff_select( * If "cond" involves and NaN, then we conservatively return a NaN * on its entire domain. In principle, we could consider the pieces * where it is NaN separately from those where it is not. + * + * If "pwaff_true" and "pwaff_false" are obviously equal to each other, + * then only use the domain of "cond" to restrict the domain. */ __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond, __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false) { isl_set *cond_true, *cond_false; + isl_bool equal; if (!cond) goto error; @@ -3289,6 +3248,21 @@ __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond, return isl_pw_aff_nan_on_domain(ls); } + pwaff_true = isl_pw_aff_align_params(pwaff_true, + isl_pw_aff_get_space(pwaff_false)); + pwaff_false = isl_pw_aff_align_params(pwaff_false, + isl_pw_aff_get_space(pwaff_true)); + equal = isl_pw_aff_plain_is_equal(pwaff_true, pwaff_false); + if (equal < 0) + goto error; + if (equal) { + isl_set *dom; + + dom = isl_set_coalesce(isl_pw_aff_domain(cond)); + isl_pw_aff_free(pwaff_false); + return isl_pw_aff_intersect_domain(pwaff_true, dom); + } + cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond)); cond_false = isl_pw_aff_zero_set(cond); return isl_pw_aff_select(cond_true, pwaff_true, @@ -3760,6 +3734,7 @@ error: #include <isl_multi_templ.c> #include <isl_multi_apply_set.c> +#include <isl_multi_cmp.c> #include <isl_multi_floor.c> #include <isl_multi_gist.c> @@ -4037,11 +4012,21 @@ __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1, } /* Return the set of domain elements where "ma1" is lexicographically - * greater than or equal to "ma2". + * smaller than "ma2". */ -__isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, +__isl_give isl_set *isl_multi_aff_lex_lt_set(__isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2) { + return isl_multi_aff_lex_gt_set(ma2, ma1); +} + +/* Return the set of domain elements where "ma1" and "ma2" + * satisfy "order". + */ +static __isl_give isl_set *isl_multi_aff_order_set( + __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2, + __isl_give isl_map *order(__isl_take isl_space *set_space)) +{ isl_space *space; isl_map *map1, *map2; isl_map *map, *ge; @@ -4051,12 +4036,30 @@ __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, map = isl_map_range_product(map1, map2); space = isl_space_range(isl_map_get_space(map)); space = isl_space_domain(isl_space_unwrap(space)); - ge = isl_map_lex_ge(space); + ge = order(space); map = isl_map_intersect_range(map, isl_map_wrap(ge)); return isl_map_domain(map); } +/* Return the set of domain elements where "ma1" is lexicographically + * greater than or equal to "ma2". + */ +__isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, + __isl_take isl_multi_aff *ma2) +{ + return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_ge); +} + +/* Return the set of domain elements where "ma1" is lexicographically + * greater than "ma2". + */ +__isl_give isl_set *isl_multi_aff_lex_gt_set(__isl_take isl_multi_aff *ma1, + __isl_take isl_multi_aff *ma2) +{ + return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_gt); +} + #undef PW #define PW isl_pw_multi_aff #undef EL @@ -4081,6 +4084,7 @@ __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, #define NO_MORPH #include <isl_pw_templ.c> +#include <isl_pw_union_opt.c> #undef NO_SUB @@ -4094,121 +4098,12 @@ __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, #include <isl_union_multi.c> #include <isl_union_neg.c> -/* Given a function "cmp" that returns the set of elements where - * "ma1" is "better" than "ma2", return the intersection of this - * set with "dom1" and "dom2". - */ -static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1, - __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1, - __isl_keep isl_multi_aff *ma2, - __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1, - __isl_take isl_multi_aff *ma2)) -{ - isl_set *common; - isl_set *better; - int is_empty; - - common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2)); - is_empty = isl_set_plain_is_empty(common); - if (is_empty >= 0 && is_empty) - return common; - if (is_empty < 0) - return isl_set_free(common); - better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2)); - better = isl_set_intersect(common, better); - - return better; -} - -/* Given a function "cmp" that returns the set of elements where - * "ma1" is "better" than "ma2", return a piecewise multi affine - * expression defined on the union of the definition domains - * of "pma1" and "pma2" that maps to the "best" of "pma1" and - * "pma2" on each cell. If only one of the two input functions - * is defined on a given cell, then it is considered the best. - */ -static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt( - __isl_take isl_pw_multi_aff *pma1, - __isl_take isl_pw_multi_aff *pma2, - __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1, - __isl_take isl_multi_aff *ma2)) -{ - int i, j, n; - isl_pw_multi_aff *res = NULL; - isl_ctx *ctx; - isl_set *set = NULL; - - if (!pma1 || !pma2) - goto error; - - ctx = isl_space_get_ctx(pma1->dim); - if (!isl_space_is_equal(pma1->dim, pma2->dim)) - isl_die(ctx, isl_error_invalid, - "arguments should live in the same space", goto error); - - if (isl_pw_multi_aff_is_empty(pma1)) { - isl_pw_multi_aff_free(pma1); - return pma2; - } - - if (isl_pw_multi_aff_is_empty(pma2)) { - isl_pw_multi_aff_free(pma2); - return pma1; - } - - n = 2 * (pma1->n + 1) * (pma2->n + 1); - res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n); - - for (i = 0; i < pma1->n; ++i) { - set = isl_set_copy(pma1->p[i].set); - for (j = 0; j < pma2->n; ++j) { - isl_set *better; - int is_empty; - - better = shared_and_better(pma2->p[j].set, - pma1->p[i].set, pma2->p[j].maff, - pma1->p[i].maff, cmp); - is_empty = isl_set_plain_is_empty(better); - if (is_empty < 0 || is_empty) { - isl_set_free(better); - if (is_empty < 0) - goto error; - continue; - } - set = isl_set_subtract(set, isl_set_copy(better)); - - res = isl_pw_multi_aff_add_piece(res, better, - isl_multi_aff_copy(pma2->p[j].maff)); - } - res = isl_pw_multi_aff_add_piece(res, set, - isl_multi_aff_copy(pma1->p[i].maff)); - } - - for (j = 0; j < pma2->n; ++j) { - set = isl_set_copy(pma2->p[j].set); - for (i = 0; i < pma1->n; ++i) - set = isl_set_subtract(set, - isl_set_copy(pma1->p[i].set)); - res = isl_pw_multi_aff_add_piece(res, set, - isl_multi_aff_copy(pma2->p[j].maff)); - } - - isl_pw_multi_aff_free(pma1); - isl_pw_multi_aff_free(pma2); - - return res; -error: - isl_pw_multi_aff_free(pma1); - isl_pw_multi_aff_free(pma2); - isl_set_free(set); - return isl_pw_multi_aff_free(res); -} - static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax( __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) { - return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set); + return isl_pw_multi_aff_union_opt_cmp(pma1, pma2, + &isl_multi_aff_lex_ge_set); } /* Given two piecewise multi affine expressions, return a piecewise @@ -4229,7 +4124,8 @@ static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin( __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2) { - return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set); + return isl_pw_multi_aff_union_opt_cmp(pma1, pma2, + &isl_multi_aff_lex_le_set); } /* Given two piecewise multi affine expressions, return a piecewise @@ -6171,6 +6067,7 @@ error: #include <isl_multi_apply_set.c> #include <isl_multi_coalesce.c> #include <isl_multi_gist.c> +#include <isl_multi_hash.c> #include <isl_multi_intersect.c> /* Scale the elements of "pma" by the corresponding elements of "mv". @@ -6472,10 +6369,15 @@ __isl_give isl_multi_pw_aff *isl_multi_pw_aff_from_pw_multi_aff( * * We first check if they are obviously equal. * If not, we convert them to maps and check if those are equal. + * + * If "pa1" or "pa2" contain any NaNs, then they are considered + * not to be the same. A NaN is not equal to anything, not even + * to another NaN. */ int isl_pw_aff_is_equal(__isl_keep isl_pw_aff *pa1, __isl_keep isl_pw_aff *pa2) { int equal; + isl_bool has_nan; isl_map *map1, *map2; if (!pa1 || !pa2) @@ -6484,6 +6386,13 @@ int isl_pw_aff_is_equal(__isl_keep isl_pw_aff *pa1, __isl_keep isl_pw_aff *pa2) equal = isl_pw_aff_plain_is_equal(pa1, pa2); if (equal < 0 || equal) return equal; + has_nan = isl_pw_aff_involves_nan(pa1); + if (has_nan >= 0 && !has_nan) + has_nan = isl_pw_aff_involves_nan(pa2); + if (has_nan < 0) + return -1; + if (has_nan) + return 0; map1 = map_from_pw_aff(isl_pw_aff_copy(pa1)); map2 = map_from_pw_aff(isl_pw_aff_copy(pa2)); @@ -8302,14 +8211,13 @@ isl_union_pw_multi_aff_from_multi_union_pw_aff( if (!mupa) return NULL; - space = isl_multi_union_pw_aff_get_space(mupa); - n = isl_multi_union_pw_aff_dim(mupa, isl_dim_set); if (n == 0) isl_die(isl_multi_union_pw_aff_get_ctx(mupa), isl_error_invalid, "cannot determine domain of zero-dimensional " "isl_multi_union_pw_aff", goto error); + space = isl_multi_union_pw_aff_get_space(mupa); upa = isl_multi_union_pw_aff_get_union_pw_aff(mupa, 0); upma = isl_union_pw_multi_aff_from_union_pw_aff(upa); diff --git a/polly/lib/External/isl/isl_aff_private.h b/polly/lib/External/isl/isl_aff_private.h index 2214942736b..fc6555ffbd9 100644 --- a/polly/lib/External/isl/isl_aff_private.h +++ b/polly/lib/External/isl/isl_aff_private.h @@ -79,6 +79,8 @@ __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff, enum isl_dim_type type, int pos, isl_int v); __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v); +int isl_aff_plain_cmp(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2); + __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff); __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff, diff --git a/polly/lib/External/isl/isl_ast.c b/polly/lib/External/isl/isl_ast.c index be802a3af32..baa0a23c560 100644 --- a/polly/lib/External/isl/isl_ast.c +++ b/polly/lib/External/isl/isl_ast.c @@ -733,7 +733,7 @@ __isl_give isl_ast_expr *isl_ast_expr_substitute_ids( __isl_take isl_ast_expr *expr, __isl_take isl_id_to_ast_expr *id2expr) { int i; - isl_id *id; + isl_maybe_isl_ast_expr m; if (!expr || !id2expr) goto error; @@ -742,11 +742,13 @@ __isl_give isl_ast_expr *isl_ast_expr_substitute_ids( case isl_ast_expr_int: break; case isl_ast_expr_id: - if (!isl_id_to_ast_expr_has(id2expr, expr->u.id)) + m = isl_id_to_ast_expr_try_get(id2expr, expr->u.id); + if (m.valid < 0) + goto error; + if (!m.valid) break; - id = isl_id_copy(expr->u.id); isl_ast_expr_free(expr); - expr = isl_id_to_ast_expr_get(id2expr, id); + expr = m.value; break; case isl_ast_expr_op: for (i = 0; i < expr->u.op.n_arg; ++i) { diff --git a/polly/lib/External/isl/isl_ast_build.c b/polly/lib/External/isl/isl_ast_build.c index ce7272c437c..9418006fd14 100644 --- a/polly/lib/External/isl/isl_ast_build.c +++ b/polly/lib/External/isl/isl_ast_build.c @@ -2033,18 +2033,16 @@ int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build, /* Does the dimension at (internal) position "pos" have a non-trivial stride? */ -int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos) +isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos) { isl_val *v; - int has_stride; + isl_bool has_stride; if (!build) - return -1; + return isl_bool_error; v = isl_vec_get_element_val(build->strides, pos); - if (!v) - return -1; - has_stride = !isl_val_is_one(v); + has_stride = isl_bool_not(isl_val_is_one(v)); isl_val_free(v); return has_stride; diff --git a/polly/lib/External/isl/isl_ast_build_expr.c b/polly/lib/External/isl/isl_ast_build_expr.c index 6445074be4a..49c5638f580 100644 --- a/polly/lib/External/isl/isl_ast_build_expr.c +++ b/polly/lib/External/isl/isl_ast_build_expr.c @@ -15,9 +15,10 @@ #include <isl_ast_build_expr.h> #include <isl_ast_private.h> #include <isl_ast_build_private.h> +#include <isl_sort.h> /* Compute the "opposite" of the (numerator of the) argument of a div - * with denonimator "d". + * with denominator "d". * * In particular, compute * @@ -1592,67 +1593,140 @@ enum isl_from_pw_aff_state { 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. +/* Internal date structure representing a single piece in the input of + * isl_ast_build_expr_from_pw_aff_internal. * * 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. + * single previous subpiece. * 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 + * a sequence of several previous subpieces 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 + * a sequence of several previous subpieces that are equal to the maximum * of the entries in "aff_list" over the union of "set_list" + * + * During the construction of the pieces, "set" is NULL. + * After the construction, "set" is set to the union of the elements + * in "set_list", at which point "set_list" is set to NULL. + */ +struct isl_from_pw_aff_piece { + enum isl_from_pw_aff_state state; + isl_set *set; + isl_set_list *set_list; + isl_aff_list *aff_list; +}; + +/* Internal data structure for isl_ast_build_expr_from_pw_aff_internal. + * + * "build" specifies the domain against which the result is simplified. + * "dom" is the domain of the entire isl_pw_aff. + * + * "n" is the number of pieces constructed already. + * In particular, during the construction of the pieces, "n" points to + * the piece that is being constructed. After the construction of the + * pieces, "n" is set to the total number of pieces. + * "max" is the total number of allocated entries. + * "p" contains the individual pieces. */ struct isl_from_pw_aff_data { isl_ast_build *build; - isl_ast_expr **next; isl_set *dom; - enum isl_from_pw_aff_state state; - isl_set_list *set_list; - isl_aff_list *aff_list; + int n; + int max; + struct isl_from_pw_aff_piece *p; }; -/* Store "set" and "aff" in "data" as a single piece. +/* Initialize "data" based on "build" and "pa". + */ +static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data, + __isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa) +{ + int n; + isl_ctx *ctx; + + ctx = isl_pw_aff_get_ctx(pa); + n = isl_pw_aff_n_piece(pa); + if (n == 0) + isl_die(ctx, isl_error_invalid, + "cannot handle void expression", return isl_stat_error); + data->max = n; + data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n); + if (!data->p) + return isl_stat_error; + data->build = build; + data->dom = isl_pw_aff_domain(isl_pw_aff_copy(pa)); + data->n = 0; + + return isl_stat_ok; +} + +/* Free all memory allocated for "data". + */ +static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data) +{ + int i; + + isl_set_free(data->dom); + if (!data->p) + return; + + for (i = 0; i < data->max; ++i) { + isl_set_free(data->p[i].set); + isl_set_list_free(data->p[i].set_list); + isl_aff_list_free(data->p[i].aff_list); + } + free(data->p); +} + +/* Initialize the current entry of "data" to an unused piece. + */ +static void set_none(struct isl_from_pw_aff_data *data) +{ + data->p[data->n].state = isl_state_none; + data->p[data->n].set_list = NULL; + data->p[data->n].aff_list = NULL; +} + +/* Store "set" and "aff" in the current entry of "data" as a single subpiece. */ 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); + data->p[data->n].state = isl_state_single; + data->p[data->n].set_list = isl_set_list_from_set(set); + data->p[data->n].aff_list = isl_aff_list_from_aff(aff); } -/* Extend "data" with "set" and "aff" as a minimum expression. +/* Extend the current entry of "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); + int n = data->n; + data->p[n].state = isl_state_min; + data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set); + data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff); - if (!data->set_list || !data->aff_list) + if (!data->p[n].set_list || !data->p[n].aff_list) return isl_stat_error; return isl_stat_ok; } -/* Extend "data" with "set" and "aff" as a maximum expression. +/* Extend the current entry of "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); + int n = data->n; + data->p[n].state = isl_state_max; + data->p[n].set_list = isl_set_list_add(data->p[n].set_list, set); + data->p[n].aff_list = isl_aff_list_add(data->p[n].aff_list, aff); - if (!data->set_list || !data->aff_list) + if (!data->p[n].set_list || !data->p[n].aff_list) return isl_stat_error; return isl_stat_ok; } @@ -1701,29 +1775,29 @@ error: return NULL; } -/* Extend the expression in data->next to take into account - * the piece in "data", allowing for a further extension +/* Extend the expression in "next" to take into account + * the piece at position "pos" 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. + * In particular, "next" is set to a select operation that selects + * an isl_ast_expr corresponding to data->aff_list on data->set and + * to an expression that will be filled in by later calls. + * Return a pointer to this location. * Afterwards, the state of "data" is set to isl_state_none. * - * The constraints of data->set_list are added to the generated + * The constraints of data->set 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) +static isl_ast_expr **add_intermediate_piece(struct isl_from_pw_aff_data *data, + int pos, isl_ast_expr **next) { 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; + set = data->p[pos].set; + data->p[pos].set = 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)); @@ -1731,57 +1805,121 @@ static isl_stat build_intermediate_piece(struct isl_from_pw_aff_data *data) 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; + arg = ast_expr_from_aff_list(data->p[pos].aff_list, + data->p[pos].state, build); + data->p[pos].aff_list = NULL; isl_ast_build_free(build); ternary = isl_ast_expr_set_op_arg(ternary, 1, arg); - data->state = isl_state_none; + data->p[pos].state = isl_state_none; if (!ternary) - return isl_stat_error; - - *data->next = ternary; - data->next = &ternary->u.op.args[2]; + return NULL; - return isl_stat_ok; + *next = ternary; + return &ternary->u.op.args[2]; } -/* 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 +/* Extend the expression in "next" to take into account + * the final piece, located at position "pos" in "data". + * In particular, "next" is set to evaluate data->aff_list * and the domain is ignored. + * Return isl_stat_ok on success and isl_stat_error on failure. * - * The constraints of data->set_list are however added to the generated + * The constraints of data->set are however 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_last_piece(struct isl_from_pw_aff_data *data) +static isl_stat add_last_piece(struct isl_from_pw_aff_data *data, + int pos, isl_ast_expr **next) { isl_ast_build *build; - isl_set *set; - if (data->state == isl_state_none) + if (data->p[pos].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; + build = isl_ast_build_restrict_generated(build, data->p[pos].set); + data->p[pos].set = NULL; + *next = ast_expr_from_aff_list(data->p[pos].aff_list, + data->p[pos].state, build); + data->p[pos].aff_list = NULL; isl_ast_build_free(build); - data->state = isl_state_none; - if (!*data->next) + data->p[pos].state = isl_state_none; + if (!*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"? +/* Return -1 if the piece "p1" should be sorted before "p2" + * and 1 if it should be sorted after "p2". + * Return 0 if they do not need to be sorted in a specific order. + * + * Pieces are sorted according to the number of disjuncts + * in their domains. + */ +static int sort_pieces_cmp(const void *p1, const void *p2, void *arg) +{ + const struct isl_from_pw_aff_piece *piece1 = p1; + const struct isl_from_pw_aff_piece *piece2 = p2; + int n1, n2; + + n1 = isl_set_n_basic_set(piece1->set); + n2 = isl_set_n_basic_set(piece2->set); + + return n1 - n2; +} + +/* Construct an isl_ast_expr from the pieces in "data". + * Return the result or NULL on failure. + * + * When this function is called, data->n points to the current piece. + * If this is an effective piece, then first increment data->n such + * that data->n contains the number of pieces. + * The "set_list" fields are subsequently replaced by the corresponding + * "set" fields, after which the pieces are sorted according to + * the number of disjuncts in these "set" fields. + * + * Construct intermediate AST expressions for the initial pieces and + * finish off with the final pieces. + */ +static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data) +{ + int i; + isl_ast_expr *res = NULL; + isl_ast_expr **next = &res; + + if (data->p[data->n].state != isl_state_none) + data->n++; + if (data->n == 0) + isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid, + "cannot handle void expression", return NULL); + + for (i = 0; i < data->n; ++i) { + data->p[i].set = isl_set_list_union(data->p[i].set_list); + if (data->p[i].state != isl_state_single) + data->p[i].set = isl_set_coalesce(data->p[i].set); + data->p[i].set_list = NULL; + } + + if (isl_sort(data->p, data->n, sizeof(data->p[0]), + &sort_pieces_cmp, NULL) < 0) + return isl_ast_expr_free(res); + + for (i = 0; i + 1 < data->n; ++i) { + next = add_intermediate_piece(data, i, next); + if (!next) + return isl_ast_expr_free(res); + } + + if (add_last_piece(data, data->n - 1, next) < 0) + return isl_ast_expr_free(res); + + return res; +} + +/* Can the list of subpieces in the last piece of "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 @@ -1810,16 +1948,16 @@ static isl_bool extends(struct isl_from_pw_aff_data *data, 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); + n = isl_set_list_n_set(data->p[data->n].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); + aff_i = isl_aff_list_get_aff(data->p[data->n].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); + required = isl_set_list_get_set(data->p[data->n].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); @@ -1830,7 +1968,7 @@ static isl_bool extends(struct isl_from_pw_aff_data *data, return is_valid; } - aff_i = isl_aff_list_get_aff(data->aff_list, i); + aff_i = isl_aff_list_get_aff(data->p[data->n].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); @@ -1872,39 +2010,39 @@ static isl_bool extends_max(struct isl_from_pw_aff_data *data, /* 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 the last piece of "data" contains either a single subpiece + * 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. + * If no such extension can be performed, then move to the next piece + * in "data" (if the current piece contains any data), and then store + * the current subpiece in the current piece of "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_bool test; + enum isl_from_pw_aff_state state; - if (data->state == isl_state_single || data->state == isl_state_min) { + state = data->p[data->n].state; + if (state == isl_state_single || 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) { + if (state == isl_state_single || 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; - } + if (state != isl_state_none) + data->n++; set_single(data, set, aff); return isl_stat_ok; @@ -1922,7 +2060,7 @@ error: __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal( __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa) { - struct isl_from_pw_aff_data data; + struct isl_from_pw_aff_data data = { NULL }; isl_ast_expr *res = NULL; pa = isl_ast_build_compute_gist_pw_aff(build, pa); @@ -1930,22 +2068,20 @@ __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal( if (!pa) return NULL; - data.build = build; - 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_from_pw_aff_data_init(&data, build, pa) < 0) + goto error; + set_none(&data); - 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); + if (isl_pw_aff_foreach_piece(pa, &ast_expr_from_pw_aff, &data) >= 0) + res = build_pieces(&data); isl_pw_aff_free(pa); - isl_set_list_free(data.set_list); - isl_aff_list_free(data.aff_list); - isl_set_free(data.dom); + isl_from_pw_aff_data_clear(&data); return res; +error: + isl_pw_aff_free(pa); + isl_from_pw_aff_data_clear(&data); + return NULL; } /* Construct an isl_ast_expr that evaluates "pa". diff --git a/polly/lib/External/isl/isl_ast_build_private.h b/polly/lib/External/isl/isl_ast_build_private.h index 9cd010be14b..ae638c7157b 100644 --- a/polly/lib/External/isl/isl_ast_build_private.h +++ b/polly/lib/External/isl/isl_ast_build_private.h @@ -293,7 +293,7 @@ __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain( int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build, __isl_keep isl_aff *aff); -int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos); +isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos); __isl_give isl_aff *isl_ast_build_get_offset(__isl_keep isl_ast_build *build, int pos); __isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build, diff --git a/polly/lib/External/isl/isl_ast_codegen.c b/polly/lib/External/isl/isl_ast_codegen.c index 350a8402165..ccb11bb5361 100644 --- a/polly/lib/External/isl/isl_ast_codegen.c +++ b/polly/lib/External/isl/isl_ast_codegen.c @@ -1107,6 +1107,9 @@ static __isl_give isl_ast_graft *set_for_node_expressions( node->u.f.init = reduce_list(isl_ast_op_max, lower, build); node->u.f.inc = for_inc(build); + if (!node->u.f.init || !node->u.f.inc) + graft = isl_ast_graft_free(graft); + if (use_list) graft = set_for_cond_from_list(graft, upper_list, build); else @@ -1114,10 +1117,6 @@ static __isl_give isl_ast_graft *set_for_node_expressions( isl_ast_build_free(build); - if (!node->u.f.iterator || !node->u.f.init || - !node->u.f.cond || !node->u.f.inc) - return isl_ast_graft_free(graft); - return graft; } diff --git a/polly/lib/External/isl/isl_ctx.c b/polly/lib/External/isl/isl_ctx.c index 95880345ab8..002863e2cb3 100644 --- a/polly/lib/External/isl/isl_ctx.c +++ b/polly/lib/External/isl/isl_ctx.c @@ -14,6 +14,14 @@ #define __isl_calloc(type,size) ((type *)calloc(1, size)) #define __isl_calloc_type(type) __isl_calloc(type,sizeof(type)) +/* Return the negation of "b", where the negation of isl_bool_error + * is isl_bool_error again. + */ +isl_bool isl_bool_not(isl_bool b) +{ + return b < 0 ? isl_bool_error : !b; +} + /* Check that the result of an allocation ("p") is not NULL and * complain if it is. * The only exception is when allocation size ("size") is equal to zero. diff --git a/polly/lib/External/isl/isl_equalities.c b/polly/lib/External/isl/isl_equalities.c index 83572a07b1e..a43aa42e892 100644 --- a/polly/lib/External/isl/isl_equalities.c +++ b/polly/lib/External/isl/isl_equalities.c @@ -430,17 +430,70 @@ __isl_give isl_mat *isl_mat_parameter_compression_ext(__isl_take isl_mat *B, return isl_mat_parameter_compression(B, d); } +/* Return a compression matrix that indicates that there are no solutions + * to the original constraints. In particular, return a zero-column + * matrix with 1 + dim rows. If "T2" is not NULL, then assign *T2 + * the inverse of this matrix. *T2 may already have been assigned + * matrix, so free it first. + * "free1", "free2" and "free3" are temporary matrices that are + * not useful when an empty compression is returned. They are + * simply freed. + */ +static __isl_give isl_mat *empty_compression(isl_ctx *ctx, unsigned dim, + __isl_give isl_mat **T2, __isl_take isl_mat *free1, + __isl_take isl_mat *free2, __isl_take isl_mat *free3) +{ + isl_mat_free(free1); + isl_mat_free(free2); + isl_mat_free(free3); + if (T2) { + isl_mat_free(*T2); + *T2 = isl_mat_alloc(ctx, 0, 1 + dim); + } + return isl_mat_alloc(ctx, 1 + dim, 0); +} + +/* Given a matrix that maps a (possibly) parametric domain to + * a parametric domain, add in rows that map the "nparam" parameters onto + * themselves. + */ +static __isl_give isl_mat *insert_parameter_rows(__isl_take isl_mat *mat, + unsigned nparam) +{ + int i; + + if (nparam == 0) + return mat; + if (!mat) + return NULL; + + mat = isl_mat_insert_rows(mat, 1, nparam); + if (!mat) + return NULL; + + for (i = 0; i < nparam; ++i) { + isl_seq_clr(mat->row[1 + i], mat->n_col); + isl_int_set(mat->row[1 + i][1 + i], mat->row[0][0]); + } + + return mat; +} + /* Given a set of equalities * - * M x - c = 0 + * -C(y) + M x = 0 * * this function computes a unimodular transformation from a lower-dimensional * space to the original space that bijectively maps the integer points x' * in the lower-dimensional space to the integer points x in the original * space that satisfy the equalities. * - * The input is given as a matrix B = [ -c M ] and the output is a + * The input is given as a matrix B = [ -C M ] and the output is a * matrix that maps [1 x'] to [1 x]. + * The number of equality constraints in B is assumed to be smaller than + * or equal to the number of variables x. + * "first" is the position of the first x variable. + * The preceding variables are considered to by y-variables. * If T2 is not NULL, then *T2 is set to a matrix mapping [1 x] to [1 x']. * * First compute the (left) Hermite normal form of M, @@ -458,24 +511,27 @@ __isl_give isl_mat *isl_mat_parameter_compression_ext(__isl_take isl_mat *B, * * The equalities then become * - * H1 x1' - c = 0 or x1' = H1^{-1} c = c' + * -C(y) + H1 x1' = 0 or x1' = H1^{-1} C(y) = C'(y) * - * If any of the c' is non-integer, then the original set has no - * integer solutions (since the x' are a unimodular transformation - * of the x) and a zero-column matrix is returned. + * If the denominator of the constant term does not divide the + * the common denominator of the coefficients of y, then every + * integer point is mapped to a non-integer point and then the original set + * has no integer solutions (since the x' are a unimodular transformation + * of the x). In this case, a zero-column matrix is returned. * Otherwise, the transformation is given by * - * x = U1 H1^{-1} c + U2 x2' + * x = U1 H1^{-1} C(y) + U2 x2' * * The inverse transformation is simply * * x2' = Q2 x */ -__isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, - __isl_give isl_mat **T2) +__isl_give isl_mat *isl_mat_final_variable_compression(__isl_take isl_mat *B, + int first, __isl_give isl_mat **T2) { - int i; - struct isl_mat *H = NULL, *C = NULL, *H1, *U = NULL, *U1, *U2, *TC; + int i, n; + isl_ctx *ctx; + isl_mat *H = NULL, *C, *H1, *U = NULL, *U1, *U2; unsigned dim; if (T2) @@ -483,56 +539,62 @@ __isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, if (!B) goto error; + ctx = isl_mat_get_ctx(B); dim = B->n_col - 1; - H = isl_mat_sub_alloc(B, 0, B->n_row, 1, dim); + n = dim - first; + if (n < B->n_row) + isl_die(ctx, isl_error_invalid, "too many equality constraints", + goto error); + H = isl_mat_sub_alloc(B, 0, B->n_row, 1 + first, n); H = isl_mat_left_hermite(H, 0, &U, T2); if (!H || !U || (T2 && !*T2)) goto error; if (T2) { *T2 = isl_mat_drop_rows(*T2, 0, B->n_row); - *T2 = isl_mat_lin_to_aff(*T2); + *T2 = isl_mat_diagonal(isl_mat_identity(ctx, 1 + first), *T2); if (!*T2) goto error; } - C = isl_mat_alloc(B->ctx, 1+B->n_row, 1); + C = isl_mat_alloc(ctx, 1 + B->n_row, 1 + first); if (!C) goto error; isl_int_set_si(C->row[0][0], 1); - isl_mat_sub_neg(C->ctx, C->row+1, B->row, B->n_row, 0, 0, 1); + isl_seq_clr(C->row[0] + 1, first); + isl_mat_sub_neg(ctx, C->row + 1, B->row, B->n_row, 0, 0, 1 + first); H1 = isl_mat_sub_alloc(H, 0, H->n_row, 0, H->n_row); H1 = isl_mat_lin_to_aff(H1); - TC = isl_mat_inverse_product(H1, C); - if (!TC) + C = isl_mat_inverse_product(H1, C); + if (!C) goto error; isl_mat_free(H); - if (!isl_int_is_one(TC->row[0][0])) { + if (!isl_int_is_one(C->row[0][0])) { + isl_int g; + + isl_int_init(g); for (i = 0; i < B->n_row; ++i) { - if (!isl_int_is_divisible_by(TC->row[1+i][0], TC->row[0][0])) { - struct isl_ctx *ctx = B->ctx; - isl_mat_free(B); - isl_mat_free(TC); - isl_mat_free(U); - if (T2) { - isl_mat_free(*T2); - *T2 = isl_mat_alloc(ctx, 0, 1 + dim); - } - return isl_mat_alloc(ctx, 1 + dim, 0); - } - isl_seq_scale_down(TC->row[1+i], TC->row[1+i], TC->row[0][0], 1); + isl_seq_gcd(C->row[1 + i] + 1, first, &g); + isl_int_gcd(g, g, C->row[0][0]); + if (!isl_int_is_divisible_by(C->row[1 + i][0], g)) + break; } - isl_int_set_si(TC->row[0][0], 1); + isl_int_clear(g); + + if (i < B->n_row) + return empty_compression(ctx, dim, T2, B, C, U); + C = isl_mat_normalize(C); } U1 = isl_mat_sub_alloc(U, 0, U->n_row, 0, B->n_row); U1 = isl_mat_lin_to_aff(U1); U2 = isl_mat_sub_alloc(U, 0, U->n_row, B->n_row, U->n_row - B->n_row); U2 = isl_mat_lin_to_aff(U2); isl_mat_free(U); - TC = isl_mat_product(U1, TC); - TC = isl_mat_aff_direct_sum(TC, U2); + C = isl_mat_product(U1, C); + C = isl_mat_aff_direct_sum(C, U2); + C = insert_parameter_rows(C, first); isl_mat_free(B); - return TC; + return C; error: isl_mat_free(B); isl_mat_free(H); @@ -544,6 +606,27 @@ error: return NULL; } +/* Given a set of equalities + * + * M x - c = 0 + * + * this function computes a unimodular transformation from a lower-dimensional + * space to the original space that bijectively maps the integer points x' + * in the lower-dimensional space to the integer points x in the original + * space that satisfy the equalities. + * + * The input is given as a matrix B = [ -c M ] and the output is a + * matrix that maps [1 x'] to [1 x]. + * The number of equality constraints in B is assumed to be smaller than + * or equal to the number of variables x. + * If T2 is not NULL, then *T2 is set to a matrix mapping [1 x] to [1 x']. + */ +__isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, + __isl_give isl_mat **T2) +{ + return isl_mat_final_variable_compression(B, 0, T2); +} + /* Return "bset" and set *T and *T2 to the identity transformation * on "bset" (provided T and T2 are not NULL). */ diff --git a/polly/lib/External/isl/isl_equalities.h b/polly/lib/External/isl/isl_equalities.h index 0206cd1c222..a64d1234810 100644 --- a/polly/lib/External/isl/isl_equalities.h +++ b/polly/lib/External/isl/isl_equalities.h @@ -17,6 +17,8 @@ extern "C" { #endif +__isl_give isl_mat *isl_mat_final_variable_compression(__isl_take isl_mat *B, + int first, __isl_give isl_mat **T2); __isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, __isl_give isl_mat **T2); struct isl_mat *isl_mat_parameter_compression( diff --git a/polly/lib/External/isl/isl_fold.c b/polly/lib/External/isl/isl_fold.c index c2162cfbf50..e05ee101737 100644 --- a/polly/lib/External/isl/isl_fold.c +++ b/polly/lib/External/isl/isl_fold.c @@ -1022,6 +1022,37 @@ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add( return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2); } +/* Compare two quasi-polynomial reductions. + * + * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater" + * than "fold2" and 0 if they are equal. + */ +int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1, + __isl_keep isl_qpolynomial_fold *fold2) +{ + int i; + + if (fold1 == fold2) + return 0; + if (!fold1) + return -1; + if (!fold2) + return 1; + + if (fold1->n != fold2->n) + return fold1->n - fold2->n; + + for (i = 0; i < fold1->n; ++i) { + int cmp; + + cmp = isl_qpolynomial_plain_cmp(fold1->qp[i], fold2->qp[i]); + if (cmp != 0) + return cmp; + } + + return 0; +} + int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1, __isl_keep isl_qpolynomial_fold *fold2) { diff --git a/polly/lib/External/isl/isl_hmap_templ.c b/polly/lib/External/isl/isl_hmap_templ.c deleted file mode 100644 index c6a67473bce..00000000000 --- a/polly/lib/External/isl/isl_hmap_templ.c +++ /dev/null @@ -1,389 +0,0 @@ -/* - * Copyright 2011 INRIA Saclay - * Copyright 2013 Ecole Normale Superieure - * - * Use of this software is governed by the MIT license - * - * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, - * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, - * 91893 Orsay, France - * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France - */ - -#include <isl/ctx.h> -#include <isl/hash.h> - -#define xCAT(A,B) A ## B -#define CAT(A,B) xCAT(A,B) -#define KEY CAT(isl_,KEY_BASE) -#define VAL CAT(isl_,VAL_BASE) -#define xFN(TYPE,NAME) TYPE ## _ ## NAME -#define FN(TYPE,NAME) xFN(TYPE,NAME) -#define xHMAP(KEY,VAL_BASE) KEY ## _to_ ## VAL_BASE -#define yHMAP(KEY,VAL_BASE) xHMAP(KEY,VAL_BASE) -#define HMAP yHMAP(KEY,VAL_BASE) -#define HMAP_BASE yHMAP(KEY_BASE,VAL_BASE) -#define xS(TYPE1,TYPE2,NAME) struct isl_ ## TYPE1 ## _ ## TYPE2 ## _ ## NAME -#define yS(TYPE1,TYPE2,NAME) xS(TYPE1,TYPE2,NAME) -#define S(NAME) yS(KEY_BASE,VAL_BASE,NAME) - -struct HMAP { - int ref; - isl_ctx *ctx; - struct isl_hash_table table; -}; - -S(pair) { - KEY *key; - VAL *val; -}; - -__isl_give HMAP *FN(HMAP,alloc)(isl_ctx *ctx, int min_size) -{ - HMAP *hmap; - - hmap = isl_calloc_type(ctx, HMAP); - if (!hmap) - return NULL; - - hmap->ctx = ctx; - isl_ctx_ref(ctx); - hmap->ref = 1; - - if (isl_hash_table_init(ctx, &hmap->table, min_size) < 0) - return FN(HMAP,free)(hmap); - - return hmap; -} - -static isl_stat free_pair(void **entry, void *user) -{ - S(pair) *pair = *entry; - FN(KEY,free)(pair->key); - FN(VAL,free)(pair->val); - free(pair); - *entry = NULL; - return isl_stat_ok; -} - -__isl_null HMAP *FN(HMAP,free)(__isl_take HMAP *hmap) -{ - if (!hmap) - return NULL; - if (--hmap->ref > 0) - return NULL; - isl_hash_table_foreach(hmap->ctx, &hmap->table, &free_pair, NULL); - isl_hash_table_clear(&hmap->table); - isl_ctx_deref(hmap->ctx); - free(hmap); - return NULL; -} - -isl_ctx *FN(HMAP,get_ctx)(__isl_keep HMAP *hmap) -{ - return hmap ? hmap->ctx : NULL; -} - -/* Add a mapping from "key" to "val" to the associative array - * pointed to by user. - */ -static isl_stat add_key_val(__isl_take KEY *key, __isl_take VAL *val, - void *user) -{ - HMAP **hmap = (HMAP **) user; - - *hmap = FN(HMAP,set)(*hmap, key, val); - - if (!*hmap) - return isl_stat_error; - - return isl_stat_ok; -} - -__isl_give HMAP *FN(HMAP,dup)(__isl_keep HMAP *hmap) -{ - HMAP *dup; - - if (!hmap) - return NULL; - - dup = FN(HMAP,alloc)(hmap->ctx, hmap->table.n); - if (FN(HMAP,foreach)(hmap, &add_key_val, &dup) < 0) - return FN(HMAP,free)(dup); - - return dup; -} - -__isl_give HMAP *FN(HMAP,cow)(__isl_take HMAP *hmap) -{ - if (!hmap) - return NULL; - - if (hmap->ref == 1) - return hmap; - hmap->ref--; - return FN(HMAP,dup)(hmap); -} - -__isl_give HMAP *FN(HMAP,copy)(__isl_keep HMAP *hmap) -{ - if (!hmap) - return NULL; - - hmap->ref++; - return hmap; -} - -static int has_key(const void *entry, const void *c_key) -{ - const S(pair) *pair = entry; - KEY *key = (KEY *) c_key; - - return KEY_EQUAL(pair->key, key); -} - -isl_bool FN(HMAP,has)(__isl_keep HMAP *hmap, __isl_keep KEY *key) -{ - uint32_t hash; - - if (!hmap) - return isl_bool_error; - - hash = FN(KEY,get_hash)(key); - return !!isl_hash_table_find(hmap->ctx, &hmap->table, hash, - &has_key, key, 0); -} - -__isl_give VAL *FN(HMAP,get)(__isl_keep HMAP *hmap, __isl_take KEY *key) -{ - struct isl_hash_table_entry *entry; - S(pair) *pair; - uint32_t hash; - - if (!hmap || !key) - goto error; - - hash = FN(KEY,get_hash)(key); - entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, - &has_key, key, 0); - FN(KEY,free)(key); - - if (!entry) - return NULL; - - pair = entry->data; - - return FN(VAL,copy)(pair->val); -error: - FN(KEY,free)(key); - return NULL; -} - -/* Remove the mapping between "key" and its associated value (if any) - * from "hmap". - * - * If "key" is not mapped to anything, then we leave "hmap" untouched" - */ -__isl_give HMAP *FN(HMAP,drop)(__isl_take HMAP *hmap, __isl_take KEY *key) -{ - struct isl_hash_table_entry *entry; - S(pair) *pair; - uint32_t hash; - - if (!hmap || !key) - goto error; - - hash = FN(KEY,get_hash)(key); - entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, - &has_key, key, 0); - if (!entry) { - FN(KEY,free)(key); - return hmap; - } - - hmap = FN(HMAP,cow)(hmap); - if (!hmap) - goto error; - entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, - &has_key, key, 0); - FN(KEY,free)(key); - - if (!entry) - isl_die(hmap->ctx, isl_error_internal, - "missing entry" , goto error); - - pair = entry->data; - isl_hash_table_remove(hmap->ctx, &hmap->table, entry); - FN(KEY,free)(pair->key); - FN(VAL,free)(pair->val); - free(pair); - - return hmap; -error: - FN(KEY,free)(key); - FN(HMAP,free)(hmap); - return NULL; -} - -/* Add a mapping from "key" to "val" to "hmap". - * If "key" was already mapped to something else, then that mapping - * is replaced. - * If key happened to be mapped to "val" already, then we leave - * "hmap" untouched. - */ -__isl_give HMAP *FN(HMAP,set)(__isl_take HMAP *hmap, - __isl_take KEY *key, __isl_take VAL *val) -{ - struct isl_hash_table_entry *entry; - S(pair) *pair; - uint32_t hash; - - if (!hmap || !key || !val) - goto error; - - hash = FN(KEY,get_hash)(key); - entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, - &has_key, key, 0); - if (entry) { - int equal; - pair = entry->data; - equal = VAL_EQUAL(pair->val, val); - if (equal < 0) - goto error; - if (equal) { - FN(KEY,free)(key); - FN(VAL,free)(val); - return hmap; - } - } - - hmap = FN(HMAP,cow)(hmap); - if (!hmap) - goto error; - - entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash, - &has_key, key, 1); - - if (!entry) - goto error; - - if (entry->data) { - pair = entry->data; - FN(VAL,free)(pair->val); - pair->val = val; - FN(KEY,free)(key); - return hmap; - } - - pair = isl_alloc_type(hmap->ctx, S(pair)); - if (!pair) - goto error; - - entry->data = pair; - pair->key = key; - pair->val = val; - return hmap; -error: - FN(KEY,free)(key); - FN(VAL,free)(val); - return FN(HMAP,free)(hmap); -} - -/* Internal data structure for isl_map_to_basic_set_foreach. - * - * fn is the function that should be called on each entry. - * user is the user-specified final argument to fn. - */ -S(foreach_data) { - isl_stat (*fn)(__isl_take KEY *key, __isl_take VAL *val, void *user); - void *user; -}; - -/* Call data->fn on a copy of the key and value in *entry. - */ -static isl_stat call_on_copy(void **entry, void *user) -{ - S(pair) *pair = *entry; - S(foreach_data) *data = (S(foreach_data) *) user; - - return data->fn(FN(KEY,copy)(pair->key), FN(VAL,copy)(pair->val), - data->user); -} - -/* Call "fn" on each pair of key and value in "hmap". - */ -isl_stat FN(HMAP,foreach)(__isl_keep HMAP *hmap, - isl_stat (*fn)(__isl_take KEY *key, __isl_take VAL *val, void *user), - void *user) -{ - S(foreach_data) data = { fn, user }; - - if (!hmap) - return isl_stat_error; - - return isl_hash_table_foreach(hmap->ctx, &hmap->table, - &call_on_copy, &data); -} - -/* Internal data structure for print_pair. - * - * p is the printer on which the associative array is being printed. - * first is set if the current key-value pair is the first to be printed. - */ -S(print_data) { - isl_printer *p; - int first; -}; - -/* Print the given key-value pair to data->p. - */ -static isl_stat print_pair(__isl_take KEY *key, __isl_take VAL *val, void *user) -{ - S(print_data) *data = user; - - if (!data->first) - data->p = isl_printer_print_str(data->p, ", "); - data->p = FN(isl_printer_print,KEY_BASE)(data->p, key); - data->p = isl_printer_print_str(data->p, ": "); - data->p = FN(isl_printer_print,VAL_BASE)(data->p, val); - data->first = 0; - - FN(KEY,free)(key); - FN(VAL,free)(val); - return isl_stat_ok; -} - -/* Print the associative array to "p". - */ -__isl_give isl_printer *FN(isl_printer_print,HMAP_BASE)( - __isl_take isl_printer *p, __isl_keep HMAP *hmap) -{ - S(print_data) data; - - if (!p || !hmap) - return isl_printer_free(p); - - p = isl_printer_print_str(p, "{"); - data.p = p; - data.first = 1; - if (FN(HMAP,foreach)(hmap, &print_pair, &data) < 0) - data.p = isl_printer_free(data.p); - p = data.p; - p = isl_printer_print_str(p, "}"); - - return p; -} - -void FN(HMAP,dump)(__isl_keep HMAP *hmap) -{ - isl_printer *printer; - - if (!hmap) - return; - - printer = isl_printer_to_file(FN(HMAP,get_ctx)(hmap), stderr); - printer = FN(isl_printer_print,HMAP_BASE)(printer, hmap); - printer = isl_printer_end_line(printer); - - isl_printer_free(printer); -} diff --git a/polly/lib/External/isl/isl_id_to_ast_expr.c b/polly/lib/External/isl/isl_id_to_ast_expr.c index f8ac7f7c68e..e0885654495 100644 --- a/polly/lib/External/isl/isl_id_to_ast_expr.c +++ b/polly/lib/External/isl/isl_id_to_ast_expr.c @@ -3,9 +3,13 @@ #define isl_id_is_equal(id1,id2) id1 == id2 -#define KEY_BASE id -#define KEY_EQUAL isl_id_is_equal -#define VAL_BASE ast_expr -#define VAL_EQUAL isl_ast_expr_is_equal +#define ISL_KEY isl_id +#define ISL_VAL isl_ast_expr +#define ISL_HMAP_SUFFIX id_to_ast_expr +#define ISL_HMAP isl_id_to_ast_expr +#define ISL_KEY_IS_EQUAL isl_id_is_equal +#define ISL_VAL_IS_EQUAL isl_ast_expr_is_equal +#define ISL_KEY_PRINT isl_printer_print_id +#define ISL_VAL_PRINT isl_printer_print_ast_expr -#include <isl_hmap_templ.c> +#include <isl/hmap_templ.c> diff --git a/polly/lib/External/isl/isl_id_to_id.c b/polly/lib/External/isl/isl_id_to_id.c index 91f28d13698..dba2cf36739 100644 --- a/polly/lib/External/isl/isl_id_to_id.c +++ b/polly/lib/External/isl/isl_id_to_id.c @@ -2,9 +2,13 @@ #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 +#define ISL_KEY isl_id +#define ISL_VAL isl_id +#define ISL_HMAP_SUFFIX id_to_id +#define ISL_HMAP isl_id_to_id +#define ISL_KEY_IS_EQUAL isl_id_is_equal +#define ISL_VAL_IS_EQUAL isl_id_is_equal +#define ISL_KEY_PRINT isl_printer_print_id +#define ISL_VAL_PRINT isl_printer_print_id -#include <isl_hmap_templ.c> +#include <isl/hmap_templ.c> diff --git a/polly/lib/External/isl/isl_id_to_pw_aff.c b/polly/lib/External/isl/isl_id_to_pw_aff.c index 2fce240dd30..6ea6fea36af 100644 --- a/polly/lib/External/isl/isl_id_to_pw_aff.c +++ b/polly/lib/External/isl/isl_id_to_pw_aff.c @@ -3,9 +3,13 @@ #define isl_id_is_equal(id1,id2) id1 == id2 -#define KEY_BASE id -#define KEY_EQUAL isl_id_is_equal -#define VAL_BASE pw_aff -#define VAL_EQUAL isl_pw_aff_plain_is_equal +#define ISL_KEY isl_id +#define ISL_VAL isl_pw_aff +#define ISL_HMAP_SUFFIX id_to_pw_aff +#define ISL_HMAP isl_id_to_pw_aff +#define ISL_KEY_IS_EQUAL isl_id_is_equal +#define ISL_VAL_IS_EQUAL isl_pw_aff_plain_is_equal +#define ISL_KEY_PRINT isl_printer_print_id +#define ISL_VAL_PRINT isl_printer_print_pw_aff -#include <isl_hmap_templ.c> +#include <isl/hmap_templ.c> diff --git a/polly/lib/External/isl/isl_local.c b/polly/lib/External/isl/isl_local.c new file mode 100644 index 00000000000..7725af9d006 --- /dev/null +++ b/polly/lib/External/isl/isl_local.c @@ -0,0 +1,74 @@ +/* + * Copyright 2014 Ecole Normale Superieure + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, + * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + */ + +#include <isl_mat_private.h> +#include <isl_seq.h> + +/* Given a matrix "div" representing local variables, + * does the variable at position "pos" have an explicit representation? + */ +isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos) +{ + if (!div) + return isl_bool_error; + if (pos < 0 || pos >= div->n_row) + isl_die(isl_mat_get_ctx(div), isl_error_invalid, + "position out of bounds", return isl_bool_error); + return !isl_int_is_zero(div->row[pos][0]); +} + +/* Compare two matrices representing local variables, defined over + * the same space. + * + * Return -1 if "div1" is "smaller" than "div2", 1 if "div1" is "greater" + * than "div2" and 0 if they are equal. + * + * The order is fairly arbitrary. We do "prefer" divs that only involve + * earlier dimensions in the sense that we consider matrices where + * the first differing div involves earlier dimensions to be smaller. + */ +int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2) +{ + int i; + int cmp; + int known1, known2; + int last1, last2; + int n_col; + + if (div1 == div2) + return 0; + if (!div1) + return -1; + if (!div2) + return 1; + + if (div1->n_row != div2->n_row) + return div1->n_row - div2->n_row; + + n_col = isl_mat_cols(div1); + for (i = 0; i < div1->n_row; ++i) { + known1 = isl_local_div_is_known(div1, i); + known2 = isl_local_div_is_known(div2, i); + if (!known1 && !known2) + continue; + if (!known1) + return 1; + if (!known2) + return -1; + last1 = isl_seq_last_non_zero(div1->row[i] + 1, n_col - 1); + last2 = isl_seq_last_non_zero(div2->row[i] + 1, n_col - 1); + if (last1 != last2) + return last1 - last2; + cmp = isl_seq_cmp(div1->row[i], div2->row[i], n_col); + if (cmp != 0) + return cmp; + } + + return 0; +} diff --git a/polly/lib/External/isl/isl_local.h b/polly/lib/External/isl/isl_local.h new file mode 100644 index 00000000000..f989fcbe79f --- /dev/null +++ b/polly/lib/External/isl/isl_local.h @@ -0,0 +1,9 @@ +#ifndef ISL_LOCAL_H +#define ISL_LOCAL_H + +#include <isl/mat.h> + +isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos); +int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2); + +#endif diff --git a/polly/lib/External/isl/isl_local_space.c b/polly/lib/External/isl/isl_local_space.c index 7c06b59d2ab..ece514bdb09 100644 --- a/polly/lib/External/isl/isl_local_space.c +++ b/polly/lib/External/isl/isl_local_space.c @@ -18,12 +18,31 @@ #include <isl_aff_private.h> #include <isl_vec_private.h> #include <isl_seq.h> +#include <isl_local.h> isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls) { return ls ? ls->dim->ctx : NULL; } +/* Return a hash value that digests "ls". + */ +uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls) +{ + uint32_t hash, space_hash, div_hash; + + if (!ls) + return 0; + + hash = isl_hash_init(); + space_hash = isl_space_get_hash(ls->dim); + isl_hash_hash(hash, space_hash); + div_hash = isl_mat_get_hash(ls->div); + isl_hash_hash(hash, div_hash); + + return hash; +} + __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim, __isl_take isl_mat *div) { @@ -162,19 +181,11 @@ isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1, * * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater" * than "ls2" and 0 if they are equal. - * - * The order is fairly arbitrary. We do "prefer" divs that only involve - * earlier dimensions in the sense that we consider local spaces where - * the first differing div involves earlier dimensions to be smaller. */ int isl_local_space_cmp(__isl_keep isl_local_space *ls1, __isl_keep isl_local_space *ls2) { - int i; int cmp; - int known1, known2; - int last1, last2; - int n_col; if (ls1 == ls2) return 0; @@ -187,29 +198,7 @@ int isl_local_space_cmp(__isl_keep isl_local_space *ls1, if (cmp != 0) return cmp; - if (ls1->div->n_row != ls2->div->n_row) - return ls1->div->n_row - ls2->div->n_row; - - n_col = isl_mat_cols(ls1->div); - for (i = 0; i < ls1->div->n_row; ++i) { - known1 = isl_local_space_div_is_known(ls1, i); - known2 = isl_local_space_div_is_known(ls2, i); - if (!known1 && !known2) - continue; - if (!known1) - return 1; - if (!known2) - return -1; - last1 = isl_seq_last_non_zero(ls1->div->row[i] + 1, n_col - 1); - last2 = isl_seq_last_non_zero(ls2->div->row[i] + 1, n_col - 1); - if (last1 != last2) - return last1 - last2; - cmp = isl_seq_cmp(ls1->div->row[i], ls2->div->row[i], n_col); - if (cmp != 0) - return cmp; - } - - return 0; + return isl_local_cmp(ls1->div, ls2->div); } int isl_local_space_dim(__isl_keep isl_local_space *ls, @@ -730,14 +719,11 @@ error: /* Does "ls" have an explicit representation for div "div"? */ -int isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div) +isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div) { if (!ls) - return -1; - if (div < 0 || div >= ls->div->n_row) - isl_die(isl_local_space_get_ctx(ls), isl_error_invalid, - "position out of bounds", return -1); - return !isl_int_is_zero(ls->div->row[div][0]); + return isl_bool_error; + return isl_local_div_is_known(ls->div, div); } /* Does "ls" have an explicit representation for all local variables? @@ -749,9 +735,11 @@ isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls) if (!ls) return isl_bool_error; - for (i = 0; i < ls->div->n_row; ++i) - if (isl_int_is_zero(ls->div->row[i][0])) - return isl_bool_false; + for (i = 0; i < ls->div->n_row; ++i) { + isl_bool known = isl_local_space_div_is_known(ls, i); + if (known < 0 || !known) + return known; + } return isl_bool_true; } diff --git a/polly/lib/External/isl/isl_local_space_private.h b/polly/lib/External/isl/isl_local_space_private.h index 5d5330500f7..5f62a3c948f 100644 --- a/polly/lib/External/isl/isl_local_space_private.h +++ b/polly/lib/External/isl/isl_local_space_private.h @@ -12,6 +12,8 @@ struct isl_local_space { isl_mat *div; }; +uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls); + __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim, unsigned n_div); __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim, @@ -31,7 +33,7 @@ unsigned isl_local_space_offset(__isl_keep isl_local_space *ls, __isl_give isl_local_space *isl_local_space_replace_divs( __isl_take isl_local_space *ls, __isl_take isl_mat *div); -int isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div); +isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div); isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls); __isl_give isl_local_space *isl_local_space_substitute_equalities( diff --git a/polly/lib/External/isl/isl_map.c b/polly/lib/External/isl/isl_map.c index 16cc3c24575..50c0521b8bc 100644 --- a/polly/lib/External/isl/isl_map.c +++ b/polly/lib/External/isl/isl_map.c @@ -6117,13 +6117,16 @@ __isl_give isl_pw_multi_aff *isl_basic_map_lexmin_pw_multi_aff( /* Given a map "map", compute the lexicographically minimal * (or maximal) image element for each domain element in dom, * in the form of an isl_pw_multi_aff. - * Set *empty to those elements in dom that do not have an image element. + * If "empty" is not NULL, then set *empty to those elements in dom that + * do not have an image element. * * We first compute the lexicographically minimal or maximal element * in the first basic map. This results in a partial solution "res" * and a subset "todo" of dom that still need to be handled. * We then consider each of the remaining maps in "map" and successively * update both "res" and "todo". + * If "empty" is NULL, then the todo sets are not needed and therefore + * also not computed. */ static __isl_give isl_pw_multi_aff *isl_map_partial_lexopt_aligned_pw_multi_aff( __isl_take isl_map *map, __isl_take isl_set *dom, @@ -6146,22 +6149,24 @@ static __isl_give isl_pw_multi_aff *isl_map_partial_lexopt_aligned_pw_multi_aff( res = basic_map_partial_lexopt_pw_multi_aff( isl_basic_map_copy(map->p[0]), - isl_set_copy(dom), &todo, max); + isl_set_copy(dom), empty, max); + if (empty) + todo = *empty; for (i = 1; i < map->n; ++i) { isl_pw_multi_aff *res_i; - isl_set *todo_i; res_i = basic_map_partial_lexopt_pw_multi_aff( isl_basic_map_copy(map->p[i]), - isl_set_copy(dom), &todo_i, max); + isl_set_copy(dom), empty, max); if (max) res = isl_pw_multi_aff_union_lexmax(res, res_i); else res = isl_pw_multi_aff_union_lexmin(res, res_i); - todo = isl_set_intersect(todo, todo_i); + if (empty) + todo = isl_set_intersect(todo, *empty); } isl_set_free(dom); @@ -6169,8 +6174,6 @@ static __isl_give isl_pw_multi_aff *isl_map_partial_lexopt_aligned_pw_multi_aff( if (empty) *empty = todo; - else - isl_set_free(todo); return res; error: @@ -6567,42 +6570,34 @@ error: /* Apply a preimage specified by "mat" on the parameters of "set". * set is assumed to have only parameters and divs. */ -static struct isl_set *set_parameter_preimage( - struct isl_set *set, struct isl_mat *mat) +static __isl_give isl_set *set_parameter_preimage(__isl_take isl_set *set, + __isl_take isl_mat *mat) { - isl_space *dim = NULL; + isl_space *space; unsigned nparam; if (!set || !mat) goto error; - dim = isl_space_copy(set->dim); - dim = isl_space_cow(dim); - if (!dim) - goto error; - nparam = isl_set_dim(set, isl_dim_param); - isl_assert(set->ctx, mat->n_row == 1 + nparam, goto error); + if (mat->n_row != 1 + nparam) + isl_die(isl_set_get_ctx(set), isl_error_internal, + "unexpected number of rows", goto error); - dim->nparam = 0; - dim->n_out = nparam; - isl_set_reset_space(set, dim); + space = isl_set_get_space(set); + space = isl_space_move_dims(space, isl_dim_set, 0, + isl_dim_param, 0, nparam); + set = isl_set_reset_space(set, space); set = isl_set_preimage(set, mat); - if (!set) - goto error2; - dim = isl_space_copy(set->dim); - dim = isl_space_cow(dim); - if (!dim) - goto error2; - dim->nparam = dim->n_out; - dim->n_out = 0; - isl_set_reset_space(set, dim); + nparam = isl_set_dim(set, isl_dim_out); + space = isl_set_get_space(set); + space = isl_space_move_dims(space, isl_dim_param, 0, + isl_dim_out, 0, nparam); + set = isl_set_reset_space(set, space); return set; error: - isl_space_free(dim); isl_mat_free(mat); -error2: isl_set_free(set); return NULL; } @@ -6925,7 +6920,7 @@ static struct isl_map *compute_divs(struct isl_basic_map *bmap) unsigned nparam; unsigned n_in; unsigned n_out; - unsigned n_known; + int n_known; int i; bmap = isl_basic_map_sort_divs(bmap); @@ -6933,9 +6928,9 @@ static struct isl_map *compute_divs(struct isl_basic_map *bmap) if (!bmap) return NULL; - for (n_known = 0; n_known < bmap->n_div; ++n_known) - if (isl_int_is_zero(bmap->div[n_known][0])) - break; + n_known = isl_basic_map_first_unknown_div(bmap); + if (n_known < 0) + return isl_map_from_basic_map(isl_basic_map_free(bmap)); nparam = isl_basic_map_dim(bmap, isl_dim_param); n_in = isl_basic_map_dim(bmap, isl_dim_in); @@ -6967,6 +6962,27 @@ error: return NULL; } +/* Remove the explicit representation of local variable "div", + * if there is any. + */ +__isl_give isl_basic_map *isl_basic_map_mark_div_unknown( + __isl_take isl_basic_map *bmap, int div) +{ + isl_bool known; + + known = isl_basic_map_div_is_known(bmap, div); + if (known < 0) + return isl_basic_map_free(bmap); + if (!known) + return bmap; + + bmap = isl_basic_map_cow(bmap); + if (!bmap) + return NULL; + isl_int_set_si(bmap->div[div][0], 0); + return bmap; +} + /* Does local variable "div" of "bmap" have an explicit representation? */ isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div) @@ -6979,24 +6995,37 @@ isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div) return !isl_int_is_zero(bmap->div[div][0]); } -/* Does "bmap" have an explicit representation for all local variables? +/* Return the position of the first local variable that does not + * have an explicit representation. + * Return the total number of local variables if they all have + * an explicit representation. + * Return -1 on error. */ -isl_bool isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) +int isl_basic_map_first_unknown_div(__isl_keep isl_basic_map *bmap) { int i; - unsigned off; if (!bmap) - return isl_bool_error; + return -1; - off = isl_space_dim(bmap->dim, isl_dim_all); for (i = 0; i < bmap->n_div; ++i) { if (!isl_basic_map_div_is_known(bmap, i)) - return isl_bool_false; - isl_assert(bmap->ctx, isl_int_is_zero(bmap->div[i][1+1+off+i]), - return isl_bool_error); + return i; } - return isl_bool_true; + return bmap->n_div; +} + +/* Does "bmap" have an explicit representation for all local variables? + */ +isl_bool isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap) +{ + int first, n; + + n = isl_basic_map_dim(bmap, isl_dim_div); + first = isl_basic_map_first_unknown_div(bmap); + if (first < 0) + return isl_bool_error; + return first == n; } /* Do all basic maps in "map" have an explicit representation @@ -8184,6 +8213,10 @@ struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap) bmap->n_div-i); if (pos == -1) continue; + if (pos == 0) + isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal, + "integer division depends on itself", + return isl_basic_map_free(bmap)); isl_basic_map_swap_div(bmap, i, i + pos); --i; } @@ -11797,16 +11830,25 @@ __isl_give isl_map *isl_map_uncurry(__isl_take isl_map *map) /* Construct a basic map mapping the domain of the affine expression * to a one-dimensional range prescribed by the affine expression. + * + * A NaN affine expression cannot be converted to a basic map. */ __isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff) { int k; int pos; + isl_bool is_nan; isl_local_space *ls; - isl_basic_map *bmap; + isl_basic_map *bmap = NULL; if (!aff) return NULL; + is_nan = isl_aff_is_nan(aff); + if (is_nan < 0) + goto error; + if (is_nan) + isl_die(isl_aff_get_ctx(aff), isl_error_invalid, + "cannot convert NaN", goto error); ls = isl_aff_get_local_space(aff); bmap = isl_basic_map_from_local_space(ls); diff --git a/polly/lib/External/isl/isl_map_lexopt_templ.c b/polly/lib/External/isl/isl_map_lexopt_templ.c index 1196a87f7ea..d3b6a67947b 100644 --- a/polly/lib/External/isl/isl_map_lexopt_templ.c +++ b/polly/lib/External/isl/isl_map_lexopt_templ.c @@ -19,7 +19,8 @@ /* Given a basic map "bmap", compute the lexicographically minimal * (or maximal) image element for each domain element in dom. - * Set *empty to those elements in dom that do not have an image element. + * If empty is not NULL, then set *empty to those elements in dom + * that do not have an image element. * * We first make sure the basic sets in dom are disjoint and then * simply collect the results over each of the basic sets separately. @@ -32,6 +33,7 @@ static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)( { int i; TYPE *res; + isl_set *all_empty; dom = isl_set_make_disjoint(dom); if (!dom) @@ -49,24 +51,29 @@ static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)( res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap), isl_basic_set_copy(dom->p[0]), empty, max); - + + if (empty) + all_empty = *empty; for (i = 1; i < dom->n; ++i) { TYPE *res_i; - isl_set *empty_i; res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)( isl_basic_map_copy(bmap), - isl_basic_set_copy(dom->p[i]), &empty_i, max); + isl_basic_set_copy(dom->p[i]), empty, max); res = ADD(res, res_i); - *empty = isl_set_union_disjoint(*empty, empty_i); + if (empty) + all_empty = isl_set_union_disjoint(all_empty, *empty); } + if (empty) + *empty = all_empty; isl_set_free(dom); isl_basic_map_free(bmap); return res; error: - *empty = NULL; + if (empty) + *empty = NULL; isl_set_free(dom); isl_basic_map_free(bmap); return NULL; diff --git a/polly/lib/External/isl/isl_map_private.h b/polly/lib/External/isl/isl_map_private.h index 705b2814c5d..1676861029f 100644 --- a/polly/lib/External/isl/isl_map_private.h +++ b/polly/lib/External/isl/isl_map_private.h @@ -11,6 +11,7 @@ #define ISL_MAP_PRIVATE_H #define isl_basic_set isl_basic_map +#define isl_maybe_isl_basic_set isl_maybe_isl_basic_map #define isl_set isl_map #define isl_basic_set_list isl_basic_map_list #define isl_set_list isl_map_list @@ -412,7 +413,10 @@ __isl_give isl_basic_map *isl_basic_map_from_local_space( __isl_give isl_basic_set *isl_basic_set_expand_divs( __isl_take isl_basic_set *bset, __isl_take isl_mat *div, int *exp); +__isl_give isl_basic_map *isl_basic_map_mark_div_unknown( + __isl_take isl_basic_map *bmap, int div); isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div); +int isl_basic_map_first_unknown_div(__isl_keep isl_basic_map *bmap); isl_bool isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap); isl_bool isl_map_divs_known(__isl_keep isl_map *map); __isl_give isl_mat *isl_basic_set_get_divs(__isl_keep isl_basic_set *bset); diff --git a/polly/lib/External/isl/isl_map_simplify.c b/polly/lib/External/isl/isl_map_simplify.c index 15d5c20d539..4bfa11a6eca 100644 --- a/polly/lib/External/isl/isl_map_simplify.c +++ b/polly/lib/External/isl/isl_map_simplify.c @@ -1692,7 +1692,9 @@ static struct isl_basic_map *remove_dependent_vars(struct isl_basic_map *bmap, continue; if (isl_int_is_zero(bmap->div[i][1+1+pos])) continue; - isl_int_set_si(bmap->div[i][0], 0); + bmap = isl_basic_map_mark_div_unknown(bmap, i); + if (!bmap) + return NULL; } return bmap; } @@ -2813,6 +2815,369 @@ error: return NULL; } +/* Return the number of equality constraints in "bmap" that involve + * local variables. This function assumes that Gaussian elimination + * has been applied to the equality constraints. + */ +static int n_div_eq(__isl_keep isl_basic_map *bmap) +{ + int i; + int total, n_div; + + if (!bmap) + return -1; + + if (bmap->n_eq == 0) + return 0; + + total = isl_basic_map_dim(bmap, isl_dim_all); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + total -= n_div; + + for (i = 0; i < bmap->n_eq; ++i) + if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total, + n_div) == -1) + return i; + + return bmap->n_eq; +} + +/* Construct a basic map in "space" defined by the equality constraints in "eq". + * The constraints are assumed not to involve any local variables. + */ +static __isl_give isl_basic_map *basic_map_from_equalities( + __isl_take isl_space *space, __isl_take isl_mat *eq) +{ + int i, k; + isl_basic_map *bmap = NULL; + + if (!space || !eq) + goto error; + + if (1 + isl_space_dim(space, isl_dim_all) != eq->n_col) + isl_die(isl_space_get_ctx(space), isl_error_internal, + "unexpected number of columns", goto error); + + bmap = isl_basic_map_alloc_space(isl_space_copy(space), + 0, eq->n_row, 0); + for (i = 0; i < eq->n_row; ++i) { + k = isl_basic_map_alloc_equality(bmap); + if (k < 0) + goto error; + isl_seq_cpy(bmap->eq[k], eq->row[i], eq->n_col); + } + + isl_space_free(space); + isl_mat_free(eq); + return bmap; +error: + isl_space_free(space); + isl_mat_free(eq); + isl_basic_map_free(bmap); + return NULL; +} + +/* Construct and return a variable compression based on the equality + * constraints in "bmap1" and "bmap2" that do not involve the local variables. + * "n1" is the number of (initial) equality constraints in "bmap1" + * that do involve local variables. + * "n2" is the number of (initial) equality constraints in "bmap2" + * that do involve local variables. + * "total" is the total number of other variables. + * This function assumes that Gaussian elimination + * has been applied to the equality constraints in both "bmap1" and "bmap2" + * such that the equality constraints not involving local variables + * are those that start at "n1" or "n2". + * + * If either of "bmap1" and "bmap2" does not have such equality constraints, + * then simply compute the compression based on the equality constraints + * in the other basic map. + * Otherwise, combine the equality constraints from both into a new + * basic map such that Gaussian elimination can be applied to this combination + * and then construct a variable compression from the resulting + * equality constraints. + */ +static __isl_give isl_mat *combined_variable_compression( + __isl_keep isl_basic_map *bmap1, int n1, + __isl_keep isl_basic_map *bmap2, int n2, int total) +{ + isl_ctx *ctx; + isl_mat *E1, *E2, *V; + isl_basic_map *bmap; + + ctx = isl_basic_map_get_ctx(bmap1); + if (bmap1->n_eq == n1) { + E2 = isl_mat_sub_alloc6(ctx, bmap2->eq, + n2, bmap2->n_eq - n2, 0, 1 + total); + return isl_mat_variable_compression(E2, NULL); + } + if (bmap2->n_eq == n2) { + E1 = isl_mat_sub_alloc6(ctx, bmap1->eq, + n1, bmap1->n_eq - n1, 0, 1 + total); + return isl_mat_variable_compression(E1, NULL); + } + E1 = isl_mat_sub_alloc6(ctx, bmap1->eq, + n1, bmap1->n_eq - n1, 0, 1 + total); + E2 = isl_mat_sub_alloc6(ctx, bmap2->eq, + n2, bmap2->n_eq - n2, 0, 1 + total); + E1 = isl_mat_concat(E1, E2); + bmap = basic_map_from_equalities(isl_basic_map_get_space(bmap1), E1); + bmap = isl_basic_map_gauss(bmap, NULL); + if (!bmap) + return NULL; + E1 = isl_mat_sub_alloc6(ctx, bmap->eq, 0, bmap->n_eq, 0, 1 + total); + V = isl_mat_variable_compression(E1, NULL); + isl_basic_map_free(bmap); + + return V; +} + +/* Extract the stride constraints from "bmap", compressed + * with respect to both the stride constraints in "context" and + * the remaining equality constraints in both "bmap" and "context". + * "bmap_n_eq" is the number of (initial) stride constraints in "bmap". + * "context_n_eq" is the number of (initial) stride constraints in "context". + * + * Let x be all variables in "bmap" (and "context") other than the local + * variables. First compute a variable compression + * + * x = V x' + * + * based on the non-stride equality constraints in "bmap" and "context". + * Consider the stride constraints of "context", + * + * A(x) + B(y) = 0 + * + * with y the local variables and plug in the variable compression, + * resulting in + * + * A(V x') + B(y) = 0 + * + * Use these constraints to compute a parameter compression on x' + * + * x' = T x'' + * + * Now consider the stride constraints of "bmap" + * + * C(x) + D(y) = 0 + * + * and plug in x = V*T x''. + * That is, return A = [C*V*T D]. + */ +static __isl_give isl_mat *extract_compressed_stride_constraints( + __isl_keep isl_basic_map *bmap, int bmap_n_eq, + __isl_keep isl_basic_map *context, int context_n_eq) +{ + int total, n_div; + isl_ctx *ctx; + isl_mat *A, *B, *T, *V; + + total = isl_basic_map_dim(context, isl_dim_all); + n_div = isl_basic_map_dim(context, isl_dim_div); + total -= n_div; + + ctx = isl_basic_map_get_ctx(bmap); + + V = combined_variable_compression(bmap, bmap_n_eq, + context, context_n_eq, total); + + A = isl_mat_sub_alloc6(ctx, context->eq, 0, context_n_eq, 0, 1 + total); + B = isl_mat_sub_alloc6(ctx, context->eq, + 0, context_n_eq, 1 + total, n_div); + A = isl_mat_product(A, isl_mat_copy(V)); + T = isl_mat_parameter_compression_ext(A, B); + T = isl_mat_product(V, T); + + n_div = isl_basic_map_dim(bmap, isl_dim_div); + T = isl_mat_diagonal(T, isl_mat_identity(ctx, n_div)); + + A = isl_mat_sub_alloc6(ctx, bmap->eq, + 0, bmap_n_eq, 0, 1 + total + n_div); + A = isl_mat_product(A, T); + + return A; +} + +/* Remove the prime factors from *g that have an exponent that + * is strictly smaller than the exponent in "c". + * All exponents in *g are known to be smaller than or equal + * to those in "c". + * + * That is, if *g is equal to + * + * p_1^{e_1} p_2^{e_2} ... p_n^{e_n} + * + * and "c" is equal to + * + * p_1^{f_1} p_2^{f_2} ... p_n^{f_n} + * + * then update *g to + * + * p_1^{e_1 * (e_1 = f_1)} p_2^{e_2 * (e_2 = f_2)} ... + * p_n^{e_n * (e_n = f_n)} + * + * If e_i = f_i, then c / *g does not have any p_i factors and therefore + * neither does the gcd of *g and c / *g. + * If e_i < f_i, then the gcd of *g and c / *g has a positive + * power min(e_i, s_i) of p_i with s_i = f_i - e_i among its factors. + * Dividing *g by this gcd therefore strictly reduces the exponent + * of the prime factors that need to be removed, while leaving the + * other prime factors untouched. + * Repeating this process until gcd(*g, c / *g) = 1 therefore + * removes all undesired factors, without removing any others. + */ +static void remove_incomplete_powers(isl_int *g, isl_int c) +{ + isl_int t; + + isl_int_init(t); + for (;;) { + isl_int_divexact(t, c, *g); + isl_int_gcd(t, t, *g); + if (isl_int_is_one(t)) + break; + isl_int_divexact(*g, *g, t); + } + isl_int_clear(t); +} + +/* Reduce the "n" stride constraints in "bmap" based on a copy "A" + * of the same stride constraints in a compressed space that exploits + * all equalities in the context and the other equalities in "bmap". + * + * If the stride constraints of "bmap" are of the form + * + * C(x) + D(y) = 0 + * + * then A is of the form + * + * B(x') + D(y) = 0 + * + * If any of these constraints involves only a single local variable y, + * then the constraint appears as + * + * f(x) + m y_i = 0 + * + * in "bmap" and as + * + * h(x') + m y_i = 0 + * + * in "A". + * + * Let g be the gcd of m and the coefficients of h. + * Then, in particular, g is a divisor of the coefficients of h and + * + * f(x) = h(x') + * + * is known to be a multiple of g. + * If some prime factor in m appears with the same exponent in g, + * then it can be removed from m because f(x) is already known + * to be a multiple of g and therefore in particular of this power + * of the prime factors. + * Prime factors that appear with a smaller exponent in g cannot + * be removed from m. + * Let g' be the divisor of g containing all prime factors that + * appear with the same exponent in m and g, then + * + * f(x) + m y_i = 0 + * + * can be replaced by + * + * f(x) + m/g' y_i' = 0 + * + * Note that (if g' != 1) this changes the explicit representation + * of y_i to that of y_i', so the integer division at position i + * is marked unknown and later recomputed by a call to + * isl_basic_map_gauss. + */ +static __isl_give isl_basic_map *reduce_stride_constraints( + __isl_take isl_basic_map *bmap, int n, __isl_keep isl_mat *A) +{ + int i; + int total, n_div; + int any = 0; + isl_int gcd; + + if (!bmap || !A) + return isl_basic_map_free(bmap); + + total = isl_basic_map_dim(bmap, isl_dim_all); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + total -= n_div; + + isl_int_init(gcd); + for (i = 0; i < n; ++i) { + int div; + + div = isl_seq_first_non_zero(bmap->eq[i] + 1 + total, n_div); + if (div < 0) + isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal, + "equality constraints modified unexpectedly", + goto error); + if (isl_seq_first_non_zero(bmap->eq[i] + 1 + total + div + 1, + n_div - div - 1) != -1) + continue; + if (isl_mat_row_gcd(A, i, &gcd) < 0) + goto error; + if (isl_int_is_one(gcd)) + continue; + remove_incomplete_powers(&gcd, bmap->eq[i][1 + total + div]); + if (isl_int_is_one(gcd)) + continue; + isl_int_divexact(bmap->eq[i][1 + total + div], + bmap->eq[i][1 + total + div], gcd); + bmap = isl_basic_map_mark_div_unknown(bmap, div); + if (!bmap) + goto error; + any = 1; + } + isl_int_clear(gcd); + + if (any) + bmap = isl_basic_map_gauss(bmap, NULL); + + return bmap; +error: + isl_int_clear(gcd); + isl_basic_map_free(bmap); + return NULL; +} + +/* Simplify the stride constraints in "bmap" based on + * the remaining equality constraints in "bmap" and all equality + * constraints in "context". + * Only do this if both "bmap" and "context" have stride constraints. + * + * First extract a copy of the stride constraints in "bmap" in a compressed + * space exploiting all the other equality constraints and then + * use this compressed copy to simplify the original stride constraints. + */ +static __isl_give isl_basic_map *gist_strides(__isl_take isl_basic_map *bmap, + __isl_keep isl_basic_map *context) +{ + int bmap_n_eq, context_n_eq; + isl_mat *A; + + if (!bmap || !context) + return isl_basic_map_free(bmap); + + bmap_n_eq = n_div_eq(bmap); + context_n_eq = n_div_eq(context); + + if (bmap_n_eq < 0 || context_n_eq < 0) + return isl_basic_map_free(bmap); + if (bmap_n_eq == 0 || context_n_eq == 0) + return bmap; + + A = extract_compressed_stride_constraints(bmap, bmap_n_eq, + context, context_n_eq); + bmap = reduce_stride_constraints(bmap, bmap_n_eq, A); + + isl_mat_free(A); + + return bmap; +} + /* Return a basic map that has the same intersection with "context" as "bmap" * and that is as "simple" as possible. * @@ -2828,6 +3193,10 @@ error: * this form that are most obviously redundant with respect to * the context. We also remove those div constraints that are * redundant with respect to the other constraints in the result. + * + * The stride constraints among the equality constraints in "bmap" are + * also simplified with respecting to the other equality constraints + * in "bmap" and with respect to all equality constraints in "context". */ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap, struct isl_basic_map *context) @@ -2886,6 +3255,7 @@ struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap, bset = isl_basic_set_free(bset); eq_bmap = isl_basic_map_overlying_set(eq, isl_basic_map_copy(bmap)); + eq_bmap = gist_strides(eq_bmap, context); eq_bmap = isl_basic_map_remove_shifted_constraints(eq_bmap, context); bmap = isl_basic_map_overlying_set(bset, bmap); bmap = isl_basic_map_intersect(bmap, eq_bmap); @@ -3121,7 +3491,7 @@ static __isl_give isl_map *replace_by_disjunct(__isl_take isl_map *map, /* Remove the constraints in "context" from "map". * If any of the disjuncts in the result turns out to be the universe, - * the return this universe. + * then return this universe. * "context" is assumed to have explicit representations * for all local variables. */ @@ -3394,25 +3764,38 @@ int isl_basic_set_plain_is_disjoint(__isl_keep isl_basic_set *bset1, (struct isl_basic_map *)bset2); } -/* Are "map1" and "map2" obviously disjoint? - * - * If one of them is empty or if they live in different spaces (ignoring - * parameters), then they are clearly disjoint. - * - * If they have different parameters, then we skip any further tests. - * - * If they are obviously equal, but not obviously empty, then we will - * not be able to detect if they are disjoint. +/* Does "test" hold for all pairs of basic maps in "map1" and "map2"? + */ +static isl_bool all_pairs(__isl_keep isl_map *map1, __isl_keep isl_map *map2, + isl_bool (*test)(__isl_keep isl_basic_map *bmap1, + __isl_keep isl_basic_map *bmap2)) +{ + int i, j; + + if (!map1 || !map2) + return isl_bool_error; + + for (i = 0; i < map1->n; ++i) { + for (j = 0; j < map2->n; ++j) { + isl_bool d = test(map1->p[i], map2->p[j]); + if (d != isl_bool_true) + return d; + } + } + + return isl_bool_true; +} + +/* Are "map1" and "map2" obviously disjoint, based on information + * that can be derived without looking at the individual basic maps? * - * Otherwise we check if each basic map in "map1" is obviously disjoint - * from each basic map in "map2". + * In particular, if one of them is empty or if they live in different spaces + * (ignoring parameters), then they are clearly disjoint. */ -isl_bool isl_map_plain_is_disjoint(__isl_keep isl_map *map1, +static isl_bool isl_map_plain_is_disjoint_global(__isl_keep isl_map *map1, __isl_keep isl_map *map2) { - int i, j; isl_bool disjoint; - isl_bool intersect; isl_bool match; if (!map1 || !map2) @@ -3436,6 +3819,34 @@ isl_bool isl_map_plain_is_disjoint(__isl_keep isl_map *map1, if (match < 0 || !match) return match < 0 ? isl_bool_error : isl_bool_true; + return isl_bool_false; +} + +/* Are "map1" and "map2" obviously disjoint? + * + * If one of them is empty or if they live in different spaces (ignoring + * parameters), then they are clearly disjoint. + * This is checked by isl_map_plain_is_disjoint_global. + * + * If they have different parameters, then we skip any further tests. + * + * If they are obviously equal, but not obviously empty, then we will + * not be able to detect if they are disjoint. + * + * Otherwise we check if each basic map in "map1" is obviously disjoint + * from each basic map in "map2". + */ +isl_bool isl_map_plain_is_disjoint(__isl_keep isl_map *map1, + __isl_keep isl_map *map2) +{ + isl_bool disjoint; + isl_bool intersect; + isl_bool match; + + disjoint = isl_map_plain_is_disjoint_global(map1, map2); + if (disjoint < 0 || disjoint) + return disjoint; + match = isl_space_match(map1->dim, isl_dim_param, map2->dim, isl_dim_param); if (match < 0 || !match) @@ -3445,31 +3856,24 @@ isl_bool isl_map_plain_is_disjoint(__isl_keep isl_map *map1, if (intersect < 0 || intersect) return intersect < 0 ? isl_bool_error : isl_bool_false; - for (i = 0; i < map1->n; ++i) { - for (j = 0; j < map2->n; ++j) { - isl_bool d = isl_basic_map_plain_is_disjoint(map1->p[i], - map2->p[j]); - if (d != isl_bool_true) - return d; - } - } - return isl_bool_true; + return all_pairs(map1, map2, &isl_basic_map_plain_is_disjoint); } /* Are "map1" and "map2" disjoint? * * They are disjoint if they are "obviously disjoint" or if one of them * is empty. Otherwise, they are not disjoint if one of them is universal. - * If none of these cases apply, we compute the intersection and see if - * the result is empty. + * If the two inputs are (obviously) equal and not empty, then they are + * not disjoint. + * If none of these cases apply, then check if all pairs of basic maps + * are disjoint. */ isl_bool isl_map_is_disjoint(__isl_keep isl_map *map1, __isl_keep isl_map *map2) { isl_bool disjoint; isl_bool intersect; - isl_map *test; - disjoint = isl_map_plain_is_disjoint(map1, map2); + disjoint = isl_map_plain_is_disjoint_global(map1, map2); if (disjoint < 0 || disjoint) return disjoint; @@ -3489,11 +3893,11 @@ isl_bool isl_map_is_disjoint(__isl_keep isl_map *map1, __isl_keep isl_map *map2) if (intersect < 0 || intersect) return intersect < 0 ? isl_bool_error : isl_bool_false; - test = isl_map_intersect(isl_map_copy(map1), isl_map_copy(map2)); - disjoint = isl_map_is_empty(test); - isl_map_free(test); + intersect = isl_map_plain_is_equal(map1, map2); + if (intersect < 0 || intersect) + return isl_bool_not(intersect); - return disjoint; + return all_pairs(map1, map2, &isl_basic_map_is_disjoint); } /* Are "bmap1" and "bmap2" disjoint? @@ -4239,7 +4643,8 @@ static __isl_give isl_basic_map *fix_cst_lower(__isl_take isl_basic_map *bmap, return isl_basic_map_drop_redundant_divs(bmap); } -/* Remove divs that are not strictly needed. +/* Remove divs that are not strictly needed based on the inequality + * constraints. * In particular, if a div only occurs positively (or negatively) * in constraints, then it can simply be dropped. * Also, if a div occurs in only two constraints and if moreover @@ -4280,8 +4685,8 @@ static __isl_give isl_basic_map *fix_cst_lower(__isl_take isl_basic_map *bmap, * If any divs are left after these simple checks then we move on * to more complicated cases in drop_more_redundant_divs. */ -struct isl_basic_map *isl_basic_map_drop_redundant_divs( - struct isl_basic_map *bmap) +static __isl_give isl_basic_map *isl_basic_map_drop_redundant_divs_ineq( + __isl_take isl_basic_map *bmap) { int i, j; unsigned off; @@ -4394,6 +4799,177 @@ error: return NULL; } +/* Consider the coefficients at "c" as a row vector and replace + * them with their product with "T". "T" is assumed to be a square matrix. + */ +static isl_stat preimage(isl_int *c, __isl_keep isl_mat *T) +{ + int n; + isl_ctx *ctx; + isl_vec *v; + + if (!T) + return isl_stat_error; + n = isl_mat_rows(T); + if (isl_seq_first_non_zero(c, n) == -1) + return isl_stat_ok; + ctx = isl_mat_get_ctx(T); + v = isl_vec_alloc(ctx, n); + if (!v) + return isl_stat_error; + isl_seq_swp_or_cpy(v->el, c, n); + v = isl_vec_mat_product(v, isl_mat_copy(T)); + if (!v) + return isl_stat_error; + isl_seq_swp_or_cpy(c, v->el, n); + isl_vec_free(v); + + return isl_stat_ok; +} + +/* Plug in T for the variables in "bmap" starting at "pos". + * T is a linear unimodular matrix, i.e., without constant term. + */ +static __isl_give isl_basic_map *isl_basic_map_preimage_vars( + __isl_take isl_basic_map *bmap, unsigned pos, __isl_take isl_mat *T) +{ + int i; + unsigned n, total; + + bmap = isl_basic_map_cow(bmap); + if (!bmap || !T) + goto error; + + n = isl_mat_cols(T); + if (n != isl_mat_rows(T)) + isl_die(isl_mat_get_ctx(T), isl_error_invalid, + "expecting square matrix", goto error); + + total = isl_basic_map_dim(bmap, isl_dim_all); + if (pos + n > total || pos + n < pos) + isl_die(isl_mat_get_ctx(T), isl_error_invalid, + "invalid range", goto error); + + for (i = 0; i < bmap->n_eq; ++i) + if (preimage(bmap->eq[i] + 1 + pos, T) < 0) + goto error; + for (i = 0; i < bmap->n_ineq; ++i) + if (preimage(bmap->ineq[i] + 1 + pos, T) < 0) + goto error; + for (i = 0; i < bmap->n_div; ++i) { + if (!isl_basic_map_div_is_known(bmap, i)) + continue; + if (preimage(bmap->div[i] + 1 + 1 + pos, T) < 0) + goto error; + } + + isl_mat_free(T); + return bmap; +error: + isl_basic_map_free(bmap); + isl_mat_free(T); + return NULL; +} + +/* Remove divs that are not strictly needed. + * + * First look for an equality constraint involving two or more + * existentially quantified variables without an explicit + * representation. Replace the combination that appears + * in the equality constraint by a single existentially quantified + * variable such that the equality can be used to derive + * an explicit representation for the variable. + * If there are no more such equality constraints, then continue + * with isl_basic_map_drop_redundant_divs_ineq. + * + * In particular, if the equality constraint is of the form + * + * f(x) + \sum_i c_i a_i = 0 + * + * with a_i existentially quantified variable without explicit + * representation, then apply a transformation on the existentially + * quantified variables to turn the constraint into + * + * f(x) + g a_1' = 0 + * + * with g the gcd of the c_i. + * In order to easily identify which existentially quantified variables + * have a complete explicit representation, i.e., without being defined + * in terms of other existentially quantified variables without + * an explicit representation, the existentially quantified variables + * are first sorted. + * + * The variable transformation is computed by extending the row + * [c_1/g ... c_n/g] to a unimodular matrix, obtaining the transformation + * + * [a_1'] [c_1/g ... c_n/g] [ a_1 ] + * [a_2'] [ a_2 ] + * ... = U .... + * [a_n'] [ a_n ] + * + * with [c_1/g ... c_n/g] representing the first row of U. + * The inverse of U is then plugged into the original constraints. + * The call to isl_basic_map_simplify makes sure the explicit + * representation for a_1' is extracted from the equality constraint. + */ +__isl_give isl_basic_map *isl_basic_map_drop_redundant_divs( + __isl_take isl_basic_map *bmap) +{ + int first; + int i; + unsigned o_div, n_div; + int l; + isl_ctx *ctx; + isl_mat *T; + + if (!bmap) + return NULL; + if (isl_basic_map_divs_known(bmap)) + return isl_basic_map_drop_redundant_divs_ineq(bmap); + if (bmap->n_eq == 0) + return isl_basic_map_drop_redundant_divs_ineq(bmap); + bmap = isl_basic_map_sort_divs(bmap); + if (!bmap) + return NULL; + + first = isl_basic_map_first_unknown_div(bmap); + if (first < 0) + return isl_basic_map_free(bmap); + + o_div = isl_basic_map_offset(bmap, isl_dim_div); + n_div = isl_basic_map_dim(bmap, isl_dim_div); + + for (i = 0; i < bmap->n_eq; ++i) { + l = isl_seq_first_non_zero(bmap->eq[i] + o_div + first, + n_div - (first)); + if (l < 0) + continue; + l += first; + if (isl_seq_first_non_zero(bmap->eq[i] + o_div + l + 1, + n_div - (l + 1)) == -1) + continue; + break; + } + if (i >= bmap->n_eq) + return isl_basic_map_drop_redundant_divs_ineq(bmap); + + ctx = isl_basic_map_get_ctx(bmap); + T = isl_mat_alloc(ctx, n_div - l, n_div - l); + if (!T) + return isl_basic_map_free(bmap); + isl_seq_cpy(T->row[0], bmap->eq[i] + o_div + l, n_div - l); + T = isl_mat_normalize_row(T, 0); + T = isl_mat_unimodular_complete(T, 1); + T = isl_mat_right_inverse(T); + + for (i = l; i < n_div; ++i) + bmap = isl_basic_map_mark_div_unknown(bmap, i); + bmap = isl_basic_map_preimage_vars(bmap, o_div - 1 + l, T); + bmap = isl_basic_map_simplify(bmap); + + return isl_basic_map_drop_redundant_divs(bmap); +} + struct isl_basic_set *isl_basic_set_drop_redundant_divs( struct isl_basic_set *bset) { diff --git a/polly/lib/External/isl/isl_map_to_basic_set.c b/polly/lib/External/isl/isl_map_to_basic_set.c index 6755d52bcdd..f0c8d505c6c 100644 --- a/polly/lib/External/isl/isl_map_to_basic_set.c +++ b/polly/lib/External/isl/isl_map_to_basic_set.c @@ -2,9 +2,13 @@ #include <isl/map.h> #include <isl/set.h> -#define KEY_BASE map -#define KEY_EQUAL isl_map_plain_is_equal -#define VAL_BASE basic_set -#define VAL_EQUAL isl_basic_set_plain_is_equal +#define ISL_KEY isl_map +#define ISL_VAL isl_basic_set +#define ISL_HMAP_SUFFIX map_to_basic_set +#define ISL_HMAP isl_map_to_basic_set +#define ISL_KEY_IS_EQUAL isl_map_plain_is_equal +#define ISL_VAL_IS_EQUAL isl_basic_set_plain_is_equal +#define ISL_KEY_PRINT isl_printer_print_map +#define ISL_VAL_PRINT isl_printer_print_basic_set -#include <isl_hmap_templ.c> +#include <isl/hmap_templ.c> diff --git a/polly/lib/External/isl/isl_mat.c b/polly/lib/External/isl/isl_mat.c index efb22310e55..b0af75e2d57 100644 --- a/polly/lib/External/isl/isl_mat.c +++ b/polly/lib/External/isl/isl_mat.c @@ -24,6 +24,29 @@ isl_ctx *isl_mat_get_ctx(__isl_keep isl_mat *mat) return mat ? mat->ctx : NULL; } +/* Return a hash value that digests "mat". + */ +uint32_t isl_mat_get_hash(__isl_keep isl_mat *mat) +{ + int i; + uint32_t hash; + + if (!mat) + return 0; + + hash = isl_hash_init(); + isl_hash_byte(hash, mat->n_row & 0xFF); + isl_hash_byte(hash, mat->n_col & 0xFF); + for (i = 0; i < mat->n_row; ++i) { + uint32_t row_hash; + + row_hash = isl_seq_get_hash(mat->row[i], mat->n_col); + isl_hash_hash(hash, row_hash); + } + + return hash; +} + struct isl_mat *isl_mat_alloc(struct isl_ctx *ctx, unsigned n_row, unsigned n_col) { @@ -1669,6 +1692,22 @@ error: return NULL; } +/* Return the gcd of the elements in row "row" of "mat" in *gcd. + * Return isl_stat_ok on success and isl_stat_error on failure. + */ +isl_stat isl_mat_row_gcd(__isl_keep isl_mat *mat, int row, isl_int *gcd) +{ + if (!mat) + return isl_stat_error; + + if (row < 0 || row >= mat->n_row) + isl_die(isl_mat_get_ctx(mat), isl_error_invalid, + "row out of range", return isl_stat_error); + isl_seq_gcd(mat->row[row], mat->n_col, gcd); + + return isl_stat_ok; +} + void isl_mat_gcd(__isl_keep isl_mat *mat, isl_int *gcd) { int i; diff --git a/polly/lib/External/isl/isl_mat_private.h b/polly/lib/External/isl/isl_mat_private.h index 566634d352b..fd808ed0e26 100644 --- a/polly/lib/External/isl/isl_mat_private.h +++ b/polly/lib/External/isl/isl_mat_private.h @@ -20,6 +20,8 @@ struct isl_mat { struct isl_blk block; }; +uint32_t isl_mat_get_hash(__isl_keep isl_mat *mat); + __isl_give isl_mat *isl_mat_sub_alloc(__isl_keep isl_mat *mat, unsigned first_row, unsigned n_row, unsigned first_col, unsigned n_col); __isl_give isl_mat *isl_mat_sub_alloc6(isl_ctx *ctx, isl_int **row, @@ -37,6 +39,8 @@ __isl_give isl_vec *isl_mat_get_row(__isl_keep isl_mat *mat, unsigned row); int isl_mat_is_scaled_identity(__isl_keep isl_mat *mat); +isl_stat isl_mat_row_gcd(__isl_keep isl_mat *mat, int row, isl_int *gcd); + void isl_mat_col_mul(struct isl_mat *mat, int dst_col, isl_int f, int src_col); void isl_mat_col_submul(struct isl_mat *mat, int dst_col, isl_int f, int src_col); diff --git a/polly/lib/External/isl/isl_morph.c b/polly/lib/External/isl/isl_morph.c index 92215af667f..1917148c50a 100644 --- a/polly/lib/External/isl/isl_morph.c +++ b/polly/lib/External/isl/isl_morph.c @@ -352,32 +352,6 @@ __isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_set *bset) id, isl_mat_copy(id)); } -/* Given a matrix that maps a (possibly) parametric domain to - * a parametric domain, add in rows that map the "nparam" parameters onto - * themselves. - */ -static __isl_give isl_mat *insert_parameter_rows(__isl_take isl_mat *mat, - unsigned nparam) -{ - int i; - - if (nparam == 0) - return mat; - if (!mat) - return NULL; - - mat = isl_mat_insert_rows(mat, 1, nparam); - if (!mat) - return NULL; - - for (i = 0; i < nparam; ++i) { - isl_seq_clr(mat->row[1 + i], mat->n_col); - isl_int_set(mat->row[1 + i][1 + i], mat->row[0][0]); - } - - return mat; -} - /* Construct a basic set described by the "n" equalities of "bset" starting * at "first". */ @@ -411,10 +385,6 @@ error: * a morphishm that maps the basic set to a lower-dimensional space. * Specifically, the morphism reduces the number of dimensions of type "type". * - * This function is a slight generalization of isl_mat_variable_compression - * in that it allows the input to be parametric and that it allows for the - * compression of either parameters or set variables. - * * We first select the equalities of interest, that is those that involve * variables of type "type" and no later variables. * Denote those equalities as @@ -424,35 +394,14 @@ error: * where C(p) depends on the parameters if type == isl_dim_set and * is a constant if type == isl_dim_param. * - * First compute the (left) Hermite normal form of M, + * Use isl_mat_final_variable_compression to construct a compression * - * M [U1 U2] = M U = H = [H1 0] - * or - * M = H Q = [H1 0] [Q1] - * [Q2] - * - * with U, Q unimodular, Q = U^{-1} (and H lower triangular). - * Define the transformed variables as - * - * x = [U1 U2] [ x1' ] = [U1 U2] [Q1] x - * [ x2' ] [Q2] - * - * The equalities then become + * x = T x' * - * -C(p) + H1 x1' = 0 or x1' = H1^{-1} C(p) = C'(p) + * x' = Q x * - * If the denominator of the constant term does not divide the - * the common denominator of the parametric terms, then every - * integer point is mapped to a non-integer point and then the original set has no - * integer solutions (since the x' are a unimodular transformation - * of the x). In this case, an empty morphism is returned. - * Otherwise, the transformation is given by - * - * x = U1 H1^{-1} C(p) + U2 x2' - * - * The inverse transformation is simply - * - * x2' = Q2 x + * If T is a zero-column matrix, then the set of equality constraints + * do not admit a solution. In this case, an empty morphism is returned. * * Both matrices are extended to map the full original space to the full * compressed space. @@ -466,7 +415,7 @@ __isl_give isl_morph *isl_basic_set_variable_compression( unsigned nrest; int f_eq, n_eq; isl_space *dim; - isl_mat *H, *U, *Q, *C = NULL, *H1, *U1, *U2; + isl_mat *E, *Q, *C; isl_basic_set *dom, *ran; if (!bset) @@ -491,58 +440,17 @@ __isl_give isl_morph *isl_basic_set_variable_compression( if (n_eq == 0) return isl_morph_identity(bset); - H = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, otype, ntype); - H = isl_mat_left_hermite(H, 0, &U, &Q); - if (!H || !U || !Q) - goto error; - Q = isl_mat_drop_rows(Q, 0, n_eq); - Q = isl_mat_diagonal(isl_mat_identity(bset->ctx, otype), Q); - Q = isl_mat_diagonal(Q, isl_mat_identity(bset->ctx, nrest)); - C = isl_mat_alloc(bset->ctx, 1 + n_eq, otype); - if (!C) - goto error; - isl_int_set_si(C->row[0][0], 1); - isl_seq_clr(C->row[0] + 1, otype - 1); - isl_mat_sub_neg(C->ctx, C->row + 1, bset->eq + f_eq, n_eq, 0, 0, otype); - H1 = isl_mat_sub_alloc(H, 0, H->n_row, 0, H->n_row); - H1 = isl_mat_lin_to_aff(H1); - C = isl_mat_inverse_product(H1, C); - if (!C) - goto error; - isl_mat_free(H); - - if (!isl_int_is_one(C->row[0][0])) { - int i; - isl_int g; - - isl_int_init(g); - for (i = 0; i < n_eq; ++i) { - isl_seq_gcd(C->row[1 + i] + 1, otype - 1, &g); - isl_int_gcd(g, g, C->row[0][0]); - if (!isl_int_is_divisible_by(C->row[1 + i][0], g)) - break; - } - isl_int_clear(g); - - if (i < n_eq) { - isl_mat_free(C); - isl_mat_free(U); - isl_mat_free(Q); - return isl_morph_empty(bset); - } - - C = isl_mat_normalize(C); + E = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, 0, orest); + C = isl_mat_final_variable_compression(E, otype - 1, &Q); + if (!Q) + C = isl_mat_free(C); + if (C && C->n_col == 0) { + isl_mat_free(C); + isl_mat_free(Q); + return isl_morph_empty(bset); } - U1 = isl_mat_sub_alloc(U, 0, U->n_row, 0, n_eq); - U1 = isl_mat_lin_to_aff(U1); - U2 = isl_mat_sub_alloc(U, 0, U->n_row, n_eq, U->n_row - n_eq); - U2 = isl_mat_lin_to_aff(U2); - isl_mat_free(U); - - C = isl_mat_product(U1, C); - C = isl_mat_aff_direct_sum(C, U2); - C = insert_parameter_rows(C, otype - 1); + Q = isl_mat_diagonal(Q, isl_mat_identity(bset->ctx, nrest)); C = isl_mat_diagonal(C, isl_mat_identity(bset->ctx, nrest)); dim = isl_space_copy(bset->dim); @@ -552,12 +460,6 @@ __isl_give isl_morph *isl_basic_set_variable_compression( dom = copy_equalities(bset, f_eq, n_eq); return isl_morph_alloc(dom, ran, Q, C); -error: - isl_mat_free(C); - isl_mat_free(H); - isl_mat_free(U); - isl_mat_free(Q); - return NULL; } /* Construct a parameter compression for "bset". diff --git a/polly/lib/External/isl/isl_multi_cmp.c b/polly/lib/External/isl/isl_multi_cmp.c new file mode 100644 index 00000000000..a99d3707a57 --- /dev/null +++ b/polly/lib/External/isl/isl_multi_cmp.c @@ -0,0 +1,40 @@ +/* + * Copyright 2016 Sven Verdoolaege + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege + */ + +#include <isl_multi_macro.h> + +/* Compare two multi expressions. + * + * Return -1 if "multi1" is "smaller" than "multi2", 1 if "multi1" is "greater" + * than "multi2" and 0 if they are equal. + */ +int FN(MULTI(BASE),plain_cmp)(__isl_keep MULTI(BASE) *multi1, + __isl_keep MULTI(BASE) *multi2) +{ + int i; + int cmp; + + if (multi1 == multi2) + return 0; + if (!multi1) + return -1; + if (!multi2) + return 1; + + cmp = isl_space_cmp(multi1->space, multi2->space); + if (cmp != 0) + return cmp; + + for (i = 0; i < multi1->n; ++i) { + cmp = FN(EL,plain_cmp)(multi1->p[i], multi2->p[i]); + if (cmp != 0) + return cmp; + } + + return 0; +} diff --git a/polly/lib/External/isl/isl_multi_hash.c b/polly/lib/External/isl/isl_multi_hash.c new file mode 100644 index 00000000000..b4bb6c321a0 --- /dev/null +++ b/polly/lib/External/isl/isl_multi_hash.c @@ -0,0 +1,30 @@ +/* + * Copyright 2016 Sven Verdoolaege + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege + */ + +#include <isl_multi_macro.h> +#include <isl/hash.h> + +/* Return a hash value that digests "multi". + */ +uint32_t FN(MULTI(BASE),get_hash)(__isl_keep MULTI(BASE) *multi) +{ + int i; + uint32_t hash; + + if (!multi) + return 0; + + hash = isl_hash_init(); + for (i = 0; i < multi->n; ++i) { + uint32_t el_hash; + el_hash = FN(EL,get_hash)(multi->p[i]); + isl_hash_hash(hash, el_hash); + } + + return hash; +} diff --git a/polly/lib/External/isl/isl_output.c b/polly/lib/External/isl/isl_output.c index aeb7a98ebac..a894cf8d775 100644 --- a/polly/lib/External/isl/isl_output.c +++ b/polly/lib/External/isl/isl_output.c @@ -1134,7 +1134,8 @@ static int defining_equality(__isl_keep isl_basic_map *eq, * data->user is assumed to be an isl_basic_map keeping track of equalities. * * If the current dimension is defined by these equalities, then print - * the corresponding expression. Otherwise, print the name of the dimension. + * the corresponding expression, assigned to the name of the dimension + * if there is any. Otherwise, print the name of the dimension. */ static __isl_give isl_printer *print_dim_eq(__isl_take isl_printer *p, struct isl_print_space_data *data, unsigned pos) @@ -1144,6 +1145,11 @@ static __isl_give isl_printer *print_dim_eq(__isl_take isl_printer *p, j = defining_equality(eq, data->space, data->type, pos); if (j >= 0) { + if (isl_space_has_dim_name(data->space, data->type, pos)) { + p = print_name(data->space, p, data->type, pos, + data->latex); + p = isl_printer_print_str(p, " = "); + } pos += 1 + isl_space_offset(data->space, data->type); p = print_affine_of_len(eq->dim, NULL, p, eq->eq[j], pos); } else { diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c index 277912ad8db..3772abf6794 100644 --- a/polly/lib/External/isl/isl_polynomial.c +++ b/polly/lib/External/isl/isl_polynomial.c @@ -23,6 +23,7 @@ #include <isl_mat_private.h> #include <isl_vec_private.h> #include <isl_range.h> +#include <isl_local.h> #include <isl_local_space_private.h> #include <isl_aff_private.h> #include <isl_val_private.h> @@ -67,6 +68,57 @@ __isl_keep struct isl_upoly_rec *isl_upoly_as_rec(__isl_keep struct isl_upoly *u return (struct isl_upoly_rec *)up; } +/* Compare two polynomials. + * + * Return -1 if "up1" is "smaller" than "up2", 1 if "up1" is "greater" + * than "up2" and 0 if they are equal. + */ +static int isl_upoly_plain_cmp(__isl_keep struct isl_upoly *up1, + __isl_keep struct isl_upoly *up2) +{ + int i; + struct isl_upoly_rec *rec1, *rec2; + + if (up1 == up2) + return 0; + if (!up1) + return -1; + if (!up2) + return 1; + if (up1->var != up2->var) + return up1->var - up2->var; + + if (isl_upoly_is_cst(up1)) { + struct isl_upoly_cst *cst1, *cst2; + int cmp; + + cst1 = isl_upoly_as_cst(up1); + cst2 = isl_upoly_as_cst(up2); + if (!cst1 || !cst2) + return 0; + cmp = isl_int_cmp(cst1->n, cst2->n); + if (cmp != 0) + return cmp; + return isl_int_cmp(cst1->d, cst2->d); + } + + rec1 = isl_upoly_as_rec(up1); + rec2 = isl_upoly_as_rec(up2); + if (!rec1 || !rec2) + return 0; + + if (rec1->n != rec2->n) + return rec1->n - rec2->n; + + for (i = 0; i < rec1->n; ++i) { + int cmp = isl_upoly_plain_cmp(rec1->p[i], rec2->p[i]); + if (cmp != 0) + return cmp; + } + + return 0; +} + isl_bool isl_upoly_is_equal(__isl_keep struct isl_upoly *up1, __isl_keep struct isl_upoly *up2) { @@ -1892,6 +1944,34 @@ error: return NULL; } +/* Compare two quasi-polynomials. + * + * Return -1 if "qp1" is "smaller" than "qp2", 1 if "qp1" is "greater" + * than "qp2" and 0 if they are equal. + */ +int isl_qpolynomial_plain_cmp(__isl_keep isl_qpolynomial *qp1, + __isl_keep isl_qpolynomial *qp2) +{ + int cmp; + + if (qp1 == qp2) + return 0; + if (!qp1) + return -1; + if (!qp2) + return 1; + + cmp = isl_space_cmp(qp1->dim, qp2->dim); + if (cmp != 0) + return cmp; + + cmp = isl_local_cmp(qp1->div, qp2->div); + if (cmp != 0) + return cmp; + + return isl_upoly_plain_cmp(qp1->upoly, qp2->upoly); +} + /* Is "qp1" obviously equal to "qp2"? * * NaN is not equal to anything, not even to another NaN. diff --git a/polly/lib/External/isl/isl_polynomial_private.h b/polly/lib/External/isl/isl_polynomial_private.h index 7b7ef190ef0..17b1a2d11e7 100644 --- a/polly/lib/External/isl/isl_polynomial_private.h +++ b/polly/lib/External/isl/isl_polynomial_private.h @@ -139,6 +139,9 @@ __isl_give isl_qpolynomial *isl_qpolynomial_add_on_domain( __isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2); +int isl_qpolynomial_plain_cmp(__isl_keep isl_qpolynomial *qp1, + __isl_keep isl_qpolynomial *qp2); + int isl_qpolynomial_degree(__isl_keep isl_qpolynomial *poly); __isl_give isl_qpolynomial *isl_qpolynomial_coeff( __isl_keep isl_qpolynomial *poly, @@ -183,6 +186,9 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain( __isl_take isl_qpolynomial_fold *fold1, __isl_take isl_qpolynomial_fold *fold2); +int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1, + __isl_keep isl_qpolynomial_fold *fold2); + __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain( __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max); diff --git a/polly/lib/External/isl/isl_printer.c b/polly/lib/External/isl/isl_printer.c index 6b76390be0e..f297b7b322e 100644 --- a/polly/lib/External/isl/isl_printer.c +++ b/polly/lib/External/isl/isl_printer.c @@ -755,6 +755,8 @@ __isl_give isl_printer *isl_printer_yaml_end_mapping( __isl_give isl_printer *isl_printer_yaml_start_sequence( __isl_take isl_printer *p) { + if (!p) + return NULL; p = enter_state(p, p->yaml_style == ISL_YAML_STYLE_BLOCK); p = push_state(p, isl_yaml_sequence_first_start); if (!p) diff --git a/polly/lib/External/isl/isl_pw_hash.c b/polly/lib/External/isl/isl_pw_hash.c new file mode 100644 index 00000000000..4d121c07986 --- /dev/null +++ b/polly/lib/External/isl/isl_pw_hash.c @@ -0,0 +1,33 @@ +/* + * Copyright 2016 Sven Verdoolaege + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege + */ + +#include <isl_pw_macro.h> +#include <isl/hash.h> + +/* Return a hash value that digests "pw". + */ +uint32_t FN(PW,get_hash)(__isl_keep PW *pw) +{ + int i; + uint32_t hash; + + if (!pw) + return 0; + + hash = isl_hash_init(); + for (i = 0; i < pw->n; ++i) { + uint32_t set_hash, el_hash; + + set_hash = isl_set_get_hash(pw->p[i].set); + isl_hash_hash(hash, set_hash); + el_hash = FN(EL,get_hash)(pw->p[i].FIELD); + isl_hash_hash(hash, el_hash); + } + + return hash; +} diff --git a/polly/lib/External/isl/isl_pw_macro.h b/polly/lib/External/isl/isl_pw_macro.h new file mode 100644 index 00000000000..f445df6729e --- /dev/null +++ b/polly/lib/External/isl/isl_pw_macro.h @@ -0,0 +1,4 @@ +#define xFN(TYPE,NAME) TYPE ## _ ## NAME +#define FN(TYPE,NAME) xFN(TYPE,NAME) +#define xS(TYPE,NAME) struct TYPE ## _ ## NAME +#define S(TYPE,NAME) xS(TYPE,NAME) diff --git a/polly/lib/External/isl/isl_pw_templ.c b/polly/lib/External/isl/isl_pw_templ.c index f7106cf6bcd..a9b4404ce72 100644 --- a/polly/lib/External/isl/isl_pw_templ.c +++ b/polly/lib/External/isl/isl_pw_templ.c @@ -12,12 +12,10 @@ */ #include <isl/aff.h> +#include <isl_sort.h> #include <isl_val_private.h> -#define xFN(TYPE,NAME) TYPE ## _ ## NAME -#define FN(TYPE,NAME) xFN(TYPE,NAME) -#define xS(TYPE,NAME) struct TYPE ## _ ## NAME -#define S(TYPE,NAME) xS(TYPE,NAME) +#include <isl_pw_macro.h> #ifdef HAS_TYPE __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, @@ -1046,30 +1044,76 @@ __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw, &FN(PW,gist_params_aligned)); } -__isl_give PW *FN(PW,coalesce)(__isl_take PW *pw) +/* Return -1 if the piece "p1" should be sorted before "p2" + * and 1 if it should be sorted after "p2". + * Return 0 if they do not need to be sorted in a specific order. + * + * The two pieces are compared on the basis of their function value expressions. + */ +static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg) +{ + struct FN(PW,piece) const *pc1 = p1; + struct FN(PW,piece) const *pc2 = p2; + + return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD); +} + +/* Sort the pieces of "pw" according to their function value + * expressions and then combine pairs of adjacent pieces with + * the same such expression. + * + * The sorting is performed in place because it does not + * change the meaning of "pw", but care needs to be + * taken not to change any possible other copies of "pw" + * in case anything goes wrong. + */ +__isl_give PW *FN(PW,sort)(__isl_take PW *pw) { int i, j; + isl_set *set; if (!pw) return NULL; - if (pw->n == 0) + if (pw->n <= 1) return pw; - - for (i = pw->n - 1; i >= 0; --i) { - for (j = i - 1; j >= 0; --j) { - if (!FN(EL,plain_is_equal)(pw->p[i].FIELD, - pw->p[j].FIELD)) - continue; - pw->p[j].set = isl_set_union(pw->p[j].set, - pw->p[i].set); - FN(EL,free)(pw->p[i].FIELD); - if (i != pw->n - 1) - pw->p[i] = pw->p[pw->n - 1]; - pw->n--; - break; - } - if (j >= 0) + if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]), + &FN(PW,sort_field_cmp), NULL) < 0) + return FN(PW,free)(pw); + for (i = pw->n - 1; i >= 1; --i) { + if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD)) continue; + set = isl_set_union(isl_set_copy(pw->p[i - 1].set), + isl_set_copy(pw->p[i].set)); + if (!set) + return FN(PW,free)(pw); + isl_set_free(pw->p[i].set); + FN(EL,free)(pw->p[i].FIELD); + isl_set_free(pw->p[i - 1].set); + pw->p[i - 1].set = set; + for (j = i + 1; j < pw->n; ++j) + pw->p[j - 1] = pw->p[j]; + pw->n--; + } + + return pw; +} + +/* Coalesce the domains of "pw". + * + * Prior to the actual coalescing, first sort the pieces such that + * pieces with the same function value expression are combined + * into a single piece, the combined domain of which can then + * be coalesced. + */ +__isl_give PW *FN(PW,coalesce)(__isl_take PW *pw) +{ + int i; + + pw = FN(PW,sort)(pw); + if (!pw) + return NULL; + + for (i = 0; i < pw->n; ++i) { pw->p[i].set = isl_set_coalesce(pw->p[i].set); if (!pw->p[i].set) goto error; @@ -1884,23 +1928,21 @@ __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v) return FN(PW,mul_isl_int)(pw, v); } -static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2) -{ - isl_set *set1 = *(isl_set * const *)p1; - isl_set *set2 = *(isl_set * const *)p2; - - return isl_set_plain_cmp(set1, set2); -} - -/* We normalize in place, but if anything goes wrong we need +/* Apply some normalization to "pw". + * In particular, sort the pieces according to their function value + * expressions, combining pairs of adjacent pieces with + * the same such expression, and then normalize the domains of the pieces. + * + * We normalize in place, but if anything goes wrong we need * to return NULL, so we need to make sure we don't change the - * meaning of any possible other copies of map. + * meaning of any possible other copies of "pw". */ __isl_give PW *FN(PW,normalize)(__isl_take PW *pw) { - int i, j; + int i; isl_set *set; + pw = FN(PW,sort)(pw); if (!pw) return NULL; for (i = 0; i < pw->n; ++i) { @@ -1910,24 +1952,6 @@ __isl_give PW *FN(PW,normalize)(__isl_take PW *pw) isl_set_free(pw->p[i].set); pw->p[i].set = set; } - qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp)); - for (i = pw->n - 1; i >= 1; --i) { - if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set)) - continue; - if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD)) - continue; - set = isl_set_union(isl_set_copy(pw->p[i - 1].set), - isl_set_copy(pw->p[i].set)); - if (!set) - return FN(PW,free)(pw); - isl_set_free(pw->p[i].set); - FN(EL,free)(pw->p[i].FIELD); - isl_set_free(pw->p[i - 1].set); - pw->p[i - 1].set = set; - for (j = i + 1; j < pw->n; ++j) - pw->p[j - 1] = pw->p[j]; - pw->n--; - } return pw; } diff --git a/polly/lib/External/isl/isl_pw_union_opt.c b/polly/lib/External/isl/isl_pw_union_opt.c new file mode 100644 index 00000000000..c10126a3e92 --- /dev/null +++ b/polly/lib/External/isl/isl_pw_union_opt.c @@ -0,0 +1,253 @@ +/* + * Copyright 2011 INRIA Saclay + * Copyright 2012 Ecole Normale Superieure + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, + * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, + * 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + */ + +#include <isl_pw_macro.h> + +/* Given a function "cmp" that returns the set of elements where + * "el1" is "better" than "el2", return this set. + */ +static __isl_give isl_set *FN(PW,better)(__isl_keep EL *el1, __isl_keep EL *el2, + __isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2)) +{ + return cmp(FN(EL,copy)(el1), FN(EL,copy)(el2)); +} + +/* Return a list containing the domains of the pieces of "pw". + */ +static __isl_give isl_set_list *FN(PW,extract_domains)(__isl_keep PW *pw) +{ + int i; + isl_ctx *ctx; + isl_set_list *list; + + if (!pw) + return NULL; + ctx = FN(PW,get_ctx)(pw); + list = isl_set_list_alloc(ctx, pw->n); + for (i = 0; i < pw->n; ++i) + list = isl_set_list_add(list, isl_set_copy(pw->p[i].set)); + + return list; +} + +/* Given sets B ("set"), C ("better") and A' ("out"), return + * + * (B \cap C) \cup ((B \setminus C) \setminus A') + */ +static __isl_give isl_set *FN(PW,better_or_out)(__isl_take isl_set *set, + __isl_take isl_set *better, __isl_take isl_set *out) +{ + isl_set *set_better, *set_out; + + set_better = isl_set_intersect(isl_set_copy(set), isl_set_copy(better)); + set_out = isl_set_subtract(isl_set_subtract(set, better), out); + + return isl_set_union(set_better, set_out); +} + +/* Given sets A ("set"), C ("better") and B' ("out"), return + * + * (A \setminus C) \cup ((A \cap C) \setminus B') + */ +static __isl_give isl_set *FN(PW,worse_or_out)(__isl_take isl_set *set, + __isl_take isl_set *better, __isl_take isl_set *out) +{ + isl_set *set_worse, *set_out; + + set_worse = isl_set_subtract(isl_set_copy(set), isl_set_copy(better)); + set_out = isl_set_subtract(isl_set_intersect(set, better), out); + + return isl_set_union(set_worse, set_out); +} + +/* Given two piecewise expressions "pw1" and "pw2", replace their domains + * by the sets in "list1" and "list2" and combine the results into + * a single piecewise expression. + * The pieces of "pw1" and "pw2" are assumed to have been sorted + * according to the function value expressions. + * The pieces of the result are also sorted in this way. + * + * Run through the pieces of "pw1" and "pw2" in order until they + * have both been exhausted, picking the piece from "pw1" or "pw2" + * depending on which should come first, together with the corresponding + * domain from "list1" or "list2". In cases where the next pieces + * in both "pw1" and "pw2" have the same function value expression, + * construct only a single piece in the result with as domain + * the union of the domains in "list1" and "list2". + */ +static __isl_give PW *FN(PW,merge)(__isl_take PW *pw1, __isl_take PW *pw2, + __isl_take isl_set_list *list1, __isl_take isl_set_list *list2) +{ + int i, j; + PW *res; + + if (!pw1 || !pw2) + goto error; + + res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->n + pw2->n); + + i = 0; j = 0; + while (i < pw1->n || j < pw2->n) { + int cmp; + isl_set *set; + EL *el; + + if (i < pw1->n && j < pw2->n) + cmp = FN(EL,plain_cmp)(pw1->p[i].FIELD, + pw2->p[j].FIELD); + else + cmp = i < pw1->n ? -1 : 1; + + if (cmp < 0) { + set = isl_set_list_get_set(list1, i); + el = FN(EL,copy)(pw1->p[i].FIELD); + ++i; + } else if (cmp > 0) { + set = isl_set_list_get_set(list2, j); + el = FN(EL,copy)(pw2->p[j].FIELD); + ++j; + } else { + set = isl_set_union(isl_set_list_get_set(list1, i), + isl_set_list_get_set(list2, j)); + el = FN(EL,copy)(pw1->p[i].FIELD); + ++i; + ++j; + } + res = FN(PW,add_piece)(res, set, el); + } + + isl_set_list_free(list1); + isl_set_list_free(list2); + FN(PW,free)(pw1); + FN(PW,free)(pw2); + return res; +error: + isl_set_list_free(list1); + isl_set_list_free(list2); + FN(PW,free)(pw1); + FN(PW,free)(pw2); + return NULL; +} + +/* Given a function "cmp" that returns the set of elements where + * "el1" is "better" than "el2", return a piecewise + * expression defined on the union of the definition domains + * of "pw1" and "pw2" that maps to the "best" of "pw1" and + * "pw2" on each cell. If only one of the two input functions + * is defined on a given cell, then it is considered the best. + * + * Run through all pairs of pieces in "pw1" and "pw2". + * If the domains of these pieces intersect, then the intersection + * needs to be distributed over the two pieces based on "cmp". + * Let C be the set where the piece from "pw2" is better (according to "cmp") + * than the piece from "pw1". Let A be the domain of the piece from "pw1" and + * B the domain of the piece from "pw2". + * + * The elements in C need to be removed from A, except for those parts + * that lie outside of B. That is, + * + * A <- (A \setminus C) \cup ((A \cap C) \setminus B') + * + * Conversely, the elements in B need to be restricted to C, except + * for those parts that lie outside of A. That is + * + * B <- (B \cap C) \cup ((B \setminus C) \setminus A') + * + * Since all pairs of pieces are considered, the domains are updated + * several times. A and B refer to these updated domains + * (kept track of in "list1" and "list2"), while A' and B' refer + * to the original domains of the pieces. It is safe to use these + * original domains because the difference between, say, A' and A is + * the domains of pw2-pieces that have been removed before and + * those domains are disjoint from B. A' is used instead of A + * because the continued updating of A may result in this domain + * getting broken up into more disjuncts. + * + * After the updated domains have been computed, the result is constructed + * from "pw1", "pw2", "list1" and "list2". If there are any pieces + * in "pw1" and "pw2" with the same function value expression, then + * they are combined into a single piece in the result. + * In order to be able to do this efficiently, the pieces of "pw1" and + * "pw2" are first sorted according to their function value expressions. + */ +static __isl_give PW *FN(PW,union_opt_cmp)( + __isl_take PW *pw1, __isl_take PW *pw2, + __isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2)) +{ + int i, j; + PW *res = NULL; + isl_ctx *ctx; + isl_set *set = NULL; + isl_set_list *list1 = NULL, *list2 = NULL; + + if (!pw1 || !pw2) + goto error; + + ctx = isl_space_get_ctx(pw1->dim); + if (!isl_space_is_equal(pw1->dim, pw2->dim)) + isl_die(ctx, isl_error_invalid, + "arguments should live in the same space", goto error); + + if (FN(PW,is_empty)(pw1)) { + FN(PW,free)(pw1); + return pw2; + } + + if (FN(PW,is_empty)(pw2)) { + FN(PW,free)(pw2); + return pw1; + } + + pw1 = FN(PW,sort)(pw1); + pw2 = FN(PW,sort)(pw2); + if (!pw1 || !pw2) + goto error; + + list1 = FN(PW,extract_domains)(pw1); + list2 = FN(PW,extract_domains)(pw2); + + for (i = 0; i < pw1->n; ++i) { + for (j = 0; j < pw2->n; ++j) { + isl_bool disjoint; + isl_set *better, *set_i, *set_j; + + disjoint = isl_set_is_disjoint(pw1->p[i].set, + pw2->p[j].set); + if (disjoint < 0) + goto error; + if (disjoint) + continue; + better = FN(PW,better)(pw2->p[j].FIELD, + pw1->p[i].FIELD, cmp); + set_i = isl_set_list_get_set(list1, i); + set_j = isl_set_copy(pw2->p[j].set); + set_i = FN(PW,worse_or_out)(set_i, + isl_set_copy(better), set_j); + list1 = isl_set_list_set_set(list1, i, set_i); + set_i = isl_set_copy(pw1->p[i].set); + set_j = isl_set_list_get_set(list2, j); + set_j = FN(PW,better_or_out)(set_j, better, set_i); + list2 = isl_set_list_set_set(list2, j, set_j); + } + } + + res = FN(PW,merge)(pw1, pw2, list1, list2); + + return res; +error: + isl_set_list_free(list1); + isl_set_list_free(list2); + FN(PW,free)(pw1); + FN(PW,free)(pw2); + isl_set_free(set); + return FN(PW,free)(res); +} diff --git a/polly/lib/External/isl/isl_sample.c b/polly/lib/External/isl/isl_sample.c index 71dec424df0..8d2db7dc2a7 100644 --- a/polly/lib/External/isl/isl_sample.c +++ b/polly/lib/External/isl/isl_sample.c @@ -1214,6 +1214,8 @@ __isl_give isl_basic_map *isl_basic_map_sample(__isl_take isl_basic_map *bmap) isl_vec_free(sample_vec); return isl_basic_map_set_to_empty(bmap); } + isl_vec_free(bmap->sample); + bmap->sample = isl_vec_copy(sample_vec); bset = isl_basic_set_from_vec(sample_vec); return isl_basic_map_overlying_set(bset, bmap); error: diff --git a/polly/lib/External/isl/isl_scheduler.c b/polly/lib/External/isl/isl_scheduler.c index 22e88c65f98..0052cdd16ab 100644 --- a/polly/lib/External/isl/isl_scheduler.c +++ b/polly/lib/External/isl/isl_scheduler.c @@ -1583,9 +1583,13 @@ static __isl_give isl_basic_set *intra_coefficients( isl_set *delta; isl_map *key; isl_basic_set *coef; + isl_maybe_isl_basic_set m; - if (isl_map_to_basic_set_has(graph->intra_hmap, map)) - return isl_map_to_basic_set_get(graph->intra_hmap, map); + m = isl_map_to_basic_set_try_get(graph->intra_hmap, map); + if (m.valid < 0 || m.valid) { + isl_map_free(map); + return m.value; + } key = isl_map_copy(map); if (node->compressed) { @@ -1620,9 +1624,13 @@ static __isl_give isl_basic_set *inter_coefficients( isl_set *set; isl_map *key; isl_basic_set *coef; + isl_maybe_isl_basic_set m; - if (isl_map_to_basic_set_has(graph->inter_hmap, map)) - return isl_map_to_basic_set_get(graph->inter_hmap, map); + m = isl_map_to_basic_set_try_get(graph->inter_hmap, map); + if (m.valid < 0 || m.valid) { + isl_map_free(map); + return m.value; + } key = isl_map_copy(map); if (edge->src->compressed) diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index e6bbace3d3d..61668651149 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -1383,8 +1383,31 @@ struct { { "{ [0, 0, q, p] : -5 <= q <= 5 and p >= 0 }", "{ [a, b, q, p] : b >= 1 + a }", "{ [a, b, q, p] : false }" }, + { "[n] -> { [x] : x = n && x mod 32 = 0 }", + "[n] -> { [x] : x mod 32 = 0 }", + "[n] -> { [x = n] }" }, + { "{ [x] : x mod 6 = 0 }", "{ [x] : x mod 3 = 0 }", + "{ [x] : x mod 2 = 0 }" }, + { "{ [x] : x mod 3200 = 0 }", "{ [x] : x mod 10000 = 0 }", + "{ [x] : x mod 128 = 0 }" }, + { "{ [x] : x mod 3200 = 0 }", "{ [x] : x mod 10 = 0 }", + "{ [x] : x mod 3200 = 0 }" }, + { "{ [a, b, c] : a mod 2 = 0 and a = c }", + "{ [a, b, c] : b mod 2 = 0 and b = c }", + "{ [a, b, c = a] }" }, + { "{ [a, b, c] : a mod 6 = 0 and a = c }", + "{ [a, b, c] : b mod 2 = 0 and b = c }", + "{ [a, b, c = a] : a mod 3 = 0 }" }, }; +/* Check that isl_set_gist behaves as expected. + * + * For the test cases in gist_tests, besides checking that the result + * is as expected, also check that applying the gist operation does + * not modify the input set (an earlier version of isl would do that) and + * that the test case is consistent, i.e., that the gist has the same + * intersection with the context as the input set. + */ static int test_gist(struct isl_ctx *ctx) { int i; @@ -1394,22 +1417,25 @@ static int test_gist(struct isl_ctx *ctx) int equal; for (i = 0; i < ARRAY_SIZE(gist_tests); ++i) { - int equal_input; - isl_set *set1, *set2, *copy; + int equal_input, equal_intersection; + isl_set *set1, *set2, *copy, *context; set1 = isl_set_read_from_str(ctx, gist_tests[i].set); - set2 = isl_set_read_from_str(ctx, gist_tests[i].context); + context = isl_set_read_from_str(ctx, gist_tests[i].context); copy = isl_set_copy(set1); - set1 = isl_set_gist(set1, set2); + set1 = isl_set_gist(set1, isl_set_copy(context)); set2 = isl_set_read_from_str(ctx, gist_tests[i].gist); equal = isl_set_is_equal(set1, set2); isl_set_free(set1); - isl_set_free(set2); set1 = isl_set_read_from_str(ctx, gist_tests[i].set); equal_input = isl_set_is_equal(set1, copy); - isl_set_free(set1); isl_set_free(copy); - if (equal < 0 || equal_input < 0) + set1 = isl_set_intersect(set1, isl_set_copy(context)); + set2 = isl_set_intersect(set2, context); + equal_intersection = isl_set_is_equal(set1, set2); + isl_set_free(set2); + isl_set_free(set1); + if (equal < 0 || equal_input < 0 || equal_intersection < 0) return -1; if (!equal) isl_die(ctx, isl_error_unknown, @@ -1417,6 +1443,9 @@ static int test_gist(struct isl_ctx *ctx) if (!equal_input) isl_die(ctx, isl_error_unknown, "gist modified input", return -1); + if (!equal_input) + isl_die(ctx, isl_error_unknown, + "inconsistent gist test case", return -1); } test_gist_case(ctx, "gist1"); @@ -5823,7 +5852,7 @@ static int test_multi_pw_aff(isl_ctx *ctx) * is empty and would end up in an infinite loop if it didn't test * explicitly for empty basic maps in the outer loop. */ -static int test_simplify(isl_ctx *ctx) +static int test_simplify_1(isl_ctx *ctx) { const char *str; isl_basic_set *bset; @@ -5846,6 +5875,39 @@ static int test_simplify(isl_ctx *ctx) return 0; } +/* Check that the equality in the set description below + * is simplified away. + */ +static int test_simplify_2(isl_ctx *ctx) +{ + const char *str; + isl_basic_set *bset; + isl_bool universe; + + str = "{ [a] : exists e0, e1: 32e1 = 31 + 31a + 31e0 }"; + bset = isl_basic_set_read_from_str(ctx, str); + universe = isl_basic_set_plain_is_universe(bset); + isl_basic_set_free(bset); + + if (universe < 0) + return -1; + if (!universe) + isl_die(ctx, isl_error_unknown, + "equality not simplified away", return -1); + return 0; +} + +/* Some simplification tests. + */ +static int test_simplify(isl_ctx *ctx) +{ + if (test_simplify_1(ctx) < 0) + return -1; + if (test_simplify_2(ctx) < 0) + return -1; + return 0; +} + /* This is a regression test for a bug where isl_tab_basic_map_partial_lexopt * with gbr context would fail to disable the use of the shifted tableau * when transferring equalities for the input to the context, resulting diff --git a/polly/lib/External/isl/isl_union_map.c b/polly/lib/External/isl/isl_union_map.c index cf616c9e3dc..a6863d6d1a0 100644 --- a/polly/lib/External/isl/isl_union_map.c +++ b/polly/lib/External/isl/isl_union_map.c @@ -3820,3 +3820,40 @@ __isl_give isl_union_set *isl_union_set_list_union( isl_union_set_list_free(list); return res; } + +/* Update *hash with the hash value of "map". + */ +static isl_stat add_hash(__isl_take isl_map *map, void *user) +{ + uint32_t *hash = user; + uint32_t map_hash; + + map_hash = isl_map_get_hash(map); + isl_hash_hash(*hash, map_hash); + + isl_map_free(map); + return isl_stat_ok; +} + +/* Return a hash value that digests "umap". + */ +uint32_t isl_union_map_get_hash(__isl_keep isl_union_map *umap) +{ + uint32_t hash; + + if (!umap) + return 0; + + hash = isl_hash_init(); + if (isl_union_map_foreach_map(umap, &add_hash, &hash) < 0) + return 0; + + return hash; +} + +/* Return a hash value that digests "uset". + */ +uint32_t isl_union_set_get_hash(__isl_keep isl_union_set *uset) +{ + return isl_union_map_get_hash(uset); +} diff --git a/polly/lib/External/isl/isl_val.c b/polly/lib/External/isl/isl_val.c index b6307612867..6a62a33ba79 100644 --- a/polly/lib/External/isl/isl_val.c +++ b/polly/lib/External/isl/isl_val.c @@ -356,6 +356,22 @@ isl_ctx *isl_val_get_ctx(__isl_keep isl_val *val) return val ? val->ctx : NULL; } +/* Return a hash value that digests "val". + */ +uint32_t isl_val_get_hash(__isl_keep isl_val *val) +{ + uint32_t hash; + + if (!val) + return 0; + + hash = isl_hash_init(); + hash = isl_int_hash(val->n, hash); + hash = isl_int_hash(val->d, hash); + + return hash; +} + /* Normalize "v". * * In particular, make sure that the denominator of a rational value diff --git a/polly/lib/External/isl/isl_vec.c b/polly/lib/External/isl/isl_vec.c index 0ed6f7d55e5..747f89eb0cf 100644 --- a/polly/lib/External/isl/isl_vec.c +++ b/polly/lib/External/isl/isl_vec.c @@ -20,6 +20,16 @@ isl_ctx *isl_vec_get_ctx(__isl_keep isl_vec *vec) return vec ? vec->ctx : NULL; } +/* Return a hash value that digests "vec". + */ +uint32_t isl_vec_get_hash(__isl_keep isl_vec *vec) +{ + if (!vec) + return 0; + + return isl_seq_get_hash(vec->el, vec->size); +} + struct isl_vec *isl_vec_alloc(struct isl_ctx *ctx, unsigned size) { struct isl_vec *vec; diff --git a/polly/lib/External/isl/isl_vec_private.h b/polly/lib/External/isl/isl_vec_private.h index c3fcd9227a2..be1994b0ee8 100644 --- a/polly/lib/External/isl/isl_vec_private.h +++ b/polly/lib/External/isl/isl_vec_private.h @@ -15,6 +15,8 @@ struct isl_vec { struct isl_blk block; }; +uint32_t isl_vec_get_hash(__isl_keep isl_vec *vec); + __isl_give isl_vec *isl_vec_cow(__isl_take isl_vec *vec); void isl_vec_lcm(struct isl_vec *vec, isl_int *lcm); 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 5fd62076ccc..fa6ff75f0a5 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 = min(2 * c0, 4); c1 <= max(2 * c0, 4); c1 += 1) { + for (int c1 = min(4, 2 * c0); c1 <= max(4, 2 * c0); c1 += 1) { if (c1 == 2 * c0) S1(c0, 2 * c0); if (c1 == 4) diff --git a/polly/lib/External/isl/test_inputs/codegen/correlation.c b/polly/lib/External/isl/test_inputs/codegen/correlation.c new file mode 100644 index 00000000000..d331fae6cd9 --- /dev/null +++ b/polly/lib/External/isl/test_inputs/codegen/correlation.c @@ -0,0 +1,54 @@ +for (int c0 = 0; c0 <= max(0, m - 1); c0 += 32) + if (m >= c0 + 1) + for (int c1 = (n >= 32 && m >= c0 + 2) || (m == 1 && c0 == 0) ? 0 : 32 * n - 32 * floord(31 * n + 31, 32); c1 <= ((n <= -1 && c0 == 0) || (m == 1 && n >= 0 && c0 == 0) ? max(0, n - 1) : n); c1 += 32) + for (int c2 = c0; c2 <= (m >= 2 && c0 + 31 >= m && n >= c1 && c1 + 31 >= n ? 2 * m - 3 : (m >= 2 * c0 + 63 && c1 <= -32 && n >= c1 && c1 + 31 >= n) || (m >= c0 + 32 && 2 * c0 + 62 >= m && n >= c1 && c1 + 31 >= n) || (n >= 0 && c0 >= 32 && m >= 2 * c0 + 63 && c1 == n) || (m >= 63 && n >= 32 && c0 == 0 && c1 == n) ? 2 * c0 + 61 : m - 1); c2 += 32) { + if (c1 >= n) { + if (c0 == 0 && c1 == 0) + for (int c5 = 0; c5 <= min(31, m - c2 - 1); c5 += 1) + S_14(c2 + c5); + if (c1 == n) + for (int c3 = max(0, (c2 / 2) - c0 + 1); c3 <= min(31, m - c0 - 1); c3 += 1) + for (int c5 = max(0, c0 - c2 + c3); c5 <= min(31, 2 * c0 - c2 + 2 * c3 - 1); c5 += 1) + S_29(-c0 + c2 - c3 + c5, c0 + c3); + } else if (c1 >= 0 && m >= c2 + 1) { + for (int c3 = 0; c3 <= min(min(31, m - c0 - 2), -c0 + c2 + 30); c3 += 1) { + for (int c4 = 0; c4 <= min(31, n - c1 - 1); c4 += 1) { + if (c0 == 0 && c2 == 0 && c3 == 0) { + if (c1 == 0 && c4 == 0) + S_14(0); + S_19(c1 + c4, 0); + } + for (int c5 = max(0, c0 - c2 + c3 + 1); c5 <= min(31, m - c2 - 1); c5 += 1) { + if (c0 == 0 && c1 == 0 && c3 == 0 && c4 == 0) + S_14(c2 + c5); + if (c0 == 0 && c3 == 0) + S_19(c1 + c4, c2 + c5); + S_27(c0 + c3, c2 + c5, c1 + c4); + } + } + if (c1 + 31 >= n) + for (int c5 = max(0, c0 - c2 + c3); c5 <= min(31, 2 * c0 - c2 + 2 * c3 - 1); c5 += 1) + S_29(-c0 + c2 - c3 + c5, c0 + c3); + } + if (c0 + 31 >= m && c1 + 31 >= n && c2 == c0) { + for (int c5 = m - c0 - 1; c5 <= min(31, 2 * m - c0 - 3); c5 += 1) + S_29(-m + c0 + c5 + 1, m - 1); + } else if (m >= c0 + 32 && c1 + 31 >= n && c2 == c0) + S_29(0, c0 + 31); + } else if (c1 + 31 >= n && c2 >= m) { + for (int c3 = max(0, (c2 / 2) - c0 + 1); c3 <= min(31, m - c0 - 1); c3 += 1) + for (int c5 = 0; c5 <= min(31, 2 * c0 - c2 + 2 * c3 - 1); c5 += 1) + S_29(-c0 + c2 - c3 + c5, c0 + c3); + } else if (c1 <= -32 && c1 + 31 >= n && m >= c2 + 1) + for (int c3 = max(0, (c2 / 2) - c0 + 1); c3 <= min(31, m - c0 - 1); c3 += 1) + for (int c5 = max(0, c0 - c2 + c3); c5 <= min(31, 2 * c0 - c2 + 2 * c3 - 1); c5 += 1) + S_29(-c0 + c2 - c3 + c5, c0 + c3); + if (m == 1 && c0 == 0 && c1 >= 32 && c2 == 0) { + for (int c4 = 0; c4 <= min(31, n - c1 - 1); c4 += 1) + S_19(c1 + c4, 0); + } else if (m == 1 && n >= 1 && c0 == 0 && c1 == 0 && c2 == 0) { + S_14(0); + for (int c4 = 0; c4 <= min(31, n - 1); c4 += 1) + S_19(c4, 0); + } + } diff --git a/polly/lib/External/isl/test_inputs/codegen/correlation.st b/polly/lib/External/isl/test_inputs/codegen/correlation.st new file mode 100644 index 00000000000..bba5a09d8ef --- /dev/null +++ b/polly/lib/External/isl/test_inputs/codegen/correlation.st @@ -0,0 +1,18 @@ +domain: "[m, n] -> { S_14[j] : 0 <= j < m; S_19[i, j] : 0 <= i < n and 0 <= j < m; S_27[i, j, k] : i >= 0 and i < j < m and 0 <= k < n; S_29[i, j] : i >= 0 and i < j < m }" +child: + context: "[m, n] -> { [] : 0 < m <= 2147483647 and -2147483648 <= n <= 2147483647 }" + child: + schedule: "[m, n] -> [{ S_19[i, j] -> [(0)]; S_29[i, j] -> [(32*floor((j)/32))]; S_27[i, j, k] -> [(32*floor((i)/32))]; S_14[j] -> [(0)] }, { S_19[i, j] -> [(32*floor((i)/32))]; S_29[i, j] -> [(32*floor((n)/32))]; S_27[i, j, k] -> [(32*floor((k)/32))]; S_14[j] -> [(0)] }, { S_19[i, j] -> [(32*floor((j)/32))]; S_29[i, j] -> [(32*floor((i + j)/32))]; S_27[i, j, k] -> [(32*floor((j)/32))]; S_14[j] -> [(32*floor((j)/32))] }]" + permutable: 1 + coincident: [ 1, 1, 1 ] + options: "{ atomic[i0] : 0 <= i0 <= 2 }" + child: + schedule: "[m, n] -> [{ S_19[i, j] -> [(0)]; S_29[i, j] -> [(j - 32*floor((j)/32))]; S_27[i, j, k] -> [(i - 32*floor((i)/32))]; S_14[j] -> [(0)] }, { S_19[i, j] -> [(i - 32*floor((i)/32))]; S_29[i, j] -> [(n - 32*floor((n)/32))]; S_27[i, j, k] -> [(k - 32*floor((k)/32))]; S_14[j] -> [(0)] }, { S_19[i, j] -> [(j - 32*floor((j)/32))]; S_29[i, j] -> [(i + j - 32*floor((i + j)/32))]; S_27[i, j, k] -> [(j - 32*floor((j)/32))]; S_14[j] -> [(j - 32*floor((j)/32))] }]" + permutable: 1 + coincident: [ 1, 1, 1 ] + child: + sequence: + - filter: "[m, n] -> { S_29[i, j] }" + - filter: "[m, n] -> { S_14[j] }" + - filter: "[m, n] -> { S_19[i, j] }" + - filter: "[m, n] -> { S_27[i, j, k] }" diff --git a/polly/lib/External/isl/test_inputs/codegen/shift2.c b/polly/lib/External/isl/test_inputs/codegen/shift2.c index 30ea633b674..5d038f37733 100644 --- a/polly/lib/External/isl/test_inputs/codegen/shift2.c +++ b/polly/lib/External/isl/test_inputs/codegen/shift2.c @@ -27,9 +27,9 @@ for (int c0 = 0; c0 <= 1; c0 += 1) { if (c3 + 30 >= 2 * length && c4 == 0) S_4(c0); } - if (c2 + 16 == length && (length - 16) % 32 == 0) + if (c2 + 16 == length) S_4(c0); - } else if (length == 0) { + } else if (length >= 32) { S_4(c0); } else S_4(c0); diff --git a/polly/test/Isl/Ast/dependence_distance_parametric.ll b/polly/test/Isl/Ast/dependence_distance_parametric.ll index fd408314f3b..101ec572821 100644 --- a/polly/test/Isl/Ast/dependence_distance_parametric.ll +++ b/polly/test/Isl/Ast/dependence_distance_parametric.ll @@ -3,7 +3,7 @@ ; void f(int *A, int N, int c) { ; CHECK: #pragma minimal dependence distance: 1 ; for (int j = 0; j < N; j++) -; CHECK: #pragma minimal dependence distance: c >= 1 ? c : -c +; CHECK: #pragma minimal dependence distance: c <= -1 ? -c : c ; for (int i = 0; i < N; i++) ; A[i + c] = A[i] + 1; ; } diff --git a/polly/test/Isl/Ast/dependence_distance_parametric_expr.ll b/polly/test/Isl/Ast/dependence_distance_parametric_expr.ll index 686ea5c1f93..45340e71fc8 100644 --- a/polly/test/Isl/Ast/dependence_distance_parametric_expr.ll +++ b/polly/test/Isl/Ast/dependence_distance_parametric_expr.ll @@ -3,7 +3,7 @@ ; void f(int *A, int N, int c, int v) { ; CHECK: #pragma minimal dependence distance: 1 ; for (int j = 0; j < N; j++) -; CHECK: #pragma minimal dependence distance: c + v >= 1 ? c + v : -c - v +; CHECK: #pragma minimal dependence distance: c + v <= -1 ? -c - v : c + v ; for (int i = 0; i < N; i++) ; A[i + c + v] = A[i] + 1; ; } |
