/* * Copyright 2010-2011 INRIA Saclay * Copyright 2011 Sven Verdoolaege * Copyright 2012-2014 Ecole Normale Superieure * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, * 91893 Orsay, France * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ #include <isl/id.h> #include <isl/aff.h> #include <isl_sort.h> #include <isl_val_private.h> #include <isl_pw_macro.h> #include "opt_type.h" __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *space OPT_TYPE_PARAM, int n) { … } __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM) { … } /* Add a piece with domain "set" and base expression "el" * to the piecewise expression "pw". * * Do this independently of the values of "set" and "el", * such that this function can be used by isl_pw_*_dup. */ static __isl_give PW *FN(PW,add_dup_piece)(__isl_take PW *pw, __isl_take isl_set *set, __isl_take EL *el) { … } /* Add a piece with domain "set" and base expression "el" * to the piecewise expression "pw", provided the domain * is not obviously empty and the base expression * is not equal to the default value. */ __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw, __isl_take isl_set *set, __isl_take EL *el) { … } /* Does the space of "set" correspond to that of the domain of "el". */ static isl_bool FN(PW,compatible_domain)(__isl_keep EL *el, __isl_keep isl_set *set) { … } /* Check that the space of "set" corresponds to that of the domain of "el". */ static isl_stat FN(PW,check_compatible_domain)(__isl_keep EL *el, __isl_keep isl_set *set) { … } __isl_give PW *FN(PW,alloc)(OPT_TYPE_PARAM_FIRST __isl_take isl_set *set, __isl_take EL *el) { … } __isl_give PW *FN(PW,dup)(__isl_keep PW *pw) { … } __isl_give PW *FN(PW,cow)(__isl_take PW *pw) { … } __isl_give PW *FN(PW,copy)(__isl_keep PW *pw) { … } __isl_null PW *FN(PW,free)(__isl_take PW *pw) { … } /* Return the space of "pw". */ __isl_keep isl_space *FN(PW,peek_space)(__isl_keep PW *pw) { … } __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw) { … } /* Return the space of "pw". * This may be either a copy or the space itself * if there is only one reference to "pw". * This allows the space to be modified inplace * if both the piecewise expression and its space have only a single reference. * The caller is not allowed to modify "pw" between this call and * a subsequent call to isl_pw_*_restore_*. * The only exception is that isl_pw_*_free can be called instead. */ static __isl_give isl_space *FN(PW,take_space)(__isl_keep PW *pw) { … } /* Set the space of "pw" to "space", where the space of "pw" may be missing * due to a preceding call to isl_pw_*_take_space. * However, in this case, "pw" only has a single reference and * then the call to isl_pw_*_cow has no effect. */ static __isl_give PW *FN(PW,restore_space)(__isl_take PW *pw, __isl_take isl_space *space) { … } /* Check that "pos" is a valid position for a cell in "pw". */ static isl_stat FN(PW,check_pos)(__isl_keep PW *pw, int pos) { … } /* Return the cell at position "pos" in "pw". */ static __isl_keep isl_set *FN(PW,peek_domain_at)(__isl_keep PW *pw, int pos) { … } /* Return a copy of the cell at position "pos" in "pw". */ static __isl_give isl_set *FN(PW,get_domain_at)(__isl_keep PW *pw, int pos) { … } /* Return the cell at position "pos" in "pw". * This may be either a copy or the cell itself * if there is only one reference to "pw". * This allows the cell to be modified inplace * if both the piecewise expression and this cell * have only a single reference. * The caller is not allowed to modify "pw" between this call and * the subsequent call to isl_pw_*_restore_domain_at. * The only exception is that isl_pw_*_free can be called instead. */ static __isl_give isl_set *FN(PW,take_domain_at)(__isl_keep PW *pw, int pos) { … } /* Set the cell at position "pos" in "pw" to "el", * where this cell may be missing * due to a preceding call to isl_pw_*_take_domain_at. * However, in this case, "pw" only has a single reference and * then the call to isl_pw_*_cow has no effect. */ static __isl_give PW *FN(PW,restore_domain_at)(__isl_take PW *pw, int pos, __isl_take isl_set *domain) { … } /* Return the base expression associated to * the cell at position "pos" in "pw". */ __isl_keep EL *FN(PW,peek_base_at)(__isl_keep PW *pw, int pos) { … } /* Return a copy of the base expression associated to * the cell at position "pos" in "pw". */ static __isl_give EL *FN(PW,get_base_at)(__isl_keep PW *pw, int pos) { … } /* Return the base expression associated to * the cell at position "pos" in "pw". * This may be either a copy or the base expression itself * if there is only one reference to "pw". * This allows the base expression to be modified inplace * if both the piecewise expression and this base expression * have only a single reference. * The caller is not allowed to modify "pw" between this call and * a subsequent call to isl_pw_*_restore_*. * The only exception is that isl_pw_*_free can be called instead. */ static __isl_give EL *FN(PW,take_base_at)(__isl_keep PW *pw, int pos) { … } /* Set the base expression associated to * the cell at position "pos" in "pw" to "el", * where this base expression may be missing * due to a preceding call to isl_pw_*_take_base_at. * However, in this case, "pw" only has a single reference and * then the call to isl_pw_*_cow has no effect. * If "inplace" is set, then replacing the base expression by "el" * is known not to change the meaning of "pw". It can therefore be replaced * in all references to "pw". */ static __isl_give PW *FN(PW,restore_base_at_)(__isl_take PW *pw, int pos, __isl_take EL *el, int inplace) { … } /* Set the base expression associated to * the cell at position "pos" in "pw" to "el", * where this base expression may be missing * due to a preceding call to isl_pw_*_take_base_at. */ static __isl_give PW *FN(PW,restore_base_at)(__isl_take PW *pw, int pos, __isl_take EL *el) { … } /* Set the base expression associated to * the cell at position "pos" in "pw" to "el", * where this base expression may be missing * due to a preceding call to isl_pw_*_take_base_at. * Furthermore, replacing the base expression by "el" * is known not to change the meaning of "pw". */ static __isl_give PW *FN(PW,restore_base_at_inplace)(__isl_take PW *pw, int pos, __isl_take EL *el) { … } /* Create a piecewise expression with the given base expression on a universe * domain. */ static __isl_give PW *FN(FN(FN(PW,from),BASE),type_base)(__isl_take EL *el OPT_TYPE_PARAM) { … } /* Create a piecewise expression with the given base expression on a universe * domain. * * If the default value of this piecewise type is zero and * if "el" is effectively zero, then create an empty piecewise expression * instead. */ static __isl_give PW *FN(FN(FN(PW,from),BASE),type)(__isl_take EL *el OPT_TYPE_PARAM) { … } #ifdef HAS_TYPE /* Create a piecewise expression with the given base expression on a universe * domain. * * Pass along the type as an extra argument for improved uniformity * with piecewise types that do not have a fold type. */ __isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el) { enum isl_fold type = FN(EL,get_type)(el); return FN(FN(FN(PW,from),BASE),type)(el, type); } #else __isl_give PW *FN(FN(PW,from),BASE)(__isl_take EL *el) { … } #endif const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type, unsigned pos) { … } isl_bool FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type, unsigned pos) { … } __isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type, unsigned pos) { … } isl_bool FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type) { … } const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type) { … } isl_bool FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type) { … } __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type) { … } isl_bool FN(PW,IS_ZERO)(__isl_keep PW *pw) { … } static __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw, __isl_take isl_reordering *exp) { … } #undef TYPE #define TYPE … #include "isl_check_named_params_templ.c" /* Align the parameters of "pw" to those of "model". */ __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model) { … } #undef TYPE #define TYPE … static #include "isl_align_params_bin_templ.c" #undef SUFFIX #define SUFFIX … #undef ARG1 #define ARG1 … #undef ARG2 #define ARG2 … static #include "isl_align_params_templ.c" #undef TYPE #define TYPE … #include "isl_type_has_equal_space_bin_templ.c" #include "isl_type_check_equal_space_templ.c" /* Private version of "union_add". For isl_pw_qpolynomial and * isl_pw_qpolynomial_fold, we prefer to simply call it "add". */ static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2) { … } #if !DEFAULT_IS_ZERO /* Compute the sum of "pw1" and "pw2 on the union of their domains, * with the actual sum on the shared domain and * the defined expression on the symmetric difference of the domains. * * This function is only defined for object types that do not have * a default zero value. For other object types, this function * is simply called "add". */ __isl_give PW *FN(PW,union_add)(__isl_take PW *pw1, __isl_take PW *pw2) { … } #endif /* This function is currently only used from isl_aff.c */ static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1, __isl_take PW *pw2, __isl_take isl_space *space, __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) __attribute__ ((unused)); /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains. * The result of "fn" (and therefore also of this function) lives in "space". */ static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1, __isl_take PW *pw2, __isl_take isl_space *space, __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) { … } /* This function is currently only used from isl_aff.c */ static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1, __isl_take PW *pw2, __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) __attribute__ ((unused)); /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains. * The result of "fn" is assumed to live in the same space as "pw1" and "pw2". */ static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1, __isl_take PW *pw2, __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2)) { … } /* Return the parameter domain of "pw". */ __isl_give isl_set *FN(PW,params)(__isl_take PW *pw) { … } __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw) { … } /* Exploit the equalities in the domain of piece "i" of "pw" * to simplify the associated function. * If the domain of piece "i" is empty, then remove it entirely, * replacing it with the final piece. */ static __isl_give PW *FN(PW,exploit_equalities_and_remove_if_empty)( __isl_take PW *pw, int i) { … } /* Restrict the domain of "pw" by combining each cell * with "set" through a call to "fn", where "fn" may be * isl_set_intersect, isl_set_intersect_params, isl_set_intersect_factor_domain, * isl_set_intersect_factor_range or isl_set_subtract. */ static __isl_give PW *FN(PW,restrict_domain)(__isl_take PW *pw, __isl_take isl_set *set, __isl_give isl_set *(*fn)(__isl_take isl_set *set1, __isl_take isl_set *set2)) { … } __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw, __isl_take isl_set *context) { … } /* Intersect the domain of "pw" with the parameter domain "context". */ __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw, __isl_take isl_set *context) { … } /* Given a piecewise expression "pw" with domain in a space [A -> B] and * a set in the space A, intersect the domain with the set. */ __isl_give PW *FN(PW,intersect_domain_wrapped_domain)(__isl_take PW *pw, __isl_take isl_set *set) { … } /* Given a piecewise expression "pw" with domain in a space [A -> B] and * a set in the space B, intersect the domain with the set. */ __isl_give PW *FN(PW,intersect_domain_wrapped_range)(__isl_take PW *pw, __isl_take isl_set *set) { … } /* Subtract "domain' from the domain of "pw". */ __isl_give PW *FN(PW,subtract_domain)(__isl_take PW *pw, __isl_take isl_set *domain) { … } /* Return -1 if the piece "p1" should be sorted before "p2" * and 1 if it should be sorted after "p2". * Return 0 if they do not need to be sorted in a specific order. * * The two pieces are compared on the basis of their function value expressions. */ static int FN(PW,sort_field_cmp)(const void *p1, const void *p2, void *arg) { … } /* Sort the pieces of "pw" according to their function value * expressions and then combine pairs of adjacent pieces with * the same such expression. * * The sorting is performed in place because it does not * change the meaning of "pw", but care needs to be * taken not to change any possible other copies of "pw" * in case anything goes wrong. */ static __isl_give PW *FN(PW,sort_unique)(__isl_take PW *pw) { … } /* Compute the gist of "pw" with respect to the domain constraints * of "context" for the case where the domain of the last element * of "pw" is equal to "context". * Compute the gist of this element, replace * its domain by the universe and drop all other elements * as their domains are necessarily disjoint from "context". */ static __isl_give PW *FN(PW,gist_last)(__isl_take PW *pw, __isl_take isl_set *context) { … } /* Compute the gist of "pw" with respect to the domain constraints * of "context". * Call "fn_dom" to compute the gist of the domains and * "intersect_context" to intersect the domain with the context. * * If the piecewise expression is empty or the context is the universe, * then nothing can be simplified. * If "pw" has a single domain and it is equal to "context", * then simply replace the domain by the universe. * Combine duplicate function value expressions first * to increase the chance of "pw" having a single domain. */ static __isl_give PW *FN(PW,gist_fn)(__isl_take PW *pw, __isl_take isl_set *context, __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set, __isl_take isl_basic_set *bset), __isl_give isl_set *intersect_context(__isl_take isl_set *set, __isl_take isl_set *context)) { … } __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context) { … } __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw, __isl_take isl_set *context) { … } /* Coalesce the domains of "pw". * * Prior to the actual coalescing, first sort the pieces such that * pieces with the same function value expression are combined * into a single piece, the combined domain of which can then * be coalesced. */ __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw) { … } isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw) { … } isl_bool FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type, unsigned first, unsigned n) { … } __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw, enum isl_dim_type type, unsigned pos, const char *s) { … } __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw, enum isl_dim_type type, unsigned first, unsigned n) { … } /* This function is very similar to drop_dims. * The only difference is that the cells may still involve * the specified dimensions. They are removed using * isl_set_project_out instead of isl_set_drop. */ __isl_give PW *FN(PW,project_out)(__isl_take PW *pw, enum isl_dim_type type, unsigned first, unsigned n) { … } /* Project the domain of pw onto its parameter space. */ __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw) { … } /* Drop all parameters not referenced by "pw". */ __isl_give PW *FN(PW,drop_unused_params)(__isl_take PW *pw) { … } isl_size FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type) { … } __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw) { … } /* Return the position of the dimension of the given type and name * in "pw". * Return -1 if no such dimension can be found. */ int FN(PW,find_dim_by_name)(__isl_keep PW *pw, enum isl_dim_type type, const char *name) { … } /* Return the position of the dimension of the given type and identifier * in "pw". * Return -1 if no such dimension can be found. */ static int FN(PW,find_dim_by_id)(__isl_keep PW *pw, enum isl_dim_type type, __isl_keep isl_id *id) { … } /* Does the piecewise expression "pw" depend in any way * on the parameter with identifier "id"? */ isl_bool FN(PW,involves_param_id)(__isl_keep PW *pw, __isl_keep isl_id *id) { … } /* Reset the space of "pw". Since we don't know if the elements * represent the spaces themselves or their domains, we pass along * both when we call their reset_space_and_domain. */ static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw, __isl_take isl_space *space, __isl_take isl_space *domain) { … } __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw, __isl_take isl_space *domain) { … } __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *space) { … } __isl_give PW *FN(PW,set_tuple_id)(__isl_take PW *pw, enum isl_dim_type type, __isl_take isl_id *id) { … } /* Drop the id on the specified tuple. */ __isl_give PW *FN(PW,reset_tuple_id)(__isl_take PW *pw, enum isl_dim_type type) { … } __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw, enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) { … } /* Reset the user pointer on all identifiers of parameters and tuples * of the space of "pw". */ __isl_give PW *FN(PW,reset_user)(__isl_take PW *pw) { … } isl_size FN(PW,n_piece)(__isl_keep PW *pw) { … } isl_stat FN(PW,foreach_piece)(__isl_keep PW *pw, isl_stat (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user), void *user) { … } /* Does "test" succeed on every cell of "pw"? */ isl_bool FN(PW,every_piece)(__isl_keep PW *pw, isl_bool (*test)(__isl_keep isl_set *set, __isl_keep EL *el, void *user), void *user) { … } /* Is "pw" defined over a single universe domain? * * If the default value of this piecewise type is zero, * then a "pw" with a zero number of cells is also accepted * as it represents the default zero value. */ isl_bool FN(FN(PW,isa),BASE)(__isl_keep PW *pw) { … } /* Return a zero base expression in the same space (and of the same type) * as "pw". */ static __isl_give EL *FN(EL,zero_like_type)(__isl_take PW *pw OPT_TYPE_PARAM) { … } #ifndef HAS_TYPE /* Return a zero base expression in the same space as "pw". */ static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw) { … } #else /* Return a zero base expression in the same space and of the same type * as "pw". * * Pass along the type as an explicit argument for uniform handling * in isl_*_zero_like_type. */ static __isl_give EL *FN(EL,zero_like)(__isl_take PW *pw) { enum isl_fold type; type = FN(PW,get_type)(pw); if (type < 0) goto error; return FN(EL,zero_like_type)(pw, type); error: FN(PW,free)(pw); return NULL; } #endif /* Given that "pw" is defined over a single universe domain, * return the base expression associated to this domain. * * If the number of cells is zero, then "pw" is of a piecewise type * with a default zero value and effectively represents zero. * In this case, create a zero base expression in the same space * (and with the same type). * Otherwise, simply extract the associated base expression. */ __isl_give EL *FN(FN(PW,as),BASE)(__isl_take PW *pw) { … } #ifdef HAS_TYPE /* Negate the type of "pw". */ static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw) { pw = FN(PW,cow)(pw); if (!pw) return NULL; pw->type = isl_fold_type_negate(pw->type); return pw; } #else /* Negate the type of "pw". * Since "pw" does not have a type, do nothing. */ static __isl_give PW *FN(PW,negate_type)(__isl_take PW *pw) { … } #endif /* Multiply the pieces of "pw" by "v" and return the result. */ __isl_give PW *FN(PW,scale_val)(__isl_take PW *pw, __isl_take isl_val *v) { … } /* Divide the pieces of "pw" by "v" and return the result. */ __isl_give PW *FN(PW,scale_down_val)(__isl_take PW *pw, __isl_take isl_val *v) { … } /* Apply some normalization to "pw". * In particular, sort the pieces according to their function value * expressions, combining pairs of adjacent pieces with * the same such expression, and then normalize the domains of the pieces. * * We normalize in place, but if anything goes wrong we need * to return NULL, so we need to make sure we don't change the * meaning of any possible other copies of "pw". */ static __isl_give PW *FN(PW,normalize)(__isl_take PW *pw) { … } /* Is pw1 obviously equal to pw2? * That is, do they have obviously identical cells and obviously identical * elements on each cell? * * If "pw1" or "pw2" contain any NaNs, then they are considered * not to be the same. A NaN is not equal to anything, not even * to another NaN. */ isl_bool FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2) { … } /* Does "pw" involve any NaNs? */ isl_bool FN(PW,involves_nan)(__isl_keep PW *pw) { … }
Codebase Browser
llvm