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 #include <isl_map_private.h> 12 #include <isl_union_map_private.h> 13 #include <isl_polynomial_private.h> 14 #include <isl_point_private.h> 15 #include <isl_space_private.h> 16 #include <isl_lp_private.h> 17 #include <isl_seq.h> 18 #include <isl_mat_private.h> 19 #include <isl_val_private.h> 20 #include <isl_vec_private.h> 21 #include <isl_config.h> 22 23 #undef EL_BASE 24 #define EL_BASE pw_qpolynomial_fold 25 26 #include <isl_list_templ.c> 27 28 enum isl_fold isl_fold_type_negate(enum isl_fold type) 29 { 30 switch (type) { 31 case isl_fold_error: 32 return isl_fold_error; 33 case isl_fold_min: 34 return isl_fold_max; 35 case isl_fold_max: 36 return isl_fold_min; 37 case isl_fold_list: 38 return isl_fold_list; 39 } 40 41 isl_die(NULL, isl_error_internal, "unhandled isl_fold type", abort()); 42 } 43 44 /* Construct a new reduction with the given type, domain space and 45 * list of polynomials. 46 */ 47 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc( 48 enum isl_fold type, __isl_take isl_space *space, 49 __isl_take isl_qpolynomial_list *list) 50 { 51 isl_ctx *ctx; 52 isl_qpolynomial_fold *fold; 53 54 if (type < 0 || !space || !list) 55 goto error; 56 57 ctx = isl_space_get_ctx(space); 58 fold = isl_calloc_type(ctx, struct isl_qpolynomial_fold); 59 if (!fold) 60 goto error; 61 62 fold->ref = 1; 63 fold->type = type; 64 fold->dim = space; 65 fold->list = list; 66 67 return fold; 68 error: 69 isl_space_free(space); 70 isl_qpolynomial_list_free(list); 71 return NULL; 72 } 73 74 isl_ctx *isl_qpolynomial_fold_get_ctx(__isl_keep isl_qpolynomial_fold *fold) 75 { 76 return fold ? fold->dim->ctx : NULL; 77 } 78 79 /* Return the domain space of "fold". 80 */ 81 static __isl_keep isl_space *isl_qpolynomial_fold_peek_domain_space( 82 __isl_keep isl_qpolynomial_fold *fold) 83 { 84 return fold ? fold->dim : NULL; 85 } 86 87 __isl_give isl_space *isl_qpolynomial_fold_get_domain_space( 88 __isl_keep isl_qpolynomial_fold *fold) 89 { 90 return isl_space_copy(isl_qpolynomial_fold_peek_domain_space(fold)); 91 } 92 93 /* Return the space of the domain of "fold". 94 * This may be either a copy or the space itself 95 * if there is only one reference to "fold". 96 * This allows the space to be modified inplace 97 * if both the expression and its space have only a single reference. 98 * The caller is not allowed to modify "fold" between this call and 99 * a subsequent call to isl_qpolynomial_fold_restore_domain_space. 100 * The only exception is that isl_qpolynomial_fold_free can be called instead. 101 */ 102 static __isl_give isl_space *isl_qpolynomial_fold_take_domain_space( 103 __isl_keep isl_qpolynomial_fold *fold) 104 { 105 isl_space *space; 106 107 if (!fold) 108 return NULL; 109 if (fold->ref != 1) 110 return isl_qpolynomial_fold_get_domain_space(fold); 111 space = fold->dim; 112 fold->dim = NULL; 113 return space; 114 } 115 116 /* Set the space of the domain of "fold" to "space", 117 * where the space of "fold" may be missing 118 * due to a preceding call to isl_qpolynomial_fold_take_domain_space. 119 * However, in this case, "fold" only has a single reference and 120 * then the call to isl_qpolynomial_fold_cow has no effect. 121 */ 122 static 123 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_restore_domain_space( 124 __isl_keep isl_qpolynomial_fold *fold, __isl_take isl_space *space) 125 { 126 if (!fold || !space) 127 goto error; 128 129 if (fold->dim == space) { 130 isl_space_free(space); 131 return fold; 132 } 133 134 fold = isl_qpolynomial_fold_cow(fold); 135 if (!fold) 136 goto error; 137 isl_space_free(fold->dim); 138 fold->dim = space; 139 140 return fold; 141 error: 142 isl_qpolynomial_fold_free(fold); 143 isl_space_free(space); 144 return NULL; 145 } 146 147 __isl_give isl_space *isl_qpolynomial_fold_get_space( 148 __isl_keep isl_qpolynomial_fold *fold) 149 { 150 isl_space *space; 151 if (!fold) 152 return NULL; 153 space = isl_space_copy(fold->dim); 154 space = isl_space_from_domain(space); 155 space = isl_space_add_dims(space, isl_dim_out, 1); 156 return space; 157 } 158 159 /* Return the list of polynomials in the reduction "fold". 160 */ 161 __isl_keep isl_qpolynomial_list *isl_qpolynomial_fold_peek_list( 162 __isl_keep isl_qpolynomial_fold *fold) 163 { 164 return fold ? fold->list : NULL; 165 } 166 167 /* Return a copy of the list of polynomials in the reduction "fold". 168 */ 169 static __isl_give isl_qpolynomial_list *isl_qpolynomial_fold_get_list( 170 __isl_keep isl_qpolynomial_fold *fold) 171 { 172 return isl_qpolynomial_list_copy(isl_qpolynomial_fold_peek_list(fold)); 173 } 174 175 /* Return the list of polynomials of "fold". 176 * This may be either a copy or the list itself 177 * if there is only one reference to "fold". 178 * This allows the list to be modified inplace 179 * if both the expression and its list have only a single reference. 180 * The caller is not allowed to modify "fold" between this call and 181 * a subsequent call to isl_qpolynomial_fold_restore_list. 182 * The only exception is that isl_qpolynomial_fold_free can be called instead. 183 */ 184 static __isl_give isl_qpolynomial_list *isl_qpolynomial_fold_take_list( 185 __isl_keep isl_qpolynomial_fold *fold) 186 { 187 isl_qpolynomial_list *list; 188 189 if (!fold) 190 return NULL; 191 if (fold->ref != 1) 192 return isl_qpolynomial_fold_get_list(fold); 193 list = fold->list; 194 fold->list = NULL; 195 return list; 196 } 197 198 /* Set the space of the list of polynomials of "fold" to "space", 199 * where the list of polynomials of "fold" may be missing 200 * due to a preceding call to isl_qpolynomial_fold_take_list. 201 * However, in this case, "fold" only has a single reference and 202 * then the call to isl_qpolynomial_fold_cow has no effect. 203 */ 204 static __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_restore_list( 205 __isl_keep isl_qpolynomial_fold *fold, 206 __isl_take isl_qpolynomial_list *list) 207 { 208 if (!fold || !list) 209 goto error; 210 211 if (fold->list == list) { 212 isl_qpolynomial_list_free(list); 213 return fold; 214 } 215 216 fold = isl_qpolynomial_fold_cow(fold); 217 if (!fold) 218 goto error; 219 isl_qpolynomial_list_free(fold->list); 220 fold->list = list; 221 222 return fold; 223 error: 224 isl_qpolynomial_fold_free(fold); 225 isl_qpolynomial_list_free(list); 226 return NULL; 227 } 228 229 /* isl_qpolynomial_list_map callback that calls 230 * isl_qpolynomial_reset_domain_space on "qp". 231 */ 232 static __isl_give isl_qpolynomial *reset_domain_space( 233 __isl_take isl_qpolynomial *qp, void *user) 234 { 235 isl_space *space = user; 236 237 return isl_qpolynomial_reset_domain_space(qp, isl_space_copy(space)); 238 } 239 240 /* Replace the domain space of "fold" by "space". 241 * 242 * Replace the domain space itself and that of all polynomials 243 * in the list. 244 */ 245 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_domain_space( 246 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space) 247 { 248 isl_qpolynomial_list *list; 249 250 list = isl_qpolynomial_fold_take_list(fold); 251 list = isl_qpolynomial_list_map(list, &reset_domain_space, space); 252 fold = isl_qpolynomial_fold_restore_list(fold, list); 253 254 isl_space_free(isl_qpolynomial_fold_take_domain_space(fold)); 255 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 256 257 return fold; 258 } 259 260 /* Reset the space of "fold". This function is called from isl_pw_templ.c 261 * and doesn't know if the space of an element object is represented 262 * directly or through its domain. It therefore passes along both. 263 */ 264 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_reset_space_and_domain( 265 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space, 266 __isl_take isl_space *domain) 267 { 268 isl_space_free(space); 269 return isl_qpolynomial_fold_reset_domain_space(fold, domain); 270 } 271 272 /* Internal data structure for isl_qpolynomial_fold_*_dims 273 * representing their arguments. 274 */ 275 struct isl_fold_dims_data { 276 enum isl_dim_type type; 277 unsigned first; 278 unsigned n; 279 }; 280 281 /* isl_qpolynomial_list_every callback that checks whether "qp" 282 * does not involve any dimensions in the given range. 283 */ 284 static isl_bool not_involved(__isl_keep isl_qpolynomial *qp, void *user) 285 { 286 struct isl_fold_dims_data *data = user; 287 isl_bool involves; 288 289 involves = isl_qpolynomial_involves_dims(qp, data->type, 290 data->first, data->n); 291 return isl_bool_not(involves); 292 } 293 294 /* Does "fold" involve any dimensions in the given range. 295 * 296 * It involves any of those dimensions if it is not the case 297 * that every polynomial in the reduction does not involve 298 * any of the dimensions. 299 */ 300 static isl_bool isl_qpolynomial_fold_involves_dims( 301 __isl_keep isl_qpolynomial_fold *fold, 302 enum isl_dim_type type, unsigned first, unsigned n) 303 { 304 struct isl_fold_dims_data data = { type, first, n }; 305 isl_qpolynomial_list *list; 306 isl_bool not; 307 308 if (!fold) 309 return isl_bool_error; 310 if (n == 0) 311 return isl_bool_false; 312 313 list = isl_qpolynomial_fold_peek_list(fold); 314 not = isl_qpolynomial_list_every(list, ¬_involved, &data); 315 return isl_bool_not(not); 316 } 317 318 /* Internal data structure for isl_qpolynomial_fold_set_dim_name 319 * representing its arguments. 320 */ 321 struct isl_fold_set_dim_name_data { 322 enum isl_dim_type type; 323 unsigned pos; 324 const char *s; 325 }; 326 327 /* isl_qpolynomial_list_map callback for calling 328 * isl_qpolynomial_set_dim_name on "qp". 329 */ 330 static __isl_give isl_qpolynomial *set_dim_name(__isl_take isl_qpolynomial *qp, 331 void *user) 332 { 333 struct isl_fold_set_dim_name_data *data = user; 334 335 qp = isl_qpolynomial_set_dim_name(qp, data->type, data->pos, data->s); 336 return qp; 337 } 338 339 /* Given a dimension type for an isl_qpolynomial_fold, 340 * return the corresponding type for the domain. 341 */ 342 static enum isl_dim_type domain_type(enum isl_dim_type type) 343 { 344 if (type == isl_dim_in) 345 return isl_dim_set; 346 return type; 347 } 348 349 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_set_dim_name( 350 __isl_take isl_qpolynomial_fold *fold, 351 enum isl_dim_type type, unsigned pos, const char *s) 352 { 353 struct isl_fold_set_dim_name_data data = { type, pos, s }; 354 enum isl_dim_type set_type; 355 isl_space *space; 356 isl_qpolynomial_list *list; 357 358 list = isl_qpolynomial_fold_take_list(fold); 359 list = isl_qpolynomial_list_map(list, &set_dim_name, &data); 360 fold = isl_qpolynomial_fold_restore_list(fold, list); 361 362 set_type = domain_type(type); 363 space = isl_qpolynomial_fold_take_domain_space(fold); 364 space = isl_space_set_dim_name(space, set_type, pos, s); 365 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 366 367 return fold; 368 } 369 370 /* isl_qpolynomial_list_map callback for calling 371 * isl_qpolynomial_drop_dims on "qp". 372 */ 373 static __isl_give isl_qpolynomial *drop_dims(__isl_take isl_qpolynomial *qp, 374 void *user) 375 { 376 struct isl_fold_dims_data *data = user; 377 378 qp = isl_qpolynomial_drop_dims(qp, data->type, data->first, data->n); 379 return qp; 380 } 381 382 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims( 383 __isl_take isl_qpolynomial_fold *fold, 384 enum isl_dim_type type, unsigned first, unsigned n) 385 { 386 struct isl_fold_dims_data data = { type, first, n }; 387 enum isl_dim_type set_type; 388 isl_space *space; 389 isl_qpolynomial_list *list; 390 391 if (!fold) 392 return NULL; 393 if (n == 0) 394 return fold; 395 396 set_type = domain_type(type); 397 398 list = isl_qpolynomial_fold_take_list(fold); 399 list = isl_qpolynomial_list_map(list, &drop_dims, &data); 400 fold = isl_qpolynomial_fold_restore_list(fold, list); 401 402 space = isl_qpolynomial_fold_take_domain_space(fold); 403 space = isl_space_drop_dims(space, set_type, first, n); 404 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 405 406 return fold; 407 } 408 409 /* isl_qpolynomial_list_map callback for calling 410 * isl_qpolynomial_insert_dims on "qp". 411 */ 412 static __isl_give isl_qpolynomial *insert_dims(__isl_take isl_qpolynomial *qp, 413 void *user) 414 { 415 struct isl_fold_dims_data *data = user; 416 417 qp = isl_qpolynomial_insert_dims(qp, data->type, data->first, data->n); 418 return qp; 419 } 420 421 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_insert_dims( 422 __isl_take isl_qpolynomial_fold *fold, 423 enum isl_dim_type type, unsigned first, unsigned n) 424 { 425 struct isl_fold_dims_data data = { type, first, n }; 426 enum isl_dim_type set_type; 427 isl_space *space; 428 isl_qpolynomial_list *list; 429 430 if (!fold) 431 return NULL; 432 if (n == 0 && !isl_space_is_named_or_nested(fold->dim, type)) 433 return fold; 434 435 list = isl_qpolynomial_fold_take_list(fold); 436 list = isl_qpolynomial_list_map(list, &insert_dims, &data); 437 fold = isl_qpolynomial_fold_restore_list(fold, list); 438 439 set_type = domain_type(type); 440 space = isl_qpolynomial_fold_take_domain_space(fold); 441 space = isl_space_insert_dims(space, set_type, first, n); 442 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 443 444 return fold; 445 } 446 447 /* Determine the sign of the constant quasipolynomial "qp". 448 * 449 * Return 450 * -1 if qp <= 0 451 * 1 if qp >= 0 452 * 0 if unknown 453 * 454 * For qp == 0, we can return either -1 or 1. In practice, we return 1. 455 * For qp == NaN, the sign is undefined, so we return 0. 456 */ 457 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp) 458 { 459 isl_poly_cst *cst; 460 461 if (isl_qpolynomial_is_nan(qp)) 462 return 0; 463 464 cst = isl_poly_as_cst(qp->poly); 465 if (!cst) 466 return 0; 467 468 return isl_int_sgn(cst->n) < 0 ? -1 : 1; 469 } 470 471 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set, 472 __isl_keep isl_qpolynomial *qp) 473 { 474 enum isl_lp_result res; 475 isl_vec *aff; 476 isl_int opt; 477 int sgn = 0; 478 479 aff = isl_qpolynomial_extract_affine(qp); 480 if (!aff) 481 return 0; 482 483 isl_int_init(opt); 484 485 res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0], 486 &opt, NULL, NULL); 487 if (res == isl_lp_error) 488 goto done; 489 if (res == isl_lp_empty || 490 (res == isl_lp_ok && !isl_int_is_neg(opt))) { 491 sgn = 1; 492 goto done; 493 } 494 495 res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0], 496 &opt, NULL, NULL); 497 if (res == isl_lp_ok && !isl_int_is_pos(opt)) 498 sgn = -1; 499 500 done: 501 isl_int_clear(opt); 502 isl_vec_free(aff); 503 return sgn; 504 } 505 506 /* Determine, if possible, the sign of the quasipolynomial "qp" on 507 * the domain "set". 508 * 509 * If qp is a constant, then the problem is trivial. 510 * If qp is linear, then we check if the minimum of the corresponding 511 * affine constraint is non-negative or if the maximum is non-positive. 512 * 513 * Otherwise, we check if the outermost variable "v" has a lower bound "l" 514 * in "set". If so, we write qp(v,v') as 515 * 516 * q(v,v') * (v - l) + r(v') 517 * 518 * if q(v,v') and r(v') have the same known sign, then the original 519 * quasipolynomial has the same sign as well. 520 * 521 * Return 522 * -1 if qp <= 0 523 * 1 if qp >= 0 524 * 0 if unknown 525 */ 526 static int isl_qpolynomial_sign(__isl_keep isl_set *set, 527 __isl_keep isl_qpolynomial *qp) 528 { 529 isl_size d; 530 int i; 531 isl_bool is; 532 isl_poly_rec *rec; 533 isl_vec *v; 534 isl_int l; 535 enum isl_lp_result res; 536 int sgn = 0; 537 538 is = isl_qpolynomial_is_cst(qp, NULL, NULL); 539 if (is < 0) 540 return 0; 541 if (is) 542 return isl_qpolynomial_cst_sign(qp); 543 544 is = isl_qpolynomial_is_affine(qp); 545 if (is < 0) 546 return 0; 547 if (is) 548 return isl_qpolynomial_aff_sign(set, qp); 549 550 if (qp->div->n_row > 0) 551 return 0; 552 553 rec = isl_poly_as_rec(qp->poly); 554 if (!rec) 555 return 0; 556 557 d = isl_space_dim(qp->dim, isl_dim_all); 558 if (d < 0) 559 return 0; 560 v = isl_vec_alloc(set->ctx, 2 + d); 561 if (!v) 562 return 0; 563 564 isl_seq_clr(v->el + 1, 1 + d); 565 isl_int_set_si(v->el[0], 1); 566 isl_int_set_si(v->el[2 + qp->poly->var], 1); 567 568 isl_int_init(l); 569 570 res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL); 571 if (res == isl_lp_ok) { 572 isl_qpolynomial *min; 573 isl_qpolynomial *base; 574 isl_qpolynomial *r, *q; 575 isl_qpolynomial *t; 576 577 min = isl_qpolynomial_cst_on_domain(isl_space_copy(qp->dim), l); 578 base = isl_qpolynomial_var_pow_on_domain(isl_space_copy(qp->dim), 579 qp->poly->var, 1); 580 581 r = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0, 582 isl_poly_copy(rec->p[rec->n - 1])); 583 q = isl_qpolynomial_copy(r); 584 585 for (i = rec->n - 2; i >= 0; --i) { 586 r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min)); 587 t = isl_qpolynomial_alloc(isl_space_copy(qp->dim), 0, 588 isl_poly_copy(rec->p[i])); 589 r = isl_qpolynomial_add(r, t); 590 if (i == 0) 591 break; 592 q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base)); 593 q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r)); 594 } 595 596 if (isl_qpolynomial_is_zero(q)) 597 sgn = isl_qpolynomial_sign(set, r); 598 else if (isl_qpolynomial_is_zero(r)) 599 sgn = isl_qpolynomial_sign(set, q); 600 else { 601 int sgn_q, sgn_r; 602 sgn_r = isl_qpolynomial_sign(set, r); 603 sgn_q = isl_qpolynomial_sign(set, q); 604 if (sgn_r == sgn_q) 605 sgn = sgn_r; 606 } 607 608 isl_qpolynomial_free(min); 609 isl_qpolynomial_free(base); 610 isl_qpolynomial_free(q); 611 isl_qpolynomial_free(r); 612 } 613 614 isl_int_clear(l); 615 616 isl_vec_free(v); 617 618 return sgn; 619 } 620 621 /* Check that "fold1" and "fold2" have the same type. 622 */ 623 static isl_stat isl_qpolynomial_fold_check_equal_type( 624 __isl_keep isl_qpolynomial_fold *fold1, 625 __isl_keep isl_qpolynomial_fold *fold2) 626 { 627 enum isl_fold type1, type2; 628 629 type1 = isl_qpolynomial_fold_get_type(fold1); 630 type2 = isl_qpolynomial_fold_get_type(fold2); 631 if (type1 < 0 || type2 < 0) 632 return isl_stat_error; 633 if (type1 != type2) 634 isl_die(isl_qpolynomial_fold_get_ctx(fold1), isl_error_invalid, 635 "fold types don't match", return isl_stat_error); 636 return isl_stat_ok; 637 } 638 639 /* Check that "fold1" and "fold2" have the same (domain) space. 640 */ 641 static isl_stat isl_qpolynomial_fold_check_equal_space( 642 __isl_keep isl_qpolynomial_fold *fold1, 643 __isl_keep isl_qpolynomial_fold *fold2) 644 { 645 isl_bool equal; 646 isl_space *space1, *space2; 647 648 space1 = isl_qpolynomial_fold_peek_domain_space(fold1); 649 space2 = isl_qpolynomial_fold_peek_domain_space(fold2); 650 equal = isl_space_is_equal(space1, space2); 651 if (equal < 0) 652 return isl_stat_error; 653 if (!equal) 654 isl_die(isl_qpolynomial_fold_get_ctx(fold1), isl_error_invalid, 655 "spaces don't match", return isl_stat_error); 656 return isl_stat_ok; 657 } 658 659 /* Combine "list1" and "list2" into a single list, eliminating 660 * those elements of one list that are already covered by the other 661 * list on "set". 662 * 663 * "better" is the sign that the difference qp1 - qp2 needs to have for qp1 664 * to be covered by qp2. 665 */ 666 static __isl_give isl_qpolynomial_list *merge_lists(__isl_keep isl_set *set, 667 __isl_take isl_qpolynomial_list *list1, 668 __isl_take isl_qpolynomial_list *list2, int better) 669 { 670 int i, j; 671 isl_size n1, n2; 672 673 n1 = isl_qpolynomial_list_size(list1); 674 n2 = isl_qpolynomial_list_size(list2); 675 if (n1 < 0 || n2 < 0) 676 goto error; 677 678 for (i = n2 - 1; i >= 0; --i) { 679 for (j = n1 - 1; j >= 0; --j) { 680 isl_qpolynomial *qp1, *qp2, *d; 681 int sgn; 682 isl_bool equal; 683 684 qp1 = isl_qpolynomial_list_peek(list1, j); 685 qp2 = isl_qpolynomial_list_peek(list2, i); 686 equal = isl_qpolynomial_plain_is_equal(qp1, qp2); 687 if (equal < 0) 688 goto error; 689 if (equal) 690 break; 691 d = isl_qpolynomial_sub( 692 isl_qpolynomial_copy(qp1), 693 isl_qpolynomial_copy(qp2)); 694 sgn = isl_qpolynomial_sign(set, d); 695 isl_qpolynomial_free(d); 696 if (sgn == 0) 697 continue; 698 if (sgn != better) 699 break; 700 list1 = isl_qpolynomial_list_drop(list1, j, 1); 701 n1--; 702 } 703 if (j < 0) 704 continue; 705 list2 = isl_qpolynomial_list_drop(list2, i, 1); 706 n2--; 707 } 708 709 return isl_qpolynomial_list_concat(list1, list2); 710 error: 711 isl_qpolynomial_list_free(list1); 712 isl_qpolynomial_list_free(list2); 713 return NULL; 714 } 715 716 /* Combine "fold1" and "fold2" into a single reduction, eliminating 717 * those elements of one reduction that are already covered by the other 718 * reduction on "set". 719 * 720 * If "fold1" or "fold2" is an empty reduction, then return 721 * the other reduction. 722 * If "fold1" or "fold2" is a NaN, then return this NaN. 723 */ 724 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain( 725 __isl_keep isl_set *set, 726 __isl_take isl_qpolynomial_fold *fold1, 727 __isl_take isl_qpolynomial_fold *fold2) 728 { 729 isl_qpolynomial_list *list1; 730 isl_qpolynomial_list *list2; 731 int better; 732 733 if (isl_qpolynomial_fold_check_equal_type(fold1, fold2) < 0) 734 goto error; 735 if (isl_qpolynomial_fold_check_equal_space(fold1, fold2) < 0) 736 goto error; 737 738 better = fold1->type == isl_fold_max ? -1 : 1; 739 740 if (isl_qpolynomial_fold_is_empty(fold1) || 741 isl_qpolynomial_fold_is_nan(fold2)) { 742 isl_qpolynomial_fold_free(fold1); 743 return fold2; 744 } 745 746 if (isl_qpolynomial_fold_is_empty(fold2) || 747 isl_qpolynomial_fold_is_nan(fold1)) { 748 isl_qpolynomial_fold_free(fold2); 749 return fold1; 750 } 751 752 list1 = isl_qpolynomial_fold_take_list(fold1); 753 list2 = isl_qpolynomial_fold_take_list(fold2); 754 755 list1 = merge_lists(set, list1, list2, better); 756 757 fold1 = isl_qpolynomial_fold_restore_list(fold1, list1); 758 isl_qpolynomial_fold_free(fold2); 759 760 return fold1; 761 error: 762 isl_qpolynomial_fold_free(fold1); 763 isl_qpolynomial_fold_free(fold2); 764 return NULL; 765 } 766 767 /* isl_qpolynomial_list_map callback for adding "qp2" to "qp". 768 */ 769 static __isl_give isl_qpolynomial *add_qpolynomial( 770 __isl_take isl_qpolynomial *qp, void *user) 771 { 772 isl_qpolynomial *qp2 = user; 773 774 return isl_qpolynomial_add(qp, isl_qpolynomial_copy(qp2)); 775 } 776 777 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_qpolynomial( 778 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_qpolynomial *qp) 779 { 780 isl_qpolynomial_list *list; 781 782 if (!fold || !qp) 783 goto error; 784 785 if (isl_qpolynomial_is_zero(qp)) { 786 isl_qpolynomial_free(qp); 787 return fold; 788 } 789 790 list = isl_qpolynomial_fold_take_list(fold); 791 list = isl_qpolynomial_list_map(list, &add_qpolynomial, qp); 792 fold = isl_qpolynomial_fold_restore_list(fold, list); 793 794 isl_qpolynomial_free(qp); 795 return fold; 796 error: 797 isl_qpolynomial_fold_free(fold); 798 isl_qpolynomial_free(qp); 799 return NULL; 800 } 801 802 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_add_on_domain( 803 __isl_keep isl_set *dom, 804 __isl_take isl_qpolynomial_fold *fold1, 805 __isl_take isl_qpolynomial_fold *fold2) 806 { 807 int i; 808 isl_size n1, n2; 809 isl_qpolynomial_fold *res = NULL; 810 isl_qpolynomial *qp; 811 isl_qpolynomial_list *list1, *list2; 812 813 if (!fold1 || !fold2) 814 goto error; 815 816 if (isl_qpolynomial_fold_is_empty(fold1)) { 817 isl_qpolynomial_fold_free(fold1); 818 return fold2; 819 } 820 821 if (isl_qpolynomial_fold_is_empty(fold2)) { 822 isl_qpolynomial_fold_free(fold2); 823 return fold1; 824 } 825 826 list1 = isl_qpolynomial_fold_peek_list(fold1); 827 list2 = isl_qpolynomial_fold_peek_list(fold2); 828 n1 = isl_qpolynomial_list_size(list1); 829 n2 = isl_qpolynomial_list_size(list2); 830 if (n1 < 0 || n2 < 0) 831 goto error; 832 833 if (n1 == 1 && n2 != 1) 834 return isl_qpolynomial_fold_add_on_domain(dom, fold2, fold1); 835 836 qp = isl_qpolynomial_list_get_at(list2, 0); 837 if (n2 == 1) { 838 res = isl_qpolynomial_fold_add_qpolynomial(fold1, qp); 839 isl_qpolynomial_fold_free(fold2); 840 return res; 841 } 842 843 res = isl_qpolynomial_fold_add_qpolynomial( 844 isl_qpolynomial_fold_copy(fold1), qp); 845 846 for (i = 1; i < n2; ++i) { 847 isl_qpolynomial_fold *res_i; 848 849 qp = isl_qpolynomial_list_get_at(list2, i); 850 res_i = isl_qpolynomial_fold_add_qpolynomial( 851 isl_qpolynomial_fold_copy(fold1), qp); 852 res = isl_qpolynomial_fold_fold_on_domain(dom, res, res_i); 853 } 854 855 isl_qpolynomial_fold_free(fold1); 856 isl_qpolynomial_fold_free(fold2); 857 return res; 858 error: 859 isl_qpolynomial_fold_free(res); 860 isl_qpolynomial_fold_free(fold1); 861 isl_qpolynomial_fold_free(fold2); 862 return NULL; 863 } 864 865 /* isl_qpolynomial_list_map callback for calling 866 * isl_qpolynomial_substitute_equalities on "qp" and "eq". 867 */ 868 static __isl_give isl_qpolynomial *substitute_equalities( 869 __isl_take isl_qpolynomial *qp, void *user) 870 { 871 isl_basic_set *eq = user; 872 873 eq = isl_basic_set_copy(eq); 874 return isl_qpolynomial_substitute_equalities(qp, eq); 875 } 876 877 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities( 878 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq) 879 { 880 isl_qpolynomial_list *list; 881 882 list = isl_qpolynomial_fold_take_list(fold); 883 list = isl_qpolynomial_list_map(list, &substitute_equalities, eq); 884 fold = isl_qpolynomial_fold_restore_list(fold, list); 885 886 isl_basic_set_free(eq); 887 return fold; 888 } 889 890 /* isl_qpolynomial_list_map callback for calling 891 * isl_qpolynomial_substitute_equalities on "qp" and "context". 892 */ 893 static __isl_give isl_qpolynomial *gist(__isl_take isl_qpolynomial *qp, 894 void *user) 895 { 896 isl_set *context = user; 897 898 return isl_qpolynomial_gist(qp, isl_set_copy(context)); 899 } 900 901 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist( 902 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context) 903 { 904 isl_qpolynomial_list *list; 905 906 list = isl_qpolynomial_fold_take_list(fold); 907 list = isl_qpolynomial_list_map(list, &gist, context); 908 fold = isl_qpolynomial_fold_restore_list(fold, list); 909 910 isl_set_free(context); 911 return fold; 912 } 913 914 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_gist_params( 915 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *context) 916 { 917 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); 918 isl_set *dom_context = isl_set_universe(space); 919 dom_context = isl_set_intersect_params(dom_context, context); 920 return isl_qpolynomial_fold_gist(fold, dom_context); 921 } 922 923 /* Return a zero (i.e., empty) isl_qpolynomial_fold in the given space. 924 * 925 * This is a helper function for isl_pw_*_as_* that ensures a uniform 926 * interface over all piecewise types. 927 */ 928 static __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_zero_in_space( 929 __isl_take isl_space *space, enum isl_fold type) 930 { 931 return isl_qpolynomial_fold_empty(type, isl_space_domain(space)); 932 } 933 934 #define isl_qpolynomial_fold_involves_nan isl_qpolynomial_fold_is_nan 935 936 #define HAS_TYPE 937 938 #undef PW 939 #define PW isl_pw_qpolynomial_fold 940 #undef BASE 941 #define BASE qpolynomial_fold 942 #undef EL_IS_ZERO 943 #define EL_IS_ZERO is_empty 944 #undef ZERO 945 #define ZERO zero 946 #undef IS_ZERO 947 #define IS_ZERO is_zero 948 #undef FIELD 949 #define FIELD fold 950 #undef DEFAULT_IS_ZERO 951 #define DEFAULT_IS_ZERO 1 952 953 #include <isl_pw_templ.c> 954 #include <isl_pw_add_disjoint_templ.c> 955 #include <isl_pw_eval.c> 956 #include <isl_pw_fix_templ.c> 957 #include <isl_pw_from_range_templ.c> 958 #include <isl_pw_insert_dims_templ.c> 959 #include <isl_pw_lift_templ.c> 960 #include <isl_pw_morph_templ.c> 961 #include <isl_pw_move_dims_templ.c> 962 #include <isl_pw_opt_templ.c> 963 964 #undef BASE 965 #define BASE pw_qpolynomial_fold 966 967 #include <isl_union_single.c> 968 #include <isl_union_eval.c> 969 970 /* Construct a new reduction of the given type and space 971 * with an empty list of polynomials. 972 */ 973 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type, 974 __isl_take isl_space *space) 975 { 976 isl_ctx *ctx; 977 isl_qpolynomial_list *list; 978 979 if (!space) 980 return NULL; 981 ctx = isl_space_get_ctx(space); 982 list = isl_qpolynomial_list_alloc(ctx, 0); 983 return qpolynomial_fold_alloc(type, space, list); 984 } 985 986 /* Construct a new reduction of the given type and 987 * a single given polynomial. 988 */ 989 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc( 990 enum isl_fold type, __isl_take isl_qpolynomial *qp) 991 { 992 isl_space *space; 993 isl_qpolynomial_list *list; 994 995 space = isl_qpolynomial_get_domain_space(qp); 996 list = isl_qpolynomial_list_from_qpolynomial(qp); 997 return qpolynomial_fold_alloc(type, space, list); 998 } 999 1000 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy( 1001 __isl_keep isl_qpolynomial_fold *fold) 1002 { 1003 if (!fold) 1004 return NULL; 1005 1006 fold->ref++; 1007 return fold; 1008 } 1009 1010 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup( 1011 __isl_keep isl_qpolynomial_fold *fold) 1012 { 1013 enum isl_fold type; 1014 isl_space *space; 1015 isl_qpolynomial_list *list; 1016 1017 type = isl_qpolynomial_fold_get_type(fold); 1018 space = isl_qpolynomial_fold_get_domain_space(fold); 1019 list = isl_qpolynomial_fold_get_list(fold); 1020 return qpolynomial_fold_alloc(type, space, list); 1021 } 1022 1023 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow( 1024 __isl_take isl_qpolynomial_fold *fold) 1025 { 1026 if (!fold) 1027 return NULL; 1028 1029 if (fold->ref == 1) 1030 return fold; 1031 fold->ref--; 1032 return isl_qpolynomial_fold_dup(fold); 1033 } 1034 1035 __isl_null isl_qpolynomial_fold *isl_qpolynomial_fold_free( 1036 __isl_take isl_qpolynomial_fold *fold) 1037 { 1038 if (!fold) 1039 return NULL; 1040 if (--fold->ref > 0) 1041 return NULL; 1042 1043 isl_qpolynomial_list_free(fold->list); 1044 isl_space_free(fold->dim); 1045 free(fold); 1046 1047 return NULL; 1048 } 1049 1050 isl_bool isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold) 1051 { 1052 isl_size n; 1053 isl_qpolynomial_list *list; 1054 1055 list = isl_qpolynomial_fold_peek_list(fold); 1056 n = isl_qpolynomial_list_size(list); 1057 if (n < 0) 1058 return isl_bool_error; 1059 1060 return isl_bool_ok(n == 0); 1061 } 1062 1063 /* Does "fold" represent max(NaN) or min(NaN)? 1064 */ 1065 isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold) 1066 { 1067 isl_size n; 1068 isl_qpolynomial *qp; 1069 isl_qpolynomial_list *list; 1070 1071 list = isl_qpolynomial_fold_peek_list(fold); 1072 n = isl_qpolynomial_list_size(list); 1073 if (n < 0) 1074 return isl_bool_error; 1075 if (n != 1) 1076 return isl_bool_false; 1077 qp = isl_qpolynomial_list_peek(list, 0); 1078 return isl_qpolynomial_is_nan(qp); 1079 } 1080 1081 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold( 1082 __isl_take isl_qpolynomial_fold *fold1, 1083 __isl_take isl_qpolynomial_fold *fold2) 1084 { 1085 isl_qpolynomial_list *list1, *list2; 1086 1087 if (isl_qpolynomial_fold_check_equal_type(fold1, fold2) < 0) 1088 goto error; 1089 if (isl_qpolynomial_fold_check_equal_space(fold1, fold2) < 0) 1090 goto error; 1091 1092 if (isl_qpolynomial_fold_is_empty(fold1)) { 1093 isl_qpolynomial_fold_free(fold1); 1094 return fold2; 1095 } 1096 1097 if (isl_qpolynomial_fold_is_empty(fold2)) { 1098 isl_qpolynomial_fold_free(fold2); 1099 return fold1; 1100 } 1101 1102 list1 = isl_qpolynomial_fold_take_list(fold1); 1103 list2 = isl_qpolynomial_fold_take_list(fold2); 1104 list1 = isl_qpolynomial_list_concat(list1, list2); 1105 fold1 = isl_qpolynomial_fold_restore_list(fold1, list1); 1106 isl_qpolynomial_fold_free(fold2); 1107 1108 return fold1; 1109 error: 1110 isl_qpolynomial_fold_free(fold1); 1111 isl_qpolynomial_fold_free(fold2); 1112 return NULL; 1113 } 1114 1115 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold( 1116 __isl_take isl_pw_qpolynomial_fold *pw1, 1117 __isl_take isl_pw_qpolynomial_fold *pw2) 1118 { 1119 int i, j, n; 1120 struct isl_pw_qpolynomial_fold *res; 1121 isl_set *set; 1122 1123 if (!pw1 || !pw2) 1124 goto error; 1125 1126 isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error); 1127 1128 if (isl_pw_qpolynomial_fold_is_zero(pw1)) { 1129 isl_pw_qpolynomial_fold_free(pw1); 1130 return pw2; 1131 } 1132 1133 if (isl_pw_qpolynomial_fold_is_zero(pw2)) { 1134 isl_pw_qpolynomial_fold_free(pw2); 1135 return pw1; 1136 } 1137 1138 if (pw1->type != pw2->type) 1139 isl_die(pw1->dim->ctx, isl_error_invalid, 1140 "fold types don't match", goto error); 1141 1142 n = (pw1->n + 1) * (pw2->n + 1); 1143 res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim), 1144 pw1->type, n); 1145 1146 for (i = 0; i < pw1->n; ++i) { 1147 set = isl_set_copy(pw1->p[i].set); 1148 for (j = 0; j < pw2->n; ++j) { 1149 struct isl_set *common; 1150 isl_qpolynomial_fold *sum; 1151 set = isl_set_subtract(set, 1152 isl_set_copy(pw2->p[j].set)); 1153 common = isl_set_intersect(isl_set_copy(pw1->p[i].set), 1154 isl_set_copy(pw2->p[j].set)); 1155 if (isl_set_plain_is_empty(common)) { 1156 isl_set_free(common); 1157 continue; 1158 } 1159 1160 sum = isl_qpolynomial_fold_fold_on_domain(common, 1161 isl_qpolynomial_fold_copy(pw1->p[i].fold), 1162 isl_qpolynomial_fold_copy(pw2->p[j].fold)); 1163 1164 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum); 1165 } 1166 res = isl_pw_qpolynomial_fold_add_piece(res, set, 1167 isl_qpolynomial_fold_copy(pw1->p[i].fold)); 1168 } 1169 1170 for (j = 0; j < pw2->n; ++j) { 1171 set = isl_set_copy(pw2->p[j].set); 1172 for (i = 0; i < pw1->n; ++i) 1173 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set)); 1174 res = isl_pw_qpolynomial_fold_add_piece(res, set, 1175 isl_qpolynomial_fold_copy(pw2->p[j].fold)); 1176 } 1177 1178 isl_pw_qpolynomial_fold_free(pw1); 1179 isl_pw_qpolynomial_fold_free(pw2); 1180 1181 return res; 1182 error: 1183 isl_pw_qpolynomial_fold_free(pw1); 1184 isl_pw_qpolynomial_fold_free(pw2); 1185 return NULL; 1186 } 1187 1188 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 1189 __isl_take isl_union_pw_qpolynomial_fold *u, 1190 __isl_take isl_pw_qpolynomial_fold *part) 1191 { 1192 struct isl_hash_table_entry *entry; 1193 1194 u = isl_union_pw_qpolynomial_fold_cow(u); 1195 1196 if (!part || !u) 1197 goto error; 1198 if (isl_space_check_equal_params(part->dim, u->space) < 0) 1199 goto error; 1200 1201 entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1); 1202 if (!entry) 1203 goto error; 1204 1205 if (!entry->data) 1206 entry->data = part; 1207 else { 1208 entry->data = isl_pw_qpolynomial_fold_fold(entry->data, 1209 isl_pw_qpolynomial_fold_copy(part)); 1210 if (!entry->data) 1211 goto error; 1212 isl_pw_qpolynomial_fold_free(part); 1213 } 1214 1215 return u; 1216 error: 1217 isl_pw_qpolynomial_fold_free(part); 1218 isl_union_pw_qpolynomial_fold_free(u); 1219 return NULL; 1220 } 1221 1222 static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user) 1223 { 1224 isl_union_pw_qpolynomial_fold **u; 1225 u = (isl_union_pw_qpolynomial_fold **)user; 1226 1227 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part); 1228 1229 return isl_stat_ok; 1230 } 1231 1232 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold( 1233 __isl_take isl_union_pw_qpolynomial_fold *u1, 1234 __isl_take isl_union_pw_qpolynomial_fold *u2) 1235 { 1236 u1 = isl_union_pw_qpolynomial_fold_cow(u1); 1237 1238 if (!u1 || !u2) 1239 goto error; 1240 1241 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2, 1242 &fold_part, &u1) < 0) 1243 goto error; 1244 1245 isl_union_pw_qpolynomial_fold_free(u2); 1246 1247 return u1; 1248 error: 1249 isl_union_pw_qpolynomial_fold_free(u1); 1250 isl_union_pw_qpolynomial_fold_free(u2); 1251 return NULL; 1252 } 1253 1254 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial( 1255 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp) 1256 { 1257 int i; 1258 isl_pw_qpolynomial_fold *pwf; 1259 1260 if (!pwqp) 1261 return NULL; 1262 1263 pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim), 1264 type, pwqp->n); 1265 1266 for (i = 0; i < pwqp->n; ++i) 1267 pwf = isl_pw_qpolynomial_fold_add_piece(pwf, 1268 isl_set_copy(pwqp->p[i].set), 1269 isl_qpolynomial_fold_alloc(type, 1270 isl_qpolynomial_copy(pwqp->p[i].qp))); 1271 1272 isl_pw_qpolynomial_free(pwqp); 1273 1274 return pwf; 1275 } 1276 1277 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add( 1278 __isl_take isl_pw_qpolynomial_fold *pwf1, 1279 __isl_take isl_pw_qpolynomial_fold *pwf2) 1280 { 1281 return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2); 1282 } 1283 1284 /* Compare two quasi-polynomial reductions. 1285 * 1286 * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater" 1287 * than "fold2" and 0 if they are equal. 1288 */ 1289 int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1, 1290 __isl_keep isl_qpolynomial_fold *fold2) 1291 { 1292 int i; 1293 isl_size n1, n2; 1294 isl_qpolynomial_list *list1, *list2; 1295 1296 if (fold1 == fold2) 1297 return 0; 1298 list1 = isl_qpolynomial_fold_peek_list(fold1); 1299 list2 = isl_qpolynomial_fold_peek_list(fold2); 1300 n1 = isl_qpolynomial_list_size(list1); 1301 n2 = isl_qpolynomial_list_size(list2); 1302 if (n1 < 0) 1303 return -1; 1304 if (n2 < 0) 1305 return 1; 1306 1307 if (n1 != n2) 1308 return n1 - n2; 1309 1310 for (i = 0; i < n1; ++i) { 1311 int cmp; 1312 isl_qpolynomial *qp1, *qp2; 1313 1314 qp1 = isl_qpolynomial_list_peek(list1, i); 1315 qp2 = isl_qpolynomial_list_peek(list2, i); 1316 cmp = isl_qpolynomial_plain_cmp(qp1, qp2); 1317 if (cmp != 0) 1318 return cmp; 1319 } 1320 1321 return 0; 1322 } 1323 1324 /* Are the lists "list1" and "list2", both consisting of "n" elements 1325 * obviously equal to each other? 1326 */ 1327 static isl_bool isl_qpolynomial_list_plain_is_equal(unsigned n, 1328 isl_qpolynomial_list *list1, isl_qpolynomial_list *list2) 1329 { 1330 int i; 1331 1332 for (i = 0; i < n; ++i) { 1333 isl_bool eq; 1334 isl_qpolynomial *qp1, *qp2; 1335 1336 qp1 = isl_qpolynomial_list_peek(list1, i); 1337 qp2 = isl_qpolynomial_list_peek(list2, i); 1338 eq = isl_qpolynomial_plain_is_equal(qp1, qp2); 1339 if (eq < 0 || !eq) 1340 return eq; 1341 } 1342 1343 return isl_bool_true; 1344 } 1345 1346 /* Wrapper around isl_qpolynomial_plain_cmp for use 1347 * as a isl_qpolynomial_list_sort callback. 1348 */ 1349 static int qpolynomial_cmp(__isl_keep isl_qpolynomial *a, 1350 __isl_keep isl_qpolynomial *b, void *user) 1351 { 1352 return isl_qpolynomial_plain_cmp(a, b); 1353 } 1354 1355 isl_bool isl_qpolynomial_fold_plain_is_equal( 1356 __isl_keep isl_qpolynomial_fold *fold1, 1357 __isl_keep isl_qpolynomial_fold *fold2) 1358 { 1359 isl_bool equal; 1360 isl_size n1, n2; 1361 isl_qpolynomial_list *list1, *list2; 1362 1363 list1 = isl_qpolynomial_fold_peek_list(fold1); 1364 list2 = isl_qpolynomial_fold_peek_list(fold2); 1365 n1 = isl_qpolynomial_list_size(list1); 1366 n2 = isl_qpolynomial_list_size(list2); 1367 if (n1 < 0 || n2 < 0) 1368 return isl_bool_error; 1369 1370 if (n1 != n2) 1371 return isl_bool_false; 1372 1373 list1 = isl_qpolynomial_list_copy(list1); 1374 list1 = isl_qpolynomial_list_sort(list1, &qpolynomial_cmp, NULL); 1375 list2 = isl_qpolynomial_list_copy(list2); 1376 list2 = isl_qpolynomial_list_sort(list2, &qpolynomial_cmp, NULL); 1377 equal = isl_qpolynomial_list_plain_is_equal(n1, list1, list2); 1378 isl_qpolynomial_list_free(list1); 1379 isl_qpolynomial_list_free(list2); 1380 return equal; 1381 } 1382 1383 __isl_give isl_val *isl_qpolynomial_fold_eval( 1384 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt) 1385 { 1386 isl_size n; 1387 isl_ctx *ctx; 1388 isl_val *v; 1389 isl_qpolynomial *qp; 1390 isl_qpolynomial_list *list; 1391 1392 if (!fold || !pnt) 1393 goto error; 1394 ctx = isl_point_get_ctx(pnt); 1395 isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error); 1396 isl_assert(pnt->dim->ctx, 1397 fold->type == isl_fold_max || fold->type == isl_fold_min, 1398 goto error); 1399 1400 list = isl_qpolynomial_fold_peek_list(fold); 1401 n = isl_qpolynomial_list_size(list); 1402 if (n < 0) 1403 goto error; 1404 1405 if (n == 0) 1406 v = isl_val_zero(ctx); 1407 else { 1408 int i; 1409 1410 qp = isl_qpolynomial_list_get_at(list, 0); 1411 v = isl_qpolynomial_eval(qp, isl_point_copy(pnt)); 1412 for (i = 1; i < n; ++i) { 1413 isl_val *v_i; 1414 1415 qp = isl_qpolynomial_list_get_at(list, i); 1416 v_i = isl_qpolynomial_eval(qp, isl_point_copy(pnt)); 1417 if (fold->type == isl_fold_max) 1418 v = isl_val_max(v, v_i); 1419 else 1420 v = isl_val_min(v, v_i); 1421 } 1422 } 1423 isl_qpolynomial_fold_free(fold); 1424 isl_point_free(pnt); 1425 1426 return v; 1427 error: 1428 isl_qpolynomial_fold_free(fold); 1429 isl_point_free(pnt); 1430 return NULL; 1431 } 1432 1433 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf) 1434 { 1435 int i; 1436 size_t n = 0; 1437 1438 for (i = 0; i < pwf->n; ++i) { 1439 isl_size n_i; 1440 isl_qpolynomial_list *list; 1441 1442 list = isl_qpolynomial_fold_peek_list(pwf->p[i].fold); 1443 n_i = isl_qpolynomial_list_size(list); 1444 if (n_i < 0) 1445 return isl_size_error; 1446 1447 n += n_i; 1448 } 1449 1450 return n; 1451 } 1452 1453 __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain( 1454 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max) 1455 { 1456 int i; 1457 isl_size n; 1458 isl_val *opt; 1459 isl_qpolynomial *qp; 1460 isl_qpolynomial_list *list; 1461 1462 list = isl_qpolynomial_fold_peek_list(fold); 1463 n = isl_qpolynomial_list_size(list); 1464 if (!set || n < 0) 1465 goto error; 1466 1467 if (n == 0) { 1468 opt = isl_val_zero(isl_set_get_ctx(set)); 1469 isl_set_free(set); 1470 isl_qpolynomial_fold_free(fold); 1471 return opt; 1472 } 1473 1474 qp = isl_qpolynomial_list_get_at(list, 0); 1475 opt = isl_qpolynomial_opt_on_domain(qp, isl_set_copy(set), max); 1476 for (i = 1; i < n; ++i) { 1477 isl_val *opt_i; 1478 1479 qp = isl_qpolynomial_list_get_at(list, i); 1480 opt_i = isl_qpolynomial_opt_on_domain(qp, 1481 isl_set_copy(set), max); 1482 if (max) 1483 opt = isl_val_max(opt, opt_i); 1484 else 1485 opt = isl_val_min(opt, opt_i); 1486 } 1487 1488 isl_set_free(set); 1489 isl_qpolynomial_fold_free(fold); 1490 1491 return opt; 1492 error: 1493 isl_set_free(set); 1494 isl_qpolynomial_fold_free(fold); 1495 return NULL; 1496 } 1497 1498 /* Check whether for each quasi-polynomial in "fold2" there is 1499 * a quasi-polynomial in "fold1" that dominates it on "set". 1500 */ 1501 static isl_bool qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set, 1502 __isl_keep isl_qpolynomial_fold *fold1, 1503 __isl_keep isl_qpolynomial_fold *fold2) 1504 { 1505 int i, j; 1506 int covers; 1507 isl_size n1, n2; 1508 isl_qpolynomial_list *list1, *list2; 1509 1510 list1 = isl_qpolynomial_fold_peek_list(fold1); 1511 list2 = isl_qpolynomial_fold_peek_list(fold2); 1512 n1 = isl_qpolynomial_list_size(list1); 1513 n2 = isl_qpolynomial_list_size(list2); 1514 if (!set || n1 < 0 || n2 < 0) 1515 return isl_bool_error; 1516 1517 covers = fold1->type == isl_fold_max ? 1 : -1; 1518 1519 for (i = 0; i < n2; ++i) { 1520 for (j = 0; j < n1; ++j) { 1521 isl_qpolynomial *qp1, *qp2, *d; 1522 int sgn; 1523 1524 qp1 = isl_qpolynomial_list_get_at(list1, j); 1525 qp2 = isl_qpolynomial_list_get_at(list2, i); 1526 d = isl_qpolynomial_sub(qp1, qp2); 1527 sgn = isl_qpolynomial_sign(set, d); 1528 isl_qpolynomial_free(d); 1529 if (sgn == covers) 1530 break; 1531 } 1532 if (j >= n1) 1533 return isl_bool_false; 1534 } 1535 1536 return isl_bool_true; 1537 } 1538 1539 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains 1540 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates 1541 * that of pwf2. 1542 */ 1543 isl_bool isl_pw_qpolynomial_fold_covers( 1544 __isl_keep isl_pw_qpolynomial_fold *pwf1, 1545 __isl_keep isl_pw_qpolynomial_fold *pwf2) 1546 { 1547 int i, j; 1548 isl_set *dom1, *dom2; 1549 isl_bool is_subset; 1550 1551 if (!pwf1 || !pwf2) 1552 return isl_bool_error; 1553 1554 if (pwf2->n == 0) 1555 return isl_bool_true; 1556 if (pwf1->n == 0) 1557 return isl_bool_false; 1558 1559 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1)); 1560 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2)); 1561 is_subset = isl_set_is_subset(dom2, dom1); 1562 isl_set_free(dom1); 1563 isl_set_free(dom2); 1564 1565 if (is_subset < 0 || !is_subset) 1566 return is_subset; 1567 1568 for (i = 0; i < pwf2->n; ++i) { 1569 for (j = 0; j < pwf1->n; ++j) { 1570 isl_bool is_empty; 1571 isl_set *common; 1572 isl_bool covers; 1573 1574 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set), 1575 isl_set_copy(pwf2->p[i].set)); 1576 is_empty = isl_set_is_empty(common); 1577 if (is_empty < 0 || is_empty) { 1578 isl_set_free(common); 1579 if (is_empty < 0) 1580 return isl_bool_error; 1581 continue; 1582 } 1583 covers = qpolynomial_fold_covers_on_domain(common, 1584 pwf1->p[j].fold, pwf2->p[i].fold); 1585 isl_set_free(common); 1586 if (covers < 0 || !covers) 1587 return covers; 1588 } 1589 } 1590 1591 return isl_bool_true; 1592 } 1593 1594 /* isl_qpolynomial_list_map callback that calls 1595 * isl_qpolynomial_morph_domain on "qp". 1596 */ 1597 static __isl_give isl_qpolynomial *morph_domain( 1598 __isl_take isl_qpolynomial *qp, void *user) 1599 { 1600 isl_morph *morph = user; 1601 1602 return isl_qpolynomial_morph_domain(qp, isl_morph_copy(morph)); 1603 } 1604 1605 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain( 1606 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph) 1607 { 1608 isl_space *space; 1609 isl_qpolynomial_list *list; 1610 1611 space = isl_qpolynomial_fold_peek_domain_space(fold); 1612 if (isl_morph_check_applies(morph, space) < 0) 1613 goto error; 1614 1615 list = isl_qpolynomial_fold_take_list(fold); 1616 list = isl_qpolynomial_list_map(list, &morph_domain, morph); 1617 fold = isl_qpolynomial_fold_restore_list(fold, list); 1618 1619 space = isl_morph_get_ran_space(morph); 1620 isl_space_free(isl_qpolynomial_fold_take_domain_space(fold)); 1621 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 1622 1623 isl_morph_free(morph); 1624 1625 return fold; 1626 error: 1627 isl_qpolynomial_fold_free(fold); 1628 isl_morph_free(morph); 1629 return NULL; 1630 } 1631 1632 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold) 1633 { 1634 if (!fold) 1635 return isl_fold_error; 1636 return fold->type; 1637 } 1638 1639 /* Return the type of this piecewise quasipolynomial reduction. 1640 */ 1641 enum isl_fold isl_pw_qpolynomial_fold_get_type( 1642 __isl_keep isl_pw_qpolynomial_fold *pwf) 1643 { 1644 if (!pwf) 1645 return isl_fold_error; 1646 return pwf->type; 1647 } 1648 1649 enum isl_fold isl_union_pw_qpolynomial_fold_get_type( 1650 __isl_keep isl_union_pw_qpolynomial_fold *upwf) 1651 { 1652 if (!upwf) 1653 return isl_fold_error; 1654 return upwf->type; 1655 } 1656 1657 /* isl_qpolynomial_list_map callback that calls 1658 * isl_qpolynomial_lift on "qp". 1659 */ 1660 static __isl_give isl_qpolynomial *lift(__isl_take isl_qpolynomial *qp, 1661 void *user) 1662 { 1663 isl_space *space = user; 1664 1665 return isl_qpolynomial_lift(qp, isl_space_copy(space)); 1666 } 1667 1668 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift( 1669 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space) 1670 { 1671 isl_qpolynomial_list *list; 1672 1673 if (!fold || !space) 1674 goto error; 1675 1676 if (isl_space_is_equal(fold->dim, space)) { 1677 isl_space_free(space); 1678 return fold; 1679 } 1680 1681 list = isl_qpolynomial_fold_take_list(fold); 1682 list = isl_qpolynomial_list_map(list, &lift, space); 1683 fold = isl_qpolynomial_fold_restore_list(fold, list); 1684 1685 isl_space_free(isl_qpolynomial_fold_take_domain_space(fold)); 1686 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 1687 1688 return fold; 1689 error: 1690 isl_qpolynomial_fold_free(fold); 1691 isl_space_free(space); 1692 return NULL; 1693 } 1694 1695 isl_stat isl_qpolynomial_fold_foreach_qpolynomial( 1696 __isl_keep isl_qpolynomial_fold *fold, 1697 isl_stat (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user) 1698 { 1699 isl_qpolynomial_list *list; 1700 1701 list = isl_qpolynomial_fold_peek_list(fold); 1702 return isl_qpolynomial_list_foreach(list, fn, user); 1703 } 1704 1705 /* Internal data structure for isl_qpolynomial_fold_move_dims 1706 * representing its arguments. 1707 */ 1708 struct isl_fold_move_dims_data { 1709 enum isl_dim_type dst_type; 1710 unsigned dst_pos; 1711 enum isl_dim_type src_type; 1712 unsigned src_pos; 1713 unsigned n; 1714 }; 1715 1716 /* isl_qpolynomial_list_map callback for calling 1717 * isl_qpolynomial_move_dims on "qp". 1718 */ 1719 static __isl_give isl_qpolynomial *move_dims(__isl_take isl_qpolynomial *qp, 1720 void *user) 1721 { 1722 struct isl_fold_move_dims_data *data = user; 1723 1724 qp = isl_qpolynomial_move_dims(qp, data->dst_type, data->dst_pos, 1725 data->src_type, data->src_pos, data->n); 1726 return qp; 1727 } 1728 1729 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims( 1730 __isl_take isl_qpolynomial_fold *fold, 1731 enum isl_dim_type dst_type, unsigned dst_pos, 1732 enum isl_dim_type src_type, unsigned src_pos, unsigned n) 1733 { 1734 struct isl_fold_move_dims_data data = 1735 { dst_type, dst_pos, src_type, src_pos, n }; 1736 enum isl_dim_type set_src_type, set_dst_type; 1737 isl_space *space; 1738 isl_qpolynomial_list *list; 1739 1740 if (n == 0) 1741 return fold; 1742 1743 fold = isl_qpolynomial_fold_cow(fold); 1744 if (!fold) 1745 return NULL; 1746 1747 set_src_type = domain_type(src_type); 1748 set_dst_type = domain_type(dst_type); 1749 1750 list = isl_qpolynomial_fold_take_list(fold); 1751 list = isl_qpolynomial_list_map(list, &move_dims, &data); 1752 fold = isl_qpolynomial_fold_restore_list(fold, list); 1753 1754 space = isl_qpolynomial_fold_take_domain_space(fold); 1755 space = isl_space_move_dims(space, set_dst_type, dst_pos, 1756 set_src_type, src_pos, n); 1757 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 1758 1759 return fold; 1760 } 1761 1762 /* Internal data structure for isl_qpolynomial_fold_substitute 1763 * representing its arguments. 1764 */ 1765 struct isl_fold_substitute { 1766 enum isl_dim_type type; 1767 unsigned first; 1768 unsigned n; 1769 isl_qpolynomial **subs; 1770 }; 1771 1772 /* isl_qpolynomial_list_map callback for calling 1773 * isl_qpolynomial_substitute on "qp". 1774 */ 1775 static __isl_give isl_qpolynomial *substitute(__isl_take isl_qpolynomial *qp, 1776 void *user) 1777 { 1778 struct isl_fold_substitute *data = user; 1779 1780 qp = isl_qpolynomial_substitute(qp, 1781 data->type, data->first, data->n, data->subs); 1782 return qp; 1783 } 1784 1785 /* For each 0 <= i < "n", replace variable "first" + i of type "type" 1786 * in fold->qp[k] by subs[i]. 1787 */ 1788 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute( 1789 __isl_take isl_qpolynomial_fold *fold, 1790 enum isl_dim_type type, unsigned first, unsigned n, 1791 __isl_keep isl_qpolynomial **subs) 1792 { 1793 struct isl_fold_substitute data = { type, first, n, subs }; 1794 isl_qpolynomial_list *list; 1795 1796 if (n == 0) 1797 return fold; 1798 1799 list = isl_qpolynomial_fold_take_list(fold); 1800 list = isl_qpolynomial_list_map(list, &substitute, &data); 1801 fold = isl_qpolynomial_fold_restore_list(fold, list); 1802 1803 return fold; 1804 } 1805 1806 static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user) 1807 { 1808 isl_pw_qpolynomial_fold *pwf; 1809 isl_union_pw_qpolynomial_fold **upwf; 1810 struct isl_hash_table_entry *entry; 1811 1812 upwf = (isl_union_pw_qpolynomial_fold **)user; 1813 1814 entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf, 1815 pwqp->dim, 1); 1816 if (!entry) 1817 goto error; 1818 1819 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp); 1820 if (!entry->data) 1821 entry->data = pwf; 1822 else { 1823 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf); 1824 if (!entry->data) 1825 return isl_stat_error; 1826 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) 1827 *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry( 1828 *upwf, entry); 1829 } 1830 1831 return isl_stat_ok; 1832 error: 1833 isl_pw_qpolynomial_free(pwqp); 1834 return isl_stat_error; 1835 } 1836 1837 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial( 1838 __isl_take isl_union_pw_qpolynomial_fold *upwf, 1839 __isl_take isl_union_pw_qpolynomial *upwqp) 1840 { 1841 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, 1842 isl_union_pw_qpolynomial_get_space(upwqp)); 1843 upwqp = isl_union_pw_qpolynomial_align_params(upwqp, 1844 isl_union_pw_qpolynomial_fold_get_space(upwf)); 1845 1846 upwf = isl_union_pw_qpolynomial_fold_cow(upwf); 1847 if (!upwf || !upwqp) 1848 goto error; 1849 1850 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp, 1851 &upwf) < 0) 1852 goto error; 1853 1854 isl_union_pw_qpolynomial_free(upwqp); 1855 1856 return upwf; 1857 error: 1858 isl_union_pw_qpolynomial_fold_free(upwf); 1859 isl_union_pw_qpolynomial_free(upwqp); 1860 return NULL; 1861 } 1862 1863 static isl_bool join_compatible(__isl_keep isl_space *space1, 1864 __isl_keep isl_space *space2) 1865 { 1866 isl_bool m; 1867 m = isl_space_has_equal_params(space1, space2); 1868 if (m < 0 || !m) 1869 return m; 1870 return isl_space_tuple_is_equal(space1, isl_dim_out, 1871 space2, isl_dim_in); 1872 } 1873 1874 /* Compute the intersection of the range of the map and the domain 1875 * of the piecewise quasipolynomial reduction and then compute a bound 1876 * on the associated quasipolynomial reduction over all elements 1877 * in this intersection. 1878 * 1879 * We first introduce some unconstrained dimensions in the 1880 * piecewise quasipolynomial, intersect the resulting domain 1881 * with the wrapped map and the compute the sum. 1882 */ 1883 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold( 1884 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf, 1885 isl_bool *tight) 1886 { 1887 isl_ctx *ctx; 1888 isl_set *dom; 1889 isl_space *map_space; 1890 isl_space *pwf_space; 1891 isl_size n_in; 1892 isl_bool ok; 1893 1894 ctx = isl_map_get_ctx(map); 1895 if (!ctx) 1896 goto error; 1897 1898 map_space = isl_map_get_space(map); 1899 pwf_space = isl_pw_qpolynomial_fold_get_space(pwf); 1900 ok = join_compatible(map_space, pwf_space); 1901 isl_space_free(map_space); 1902 isl_space_free(pwf_space); 1903 if (ok < 0) 1904 goto error; 1905 if (!ok) 1906 isl_die(ctx, isl_error_invalid, "incompatible dimensions", 1907 goto error); 1908 1909 n_in = isl_map_dim(map, isl_dim_in); 1910 if (n_in < 0) 1911 goto error; 1912 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in); 1913 1914 dom = isl_map_wrap(map); 1915 pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf, 1916 isl_set_get_space(dom)); 1917 1918 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom); 1919 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight); 1920 1921 return pwf; 1922 error: 1923 isl_map_free(map); 1924 isl_pw_qpolynomial_fold_free(pwf); 1925 return NULL; 1926 } 1927 1928 __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold( 1929 __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf, 1930 isl_bool *tight) 1931 { 1932 return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight); 1933 } 1934 1935 struct isl_apply_fold_data { 1936 isl_union_pw_qpolynomial_fold *upwf; 1937 isl_union_pw_qpolynomial_fold *res; 1938 isl_map *map; 1939 isl_bool tight; 1940 }; 1941 1942 static isl_stat pw_qpolynomial_fold_apply( 1943 __isl_take isl_pw_qpolynomial_fold *pwf, void *user) 1944 { 1945 isl_space *map_dim; 1946 isl_space *pwf_dim; 1947 struct isl_apply_fold_data *data = user; 1948 isl_bool ok; 1949 1950 map_dim = isl_map_get_space(data->map); 1951 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf); 1952 ok = join_compatible(map_dim, pwf_dim); 1953 isl_space_free(map_dim); 1954 isl_space_free(pwf_dim); 1955 1956 if (ok < 0) 1957 return isl_stat_error; 1958 if (ok) { 1959 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map), 1960 pwf, data->tight ? &data->tight : NULL); 1961 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 1962 data->res, pwf); 1963 } else 1964 isl_pw_qpolynomial_fold_free(pwf); 1965 1966 return isl_stat_ok; 1967 } 1968 1969 static isl_stat map_apply(__isl_take isl_map *map, void *user) 1970 { 1971 struct isl_apply_fold_data *data = user; 1972 isl_stat r; 1973 1974 data->map = map; 1975 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold( 1976 data->upwf, &pw_qpolynomial_fold_apply, data); 1977 1978 isl_map_free(map); 1979 return r; 1980 } 1981 1982 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold( 1983 __isl_take isl_union_map *umap, 1984 __isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight) 1985 { 1986 isl_space *space; 1987 enum isl_fold type; 1988 struct isl_apply_fold_data data; 1989 1990 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, 1991 isl_union_map_get_space(umap)); 1992 umap = isl_union_map_align_params(umap, 1993 isl_union_pw_qpolynomial_fold_get_space(upwf)); 1994 1995 data.upwf = upwf; 1996 data.tight = tight ? isl_bool_true : isl_bool_false; 1997 space = isl_union_pw_qpolynomial_fold_get_space(upwf); 1998 type = isl_union_pw_qpolynomial_fold_get_type(upwf); 1999 data.res = isl_union_pw_qpolynomial_fold_zero(space, type); 2000 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0) 2001 goto error; 2002 2003 isl_union_map_free(umap); 2004 isl_union_pw_qpolynomial_fold_free(upwf); 2005 2006 if (tight) 2007 *tight = data.tight; 2008 2009 return data.res; 2010 error: 2011 isl_union_map_free(umap); 2012 isl_union_pw_qpolynomial_fold_free(upwf); 2013 isl_union_pw_qpolynomial_fold_free(data.res); 2014 return NULL; 2015 } 2016 2017 __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold( 2018 __isl_take isl_union_set *uset, 2019 __isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight) 2020 { 2021 return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight); 2022 } 2023 2024 /* isl_qpolynomial_list_map callback for calling 2025 * isl_qpolynomial_realign_domain on "qp". 2026 */ 2027 static __isl_give isl_qpolynomial *realign_domain( 2028 __isl_take isl_qpolynomial *qp, void *user) 2029 { 2030 isl_reordering *r = user; 2031 2032 qp = isl_qpolynomial_realign_domain(qp, isl_reordering_copy(r)); 2033 return qp; 2034 } 2035 2036 /* Reorder the dimension of "fold" according to the given reordering. 2037 */ 2038 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain( 2039 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r) 2040 { 2041 isl_space *space; 2042 isl_qpolynomial_list *list; 2043 2044 list = isl_qpolynomial_fold_take_list(fold); 2045 list = isl_qpolynomial_list_map(list, &realign_domain, r); 2046 fold = isl_qpolynomial_fold_restore_list(fold, list); 2047 2048 space = isl_reordering_get_space(r); 2049 fold = isl_qpolynomial_fold_reset_domain_space(fold, space); 2050 2051 isl_reordering_free(r); 2052 2053 return fold; 2054 } 2055 2056 /* isl_qpolynomial_list_map callback for calling 2057 * isl_qpolynomial_mul_isl_int on "qp". 2058 */ 2059 static __isl_give isl_qpolynomial *mul_int(__isl_take isl_qpolynomial *qp, 2060 void *user) 2061 { 2062 isl_int *v = user; 2063 2064 qp = isl_qpolynomial_mul_isl_int(qp, *v); 2065 return qp; 2066 } 2067 2068 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int( 2069 __isl_take isl_qpolynomial_fold *fold, isl_int v) 2070 { 2071 isl_qpolynomial_list *list; 2072 2073 if (isl_int_is_one(v)) 2074 return fold; 2075 if (fold && isl_int_is_zero(v)) { 2076 isl_qpolynomial_fold *zero; 2077 isl_space *space = isl_space_copy(fold->dim); 2078 zero = isl_qpolynomial_fold_empty(fold->type, space); 2079 isl_qpolynomial_fold_free(fold); 2080 return zero; 2081 } 2082 2083 fold = isl_qpolynomial_fold_cow(fold); 2084 if (!fold) 2085 return NULL; 2086 2087 if (isl_int_is_neg(v)) 2088 fold->type = isl_fold_type_negate(fold->type); 2089 2090 list = isl_qpolynomial_fold_take_list(fold); 2091 list = isl_qpolynomial_list_map(list, &mul_int, &v); 2092 fold = isl_qpolynomial_fold_restore_list(fold, list); 2093 2094 return fold; 2095 } 2096 2097 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale( 2098 __isl_take isl_qpolynomial_fold *fold, isl_int v) 2099 { 2100 return isl_qpolynomial_fold_mul_isl_int(fold, v); 2101 } 2102 2103 /* isl_qpolynomial_list_map callback for calling 2104 * isl_qpolynomial_scale_val on "qp". 2105 */ 2106 static __isl_give isl_qpolynomial *scale_val(__isl_take isl_qpolynomial *qp, 2107 void *user) 2108 { 2109 isl_val *v = user; 2110 2111 qp = isl_qpolynomial_scale_val(qp, isl_val_copy(v)); 2112 return qp; 2113 } 2114 2115 /* Multiply "fold" by "v". 2116 */ 2117 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val( 2118 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) 2119 { 2120 isl_qpolynomial_list *list; 2121 2122 if (!fold || !v) 2123 goto error; 2124 2125 if (isl_val_is_one(v)) { 2126 isl_val_free(v); 2127 return fold; 2128 } 2129 if (isl_val_is_zero(v)) { 2130 isl_qpolynomial_fold *zero; 2131 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); 2132 zero = isl_qpolynomial_fold_empty(fold->type, space); 2133 isl_qpolynomial_fold_free(fold); 2134 isl_val_free(v); 2135 return zero; 2136 } 2137 if (!isl_val_is_rat(v)) 2138 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid, 2139 "expecting rational factor", goto error); 2140 2141 fold = isl_qpolynomial_fold_cow(fold); 2142 if (!fold) 2143 goto error; 2144 2145 if (isl_val_is_neg(v)) 2146 fold->type = isl_fold_type_negate(fold->type); 2147 2148 list = isl_qpolynomial_fold_take_list(fold); 2149 list = isl_qpolynomial_list_map(list, &scale_val, v); 2150 fold = isl_qpolynomial_fold_restore_list(fold, list); 2151 2152 isl_val_free(v); 2153 return fold; 2154 error: 2155 isl_val_free(v); 2156 isl_qpolynomial_fold_free(fold); 2157 return NULL; 2158 } 2159 2160 /* Divide "fold" by "v". 2161 */ 2162 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_down_val( 2163 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) 2164 { 2165 if (!fold || !v) 2166 goto error; 2167 2168 if (isl_val_is_one(v)) { 2169 isl_val_free(v); 2170 return fold; 2171 } 2172 if (!isl_val_is_rat(v)) 2173 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid, 2174 "expecting rational factor", goto error); 2175 if (isl_val_is_zero(v)) 2176 isl_die(isl_val_get_ctx(v), isl_error_invalid, 2177 "cannot scale down by zero", goto error); 2178 2179 return isl_qpolynomial_fold_scale_val(fold, isl_val_inv(v)); 2180 error: 2181 isl_val_free(v); 2182 isl_qpolynomial_fold_free(fold); 2183 return NULL; 2184 } 2185
Indexes created Sat Jun 27 00:24:51 UTC 2026