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