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