X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=basis_reduction_tab.c;h=6c7b040370f396b5e1af06741aa928322d1578c4;hb=7bc3560a92635b5dcf7eb9e7329992fc935a1ce2;hp=29b4ef6947ad9d6006b68338fb0a477e68efd4bc;hpb=40b68affd1cac1feb20f5203f917df7dc75639d0;p=platform%2Fupstream%2Fisl.git

diff --git a/basis_reduction_tab.c b/basis_reduction_tab.c
index 29b4ef6..6c7b040 100644
--- a/basis_reduction_tab.c
+++ b/basis_reduction_tab.c
@@ -1,4 +1,15 @@
+/*
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * Use of this software is governed by the MIT license
+ *
+ * Written by Sven Verdoolaege, K.U.Leuven, Departement
+ * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
+ */
+
 #include <assert.h>
+#include <isl_map_private.h>
+#include <isl/seq.h>
 #include "isl_tab.h"
 
 struct tab_lp {
@@ -9,19 +20,25 @@ struct tab_lp {
 	isl_int		*obj;
 	isl_int		 opt;
 	isl_int		 opt_denom;
+	isl_int		 tmp;
+	isl_int		 tmp2;
 	int	         neq;
 	unsigned	 dim;
-	int		 n_ineq;
+	/* number of constraints in initial product tableau */
+	int		 con_offset;
+	/* objective function has fixed or no integer value */
+	int		 is_fixed;
 };
 
-static struct tab_lp *init_lp(struct isl_basic_set *bset);
+static struct tab_lp *init_lp(struct isl_tab *tab);
 static void set_lp_obj(struct tab_lp *lp, isl_int *row, int dim);
 static int solve_lp(struct tab_lp *lp);
 static void get_obj_val(struct tab_lp* lp, mpq_t *F);
 static void delete_lp(struct tab_lp *lp);
 static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim);
 static void get_alpha(struct tab_lp* lp, int row, mpq_t *alpha);
-static void del_lp_row(struct tab_lp *lp);
+static int del_lp_row(struct tab_lp *lp) WARN_UNUSED;
+static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row);
 
 #define GBR_LP			    	    struct tab_lp
 #define GBR_type		    	    mpq_t
@@ -31,6 +48,7 @@ static void del_lp_row(struct tab_lp *lp);
 #define GBR_set_ui(a,b)			    mpq_set_ui(a,b,1)
 #define GBR_mul(a,b,c)			    mpq_mul(a,b,c)
 #define GBR_lt(a,b)			    (mpq_cmp(a,b) < 0)
+#define GBR_is_zero(a)			    (mpq_sgn(a) == 0)
 #define GBR_floor(a,b)			    mpz_fdiv_q(a,mpq_numref(b),mpq_denref(b))
 #define GBR_ceil(a,b)			    mpz_cdiv_q(a,mpq_numref(b),mpq_denref(b))
 #define GBR_lp_init(P)		    	    init_lp(P)
@@ -41,61 +59,51 @@ static void del_lp_row(struct tab_lp *lp);
 #define GBR_lp_next_row(lp)		    lp->neq
 #define GBR_lp_add_row(lp, row, dim)	    add_lp_row(lp, row, dim)
 #define GBR_lp_get_alpha(lp, row, alpha)    get_alpha(lp, row, alpha)
-#define GBR_lp_del_row(lp)		    del_lp_row(lp);
+#define GBR_lp_del_row(lp)		    del_lp_row(lp)
+#define GBR_lp_is_fixed(lp)		    (lp)->is_fixed
+#define GBR_lp_cut(lp, obj)	    	    cut_lp_to_hyperplane(lp, obj)
 #include "basis_reduction_templ.c"
 
 /* Set up a tableau for the Cartesian product of bset with itself.
  * This could be optimized by first setting up a tableau for bset
  * and then performing the Cartesian product on the tableau.
  */
