2185 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 *4 * Use of this software is governed by the MIT license5 *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_BASE24#define EL_BASE pw_qpolynomial_fold25 26#include <isl_list_templ.c>27 28enum 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 and45 * list of polynomials.46 */47static __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;68error:69 isl_space_free(space);70 isl_qpolynomial_list_free(list);71 return NULL;72}73 74isl_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 */81static __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 itself95 * if there is only one reference to "fold".96 * This allows the space to be modified inplace97 * if both the expression and its space have only a single reference.98 * The caller is not allowed to modify "fold" between this call and99 * 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 */102static __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 missing118 * due to a preceding call to isl_qpolynomial_fold_take_domain_space.119 * However, in this case, "fold" only has a single reference and120 * then the call to isl_qpolynomial_fold_cow has no effect.121 */122static123__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;141error: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 */169static __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 itself177 * if there is only one reference to "fold".178 * This allows the list to be modified inplace179 * if both the expression and its list have only a single reference.180 * The caller is not allowed to modify "fold" between this call and181 * a subsequent call to isl_qpolynomial_fold_restore_list.182 * The only exception is that isl_qpolynomial_fold_free can be called instead.183 */184static __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 missing200 * due to a preceding call to isl_qpolynomial_fold_take_list.201 * However, in this case, "fold" only has a single reference and202 * then the call to isl_qpolynomial_fold_cow has no effect.203 */204static __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;223error:224 isl_qpolynomial_fold_free(fold);225 isl_qpolynomial_list_free(list);226 return NULL;227}228 229/* isl_qpolynomial_list_map callback that calls230 * isl_qpolynomial_reset_domain_space on "qp".231 */232static __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 polynomials243 * 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.c261 * and doesn't know if the space of an element object is represented262 * 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_*_dims273 * representing their arguments.274 */275struct 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 */284static 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 case297 * that every polynomial in the reduction does not involve298 * any of the dimensions.299 */300static 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_name319 * representing its arguments.320 */321struct 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 calling328 * isl_qpolynomial_set_dim_name on "qp".329 */330static __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 */342static 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 calling371 * isl_qpolynomial_drop_dims on "qp".372 */373static __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 calling410 * isl_qpolynomial_insert_dims on "qp".411 */412static __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 * Return450 * -1 if qp <= 0451 * 1 if qp >= 0452 * 0 if unknown453 *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 */457static 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 471static 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 500done: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" on507 * 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 corresponding511 * 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') as515 *516 * q(v,v') * (v - l) + r(v')517 *518 * if q(v,v') and r(v') have the same known sign, then the original519 * quasipolynomial has the same sign as well.520 *521 * Return522 * -1 if qp <= 0523 * 1 if qp >= 0524 * 0 if unknown525 */526static 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 */623static 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 */641static 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, eliminating660 * those elements of one list that are already covered by the other661 * list on "set".662 *663 * "better" is the sign that the difference qp1 - qp2 needs to have for qp1664 * to be covered by qp2.665 */666static __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);710error: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, eliminating717 * those elements of one reduction that are already covered by the other718 * reduction on "set".719 *720 * If "fold1" or "fold2" is an empty reduction, then return721 * 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;761error: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 */769static __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;796error: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;858error: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 calling866 * isl_qpolynomial_substitute_equalities on "qp" and "eq".867 */868static __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 calling891 * isl_qpolynomial_substitute_equalities on "qp" and "context".892 */893static __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 uniform926 * interface over all piecewise types.927 */928static __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_nan935 936#define HAS_TYPE937 938#undef PW939#define PW isl_pw_qpolynomial_fold940#undef BASE941#define BASE qpolynomial_fold942#undef EL_IS_ZERO943#define EL_IS_ZERO is_empty944#undef ZERO945#define ZERO zero946#undef IS_ZERO947#define IS_ZERO is_zero948#undef FIELD949#define FIELD fold950#undef DEFAULT_IS_ZERO951#define DEFAULT_IS_ZERO 1952 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 BASE965#define BASE pw_qpolynomial_fold966 967#include <isl_union_single.c>968#include <isl_union_eval.c>969 970/* Construct a new reduction of the given type and space971 * 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 and987 * 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 1050isl_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 */1065isl_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;1109error: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;1182error: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;1216error:1217 isl_pw_qpolynomial_fold_free(part);1218 isl_union_pw_qpolynomial_fold_free(u);1219 return NULL;1220}1221 1222static 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;1248error: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 */1289int 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" elements1325 * obviously equal to each other?1326 */1327static 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 use1347 * as a isl_qpolynomial_list_sort callback.1348 */1349static 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 1355isl_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 else1420 v = isl_val_min(v, v_i);1421 }1422 }1423 isl_qpolynomial_fold_free(fold);1424 isl_point_free(pnt);1425 1426 return v;1427error:1428 isl_qpolynomial_fold_free(fold);1429 isl_point_free(pnt);1430 return NULL;1431}1432 1433size_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 else1485 opt = isl_val_min(opt, opt_i);1486 }1487 1488 isl_set_free(set);1489 isl_qpolynomial_fold_free(fold);1490 1491 return opt;1492error: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 is1499 * a quasi-polynomial in "fold1" that dominates it on "set".1500 */1501static 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" contains1540 * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates1541 * that of pwf2.1542 */1543isl_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 calls1595 * isl_qpolynomial_morph_domain on "qp".1596 */1597static __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;1626error:1627 isl_qpolynomial_fold_free(fold);1628 isl_morph_free(morph);1629 return NULL;1630}1631 1632enum 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 */1641enum 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 1649enum 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 calls1658 * isl_qpolynomial_lift on "qp".1659 */1660static __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;1689error:1690 isl_qpolynomial_fold_free(fold);1691 isl_space_free(space);1692 return NULL;1693}1694 1695isl_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_dims1706 * representing its arguments.1707 */1708struct 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 calling1717 * isl_qpolynomial_move_dims on "qp".1718 */1719static __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_substitute1763 * representing its arguments.1764 */1765struct 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 calling1773 * isl_qpolynomial_substitute on "qp".1774 */1775static __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 1806static 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;1832error: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;1857error:1858 isl_union_pw_qpolynomial_fold_free(upwf);1859 isl_union_pw_qpolynomial_free(upwqp);1860 return NULL;1861}1862 1863static 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 domain1875 * of the piecewise quasipolynomial reduction and then compute a bound1876 * on the associated quasipolynomial reduction over all elements1877 * in this intersection.1878 *1879 * We first introduce some unconstrained dimensions in the1880 * piecewise quasipolynomial, intersect the resulting domain1881 * 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;1922error: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 1935struct 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 1942static 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 } else1964 isl_pw_qpolynomial_fold_free(pwf);1965 1966 return isl_stat_ok;1967}1968 1969static 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;2010error: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 calling2025 * isl_qpolynomial_realign_domain on "qp".2026 */2027static __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 calling2057 * isl_qpolynomial_mul_isl_int on "qp".2058 */2059static __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 calling2104 * isl_qpolynomial_scale_val on "qp".2105 */2106static __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;2154error: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));2180error:2181 isl_val_free(v);2182 isl_qpolynomial_fold_free(fold);2183 return NULL;2184}2185