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