polly/lib/External/isl/isl_union_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  * Copyright 2013      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #undef TYPE
  14 #define TYPE    UNION
  15 static
  16 #include "has_single_reference_templ.c"
  17
  18 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
  19
  20 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
  21 {
  22         return u ? u->space->ctx : NULL;
  23 }
  24
  25 /* Return the space of "u".
  26  */
  27 static __isl_keep isl_space *FN(UNION,peek_space)(__isl_keep UNION *u)
  28 {
  29         if (!u)
  30                 return NULL;
  31         return u->space;
  32 }
  33
  34 /* Return a copy of the space of "u".
  35  */
  36 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
  37 {
  38         return isl_space_copy(FN(UNION,peek_space)(u));
  39 }
  40
  41 /* Return the number of parameters of "u", where "type"
  42  * is required to be set to isl_dim_param.
  43  */
  44 isl_size FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
  45 {
  46         if (!u)
  47                 return isl_size_error;
  48
  49         if (type != isl_dim_param)
  50                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
  51                         "can only reference parameters", return isl_size_error);
  52
  53         return isl_space_dim(u->space, type);
  54 }
  55
  56 /* Return the position of the parameter with the given name
  57  * in "u".
  58  * Return -1 if no such dimension can be found.
  59  */
  60 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
  61         const char *name)
  62 {
  63         if (!u)
  64                 return -1;
  65         return isl_space_find_dim_by_name(u->space, type, name);
  66 }
  67
  68 #include "opt_type.h"
  69
  70 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space
  71         OPT_TYPE_PARAM, int size)
  72 {
  73         UNION *u;
  74
  75         space = isl_space_params(space);
  76         if (!space)
  77                 return NULL;
  78
  79         u = isl_calloc_type(space->ctx, UNION);
  80         if (!u)
  81                 goto error;
  82
  83         u->ref = 1;
  84         OPT_SET_TYPE(u->, type);
  85         u->space = space;
  86         if (isl_hash_table_init(space->ctx, &u->table, size) < 0)
  87                 return FN(UNION,free)(u);
  88
  89         return u;
  90 error:
  91         isl_space_free(space);
  92         return NULL;
  93 }
  94
  95 /* Create an empty/zero union without specifying any parameters.
  96  */
  97 __isl_give UNION *FN(FN(UNION,ZERO),ctx)(isl_ctx *ctx OPT_TYPE_PARAM)
  98 {
  99         isl_space *space;
 100
 101         space = isl_space_unit(ctx);
 102         return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
 103 }
 104
 105 __isl_give UNION *FN(FN(UNION,ZERO),space)(__isl_take isl_space *space
 106         OPT_TYPE_PARAM)
 107 {
 108         return FN(UNION,alloc)(space OPT_TYPE_ARG(NO_LOC), 16);
 109 }
 110
 111 /* This is an alternative name for the function above.
 112  */
 113 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
 114 {
 115         return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
 116 }
 117
 118 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
 119 {
 120         if (!u)
 121                 return NULL;
 122
 123         u->ref++;
 124         return u;
 125 }
 126
 127 /* Do the tuples of "space" correspond to those of the domain of "part"?
 128  * That is, is the domain space of "part" equal to "space", ignoring parameters?
 129  */
 130 static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part,
 131         __isl_keep isl_space *space)
 132 {
 133         return isl_space_has_domain_tuples(space, FN(PART,peek_space)(part));
 134 }
 135
 136 /* Extract the element of "u" living in "space" (ignoring parameters).
 137  *
 138  * Return the ZERO element if "u" does not contain any element
 139  * living in "space".
 140  */
 141 __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
 142         __isl_take isl_space *space)
 143 {
 144         struct isl_hash_table_entry *entry;
 145
 146         entry = FN(UNION,find_part_entry)(u, space, 0);
 147         if (!entry)
 148                 goto error;
 149         if (entry == isl_hash_table_entry_none)
 150                 return FN(PART,ZERO)(space OPT_TYPE_ARG(u->));
 151         isl_space_free(space);
 152         return FN(PART,copy)(entry->data);
 153 error:
 154         isl_space_free(space);
 155         return NULL;
 156 }
 157
 158 /* Add "part" to "u".
 159  * If "disjoint" is set, then "u" is not allowed to already have
 160  * a part that is defined over a domain that overlaps with the domain
 161  * of "part".
 162  * Otherwise, compute the union sum of "part" and the part in "u"
 163  * defined on the same space.
 164  */
 165 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
 166         __isl_take PART *part, int disjoint)
 167 {
 168         int empty;
 169         struct isl_hash_table_entry *entry;
 170
 171         if (!part)
 172                 goto error;
 173
 174         empty = FN(PART,IS_ZERO)(part);
 175         if (empty < 0)
 176                 goto error;
 177         if (empty) {
 178                 FN(PART,free)(part);
 179                 return u;
 180         }
 181
 182         u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
 183         part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
 184
 185         u = FN(UNION,cow)(u);
 186
 187         if (!u)
 188                 goto error;
 189
 190         if (FN(UNION,check_disjoint_domain_other)(u, part) < 0)
 191                 goto error;
 192         entry = FN(UNION,find_part_entry)(u, part->dim, 1);
 193         if (!entry)
 194                 goto error;
 195
 196         if (!entry->data)
 197                 entry->data = part;
 198         else {
 199                 if (disjoint &&
 200                     FN(UNION,check_disjoint_domain)(entry->data, part) < 0)
 201                         goto error;
 202                 entry->data = FN(PART,union_add_)(entry->data,
 203                                                 FN(PART,copy)(part));
 204                 empty = FN(PART,IS_ZERO)(entry->data);
 205                 if (empty < 0)
 206                         goto error;
 207                 if (empty)
 208                         u = FN(UNION,remove_part_entry)(u, entry);
 209                 FN(PART,free)(part);
 210         }
 211
 212         return u;
 213 error:
 214         FN(PART,free)(part);
 215         FN(UNION,free)(u);
 216         return NULL;
 217 }
 218
 219 /* Add "part" to "u", where "u" is assumed not to already have
 220  * a part that is defined on the same space as "part".
 221  */
 222 __isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
 223         __isl_take PART *part)
 224 {
 225         return FN(UNION,add_part_generic)(u, part, 1);
 226 }
 227
 228 /* Allocate a UNION with the same type (if any) and the same size as "u" and
 229  * with space "space".
 230  */
 231 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
 232         __isl_take isl_space *space)
 233 {
 234         if (!u)
 235                 goto error;
 236         return FN(UNION,alloc)(space OPT_TYPE_ARG(u->), u->table.n);
 237 error:
 238         isl_space_free(space);
 239         return NULL;
 240 }
 241
 242 /* Allocate a UNION with the same space, the same type (if any) and
 243  * the same size as "u".
 244  */
 245 static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
 246 {
 247         return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
 248 }
 249
 250 /* Data structure that specifies how isl_union_*_transform
 251  * should modify the base expressions in the union expression.
 252  *
 253  * If "inplace" is set, then the base expression in the input union
 254  * are modified in place.  This means that "fn" should not
 255  * change the meaning of the union or that the union only
 256  * has a single reference.
 257  * If "space" is not NULL, then a new union is created in this space.
 258  * If "filter" is not NULL, then only the base expressions that satisfy "filter"
 259  * are taken into account.
 260  * "filter_user" is passed as the second argument to "filter".
 261  * If "fn" it not NULL, then it is applied to each entry in the input.
 262  * "fn_user" is passed as the second argument to "fn".
 263  */
 264 S(UNION,transform_control) {
 265         int inplace;
 266         isl_space *space;
 267         isl_bool (*filter)(__isl_keep PART *part, void *user);
 268         void *filter_user;
 269         __isl_give PART *(*fn)(__isl_take PART *part, void *user);
 270         void *fn_user;
 271 };
 272
 273 /* Internal data structure for isl_union_*_transform_space.
 274  * "control" specifies how the base expressions should be modified.
 275  * "res" collects the results (if control->inplace is not set).
 276  */
 277 S(UNION,transform_data)
 278 {
 279         S(UNION,transform_control) *control;
 280         UNION *res;
 281 };
 282
 283 /* Apply control->fn to "part" and add the result to data->res or
 284  * place it back into the input union if control->inplace is set.
 285  */
 286 static isl_stat FN(UNION,transform_entry)(void **entry, void *user)
 287 {
 288         S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
 289         S(UNION,transform_control) *control = data->control;
 290         PART *part = *entry;
 291
 292         if (control->filter) {
 293                 isl_bool handle;
 294
 295                 handle = control->filter(part, control->filter_user);
 296                 if (handle < 0)
 297                         return isl_stat_error;
 298                 if (!handle)
 299                         return isl_stat_ok;
 300         }
 301
 302         if (!control->inplace)
 303                 part = FN(PART,copy)(part);
 304         if (control->fn)
 305                 part = control->fn(part, control->fn_user);
 306         if (control->inplace)
 307                 *entry = part;
 308         else
 309                 data->res = FN(FN(UNION,add),BASE)(data->res, part);
 310         if (!part || !data->res)
 311                 return isl_stat_error;
 312
 313         return isl_stat_ok;
 314 }
 315
 316 /* Return a UNION that is obtained by modifying "u" according to "control".
 317  */
 318 static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
 319         S(UNION,transform_control) *control)
 320 {
 321         S(UNION,transform_data) data = { control };
 322         isl_space *space;
 323
 324         if (control->inplace) {
 325                 data.res = u;
 326         } else {
 327                 if (control->space)
 328                         space = isl_space_copy(control->space);
 329                 else
 330                         space = FN(UNION,get_space)(u);
 331                 data.res = FN(UNION,alloc_same_size_on_space)(u, space);
 332         }
 333         if (FN(UNION,foreach_inplace)(u, &FN(UNION,transform_entry), &data) < 0)
 334                 data.res = FN(UNION,free)(data.res);
 335         if (!control->inplace)
 336                 FN(UNION,free)(u);
 337         return data.res;
 338 }
 339
 340 /* Return a UNION living in "space" that is otherwise obtained by modifying "u"
 341  * according to "control".
 342  */
 343 static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
 344         __isl_take isl_space *space, S(UNION,transform_control) *control)
 345 {
 346         if (!space)
 347                 return FN(UNION,free)(u);
 348         control->space = space;
 349         u = FN(UNION,transform)(u, control);
 350         isl_space_free(space);
 351         return u;
 352 }
 353
 354 /* Update "u" by applying "fn" to each entry.
 355  * This operation is assumed not to change the number of entries nor
 356  * the spaces of the entries.
 357  *
 358  * If there is only one reference to "u", then change "u" inplace.
 359  * Otherwise, create a new UNION from "u" and discard the original.
 360  */
 361 static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
 362         __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
 363 {
 364         S(UNION,transform_control) control = { .fn = fn, .fn_user = user };
 365         isl_bool single_ref;
 366
 367         single_ref = FN(UNION,has_single_reference)(u);
 368         if (single_ref < 0)
 369                 return FN(UNION,free)(u);
 370         if (single_ref)
 371                 control.inplace = 1;
 372         return FN(UNION,transform)(u, &control);
 373 }
 374
 375 /* An isl_union_*_transform callback for use in isl_union_*_dup
 376  * that simply returns "part".
 377  */
 378 static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
 379 {
 380         return part;
 381 }
 382
 383 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 384 {
 385         S(UNION,transform_control) control = { .fn = &FN(UNION,copy_part) };
 386
 387         u = FN(UNION,copy)(u);
 388         return FN(UNION,transform)(u, &control);
 389 }
 390
 391 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 392 {
 393         if (!u)
 394                 return NULL;
 395
 396         if (u->ref == 1)
 397                 return u;
 398         u->ref--;
 399         return FN(UNION,dup)(u);
 400 }
 401
 402 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
 403 {
 404         if (!u)
 405                 return NULL;
 406
 407         if (--u->ref > 0)
 408                 return NULL;
 409
 410         isl_hash_table_foreach(u->space->ctx, &u->table,
 411                                 &FN(UNION,free_u_entry), NULL);
 412         isl_hash_table_clear(&u->table);
 413         isl_space_free(u->space);
 414         free(u);
 415         return NULL;
 416 }
 417
 418 static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
 419 {
 420         isl_reordering *exp = user;
 421
 422         exp = isl_reordering_extend_space(isl_reordering_copy(exp),
 423                                     FN(PART,get_domain_space)(part));
 424         return FN(PART,realign_domain)(part, exp);
 425 }
 426
 427 /* Reorder the parameters of "u" according to the given reordering.
 428  */
 429 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
 430         __isl_take isl_reordering *r)
 431 {
 432         S(UNION,transform_control) control = {
 433                 .fn = &FN(UNION,align_entry),
 434                 .fn_user = r,
 435         };
 436         isl_space *space;
 437
 438         if (!u || !r)
 439                 goto error;
 440
 441         space = isl_reordering_get_space(r);
 442         u = FN(UNION,transform_space)(u, space, &control);
 443         isl_reordering_free(r);
 444         return u;
 445 error:
 446         FN(UNION,free)(u);
 447         isl_reordering_free(r);
 448         return NULL;
 449 }
 450
 451 /* Align the parameters of "u" to those of "model".
 452  */
 453 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 454         __isl_take isl_space *model)
 455 {
 456         isl_space *space;
 457         isl_bool equal_params;
 458         isl_reordering *r;
 459
 460         space = FN(UNION,peek_space)(u);
 461         equal_params = isl_space_has_equal_params(space, model);
 462         if (equal_params < 0)
 463                 goto error;
 464         if (equal_params) {
 465                 isl_space_free(model);
 466                 return u;
 467         }
 468
 469         r = isl_parameter_alignment_reordering(space, model);
 470         isl_space_free(model);
 471
 472         return FN(UNION,realign_domain)(u, r);
 473 error:
 474         isl_space_free(model);
 475         FN(UNION,free)(u);
 476         return NULL;
 477 }
 478
 479 /* Add "part" to *u, taking the union sum if "u" already has
 480  * a part defined on the same space as "part".
 481  */
 482 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
 483 {
 484         UNION **u = (UNION **)user;
 485
 486         *u = FN(UNION,add_part_generic)(*u, part, 0);
 487
 488         return isl_stat_ok;
 489 }
 490
 491 /* Compute the sum of "u1" and "u2" on the union of their domains,
 492  * with the actual sum on the shared domain and
 493  * the defined expression on the symmetric difference of the domains.
 494  *
 495  * This is an internal function that is exposed under different
 496  * names depending on whether the base expressions have a zero default
 497  * value.
 498  * If they do, then this function is called "add".
 499  * Otherwise, it is called "union_add".
 500  */
 501 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
 502         __isl_take UNION *u2)
 503 {
 504         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 505         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 506
 507         u1 = FN(UNION,cow)(u1);
 508
 509         if (!u1 || !u2)
 510                 goto error;
 511
 512         if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
 513                 goto error;
 514
 515         FN(UNION,free)(u2);
 516
 517         return u1;
 518 error:
 519         FN(UNION,free)(u1);
 520         FN(UNION,free)(u2);
 521         return NULL;
 522 }
 523
 524 #if !DEFAULT_IS_ZERO
 525
 526 /* Compute the sum of "u1" and "u2" on the union of their domains,
 527  * with the actual sum on the shared domain and
 528  * the defined expression on the symmetric difference of the domains.
 529  */
 530 __isl_give UNION *FN(UNION,union_add)(__isl_take UNION *u1,
 531         __isl_take UNION *u2)
 532 {
 533         return FN(UNION,union_add_)(u1, u2);
 534 }
 535
 536 #endif
 537
 538 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
 539 {
 540         isl_space *space;
 541         UNION *u;
 542
 543         if (!part)
 544                 return NULL;
 545
 546         space = FN(PART,get_space)(part);
 547         space = isl_space_drop_dims(space, isl_dim_in, 0,
 548                                         isl_space_dim(space, isl_dim_in));
 549         space = isl_space_drop_dims(space, isl_dim_out, 0,
 550                                         isl_space_dim(space, isl_dim_out));
 551         u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->));
 552         u = FN(FN(UNION,add),BASE)(u, part);
 553
 554         return u;
 555 }
 556
 557 /* This function performs the same operation as isl_union_pw_*_from_pw_*,
 558  * but is considered as a function on an isl_pw_* when exported.
 559  */
 560 __isl_give UNION *FN(FN(PART,to_union),BASE)(__isl_take PART *part)
 561 {
 562         return FN(FN(UNION,from),BASE)(part);
 563 }
 564
 565 S(UNION,match_bin_data) {
 566         UNION *u2;
 567         UNION *res;
 568         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 569 };
 570
 571 /* Check if data->u2 has an element living in the same space as "part".
 572  * If so, call data->fn on the two elements and add the result to
 573  * data->res.
 574  */
 575 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
 576 {
 577         S(UNION,match_bin_data) *data = user;
 578         struct isl_hash_table_entry *entry2;
 579         isl_space *space;
 580         PART *part2;
 581
 582         space = FN(PART,get_space)(part);
 583         entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
 584         isl_space_free(space);
 585         if (!entry2)
 586                 goto error;
 587         if (entry2 == isl_hash_table_entry_none) {
 588                 FN(PART,free)(part);
 589                 return isl_stat_ok;
 590         }
 591
 592         part2 = entry2->data;
 593         if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
 594                                         part2->dim, isl_dim_out))
 595                 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
 596                         "entries should have the same range space",
 597                         goto error);
 598
 599         part = data->fn(part, FN(PART, copy)(entry2->data));
 600
 601         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 602         if (!data->res)
 603                 return isl_stat_error;
 604
 605         return isl_stat_ok;
 606 error:
 607         FN(PART,free)(part);
 608         return isl_stat_error;
 609 }
 610
 611 /* This function is currently only used from isl_polynomial.c
 612  * and not from isl_fold.c.
 613  */
 614 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 615         __isl_take UNION *u2,
 616         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 617         __attribute__ ((unused));
 618 /* For each pair of elements in "u1" and "u2" living in the same space,
 619  * call "fn" and collect the results.
 620  */
 621 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 622         __isl_take UNION *u2,
 623         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 624 {
 625         S(UNION,match_bin_data) data = { NULL, NULL, fn };
 626
 627         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 628         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 629
 630         if (!u1 || !u2)
 631                 goto error;
 632
 633         data.u2 = u2;
 634         data.res = FN(UNION,alloc_same_size)(u1);
 635         if (FN(FN(UNION,foreach),BASE)(u1,
 636                                     &FN(UNION,match_bin_entry), &data) < 0)
 637                 goto error;
 638
 639         FN(UNION,free)(u1);
 640         FN(UNION,free)(u2);
 641         return data.res;
 642 error:
 643         FN(UNION,free)(u1);
 644         FN(UNION,free)(u2);
 645         FN(UNION,free)(data.res);
 646         return NULL;
 647 }
 648
 649 /* Compute the sum of "u1" and "u2".
 650  *
 651  * If the base expressions have a default zero value, then the sum
 652  * is computed on the union of the domains of "u1" and "u2".
 653  * Otherwise, it is computed on their shared domains.
 654  */
 655 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 656 {
 657 #if DEFAULT_IS_ZERO
 658         return FN(UNION,union_add_)(u1, u2);
 659 #else
 660         return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
 661 #endif
 662 }
 663
 664 S(UNION,any_set_data) {
 665         isl_set *set;
 666         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 667 };
 668
 669 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
 670         void *user)
 671 {
 672         S(UNION,any_set_data) *data = user;
 673
 674         return data->fn(part, isl_set_copy(data->set));
 675 }
 676
 677 /* Update each element of "u" by calling "fn" on the element and "set".
 678  */
 679 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
 680         __isl_take isl_set *set,
 681         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 682 {
 683         S(UNION,any_set_data) data = { NULL, fn };
 684         S(UNION,transform_control) control = {
 685                 .fn = &FN(UNION,any_set_entry),
 686                 .fn_user = &data,
 687         };
 688
 689         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 690         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 691
 692         if (!u || !set)
 693                 goto error;
 694
 695         data.set = set;
 696         u = FN(UNION,transform)(u, &control);
 697         isl_set_free(set);
 698         return u;
 699 error:
 700         FN(UNION,free)(u);
 701         isl_set_free(set);
 702         return NULL;
 703 }
 704
 705 /* Intersect the domain of "u" with the parameter domain "context".
 706  */
 707 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 708         __isl_take isl_set *set)
 709 {
 710         return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
 711 }
 712
 713 /* Compute the gist of the domain of "u" with respect to
 714  * the parameter domain "context".
 715  */
 716 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 717         __isl_take isl_set *set)
 718 {
 719         return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
 720 }
 721
 722 /* Data structure that specifies how isl_union_*_match_domain_op
 723  * should combine its arguments.
 724  *
 725  * If "filter" is not NULL, then only parts that pass the given
 726  * filter are considered for matching.
 727  * "fn" is applied to each part in the union and each corresponding
 728  * set in the union set, i.e., such that the set lives in the same space
 729  * as the domain of the part.
 730  * If "match_space" is not NULL, then the set extracted from the union set
 731  * does not live in the same space as the domain of the part,
 732  * but rather in the space that results from calling "match_space"
 733  * on this domain space.
 734  */
 735 S(UNION,match_domain_control) {
 736         isl_bool (*filter)(__isl_keep PART *part);
 737         __isl_give isl_space *(*match_space)(__isl_take isl_space *space);
 738         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 739 };
 740
 741 S(UNION,match_domain_data) {
 742         isl_union_set *uset;
 743         UNION *res;
 744         S(UNION,match_domain_control) *control;
 745 };
 746
 747 /* Find the set in data->uset that lives in the same space as the domain
 748  * of "part" (ignoring parameters), apply data->fn to *entry and this set
 749  * (if any), and add the result to data->res.
 750  */
 751 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
 752 {
 753         S(UNION,match_domain_data) *data = user;
 754         struct isl_hash_table_entry *entry2;
 755         isl_space *space;
 756
 757         if (data->control->filter) {
 758                 isl_bool pass = data->control->filter(part);
 759                 if (pass < 0 || !pass) {
 760                         FN(PART,free)(part);
 761                         return pass < 0 ? isl_stat_error : isl_stat_ok;
 762                 }
 763         }
 764
 765         space = FN(PART,get_domain_space)(part);
 766         if (data->control->match_space)
 767                 space = data->control->match_space(space);
 768         entry2 = isl_union_set_find_entry(data->uset, space, 0);
 769         isl_space_free(space);
 770         if (!entry2 || entry2 == isl_hash_table_entry_none) {
 771                 FN(PART,free)(part);
 772                 return isl_stat_non_null(entry2);
 773         }
 774
 775         part = data->control->fn(part, isl_set_copy(entry2->data));
 776
 777         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 778         if (!data->res)
 779                 return isl_stat_error;
 780
 781         return isl_stat_ok;
 782 }
 783
 784 /* Combine "u" and "uset" according to "control"
 785  * and collect the results.
 786  */
 787 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
 788         __isl_take isl_union_set *uset, S(UNION,match_domain_control) *control)
 789 {
 790         S(UNION,match_domain_data) data = { NULL, NULL, control };
 791
 792         if (!u || !uset)
 793                 goto error;
 794
 795         data.uset = uset;
 796         data.res = FN(UNION,alloc_same_size)(u);
 797         if (FN(FN(UNION,foreach),BASE)(u,
 798                                    &FN(UNION,match_domain_entry), &data) < 0)
 799                 goto error;
 800
 801         FN(UNION,free)(u);
 802         isl_union_set_free(uset);
 803         return data.res;
 804 error:
 805         FN(UNION,free)(u);
 806         isl_union_set_free(uset);
 807         FN(UNION,free)(data.res);
 808         return NULL;
 809 }
 810
 811 /* Intersect the domain of "u" with "uset".
 812  * If "uset" is a parameters domain, then intersect the parameter
 813  * domain of "u" with this set.
 814  */
 815 __isl_give UNION *FN(UNION,intersect_domain_union_set)(__isl_take UNION *u,
 816         __isl_take isl_union_set *uset)
 817 {
 818         S(UNION,match_domain_control) control = {
 819                 .fn = &FN(PW,intersect_domain),
 820         };
 821
 822         if (isl_union_set_is_params(uset))
 823                 return FN(UNION,intersect_params)(u,
 824                                                 isl_set_from_union_set(uset));
 825         return FN(UNION,match_domain_op)(u, uset, &control);
 826 }
 827
 828 /* This is an alternative name for the function above.
 829  */
 830 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 831         __isl_take isl_union_set *uset)
 832 {
 833         return FN(UNION,intersect_domain_union_set)(u, uset);
 834 }
 835
 836 /* Return true if this part should be kept.
 837  *
 838  * In particular, it should be kept if its domain space
 839  * corresponds to "space".
 840  */
 841 static isl_bool FN(UNION,select_entry)(__isl_keep PART *part, void *user)
 842 {
 843         isl_space *space = user;
 844
 845         return FN(PW,has_domain_space_tuples)(part, space);
 846 }
 847
 848 /* Remove any not element in "space" from the domain of "u".
 849  *
 850  * In particular, select any part of the function defined
 851  * on this domain space.
 852  */
 853 __isl_give UNION *FN(UNION,intersect_domain_space)(__isl_take UNION *u,
 854         __isl_take isl_space *space)
 855 {
 856         S(UNION,transform_control) control = {
 857                 .filter = &FN(UNION,select_entry),
 858                 .filter_user = space,
 859         };
 860
 861         u = FN(UNION,transform)(u, &control);
 862         isl_space_free(space);
 863         return u;
 864 }
 865
 866 /* Is the domain of "pw" a wrapped relation?
 867  */
 868 static isl_bool FN(PW,domain_is_wrapping)(__isl_keep PW *pw)
 869 {
 870         return isl_space_domain_is_wrapping(FN(PW,peek_space)(pw));
 871 }
 872
 873 /* Intersect the domain of the wrapped relation inside the domain of "u"
 874  * with "uset".
 875  */
 876 __isl_give UNION *FN(UNION,intersect_domain_wrapped_domain)(__isl_take UNION *u,
 877         __isl_take isl_union_set *uset)
 878 {
 879         S(UNION,match_domain_control) control = {
 880                 .filter = &FN(PART,domain_is_wrapping),
 881                 .match_space = &isl_space_factor_domain,
 882                 .fn = &FN(PW,intersect_domain_wrapped_domain),
 883         };
 884
 885         return FN(UNION,match_domain_op)(u, uset, &control);
 886 }
 887
 888 /* Intersect the range of the wrapped relation inside the domain of "u"
 889  * with "uset".
 890  */
 891 __isl_give UNION *FN(UNION,intersect_domain_wrapped_range)(__isl_take UNION *u,
 892         __isl_take isl_union_set *uset)
 893 {
 894         S(UNION,match_domain_control) control = {
 895                 .filter = &FN(PART,domain_is_wrapping),
 896                 .match_space = &isl_space_factor_range,
 897                 .fn = &FN(PW,intersect_domain_wrapped_range),
 898         };
 899
 900         return FN(UNION,match_domain_op)(u, uset, &control);
 901 }
 902
 903 /* Take the set (which may be empty) in data->uset that lives
 904  * in the same space as the domain of "pw", subtract it from the domain
 905  * of "part" and return the result.
 906  */
 907 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
 908         void *user)
 909 {
 910         isl_union_set *uset = user;
 911         isl_space *space;
 912         isl_set *set;
 913
 914         space = FN(PART,get_domain_space)(part);
 915         set = isl_union_set_extract_set(uset, space);
 916         return FN(PART,subtract_domain)(part, set);
 917 }
 918
 919 /* Subtract "uset" from the domain of "u".
 920  */
 921 __isl_give UNION *FN(UNION,subtract_domain_union_set)(__isl_take UNION *u,
 922         __isl_take isl_union_set *uset)
 923 {
 924         S(UNION,transform_control) control = {
 925                 .fn = &FN(UNION,subtract_domain_entry),
 926                 .fn_user = uset,
 927         };
 928
 929         u = FN(UNION,transform)(u, &control);
 930         isl_union_set_free(uset);
 931         return u;
 932 }
 933
 934 /* This is an alternative name for the function above.
 935  */
 936 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
 937         __isl_take isl_union_set *uset)
 938 {
 939         return FN(UNION,subtract_domain_union_set)(u, uset);
 940 }
 941
 942 /* Return true if this part should be kept.
 943  *
 944  * In particular, it should be kept if its domain space
 945  * does not correspond to "space".
 946  */
 947 static isl_bool FN(UNION,filter_out_entry)(__isl_keep PART *part, void *user)
 948 {
 949         isl_space *space = user;
 950
 951         return isl_bool_not(FN(PW,has_domain_space_tuples)(part, space));
 952 }
 953
 954 /* Remove any element in "space" from the domain of "u".
 955  *
 956  * In particular, filter out any part of the function defined
 957  * on this domain space.
 958  */
 959 __isl_give UNION *FN(UNION,subtract_domain_space)(__isl_take UNION *u,
 960         __isl_take isl_space *space)
 961 {
 962         S(UNION,transform_control) control = {
 963                 .filter = &FN(UNION,filter_out_entry),
 964                 .filter_user = space,
 965         };
 966
 967         u = FN(UNION,transform)(u, &control);
 968         isl_space_free(space);
 969         return u;
 970 }
 971
 972 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 973         __isl_take isl_union_set *uset)
 974 {
 975         S(UNION,match_domain_control) control = {
 976                 .fn = &FN(PW,gist),
 977         };
 978
 979         if (isl_union_set_is_params(uset))
 980                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 981         return FN(UNION,match_domain_op)(u, uset, &control);
 982 }
 983
 984 /* Coalesce an entry in a UNION.  Coalescing is performed in-place.
 985  * Since the UNION may have several references, the entry is only
 986  * replaced if the coalescing is successful.
 987  */
 988 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
 989 {
 990         PART **part_p = (PART **) entry;
 991         PART *part;
 992
 993         part = FN(PART,copy)(*part_p);
 994         part = FN(PW,coalesce)(part);
 995         if (!part)
 996                 return isl_stat_error;
 997         FN(PART,free)(*part_p);
 998         *part_p = part;
 999
1000         return isl_stat_ok;
1001 }
1002
1003 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
1004 {
1005         if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
1006                 goto error;
1007
1008         return u;
1009 error:
1010         FN(UNION,free)(u);
1011         return NULL;
1012 }
1013
1014 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
1015 {
1016         isl_union_set **uset = (isl_union_set **)user;
1017
1018         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
1019
1020         return isl_stat_ok;
1021 }
1022
1023 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
1024 {
1025         isl_union_set *uset;
1026
1027         uset = isl_union_set_empty(FN(UNION,get_space)(u));
1028         if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
1029                 goto error;
1030
1031         FN(UNION,free)(u);
1032
1033         return uset;
1034 error:
1035         isl_union_set_free(uset);
1036         FN(UNION,free)(u);
1037         return NULL;
1038 }
1039
1040 #ifdef HAS_TYPE
1041 /* Negate the type of "u".
1042  */
1043 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1044 {
1045         u = FN(UNION,cow)(u);
1046         if (!u)
1047                 return NULL;
1048         u->type = isl_fold_type_negate(u->type);
1049         return u;
1050 }
1051 #else
1052 /* Negate the type of "u".
1053  * Since "u" does not have a type, do nothing.
1054  */
1055 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1056 {
1057         return u;
1058 }
1059 #endif
1060
1061 /* Multiply "part" by the isl_val "user" and return the result.
1062  */
1063 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
1064         void *user)
1065 {
1066         isl_val *v = user;
1067
1068         return FN(PART,scale_val)(part, isl_val_copy(v));
1069 }
1070
1071 /* Multiply "u" by "v" and return the result.
1072  */
1073 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1074         __isl_take isl_val *v)
1075 {
1076         if (!u || !v)
1077                 goto error;
1078         if (isl_val_is_one(v)) {
1079                 isl_val_free(v);
1080                 return u;
1081         }
1082
1083         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1084                 UNION *zero;
1085                 isl_space *space = FN(UNION,get_space)(u);
1086                 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->));
1087                 FN(UNION,free)(u);
1088                 isl_val_free(v);
1089                 return zero;
1090         }
1091
1092         if (!isl_val_is_rat(v))
1093                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1094                         "expecting rational factor", goto error);
1095
1096         u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
1097         if (isl_val_is_neg(v))
1098                 u = FN(UNION,negate_type)(u);
1099
1100         isl_val_free(v);
1101         return u;
1102 error:
1103         isl_val_free(v);
1104         FN(UNION,free)(u);
1105         return NULL;
1106 }
1107
1108 /* Divide "part" by the isl_val "user" and return the result.
1109  */
1110 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
1111         void *user)
1112 {
1113         isl_val *v = user;
1114
1115         return FN(PART,scale_down_val)(part, isl_val_copy(v));
1116 }
1117
1118 /* Divide "u" by "v" and return the result.
1119  */
1120 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1121         __isl_take isl_val *v)
1122 {
1123         if (!u || !v)
1124                 goto error;
1125         if (isl_val_is_one(v)) {
1126                 isl_val_free(v);
1127                 return u;
1128         }
1129
1130         if (!isl_val_is_rat(v))
1131                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1132                         "expecting rational factor", goto error);
1133         if (isl_val_is_zero(v))
1134                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1135                         "cannot scale down by zero", goto error);
1136
1137         u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
1138         if (isl_val_is_neg(v))
1139                 u = FN(UNION,negate_type)(u);
1140
1141         isl_val_free(v);
1142         return u;
1143 error:
1144         isl_val_free(v);
1145         FN(UNION,free)(u);
1146         return NULL;
1147 }
1148
1149 /* Internal data structure for isl_union_*_every_*.
1150  *
1151  * "test" is the user-specified callback function.
1152  * "user" is the user-specified callback function argument.
1153  *
1154  * "res" is the final result, initialized to isl_bool_true.
1155  */
1156 S(UNION,every_data) {
1157         isl_bool (*test)(__isl_keep PW *pw, void *user);
1158         void *user;
1159
1160         isl_bool res;
1161 };
1162
1163 /* Call data->test on the piecewise expression at *entry,
1164  * updating the result in data->res.
1165  * Abort if this result is no longer isl_bool_true.
1166  */
1167 static isl_stat FN(UNION,every_entry)(void **entry, void *user)
1168 {
1169         S(UNION,every_data) *data = user;
1170         PW *pw = *entry;
1171
1172         data->res = data->test(pw, data->user);
1173         if (data->res < 0 || !data->res)
1174                 return isl_stat_error;
1175
1176         return isl_stat_ok;
1177 }
1178
1179 /* Does "test" succeed on every piecewise expression in "u"?
1180  */
1181 isl_bool FN(FN(UNION,every),BASE)(__isl_keep UNION *u,
1182         isl_bool (*test)(__isl_keep PW *pw, void *user), void *user)
1183 {
1184         S(UNION,every_data) data = { test, user };
1185
1186         data.res = isl_bool_true;
1187         if (FN(UNION,foreach_inplace)(u, &FN(UNION,every_entry), &data) < 0 &&
1188             data.res == isl_bool_true)
1189                 return isl_bool_error;
1190
1191         return data.res;
1192 }
1193
1194 S(UNION,plain_is_equal_data)
1195 {
1196         UNION *u2;
1197 };
1198
1199 static isl_bool FN(UNION,plain_is_equal_el)(__isl_keep PW *pw, void *user)
1200 {
1201         S(UNION,plain_is_equal_data) *data = user;
1202         struct isl_hash_table_entry *entry;
1203
1204         entry = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1205         if (!entry)
1206                 return isl_bool_error;
1207         if (entry == isl_hash_table_entry_none)
1208                 return isl_bool_false;
1209
1210         return FN(PW,plain_is_equal)(pw, entry->data);
1211 }
1212
1213 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1214 {
1215         S(UNION,plain_is_equal_data) data;
1216         isl_size n1, n2;
1217         isl_bool is_equal;
1218
1219         if (!u1 || !u2)
1220                 return isl_bool_error;
1221         if (u1 == u2)
1222                 return isl_bool_true;
1223         if (u1->table.n != u2->table.n)
1224                 return isl_bool_false;
1225         n1 = FN(FN(UNION,n),BASE)(u1);
1226         n2 = FN(FN(UNION,n),BASE)(u2);
1227         if (n1 < 0 || n2 < 0)
1228                 return isl_bool_error;
1229         if (n1 != n2)
1230                 return isl_bool_false;
1231
1232         u1 = FN(UNION,copy)(u1);
1233         u2 = FN(UNION,copy)(u2);
1234         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1235         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1236         if (!u1 || !u2)
1237                 goto error;
1238
1239         data.u2 = u2;
1240         is_equal = FN(FN(UNION,every),BASE)(u1,
1241                                           &FN(UNION,plain_is_equal_el), &data);
1242
1243         FN(UNION,free)(u1);
1244         FN(UNION,free)(u2);
1245
1246         return is_equal;
1247 error:
1248         FN(UNION,free)(u1);
1249         FN(UNION,free)(u2);
1250         return isl_bool_error;
1251 }
1252
1253 /* An isl_union_*_every_* callback that checks whether "pw"
1254  * does not involve any NaNs.
1255  */
1256 static isl_bool FN(UNION,no_nan_el)(__isl_keep PW *pw, void *user)
1257 {
1258         return isl_bool_not(FN(PW,involves_nan)(pw));
1259 }
1260
1261 /* Does "u" involve any NaNs?
1262  */
1263 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1264 {
1265         isl_bool no_nan;
1266
1267         no_nan = FN(FN(UNION,every),BASE)(u, &FN(UNION,no_nan_el), NULL);
1268
1269         return isl_bool_not(no_nan);
1270 }
1271
1272 /* Internal data structure for isl_union_*_drop_dims.
1273  * type, first and n are passed to isl_*_drop_dims.
1274  */
1275 S(UNION,drop_dims_data) {
1276         enum isl_dim_type type;
1277         unsigned first;
1278         unsigned n;
1279 };
1280
1281 /* Drop the parameters specified by "data" from "part" and return the result.
1282  */
1283 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1284         void *user)
1285 {
1286         S(UNION,drop_dims_data) *data = user;
1287
1288         return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1289 }
1290
1291 /* Drop the specified parameters from "u".
1292  * That is, type is required to be isl_dim_param.
1293  */
1294 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1295         enum isl_dim_type type, unsigned first, unsigned n)
1296 {
1297         isl_space *space;
1298         S(UNION,drop_dims_data) data = { type, first, n };
1299         S(UNION,transform_control) control = {
1300                 .fn = &FN(UNION,drop_dims_entry),
1301                 .fn_user = &data,
1302         };
1303
1304         if (!u)
1305                 return NULL;
1306
1307         if (type != isl_dim_param)
1308                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1309                         "can only project out parameters",
1310                         return FN(UNION,free)(u));
1311
1312         space = FN(UNION,get_space)(u);
1313         space = isl_space_drop_dims(space, type, first, n);
1314         return FN(UNION,transform_space)(u, space, &control);
1315 }
1316
1317 /* Internal data structure for isl_union_*_set_dim_name.
1318  * pos is the position of the parameter that needs to be renamed.
1319  * s is the new name.
1320  */
1321 S(UNION,set_dim_name_data) {
1322         unsigned pos;
1323         const char *s;
1324 };
1325
1326 /* Change the name of the parameter at position data->pos of "part" to data->s
1327  * and return the result.
1328  */
1329 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1330         void *user)
1331 {
1332         S(UNION,set_dim_name_data) *data = user;
1333
1334         return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1335 }
1336
1337 /* Change the name of the parameter at position "pos" to "s".
1338  * That is, type is required to be isl_dim_param.
1339  */
1340 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1341         enum isl_dim_type type, unsigned pos, const char *s)
1342 {
1343         S(UNION,set_dim_name_data) data = { pos, s };
1344         S(UNION,transform_control) control = {
1345                 .fn = &FN(UNION,set_dim_name_entry),
1346                 .fn_user = &data,
1347         };
1348         isl_space *space;
1349
1350         if (!u)
1351                 return NULL;
1352
1353         if (type != isl_dim_param)
1354                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1355                         "can only set parameter names",
1356                         return FN(UNION,free)(u));
1357
1358         space = FN(UNION,get_space)(u);
1359         space = isl_space_set_dim_name(space, type, pos, s);
1360         return FN(UNION,transform_space)(u, space, &control);
1361 }
1362
1363 /* Reset the user pointer on all identifiers of parameters and tuples
1364  * of the space of "part" and return the result.
1365  */
1366 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1367         void *user)
1368 {
1369         return FN(PART,reset_user)(part);
1370 }
1371
1372 /* Reset the user pointer on all identifiers of parameters and tuples
1373  * of the spaces of "u".
1374  */
1375 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1376 {
1377         S(UNION,transform_control) control = {
1378                 .fn = &FN(UNION,reset_user_entry),
1379         };
1380         isl_space *space;
1381
1382         space = FN(UNION,get_space)(u);
1383         space = isl_space_reset_user(space);
1384         return FN(UNION,transform_space)(u, space, &control);
1385 }
1386
1387 /* Add the base expression held by "entry" to "list".
1388  */
1389 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1390 {
1391         PW *pw = *entry;
1392         LIST(PART) **list = user;
1393
1394         *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1395         if (!*list)
1396                 return isl_stat_error;
1397
1398         return isl_stat_ok;
1399 }
1400
1401 /* Return a list containing all the base expressions in "u".
1402  *
1403  * First construct a list of the appropriate size and
1404  * then add all the elements.
1405  */
1406 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1407 {
1408         isl_size n;
1409         LIST(PART) *list;
1410
1411         if (!u)
1412                 return NULL;
1413         n = FN(FN(UNION,n),BASE)(u);
1414         if (n < 0)
1415                 return NULL;
1416         list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1417         if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1418                 return FN(LIST(PART),free)(list);
1419
1420         return list;
1421 }