-static struct isl_tab *gbr_tab(struct isl_basic_set *bset,
-	struct isl_vec *row)
+static struct isl_tab *gbr_tab(struct isl_tab *tab, struct isl_vec *row)
 {
-	int i, j;
 	unsigned dim;
-	struct isl_tab *tab;
+	struct isl_tab *prod;
 
-	if (!bset || !row)
+	if (!tab || !row)
 		return NULL;
 
-	dim = isl_basic_set_total_dim(bset);
-	tab = isl_tab_alloc(bset->ctx, 2 * bset->n_ineq + dim + 1, 2 * dim, 0);
-
-	for (i = 0; i < 2; ++i) {
-		isl_seq_clr(row->el + 1 + (1 - i) * dim, dim);
-		for (j = 0; j < bset->n_ineq; ++j) {
-			isl_int_set(row->el[0], bset->ineq[j][0]);
-			isl_seq_cpy(row->el + 1 + i * dim,
-				    bset->ineq[j] + 1, dim);
-			tab = isl_tab_add_ineq(tab, row->el);
-			if (!tab || tab->empty)
-				return tab;
-		}
+	dim = tab->n_var;
+	prod = isl_tab_product(tab, tab);
+	if (isl_tab_extend_cons(prod, 3 * dim + 1) < 0) {
+		isl_tab_free(prod);
+		return NULL;
 	}
-
-	return tab;
+	return prod;
 }
 
-static struct tab_lp *init_lp(struct isl_basic_set *bset)
+static struct tab_lp *init_lp(struct isl_tab *tab)
 {
 	struct tab_lp *lp = NULL;
 
-	if (!bset)
+	if (!tab)
 		return NULL;
 
-	isl_assert(bset->ctx, bset->n_eq == 0, return NULL);
-
-	lp = isl_calloc_type(bset->ctx, struct tab_lp);
+	lp = isl_calloc_type(tab->mat->ctx, struct tab_lp);
 	if (!lp)
 		return NULL;
 
 	isl_int_init(lp->opt);
 	isl_int_init(lp->opt_denom);
+	isl_int_init(lp->tmp);
+	isl_int_init(lp->tmp2);
 
-	lp->dim = isl_basic_set_total_dim(bset);
-	lp->n_ineq = bset->n_ineq;
+	lp->dim = tab->n_var;
 
-	lp->ctx = bset->ctx;
+	lp->ctx = tab->mat->ctx;
 	isl_ctx_ref(lp->ctx);
 
 	lp->stack = isl_alloc_array(lp->ctx, struct isl_tab_undo *, lp->dim);
@@ -103,9 +111,10 @@ static struct tab_lp *init_lp(struct isl_basic_set *bset)
 	lp->row = isl_vec_alloc(lp->ctx, 1 + 2 * lp->dim);
 	if (!lp->row)
 		goto error;
-	lp->tab = gbr_tab(bset, lp->row);
+	lp->tab = gbr_tab(tab, lp->row);
 	if (!lp->tab)
 		goto error;
+	lp->con_offset = lp->tab->n_con;
 	lp->obj = NULL;
 	lp->neq = 0;
 
@@ -125,6 +134,8 @@ static int solve_lp(struct tab_lp *lp)
 	enum isl_lp_result res;
 	unsigned flags = 0;
 
+	lp->is_fixed = 0;
+
 	isl_int_set_si(lp->row->el[0], 0);
 	isl_seq_cpy(lp->row->el + 1, lp->obj, lp->dim);
 	isl_seq_neg(lp->row->el + 1 + lp->dim, lp->obj, lp->dim);
@@ -132,11 +143,56 @@ static int solve_lp(struct tab_lp *lp)
 		flags = ISL_TAB_SAVE_DUAL;
 	res = isl_tab_min(lp->tab, lp->row->el, lp->ctx->one,
 			  &lp->opt, &lp->opt_denom, flags);
+	isl_int_mul_ui(lp->opt_denom, lp->opt_denom, 2);
+	if (isl_int_abs_lt(lp->opt, lp->opt_denom)) {
+		struct isl_vec *sample = isl_tab_get_sample_value(lp->tab);
+		if (!sample)
+			return -1;
+		isl_seq_inner_product(lp->obj, sample->el + 1, lp->dim, &lp->tmp);
+		isl_seq_inner_product(lp->obj, sample->el + 1 + lp->dim, lp->dim, &lp->tmp2);
+		isl_int_cdiv_q(lp->tmp, lp->tmp, sample->el[0]);
+		isl_int_fdiv_q(lp->tmp2, lp->tmp2, sample->el[0]);
+		if (isl_int_ge(lp->tmp, lp->tmp2))
+			lp->is_fixed = 1;
+		isl_vec_free(sample);
+	}
+	isl_int_divexact_ui(lp->opt_denom, lp->opt_denom, 2);
 	if (res != isl_lp_ok)
 		return -1;
 	return 0;
 }
 
+/* The current objective function has a fixed (or no) integer value.
+ * Cut the tableau to the hyperplane that fixes this value in
+ * both halves of the tableau.
+ * Return 1 if the resulting tableau is empty.
+ */
+static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row)
+{
+	enum isl_lp_result res;
+
+	isl_int_set_si(lp->row->el[0], 0);
+	isl_seq_cpy(lp->row->el + 1, row, lp->dim);
+	isl_seq_clr(lp->row->el + 1 + lp->dim, lp->dim);
+	res = isl_tab_min(lp->tab, lp->row->el, lp->ctx->one,
+			  &lp->tmp, NULL, 0);
+	if (res != isl_lp_ok)
+		return -1;
+
+	isl_int_neg(lp->row->el[0], lp->tmp);
+	if (isl_tab_add_eq(lp->tab, lp->row->el) < 0)
+		return -1;
+
+	isl_seq_cpy(lp->row->el + 1 + lp->dim, row, lp->dim);
+	isl_seq_clr(lp->row->el + 1, lp->dim);
+	if (isl_tab_add_eq(lp->tab, lp->row->el) < 0)
+		return -1;
+
+	lp->con_offset += 2;
+
+	return lp->tab->empty;
+}
+
 static void get_obj_val(struct tab_lp* lp, mpq_t *F)
 {
 	isl_int_neg(mpq_numref(*F), lp->opt);
@@ -150,6 +206,8 @@ static void delete_lp(struct tab_lp *lp)
 
 	isl_int_clear(lp->opt);
 	isl_int_clear(lp->opt_denom);
+	isl_int_clear(lp->tmp);
+	isl_int_clear(lp->tmp2);
 	isl_vec_free(lp->row);
 	free(lp->stack);
 	isl_tab_free(lp->tab);
@@ -165,20 +223,21 @@ static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim)
 	isl_seq_cpy(lp->row->el + 1, row, lp->dim);
 	isl_seq_neg(lp->row->el + 1 + lp->dim, row, lp->dim);
 
-	lp->tab = isl_tab_add_valid_eq(lp->tab, lp->row->el);
+	if (isl_tab_add_valid_eq(lp->tab, lp->row->el) < 0)
+		return -1;
 
 	return lp->neq++;
 }
 
 static void get_alpha(struct tab_lp* lp, int row, mpq_t *alpha)
 {
-	row += 2 * lp->n_ineq;
+	row += lp->con_offset;
 	isl_int_neg(mpq_numref(*alpha), lp->tab->dual->el[1 + row]);
 	isl_int_set(mpq_denref(*alpha), lp->tab->dual->el[0]);
 }
 
-static void del_lp_row(struct tab_lp *lp)
+static int del_lp_row(struct tab_lp *lp)
 {
 	lp->neq--;
-	isl_tab_rollback(lp->tab, lp->stack[lp->neq]);
+	return isl_tab_rollback(lp->tab, lp->stack[lp->neq]);
 }