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