diff options
25 files changed, 607 insertions, 456 deletions
diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID index 218fde0ab27..2e979ca877e 100644 --- a/polly/lib/External/isl/GIT_HEAD_ID +++ b/polly/lib/External/isl/GIT_HEAD_ID @@ -1 +1 @@ -isl-0.15-35-ga1e44f0 +isl-0.15-61-gcea776f diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am index 7c660525a85..fa9827186a7 100644 --- a/polly/lib/External/isl/Makefile.am +++ b/polly/lib/External/isl/Makefile.am @@ -106,6 +106,7 @@ libisl_la_SOURCES = \ isl_flow.c \ isl_fold.c \ isl_hash.c \ + isl_hash_private.h \ isl_id_to_ast_expr.c \ isl_id_to_pw_aff.c \ isl_ilp.c \ @@ -322,7 +323,10 @@ EXTRA_DIST = \ print_templ.c \ isl_power_templ.c \ isl_pw_templ.c \ + isl_union_macro.h \ isl_union_templ.c \ + isl_union_eval.c \ + isl_union_neg.c \ isl.py \ doc/CodingStyle \ doc/SubmittingPatches \ diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in index 3c86994f1b2..acd3f02821b 100644 --- a/polly/lib/External/isl/Makefile.in +++ b/polly/lib/External/isl/Makefile.in @@ -179,9 +179,10 @@ am__libisl_la_SOURCES_DIST = mp_get_memory_functions.c isl_int_gmp.h \ isl_convex_hull.c isl_ctx.c isl_ctx_private.h isl_deprecated.c \ isl_dim_map.h isl_dim_map.c isl_equalities.c isl_equalities.h \ isl_factorization.c isl_factorization.h isl_farkas.c isl_ffs.c \ - isl_flow.c isl_fold.c isl_hash.c isl_id_to_ast_expr.c \ - isl_id_to_pw_aff.c isl_ilp.c isl_ilp_private.h isl_input.c \ - isl_int.h isl_local_space_private.h isl_local_space.c isl_lp.c \ + isl_flow.c isl_fold.c isl_hash.c isl_hash_private.h \ + isl_id_to_ast_expr.c isl_id_to_pw_aff.c isl_ilp.c \ + isl_ilp_private.h isl_input.c isl_int.h \ + isl_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 \ @@ -849,6 +850,7 @@ libisl_la_SOURCES = \ isl_flow.c \ isl_fold.c \ isl_hash.c \ + isl_hash_private.h \ isl_id_to_ast_expr.c \ isl_id_to_pw_aff.c \ isl_ilp.c \ @@ -1063,7 +1065,10 @@ EXTRA_DIST = \ print_templ.c \ isl_power_templ.c \ isl_pw_templ.c \ + isl_union_macro.h \ isl_union_templ.c \ + isl_union_eval.c \ + isl_union_neg.c \ isl.py \ doc/CodingStyle \ doc/SubmittingPatches \ diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf Binary files differindex 1d61308c625..ca4b6183858 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 4492e80c461..9eb4559cac5 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -196,7 +196,7 @@ an C<isl_val> instead of an C<isl_qpolynomial>. =item * The function C<isl_band_member_is_zero_distance> has been removed. Essentially the same functionality is available -through C<isl_band_member_is_coincident>, except that is requires +through C<isl_band_member_is_coincident>, except that it requires setting up coincidence constraints. The option C<schedule_outer_zero_distance> has accordingly been replaced by the option C<schedule_outer_coincidence>. diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c index d1d293fdfd3..29bbe5b7f67 100644 --- a/polly/lib/External/isl/isl_aff.c +++ b/polly/lib/External/isl/isl_aff.c @@ -2578,9 +2578,8 @@ __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff) #undef PARTS #define PARTS pw_aff -#define NO_EVAL - #include <isl_union_templ.c> +#include <isl_union_neg.c> static __isl_give isl_set *align_params_pw_pw_set_and( __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2, @@ -4074,9 +4073,8 @@ __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, #undef PARTS #define PARTS pw_multi_aff -#define NO_EVAL - #include <isl_union_templ.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 @@ -5765,8 +5763,7 @@ static __isl_give isl_union_pw_multi_aff *bin_op( goto error; data.upma2 = upma2; - data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->space), - upma1->table.n); + data.res = isl_union_pw_multi_aff_alloc_same_size(upma1); if (isl_hash_table_foreach(upma1->space->ctx, &upma1->table, &bin_entry, &data) < 0) goto error; @@ -6049,40 +6046,26 @@ error: return NULL; } -/* Internal data structure for isl_union_pw_multi_aff_scale_multi_val. - * mv contains the mv argument. - * res collects the results. - */ -struct isl_union_pw_multi_aff_scale_multi_val_data { - isl_multi_val *mv; - isl_union_pw_multi_aff *res; -}; - /* This function is called for each entry of an isl_union_pw_multi_aff. * If the space of the entry matches that of data->mv, - * then apply isl_pw_multi_aff_scale_multi_val and add the result - * to data->res. + * then apply isl_pw_multi_aff_scale_multi_val and return the result. + * Otherwise, return an empty isl_pw_multi_aff. */ -static isl_stat union_pw_multi_aff_scale_multi_val_entry(void **entry, - void *user) +static __isl_give isl_pw_multi_aff *union_pw_multi_aff_scale_multi_val_entry( + __isl_take isl_pw_multi_aff *pma, void *user) { - struct isl_union_pw_multi_aff_scale_multi_val_data *data = user; - isl_pw_multi_aff *pma = *entry; + isl_multi_val *mv = user; if (!pma) - return isl_stat_error; + return NULL; if (!isl_space_tuple_is_equal(pma->dim, isl_dim_out, - data->mv->space, isl_dim_set)) - return isl_stat_ok; - - pma = isl_pw_multi_aff_copy(pma); - pma = isl_pw_multi_aff_scale_multi_val(pma, - isl_multi_val_copy(data->mv)); - data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma); - if (!data->res) - return isl_stat_error; + mv->space, isl_dim_set)) { + isl_space *space = isl_pw_multi_aff_get_space(pma); + isl_pw_multi_aff_free(pma); + return isl_pw_multi_aff_empty(space); + } - return isl_stat_ok; + return isl_pw_multi_aff_scale_multi_val(pma, isl_multi_val_copy(mv)); } /* Scale the elements of "upma" by the corresponding elements of "mv", @@ -6091,8 +6074,6 @@ static isl_stat union_pw_multi_aff_scale_multi_val_entry(void **entry, __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_scale_multi_val( __isl_take isl_union_pw_multi_aff *upma, __isl_take isl_multi_val *mv) { - struct isl_union_pw_multi_aff_scale_multi_val_data data; - upma = isl_union_pw_multi_aff_align_params(upma, isl_multi_val_get_space(mv)); mv = isl_multi_val_align_params(mv, @@ -6100,16 +6081,11 @@ __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_scale_multi_val( if (!upma || !mv) goto error; - data.mv = mv; - data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma->space), - upma->table.n); - if (isl_hash_table_foreach(upma->space->ctx, &upma->table, - &union_pw_multi_aff_scale_multi_val_entry, &data) < 0) - goto error; + return isl_union_pw_multi_aff_transform(upma, + &union_pw_multi_aff_scale_multi_val_entry, mv); isl_multi_val_free(mv); - isl_union_pw_multi_aff_free(upma); - return data.res; + return upma; error: isl_multi_val_free(mv); isl_union_pw_multi_aff_free(upma); @@ -7707,8 +7683,7 @@ __isl_give isl_union_pw_aff *isl_union_pw_aff_pullback_union_pw_multi_aff( ctx = isl_union_pw_aff_get_ctx(upa); data.upma = upma; - space = isl_union_pw_aff_get_space(upa); - data.res = isl_union_pw_aff_alloc(space, upa->table.n); + data.res = isl_union_pw_aff_alloc_same_size(upa); if (isl_hash_table_foreach(ctx, &upa->table, &upa_pb_upma, &data) < 0) data.res = isl_union_pw_aff_free(data.res); diff --git a/polly/lib/External/isl/isl_arg.c b/polly/lib/External/isl/isl_arg.c index d85dccecf4e..4798a421dc2 100644 --- a/polly/lib/External/isl/isl_arg.c +++ b/polly/lib/External/isl/isl_arg.c @@ -812,7 +812,8 @@ static int parse_choice_option(struct isl_arg *decl, char **arg, if (!has_argument && (!arg[1] || arg[1][0] == '-')) { unsigned u = decl->u.choice.default_selected; - *(unsigned *)(((char *)opt) + decl->offset) = u; + if (decl->offset != (size_t) -1) + *(unsigned *)(((char *)opt) + decl->offset) = u; if (decl->u.choice.set) decl->u.choice.set(opt, u); @@ -829,7 +830,8 @@ static int parse_choice_option(struct isl_arg *decl, char **arg, continue; u = decl->u.choice.choice[i].value; - *(unsigned *)(((char *)opt) + decl->offset) = u; + if (decl->offset != (size_t) -1) + *(unsigned *)(((char *)opt) + decl->offset) = u; if (decl->u.choice.set) decl->u.choice.set(opt, u); diff --git a/polly/lib/External/isl/isl_ast_codegen.c b/polly/lib/External/isl/isl_ast_codegen.c index 3c698058ce7..2b791a5935b 100644 --- a/polly/lib/External/isl/isl_ast_codegen.c +++ b/polly/lib/External/isl/isl_ast_codegen.c @@ -1449,6 +1449,7 @@ static __isl_give isl_ast_graft *create_node_scaled( depth = isl_ast_build_get_depth(build); sub_build = isl_ast_build_copy(build); + bounds = isl_basic_set_remove_redundancies(bounds); sub_build = isl_ast_build_set_loop_bounds(sub_build, isl_basic_set_copy(bounds)); degenerate = isl_ast_build_has_value(sub_build); diff --git a/polly/lib/External/isl/isl_fold.c b/polly/lib/External/isl/isl_fold.c index a7f088ad13f..d61d41fd2b1 100644 --- a/polly/lib/External/isl/isl_fold.c +++ b/polly/lib/External/isl/isl_fold.c @@ -685,6 +685,7 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params( #define NO_SUB #include <isl_union_templ.c> +#include <isl_union_eval.c> __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type, __isl_take isl_space *dim) @@ -927,7 +928,6 @@ __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_ __isl_take isl_union_pw_qpolynomial_fold *u, __isl_take isl_pw_qpolynomial_fold *part) { - uint32_t hash; struct isl_hash_table_entry *entry; u = isl_union_pw_qpolynomial_fold_cow(u); @@ -939,10 +939,7 @@ __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_ isl_space_match(part->dim, isl_dim_param, u->space, isl_dim_param), goto error); - hash = isl_space_get_hash(part->dim); - entry = isl_hash_table_find(u->space->ctx, &u->table, hash, - &isl_union_pw_qpolynomial_fold_has_same_domain_space, - part->dim, 1); + entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1); if (!entry) goto error; @@ -1399,15 +1396,12 @@ static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user) isl_ctx *ctx; isl_pw_qpolynomial_fold *pwf; isl_union_pw_qpolynomial_fold **upwf; - uint32_t hash; struct isl_hash_table_entry *entry; upwf = (isl_union_pw_qpolynomial_fold **)user; ctx = pwqp->dim->ctx; - hash = isl_space_get_hash(pwqp->dim); - entry = isl_hash_table_find(ctx, &(*upwf)->table, hash, - &isl_union_pw_qpolynomial_fold_has_same_domain_space, + entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf, pwqp->dim, 1); if (!entry) goto error; @@ -1419,10 +1413,9 @@ static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user) entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf); if (!entry->data) return isl_stat_error; - if (isl_pw_qpolynomial_fold_is_zero(entry->data)) { - isl_pw_qpolynomial_fold_free(entry->data); - isl_hash_table_remove(ctx, &(*upwf)->table, entry); - } + if (isl_pw_qpolynomial_fold_is_zero(entry->data)) + *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry( + *upwf, entry); } return isl_stat_ok; diff --git a/polly/lib/External/isl/isl_hash.c b/polly/lib/External/isl/isl_hash.c index cd444d15e92..ca25d0d5851 100644 --- a/polly/lib/External/isl/isl_hash.c +++ b/polly/lib/External/isl/isl_hash.c @@ -8,7 +8,7 @@ */ #include <stdlib.h> -#include <isl/hash.h> +#include <isl_hash_private.h> #include <isl/ctx.h> #include "isl_config.h" @@ -148,6 +148,13 @@ void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table) free(table); } +/* A dummy entry that can be used to make a distinction between + * a missing entry and an error condition. + * It is used by isl_union_*_find_part_entry. + */ +static struct isl_hash_table_entry none = { 0, NULL }; +struct isl_hash_table_entry *isl_hash_table_entry_none = &none; + struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx, struct isl_hash_table *table, uint32_t key_hash, diff --git a/polly/lib/External/isl/isl_hash_private.h b/polly/lib/External/isl/isl_hash_private.h new file mode 100644 index 00000000000..c6b272ae49c --- /dev/null +++ b/polly/lib/External/isl/isl_hash_private.h @@ -0,0 +1,8 @@ +#ifndef ISL_HASH_PRIVATE +#define ISL_HASH_PRIVATE + +#include <isl/hash.h> + +extern struct isl_hash_table_entry *isl_hash_table_entry_none; + +#endif diff --git a/polly/lib/External/isl/isl_int_sioimath.c b/polly/lib/External/isl/isl_int_sioimath.c index e4bd7952e09..50c159f3e5b 100644 --- a/polly/lib/External/isl/isl_int_sioimath.c +++ b/polly/lib/External/isl/isl_int_sioimath.c @@ -100,7 +100,7 @@ static uint32_t isl_sioimath_smallgcd(int32_t lhs, int32_t rhs) * * Per GMP convention, gcd(0,0)==0 and otherwise always positive. */ -inline void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs, +void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs, isl_sioimath_src rhs) { int32_t lhssmall, rhssmall; diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c index 414e7c0b23e..8c9522ba7c5 100644 --- a/polly/lib/External/isl/isl_polynomial.c +++ b/polly/lib/External/isl/isl_polynomial.c @@ -2818,6 +2818,8 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial( #define PARTS pw_qpolynomial #include <isl_union_templ.c> +#include <isl_union_eval.c> +#include <isl_union_neg.c> int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp) { diff --git a/polly/lib/External/isl/isl_space.c b/polly/lib/External/isl/isl_space.c index 8bc1d879d0d..78e25a3bd2c 100644 --- a/polly/lib/External/isl/isl_space.c +++ b/polly/lib/External/isl/isl_space.c @@ -1897,30 +1897,64 @@ int isl_space_compatible(__isl_keep isl_space *dim1, dim1->n_in + dim1->n_out == dim2->n_in + dim2->n_out; } -static uint32_t isl_hash_dim(uint32_t hash, __isl_keep isl_space *dim) +/* Update "hash" by hashing in "space". + * Changes in this function should be reflected in isl_hash_space_domain. + */ +static uint32_t isl_hash_space(uint32_t hash, __isl_keep isl_space *space) { int i; isl_id *id; - if (!dim) + if (!space) return hash; - isl_hash_byte(hash, dim->nparam % 256); - isl_hash_byte(hash, dim->n_in % 256); - isl_hash_byte(hash, dim->n_out % 256); + isl_hash_byte(hash, space->nparam % 256); + isl_hash_byte(hash, space->n_in % 256); + isl_hash_byte(hash, space->n_out % 256); - for (i = 0; i < dim->nparam; ++i) { - id = get_id(dim, isl_dim_param, i); + for (i = 0; i < space->nparam; ++i) { + id = get_id(space, isl_dim_param, i); hash = isl_hash_id(hash, id); } - id = tuple_id(dim, isl_dim_in); + id = tuple_id(space, isl_dim_in); hash = isl_hash_id(hash, id); - id = tuple_id(dim, isl_dim_out); + id = tuple_id(space, isl_dim_out); hash = isl_hash_id(hash, id); - hash = isl_hash_dim(hash, dim->nested[0]); - hash = isl_hash_dim(hash, dim->nested[1]); + hash = isl_hash_space(hash, space->nested[0]); + hash = isl_hash_space(hash, space->nested[1]); + + return hash; +} + +/* Update "hash" by hashing in the domain of "space". + * The result of this function is equal to the result of applying + * isl_hash_space to the domain of "space". + */ +static uint32_t isl_hash_space_domain(uint32_t hash, + __isl_keep isl_space *space) +{ + int i; + isl_id *id; + + if (!space) + return hash; + + isl_hash_byte(hash, space->nparam % 256); + isl_hash_byte(hash, 0); + isl_hash_byte(hash, space->n_in % 256); + + for (i = 0; i < space->nparam; ++i) { + id = get_id(space, isl_dim_param, i); + hash = isl_hash_id(hash, id); + } + + hash = isl_hash_id(hash, &isl_id_none); + id = tuple_id(space, isl_dim_in); + hash = isl_hash_id(hash, id); + + hash = isl_hash_space(hash, space->nested[0]); return hash; } @@ -1933,7 +1967,24 @@ uint32_t isl_space_get_hash(__isl_keep isl_space *dim) return 0; hash = isl_hash_init(); - hash = isl_hash_dim(hash, dim); + hash = isl_hash_space(hash, dim); + + return hash; +} + +/* Return the hash value of the domain of "space". + * That is, isl_space_get_domain_hash(space) is equal to + * isl_space_get_hash(isl_space_domain(space)). + */ +uint32_t isl_space_get_domain_hash(__isl_keep isl_space *space) +{ + uint32_t hash; + + if (!space) + return 0; + + hash = isl_hash_init(); + hash = isl_hash_space_domain(hash, space); return hash; } diff --git a/polly/lib/External/isl/isl_space_private.h b/polly/lib/External/isl/isl_space_private.h index a07acea7047..6ceba0767f1 100644 --- a/polly/lib/External/isl/isl_space_private.h +++ b/polly/lib/External/isl/isl_space_private.h @@ -28,6 +28,7 @@ __isl_give isl_space *isl_space_underlying(__isl_take isl_space *dim, unsigned n_div); uint32_t isl_space_get_hash(__isl_keep isl_space *dim); +uint32_t isl_space_get_domain_hash(__isl_keep isl_space *space); isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1, __isl_keep isl_space *space2); diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index 5eed5d26cca..250128f0ce4 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -21,6 +21,7 @@ #include <isl_ctx_private.h> #include <isl_map_private.h> #include <isl_aff_private.h> +#include <isl_space_private.h> #include <isl/set.h> #include <isl/flow.h> #include <isl_constraint_private.h> @@ -4384,6 +4385,35 @@ int test_union_pw(isl_ctx *ctx) return 0; } +/* Test that isl_union_pw_qpolynomial_eval picks up the function + * defined over the correct domain space. + */ +static int test_eval(isl_ctx *ctx) +{ + const char *str; + isl_point *pnt; + isl_set *set; + isl_union_pw_qpolynomial *upwqp; + isl_val *v; + int cmp; + + str = "{ A[x] -> x^2; B[x] -> -x^2 }"; + upwqp = isl_union_pw_qpolynomial_read_from_str(ctx, str); + str = "{ A[6] }"; + set = isl_set_read_from_str(ctx, str); + pnt = isl_set_sample_point(set); + v = isl_union_pw_qpolynomial_eval(upwqp, pnt); + cmp = isl_val_cmp_si(v, 36); + isl_val_free(v); + + if (!v) + return -1; + if (cmp != 0) + isl_die(ctx, isl_error_unknown, "unexpected value", return -1); + + return 0; +} + int test_output(isl_ctx *ctx) { char *s; @@ -5885,10 +5915,37 @@ static int test_tile(isl_ctx *ctx) return 0; } +/* Check that the domain hash of a space is equal to the hash + * of the domain of the space. + */ +static int test_domain_hash(isl_ctx *ctx) +{ + isl_map *map; + isl_space *space; + uint32_t hash1, hash2; + + map = isl_map_read_from_str(ctx, "[n] -> { A[B[x] -> C[]] -> D[] }"); + space = isl_map_get_space(map); + isl_map_free(map); + hash1 = isl_space_get_domain_hash(space); + space = isl_space_domain(space); + hash2 = isl_space_get_hash(space); + isl_space_free(space); + + if (!space) + return -1; + if (hash1 != hash2) + isl_die(ctx, isl_error_unknown, + "domain hash not equal to hash of domain", return -1); + + return 0; +} + struct { const char *name; int (*fn)(isl_ctx *ctx); } tests [] = { + { "domain hash", &test_domain_hash }, { "dual", &test_dual }, { "dependence analysis", &test_flow }, { "val", &test_val }, @@ -5925,6 +5982,7 @@ struct { { "schedule tree grouping", &test_schedule_tree_group }, { "tile", &test_tile }, { "union_pw", &test_union_pw }, + { "eval", &test_eval }, { "parse", &test_parse }, { "single-valued", &test_sv }, { "affine hull", &test_affine_hull }, diff --git a/polly/lib/External/isl/isl_union_eval.c b/polly/lib/External/isl/isl_union_eval.c new file mode 100644 index 00000000000..3daab3fc99d --- /dev/null +++ b/polly/lib/External/isl/isl_union_eval.c @@ -0,0 +1,58 @@ +/* + * Copyright 2010 INRIA Saclay + * + * 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 + */ + +#include <isl_union_macro.h> + +/* Is the domain space of "entry" equal to "space"? + */ +static int FN(UNION,has_domain_space)(const void *entry, const void *val) +{ + PART *part = (PART *)entry; + isl_space *space = (isl_space *) val; + + if (isl_space_is_params(space)) + return isl_space_is_set(part->dim); + + return isl_space_tuple_is_equal(part->dim, isl_dim_in, + space, isl_dim_set); +} + +__isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u, + __isl_take isl_point *pnt) +{ + uint32_t hash; + struct isl_hash_table_entry *entry; + isl_space *space; + isl_val *v; + + if (!u || !pnt) + goto error; + + space = isl_space_copy(pnt->dim); + if (!space) + goto error; + hash = isl_space_get_hash(space); + entry = isl_hash_table_find(u->space->ctx, &u->table, + hash, &FN(UNION,has_domain_space), + space, 0); + isl_space_free(space); + if (!entry) { + v = isl_val_zero(isl_point_get_ctx(pnt)); + isl_point_free(pnt); + } else { + v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt); + } + FN(UNION,free)(u); + return v; +error: + FN(UNION,free)(u); + isl_point_free(pnt); + return NULL; +} diff --git a/polly/lib/External/isl/isl_union_macro.h b/polly/lib/External/isl/isl_union_macro.h new file mode 100644 index 00000000000..f445df6729e --- /dev/null +++ b/polly/lib/External/isl/isl_union_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_union_neg.c b/polly/lib/External/isl/isl_union_neg.c new file mode 100644 index 00000000000..4a3e7bb23ff --- /dev/null +++ b/polly/lib/External/isl/isl_union_neg.c @@ -0,0 +1,39 @@ +/* + * Copyright 2010 INRIA Saclay + * + * 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 + */ + +#include <isl_union_macro.h> + +/* Replace *entry by its opposite. + * + * Return isl_stat_ok on success and isl_stat_error on error. + */ +static isl_stat FN(UNION,neg_entry)(void **entry, void *user) +{ + PW **pw = (PW **) entry; + + *pw = FN(PW,neg)(*pw); + + return *pw ? isl_stat_ok : isl_stat_error; +} + +/* Return the opposite of "u". + */ +__isl_give UNION *FN(UNION,neg)(__isl_take UNION *u) +{ + u = FN(UNION,cow)(u); + if (!u) + return NULL; + + if (isl_hash_table_foreach(u->space->ctx, &u->table, + &FN(UNION,neg_entry), NULL) < 0) + return FN(UNION,free)(u); + + return u; +} diff --git a/polly/lib/External/isl/isl_union_templ.c b/polly/lib/External/isl/isl_union_templ.c index f0fb6b38e3c..d6f1743222b 100644 --- a/polly/lib/External/isl/isl_union_templ.c +++ b/polly/lib/External/isl/isl_union_templ.c @@ -10,11 +10,13 @@ * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ -#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_hash_private.h> +#include <isl_union_macro.h> +/* A union of expressions defined over different domain spaces. + * "space" describes the parameters. + * The entries of "table" are keyed on the domain space of the entry. + */ struct UNION { int ref; #ifdef HAS_TYPE @@ -151,47 +153,78 @@ isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u, &FN(UNION,call_on_copy), &data); } -/* Is the space of "entry" equal to "space"? +/* Is the domain space of "entry" equal to the domain of "space"? */ -static int FN(UNION,has_space)(const void *entry, const void *val) +static int FN(UNION,has_same_domain_space)(const void *entry, const void *val) { PART *part = (PART *)entry; isl_space *space = (isl_space *) val; - return isl_space_is_equal(part->dim, space); -} + if (isl_space_is_set(space)) + return isl_space_is_set(part->dim); -/* This function is not currently used by isl_aff.c. - */ -static int FN(UNION,has_domain_space)(const void *entry, const void *val) - __attribute__ ((unused)); + return isl_space_tuple_is_equal(part->dim, isl_dim_in, + space, isl_dim_in); +} -/* Is the domain space of "entry" equal to "space"? +/* Return the entry, if any, in "u" that lives in "space". + * If "reserve" is set, then an entry is created if it does not exist yet. + * Return NULL on error and isl_hash_table_entry_none if no entry was found. + * Note that when "reserve" is set, the function will never return + * isl_hash_table_entry_none. + * + * First look for the entry (if any) with the same domain space. + * If it exists, then check if the range space also matches. */ -static int FN(UNION,has_domain_space)(const void *entry, const void *val) +static struct isl_hash_table_entry *FN(UNION,find_part_entry)( + __isl_keep UNION *u, __isl_keep isl_space *space, int reserve) { - PART *part = (PART *)entry; - isl_space *space = (isl_space *) val; + isl_ctx *ctx; + uint32_t hash; + struct isl_hash_table_entry *entry; + isl_bool equal; + PART *part; - if (isl_space_is_params(space)) - return isl_space_is_set(part->dim); + if (!u || !space) + return NULL; - return isl_space_tuple_is_equal(part->dim, isl_dim_in, - space, isl_dim_set); + ctx = FN(UNION,get_ctx)(u); + hash = isl_space_get_domain_hash(space); + entry = isl_hash_table_find(ctx, &u->table, hash, + &FN(UNION,has_same_domain_space), space, reserve); + if (!entry) + return reserve ? NULL : isl_hash_table_entry_none; + if (reserve && !entry->data) + return entry; + part = entry->data; + equal = isl_space_tuple_is_equal(part->dim, isl_dim_out, + space, isl_dim_out); + if (equal < 0) + return NULL; + if (equal) + return entry; + if (!reserve) + return isl_hash_table_entry_none; + isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, + "union expression can only contain a single " + "expression over a given domain", return NULL); } -/* Is the domain space of "entry" equal to the domain of "space"? +/* Remove "part_entry" from the hash table of "u". */ -static int FN(UNION,has_same_domain_space)(const void *entry, const void *val) +static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u, + struct isl_hash_table_entry *part_entry) { - PART *part = (PART *)entry; - isl_space *space = (isl_space *) val; + isl_ctx *ctx; - if (isl_space_is_set(space)) - return isl_space_is_set(part->dim); + if (!u || !part_entry) + return FN(UNION,free)(u); - return isl_space_tuple_is_equal(part->dim, isl_dim_in, - space, isl_dim_in); + ctx = FN(UNION,get_ctx)(u); + isl_hash_table_remove(ctx, &u->table, part_entry); + FN(PART,free)(part_entry->data); + + return u; } /* Extract the element of "u" living in "space" (ignoring parameters). @@ -202,7 +235,6 @@ static int FN(UNION,has_same_domain_space)(const void *entry, const void *val) __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u, __isl_take isl_space *space) { - uint32_t hash; struct isl_hash_table_entry *entry; if (!u || !space) @@ -216,10 +248,10 @@ __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u, goto error; } - hash = isl_space_get_hash(space); - entry = isl_hash_table_find(u->space->ctx, &u->table, hash, - &FN(UNION,has_space), space, 0); + entry = FN(UNION,find_part_entry)(u, space, 0); if (!entry) + goto error; + if (entry == isl_hash_table_entry_none) #ifdef HAS_TYPE return FN(PART,ZERO)(space, u->type); #else @@ -242,7 +274,6 @@ static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u, __isl_take PART *part, int disjoint) { int empty; - uint32_t hash; struct isl_hash_table_entry *entry; if (!part) @@ -264,26 +295,17 @@ static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u, if (!u) goto error; - hash = isl_space_get_hash(part->dim); - entry = isl_hash_table_find(u->space->ctx, &u->table, hash, - &FN(UNION,has_same_domain_space), - part->dim, 1); + entry = FN(UNION,find_part_entry)(u, part->dim, 1); if (!entry) goto error; if (!entry->data) entry->data = part; else { - PART *entry_part = entry->data; if (disjoint) isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, "additional part should live on separate " "space", goto error); - if (!isl_space_tuple_is_equal(entry_part->dim, isl_dim_out, - part->dim, isl_dim_out)) - isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, - "union expression can only contain a single " - "expression over a given domain", goto error); entry->data = FN(PART,union_add_)(entry->data, FN(PART,copy)(part)); if (!entry->data) @@ -291,10 +313,8 @@ static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u, empty = FN(PART,IS_ZERO)(part); if (empty < 0) goto error; - if (empty) { - FN(PART,free)(entry->data); - isl_hash_table_remove(u->space->ctx, &u->table, entry); - } + if (empty) + u = FN(UNION,remove_part_entry)(u, entry); FN(PART,free)(part); } @@ -314,33 +334,114 @@ __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u, return FN(UNION,add_part_generic)(u, part, 1); } -static isl_stat FN(UNION,add_part)(__isl_take PART *part, void *user) +#ifdef HAS_TYPE +/* Allocate a UNION with the same type and the same size as "u" and + * with space "space". + */ +static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u, + __isl_take isl_space *space) { - UNION **u = (UNION **)user; + if (!u) + space = isl_space_free(space); + return FN(UNION,alloc)(space, u->type, u->table.n); +} +#else +/* Allocate a UNION with the same size as "u" and with space "space". + */ +static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u, + __isl_take isl_space *space) +{ + if (!u) + space = isl_space_free(space); + return FN(UNION,alloc)(space, u->table.n); +} +#endif - *u = FN(FN(UNION,add),PARTS)(*u, part); +/* Allocate a UNION with the same space, the same type (if any) and + * the same size as "u". + */ +static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u) +{ + return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u)); +} + +/* Call "fn" on each part entry of "u". + */ +static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u, + isl_stat (*fn)(void **part, void *user), void *user) +{ + isl_ctx *ctx; + + if (!u) + return isl_stat_error; + ctx = FN(UNION,get_ctx)(u); + return isl_hash_table_foreach(ctx, &u->table, fn, user); +} + +/* Internal data structure for isl_union_*_transform_space. + * "fn' is applied to each entry in the input. + * "res" collects the results. + */ +S(UNION,transform_data) +{ + __isl_give PART *(*fn)(__isl_take PART *part, void *user); + void *user; + + UNION *res; +}; + +/* Apply data->fn to "part" and add the result to data->res. + */ +static isl_stat FN(UNION,transform_entry)(__isl_take PART *part, void *user) +{ + S(UNION,transform_data) *data = (S(UNION,transform_data) *)user; + + part = data->fn(part, data->user); + data->res = FN(FN(UNION,add),PARTS)(data->res, part); + if (!data->res) + return isl_stat_error; return isl_stat_ok; } -__isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u) +/* Return a UNION living in "space" that is obtained by applying "fn" + * to each of the entries in "u". + */ +static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u, + isl_space *space, + __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user) { - UNION *dup; + S(UNION,transform_data) data = { fn, user }; - if (!u) - return NULL; + data.res = FN(UNION,alloc_same_size_on_space)(u, space); + if (FN(FN(UNION,foreach),PARTS)(u, + &FN(UNION,transform_entry), &data) < 0) + data.res = FN(UNION,free)(data.res); + FN(UNION,free)(u); + return data.res; +} -#ifdef HAS_TYPE - dup = FN(UNION,ZERO)(isl_space_copy(u->space), u->type); -#else - dup = FN(UNION,ZERO)(isl_space_copy(u->space)); -#endif - if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,add_part), &dup) < 0) - goto error; - return dup; -error: - FN(UNION,free)(dup); - return NULL; +/* Return a UNION that lives in the same space as "u" and that is obtained + * by applying "fn" to each of the entries in "u". + */ +static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u, + __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user) +{ + return FN(UNION,transform_space)(u, FN(UNION,get_space)(u), fn, user); +} + +/* An isl_union_*_transform callback for use in isl_union_*_dup + * that simply returns "part". + */ +static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user) +{ + return part; +} + +__isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u) +{ + u = FN(UNION,copy)(u); + return FN(UNION,transform)(u, &FN(UNION,copy_part), NULL); } __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u) @@ -377,23 +478,13 @@ __isl_null UNION *FN(UNION,free)(__isl_take UNION *u) return NULL; } -S(UNION,align) { - isl_reordering *exp; - UNION *res; -}; - -static isl_stat FN(UNION,align_entry)(__isl_take PART *part, void *user) +static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user) { - isl_reordering *exp; - S(UNION,align) *data = user; + isl_reordering *exp = user; - exp = isl_reordering_extend_space(isl_reordering_copy(data->exp), + exp = isl_reordering_extend_space(isl_reordering_copy(exp), FN(PART,get_domain_space)(part)); - - data->res = FN(FN(UNION,add),PARTS)(data->res, - FN(PART,realign_domain)(part, exp)); - - return isl_stat_ok; + return FN(PART,realign_domain)(part, exp); } /* Reorder the parameters of "u" according to the given reordering. @@ -401,23 +492,15 @@ static isl_stat FN(UNION,align_entry)(__isl_take PART *part, void *user) static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u, __isl_take isl_reordering *r) { - S(UNION,align) data = { NULL, NULL }; + isl_space *space; if (!u || !r) goto error; -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(isl_space_copy(r->dim), u->type, u->table.n); -#else - data.res = FN(UNION,alloc)(isl_space_copy(r->dim), u->table.n); -#endif - data.exp = r; - if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,align_entry), &data) < 0) - data.res = FN(UNION,free)(data.res); - - isl_reordering_free(data.exp); - FN(UNION,free)(u); - return data.res; + space = isl_space_copy(r->dim); + u = FN(UNION,transform_space)(u, space, &FN(UNION,align_entry), r); + isl_reordering_free(r); + return u; error: FN(UNION,free)(u); isl_reordering_free(r); @@ -529,19 +612,17 @@ S(UNION,match_bin_data) { static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user) { S(UNION,match_bin_data) *data = user; - uint32_t hash; struct isl_hash_table_entry *entry2; isl_space *space; PART *part = *entry; PART *part2; space = FN(PART,get_space)(part); - hash = isl_space_get_hash(space); - entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table, - hash, &FN(UNION,has_same_domain_space), - space, 0); + entry2 = FN(UNION,find_part_entry)(data->u2, space, 0); isl_space_free(space); if (!entry2) + return isl_stat_error; + if (entry2 == isl_hash_table_entry_none) return isl_stat_ok; part2 = entry2->data; @@ -584,12 +665,7 @@ static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1, goto error; data.u2 = u2; -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->type, - u1->table.n); -#else - data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->table.n); -#endif + data.res = FN(UNION,alloc_same_size)(u1); if (isl_hash_table_foreach(u1->space->ctx, &u1->table, &FN(UNION,match_bin_entry), &data) < 0) goto error; @@ -630,23 +706,15 @@ __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2) S(UNION,any_set_data) { isl_set *set; - UNION *res; __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*); }; -static isl_stat FN(UNION,any_set_entry)(void **entry, void *user) +static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part, + void *user) { S(UNION,any_set_data) *data = user; - PW *pw = *entry; - - pw = FN(PW,copy)(pw); - pw = data->fn(pw, isl_set_copy(data->set)); - - data->res = FN(FN(UNION,add),PARTS)(data->res, pw); - if (!data->res) - return isl_stat_error; - return isl_stat_ok; + return data->fn(part, isl_set_copy(data->set)); } /* Update each element of "u" by calling "fn" on the element and "set". @@ -655,7 +723,7 @@ static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u, __isl_take isl_set *set, __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*)) { - S(UNION,any_set_data) data = { NULL, NULL, fn }; + S(UNION,any_set_data) data = { NULL, fn }; u = FN(UNION,align_params)(u, isl_set_get_space(set)); set = isl_set_align_params(set, FN(UNION,get_space)(u)); @@ -664,23 +732,12 @@ static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u, goto error; data.set = set; -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type, - u->table.n); -#else - data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n); -#endif - if (isl_hash_table_foreach(u->space->ctx, &u->table, - &FN(UNION,any_set_entry), &data) < 0) - goto error; - - FN(UNION,free)(u); + u = FN(UNION,transform)(u, &FN(UNION,any_set_entry), &data); isl_set_free(set); - return data.res; + return u; error: FN(UNION,free)(u); isl_set_free(set); - FN(UNION,free)(data.res); return NULL; } @@ -762,12 +819,7 @@ static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u, goto error; data.uset = uset; -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type, - u->table.n); -#else - data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n); -#endif + data.res = FN(UNION,alloc_same_size)(u); if (isl_hash_table_foreach(u->space->ctx, &u->table, &FN(UNION,match_domain_entry), &data) < 0) goto error; @@ -795,31 +847,20 @@ __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u, return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain)); } -/* Internal data structure for isl_union_*_subtract_domain. - * uset is the set that needs to be removed from the domain. - * res collects the results. - */ -S(UNION,subtract_domain_data) { - isl_union_set *uset; - UNION *res; -}; - /* Take the set (which may be empty) in data->uset that lives * in the same space as the domain of "pw", subtract it from the domain - * of "pw" and add the result to data->res. + * of "part" and return the result. */ -static isl_stat FN(UNION,subtract_domain_entry)(__isl_take PW *pw, void *user) +static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part, + void *user) { - S(UNION,subtract_domain_data) *data = user; + isl_union_set *uset = user; isl_space *space; isl_set *set; - space = FN(PW,get_domain_space)(pw); - set = isl_union_set_extract_set(data->uset, space); - pw = FN(PW,subtract_domain)(pw, set); - data->res = FN(FN(UNION,add),PARTS)(data->res, pw); - - return isl_stat_ok; + space = FN(PART,get_domain_space)(part); + set = isl_union_set_extract_set(uset, space); + return FN(PART,subtract_domain)(part, set); } /* Subtract "uset' from the domain of "u". @@ -827,29 +868,9 @@ static isl_stat FN(UNION,subtract_domain_entry)(__isl_take PW *pw, void *user) __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u, __isl_take isl_union_set *uset) { - S(UNION,subtract_domain_data) data; - - if (!u || !uset) - goto error; - - data.uset = uset; -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type, - u->table.n); -#else - data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n); -#endif - if (FN(FN(UNION,foreach),PARTS)(u, - &FN(UNION,subtract_domain_entry), &data) < 0) - data.res = FN(UNION,free)(data.res); - - FN(UNION,free)(u); + u = FN(UNION,transform)(u, &FN(UNION,subtract_domain_entry), uset); isl_union_set_free(uset); - return data.res; -error: - FN(UNION,free)(u); - isl_union_set_free(uset); - return NULL; + return u; } __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u, @@ -860,59 +881,28 @@ __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u, return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist)); } -#ifndef NO_EVAL -__isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u, - __isl_take isl_point *pnt) -{ - uint32_t hash; - struct isl_hash_table_entry *entry; - isl_space *space; - isl_val *v; - - if (!u || !pnt) - goto error; - - space = isl_space_copy(pnt->dim); - if (!space) - goto error; - hash = isl_space_get_hash(space); - entry = isl_hash_table_find(u->space->ctx, &u->table, - hash, &FN(UNION,has_domain_space), - space, 0); - isl_space_free(space); - if (!entry) { - v = isl_val_zero(isl_point_get_ctx(pnt)); - isl_point_free(pnt); - } else { - v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt); - } - FN(UNION,free)(u); - return v; -error: - FN(UNION,free)(u); - isl_point_free(pnt); - return NULL; -} -#endif - +/* Coalesce an entry in a UNION. Coalescing is performed in-place. + * Since the UNION may have several references, the entry is only + * replaced if the coalescing is successful. + */ static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user) { - PW **pw = (PW **)entry; + PART **part_p = (PART **) entry; + PART *part; - *pw = FN(PW,coalesce)(*pw); - if (!*pw) + part = FN(PART,copy)(*part_p); + part = FN(PW,coalesce)(part); + if (!part) return isl_stat_error; + FN(PART,free)(*part_p); + *part_p = part; return isl_stat_ok; } __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u) { - if (!u) - return NULL; - - if (isl_hash_table_foreach(u->space->ctx, &u->table, - &FN(UNION,coalesce_entry), NULL) < 0) + if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0) goto error; return u; @@ -947,6 +937,27 @@ error: return NULL; } +#ifdef HAS_TYPE +/* Negate the type of "u". + */ +static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u) +{ + u = FN(UNION,cow)(u); + if (!u) + return NULL; + u->type = isl_fold_type_negate(u->type); + return u; +} +#else +/* Negate the type of "u". + * Since "u" does not have a type, do nothing. + */ +static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u) +{ + return u; +} +#endif + static isl_stat FN(UNION,mul_isl_int_entry)(void **entry, void *user) { PW **pw = (PW **)entry; @@ -977,13 +988,11 @@ __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v) } u = FN(UNION,cow)(u); + if (isl_int_is_neg(v)) + u = FN(UNION,negate_type)(u); if (!u) return NULL; -#ifdef HAS_TYPE - if (isl_int_is_neg(v)) - u->type = isl_fold_type_negate(u->type); -#endif if (isl_hash_table_foreach(u->space->ctx, &u->table, &FN(UNION,mul_isl_int_entry), &v) < 0) goto error; @@ -1040,13 +1049,11 @@ __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u, "expecting rational factor", goto error); u = FN(UNION,cow)(u); + if (isl_val_is_neg(v)) + u = FN(UNION,negate_type)(u); if (!u) return NULL; -#ifdef HAS_TYPE - if (isl_val_is_neg(v)) - u->type = isl_fold_type_negate(u->type); -#endif if (isl_hash_table_foreach(u->space->ctx, &u->table, &FN(UNION,scale_val_entry), v) < 0) goto error; @@ -1095,13 +1102,11 @@ __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u, "cannot scale down by zero", goto error); u = FN(UNION,cow)(u); + if (isl_val_is_neg(v)) + u = FN(UNION,negate_type)(u); if (!u) return NULL; -#ifdef HAS_TYPE - if (isl_val_is_neg(v)) - u->type = isl_fold_type_negate(u->type); -#endif if (isl_hash_table_foreach(FN(UNION,get_ctx)(u), &u->table, &FN(UNION,scale_down_val_entry), v) < 0) goto error; @@ -1123,16 +1128,15 @@ S(UNION,plain_is_equal_data) static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user) { S(UNION,plain_is_equal_data) *data = user; - uint32_t hash; struct isl_hash_table_entry *entry2; PW *pw = *entry; - hash = isl_space_get_hash(pw->dim); - entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table, - hash, &FN(UNION,has_same_domain_space), - pw->dim, 0); - if (!entry2) { - data->is_equal = isl_bool_false; + entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0); + if (!entry2 || entry2 == isl_hash_table_entry_none) { + if (!entry2) + data->is_equal = isl_bool_error; + else + data->is_equal = isl_bool_false; return isl_stat_error; } @@ -1162,7 +1166,7 @@ isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2) goto error; data.u2 = u2; - if (isl_hash_table_foreach(u1->space->ctx, &u1->table, + if (FN(UNION,foreach_inplace)(u1, &FN(UNION,plain_is_equal_entry), &data) < 0 && data.is_equal) goto error; @@ -1177,61 +1181,23 @@ error: return isl_bool_error; } -#ifndef NO_NEG -/* Replace *entry by its opposite. - * - * Return 0 on success and -1 on error. - */ -static isl_stat FN(UNION,neg_entry)(void **entry, void *user) -{ - PW **pw = (PW **) entry; - - *pw = FN(PW,neg)(*pw); - - return *pw ? isl_stat_ok : isl_stat_error; -} - -/* Return the opposite of "u". - */ -__isl_give UNION *FN(UNION,neg)(__isl_take UNION *u) -{ - u = FN(UNION,cow)(u); - if (!u) - return NULL; - - if (isl_hash_table_foreach(u->space->ctx, &u->table, - &FN(UNION,neg_entry), NULL) < 0) - return FN(UNION,free)(u); - - return u; -} -#endif - /* Internal data structure for isl_union_*_drop_dims. * type, first and n are passed to isl_*_drop_dims. - * res collects the results. */ S(UNION,drop_dims_data) { enum isl_dim_type type; unsigned first; unsigned n; - - UNION *res; }; -/* Drop the parameters specified by "data" from "part" and - * add the results to data->res. +/* Drop the parameters specified by "data" from "part" and return the result. */ -static isl_stat FN(UNION,drop_dims_entry)(__isl_take PART *part, void *user) +static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part, + void *user) { S(UNION,drop_dims_data) *data = user; - part = FN(PART,drop_dims)(part, data->type, data->first, data->n); - data->res = FN(FN(UNION,add),PARTS)(data->res, part); - if (!data->res) - return isl_stat_error; - - return isl_stat_ok; + return FN(PART,drop_dims)(part, data->type, data->first, data->n); } /* Drop the specified parameters from "u". @@ -1253,45 +1219,28 @@ __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u, space = FN(UNION,get_space)(u); space = isl_space_drop_dims(space, type, first, n); -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(space, u->type, u->table.n); -#else - data.res = FN(UNION,alloc)(space, u->table.n); -#endif - if (FN(FN(UNION,foreach),PARTS)(u, - &FN(UNION,drop_dims_entry), &data) < 0) - data.res = FN(UNION,free)(data.res); - - FN(UNION,free)(u); - - return data.res; + return FN(UNION,transform_space)(u, space, &FN(UNION,drop_dims_entry), + &data); } /* Internal data structure for isl_union_*_set_dim_name. * pos is the position of the parameter that needs to be renamed. * s is the new name. - * res collects the results. */ S(UNION,set_dim_name_data) { unsigned pos; const char *s; - - UNION *res; }; /* Change the name of the parameter at position data->pos of "part" to data->s - * and add the result to data->res. + * and return the result. */ -static isl_stat FN(UNION,set_dim_name_entry)(__isl_take PART *part, void *user) +static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part, + void *user) { S(UNION,set_dim_name_data) *data = user; - part = FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s); - data->res = FN(FN(UNION,add),PARTS)(data->res, part); - if (!data->res) - return isl_stat_error; - - return isl_stat_ok; + return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s); } /* Change the name of the parameter at position "pos" to "s". @@ -1313,34 +1262,17 @@ __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u, space = FN(UNION,get_space)(u); space = isl_space_set_dim_name(space, type, pos, s); -#ifdef HAS_TYPE - data.res = FN(UNION,alloc)(space, u->type, u->table.n); -#else - data.res = FN(UNION,alloc)(space, u->table.n); -#endif - - if (FN(FN(UNION,foreach),PARTS)(u, - &FN(UNION,set_dim_name_entry), &data) < 0) - data.res = FN(UNION,free)(data.res); - - FN(UNION,free)(u); - - return data.res; + return FN(UNION,transform_space)(u, space, + &FN(UNION,set_dim_name_entry), &data); } /* Reset the user pointer on all identifiers of parameters and tuples - * of the space of "part" and add the result to *res. + * of the space of "part" and return the result. */ -static isl_stat FN(UNION,reset_user_entry)(__isl_take PART *part, void *user) +static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part, + void *user) { - UNION **res = user; - - part = FN(PART,reset_user)(part); - *res = FN(FN(UNION,add),PARTS)(*res, part); - if (!*res) - return isl_stat_error; - - return isl_stat_ok; + return FN(PART,reset_user)(part); } /* Reset the user pointer on all identifiers of parameters and tuples @@ -1349,23 +1281,9 @@ static isl_stat FN(UNION,reset_user_entry)(__isl_take PART *part, void *user) __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u) { isl_space *space; - UNION *res; - - if (!u) - return NULL; space = FN(UNION,get_space)(u); space = isl_space_reset_user(space); -#ifdef HAS_TYPE - res = FN(UNION,alloc)(space, u->type, u->table.n); -#else - res = FN(UNION,alloc)(space, u->table.n); -#endif - if (FN(FN(UNION,foreach),PARTS)(u, - &FN(UNION,reset_user_entry), &res) < 0) - res = FN(UNION,free)(res); - - FN(UNION,free)(u); - - return res; + return FN(UNION,transform_space)(u, space, &FN(UNION,reset_user_entry), + NULL); } diff --git a/polly/lib/External/isl/ltmain.sh b/polly/lib/External/isl/ltmain.sh index c29db3631ea..bffda54187a 100644 --- a/polly/lib/External/isl/ltmain.sh +++ b/polly/lib/External/isl/ltmain.sh @@ -70,7 +70,7 @@ # compiler: $LTCC # compiler flags: $LTCFLAGS # linker: $LD (gnu? $with_gnu_ld) -# $progname: (GNU libtool) 2.4.2 Debian-2.4.2-1.10ubuntu1 +# $progname: (GNU libtool) 2.4.2 Debian-2.4.2-1.11 # automake: $automake_version # autoconf: $autoconf_version # @@ -80,7 +80,7 @@ PROGRAM=libtool PACKAGE=libtool -VERSION="2.4.2 Debian-2.4.2-1.10ubuntu1" +VERSION="2.4.2 Debian-2.4.2-1.11" TIMESTAMP="" package_revision=1.3337 diff --git a/polly/lib/External/isl/test_inputs/brisebarre.pip b/polly/lib/External/isl/test_inputs/brisebarre.pip index f3decadfd27..5d25dae309b 100644 --- a/polly/lib/External/isl/test_inputs/brisebarre.pip +++ b/polly/lib/External/isl/test_inputs/brisebarre.pip @@ -1,34 +1,34 @@ -# ---------------------- CONTEXT ---------------------- -1 2 -1 0 - --1 - -# ----------------------- DOMAIN ---------------------- -26 6 -1 3 0 0 0 -98300 -1 -3 0 0 0 98308 -1 432 36 6 1 -14757611 -1 -432 -36 -6 -1 14758510 -1 54 9 3 1 -1923190 -1 -54 -9 -3 -1 1923303 -1 48 12 6 3 -1782238 -1 -48 -12 -6 -3 1782339 -1 27 9 6 4 -1045164 -1 -27 -9 -6 -4 1045221 -1 432 180 150 125 -17434139 -1 -432 -180 -150 -125 17435038 -1 6 3 3 3 -252443 -1 -6 -3 -3 -3 252456 -1 432 252 294 343 -18949275 -1 -432 -252 -294 -343 18950174 -1 27 18 24 32 -1234720 -1 -27 -18 -24 -32 1234777 -1 48 36 54 81 -2288453 -1 -48 -36 -54 -81 2288554 -1 54 45 75 125 -2684050 -1 -54 -45 -75 -125 2684163 -1 432 396 726 1331 -22386005 -1 -432 -396 -726 -1331 22386904 -1 3 3 6 12 -162072 -1 -3 -3 -6 -12 162080 +# ---------------------- CONTEXT ----------------------
+1 2
+1 0
+
+-1
+
+# ----------------------- DOMAIN ----------------------
+26 6
+1 3 0 0 0 -98300
+1 -3 0 0 0 98308
+1 432 36 6 1 -14757611
+1 -432 -36 -6 -1 14758510
+1 54 9 3 1 -1923190
+1 -54 -9 -3 -1 1923303
+1 48 12 6 3 -1782238
+1 -48 -12 -6 -3 1782339
+1 27 9 6 4 -1045164
+1 -27 -9 -6 -4 1045221
+1 432 180 150 125 -17434139
+1 -432 -180 -150 -125 17435038
+1 6 3 3 3 -252443
+1 -6 -3 -3 -3 252456
+1 432 252 294 343 -18949275
+1 -432 -252 -294 -343 18950174
+1 27 18 24 32 -1234720
+1 -27 -18 -24 -32 1234777
+1 48 36 54 81 -2288453
+1 -48 -36 -54 -81 2288554
+1 54 45 75 125 -2684050
+1 -54 -45 -75 -125 2684163
+1 432 396 726 1331 -22386005
+1 -432 -396 -726 -1331 22386904
+1 3 3 6 12 -162072
+1 -3 -3 -6 -12 162080
diff --git a/polly/lib/External/isl/test_inputs/codegen/omega/lefur04-0.c b/polly/lib/External/isl/test_inputs/codegen/omega/lefur04-0.c index 124d0f15cb5..72ecbe49f62 100644 --- a/polly/lib/External/isl/test_inputs/codegen/omega/lefur04-0.c +++ b/polly/lib/External/isl/test_inputs/codegen/omega/lefur04-0.c @@ -2,7 +2,7 @@ for (int c0 = 0; c0 <= 3; c0 += 1) for (int c1 = max(2 * c0 - 3, c0 / 2); c1 <= min(3, c0 + 1); c1 += 1) for (int c2 = c0; c2 <= min(min(3, 2 * c0 - c1 + 1), 3 * c1 + 2); c2 += 1) for (int c3 = max(max(max(c1 - (-c1 + 3) / 3, c0 - (-c2 + 3) / 3), c2 - (c2 + 2) / 3), c2 + floord(3 * c1 - c2 - 1, 6)); c3 <= min(3, c0 + c2 / 3 + 1); c3 += 1) - for (int c5 = max(max(max(max(0, 2 * c3 - 4), c1 - (-c1 + 3) / 3), c2 - (c2 + 3) / 3), c3 - (c3 + 3) / 3); c5 <= min(min(c1 + 1, c3), -c2 + 2 * c3 - (c2 + 3) / 3 + 2); c5 += 1) + for (int c5 = max(max(max(max(0, 2 * c3 - 4), c2 - (c2 + 3) / 3), c3 - (c3 + 3) / 3), c1 - (c1 - 2 * c3 + 5) / 5); c5 <= min(min(c1 + 1, c3), -c2 + 2 * c3 - (c2 + 3) / 3 + 2); c5 += 1) for (int c6 = max(max(max(max(max(-200 * c1 + 400 * c3 - 199, 250 * c3 + 1), 1000 * c0 - 500 * c5 - 501), 667 * c0 - 333 * c1 - (c0 + c1 + 3) / 3 - 332), 333 * c1 + c1 / 3), 333 * c2 + (c2 + 1) / 3); c6 <= min(min(min(min(min(min(1000, 500 * c0 + 499), -200 * c1 + 400 * c3 + 400), 500 * c5 + 501), 1000 * c0 - 500 * c5 + 997), 333 * c2 - (-c2 + 3) / 3 + 333), 333 * c3 - (-c3 + 3) / 3 + 334); c6 += 1) for (int c7 = max(max(max(max(500 * c5 + 2, c6), 1000 * c0 - c6), 1000 * c3 - 2 * c6 + 2), 500 * c1 + (c6 + 1) / 2); c7 <= min(min(min(min(500 * c5 + 501, 2 * c6 + 1), 1000 * c0 - c6 + 999), 1000 * c3 - 2 * c6 + 1001), 500 * c1 + (c6 + 1) / 2 + 499); c7 += 1) s0(c0, c1, c2, c3, c2 / 3, c5, c6, c7); diff --git a/polly/lib/External/isl/test_inputs/codegen/redundant.c b/polly/lib/External/isl/test_inputs/codegen/redundant.c new file mode 100644 index 00000000000..809692ed380 --- /dev/null +++ b/polly/lib/External/isl/test_inputs/codegen/redundant.c @@ -0,0 +1,19 @@ +for (int c0 = 0; c0 <= 2; c0 += 1) + for (int c1 = max(0, b0 - 4 * c0 - 1); c1 <= 1; c1 += 1) { + if (b0 >= 1 && 4 * c0 + c1 >= 1) + for (int c2 = 1; c2 <= 2; c2 += 1) { + if (c2 == 2) { + for (int c3 = 1; c3 <= 14; c3 += 1) + write(c0, c1, 8 * b0 - 3, c3); + } else if (c1 == 1) { + for (int c3 = 1; c3 <= 14; c3 += 1) + write(c0, 1, 8 * b0 - 4, c3); + } else + for (int c3 = 1; c3 <= 14; c3 += 1) + write(c0, 0, 8 * b0 - 4, c3); + } + for (int c2 = max(max(3, -8 * b0 + 6), 8 * c0 - 12); c2 <= min(min(7, -8 * b0 + 17), 8 * c0 + 6); c2 += 1) + if (4 * c0 + c1 >= 2 * floord(2 * c1 + c2 - 5, 4) + 1 && 2 * ((2 * c1 + c2 - 1) / 4) + 7 >= 4 * c0 + c1 && 2 * c1 + c2 >= 4 * ((2 * c1 + c2 - 1) / 4) + 2 && ((-2 * c1 - c2 + 8) % 4) + 2 * c2 <= 14) + for (int c3 = 1; c3 <= 14; c3 += 1) + write(c0, c1, 8 * b0 + c2 - 5, c3); + } diff --git a/polly/lib/External/isl/test_inputs/codegen/redundant.st b/polly/lib/External/isl/test_inputs/codegen/redundant.st new file mode 100644 index 00000000000..e766f740c9f --- /dev/null +++ b/polly/lib/External/isl/test_inputs/codegen/redundant.st @@ -0,0 +1,6 @@ +# Check that b1 >= 1 is not dropped by mistake in 4 * c0 + c1 >= 1 part +domain: "[b0] -> { write[i0, o1, o2, o3] : ((exists (e0 = floor((4 + o2)/8), e1 = floor((5 + o2)/8), e2 = floor((4 + o2)/262144), e3, e4: o1 <= 1 and o1 >= 0 and o2 <= 12 and o2 >= 1 and o3 <= 14 and o3 >= 1 and 8e0 <= 4 + o2 and 8e1 <= 5 + o2 and 262144e2 <= 4 - 8b0 + o2 and 262144e2 >= -262139 + o2 and 262144e2 <= 4 + o2 and 262144e2 >= -3 - 8b0 + o2 and 4e4 <= 1 - 8i0 + 2o1 - o2 + 8e0 and 4e4 <= 4 - 8i0 + 2o1 + o2 - 8e0 and 4e4 >= 2o1 + o2 - 8e1 - 8e3 and 4e4 >= -3 + 2o1 + o2 - 8e0 - 8e3 and 4e4 >= -6 + 2o1 - o2 + 8e0 - 8e3 and 2e4 >= -9 + o1 and 2e4 <= -1 + o1 and 4e4 <= -6 + 2o1 - o2 + 8e1 - 8e3 and 4e4 >= -3 - 8i0 + 2o1 + o2 - 8e0 and 4e4 >= -6 - 8i0 + 2o1 - o2 + 8e0)) or (exists (e0 = floor((4 + o2)/8), e1 = floor((5 + o2)/8), e2 = floor((4 + o2)/262144), e3, e4: o1 <= 1 and o1 >= 0 and o2 <= 12 and o2 >= 1 and o3 <= 14 and o3 >= 1 and 8e0 <= 4 + o2 and 8e1 >= -2 + o2 and 262144e2 <= 4 - 8b0 + o2 and 262144e2 >= -262139 + o2 and 262144e2 <= 4 + o2 and 262144e2 >= -3 - 8b0 + o2 and 4e4 <= 1 - 8i0 + 2o1 - o2 + 8e0 and 4e4 <= 4 - 8i0 + 2o1 + o2 - 8e0 and 4e4 >= -3 + 2o1 + o2 - 8e0 - 8e3 and 4e4 >= -6 + 2o1 - o2 + 8e0 - 8e3 and 2e4 >= -9 + o1 and 2e4 <= -1 + o1 and 4e4 <= 1 + 2o1 - o2 + 8e0 - 8e3 and 4e4 <= 4 + 2o1 + o2 - 8e0 - 8e3 and 4e4 <= -1 + 2o1 + o2 - 8e1 - 8e3 and 4e4 >= -3 - 8i0 + 2o1 + o2 - 8e0 and 4e4 >= -6 - 8i0 + 2o1 - o2 + 8e0)) or (exists (e0 = floor((2 + o2)/8), e1 = floor((4 + o2)/8), e2 = floor((4 + o2)/262144), e3, e4: o1 <= 1 and o1 >= 0 and o2 <= 13 and o2 >= 3 and o3 <= 14 and o3 >= 1 and 8e0 >= -5 + o2 and 8e1 <= 4 + o2 and 262144e2 <= 4 - 8b0 + o2 and 262144e2 >= -262139 + o2 and 262144e2 <= 4 + o2 and 262144e2 >= -3 - 8b0 + o2 and 4e4 <= 1 - 8i0 + 2o1 - o2 + 8e1 and 4e4 <= 4 - 8i0 + 2o1 + o2 - 8e1 and 4e4 >= -3 + 2o1 + o2 - 8e1 - 8e3 and 4e4 >= -6 + 2o1 - o2 + 8e1 - 8e3 and 2e4 >= -9 + o1 and 2e4 <= -1 + o1 and 4e4 <= 1 + 2o1 - o2 + 8e1 - 8e3 and 4e4 <= -4 + 2o1 + o2 - 8e0 - 8e3 and 4e4 <= 4 + 2o1 + o2 - 8e1 - 8e3 and 4e4 >= -3 - 8i0 + 2o1 + o2 - 8e1 and 4e4 >= -6 - 8i0 + 2o1 - o2 + 8e1))) and b0 >= 0 and i0 <= 2 and i0 >= 0 and b0 <= 2 }" +child: + context: "[b0] -> { [] : b0 <= 2 and b0 >= 0 }" + child: + schedule: "[b0] -> [{ write[i0, o1, o2, o3] -> [i0] }, { write[i0, i1, i2, i3] -> [(i1)] }, { write[i0, i1, i2, i3] -> [(5 - 8b0 + i2)] }, { write[i0,i1, i2, i3] -> [(i3)] }]" |
