/* * Copyright 2010-2011 INRIA Saclay * Copyright 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_map_private.h> #include <isl_aff_private.h> #include <isl_morph.h> #include <isl_seq.h> #include <isl_mat_private.h> #include <isl_space_private.h> #include <isl_equalities.h> #include <isl_id_private.h> #include <isl_aff_private.h> #include <isl_vec_private.h> isl_ctx *isl_morph_get_ctx(__isl_keep isl_morph *morph) { … } __isl_give isl_morph *isl_morph_alloc( __isl_take isl_basic_set *dom, __isl_take isl_basic_set *ran, __isl_take isl_mat *map, __isl_take isl_mat *inv) { … } __isl_give isl_morph *isl_morph_copy(__isl_keep isl_morph *morph) { … } __isl_give isl_morph *isl_morph_dup(__isl_keep isl_morph *morph) { … } __isl_give isl_morph *isl_morph_cow(__isl_take isl_morph *morph) { … } __isl_null isl_morph *isl_morph_free(__isl_take isl_morph *morph) { … } /* Is "morph" an identity on the parameters? */ static isl_bool identity_on_parameters(__isl_keep isl_morph *morph) { … } /* Return an affine expression of the variables of the range of "morph" * in terms of the parameters and the variables of the domain on "morph". * * In order for the space manipulations to make sense, we require * that the parameters are not modified by "morph". */ __isl_give isl_multi_aff *isl_morph_get_var_multi_aff( __isl_keep isl_morph *morph) { … } /* Return the domain space of "morph". */ static __isl_keep isl_space *isl_morph_peek_dom_space( __isl_keep isl_morph *morph) { … } /* Return a copy of the domain space of "morph". */ __isl_give isl_space *isl_morph_get_dom_space(__isl_keep isl_morph *morph) { … } /* Check that the match against "space" with result "match" was successful. */ static isl_stat check_space_match(__isl_keep isl_space *space, isl_bool match) { … } /* Check that "morph" can be applied to the "space". */ isl_stat isl_morph_check_applies(__isl_keep isl_morph *morph, __isl_keep isl_space *space) { … } __isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph) { … } isl_size isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type) { … } isl_size isl_morph_ran_dim(__isl_keep isl_morph *morph, enum isl_dim_type type) { … } __isl_give isl_morph *isl_morph_remove_dom_dims(__isl_take isl_morph *morph, enum isl_dim_type type, unsigned first, unsigned n) { … } __isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph, enum isl_dim_type type, unsigned first, unsigned n) { … } /* Project domain of morph onto its parameter domain. */ __isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph) { … } /* Project range of morph onto its parameter domain. */ __isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph) { … } /* Replace the identifier of the tuple of the range of the morph by "id". */ static __isl_give isl_morph *isl_morph_set_ran_tuple_id( __isl_take isl_morph *morph, __isl_keep isl_id *id) { … } void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out) { … } void isl_morph_dump(__isl_take isl_morph *morph) { … } __isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset) { … } /* Create a(n identity) morphism between empty sets of the same dimension * a "bset". */ __isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_set *bset) { … } /* Construct a basic set described by the "n" equalities of "bset" starting * at "first". */ static __isl_give isl_basic_set *copy_equalities(__isl_keep isl_basic_set *bset, unsigned first, unsigned n) { … } /* Given a basic set, exploit the equalities in the basic set to construct * a morphism that maps the basic set to a lower-dimensional space. * Specifically, the morphism reduces the number of dimensions of type "type". * * We first select the equalities of interest, that is those that involve * variables of type "type" and no later variables. * Denote those equalities as * * -C(p) + M x = 0 * * where C(p) depends on the parameters if type == isl_dim_set and * is a constant if type == isl_dim_param. * * Use isl_mat_final_variable_compression to construct a compression * * x = T x' * * x' = Q x * * If T is a zero-column matrix, then the set of equality constraints * do not admit a solution. In this case, an empty morphism is returned. * * Both matrices are extended to map the full original space to the full * compressed space. */ __isl_give isl_morph *isl_basic_set_variable_compression( __isl_keep isl_basic_set *bset, enum isl_dim_type type) { … } /* Given a basic set, exploit the equalities in the basic set to construct * a morphism that maps the basic set to a lower-dimensional space * with identifier "id". * Specifically, the morphism reduces the number of set dimensions. */ __isl_give isl_morph *isl_basic_set_variable_compression_with_id( __isl_keep isl_basic_set *bset, __isl_keep isl_id *id) { … } /* Construct a parameter compression for "bset". * We basically just call isl_mat_parameter_compression with the right input * and then extend the resulting matrix to include the variables. * * The implementation assumes that "bset" does not have any equalities * that only involve the parameters and that isl_basic_set_gauss has * been applied to "bset". * * Let the equalities be given as * * B(p) + A x = 0. * * We use isl_mat_parameter_compression_ext to compute the compression * * p = T p'. */ __isl_give isl_morph *isl_basic_set_parameter_compression( __isl_keep isl_basic_set *bset) { … } /* Construct an isl_multi_aff that corresponds * to the affine transformation matrix "mat" and * that lives in an anonymous space. */ static __isl_give isl_multi_aff *isl_multi_aff_from_aff_mat_anonymous( __isl_take isl_mat *mat) { … } /* Apply the morphism to the basic set. * In particular, compute the preimage of "bset" under the inverse mapping * in morph and intersect with the range of the morphism. * Note that the mapping in morph applies to both parameters and set dimensions, * so the parameters need to be treated as set dimensions during the call * to isl_basic_set_preimage_multi_aff. */ __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph, __isl_take isl_basic_set *bset) { … } /* Apply the morphism to the set. * In particular, compute the preimage of "set" under the inverse mapping * in morph and intersect with the range of the morphism. * Note that the mapping in morph applies to both parameters and set dimensions, * so the parameters need to be treated as set dimensions during the call * to isl_set_preimage_multi_aff. */ __isl_give isl_set *isl_morph_set(__isl_take isl_morph *morph, __isl_take isl_set *set) { … } /* Construct a morphism that first does morph2 and then morph1. */ __isl_give isl_morph *isl_morph_compose(__isl_take isl_morph *morph1, __isl_take isl_morph *morph2) { … } __isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph) { … } /* We detect all the equalities first to avoid implicit equalities * being discovered during the computations. In particular, * the compression on the variables could expose additional stride * constraints on the parameters. This would result in existentially * quantified variables after applying the resulting morph, which * in turn could break invariants of the calling functions. */ __isl_give isl_morph *isl_basic_set_full_compression( __isl_keep isl_basic_set *bset) { … } __isl_give isl_vec *isl_morph_vec(__isl_take isl_morph *morph, __isl_take isl_vec *vec) { … }