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