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 static __isl_give PW *FN(PW,alloc_)(__isl_take isl_dim *dim,
   8         enum isl_fold type, int n)
   9 #else
  10 static __isl_give PW *FN(PW,alloc_)(__isl_take isl_dim *dim, int n)
  11 #endif
  12 {
  13         isl_ctx *ctx;
  14         struct PW *pw;
  15
  16         if (!dim)
  17                 return NULL;
  18         ctx = isl_dim_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_dim_free(dim);
  35         return NULL;
  36 }
  37
  38 #ifdef HAS_TYPE
  39 __isl_give PW *FN(PW,ZERO)(__isl_take isl_dim *dim, enum isl_fold type)
  40 {
  41         return FN(PW,alloc_)(dim, type, 0);
  42 }
  43 #else
  44 __isl_give PW *FN(PW,ZERO)(__isl_take isl_dim *dim)
  45 {
  46         return FN(PW,alloc_)(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_dim *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_dim(el));
  72         isl_assert(ctx, isl_dim_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_dim_free(el_dim);
  80         return pw;
  81 error:
  82         isl_dim_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_)(isl_set_get_dim(set), type, 1);
 103 #else
 104         pw = FN(PW,alloc_)(isl_set_get_dim(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_)(isl_dim_copy(pw->dim), pw->type, pw->n);
 124 #else
 125         dup = FN(PW,alloc_)(isl_dim_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_dim_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_dim)(pw, isl_dim_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_dim *model)
 217 {
 218         isl_ctx *ctx;
 219
 220         if (!pw || !model)
 221                 goto error;
 222
 223         ctx = isl_dim_get_ctx(model);
 224         if (!isl_dim_has_named_params(model))
 225                 isl_die(ctx, isl_error_invalid,
 226                         "model has unnamed parameters", goto error);
 227         if (!isl_dim_has_named_params(pw->dim))
 228                 isl_die(ctx, isl_error_invalid,
 229                         "input has unnamed parameters", goto error);
 230         if (!isl_dim_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
 231                 isl_reordering *exp;
 232
 233                 model = isl_dim_drop(model, isl_dim_in,
 234                                         0, isl_dim_size(model, isl_dim_in));
 235                 model = isl_dim_drop(model, isl_dim_out,
 236                                         0, isl_dim_size(model, isl_dim_out));
 237                 exp = isl_parameter_alignment_reordering(pw->dim, model);
 238                 exp = isl_reordering_extend_dim(exp, FN(PW,get_dim)(pw));
 239                 pw = FN(PW,realign)(pw, exp);
 240         }
 241
 242         isl_dim_free(model);
 243         return pw;
 244 error:
 245         isl_dim_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_dim_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_dim_has_named_params(pw1->dim) ||
 262             !isl_dim_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_dim)(pw2));
 266         pw2 = FN(PW,align_params)(pw2, FN(PW,get_dim)(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_dim_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_dim_has_named_params(pw->dim) ||
 286             !isl_dim_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_dim(set));
 290         set = isl_set_align_params(set, FN(PW,get_dim)(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_dim_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_dim_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_)(isl_dim_copy(pw1->dim), pw1->type, n);
 330 #else
 331         res = FN(PW,alloc_)(isl_dim_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 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
 381         __isl_take PW *pw2)
 382 {
 383         int i;
 384         isl_ctx *ctx;
 385         PW *res;
 386
 387         if (!pw1 || !pw2)
 388                 goto error;
 389
 390         ctx = isl_dim_get_ctx(pw1->dim);
 391 #ifdef HAS_TYPE
 392         if (pw1->type != pw2->type)
 393                 isl_die(ctx, isl_error_invalid,
 394                         "fold types don't match", goto error);
 395 #endif
 396         isl_assert(ctx, isl_dim_equal(pw1->dim, pw2->dim), goto error);
 397
 398         if (FN(PW,IS_ZERO)(pw1)) {
 399                 FN(PW,free)(pw1);
 400                 return pw2;
 401         }
 402
 403         if (FN(PW,IS_ZERO)(pw2)) {
 404                 FN(PW,free)(pw2);
 405                 return pw1;
 406         }
 407
 408 #ifdef HAS_TYPE
 409         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->type, pw1->n + pw2->n);
 410 #else
 411         res = FN(PW,alloc_)(isl_dim_copy(pw1->dim), pw1->n + pw2->n);
 412 #endif
 413
 414         for (i = 0; i < pw1->n; ++i)
 415                 res = FN(PW,add_piece)(res,
 416                                 isl_set_copy(pw1->p[i].set),
 417                                 FN(EL,copy)(pw1->p[i].FIELD));
 418
 419         for (i = 0; i < pw2->n; ++i)
 420                 res = FN(PW,add_piece)(res,
 421                                 isl_set_copy(pw2->p[i].set),
 422                                 FN(EL,copy)(pw2->p[i].FIELD));
 423
 424         FN(PW,free)(pw1);
 425         FN(PW,free)(pw2);
 426
 427         return res;
 428 error:
 429         FN(PW,free)(pw1);
 430         FN(PW,free)(pw2);
 431         return NULL;
 432 }
 433
 434 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
 435 {
 436         return align_params_pw_pw_and(pw1, pw2, &FN(PW,add_disjoint_aligned));
 437 }
 438
 439 #ifndef NO_NEG
 440 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
 441 {
 442         int i;
 443
 444         if (!pw)
 445                 return NULL;
 446
 447         if (FN(PW,IS_ZERO)(pw))
 448                 return pw;
 449
 450         pw = FN(PW,cow)(pw);
 451         if (!pw)
 452                 return NULL;
 453
 454         for (i = 0; i < pw->n; ++i) {
 455                 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
 456                 if (!pw->p[i].FIELD)
 457                         return FN(PW,free)(pw);
 458         }
 459
 460         return pw;
 461 }
 462
 463 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
 464 {
 465         return FN(PW,add)(pw1, FN(PW,neg)(pw2));
 466 }
 467 #endif
 468
 469 #ifndef NO_EVAL
 470 __isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw,
 471         __isl_take isl_point *pnt)
 472 {
 473         int i;
 474         int found = 0;
 475         isl_ctx *ctx;
 476         isl_dim *pnt_dim = NULL;
 477         isl_qpolynomial *qp;
 478
 479         if (!pw || !pnt)
 480                 goto error;
 481         ctx = isl_point_get_ctx(pnt);
 482         pnt_dim = isl_point_get_dim(pnt);
 483         isl_assert(ctx, isl_dim_equal(pnt_dim, pw->dim), goto error);
 484
 485         for (i = 0; i < pw->n; ++i) {
 486                 found = isl_set_contains_point(pw->p[i].set, pnt);
 487                 if (found < 0)
 488                         goto error;
 489                 if (found)
 490                         break;
 491         }
 492         if (found)
 493                 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
 494                                             isl_point_copy(pnt));
 495         else
 496                 qp = isl_qpolynomial_zero(isl_dim_copy(pw->dim));
 497         FN(PW,free)(pw);
 498         isl_dim_free(pnt_dim);
 499         isl_point_free(pnt);
 500         return qp;
 501 error:
 502         FN(PW,free)(pw);
 503         isl_dim_free(pnt_dim);
 504         isl_point_free(pnt);
 505         return NULL;
 506 }
 507 #endif
 508
 509 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
 510 {
 511         int i;
 512         isl_set *dom;
 513
 514         if (!pw)
 515                 return NULL;
 516
 517         dom = isl_set_empty(isl_dim_copy(pw->dim));
 518         for (i = 0; i < pw->n; ++i)
 519                 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
 520
 521         FN(PW,free)(pw);
 522
 523         return dom;
 524 }
 525
 526 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
 527         __isl_take isl_set *set)
 528 {
 529         int i;
 530
 531         if (!pw || !set)
 532                 goto error;
 533
 534         if (pw->n == 0) {
 535                 isl_set_free(set);
 536                 return pw;
 537         }
 538
 539         pw = FN(PW,cow)(pw);
 540         if (!pw)
 541                 goto error;
 542
 543         for (i = pw->n - 1; i >= 0; --i) {
 544                 isl_basic_set *aff;
 545                 pw->p[i].set = isl_set_intersect(pw->p[i].set, isl_set_copy(set));
 546                 if (!pw->p[i].set)
 547                         goto error;
 548                 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
 549                 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD,
 550                                                                 aff);
 551                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 552                         isl_set_free(pw->p[i].set);
 553                         FN(EL,free)(pw->p[i].FIELD);
 554                         if (i != pw->n - 1)
 555                                 pw->p[i] = pw->p[pw->n - 1];
 556                         pw->n--;
 557                 }
 558         }
 559
 560         isl_set_free(set);
 561         return pw;
 562 error:
 563         isl_set_free(set);
 564         FN(PW,free)(pw);
 565         return NULL;
 566 }
 567
 568 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
 569         __isl_take isl_set *context)
 570 {
 571         return align_params_pw_set_and(pw, context,
 572                                         &FN(PW,intersect_domain_aligned));
 573 }
 574
 575 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
 576         __isl_take isl_set *context)
 577 {
 578         int i;
 579         isl_basic_set *hull = NULL;
 580
 581         if (!pw || !context)
 582                 goto error;
 583
 584         if (pw->n == 0) {
 585                 isl_set_free(context);
 586                 return pw;
 587         }
 588
 589         if (!isl_dim_match(pw->dim, isl_dim_param,
 590                                 context->dim, isl_dim_param)) {
 591                 pw = FN(PW,align_params)(pw, isl_set_get_dim(context));
 592                 context = isl_set_align_params(context, FN(PW,get_dim)(pw));
 593         }
 594
 595         context = isl_set_compute_divs(context);
 596         hull = isl_set_simple_hull(isl_set_copy(context));
 597
 598         pw = FN(PW,cow)(pw);
 599         if (!pw)
 600                 goto error;
 601
 602         for (i = pw->n - 1; i >= 0; --i) {
 603                 pw->p[i].set = isl_set_intersect(pw->p[i].set,
 604                                                  isl_set_copy(context));
 605                 if (!pw->p[i].set)
 606                         goto error;
 607                 pw->p[i].FIELD = FN(EL,gist)(pw->p[i].FIELD,
 608                                              isl_set_copy(pw->p[i].set));
 609                 pw->p[i].set = isl_set_gist_basic_set(pw->p[i].set,
 610                                                 isl_basic_set_copy(hull));
 611                 if (!pw->p[i].set)
 612                         goto error;
 613                 if (isl_set_plain_is_empty(pw->p[i].set)) {
 614                         isl_set_free(pw->p[i].set);
 615                         FN(EL,free)(pw->p[i].FIELD);
 616                         if (i != pw->n - 1)
 617                                 pw->p[i] = pw->p[pw->n - 1];
 618                         pw->n--;
 619                 }
 620         }
 621
 622         isl_basic_set_free(hull);
 623         isl_set_free(context);
 624
 625         return pw;
 626 error:
 627         FN(PW,free)(pw);
 628         isl_basic_set_free(hull);
 629         isl_set_free(context);
 630         return NULL;
 631 }
 632
 633 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
 634 {
 635         return align_params_pw_set_and(pw, context, &FN(PW,gist_aligned));
 636 }
 637
 638 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
 639 {
 640         int i, j;
 641
 642         if (!pw)
 643                 return NULL;
 644         if (pw->n == 0)
 645                 return pw;
 646
 647         for (i = pw->n - 1; i >= 0; --i) {
 648                 for (j = i - 1; j >= 0; --j) {
 649                         if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
 650                                                         pw->p[j].FIELD))
 651                                 continue;
 652                         pw->p[j].set = isl_set_union(pw->p[j].set,
 653                                                         pw->p[i].set);
 654                         FN(EL,free)(pw->p[i].FIELD);
 655                         if (i != pw->n - 1)
 656                                 pw->p[i] = pw->p[pw->n - 1];
 657                         pw->n--;
 658                         break;
 659                 }
 660                 if (j >= 0)
 661                         continue;
 662                 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
 663                 if (!pw->p[i].set)
 664                         goto error;
 665         }
 666
 667         return pw;
 668 error:
 669         FN(PW,free)(pw);
 670         return NULL;
 671 }
 672
 673 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
 674 {
 675         return pw ? isl_dim_get_ctx(pw->dim) : NULL;
 676 }
 677
 678 #ifndef NO_INVOLVES_DIMS
 679 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
 680         unsigned first, unsigned n)
 681 {
 682         int i;
 683
 684         if (!pw)
 685                 return -1;
 686         if (pw->n == 0 || n == 0)
 687                 return 0;
 688         for (i = 0; i < pw->n; ++i) {
 689                 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
 690                                                         type, first, n);
 691                 if (involves < 0 || involves)
 692                         return involves;
 693                 involves = isl_set_involves_dims(pw->p[i].set, type, first, n);
 694                 if (involves < 0 || involves)
 695                         return involves;
 696         }
 697         return 0;
 698 }
 699 #endif
 700
 701 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
 702         enum isl_dim_type type, unsigned pos, const char *s)
 703 {
 704         int i;
 705
 706         pw = FN(PW,cow)(pw);
 707         if (!pw)
 708                 return NULL;
 709
 710         pw->dim = isl_dim_set_name(pw->dim, type, pos, s);
 711         if (!pw->dim)
 712                 goto error;
 713
 714         for (i = 0; i < pw->n; ++i) {
 715                 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set, type, pos, s);
 716                 if (!pw->p[i].set)
 717                         goto error;
 718                 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
 719                 if (!pw->p[i].FIELD)
 720                         goto error;
 721         }
 722
 723         return pw;
 724 error:
 725         FN(PW,free)(pw);
 726         return NULL;
 727 }
 728
 729 #ifndef NO_DROP_DIMS
 730 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
 731         enum isl_dim_type type, unsigned first, unsigned n)
 732 {
 733         int i;
 734
 735         if (!pw)
 736                 return NULL;
 737         if (n == 0 && !isl_dim_get_tuple_name(pw->dim, type))
 738                 return pw;
 739
 740         pw = FN(PW,cow)(pw);
 741         if (!pw)
 742                 return NULL;
 743         pw->dim = isl_dim_drop(pw->dim, type, first, n);
 744         if (!pw->dim)
 745                 goto error;
 746         for (i = 0; i < pw->n; ++i) {
 747                 pw->p[i].set = isl_set_drop(pw->p[i].set, type, first, n);
 748                 if (!pw->p[i].set)
 749                         goto error;
 750                 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
 751                 if (!pw->p[i].FIELD)
 752                         goto error;
 753         }
 754
 755         return pw;
 756 error:
 757         FN(PW,free)(pw);
 758         return NULL;
 759 }
 760 #endif
 761
 762 #ifndef NO_INSERT_DIMS
 763 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
 764         unsigned first, unsigned n)
 765 {
 766         int i;
 767
 768         if (!pw)
 769                 return NULL;
 770         if (n == 0 && !isl_dim_is_named_or_nested(pw->dim, type))
 771                 return pw;
 772
 773         pw = FN(PW,cow)(pw);
 774         if (!pw)
 775                 return NULL;
 776
 777         pw->dim = isl_dim_insert(pw->dim, type, first, n);
 778         if (!pw->dim)
 779                 goto error;
 780
 781         for (i = 0; i < pw->n; ++i) {
 782                 pw->p[i].set = isl_set_insert(pw->p[i].set, type, first, n);
 783                 if (!pw->p[i].set)
 784                         goto error;
 785                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 786                                                                 type, first, n);
 787                 if (!pw->p[i].FIELD)
 788                         goto error;
 789         }
 790
 791         return pw;
 792 error:
 793         FN(PW,free)(pw);
 794         return NULL;
 795 }
 796 #endif
 797
 798 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 799         enum isl_dim_type type, unsigned pos, isl_int v)
 800 {
 801         int i;
 802
 803         if (!pw)
 804                 return NULL;
 805
 806         pw = FN(PW,cow)(pw);
 807         if (!pw)
 808                 return NULL;
 809         for (i = 0; i < pw->n; ++i) {
 810                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 811                 if (!pw->p[i].set)
 812                         goto error;
 813         }
 814
 815         return pw;
 816 error:
 817         FN(PW,free)(pw);
 818         return NULL;
 819 }
 820
 821 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 822 {
 823         return pw ? isl_dim_size(pw->dim, type) : 0;
 824 }
 825
 826 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 827         enum isl_dim_type type, unsigned first, unsigned n)
 828 {
 829         int i;
 830
 831         if (!pw)
 832                 return NULL;
 833         if (n == 0)
 834                 return pw;
 835
 836         pw = FN(PW,cow)(pw);
 837         if (!pw)
 838                 return NULL;
 839         if (!pw->dim)
 840                 goto error;
 841         for (i = 0; i < pw->n; ++i) {
 842                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 843                 if (!pw->p[i].set)
 844                         goto error;
 845         }
 846
 847         return pw;
 848 error:
 849         FN(PW,free)(pw);
 850         return NULL;
 851 }
 852
 853 #ifndef NO_OPT
 854 /* Compute the maximal value attained by the piecewise quasipolynomial
 855  * on its domain or zero if the domain is empty.
 856  * In the worst case, the domain is scanned completely,
 857  * so the domain is assumed to be bounded.
 858  */
 859 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 860 {
 861         int i;
 862         isl_qpolynomial *opt;
 863
 864         if (!pw)
 865                 return NULL;
 866
 867         if (pw->n == 0) {
 868                 isl_dim *dim = isl_dim_copy(pw->dim);
 869                 FN(PW,free)(pw);
 870                 return isl_qpolynomial_zero(dim);
 871         }
 872
 873         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
 874                                         isl_set_copy(pw->p[0].set), max);
 875         for (i = 1; i < pw->n; ++i) {
 876                 isl_qpolynomial *opt_i;
 877                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
 878                                                 isl_set_copy(pw->p[i].set), max);
 879                 if (max)
 880                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 881                 else
 882                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 883         }
 884
 885         FN(PW,free)(pw);
 886         return opt;
 887 }
 888
 889 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
 890 {
 891         return FN(PW,opt)(pw, 1);
 892 }
 893
 894 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
 895 {
 896         return FN(PW,opt)(pw, 0);
 897 }
 898 #endif
 899
 900 __isl_give isl_dim *FN(PW,get_dim)(__isl_keep PW *pw)
 901 {
 902         return pw ? isl_dim_copy(pw->dim) : NULL;
 903 }
 904
 905 #ifndef NO_RESET_DIM
 906 __isl_give PW *FN(PW,reset_dim)(__isl_take PW *pw, __isl_take isl_dim *dim)
 907 {
 908         int i;
 909
 910         pw = FN(PW,cow)(pw);
 911         if (!pw || !dim)
 912                 goto error;
 913
 914         for (i = 0; i < pw->n; ++i) {
 915                 pw->p[i].set = isl_set_reset_dim(pw->p[i].set,
 916                                                  isl_dim_copy(dim));
 917                 if (!pw->p[i].set)
 918                         goto error;
 919                 pw->p[i].FIELD = FN(EL,reset_dim)(pw->p[i].FIELD,
 920                                                   isl_dim_copy(dim));
 921                 if (!pw->p[i].FIELD)
 922                         goto error;
 923         }
 924         isl_dim_free(pw->dim);
 925         pw->dim = dim;
 926
 927         return pw;
 928 error:
 929         isl_dim_free(dim);
 930         FN(PW,free)(pw);
 931         return NULL;
 932 }
 933 #endif
 934
 935 int FN(PW,has_equal_dim)(__isl_keep PW *pw1, __isl_keep PW *pw2)
 936 {
 937         if (!pw1 || !pw2)
 938                 return -1;
 939
 940         return isl_dim_equal(pw1->dim, pw2->dim);
 941 }
 942
 943 #ifndef NO_MORPH
 944 __isl_give PW *FN(PW,morph)(__isl_take PW *pw, __isl_take isl_morph *morph)
 945 {
 946         int i;
 947         isl_ctx *ctx;
 948
 949         if (!pw || !morph)
 950                 goto error;
 951
 952         ctx = isl_dim_get_ctx(pw->dim);
 953         isl_assert(ctx, isl_dim_equal(pw->dim, morph->dom->dim),
 954                 goto error);
 955
 956         pw = FN(PW,cow)(pw);
 957         if (!pw)
 958                 goto error;
 959         isl_dim_free(pw->dim);
 960         pw->dim = isl_dim_copy(morph->ran->dim);
 961         if (!pw->dim)
 962                 goto error;
 963
 964         for (i = 0; i < pw->n; ++i) {
 965                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
 966                 if (!pw->p[i].set)
 967                         goto error;
 968                 pw->p[i].FIELD = FN(EL,morph)(pw->p[i].FIELD,
 969                                                 isl_morph_copy(morph));
 970                 if (!pw->p[i].FIELD)
 971                         goto error;
 972         }
 973
 974         isl_morph_free(morph);
 975
 976         return pw;
 977 error:
 978         FN(PW,free)(pw);
 979         isl_morph_free(morph);
 980         return NULL;
 981 }
 982 #endif
 983
 984 int FN(PW,foreach_piece)(__isl_keep PW *pw,
 985         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
 986         void *user)
 987 {
 988         int i;
 989
 990         if (!pw)
 991                 return -1;
 992
 993         for (i = 0; i < pw->n; ++i)
 994                 if (fn(isl_set_copy(pw->p[i].set),
 995                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
 996                         return -1;
 997
 998         return 0;
 999 }
1000
1001 #ifndef NO_LIFT
1002 static int any_divs(__isl_keep isl_set *set)
1003 {
1004         int i;
1005
1006         if (!set)
1007                 return -1;
1008
1009         for (i = 0; i < set->n; ++i)
1010                 if (set->p[i]->n_div > 0)
1011                         return 1;
1012
1013         return 0;
1014 }
1015
1016 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1017         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1018                     void *user), void *user)
1019 {
1020         int i;
1021
1022         if (!set || !el)
1023                 goto error;
1024
1025         for (i = 0; i < set->n; ++i) {
1026                 isl_set *lift;
1027                 EL *copy;
1028
1029                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1030                 lift = isl_set_lift(lift);
1031
1032                 copy = FN(EL,copy)(el);
1033                 copy = FN(EL,lift)(copy, isl_set_get_dim(lift));
1034
1035                 if (fn(lift, copy, user) < 0)
1036                         goto error;
1037         }
1038
1039         isl_set_free(set);
1040         FN(EL,free)(el);
1041
1042         return 0;
1043 error:
1044         isl_set_free(set);
1045         FN(EL,free)(el);
1046         return -1;
1047 }
1048
1049 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1050         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1051                     void *user), void *user)
1052 {
1053         int i;
1054
1055         if (!pw)
1056                 return -1;
1057
1058         for (i = 0; i < pw->n; ++i) {
1059                 isl_set *set;
1060                 EL *el;
1061
1062                 set = isl_set_copy(pw->p[i].set);
1063                 el = FN(EL,copy)(pw->p[i].FIELD);
1064                 if (!any_divs(set)) {
1065                         if (fn(set, el, user) < 0)
1066                                 return -1;
1067                         continue;
1068                 }
1069                 if (foreach_lifted_subset(set, el, fn, user) < 0)
1070                         return -1;
1071         }
1072
1073         return 0;
1074 }
1075 #endif
1076
1077 #ifndef NO_MOVE_DIMS
1078 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1079         enum isl_dim_type dst_type, unsigned dst_pos,
1080         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1081 {
1082         int i;
1083
1084         pw = FN(PW,cow)(pw);
1085         if (!pw)
1086                 return NULL;
1087
1088         pw->dim = isl_dim_move(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1089         if (!pw->dim)
1090                 goto error;
1091
1092         for (i = 0; i < pw->n; ++i) {
1093                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1094                                                 dst_type, dst_pos,
1095                                                 src_type, src_pos, n);
1096                 if (!pw->p[i].set)
1097                         goto error;
1098                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1099                                         dst_type, dst_pos, src_type, src_pos, n);
1100                 if (!pw->p[i].FIELD)
1101                         goto error;
1102         }
1103
1104         return pw;
1105 error:
1106         FN(PW,free)(pw);
1107         return NULL;
1108 }
1109 #endif
1110
1111 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1112 {
1113         int i;
1114
1115         if (isl_int_is_one(v))
1116                 return pw;
1117         if (pw && isl_int_is_zero(v)) {
1118                 PW *zero;
1119                 isl_dim *dim = FN(PW,get_dim)(pw);
1120 #ifdef HAS_TYPE
1121                 zero = FN(PW,ZERO)(dim, pw->type);
1122 #else
1123                 zero = FN(PW,ZERO)(dim);
1124 #endif
1125                 FN(PW,free)(pw);
1126                 return zero;
1127         }
1128         pw = FN(PW,cow)(pw);
1129         if (!pw)
1130                 return NULL;
1131         if (pw->n == 0)
1132                 return pw;
1133
1134 #ifdef HAS_TYPE
1135         if (isl_int_is_neg(v))
1136                 pw->type = isl_fold_type_negate(pw->type);
1137 #endif
1138         for (i = 0; i < pw->n; ++i) {
1139                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1140                 if (!pw->p[i].FIELD)
1141                         goto error;
1142         }
1143
1144         return pw;
1145 error:
1146         FN(PW,free)(pw);
1147         return NULL;
1148 }
1149
1150 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1151 {
1152         return FN(PW,mul_isl_int)(pw, v);
1153 }