X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_map.c;h=b9f8b01d800ceb9b22386a2e0d59150413d7bfe4;hb=bdc8ebd299c5c3b1b1fac36ab3b1b44e2d7de85c;hp=8d6bfacdcd4174fa263c8bb4af4e6516ac8853d9;hpb=59bbb398f4ef67d88dd66f4b281cf7a2b9f5c4af;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_map.c b/isl_map.c
index 8d6bfac..b9f8b01 100644
--- a/isl_map.c
+++ b/isl_map.c
@@ -1,17 +1,20 @@
 /*
  * 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 <strings.h>
 #include "isl_ctx.h"
 #include "isl_blk.h"
-#include "isl_dim.h"
+#include "isl_dim_private.h"
 #include "isl_equalities.h"
 #include "isl_list.h"
 #include "isl_lp.h"
@@ -52,6 +55,7 @@ static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
 	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;
 	}
 }
 
@@ -61,11 +65,13 @@ static unsigned pos(struct isl_dim *dim, enum isl_dim_type 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;
 	}
 }
 
-static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
-		enum isl_dim_type type, unsigned dst_pos)
+static void isl_dim_map_dim_range(struct isl_dim_map *dim_map,
+	struct isl_dim *dim, enum isl_dim_type type,
+	unsigned first, unsigned n, unsigned dst_pos)
 {
 	int i;
 	unsigned src_pos;
@@ -74,8 +80,14 @@ static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
 		return;
 	
 	src_pos = pos(dim, type);
-	for (i = 0; i < n(dim, type); ++i)
-		dim_map->pos[1 + dst_pos + i] = src_pos + i;
+	for (i = 0; i < n; ++i)
+		dim_map->pos[1 + dst_pos + i] = src_pos + first + i;
+}
+
+static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
+		enum isl_dim_type type, unsigned dst_pos)
+{
+	isl_dim_map_dim_range(dim_map, dim, type, 0, n(dim, type), dst_pos);
 }
 
 static void isl_dim_map_div(struct isl_dim_map *dim_map,
@@ -104,23 +116,26 @@ static void isl_dim_map_dump(struct isl_dim_map *dim_map)
 unsigned isl_basic_map_dim(const struct isl_basic_map *bmap,
 				enum isl_dim_type type)
 {
+	if (!bmap)
+		return 0;
 	switch (type) {
 	case isl_dim_param:
 	case isl_dim_in:
 	case isl_dim_out:	return isl_dim_size(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(const struct isl_map *map, enum isl_dim_type type)
 {
-	return n(map->dim, type);
+	return map ? n(map->dim, type) : 0;
 }
 
 unsigned isl_set_dim(const struct isl_set *set, enum isl_dim_type type)
 {
-	return n(set->dim, type);
+	return set ? n(set->dim, type) : 0;
 }
 
 unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
@@ -132,6 +147,7 @@ unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
 	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;
 	}
 }
 
@@ -148,12 +164,12 @@ unsigned isl_basic_set_dim(const struct isl_basic_set *bset,
 
 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
 {
-	return bset->dim->n_out;
+	return isl_basic_set_dim(bset, isl_dim_set);
 }
 
 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
 {
-	return bset->dim->nparam;
+	return isl_basic_set_dim(bset, isl_dim_param);
 }
 
 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
@@ -163,12 +179,12 @@ unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
 
 unsigned isl_set_n_dim(const struct isl_set *set)
 {
-	return set->dim->n_out;
+	return isl_set_dim(set, isl_dim_set);
 }
 
 unsigned isl_set_n_param(const struct isl_set *set)
 {
-	return set->dim->nparam;
+	return isl_set_dim(set, isl_dim_param);
 }
 
 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
@@ -193,7 +209,7 @@ unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
 
 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
 {
-	return isl_dim_total(bmap->dim) + bmap->n_div;
+	return bmap ? isl_dim_total(bmap->dim) + bmap->n_div : 0;
 }
 
 unsigned isl_map_n_in(const struct isl_map *map)
@@ -231,6 +247,11 @@ int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
 	       bmap->dim->nparam == bset->dim->nparam;
 }
 
+isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
+{
+	return map ? map->ctx : NULL;
+}
+
 struct isl_dim *isl_basic_map_get_dim(struct isl_basic_map *bmap)
 {
 	if (!bmap)
@@ -259,6 +280,66 @@ struct isl_dim *isl_set_get_dim(struct isl_set *set)
 	return isl_dim_copy(set->dim);
 }
 
+__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)
+{
+	if (!bmap)
+		return NULL;
+	bmap->dim = isl_dim_set_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;
+
+	if (!map)
+		return NULL;
+
+	map->dim = isl_dim_set_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_is_rational(__isl_keep isl_basic_map *bmap)
+{
+	if (!bmap)
+		return -1;
+	return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
+}
+
 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)
@@ -266,39 +347,28 @@ static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 	int i;
 	size_t row_size = 1 + isl_dim_total(bmap->dim) + 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)) {
-		free(bmap);
-		return NULL;
-	}
+	if (isl_blk_is_error(bmap->block))
+		goto error;
 
 	bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
-	if (!bmap->ineq) {
-		isl_blk_free(ctx, bmap->block);
-		free(bmap);
-		return NULL;
-	}
+	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)) {
-			free(bmap->ineq);
-			isl_blk_free(ctx, bmap->block);
-			free(bmap);
-			return NULL;
-		}
+		if (isl_blk_is_error(bmap->block2))
+			goto error;
 
 		bmap->div = isl_alloc_array(ctx, isl_int *, extra);
-		if (!bmap->div) {
-			isl_blk_free(ctx, bmap->block2);
-			free(bmap->ineq);
-			isl_blk_free(ctx, bmap->block);
-			free(bmap);
-			return NULL;
-		}
+		if (!bmap->div)
+			goto error;
 	}
 
 	for (i = 0; i < n_ineq + n_eq; ++i)
@@ -307,8 +377,6 @@ static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
 	for (i = 0; i < extra; ++i)
 		bmap->div[i] = bmap->block2.data + i * (1 + row_size);
 
-	bmap->ctx = ctx;
-	isl_ctx_ref(ctx);
 	bmap->ref = 1;
 	bmap->flags = 0;
 	bmap->c_size = n_eq + n_ineq;
@@ -352,7 +420,7 @@ struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_dim *dim,
 
 	if (!dim)
 		return NULL;
-	bmap = isl_alloc_type(dim->ctx, struct isl_basic_map);
+	bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
 	if (!bmap)
 		goto error;
 	bmap->dim = dim;
@@ -455,7 +523,10 @@ struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
 		bmap->ref++;
 		return bmap;
 	}
-	return isl_basic_map_dup(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)
@@ -976,10 +1047,13 @@ struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
 		return NULL;
 	dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out);
 	if (!dim)
-		return NULL;
+		goto error;
 
 	bmap = isl_basic_map_extend_dim(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,
@@ -1014,7 +1088,8 @@ struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
 		bmap->ref--;
 		bmap = isl_basic_map_dup(bmap);
 	}
-	ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
+	if (bmap)
+		ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
 	return bmap;
 }
 
@@ -1125,7 +1200,7 @@ struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
 	if (bmap->n_eq > 0)
 		isl_basic_map_free_equality(bmap, bmap->n_eq-1);
 	else {
-		isl_basic_map_alloc_equality(bmap);
+		i = isl_basic_map_alloc_equality(bmap);
 		if (i < 0)
 			goto error;
 	}
@@ -1166,38 +1241,56 @@ void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
 }
 
 /* Eliminate the specified n dimensions starting at first from the
- * constraints using Fourier-Motzkin, The dimensions themselves
+ * constraints using Fourier-Motzkin.  The dimensions themselves
  * are not removed.
  */
