X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_morph.c;h=9fc39d2e0ad28194e6aa4442bb432e2d850f73c0;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=8bc4db82eeeee7e67786fb29a5216298b90ac2aa;hpb=093abd9827a83a22e2f06ff1e0f6f14d8ed9245c;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_morph.c b/isl_morph.c
index 8bc4db8..9fc39d2 100644
--- a/isl_morph.c
+++ b/isl_morph.c
@@ -1,18 +1,18 @@
 /*
  * 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,
  * 91893 Orsay, France 
  */
 
-#include <isl_morph.h>
-#include <isl_seq.h>
 #include <isl_map_private.h>
+#include <isl_morph.h>
+#include <isl/seq.h>
 #include <isl_mat_private.h>
-#include <isl_dim_private.h>
+#include <isl_space_private.h>
 #include <isl_equalities.h>
 
 __isl_give isl_morph *isl_morph_alloc(
@@ -88,12 +88,12 @@ void isl_morph_free(__isl_take isl_morph *morph)
 	free(morph);
 }
 
-__isl_give isl_dim *isl_morph_get_ran_dim(__isl_keep isl_morph *morph)
+__isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph)
 {
 	if (!morph)
 		return NULL;
 	
-	return isl_dim_copy(morph->ran->dim);
+	return isl_space_copy(morph->ran->dim);
 }
 
 unsigned isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
@@ -124,9 +124,9 @@ __isl_give isl_morph *isl_morph_remove_dom_dims(__isl_take isl_morph *morph,
 	if (!morph)
 		return NULL;
 
-	dom_offset = 1 + isl_dim_offset(morph->dom->dim, type);
+	dom_offset = 1 + isl_space_offset(morph->dom->dim, type);
 
-	morph->dom = isl_basic_set_remove(morph->dom, type, first, n);
+	morph->dom = isl_basic_set_remove_dims(morph->dom, type, first, n);
 
 	morph->map = isl_mat_drop_cols(morph->map, dom_offset + first, n);
 
@@ -151,9 +151,9 @@ __isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph,
 	if (!morph)
 		return NULL;
 
-	ran_offset = 1 + isl_dim_offset(morph->ran->dim, type);
+	ran_offset = 1 + isl_space_offset(morph->ran->dim, type);
 
-	morph->ran = isl_basic_set_remove(morph->ran, type, first, n);
+	morph->ran = isl_basic_set_remove_dims(morph->ran, type, first, n);
 
 	morph->map = isl_mat_drop_rows(morph->map, ran_offset + first, n);
 
@@ -166,15 +166,62 @@ __isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph,
 	return NULL;
 }
 
-void isl_morph_dump(__isl_take isl_morph *morph, FILE *out)
+/* Project domain of morph onto its parameter domain.
+ */
+__isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph)
+{
+	unsigned n;
+
+	morph = isl_morph_cow(morph);
+	if (!morph)
+		return NULL;
+	n = isl_basic_set_dim(morph->dom, isl_dim_set);
+	morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, n);
+	if (!morph)
+		return NULL;
+	morph->dom = isl_basic_set_params(morph->dom);
+	if (morph->dom)
+		return morph;
+
+	isl_morph_free(morph);
+	return NULL;
+}
+
+/* Project range of morph onto its parameter domain.
+ */
+__isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph)
+{
+	unsigned n;
+
+	morph = isl_morph_cow(morph);
+	if (!morph)
+		return NULL;
+	n = isl_basic_set_dim(morph->ran, isl_dim_set);
+	morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, n);
+	if (!morph)
+		return NULL;
+	morph->ran = isl_basic_set_params(morph->ran);
+	if (morph->ran)
+		return morph;
+
+	isl_morph_free(morph);
+	return NULL;
+}
+
+void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out)
 {
 	if (!morph)
 		return;
 
 	isl_basic_set_print(morph->dom, out, 0, "", "", ISL_FORMAT_ISL);
 	isl_basic_set_print(morph->ran, out, 0, "", "", ISL_FORMAT_ISL);
-	isl_mat_dump(morph->map, out, 4);
-	isl_mat_dump(morph->inv, out, 4);
+	isl_mat_print_internal(morph->map, out, 4);
+	isl_mat_print_internal(morph->inv, out, 4);
+}
+
+void isl_morph_dump(__isl_take isl_morph *morph)
+{
+	isl_morph_print_internal(morph, stderr);
 }
 
 __isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset)
