1#include <isl/aff.h> 2#include <isl_val_private.h> 3 4#define xFN(TYPE,NAME) TYPE ## _ ## NAME 5#define FN(TYPE,NAME) xFN(TYPE,NAME) 6#define xS(TYPE,NAME) struct TYPE ## _ ## NAME 7#define S(TYPE,NAME) xS(TYPE,NAME) 8 9#ifdef HAS_TYPE 10__isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, 11 enum isl_fold type, int n) 12#else 13__isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, int n) 14#endif 15{ 16 isl_ctx *ctx; 17 struct PW *pw; 18 19 if (!dim) 20 return NULL; 21 ctx = isl_space_get_ctx(dim); 22 isl_assert(ctx, n >= 0, goto error); 23 pw = isl_alloc(ctx, struct PW, 24 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece))); 25 if (!pw) 26 goto error; 27 28 pw->ref = 1; 29#ifdef HAS_TYPE 30 pw->type = type; 31#endif 32 pw->size = n; 33 pw->n = 0; 34 pw->dim = dim; 35 return pw; 36error: 37 isl_space_free(dim); 38 return NULL; 39} 40 41#ifdef HAS_TYPE 42__isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim, enum isl_fold type) 43{ 44 return FN(PW,alloc_size)(dim, type, 0); 45} 46#else 47__isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim) 48{ 49 return FN(PW,alloc_size)(dim, 0); 50} 51#endif 52 53__isl_give PW *FN(PW,add_piece)(__isl_take PW *pw, 54 __isl_take isl_set *set, __isl_take EL *el) 55{ 56 isl_ctx *ctx; 57 isl_space *el_dim = NULL; 58 59 if (!pw || !set || !el) 60 goto error; 61 62 if (isl_set_plain_is_empty(set) || FN(EL,EL_IS_ZERO)(el)) { 63 isl_set_free(set); 64 FN(EL,free)(el); 65 return pw; 66 } 67 68 ctx = isl_set_get_ctx(set); 69#ifdef HAS_TYPE 70 if (pw->type != el->type) 71 isl_die(ctx, isl_error_invalid, "fold types don't match", 72 goto error); 73#endif 74 el_dim = FN(EL,get_space(el)); 75 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error); 76 isl_assert(ctx, pw->n < pw->size, goto error); 77 78 pw->p[pw->n].set = set; 79 pw->p[pw->n].FIELD = el; 80 pw->n++; 81 82 isl_space_free(el_dim); 83 return pw; 84error: 85 isl_space_free(el_dim); 86 FN(PW,free)(pw); 87 isl_set_free(set); 88 FN(EL,free)(el); 89 return NULL; 90} 91 92#ifdef HAS_TYPE 93__isl_give PW *FN(PW,alloc)(enum isl_fold type, 94 __isl_take isl_set *set, __isl_take EL *el) 95#else 96__isl_give PW *FN(PW,alloc)(__isl_take isl_set *set, __isl_take EL *el) 97#endif 98{ 99 PW *pw; 100 101 if (!set || !el) 102 goto error; 103 104#ifdef HAS_TYPE 105 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), type, 1); 106#else 107 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), 1); 108#endif 109 110 return FN(PW,add_piece)(pw, set, el); 111error: 112 isl_set_free(set); 113 FN(EL,free)(el); 114 return NULL; 115} 116 117__isl_give PW *FN(PW,dup)(__isl_keep PW *pw) 118{ 119 int i; 120 PW *dup; 121 122 if (!pw) 123 return NULL; 124 125#ifdef HAS_TYPE 126 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, pw->n); 127#else 128 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->n); 129#endif 130 if (!dup) 131 return NULL; 132 133 for (i = 0; i < pw->n; ++i) 134 dup = FN(PW,add_piece)(dup, isl_set_copy(pw->p[i].set), 135 FN(EL,copy)(pw->p[i].FIELD)); 136 137 return dup; 138} 139 140__isl_give PW *FN(PW,cow)(__isl_take PW *pw) 141{ 142 if (!pw) 143 return NULL; 144 145 if (pw->ref == 1) 146 return pw; 147 pw->ref--; 148 return FN(PW,dup)(pw); 149} 150 151__isl_give PW *FN(PW,copy)(__isl_keep PW *pw) 152{ 153 if (!pw) 154 return NULL; 155 156 pw->ref++; 157 return pw; 158} 159 160void *FN(PW,free)(__isl_take PW *pw) 161{ 162 int i; 163 164 if (!pw) 165 return NULL; 166 if (--pw->ref > 0) 167 return NULL; 168 169 for (i = 0; i < pw->n; ++i) { 170 isl_set_free(pw->p[i].set); 171 FN(EL,free)(pw->p[i].FIELD); 172 } 173 isl_space_free(pw->dim); 174 free(pw); 175 176 return NULL; 177} 178 179const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type, 180 unsigned pos) 181{ 182 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL; 183} 184 185int FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type, unsigned pos) 186{ 187 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : -1; 188} 189 190__isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type, 191 unsigned pos) 192{ 193 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL; 194} 195 196int FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type) 197{ 198 return pw ? isl_space_has_tuple_name(pw->dim, type) : -1; 199} 200 201const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type) 202{ 203 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL; 204} 205 206int FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type) 207{ 208 return pw ? isl_space_has_tuple_id(pw->dim, type) : -1; 209} 210 211__isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type) 212{ 213 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL; 214} 215 216int FN(PW,IS_ZERO)(__isl_keep PW *pw) 217{ 218 if (!pw) 219 return -1; 220 221 return pw->n == 0; 222} 223 224#ifndef NO_REALIGN 225__isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw, 226 __isl_take isl_reordering *exp) 227{ 228 int i; 229 230 pw = FN(PW,cow)(pw); 231 if (!pw || !exp) 232 goto error; 233 234 for (i = 0; i < pw->n; ++i) { 235 pw->p[i].set = isl_set_realign(pw->p[i].set, 236 isl_reordering_copy(exp)); 237 if (!pw->p[i].set) 238 goto error; 239 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD, 240 isl_reordering_copy(exp)); 241 if (!pw->p[i].FIELD) 242 goto error; 243 } 244 245 pw = FN(PW,reset_domain_space)(pw, isl_space_copy(exp->dim)); 246 247 isl_reordering_free(exp); 248 return pw; 249error: 250 isl_reordering_free(exp); 251 FN(PW,free)(pw); 252 return NULL; 253} 254 255/* Align the parameters of "pw" to those of "model". 256 */ 257__isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model) 258{ 259 isl_ctx *ctx; 260 261 if (!pw || !model) 262 goto error; 263 264 ctx = isl_space_get_ctx(model); 265 if (!isl_space_has_named_params(model)) 266 isl_die(ctx, isl_error_invalid, 267 "model has unnamed parameters", goto error); 268 if (!isl_space_has_named_params(pw->dim)) 269 isl_die(ctx, isl_error_invalid, 270 "input has unnamed parameters", goto error); 271 if (!isl_space_match(pw->dim, isl_dim_param, model, isl_dim_param)) { 272 isl_reordering *exp; 273 274 model = isl_space_drop_dims(model, isl_dim_in, 275 0, isl_space_dim(model, isl_dim_in)); 276 model = isl_space_drop_dims(model, isl_dim_out, 277 0, isl_space_dim(model, isl_dim_out)); 278 exp = isl_parameter_alignment_reordering(pw->dim, model); 279 exp = isl_reordering_extend_space(exp, 280 FN(PW,get_domain_space)(pw)); 281 pw = FN(PW,realign_domain)(pw, exp); 282 } 283 284 isl_space_free(model); 285 return pw; 286error: 287 isl_space_free(model); 288 FN(PW,free)(pw); 289 return NULL; 290} 291 292static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1, 293 __isl_take PW *pw2, 294 __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2)) 295{ 296 isl_ctx *ctx; 297 298 if (!pw1 || !pw2) 299 goto error; 300 if (isl_space_match(pw1->dim, isl_dim_param, pw2->dim, isl_dim_param)) 301 return fn(pw1, pw2); 302 ctx = FN(PW,get_ctx)(pw1); 303 if (!isl_space_has_named_params(pw1->dim) || 304 !isl_space_has_named_params(pw2->dim)) 305 isl_die(ctx, isl_error_invalid, 306 "unaligned unnamed parameters", goto error); 307 pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2)); 308 pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1)); 309 return fn(pw1, pw2); 310error: 311 FN(PW,free)(pw1); 312 FN(PW,free)(pw2); 313 return NULL; 314} 315 316static __isl_give PW *FN(PW,align_params_pw_set_and)(__isl_take PW *pw, 317 __isl_take isl_set *set, 318 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set)) 319{ 320 isl_ctx *ctx; 321 322 if (!pw || !set) 323 goto error; 324 if (isl_space_match(pw->dim, isl_dim_param, set->dim, isl_dim_param)) 325 return fn(pw, set); 326 ctx = FN(PW,get_ctx)(pw); 327 if (!isl_space_has_named_params(pw->dim) || 328 !isl_space_has_named_params(set->dim)) 329 isl_die(ctx, isl_error_invalid, 330 "unaligned unnamed parameters", goto error); 331 pw = FN(PW,align_params)(pw, isl_set_get_space(set)); 332 set = isl_set_align_params(set, FN(PW,get_space)(pw)); 333 return fn(pw, set); 334error: 335 FN(PW,free)(pw); 336 isl_set_free(set); 337 return NULL; 338} 339#endif 340 341static __isl_give PW *FN(PW,union_add_aligned)(__isl_take PW *pw1, 342 __isl_take PW *pw2) 343{ 344 int i, j, n; 345 struct PW *res; 346 isl_ctx *ctx; 347 isl_set *set; 348 349 if (!pw1 || !pw2) 350 goto error; 351 352 ctx = isl_space_get_ctx(pw1->dim); 353#ifdef HAS_TYPE 354 if (pw1->type != pw2->type) 355 isl_die(ctx, isl_error_invalid, 356 "fold types don't match", goto error); 357#endif 358 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error); 359 360 if (FN(PW,IS_ZERO)(pw1)) { 361 FN(PW,free)(pw1); 362 return pw2; 363 } 364 365 if (FN(PW,IS_ZERO)(pw2)) { 366 FN(PW,free)(pw2); 367 return pw1; 368 } 369 370 n = (pw1->n + 1) * (pw2->n + 1); 371#ifdef HAS_TYPE 372 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->type, n); 373#else 374 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), n); 375#endif 376 377 for (i = 0; i < pw1->n; ++i) { 378 set = isl_set_copy(pw1->p[i].set); 379 for (j = 0; j < pw2->n; ++j) { 380 struct isl_set *common; 381 EL *sum; 382 common = isl_set_intersect(isl_set_copy(pw1->p[i].set), 383 isl_set_copy(pw2->p[j].set)); 384 if (isl_set_plain_is_empty(common)) { 385 isl_set_free(common); 386 continue; 387 } 388 set = isl_set_subtract(set, 389 isl_set_copy(pw2->p[j].set)); 390 391 sum = FN(EL,add_on_domain)(common, 392 FN(EL,copy)(pw1->p[i].FIELD), 393 FN(EL,copy)(pw2->p[j].FIELD)); 394 395 res = FN(PW,add_piece)(res, common, sum); 396 } 397 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD)); 398 } 399 400 for (j = 0; j < pw2->n; ++j) { 401 set = isl_set_copy(pw2->p[j].set); 402 for (i = 0; i < pw1->n; ++i) 403 set = isl_set_subtract(set, 404 isl_set_copy(pw1->p[i].set)); 405 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD)); 406 } 407 408 FN(PW,free)(pw1); 409 FN(PW,free)(pw2); 410 411 return res; 412error: 413 FN(PW,free)(pw1); 414 FN(PW,free)(pw2); 415 return NULL; 416} 417 418/* Private version of "union_add". For isl_pw_qpolynomial and 419 * isl_pw_qpolynomial_fold, we prefer to simply call it "add". 420 */ 421static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2) 422{ 423 return FN(PW,align_params_pw_pw_and)(pw1, pw2, 424 &FN(PW,union_add_aligned)); 425} 426 427/* Make sure "pw" has room for at least "n" more pieces. 428 * 429 * If there is only one reference to pw, we extend it in place. 430 * Otherwise, we create a new PW and copy the pieces. 431 */ 432static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n) 433{ 434 int i; 435 isl_ctx *ctx; 436 PW *res; 437 438 if (!pw) 439 return NULL; 440 if (pw->n + n <= pw->size) 441 return pw; 442 ctx = FN(PW,get_ctx)(pw); 443 n += pw->n; 444 if (pw->ref == 1) { 445 res = isl_realloc(ctx, pw, struct PW, 446 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece))); 447 if (!res) 448 return FN(PW,free)(pw); 449 res->size = n; 450 return res; 451 } 452#ifdef HAS_TYPE 453 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, n); 454#else 455 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), n); 456#endif 457 if (!res) 458 return FN(PW,free)(pw); 459 for (i = 0; i < pw->n; ++i) 460 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set), 461 FN(EL,copy)(pw->p[i].FIELD)); 462 FN(PW,free)(pw); 463 return res; 464} 465 466static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1, 467 __isl_take PW *pw2) 468{ 469 int i; 470 isl_ctx *ctx; 471 472 if (!pw1 || !pw2) 473 goto error; 474 475 if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n) 476 return FN(PW,add_disjoint_aligned)(pw2, pw1); 477 478 ctx = isl_space_get_ctx(pw1->dim); 479#ifdef HAS_TYPE 480 if (pw1->type != pw2->type) 481 isl_die(ctx, isl_error_invalid, 482 "fold types don't match", goto error); 483#endif 484 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error); 485 486 if (FN(PW,IS_ZERO)(pw1)) { 487 FN(PW,free)(pw1); 488 return pw2; 489 } 490 491 if (FN(PW,IS_ZERO)(pw2)) { 492 FN(PW,free)(pw2); 493 return pw1; 494 } 495 496 pw1 = FN(PW,grow)(pw1, pw2->n); 497 if (!pw1) 498 goto error; 499 500 for (i = 0; i < pw2->n; ++i) 501 pw1 = FN(PW,add_piece)(pw1, 502 isl_set_copy(pw2->p[i].set), 503 FN(EL,copy)(pw2->p[i].FIELD)); 504 505 FN(PW,free)(pw2); 506 507 return pw1; 508error: 509 FN(PW,free)(pw1); 510 FN(PW,free)(pw2); 511 return NULL; 512} 513 514__isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2) 515{ 516 return FN(PW,align_params_pw_pw_and)(pw1, pw2, 517 &FN(PW,add_disjoint_aligned)); 518} 519 520/* This function is currently only used from isl_aff.c 521 */ 522static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1, 523 __isl_take PW *pw2, __isl_take isl_space *space, 524 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) 525 __attribute__ ((unused)); 526 527/* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains. 528 * The result of "fn" (and therefore also of this function) lives in "space". 529 */ 530static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1, 531 __isl_take PW *pw2, __isl_take isl_space *space, 532 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) 533{ 534 int i, j, n; 535 PW *res = NULL; 536 537 if (!pw1 || !pw2) 538 goto error; 539 540 n = pw1->n * pw2->n; 541#ifdef HAS_TYPE 542 res = FN(PW,alloc_size)(isl_space_copy(space), pw1->type, n); 543#else 544 res = FN(PW,alloc_size)(isl_space_copy(space), n); 545#endif 546 547 for (i = 0; i < pw1->n; ++i) { 548 for (j = 0; j < pw2->n; ++j) { 549 isl_set *common; 550 EL *res_ij; 551 int empty; 552 553 common = isl_set_intersect( 554 isl_set_copy(pw1->p[i].set), 555 isl_set_copy(pw2->p[j].set)); 556 empty = isl_set_plain_is_empty(common); 557 if (empty < 0 || empty) { 558 isl_set_free(common); 559 if (empty < 0) 560 goto error; 561 continue; 562 } 563 564 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD), 565 FN(EL,copy)(pw2->p[j].FIELD)); 566 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common)); 567 568 res = FN(PW,add_piece)(res, common, res_ij); 569 } 570 } 571 572 isl_space_free(space); 573 FN(PW,free)(pw1); 574 FN(PW,free)(pw2); 575 return res; 576error: 577 isl_space_free(space); 578 FN(PW,free)(pw1); 579 FN(PW,free)(pw2); 580 FN(PW,free)(res); 581 return NULL; 582} 583 584/* This function is currently only used from isl_aff.c 585 */ 586static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1, 587 __isl_take PW *pw2, 588 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) 589 __attribute__ ((unused)); 590 591/* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains. 592 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2". 593 */ 594static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1, 595 __isl_take PW *pw2, 596 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) 597{ 598 isl_space *space; 599 600 if (!pw1 || !pw2) 601 goto error; 602 603 space = isl_space_copy(pw1->dim); 604 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn); 605error: 606 FN(PW,free)(pw1); 607 FN(PW,free)(pw2); 608 return NULL; 609} 610 611#ifndef NO_NEG 612__isl_give PW *FN(PW,neg)(__isl_take PW *pw) 613{ 614 int i; 615 616 if (!pw) 617 return NULL; 618 619 if (FN(PW,IS_ZERO)(pw)) 620 return pw; 621 622 pw = FN(PW,cow)(pw); 623 if (!pw) 624 return NULL; 625 626 for (i = 0; i < pw->n; ++i) { 627 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD); 628 if (!pw->p[i].FIELD) 629 return FN(PW,free)(pw); 630 } 631 632 return pw; 633} 634 635__isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2) 636{ 637 return FN(PW,add)(pw1, FN(PW,neg)(pw2)); 638} 639#endif 640 641#ifndef NO_EVAL 642__isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw, 643 __isl_take isl_point *pnt) 644{ 645 int i; 646 int found = 0; 647 isl_ctx *ctx; 648 isl_space *pnt_dim = NULL; 649 isl_qpolynomial *qp; 650 651 if (!pw || !pnt) 652 goto error; 653 ctx = isl_point_get_ctx(pnt); 654 pnt_dim = isl_point_get_space(pnt); 655 isl_assert(ctx, isl_space_is_domain_internal(pnt_dim, pw->dim), 656 goto error); 657 658 for (i = 0; i < pw->n; ++i) { 659 found = isl_set_contains_point(pw->p[i].set, pnt); 660 if (found < 0) 661 goto error; 662 if (found) 663 break; 664 } 665 if (found) 666 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD), 667 isl_point_copy(pnt)); 668 else 669 qp = isl_qpolynomial_zero_on_domain(FN(PW,get_domain_space)(pw)); 670 FN(PW,free)(pw); 671 isl_space_free(pnt_dim); 672 isl_point_free(pnt); 673 return qp; 674error: 675 FN(PW,free)(pw); 676 isl_space_free(pnt_dim); 677 isl_point_free(pnt); 678 return NULL; 679} 680#endif 681 682__isl_give isl_set *FN(PW,domain)(__isl_take PW *pw) 683{ 684 int i; 685 isl_set *dom; 686 687 if (!pw) 688 return NULL; 689 690 dom = isl_set_empty(FN(PW,get_domain_space)(pw)); 691 for (i = 0; i < pw->n; ++i) 692 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set)); 693 694 FN(PW,free)(pw); 695 696 return dom; 697} 698 699/* Exploit the equalities in the domain of piece "i" of "pw" 700 * to simplify the associated function. 701 * If the domain of piece "i" is empty, then remove it entirely, 702 * replacing it with the final piece. 703 */ 704static int FN(PW,exploit_equalities_and_remove_if_empty)(__isl_keep PW *pw, 705 int i) 706{ 707 isl_basic_set *aff; 708 int empty = isl_set_plain_is_empty(pw->p[i].set); 709 710 if (empty < 0) 711 return -1; 712 if (empty) { 713 isl_set_free(pw->p[i].set); 714 FN(EL,free)(pw->p[i].FIELD); 715 if (i != pw->n - 1) 716 pw->p[i] = pw->p[pw->n - 1]; 717 pw->n--; 718 719 return 0; 720 } 721 722 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set)); 723 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD, aff); 724 if (!pw->p[i].FIELD) 725 return -1; 726 727 return 0; 728} 729 730/* Restrict the domain of "pw" by combining each cell 731 * with "set" through a call to "fn", where "fn" may be 732 * isl_set_intersect or isl_set_intersect_params. 733 */ 734static __isl_give PW *FN(PW,intersect_aligned)(__isl_take PW *pw, 735 __isl_take isl_set *set, 736 __isl_give isl_set *(*fn)(__isl_take isl_set *set1, 737 __isl_take isl_set *set2)) 738{ 739 int i; 740 741 if (!pw || !set) 742 goto error; 743 744 if (pw->n == 0) { 745 isl_set_free(set); 746 return pw; 747 } 748 749 pw = FN(PW,cow)(pw); 750 if (!pw) 751 goto error; 752 753 for (i = pw->n - 1; i >= 0; --i) { 754 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set)); 755 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0) 756 goto error; 757 } 758 759 isl_set_free(set); 760 return pw; 761error: 762 isl_set_free(set); 763 FN(PW,free)(pw); 764 return NULL; 765} 766 767static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw, 768 __isl_take isl_set *set) 769{ 770 return FN(PW,intersect_aligned)(pw, set, &isl_set_intersect); 771} 772 773__isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw, 774 __isl_take isl_set *context) 775{ 776 return FN(PW,align_params_pw_set_and)(pw, context, 777 &FN(PW,intersect_domain_aligned)); 778} 779 780static __isl_give PW *FN(PW,intersect_params_aligned)(__isl_take PW *pw, 781 __isl_take isl_set *set) 782{ 783 return FN(PW,intersect_aligned)(pw, set, &isl_set_intersect_params); 784} 785 786/* Intersect the domain of "pw" with the parameter domain "context". 787 */ 788__isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw, 789 __isl_take isl_set *context) 790{ 791 return FN(PW,align_params_pw_set_and)(pw, context, 792 &FN(PW,intersect_params_aligned)); 793} 794 795static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw, 796 __isl_take isl_set *context, 797 __isl_give EL *(*fn_el)(__isl_take EL *el, 798 __isl_take isl_set *set), 799 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set, 800 __isl_take isl_basic_set *bset)) 801{ 802 int i; 803 isl_basic_set *hull = NULL; 804 805 if (!pw || !context) 806 goto error; 807 808 if (pw->n == 0) { 809 isl_set_free(context); 810 return pw; 811 } 812 813 if (!isl_space_match(pw->dim, isl_dim_param, 814 context->dim, isl_dim_param)) { 815 pw = FN(PW,align_params)(pw, isl_set_get_space(context)); 816 context = isl_set_align_params(context, FN(PW,get_space)(pw)); 817 } 818 819 context = isl_set_compute_divs(context); 820 hull = isl_set_simple_hull(isl_set_copy(context)); 821 822 pw = FN(PW,cow)(pw); 823 if (!pw) 824 goto error; 825 826 for (i = pw->n - 1; i >= 0; --i) { 827 isl_set *set_i; 828 int empty; 829 830 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set), 831 isl_set_copy(context)); 832 empty = isl_set_plain_is_empty(set_i); 833 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i); 834 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull)); 835 if (!pw->p[i].FIELD || !pw->p[i].set) 836 goto error; 837 if (empty) { 838 isl_set_free(pw->p[i].set); 839 FN(EL,free)(pw->p[i].FIELD); 840 if (i != pw->n - 1) 841 pw->p[i] = pw->p[pw->n - 1]; 842 pw->n--; 843 } 844 } 845 846 isl_basic_set_free(hull); 847 isl_set_free(context); 848 849 return pw; 850error: 851 FN(PW,free)(pw); 852 isl_basic_set_free(hull); 853 isl_set_free(context); 854 return NULL; 855} 856 857static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw, 858 __isl_take isl_set *set) 859{ 860 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist), 861 &isl_set_gist_basic_set); 862} 863 864__isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context) 865{ 866 return FN(PW,align_params_pw_set_and)(pw, context, 867 &FN(PW,gist_domain_aligned)); 868} 869 870static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw, 871 __isl_take isl_set *set) 872{ 873 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params), 874 &isl_set_gist_params_basic_set); 875} 876 877__isl_give PW *FN(PW,gist_params)(__isl_take PW *pw, 878 __isl_take isl_set *context) 879{ 880 return FN(PW,align_params_pw_set_and)(pw, context, 881 &FN(PW,gist_params_aligned)); 882} 883 884__isl_give PW *FN(PW,coalesce)(__isl_take PW *pw) 885{ 886 int i, j; 887 888 if (!pw) 889 return NULL; 890 if (pw->n == 0) 891 return pw; 892 893 for (i = pw->n - 1; i >= 0; --i) { 894 for (j = i - 1; j >= 0; --j) { 895 if (!FN(EL,plain_is_equal)(pw->p[i].FIELD, 896 pw->p[j].FIELD)) 897 continue; 898 pw->p[j].set = isl_set_union(pw->p[j].set, 899 pw->p[i].set); 900 FN(EL,free)(pw->p[i].FIELD); 901 if (i != pw->n - 1) 902 pw->p[i] = pw->p[pw->n - 1]; 903 pw->n--; 904 break; 905 } 906 if (j >= 0) 907 continue; 908 pw->p[i].set = isl_set_coalesce(pw->p[i].set); 909 if (!pw->p[i].set) 910 goto error; 911 } 912 913 return pw; 914error: 915 FN(PW,free)(pw); 916 return NULL; 917} 918 919isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw) 920{ 921 return pw ? isl_space_get_ctx(pw->dim) : NULL; 922} 923 924#ifndef NO_INVOLVES_DIMS 925int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type, 926 unsigned first, unsigned n) 927{ 928 int i; 929 enum isl_dim_type set_type; 930 931 if (!pw) 932 return -1; 933 if (pw->n == 0 || n == 0) 934 return 0; 935 936 set_type = type == isl_dim_in ? isl_dim_set : type; 937 938 for (i = 0; i < pw->n; ++i) { 939 int involves = FN(EL,involves_dims)(pw->p[i].FIELD, 940 type, first, n); 941 if (involves < 0 || involves) 942 return involves; 943 involves = isl_set_involves_dims(pw->p[i].set, 944 set_type, first, n); 945 if (involves < 0 || involves) 946 return involves; 947 } 948 return 0; 949} 950#endif 951 952__isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw, 953 enum isl_dim_type type, unsigned pos, const char *s) 954{ 955 int i; 956 enum isl_dim_type set_type; 957 958 pw = FN(PW,cow)(pw); 959 if (!pw) 960 return NULL; 961 962 set_type = type == isl_dim_in ? isl_dim_set : type; 963 964 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s); 965 if (!pw->dim) 966 goto error; 967 968 for (i = 0; i < pw->n; ++i) { 969 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set, 970 set_type, pos, s); 971 if (!pw->p[i].set) 972 goto error; 973 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s); 974 if (!pw->p[i].FIELD) 975 goto error; 976 } 977 978 return pw; 979error: 980 FN(PW,free)(pw); 981 return NULL; 982} 983 984#ifndef NO_DROP_DIMS 985__isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw, 986 enum isl_dim_type type, unsigned first, unsigned n) 987{ 988 int i; 989 enum isl_dim_type set_type; 990 991 if (!pw) 992 return NULL; 993 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type)) 994 return pw; 995 996 set_type = type == isl_dim_in ? isl_dim_set : type; 997 998 pw = FN(PW,cow)(pw); 999 if (!pw) 1000 return NULL; 1001 pw->dim = isl_space_drop_dims(pw->dim, type, first, n); 1002 if (!pw->dim) 1003 goto error; 1004 for (i = 0; i < pw->n; ++i) { 1005 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n); 1006 if (!pw->p[i].FIELD) 1007 goto error; 1008 if (type == isl_dim_out) 1009 continue; 1010 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n); 1011 if (!pw->p[i].set) 1012 goto error; 1013 } 1014 1015 return pw; 1016error: 1017 FN(PW,free)(pw); 1018 return NULL; 1019} 1020 1021/* This function is very similar to drop_dims. 1022 * The only difference is that the cells may still involve 1023 * the specified dimensions. They are removed using 1024 * isl_set_project_out instead of isl_set_drop. 1025 */ 1026__isl_give PW *FN(PW,project_out)(__isl_take PW *pw, 1027 enum isl_dim_type type, unsigned first, unsigned n) 1028{ 1029 int i; 1030 enum isl_dim_type set_type; 1031 1032 if (!pw) 1033 return NULL; 1034 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type)) 1035 return pw; 1036 1037 set_type = type == isl_dim_in ? isl_dim_set : type; 1038 1039 pw = FN(PW,cow)(pw); 1040 if (!pw) 1041 return NULL; 1042 pw->dim = isl_space_drop_dims(pw->dim, type, first, n); 1043 if (!pw->dim) 1044 goto error; 1045 for (i = 0; i < pw->n; ++i) { 1046 pw->p[i].set = isl_set_project_out(pw->p[i].set, 1047 set_type, first, n); 1048 if (!pw->p[i].set) 1049 goto error; 1050 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n); 1051 if (!pw->p[i].FIELD) 1052 goto error; 1053 } 1054 1055 return pw; 1056error: 1057 FN(PW,free)(pw); 1058 return NULL; 1059} 1060 1061/* Project the domain of pw onto its parameter space. 1062 */ 1063__isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw) 1064{ 1065 isl_space *space; 1066 unsigned n; 1067 1068 n = FN(PW,dim)(pw, isl_dim_in); 1069 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n); 1070 space = FN(PW,get_domain_space)(pw); 1071 space = isl_space_params(space); 1072 pw = FN(PW,reset_domain_space)(pw, space); 1073 return pw; 1074} 1075#endif 1076 1077#ifndef NO_INSERT_DIMS 1078__isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type, 1079 unsigned first, unsigned n) 1080{ 1081 int i; 1082 enum isl_dim_type set_type; 1083 1084 if (!pw) 1085 return NULL; 1086 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type)) 1087 return pw; 1088 1089 set_type = type == isl_dim_in ? isl_dim_set : type; 1090 1091 pw = FN(PW,cow)(pw); 1092 if (!pw) 1093 return NULL; 1094 1095 pw->dim = isl_space_insert_dims(pw->dim, type, first, n); 1096 if (!pw->dim) 1097 goto error; 1098 1099 for (i = 0; i < pw->n; ++i) { 1100 pw->p[i].set = isl_set_insert_dims(pw->p[i].set, 1101 set_type, first, n); 1102 if (!pw->p[i].set) 1103 goto error; 1104 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD, 1105 type, first, n); 1106 if (!pw->p[i].FIELD) 1107 goto error; 1108 } 1109 1110 return pw; 1111error: 1112 FN(PW,free)(pw); 1113 return NULL; 1114} 1115#endif 1116 1117__isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw, 1118 enum isl_dim_type type, unsigned pos, isl_int v) 1119{ 1120 int i; 1121 1122 if (!pw) 1123 return NULL; 1124 1125 if (type == isl_dim_in) 1126 type = isl_dim_set; 1127 1128 pw = FN(PW,cow)(pw); 1129 if (!pw) 1130 return NULL; 1131 for (i = 0; i < pw->n; ++i) { 1132 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v); 1133 if (FN(PW,exploit_equalities_and_remove_if_empty)(pw, i) < 0) 1134 return FN(PW,free)(pw); 1135 } 1136 1137 return pw; 1138} 1139 1140/* Fix the value of the variable at position "pos" of type "type" of "pw" 1141 * to be equal to "v". 1142 */ 1143__isl_give PW *FN(PW,fix_val)(__isl_take PW *pw, 1144 enum isl_dim_type type, unsigned pos, __isl_take isl_val *v) 1145{ 1146 if (!v) 1147 return FN(PW,free)(pw); 1148 if (!isl_val_is_int(v)) 1149 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid, 1150 "expecting integer value", goto error); 1151 1152 pw = FN(PW,fix_dim)(pw, type, pos, v->n); 1153 isl_val_free(v); 1154 1155 return pw; 1156error: 1157 isl_val_free(v); 1158 return FN(PW,free)(pw); 1159} 1160 1161unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type) 1162{ 1163 return pw ? isl_space_dim(pw->dim, type) : 0; 1164} 1165 1166__isl_give PW *FN(PW,split_dims)(__isl_take PW *pw, 1167 enum isl_dim_type type, unsigned first, unsigned n) 1168{ 1169 int i; 1170 1171 if (!pw) 1172 return NULL; 1173 if (n == 0) 1174 return pw; 1175 1176 if (type == isl_dim_in) 1177 type = isl_dim_set; 1178 1179 pw = FN(PW,cow)(pw); 1180 if (!pw) 1181 return NULL; 1182 if (!pw->dim) 1183 goto error; 1184 for (i = 0; i < pw->n; ++i) { 1185 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n); 1186 if (!pw->p[i].set) 1187 goto error; 1188 } 1189 1190 return pw; 1191error: 1192 FN(PW,free)(pw); 1193 return NULL; 1194} 1195 1196#ifndef NO_OPT 1197/* Compute the maximal value attained by the piecewise quasipolynomial 1198 * on its domain or zero if the domain is empty. 1199 * In the worst case, the domain is scanned completely, 1200 * so the domain is assumed to be bounded. 1201 */ 1202__isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max) 1203{ 1204 int i; 1205 isl_qpolynomial *opt; 1206 1207 if (!pw) 1208 return NULL; 1209 1210 if (pw->n == 0) { 1211 isl_space *dim = isl_space_copy(pw->dim); 1212 FN(PW,free)(pw); 1213 return isl_qpolynomial_zero_on_domain(isl_space_domain(dim)); 1214 } 1215 1216 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD), 1217 isl_set_copy(pw->p[0].set), max); 1218 for (i = 1; i < pw->n; ++i) { 1219 isl_qpolynomial *opt_i; 1220 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD), 1221 isl_set_copy(pw->p[i].set), max); 1222 if (max) 1223 opt = isl_qpolynomial_max_cst(opt, opt_i); 1224 else 1225 opt = isl_qpolynomial_min_cst(opt, opt_i); 1226 } 1227 1228 FN(PW,free)(pw); 1229 return opt; 1230} 1231 1232__isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw) 1233{ 1234 return FN(PW,opt)(pw, 1); 1235} 1236 1237__isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw) 1238{ 1239 return FN(PW,opt)(pw, 0); 1240} 1241#endif 1242 1243__isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw) 1244{ 1245 return pw ? isl_space_copy(pw->dim) : NULL; 1246} 1247 1248__isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw) 1249{ 1250 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL; 1251} 1252 1253#ifndef NO_RESET_DIM 1254/* Reset the space of "pw". Since we don't know if the elements 1255 * represent the spaces themselves or their domains, we pass along 1256 * both when we call their reset_space_and_domain. 1257 */ 1258static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw, 1259 __isl_take isl_space *space, __isl_take isl_space *domain) 1260{ 1261 int i; 1262 1263 pw = FN(PW,cow)(pw); 1264 if (!pw || !space || !domain) 1265 goto error; 1266 1267 for (i = 0; i < pw->n; ++i) { 1268 pw->p[i].set = isl_set_reset_space(pw->p[i].set, 1269 isl_space_copy(domain)); 1270 if (!pw->p[i].set) 1271 goto error; 1272 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD, 1273 isl_space_copy(space), isl_space_copy(domain)); 1274 if (!pw->p[i].FIELD) 1275 goto error; 1276 } 1277 1278 isl_space_free(domain); 1279 1280 isl_space_free(pw->dim); 1281 pw->dim = space; 1282 1283 return pw; 1284error: 1285 isl_space_free(domain); 1286 isl_space_free(space); 1287 FN(PW,free)(pw); 1288 return NULL; 1289} 1290 1291__isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw, 1292 __isl_take isl_space *domain) 1293{ 1294 isl_space *space; 1295 1296 space = isl_space_extend_domain_with_range(isl_space_copy(domain), 1297 FN(PW,get_space)(pw)); 1298 return FN(PW,reset_space_and_domain)(pw, space, domain); 1299} 1300 1301__isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim) 1302{ 1303 isl_space *domain; 1304 1305 domain = isl_space_domain(isl_space_copy(dim)); 1306 return FN(PW,reset_space_and_domain)(pw, dim, domain); 1307} 1308 1309__isl_give PW *FN(PW,set_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type, 1310 __isl_take isl_id *id) 1311{ 1312 isl_space *space; 1313 1314 pw = FN(PW,cow)(pw); 1315 if (!pw) 1316 return isl_id_free(id); 1317 1318 space = FN(PW,get_space)(pw); 1319 space = isl_space_set_tuple_id(space, type, id); 1320 1321 return FN(PW,reset_space)(pw, space); 1322} 1323 1324__isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw, 1325 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) 1326{ 1327 pw = FN(PW,cow)(pw); 1328 if (!pw) 1329 return isl_id_free(id); 1330 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id); 1331 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim)); 1332} 1333#endif 1334 1335int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2) 1336{ 1337 if (!pw1 || !pw2) 1338 return -1; 1339 1340 return isl_space_is_equal(pw1->dim, pw2->dim); 1341} 1342 1343#ifndef NO_MORPH 1344__isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw, 1345 __isl_take isl_morph *morph) 1346{ 1347 int i; 1348 isl_ctx *ctx; 1349 1350 if (!pw || !morph) 1351 goto error; 1352 1353 ctx = isl_space_get_ctx(pw->dim); 1354 isl_assert(ctx, isl_space_is_domain_internal(morph->dom->dim, pw->dim), 1355 goto error); 1356 1357 pw = FN(PW,cow)(pw); 1358 if (!pw) 1359 goto error; 1360 pw->dim = isl_space_extend_domain_with_range( 1361 isl_space_copy(morph->ran->dim), pw->dim); 1362 if (!pw->dim) 1363 goto error; 1364 1365 for (i = 0; i < pw->n; ++i) { 1366 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set); 1367 if (!pw->p[i].set) 1368 goto error; 1369 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD, 1370 isl_morph_copy(morph)); 1371 if (!pw->p[i].FIELD) 1372 goto error; 1373 } 1374 1375 isl_morph_free(morph); 1376 1377 return pw; 1378error: 1379 FN(PW,free)(pw); 1380 isl_morph_free(morph); 1381 return NULL; 1382} 1383#endif 1384 1385int FN(PW,n_piece)(__isl_keep PW *pw) 1386{ 1387 return pw ? pw->n : 0; 1388} 1389 1390int FN(PW,foreach_piece)(__isl_keep PW *pw, 1391 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user), 1392 void *user) 1393{ 1394 int i; 1395 1396 if (!pw) 1397 return -1; 1398 1399 for (i = 0; i < pw->n; ++i) 1400 if (fn(isl_set_copy(pw->p[i].set), 1401 FN(EL,copy)(pw->p[i].FIELD), user) < 0) 1402 return -1; 1403 1404 return 0; 1405} 1406 1407#ifndef NO_LIFT 1408static int any_divs(__isl_keep isl_set *set) 1409{ 1410 int i; 1411 1412 if (!set) 1413 return -1; 1414 1415 for (i = 0; i < set->n; ++i) 1416 if (set->p[i]->n_div > 0) 1417 return 1; 1418 1419 return 0; 1420} 1421 1422static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el, 1423 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, 1424 void *user), void *user) 1425{ 1426 int i; 1427 1428 if (!set || !el) 1429 goto error; 1430 1431 for (i = 0; i < set->n; ++i) { 1432 isl_set *lift; 1433 EL *copy; 1434 1435 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i])); 1436 lift = isl_set_lift(lift); 1437 1438 copy = FN(EL,copy)(el); 1439 copy = FN(EL,lift)(copy, isl_set_get_space(lift)); 1440 1441 if (fn(lift, copy, user) < 0) 1442 goto error; 1443 } 1444 1445 isl_set_free(set); 1446 FN(EL,free)(el); 1447 1448 return 0; 1449error: 1450 isl_set_free(set); 1451 FN(EL,free)(el); 1452 return -1; 1453} 1454 1455int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw, 1456 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, 1457 void *user), void *user) 1458{ 1459 int i; 1460 1461 if (!pw) 1462 return -1; 1463 1464 for (i = 0; i < pw->n; ++i) { 1465 isl_set *set; 1466 EL *el; 1467 1468 set = isl_set_copy(pw->p[i].set); 1469 el = FN(EL,copy)(pw->p[i].FIELD); 1470 if (!any_divs(set)) { 1471 if (fn(set, el, user) < 0) 1472 return -1; 1473 continue; 1474 } 1475 if (foreach_lifted_subset(set, el, fn, user) < 0) 1476 return -1; 1477 } 1478 1479 return 0; 1480} 1481#endif 1482 1483#ifndef NO_MOVE_DIMS 1484__isl_give PW *FN(PW,move_dims)(__isl_take PW *pw, 1485 enum isl_dim_type dst_type, unsigned dst_pos, 1486 enum isl_dim_type src_type, unsigned src_pos, unsigned n) 1487{ 1488 int i; 1489 1490 pw = FN(PW,cow)(pw); 1491 if (!pw) 1492 return NULL; 1493 1494 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n); 1495 if (!pw->dim) 1496 goto error; 1497 1498 for (i = 0; i < pw->n; ++i) { 1499 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD, 1500 dst_type, dst_pos, src_type, src_pos, n); 1501 if (!pw->p[i].FIELD) 1502 goto error; 1503 } 1504 1505 if (dst_type == isl_dim_in) 1506 dst_type = isl_dim_set; 1507 if (src_type == isl_dim_in) 1508 src_type = isl_dim_set; 1509 1510 for (i = 0; i < pw->n; ++i) { 1511 pw->p[i].set = isl_set_move_dims(pw->p[i].set, 1512 dst_type, dst_pos, 1513 src_type, src_pos, n); 1514 if (!pw->p[i].set) 1515 goto error; 1516 } 1517 1518 return pw; 1519error: 1520 FN(PW,free)(pw); 1521 return NULL; 1522} 1523#endif 1524 1525__isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v) 1526{ 1527 int i; 1528 1529 if (isl_int_is_one(v)) 1530 return pw; 1531 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) { 1532 PW *zero; 1533 isl_space *dim = FN(PW,get_space)(pw); 1534#ifdef HAS_TYPE 1535 zero = FN(PW,ZERO)(dim, pw->type); 1536#else 1537 zero = FN(PW,ZERO)(dim); 1538#endif 1539 FN(PW,free)(pw); 1540 return zero; 1541 } 1542 pw = FN(PW,cow)(pw); 1543 if (!pw) 1544 return NULL; 1545 if (pw->n == 0) 1546 return pw; 1547 1548#ifdef HAS_TYPE 1549 if (isl_int_is_neg(v)) 1550 pw->type = isl_fold_type_negate(pw->type); 1551#endif 1552 for (i = 0; i < pw->n; ++i) { 1553 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v); 1554 if (!pw->p[i].FIELD) 1555 goto error; 1556 } 1557 1558 return pw; 1559error: 1560 FN(PW,free)(pw); 1561 return NULL; 1562} 1563 1564/* Multiply the pieces of "pw" by "v" and return the result. 1565 */ 1566__isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v) 1567{ 1568 int i; 1569 1570 if (!pw || !v) 1571 goto error; 1572 1573 if (isl_val_is_one(v)) { 1574 isl_val_free(v); 1575 return pw; 1576 } 1577 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) { 1578 PW *zero; 1579 isl_space *space = FN(PW,get_space)(pw); 1580#ifdef HAS_TYPE 1581 zero = FN(PW,ZERO)(space, pw->type); 1582#else 1583 zero = FN(PW,ZERO)(space); 1584#endif 1585 FN(PW,free)(pw); 1586 isl_val_free(v); 1587 return zero; 1588 } 1589 if (pw->n == 0) { 1590 isl_val_free(v); 1591 return pw; 1592 } 1593 pw = FN(PW,cow)(pw); 1594 if (!pw) 1595 goto error; 1596 1597#ifdef HAS_TYPE 1598 if (isl_val_is_neg(v)) 1599 pw->type = isl_fold_type_negate(pw->type); 1600#endif 1601 for (i = 0; i < pw->n; ++i) { 1602 pw->p[i].FIELD = FN(EL,scale_val)(pw->p[i].FIELD, 1603 isl_val_copy(v)); 1604 if (!pw->p[i].FIELD) 1605 goto error; 1606 } 1607 1608 isl_val_free(v); 1609 return pw; 1610error: 1611 isl_val_free(v); 1612 FN(PW,free)(pw); 1613 return NULL; 1614} 1615 1616__isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v) 1617{ 1618 return FN(PW,mul_isl_int)(pw, v); 1619} 1620 1621static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2) 1622{ 1623 isl_set *set1 = *(isl_set * const *)p1; 1624 isl_set *set2 = *(isl_set * const *)p2; 1625 1626 return isl_set_plain_cmp(set1, set2); 1627} 1628 1629/* We normalize in place, but if anything goes wrong we need 1630 * to return NULL, so we need to make sure we don't change the 1631 * meaning of any possible other copies of map. 1632 */ 1633__isl_give PW *FN(PW,normalize)(__isl_take PW *pw) 1634{ 1635 int i, j; 1636 isl_set *set; 1637 1638 if (!pw) 1639 return NULL; 1640 for (i = 0; i < pw->n; ++i) { 1641 set = isl_set_normalize(isl_set_copy(pw->p[i].set)); 1642 if (!set) 1643 return FN(PW,free)(pw); 1644 isl_set_free(pw->p[i].set); 1645 pw->p[i].set = set; 1646 } 1647 qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp)); 1648 for (i = pw->n - 1; i >= 1; --i) { 1649 if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set)) 1650 continue; 1651 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD)) 1652 continue; 1653 set = isl_set_union(isl_set_copy(pw->p[i - 1].set), 1654 isl_set_copy(pw->p[i].set)); 1655 if (!set) 1656 return FN(PW,free)(pw); 1657 isl_set_free(pw->p[i].set); 1658 FN(EL,free)(pw->p[i].FIELD); 1659 isl_set_free(pw->p[i - 1].set); 1660 pw->p[i - 1].set = set; 1661 for (j = i + 1; j < pw->n; ++j) 1662 pw->p[j - 1] = pw->p[j]; 1663 pw->n--; 1664 } 1665 1666 return pw; 1667} 1668 1669/* Is pw1 obviously equal to pw2? 1670 * That is, do they have obviously identical cells and obviously identical 1671 * elements on each cell? 1672 */ 1673int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2) 1674{ 1675 int i; 1676 int equal; 1677 1678 if (!pw1 || !pw2) 1679 return -1; 1680 1681 if (pw1 == pw2) 1682 return 1; 1683 if (!isl_space_is_equal(pw1->dim, pw2->dim)) 1684 return 0; 1685 1686 pw1 = FN(PW,copy)(pw1); 1687 pw2 = FN(PW,copy)(pw2); 1688 pw1 = FN(PW,normalize)(pw1); 1689 pw2 = FN(PW,normalize)(pw2); 1690 if (!pw1 || !pw2) 1691 goto error; 1692 1693 equal = pw1->n == pw2->n; 1694 for (i = 0; equal && i < pw1->n; ++i) { 1695 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set); 1696 if (equal < 0) 1697 goto error; 1698 if (!equal) 1699 break; 1700 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD); 1701 if (equal < 0) 1702 goto error; 1703 } 1704 1705 FN(PW,free)(pw1); 1706 FN(PW,free)(pw2); 1707 return equal; 1708error: 1709 FN(PW,free)(pw1); 1710 FN(PW,free)(pw2); 1711 return -1; 1712} 1713 1714#ifndef NO_PULLBACK 1715static __isl_give PW *FN(PW,align_params_pw_multi_aff_and)(__isl_take PW *pw, 1716 __isl_take isl_multi_aff *ma, 1717 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_multi_aff *ma)) 1718{ 1719 isl_ctx *ctx; 1720 isl_space *ma_space; 1721 1722 ma_space = isl_multi_aff_get_space(ma); 1723 if (!pw || !ma || !ma_space) 1724 goto error; 1725 if (isl_space_match(pw->dim, isl_dim_param, ma_space, isl_dim_param)) { 1726 isl_space_free(ma_space); 1727 return fn(pw, ma); 1728 } 1729 ctx = FN(PW,get_ctx)(pw); 1730 if (!isl_space_has_named_params(pw->dim) || 1731 !isl_space_has_named_params(ma_space)) 1732 isl_die(ctx, isl_error_invalid, 1733 "unaligned unnamed parameters", goto error); 1734 pw = FN(PW,align_params)(pw, ma_space); 1735 ma = isl_multi_aff_align_params(ma, FN(PW,get_space)(pw)); 1736 return fn(pw, ma); 1737error: 1738 isl_space_free(ma_space); 1739 FN(PW,free)(pw); 1740 isl_multi_aff_free(ma); 1741 return NULL; 1742} 1743 1744static __isl_give PW *FN(PW,align_params_pw_pw_multi_aff_and)(__isl_take PW *pw, 1745 __isl_take isl_pw_multi_aff *pma, 1746 __isl_give PW *(*fn)(__isl_take PW *pw, 1747 __isl_take isl_pw_multi_aff *ma)) 1748{ 1749 isl_ctx *ctx; 1750 isl_space *pma_space; 1751 1752 pma_space = isl_pw_multi_aff_get_space(pma); 1753 if (!pw || !pma || !pma_space) 1754 goto error; 1755 if (isl_space_match(pw->dim, isl_dim_param, pma_space, isl_dim_param)) { 1756 isl_space_free(pma_space); 1757 return fn(pw, pma); 1758 } 1759 ctx = FN(PW,get_ctx)(pw); 1760 if (!isl_space_has_named_params(pw->dim) || 1761 !isl_space_has_named_params(pma_space)) 1762 isl_die(ctx, isl_error_invalid, 1763 "unaligned unnamed parameters", goto error); 1764 pw = FN(PW,align_params)(pw, pma_space); 1765 pma = isl_pw_multi_aff_align_params(pma, FN(PW,get_space)(pw)); 1766 return fn(pw, pma); 1767error: 1768 isl_space_free(pma_space); 1769 FN(PW,free)(pw); 1770 isl_pw_multi_aff_free(pma); 1771 return NULL; 1772} 1773 1774/* Compute the pullback of "pw" by the function represented by "ma". 1775 * In other words, plug in "ma" in "pw". 1776 */ 1777static __isl_give PW *FN(PW,pullback_multi_aff_aligned)(__isl_take PW *pw, 1778 __isl_take isl_multi_aff *ma) 1779{ 1780 int i; 1781 isl_space *space = NULL; 1782 1783 ma = isl_multi_aff_align_divs(ma); 1784 pw = FN(PW,cow)(pw); 1785 if (!pw || !ma) 1786 goto error; 1787 1788 space = isl_space_join(isl_multi_aff_get_space(ma), 1789 FN(PW,get_space)(pw)); 1790 1791 for (i = 0; i < pw->n; ++i) { 1792 pw->p[i].set = isl_set_preimage_multi_aff(pw->p[i].set, 1793 isl_multi_aff_copy(ma)); 1794 if (!pw->p[i].set) 1795 goto error; 1796 pw->p[i].FIELD = FN(EL,pullback_multi_aff)(pw->p[i].FIELD, 1797 isl_multi_aff_copy(ma)); 1798 if (!pw->p[i].FIELD) 1799 goto error; 1800 } 1801 1802 pw = FN(PW,reset_space)(pw, space); 1803 isl_multi_aff_free(ma); 1804 return pw; 1805error: 1806 isl_space_free(space); 1807 isl_multi_aff_free(ma); 1808 FN(PW,free)(pw); 1809 return NULL; 1810} 1811 1812__isl_give PW *FN(PW,pullback_multi_aff)(__isl_take PW *pw, 1813 __isl_take isl_multi_aff *ma) 1814{ 1815 return FN(PW,align_params_pw_multi_aff_and)(pw, ma, 1816 &FN(PW,pullback_multi_aff_aligned)); 1817} 1818 1819/* Compute the pullback of "pw" by the function represented by "pma". 1820 * In other words, plug in "pma" in "pw". 1821 */ 1822static __isl_give PW *FN(PW,pullback_pw_multi_aff_aligned)(__isl_take PW *pw, 1823 __isl_take isl_pw_multi_aff *pma) 1824{ 1825 int i; 1826 PW *res; 1827 1828 if (!pma) 1829 goto error; 1830 1831 if (pma->n == 0) { 1832 isl_space *space; 1833 space = isl_space_join(isl_pw_multi_aff_get_space(pma), 1834 FN(PW,get_space)(pw)); 1835 isl_pw_multi_aff_free(pma); 1836 res = FN(PW,empty)(space); 1837 FN(PW,free)(pw); 1838 return res; 1839 } 1840 1841 res = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw), 1842 isl_multi_aff_copy(pma->p[0].maff)); 1843 res = FN(PW,intersect_domain)(res, isl_set_copy(pma->p[0].set)); 1844 1845 for (i = 1; i < pma->n; ++i) { 1846 PW *res_i; 1847 1848 res_i = FN(PW,pullback_multi_aff)(FN(PW,copy)(pw), 1849 isl_multi_aff_copy(pma->p[i].maff)); 1850 res_i = FN(PW,intersect_domain)(res_i, 1851 isl_set_copy(pma->p[i].set)); 1852 res = FN(PW,add_disjoint)(res, res_i); 1853 } 1854 1855 isl_pw_multi_aff_free(pma); 1856 FN(PW,free)(pw); 1857 return res; 1858error: 1859 isl_pw_multi_aff_free(pma); 1860 FN(PW,free)(pw); 1861 return NULL; 1862} 1863 1864__isl_give PW *FN(PW,pullback_pw_multi_aff)(__isl_take PW *pw, 1865 __isl_take isl_pw_multi_aff *pma) 1866{ 1867 return FN(PW,align_params_pw_pw_multi_aff_and)(pw, pma, 1868 &FN(PW,pullback_pw_multi_aff_aligned)); 1869} 1870#endif 1871