-struct isl_set *isl_set_eliminate_dims(struct isl_set *set,
-	unsigned first, unsigned n)
+__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
+	enum isl_dim_type type, unsigned first, unsigned n)
 {
 	int i;
-	unsigned nparam;
 
-	if (!set)
+	if (!map)
 		return NULL;
 	if (n == 0)
-		return set;
+		return map;
 
-	set = isl_set_cow(set);
-	if (!set)
+	map = isl_map_cow(map);
+	if (!map)
 		return NULL;
-	isl_assert(set->ctx, first+n <= isl_set_n_dim(set), goto error);
-	nparam = isl_set_n_param(set);
+	isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
+	first += pos(map->dim, type) - 1;
 	
-	for (i = 0; i < set->n; ++i) {
-		set->p[i] = isl_basic_set_eliminate_vars(set->p[i],
-							    nparam + first, n);
-		if (!set->p[i])
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_eliminate_vars(map->p[i], first, n);
+		if (!map->p[i])
 			goto error;
 	}
-	return set;
+	return map;
 error:
-	isl_set_free(set);
+	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);
+}
+
 /* Project out n dimensions starting at first using Fourier-Motzkin */
 struct isl_set *isl_set_remove_dims(struct isl_set *set,
 	unsigned first, unsigned n)
@@ -1683,10 +1776,10 @@ struct isl_basic_map *isl_basic_map_intersect_domain(
 		    isl_basic_map_compatible_domain(bmap, bset), goto error);
 
 	bmap = isl_basic_map_cow(bmap);
-	bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
-			bset->n_div, bset->n_eq, bset->n_ineq);
 	if (!bmap)
 		goto error;
+	bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
+			bset->n_div, bset->n_eq, bset->n_ineq);
 	dim = isl_dim_reverse(isl_dim_copy(bset->dim));
 	bmap_domain = isl_basic_map_from_basic_set(bset, dim);
 	bmap = add_constraints(bmap, bmap_domain, 0, 0);
@@ -1715,10 +1808,10 @@ struct isl_basic_map *isl_basic_map_intersect_range(
 		    isl_basic_map_compatible_range(bmap, bset), goto error);
 
 	bmap = isl_basic_map_cow(bmap);
-	bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
-			bset->n_div, bset->n_eq, bset->n_ineq);
 	if (!bmap)
 		goto error;
+	bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
+			bset->n_div, bset->n_eq, bset->n_ineq);
 	bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
 	bmap = add_constraints(bmap, bmap_range, 0, 0);
 
@@ -1799,13 +1892,15 @@ struct isl_basic_map *isl_basic_map_intersect(
 		sample = isl_vec_copy(bmap2->sample);
 
 	bmap1 = isl_basic_map_cow(bmap1);
-	bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
-			bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
 	if (!bmap1)
 		goto error;
+	bmap1 = isl_basic_map_extend_dim(bmap1, isl_dim_copy(bmap1->dim),
+			bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
 	bmap1 = add_constraints(bmap1, bmap2, 0, 0);
 
-	if (sample) {
+	if (!bmap1)
+		isl_vec_free(sample);
+	else if (sample) {
 		isl_vec_free(bmap1->sample);
 		bmap1->sample = sample;
 	}
@@ -1854,6 +1949,10 @@ static __isl_give isl_map *map_intersect_add_constraint(
 	map1 = isl_map_cow(map1);
 	if (!map1)
 		goto error;
+	if (isl_map_fast_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]);
@@ -1866,6 +1965,11 @@ static __isl_give isl_map *map_intersect_add_constraint(
 	if (!map1->p[0])
 		goto error;
 
+	if (isl_basic_map_fast_is_empty(map1->p[0])) {
+		isl_basic_map_free(map1->p[0]);
+		map1->n = 0;
+	}
+
 	isl_map_free(map2);
 
 	return map1;
@@ -1884,6 +1988,15 @@ struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
 	if (!map1 || !map2)
 		goto error;
 
+	if (isl_map_fast_is_empty(map1)) {
+		isl_map_free(map2);
+		return map1;
+	}
+	if (isl_map_fast_is_empty(map2)) {
+		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_dim_equal(map1->dim, map2->dim) &&
@@ -1956,13 +2069,14 @@ struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
 	return isl_basic_map_from_basic_set(bset, dim);
 }
 
-__isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
-		enum isl_dim_type type, unsigned n)
+__isl_give isl_basic_map *isl_basic_map_insert(__isl_take isl_basic_map *bmap,
+		enum isl_dim_type type, unsigned pos, unsigned n)
 {
 	struct isl_dim *res_dim;
 	struct isl_basic_map *res;
 	struct isl_dim_map *dim_map;
-	unsigned total, pos;
+	unsigned total, off;
+	enum isl_dim_type t;
 
 	if (n == 0)
 		return bmap;
@@ -1970,18 +2084,24 @@ __isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
 	if (!bmap)
 		return NULL;
 
-	res_dim = isl_dim_add(isl_basic_map_get_dim(bmap), type, n);
+	res_dim = isl_dim_insert(isl_basic_map_get_dim(bmap), type, pos, n);
 
 	total = isl_basic_map_total_dim(bmap) + n;
 	dim_map = isl_dim_map_alloc(bmap->ctx, total);
-	pos = 0;
-	isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos);
-	pos += isl_dim_size(res_dim, isl_dim_param);
-	isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos);
-	pos += isl_dim_size(res_dim, isl_dim_in);
-	isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos);
-	pos += isl_dim_size(res_dim, isl_dim_out);
-	isl_dim_map_div(dim_map, bmap, pos);
+	off = 0;
+	for (t = isl_dim_param; t <= isl_dim_out; ++t) {
+		if (t != type) {
+			isl_dim_map_dim(dim_map, bmap->dim, t, off);
+		} else {
+			unsigned size = isl_basic_map_dim(bmap, t);
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+						0, pos, off);
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+						pos, size - pos, off + pos + n);
+		}
+		off += isl_dim_size(res_dim, t);
+	}
+	isl_dim_map_div(dim_map, bmap, off);
 
 	res = isl_basic_map_alloc_dim(res_dim,
 			bmap->n_div, bmap->n_eq, bmap->n_ineq);
@@ -1990,6 +2110,15 @@ __isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
 	return isl_basic_map_finalize(res);
 }
 
+__isl_give isl_basic_map *isl_basic_map_add(__isl_take isl_basic_map *bmap,
+		enum isl_dim_type type, unsigned n)
+{
+	if (!bmap)
+		return NULL;
+	return isl_basic_map_insert(bmap, type,
+					isl_basic_map_dim(bmap, type), n);
+}
+
 __isl_give isl_basic_set *isl_basic_set_add(__isl_take isl_basic_set *bset,
 		enum isl_dim_type type, unsigned n)
 {
@@ -2002,8 +2131,8 @@ error:
 	return NULL;
 }
 
