1/* 2 * Copyright 2011 Sven Verdoolaege 3 * Copyright 2012-2014 Ecole Normale Superieure 4 * 5 * Use of this software is governed by the MIT license 6 * 7 * Written by Sven Verdoolaege, 8 * Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 9 */ 10 11#include <isl/id.h> 12#include <isl_space_private.h> 13#include <isl/set.h> 14#include <isl_reordering.h> 15 16#include <isl_multi_macro.h> 17 18#define MULTI_NAME(BASE) "isl_multi_" #BASE 19 20isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi) 21{ 22 return multi ? isl_space_get_ctx(multi->space) : NULL; 23} 24 25/* Return the space of "multi". 26 */ 27__isl_keep isl_space *FN(MULTI(BASE),peek_space)(__isl_keep MULTI(BASE) *multi) 28{ 29 return multi ? multi->space : NULL; 30} 31 32__isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi) 33{ 34 return isl_space_copy(FN(MULTI(BASE),peek_space)(multi)); 35} 36 37__isl_give isl_space *FN(MULTI(BASE),get_domain_space)( 38 __isl_keep MULTI(BASE) *multi) 39{ 40 return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL; 41} 42 43/* Allocate a multi expression living in "space". 44 * 45 * If the number of base expressions is zero, then make sure 46 * there is enough room in the structure for the explicit domain, 47 * in case the type supports such an explicit domain. 48 */ 49__isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space) 50{ 51 isl_ctx *ctx; 52 isl_size n; 53 MULTI(BASE) *multi; 54 55 n = isl_space_dim(space, isl_dim_out); 56 if (n < 0) 57 goto error; 58 59 ctx = isl_space_get_ctx(space); 60 if (n > 0) 61 multi = isl_calloc(ctx, MULTI(BASE), 62 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *)); 63 else 64 multi = isl_calloc(ctx, MULTI(BASE), sizeof(MULTI(BASE))); 65 if (!multi) 66 goto error; 67 68 multi->space = space; 69 multi->n = n; 70 multi->ref = 1; 71 if (FN(MULTI(BASE),has_explicit_domain)(multi)) 72 multi = FN(MULTI(BASE),init_explicit_domain)(multi); 73 return multi; 74error: 75 isl_space_free(space); 76 return NULL; 77} 78 79__isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi) 80{ 81 int i; 82 MULTI(BASE) *dup; 83 84 if (!multi) 85 return NULL; 86 87 dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space)); 88 if (!dup) 89 return NULL; 90 91 for (i = 0; i < multi->n; ++i) 92 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i, 93 FN(EL,copy)(multi->u.p[i])); 94 if (FN(MULTI(BASE),has_explicit_domain)(multi)) 95 dup = FN(MULTI(BASE),copy_explicit_domain)(dup, multi); 96 97 return dup; 98} 99 100__isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi) 101{ 102 if (!multi) 103 return NULL; 104 105 if (multi->ref == 1) 106 return multi; 107 108 multi->ref--; 109 return FN(MULTI(BASE),dup)(multi); 110} 111 112__isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi) 113{ 114 if (!multi) 115 return NULL; 116 117 multi->ref++; 118 return multi; 119} 120 121__isl_null MULTI(BASE) *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi) 122{ 123 int i; 124 125 if (!multi) 126 return NULL; 127 128 if (--multi->ref > 0) 129 return NULL; 130 131 isl_space_free(multi->space); 132 for (i = 0; i < multi->n; ++i) 133 FN(EL,free)(multi->u.p[i]); 134 if (FN(MULTI(BASE),has_explicit_domain)(multi)) 135 FN(MULTI(BASE),free_explicit_domain)(multi); 136 free(multi); 137 138 return NULL; 139} 140 141/* Return the space of "multi". 142 * The caller is not allowed to modify "multi" between this call 143 * and the call to *_restore_space because the number 144 * of references needs to stay the same. 145 * The only exception is that isl_multi_*_free can be called instead. 146 * No copy is taken of multi->space if "multi" has only one reference 147 * such that it can be modified inplace if both have only a single reference. 148 */ 149__isl_give isl_space *FN(MULTI(BASE),take_space)(__isl_keep MULTI(BASE) *multi) 150{ 151 isl_space *space; 152 153 if (!multi) 154 return NULL; 155 if (multi->ref != 1) 156 return FN(MULTI(BASE),get_space)(multi); 157 space = multi->space; 158 multi->space = NULL; 159 return space; 160} 161 162/* Set the space of "multi" to "space", where the space of "multi" 163 * may be missing due to a preceding call to isl_multi_*_take_space. 164 * However, in this case, "multi" only has a single reference and 165 * then the call to isl_multi_*_cow has no effect. 166 */ 167__isl_give MULTI(BASE) *FN(MULTI(BASE),restore_space)( 168 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space) 169{ 170 if (!multi || !space) 171 goto error; 172 173 if (multi->space == space) { 174 isl_space_free(space); 175 return multi; 176 } 177 178 multi = FN(MULTI(BASE),cow)(multi); 179 if (!multi) 180 goto error; 181 isl_space_free(multi->space); 182 multi->space = space; 183 184 return multi; 185error: 186 FN(MULTI(BASE),free)(multi); 187 isl_space_free(space); 188 return NULL; 189} 190 191isl_size FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi, 192 enum isl_dim_type type) 193{ 194 return isl_space_dim(FN(MULTI(BASE),peek_space)(multi), type); 195} 196 197/* Return the number of base expressions in "multi". 198 */ 199isl_size FN(MULTI(BASE),size)(__isl_keep MULTI(BASE) *multi) 200{ 201 return multi ? multi->n : isl_size_error; 202} 203 204#undef TYPE 205#define TYPE MULTI(BASE) 206static 207#include "check_type_range_templ.c" 208 209/* Return the base expression at position "pos" in "multi". 210 */ 211static __isl_give EL *FN(MULTI(BASE),peek_at)(__isl_keep MULTI(BASE) *multi, 212 int pos) 213{ 214 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0) 215 return NULL; 216 return multi->u.p[pos]; 217} 218 219/* Return a copy of the base expression at position "pos" in "multi". 220 */ 221__isl_give EL *FN(MULTI(BASE),get_at)(__isl_keep MULTI(BASE) *multi, int pos) 222{ 223 return FN(EL,copy)(FN(MULTI(BASE),peek_at)(multi, pos)); 224} 225 226/* This is an alternative name for the function above. 227 */ 228__isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi, 229 int pos) 230{ 231 return FN(MULTI(BASE),get_at)(multi, pos); 232} 233 234/* Return the base expression at position "pos" in "multi". 235 * This may be either a copy or the base expression itself 236 * if there is only one reference to "multi". 237 * This allows the base expression to be modified inplace 238 * if both the multi expression and this base expression 239 * have only a single reference. 240 * The caller is not allowed to modify "multi" between this call and 241 * the subsequent call to isl_multi_*_restore_at_*. 242 * The only exception is that isl_multi_*_free can be called instead. 243 */ 244static __isl_give EL *FN(MULTI(BASE),take_at)(__isl_keep MULTI(BASE) *multi, 245 int pos) 246{ 247 EL *el; 248 249 if (!multi) 250 return NULL; 251 if (multi->ref != 1) 252 return FN(MULTI(BASE),get_at)(multi, pos); 253 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0) 254 return NULL; 255 el = multi->u.p[pos]; 256 multi->u.p[pos] = NULL; 257 return el; 258} 259 260/* Set the element at position "pos" of "multi" to "el", 261 * where the position may be empty if "multi" has only a single reference. 262 */ 263static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_at)( 264 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el) 265{ 266 if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0 || !el) 267 goto error; 268 269 if (multi->u.p[pos] == el) { 270 FN(EL,free)(el); 271 return multi; 272 } 273 274 multi = FN(MULTI(BASE),cow)(multi); 275 if (!multi) 276 goto error; 277 278 FN(EL,free)(multi->u.p[pos]); 279 multi->u.p[pos] = el; 280 281 return multi; 282error: 283 FN(MULTI(BASE),free)(multi); 284 FN(EL,free)(el); 285 return NULL; 286} 287 288/* Set the element at position "pos" of "multi" to "el", 289 * where the position may be empty if "multi" has only a single reference. 290 * However, the space of "multi" is available and is checked 291 * for compatibility with "el". 292 */ 293static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)( 294 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el) 295{ 296 isl_space *space; 297 298 space = FN(MULTI(BASE),peek_space)(multi); 299 if (FN(EL,check_match_domain_space)(el, space) < 0) 300 multi = FN(MULTI(BASE),free)(multi); 301 return FN(MULTI(BASE),restore_at)(multi, pos, el); 302} 303 304/* Replace the base expression at position "pos" in "multi" with "el". 305 */ 306__isl_give MULTI(BASE) *FN(MULTI(BASE),set_at)( 307 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el) 308{ 309 isl_space *multi_space = NULL; 310 isl_space *el_space = NULL; 311 isl_bool match; 312 313 multi_space = FN(MULTI(BASE),get_space)(multi); 314 match = FN(EL,matching_params)(el, multi_space); 315 if (match < 0) 316 goto error; 317 if (!match) { 318 multi = FN(MULTI(BASE),align_params)(multi, 319 FN(EL,get_space)(el)); 320 isl_space_free(multi_space); 321 multi_space = FN(MULTI(BASE),get_space)(multi); 322 el = FN(EL,align_params)(el, isl_space_copy(multi_space)); 323 } 324 325 multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el); 326 327 isl_space_free(multi_space); 328 isl_space_free(el_space); 329 330 return multi; 331error: 332 FN(MULTI(BASE),free)(multi); 333 FN(EL,free)(el); 334 isl_space_free(multi_space); 335 isl_space_free(el_space); 336 return NULL; 337} 338 339/* This is an alternative name for the function above. 340 */ 341__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)( 342 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el) 343{ 344 return FN(MULTI(BASE),set_at)(multi, pos, el); 345} 346 347/* Return the base expressions of "multi" as a list. 348 */ 349__isl_give LIST(EL) *FN(MULTI(BASE),get_list)( 350 __isl_keep MULTI(BASE) *multi) 351{ 352 isl_size n; 353 int i; 354 LIST(EL) *list; 355 356 n = FN(MULTI(BASE),size)(multi); 357 if (n < 0) 358 return NULL; 359 list = FN(LIST(EL),alloc)(FN(MULTI(BASE),get_ctx(multi)), n); 360 for (i = 0; i < n; ++i) { 361 EL *el = FN(MULTI(BASE),get_at)(multi, i); 362 list = FN(LIST(EL),add)(list, el); 363 } 364 365 return list; 366} 367 368/* Reset the space of "multi". This function is called from isl_pw_templ.c 369 * and doesn't know if the space of an element object is represented 370 * directly or through its domain. It therefore passes along both, 371 * which we pass along to the element function since we don't know how 372 * that is represented either. 373 * 374 * If "multi" has an explicit domain, then the caller is expected 375 * to make sure that any modification that would change the dimensions 376 * of the explicit domain has bee applied before this function is called. 377 */ 378__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)( 379 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space, 380 __isl_take isl_space *domain) 381{ 382 isl_size n; 383 int i; 384 385 n = FN(MULTI(BASE),size)(multi); 386 if (n < 0 || !space || !domain) 387 goto error; 388 389 for (i = 0; i < n; ++i) { 390 EL *el; 391 392 el = FN(MULTI(BASE),take_at)(multi, i); 393 el = FN(EL,reset_domain_space)(el, isl_space_copy(domain)); 394 multi = FN(MULTI(BASE),restore_at)(multi, i, el); 395 } 396 if (FN(MULTI(BASE),has_explicit_domain)(multi)) 397 multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi, 398 isl_space_copy(domain)); 399 isl_space_free(domain); 400 401 multi = FN(MULTI(BASE),restore_space)(multi, space); 402 403 return multi; 404error: 405 isl_space_free(domain); 406 isl_space_free(space); 407 FN(MULTI(BASE),free)(multi); 408 return NULL; 409} 410 411__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)( 412 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain) 413{ 414 isl_space *space, *multi_space; 415 416 multi_space = FN(MULTI(BASE),get_space)(multi); 417 space = isl_space_extend_domain_with_range(isl_space_copy(domain), 418 multi_space); 419 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain); 420} 421 422__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)( 423 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space) 424{ 425 isl_space *domain; 426 427 domain = isl_space_domain(isl_space_copy(space)); 428 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain); 429} 430 431/* Reset the user pointer on all identifiers of parameters and tuples 432 * of the space of "multi". 433 */ 434__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_user)( 435 __isl_take MULTI(BASE) *multi) 436{ 437 isl_space *space; 438 439 space = FN(MULTI(BASE),get_space)(multi); 440 space = isl_space_reset_user(space); 441 442 return FN(MULTI(BASE),reset_space)(multi, space); 443} 444 445__isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)( 446 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp) 447{ 448 int i; 449 isl_size n; 450 isl_space *space; 451 452 n = FN(MULTI(BASE),size)(multi); 453 if (n < 0 || !exp) 454 goto error; 455 456 for (i = 0; i < n; ++i) { 457 EL *el; 458 459 el = FN(MULTI(BASE),take_at)(multi, i); 460 el = FN(EL,realign_domain)(el, isl_reordering_copy(exp)); 461 multi = FN(MULTI(BASE),restore_at)(multi, i, el); 462 } 463 464 space = isl_reordering_get_space(exp); 465 multi = FN(MULTI(BASE),reset_domain_space)(multi, space); 466 467 isl_reordering_free(exp); 468 return multi; 469error: 470 isl_reordering_free(exp); 471 FN(MULTI(BASE),free)(multi); 472 return NULL; 473} 474 475/* Align the parameters of "multi" to those of "model". 476 * 477 * If "multi" has an explicit domain, then align the parameters 478 * of the domain first. 479 */ 480__isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)( 481 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model) 482{ 483 isl_ctx *ctx; 484 isl_bool equal_params; 485 isl_space *domain_space; 486 isl_reordering *exp; 487 488 if (!multi || !model) 489 goto error; 490 491 equal_params = isl_space_has_equal_params(multi->space, model); 492 if (equal_params < 0) 493 goto error; 494 if (equal_params) { 495 isl_space_free(model); 496 return multi; 497 } 498 499 ctx = isl_space_get_ctx(model); 500 if (!isl_space_has_named_params(model)) 501 isl_die(ctx, isl_error_invalid, 502 "model has unnamed parameters", goto error); 503 if (!isl_space_has_named_params(multi->space)) 504 isl_die(ctx, isl_error_invalid, 505 "input has unnamed parameters", goto error); 506 507 if (FN(MULTI(BASE),has_explicit_domain)(multi)) { 508 multi = FN(MULTI(BASE),align_explicit_domain_params)(multi, 509 isl_space_copy(model)); 510 if (!multi) 511 goto error; 512 } 513 domain_space = FN(MULTI(BASE),get_domain_space)(multi); 514 exp = isl_parameter_alignment_reordering(domain_space, model); 515 isl_space_free(domain_space); 516 multi = FN(MULTI(BASE),realign_domain)(multi, exp); 517 518 isl_space_free(model); 519 return multi; 520error: 521 isl_space_free(model); 522 FN(MULTI(BASE),free)(multi); 523 return NULL; 524} 525 526/* Create a multi expression in the given space with the elements of "list" 527 * as base expressions. 528 * 529 * Since isl_multi_*_restore_* assumes that the element and 530 * the multi expression have matching spaces, the alignment 531 * (if any) needs to be performed beforehand. 532 */ 533__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))( 534 __isl_take isl_space *space, __isl_take LIST(EL) *list) 535{ 536 int i; 537 isl_size n, dim; 538 isl_ctx *ctx; 539 MULTI(BASE) *multi; 540 541 dim = isl_space_dim(space, isl_dim_out); 542 n = FN(FN(LIST(EL),n),BASE)(list); 543 if (dim < 0 || n < 0) 544 goto error; 545 546 ctx = isl_space_get_ctx(space); 547 if (n != dim) 548 isl_die(ctx, isl_error_invalid, 549 "invalid number of elements in list", goto error); 550 551 for (i = 0; i < n; ++i) { 552 EL *el = FN(LIST(EL),peek)(list, i); 553 space = isl_space_align_params(space, FN(EL,get_space)(el)); 554 } 555 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space)); 556 for (i = 0; i < n; ++i) { 557 EL *el = FN(FN(LIST(EL),get),BASE)(list, i); 558 el = FN(EL,align_params)(el, isl_space_copy(space)); 559 multi = FN(MULTI(BASE),restore_check_space)(multi, i, el); 560 } 561 562 isl_space_free(space); 563 FN(LIST(EL),free)(list); 564 return multi; 565error: 566 isl_space_free(space); 567 FN(LIST(EL),free)(list); 568 return NULL; 569} 570 571/* This function performs the same operation as isl_multi_*_from_*_list, 572 * but is considered as a function on an isl_space when exported. 573 */ 574__isl_give MULTI(BASE) *FN(isl_space_multi,BASE)(__isl_take isl_space *space, 575 __isl_take LIST(EL) *list) 576{ 577 return FN(FN(MULTI(BASE),from),LIST(BASE))(space, list); 578} 579 580/* Drop the "n" output dimensions of "multi" starting at "first", 581 * where the space is assumed to have been adjusted already. 582 */ 583static __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_output_dims)( 584 __isl_take MULTI(BASE) *multi, unsigned first, unsigned n) 585{ 586 int i; 587 588 multi = FN(MULTI(BASE),cow)(multi); 589 if (!multi) 590 return NULL; 591 592 for (i = 0; i < n; ++i) 593 FN(EL,free)(multi->u.p[first + i]); 594 for (i = first; i + n < multi->n; ++i) 595 multi->u.p[i] = multi->u.p[i + n]; 596 multi->n -= n; 597 if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi)) 598 multi = FN(MULTI(BASE),init_explicit_domain)(multi); 599 600 return multi; 601} 602 603__isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)( 604 __isl_take MULTI(BASE) *multi, 605 enum isl_dim_type type, unsigned first, unsigned n) 606{ 607 isl_space *space; 608 isl_size size; 609 int i; 610 611 if (FN(MULTI(BASE),check_range)(multi, type, first, n) < 0) 612 return FN(MULTI(BASE),free)(multi); 613 614 space = FN(MULTI(BASE),take_space)(multi); 615 space = isl_space_drop_dims(space, type, first, n); 616 multi = FN(MULTI(BASE),restore_space)(multi, space); 617 618 if (type == isl_dim_out) 619 return FN(MULTI(BASE),drop_output_dims)(multi, first, n); 620 621 if (FN(MULTI(BASE),has_explicit_domain)(multi)) 622 multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi, 623 type, first, n); 624 625 size = FN(MULTI(BASE),size)(multi); 626 if (size < 0) 627 return FN(MULTI(BASE),free)(multi); 628 for (i = 0; i < size; ++i) { 629 EL *el; 630 631 el = FN(MULTI(BASE),take_at)(multi, i); 632 el = FN(EL,drop_dims)(el, type, first, n); 633 multi = FN(MULTI(BASE),restore_at)(multi, i, el); 634 } 635 636 return multi; 637} 638 639#undef TYPE 640#define TYPE MULTI(BASE) 641 642#include "isl_check_named_params_templ.c" 643static 644#include "isl_align_params_bin_templ.c" 645 646/* Given two MULTI(BASE)s A -> B and C -> D, 647 * construct a MULTI(BASE) (A * C) -> [B -> D]. 648 * 649 * If "multi1" and/or "multi2" has an explicit domain, then 650 * intersect the domain of the result with these explicit domains. 651 */ 652__isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)( 653 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2) 654{ 655 int i; 656 isl_size n1, n2; 657 EL *el; 658 isl_space *space; 659 MULTI(BASE) *res; 660 661 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2); 662 n1 = FN(MULTI(BASE),size)(multi1); 663 n2 = FN(MULTI(BASE),size)(multi2); 664 if (n1 < 0 || n2 < 0) 665 goto error; 666 667 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1), 668 FN(MULTI(BASE),get_space)(multi2)); 669 res = FN(MULTI(BASE),alloc)(space); 670 671 for (i = 0; i < n1; ++i) { 672 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i); 673 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el); 674 } 675 676 for (i = 0; i < n2; ++i) { 677 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i); 678 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el); 679 } 680 681 if (FN(MULTI(BASE),has_explicit_domain)(multi1)) 682 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1); 683 if (FN(MULTI(BASE),has_explicit_domain)(multi2)) 684 res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2); 685 686 FN(MULTI(BASE),free)(multi1); 687 FN(MULTI(BASE),free)(multi2); 688 return res; 689error: 690 FN(MULTI(BASE),free)(multi1); 691 FN(MULTI(BASE),free)(multi2); 692 return NULL; 693} 694 695/* Is the range of "multi" a wrapped relation? 696 */ 697isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi) 698{ 699 if (!multi) 700 return isl_bool_error; 701 return isl_space_range_is_wrapping(multi->space); 702} 703 704/* Given a function A -> [B -> C], extract the function A -> B. 705 */ 706__isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)( 707 __isl_take MULTI(BASE) *multi) 708{ 709 isl_space *space; 710 isl_size total, keep; 711 712 total = FN(MULTI(BASE),dim)(multi, isl_dim_out); 713 if (total < 0) 714 return FN(MULTI(BASE),free)(multi); 715 if (!isl_space_range_is_wrapping(multi->space)) 716 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid, 717 "range is not a product", 718 return FN(MULTI(BASE),free)(multi)); 719 720 space = FN(MULTI(BASE),get_space)(multi); 721 space = isl_space_range_factor_domain(space); 722 keep = isl_space_dim(space, isl_dim_out); 723 if (keep < 0) 724 multi = FN(MULTI(BASE),free)(multi); 725 multi = FN(MULTI(BASE),drop_dims)(multi, 726 isl_dim_out, keep, total - keep); 727 multi = FN(MULTI(BASE),reset_space)(multi, space); 728 729 return multi; 730} 731 732/* Given a function A -> [B -> C], extract the function A -> C. 733 */ 734__isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)( 735 __isl_take MULTI(BASE) *multi) 736{ 737 isl_space *space; 738 isl_size total, keep; 739 740 total = FN(MULTI(BASE),dim)(multi, isl_dim_out); 741 if (total < 0) 742 return FN(MULTI(BASE),free)(multi); 743 if (!isl_space_range_is_wrapping(multi->space)) 744 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid, 745 "range is not a product", 746 return FN(MULTI(BASE),free)(multi)); 747 748 space = FN(MULTI(BASE),get_space)(multi); 749 space = isl_space_range_factor_range(space); 750 keep = isl_space_dim(space, isl_dim_out); 751 if (keep < 0) 752 multi = FN(MULTI(BASE),free)(multi); 753 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep); 754 multi = FN(MULTI(BASE),reset_space)(multi, space); 755 756 return multi; 757} 758 759/* Given a function [B -> C], extract the function C. 760 */ 761__isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)( 762 __isl_take MULTI(BASE) *multi) 763{ 764 isl_space *space; 765 isl_size total, keep; 766 767 total = FN(MULTI(BASE),dim)(multi, isl_dim_set); 768 if (total < 0) 769 return FN(MULTI(BASE),free)(multi); 770 if (!isl_space_is_wrapping(multi->space)) 771 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid, 772 "not a product", return FN(MULTI(BASE),free)(multi)); 773 774 space = FN(MULTI(BASE),get_space)(multi); 775 space = isl_space_factor_range(space); 776 keep = isl_space_dim(space, isl_dim_set); 777 if (keep < 0) 778 multi = FN(MULTI(BASE),free)(multi); 779 multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_set, 0, total - keep); 780 multi = FN(MULTI(BASE),reset_space)(multi, space); 781 782 return multi; 783} 784 785__isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)( 786 __isl_take MULTI(BASE) *multi) 787{ 788 isl_space *space; 789 790 space = FN(MULTI(BASE),take_space)(multi); 791 space = isl_space_flatten_range(space); 792 multi = FN(MULTI(BASE),restore_space)(multi, space); 793 794 return multi; 795} 796 797/* Given two MULTI(BASE)s A -> B and C -> D, 798 * construct a MULTI(BASE) (A * C) -> (B, D). 799 */ 800__isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)( 801 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2) 802{ 803 MULTI(BASE) *multi; 804 805 multi = FN(MULTI(BASE),range_product)(multi1, multi2); 806 multi = FN(MULTI(BASE),flatten_range)(multi); 807 return multi; 808} 809 810/* Given two multi expressions, "multi1" 811 * 812 * [A] -> [B1 B2] 813 * 814 * where B2 starts at position "pos", and "multi2" 815 * 816 * [A] -> [D] 817 * 818 * return the multi expression 819 * 820 * [A] -> [B1 D B2] 821 */ 822__isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)( 823 __isl_take MULTI(BASE) *multi1, unsigned pos, 824 __isl_take MULTI(BASE) *multi2) 825{ 826 MULTI(BASE) *res; 827 isl_size dim; 828 829 dim = FN(MULTI(BASE),size)(multi1); 830 if (dim < 0 || !multi2) 831 goto error; 832 833 if (FN(MULTI(BASE),check_range)(multi1, isl_dim_out, pos, 0) < 0) 834 goto error; 835 836 res = FN(MULTI(BASE),copy)(multi1); 837 res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos); 838 multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos); 839 840 res = FN(MULTI(BASE),flat_range_product)(res, multi2); 841 res = FN(MULTI(BASE),flat_range_product)(res, multi1); 842 843 return res; 844error: 845 FN(MULTI(BASE),free)(multi1); 846 FN(MULTI(BASE),free)(multi2); 847 return NULL; 848} 849 850#undef TYPE 851#define TYPE MULTI(BASE) 852 853static 854#include "isl_type_has_equal_space_bin_templ.c" 855static 856#include "isl_type_check_equal_space_templ.c" 857 858/* This function is currently only used from isl_aff.c 859 */ 860static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)( 861 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2, 862 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *)) 863 __attribute__ ((unused)); 864 865/* Pairwise perform "fn" to the elements of "multi1" and "multi2" and 866 * return the result. 867 * 868 * If "multi2" has an explicit domain, then 869 * intersect the domain of the result with this explicit domain. 870 */ 871static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)( 872 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2, 873 __isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *)) 874{ 875 isl_size n; 876 int i; 877 878 FN(MULTI(BASE),align_params_bin)(&multi1, &multi2); 879 n = FN(MULTI(BASE),size)(multi1); 880 if (n < 0 || FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0) 881 goto error; 882 883 for (i = 0; i < n; ++i) { 884 EL *el1, *el2; 885 886 el2 = FN(MULTI(BASE),get_at)(multi2, i); 887 el1 = FN(MULTI(BASE),take_at)(multi1, i); 888 el1 = fn(el1, el2); 889 multi1 = FN(MULTI(BASE),restore_at)(multi1, i, el1); 890 } 891 892 if (FN(MULTI(BASE),has_explicit_domain)(multi2)) 893 multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1, 894 multi2); 895 896 FN(MULTI(BASE),free)(multi2); 897 return multi1; 898error: 899 FN(MULTI(BASE),free)(multi1); 900 FN(MULTI(BASE),free)(multi2); 901 return NULL; 902} 903 904/* Only used on some multi-expressions. 905 */ 906static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi, 907 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused)); 908 909/* Does "test" succeed on any base expression of "multi"? 910 */ 911static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi, 912 isl_bool (*test)(__isl_keep EL *)) 913{ 914 isl_size n; 915 int i; 916 917 n = FN(MULTI(BASE),size)(multi); 918 if (n < 0) 919 return isl_bool_error; 920 921 for (i = 0; i < n; ++i) { 922 isl_bool any = test(multi->u.p[i]); 923 if (any < 0 || any) 924 return any; 925 } 926 927 return isl_bool_false; 928} 929 930/* Only used on some multi-expressions. 931 */ 932static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi, 933 isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused)); 934 935/* Does "test" succeed on every base expression of "multi"? 936 */ 937static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi, 938 isl_bool (*test)(__isl_keep EL *)) 939{ 940 isl_size n; 941 int i; 942 943 n = FN(MULTI(BASE),size)(multi); 944 if (n < 0) 945 return isl_bool_error; 946 947 for (i = 0; i < n; ++i) { 948 isl_bool every = test(multi->u.p[i]); 949 if (every < 0 || !every) 950 return every; 951 } 952 953 return isl_bool_true; 954} 955 956#undef TYPE 957#define TYPE MULTI(BASE) 958#include "isl_from_range_templ.c" 959 960/* Are "multi1" and "multi2" obviously equal? 961 */ 962isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1, 963 __isl_keep MULTI(BASE) *multi2) 964{ 965 int i; 966 isl_bool equal; 967 968 if (!multi1 || !multi2) 969 return isl_bool_error; 970 if (multi1->n != multi2->n) 971 return isl_bool_false; 972 equal = isl_space_is_equal(multi1->space, multi2->space); 973 if (equal < 0 || !equal) 974 return equal; 975 976 for (i = 0; i < multi1->n; ++i) { 977 equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]); 978 if (equal < 0 || !equal) 979 return equal; 980 } 981 982 if (FN(MULTI(BASE),has_explicit_domain)(multi1) || 983 FN(MULTI(BASE),has_explicit_domain)(multi2)) { 984 equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2); 985 if (equal < 0 || !equal) 986 return equal; 987 } 988 989 return isl_bool_true; 990} 991