X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp.c;h=4ff9f25351e6bbd117983625521baa1de52087e8;hb=5c4c889a99e6bd23a35e108b4b4e9a6cbd9e695b;hp=111bef007681240847a09609ed68b7efd564c4d3;hpb=bc6aa15e71b0fe97accfbe566c027049828ea513;p=libfirm

diff --git a/ir/be/becopyilp.c b/ir/be/becopyilp.c
index 111bef007..4ff9f2535 100644
--- a/ir/be/becopyilp.c
+++ b/ir/be/becopyilp.c
@@ -17,17 +17,20 @@
 
 #include "irprog.h"
 
-#include "lpp.h"
-#include "lpp_local.h"
-#include "lpp_remote.h"
+#include <lpp/lpp.h>
+#include <lpp/lpp_net.h>
 #include "xmalloc.h"
 #include "becopyopt.h"
 #include "becopystat.h"
+#include "besched_t.h"
+
+#define LPP_HOST "i44pc52"
+#define LPP_SOLVER "cplex"
 
 #undef DUMP_MPS
-#define DEBUG_LVL SET_LEVEL_1
 static firm_dbg_module_t *dbg = NULL;
 
+#define MAX(a,b) ((a<b)?(b):(a))
 #define EPSILON 0.00001
 #define SLOTS_LIVING 32
 
