/* * Copyright 2010 INRIA Saclay * * 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 */ #include <isl_map_private.h> #include <isl_aff_private.h> #include <isl/set.h> #include <isl_seq.h> #include <isl_tab.h> #include <isl_space_private.h> #include <isl_morph.h> #include <isl_vertices_private.h> #include <isl_mat_private.h> #include <isl_vec_private.h> #define SELECTED … #define DESELECTED … #define UNSELECTED … static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset, __isl_take isl_vertices *vertices); __isl_give isl_vertices *isl_vertices_copy(__isl_keep isl_vertices *vertices) { … } __isl_null isl_vertices *isl_vertices_free(__isl_take isl_vertices *vertices) { … } struct isl_vertex_list { … }; static struct isl_vertex_list *free_vertex_list(struct isl_vertex_list *list) { … } static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_set *bset, int n_vertices, struct isl_vertex_list *list) { … } /* Prepend a vertex to the linked list "list" based on the equalities in "tab". * Return isl_bool_true if the vertex was actually added and * isl_bool_false otherwise. * In particular, vertices with a lower-dimensional activity domain are * not added to the list because they would not be included in any chamber. * Return isl_bool_error on error. */ static isl_bool add_vertex(struct isl_vertex_list **list, __isl_keep isl_basic_set *bset, struct isl_tab *tab) { … } /* Compute the parametric vertices and the chamber decomposition * of an empty parametric polytope. */ static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset) { … } /* Compute the parametric vertices and the chamber decomposition * of the parametric polytope defined using the same constraints * as "bset" in the 0D case. * There is exactly one 0D vertex and a single chamber containing * the vertex. */ static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset) { … } /* Is the row pointed to by "f" linearly independent of the "n" first * rows in "facets"? */ static isl_bool is_independent(__isl_keep isl_mat *facets, int n, isl_int *f) { … } /* Check whether we can select constraint "level", given the current selection * reflected by facets in "tab", the rows of "facets" and the earlier * "selected" elements of "selection". * * If the constraint is (strictly) redundant in the tableau, selecting it would * result in an empty tableau, so it can't be selected. * If the set variable part of the constraint is not linearly independent * of the set variable parts of the already selected constraints, * the constraint cannot be selected. * If selecting the constraint results in an empty tableau, the constraint * cannot be selected. * Finally, if selecting the constraint results in some explicitly * deselected constraints turning into equalities, then the corresponding * vertices have already been generated, so the constraint cannot be selected. */ static isl_bool can_select(__isl_keep isl_basic_set *bset, int level, struct isl_tab *tab, __isl_keep isl_mat *facets, int selected, int *selection) { … } /* Compute the parametric vertices and the chamber decomposition * of a parametric polytope that is not full-dimensional. * * Simply map the parametric polytope to a lower dimensional space * and map the resulting vertices back. */ static __isl_give isl_vertices *lower_dim_vertices( __isl_take isl_basic_set *bset) { … } /* Compute the parametric vertices and the chamber decomposition * of a parametric polytope "bset" that is not full-dimensional. * Additionally, free both "copy" and "tab". */ static __isl_give isl_vertices *lower_dim_vertices_free( __isl_take isl_basic_set *bset, __isl_take isl_basic_set *copy, struct isl_tab *tab) { … } /* Detect implicit equality constraints in "bset" using the tableau * representation "tab". * Return a copy of "bset" with the implicit equality constraints * made explicit, leaving the original "bset" unmodified. */ static __isl_give isl_basic_set *detect_implicit_equality_constraints( __isl_keep isl_basic_set *bset, struct isl_tab *tab) { … } /* Compute the parametric vertices and the chamber decomposition * of the parametric polytope defined using the same constraints * as "bset". "bset" is assumed to have no existentially quantified * variables. * * The vertices themselves are computed in a fairly simplistic way. * We simply run through all combinations of d constraints, * with d the number of set variables, and check if those d constraints * define a vertex. To avoid the generation of duplicate vertices, * which may happen if a vertex is defined by more than d constraints, * we make sure we only generate the vertex for the d constraints with * smallest index. * * Only potential vertices with a full-dimensional activity domain * are considered. However, if the input has (implicit) equality * constraints among the parameters, then activity domain * should be considered full-dimensional if it does not satisfy * any extra equality constraints beyond those of the input. * The implicit equality constraints of the input are therefore first detected. * If there are any, then the input is mapped to a lower dimensional space * such that the check for full-dimensional activity domains * can be performed with respect to a full-dimensional space. * Note that it is important to leave "bset" unmodified while detecting * equality constraints since the inequality constraints of "bset" * are assumed to correspond to those of the tableau. * * We set up a tableau and keep track of which facets have been * selected. The tableau is marked strict_redundant so that we can be * sure that any constraint that is marked redundant (and that is not * also marked zero) is not an equality. * If a constraint is marked DESELECTED, it means the constraint was * SELECTED before (in combination with the same selection of earlier * constraints). If such a deselected constraint turns out to be an * equality, then any vertex that may still be found with the current * selection has already been generated when the constraint was selected. * A constraint is marked UNSELECTED when there is no way selecting * the constraint could lead to a vertex (in combination with the current * selection of earlier constraints). * * The set variable coefficients of the selected constraints are stored * in the facets matrix. */ __isl_give isl_vertices *isl_basic_set_compute_vertices( __isl_keep isl_basic_set *bset) { … } struct isl_chamber_list { … }; static void free_chamber_list(struct isl_chamber_list *list) { … } /* Check whether the basic set "bset" is a superset of the basic set described * by "tab", i.e., check whether all constraints of "bset" are redundant. */ static isl_bool bset_covers_tab(__isl_keep isl_basic_set *bset, struct isl_tab *tab) { … } static __isl_give isl_vertices *vertices_add_chambers( __isl_take isl_vertices *vertices, int n_chambers, struct isl_chamber_list *list) { … } /* Can "tab" be intersected with "bset" without resulting in * a lower-dimensional set. * "bset" itself is assumed to be full-dimensional. */ static isl_bool can_intersect(struct isl_tab *tab, __isl_keep isl_basic_set *bset) { … } static int add_chamber(struct isl_chamber_list **list, __isl_keep isl_vertices *vertices, struct isl_tab *tab, int *selection) { … } struct isl_facet_todo { … }; static void free_todo(struct isl_facet_todo *todo) { … } static struct isl_facet_todo *create_todo(struct isl_tab *tab, int con) { … } /* Create todo items for all interior facets of the chamber represented * by "tab" and collect them in "next". */ static int init_todo(struct isl_facet_todo **next, struct isl_tab *tab) { … } /* Does the linked list contain a todo item that is the opposite of "todo". * If so, return 1 and remove the opposite todo item. */ static int has_opposite(struct isl_facet_todo *todo, struct isl_facet_todo **list) { … } /* Create todo items for all interior facets of the chamber represented * by "tab" and collect them in first->next, taking care to cancel * opposite todo items. */ static int update_todo(struct isl_facet_todo *first, struct isl_tab *tab) { … } /* Compute the chamber decomposition of the parametric polytope respresented * by "bset" given the parametric vertices and their activity domains. * * We are only interested in full-dimensional chambers. * Each of these chambers is the intersection of the activity domains of * one or more vertices and the union of all chambers is equal to the * projection of the entire parametric polytope onto the parameter space. * * We first create an initial chamber by intersecting as many activity * domains as possible without ending up with an empty or lower-dimensional * set. As a minor optimization, we only consider those activity domains * that contain some arbitrary point. * * For each of the interior facets of the chamber, we construct a todo item, * containing the facet and a constraint containing the other side of the facet, * for constructing the chamber on the other side. * While their are any todo items left, we pick a todo item and * create the required chamber by intersecting all activity domains * that contain the facet and have a full-dimensional intersection with * the other side of the facet. For each of the interior facets, we * again create todo items, taking care to cancel opposite todo items. */ static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset, __isl_take isl_vertices *vertices) { … } isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex) { … } isl_size isl_vertex_get_id(__isl_keep isl_vertex *vertex) { … } /* Return the activity domain of the vertex "vertex". */ __isl_give isl_basic_set *isl_vertex_get_domain(__isl_keep isl_vertex *vertex) { … } /* Return a multiple quasi-affine expression describing the vertex "vertex" * in terms of the parameters, */ __isl_give isl_multi_aff *isl_vertex_get_expr(__isl_keep isl_vertex *vertex) { … } static __isl_give isl_vertex *isl_vertex_alloc(__isl_take isl_vertices *vertices, int id) { … } __isl_null isl_vertex *isl_vertex_free(__isl_take isl_vertex *vertex) { … } isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell) { … } __isl_give isl_basic_set *isl_cell_get_domain(__isl_keep isl_cell *cell) { … } static __isl_give isl_cell *isl_cell_alloc(__isl_take isl_vertices *vertices, __isl_take isl_basic_set *dom, int id) { … } __isl_null isl_cell *isl_cell_free(__isl_take isl_cell *cell) { … } /* Create a tableau of the cone obtained by first homogenizing the given * polytope and then making all inequalities strict by setting the * constant term to -1. */ static struct isl_tab *tab_for_shifted_cone(__isl_keep isl_basic_set *bset) { … } /* Compute an interior point of "bset" by selecting an interior * point in homogeneous space and projecting the point back down. */ static __isl_give isl_vec *isl_basic_set_interior_point( __isl_keep isl_basic_set *bset) { … } /* Call "fn" on all chambers of the parametric polytope with the shared * facets of neighboring chambers only appearing in one of the chambers. * * We pick an interior point from one of the chambers and then make * all constraints that do not satisfy this point strict. * For constraints that saturate the interior point, the sign * of the first non-zero coefficient is used to determine which * of the two (internal) constraints should be tightened. */ isl_stat isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices *vertices, isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user) { … } isl_stat isl_vertices_foreach_cell(__isl_keep isl_vertices *vertices, isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user) { … } isl_stat isl_vertices_foreach_vertex(__isl_keep isl_vertices *vertices, isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user) { … } isl_stat isl_cell_foreach_vertex(__isl_keep isl_cell *cell, isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user) { … } isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices) { … } isl_size isl_vertices_get_n_vertices(__isl_keep isl_vertices *vertices) { … } __isl_give isl_vertices *isl_morph_vertices(__isl_take isl_morph *morph, __isl_take isl_vertices *vertices) { … } /* Construct a simplex isl_cell spanned by the vertices with indices in * "simplex_ids" and "other_ids" and call "fn" on this isl_cell. */ static isl_stat call_on_simplex(__isl_keep isl_cell *cell, int *simplex_ids, int n_simplex, int *other_ids, int n_other, isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user) { … } /* Check whether the parametric vertex described by "vertex" * lies on the facet corresponding to constraint "facet" of "bset". * The isl_vec "v" is a temporary vector than can be used by this function. * * We eliminate the variables from the facet constraint using the * equalities defining the vertex and check if the result is identical * to zero. * * It would probably be better to keep track of the constraints defining * a vertex during the vertex construction so that we could simply look * it up here. */ static int vertex_on_facet(__isl_keep isl_basic_set *vertex, __isl_keep isl_basic_set *bset, int facet, __isl_keep isl_vec *v) { … } /* Triangulate the polytope spanned by the vertices with ids * in "simplex_ids" and "other_ids" and call "fn" on each of * the resulting simplices. * If the input polytope is already a simplex, we simply call "fn". * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids". * Then we consider each facet of "bset" that does not contain the point * we just picked, but does contain some of the other points in "other_ids" * and call ourselves recursively on the polytope spanned by the new * "simplex_ids" and those points in "other_ids" that lie on the facet. */ static isl_stat triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v, int *simplex_ids, int n_simplex, int *other_ids, int n_other, isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user) { … } /* Triangulate the given cell and call "fn" on each of the resulting * simplices. */ isl_stat isl_cell_foreach_simplex(__isl_take isl_cell *cell, isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user) { … }