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