@@ -52,7 +55,7 @@ typedef struct _problem_instance_t {
 
 #define is_removed(irn) pset_find_ptr(pi->removed, irn)
 
-#define is_color_possible(irn,color) arch_reg_is_allocatable(pi->co->chordal_env->arch_env, irn, arch_pos_make_out(0), arch_register_for_index(pi->co->chordal_env->cls, color))
+#define is_color_possible(irn,color) arch_reg_is_allocatable(get_arch_env(pi->co), irn, arch_pos_make_out(0), arch_register_for_index(pi->co->chordal_env->cls, color))
 
 /*
  * Some stuff for variable name handling.
@@ -109,8 +112,8 @@ static void pi_find_simplicials(problem_instance_t *pi) {
 	while (redo) {
 		redo = 0;
 		for (ifn = set_first(if_nodes); ifn; ifn = set_next(if_nodes)) {
-			ir_node *irn = get_irn_for_graph_nr(pi->co->chordal_env->irg, ifn->nnr);
-			if (!is_removed(irn) && !is_optimizable(pi->co->chordal_env->arch_env, irn) &&
+			ir_node *irn = get_irn_for_graph_nr(get_irg(pi->co), ifn->nnr);
+			if (!is_removed(irn) && !is_optimizable(get_arch_env(pi->co), irn) &&
           !is_optimizable_arg(pi->co, irn) && pi_is_simplicial(pi, ifn)) {
 				simpl_t *s = xmalloc(sizeof(*s));
 				s->ifn = ifn;
@@ -145,15 +148,15 @@ static void pi_add_constr_A(problem_instance_t *pi) {
 
 				nnr = get_irn_graph_nr(curr->irn);
 				mangle_cst(pi->buf, 'A', nnr);
-				cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, equal, 1);
+				cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_equal, 1);
 
 				// iterate over all possible colors in order
 				bitset_clear_all(pos_regs);
-				arch_get_allocatable_regs(pi->co->chordal_env->arch_env, curr->irn, arch_pos_make_out(0), pi->co->chordal_env->cls, pos_regs);
+				arch_get_allocatable_regs(get_arch_env(pi->co), curr->irn, arch_pos_make_out(0), pi->co->chordal_env->cls, pos_regs);
 				bitset_foreach(pos_regs, col) {
 					int var_idx;
 					mangle_var(pi->buf, 'x', nnr, col);
-					var_idx = lpp_add_var(pi->curr_lp, pi->buf, binary, 0);
+					var_idx = lpp_add_var(pi->curr_lp, pi->buf, lpp_binary, 0);
 					pi->last_x_var = var_idx;
 					lpp_set_factor_fast(pi->curr_lp, cst_idx, var_idx, 1);
 				}
@@ -213,7 +216,7 @@ static void pi_add_constr_B(problem_instance_t *pi, int color) {
 					int cst_idx;
 					ir_node *n;
 					mangle_cst(pi->buf, 'B', pi->cst_counter);
-					cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, less, 1);
+					cst_idx = lpp_add_cst(pi->curr_lp, pi->buf, lpp_less, 1);
 					for (n = pset_first(living); n; n = pset_next(living)) {
 						int var_idx;
 						mangle_var_irn(pi->buf, 'x', n, color);
@@ -233,16 +236,16 @@ static void pi_add_constr_B(problem_instance_t *pi, int color) {
 
 /**
  * Generates constraints which interrelate x with y variables.
- * y=1 ==> x1 and x2 must have the same color.
- *     <== is achieved automatically by minimization.
+ * x1 and x2 have the different colors ==> y_12 = 1
  */
 static void pi_add_constr_E(problem_instance_t *pi) {
 	unit_t *curr;
-	bitset_t *root_regs, *arg_regs;
+	bitset_t *root_regs, *arg_regs, *work_regs;
 	int cst_counter = 0;
 	unsigned nregs = pi->co->chordal_env->cls->n_regs;
 	root_regs = bitset_alloca(nregs);
 	arg_regs = bitset_alloca(nregs);
+	work_regs = bitset_alloca(nregs);
 
 	DBG((dbg, LEVEL_2, "Add E constraints...\n"));
 	/* for all roots of optimization units */
@@ -255,25 +258,27 @@ static void pi_add_constr_E(problem_instance_t *pi) {
 		root = curr->nodes[0];
 		rootnr = get_irn_graph_nr(root);
 		bitset_clear_all(root_regs);
-		arch_get_allocatable_regs(pi->co->chordal_env->arch_env, root, arch_pos_make_out(0), pi->co->chordal_env->cls, root_regs);
+		arch_get_allocatable_regs(get_arch_env(pi->co), root, arch_pos_make_out(0), pi->co->chordal_env->cls, root_regs);
 
 		/* for all arguments of root */
 		for (i = 1; i < curr->node_count; ++i) {
 			arg = curr->nodes[i];
 			argnr = get_irn_graph_nr(arg);
 			bitset_clear_all(arg_regs);
-			arch_get_allocatable_regs(pi->co->chordal_env->arch_env, arg, arch_pos_make_out(0), pi->co->chordal_env->cls, arg_regs);
+			arch_get_allocatable_regs(get_arch_env(pi->co), arg, arch_pos_make_out(0), pi->co->chordal_env->cls, arg_regs);
 
 			/* Introduce new variable and set factor in objective function */
 			mangle_var(buf, 'y', rootnr, argnr);
-			y_idx = lpp_add_var(pi->curr_lp, buf, continous, curr->costs[i]);
+			y_idx = lpp_add_var(pi->curr_lp, buf, lpp_continous, curr->costs[i]);
 
+			//BETTER: y vars as binary or continous	vars ??
 			/* set starting value */
 			//lpp_set_start_value(pi->curr_lp, y_idx, (get_irn_col(pi->co, root) != get_irn_col(pi->co, arg)));
 
 			/* For all colors root and arg have in common, add 2 constraints to E */
-			bitset_and(arg_regs, root_regs);
-			bitset_foreach(arg_regs, color) {
+			bitset_copy(work_regs, root_regs);
+			bitset_and(work_regs, arg_regs);
+			bitset_foreach(work_regs, color) {
 				int root_idx, arg_idx, cst_idx;
 				mangle_var(buf, 'x', rootnr, color);
 				root_idx = lpp_get_var_idx(pi->curr_lp, buf);
@@ -282,31 +287,58 @@ static void pi_add_constr_E(problem_instance_t *pi) {
 
 				/* add root-arg-y <= 0 */
 				mangle_cst(buf, 'E', cst_counter++);
-				cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0);
+				cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0);
 				lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1);
 				lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, -1);
 				lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 
 				/* add arg-root-y <= 0 */
 				mangle_cst(buf, 'E', cst_counter++);
-				cst_idx = lpp_add_cst(pi->curr_lp, buf, less, 0);
+				cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0);
 				lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, -1);
 				lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1);
 				lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
 			}
+			/* For all colors root and arg have "disjunct", add 1 constraints to E.
+			 * If root gets a color the arg is not possible to get then they will
+			 * definetly get different colors. So y has to be 1.
+			 * Vice versa for arg.
+			 */
+			bitset_copy(work_regs, root_regs);
+			bitset_xor(work_regs, arg_regs);
+			bitset_foreach(work_regs, color) {
+				int root_idx, arg_idx, cst_idx;
+				mangle_var(buf, 'x', rootnr, color);
+				root_idx = lpp_get_var_idx(pi->curr_lp, buf);
+				mangle_var(buf, 'x', argnr, color);
+				arg_idx = lpp_get_var_idx(pi->curr_lp, buf);
+
+				mangle_cst(buf, 'E', cst_counter++);
+				cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_less, 0);
+				if (bitset_is_set(root_regs, color)) {
+					/* add root-y <= 0 */
+					lpp_set_factor_fast(pi->curr_lp, cst_idx, root_idx, 1);
+					lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
+				} else {
+					assert(bitset_is_set(arg_regs, color) && "bitset_xor is buggy");
+					/* add arg-y <= 0 */
+					lpp_set_factor_fast(pi->curr_lp, cst_idx, arg_idx, 1);
+					lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, -1);
+				}
+			}
 		}
 	}
 }
 
 /**
- * Matrix M: maximum independent set constraints
+ * Matrix S: maximum independent set constraints
  * Generates lower bound-cuts for optimization units with inner interferences.
  * Sum(y_{root, arg}, arg \in Args) <= max_indep_set_size - 1
  */
