/* * Copyright 2011 INRIA Saclay * 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_ctx_private.h> #include <isl/id.h> #include <isl_map_private.h> #include <isl_local_space_private.h> #include <isl_space_private.h> #include <isl_mat_private.h> #include <isl_aff_private.h> #include <isl_vec_private.h> #include <isl_point_private.h> #include <isl_seq.h> #include <isl_local.h> isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls) { … } /* Return a hash value that digests "ls". */ uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_alloc_div( __isl_take isl_space *space, __isl_take isl_mat *div) { … } __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *space, unsigned n_div) { … } __isl_give isl_local_space *isl_local_space_from_space( __isl_take isl_space *space) { … } __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls) { … } __isl_null isl_local_space *isl_local_space_free( __isl_take isl_local_space *ls) { … } /* Is the local space that of a parameter domain? */ isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls) { … } /* Is the local space that of a set? */ isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls) { … } #undef TYPE #define TYPE … #include "isl_type_has_equal_space_bin_templ.c" #include "isl_type_has_space_templ.c" /* Check that the space of "ls" is equal to "space". */ static isl_stat isl_local_space_check_has_space(__isl_keep isl_local_space *ls, __isl_keep isl_space *space) { … } /* Return true if the two local spaces are identical, with identical * expressions for the integer divisions. */ isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1, __isl_keep isl_local_space *ls2) { … } /* Compare two isl_local_spaces. * * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater" * than "ls2" and 0 if they are equal. */ int isl_local_space_cmp(__isl_keep isl_local_space *ls1, __isl_keep isl_local_space *ls2) { … } isl_size isl_local_space_dim(__isl_keep isl_local_space *ls, enum isl_dim_type type) { … } #undef TYPE #define TYPE … #include "check_type_range_templ.c" /* Return the position of the variables of the given type * within the sequence of variables of "ls". */ isl_size isl_local_space_var_offset(__isl_keep isl_local_space *ls, enum isl_dim_type type) { … } /* Return the position of the coefficients of the variables of the given type * within the sequence of coefficients of "ls". */ unsigned isl_local_space_offset(__isl_keep isl_local_space *ls, enum isl_dim_type type) { … } /* Return the position of the dimension of the given type and name * in "ls". * Return -1 if no such dimension can be found. */ int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls, enum isl_dim_type type, const char *name) { … } /* Does the given dimension have a name? */ isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls, enum isl_dim_type type, unsigned pos) { … } const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls, enum isl_dim_type type, unsigned pos) { … } isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls, enum isl_dim_type type, unsigned pos) { … } __isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls, enum isl_dim_type type, unsigned pos) { … } /* Return the argument of the integer division at position "pos" in "ls". * All local variables in "ls" are known to have a (complete) explicit * representation. */ static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos) { … } /* Return the argument of the integer division at position "pos" in "ls". * The integer division at that position is known to have a complete * explicit representation, but some of the others do not. * Remove them first because the domain of an isl_aff * is not allowed to have unknown local variables. */ static __isl_give isl_aff *drop_unknown_divs_and_extract_div( __isl_keep isl_local_space *ls, int pos) { … } /* Return the argument of the integer division at position "pos" in "ls". * The integer division is assumed to have a complete explicit * representation. If some of the other integer divisions * do not have an explicit representation, then they need * to be removed first because the domain of an isl_aff * is not allowed to have unknown local variables. */ __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls, int pos) { … } /* Return the space of "ls". */ __isl_keep isl_space *isl_local_space_peek_space(__isl_keep isl_local_space *ls) { … } __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls) { … } /* Return the space of "ls". * This may be either a copy or the space itself * if there is only one reference to "ls". * This allows the space to be modified inplace * if both the local space and its space have only a single reference. * The caller is not allowed to modify "ls" between this call and * a subsequent call to isl_local_space_restore_space. * The only exception is that isl_local_space_free can be called instead. */ __isl_give isl_space *isl_local_space_take_space(__isl_keep isl_local_space *ls) { … } /* Set the space of "ls" to "space", where the space of "ls" may be missing * due to a preceding call to isl_local_space_take_space. * However, in this case, "ls" only has a single reference and * then the call to isl_local_space_cow has no effect. */ __isl_give isl_local_space *isl_local_space_restore_space( __isl_take isl_local_space *ls, __isl_take isl_space *space) { … } /* Return the local variables of "ls". */ __isl_keep isl_local *isl_local_space_peek_local(__isl_keep isl_local_space *ls) { … } /* Return a copy of the local variables of "ls". */ __isl_keep isl_local *isl_local_space_get_local(__isl_keep isl_local_space *ls) { … } /* Return the local variables of "ls". * This may be either a copy or the local variables itself * if there is only one reference to "ls". * This allows the local variables to be modified inplace * if both the local space and its local variables have only a single reference. * The caller is not allowed to modify "ls" between this call and * the subsequent call to isl_local_space_restore_local. * The only exception is that isl_local_space_free can be called instead. */ static __isl_give isl_local *isl_local_space_take_local( __isl_keep isl_local_space *ls) { … } /* Set the local variables of "ls" to "local", * where the local variables of "ls" may be missing * due to a preceding call to isl_local_space_take_local. * However, in this case, "ls" only has a single reference and * then the call to isl_local_space_cow has no effect. */ static __isl_give isl_local_space *isl_local_space_restore_local( __isl_take isl_local_space *ls, __isl_take isl_local *local) { … } /* Replace the identifier of the tuple of type "type" by "id". */ __isl_give isl_local_space *isl_local_space_set_tuple_id( __isl_take isl_local_space *ls, enum isl_dim_type type, __isl_take isl_id *id) { … } __isl_give isl_local_space *isl_local_space_set_dim_name( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned pos, const char *s) { … } __isl_give isl_local_space *isl_local_space_set_dim_id( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned pos, __isl_take isl_id *id) { … } /* Construct a zero-dimensional local space with the given parameter domain. */ __isl_give isl_local_space *isl_local_space_set_from_params( __isl_take isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_reset_space( __isl_take isl_local_space *ls, __isl_take isl_space *space) { … } /* Reorder the dimensions of "ls" according to the given reordering. * The reordering r is assumed to have been extended with the local * variables, leaving them in the same order. */ __isl_give isl_local_space *isl_local_space_realign( __isl_take isl_local_space *ls, __isl_take isl_reordering *r) { … } __isl_give isl_local_space *isl_local_space_add_div( __isl_take isl_local_space *ls, __isl_take isl_vec *div) { … } __isl_give isl_local_space *isl_local_space_replace_divs( __isl_take isl_local_space *ls, __isl_take isl_mat *div) { … } /* Copy row "s" of "src" to row "d" of "dst", applying the expansion * defined by "exp". */ static void expand_row(__isl_keep isl_mat *dst, int d, __isl_keep isl_mat *src, int s, int *exp) { … } /* Compare (known) divs. * Return non-zero if at least one of the two divs is unknown. * In particular, if both divs are unknown, we respect their * current order. Otherwise, we sort the known div after the unknown * div only if the known div depends on the unknown div. */ static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j, unsigned n_row, unsigned n_col) { … } /* Call cmp_row for divs in a matrix. */ int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j) { … } /* Call cmp_row for divs in a basic map. */ static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j, unsigned total) { … } /* Sort the divs in "bmap". * * We first make sure divs are placed after divs on which they depend. * Then we perform a simple insertion sort based on the same ordering * that is used in isl_merge_divs. */ __isl_give isl_basic_map *isl_basic_map_sort_divs( __isl_take isl_basic_map *bmap) { … } /* Sort the divs in the basic maps of "map". */ __isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map) { … } /* Combine the two lists of divs into a single list. * For each row i in div1, exp1[i] is set to the position of the corresponding * row in the result. Similarly for div2 and exp2. * This function guarantees * exp1[i] >= i * exp1[i+1] > exp1[i] * For optimal merging, the two input list should have been sorted. */ __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2, int *exp1, int *exp2) { … } /* Swap divs "a" and "b" in "ls". */ __isl_give isl_local_space *isl_local_space_swap_div( __isl_take isl_local_space *ls, int a, int b) { … } /* Construct a local space that contains all the divs in either * "ls1" or "ls2". */ __isl_give isl_local_space *isl_local_space_intersect( __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2) { … } /* Is the local variable "div" of "ls" marked as not having * an explicit representation? * Note that even if this variable is not marked in this way and therefore * does have an explicit representation, this representation may still * depend (indirectly) on other local variables that do not * have an explicit representation. */ isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls, int div) { … } /* Does "ls" have a complete explicit representation for div "div"? */ isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div) { … } /* Does "ls" have an explicit representation for all local variables? */ isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_domain( __isl_take isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_range( __isl_take isl_local_space *ls) { … } /* Construct a local space for a map that has the given local * space as domain and that has a zero-dimensional range. */ __isl_give isl_local_space *isl_local_space_from_domain( __isl_take isl_local_space *ls) { … } __isl_give isl_local_space *isl_local_space_add_dims( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n) { … } /* Lift the basic set "bset", living in the space of "ls" * to live in a space with extra coordinates corresponding * to the local variables of "ls". */ __isl_give isl_basic_set *isl_local_space_lift_basic_set( __isl_take isl_local_space *ls, __isl_take isl_basic_set *bset) { … } /* Lift the set "set", living in the space of "ls" * to live in a space with extra coordinates corresponding * to the local variables of "ls". */ __isl_give isl_set *isl_local_space_lift_set(__isl_take isl_local_space *ls, __isl_take isl_set *set) { … } /* Remove common factor of non-constant terms and denominator. */ static __isl_give isl_local_space *normalize_div( __isl_take isl_local_space *ls, int div) { … } /* Exploit the equalities in "eq" to simplify the expressions of * the integer divisions in "ls". * The integer divisions in "ls" are assumed to appear as regular * dimensions in "eq". */ __isl_give isl_local_space *isl_local_space_substitute_equalities( __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq) { … } /* Plug in the affine expressions "subs" of length "subs_len" (including * the denominator and the constant term) into the variable at position "pos" * of the "n" div expressions starting at "first". * * Let i be the dimension to replace and let "subs" be of the form * * f/d * * Any integer division starting at "first" with a non-zero coefficient for i, * * floor((a i + g)/m) * * is replaced by * * floor((a f + d g)/(m d)) */ __isl_give isl_local_space *isl_local_space_substitute_seq( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len, int first, int n) { … } /* Plug in "subs" for dimension "type", "pos" in the integer divisions * of "ls". * * Let i be the dimension to replace and let "subs" be of the form * * f/d * * Any integer division with a non-zero coefficient for i, * * floor((a i + g)/m) * * is replaced by * * floor((a f + d g)/(m d)) */ __isl_give isl_local_space *isl_local_space_substitute( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs) { … } isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls, enum isl_dim_type type) { … } __isl_give isl_local_space *isl_local_space_drop_dims( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned first, unsigned n) { … } __isl_give isl_local_space *isl_local_space_insert_dims( __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned first, unsigned n) { … } /* Does the linear part of "constraint" correspond to * integer division "div" in "ls"? * * That is, given div = floor((c + f)/m), is the constraint of the form * * f - m d + c' >= 0 [sign = 1] * or * -f + m d + c'' >= 0 [sign = -1] * ? * If so, set *sign to the corresponding value. */ static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls, isl_int *constraint, unsigned div, int *sign) { … } /* Check if the constraints pointed to by "constraint" is a div * constraint corresponding to div "div" in "ls". * * That is, if div = floor(f/m), then check if the constraint is * * f - m d >= 0 * or * -(f-(m-1)) + m d >= 0 * * First check if the linear part is of the right form and * then check the constant term. */ isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls, isl_int *constraint, unsigned div) { … } /* Is the constraint pointed to by "constraint" one * of an equality that corresponds to integer division "div" in "ls"? * * 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_local_space_is_div_equality(__isl_keep isl_local_space *ls, isl_int *constraint, unsigned div) { … } /* * Set active[i] to 1 if the dimension at position i is involved * in the linear expression l. */ int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l) { … } /* Given a local space "ls" of a set, create a local space * for the lift of the set. In particular, the result * is of the form [dim -> local[..]], with ls->div->n_row variables in the * range of the wrapped map. */ __isl_give isl_local_space *isl_local_space_lift( __isl_take isl_local_space *ls) { … } /* Construct a basic map that maps a set living in local space "ls" * to the corresponding lifted local space. */ __isl_give isl_basic_map *isl_local_space_lifting( __isl_take isl_local_space *ls) { … } /* Compute the preimage of "ls" under the function represented by "ma". * In other words, plug in "ma" in "ls". The result is a local space * that is part of the domain space of "ma". * * If the divs in "ls" are represented as * * floor((a_i(p) + b_i x + c_i(divs))/n_i) * * and ma is represented by * * x = D(p) + F(y) + G(divs') * * then the resulting divs are * * floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i) * * We first copy over the divs from "ma" and then * we add the modified divs from "ls". */ __isl_give isl_local_space *isl_local_space_preimage_multi_aff( __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma) { … } /* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls" * to dimensions of "dst_type" at "dst_pos". * * Moving to/from local dimensions is not allowed. * We currently assume that the dimension type changes. */ __isl_give isl_local_space *isl_local_space_move_dims( __isl_take isl_local_space *ls, enum isl_dim_type dst_type, unsigned dst_pos, enum isl_dim_type src_type, unsigned src_pos, unsigned n) { … } /* Remove any internal structure of the domain of "ls". * If there is any such internal structure in the input, * then the name of the corresponding space is also removed. */ __isl_give isl_local_space *isl_local_space_flatten_domain( __isl_take isl_local_space *ls) { … } /* Remove any internal structure of the range of "ls". * If there is any such internal structure in the input, * then the name of the corresponding space is also removed. */ __isl_give isl_local_space *isl_local_space_flatten_range( __isl_take isl_local_space *ls) { … } /* Given the local space "ls" of a map, return the local space of a set * that lives in a space that wraps the space of "ls" and that has * the same divs. */ __isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls) { … } /* Lift the point "pnt", living in the (set) space of "ls" * to live in a space with extra coordinates corresponding * to the local variables of "ls". */ __isl_give isl_point *isl_local_space_lift_point(__isl_take isl_local_space *ls, __isl_take isl_point *pnt) { … }
Codebase Browser
llvm