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

/*
 * Copyright 2008-2009 Katholieke Universiteit Leuven
 * Copyright 2010      INRIA Saclay
 * Copyright 2012-2014 Ecole Normale Superieure
 * Copyright 2014      INRIA Rocquencourt
 * Copyright 2016      INRIA Paris
 * Copyright 2016      Sven Verdoolaege
 * Copyright 2018-2019 Cerebras Systems
 *
 * 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 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
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
 * B.P. 105 - 78153 Le Chesnay, France
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
 * CS 42112, 75589 Paris Cedex 12, France
 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
 */

#include <string.h>
#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include <isl_blk.h>
#include <isl_id_private.h>
#include <isl/constraint.h>
#include "isl_space_private.h"
#include "isl_equalities.h"
#include <isl_lp_private.h>
#include <isl_seq.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl_reordering.h>
#include "isl_sample.h"
#include <isl_sort.h>
#include "isl_tab.h"
#include <isl/vec.h>
#include <isl_mat_private.h>
#include <isl_vec_private.h>
#include <isl_dim_map.h>
#include <isl_local_space_private.h>
#include <isl_aff_private.h>
#include <isl_options_private.h>
#include <isl_morph.h>
#include <isl_val_private.h>
#include <isl_printer_private.h>

#include <bset_to_bmap.c>
#include <bset_from_bmap.c>
#include <set_to_map.c>
#include <set_from_map.c>

/* Treat "bset" as a basic map.
 * Internally, isl_basic_set is defined to isl_basic_map, so in practice,
 * this function performs a redundant cast.
 */
static __isl_keep const isl_basic_map *const_bset_to_bmap(
	__isl_keep const isl_basic_set *bset)
{ … }

#undef TYPE
#define TYPE …
#include "has_single_reference_templ.c"

static unsigned pos(__isl_keep isl_space *space, enum isl_dim_type type)
{ … }

isl_size isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
				enum isl_dim_type type)
{ … }

/* Return the space of "map".
 */
__isl_keep isl_space *isl_map_peek_space(__isl_keep const isl_map *map)
{ … }

/* Return the space of "set".
 */
__isl_keep isl_space *isl_set_peek_space(__isl_keep isl_set *set)
{ … }

isl_size isl_map_dim(__isl_keep isl_map *map, enum isl_dim_type type)
{ … }

/* Return the dimensionality of the domain (tuple) of the map.
 */
isl_size isl_map_domain_tuple_dim(__isl_keep isl_map *map)
{ … }

/* Return the dimensionality of the range (tuple) of the map.
 */
isl_size isl_map_range_tuple_dim(__isl_keep isl_map *map)
{ … }

isl_size isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
{ … }

/* Return the dimensionality of the (tuple of the) set.
 */
isl_size isl_set_tuple_dim(__isl_keep isl_set *set)
{ … }

/* Return the position of the variables of the given type
 * within the sequence of variables of "bmap".
 */
isl_size isl_basic_map_var_offset(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type)
{ … }

/* Return the position of the variables of the given type
 * within the sequence of variables of "bset".
 */
isl_size isl_basic_set_var_offset(__isl_keep isl_basic_set *bset,
	enum isl_dim_type type)
{ … }

/* Return the position of the coefficients of the variables of the given type
 * within the sequence of coefficients of "bmap".
 */
unsigned isl_basic_map_offset(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type)
{ … }

unsigned isl_basic_set_offset(__isl_keep isl_basic_set *bset,
					enum isl_dim_type type)
{ … }

static unsigned map_offset(__isl_keep isl_map *map, enum isl_dim_type type)
{ … }

isl_size isl_basic_set_dim(__isl_keep isl_basic_set *bset,
				enum isl_dim_type type)
{ … }

isl_size isl_basic_set_n_dim(__isl_keep isl_basic_set *bset)
{ … }

isl_size isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
{ … }

isl_size isl_basic_set_total_dim(__isl_keep const isl_basic_set *bset)
{ … }

isl_size isl_set_n_dim(__isl_keep isl_set *set)
{ … }

isl_size isl_set_n_param(__isl_keep isl_set *set)
{ … }

isl_size isl_basic_map_total_dim(__isl_keep const isl_basic_map *bmap)
{ … }

/* Return the number of equality constraints in the description of "bmap".
 * Return isl_size_error on error.
 */
isl_size isl_basic_map_n_equality(__isl_keep isl_basic_map *bmap)
{ … }

/* Return the number of equality constraints in the description of "bset".
 * Return isl_size_error on error.
 */
isl_size isl_basic_set_n_equality(__isl_keep isl_basic_set *bset)
{ … }

/* Return the number of inequality constraints in the description of "bmap".
 * Return isl_size_error on error.
 */
isl_size isl_basic_map_n_inequality(__isl_keep isl_basic_map *bmap)
{ … }

/* Return the number of inequality constraints in the description of "bset".
 * Return isl_size_error on error.
 */
isl_size isl_basic_set_n_inequality(__isl_keep isl_basic_set *bset)
{ … }

/* Do "bmap1" and "bmap2" have the same parameters?
 */
static isl_bool isl_basic_map_has_equal_params(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

/* Do "map1" and "map2" have the same parameters?
 */
isl_bool isl_map_has_equal_params(__isl_keep isl_map *map1,
	__isl_keep isl_map *map2)
{ … }

/* Do "map" and "set" have the same parameters?
 */
static isl_bool isl_map_set_has_equal_params(__isl_keep isl_map *map,
	__isl_keep isl_set *set)
{ … }

/* Is the tuple of type "type" of "bmap" the same as the single tuple of "bset"?
 */
static isl_bool isl_basic_map_set_tuple_is_equal(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, __isl_keep isl_basic_set *bset)
{ … }

/* Is the tuple of type "type" of "map" the same as the single tuple of "set"?
 */
static isl_bool isl_map_set_tuple_is_equal(__isl_keep isl_map *map,
	enum isl_dim_type type, __isl_keep isl_set *set)
{ … }

isl_bool isl_map_compatible_domain(__isl_keep isl_map *map,
	__isl_keep isl_set *set)
{ … }

isl_bool isl_basic_map_compatible_domain(__isl_keep isl_basic_map *bmap,
	__isl_keep isl_basic_set *bset)
{ … }

isl_bool isl_map_compatible_range(__isl_keep isl_map *map,
	__isl_keep isl_set *set)
{ … }

isl_bool isl_basic_map_compatible_range(__isl_keep isl_basic_map *bmap,
	__isl_keep isl_basic_set *bset)
{ … }

isl_ctx *isl_basic_map_get_ctx(__isl_keep isl_basic_map *bmap)
{ … }

isl_ctx *isl_basic_set_get_ctx(__isl_keep isl_basic_set *bset)
{ … }

isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
{ … }

isl_ctx *isl_set_get_ctx(__isl_keep isl_set *set)
{ … }

/* Return the space of "bmap".
 */
__isl_keep isl_space *isl_basic_map_peek_space(
	__isl_keep const isl_basic_map *bmap)
{ … }

/* Return the space of "bset".
 */
__isl_keep isl_space *isl_basic_set_peek_space(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_space *isl_basic_map_get_space(__isl_keep isl_basic_map *bmap)
{ … }

__isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
{ … }

/* Return the space of "bmap".
 * This may be either a copy or the space itself
 * if there is only one reference to "bmap".
 * This allows the space to be modified inplace
 * if both the basic map and its space have only a single reference.
 * The caller is not allowed to modify "bmap" between this call and
 * a subsequent call to isl_basic_map_restore_space.
 * The only exception is that isl_basic_map_free can be called instead.
 */
static __isl_give isl_space *isl_basic_map_take_space(
	__isl_keep isl_basic_map *bmap)
{ … }

/* Set the space of "bmap" to "space", where the space of "bmap" may be missing
 * due to a preceding call to isl_basic_map_take_space.
 * However, in this case, "bmap" only has a single reference and
 * then the call to isl_basic_map_cow has no effect.
 */
static __isl_give isl_basic_map *isl_basic_map_restore_space(
	__isl_take isl_basic_map *bmap, __isl_take isl_space *space)
{ … }

/* Extract the divs in "bmap" as a matrix.
 */
__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap)
{ … }

/* Extract the divs in "bset" as a matrix.
 */
__isl_give isl_mat *isl_basic_set_get_divs(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_local_space *isl_basic_map_get_local_space(
	__isl_keep isl_basic_map *bmap)
{ … }

__isl_give isl_local_space *isl_basic_set_get_local_space(
	__isl_keep isl_basic_set *bset)
{ … }

/* For each known div d = floor(f/m), add the constraints
 *
 *		f - m d >= 0
 *		-(f-(m-1)) + m d >= 0
 *
 * Do not finalize the result.
 */
static __isl_give isl_basic_map *add_known_div_constraints(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_map *isl_basic_map_from_local_space(
	__isl_take isl_local_space *ls)
{ … }

__isl_give isl_basic_set *isl_basic_set_from_local_space(
	__isl_take isl_local_space *ls)
{ … }

__isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map)
{ … }

__isl_give isl_space *isl_set_get_space(__isl_keep isl_set *set)
{ … }

/* Return the space of "map".
 * This may be either a copy or the space itself
 * if there is only one reference to "map".
 * This allows the space to be modified inplace
 * if both the map and its space have only a single reference.
 * The caller is not allowed to modify "map" between this call and
 * a subsequent call to isl_map_restore_space.
 * The only exception is that isl_map_free can be called instead.
 */
static __isl_give isl_space *isl_map_take_space(__isl_keep isl_map *map)
{ … }

/* Set the space of "map" to "space", where the space of "map" may be missing
 * due to a preceding call to isl_map_take_space.
 * However, in this case, "map" only has a single reference and
 * then the call to isl_map_cow has no effect.
 */
static __isl_give isl_map *isl_map_restore_space(__isl_take isl_map *map,
	__isl_take isl_space *space)
{ … }

__isl_give isl_basic_map *isl_basic_map_set_tuple_name(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type, const char *s)
{ … }

__isl_give isl_basic_set *isl_basic_set_set_tuple_name(
	__isl_take isl_basic_set *bset, const char *s)
{ … }

const char *isl_basic_map_get_tuple_name(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type)
{ … }

__isl_give isl_map *isl_map_set_tuple_name(__isl_take isl_map *map,
	enum isl_dim_type type, const char *s)
{ … }

/* Replace the identifier of the tuple of type "type" by "id".
 */
__isl_give isl_basic_map *isl_basic_map_set_tuple_id(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, __isl_take isl_id *id)
{ … }

/* Replace the identifier of the tuple by "id".
 */
__isl_give isl_basic_set *isl_basic_set_set_tuple_id(
	__isl_take isl_basic_set *bset, __isl_take isl_id *id)
{ … }

/* Does the input or output tuple have a name?
 */
isl_bool isl_map_has_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type)
{ … }

const char *isl_map_get_tuple_name(__isl_keep isl_map *map,
	enum isl_dim_type type)
{ … }

__isl_give isl_set *isl_set_set_tuple_name(__isl_take isl_set *set,
	const char *s)
{ … }

__isl_give isl_map *isl_map_set_tuple_id(__isl_take isl_map *map,
	enum isl_dim_type type, __isl_take isl_id *id)
{ … }

/* Replace the identifier of the domain tuple of "map" by "id".
 */
__isl_give isl_map *isl_map_set_domain_tuple_id(__isl_take isl_map *map,
	__isl_take isl_id *id)
{ … }

/* Replace the identifier of the range tuple of "map" by "id".
 */
__isl_give isl_map *isl_map_set_range_tuple_id(__isl_take isl_map *map,
	__isl_take isl_id *id)
{ … }

__isl_give isl_set *isl_set_set_tuple_id(__isl_take isl_set *set,
	__isl_take isl_id *id)
{ … }

__isl_give isl_map *isl_map_reset_tuple_id(__isl_take isl_map *map,
	enum isl_dim_type type)
{ … }

__isl_give isl_set *isl_set_reset_tuple_id(__isl_take isl_set *set)
{ … }

isl_bool isl_map_has_tuple_id(__isl_keep isl_map *map, enum isl_dim_type type)
{ … }

/* Does the domain tuple of "map" have an identifier?
 */
isl_bool isl_map_has_domain_tuple_id(__isl_keep isl_map *map)
{ … }

/* Does the range tuple of "map" have an identifier?
 */
isl_bool isl_map_has_range_tuple_id(__isl_keep isl_map *map)
{ … }

__isl_give isl_id *isl_map_get_tuple_id(__isl_keep isl_map *map,
	enum isl_dim_type type)
{ … }

/* Return the identifier of the domain tuple of "map", assuming it has one.
 */
__isl_give isl_id *isl_map_get_domain_tuple_id(__isl_keep isl_map *map)
{ … }

/* Return the identifier of the range tuple of "map", assuming it has one.
 */
__isl_give isl_id *isl_map_get_range_tuple_id(__isl_keep isl_map *map)
{ … }

isl_bool isl_set_has_tuple_id(__isl_keep isl_set *set)
{ … }

__isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set)
{ … }

/* Does the set tuple have a name?
 */
isl_bool isl_set_has_tuple_name(__isl_keep isl_set *set)
{ … }


const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset)
{ … }

const char *isl_set_get_tuple_name(__isl_keep isl_set *set)
{ … }

const char *isl_basic_map_get_dim_name(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos)
{ … }

const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Does the given dimension have a name?
 */
isl_bool isl_map_has_dim_name(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos)
{ … }

const char *isl_map_get_dim_name(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos)
{ … }

const char *isl_set_get_dim_name(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Does the given dimension have a name?
 */
isl_bool isl_set_has_dim_name(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

__isl_give isl_basic_map *isl_basic_map_set_dim_name(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, const char *s)
{ … }

__isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, const char *s)
{ … }

__isl_give isl_basic_set *isl_basic_set_set_dim_name(
	__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned pos, const char *s)
{ … }

__isl_give isl_set *isl_set_set_dim_name(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, const char *s)
{ … }

isl_bool isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos)
{ … }

__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset,
	enum isl_dim_type type, unsigned pos)
{ … }

isl_bool isl_map_has_dim_id(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos)
{ … }

__isl_give isl_id *isl_map_get_dim_id(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos)
{ … }

