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