@@ -188,7 +235,7 @@ __isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset)
 
 	total = isl_basic_set_total_dim(bset);
 	id = isl_mat_identity(bset->ctx, 1 + total);
-	universe = isl_basic_set_universe(isl_dim_copy(bset->dim));
+	universe = isl_basic_set_universe(isl_space_copy(bset->dim));
 
 	return isl_morph_alloc(universe, isl_basic_set_copy(universe),
 		id, isl_mat_copy(id));
@@ -208,7 +255,7 @@ __isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_set *bset)
 
 	total = isl_basic_set_total_dim(bset);
 	id = isl_mat_identity(bset->ctx, 1 + total);
-	empty = isl_basic_set_empty(isl_dim_copy(bset->dim));
+	empty = isl_basic_set_empty(isl_space_copy(bset->dim));
 
 	return isl_morph_alloc(empty, isl_basic_set_copy(empty),
 		id, isl_mat_copy(id));
@@ -253,7 +300,7 @@ static __isl_give isl_basic_set *copy_equalities(__isl_keep isl_basic_set *bset,
 	isl_assert(bset->ctx, bset->n_div == 0, return NULL);
 
 	total = isl_basic_set_total_dim(bset);
-	eq = isl_basic_set_alloc_dim(isl_dim_copy(bset->dim), 0, n, 0);
+	eq = isl_basic_set_alloc_space(isl_space_copy(bset->dim), 0, n, 0);
 	if (!eq)
 		return NULL;
 	for (i = 0; i < n; ++i) {
@@ -269,7 +316,7 @@ error:
 	return NULL;
 }
 
-/* Given a basic set, exploit the equalties in the a basic set to construct
+/* Given a basic set, exploit the equalties in the basic set to construct
  * a morphishm that maps the basic set to a lower-dimensional space.
  * Specifically, the morphism reduces the number of dimensions of type "type".
  *
@@ -326,21 +373,20 @@ __isl_give isl_morph *isl_basic_set_variable_compression(
 	unsigned ntype;
 	unsigned orest;
 	unsigned nrest;
-	unsigned total;
 	int f_eq, n_eq;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_mat *H, *U, *Q, *C = NULL, *H1, *U1, *U2;
 	isl_basic_set *dom, *ran;
 
 	if (!bset)
 		return NULL;
 
-	if (isl_basic_set_fast_is_empty(bset))
+	if (isl_basic_set_plain_is_empty(bset))
 		return isl_morph_empty(bset);
 
 	isl_assert(bset->ctx, bset->n_div == 0, return NULL);
 
-	otype = 1 + isl_dim_offset(bset->dim, type);
+	otype = 1 + isl_space_offset(bset->dim, type);
 	ntype = isl_basic_set_dim(bset, type);
 	orest = otype + ntype;
 	nrest = isl_basic_set_total_dim(bset) - (orest - 1);
@@ -354,7 +400,7 @@ __isl_give isl_morph *isl_basic_set_variable_compression(
 	if (n_eq == 0)
 		return isl_morph_identity(bset);
 
-	H = isl_mat_sub_alloc(bset->ctx, bset->eq, f_eq, n_eq, otype, ntype);
+	H = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, otype, ntype);
 	H = isl_mat_left_hermite(H, 0, &U, &Q);
 	if (!H || !U || !Q)
 		goto error;
@@ -367,7 +413,7 @@ __isl_give isl_morph *isl_basic_set_variable_compression(
 	isl_int_set_si(C->row[0][0], 1);
 	isl_seq_clr(C->row[0] + 1, otype - 1);
 	isl_mat_sub_neg(C->ctx, C->row + 1, bset->eq + f_eq, n_eq, 0, 0, otype);
-	H1 = isl_mat_sub_alloc(H->ctx, H->row, 0, H->n_row, 0, H->n_row);
+	H1 = isl_mat_sub_alloc(H, 0, H->n_row, 0, H->n_row);
 	H1 = isl_mat_lin_to_aff(H1);
 	C = isl_mat_inverse_product(H1, C);
 	if (!C)
@@ -397,9 +443,9 @@ __isl_give isl_morph *isl_basic_set_variable_compression(
 		C = isl_mat_normalize(C);
 	}
 
-	U1 = isl_mat_sub_alloc(U->ctx, U->row, 0, U->n_row, 0, n_eq);
+	U1 = isl_mat_sub_alloc(U, 0, U->n_row, 0, n_eq);
 	U1 = isl_mat_lin_to_aff(U1);
-	U2 = isl_mat_sub_alloc(U->ctx, U->row, 0, U->n_row, n_eq, U->n_row - n_eq);
+	U2 = isl_mat_sub_alloc(U, 0, U->n_row, n_eq, U->n_row - n_eq);
 	U2 = isl_mat_lin_to_aff(U2);
 	isl_mat_free(U);
 
@@ -408,9 +454,9 @@ __isl_give isl_morph *isl_basic_set_variable_compression(
 	C = insert_parameter_rows(C, otype - 1);
 	C = isl_mat_diagonal(C, isl_mat_identity(bset->ctx, nrest));
 
-	dim = isl_dim_copy(bset->dim);
-	dim = isl_dim_drop(dim, type, 0, ntype);
-	dim = isl_dim_add(dim, type, ntype - n_eq);
+	dim = isl_space_copy(bset->dim);
+	dim = isl_space_drop_dims(dim, type, 0, ntype);
+	dim = isl_space_add_dims(dim, type, ntype - n_eq);
 	ran = isl_basic_set_universe(dim);
 	dom = copy_equalities(bset, f_eq, n_eq);
 
@@ -427,6 +473,10 @@ error:
  * We basically just call isl_mat_parameter_compression with the right input
  * and then extend the resulting matrix to include the variables.
  *
+ * The implementation assumes that "bset" does not have any equalities
+ * that only involve the parameters and that isl_basic_set_gauss has
+ * been applied to "bset".
+ *
  * Let the equalities be given as
  *
  *	B(p) + A x = 0
@@ -452,7 +502,7 @@ __isl_give isl_morph *isl_basic_set_parameter_compression(
 	if (!bset)
 		return NULL;
 
-	if (isl_basic_set_fast_is_empty(bset))
+	if (isl_basic_set_plain_is_empty(bset))
 		return isl_morph_empty(bset);
 	if (bset->n_eq == 0)
 		return isl_morph_identity(bset);
@@ -463,18 +513,25 @@ __isl_give isl_morph *isl_basic_set_parameter_compression(
 	nparam = isl_basic_set_dim(bset, isl_dim_param);
 	nvar = isl_basic_set_dim(bset, isl_dim_set);
 
-	isl_assert(bset->ctx, n_eq <= nvar, return NULL);
+	if (isl_seq_first_non_zero(bset->eq[bset->n_eq - 1] + 1 + nparam,
+				    nvar) == -1)
+		isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
+			"input not allowed to have parameter equalities",
+			return NULL);
+	if (n_eq > nvar)
+		isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
+			"input not gaussed", return NULL);
 
 	d = isl_vec_alloc(bset->ctx, n_eq);
-	B = isl_mat_sub_alloc(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam);
-	H = isl_mat_sub_alloc(bset->ctx, bset->eq, 0, n_eq, 1 + nparam, nvar);
+	B = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam);
+	H = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 1 + nparam, nvar);
 	H = isl_mat_left_hermite(H, 0, NULL, NULL);
 	H = isl_mat_drop_cols(H, n_eq, nvar - n_eq);
 	H = isl_mat_lin_to_aff(H);
 	H = isl_mat_right_inverse(H);
 	if (!H || !d)
 		goto error;
-	isl_seq_set(d->el, H->row[0][0], d->size);
+	d = isl_vec_set(d, H->row[0][0]);
 	H = isl_mat_drop_rows(H, 0, 1);
 	H = isl_mat_drop_cols(H, 0, 1);
 	B = isl_mat_product(H, B);
@@ -482,8 +539,8 @@ __isl_give isl_morph *isl_basic_set_parameter_compression(
 	inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar));
 	map = isl_mat_right_inverse(isl_mat_copy(inv));
 
-	dom = isl_basic_set_universe(isl_dim_copy(bset->dim));
-	ran = isl_basic_set_universe(isl_dim_copy(bset->dim));
+	dom = isl_basic_set_universe(isl_space_copy(bset->dim));
+	ran = isl_basic_set_universe(isl_space_copy(bset->dim));
 
 	return isl_morph_alloc(dom, ran, map, inv);
 error:
@@ -535,6 +592,7 @@ static __isl_give isl_basic_set *add_strides(__isl_take isl_basic_set *bset,
 		div = isl_basic_set_alloc_div(bset);
 		if (div < 0)
 			goto error;
+		isl_int_set_si(bset->div[div][0], 0);
 		k = isl_basic_set_alloc_equality(bset);
 		if (k < 0)
 			goto error;
@@ -570,20 +628,20 @@ __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph,
 	if (!morph || !bset)
 		goto error;
 
-	isl_assert(bset->ctx, isl_dim_equal(bset->dim, morph->dom->dim),
+	isl_assert(bset->ctx, isl_space_is_equal(bset->dim, morph->dom->dim),
 		    goto error);
 
 	max_stride = morph->inv->n_row - 1;
 	if (isl_int_is_one(morph->inv->row[0][0]))
 		max_stride = 0;
-	res = isl_basic_set_alloc_dim(isl_dim_copy(morph->ran->dim),
+	res = isl_basic_set_alloc_space(isl_space_copy(morph->ran->dim),
 		bset->n_div + max_stride, bset->n_eq + max_stride, bset->n_ineq);
 
 	for (i = 0; i < bset->n_div; ++i)
 		if (isl_basic_set_alloc_div(res) < 0)
 			goto error;
 
-	mat = isl_mat_sub_alloc(bset->ctx, bset->eq, 0, bset->n_eq,
+	mat = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
 					0, morph->inv->n_row);
 	mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
 	if (!mat)
@@ -598,7 +656,7 @@ __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph,
 	}
 	isl_mat_free(mat);
 
-	mat = isl_mat_sub_alloc(bset->ctx, bset->ineq, 0, bset->n_ineq,
+	mat = isl_mat_sub_alloc6(bset->ctx, bset->ineq, 0, bset->n_ineq,
 					0, morph->inv->n_row);
 	mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
 	if (!mat)
@@ -614,7 +672,7 @@ __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph,
 	}
 	isl_mat_free(mat);
 
-	mat = isl_mat_sub_alloc(bset->ctx, bset->div, 0, bset->n_div,
+	mat = isl_mat_sub_alloc6(bset->ctx, bset->div, 0, bset->n_div,
 					1, morph->inv->n_row);
 	mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
 	if (!mat)
@@ -631,6 +689,9 @@ __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph,
 
 	res = add_strides(res, morph);
 
+	if (isl_basic_set_is_rational(bset))
+		res = isl_basic_set_set_rational(res);
+
 	res = isl_basic_set_simplify(res);
 	res = isl_basic_set_finalize(res);
 
@@ -657,14 +718,14 @@ __isl_give isl_set *isl_morph_set(__isl_take isl_morph *morph,
 	if (!morph || !set)
 		goto error;
 
-	isl_assert(set->ctx, isl_dim_equal(set->dim, morph->dom->dim), goto error);
+	isl_assert(set->ctx, isl_space_is_equal(set->dim, morph->dom->dim), goto error);
 
 	set = isl_set_cow(set);
 	if (!set)
 		goto error;
 
-	isl_dim_free(set->dim);
-	set->dim = isl_dim_copy(morph->ran->dim);
+	isl_space_free(set->dim);
+	set->dim = isl_space_copy(morph->ran->dim);
 	if (!set->dim)
 		goto error;
 
@@ -735,12 +796,20 @@ __isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph)
 	return morph;
 }
 
+/* We detect all the equalities first to avoid implicit equalties
+ * being discovered during the computations.  In particular,
+ * the compression on the variables could expose additional stride
+ * constraints on the parameters.  This would result in existentially
+ * quantified variables after applying the resulting morph, which
+ * in turn could break invariants of the calling functions.
+ */
 __isl_give isl_morph *isl_basic_set_full_compression(
 	__isl_keep isl_basic_set *bset)
 {
 	isl_morph *morph, *morph2;
 
 	bset = isl_basic_set_copy(bset);
+	bset = isl_basic_set_detect_equalities(bset);
 
 	morph = isl_basic_set_variable_compression(bset, isl_dim_param);
 	bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
@@ -757,3 +826,19 @@ __isl_give isl_morph *isl_basic_set_full_compression(
 
 	return morph;
 }
+
+__isl_give isl_vec *isl_morph_vec(__isl_take isl_morph *morph,
+	__isl_take isl_vec *vec)
+{
+	if (!morph)
+		goto error;
+
+	vec = isl_mat_vec_product(isl_mat_copy(morph->map), vec);
+
+	isl_morph_free(morph);
+	return vec;
+error:
+	isl_morph_free(morph);
+	isl_vec_free(vec);
+	return NULL;
+}