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)(FN(EL,get_space)(el), type, 1);
 103 #else
 104         pw = FN(PW,alloc_size)(FN(EL,get_space)(el), 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 const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
 177 {
 178         return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;
 179 }
 180
 181 int FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
 182 {
 183         return pw ? isl_space_has_tuple_id(pw->dim, type) : -1;
 184 }
 185
 186 __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
 187 {
 188         return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;
 189 }
 190
 191 int FN(PW,IS_ZERO)(__isl_keep PW *pw)
 192 {
 193         if (!pw)
 194                 return -1;
 195
 196         return pw->n == 0;
 197 }
 198
 199 #ifndef NO_REALIGN
 200 __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
 201         __isl_take isl_reordering *exp)
 202 {
 203         int i;
 204
 205         pw = FN(PW,cow)(pw);
 206         if (!pw || !exp)
 207                 return NULL;
 208
 209         for (i = 0; i < pw->n; ++i) {
 210                 pw->p[i].set = isl_set_realign(pw->p[i].set,
 211                                                     isl_reordering_copy(exp));
 212                 if (!pw->p[i].set)
 213                         goto error;
 214                 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD,
 215                                                     isl_reordering_copy(exp));
 216                 if (!pw->p[i].FIELD)
 217                         goto error;
 218         }
 219
 220         pw = FN(PW,reset_domain_space)(pw, isl_space_copy(exp->dim));
 221
 222         isl_reordering_free(exp);
 223         return pw;
 224 error:
 225         isl_reordering_free(exp);
 226         FN(PW,free)(pw);
 227         return NULL;
 228 }
 229
 230 /* Align the parameters of "pw" to those of "model".
 231  */
 232 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
 233 {
 234         isl_ctx *ctx;
 235
 236         if (!pw || !model)
 237                 goto error;
 238
 239         ctx = isl_space_get_ctx(model);
 240         if (!isl_space_has_named_params(model))
 241                 isl_die(ctx, isl_error_invalid,
 242                         "model has unnamed parameters", goto error);
 243         if (!isl_space_has_named_params(pw->dim))
 244                 isl_die(ctx, isl_error_invalid,
 245                         "input has unnamed parameters", goto error);
 246         if (!isl_space_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
 247                 isl_reordering *exp;
 248
 249                 model = isl_space_drop_dims(model, isl_dim_in,
 250                                         0, isl_space_dim(model, isl_dim_in));
 251                 model = isl_space_drop_dims(model, isl_dim_out,
 252                                         0, isl_space_dim(model, isl_dim_out));
 253                 exp = isl_parameter_alignment_reordering(pw->dim, model);
 254                 exp = isl_reordering_extend_space(exp,
 255                                         FN(PW,get_domain_space)(pw));
 256                 pw = FN(PW,realign_domain)(pw, exp);
 257         }
 258
 259         isl_space_free(model);
 260         return pw;
 261 error:
 262         isl_space_free(model);
 263         FN(PW,free)(pw);
 264         return NULL;
 265 }
 266
 267 static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
 268         __isl_take PW *pw2,
 269         __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
 270 {
 271         isl_ctx *ctx;
 272
 273         if (!pw1 || !pw2)
 274                 goto error;
 275         if (isl_space_match(pw1->dim, isl_dim_param, pw2->dim, isl_dim_param))
 276                 return fn(pw1, pw2);
 277         ctx = FN(PW,get_ctx)(pw1);
 278         if (!isl_space_has_named_params(pw1->dim) ||
 279             !isl_space_has_named_params(pw2->dim))
 280                 isl_die(ctx, isl_error_invalid,
 281                         "unaligned unnamed parameters", goto error);
 282         pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2));
 283         pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1));
 284         return fn(pw1, pw2);
 285 error:
 286         FN(PW,free)(pw1);
 287         FN(PW,free)(pw2);
 288         return NULL;
 289 }
 290
 291 static __isl_give PW *FN(PW,align_params_pw_set_and)(__isl_take PW *pw,
 292         __isl_take isl_set *set,
 293         __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set))
 294 {
 295         isl_ctx *ctx;
 296
 297         if (!pw || !set)
 298                 goto error;
 299         if (isl_space_match(pw->dim, isl_dim_param, set->dim, isl_dim_param))
 300                 return fn(pw, set);
 301         ctx = FN(PW,get_ctx)(pw);
 302         if (!isl_space_has_named_params(pw->dim) ||
 303             !isl_space_has_named_params(set->dim))
 304                 isl_die(ctx, isl_error_invalid,
 305                         "unaligned unnamed parameters", goto error);
 306         pw = FN(PW,align_params)(pw, isl_set_get_space(set));
 307         set = isl_set_align_params(set, FN(PW,get_space)(pw));
 308         return fn(pw, set);
 309 error:
 310         FN(PW,free)(pw);
 311         isl_set_free(set);
 312         return NULL;
 313 }
 314 #endif
 315
 316 static __isl_give PW *FN(PW,add_aligned)(__isl_take PW *pw1, __isl_take PW *pw2)
 317 {
 318         int i, j, n;
 319         struct PW *res;
 320         isl_ctx *ctx;
 321         isl_set *set;
 322
 323         if (!pw1 || !pw2)
 324                 goto error;
 325
 326         ctx = isl_space_get_ctx(pw1->dim);
 327 #ifdef HAS_TYPE
 328         if (pw1->type != pw2->type)
 329                 isl_die(ctx, isl_error_invalid,
 330                         "fold types don't match", goto error);
 331 #endif
 332         isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
 333
 334         if (FN(PW,IS_ZERO)(pw1)) {
 335                 FN(PW,free)(pw1);
 336                 return pw2;
 337         }
 338
 339         if (FN(PW,IS_ZERO)(pw2)) {
 340                 FN(PW,free)(pw2);
 341                 return pw1;
 342         }
 343
 344         n = (pw1->n + 1) * (pw2->n + 1);
 345 #ifdef HAS_TYPE
 346         res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->type, n);
 347 #else
 348         res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), n);
 349 #endif
 350
 351         for (i = 0; i < pw1->n; ++i) {
 352                 set = isl_set_copy(pw1->p[i].set);
 353                 for (j = 0; j < pw2->n; ++j) {
 354                         struct isl_set *common;
 355                         EL *sum;
 356                         set = isl_set_subtract(set,
 357                                         isl_set_copy(pw2->p[j].set));
 358                         common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
 359                                                 isl_set_copy(pw2->p[j].set));
 360                         if (isl_set_plain_is_empty(common)) {
 361                                 isl_set_free(common);
 362                                 continue;
 363                         }
 364
 365                         sum = FN(EL,add_on_domain)(common,
 366                                                    FN(EL,copy)(pw1->p[i].FIELD),
 367                                                    FN(EL,copy)(pw2->p[j].FIELD));
 368
 369                         res = FN(PW,add_piece)(res, common, sum);
 370                 }
 371                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
 372         }
 373
 374         for (j = 0; j < pw2->n; ++j) {
 375                 set = isl_set_copy(pw2->p[j].set);
 376                 for (i = 0; i < pw1->n; ++i)
 377                         set = isl_set_subtract(set,
 378                                         isl_set_copy(pw1->p[i].set));
 379                 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
 380         }
 381
 382         FN(PW,free)(pw1);
 383         FN(PW,free)(pw2);
 384
 385         return res;
 386 error:
 387         FN(PW,free)(pw1);
 388         FN(PW,free)(pw2);
 389         return NULL;
 390 }
 391
 392 __isl_give PW *FN(PW,add)(__isl_take PW *pw1, __isl_take PW *pw2)
 393 {
 394         return FN(PW,align_params_pw_pw_and)(pw1, pw2, &FN(PW,add_aligned));
 395 }
 396
 397 /* Make sure "pw" has room for at least "n" more pieces.
 398  *
 399  * If there is only one reference to pw, we extend it in place.
 400  * Otherwise, we create a new PW and copy the pieces.
 401  */
 402 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
 403 {
 404         int i;
 405         isl_ctx *ctx;
 406         PW *res;
 407
 408         if (!pw)
 409                 return NULL;
 410         if (pw->n + n <= pw->size)
 411                 return pw;
 412         ctx = FN(PW,get_ctx)(pw);
 413         n += pw->n;
 414         if (pw->ref == 1) {
 415                 res = isl_realloc(ctx, pw, struct PW,
 416                             sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
 417                 if (!res)
 418                         return FN(PW,free)(pw);
 419                 res->size = n;
 420                 return res;
 421         }
 422 #ifdef HAS_TYPE
 423         res = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, n);
 424 #else
 425         res = FN(PW,alloc_size)(isl_space_copy(pw->dim), n);
 426 #endif
 427         if (!res)
 428                 return FN(PW,free)(pw);
 429         for (i = 0; i < pw->n; ++i)
 430                 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
 431                                             FN(EL,copy)(pw->p[i].FIELD));
 432         FN(PW,free)(pw);
 433         return res;
 434 }
 435
 436 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
 437         __isl_take PW *pw2)
 438 {
 439         int i;
 440         isl_ctx *ctx;
 441
 442         if (!pw1 || !pw2)
 443                 goto error;
 444
 445         if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
 446                 return FN(PW,add_disjoint_aligned)(pw2, pw1);
 447
 448         ctx = isl_space_get_ctx(pw1->dim);
 449 #ifdef HAS_TYPE
 450         if (pw1->type != pw2->type)
 451                 isl_die(ctx, isl_error_invalid,
 452                         "fold types don't match", goto error);
 453 #endif
 454         isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
 455
 456         if (FN(PW,IS_ZERO)(pw1)) {
 457                 FN(PW,free)(pw1);
 458                 return pw2;
 459         }
 460
 461         if (FN(PW,IS_ZERO)(pw2)) {
 462                 FN(PW,free)(pw2);
 463                 return pw1;
 464         }
 465
 466         pw1 = FN(PW,grow)(pw1, pw2->n);
 467         if (!pw1)
 468                 goto error;
 469
 470         for (i = 0; i < pw2->n; ++i)
 471                 pw1 = FN(PW,add_piece)(pw1,
 472                                 isl_set_copy(pw2->p[i].set),
 473                                 FN(EL,copy)(pw2->p[i].FIELD));
 474
 475         FN(PW,free)(pw2);
 476
 477         return pw1;
 478 error:
 479         FN(PW,free)(pw1);
 480         FN(PW,free)(pw2);
 481         return NULL;
 482 }
 483
 484 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
 485 {
 486         return FN(PW,align_params_pw_pw_and)(pw1, pw2,
 487                                                 &FN(PW,add_disjoint_aligned));
 488 }
 489
 490 #ifndef NO_NEG
 491 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
 492 {
 493         int i;
 494
 495         if (!pw)
 496                 return NULL;
 497
 498         if (FN(PW,IS_ZERO)(pw))
 499                 return pw;
 500
 501         pw = FN(PW,cow)(pw);
 502         if (!pw)
 503                 return NULL;
 504
 505         for (i = 0; i < pw->n; ++i) {
 506                 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
 507                 if (!pw->p[i].FIELD)
 508                         return FN(PW,free)(pw);
 509         }
 510
 511         return pw;
 512 }
 513
 514 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
 515 {
 516         return FN(PW,add)(pw1, FN(PW,neg)(pw2));
 517 }
 518 #endif
 519
 520 #ifndef NO_EVAL
 521 __isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw,
 522         __isl_take isl_point *pnt)
 523 {
 524         int i;
 525         int found = 0;
 526         isl_ctx *ctx;
 527         isl_space *pnt_dim = NULL;
 528         isl_qpolynomial *qp;
 529
 530         if (!pw || !pnt)
 531                 goto error;
 532         ctx = isl_point_get_ctx(pnt);
 533         pnt_dim = isl_point_get_space(pnt);
 534         isl_assert(ctx, isl_space_is_domain(pnt_dim, pw->dim), goto error);
 535
 536         for (i = 0; i < pw->n; ++i) {
 537                 found = isl_set_contains_point(pw->p[i].set, pnt);
 538                 if (found < 0)
 539                         goto error;
 540                 if (found)
 541                         break;
 542         }
 543         if (found)
 544                 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
 545                                             isl_point_copy(pnt));
 546         else
 547                 qp = isl_qpolynomial_zero_on_domain(FN(PW,get_domain_space)(pw));
 548         FN(PW,free)(pw);
 549         isl_space_free(pnt_dim);
 550         isl_point_free(pnt);
 551         return qp;
 552 error:
 553         FN(PW,free)(pw);
 554         isl_space_free(pnt_dim);
 555         isl_point_free(pnt);
 556         return NULL;
 557 }
 558 #endif
 559
 560 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
 561 {
 562         int i;
 563         isl_set *dom;
 564
 565         if (!pw)
 566                 return NULL;
 567
 568         dom = isl_set_empty(FN(PW,get_domain_space)(pw));
 569         for (i = 0; i < pw->n; ++i)
 570                 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
 571
 572         FN(PW,free)(pw);
 573
 574         return dom;
 575 }
 576
 577 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
 578         __isl_take isl_set *set)
 579 {
 580         int i;
 581
 582         if (!pw || !set)
 583                 goto error;
 584
 585         if (pw->n == 0) {
 586                 isl_set_free(set);
 587                 return pw;
 588         }
 589
 590         pw = FN(PW,cow)(pw);
 591         if (!pw)
 592                 goto error;
 593
 594         for (i = pw->n - 1; i >= 0; --i) {
 595                 isl_basic_set *aff;
 596                 pw->p[i].set = isl_set_intersect(pw->p[i].set, isl_set_copy(set));
 597                 if (!pw->p[i].set)
 598                         goto error;
 599                 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
 600                 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD,
 601                                                                 aff);
 602                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 603                         isl_set_free(pw->p[i].set);
 604                         FN(EL,free)(pw->p[i].FIELD);
 605                         if (i != pw->n - 1)
 606                                 pw->p[i] = pw->p[pw->n - 1];
 607                         pw->n--;
 608                 }
 609         }
 610
 611         isl_set_free(set);
 612         return pw;
 613 error:
 614         isl_set_free(set);
 615         FN(PW,free)(pw);
 616         return NULL;
 617 }
 618
 619 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
 620         __isl_take isl_set *context)
 621 {
 622         return FN(PW,align_params_pw_set_and)(pw, context,
 623                                         &FN(PW,intersect_domain_aligned));
 624 }
 625
 626 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
 627         __isl_take isl_set *context)
 628 {
 629         int i;
 630         isl_basic_set *hull = NULL;
 631
 632         if (!pw || !context)
 633                 goto error;
 634
 635         if (pw->n == 0) {
 636                 isl_set_free(context);
 637                 return pw;
 638         }
 639
 640         if (!isl_space_match(pw->dim, isl_dim_param,
 641                                 context->dim, isl_dim_param)) {
 642                 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
 643                 context = isl_set_align_params(context, FN(PW,get_space)(pw));
 644         }
 645
 646         context = isl_set_compute_divs(context);
 647         hull = isl_set_simple_hull(isl_set_copy(context));
 648
 649         pw = FN(PW,cow)(pw);
 650         if (!pw)
 651                 goto error;
 652
 653         for (i = pw->n - 1; i >= 0; --i) {
 654                 pw->p[i].set = isl_set_intersect(pw->p[i].set,
 655                                                  isl_set_copy(context));
 656                 if (!pw->p[i].set)
 657                         goto error;
 658                 pw->p[i].FIELD = FN(EL,gist)(pw->p[i].FIELD,
 659                                              isl_set_copy(pw->p[i].set));
 660                 pw->p[i].set = isl_set_gist_basic_set(pw->p[i].set,
 661                                                 isl_basic_set_copy(hull));
 662                 if (!pw->p[i].set)
 663                         goto error;
 664                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 665                         isl_set_free(pw->p[i].set);
 666                         FN(EL,free)(pw->p[i].FIELD);
 667                         if (i != pw->n - 1)
 668                                 pw->p[i] = pw->p[pw->n - 1];
 669                         pw->n--;
 670                 }
 671         }
 672
 673         isl_basic_set_free(hull);
 674         isl_set_free(context);
 675
 676         return pw;
 677 error:
 678         FN(PW,free)(pw);
 679         isl_basic_set_free(hull);
 680         isl_set_free(context);
 681         return NULL;
 682 }
 683
 684 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
 685 {
 686         return FN(PW,align_params_pw_set_and)(pw, context, &FN(PW,gist_aligned));
 687 }
 688
 689 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
 690 {
 691         int i, j;
 692
 693         if (!pw)
 694                 return NULL;
 695         if (pw->n == 0)
 696                 return pw;
 697
 698         for (i = pw->n - 1; i >= 0; --i) {
 699                 for (j = i - 1; j >= 0; --j) {
 700                         if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
 701                                                         pw->p[j].FIELD))
 702                                 continue;
 703                         pw->p[j].set = isl_set_union(pw->p[j].set,
 704                                                         pw->p[i].set);
 705                         FN(EL,free)(pw->p[i].FIELD);
 706                         if (i != pw->n - 1)
 707                                 pw->p[i] = pw->p[pw->n - 1];
 708                         pw->n--;
 709                         break;
 710                 }
 711                 if (j >= 0)
 712                         continue;
 713                 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
 714                 if (!pw->p[i].set)
 715                         goto error;
 716         }
 717
 718         return pw;
 719 error:
 720         FN(PW,free)(pw);
 721         return NULL;
 722 }
 723
 724 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
 725 {
 726         return pw ? isl_space_get_ctx(pw->dim) : NULL;
 727 }
 728
 729 #ifndef NO_INVOLVES_DIMS
 730 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
 731         unsigned first, unsigned n)
 732 {
 733         int i;
 734         enum isl_dim_type set_type;
 735
 736         if (!pw)
 737                 return -1;
 738         if (pw->n == 0 || n == 0)
 739                 return 0;
 740
 741         set_type = type == isl_dim_in ? isl_dim_set : type;
 742
 743         for (i = 0; i < pw->n; ++i) {
 744                 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
 745                                                         type, first, n);
 746                 if (involves < 0 || involves)
 747                         return involves;
 748                 involves = isl_set_involves_dims(pw->p[i].set,
 749                                                         set_type, first, n);
 750                 if (involves < 0 || involves)
 751                         return involves;
 752         }
 753         return 0;
 754 }
 755 #endif
 756
 757 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
 758         enum isl_dim_type type, unsigned pos, const char *s)
 759 {
 760         int i;
 761         enum isl_dim_type set_type;
 762
 763         pw = FN(PW,cow)(pw);
 764         if (!pw)
 765                 return NULL;
 766
 767         set_type = type == isl_dim_in ? isl_dim_set : type;
 768
 769         pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
 770         if (!pw->dim)
 771                 goto error;
 772
 773         for (i = 0; i < pw->n; ++i) {
 774                 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
 775                                                         set_type, pos, s);
 776                 if (!pw->p[i].set)
 777                         goto error;
 778                 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
 779                 if (!pw->p[i].FIELD)
 780                         goto error;
 781         }
 782
 783         return pw;
 784 error:
 785         FN(PW,free)(pw);
 786         return NULL;
 787 }
 788
 789 #ifndef NO_DROP_DIMS
 790 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
 791         enum isl_dim_type type, unsigned first, unsigned n)
 792 {
 793         int i;
 794         enum isl_dim_type set_type;
 795
 796         if (!pw)
 797                 return NULL;
 798         if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
 799                 return pw;
 800
 801         set_type = type == isl_dim_in ? isl_dim_set : type;
 802
 803         pw = FN(PW,cow)(pw);
 804         if (!pw)
 805                 return NULL;
 806         pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
 807         if (!pw->dim)
 808                 goto error;
 809         for (i = 0; i < pw->n; ++i) {
 810                 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
 811                 if (!pw->p[i].set)
 812                         goto error;
 813                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 814                 if (!pw->p[i].FIELD)
 815                         goto error;
 816         }
 817
 818         return pw;
 819 error:
 820         FN(PW,free)(pw);
 821         return NULL;
 822 }
 823
 824 /* This function is very similar to drop_dims.
 825  * The only difference is that the cells may still involve
 826  * the specified dimensions.  They are removed using
 827  * isl_set_project_out instead of isl_set_drop.
 828  */
 829 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
 830         enum isl_dim_type type, unsigned first, unsigned n)
 831 {
 832         int i;
 833         enum isl_dim_type set_type;
 834
 835         if (!pw)
 836                 return NULL;
 837         if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
 838                 return pw;
 839
 840         set_type = type == isl_dim_in ? isl_dim_set : type;
 841
 842         pw = FN(PW,cow)(pw);
 843         if (!pw)
 844                 return NULL;
 845         pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
 846         if (!pw->dim)
 847                 goto error;
 848         for (i = 0; i < pw->n; ++i) {
 849                 pw->p[i].set = isl_set_project_out(pw->p[i].set,
 850                                                         set_type, first, n);
 851                 if (!pw->p[i].set)
 852                         goto error;
 853                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 854                 if (!pw->p[i].FIELD)
 855                         goto error;
 856         }
 857
 858         return pw;
 859 error:
 860         FN(PW,free)(pw);
 861         return NULL;
 862 }
 863
 864 /* Project the domain of pw onto its parameter space.
 865  */
 866 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
 867 {
 868         isl_space *space;
 869         unsigned n;
 870
 871         n = FN(PW,dim)(pw, isl_dim_in);
 872         pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
 873         space = FN(PW,get_domain_space)(pw);
 874         space = isl_space_params(space);
 875         pw = FN(PW,reset_domain_space)(pw, space);
 876         return pw;
 877 }
 878 #endif
 879
 880 #ifndef NO_INSERT_DIMS
 881 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
 882         unsigned first, unsigned n)
 883 {
 884         int i;
 885         enum isl_dim_type set_type;
 886
 887         if (!pw)
 888                 return NULL;
 889         if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
 890                 return pw;
 891
 892         set_type = type == isl_dim_in ? isl_dim_set : type;
 893
 894         pw = FN(PW,cow)(pw);
 895         if (!pw)
 896                 return NULL;
 897
 898         pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
 899         if (!pw->dim)
 900                 goto error;
 901
 902         for (i = 0; i < pw->n; ++i) {
 903                 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
 904                                                             set_type, first, n);
 905                 if (!pw->p[i].set)
 906                         goto error;
 907                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 908                                                                 type, first, n);
 909                 if (!pw->p[i].FIELD)
 910                         goto error;
 911         }
 912
 913         return pw;
 914 error:
 915         FN(PW,free)(pw);
 916         return NULL;
 917 }
 918 #endif
 919
 920 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 921         enum isl_dim_type type, unsigned pos, isl_int v)
 922 {
 923         int i;
 924
 925         if (!pw)
 926                 return NULL;
 927
 928         if (type == isl_dim_in)
 929                 type = isl_dim_set;
 930
 931         pw = FN(PW,cow)(pw);
 932         if (!pw)
 933                 return NULL;
 934         for (i = 0; i < pw->n; ++i) {
 935                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 936                 if (!pw->p[i].set)
 937                         goto error;
 938         }
 939
 940         return pw;
 941 error:
 942         FN(PW,free)(pw);
 943         return NULL;
 944 }
 945
 946 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 947 {
 948         return pw ? isl_space_dim(pw->dim, type) : 0;
 949 }
 950
 951 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 952         enum isl_dim_type type, unsigned first, unsigned n)
 953 {
 954         int i;
 955
 956         if (!pw)
 957                 return NULL;
 958         if (n == 0)
 959                 return pw;
 960
 961         if (type == isl_dim_in)
 962                 type = isl_dim_set;
 963
 964         pw = FN(PW,cow)(pw);
 965         if (!pw)
 966                 return NULL;
 967         if (!pw->dim)
 968                 goto error;
 969         for (i = 0; i < pw->n; ++i) {
 970                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 971                 if (!pw->p[i].set)
 972                         goto error;
 973         }
 974
 975         return pw;
 976 error:
 977         FN(PW,free)(pw);
 978         return NULL;
 979 }
 980
 981 #ifndef NO_OPT
 982 /* Compute the maximal value attained by the piecewise quasipolynomial
 983  * on its domain or zero if the domain is empty.
 984  * In the worst case, the domain is scanned completely,
 985  * so the domain is assumed to be bounded.
 986  */
 987 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 988 {
 989         int i;
 990         isl_qpolynomial *opt;
 991
 992         if (!pw)
 993                 return NULL;
 994
 995         if (pw->n == 0) {
 996                 isl_space *dim = isl_space_copy(pw->dim);
 997                 FN(PW,free)(pw);
 998                 return isl_qpolynomial_zero_on_domain(dim);
 999         }
1000
1001         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1002                                         isl_set_copy(pw->p[0].set), max);
1003         for (i = 1; i < pw->n; ++i) {
1004                 isl_qpolynomial *opt_i;
1005                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1006                                                 isl_set_copy(pw->p[i].set), max);
1007                 if (max)
1008                         opt = isl_qpolynomial_max_cst(opt, opt_i);
1009                 else
1010                         opt = isl_qpolynomial_min_cst(opt, opt_i);
1011         }
1012
1013         FN(PW,free)(pw);
1014         return opt;
1015 }
1016
1017 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
1018 {
1019         return FN(PW,opt)(pw, 1);
1020 }
1021
1022 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
1023 {
1024         return FN(PW,opt)(pw, 0);
1025 }
1026 #endif
1027
1028 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1029 {
1030         return pw ? isl_space_copy(pw->dim) : NULL;
1031 }
1032
1033 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1034 {
1035         return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1036 }
1037
1038 #ifndef NO_RESET_DIM
1039 /* Reset the space of "pw".  Since we don't know if the elements
1040  * represent the spaces themselves or their domains, we pass along
1041  * both when we call their reset_space_and_domain.
1042  */
1043 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1044         __isl_take isl_space *space, __isl_take isl_space *domain)
1045 {
1046         int i;
1047
1048         pw = FN(PW,cow)(pw);
1049         if (!pw || !space || !domain)
1050                 goto error;
1051
1052         for (i = 0; i < pw->n; ++i) {
1053                 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1054                                                  isl_space_copy(domain));
1055                 if (!pw->p[i].set)
1056                         goto error;
1057                 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1058                               isl_space_copy(space), isl_space_copy(domain));
1059                 if (!pw->p[i].FIELD)
1060                         goto error;
1061         }
1062
1063         isl_space_free(domain);
1064
1065         isl_space_free(pw->dim);
1066         pw->dim = space;
1067
1068         return pw;
1069 error:
1070         isl_space_free(domain);
1071         isl_space_free(space);
1072         FN(PW,free)(pw);
1073         return NULL;
1074 }
1075
1076 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1077         __isl_take isl_space *domain)
1078 {
1079         isl_space *space;
1080
1081         space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1082                                                    FN(PW,get_space)(pw));
1083         return FN(PW,reset_space_and_domain)(pw, space, domain);
1084 }
1085
1086 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1087 {
1088         isl_space *domain;
1089
1090         domain = isl_space_domain(isl_space_copy(dim));
1091         return FN(PW,reset_space_and_domain)(pw, dim, domain);
1092 }
1093
1094 __isl_give PW *FN(PW,set_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type,
1095         __isl_take isl_id *id)
1096 {
1097         isl_space *space;
1098
1099         pw = FN(PW,cow)(pw);
1100         if (!pw)
1101                 return isl_id_free(id);
1102
1103         space = FN(PW,get_space)(pw);
1104         space = isl_space_set_tuple_id(space, type, id);
1105
1106         return FN(PW,reset_space)(pw, space);
1107 }
1108
1109 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1110         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1111 {
1112         pw = FN(PW,cow)(pw);
1113         if (!pw)
1114                 return isl_id_free(id);
1115         pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1116         return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1117 }
1118 #endif
1119
1120 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1121 {
1122         if (!pw1 || !pw2)
1123                 return -1;
1124
1125         return isl_space_is_equal(pw1->dim, pw2->dim);
1126 }
1127
1128 #ifndef NO_MORPH
1129 __isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw,
1130         __isl_take isl_morph *morph)
1131 {
1132         int i;
1133         isl_ctx *ctx;
1134
1135         if (!pw || !morph)
1136                 goto error;
1137
1138         ctx = isl_space_get_ctx(pw->dim);
1139         isl_assert(ctx, isl_space_is_domain(morph->dom->dim, pw->dim),
1140                 goto error);
1141
1142         pw = FN(PW,cow)(pw);
1143         if (!pw)
1144                 goto error;
1145         pw->dim = isl_space_extend_domain_with_range(
1146                         isl_space_copy(morph->ran->dim), pw->dim);
1147         if (!pw->dim)
1148                 goto error;
1149
1150         for (i = 0; i < pw->n; ++i) {
1151                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1152                 if (!pw->p[i].set)
1153                         goto error;
1154                 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD,
1155                                                 isl_morph_copy(morph));
1156                 if (!pw->p[i].FIELD)
1157                         goto error;
1158         }
1159
1160         isl_morph_free(morph);
1161
1162         return pw;
1163 error:
1164         FN(PW,free)(pw);
1165         isl_morph_free(morph);
1166         return NULL;
1167 }
1168 #endif
1169
1170 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1171         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1172         void *user)
1173 {
1174         int i;
1175
1176         if (!pw)
1177                 return -1;
1178
1179         for (i = 0; i < pw->n; ++i)
1180                 if (fn(isl_set_copy(pw->p[i].set),
1181                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1182                         return -1;
1183
1184         return 0;
1185 }
1186
1187 #ifndef NO_LIFT
1188 static int any_divs(__isl_keep isl_set *set)
1189 {
1190         int i;
1191
1192         if (!set)
1193                 return -1;
1194
1195         for (i = 0; i < set->n; ++i)
1196                 if (set->p[i]->n_div > 0)
1197                         return 1;
1198
1199         return 0;
1200 }
1201
1202 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1203         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1204                     void *user), void *user)
1205 {
1206         int i;
1207
1208         if (!set || !el)
1209                 goto error;
1210
1211         for (i = 0; i < set->n; ++i) {
1212                 isl_set *lift;
1213                 EL *copy;
1214
1215                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1216                 lift = isl_set_lift(lift);
1217
1218                 copy = FN(EL,copy)(el);
1219                 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1220
1221                 if (fn(lift, copy, user) < 0)
1222                         goto error;
1223         }
1224
1225         isl_set_free(set);
1226         FN(EL,free)(el);
1227
1228         return 0;
1229 error:
1230         isl_set_free(set);
1231         FN(EL,free)(el);
1232         return -1;
1233 }
1234
1235 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1236         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1237                     void *user), void *user)
1238 {
1239         int i;
1240
1241         if (!pw)
1242                 return -1;
1243
1244         for (i = 0; i < pw->n; ++i) {
1245                 isl_set *set;
1246                 EL *el;
1247
1248                 set = isl_set_copy(pw->p[i].set);
1249                 el = FN(EL,copy)(pw->p[i].FIELD);
1250                 if (!any_divs(set)) {
1251                         if (fn(set, el, user) < 0)
1252                                 return -1;
1253                         continue;
1254                 }
1255                 if (foreach_lifted_subset(set, el, fn, user) < 0)
1256                         return -1;
1257         }
1258
1259         return 0;
1260 }
1261 #endif
1262
1263 #ifndef NO_MOVE_DIMS
1264 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1265         enum isl_dim_type dst_type, unsigned dst_pos,
1266         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1267 {
1268         int i;
1269
1270         pw = FN(PW,cow)(pw);
1271         if (!pw)
1272                 return NULL;
1273
1274         pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1275         if (!pw->dim)
1276                 goto error;
1277
1278         for (i = 0; i < pw->n; ++i) {
1279                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1280                                         dst_type, dst_pos, src_type, src_pos, n);
1281                 if (!pw->p[i].FIELD)
1282                         goto error;
1283         }
1284
1285         if (dst_type == isl_dim_in)
1286                 dst_type = isl_dim_set;
1287         if (src_type == isl_dim_in)
1288                 src_type = isl_dim_set;
1289
1290         for (i = 0; i < pw->n; ++i) {
1291                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1292                                                 dst_type, dst_pos,
1293                                                 src_type, src_pos, n);
1294                 if (!pw->p[i].set)
1295                         goto error;
1296         }
1297
1298         return pw;
1299 error:
1300         FN(PW,free)(pw);
1301         return NULL;
1302 }
1303 #endif
1304
1305 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1306 {
1307         int i;
1308
1309         if (isl_int_is_one(v))
1310                 return pw;
1311         if (pw && isl_int_is_zero(v)) {
1312                 PW *zero;
1313                 isl_space *dim = FN(PW,get_space)(pw);
1314 #ifdef HAS_TYPE
1315                 zero = FN(PW,ZERO)(dim, pw->type);
1316 #else
1317                 zero = FN(PW,ZERO)(dim);
1318 #endif
1319                 FN(PW,free)(pw);
1320                 return zero;
1321         }
1322         pw = FN(PW,cow)(pw);
1323         if (!pw)
1324                 return NULL;
1325         if (pw->n == 0)
1326                 return pw;
1327
1328 #ifdef HAS_TYPE
1329         if (isl_int_is_neg(v))
1330                 pw->type = isl_fold_type_negate(pw->type);
1331 #endif
1332         for (i = 0; i < pw->n; ++i) {
1333                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1334                 if (!pw->p[i].FIELD)
1335                         goto error;
1336         }
1337
1338         return pw;
1339 error:
1340         FN(PW,free)(pw);
1341         return NULL;
1342 }
1343
1344 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1345 {
1346         return FN(PW,mul_isl_int)(pw, v);
1347 }
1348
1349 static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2)
1350 {
1351         const isl_set *set1 = *(const isl_set **)p1;
1352         const isl_set *set2 = *(const isl_set **)p2;
1353
1354         return isl_set_plain_cmp(set1, set2);
1355 }
1356
1357 /* We normalize in place, but if anything goes wrong we need
1358  * to return NULL, so we need to make sure we don't change the
1359  * meaning of any possible other copies of map.
1360  */
1361 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1362 {
1363         int i, j;
1364         isl_set *set;
1365
1366         if (!pw)
1367                 return NULL;
1368         for (i = 0; i < pw->n; ++i) {
1369                 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1370                 if (!set)
1371                         return FN(PW,free)(pw);
1372                 isl_set_free(pw->p[i].set);
1373                 pw->p[i].set = set;
1374         }
1375         qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp));
1376         for (i = pw->n - 1; i >= 1; --i) {
1377                 if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set))
1378                         continue;
1379                 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1380                         continue;
1381                 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1382                                     isl_set_copy(pw->p[i].set));
1383                 if (!set)
1384                         return FN(PW,free)(pw);
1385                 isl_set_free(pw->p[i].set);
1386                 FN(EL,free)(pw->p[i].FIELD);
1387                 isl_set_free(pw->p[i - 1].set);
1388                 pw->p[i - 1].set = set;
1389                 for (j = i + 1; j < pw->n; ++j)
1390                         pw->p[j - 1] = pw->p[j];
1391                 pw->n--;
1392         }
1393
1394         return pw;
1395 }
1396
1397 /* Is pw1 obviously equal to pw2?
1398  * That is, do they have obviously identical cells and obviously identical
1399  * elements on each cell?
1400  */
1401 int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1402 {
1403         int i;
1404         int equal;
1405
1406         if (!pw1 || !pw2)
1407                 return -1;
1408
1409         if (pw1 == pw2)
1410                 return 1;
1411         if (!isl_space_is_equal(pw1->dim, pw2->dim))
1412                 return 0;
1413
1414         pw1 = FN(PW,copy)(pw1);
1415         pw2 = FN(PW,copy)(pw2);
1416         pw1 = FN(PW,normalize)(pw1);
1417         pw2 = FN(PW,normalize)(pw2);
1418         if (!pw1 || !pw2)
1419                 goto error;
1420
1421         equal = pw1->n == pw2->n;
1422         for (i = 0; equal && i < pw1->n; ++i) {
1423                 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1424                 if (equal < 0)
1425                         goto error;
1426                 if (!equal)
1427                         break;
1428                 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1429                 if (equal < 0)
1430                         goto error;
1431         }
1432
1433         FN(PW,free)(pw1);
1434         FN(PW,free)(pw2);
1435         return equal;
1436 error:
1437         FN(PW,free)(pw1);
1438         FN(PW,free)(pw2);
1439         return -1;
1440 }