X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=basis_reduction_templ.c;h=7f4b28f06c9fc95557fc06e1e27d8ef4d2aa01e6;hb=refs%2Ftags%2Faccepted%2Ftizen%2F20130912.195944;hp=bd5f842632a95e3e48ee8ba84ebb9b41af5c6485;hpb=ec21e6de21d784ee1ba32689aebcbda9f786fd30;p=platform%2Fupstream%2Fisl.git

diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c
index bd5f842..7f4b28f 100644
--- a/basis_reduction_templ.c
+++ b/basis_reduction_templ.c
@@ -1,4 +1,19 @@
+/*
+ * Copyright 2006-2007 Universiteit Leiden
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * Use of this software is governed by the MIT license
+ *
+ * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
+ * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
+ * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
+ * B-3001 Leuven, Belgium
+ */
+
 #include <stdlib.h>
+#include <isl_ctx_private.h>
+#include <isl_map_private.h>
+#include <isl_options_private.h>
 #include "isl_basis_reduction.h"
 
 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
@@ -10,7 +25,7 @@ static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
 }
 
 /* Compute a reduced basis for the set represented by the tableau "tab".
- * tab->basis, must be initialized by the calling function to an affine
+ * tab->basis, which must be initialized by the calling function to an affine
  * unimodular basis, is updated to reflect the reduced basis.
  * The first tab->n_zero rows of the basis (ignoring the constant row)
  * are assumed to correspond to equalities and are left untouched.
@@ -26,7 +41,7 @@ static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
  *  for Integer Programming" of Cook el al. to compute a reduced basis.
  * We use \epsilon = 1/4.
  *
- * If ctx->gbr_only_first is set, the user is only interested
+ * If ctx->opt->gbr_only_first is set, the user is only interested
  * in the first direction.  In this case we stop the basis reduction when
  * the width in the first direction becomes smaller than 2.
  */
@@ -56,11 +71,16 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
 	int fixed_saved = 0;
 	int mu_fixed[2];
 	int n_bounded;
+	int gbr_only_first;
 
 	if (!tab)
 		return NULL;
 
+	if (tab->empty)
+		return tab;
+
 	ctx = tab->mat->ctx;
+	gbr_only_first = ctx->opt->gbr_only_first;
 	dim = tab->n_var;
 	B = tab->basis;
 	if (!B)
@@ -225,7 +245,7 @@ struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
 				--i;
 			} else {
 				GBR_set(F[tab->n_zero], F_new);
-				if (ctx->gbr_only_first && GBR_lt(F[tab->n_zero], two))
+				if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
 					break;
 
 				if (fixed) {
@@ -285,15 +305,46 @@ error:
 	return tab;
 }
 
+/* Compute an affine form of a reduced basis of the given basic
+ * non-parametric set, which is assumed to be bounded and not
+ * include any integer divisions.
+ * The first column and the first row correspond to the constant term.
+ *
+ * If the input contains any equalities, we first create an initial
+ * basis with the equalities first.  Otherwise, we start off with
+ * the identity matrix.
+ */
 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 {
 	struct isl_mat *basis;
 	struct isl_tab *tab;
 
-	isl_assert(bset->ctx, bset->n_eq == 0, return NULL);
+	if (!bset)
+		return NULL;
+
+	if (isl_basic_set_dim(bset, isl_dim_div) != 0)
+		isl_die(bset->ctx, isl_error_invalid,
+			"no integer division allowed", return NULL);
+	if (isl_basic_set_dim(bset, isl_dim_param) != 0)
+		isl_die(bset->ctx, isl_error_invalid,
+			"no parameters allowed", return NULL);
 
-	tab = isl_tab_from_basic_set(bset);
-	tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
+	tab = isl_tab_from_basic_set(bset, 0);
+	if (!tab)
+		return NULL;
+
+	if (bset->n_eq == 0)
+		tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
+	else {
+		isl_mat *eq;
+		unsigned nvar = isl_basic_set_total_dim(bset);
+		eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
+					1, nvar);
+		eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis);
+		tab->basis = isl_mat_lin_to_aff(tab->basis);
+		tab->n_zero = bset->n_eq;
+		isl_mat_free(eq);
+	}
 	tab = isl_tab_compute_reduced_basis(tab);
 	if (!tab)
 		return NULL;