-__isl_give isl_map *isl_map_add(__isl_take isl_map *map,
-		enum isl_dim_type type, unsigned n)
+__isl_give isl_map *isl_map_insert(__isl_take isl_map *map,
+		enum isl_dim_type type, unsigned pos, unsigned n)
 {
 	int i;
 
@@ -2014,12 +2143,12 @@ __isl_give isl_map *isl_map_add(__isl_take isl_map *map,
 	if (!map)
 		return NULL;
 
-	map->dim = isl_dim_add(map->dim, type, n);
+	map->dim = isl_dim_insert(map->dim, type, pos, n);
 	if (!map->dim)
 		goto error;
 
 	for (i = 0; i < map->n; ++i) {
-		map->p[i] = isl_basic_map_add(map->p[i], type, n);
+		map->p[i] = isl_basic_map_insert(map->p[i], type, pos, n);
 		if (!map->p[i])
 			goto error;
 	}
@@ -2030,6 +2159,14 @@ error:
 	return NULL;
 }
 
+__isl_give isl_map *isl_map_add(__isl_take isl_map *map,
+		enum isl_dim_type type, unsigned n)
+{
+	if (!map)
+		return NULL;
+	return isl_map_insert(map, type, isl_map_dim(map, type), n);
+}
+
 __isl_give isl_set *isl_set_add(__isl_take isl_set *set,
 		enum isl_dim_type type, unsigned n)
 {
@@ -2042,95 +2179,323 @@ error:
 	return NULL;
 }
 
-/* Turn final n dimensions into existentially quantified variables.
- */
-struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
-		enum isl_dim_type type, unsigned first, 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)
 {
 	int i;
-	size_t row_size;
-	isl_int **new_div;
-	isl_int *old;
+	struct isl_dim_map *dim_map;
+	struct isl_basic_map *res;
+	enum isl_dim_type t;
+	unsigned total, off;
 
-	if (!bset)
+	if (!bmap)
 		return NULL;
+	if (n == 0)
+		return bmap;
+
+	isl_assert(bmap->ctx, src_pos + n <= isl_basic_map_dim(bmap, src_type),
+		goto error);
 
-	isl_assert(bset->ctx, type == isl_dim_set, goto error);
-	isl_assert(bset->ctx, first + n == isl_basic_set_n_dim(bset), goto error);
+	if (dst_type == src_type && dst_pos == src_pos)
+		return bmap;
 
-	if (n == 0)
-		return bset;
+	isl_assert(bmap->ctx, dst_type != src_type, goto error);
 
-	if (ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL))
-		return isl_basic_set_remove(bset, type, first, n);
+	if (pos(bmap->dim, dst_type) + dst_pos ==
+	    pos(bmap->dim, src_type) + src_pos +
+					    ((src_type < dst_type) ? n : 0)) {
+		bmap = isl_basic_map_cow(bmap);
+		if (!bmap)
+			return NULL;
 
-	bset = isl_basic_set_cow(bset);
+		bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
+						src_type, src_pos, n);
+		if (!bmap->dim)
+			goto error;
 
-	row_size = 1 + isl_dim_total(bset->dim) + bset->extra;
-	old = bset->block2.data;
-	bset->block2 = isl_blk_extend(bset->ctx, bset->block2,
-					(bset->extra + n) * (1 + row_size));
-	if (!bset->block2.data)
-		goto error;
-	new_div = isl_alloc_array(ctx, isl_int *, bset->extra + n);
-	if (!new_div)
-		goto error;
-	for (i = 0; i < n; ++i) {
-		new_div[i] = bset->block2.data +
-				(bset->extra + i) * (1 + row_size);
-		isl_seq_clr(new_div[i], 1 + row_size);
+		bmap = isl_basic_map_finalize(bmap);
+
+		return bmap;
 	}
-	for (i = 0; i < bset->extra; ++i)
-		new_div[n + i] = bset->block2.data + (bset->div[i] - old);
-	free(bset->div);
-	bset->div = new_div;
-	bset->n_div += n;
-	bset->extra += n;
-	bset->dim = isl_dim_drop_outputs(bset->dim,
-					    isl_basic_set_n_dim(bset) - n, n);
-	if (!bset->dim)
+
+	total = isl_basic_map_total_dim(bmap);
+	dim_map = isl_dim_map_alloc(bmap->ctx, total);
+
+	off = 0;
+	for (t = isl_dim_param; t <= isl_dim_out; ++t) {
+		unsigned size = isl_dim_size(bmap->dim, t);
+		if (t == dst_type) {
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					    0, dst_pos, off);
+			off += dst_pos;
+			isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
+					    src_pos, n, off);
+			off += n;
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					    dst_pos, size - dst_pos, off);
+			off += size - dst_pos;
+		} else if (t == src_type) {
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					    0, src_pos, off);
+			off += src_pos;
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					src_pos + n, size - src_pos - n, off);
+			off += size - src_pos - n;
+		} else {
+			isl_dim_map_dim(dim_map, bmap->dim, t, off);
+			off += size;
+		}
+	}
+	isl_dim_map_div(dim_map, bmap, off);
+
+	res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
+			bmap->n_div, bmap->n_eq, bmap->n_ineq);
+	bmap = add_constraints_dim_map(res, bmap, dim_map);
+
+	bmap->dim = isl_dim_move(bmap->dim, dst_type, dst_pos,
+					src_type, src_pos, n);
+	if (!bmap->dim)
 		goto error;
-	bset = isl_basic_set_simplify(bset);
-	bset = isl_basic_set_drop_redundant_divs(bset);
-	return isl_basic_set_finalize(bset);
+
+	ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
+	bmap = isl_basic_map_gauss(bmap, NULL);
+	bmap = isl_basic_map_finalize(bmap);
+
+	return bmap;
 error:
-	isl_basic_set_free(bset);
+	isl_basic_map_free(bmap);
 	return NULL;
 }
 
