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