From 2b783a80d4a29b5958e5653ba19ea062f429cf89 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sun, 28 Jun 2015 20:22:42 +0200 Subject: [PATCH] isl_union_*: use consistent hash values In 4d102a4 (only allow a single isl_pw_* object with given domain space in isl_union_pw_*, Sat Jun 7 11:19:41 2014 +0200), the isl_union_* objects were changed to only contain a single entry with a given domain space. However, the hash value in the table would still be computed based on the complete space, meaning that multiple entries with the same domain space would not necessarily get detected if the hash values for the complete spaces are different. Moreover, isl_union_*_eval would use the hash value of the domain space, meaning that it would not be able to find the right entry. Consistently use the hash value of the domain space to solve this problem. Moreover, extract out the handling into a new isl_union_*_find_part_entry function to reduce the risk of inconsistencies. Signed-off-by: Sven Verdoolaege --- Makefile.am | 1 + isl_fold.c | 11 ++---- isl_hash.c | 9 ++++- isl_hash_private.h | 8 +++++ isl_test.c | 30 ++++++++++++++++ isl_union_templ.c | 104 ++++++++++++++++++++++++++++++++++------------------- 6 files changed, 116 insertions(+), 47 deletions(-) create mode 100644 isl_hash_private.h diff --git a/Makefile.am b/Makefile.am index 87655b19..0d34fc09 100644 --- a/Makefile.am +++ b/Makefile.am @@ -95,6 +95,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 \ diff --git a/isl_fold.c b/isl_fold.c index a7f088ad..4d44112a 100644 --- a/isl_fold.c +++ b/isl_fold.c @@ -927,7 +927,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 +938,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 +1395,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; diff --git a/isl_hash.c b/isl_hash.c index 290807bc..89beecc7 100644 --- a/isl_hash.c +++ b/isl_hash.c @@ -9,7 +9,7 @@ #include #include -#include +#include #include #include "isl_config.h" @@ -149,6 +149,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/isl_hash_private.h b/isl_hash_private.h new file mode 100644 index 00000000..c6b272ae --- /dev/null +++ b/isl_hash_private.h @@ -0,0 +1,8 @@ +#ifndef ISL_HASH_PRIVATE +#define ISL_HASH_PRIVATE + +#include + +extern struct isl_hash_table_entry *isl_hash_table_entry_none; + +#endif diff --git a/isl_test.c b/isl_test.c index 4ec7deb5..bc26e928 100644 --- a/isl_test.c +++ b/isl_test.c @@ -4387,6 +4387,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; @@ -5928,6 +5957,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/isl_union_templ.c b/isl_union_templ.c index 4de0aa8c..56d068fb 100644 --- a/isl_union_templ.c +++ b/isl_union_templ.c @@ -10,11 +10,17 @@ * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ +#include + #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) +/* 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,16 +157,6 @@ 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"? - */ -static int FN(UNION,has_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); -} - /* This function is not currently used by isl_aff.c. */ static int FN(UNION,has_domain_space)(const void *entry, const void *val) @@ -194,6 +190,54 @@ static int FN(UNION,has_same_domain_space)(const void *entry, const void *val) 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; + isl_space *domain; + PART *part; + + if (!u) + return NULL; + + ctx = FN(UNION,get_ctx)(u); + domain = isl_space_domain(isl_space_copy(space)); + if (!domain) + return NULL; + hash = isl_space_get_hash(domain); + isl_space_free(domain); + 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); +} + /* Extract the element of "u" living in "space" (ignoring parameters). * * Return the ZERO element if "u" does not contain any element @@ -202,7 +246,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 +259,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 +285,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 +306,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) @@ -529,19 +562,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; @@ -1131,16 +1162,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; } -- 2.11.4.GIT