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