1/* 2 * Copyright 2010-2011 INRIA Saclay 3 * 4 * Use of this software is governed by the MIT license 5 * 6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, 7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, 8 * 91893 Orsay, France 9 */ 10 11#define ISL_DIM_H 12#include <isl_map_private.h> 13#include <isl/ctx.h> 14#include <isl/hash.h> 15#include <isl/aff.h> 16#include <isl/map.h> 17#include <isl/set.h> 18#include <isl_space_private.h> 19#include <isl_union_map_private.h> 20#include <isl/union_set.h> 21 22/* Is this union set a parameter domain? 23 */ 24int isl_union_set_is_params(__isl_keep isl_union_set *uset) 25{ 26 isl_set *set; 27 int params; 28 29 if (!uset) 30 return -1; 31 if (uset->table.n != 1) 32 return 0; 33 34 set = isl_set_from_union_set(isl_union_set_copy(uset)); 35 params = isl_set_is_params(set); 36 isl_set_free(set); 37 return params; 38} 39 40static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim, 41 int size) 42{ 43 isl_union_map *umap; 44 45 dim = isl_space_params(dim); 46 if (!dim) 47 return NULL; 48 49 umap = isl_calloc_type(dim->ctx, isl_union_map); 50 if (!umap) 51 return NULL; 52 53 umap->ref = 1; 54 umap->dim = dim; 55 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0) 56 return isl_union_map_free(umap); 57 58 return umap; 59} 60 61__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim) 62{ 63 return isl_union_map_alloc(dim, 16); 64} 65 66__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim) 67{ 68 return isl_union_map_empty(dim); 69} 70 71isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap) 72{ 73 return umap ? umap->dim->ctx : NULL; 74} 75 76isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset) 77{ 78 return uset ? uset->dim->ctx : NULL; 79} 80 81__isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap) 82{ 83 if (!umap) 84 return NULL; 85 return isl_space_copy(umap->dim); 86} 87 88__isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset) 89{ 90 return isl_union_map_get_space(uset); 91} 92 93static int free_umap_entry(void **entry, void *user) 94{ 95 isl_map *map = *entry; 96 isl_map_free(map); 97 return 0; 98} 99 100static int add_map(__isl_take isl_map *map, void *user) 101{ 102 isl_union_map **umap = (isl_union_map **)user; 103 104 *umap = isl_union_map_add_map(*umap, map); 105 106 return 0; 107} 108 109__isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap) 110{ 111 isl_union_map *dup; 112 113 if (!umap) 114 return NULL; 115 116 dup = isl_union_map_empty(isl_space_copy(umap->dim)); 117 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0) 118 goto error; 119 return dup; 120error: 121 isl_union_map_free(dup); 122 return NULL; 123} 124 125__isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap) 126{ 127 if (!umap) 128 return NULL; 129 130 if (umap->ref == 1) 131 return umap; 132 umap->ref--; 133 return isl_union_map_dup(umap); 134} 135 136struct isl_union_align { 137 isl_reordering *exp; 138 isl_union_map *res; 139}; 140 141static int align_entry(void **entry, void *user) 142{ 143 isl_map *map = *entry; 144 isl_reordering *exp; 145 struct isl_union_align *data = user; 146 147 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp), 148 isl_map_get_space(map)); 149 150 data->res = isl_union_map_add_map(data->res, 151 isl_map_realign(isl_map_copy(map), exp)); 152 153 return 0; 154} 155 156/* Align the parameters of umap along those of model. 157 * The result has the parameters of model first, in the same order 158 * as they appear in model, followed by any remaining parameters of 159 * umap that do not appear in model. 160 */ 161__isl_give isl_union_map *isl_union_map_align_params( 162 __isl_take isl_union_map *umap, __isl_take isl_space *model) 163{ 164 struct isl_union_align data = { NULL, NULL }; 165 166 if (!umap || !model) 167 goto error; 168 169 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) { 170 isl_space_free(model); 171 return umap; 172 } 173 174 model = isl_space_params(model); 175 data.exp = isl_parameter_alignment_reordering(umap->dim, model); 176 if (!data.exp) 177 goto error; 178 179 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim), 180 umap->table.n); 181 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, 182 &align_entry, &data) < 0) 183 goto error; 184 185 isl_reordering_free(data.exp); 186 isl_union_map_free(umap); 187 isl_space_free(model); 188 return data.res; 189error: 190 isl_reordering_free(data.exp); 191 isl_union_map_free(umap); 192 isl_union_map_free(data.res); 193 isl_space_free(model); 194 return NULL; 195} 196 197__isl_give isl_union_set *isl_union_set_align_params( 198 __isl_take isl_union_set *uset, __isl_take isl_space *model) 199{ 200 return isl_union_map_align_params(uset, model); 201} 202 203__isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1, 204 __isl_take isl_union_map *umap2) 205{ 206 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); 207 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); 208 209 umap1 = isl_union_map_cow(umap1); 210 211 if (!umap1 || !umap2) 212 goto error; 213 214 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0) 215 goto error; 216 217 isl_union_map_free(umap2); 218 219 return umap1; 220error: 221 isl_union_map_free(umap1); 222 isl_union_map_free(umap2); 223 return NULL; 224} 225 226__isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1, 227 __isl_take isl_union_set *uset2) 228{ 229 return isl_union_map_union(uset1, uset2); 230} 231 232__isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap) 233{ 234 if (!umap) 235 return NULL; 236 237 umap->ref++; 238 return umap; 239} 240 241__isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset) 242{ 243 return isl_union_map_copy(uset); 244} 245 246void *isl_union_map_free(__isl_take isl_union_map *umap) 247{ 248 if (!umap) 249 return NULL; 250 251 if (--umap->ref > 0) 252 return NULL; 253 254 isl_hash_table_foreach(umap->dim->ctx, &umap->table, 255 &free_umap_entry, NULL); 256 isl_hash_table_clear(&umap->table); 257 isl_space_free(umap->dim); 258 free(umap); 259 return NULL; 260} 261 262void *isl_union_set_free(__isl_take isl_union_set *uset) 263{ 264 return isl_union_map_free(uset); 265} 266 267static int has_dim(const void *entry, const void *val) 268{ 269 isl_map *map = (isl_map *)entry; 270 isl_space *dim = (isl_space *)val; 271 272 return isl_space_is_equal(map->dim, dim); 273} 274 275__isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap, 276 __isl_take isl_map *map) 277{ 278 uint32_t hash; 279 struct isl_hash_table_entry *entry; 280 281 if (!map || !umap) 282 goto error; 283 284 if (isl_map_plain_is_empty(map)) { 285 isl_map_free(map); 286 return umap; 287 } 288 289 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) { 290 umap = isl_union_map_align_params(umap, isl_map_get_space(map)); 291 map = isl_map_align_params(map, isl_union_map_get_space(umap)); 292 } 293 294 umap = isl_union_map_cow(umap); 295 296 if (!map || !umap) 297 goto error; 298 299 hash = isl_space_get_hash(map->dim); 300 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash, 301 &has_dim, map->dim, 1); 302 if (!entry) 303 goto error; 304 305 if (!entry->data) 306 entry->data = map; 307 else { 308 entry->data = isl_map_union(entry->data, isl_map_copy(map)); 309 if (!entry->data) 310 goto error; 311 isl_map_free(map); 312 } 313 314 return umap; 315error: 316 isl_map_free(map); 317 isl_union_map_free(umap); 318 return NULL; 319} 320 321__isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset, 322 __isl_take isl_set *set) 323{ 324 return isl_union_map_add_map(uset, (isl_map *)set); 325} 326 327__isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map) 328{ 329 isl_space *dim; 330 isl_union_map *umap; 331 332 if (!map) 333 return NULL; 334 335 dim = isl_map_get_space(map); 336 dim = isl_space_params(dim); 337 umap = isl_union_map_empty(dim); 338 umap = isl_union_map_add_map(umap, map); 339 340 return umap; 341} 342 343__isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set) 344{ 345 return isl_union_map_from_map((isl_map *)set); 346} 347 348__isl_give isl_union_map *isl_union_map_from_basic_map( 349 __isl_take isl_basic_map *bmap) 350{ 351 return isl_union_map_from_map(isl_map_from_basic_map(bmap)); 352} 353 354__isl_give isl_union_set *isl_union_set_from_basic_set( 355 __isl_take isl_basic_set *bset) 356{ 357 return isl_union_map_from_basic_map(bset); 358} 359 360struct isl_union_map_foreach_data 361{ 362 int (*fn)(__isl_take isl_map *map, void *user); 363 void *user; 364}; 365 366static int call_on_copy(void **entry, void *user) 367{ 368 isl_map *map = *entry; 369 struct isl_union_map_foreach_data *data; 370 data = (struct isl_union_map_foreach_data *)user; 371 372 return data->fn(isl_map_copy(map), data->user); 373} 374 375int isl_union_map_n_map(__isl_keep isl_union_map *umap) 376{ 377 return umap ? umap->table.n : 0; 378} 379 380int isl_union_set_n_set(__isl_keep isl_union_set *uset) 381{ 382 return uset ? uset->table.n : 0; 383} 384 385int isl_union_map_foreach_map(__isl_keep isl_union_map *umap, 386 int (*fn)(__isl_take isl_map *map, void *user), void *user) 387{ 388 struct isl_union_map_foreach_data data = { fn, user }; 389 390 if (!umap) 391 return -1; 392 393 return isl_hash_table_foreach(umap->dim->ctx, &umap->table, 394 &call_on_copy, &data); 395} 396 397static int copy_map(void **entry, void *user) 398{ 399 isl_map *map = *entry; 400 isl_map **map_p = user; 401 402 *map_p = isl_map_copy(map); 403 404 return -1; 405} 406 407__isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap) 408{ 409 isl_ctx *ctx; 410 isl_map *map = NULL; 411 412 if (!umap) 413 return NULL; 414 ctx = isl_union_map_get_ctx(umap); 415 if (umap->table.n != 1) 416 isl_die(ctx, isl_error_invalid, 417 "union map needs to contain elements in exactly " 418 "one space", return isl_union_map_free(umap)); 419 420 isl_hash_table_foreach(ctx, &umap->table, ©_map, &map); 421 422 isl_union_map_free(umap); 423 424 return map; 425} 426 427__isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset) 428{ 429 return isl_map_from_union_map(uset); 430} 431 432/* Extract the map in "umap" that lives in the given space (ignoring 433 * parameters). 434 */ 435__isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap, 436 __isl_take isl_space *space) 437{ 438 uint32_t hash; 439 struct isl_hash_table_entry *entry; 440 441 space = isl_space_drop_dims(space, isl_dim_param, 442 0, isl_space_dim(space, isl_dim_param)); 443 space = isl_space_align_params(space, isl_union_map_get_space(umap)); 444 if (!umap || !space) 445 goto error; 446 447 hash = isl_space_get_hash(space); 448 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash, 449 &has_dim, space, 0); 450 if (!entry) 451 return isl_map_empty(space); 452 isl_space_free(space); 453 return isl_map_copy(entry->data); 454error: 455 isl_space_free(space); 456 return NULL; 457} 458 459__isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset, 460 __isl_take isl_space *dim) 461{ 462 return (isl_set *)isl_union_map_extract_map(uset, dim); 463} 464 465/* Check if umap contains a map in the given space. 466 */ 467__isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap, 468 __isl_keep isl_space *dim) 469{ 470 uint32_t hash; 471 struct isl_hash_table_entry *entry; 472 473 if (!umap || !dim) 474 return -1; 475 476 hash = isl_space_get_hash(dim); 477 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash, 478 &has_dim, dim, 0); 479 return !!entry; 480} 481 482__isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset, 483 __isl_keep isl_space *dim) 484{ 485 return isl_union_map_contains(uset, dim); 486} 487 488int isl_union_set_foreach_set(__isl_keep isl_union_set *uset, 489 int (*fn)(__isl_take isl_set *set, void *user), void *user) 490{ 491 return isl_union_map_foreach_map(uset, 492 (int(*)(__isl_take isl_map *, void*))fn, user); 493} 494 495struct isl_union_set_foreach_point_data { 496 int (*fn)(__isl_take isl_point *pnt, void *user); 497 void *user; 498}; 499 500static int foreach_point(__isl_take isl_set *set, void *user) 501{ 502 struct isl_union_set_foreach_point_data *data = user; 503 int r; 504 505 r = isl_set_foreach_point(set, data->fn, data->user); 506 isl_set_free(set); 507 508 return r; 509} 510 511int isl_union_set_foreach_point(__isl_keep isl_union_set *uset, 512 int (*fn)(__isl_take isl_point *pnt, void *user), void *user) 513{ 514 struct isl_union_set_foreach_point_data data = { fn, user }; 515 return isl_union_set_foreach_set(uset, &foreach_point, &data); 516} 517 518struct isl_union_map_gen_bin_data { 519 isl_union_map *umap2; 520 isl_union_map *res; 521}; 522 523static int subtract_entry(void **entry, void *user) 524{ 525 struct isl_union_map_gen_bin_data *data = user; 526 uint32_t hash; 527 struct isl_hash_table_entry *entry2; 528 isl_map *map = *entry; 529 530 hash = isl_space_get_hash(map->dim); 531 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 532 hash, &has_dim, map->dim, 0); 533 map = isl_map_copy(map); 534 if (entry2) { 535 int empty; 536 map = isl_map_subtract(map, isl_map_copy(entry2->data)); 537 538 empty = isl_map_is_empty(map); 539 if (empty < 0) { 540 isl_map_free(map); 541 return -1; 542 } 543 if (empty) { 544 isl_map_free(map); 545 return 0; 546 } 547 } 548 data->res = isl_union_map_add_map(data->res, map); 549 550 return 0; 551} 552 553static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1, 554 __isl_take isl_union_map *umap2, int (*fn)(void **, void *)) 555{ 556 struct isl_union_map_gen_bin_data data = { NULL, NULL }; 557 558 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); 559 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); 560 561 if (!umap1 || !umap2) 562 goto error; 563 564 data.umap2 = umap2; 565 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim), 566 umap1->table.n); 567 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, 568 fn, &data) < 0) 569 goto error; 570 571 isl_union_map_free(umap1); 572 isl_union_map_free(umap2); 573 return data.res; 574error: 575 isl_union_map_free(umap1); 576 isl_union_map_free(umap2); 577 isl_union_map_free(data.res); 578 return NULL; 579} 580 581__isl_give isl_union_map *isl_union_map_subtract( 582 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 583{ 584 return gen_bin_op(umap1, umap2, &subtract_entry); 585} 586 587__isl_give isl_union_set *isl_union_set_subtract( 588 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2) 589{ 590 return isl_union_map_subtract(uset1, uset2); 591} 592 593struct isl_union_map_gen_bin_set_data { 594 isl_set *set; 595 isl_union_map *res; 596}; 597 598static int intersect_params_entry(void **entry, void *user) 599{ 600 struct isl_union_map_gen_bin_set_data *data = user; 601 isl_map *map = *entry; 602 int empty; 603 604 map = isl_map_copy(map); 605 map = isl_map_intersect_params(map, isl_set_copy(data->set)); 606 607 empty = isl_map_is_empty(map); 608 if (empty < 0) { 609 isl_map_free(map); 610 return -1; 611 } 612 613 data->res = isl_union_map_add_map(data->res, map); 614 615 return 0; 616} 617 618static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap, 619 __isl_take isl_set *set, int (*fn)(void **, void *)) 620{ 621 struct isl_union_map_gen_bin_set_data data = { NULL, NULL }; 622 623 umap = isl_union_map_align_params(umap, isl_set_get_space(set)); 624 set = isl_set_align_params(set, isl_union_map_get_space(umap)); 625 626 if (!umap || !set) 627 goto error; 628 629 data.set = set; 630 data.res = isl_union_map_alloc(isl_space_copy(umap->dim), 631 umap->table.n); 632 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, 633 fn, &data) < 0) 634 goto error; 635 636 isl_union_map_free(umap); 637 isl_set_free(set); 638 return data.res; 639error: 640 isl_union_map_free(umap); 641 isl_set_free(set); 642 isl_union_map_free(data.res); 643 return NULL; 644} 645 646__isl_give isl_union_map *isl_union_map_intersect_params( 647 __isl_take isl_union_map *umap, __isl_take isl_set *set) 648{ 649 return gen_bin_set_op(umap, set, &intersect_params_entry); 650} 651 652__isl_give isl_union_set *isl_union_set_intersect_params( 653 __isl_take isl_union_set *uset, __isl_take isl_set *set) 654{ 655 return isl_union_map_intersect_params(uset, set); 656} 657 658static __isl_give isl_union_map *union_map_intersect_params( 659 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset) 660{ 661 return isl_union_map_intersect_params(umap, 662 isl_set_from_union_set(uset)); 663} 664 665static __isl_give isl_union_map *union_map_gist_params( 666 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset) 667{ 668 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset)); 669} 670 671struct isl_union_map_match_bin_data { 672 isl_union_map *umap2; 673 isl_union_map *res; 674 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*); 675}; 676 677static int match_bin_entry(void **entry, void *user) 678{ 679 struct isl_union_map_match_bin_data *data = user; 680 uint32_t hash; 681 struct isl_hash_table_entry *entry2; 682 isl_map *map = *entry; 683 int empty; 684 685 hash = isl_space_get_hash(map->dim); 686 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 687 hash, &has_dim, map->dim, 0); 688 if (!entry2) 689 return 0; 690 691 map = isl_map_copy(map); 692 map = data->fn(map, isl_map_copy(entry2->data)); 693 694 empty = isl_map_is_empty(map); 695 if (empty < 0) { 696 isl_map_free(map); 697 return -1; 698 } 699 if (empty) { 700 isl_map_free(map); 701 return 0; 702 } 703 704 data->res = isl_union_map_add_map(data->res, map); 705 706 return 0; 707} 708 709static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1, 710 __isl_take isl_union_map *umap2, 711 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*)) 712{ 713 struct isl_union_map_match_bin_data data = { NULL, NULL, fn }; 714 715 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); 716 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); 717 718 if (!umap1 || !umap2) 719 goto error; 720 721 data.umap2 = umap2; 722 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim), 723 umap1->table.n); 724 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, 725 &match_bin_entry, &data) < 0) 726 goto error; 727 728 isl_union_map_free(umap1); 729 isl_union_map_free(umap2); 730 return data.res; 731error: 732 isl_union_map_free(umap1); 733 isl_union_map_free(umap2); 734 isl_union_map_free(data.res); 735 return NULL; 736} 737 738__isl_give isl_union_map *isl_union_map_intersect( 739 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 740{ 741 return match_bin_op(umap1, umap2, &isl_map_intersect); 742} 743 744/* Compute the intersection of the two union_sets. 745 * As a special case, if exactly one of the two union_sets 746 * is a parameter domain, then intersect the parameter domain 747 * of the other one with this set. 748 */ 749__isl_give isl_union_set *isl_union_set_intersect( 750 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2) 751{ 752 int p1, p2; 753 754 p1 = isl_union_set_is_params(uset1); 755 p2 = isl_union_set_is_params(uset2); 756 if (p1 < 0 || p2 < 0) 757 goto error; 758 if (!p1 && p2) 759 return union_map_intersect_params(uset1, uset2); 760 if (p1 && !p2) 761 return union_map_intersect_params(uset2, uset1); 762 return isl_union_map_intersect(uset1, uset2); 763error: 764 isl_union_set_free(uset1); 765 isl_union_set_free(uset2); 766 return NULL; 767} 768 769static int gist_params_entry(void **entry, void *user) 770{ 771 struct isl_union_map_gen_bin_set_data *data = user; 772 isl_map *map = *entry; 773 int empty; 774 775 map = isl_map_copy(map); 776 map = isl_map_gist_params(map, isl_set_copy(data->set)); 777 778 empty = isl_map_is_empty(map); 779 if (empty < 0) { 780 isl_map_free(map); 781 return -1; 782 } 783 784 data->res = isl_union_map_add_map(data->res, map); 785 786 return 0; 787} 788 789__isl_give isl_union_map *isl_union_map_gist_params( 790 __isl_take isl_union_map *umap, __isl_take isl_set *set) 791{ 792 return gen_bin_set_op(umap, set, &gist_params_entry); 793} 794 795__isl_give isl_union_set *isl_union_set_gist_params( 796 __isl_take isl_union_set *uset, __isl_take isl_set *set) 797{ 798 return isl_union_map_gist_params(uset, set); 799} 800 801__isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap, 802 __isl_take isl_union_map *context) 803{ 804 return match_bin_op(umap, context, &isl_map_gist); 805} 806 807__isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset, 808 __isl_take isl_union_set *context) 809{ 810 if (isl_union_set_is_params(context)) 811 return union_map_gist_params(uset, context); 812 return isl_union_map_gist(uset, context); 813} 814 815static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1, 816 __isl_take isl_map *set2) 817{ 818 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2); 819} 820 821static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1, 822 __isl_take isl_map *set2) 823{ 824 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2); 825} 826 827__isl_give isl_union_map *isl_union_set_lex_lt_union_set( 828 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2) 829{ 830 return match_bin_op(uset1, uset2, &lex_lt_set); 831} 832 833__isl_give isl_union_map *isl_union_set_lex_le_union_set( 834 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2) 835{ 836 return match_bin_op(uset1, uset2, &lex_le_set); 837} 838 839__isl_give isl_union_map *isl_union_set_lex_gt_union_set( 840 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2) 841{ 842 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1)); 843} 844 845__isl_give isl_union_map *isl_union_set_lex_ge_union_set( 846 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2) 847{ 848 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1)); 849} 850 851__isl_give isl_union_map *isl_union_map_lex_gt_union_map( 852 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 853{ 854 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1)); 855} 856 857__isl_give isl_union_map *isl_union_map_lex_ge_union_map( 858 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 859{ 860 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1)); 861} 862 863static int intersect_domain_entry(void **entry, void *user) 864{ 865 struct isl_union_map_gen_bin_data *data = user; 866 uint32_t hash; 867 struct isl_hash_table_entry *entry2; 868 isl_space *dim; 869 isl_map *map = *entry; 870 int empty; 871 872 dim = isl_map_get_space(map); 873 dim = isl_space_domain(dim); 874 hash = isl_space_get_hash(dim); 875 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 876 hash, &has_dim, dim, 0); 877 isl_space_free(dim); 878 if (!entry2) 879 return 0; 880 881 map = isl_map_copy(map); 882 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data)); 883 884 empty = isl_map_is_empty(map); 885 if (empty < 0) { 886 isl_map_free(map); 887 return -1; 888 } 889 if (empty) { 890 isl_map_free(map); 891 return 0; 892 } 893 894 data->res = isl_union_map_add_map(data->res, map); 895 896 return 0; 897} 898 899/* Intersect the domain of "umap" with "uset". 900 * If "uset" is a parameters domain, then intersect the parameter 901 * domain of "umap" with this set. 902 */ 903__isl_give isl_union_map *isl_union_map_intersect_domain( 904 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset) 905{ 906 if (isl_union_set_is_params(uset)) 907 return union_map_intersect_params(umap, uset); 908 return gen_bin_op(umap, uset, &intersect_domain_entry); 909} 910 911/* Remove the elements of data->umap2 from the domain of *entry 912 * and add the result to data->res. 913 */ 914static int subtract_domain_entry(void **entry, void *user) 915{ 916 struct isl_union_map_gen_bin_data *data = user; 917 uint32_t hash; 918 struct isl_hash_table_entry *entry2; 919 isl_space *dim; 920 isl_map *map = *entry; 921 int empty; 922 923 dim = isl_map_get_space(map); 924 dim = isl_space_domain(dim); 925 hash = isl_space_get_hash(dim); 926 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 927 hash, &has_dim, dim, 0); 928 isl_space_free(dim); 929 930 map = isl_map_copy(map); 931 932 if (!entry2) { 933 data->res = isl_union_map_add_map(data->res, map); 934 return 0; 935 } 936 937 map = isl_map_subtract_domain(map, isl_set_copy(entry2->data)); 938 939 empty = isl_map_is_empty(map); 940 if (empty < 0) { 941 isl_map_free(map); 942 return -1; 943 } 944 if (empty) { 945 isl_map_free(map); 946 return 0; 947 } 948 949 data->res = isl_union_map_add_map(data->res, map); 950 951 return 0; 952} 953 954/* Remove the elements of "uset" from the domain of "umap". 955 */ 956__isl_give isl_union_map *isl_union_map_subtract_domain( 957 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom) 958{ 959 return gen_bin_op(umap, dom, &subtract_domain_entry); 960} 961 962/* Remove the elements of data->umap2 from the range of *entry 963 * and add the result to data->res. 964 */ 965static int subtract_range_entry(void **entry, void *user) 966{ 967 struct isl_union_map_gen_bin_data *data = user; 968 uint32_t hash; 969 struct isl_hash_table_entry *entry2; 970 isl_space *space; 971 isl_map *map = *entry; 972 int empty; 973 974 space = isl_map_get_space(map); 975 space = isl_space_range(space); 976 hash = isl_space_get_hash(space); 977 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 978 hash, &has_dim, space, 0); 979 isl_space_free(space); 980 981 map = isl_map_copy(map); 982 983 if (!entry2) { 984 data->res = isl_union_map_add_map(data->res, map); 985 return 0; 986 } 987 988 map = isl_map_subtract_range(map, isl_set_copy(entry2->data)); 989 990 empty = isl_map_is_empty(map); 991 if (empty < 0) { 992 isl_map_free(map); 993 return -1; 994 } 995 if (empty) { 996 isl_map_free(map); 997 return 0; 998 } 999 1000 data->res = isl_union_map_add_map(data->res, map); 1001 1002 return 0; 1003} 1004 1005/* Remove the elements of "uset" from the range of "umap". 1006 */ 1007__isl_give isl_union_map *isl_union_map_subtract_range( 1008 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom) 1009{ 1010 return gen_bin_op(umap, dom, &subtract_range_entry); 1011} 1012 1013static int gist_domain_entry(void **entry, void *user) 1014{ 1015 struct isl_union_map_gen_bin_data *data = user; 1016 uint32_t hash; 1017 struct isl_hash_table_entry *entry2; 1018 isl_space *dim; 1019 isl_map *map = *entry; 1020 int empty; 1021 1022 dim = isl_map_get_space(map); 1023 dim = isl_space_domain(dim); 1024 hash = isl_space_get_hash(dim); 1025 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 1026 hash, &has_dim, dim, 0); 1027 isl_space_free(dim); 1028 if (!entry2) 1029 return 0; 1030 1031 map = isl_map_copy(map); 1032 map = isl_map_gist_domain(map, isl_set_copy(entry2->data)); 1033 1034 empty = isl_map_is_empty(map); 1035 if (empty < 0) { 1036 isl_map_free(map); 1037 return -1; 1038 } 1039 1040 data->res = isl_union_map_add_map(data->res, map); 1041 1042 return 0; 1043} 1044 1045/* Compute the gist of "umap" with respect to the domain "uset". 1046 * If "uset" is a parameters domain, then compute the gist 1047 * with respect to this parameter domain. 1048 */ 1049__isl_give isl_union_map *isl_union_map_gist_domain( 1050 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset) 1051{ 1052 if (isl_union_set_is_params(uset)) 1053 return union_map_gist_params(umap, uset); 1054 return gen_bin_op(umap, uset, &gist_domain_entry); 1055} 1056 1057static int gist_range_entry(void **entry, void *user) 1058{ 1059 struct isl_union_map_gen_bin_data *data = user; 1060 uint32_t hash; 1061 struct isl_hash_table_entry *entry2; 1062 isl_space *space; 1063 isl_map *map = *entry; 1064 int empty; 1065 1066 space = isl_map_get_space(map); 1067 space = isl_space_range(space); 1068 hash = isl_space_get_hash(space); 1069 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 1070 hash, &has_dim, space, 0); 1071 isl_space_free(space); 1072 if (!entry2) 1073 return 0; 1074 1075 map = isl_map_copy(map); 1076 map = isl_map_gist_range(map, isl_set_copy(entry2->data)); 1077 1078 empty = isl_map_is_empty(map); 1079 if (empty < 0) { 1080 isl_map_free(map); 1081 return -1; 1082 } 1083 1084 data->res = isl_union_map_add_map(data->res, map); 1085 1086 return 0; 1087} 1088 1089/* Compute the gist of "umap" with respect to the range "uset". 1090 */ 1091__isl_give isl_union_map *isl_union_map_gist_range( 1092 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset) 1093{ 1094 return gen_bin_op(umap, uset, &gist_range_entry); 1095} 1096 1097static int intersect_range_entry(void **entry, void *user) 1098{ 1099 struct isl_union_map_gen_bin_data *data = user; 1100 uint32_t hash; 1101 struct isl_hash_table_entry *entry2; 1102 isl_space *dim; 1103 isl_map *map = *entry; 1104 int empty; 1105 1106 dim = isl_map_get_space(map); 1107 dim = isl_space_range(dim); 1108 hash = isl_space_get_hash(dim); 1109 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 1110 hash, &has_dim, dim, 0); 1111 isl_space_free(dim); 1112 if (!entry2) 1113 return 0; 1114 1115 map = isl_map_copy(map); 1116 map = isl_map_intersect_range(map, isl_set_copy(entry2->data)); 1117 1118 empty = isl_map_is_empty(map); 1119 if (empty < 0) { 1120 isl_map_free(map); 1121 return -1; 1122 } 1123 if (empty) { 1124 isl_map_free(map); 1125 return 0; 1126 } 1127 1128 data->res = isl_union_map_add_map(data->res, map); 1129 1130 return 0; 1131} 1132 1133__isl_give isl_union_map *isl_union_map_intersect_range( 1134 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset) 1135{ 1136 return gen_bin_op(umap, uset, &intersect_range_entry); 1137} 1138 1139struct isl_union_map_bin_data { 1140 isl_union_map *umap2; 1141 isl_union_map *res; 1142 isl_map *map; 1143 int (*fn)(void **entry, void *user); 1144}; 1145 1146static int apply_range_entry(void **entry, void *user) 1147{ 1148 struct isl_union_map_bin_data *data = user; 1149 isl_map *map2 = *entry; 1150 int empty; 1151 1152 if (!isl_space_tuple_match(data->map->dim, isl_dim_out, 1153 map2->dim, isl_dim_in)) 1154 return 0; 1155 1156 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2)); 1157 1158 empty = isl_map_is_empty(map2); 1159 if (empty < 0) { 1160 isl_map_free(map2); 1161 return -1; 1162 } 1163 if (empty) { 1164 isl_map_free(map2); 1165 return 0; 1166 } 1167 1168 data->res = isl_union_map_add_map(data->res, map2); 1169 1170 return 0; 1171} 1172 1173static int bin_entry(void **entry, void *user) 1174{ 1175 struct isl_union_map_bin_data *data = user; 1176 isl_map *map = *entry; 1177 1178 data->map = map; 1179 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table, 1180 data->fn, data) < 0) 1181 return -1; 1182 1183 return 0; 1184} 1185 1186static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1, 1187 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user)) 1188{ 1189 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn }; 1190 1191 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); 1192 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); 1193 1194 if (!umap1 || !umap2) 1195 goto error; 1196 1197 data.umap2 = umap2; 1198 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim), 1199 umap1->table.n); 1200 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, 1201 &bin_entry, &data) < 0) 1202 goto error; 1203 1204 isl_union_map_free(umap1); 1205 isl_union_map_free(umap2); 1206 return data.res; 1207error: 1208 isl_union_map_free(umap1); 1209 isl_union_map_free(umap2); 1210 isl_union_map_free(data.res); 1211 return NULL; 1212} 1213 1214__isl_give isl_union_map *isl_union_map_apply_range( 1215 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1216{ 1217 return bin_op(umap1, umap2, &apply_range_entry); 1218} 1219 1220__isl_give isl_union_map *isl_union_map_apply_domain( 1221 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1222{ 1223 umap1 = isl_union_map_reverse(umap1); 1224 umap1 = isl_union_map_apply_range(umap1, umap2); 1225 return isl_union_map_reverse(umap1); 1226} 1227 1228__isl_give isl_union_set *isl_union_set_apply( 1229 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap) 1230{ 1231 return isl_union_map_apply_range(uset, umap); 1232} 1233 1234static int map_lex_lt_entry(void **entry, void *user) 1235{ 1236 struct isl_union_map_bin_data *data = user; 1237 isl_map *map2 = *entry; 1238 1239 if (!isl_space_tuple_match(data->map->dim, isl_dim_out, 1240 map2->dim, isl_dim_out)) 1241 return 0; 1242 1243 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2)); 1244 1245 data->res = isl_union_map_add_map(data->res, map2); 1246 1247 return 0; 1248} 1249 1250__isl_give isl_union_map *isl_union_map_lex_lt_union_map( 1251 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1252{ 1253 return bin_op(umap1, umap2, &map_lex_lt_entry); 1254} 1255 1256static int map_lex_le_entry(void **entry, void *user) 1257{ 1258 struct isl_union_map_bin_data *data = user; 1259 isl_map *map2 = *entry; 1260 1261 if (!isl_space_tuple_match(data->map->dim, isl_dim_out, 1262 map2->dim, isl_dim_out)) 1263 return 0; 1264 1265 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2)); 1266 1267 data->res = isl_union_map_add_map(data->res, map2); 1268 1269 return 0; 1270} 1271 1272__isl_give isl_union_map *isl_union_map_lex_le_union_map( 1273 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1274{ 1275 return bin_op(umap1, umap2, &map_lex_le_entry); 1276} 1277 1278static int product_entry(void **entry, void *user) 1279{ 1280 struct isl_union_map_bin_data *data = user; 1281 isl_map *map2 = *entry; 1282 1283 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2)); 1284 1285 data->res = isl_union_map_add_map(data->res, map2); 1286 1287 return 0; 1288} 1289 1290__isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1, 1291 __isl_take isl_union_map *umap2) 1292{ 1293 return bin_op(umap1, umap2, &product_entry); 1294} 1295 1296static int set_product_entry(void **entry, void *user) 1297{ 1298 struct isl_union_map_bin_data *data = user; 1299 isl_set *set2 = *entry; 1300 1301 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2)); 1302 1303 data->res = isl_union_set_add_set(data->res, set2); 1304 1305 return 0; 1306} 1307 1308__isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1, 1309 __isl_take isl_union_set *uset2) 1310{ 1311 return bin_op(uset1, uset2, &set_product_entry); 1312} 1313 1314static int domain_product_entry(void **entry, void *user) 1315{ 1316 struct isl_union_map_bin_data *data = user; 1317 isl_map *map2 = *entry; 1318 1319 if (!isl_space_tuple_match(data->map->dim, isl_dim_out, 1320 map2->dim, isl_dim_out)) 1321 return 0; 1322 1323 map2 = isl_map_domain_product(isl_map_copy(data->map), 1324 isl_map_copy(map2)); 1325 1326 data->res = isl_union_map_add_map(data->res, map2); 1327 1328 return 0; 1329} 1330 1331/* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D) 1332 */ 1333__isl_give isl_union_map *isl_union_map_domain_product( 1334 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1335{ 1336 return bin_op(umap1, umap2, &domain_product_entry); 1337} 1338 1339static int range_product_entry(void **entry, void *user) 1340{ 1341 struct isl_union_map_bin_data *data = user; 1342 isl_map *map2 = *entry; 1343 1344 if (!isl_space_tuple_match(data->map->dim, isl_dim_in, 1345 map2->dim, isl_dim_in)) 1346 return 0; 1347 1348 map2 = isl_map_range_product(isl_map_copy(data->map), 1349 isl_map_copy(map2)); 1350 1351 data->res = isl_union_map_add_map(data->res, map2); 1352 1353 return 0; 1354} 1355 1356__isl_give isl_union_map *isl_union_map_range_product( 1357 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1358{ 1359 return bin_op(umap1, umap2, &range_product_entry); 1360} 1361 1362static int flat_range_product_entry(void **entry, void *user) 1363{ 1364 struct isl_union_map_bin_data *data = user; 1365 isl_map *map2 = *entry; 1366 1367 if (!isl_space_tuple_match(data->map->dim, isl_dim_in, 1368 map2->dim, isl_dim_in)) 1369 return 0; 1370 1371 map2 = isl_map_flat_range_product(isl_map_copy(data->map), 1372 isl_map_copy(map2)); 1373 1374 data->res = isl_union_map_add_map(data->res, map2); 1375 1376 return 0; 1377} 1378 1379__isl_give isl_union_map *isl_union_map_flat_range_product( 1380 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) 1381{ 1382 return bin_op(umap1, umap2, &flat_range_product_entry); 1383} 1384 1385static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap, 1386 int (*fn)(void **, void *)) 1387{ 1388 isl_union_set *res; 1389 1390 if (!umap) 1391 return NULL; 1392 1393 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n); 1394 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0) 1395 goto error; 1396 1397 isl_union_map_free(umap); 1398 return res; 1399error: 1400 isl_union_map_free(umap); 1401 isl_union_set_free(res); 1402 return NULL; 1403} 1404 1405static int from_range_entry(void **entry, void *user) 1406{ 1407 isl_map *set = *entry; 1408 isl_union_set **res = user; 1409 1410 *res = isl_union_map_add_map(*res, 1411 isl_map_from_range(isl_set_copy(set))); 1412 1413 return 0; 1414} 1415 1416__isl_give isl_union_map *isl_union_map_from_range( 1417 __isl_take isl_union_set *uset) 1418{ 1419 return cond_un_op(uset, &from_range_entry); 1420} 1421 1422__isl_give isl_union_map *isl_union_map_from_domain( 1423 __isl_take isl_union_set *uset) 1424{ 1425 return isl_union_map_reverse(isl_union_map_from_range(uset)); 1426} 1427 1428__isl_give isl_union_map *isl_union_map_from_domain_and_range( 1429 __isl_take isl_union_set *domain, __isl_take isl_union_set *range) 1430{ 1431 return isl_union_map_apply_range(isl_union_map_from_domain(domain), 1432 isl_union_map_from_range(range)); 1433} 1434 1435static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap, 1436 int (*fn)(void **, void *)) 1437{ 1438 umap = isl_union_map_cow(umap); 1439 if (!umap) 1440 return NULL; 1441 1442 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0) 1443 goto error; 1444 1445 return umap; 1446error: 1447 isl_union_map_free(umap); 1448 return NULL; 1449} 1450 1451static int affine_entry(void **entry, void *user) 1452{ 1453 isl_map **map = (isl_map **)entry; 1454 1455 *map = isl_map_from_basic_map(isl_map_affine_hull(*map)); 1456 1457 return *map ? 0 : -1; 1458} 1459 1460__isl_give isl_union_map *isl_union_map_affine_hull( 1461 __isl_take isl_union_map *umap) 1462{ 1463 return un_op(umap, &affine_entry); 1464} 1465 1466__isl_give isl_union_set *isl_union_set_affine_hull( 1467 __isl_take isl_union_set *uset) 1468{ 1469 return isl_union_map_affine_hull(uset); 1470} 1471 1472static int polyhedral_entry(void **entry, void *user) 1473{ 1474 isl_map **map = (isl_map **)entry; 1475 1476 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map)); 1477 1478 return *map ? 0 : -1; 1479} 1480 1481__isl_give isl_union_map *isl_union_map_polyhedral_hull( 1482 __isl_take isl_union_map *umap) 1483{ 1484 return un_op(umap, &polyhedral_entry); 1485} 1486 1487__isl_give isl_union_set *isl_union_set_polyhedral_hull( 1488 __isl_take isl_union_set *uset) 1489{ 1490 return isl_union_map_polyhedral_hull(uset); 1491} 1492 1493static int simple_entry(void **entry, void *user) 1494{ 1495 isl_map **map = (isl_map **)entry; 1496 1497 *map = isl_map_from_basic_map(isl_map_simple_hull(*map)); 1498 1499 return *map ? 0 : -1; 1500} 1501 1502__isl_give isl_union_map *isl_union_map_simple_hull( 1503 __isl_take isl_union_map *umap) 1504{ 1505 return un_op(umap, &simple_entry); 1506} 1507 1508__isl_give isl_union_set *isl_union_set_simple_hull( 1509 __isl_take isl_union_set *uset) 1510{ 1511 return isl_union_map_simple_hull(uset); 1512} 1513 1514static int inplace_entry(void **entry, void *user) 1515{ 1516 __isl_give isl_map *(*fn)(__isl_take isl_map *); 1517 isl_map **map = (isl_map **)entry; 1518 isl_map *copy; 1519 1520 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user; 1521 copy = fn(isl_map_copy(*map)); 1522 if (!copy) 1523 return -1; 1524 1525 isl_map_free(*map); 1526 *map = copy; 1527 1528 return 0; 1529} 1530 1531static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap, 1532 __isl_give isl_map *(*fn)(__isl_take isl_map *)) 1533{ 1534 if (!umap) 1535 return NULL; 1536 1537 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, 1538 &inplace_entry, &fn) < 0) 1539 goto error; 1540 1541 return umap; 1542error: 1543 isl_union_map_free(umap); 1544 return NULL; 1545} 1546 1547__isl_give isl_union_map *isl_union_map_coalesce( 1548 __isl_take isl_union_map *umap) 1549{ 1550 return inplace(umap, &isl_map_coalesce); 1551} 1552 1553__isl_give isl_union_set *isl_union_set_coalesce( 1554 __isl_take isl_union_set *uset) 1555{ 1556 return isl_union_map_coalesce(uset); 1557} 1558 1559__isl_give isl_union_map *isl_union_map_detect_equalities( 1560 __isl_take isl_union_map *umap) 1561{ 1562 return inplace(umap, &isl_map_detect_equalities); 1563} 1564 1565__isl_give isl_union_set *isl_union_set_detect_equalities( 1566 __isl_take isl_union_set *uset) 1567{ 1568 return isl_union_map_detect_equalities(uset); 1569} 1570 1571__isl_give isl_union_map *isl_union_map_compute_divs( 1572 __isl_take isl_union_map *umap) 1573{ 1574 return inplace(umap, &isl_map_compute_divs); 1575} 1576 1577__isl_give isl_union_set *isl_union_set_compute_divs( 1578 __isl_take isl_union_set *uset) 1579{ 1580 return isl_union_map_compute_divs(uset); 1581} 1582 1583static int lexmin_entry(void **entry, void *user) 1584{ 1585 isl_map **map = (isl_map **)entry; 1586 1587 *map = isl_map_lexmin(*map); 1588 1589 return *map ? 0 : -1; 1590} 1591 1592__isl_give isl_union_map *isl_union_map_lexmin( 1593 __isl_take isl_union_map *umap) 1594{ 1595 return un_op(umap, &lexmin_entry); 1596} 1597 1598__isl_give isl_union_set *isl_union_set_lexmin( 1599 __isl_take isl_union_set *uset) 1600{ 1601 return isl_union_map_lexmin(uset); 1602} 1603 1604static int lexmax_entry(void **entry, void *user) 1605{ 1606 isl_map **map = (isl_map **)entry; 1607 1608 *map = isl_map_lexmax(*map); 1609 1610 return *map ? 0 : -1; 1611} 1612 1613__isl_give isl_union_map *isl_union_map_lexmax( 1614 __isl_take isl_union_map *umap) 1615{ 1616 return un_op(umap, &lexmax_entry); 1617} 1618 1619__isl_give isl_union_set *isl_union_set_lexmax( 1620 __isl_take isl_union_set *uset) 1621{ 1622 return isl_union_map_lexmax(uset); 1623} 1624 1625static int universe_entry(void **entry, void *user) 1626{ 1627 isl_map *map = *entry; 1628 isl_union_map **res = user; 1629 1630 map = isl_map_universe(isl_map_get_space(map)); 1631 *res = isl_union_map_add_map(*res, map); 1632 1633 return 0; 1634} 1635 1636__isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap) 1637{ 1638 return cond_un_op(umap, &universe_entry); 1639} 1640 1641__isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset) 1642{ 1643 return isl_union_map_universe(uset); 1644} 1645 1646static int reverse_entry(void **entry, void *user) 1647{ 1648 isl_map *map = *entry; 1649 isl_union_map **res = user; 1650 1651 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map))); 1652 1653 return 0; 1654} 1655 1656__isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap) 1657{ 1658 return cond_un_op(umap, &reverse_entry); 1659} 1660 1661static int params_entry(void **entry, void *user) 1662{ 1663 isl_map *map = *entry; 1664 isl_union_set **res = user; 1665 1666 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map))); 1667 1668 return 0; 1669} 1670 1671/* Compute the parameter domain of the given union map. 1672 */ 1673__isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap) 1674{ 1675 int empty; 1676 1677 empty = isl_union_map_is_empty(umap); 1678 if (empty < 0) 1679 return isl_union_map_free(umap); 1680 if (empty) { 1681 isl_space *space; 1682 space = isl_union_map_get_space(umap); 1683 isl_union_map_free(umap); 1684 return isl_set_empty(space); 1685 } 1686 return isl_set_from_union_set(cond_un_op(umap, ¶ms_entry)); 1687} 1688 1689/* Compute the parameter domain of the given union set. 1690 */ 1691__isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset) 1692{ 1693 return isl_union_map_params(uset); 1694} 1695 1696static int domain_entry(void **entry, void *user) 1697{ 1698 isl_map *map = *entry; 1699 isl_union_set **res = user; 1700 1701 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map))); 1702 1703 return 0; 1704} 1705 1706__isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap) 1707{ 1708 return cond_un_op(umap, &domain_entry); 1709} 1710 1711static int range_entry(void **entry, void *user) 1712{ 1713 isl_map *map = *entry; 1714 isl_union_set **res = user; 1715 1716 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map))); 1717 1718 return 0; 1719} 1720 1721__isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap) 1722{ 1723 return cond_un_op(umap, &range_entry); 1724} 1725 1726static int domain_map_entry(void **entry, void *user) 1727{ 1728 isl_map *map = *entry; 1729 isl_union_set **res = user; 1730 1731 *res = isl_union_map_add_map(*res, 1732 isl_map_domain_map(isl_map_copy(map))); 1733 1734 return 0; 1735} 1736 1737__isl_give isl_union_map *isl_union_map_domain_map( 1738 __isl_take isl_union_map *umap) 1739{ 1740 return cond_un_op(umap, &domain_map_entry); 1741} 1742 1743static int range_map_entry(void **entry, void *user) 1744{ 1745 isl_map *map = *entry; 1746 isl_union_set **res = user; 1747 1748 *res = isl_union_map_add_map(*res, 1749 isl_map_range_map(isl_map_copy(map))); 1750 1751 return 0; 1752} 1753 1754__isl_give isl_union_map *isl_union_map_range_map( 1755 __isl_take isl_union_map *umap) 1756{ 1757 return cond_un_op(umap, &range_map_entry); 1758} 1759 1760static int deltas_entry(void **entry, void *user) 1761{ 1762 isl_map *map = *entry; 1763 isl_union_set **res = user; 1764 1765 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out)) 1766 return 0; 1767 1768 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map))); 1769 1770 return 0; 1771} 1772 1773__isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap) 1774{ 1775 return cond_un_op(umap, &deltas_entry); 1776} 1777 1778static int deltas_map_entry(void **entry, void *user) 1779{ 1780 isl_map *map = *entry; 1781 isl_union_map **res = user; 1782 1783 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out)) 1784 return 0; 1785 1786 *res = isl_union_map_add_map(*res, 1787 isl_map_deltas_map(isl_map_copy(map))); 1788 1789 return 0; 1790} 1791 1792__isl_give isl_union_map *isl_union_map_deltas_map( 1793 __isl_take isl_union_map *umap) 1794{ 1795 return cond_un_op(umap, &deltas_map_entry); 1796} 1797 1798static int identity_entry(void **entry, void *user) 1799{ 1800 isl_set *set = *entry; 1801 isl_union_map **res = user; 1802 1803 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set))); 1804 1805 return 0; 1806} 1807 1808__isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset) 1809{ 1810 return cond_un_op(uset, &identity_entry); 1811} 1812 1813static int unwrap_entry(void **entry, void *user) 1814{ 1815 isl_set *set = *entry; 1816 isl_union_set **res = user; 1817 1818 if (!isl_set_is_wrapping(set)) 1819 return 0; 1820 1821 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set))); 1822 1823 return 0; 1824} 1825 1826__isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset) 1827{ 1828 return cond_un_op(uset, &unwrap_entry); 1829} 1830 1831static int wrap_entry(void **entry, void *user) 1832{ 1833 isl_map *map = *entry; 1834 isl_union_set **res = user; 1835 1836 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map))); 1837 1838 return 0; 1839} 1840 1841__isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap) 1842{ 1843 return cond_un_op(umap, &wrap_entry); 1844} 1845 1846struct isl_union_map_is_subset_data { 1847 isl_union_map *umap2; 1848 int is_subset; 1849}; 1850 1851static int is_subset_entry(void **entry, void *user) 1852{ 1853 struct isl_union_map_is_subset_data *data = user; 1854 uint32_t hash; 1855 struct isl_hash_table_entry *entry2; 1856 isl_map *map = *entry; 1857 1858 hash = isl_space_get_hash(map->dim); 1859 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, 1860 hash, &has_dim, map->dim, 0); 1861 if (!entry2) { 1862 int empty = isl_map_is_empty(map); 1863 if (empty < 0) 1864 return -1; 1865 if (empty) 1866 return 0; 1867 data->is_subset = 0; 1868 return -1; 1869 } 1870 1871 data->is_subset = isl_map_is_subset(map, entry2->data); 1872 if (data->is_subset < 0 || !data->is_subset) 1873 return -1; 1874 1875 return 0; 1876} 1877 1878int isl_union_map_is_subset(__isl_keep isl_union_map *umap1, 1879 __isl_keep isl_union_map *umap2) 1880{ 1881 struct isl_union_map_is_subset_data data = { NULL, 1 }; 1882 1883 umap1 = isl_union_map_copy(umap1); 1884 umap2 = isl_union_map_copy(umap2); 1885 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); 1886 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); 1887 1888 if (!umap1 || !umap2) 1889 goto error; 1890 1891 data.umap2 = umap2; 1892 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, 1893 &is_subset_entry, &data) < 0 && 1894 data.is_subset) 1895 goto error; 1896 1897 isl_union_map_free(umap1); 1898 isl_union_map_free(umap2); 1899 1900 return data.is_subset; 1901error: 1902 isl_union_map_free(umap1); 1903 isl_union_map_free(umap2); 1904 return -1; 1905} 1906 1907int isl_union_set_is_subset(__isl_keep isl_union_set *uset1, 1908 __isl_keep isl_union_set *uset2) 1909{ 1910 return isl_union_map_is_subset(uset1, uset2); 1911} 1912 1913int isl_union_map_is_equal(__isl_keep isl_union_map *umap1, 1914 __isl_keep isl_union_map *umap2) 1915{ 1916 int is_subset; 1917 1918 if (!umap1 || !umap2) 1919 return -1; 1920 is_subset = isl_union_map_is_subset(umap1, umap2); 1921 if (is_subset != 1) 1922 return is_subset; 1923 is_subset = isl_union_map_is_subset(umap2, umap1); 1924 return is_subset; 1925} 1926 1927int isl_union_set_is_equal(__isl_keep isl_union_set *uset1, 1928 __isl_keep isl_union_set *uset2) 1929{ 1930 return isl_union_map_is_equal(uset1, uset2); 1931} 1932 1933int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1, 1934 __isl_keep isl_union_map *umap2) 1935{ 1936 int is_subset; 1937 1938 if (!umap1 || !umap2) 1939 return -1; 1940 is_subset = isl_union_map_is_subset(umap1, umap2); 1941 if (is_subset != 1) 1942 return is_subset; 1943 is_subset = isl_union_map_is_subset(umap2, umap1); 1944 if (is_subset == -1) 1945 return is_subset; 1946 return !is_subset; 1947} 1948 1949int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1, 1950 __isl_keep isl_union_set *uset2) 1951{ 1952 return isl_union_map_is_strict_subset(uset1, uset2); 1953} 1954 1955static int sample_entry(void **entry, void *user) 1956{ 1957 isl_basic_map **sample = (isl_basic_map **)user; 1958 isl_map *map = *entry; 1959 1960 *sample = isl_map_sample(isl_map_copy(map)); 1961 if (!*sample) 1962 return -1; 1963 if (!isl_basic_map_plain_is_empty(*sample)) 1964 return -1; 1965 return 0; 1966} 1967 1968__isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap) 1969{ 1970 isl_basic_map *sample = NULL; 1971 1972 if (!umap) 1973 return NULL; 1974 1975 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, 1976 &sample_entry, &sample) < 0 && 1977 !sample) 1978 goto error; 1979 1980 if (!sample) 1981 sample = isl_basic_map_empty(isl_union_map_get_space(umap)); 1982 1983 isl_union_map_free(umap); 1984 1985 return sample; 1986error: 1987 isl_union_map_free(umap); 1988 return NULL; 1989} 1990 1991__isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset) 1992{ 1993 return (isl_basic_set *)isl_union_map_sample(uset); 1994} 1995 1996struct isl_forall_data { 1997 int res; 1998 int (*fn)(__isl_keep isl_map *map); 1999}; 2000 2001static int forall_entry(void **entry, void *user) 2002{ 2003 struct isl_forall_data *data = user; 2004 isl_map *map = *entry; 2005 2006 data->res = data->fn(map); 2007 if (data->res < 0) 2008 return -1; 2009 2010 if (!data->res) 2011 return -1; 2012 2013 return 0; 2014} 2015 2016static int union_map_forall(__isl_keep isl_union_map *umap, 2017 int (*fn)(__isl_keep isl_map *map)) 2018{ 2019 struct isl_forall_data data = { 1, fn }; 2020 2021 if (!umap) 2022 return -1; 2023 2024 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, 2025 &forall_entry, &data) < 0 && data.res) 2026 return -1; 2027 2028 return data.res; 2029} 2030 2031struct isl_forall_user_data { 2032 int res; 2033 int (*fn)(__isl_keep isl_map *map, void *user); 2034 void *user; 2035}; 2036 2037static int forall_user_entry(void **entry, void *user) 2038{ 2039 struct isl_forall_user_data *data = user; 2040 isl_map *map = *entry; 2041 2042 data->res = data->fn(map, data->user); 2043 if (data->res < 0) 2044 return -1; 2045 2046 if (!data->res) 2047 return -1; 2048 2049 return 0; 2050} 2051 2052/* Check if fn(map, user) returns true for all maps "map" in umap. 2053 */ 2054static int union_map_forall_user(__isl_keep isl_union_map *umap, 2055 int (*fn)(__isl_keep isl_map *map, void *user), void *user) 2056{ 2057 struct isl_forall_user_data data = { 1, fn, user }; 2058 2059 if (!umap) 2060 return -1; 2061 2062 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, 2063 &forall_user_entry, &data) < 0 && data.res) 2064 return -1; 2065 2066 return data.res; 2067} 2068 2069int isl_union_map_is_empty(__isl_keep isl_union_map *umap) 2070{ 2071 return union_map_forall(umap, &isl_map_is_empty); 2072} 2073 2074int isl_union_set_is_empty(__isl_keep isl_union_set *uset) 2075{ 2076 return isl_union_map_is_empty(uset); 2077} 2078 2079static int is_subset_of_identity(__isl_keep isl_map *map) 2080{ 2081 int is_subset; 2082 isl_space *dim; 2083 isl_map *id; 2084 2085 if (!map) 2086 return -1; 2087 2088 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out)) 2089 return 0; 2090 2091 dim = isl_map_get_space(map); 2092 id = isl_map_identity(dim); 2093 2094 is_subset = isl_map_is_subset(map, id); 2095 2096 isl_map_free(id); 2097 2098 return is_subset; 2099} 2100 2101/* Check if the given map is single-valued. 2102 * We simply compute 2103 * 2104 * M \circ M^-1 2105 * 2106 * and check if the result is a subset of the identity mapping. 2107 */ 2108int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap) 2109{ 2110 isl_union_map *test; 2111 int sv; 2112 2113 if (isl_union_map_n_map(umap) == 1) { 2114 isl_map *map; 2115 umap = isl_union_map_copy(umap); 2116 map = isl_map_from_union_map(umap); 2117 sv = isl_map_is_single_valued(map); 2118 isl_map_free(map); 2119 return sv; 2120 } 2121 2122 test = isl_union_map_reverse(isl_union_map_copy(umap)); 2123 test = isl_union_map_apply_range(test, isl_union_map_copy(umap)); 2124 2125 sv = union_map_forall(test, &is_subset_of_identity); 2126 2127 isl_union_map_free(test); 2128 2129 return sv; 2130} 2131 2132int isl_union_map_is_injective(__isl_keep isl_union_map *umap) 2133{ 2134 int in; 2135 2136 umap = isl_union_map_copy(umap); 2137 umap = isl_union_map_reverse(umap); 2138 in = isl_union_map_is_single_valued(umap); 2139 isl_union_map_free(umap); 2140 2141 return in; 2142} 2143 2144/* Represents a map that has a fixed value (v) for one of its 2145 * range dimensions. 2146 * The map in this structure is not reference counted, so it 2147 * is only valid while the isl_union_map from which it was 2148 * obtained is still alive. 2149 */ 2150struct isl_fixed_map { 2151 isl_int v; 2152 isl_map *map; 2153}; 2154 2155static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx, 2156 int n) 2157{ 2158 int i; 2159 struct isl_fixed_map *v; 2160 2161 v = isl_calloc_array(ctx, struct isl_fixed_map, n); 2162 if (!v) 2163 return NULL; 2164 for (i = 0; i < n; ++i) 2165 isl_int_init(v[i].v); 2166 return v; 2167} 2168 2169static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n) 2170{ 2171 int i; 2172 2173 if (!v) 2174 return; 2175 for (i = 0; i < n; ++i) 2176 isl_int_clear(v[i].v); 2177 free(v); 2178} 2179 2180/* Compare the "v" field of two isl_fixed_map structs. 2181 */ 2182static int qsort_fixed_map_cmp(const void *p1, const void *p2) 2183{ 2184 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1; 2185 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2; 2186 2187 return isl_int_cmp(e1->v, e2->v); 2188} 2189 2190/* Internal data structure used while checking whether all maps 2191 * in a union_map have a fixed value for a given output dimension. 2192 * v is the list of maps, with the fixed value for the dimension 2193 * n is the number of maps considered so far 2194 * pos is the output dimension under investigation 2195 */ 2196struct isl_fixed_dim_data { 2197 struct isl_fixed_map *v; 2198 int n; 2199 int pos; 2200}; 2201 2202static int fixed_at_pos(__isl_keep isl_map *map, void *user) 2203{ 2204 struct isl_fixed_dim_data *data = user; 2205 2206 data->v[data->n].map = map; 2207 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos, 2208 &data->v[data->n++].v); 2209} 2210 2211static int plain_injective_on_range(__isl_take isl_union_map *umap, 2212 int first, int n_range); 2213 2214/* Given a list of the maps, with their fixed values at output dimension "pos", 2215 * check whether the ranges of the maps form an obvious partition. 2216 * 2217 * We first sort the maps according to their fixed values. 2218 * If all maps have a different value, then we know the ranges form 2219 * a partition. 2220 * Otherwise, we collect the maps with the same fixed value and 2221 * check whether each such collection is obviously injective 2222 * based on later dimensions. 2223 */ 2224static int separates(struct isl_fixed_map *v, int n, 2225 __isl_take isl_space *dim, int pos, int n_range) 2226{ 2227 int i; 2228 2229 if (!v) 2230 goto error; 2231 2232 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp); 2233 2234 for (i = 0; i + 1 < n; ++i) { 2235 int j, k; 2236 isl_union_map *part; 2237 int injective; 2238 2239 for (j = i + 1; j < n; ++j) 2240 if (isl_int_ne(v[i].v, v[j].v)) 2241 break; 2242 2243 if (j == i + 1) 2244 continue; 2245 2246 part = isl_union_map_alloc(isl_space_copy(dim), j - i); 2247 for (k = i; k < j; ++k) 2248 part = isl_union_map_add_map(part, 2249 isl_map_copy(v[k].map)); 2250 2251 injective = plain_injective_on_range(part, pos + 1, n_range); 2252 if (injective < 0) 2253 goto error; 2254 if (!injective) 2255 break; 2256 2257 i = j - 1; 2258 } 2259 2260 isl_space_free(dim); 2261 free_isl_fixed_map_array(v, n); 2262 return i + 1 >= n; 2263error: 2264 isl_space_free(dim); 2265 free_isl_fixed_map_array(v, n); 2266 return -1; 2267} 2268 2269/* Check whether the maps in umap have obviously distinct ranges. 2270 * In particular, check for an output dimension in the range 2271 * [first,n_range) for which all maps have a fixed value 2272 * and then check if these values, possibly along with fixed values 2273 * at later dimensions, entail distinct ranges. 2274 */ 2275static int plain_injective_on_range(__isl_take isl_union_map *umap, 2276 int first, int n_range) 2277{ 2278 isl_ctx *ctx; 2279 int n; 2280 struct isl_fixed_dim_data data = { NULL }; 2281 2282 ctx = isl_union_map_get_ctx(umap); 2283 2284 n = isl_union_map_n_map(umap); 2285 if (!umap) 2286 goto error; 2287 2288 if (n <= 1) { 2289 isl_union_map_free(umap); 2290 return 1; 2291 } 2292 2293 if (first >= n_range) { 2294 isl_union_map_free(umap); 2295 return 0; 2296 } 2297 2298 data.v = alloc_isl_fixed_map_array(ctx, n); 2299 if (!data.v) 2300 goto error; 2301 2302 for (data.pos = first; data.pos < n_range; ++data.pos) { 2303 int fixed; 2304 int injective; 2305 isl_space *dim; 2306 2307 data.n = 0; 2308 fixed = union_map_forall_user(umap, &fixed_at_pos, &data); 2309 if (fixed < 0) 2310 goto error; 2311 if (!fixed) 2312 continue; 2313 dim = isl_union_map_get_space(umap); 2314 injective = separates(data.v, n, dim, data.pos, n_range); 2315 isl_union_map_free(umap); 2316 return injective; 2317 } 2318 2319 free_isl_fixed_map_array(data.v, n); 2320 isl_union_map_free(umap); 2321 2322 return 0; 2323error: 2324 free_isl_fixed_map_array(data.v, n); 2325 isl_union_map_free(umap); 2326 return -1; 2327} 2328 2329/* Check whether the maps in umap that map to subsets of "ran" 2330 * have obviously distinct ranges. 2331 */ 2332static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user) 2333{ 2334 isl_union_map *umap = user; 2335 2336 umap = isl_union_map_copy(umap); 2337 umap = isl_union_map_intersect_range(umap, 2338 isl_union_set_from_set(isl_set_copy(ran))); 2339 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set)); 2340} 2341 2342/* Check if the given union_map is obviously injective. 2343 * 2344 * In particular, we first check if all individual maps are obviously 2345 * injective and then check if all the ranges of these maps are 2346 * obviously disjoint. 2347 */ 2348int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap) 2349{ 2350 int in; 2351 isl_union_map *univ; 2352 isl_union_set *ran; 2353 2354 in = union_map_forall(umap, &isl_map_plain_is_injective); 2355 if (in < 0) 2356 return -1; 2357 if (!in) 2358 return 0; 2359 2360 univ = isl_union_map_universe(isl_union_map_copy(umap)); 2361 ran = isl_union_map_range(univ); 2362 2363 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap); 2364 2365 isl_union_set_free(ran); 2366 2367 return in; 2368} 2369 2370int isl_union_map_is_bijective(__isl_keep isl_union_map *umap) 2371{ 2372 int sv; 2373 2374 sv = isl_union_map_is_single_valued(umap); 2375 if (sv < 0 || !sv) 2376 return sv; 2377 2378 return isl_union_map_is_injective(umap); 2379} 2380 2381static int zip_entry(void **entry, void *user) 2382{ 2383 isl_map *map = *entry; 2384 isl_union_map **res = user; 2385 2386 if (!isl_map_can_zip(map)) 2387 return 0; 2388 2389 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map))); 2390 2391 return 0; 2392} 2393 2394__isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap) 2395{ 2396 return cond_un_op(umap, &zip_entry); 2397} 2398 2399static int uncurry_entry(void **entry, void *user) 2400{ 2401 isl_map *map = *entry; 2402 isl_union_map **res = user; 2403 2404 if (!isl_map_can_uncurry(map)) 2405 return 0; 2406 2407 *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map))); 2408 2409 return 0; 2410} 2411 2412/* Given a union map, take the maps of the form A -> (B -> C) and 2413 * return the union of the corresponding maps (A -> B) -> C. 2414 */ 2415__isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap) 2416{ 2417 return cond_un_op(umap, &uncurry_entry); 2418} 2419 2420static int curry_entry(void **entry, void *user) 2421{ 2422 isl_map *map = *entry; 2423 isl_union_map **res = user; 2424 2425 if (!isl_map_can_curry(map)) 2426 return 0; 2427 2428 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map))); 2429 2430 return 0; 2431} 2432 2433/* Given a union map, take the maps of the form (A -> B) -> C and 2434 * return the union of the corresponding maps A -> (B -> C). 2435 */ 2436__isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap) 2437{ 2438 return cond_un_op(umap, &curry_entry); 2439} 2440 2441static int lift_entry(void **entry, void *user) 2442{ 2443 isl_set *set = *entry; 2444 isl_union_set **res = user; 2445 2446 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set))); 2447 2448 return 0; 2449} 2450 2451__isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset) 2452{ 2453 return cond_un_op(uset, &lift_entry); 2454} 2455 2456static int coefficients_entry(void **entry, void *user) 2457{ 2458 isl_set *set = *entry; 2459 isl_union_set **res = user; 2460 2461 set = isl_set_copy(set); 2462 set = isl_set_from_basic_set(isl_set_coefficients(set)); 2463 *res = isl_union_set_add_set(*res, set); 2464 2465 return 0; 2466} 2467 2468__isl_give isl_union_set *isl_union_set_coefficients( 2469 __isl_take isl_union_set *uset) 2470{ 2471 isl_ctx *ctx; 2472 isl_space *dim; 2473 isl_union_set *res; 2474 2475 if (!uset) 2476 return NULL; 2477 2478 ctx = isl_union_set_get_ctx(uset); 2479 dim = isl_space_set_alloc(ctx, 0, 0); 2480 res = isl_union_map_alloc(dim, uset->table.n); 2481 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table, 2482 &coefficients_entry, &res) < 0) 2483 goto error; 2484 2485 isl_union_set_free(uset); 2486 return res; 2487error: 2488 isl_union_set_free(uset); 2489 isl_union_set_free(res); 2490 return NULL; 2491} 2492 2493static int solutions_entry(void **entry, void *user) 2494{ 2495 isl_set *set = *entry; 2496 isl_union_set **res = user; 2497 2498 set = isl_set_copy(set); 2499 set = isl_set_from_basic_set(isl_set_solutions(set)); 2500 if (!*res) 2501 *res = isl_union_set_from_set(set); 2502 else 2503 *res = isl_union_set_add_set(*res, set); 2504 2505 if (!*res) 2506 return -1; 2507 2508 return 0; 2509} 2510 2511__isl_give isl_union_set *isl_union_set_solutions( 2512 __isl_take isl_union_set *uset) 2513{ 2514 isl_union_set *res = NULL; 2515 2516 if (!uset) 2517 return NULL; 2518 2519 if (uset->table.n == 0) { 2520 res = isl_union_set_empty(isl_union_set_get_space(uset)); 2521 isl_union_set_free(uset); 2522 return res; 2523 } 2524 2525 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table, 2526 &solutions_entry, &res) < 0) 2527 goto error; 2528 2529 isl_union_set_free(uset); 2530 return res; 2531error: 2532 isl_union_set_free(uset); 2533 isl_union_set_free(res); 2534 return NULL; 2535} 2536 2537/* Internal data structure for isl_union_map_preimage_domain_multi_aff. 2538 * 2539 * "ma" is the function under which the preimage should be taken. 2540 * "space" is the space of "ma". 2541 * "res" collects the results. 2542 */ 2543struct isl_union_map_preimage_domain_data { 2544 isl_space *space; 2545 isl_multi_aff *ma; 2546 isl_union_map *res; 2547}; 2548 2549/* Compute the preimage of the domain of *entry under the function 2550 * represented by data->ma, provided the domain space of *entry 2551 * match the target space of data->ma, and add the result to data->res. 2552 */ 2553static int preimage_domain_entry(void **entry, void *user) 2554{ 2555 int m; 2556 isl_map *map = *entry; 2557 struct isl_union_map_preimage_domain_data *data = user; 2558 int empty; 2559 2560 m = isl_space_tuple_match(map->dim, isl_dim_in, 2561 data->space, isl_dim_out); 2562 if (m < 0) 2563 return -1; 2564 if (!m) 2565 return 0; 2566 2567 map = isl_map_copy(map); 2568 map = isl_map_preimage_domain_multi_aff(map, 2569 isl_multi_aff_copy(data->ma)); 2570 2571 empty = isl_map_is_empty(map); 2572 if (empty < 0 || empty) { 2573 isl_map_free(map); 2574 return empty < 0 ? -1 : 0; 2575 } 2576 2577 data->res = isl_union_map_add_map(data->res, map); 2578 2579 return 0; 2580} 2581 2582/* Compute the preimage of the domain of "umap" under the function 2583 * represented by "ma". 2584 * In other words, plug in "ma" in the domain of "umap". 2585 * The result contains maps that live in the same spaces as the maps of "umap" 2586 * with domain space equal to the target space of "ma", 2587 * except that the domain has been replaced by the domain space of "ma". 2588 */ 2589__isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff( 2590 __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma) 2591{ 2592 isl_ctx *ctx; 2593 isl_space *space; 2594 struct isl_union_map_preimage_domain_data data; 2595 2596 if (!umap || !ma) 2597 goto error; 2598 2599 ctx = isl_union_map_get_ctx(umap); 2600 space = isl_union_map_get_space(umap); 2601 data.space = isl_multi_aff_get_space(ma); 2602 data.ma = ma; 2603 data.res = isl_union_map_alloc(space, umap->table.n); 2604 if (isl_hash_table_foreach(ctx, &umap->table, &preimage_domain_entry, 2605 &data) < 0) 2606 data.res = isl_union_map_free(data.res); 2607 2608 isl_space_free(data.space); 2609 isl_union_map_free(umap); 2610 isl_multi_aff_free(ma); 2611 return data.res; 2612error: 2613 isl_union_map_free(umap); 2614 isl_multi_aff_free(ma); 2615 return NULL; 2616} 2617