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