X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_morph.c;h=3700874a6022a02b21a075f5dc201b1e7c9966d5;hb=63fb8a7f484648c3caa25351c8c94ac2395ec563;hp=a888f4cb9314b0d7f66e86182c3788c27bb56762;hpb=db847315005909df04467d48b2887b6496017bf6;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_morph.c b/isl_morph.c
index a888f4c..3700874 100644
--- a/isl_morph.c
+++ b/isl_morph.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,
@@ -316,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".
  *
@@ -473,25 +473,26 @@ error:
  * We basically just call isl_mat_parameter_compression with the right input
  * and then extend the resulting matrix to include the variables.
  *
- * Let the equalities be given as
+ * 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".
  *
- *	B(p) + A x = 0
+ * Let the equalities be given as
  *
- * and let [H 0] be the Hermite Normal Form of A, then
+ *	B(p) + A x = 0.
  *
- *	H^-1 B(p)
+ * We use isl_mat_parameter_compression_ext to compute the compression
  *
- * needs to be integer, so we impose that each row is divisible by
- * the denominator.
+ *	p = T p'.
  */
 __isl_give isl_morph *isl_basic_set_parameter_compression(
 	__isl_keep isl_basic_set *bset)
 {
 	unsigned nparam;
 	unsigned nvar;
+	unsigned n_div;
 	int n_eq;
 	isl_mat *H, *B;
-	isl_vec *d;
 	isl_mat *map, *inv;
 	isl_basic_set *dom, *ran;
 
@@ -503,28 +504,24 @@ __isl_give isl_morph *isl_basic_set_parameter_compression(
 	if (bset->n_eq == 0)
 		return isl_morph_identity(bset);
 
-	isl_assert(bset->ctx, bset->n_div == 0, return NULL);
-
 	n_eq = bset->n_eq;
 	nparam = isl_basic_set_dim(bset, isl_dim_param);
 	nvar = isl_basic_set_dim(bset, isl_dim_set);
+	n_div = isl_basic_set_dim(bset, isl_dim_div);
 
-	isl_assert(bset->ctx, n_eq <= nvar, return NULL);
+	if (isl_seq_first_non_zero(bset->eq[bset->n_eq - 1] + 1 + nparam,
+				    nvar + n_div) == -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 + n_div)
+		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_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);
-	H = isl_mat_drop_rows(H, 0, 1);
-	H = isl_mat_drop_cols(H, 0, 1);
-	B = isl_mat_product(H, B);
-	inv = isl_mat_parameter_compression(B, d);
+	H = isl_mat_sub_alloc6(bset->ctx, bset->eq,
+				0, n_eq, 1 + nparam, nvar + n_div);
+	inv = isl_mat_parameter_compression_ext(B, H);
 	inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar));
 	map = isl_mat_right_inverse(isl_mat_copy(inv));
 
@@ -532,11 +529,6 @@ __isl_give isl_morph *isl_basic_set_parameter_compression(
 	ran = isl_basic_set_universe(isl_space_copy(bset->dim));
 
 	return isl_morph_alloc(dom, ran, map, inv);
-error:
-	isl_mat_free(H);
-	isl_mat_free(B);
-	isl_vec_free(d);
-	return NULL;
 }
 
 /* Add stride constraints to "bset" based on the inverse mapping
@@ -562,6 +554,7 @@ error:
  *
  *	exists alpha in Z^m: B x = d alpha
  *
+ * This function is similar to add_strides in isl_affine_hull.c
  */
 static __isl_give isl_basic_set *add_strides(__isl_take isl_basic_set *bset,
 	__isl_keep isl_morph *morph)
@@ -581,6 +574,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;
@@ -784,12 +778,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);