X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_polynomial.c;h=bc0937dcc377ffbb3d1dcc2ddd3a44799ad3aaba;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=6f3be323d7da05803bbb66f80a1715f4feda8f48;hpb=0880a04a185fbb701aa4ea56cc305c92934da26f;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_polynomial.c b/isl_polynomial.c
index 6f3be32..bc0937d 100644
--- a/isl_polynomial.c
+++ b/isl_polynomial.c
@@ -1,7 +1,7 @@
 /*
  * Copyright 2010      INRIA Saclay
  *
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
  *
  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
@@ -9,23 +9,24 @@
  */
 
 #include <stdlib.h>
+#define ISL_DIM_H
 #include <isl_ctx_private.h>
 #include <isl_map_private.h>
 #include <isl_factorization.h>
 #include <isl/lp.h>
 #include <isl/seq.h>
 #include <isl_union_map_private.h>
+#include <isl_constraint_private.h>
 #include <isl_polynomial_private.h>
 #include <isl_point_private.h>
-#include <isl_dim_private.h>
-#include <isl_div_private.h>
+#include <isl_space_private.h>
 #include <isl_mat_private.h>
 #include <isl_range.h>
 #include <isl_local_space_private.h>
 #include <isl_aff_private.h>
 #include <isl_config.h>
 
