1/* 2 * Copyright 2010 INRIA Saclay 3 * Copyright 2013 Ecole Normale Superieure 4 * 5 * Use of this software is governed by the MIT license 6 * 7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, 8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, 9 * 91893 Orsay, France 10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France 11 */ 12 13#undef TYPE 14#define TYPE UNION 15static 16#include "has_single_reference_templ.c" 17 18__isl_give UNION *FN(UNION,cow)(__isl_take UNION *u); 19 20isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u) 21{ 22 return u ? u->space->ctx : NULL; 23} 24 25/* Return the space of "u". 26 */ 27static __isl_keep isl_space *FN(UNION,peek_space)(__isl_keep UNION *u) 28{ 29 if (!u) 30 return NULL; 31 return u->space; 32} 33 34/* Return a copy of the space of "u". 35 */ 36__isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u) 37{ 38 return isl_space_copy(FN(UNION,peek_space)(u)); 39} 40 41/* Return the number of parameters of "u", where "type" 42 * is required to be set to isl_dim_param. 43 */ 44isl_size FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type) 45{ 46 if (!u) 47 return isl_size_error; 48 49 if (type != isl_dim_param) 50 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, 51 "can only reference parameters", return isl_size_error); 52 53 return isl_space_dim(u->space, type); 54} 55 56/* Return the position of the parameter with the given name 57 * in "u". 58 * Return -1 if no such dimension can be found. 59 */ 60int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type, 61 const char *name) 62{ 63 if (!u) 64 return -1; 65 return isl_space_find_dim_by_name(u->space, type, name); 66} 67 68#include "opt_type.h" 69 70static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space 71 OPT_TYPE_PARAM, int size) 72{ 73 UNION *u; 74 75 space = isl_space_params(space); 76 if (!space) 77 return NULL; 78 79 u = isl_calloc_type(space->ctx, UNION); 80 if (!u) 81 goto error; 82 83 u->ref = 1; 84 OPT_SET_TYPE(u->, type); 85 u->space = space; 86 if (isl_hash_table_init(space->ctx, &u->table, size) < 0) 87 return FN(UNION,free)(u); 88 89 return u; 90error: 91 isl_space_free(space); 92 return NULL; 93} 94 95/* Create an empty/zero union without specifying any parameters. 96 */ 97__isl_give UNION *FN(FN(UNION,ZERO),ctx)(isl_ctx *ctx OPT_TYPE_PARAM) 98{ 99 isl_space *space; 100 101 space = isl_space_unit(ctx); 102 return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC)); 103} 104 105__isl_give UNION *FN(FN(UNION,ZERO),space)(__isl_take isl_space *space 106 OPT_TYPE_PARAM) 107{ 108 return FN(UNION,alloc)(space OPT_TYPE_ARG(NO_LOC), 16); 109} 110 111/* This is an alternative name for the function above. 112 */ 113__isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM) 114{ 115 return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC)); 116} 117 118__isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u) 119{ 120 if (!u) 121 return NULL; 122 123 u->ref++; 124 return u; 125} 126 127/* Do the tuples of "space" correspond to those of the domain of "part"? 128 * That is, is the domain space of "part" equal to "space", ignoring parameters? 129 */ 130static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part, 131 __isl_keep isl_space *space) 132{ 133 return isl_space_has_domain_tuples(space, FN(PART,peek_space)(part)); 134} 135 136/* Extract the element of "u" living in "space" (ignoring parameters). 137 * 138 * Return the ZERO element if "u" does not contain any element 139 * living in "space". 140 */ 141__isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u, 142 __isl_take isl_space *space) 143{ 144 struct isl_hash_table_entry *entry; 145 146 entry = FN(UNION,find_part_entry)(u, space, 0); 147 if (!entry) 148 goto error; 149 if (entry == isl_hash_table_entry_none) 150 return FN(PART,ZERO)(space OPT_TYPE_ARG(u->)); 151 isl_space_free(space); 152 return FN(PART,copy)(entry->data); 153error: 154 isl_space_free(space); 155 return NULL; 156} 157 158/* Add "part" to "u". 159 * If "disjoint" is set, then "u" is not allowed to already have 160 * a part that is defined over a domain that overlaps with the domain 161 * of "part". 162 * Otherwise, compute the union sum of "part" and the part in "u" 163 * defined on the same space. 164 */ 165static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u, 166 __isl_take PART *part, int disjoint) 167{ 168 int empty; 169 struct isl_hash_table_entry *entry; 170 171 if (!part) 172 goto error; 173 174 empty = FN(PART,IS_ZERO)(part); 175 if (empty < 0) 176 goto error; 177 if (empty) { 178 FN(PART,free)(part); 179 return u; 180 } 181 182 u = FN(UNION,align_params)(u, FN(PART,get_space)(part)); 183 part = FN(PART,align_params)(part, FN(UNION,get_space)(u)); 184 185 u = FN(UNION,cow)(u); 186 187 if (!u) 188 goto error; 189 190 if (FN(UNION,check_disjoint_domain_other)(u, part) < 0) 191 goto error; 192 entry = FN(UNION,find_part_entry)(u, part->dim, 1); 193 if (!entry) 194 goto error; 195 196 if (!entry->data) 197 entry->data = part; 198 else { 199 if (disjoint && 200 FN(UNION,check_disjoint_domain)(entry->data, part) < 0) 201 goto error; 202 entry->data = FN(PART,union_add_)(entry->data, 203 FN(PART,copy)(part)); 204 empty = FN(PART,IS_ZERO)(entry->data); 205 if (empty < 0) 206 goto error; 207 if (empty) 208 u = FN(UNION,remove_part_entry)(u, entry); 209 FN(PART,free)(part); 210 } 211 212 return u; 213error: 214 FN(PART,free)(part); 215 FN(UNION,free)(u); 216 return NULL; 217} 218 219/* Add "part" to "u", where "u" is assumed not to already have 220 * a part that is defined on the same space as "part". 221 */ 222__isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u, 223 __isl_take PART *part) 224{ 225 return FN(UNION,add_part_generic)(u, part, 1); 226} 227 228/* Allocate a UNION with the same type (if any) and the same size as "u" and 229 * with space "space". 230 */ 231static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u, 232 __isl_take isl_space *space) 233{ 234 if (!u) 235 goto error; 236 return FN(UNION,alloc)(space OPT_TYPE_ARG(u->), u->table.n); 237error: 238 isl_space_free(space); 239 return NULL; 240} 241 242/* Allocate a UNION with the same space, the same type (if any) and 243 * the same size as "u". 244 */ 245static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u) 246{ 247 return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u)); 248} 249 250/* Data structure that specifies how isl_union_*_transform 251 * should modify the base expressions in the union expression. 252 * 253 * If "inplace" is set, then the base expression in the input union 254 * are modified in place. This means that "fn" should not 255 * change the meaning of the union or that the union only 256 * has a single reference. 257 * If "space" is not NULL, then a new union is created in this space. 258 * If "filter" is not NULL, then only the base expressions that satisfy "filter" 259 * are taken into account. 260 * "filter_user" is passed as the second argument to "filter". 261 * If "fn" it not NULL, then it is applied to each entry in the input. 262 * "fn_user" is passed as the second argument to "fn". 263 */ 264S(UNION,transform_control) { 265 int inplace; 266 isl_space *space; 267 isl_bool (*filter)(__isl_keep PART *part, void *user); 268 void *filter_user; 269 __isl_give PART *(*fn)(__isl_take PART *part, void *user); 270 void *fn_user; 271}; 272 273/* Internal data structure for isl_union_*_transform_space. 274 * "control" specifies how the base expressions should be modified. 275 * "res" collects the results (if control->inplace is not set). 276 */ 277S(UNION,transform_data) 278{ 279 S(UNION,transform_control) *control; 280 UNION *res; 281}; 282 283/* Apply control->fn to "part" and add the result to data->res or 284 * place it back into the input union if control->inplace is set. 285 */ 286static isl_stat FN(UNION,transform_entry)(void **entry, void *user) 287{ 288 S(UNION,transform_data) *data = (S(UNION,transform_data) *)user; 289 S(UNION,transform_control) *control = data->control; 290 PART *part = *entry; 291 292 if (control->filter) { 293 isl_bool handle; 294 295 handle = control->filter(part, control->filter_user); 296 if (handle < 0) 297 return isl_stat_error; 298 if (!handle) 299 return isl_stat_ok; 300 } 301 302 if (!control->inplace) 303 part = FN(PART,copy)(part); 304 if (control->fn) 305 part = control->fn(part, control->fn_user); 306 if (control->inplace) 307 *entry = part; 308 else 309 data->res = FN(FN(UNION,add),BASE)(data->res, part); 310 if (!part || !data->res) 311 return isl_stat_error; 312 313 return isl_stat_ok; 314} 315 316/* Return a UNION that is obtained by modifying "u" according to "control". 317 */ 318static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u, 319 S(UNION,transform_control) *control) 320{ 321 S(UNION,transform_data) data = { control }; 322 isl_space *space; 323 324 if (control->inplace) { 325 data.res = u; 326 } else { 327 if (control->space) 328 space = isl_space_copy(control->space); 329 else 330 space = FN(UNION,get_space)(u); 331 data.res = FN(UNION,alloc_same_size_on_space)(u, space); 332 } 333 if (FN(UNION,foreach_inplace)(u, &FN(UNION,transform_entry), &data) < 0) 334 data.res = FN(UNION,free)(data.res); 335 if (!control->inplace) 336 FN(UNION,free)(u); 337 return data.res; 338} 339 340/* Return a UNION living in "space" that is otherwise obtained by modifying "u" 341 * according to "control". 342 */ 343static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u, 344 __isl_take isl_space *space, S(UNION,transform_control) *control) 345{ 346 if (!space) 347 return FN(UNION,free)(u); 348 control->space = space; 349 u = FN(UNION,transform)(u, control); 350 isl_space_free(space); 351 return u; 352} 353 354/* Update "u" by applying "fn" to each entry. 355 * This operation is assumed not to change the number of entries nor 356 * the spaces of the entries. 357 * 358 * If there is only one reference to "u", then change "u" inplace. 359 * Otherwise, create a new UNION from "u" and discard the original. 360 */ 361static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u, 362 __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user) 363{ 364 S(UNION,transform_control) control = { .fn = fn, .fn_user = user }; 365 isl_bool single_ref; 366 367 single_ref = FN(UNION,has_single_reference)(u); 368 if (single_ref < 0) 369 return FN(UNION,free)(u); 370 if (single_ref) 371 control.inplace = 1; 372 return FN(UNION,transform)(u, &control); 373} 374 375/* An isl_union_*_transform callback for use in isl_union_*_dup 376 * that simply returns "part". 377 */ 378static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user) 379{ 380 return part; 381} 382 383__isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u) 384{ 385 S(UNION,transform_control) control = { .fn = &FN(UNION,copy_part) }; 386 387 u = FN(UNION,copy)(u); 388 return FN(UNION,transform)(u, &control); 389} 390 391__isl_give UNION *FN(UNION,cow)(__isl_take UNION *u) 392{ 393 if (!u) 394 return NULL; 395 396 if (u->ref == 1) 397 return u; 398 u->ref--; 399 return FN(UNION,dup)(u); 400} 401 402__isl_null UNION *FN(UNION,free)(__isl_take UNION *u) 403{ 404 if (!u) 405 return NULL; 406 407 if (--u->ref > 0) 408 return NULL; 409 410 isl_hash_table_foreach(u->space->ctx, &u->table, 411 &FN(UNION,free_u_entry), NULL); 412 isl_hash_table_clear(&u->table); 413 isl_space_free(u->space); 414 free(u); 415 return NULL; 416} 417 418static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user) 419{ 420 isl_reordering *exp = user; 421 422 exp = isl_reordering_extend_space(isl_reordering_copy(exp), 423 FN(PART,get_domain_space)(part)); 424 return FN(PART,realign_domain)(part, exp); 425} 426 427/* Reorder the parameters of "u" according to the given reordering. 428 */ 429static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u, 430 __isl_take isl_reordering *r) 431{ 432 S(UNION,transform_control) control = { 433 .fn = &FN(UNION,align_entry), 434 .fn_user = r, 435 }; 436 isl_space *space; 437 438 if (!u || !r) 439 goto error; 440 441 space = isl_reordering_get_space(r); 442 u = FN(UNION,transform_space)(u, space, &control); 443 isl_reordering_free(r); 444 return u; 445error: 446 FN(UNION,free)(u); 447 isl_reordering_free(r); 448 return NULL; 449} 450 451/* Align the parameters of "u" to those of "model". 452 */ 453__isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u, 454 __isl_take isl_space *model) 455{ 456 isl_space *space; 457 isl_bool equal_params; 458 isl_reordering *r; 459 460 space = FN(UNION,peek_space)(u); 461 equal_params = isl_space_has_equal_params(space, model); 462 if (equal_params < 0) 463 goto error; 464 if (equal_params) { 465 isl_space_free(model); 466 return u; 467 } 468 469 r = isl_parameter_alignment_reordering(space, model); 470 isl_space_free(model); 471 472 return FN(UNION,realign_domain)(u, r); 473error: 474 isl_space_free(model); 475 FN(UNION,free)(u); 476 return NULL; 477} 478 479/* Add "part" to *u, taking the union sum if "u" already has 480 * a part defined on the same space as "part". 481 */ 482static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user) 483{ 484 UNION **u = (UNION **)user; 485 486 *u = FN(UNION,add_part_generic)(*u, part, 0); 487 488 return isl_stat_ok; 489} 490 491/* Compute the sum of "u1" and "u2" on the union of their domains, 492 * with the actual sum on the shared domain and 493 * the defined expression on the symmetric difference of the domains. 494 * 495 * This is an internal function that is exposed under different 496 * names depending on whether the base expressions have a zero default 497 * value. 498 * If they do, then this function is called "add". 499 * Otherwise, it is called "union_add". 500 */ 501static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1, 502 __isl_take UNION *u2) 503{ 504 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2)); 505 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1)); 506 507 u1 = FN(UNION,cow)(u1); 508 509 if (!u1 || !u2) 510 goto error; 511 512 if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0) 513 goto error; 514 515 FN(UNION,free)(u2); 516 517 return u1; 518error: 519 FN(UNION,free)(u1); 520 FN(UNION,free)(u2); 521 return NULL; 522} 523 524#if !DEFAULT_IS_ZERO 525 526/* Compute the sum of "u1" and "u2" on the union of their domains, 527 * with the actual sum on the shared domain and 528 * the defined expression on the symmetric difference of the domains. 529 */ 530__isl_give UNION *FN(UNION,union_add)(__isl_take UNION *u1, 531 __isl_take UNION *u2) 532{ 533 return FN(UNION,union_add_)(u1, u2); 534} 535 536#endif 537 538__isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part) 539{ 540 isl_space *space; 541 UNION *u; 542 543 if (!part) 544 return NULL; 545 546 space = FN(PART,get_space)(part); 547 space = isl_space_drop_dims(space, isl_dim_in, 0, 548 isl_space_dim(space, isl_dim_in)); 549 space = isl_space_drop_dims(space, isl_dim_out, 0, 550 isl_space_dim(space, isl_dim_out)); 551 u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->)); 552 u = FN(FN(UNION,add),BASE)(u, part); 553 554 return u; 555} 556 557/* This function performs the same operation as isl_union_pw_*_from_pw_*, 558 * but is considered as a function on an isl_pw_* when exported. 559 */ 560__isl_give UNION *FN(FN(PART,to_union),BASE)(__isl_take PART *part) 561{ 562 return FN(FN(UNION,from),BASE)(part); 563} 564 565S(UNION,match_bin_data) { 566 UNION *u2; 567 UNION *res; 568 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *); 569}; 570 571/* Check if data->u2 has an element living in the same space as "part". 572 * If so, call data->fn on the two elements and add the result to 573 * data->res. 574 */ 575static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user) 576{ 577 S(UNION,match_bin_data) *data = user; 578 struct isl_hash_table_entry *entry2; 579 isl_space *space; 580 PART *part2; 581 582 space = FN(PART,get_space)(part); 583 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0); 584 isl_space_free(space); 585 if (!entry2) 586 goto error; 587 if (entry2 == isl_hash_table_entry_none) { 588 FN(PART,free)(part); 589 return isl_stat_ok; 590 } 591 592 part2 = entry2->data; 593 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out, 594 part2->dim, isl_dim_out)) 595 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid, 596 "entries should have the same range space", 597 goto error); 598 599 part = data->fn(part, FN(PART, copy)(entry2->data)); 600 601 data->res = FN(FN(UNION,add),BASE)(data->res, part); 602 if (!data->res) 603 return isl_stat_error; 604 605 return isl_stat_ok; 606error: 607 FN(PART,free)(part); 608 return isl_stat_error; 609} 610 611/* This function is currently only used from isl_polynomial.c 612 * and not from isl_fold.c. 613 */ 614static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1, 615 __isl_take UNION *u2, 616 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *)) 617 __attribute__ ((unused)); 618/* For each pair of elements in "u1" and "u2" living in the same space, 619 * call "fn" and collect the results. 620 */ 621static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1, 622 __isl_take UNION *u2, 623 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *)) 624{ 625 S(UNION,match_bin_data) data = { NULL, NULL, fn }; 626 627 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2)); 628 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1)); 629 630 if (!u1 || !u2) 631 goto error; 632 633 data.u2 = u2; 634 data.res = FN(UNION,alloc_same_size)(u1); 635 if (FN(FN(UNION,foreach),BASE)(u1, 636 &FN(UNION,match_bin_entry), &data) < 0) 637 goto error; 638 639 FN(UNION,free)(u1); 640 FN(UNION,free)(u2); 641 return data.res; 642error: 643 FN(UNION,free)(u1); 644 FN(UNION,free)(u2); 645 FN(UNION,free)(data.res); 646 return NULL; 647} 648 649/* Compute the sum of "u1" and "u2". 650 * 651 * If the base expressions have a default zero value, then the sum 652 * is computed on the union of the domains of "u1" and "u2". 653 * Otherwise, it is computed on their shared domains. 654 */ 655__isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2) 656{ 657#if DEFAULT_IS_ZERO 658 return FN(UNION,union_add_)(u1, u2); 659#else 660 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add)); 661#endif 662} 663 664S(UNION,any_set_data) { 665 isl_set *set; 666 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*); 667}; 668 669static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part, 670 void *user) 671{ 672 S(UNION,any_set_data) *data = user; 673 674 return data->fn(part, isl_set_copy(data->set)); 675} 676 677/* Update each element of "u" by calling "fn" on the element and "set". 678 */ 679static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u, 680 __isl_take isl_set *set, 681 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*)) 682{ 683 S(UNION,any_set_data) data = { NULL, fn }; 684 S(UNION,transform_control) control = { 685 .fn = &FN(UNION,any_set_entry), 686 .fn_user = &data, 687 }; 688 689 u = FN(UNION,align_params)(u, isl_set_get_space(set)); 690 set = isl_set_align_params(set, FN(UNION,get_space)(u)); 691 692 if (!u || !set) 693 goto error; 694 695 data.set = set; 696 u = FN(UNION,transform)(u, &control); 697 isl_set_free(set); 698 return u; 699error: 700 FN(UNION,free)(u); 701 isl_set_free(set); 702 return NULL; 703} 704 705/* Intersect the domain of "u" with the parameter domain "context". 706 */ 707__isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u, 708 __isl_take isl_set *set) 709{ 710 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params)); 711} 712 713/* Compute the gist of the domain of "u" with respect to 714 * the parameter domain "context". 715 */ 716__isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u, 717 __isl_take isl_set *set) 718{ 719 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params)); 720} 721 722/* Data structure that specifies how isl_union_*_match_domain_op 723 * should combine its arguments. 724 * 725 * If "filter" is not NULL, then only parts that pass the given 726 * filter are considered for matching. 727 * "fn" is applied to each part in the union and each corresponding 728 * set in the union set, i.e., such that the set lives in the same space 729 * as the domain of the part. 730 * If "match_space" is not NULL, then the set extracted from the union set 731 * does not live in the same space as the domain of the part, 732 * but rather in the space that results from calling "match_space" 733 * on this domain space. 734 */ 735S(UNION,match_domain_control) { 736 isl_bool (*filter)(__isl_keep PART *part); 737 __isl_give isl_space *(*match_space)(__isl_take isl_space *space); 738 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*); 739}; 740 741S(UNION,match_domain_data) { 742 isl_union_set *uset; 743 UNION *res; 744 S(UNION,match_domain_control) *control; 745}; 746 747/* Find the set in data->uset that lives in the same space as the domain 748 * of "part" (ignoring parameters), apply data->fn to *entry and this set 749 * (if any), and add the result to data->res. 750 */ 751static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user) 752{ 753 S(UNION,match_domain_data) *data = user; 754 struct isl_hash_table_entry *entry2; 755 isl_space *space; 756 757 if (data->control->filter) { 758 isl_bool pass = data->control->filter(part); 759 if (pass < 0 || !pass) { 760 FN(PART,free)(part); 761 return pass < 0 ? isl_stat_error : isl_stat_ok; 762 } 763 } 764 765 space = FN(PART,get_domain_space)(part); 766 if (data->control->match_space) 767 space = data->control->match_space(space); 768 entry2 = isl_union_set_find_entry(data->uset, space, 0); 769 isl_space_free(space); 770 if (!entry2 || entry2 == isl_hash_table_entry_none) { 771 FN(PART,free)(part); 772 return isl_stat_non_null(entry2); 773 } 774 775 part = data->control->fn(part, isl_set_copy(entry2->data)); 776 777 data->res = FN(FN(UNION,add),BASE)(data->res, part); 778 if (!data->res) 779 return isl_stat_error; 780 781 return isl_stat_ok; 782} 783 784/* Combine "u" and "uset" according to "control" 785 * and collect the results. 786 */ 787static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u, 788 __isl_take isl_union_set *uset, S(UNION,match_domain_control) *control) 789{ 790 S(UNION,match_domain_data) data = { NULL, NULL, control }; 791 792 if (!u || !uset) 793 goto error; 794 795 data.uset = uset; 796 data.res = FN(UNION,alloc_same_size)(u); 797 if (FN(FN(UNION,foreach),BASE)(u, 798 &FN(UNION,match_domain_entry), &data) < 0) 799 goto error; 800 801 FN(UNION,free)(u); 802 isl_union_set_free(uset); 803 return data.res; 804error: 805 FN(UNION,free)(u); 806 isl_union_set_free(uset); 807 FN(UNION,free)(data.res); 808 return NULL; 809} 810 811/* Intersect the domain of "u" with "uset". 812 * If "uset" is a parameters domain, then intersect the parameter 813 * domain of "u" with this set. 814 */ 815__isl_give UNION *FN(UNION,intersect_domain_union_set)(__isl_take UNION *u, 816 __isl_take isl_union_set *uset) 817{ 818 S(UNION,match_domain_control) control = { 819 .fn = &FN(PW,intersect_domain), 820 }; 821 822 if (isl_union_set_is_params(uset)) 823 return FN(UNION,intersect_params)(u, 824 isl_set_from_union_set(uset)); 825 return FN(UNION,match_domain_op)(u, uset, &control); 826} 827 828/* This is an alternative name for the function above. 829 */ 830__isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u, 831 __isl_take isl_union_set *uset) 832{ 833 return FN(UNION,intersect_domain_union_set)(u, uset); 834} 835 836/* Return true if this part should be kept. 837 * 838 * In particular, it should be kept if its domain space 839 * corresponds to "space". 840 */ 841static isl_bool FN(UNION,select_entry)(__isl_keep PART *part, void *user) 842{ 843 isl_space *space = user; 844 845 return FN(PW,has_domain_space_tuples)(part, space); 846} 847 848/* Remove any not element in "space" from the domain of "u". 849 * 850 * In particular, select any part of the function defined 851 * on this domain space. 852 */ 853__isl_give UNION *FN(UNION,intersect_domain_space)(__isl_take UNION *u, 854 __isl_take isl_space *space) 855{ 856 S(UNION,transform_control) control = { 857 .filter = &FN(UNION,select_entry), 858 .filter_user = space, 859 }; 860 861 u = FN(UNION,transform)(u, &control); 862 isl_space_free(space); 863 return u; 864} 865 866/* Is the domain of "pw" a wrapped relation? 867 */ 868static isl_bool FN(PW,domain_is_wrapping)(__isl_keep PW *pw) 869{ 870 return isl_space_domain_is_wrapping(FN(PW,peek_space)(pw)); 871} 872 873/* Intersect the domain of the wrapped relation inside the domain of "u" 874 * with "uset". 875 */ 876__isl_give UNION *FN(UNION,intersect_domain_wrapped_domain)(__isl_take UNION *u, 877 __isl_take isl_union_set *uset) 878{ 879 S(UNION,match_domain_control) control = { 880 .filter = &FN(PART,domain_is_wrapping), 881 .match_space = &isl_space_factor_domain, 882 .fn = &FN(PW,intersect_domain_wrapped_domain), 883 }; 884 885 return FN(UNION,match_domain_op)(u, uset, &control); 886} 887 888/* Intersect the range of the wrapped relation inside the domain of "u" 889 * with "uset". 890 */ 891__isl_give UNION *FN(UNION,intersect_domain_wrapped_range)(__isl_take UNION *u, 892 __isl_take isl_union_set *uset) 893{ 894 S(UNION,match_domain_control) control = { 895 .filter = &FN(PART,domain_is_wrapping), 896 .match_space = &isl_space_factor_range, 897 .fn = &FN(PW,intersect_domain_wrapped_range), 898 }; 899 900 return FN(UNION,match_domain_op)(u, uset, &control); 901} 902 903/* Take the set (which may be empty) in data->uset that lives 904 * in the same space as the domain of "pw", subtract it from the domain 905 * of "part" and return the result. 906 */ 907static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part, 908 void *user) 909{ 910 isl_union_set *uset = user; 911 isl_space *space; 912 isl_set *set; 913 914 space = FN(PART,get_domain_space)(part); 915 set = isl_union_set_extract_set(uset, space); 916 return FN(PART,subtract_domain)(part, set); 917} 918 919/* Subtract "uset" from the domain of "u". 920 */ 921__isl_give UNION *FN(UNION,subtract_domain_union_set)(__isl_take UNION *u, 922 __isl_take isl_union_set *uset) 923{ 924 S(UNION,transform_control) control = { 925 .fn = &FN(UNION,subtract_domain_entry), 926 .fn_user = uset, 927 }; 928 929 u = FN(UNION,transform)(u, &control); 930 isl_union_set_free(uset); 931 return u; 932} 933 934/* This is an alternative name for the function above. 935 */ 936__isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u, 937 __isl_take isl_union_set *uset) 938{ 939 return FN(UNION,subtract_domain_union_set)(u, uset); 940} 941 942/* Return true if this part should be kept. 943 * 944 * In particular, it should be kept if its domain space 945 * does not correspond to "space". 946 */ 947static isl_bool FN(UNION,filter_out_entry)(__isl_keep PART *part, void *user) 948{ 949 isl_space *space = user; 950 951 return isl_bool_not(FN(PW,has_domain_space_tuples)(part, space)); 952} 953 954/* Remove any element in "space" from the domain of "u". 955 * 956 * In particular, filter out any part of the function defined 957 * on this domain space. 958 */ 959__isl_give UNION *FN(UNION,subtract_domain_space)(__isl_take UNION *u, 960 __isl_take isl_space *space) 961{ 962 S(UNION,transform_control) control = { 963 .filter = &FN(UNION,filter_out_entry), 964 .filter_user = space, 965 }; 966 967 u = FN(UNION,transform)(u, &control); 968 isl_space_free(space); 969 return u; 970} 971 972__isl_give UNION *FN(UNION,gist)(__isl_take UNION *u, 973 __isl_take isl_union_set *uset) 974{ 975 S(UNION,match_domain_control) control = { 976 .fn = &FN(PW,gist), 977 }; 978 979 if (isl_union_set_is_params(uset)) 980 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset)); 981 return FN(UNION,match_domain_op)(u, uset, &control); 982} 983 984/* Coalesce an entry in a UNION. Coalescing is performed in-place. 985 * Since the UNION may have several references, the entry is only 986 * replaced if the coalescing is successful. 987 */ 988static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user) 989{ 990 PART **part_p = (PART **) entry; 991 PART *part; 992 993 part = FN(PART,copy)(*part_p); 994 part = FN(PW,coalesce)(part); 995 if (!part) 996 return isl_stat_error; 997 FN(PART,free)(*part_p); 998 *part_p = part; 999 1000 return isl_stat_ok; 1001} 1002 1003__isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u) 1004{ 1005 if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0) 1006 goto error; 1007 1008 return u; 1009error: 1010 FN(UNION,free)(u); 1011 return NULL; 1012} 1013 1014static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user) 1015{ 1016 isl_union_set **uset = (isl_union_set **)user; 1017 1018 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part)); 1019 1020 return isl_stat_ok; 1021} 1022 1023__isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u) 1024{ 1025 isl_union_set *uset; 1026 1027 uset = isl_union_set_empty(FN(UNION,get_space)(u)); 1028 if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0) 1029 goto error; 1030 1031 FN(UNION,free)(u); 1032 1033 return uset; 1034error: 1035 isl_union_set_free(uset); 1036 FN(UNION,free)(u); 1037 return NULL; 1038} 1039 1040#ifdef HAS_TYPE 1041/* Negate the type of "u". 1042 */ 1043static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u) 1044{ 1045 u = FN(UNION,cow)(u); 1046 if (!u) 1047 return NULL; 1048 u->type = isl_fold_type_negate(u->type); 1049 return u; 1050} 1051#else 1052/* Negate the type of "u". 1053 * Since "u" does not have a type, do nothing. 1054 */ 1055static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u) 1056{ 1057 return u; 1058} 1059#endif 1060 1061/* Multiply "part" by the isl_val "user" and return the result. 1062 */ 1063static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part, 1064 void *user) 1065{ 1066 isl_val *v = user; 1067 1068 return FN(PART,scale_val)(part, isl_val_copy(v)); 1069} 1070 1071/* Multiply "u" by "v" and return the result. 1072 */ 1073__isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u, 1074 __isl_take isl_val *v) 1075{ 1076 if (!u || !v) 1077 goto error; 1078 if (isl_val_is_one(v)) { 1079 isl_val_free(v); 1080 return u; 1081 } 1082 1083 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) { 1084 UNION *zero; 1085 isl_space *space = FN(UNION,get_space)(u); 1086 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->)); 1087 FN(UNION,free)(u); 1088 isl_val_free(v); 1089 return zero; 1090 } 1091 1092 if (!isl_val_is_rat(v)) 1093 isl_die(isl_val_get_ctx(v), isl_error_invalid, 1094 "expecting rational factor", goto error); 1095 1096 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v); 1097 if (isl_val_is_neg(v)) 1098 u = FN(UNION,negate_type)(u); 1099 1100 isl_val_free(v); 1101 return u; 1102error: 1103 isl_val_free(v); 1104 FN(UNION,free)(u); 1105 return NULL; 1106} 1107 1108/* Divide "part" by the isl_val "user" and return the result. 1109 */ 1110static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part, 1111 void *user) 1112{ 1113 isl_val *v = user; 1114 1115 return FN(PART,scale_down_val)(part, isl_val_copy(v)); 1116} 1117 1118/* Divide "u" by "v" and return the result. 1119 */ 1120__isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u, 1121 __isl_take isl_val *v) 1122{ 1123 if (!u || !v) 1124 goto error; 1125 if (isl_val_is_one(v)) { 1126 isl_val_free(v); 1127 return u; 1128 } 1129 1130 if (!isl_val_is_rat(v)) 1131 isl_die(isl_val_get_ctx(v), isl_error_invalid, 1132 "expecting rational factor", goto error); 1133 if (isl_val_is_zero(v)) 1134 isl_die(isl_val_get_ctx(v), isl_error_invalid, 1135 "cannot scale down by zero", goto error); 1136 1137 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v); 1138 if (isl_val_is_neg(v)) 1139 u = FN(UNION,negate_type)(u); 1140 1141 isl_val_free(v); 1142 return u; 1143error: 1144 isl_val_free(v); 1145 FN(UNION,free)(u); 1146 return NULL; 1147} 1148 1149/* Internal data structure for isl_union_*_every_*. 1150 * 1151 * "test" is the user-specified callback function. 1152 * "user" is the user-specified callback function argument. 1153 * 1154 * "res" is the final result, initialized to isl_bool_true. 1155 */ 1156S(UNION,every_data) { 1157 isl_bool (*test)(__isl_keep PW *pw, void *user); 1158 void *user; 1159 1160 isl_bool res; 1161}; 1162 1163/* Call data->test on the piecewise expression at *entry, 1164 * updating the result in data->res. 1165 * Abort if this result is no longer isl_bool_true. 1166 */ 1167static isl_stat FN(UNION,every_entry)(void **entry, void *user) 1168{ 1169 S(UNION,every_data) *data = user; 1170 PW *pw = *entry; 1171 1172 data->res = data->test(pw, data->user); 1173 if (data->res < 0 || !data->res) 1174 return isl_stat_error; 1175 1176 return isl_stat_ok; 1177} 1178 1179/* Does "test" succeed on every piecewise expression in "u"? 1180 */ 1181isl_bool FN(FN(UNION,every),BASE)(__isl_keep UNION *u, 1182 isl_bool (*test)(__isl_keep PW *pw, void *user), void *user) 1183{ 1184 S(UNION,every_data) data = { test, user }; 1185 1186 data.res = isl_bool_true; 1187 if (FN(UNION,foreach_inplace)(u, &FN(UNION,every_entry), &data) < 0 && 1188 data.res == isl_bool_true) 1189 return isl_bool_error; 1190 1191 return data.res; 1192} 1193 1194S(UNION,plain_is_equal_data) 1195{ 1196 UNION *u2; 1197}; 1198 1199static isl_bool FN(UNION,plain_is_equal_el)(__isl_keep PW *pw, void *user) 1200{ 1201 S(UNION,plain_is_equal_data) *data = user; 1202 struct isl_hash_table_entry *entry; 1203 1204 entry = FN(UNION,find_part_entry)(data->u2, pw->dim, 0); 1205 if (!entry) 1206 return isl_bool_error; 1207 if (entry == isl_hash_table_entry_none) 1208 return isl_bool_false; 1209 1210 return FN(PW,plain_is_equal)(pw, entry->data); 1211} 1212 1213isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2) 1214{ 1215 S(UNION,plain_is_equal_data) data; 1216 isl_size n1, n2; 1217 isl_bool is_equal; 1218 1219 if (!u1 || !u2) 1220 return isl_bool_error; 1221 if (u1 == u2) 1222 return isl_bool_true; 1223 if (u1->table.n != u2->table.n) 1224 return isl_bool_false; 1225 n1 = FN(FN(UNION,n),BASE)(u1); 1226 n2 = FN(FN(UNION,n),BASE)(u2); 1227 if (n1 < 0 || n2 < 0) 1228 return isl_bool_error; 1229 if (n1 != n2) 1230 return isl_bool_false; 1231 1232 u1 = FN(UNION,copy)(u1); 1233 u2 = FN(UNION,copy)(u2); 1234 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2)); 1235 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1)); 1236 if (!u1 || !u2) 1237 goto error; 1238 1239 data.u2 = u2; 1240 is_equal = FN(FN(UNION,every),BASE)(u1, 1241 &FN(UNION,plain_is_equal_el), &data); 1242 1243 FN(UNION,free)(u1); 1244 FN(UNION,free)(u2); 1245 1246 return is_equal; 1247error: 1248 FN(UNION,free)(u1); 1249 FN(UNION,free)(u2); 1250 return isl_bool_error; 1251} 1252 1253/* An isl_union_*_every_* callback that checks whether "pw" 1254 * does not involve any NaNs. 1255 */ 1256static isl_bool FN(UNION,no_nan_el)(__isl_keep PW *pw, void *user) 1257{ 1258 return isl_bool_not(FN(PW,involves_nan)(pw)); 1259} 1260 1261/* Does "u" involve any NaNs? 1262 */ 1263isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u) 1264{ 1265 isl_bool no_nan; 1266 1267 no_nan = FN(FN(UNION,every),BASE)(u, &FN(UNION,no_nan_el), NULL); 1268 1269 return isl_bool_not(no_nan); 1270} 1271 1272/* Internal data structure for isl_union_*_drop_dims. 1273 * type, first and n are passed to isl_*_drop_dims. 1274 */ 1275S(UNION,drop_dims_data) { 1276 enum isl_dim_type type; 1277 unsigned first; 1278 unsigned n; 1279}; 1280 1281/* Drop the parameters specified by "data" from "part" and return the result. 1282 */ 1283static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part, 1284 void *user) 1285{ 1286 S(UNION,drop_dims_data) *data = user; 1287 1288 return FN(PART,drop_dims)(part, data->type, data->first, data->n); 1289} 1290 1291/* Drop the specified parameters from "u". 1292 * That is, type is required to be isl_dim_param. 1293 */ 1294__isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u, 1295 enum isl_dim_type type, unsigned first, unsigned n) 1296{ 1297 isl_space *space; 1298 S(UNION,drop_dims_data) data = { type, first, n }; 1299 S(UNION,transform_control) control = { 1300 .fn = &FN(UNION,drop_dims_entry), 1301 .fn_user = &data, 1302 }; 1303 1304 if (!u) 1305 return NULL; 1306 1307 if (type != isl_dim_param) 1308 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, 1309 "can only project out parameters", 1310 return FN(UNION,free)(u)); 1311 1312 space = FN(UNION,get_space)(u); 1313 space = isl_space_drop_dims(space, type, first, n); 1314 return FN(UNION,transform_space)(u, space, &control); 1315} 1316 1317/* isl_union_*_every_* callback that checks whether "pw" 1318 * does not involve the parameter at position "pos". 1319 */ 1320static isl_bool FN(UNION,el_does_not_involve_param_at)(__isl_keep PW *pw, 1321 void *user) 1322{ 1323 unsigned *pos = user; 1324 1325 return isl_bool_not(FN(PW,involves_dims)(pw, isl_dim_param, *pos, 1)); 1326} 1327 1328/* This is a specialized version of isl_union_*_involves_dims for use 1329 * by isl_union_*_drop_unused_params. 1330 * 1331 * In particular, this function is only called on individual parameters, 1332 * so only this case needs to be supported. 1333 */ 1334static isl_bool FN(UNION,involves_dims)(__isl_take UNION *u, 1335 enum isl_dim_type type, unsigned first, unsigned n) 1336{ 1337 isl_bool none; 1338 1339 if (type != isl_dim_param) 1340 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, 1341 "only parameters can be involved", 1342 return isl_bool_error); 1343 if (n != 1) 1344 isl_die(FN(UNION,get_ctx)(u), isl_error_unsupported, 1345 "only check for single parameter is supported", 1346 return isl_bool_error); 1347 1348 none = FN(FN(UNION,every),BASE)(u, 1349 &FN(UNION,el_does_not_involve_param_at), &first); 1350 1351 return isl_bool_not(none); 1352} 1353 1354#undef TYPE 1355#define TYPE UNION 1356static 1357#include "isl_check_named_params_templ.c" 1358#include "isl_drop_unused_params_templ.c" 1359 1360/* Internal data structure for isl_union_*_set_dim_name. 1361 * pos is the position of the parameter that needs to be renamed. 1362 * s is the new name. 1363 */ 1364S(UNION,set_dim_name_data) { 1365 unsigned pos; 1366 const char *s; 1367}; 1368 1369/* Change the name of the parameter at position data->pos of "part" to data->s 1370 * and return the result. 1371 */ 1372static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part, 1373 void *user) 1374{ 1375 S(UNION,set_dim_name_data) *data = user; 1376 1377 return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s); 1378} 1379 1380/* Change the name of the parameter at position "pos" to "s". 1381 * That is, type is required to be isl_dim_param. 1382 */ 1383__isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u, 1384 enum isl_dim_type type, unsigned pos, const char *s) 1385{ 1386 S(UNION,set_dim_name_data) data = { pos, s }; 1387 S(UNION,transform_control) control = { 1388 .fn = &FN(UNION,set_dim_name_entry), 1389 .fn_user = &data, 1390 }; 1391 isl_space *space; 1392 1393 if (!u) 1394 return NULL; 1395 1396 if (type != isl_dim_param) 1397 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid, 1398 "can only set parameter names", 1399 return FN(UNION,free)(u)); 1400 1401 space = FN(UNION,get_space)(u); 1402 space = isl_space_set_dim_name(space, type, pos, s); 1403 return FN(UNION,transform_space)(u, space, &control); 1404} 1405 1406/* Reset the user pointer on all identifiers of parameters and tuples 1407 * of the space of "part" and return the result. 1408 */ 1409static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part, 1410 void *user) 1411{ 1412 return FN(PART,reset_user)(part); 1413} 1414 1415/* Reset the user pointer on all identifiers of parameters and tuples 1416 * of the spaces of "u". 1417 */ 1418__isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u) 1419{ 1420 S(UNION,transform_control) control = { 1421 .fn = &FN(UNION,reset_user_entry), 1422 }; 1423 isl_space *space; 1424 1425 space = FN(UNION,get_space)(u); 1426 space = isl_space_reset_user(space); 1427 return FN(UNION,transform_space)(u, space, &control); 1428} 1429 1430/* Add the base expression held by "entry" to "list". 1431 */ 1432static isl_stat FN(UNION,add_to_list)(void **entry, void *user) 1433{ 1434 PW *pw = *entry; 1435 LIST(PART) **list = user; 1436 1437 *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw)); 1438 if (!*list) 1439 return isl_stat_error; 1440 1441 return isl_stat_ok; 1442} 1443 1444/* Return a list containing all the base expressions in "u". 1445 * 1446 * First construct a list of the appropriate size and 1447 * then add all the elements. 1448 */ 1449__isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u) 1450{ 1451 isl_size n; 1452 LIST(PART) *list; 1453 1454 if (!u) 1455 return NULL; 1456 n = FN(FN(UNION,n),BASE)(u); 1457 if (n < 0) 1458 return NULL; 1459 list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n); 1460 if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0) 1461 return FN(LIST(PART),free)(list); 1462 1463 return list; 1464} 1465