550 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 * Copyright 2013 Ecole Normale Superieure4 * Copyright 2015 INRIA Paris-Rocquencourt5 *6 * Use of this software is governed by the MIT license7 *8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,10 * 91893 Orsay, France11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France12 * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,13 * 78153 Le Chesnay Cedex France14 */15 16#include <isl/hash.h>17#include <isl_union_macro.h>18 19/* A group of expressions defined over the same domain space "domain_space".20 * The entries of "part_table" are the individual expressions,21 * keyed on the entire space of the expression (ignoring parameters).22 *23 * Each UNION has its own groups, so there can only ever be a single24 * reference to each group.25 */26S(UNION,group) {27 isl_space *domain_space;28 struct isl_hash_table part_table;29};30 31/* A union of expressions defined over different disjoint domains.32 * "space" describes the parameters.33 * The entries of "table" are keyed on the domain space of the entry34 * (ignoring parameters) and35 * contain groups of expressions that are defined over the same domain space.36 */37struct UNION {38 int ref;39 isl_space *space;40 41 struct isl_hash_table table;42};43 44/* Internal data structure for isl_union_*_foreach_group.45 * "fn" is the function that needs to be called on each group.46 */47S(UNION,foreach_group_data)48{49 isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user);50 void *user;51};52 53/* Call data->fn on the group stored at *entry.54 */55static isl_stat FN(UNION,call_on_group)(void **entry, void *user)56{57 S(UNION,group) *group = *entry;58 S(UNION,foreach_group_data) *data;59 60 data = (S(UNION,foreach_group_data) *) user;61 return data->fn(group, data->user);62}63 64/* Call "fn" on each group of expressions in "u".65 */66static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u,67 isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user),68 void *user)69{70 S(UNION,foreach_group_data) data = { fn, user };71 72 if (!u)73 return isl_stat_error;74 75 return isl_hash_table_foreach(u->space->ctx, &u->table,76 &FN(UNION,call_on_group), &data);77}78 79/* A isl_union_*_foreach_group callback for counting the total number80 * of expressions in a UNION. Add the number of expressions in "group"81 * to *n.82 */83static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,84 void *user)85{86 int *n = user;87 88 if (!group)89 return isl_stat_error;90 91 *n += group->part_table.n;92 return isl_stat_ok;93}94 95/* Return the number of base expressions in "u".96 */97isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)98{99 int n;100 101 n = 0;102 if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0)103 return isl_size_error;104 return n;105}106 107/* Free an entry in a group of expressions.108 * Each entry in such a group is a single expression.109 */110static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)111{112 PART *part = *entry;113 114 FN(PART,free)(part);115 return isl_stat_ok;116}117 118/* Free all memory allocated for "group" and return NULL.119 */120static __isl_null S(UNION,group) *FN(UNION,group_free)(121 __isl_take S(UNION,group) *group)122{123 isl_ctx *ctx;124 125 if (!group)126 return NULL;127 128 ctx = isl_space_get_ctx(group->domain_space);129 isl_hash_table_foreach(ctx, &group->part_table,130 &FN(UNION,free_group_entry), NULL);131 isl_hash_table_clear(&group->part_table);132 isl_space_free(group->domain_space);133 free(group);134 return NULL;135}136 137/* Allocate a group of expressions defined over the same domain space138 * with domain space "domain_space" and initial size "size".139 */140static __isl_give S(UNION,group) *FN(UNION,group_alloc)(141 __isl_take isl_space *domain_space, int size)142{143 isl_ctx *ctx;144 S(UNION,group) *group;145 146 if (!domain_space)147 return NULL;148 ctx = isl_space_get_ctx(domain_space);149 group = isl_calloc_type(ctx, S(UNION,group));150 if (!group)151 goto error;152 group->domain_space = domain_space;153 if (isl_hash_table_init(ctx, &group->part_table, size) < 0)154 return FN(UNION,group_free)(group);155 156 return group;157error:158 isl_space_free(domain_space);159 return NULL;160}161 162/* Is the space of "entry" equal to "space", ignoring parameters?163 */164static isl_bool FN(UNION,has_space_tuples)(const void *entry, const void *val)165{166 PART *part = (PART *) entry;167 isl_space *space = (isl_space *) val;168 isl_space *part_space;169 170 part_space = FN(PART,peek_space)(part);171 return isl_space_has_equal_tuples(part_space, space);172}173 174/* Return a group equal to "group", but with a single reference.175 * Since all groups have only a single reference, simply return "group".176 */177static __isl_give S(UNION,group) *FN(UNION,group_cow)(178 __isl_take S(UNION,group) *group)179{180 return group;181}182 183S(UNION,foreach_data)184{185 isl_stat (*fn)(__isl_take PART *part, void *user);186 void *user;187};188 189static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)190{191 PART *part = *entry;192 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user;193 194 part = FN(PART,copy)(part);195 if (!part)196 return isl_stat_error;197 return data->fn(part, data->user);198}199 200/* Call data->fn on a copy of each expression in "group".201 */202static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,203 void *user)204{205 isl_ctx *ctx;206 207 if (!group)208 return isl_stat_error;209 210 ctx = isl_space_get_ctx(group->domain_space);211 return isl_hash_table_foreach(ctx, &group->part_table,212 &FN(UNION,call_on_copy), user);213}214 215isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,216 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)217{218 S(UNION,foreach_data) data = { fn, user };219 220 if (!u)221 return isl_stat_error;222 223 return FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data);224}225 226/* Is the domain space of the group of expressions at "entry"227 * equal to that of "space", ignoring parameters?228 */229static isl_bool FN(UNION,group_has_same_domain_space_tuples)(const void *entry,230 const void *val)231{232 S(UNION,group) *group = (S(UNION,group) *) entry;233 isl_space *space = (isl_space *) val;234 235 return isl_space_has_domain_tuples(group->domain_space, space);236}237 238/* Return the entry, if any, in "u" that lives in "space".239 * If "reserve" is set, then an entry is created if it does not exist yet.240 * Return NULL on error and isl_hash_table_entry_none if no entry was found.241 * Note that when "reserve" is set, the function will never return242 * isl_hash_table_entry_none.243 *244 * First look for the group of expressions with the same domain space,245 * creating one if needed.246 * Then look for the expression living in the specified space in that group.247 */248static struct isl_hash_table_entry *FN(UNION,find_part_entry)(249 __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)250{251 isl_ctx *ctx;252 uint32_t hash;253 struct isl_hash_table_entry *group_entry;254 S(UNION,group) *group;255 256 if (!u || !space)257 return NULL;258 259 ctx = FN(UNION,get_ctx)(u);260 hash = isl_space_get_tuple_domain_hash(space);261 group_entry = isl_hash_table_find(ctx, &u->table, hash,262 &FN(UNION,group_has_same_domain_space_tuples), space, reserve);263 if (!group_entry || group_entry == isl_hash_table_entry_none)264 return group_entry;265 if (reserve && !group_entry->data) {266 isl_space *domain = isl_space_domain(isl_space_copy(space));267 group = FN(UNION,group_alloc)(domain, 1);268 group_entry->data = group;269 } else {270 group = group_entry->data;271 if (reserve)272 group = FN(UNION,group_cow)(group);273 }274 if (!group)275 return NULL;276 hash = isl_space_get_tuple_hash(space);277 return isl_hash_table_find(ctx, &group->part_table, hash,278 &FN(UNION,has_space_tuples), space, reserve);279}280 281/* Remove "part_entry" from the hash table of "u".282 *283 * First look the group_entry in "u" holding the group that284 * contains "part_entry". Remove "part_entry" from that group.285 * If the group becomes empty, then also remove the group_entry from "u".286 */287static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,288 struct isl_hash_table_entry *part_entry)289{290 isl_ctx *ctx;291 uint32_t hash;292 isl_space *space;293 PART *part;294 struct isl_hash_table_entry *group_entry;295 S(UNION,group) *group;296 297 if (!u || !part_entry)298 return FN(UNION,free)(u);299 300 part = part_entry->data;301 ctx = FN(UNION,get_ctx)(u);302 space = FN(PART,peek_space)(part);303 hash = isl_space_get_tuple_domain_hash(space);304 group_entry = isl_hash_table_find(ctx, &u->table, hash,305 &FN(UNION,group_has_same_domain_space_tuples), space, 0);306 if (!group_entry)307 return FN(UNION,free)(u);308 if (group_entry == isl_hash_table_entry_none)309 isl_die(ctx, isl_error_internal, "missing group",310 return FN(UNION,free)(u));311 group = group_entry->data;312 isl_hash_table_remove(ctx, &group->part_table, part_entry);313 FN(PART,free)(part);314 315 if (group->part_table.n != 0)316 return u;317 318 isl_hash_table_remove(ctx, &u->table, group_entry);319 FN(UNION,group_free)(group);320 321 return u;322}323 324/* Are the domains of "part1" and "part2" disjoint?325 */326static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,327 __isl_keep PART *part2)328{329 isl_set *dom1, *dom2;330 isl_bool disjoint;331 332 if (!part1 || !part2)333 return isl_bool_error;334 dom1 = FN(PART,domain)(FN(PART,copy)(part1));335 dom2 = FN(PART,domain)(FN(PART,copy)(part2));336 disjoint = isl_set_is_disjoint(dom1, dom2);337 isl_set_free(dom1);338 isl_set_free(dom2);339 340 return disjoint;341}342 343/* Check that the expression at *entry has a domain that is disjoint344 * from that of "part", unless they also have the same target space.345 */346static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)347{348 PART *part = user;349 PART *other = *entry;350 isl_bool equal;351 isl_bool disjoint;352 353 equal = isl_space_is_equal(part->dim, other->dim);354 if (equal < 0)355 return isl_stat_error;356 if (equal)357 return isl_stat_ok;358 359 disjoint = FN(UNION,disjoint_domain)(part, other);360 if (disjoint < 0)361 return isl_stat_error;362 if (!disjoint)363 isl_die(FN(PART,get_ctx)(part), isl_error_invalid,364 "overlapping domain with other part",365 return isl_stat_error);366 return isl_stat_ok;367}368 369/* Check that the domain of "part" is disjoint from the domain of the entries370 * in "u" that are defined on the same domain space, but have a different371 * target space.372 * If there is no group of expressions in "u" with the same domain space,373 * then everything is fine. Otherwise, check the individual expressions374 * in that group.375 */376static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,377 __isl_keep PART *part)378{379 isl_ctx *ctx;380 uint32_t hash;381 isl_space *space;382 struct isl_hash_table_entry *group_entry;383 S(UNION,group) *group;384 385 if (!u || !part)386 return isl_stat_error;387 ctx = FN(UNION,get_ctx)(u);388 space = FN(PART,peek_space)(part);389 hash = isl_space_get_tuple_domain_hash(space);390 group_entry = isl_hash_table_find(ctx, &u->table, hash,391 &FN(UNION,group_has_same_domain_space_tuples), space, 0);392 if (!group_entry)393 return isl_stat_error;394 if (group_entry == isl_hash_table_entry_none)395 return isl_stat_ok;396 group = group_entry->data;397 return isl_hash_table_foreach(ctx, &group->part_table,398 &FN(UNION,check_disjoint_domain_entry), part);399}400 401/* Check that the domain of "part1" is disjoint from the domain of "part2".402 * This check is performed before "part2" is added to a UNION to ensure403 * that the UNION expression remains a function.404 */405static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,406 __isl_keep PART *part2)407{408 isl_bool disjoint;409 410 disjoint = FN(UNION,disjoint_domain)(part1, part2);411 if (disjoint < 0)412 return isl_stat_error;413 if (!disjoint)414 isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,415 "domain of additional part should be disjoint",416 return isl_stat_error);417 return isl_stat_ok;418}419 420/* Internal data structure for isl_union_*_foreach_inplace.421 * "fn" is the function that needs to be called on each entry.422 */423S(UNION,foreach_inplace_data)424{425 isl_stat (*fn)(void **entry, void *user);426 void *user;427};428 429/* isl_union_*_foreach_group callback for calling data->fn on430 * each part entry in the group.431 */432static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,433 void *user)434{435 isl_ctx *ctx;436 S(UNION,foreach_inplace_data) *data;437 438 if (!group)439 return isl_stat_error;440 441 data = (S(UNION,foreach_inplace_data) *) user;442 ctx = isl_space_get_ctx(group->domain_space);443 return isl_hash_table_foreach(ctx, &group->part_table,444 data->fn, data->user);445}446 447/* Call "fn" on each part entry of "u".448 */449static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,450 isl_stat (*fn)(void **part, void *user), void *user)451{452 S(UNION,foreach_inplace_data) data = { fn, user };453 454 return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data);455}456 457static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)458{459 S(UNION,group) *group = *entry;460 FN(UNION,group_free)(group);461 return isl_stat_ok;462}463 464/* Does "u" have an obviously empty definition domain?465 */466isl_bool FN(UNION,plain_is_empty)(__isl_take UNION *u)467{468 if (!u)469 return isl_bool_error;470 return isl_bool_ok(u->table.n == 0);471}472 473/* Set "single" to true if this group of expressions474 * contains an expression living in exactly one space.475 */476static isl_stat FN(UNION,group_single_space)(__isl_keep S(UNION,group) *group,477 void *user)478{479 isl_bool *single = user;480 481 if (!group)482 return isl_stat_error;483 *single = isl_bool_ok(group->part_table.n == 1);484 return isl_stat_ok;485}486 487/* Can this union expression be converted to a single base expression?488 * That is, does it contain a base expression in exactly one space?489 * In particular, is only one domain space involved and490 * is only a single expression associated to that domain?491 */492isl_bool FN(FN(UNION,isa),BASE)(__isl_take UNION *u)493{494 isl_bool single;495 496 if (!u)497 return isl_bool_error;498 if (u->table.n != 1)499 return isl_bool_false;500 if (FN(UNION,foreach_group)(u,501 &FN(UNION,group_single_space), &single) < 0)502 return isl_bool_error;503 return single;504}505 506/* Callback for isl_union_*_foreach_inplace call507 * on a union expression with a single base expression.508 * Store that base expression in "user".509 * This callback should only be called once510 * for any given isl_union_*_foreach_inplace call.511 */512static isl_stat FN(UNION,extract_part)(void **entry, void *user)513{514 PART **part_p = user;515 PART *part = *entry;516 517 if (*part_p)518 isl_die(FN(PART,get_ctx)(part), isl_error_internal,519 "more than one part", return isl_stat_error);520 *part_p = FN(PART,copy)(part);521 if (!*part_p)522 return isl_stat_error;523 return isl_stat_ok;524}525 526/* Convert the union expression to its single base expression.527 */528__isl_give PART *FN(FN(UNION,as),BASE)(__isl_take UNION *u)529{530 isl_bool has_single_space;531 PART *part = NULL;532 533 has_single_space = FN(FN(UNION,isa),BASE)(u);534 if (has_single_space < 0)535 goto error;536 if (!has_single_space)537 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,538 "expecting elements in exactly one space",539 goto error);540 if (FN(UNION,foreach_inplace)(u, &FN(UNION,extract_part), &part) < 0)541 part = FN(PART,free)(part);542 FN(UNION,free)(u);543 return part;544error:545 FN(UNION,free)(u);546 return NULL;547}548 549#include <isl_union_templ.c>550