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_eval.c> 955 #include <isl_pw_insert_dims_templ.c> 956 #include <isl_pw_lift_templ.c> 957 #include <isl_pw_morph_templ.c> 958 #include <isl_pw_move_dims_templ.c> 959 #include <isl_pw_opt_templ.c> 960 961 #undef BASE 962 #define BASE pw_qpolynomial_fold 963 964 #define NO_SUB 965 966 #include <isl_union_single.c> 967 #include <isl_union_eval.c> 968 969 /* Construct a new reduction of the given type and space 970 * with an empty list of polynomials. 971 */ 972 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type, 973 __isl_take isl_space *space) 974 { 975 isl_ctx *ctx; 976 isl_qpolynomial_list *list; 977 978 if (!space) 979 return NULL; 980 ctx = isl_space_get_ctx(space); 981 list = isl_qpolynomial_list_alloc(ctx, 0); 982 return qpolynomial_fold_alloc(type, space, list); 983 } 984 985 /* Construct a new reduction of the given type and 986 * a single given polynomial. 987 */ 988 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc( 989 enum isl_fold type, __isl_take isl_qpolynomial *qp) 990 { 991 isl_space *space; 992 isl_qpolynomial_list *list; 993 994 space = isl_qpolynomial_get_domain_space(qp); 995 list = isl_qpolynomial_list_from_qpolynomial(qp); 996 return qpolynomial_fold_alloc(type, space, list); 997 } 998 999 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy( 1000 __isl_keep isl_qpolynomial_fold *fold) 1001 { 1002 if (!fold) 1003 return NULL; 1004 1005 fold->ref++; 1006 return fold; 1007 } 1008 1009 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup( 1010 __isl_keep isl_qpolynomial_fold *fold) 1011 { 1012 enum isl_fold type; 1013 isl_space *space; 1014 isl_qpolynomial_list *list; 1015 1016 type = isl_qpolynomial_fold_get_type(fold); 1017 space = isl_qpolynomial_fold_get_domain_space(fold); 1018 list = isl_qpolynomial_fold_get_list(fold); 1019 return qpolynomial_fold_alloc(type, space, list); 1020 } 1021 1022 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow( 1023 __isl_take isl_qpolynomial_fold *fold) 1024 { 1025 if (!fold) 1026 return NULL; 1027 1028 if (fold->ref == 1) 1029 return fold; 1030 fold->ref--; 1031 return isl_qpolynomial_fold_dup(fold); 1032 } 1033 1034 __isl_null isl_qpolynomial_fold *isl_qpolynomial_fold_free( 1035 __isl_take isl_qpolynomial_fold *fold) 1036 { 1037 if (!fold) 1038 return NULL; 1039 if (--fold->ref > 0) 1040 return NULL; 1041 1042 isl_qpolynomial_list_free(fold->list); 1043 isl_space_free(fold->dim); 1044 free(fold); 1045 1046 return NULL; 1047 } 1048 1049 isl_bool isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold) 1050 { 1051 isl_size n; 1052 isl_qpolynomial_list *list; 1053 1054 list = isl_qpolynomial_fold_peek_list(fold); 1055 n = isl_qpolynomial_list_size(list); 1056 if (n < 0) 1057 return isl_bool_error; 1058 1059 return isl_bool_ok(n == 0); 1060 } 1061 1062 /* Does "fold" represent max(NaN) or min(NaN)? 1063 */ 1064 isl_bool isl_qpolynomial_fold_is_nan(__isl_keep isl_qpolynomial_fold *fold) 1065 { 1066 isl_size n; 1067 isl_qpolynomial *qp; 1068 isl_qpolynomial_list *list; 1069 1070 list = isl_qpolynomial_fold_peek_list(fold); 1071 n = isl_qpolynomial_list_size(list); 1072 if (n < 0) 1073 return isl_bool_error; 1074 if (n != 1) 1075 return isl_bool_false; 1076 qp = isl_qpolynomial_list_peek(list, 0); 1077 return isl_qpolynomial_is_nan(qp); 1078 } 1079 1080 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold( 1081 __isl_take isl_qpolynomial_fold *fold1, 1082 __isl_take isl_qpolynomial_fold *fold2) 1083 { 1084 isl_qpolynomial_list *list1, *list2; 1085 1086 if (isl_qpolynomial_fold_check_equal_type(fold1, fold2) < 0) 1087 goto error; 1088 if (isl_qpolynomial_fold_check_equal_space(fold1, fold2) < 0) 1089 goto error; 1090 1091 if (isl_qpolynomial_fold_is_empty(fold1)) { 1092 isl_qpolynomial_fold_free(fold1); 1093 return fold2; 1094 } 1095 1096 if (isl_qpolynomial_fold_is_empty(fold2)) { 1097 isl_qpolynomial_fold_free(fold2); 1098 return fold1; 1099 } 1100 1101 list1 = isl_qpolynomial_fold_take_list(fold1); 1102 list2 = isl_qpolynomial_fold_take_list(fold2); 1103 list1 = isl_qpolynomial_list_concat(list1, list2); 1104 fold1 = isl_qpolynomial_fold_restore_list(fold1, list1); 1105 isl_qpolynomial_fold_free(fold2); 1106 1107 return fold1; 1108 error: 1109 isl_qpolynomial_fold_free(fold1); 1110 isl_qpolynomial_fold_free(fold2); 1111 return NULL; 1112 } 1113 1114 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold( 1115 __isl_take isl_pw_qpolynomial_fold *pw1, 1116 __isl_take isl_pw_qpolynomial_fold *pw2) 1117 { 1118 int i, j, n; 1119 struct isl_pw_qpolynomial_fold *res; 1120 isl_set *set; 1121 1122 if (!pw1 || !pw2) 1123 goto error; 1124 1125 isl_assert(pw1->dim->ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error); 1126 1127 if (isl_pw_qpolynomial_fold_is_zero(pw1)) { 1128 isl_pw_qpolynomial_fold_free(pw1); 1129 return pw2; 1130 } 1131 1132 if (isl_pw_qpolynomial_fold_is_zero(pw2)) { 1133 isl_pw_qpolynomial_fold_free(pw2); 1134 return pw1; 1135 } 1136 1137 if (pw1->type != pw2->type) 1138 isl_die(pw1->dim->ctx, isl_error_invalid, 1139 "fold types don't match", goto error); 1140 1141 n = (pw1->n + 1) * (pw2->n + 1); 1142 res = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pw1->dim), 1143 pw1->type, n); 1144 1145 for (i = 0; i < pw1->n; ++i) { 1146 set = isl_set_copy(pw1->p[i].set); 1147 for (j = 0; j < pw2->n; ++j) { 1148 struct isl_set *common; 1149 isl_qpolynomial_fold *sum; 1150 set = isl_set_subtract(set, 1151 isl_set_copy(pw2->p[j].set)); 1152 common = isl_set_intersect(isl_set_copy(pw1->p[i].set), 1153 isl_set_copy(pw2->p[j].set)); 1154 if (isl_set_plain_is_empty(common)) { 1155 isl_set_free(common); 1156 continue; 1157 } 1158 1159 sum = isl_qpolynomial_fold_fold_on_domain(common, 1160 isl_qpolynomial_fold_copy(pw1->p[i].fold), 1161 isl_qpolynomial_fold_copy(pw2->p[j].fold)); 1162 1163 res = isl_pw_qpolynomial_fold_add_piece(res, common, sum); 1164 } 1165 res = isl_pw_qpolynomial_fold_add_piece(res, set, 1166 isl_qpolynomial_fold_copy(pw1->p[i].fold)); 1167 } 1168 1169 for (j = 0; j < pw2->n; ++j) { 1170 set = isl_set_copy(pw2->p[j].set); 1171 for (i = 0; i < pw1->n; ++i) 1172 set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set)); 1173 res = isl_pw_qpolynomial_fold_add_piece(res, set, 1174 isl_qpolynomial_fold_copy(pw2->p[j].fold)); 1175 } 1176 1177 isl_pw_qpolynomial_fold_free(pw1); 1178 isl_pw_qpolynomial_fold_free(pw2); 1179 1180 return res; 1181 error: 1182 isl_pw_qpolynomial_fold_free(pw1); 1183 isl_pw_qpolynomial_fold_free(pw2); 1184 return NULL; 1185 } 1186 1187 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 1188 __isl_take isl_union_pw_qpolynomial_fold *u, 1189 __isl_take isl_pw_qpolynomial_fold *part) 1190 { 1191 struct isl_hash_table_entry *entry; 1192 1193 u = isl_union_pw_qpolynomial_fold_cow(u); 1194 1195 if (!part || !u) 1196 goto error; 1197 if (isl_space_check_equal_params(part->dim, u->space) < 0) 1198 goto error; 1199 1200 entry = isl_union_pw_qpolynomial_fold_find_part_entry(u, part->dim, 1); 1201 if (!entry) 1202 goto error; 1203 1204 if (!entry->data) 1205 entry->data = part; 1206 else { 1207 entry->data = isl_pw_qpolynomial_fold_fold(entry->data, 1208 isl_pw_qpolynomial_fold_copy(part)); 1209 if (!entry->data) 1210 goto error; 1211 isl_pw_qpolynomial_fold_free(part); 1212 } 1213 1214 return u; 1215 error: 1216 isl_pw_qpolynomial_fold_free(part); 1217 isl_union_pw_qpolynomial_fold_free(u); 1218 return NULL; 1219 } 1220 1221 static isl_stat fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user) 1222 { 1223 isl_union_pw_qpolynomial_fold **u; 1224 u = (isl_union_pw_qpolynomial_fold **)user; 1225 1226 *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part); 1227 1228 return isl_stat_ok; 1229 } 1230 1231 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold( 1232 __isl_take isl_union_pw_qpolynomial_fold *u1, 1233 __isl_take isl_union_pw_qpolynomial_fold *u2) 1234 { 1235 u1 = isl_union_pw_qpolynomial_fold_cow(u1); 1236 1237 if (!u1 || !u2) 1238 goto error; 1239 1240 if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2, 1241 &fold_part, &u1) < 0) 1242 goto error; 1243 1244 isl_union_pw_qpolynomial_fold_free(u2); 1245 1246 return u1; 1247 error: 1248 isl_union_pw_qpolynomial_fold_free(u1); 1249 isl_union_pw_qpolynomial_fold_free(u2); 1250 return NULL; 1251 } 1252 1253 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial( 1254 enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp) 1255 { 1256 int i; 1257 isl_pw_qpolynomial_fold *pwf; 1258 1259 if (!pwqp) 1260 return NULL; 1261 1262 pwf = isl_pw_qpolynomial_fold_alloc_size(isl_space_copy(pwqp->dim), 1263 type, pwqp->n); 1264 1265 for (i = 0; i < pwqp->n; ++i) 1266 pwf = isl_pw_qpolynomial_fold_add_piece(pwf, 1267 isl_set_copy(pwqp->p[i].set), 1268 isl_qpolynomial_fold_alloc(type, 1269 isl_qpolynomial_copy(pwqp->p[i].qp))); 1270 1271 isl_pw_qpolynomial_free(pwqp); 1272 1273 return pwf; 1274 } 1275 1276 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add( 1277 __isl_take isl_pw_qpolynomial_fold *pwf1, 1278 __isl_take isl_pw_qpolynomial_fold *pwf2) 1279 { 1280 return isl_pw_qpolynomial_fold_union_add_(pwf1, pwf2); 1281 } 1282 1283 /* Compare two quasi-polynomial reductions. 1284 * 1285 * Return -1 if "fold1" is "smaller" than "fold2", 1 if "fold1" is "greater" 1286 * than "fold2" and 0 if they are equal. 1287 */ 1288 int isl_qpolynomial_fold_plain_cmp(__isl_keep isl_qpolynomial_fold *fold1, 1289 __isl_keep isl_qpolynomial_fold *fold2) 1290 { 1291 int i; 1292 isl_size n1, n2; 1293 isl_qpolynomial_list *list1, *list2; 1294 1295 if (fold1 == fold2) 1296 return 0; 1297 list1 = isl_qpolynomial_fold_peek_list(fold1); 1298 list2 = isl_qpolynomial_fold_peek_list(fold2); 1299 n1 = isl_qpolynomial_list_size(list1); 1300 n2 = isl_qpolynomial_list_size(list2); 1301 if (n1 < 0) 1302 return -1; 1303 if (n2 < 0) 1304 return 1; 1305 1306 if (n1 != n2) 1307 return n1 - n2; 1308 1309 for (i = 0; i < n1; ++i) { 1310 int cmp; 1311 isl_qpolynomial *qp1, *qp2; 1312 1313 qp1 = isl_qpolynomial_list_peek(list1, i); 1314 qp2 = isl_qpolynomial_list_peek(list2, i); 1315 cmp = isl_qpolynomial_plain_cmp(qp1, qp2); 1316 if (cmp != 0) 1317 return cmp; 1318 } 1319 1320 return 0; 1321 } 1322 1323 /* Are the lists "list1" and "list2", both consisting of "n" elements 1324 * obviously equal to each other? 1325 */ 1326 static isl_bool isl_qpolynomial_list_plain_is_equal(unsigned n, 1327 isl_qpolynomial_list *list1, isl_qpolynomial_list *list2) 1328 { 1329 int i; 1330 1331 for (i = 0; i < n; ++i) { 1332 isl_bool eq; 1333 isl_qpolynomial *qp1, *qp2; 1334 1335 qp1 = isl_qpolynomial_list_peek(list1, i); 1336 qp2 = isl_qpolynomial_list_peek(list2, i); 1337 eq = isl_qpolynomial_plain_is_equal(qp1, qp2); 1338 if (eq < 0 || !eq) 1339 return eq; 1340 } 1341 1342 return isl_bool_true; 1343 } 1344 1345 /* Wrapper around isl_qpolynomial_plain_cmp for use 1346 * as a isl_qpolynomial_list_sort callback. 1347 */ 1348 static int qpolynomial_cmp(__isl_keep isl_qpolynomial *a, 1349 __isl_keep isl_qpolynomial *b, void *user) 1350 { 1351 return isl_qpolynomial_plain_cmp(a, b); 1352 } 1353 1354 isl_bool isl_qpolynomial_fold_plain_is_equal( 1355 __isl_keep isl_qpolynomial_fold *fold1, 1356 __isl_keep isl_qpolynomial_fold *fold2) 1357 { 1358 isl_bool equal; 1359 isl_size n1, n2; 1360 isl_qpolynomial_list *list1, *list2; 1361 1362 list1 = isl_qpolynomial_fold_peek_list(fold1); 1363 list2 = isl_qpolynomial_fold_peek_list(fold2); 1364 n1 = isl_qpolynomial_list_size(list1); 1365 n2 = isl_qpolynomial_list_size(list2); 1366 if (n1 < 0 || n2 < 0) 1367 return isl_bool_error; 1368 1369 if (n1 != n2) 1370 return isl_bool_false; 1371 1372 list1 = isl_qpolynomial_list_copy(list1); 1373 list1 = isl_qpolynomial_list_sort(list1, &qpolynomial_cmp, NULL); 1374 list2 = isl_qpolynomial_list_copy(list2); 1375 list2 = isl_qpolynomial_list_sort(list2, &qpolynomial_cmp, NULL); 1376 equal = isl_qpolynomial_list_plain_is_equal(n1, list1, list2); 1377 isl_qpolynomial_list_free(list1); 1378 isl_qpolynomial_list_free(list2); 1379 return equal; 1380 } 1381 1382 __isl_give isl_val *isl_qpolynomial_fold_eval( 1383 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt) 1384 { 1385 isl_size n; 1386 isl_ctx *ctx; 1387 isl_val *v; 1388 isl_qpolynomial *qp; 1389 isl_qpolynomial_list *list; 1390 1391 if (!fold || !pnt) 1392 goto error; 1393 ctx = isl_point_get_ctx(pnt); 1394 isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, fold->dim), goto error); 1395 isl_assert(pnt->dim->ctx, 1396 fold->type == isl_fold_max || fold->type == isl_fold_min, 1397 goto error); 1398 1399 list = isl_qpolynomial_fold_peek_list(fold); 1400 n = isl_qpolynomial_list_size(list); 1401 if (n < 0) 1402 goto error; 1403 1404 if (n == 0) 1405 v = isl_val_zero(ctx); 1406 else { 1407 int i; 1408 1409 qp = isl_qpolynomial_list_get_at(list, 0); 1410 v = isl_qpolynomial_eval(qp, isl_point_copy(pnt)); 1411 for (i = 1; i < n; ++i) { 1412 isl_val *v_i; 1413 1414 qp = isl_qpolynomial_list_get_at(list, i); 1415 v_i = isl_qpolynomial_eval(qp, isl_point_copy(pnt)); 1416 if (fold->type == isl_fold_max) 1417 v = isl_val_max(v, v_i); 1418 else 1419 v = isl_val_min(v, v_i); 1420 } 1421 } 1422 isl_qpolynomial_fold_free(fold); 1423 isl_point_free(pnt); 1424 1425 return v; 1426 error: 1427 isl_qpolynomial_fold_free(fold); 1428 isl_point_free(pnt); 1429 return NULL; 1430 } 1431 1432 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf) 1433 { 1434 int i; 1435 size_t n = 0; 1436 1437 for (i = 0; i < pwf->n; ++i) { 1438 isl_size n_i; 1439 isl_qpolynomial_list *list; 1440 1441 list = isl_qpolynomial_fold_peek_list(pwf->p[i].fold); 1442 n_i = isl_qpolynomial_list_size(list); 1443 if (n_i < 0) 1444 return isl_size_error; 1445 1446 n += n_i; 1447 } 1448 1449 return n; 1450 } 1451 1452 __isl_give isl_val *isl_qpolynomial_fold_opt_on_domain( 1453 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max) 1454 { 1455 int i; 1456 isl_size n; 1457 isl_val *opt; 1458 isl_qpolynomial *qp; 1459 isl_qpolynomial_list *list; 1460 1461 list = isl_qpolynomial_fold_peek_list(fold); 1462 n = isl_qpolynomial_list_size(list); 1463 if (!set || n < 0) 1464 goto error; 1465 1466 if (n == 0) { 1467 opt = isl_val_zero(isl_set_get_ctx(set)); 1468 isl_set_free(set); 1469 isl_qpolynomial_fold_free(fold); 1470 return opt; 1471 } 1472 1473 qp = isl_qpolynomial_list_get_at(list, 0); 1474 opt = isl_qpolynomial_opt_on_domain(qp, isl_set_copy(set), max); 1475 for (i = 1; i < n; ++i) { 1476 isl_val *opt_i; 1477 1478 qp = isl_qpolynomial_list_get_at(list, i); 1479 opt_i = isl_qpolynomial_opt_on_domain(qp, 1480 isl_set_copy(set), max); 1481 if (max) 1482 opt = isl_val_max(opt, opt_i); 1483 else 1484 opt = isl_val_min(opt, opt_i); 1485 } 1486 1487 isl_set_free(set); 1488 isl_qpolynomial_fold_free(fold); 1489 1490 return opt; 1491 error: 1492 isl_set_free(set); 1493 isl_qpolynomial_fold_free(fold); 1494 return NULL; 1495 } 1496 1497 /* Check whether for each quasi-polynomial in "fold2" there is 1498 * a quasi-polynomial in "fold1" that dominates it on "set". 1499 */ 1500 static isl_bool qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set, 1501 __isl_keep isl_qpolynomial_fold *fold1, 1502 __isl_keep isl_qpolynomial_fold *fold2) 1503 { 1504 int i, j; 1505 int covers; 1506 isl_size n1, n2; 1507 isl_qpolynomial_list *list1, *list2; 1508 1509 list1 = isl_qpolynomial_fold_peek_list(fold1); 1510 list2 = isl_qpolynomial_fold_peek_list(fold2); 1511 n1 = isl_qpolynomial_list_size(list1); 1512 n2 = isl_qpolynomial_list_size(list2); 1513 if (!set || n1 < 0 || n2 < 0) 1514 return isl_bool_error; 1515 1516 covers = fold1->type == isl_fold_max ? 1 : -1; 1517 1518 for (i = 0; i < n2; ++i) { 1519 for (j = 0; j < n1; ++j) { 1520 isl_qpolynomial *qp1, *qp2, *d; 1521 int sgn; 1522 1523 qp1 = isl_qpolynomial_list_get_at(list1, j); 1524 qp2 = isl_qpolynomial_list_get_at(list2, i); 1525 d = isl_qpolynomial_sub(qp1, qp2); 1526 sgn = isl_qpolynomial_sign(set, d); 1527 isl_qpolynomial_free(d); 1528 if (sgn == covers) 1529 break; 1530 } 1531 if (j >= n1) 1532 return isl_bool_false; 1533 } 1534 1535 return isl_bool_true; 1536 } 1537 1538 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains 1539 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates 1540 * that of pwf2. 1541 */ 1542 isl_bool isl_pw_qpolynomial_fold_covers( 1543 __isl_keep isl_pw_qpolynomial_fold *pwf1, 1544 __isl_keep isl_pw_qpolynomial_fold *pwf2) 1545 { 1546 int i, j; 1547 isl_set *dom1, *dom2; 1548 isl_bool is_subset; 1549 1550 if (!pwf1 || !pwf2) 1551 return isl_bool_error; 1552 1553 if (pwf2->n == 0) 1554 return isl_bool_true; 1555 if (pwf1->n == 0) 1556 return isl_bool_false; 1557 1558 dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1)); 1559 dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2)); 1560 is_subset = isl_set_is_subset(dom2, dom1); 1561 isl_set_free(dom1); 1562 isl_set_free(dom2); 1563 1564 if (is_subset < 0 || !is_subset) 1565 return is_subset; 1566 1567 for (i = 0; i < pwf2->n; ++i) { 1568 for (j = 0; j < pwf1->n; ++j) { 1569 isl_bool is_empty; 1570 isl_set *common; 1571 isl_bool covers; 1572 1573 common = isl_set_intersect(isl_set_copy(pwf1->p[j].set), 1574 isl_set_copy(pwf2->p[i].set)); 1575 is_empty = isl_set_is_empty(common); 1576 if (is_empty < 0 || is_empty) { 1577 isl_set_free(common); 1578 if (is_empty < 0) 1579 return isl_bool_error; 1580 continue; 1581 } 1582 covers = qpolynomial_fold_covers_on_domain(common, 1583 pwf1->p[j].fold, pwf2->p[i].fold); 1584 isl_set_free(common); 1585 if (covers < 0 || !covers) 1586 return covers; 1587 } 1588 } 1589 1590 return isl_bool_true; 1591 } 1592 1593 /* isl_qpolynomial_list_map callback that calls 1594 * isl_qpolynomial_morph_domain on "qp". 1595 */ 1596 static __isl_give isl_qpolynomial *morph_domain( 1597 __isl_take isl_qpolynomial *qp, void *user) 1598 { 1599 isl_morph *morph = user; 1600 1601 return isl_qpolynomial_morph_domain(qp, isl_morph_copy(morph)); 1602 } 1603 1604 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph_domain( 1605 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph) 1606 { 1607 isl_space *space; 1608 isl_qpolynomial_list *list; 1609 1610 space = isl_qpolynomial_fold_peek_domain_space(fold); 1611 if (isl_morph_check_applies(morph, space) < 0) 1612 goto error; 1613 1614 list = isl_qpolynomial_fold_take_list(fold); 1615 list = isl_qpolynomial_list_map(list, &morph_domain, morph); 1616 fold = isl_qpolynomial_fold_restore_list(fold, list); 1617 1618 space = isl_morph_get_ran_space(morph); 1619 isl_space_free(isl_qpolynomial_fold_take_domain_space(fold)); 1620 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 1621 1622 isl_morph_free(morph); 1623 1624 return fold; 1625 error: 1626 isl_qpolynomial_fold_free(fold); 1627 isl_morph_free(morph); 1628 return NULL; 1629 } 1630 1631 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold) 1632 { 1633 if (!fold) 1634 return isl_fold_error; 1635 return fold->type; 1636 } 1637 1638 /* Return the type of this piecewise quasipolynomial reduction. 1639 */ 1640 enum isl_fold isl_pw_qpolynomial_fold_get_type( 1641 __isl_keep isl_pw_qpolynomial_fold *pwf) 1642 { 1643 if (!pwf) 1644 return isl_fold_error; 1645 return pwf->type; 1646 } 1647 1648 enum isl_fold isl_union_pw_qpolynomial_fold_get_type( 1649 __isl_keep isl_union_pw_qpolynomial_fold *upwf) 1650 { 1651 if (!upwf) 1652 return isl_fold_error; 1653 return upwf->type; 1654 } 1655 1656 /* isl_qpolynomial_list_map callback that calls 1657 * isl_qpolynomial_lift on "qp". 1658 */ 1659 static __isl_give isl_qpolynomial *lift(__isl_take isl_qpolynomial *qp, 1660 void *user) 1661 { 1662 isl_space *space = user; 1663 1664 return isl_qpolynomial_lift(qp, isl_space_copy(space)); 1665 } 1666 1667 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift( 1668 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_space *space) 1669 { 1670 isl_qpolynomial_list *list; 1671 1672 if (!fold || !space) 1673 goto error; 1674 1675 if (isl_space_is_equal(fold->dim, space)) { 1676 isl_space_free(space); 1677 return fold; 1678 } 1679 1680 list = isl_qpolynomial_fold_take_list(fold); 1681 list = isl_qpolynomial_list_map(list, &lift, space); 1682 fold = isl_qpolynomial_fold_restore_list(fold, list); 1683 1684 isl_space_free(isl_qpolynomial_fold_take_domain_space(fold)); 1685 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 1686 1687 return fold; 1688 error: 1689 isl_qpolynomial_fold_free(fold); 1690 isl_space_free(space); 1691 return NULL; 1692 } 1693 1694 isl_stat isl_qpolynomial_fold_foreach_qpolynomial( 1695 __isl_keep isl_qpolynomial_fold *fold, 1696 isl_stat (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user) 1697 { 1698 isl_qpolynomial_list *list; 1699 1700 list = isl_qpolynomial_fold_peek_list(fold); 1701 return isl_qpolynomial_list_foreach(list, fn, user); 1702 } 1703 1704 /* Internal data structure for isl_qpolynomial_fold_move_dims 1705 * representing its arguments. 1706 */ 1707 struct isl_fold_move_dims_data { 1708 enum isl_dim_type dst_type; 1709 unsigned dst_pos; 1710 enum isl_dim_type src_type; 1711 unsigned src_pos; 1712 unsigned n; 1713 }; 1714 1715 /* isl_qpolynomial_list_map callback for calling 1716 * isl_qpolynomial_move_dims on "qp". 1717 */ 1718 static __isl_give isl_qpolynomial *move_dims(__isl_take isl_qpolynomial *qp, 1719 void *user) 1720 { 1721 struct isl_fold_move_dims_data *data = user; 1722 1723 qp = isl_qpolynomial_move_dims(qp, data->dst_type, data->dst_pos, 1724 data->src_type, data->src_pos, data->n); 1725 return qp; 1726 } 1727 1728 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims( 1729 __isl_take isl_qpolynomial_fold *fold, 1730 enum isl_dim_type dst_type, unsigned dst_pos, 1731 enum isl_dim_type src_type, unsigned src_pos, unsigned n) 1732 { 1733 struct isl_fold_move_dims_data data = 1734 { dst_type, dst_pos, src_type, src_pos, n }; 1735 enum isl_dim_type set_src_type, set_dst_type; 1736 isl_space *space; 1737 isl_qpolynomial_list *list; 1738 1739 if (n == 0) 1740 return fold; 1741 1742 fold = isl_qpolynomial_fold_cow(fold); 1743 if (!fold) 1744 return NULL; 1745 1746 set_src_type = domain_type(src_type); 1747 set_dst_type = domain_type(dst_type); 1748 1749 list = isl_qpolynomial_fold_take_list(fold); 1750 list = isl_qpolynomial_list_map(list, &move_dims, &data); 1751 fold = isl_qpolynomial_fold_restore_list(fold, list); 1752 1753 space = isl_qpolynomial_fold_take_domain_space(fold); 1754 space = isl_space_move_dims(space, set_dst_type, dst_pos, 1755 set_src_type, src_pos, n); 1756 fold = isl_qpolynomial_fold_restore_domain_space(fold, space); 1757 1758 return fold; 1759 } 1760 1761 /* Internal data structure for isl_qpolynomial_fold_substitute 1762 * representing its arguments. 1763 */ 1764 struct isl_fold_substitute { 1765 enum isl_dim_type type; 1766 unsigned first; 1767 unsigned n; 1768 isl_qpolynomial **subs; 1769 }; 1770 1771 /* isl_qpolynomial_list_map callback for calling 1772 * isl_qpolynomial_substitute on "qp". 1773 */ 1774 static __isl_give isl_qpolynomial *substitute(__isl_take isl_qpolynomial *qp, 1775 void *user) 1776 { 1777 struct isl_fold_substitute *data = user; 1778 1779 qp = isl_qpolynomial_substitute(qp, 1780 data->type, data->first, data->n, data->subs); 1781 return qp; 1782 } 1783 1784 /* For each 0 <= i < "n", replace variable "first" + i of type "type" 1785 * in fold->qp[k] by subs[i]. 1786 */ 1787 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute( 1788 __isl_take isl_qpolynomial_fold *fold, 1789 enum isl_dim_type type, unsigned first, unsigned n, 1790 __isl_keep isl_qpolynomial **subs) 1791 { 1792 struct isl_fold_substitute data = { type, first, n, subs }; 1793 isl_qpolynomial_list *list; 1794 1795 if (n == 0) 1796 return fold; 1797 1798 list = isl_qpolynomial_fold_take_list(fold); 1799 list = isl_qpolynomial_list_map(list, &substitute, &data); 1800 fold = isl_qpolynomial_fold_restore_list(fold, list); 1801 1802 return fold; 1803 } 1804 1805 static isl_stat add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user) 1806 { 1807 isl_pw_qpolynomial_fold *pwf; 1808 isl_union_pw_qpolynomial_fold **upwf; 1809 struct isl_hash_table_entry *entry; 1810 1811 upwf = (isl_union_pw_qpolynomial_fold **)user; 1812 1813 entry = isl_union_pw_qpolynomial_fold_find_part_entry(*upwf, 1814 pwqp->dim, 1); 1815 if (!entry) 1816 goto error; 1817 1818 pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp); 1819 if (!entry->data) 1820 entry->data = pwf; 1821 else { 1822 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf); 1823 if (!entry->data) 1824 return isl_stat_error; 1825 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) 1826 *upwf = isl_union_pw_qpolynomial_fold_remove_part_entry( 1827 *upwf, entry); 1828 } 1829 1830 return isl_stat_ok; 1831 error: 1832 isl_pw_qpolynomial_free(pwqp); 1833 return isl_stat_error; 1834 } 1835 1836 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial( 1837 __isl_take isl_union_pw_qpolynomial_fold *upwf, 1838 __isl_take isl_union_pw_qpolynomial *upwqp) 1839 { 1840 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, 1841 isl_union_pw_qpolynomial_get_space(upwqp)); 1842 upwqp = isl_union_pw_qpolynomial_align_params(upwqp, 1843 isl_union_pw_qpolynomial_fold_get_space(upwf)); 1844 1845 upwf = isl_union_pw_qpolynomial_fold_cow(upwf); 1846 if (!upwf || !upwqp) 1847 goto error; 1848 1849 if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp, 1850 &upwf) < 0) 1851 goto error; 1852 1853 isl_union_pw_qpolynomial_free(upwqp); 1854 1855 return upwf; 1856 error: 1857 isl_union_pw_qpolynomial_fold_free(upwf); 1858 isl_union_pw_qpolynomial_free(upwqp); 1859 return NULL; 1860 } 1861 1862 static isl_bool join_compatible(__isl_keep isl_space *space1, 1863 __isl_keep isl_space *space2) 1864 { 1865 isl_bool m; 1866 m = isl_space_has_equal_params(space1, space2); 1867 if (m < 0 || !m) 1868 return m; 1869 return isl_space_tuple_is_equal(space1, isl_dim_out, 1870 space2, isl_dim_in); 1871 } 1872 1873 /* Compute the intersection of the range of the map and the domain 1874 * of the piecewise quasipolynomial reduction and then compute a bound 1875 * on the associated quasipolynomial reduction over all elements 1876 * in this intersection. 1877 * 1878 * We first introduce some unconstrained dimensions in the 1879 * piecewise quasipolynomial, intersect the resulting domain 1880 * with the wrapped map and the compute the sum. 1881 */ 1882 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold( 1883 __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf, 1884 isl_bool *tight) 1885 { 1886 isl_ctx *ctx; 1887 isl_set *dom; 1888 isl_space *map_space; 1889 isl_space *pwf_space; 1890 isl_size n_in; 1891 isl_bool ok; 1892 1893 ctx = isl_map_get_ctx(map); 1894 if (!ctx) 1895 goto error; 1896 1897 map_space = isl_map_get_space(map); 1898 pwf_space = isl_pw_qpolynomial_fold_get_space(pwf); 1899 ok = join_compatible(map_space, pwf_space); 1900 isl_space_free(map_space); 1901 isl_space_free(pwf_space); 1902 if (ok < 0) 1903 goto error; 1904 if (!ok) 1905 isl_die(ctx, isl_error_invalid, "incompatible dimensions", 1906 goto error); 1907 1908 n_in = isl_map_dim(map, isl_dim_in); 1909 if (n_in < 0) 1910 goto error; 1911 pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_in, 0, n_in); 1912 1913 dom = isl_map_wrap(map); 1914 pwf = isl_pw_qpolynomial_fold_reset_domain_space(pwf, 1915 isl_set_get_space(dom)); 1916 1917 pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom); 1918 pwf = isl_pw_qpolynomial_fold_bound(pwf, tight); 1919 1920 return pwf; 1921 error: 1922 isl_map_free(map); 1923 isl_pw_qpolynomial_fold_free(pwf); 1924 return NULL; 1925 } 1926 1927 __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold( 1928 __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf, 1929 isl_bool *tight) 1930 { 1931 return isl_map_apply_pw_qpolynomial_fold(set, pwf, tight); 1932 } 1933 1934 struct isl_apply_fold_data { 1935 isl_union_pw_qpolynomial_fold *upwf; 1936 isl_union_pw_qpolynomial_fold *res; 1937 isl_map *map; 1938 isl_bool tight; 1939 }; 1940 1941 static isl_stat pw_qpolynomial_fold_apply( 1942 __isl_take isl_pw_qpolynomial_fold *pwf, void *user) 1943 { 1944 isl_space *map_dim; 1945 isl_space *pwf_dim; 1946 struct isl_apply_fold_data *data = user; 1947 isl_bool ok; 1948 1949 map_dim = isl_map_get_space(data->map); 1950 pwf_dim = isl_pw_qpolynomial_fold_get_space(pwf); 1951 ok = join_compatible(map_dim, pwf_dim); 1952 isl_space_free(map_dim); 1953 isl_space_free(pwf_dim); 1954 1955 if (ok < 0) 1956 return isl_stat_error; 1957 if (ok) { 1958 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map), 1959 pwf, data->tight ? &data->tight : NULL); 1960 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold( 1961 data->res, pwf); 1962 } else 1963 isl_pw_qpolynomial_fold_free(pwf); 1964 1965 return isl_stat_ok; 1966 } 1967 1968 static isl_stat map_apply(__isl_take isl_map *map, void *user) 1969 { 1970 struct isl_apply_fold_data *data = user; 1971 isl_stat r; 1972 1973 data->map = map; 1974 r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold( 1975 data->upwf, &pw_qpolynomial_fold_apply, data); 1976 1977 isl_map_free(map); 1978 return r; 1979 } 1980 1981 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold( 1982 __isl_take isl_union_map *umap, 1983 __isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight) 1984 { 1985 isl_space *space; 1986 enum isl_fold type; 1987 struct isl_apply_fold_data data; 1988 1989 upwf = isl_union_pw_qpolynomial_fold_align_params(upwf, 1990 isl_union_map_get_space(umap)); 1991 umap = isl_union_map_align_params(umap, 1992 isl_union_pw_qpolynomial_fold_get_space(upwf)); 1993 1994 data.upwf = upwf; 1995 data.tight = tight ? isl_bool_true : isl_bool_false; 1996 space = isl_union_pw_qpolynomial_fold_get_space(upwf); 1997 type = isl_union_pw_qpolynomial_fold_get_type(upwf); 1998 data.res = isl_union_pw_qpolynomial_fold_zero(space, type); 1999 if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0) 2000 goto error; 2001 2002 isl_union_map_free(umap); 2003 isl_union_pw_qpolynomial_fold_free(upwf); 2004 2005 if (tight) 2006 *tight = data.tight; 2007 2008 return data.res; 2009 error: 2010 isl_union_map_free(umap); 2011 isl_union_pw_qpolynomial_fold_free(upwf); 2012 isl_union_pw_qpolynomial_fold_free(data.res); 2013 return NULL; 2014 } 2015 2016 __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold( 2017 __isl_take isl_union_set *uset, 2018 __isl_take isl_union_pw_qpolynomial_fold *upwf, isl_bool *tight) 2019 { 2020 return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight); 2021 } 2022 2023 /* isl_qpolynomial_list_map callback for calling 2024 * isl_qpolynomial_realign_domain on "qp". 2025 */ 2026 static __isl_give isl_qpolynomial *realign_domain( 2027 __isl_take isl_qpolynomial *qp, void *user) 2028 { 2029 isl_reordering *r = user; 2030 2031 qp = isl_qpolynomial_realign_domain(qp, isl_reordering_copy(r)); 2032 return qp; 2033 } 2034 2035 /* Reorder the dimension of "fold" according to the given reordering. 2036 */ 2037 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign_domain( 2038 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r) 2039 { 2040 isl_space *space; 2041 isl_qpolynomial_list *list; 2042 2043 list = isl_qpolynomial_fold_take_list(fold); 2044 list = isl_qpolynomial_list_map(list, &realign_domain, r); 2045 fold = isl_qpolynomial_fold_restore_list(fold, list); 2046 2047 space = isl_reordering_get_space(r); 2048 fold = isl_qpolynomial_fold_reset_domain_space(fold, space); 2049 2050 isl_reordering_free(r); 2051 2052 return fold; 2053 } 2054 2055 /* isl_qpolynomial_list_map callback for calling 2056 * isl_qpolynomial_mul_isl_int on "qp". 2057 */ 2058 static __isl_give isl_qpolynomial *mul_int(__isl_take isl_qpolynomial *qp, 2059 void *user) 2060 { 2061 isl_int *v = user; 2062 2063 qp = isl_qpolynomial_mul_isl_int(qp, *v); 2064 return qp; 2065 } 2066 2067 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int( 2068 __isl_take isl_qpolynomial_fold *fold, isl_int v) 2069 { 2070 isl_qpolynomial_list *list; 2071 2072 if (isl_int_is_one(v)) 2073 return fold; 2074 if (fold && isl_int_is_zero(v)) { 2075 isl_qpolynomial_fold *zero; 2076 isl_space *space = isl_space_copy(fold->dim); 2077 zero = isl_qpolynomial_fold_empty(fold->type, space); 2078 isl_qpolynomial_fold_free(fold); 2079 return zero; 2080 } 2081 2082 fold = isl_qpolynomial_fold_cow(fold); 2083 if (!fold) 2084 return NULL; 2085 2086 if (isl_int_is_neg(v)) 2087 fold->type = isl_fold_type_negate(fold->type); 2088 2089 list = isl_qpolynomial_fold_take_list(fold); 2090 list = isl_qpolynomial_list_map(list, &mul_int, &v); 2091 fold = isl_qpolynomial_fold_restore_list(fold, list); 2092 2093 return fold; 2094 } 2095 2096 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale( 2097 __isl_take isl_qpolynomial_fold *fold, isl_int v) 2098 { 2099 return isl_qpolynomial_fold_mul_isl_int(fold, v); 2100 } 2101 2102 /* isl_qpolynomial_list_map callback for calling 2103 * isl_qpolynomial_scale_val on "qp". 2104 */ 2105 static __isl_give isl_qpolynomial *scale_val(__isl_take isl_qpolynomial *qp, 2106 void *user) 2107 { 2108 isl_val *v = user; 2109 2110 qp = isl_qpolynomial_scale_val(qp, isl_val_copy(v)); 2111 return qp; 2112 } 2113 2114 /* Multiply "fold" by "v". 2115 */ 2116 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val( 2117 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) 2118 { 2119 isl_qpolynomial_list *list; 2120 2121 if (!fold || !v) 2122 goto error; 2123 2124 if (isl_val_is_one(v)) { 2125 isl_val_free(v); 2126 return fold; 2127 } 2128 if (isl_val_is_zero(v)) { 2129 isl_qpolynomial_fold *zero; 2130 isl_space *space = isl_qpolynomial_fold_get_domain_space(fold); 2131 zero = isl_qpolynomial_fold_empty(fold->type, space); 2132 isl_qpolynomial_fold_free(fold); 2133 isl_val_free(v); 2134 return zero; 2135 } 2136 if (!isl_val_is_rat(v)) 2137 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid, 2138 "expecting rational factor", goto error); 2139 2140 fold = isl_qpolynomial_fold_cow(fold); 2141 if (!fold) 2142 goto error; 2143 2144 if (isl_val_is_neg(v)) 2145 fold->type = isl_fold_type_negate(fold->type); 2146 2147 list = isl_qpolynomial_fold_take_list(fold); 2148 list = isl_qpolynomial_list_map(list, &scale_val, v); 2149 fold = isl_qpolynomial_fold_restore_list(fold, list); 2150 2151 isl_val_free(v); 2152 return fold; 2153 error: 2154 isl_val_free(v); 2155 isl_qpolynomial_fold_free(fold); 2156 return NULL; 2157 } 2158 2159 /* Divide "fold" by "v". 2160 */ 2161 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_down_val( 2162 __isl_take isl_qpolynomial_fold *fold, __isl_take isl_val *v) 2163 { 2164 if (!fold || !v) 2165 goto error; 2166 2167 if (isl_val_is_one(v)) { 2168 isl_val_free(v); 2169 return fold; 2170 } 2171 if (!isl_val_is_rat(v)) 2172 isl_die(isl_qpolynomial_fold_get_ctx(fold), isl_error_invalid, 2173 "expecting rational factor", goto error); 2174 if (isl_val_is_zero(v)) 2175 isl_die(isl_val_get_ctx(v), isl_error_invalid, 2176 "cannot scale down by zero", goto error); 2177 2178 return isl_qpolynomial_fold_scale_val(fold, isl_val_inv(v)); 2179 error: 2180 isl_val_free(v); 2181 isl_qpolynomial_fold_free(fold); 2182 return NULL; 2183 } 2184