-static unsigned pos(__isl_keep isl_dim *dim, enum isl_dim_type type)
+static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
 {
 	switch (type) {
 	case isl_dim_param:	return 0;
@@ -342,37 +343,70 @@ __isl_give struct isl_upoly_rec *isl_upoly_alloc_rec(struct isl_ctx *ctx,
 	return rec;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_reset_dim(
-	__isl_take isl_qpolynomial *qp, __isl_take isl_dim *dim)
+__isl_give isl_qpolynomial *isl_qpolynomial_reset_domain_space(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_space *dim)
 {
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp || !dim)
 		goto error;
 
-	isl_dim_free(qp->dim);
+	isl_space_free(qp->dim);
 	qp->dim = dim;
 
 	return qp;
 error:
 	isl_qpolynomial_free(qp);
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	return NULL;
 }
 
+/* Reset the space of "qp".  This function is called from isl_pw_templ.c
+ * and doesn't know if the space of an element object is represented
+ * directly or through its domain.  It therefore passes along both.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_reset_space_and_domain(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_space *space,
+	__isl_take isl_space *domain)
+{
+	isl_space_free(space);
+	return isl_qpolynomial_reset_domain_space(qp, domain);
+}
+
 isl_ctx *isl_qpolynomial_get_ctx(__isl_keep isl_qpolynomial *qp)
 {
 	return qp ? qp->dim->ctx : NULL;
 }
 
-__isl_give isl_dim *isl_qpolynomial_get_dim(__isl_keep isl_qpolynomial *qp)
+__isl_give isl_space *isl_qpolynomial_get_domain_space(
+	__isl_keep isl_qpolynomial *qp)
+{
+	return qp ? isl_space_copy(qp->dim) : NULL;
+}
+
+__isl_give isl_space *isl_qpolynomial_get_space(__isl_keep isl_qpolynomial *qp)
 {
-	return qp ? isl_dim_copy(qp->dim) : NULL;
+	isl_space *space;
+	if (!qp)
+		return NULL;
+	space = isl_space_copy(qp->dim);
+	space = isl_space_from_domain(space);
+	space = isl_space_add_dims(space, isl_dim_out, 1);
+	return space;
 }
 
+/* Externally, an isl_qpolynomial has a map space, but internally, the
+ * ls field corresponds to the domain of that space.
+ */
 unsigned isl_qpolynomial_dim(__isl_keep isl_qpolynomial *qp,
 	enum isl_dim_type type)
 {
-	return qp ? isl_dim_size(qp->dim, type) : 0;
+	if (!qp)
+		return 0;
+	if (type == isl_dim_out)
+		return 1;
+	if (type == isl_dim_in)
+		type = isl_dim_set;
+	return isl_space_dim(qp->dim, type);
 }
 
 int isl_qpolynomial_is_zero(__isl_keep isl_qpolynomial *qp)
@@ -944,7 +978,7 @@ __isl_give struct isl_upoly *isl_upoly_pow(__isl_take struct isl_upoly *up,
 	return res;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_dim *dim,
+__isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_space *dim,
 	unsigned n_div, __isl_take struct isl_upoly *up)
 {
 	struct isl_qpolynomial *qp = NULL;
@@ -953,7 +987,11 @@ __isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_dim *dim,
 	if (!dim || !up)
 		goto error;
 
-	total = isl_dim_total(dim);
+	if (!isl_space_is_set(dim))
+		isl_die(isl_space_get_ctx(dim), isl_error_invalid,
+			"domain of polynomial should be a set", goto error);
+
+	total = isl_space_dim(dim, isl_dim_all);
 
 	qp = isl_calloc_type(dim->ctx, struct isl_qpolynomial);
 	if (!qp)
@@ -969,7 +1007,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_alloc(__isl_take isl_dim *dim,
 
 	return qp;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	isl_upoly_free(up);
 	isl_qpolynomial_free(qp);
 	return NULL;
@@ -991,7 +1029,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_dup(__isl_keep isl_qpolynomial *qp)
 	if (!qp)
 		return NULL;
 
-	dup = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), qp->div->n_row,
+	dup = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row,
 				    isl_upoly_copy(qp->upoly));
 	if (!dup)
 		return NULL;
@@ -1017,19 +1055,20 @@ __isl_give isl_qpolynomial *isl_qpolynomial_cow(__isl_take isl_qpolynomial *qp)
 	return isl_qpolynomial_dup(qp);
 }
 
-void isl_qpolynomial_free(__isl_take isl_qpolynomial *qp)
+void *isl_qpolynomial_free(__isl_take isl_qpolynomial *qp)
 {
 	if (!qp)
-		return;
+		return NULL;
 
 	if (--qp->ref > 0)
-		return;
+		return NULL;
 
-	isl_dim_free(qp->dim);
+	isl_space_free(qp->dim);
 	isl_mat_free(qp->div);
 	isl_upoly_free(qp->upoly);
 
 	free(qp);
+	return NULL;
 }
 
 __isl_give struct isl_upoly *isl_upoly_var_pow(isl_ctx *ctx, int pos, int power)
@@ -1160,7 +1199,7 @@ static __isl_give isl_qpolynomial *sort_divs(__isl_take isl_qpolynomial *qp)
 	if (qp->div->n_row <= 1)
 		return qp;
 
-	div_pos = isl_dim_total(qp->dim);
+	div_pos = isl_space_dim(qp->dim, isl_dim_all);
 
 	array = isl_alloc_array(qp->div->ctx, struct isl_div_sort_info,
 				qp->div->n_row);
@@ -1329,7 +1368,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_add(__isl_take isl_qpolynomial *qp1,
 	if (qp1->div->n_row < qp2->div->n_row)
 		return isl_qpolynomial_add(qp2, qp1);
 
-	isl_assert(qp1->dim->ctx, isl_dim_equal(qp1->dim, qp2->dim), goto error);
+	isl_assert(qp1->dim->ctx, isl_space_is_equal(qp1->dim, qp2->dim), goto error);
 	if (!compatible_divs(qp1->div, qp2->div))
 		return with_merged_divs(isl_qpolynomial_add, qp1, qp2);
 
@@ -1399,7 +1438,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_mul_isl_int(
 
 	if (qp && isl_int_is_zero(v)) {
 		isl_qpolynomial *zero;
-		zero = isl_qpolynomial_zero(isl_dim_copy(qp->dim));
+		zero = isl_qpolynomial_zero_on_domain(isl_space_copy(qp->dim));
 		isl_qpolynomial_free(qp);
 		return zero;
 	}
@@ -1418,6 +1457,12 @@ error:
 	return NULL;
 }
 
+__isl_give isl_qpolynomial *isl_qpolynomial_scale(
+	__isl_take isl_qpolynomial *qp, isl_int v)
+{
+	return isl_qpolynomial_mul_isl_int(qp, v);
+}
+
 __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1,
 	__isl_take isl_qpolynomial *qp2)
 {
@@ -1429,7 +1474,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1,
 	if (qp1->div->n_row < qp2->div->n_row)
 		return isl_qpolynomial_mul(qp2, qp1);
 
-	isl_assert(qp1->dim->ctx, isl_dim_equal(qp1->dim, qp2->dim), goto error);
+	isl_assert(qp1->dim->ctx, isl_space_is_equal(qp1->dim, qp2->dim), goto error);
 	if (!compatible_divs(qp1->div, qp2->div))
 		return with_merged_divs(isl_qpolynomial_mul, qp1, qp2);
 
@@ -1464,42 +1509,69 @@ error:
 	return NULL;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_zero(__isl_take isl_dim *dim)
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_pow(
+	__isl_take isl_pw_qpolynomial *pwqp, unsigned power)
+{
+	int i;
+
+	if (power == 1)
+		return pwqp;
+
+	pwqp = isl_pw_qpolynomial_cow(pwqp);
+	if (!pwqp)
+		return NULL;
+
+	for (i = 0; i < pwqp->n; ++i) {
+		pwqp->p[i].qp = isl_qpolynomial_pow(pwqp->p[i].qp, power);
+		if (!pwqp->p[i].qp)
+			return isl_pw_qpolynomial_free(pwqp);
+	}
+
+	return pwqp;
+}
+
+__isl_give isl_qpolynomial *isl_qpolynomial_zero_on_domain(
+	__isl_take isl_space *dim)
 {
 	if (!dim)
 		return NULL;
 	return isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_one(__isl_take isl_dim *dim)
+__isl_give isl_qpolynomial *isl_qpolynomial_one_on_domain(
+	__isl_take isl_space *dim)
 {
 	if (!dim)
 		return NULL;
 	return isl_qpolynomial_alloc(dim, 0, isl_upoly_one(dim->ctx));
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_infty(__isl_take isl_dim *dim)
+__isl_give isl_qpolynomial *isl_qpolynomial_infty_on_domain(
+	__isl_take isl_space *dim)
 {
 	if (!dim)
 		return NULL;
 	return isl_qpolynomial_alloc(dim, 0, isl_upoly_infty(dim->ctx));
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_neginfty(__isl_take isl_dim *dim)
+__isl_give isl_qpolynomial *isl_qpolynomial_neginfty_on_domain(
+	__isl_take isl_space *dim)
 {
 	if (!dim)
 		return NULL;
 	return isl_qpolynomial_alloc(dim, 0, isl_upoly_neginfty(dim->ctx));
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_nan(__isl_take isl_dim *dim)
+__isl_give isl_qpolynomial *isl_qpolynomial_nan_on_domain(
+	__isl_take isl_space *dim)
 {
 	if (!dim)
 		return NULL;
 	return isl_qpolynomial_alloc(dim, 0, isl_upoly_nan(dim->ctx));
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_cst(__isl_take isl_dim *dim,
+__isl_give isl_qpolynomial *isl_qpolynomial_cst_on_domain(
+	__isl_take isl_space *dim,
 	isl_int v)
 {
 	struct isl_qpolynomial *qp;
@@ -1642,7 +1714,7 @@ __isl_give isl_vec *isl_qpolynomial_extract_affine(
 	if (!qp)
 		return NULL;
 
-	d = isl_dim_total(qp->dim);
+	d = isl_space_dim(qp->dim, isl_dim_all);
 	aff = isl_vec_alloc(qp->div->ctx, 2 + d + qp->div->n_row);
 	if (!aff)
 		return NULL;
@@ -1659,12 +1731,22 @@ error:
 	return NULL;
 }
 
-int isl_qpolynomial_is_equal(__isl_keep isl_qpolynomial *qp1,
+int isl_qpolynomial_plain_is_equal(__isl_keep isl_qpolynomial *qp1,
 	__isl_keep isl_qpolynomial *qp2)
 {
+	int equal;
+
 	if (!qp1 || !qp2)
 		return -1;
 
+	equal = isl_space_is_equal(qp1->dim, qp2->dim);
+	if (equal < 0 || !equal)
+		return equal;
+
+	equal = isl_mat_is_equal(qp1->div, qp2->div);
+	if (equal < 0 || !equal)
+		return equal;
+
 	return isl_upoly_is_equal(qp1->upoly, qp2->upoly);
 }
 
@@ -1698,8 +1780,8 @@ void isl_qpolynomial_get_den(__isl_keep isl_qpolynomial *qp, isl_int *d)
 	upoly_update_den(qp->upoly, d);
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_var_pow(__isl_take isl_dim *dim,
-	int pos, int power)
+__isl_give isl_qpolynomial *isl_qpolynomial_var_pow_on_domain(
+	__isl_take isl_space *dim, int pos, int power)
 {
 	struct isl_ctx *ctx;
 
@@ -1711,21 +1793,21 @@ __isl_give isl_qpolynomial *isl_qpolynomial_var_pow(__isl_take isl_dim *dim,
 	return isl_qpolynomial_alloc(dim, 0, isl_upoly_var_pow(ctx, pos, power));
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_var(__isl_take isl_dim *dim,
+__isl_give isl_qpolynomial *isl_qpolynomial_var_on_domain(__isl_take isl_space *dim,
 	enum isl_dim_type type, unsigned pos)
 {
 	if (!dim)
 		return NULL;
 
-	isl_assert(dim->ctx, isl_dim_size(dim, isl_dim_in) == 0, goto error);
-	isl_assert(dim->ctx, pos < isl_dim_size(dim, type), goto error);
+	isl_assert(dim->ctx, isl_space_dim(dim, isl_dim_in) == 0, goto error);
+	isl_assert(dim->ctx, pos < isl_space_dim(dim, type), goto error);
 
 	if (type == isl_dim_set)
-		pos += isl_dim_size(dim, isl_dim_param);
+		pos += isl_space_dim(dim, isl_dim_param);
 
-	return isl_qpolynomial_var_pow(dim, pos, 1);
+	return isl_qpolynomial_var_pow_on_domain(dim, pos, 1);
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	return NULL;
 }
 
@@ -1838,7 +1920,7 @@ static __isl_give isl_qpolynomial *substitute_div(
 	if (!qp)
 		goto error;
 
-	total = isl_dim_total(qp->dim);
+	total = isl_space_dim(qp->dim, isl_dim_all);
 	qp->upoly = isl_upoly_subs(qp->upoly, total + div, 1, &s);
 	if (!qp->upoly)
 		goto error;
@@ -1879,7 +1961,7 @@ static __isl_give isl_qpolynomial *substitute_non_divs(
 	if (!qp)
 		return NULL;
 
-	total = isl_dim_total(qp->dim);
+	total = isl_space_dim(qp->dim, isl_dim_all);
 	for (i = 0; qp && i < qp->div->n_row; ++i) {
 		if (!isl_int_is_one(qp->div->row[i][0]))
 			continue;
@@ -2044,63 +2126,15 @@ error:
 	return NULL;
 }
 
-/* Assumes each div only depends on earlier divs.
- */
-__isl_give isl_qpolynomial *isl_qpolynomial_div_pow(__isl_take isl_div *div,
-	int power)
+__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain(
+	__isl_take isl_space *dim, const isl_int n, const isl_int d)
 {
-	struct isl_qpolynomial *qp = NULL;
-	struct isl_upoly_rec *rec;
+	struct isl_qpolynomial *qp;
 	struct isl_upoly_cst *cst;
-	int i, d;
-	int pos;
 
-	if (!div)
+	if (!dim)
 		return NULL;
 
-	d = div->line - div->bmap->div;
-
-	pos = isl_dim_total(div->bmap->dim) + d;
-	rec = isl_upoly_alloc_rec(div->ctx, pos, 1 + power);
-	qp = isl_qpolynomial_alloc(isl_basic_map_get_dim(div->bmap),
-				   div->bmap->n_div, &rec->up);
-	if (!qp)
-		goto error;
-
-	for (i = 0; i < div->bmap->n_div; ++i)
-		isl_seq_cpy(qp->div->row[i], div->bmap->div[i], qp->div->n_col);
-
-	for (i = 0; i < 1 + power; ++i) {
-		rec->p[i] = isl_upoly_zero(div->ctx);
-		if (!rec->p[i])
-			goto error;
-		rec->n++;
-	}
-	cst = isl_upoly_as_cst(rec->p[power]);
-	isl_int_set_si(cst->n, 1);
-
-	isl_div_free(div);
-
-	qp = reduce_divs(qp);
-
-	return qp;
-error:
-	isl_qpolynomial_free(qp);
-	isl_div_free(div);
-	return NULL;
-}
-
-__isl_give isl_qpolynomial *isl_qpolynomial_div(__isl_take isl_div *div)
-{
-	return isl_qpolynomial_div_pow(div, 1);
-}
-
-__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst(__isl_take isl_dim *dim,
-	const isl_int n, const isl_int d)
-{
-	struct isl_qpolynomial *qp;
-	struct isl_upoly_cst *cst;
-
 	qp = isl_qpolynomial_alloc(dim, 0, isl_upoly_zero(dim->ctx));
 	if (!qp)
 		return NULL;
@@ -2137,7 +2171,7 @@ static int up_set_active(__isl_keep struct isl_upoly *up, int *active, int d)
 static int set_active(__isl_keep isl_qpolynomial *qp, int *active)
 {
 	int i, j;
-	int d = isl_dim_total(qp->dim);
+	int d = isl_space_dim(qp->dim, isl_dim_all);
 
 	if (!qp || !active)
 		return -1;
@@ -2165,17 +2199,18 @@ int isl_qpolynomial_involves_dims(__isl_keep isl_qpolynomial *qp,
 	if (n == 0)
 		return 0;
 
-	isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
-			return -1);
+	isl_assert(qp->dim->ctx,
+		    first + n <= isl_qpolynomial_dim(qp, type), return -1);
 	isl_assert(qp->dim->ctx, type == isl_dim_param ||
-				 type == isl_dim_set, return -1);
+				 type == isl_dim_in, return -1);
 
-	active = isl_calloc_array(qp->dim->ctx, int, isl_dim_total(qp->dim));
+	active = isl_calloc_array(qp->dim->ctx, int,
+					isl_space_dim(qp->dim, isl_dim_all));
 	if (set_active(qp, active) < 0)
 		goto error;
 
-	if (type == isl_dim_set)
-		first += isl_dim_size(qp->dim, isl_dim_param);
+	if (type == isl_dim_in)
+		first += isl_space_dim(qp->dim, isl_dim_param);
 	for (i = 0; i < n; ++i)
 		if (active[first + i]) {
 			involves = 1;
@@ -2204,15 +2239,17 @@ static __isl_give isl_qpolynomial *remove_redundant_divs(
 	int *reordering = NULL;
 	int redundant = 0;
 	int n_div;
+	isl_ctx *ctx;
 
 	if (!qp)
 		return NULL;
 	if (qp->div->n_row == 0)
 		return qp;
 
-	d = isl_dim_total(qp->dim);
+	d = isl_space_dim(qp->dim, isl_dim_all);
 	len = qp->div->n_col - 2;
-	active = isl_calloc_array(qp->ctx, int, len);
+	ctx = isl_qpolynomial_get_ctx(qp);
+	active = isl_calloc_array(ctx, int, len);
 	if (!active)
 		goto error;
 
@@ -2313,7 +2350,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name(
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp)
 		return NULL;
-	qp->dim = isl_dim_set_name(qp->dim, type, pos, s);
+	qp->dim = isl_space_set_dim_name(qp->dim, type, pos, s);
 	if (!qp->dim)
 		goto error;
 	return qp;
@@ -2328,24 +2365,30 @@ __isl_give isl_qpolynomial *isl_qpolynomial_drop_dims(
 {
 	if (!qp)
 		return NULL;
-	if (n == 0 && !isl_dim_get_tuple_name(qp->dim, type))
+	if (type == isl_dim_out)
+		isl_die(qp->dim->ctx, isl_error_invalid,
+			"cannot drop output/set dimension",
+			goto error);
+	if (type == isl_dim_in)
+		type = isl_dim_set;
+	if (n == 0 && !isl_space_is_named_or_nested(qp->dim, type))
 		return qp;
 
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp)
 		return NULL;
 
-	isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
+	isl_assert(qp->dim->ctx, first + n <= isl_space_dim(qp->dim, type),
 			goto error);
 	isl_assert(qp->dim->ctx, type == isl_dim_param ||
 				 type == isl_dim_set, goto error);
 
-	qp->dim = isl_dim_drop(qp->dim, type, first, n);
+	qp->dim = isl_space_drop_dims(qp->dim, type, first, n);
 	if (!qp->dim)
 		goto error;
 
 	if (type == isl_dim_set)
-		first += isl_dim_size(qp->dim, isl_dim_param);
+		first += isl_space_dim(qp->dim, isl_dim_param);
 
 	qp->div = isl_mat_drop_cols(qp->div, 2 + first, n);
 	if (!qp->div)
@@ -2361,7 +2404,32 @@ error:
 	return NULL;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
+/* Project the domain of the quasi-polynomial onto its parameter space.
+ * The quasi-polynomial may not involve any of the domain dimensions.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_project_domain_on_params(
+	__isl_take isl_qpolynomial *qp)
+{
+	isl_space *space;
+	unsigned n;
+	int involves;
+
+	n = isl_qpolynomial_dim(qp, isl_dim_in);
+	involves = isl_qpolynomial_involves_dims(qp, isl_dim_in, 0, n);
+	if (involves < 0)
+		return isl_qpolynomial_free(qp);
+	if (involves)
+		isl_die(isl_qpolynomial_get_ctx(qp), isl_error_invalid,
+			"polynomial involves some of the domain dimensions",
+			return isl_qpolynomial_free(qp));
+	qp = isl_qpolynomial_drop_dims(qp, isl_dim_in, 0, n);
+	space = isl_qpolynomial_get_domain_space(qp);
+	space = isl_space_params(space);
+	qp = isl_qpolynomial_reset_domain_space(qp, space);
+	return qp;
+}
+
+static __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities_lifted(
 	__isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq)
 {
 	int i, j, k;
@@ -2384,7 +2452,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
 	if (!qp->div)
 		goto error;
 
-	total = 1 + isl_dim_total(eq->dim);
+	total = 1 + isl_space_dim(eq->dim, isl_dim_all);
 	n_div = eq->n_div;
 	isl_int_init(denom);
 	for (i = 0; i < eq->n_eq; ++i) {
@@ -2427,6 +2495,22 @@ error:
 	return NULL;
 }
 
+/* Exploit the equalities in "eq" to simplify the quasi-polynomial.
+ */
+__isl_give isl_qpolynomial *isl_qpolynomial_substitute_equalities(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_basic_set *eq)
+{
+	if (!qp || !eq)
+		goto error;
+	if (qp->div->n_row > 0)
+		eq = isl_basic_set_add_dims(eq, isl_dim_set, qp->div->n_row);
+	return isl_qpolynomial_substitute_equalities_lifted(qp, eq);
+error:
+	isl_basic_set_free(eq);
+	isl_qpolynomial_free(qp);
+	return NULL;
+}
+
 static __isl_give isl_basic_set *add_div_constraints(
 	__isl_take isl_basic_set *bset, __isl_take isl_mat *div)
 {
@@ -2469,28 +2553,62 @@ __isl_give isl_qpolynomial *isl_qpolynomial_gist(
 		isl_basic_set *bset;
 		context = isl_set_add_dims(context, isl_dim_set,
 					    qp->div->n_row);
-		bset = isl_basic_set_universe(isl_set_get_dim(context));
+		bset = isl_basic_set_universe(isl_set_get_space(context));
 		bset = add_div_constraints(bset, isl_mat_copy(qp->div));
 		context = isl_set_intersect(context,
 					    isl_set_from_basic_set(bset));
 	}
 
 	aff = isl_set_affine_hull(context);
-	return isl_qpolynomial_substitute_equalities(qp, aff);
+	return isl_qpolynomial_substitute_equalities_lifted(qp, aff);
 error:
 	isl_qpolynomial_free(qp);
 	isl_set_free(context);
 	return NULL;
 }
 
+__isl_give isl_qpolynomial *isl_qpolynomial_gist_params(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_set *context)
+{
+	isl_space *space = isl_qpolynomial_get_domain_space(qp);
+	isl_set *dom_context = isl_set_universe(space);
+	dom_context = isl_set_intersect_params(dom_context, context);
+	return isl_qpolynomial_gist(qp, dom_context);
+}
+
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_qpolynomial(
+	__isl_take isl_qpolynomial *qp)
+{
+	isl_set *dom;
+
+	if (!qp)
+		return NULL;
+	if (isl_qpolynomial_is_zero(qp)) {
+		isl_space *dim = isl_qpolynomial_get_space(qp);
+		isl_qpolynomial_free(qp);
+		return isl_pw_qpolynomial_zero(dim);
+	}
+
+	dom = isl_set_universe(isl_qpolynomial_get_domain_space(qp));
+	return isl_pw_qpolynomial_alloc(dom, qp);
+}
+
 #undef PW
 #define PW isl_pw_qpolynomial
 #undef EL
 #define EL isl_qpolynomial
+#undef EL_IS_ZERO
+#define EL_IS_ZERO is_zero
+#undef ZERO
+#define ZERO zero
 #undef IS_ZERO
 #define IS_ZERO is_zero
 #undef FIELD
 #define FIELD qp
+#undef DEFAULT_IS_ZERO
+#define DEFAULT_IS_ZERO 1
+
+#define NO_PULLBACK
 
 #include <isl_pw_templ.c>
 
@@ -2500,6 +2618,7 @@ error:
 #define PART isl_pw_qpolynomial
 #undef PARTS
 #define PARTS pw_qpolynomial
+#define ALIGN_DOMAIN
 
 #include <isl_union_templ.c>
 
@@ -2517,6 +2636,13 @@ int isl_pw_qpolynomial_is_one(__isl_keep isl_pw_qpolynomial *pwqp)
 	return isl_qpolynomial_is_one(pwqp->p[0].qp);
 }
 
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
+	__isl_take isl_pw_qpolynomial *pwqp1,
+	__isl_take isl_pw_qpolynomial *pwqp2)
+{
+	return isl_pw_qpolynomial_union_add_(pwqp1, pwqp2);
+}
+
 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
 	__isl_take isl_pw_qpolynomial *pwqp1,
 	__isl_take isl_pw_qpolynomial *pwqp2)
@@ -2527,7 +2653,7 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
 	if (!pwqp1 || !pwqp2)
 		goto error;
 
-	isl_assert(pwqp1->dim->ctx, isl_dim_equal(pwqp1->dim, pwqp2->dim),
+	isl_assert(pwqp1->dim->ctx, isl_space_is_equal(pwqp1->dim, pwqp2->dim),
 			goto error);
 
 	if (isl_pw_qpolynomial_is_zero(pwqp1)) {
@@ -2551,7 +2677,7 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
 	}
 
 	n = pwqp1->n * pwqp2->n;
-	res = isl_pw_qpolynomial_alloc_(isl_dim_copy(pwqp1->dim), n);
+	res = isl_pw_qpolynomial_alloc_size(isl_space_copy(pwqp1->dim), n);
 
 	for (i = 0; i < pwqp1->n; ++i) {
 		for (j = 0; j < pwqp2->n; ++j) {
@@ -2582,40 +2708,6 @@ error:
 	return NULL;
 }
 
-__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_neg(
-	__isl_take isl_pw_qpolynomial *pwqp)
-{
-	int i;
-
-	if (!pwqp)
-		return NULL;
-
-	if (isl_pw_qpolynomial_is_zero(pwqp))
-		return pwqp;
-
-	pwqp = isl_pw_qpolynomial_cow(pwqp);
-	if (!pwqp)
-		return NULL;
-
-	for (i = 0; i < pwqp->n; ++i) {
-		pwqp->p[i].qp = isl_qpolynomial_neg(pwqp->p[i].qp);
-		if (!pwqp->p[i].qp)
-			goto error;
-	}
-
-	return pwqp;
-error:
-	isl_pw_qpolynomial_free(pwqp);
-	return NULL;
-}
-
-__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sub(
-	__isl_take isl_pw_qpolynomial *pwqp1,
-	__isl_take isl_pw_qpolynomial *pwqp2)
-{
-	return isl_pw_qpolynomial_add(pwqp1, isl_pw_qpolynomial_neg(pwqp2));
-}
-
 __isl_give struct isl_upoly *isl_upoly_eval(
 	__isl_take struct isl_upoly *up, __isl_take isl_vec *vec)
 {
@@ -2662,17 +2754,17 @@ __isl_give isl_qpolynomial *isl_qpolynomial_eval(
 {
 	isl_vec *ext;
 	struct isl_upoly *up;
-	isl_dim *dim;
+	isl_space *dim;
 
 	if (!qp || !pnt)
 		goto error;
-	isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, qp->dim), goto error);
+	isl_assert(pnt->dim->ctx, isl_space_is_equal(pnt->dim, qp->dim), goto error);
 
 	if (qp->div->n_row == 0)
 		ext = isl_vec_copy(pnt->vec);
 	else {
 		int i;
-		unsigned dim = isl_dim_total(qp->dim);
+		unsigned dim = isl_space_dim(qp->dim, isl_dim_all);
 		ext = isl_vec_alloc(qp->dim->ctx, 1 + dim + qp->div->n_row);
 		if (!ext)
 			goto error;
@@ -2690,7 +2782,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_eval(
 	if (!up)
 		goto error;
 
-	dim = isl_dim_copy(qp->dim);
+	dim = isl_space_copy(qp->dim);
 	isl_qpolynomial_free(qp);
 	isl_point_free(pnt);
 
@@ -2795,19 +2887,27 @@ __isl_give isl_qpolynomial *isl_qpolynomial_insert_dims(
 	unsigned g_pos;
 	int *exp;
 
-	if (n == 0)
+	if (!qp)
+		return NULL;
+	if (type == isl_dim_out)
+		isl_die(qp->div->ctx, isl_error_invalid,
+			"cannot insert output/set dimensions",
+			goto error);
+	if (type == isl_dim_in)
+		type = isl_dim_set;
+	if (n == 0 && !isl_space_is_named_or_nested(qp->dim, type))
 		return qp;
 
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp)
 		return NULL;
 
-	isl_assert(qp->div->ctx, first <= isl_dim_size(qp->dim, type),
+	isl_assert(qp->div->ctx, first <= isl_space_dim(qp->dim, type),
 		    goto error);
 
 	g_pos = pos(qp->dim, type) + first;
 
-	qp->div = isl_mat_insert_cols(qp->div, 2 + g_pos, n);
+	qp->div = isl_mat_insert_zero_cols(qp->div, 2 + g_pos, n);
 	if (!qp->div)
 		goto error;
 
@@ -2825,7 +2925,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_insert_dims(
 			goto error;
 	}
 
-	qp->dim = isl_dim_insert(qp->dim, type, first, n);
+	qp->dim = isl_space_insert_dims(qp->dim, type, first, n);
 	if (!qp->dim)
 		goto error;
 
@@ -2902,7 +3002,16 @@ __isl_give isl_qpolynomial *isl_qpolynomial_move_dims(
 	if (!qp)
 		return NULL;
 
-	isl_assert(qp->dim->ctx, src_pos + n <= isl_dim_size(qp->dim, src_type),
+	if (dst_type == isl_dim_out || src_type == isl_dim_out)
+		isl_die(qp->dim->ctx, isl_error_invalid,
+			"cannot move output/set dimension",
+			goto error);
+	if (dst_type == isl_dim_in)
+		dst_type = isl_dim_set;
+	if (src_type == isl_dim_in)
+		src_type = isl_dim_set;
+
+	isl_assert(qp->dim->ctx, src_pos + n <= isl_space_dim(qp->dim, src_type),
 		goto error);
 
 	g_dst_pos = pos(qp->dim, dst_type) + dst_pos;
@@ -2927,7 +3036,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_move_dims(
 	if (!qp->upoly)
 		goto error;
 
-	qp->dim = isl_dim_move(qp->dim, dst_type, dst_pos, src_type, src_pos, n);
+	qp->dim = isl_space_move_dims(qp->dim, dst_type, dst_pos, src_type, src_pos, n);
 	if (!qp->dim)
 		goto error;
 
@@ -2937,15 +3046,17 @@ error:
 	return NULL;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_dim *dim,
+__isl_give isl_qpolynomial *isl_qpolynomial_from_affine(__isl_take isl_space *dim,
 	isl_int *f, isl_int denom)
 {
 	struct isl_upoly *up;
 
+	dim = isl_space_domain(dim);
 	if (!dim)
 		return NULL;
 
-	up = isl_upoly_from_affine(dim->ctx, f, denom, 1 + isl_dim_total(dim));
+	up = isl_upoly_from_affine(dim->ctx, f, denom,
+					1 + isl_space_dim(dim, isl_dim_all));
 
 	return isl_qpolynomial_alloc(dim, 0, up);
 }
@@ -2963,7 +3074,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_from_aff(__isl_take isl_aff *aff)
 	up = isl_upoly_from_affine(ctx, aff->v->el + 1, aff->v->el[0],
 				    aff->v->size - 1);
 
-	qp = isl_qpolynomial_alloc(isl_aff_get_dim(aff),
+	qp = isl_qpolynomial_alloc(isl_aff_get_domain_space(aff),
 				    aff->ls->div->n_row, up);
 	if (!qp)
 		goto error;
@@ -2983,39 +3094,39 @@ error:
 	return NULL;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
-	__isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
+__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_from_pw_aff(
+	__isl_take isl_pw_aff *pwaff)
 {
-	isl_int denom;
-	isl_dim *dim;
-	struct isl_upoly *up;
-	isl_qpolynomial *qp;
-	int sgn;
+	int i;
+	isl_pw_qpolynomial *pwqp;
 
-	if (!c)
+	if (!pwaff)
 		return NULL;
 
-	isl_int_init(denom);
+	pwqp = isl_pw_qpolynomial_alloc_size(isl_pw_aff_get_space(pwaff),
+						pwaff->n);
 
-	isl_constraint_get_coefficient(c, type, pos, &denom);
-	isl_constraint_set_coefficient(c, type, pos, c->ctx->zero);
-	sgn = isl_int_sgn(denom);
-	isl_int_abs(denom, denom);
-	up = isl_upoly_from_affine(c->ctx, c->line[0], denom,
-					1 + isl_constraint_dim(c, isl_dim_all));
-	if (sgn < 0)
-		isl_int_neg(denom, denom);
-	isl_constraint_set_coefficient(c, type, pos, denom);
+	for (i = 0; i < pwaff->n; ++i) {
+		isl_set *dom;
+		isl_qpolynomial *qp;
 
-	dim = isl_dim_copy(c->bmap->dim);
+		dom = isl_set_copy(pwaff->p[i].set);
+		qp = isl_qpolynomial_from_aff(isl_aff_copy(pwaff->p[i].aff));
+		pwqp = isl_pw_qpolynomial_add_piece(pwqp,  dom, qp);
+	}
 
-	isl_int_clear(denom);
-	isl_constraint_free(c);
+	isl_pw_aff_free(pwaff);
+	return pwqp;
+}
 
-	qp = isl_qpolynomial_alloc(dim, 0, up);
-	if (sgn > 0)
-		qp = isl_qpolynomial_neg(qp);
-	return qp;
+__isl_give isl_qpolynomial *isl_qpolynomial_from_constraint(
+	__isl_take isl_constraint *c, enum isl_dim_type type, unsigned pos)
+{
+	isl_aff *aff;
+
+	aff = isl_constraint_get_bound(c, type, pos);
+	isl_constraint_free(c);
+	return isl_qpolynomial_from_aff(aff);
 }
 
 /* For each 0 <= i < "n", replace variable "first" + i of type "type"
@@ -3035,15 +3146,23 @@ __isl_give isl_qpolynomial *isl_qpolynomial_substitute(
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp)
 		return NULL;
+
+	if (type == isl_dim_out)
+		isl_die(qp->dim->ctx, isl_error_invalid,
+			"cannot substitute output/set dimension",
+			goto error);
+	if (type == isl_dim_in)
+		type = isl_dim_set;
+
 	for (i = 0; i < n; ++i)
 		if (!subs[i])
 			goto error;
 
-	isl_assert(qp->dim->ctx, first + n <= isl_dim_size(qp->dim, type),
+	isl_assert(qp->dim->ctx, first + n <= isl_space_dim(qp->dim, type),
 			goto error);
 
 	for (i = 0; i < n; ++i)
-		isl_assert(qp->dim->ctx, isl_dim_equal(qp->dim, subs[i]->dim),
+		isl_assert(qp->dim->ctx, isl_space_is_equal(qp->dim, subs[i]->dim),
 				goto error);
 
 	isl_assert(qp->dim->ctx, qp->div->n_row == 0, goto error);
@@ -3081,7 +3200,7 @@ int isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp,
 	int (*fn)(__isl_take isl_basic_set *bset,
 		  __isl_take isl_qpolynomial *poly, void *user), void *user)
 {
-	isl_dim *dim;
+	isl_space *dim;
 	isl_mat *div;
 	isl_qpolynomial *poly;
 
@@ -3092,11 +3211,11 @@ int isl_qpolynomial_as_polynomial_on_domain(__isl_keep isl_qpolynomial *qp,
 			  user);
 
 	div = isl_mat_copy(qp->div);
-	dim = isl_dim_copy(qp->dim);
-	dim = isl_dim_add(dim, isl_dim_set, qp->div->n_row);
+	dim = isl_space_copy(qp->dim);
+	dim = isl_space_add_dims(dim, isl_dim_set, qp->div->n_row);
 	poly = isl_qpolynomial_alloc(dim, 0, isl_upoly_copy(qp->upoly));
 	bset = isl_basic_set_copy(bset);
-	bset = isl_basic_set_add(bset, isl_dim_set, qp->div->n_row);
+	bset = isl_basic_set_add_dims(bset, isl_dim_set, qp->div->n_row);
 	bset = add_div_constraints(bset, div);
 
 	return fn(bset, poly, user);
@@ -3148,8 +3267,8 @@ int isl_qpolynomial_degree(__isl_keep isl_qpolynomial *poly)
 	if (!poly)
 		return -2;
 
-	ovar = isl_dim_offset(poly->dim, isl_dim_set);
-	nvar = isl_dim_size(poly->dim, isl_dim_set);
+	ovar = isl_space_offset(poly->dim, isl_dim_set);
+	nvar = isl_space_dim(poly->dim, isl_dim_set);
 	return isl_upoly_degree(poly->upoly, ovar, ovar + nvar);
 }
 
@@ -3214,13 +3333,20 @@ __isl_give isl_qpolynomial *isl_qpolynomial_coeff(
 	if (!qp)
 		return NULL;
 
-	isl_assert(qp->div->ctx, t_pos < isl_dim_size(qp->dim, type),
+	if (type == isl_dim_out)
+		isl_die(qp->div->ctx, isl_error_invalid,
+			"output/set dimension does not have a coefficient",
+			return NULL);
+	if (type == isl_dim_in)
+		type = isl_dim_set;
+
+	isl_assert(qp->div->ctx, t_pos < isl_space_dim(qp->dim, type),
 			return NULL);
 
 	g_pos = pos(qp->dim, type) + t_pos;
 	up = isl_upoly_coeff(qp->upoly, g_pos, deg);
 
-	c = isl_qpolynomial_alloc(isl_dim_copy(qp->dim), qp->div->n_row, up);
+	c = isl_qpolynomial_alloc(isl_space_copy(qp->dim), qp->div->n_row, up);
 	if (!c)
 		return NULL;
 	isl_mat_free(c->div);
@@ -3296,13 +3422,13 @@ __isl_give isl_qpolynomial *isl_qpolynomial_homogenize(
 	if (deg < -1)
 		goto error;
 
-	poly = isl_qpolynomial_insert_dims(poly, isl_dim_set, 0, 1);
+	poly = isl_qpolynomial_insert_dims(poly, isl_dim_in, 0, 1);
 	poly = isl_qpolynomial_cow(poly);
 	if (!poly)
 		goto error;
 
-	ovar = isl_dim_offset(poly->dim, isl_dim_set);
-	nvar = isl_dim_size(poly->dim, isl_dim_set);
+	ovar = isl_space_offset(poly->dim, isl_dim_set);
+	nvar = isl_space_dim(poly->dim, isl_dim_set);
 	poly->upoly = isl_upoly_homogenize(poly->upoly, 0, deg,
 						ovar, ovar + nvar);
 	if (!poly->upoly)
@@ -3314,7 +3440,7 @@ error:
 	return NULL;
 }
 
-__isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim,
+__isl_give isl_term *isl_term_alloc(__isl_take isl_space *dim,
 	__isl_take isl_mat *div)
 {
 	isl_term *term;
@@ -3323,7 +3449,7 @@ __isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim,
 	if (!dim || !div)
 		goto error;
 
-	n = isl_dim_total(dim) + div->n_row;
+	n = isl_space_dim(dim, isl_dim_all) + div->n_row;
 
 	term = isl_calloc(dim->ctx, struct isl_term,
 			sizeof(struct isl_term) + (n - 1) * sizeof(int));
@@ -3338,7 +3464,7 @@ __isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim,
 	
 	return term;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	isl_mat_free(div);
 	return NULL;
 }
@@ -3358,12 +3484,12 @@ __isl_give isl_term *isl_term_dup(__isl_keep isl_term *term)
 	isl_term *dup;
 	unsigned total;
 
-	if (term)
+	if (!term)
 		return NULL;
 
-	total = isl_dim_total(term->dim) + term->div->n_row;
+	total = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
 
-	dup = isl_term_alloc(isl_dim_copy(term->dim), isl_mat_copy(term->div));
+	dup = isl_term_alloc(isl_space_copy(term->dim), isl_mat_copy(term->div));
 	if (!dup)
 		return NULL;
 
@@ -3395,7 +3521,7 @@ void isl_term_free(__isl_take isl_term *term)
 	if (--term->ref > 0)
 		return;
 
-	isl_dim_free(term->dim);
+	isl_space_free(term->dim);
 	isl_mat_free(term->div);
 	isl_int_clear(term->n);
 	isl_int_clear(term->d);
@@ -3410,9 +3536,10 @@ unsigned isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type)
 	switch (type) {
 	case isl_dim_param:
 	case isl_dim_in:
-	case isl_dim_out:	return isl_dim_size(term->dim, type);
+	case isl_dim_out:	return isl_space_dim(term->dim, type);
 	case isl_dim_div:	return term->div->n_row;
-	case isl_dim_all:	return isl_dim_total(term->dim) + term->div->n_row;
+	case isl_dim_all:	return isl_space_dim(term->dim, isl_dim_all) +
+								term->div->n_row;
 	default:		return 0;
 	}
 }
@@ -3445,18 +3572,17 @@ int isl_term_get_exp(__isl_keep isl_term *term,
 	isl_assert(term->dim->ctx, pos < isl_term_dim(term, type), return -1);
 
 	if (type >= isl_dim_set)
-		pos += isl_dim_size(term->dim, isl_dim_param);
+		pos += isl_space_dim(term->dim, isl_dim_param);
 	if (type >= isl_dim_div)
-		pos += isl_dim_size(term->dim, isl_dim_set);
+		pos += isl_space_dim(term->dim, isl_dim_set);
 
 	return term->pow[pos];
 }
 
-__isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
+__isl_give isl_aff *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
 {
-	isl_basic_map *bmap;
-	unsigned total;
-	int k;
+	isl_local_space *ls;
+	isl_aff *aff;
 
 	if (!term)
 		return NULL;
@@ -3464,23 +3590,17 @@ __isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos)
 	isl_assert(term->dim->ctx, pos < isl_term_dim(term, isl_dim_div),
 			return NULL);
 
-	total = term->div->n_col - term->div->n_row - 2;
-	/* No nested divs for now */
-	isl_assert(term->dim->ctx,
-		isl_seq_first_non_zero(term->div->row[pos] + 2 + total,
-					term->div->n_row) == -1,
-		return NULL);
+	ls = isl_local_space_alloc_div(isl_space_copy(term->dim),
+					isl_mat_copy(term->div));
+	aff = isl_aff_alloc(ls);
+	if (!aff)
+		return NULL;
 
-	bmap = isl_basic_map_alloc_dim(isl_dim_copy(term->dim), 1, 0, 0);
-	if ((k = isl_basic_map_alloc_div(bmap)) < 0)
-		goto error;
+	isl_seq_cpy(aff->v->el, term->div->row[pos], aff->v->size);
 
-	isl_seq_cpy(bmap->div[k], term->div->row[pos], 2 + total);
+	aff = isl_aff_normalize(aff);
 
-	return isl_basic_map_div(bmap, k);
-error:
-	isl_basic_map_free(bmap);
-	return NULL;
+	return aff;
 }
 
 __isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up,
@@ -3544,7 +3664,7 @@ int isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp,
 	if (!qp)
 		return -1;
 
-	term = isl_term_alloc(isl_dim_copy(qp->dim), isl_mat_copy(qp->div));
+	term = isl_term_alloc(isl_space_copy(qp->dim), isl_mat_copy(qp->div));
 	if (!term)
 		return -1;
 
@@ -3564,7 +3684,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_from_term(__isl_take isl_term *term)
 	if (!term)
 		return NULL;
 
-	n = isl_dim_total(term->dim) + term->div->n_row;
+	n = isl_space_dim(term->dim, isl_dim_all) + term->div->n_row;
 
 	up = isl_upoly_rat_cst(term->dim->ctx, term->n, term->d);
 	for (i = 0; i < n; ++i) {
@@ -3574,7 +3694,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_from_term(__isl_take isl_term *term)
 			isl_upoly_var_pow(term->dim->ctx, i, term->pow[i]));
 	}
 
-	qp = isl_qpolynomial_alloc(isl_dim_copy(term->dim), term->div->n_row, up);
+	qp = isl_qpolynomial_alloc(isl_space_copy(term->dim), term->div->n_row, up);
 	if (!qp)
 		goto error;
 	isl_mat_free(qp->div);
@@ -3591,7 +3711,7 @@ error:
 }
 
 __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
-	__isl_take isl_dim *dim)
+	__isl_take isl_space *dim)
 {
 	int i;
 	int extra;
@@ -3600,8 +3720,8 @@ __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
 	if (!qp || !dim)
 		goto error;
 
-	if (isl_dim_equal(qp->dim, dim)) {
-		isl_dim_free(dim);
+	if (isl_space_is_equal(qp->dim, dim)) {
+		isl_space_free(dim);
 		return qp;
 	}
 
@@ -3609,9 +3729,9 @@ __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
 	if (!qp)
 		goto error;
 
-	extra = isl_dim_size(dim, isl_dim_set) -
-			isl_dim_size(qp->dim, isl_dim_set);
-	total = isl_dim_total(qp->dim);
+	extra = isl_space_dim(dim, isl_dim_set) -
+			isl_space_dim(qp->dim, isl_dim_set);
+	total = isl_space_dim(qp->dim, isl_dim_all);
 	if (qp->div->n_row) {
 		int *exp;
 
@@ -3631,12 +3751,12 @@ __isl_give isl_qpolynomial *isl_qpolynomial_lift(__isl_take isl_qpolynomial *qp,
 	for (i = 0; i < qp->div->n_row; ++i)
 		isl_seq_clr(qp->div->row[i] + 2 + total, extra);
 
-	isl_dim_free(qp->dim);
+	isl_space_free(qp->dim);
 	qp->dim = dim;
 
 	return qp;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	isl_qpolynomial_free(qp);
 	return NULL;
 }
@@ -3656,7 +3776,7 @@ static __isl_give isl_set *fix_inactive(__isl_take isl_set *set,
 	if (!set || !qp)
 		goto error;
 
-	d = isl_dim_total(set->dim);
+	d = isl_space_dim(set->dim, isl_dim_all);
 	active = isl_calloc_array(set->ctx, int, d);
 	if (set_active(qp, active) < 0)
 		goto error;
@@ -3670,8 +3790,8 @@ static __isl_give isl_set *fix_inactive(__isl_take isl_set *set,
 		return set;
 	}
 
-	nparam = isl_dim_size(set->dim, isl_dim_param);
-	nvar = isl_dim_size(set->dim, isl_dim_set);
+	nparam = isl_space_dim(set->dim, isl_dim_param);
+	nvar = isl_space_dim(set->dim, isl_dim_set);
 	for (i = 0; i < nparam; ++i) {
 		if (active[i])
 			continue;
@@ -3738,8 +3858,10 @@ __isl_give isl_qpolynomial *isl_qpolynomial_opt_on_domain(
 	if (isl_set_foreach_point(set, opt_fn, &data) < 0)
 		goto error;
 
-	if (data.first)
-		data.opt = isl_qpolynomial_zero(isl_qpolynomial_get_dim(qp));
+	if (data.first) {
+		isl_space *space = isl_qpolynomial_get_domain_space(qp);
+		data.opt = isl_qpolynomial_zero_on_domain(space);
+	}
 
 	isl_set_free(set);
 	isl_qpolynomial_free(qp);
@@ -3751,21 +3873,21 @@ error:
 	return NULL;
 }
 
-__isl_give isl_qpolynomial *isl_qpolynomial_morph(__isl_take isl_qpolynomial *qp,
-	__isl_take isl_morph *morph)
+__isl_give isl_qpolynomial *isl_qpolynomial_morph_domain(
+	__isl_take isl_qpolynomial *qp, __isl_take isl_morph *morph)
 {
 	int i;
 	int n_sub;
 	isl_ctx *ctx;
 	struct isl_upoly **subs;
-	isl_mat *mat;
+	isl_mat *mat, *diag;
 
 	qp = isl_qpolynomial_cow(qp);
 	if (!qp || !morph)
 		goto error;
 
 	ctx = qp->dim->ctx;
-	isl_assert(ctx, isl_dim_equal(qp->dim, morph->dom->dim), goto error);
+	isl_assert(ctx, isl_space_is_equal(qp->dim, morph->dom->dim), goto error);
 
 	n_sub = morph->inv->n_row - 1;
 	if (morph->inv->n_row != morph->inv->n_col)
@@ -3788,11 +3910,13 @@ __isl_give isl_qpolynomial *isl_qpolynomial_morph(__isl_take isl_qpolynomial *qp
 		isl_upoly_free(subs[i]);
 	free(subs);
 
-	mat = isl_mat_diagonal(isl_mat_identity(ctx, 1), isl_mat_copy(morph->inv));
-	mat = isl_mat_diagonal(mat, isl_mat_identity(ctx, qp->div->n_row));
+	diag = isl_mat_diag(ctx, 1, morph->inv->row[0][0]);
+	mat = isl_mat_diagonal(diag, isl_mat_copy(morph->inv));
+	diag = isl_mat_diag(ctx, qp->div->n_row, morph->inv->row[0][0]);
+	mat = isl_mat_diagonal(mat, diag);
 	qp->div = isl_mat_product(qp->div, mat);
-	isl_dim_free(qp->dim);
-	qp->dim = isl_dim_copy(morph->ran->dim);
+	isl_space_free(qp->dim);
+	qp->dim = isl_space_copy(morph->ran->dim);
 
 	if (!qp->upoly || !qp->div || !qp->dim)
 		goto error;
@@ -3840,44 +3964,11 @@ __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub(
 					isl_union_pw_qpolynomial_neg(upwqp2));
 }
 
-static int mul_entry(void **entry, void *user)
-{
-	struct isl_union_pw_qpolynomial_match_bin_data *data = user;
-	uint32_t hash;
-	struct isl_hash_table_entry *entry2;
-	isl_pw_qpolynomial *pwpq = *entry;
-	int empty;
-
-	hash = isl_dim_get_hash(pwpq->dim);
-	entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
-				     hash, &has_dim, pwpq->dim, 0);
-	if (!entry2)
-		return 0;
-
-	pwpq = isl_pw_qpolynomial_copy(pwpq);
-	pwpq = isl_pw_qpolynomial_mul(pwpq,
-				      isl_pw_qpolynomial_copy(entry2->data));
-
-	empty = isl_pw_qpolynomial_is_zero(pwpq);
-	if (empty < 0) {
-		isl_pw_qpolynomial_free(pwpq);
-		return -1;
-	}
-	if (empty) {
-		isl_pw_qpolynomial_free(pwpq);
-		return 0;
-	}
-
-	data->res = isl_union_pw_qpolynomial_add_pw_qpolynomial(data->res, pwpq);
-
-	return 0;
-}
-
 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
 	__isl_take isl_union_pw_qpolynomial *upwqp1,
 	__isl_take isl_union_pw_qpolynomial *upwqp2)
 {
-	return match_bin_op(upwqp1, upwqp2, &mul_entry);
+	return match_bin_op(upwqp1, upwqp2, &isl_pw_qpolynomial_mul);
 }
 
 /* Reorder the columns of the given div definitions according to the
@@ -3893,7 +3984,7 @@ static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
 	if (!div || !r)
 		goto error;
 
-	extra = isl_dim_total(r->dim) + div->n_row - r->len;
+	extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
 	mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
 	if (!mat)
 		goto error;
@@ -3917,7 +4008,7 @@ error:
 
 /* Reorder the dimension of "qp" according to the given reordering.
  */
-__isl_give isl_qpolynomial *isl_qpolynomial_realign(
+__isl_give isl_qpolynomial *isl_qpolynomial_realign_domain(
 	__isl_take isl_qpolynomial *qp, __isl_take isl_reordering *r)
 {
 	qp = isl_qpolynomial_cow(qp);
@@ -3936,7 +4027,7 @@ __isl_give isl_qpolynomial *isl_qpolynomial_realign(
 	if (!qp->upoly)
 		goto error;
 
-	qp = isl_qpolynomial_reset_dim(qp, isl_dim_copy(r->dim));
+	qp = isl_qpolynomial_reset_domain_space(qp, isl_space_copy(r->dim));
 
 	isl_reordering_free(r);
 	return qp;
@@ -3947,28 +4038,28 @@ error:
 }
 
 __isl_give isl_qpolynomial *isl_qpolynomial_align_params(
-	__isl_take isl_qpolynomial *qp, __isl_take isl_dim *model)
+	__isl_take isl_qpolynomial *qp, __isl_take isl_space *model)
 {
 	if (!qp || !model)
 		goto error;
 
-	if (!isl_dim_match(qp->dim, isl_dim_param, model, isl_dim_param)) {
+	if (!isl_space_match(qp->dim, isl_dim_param, model, isl_dim_param)) {
 		isl_reordering *exp;
 
-		model = isl_dim_drop(model, isl_dim_in,
-					0, isl_dim_size(model, isl_dim_in));
-		model = isl_dim_drop(model, isl_dim_out,
-					0, isl_dim_size(model, isl_dim_out));
+		model = isl_space_drop_dims(model, isl_dim_in,
+					0, isl_space_dim(model, isl_dim_in));
+		model = isl_space_drop_dims(model, isl_dim_out,
+					0, isl_space_dim(model, isl_dim_out));
 		exp = isl_parameter_alignment_reordering(qp->dim, model);
-		exp = isl_reordering_extend_dim(exp,
-						isl_qpolynomial_get_dim(qp));
-		qp = isl_qpolynomial_realign(qp, exp);
+		exp = isl_reordering_extend_space(exp,
+					isl_qpolynomial_get_domain_space(qp));
+		qp = isl_qpolynomial_realign_domain(qp, exp);
 	}
 
-	isl_dim_free(model);
+	isl_space_free(model);
 	return qp;
 error:
-	isl_dim_free(model);
+	isl_space_free(model);
 	isl_qpolynomial_free(qp);
 	return NULL;
 }
@@ -3988,7 +4079,7 @@ struct isl_split_periods_data {
  *	f - m v >= 0
  *	-f + m v + (m - 1) >= 0
  */
-static __isl_give isl_set *set_div_slice(__isl_take isl_dim *dim,
+static __isl_give isl_set *set_div_slice(__isl_take isl_space *dim,
 	__isl_keep isl_qpolynomial *qp, int div, isl_int v)
 {
 	int total;
@@ -3998,8 +4089,8 @@ static __isl_give isl_set *set_div_slice(__isl_take isl_dim *dim,
 	if (!dim || !qp)
 		goto error;
 
-	total = isl_dim_total(dim);
-	bset = isl_basic_set_alloc_dim(isl_dim_copy(dim), 0, 0, 2);
+	total = isl_space_dim(dim, isl_dim_all);
+	bset = isl_basic_set_alloc_space(isl_space_copy(dim), 0, 0, 2);
 
 	k = isl_basic_set_alloc_inequality(bset);
 	if (k < 0)
@@ -4015,11 +4106,11 @@ static __isl_give isl_set *set_div_slice(__isl_take isl_dim *dim,
 	isl_int_add(bset->ineq[k][0], bset->ineq[k][0], qp->div->row[div][0]);
 	isl_int_sub_ui(bset->ineq[k][0], bset->ineq[k][0], 1);
 
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	return isl_set_from_basic_set(bset);
 error:
 	isl_basic_set_free(bset);
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	return NULL;
 }
 
@@ -4039,13 +4130,13 @@ static int set_div(__isl_take isl_set *set,
 	isl_set *slice;
 	struct isl_upoly *cst;
 
-	slice = set_div_slice(isl_set_get_dim(set), qp, div, v);
+	slice = set_div_slice(isl_set_get_space(set), qp, div, v);
 	set = isl_set_intersect(set, slice);
 
 	if (!qp)
 		goto error;
 
-	total = isl_dim_total(qp->dim);
+	total = isl_space_dim(qp->dim, isl_dim_all);
 
 	for (i = div + 1; i < qp->div->n_row; ++i) {
 		if (isl_int_is_zero(qp->div->row[i][2 + total + div]))
@@ -4118,7 +4209,7 @@ static int split_periods(__isl_take isl_set *set,
 
 	isl_int_init(min);
 	isl_int_init(max);
-	total = isl_dim_total(qp->dim);
+	total = isl_space_dim(qp->dim, isl_dim_all);
 	for (i = 0; i < qp->div->n_row; ++i) {
 		enum isl_lp_result lp_res;
 
@@ -4179,7 +4270,7 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_split_periods(
 	struct isl_split_periods_data data;
 
 	data.max_periods = max_periods;
-	data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_dim(pwqp));
+	data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
 
 	if (isl_pw_qpolynomial_foreach_piece(pwqp, &split_periods, &data) < 0)
 		goto error;
@@ -4202,20 +4293,20 @@ error:
 static __isl_give isl_pw_qpolynomial *constant_on_domain(
 	__isl_take isl_basic_set *bset, int cst)
 {
-	isl_dim *dim;
+	isl_space *dim;
 	isl_qpolynomial *qp;
 
 	if (!bset)
 		return NULL;
 
-	bset = isl_basic_map_domain(isl_basic_map_from_range(bset));
-	dim = isl_basic_set_get_dim(bset);
+	bset = isl_basic_set_params(bset);
+	dim = isl_basic_set_get_space(bset);
 	if (cst < 0)
-		qp = isl_qpolynomial_infty(dim);
+		qp = isl_qpolynomial_infty_on_domain(dim);
 	else if (cst == 0)
-		qp = isl_qpolynomial_zero(dim);
+		qp = isl_qpolynomial_zero_on_domain(dim);
 	else
-		qp = isl_qpolynomial_one(dim);
+		qp = isl_qpolynomial_one_on_domain(dim);
 	return isl_pw_qpolynomial_alloc(isl_set_from_basic_set(bset), qp);
 }
 
@@ -4230,7 +4321,7 @@ static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call(
 	__isl_give isl_pw_qpolynomial *(*fn)(__isl_take isl_basic_set *bset))
 {
 	int i, n;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_set *set;
 	isl_factorizer *f;
 	isl_qpolynomial *qp;
@@ -4249,10 +4340,10 @@ static __isl_give isl_pw_qpolynomial *compressed_multiplicative_call(
 	nparam = isl_basic_set_dim(bset, isl_dim_param);
 	nvar = isl_basic_set_dim(bset, isl_dim_set);
 
-	dim = isl_basic_set_get_dim(bset);
-	dim = isl_dim_domain(dim);
-	set = isl_set_universe(isl_dim_copy(dim));
-	qp = isl_qpolynomial_one(dim);
+	dim = isl_basic_set_get_space(bset);
+	dim = isl_space_domain(dim);
+	set = isl_set_universe(isl_space_copy(dim));
+	qp = isl_qpolynomial_one_on_domain(dim);
 	pwqp = isl_pw_qpolynomial_alloc(set, qp);
 
 	bset = isl_morph_basic_set(isl_morph_copy(f->morph), bset);
@@ -4300,7 +4391,6 @@ __isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call(
 	int bounded;
 	isl_morph *morph;
 	isl_pw_qpolynomial *pwqp;
-	unsigned orig_nvar, final_nvar;
 
 	if (!bset)
 		return NULL;
@@ -4308,9 +4398,7 @@ __isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call(
 	if (isl_basic_set_plain_is_empty(bset))
 		return constant_on_domain(bset, 0);
 
-	orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
-
-	if (orig_nvar == 0)
+	if (isl_basic_set_dim(bset, isl_dim_set) == 0)
 		return constant_on_domain(bset, 1);
 
 	bounded = isl_basic_set_is_bounded(bset);
@@ -4325,15 +4413,13 @@ __isl_give isl_pw_qpolynomial *isl_basic_set_multiplicative_call(
 	morph = isl_basic_set_full_compression(bset);
 	bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
 
-	final_nvar = isl_basic_set_dim(bset, isl_dim_set);
-
 	pwqp = compressed_multiplicative_call(bset, fn);
 
-	morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
-	morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
+	morph = isl_morph_dom_params(morph);
+	morph = isl_morph_ran_params(morph);
 	morph = isl_morph_inverse(morph);
 
-	pwqp = isl_pw_qpolynomial_morph(pwqp, morph);
+	pwqp = isl_pw_qpolynomial_morph_domain(pwqp, morph);
 
 	return pwqp;
 error:
@@ -4437,7 +4523,7 @@ static __isl_give isl_qpolynomial *make_divs_pos(__isl_take isl_qpolynomial *qp,
 	if (!qp->div)
 		goto error;
 
-	total = isl_dim_total(qp->dim);
+	total = isl_space_dim(qp->dim, isl_dim_all);
 	v = isl_vec_alloc(qp->div->ctx, qp->div->n_col - 1);
 
 	for (i = 0; i < qp->div->n_row; ++i) {
@@ -4554,7 +4640,7 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial(
 		return NULL;
 
 	data.sign = sign;
-	data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_dim(pwqp));
+	data.res = isl_pw_qpolynomial_zero(isl_pw_qpolynomial_get_space(pwqp));
 
 	for (i = 0; i < pwqp->n; ++i) {
 		if (pwqp->p[i].qp->div->n_row == 0) {
@@ -4611,7 +4697,7 @@ __isl_give isl_basic_map *isl_basic_map_from_qpolynomial(
 	__isl_take isl_qpolynomial *qp)
 {
 	int i, k;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_vec *aff = NULL;
 	isl_basic_map *bmap = NULL;
 	unsigned pos;
@@ -4625,12 +4711,10 @@ __isl_give isl_basic_map *isl_basic_map_from_qpolynomial(
 	aff = isl_qpolynomial_extract_affine(qp);
 	if (!aff)
 		goto error;
-	dim = isl_qpolynomial_get_dim(qp);
-	dim = isl_dim_from_domain(dim);
-	pos = 1 + isl_dim_offset(dim, isl_dim_out);
-	dim = isl_dim_add(dim, isl_dim_out, 1);
+	dim = isl_qpolynomial_get_space(qp);
+	pos = 1 + isl_space_offset(dim, isl_dim_out);
 	n_div = qp->div->n_row;
-	bmap = isl_basic_map_alloc_dim(dim, n_div, 1, 2 * n_div);
+	bmap = isl_basic_map_alloc_space(dim, n_div, 1, 2 * n_div);
 
 	for (i = 0; i < n_div; ++i) {
 		k = isl_basic_map_alloc_div(bmap);