isl_pw_templ.c

   1 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
   2 #define FN(TYPE,NAME) xFN(TYPE,NAME)
   3 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
   4 #define S(TYPE,NAME) xS(TYPE,NAME)
   5
   6 #ifdef HAS_TYPE
   7 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim,
   8         enum isl_fold type, int n)
   9 #else
  10 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, int n)
  11 #endif
  12 {
  13         isl_ctx *ctx;
  14         struct PW *pw;
  15
  16         if (!dim)
  17                 return NULL;
  18         ctx = isl_space_get_ctx(dim);
  19         isl_assert(ctx, n >= 0, goto error);
  20         pw = isl_alloc(ctx, struct PW,
  21                         sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
  22         if (!pw)
  23                 goto error;
  24
  25         pw->ref = 1;
  26 #ifdef HAS_TYPE
  27         pw->type = type;
  28 #endif
  29         pw->size = n;
  30         pw->n = 0;
  31         pw->dim = dim;
  32         return pw;
  33 error:
  34         isl_space_free(dim);
  35         return NULL;
  36 }
  37
  38 #ifdef HAS_TYPE
  39 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
  40 {
  41         return FN(PW,alloc_size)(dim, type, 0);
  42 }
  43 #else
  44 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim)
  45 {
  46         return FN(PW,alloc_size)(dim, 0);
  47 }
  48 #endif
  49
  50 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
  51         __isl_take isl_set *set, __isl_take EL *el)
  52 {
  53         isl_ctx *ctx;
  54         isl_space *el_dim = NULL;
  55
  56         if (!pw || !set || !el)
  57                 goto error;
  58
  59         if (isl_set_plain_is_empty(set) || FN(EL,EL_IS_ZERO)(el)) {
  60                 isl_set_free(set);
  61                 FN(EL,free)(el);
  62                 return pw;
  63         }
  64
  65         ctx = isl_set_get_ctx(set);
  66 #ifdef HAS_TYPE
  67         if (pw->type != el->type)
  68                 isl_die(ctx, isl_error_invalid, "fold types don't match",
  69                         goto error);
  70 #endif
  71         el_dim = FN(EL,get_space(el));
  72         isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);
  73         isl_assert(ctx, pw->n < pw->size, goto error);
  74
  75         pw->p[pw->n].set = set;
  76         pw->p[pw->n].FIELD = el;
  77         pw->n++;
  78
  79         isl_space_free(el_dim);
  80         return pw;
  81 error:
  82         isl_space_free(el_dim);
  83         FN(PW,free)(pw);
  84         isl_set_free(set);
  85         FN(EL,free)(el);
  86         return NULL;
  87 }
  88
  89 #ifdef HAS_TYPE
  90 __isl_give PW *FN(PW,alloc)(enum isl_fold type,
  91         __isl_take isl_set *set, __isl_take EL *el)
  92 #else
  93 __isl_give PW *FN(PW,alloc)(__isl_take isl_set *set, __isl_take EL *el)
  94 #endif
  95 {
  96         PW *pw;
  97
  98         if (!set || !el)
  99                 goto error;
 100
 101 #ifdef HAS_TYPE
 102         pw = FN(PW,alloc_size)(isl_set_get_space(set), type, 1);
 103 #else
 104         pw = FN(PW,alloc_size)(isl_set_get_space(set), 1);
 105 #endif
 106
 107         return FN(PW,add_piece)(pw, set, el);
 108 error:
 109         isl_set_free(set);
 110         FN(EL,free)(el);
 111         return NULL;
 112 }
 113
 114 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
 115 {
 116         int i;
 117         PW *dup;
 118
 119         if (!pw)
 120                 return NULL;
 121
 122 #ifdef HAS_TYPE
 123         dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, pw->n);
 124 #else
 125         dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->n);
 126 #endif
 127         if (!dup)
 128                 return NULL;
 129
 130         for (i = 0; i < pw->n; ++i)
 131                 dup = FN(PW,add_piece)(dup, isl_set_copy(pw->p[i].set),
 132                                             FN(EL,copy)(pw->p[i].FIELD));
 133
 134         return dup;
 135 }
 136
 137 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
 138 {
 139         if (!pw)
 140                 return NULL;
 141
 142         if (pw->ref == 1)
 143                 return pw;
 144         pw->ref--;
 145         return FN(PW,dup)(pw);
 146 }
 147
 148 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
 149 {
 150         if (!pw)
 151                 return NULL;
 152
 153         pw->ref++;
 154         return pw;
 155 }
 156
 157 void *FN(PW,free)(__isl_take PW *pw)
 158 {
 159         int i;
 160
 161         if (!pw)
 162                 return NULL;
 163         if (--pw->ref > 0)
 164                 return NULL;
 165
 166         for (i = 0; i < pw->n; ++i) {
 167                 isl_set_free(pw->p[i].set);
 168                 FN(EL,free)(pw->p[i].FIELD);
 169         }
 170         isl_space_free(pw->dim);
 171         free(pw);
 172
 173         return NULL;
 174 }
 175
 176 int FN(PW,IS_ZERO)(__isl_keep PW *pw)
 177 {
 178         if (!pw)
 179                 return -1;
 180
 181         return pw->n == 0;
 182 }
 183
 184 #ifndef NO_REALIGN
 185 __isl_give PW *FN(PW,realign)(__isl_take PW *pw, __isl_take isl_reordering *exp)
 186 {
 187         int i;
 188
 189         pw = FN(PW,cow)(pw);
 190         if (!pw || !exp)
 191                 return NULL;
 192
 193         for (i = 0; i < pw->n; ++i) {
 194                 pw->p[i].set = isl_set_realign(pw->p[i].set,
 195                                                     isl_reordering_copy(exp));
 196                 if (!pw->p[i].set)
 197                         goto error;
 198                 pw->p[i].FIELD = FN(EL,realign)(pw->p[i].FIELD,
 199                                                     isl_reordering_copy(exp));
 200                 if (!pw->p[i].FIELD)
 201                         goto error;
 202         }
 203
 204         pw = FN(PW,reset_space)(pw, isl_space_copy(exp->dim));
 205
 206         isl_reordering_free(exp);
 207         return pw;
 208 error:
 209         isl_reordering_free(exp);
 210         FN(PW,free)(pw);
 211         return NULL;
 212 }
 213
 214 /* Align the parameters of "pw" to those of "model".
 215  */
 216 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
 217 {
 218         isl_ctx *ctx;
 219
 220         if (!pw || !model)
 221                 goto error;
 222
 223         ctx = isl_space_get_ctx(model);
 224         if (!isl_space_has_named_params(model))
 225                 isl_die(ctx, isl_error_invalid,
 226                         "model has unnamed parameters", goto error);
 227         if (!isl_space_has_named_params(pw->dim))
 228                 isl_die(ctx, isl_error_invalid,
 229                         "input has unnamed parameters", goto error);
 230         if (!isl_space_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
 231                 isl_reordering *exp;
 232
 233                 model = isl_space_drop_dims(model, isl_dim_in,
 234                                         0, isl_space_dim(model, isl_dim_in));
 235                 model = isl_space_drop_dims(model, isl_dim_out,
 236                                         0, isl_space_dim(model, isl_dim_out));
 237                 exp = isl_parameter_alignment_reordering(pw->dim, model);
 238                 exp = isl_reordering_extend_space(exp, FN(PW,get_space)(pw));
 239                 pw = FN(PW,realign)(pw, exp);
 240         }
 241
 242         isl_space_free(model);
 243         return pw;
 244 error:
 245         isl_space_free(model);
 246         FN(PW,free)(pw);
 247         return NULL;
 248 }
 249
 250 static __isl_give PW *align_params_pw_pw_and(__isl_take PW *pw1,
 251         __isl_take PW *pw2,
 252         __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
 253 {
 254         isl_ctx *ctx;
 255
 256         if (!pw1 || !pw2)
 257                 goto error;
 258         if (isl_space_match(pw1->dim, isl_dim_param, pw2->dim, isl_dim_param))
 259                 return fn(pw1, pw2);
 260         ctx = FN(PW,get_ctx)(pw1);
 261         if (!isl_space_has_named_params(pw1->dim) ||
 262             !isl_space_has_named_params(pw2->dim))
 263                 isl_die(ctx, isl_error_invalid,
 264                         "unaligned unnamed parameters", goto error);
 265         pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2));
 266         pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1));
 267         return fn(pw1, pw2);
 268 error:
 269         FN(PW,free)(pw1);
 270         FN(PW,free)(pw2);
 271         return NULL;
 272 }
 273
 274 static __isl_give PW *align_params_pw_set_and(__isl_take PW *pw,
 275         __isl_take isl_set *set,
 276         __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set))
 277 {
 278         isl_ctx *ctx;
 279
 280         if (!pw || !set)
 281                 goto error;
 282         if (isl_space_match(pw->dim, isl_dim_param, set->dim, isl_dim_param))
 283                 return fn(pw, set);
 284         ctx = FN(PW,get_ctx)(pw);
 285         if (!isl_space_has_named_params(pw->dim) ||
 286             !isl_space_has_named_params(set->dim))
 287                 isl_die(ctx, isl_error_invalid,
 288                         "unaligned unnamed parameters", goto error);
 289         pw = FN(PW,align_params)(pw, isl_set_get_space(set));
 290         set = isl_set_align_params(set, FN(PW,get_space)(pw));
 291         return fn(pw, set);
 292 error:
 293         FN(PW,free)(pw);
 294         isl_set_free(set);
 295         return NULL;
 296 }
 297 #endif
 298
 299 static __isl_give PW *FN(PW,add_aligned)(__isl_take PW *pw1, __isl_take PW *pw2)
 300 {
 301         int i, j, n;
 302         struct PW *res;
 303         isl_ctx *ctx;
 304         isl_set *set;
 305
 306         if (!pw1 || !pw2)
 307                 goto error;
 308
 309         ctx = isl_space_get_ctx(pw1->dim);
 310 #ifdef HAS_TYPE
 311         if (pw1->type != pw2->type)
 312                 isl_die(ctx, isl_error_invalid,
 313                         "fold types don't match", goto error);
 314 #endif
 315         isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
 316
 317         if (FN(PW,IS_ZERO)(pw1)) {
 318                 FN(PW,free)(pw1);
 319                 return pw2;
 320         }
 321
 322         if (FN(PW,IS_ZERO)(pw2)) {
 323                 FN(PW,free)(pw2);
 324                 return pw1;
 325         }
 326
 327         n = (pw1->n + 1) * (pw2->n + 1);
 328 #ifdef HAS_TYPE
 329         res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->type, n);
 330 #else
 331         res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), n);
 332 #endif
 333
 334         for (i = 0; i < pw1->n; ++i) {
 335                 set = isl_set_copy(pw1->p[i].set);
 336                 for (j = 0; j < pw2->n; ++j) {
 337                         struct isl_set *common;
 338                         EL *sum;
 339                         set = isl_set_subtract(set,
 340                                         isl_set_copy(pw2->p[j].set));
 341                         common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
 342                                                 isl_set_copy(pw2->p[j].set));
 343                         if (isl_set_plain_is_empty(common)) {
 344                                 isl_set_free(common);
 345                                 continue;
 346                         }
 347
 348                         sum = FN(EL,add_on_domain)(common,
 349                                                    FN(EL,copy)(pw1->p[i].FIELD),
 350                                                    FN(EL,copy)(pw2->p[j].FIELD));
 351
 352                         res = FN(PW,add_piece)(res, common, sum);
 353                 }
 354                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
 355         }
 356
 357         for (j = 0; j < pw2->n; ++j) {
 358                 set = isl_set_copy(pw2->p[j].set);
 359                 for (i = 0; i < pw1->n; ++i)
 360                         set = isl_set_subtract(set,
 361                                         isl_set_copy(pw1->p[i].set));
 362                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
 363         }
 364
 365         FN(PW,free)(pw1);
 366         FN(PW,free)(pw2);
 367
 368         return res;
 369 error:
 370         FN(PW,free)(pw1);
 371         FN(PW,free)(pw2);
 372         return NULL;
 373 }
 374
 375 __isl_give PW *FN(PW,add)(__isl_take PW *pw1, __isl_take PW *pw2)
 376 {
 377         return align_params_pw_pw_and(pw1, pw2, &FN(PW,add_aligned));
 378 }
 379
 380 /* Make sure "pw" has room for at least "n" more pieces.
 381  *
 382  * If there is only one reference to pw, we extend it in place.
 383  * Otherwise, we create a new PW and copy the pieces.
 384  */
 385 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
 386 {
 387         int i;
 388         isl_ctx *ctx;
 389         PW *res;
 390
 391         if (!pw)
 392                 return NULL;
 393         if (pw->n + n <= pw->size)
 394                 return pw;
 395         ctx = FN(PW,get_ctx)(pw);
 396         n += pw->n;
 397         if (pw->ref == 1) {
 398                 res = isl_realloc(ctx, pw, struct PW,
 399                             sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
 400                 if (!res)
 401                         return FN(PW,free)(pw);
 402                 res->size = n;
 403                 return res;
 404         }
 405 #ifdef HAS_TYPE
 406         res = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, n);
 407 #else
 408         res = FN(PW,alloc_size)(isl_space_copy(pw->dim), n);
 409 #endif
 410         if (!res)
 411                 return FN(PW,free)(pw);
 412         for (i = 0; i < pw->n; ++i)
 413                 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
 414                                             FN(EL,copy)(pw->p[i].FIELD));
 415         FN(PW,free)(pw);
 416         return res;
 417 }
 418
 419 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
 420         __isl_take PW *pw2)
 421 {
 422         int i;
 423         isl_ctx *ctx;
 424
 425         if (!pw1 || !pw2)
 426                 goto error;
 427
 428         if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
 429                 return FN(PW,add_disjoint_aligned)(pw2, pw1);
 430
 431         ctx = isl_space_get_ctx(pw1->dim);
 432 #ifdef HAS_TYPE
 433         if (pw1->type != pw2->type)
 434                 isl_die(ctx, isl_error_invalid,
 435                         "fold types don't match", goto error);
 436 #endif
 437         isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
 438
 439         if (FN(PW,IS_ZERO)(pw1)) {
 440                 FN(PW,free)(pw1);
 441                 return pw2;
 442         }
 443
 444         if (FN(PW,IS_ZERO)(pw2)) {
 445                 FN(PW,free)(pw2);
 446                 return pw1;
 447         }
 448
 449         pw1 = FN(PW,grow)(pw1, pw2->n);
 450         if (!pw1)
 451                 goto error;
 452
 453         for (i = 0; i < pw2->n; ++i)
 454                 pw1 = FN(PW,add_piece)(pw1,
 455                                 isl_set_copy(pw2->p[i].set),
 456                                 FN(EL,copy)(pw2->p[i].FIELD));
 457
 458         FN(PW,free)(pw2);
 459
 460         return pw1;
 461 error:
 462         FN(PW,free)(pw1);
 463         FN(PW,free)(pw2);
 464         return NULL;
 465 }
 466
 467 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
 468 {
 469         return align_params_pw_pw_and(pw1, pw2, &FN(PW,add_disjoint_aligned));
 470 }
 471
 472 #ifndef NO_NEG
 473 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
 474 {
 475         int i;
 476
 477         if (!pw)
 478                 return NULL;
 479
 480         if (FN(PW,IS_ZERO)(pw))
 481                 return pw;
 482
 483         pw = FN(PW,cow)(pw);
 484         if (!pw)
 485                 return NULL;
 486
 487         for (i = 0; i < pw->n; ++i) {
 488                 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
 489                 if (!pw->p[i].FIELD)
 490                         return FN(PW,free)(pw);
 491         }
 492
 493         return pw;
 494 }
 495
 496 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
 497 {
 498         return FN(PW,add)(pw1, FN(PW,neg)(pw2));
 499 }
 500 #endif
 501
 502 #ifndef NO_EVAL
 503 __isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw,
 504         __isl_take isl_point *pnt)
 505 {
 506         int i;
 507         int found = 0;
 508         isl_ctx *ctx;
 509         isl_space *pnt_dim = NULL;
 510         isl_qpolynomial *qp;
 511
 512         if (!pw || !pnt)
 513                 goto error;
 514         ctx = isl_point_get_ctx(pnt);
 515         pnt_dim = isl_point_get_space(pnt);
 516         isl_assert(ctx, isl_space_is_equal(pnt_dim, pw->dim), goto error);
 517
 518         for (i = 0; i < pw->n; ++i) {
 519                 found = isl_set_contains_point(pw->p[i].set, pnt);
 520                 if (found < 0)
 521                         goto error;
 522                 if (found)
 523                         break;
 524         }
 525         if (found)
 526                 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
 527                                             isl_point_copy(pnt));
 528         else
 529                 qp = isl_qpolynomial_zero(isl_space_copy(pw->dim));
 530         FN(PW,free)(pw);
 531         isl_space_free(pnt_dim);
 532         isl_point_free(pnt);
 533         return qp;
 534 error:
 535         FN(PW,free)(pw);
 536         isl_space_free(pnt_dim);
 537         isl_point_free(pnt);
 538         return NULL;
 539 }
 540 #endif
 541
 542 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
 543 {
 544         int i;
 545         isl_set *dom;
 546
 547         if (!pw)
 548                 return NULL;
 549
 550         dom = isl_set_empty(isl_space_copy(pw->dim));
 551         for (i = 0; i < pw->n; ++i)
 552                 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
 553
 554         FN(PW,free)(pw);
 555
 556         return dom;
 557 }
 558
 559 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
 560         __isl_take isl_set *set)
 561 {
 562         int i;
 563
 564         if (!pw || !set)
 565                 goto error;
 566
 567         if (pw->n == 0) {
 568                 isl_set_free(set);
 569                 return pw;
 570         }
 571
 572         pw = FN(PW,cow)(pw);
 573         if (!pw)
 574                 goto error;
 575
 576         for (i = pw->n - 1; i >= 0; --i) {
 577                 isl_basic_set *aff;
 578                 pw->p[i].set = isl_set_intersect(pw->p[i].set, isl_set_copy(set));
 579                 if (!pw->p[i].set)
 580                         goto error;
 581                 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
 582                 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD,
 583                                                                 aff);
 584                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 585                         isl_set_free(pw->p[i].set);
 586                         FN(EL,free)(pw->p[i].FIELD);
 587                         if (i != pw->n - 1)
 588                                 pw->p[i] = pw->p[pw->n - 1];
 589                         pw->n--;
 590                 }
 591         }
 592
 593         isl_set_free(set);
 594         return pw;
 595 error:
 596         isl_set_free(set);
 597         FN(PW,free)(pw);
 598         return NULL;
 599 }
 600
 601 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
 602         __isl_take isl_set *context)
 603 {
 604         return align_params_pw_set_and(pw, context,
 605                                         &FN(PW,intersect_domain_aligned));
 606 }
 607
 608 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
 609         __isl_take isl_set *context)
 610 {
 611         int i;
 612         isl_basic_set *hull = NULL;
 613
 614         if (!pw || !context)
 615                 goto error;
 616
 617         if (pw->n == 0) {
 618                 isl_set_free(context);
 619                 return pw;
 620         }
 621
 622         if (!isl_space_match(pw->dim, isl_dim_param,
 623                                 context->dim, isl_dim_param)) {
 624                 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
 625                 context = isl_set_align_params(context, FN(PW,get_space)(pw));
 626         }
 627
 628         context = isl_set_compute_divs(context);
 629         hull = isl_set_simple_hull(isl_set_copy(context));
 630
 631         pw = FN(PW,cow)(pw);
 632         if (!pw)
 633                 goto error;
 634
 635         for (i = pw->n - 1; i >= 0; --i) {
 636                 pw->p[i].set = isl_set_intersect(pw->p[i].set,
 637                                                  isl_set_copy(context));
 638                 if (!pw->p[i].set)
 639                         goto error;
 640                 pw->p[i].FIELD = FN(EL,gist)(pw->p[i].FIELD,
 641                                              isl_set_copy(pw->p[i].set));
 642                 pw->p[i].set = isl_set_gist_basic_set(pw->p[i].set,
 643                                                 isl_basic_set_copy(hull));
 644                 if (!pw->p[i].set)
 645                         goto error;
 646                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 647                         isl_set_free(pw->p[i].set);
 648                         FN(EL,free)(pw->p[i].FIELD);
 649                         if (i != pw->n - 1)
 650                                 pw->p[i] = pw->p[pw->n - 1];
 651                         pw->n--;
 652                 }
 653         }
 654
 655         isl_basic_set_free(hull);
 656         isl_set_free(context);
 657
 658         return pw;
 659 error:
 660         FN(PW,free)(pw);
 661         isl_basic_set_free(hull);
 662         isl_set_free(context);
 663         return NULL;
 664 }
 665
 666 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
 667 {
 668         return align_params_pw_set_and(pw, context, &FN(PW,gist_aligned));
 669 }
 670
 671 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
 672 {
 673         int i, j;
 674
 675         if (!pw)
 676                 return NULL;
 677         if (pw->n == 0)
 678                 return pw;
 679
 680         for (i = pw->n - 1; i >= 0; --i) {
 681                 for (j = i - 1; j >= 0; --j) {
 682                         if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
 683                                                         pw->p[j].FIELD))
 684                                 continue;
 685                         pw->p[j].set = isl_set_union(pw->p[j].set,
 686                                                         pw->p[i].set);
 687                         FN(EL,free)(pw->p[i].FIELD);
 688                         if (i != pw->n - 1)
 689                                 pw->p[i] = pw->p[pw->n - 1];
 690                         pw->n--;
 691                         break;
 692                 }
 693                 if (j >= 0)
 694                         continue;
 695                 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
 696                 if (!pw->p[i].set)
 697                         goto error;
 698         }
 699
 700         return pw;
 701 error:
 702         FN(PW,free)(pw);
 703         return NULL;
 704 }
 705
 706 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
 707 {
 708         return pw ? isl_space_get_ctx(pw->dim) : NULL;
 709 }
 710
 711 #ifndef NO_INVOLVES_DIMS
 712 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
 713         unsigned first, unsigned n)
 714 {
 715         int i;
 716
 717         if (!pw)
 718                 return -1;
 719         if (pw->n == 0 || n == 0)
 720                 return 0;
 721         for (i = 0; i < pw->n; ++i) {
 722                 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
 723                                                         type, first, n);
 724                 if (involves < 0 || involves)
 725                         return involves;
 726                 involves = isl_set_involves_dims(pw->p[i].set, type, first, n);
 727                 if (involves < 0 || involves)
 728                         return involves;
 729         }
 730         return 0;
 731 }
 732 #endif
 733
 734 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
 735         enum isl_dim_type type, unsigned pos, const char *s)
 736 {
 737         int i;
 738
 739         pw = FN(PW,cow)(pw);
 740         if (!pw)
 741                 return NULL;
 742
 743         pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
 744         if (!pw->dim)
 745                 goto error;
 746
 747         for (i = 0; i < pw->n; ++i) {
 748                 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set, type, pos, s);
 749                 if (!pw->p[i].set)
 750                         goto error;
 751                 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
 752                 if (!pw->p[i].FIELD)
 753                         goto error;
 754         }
 755
 756         return pw;
 757 error:
 758         FN(PW,free)(pw);
 759         return NULL;
 760 }
 761
 762 #ifndef NO_DROP_DIMS
 763 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
 764         enum isl_dim_type type, unsigned first, unsigned n)
 765 {
 766         int i;
 767
 768         if (!pw)
 769                 return NULL;
 770         if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
 771                 return pw;
 772
 773         pw = FN(PW,cow)(pw);
 774         if (!pw)
 775                 return NULL;
 776         pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
 777         if (!pw->dim)
 778                 goto error;
 779         for (i = 0; i < pw->n; ++i) {
 780                 pw->p[i].set = isl_set_drop(pw->p[i].set, type, first, n);
 781                 if (!pw->p[i].set)
 782                         goto error;
 783                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 784                 if (!pw->p[i].FIELD)
 785                         goto error;
 786         }
 787
 788         return pw;
 789 error:
 790         FN(PW,free)(pw);
 791         return NULL;
 792 }
 793
 794 /* This function is very similar to drop_dims.
 795  * The only difference is that the cells may still involve
 796  * the specified dimensions.  They are removed using
 797  * isl_set_project_out instead of isl_set_drop.
 798  */
 799 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
 800         enum isl_dim_type type, unsigned first, unsigned n)
 801 {
 802         int i;
 803
 804         if (!pw)
 805                 return NULL;
 806         if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
 807                 return pw;
 808
 809         pw = FN(PW,cow)(pw);
 810         if (!pw)
 811                 return NULL;
 812         pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
 813         if (!pw->dim)
 814                 goto error;
 815         for (i = 0; i < pw->n; ++i) {
 816                 pw->p[i].set = isl_set_project_out(pw->p[i].set, type, first, n);
 817                 if (!pw->p[i].set)
 818                         goto error;
 819                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 820                 if (!pw->p[i].FIELD)
 821                         goto error;
 822         }
 823
 824         return pw;
 825 error:
 826         FN(PW,free)(pw);
 827         return NULL;
 828 }
 829
 830 /* Project the domain of pw onto its parameter space.
 831  */
 832 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
 833 {
 834         isl_space *space;
 835         unsigned n;
 836
 837         n = FN(PW,dim)(pw, isl_dim_set);
 838         pw = FN(PW,project_out)(pw, isl_dim_set, 0, n);
 839         space = FN(PW,get_space)(pw);
 840         space = isl_space_params(space);
 841         pw = FN(PW,reset_space)(pw, space);
 842         return pw;
 843 }
 844 #endif
 845
 846 #ifndef NO_INSERT_DIMS
 847 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
 848         unsigned first, unsigned n)
 849 {
 850         int i;
 851
 852         if (!pw)
 853                 return NULL;
 854         if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
 855                 return pw;
 856
 857         pw = FN(PW,cow)(pw);
 858         if (!pw)
 859                 return NULL;
 860
 861         pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
 862         if (!pw->dim)
 863                 goto error;
 864
 865         for (i = 0; i < pw->n; ++i) {
 866                 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
 867                                                                 type, first, n);
 868                 if (!pw->p[i].set)
 869                         goto error;
 870                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 871                                                                 type, first, n);
 872                 if (!pw->p[i].FIELD)
 873                         goto error;
 874         }
 875
 876         return pw;
 877 error:
 878         FN(PW,free)(pw);
 879         return NULL;
 880 }
 881 #endif
 882
 883 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 884         enum isl_dim_type type, unsigned pos, isl_int v)
 885 {
 886         int i;
 887
 888         if (!pw)
 889                 return NULL;
 890
 891         pw = FN(PW,cow)(pw);
 892         if (!pw)
 893                 return NULL;
 894         for (i = 0; i < pw->n; ++i) {
 895                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 896                 if (!pw->p[i].set)
 897                         goto error;
 898         }
 899
 900         return pw;
 901 error:
 902         FN(PW,free)(pw);
 903         return NULL;
 904 }
 905
 906 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 907 {
 908         return pw ? isl_space_dim(pw->dim, type) : 0;
 909 }
 910
 911 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 912         enum isl_dim_type type, unsigned first, unsigned n)
 913 {
 914         int i;
 915
 916         if (!pw)
 917                 return NULL;
 918         if (n == 0)
 919                 return pw;
 920
 921         pw = FN(PW,cow)(pw);
 922         if (!pw)
 923                 return NULL;
 924         if (!pw->dim)
 925                 goto error;
 926         for (i = 0; i < pw->n; ++i) {
 927                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 928                 if (!pw->p[i].set)
 929                         goto error;
 930         }
 931
 932         return pw;
 933 error:
 934         FN(PW,free)(pw);
 935         return NULL;
 936 }
 937
 938 #ifndef NO_OPT
 939 /* Compute the maximal value attained by the piecewise quasipolynomial
 940  * on its domain or zero if the domain is empty.
 941  * In the worst case, the domain is scanned completely,
 942  * so the domain is assumed to be bounded.
 943  */
 944 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 945 {
 946         int i;
 947         isl_qpolynomial *opt;
 948
 949         if (!pw)
 950                 return NULL;
 951
 952         if (pw->n == 0) {
 953                 isl_space *dim = isl_space_copy(pw->dim);
 954                 FN(PW,free)(pw);
 955                 return isl_qpolynomial_zero(dim);
 956         }
 957
 958         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
 959                                         isl_set_copy(pw->p[0].set), max);
 960         for (i = 1; i < pw->n; ++i) {
 961                 isl_qpolynomial *opt_i;
 962                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
 963                                                 isl_set_copy(pw->p[i].set), max);
 964                 if (max)
 965                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 966                 else
 967                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 968         }
 969
 970         FN(PW,free)(pw);
 971         return opt;
 972 }
 973
 974 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
 975 {
 976         return FN(PW,opt)(pw, 1);
 977 }
 978
 979 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
 980 {
 981         return FN(PW,opt)(pw, 0);
 982 }
 983 #endif
 984
 985 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
 986 {
 987         return pw ? isl_space_copy(pw->dim) : NULL;
 988 }
 989
 990 #ifndef NO_RESET_DIM
 991 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
 992 {
 993         int i;
 994
 995         pw = FN(PW,cow)(pw);
 996         if (!pw || !dim)
 997                 goto error;
 998
 999         for (i = 0; i < pw->n; ++i) {
1000                 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1001                                                  isl_space_copy(dim));
1002                 if (!pw->p[i].set)
1003                         goto error;
1004                 pw->p[i].FIELD = FN(EL,reset_space)(pw->p[i].FIELD,
1005                                                   isl_space_copy(dim));
1006                 if (!pw->p[i].FIELD)
1007                         goto error;
1008         }
1009         isl_space_free(pw->dim);
1010         pw->dim = dim;
1011
1012         return pw;
1013 error:
1014         isl_space_free(dim);
1015         FN(PW,free)(pw);
1016         return NULL;
1017 }
1018 #endif
1019
1020 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1021 {
1022         if (!pw1 || !pw2)
1023                 return -1;
1024
1025         return isl_space_is_equal(pw1->dim, pw2->dim);
1026 }
1027
1028 #ifndef NO_MORPH
1029 __isl_give PW *FN(PW,morph)(__isl_take PW *pw, __isl_take isl_morph *morph)
1030 {
1031         int i;
1032         isl_ctx *ctx;
1033
1034         if (!pw || !morph)
1035                 goto error;
1036
1037         ctx = isl_space_get_ctx(pw->dim);
1038         isl_assert(ctx, isl_space_is_equal(pw->dim, morph->dom->dim),
1039                 goto error);
1040
1041         pw = FN(PW,cow)(pw);
1042         if (!pw)
1043                 goto error;
1044         isl_space_free(pw->dim);
1045         pw->dim = isl_space_copy(morph->ran->dim);
1046         if (!pw->dim)
1047                 goto error;
1048
1049         for (i = 0; i < pw->n; ++i) {
1050                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1051                 if (!pw->p[i].set)
1052                         goto error;
1053                 pw->p[i].FIELD = FN(EL,morph)(pw->p[i].FIELD,
1054                                                 isl_morph_copy(morph));
1055                 if (!pw->p[i].FIELD)
1056                         goto error;
1057         }
1058
1059         isl_morph_free(morph);
1060
1061         return pw;
1062 error:
1063         FN(PW,free)(pw);
1064         isl_morph_free(morph);
1065         return NULL;
1066 }
1067 #endif
1068
1069 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1070         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1071         void *user)
1072 {
1073         int i;
1074
1075         if (!pw)
1076                 return -1;
1077
1078         for (i = 0; i < pw->n; ++i)
1079                 if (fn(isl_set_copy(pw->p[i].set),
1080                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1081                         return -1;
1082
1083         return 0;
1084 }
1085
1086 #ifndef NO_LIFT
1087 static int any_divs(__isl_keep isl_set *set)
1088 {
1089         int i;
1090
1091         if (!set)
1092                 return -1;
1093
1094         for (i = 0; i < set->n; ++i)
1095                 if (set->p[i]->n_div > 0)
1096                         return 1;
1097
1098         return 0;
1099 }
1100
1101 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1102         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1103                     void *user), void *user)
1104 {
1105         int i;
1106
1107         if (!set || !el)
1108                 goto error;
1109
1110         for (i = 0; i < set->n; ++i) {
1111                 isl_set *lift;
1112                 EL *copy;
1113
1114                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1115                 lift = isl_set_lift(lift);
1116
1117                 copy = FN(EL,copy)(el);
1118                 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1119
1120                 if (fn(lift, copy, user) < 0)
1121                         goto error;
1122         }
1123
1124         isl_set_free(set);
1125         FN(EL,free)(el);
1126
1127         return 0;
1128 error:
1129         isl_set_free(set);
1130         FN(EL,free)(el);
1131         return -1;
1132 }
1133
1134 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1135         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1136                     void *user), void *user)
1137 {
1138         int i;
1139
1140         if (!pw)
1141                 return -1;
1142
1143         for (i = 0; i < pw->n; ++i) {
1144                 isl_set *set;
1145                 EL *el;
1146
1147                 set = isl_set_copy(pw->p[i].set);
1148                 el = FN(EL,copy)(pw->p[i].FIELD);
1149                 if (!any_divs(set)) {
1150                         if (fn(set, el, user) < 0)
1151                                 return -1;
1152                         continue;
1153                 }
1154                 if (foreach_lifted_subset(set, el, fn, user) < 0)
1155                         return -1;
1156         }
1157
1158         return 0;
1159 }
1160 #endif
1161
1162 #ifndef NO_MOVE_DIMS
1163 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1164         enum isl_dim_type dst_type, unsigned dst_pos,
1165         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1166 {
1167         int i;
1168
1169         pw = FN(PW,cow)(pw);
1170         if (!pw)
1171                 return NULL;
1172
1173         pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1174         if (!pw->dim)
1175                 goto error;
1176
1177         for (i = 0; i < pw->n; ++i) {
1178                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1179                                                 dst_type, dst_pos,
1180                                                 src_type, src_pos, n);
1181                 if (!pw->p[i].set)
1182                         goto error;
1183                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1184                                         dst_type, dst_pos, src_type, src_pos, n);
1185                 if (!pw->p[i].FIELD)
1186                         goto error;
1187         }
1188
1189         return pw;
1190 error:
1191         FN(PW,free)(pw);
1192         return NULL;
1193 }
1194 #endif
1195
1196 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1197 {
1198         int i;
1199
1200         if (isl_int_is_one(v))
1201                 return pw;
1202         if (pw && isl_int_is_zero(v)) {
1203                 PW *zero;
1204                 isl_space *dim = FN(PW,get_space)(pw);
1205 #ifdef HAS_TYPE
1206                 zero = FN(PW,ZERO)(dim, pw->type);
1207 #else
1208                 zero = FN(PW,ZERO)(dim);
1209 #endif
1210                 FN(PW,free)(pw);
1211                 return zero;
1212         }
1213         pw = FN(PW,cow)(pw);
1214         if (!pw)
1215                 return NULL;
1216         if (pw->n == 0)
1217                 return pw;
1218
1219 #ifdef HAS_TYPE
1220         if (isl_int_is_neg(v))
1221                 pw->type = isl_fold_type_negate(pw->type);
1222 #endif
1223         for (i = 0; i < pw->n; ++i) {
1224                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1225                 if (!pw->p[i].FIELD)
1226                         goto error;
1227         }
1228
1229         return pw;
1230 error:
1231         FN(PW,free)(pw);
1232         return NULL;
1233 }
1234
1235 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1236 {
1237         return FN(PW,mul_isl_int)(pw, v);
1238 }