From 800a3491e2d91a4b89eb5d8a7058827cdb94c9f4 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 12 Apr 2011 11:57:58 +0200 Subject: [PATCH] add isl_union_map_is_single_valued Signed-off-by: Sven Verdoolaege --- doc/user.pod | 1 + include/isl/union_map.h | 1 + isl_test.c | 46 ++++++++++++++++++++++++--- isl_union_map.c | 84 +++++++++++++++++++++++++++++++++++++++++++------ 4 files changed, 118 insertions(+), 14 deletions(-) diff --git a/doc/user.pod b/doc/user.pod index daf69da..90a629c 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -1172,6 +1172,7 @@ is already known to be empty. =item * Single-valuedness int isl_map_is_single_valued(__isl_keep isl_map *map); + int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap); =item * Bijectivity diff --git a/include/isl/union_map.h b/include/isl/union_map.h index fd59231..709c985 100644 --- a/include/isl/union_map.h +++ b/include/isl/union_map.h @@ -84,6 +84,7 @@ __isl_give isl_union_map *isl_union_map_deltas_map( __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset); int isl_union_map_is_empty(__isl_keep isl_union_map *umap); +int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap); int isl_union_map_is_subset(__isl_keep isl_union_map *umap1, __isl_keep isl_union_map *umap2); diff --git a/isl_test.c b/isl_test.c index 01839c3..d65ae0e 100644 --- a/isl_test.c +++ b/isl_test.c @@ -1506,20 +1506,54 @@ void test_dep(struct isl_ctx *ctx) isl_flow_free(flow); } -void test_sv(struct isl_ctx *ctx) +int test_sv(isl_ctx *ctx) { const char *str; isl_map *map; + isl_union_map *umap; + int sv; str = "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 9 }"; map = isl_map_read_from_str(ctx, str, -1); - assert(isl_map_is_single_valued(map)); + sv = isl_map_is_single_valued(map); isl_map_free(map); + if (sv < 0) + return -1; + if (!sv) + isl_die(ctx, isl_error_internal, + "map not detected as single valued", return -1); str = "[N] -> { [i] -> [f] : 0 <= i <= N and 0 <= i - 10 f <= 10 }"; map = isl_map_read_from_str(ctx, str, -1); - assert(!isl_map_is_single_valued(map)); + sv = isl_map_is_single_valued(map); isl_map_free(map); + if (sv < 0) + return -1; + if (sv) + isl_die(ctx, isl_error_internal, + "map detected as single valued", return -1); + + str = "{ S1[i] -> [i] : 0 <= i <= 9; S2[i] -> [i] : 0 <= i <= 9 }"; + umap = isl_union_map_read_from_str(ctx, str); + sv = isl_union_map_is_single_valued(umap); + isl_union_map_free(umap); + if (sv < 0) + return -1; + if (!sv) + isl_die(ctx, isl_error_internal, + "map not detected as single valued", return -1); + + str = "{ [i] -> S1[i] : 0 <= i <= 9; [i] -> S2[i] : 0 <= i <= 9 }"; + umap = isl_union_map_read_from_str(ctx, str); + sv = isl_union_map_is_single_valued(umap); + isl_union_map_free(umap); + if (sv < 0) + return -1; + if (sv) + isl_die(ctx, isl_error_internal, + "map detected as single valued", return -1); + + return 0; } void test_bijective_case(struct isl_ctx *ctx, const char *str, int bijective) @@ -1785,7 +1819,8 @@ int main() test_parse(ctx); test_pwqp(ctx); test_lex(ctx); - test_sv(ctx); + if (test_sv(ctx) < 0) + goto error; test_bijective(ctx); test_dep(ctx); test_read(ctx); @@ -1802,4 +1837,7 @@ int main() test_lexmin(ctx); isl_ctx_free(ctx); return 0; +error: + isl_ctx_free(ctx); + return -1; } diff --git a/isl_union_map.c b/isl_union_map.c index b7323c0..beddbf3 100644 --- a/isl_union_map.c +++ b/isl_union_map.c @@ -1485,31 +1485,44 @@ __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset) return (isl_basic_set *)isl_union_map_sample(uset); } -static int empty_entry(void **entry, void *user) +struct isl_forall_data { + int res; + int (*fn)(__isl_keep isl_map *map); +}; + +static int forall_entry(void **entry, void *user) { - int *empty = user; + struct isl_forall_data *data = user; isl_map *map = *entry; - if (isl_map_is_empty(map)) - return 0; + data->res = data->fn(map); + if (data->res < 0) + return -1; - *empty = 0; + if (!data->res) + return -1; - return -1; + return 0; } -__isl_give int isl_union_map_is_empty(__isl_keep isl_union_map *umap) +static int union_map_forall(__isl_keep isl_union_map *umap, + int (*fn)(__isl_keep isl_map *map)) { - int empty = 1; + struct isl_forall_data data = { 1, fn }; if (!umap) return -1; if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, - &empty_entry, &empty) < 0 && empty) + &forall_entry, &data) < 0 && data.res) return -1; - return empty; + return data.res; +} + +int isl_union_map_is_empty(__isl_keep isl_union_map *umap) +{ + return union_map_forall(umap, &isl_map_is_empty); } int isl_union_set_is_empty(__isl_keep isl_union_set *uset) @@ -1517,6 +1530,57 @@ int isl_union_set_is_empty(__isl_keep isl_union_set *uset) return isl_union_map_is_empty(uset); } +static int is_subset_of_identity(__isl_keep isl_map *map) +{ + int is_subset; + isl_dim *dim; + isl_map *id; + + if (!map) + return -1; + + if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out)) + return 0; + + dim = isl_map_get_dim(map); + id = isl_map_identity(dim); + + is_subset = isl_map_is_subset(map, id); + + isl_map_free(id); + + return is_subset; +} + +/* Check if the given map is single-valued. + * We simply compute + * + * M \circ M^-1 + * + * and check if the result is a subset of the identity mapping. + */ +int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap) +{ + isl_union_map *test; + int sv; + + if (isl_union_map_n_map(umap) == 1) { + isl_map *map = isl_union_map_copy_map(umap); + sv = isl_map_is_single_valued(map); + isl_map_free(map); + return sv; + } + + test = isl_union_map_reverse(isl_union_map_copy(umap)); + test = isl_union_map_apply_range(test, isl_union_map_copy(umap)); + + sv = union_map_forall(test, &is_subset_of_identity); + + isl_union_map_free(test); + + return sv; +} + static int zip_entry(void **entry, void *user) { isl_map *map = *entry; -- 2.7.4