1422 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 * Copyright 2013 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *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, France11 */12 13#undef TYPE14#define TYPE UNION15static16#include "has_single_reference_templ.c"17 18__isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);19 20isl_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 */27static __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 */44isl_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 name57 * in "u".58 * Return -1 if no such dimension can be found.59 */60int 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 70static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space71 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;90error: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 *space106 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 */130static 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 element139 * 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);153error: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 have160 * a part that is defined over a domain that overlaps with the domain161 * of "part".162 * Otherwise, compute the union sum of "part" and the part in "u"163 * defined on the same space.164 */165static __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;213error: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 have220 * 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" and229 * with space "space".230 */231static __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);237error:238 isl_space_free(space);239 return NULL;240}241 242/* Allocate a UNION with the same space, the same type (if any) and243 * the same size as "u".244 */245static __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_*_transform251 * should modify the base expressions in the union expression.252 *253 * If "inplace" is set, then the base expression in the input union254 * are modified in place. This means that "fn" should not255 * change the meaning of the union or that the union only256 * 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 */264S(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 */277S(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 or284 * place it back into the input union if control->inplace is set.285 */286static 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 else309 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 */318static __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 else330 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 */343static __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 nor356 * 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 */361static __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_*_dup376 * that simply returns "part".377 */378static __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 418static __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 */429static __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;445error: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);473error: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 has480 * a part defined on the same space as "part".481 */482static 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 and493 * the defined expression on the symmetric difference of the domains.494 *495 * This is an internal function that is exposed under different496 * names depending on whether the base expressions have a zero default497 * value.498 * If they do, then this function is called "add".499 * Otherwise, it is called "union_add".500 */501static __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;518error:519 FN(UNION,free)(u1);520 FN(UNION,free)(u2);521 return NULL;522}523 524#if !DEFAULT_IS_ZERO525 526/* Compute the sum of "u1" and "u2" on the union of their domains,527 * with the actual sum on the shared domain and528 * 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#endif537 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 565S(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 to573 * data->res.574 */575static 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;606error:607 FN(PART,free)(part);608 return isl_stat_error;609}610 611/* This function is currently only used from isl_polynomial.c612 * and not from isl_fold.c.613 */614static __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 */621static __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;642error: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 sum652 * 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_ZERO658 return FN(UNION,union_add_)(u1, u2);659#else660 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));661#endif662}663 664S(UNION,any_set_data) {665 isl_set *set;666 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);667};668 669static __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 */679static __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;699error: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 to714 * 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_op723 * should combine its arguments.724 *725 * If "filter" is not NULL, then only parts that pass the given726 * filter are considered for matching.727 * "fn" is applied to each part in the union and each corresponding728 * set in the union set, i.e., such that the set lives in the same space729 * as the domain of the part.730 * If "match_space" is not NULL, then the set extracted from the union set731 * 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 */735S(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 741S(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 domain748 * of "part" (ignoring parameters), apply data->fn to *entry and this set749 * (if any), and add the result to data->res.750 */751static 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 */787static __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;804error: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 parameter813 * 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 space839 * corresponds to "space".840 */841static 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 defined851 * 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 */868static 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 lives904 * in the same space as the domain of "pw", subtract it from the domain905 * of "part" and return the result.906 */907static __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 space945 * does not correspond to "space".946 */947static 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 defined957 * 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 only986 * replaced if the coalescing is successful.987 */988static 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;1009error:1010 FN(UNION,free)(u);1011 return NULL;1012}1013 1014static 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;1034error:1035 isl_union_set_free(uset);1036 FN(UNION,free)(u);1037 return NULL;1038}1039 1040#ifdef HAS_TYPE1041/* Negate the type of "u".1042 */1043static __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#else1052/* Negate the type of "u".1053 * Since "u" does not have a type, do nothing.1054 */1055static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)1056{1057 return u;1058}1059#endif1060 1061/* Multiply "part" by the isl_val "user" and return the result.1062 */1063static __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;1102error: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 */1110static __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;1143error: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 */1156S(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 */1167static 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 */1181isl_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 1194S(UNION,plain_is_equal_data)1195{1196 UNION *u2;1197};1198 1199static 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 1213isl_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;1247error: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 */1256static 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 */1263isl_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 */1275S(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 */1283static __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 */1321S(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->s1327 * and return the result.1328 */1329static __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 tuples1364 * of the space of "part" and return the result.1365 */1366static __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 tuples1373 * 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 */1389static 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 and1404 * 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}1422