isl_fold.c

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