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