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