blob: 8b4aea37b130807d4595ea9f5f7b7d3302ca8f8a [file] [log] [blame]
/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
* Copyright 2010 INRIA Saclay
*
* Use of this software is governed by the GNU LGPLv2.1 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
*/
#include <string.h>
#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include <isl/blk.h>
#include "isl_space_private.h"
#include "isl_equalities.h"
#include <isl_list_private.h>
#include <isl/lp.h>
#include <isl/seq.h>
#include <isl/set.h>
#include <isl/map.h>
#include "isl_map_piplib.h"
#include <isl_reordering.h>
#include "isl_sample.h"
#include "isl_tab.h"
#include <isl/vec.h>
#include <isl_mat_private.h>
#include <isl_dim_map.h>
#include <isl_local_space_private.h>
#include <isl_aff_private.h>
#include <isl_options_private.h>
static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
{
switch (type) {
case isl_dim_param: return dim->nparam;
case isl_dim_in: return dim->n_in;
case isl_dim_out: return dim->n_out;
case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out;
default: return 0;
}
}
static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
{
switch (type) {
case isl_dim_param: return 1;
case isl_dim_in: return 1 + dim->nparam;
case isl_dim_out: return 1 + dim->nparam + dim->n_in;
default: return 0;
}
}
unsigned isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
enum isl_dim_type type)
{
if (!bmap)
return 0;
switch (type) {
case isl_dim_cst: return 1;
case isl_dim_param:
case isl_dim_in:
case isl_dim_out: return isl_space_dim(bmap->dim, type);
case isl_dim_div: return bmap->n_div;
case isl_dim_all: return isl_basic_map_total_dim(bmap);
default: return 0;
}
}
unsigned isl_map_dim(__isl_keep isl_map *map, enum isl_dim_type type)
{
return map ? n(map->dim, type) : 0;
}
unsigned isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
{
return set ? n(set->dim, type) : 0;
}
unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
enum isl_dim_type type)
{
isl_space *dim = bmap->dim;
switch (type) {
case isl_dim_cst: return 0;
case isl_dim_param: return 1;
case isl_dim_in: return 1 + dim->nparam;
case isl_dim_out: return 1 + dim->nparam + dim->n_in;
case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
default: return 0;
}
}
unsigned isl_basic_set_offset(struct isl_basic_set *bset,
enum isl_dim_type type)
{
return isl_basic_map_offset(bset, type);
}
static unsigned map_offset(struct isl_map *map, enum isl_dim_type type)
{
return pos(map->dim, type);
}
unsigned isl_basic_set_dim(__isl_keep isl_basic_set *bset,
enum isl_dim_type type)
{
return isl_basic_map_dim(bset, type);
}
unsigned isl_basic_set_n_dim(__isl_keep isl_basic_set *bset)
{
return isl_basic_set_dim(bset, isl_dim_set);
}
unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
{
return isl_basic_set_dim(bset, isl_dim_param);
}
unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
{
return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div;
}
unsigned isl_set_n_dim(__isl_keep isl_set *set)
{
return isl_set_dim(set, isl_dim_set);
}
unsigned isl_set_n_param(__isl_keep isl_set *set)
{
return isl_set_dim(set, isl_dim_param);
}
unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
{
return bmap ? bmap->dim->n_in : 0;
}
unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
{
return bmap ? bmap->dim->n_out : 0;
}
unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
{
return bmap ? bmap->dim->nparam : 0;
}
unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
{
return bmap ? bmap->n_div : 0;
}
unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
{
return bmap ? isl_space_dim(bmap->dim, isl_dim_all) + bmap->n_div : 0;
}
unsigned isl_map_n_in(const struct isl_map *map)
{
return map ? map->dim->n_in : 0;
}
unsigned isl_map_n_out(const struct isl_map *map)
{
return map ? map->dim->n_out : 0;
}
unsigned isl_map_n_param(const struct isl_map *map)
{
return map ? map->dim->nparam : 0;
}
int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
{
int m;
if (!map || !set)
return -1;
m = isl_space_match(map->dim, isl_dim_param, set->dim, isl_dim_param);
if (m < 0 || !m)
return m;
return isl_space_tuple_match(map->dim, isl_dim_in, set->dim, isl_dim_set);
}
int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
struct isl_basic_set *bset)
{
int m;
if (!bmap || !bset)
return -1;
m = isl_space_match(bmap->dim, isl_dim_param, bset->dim, isl_dim_param);
if (m < 0 || !m)
return m;
return isl_space_tuple_match(bmap->dim, isl_dim_in, bset->dim, isl_dim_set);
}
int isl_map_compatible_range(__isl_keep isl_map *map, __isl_keep isl_set *set)
{
int m;
if (!map || !set)
return -1;
m = isl_space_match(map->dim, isl_dim_param, set->dim, isl_dim_param);
if (m < 0 || !m)
return m;
return isl_space_tuple_match(map->dim, isl_dim_out, set->dim, isl_dim_set);
}
int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
struct isl_basic_set *bset)
{
int m;
if (!bmap || !bset)
return -1;
m = isl_space_match(bmap->dim, isl_dim_param, bset->dim, isl_dim_param);
if (m < 0 || !m)
return m;
return isl_space_tuple_match(bmap->dim, isl_dim_out, bset->dim, isl_dim_set);
}
isl_ctx *isl_basic_map_get_ctx(__isl_keep isl_basic_map *bmap)
{
return bmap ? bmap->ctx : NULL;
}
isl_ctx *isl_basic_set_get_ctx(__isl_keep isl_basic_set *bset)
{
return bset ? bset->ctx : NULL;
}
isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
{
return map ? map->ctx : NULL;
}
isl_ctx *isl_set_get_ctx(__isl_keep isl_set *set)
{
return set ? set->ctx : NULL;
}
__isl_give isl_space *isl_basic_map_get_space(__isl_keep isl_basic_map *bmap)
{
if (!bmap)
return NULL;
return isl_space_copy(bmap->dim);
}
__isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
{
if (!bset)
return NULL;
return isl_space_copy(bset->dim);
}
__isl_give isl_local_space *isl_basic_map_get_local_space(
__isl_keep isl_basic_map *bmap)
{
int i;
isl_local_space *ls;
unsigned total;
if (!bmap)
return NULL;
total = isl_basic_map_total_dim(bmap);
ls = isl_local_space_alloc(isl_space_copy(bmap->dim), bmap->n_div);
if (!ls)
return NULL;
for (i = 0; i < bmap->n_div; ++i)
isl_seq_cpy(ls->div->row[i], bmap->div[i], 2 + total);
return ls;
}
__isl_give isl_local_space *isl_basic_set_get_local_space(
__isl_keep isl_basic_set *bset)
{
return isl_basic_map_get_local_space(bset);
}
__isl_give isl_basic_map *isl_basic_map_from_local_space(
__isl_take isl_local_space *ls)
{
int i;
int n_div;
isl_basic_map *bmap;
if (!ls)
return NULL;
n_div = isl_local_space_dim(ls, isl_dim_div);
bmap = isl_basic_map_alloc_space(isl_local_space_get_space(ls),
n_div, 0, 2 * n_div);
for (i = 0; i < n_div; ++i)
if (isl_basic_map_alloc_div(bmap) < 0)
goto error;
for (i = 0; i < n_div; ++i) {
isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col);
if (isl_basic_map_add_div_constraints(bmap, i) < 0)
goto error;
}
isl_local_space_free(ls);
return bmap;
error:
isl_local_space_free(ls);
isl_basic_map_free(bmap);
return NULL;
}
__isl_give isl_basic_set *isl_basic_set_from_local_space(
__isl_take isl_local_space *ls)
{
return isl_basic_map_from_local_space(ls);
}
__isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map)
{
if (!map)
return NULL;
return isl_space_copy(map->dim);
}
__isl_give isl_space *isl_set_get_space(__isl_keep isl_set *set)
{
if (!set)
return NULL;
return isl_space_copy(set->dim);
}
__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)
{
bmap = isl_basic_map_cow(bmap);
if (!bmap)
return NULL;
bmap->dim = isl_space_set_tuple_name(bmap->dim, type, s);
if (!bmap->dim)
goto error;
bmap = isl_basic_map_finalize(bmap);
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
__isl_give isl_basic_set *isl_basic_set_set_tuple_name(
__isl_take isl_basic_set *bset, const char *s)
{
return isl_basic_map_set_tuple_name(bset, isl_dim_set, s);
}
const char *isl_basic_map_get_tuple_name(__isl_keep isl_basic_map *bmap,
enum isl_dim_type type)
{
return bmap ? isl_space_get_tuple_name(bmap->dim, type) : NULL;
}
__isl_give isl_map *isl_map_set_tuple_name(__isl_take isl_map *map,
enum isl_dim_type type, const char *s)
{
int i;
map = isl_map_cow(map);
if (!map)
return NULL;
map->dim = isl_space_set_tuple_name(map->dim, type, s);
if (!map->dim)
goto error;
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_set_tuple_name(map->p[i], type, s);
if (!map->p[i])
goto error;
}
return map;
error:
isl_map_free(map);
return NULL;
}
const char *isl_map_get_tuple_name(__isl_keep isl_map *map,
enum isl_dim_type type)
{
return map ? isl_space_get_tuple_name(map->dim, type) : NULL;
}
__isl_give isl_set *isl_set_set_tuple_name(__isl_take isl_set *set,
const char *s)
{
return (isl_set *)isl_map_set_tuple_name((isl_map *)set, isl_dim_set, 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)
{
map = isl_map_cow(map);
if (!map)
return isl_id_free(id);
map->dim = isl_space_set_tuple_id(map->dim, type, id);
return isl_map_reset_space(map, isl_space_copy(map->dim));
}
__isl_give isl_set *isl_set_set_tuple_id(__isl_take isl_set *set,
__isl_take isl_id *id)
{
return isl_map_set_tuple_id(set, isl_dim_set, id);
}
__isl_give isl_map *isl_map_reset_tuple_id(__isl_take isl_map *map,
enum isl_dim_type type)
{
map = isl_map_cow(map);
if (!map)
return NULL;
map->dim = isl_space_reset_tuple_id(map->dim, type);
return isl_map_reset_space(map, isl_space_copy(map->dim));
}
__isl_give isl_set *isl_set_reset_tuple_id(__isl_take isl_set *set)
{
return isl_map_reset_tuple_id(set, isl_dim_set);
}
int isl_map_has_tuple_id(__isl_keep isl_map *map, enum isl_dim_type type)
{
return map ? isl_space_has_tuple_id(map->dim, type) : -1;
}
__isl_give isl_id *isl_map_get_tuple_id(__isl_keep isl_map *map,
enum isl_dim_type type)
{
return map ? isl_space_get_tuple_id(map->dim, type) : NULL;
}
int isl_set_has_tuple_id(__isl_keep isl_set *set)
{
return isl_map_has_tuple_id(set, isl_dim_set);
}
__isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set)
{
return isl_map_get_tuple_id(set, isl_dim_set);
}
const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset)
{
return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL;
}
const char *isl_set_get_tuple_name(__isl_keep isl_set *set)
{
return set ? isl_space_get_tuple_name(set->dim, isl_dim_set) : NULL;
}
const char *isl_basic_map_get_dim_name(__isl_keep isl_basic_map *bmap,
enum isl_dim_type type, unsigned pos)
{
return bmap ? isl_space_get_dim_name(bmap->dim, type, pos) : NULL;
}
const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset,
enum isl_dim_type type, unsigned pos)
{
return bset ? isl_space_get_dim_name(bset->dim, type, pos) : NULL;
}
const char *isl_map_get_dim_name(__isl_keep isl_map *map,
enum isl_dim_type type, unsigned pos)
{
return map ? isl_space_get_dim_name(map->dim, type, pos) : NULL;
}
const char *isl_set_get_dim_name(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned pos)
{
return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL;
}
__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)
{
bmap = isl_basic_map_cow(bmap);
if (!bmap)
return NULL;
bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s);
if (!bmap->dim)
goto error;
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
__isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map,
enum isl_dim_type type, unsigned pos, const char *s)
{
int i;
map = isl_map_cow(map);
if (!map)
return NULL;
map->dim = isl_space_set_dim_name(map->dim, type, pos, s);
if (!map->dim)
goto error;
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_set_dim_name(map->p[i], type, pos, s);
if (!map->p[i])
goto error;
}
return map;
error:
isl_map_free(map);
return NULL;
}
__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)
{
return (isl_basic_set *)isl_basic_map_set_dim_name(
(isl_basic_map *)bset, type, pos, 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)
{
return (isl_set *)isl_map_set_dim_name((isl_map *)set, type, pos, s);
}
int isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap,
enum isl_dim_type type, unsigned pos)
{
return bmap ? isl_space_has_dim_id(bmap->dim, type, pos) : -1;
}
int isl_map_has_dim_id(__isl_keep isl_map *map,
enum isl_dim_type type, unsigned pos)
{
return map ? isl_space_has_dim_id(map->dim, type, pos) : -1;
}
__isl_give isl_id *isl_map_get_dim_id(__isl_keep isl_map *map,
enum isl_dim_type type, unsigned pos)
{
return map ? isl_space_get_dim_id(map->dim, type, pos) : NULL;
}
int isl_set_has_dim_id(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned pos)
{
return isl_map_has_dim_id(set, type, pos);
}
__isl_give isl_id *isl_set_get_dim_id(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned pos)
{
return isl_map_get_dim_id(set, type, 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)
{
map = isl_map_cow(map);
if (!map)
return isl_id_free(id);
map->dim = isl_space_set_dim_id(map->dim, type, pos, id);
return isl_map_reset_space(map, isl_space_copy(map->dim));
}
__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)
{
return isl_map_set_dim_id(set, type, pos, id);
}
int isl_map_find_dim_by_id(__isl_keep isl_map *map, enum isl_dim_type type,
__isl_keep isl_id *id)
{
if (!map)
return -1;
return isl_space_find_dim_by_id(map->dim, type, id);
}
int isl_set_find_dim_by_id(__isl_keep isl_set *set, enum isl_dim_type type,
__isl_keep isl_id *id)
{
return isl_map_find_dim_by_id(set, type, id);
}
int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type,
const char *name)
{
if (!map)
return -1;
return isl_space_find_dim_by_name(map->dim, type, name);
}
int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type,
const char *name)
{
return isl_map_find_dim_by_name(set, type, name);
}
int isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
{
if (!bmap)
return -1;
return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
}
int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
{
return isl_basic_map_is_rational(bset);
}
/* Is this basic set a parameter domain?
*/
int isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
{
if (!bset)
return -1;
return isl_space_is_params(bset->dim);
}
/* Is this set a parameter domain?
*/
int isl_set_is_params(__isl_keep isl_set *set)
{
if (!set)
return -1;
return isl_space_is_params(set->dim);
}
/* Is this map actually a parameter domain?
* Users should never call this function. Outside of isl,
* a map can never be a parameter domain.
*/
int isl_map_is_params(__isl_keep isl_map *map)
{
if (!map)
return -1;
return isl_space_is_params(map->dim);
}
static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
struct isl_basic_map *bmap, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
int i;
size_t row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + extra;
bmap->ctx = ctx;
isl_ctx_ref(ctx);
bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
if (isl_blk_is_error(bmap->block))
goto error;
bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
if (!bmap->ineq)
goto error;
if (extra == 0) {
bmap->block2 = isl_blk_empty();
bmap->div = NULL;
} else {
bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
if (isl_blk_is_error(bmap->block2))
goto error;
bmap->div = isl_alloc_array(ctx, isl_int *, extra);
if (!bmap->div)
goto error;
}
for (i = 0; i < n_ineq + n_eq; ++i)
bmap->ineq[i] = bmap->block.data + i * row_size;
for (i = 0; i < extra; ++i)
bmap->div[i] = bmap->block2.data + i * (1 + row_size);
bmap->ref = 1;
bmap->flags = 0;
bmap->c_size = n_eq + n_ineq;
bmap->eq = bmap->ineq + n_ineq;
bmap->extra = extra;
bmap->n_eq = 0;
bmap->n_ineq = 0;
bmap->n_div = 0;
bmap->sample = NULL;
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
unsigned nparam, unsigned dim, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
struct isl_basic_map *bmap;
isl_space *space;
space = isl_space_set_alloc(ctx, nparam, dim);
if (!space)
return NULL;
bmap = isl_basic_map_alloc_space(space, extra, n_eq, n_ineq);
return (struct isl_basic_set *)bmap;
}
struct isl_basic_set *isl_basic_set_alloc_space(__isl_take isl_space *dim,
unsigned extra, unsigned n_eq, unsigned n_ineq)
{
struct isl_basic_map *bmap;
if (!dim)
return NULL;
isl_assert(dim->ctx, dim->n_in == 0, goto error);
bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
return (struct isl_basic_set *)bmap;
error:
isl_space_free(dim);
return NULL;
}
struct isl_basic_map *isl_basic_map_alloc_space(__isl_take isl_space *dim,
unsigned extra, unsigned n_eq, unsigned n_ineq)
{
struct isl_basic_map *bmap;
if (!dim)
return NULL;
bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
if (!bmap)
goto error;
bmap->dim = dim;
return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
error:
isl_space_free(dim);
return NULL;
}
struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
unsigned nparam, unsigned in, unsigned out, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
struct isl_basic_map *bmap;
isl_space *dim;
dim = isl_space_alloc(ctx, nparam, in, out);
if (!dim)
return NULL;
bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
return bmap;
}
static void dup_constraints(
struct isl_basic_map *dst, struct isl_basic_map *src)
{
int i;
unsigned total = isl_basic_map_total_dim(src);
for (i = 0; i < src->n_eq; ++i) {
int j = isl_basic_map_alloc_equality(dst);
isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
}
for (i = 0; i < src->n_ineq; ++i) {
int j = isl_basic_map_alloc_inequality(dst);
isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
}
for (i = 0; i < src->n_div; ++i) {
int j = isl_basic_map_alloc_div(dst);
isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
}
ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
}
struct isl_basic_map *isl_basic_map_dup(struct isl_basic_map *bmap)
{
struct isl_basic_map *dup;
if (!bmap)
return NULL;
dup = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
bmap->n_div, bmap->n_eq, bmap->n_ineq);
if (!dup)
return NULL;
dup_constraints(dup, bmap);
dup->flags = bmap->flags;
dup->sample = isl_vec_copy(bmap->sample);
return dup;
}
struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
{
struct isl_basic_map *dup;
dup = isl_basic_map_dup((struct isl_basic_map *)bset);
return (struct isl_basic_set *)dup;
}
struct isl_basic_set *isl_basic_set_copy(struct isl_basic_set *bset)
{
if (!bset)
return NULL;
if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
bset->ref++;
return bset;
}
return isl_basic_set_dup(bset);
}
struct isl_set *isl_set_copy(struct isl_set *set)
{
if (!set)
return NULL;
set->ref++;
return set;
}
struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
{
if (!bmap)
return NULL;
if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
bmap->ref++;
return bmap;
}
bmap = isl_basic_map_dup(bmap);
if (bmap)
ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
return bmap;
}
struct isl_map *isl_map_copy(struct isl_map *map)
{
if (!map)
return NULL;
map->ref++;
return map;
}
void isl_basic_map_free(struct isl_basic_map *bmap)
{
if (!bmap)
return;
if (--bmap->ref > 0)
return;
isl_ctx_deref(bmap->ctx);
free(bmap->div);
isl_blk_free(bmap->ctx, bmap->block2);
free(bmap->ineq);
isl_blk_free(bmap->ctx, bmap->block);
isl_vec_free(bmap->sample);
isl_space_free(bmap->dim);
free(bmap);
}
void isl_basic_set_free(struct isl_basic_set *bset)
{
isl_basic_map_free((struct isl_basic_map *)bset);
}
static int room_for_con(struct isl_basic_map *bmap, unsigned n)
{
return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
}
__isl_give isl_map *isl_map_align_params_map_map_and(
__isl_take isl_map *map1, __isl_take isl_map *map2,
__isl_give isl_map *(*fn)(__isl_take isl_map *map1,
__isl_take isl_map *map2))
{
if (!map1 || !map2)
goto error;
if (isl_space_match(map1->dim, isl_dim_param, map2->dim, isl_dim_param))
return fn(map1, map2);
if (!isl_space_has_named_params(map1->dim) ||
!isl_space_has_named_params(map2->dim))
isl_die(map1->ctx, isl_error_invalid,
"unaligned unnamed parameters", goto error);
map1 = isl_map_align_params(map1, isl_map_get_space(map2));
map2 = isl_map_align_params(map2, isl_map_get_space(map1));
return fn(map1, map2);
error:
isl_map_free(map1);
isl_map_free(map2);
return NULL;
}
int isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1,
__isl_keep isl_map *map2,
int (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2))
{
int r;
if (!map1 || !map2)
return -1;
if (isl_space_match(map1->dim, isl_dim_param, map2->dim, isl_dim_param))
return fn(map1, map2);
if (!isl_space_has_named_params(map1->dim) ||
!isl_space_has_named_params(map2->dim))
isl_die(map1->ctx, isl_error_invalid,
"unaligned unnamed parameters", return -1);
map1 = isl_map_copy(map1);
map2 = isl_map_copy(map2);
map1 = isl_map_align_params(map1, isl_map_get_space(map2));
map2 = isl_map_align_params(map2, isl_map_get_space(map1));
r = fn(map1, map2);
isl_map_free(map1);
isl_map_free(map2);
return r;
}
int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
{
struct isl_ctx *ctx;
if (!bmap)
return -1;
ctx = bmap->ctx;
isl_assert(ctx, room_for_con(bmap, 1), return -1);
isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
return -1);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
isl_int *t;
int j = isl_basic_map_alloc_inequality(bmap);
if (j < 0)
return -1;
t = bmap->ineq[j];
bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
bmap->eq[-1] = t;
bmap->n_eq++;
bmap->n_ineq--;
bmap->eq--;
return 0;
}
isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
bmap->extra - bmap->n_div);
return bmap->n_eq++;
}
int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
{
return isl_basic_map_alloc_equality((struct isl_basic_map *)bset);
}
int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
{
if (!bmap)
return -1;
isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
bmap->n_eq -= n;
return 0;
}
int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
{
return isl_basic_map_free_equality((struct isl_basic_map *)bset, n);
}
int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
{
isl_int *t;
if (!bmap)
return -1;
isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
if (pos != bmap->n_eq - 1) {
t = bmap->eq[pos];
bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
bmap->eq[bmap->n_eq - 1] = t;
}
bmap->n_eq--;
return 0;
}
int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos)
{
return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos);
}
void isl_basic_map_inequality_to_equality(
struct isl_basic_map *bmap, unsigned pos)
{
isl_int *t;
t = bmap->ineq[pos];
bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
bmap->eq[-1] = t;
bmap->n_eq++;
bmap->n_ineq--;
bmap->eq--;
ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
}
static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
{
return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
}
int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap)
{
struct isl_ctx *ctx;
if (!bmap)
return -1;
ctx = bmap->ctx;
isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
isl_seq_clr(bmap->ineq[bmap->n_ineq] +
1 + isl_basic_map_total_dim(bmap),
bmap->extra - bmap->n_div);
return bmap->n_ineq++;
}
int isl_basic_set_alloc_inequality(struct isl_basic_set *bset)
{
return isl_basic_map_alloc_inequality((struct isl_basic_map *)bset);
}
int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
{
if (!bmap)
return -1;
isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
bmap->n_ineq -= n;
return 0;
}
int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
{
return isl_basic_map_free_inequality((struct isl_basic_map *)bset, n);
}
int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
{
isl_int *t;
if (!bmap)
return -1;
isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
if (pos != bmap->n_ineq - 1) {
t = bmap->ineq[pos];
bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
bmap->ineq[bmap->n_ineq - 1] = t;
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
}
bmap->n_ineq--;
return 0;
}
int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
{
return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos);
}
__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
isl_int *eq)
{
int k;
bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
if (!bmap)
return NULL;
k = isl_basic_map_alloc_equality(bmap);
if (k < 0)
goto error;
isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
isl_int *eq)
{
return (isl_basic_set *)
isl_basic_map_add_eq((isl_basic_map *)bset, eq);
}
__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
isl_int *ineq)
{
int k;
bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
if (!bmap)
return NULL;
k = isl_basic_map_alloc_inequality(bmap);
if (k < 0)
goto error;
isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
isl_int *ineq)
{
return (isl_basic_set *)
isl_basic_map_add_ineq((isl_basic_map *)bset, ineq);
}
int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
{
if (!bmap)
return -1;
isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
isl_seq_clr(bmap->div[bmap->n_div] +
1 + 1 + isl_basic_map_total_dim(bmap),
bmap->extra - bmap->n_div);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
return bmap->n_div++;
}
int isl_basic_set_alloc_div(struct isl_basic_set *bset)
{
return isl_basic_map_alloc_div((struct isl_basic_map *)bset);
}
int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
{
if (!bmap)
return -1;
isl_assert(bmap->ctx, n <= bmap->n_div, return -1);
bmap->n_div -= n;
return 0;
}
int isl_basic_set_free_div(struct isl_basic_set *bset, unsigned n)
{
return isl_basic_map_free_div((struct isl_basic_map *)bset, n);
}
/* Copy constraint from src to dst, putting the vars of src at offset
* dim_off in dst and the divs of src at offset div_off in dst.
* If both sets are actually map, then dim_off applies to the input
* variables.
*/
static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
struct isl_basic_map *src_map, isl_int *src,
unsigned in_off, unsigned out_off, unsigned div_off)
{
unsigned src_nparam = isl_basic_map_n_param(src_map);
unsigned dst_nparam = isl_basic_map_n_param(dst_map);
unsigned src_in = isl_basic_map_n_in(src_map);
unsigned dst_in = isl_basic_map_n_in(dst_map);
unsigned src_out = isl_basic_map_n_out(src_map);
unsigned dst_out = isl_basic_map_n_out(dst_map);
isl_int_set(dst[0], src[0]);
isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
if (dst_nparam > src_nparam)
isl_seq_clr(dst+1+src_nparam,
dst_nparam - src_nparam);
isl_seq_clr(dst+1+dst_nparam, in_off);
isl_seq_cpy(dst+1+dst_nparam+in_off,
src+1+src_nparam,
isl_min(dst_in-in_off, src_in));
if (dst_in-in_off > src_in)
isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
dst_in - in_off - src_in);
isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
src+1+src_nparam+src_in,
isl_min(dst_out-out_off, src_out));
if (dst_out-out_off > src_out)
isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
dst_out - out_off - src_out);
isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
src+1+src_nparam+src_in+src_out,
isl_min(dst_map->extra-div_off, src_map->n_div));
if (dst_map->n_div-div_off > src_map->n_div)
isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
div_off+src_map->n_div,
dst_map->n_div - div_off - src_map->n_div);
}
static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
struct isl_basic_map *src_map, isl_int *src,
unsigned in_off, unsigned out_off, unsigned div_off)
{
isl_int_set(dst[0], src[0]);
copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
}
static struct isl_basic_map *add_constraints(struct isl_basic_map *bmap1,
struct isl_basic_map *bmap2, unsigned i_pos, unsigned o_pos)
{
int i;
unsigned div_off;
if (!bmap1 || !bmap2)
goto error;
div_off = bmap1->n_div;
for (i = 0; i < bmap2->n_eq; ++i) {
int i1 = isl_basic_map_alloc_equality(bmap1);
if (i1 < 0)
goto error;
copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
i_pos, o_pos, div_off);
}
for (i = 0; i < bmap2->n_ineq; ++i) {
int i1 = isl_basic_map_alloc_inequality(bmap1);
if (i1 < 0)
goto error;
copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
i_pos, o_pos, div_off);
}
for (i = 0; i < bmap2->n_div; ++i) {
int i1 = isl_basic_map_alloc_div(bmap1);
if (i1 < 0)
goto error;
copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
i_pos, o_pos, div_off);
}
isl_basic_map_free(bmap2);
return bmap1;
error:
isl_basic_map_free(bmap1);
isl_basic_map_free(bmap2);
return NULL;
}
struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
struct isl_basic_set *bset2, unsigned pos)
{
return (struct isl_basic_set *)
add_constraints((struct isl_basic_map *)bset1,
(struct isl_basic_map *)bset2, 0, pos);
}
struct isl_basic_map *isl_basic_map_extend_space(struct isl_basic_map *base,
__isl_take isl_space *dim, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
struct isl_basic_map *ext;
unsigned flags;
int dims_ok;
if (!dim)
goto error;
if (!base)
goto error;
dims_ok = isl_space_is_equal(base->dim, dim) &&
base->extra >= base->n_div + extra;
if (dims_ok && room_for_con(base, n_eq + n_ineq) &&
room_for_ineq(base, n_ineq)) {
isl_space_free(dim);
return base;
}
isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
extra += base->extra;
n_eq += base->n_eq;
n_ineq += base->n_ineq;
ext = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
dim = NULL;
if (!ext)
goto error;
if (dims_ok)
ext->sample = isl_vec_copy(base->sample);
flags = base->flags;
ext = add_constraints(ext, base, 0, 0);
if (ext) {
ext->flags = flags;
ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
}
return ext;
error:
isl_space_free(dim);
isl_basic_map_free(base);
return NULL;
}
struct isl_basic_set *isl_basic_set_extend_space(struct isl_basic_set *base,
__isl_take isl_space *dim, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
return (struct isl_basic_set *)
isl_basic_map_extend_space((struct isl_basic_map *)base, dim,
extra, n_eq, n_ineq);
}
struct isl_basic_map *isl_basic_map_extend_constraints(
struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
{
if (!base)
return NULL;
return isl_basic_map_extend_space(base, isl_space_copy(base->dim),
0, n_eq, n_ineq);
}
struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
struct isl_basic_map *bmap;
isl_space *dim;
if (!base)
return NULL;
dim = isl_space_alloc(base->ctx, nparam, n_in, n_out);
if (!dim)
goto error;
bmap = isl_basic_map_extend_space(base, dim, extra, n_eq, n_ineq);
return bmap;
error:
isl_basic_map_free(base);
return NULL;
}
struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
unsigned nparam, unsigned dim, unsigned extra,
unsigned n_eq, unsigned n_ineq)
{
return (struct isl_basic_set *)
isl_basic_map_extend((struct isl_basic_map *)base,
nparam, 0, dim, extra, n_eq, n_ineq);
}
struct isl_basic_set *isl_basic_set_extend_constraints(
struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
{
return (struct isl_basic_set *)
isl_basic_map_extend_constraints((struct isl_basic_map *)base,
n_eq, n_ineq);
}
struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset)
{
return (struct isl_basic_set *)
isl_basic_map_cow((struct isl_basic_map *)bset);
}
struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
{
if (!bmap)
return NULL;
if (bmap->ref > 1) {
bmap->ref--;
bmap = isl_basic_map_dup(bmap);
}
if (bmap)
ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
return bmap;
}
struct isl_set *isl_set_cow(struct isl_set *set)
{
if (!set)
return NULL;
if (set->ref == 1)
return set;
set->ref--;
return isl_set_dup(set);
}
struct isl_map *isl_map_cow(struct isl_map *map)
{
if (!map)
return NULL;
if (map->ref == 1)
return map;
map->ref--;
return isl_map_dup(map);
}
static void swap_vars(struct isl_blk blk, isl_int *a,
unsigned a_len, unsigned b_len)
{
isl_seq_cpy(blk.data, a+a_len, b_len);
isl_seq_cpy(blk.data+b_len, a, a_len);
isl_seq_cpy(a, blk.data, b_len+a_len);
}
static __isl_give isl_basic_map *isl_basic_map_swap_vars(
__isl_take isl_basic_map *bmap, unsigned pos, unsigned n1, unsigned n2)
{
int i;
struct isl_blk blk;
if (!bmap)
goto error;
isl_assert(bmap->ctx,
pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error);
if (n1 == 0 || n2 == 0)
return bmap;
bmap = isl_basic_map_cow(bmap);
if (!bmap)
return NULL;
blk = isl_blk_alloc(bmap->ctx, n1 + n2);
if (isl_blk_is_error(blk))
goto error;
for (i = 0; i < bmap->n_eq; ++i)
swap_vars(blk,
bmap->eq[i] + pos, n1, n2);
for (i = 0; i < bmap->n_ineq; ++i)
swap_vars(blk,
bmap->ineq[i] + pos, n1, n2);
for (i = 0; i < bmap->n_div; ++i)
swap_vars(blk,
bmap->div[i]+1 + pos, n1, n2);
isl_blk_free(bmap->ctx, blk);
ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED);
bmap = isl_basic_map_gauss(bmap, NULL);
return isl_basic_map_finalize(bmap);
error:
isl_basic_map_free(bmap);
return NULL;
}
static __isl_give isl_basic_set *isl_basic_set_swap_vars(
__isl_take isl_basic_set *bset, unsigned n)
{
unsigned dim;
unsigned nparam;
nparam = isl_basic_set_n_param(bset);
dim = isl_basic_set_n_dim(bset);
isl_assert(bset->ctx, n <= dim, goto error);
return isl_basic_map_swap_vars(bset, 1 + nparam, n, dim - n);
error:
isl_basic_set_free(bset);
return NULL;
}
struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
{
int i = 0;
unsigned total;
if (!bmap)
goto error;
total = isl_basic_map_total_dim(bmap);
isl_basic_map_free_div(bmap, bmap->n_div);
isl_basic_map_free_inequality(bmap, bmap->n_ineq);
if (bmap->n_eq > 0)
isl_basic_map_free_equality(bmap, bmap->n_eq-1);
else {
i = isl_basic_map_alloc_equality(bmap);
if (i < 0)
goto error;
}
isl_int_set_si(bmap->eq[i][0], 1);
isl_seq_clr(bmap->eq[i]+1, total);
ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
isl_vec_free(bmap->sample);
bmap->sample = NULL;
return isl_basic_map_finalize(bmap);
error:
isl_basic_map_free(bmap);
return NULL;
}
struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset)
{
return (struct isl_basic_set *)
isl_basic_map_set_to_empty((struct isl_basic_map *)bset);
}
void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
{
int i;
unsigned off = isl_space_dim(bmap->dim, isl_dim_all);
isl_int *t = bmap->div[a];
bmap->div[a] = bmap->div[b];
bmap->div[b] = t;
for (i = 0; i < bmap->n_eq; ++i)
isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
for (i = 0; i < bmap->n_ineq; ++i)
isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
for (i = 0; i < bmap->n_div; ++i)
isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
}
/* Eliminate the specified n dimensions starting at first from the
* constraints using Fourier-Motzkin. The dimensions themselves
* are not removed.
*/
__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
enum isl_dim_type type, unsigned first, unsigned n)
{
int i;
if (!map)
return NULL;
if (n == 0)
return map;
map = isl_map_cow(map);
if (!map)
return NULL;
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_eliminate(map->p[i], type, first, n);
if (!map->p[i])
goto error;
}
return map;
error:
isl_map_free(map);
return NULL;
}
/* Eliminate the specified n dimensions starting at first from the
* constraints using Fourier-Motzkin. The dimensions themselves
* are not removed.
*/
__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
enum isl_dim_type type, unsigned first, unsigned n)
{
return (isl_set *)isl_map_eliminate((isl_map *)set, type, first, n);
}
/* Eliminate the specified n dimensions starting at first from the
* constraints using Fourier-Motzkin. The dimensions themselves
* are not removed.
*/
__isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
unsigned first, unsigned n)
{
return isl_set_eliminate(set, isl_dim_set, first, n);
}
__isl_give isl_basic_map *isl_basic_map_remove_divs(
__isl_take isl_basic_map *bmap)
{
if (!bmap)
return NULL;
bmap = isl_basic_map_eliminate_vars(bmap,
isl_space_dim(bmap->dim, isl_dim_all), bmap->n_div);
if (!bmap)
return NULL;
bmap->n_div = 0;
return isl_basic_map_finalize(bmap);
}
__isl_give isl_basic_set *isl_basic_set_remove_divs(
__isl_take isl_basic_set *bset)
{
return (struct isl_basic_set *)isl_basic_map_remove_divs(
(struct isl_basic_map *)bset);
}
__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
{
int i;
if (!map)
return NULL;
if (map->n == 0)
return map;
map = isl_map_cow(map);
if (!map)
return NULL;
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_remove_divs(map->p[i]);
if (!map->p[i])
goto error;
}
return map;
error:
isl_map_free(map);
return NULL;
}
__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
{
return isl_map_remove_divs(set);
}
struct isl_basic_map *isl_basic_map_remove_dims(struct isl_basic_map *bmap,
enum isl_dim_type type, unsigned first, unsigned n)
{
if (!bmap)
return NULL;
isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
goto error);
if (n == 0 && !isl_space_is_named_or_nested(bmap->dim, type))
return bmap;
bmap = isl_basic_map_eliminate_vars(bmap,
isl_basic_map_offset(bmap, type) - 1 + first, n);
if (!bmap)
return bmap;
if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && type == isl_dim_div)
return bmap;
bmap = isl_basic_map_drop(bmap, type, first, n);
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
/* Return true if the definition of the given div (recursively) involves
* any of the given variables.
*/
static int div_involves_vars(__isl_keep isl_basic_map *bmap, int div,
unsigned first, unsigned n)
{
int i;
unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
if (isl_int_is_zero(bmap->div[div][0]))
return 0;
if (isl_seq_first_non_zero(bmap->div[div] + 1 + first, n) >= 0)
return 1;
for (i = bmap->n_div - 1; i >= 0; --i) {
if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
continue;
if (div_involves_vars(bmap, i, first, n))
return 1;
}
return 0;
}
/* 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)
{
int i;
if (!bmap)
return NULL;
isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
goto error);
first += isl_basic_map_offset(bmap, type);
for (i = bmap->n_div - 1; i >= 0; --i) {
if (!div_involves_vars(bmap, i, first, n))
continue;
bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
if (!bmap)
return NULL;
i = bmap->n_div;
}
return bmap;
error:
isl_basic_map_free(bmap);
return NULL;
}
__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map,
enum isl_dim_type type, unsigned first, unsigned n)
{
int i;
if (!map)
return NULL;
if (map->n == 0)
return map;
map = isl_map_cow(map);
if (!map)
return NULL;
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_remove_divs_involving_dims(map->p[i],
type, first, n);
if (!map->p[i])
goto error;
}
return map;
error:
isl_map_free(map);
return NULL;
}
__isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set,
enum isl_dim_type type, unsigned first, unsigned n)
{
return (isl_set *)isl_map_remove_divs_involving_dims((isl_map *)set,
type, first, n);
}
/* Does the desciption 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.
*/
int isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap,
enum isl_dim_type type, unsigned first, unsigned n)
{
int i;
if (!bmap)
return -1;
if (first + n > isl_basic_map_dim(bmap, type))
isl_die(bmap->ctx, isl_error_invalid,
"index out of bounds", return -1);
first += isl_basic_map_offset(bmap, type);
for (i = 0; i < bmap->n_eq; ++i)
if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0)
return 1;
for (i = 0; i < bmap->n_ineq; ++i)
if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0)
return 1;
for (i = 0; i < bmap->n_div; ++i) {
if (isl_int_is_zero(bmap->div[i][0]))
continue;
if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0)
return 1;
}
return 0;
}
int isl_map_involves_dims(__isl_keep isl_map *map,
enum isl_dim_type type, unsigned first, unsigned n)
{
int i;
if (!map)
return -1;
if (first + n > isl_map_dim(map, type))
isl_die(map->ctx, isl_error_invalid,
"index out of bounds", return -1);
for (i = 0; i < map->n; ++i) {
int involves = isl_basic_map_involves_dims(map->p[i],
type, first, n);
if (involves < 0 || involves)
return involves;
}
return 0;
}
int isl_basic_set_involves_dims(__isl_keep isl_basic_set *bset,
enum isl_dim_type type, unsigned first, unsigned n)
{
return isl_basic_map_involves_dims(bset, type, first, n);
}
int isl_set_involves_dims(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned first, unsigned n)
{
return isl_map_involves_dims(set, type, first, n);
}
/* Return true if the definition of the given div is unknown or depends
* on unknown divs.
*/
static int div_is_unknown(__isl_keep isl_basic_map *bmap, int div)
{
int i;
unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
if (isl_int_is_zero(bmap->div[div][0]))
return 1;
for (i = bmap->n_div - 1; i >= 0; --i) {
if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
continue;
if (div_is_unknown(bmap, i))
return 1;
}
return 0;
}
/* 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)
{
int i;
if (!bmap)
return NULL;
for (i = bmap->n_div - 1; i >= 0; --i) {
if (!div_is_unknown(bmap, i))
continue;
bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
}
return bmap;
}
__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
{
int i;
if (!map)
return NULL;
if (map->n == 0)
return map;
map = isl_map_cow(map);
if (!map)
return NULL;
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_remove_unknown_divs(map->p[i]);
if (!map->p[i])
goto error;
}
return map;
error:
isl_map_free(map);
return NULL;
}
__isl_give isl_set *isl_set_remove_unknown_divs(__isl_take isl_set *set)
{
return (isl_set *)isl_map_remove_unknown_divs((isl_map *)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)
{
return (isl_basic_set *)
isl_basic_map_remove_dims((isl_basic_map *)bset, type, first, n);
}
struct isl_map *isl_map_remove_dims(struct isl_map *map,
enum isl_dim_type type, unsigned first, unsigned n)
{
int i;
if (n == 0)
return map;
map = isl_map_cow(map);
if (!map)
return NULL;
isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
for (i = 0; i < map->n; ++i) {
map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
isl_basic_map_offset(map->p[i], type) - 1 + first, n);
if (!map->p[i])
goto error;
}
map = isl_map_drop(map, type, first, n);
return map;
error:
isl_map_free(map);
return NULL;
}
__isl_give isl_set *isl_set_remove_dims(__isl_take isl_set *bset,
enum isl_dim_type type, unsigned first, unsigned n)
{
return (isl_set *)isl_map_remove_dims((isl_map *)bset, type, first, n);
}
/* Project out n inputs starting at first using Fourier-Motzkin */
struct isl_map *isl_map_remove_inputs(struct isl_map *map,
unsigned first, unsigned n)
{
return isl_map_remove_dims(map, isl_dim_in, first, n);
}
static void dump_term(struct isl_basic_map *bmap,
isl_int c, int pos, FILE *out)
{
const char *name;
unsigned in = isl_basic_map_n_in(bmap);
unsigned dim = in + isl_basic_map_n_out(bmap);
unsigned nparam = isl_basic_map_n_param(bmap);
if (!pos)
isl_int_print(out, c, 0);
else {
if (!isl_int_is_one(c))
isl_int_print(out, c, 0);
if (pos < 1 + nparam) {
name = isl_space_get_dim_name(bmap->dim,
isl_dim_param, pos - 1);
if (name)
fprintf(out, "%s", name);
else
fprintf(out, "p%d", pos - 1);
} else if (pos < 1 + nparam + in)
fprintf(out, "i%d", pos - 1 - nparam);
else if (pos < 1 + nparam + dim)
fprintf(out, "o%d", pos - 1 - nparam - in);
else
fprintf(out, "e%d", pos - 1 - nparam - dim);
}
}
static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
int sign, FILE *out)
{
int i;
int first;
unsigned len = 1 + isl_basic_map_total_dim(bmap);
isl_int v;
isl_int_init(v);
for (i = 0, first = 1; i < len; ++i) {
if (isl_int_sgn(c[i]) * sign <= 0)
continue;
if (!first)
fprintf(out, " + ");
first = 0;
isl_int_abs(v, c[i]);
dump_term(bmap, v, i, out);
}
isl_int_clear(v);
if (first)
fprintf(out, "0");
}
static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
const char *op, FILE *out, int indent)
{
int i;
fprintf(out, "%*s", indent, "");
dump_constraint_sign(bmap, c, 1, out);
fprintf(out, " %s ", op);
dump_constraint_sign(bmap, c, -1, out);
fprintf(out, "\n");
for (i = bmap->n_div; i < bmap->extra; ++i) {
if (isl_int_is_zero(c[1+isl_space_dim(bmap->dim, isl_dim_all)+i]))
continue;
fprintf(out, "%*s", indent, "");
fprintf(out, "ERROR: unused div coefficient not zero\n");
abort();
}
}
static void dump_constraints(struct isl_basic_map *bmap,
isl_int **c, unsigned n,
const char *op, FILE *out, int indent)
{
int i;
for (i = 0; i < n; ++i)
dump_constraint(bmap, c[i], op, out, indent);
}
static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
{
int j;
int first = 1;
unsigned total = isl_basic_map_total_dim(bmap);
for (j = 0; j < 1 + total; ++j) {
if (isl_int_is_zero(exp[j]))
continue;
if (!first && isl_int_is_pos(exp[j]))
fprintf(out, "+");
dump_term(bmap, exp[j], j, out);
first = 0;
}
}
static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
{
int i;
dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
for (i = 0; i < bmap->n_div; ++i) {
fprintf(out, "%*s", indent, "");
fprintf(out, "e%d = [(", i);
dump_affine(bmap, bmap->div[i]+1, out);
fprintf(out, ")/");
isl_int_print(out, bmap->div[i][0], 0);
fprintf(out, "]\n");
}
}
void isl_basic_set_print_internal(struct isl_basic_set *bset,
FILE *out, int indent)
{
if (!bset) {
fprintf(out, "null basic set\n");
return;
}
fprintf(out, "%*s", indent, "");
fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
bset->ref, bset->dim->nparam, bset->dim->n_out,
bset->extra, bset->flags);
dump((struct isl_basic_map *)bset, out, indent);
}
void isl_basic_map_print_internal(struct isl_basic_map *bmap,
FILE *out, int indent)
{
if (!bmap) {
fprintf(out, "null basic map\n");
return;
}
fprintf(out, "%*s", indent, "");
fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
"flags: %x, n_name: %d\n",
bmap->ref,
bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
bmap->extra, bmap->flags, bmap->dim->n_id);
dump(bmap, out, indent);
}
int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
{
unsigned total;
if (!bmap)
return -1;
total = isl_basic_map_total_dim(bmap);
isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
return 0;
}
__isl_give isl_set *isl_set_alloc_space(__isl_take isl_space *dim, int n,
unsigned flags)
{
struct isl_set *set;
if (!dim)
return NULL;
isl_assert(dim->ctx, dim->n_in == 0, goto error);
isl_assert(dim->ctx, n >= 0, goto error);
set = isl_alloc(dim->ctx, struct isl_set,
sizeof(struct isl_set) +
(n - 1) * sizeof(struct isl_basic_set *));
if (!set)
goto error;
set->ctx = dim->ctx;
isl_ctx_ref(set->ctx);
set->ref = 1;
set->size = n;
set->n = 0;
set->dim = dim;
set->flags = flags;
return set;
error:
isl_space_free(dim);
return NULL;
}
struct isl_set *isl_set_alloc(struct isl_ctx *ctx,
unsigned nparam, unsigned dim, int n, unsigned flags)
{
struct isl_set *set;
isl_space *dims;
dims = isl_space_alloc(ctx, nparam, 0, dim);
if (!dims)
return NULL;
set = isl_set_alloc_space(dims, n, flags);
return set;
}
/* Make sure "map" has room for at least "n" more basic maps.
*/
struct isl_map *isl_map_grow(struct isl_map *map, int n)
{
int i;
struct isl_map *grown = NULL;
if (!map)
return NULL;
isl_assert(map->ctx, n >= 0, goto error);
if (map->n + n <= map->size)
return map;
grown = isl_map_alloc_space(isl_map_get_space(map), map->n + n, map->flags);
if (!grown)
goto error;
for (i = 0; i < map->n; ++i) {
grown->p[i] = isl_basic_map_copy(map->p[i]);
if (!grown->p[i])
goto error;
grown->n++;
}
isl_map_free(map);
return grown;
error:
isl_map_free(grown);
isl_map_free(map);
return NULL;
}
/* Make sure "set" has room for at least "n" more basic sets.
*/
struct isl_set *isl_set_grow(struct isl_set *set, int n)
{
return (struct isl_set *)isl_map_grow((struct isl_map *)set, n);
}
struct isl_set *isl_set_dup(struct isl_set *set)
{
int i;
struct isl_set *dup;
if (!set)
return NULL;
dup = isl_set_alloc_space(isl_space_copy(set->dim), set->n, set->flags);
if (!dup)
return NULL;
for (i = 0; i < set->n; ++i)
dup = isl_set_add_basic_set(dup, isl_basic_set_copy(set->p[i]));
return dup;
}
struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset)
{
return isl_map_from_basic_map(bset);
}
struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap)
{
struct isl_map *map;
if (!bmap)
return NULL;
map = isl_map_alloc_space(isl_space_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
return isl_map_add_basic_map(map, bmap);
}
__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
__isl_take isl_basic_set *bset)
{
return (struct isl_set *)isl_map_add_basic_map((struct isl_map *)set,
(struct isl_basic_map *)bset);
}
void isl_set_free(struct isl_set *set)
{
int i;
if (!set)
return;
if (--set->ref > 0)
return;
isl_ctx_deref(set->ctx);
for (i = 0; i < set->n; ++i)
isl_basic_set_free(set->p[i]);
isl_space_free(set->dim);
free(set);
}
void isl_set_print_internal(struct isl_set *set, FILE *out, int indent)
{
int i;
if (!set) {
fprintf(out, "null set\n");
return;
}
fprintf(out, "%*s", indent, "");
fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
set->ref, set->n, set->dim->nparam, set->dim->n_out,
set->flags);
for (i = 0; i < set->n; ++i) {
fprintf(out, "%*s", indent, "");
fprintf(out, "basic set %d:\n", i);
isl_basic_set_print_internal(set->p[i], out, indent+4);
}
}
void isl_map_print_internal(struct isl_map *map, FILE *out, int indent)
{
int i;
if (!map) {
fprintf(out, "null map\n");
return;
}
fprintf(out, "%*s", indent, "");
fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
"flags: %x, n_name: %d\n",
map->ref, map->n, map->dim->nparam, map->dim->n_in,
map->dim->n_out, map->flags, map->dim->n_id);
for (i = 0; i < map->n; ++i) {
fprintf(out, "%*s", indent, "");
fprintf(out, "basic map %d:\n", i);
isl_basic_map_print_internal(map->p[i], out, indent+4);
}
}
struct isl_basic_map *isl_basic_map_intersect_domain(
struct isl_basic_map *bmap, struct isl_basic_set *bset)
{
struct isl_basic_map *bmap_domain;
if (!bmap || !bset)
goto error;
isl_assert(bset->ctx, isl_space_match(bmap->dim, isl_dim_param,
bset->dim, isl_dim_param), goto error);
if (isl_space_dim(bset->dim, isl_dim_set) != 0)
isl_assert(bset->ctx,
isl_basic_map_compatible_domain(bmap, bset), goto error);
bmap = isl_basic_map_cow(bmap);
if (!bmap)
goto error;
bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
bset->n_div, bset->n_eq, bset->n_ineq);
bmap_domain = isl_basic_map_from_domain(bset);
bmap = add_constraints(bmap, bmap_domain, 0, 0);
bmap = isl_basic_map_simplify(bmap);
return isl_basic_map_finalize(bmap);
error:
isl_basic_map_free(bmap);
isl_basic_set_free(bset);
return NULL;
}
struct isl_basic_map *isl_basic_map_intersect_range(
struct isl_basic_map *bmap, struct isl_basic_set *bset)
{
struct isl_basic_map *bmap_range;
if (!bmap || !bset)
goto error;
isl_assert(bset->ctx, isl_space_match(bmap->dim, isl_dim_param,
bset->dim, isl_dim_param), goto error);
if (isl_space_dim(bset->dim, isl_dim_set) != 0)
isl_assert(bset->ctx,
isl_basic_map_compatible_range(bmap, bset), goto error);
if (isl_basic_set_is_universe(bset)) {
isl_basic_set_free(bset);
return bmap;
}
bmap = isl_basic_map_cow(bmap);
if (!bmap)
goto error;
bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
bset->n_div, bset->n_eq, bset->n_ineq);
bmap_range = isl_basic_map_from_basic_set(bset, isl_space_copy(bset->dim));
bmap = add_constraints(bmap, bmap_range, 0, 0);
bmap = isl_basic_map_simplify(bmap);
return isl_basic_map_finalize(bmap);
error:
isl_basic_map_free(bmap);
isl_basic_set_free(bset);
return NULL;
}
int isl_basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
{
int i;
unsigned total;
isl_int s;
total = 1 + isl_basic_map_total_dim(bmap);
if (total != vec->size)
return -1;
isl_int_init(s);
for (i = 0; i < bmap->n_eq; ++i) {
isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
if (!isl_int_is_zero(s)) {
isl_int_clear(s);
return 0;
}
}
for (i = 0; i < bmap->n_ineq; ++i) {
isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
if (isl_int_is_neg(s)) {
isl_int_clear(s);
return 0;
}
}
isl_int_clear(s);
return 1;
}
int isl_basic_set_contains(struct isl_basic_set *bset, struct isl_vec *vec)
{
return isl_basic_map_contains((struct isl_basic_map *)bset, vec);
}
struct isl_basic_map *isl_basic_map_intersect(
struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
{
struct isl_vec *sample = NULL;
if (!bmap1 || !bmap2)
goto error;
isl_assert(bmap1->ctx, isl_space_match(bmap1->dim, isl_dim_param,
bmap2->dim, isl_dim_param), goto error);
if (isl_space_dim(bmap1->dim, isl_dim_all) ==
isl_space_dim(bmap1->dim, isl_dim_param) &&
isl_space_dim(bmap2->dim, isl_dim_all) !=
isl_space_dim(bmap2->dim, isl_dim_param))
return isl_basic_map_intersect(bmap2, bmap1);
if (isl_space_dim(bmap2->dim, isl_dim_all) !=
isl_space_dim(bmap2->dim, isl_dim_param))
isl_assert(bmap1->ctx,
isl_space_is_equal(bmap1->dim, bmap2->dim), goto error);
if (bmap1->sample &&
isl_basic_map_contains(bmap1, bmap1->sample) > 0 &&
isl_basic_map_contains(bmap2, bmap1->sample) > 0)
sample = isl_vec_copy(bmap1->sample);
else if (bmap2->sample &&
isl_basic_map_contains(bmap1, bmap2->sample) > 0 &&
isl_basic_map_contains(bmap2, bmap2->sample) > 0)
sample = isl_vec_copy(bmap2->sample);
bmap1 = isl_basic_map_cow(bmap1);
if (!bmap1)
goto error;
bmap1 = isl_basic_map_extend_space(bmap1, isl_space_copy(bmap1->dim),
bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
bmap1 = add_constraints(bmap1, bmap2, 0, 0);
if (!bmap1)
isl_vec_free(sample);
else if (sample) {
isl_vec_free(bmap1->sample);
bmap1->sample = sample;
}
bmap1 = isl_basic_map_simplify(bmap1);
return isl_basic_map_finalize(bmap1);
error:
if (sample)
isl_vec_free(sample);
isl_basic_map_free(bmap1);
isl_basic_map_free(bmap2);
return NULL;
}
struct isl_basic_set *isl_basic_set_intersect(
struct isl_basic_set *bset1, struct isl_basic_set *bset2)
{
return (struct isl_basic_set *)
isl_basic_map_intersect(
(struct isl_basic_map *)bset1,
(struct isl_basic_map *)bset2);
}
__isl_give isl_basic_set *isl_basic_set_intersect_params(
__isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
{
return isl_basic_set_intersect(bset1, bset2);
}
/* 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)
{
isl_assert(map1->ctx, map1->n == 1, goto error);
isl_assert(map2->ctx, map1->n == 1, goto error);
isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);
if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
return isl_map_intersect(map2, map1);
isl_assert(map2->ctx,
map2->p[0]->n_eq + map2->p[0]->n_ineq == 1, goto error);
map1 = isl_map_cow(map1);
if (!map1)
goto error;
if (isl_map_plain_is_empty(map1)) {
isl_map_free(map2);
return map1;
}
map1->p[0] = isl_basic_map_cow(map1->p[0]);
if (map2->p[0]->n_eq == 1)
map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
else
map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
map2->p[0]->ineq[0]);
map1->p[0] = isl_basic_map_simplify(map1->p[0]);
map1->p[0] = isl_basic_map_finalize(map1->p[0]);
if (!map1->p[0])
goto error;
if (isl_basic_map_plain_is_empty(map1->p[0])) {
isl_basic_map_free(map1->p[0]);
map1->n = 0;
}
isl_map_free(map2);
return map1;
error:
isl_map_free(map1);
isl_map_free(map2);
return NULL;
}
/* 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)
{
unsigned flags = 0;
struct isl_map *result;
int i, j;
if (!map1 || !map2)
goto error;
if (isl_map_plain_is_empty(map1) &&
isl_space_is_equal(map1->dim, map2->dim)) {
isl_map_free(map2);
return map1;
}
if (isl_map_plain_is_empty(map2) &&
isl_space_is_equal(map1->dim, map2->dim)) {
isl_map_free(map1);
return map2;
}
if (map1->n == 1 && map2->n == 1 &&
map1->p[0]->n_div == 0 && map2->p[0]->n_div == 0 &&
isl_space_is_equal(map1->dim, map2->dim) &&
(map1->p[0]->n_eq + map1->p[0]->n_ineq == 1 ||
map2->p[0]->n_eq + map2->p[0]->n_ineq == 1))
return map_intersect_add_constraint(map1, map2);
if (isl_space_dim(map2->dim, isl_dim_all) !=
isl_space_dim(map2->dim, isl_dim_param))
isl_assert(map1->ctx,
isl_space_is_equal(map1->dim, map2->dim), goto error);
if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
ISL_F_ISSET(map2, ISL_MAP_DISJOINT))
ISL_FL_SET(flags, ISL_MAP_DISJOINT);
result = isl_map_alloc_space(isl_space_copy(map1->dim),
map1->n * map2->n, flags);
if (!result)
goto error;
for (i = 0; i < map1->n; ++i)
for (j = 0; j < map2->n; ++j) {
struct isl_basic_map *part;
part = isl_basic_map_intersect(
isl_basic_map_copy(map1->p[i]),
isl_basic_map_copy(map2->p[j]));
if (isl_basic_map_is_empty(part))
isl_basic_map_free(part);
else
result = isl_map_add_basic_map(result, part);
if (!result)
goto error;
}
isl_map_free(map1);
isl_map_free(map2);
return result;
error:
isl_map_free(map1);
isl_map_free(map2);
return NULL;
}
static __isl_give isl_map *map_intersect(__isl_take isl_map *map1,
__isl_take isl_map *map2)
{
if (!map1 || !map2)
goto error;
if (!isl_space_is_equal(map1->dim, map2->dim))
isl_die(isl_map_get_ctx(map1), isl_error_invalid,
"spaces don't match", goto error);
return map_intersect_internal(map1, map2);
error:
isl_map_free(map1);
isl_map_free(map2);
return NULL;
}
__isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1,
__isl_take isl_map *map2)
{
return isl_map_align_params_map_map_and(map1, map2, &map_intersect);
}
struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
{
return (struct isl_set *)
isl_map_intersect((struct isl_map *)set1,
(struct isl_map *)set2);
}
/* map_intersect_internal accepts intersections
* with parameter domains, so we can just call that function.
*/
static __isl_give isl_map *map_intersect_params(__isl_take isl_map *map,
__isl_take isl_set *params)
{
return map_intersect_internal(map, params);
}
__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map1,
__isl_take isl_map *map2)
{
return isl_map_align_params_map_map_and(map1, map2, &map_intersect_params);
}
__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set,
__isl_take isl_set *params)
{
return isl_map_intersect_params(set, params);
}
struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)