1915 lines · c
1/*2 * Copyright 2010-2011 INRIA Saclay3 * Copyright 2011 Sven Verdoolaege4 * Copyright 2012-2014 Ecole Normale Superieure5 *6 * Use of this software is governed by the MIT license7 *8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,10 * 91893 Orsay, France11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France12 */13 14#include <isl/id.h>15#include <isl/aff.h>16#include <isl_sort.h>17#include <isl_val_private.h>18 19#include <isl_pw_macro.h>20 21#include "opt_type.h"22 23__isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *space24 OPT_TYPE_PARAM, int n)25{26 isl_ctx *ctx;27 struct PW *pw;28 29 if (!space)30 return NULL;31 ctx = isl_space_get_ctx(space);32 isl_assert(ctx, n >= 0, goto error);33 pw = isl_alloc(ctx, struct PW,34 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));35 if (!pw)36 goto error;37 38 pw->ref = 1;39 OPT_SET_TYPE(pw->, type);40 pw->size = n;41 pw->n = 0;42 pw->dim = space;43 return pw;44error:45 isl_space_free(space);46 return NULL;47}48 49__isl_give PW *FN(PW,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)50{51 return FN(PW,alloc_size)(space OPT_TYPE_ARG(NO_LOC), 0);52}53 54/* Add a piece with domain "set" and base expression "el"55 * to the piecewise expression "pw".56 *57 * Do this independently of the values of "set" and "el",58 * such that this function can be used by isl_pw_*_dup.59 */60static __isl_give PW *FN(PW,add_dup_piece)(__isl_take PW *pw,61 __isl_take isl_set *set, __isl_take EL *el)62{63 isl_ctx *ctx;64 isl_space *el_dim = NULL;65 66 if (!pw || !set || !el)67 goto error;68 69 ctx = isl_set_get_ctx(set);70 if (!OPT_EQUAL_TYPES(pw->, el->))71 isl_die(ctx, isl_error_invalid, "fold types don't match",72 goto error);73 el_dim = FN(EL,get_space(el));74 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);75 isl_assert(ctx, pw->n < pw->size, goto error);76 77 pw->p[pw->n].set = set;78 pw->p[pw->n].FIELD = el;79 pw->n++;80 81 isl_space_free(el_dim);82 return pw;83error:84 isl_space_free(el_dim);85 FN(PW,free)(pw);86 isl_set_free(set);87 FN(EL,free)(el);88 return NULL;89}90 91/* Add a piece with domain "set" and base expression "el"92 * to the piecewise expression "pw", provided the domain93 * is not obviously empty and the base expression94 * is not equal to the default value.95 */96__isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,97 __isl_take isl_set *set, __isl_take EL *el)98{99 isl_bool skip;100 101 skip = isl_set_plain_is_empty(set);102 if (skip >= 0 && !skip)103 skip = FN(EL,EL_IS_ZERO)(el);104 if (skip >= 0 && !skip)105 return FN(PW,add_dup_piece)(pw, set, el);106 107 isl_set_free(set);108 FN(EL,free)(el);109 if (skip < 0)110 return FN(PW,free)(pw);111 return pw;112}113 114/* Does the space of "set" correspond to that of the domain of "el".115 */116static isl_bool FN(PW,compatible_domain)(__isl_keep EL *el,117 __isl_keep isl_set *set)118{119 isl_bool ok;120 isl_space *el_space, *set_space;121 122 if (!set || !el)123 return isl_bool_error;124 set_space = isl_set_get_space(set);125 el_space = FN(EL,get_space)(el);126 ok = isl_space_is_domain_internal(set_space, el_space);127 isl_space_free(el_space);128 isl_space_free(set_space);129 return ok;130}131 132/* Check that the space of "set" corresponds to that of the domain of "el".133 */134static isl_stat FN(PW,check_compatible_domain)(__isl_keep EL *el,135 __isl_keep isl_set *set)136{137 isl_bool ok;138 139 ok = FN(PW,compatible_domain)(el, set);140 if (ok < 0)141 return isl_stat_error;142 if (!ok)143 isl_die(isl_set_get_ctx(set), isl_error_invalid,144 "incompatible spaces", return isl_stat_error);145 146 return isl_stat_ok;147}148 149__isl_give PW *FN(PW,alloc)(OPT_TYPE_PARAM_FIRST150 __isl_take isl_set *set, __isl_take EL *el)151{152 PW *pw;153 154 if (FN(PW,check_compatible_domain)(el, set) < 0)155 goto error;156 157 pw = FN(PW,alloc_size)(FN(EL,get_space)(el) OPT_TYPE_ARG(NO_LOC), 1);158 159 return FN(PW,add_piece)(pw, set, el);160error:161 isl_set_free(set);162 FN(EL,free)(el);163 return NULL;164}165 166__isl_give PW *FN(PW,dup)(__isl_keep PW *pw)167{168 int i;169 PW *dup;170 171 if (!pw)172 return NULL;173 174 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim)175 OPT_TYPE_ARG(pw->), pw->n);176 if (!dup)177 return NULL;178 179 for (i = 0; i < pw->n; ++i)180 dup = FN(PW,add_dup_piece)(dup, isl_set_copy(pw->p[i].set),181 FN(EL,copy)(pw->p[i].FIELD));182 183 return dup;184}185 186__isl_give PW *FN(PW,cow)(__isl_take PW *pw)187{188 if (!pw)189 return NULL;190 191 if (pw->ref == 1)192 return pw;193 pw->ref--;194 return FN(PW,dup)(pw);195}196 197__isl_give PW *FN(PW,copy)(__isl_keep PW *pw)198{199 if (!pw)200 return NULL;201 202 pw->ref++;203 return pw;204}205 206__isl_null PW *FN(PW,free)(__isl_take PW *pw)207{208 int i;209 210 if (!pw)211 return NULL;212 if (--pw->ref > 0)213 return NULL;214 215 for (i = 0; i < pw->n; ++i) {216 isl_set_free(pw->p[i].set);217 FN(EL,free)(pw->p[i].FIELD);218 }219 isl_space_free(pw->dim);220 free(pw);221 222 return NULL;223}224 225/* Return the space of "pw".226 */227__isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw)228{229 return pw ? pw->dim : NULL;230}231 232__isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)233{234 return isl_space_copy(FN(PW,peek_space)(pw));235}236 237/* Return the space of "pw".238 * This may be either a copy or the space itself239 * if there is only one reference to "pw".240 * This allows the space to be modified inplace241 * if both the piecewise expression and its space have only a single reference.242 * The caller is not allowed to modify "pw" between this call and243 * a subsequent call to isl_pw_*_restore_*.244 * The only exception is that isl_pw_*_free can be called instead.245 */246static __isl_give isl_space *FN(PW,take_space)(__isl_keep PW *pw)247{248 isl_space *space;249 250 if (!pw)251 return NULL;252 if (pw->ref != 1)253 return FN(PW,get_space)(pw);254 space = pw->dim;255 pw->dim = NULL;256 return space;257}258 259/* Set the space of "pw" to "space", where the space of "pw" may be missing260 * due to a preceding call to isl_pw_*_take_space.261 * However, in this case, "pw" only has a single reference and262 * then the call to isl_pw_*_cow has no effect.263 */264static __isl_give PW *FN(PW,restore_space)(__isl_take PW *pw,265 __isl_take isl_space *space)266{267 if (!pw || !space)268 goto error;269 270 if (pw->dim == space) {271 isl_space_free(space);272 return pw;273 }274 275 pw = FN(PW,cow)(pw);276 if (!pw)277 goto error;278 isl_space_free(pw->dim);279 pw->dim = space;280 281 return pw;282error:283 FN(PW,free)(pw);284 isl_space_free(space);285 return NULL;286}287 288/* Check that "pos" is a valid position for a cell in "pw".289 */290static isl_stat FN(PW,check_pos)(__isl_keep PW *pw, int pos)291{292 if (!pw)293 return isl_stat_error;294 if (pos < 0 || pos >= pw->n)295 isl_die(FN(PW,get_ctx)(pw), isl_error_internal,296 "position out of bounds", return isl_stat_error);297 return isl_stat_ok;298}299 300/* Return the cell at position "pos" in "pw".301 */302static __isl_keep isl_set *FN(PW,peek_domain_at)(__isl_keep PW *pw, int pos)303{304 if (FN(PW,check_pos)(pw, pos) < 0)305 return NULL;306 return pw->p[pos].set;307}308 309/* Return a copy of the cell at position "pos" in "pw".310 */311static __isl_give isl_set *FN(PW,get_domain_at)(__isl_keep PW *pw, int pos)312{313 return isl_set_copy(FN(PW,peek_domain_at)(pw, pos));314}315 316/* Return the cell at position "pos" in "pw".317 * This may be either a copy or the cell itself318 * if there is only one reference to "pw".319 * This allows the cell to be modified inplace320 * if both the piecewise expression and this cell321 * have only a single reference.322 * The caller is not allowed to modify "pw" between this call and323 * the subsequent call to isl_pw_*_restore_domain_at.324 * The only exception is that isl_pw_*_free can be called instead.325 */326static __isl_give isl_set *FN(PW,take_domain_at)(__isl_keep PW *pw, int pos)327{328 isl_set *domain;329 330 if (!pw)331 return NULL;332 if (pw->ref != 1)333 return FN(PW,get_domain_at)(pw, pos);334 if (FN(PW,check_pos)(pw, pos) < 0)335 return NULL;336 domain = pw->p[pos].set;337 pw->p[pos].set = NULL;338 return domain;339}340 341/* Set the cell at position "pos" in "pw" to "el",342 * where this cell may be missing343 * due to a preceding call to isl_pw_*_take_domain_at.344 * However, in this case, "pw" only has a single reference and345 * then the call to isl_pw_*_cow has no effect.346 */347static __isl_give PW *FN(PW,restore_domain_at)(__isl_take PW *pw, int pos,348 __isl_take isl_set *domain)349{350 if (FN(PW,check_pos)(pw, pos) < 0 || !domain)351 goto error;352 353 if (pw->p[pos].set == domain) {354 isl_set_free(domain);355 return pw;356 }357 358 pw = FN(PW,cow)(pw);359 if (!pw)360 goto error;361 isl_set_free(pw->p[pos].set);362 pw->p[pos].set = domain;363 364 return pw;365error:366 FN(PW,free)(pw);367 isl_set_free(domain);368 return NULL;369}370 371/* Return the base expression associated to372 * the cell at position "pos" in "pw".373 */374__isl_keep EL *FN(PW,peek_base_at)(__isl_keep PW *pw, int pos)375{376 if (FN(PW,check_pos)(pw, pos) < 0)377 return NULL;378 return pw->p[pos].FIELD;379}380 381/* Return a copy of the base expression associated to382 * the cell at position "pos" in "pw".383 */384static __isl_give EL *FN(PW,get_base_at)(__isl_keep PW *pw, int pos)385{386 return FN(EL,copy)(FN(PW,peek_base_at)(pw, pos));387}388 389/* Return the base expression associated to390 * the cell at position "pos" in "pw".391 * This may be either a copy or the base expression itself392 * if there is only one reference to "pw".393 * This allows the base expression to be modified inplace394 * if both the piecewise expression and this base expression395 * have only a single reference.396 * The caller is not allowed to modify "pw" between this call and397 * a subsequent call to isl_pw_*_restore_*.398 * The only exception is that isl_pw_*_free can be called instead.399 */400static __isl_give EL *FN(PW,take_base_at)(__isl_keep PW *pw, int pos)401{402 EL *el;403 404 if (!pw)405 return NULL;406 if (pw->ref != 1)407 return FN(PW,get_base_at)(pw, pos);408 if (FN(PW,check_pos)(pw, pos) < 0)409 return NULL;410 el = pw->p[pos].FIELD;411 pw->p[pos].FIELD = NULL;412 return el;413}414 415/* Set the base expression associated to416 * the cell at position "pos" in "pw" to "el",417 * where this base expression may be missing418 * due to a preceding call to isl_pw_*_take_base_at.419 * However, in this case, "pw" only has a single reference and420 * then the call to isl_pw_*_cow has no effect.421 * If "inplace" is set, then replacing the base expression by "el"422 * is known not to change the meaning of "pw". It can therefore be replaced423 * in all references to "pw".424 */425static __isl_give PW *FN(PW,restore_base_at_)(__isl_take PW *pw, int pos,426 __isl_take EL *el, int inplace)427{428 if (FN(PW,check_pos)(pw, pos) < 0 || !el)429 goto error;430 431 if (pw->p[pos].FIELD == el) {432 FN(EL,free)(el);433 return pw;434 }435 436 if (!inplace)437 pw = FN(PW,cow)(pw);438 if (!pw)439 goto error;440 FN(EL,free)(pw->p[pos].FIELD);441 pw->p[pos].FIELD = el;442 443 return pw;444error:445 FN(PW,free)(pw);446 FN(EL,free)(el);447 return NULL;448}449 450/* Set the base expression associated to451 * the cell at position "pos" in "pw" to "el",452 * where this base expression may be missing453 * due to a preceding call to isl_pw_*_take_base_at.454 */455static __isl_give PW *FN(PW,restore_base_at)(__isl_take PW *pw, int pos,456 __isl_take EL *el)457{458 return FN(PW,restore_base_at_)(pw, pos, el, 0);459}460 461/* Set the base expression associated to462 * the cell at position "pos" in "pw" to "el",463 * where this base expression may be missing464 * due to a preceding call to isl_pw_*_take_base_at.465 * Furthermore, replacing the base expression by "el"466 * is known not to change the meaning of "pw".467 */468static __isl_give PW *FN(PW,restore_base_at_inplace)(__isl_take PW *pw, int pos,469 __isl_take EL *el)470{471 return FN(PW,restore_base_at_)(pw, pos, el, 1);472}473 474/* Create a piecewise expression with the given base expression on a universe475 * domain.476 */477static __isl_give PW *FN(FN(FN(PW,from),BASE),type_base)(__isl_take EL *el478 OPT_TYPE_PARAM)479{480 isl_set *dom = isl_set_universe(FN(EL,get_domain_space)(el));481 return FN(PW,alloc)(OPT_TYPE_ARG_FIRST(NO_LOC) dom, el);482}483 484/* Create a piecewise expression with the given base expression on a universe485 * domain.486 *487 * If the default value of this piecewise type is zero and488 * if "el" is effectively zero, then create an empty piecewise expression489 * instead.490 */491static __isl_give PW *FN(FN(FN(PW,from),BASE),type)(__isl_take EL *el492 OPT_TYPE_PARAM)493{494 isl_bool is_zero;495 isl_space *space;496 497 if (!DEFAULT_IS_ZERO)498 return FN(FN(FN(PW,from),BASE),type_base)(el499 OPT_TYPE_ARG(NO_LOC));500 is_zero = FN(EL,EL_IS_ZERO)(el);501 if (is_zero < 0)502 goto error;503 if (!is_zero)504 return FN(FN(FN(PW,from),BASE),type_base)(el505 OPT_TYPE_ARG(NO_LOC));506 space = FN(EL,get_space)(el);507 FN(EL,free)(el);508 return FN(PW,ZERO)(space OPT_TYPE_ARG(NO_LOC));509error:510 FN(EL,free)(el);511 return NULL;512}513 514#ifdef HAS_TYPE515/* Create a piecewise expression with the given base expression on a universe516 * domain.517 *518 * Pass along the type as an extra argument for improved uniformity519 * with piecewise types that do not have a fold type.520 */521__isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el)522{523 enum isl_fold type = FN(EL,get_type)(el);524 return FN(FN(FN(PW,from),BASE),type)(el, type);525}526#else527__isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el)528{529 return FN(FN(FN(PW,from),BASE),type)(el);530}531#endif532 533const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type,534 unsigned pos)535{536 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL;537}538 539isl_bool FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,540 unsigned pos)541{542 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : isl_bool_error;543}544 545__isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,546 unsigned pos)547{548 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL;549}550 551isl_bool FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)552{553 return pw ? isl_space_has_tuple_name(pw->dim, type) : isl_bool_error;554}555 556const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)557{558 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;559}560 561isl_bool FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)562{563 return pw ? isl_space_has_tuple_id(pw->dim, type) : isl_bool_error;564}565 566__isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)567{568 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;569}570 571isl_bool FN(PW,IS_ZERO)(__isl_keep PW *pw)572{573 if (!pw)574 return isl_bool_error;575 576 return isl_bool_ok(pw->n == 0);577}578 579static __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,580 __isl_take isl_reordering *exp)581{582 int i;583 isl_size n;584 585 n = FN(PW,n_piece)(pw);586 if (n < 0 || !exp)587 goto error;588 589 for (i = 0; i < n; ++i) {590 isl_set *domain;591 EL *el;592 593 domain = FN(PW,take_domain_at)(pw, i);594 domain = isl_set_realign(domain, isl_reordering_copy(exp));595 pw = FN(PW,restore_domain_at)(pw, i, domain);596 597 el = FN(PW,take_base_at)(pw, i);598 el = FN(EL,realign_domain)(el, isl_reordering_copy(exp));599 pw = FN(PW,restore_base_at)(pw, i, el);600 }601 602 pw = FN(PW,reset_domain_space)(pw, isl_reordering_get_space(exp));603 604 isl_reordering_free(exp);605 return pw;606error:607 isl_reordering_free(exp);608 FN(PW,free)(pw);609 return NULL;610}611 612#undef TYPE613#define TYPE PW614 615#include "isl_check_named_params_templ.c"616 617/* Align the parameters of "pw" to those of "model".618 */619__isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)620{621 isl_ctx *ctx;622 isl_bool equal_params;623 624 if (!pw || !model)625 goto error;626 627 ctx = isl_space_get_ctx(model);628 if (!isl_space_has_named_params(model))629 isl_die(ctx, isl_error_invalid,630 "model has unnamed parameters", goto error);631 if (FN(PW,check_named_params)(pw) < 0)632 goto error;633 equal_params = isl_space_has_equal_params(pw->dim, model);634 if (equal_params < 0)635 goto error;636 if (!equal_params) {637 isl_space *space;638 isl_reordering *exp;639 640 space = FN(PW,get_domain_space)(pw);641 exp = isl_parameter_alignment_reordering(space, model);642 isl_space_free(space);643 pw = FN(PW,realign_domain)(pw, exp);644 }645 646 isl_space_free(model);647 return pw;648error:649 isl_space_free(model);650 FN(PW,free)(pw);651 return NULL;652}653 654#undef TYPE655#define TYPE PW656 657static658#include "isl_align_params_bin_templ.c"659 660#undef SUFFIX661#define SUFFIX set662#undef ARG1663#define ARG1 PW664#undef ARG2665#define ARG2 isl_set666 667static668#include "isl_align_params_templ.c"669 670#undef TYPE671#define TYPE PW672 673#include "isl_type_has_equal_space_bin_templ.c"674#include "isl_type_check_equal_space_templ.c"675 676/* Private version of "union_add". For isl_pw_qpolynomial and677 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".678 */679static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)680{681 int i, j, n;682 struct PW *res;683 isl_ctx *ctx;684 isl_set *set;685 686 if (FN(PW,align_params_bin)(&pw1, &pw2) < 0)687 goto error;688 689 ctx = isl_space_get_ctx(pw1->dim);690 if (!OPT_EQUAL_TYPES(pw1->, pw2->))691 isl_die(ctx, isl_error_invalid,692 "fold types don't match", goto error);693 if (FN(PW,check_equal_space)(pw1, pw2) < 0)694 goto error;695 696 if (FN(PW,IS_ZERO)(pw1)) {697 FN(PW,free)(pw1);698 return pw2;699 }700 701 if (FN(PW,IS_ZERO)(pw2)) {702 FN(PW,free)(pw2);703 return pw1;704 }705 706 n = (pw1->n + 1) * (pw2->n + 1);707 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim)708 OPT_TYPE_ARG(pw1->), n);709 710 for (i = 0; i < pw1->n; ++i) {711 set = isl_set_copy(pw1->p[i].set);712 for (j = 0; j < pw2->n; ++j) {713 struct isl_set *common;714 EL *sum;715 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),716 isl_set_copy(pw2->p[j].set));717 if (isl_set_plain_is_empty(common)) {718 isl_set_free(common);719 continue;720 }721 set = isl_set_subtract(set,722 isl_set_copy(pw2->p[j].set));723 724 sum = FN(EL,add_on_domain)(common,725 FN(EL,copy)(pw1->p[i].FIELD),726 FN(EL,copy)(pw2->p[j].FIELD));727 728 res = FN(PW,add_piece)(res, common, sum);729 }730 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));731 }732 733 for (j = 0; j < pw2->n; ++j) {734 set = isl_set_copy(pw2->p[j].set);735 for (i = 0; i < pw1->n; ++i)736 set = isl_set_subtract(set,737 isl_set_copy(pw1->p[i].set));738 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));739 }740 741 FN(PW,free)(pw1);742 FN(PW,free)(pw2);743 744 return res;745error:746 FN(PW,free)(pw1);747 FN(PW,free)(pw2);748 return NULL;749}750 751#if !DEFAULT_IS_ZERO752 753/* Compute the sum of "pw1" and "pw2 on the union of their domains,754 * with the actual sum on the shared domain and755 * the defined expression on the symmetric difference of the domains.756 *757 * This function is only defined for object types that do not have758 * a default zero value. For other object types, this function759 * is simply called "add".760 */761__isl_give PW *FN(PW,union_add)(__isl_take PW *pw1, __isl_take PW *pw2)762{763 return FN(PW,union_add_)(pw1, pw2);764}765 766#endif767 768/* This function is currently only used from isl_aff.c769 */770static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,771 __isl_take PW *pw2, __isl_take isl_space *space,772 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))773 __attribute__ ((unused));774 775/* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.776 * The result of "fn" (and therefore also of this function) lives in "space".777 */778static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,779 __isl_take PW *pw2, __isl_take isl_space *space,780 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))781{782 int i, j, n;783 PW *res = NULL;784 785 if (!pw1 || !pw2)786 goto error;787 788 n = pw1->n * pw2->n;789 res = FN(PW,alloc_size)(isl_space_copy(space) OPT_TYPE_ARG(pw1->), n);790 791 for (i = 0; i < pw1->n; ++i) {792 for (j = 0; j < pw2->n; ++j) {793 isl_set *common;794 EL *res_ij;795 int empty;796 797 common = isl_set_intersect(798 isl_set_copy(pw1->p[i].set),799 isl_set_copy(pw2->p[j].set));800 empty = isl_set_plain_is_empty(common);801 if (empty < 0 || empty) {802 isl_set_free(common);803 if (empty < 0)804 goto error;805 continue;806 }807 808 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),809 FN(EL,copy)(pw2->p[j].FIELD));810 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));811 812 res = FN(PW,add_piece)(res, common, res_ij);813 }814 }815 816 isl_space_free(space);817 FN(PW,free)(pw1);818 FN(PW,free)(pw2);819 return res;820error:821 isl_space_free(space);822 FN(PW,free)(pw1);823 FN(PW,free)(pw2);824 FN(PW,free)(res);825 return NULL;826}827 828/* This function is currently only used from isl_aff.c829 */830static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,831 __isl_take PW *pw2,832 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))833 __attribute__ ((unused));834 835/* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.836 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".837 */838static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,839 __isl_take PW *pw2,840 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))841{842 isl_space *space;843 844 if (FN(PW,check_equal_space)(pw1, pw2) < 0)845 goto error;846 847 space = isl_space_copy(pw1->dim);848 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);849error:850 FN(PW,free)(pw1);851 FN(PW,free)(pw2);852 return NULL;853}854 855/* Return the parameter domain of "pw".856 */857__isl_give isl_set *FN(PW,params)(__isl_take PW *pw)858{859 return isl_set_params(FN(PW,domain)(pw));860}861 862__isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)863{864 int i;865 isl_set *dom;866 867 if (!pw)868 return NULL;869 870 dom = isl_set_empty(FN(PW,get_domain_space)(pw));871 for (i = 0; i < pw->n; ++i)872 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));873 874 FN(PW,free)(pw);875 876 return dom;877}878 879/* Exploit the equalities in the domain of piece "i" of "pw"880 * to simplify the associated function.881 * If the domain of piece "i" is empty, then remove it entirely,882 * replacing it with the final piece.883 */884static __isl_give PW *FN(PW,exploit_equalities_and_remove_if_empty)(885 __isl_take PW *pw, int i)886{887 EL *el;888 isl_set *domain;889 isl_basic_set *aff;890 int empty;891 892 domain = FN(PW,peek_domain_at)(pw, i);893 empty = isl_set_plain_is_empty(domain);894 if (empty < 0)895 return FN(PW,free)(pw);896 if (empty) {897 isl_set_free(pw->p[i].set);898 FN(EL,free)(pw->p[i].FIELD);899 if (i != pw->n - 1)900 pw->p[i] = pw->p[pw->n - 1];901 pw->n--;902 903 return pw;904 }905 906 aff = isl_set_affine_hull(FN(PW,get_domain_at)(pw, i));907 el = FN(PW,take_base_at)(pw, i);908 el = FN(EL,substitute_equalities)(el, aff);909 pw = FN(PW,restore_base_at_inplace)(pw, i, el);910 911 return pw;912}913 914/* Restrict the domain of "pw" by combining each cell915 * with "set" through a call to "fn", where "fn" may be916 * isl_set_intersect, isl_set_intersect_params, isl_set_intersect_factor_domain,917 * isl_set_intersect_factor_range or isl_set_subtract.918 */919static __isl_give PW *FN(PW,restrict_domain)(__isl_take PW *pw,920 __isl_take isl_set *set,921 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,922 __isl_take isl_set *set2))923{924 int i;925 isl_size n;926 927 FN(PW,align_params_set)(&pw, &set);928 n = FN(PW,n_piece)(pw);929 if (n < 0 || !set)930 goto error;931 932 for (i = n - 1; i >= 0; --i) {933 isl_set *domain;934 935 domain = FN(PW,take_domain_at)(pw, i);936 domain = fn(domain, isl_set_copy(set));937 pw = FN(PW,restore_domain_at)(pw, i, domain);938 pw = FN(PW,exploit_equalities_and_remove_if_empty)(pw, i);939 }940 941 isl_set_free(set);942 return pw;943error:944 isl_set_free(set);945 FN(PW,free)(pw);946 return NULL;947}948 949__isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,950 __isl_take isl_set *context)951{952 return FN(PW,restrict_domain)(pw, context, &isl_set_intersect);953}954 955/* Intersect the domain of "pw" with the parameter domain "context".956 */957__isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,958 __isl_take isl_set *context)959{960 return FN(PW,restrict_domain)(pw, context, &isl_set_intersect_params);961}962 963/* Given a piecewise expression "pw" with domain in a space [A -> B] and964 * a set in the space A, intersect the domain with the set.965 */966__isl_give PW *FN(PW,intersect_domain_wrapped_domain)(__isl_take PW *pw,967 __isl_take isl_set *set)968{969 return FN(PW,restrict_domain)(pw, set,970 &isl_set_intersect_factor_domain);971}972 973/* Given a piecewise expression "pw" with domain in a space [A -> B] and974 * a set in the space B, intersect the domain with the set.975 */976__isl_give PW *FN(PW,intersect_domain_wrapped_range)(__isl_take PW *pw,977 __isl_take isl_set *set)978{979 return FN(PW,restrict_domain)(pw, set, &isl_set_intersect_factor_range);980}981 982/* Subtract "domain' from the domain of "pw".983 */984__isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw,985 __isl_take isl_set *domain)986{987 return FN(PW,restrict_domain)(pw, domain, &isl_set_subtract);988}989 990/* Return -1 if the piece "p1" should be sorted before "p2"991 * and 1 if it should be sorted after "p2".992 * Return 0 if they do not need to be sorted in a specific order.993 *994 * The two pieces are compared on the basis of their function value expressions.995 */996static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg)997{998 struct FN(PW,piece) const *pc1 = p1;999 struct FN(PW,piece) const *pc2 = p2;1000 1001 return FN(EL,plain_cmp)(pc1->FIELD, pc2->FIELD);1002}1003 1004/* Sort the pieces of "pw" according to their function value1005 * expressions and then combine pairs of adjacent pieces with1006 * the same such expression.1007 *1008 * The sorting is performed in place because it does not1009 * change the meaning of "pw", but care needs to be1010 * taken not to change any possible other copies of "pw"1011 * in case anything goes wrong.1012 */1013static __isl_give PW *FN(PW,sort_unique)(__isl_take PW *pw)1014{1015 int i, j;1016 isl_set *set;1017 1018 if (!pw)1019 return NULL;1020 if (pw->n <= 1)1021 return pw;1022 if (isl_sort(pw->p, pw->n, sizeof(pw->p[0]),1023 &FN(PW,sort_field_cmp), NULL) < 0)1024 return FN(PW,free)(pw);1025 for (i = pw->n - 1; i >= 1; --i) {1026 isl_bool equal;1027 EL *el, *el_prev;1028 isl_set *set_prev;1029 1030 el = FN(PW,peek_base_at)(pw, i);1031 el_prev = FN(PW,peek_base_at)(pw, i - 1);1032 equal = FN(EL,plain_is_equal)(el, el_prev);1033 if (equal < 0)1034 return FN(PW,free)(pw);1035 if (!equal)1036 continue;1037 set = FN(PW,get_domain_at)(pw, i);1038 set_prev = FN(PW,get_domain_at)(pw, i - 1);1039 set = isl_set_union(set_prev, set);1040 if (!set)1041 return FN(PW,free)(pw);1042 isl_set_free(pw->p[i].set);1043 FN(EL,free)(pw->p[i].FIELD);1044 isl_set_free(pw->p[i - 1].set);1045 pw->p[i - 1].set = set;1046 for (j = i + 1; j < pw->n; ++j)1047 pw->p[j - 1] = pw->p[j];1048 pw->n--;1049 }1050 1051 return pw;1052}1053 1054/* Compute the gist of "pw" with respect to the domain constraints1055 * of "context" for the case where the domain of the last element1056 * of "pw" is equal to "context".1057 * Compute the gist of this element, replace1058 * its domain by the universe and drop all other elements1059 * as their domains are necessarily disjoint from "context".1060 */1061static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw,1062 __isl_take isl_set *context)1063{1064 int i;1065 isl_space *space;1066 EL *el;1067 1068 for (i = 0; i < pw->n - 1; ++i) {1069 isl_set_free(pw->p[i].set);1070 FN(EL,free)(pw->p[i].FIELD);1071 }1072 pw->p[0].FIELD = pw->p[pw->n - 1].FIELD;1073 pw->p[0].set = pw->p[pw->n - 1].set;1074 pw->n = 1;1075 1076 space = isl_set_get_space(context);1077 el = FN(PW,take_base_at)(pw, 0);1078 el = FN(EL,gist)(el, context);1079 pw = FN(PW,restore_base_at)(pw, 0, el);1080 context = isl_set_universe(space);1081 pw = FN(PW,restore_domain_at)(pw, 0, context);1082 1083 return pw;1084}1085 1086/* Compute the gist of "pw" with respect to the domain constraints1087 * of "context".1088 * Call "fn_dom" to compute the gist of the domains and1089 * "intersect_context" to intersect the domain with the context.1090 *1091 * If the piecewise expression is empty or the context is the universe,1092 * then nothing can be simplified.1093 * If "pw" has a single domain and it is equal to "context",1094 * then simply replace the domain by the universe.1095 * Combine duplicate function value expressions first1096 * to increase the chance of "pw" having a single domain.1097 */1098static __isl_give PW *FN(PW,gist_fn)(__isl_take PW *pw,1099 __isl_take isl_set *context,1100 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,1101 __isl_take isl_basic_set *bset),1102 __isl_give isl_set *intersect_context(__isl_take isl_set *set,1103 __isl_take isl_set *context))1104{1105 int i;1106 int is_universe;1107 isl_basic_set *hull = NULL;1108 1109 pw = FN(PW,sort_unique)(pw);1110 if (!pw || !context)1111 goto error;1112 1113 if (pw->n == 0) {1114 isl_set_free(context);1115 return pw;1116 }1117 1118 is_universe = isl_set_plain_is_universe(context);1119 if (is_universe < 0)1120 goto error;1121 if (is_universe) {1122 isl_set_free(context);1123 return pw;1124 }1125 1126 FN(PW,align_params_set)(&pw, &context);1127 1128 pw = FN(PW,cow)(pw);1129 if (!pw)1130 goto error;1131 1132 if (pw->n == 1) {1133 int equal;1134 1135 equal = isl_set_plain_is_equal(pw->p[0].set, context);1136 if (equal < 0)1137 goto error;1138 if (equal)1139 return FN(PW,gist_last)(pw, context);1140 }1141 1142 context = isl_set_compute_divs(context);1143 hull = isl_set_simple_hull(isl_set_copy(context));1144 1145 for (i = pw->n - 1; i >= 0; --i) {1146 isl_set *set_i;1147 EL *el;1148 int empty;1149 1150 if (i == pw->n - 1) {1151 int equal;1152 equal = isl_set_plain_is_equal(pw->p[i].set, context);1153 if (equal < 0)1154 goto error;1155 if (equal) {1156 isl_basic_set_free(hull);1157 return FN(PW,gist_last)(pw, context);1158 }1159 }1160 set_i = FN(PW,get_domain_at)(pw, i);1161 set_i = intersect_context(set_i, isl_set_copy(context));1162 empty = isl_set_plain_is_empty(set_i);1163 el = FN(PW,take_base_at)(pw, i);1164 el = FN(EL,gist)(el, set_i);1165 pw = FN(PW,restore_base_at)(pw, i, el);1166 set_i = FN(PW,take_domain_at)(pw, i);1167 set_i = fn_dom(set_i, isl_basic_set_copy(hull));1168 pw = FN(PW,restore_domain_at)(pw, i, set_i);1169 if (empty < 0 || !pw)1170 goto error;1171 if (empty) {1172 isl_set_free(pw->p[i].set);1173 FN(EL,free)(pw->p[i].FIELD);1174 if (i != pw->n - 1)1175 pw->p[i] = pw->p[pw->n - 1];1176 pw->n--;1177 }1178 }1179 1180 isl_basic_set_free(hull);1181 isl_set_free(context);1182 1183 return pw;1184error:1185 FN(PW,free)(pw);1186 isl_basic_set_free(hull);1187 isl_set_free(context);1188 return NULL;1189}1190 1191__isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)1192{1193 return FN(PW,gist_fn)(pw, context, &isl_set_gist_basic_set,1194 &isl_set_intersect);1195}1196 1197__isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,1198 __isl_take isl_set *context)1199{1200 return FN(PW,gist_fn)(pw, context, &isl_set_gist_params_basic_set,1201 &isl_set_intersect_params);1202}1203 1204/* Coalesce the domains of "pw".1205 *1206 * Prior to the actual coalescing, first sort the pieces such that1207 * pieces with the same function value expression are combined1208 * into a single piece, the combined domain of which can then1209 * be coalesced.1210 */1211__isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)1212{1213 int i;1214 isl_size n;1215 1216 pw = FN(PW,sort_unique)(pw);1217 n = FN(PW,n_piece)(pw);1218 if (n < 0)1219 return FN(PW,free)(pw);1220 1221 for (i = 0; i < n; ++i) {1222 pw->p[i].set = isl_set_coalesce(pw->p[i].set);1223 if (!pw->p[i].set)1224 goto error;1225 }1226 1227 return pw;1228error:1229 FN(PW,free)(pw);1230 return NULL;1231}1232 1233isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)1234{1235 return pw ? isl_space_get_ctx(pw->dim) : NULL;1236}1237 1238isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,1239 unsigned first, unsigned n)1240{1241 int i;1242 enum isl_dim_type set_type;1243 1244 if (!pw)1245 return isl_bool_error;1246 if (pw->n == 0 || n == 0)1247 return isl_bool_false;1248 1249 set_type = type == isl_dim_in ? isl_dim_set : type;1250 1251 for (i = 0; i < pw->n; ++i) {1252 isl_bool involves = FN(EL,involves_dims)(pw->p[i].FIELD,1253 type, first, n);1254 if (involves < 0 || involves)1255 return involves;1256 involves = isl_set_involves_dims(pw->p[i].set,1257 set_type, first, n);1258 if (involves < 0 || involves)1259 return involves;1260 }1261 return isl_bool_false;1262}1263 1264__isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,1265 enum isl_dim_type type, unsigned pos, const char *s)1266{1267 isl_space *space;1268 1269 space = FN(PW,get_space)(pw);1270 space = isl_space_set_dim_name(space, type, pos, s);1271 return FN(PW,reset_space)(pw, space);1272}1273 1274__isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,1275 enum isl_dim_type type, unsigned first, unsigned n)1276{1277 int i;1278 isl_size n_piece;1279 enum isl_dim_type set_type;1280 isl_space *space;1281 1282 n_piece = FN(PW,n_piece)(pw);1283 if (n_piece < 0)1284 return FN(PW,free)(pw);1285 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))1286 return pw;1287 1288 set_type = type == isl_dim_in ? isl_dim_set : type;1289 1290 space = FN(PW,take_space)(pw);1291 space = isl_space_drop_dims(space, type, first, n);1292 pw = FN(PW,restore_space)(pw, space);1293 for (i = 0; i < n_piece; ++i) {1294 isl_set *domain;1295 EL *el;1296 1297 el = FN(PW,take_base_at)(pw, i);1298 el = FN(EL,drop_dims)(el, type, first, n);1299 pw = FN(PW,restore_base_at)(pw, i, el);1300 if (type == isl_dim_out)1301 continue;1302 domain = FN(PW,take_domain_at)(pw, i);1303 domain = isl_set_drop(domain, set_type, first, n);1304 pw = FN(PW,restore_domain_at)(pw, i, domain);1305 }1306 1307 return pw;1308}1309 1310/* This function is very similar to drop_dims.1311 * The only difference is that the cells may still involve1312 * the specified dimensions. They are removed using1313 * isl_set_project_out instead of isl_set_drop.1314 */1315__isl_give PW *FN(PW,project_out)(__isl_take PW *pw,1316 enum isl_dim_type type, unsigned first, unsigned n)1317{1318 int i;1319 isl_size n_piece;1320 enum isl_dim_type set_type;1321 isl_space *space;1322 1323 n_piece = FN(PW,n_piece)(pw);1324 if (n_piece < 0)1325 return FN(PW,free)(pw);1326 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))1327 return pw;1328 1329 set_type = type == isl_dim_in ? isl_dim_set : type;1330 1331 space = FN(PW,take_space)(pw);1332 space = isl_space_drop_dims(space, type, first, n);1333 pw = FN(PW,restore_space)(pw, space);1334 for (i = 0; i < n_piece; ++i) {1335 isl_set *domain;1336 EL *el;1337 1338 domain = FN(PW,take_domain_at)(pw, i);1339 domain = isl_set_project_out(domain, set_type, first, n);1340 pw = FN(PW,restore_domain_at)(pw, i, domain);1341 el = FN(PW,take_base_at)(pw, i);1342 el = FN(EL,drop_dims)(el, type, first, n);1343 pw = FN(PW,restore_base_at)(pw, i, el);1344 }1345 1346 return pw;1347}1348 1349/* Project the domain of pw onto its parameter space.1350 */1351__isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)1352{1353 isl_space *space;1354 isl_size n;1355 1356 n = FN(PW,dim)(pw, isl_dim_in);1357 if (n < 0)1358 return FN(PW,free)(pw);1359 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);1360 space = FN(PW,get_domain_space)(pw);1361 space = isl_space_params(space);1362 pw = FN(PW,reset_domain_space)(pw, space);1363 return pw;1364}1365 1366/* Drop all parameters not referenced by "pw".1367 */1368__isl_give PW *FN(PW,drop_unused_params)(__isl_take PW *pw)1369{1370 isl_size n;1371 int i;1372 1373 if (FN(PW,check_named_params)(pw) < 0)1374 return FN(PW,free)(pw);1375 1376 n = FN(PW,dim)(pw, isl_dim_param);1377 if (n < 0)1378 return FN(PW,free)(pw);1379 for (i = n - 1; i >= 0; i--) {1380 isl_bool involves;1381 1382 involves = FN(PW,involves_dims)(pw, isl_dim_param, i, 1);1383 if (involves < 0)1384 return FN(PW,free)(pw);1385 if (!involves)1386 pw = FN(PW,drop_dims)(pw, isl_dim_param, i, 1);1387 }1388 1389 return pw;1390}1391 1392isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)1393{1394 return isl_space_dim(FN(PW,peek_space)(pw), type);1395}1396 1397__isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)1398{1399 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;1400}1401 1402/* Return the position of the dimension of the given type and name1403 * in "pw".1404 * Return -1 if no such dimension can be found.1405 */1406int FN(PW,find_dim_by_name)(__isl_keep PW *pw,1407 enum isl_dim_type type, const char *name)1408{1409 if (!pw)1410 return -1;1411 return isl_space_find_dim_by_name(pw->dim, type, name);1412}1413 1414/* Return the position of the dimension of the given type and identifier1415 * in "pw".1416 * Return -1 if no such dimension can be found.1417 */1418static int FN(PW,find_dim_by_id)(__isl_keep PW *pw,1419 enum isl_dim_type type, __isl_keep isl_id *id)1420{1421 isl_space *space;1422 1423 space = FN(PW,peek_space)(pw);1424 return isl_space_find_dim_by_id(space, type, id);1425}1426 1427/* Does the piecewise expression "pw" depend in any way1428 * on the parameter with identifier "id"?1429 */1430isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id)1431{1432 int pos;1433 1434 if (!pw || !id)1435 return isl_bool_error;1436 if (pw->n == 0)1437 return isl_bool_false;1438 1439 pos = FN(PW,find_dim_by_id)(pw, isl_dim_param, id);1440 if (pos < 0)1441 return isl_bool_false;1442 return FN(PW,involves_dims)(pw, isl_dim_param, pos, 1);1443}1444 1445/* Reset the space of "pw". Since we don't know if the elements1446 * represent the spaces themselves or their domains, we pass along1447 * both when we call their reset_space_and_domain.1448 */1449static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,1450 __isl_take isl_space *space, __isl_take isl_space *domain)1451{1452 int i;1453 isl_size n;1454 1455 n = FN(PW,n_piece)(pw);1456 if (n < 0 || !space || !domain)1457 goto error;1458 1459 for (i = 0; i < n; ++i) {1460 isl_set *set;1461 EL *el;1462 1463 set = FN(PW,take_domain_at)(pw, i);1464 set = isl_set_reset_space(set, isl_space_copy(domain));1465 pw = FN(PW,restore_domain_at)(pw, i, set);1466 el = FN(PW,take_base_at)(pw, i);1467 el = FN(EL,reset_space_and_domain)(el,1468 isl_space_copy(space), isl_space_copy(domain));1469 pw = FN(PW,restore_base_at)(pw, i, el);1470 }1471 1472 isl_space_free(domain);1473 1474 pw = FN(PW,restore_space)(pw, space);1475 1476 return pw;1477error:1478 isl_space_free(domain);1479 isl_space_free(space);1480 FN(PW,free)(pw);1481 return NULL;1482}1483 1484__isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,1485 __isl_take isl_space *domain)1486{1487 isl_space *space;1488 1489 space = isl_space_extend_domain_with_range(isl_space_copy(domain),1490 FN(PW,get_space)(pw));1491 return FN(PW,reset_space_and_domain)(pw, space, domain);1492}1493 1494__isl_give PW *FN(PW,reset_space)(__isl_take PW *pw,1495 __isl_take isl_space *space)1496{1497 isl_space *domain;1498 1499 domain = isl_space_domain(isl_space_copy(space));1500 return FN(PW,reset_space_and_domain)(pw, space, domain);1501}1502 1503__isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type,1504 __isl_take isl_id *id)1505{1506 isl_space *space;1507 1508 pw = FN(PW,cow)(pw);1509 if (!pw)1510 goto error;1511 1512 space = FN(PW,get_space)(pw);1513 space = isl_space_set_tuple_id(space, type, id);1514 1515 return FN(PW,reset_space)(pw, space);1516error:1517 isl_id_free(id);1518 return FN(PW,free)(pw);1519}1520 1521/* Drop the id on the specified tuple.1522 */1523__isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type)1524{1525 isl_space *space;1526 1527 if (!pw)1528 return NULL;1529 if (!FN(PW,has_tuple_id)(pw, type))1530 return pw;1531 1532 pw = FN(PW,cow)(pw);1533 if (!pw)1534 return NULL;1535 1536 space = FN(PW,get_space)(pw);1537 space = isl_space_reset_tuple_id(space, type);1538 1539 return FN(PW,reset_space)(pw, space);1540}1541 1542__isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,1543 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)1544{1545 isl_space *space;1546 1547 space = FN(PW,get_space)(pw);1548 space = isl_space_set_dim_id(space, type, pos, id);1549 return FN(PW,reset_space)(pw, space);1550}1551 1552/* Reset the user pointer on all identifiers of parameters and tuples1553 * of the space of "pw".1554 */1555__isl_give PW *FN(PW,reset_user)(__isl_take PW *pw)1556{1557 isl_space *space;1558 1559 space = FN(PW,get_space)(pw);1560 space = isl_space_reset_user(space);1561 1562 return FN(PW,reset_space)(pw, space);1563}1564 1565isl_size FN(PW,n_piece)(__isl_keep PW *pw)1566{1567 return pw ? pw->n : isl_size_error;1568}1569 1570isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw,1571 isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),1572 void *user)1573{1574 int i;1575 1576 if (!pw)1577 return isl_stat_error;1578 1579 for (i = 0; i < pw->n; ++i)1580 if (fn(isl_set_copy(pw->p[i].set),1581 FN(EL,copy)(pw->p[i].FIELD), user) < 0)1582 return isl_stat_error;1583 1584 return isl_stat_ok;1585}1586 1587/* Does "test" succeed on every cell of "pw"?1588 */1589isl_bool FN(PW,every_piece)(__isl_keep PW *pw,1590 isl_bool (*test)(__isl_keep isl_set *set,1591 __isl_keep EL *el, void *user), void *user)1592{1593 int i;1594 1595 if (!pw)1596 return isl_bool_error;1597 1598 for (i = 0; i < pw->n; ++i) {1599 isl_bool r;1600 1601 r = test(pw->p[i].set, pw->p[i].FIELD, user);1602 if (r < 0 || !r)1603 return r;1604 }1605 1606 return isl_bool_true;1607}1608 1609/* Is "pw" defined over a single universe domain?1610 *1611 * If the default value of this piecewise type is zero,1612 * then a "pw" with a zero number of cells is also accepted1613 * as it represents the default zero value.1614 */1615isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw)1616{1617 isl_size n;1618 1619 n = FN(PW,n_piece)(pw);1620 if (n < 0)1621 return isl_bool_error;1622 if (DEFAULT_IS_ZERO && n == 0)1623 return isl_bool_true;1624 if (n != 1)1625 return isl_bool_false;1626 return isl_set_plain_is_universe(FN(PW,peek_domain_at)(pw, 0));1627}1628 1629/* Return a zero base expression in the same space (and of the same type)1630 * as "pw".1631 */1632static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM)1633{1634 isl_space *space;1635 1636 space = FN(PW,get_space)(pw);1637 FN(PW,free)(pw);1638 return FN(EL,zero_in_space)(space OPT_TYPE_ARG(NO_LOC));1639}1640 1641#ifndef HAS_TYPE1642/* Return a zero base expression in the same space as "pw".1643 */1644static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)1645{1646 return FN(EL,zero_like_type)(pw);1647}1648#else1649/* Return a zero base expression in the same space and of the same type1650 * as "pw".1651 *1652 * Pass along the type as an explicit argument for uniform handling1653 * in isl_*_zero_like_type.1654 */1655static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw)1656{1657 enum isl_fold type;1658 1659 type = FN(PW,get_type)(pw);1660 if (type < 0)1661 goto error;1662 return FN(EL,zero_like_type)(pw, type);1663error:1664 FN(PW,free)(pw);1665 return NULL;1666}1667#endif1668 1669/* Given that "pw" is defined over a single universe domain,1670 * return the base expression associated to this domain.1671 *1672 * If the number of cells is zero, then "pw" is of a piecewise type1673 * with a default zero value and effectively represents zero.1674 * In this case, create a zero base expression in the same space1675 * (and with the same type).1676 * Otherwise, simply extract the associated base expression.1677 */1678__isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw)1679{1680 isl_bool is_total;1681 isl_size n;1682 EL *el;1683 1684 is_total = FN(FN(PW,isa),BASE)(pw);1685 if (is_total < 0)1686 goto error;1687 if (!is_total)1688 isl_die(FN(PW,get_ctx)(pw), isl_error_invalid,1689 "expecting single total function", goto error);1690 n = FN(PW,n_piece)(pw);1691 if (n < 0)1692 goto error;1693 if (n == 0)1694 return FN(EL,zero_like)(pw);1695 el = FN(PW,take_base_at)(pw, 0);1696 FN(PW,free)(pw);1697 return el;1698error:1699 FN(PW,free)(pw);1700 return NULL;1701}1702 1703#ifdef HAS_TYPE1704/* Negate the type of "pw".1705 */1706static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)1707{1708 pw = FN(PW,cow)(pw);1709 if (!pw)1710 return NULL;1711 pw->type = isl_fold_type_negate(pw->type);1712 return pw;1713}1714#else1715/* Negate the type of "pw".1716 * Since "pw" does not have a type, do nothing.1717 */1718static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw)1719{1720 return pw;1721}1722#endif1723 1724/* Multiply the pieces of "pw" by "v" and return the result.1725 */1726__isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v)1727{1728 int i;1729 isl_size n;1730 1731 if (!pw || !v)1732 goto error;1733 1734 if (isl_val_is_one(v)) {1735 isl_val_free(v);1736 return pw;1737 }1738 if (pw && DEFAULT_IS_ZERO && isl_val_is_zero(v)) {1739 PW *zero;1740 isl_space *space = FN(PW,get_space)(pw);1741 zero = FN(PW,ZERO)(space OPT_TYPE_ARG(pw->));1742 FN(PW,free)(pw);1743 isl_val_free(v);1744 return zero;1745 }1746 if (isl_val_is_neg(v))1747 pw = FN(PW,negate_type)(pw);1748 n = FN(PW,n_piece)(pw);1749 if (n < 0)1750 goto error;1751 1752 for (i = 0; i < n; ++i) {1753 EL *el;1754 1755 el = FN(PW,take_base_at)(pw, i);1756 el = FN(EL,scale_val)(el, isl_val_copy(v));1757 pw = FN(PW,restore_base_at)(pw, i, el);1758 }1759 1760 isl_val_free(v);1761 return pw;1762error:1763 isl_val_free(v);1764 FN(PW,free)(pw);1765 return NULL;1766}1767 1768/* Divide the pieces of "pw" by "v" and return the result.1769 */1770__isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v)1771{1772 int i;1773 isl_size n;1774 1775 if (!pw || !v)1776 goto error;1777 1778 if (isl_val_is_one(v)) {1779 isl_val_free(v);1780 return pw;1781 }1782 1783 if (!isl_val_is_rat(v))1784 isl_die(isl_val_get_ctx(v), isl_error_invalid,1785 "expecting rational factor", goto error);1786 if (isl_val_is_zero(v))1787 isl_die(isl_val_get_ctx(v), isl_error_invalid,1788 "cannot scale down by zero", goto error);1789 1790 if (isl_val_is_neg(v))1791 pw = FN(PW,negate_type)(pw);1792 n = FN(PW,n_piece)(pw);1793 if (n < 0)1794 goto error;1795 1796 for (i = 0; i < n; ++i) {1797 EL *el;1798 1799 el = FN(PW,take_base_at)(pw, i);1800 el = FN(EL,scale_down_val)(el, isl_val_copy(v));1801 pw = FN(PW,restore_base_at)(pw, i, el);1802 }1803 1804 isl_val_free(v);1805 return pw;1806error:1807 isl_val_free(v);1808 FN(PW,free)(pw);1809 return NULL;1810}1811 1812/* Apply some normalization to "pw".1813 * In particular, sort the pieces according to their function value1814 * expressions, combining pairs of adjacent pieces with1815 * the same such expression, and then normalize the domains of the pieces.1816 *1817 * We normalize in place, but if anything goes wrong we need1818 * to return NULL, so we need to make sure we don't change the1819 * meaning of any possible other copies of "pw".1820 */1821static __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)1822{1823 int i;1824 isl_set *set;1825 1826 pw = FN(PW,sort_unique)(pw);1827 if (!pw)1828 return NULL;1829 for (i = 0; i < pw->n; ++i) {1830 set = isl_set_normalize(isl_set_copy(pw->p[i].set));1831 if (!set)1832 return FN(PW,free)(pw);1833 isl_set_free(pw->p[i].set);1834 pw->p[i].set = set;1835 }1836 1837 return pw;1838}1839 1840/* Is pw1 obviously equal to pw2?1841 * That is, do they have obviously identical cells and obviously identical1842 * elements on each cell?1843 *1844 * If "pw1" or "pw2" contain any NaNs, then they are considered1845 * not to be the same. A NaN is not equal to anything, not even1846 * to another NaN.1847 */1848isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)1849{1850 int i;1851 isl_bool equal, has_nan;1852 1853 if (!pw1 || !pw2)1854 return isl_bool_error;1855 1856 has_nan = FN(PW,involves_nan)(pw1);1857 if (has_nan >= 0 && !has_nan)1858 has_nan = FN(PW,involves_nan)(pw2);1859 if (has_nan < 0 || has_nan)1860 return isl_bool_not(has_nan);1861 1862 if (pw1 == pw2)1863 return isl_bool_true;1864 equal = FN(PW,has_equal_space)(pw1, pw2);1865 if (equal < 0 || !equal)1866 return equal;1867 1868 pw1 = FN(PW,copy)(pw1);1869 pw2 = FN(PW,copy)(pw2);1870 pw1 = FN(PW,normalize)(pw1);1871 pw2 = FN(PW,normalize)(pw2);1872 if (!pw1 || !pw2)1873 goto error;1874 1875 equal = isl_bool_ok(pw1->n == pw2->n);1876 for (i = 0; equal && i < pw1->n; ++i) {1877 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);1878 if (equal < 0)1879 goto error;1880 if (!equal)1881 break;1882 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);1883 if (equal < 0)1884 goto error;1885 }1886 1887 FN(PW,free)(pw1);1888 FN(PW,free)(pw2);1889 return equal;1890error:1891 FN(PW,free)(pw1);1892 FN(PW,free)(pw2);1893 return isl_bool_error;1894}1895 1896/* Does "pw" involve any NaNs?1897 */1898isl_bool FN(PW,involves_nan)(__isl_keep PW *pw)1899{1900 int i;1901 1902 if (!pw)1903 return isl_bool_error;1904 if (pw->n == 0)1905 return isl_bool_false;1906 1907 for (i = 0; i < pw->n; ++i) {1908 isl_bool has_nan = FN(EL,involves_nan)(pw->p[i].FIELD);1909 if (has_nan < 0 || has_nan)1910 return has_nan;1911 }1912 1913 return isl_bool_false;1914}1915