isl_fold.c

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