diff options
21 files changed, 352 insertions, 391 deletions
diff --git a/polly/lib/External/isl/GIT_HEAD_ID b/polly/lib/External/isl/GIT_HEAD_ID index 2e979ca877e..c99fa174f3a 100644 --- a/polly/lib/External/isl/GIT_HEAD_ID +++ b/polly/lib/External/isl/GIT_HEAD_ID @@ -1 +1 @@ -isl-0.15-61-gcea776f +isl-0.15-86-g595055e diff --git a/polly/lib/External/isl/Makefile.am b/polly/lib/External/isl/Makefile.am index fa9827186a7..a7b0b6cb6a1 100644 --- a/polly/lib/External/isl/Makefile.am +++ b/polly/lib/External/isl/Makefile.am @@ -325,6 +325,8 @@ EXTRA_DIST = \ isl_pw_templ.c \ isl_union_macro.h \ isl_union_templ.c \ + isl_union_single.c \ + isl_union_multi.c \ isl_union_eval.c \ isl_union_neg.c \ isl.py \ diff --git a/polly/lib/External/isl/Makefile.in b/polly/lib/External/isl/Makefile.in index acd3f02821b..9e98d2a7adb 100644 --- a/polly/lib/External/isl/Makefile.in +++ b/polly/lib/External/isl/Makefile.in @@ -1067,6 +1067,8 @@ EXTRA_DIST = \ isl_pw_templ.c \ isl_union_macro.h \ isl_union_templ.c \ + isl_union_single.c \ + isl_union_multi.c \ isl_union_eval.c \ isl_union_neg.c \ isl.py \ diff --git a/polly/lib/External/isl/doc/manual.pdf b/polly/lib/External/isl/doc/manual.pdf Binary files differindex ca4b6183858..18400653e1a 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 9eb4559cac5..db98c60184e 100644 --- a/polly/lib/External/isl/doc/user.pod +++ b/polly/lib/External/isl/doc/user.pod @@ -212,9 +212,6 @@ a regular basic set, rather than a rational basic set. =over -=item * Objects of type C<isl_union_pw_multi_aff> can no longer contain -two or more C<isl_pw_multi_aff> objects with the same domain space. - =item * The function C<isl_union_pw_multi_aff_add> now consistently computes the sum on the shared definition domain. The function C<isl_union_pw_multi_aff_union_add> has been added @@ -3128,6 +3125,14 @@ is that of the shared parameter space. The union expression types defined by C<isl> are C<isl_union_pw_aff>, C<isl_union_pw_multi_aff>, C<isl_union_pw_qpolynomial> and C<isl_union_pw_qpolynomial_fold>. +In case of +C<isl_union_pw_aff>, +C<isl_union_pw_qpolynomial> and C<isl_union_pw_qpolynomial_fold>, +there can be at most one base expression for a given domain space. +In case of +C<isl_union_pw_multi_aff>, +there can be multiple such expressions for a given domain space, +but the domains of these expressions need to be disjoint. An empty union expression can be created using the following functions. diff --git a/polly/lib/External/isl/isl_aff.c b/polly/lib/External/isl/isl_aff.c index 29bbe5b7f67..fbbfde6cc6b 100644 --- a/polly/lib/External/isl/isl_aff.c +++ b/polly/lib/External/isl/isl_aff.c @@ -2578,7 +2578,7 @@ __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff) #undef PARTS #define PARTS pw_aff -#include <isl_union_templ.c> +#include <isl_union_single.c> #include <isl_union_neg.c> static __isl_give isl_set *align_params_pw_pw_set_and( @@ -4073,7 +4073,7 @@ __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1, #undef PARTS #define PARTS pw_multi_aff -#include <isl_union_templ.c> +#include <isl_union_multi.c> #include <isl_union_neg.c> /* Given a function "cmp" that returns the set of elements where @@ -5722,23 +5722,23 @@ struct isl_union_pw_multi_aff_bin_data { isl_union_pw_multi_aff *upma2; isl_union_pw_multi_aff *res; isl_pw_multi_aff *pma; - isl_stat (*fn)(void **entry, void *user); + isl_stat (*fn)(__isl_take isl_pw_multi_aff *pma, void *user); }; /* Given an isl_pw_multi_aff from upma1, store it in data->pma * and call data->fn for each isl_pw_multi_aff in data->upma2. */ -static isl_stat bin_entry(void **entry, void *user) +static isl_stat bin_entry(__isl_take isl_pw_multi_aff *pma, void *user) { struct isl_union_pw_multi_aff_bin_data *data = user; - isl_pw_multi_aff *pma = *entry; + isl_stat r; data->pma = pma; - if (isl_hash_table_foreach(data->upma2->space->ctx, &data->upma2->table, - data->fn, data) < 0) - return isl_stat_error; + r = isl_union_pw_multi_aff_foreach_pw_multi_aff(data->upma2, + data->fn, data); + isl_pw_multi_aff_free(pma); - return isl_stat_ok; + return r; } /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2". @@ -5749,7 +5749,7 @@ static isl_stat bin_entry(void **entry, void *user) static __isl_give isl_union_pw_multi_aff *bin_op( __isl_take isl_union_pw_multi_aff *upma1, __isl_take isl_union_pw_multi_aff *upma2, - isl_stat (*fn)(void **entry, void *user)) + isl_stat (*fn)(__isl_take isl_pw_multi_aff *pma, void *user)) { isl_space *space; struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn }; @@ -5764,7 +5764,7 @@ static __isl_give isl_union_pw_multi_aff *bin_op( data.upma2 = upma2; data.res = isl_union_pw_multi_aff_alloc_same_size(upma1); - if (isl_hash_table_foreach(upma1->space->ctx, &upma1->table, + if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma1, &bin_entry, &data) < 0) goto error; @@ -5827,21 +5827,22 @@ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product( &pw_multi_aff_flat_range_product); } -/* If data->pma and *entry have the same domain space, then compute +/* If data->pma and "pma2" have the same domain space, then compute * their flat range product and the result to data->res. */ -static isl_stat flat_range_product_entry(void **entry, void *user) +static isl_stat flat_range_product_entry(__isl_take isl_pw_multi_aff *pma2, + void *user) { struct isl_union_pw_multi_aff_bin_data *data = user; - isl_pw_multi_aff *pma2 = *entry; if (!isl_space_tuple_is_equal(data->pma->dim, isl_dim_in, - pma2->dim, isl_dim_in)) + pma2->dim, isl_dim_in)) { + isl_pw_multi_aff_free(pma2); return isl_stat_ok; + } pma2 = isl_pw_multi_aff_flat_range_product( - isl_pw_multi_aff_copy(data->pma), - isl_pw_multi_aff_copy(pma2)); + isl_pw_multi_aff_copy(data->pma), pma2); data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2); @@ -7118,18 +7119,18 @@ __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_multi_val_on_domain( /* Compute the pullback of data->pma by the function represented by "pma2", * provided the spaces match, and add the results to data->res. */ -static isl_stat pullback_entry(void **entry, void *user) +static isl_stat pullback_entry(__isl_take isl_pw_multi_aff *pma2, void *user) { struct isl_union_pw_multi_aff_bin_data *data = user; - isl_pw_multi_aff *pma2 = *entry; if (!isl_space_tuple_is_equal(data->pma->dim, isl_dim_in, - pma2->dim, isl_dim_out)) + pma2->dim, isl_dim_out)) { + isl_pw_multi_aff_free(pma2); return isl_stat_ok; + } pma2 = isl_pw_multi_aff_pullback_pw_multi_aff( - isl_pw_multi_aff_copy(data->pma), - isl_pw_multi_aff_copy(pma2)); + isl_pw_multi_aff_copy(data->pma), pma2); data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2); if (!data->res) @@ -7265,18 +7266,11 @@ static __isl_give isl_union_pw_aff *isl_union_pw_aff_reset_domain_space( return data.res; } -/* Replace the entry of isl_union_pw_aff to which "entry" points - * by its floor. +/* Return the floor of "pa". */ -static isl_stat floor_entry(void **entry, void *user) +static __isl_give isl_pw_aff *floor_entry(__isl_take isl_pw_aff *pa, void *user) { - isl_pw_aff **pa = (isl_pw_aff **) entry; - - *pa = isl_pw_aff_floor(*pa); - if (!*pa) - return isl_stat_error; - - return isl_stat_ok; + return isl_pw_aff_floor(pa); } /* Given f, return floor(f). @@ -7284,17 +7278,7 @@ static isl_stat floor_entry(void **entry, void *user) __isl_give isl_union_pw_aff *isl_union_pw_aff_floor( __isl_take isl_union_pw_aff *upa) { - isl_ctx *ctx; - - upa = isl_union_pw_aff_cow(upa); - if (!upa) - return NULL; - - ctx = isl_union_pw_aff_get_ctx(upa); - if (isl_hash_table_foreach(ctx, &upa->table, &floor_entry, NULL) < 0) - upa = isl_union_pw_aff_free(upa); - - return upa; + return isl_union_pw_aff_transform_inplace(upa, &floor_entry, NULL); } /* Compute @@ -7618,17 +7602,17 @@ struct isl_union_pw_aff_pullback_upma_data { /* Check if "pma" can be plugged into data->pa. * If so, perform the pullback and add the result to data->res. */ -static isl_stat pa_pb_pma(void **entry, void *user) +static isl_stat pa_pb_pma(__isl_take isl_pw_multi_aff *pma, void *user) { struct isl_union_pw_aff_pullback_upma_data *data = user; - isl_pw_multi_aff *pma = *entry; isl_pw_aff *pa; if (!isl_space_tuple_is_equal(data->pa->dim, isl_dim_in, - pma->dim, isl_dim_out)) + pma->dim, isl_dim_out)) { + isl_pw_multi_aff_free(pma); return isl_stat_ok; + } - pma = isl_pw_multi_aff_copy(pma); pa = isl_pw_aff_copy(data->pa); pa = isl_pw_aff_pullback_pw_multi_aff(pa, pma); @@ -7640,19 +7624,17 @@ static isl_stat pa_pb_pma(void **entry, void *user) /* Check if any of the elements of data->upma can be plugged into pa, * add if so add the result to data->res. */ -static isl_stat upa_pb_upma(void **entry, void *user) +static isl_stat upa_pb_upma(__isl_take isl_pw_aff *pa, void *user) { struct isl_union_pw_aff_pullback_upma_data *data = user; - isl_ctx *ctx; - isl_pw_aff *pa = *entry; + isl_stat r; data->pa = pa; - ctx = isl_union_pw_multi_aff_get_ctx(data->upma); - if (isl_hash_table_foreach(ctx, &data->upma->table, - &pa_pb_pma, data) < 0) - return isl_stat_error; + r = isl_union_pw_multi_aff_foreach_pw_multi_aff(data->upma, + &pa_pb_pma, data); + isl_pw_aff_free(pa); - return isl_stat_ok; + return r; } /* Compute the pullback of "upa" by the function represented by "upma". @@ -7670,7 +7652,6 @@ __isl_give isl_union_pw_aff *isl_union_pw_aff_pullback_union_pw_multi_aff( __isl_take isl_union_pw_multi_aff *upma) { struct isl_union_pw_aff_pullback_upma_data data = { NULL, NULL }; - isl_ctx *ctx; isl_space *space; space = isl_union_pw_multi_aff_get_space(upma); @@ -7681,10 +7662,9 @@ __isl_give isl_union_pw_aff *isl_union_pw_aff_pullback_union_pw_multi_aff( if (!upa || !upma) goto error; - ctx = isl_union_pw_aff_get_ctx(upa); data.upma = upma; data.res = isl_union_pw_aff_alloc_same_size(upa); - if (isl_hash_table_foreach(ctx, &upa->table, &upa_pb_upma, &data) < 0) + if (isl_union_pw_aff_foreach_pw_aff(upa, &upa_pb_upma, &data) < 0) data.res = isl_union_pw_aff_free(data.res); isl_union_pw_aff_free(upa); diff --git a/polly/lib/External/isl/isl_ast_build.c b/polly/lib/External/isl/isl_ast_build.c index febc7d4a93e..381d8f65475 100644 --- a/polly/lib/External/isl/isl_ast_build.c +++ b/polly/lib/External/isl/isl_ast_build.c @@ -825,6 +825,10 @@ static __isl_give isl_ast_build *update_values( * Otherwise, we would indirectly intersect the build domain with itself, * which can lead to inefficiencies, in particular if the build domain * contains any unknown divs. + * + * The pending and generated sets are not updated by this function to + * match the updated domain. + * The caller still needs to call isl_ast_build_set_pending_generated. */ __isl_give isl_ast_build *isl_ast_build_set_loop_bounds( __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds) @@ -835,12 +839,10 @@ __isl_give isl_ast_build *isl_ast_build_set_loop_bounds( if (!build) goto error; - bounds = isl_basic_set_preimage_multi_aff(bounds, - isl_multi_aff_copy(build->values)); build = update_values(build, isl_basic_set_copy(bounds)); if (!build) goto error; - set = isl_set_from_basic_set(isl_basic_set_copy(bounds)); + set = isl_set_from_basic_set(bounds); if (isl_ast_build_has_affine_value(build, build->depth)) { set = isl_set_eliminate(set, isl_dim_set, build->depth, 1); set = isl_set_compute_divs(set); @@ -848,24 +850,11 @@ __isl_give isl_ast_build *isl_ast_build_set_loop_bounds( isl_set_copy(set)); build->domain = isl_set_intersect(build->domain, set); } else { - isl_basic_set *generated, *pending; - - pending = isl_basic_set_copy(bounds); - pending = isl_basic_set_drop_constraints_involving_dims(pending, - isl_dim_set, build->depth, 1); - build->pending = isl_set_intersect(build->pending, - isl_set_from_basic_set(pending)); - generated = isl_basic_set_copy(bounds); - generated = isl_basic_set_drop_constraints_not_involving_dims( - generated, isl_dim_set, build->depth, 1); - build->generated = isl_set_intersect(build->generated, - isl_set_from_basic_set(generated)); build->domain = isl_set_intersect(build->domain, set); build = isl_ast_build_include_stride(build); if (!build) goto error; } - isl_basic_set_free(bounds); if (!build->domain || !build->pending || !build->generated) return isl_ast_build_free(build); @@ -877,6 +866,49 @@ error: return NULL; } +/* Update the pending and generated sets of "build" according to "bounds". + * If the build has an affine value at the current depth, + * then isl_ast_build_set_loop_bounds has already set the pending set. + * Otherwise, do it here. + */ +__isl_give isl_ast_build *isl_ast_build_set_pending_generated( + __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds) +{ + isl_basic_set *generated, *pending; + + if (!build) + goto error; + + if (isl_ast_build_has_affine_value(build, build->depth)) { + isl_basic_set_free(bounds); + return build; + } + + build = isl_ast_build_cow(build); + if (!build) + goto error; + + pending = isl_basic_set_copy(bounds); + pending = isl_basic_set_drop_constraints_involving_dims(pending, + isl_dim_set, build->depth, 1); + build->pending = isl_set_intersect(build->pending, + isl_set_from_basic_set(pending)); + generated = bounds; + generated = isl_basic_set_drop_constraints_not_involving_dims( + generated, isl_dim_set, build->depth, 1); + build->generated = isl_set_intersect(build->generated, + isl_set_from_basic_set(generated)); + + if (!build->pending || !build->generated) + return isl_ast_build_free(build); + + return build; +error: + isl_ast_build_free(build); + isl_basic_set_free(bounds); + return NULL; +} + /* Intersect build->domain with "set", where "set" is specified * in terms of the internal schedule domain. */ @@ -2193,6 +2225,18 @@ __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build, isl_multi_aff_copy(build->values)); } +/* Plug in the known affine values of outer loop iterators in "bset". + */ +__isl_give isl_basic_set *isl_ast_build_specialize_basic_set( + __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset) +{ + if (!build) + return isl_basic_set_free(bset); + + return isl_basic_set_preimage_multi_aff(bset, + isl_multi_aff_copy(build->values)); +} + /* Simplify the map "map" based on what we know about * the iterators of already generated loops. * diff --git a/polly/lib/External/isl/isl_ast_build_expr.c b/polly/lib/External/isl/isl_ast_build_expr.c index 29eb53fd5ee..59fe841ce94 100644 --- a/polly/lib/External/isl/isl_ast_build_expr.c +++ b/polly/lib/External/isl/isl_ast_build_expr.c @@ -1453,7 +1453,7 @@ __isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set( return NULL; n = isl_constraint_list_n_constraint(list); if (n == 0) { - isl_ctx *ctx = isl_basic_set_get_ctx(bset); + isl_ctx *ctx = isl_constraint_list_get_ctx(list); isl_constraint_list_free(list); return isl_ast_expr_alloc_int_si(ctx, 1); } diff --git a/polly/lib/External/isl/isl_ast_build_private.h b/polly/lib/External/isl/isl_ast_build_private.h index 59eec25fd6b..25b56874546 100644 --- a/polly/lib/External/isl/isl_ast_build_private.h +++ b/polly/lib/External/isl/isl_ast_build_private.h @@ -221,6 +221,8 @@ __isl_give isl_ast_build *isl_ast_build_product( __isl_take isl_ast_build *build, __isl_take isl_space *embedding); __isl_give isl_ast_build *isl_ast_build_set_loop_bounds( __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds); +__isl_give isl_ast_build *isl_ast_build_set_pending_generated( + __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds); __isl_give isl_ast_build *isl_ast_build_detect_strides( __isl_take isl_ast_build *build, __isl_take isl_set *set); __isl_give isl_ast_build *isl_ast_build_include_stride( @@ -270,6 +272,8 @@ int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build); __isl_give isl_set *isl_ast_build_get_isolated( __isl_keep isl_ast_build *build); +__isl_give isl_basic_set *isl_ast_build_specialize_basic_set( + __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset); __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set( __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset); __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build, diff --git a/polly/lib/External/isl/isl_ast_codegen.c b/polly/lib/External/isl/isl_ast_codegen.c index 2b791a5935b..2cb6401c6e4 100644 --- a/polly/lib/External/isl/isl_ast_codegen.c +++ b/polly/lib/External/isl/isl_ast_codegen.c @@ -1450,12 +1450,17 @@ 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); + bounds = isl_ast_build_specialize_basic_set(sub_build, bounds); sub_build = isl_ast_build_set_loop_bounds(sub_build, isl_basic_set_copy(bounds)); degenerate = isl_ast_build_has_value(sub_build); eliminated = isl_ast_build_has_affine_value(sub_build, depth); if (degenerate < 0 || eliminated < 0) executed = isl_union_map_free(executed); + if (!degenerate) + bounds = isl_ast_build_compute_gist_basic_set(build, bounds); + sub_build = isl_ast_build_set_pending_generated(sub_build, + isl_basic_set_copy(bounds)); if (eliminated) executed = plug_in_values(executed, sub_build); else @@ -1481,8 +1486,6 @@ static __isl_give isl_ast_graft *create_node_scaled( graft = isl_ast_graft_alloc_from_children(children, isl_set_copy(guard), enforced, build, sub_build); - if (!degenerate) - bounds = isl_ast_build_compute_gist_basic_set(build, bounds); if (!eliminated) { isl_ast_build *for_build; diff --git a/polly/lib/External/isl/isl_coalesce.c b/polly/lib/External/isl/isl_coalesce.c index 9b0e47f777a..a1993d69348 100644 --- a/polly/lib/External/isl/isl_coalesce.c +++ b/polly/lib/External/isl/isl_coalesce.c @@ -2142,18 +2142,26 @@ error: return NULL; } -/* Add variables to "tab" corresponding to the elements in "list" - * that are not set to NaN. +/* Add variables to info->bmap and info->tab corresponding to the elements + * in "list" that are not set to NaN. + * "extra_var" is the number of these elements. * "dim" is the offset in the variables of "tab" where we should * start considering the elements in "list". * When this function returns, the total number of variables in "tab" * is equal to "dim" plus the number of elements in "list". */ -static int add_sub_vars(struct isl_tab *tab, __isl_keep isl_aff_list *list, - int dim) +static int add_sub_vars(struct isl_coalesce_info *info, + __isl_keep isl_aff_list *list, int dim, int extra_var) { int i, n; + isl_space *space; + space = isl_basic_map_get_space(info->bmap); + info->bmap = isl_basic_map_cow(info->bmap); + info->bmap = isl_basic_map_extend_space(info->bmap, space, + extra_var, 0, 0); + if (!info->bmap) + return -1; n = isl_aff_list_n_aff(list); for (i = 0; i < n; ++i) { int is_nan; @@ -2164,9 +2172,15 @@ static int add_sub_vars(struct isl_tab *tab, __isl_keep isl_aff_list *list, isl_aff_free(aff); if (is_nan < 0) return -1; + if (is_nan) + continue; - if (!is_nan && isl_tab_insert_var(tab, dim + i) < 0) + if (isl_tab_insert_var(info->tab, dim + i) < 0) return -1; + if (isl_basic_map_alloc_div(info->bmap) < 0) + return -1; + if (i != n - 1) + isl_basic_map_swap_div(info->bmap, i, n - 1); } return 0; @@ -2217,53 +2231,33 @@ error: return -1; } -/* Add variables to info->tab corresponding to the elements in "list" - * that are not set to NaN. The value of the added variable - * is fixed to the purely affine expression defined by the element. +/* Add variables to info->tab and info->bmap corresponding to the elements + * in "list" that are not set to NaN. The value of the added variable + * in info->tab is fixed to the purely affine expression defined by the element. * "dim" is the offset in the variables of info->tab where we should * start considering the elements in "list". * When this function returns, the total number of variables in info->tab * is equal to "dim" plus the number of elements in "list". - * Additionally, add the div constraints that have been added info->bmap - * after the tableau was constructed to info->tab. These constraints - * start at position "n_ineq" in info->bmap. - * The constraints need to be added to the tableau before - * the equalities assigning the purely affine expression - * because the position needs to match that in info->bmap. - * They are frozen because the corresponding added equality is a consequence - * of the two div constraints and the other equalities, meaning that - * the div constraints would otherwise get marked as redundant, - * while they are only redundant with respect to the extra equalities - * added to the tableau, which do not appear explicitly in the basic map. */ static int add_subs(struct isl_coalesce_info *info, - __isl_keep isl_aff_list *list, int dim, int n_ineq) + __isl_keep isl_aff_list *list, int dim) { - int i, extra_var, extra_con; + int extra_var; int n; - unsigned n_eq = info->bmap->n_eq; if (!list) return -1; n = isl_aff_list_n_aff(list); extra_var = n - (info->tab->n_var - dim); - extra_con = info->bmap->n_ineq - n_ineq; if (isl_tab_extend_vars(info->tab, extra_var) < 0) return -1; - if (isl_tab_extend_cons(info->tab, extra_con + 2 * extra_var) < 0) + if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0) return -1; - if (add_sub_vars(info->tab, list, dim) < 0) + if (add_sub_vars(info, list, dim, extra_var) < 0) return -1; - for (i = n_ineq; i < info->bmap->n_ineq; ++i) { - if (isl_tab_add_ineq(info->tab, info->bmap->ineq[i]) < 0) - return -1; - if (isl_tab_freeze_constraint(info->tab, n_eq + i) < 0) - return -1; - } - return add_sub_equalities(info->tab, list, dim); } @@ -2273,9 +2267,6 @@ static int add_subs(struct isl_coalesce_info *info, * is equal to the number of integer divisions in "i", while the number * of NaN elements in the list is equal to the number of integer divisions * in "j". - * Adding extra integer divisions to "j" through isl_basic_map_align_divs - * also adds the corresponding div constraints. These need to be added - * to the corresponding tableau as well in add_subs to maintain consistency. * * If no coalescing can be performed, then we need to revert basic map "j" * to its original state. We do the same if basic map "i" gets dropped @@ -2290,19 +2281,13 @@ static enum isl_change coalesce_with_subs(int i, int j, struct isl_tab_undo *snap; unsigned dim; enum isl_change change; - int n_ineq; bmap_j = isl_basic_map_copy(info[j].bmap); - n_ineq = info[j].bmap->n_ineq; - info[j].bmap = isl_basic_map_align_divs(info[j].bmap, info[i].bmap); - if (!info[j].bmap) - goto error; - snap = isl_tab_snap(info[j].tab); dim = isl_basic_map_dim(bmap_j, isl_dim_all); dim -= isl_basic_map_dim(bmap_j, isl_dim_div); - if (add_subs(&info[j], list, dim, n_ineq) < 0) + if (add_subs(&info[j], list, dim) < 0) goto error; change = coalesce_local_pair(i, j, info); diff --git a/polly/lib/External/isl/isl_convex_hull.c b/polly/lib/External/isl/isl_convex_hull.c index b5ca0d9d53e..a61462e62e0 100644 --- a/polly/lib/External/isl/isl_convex_hull.c +++ b/polly/lib/External/isl/isl_convex_hull.c @@ -2326,6 +2326,25 @@ error: /* Compute a superset of the convex hull of map that is described * by only (translates of) the constraints in the constituents of map. + * Handle trivial cases where map is NULL or contains at most one disjunct. + */ +static __isl_give isl_basic_map *map_simple_hull_trivial( + __isl_take isl_map *map) +{ + isl_basic_map *hull; + + if (!map) + return NULL; + if (map->n == 0) + return replace_map_by_empty_basic_map(map); + + hull = isl_basic_map_copy(map->p[0]); + isl_map_free(map); + return hull; +} + +/* Compute a superset of the convex hull of map that is described + * by only (translates of) the constraints in the constituents of map. * Translation is only allowed if "shift" is set. */ static __isl_give isl_basic_map *map_simple_hull(__isl_take isl_map *map, @@ -2337,17 +2356,12 @@ static __isl_give isl_basic_map *map_simple_hull(__isl_take isl_map *map, struct isl_basic_map *affine_hull; struct isl_basic_set *bset = NULL; - if (!map) - return NULL; - if (map->n == 0) - return replace_map_by_empty_basic_map(map); - if (map->n == 1) { - hull = isl_basic_map_copy(map->p[0]); - isl_map_free(map); - return hull; - } + if (!map || map->n <= 1) + return map_simple_hull_trivial(map); map = isl_map_detect_equalities(map); + if (!map || map->n <= 1) + return map_simple_hull_trivial(map); affine_hull = isl_map_affine_hull(isl_map_copy(map)); map = isl_map_align_divs(map); model = map ? isl_basic_map_copy(map->p[0]) : NULL; diff --git a/polly/lib/External/isl/isl_equalities.c b/polly/lib/External/isl/isl_equalities.c index 44cf8f06e45..dbba7fa8cfa 100644 --- a/polly/lib/External/isl/isl_equalities.c +++ b/polly/lib/External/isl/isl_equalities.c @@ -514,7 +514,7 @@ __isl_give isl_mat *isl_mat_variable_compression(__isl_take isl_mat *B, isl_mat_free(U); if (T2) { isl_mat_free(*T2); - *T2 = NULL; + *T2 = isl_mat_alloc(ctx, 0, 1 + dim); } return isl_mat_alloc(ctx, 1 + dim, 0); } diff --git a/polly/lib/External/isl/isl_fold.c b/polly/lib/External/isl/isl_fold.c index d61d41fd2b1..c2162cfbf50 100644 --- a/polly/lib/External/isl/isl_fold.c +++ b/polly/lib/External/isl/isl_fold.c @@ -684,7 +684,7 @@ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params( #define NO_SUB -#include <isl_union_templ.c> +#include <isl_union_single.c> #include <isl_union_eval.c> __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type, diff --git a/polly/lib/External/isl/isl_polynomial.c b/polly/lib/External/isl/isl_polynomial.c index 8c9522ba7c5..277912ad8db 100644 --- a/polly/lib/External/isl/isl_polynomial.c +++ b/polly/lib/External/isl/isl_polynomial.c @@ -2817,7 +2817,7 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial( #undef PARTS #define PARTS pw_qpolynomial -#include <isl_union_templ.c> +#include <isl_union_single.c> #include <isl_union_eval.c> #include <isl_union_neg.c> @@ -4772,31 +4772,19 @@ error: return NULL; } -static isl_stat poly_entry(void **entry, void *user) +static __isl_give isl_pw_qpolynomial *poly_entry( + __isl_take isl_pw_qpolynomial *pwqp, void *user) { int *sign = user; - isl_pw_qpolynomial **pwqp = (isl_pw_qpolynomial **)entry; - *pwqp = isl_pw_qpolynomial_to_polynomial(*pwqp, *sign); - - return *pwqp ? isl_stat_ok : isl_stat_error; + return isl_pw_qpolynomial_to_polynomial(pwqp, *sign); } __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_to_polynomial( __isl_take isl_union_pw_qpolynomial *upwqp, int sign) { - upwqp = isl_union_pw_qpolynomial_cow(upwqp); - if (!upwqp) - return NULL; - - if (isl_hash_table_foreach(upwqp->space->ctx, &upwqp->table, - &poly_entry, &sign) < 0) - goto error; - - return upwqp; -error: - isl_union_pw_qpolynomial_free(upwqp); - return NULL; + return isl_union_pw_qpolynomial_transform_inplace(upwqp, + &poly_entry, &sign); } __isl_give isl_basic_map *isl_basic_map_from_qpolynomial( diff --git a/polly/lib/External/isl/isl_test.c b/polly/lib/External/isl/isl_test.c index 250128f0ce4..a618e9da09a 100644 --- a/polly/lib/External/isl/isl_test.c +++ b/polly/lib/External/isl/isl_test.c @@ -1105,6 +1105,30 @@ int test_affine_hull(struct isl_ctx *ctx) return 0; } +static int test_simple_hull(struct isl_ctx *ctx) +{ + const char *str; + isl_set *set; + isl_basic_set *bset; + isl_bool is_empty; + + str = "{ [x, y] : 3y <= 2x and y >= -2 + 2x and 2y >= 2 - x;" + "[y, x] : 3y <= 2x and y >= -2 + 2x and 2y >= 2 - x }"; + set = isl_set_read_from_str(ctx, str); + bset = isl_set_simple_hull(set); + is_empty = isl_basic_set_is_empty(bset); + isl_basic_set_free(bset); + + if (is_empty == isl_bool_error) + return -1; + + if (is_empty == isl_bool_false) + isl_die(ctx, isl_error_unknown, "Empty set should be detected", + return -1); + + return 0; +} + void test_convex_hull_case(struct isl_ctx *ctx, const char *name) { char *filename; @@ -1598,6 +1622,7 @@ struct { "32e0 >= -31 + i2 and 32e0 <= 30 + i2 and 32e0 <= 31 + i1 and " "32e0 <= 31 + i0)) or " "i0 >= 0 }" }, + { 1, "{ [a, b, c] : 2b = 1 + a and 2c = 2 + a; [0, 0, 0] }" }, }; /* A specialized coalescing test case that would result @@ -3896,6 +3921,17 @@ struct { { &isl_union_pw_multi_aff_union_add, "{ A[] -> [0]; B[0] -> [1] }", "{ B[x] -> [2] : x >= 0 }", "{ A[] -> [0]; B[0] -> [3]; B[x] -> [2] : x >= 1 }" }, + { &isl_union_pw_multi_aff_pullback_union_pw_multi_aff, + "{ A[] -> B[0]; C[x] -> B[1] : x < 10; C[y] -> B[2] : y >= 10 }", + "{ D[i] -> A[] : i < 0; D[i] -> C[i + 5] : i >= 0 }", + "{ D[i] -> B[0] : i < 0; D[i] -> B[1] : 0 <= i < 5; " + "D[i] -> B[2] : i >= 5 }" }, + { &isl_union_pw_multi_aff_union_add, "{ B[x] -> A[1] : x <= 0 }", + "{ B[x] -> C[2] : x > 0 }", + "{ B[x] -> A[1] : x <= 0; B[x] -> C[2] : x > 0 }" }, + { &isl_union_pw_multi_aff_union_add, "{ B[x] -> A[1] : x <= 0 }", + "{ B[x] -> A[2] : x >= 0 }", + "{ B[x] -> A[1] : x < 0; B[x] -> A[2] : x > 0; B[0] -> A[3] }" }, }; /* Perform some basic tests of binary operations on @@ -3928,6 +3964,47 @@ static int test_bin_upma(isl_ctx *ctx) return 0; } +struct { + __isl_give isl_union_pw_multi_aff *(*fn)( + __isl_take isl_union_pw_multi_aff *upma1, + __isl_take isl_union_pw_multi_aff *upma2); + const char *arg1; + const char *arg2; +} upma_bin_fail_tests[] = { + { &isl_union_pw_multi_aff_union_add, "{ B[x] -> A[1] : x <= 0 }", + "{ B[x] -> C[2] : x >= 0 }" }, +}; + +/* Perform some basic tests of binary operations on + * isl_union_pw_multi_aff objects that are expected to fail. + */ +static int test_bin_upma_fail(isl_ctx *ctx) +{ + int i, n; + isl_union_pw_multi_aff *upma1, *upma2; + int on_error; + + on_error = isl_options_get_on_error(ctx); + isl_options_set_on_error(ctx, ISL_ON_ERROR_CONTINUE); + n = ARRAY_SIZE(upma_bin_fail_tests); + for (i = 0; i < n; ++i) { + upma1 = isl_union_pw_multi_aff_read_from_str(ctx, + upma_bin_fail_tests[i].arg1); + upma2 = isl_union_pw_multi_aff_read_from_str(ctx, + upma_bin_fail_tests[i].arg2); + upma1 = upma_bin_fail_tests[i].fn(upma1, upma2); + isl_union_pw_multi_aff_free(upma1); + if (upma1) + break; + } + isl_options_set_on_error(ctx, on_error); + if (i < n) + isl_die(ctx, isl_error_unknown, + "operation not expected to succeed", return -1); + + return 0; +} + int test_aff(isl_ctx *ctx) { const char *str; @@ -3941,6 +4018,8 @@ int test_aff(isl_ctx *ctx) return -1; if (test_bin_upma(ctx) < 0) return -1; + if (test_bin_upma_fail(ctx) < 0) + return -1; space = isl_space_set_alloc(ctx, 0, 1); ls = isl_local_space_from_space(space); @@ -5986,6 +6065,7 @@ struct { { "parse", &test_parse }, { "single-valued", &test_sv }, { "affine hull", &test_affine_hull }, + { "simple_hull", &test_simple_hull }, { "coalesce", &test_coalesce }, { "factorize", &test_factorize }, { "subset", &test_subset }, diff --git a/polly/lib/External/isl/isl_union_neg.c b/polly/lib/External/isl/isl_union_neg.c index 4a3e7bb23ff..386b8dcd801 100644 --- a/polly/lib/External/isl/isl_union_neg.c +++ b/polly/lib/External/isl/isl_union_neg.c @@ -10,30 +10,16 @@ #include <isl_union_macro.h> -/* Replace *entry by its opposite. - * - * Return isl_stat_ok on success and isl_stat_error on error. +/* Return the opposite of "part". */ -static isl_stat FN(UNION,neg_entry)(void **entry, void *user) +static __isl_give PART *FN(UNION,neg_entry)(__isl_take PART *part, void *user) { - PW **pw = (PW **) entry; - - *pw = FN(PW,neg)(*pw); - - return *pw ? isl_stat_ok : isl_stat_error; + return FN(PART,neg)(part); } /* 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; + return FN(UNION,transform_inplace)(u, &FN(UNION,neg_entry), NULL); } diff --git a/polly/lib/External/isl/isl_union_templ.c b/polly/lib/External/isl/isl_union_templ.c index d6f1743222b..463b7bddd0f 100644 --- a/polly/lib/External/isl/isl_union_templ.c +++ b/polly/lib/External/isl/isl_union_templ.c @@ -10,23 +10,6 @@ * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ -#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 - enum isl_fold type; -#endif - isl_space *space; - - struct isl_hash_table table; -}; - __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u); isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u) @@ -120,113 +103,6 @@ __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u) return u; } -/* Return the number of base expressions in "u". - */ -int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u) -{ - return u ? u->table.n : 0; -} - -S(UNION,foreach_data) -{ - isl_stat (*fn)(__isl_take PART *part, void *user); - void *user; -}; - -static isl_stat FN(UNION,call_on_copy)(void **entry, void *user) -{ - PART *part = *entry; - S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user; - - return data->fn(FN(PART,copy)(part), data->user); -} - -isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u, - isl_stat (*fn)(__isl_take PART *part, void *user), void *user) -{ - S(UNION,foreach_data) data = { fn, user }; - - if (!u) - return isl_stat_error; - - return isl_hash_table_foreach(u->space->ctx, &u->table, - &FN(UNION,call_on_copy), &data); -} - -/* Is the domain space of "entry" equal to the domain of "space"? - */ -static int FN(UNION,has_same_domain_space)(const void *entry, const void *val) -{ - PART *part = (PART *)entry; - isl_space *space = (isl_space *) val; - - if (isl_space_is_set(space)) - return isl_space_is_set(part->dim); - - return isl_space_tuple_is_equal(part->dim, isl_dim_in, - space, isl_dim_in); -} - -/* 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 struct isl_hash_table_entry *FN(UNION,find_part_entry)( - __isl_keep UNION *u, __isl_keep isl_space *space, int reserve) -{ - isl_ctx *ctx; - uint32_t hash; - struct isl_hash_table_entry *entry; - isl_bool equal; - PART *part; - - if (!u || !space) - return NULL; - - 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); -} - -/* Remove "part_entry" from the hash table of "u". - */ -static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u, - struct isl_hash_table_entry *part_entry) -{ - isl_ctx *ctx; - - if (!u || !part_entry) - return FN(UNION,free)(u); - - 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). * * Return the ZERO element if "u" does not contain any element @@ -266,7 +142,8 @@ error: /* Add "part" to "u". * If "disjoint" is set, then "u" is not allowed to already have - * a part that is defined on the same space as "part". + * a part that is defined over a domain that overlaps with the domain + * of "part". * Otherwise, compute the union sum of "part" and the part in "u" * defined on the same space. */ @@ -295,6 +172,8 @@ static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u, if (!u) goto error; + if (FN(UNION,check_disjoint_domain_other)(u, part) < 0) + goto error; entry = FN(UNION,find_part_entry)(u, part->dim, 1); if (!entry) goto error; @@ -302,10 +181,9 @@ static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u, if (!entry->data) entry->data = part; else { - if (disjoint) - isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, - "additional part should live on separate " - "space", goto error); + if (disjoint && + FN(UNION,check_disjoint_domain)(entry->data, part) < 0) + goto error; entry->data = FN(PART,union_add_)(entry->data, FN(PART,copy)(part)); if (!entry->data) @@ -365,19 +243,6 @@ 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. @@ -430,6 +295,43 @@ static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u, return FN(UNION,transform_space)(u, FN(UNION,get_space)(u), fn, user); } +/* Apply data->fn to *part and store the result back into *part. + */ +static isl_stat FN(UNION,transform_inplace_entry)(void **part, void *user) +{ + S(UNION,transform_data) *data = (S(UNION,transform_data) *) user; + + *part = data->fn(*part, data->user); + if (!*part) + return isl_stat_error; + return isl_stat_ok; +} + +/* Update "u" by applying "fn" to each entry. + * This operation is assumed not to change the number of entries nor + * the spaces of the entries. + * + * If there is only one reference to "u", then change "u" inplace. + * Otherwise, create a new UNION from "u" and discard the original. + */ +static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u, + __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user) +{ + isl_bool single_ref; + + single_ref = FN(UNION,has_single_reference)(u); + if (single_ref < 0) + return FN(UNION,free)(u); + if (single_ref) { + S(UNION,transform_data) data = { fn, user }; + if (FN(UNION,foreach_inplace)(u, + &FN(UNION,transform_inplace_entry), &data) < 0) + return FN(UNION,free)(u); + return u; + } + return FN(UNION,transform)(u, fn, user); +} + /* An isl_union_*_transform callback for use in isl_union_*_dup * that simply returns "part". */ @@ -455,13 +357,6 @@ __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u) return FN(UNION,dup)(u); } -static isl_stat FN(UNION,free_u_entry)(void **entry, void *user) -{ - PART *part = *entry; - FN(PART,free)(part); - return isl_stat_ok; -} - __isl_null UNION *FN(UNION,free)(__isl_take UNION *u) { if (!u) @@ -605,34 +500,34 @@ S(UNION,match_bin_data) { __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *); }; -/* Check if data->u2 has an element living in the same space as *entry. +/* Check if data->u2 has an element living in the same space as "part". * If so, call data->fn on the two elements and add the result to * data->res. */ -static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user) +static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user) { S(UNION,match_bin_data) *data = user; struct isl_hash_table_entry *entry2; isl_space *space; - PART *part = *entry; PART *part2; space = FN(PART,get_space)(part); 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) + goto error; + if (entry2 == isl_hash_table_entry_none) { + FN(PART,free)(part); return isl_stat_ok; + } part2 = entry2->data; if (!isl_space_tuple_is_equal(part->dim, isl_dim_out, part2->dim, isl_dim_out)) isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid, "entries should have the same range space", - return isl_stat_error); + goto error); - part = FN(PART, copy)(part); part = data->fn(part, FN(PART, copy)(entry2->data)); data->res = FN(FN(UNION,add),PARTS)(data->res, part); @@ -640,6 +535,9 @@ static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user) return isl_stat_error; return isl_stat_ok; +error: + FN(PART,free)(part); + return isl_stat_error; } /* This function is currently only used from isl_polynomial.c @@ -666,7 +564,7 @@ static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1, data.u2 = u2; data.res = FN(UNION,alloc_same_size)(u1); - if (isl_hash_table_foreach(u1->space->ctx, &u1->table, + if (FN(FN(UNION,foreach),PARTS)(u1, &FN(UNION,match_bin_entry), &data) < 0) goto error; @@ -773,29 +671,29 @@ static int FN(UNION,set_has_dim)(const void *entry, const void *val) } /* Find the set in data->uset that lives in the same space as the domain - * of *entry, apply data->fn to *entry and this set (if any), and add + * of "part", apply data->fn to *entry and this set (if any), and add * the result to data->res. */ -static isl_stat FN(UNION,match_domain_entry)(void **entry, void *user) +static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user) { S(UNION,match_domain_data) *data = user; uint32_t hash; struct isl_hash_table_entry *entry2; - PW *pw = *entry; isl_space *space; - space = FN(PW,get_domain_space)(pw); + space = FN(PART,get_domain_space)(part); hash = isl_space_get_hash(space); entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table, hash, &FN(UNION,set_has_dim), space, 0); isl_space_free(space); - if (!entry2) + if (!entry2) { + FN(PART,free)(part); return isl_stat_ok; + } - pw = FN(PW,copy)(pw); - pw = data->fn(pw, isl_set_copy(entry2->data)); + part = data->fn(part, isl_set_copy(entry2->data)); - data->res = FN(FN(UNION,add),PARTS)(data->res, pw); + data->res = FN(FN(UNION,add),PARTS)(data->res, part); if (!data->res) return isl_stat_error; @@ -820,7 +718,7 @@ static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u, data.uset = uset; data.res = FN(UNION,alloc_same_size)(u); - if (isl_hash_table_foreach(u->space->ctx, &u->table, + if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,match_domain_entry), &data) < 0) goto error; @@ -958,16 +856,12 @@ static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u) } #endif -static isl_stat FN(UNION,mul_isl_int_entry)(void **entry, void *user) +static __isl_give PART *FN(UNION,mul_isl_int_entry)(__isl_take PART *part, + void *user) { - PW **pw = (PW **)entry; isl_int *v = user; - *pw = FN(PW,mul_isl_int)(*pw, *v); - if (!*pw) - return isl_stat_error; - - return isl_stat_ok; + return FN(PW,mul_isl_int)(part, *v); } __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v) @@ -987,36 +881,21 @@ __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v) return zero; } - u = FN(UNION,cow)(u); + u = FN(UNION,transform_inplace)(u, &FN(UNION,mul_isl_int_entry), &v); if (isl_int_is_neg(v)) u = FN(UNION,negate_type)(u); - if (!u) - return NULL; - - if (isl_hash_table_foreach(u->space->ctx, &u->table, - &FN(UNION,mul_isl_int_entry), &v) < 0) - goto error; return u; -error: - FN(UNION,free)(u); - return NULL; } -/* Multiply *entry by the isl_val "user". - * - * Return 0 on success and -1 on error. +/* Multiply "part" by the isl_val "user" and return the result. */ -static isl_stat FN(UNION,scale_val_entry)(void **entry, void *user) +static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part, + void *user) { - PW **pw = (PW **)entry; isl_val *v = user; - *pw = FN(PW,scale_val)(*pw, isl_val_copy(v)); - if (!*pw) - return isl_stat_error; - - return isl_stat_ok; + return FN(PART,scale_val)(part, isl_val_copy(v)); } /* Multiply "u" by "v" and return the result. @@ -1048,15 +927,9 @@ __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u, isl_die(isl_val_get_ctx(v), isl_error_invalid, "expecting rational factor", goto error); - u = FN(UNION,cow)(u); + u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v); if (isl_val_is_neg(v)) u = FN(UNION,negate_type)(u); - if (!u) - return NULL; - - if (isl_hash_table_foreach(u->space->ctx, &u->table, - &FN(UNION,scale_val_entry), v) < 0) - goto error; isl_val_free(v); return u; @@ -1066,20 +939,14 @@ error: return NULL; } -/* Divide *entry by the isl_val "user". - * - * Return 0 on success and -1 on error. +/* Divide "part" by the isl_val "user" and return the result. */ -static isl_stat FN(UNION,scale_down_val_entry)(void **entry, void *user) +static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part, + void *user) { - PW **pw = (PW **)entry; isl_val *v = user; - *pw = FN(PW,scale_down_val)(*pw, isl_val_copy(v)); - if (!*pw) - return isl_stat_error; - - return isl_stat_ok; + return FN(PART,scale_down_val)(part, isl_val_copy(v)); } /* Divide "u" by "v" and return the result. @@ -1101,15 +968,9 @@ __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u, isl_die(isl_val_get_ctx(v), isl_error_invalid, "cannot scale down by zero", goto error); - u = FN(UNION,cow)(u); + u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v); if (isl_val_is_neg(v)) u = FN(UNION,negate_type)(u); - if (!u) - return NULL; - - if (isl_hash_table_foreach(FN(UNION,get_ctx)(u), &u->table, - &FN(UNION,scale_down_val_entry), v) < 0) - goto error; isl_val_free(v); return u; @@ -1150,6 +1011,7 @@ static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user) isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2) { S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true }; + int n1, n2; if (!u1 || !u2) return isl_bool_error; @@ -1157,6 +1019,12 @@ isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2) return isl_bool_true; if (u1->table.n != u2->table.n) return isl_bool_false; + n1 = FN(FN(UNION,n),PARTS)(u1); + n2 = FN(FN(UNION,n),PARTS)(u2); + if (n1 < 0 || n2 < 0) + return isl_bool_error; + if (n1 != n2) + return isl_bool_false; u1 = FN(UNION,copy)(u1); u2 = FN(UNION,copy)(u2); diff --git a/polly/lib/External/isl/ltmain.sh b/polly/lib/External/isl/ltmain.sh index bffda54187a..c29db3631ea 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.11 +# $progname: (GNU libtool) 2.4.2 Debian-2.4.2-1.10ubuntu1 # automake: $automake_version # autoconf: $autoconf_version # @@ -80,7 +80,7 @@ PROGRAM=libtool PACKAGE=libtool -VERSION="2.4.2 Debian-2.4.2-1.11" +VERSION="2.4.2 Debian-2.4.2-1.10ubuntu1" TIMESTAMP="" package_revision=1.3337 diff --git a/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c b/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c index 934aa82ef16..ab54229b829 100644 --- a/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c +++ b/polly/lib/External/isl/test_inputs/codegen/cloog/faber.c @@ -85,7 +85,7 @@ for (int c2 = max(c1 + 24, -2 * c1 + 30); c2 <= c1 - (3 * c0 + 17) / 14 + 56; c2 += 1) S1(c0, c1, c2); } - if (c0 >= 79 && c0 % 14 >= 9) { + if (c0 >= 70 && c0 % 14 >= 9) { for (int c2 = max(c0 / 14 + 19, -((3 * c0 + 14) / 14) + c0 / 14 + 44); c2 <= -((3 * c0 + 17) / 14) + c0 / 14 + 51; c2 += 1) S1(c0, c0 / 14 - 5, c2); } else if (c0 <= 69 && c0 % 14 >= 9) { diff --git a/polly/lib/External/isl/test_inputs/codegen/separate2.c b/polly/lib/External/isl/test_inputs/codegen/separate2.c index 81668215c9e..0fba4f1f552 100644 --- a/polly/lib/External/isl/test_inputs/codegen/separate2.c +++ b/polly/lib/External/isl/test_inputs/codegen/separate2.c @@ -2,7 +2,7 @@ if ((length - 1) % 16 <= 14) for (int c0 = 0; c0 <= 1; c0 += 1) for (int c5 = 0; c5 <= 31; c5 += 1) for (int c6 = max(0, 2 * ((length - 1) % 16) + 2 * c5 - 60); c6 <= 30; c6 += 1) { - if (length + c5 >= ((length - 1) % 32) + 2 && (length - 1) % 32 >= c5 && 2 * ((length - 1) % 32) + c6 >= 2 * c5 && 2 * c5 + 30 >= 2 * ((length - 1) % 32) + c6 && 2 * ((length - 1) % 32) + c6 == 2 * ((length - 1) % 16) + 2 * c5 && (2 * c5 - c6) % 32 == 0) + if (2 * length + c6 >= 2 * ((length - 1) % 16) + 4 && 2 * ((length - 1) % 16) >= c6 && 2 * ((length - 1) % 16) + 2 * c5 >= c6 && c6 + 62 >= 2 * ((length - 1) % 16) + 2 * c5 && 2 * ((length - 1) % 16) + 2 * c5 == 2 * ((length - 1) % 32) + c6 && (2 * c5 - c6) % 32 == 0) S_3(c0, 0, (c6 / 2) - ((length - 1) % 16) + length - 1); if (length <= 16 && length >= c5 + 1 && c6 >= 1 && length >= c6) S_0(c0, c5, c6 - 1); |
