llvm/polly/lib/External/isl/isl_vertices.c

/*
 * 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)
{}