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 IS_ZERO
 593 #define IS_ZERO is_empty
 594 #undef FIELD
 595 #define FIELD fold
 596
 597 #include <isl_pw_templ.c>
 598
 599 #undef UNION
 600 #define UNION isl_union_pw_qpolynomial_fold
 601 #undef PART
 602 #define PART isl_pw_qpolynomial_fold
 603 #undef PARTS
 604 #define PARTS pw_qpolynomial_fold
 605
 606 #include <isl_union_templ.c>
 607
 608 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
 609         __isl_take isl_dim *dim)
 610 {
 611         return qpolynomial_fold_alloc(type, dim, 0);
 612 }
 613
 614 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
 615         enum isl_fold type, __isl_take isl_qpolynomial *qp)
 616 {
 617         isl_qpolynomial_fold *fold;
 618
 619         if (!qp)
 620                 return NULL;
 621
 622         fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
 623         if (!fold)
 624                 goto error;
 625
 626         fold->qp[0] = qp;
 627         fold->n++;
 628
 629         return fold;
 630 error:
 631         isl_qpolynomial_fold_free(fold);
 632         isl_qpolynomial_free(qp);
 633         return NULL;
 634 }
 635
 636 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
 637         __isl_keep isl_qpolynomial_fold *fold)
 638 {
 639         if (!fold)
 640                 return NULL;
 641
 642         fold->ref++;
 643         return fold;
 644 }
 645
 646 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
 647         __isl_keep isl_qpolynomial_fold *fold)
 648 {
 649         int i;
 650         isl_qpolynomial_fold *dup;
 651
 652         if (!fold)
 653                 return NULL;
 654         dup = qpolynomial_fold_alloc(fold->type,
 655                                         isl_dim_copy(fold->dim), fold->n);
 656         if (!dup)
 657                 return NULL;
 658
 659         dup->n = fold->n;
 660         for (i = 0; i < fold->n; ++i) {
 661                 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
 662                 if (!dup->qp[i])
 663                         goto error;
 664         }
 665
 666         return dup;
 667 error:
 668         isl_qpolynomial_fold_free(dup);
 669         return NULL;
 670 }
 671
 672 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
 673         __isl_take isl_qpolynomial_fold *fold)
 674 {
 675         if (!fold)
 676                 return NULL;
 677
 678         if (fold->ref == 1)
 679                 return fold;
 680         fold->ref--;
 681         return isl_qpolynomial_fold_dup(fold);
 682 }
 683
 684 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
 685 {
 686         int i;
 687
 688         if (!fold)
 689                 return;
 690         if (--fold->ref > 0)
 691                 return;
 692
 693         for (i = 0; i < fold->n; ++i)
 694                 isl_qpolynomial_free(fold->qp[i]);
 695         isl_dim_free(fold->dim);
 696         free(fold);
 697 }
 698
 699 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
 700 {
 701         if (!fold)
 702                 return -1;
 703
 704         return fold->n == 0;
 705 }
 706
 707 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
 708         __isl_take isl_qpolynomial_fold *fold1,
 709         __isl_take isl_qpolynomial_fold *fold2)
 710 {
 711         int i;
 712         struct isl_qpolynomial_fold *res = NULL;
 713
 714         if (!fold1 || !fold2)
 715                 goto error;
 716
 717         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 718         isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
 719                         goto error);
 720
 721         if (isl_qpolynomial_fold_is_empty(fold1)) {
 722                 isl_qpolynomial_fold_free(fold1);
 723                 return fold2;
 724         }
 725
 726         if (isl_qpolynomial_fold_is_empty(fold2)) {
 727                 isl_qpolynomial_fold_free(fold2);
 728                 return fold1;
 729         }
 730
 731         res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
 732                                         fold1->n + fold2->n);
 733         if (!res)
 734                 goto error;
 735
 736         for (i = 0; i < fold1->n; ++i) {
 737                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 738                 if (!res->qp[res->n])
 739                         goto error;
 740                 res->n++;
 741         }
 742
 743         for (i = 0; i < fold2->n; ++i) {
 744                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 745                 if (!res->qp[res->n])
 746                         goto error;
 747                 res->n++;
 748         }
 749
 750         isl_qpolynomial_fold_free(fold1);
 751         isl_qpolynomial_fold_free(fold2);
 752
 753         return res;
 754 error:
 755         isl_qpolynomial_fold_free(res);
 756         isl_qpolynomial_fold_free(fold1);
 757         isl_qpolynomial_fold_free(fold2);
 758         return NULL;
 759 }
 760
 761 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
 762         __isl_take isl_pw_qpolynomial_fold *pw1,
 763         __isl_take isl_pw_qpolynomial_fold *pw2)
 764 {
 765         int i, j, n;
 766         struct isl_pw_qpolynomial_fold *res;
 767         isl_set *set;
 768
 769         if (!pw1 || !pw2)
 770                 goto error;
 771
 772         isl_assert(pw1->dim->ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
 773
 774         if (isl_pw_qpolynomial_fold_is_zero(pw1)) {
 775                 isl_pw_qpolynomial_fold_free(pw1);
 776                 return pw2;
 777         }
 778
 779         if (isl_pw_qpolynomial_fold_is_zero(pw2)) {
 780                 isl_pw_qpolynomial_fold_free(pw2);
 781                 return pw1;
 782         }
 783
 784         if (pw1->type != pw2->type)
 785                 isl_die(pw1->dim->ctx, isl_error_invalid,
 786                         "fold types don't match", goto error);
 787
 788         n = (pw1->n + 1) * (pw2->n + 1);
 789         res = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pw1->dim),
 790                                                 pw1->type, n);
 791
 792         for (i = 0; i < pw1->n; ++i) {
 793                 set = isl_set_copy(pw1->p[i].set);
 794                 for (j = 0; j < pw2->n; ++j) {
 795                         struct isl_set *common;
 796                         isl_qpolynomial_fold *sum;
 797                         set = isl_set_subtract(set,
 798                                         isl_set_copy(pw2->p[j].set));
 799                         common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
 800                                                 isl_set_copy(pw2->p[j].set));
 801                         if (isl_set_plain_is_empty(common)) {
 802                                 isl_set_free(common);
 803                                 continue;
 804                         }
 805
 806                         sum = isl_qpolynomial_fold_fold_on_domain(common,
 807                                isl_qpolynomial_fold_copy(pw1->p[i].fold),
 808                                isl_qpolynomial_fold_copy(pw2->p[j].fold));
 809
 810                         res = isl_pw_qpolynomial_fold_add_piece(res, common, sum);
 811                 }
 812                 res = isl_pw_qpolynomial_fold_add_piece(res, set,
 813                         isl_qpolynomial_fold_copy(pw1->p[i].fold));
 814         }
 815
 816         for (j = 0; j < pw2->n; ++j) {
 817                 set = isl_set_copy(pw2->p[j].set);
 818                 for (i = 0; i < pw1->n; ++i)
 819                         set = isl_set_subtract(set, isl_set_copy(pw1->p[i].set));
 820                 res = isl_pw_qpolynomial_fold_add_piece(res, set,
 821                                     isl_qpolynomial_fold_copy(pw2->p[j].fold));
 822         }
 823
 824         isl_pw_qpolynomial_fold_free(pw1);
 825         isl_pw_qpolynomial_fold_free(pw2);
 826
 827         return res;
 828 error:
 829         isl_pw_qpolynomial_fold_free(pw1);
 830         isl_pw_qpolynomial_fold_free(pw2);
 831         return NULL;
 832 }
 833
 834 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
 835         __isl_take isl_union_pw_qpolynomial_fold *u,
 836         __isl_take isl_pw_qpolynomial_fold *part)
 837 {
 838         uint32_t hash;
 839         struct isl_hash_table_entry *entry;
 840
 841         u = isl_union_pw_qpolynomial_fold_cow(u);
 842
 843         if (!part || !u)
 844                 goto error;
 845
 846         isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
 847                                               isl_dim_param), goto error);
 848
 849         hash = isl_dim_get_hash(part->dim);
 850         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 851                                     &has_dim, part->dim, 1);
 852         if (!entry)
 853                 goto error;
 854
 855         if (!entry->data)
 856                 entry->data = part;
 857         else {
 858                 entry->data = isl_pw_qpolynomial_fold_fold(entry->data,
 859                                             isl_pw_qpolynomial_fold_copy(part));
 860                 if (!entry->data)
 861                         goto error;
 862                 isl_pw_qpolynomial_fold_free(part);
 863         }
 864
 865         return u;
 866 error:
 867         isl_pw_qpolynomial_fold_free(part);
 868         isl_union_pw_qpolynomial_fold_free(u);
 869         return NULL;
 870 }
 871
 872 static int fold_part(__isl_take isl_pw_qpolynomial_fold *part, void *user)
 873 {
 874         isl_union_pw_qpolynomial_fold **u;
 875         u = (isl_union_pw_qpolynomial_fold **)user;
 876
 877         *u = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(*u, part);
 878
 879         return 0;
 880 }
 881
 882 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
 883         __isl_take isl_union_pw_qpolynomial_fold *u1,
 884         __isl_take isl_union_pw_qpolynomial_fold *u2)
 885 {
 886         u1 = isl_union_pw_qpolynomial_fold_cow(u1);
 887
 888         if (!u1 || !u2)
 889                 goto error;
 890
 891         if (isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(u2,
 892                                                         &fold_part, &u1) < 0)
 893                 goto error;
 894
 895         isl_union_pw_qpolynomial_fold_free(u2);
 896
 897         return u1;
 898 error:
 899         isl_union_pw_qpolynomial_fold_free(u1);
 900         isl_union_pw_qpolynomial_fold_free(u2);
 901         return NULL;
 902 }
 903
 904 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
 905         enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
 906 {
 907         int i;
 908         isl_pw_qpolynomial_fold *pwf;
 909
 910         if (!pwqp)
 911                 return NULL;
 912
 913         pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), type,
 914                                                 pwqp->n);
 915
 916         for (i = 0; i < pwqp->n; ++i)
 917                 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
 918                         isl_set_copy(pwqp->p[i].set),
 919                         isl_qpolynomial_fold_alloc(type,
 920                                 isl_qpolynomial_copy(pwqp->p[i].qp)));
 921
 922         isl_pw_qpolynomial_free(pwqp);
 923
 924         return pwf;
 925 }
 926
 927 int isl_qpolynomial_fold_plain_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
 928         __isl_keep isl_qpolynomial_fold *fold2)
 929 {
 930         int i;
 931
 932         if (!fold1 || !fold2)
 933                 return -1;
 934
 935         if (fold1->n != fold2->n)
 936                 return 0;
 937
 938         /* We probably want to sort the qps first... */
 939         for (i = 0; i < fold1->n; ++i) {
 940                 int eq = isl_qpolynomial_plain_is_equal(fold1->qp[i], fold2->qp[i]);
 941                 if (eq < 0 || !eq)
 942                         return eq;
 943         }
 944
 945         return 1;
 946 }
 947
 948 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
 949         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
 950 {
 951         isl_qpolynomial *qp;
 952
 953         if (!fold || !pnt)
 954                 goto error;
 955         isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
 956         isl_assert(pnt->dim->ctx,
 957                 fold->type == isl_fold_max || fold->type == isl_fold_min,
 958                 goto error);
 959
 960         if (fold->n == 0)
 961                 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
 962         else {
 963                 int i;
 964                 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
 965                                                 isl_point_copy(pnt));
 966                 for (i = 1; i < fold->n; ++i) {
 967                         isl_qpolynomial *qp_i;
 968                         qp_i = isl_qpolynomial_eval(
 969                                             isl_qpolynomial_copy(fold->qp[i]),
 970                                             isl_point_copy(pnt));
 971                         if (fold->type == isl_fold_max)
 972                                 qp = isl_qpolynomial_max_cst(qp, qp_i);
 973                         else
 974                                 qp = isl_qpolynomial_min_cst(qp, qp_i);
 975                 }
 976         }
 977         isl_qpolynomial_fold_free(fold);
 978         isl_point_free(pnt);
 979
 980         return qp;
 981 error:
 982         isl_qpolynomial_fold_free(fold);
 983         isl_point_free(pnt);
 984         return NULL;
 985 }
 986
 987 size_t isl_pw_qpolynomial_fold_size(__isl_keep isl_pw_qpolynomial_fold *pwf)
 988 {
 989         int i;
 990         size_t n = 0;
 991
 992         for (i = 0; i < pwf->n; ++i)
 993                 n += pwf->p[i].fold->n;
 994
 995         return n;
 996 }
 997
 998 __isl_give isl_qpolynomial *isl_qpolynomial_fold_opt_on_domain(
 999         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_set *set, int max)
