isl_fold.c

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