-/* Turn final n dimensions 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)
+__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)
 {
-	int i;
+	return (isl_basic_set *)isl_basic_map_move_dims(
+		(isl_basic_map *)bset, dst_type, dst_pos, src_type, src_pos, 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)
+{
 	if (!set)
 		return NULL;
+	isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
+	return (isl_set *)isl_map_move_dims((isl_map *)set, dst_type, dst_pos,
+					src_type, src_pos, n);
+error:
+	isl_set_free(set);
+	return NULL;
+}
 
-	isl_assert(set->ctx, type == isl_dim_set, goto error);
-	isl_assert(set->ctx, first + n == isl_set_n_dim(set), goto error);
+__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)
+{
+	int i;
 
-	set = isl_set_cow(set);
-	if (!set)
+	if (!map)
+		return NULL;
+	if (n == 0)
+		return map;
+
+	isl_assert(map->ctx, src_pos + n <= isl_map_dim(map, src_type),
+		goto error);
+
+	if (dst_type == src_type && dst_pos == src_pos)
+		return map;
+
+	isl_assert(map->ctx, dst_type != src_type, goto error);
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	map->dim = isl_dim_move(map->dim, dst_type, dst_pos, src_type, src_pos, n);
+	if (!map->dim)
 		goto error;
-	set->dim = isl_dim_drop_outputs(set->dim, first, n);
-	for (i = 0; i < set->n; ++i) {
-		set->p[i] = isl_basic_set_project_out(set->p[i], type, first, n);
-		if (!set->p[i])
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_move_dims(map->p[i],
+						dst_type, dst_pos,
+						src_type, src_pos, n);
+		if (!map->p[i])
 			goto error;
 	}
 
-	ISL_F_CLR(set, ISL_SET_NORMALIZED);
-	return set;
+	return map;
 error:
-	isl_set_free(set);
+	isl_map_free(map);
 	return NULL;
 }
 
-static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, 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)
 {
-	int i, j;
+	struct isl_dim_map *dim_map;
+	struct isl_basic_map *res;
+	enum isl_dim_type t;
+	unsigned total, off;
+
+	if (!bmap)
+		return NULL;
+	if (pos(bmap->dim, type) + first + n == 1 + isl_dim_total(bmap->dim))
+		return bmap;
+
+	total = isl_basic_map_total_dim(bmap);
+	dim_map = isl_dim_map_alloc(bmap->ctx, total);
+
+	off = 0;
+	for (t = isl_dim_param; t <= isl_dim_out; ++t) {
+		unsigned size = isl_dim_size(bmap->dim, t);
+		if (t == type) {
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					    0, first, off);
+			off += first;
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					    first, n, total - bmap->n_div - n);
+			isl_dim_map_dim_range(dim_map, bmap->dim, t,
+					    first + n, size - (first + n), off);
+			off += size - (first + n);
+		} else {
+			isl_dim_map_dim(dim_map, bmap->dim, t, off);
+			off += size;
+		}
+	}
+	isl_dim_map_div(dim_map, bmap, off + n);
+
+	res = isl_basic_map_alloc_dim(isl_basic_map_get_dim(bmap),
+			bmap->n_div, bmap->n_eq, bmap->n_ineq);
+	res = add_constraints_dim_map(res, bmap, dim_map);
+	return res;
+}
+
+/* Turn the n dimensions of type type, starting at first
+ * into existentially quantified variables.
+ */
+__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)
+{
+	int i;
+	size_t row_size;
+	isl_int **new_div;
+	isl_int *old;
+
+	if (n == 0)
+		return bmap;
+
+	if (!bmap)
+		return NULL;
+
+	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
+		return isl_basic_map_remove(bmap, type, first, n);
+
+	isl_assert(bmap->ctx, first + n <= isl_basic_map_dim(bmap, type),
+			goto error);
+
+	bmap = move_last(bmap, type, first, n);
+	bmap = isl_basic_map_cow(bmap);
+	if (!bmap)
+		return NULL;
+
+	row_size = 1 + isl_dim_total(bmap->dim) + bmap->extra;
+	old = bmap->block2.data;
+	bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
+					(bmap->extra + n) * (1 + row_size));
+	if (!bmap->block2.data)
+		goto error;
+	new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
+	if (!new_div)
+		goto error;
+	for (i = 0; i < n; ++i) {
+		new_div[i] = bmap->block2.data +
+				(bmap->extra + i) * (1 + row_size);
+		isl_seq_clr(new_div[i], 1 + row_size);
+	}
+	for (i = 0; i < bmap->extra; ++i)
+		new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
+	free(bmap->div);
+	bmap->div = new_div;
+	bmap->n_div += n;
+	bmap->extra += n;
+
+	bmap->dim = isl_dim_drop(bmap->dim, type, first, n);
+	if (!bmap->dim)
+		goto error;
+	bmap = isl_basic_map_simplify(bmap);
+	bmap = isl_basic_map_drop_redundant_divs(bmap);
+	return isl_basic_map_finalize(bmap);
+error:
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
+/* Turn the n dimensions of type type, starting at first
+ * into existentially quantified variables.
+ */
+struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
+		enum isl_dim_type type, unsigned first, unsigned n)
+{
+	return (isl_basic_set *)isl_basic_map_project_out(
+			(isl_basic_map *)bset, type, first, 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)
+{
+	int i;
+
+	if (!map)
+		return NULL;
+
+	if (n == 0)
+		return map;
+
+	isl_assert(map->ctx, first + n <= isl_map_dim(map, type), goto error);
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	map->dim = isl_dim_drop(map->dim, type, first, n);
+	if (!map->dim)
+		goto error;
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
+		if (!map->p[i])
+			goto error;
+	}
+
+	return map;
+error:
+	isl_map_free(map);
+	return NULL;
+}
+
+/* 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)
+{
+	return (isl_set *)isl_map_project_out((isl_map *)set, type, first, n);
+}
+
+static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
+{
+	int i, j;
 
 	for (i = 0; i < n; ++i) {
 		j = isl_basic_map_alloc_div(bmap);
@@ -2327,6 +2692,12 @@ error:
 	return NULL;
 }
 
+__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
+	__isl_take isl_set *set2)
+{
+	return (isl_set *)isl_map_sum((isl_map *)set1, (isl_map *)set2);
+}
+
 /* Given a basic map A -> f(A), construct A -> -f(A).
  */
 struct isl_basic_map *isl_basic_map_neg(struct isl_basic_map *bmap)
@@ -2374,6 +2745,11 @@ error:
 	return NULL;
 }
 
+__isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
+{
+	return (isl_set *)isl_map_neg((isl_map *)set);
+}
+
 /* Given a basic map A -> f(A) and an integer d, construct a basic map
  * A -> floor(f(A)/d).
  */
@@ -2496,6 +2872,29 @@ error:
 	return NULL;
 }
 
+/* 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)
+{
+	int i;
+	unsigned nparam;
+	unsigned n_in;
+
+	i = isl_basic_map_alloc_inequality(bmap);
+	if (i < 0)
+		goto error;
+	nparam = isl_basic_map_n_param(bmap);
+	n_in = isl_basic_map_n_in(bmap);
+	isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
+	isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
+	isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
+	return isl_basic_map_finalize(bmap);
+error:
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
 /* Add a constraints to "bmap" expressing i_pos > o_pos
  */
 static struct isl_basic_map *var_more(struct isl_basic_map *bmap, unsigned pos)
@@ -2519,6 +2918,29 @@ error:
 	return NULL;
 }
 
+/* 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)
+{
+	int i;
+	unsigned nparam;
+	unsigned n_in;
+
+	i = isl_basic_map_alloc_inequality(bmap);
+	if (i < 0)
+		goto error;
+	nparam = isl_basic_map_n_param(bmap);
+	n_in = isl_basic_map_n_in(bmap);
+	isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
+	isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
+	isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
+	return isl_basic_map_finalize(bmap);
+error:
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
 struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
 {
 	int i;
@@ -2531,7 +2953,7 @@ struct isl_basic_map *isl_basic_map_equal(struct isl_dim *dim, unsigned n_equal)
 	return isl_basic_map_finalize(bmap);
 }
 
-/* Return a relation on pairs of sets of dimension "dim" expressing i_pos < o_pos
+/* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
  */
 struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
 {
@@ -2547,6 +2969,21 @@ struct isl_basic_map *isl_basic_map_less_at(struct isl_dim *dim, unsigned pos)
 	return isl_basic_map_finalize(bmap);
 }
 
+/* Return a relation on of dimension "dim" expressing i_[0..pos] <<= o_[0..pos]
+ */
+__isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
+	__isl_take isl_dim *dim, unsigned pos)
+{
+	int i;
+	isl_basic_map *bmap;
+
+	bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
+	for (i = 0; i < pos; ++i)
+		bmap = var_equal(bmap, i);
+	bmap = var_less_or_equal(bmap, pos);
+	return isl_basic_map_finalize(bmap);
+}
+
 /* Return a relation on pairs of sets of dimension "dim" expressing i_pos > o_pos
  */
 struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
@@ -2563,28 +3000,65 @@ struct isl_basic_map *isl_basic_map_more_at(struct isl_dim *dim, unsigned pos)
 	return isl_basic_map_finalize(bmap);
 }
 
-static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
+/* Return a relation on of dimension "dim" expressing i_[0..pos] >>= o_[0..pos]
+ */
+__isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
+	__isl_take isl_dim *dim, unsigned pos)
+{
+	int i;
+	isl_basic_map *bmap;
+
+	bmap = isl_basic_map_alloc_dim(dim, 0, pos, 1);
+	for (i = 0; i < pos; ++i)
+		bmap = var_equal(bmap, i);
+	bmap = var_more_or_equal(bmap, pos);
+	return isl_basic_map_finalize(bmap);
+}
+
+static __isl_give isl_map *map_lex_lte_first(__isl_take isl_dim *dims,
+	unsigned n, int equal)
 {
 	struct isl_map *map;
-	unsigned dim;
 	int i;
 
-	if (!dims)
-		return NULL;
-	dim = dims->n_out;
-	map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT);
+	if (n == 0 && equal)
+		return isl_map_universe(dims);
+
+	map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
 
