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_space *dim,
   8         enum isl_fold type, int n)
   9 #else
  10 static __isl_give PW *FN(PW,alloc_)(__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_)(dim, type, 0);
  42 }
  43 #else
  44 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *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_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_)(isl_set_get_space(set), type, 1);
 103 #else
 104         pw = FN(PW,alloc_)(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_)(isl_space_copy(pw->dim), pw->type, pw->n);
 124 #else
 125         dup = FN(PW,alloc_)(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_)(isl_space_copy(pw1->dim), pw1->type, n);
 330 #else
 331         res = FN(PW,alloc_)(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 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_space_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_space_is_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_space_copy(pw1->dim), pw1->type, pw1->n + pw2->n);
 410 #else
 411         res = FN(PW,alloc_)(isl_space_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_space *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_space(pnt);
 483         isl_assert(ctx, isl_space_is_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_space_copy(pw->dim));
 497         FN(PW,free)(pw);
 498         isl_space_free(pnt_dim);
 499         isl_point_free(pnt);
 500         return qp;
 501 error:
 502         FN(PW,free)(pw);
 503         isl_space_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_space_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_space_match(pw->dim, isl_dim_param,
 590                                 context->dim, isl_dim_param)) {
 591                 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
 592                 context = isl_set_align_params(context, FN(PW,get_space)(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_space_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_space_set_dim_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_space_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_space_drop_dims(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_space_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_space_insert_dims(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_dims(pw->p[i].set,
 783                                                                 type, first, n);
 784                 if (!pw->p[i].set)
 785                         goto error;
 786                 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
 787                                                                 type, first, n);
 788                 if (!pw->p[i].FIELD)
 789                         goto error;
 790         }
 791
 792         return pw;
 793 error:
 794         FN(PW,free)(pw);
 795         return NULL;
 796 }
 797 #endif
 798
 799 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
 800         enum isl_dim_type type, unsigned pos, isl_int v)
 801 {
 802         int i;
 803
 804         if (!pw)
 805                 return NULL;
 806
 807         pw = FN(PW,cow)(pw);
 808         if (!pw)
 809                 return NULL;
 810         for (i = 0; i < pw->n; ++i) {
 811                 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
 812                 if (!pw->p[i].set)
 813                         goto error;
 814         }
 815
 816         return pw;
 817 error:
 818         FN(PW,free)(pw);
 819         return NULL;
 820 }
 821
 822 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
 823 {
 824         return pw ? isl_space_dim(pw->dim, type) : 0;
 825 }
 826
 827 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
 828         enum isl_dim_type type, unsigned first, unsigned n)
 829 {
 830         int i;
 831
 832         if (!pw)
 833                 return NULL;
 834         if (n == 0)
 835                 return pw;
 836
 837         pw = FN(PW,cow)(pw);
 838         if (!pw)
 839                 return NULL;
 840         if (!pw->dim)
 841                 goto error;
 842         for (i = 0; i < pw->n; ++i) {
 843                 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
 844                 if (!pw->p[i].set)
 845                         goto error;
 846         }
 847
 848         return pw;
 849 error:
 850         FN(PW,free)(pw);
 851         return NULL;
 852 }
 853
 854 #ifndef NO_OPT
 855 /* Compute the maximal value attained by the piecewise quasipolynomial
 856  * on its domain or zero if the domain is empty.
 857  * In the worst case, the domain is scanned completely,
 858  * so the domain is assumed to be bounded.
 859  */
 860 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
 861 {
 862         int i;
 863         isl_qpolynomial *opt;
 864
 865         if (!pw)
 866                 return NULL;
 867
 868         if (pw->n == 0) {
 869                 isl_space *dim = isl_space_copy(pw->dim);
 870                 FN(PW,free)(pw);
 871                 return isl_qpolynomial_zero(dim);
 872         }
 873
 874         opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
 875                                         isl_set_copy(pw->p[0].set), max);
 876         for (i = 1; i < pw->n; ++i) {
 877                 isl_qpolynomial *opt_i;
 878                 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
 879                                                 isl_set_copy(pw->p[i].set), max);
 880                 if (max)
 881                         opt = isl_qpolynomial_max_cst(opt, opt_i);
 882                 else
 883                         opt = isl_qpolynomial_min_cst(opt, opt_i);
 884         }
 885
 886         FN(PW,free)(pw);
 887         return opt;
 888 }
 889
 890 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
 891 {
 892         return FN(PW,opt)(pw, 1);
 893 }
 894
 895 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
 896 {
 897         return FN(PW,opt)(pw, 0);
 898 }
 899 #endif
 900
 901 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
 902 {
 903         return pw ? isl_space_copy(pw->dim) : NULL;
 904 }
 905
 906 #ifndef NO_RESET_DIM
 907 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
 908 {
 909         int i;
 910
 911         pw = FN(PW,cow)(pw);
 912         if (!pw || !dim)
 913                 goto error;
 914
 915         for (i = 0; i < pw->n; ++i) {
 916                 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
 917                                                  isl_space_copy(dim));
 918                 if (!pw->p[i].set)
 919                         goto error;
 920                 pw->p[i].FIELD = FN(EL,reset_space)(pw->p[i].FIELD,
 921                                                   isl_space_copy(dim));
 922                 if (!pw->p[i].FIELD)
 923                         goto error;
 924         }
 925         isl_space_free(pw->dim);
 926         pw->dim = dim;
 927
 928         return pw;
 929 error:
 930         isl_space_free(dim);
 931         FN(PW,free)(pw);
 932         return NULL;
 933 }
 934 #endif
 935
 936 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
 937 {
 938         if (!pw1 || !pw2)
 939                 return -1;
 940
 941         return isl_space_is_equal(pw1->dim, pw2->dim);
 942 }
 943
 944 #ifndef NO_MORPH
 945 __isl_give PW *FN(PW,morph)(__isl_take PW *pw, __isl_take isl_morph *morph)
 946 {
 947         int i;
 948         isl_ctx *ctx;
 949
 950         if (!pw || !morph)
 951                 goto error;
 952
 953         ctx = isl_space_get_ctx(pw->dim);
 954         isl_assert(ctx, isl_space_is_equal(pw->dim, morph->dom->dim),
 955                 goto error);
 956
 957         pw = FN(PW,cow)(pw);
 958         if (!pw)
 959                 goto error;
 960         isl_space_free(pw->dim);
 961         pw->dim = isl_space_copy(morph->ran->dim);
 962         if (!pw->dim)
 963                 goto error;
 964
 965         for (i = 0; i < pw->n; ++i) {
 966                 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
 967                 if (!pw->p[i].set)
 968                         goto error;
 969                 pw->p[i].FIELD = FN(EL,morph)(pw->p[i].FIELD,
 970                                                 isl_morph_copy(morph));
 971                 if (!pw->p[i].FIELD)
 972                         goto error;
 973         }
 974
 975         isl_morph_free(morph);
 976
 977         return pw;
 978 error:
 979         FN(PW,free)(pw);
 980         isl_morph_free(morph);
 981         return NULL;
 982 }
 983 #endif
 984
 985 int FN(PW,foreach_piece)(__isl_keep PW *pw,
 986         int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
 987         void *user)
 988 {
 989         int i;
 990
 991         if (!pw)
 992                 return -1;
 993
 994         for (i = 0; i < pw->n; ++i)
 995                 if (fn(isl_set_copy(pw->p[i].set),
 996                                 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
 997                         return -1;
 998
 999         return 0;
1000 }
1001
1002 #ifndef NO_LIFT
1003 static int any_divs(__isl_keep isl_set *set)
1004 {
1005         int i;
1006
1007         if (!set)
1008                 return -1;
1009
1010         for (i = 0; i < set->n; ++i)
1011                 if (set->p[i]->n_div > 0)
1012                         return 1;
1013
1014         return 0;
1015 }
1016
1017 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1018         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1019                     void *user), void *user)
1020 {
1021         int i;
1022
1023         if (!set || !el)
1024                 goto error;
1025
1026         for (i = 0; i < set->n; ++i) {
1027                 isl_set *lift;
1028                 EL *copy;
1029
1030                 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1031                 lift = isl_set_lift(lift);
1032
1033                 copy = FN(EL,copy)(el);
1034                 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1035
1036                 if (fn(lift, copy, user) < 0)
1037                         goto error;
1038         }
1039
1040         isl_set_free(set);
1041         FN(EL,free)(el);
1042
1043         return 0;
1044 error:
1045         isl_set_free(set);
1046         FN(EL,free)(el);
1047         return -1;
1048 }
1049
1050 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1051         int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1052                     void *user), void *user)
1053 {
1054         int i;
1055
1056         if (!pw)
1057                 return -1;
1058
1059         for (i = 0; i < pw->n; ++i) {
1060                 isl_set *set;
1061                 EL *el;
1062
1063                 set = isl_set_copy(pw->p[i].set);
1064                 el = FN(EL,copy)(pw->p[i].FIELD);
1065                 if (!any_divs(set)) {
1066                         if (fn(set, el, user) < 0)
1067                                 return -1;
1068                         continue;
1069                 }
1070                 if (foreach_lifted_subset(set, el, fn, user) < 0)
1071                         return -1;
1072         }
1073
1074         return 0;
1075 }
1076 #endif
1077
1078 #ifndef NO_MOVE_DIMS
1079 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1080         enum isl_dim_type dst_type, unsigned dst_pos,
1081         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1082 {
1083         int i;
1084
1085         pw = FN(PW,cow)(pw);
1086         if (!pw)
1087                 return NULL;
1088
1089         pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1090         if (!pw->dim)
1091                 goto error;
1092
1093         for (i = 0; i < pw->n; ++i) {
1094                 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1095                                                 dst_type, dst_pos,
1096                                                 src_type, src_pos, n);
1097                 if (!pw->p[i].set)
1098                         goto error;
1099                 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1100                                         dst_type, dst_pos, src_type, src_pos, n);
1101                 if (!pw->p[i].FIELD)
1102                         goto error;
1103         }
1104
1105         return pw;
1106 error:
1107         FN(PW,free)(pw);
1108         return NULL;
1109 }
1110 #endif
1111
1112 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1113 {
1114         int i;
1115
1116         if (isl_int_is_one(v))
1117                 return pw;
1118         if (pw && isl_int_is_zero(v)) {
1119                 PW *zero;
1120                 isl_space *dim = FN(PW,get_space)(pw);
1121 #ifdef HAS_TYPE
1122                 zero = FN(PW,ZERO)(dim, pw->type);
1123 #else
1124                 zero = FN(PW,ZERO)(dim);
1125 #endif
1126                 FN(PW,free)(pw);
1127                 return zero;
1128         }
1129         pw = FN(PW,cow)(pw);
1130         if (!pw)
1131                 return NULL;
1132         if (pw->n == 0)
1133                 return pw;
1134
1135 #ifdef HAS_TYPE
1136         if (isl_int_is_neg(v))
1137                 pw->type = isl_fold_type_negate(pw->type);
1138 #endif
1139         for (i = 0; i < pw->n; ++i) {
1140                 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1141                 if (!pw->p[i].FIELD)
1142                         goto error;
1143         }
1144
1145         return pw;
1146 error:
1147         FN(PW,free)(pw);
1148         return NULL;
1149 }
1150
1151 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1152 {
1153         return FN(PW,mul_isl_int)(pw, v);
1154 }