-static void pi_add_constr_M(problem_instance_t *pi) {
+static void pi_add_constr_S(problem_instance_t *pi) {
 	unit_t *curr;
 	int cst_counter = 0;
-	DBG((dbg, LEVEL_2, "Add M constraints...\n"));
+	DBG((dbg, LEVEL_2, "Add S constraints...\n"));
 
 	/* for all optimization units */
 	list_for_each_entry(unit_t, curr, &pi->co->units, units) {
@@ -315,13 +347,13 @@ static void pi_add_constr_M(problem_instance_t *pi) {
 		int cst_idx, y_idx, i;
 		char buf[32];
 
-		if (curr->minimal_costs == 0)
+		if (curr->min_nodes_costs == 0)
 			continue;
 
 		root = curr->nodes[0];
 		rootnr = get_irn_graph_nr(root);
-		mangle_cst(buf, 'M', cst_counter++);
-		cst_idx = lpp_add_cst(pi->curr_lp, buf, greater, curr->minimal_costs);
+		mangle_cst(buf, 'S', cst_counter++);
+		cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, curr->min_nodes_costs);
 
 		/* for all arguments */
 		for (i = 1; i < curr->node_count; ++i) {
@@ -329,11 +361,132 @@ static void pi_add_constr_M(problem_instance_t *pi) {
 			argnr = get_irn_graph_nr(arg);
 			mangle_var(buf, 'y', rootnr, argnr);
 			y_idx = lpp_get_var_idx(pi->curr_lp, buf);
-			lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, 1);
+			lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, curr->costs[i]);
 		}
 	}
 }
 
