1/* 2 * Copyright 2010 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_union_map_private.h> 14#include <isl_polynomial_private.h> 15#include <isl_point_private.h> 16#include <isl_space_private.h> 17#include <isl/lp.h> 18#include <isl/seq.h> 19#include <isl_mat_private.h> 20#include <isl_val_private.h> 21#include <isl_config.h> 22 23enum isl_fold isl_fold_type_negate(enum isl_fold type) 24{ 25 switch (type) { 26 case isl_fold_min: 27 return isl_fold_max; 28 case isl_fold_max: 29 return isl_fold_min; 30 case isl_fold_list: 31 return isl_fold_list; 32 } 33 34 isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort()); 35} 36 37static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc( 38 enum isl_fold type, __isl_take isl_space *dim, int n) 39{ 40 isl_qpolynomial_fold *fold; 41 42 if (!dim) 43 goto error; 44 45 isl_assert(dim->ctx, n >= 0, goto error); 46 fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold, 47 sizeof(struct isl_qpolynomial_fold) + 48 (n - 1) * sizeof(struct isl_qpolynomial *)); 49 if (!fold) 50 goto error; 51 52 fold->ref = 1; 53 fold->size = n; 54 fold->n = 0; 55 fold->type = type; 56 fold->dim = dim; 57 58 return fold; 59error: 60 isl_space_free(dim); 61 return NULL; 62} 63 64isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold) 65{ 66 return fold ? fold->dim->ctx : NULL; 67} 68 69__isl_give isl_space *isl_qpolynomial_fold_get_domain_space( 70 __isl_keep isl_qpolynomial_fold *fold) 71{ 72 return fold ? isl_space_copy(fold->dim) : NULL; 73} 74 75__isl_give isl_space *isl_qpolynomial_fold_get_space( 76 __isl_keep isl_qpolynomial_fold *fold) 77{ 78 isl_space *space; 79 if (!fold) 80 return NULL; 81 space = isl_space_copy(fold->dim); 82 space = isl_space_from_domain(space); 83 space = isl_space_add_dims(space, isl_dim_out, 1); 84 return space; 85} 86 87__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_domain_space( 88 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim) 89{ 90 int i; 91 92 fold = isl_qpolynomial_fold_cow(fold); 93 if (!fold || !dim) 94 goto error; 95 96 for (i = 0; i < fold->n; ++i) { 97 fold->qp[i] = isl_qpolynomial_reset_domain_space(fold->qp[i], 98 isl_space_copy(dim)); 99 if (!fold->qp[i]) 100 goto error; 101 } 102 103 isl_space_free(fold->dim); 104 fold->dim = dim; 105 106 return fold; 107error: 108 isl_qpolynomial_fold_free(fold); 109 isl_space_free(dim); 110 return NULL; 111} 112 113/* Reset the space of "fold". This function is called from isl_pw_templ.c 114 * and doesn't know if the space of an element object is represented 115 * directly or through its domain. It therefore passes along both. 116 */ 117__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space_and_domain( 118 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space, 119 __isl_take isl_space *domain) 120{ 121 isl_space_free(space); 122 return isl_qpolynomial_fold_reset_domain_space(fold, domain); 123} 124 125int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold, 126 enum isl_dim_type type, unsigned first, unsigned n) 127{ 128 int i; 129 130 if (!fold) 131 return -1; 132 if (fold->n == 0 || n == 0) 133 return 0; 134 135 for (i = 0; i < fold->n; ++i) { 136 int involves = isl_qpolynomial_involves_dims(fold->qp[i], 137 type, first, n); 138 if (involves < 0 || involves) 139 return involves; 140 } 141 return 0; 142} 143 144__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name( 145 __isl_take isl_qpolynomial_fold *fold, 146 enum isl_dim_type type, unsigned pos, const char *s) 147{ 148 int i; 149 150 fold = isl_qpolynomial_fold_cow(fold); 151 if (!fold) 152 return NULL; 153 fold->dim = isl_space_set_dim_name(fold->dim, type, pos, s); 154 if (!fold->dim) 155 goto error; 156 157 for (i = 0; i < fold->n; ++i) { 158 fold->qp[i] = isl_qpolynomial_set_dim_name(fold->qp[i], 159 type, pos, s); 160 if (!fold->qp[i]) 161 goto error; 162 } 163 164 return fold; 165error: 166 isl_qpolynomial_fold_free(fold); 167 return NULL; 168} 169 170__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims( 171 __isl_take isl_qpolynomial_fold *fold, 172 enum isl_dim_type type, unsigned first, unsigned n) 173{ 174 int i; 175 enum isl_dim_type set_type; 176 177 if (!fold) 178 return NULL; 179 if (n == 0) 180 return fold; 181 182 set_type = type == isl_dim_in ? isl_dim_set : type; 183 184 fold = isl_qpolynomial_fold_cow(fold); 185 if (!fold) 186 return NULL; 187 fold->dim = isl_space_drop_dims(fold->dim, set_type, first, n); 188 if (!fold->dim) 189 goto error; 190 191 for (i = 0; i < fold->n; ++i) { 192 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i], 193 type, first, n); 194 if (!fold->qp[i]) 195 goto error; 196 } 197 198 return fold; 199error: 200 isl_qpolynomial_fold_free(fold); 201 return NULL; 202} 203 204__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims( 205 __isl_take isl_qpolynomial_fold *fold, 206 enum isl_dim_type type, unsigned first, unsigned n) 207{ 208 int i; 209 210 if (!fold) 211 return NULL; 212 if (n == 0 && !isl_space_is_named_or_nested(fold->dim, type)) 213 return fold; 214 215 fold = isl_qpolynomial_fold_cow(fold); 216 if (!fold) 217 return NULL; 218 fold->dim = isl_space_insert_dims(fold->dim, type, first, n); 219 if (!fold->dim) 220 goto error; 221 222 for (i = 0; i < fold->n; ++i) { 223 fold->qp[i] = isl_qpolynomial_insert_dims(fold->qp[i], 224 type, first, n); 225 if (!fold->qp[i]) 226 goto error; 227 } 228 229 return fold; 230error: 231 isl_qpolynomial_fold_free(fold); 232 return NULL; 233} 234 235static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp) 236{ 237 struct isl_upoly_cst *cst; 238 239 cst = isl_upoly_as_cst(qp->upoly); 240 if (!cst) 241 return 0; 242 243 return isl_int_sgn(cst->n) < 0 ? -1 : 1; 244} 245 246static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set, 247 __isl_keep isl_qpolynomial *qp) 248{ 249 enum isl_lp_result res; 250 isl_vec *aff; 251 isl_int opt; 252 int sgn = 0; 253 254 aff = isl_qpolynomial_extract_affine(qp); 255 if (!aff) 256 return 0; 257 258 isl_int_init(opt); 259 260 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0], 261 &opt, NULL, NULL); 262 if (res == isl_lp_error) 263 goto done; 264 if (res == isl_lp_empty || 265 (res == isl_lp_ok && !isl_int_is_neg(opt))) { 266 sgn = 1; 267 goto done; 268 } 269 270 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0], 271 &opt, NULL, NULL); 272 if (res == isl_lp_ok && !isl_int_is_pos(opt)) 273 sgn = -1; 274 275done: 276 isl_int_clear(opt); 277 isl_vec_free(aff); 278 return sgn; 279} 280 281/* Determine, if possible, the sign of the quasipolynomial "qp" on 282 * the domain "set". 283 * 284 * If qp is a constant, then the problem is trivial. 285 * If qp is linear, then we check if the minimum of the corresponding 286 * affine constraint is non-negative or if the maximum is non-positive. 287 * 288 * Otherwise, we check if the outermost variable "v" has a lower bound "l" 289 * in "set". If so, we write qp(v,v') as 290 * 291 * q(v,v') * (v - l) + r(v') 292 * 293 * if q(v,v') and r(v') have the same known sign, then the original 294 * quasipolynomial has the same sign as well. 295 * 296 * Return 297 * -1 if qp <= 0 298 * 1 if qp >= 0 299 * 0 if unknown 300 */ 301static int isl_qpolynomial_sign(__isl_keep isl_set *set, 302 __isl_keep isl_qpolynomial *qp) 303{ 304 int d; 305 int i; 306 int is; 307 struct isl_upoly_rec *rec; 308 isl_vec *v; 309 isl_int l; 310 enum isl_lp_result res; 311 int sgn = 0; 312 313 is = isl_qpolynomial_is_cst(qp, NULL, NULL); 314 if (is < 0) 315 return 0; 316 if (is) 317 return isl_qpolynomial_cst_sign(qp); 318 319 is = isl_qpolynomial_is_affine(qp); 320 if (is < 0) 321 return 0; 322 if (is) 323 return isl_qpolynomial_aff_sign(set, qp); 324 325 if (qp->div->n_row > 0) 326 return 0; 327 328 rec = isl_upoly_as_rec(qp->upoly); 329 if (!rec) 330 return 0; 331 332 d = isl_space_dim(qp->dim, isl_dim_all); 333 v = isl_vec_alloc(set->ctx, 2 + d); 334 if (!v) 335 return 0; 336 337 isl_seq_clr(v->el + 1, 1 + d); 338 isl_int_set_si(v->el[0], 1); 339 isl_int_set_si(v->el[2 + qp->upoly->var], 1); 340 341 isl_int_init(l); 342 343 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL); 344 if (res == isl_lp_ok) { 345 isl_qpolynomial *min; 346 isl_qpolynomial *base; 347 isl_qpolynomial *r, *q; 348 isl_qpolynomial *t; 349 350 min = isl_qpolynomial_cst_on_domain(isl_space_copy(qp->dim), l); 351 base = isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp->dim), 352 qp->upoly->var, 1); 353 354 r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0, 355 isl_upoly_copy(rec->p[rec->n - 1])); 356 q = isl_qpolynomial_copy(r); 357 358 for (i = rec->n - 2; i >= 0; --i) { 359 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min)); 360 t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0, 361 isl_upoly_copy(rec->p[i])); 362 r = isl_qpolynomial_add(r, t); 363 if (i == 0) 364 break; 365 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base)); 366 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r)); 367 } 368 369 if (isl_qpolynomial_is_zero(q)) 370 sgn = isl_qpolynomial_sign(set, r); 371 else if (isl_qpolynomial_is_zero(r)) 372 sgn = isl_qpolynomial_sign(set, q); 373 else { 374 int sgn_q, sgn_r; 375 sgn_r = isl_qpolynomial_sign(set, r); 376 sgn_q = isl_qpolynomial_sign(set, q); 377 if (sgn_r == sgn_q) 378 sgn = sgn_r; 379 } 380 381 isl_qpolynomial_free(min); 382 isl_qpolynomial_free(base); 383 isl_qpolynomial_free(q); 384 isl_qpolynomial_free(r); 385 } 386 387 isl_int_clear(l); 388 389 isl_vec_free(v); 390 391 return sgn; 392} 393 394__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain( 395 __isl_keep isl_set *set, 396 __isl_take isl_qpolynomial_fold *fold1, 397 __isl_take isl_qpolynomial_fold *fold2) 398{ 399 int i, j; 400 int n1; 401 struct isl_qpolynomial_fold *res = NULL; 402 int better; 403 404 if (!fold1 || !fold2) 405 goto error; 406 407 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error); 408 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim), 409 goto error); 410 411 better = fold1->type == isl_fold_max ? -1 : 1; 412 413 if (isl_qpolynomial_fold_is_empty(fold1)) { 414 isl_qpolynomial_fold_free(fold1); 415 return fold2; 416 } 417 418 if (isl_qpolynomial_fold_is_empty(fold2)) { 419 isl_qpolynomial_fold_free(fold2); 420 return fold1; 421 } 422 423 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim), 424 fold1->n + fold2->n); 425 if (!res) 426 goto error; 427 428 for (i = 0; i < fold1->n; ++i) { 429 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]); 430 if (!res->qp[res->n]) 431 goto error; 432 res->n++; 433 } 434 n1 = res->n; 435 436 for (i = 0; i < fold2->n; ++i) { 437 for (j = n1 - 1; j >= 0; --j) { 438 isl_qpolynomial *d; 439 int sgn; 440 d = isl_qpolynomial_sub( 441 isl_qpolynomial_copy(res->qp[j]), 442 isl_qpolynomial_copy(fold2->qp[i])); 443 sgn = isl_qpolynomial_sign(set, d); 444 isl_qpolynomial_free(d); 445 if (sgn == 0) 446 continue; 447 if (sgn != better) 448 break; 449 isl_qpolynomial_free(res->qp[j]); 450 if (j != n1 - 1) 451 res->qp[j] = res->qp[n1 - 1]; 452 n1--; 453 if (n1 != res->n - 1) 454 res->qp[n1] = res->qp[res->n - 1]; 455 res->n--; 456 } 457 if (j >= 0) 458 continue; 459 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]); 460 if (!res->qp[res->n]) 461 goto error; 462 res->n++; 463 } 464 465 isl_qpolynomial_fold_free(fold1); 466 isl_qpolynomial_fold_free(fold2); 467 468 return res; 469error: 470 isl_qpolynomial_fold_free(res); 471 isl_qpolynomial_fold_free(fold1); 472 isl_qpolynomial_fold_free(fold2); 473 return NULL; 474} 475 476__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial( 477 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp) 478{ 479 int i; 480 481 if (!fold || !qp) 482 goto error; 483 484 if (isl_qpolynomial_is_zero(qp)) { 485 isl_qpolynomial_free(qp); 486 return fold; 487 } 488 489 fold = isl_qpolynomial_fold_cow(fold); 490 if (!fold) 491 goto error; 492 493 for (i = 0; i < fold->n; ++i) { 494 fold->qp[i] = isl_qpolynomial_add(fold->qp[i], 495 isl_qpolynomial_copy(qp)); 496 if (!fold->qp[i]) 497 goto error; 498 } 499 500 isl_qpolynomial_free(qp); 501 return fold; 502error: 503 isl_qpolynomial_fold_free(fold); 504 isl_qpolynomial_free(qp); 505 return NULL; 506} 507 508__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain( 509 __isl_keep isl_set *dom, 510 __isl_take isl_qpolynomial_fold *fold1, 511 __isl_take isl_qpolynomial_fold *fold2) 512{ 513 int i; 514 isl_qpolynomial_fold *res = NULL; 515 516 if (!fold1 || !fold2) 517 goto error; 518 519 if (isl_qpolynomial_fold_is_empty(fold1)) { 520 isl_qpolynomial_fold_free(fold1); 521 return fold2; 522 } 523 524 if (isl_qpolynomial_fold_is_empty(fold2)) { 525 isl_qpolynomial_fold_free(fold2); 526 return fold1; 527 } 528 529 if (fold1->n == 1 && fold2->n != 1) 530 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1); 531 532 if (fold2->n == 1) { 533 res = isl_qpolynomial_fold_add_qpolynomial(fold1, 534 isl_qpolynomial_copy(fold2->qp[0])); 535 isl_qpolynomial_fold_free(fold2); 536 return res; 537 } 538 539 res = isl_qpolynomial_fold_add_qpolynomial( 540 isl_qpolynomial_fold_copy(fold1), 541 isl_qpolynomial_copy(fold2->qp[0])); 542 543 for (i = 1; i < fold2->n; ++i) { 544 isl_qpolynomial_fold *res_i; 545 res_i = isl_qpolynomial_fold_add_qpolynomial( 546 isl_qpolynomial_fold_copy(fold1), 547 isl_qpolynomial_copy(fold2->qp[i])); 548 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i); 549 } 550 551 isl_qpolynomial_fold_free(fold1); 552 isl_qpolynomial_fold_free(fold2); 553 return res; 554error: 555 isl_qpolynomial_fold_free(res); 556 isl_qpolynomial_fold_free(fold1); 557 isl_qpolynomial_fold_free(fold2); 558 return NULL; 559} 560 561__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities( 562 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq) 563{ 564 int i; 565 566 if (!fold || !eq) 567 goto error; 568 569 fold = isl_qpolynomial_fold_cow(fold); 570 if (!fold) 571 return NULL; 572 573 for (i = 0; i < fold->n; ++i) { 574 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i], 575 isl_basic_set_copy(eq)); 576 if (!fold->qp[i]) 577 goto error; 578 } 579 580 isl_basic_set_free(eq); 581 return fold; 582error: 583 isl_basic_set_free(eq); 584 isl_qpolynomial_fold_free(fold); 585 return NULL; 586} 587 588__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist( 589 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context) 590{ 591 int i; 592 593 if (!fold || !context) 594 goto error; 595 596 fold = isl_qpolynomial_fold_cow(fold); 597 if (!fold) 598 return NULL; 599 600 for (i = 0; i < fold->n; ++i) { 601 fold->qp[i] = isl_qpolynomial_gist(fold->qp[i], 602 isl_set_copy(context)); 603 if (!fold->qp[i]) 604 goto error; 605 } 606 607 isl_set_free(context); 608 return fold; 609error: 610 isl_set_free(context); 611 isl_qpolynomial_fold_free(fold); 612 return NULL; 613} 614 615__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params( 616 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context) 617{ 618 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); 619 isl_set *dom_context = isl_set_universe(space); 620 dom_context = isl_set_intersect_params(dom_context, context); 621 return isl_qpolynomial_fold_gist(fold, dom_context); 622} 623 624#define HAS_TYPE 625 626#undef PW 627#define PW isl_pw_qpolynomial_fold 628#undef EL 629#define EL isl_qpolynomial_fold 630#undef EL_IS_ZERO 631#define EL_IS_ZERO is_empty 632#undef ZERO 633#define ZERO zero 634#undef IS_ZERO 635#define IS_ZERO is_zero 636#undef FIELD 637#define FIELD fold 638#undef DEFAULT_IS_ZERO 639#define DEFAULT_IS_ZERO 1 640 641#define NO_NEG 642#define NO_PULLBACK 643 644#include <isl_pw_templ.c> 645 646#undef UNION 647#define UNION isl_union_pw_qpolynomial_fold 648#undef PART 649#define PART isl_pw_qpolynomial_fold 650#undef PARTS 651#define PARTS pw_qpolynomial_fold 652#define ALIGN_DOMAIN 653 654#define NO_SUB 655 656#include <isl_union_templ.c> 657 658__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type, 659 __isl_take isl_space *dim) 660{ 661 return qpolynomial_fold_alloc(type, dim, 0); 662} 663 664__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc( 665 enum isl_fold type, __isl_take isl_qpolynomial *qp) 666{ 667 isl_qpolynomial_fold *fold; 668 669 if (!qp) 670 return NULL; 671 672 fold = qpolynomial_fold_alloc(type, isl_space_copy(qp->dim), 1); 673 if (!fold) 674 goto error; 675 676 fold->qp[0] = qp; 677 fold->n++; 678 679 return fold; 680error: 681 isl_qpolynomial_fold_free(fold); 682 isl_qpolynomial_free(qp); 683 return NULL; 684} 685 686__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy( 687 __isl_keep isl_qpolynomial_fold *fold) 688{ 689 if (!fold) 690 return NULL; 691 692 fold->ref++; 693 return fold; 694} 695 696__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup( 697 __isl_keep isl_qpolynomial_fold *fold) 698{ 699 int i; 700 isl_qpolynomial_fold *dup; 701 702 if (!fold) 703 return NULL; 704 dup = qpolynomial_fold_alloc(fold->type, 705 isl_space_copy(fold->dim), fold->n); 706 if (!dup) 707 return NULL; 708 709 dup->n = fold->n; 710 for (i = 0; i < fold->n; ++i) { 711 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]); 712 if (!dup->qp[i]) 713 goto error; 714 } 715 716 return dup; 717error: 718 isl_qpolynomial_fold_free(dup); 719 return NULL; 720} 721 722__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow( 723 __isl_take isl_qpolynomial_fold *fold) 724{ 725 if (!fold) 726 return NULL; 727 728 if (fold->ref == 1) 729 return fold; 730 fold->ref--; 731 return isl_qpolynomial_fold_dup(fold); 732} 733 734void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold) 735{ 736 int i; 737 738 if (!fold) 739 return; 740 if (--fold->ref > 0) 741 return; 742 743 for (i = 0; i < fold->n; ++i) 744 isl_qpolynomial_free(fold->qp[i]); 745 isl_space_free(fold->dim); 746 free(fold); 747} 748 749int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold) 750{ 751 if (!fold) 752 return -1; 753 754 return fold->n == 0; 755} 756 757__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold( 758 __isl_take isl_qpolynomial_fold *fold1, 759 __isl_take isl_qpolynomial_fold *fold2) 760{ 761 int i; 762 struct isl_qpolynomial_fold *res = NULL; 763 764 if (!fold1 || !fold2) 765 goto error; 766 767 isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error); 768 isl_assert(fold1->dim->ctx, isl_space_is_equal(fold1->dim, fold2->dim), 769 goto error); 770 771 if (isl_qpolynomial_fold_is_empty(fold1)) { 772 isl_qpolynomial_fold_free(fold1); 773 return fold2; 774 } 775 776 if (isl_qpolynomial_fold_is_empty(fold2)) { 777 isl_qpolynomial_fold_free(fold2); 778 return fold1; 779 } 780 781 res = qpolynomial_fold_alloc(fold1->type, isl_space_copy(fold1->dim), 782 fold1->n + fold2->n); 783 if (!res) 784 goto error; 785 786 for (i = 0; i < fold1->n; ++i) { 787 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]); 788 if (!res->qp[res->n]) 789 goto error; 790 res->n++; 791 } 792 793 for (i = 0; i < fold2->n; ++i) { 794 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]); 795 if (!res->qp[res->n]) 796 goto error; 797 res->n++; 798 } 799 800 isl_qpolynomial_fold_free(fold1); 801 isl_qpolynomial_fold_free(fold2); 802 803 return res; 804error: 805 isl_qpolynomial_fold_free(res); 806 isl_qpolynomial_fold_free(fold1); 807 isl_qpolynomial_fold_free(fold2); 808 return NULL; 809} 810 811__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold( 812 __isl_take isl_pw_qpolynomial_fold *pw1, 813 __isl_take isl_pw_qpolynomial_fold *pw2) 814{ 815 int i, j, n; 816 struct isl_pw_qpolynomial_fold *res; 817 isl_set *set; 818 819 if (!pw1 || !pw2) 820 goto error; 821 822 isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error); 823 824 if (isl_pw_qpolynomial_fold_is_zero(pw1)) { 825 isl_pw_qpolynomial_fold_free(pw1); 826 return pw2; 827 } 828 829 if (isl_pw_qpolynomial_fold_is_zero(pw2)) { 830 isl_pw_qpolynomial_fold_free(pw2); 831 return pw1; 832 } 833 834 if (pw1->type != pw2->type) 835 isl_die(pw1->dim->ctx, isl_error_invalid, 836 "fold types don't match", goto error); 837 838 n = (pw1->n + 1) * (pw2->n + 1); 839 res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim), 840 pw1->type, n); 841 842 for (i = 0; i < pw1->n; ++i) { 843 set = isl_set_copy(pw1->p[i].set); 844 for (j = 0; j < pw2->n; ++j) { 845 struct isl_set *common; 846 isl_qpolynomial_fold *sum; 847 set = isl_set_subtract(set, 848 isl_set_copy(pw2->p[j].set)); 849 common = isl_set_intersect(isl_set_copy(pw1->p[i].set), 850 isl_set_copy(pw2->p[j].set)); 851 if (isl_set_plain_is_empty(common)) { 852 isl_set_free(common); 853 continue; 854 } 855 856 sum = isl_qpolynomial_fold_fold_on_domain(common, 857 isl_qpolynomial_fold_copy(pw1->p[i].fold), 858 isl_qpolynomial_fold_copy(pw2->p[j].fold)); 859 860 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum); 861 } 862 res = isl_pw_qpolynomial_fold_add_piece(res, set, 863 isl_qpolynomial_fold_copy(pw1->p[i].fold)); 864 } 865 866 for (j = 0; j < pw2->n; ++j) { 867 set = isl_set_copy(pw2->p[j].set); 868 for (i = 0; i < pw1->n; ++i) 869 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set)); 870 res = isl_pw_qpolynomial_fold_add_piece(res, set, 871 isl_qpolynomial_fold_copy(pw2->p[j].fold)); 872 } 873 874 isl_pw_qpolynomial_fold_free(pw1); 875 isl_pw_qpolynomial_fold_free(pw2); 876 877 return res; 878error: 879 isl_pw_qpolynomial_fold_free(pw1); 880 isl_pw_qpolynomial_fold_free(pw2); 881 return NULL; 882} 883 884__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 885 __isl_take isl_union_pw_qpolynomial_fold *u, 886 __isl_take isl_pw_qpolynomial_fold *part) 887{ 888 uint32_t hash; 889 struct isl_hash_table_entry *entry; 890 891 u = isl_union_pw_qpolynomial_fold_cow(u); 892 893 if (!part || !u) 894 goto error; 895 896 isl_assert(u->dim->ctx, isl_space_match(part->dim, isl_dim_param, u->dim, 897 isl_dim_param), goto error); 898 899 hash = isl_space_get_hash(part->dim); 900 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash, 901 &has_dim, part->dim, 1); 902 if (!entry) 903 goto error; 904 905 if (!entry->data) 906 entry->data = part; 907 else { 908 entry->data = isl_pw_qpolynomial_fold_fold(entry->data, 909 isl_pw_qpolynomial_fold_copy(part)); 910 if (!entry->data) 911 goto error; 912 isl_pw_qpolynomial_fold_free(part); 913 } 914 915 return u; 916error: 917 isl_pw_qpolynomial_fold_free(part); 918 isl_union_pw_qpolynomial_fold_free(u); 919 return NULL; 920} 921 922static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user) 923{ 924 isl_union_pw_qpolynomial_fold **u; 925 u = (isl_union_pw_qpolynomial_fold **)user; 926 927 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part); 928 929 return 0; 930} 931 932__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold( 933 __isl_take isl_union_pw_qpolynomial_fold *u1, 934 __isl_take isl_union_pw_qpolynomial_fold *u2) 935{ 936 u1 = isl_union_pw_qpolynomial_fold_cow(u1); 937 938 if (!u1 || !u2) 939 goto error; 940 941 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2, 942 &fold_part, &u1) < 0) 943 goto error; 944 945 isl_union_pw_qpolynomial_fold_free(u2); 946 947 return u1; 948error: 949 isl_union_pw_qpolynomial_fold_free(u1); 950 isl_union_pw_qpolynomial_fold_free(u2); 951 return NULL; 952} 953 954__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial( 955 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp) 956{ 957 int i; 958 isl_pw_qpolynomial_fold *pwf; 959 960 if (!pwqp) 961 return NULL; 962 963 pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim), 964 type, pwqp->n); 965 966 for (i = 0; i < pwqp->n; ++i) 967 pwf = isl_pw_qpolynomial_fold_add_piece(pwf, 968 isl_set_copy(pwqp->p[i].set), 969 isl_qpolynomial_fold_alloc(type, 970 isl_qpolynomial_copy(pwqp->p[i].qp))); 971 972 isl_pw_qpolynomial_free(pwqp); 973 974 return pwf; 975} 976 977__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add( 978 __isl_take isl_pw_qpolynomial_fold *pwf1, 979 __isl_take isl_pw_qpolynomial_fold *pwf2) 980{ 981 return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2); 982} 983 984int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1, 985 __isl_keep isl_qpolynomial_fold *fold2) 986{ 987 int i; 988 989 if (!fold1 || !fold2) 990 return -1; 991 992 if (fold1->n != fold2->n) 993 return 0; 994 995 /* We probably want to sort the qps first... */ 996 for (i = 0; i < fold1->n; ++i) { 997 int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]); 998 if (eq < 0 || !eq) 999 return eq; 1000 } 1001 1002 return 1; 1003} 1004 1005__isl_give isl_qpolynomial *isl_qpolynomial_fold_eval( 1006 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt) 1007{ 1008 isl_qpolynomial *qp; 1009 1010 if (!fold || !pnt) 1011 goto error; 1012 isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error); 1013 isl_assert(pnt->dim->ctx, 1014 fold->type == isl_fold_max || fold->type == isl_fold_min, 1015 goto error); 1016 1017 if (fold->n == 0) 1018 qp = isl_qpolynomial_zero_on_domain(isl_space_copy(fold->dim)); 1019 else { 1020 int i; 1021 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]), 1022 isl_point_copy(pnt)); 1023 for (i = 1; i < fold->n; ++i) { 1024 isl_qpolynomial *qp_i; 1025 qp_i = isl_qpolynomial_eval( 1026 isl_qpolynomial_copy(fold->qp[i]), 1027 isl_point_copy(pnt)); 1028 if (fold->type == isl_fold_max) 1029 qp = isl_qpolynomial_max_cst(qp, qp_i); 1030 else 1031 qp = isl_qpolynomial_min_cst(qp, qp_i); 1032 } 1033 } 1034 isl_qpolynomial_fold_free(fold); 1035 isl_point_free(pnt); 1036 1037 return qp; 1038error: 1039 isl_qpolynomial_fold_free(fold); 1040 isl_point_free(pnt); 1041 return NULL; 1042} 1043 1044size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf) 1045{ 1046 int i; 1047 size_t n = 0; 1048 1049 for (i = 0; i < pwf->n; ++i) 1050 n += pwf->p[i].fold->n; 1051 1052 return n; 1053} 1054 1055__isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain( 1056 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max) 1057{ 1058 int i; 1059 isl_qpolynomial *opt; 1060 1061 if (!set || !fold) 1062 goto error; 1063 1064 if (fold->n == 0) { 1065 isl_space *dim = isl_space_copy(fold->dim); 1066 isl_set_free(set); 1067 isl_qpolynomial_fold_free(fold); 1068 return isl_qpolynomial_zero_on_domain(dim); 1069 } 1070 1071 opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]), 1072 isl_set_copy(set), max); 1073 for (i = 1; i < fold->n; ++i) { 1074 isl_qpolynomial *opt_i; 1075 opt_i = isl_qpolynomial_opt_on_domain( 1076 isl_qpolynomial_copy(fold->qp[i]), 1077 isl_set_copy(set), max); 1078 if (max) 1079 opt = isl_qpolynomial_max_cst(opt, opt_i); 1080 else 1081 opt = isl_qpolynomial_min_cst(opt, opt_i); 1082 } 1083 1084 isl_set_free(set); 1085 isl_qpolynomial_fold_free(fold); 1086 1087 return opt; 1088error: 1089 isl_set_free(set); 1090 isl_qpolynomial_fold_free(fold); 1091 return NULL; 1092} 1093 1094/* Check whether for each quasi-polynomial in "fold2" there is 1095 * a quasi-polynomial in "fold1" that dominates it on "set". 1096 */ 1097static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set, 1098 __isl_keep isl_qpolynomial_fold *fold1, 1099 __isl_keep isl_qpolynomial_fold *fold2) 1100{ 1101 int i, j; 1102 int covers; 1103 1104 if (!set || !fold1 || !fold2) 1105 return -1; 1106 1107 covers = fold1->type == isl_fold_max ? 1 : -1; 1108 1109 for (i = 0; i < fold2->n; ++i) { 1110 for (j = 0; j < fold1->n; ++j) { 1111 isl_qpolynomial *d; 1112 int sgn; 1113 1114 d = isl_qpolynomial_sub( 1115 isl_qpolynomial_copy(fold1->qp[j]), 1116 isl_qpolynomial_copy(fold2->qp[i])); 1117 sgn = isl_qpolynomial_sign(set, d); 1118 isl_qpolynomial_free(d); 1119 if (sgn == covers) 1120 break; 1121 } 1122 if (j >= fold1->n) 1123 return 0; 1124 } 1125 1126 return 1; 1127} 1128 1129/* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains 1130 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates 1131 * that of pwf2. 1132 */ 1133int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1, 1134 __isl_keep isl_pw_qpolynomial_fold *pwf2) 1135{ 1136 int i, j; 1137 isl_set *dom1, *dom2; 1138 int is_subset; 1139 1140 if (!pwf1 || !pwf2) 1141 return -1; 1142 1143 if (pwf2->n == 0) 1144 return 1; 1145 if (pwf1->n == 0) 1146 return 0; 1147 1148 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1)); 1149 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2)); 1150 is_subset = isl_set_is_subset(dom2, dom1); 1151 isl_set_free(dom1); 1152 isl_set_free(dom2); 1153 1154 if (is_subset < 0 || !is_subset) 1155 return is_subset; 1156 1157 for (i = 0; i < pwf2->n; ++i) { 1158 for (j = 0; j < pwf1->n; ++j) { 1159 int is_empty; 1160 isl_set *common; 1161 int covers; 1162 1163 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set), 1164 isl_set_copy(pwf2->p[i].set)); 1165 is_empty = isl_set_is_empty(common); 1166 if (is_empty < 0 || is_empty) { 1167 isl_set_free(common); 1168 if (is_empty < 0) 1169 return -1; 1170 continue; 1171 } 1172 covers = qpolynomial_fold_covers_on_domain(common, 1173 pwf1->p[j].fold, pwf2->p[i].fold); 1174 isl_set_free(common); 1175 if (covers < 0 || !covers) 1176 return covers; 1177 } 1178 } 1179 1180 return 1; 1181} 1182 1183__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain( 1184 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph) 1185{ 1186 int i; 1187 isl_ctx *ctx; 1188 1189 if (!fold || !morph) 1190 goto error; 1191 1192 ctx = fold->dim->ctx; 1193 isl_assert(ctx, isl_space_is_equal(fold->dim, morph->dom->dim), goto error); 1194 1195 fold = isl_qpolynomial_fold_cow(fold); 1196 if (!fold) 1197 goto error; 1198 1199 isl_space_free(fold->dim); 1200 fold->dim = isl_space_copy(morph->ran->dim); 1201 if (!fold->dim) 1202 goto error; 1203 1204 for (i = 0; i < fold->n; ++i) { 1205 fold->qp[i] = isl_qpolynomial_morph_domain(fold->qp[i], 1206 isl_morph_copy(morph)); 1207 if (!fold->qp[i]) 1208 goto error; 1209 } 1210 1211 isl_morph_free(morph); 1212 1213 return fold; 1214error: 1215 isl_qpolynomial_fold_free(fold); 1216 isl_morph_free(morph); 1217 return NULL; 1218} 1219 1220enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold) 1221{ 1222 if (!fold) 1223 return isl_fold_list; 1224 return fold->type; 1225} 1226 1227enum isl_fold isl_union_pw_qpolynomial_fold_get_type( 1228 __isl_keep isl_union_pw_qpolynomial_fold *upwf) 1229{ 1230 if (!upwf) 1231 return isl_fold_list; 1232 return upwf->type; 1233} 1234 1235__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift( 1236 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *dim) 1237{ 1238 int i; 1239 1240 if (!fold || !dim) 1241 goto error; 1242 1243 if (isl_space_is_equal(fold->dim, dim)) { 1244 isl_space_free(dim); 1245 return fold; 1246 } 1247 1248 fold = isl_qpolynomial_fold_cow(fold); 1249 if (!fold) 1250 goto error; 1251 1252 isl_space_free(fold->dim); 1253 fold->dim = isl_space_copy(dim); 1254 if (!fold->dim) 1255 goto error; 1256 1257 for (i = 0; i < fold->n; ++i) { 1258 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i], 1259 isl_space_copy(dim)); 1260 if (!fold->qp[i]) 1261 goto error; 1262 } 1263 1264 isl_space_free(dim); 1265 1266 return fold; 1267error: 1268 isl_qpolynomial_fold_free(fold); 1269 isl_space_free(dim); 1270 return NULL; 1271} 1272 1273int isl_qpolynomial_fold_foreach_qpolynomial( 1274 __isl_keep isl_qpolynomial_fold *fold, 1275 int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user) 1276{ 1277 int i; 1278 1279 if (!fold) 1280 return -1; 1281 1282 for (i = 0; i < fold->n; ++i) 1283 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0) 1284 return -1; 1285 1286 return 0; 1287} 1288 1289__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims( 1290 __isl_take isl_qpolynomial_fold *fold, 1291 enum isl_dim_type dst_type, unsigned dst_pos, 1292 enum isl_dim_type src_type, unsigned src_pos, unsigned n) 1293{ 1294 int i; 1295 1296 if (n == 0) 1297 return fold; 1298 1299 fold = isl_qpolynomial_fold_cow(fold); 1300 if (!fold) 1301 return NULL; 1302 1303 fold->dim = isl_space_move_dims(fold->dim, dst_type, dst_pos, 1304 src_type, src_pos, n); 1305 if (!fold->dim) 1306 goto error; 1307 1308 for (i = 0; i < fold->n; ++i) { 1309 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i], 1310 dst_type, dst_pos, src_type, src_pos, n); 1311 if (!fold->qp[i]) 1312 goto error; 1313 } 1314 1315 return fold; 1316error: 1317 isl_qpolynomial_fold_free(fold); 1318 return NULL; 1319} 1320 1321/* For each 0 <= i < "n", replace variable "first" + i of type "type" 1322 * in fold->qp[k] by subs[i]. 1323 */ 1324__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute( 1325 __isl_take isl_qpolynomial_fold *fold, 1326 enum isl_dim_type type, unsigned first, unsigned n, 1327 __isl_keep isl_qpolynomial **subs) 1328{ 1329 int i; 1330 1331 if (n == 0) 1332 return fold; 1333 1334 fold = isl_qpolynomial_fold_cow(fold); 1335 if (!fold) 1336 return NULL; 1337 1338 for (i = 0; i < fold->n; ++i) { 1339 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i], 1340 type, first, n, subs); 1341 if (!fold->qp[i]) 1342 goto error; 1343 } 1344 1345 return fold; 1346error: 1347 isl_qpolynomial_fold_free(fold); 1348 return NULL; 1349} 1350 1351static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user) 1352{ 1353 isl_ctx *ctx; 1354 isl_pw_qpolynomial_fold *pwf; 1355 isl_union_pw_qpolynomial_fold **upwf; 1356 uint32_t hash; 1357 struct isl_hash_table_entry *entry; 1358 1359 upwf = (isl_union_pw_qpolynomial_fold **)user; 1360 1361 ctx = pwqp->dim->ctx; 1362 hash = isl_space_get_hash(pwqp->dim); 1363 entry = isl_hash_table_find(ctx, &(*upwf)->table, 1364 hash, &has_dim, pwqp->dim, 1); 1365 if (!entry) 1366 goto error; 1367 1368 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp); 1369 if (!entry->data) 1370 entry->data = pwf; 1371 else { 1372 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf); 1373 if (!entry->data) 1374 return -1; 1375 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) { 1376 isl_pw_qpolynomial_fold_free(entry->data); 1377 isl_hash_table_remove(ctx, &(*upwf)->table, entry); 1378 } 1379 } 1380 1381 return 0; 1382error: 1383 isl_pw_qpolynomial_free(pwqp); 1384 return -1; 1385} 1386 1387__isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial( 1388 __isl_take isl_union_pw_qpolynomial_fold *upwf, 1389 __isl_take isl_union_pw_qpolynomial *upwqp) 1390{ 1391 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, 1392 isl_union_pw_qpolynomial_get_space(upwqp)); 1393 upwqp = isl_union_pw_qpolynomial_align_params(upwqp, 1394 isl_union_pw_qpolynomial_fold_get_space(upwf)); 1395 1396 upwf = isl_union_pw_qpolynomial_fold_cow(upwf); 1397 if (!upwf || !upwqp) 1398 goto error; 1399 1400 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp, 1401 &upwf) < 0) 1402 goto error; 1403 1404 isl_union_pw_qpolynomial_free(upwqp); 1405 1406 return upwf; 1407error: 1408 isl_union_pw_qpolynomial_fold_free(upwf); 1409 isl_union_pw_qpolynomial_free(upwqp); 1410 return NULL; 1411} 1412 1413static int join_compatible(__isl_keep isl_space *dim1, __isl_keep isl_space *dim2) 1414{ 1415 int m; 1416 m = isl_space_match(dim1, isl_dim_param, dim2, isl_dim_param); 1417 if (m < 0 || !m) 1418 return m; 1419 return isl_space_tuple_match(dim1, isl_dim_out, dim2, isl_dim_in); 1420} 1421 1422/* Compute the intersection of the range of the map and the domain 1423 * of the piecewise quasipolynomial reduction and then compute a bound 1424 * on the associated quasipolynomial reduction over all elements 1425 * in this intersection. 1426 * 1427 * We first introduce some unconstrained dimensions in the 1428 * piecewise quasipolynomial, intersect the resulting domain 1429 * with the wrapped map and the compute the sum. 1430 */ 1431__isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold( 1432 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf, 1433 int *tight) 1434{ 1435 isl_ctx *ctx; 1436 isl_set *dom; 1437 isl_space *map_dim; 1438 isl_space *pwf_dim; 1439 unsigned n_in; 1440 int ok; 1441 1442 ctx = isl_map_get_ctx(map); 1443 if (!ctx) 1444 goto error; 1445 1446 map_dim = isl_map_get_space(map); 1447 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf); 1448 ok = join_compatible(map_dim, pwf_dim); 1449 isl_space_free(map_dim); 1450 isl_space_free(pwf_dim); 1451 if (!ok) 1452 isl_die(ctx, isl_error_invalid, "incompatible dimensions", 1453 goto error); 1454 1455 n_in = isl_map_dim(map, isl_dim_in); 1456 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in); 1457 1458 dom = isl_map_wrap(map); 1459 pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf, 1460 isl_set_get_space(dom)); 1461 1462 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom); 1463 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight); 1464 1465 return pwf; 1466error: 1467 isl_map_free(map); 1468 isl_pw_qpolynomial_fold_free(pwf); 1469 return NULL; 1470} 1471 1472__isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold( 1473 __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf, 1474 int *tight) 1475{ 1476 return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight); 1477} 1478 1479struct isl_apply_fold_data { 1480 isl_union_pw_qpolynomial_fold *upwf; 1481 isl_union_pw_qpolynomial_fold *res; 1482 isl_map *map; 1483 int tight; 1484}; 1485 1486static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf, 1487 void *user) 1488{ 1489 isl_space *map_dim; 1490 isl_space *pwf_dim; 1491 struct isl_apply_fold_data *data = user; 1492 int ok; 1493 1494 map_dim = isl_map_get_space(data->map); 1495 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf); 1496 ok = join_compatible(map_dim, pwf_dim); 1497 isl_space_free(map_dim); 1498 isl_space_free(pwf_dim); 1499 1500 if (ok) { 1501 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map), 1502 pwf, data->tight ? &data->tight : NULL); 1503 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 1504 data->res, pwf); 1505 } else 1506 isl_pw_qpolynomial_fold_free(pwf); 1507 1508 return 0; 1509} 1510 1511static int map_apply(__isl_take isl_map *map, void *user) 1512{ 1513 struct isl_apply_fold_data *data = user; 1514 int r; 1515 1516 data->map = map; 1517 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold( 1518 data->upwf, &pw_qpolynomial_fold_apply, data); 1519 1520 isl_map_free(map); 1521 return r; 1522} 1523 1524__isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold( 1525 __isl_take isl_union_map *umap, 1526 __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight) 1527{ 1528 isl_space *dim; 1529 enum isl_fold type; 1530 struct isl_apply_fold_data data; 1531 1532 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, 1533 isl_union_map_get_space(umap)); 1534 umap = isl_union_map_align_params(umap, 1535 isl_union_pw_qpolynomial_fold_get_space(upwf)); 1536 1537 data.upwf = upwf; 1538 data.tight = tight ? 1 : 0; 1539 dim = isl_union_pw_qpolynomial_fold_get_space(upwf); 1540 type = isl_union_pw_qpolynomial_fold_get_type(upwf); 1541 data.res = isl_union_pw_qpolynomial_fold_zero(dim, type); 1542 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0) 1543 goto error; 1544 1545 isl_union_map_free(umap); 1546 isl_union_pw_qpolynomial_fold_free(upwf); 1547 1548 if (tight) 1549 *tight = data.tight; 1550 1551 return data.res; 1552error: 1553 isl_union_map_free(umap); 1554 isl_union_pw_qpolynomial_fold_free(upwf); 1555 isl_union_pw_qpolynomial_fold_free(data.res); 1556 return NULL; 1557} 1558 1559__isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold( 1560 __isl_take isl_union_set *uset, 1561 __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight) 1562{ 1563 return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight); 1564} 1565 1566/* Reorder the dimension of "fold" according to the given reordering. 1567 */ 1568__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain( 1569 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r) 1570{ 1571 int i; 1572 1573 fold = isl_qpolynomial_fold_cow(fold); 1574 if (!fold || !r) 1575 goto error; 1576 1577 for (i = 0; i < fold->n; ++i) { 1578 fold->qp[i] = isl_qpolynomial_realign_domain(fold->qp[i], 1579 isl_reordering_copy(r)); 1580 if (!fold->qp[i]) 1581 goto error; 1582 } 1583 1584 fold = isl_qpolynomial_fold_reset_domain_space(fold, 1585 isl_space_copy(r->dim)); 1586 1587 isl_reordering_free(r); 1588 1589 return fold; 1590error: 1591 isl_qpolynomial_fold_free(fold); 1592 isl_reordering_free(r); 1593 return NULL; 1594} 1595 1596__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int( 1597 __isl_take isl_qpolynomial_fold *fold, isl_int v) 1598{ 1599 int i; 1600 1601 if (isl_int_is_one(v)) 1602 return fold; 1603 if (fold && isl_int_is_zero(v)) { 1604 isl_qpolynomial_fold *zero; 1605 isl_space *dim = isl_space_copy(fold->dim); 1606 zero = isl_qpolynomial_fold_empty(fold->type, dim); 1607 isl_qpolynomial_fold_free(fold); 1608 return zero; 1609 } 1610 1611 fold = isl_qpolynomial_fold_cow(fold); 1612 if (!fold) 1613 return NULL; 1614 1615 if (isl_int_is_neg(v)) 1616 fold->type = isl_fold_type_negate(fold->type); 1617 for (i = 0; i < fold->n; ++i) { 1618 fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v); 1619 if (!fold->qp[i]) 1620 goto error; 1621 } 1622 1623 return fold; 1624error: 1625 isl_qpolynomial_fold_free(fold); 1626 return NULL; 1627} 1628 1629__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale( 1630 __isl_take isl_qpolynomial_fold *fold, isl_int v) 1631{ 1632 return isl_qpolynomial_fold_mul_isl_int(fold, v); 1633} 1634 1635/* Multiply "fold" by "v". 1636 */ 1637__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val( 1638 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) 1639{ 1640 int i; 1641 1642 if (!fold || !v) 1643 goto error; 1644 1645 if (isl_val_is_one(v)) { 1646 isl_val_free(v); 1647 return fold; 1648 } 1649 if (isl_val_is_zero(v)) { 1650 isl_qpolynomial_fold *zero; 1651 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); 1652 zero = isl_qpolynomial_fold_empty(fold->type, space); 1653 isl_qpolynomial_fold_free(fold); 1654 isl_val_free(v); 1655 return zero; 1656 } 1657 if (!isl_val_is_rat(v)) 1658 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid, 1659 "expecting rational factor", goto error); 1660 1661 fold = isl_qpolynomial_fold_cow(fold); 1662 if (!fold) 1663 goto error; 1664 1665 if (isl_val_is_neg(v)) 1666 fold->type = isl_fold_type_negate(fold->type); 1667 for (i = 0; i < fold->n; ++i) { 1668 fold->qp[i] = isl_qpolynomial_scale_val(fold->qp[i], 1669 isl_val_copy(v)); 1670 if (!fold->qp[i]) 1671 goto error; 1672 } 1673 1674 isl_val_free(v); 1675 return fold; 1676error: 1677 isl_val_free(v); 1678 isl_qpolynomial_fold_free(fold); 1679 return NULL; 1680} 1681