isl_union_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  14 #define S(TYPE,NAME) xS(TYPE,NAME)
  15
  16 struct UNION {
  17         int ref;
  18 #ifdef HAS_TYPE
  19         enum isl_fold type;
  20 #endif
  21         isl_space *dim;
  22
  23         struct isl_hash_table   table;
  24 };
  25
  26 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
  27
  28 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
  29 {
  30         return u ? u->dim->ctx : NULL;
  31 }
  32
  33 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
  34 {
  35         if (!u)
  36                 return NULL;
  37         return isl_space_copy(u->dim);
  38 }
  39
  40 #ifdef HAS_TYPE
  41 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
  42         enum isl_fold type, int size)
  43 #else
  44 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
  45 #endif
  46 {
  47         UNION *u;
  48
  49         dim = isl_space_params(dim);
  50         if (!dim)
  51                 return NULL;
  52
  53         u = isl_calloc_type(dim->ctx, UNION);
  54         if (!u)
  55                 goto error;
  56
  57         u->ref = 1;
  58 #ifdef HAS_TYPE
  59         u->type = type;
  60 #endif
  61         u->dim = dim;
  62         if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
  63                 return FN(UNION,free)(u);
  64
  65         return u;
  66 error:
  67         isl_space_free(dim);
  68         return NULL;
  69 }
  70
  71 #ifdef HAS_TYPE
  72 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
  73 {
  74         return FN(UNION,alloc)(dim, type, 16);
  75 }
  76 #else
  77 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
  78 {
  79         return FN(UNION,alloc)(dim, 16);
  80 }
  81 #endif
  82
  83 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
  84 {
  85         if (!u)
  86                 return NULL;
  87
  88         u->ref++;
  89         return u;
  90 }
  91
  92 S(UNION,foreach_data)
  93 {
  94         int (*fn)(__isl_take PART *part, void *user);
  95         void *user;
  96 };
  97
  98 static int call_on_copy(void **entry, void *user)
  99 {
 100         PART *part = *entry;
 101         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
 102
 103         return data->fn(FN(PART,copy)(part), data->user);
 104 }
 105
 106 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
 107         int (*fn)(__isl_take PART *part, void *user), void *user)
 108 {
 109         S(UNION,foreach_data) data = { fn, user };
 110
 111         if (!u)
 112                 return -1;
 113
 114         return isl_hash_table_foreach(u->dim->ctx, &u->table,
 115                                       &call_on_copy, &data);
 116 }
 117
 118 static int has_dim(const void *entry, const void *val)
 119 {
 120         PART *part = (PART *)entry;
 121         isl_space *dim = (isl_space *)val;
 122
 123         return isl_space_is_equal(part->dim, dim);
 124 }
 125
 126 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
 127         __isl_take isl_space *dim)
 128 {
 129         uint32_t hash;
 130         struct isl_hash_table_entry *entry;
 131
 132         if (!u || !dim)
 133                 goto error;
 134
 135         hash = isl_space_get_hash(dim);
 136         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 137                                     &has_dim, dim, 0);
 138         if (!entry)
 139 #ifdef HAS_TYPE
 140                 return FN(PART,ZERO)(dim, u->type);
 141 #else
 142                 return FN(PART,ZERO)(dim);
 143 #endif
 144         isl_space_free(dim);
 145         return FN(PART,copy)(entry->data);
 146 error:
 147         isl_space_free(dim);
 148         return NULL;
 149 }
 150
 151 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 152         __isl_take PART *part)
 153 {
 154         uint32_t hash;
 155         struct isl_hash_table_entry *entry;
 156
 157         if (!part)
 158                 goto error;
 159
 160         if (DEFAULT_IS_ZERO && FN(PART,IS_ZERO)(part)) {
 161                 FN(PART,free)(part);
 162                 return u;
 163         }
 164
 165         u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
 166         part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
 167
 168         u = FN(UNION,cow)(u);
 169
 170         if (!u)
 171                 goto error;
 172
 173         hash = isl_space_get_hash(part->dim);
 174         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 175                                     &has_dim, part->dim, 1);
 176         if (!entry)
 177                 goto error;
 178
 179         if (!entry->data)
 180                 entry->data = part;
 181         else {
 182                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
 183                 if (!entry->data)
 184                         goto error;
 185                 FN(PART,free)(part);
 186                 if (DEFAULT_IS_ZERO && FN(PART,IS_ZERO)(entry->data)) {
 187                         FN(PART,free)(entry->data);
 188                         isl_hash_table_remove(u->dim->ctx, &u->table, entry);
 189                 }
 190         }
 191
 192         return u;
 193 error:
 194         FN(PART,free)(part);
 195         FN(UNION,free)(u);
 196         return NULL;
 197 }
 198
 199 static int add_part(__isl_take PART *part, void *user)
 200 {
 201         UNION **u = (UNION **)user;
 202
 203         *u = FN(FN(UNION,add),PARTS)(*u, part);
 204
 205         return 0;
 206 }
 207
 208 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 209 {
 210         UNION *dup;
 211
 212         if (!u)
 213                 return NULL;
 214
 215 #ifdef HAS_TYPE
 216         dup = FN(UNION,ZERO)(isl_space_copy(u->dim), u->type);
 217 #else
 218         dup = FN(UNION,ZERO)(isl_space_copy(u->dim));
 219 #endif
 220         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 221                 goto error;
 222         return dup;
 223 error:
 224         FN(UNION,free)(dup);
 225         return NULL;
 226 }
 227
 228 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 229 {
 230         if (!u)
 231                 return NULL;
 232
 233         if (u->ref == 1)
 234                 return u;
 235         u->ref--;
 236         return FN(UNION,dup)(u);
 237 }
 238
 239 static int free_u_entry(void **entry, void *user)
 240 {
 241         PART *part = *entry;
 242         FN(PART,free)(part);
 243         return 0;
 244 }
 245
 246 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
 247 {
 248         if (!u)
 249                 return NULL;
 250
 251         if (--u->ref > 0)
 252                 return NULL;
 253
 254         isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
 255         isl_hash_table_clear(&u->table);
 256         isl_space_free(u->dim);
 257         free(u);
 258         return NULL;
 259 }
 260
 261 S(UNION,align) {
 262         isl_reordering *exp;
 263         UNION *res;
 264 };
 265
 266 #ifdef ALIGN_DOMAIN
 267 static int align_entry(__isl_take PART *part, void *user)
 268 {
 269         isl_reordering *exp;
 270         S(UNION,align) *data = user;
 271
 272         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 273                                     FN(PART,get_domain_space)(part));
 274
 275         data->res = FN(FN(UNION,add),PARTS)(data->res,
 276                                             FN(PART,realign_domain)(part, exp));
 277
 278         return 0;
 279 }
 280 #else
 281 static int align_entry(__isl_take PART *part, void *user)
 282 {
 283         isl_reordering *exp;
 284         S(UNION,align) *data = user;
 285
 286         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 287                                     FN(PART,get_space)(part));
 288
 289         data->res = FN(FN(UNION,add),PARTS)(data->res,
 290                                             FN(PART,realign)(part, exp));
 291
 292         return 0;
 293 }
 294 #endif
 295
 296 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 297         __isl_take isl_space *model)
 298 {
 299         S(UNION,align) data = { NULL, NULL };
 300
 301         if (!u || !model)
 302                 goto error;
 303
 304         if (isl_space_match(u->dim, isl_dim_param, model, isl_dim_param)) {
 305                 isl_space_free(model);
 306                 return u;
 307         }
 308
 309         model = isl_space_params(model);
 310         data.exp = isl_parameter_alignment_reordering(u->dim, model);
 311         if (!data.exp)
 312                 goto error;
 313
 314 #ifdef HAS_TYPE
 315         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
 316                                                 u->type, u->table.n);
 317 #else
 318         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
 319 #endif
 320         if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
 321                 goto error;
 322
 323         isl_reordering_free(data.exp);
 324         FN(UNION,free)(u);
 325         isl_space_free(model);
 326         return data.res;
 327 error:
 328         isl_reordering_free(data.exp);
 329         FN(UNION,free)(u);
 330         FN(UNION,free)(data.res);
 331         isl_space_free(model);
 332         return NULL;
 333 }
 334
 335 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 336 {
 337         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 338         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 339
 340         u1 = FN(UNION,cow)(u1);
 341
 342         if (!u1 || !u2)
 343                 goto error;
 344
 345         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
 346                 goto error;
 347
 348         FN(UNION,free)(u2);
 349
 350         return u1;
 351 error:
 352         FN(UNION,free)(u1);
 353         FN(UNION,free)(u2);
 354         return NULL;
 355 }
 356
 357 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 358 {
 359         isl_space *dim;
 360         UNION *u;
 361
 362         if (!part)
 363                 return NULL;
 364
 365         dim = FN(PART,get_space)(part);
 366         dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
 367         dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
 368 #ifdef HAS_TYPE
 369         u = FN(UNION,ZERO)(dim, part->type);
 370 #else
 371         u = FN(UNION,ZERO)(dim);
 372 #endif
 373         u = FN(FN(UNION,add),PARTS)(u, part);
 374
 375         return u;
 376 }
 377
 378 S(UNION,match_bin_data) {
 379         UNION *u2;
 380         UNION *res;
 381         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 382 };
 383
 384 /* Check if data->u2 has an element living in the same space as *entry.
 385  * If so, call data->fn on the two elements and add the result to
 386  * data->res.
 387  */
 388 static int match_bin_entry(void **entry, void *user)
 389 {
 390         S(UNION,match_bin_data) *data = user;
 391         uint32_t hash;
 392         struct isl_hash_table_entry *entry2;
 393         isl_space *space;
 394         PART *part = *entry;
 395
 396         space = FN(PART,get_space)(part);
 397         hash = isl_space_get_hash(space);
 398         entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
 399                                      hash, &has_dim, space, 0);
 400         isl_space_free(space);
 401         if (!entry2)
 402                 return 0;
 403
 404         part = FN(PART, copy)(part);
 405         part = data->fn(part, FN(PART, copy)(entry2->data));
 406
 407         if (DEFAULT_IS_ZERO) {
 408                 int empty;
 409
 410                 empty = FN(PART,IS_ZERO)(part);
 411                 if (empty < 0) {
 412                         FN(PART,free)(part);
 413                         return -1;
 414                 }
 415                 if (empty) {
 416                         FN(PART,free)(part);
 417                         return 0;
 418                 }
 419         }
 420
 421         data->res = FN(FN(UNION,add),PARTS)(data->res, part);
 422
 423         return 0;
 424 }
 425
 426 /* This function is currently only used from isl_polynomial.c
 427  * and not from isl_fold.c.
 428  */
 429 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 430         __isl_take UNION *u2,
 431         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 432         __attribute__ ((unused));
 433 /* For each pair of elements in "u1" and "u2" living in the same space,
 434  * call "fn" and collect the results.
 435  */
 436 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 437         __isl_take UNION *u2,
 438         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 439 {
 440         S(UNION,match_bin_data) data = { NULL, NULL, fn };
 441
 442         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 443         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 444
 445         if (!u1 || !u2)
 446                 goto error;
 447
 448         data.u2 = u2;
 449 #ifdef HAS_TYPE
 450         data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->type, u1->table.n);
 451 #else
 452         data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->table.n);
 453 #endif
 454         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
 455                                     &match_bin_entry, &data) < 0)
 456                 goto error;
 457
 458         FN(UNION,free)(u1);
 459         FN(UNION,free)(u2);
 460         return data.res;
 461 error:
 462         FN(UNION,free)(u1);
 463         FN(UNION,free)(u2);
 464         FN(UNION,free)(data.res);
 465         return NULL;
 466 }
 467
 468 #ifndef NO_SUB
 469 /* Subtract "u2" from "u1" and return the result.
 470  */
 471 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
 472 {
 473         return match_bin_op(u1, u2, &FN(PART,sub));
 474 }
 475 #endif
 476
 477 S(UNION,any_set_data) {
 478         isl_set *set;
 479         UNION *res;
 480         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 481 };
 482
 483 static int any_set_entry(void **entry, void *user)
 484 {
 485         S(UNION,any_set_data) *data = user;
 486         PW *pw = *entry;
 487
 488         pw = FN(PW,copy)(pw);
 489         pw = data->fn(pw, isl_set_copy(data->set));
 490
 491         if (DEFAULT_IS_ZERO) {
 492                 int empty;
 493
 494                 empty = FN(PW,IS_ZERO)(pw);
 495                 if (empty < 0) {
 496                         FN(PW,free)(pw);
 497                         return -1;
 498                 }
 499                 if (empty) {
 500                         FN(PW,free)(pw);
 501                         return 0;
 502                 }
 503         }
 504
 505         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 506
 507         return 0;
 508 }
 509
 510 /* Update each element of "u" by calling "fn" on the element and "set".
 511  */
 512 static __isl_give UNION *any_set_op(__isl_take UNION *u,
 513         __isl_take isl_set *set,
 514         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 515 {
 516         S(UNION,any_set_data) data = { NULL, NULL, fn };
 517
 518         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 519         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 520
 521         if (!u || !set)
 522                 goto error;
 523
 524         data.set = set;
 525 #ifdef HAS_TYPE
 526         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
 527 #else
 528         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
 529 #endif
 530         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 531                                    &any_set_entry, &data) < 0)
 532                 goto error;
 533
 534         FN(UNION,free)(u);
 535         isl_set_free(set);
 536         return data.res;
 537 error:
 538         FN(UNION,free)(u);
 539         isl_set_free(set);
 540         FN(UNION,free)(data.res);
 541         return NULL;
 542 }
 543
 544 /* Intersect the domain of "u" with the parameter domain "context".
 545  */
 546 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 547         __isl_take isl_set *set)
 548 {
 549         return any_set_op(u, set, &FN(PW,intersect_params));
 550 }
 551
 552 /* Compute the gist of the domain of "u" with respect to
 553  * the parameter domain "context".
 554  */
 555 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 556         __isl_take isl_set *set)
 557 {
 558         return any_set_op(u, set, &FN(PW,gist_params));
 559 }
 560
 561 S(UNION,match_domain_data) {
 562         isl_union_set *uset;
 563         UNION *res;
 564         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 565 };
 566
 567 static int set_has_dim(const void *entry, const void *val)
 568 {
 569         isl_set *set = (isl_set *)entry;
 570         isl_space *dim = (isl_space *)val;
 571
 572         return isl_space_is_equal(set->dim, dim);
 573 }
 574
 575 /* Find the set in data->uset that live in the same space as the domain
 576  * of *entry, apply data->fn to *entry and this set (if any), and add
 577  * the result to data->res.
 578  */
 579 static int match_domain_entry(void **entry, void *user)
 580 {
 581         S(UNION,match_domain_data) *data = user;
 582         uint32_t hash;
 583         struct isl_hash_table_entry *entry2;
 584         PW *pw = *entry;
 585         isl_space *space;
 586
 587         space = FN(PW,get_domain_space)(pw);
 588         hash = isl_space_get_hash(space);
 589         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 590                                      hash, &set_has_dim, space, 0);
 591         isl_space_free(space);
 592         if (!entry2)
 593                 return 0;
 594
 595         pw = FN(PW,copy)(pw);
 596         pw = data->fn(pw, isl_set_copy(entry2->data));
 597
 598         if (DEFAULT_IS_ZERO) {
 599                 int empty;
 600
 601                 empty = FN(PW,IS_ZERO)(pw);
 602                 if (empty < 0) {
 603                         FN(PW,free)(pw);
 604                         return -1;
 605                 }
 606                 if (empty) {
 607                         FN(PW,free)(pw);
 608                         return 0;
 609                 }
 610         }
 611
 612         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 613
 614         return 0;
 615 }
 616
 617 /* Apply fn to each pair of PW in u and set in uset such that
 618  * the set lives in the same space as the domain of PW
 619  * and collect the results.
 620  */
 621 static __isl_give UNION *match_domain_op(__isl_take UNION *u,
 622         __isl_take isl_union_set *uset,
 623         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 624 {
 625         S(UNION,match_domain_data) data = { NULL, NULL, fn };
 626
 627         u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
 628         uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
 629
 630         if (!u || !uset)
 631                 goto error;
 632
 633         data.uset = uset;
 634 #ifdef HAS_TYPE
 635         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
 636 #else
 637         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
 638 #endif
 639         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 640                                    &match_domain_entry, &data) < 0)
 641                 goto error;
 642
 643         FN(UNION,free)(u);
 644         isl_union_set_free(uset);
 645         return data.res;
 646 error:
 647         FN(UNION,free)(u);
 648         isl_union_set_free(uset);
 649         FN(UNION,free)(data.res);
 650         return NULL;
 651 }
 652
 653 /* Intersect the domain of "u" with "uset".
 654  * If "uset" is a parameters domain, then intersect the parameter
 655  * domain of "u" with this set.
 656  */
 657 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 658         __isl_take isl_union_set *uset)
 659 {
 660         if (isl_union_set_is_params(uset))
 661                 return FN(UNION,intersect_params)(u,
 662                                                 isl_set_from_union_set(uset));
 663         return match_domain_op(u, uset, &FN(PW,intersect_domain));
 664 }
 665
 666 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 667         __isl_take isl_union_set *uset)
 668 {
 669         if (isl_union_set_is_params(uset))
 670                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 671         return match_domain_op(u, uset, &FN(PW,gist));
 672 }
 673
 674 #ifndef NO_EVAL
 675 __isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u,
 676         __isl_take isl_point *pnt)
 677 {
 678         uint32_t hash;
 679         struct isl_hash_table_entry *entry;
 680         isl_space *space;
 681         isl_val *v;
 682
 683         if (!u || !pnt)
 684                 goto error;
 685
 686         space = isl_space_copy(pnt->dim);
 687         space = isl_space_from_domain(space);
 688         space = isl_space_add_dims(space, isl_dim_out, 1);
 689         if (!space)
 690                 goto error;
 691         hash = isl_space_get_hash(space);
 692         entry = isl_hash_table_find(u->dim->ctx, &u->table,
 693                                     hash, &has_dim, space, 0);
 694         isl_space_free(space);
 695         if (!entry) {
 696                 v = isl_val_zero(isl_point_get_ctx(pnt));
 697                 isl_point_free(pnt);
 698         } else {
 699                 v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 700         }
 701         FN(UNION,free)(u);
 702         return v;
 703 error:
 704         FN(UNION,free)(u);
 705         isl_point_free(pnt);
 706         return NULL;
 707 }
 708 #endif
 709
 710 static int coalesce_entry(void **entry, void *user)
 711 {
 712         PW **pw = (PW **)entry;
 713
 714         *pw = FN(PW,coalesce)(*pw);
 715         if (!*pw)
 716                 return -1;
 717
 718         return 0;
 719 }
 720
 721 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 722 {
 723         if (!u)
 724                 return NULL;
 725
 726         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 727                                    &coalesce_entry, NULL) < 0)
 728                 goto error;
 729
 730         return u;
 731 error:
 732         FN(UNION,free)(u);
 733         return NULL;
 734 }
 735
 736 static int domain(__isl_take PART *part, void *user)
 737 {
 738         isl_union_set **uset = (isl_union_set **)user;
 739
 740         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 741
 742         return 0;
 743 }
 744
 745 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 746 {
 747         isl_union_set *uset;
 748
 749         uset = isl_union_set_empty(FN(UNION,get_space)(u));
 750         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 751                 goto error;
 752
 753         FN(UNION,free)(u);
 754
 755         return uset;
 756 error:
 757         isl_union_set_free(uset);
 758         FN(UNION,free)(u);
 759         return NULL;
 760 }
 761
 762 static int mul_isl_int(void **entry, void *user)
 763 {
 764         PW **pw = (PW **)entry;
 765         isl_int *v = user;
 766
 767         *pw = FN(PW,mul_isl_int)(*pw, *v);
 768         if (!*pw)
 769                 return -1;
 770
 771         return 0;
 772 }
 773
 774 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
 775 {
 776         if (isl_int_is_one(v))
 777                 return u;
 778
 779         if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
 780                 UNION *zero;
 781                 isl_space *dim = FN(UNION,get_space)(u);
 782 #ifdef HAS_TYPE
 783                 zero = FN(UNION,ZERO)(dim, u->type);
 784 #else
 785                 zero = FN(UNION,ZERO)(dim);
 786 #endif
 787                 FN(UNION,free)(u);
 788                 return zero;
 789         }
 790
 791         u = FN(UNION,cow)(u);
 792         if (!u)
 793                 return NULL;
 794
 795 #ifdef HAS_TYPE
 796         if (isl_int_is_neg(v))
 797                 u->type = isl_fold_type_negate(u->type);
 798 #endif
 799         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 800                                     &mul_isl_int, &v) < 0)
 801                 goto error;
 802
 803         return u;
 804 error:
 805         FN(UNION,free)(u);
 806         return NULL;
 807 }
 808
 809 /* Multiply *entry by the isl_val "user".
 810  *
 811  * Return 0 on success and -1 on error.
 812  */
 813 static int scale_val(void **entry, void *user)
 814 {
 815         PW **pw = (PW **)entry;
 816         isl_val *v = user;
 817
 818         *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
 819         if (!*pw)
 820                 return -1;
 821
 822         return 0;
 823 }
 824
 825 /* Multiply "u" by "v" and return the result.
 826  */
 827 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
 828         __isl_take isl_val *v)
 829 {
 830         if (!u || !v)
 831                 goto error;
 832         if (isl_val_is_one(v)) {
 833                 isl_val_free(v);
 834                 return u;
 835         }
 836
 837         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
 838                 UNION *zero;
 839                 isl_space *space = FN(UNION,get_space)(u);
 840 #ifdef HAS_TYPE
 841                 zero = FN(UNION,ZERO)(space, u->type);
 842 #else
 843                 zero = FN(UNION,ZERO)(space);
 844 #endif
 845                 FN(UNION,free)(u);
 846                 isl_val_free(v);
 847                 return zero;
 848         }
 849
 850         if (!isl_val_is_rat(v))
 851                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 852                         "expecting rational factor", goto error);
 853
 854         u = FN(UNION,cow)(u);
 855         if (!u)
 856                 return NULL;
 857
 858 #ifdef HAS_TYPE
 859         if (isl_val_is_neg(v))
 860                 u->type = isl_fold_type_negate(u->type);
 861 #endif
 862         if (isl_hash_table_foreach(u->dim->ctx, &u->table, &scale_val, v) < 0)
 863                 goto error;
 864
 865         isl_val_free(v);
 866         return u;
 867 error:
 868         isl_val_free(v);
 869         FN(UNION,free)(u);
 870         return NULL;
 871 }
 872
 873 S(UNION,plain_is_equal_data)
 874 {
 875         UNION *u2;
 876         int is_equal;
 877 };
 878
 879 static int plain_is_equal_entry(void **entry, void *user)
 880 {
 881         S(UNION,plain_is_equal_data) *data = user;
 882         uint32_t hash;
 883         struct isl_hash_table_entry *entry2;
 884         PW *pw = *entry;
 885
 886         hash = isl_space_get_hash(pw->dim);
 887         entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
 888                                      hash, &has_dim, pw->dim, 0);
 889         if (!entry2) {
 890                 data->is_equal = 0;
 891                 return -1;
 892         }
 893
 894         data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
 895         if (data->is_equal < 0 || !data->is_equal)
 896                 return -1;
 897
 898         return 0;
 899 }
 900
 901 int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
 902 {
 903         S(UNION,plain_is_equal_data) data = { NULL, 1 };
 904
 905         if (!u1 || !u2)
 906                 return -1;
 907         if (u1 == u2)
 908                 return 1;
 909         if (u1->table.n != u2->table.n)
 910                 return 0;
 911
 912         u1 = FN(UNION,copy)(u1);
 913         u2 = FN(UNION,copy)(u2);
 914         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 915         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 916         if (!u1 || !u2)
 917                 goto error;
 918
 919         data.u2 = u2;
 920         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
 921                                    &plain_is_equal_entry, &data) < 0 &&
 922             data.is_equal)
 923                 goto error;
 924
 925         FN(UNION,free)(u1);
 926         FN(UNION,free)(u2);
 927
 928         return data.is_equal;
 929 error:
 930         FN(UNION,free)(u1);
 931         FN(UNION,free)(u2);
 932         return -1;
 933 }