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