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
  19 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
  20         enum isl_fold type, __isl_take isl_dim *dim, int n)
  21 {
  22         isl_qpolynomial_fold *fold;
  23
  24         if (!dim)
  25                 goto error;
  26
  27         isl_assert(dim->ctx, n >= 0, goto error);
  28         fold = isl_calloc(dim->ctx, struct isl_qpolynomial_fold,
  29                         sizeof(struct isl_qpolynomial_fold) +
  30                         (n - 1) * sizeof(struct isl_qpolynomial *));
  31         if (!fold)
  32                 goto error;
  33
  34         fold->ref = 1;
  35         fold->size = n;
  36         fold->n = 0;
  37         fold->type = type;
  38         fold->dim = dim;
  39
  40         return fold;
  41 error:
  42         isl_dim_free(dim);
  43         return NULL;
  44 }
  45
  46 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
  47         enum isl_dim_type type, unsigned first, unsigned n)
  48 {
  49         int i;
  50
  51         if (!fold)
  52                 return -1;
  53         if (fold->n == 0 || n == 0)
  54                 return 0;
  55
  56         for (i = 0; i < fold->n; ++i) {
  57                 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
  58                                                             type, first, n);
  59                 if (involves < 0 || involves)
  60                         return involves;
  61         }
  62         return 0;
  63 }
  64
  65 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
  66         __isl_take isl_qpolynomial_fold *fold,
  67         enum isl_dim_type type, unsigned first, unsigned n)
  68 {
  69         int i;
  70
  71         if (!fold)
  72                 return NULL;
  73         if (n == 0)
  74                 return fold;
  75
  76         fold = isl_qpolynomial_fold_cow(fold);
  77         if (!fold)
  78                 return NULL;
  79         fold->dim = isl_dim_drop(fold->dim, type, first, n);
  80         if (!fold->dim)
  81                 goto error;
  82
  83         for (i = 0; i < fold->n; ++i) {
  84                 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
  85                                                             type, first, n);
  86                 if (!fold->qp[i])
  87                         goto error;
  88         }
  89
  90         return fold;
  91 error:
  92         isl_qpolynomial_fold_free(fold);
  93         return NULL;
  94 }
  95
  96 static int isl_qpolynomial_cst_sign(__isl_keep isl_qpolynomial *qp)
  97 {
  98         struct isl_upoly_cst *cst;
  99
 100         cst = isl_upoly_as_cst(qp->upoly);
 101         if (!cst)
 102                 return 0;
 103
 104         return isl_int_sgn(cst->n) < 0 ? -1 : 1;
 105 }
 106
 107 static int isl_qpolynomial_aff_sign(__isl_keep isl_set *set,
 108         __isl_keep isl_qpolynomial *qp)
 109 {
 110         enum isl_lp_result res;
 111         isl_vec *aff;
 112         isl_int opt;
 113         int sgn = 0;
 114
 115         aff = isl_qpolynomial_extract_affine(qp);
 116         if (!aff)
 117                 return 0;
 118
 119         isl_int_init(opt);
 120
 121         res = isl_set_solve_lp(set, 0, aff->el + 1, aff->el[0],
 122                                 &opt, NULL, NULL);
 123         if (res == isl_lp_error)
 124                 goto done;
 125         if (res == isl_lp_empty ||
 126             (res == isl_lp_ok && !isl_int_is_neg(opt))) {
 127                 sgn = 1;
 128                 goto done;
 129         }
 130
 131         res = isl_set_solve_lp(set, 1, aff->el + 1, aff->el[0],
 132                                 &opt, NULL, NULL);
 133         if (res == isl_lp_ok && !isl_int_is_pos(opt))
 134                 sgn = -1;
 135
 136 done:
 137         isl_int_clear(opt);
 138         isl_vec_free(aff);
 139         return sgn;
 140 }
 141
 142 /* Determine, if possible, the sign of the quasipolynomial "qp" on
 143  * the domain "set".
 144  *
 145  * If qp is a constant, then the problem is trivial.
 146  * If qp is linear, then we check if the minimum of the corresponding
 147  * affine constraint is non-negative or if the maximum is non-positive.
 148  *
 149  * Otherwise, we check if the outermost variable "v" has a lower bound "l"
 150  * in "set".  If so, we write qp(v,v') as
 151  *
 152  *      q(v,v') * (v - l) + r(v')
 153  *
 154  * if q(v,v') and r(v') have the same known sign, then the original
 155  * quasipolynomial has the same sign as well.
 156  *
 157  * Return
 158  *      -1 if qp <= 0
 159  *       1 if qp >= 0
 160  *       0 if unknown
 161  */
 162 static int isl_qpolynomial_sign(__isl_keep isl_set *set,
 163         __isl_keep isl_qpolynomial *qp)
 164 {
 165         int d;
 166         int i;
 167         int is;
 168         struct isl_upoly_rec *rec;
 169         isl_vec *v;
 170         isl_int l;
 171         enum isl_lp_result res;
 172         int sgn = 0;
 173
 174         is = isl_qpolynomial_is_cst(qp, NULL, NULL);
 175         if (is < 0)
 176                 return 0;
 177         if (is)
 178                 return isl_qpolynomial_cst_sign(qp);
 179
 180         is = isl_qpolynomial_is_affine(qp);
 181         if (is < 0)
 182                 return 0;
 183         if (is)
 184                 return isl_qpolynomial_aff_sign(set, qp);
 185
 186         if (qp->div->n_row > 0)
 187                 return 0;
 188
 189         rec = isl_upoly_as_rec(qp->upoly);
 190         if (!rec)
 191                 return 0;
 192
 193         d = isl_dim_total(qp->dim);
 194         v = isl_vec_alloc(set->ctx, 2 + d);
 195         if (!v)
 196                 return 0;
 197
 198         isl_seq_clr(v->el + 1, 1 + d);
 199         isl_int_set_si(v->el[0], 1);
 200         isl_int_set_si(v->el[2 + qp->upoly->var], 1);
 201
 202         isl_int_init(l);
 203
 204         res = isl_set_solve_lp(set, 0, v->el + 1, v->el[0], &l, NULL, NULL);
 205         if (res == isl_lp_ok) {
 206                 isl_qpolynomial *min;
 207                 isl_qpolynomial *base;
 208                 isl_qpolynomial *r, *q;
 209                 isl_qpolynomial *t;
 210
 211                 min = isl_qpolynomial_cst(isl_dim_copy(qp->dim), l);
 212                 base = isl_qpolynomial_pow(isl_dim_copy(qp->dim),
 213                                                 qp->upoly->var, 1);
 214
 215                 r = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
 216                                           isl_upoly_copy(rec->p[rec->n - 1]));
 217                 q = isl_qpolynomial_copy(r);
 218
 219                 for (i = rec->n - 2; i >= 0; --i) {
 220                         r = isl_qpolynomial_mul(r, isl_qpolynomial_copy(min));
 221                         t = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), 0,
 222                                                   isl_upoly_copy(rec->p[i]));
 223                         r = isl_qpolynomial_add(r, t);
 224                         if (i == 0)
 225                                 break;
 226                         q = isl_qpolynomial_mul(q, isl_qpolynomial_copy(base));
 227                         q = isl_qpolynomial_add(q, isl_qpolynomial_copy(r));
 228                 }
 229
 230                 if (isl_qpolynomial_is_zero(q))
 231                         sgn = isl_qpolynomial_sign(set, r);
 232                 else if (isl_qpolynomial_is_zero(r))
 233                         sgn = isl_qpolynomial_sign(set, q);
 234                 else {
 235                         int sgn_q, sgn_r;
 236                         sgn_r = isl_qpolynomial_sign(set, r);
 237                         sgn_q = isl_qpolynomial_sign(set, q);
 238                         if (sgn_r == sgn_q)
 239                                 sgn = sgn_r;
 240                 }
 241
 242                 isl_qpolynomial_free(min);
 243                 isl_qpolynomial_free(base);
 244                 isl_qpolynomial_free(q);
 245                 isl_qpolynomial_free(r);
 246         }
 247
 248         isl_int_clear(l);
 249
 250         isl_vec_free(v);
 251
 252         return sgn;
 253 }
 254
 255 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold_on_domain(
 256         __isl_keep isl_set *set,
 257         __isl_take isl_qpolynomial_fold *fold1,
 258         __isl_take isl_qpolynomial_fold *fold2)
 259 {
 260         int i, j;
 261         int n1;
 262         struct isl_qpolynomial_fold *res = NULL;
 263         int better;
 264
 265         if (!fold1 || !fold2)
 266                 goto error;
 267
 268         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 269         isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
 270                         goto error);
 271
 272         better = fold1->type == isl_fold_max ? -1 : 1;
 273
 274         if (isl_qpolynomial_fold_is_empty(fold1)) {
 275                 isl_qpolynomial_fold_free(fold1);
 276                 return fold2;
 277         }
 278
 279         if (isl_qpolynomial_fold_is_empty(fold2)) {
 280                 isl_qpolynomial_fold_free(fold2);
 281                 return fold1;
 282         }
 283
 284         res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
 285                                         fold1->n + fold2->n);
 286         if (!res)
 287                 goto error;
 288
 289         for (i = 0; i < fold1->n; ++i) {
 290                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 291                 if (!res->qp[res->n])
 292                         goto error;
 293                 res->n++;
 294         }
 295         n1 = res->n;
 296
 297         for (i = 0; i < fold2->n; ++i) {
 298                 for (j = n1 - 1; j >= 0; --j) {
 299                         isl_qpolynomial *d;
 300                         int sgn;
 301                         d = isl_qpolynomial_sub(
 302                                 isl_qpolynomial_copy(res->qp[j]),
 303                                 isl_qpolynomial_copy(fold2->qp[i]));
 304                         sgn = isl_qpolynomial_sign(set, d);
 305                         isl_qpolynomial_free(d);
 306                         if (sgn == 0)
 307                                 continue;
 308                         if (sgn != better)
 309                                 break;
 310                         isl_qpolynomial_free(res->qp[j]);
 311                         if (j != n1 - 1)
 312                                 res->qp[j] = res->qp[n1 - 1];
 313                         n1--;
 314                         if (n1 != res->n - 1)
 315                                 res->qp[n1] = res->qp[res->n - 1];
 316                         res->n--;
 317                 }
 318                 if (j >= 0)
 319                         continue;
 320                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 321                 if (!res->qp[res->n])
 322                         goto error;
 323                 res->n++;
 324         }
 325
 326         isl_qpolynomial_fold_free(fold1);
 327         isl_qpolynomial_fold_free(fold2);
 328
 329         return res;
 330 error:
 331         isl_qpolynomial_fold_free(res);
 332         isl_qpolynomial_fold_free(fold1);
 333         isl_qpolynomial_fold_free(fold2);
 334         return NULL;
 335 }
 336
 337 #undef PW
 338 #define PW isl_pw_qpolynomial_fold
 339 #undef EL
 340 #define EL isl_qpolynomial_fold
 341 #undef IS_ZERO
 342 #define IS_ZERO is_empty
 343 #undef FIELD
 344 #define FIELD fold
 345 #undef ADD
 346 #define ADD(d,e1,e2)    isl_qpolynomial_fold_fold_on_domain(d,e1,e2)
 347
 348 #include <isl_pw_templ.c>
 349
 350 #undef UNION
 351 #define UNION isl_union_pw_qpolynomial_fold
 352 #undef PART
 353 #define PART isl_pw_qpolynomial_fold
 354 #undef PARTS
 355 #define PARTS pw_qpolynomial_fold
 356
 357 #include <isl_union_templ.c>
 358
 359 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
 360         __isl_take isl_dim *dim)
 361 {
 362         return qpolynomial_fold_alloc(type, dim, 0);
 363 }
 364
 365 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
 366         enum isl_fold type, __isl_take isl_qpolynomial *qp)
 367 {
 368         isl_qpolynomial_fold *fold;
 369
 370         if (!qp)
 371                 return NULL;
 372
 373         fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
 374         if (!fold)
 375                 goto error;
 376
 377         fold->qp[0] = qp;
 378         fold->n++;
 379
 380         return fold;
 381 error:
 382         isl_qpolynomial_fold_free(fold);
 383         isl_qpolynomial_free(qp);
 384         return NULL;
 385 }
 386
 387 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
 388         __isl_keep isl_qpolynomial_fold *fold)
 389 {
 390         if (!fold)
 391                 return NULL;
 392
 393         fold->ref++;
 394         return fold;
 395 }
 396
 397 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
 398         __isl_keep isl_qpolynomial_fold *fold)
 399 {
 400         int i;
 401         isl_qpolynomial_fold *dup;
 402
 403         if (!fold)
 404                 return NULL;
 405         dup = qpolynomial_fold_alloc(fold->type,
 406                                         isl_dim_copy(fold->dim), fold->n);
 407         if (!dup)
 408                 return NULL;
 409
 410         dup->n = fold->n;
 411         for (i = 0; i < fold->n; ++i) {
 412                 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
 413                 if (!dup->qp[i])
 414                         goto error;
 415         }
 416
 417         return dup;
 418 error:
 419         isl_qpolynomial_fold_free(dup);
 420         return NULL;
 421 }
 422
 423 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
 424         __isl_take isl_qpolynomial_fold *fold)
 425 {
 426         if (!fold)
 427                 return NULL;
 428
 429         if (fold->ref == 1)
 430                 return fold;
 431         fold->ref--;
 432         return isl_qpolynomial_fold_dup(fold);
 433 }
 434
 435 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
 436 {
 437         int i;
 438
 439         if (!fold)
 440                 return;
 441         if (--fold->ref > 0)
 442                 return;
 443
 444         for (i = 0; i < fold->n; ++i)
 445                 isl_qpolynomial_free(fold->qp[i]);
 446         isl_dim_free(fold->dim);
 447         free(fold);
 448 }
 449
 450 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
 451 {
 452         if (!fold)
 453                 return -1;
 454
 455         return fold->n == 0;
 456 }
 457
 458 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
 459         __isl_take isl_qpolynomial_fold *fold1,
 460         __isl_take isl_qpolynomial_fold *fold2)
 461 {
 462         int i;
 463         struct isl_qpolynomial_fold *res = NULL;
 464
 465         if (!fold1 || !fold2)
 466                 goto error;
 467
 468         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 469         isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
 470                         goto error);
 471
 472         if (isl_qpolynomial_fold_is_empty(fold1)) {
 473                 isl_qpolynomial_fold_free(fold1);
 474                 return fold2;
 475         }
 476
 477         if (isl_qpolynomial_fold_is_empty(fold2)) {
 478                 isl_qpolynomial_fold_free(fold2);
 479                 return fold1;
 480         }
 481
 482         res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
 483                                         fold1->n + fold2->n);
 484         if (!res)
 485                 goto error;
 486
 487         for (i = 0; i < fold1->n; ++i) {
 488                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 489                 if (!res->qp[res->n])
 490                         goto error;
 491                 res->n++;
 492         }
 493
 494         for (i = 0; i < fold2->n; ++i) {
 495                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 496                 if (!res->qp[res->n])
 497                         goto error;
 498                 res->n++;
 499         }
 500
 501         isl_qpolynomial_fold_free(fold1);
 502         isl_qpolynomial_fold_free(fold2);
 503
 504         return res;
 505 error:
 506         isl_qpolynomial_fold_free(res);
 507         isl_qpolynomial_fold_free(fold1);
 508         isl_qpolynomial_fold_free(fold2);
 509         return NULL;
 510 }
 511
 512 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
 513         enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
 514 {
 515         int i;
 516         isl_pw_qpolynomial_fold *pwf;
 517
 518         if (!pwqp)
 519                 return NULL;
 520
 521         pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
 522
 523         for (i = 0; i < pwqp->n; ++i)
 524                 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
 525                         isl_set_copy(pwqp->p[i].set),
 526                         isl_qpolynomial_fold_alloc(type,
 527                                 isl_qpolynomial_copy(pwqp->p[i].qp)));
 528
 529         isl_pw_qpolynomial_free(pwqp);
 530
 531         return pwf;
 532 }
 533
 534 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
 535         __isl_keep isl_qpolynomial_fold *fold2)
 536 {
 537         int i;
 538
 539         if (!fold1 || !fold2)
 540                 return -1;
 541
 542         if (fold1->n != fold2->n)
 543                 return 0;
 544
 545         /* We probably want to sort the qps first... */
 546         for (i = 0; i < fold1->n; ++i) {
 547                 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
 548                 if (eq < 0 || !eq)
 549                         return eq;
 550         }
 551
 552         return 1;
 553 }
 554
 555 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
 556         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
 557 {
 558         isl_qpolynomial *qp;
 559
 560         if (!fold || !pnt)
 561                 goto error;
 562         isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
 563         isl_assert(pnt->dim->ctx,
 564                 fold->type == isl_fold_max || fold->type == isl_fold_min,
 565                 goto error);
 566
 567         if (fold->n == 0)
 568                 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
 569         else {
 570                 int i;
 571                 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
 572                                                 isl_point_copy(pnt));
 573                 for (i = 1; i < fold->n; ++i) {
 574                         isl_qpolynomial *qp_i;
 575                         qp_i = isl_qpolynomial_eval(
 576                                             isl_qpolynomial_copy(fold->qp[i]),
 577                                             isl_point_copy(pnt));
 578                         if (fold->type == isl_fold_max)
 579                                 qp = isl_qpolynomial_max_cst(qp, qp_i);
 580                         else
 581                                 qp = isl_qpolynomial_min_cst(qp, qp_i);
 582                 }
 583         }
 584         isl_qpolynomial_fold_free(fold);
 585         isl_point_free(pnt);
 586
 587         return qp;
 588 error:
 589         isl_qpolynomial_fold_free(fold);
 590         isl_point_free(pnt);
 591         return NULL;
 592 }
 593
 594 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
 595 {
 596         int i;
 597         size_t n = 0;
 598
 599         for (i = 0; i < pwf->n; ++i)
 600                 n += pwf->p[i].fold->n;
 601
 602         return n;
 603 }
 604
 605 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
 606         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
 607 {
 608         int i;
 609         isl_qpolynomial *opt;
 610
 611         if (!set || !fold)
 612                 goto error;
 613
 614         if (fold->n == 0) {
 615                 isl_dim *dim = isl_dim_copy(fold->dim);
 616                 isl_set_free(set);
 617                 isl_qpolynomial_fold_free(fold);
 618                 return isl_qpolynomial_zero(dim);
 619         }
 620
 621         opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
 622                                                 isl_set_copy(set), max);
 623         for (i = 1; i < fold->n; ++i) {
 624                 isl_qpolynomial *opt_i;
 625                 opt_i = isl_qpolynomial_opt_on_domain(
 626                                 isl_qpolynomial_copy(fold->qp[i]),
 627                                 isl_set_copy(set), max);
 628                 if (max)
 629                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 630                 else
 631                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 632         }
 633
 634         isl_set_free(set);
 635         isl_qpolynomial_fold_free(fold);
 636
 637         return opt;
 638 error:
 639         isl_set_free(set);
 640         isl_qpolynomial_fold_free(fold);
 641         return NULL;
 642 }
 643
 644 /* Check whether for each quasi-polynomial in "fold2" there is
 645  * a quasi-polynomial in "fold1" that dominates it on "set".
 646  */
 647 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
 648         __isl_keep isl_qpolynomial_fold *fold1,
 649         __isl_keep isl_qpolynomial_fold *fold2)
 650 {
 651         int i, j;
 652         int covers;
 653
 654         if (!set || !fold1 || !fold2)
 655                 return -1;
 656
 657         covers = fold1->type == isl_fold_max ? 1 : -1;
 658
 659         for (i = 0; i < fold2->n; ++i) {
 660                 for (j = 0; j < fold1->n; ++j) {
 661                         isl_qpolynomial *d;
 662                         int sgn;
 663
 664                         d = isl_qpolynomial_sub(
 665                                 isl_qpolynomial_copy(fold1->qp[j]),
 666                                 isl_qpolynomial_copy(fold2->qp[i]));
 667                         sgn = isl_qpolynomial_sign(set, d);
 668                         isl_qpolynomial_free(d);
 669                         if (sgn == covers)
 670                                 break;
 671                 }
 672                 if (j >= fold1->n)
 673                         return 0;
 674         }
 675
 676         return 1;
 677 }
 678
 679 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
 680  * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
 681  * that of pwf2.
 682  */
 683 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
 684         __isl_keep isl_pw_qpolynomial_fold *pwf2)
 685 {
 686         int i, j;
 687         isl_set *dom1, *dom2;
 688         int is_subset;
 689
 690         if (!pwf1 || !pwf2)
 691                 return -1;
 692
 693         if (pwf2->n == 0)
 694                 return 1;
 695         if (pwf1->n == 0)
 696                 return 0;
 697
 698         dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
 699         dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
 700         is_subset = isl_set_is_subset(dom2, dom1);
 701         isl_set_free(dom1);
 702         isl_set_free(dom2);
 703
 704         if (is_subset < 0 || !is_subset)
 705                 return is_subset;
 706
 707         for (i = 0; i < pwf2->n; ++i) {
 708                 for (j = 0; j < pwf1->n; ++j) {
 709                         int is_empty;
 710                         isl_set *common;
 711                         int covers;
 712
 713                         common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
 714                                                    isl_set_copy(pwf2->p[i].set));
 715                         is_empty = isl_set_is_empty(common);
 716                         if (is_empty < 0 || is_empty) {
 717                                 isl_set_free(common);
 718                                 if (is_empty < 0)
 719                                         return -1;
 720                                 continue;
 721                         }
 722                         covers = qpolynomial_fold_covers_on_domain(common,
 723                                         pwf1->p[j].fold, pwf2->p[i].fold);
 724                         isl_set_free(common);
 725                         if (covers < 0 || !covers)
 726                                 return covers;
 727                 }
 728         }
 729
 730         return 1;
 731 }
 732
 733 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
 734         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
 735 {
 736         int i;
 737         isl_ctx *ctx;
 738
 739         if (!fold || !morph)
 740                 goto error;
 741
 742         ctx = fold->dim->ctx;
 743         isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
 744
 745         fold = isl_qpolynomial_fold_cow(fold);
 746         if (!fold)
 747                 goto error;
 748
 749         isl_dim_free(fold->dim);
 750         fold->dim = isl_dim_copy(morph->ran->dim);
 751         if (!fold->dim)
 752                 goto error;
 753
 754         for (i = 0; i < fold->n; ++i) {
 755                 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
 756                                                 isl_morph_copy(morph));
 757                 if (!fold->qp[i])
 758                         goto error;
 759         }
 760
 761         isl_morph_free(morph);
 762
 763         return fold;
 764 error:
 765         isl_qpolynomial_fold_free(fold);
 766         isl_morph_free(morph);
 767         return NULL;
 768 }
 769
 770 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
 771 {
 772         if (!fold)
 773                 return isl_fold_list;
 774         return fold->type;
 775 }
 776
 777 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
 778         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
 779 {
 780         int i;
 781         isl_ctx *ctx;
 782
 783         if (!fold || !dim)
 784                 goto error;
 785
 786         if (isl_dim_equal(fold->dim, dim)) {
 787                 isl_dim_free(dim);
 788                 return fold;
 789         }
 790
 791         fold = isl_qpolynomial_fold_cow(fold);
 792         if (!fold)
 793                 goto error;
 794
 795         isl_dim_free(fold->dim);
 796         fold->dim = isl_dim_copy(dim);
 797         if (!fold->dim)
 798                 goto error;
 799
 800         for (i = 0; i < fold->n; ++i) {
 801                 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
 802                                                 isl_dim_copy(dim));
 803                 if (!fold->qp[i])
 804                         goto error;
 805         }
 806
 807         isl_dim_free(dim);
 808
 809         return fold;
 810 error:
 811         isl_qpolynomial_fold_free(fold);
 812         isl_dim_free(dim);
 813         return NULL;
 814 }
 815
 816 int isl_qpolynomial_fold_foreach_qpolynomial(
 817         __isl_keep isl_qpolynomial_fold *fold,
 818         int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
 819 {
 820         int i;
 821
 822         if (!fold)
 823                 return -1;
 824
 825         for (i = 0; i < fold->n; ++i)
 826                 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
 827                         return -1;
 828
 829         return 0;
 830 }
 831
 832 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
 833         __isl_take isl_qpolynomial_fold *fold,
 834         enum isl_dim_type dst_type, unsigned dst_pos,
 835         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 836 {
 837         int i;
 838
 839         if (n == 0)
 840                 return fold;
 841
 842         fold = isl_qpolynomial_fold_cow(fold);
 843         if (!fold)
 844                 return NULL;
 845
 846         fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
 847                                                 src_type, src_pos, n);
 848         if (!fold->dim)
 849                 goto error;
 850
 851         for (i = 0; i < fold->n; ++i) {
 852                 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
 853                                 dst_type, dst_pos, src_type, src_pos, n);
 854                 if (!fold->qp[i])
 855                         goto error;
 856         }
 857
 858         return fold;
 859 error:
 860         isl_qpolynomial_fold_free(fold);
 861         return NULL;
 862 }