-	for (i = 0; i < dim; ++i)
+	for (i = 0; i + 1 < n; ++i)
 		map = isl_map_add_basic_map(map,
 				  isl_basic_map_less_at(isl_dim_copy(dims), i));
-	if (equal)
-		map = isl_map_add_basic_map(map,
-				  isl_basic_map_equal(isl_dim_copy(dims), dim));
+	if (n > 0) {
+		if (equal)
+			map = isl_map_add_basic_map(map,
+			      isl_basic_map_less_or_equal_at(dims, n - 1));
+		else
+			map = isl_map_add_basic_map(map,
+			      isl_basic_map_less_at(dims, n - 1));
+	} else
+		isl_dim_free(dims);
 
-	isl_dim_free(dims);
 	return map;
 }
 
+static __isl_give isl_map *map_lex_lte(__isl_take isl_dim *dims, int equal)
+{
+	if (!dims)
+		return NULL;
+	return map_lex_lte_first(dims, dims->n_out, equal);
+}
+
+__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_dim *dim, unsigned n)
+{
+	return map_lex_lte_first(dim, n, 0);
+}
+
+__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_dim *dim, unsigned n)
+{
+	return map_lex_lte_first(dim, n, 1);
+}
+
 __isl_give isl_map *isl_map_lex_lt(__isl_take isl_dim *set_dim)
 {
 	return map_lex_lte(isl_dim_map(set_dim), 0);
@@ -2595,28 +3069,50 @@ __isl_give isl_map *isl_map_lex_le(__isl_take isl_dim *set_dim)
 	return map_lex_lte(isl_dim_map(set_dim), 1);
 }
 
-static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
+static __isl_give isl_map *map_lex_gte_first(__isl_take isl_dim *dims,
+	unsigned n, int equal)
 {
 	struct isl_map *map;
-	unsigned dim;
 	int i;
 
-	if (!dims)
-		return NULL;
-	dim = dims->n_out;
-	map = isl_map_alloc_dim(isl_dim_copy(dims), dim + equal, ISL_MAP_DISJOINT);
+	if (n == 0 && equal)
+		return isl_map_universe(dims);
+
+	map = isl_map_alloc_dim(isl_dim_copy(dims), n, ISL_MAP_DISJOINT);
 
-	for (i = 0; i < dim; ++i)
+	for (i = 0; i + 1 < n; ++i)
 		map = isl_map_add_basic_map(map,
 				  isl_basic_map_more_at(isl_dim_copy(dims), i));
-	if (equal)
-		map = isl_map_add_basic_map(map,
-				  isl_basic_map_equal(isl_dim_copy(dims), dim));
+	if (n > 0) {
+		if (equal)
+			map = isl_map_add_basic_map(map,
+			      isl_basic_map_more_or_equal_at(dims, n - 1));
+		else
+			map = isl_map_add_basic_map(map,
+			      isl_basic_map_more_at(dims, n - 1));
+	} else
+		isl_dim_free(dims);
 
-	isl_dim_free(dims);
 	return map;
 }
 
+static __isl_give isl_map *map_lex_gte(__isl_take isl_dim *dims, int equal)
+{
+	if (!dims)
+		return NULL;
+	return map_lex_gte_first(dims, dims->n_out, equal);
+}
+
+__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_dim *dim, unsigned n)
+{
+	return map_lex_gte_first(dim, n, 0);
+}
+
+__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_dim *dim, unsigned n)
+{
+	return map_lex_gte_first(dim, n, 1);
+}
+
 __isl_give isl_map *isl_map_lex_gt(__isl_take isl_dim *set_dim)
 {
 	return map_lex_gte(isl_dim_map(set_dim), 0);
@@ -2677,27 +3173,43 @@ error:
  *
  *		f - m d >= n
  */
-int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
+int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
+	unsigned pos, isl_int *div)
 {
 	int i, j;
 	unsigned total = isl_basic_map_total_dim(bmap);
-	unsigned div_pos = 1 + total - bmap->n_div + div;
 
 	i = isl_basic_map_alloc_inequality(bmap);
 	if (i < 0)
 		return -1;
-	isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total);
-	isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]);
+	isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
+	isl_int_neg(bmap->ineq[i][1 + pos], div[0]);
 
 	j = isl_basic_map_alloc_inequality(bmap);
 	if (j < 0)
 		return -1;
 	isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
-	isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]);
+	isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][1 + pos]);
 	isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
 	return j;
 }
 
+int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
+	unsigned pos, isl_int *div)
+{
+	return isl_basic_map_add_div_constraints_var((isl_basic_map *)bset,
+							pos, div);
+}
+
+int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
+{
+	unsigned total = isl_basic_map_total_dim(bmap);
+	unsigned div_pos = total - bmap->n_div + div;
+
+	return isl_basic_map_add_div_constraints_var(bmap, div_pos,
+							bmap->div[div]);
+}
+
 struct isl_basic_set *isl_basic_map_underlying_set(
 		struct isl_basic_map *bmap)
 {
@@ -2873,17 +3385,80 @@ struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
 	return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
 }
 
+static __isl_give isl_basic_map *isl_basic_map_reset_dim(
+	__isl_take isl_basic_map *bmap, __isl_take isl_dim *dim)
+{
+	bmap = isl_basic_map_cow(bmap);
+	if (!bmap || !dim)
+		goto error;
+
+	isl_dim_free(bmap->dim);
+	bmap->dim = dim;
+
+	return bmap;
+error:
+	isl_basic_map_free(bmap);
+	isl_dim_free(dim);
+	return NULL;
+}
+
+static __isl_give isl_basic_set *isl_basic_set_reset_dim(
+	__isl_take isl_basic_set *bset, __isl_take isl_dim *dim)
+{
+	return (isl_basic_set *)isl_basic_map_reset_dim((isl_basic_map *)bset,
+							dim);
+}
+
+__isl_give isl_map *isl_map_reset_dim(__isl_take isl_map *map,
+	__isl_take isl_dim *dim)
+{
+	int i;
+
+	map = isl_map_cow(map);
+	if (!map || !dim)
+		goto error;
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_reset_dim(map->p[i],
+						    isl_dim_copy(dim));
+		if (!map->p[i])
+			goto error;
+	}
+	isl_dim_free(map->dim);
+	map->dim = dim;
+
+	return map;
+error:
+	isl_map_free(map);
+	isl_dim_free(dim);
+	return NULL;
+}
+
+__isl_give isl_set *isl_set_reset_dim(__isl_take isl_set *set,
+	__isl_take isl_dim *dim)
+{
+	return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
+}
+
 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
 {
+	isl_dim *dim;
 	struct isl_basic_set *domain;
 	unsigned n_in;
 	unsigned n_out;
+
 	if (!bmap)
 		return NULL;
+	dim = isl_dim_domain(isl_basic_map_get_dim(bmap));
+
 	n_in = isl_basic_map_n_in(bmap);
 	n_out = isl_basic_map_n_out(bmap);
 	domain = isl_basic_set_from_basic_map(bmap);
-	return isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
+	domain = isl_basic_set_project_out(domain, isl_dim_set, n_in, n_out);
+
+	domain = isl_basic_set_reset_dim(domain, dim);
+
+	return domain;
 }
 
 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
@@ -2898,16 +3473,17 @@ struct isl_set *isl_map_range(struct isl_map *map)
 
 	if (!map)
 		goto error;
+	if (isl_map_dim(map, isl_dim_in) == 0)
+		return (isl_set *)map;
+
 	map = isl_map_cow(map);
 	if (!map)
 		goto error;
 
 	set = (struct isl_set *) map;
