diff options
Diffstat (limited to 'isl_union_multi.c')
-rw-r--r-- | isl_union_multi.c | 465 |
1 files changed, 465 insertions, 0 deletions
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 <isl_hash_private.h> +#include <isl_union_macro.h> + +/* 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 <isl_union_templ.c> |