+static INLINE int get_costs(problem_instance_t *pi, ir_node *phi, ir_node *irn) {
+	int i;
+	unit_t *curr;
+	/* search optimization unit for phi */
+	list_for_each_entry(unit_t, curr, &pi->co->units, units)
+		if (curr->nodes[0] == phi) {
+			for (i=1; i<curr->node_count; ++i)
+				if (curr->nodes[i] == irn)
+					return curr->costs[i];
+			assert(0 && "irn must occur in this ou");
+		}
+	assert(0 && "phi must be found in a ou");
+	return 0;
+}
+
+/*
+ * TODO: Because this here uses a phi-walker and not the ou's,
+ * it is possible, that the interfering args of a phi will cause a bug ??!!
+ */
+static void M_constr_walker(ir_node *block, void *env) {
+	problem_instance_t *pi = env;
+	int count, arity, row, col, other_row, *costs;
+	ir_node **phis, *phi, *irn, **phi_matrix;
+	pset *done;
+	bitset_t *candidates;
+
+	/* Count all phi nodes of this block */
+	for (count=0, irn = sched_first(block); is_Phi(irn); irn = sched_next(irn))
+		count++;
+
+	/* We at least 2 phi nodes for this class of inequalities */
+	if (count < 2)
+		return;
+
+	/* Build the \Phi-Matrix */
+	arity = get_irn_arity(sched_first(block));
+	phis = alloca(count * sizeof(*phis));
+	costs = alloca(count * sizeof(costs));
+	phi_matrix = alloca(count*arity * sizeof(*phi_matrix));
+	candidates = bitset_alloca(count);
+
+	phi = sched_first(block);
+	for (row=0; row<count; ++row) {
+		phis[row] = phi;
+		for (col=0; col<arity; ++col)
+			phi_matrix[row*arity + col] = get_irn_n(phi, col);
+		phi = sched_next(phi);
+	}
+
+	/* Now find the interesting patterns in the matrix:
+	 * All nodes which are used at least twice in a column. */
+	/* columnwise ... */
+	for (col=0; col<arity; ++col) {
+		done = pset_new_ptr_default();
+		for (row=0; row<count; ++row) {
+			irn = phi_matrix[row*arity + col];
+			/* has the irn already been processed in this col? */
+			if (pset_find_ptr(done, irn))
+				continue;
+			else
+				pset_insert_ptr(done, irn);
+
+			/* insert irn in candidates */
+			bitset_clear_all(candidates);
+			bitset_set(candidates, row);
+			/* search the irn in the rows below */
+			for (other_row = row+1; other_row<count; ++other_row)
+				if (irn == phi_matrix[other_row*arity + col]) {
+					/* found the irn in the same col in another row */
+					bitset_set(candidates, other_row);
+				}
+
+			/* now we know all occurences of irn in this col */
+			if (bitset_popcnt(candidates) < 2)
+				continue;
+
+			/* compute the minimal costs (rhs) */
+			int phi_nr, sum=0, max=-1, minimal_costs;
+			bitset_foreach(candidates, phi_nr) {
+				costs[phi_nr] = get_costs(pi, phis[phi_nr], irn);
+				sum += costs[phi_nr];
+				max = MAX(max, costs[phi_nr]);
+			}
+			minimal_costs = sum - max;
+
+			/* generate an unequation finally.
+			 * phis are indexed in the bitset,
+			 * shared argument is irn
+			 * rhs is minimal_costs */
+			{
+				char buf[32];
+				ir_node *root;
+				int pos, irnnr, rootnr, cst_idx, y_idx, cst_counter = 0;
+
+				irnnr = get_irn_graph_nr(irn);
+				mangle_cst(buf, 'M', cst_counter++);
+				cst_idx = lpp_add_cst(pi->curr_lp, buf, lpp_greater, minimal_costs);
+
+				/* for all phis */
+				bitset_foreach(candidates, pos) {
+					root = phis[pos];
+					rootnr = get_irn_graph_nr(root);
+					mangle_var(buf, 'y', rootnr, irnnr);
+					y_idx = lpp_get_var_idx(pi->curr_lp, buf);
+					lpp_set_factor_fast(pi->curr_lp, cst_idx, y_idx, costs[pos]);
+				}
+			}
+		}
+		del_pset(done); /* clear set for next row */
+	} /*next col*/
+}
+
+/**
+ * Matrix M: Multi-Arg-Use. Interrelates different \phi-functions
+ * in the same block, iff they use the same arg at the same pos.
+ * Only one of the phis can get the arg.
+ */
+static void pi_add_constr_M(problem_instance_t *pi) {
+	dom_tree_walk_irg(get_irg(pi->co), M_constr_walker, NULL, pi);
+}
+
 /**
  * Generate the initial problem matrices and vectors.
  */
