isl_fold.c

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