isl_pw_templ.c

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