From 4f9e65f032cf0dba06e5949c3ab7ae4995c6e840 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 26 Jun 2015 22:21:59 +0200 Subject: [PATCH] allow multiple isl_pw_multi_aff objects with given domain space in union The ability for an isl_union_pw_multi_aff to contain multiple isl_pw_multi_aff objects with the same domain space was removed 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 reason was that there were no checks that these multiple isl_pw_multi_aff objects have disjoint domains, resulting in isl_union_pw_multi_aff objects that do not represent a function. It can however, be very useful to have isl_union_pw_multi_aff objects with multiple isl_pw_multi_aff objects defined over the same domain. In particular, when combining instance set splitting with grouping in a schedule tree, the corresponding contraction would map instances from the same space to different groups, which then could not be represented by an isl_union_pw_multi_aff. Allow an isl_union_pw_multi_aff object to have multiple isl_pw_multi_aff objects with the same domain space again by implementing the checks for disjoint domains. To facilitate such checks, the objects with the same domain space are grouped together. There is no point in doing the same for isl_union_pw_aff, isl_union_pw_qpolynomial or isl_union_pw_qpolynomial_fold because the base expressions have a fixed target space. Moreover, an isl_pw_qpolynomial is assumed to be defined over its entire domain space (with implicit value zero). Signed-off-by: Sven Verdoolaege --- Makefile.am | 1 + doc/user.pod | 11 +- isl_aff.c | 2 +- isl_test.c | 54 +++++++ isl_union_multi.c | 465 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 529 insertions(+), 4 deletions(-) create mode 100644 isl_union_multi.c diff --git a/Makefile.am b/Makefile.am index 4b1000a1..a7b0b6cb 100644 --- a/Makefile.am +++ b/Makefile.am @@ -326,6 +326,7 @@ EXTRA_DIST = \ 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/doc/user.pod b/doc/user.pod index 9eb4559c..db98c601 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -212,9 +212,6 @@ a regular basic set, rather than a rational basic set. =over -=item * Objects of type C can no longer contain -two or more C objects with the same domain space. - =item * The function C now consistently computes the sum on the shared definition domain. The function C has been added @@ -3128,6 +3125,14 @@ is that of the shared parameter space. The union expression types defined by C are C, C, C and C. +In case of +C, +C and C, +there can be at most one base expression for a given domain space. +In case of +C, +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/isl_aff.c b/isl_aff.c index 058f431b..fbbfde6c 100644 --- a/isl_aff.c +++ b/isl_aff.c @@ -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 +#include #include /* Given a function "cmp" that returns the set of elements where diff --git a/isl_test.c b/isl_test.c index 250128f0..3cb773c1 100644 --- a/isl_test.c +++ b/isl_test.c @@ -3896,6 +3896,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 +3939,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 +3993,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); diff --git a/isl_union_multi.c b/isl_union_multi.c new file mode 100644 index 00000000..e78e36bf --- /dev/null +++ b/isl_union_multi.c @@ -0,0 +1,465 @@ +/* + * Copyright 2010 INRIA Saclay + * Copyright 2013 Ecole Normale Superieure + * Copyright 2015 INRIA Paris-Rocquencourt + * + * Use of this software is governed by the MIT license + * + * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, + * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, + * 91893 Orsay, France + * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France + * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105, + * 78153 Le Chesnay Cedex France + */ + +#include +#include + +/* A group of expressions defined over the same domain space "domain_space". + * The entries of "part_table" are the individual expressions, + * keyed on the entire space of the expression. + * + * Each UNION has its own groups, so there can only ever be a single + * reference to each group. + */ +S(UNION,group) { + isl_space *domain_space; + struct isl_hash_table part_table; +}; + +/* A union of expressions defined over different disjoint domains. + * "space" describes the parameters. + * The entries of "table" are keyed on the domain space of the entry and + * contain groups of expressions that are defined over the same domain space. + */ +struct UNION { + int ref; + isl_space *space; + + struct isl_hash_table table; +}; + +/* Internal data structure for isl_union_*_foreach_group. + * "fn" is the function that needs to be called on each group. + */ +S(UNION,foreach_group_data) +{ + isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user); + void *user; +}; + +/* Call data->fn on the group stored at *entry. + */ +static isl_stat FN(UNION,call_on_group)(void **entry, void *user) +{ + S(UNION,group) *group = *entry; + S(UNION,foreach_group_data) *data; + + data = (S(UNION,foreach_group_data) *) user; + return data->fn(group, data->user); +} + +/* Call "fn" on each group of expressions in "u". + */ +static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u, + isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user), + void *user) +{ + S(UNION,foreach_group_data) data = { fn, user }; + + if (!u) + return isl_stat_error; + + return isl_hash_table_foreach(u->space->ctx, &u->table, + &FN(UNION,call_on_group), &data); +} + +/* A isl_union_*_foreach_group callback for counting the total number + * of expressions in a UNION. Add the number of expressions in "group" + * to *n. + */ +static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group, + void *user) +{ + int *n = user; + + if (!group) + return isl_stat_error; + + *n += group->part_table.n; + return isl_stat_ok; +} + +/* Return the number of base expressions in "u". + */ +int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u) +{ + int n; + + n = 0; + if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0) + n = -1; + return n; +} + +/* Free an entry in a group of expressions. + * Each entry in such a group is a single expression. + */ +static isl_stat FN(UNION,free_group_entry)(void **entry, void *user) +{ + PART *part = *entry; + + FN(PART,free)(part); + return isl_stat_ok; +} + +/* Free all memory allocated for "group" and return NULL. + */ +static __isl_null S(UNION,group) *FN(UNION,group_free)( + __isl_take S(UNION,group) *group) +{ + isl_ctx *ctx; + + if (!group) + return NULL; + + ctx = isl_space_get_ctx(group->domain_space); + isl_hash_table_foreach(ctx, &group->part_table, + &FN(UNION,free_group_entry), NULL); + isl_hash_table_clear(&group->part_table); + isl_space_free(group->domain_space); + free(group); + return NULL; +} + +/* Allocate a group of expressions defined over the same domain space + * with domain space "domain_space" and initial size "size". + */ +static __isl_give S(UNION,group) *FN(UNION,group_alloc)( + __isl_take isl_space *domain_space, int size) +{ + isl_ctx *ctx; + S(UNION,group) *group; + + if (!domain_space) + return NULL; + ctx = isl_space_get_ctx(domain_space); + group = isl_calloc_type(ctx, S(UNION,group)); + if (!group) + goto error; + group->domain_space = domain_space; + if (isl_hash_table_init(ctx, &group->part_table, size) < 0) + return FN(UNION,group_free)(group); + + return group; +error: + isl_space_free(domain_space); + return NULL; +} + +/* 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); +} + +/* Return a group equal to "group", but with a single reference. + * Since all groups have only a single reference, simply return "group". + */ +static __isl_give S(UNION,group) *FN(UNION,group_cow)( + __isl_take S(UNION,group) *group) +{ + return group; +} + +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; + + part = FN(PART,copy)(part); + if (!part) + return isl_stat_error; + return data->fn(part, data->user); +} + +/* Call data->fn on a copy of each expression in "group". + */ +static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group, + void *user) +{ + isl_ctx *ctx; + + if (!group) + return isl_stat_error; + + ctx = isl_space_get_ctx(group->domain_space); + return isl_hash_table_foreach(ctx, &group->part_table, + &FN(UNION,call_on_copy), 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 FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data); +} + +/* Is the domain space of the group of expressions at "entry" + * equal to "space"? + */ +static int FN(UNION,group_has_domain_space)(const void *entry, const void *val) +{ + S(UNION,group) *group = (S(UNION,group) *) entry; + isl_space *space = (isl_space *) val; + + return isl_space_is_domain_internal(group->domain_space, 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 group of expressions with the same domain space, + * creating one if needed. + * Then look for the expression living in the specified space in that group. + */ +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 *group_entry, *part_entry; + S(UNION,group) *group; + + if (!u || !space) + return NULL; + + ctx = FN(UNION,get_ctx)(u); + hash = isl_space_get_domain_hash(space); + group_entry = isl_hash_table_find(ctx, &u->table, hash, + &FN(UNION,group_has_domain_space), space, reserve); + if (!group_entry) + return reserve ? NULL : isl_hash_table_entry_none; + if (reserve && !group_entry->data) { + isl_space *domain = isl_space_domain(isl_space_copy(space)); + group = FN(UNION,group_alloc)(domain, 1); + group_entry->data = group; + } else { + group = group_entry->data; + if (reserve) + group = FN(UNION,group_cow)(group); + } + if (!group) + return NULL; + hash = isl_space_get_hash(space); + part_entry = isl_hash_table_find(ctx, &group->part_table, hash, + &FN(UNION,has_space), space, reserve); + if (!reserve && !part_entry) + return isl_hash_table_entry_none; + return part_entry; +} + +/* Remove "part_entry" from the hash table of "u". + * + * First look the group_entry in "u" holding the group that + * contains "part_entry". Remove "part_entry" from that group. + * If the group becomes empty, then also remove the group_entry from "u". + */ +static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u, + struct isl_hash_table_entry *part_entry) +{ + isl_ctx *ctx; + uint32_t hash; + PART *part; + struct isl_hash_table_entry *group_entry; + S(UNION,group) *group; + + if (!u || !part_entry) + return FN(UNION,free)(u); + + part = part_entry->data; + ctx = FN(UNION,get_ctx)(u); + hash = isl_space_get_domain_hash(part->dim); + group_entry = isl_hash_table_find(ctx, &u->table, hash, + &FN(UNION,group_has_domain_space), part->dim, 0); + if (!group_entry) + isl_die(ctx, isl_error_internal, "missing group", + return FN(UNION,free)(u)); + group = group_entry->data; + isl_hash_table_remove(ctx, &group->part_table, part_entry); + FN(PART,free)(part); + + if (group->part_table.n != 0) + return u; + + isl_hash_table_remove(ctx, &u->table, group_entry); + FN(UNION,group_free)(group); + + return u; +} + +/* Are the domains of "part1" and "part2" disjoint? + */ +static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1, + __isl_keep PART *part2) +{ + isl_set *dom1, *dom2; + isl_bool disjoint; + + if (!part1 || !part2) + return isl_bool_error; + dom1 = FN(PART,domain)(FN(PART,copy)(part1)); + dom2 = FN(PART,domain)(FN(PART,copy)(part2)); + disjoint = isl_set_is_disjoint(dom1, dom2); + isl_set_free(dom1); + isl_set_free(dom2); + + return disjoint; +} + +/* Check that the expression at *entry has a domain that is disjoint + * from that of "part", unless they also have the same target space. + */ +static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user) +{ + PART *part = user; + PART *other = *entry; + isl_bool equal; + isl_bool disjoint; + + equal = isl_space_is_equal(part->dim, other->dim); + if (equal < 0) + return isl_stat_error; + if (equal) + return isl_stat_ok; + + disjoint = FN(UNION,disjoint_domain)(part, other); + if (disjoint < 0) + return isl_stat_error; + if (!disjoint) + isl_die(FN(PART,get_ctx)(part), isl_error_invalid, + "overlapping domain with other part", + return isl_stat_error); + return isl_stat_ok; +} + +/* Check that the domain of "part" is disjoint from the domain of the entries + * in "u" that are defined on the same domain space, but have a different + * target space. + * If there is no group of expressions in "u" with the same domain space, + * then everything is fine. Otherwise, check the individual expressions + * in that group. + */ +static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u, + __isl_keep PART *part) +{ + isl_ctx *ctx; + uint32_t hash; + struct isl_hash_table_entry *group_entry; + S(UNION,group) *group; + + if (!u || !part) + return isl_stat_error; + ctx = FN(UNION,get_ctx)(u); + hash = isl_space_get_domain_hash(part->dim); + group_entry = isl_hash_table_find(ctx, &u->table, hash, + &FN(UNION,group_has_domain_space), part->dim, 0); + if (!group_entry) + return isl_stat_ok; + group = group_entry->data; + return isl_hash_table_foreach(ctx, &group->part_table, + &FN(UNION,check_disjoint_domain_entry), part); +} + +/* Check that the domain of "part1" is disjoint from the domain of "part2". + * This check is performed before "part2" is added to a UNION to ensure + * that the UNION expression remains a function. + */ +static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1, + __isl_keep PART *part2) +{ + isl_bool disjoint; + + disjoint = FN(UNION,disjoint_domain)(part1, part2); + if (disjoint < 0) + return isl_stat_error; + if (!disjoint) + isl_die(FN(PART,get_ctx)(part1), isl_error_invalid, + "domain of additional part should be disjoint", + return isl_stat_error); + return isl_stat_ok; +} + +/* Internal data structure for isl_union_*_foreach_inplace. + * "fn" is the function that needs to be called on each entry. + */ +S(UNION,foreach_inplace_data) +{ + isl_stat (*fn)(void **entry, void *user); + void *user; +}; + +/* isl_union_*_foreach_group callback for calling data->fn on + * each part entry in the group. + */ +static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group, + void *user) +{ + isl_ctx *ctx; + S(UNION,foreach_inplace_data) *data; + + if (!group) + return isl_stat_error; + + data = (S(UNION,foreach_inplace_data) *) user; + ctx = isl_space_get_ctx(group->domain_space); + return isl_hash_table_foreach(ctx, &group->part_table, + data->fn, data->user); +} + +/* 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) +{ + S(UNION,foreach_inplace_data) data = { fn, user }; + + return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data); +} + +/* Does "u" have a single reference? + * That is, can we change "u" inplace? + */ +static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u) +{ + if (!u) + return isl_bool_error; + return u->ref == 1; +} + +static isl_stat FN(UNION,free_u_entry)(void **entry, void *user) +{ + S(UNION,group) *group = *entry; + FN(UNION,group_free)(group); + return isl_stat_ok; +} + +#include -- 2.11.4.GIT