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