1000 {
1001         int i;
1002         isl_qpolynomial *opt;
1003
1004         if (!set || !fold)
1005                 goto error;
1006
1007         if (fold->n == 0) {
1008                 isl_dim *dim = isl_dim_copy(fold->dim);
1009                 isl_set_free(set);
1010                 isl_qpolynomial_fold_free(fold);
1011                 return isl_qpolynomial_zero(dim);
1012         }
1013
1014         opt = isl_qpolynomial_opt_on_domain(isl_qpolynomial_copy(fold->qp[0]),
1015                                                 isl_set_copy(set), max);
1016         for (i = 1; i < fold->n; ++i) {
1017                 isl_qpolynomial *opt_i;
1018                 opt_i = isl_qpolynomial_opt_on_domain(
1019                                 isl_qpolynomial_copy(fold->qp[i]),
1020                                 isl_set_copy(set), max);
1021                 if (max)
1022                         opt = isl_qpolynomial_max_cst(opt, opt_i);
1023                 else
1024                         opt = isl_qpolynomial_min_cst(opt, opt_i);
1025         }
1026
1027         isl_set_free(set);
1028         isl_qpolynomial_fold_free(fold);
1029
1030         return opt;
1031 error:
1032         isl_set_free(set);
1033         isl_qpolynomial_fold_free(fold);
1034         return NULL;
1035 }
1036
1037 /* Check whether for each quasi-polynomial in "fold2" there is
1038  * a quasi-polynomial in "fold1" that dominates it on "set".
1039  */
1040 static int qpolynomial_fold_covers_on_domain(__isl_keep isl_set *set,
1041         __isl_keep isl_qpolynomial_fold *fold1,
1042         __isl_keep isl_qpolynomial_fold *fold2)
1043 {
1044         int i, j;
1045         int covers;
1046
1047         if (!set || !fold1 || !fold2)
1048                 return -1;
1049
1050         covers = fold1->type == isl_fold_max ? 1 : -1;
1051
1052         for (i = 0; i < fold2->n; ++i) {
1053                 for (j = 0; j < fold1->n; ++j) {
1054                         isl_qpolynomial *d;
1055                         int sgn;
1056
1057                         d = isl_qpolynomial_sub(
1058                                 isl_qpolynomial_copy(fold1->qp[j]),
1059                                 isl_qpolynomial_copy(fold2->qp[i]));
1060                         sgn = isl_qpolynomial_sign(set, d);
1061                         isl_qpolynomial_free(d);
1062                         if (sgn == covers)
1063                                 break;
1064                 }
1065                 if (j >= fold1->n)
1066                         return 0;
1067         }
1068
1069         return 1;
1070 }
1071
1072 /* Check whether "pwf1" dominated "pwf2", i.e., the domain of "pwf1" contains
1073  * that of "pwf2" and on each cell, the corresponding fold from pwf1 dominates
1074  * that of pwf2.
1075  */
1076 int isl_pw_qpolynomial_fold_covers(__isl_keep isl_pw_qpolynomial_fold *pwf1,
1077         __isl_keep isl_pw_qpolynomial_fold *pwf2)
1078 {
1079         int i, j;
1080         isl_set *dom1, *dom2;
1081         int is_subset;
1082
1083         if (!pwf1 || !pwf2)
1084                 return -1;
1085
1086         if (pwf2->n == 0)
1087                 return 1;
1088         if (pwf1->n == 0)
1089                 return 0;
1090
1091         dom1 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf1));
1092         dom2 = isl_pw_qpolynomial_fold_domain(isl_pw_qpolynomial_fold_copy(pwf2));
1093         is_subset = isl_set_is_subset(dom2, dom1);
1094         isl_set_free(dom1);
1095         isl_set_free(dom2);
1096
1097         if (is_subset < 0 || !is_subset)
1098                 return is_subset;
1099
1100         for (i = 0; i < pwf2->n; ++i) {
1101                 for (j = 0; j < pwf1->n; ++j) {
1102                         int is_empty;
1103                         isl_set *common;
1104                         int covers;
1105
1106                         common = isl_set_intersect(isl_set_copy(pwf1->p[j].set),
1107                                                    isl_set_copy(pwf2->p[i].set));
1108                         is_empty = isl_set_is_empty(common);
1109                         if (is_empty < 0 || is_empty) {
1110                                 isl_set_free(common);
1111                                 if (is_empty < 0)
1112                                         return -1;
1113                                 continue;
1114                         }
1115                         covers = qpolynomial_fold_covers_on_domain(common,
1116                                         pwf1->p[j].fold, pwf2->p[i].fold);
1117                         isl_set_free(common);
1118                         if (covers < 0 || !covers)
1119                                 return covers;
1120                 }
1121         }
1122
1123         return 1;
1124 }
1125
1126 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_morph(
1127         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_morph *morph)
1128 {
1129         int i;
1130         isl_ctx *ctx;
1131
1132         if (!fold || !morph)
1133                 goto error;
1134
1135         ctx = fold->dim->ctx;
1136         isl_assert(ctx, isl_dim_equal(fold->dim, morph->dom->dim), goto error);
1137
1138         fold = isl_qpolynomial_fold_cow(fold);
1139         if (!fold)
1140                 goto error;
1141
1142         isl_dim_free(fold->dim);
1143         fold->dim = isl_dim_copy(morph->ran->dim);
1144         if (!fold->dim)
1145                 goto error;
1146
1147         for (i = 0; i < fold->n; ++i) {
1148                 fold->qp[i] = isl_qpolynomial_morph(fold->qp[i],
1149                                                 isl_morph_copy(morph));
1150                 if (!fold->qp[i])
1151                         goto error;
1152         }
1153
1154         isl_morph_free(morph);
1155
1156         return fold;
1157 error:
1158         isl_qpolynomial_fold_free(fold);
1159         isl_morph_free(morph);
1160         return NULL;
1161 }
1162
1163 enum isl_fold isl_qpolynomial_fold_get_type(__isl_keep isl_qpolynomial_fold *fold)
1164 {
1165         if (!fold)
1166                 return isl_fold_list;
1167         return fold->type;
1168 }
1169
1170 enum isl_fold isl_union_pw_qpolynomial_fold_get_type(
1171         __isl_keep isl_union_pw_qpolynomial_fold *upwf)
1172 {
1173         if (!upwf)
1174                 return isl_fold_list;
1175         return upwf->type;
1176 }
1177
1178 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_lift(
1179         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_dim *dim)
1180 {
1181         int i;
1182
1183         if (!fold || !dim)
1184                 goto error;
1185
1186         if (isl_dim_equal(fold->dim, dim)) {
1187                 isl_dim_free(dim);
1188                 return fold;
1189         }
1190
1191         fold = isl_qpolynomial_fold_cow(fold);
1192         if (!fold)
1193                 goto error;
1194
1195         isl_dim_free(fold->dim);
1196         fold->dim = isl_dim_copy(dim);
1197         if (!fold->dim)
1198                 goto error;
1199
1200         for (i = 0; i < fold->n; ++i) {
1201                 fold->qp[i] = isl_qpolynomial_lift(fold->qp[i],
1202                                                 isl_dim_copy(dim));
1203                 if (!fold->qp[i])
1204                         goto error;
1205         }
1206
1207         isl_dim_free(dim);
1208
1209         return fold;
1210 error:
1211         isl_qpolynomial_fold_free(fold);
1212         isl_dim_free(dim);
1213         return NULL;
1214 }
1215
1216 int isl_qpolynomial_fold_foreach_qpolynomial(
1217         __isl_keep isl_qpolynomial_fold *fold,
1218         int (*fn)(__isl_take isl_qpolynomial *qp, void *user), void *user)
1219 {
1220         int i;
1221
1222         if (!fold)
1223                 return -1;
1224
1225         for (i = 0; i < fold->n; ++i)
1226                 if (fn(isl_qpolynomial_copy(fold->qp[i]), user) < 0)
1227                         return -1;
1228
1229         return 0;
1230 }
1231
1232 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_move_dims(
1233         __isl_take isl_qpolynomial_fold *fold,
1234         enum isl_dim_type dst_type, unsigned dst_pos,
1235         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1236 {
1237         int i;
1238
1239         if (n == 0)
1240                 return fold;
1241
1242         fold = isl_qpolynomial_fold_cow(fold);
1243         if (!fold)
1244                 return NULL;
1245
1246         fold->dim = isl_dim_move(fold->dim, dst_type, dst_pos,
1247                                                 src_type, src_pos, n);
1248         if (!fold->dim)
1249                 goto error;
1250
1251         for (i = 0; i < fold->n; ++i) {
1252                 fold->qp[i] = isl_qpolynomial_move_dims(fold->qp[i],
1253                                 dst_type, dst_pos, src_type, src_pos, n);
1254                 if (!fold->qp[i])
1255                         goto error;
1256         }
1257
1258         return fold;
1259 error:
1260         isl_qpolynomial_fold_free(fold);
1261         return NULL;
1262 }
1263
1264 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
1265  * in fold->qp[k] by subs[i].
1266  */
1267 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_substitute(
1268         __isl_take isl_qpolynomial_fold *fold,
1269         enum isl_dim_type type, unsigned first, unsigned n,
1270         __isl_keep isl_qpolynomial **subs)
1271 {
1272         int i;
1273
1274         if (n == 0)
1275                 return fold;
1276
1277         fold = isl_qpolynomial_fold_cow(fold);
1278         if (!fold)
1279                 return NULL;
1280
1281         for (i = 0; i < fold->n; ++i) {
1282                 fold->qp[i] = isl_qpolynomial_substitute(fold->qp[i],
1283                                 type, first, n, subs);
1284                 if (!fold->qp[i])
1285                         goto error;
1286         }
1287
1288         return fold;
1289 error:
1290         isl_qpolynomial_fold_free(fold);
1291         return NULL;
1292 }
1293
1294 static int add_pwqp(__isl_take isl_pw_qpolynomial *pwqp, void *user)
1295 {
1296         isl_ctx *ctx;
1297         isl_pw_qpolynomial_fold *pwf;
1298         isl_union_pw_qpolynomial_fold **upwf;
1299         uint32_t hash;
1300         struct isl_hash_table_entry *entry;
1301
1302         upwf = (isl_union_pw_qpolynomial_fold **)user;
1303
1304         ctx = pwqp->dim->ctx;
1305         hash = isl_dim_get_hash(pwqp->dim);
1306         entry = isl_hash_table_find(ctx, &(*upwf)->table,
1307                                      hash, &has_dim, pwqp->dim, 1);
1308         if (!entry)
1309                 goto error;
1310
1311         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial((*upwf)->type, pwqp);
1312         if (!entry->data)
1313                 entry->data = pwf;
1314         else {
1315                 entry->data = isl_pw_qpolynomial_fold_add(entry->data, pwf);
1316                 if (!entry->data)
1317                         return -1;
1318                 if (isl_pw_qpolynomial_fold_is_zero(entry->data)) {
1319                         isl_pw_qpolynomial_fold_free(entry->data);
1320                         isl_hash_table_remove(ctx, &(*upwf)->table, entry);
1321                 }
1322         }
1323
1324         return 0;
1325 error:
1326         isl_pw_qpolynomial_free(pwqp);
1327         return -1;
1328 }
1329
1330 __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(
1331         __isl_take isl_union_pw_qpolynomial_fold *upwf,
1332         __isl_take isl_union_pw_qpolynomial *upwqp)
1333 {
1334         upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1335                                 isl_union_pw_qpolynomial_get_dim(upwqp));
1336         upwqp = isl_union_pw_qpolynomial_align_params(upwqp,
1337                                 isl_union_pw_qpolynomial_fold_get_dim(upwf));
1338
1339         upwf = isl_union_pw_qpolynomial_fold_cow(upwf);
1340         if (!upwf || !upwqp)
1341                 goto error;
1342
1343         if (isl_union_pw_qpolynomial_foreach_pw_qpolynomial(upwqp, &add_pwqp,
1344                                                          &upwf) < 0)
1345                 goto error;
1346
1347         isl_union_pw_qpolynomial_free(upwqp);
1348
1349         return upwf;
1350 error:
1351         isl_union_pw_qpolynomial_fold_free(upwf);
1352         isl_union_pw_qpolynomial_free(upwqp);
1353         return NULL;
1354 }
1355
1356 static int compatible_range(__isl_keep isl_dim *dim1, __isl_keep isl_dim *dim2)
1357 {
1358         int m;
1359         m = isl_dim_match(dim1, isl_dim_param, dim2, isl_dim_param);
1360         if (m < 0 || !m)
1361                 return m;
1362         return isl_dim_tuple_match(dim1, isl_dim_out, dim2, isl_dim_set);
1363 }
1364
1365 /* Compute the intersection of the range of the map and the domain
1366  * of the piecewise quasipolynomial reduction and then compute a bound
1367  * on the associated quasipolynomial reduction over all elements
1368  * in this intersection.
1369  *
1370  * We first introduce some unconstrained dimensions in the
1371  * piecewise quasipolynomial, intersect the resulting domain
1372  * with the wrapped map and the compute the sum.
1373  */
1374 __isl_give isl_pw_qpolynomial_fold *isl_map_apply_pw_qpolynomial_fold(
1375         __isl_take isl_map *map, __isl_take isl_pw_qpolynomial_fold *pwf,
1376         int *tight)
1377 {
1378         isl_ctx *ctx;
1379         isl_set *dom;
1380         isl_dim *map_dim;
1381         isl_dim *pwf_dim;
1382         unsigned n_in;
1383         int ok;
1384
1385         ctx = isl_map_get_ctx(map);
1386         if (!ctx)
1387                 goto error;
1388
1389         map_dim = isl_map_get_dim(map);
1390         pwf_dim = isl_pw_qpolynomial_fold_get_dim(pwf);
1391         ok = compatible_range(map_dim, pwf_dim);
1392         isl_dim_free(map_dim);
1393         isl_dim_free(pwf_dim);
1394         if (!ok)
1395                 isl_die(ctx, isl_error_invalid, "incompatible dimensions",
1396                         goto error);
1397
1398         n_in = isl_map_dim(map, isl_dim_in);
1399         pwf = isl_pw_qpolynomial_fold_insert_dims(pwf, isl_dim_set, 0, n_in);
1400
1401         dom = isl_map_wrap(map);
1402         pwf = isl_pw_qpolynomial_fold_reset_dim(pwf, isl_set_get_dim(dom));
1403
1404         pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, dom);
1405         pwf = isl_pw_qpolynomial_fold_bound(pwf, tight);
1406
1407         return pwf;
1408 error:
1409         isl_map_free(map);
1410         isl_pw_qpolynomial_fold_free(pwf);
1411         return NULL;
1412 }
1413
1414 __isl_give isl_pw_qpolynomial_fold *isl_set_apply_pw_qpolynomial_fold(
1415         __isl_take isl_set *set, __isl_take isl_pw_qpolynomial_fold *pwf,
1416         int *tight)
1417 {
1418         isl_map *map;
1419
1420         map = isl_map_from_range(set);
1421         return isl_map_apply_pw_qpolynomial_fold(map, pwf, tight);
1422 }
1423
1424 struct isl_apply_fold_data {
1425         isl_union_pw_qpolynomial_fold *upwf;
1426         isl_union_pw_qpolynomial_fold *res;
1427         isl_map *map;
1428         int tight;
1429 };
1430
1431 static int pw_qpolynomial_fold_apply(__isl_take isl_pw_qpolynomial_fold *pwf,
1432         void *user)
1433 {
1434         isl_dim *map_dim;
1435         isl_dim *pwf_dim;
1436         struct isl_apply_fold_data *data = user;
1437         int ok;
1438
1439         map_dim = isl_map_get_dim(data->map);
1440         pwf_dim = isl_pw_qpolynomial_fold_get_dim(pwf);
1441         ok = compatible_range(map_dim, pwf_dim);
1442         isl_dim_free(map_dim);
1443         isl_dim_free(pwf_dim);
1444
1445         if (ok) {
1446                 pwf = isl_map_apply_pw_qpolynomial_fold(isl_map_copy(data->map),
1447                                     pwf, data->tight ? &data->tight : NULL);
1448                 data->res = isl_union_pw_qpolynomial_fold_fold_pw_qpolynomial_fold(
1449                                                         data->res, pwf);
1450         } else
1451                 isl_pw_qpolynomial_fold_free(pwf);
1452
1453         return 0;
1454 }
1455
1456 static int map_apply(__isl_take isl_map *map, void *user)
1457 {
1458         struct isl_apply_fold_data *data = user;
1459         int r;
1460
1461         data->map = map;
1462         r = isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
1463                                 data->upwf, &pw_qpolynomial_fold_apply, data);
1464
1465         isl_map_free(map);
1466         return r;
1467 }
1468
1469 __isl_give isl_union_pw_qpolynomial_fold *isl_union_map_apply_union_pw_qpolynomial_fold(
1470         __isl_take isl_union_map *umap,
1471         __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1472 {
1473         isl_dim *dim;
1474         enum isl_fold type;
1475         struct isl_apply_fold_data data;
1476
1477         upwf = isl_union_pw_qpolynomial_fold_align_params(upwf,
1478                                 isl_union_map_get_dim(umap));
1479         umap = isl_union_map_align_params(umap,
1480                                 isl_union_pw_qpolynomial_fold_get_dim(upwf));
1481
1482         data.upwf = upwf;
1483         data.tight = tight ? 1 : 0;
1484         dim = isl_union_pw_qpolynomial_fold_get_dim(upwf);
1485         type = isl_union_pw_qpolynomial_fold_get_type(upwf);
1486         data.res = isl_union_pw_qpolynomial_fold_zero(dim, type);
1487         if (isl_union_map_foreach_map(umap, &map_apply, &data) < 0)
1488                 goto error;
1489
1490         isl_union_map_free(umap);
1491         isl_union_pw_qpolynomial_fold_free(upwf);
1492
1493         if (tight)
1494                 *tight = data.tight;
1495
1496         return data.res;
1497 error:
1498         isl_union_map_free(umap);
1499         isl_union_pw_qpolynomial_fold_free(upwf);
1500         isl_union_pw_qpolynomial_fold_free(data.res);
1501         return NULL;
1502 }
1503
1504 __isl_give isl_union_pw_qpolynomial_fold *isl_union_set_apply_union_pw_qpolynomial_fold(
1505         __isl_take isl_union_set *uset,
1506         __isl_take isl_union_pw_qpolynomial_fold *upwf, int *tight)
1507 {
1508         return isl_union_map_apply_union_pw_qpolynomial_fold(uset, upwf, tight);
1509 }
1510
1511 /* Reorder the dimension of "fold" according to the given reordering.
1512  */
1513 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_realign(
1514         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_reordering *r)
1515 {
1516         int i;
1517
1518         fold = isl_qpolynomial_fold_cow(fold);
1519         if (!fold || !r)
1520                 goto error;
1521
1522         for (i = 0; i < fold->n; ++i) {
1523                 fold->qp[i] = isl_qpolynomial_realign(fold->qp[i],
1524                                                     isl_reordering_copy(r));
1525                 if (!fold->qp[i])
1526                         goto error;
1527         }
1528
1529         fold = isl_qpolynomial_fold_reset_dim(fold, isl_dim_copy(r->dim));
1530
1531         isl_reordering_free(r);
1532
1533         return fold;
1534 error:
1535         isl_qpolynomial_fold_free(fold);
1536         isl_reordering_free(r);
1537         return NULL;
1538 }
1539
1540 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_mul_isl_int(
1541         __isl_take isl_qpolynomial_fold *fold, isl_int v)
1542 {
1543         int i;
1544
1545         if (isl_int_is_one(v))
1546                 return fold;
1547         if (fold && isl_int_is_zero(v)) {
1548                 isl_qpolynomial_fold *zero;
1549                 isl_dim *dim = isl_dim_copy(fold->dim);
1550                 zero = isl_qpolynomial_fold_empty(fold->type, dim);
1551                 isl_qpolynomial_fold_free(fold);
1552                 return zero;
1553         }
1554
1555         fold = isl_qpolynomial_fold_cow(fold);
1556         if (!fold)
1557                 return NULL;
1558
1559         if (isl_int_is_neg(v))
1560                 fold->type = isl_fold_type_negate(fold->type);
1561         for (i = 0; i < fold->n; ++i) {
1562                 fold->qp[i] = isl_qpolynomial_mul_isl_int(fold->qp[i], v);
1563                 if (!fold->qp[i])
1564                         goto error;
1565         }
1566
1567         return fold;
1568 error:
1569         isl_qpolynomial_fold_free(fold);
1570         return NULL;
1571 }