-	if (set->dim->n_in != 0) {
-		set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
-		if (!set->dim)
-			goto error;
-	}
+	set->dim = isl_dim_drop_inputs(set->dim, 0, set->dim->n_in);
+	if (!set->dim)
+		goto error;
 	for (i = 0; i < map->n; ++i) {
 		set->p[i] = isl_basic_map_range(map->p[i]);
 		if (!set->p[i])
@@ -2953,14 +3529,14 @@ struct isl_map *isl_map_from_range(struct isl_set *set)
 
 __isl_give isl_map *isl_map_from_domain(__isl_take isl_set *set)
 {
-	return isl_map_reverse(isl_map_from_range(set));;
+	return isl_map_reverse(isl_map_from_range(set));
 }
 
 __isl_give isl_map *isl_map_from_domain_and_range(__isl_take isl_set *domain,
 	__isl_take isl_set *range)
 {
-	return isl_map_product(isl_map_from_domain(domain),
-			       isl_map_from_range(range));
+	return isl_map_apply_range(isl_map_from_domain(domain),
+				   isl_map_from_range(range));
 }
 
 struct isl_set *isl_set_from_map(struct isl_map *map)
@@ -3374,6 +3950,13 @@ error:
 	return NULL;
 }
 
+__isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
+		enum isl_dim_type type, unsigned pos, int value)
+{
+	return (struct isl_set *)
+		isl_map_fix_si((struct isl_map *)set, type, pos, value);
+}
+
 __isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
 		enum isl_dim_type type, unsigned pos, isl_int value)
 {
@@ -3414,6 +3997,31 @@ struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
 		isl_map_fix_si((struct isl_map *)set, isl_dim_set, dim, value);
 }
 
+__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)
+{
+	int j;
+
+	if (!bmap)
+		return NULL;
+	isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), goto error);
+	pos += isl_basic_map_offset(bmap, type);
+	bmap = isl_basic_map_cow(bmap);
+	bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
+	j = isl_basic_map_alloc_inequality(bmap);
+	if (j < 0)
+		goto error;
+	isl_seq_clr(bmap->ineq[j], 1 + isl_basic_map_total_dim(bmap));
+	isl_int_set_si(bmap->ineq[j][pos], 1);
+	isl_int_set_si(bmap->ineq[j][0], -value);
+	bmap = isl_basic_map_simplify(bmap);
+	return isl_basic_map_finalize(bmap);
+error:
+	isl_basic_map_free(bmap);
+	return NULL;
+}
+
 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
 	unsigned dim, isl_int value)
 {
@@ -3434,6 +4042,36 @@ error:
 	return NULL;
 }
 
+__isl_give isl_map *isl_map_lower_bound_si(__isl_take isl_map *map,
+		enum isl_dim_type type, unsigned pos, int value)
+{
+	int i;
+
+	map = isl_map_cow(map);
+	if (!map)
+		return NULL;
+
+	isl_assert(map->ctx, pos < isl_map_dim(map, type), goto error);
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_lower_bound_si(map->p[i],
+							 type, pos, value);
+		if (!map->p[i])
+			goto error;
+	}
+	ISL_F_CLR(map, ISL_MAP_NORMALIZED);
+	return map;
+error:
+	isl_map_free(map);
+	return NULL;
+}
+
+__isl_give isl_set *isl_set_lower_bound_si(__isl_take isl_set *set,
+		enum isl_dim_type type, unsigned pos, int value)
+{
+	return (struct isl_set *)
+		isl_map_lower_bound_si((struct isl_map *)set, type, pos, value);
+}
+
 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
 					isl_int value)
 {
@@ -3763,42 +4401,14 @@ __isl_give isl_map *isl_map_lexmax(__isl_take isl_map *map)
 	return isl_map_lexopt(map, 1);
 }
 