isl_bool isl_set_has_dim_id(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

__isl_give isl_id *isl_set_get_dim_id(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

__isl_give isl_map *isl_map_set_dim_id(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
{ … }

__isl_give isl_set *isl_set_set_dim_id(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
{ … }

int isl_map_find_dim_by_id(__isl_keep isl_map *map, enum isl_dim_type type,
	__isl_keep isl_id *id)
{ … }

int isl_set_find_dim_by_id(__isl_keep isl_set *set, enum isl_dim_type type,
	__isl_keep isl_id *id)
{ … }

/* Return the position of the dimension of the given type and name
 * in "bmap".
 * Return -1 if no such dimension can be found.
 */
int isl_basic_map_find_dim_by_name(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, const char *name)
{ … }

int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type,
	const char *name)
{ … }

int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type,
	const char *name)
{ … }

/* Check whether equality i of bset is a pure stride constraint
 * on a single dimension, i.e., of the form
 *
 *	v = k e
 *
 * with k a constant and e an existentially quantified variable.
 */
isl_bool isl_basic_set_eq_is_stride(__isl_keep isl_basic_set *bset, int i)
{ … }

/* Reset the user pointer on all identifiers of parameters and tuples
 * of the space of "map".
 */
__isl_give isl_map *isl_map_reset_user(__isl_take isl_map *map)
{ … }

/* Reset the user pointer on all identifiers of parameters and tuples
 * of the space of "set".
 */
__isl_give isl_set *isl_set_reset_user(__isl_take isl_set *set)
{ … }

isl_bool isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
{ … }

/* Has "map" been marked as a rational map?
 * In particular, have all basic maps in "map" been marked this way?
 * An empty map is not considered to be rational.
 * Maps where only some of the basic maps are marked rational
 * are not allowed.
 */
isl_bool isl_map_is_rational(__isl_keep isl_map *map)
{ … }

/* Has "set" been marked as a rational set?
 * In particular, have all basic set in "set" been marked this way?
 * An empty set is not considered to be rational.
 * Sets where only some of the basic sets are marked rational
 * are not allowed.
 */
isl_bool isl_set_is_rational(__isl_keep isl_set *set)
{ … }

int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
{ … }

/* Does "bmap" contain any rational points?
 *
 * If "bmap" has an equality for each dimension, equating the dimension
 * to an integer constant, then it has no rational points, even if it
 * is marked as rational.
 */
isl_bool isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap)
{ … }

/* Does "map" contain any rational points?
 */
isl_bool isl_map_has_rational(__isl_keep isl_map *map)
{ … }

/* Does "set" contain any rational points?
 */
isl_bool isl_set_has_rational(__isl_keep isl_set *set)
{ … }

/* Is this basic set a parameter domain?
 */
isl_bool isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
{ … }

/* Is this set a parameter domain?
 */
isl_bool isl_set_is_params(__isl_keep isl_set *set)
{ … }

/* Is this map actually a parameter domain?
 * Users should never call this function.  Outside of isl,
 * a map can never be a parameter domain.
 */
isl_bool isl_map_is_params(__isl_keep isl_map *map)
{ … }

static __isl_give isl_basic_map *basic_map_init(isl_ctx *ctx,
	__isl_take isl_basic_map *bmap, unsigned extra,
	unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_set *isl_basic_set_alloc(isl_ctx *ctx,
		unsigned nparam, unsigned dim, unsigned extra,
		unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_set *isl_basic_set_alloc_space(__isl_take isl_space *space,
		unsigned extra, unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_map *isl_basic_map_alloc_space(__isl_take isl_space *space,
		unsigned extra, unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_map *isl_basic_map_alloc(isl_ctx *ctx,
		unsigned nparam, unsigned in, unsigned out, unsigned extra,
		unsigned n_eq, unsigned n_ineq)
{ … }

static __isl_give isl_basic_map *dup_constraints(__isl_take isl_basic_map *dst,
	__isl_keep isl_basic_map *src)
{ … }

__isl_give isl_basic_map *isl_basic_map_dup(__isl_keep isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_dup(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_basic_set *isl_basic_set_copy(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_set *isl_set_copy(__isl_keep isl_set *set)
{ … }

__isl_give isl_basic_map *isl_basic_map_copy(__isl_keep isl_basic_map *bmap)
{ … }

__isl_give isl_map *isl_map_copy(__isl_keep isl_map *map)
{ … }

__isl_null isl_basic_map *isl_basic_map_free(__isl_take isl_basic_map *bmap)
{ … }

__isl_null isl_basic_set *isl_basic_set_free(__isl_take isl_basic_set *bset)
{ … }

static int room_for_con(__isl_keep isl_basic_map *bmap, unsigned n)
{ … }

/* Check that "bset" does not involve any parameters.
 */
isl_stat isl_basic_set_check_no_params(__isl_keep isl_basic_set *bset)
{ … }

/* Check that "bset" does not involve any local variables.
 */
isl_stat isl_basic_set_check_no_locals(__isl_keep isl_basic_set *bset)
{ … }

#undef TYPE
#define TYPE …

#include "isl_check_named_params_templ.c"

#undef TYPE
#define TYPE …

static
#include "isl_check_named_params_templ.c"

/* Check that "bmap1" and "bmap2" have the same parameters,
 * reporting an error if they do not.
 */
static isl_stat isl_basic_map_check_equal_params(
	__isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2)
{ … }

#undef TYPE
#define TYPE …

#include "isl_align_params_bin_templ.c"

#undef SUFFIX
#define SUFFIX …
#undef ARG1
#define ARG1 …
#undef ARG2
#define ARG2 …

#include "isl_align_params_templ.c"

isl_bool isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1,
	__isl_keep isl_map *map2,
	isl_bool (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2))
{ … }

int isl_basic_map_alloc_equality(__isl_keep isl_basic_map *bmap)
{ … }

int isl_basic_set_alloc_equality(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_free_equality(
	__isl_take isl_basic_map *bmap, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_free_equality(
	__isl_take isl_basic_set *bset, unsigned n)
{ … }

/* Drop the equality constraint at position "pos",
 * preserving the order of the other equality constraints.
 */
int isl_basic_map_drop_equality(__isl_keep isl_basic_map *bmap, unsigned pos)
{ … }

/* Turn inequality "pos" of "bmap" into an equality.
 *
 * In particular, we move the inequality in front of the equalities
 * and move the last inequality in the position of the moved inequality.
 * Note that isl_tab_make_equalities_explicit depends on this particular
 * change in the ordering of the constraints.
 */
void isl_basic_map_inequality_to_equality(
		__isl_keep isl_basic_map *bmap, unsigned pos)
{ … }

static int room_for_ineq(__isl_keep isl_basic_map *bmap, unsigned n)
{ … }

int isl_basic_map_alloc_inequality(__isl_keep isl_basic_map *bmap)
{ … }

int isl_basic_set_alloc_inequality(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_free_inequality(
	__isl_take isl_basic_map *bmap, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_free_inequality(
	__isl_take isl_basic_set *bset, unsigned n)
{ … }

int isl_basic_map_drop_inequality(__isl_keep isl_basic_map *bmap, unsigned pos)
{ … }

int isl_basic_set_drop_inequality(__isl_keep isl_basic_set *bset, unsigned pos)
{ … }

__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
	isl_int *eq)
{ … }

__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
	isl_int *eq)
{ … }

__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
	isl_int *ineq)
{ … }

__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
	isl_int *ineq)
{ … }

int isl_basic_map_alloc_div(__isl_keep isl_basic_map *bmap)
{ … }

int isl_basic_set_alloc_div(__isl_keep isl_basic_set *bset)
{ … }

#undef TYPE
#define TYPE …
#include "check_type_range_templ.c"

/* Check that there are "n" dimensions of type "type" starting at "first"
 * in "bset".
 */
isl_stat isl_basic_set_check_range(__isl_keep isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Insert an extra integer division, prescribed by "div", to "bmap"
 * at (integer division) position "pos".
 *
 * The integer division is first added at the end and then moved
 * into the right position.
 */
__isl_give isl_basic_map *isl_basic_map_insert_div(
	__isl_take isl_basic_map *bmap, int pos, __isl_keep isl_vec *div)
{ … }

isl_stat isl_basic_map_free_div(__isl_keep isl_basic_map *bmap, unsigned n)
{ … }

static __isl_give isl_basic_map *add_constraints(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2,
	unsigned i_pos, unsigned o_pos)
{ … }

__isl_give isl_basic_map *isl_basic_map_extend(__isl_take isl_basic_map *base,
	unsigned extra, unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_set *isl_basic_set_extend(__isl_take isl_basic_set *base,
	unsigned extra, unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_map *isl_basic_map_extend_constraints(
	__isl_take isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_set *isl_basic_set_extend_constraints(
	__isl_take isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
{ … }

__isl_give isl_basic_set *isl_basic_set_cow(__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_cow(__isl_take isl_basic_map *bmap)
{ … }

/* Clear all cached information in "map", either because it is about
 * to be modified or because it is being freed.
 * Always return the same pointer that is passed in.
 * This is needed for the use in isl_map_free.
 */
static __isl_give isl_map *clear_caches(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_cow(__isl_take isl_set *set)
{ … }

/* Return an isl_map that is equal to "map" and that has only
 * a single reference.
 *
 * If the original input already has only one reference, then
 * simply return it, but clear all cached information, since
 * it may be rendered invalid by the operations that will be
 * performed on the result.
 *
 * Otherwise, create a duplicate (without any cached information).
 */
__isl_give isl_map *isl_map_cow(__isl_take isl_map *map)
{ … }

static void swap_vars(struct isl_blk blk, isl_int *a,
			unsigned a_len, unsigned b_len)
{ … }

static __isl_give isl_basic_map *isl_basic_map_swap_vars(
	__isl_take isl_basic_map *bmap, unsigned pos, unsigned n1, unsigned n2)
{ … }

/* The given basic map has turned out to be empty.
 * Explicitly mark it as such and change the representation
 * to a canonical representation of the empty basic map.
 * Since the basic map has conflicting constraints,
 * it must have at least one constraint, except perhaps
 * if it was already explicitly marked as being empty.
 * Do nothing in the latter case, i.e., if it has been marked empty and
 * has no constraints.
 */
__isl_give isl_basic_map *isl_basic_map_set_to_empty(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_set_to_empty(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_set_rational(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_set_rational(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_basic_set *isl_basic_set_set_integral(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_map *isl_map_set_rational(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_set_rational(__isl_take isl_set *set)
{ … }

/* Swap divs "a" and "b" in "bmap" (without modifying any of the constraints
 * of "bmap").
 */
static void swap_div(__isl_keep isl_basic_map *bmap, int a, int b)
{ … }

/* Swap divs "a" and "b" in "bmap" and adjust the constraints and
 * div definitions accordingly.
 */
__isl_give isl_basic_map *isl_basic_map_swap_div(__isl_take isl_basic_map *bmap,
	int a, int b)
{ … }

static void constraint_drop_vars(isl_int *c, unsigned n, unsigned rem)
{ … }

/* Drop n dimensions starting at first.
 *
 * In principle, this frees up some extra variables as the number
 * of columns remains constant, but we would have to extend
 * the div array too as the number of rows in this array is assumed
 * to be equal to extra.
 */
__isl_give isl_basic_set *isl_basic_set_drop_dims(
	__isl_take isl_basic_set *bset, unsigned first, unsigned n)
{ … }

/* Move "n" divs starting at "first" to the end of the list of divs.
 */
static __isl_give isl_basic_map *move_divs_last(__isl_take isl_basic_map *bmap,
	unsigned first, unsigned n)
{ … }

#undef TYPE
#define TYPE …
static
#include "check_type_range_templ.c"

/* Check that there are "n" dimensions of type "type" starting at "first"
 * in "set".
 */
isl_stat isl_set_check_range(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop "n" dimensions of type "type" starting at "first".
 * Perform the core computation, without cowing or
 * simplifying and finalizing the result.
 *
 * In principle, this frees up some extra variables as the number
 * of columns remains constant, but we would have to extend
 * the div array too as the number of rows in this array is assumed
 * to be equal to extra.
 */
__isl_give isl_basic_map *isl_basic_map_drop_core(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type,
	unsigned first, unsigned n)
{ … }

/* Drop "n" dimensions of type "type" starting at "first".
 *
 * In principle, this frees up some extra variables as the number
 * of columns remains constant, but we would have to extend
 * the div array too as the number of rows in this array is assumed
 * to be equal to extra.
 */
__isl_give isl_basic_map *isl_basic_map_drop(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_drop(__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* No longer consider "map" to be normalized.
 */
static __isl_give isl_map *isl_map_unmark_normalized(__isl_take isl_map *map)
{ … }

__isl_give isl_map *isl_map_drop(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_set *isl_set_drop(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop the integer division at position "div", which is assumed
 * not to appear in any of the constraints or
 * in any of the other integer divisions.
 *
 * Since the integer division is redundant, there is no need to cow.
 */
__isl_give isl_basic_map *isl_basic_map_drop_div(
	__isl_take isl_basic_map *bmap, unsigned div)
{ … }

/* Eliminate the specified n dimensions starting at first from the
 * constraints, without removing the dimensions from the space.
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
 */
__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Eliminate the specified n dimensions starting at first from the
 * constraints, without removing the dimensions from the space.
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
 */
__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Eliminate the specified n dimensions starting at first from the
 * constraints, without removing the dimensions from the space.
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
 */
__isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
	unsigned first, unsigned n)
{ … }

__isl_give isl_basic_map *isl_basic_map_remove_divs(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_remove_divs(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
{ … }

__isl_give isl_basic_map *isl_basic_map_remove_dims(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type,
	unsigned first, unsigned n)
{ … }

/* Return true if the definition of the given div (recursively) involves
 * any of the given variables.
 */
static isl_bool div_involves_vars(__isl_keep isl_basic_map *bmap, int div,
	unsigned first, unsigned n)
{ … }

/* Try and add a lower and/or upper bound on "div" to "bmap"
 * based on inequality "i".
 * "total" is the total number of variables (excluding the divs).
 * "v" is a temporary object that can be used during the calculations.
 * If "lb" is set, then a lower bound should be constructed.
 * If "ub" is set, then an upper bound should be constructed.
 *
 * The calling function has already checked that the inequality does not
 * reference "div", but we still need to check that the inequality is
 * of the right form.  We'll consider the case where we want to construct
 * a lower bound.  The construction of upper bounds is similar.
 *
 * Let "div" be of the form
 *
 *	q = floor((a + f(x))/d)
 *
 * We essentially check if constraint "i" is of the form
 *
 *	b + f(x) >= 0
 *
 * so that we can use it to derive a lower bound on "div".
 * However, we allow a slightly more general form
 *
 *	b + g(x) >= 0
 *
 * with the condition that the coefficients of g(x) - f(x) are all
 * divisible by d.
 * Rewriting this constraint as
 *
 *	0 >= -b - g(x)
 *
 * adding a + f(x) to both sides and dividing by d, we obtain
 *
 *	(a + f(x))/d >= (a-b)/d + (f(x)-g(x))/d
 *
 * Taking the floor on both sides, we obtain
 *
 *	q >= floor((a-b)/d) + (f(x)-g(x))/d
 *
 * or
 *
 *	(g(x)-f(x))/d + ceil((b-a)/d) + q >= 0
 *
 * In the case of an upper bound, we construct the constraint
 *
 *	(g(x)+f(x))/d + floor((b+a)/d) - q >= 0
 *
 */
static __isl_give isl_basic_map *insert_bounds_on_div_from_ineq(
	__isl_take isl_basic_map *bmap, int div, int i,
	unsigned total, isl_int v, int lb, int ub)
{ … }

/* This function is called right before "div" is eliminated from "bmap"
 * using Fourier-Motzkin.
 * Look through the constraints of "bmap" for constraints on the argument
 * of the integer division and use them to construct constraints on the
 * integer division itself.  These constraints can then be combined
 * during the Fourier-Motzkin elimination.
 * Note that it is only useful to introduce lower bounds on "div"
 * if "bmap" already contains upper bounds on "div" as the newly
 * introduce lower bounds can then be combined with the pre-existing
 * upper bounds.  Similarly for upper bounds.
 * We therefore first check if "bmap" contains any lower and/or upper bounds
 * on "div".
 *
 * It is interesting to note that the introduction of these constraints
 * can indeed lead to more accurate results, even when compared to
 * deriving constraints on the argument of "div" from constraints on "div".
 * Consider, for example, the set
 *
 *	{ [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k }
 *
 * The second constraint can be rewritten as
 *
 *	2 * [(-i-2j+3)/4] + k >= 0
 *
 * from which we can derive
 *
 *	-i - 2j + 3 >= -2k
 *
 * or
 *
 *	i + 2j <= 3 + 2k
 *
 * Combined with the first constraint, we obtain
 *
 *	-3 <= 3 + 2k	or	k >= -3
 *
 * If, on the other hand we derive a constraint on [(i+2j)/4] from
 * the first constraint, we obtain
 *
 *	[(i + 2j)/4] >= [-3/4] = -1
 *
 * Combining this constraint with the second constraint, we obtain
 *
 *	k >= -2
 */
static __isl_give isl_basic_map *insert_bounds_on_div(
	__isl_take isl_basic_map *bmap, int div)
{ … }

/* Remove all divs (recursively) involving any of the given dimensions
 * in their definitions.
 */
__isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims(
	__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Does the description of "bmap" depend on the specified dimensions?
 * We also check whether the dimensions appear in any of the div definitions.
 * In principle there is no need for this check.  If the dimensions appear
 * in a div definition, they also appear in the defining constraints of that
 * div.
 */
isl_bool isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

isl_bool isl_map_involves_dims(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

isl_bool isl_basic_set_involves_dims(__isl_keep isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

isl_bool isl_set_involves_dims(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Does "bset" involve any local variables, i.e., integer divisions?
 */
static isl_bool isl_basic_set_involves_locals(__isl_keep isl_basic_set *bset)
{ … }

/* isl_set_every_basic_set callback that checks whether "bset"
 * is free of local variables.
 */
static isl_bool basic_set_no_locals(__isl_keep isl_basic_set *bset, void *user)
{ … }

/* Does "set" involve any local variables, i.e., integer divisions?
 */
isl_bool isl_set_involves_locals(__isl_keep isl_set *set)
{ … }

/* Drop all constraints in bmap that involve any of the dimensions
 * first to first+n-1.
 * This function only performs the actual removal of constraints.
 *
 * This function should not call finalize since it is used by
 * remove_redundant_divs, which in turn is called by isl_basic_map_finalize.
 */
__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
	__isl_take isl_basic_map *bmap, unsigned first, unsigned n)
{ … }

/* Drop all constraints in bset that involve any of the dimensions
 * first to first+n-1.
 * This function only performs the actual removal of constraints.
 */
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
	__isl_take isl_basic_set *bset, unsigned first, unsigned n)
{ … }

/* Drop all constraints in bmap that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop all constraints in bset that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
	__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop all constraints in bmap that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop all constraints in bset that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
	__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop constraints from "map" by applying "drop" to each basic map.
 */
static __isl_give isl_map *drop_constraints(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n,
	__isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap,
		enum isl_dim_type type, unsigned first, unsigned n))
{ … }

/* Drop all constraints in map that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_map *isl_map_drop_constraints_involving_dims(
	__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop all constraints in "map" that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_map *isl_map_drop_constraints_not_involving_dims(
	__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop all constraints in set that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_set *isl_set_drop_constraints_involving_dims(
	__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Drop all constraints in "set" that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_set *isl_set_drop_constraints_not_involving_dims(
	__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Does local variable "div" of "bmap" have a complete explicit representation?
 * Having a complete explicit representation requires not only
 * an explicit representation, but also that all local variables
 * that appear in this explicit representation in turn have
 * a complete explicit representation.
 */
isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div)
{ … }

/* Remove all divs that are unknown or defined in terms of unknown divs.
 */
__isl_give isl_basic_map *isl_basic_map_remove_unknown_divs(
	__isl_take isl_basic_map *bmap)
{ … }

/* Remove all divs that are unknown or defined in terms of unknown divs.
 */
__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_remove_unknown_divs(__isl_take isl_set *set)
{ … }

__isl_give isl_basic_set *isl_basic_set_remove_dims(
	__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_map *isl_map_remove_dims(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

__isl_give isl_set *isl_set_remove_dims(__isl_take isl_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Project out n inputs starting at first using Fourier-Motzkin */
__isl_give isl_map *isl_map_remove_inputs(__isl_take isl_map *map,
	unsigned first, unsigned n)
{ … }

void isl_basic_set_print_internal(__isl_keep isl_basic_set *bset,
	FILE *out, int indent)
{ … }

void isl_basic_map_print_internal(__isl_keep isl_basic_map *bmap,
	FILE *out, int indent)
{ … }

__isl_give isl_basic_map *isl_inequality_negate(__isl_take isl_basic_map *bmap,
	unsigned pos)
{ … }

__isl_give isl_set *isl_set_alloc_space(__isl_take isl_space *space, int n,
	unsigned flags)
{ … }

/* Make sure "map" has room for at least "n" more basic maps.
 */
__isl_give isl_map *isl_map_grow(__isl_take isl_map *map, int n)
{ … }

/* Make sure "set" has room for at least "n" more basic sets.
 */
__isl_give isl_set *isl_set_grow(__isl_take isl_set *set, int n)
{ … }

__isl_give isl_set *isl_set_from_basic_set(__isl_take isl_basic_set *bset)
{ … }

/* This function performs the same operation as isl_set_from_basic_set,
 * but is considered as a function on an isl_basic_set when exported.
 */
__isl_give isl_set *isl_basic_set_to_set(__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_map *isl_map_from_basic_map(__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
						__isl_take isl_basic_set *bset)
{ … }

__isl_null isl_set *isl_set_free(__isl_take isl_set *set)
{ … }

void isl_set_print_internal(__isl_keep isl_set *set, FILE *out, int indent)
{ … }

void isl_map_print_internal(__isl_keep isl_map *map, FILE *out, int indent)
{ … }

/* Check that the space of "bset" is the same as that of the domain of "bmap".
 */
static isl_stat isl_basic_map_check_compatible_domain(
	__isl_keep isl_basic_map *bmap, __isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_intersect_domain(
	__isl_take isl_basic_map *bmap, __isl_take isl_basic_set *bset)
{ … }

/* Check that the space of "bset" is the same as that of the range of "bmap".
 */
static isl_stat isl_basic_map_check_compatible_range(
	__isl_keep isl_basic_map *bmap, __isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_intersect_range(
	__isl_take isl_basic_map *bmap, __isl_take isl_basic_set *bset)
{ … }

isl_bool isl_basic_map_contains(__isl_keep isl_basic_map *bmap,
	__isl_keep isl_vec *vec)
{ … }

isl_bool isl_basic_set_contains(__isl_keep isl_basic_set *bset,
	__isl_keep isl_vec *vec)
{ … }

__isl_give isl_basic_map *isl_basic_map_intersect(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_set *isl_basic_set_intersect(
	__isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
{ … }

__isl_give isl_basic_set *isl_basic_set_intersect_params(
	__isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
{ … }

/* Does "map" consist of a single disjunct, without any local variables?
 */
static isl_bool is_convex_no_locals(__isl_keep isl_map *map)
{ … }

/* Check that "map" consists of a single disjunct, without any local variables.
 */
static isl_stat check_convex_no_locals(__isl_keep isl_map *map)
{ … }

/* Special case of isl_map_intersect, where both map1 and map2
 * are convex, without any divs and such that either map1 or map2
 * contains a single constraint.  This constraint is then simply
 * added to the other map.
 */
static __isl_give isl_map *map_intersect_add_constraint(
	__isl_take isl_map *map1, __isl_take isl_map *map2)
{ … }

/* map2 may be either a parameter domain or a map living in the same
 * space as map1.
 */
static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

static __isl_give isl_map *map_intersect(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_set *isl_set_intersect(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

/* map_intersect_internal accepts intersections
 * with parameter domains, so we can just call that function.
 */
__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map,
	__isl_take isl_set *params)
{ … }

__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set,
		__isl_take isl_set *params)
{ … }

__isl_give isl_basic_map *isl_basic_map_reverse(__isl_take isl_basic_map *bmap)
{ … }

/* Given a basic map A -> (B -> C), return the corresponding basic map
 * A -> (C -> B).
 */
static __isl_give isl_basic_map *isl_basic_map_range_reverse(
	__isl_take isl_basic_map *bmap)
{ … }

static __isl_give isl_basic_map *basic_map_space_reset(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type)
{ … }

__isl_give isl_basic_map *isl_basic_map_insert_dims(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type,
	unsigned pos, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_insert_dims(
	__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned pos, unsigned n)
{ … }

__isl_give isl_basic_map *isl_basic_map_add_dims(__isl_take isl_basic_map *bmap,
		enum isl_dim_type type, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset,
		enum isl_dim_type type, unsigned n)
{ … }

static __isl_give isl_map *map_space_reset(__isl_take isl_map *map,
	enum isl_dim_type type)
{ … }

__isl_give isl_map *isl_map_insert_dims(__isl_take isl_map *map,
		enum isl_dim_type type, unsigned pos, unsigned n)
{ … }

__isl_give isl_set *isl_set_insert_dims(__isl_take isl_set *set,
		enum isl_dim_type type, unsigned pos, unsigned n)
{ … }

__isl_give isl_map *isl_map_add_dims(__isl_take isl_map *map,
		enum isl_dim_type type, unsigned n)
{ … }

__isl_give isl_set *isl_set_add_dims(__isl_take isl_set *set,
		enum isl_dim_type type, unsigned n)
{ … }

__isl_give isl_basic_map *isl_basic_map_move_dims(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type dst_type, unsigned dst_pos,
	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{ … }

__isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
	enum isl_dim_type dst_type, unsigned dst_pos,
	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{ … }

__isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
	enum isl_dim_type dst_type, unsigned dst_pos,
	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{ … }

__isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
	enum isl_dim_type dst_type, unsigned dst_pos,
	enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{ … }

/* Move the specified dimensions to the last columns right before
 * the divs.  Don't change the dimension specification of bmap.
 * That's the responsibility of the caller.
 */
static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Insert "n" rows in the divs of "bmap".
 *
 * The number of columns is not changed, which means that the last
 * dimensions of "bmap" are being reintepreted as the new divs.
 * The space of "bmap" is not adjusted, however, which means
 * that "bmap" is left in an inconsistent state.  Removing "n" dimensions
 * from the space of "bmap" is the responsibility of the caller.
 */
static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap,
	int n)
{ … }

/* Drop constraints from "bmap" that only involve the variables
 * of "type" in the range [first, first + n] that are not related
 * to any of the variables outside that interval.
 * These constraints cannot influence the values for the variables
 * outside the interval, except in case they cause "bmap" to be empty.
 * Only drop the constraints if "bmap" is known to be non-empty.
 */
static __isl_give isl_basic_map *drop_irrelevant_constraints(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type,
	unsigned first, unsigned n)
{ … }

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 *
 * If a subset of the projected out variables are unrelated
 * to any of the variables that remain, then the constraints
 * involving this subset are simply dropped first.
 */
__isl_give isl_basic_map *isl_basic_map_project_out(
		__isl_take isl_basic_map *bmap,
		enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 */
__isl_give isl_basic_set *isl_basic_set_project_out(
	__isl_take isl_basic_set *bset, enum isl_dim_type type,
	unsigned first, unsigned n)
{ … }

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 */
__isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
		enum isl_dim_type type, unsigned first, unsigned n)
{ … }

#undef TYPE
#define TYPE …
#include "isl_project_out_all_params_templ.c"
#include "isl_project_out_param_templ.c"

/* Turn all the dimensions of type "type", except the "n" starting at "first"
 * into existentially quantified variables.
 */
__isl_give isl_map *isl_map_project_onto(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 */
__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
		enum isl_dim_type type, unsigned first, unsigned n)
{ … }

/* If "set" involves a parameter with identifier "id",
 * then turn it into an existentially quantified variable.
 */
__isl_give isl_set *isl_set_project_out_param_id(__isl_take isl_set *set,
	__isl_take isl_id *id)
{ … }

/* If "set" involves any of the parameters with identifiers in "list",
 * then turn them into existentially quantified variables.
 */
__isl_give isl_set *isl_set_project_out_param_id_list(__isl_take isl_set *set,
	__isl_take isl_id_list *list)
{ … }

/* Project out all parameters from "set" by existentially quantifying
 * over them.
 */
__isl_give isl_set *isl_set_project_out_all_params(__isl_take isl_set *set)
{ … }

/* Return a map that projects the elements in "set" onto their
 * "n" set dimensions starting at "first".
 * "type" should be equal to isl_dim_set.
 */
__isl_give isl_map *isl_set_project_onto_map(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

static __isl_give isl_basic_map *add_divs(__isl_take isl_basic_map *bmap,
	unsigned n)
{ … }

/* Does "bmap2" apply to the range of "bmap1" (ignoring parameters)?
 */
isl_bool isl_basic_map_applies_range(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

/* Check that "bmap2" applies to the range of "bmap1" (ignoring parameters).
 */
static isl_stat isl_basic_map_check_applies_range(
	__isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_map *isl_basic_map_apply_range(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_set *isl_basic_set_apply(__isl_take isl_basic_set *bset,
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_map *isl_basic_map_apply_domain(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

/* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
 * A \cap B -> f(A) + f(B)
 */
__isl_give isl_basic_map *isl_basic_map_sum(__isl_take isl_basic_map *bmap1,
	__isl_take isl_basic_map *bmap2)
{ … }

/* Given two maps A -> f(A) and B -> g(B), construct a map
 * A \cap B -> f(A) + f(B)
 */
__isl_give isl_map *isl_map_sum(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

/* Given a basic map A -> f(A), construct A -> -f(A).
 */
__isl_give isl_basic_map *isl_basic_map_neg(__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_neg(__isl_take isl_basic_set *bset)
{ … }

/* Given a map A -> f(A), construct A -> -f(A).
 */
__isl_give isl_map *isl_map_neg(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
{ … }

/* Given a basic map A -> f(A) and an integer d, construct a basic map
 * A -> floor(f(A)/d).
 */
__isl_give isl_basic_map *isl_basic_map_floordiv(__isl_take isl_basic_map *bmap,
		isl_int d)
{ … }

/* Given a map A -> f(A) and an integer d, construct a map
 * A -> floor(f(A)/d).
 */
__isl_give isl_map *isl_map_floordiv(__isl_take isl_map *map, isl_int d)
{ … }

/* Given a map A -> f(A) and an integer d, construct a map
 * A -> floor(f(A)/d).
 */
__isl_give isl_map *isl_map_floordiv_val(__isl_take isl_map *map,
	__isl_take isl_val *d)
{ … }

static __isl_give isl_basic_map *var_equal(__isl_take isl_basic_map *bmap,
	unsigned pos)
{ … }

/* Add a constraint to "bmap" expressing i_pos < o_pos
 */
static __isl_give isl_basic_map *var_less(__isl_take isl_basic_map *bmap,
	unsigned pos)
{ … }

/* Add a constraint to "bmap" expressing i_pos <= o_pos
 */
static __isl_give isl_basic_map *var_less_or_equal(
	__isl_take isl_basic_map *bmap, unsigned pos)
{ … }

/* Add a constraint to "bmap" expressing i_pos > o_pos
 */
static __isl_give isl_basic_map *var_more(__isl_take isl_basic_map *bmap,
	unsigned pos)
{ … }

/* Add a constraint to "bmap" expressing i_pos >= o_pos
 */
static __isl_give isl_basic_map *var_more_or_equal(
	__isl_take isl_basic_map *bmap, unsigned pos)
{ … }

__isl_give isl_basic_map *isl_basic_map_equal(
	__isl_take isl_space *space, unsigned n_equal)
{ … }

/* Return a relation on of dimension "space" expressing i_[0..pos] << o_[0..pos]
 */
__isl_give isl_basic_map *isl_basic_map_less_at(__isl_take isl_space *space,
	unsigned pos)
{ … }

/* Return a relation on "space" expressing i_[0..pos] <<= o_[0..pos]
 */
__isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
	__isl_take isl_space *space, unsigned pos)
{ … }

/* Return a relation on "space" expressing i_pos > o_pos
 */
__isl_give isl_basic_map *isl_basic_map_more_at(__isl_take isl_space *space,
	unsigned pos)
{ … }

/* Return a relation on "space" expressing i_[0..pos] >>= o_[0..pos]
 */
__isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
	__isl_take isl_space *space, unsigned pos)
{ … }

static __isl_give isl_map *map_lex_lte_first(__isl_take isl_space *space,
	unsigned n, int equal)
{ … }

static __isl_give isl_map *map_lex_lte(__isl_take isl_space *space, int equal)
{ … }

__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_space *space,
	unsigned n)
{ … }

__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_space *space,
	unsigned n)
{ … }

__isl_give isl_map *isl_map_lex_lt(__isl_take isl_space *set_space)
{ … }

__isl_give isl_map *isl_map_lex_le(__isl_take isl_space *set_space)
{ … }

static __isl_give isl_map *map_lex_gte_first(__isl_take isl_space *space,
	unsigned n, int equal)
{ … }

static __isl_give isl_map *map_lex_gte(__isl_take isl_space *space, int equal)
{ … }

__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_space *space,
	unsigned n)
{ … }

__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_space *space,
	unsigned n)
{ … }

__isl_give isl_map *isl_map_lex_gt(__isl_take isl_space *set_space)
{ … }

__isl_give isl_map *isl_map_lex_ge(__isl_take isl_space *set_space)
{ … }

__isl_give isl_map *isl_set_lex_le_set(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

__isl_give isl_map *isl_set_lex_lt_set(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

__isl_give isl_map *isl_set_lex_ge_set(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

__isl_give isl_map *isl_set_lex_gt_set(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

__isl_give isl_map *isl_map_lex_le_map(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_map *isl_map_lex_lt_map(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_map *isl_map_lex_ge_map(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_map *isl_map_lex_gt_map(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* For the div d = floor(f/m) at position "div", add the constraint
 *
 *		f - m d >= 0
 */
static __isl_give isl_basic_map *add_upper_div_constraint(
	__isl_take isl_basic_map *bmap, unsigned div)
{ … }

/* For the div d = floor(f/m) at position "div", add the constraint
 *
 *		-(f-(m-1)) + m d >= 0
 */
static __isl_give isl_basic_map *add_lower_div_constraint(
	__isl_take isl_basic_map *bmap, unsigned div)
{ … }

/* For the div d = floor(f/m) at position "pos", add the constraints
 *
 *		f - m d >= 0
 *		-(f-(m-1)) + m d >= 0
 *
 * Note that the second constraint is the negation of
 *
 *		f - m d >= m
 */
__isl_give isl_basic_map *isl_basic_map_add_div_constraints(
	__isl_take isl_basic_map *bmap, unsigned pos)
{ … }

/* For each known div d = floor(f/m), add the constraints
 *
 *		f - m d >= 0
 *		-(f-(m-1)) + m d >= 0
 *
 * Remove duplicate constraints in case of some these div constraints
 * already appear in "bmap".
 */
__isl_give isl_basic_map *isl_basic_map_add_known_div_constraints(
	__isl_take isl_basic_map *bmap)
{ … }

/* Add the div constraint of sign "sign" for div "div" of "bmap".
 *
 * In particular, if this div is of the form d = floor(f/m),
 * then add the constraint
 *
 *		f - m d >= 0
 *
 * if sign < 0 or the constraint
 *
 *		-(f-(m-1)) + m d >= 0
 *
 * if sign > 0.
 */
__isl_give isl_basic_map *isl_basic_map_add_div_constraint(
	__isl_take isl_basic_map *bmap, unsigned div, int sign)
{ … }

__isl_give isl_basic_set *isl_basic_map_underlying_set(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_underlying_set(
		__isl_take isl_basic_set *bset)
{ … }

/* Replace each element in "list" by the result of applying
 * isl_basic_map_underlying_set to the element.
 */
__isl_give isl_basic_set_list *isl_basic_map_list_underlying_set(
	__isl_take isl_basic_map_list *list)
{ … }

__isl_give isl_basic_map *isl_basic_map_overlying_set(
	__isl_take isl_basic_set *bset, __isl_take isl_basic_map *like)
{ … }

__isl_give isl_basic_set *isl_basic_set_from_underlying_set(
	__isl_take isl_basic_set *bset, __isl_take isl_basic_set *like)
{ … }

__isl_give isl_set *isl_map_underlying_set(__isl_take isl_map *map)
{ … }

/* Replace the space of "bmap" by "space".
 *
 * If the space of "bmap" is identical to "space" (including the identifiers
 * of the input and output dimensions), then simply return the original input.
 */
__isl_give isl_basic_map *isl_basic_map_reset_space(
	__isl_take isl_basic_map *bmap, __isl_take isl_space *space)
{ … }

__isl_give isl_basic_set *isl_basic_set_reset_space(
	__isl_take isl_basic_set *bset, __isl_take isl_space *space)
{ … }

/* Check that the total dimensions of "map" and "space" are the same.
 */
static isl_stat check_map_space_equal_total_dim(__isl_keep isl_map *map,
	__isl_keep isl_space *space)
{ … }

__isl_give isl_map *isl_map_reset_space(__isl_take isl_map *map,
	__isl_take isl_space *space)
{ … }

/* Replace the space of "map" by "space", without modifying
 * the dimension of "map".
 *
 * If the space of "map" is identical to "space" (including the identifiers
 * of the input and output dimensions), then simply return the original input.
 */
__isl_give isl_map *isl_map_reset_equal_dim_space(__isl_take isl_map *map,
	__isl_take isl_space *space)
{ … }

__isl_give isl_set *isl_set_reset_space(__isl_take isl_set *set,
	__isl_take isl_space *space)
{ … }

/* Compute the parameter domain of the given basic set.
 */
__isl_give isl_basic_set *isl_basic_set_params(__isl_take isl_basic_set *bset)
{ … }

/* Construct a zero-dimensional basic set with the given parameter domain.
 */
__isl_give isl_basic_set *isl_basic_set_from_params(
	__isl_take isl_basic_set *bset)
{ … }

/* Compute the parameter domain of the given set.
 */
__isl_give isl_set *isl_set_params(__isl_take isl_set *set)
{ … }

/* Construct a zero-dimensional set with the given parameter domain.
 */
__isl_give isl_set *isl_set_from_params(__isl_take isl_set *set)
{ … }

/* Compute the parameter domain of the given map.
 */
__isl_give isl_set *isl_map_params(__isl_take isl_map *map)
{ … }

__isl_give isl_basic_set *isl_basic_map_domain(__isl_take isl_basic_map *bmap)
{ … }

isl_bool isl_basic_map_may_be_set(__isl_keep isl_basic_map *bmap)
{ … }

/* Is this basic map actually a set?
 * Users should never call this function.  Outside of isl,
 * the type should indicate whether something is a set or a map.
 */
isl_bool isl_basic_map_is_set(__isl_keep isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_map_range(__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_map *isl_basic_map_domain_map(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_map *isl_basic_map_range_map(
	__isl_take isl_basic_map *bmap)
{ … }

int isl_map_may_be_set(__isl_keep isl_map *map)
{ … }

/* Is this map actually a set?
 * Users should never call this function.  Outside of isl,
 * the type should indicate whether something is a set or a map.
 */
isl_bool isl_map_is_set(__isl_keep isl_map *map)
{ … }

__isl_give isl_set *isl_map_range(__isl_take isl_map *map)
{ … }

/* Transform "map" by applying "fn_space" to its space and "fn_bmap"
 * to each of its basic maps.
 */
static __isl_give isl_map *isl_map_transform(__isl_take isl_map *map,
	__isl_give isl_space *(*fn_space)(__isl_take isl_space *space),
	__isl_give isl_basic_map *(*fn_bmap)(__isl_take isl_basic_map *bmap))
{ … }

__isl_give isl_map *isl_map_domain_map(__isl_take isl_map *map)
{ … }

__isl_give isl_map *isl_map_range_map(__isl_take isl_map *map)
{ … }

/* Given a wrapped map of the form A[B -> C],
 * return the map A[B -> C] -> B.
 */
__isl_give isl_map *isl_set_wrapped_domain_map(__isl_take isl_set *set)
{ … }

__isl_give isl_basic_map *isl_basic_map_from_domain(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_from_range(
	__isl_take isl_basic_set *bset)
{ … }

/* Create a relation with the given set as range.
 * The domain of the created relation is a zero-dimensional
 * flat anonymous space.
 */
__isl_give isl_map *isl_map_from_range(__isl_take isl_set *set)
{ … }

/* Create a relation with the given set as domain.
 * The range of the created relation is a zero-dimensional
 * flat anonymous space.
 */
__isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
{ … }

__isl_give isl_basic_map *isl_basic_map_from_domain_and_range(
	__isl_take isl_basic_set *domain, __isl_take isl_basic_set *range)
{ … }

__isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
	__isl_take isl_set *range)
{ … }

/* Return a newly allocated isl_map with given space and flags and
 * room for "n" basic maps.
 * Make sure that all cached information is cleared.
 */
__isl_give isl_map *isl_map_alloc_space(__isl_take isl_space *space, int n,
	unsigned flags)
{ … }

__isl_give isl_basic_map *isl_basic_map_empty(__isl_take isl_space *space)
{ … }

__isl_give isl_basic_set *isl_basic_set_empty(__isl_take isl_space *space)
{ … }

__isl_give isl_basic_map *isl_basic_map_universe(__isl_take isl_space *space)
{ … }

__isl_give isl_basic_set *isl_basic_set_universe(__isl_take isl_space *space)
{ … }

__isl_give isl_basic_map *isl_basic_map_nat_universe(
	__isl_take isl_space *space)
{ … }

__isl_give isl_basic_set *isl_basic_set_nat_universe(
	__isl_take isl_space *space)
{ … }

__isl_give isl_map *isl_map_nat_universe(__isl_take isl_space *space)
{ … }

__isl_give isl_set *isl_set_nat_universe(__isl_take isl_space *space)
{ … }

__isl_give isl_map *isl_map_empty(__isl_take isl_space *space)
{ … }

__isl_give isl_set *isl_set_empty(__isl_take isl_space *space)
{ … }

__isl_give isl_map *isl_map_universe(__isl_take isl_space *space)
{ … }

/* This function performs the same operation as isl_map_universe,
 * but is considered as a function on an isl_space when exported.
 */
__isl_give isl_map *isl_space_universe_map(__isl_take isl_space *space)
{ … }

__isl_give isl_set *isl_set_universe(__isl_take isl_space *space)
{ … }

/* This function performs the same operation as isl_set_universe,
 * but is considered as a function on an isl_space when exported.
 */
__isl_give isl_set *isl_space_universe_set(__isl_take isl_space *space)
{ … }

__isl_give isl_map *isl_map_dup(__isl_keep isl_map *map)
{ … }

__isl_give isl_map *isl_map_add_basic_map(__isl_take isl_map *map,
						__isl_take isl_basic_map *bmap)
{ … }

__isl_null isl_map *isl_map_free(__isl_take isl_map *map)
{ … }

static __isl_give isl_basic_map *isl_basic_map_fix_pos_si(
	__isl_take isl_basic_map *bmap, unsigned pos, int value)
{ … }

static __isl_give isl_basic_map *isl_basic_map_fix_pos(
	__isl_take isl_basic_map *bmap, unsigned pos, isl_int value)
{ … }

__isl_give isl_basic_map *isl_basic_map_fix_si(__isl_take isl_basic_map *bmap,
		enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_basic_map *isl_basic_map_fix(__isl_take isl_basic_map *bmap,
		enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

/* Fix the value of the variable at position "pos" of type "type" of "bmap"
 * to be equal to "v".
 */
__isl_give isl_basic_map *isl_basic_map_fix_val(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
{ … }

/* Fix the value of the variable at position "pos" of type "type" of "bset"
 * to be equal to "v".
 */
__isl_give isl_basic_set *isl_basic_set_fix_val(__isl_take isl_basic_set *bset,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
{ … }

__isl_give isl_basic_set *isl_basic_set_fix_si(__isl_take isl_basic_set *bset,
		enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_basic_set *isl_basic_set_fix(__isl_take isl_basic_set *bset,
		enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

/* Remove the basic map at position "i" from "map" if this basic map
 * is (obviously) empty.
 */
static __isl_give isl_map *remove_if_empty(__isl_take isl_map *map, int i)
{ … }

/* Perform "fn" on each basic map of "map", where we may not be holding
 * the only reference to "map".
 * In particular, "fn" should be a semantics preserving operation
 * that we want to apply to all copies of "map".  We therefore need
 * to be careful not to modify "map" in a way that breaks "map"
 * in case anything goes wrong.
 */
__isl_give isl_map *isl_map_inline_foreach_basic_map(__isl_take isl_map *map,
	__isl_give isl_basic_map *(*fn)(__isl_take isl_basic_map *bmap))
{ … }

__isl_give isl_map *isl_map_fix_si(__isl_take isl_map *map,
		enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
		enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
		enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

__isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
		enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

/* Fix the value of the variable at position "pos" of type "type" of "map"
 * to be equal to "v".
 */
__isl_give isl_map *isl_map_fix_val(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
{ … }

/* Fix the value of the variable at position "pos" of type "type" of "set"
 * to be equal to "v".
 */
__isl_give isl_set *isl_set_fix_val(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *v)
{ … }

__isl_give isl_map *isl_map_fix_input_si(__isl_take isl_map *map,
		unsigned input, int value)
{ … }

__isl_give isl_set *isl_set_fix_dim_si(__isl_take isl_set *set, unsigned dim,
	int value)
{ … }

static __isl_give isl_basic_map *basic_map_bound_si(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, int value, int upper)
{ … }

__isl_give isl_basic_map *isl_basic_map_lower_bound_si(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, int value)
{ … }

/* Constrain the values of the given dimension to be no greater than "value".
 */
__isl_give isl_basic_map *isl_basic_map_upper_bound_si(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, int value)
{ … }

static __isl_give isl_map *map_bound_si(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, int value, int upper)
{ … }

__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_map *isl_map_upper_bound_si(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
		enum isl_dim_type type, unsigned pos, int value)
{ … }

__isl_give isl_set *isl_set_upper_bound_si(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, int value)
{ … }

/* Bound the given variable of "bmap" from below (or above is "upper"
 * is set) to "value".
 */
static __isl_give isl_basic_map *basic_map_bound(
	__isl_take isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, isl_int value, int upper)
{ … }

/* Bound the given variable of "map" from below (or above is "upper"
 * is set) to "value".
 */
static __isl_give isl_map *map_bound(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, isl_int value, int upper)
{ … }

__isl_give isl_map *isl_map_lower_bound(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

__isl_give isl_map *isl_map_upper_bound(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

__isl_give isl_set *isl_set_lower_bound(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

__isl_give isl_set *isl_set_upper_bound(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, isl_int value)
{ … }

/* Force the values of the variable at position "pos" of type "type" of "map"
 * to be no smaller than "value".
 */
__isl_give isl_map *isl_map_lower_bound_val(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *value)
{ … }

/* Force the values of the variable at position "pos" of type "type" of "set"
 * to be no smaller than "value".
 */
__isl_give isl_set *isl_set_lower_bound_val(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *value)
{ … }

/* Force the values of the variable at position "pos" of type "type" of "map"
 * to be no greater than "value".
 */
__isl_give isl_map *isl_map_upper_bound_val(__isl_take isl_map *map,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *value)
{ … }

/* Force the values of the variable at position "pos" of type "type" of "set"
 * to be no greater than "value".
 */
__isl_give isl_set *isl_set_upper_bound_val(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned pos, __isl_take isl_val *value)
{ … }

/* If "mv" has an explicit domain, then intersect the domain of "map"
 * with this explicit domain.
 *
 * An isl_multi_val object never has an explicit domain,
 * so simply return "map".
 */
static __isl_give isl_map *isl_map_intersect_multi_val_explicit_domain(
	__isl_take isl_map *map, __isl_keep isl_multi_val *mv)
{ … }

#undef BASE
#define BASE …
#include "isl_map_bound_templ.c"

/* Apply "map_bound" to "set" with the corresponding value in "bound"
 * for each set dimension, by treating the set as a map.
 */
static __isl_give isl_set *set_bound_multi_val(__isl_take isl_set *set,
	__isl_take isl_multi_val *bound,
	__isl_give isl_map *map_bound(__isl_take isl_map *map,
		unsigned pos, __isl_take isl_val *value))
{ … }

#undef BASE
#define BASE …
#include "isl_map_bound_templ.c"

/* Apply "map_bound" to "set" with the corresponding value in "bound"
 * for each set dimension, by converting the set and the bound
 * to objects living in a map space.
 */
static __isl_give isl_set *set_bound_multi_pw_aff(__isl_take isl_set *set,
	__isl_take isl_multi_pw_aff *bound,
	__isl_give isl_map *set_bound(__isl_take isl_map *map,
		unsigned pos, __isl_take TYPE *value))
{ … }

/* Wrapper around isl_map_lower_bound_val for use in map_bound_multi_val,
 * setting a bound on the given output dimension.
 */
static __isl_give isl_map *map_lower_bound_val(__isl_take isl_map *map,
	unsigned pos, __isl_take isl_val *v)
{ … }

/* Force the values of the set dimensions of "set"
 * to be no smaller than the corresponding values in "lower".
 */
__isl_give isl_set *isl_set_lower_bound_multi_val(__isl_take isl_set *set,
	__isl_take isl_multi_val *lower)
{ … }

/* Wrapper around isl_map_upper_bound_val for use in map_bound_multi_val,
 * setting a bound on the given output dimension.
 */
static __isl_give isl_map *map_upper_bound_val(__isl_take isl_map *map,
	unsigned pos, __isl_take isl_val *v)
{ … }

/* Force the values of the set dimensions of "set"
 * to be no greater than the corresponding values in "upper".
 */
__isl_give isl_set *isl_set_upper_bound_multi_val(__isl_take isl_set *set,
	__isl_take isl_multi_val *upper)
{ … }

/* Force the symbolic constant expression "bound"
 * to satisfy the relation "order" with respect to
 * the output variable at position "pos" of "map".
 *
 * Create an affine expression representing the output variable
 * in terms of the range and
 * compare it using "order" to "bound" (defined on the domain).
 * The result is a relation between elements in domain and range that
 * can be intersected with "map".
 */
static __isl_give isl_map *map_bound_pw_aff(__isl_take isl_map *map,
	unsigned pos, __isl_take isl_pw_aff *bound,
	__isl_give isl_map *(*order)(__isl_take isl_pw_aff *pa1,
		__isl_take isl_pw_aff *pa2))
{ … }

/* Force the values of the output variable at position "pos" of "map"
 * to be no smaller than the symbolic constant expression "lower".
 */
static __isl_give isl_map *map_lower_bound_pw_aff(__isl_take isl_map *map,
	unsigned pos, __isl_take isl_pw_aff *lower)
{ … }

/* Force the values of the output variable at position "pos" of "map"
 * to be no greater than the symbolic constant expression "upper".
 */
static __isl_give isl_map *map_upper_bound_pw_aff(__isl_take isl_map *map,
	unsigned pos, __isl_take isl_pw_aff *upper)
{ … }

/* Force the values of the set dimensions of "set"
 * to be no smaller than the corresponding constant symbolic expressions
 * in "lower".
 */
__isl_give isl_set *isl_set_lower_bound_multi_pw_aff(__isl_take isl_set *set,
	__isl_take isl_multi_pw_aff *lower)
{ … }

/* Force the values of the set dimensions of "set"
 * to be no greater than the corresponding constant symbolic expressions
 * in "upper".
 */
__isl_give isl_set *isl_set_upper_bound_multi_pw_aff(__isl_take isl_set *set,
	__isl_take isl_multi_pw_aff *upper)
{ … }

/* Force the values of the output dimensions of "map"
 * to be no smaller than the corresponding constant symbolic expressions
 * in "lower".
 */
__isl_give isl_map *isl_map_lower_bound_multi_pw_aff(__isl_take isl_map *map,
	__isl_take isl_multi_pw_aff *lower)
{ … }

/* Force the values of the output dimensions of "map"
 * to be no greater than the corresponding constant symbolic expressions
 * in "upper".
 */
__isl_give isl_map *isl_map_upper_bound_multi_pw_aff(__isl_take isl_map *map,
	__isl_take isl_multi_pw_aff *upper)
{ … }

/* Bound the given variable of "bset" from below (or above is "upper"
 * is set) to "value".
 */
static __isl_give isl_basic_set *isl_basic_set_bound(
	__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned pos,
	isl_int value, int upper)
{ … }

/* Bound the given variable of "bset" from below (or above is "upper"
 * is set) to "value".
 */
static __isl_give isl_basic_set *isl_basic_set_bound_val(
	__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned pos,
	__isl_take isl_val *value, int upper)
{ … }

/* Bound the given variable of "bset" from below to "value".
 */
__isl_give isl_basic_set *isl_basic_set_lower_bound_val(
	__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned pos,
	__isl_take isl_val *value)
{ … }

/* Bound the given variable of "bset" from above to "value".
 */
__isl_give isl_basic_set *isl_basic_set_upper_bound_val(
	__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned pos,
	__isl_take isl_val *value)
{ … }

__isl_give isl_map *isl_map_reverse(__isl_take isl_map *map)
{ … }

/* Given a map A -> (B -> C), return the corresponding map A -> (C -> B).
 */
__isl_give isl_map *isl_map_range_reverse(__isl_take isl_map *map)
{ … }

#undef TYPE
#define TYPE …
#undef SUFFIX
#define SUFFIX …
#undef EMPTY
#define EMPTY …
#undef ADD
#define ADD …
#include "isl_map_lexopt_templ.c"

/* Given a map "map", compute the lexicographically minimal
 * (or maximal) image element for each domain element in dom,
 * in the form of an isl_pw_multi_aff.
 * If "empty" is not NULL, then set *empty to those elements in dom that
 * do not have an image element.
 * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum
 * should be computed over the domain of "map".  "empty" is also NULL
 * in this case.
 *
 * We first compute the lexicographically minimal or maximal element
 * in the first basic map.  This results in a partial solution "res"
 * and a subset "todo" of dom that still need to be handled.
 * We then consider each of the remaining maps in "map" and successively
 * update both "res" and "todo".
 * If "empty" is NULL, then the todo sets are not needed and therefore
 * also not computed.
 */
static __isl_give isl_pw_multi_aff *isl_map_partial_lexopt_aligned_pw_multi_aff(
	__isl_take isl_map *map, __isl_take isl_set *dom,
	__isl_give isl_set **empty, unsigned flags)
{ … }

#undef TYPE
#define TYPE …
#undef SUFFIX
#define SUFFIX
#undef EMPTY
#define EMPTY …
#undef ADD
#define ADD …
#include "isl_map_lexopt_templ.c"

/* Given a map "map", compute the lexicographically minimal
 * (or maximal) image element for each domain element in "dom",
 * in the form of an isl_map.
 * If "empty" is not NULL, then set *empty to those elements in "dom" that
 * do not have an image element.
 * If "flags" includes ISL_OPT_FULL, then "dom" is NULL and the optimum
 * should be computed over the domain of "map".  "empty" is also NULL
 * in this case.
 *
 * If the input consists of more than one disjunct, then first
 * compute the desired result in the form of an isl_pw_multi_aff and
 * then convert that into an isl_map.
 *
 * This function used to have an explicit implementation in terms
 * of isl_maps, but it would continually intersect the domains of
 * partial results with the complement of the domain of the next
 * partial solution, potentially leading to an explosion in the number
 * of disjuncts if there are several disjuncts in the input.
 * An even earlier implementation of this function would look for
 * better results in the domain of the partial result and for extra
 * results in the complement of this domain, which would lead to
 * even more splintering.
 */
static __isl_give isl_map *isl_map_partial_lexopt_aligned(
	__isl_take isl_map *map, __isl_take isl_set *dom,
	__isl_give isl_set **empty, unsigned flags)
{ … }

__isl_give isl_map *isl_map_partial_lexmax(
		__isl_take isl_map *map, __isl_take isl_set *dom,
		__isl_give isl_set **empty)
{ … }

__isl_give isl_map *isl_map_partial_lexmin(
		__isl_take isl_map *map, __isl_take isl_set *dom,
		__isl_give isl_set **empty)
{ … }

__isl_give isl_set *isl_set_partial_lexmin(
		__isl_take isl_set *set, __isl_take isl_set *dom,
		__isl_give isl_set **empty)
{ … }

__isl_give isl_set *isl_set_partial_lexmax(
		__isl_take isl_set *set, __isl_take isl_set *dom,
		__isl_give isl_set **empty)
{ … }

/* Compute the lexicographic minimum (or maximum if "flags" includes
 * ISL_OPT_MAX) of "bset" over its parametric domain.
 */
__isl_give isl_set *isl_basic_set_lexopt(__isl_take isl_basic_set *bset,
	unsigned flags)
{ … }

__isl_give isl_map *isl_basic_map_lexmax(__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_set *isl_basic_set_lexmin(__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_set *isl_basic_set_lexmax(__isl_take isl_basic_set *bset)
{ … }

/* Compute the lexicographic minimum of "bset" over its parametric domain
 * for the purpose of quantifier elimination.
 * That is, find an explicit representation for all the existentially
 * quantified variables in "bset" by computing their lexicographic
 * minimum.
 */
static __isl_give isl_set *isl_basic_set_lexmin_compute_divs(
	__isl_take isl_basic_set *bset)
{ … }

/* Given a basic map with one output dimension, compute the minimum or
 * maximum of that dimension as an isl_pw_aff.
 *
 * Compute the optimum as a lexicographic optimum over the single
 * output dimension and extract the single isl_pw_aff from the result.
 */
static __isl_give isl_pw_aff *basic_map_dim_opt(__isl_keep isl_basic_map *bmap,
	int max)
{ … }

/* Compute the minimum or maximum of the given output dimension
 * as a function of the parameters and the input dimensions,
 * but independently of the other output dimensions.
 *
 * We first project out the other output dimension and then compute
 * the "lexicographic" maximum in each basic map, combining the results
 * using isl_pw_aff_union_max.
 */
static __isl_give isl_pw_aff *map_dim_opt(__isl_take isl_map *map, int pos,
	int max)
{ … }

/* Compute the minimum of the given output dimension as a function of the
 * parameters and input dimensions, but independently of
 * the other output dimensions.
 */
__isl_give isl_pw_aff *isl_map_dim_min(__isl_take isl_map *map, int pos)
{ … }

/* Compute the maximum of the given output dimension as a function of the
 * parameters and input dimensions, but independently of
 * the other output dimensions.
 */
__isl_give isl_pw_aff *isl_map_dim_max(__isl_take isl_map *map, int pos)
{ … }

/* Compute the minimum or maximum of the given set dimension
 * as a function of the parameters,
 * but independently of the other set dimensions.
 */
static __isl_give isl_pw_aff *set_dim_opt(__isl_take isl_set *set, int pos,
	int max)
{ … }

/* Compute the maximum of the given set dimension as a function of the
 * parameters, but independently of the other set dimensions.
 */
__isl_give isl_pw_aff *isl_set_dim_max(__isl_take isl_set *set, int pos)
{ … }

/* Compute the minimum of the given set dimension as a function of the
 * parameters, but independently of the other set dimensions.
 */
__isl_give isl_pw_aff *isl_set_dim_min(__isl_take isl_set *set, int pos)
{ … }

/* Apply a preimage specified by "mat" on the parameters of "bset".
 * bset is assumed to have only parameters and divs.
 */
static __isl_give isl_basic_set *basic_set_parameter_preimage(
	__isl_take isl_basic_set *bset, __isl_take isl_mat *mat)
{ … }

/* Apply a preimage specified by "mat" on the parameters of "set".
 * set is assumed to have only parameters and divs.
 */
static __isl_give isl_set *set_parameter_preimage(__isl_take isl_set *set,
	__isl_take isl_mat *mat)
{ … }

/* Intersect the basic set "bset" with the affine space specified by the
 * equalities in "eq".
 */
static __isl_give isl_basic_set *basic_set_append_equalities(
	__isl_take isl_basic_set *bset, __isl_take isl_mat *eq)
{ … }

/* Intersect the set "set" with the affine space specified by the
 * equalities in "eq".
 */
static __isl_give isl_set *set_append_equalities(__isl_take isl_set *set,
	__isl_take isl_mat *eq)
{ … }

/* Given a basic set "bset" that only involves parameters and existentially
 * quantified variables, return the index of the first equality
 * that only involves parameters.  If there is no such equality then
 * return bset->n_eq.
 *
 * This function assumes that isl_basic_set_gauss has been called on "bset".
 */
static int first_parameter_equality(__isl_keep isl_basic_set *bset)
{ … }

/* Compute an explicit representation for the existentially quantified
 * variables in "bset" by computing the "minimal value" of the set
 * variables.  Since there are no set variables, the computation of
 * the minimal value essentially computes an explicit representation
 * of the non-empty part(s) of "bset".
 *
 * The input only involves parameters and existentially quantified variables.
 * All equalities among parameters have been removed.
 *
 * Since the existentially quantified variables in the result are in general
 * going to be different from those in the input, we first replace
 * them by the minimal number of variables based on their equalities.
 * This should simplify the parametric integer programming.
 */
static __isl_give isl_set *base_compute_divs(__isl_take isl_basic_set *bset)
{ … }

/* Project the given basic set onto its parameter domain, possibly introducing
 * new, explicit, existential variables in the constraints.
 * The input has parameters and (possibly implicit) existential variables.
 * The output has the same parameters, but only
 * explicit existentially quantified variables.
 *
 * The actual projection is performed by pip, but pip doesn't seem
 * to like equalities very much, so we first remove the equalities
 * among the parameters by performing a variable compression on
 * the parameters.  Afterward, an inverse transformation is performed
 * and the equalities among the parameters are inserted back in.
 *
 * The variable compression on the parameters may uncover additional
 * equalities that were only implicit before.  We therefore check
 * if there are any new parameter equalities in the result and
 * if so recurse.  The removal of parameter equalities is required
 * for the parameter compression performed by base_compute_divs.
 */
static __isl_give isl_set *parameter_compute_divs(
	__isl_take isl_basic_set *bset)
{ … }

/* Insert the divs from "ls" before those of "bmap".
 *
 * The number of columns is not changed, which means that the last
 * dimensions of "bmap" are being reintepreted as the divs from "ls".
 * The caller is responsible for removing the same number of dimensions
 * from the space of "bmap".
 */
static __isl_give isl_basic_map *insert_divs_from_local_space(
	__isl_take isl_basic_map *bmap, __isl_keep isl_local_space *ls)
{ … }

/* Replace the space of "bmap" by the space and divs of "ls".
 *
 * If "ls" has any divs, then we simplify the result since we may
 * have discovered some additional equalities that could simplify
 * the div expressions.
 */
static __isl_give isl_basic_map *basic_replace_space_by_local_space(
	__isl_take isl_basic_map *bmap, __isl_take isl_local_space *ls)
{ … }

/* Replace the space of "map" by the space and divs of "ls".
 */
static __isl_give isl_map *replace_space_by_local_space(__isl_take isl_map *map,
	__isl_take isl_local_space *ls)
{ … }

/* Compute an explicit representation for the existentially
 * quantified variables for which do not know any explicit representation yet.
 *
 * We first sort the existentially quantified variables so that the
 * existentially quantified variables for which we already have an explicit
 * representation are placed before those for which we do not.
 * The input dimensions, the output dimensions and the existentially
 * quantified variables for which we already have an explicit
 * representation are then turned into parameters.
 * compute_divs returns a map with the same parameters and
 * no input or output dimensions and the dimension specification
 * is reset to that of the input, including the existentially quantified
 * variables for which we already had an explicit representation.
 */
static __isl_give isl_map *compute_divs(__isl_take isl_basic_map *bmap)
{ … }

/* Remove the explicit representation of local variable "div",
 * if there is any.
 */
__isl_give isl_basic_map *isl_basic_map_mark_div_unknown(
	__isl_take isl_basic_map *bmap, int div)
{ … }

/* Is local variable "div" of "bmap" marked as not having an explicit
 * representation?
 * Note that even if "div" is not marked in this way and therefore
 * has an explicit representation, this representation may still
 * depend (indirectly) on other local variables that do not
 * have an explicit representation.
 */
isl_bool isl_basic_map_div_is_marked_unknown(__isl_keep isl_basic_map *bmap,
	int div)
{ … }

/* Return the position of the first local variable that does not
 * have an explicit representation.
 * Return the total number of local variables if they all have
 * an explicit representation.
 * Return -1 on error.
 */
int isl_basic_map_first_unknown_div(__isl_keep isl_basic_map *bmap)
{ … }

/* Return the position of the first local variable that does not
 * have an explicit representation.
 * Return the total number of local variables if they all have
 * an explicit representation.
 * Return -1 on error.
 */
int isl_basic_set_first_unknown_div(__isl_keep isl_basic_set *bset)
{ … }

/* Does "bmap" have an explicit representation for all local variables?
 */
isl_bool isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap)
{ … }

/* Do all basic maps in "map" have an explicit representation
 * for all local variables?
 */
isl_bool isl_map_divs_known(__isl_keep isl_map *map)
{ … }

/* If bmap contains any unknown divs, then compute explicit
 * expressions for them.  However, this computation may be
 * quite expensive, so first try to remove divs that aren't
 * strictly needed.
 */
__isl_give isl_map *isl_basic_map_compute_divs(__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_map *isl_map_compute_divs(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_basic_set_compute_divs(__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_set *isl_set_compute_divs(__isl_take isl_set *set)
{ … }

__isl_give isl_set *isl_map_domain(__isl_take isl_map *map)
{ … }

/* Return the union of "map1" and "map2", where we assume for now that
 * "map1" and "map2" are disjoint.  Note that the basic maps inside
 * "map1" or "map2" may not be disjoint from each other.
 * Also note that this function is also called from isl_map_union,
 * which takes care of handling the situation where "map1" and "map2"
 * may not be disjoint.
 *
 * If one of the inputs is empty, we can simply return the other input.
 * Similarly, if one of the inputs is universal, then it is equal to the union.
 */
static __isl_give isl_map *map_union_disjoint(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Return the union of "map1" and "map2", where "map1" and "map2" are
 * guaranteed to be disjoint by the caller.
 *
 * Note that this functions is called from within isl_map_make_disjoint,
 * so we have to be careful not to touch the constraints of the inputs
 * in any way.
 */
__isl_give isl_map *isl_map_union_disjoint(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Return the union of "map1" and "map2", where "map1" and "map2" may
 * not be disjoint.
 *
 * We currently simply call map_union_disjoint, the internal operation
 * of which does not really depend on the inputs being disjoint.
 * If the result contains more than one basic map, then we clear
 * the disjoint flag since the result may contain basic maps from
 * both inputs and these are not guaranteed to be disjoint.
 *
 * As a special case, if "map1" and "map2" are obviously equal,
 * then we simply return "map1".
 */
__isl_give isl_map *isl_map_union(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_set *isl_set_union_disjoint(
	__isl_take isl_set *set1, __isl_take isl_set *set2)
{ … }

__isl_give isl_set *isl_set_union(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

/* Apply "fn" to pairs of elements from "map" and "set" and collect
 * the results in a map living in "space".
 *
 * "map" and "set" are assumed to be compatible and non-NULL.
 */
static __isl_give isl_map *map_intersect_set(__isl_take isl_map *map,
	__isl_take isl_space *space, __isl_take isl_set *set,
	__isl_give isl_basic_map *fn(__isl_take isl_basic_map *bmap,
		__isl_take isl_basic_set *bset))
{ … }

__isl_give isl_map *isl_map_intersect_range(__isl_take isl_map *map,
	__isl_take isl_set *set)
{ … }

/* Intersect the domain of "map" with "set".
 *
 * If the domain dimensions of "map" do not have any identifiers,
 * then copy them over from "set".
 */
__isl_give isl_map *isl_map_intersect_domain(__isl_take isl_map *map,
	__isl_take isl_set *set)
{ … }

#undef TYPE
#define TYPE …
static
#include "isl_copy_tuple_id_templ.c"

/* Data structure that specifies how isl_map_intersect_factor
 * should operate.
 *
 * "preserve_type" is the tuple where the factor differs from
 * the input map and of which the identifiers needs
 * to be preserved explicitly.
 * "other_factor" is used to extract the space of the other factor
 * from the space of the product ("map").
 * "product" is used to combine the given factor and a universe map
 * in the space returned by "other_factor" to produce a map
 * that lives in the same space as the input map.
 */
struct isl_intersect_factor_control { … };

/* Given a map "map" in some product space and a map "factor"
 * living in some factor space, return the intersection.
 *
 * After aligning the parameters,
 * the map "factor" is first extended to a map living in the same space
 * as "map" and then a regular intersection is computed.
 *
 * Note that the extension is computed as a product, which is anonymous
 * by default.  If "map" has an identifier on the corresponding tuple,
 * then this identifier needs to be set on the product
 * before the intersection is computed.
 */
static __isl_give isl_map *isl_map_intersect_factor(
	__isl_take isl_map *map, __isl_take isl_map *factor,
	struct isl_intersect_factor_control *control)
{ … }

/* Return the domain product of "map2" and "map1".
 */
static __isl_give isl_map *isl_map_reverse_domain_product(
	__isl_take isl_map *map1, __isl_take isl_map *map2)
{ … }

/* Return the range product of "map2" and "map1".
 */
static __isl_give isl_map *isl_map_reverse_range_product(
	__isl_take isl_map *map1, __isl_take isl_map *map2)
{ … }

/* Given a map "map" in a space [A -> B] -> C and a map "factor"
 * in the space A -> C, return the intersection.
 */
__isl_give isl_map *isl_map_intersect_domain_factor_domain(
	__isl_take isl_map *map, __isl_take isl_map *factor)
{ … }

/* Given a map "map" in a space [A -> B] -> C and a map "factor"
 * in the space B -> C, return the intersection.
 */
__isl_give isl_map *isl_map_intersect_domain_factor_range(
	__isl_take isl_map *map, __isl_take isl_map *factor)
{ … }

/* Given a map "map" in a space A -> [B -> C] and a map "factor"
 * in the space A -> B, return the intersection.
 */
__isl_give isl_map *isl_map_intersect_range_factor_domain(
	__isl_take isl_map *map, __isl_take isl_map *factor)
{ … }

/* Given a map "map" in a space A -> [B -> C] and a map "factor"
 * in the space A -> C, return the intersection.
 */
__isl_give isl_map *isl_map_intersect_range_factor_range(
	__isl_take isl_map *map, __isl_take isl_map *factor)
{ … }

/* Given a set "set" in a space [A -> B] and a set "domain"
 * in the space A, return the intersection.
 *
 * The set "domain" is first extended to a set living in the space
 * [A -> B] and then a regular intersection is computed.
 */
__isl_give isl_set *isl_set_intersect_factor_domain(__isl_take isl_set *set,
	__isl_take isl_set *domain)
{ … }

/* Given a set "set" in a space [A -> B] and a set "range"
 * in the space B, return the intersection.
 *
 * The set "range" is first extended to a set living in the space
 * [A -> B] and then a regular intersection is computed.
 */
__isl_give isl_set *isl_set_intersect_factor_range(__isl_take isl_set *set,
	__isl_take isl_set *range)
{ … }

/* Given a map "map" in a space [A -> B] -> C and a set "domain"
 * in the space A, return the intersection.
 *
 * The set "domain" is extended to a set living in the space [A -> B] and
 * the domain of "map" is intersected with this set.
 */
__isl_give isl_map *isl_map_intersect_domain_wrapped_domain(
	__isl_take isl_map *map, __isl_take isl_set *domain)
{ … }

/* Given a map "map" in a space A -> [B -> C] and a set "domain"
 * in the space B, return the intersection.
 *
 * The set "domain" is extended to a set living in the space [B -> C] and
 * the range of "map" is intersected with this set.
 */
__isl_give isl_map *isl_map_intersect_range_wrapped_domain(
	__isl_take isl_map *map, __isl_take isl_set *domain)
{ … }

__isl_give isl_map *isl_map_apply_domain(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

__isl_give isl_map *isl_map_apply_range(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Is "bmap" a transformation, i.e.,
 * does it relate elements from the same space.
 */
isl_bool isl_basic_map_is_transformation(__isl_keep isl_basic_map *bmap)
{ … }

/* Check that "bmap" is a transformation, i.e.,
 * that it relates elements from the same space.
 */
static isl_stat isl_basic_map_check_transformation(
	__isl_keep isl_basic_map *bmap)
{ … }

/*
 * returns range - domain
 */
__isl_give isl_basic_set *isl_basic_map_deltas(__isl_take isl_basic_map *bmap)
{ … }

/* Is the tuple of type "type1" of "map" the same as
 * the tuple of type "type2" of "space"?
 */
isl_bool isl_map_space_tuple_is_equal(__isl_keep isl_map *map,
	enum isl_dim_type type1, __isl_keep isl_space *space,
	enum isl_dim_type type2)
{ … }

/* Is the tuple of type "type1" of "map1" the same as
 * the tuple of type "type2" of "map2"?
 */
isl_bool isl_map_tuple_is_equal(__isl_keep isl_map *map1,
	enum isl_dim_type type1, __isl_keep isl_map *map2,
	enum isl_dim_type type2)
{ … }

/* Is the space of "obj" equal to "space", ignoring parameters?
 */
isl_bool isl_map_has_space_tuples(__isl_keep isl_map *map,
	__isl_keep isl_space *space)
{ … }

/* Check that "map" is a transformation, i.e.,
 * that it relates elements from the same space.
 */
isl_stat isl_map_check_transformation(__isl_keep isl_map *map)
{ … }

/*
 * returns range - domain
 */
__isl_give isl_set *isl_map_deltas(__isl_take isl_map *map)
{ … }

/*
 * returns [domain -> range] -> range - domain
 */
__isl_give isl_basic_map *isl_basic_map_deltas_map(
	__isl_take isl_basic_map *bmap)
{ … }

/*
 * returns [domain -> range] -> range - domain
 */
__isl_give isl_map *isl_map_deltas_map(__isl_take isl_map *map)
{ … }

/* Return pairs of elements { x -> y } such that y - x is in "deltas".
 */
__isl_give isl_map *isl_set_translation(__isl_take isl_set *deltas)
{ … }

__isl_give isl_basic_map *isl_basic_map_identity(__isl_take isl_space *space)
{ … }

__isl_give isl_map *isl_map_identity(__isl_take isl_space *space)
{ … }

__isl_give isl_map *isl_set_identity(__isl_take isl_set *set)
{ … }

/* Construct a basic set with all set dimensions having only non-negative
 * values.
 */
__isl_give isl_basic_set *isl_basic_set_positive_orthant(
	__isl_take isl_space *space)
{ … }

/* Construct the half-space x_pos >= 0.
 */
static __isl_give isl_basic_set *nonneg_halfspace(__isl_take isl_space *space,
	int pos)
{ … }

/* Construct the half-space x_pos <= -1.
 */
static __isl_give isl_basic_set *neg_halfspace(__isl_take isl_space *space,
	int pos)
{ … }

__isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set,
	enum isl_dim_type type, unsigned first, unsigned n)
{ … }

static isl_stat foreach_orthant(__isl_take isl_set *set, int *signs, int first,
	int len,
	isl_stat (*fn)(__isl_take isl_set *orthant, int *signs, void *user),
	void *user)
{ … }

/* Call "fn" on the intersections of "set" with each of the orthants
 * (except for obviously empty intersections).  The orthant is identified
 * by the signs array, with each entry having value 1 or -1 according
 * to the sign of the corresponding variable.
 */
isl_stat isl_set_foreach_orthant(__isl_keep isl_set *set,
	isl_stat (*fn)(__isl_take isl_set *orthant, int *signs, void *user),
	void *user)
{ … }

isl_bool isl_set_is_equal(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
{ … }

isl_bool isl_basic_map_is_subset(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

isl_bool isl_basic_set_is_subset(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2)
{ … }

isl_bool isl_basic_map_is_equal(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

isl_bool isl_basic_set_is_equal(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2)
{ … }

isl_bool isl_map_is_empty(__isl_keep isl_map *map)
{ … }

isl_bool isl_map_plain_is_empty(__isl_keep isl_map *map)
{ … }

isl_bool isl_set_plain_is_empty(__isl_keep isl_set *set)
{ … }

isl_bool isl_set_is_empty(__isl_keep isl_set *set)
{ … }

#undef TYPE
#define TYPE …

static
#include "isl_type_has_equal_space_bin_templ.c"
#include "isl_type_check_equal_space_templ.c"

/* Check that "bset1" and "bset2" live in the same space,
 * reporting an error if they do not.
 */
isl_stat isl_basic_set_check_equal_space(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2)
{ … }

#undef TYPE
#define TYPE …

#include "isl_type_has_equal_space_bin_templ.c"
#include "isl_type_check_equal_space_templ.c"
#include "isl_type_has_space_templ.c"

isl_bool isl_set_has_equal_space(__isl_keep isl_set *set1,
	__isl_keep isl_set *set2)
{ … }

#undef TYPE1
#define TYPE1 …
#undef TYPE2
#define TYPE2 …
#undef TYPE_PAIR
#define TYPE_PAIR …

static
#include "isl_type_has_equal_space_templ.c"
#include "isl_type_check_equal_space_templ.c"

/* Check that "set" and "bset" live in the same space,
 * reporting an error if they do not.
 */
isl_stat isl_set_basic_set_check_equal_space(__isl_keep isl_set *set,
	__isl_keep isl_basic_set *bset)
{ … }

static isl_bool map_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
{ … }

/* Is "map1" equal to "map2"?
 *
 * First check if they are obviously equal.
 * If not, then perform a more detailed analysis.
 */
isl_bool isl_map_is_equal(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
{ … }

isl_bool isl_basic_map_is_strict_subset(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

isl_bool isl_map_is_strict_subset(__isl_keep isl_map *map1,
	__isl_keep isl_map *map2)
{ … }

isl_bool isl_set_is_strict_subset(__isl_keep isl_set *set1,
	__isl_keep isl_set *set2)
{ … }

/* Is "bmap" obviously equal to the universe with the same space?
 *
 * That is, does it not have any constraints?
 */
isl_bool isl_basic_map_plain_is_universe(__isl_keep isl_basic_map *bmap)
{ … }

/* Is "bset" obviously equal to the universe with the same space?
 */
isl_bool isl_basic_set_plain_is_universe(__isl_keep isl_basic_set *bset)
{ … }

/* If "c" does not involve any existentially quantified variables,
 * then set *univ to false and abort
 */
static isl_stat involves_divs(__isl_take isl_constraint *c, void *user)
{ … }

/* Is "bmap" equal to the universe with the same space?
 *
 * First check if it is obviously equal to the universe.
 * If not and if there are any constraints not involving
 * existentially quantified variables, then it is certainly
 * not equal to the universe.
 * Otherwise, check if the universe is a subset of "bmap".
 */
isl_bool isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap)
{ … }

/* Is "bset" equal to the universe with the same space?
 */
isl_bool isl_basic_set_is_universe(__isl_keep isl_basic_set *bset)
{ … }

isl_bool isl_map_plain_is_universe(__isl_keep isl_map *map)
{ … }

isl_bool isl_set_plain_is_universe(__isl_keep isl_set *set)
{ … }

isl_bool isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap)
{ … }

isl_bool isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap)
{ … }

isl_bool isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset)
{ … }

/* Is "bmap" known to be non-empty?
 *
 * That is, is the cached sample still valid?
 */
isl_bool isl_basic_map_plain_is_non_empty(__isl_keep isl_basic_map *bmap)
{ … }

isl_bool isl_basic_set_is_empty(__isl_keep isl_basic_set *bset)
{ … }

__isl_give isl_map *isl_basic_map_union(__isl_take isl_basic_map *bmap1,
	__isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_set *isl_basic_set_union(__isl_take isl_basic_set *bset1,
	__isl_take isl_basic_set *bset2)
{ … }

/* Order divs such that any div only depends on previous divs */
__isl_give isl_basic_map *isl_basic_map_order_divs(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
{ … }

/* Sort the local variables of "bset".
 */
__isl_give isl_basic_set *isl_basic_set_sort_divs(
	__isl_take isl_basic_set *bset)
{ … }

/* Apply the expansion computed by isl_merge_divs.
 * The expansion itself is given by "exp" while the resulting
 * list of divs is given by "div".
 *
 * Move the integer divisions of "bmap" into the right position
 * according to "exp" and then introduce the additional integer
 * divisions, adding div constraints.
 * The moving should be done first to avoid moving coefficients
 * in the definitions of the extra integer divisions.
 */
__isl_give isl_basic_map *isl_basic_map_expand_divs(
	__isl_take isl_basic_map *bmap, __isl_take isl_mat *div, int *exp)
{ … }

/* Apply the expansion computed by isl_merge_divs.
 * The expansion itself is given by "exp" while the resulting
 * list of divs is given by "div".
 */
__isl_give isl_basic_set *isl_basic_set_expand_divs(
	__isl_take isl_basic_set *bset, __isl_take isl_mat *div, int *exp)
{ … }

/* Look for a div in dst that corresponds to the div "div" in src.
 * The divs before "div" in src and dst are assumed to be the same.
 * 
 * Return the position of the corresponding div in dst
 * if there is one.  Otherwise, return a position beyond the integer divisions.
 * Return -1 on error.
 */
static int find_div(__isl_keep isl_basic_map *dst,
	__isl_keep isl_basic_map *src, unsigned div)
{ … }

/* Align the divs of "dst" to those of "src", adding divs from "src"
 * if needed.  That is, make sure that the first src->n_div divs
 * of the result are equal to those of src.
 * The integer division of "src" are assumed to be ordered.
 *
 * The integer divisions are swapped into the right position
 * (possibly after adding them first).  This may result
 * in the remaining integer divisions appearing in the wrong order,
 * i.e., with some integer division appearing before
 * some other integer division on which it depends.
 * The integer divisions therefore need to be ordered.
 * This will not affect the integer divisions aligned to those of "src",
 * since "src" is assumed to have ordered integer divisions.
 *
 * The result is not finalized as by design it will have redundant
 * divs if any divs from "src" were copied.
 */
__isl_give isl_basic_map *isl_basic_map_align_divs(
	__isl_take isl_basic_map *dst, __isl_keep isl_basic_map *src)
{ … }

__isl_give isl_map *isl_map_align_divs_internal(__isl_take isl_map *map)
{ … }

__isl_give isl_map *isl_map_align_divs(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_align_divs(__isl_take isl_set *set)
{ … }

/* Align the divs of the basic maps in "map" to those
 * of the basic maps in "list", as well as to the other basic maps in "map".
 * The elements in "list" are assumed to have known divs.
 */
__isl_give isl_map *isl_map_align_divs_to_basic_map_list(
	__isl_take isl_map *map, __isl_keep isl_basic_map_list *list)
{ … }

/* Align the divs of each element of "list" to those of "bmap".
 * Both "bmap" and the elements of "list" are assumed to have known divs.
 */
__isl_give isl_basic_map_list *isl_basic_map_list_align_divs_to_basic_map(
	__isl_take isl_basic_map_list *list, __isl_keep isl_basic_map *bmap)
{ … }

__isl_give isl_set *isl_set_apply( __isl_take isl_set *set,
	__isl_take isl_map *map)
{ … }

/* There is no need to cow as removing empty parts doesn't change
 * the meaning of the set.
 */
__isl_give isl_map *isl_map_remove_empty_parts(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_remove_empty_parts(__isl_take isl_set *set)
{ … }

/* Create a binary relation that maps the shared initial "pos" dimensions
 * of "bset1" and "bset2" to the remaining dimensions of "bset1" and "bset2".
 */
static __isl_give isl_basic_map *join_initial(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2, int pos)
{ … }

/* Given two basic sets bset1 and bset2, compute the maximal difference
 * between the values of dimension pos in bset1 and those in bset2
 * for any common value of the parameters and dimensions preceding pos.
 */
static enum isl_lp_result basic_set_maximal_difference_at(
	__isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2,
	int pos, isl_int *opt)
{ … }

/* Given two _disjoint_ basic sets bset1 and bset2, check whether
 * for any common value of the parameters and dimensions preceding pos
 * in both basic sets, the values of dimension pos in bset1 are
 * smaller or larger than those in bset2.
 *
 * Returns
 *	 1 if bset1 follows bset2
 *	-1 if bset1 precedes bset2
 *	 0 if bset1 and bset2 are incomparable
 *	-2 if some error occurred.
 */
int isl_basic_set_compare_at(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2, int pos)
{ … }

/* Given two basic sets bset1 and bset2, check whether
 * for any common value of the parameters and dimensions preceding pos
 * there is a value of dimension pos in bset1 that is larger
 * than a value of the same dimension in bset2.
 *
 * Return
 *	 1 if there exists such a pair
 *	 0 if there is no such pair, but there is a pair of equal values
 *	-1 otherwise
 *	-2 if some error occurred.
 */
int isl_basic_set_follows_at(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2, int pos)
{ … }

/* Given two sets set1 and set2, check whether
 * for any common value of the parameters and dimensions preceding pos
 * there is a value of dimension pos in set1 that is larger
 * than a value of the same dimension in set2.
 *
 * Return
 *	 1 if there exists such a pair
 *	 0 if there is no such pair, but there is a pair of equal values
 *	-1 otherwise
 *	-2 if some error occurred.
 */
int isl_set_follows_at(__isl_keep isl_set *set1,
	__isl_keep isl_set *set2, int pos)
{ … }

static isl_bool isl_basic_map_plain_has_fixed_var(
	__isl_keep isl_basic_map *bmap, unsigned pos, isl_int *val)
{ … }

static isl_bool isl_map_plain_has_fixed_var(__isl_keep isl_map *map,
	unsigned pos, isl_int *val)
{ … }

static isl_bool isl_basic_set_plain_has_fixed_var(
	__isl_keep isl_basic_set *bset, unsigned pos, isl_int *val)
{ … }

isl_bool isl_basic_map_plain_is_fixed(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, isl_int *val)
{ … }

/* If "bmap" obviously lies on a hyperplane where the given dimension
 * has a fixed value, then return that value.
 * Otherwise return NaN.
 */
__isl_give isl_val *isl_basic_map_plain_get_val_if_fixed(
	__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos)
{ … }

isl_bool isl_map_plain_is_fixed(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos, isl_int *val)
{ … }

/* If "map" obviously lies on a hyperplane where the given dimension
 * has a fixed value, then return that value.
 * Otherwise return NaN.
 */
__isl_give isl_val *isl_map_plain_get_val_if_fixed(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos)
{ … }

/* If "set" obviously lies on a hyperplane where the given dimension
 * has a fixed value, then return that value.
 * Otherwise return NaN.
 */
__isl_give isl_val *isl_set_plain_get_val_if_fixed(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Return a sequence of values in the same space as "set"
 * that are equal to the corresponding set dimensions of "set"
 * for those set dimensions that obviously lie on a hyperplane
 * where the dimension has a fixed value.
 * The other elements are set to NaN.
 */
__isl_give isl_multi_val *isl_set_get_plain_multi_val_if_fixed(
	__isl_keep isl_set *set)
{ … }

/* Check if dimension dim has fixed value and if so and if val is not NULL,
 * then return this fixed value in *val.
 */
isl_bool isl_basic_set_plain_dim_is_fixed(__isl_keep isl_basic_set *bset,
	unsigned dim, isl_int *val)
{ … }

/* Return -1 if the constraint "c1" should be sorted before "c2"
 * and 1 if it should be sorted after "c2".
 * Return 0 if the two constraints are the same (up to the constant term).
 *
 * In particular, if a constraint involves later variables than another
 * then it is sorted after this other constraint.
 * uset_gist depends on constraints without existentially quantified
 * variables sorting first.
 *
 * For constraints that have the same latest variable, those
 * with the same coefficient for this latest variable (first in absolute value
 * and then in actual value) are grouped together.
 * This is useful for detecting pairs of constraints that can
 * be chained in their printed representation.
 *
 * Finally, within a group, constraints are sorted according to
 * their coefficients (excluding the constant term).
 */
static int sort_constraint_cmp(const void *p1, const void *p2, void *arg)
{ … }

/* Return -1 if the constraint "c1" of "bmap" is sorted before "c2"
 * by isl_basic_map_sort_constraints, 1 if it is sorted after "c2"
 * and 0 if the two constraints are the same (up to the constant term).
 */
int isl_basic_map_constraint_cmp(__isl_keep isl_basic_map *bmap,
	isl_int *c1, isl_int *c2)
{ … }

__isl_give isl_basic_map *isl_basic_map_sort_constraints(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_sort_constraints(
	__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_normalize(
	__isl_take isl_basic_map *bmap)
{ … }
int isl_basic_map_plain_cmp(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

int isl_basic_set_plain_cmp(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2)
{ … }

int isl_set_plain_cmp(__isl_keep isl_set *set1, __isl_keep isl_set *set2)
{ … }

isl_bool isl_basic_map_plain_is_equal(__isl_keep isl_basic_map *bmap1,
	__isl_keep isl_basic_map *bmap2)
{ … }

isl_bool isl_basic_set_plain_is_equal(__isl_keep isl_basic_set *bset1,
	__isl_keep isl_basic_set *bset2)
{ … }

static int qsort_bmap_cmp(const void *p1, const void *p2)
{ … }

/* Sort the basic maps of "map" and remove duplicate basic maps.
 *
 * While removing basic maps, we make sure that the basic maps remain
 * sorted because isl_map_normalize expects the basic maps of the result
 * to be sorted.
 */
static __isl_give isl_map *sort_and_remove_duplicates(__isl_take isl_map *map)
{ … }

/* Remove obvious duplicates among the basic maps of "map".
 *
 * Unlike isl_map_normalize, this function does not remove redundant
 * constraints and only removes duplicates that have exactly the same
 * constraints in the input.  It does sort the constraints and
 * the basic maps to ease the detection of duplicates.
 *
 * If "map" has already been normalized or if the basic maps are
 * disjoint, then there can be no duplicates.
 */
__isl_give isl_map *isl_map_remove_obvious_duplicates(__isl_take isl_map *map)
{ … }

/* We normalize in place, but if anything goes wrong we need
 * to return NULL, so we need to make sure we don't change the
 * meaning of any possible other copies of map.
 */
__isl_give isl_map *isl_map_normalize(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_normalize(__isl_take isl_set *set)
{ … }

isl_bool isl_map_plain_is_equal(__isl_keep isl_map *map1,
	__isl_keep isl_map *map2)
{ … }

isl_bool isl_set_plain_is_equal(__isl_keep isl_set *set1,
	__isl_keep isl_set *set2)
{ … }

/* Return the basic maps in "map" as a list.
 */
__isl_give isl_basic_map_list *isl_map_get_basic_map_list(
	__isl_keep isl_map *map)
{ … }

/* Return the intersection of the elements in the non-empty list "list".
 * All elements are assumed to live in the same space.
 */
__isl_give isl_basic_map *isl_basic_map_list_intersect(
	__isl_take isl_basic_map_list *list)
{ … }

/* Return the intersection of the elements in the non-empty list "list".
 * All elements are assumed to live in the same space.
 */
__isl_give isl_basic_set *isl_basic_set_list_intersect(
	__isl_take isl_basic_set_list *list)
{ … }

/* Return the union of the elements of "list".
 * The list is required to have at least one element.
 */
__isl_give isl_set *isl_basic_set_list_union(
	__isl_take isl_basic_set_list *list)
{ … }

/* Return the union of the elements in the non-empty list "list".
 * All elements are assumed to live in the same space.
 */
__isl_give isl_set *isl_set_list_union(__isl_take isl_set_list *list)
{ … }

__isl_give isl_basic_map *isl_basic_map_product(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_map *isl_basic_map_flat_product(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_set *isl_basic_set_flat_product(
	__isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
{ … }

__isl_give isl_basic_map *isl_basic_map_domain_product(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_map *isl_basic_map_range_product(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

__isl_give isl_basic_map *isl_basic_map_flat_range_product(
	__isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{ … }

/* Apply "basic_map_product" to each pair of basic maps in "map1" and "map2"
 * and collect the results.
 * The result live in the space obtained by calling "space_product"
 * on the spaces of "map1" and "map2".
 * If "remove_duplicates" is set then the result may contain duplicates
 * (even if the inputs do not) and so we try and remove the obvious
 * duplicates.
 */
static __isl_give isl_map *map_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2,
	__isl_give isl_space *(*space_product)(__isl_take isl_space *left,
					   __isl_take isl_space *right),
	__isl_give isl_basic_map *(*basic_map_product)(
		__isl_take isl_basic_map *left,
		__isl_take isl_basic_map *right),
	int remove_duplicates)
{ … }

/* Given two maps A -> B and C -> D, construct a map [A -> C] -> [B -> D]
 */
__isl_give isl_map *isl_map_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Given two maps A -> B and C -> D, construct a map (A, C) -> (B, D)
 */
__isl_give isl_map *isl_map_flat_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Given two set A and B, construct its Cartesian product A x B.
 */
__isl_give isl_set *isl_set_product(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

__isl_give isl_set *isl_set_flat_product(__isl_take isl_set *set1,
	__isl_take isl_set *set2)
{ … }

/* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
 */
__isl_give isl_map *isl_map_domain_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Given two maps A -> B and C -> D, construct a map (A * C) -> [B -> D]
 */
__isl_give isl_map *isl_map_range_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Given a map of the form [A -> B] -> [C -> D], return the map A -> C.
 */
__isl_give isl_map *isl_map_factor_domain(__isl_take isl_map *map)
{ … }

/* Given a map of the form [A -> B] -> [C -> D], return the map B -> D.
 */
__isl_give isl_map *isl_map_factor_range(__isl_take isl_map *map)
{ … }

/* Given a map of the form [A -> B] -> C, return the map A -> C.
 */
__isl_give isl_map *isl_map_domain_factor_domain(__isl_take isl_map *map)
{ … }

/* Given a map of the form [A -> B] -> C, return the map B -> C.
 */
__isl_give isl_map *isl_map_domain_factor_range(__isl_take isl_map *map)
{ … }

/* Given a map A -> [B -> C], extract the map A -> B.
 */
__isl_give isl_map *isl_map_range_factor_domain(__isl_take isl_map *map)
{ … }

/* Given a map A -> [B -> C], extract the map A -> C.
 */
__isl_give isl_map *isl_map_range_factor_range(__isl_take isl_map *map)
{ … }

/* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D)
 */
__isl_give isl_map *isl_map_flat_domain_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

/* Given two maps A -> B and C -> D, construct a map (A * C) -> (B, D)
 */
__isl_give isl_map *isl_map_flat_range_product(__isl_take isl_map *map1,
	__isl_take isl_map *map2)
{ … }

uint32_t isl_basic_map_get_hash(__isl_keep isl_basic_map *bmap)
{ … }

uint32_t isl_basic_set_get_hash(__isl_keep isl_basic_set *bset)
{ … }

uint32_t isl_map_get_hash(__isl_keep isl_map *map)
{ … }

uint32_t isl_set_get_hash(__isl_keep isl_set *set)
{ … }

/* Return the number of basic maps in the (current) representation of "map".
 */
isl_size isl_map_n_basic_map(__isl_keep isl_map *map)
{ … }

isl_size isl_set_n_basic_set(__isl_keep isl_set *set)
{ … }

isl_stat isl_map_foreach_basic_map(__isl_keep isl_map *map,
	isl_stat (*fn)(__isl_take isl_basic_map *bmap, void *user), void *user)
{ … }

isl_stat isl_set_foreach_basic_set(__isl_keep isl_set *set,
	isl_stat (*fn)(__isl_take isl_basic_set *bset, void *user), void *user)
{ … }

/* Does "test" succeed on every basic set in "set"?
 */
isl_bool isl_set_every_basic_set(__isl_keep isl_set *set,
	isl_bool (*test)(__isl_keep isl_basic_set *bset, void *user),
	void *user)
{ … }

/* Return a list of basic sets, the union of which is equal to "set".
 */
__isl_give isl_basic_set_list *isl_set_get_basic_set_list(
	__isl_keep isl_set *set)
{ … }

__isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
{ … }

int isl_basic_set_size(__isl_keep isl_basic_set *bset)
{ … }

int isl_set_size(__isl_keep isl_set *set)
{ … }

/* Check if there is any lower bound (if lower == 0) and/or upper
 * bound (if upper == 0) on the specified dim.
 */
static isl_bool basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos, int lower, int upper)
{ … }

isl_bool isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos)
{ … }

isl_bool isl_basic_map_dim_has_lower_bound(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos)
{ … }

isl_bool isl_basic_map_dim_has_upper_bound(__isl_keep isl_basic_map *bmap,
	enum isl_dim_type type, unsigned pos)
{ … }

isl_bool isl_map_dim_is_bounded(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Return true if the specified dim is involved in both an upper bound
 * and a lower bound.
 */
isl_bool isl_set_dim_is_bounded(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Does "map" have a bound (according to "fn") for any of its basic maps?
 */
static isl_bool has_any_bound(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos,
	isl_bool (*fn)(__isl_keep isl_basic_map *bmap,
		  enum isl_dim_type type, unsigned pos))
{ … }

/* Return 1 if the specified dim is involved in any lower bound.
 */
isl_bool isl_set_dim_has_any_lower_bound(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Return 1 if the specified dim is involved in any upper bound.
 */
isl_bool isl_set_dim_has_any_upper_bound(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Does "map" have a bound (according to "fn") for all of its basic maps?
 */
static isl_bool has_bound(__isl_keep isl_map *map,
	enum isl_dim_type type, unsigned pos,
	isl_bool (*fn)(__isl_keep isl_basic_map *bmap,
		  enum isl_dim_type type, unsigned pos))
{ … }

/* Return 1 if the specified dim has a lower bound (in each of its basic sets).
 */
isl_bool isl_set_dim_has_lower_bound(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* Return 1 if the specified dim has an upper bound (in each of its basic sets).
 */
isl_bool isl_set_dim_has_upper_bound(__isl_keep isl_set *set,
	enum isl_dim_type type, unsigned pos)
{ … }

/* For each of the "n" variables starting at "first", determine
 * the sign of the variable and put the results in the first "n"
 * elements of the array "signs".
 * Sign
 *	1 means that the variable is non-negative
 *	-1 means that the variable is non-positive
 *	0 means the variable attains both positive and negative values.
 */
isl_stat isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
	unsigned first, unsigned n, int *signs)
{ … }

isl_stat isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
	enum isl_dim_type type, unsigned first, unsigned n, int *signs)
{ … }

/* Is it possible for the integer division "div" to depend (possibly
 * indirectly) on any output dimensions?
 *
 * If the div is undefined, then we conservatively assume that it
 * may depend on them.
 * Otherwise, we check if it actually depends on them or on any integer
 * divisions that may depend on them.
 */
static isl_bool div_may_involve_output(__isl_keep isl_basic_map *bmap, int div)
{ … }

/* Return the first integer division of "bmap" in the range
 * [first, first + n[ that may depend on any output dimensions and
 * that has a non-zero coefficient in "c" (where the first coefficient
 * in "c" corresponds to integer division "first").
 */
static int first_div_may_involve_output(__isl_keep isl_basic_map *bmap,
	isl_int *c, int first, int n)
{ … }

/* Look for a pair of inequality constraints in "bmap" of the form
 *
 *	-l + i >= 0		or		i >= l
 * and
 *	n + l - i >= 0		or		i <= l + n
 *
 * with n < "m" and i the output dimension at position "pos".
 * (Note that n >= 0 as otherwise the two constraints would conflict.)
 * Furthermore, "l" is only allowed to involve parameters, input dimensions
 * and earlier output dimensions, as well as integer divisions that do
 * not involve any of the output dimensions.
 *
 * Return the index of the first inequality constraint or bmap->n_ineq
 * if no such pair can be found.
 */
static int find_modulo_constraint_pair(__isl_keep isl_basic_map *bmap,
	int pos, isl_int m)
{ … }

/* Return the index of the equality of "bmap" that defines
 * the output dimension "pos" in terms of earlier dimensions.
 * The equality may also involve integer divisions, as long
 * as those integer divisions are defined in terms of
 * parameters or input dimensions.
 * In this case, *div is set to the number of integer divisions and
 * *ineq is set to the number of inequality constraints (provided
 * div and ineq are not NULL).
 *
 * The equality may also involve a single integer division involving
 * the output dimensions (typically only output dimension "pos") as
 * long as the coefficient of output dimension "pos" is 1 or -1 and
 * there is a pair of constraints i >= l and i <= l + n, with i referring
 * to output dimension "pos", l an expression involving only earlier
 * dimensions and n smaller than the coefficient of the integer division
 * in the equality.  In this case, the output dimension can be defined
 * in terms of a modulo expression that does not involve the integer division.
 * *div is then set to this single integer division and
 * *ineq is set to the index of constraint i >= l.
 *
 * Return bmap->n_eq if there is no such equality.
 * Return -1 on error.
 */
int isl_basic_map_output_defining_equality(__isl_keep isl_basic_map *bmap,
	int pos, int *div, int *ineq)
{ … }

/* Check if the given basic map is obviously single-valued.
 * In particular, for each output dimension, check that there is
 * an equality that defines the output dimension in terms of
 * earlier dimensions.
 */
isl_bool isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap)
{ … }

/* Check if the given basic map is single-valued.
 * We simply compute
 *
 *	M \circ M^-1
 *
 * and check if the result is a subset of the identity mapping.
 */
isl_bool isl_basic_map_is_single_valued(__isl_keep isl_basic_map *bmap)
{ … }

/* Check if the given map is obviously single-valued.
 */
isl_bool isl_map_plain_is_single_valued(__isl_keep isl_map *map)
{ … }

/* Check if the given map is single-valued.
 * We simply compute
 *
 *	M \circ M^-1
 *
 * and check if the result is a subset of the identity mapping.
 */
isl_bool isl_map_is_single_valued(__isl_keep isl_map *map)
{ … }

isl_bool isl_map_is_injective(__isl_keep isl_map *map)
{ … }

/* Check if the given map is obviously injective.
 */
isl_bool isl_map_plain_is_injective(__isl_keep isl_map *map)
{ … }

isl_bool isl_map_is_bijective(__isl_keep isl_map *map)
{ … }

isl_bool isl_set_is_singleton(__isl_keep isl_set *set)
{ … }

/* Does "map" only map elements to themselves?
 *
 * If the domain and range spaces are different, then "map"
 * is considered not to be an identity relation, even if it is empty.
 * Otherwise, construct the maximal identity relation and
 * check whether "map" is a subset of this relation.
 */
isl_bool isl_map_is_identity(__isl_keep isl_map *map)
{ … }

int isl_map_is_translation(__isl_keep isl_map *map)
{ … }

static int unique(isl_int *p, unsigned pos, unsigned len)
{ … }

isl_bool isl_basic_set_is_box(__isl_keep isl_basic_set *bset)
{ … }

isl_bool isl_set_is_box(__isl_keep isl_set *set)
{ … }

isl_bool isl_basic_set_is_wrapping(__isl_keep isl_basic_set *bset)
{ … }

isl_bool isl_set_is_wrapping(__isl_keep isl_set *set)
{ … }

/* Modify the space of "map" through a call to "change".
 * If "can_change" is set (not NULL), then first call it to check
 * if the modification is allowed, printing the error message "cannot_change"
 * if it is not.
 */
static __isl_give isl_map *isl_map_change_space(__isl_take isl_map *map,
	isl_bool (*can_change)(__isl_keep isl_map *map),
	const char *cannot_change,
	__isl_give isl_space *(*change)(__isl_take isl_space *space))
{ … }

/* Is the domain of "map" a wrapped relation?
 */
isl_bool isl_map_domain_is_wrapping(__isl_keep isl_map *map)
{ … }

/* Does "map" have a wrapped relation in both domain and range?
 */
isl_bool isl_map_is_product(__isl_keep isl_map *map)
{ … }

/* Is the range of "map" a wrapped relation?
 */
isl_bool isl_map_range_is_wrapping(__isl_keep isl_map *map)
{ … }

__isl_give isl_basic_set *isl_basic_map_wrap(__isl_take isl_basic_map *bmap)
{ … }

/* Given a map A -> B, return the set (A -> B).
 */
__isl_give isl_set *isl_map_wrap(__isl_take isl_map *map)
{ … }

__isl_give isl_basic_map *isl_basic_set_unwrap(__isl_take isl_basic_set *bset)
{ … }

/* Given a set (A -> B), return the map A -> B.
 * Error out if "set" is not of the form (A -> B).
 */
__isl_give isl_map *isl_set_unwrap(__isl_take isl_set *set)
{ … }

__isl_give isl_basic_map *isl_basic_map_reset(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type)
{ … }

__isl_give isl_map *isl_map_reset(__isl_take isl_map *map,
	enum isl_dim_type type)
{ … }

__isl_give isl_basic_map *isl_basic_map_flatten(__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_set *isl_basic_set_flatten(__isl_take isl_basic_set *bset)
{ … }

__isl_give isl_basic_map *isl_basic_map_flatten_domain(
	__isl_take isl_basic_map *bmap)
{ … }

__isl_give isl_basic_map *isl_basic_map_flatten_range(
	__isl_take isl_basic_map *bmap)
{ … }

/* Remove any internal structure from the spaces of domain and range of "map".
 */
__isl_give isl_map *isl_map_flatten(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_flatten(__isl_take isl_set *set)
{ … }

__isl_give isl_map *isl_set_flatten_map(__isl_take isl_set *set)
{ … }

/* Remove any internal structure from the space of the domain of "map".
 */
__isl_give isl_map *isl_map_flatten_domain(__isl_take isl_map *map)
{ … }

/* Remove any internal structure from the space of the range of "map".
 */
__isl_give isl_map *isl_map_flatten_range(__isl_take isl_map *map)
{ … }

/* Reorder the dimensions of "bmap" according to the given dim_map
 * and set the dimension specification to "space" and
 * perform Gaussian elimination on the result.
 */
__isl_give isl_basic_map *isl_basic_map_realign(__isl_take isl_basic_map *bmap,
	__isl_take isl_space *space, __isl_take struct isl_dim_map *dim_map)
{ … }

/* Reorder the dimensions of "map" according to given reordering.
 */
__isl_give isl_map *isl_map_realign(__isl_take isl_map *map,
	__isl_take isl_reordering *r)
{ … }

__isl_give isl_set *isl_set_realign(__isl_take isl_set *set,
	__isl_take isl_reordering *r)
{ … }

__isl_give isl_map *isl_map_align_params(__isl_take isl_map *map,
	__isl_take isl_space *model)
{ … }

__isl_give isl_set *isl_set_align_params(__isl_take isl_set *set,
	__isl_take isl_space *model)
{ … }

/* Align the parameters of "bmap" to those of "model", introducing
 * additional parameters if needed.
 */
__isl_give isl_basic_map *isl_basic_map_align_params(
	__isl_take isl_basic_map *bmap, __isl_take isl_space *model)
{ … }

/* Do "bset" and "space" have the same parameters?
 */
isl_bool isl_basic_set_space_has_equal_params(__isl_keep isl_basic_set *bset,
	__isl_keep isl_space *space)
{ … }

/* Do "map" and "space" have the same parameters?
 */
isl_bool isl_map_space_has_equal_params(__isl_keep isl_map *map,
	__isl_keep isl_space *space)
{ … }

/* Do "set" and "space" have the same parameters?
 */
isl_bool isl_set_space_has_equal_params(__isl_keep isl_set *set,
	__isl_keep isl_space *space)
{ … }

/* Align the parameters of "bset" to those of "model", introducing
 * additional parameters if needed.
 */
__isl_give isl_basic_set *isl_basic_set_align_params(
	__isl_take isl_basic_set *bset, __isl_take isl_space *model)
{ … }

/* Drop all parameters not referenced by "map".
 */
__isl_give isl_map *isl_map_drop_unused_params(__isl_take isl_map *map)
{ … }

/* Drop all parameters not referenced by "set".
 */
__isl_give isl_set *isl_set_drop_unused_params(
	__isl_take isl_set *set)
{ … }

/* Drop all parameters not referenced by "bmap".
 */
__isl_give isl_basic_map *isl_basic_map_drop_unused_params(
	__isl_take isl_basic_map *bmap)
{ … }

/* Drop all parameters not referenced by "bset".
 */
__isl_give isl_basic_set *isl_basic_set_drop_unused_params(
	__isl_take isl_basic_set *bset)
{ … }

/* Given a tuple of identifiers "tuple" in a space that corresponds
 * to that of "set", if any of those identifiers appear as parameters
 * in "set", then equate those parameters with the corresponding
 * set dimensions and project out the parameters.
 * The result therefore has no such parameters.
 */
static __isl_give isl_set *equate_params(__isl_take isl_set *set,
	__isl_keep isl_multi_id *tuple)
{ … }

/* Bind the set dimensions of "set" to parameters with identifiers
 * specified by "tuple", living in the same space as "set".
 *
 * If no parameters with these identifiers appear in "set" already,
 * then the set dimensions are simply reinterpreted as parameters.
 * Otherwise, the parameters are first equated to the corresponding
 * set dimensions.
 */
__isl_give isl_set *isl_set_bind(__isl_take isl_set *set,
	__isl_take isl_multi_id *tuple)
{ … }

/* Given a tuple of identifiers "tuple" in a space that corresponds
 * to the domain of "map", if any of those identifiers appear as parameters
 * in "map", then equate those parameters with the corresponding
 * input dimensions and project out the parameters.
 * The result therefore has no such parameters.
 */
static __isl_give isl_map *map_equate_params(__isl_take isl_map *map,
	__isl_keep isl_multi_id *tuple)
{ … }

/* Bind the input dimensions of "map" to parameters with identifiers
 * specified by "tuple", living in the domain space of "map".
 *
 * If no parameters with these identifiers appear in "map" already,
 * then the input dimensions are simply reinterpreted as parameters.
 * Otherwise, the parameters are first equated to the corresponding
 * input dimensions.
 */
__isl_give isl_set *isl_map_bind_domain(__isl_take isl_map *map,
	__isl_take isl_multi_id *tuple)
{ … }

/* Bind the output dimensions of "map" to parameters with identifiers
 * specified by "tuple", living in the range space of "map".
 *
 * Since binding is more easily implemented on the domain,
 * bind the input dimensions of the inverse of "map".
 */
__isl_give isl_set *isl_map_bind_range(__isl_take isl_map *map,
	__isl_take isl_multi_id *tuple)
{ … }

/* Insert a domain corresponding to "tuple"
 * into the nullary or unary relation "set".
 * The result has an extra initial tuple and is therefore
 * either a unary or binary relation.
 * Any parameters with identifiers in "tuple" are reinterpreted
 * as the corresponding domain dimensions.
 */
static __isl_give isl_map *unbind_params_insert_domain(
	__isl_take isl_set *set, __isl_take isl_multi_id *tuple)
{ … }

/* Construct a set with "tuple" as domain from the parameter domain "set".
 * Any parameters with identifiers in "tuple" are reinterpreted
 * as the corresponding set dimensions.
 */
__isl_give isl_set *isl_set_unbind_params(__isl_take isl_set *set,
	__isl_take isl_multi_id *tuple)
{ … }

/* Check that "set" is a proper set, i.e., that it is not a parameter domain.
 */
static isl_stat isl_set_check_is_set(__isl_keep isl_set *set)
{ … }

/* Construct a map with "domain" as domain and "set" as range.
 * Any parameters with identifiers in "domain" are reinterpreted
 * as the corresponding domain dimensions.
 */
__isl_give isl_map *isl_set_unbind_params_insert_domain(
	__isl_take isl_set *set, __isl_take isl_multi_id *domain)
{ … }

/* Construct a map with "domain" as domain and "set" as range.
 */
__isl_give isl_map *isl_set_insert_domain(__isl_take isl_set *set,
	__isl_take isl_space *domain)
{ … }

__isl_give isl_mat *isl_basic_map_equalities_matrix(
		__isl_keep isl_basic_map *bmap, enum isl_dim_type c1,
		enum isl_dim_type c2, enum isl_dim_type c3,
		enum isl_dim_type c4, enum isl_dim_type c5)
{ … }

__isl_give isl_mat *isl_basic_map_inequalities_matrix(
		__isl_keep isl_basic_map *bmap, enum isl_dim_type c1,
		enum isl_dim_type c2, enum isl_dim_type c3,
		enum isl_dim_type c4, enum isl_dim_type c5)
{ … }

__isl_give isl_basic_map *isl_basic_map_from_constraint_matrices(
	__isl_take isl_space *space,
	__isl_take isl_mat *eq, __isl_take isl_mat *ineq, enum isl_dim_type c1,
	enum isl_dim_type c2, enum isl_dim_type c3,
	enum isl_dim_type c4, enum isl_dim_type c5)
{ … }

__isl_give isl_mat *isl_basic_set_equalities_matrix(
	__isl_keep isl_basic_set *bset, enum isl_dim_type c1,
	enum isl_dim_type c2, enum isl_dim_type c3, enum isl_dim_type c4)
{ … }

__isl_give isl_mat *isl_basic_set_inequalities_matrix(
	__isl_keep isl_basic_set *bset, enum isl_dim_type c1,
	enum isl_dim_type c2, enum isl_dim_type c3, enum isl_dim_type c4)
{ … }

__isl_give isl_basic_set *isl_basic_set_from_constraint_matrices(
	__isl_take isl_space *space,
	__isl_take isl_mat *eq, __isl_take isl_mat *ineq, enum isl_dim_type c1,
	enum isl_dim_type c2, enum isl_dim_type c3, enum isl_dim_type c4)
{ … }

isl_bool isl_basic_map_can_zip(__isl_keep isl_basic_map *bmap)
{ … }

isl_bool isl_map_can_zip(__isl_keep isl_map *map)
{ … }

/* Given a basic map (A -> B) -> (C -> D), return the corresponding basic map
 * (A -> C) -> (B -> D).
 */
__isl_give isl_basic_map *isl_basic_map_zip(__isl_take isl_basic_map *bmap)
{ … }

/* Given a map (A -> B) -> (C -> D), return the corresponding map
 * (A -> C) -> (B -> D).
 */
__isl_give isl_map *isl_map_zip(__isl_take isl_map *map)
{ … }

/* Can we apply isl_basic_map_curry to "bmap"?
 * That is, does it have a nested relation in its domain?
 */
isl_bool isl_basic_map_can_curry(__isl_keep isl_basic_map *bmap)
{ … }

/* Can we apply isl_map_curry to "map"?
 * That is, does it have a nested relation in its domain?
 */
isl_bool isl_map_can_curry(__isl_keep isl_map *map)
{ … }

/* Given a basic map (A -> B) -> C, return the corresponding basic map
 * A -> (B -> C).
 */
__isl_give isl_basic_map *isl_basic_map_curry(__isl_take isl_basic_map *bmap)
{ … }

/* Given a map (A -> B) -> C, return the corresponding map
 * A -> (B -> C).
 */
__isl_give isl_map *isl_map_curry(__isl_take isl_map *map)
{ … }

/* Can isl_map_range_curry be applied to "map"?
 * That is, does it have a nested relation in its range,
 * the domain of which is itself a nested relation?
 */
isl_bool isl_map_can_range_curry(__isl_keep isl_map *map)
{ … }

/* Given a map A -> ((B -> C) -> D), return the corresponding map
 * A -> (B -> (C -> D)).
 */
__isl_give isl_map *isl_map_range_curry(__isl_take isl_map *map)
{ … }

/* Can we apply isl_basic_map_uncurry to "bmap"?
 * That is, does it have a nested relation in its domain?
 */
isl_bool isl_basic_map_can_uncurry(__isl_keep isl_basic_map *bmap)
{ … }

/* Can we apply isl_map_uncurry to "map"?
 * That is, does it have a nested relation in its domain?
 */
isl_bool isl_map_can_uncurry(__isl_keep isl_map *map)
{ … }

/* Given a basic map A -> (B -> C), return the corresponding basic map
 * (A -> B) -> C.
 */
__isl_give isl_basic_map *isl_basic_map_uncurry(__isl_take isl_basic_map *bmap)
{ … }

/* Given a map A -> (B -> C), return the corresponding map
 * (A -> B) -> C.
 */
__isl_give isl_map *isl_map_uncurry(__isl_take isl_map *map)
{ … }

__isl_give isl_set *isl_set_equate(__isl_take isl_set *set,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Construct a basic map where the given dimensions are equal to each other.
 */
static __isl_give isl_basic_map *equator(__isl_take isl_space *space,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the given two dimensions are equal.
 */
__isl_give isl_basic_map *isl_basic_map_equate(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the given two dimensions are equal.
 */
__isl_give isl_map *isl_map_equate(__isl_take isl_map *map,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the given two dimensions have opposite values.
 */
__isl_give isl_map *isl_map_oppose(__isl_take isl_map *map,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Construct a constraint imposing that the value of the first dimension is
 * greater than or equal to that of the second.
 */
static __isl_give isl_constraint *constraint_order_ge(
	__isl_take isl_space *space, enum isl_dim_type type1, int pos1,
	enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the value of the first dimension is
 * greater than or equal to that of the second.
 */
__isl_give isl_basic_map *isl_basic_map_order_ge(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the value of the first dimension is
 * greater than or equal to that of the second.
 */
__isl_give isl_map *isl_map_order_ge(__isl_take isl_map *map,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the value of the first dimension is
 * less than or equal to that of the second.
 */
__isl_give isl_map *isl_map_order_le(__isl_take isl_map *map,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Construct a basic map where the value of the first dimension is
 * greater than that of the second.
 */
static __isl_give isl_basic_map *greator(__isl_take isl_space *space,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the value of the first dimension is
 * greater than that of the second.
 */
__isl_give isl_basic_map *isl_basic_map_order_gt(__isl_take isl_basic_map *bmap,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the value of the first dimension is
 * greater than that of the second.
 */
__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

/* Add a constraint imposing that the value of the first dimension is
 * smaller than that of the second.
 */
__isl_give isl_map *isl_map_order_lt(__isl_take isl_map *map,
	enum isl_dim_type type1, int pos1, enum isl_dim_type type2, int pos2)
{ … }

__isl_give isl_aff *isl_basic_map_get_div(__isl_keep isl_basic_map *bmap,
	int pos)
{ … }

__isl_give isl_aff *isl_basic_set_get_div(__isl_keep isl_basic_set *bset,
	int pos)
{ … }

/* Plug in "subs" for set dimension "pos" of "set".
 */
__isl_give isl_set *isl_set_substitute(__isl_take isl_set *set,
	unsigned pos, __isl_keep isl_aff *subs)
{ … }

/* Check if the range of "ma" is compatible with the domain or range
 * (depending on "type") of "bmap".
 */
static isl_stat check_basic_map_compatible_range_multi_aff(
	__isl_keep isl_basic_map *bmap, enum isl_dim_type type,
	__isl_keep isl_multi_aff *ma)
{ … }

/* Copy the divs from "ma" to "bmap", adding zeros for the "n_before"
 * coefficients before the transformed range of dimensions,
 * the "n_after" coefficients after the transformed range of dimensions
 * and the coefficients of the other divs in "bmap".
 */
static __isl_give isl_basic_map *set_ma_divs(__isl_take isl_basic_map *bmap,
	__isl_keep isl_multi_aff *ma, int n_before, int n_after, int n_div)
{ … }

/* How many stride constraints does "ma" enforce?
 * That is, how many of the affine expressions have a denominator
 * different from one?
 */
static int multi_aff_strides(__isl_keep isl_multi_aff *ma)
{ … }

/* For each affine expression in ma of the form
 *
 *	x_i = (f_i y + h_i)/m_i
 *
 * with m_i different from one, add a constraint to "bmap"
 * of the form
 *
 *	f_i y + h_i = m_i alpha_i
 *
 * with alpha_i an additional existentially quantified variable.
 *
 * The input variables of "ma" correspond to a subset of the variables
 * of "bmap".  There are "n_before" variables in "bmap" before this
 * subset and "n_after" variables after this subset.
 * The integer divisions of the affine expressions in "ma" are assumed
 * to have been aligned.  There are "n_div_ma" of them and
 * they appear first in "bmap", straight after the "n_after" variables.
 */
static __isl_give isl_basic_map *add_ma_strides(
	__isl_take isl_basic_map *bmap, __isl_keep isl_multi_aff *ma,
	int n_before, int n_after, int n_div_ma)
{ … }

/* Replace the domain or range space (depending on "type) of "space" by "set".
 */
static __isl_give isl_space *isl_space_set(__isl_take isl_space *space,
	enum isl_dim_type type, __isl_take isl_space *set)
{ … }

/* Compute the preimage of the domain or range (depending on "type")
 * of "bmap" under the function represented by "ma".
 * In other words, plug in "ma" in the domain or range of "bmap".
 * The result is a basic map that lives in the same space as "bmap"
 * except that the domain or range has been replaced by
 * the domain space of "ma".
 *
 * If bmap is represented by
 *
 *	A(p) + S u + B x + T v + C(divs) >= 0,
 *
 * where u and x are input and output dimensions if type == isl_dim_out
 * while x and v are input and output dimensions if type == isl_dim_in,
 * and ma is represented by
 *
 *	x = D(p) + F(y) + G(divs')
 *
 * then the result is
 *
 *	A(p) + B D(p) + S u + B F(y) + T v + B G(divs') + C(divs) >= 0
 *
 * The divs in the input set are similarly adjusted.
 * In particular
 *
 *	floor((a_i(p) + s u + b_i x + t v + c_i(divs))/n_i)
 *
 * becomes
 *
 *	floor((a_i(p) + b_i D(p) + s u + b_i F(y) + t v +
 *		B_i G(divs') + c_i(divs))/n_i)
 *
 * If bmap is not a rational map and if F(y) involves any denominators
 *
 *	x_i = (f_i y + h_i)/m_i
 *
 * then additional constraints are added to ensure that we only
 * map back integer points.  That is we enforce
 *
 *	f_i y + h_i = m_i alpha_i
 *
 * with alpha_i an additional existentially quantified variable.
 *
 * We first copy over the divs from "ma".
 * Then we add the modified constraints and divs from "bmap".
 * Finally, we add the stride constraints, if needed.
 */
__isl_give isl_basic_map *isl_basic_map_preimage_multi_aff(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type,
	__isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of "bset" under the function represented by "ma".
 * In other words, plug in "ma" in "bset".  The result is a basic set
 * that lives in the domain space of "ma".
 */
__isl_give isl_basic_set *isl_basic_set_preimage_multi_aff(
	__isl_take isl_basic_set *bset, __isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of the domain of "bmap" under the function
 * represented by "ma".
 * In other words, plug in "ma" in the domain of "bmap".
 * The result is a basic map that lives in the same space as "bmap"
 * except that the domain has been replaced by the domain space of "ma".
 */
__isl_give isl_basic_map *isl_basic_map_preimage_domain_multi_aff(
	__isl_take isl_basic_map *bmap, __isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of the range of "bmap" under the function
 * represented by "ma".
 * In other words, plug in "ma" in the range of "bmap".
 * The result is a basic map that lives in the same space as "bmap"
 * except that the range has been replaced by the domain space of "ma".
 */
__isl_give isl_basic_map *isl_basic_map_preimage_range_multi_aff(
	__isl_take isl_basic_map *bmap, __isl_take isl_multi_aff *ma)
{ … }

/* Check if the range of "ma" is compatible with the domain or range
 * (depending on "type") of "map".
 * Return isl_stat_error if anything is wrong.
 */
static isl_stat check_map_compatible_range_multi_aff(
	__isl_keep isl_map *map, enum isl_dim_type type,
	__isl_keep isl_multi_aff *ma)
{ … }

/* Compute the preimage of the domain or range (depending on "type")
 * of "map" under the function represented by "ma".
 * In other words, plug in "ma" in the domain or range of "map".
 * The result is a map that lives in the same space as "map"
 * except that the domain or range has been replaced by
 * the domain space of "ma".
 *
 * The parameters are assumed to have been aligned.
 */
static __isl_give isl_map *map_preimage_multi_aff(__isl_take isl_map *map,
	enum isl_dim_type type, __isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of the domain or range (depending on "type")
 * of "map" under the function represented by "ma".
 * In other words, plug in "ma" in the domain or range of "map".
 * The result is a map that lives in the same space as "map"
 * except that the domain or range has been replaced by
 * the domain space of "ma".
 */
__isl_give isl_map *isl_map_preimage_multi_aff(__isl_take isl_map *map,
	enum isl_dim_type type, __isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of "set" under the function represented by "ma".
 * In other words, plug in "ma" in "set".  The result is a set
 * that lives in the domain space of "ma".
 */
__isl_give isl_set *isl_set_preimage_multi_aff(__isl_take isl_set *set,
	__isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of the domain of "map" under the function
 * represented by "ma".
 * In other words, plug in "ma" in the domain of "map".
 * The result is a map that lives in the same space as "map"
 * except that the domain has been replaced by the domain space of "ma".
 */
__isl_give isl_map *isl_map_preimage_domain_multi_aff(__isl_take isl_map *map,
	__isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of the range of "map" under the function
 * represented by "ma".
 * In other words, plug in "ma" in the range of "map".
 * The result is a map that lives in the same space as "map"
 * except that the range has been replaced by the domain space of "ma".
 */
__isl_give isl_map *isl_map_preimage_range_multi_aff(__isl_take isl_map *map,
	__isl_take isl_multi_aff *ma)
{ … }

/* Compute the preimage of "map" under the function represented by "pma".
 * In other words, plug in "pma" in the domain or range of "map".
 * The result is a map that lives in the same space as "map",
 * except that the space of type "type" has been replaced by
 * the domain space of "pma".
 *
 * The parameters of "map" and "pma" are assumed to have been aligned.
 */
static __isl_give isl_map *isl_map_preimage_pw_multi_aff_aligned(
	__isl_take isl_map *map, enum isl_dim_type type,
	__isl_take isl_pw_multi_aff *pma)
{ … }

/* Compute the preimage of "map" under the function represented by "pma".
 * In other words, plug in "pma" in the domain or range of "map".
 * The result is a map that lives in the same space as "map",
 * except that the space of type "type" has been replaced by
 * the domain space of "pma".
 */
__isl_give isl_map *isl_map_preimage_pw_multi_aff(__isl_take isl_map *map,
	enum isl_dim_type type, __isl_take isl_pw_multi_aff *pma)
{ … }

/* Compute the preimage of "set" under the function represented by "pma".
 * In other words, plug in "pma" in "set".  The result is a set
 * that lives in the domain space of "pma".
 */
__isl_give isl_set *isl_set_preimage_pw_multi_aff(__isl_take isl_set *set,
	__isl_take isl_pw_multi_aff *pma)
{ … }

/* Compute the preimage of the domain of "map" under the function
 * represented by "pma".
 * In other words, plug in "pma" in the domain of "map".
 * The result is a map that lives in the same space as "map",
 * except that domain space has been replaced by the domain space of "pma".
 */
__isl_give isl_map *isl_map_preimage_domain_pw_multi_aff(
	__isl_take isl_map *map, __isl_take isl_pw_multi_aff *pma)
{ … }

/* Compute the preimage of the range of "map" under the function
 * represented by "pma".
 * In other words, plug in "pma" in the range of "map".
 * The result is a map that lives in the same space as "map",
 * except that range space has been replaced by the domain space of "pma".
 */
__isl_give isl_map *isl_map_preimage_range_pw_multi_aff(
	__isl_take isl_map *map, __isl_take isl_pw_multi_aff *pma)
{ … }

/* Compute the preimage of "map" under the function represented by "mpa".
 * In other words, plug in "mpa" in the domain or range of "map".
 * The result is a map that lives in the same space as "map",
 * except that the space of type "type" has been replaced by
 * the domain space of "mpa".
 *
 * If the map does not involve any constraints that refer to the
 * dimensions of the substituted space, then the only possible
 * effect of "mpa" on the map is to map the space to a different space.
 * We create a separate isl_multi_aff to effectuate this change
 * in order to avoid spurious splitting of the map along the pieces
 * of "mpa".
 * If "mpa" has a non-trivial explicit domain, however,
 * then the full substitution should be performed.
 */
__isl_give isl_map *isl_map_preimage_multi_pw_aff(__isl_take isl_map *map,
	enum isl_dim_type type, __isl_take isl_multi_pw_aff *mpa)
{ … }

/* Compute the preimage of "map" under the function represented by "mpa".
 * In other words, plug in "mpa" in the domain "map".
 * The result is a map that lives in the same space as "map",
 * except that domain space has been replaced by the domain space of "mpa".
 */
__isl_give isl_map *isl_map_preimage_domain_multi_pw_aff(
	__isl_take isl_map *map, __isl_take isl_multi_pw_aff *mpa)
{ … }

/* Compute the preimage of "set" by the function represented by "mpa".
 * In other words, plug in "mpa" in "set".
 */
__isl_give isl_set *isl_set_preimage_multi_pw_aff(__isl_take isl_set *set,
	__isl_take isl_multi_pw_aff *mpa)
{ … }

/* Return a copy of the equality constraints of "bset" as a matrix.
 */
__isl_give isl_mat *isl_basic_set_extract_equalities(
	__isl_keep isl_basic_set *bset)
{ … }

/* Are the "n" "coefficients" starting at "first" of the integer division
 * expressions at position "pos1" in "bmap1" and "pos2" in "bmap2" equal
 * to each other?
 * The "coefficient" at position 0 is the denominator.
 * The "coefficient" at position 1 is the constant term.
 */
isl_bool isl_basic_map_equal_div_expr_part(__isl_keep isl_basic_map *bmap1,
	int pos1, __isl_keep isl_basic_map *bmap2, int pos2,
	unsigned first, unsigned n)
{ … }

/* Are the integer division expressions at position "pos1" in "bmap1" and
 * "pos2" in "bmap2" equal to each other, except that the constant terms
 * are different?
 */
isl_bool isl_basic_map_equal_div_expr_except_constant(
	__isl_keep isl_basic_map *bmap1, int pos1,
	__isl_keep isl_basic_map *bmap2, int pos2)
{ … }

/* Replace the numerator of the constant term of the integer division
 * expression at position "div" in "bmap" by "value".
 * The caller guarantees that this does not change the meaning
 * of the input.
 */
__isl_give isl_basic_map *isl_basic_map_set_div_expr_constant_num_si_inplace(
	__isl_take isl_basic_map *bmap, int div, int value)
{ … }

/* Is the point "inner" internal to inequality constraint "ineq"
 * of "bset"?
 * The point is considered to be internal to the inequality constraint,
 * if it strictly lies on the positive side of the inequality constraint,
 * or if it lies on the constraint and the constraint is lexico-positive.
 */
static isl_bool is_internal(__isl_keep isl_vec *inner,
	__isl_keep isl_basic_set *bset, int ineq)
{ … }

/* Tighten the inequality constraints of "bset" that are outward with respect
 * to the point "vec".
 * That is, tighten the constraints that are not satisfied by "vec".
 *
 * "vec" is a point internal to some superset S of "bset" that is used
 * to make the subsets of S disjoint, by tightening one half of the constraints
 * that separate two subsets.  In particular, the constraints of S
 * are all satisfied by "vec" and should not be tightened.
 * Of the internal constraints, those that have "vec" on the outside
 * are tightened.  The shared facet is included in the adjacent subset
 * with the opposite constraint.
 * For constraints that saturate "vec", this criterion cannot be used
 * to determine which of the two sides should be tightened.
 * Instead, the sign of the first non-zero coefficient is used
 * to make this choice.  Note that this second criterion is never used
 * on the constraints of S since "vec" is interior to "S".
 */
__isl_give isl_basic_set *isl_basic_set_tighten_outward(
	__isl_take isl_basic_set *bset, __isl_keep isl_vec *vec)
{ … }

/* Replace the variables x of type "type" starting at "first" in "bmap"
 * by x' with x = M x' with M the matrix trans.
 * That is, replace the corresponding coefficients c by c M.
 *
 * The transformation matrix should be a square matrix.
 */
__isl_give isl_basic_map *isl_basic_map_transform_dims(
	__isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned first,
	__isl_take isl_mat *trans)
{ … }

/* Replace the variables x of type "type" starting at "first" in "bset"
 * by x' with x = M x' with M the matrix trans.
 * That is, replace the corresponding coefficients c by c M.
 *
 * The transformation matrix should be a square matrix.
 */
__isl_give isl_basic_set *isl_basic_set_transform_dims(
	__isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned first,
	__isl_take isl_mat *trans)
{ … }