@@ -346,12 +499,12 @@ static problem_instance_t *new_pi(const copy_opt_t *co) {
 	pi->co = co;
 	pi->removed = pset_new_ptr_default();
 	INIT_LIST_HEAD(&pi->simplicials);
-	pi->dilp = new_lpp(co->name, minimize);
+	pi->dilp = new_lpp(co->name, lpp_minimize);
 	pi->last_x_var = -1;
 
 	/* problem size reduction */
 	pi_find_simplicials(pi);
-	//TODO If you wish to see it: dump_ifg_w/o_removed
+	//BETTER If you wish to see it: dump_ifg_w/o_removed
 	if (pi->all_simplicial)
 		return pi;
 
@@ -361,6 +514,7 @@ static problem_instance_t *new_pi(const copy_opt_t *co) {
 	for (col = 0; col < pi->co->chordal_env->cls->n_regs; ++col)
 		pi_add_constr_B(pi, col);
 	pi_add_constr_E(pi);
+	pi_add_constr_S(pi);
 	pi_add_constr_M(pi);
 
 	return pi;
@@ -395,8 +549,8 @@ static void pi_set_start_sol(problem_instance_t *pi) {
 		lpp_get_var_name(pi->curr_lp, i, var_name, sizeof(var_name));
 		/* split into components */
 		if (split_var(var_name, &nnr, &col) == 2) {
-			assert(get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->chordal_env->irg, nnr)) != -1);
-			val = (get_irn_col(pi->co, get_irn_for_graph_nr(pi->co->chordal_env->irg, nnr)) == col) ? 1 : 0;
+			assert(get_irn_col(pi->co, get_irn_for_graph_nr(get_irg(pi->co), nnr)) != -1);
+			val = (get_irn_col(pi->co, get_irn_for_graph_nr(get_irg(pi->co), nnr)) == col) ? 1 : 0;
 			lpp_set_start_value(pi->curr_lp, i, val);
 		} else {
 			fprintf(stderr, "Variable name is: %s\n", var_name);
@@ -408,9 +562,9 @@ static void pi_set_start_sol(problem_instance_t *pi) {
 /**
  * Invoke a solver
  */
-static void pi_solve_ilp(problem_instance_t *pi, void (*lpp_solve)(lpp_t *)) {
+static void pi_solve_ilp(problem_instance_t *pi) {
 	pi_set_start_sol(pi);
-	lpp_solve(pi->curr_lp);
+	lpp_solve_net(pi->curr_lp, LPP_HOST, LPP_SOLVER);
 }
 
 /**
@@ -430,10 +584,10 @@ static void pi_set_simplicials(problem_instance_t *pi) {
 
 		/* get free color by inspecting all neighbors */
 		ifn = simpl->ifn;
-		irn = get_irn_for_graph_nr(pi->co->chordal_env->irg, ifn->nnr);
+		irn = get_irn_for_graph_nr(get_irg(pi->co), ifn->nnr);
 		bitset_clear_all(used_cols);
 		foreach_neighb(ifn, other) {
-			other_irn = get_irn_for_graph_nr(pi->co->chordal_env->irg, other->nnr);
+			other_irn = get_irn_for_graph_nr(get_irg(pi->co), other->nnr);
 			if (!is_removed(other_irn)) /* only inspect nodes which are in graph right now */
 				bitset_set(used_cols, get_irn_col(pi->co, other_irn));
 		}
@@ -453,7 +607,7 @@ static void pi_set_simplicials(problem_instance_t *pi) {
 static void pi_apply_solution(problem_instance_t *pi) {
 	int i;
 	double *sol;
-	sol_state_t state;
+	lpp_sol_state_t state;
 	DBG((dbg, LEVEL_2, "Applying solution...\n"));
 
 #ifdef DO_STAT
@@ -463,9 +617,9 @@ static void pi_apply_solution(problem_instance_t *pi) {
 
 	sol = xmalloc((pi->last_x_var+1) * sizeof(*sol));
 	state = lpp_get_solution(pi->curr_lp, sol, 1, pi->last_x_var);
-	if (state != optimal) {
+	if (state != lpp_optimal) {
 		printf("Solution state is not 'optimal': %d\n", state);
-		assert(state >= feasible && "The solution should at least be feasible!");
+		assert(state >= lpp_feasible && "The solution should at least be feasible!");
 	}
 	for (i=0; i<pi->last_x_var; ++i) {
 		int nnr, col;
@@ -474,9 +628,9 @@ static void pi_apply_solution(problem_instance_t *pi) {
 		if (sol[i] > 1-EPSILON) { /* split varibale name into components */
 			lpp_get_var_name(pi->curr_lp, 1+i, var_name, sizeof(var_name));
 			if (split_var(var_name, &nnr, &col) == 2) {
-				DBG((dbg, LEVEL_2, "Irn %n  Idx %d  Var %s  Val %f\n", get_irn_for_graph_nr(pi->co->chordal_env->irg, nnr), i, var_name, sol[i]));
+				DBG((dbg, LEVEL_2, "Irn %n  Idx %d  Var %s  Val %f\n", get_irn_for_graph_nr(get_irg(pi->co), nnr), i, var_name, sol[i]));
 				DBG((dbg, LEVEL_2, "x%d = %d\n", nnr, col));
-				set_irn_col(pi->co, get_irn_for_graph_nr(pi->co->chordal_env->irg, nnr), col);
+				set_irn_col(pi->co, get_irn_for_graph_nr(get_irg(pi->co), nnr), col);
 			} else
 				assert(0 && "This should be a x-var");
 		}
@@ -488,9 +642,9 @@ void co_ilp_opt(copy_opt_t *co) {
 
 	dbg = firm_dbg_register("ir.be.copyoptilp");
 	if (!strcmp(co->name, DEBUG_IRG))
-		firm_dbg_set_mask(dbg, DEBUG_LVL_ILP);
+		firm_dbg_set_mask(dbg, DEBUG_IRG_LVL_ILP);
 	else
-		firm_dbg_set_mask(dbg, DEBUG_LVL);
+		firm_dbg_set_mask(dbg, DEBUG_LVL_ILP);
 
 	pi = new_pi(co);
 	if (!pi->all_simplicial) {
@@ -499,7 +653,7 @@ void co_ilp_opt(copy_opt_t *co) {
 		snprintf(buf, sizeof(buf), "%s.mps", co->name);
 		lpp_dump(pi->curr_lp, buf);
 #endif
-		pi_solve_ilp(pi, lpp_solve_local);
+		pi_solve_ilp(pi);
 		pi_apply_solution(pi);
 		pi_set_simplicials(pi);
 	}