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 #endif
 794
 795 #ifndef NO_INSERT_DIMS
 796 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
 797         unsigned first, unsigned n)
 798 {
 799         int i;
 800
 801         if (!pw)
 802                 return NULL;
 803         if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
 804                 return pw;
 805
 806         pw = FN(PW,cow)(pw);
 807         if (!pw)
 808                 return NULL;
 809
 810         pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
 811         if (!pw->dim)
 812                 goto error;
 813
 814         for (i = 0; i < pw->n; ++i) {
 815                 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
 816                                                                 type, first, n);
 817                 if (!pw->p[i].set)
 818                         goto error;
 819                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 820                                                                 type, first, n);
 821                 if (!pw->p[i].FIELD)
 822                         goto error;
 823         }
 824
 825         return pw;
 826 error:
 827         FN(PW,free)(pw);
 828         return NULL;
 829 }
 830 #endif
 831
 832 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 833         enum isl_dim_type type, unsigned pos, isl_int v)
 834 {
 835         int i;
 836
 837         if (!pw)
 838                 return NULL;
 839
 840         pw = FN(PW,cow)(pw);
 841         if (!pw)
 842                 return NULL;
 843         for (i = 0; i < pw->n; ++i) {
 844                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 845                 if (!pw->p[i].set)
 846                         goto error;
 847         }
 848
 849         return pw;
 850 error:
 851         FN(PW,free)(pw);
 852         return NULL;
 853 }
 854
 855 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 856 {
 857         return pw ? isl_space_dim(pw->dim, type) : 0;
 858 }
 859
 860 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 861         enum isl_dim_type type, unsigned first, unsigned n)
 862 {
 863         int i;
 864
 865         if (!pw)
 866                 return NULL;
 867         if (n == 0)
 868                 return pw;
 869
 870         pw = FN(PW,cow)(pw);
 871         if (!pw)
 872                 return NULL;
 873         if (!pw->dim)
 874                 goto error;
 875         for (i = 0; i < pw->n; ++i) {
 876                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 877                 if (!pw->p[i].set)
 878                         goto error;
 879         }
 880
 881         return pw;
 882 error:
 883         FN(PW,free)(pw);
 884         return NULL;
 885 }
 886
 887 #ifndef NO_OPT
 888 /* Compute the maximal value attained by the piecewise quasipolynomial
 889  * on its domain or zero if the domain is empty.
 890  * In the worst case, the domain is scanned completely,
 891  * so the domain is assumed to be bounded.
 892  */
 893 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 894 {
 895         int i;
 896         isl_qpolynomial *opt;
 897
 898         if (!pw)
 899                 return NULL;
 900
 901         if (pw->n == 0) {
 902                 isl_space *dim = isl_space_copy(pw->dim);
 903                 FN(PW,free)(pw);
 904                 return isl_qpolynomial_zero(dim);
 905         }
 906
 907         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
 908                                         isl_set_copy(pw->p[0].set), max);
 909         for (i = 1; i < pw->n; ++i) {
 910                 isl_qpolynomial *opt_i;
 911                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
 912                                                 isl_set_copy(pw->p[i].set), max);
 913                 if (max)
 914                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 915                 else
 916                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 917         }
 918
 919         FN(PW,free)(pw);
 920         return opt;
 921 }
 922
 923 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
 924 {
 925         return FN(PW,opt)(pw, 1);
 926 }
 927
 928 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
 929 {
 930         return FN(PW,opt)(pw, 0);
 931 }
 932 #endif
 933
 934 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
 935 {
 936         return pw ? isl_space_copy(pw->dim) : NULL;
 937 }
 938
 939 #ifndef NO_RESET_DIM
 940 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
 941 {
 942         int i;
 943
 944         pw = FN(PW,cow)(pw);
 945         if (!pw || !dim)
 946                 goto error;
 947
 948         for (i = 0; i < pw->n; ++i) {
 949                 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
 950                                                  isl_space_copy(dim));
 951                 if (!pw->p[i].set)
 952                         goto error;
 953                 pw->p[i].FIELD = FN(EL,reset_space)(pw->p[i].FIELD,
 954                                                   isl_space_copy(dim));
 955                 if (!pw->p[i].FIELD)
 956                         goto error;
 957         }
 958         isl_space_free(pw->dim);
 959         pw->dim = dim;
 960
 961         return pw;
 962 error:
 963         isl_space_free(dim);
 964         FN(PW,free)(pw);
 965         return NULL;
 966 }
 967 #endif
 968
 969 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
 970 {
 971         if (!pw1 || !pw2)
 972                 return -1;
 973
 974         return isl_space_is_equal(pw1->dim, pw2->dim);
 975 }
 976
 977 #ifndef NO_MORPH
 978 __isl_give PW *FN(PW,morph)(__isl_take PW *pw, __isl_take isl_morph *morph)
 979 {
 980         int i;
 981         isl_ctx *ctx;
 982
 983         if (!pw || !morph)
 984                 goto error;
 985
 986         ctx = isl_space_get_ctx(pw->dim);
 987         isl_assert(ctx, isl_space_is_equal(pw->dim, morph->dom->dim),
 988                 goto error);
 989
 990         pw = FN(PW,cow)(pw);
 991         if (!pw)
 992                 goto error;
 993         isl_space_free(pw->dim);
 994         pw->dim = isl_space_copy(morph->ran->dim);
 995         if (!pw->dim)
 996                 goto error;
 997
 998         for (i = 0; i < pw->n; ++i) {
 999                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1000                 if (!pw->p[i].set)
1001                         goto error;
1002                 pw->p[i].FIELD = FN(EL,morph)(pw->p[i].FIELD,
1003                                                 isl_morph_copy(morph));
1004                 if (!pw->p[i].FIELD)
1005                         goto error;
1006         }
1007
1008         isl_morph_free(morph);
1009
1010         return pw;
1011 error:
1012         FN(PW,free)(pw);
1013         isl_morph_free(morph);
1014         return NULL;
1015 }
1016 #endif
1017
1018 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1019         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1020         void *user)
1021 {
1022         int i;
1023
1024         if (!pw)
1025                 return -1;
1026
1027         for (i = 0; i < pw->n; ++i)
1028                 if (fn(isl_set_copy(pw->p[i].set),
1029                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1030                         return -1;
1031
1032         return 0;
1033 }
1034
1035 #ifndef NO_LIFT
1036 static int any_divs(__isl_keep isl_set *set)
1037 {
1038         int i;
1039
1040         if (!set)
1041                 return -1;
1042
1043         for (i = 0; i < set->n; ++i)
1044                 if (set->p[i]->n_div > 0)
1045                         return 1;
1046
1047         return 0;
1048 }
1049
1050 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1051         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1052                     void *user), void *user)
1053 {
1054         int i;
1055
1056         if (!set || !el)
1057                 goto error;
1058
1059         for (i = 0; i < set->n; ++i) {
1060                 isl_set *lift;
1061                 EL *copy;
1062
1063                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1064                 lift = isl_set_lift(lift);
1065
1066                 copy = FN(EL,copy)(el);
1067                 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1068
1069                 if (fn(lift, copy, user) < 0)
1070                         goto error;
1071         }
1072
1073         isl_set_free(set);
1074         FN(EL,free)(el);
1075
1076         return 0;
1077 error:
1078         isl_set_free(set);
1079         FN(EL,free)(el);
1080         return -1;
1081 }
1082
1083 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1084         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1085                     void *user), void *user)
1086 {
1087         int i;
1088
1089         if (!pw)
1090                 return -1;
1091
1092         for (i = 0; i < pw->n; ++i) {
1093                 isl_set *set;
1094                 EL *el;
1095
1096                 set = isl_set_copy(pw->p[i].set);
1097                 el = FN(EL,copy)(pw->p[i].FIELD);
1098                 if (!any_divs(set)) {
1099                         if (fn(set, el, user) < 0)
1100                                 return -1;
1101                         continue;
1102                 }
1103                 if (foreach_lifted_subset(set, el, fn, user) < 0)
1104                         return -1;
1105         }
1106
1107         return 0;
1108 }
1109 #endif
1110
1111 #ifndef NO_MOVE_DIMS
1112 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1113         enum isl_dim_type dst_type, unsigned dst_pos,
1114         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1115 {
1116         int i;
1117
1118         pw = FN(PW,cow)(pw);
1119         if (!pw)
1120                 return NULL;
1121
1122         pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1123         if (!pw->dim)
1124                 goto error;
1125
1126         for (i = 0; i < pw->n; ++i) {
1127                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1128                                                 dst_type, dst_pos,
1129                                                 src_type, src_pos, n);
1130                 if (!pw->p[i].set)
1131                         goto error;
1132                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1133                                         dst_type, dst_pos, src_type, src_pos, n);
1134                 if (!pw->p[i].FIELD)
1135                         goto error;
1136         }
1137
1138         return pw;
1139 error:
1140         FN(PW,free)(pw);
1141         return NULL;
1142 }
1143 #endif
1144
1145 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1146 {
1147         int i;
1148
1149         if (isl_int_is_one(v))
1150                 return pw;
1151         if (pw && isl_int_is_zero(v)) {
1152                 PW *zero;
1153                 isl_space *dim = FN(PW,get_space)(pw);
1154 #ifdef HAS_TYPE
1155                 zero = FN(PW,ZERO)(dim, pw->type);
1156 #else
1157                 zero = FN(PW,ZERO)(dim);
1158 #endif
1159                 FN(PW,free)(pw);
1160                 return zero;
1161         }
1162         pw = FN(PW,cow)(pw);
1163         if (!pw)
1164                 return NULL;
1165         if (pw->n == 0)
1166                 return pw;
1167
1168 #ifdef HAS_TYPE
1169         if (isl_int_is_neg(v))
1170                 pw->type = isl_fold_type_negate(pw->type);
1171 #endif
1172         for (i = 0; i < pw->n; ++i) {
1173                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1174                 if (!pw->p[i].FIELD)
1175                         goto error;
1176         }
1177
1178         return pw;
1179 error:
1180         FN(PW,free)(pw);
1181         return NULL;
1182 }
1183
1184 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1185 {
1186         return FN(PW,mul_isl_int)(pw, v);
1187 }