-__isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
-{
-	return (isl_set *)isl_map_lexmin((isl_map *)set);
-}
-
-__isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
-{
-	return (isl_set *)isl_map_lexmax((isl_map *)set);
-}
-
-static struct isl_map *isl_map_reset_dim(struct isl_map *map,
-	struct isl_dim *dim)
-{
-	int i;
-
-	if (!map || !dim)
-		goto error;
-
-	for (i = 0; i < map->n; ++i) {
-		isl_dim_free(map->p[i]->dim);
-		map->p[i]->dim = isl_dim_copy(dim);
-	}
-	isl_dim_free(map->dim);
-	map->dim = dim;
-
-	return map;
-error:
-	isl_map_free(map);
-	isl_dim_free(dim);
-	return NULL;
-}
-
-static struct isl_set *isl_set_reset_dim(struct isl_set *set,
-	struct isl_dim *dim)
+__isl_give isl_set *isl_set_lexmin(__isl_take isl_set *set)
 {
-	return (struct isl_set *) isl_map_reset_dim((struct isl_map *)set, dim);
+	return (isl_set *)isl_map_lexmin((isl_map *)set);
+}
+
+__isl_give isl_set *isl_set_lexmax(__isl_take isl_set *set)
+{
+	return (isl_set *)isl_map_lexmax((isl_map *)set);
 }
 
 /* Apply a preimage specified by "mat" on the parameters of "bset".
@@ -3904,6 +4514,9 @@ static struct isl_basic_set *basic_set_append_equalities(
 	}
 	isl_mat_free(eq);
 
+	bset = isl_basic_set_gauss(bset, NULL);
+	bset = isl_basic_set_finalize(bset);
+
 	return bset;
 error:
 	isl_mat_free(eq);
@@ -3979,6 +4592,13 @@ static struct isl_set *parameter_compute_divs(struct isl_basic_set *bset)
 		0, 1 + nparam);
 	eq = isl_mat_cow(eq);
 	T = isl_mat_variable_compression(isl_mat_copy(eq), &T2);
+	if (T && T->n_col == 0) {
+		isl_mat_free(T);
+		isl_mat_free(T2);
+		isl_mat_free(eq);
+		bset = isl_basic_set_set_to_empty(bset);
+		return isl_set_from_basic_set(bset);
+	}
 	bset = basic_set_parameter_preimage(bset, T);
 
 	set = isl_basic_set_lexmin(bset);
@@ -4342,6 +4962,7 @@ error:
  */
 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
 {
+	isl_dim *dims;
 	struct isl_basic_set *bset;
 	unsigned dim;
 	unsigned nparam;
@@ -4354,7 +4975,9 @@ struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
 	isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
 	bset = isl_basic_set_from_basic_map(bmap);
 	bset = isl_basic_set_cow(bset);
-	bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
+	dims = isl_basic_set_get_dim(bset);
+	dims = isl_dim_add(dims, isl_dim_set, dim);
+	bset = isl_basic_set_extend_dim(bset, dims, 0, dim, 0);
 	bset = isl_basic_set_swap_vars(bset, 2*dim);
 	for (i = 0; i < dim; ++i) {
 		int j = isl_basic_map_alloc_equality(
@@ -4378,14 +5001,16 @@ error:
 struct isl_set *isl_map_deltas(struct isl_map *map)
 {
 	int i;
+	isl_dim *dim;
 	struct isl_set *result;
 
 	if (!map)
 		return NULL;
 
 	isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
-	result = isl_set_alloc(map->ctx, isl_map_n_param(map),
-					isl_map_n_in(map), map->n, map->flags);
+	dim = isl_map_get_dim(map);
+	dim = isl_dim_domain(dim);
+	result = isl_set_alloc_dim(dim, map->n, map->flags);
 	if (!result)
 		goto error;
 	for (i = 0; i < map->n; ++i)
@@ -4507,6 +5132,50 @@ error:
 	return NULL;
 }
 
+__isl_give isl_set *isl_set_split_dims(__isl_take isl_set *set,
+	enum isl_dim_type type, unsigned first, unsigned n)
+{
+	int i;
+	isl_basic_set *nonneg = NULL;
+	isl_basic_set *neg = NULL;
+
+	if (!set)
+		return NULL;
+	if (n == 0)
+		return set;
+
+	isl_assert(set->ctx, first + n <= isl_set_dim(set, type), goto error);
+
+	for (i = 0; i < n; ++i) {
+		int k;
+
+		neg = NULL;
+		nonneg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
+		k = isl_basic_set_alloc_inequality(nonneg);
+		if (k < 0)
+			goto error;
+		isl_seq_clr(nonneg->ineq[k], 1 + isl_basic_set_total_dim(nonneg));
+		isl_int_set_si(nonneg->ineq[k][pos(set->dim, type) + first + i], 1);
+
+		neg = isl_basic_set_alloc_dim(isl_set_get_dim(set), 0, 0, 1);
+		k = isl_basic_set_alloc_inequality(neg);
+		if (k < 0)
+			goto error;
+		isl_seq_clr(neg->ineq[k], 1 + isl_basic_set_total_dim(neg));
+		isl_int_set_si(neg->ineq[k][0], -1);
+		isl_int_set_si(neg->ineq[k][pos(set->dim, type) + first + i], -1);
+
+		set = isl_set_intersect(set, isl_basic_set_union(nonneg, neg));
+	}
+
+	return set;
+error:
+	isl_basic_set_free(nonneg);
+	isl_basic_set_free(neg);
+	isl_set_free(set);
+	return NULL;
+}
+
 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
 {
 	return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
@@ -4573,12 +5242,12 @@ int isl_map_is_empty(struct isl_map *map)
 
 int isl_map_fast_is_empty(struct isl_map *map)
 {
-	return map->n == 0;
+	return map ? map->n == 0 : -1;
 }
 
 int isl_set_fast_is_empty(struct isl_set *set)
 {
-	return set->n == 0;
+	return set ? set->n == 0 : -1;
 }
 
 int isl_set_is_empty(struct isl_set *set)
@@ -4651,10 +5320,23 @@ int isl_basic_set_is_universe(struct isl_basic_set *bset)
 
 int isl_map_fast_is_universe(__isl_keep isl_map *map)
 {
+	int i;
+
 	if (!map)
 		return -1;
 
-	return map->n == 1 && isl_basic_map_is_universe(map->p[0]);
+	for (i = 0; i < map->n; ++i) {
+		int r = isl_basic_map_is_universe(map->p[i]);
+		if (r < 0 || r)
+			return r;
+	}
+
+	return 0;
+}
+
+int isl_set_fast_is_universe(__isl_keep isl_set *set)
+{
+	return isl_map_fast_is_universe((isl_map *) set);
 }
 
 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
@@ -4672,7 +5354,7 @@ int isl_basic_map_is_empty(struct isl_basic_map *bmap)
 
 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
 		struct isl_basic_map *copy = isl_basic_map_copy(bmap);
-		copy = isl_basic_map_convex_hull(copy);
+		copy = isl_basic_map_remove_redundancies(copy);
 		empty = ISL_F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
 		isl_basic_map_free(copy);
 		return empty;
@@ -4755,7 +5437,12 @@ struct isl_set *isl_basic_set_union(
 struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap)
 {
 	int i;
-	unsigned off = isl_dim_total(bmap->dim);
+	unsigned off;
+
+	if (!bmap)
+		return NULL;
+
+	off = isl_dim_total(bmap->dim);
 
 	for (i = 0; i < bmap->n_div; ++i) {
 		int pos;
@@ -4777,6 +5464,25 @@ struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset)
 		isl_basic_map_order_divs((struct isl_basic_map *)bset);
 }
 
+__isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map)
+{
+	int i;
+
+	if (!map)
+		return 0;
+
+	for (i = 0; i < map->n; ++i) {
+		map->p[i] = isl_basic_map_order_divs(map->p[i]);
+		if (!map->p[i])
+			goto error;
+	}
+
+	return map;
+error:
+	isl_map_free(map);
+	return NULL;
+}
+
 /* 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.
  * 
@@ -5363,13 +6069,20 @@ error:
 	return NULL;
 }
 
+__isl_give isl_basic_set *isl_basic_set_sort_constraints(
+	__isl_take isl_basic_set *bset)
+{
+	return (struct isl_basic_set *)isl_basic_map_sort_constraints(
+						(struct isl_basic_map *)bset);
+}
+
 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
 {
 	if (!bmap)
 		return NULL;
 	if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
 		return bmap;
-	bmap = isl_basic_map_convex_hull(bmap);
+	bmap = isl_basic_map_remove_redundancies(bmap);
 	bmap = isl_basic_map_sort_constraints(bmap);
 	ISL_F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
 	return bmap;
@@ -5381,8 +6094,8 @@ struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
 						(struct isl_basic_map *)bset);
 }
 
-static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
-	const struct isl_basic_map *bmap2)
+int isl_basic_map_fast_cmp(const __isl_keep isl_basic_map *bmap1,
+	const __isl_keep isl_basic_map *bmap2)
 {
 	int i, cmp;
 	unsigned total;
@@ -5427,12 +6140,19 @@ static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
 	return 0;
 }
 
-static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
-	struct isl_basic_map *bmap2)
+int isl_basic_map_fast_is_equal(__isl_keep isl_basic_map *bmap1,
+	__isl_keep isl_basic_map *bmap2)
 {
 	return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
 }
 
+int isl_basic_set_fast_is_equal(__isl_keep isl_basic_set *bset1,
+	__isl_keep isl_basic_set *bset2)
+{
+	return isl_basic_map_fast_is_equal((isl_basic_map *)bset1,
+					    (isl_basic_map *)bset2);
+}
+
 static int qsort_bmap_cmp(const void *p1, const void *p2)
 {
 	const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
@@ -5835,6 +6555,73 @@ int isl_set_foreach_basic_set(__isl_keep isl_set *set,
 	return 0;
 }
 
+__isl_give isl_basic_set *isl_basic_set_lift(__isl_take isl_basic_set *bset)
+{
+	struct isl_dim *dim;
+
+	if (!bset)
+		return NULL;
+
+	if (bset->n_div == 0)
+		return bset;
+
+	bset = isl_basic_set_cow(bset);
+	if (!bset)
+		return NULL;
+
+	dim = isl_basic_set_get_dim(bset);
+	dim = isl_dim_add(dim, isl_dim_set, bset->n_div);
+	if (!dim)
+		goto error;
+	isl_dim_free(bset->dim);
+	bset->dim = dim;
+	bset->n_div = 0;
+
+	bset = isl_basic_set_finalize(bset);
+
+	return bset;
+error:
+	isl_basic_set_free(bset);
+	return NULL;
+}
+
+__isl_give isl_set *isl_set_lift(__isl_take isl_set *set)
+{
+	int i;
+	struct isl_dim *dim;
+	unsigned n_div;
+
+	set = isl_set_align_divs(set);
+
+	if (!set)
+		return NULL;
+	if (set->n == 0 || set->p[0]->n_div == 0)
+		return set;
+
+	set = isl_set_cow(set);
+	if (!set)
+		return NULL;
+
+	n_div = set->p[0]->n_div;
+	dim = isl_set_get_dim(set);
+	dim = isl_dim_add(dim, isl_dim_set, n_div);
+	if (!dim)
+		goto error;
+	isl_dim_free(set->dim);
+	set->dim = dim;
+
+	for (i = 0; i < set->n; ++i) {
+		set->p[i] = isl_basic_set_lift(set->p[i]);
+		if (!set->p[i])
+			goto error;
+	}
+
+	return set;
+error:
+	isl_set_free(set);
+	return NULL;
+}
+
 __isl_give isl_map *isl_set_lifting(__isl_take isl_set *set)
 {
 	struct isl_dim *dim;
@@ -5923,3 +6710,255 @@ int isl_set_size(__isl_keep isl_set *set)
 
 	return size;
 }
+
+int isl_basic_map_dim_is_bounded(__isl_keep isl_basic_map *bmap,
+	enum isl_dim_type type, unsigned pos)
+{
+	int i;
+	int lower, upper;
+
+	if (!bmap)
+		return -1;
+
+	isl_assert(bmap->ctx, pos < isl_basic_map_dim(bmap, type), return -1);
+
+	pos += isl_basic_map_offset(bmap, type);
+
+	for (i = 0; i < bmap->n_eq; ++i)
+		if (!isl_int_is_zero(bmap->eq[i][pos]))
+			return 1;
+
+	lower = upper = 0;
+	for (i = 0; i < bmap->n_ineq; ++i) {
+		int sgn = isl_int_sgn(bmap->ineq[i][pos]);
+		if (sgn > 0)
+			lower = 1;
+		if (sgn < 0)
+			upper = 1;
+	}
+
+	return lower && upper;
+}
+
+int isl_map_dim_is_bounded(__isl_keep isl_map *map,
+	enum isl_dim_type type, unsigned pos)
+{
+	int i;
+
+	if (!map)
+		return -1;
+
+	for (i = 0; i < map->n; ++i) {
+		int bounded;
+		bounded = isl_basic_map_dim_is_bounded(map->p[i], type, pos);
+		if (bounded < 0 || !bounded)
+			return bounded;
+	}
+
+	return 1;
+}
+
+/* Return 1 if the specified dim is involved in both an upper bound
+ * and a lower bound.
+ */
+int isl_set_dim_is_bounded(__isl_keep isl_set *set,
+	enum isl_dim_type type, unsigned pos)
+{
+	return isl_map_dim_is_bounded((isl_map *)set, type, 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.
+ */
+int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset,
+	unsigned first, unsigned n, int *signs)
+{
+	isl_vec *bound = NULL;
+	struct isl_tab *tab = NULL;
+	struct isl_tab_undo *snap;
+	int i;
+
+	if (!bset || !signs)
+		return -1;
+
+	bound = isl_vec_alloc(bset->ctx, 1 + isl_basic_set_total_dim(bset));
+	tab = isl_tab_from_basic_set(bset);
+	if (!bound || !tab)
+		goto error;
+
+	isl_seq_clr(bound->el, bound->size);
+	isl_int_set_si(bound->el[0], -1);
+
+	snap = isl_tab_snap(tab);
+	for (i = 0; i < n; ++i) {
+		int empty;
+
+		isl_int_set_si(bound->el[1 + first + i], -1);
+		if (isl_tab_add_ineq(tab, bound->el) < 0)
+			goto error;
+		empty = tab->empty;
+		isl_int_set_si(bound->el[1 + first + i], 0);
+		if (isl_tab_rollback(tab, snap) < 0)
+			goto error;
+
+		if (empty) {
+			signs[i] = 1;
+			continue;
+		}
+
+		isl_int_set_si(bound->el[1 + first + i], 1);
+		if (isl_tab_add_ineq(tab, bound->el) < 0)
+			goto error;
+		empty = tab->empty;
+		isl_int_set_si(bound->el[1 + first + i], 0);
+		if (isl_tab_rollback(tab, snap) < 0)
+			goto error;
+
+		signs[i] = empty ? -1 : 0;
+	}
+
+	isl_tab_free(tab);
+	isl_vec_free(bound);
+	return 0;
+error:
+	isl_tab_free(tab);
+	isl_vec_free(bound);
+	return -1;
+}
+
+int isl_basic_set_dims_get_sign(__isl_keep isl_basic_set *bset,
+	enum isl_dim_type type, unsigned first, unsigned n, int *signs)
+{
+	if (!bset || !signs)
+		return -1;
+	isl_assert(bset->ctx, first + n <= isl_basic_set_dim(bset, type),
+		return -1);
+
+	first += pos(bset->dim, type) - 1;
+	return isl_basic_set_vars_get_sign(bset, first, n, signs);
+}
+
+/* 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.
+ */
+int isl_map_is_single_valued(__isl_keep isl_map *map)
+{
+	isl_map *test;
+	isl_map *id;
+	int sv;
+
+	test = isl_map_reverse(isl_map_copy(map));
+	test = isl_map_apply_range(test, isl_map_copy(map));
+
+	id = isl_map_identity(isl_dim_range(isl_map_get_dim(map)));
+
+	sv = isl_map_is_subset(test, id);
+
+	isl_map_free(test);
+	isl_map_free(id);
+
+	return sv;
+}
+
+int isl_map_is_bijective(__isl_keep isl_map *map)
+{
+	int sv;
+
+	sv = isl_map_is_single_valued(map);
+	if (sv < 0 || !sv)
+		return sv;
+
+	map = isl_map_copy(map);
+	map = isl_map_reverse(map);
+	sv = isl_map_is_single_valued(map);
+	isl_map_free(map);
+
+	return sv;
+}
+
+int isl_set_is_singleton(__isl_keep isl_set *set)
+{
+	return isl_map_is_single_valued((isl_map *)set);
+}
+
+int isl_map_is_translation(__isl_keep isl_map *map)
+{
+	int ok;
+	isl_set *delta;
+
+	delta = isl_map_deltas(isl_map_copy(map));
+	ok = isl_set_is_singleton(delta);
+	isl_set_free(delta);
+
+	return ok;
+}
+
+static int unique(isl_int *p, unsigned pos, unsigned len)
+{
+	if (isl_seq_first_non_zero(p, pos) != -1)
+		return 0;
+	if (isl_seq_first_non_zero(p + pos + 1, len - pos - 1) != -1)
+		return 0;
+	return 1;
+}
+
+int isl_basic_set_is_box(__isl_keep isl_basic_set *bset)
+{
+	int i, j;
+	unsigned nvar;
+	unsigned ovar;
+
+	if (!bset)
+		return -1;
+
+	if (isl_basic_set_dim(bset, isl_dim_div) != 0)
+		return 0;
+
+	nvar = isl_basic_set_dim(bset, isl_dim_set);
+	ovar = isl_dim_offset(bset->dim, isl_dim_set);
+	for (j = 0; j < nvar; ++j) {
+		int lower = 0, upper = 0;
+		for (i = 0; i < bset->n_eq; ++i) {
+			if (isl_int_is_zero(bset->eq[i][1 + ovar + j]))
+				continue;
+			if (!unique(bset->eq[i] + 1 + ovar, j, nvar))
+				return 0;
+			break;
+		}
+		if (i < bset->n_eq)
+			continue;
+		for (i = 0; i < bset->n_ineq; ++i) {
+			if (isl_int_is_zero(bset->ineq[i][1 + ovar + j]))
+				continue;
+			if (!unique(bset->ineq[i] + 1 + ovar, j, nvar))
+				return 0;
+			if (isl_int_is_pos(bset->ineq[i][1 + ovar + j]))
+				lower = 1;
+			else
+				upper = 1;
+		}
+		if (!lower || !upper)
+			return 0;
+	}
+
+	return 1;
+}
+
+int isl_set_is_box(__isl_keep isl_set *set)
+{
+	if (!set)
+		return -1;
+	if (set->n != 1)
+		return 0;
+
+	return isl_basic_set_is_box(set->p[0]);
+}