1 /* 2 * Copyright 2010 INRIA Saclay 3 * Copyright 2013 Ecole Normale Superieure 4 * Copyright 2015 INRIA Paris-Rocquencourt 5 * 6 * Use of this software is governed by the MIT license 7 * 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, France 11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France 12 * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105, 13 * 78153 Le Chesnay Cedex France 14 */ 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 single 24 * reference to each group. 25 */ 26 S(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 entry 34 * (ignoring parameters) and 35 * contain groups of expressions that are defined over the same domain space. 36 */ 37 struct 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 */ 47 S(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 */ 55 static 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 */ 66 static 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 number 80 * of expressions in a UNION. Add the number of expressions in "group" 81 * to *n. 82 */ 83 static 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 */ 97 isl_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 */ 110 static 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 */ 120 static __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 space 138 * with domain space "domain_space" and initial size "size". 139 */ 140 static __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; 157 error: 158 isl_space_free(domain_space); 159 return NULL; 160 } 161 162 /* Is the space of "entry" equal to "space", ignoring parameters? 163 */ 164 static 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 */ 177 static __isl_give S(UNION,group) *FN(UNION,group_cow)( 178 __isl_take S(UNION,group) *group) 179 { 180 return group; 181 } 182 183 S(UNION,foreach_data) 184 { 185 isl_stat (*fn)(__isl_take PART *part, void *user); 186 void *user; 187 }; 188 189 static 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 */ 202 static 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 215 isl_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 */ 229 static 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 return 242 * 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 */ 248 static 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 that 284 * contains "part_entry". Remove "part_entry" from that group. 285 * If the group becomes empty, then also remove the group_entry from "u". 286 */ 287 static __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 */ 326 static 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 disjoint 344 * from that of "part", unless they also have the same target space. 345 */ 346 static 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 entries 370 * in "u" that are defined on the same domain space, but have a different 371 * 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 expressions 374 * in that group. 375 */ 376 static 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 ensure 403 * that the UNION expression remains a function. 404 */ 405 static 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 */ 423 S(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 on 430 * each part entry in the group. 431 */ 432 static 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 */ 449 static 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 457 static 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 */ 466 isl_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 expressions 474 * contains an expression living in exactly one space. 475 */ 476 static 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 and 490 * is only a single expression associated to that domain? 491 */ 492 isl_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 call 507 * on a union expression with a single base expression. 508 * Store that base expression in "user". 509 * This callback should only be called once 510 * for any given isl_union_*_foreach_inplace call. 511 */ 512 static 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; 544 error: 545 FN(UNION,free)(u); 546 return NULL; 547 } 548 549 #include <isl_union_templ.c> 550