/* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France */ #include <isl_map_private.h> #include <isl_constraint_private.h> #include <isl_space_private.h> #include <isl_seq.h> #include <isl_aff_private.h> #include <isl_local_space_private.h> #include <isl_val_private.h> #include <isl_vec_private.h> #include <bset_to_bmap.c> #include <bset_from_bmap.c> #undef EL_BASE #define EL_BASE … #include <isl_list_templ.c> isl_ctx *isl_constraint_get_ctx(__isl_keep isl_constraint *c) { … } static isl_size n(__isl_keep isl_constraint *c, enum isl_dim_type type) { … } static unsigned offset(__isl_keep isl_constraint *c, enum isl_dim_type type) { … } __isl_give isl_constraint *isl_constraint_alloc_vec(int eq, __isl_take isl_local_space *ls, __isl_take isl_vec *v) { … } __isl_give isl_constraint *isl_constraint_alloc(int eq, __isl_take isl_local_space *ls) { … } __isl_give isl_constraint *isl_basic_map_constraint( __isl_take isl_basic_map *bmap, isl_int **line) { … } __isl_give isl_constraint *isl_basic_set_constraint( __isl_take isl_basic_set *bset, isl_int **line) { … } __isl_give isl_constraint *isl_constraint_alloc_equality( __isl_take isl_local_space *ls) { … } __isl_give isl_constraint *isl_constraint_alloc_inequality( __isl_take isl_local_space *ls) { … } __isl_give isl_constraint *isl_constraint_dup(__isl_keep isl_constraint *c) { … } __isl_give isl_constraint *isl_constraint_cow(__isl_take isl_constraint *c) { … } __isl_give isl_constraint *isl_constraint_copy( __isl_keep isl_constraint *constraint) { … } __isl_null isl_constraint *isl_constraint_free(__isl_take isl_constraint *c) { … } /* Return the number of constraints in "bmap", i.e., the * number of times isl_basic_map_foreach_constraint will * call the callback. */ isl_size isl_basic_map_n_constraint(__isl_keep isl_basic_map *bmap) { … } /* Return the number of constraints in "bset", i.e., the * number of times isl_basic_set_foreach_constraint will * call the callback. */ isl_size isl_basic_set_n_constraint(__isl_keep isl_basic_set *bset) { … } isl_stat isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap, isl_stat (*fn)(__isl_take isl_constraint *c, void *user), void *user) { … } isl_stat isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset, isl_stat (*fn)(__isl_take isl_constraint *c, void *user), void *user) { … } /* Add the constraint to the list that "user" points to, if it is not * a div constraint. */ static isl_stat collect_constraint(__isl_take isl_constraint *constraint, void *user) { … } /* Return a list of constraints that, when combined, are equivalent * to "bmap". The input is required to have only known divs. * * There is no need to include the div constraints as they are * implied by the div expressions. */ __isl_give isl_constraint_list *isl_basic_map_get_constraint_list( __isl_keep isl_basic_map *bmap) { … } /* Return a list of constraints that, when combined, are equivalent * to "bset". The input is required to have only known divs. */ __isl_give isl_constraint_list *isl_basic_set_get_constraint_list( __isl_keep isl_basic_set *bset) { … } int isl_constraint_is_equal(__isl_keep isl_constraint *constraint1, __isl_keep isl_constraint *constraint2) { … } __isl_give isl_basic_map *isl_basic_map_add_constraint( __isl_take isl_basic_map *bmap, __isl_take isl_constraint *constraint) { … } __isl_give isl_basic_set *isl_basic_set_add_constraint( __isl_take isl_basic_set *bset, __isl_take isl_constraint *constraint) { … } __isl_give isl_map *isl_map_add_constraint(__isl_take isl_map *map, __isl_take isl_constraint *constraint) { … } __isl_give isl_set *isl_set_add_constraint(__isl_take isl_set *set, __isl_take isl_constraint *constraint) { … } /* Return the space of "constraint". */ static __isl_keep isl_space *isl_constraint_peek_space( __isl_keep isl_constraint *constraint) { … } __isl_give isl_space *isl_constraint_get_space( __isl_keep isl_constraint *constraint) { … } __isl_give isl_local_space *isl_constraint_get_local_space( __isl_keep isl_constraint *constraint) { … } isl_size isl_constraint_dim(__isl_keep isl_constraint *constraint, enum isl_dim_type type) { … } #undef TYPE #define TYPE … static #include "check_type_range_templ.c" isl_bool isl_constraint_involves_dims(__isl_keep isl_constraint *constraint, enum isl_dim_type type, unsigned first, unsigned n) { … } /* Does the given constraint represent a lower bound on the given * dimension? */ isl_bool isl_constraint_is_lower_bound(__isl_keep isl_constraint *constraint, enum isl_dim_type type, unsigned pos) { … } /* Does the given constraint represent an upper bound on the given * dimension? */ isl_bool isl_constraint_is_upper_bound(__isl_keep isl_constraint *constraint, enum isl_dim_type type, unsigned pos) { … } const char *isl_constraint_get_dim_name(__isl_keep isl_constraint *constraint, enum isl_dim_type type, unsigned pos) { … } void isl_constraint_get_constant(__isl_keep isl_constraint *constraint, isl_int *v) { … } /* Return the constant term of "constraint". */ __isl_give isl_val *isl_constraint_get_constant_val( __isl_keep isl_constraint *constraint) { … } void isl_constraint_get_coefficient(__isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos, isl_int *v) { … } /* Return the coefficient of the variable of type "type" at position "pos" * of "constraint". */ __isl_give isl_val *isl_constraint_get_coefficient_val( __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos) { … } __isl_give isl_aff *isl_constraint_get_div(__isl_keep isl_constraint *constraint, int pos) { … } __isl_give isl_constraint *isl_constraint_set_constant( __isl_take isl_constraint *constraint, isl_int v) { … } /* Replace the constant term of "constraint" by "v". */ __isl_give isl_constraint *isl_constraint_set_constant_val( __isl_take isl_constraint *constraint, __isl_take isl_val *v) { … } __isl_give isl_constraint *isl_constraint_set_constant_si( __isl_take isl_constraint *constraint, int v) { … } /* Replace the coefficient of the variable of type "type" at position "pos" * of "constraint" by "v". */ __isl_give isl_constraint *isl_constraint_set_coefficient_val( __isl_take isl_constraint *constraint, enum isl_dim_type type, int pos, __isl_take isl_val *v) { … } __isl_give isl_constraint *isl_constraint_set_coefficient_si( __isl_take isl_constraint *constraint, enum isl_dim_type type, int pos, int v) { … } __isl_give isl_constraint *isl_constraint_negate( __isl_take isl_constraint *constraint) { … } isl_bool isl_constraint_is_equality(struct isl_constraint *constraint) { … } isl_bool isl_constraint_is_div_constraint(__isl_keep isl_constraint *constraint) { … } /* Is "constraint" an equality that corresponds to integer division "div"? * * That is, given an integer division of the form * * a = floor((f + c)/m) * * is the equality of the form * * -f + m d + c' = 0 * ? * Note that the constant term is not checked explicitly, but given * that this is a valid equality constraint, the constant c' necessarily * has a value close to -c. */ isl_bool isl_constraint_is_div_equality(__isl_keep isl_constraint *constraint, unsigned div) { … } /* We manually set ISL_BASIC_SET_FINAL instead of calling * isl_basic_map_finalize because we want to keep the position * of the divs and we therefore do not want to throw away redundant divs. * This is arguably a bit fragile. */ __isl_give isl_basic_map *isl_basic_map_from_constraint( __isl_take isl_constraint *constraint) { … } __isl_give isl_basic_set *isl_basic_set_from_constraint( __isl_take isl_constraint *constraint) { … } /* Is the variable of "type" at position "pos" of "bmap" defined * in terms of earlier dimensions through an equality? * * If so, and if c is not NULL, then return a copy of this equality in *c. */ isl_bool isl_basic_map_has_defining_equality( __isl_keep isl_basic_map *bmap, enum isl_dim_type type, int pos, __isl_give isl_constraint **c) { … } /* Is the variable of "type" at position "pos" of "bset" defined * in terms of earlier dimensions through an equality? * * If so, and if c is not NULL, then return a copy of this equality in *c. */ isl_bool isl_basic_set_has_defining_equality( __isl_keep isl_basic_set *bset, enum isl_dim_type type, int pos, __isl_give isl_constraint **c) { … } isl_bool isl_basic_set_has_defining_inequalities( struct isl_basic_set *bset, enum isl_dim_type type, int pos, struct isl_constraint **lower, struct isl_constraint **upper) { … } /* Given two constraints "a" and "b" on the variable at position "abs_pos" * (in "a" and "b"), add a constraint to "bset" that ensures that the * bound implied by "a" is (strictly) larger than the bound implied by "b". * * If both constraints imply lower bounds, then this means that "a" is * active in the result. * If both constraints imply upper bounds, then this means that "b" is * active in the result. */ static __isl_give isl_basic_set *add_larger_bound_constraint( __isl_take isl_basic_set *bset, isl_int *a, isl_int *b, unsigned abs_pos, int strict) { … } /* Add constraints to "context" that ensure that "u" is the smallest * (and therefore active) upper bound on "abs_pos" in "bset" and return * the resulting basic set. */ static __isl_give isl_basic_set *set_smallest_upper_bound( __isl_keep isl_basic_set *context, __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_upper, int u) { … } /* Add constraints to "context" that ensure that "u" is the largest * (and therefore active) upper bound on "abs_pos" in "bset" and return * the resulting basic set. */ static __isl_give isl_basic_set *set_largest_lower_bound( __isl_keep isl_basic_set *context, __isl_keep isl_basic_set *bset, unsigned abs_pos, int n_lower, int l) { … } static isl_stat foreach_upper_bound(__isl_keep isl_basic_set *bset, enum isl_dim_type type, unsigned abs_pos, __isl_take isl_basic_set *context, int n_upper, isl_stat (*fn)(__isl_take isl_constraint *lower, __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset, void *user), void *user) { … } static isl_stat foreach_lower_bound(__isl_keep isl_basic_set *bset, enum isl_dim_type type, unsigned abs_pos, __isl_take isl_basic_set *context, int n_lower, isl_stat (*fn)(__isl_take isl_constraint *lower, __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset, void *user), void *user) { … } static isl_stat foreach_bound_pair(__isl_keep isl_basic_set *bset, enum isl_dim_type type, unsigned abs_pos, __isl_take isl_basic_set *context, int n_lower, int n_upper, isl_stat (*fn)(__isl_take isl_constraint *lower, __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset, void *user), void *user) { … } /* For each pair of lower and upper bounds on the variable "pos" * of type "type", call "fn" with these lower and upper bounds and the * set of constraints on the remaining variables where these bounds * are active, i.e., (stricly) larger/smaller than the other lower/upper bounds. * * If the designated variable is equal to an affine combination of the * other variables then fn is called with both lower and upper * set to the corresponding equality. * * If there is no lower (or upper) bound, then NULL is passed * as the corresponding bound. * * We first check if the variable is involved in any equality. * If not, we count the number of lower and upper bounds and * act accordingly. */ isl_stat isl_basic_set_foreach_bound_pair(__isl_keep isl_basic_set *bset, enum isl_dim_type type, unsigned pos, isl_stat (*fn)(__isl_take isl_constraint *lower, __isl_take isl_constraint *upper, __isl_take isl_basic_set *bset, void *user), void *user) { … } __isl_give isl_aff *isl_constraint_get_bound( __isl_keep isl_constraint *constraint, enum isl_dim_type type, int pos) { … } /* For an inequality constraint * * f >= 0 * * or an equality constraint * * f = 0 * * return the affine expression f. */ __isl_give isl_aff *isl_constraint_get_aff( __isl_keep isl_constraint *constraint) { … } /* Construct an inequality (eq = 0) or equality (eq = 1) constraint from "aff". * In particular, construct aff >= 0 or aff = 0. * * The denominator of "aff" can be ignored. */ static __isl_give isl_constraint *isl_constraint_alloc_aff(int eq, __isl_take isl_aff *aff) { … } /* Construct an equality constraint equating the given affine expression * to zero. */ __isl_give isl_constraint *isl_equality_from_aff(__isl_take isl_aff *aff) { … } /* Construct an inequality constraint enforcing the given affine expression * to be non-negative. */ __isl_give isl_constraint *isl_inequality_from_aff(__isl_take isl_aff *aff) { … } /* Compare two isl_constraints. * * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater" * than "c2" and 0 if they are equal. * * The order is fairly arbitrary. We do consider constraints that only involve * earlier dimensions as "smaller". */ int isl_constraint_plain_cmp(__isl_keep isl_constraint *c1, __isl_keep isl_constraint *c2) { … } /* Compare two constraints based on their final (non-zero) coefficients. * In particular, the constraint that involves later variables or * that has a larger coefficient for a shared latest variable * is considered "greater" than the other constraint. * * Return -1 if "c1" is "smaller" than "c2", 1 if "c1" is "greater" * than "c2" and 0 if they are equal. * * If the constraints live in different local spaces, then we cannot * really compare the constraints so we compare the local spaces instead. */ int isl_constraint_cmp_last_non_zero(__isl_keep isl_constraint *c1, __isl_keep isl_constraint *c2) { … }
Codebase Browser
llvm