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 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute_equalities(
 354         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_basic_set *eq)
 355 {
 356         int i;
 357
 358         if (!fold || !eq)
 359                 goto error;
 360
 361         fold = isl_qpolynomial_fold_cow(fold);
 362         if (!fold)
 363                 return NULL;
 364
 365         for (i = 0; i < fold->n; ++i) {
 366                 fold->qp[i] = isl_qpolynomial_substitute_equalities(fold->qp[i],
 367                                                         isl_basic_set_copy(eq));
 368                 if (!fold->qp[i])
 369                         goto error;
 370         }
 371
 372         isl_basic_set_free(eq);
 373         return fold;
 374 error:
 375         isl_basic_set_free(eq);
 376         isl_qpolynomial_fold_free(fold);
 377         return NULL;
 378 }
 379
 380 #undef PW
 381 #define PW isl_pw_qpolynomial_fold
 382 #undef EL
 383 #define EL isl_qpolynomial_fold
 384 #undef IS_ZERO
 385 #define IS_ZERO is_empty
 386 #undef FIELD
 387 #define FIELD fold
 388 #undef ADD
 389 #define ADD(d,e1,e2)    isl_qpolynomial_fold_fold_on_domain(d,e1,e2)
 390
 391 #include <isl_pw_templ.c>
 392
 393 #undef UNION
 394 #define UNION isl_union_pw_qpolynomial_fold
 395 #undef PART
 396 #define PART isl_pw_qpolynomial_fold
 397 #undef PARTS
 398 #define PARTS pw_qpolynomial_fold
 399
 400 #include <isl_union_templ.c>
 401
 402 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
 403         __isl_take isl_dim *dim)
 404 {
 405         return qpolynomial_fold_alloc(type, dim, 0);
 406 }
 407
 408 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
 409         enum isl_fold type, __isl_take isl_qpolynomial *qp)
 410 {
 411         isl_qpolynomial_fold *fold;
 412
 413         if (!qp)
 414                 return NULL;
 415
 416         fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
 417         if (!fold)
 418                 goto error;
 419
 420         fold->qp[0] = qp;
 421         fold->n++;
 422
 423         return fold;
 424 error:
 425         isl_qpolynomial_fold_free(fold);
 426         isl_qpolynomial_free(qp);
 427         return NULL;
 428 }
 429
 430 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
 431         __isl_keep isl_qpolynomial_fold *fold)
 432 {
 433         if (!fold)
 434                 return NULL;
 435
 436         fold->ref++;
 437         return fold;
 438 }
 439
 440 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
 441         __isl_keep isl_qpolynomial_fold *fold)
 442 {
 443         int i;
 444         isl_qpolynomial_fold *dup;
 445
 446         if (!fold)
 447                 return NULL;
 448         dup = qpolynomial_fold_alloc(fold->type,
 449                                         isl_dim_copy(fold->dim), fold->n);
 450         if (!dup)
 451                 return NULL;
 452
 453         dup->n = fold->n;
 454         for (i = 0; i < fold->n; ++i) {
 455                 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
 456                 if (!dup->qp[i])
 457                         goto error;
 458         }
 459
 460         return dup;
 461 error:
 462         isl_qpolynomial_fold_free(dup);
 463         return NULL;
 464 }
 465
 466 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
 467         __isl_take isl_qpolynomial_fold *fold)
 468 {
 469         if (!fold)
 470                 return NULL;
 471
 472         if (fold->ref == 1)
 473                 return fold;
 474         fold->ref--;
 475         return isl_qpolynomial_fold_dup(fold);
 476 }
 477
 478 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
 479 {
 480         int i;
 481
 482         if (!fold)
 483                 return;
 484         if (--fold->ref > 0)
 485                 return;
 486
 487         for (i = 0; i < fold->n; ++i)
 488                 isl_qpolynomial_free(fold->qp[i]);
 489         isl_dim_free(fold->dim);
 490         free(fold);
 491 }
 492
 493 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
 494 {
 495         if (!fold)
 496                 return -1;
 497
 498         return fold->n == 0;
 499 }
 500
 501 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
 502         __isl_take isl_qpolynomial_fold *fold1,
 503         __isl_take isl_qpolynomial_fold *fold2)
 504 {
 505         int i;
 506         struct isl_qpolynomial_fold *res = NULL;
 507
 508         if (!fold1 || !fold2)
 509                 goto error;
 510
 511         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 512         isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
 513                         goto error);
 514
 515         if (isl_qpolynomial_fold_is_empty(fold1)) {
 516                 isl_qpolynomial_fold_free(fold1);
 517                 return fold2;
 518         }
 519
 520         if (isl_qpolynomial_fold_is_empty(fold2)) {
 521                 isl_qpolynomial_fold_free(fold2);
 522                 return fold1;
 523         }
 524
 525         res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
 526                                         fold1->n + fold2->n);
 527         if (!res)
 528                 goto error;
 529
 530         for (i = 0; i < fold1->n; ++i) {
 531                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 532                 if (!res->qp[res->n])
 533                         goto error;
 534                 res->n++;
 535         }
 536
 537         for (i = 0; i < fold2->n; ++i) {
 538                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 539                 if (!res->qp[res->n])
 540                         goto error;
 541                 res->n++;
 542         }
 543
 544         isl_qpolynomial_fold_free(fold1);
 545         isl_qpolynomial_fold_free(fold2);
 546
 547         return res;
 548 error:
 549         isl_qpolynomial_fold_free(res);
 550         isl_qpolynomial_fold_free(fold1);
 551         isl_qpolynomial_fold_free(fold2);
 552         return NULL;
 553 }
 554
 555 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
 556         enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
 557 {
 558         int i;
 559         isl_pw_qpolynomial_fold *pwf;
 560
 561         if (!pwqp)
 562                 return NULL;
 563
 564         pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
 565
 566         for (i = 0; i < pwqp->n; ++i)
 567                 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
 568                         isl_set_copy(pwqp->p[i].set),
 569                         isl_qpolynomial_fold_alloc(type,
 570                                 isl_qpolynomial_copy(pwqp->p[i].qp)));
 571
 572         isl_pw_qpolynomial_free(pwqp);
 573
 574         return pwf;
 575 }
 576
 577 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
 578         __isl_keep isl_qpolynomial_fold *fold2)
 579 {
 580         int i;
 581
 582         if (!fold1 || !fold2)
 583                 return -1;
 584
 585         if (fold1->n != fold2->n)
 586                 return 0;
 587
 588         /* We probably want to sort the qps first... */
 589         for (i = 0; i < fold1->n; ++i) {
 590                 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
 591                 if (eq < 0 || !eq)
 592                         return eq;
 593         }
 594
 595         return 1;
 596 }
 597
 598 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
 599         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
 600 {
 601         isl_qpolynomial *qp;
 602
 603         if (!fold || !pnt)
 604                 goto error;
 605         isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
 606         isl_assert(pnt->dim->ctx,
 607                 fold->type == isl_fold_max || fold->type == isl_fold_min,
 608                 goto error);
 609
 610         if (fold->n == 0)
 611                 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
 612         else {
 613                 int i;
 614                 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
 615                                                 isl_point_copy(pnt));
 616                 for (i = 1; i < fold->n; ++i) {
 617                         isl_qpolynomial *qp_i;
 618                         qp_i = isl_qpolynomial_eval(
 619                                             isl_qpolynomial_copy(fold->qp[i]),
 620                                             isl_point_copy(pnt));
 621                         if (fold->type == isl_fold_max)
 622                                 qp = isl_qpolynomial_max_cst(qp, qp_i);
 623                         else
 624                                 qp = isl_qpolynomial_min_cst(qp, qp_i);
 625                 }
 626         }
 627         isl_qpolynomial_fold_free(fold);
 628         isl_point_free(pnt);
 629
 630         return qp;
 631 error:
 632         isl_qpolynomial_fold_free(fold);
 633         isl_point_free(pnt);
 634         return NULL;
 635 }
 636
 637 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
 638 {
 639         int i;
 640         size_t n = 0;
 641
 642         for (i = 0; i < pwf->n; ++i)
 643                 n += pwf->p[i].fold->n;
 644
 645         return n;
 646 }
 647
 648 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
 649         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
 650 {
 651         int i;
 652         isl_qpolynomial *opt;
 653
 654         if (!set || !fold)
 655                 goto error;
 656
 657         if (fold->n == 0) {
 658                 isl_dim *dim = isl_dim_copy(fold->dim);
 659                 isl_set_free(set);
 660                 isl_qpolynomial_fold_free(fold);
 661                 return isl_qpolynomial_zero(dim);
 662         }
 663
 664         opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
 665                                                 isl_set_copy(set), max);
 666         for (i = 1; i < fold->n; ++i) {
 667                 isl_qpolynomial *opt_i;
 668                 opt_i = isl_qpolynomial_opt_on_domain(
 669                                 isl_qpolynomial_copy(fold->qp[i]),
 670                                 isl_set_copy(set), max);
 671                 if (max)
 672                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 673                 else
 674                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 675         }
 676
 677         isl_set_free(set);
 678         isl_qpolynomial_fold_free(fold);
 679
 680         return opt;
 681 error:
 682         isl_set_free(set);
 683         isl_qpolynomial_fold_free(fold);
 684         return NULL;
 685 }
 686
 687 /* Check whether for each quasi-polynomial in "fold2" there is
 688  * a quasi-polynomial in "fold1" that dominates it on "set".
 689  */
 690 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
 691         __isl_keep isl_qpolynomial_fold *fold1,
 692         __isl_keep isl_qpolynomial_fold *fold2)
 693 {
 694         int i, j;
 695         int covers;
 696
 697         if (!set || !fold1 || !fold2)
 698                 return -1;
 699
 700         covers = fold1->type == isl_fold_max ? 1 : -1;
 701
 702         for (i = 0; i < fold2->n; ++i) {
 703                 for (j = 0; j < fold1->n; ++j) {
 704                         isl_qpolynomial *d;
 705                         int sgn;
 706
 707                         d = isl_qpolynomial_sub(
 708                                 isl_qpolynomial_copy(fold1->qp[j]),
 709                                 isl_qpolynomial_copy(fold2->qp[i]));
 710                         sgn = isl_qpolynomial_sign(set, d);
 711                         isl_qpolynomial_free(d);
 712                         if (sgn == covers)
 713                                 break;
 714                 }
 715                 if (j >= fold1->n)
 716                         return 0;
 717         }
 718
 719         return 1;
 720 }
 721
 722 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
 723  * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
 724  * that of pwf2.
 725  */
 726 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
 727         __isl_keep isl_pw_qpolynomial_fold *pwf2)
 728 {
 729         int i, j;
 730         isl_set *dom1, *dom2;
 731         int is_subset;
 732
 733         if (!pwf1 || !pwf2)
 734                 return -1;
 735
 736         if (pwf2->n == 0)
 737                 return 1;
 738         if (pwf1->n == 0)
 739                 return 0;
 740
 741         dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
 742         dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
 743         is_subset = isl_set_is_subset(dom2, dom1);
 744         isl_set_free(dom1);
 745         isl_set_free(dom2);
 746
 747         if (is_subset < 0 || !is_subset)
 748                 return is_subset;
 749
 750         for (i = 0; i < pwf2->n; ++i) {
 751                 for (j = 0; j < pwf1->n; ++j) {
 752                         int is_empty;
 753                         isl_set *common;
 754                         int covers;
 755
 756                         common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
 757                                                    isl_set_copy(pwf2->p[i].set));
 758                         is_empty = isl_set_is_empty(common);
 759                         if (is_empty < 0 || is_empty) {
 760                                 isl_set_free(common);
 761                                 if (is_empty < 0)
 762                                         return -1;
 763                                 continue;
 764                         }
 765                         covers = qpolynomial_fold_covers_on_domain(common,
 766                                         pwf1->p[j].fold, pwf2->p[i].fold);
 767                         isl_set_free(common);
 768                         if (covers < 0 || !covers)
 769                                 return covers;
 770                 }
 771         }
 772
 773         return 1;
 774 }
 775
 776 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
 777         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
 778 {
 779         int i;
 780         isl_ctx *ctx;
 781
 782         if (!fold || !morph)
 783                 goto error;
 784
 785         ctx = fold->dim->ctx;
 786         isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
 787
 788         fold = isl_qpolynomial_fold_cow(fold);
 789         if (!fold)
 790                 goto error;
 791
 792         isl_dim_free(fold->dim);
 793         fold->dim = isl_dim_copy(morph->ran->dim);
 794         if (!fold->dim)
 795                 goto error;
 796
 797         for (i = 0; i < fold->n; ++i) {
 798                 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
 799                                                 isl_morph_copy(morph));
 800                 if (!fold->qp[i])
 801                         goto error;
 802         }
 803
 804         isl_morph_free(morph);
 805
 806         return fold;
 807 error:
 808         isl_qpolynomial_fold_free(fold);
 809         isl_morph_free(morph);
 810         return NULL;
 811 }
 812
 813 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
 814 {
 815         if (!fold)
 816                 return isl_fold_list;
 817         return fold->type;
 818 }
 819
 820 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
 821         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
 822 {
 823         int i;
 824         isl_ctx *ctx;
 825
 826         if (!fold || !dim)
 827                 goto error;
 828
 829         if (isl_dim_equal(fold->dim, dim)) {
 830                 isl_dim_free(dim);
 831                 return fold;
 832         }
 833
 834         fold = isl_qpolynomial_fold_cow(fold);
 835         if (!fold)
 836                 goto error;
 837
 838         isl_dim_free(fold->dim);
 839         fold->dim = isl_dim_copy(dim);
 840         if (!fold->dim)
 841                 goto error;
 842
 843         for (i = 0; i < fold->n; ++i) {
 844                 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
 845                                                 isl_dim_copy(dim));
 846                 if (!fold->qp[i])
 847                         goto error;
 848         }
 849
 850         isl_dim_free(dim);
 851
 852         return fold;
 853 error:
 854         isl_qpolynomial_fold_free(fold);
 855         isl_dim_free(dim);
 856         return NULL;
 857 }
 858
 859 int isl_qpolynomial_fold_foreach_qpolynomial(
 860         __isl_keep isl_qpolynomial_fold *fold,
 861         int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
 862 {
 863         int i;
 864
 865         if (!fold)
 866                 return -1;
 867
 868         for (i = 0; i < fold->n; ++i)
 869                 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
 870                         return -1;
 871
 872         return 0;
 873 }
 874
 875 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
 876         __isl_take isl_qpolynomial_fold *fold,
 877         enum isl_dim_type dst_type, unsigned dst_pos,
 878         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
 879 {
 880         int i;
 881
 882         if (n == 0)
 883                 return fold;
 884
 885         fold = isl_qpolynomial_fold_cow(fold);
 886         if (!fold)
 887                 return NULL;
 888
 889         fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
 890                                                 src_type, src_pos, n);
 891         if (!fold->dim)
 892                 goto error;
 893
 894         for (i = 0; i < fold->n; ++i) {
 895                 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
 896                                 dst_type, dst_pos, src_type, src_pos, n);
 897                 if (!fold->qp[i])
 898                         goto error;
 899         }
 900
 901         return fold;
 902 error:
 903         isl_qpolynomial_fold_free(fold);
 904         return NULL;
 905 }
 906
 907 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
 908  * in fold->qp[k] by subs[i].
 909  */
 910 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
 911         __isl_take isl_qpolynomial_fold *fold,
 912         enum isl_dim_type type, unsigned first, unsigned n,
 913         __isl_keep isl_qpolynomial **subs)
 914 {
 915         int i;
 916
 917         if (n == 0)
 918                 return fold;
 919
 920         fold = isl_qpolynomial_fold_cow(fold);
 921         if (!fold)
 922                 return NULL;
 923
 924         for (i = 0; i < fold->n; ++i) {
 925                 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
 926                                 type, first, n, subs);
 927                 if (!fold->qp[i])
 928                         goto error;
 929         }
 930
 931         return fold;
 932 error:
 933         isl_qpolynomial_fold_free(fold);
 934         return NULL;
 935 }