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