/* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2014 INRIA Rocquencourt * * 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 Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, * B.P. 105 - 78153 Le Chesnay, France */ #include <isl_ctx_private.h> #include <isl_map_private.h> #include <isl_lp_private.h> #include <isl/map.h> #include <isl_mat_private.h> #include <isl_vec_private.h> #include <isl/set.h> #include <isl_seq.h> #include <isl_options_private.h> #include "isl_equalities.h" #include "isl_tab.h" #include <isl_sort.h> #include <bset_to_bmap.c> #include <bset_from_bmap.c> #include <set_to_map.c> static __isl_give isl_basic_set *uset_convex_hull_wrap_bounded( __isl_take isl_set *set); /* Remove redundant * constraints. If the minimal value along the normal of a constraint * is the same if the constraint is removed, then the constraint is redundant. * * Since some constraints may be mutually redundant, sort the constraints * first such that constraints that involve existentially quantified * variables are considered for removal before those that do not. * The sorting is also needed for the use in map_simple_hull. * * Note that isl_tab_detect_implicit_equalities may also end up * marking some constraints as redundant. Make sure the constraints * are preserved and undo those marking such that isl_tab_detect_redundant * can consider the constraints in the sorted order. * * Alternatively, we could have intersected the basic map with the * corresponding equality and then checked if the dimension was that * of a facet. */ __isl_give isl_basic_map *isl_basic_map_remove_redundancies( __isl_take isl_basic_map *bmap) { … } __isl_give isl_basic_set *isl_basic_set_remove_redundancies( __isl_take isl_basic_set *bset) { … } /* Remove redundant constraints in each of the basic maps. */ __isl_give isl_map *isl_map_remove_redundancies(__isl_take isl_map *map) { … } __isl_give isl_set *isl_set_remove_redundancies(__isl_take isl_set *set) { … } /* Check if the set set is bound in the direction of the affine * constraint c and if so, set the constant term such that the * resulting constraint is a bounding constraint for the set. */ static isl_bool uset_is_bound(__isl_keep isl_set *set, isl_int *c, unsigned len) { … } static __isl_give isl_set *isl_set_add_basic_set_equality( __isl_take isl_set *set, isl_int *c) { … } /* Given a union of basic sets, construct the constraints for wrapping * a facet around one of its ridges. * In particular, if each of n the d-dimensional basic sets i in "set" * contains the origin, satisfies the constraints x_1 >= 0 and x_2 >= 0 * and is defined by the constraints * [ 1 ] * A_i [ x ] >= 0 * * then the resulting set is of dimension n*(1+d) and has as constraints * * [ a_i ] * A_i [ x_i ] >= 0 * * a_i >= 0 * * \sum_i x_{i,1} = 1 */ static __isl_give isl_basic_set *wrap_constraints(__isl_keep isl_set *set) { … } /* Given a facet "facet" of the convex hull of "set" and a facet "ridge" * of that facet, compute the other facet of the convex hull that contains * the ridge. * * We first transform the set such that the facet constraint becomes * * x_1 >= 0 * * I.e., the facet lies in * * x_1 = 0 * * and on that facet, the constraint that defines the ridge is * * x_2 >= 0 * * (This transformation is not strictly needed, all that is needed is * that the ridge contains the origin.) * * Since the ridge contains the origin, the cone of the convex hull * will be of the form * * x_1 >= 0 * x_2 >= a x_1 * * with this second constraint defining the new facet. * The constant a is obtained by settting x_1 in the cone of the * convex hull to 1 and minimizing x_2. * Now, each element in the cone of the convex hull is the sum * of elements in the cones of the basic sets. * If a_i is the dilation factor of basic set i, then the problem * we need to solve is * * min \sum_i x_{i,2} * st * \sum_i x_{i,1} = 1 * a_i >= 0 * [ a_i ] * A [ x_i ] >= 0 * * with * [ 1 ] * A_i [ x_i ] >= 0 * * the constraints of each (transformed) basic set. * If a = n/d, then the constraint defining the new facet (in the transformed * space) is * * -n x_1 + d x_2 >= 0 * * In the original space, we need to take the same combination of the * corresponding constraints "facet" and "ridge". * * If a = -infty = "-1/0", then we just return the original facet constraint. * This means that the facet is unbounded, but has a bounded intersection * with the union of sets. */ isl_int *isl_set_wrap_facet(__isl_keep isl_set *set, isl_int *facet, isl_int *ridge) { … } /* Compute the constraint of a facet of "set". * * We first compute the intersection with a bounding constraint * that is orthogonal to one of the coordinate axes. * If the affine hull of this intersection has only one equality, * we have found a facet. * Otherwise, we wrap the current bounding constraint around * one of the equalities of the face (one that is not equal to * the current bounding constraint). * This process continues until we have found a facet. * The dimension of the intersection increases by at least * one on each iteration, so termination is guaranteed. */ static __isl_give isl_mat *initial_facet_constraint(__isl_keep isl_set *set) { … } /* Given the bounding constraint "c" of a facet of the convex hull of "set", * compute a hyperplane description of the facet, i.e., compute the facets * of the facet. * * We compute an affine transformation that transforms the constraint * * [ 1 ] * c [ x ] = 0 * * to the constraint * * z_1 = 0 * * by computing the right inverse U of a matrix that starts with the rows * * [ 1 0 ] * [ c ] * * Then * [ 1 ] [ 1 ] * [ x ] = U [ z ] * and * [ 1 ] [ 1 ] * [ z ] = Q [ x ] * * with Q = U^{-1} * Since z_1 is zero, we can drop this variable as well as the corresponding * column of U to obtain * * [ 1 ] [ 1 ] * [ x ] = U' [ z' ] * and * [ 1 ] [ 1 ] * [ z' ] = Q' [ x ] * * with Q' equal to Q, but without the corresponding row. * After computing the facets of the facet in the z' space, * we convert them back to the x space through Q. */ static __isl_give isl_basic_set *compute_facet(__isl_keep isl_set *set, isl_int *c) { … } /* Given an initial facet constraint, compute the remaining facets. * We do this by running through all facets found so far and computing * the adjacent facets through wrapping, adding those facets that we * hadn't already found before. * * For each facet we have found so far, we first compute its facets * in the resulting convex hull. That is, we compute the ridges * of the resulting convex hull contained in the facet. * We also compute the corresponding facet in the current approximation * of the convex hull. There is no need to wrap around the ridges * in this facet since that would result in a facet that is already * present in the current approximation. * * This function can still be significantly optimized by checking which of * the facets of the basic sets are also facets of the convex hull and * using all the facets so far to help in constructing the facets of the * facets * and/or * using the technique in section "3.1 Ridge Generation" of * "Extended Convex Hull" by Fukuda et al. */ static __isl_give isl_basic_set *extend(__isl_take isl_basic_set *hull, __isl_keep isl_set *set) { … } /* Special case for computing the convex hull of a one dimensional set. * We simply collect the lower and upper bounds of each basic set * and the biggest of those. */ static __isl_give isl_basic_set *convex_hull_1d(__isl_take isl_set *set) { … } static __isl_give isl_basic_set *convex_hull_0d(__isl_take isl_set *set) { … } /* Compute the convex hull of a pair of basic sets without any parameters or * integer divisions using Fourier-Motzkin elimination. * The convex hull is the set of all points that can be written as * the sum of points from both basic sets (in homogeneous coordinates). * We set up the constraints in a space with dimensions for each of * the three sets and then project out the dimensions corresponding * to the two original basic sets, retaining only those corresponding * to the convex hull. */ static __isl_give isl_basic_set *convex_hull_pair_elim( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) { … } /* Is the set bounded for each value of the parameters? */ isl_bool isl_basic_set_is_bounded(__isl_keep isl_basic_set *bset) { … } /* Is the image bounded for each value of the parameters and * the domain variables? */ isl_bool isl_basic_map_image_is_bounded(__isl_keep isl_basic_map *bmap) { … } /* Is the set bounded for each value of the parameters? */ isl_bool isl_set_is_bounded(__isl_keep isl_set *set) { … } /* Compute the lineality space of the convex hull of bset1 and bset2. * * We first compute the intersection of the recession cone of bset1 * with the negative of the recession cone of bset2 and then compute * the linear hull of the resulting cone. */ static __isl_give isl_basic_set *induced_lineality_space( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) { … } static __isl_give isl_basic_set *uset_convex_hull(__isl_take isl_set *set); /* Given a set and a linear space "lin" of dimension n > 0, * project the linear space from the set, compute the convex hull * and then map the set back to the original space. * * Let * * M x = 0 * * describe the linear space. We first compute the Hermite normal * form H = M U of M = H Q, to obtain * * H Q x = 0 * * The last n rows of H will be zero, so the last n variables of x' = Q x * are the one we want to project out. We do this by transforming each * basic set A x >= b to A U x' >= b and then removing the last n dimensions. * After computing the convex hull in x'_1, i.e., A' x'_1 >= b', * we transform the hull back to the original space as A' Q_1 x >= b', * with Q_1 all but the last n rows of Q. */ static __isl_give isl_basic_set *modulo_lineality(__isl_take isl_set *set, __isl_take isl_basic_set *lin) { … } /* Given two polyhedra with as constraints h_{ij} x >= 0 in homegeneous space, * set up an LP for solving * * \sum_j \alpha_{1j} h_{1j} = \sum_j \alpha_{2j} h_{2j} * * \alpha{i0} corresponds to the (implicit) positivity constraint 1 >= 0 * The next \alpha{ij} correspond to the equalities and come in pairs. * The final \alpha{ij} correspond to the inequalities. */ static __isl_give isl_basic_set *valid_direction_lp( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) { … } /* Compute a vector s in the homogeneous space such that <s, r> > 0 * for all rays in the homogeneous space of the two cones that correspond * to the input polyhedra bset1 and bset2. * * We compute s as a vector that satisfies * * s = \sum_j \alpha_{ij} h_{ij} for i = 1,2 (*) * * with h_{ij} the normals of the facets of polyhedron i * (including the "positivity constraint" 1 >= 0) and \alpha_{ij} * strictly positive numbers. For simplicity we impose \alpha_{ij} >= 1. * We first set up an LP with as variables the \alpha{ij}. * In this formulation, for each polyhedron i, * the first constraint is the positivity constraint, followed by pairs * of variables for the equalities, followed by variables for the inequalities. * We then simply pick a feasible solution and compute s using (*). * * Note that we simply pick any valid direction and make no attempt * to pick a "good" or even the "best" valid direction. */ static __isl_give isl_vec *valid_direction( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) { … } /* Given a polyhedron b_i + A_i x >= 0 and a map T = S^{-1}, * compute b_i' + A_i' x' >= 0, with * * [ b_i A_i ] [ y' ] [ y' ] * [ 1 0 ] S^{-1} [ x' ] >= 0 or [ b_i' A_i' ] [ x' ] >= 0 * * In particular, add the "positivity constraint" and then perform * the mapping. */ static __isl_give isl_basic_set *homogeneous_map(__isl_take isl_basic_set *bset, __isl_take isl_mat *T) { … } /* Compute the convex hull of a pair of basic sets without any parameters or * integer divisions, where the convex hull is known to be pointed, * but the basic sets may be unbounded. * * We turn this problem into the computation of a convex hull of a pair * _bounded_ polyhedra by "changing the direction of the homogeneous * dimension". This idea is due to Matthias Koeppe. * * Consider the cones in homogeneous space that correspond to the * input polyhedra. The rays of these cones are also rays of the * polyhedra if the coordinate that corresponds to the homogeneous * dimension is zero. That is, if the inner product of the rays * with the homogeneous direction is zero. * The cones in the homogeneous space can also be considered to * correspond to other pairs of polyhedra by chosing a different * homogeneous direction. To ensure that both of these polyhedra * are bounded, we need to make sure that all rays of the cones * correspond to vertices and not to rays. * Let s be a direction such that <s, r> > 0 for all rays r of both cones. * Then using s as a homogeneous direction, we obtain a pair of polytopes. * The vector s is computed in valid_direction. * * Note that we need to consider _all_ rays of the cones and not just * the rays that correspond to rays in the polyhedra. If we were to * only consider those rays and turn them into vertices, then we * may inadvertently turn some vertices into rays. * * The standard homogeneous direction is the unit vector in the 0th coordinate. * We therefore transform the two polyhedra such that the selected * direction is mapped onto this standard direction and then proceed * with the normal computation. * Let S be a non-singular square matrix with s as its first row, * then we want to map the polyhedra to the space * * [ y' ] [ y ] [ y ] [ y' ] * [ x' ] = S [ x ] i.e., [ x ] = S^{-1} [ x' ] * * We take S to be the unimodular completion of s to limit the growth * of the coefficients in the following computations. * * Let b_i + A_i x >= 0 be the constraints of polyhedron i. * We first move to the homogeneous dimension * * b_i y + A_i x >= 0 [ b_i A_i ] [ y ] [ 0 ] * y >= 0 or [ 1 0 ] [ x ] >= [ 0 ] * * Then we change directoin * * [ b_i A_i ] [ y' ] [ y' ] * [ 1 0 ] S^{-1} [ x' ] >= 0 or [ b_i' A_i' ] [ x' ] >= 0 * * Then we compute the convex hull of the polytopes b_i' + A_i' x' >= 0 * resulting in b' + A' x' >= 0, which we then convert back * * [ y ] [ y ] * [ b' A' ] S [ x ] >= 0 or [ b A ] [ x ] >= 0 * * The polyhedron b + A x >= 0 is then the convex hull of the input polyhedra. */ static __isl_give isl_basic_set *convex_hull_pair_pointed( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) { … } static __isl_give isl_basic_set *uset_convex_hull_wrap(__isl_take isl_set *set); static __isl_give isl_basic_set *modulo_affine_hull( __isl_take isl_set *set, __isl_take isl_basic_set *affine_hull); /* Compute the convex hull of a pair of basic sets without any parameters or * integer divisions. * * This function is called from uset_convex_hull_unbounded, which * means that the complete convex hull is unbounded. Some pairs * of basic sets may still be bounded, though. * They may even lie inside a lower dimensional space, in which * case they need to be handled inside their affine hull since * the main algorithm assumes that the result is full-dimensional. * * If the convex hull of the two basic sets would have a non-trivial * lineality space, we first project out this lineality space. */ static __isl_give isl_basic_set *convex_hull_pair( __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2) { … } /* Compute the lineality space of a basic set. * We basically just drop the constants and turn every inequality * into an equality. * Any explicit representations of local variables are removed * because they may no longer be valid representations * in the lineality space. */ __isl_give isl_basic_set *isl_basic_set_lineality_space( __isl_take isl_basic_set *bset) { … } /* Compute the (linear) hull of the lineality spaces of the basic sets in the * set "set". */ __isl_give isl_basic_set *isl_set_combined_lineality_space( __isl_take isl_set *set) { … } /* Compute the convex hull of a set without any parameters or * integer divisions. * In each step, we combined two basic sets until only one * basic set is left. * The input basic sets are assumed not to have a non-trivial * lineality space. If any of the intermediate results has * a non-trivial lineality space, it is projected out. */ static __isl_give isl_basic_set *uset_convex_hull_unbounded( __isl_take isl_set *set) { … } /* Compute an initial hull for wrapping containing a single initial * facet. * This function assumes that the given set is bounded. */ static __isl_give isl_basic_set *initial_hull(__isl_take isl_basic_set *hull, __isl_keep isl_set *set) { … } struct max_constraint { … }; static isl_bool max_constraint_equal(const void *entry, const void *val) { … } static isl_stat update_constraint(struct isl_ctx *ctx, struct isl_hash_table *table, isl_int *con, unsigned len, int n, int ineq) { … } /* Check whether the constraint hash table "table" contains the constraint * "con". */ static isl_bool has_constraint(struct isl_ctx *ctx, struct isl_hash_table *table, isl_int *con, unsigned len, int n) { … } /* Are the constraints of "bset" known to be facets? * If there are any equality constraints, then they are not. * If there may be redundant constraints, then those * redundant constraints are not facets. */ static isl_bool has_facets(__isl_keep isl_basic_set *bset) { … } /* Check for inequality constraints of a basic set without equalities * or redundant constraints * such that the same or more stringent copies of the constraint appear * in all of the basic sets. Such constraints are necessarily facet * constraints of the convex hull. * * If the resulting basic set is by chance identical to one of * the basic sets in "set", then we know that this basic set contains * all other basic sets and is therefore the convex hull of set. * In this case we set *is_hull to 1. */ static __isl_give isl_basic_set *common_constraints( __isl_take isl_basic_set *hull, __isl_keep isl_set *set, int *is_hull) { … } /* Create a template for the convex hull of "set" and fill it up * obvious facet constraints, if any. If the result happens to * be the convex hull of "set" then *is_hull is set to 1. */ static __isl_give isl_basic_set *proto_hull(__isl_keep isl_set *set, int *is_hull) { … } static __isl_give isl_basic_set *uset_convex_hull_wrap(__isl_take isl_set *set) { … } /* Compute the convex hull of a set without any parameters or * integer divisions. Depending on whether the set is bounded, * we pass control to the wrapping based convex hull or * the Fourier-Motzkin elimination based convex hull. * We also handle a few special cases before checking the boundedness. */ static __isl_give isl_basic_set *uset_convex_hull(__isl_take isl_set *set) { … } /* This is the core procedure, where "set" is a "pure" set, i.e., * without parameters or divs and where the convex hull of set is * known to be full-dimensional. */ static __isl_give isl_basic_set *uset_convex_hull_wrap_bounded( __isl_take isl_set *set) { … } /* Compute the convex hull of set "set" with affine hull "affine_hull", * We first remove the equalities (transforming the set), compute the * convex hull of the transformed set and then add the equalities back * (after performing the inverse transformation. */ static __isl_give isl_basic_set *modulo_affine_hull( __isl_take isl_set *set, __isl_take isl_basic_set *affine_hull) { … } /* Return an empty basic map living in the same space as "map". */ static __isl_give isl_basic_map *replace_map_by_empty_basic_map( __isl_take isl_map *map) { … } /* Compute the convex hull of a map. * * The implementation was inspired by "Extended Convex Hull" by Fukuda et al., * specifically, the wrapping of facets to obtain new facets. */ __isl_give isl_basic_map *isl_map_convex_hull(__isl_take isl_map *map) { … } __isl_give isl_basic_set *isl_set_convex_hull(__isl_take isl_set *set) { … } __isl_give isl_basic_map *isl_map_polyhedral_hull(__isl_take isl_map *map) { … } __isl_give isl_basic_set *isl_set_polyhedral_hull(__isl_take isl_set *set) { … } struct sh_data_entry { … }; /* Holds the data needed during the simple hull computation. * In particular, * n the number of basic sets in the original set * hull_table a hash table of already computed constraints * in the simple hull * p for each basic set, * table a hash table of the constraints * tab the tableau corresponding to the basic set */ struct sh_data { … }; static void sh_data_free(struct sh_data *data) { … } struct ineq_cmp_data { … }; static isl_bool has_ineq(const void *entry, const void *val) { … } static int hash_ineq(struct isl_ctx *ctx, struct isl_hash_table *table, isl_int *ineq, unsigned len) { … } /* Fill hash table "table" with the constraints of "bset". * Equalities are added as two inequalities. * The value in the hash table is a pointer to the (in)equality of "bset". */ static isl_stat hash_basic_set(struct isl_hash_table *table, __isl_keep isl_basic_set *bset) { … } static struct sh_data *sh_data_alloc(__isl_keep isl_set *set, unsigned n_ineq) { … } /* Check if inequality "ineq" is a bound for basic set "j" or if * it can be relaxed (by increasing the constant term) to become * a bound for that basic set. In the latter case, the constant * term is updated. * Relaxation of the constant term is only allowed if "shift" is set. * * Return 1 if "ineq" is a bound * 0 if "ineq" may attain arbitrarily small values on basic set "j" * -1 if some error occurred */ static int is_bound(struct sh_data *data, __isl_keep isl_set *set, int j, isl_int *ineq, int shift) { … } /* Set the constant term of "ineq" to the maximum of those of the constraints * in the basic sets of "set" following "i" that are parallel to "ineq". * That is, if any of the basic sets of "set" following "i" have a more * relaxed copy of "ineq", then replace "ineq" by the most relaxed copy. * "c_hash" is the hash value of the linear part of "ineq". * "v" has been set up for use by has_ineq. * * Note that the two inequality constraints corresponding to an equality are * represented by the same inequality constraint in data->p[j].table * (but with different hash values). This means the constraint (or at * least its constant term) may need to be temporarily negated to get * the actually hashed constraint. */ static isl_stat set_max_constant_term(struct sh_data *data, __isl_keep isl_set *set, int i, isl_int *ineq, uint32_t c_hash, struct ineq_cmp_data *v) { … } /* Check if inequality "ineq" from basic set "i" is or can be relaxed to * become a bound on the whole set. If so, add the (relaxed) inequality * to "hull". Relaxation is only allowed if "shift" is set. * * We first check if "hull" already contains a translate of the inequality. * If so, we are done. * Then, we check if any of the previous basic sets contains a translate * of the inequality. If so, then we have already considered this * inequality and we are done. * Otherwise, for each basic set other than "i", we check if the inequality * is a bound on the basic set, but first replace the constant term * by the maximal value of any translate of the inequality in any * of the following basic sets. * For previous basic sets, we know that they do not contain a translate * of the inequality, so we directly call is_bound. * For following basic sets, we first check if a translate of the * inequality appears in its description. If so, the constant term * of the inequality has already been updated with respect to this * translate and the inequality is therefore known to be a bound * of this basic set. */ static __isl_give isl_basic_set *add_bound(__isl_take isl_basic_set *hull, struct sh_data *data, __isl_keep isl_set *set, int i, isl_int *ineq, int shift) { … } /* Check if any inequality from basic set "i" is or can be relaxed to * become a bound on the whole set. If so, add the (relaxed) inequality * to "hull". Relaxation is only allowed if "shift" is set. */ static __isl_give isl_basic_set *add_bounds(__isl_take isl_basic_set *bset, struct sh_data *data, __isl_keep isl_set *set, int i, int shift) { … } /* Compute a superset of the convex hull of set that is described * by only (translates of) the constraints in the constituents of set. * Translation is only allowed if "shift" is set. */ static __isl_give isl_basic_set *uset_simple_hull(__isl_take isl_set *set, int shift) { … } /* Compute a superset of the convex hull of map that is described * by only (translates of) the constraints in the constituents of map. * Handle trivial cases where map is NULL or contains at most one disjunct. */ static __isl_give isl_basic_map *map_simple_hull_trivial( __isl_take isl_map *map) { … } /* Return a copy of the simple hull cached inside "map". * "shift" determines whether to return the cached unshifted or shifted * simple hull. */ static __isl_give isl_basic_map *cached_simple_hull(__isl_take isl_map *map, int shift) { … } /* Compute a superset of the convex hull of map that is described * by only (translates of) the constraints in the constituents of map. * Translation is only allowed if "shift" is set. * * The constraints are sorted while removing redundant constraints * in order to indicate a preference of which constraints should * be preserved. In particular, pairs of constraints that are * sorted together are preferred to either both be preserved * or both be removed. The sorting is performed inside * isl_basic_map_remove_redundancies. * * The result of the computation is stored in map->cached_simple_hull[shift] * such that it can be reused in subsequent calls. The cache is cleared * whenever the map is modified (in isl_map_cow). * Note that the results need to be stored in the input map for there * to be any chance that they may get reused. In particular, they * are stored in a copy of the input map that is saved before * the integer division alignment. */ static __isl_give isl_basic_map *map_simple_hull(__isl_take isl_map *map, int shift) { … } /* Compute a superset of the convex hull of map that is described * by only translates of the constraints in the constituents of map. */ __isl_give isl_basic_map *isl_map_simple_hull(__isl_take isl_map *map) { … } __isl_give isl_basic_set *isl_set_simple_hull(__isl_take isl_set *set) { … } /* Compute a superset of the convex hull of map that is described * by only the constraints in the constituents of map. */ __isl_give isl_basic_map *isl_map_unshifted_simple_hull( __isl_take isl_map *map) { … } __isl_give isl_basic_set *isl_set_unshifted_simple_hull( __isl_take isl_set *set) { … } /* Drop all inequalities from "bmap1" that do not also appear in "bmap2". * A constraint that appears with different constant terms * in "bmap1" and "bmap2" is also kept, with the least restrictive * (i.e., greatest) constant term. * "bmap1" and "bmap2" are assumed to have the same (known) * integer divisions. * The constraints of both "bmap1" and "bmap2" are assumed * to have been sorted using isl_basic_map_sort_constraints. * * Run through the inequality constraints of "bmap1" and "bmap2" * in sorted order. * Each constraint of "bmap1" without a matching constraint in "bmap2" * is removed. * If a match is found, the constraint is kept. If needed, the constant * term of the constraint is adjusted. */ static __isl_give isl_basic_map *select_shared_inequalities( __isl_take isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2) { … } /* Drop all equalities from "bmap1" that do not also appear in "bmap2". * "bmap1" and "bmap2" are assumed to have the same (known) * integer divisions. * * Run through the equality constraints of "bmap1" and "bmap2". * Each constraint of "bmap1" without a matching constraint in "bmap2" * is removed. */ static __isl_give isl_basic_map *select_shared_equalities( __isl_take isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2) { … } /* Compute a superset of "bmap1" and "bmap2" that is described * by only the constraints that appear in both "bmap1" and "bmap2". * * First drop constraints that involve unknown integer divisions * since it is not trivial to check whether two such integer divisions * in different basic maps are the same. * Then align the remaining (known) divs and sort the constraints. * Finally drop all inequalities and equalities from "bmap1" that * do not also appear in "bmap2". */ __isl_give isl_basic_map *isl_basic_map_plain_unshifted_simple_hull( __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2) { … } /* Compute a superset of the convex hull of "map" that is described * by only the constraints in the constituents of "map". * In particular, the result is composed of constraints that appear * in each of the basic maps of "map" * * Constraints that involve unknown integer divisions are dropped * since it is not trivial to check whether two such integer divisions * in different basic maps are the same. * * The hull is initialized from the first basic map and then * updated with respect to the other basic maps in turn. */ __isl_give isl_basic_map *isl_map_plain_unshifted_simple_hull( __isl_take isl_map *map) { … } /* Compute a superset of the convex hull of "set" that is described * by only the constraints in the constituents of "set". * In particular, the result is composed of constraints that appear * in each of the basic sets of "set" */ __isl_give isl_basic_set *isl_set_plain_unshifted_simple_hull( __isl_take isl_set *set) { … } /* Check if "ineq" is a bound on "set" and, if so, add it to "hull". * * For each basic set in "set", we first check if the basic set * contains a translate of "ineq". If this translate is more relaxed, * then we assume that "ineq" is not a bound on this basic set. * Otherwise, we know that it is a bound. * If the basic set does not contain a translate of "ineq", then * we call is_bound to perform the test. */ static __isl_give isl_basic_set *add_bound_from_constraint( __isl_take isl_basic_set *hull, struct sh_data *data, __isl_keep isl_set *set, isl_int *ineq) { … } /* Compute a superset of the convex hull of "set" that is described * by only some of the "n_ineq" constraints in the list "ineq", where "set" * has no parameters or integer divisions. * * The inequalities in "ineq" are assumed to have been sorted such * that constraints with the same linear part appear together and * that among constraints with the same linear part, those with * smaller constant term appear first. * * We reuse the same data structure that is used by uset_simple_hull, * but we do not need the hull table since we will not consider the * same constraint more than once. We therefore allocate it with zero size. * * We run through the constraints and try to add them one by one, * skipping identical constraints. If we have added a constraint and * the next constraint is a more relaxed translate, then we skip this * next constraint as well. */ static __isl_give isl_basic_set *uset_unshifted_simple_hull_from_constraints( __isl_take isl_set *set, int n_ineq, isl_int **ineq) { … } /* Collect pointers to all the inequalities in the elements of "list" * in "ineq". For equalities, store both a pointer to the equality and * a pointer to its opposite, which is first copied to "mat". * "ineq" and "mat" are assumed to have been preallocated to the right size * (the number of inequalities + 2 times the number of equalites and * the number of equalities, respectively). */ static __isl_give isl_mat *collect_inequalities(__isl_take isl_mat *mat, __isl_keep isl_basic_set_list *list, isl_int **ineq) { … } /* Comparison routine for use as an isl_sort callback. * * Constraints with the same linear part are sorted together and * among constraints with the same linear part, those with smaller * constant term are sorted first. */ static int cmp_ineq(const void *a, const void *b, void *arg) { … } /* Compute a superset of the convex hull of "set" that is described * by only constraints in the elements of "list", where "set" has * no parameters or integer divisions. * * We collect all the constraints in those elements and then * sort the constraints such that constraints with the same linear part * are sorted together and that those with smaller constant term are * sorted first. */ static __isl_give isl_basic_set *uset_unshifted_simple_hull_from_basic_set_list( __isl_take isl_set *set, __isl_take isl_basic_set_list *list) { … } /* Compute a superset of the convex hull of "map" that is described * by only constraints in the elements of "list". * * If the list is empty, then we can only describe the universe set. * If the input map is empty, then all constraints are valid, so * we return the intersection of the elements in "list". * * Otherwise, we align all divs and temporarily treat them * as regular variables, computing the unshifted simple hull in * uset_unshifted_simple_hull_from_basic_set_list. */ static __isl_give isl_basic_map *map_unshifted_simple_hull_from_basic_map_list( __isl_take isl_map *map, __isl_take isl_basic_map_list *list) { … } /* Return a sequence of the basic maps that make up the maps in "list". */ static __isl_give isl_basic_map_list *collect_basic_maps( __isl_take isl_map_list *list) { … } /* Compute a superset of the convex hull of "map" that is described * by only constraints in the elements of "list". * * If "map" is the universe, then the convex hull (and therefore * any superset of the convexhull) is the universe as well. * * Otherwise, we collect all the basic maps in the map list and * continue with map_unshifted_simple_hull_from_basic_map_list. */ __isl_give isl_basic_map *isl_map_unshifted_simple_hull_from_map_list( __isl_take isl_map *map, __isl_take isl_map_list *list) { … } /* Compute a superset of the convex hull of "set" that is described * by only constraints in the elements of "list". */ __isl_give isl_basic_set *isl_set_unshifted_simple_hull_from_set_list( __isl_take isl_set *set, __isl_take isl_set_list *list) { … } /* Given a set "set", return parametric bounds on the dimension "dim". */ static __isl_give isl_basic_set *set_bounds(__isl_keep isl_set *set, int dim) { … } /* Computes a "simple hull" and then check if each dimension in the * resulting hull is bounded by a symbolic constant. If not, the * hull is intersected with the corresponding bounds on the whole set. */ __isl_give isl_basic_set *isl_set_bounded_simple_hull(__isl_take isl_set *set) { … }
Codebase Browser
llvm