X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyilp2.c;h=b323464e583a203689bea22c8bfcdd1957c02b20;hb=7438ae082c9ec7658ccd006b40aa62084aedca2d;hp=5cf5556eb4665b14f2ae46bfb4bfd61e4f6d7569;hpb=646d941217399e4bc713359fd5ad393e4db8b905;p=libfirm

diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c
index 5cf5556eb..b323464e5 100644
--- a/ir/be/becopyilp2.c
+++ b/ir/be/becopyilp2.c
@@ -4,25 +4,26 @@
  * Copyright:   (c) Universitaet Karlsruhe
  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  *
+ *
  * ILP formalization using G=(V, E, Q):
- *  - 1 class of variables: equal color vars
+ *  - 2 class of variables: coloring vars x_ic   and   equal color vars y_ij
  *  - Path constraints
- *  - Clique path constraints
+ *  - Clique-star constraints
  *
  *
  *	\min \sum_{ (i,j) \in Q }  w_ij y_ij
  *
- *		y_ij				=  1			(i,j) \in E
+ *		\sum_c x_nc			=  1			n \in N, c \in C
  *
- *		\sum_c y_nc			=  |C| - 1		n \in N, c \in C
+ *		x_nc				=  0			n \in N, c \not\in C(n)
  *
- *		y_nc				=  1			n \in N, c \not\in C(n)
+ *		\sum x_nc			<= 1			x_nc \in Clique \in AllCliques,  c \in C
  *
  *		\sum_{e \in p} y_e	>= 1			p \in P		path constraints
  *
- *		\sum_{e \in cp} y_e	>= |cp| - 1		cp \in CP	clique-path constraints
+ *		\sum_{e \in cs} y_e	>= |cs| - 1		cs \in CP	clique-star constraints
  *
- *		y_ij \in N,   w_ij \in R^+
+ *		x_nc, y_ij \in N,   w_ij \in R^+
  */
 
 #ifdef HAVE_CONFIG_H
@@ -31,9 +32,11 @@
 
 #ifdef WITH_ILP
 
+#include "irtools.h"
+#include "irgwalk.h"
 #include "becopyilp_t.h"
 #include "beifg_t.h"
-#include "irtools.h"
+#include "besched_t.h"
 
 #define DEBUG_LVL 1
 
@@ -103,13 +106,13 @@ static void build_interference_cstr(ilp_env_t *ienv) {
 	int i, col;
 
 	void *iter = be_ifg_cliques_iter_alloca(ifg);
-	ir_node *clique = alloca(sizeof(*clique) * n_colors);
+	ir_node **clique = alloca(sizeof(*clique) * n_colors);
 	int size;
 
 	char buf[16];
 
 	/* for each maximal clique */
-	be_ifg_foreach_clique(ifg, iter, &clique, &size) {
+	be_ifg_foreach_clique(ifg, iter, clique, &size) {
 
 		if (size < 2)
 			continue;
@@ -119,7 +122,7 @@ static void build_interference_cstr(ilp_env_t *ienv) {
 			int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
 
 			/* for each member of this clique */
-			for (i=0; i<size, ++i) {
+			for (i=0; i<size; ++i) {
 				ir_node *irn = clique[i];
 
 				if (!sr_is_removed(ienv->sr, irn)) {
@@ -169,11 +172,183 @@ static void build_affinity_cstr(ilp_env_t *ienv) {
 	}
 }
 
-static void build_path_cstr(ilp_env_t *ienv) {
+/**
+ * Helping stuff for build_clique_star_cstr
+ */
+typedef struct _edge_t {
+	ir_node *n1, *n2;
+} edge_t;
+
+static int compare_edge_t(const void *k1, const void *k2, size_t size) {
+	const edge_t *e1 = k1;
+	const edge_t *e2 = k2;
+
+	return ! (e1->n1 == e2->n1   &&   e1->n2 == e2->n2);
+}
+
+#define HASH_EDGE(e) (HASH_PTR((e)->n1) ^ HASH_PTR((e)->n2))
+
+static INLINE edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) {
+	edge_t new_edge;
 
+	if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
+		new_edge.n1 = n1;
+		new_edge.n2 = n2;
+	} else {
+		new_edge.n1 = n2;
+		new_edge.n2 = n1;
+	}
+	*counter++;
+	return set_insert(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+}
+
+static INLINE edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) {
+	edge_t new_edge;
+
+	if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
+		new_edge.n1 = n1;
+		new_edge.n2 = n2;
+	} else {
+		new_edge.n1 = n2;
+		new_edge.n2 = n1;
+	}
+	return set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+}
+
+static INLINE void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) {
+	edge_t new_edge, *e;
+
+	if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
+		new_edge.n1 = n1;
+		new_edge.n2 = n2;
+	} else {
+		new_edge.n1 = n2;
+		new_edge.n2 = n1;
+	}
+	e = set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
+	if (e) {
+		e->n1 = NULL;
+		e->n2 = NULL;
+		*counter--;
+	}
 }
 
-static void build_clique_path_cstr(ilp_env_t *ienv) {
+#define pset_foreach(pset, irn)  for(irn=pset_first(pset); irn; irn=pset_next(pset))
+
+/**
+ * Search for an interference clique and an external node
+ * with affinity edges to all nodes of the clique.
+ * At most 1 node of the clique can be colored equally with the external node.
+ */
+static void build_clique_star_cstr(ilp_env_t *ienv) {
+	node_t *node;
+
+	/* for each node with affinity edges */
+	co_gs_foreach_node(ienv->co, node) {
+		struct obstack ob;
+		neighb_t *nbr;
+		ir_node *center = node->irn;
+		ir_node **nodes;
+		set *edges;
+		int i, o, n_nodes, n_edges;
+
+		obstack_init(&ob);
+		edges = new_set(compare_edge_t, 8);
+
+		/* get all affinity neighbours */
+		n_nodes = 0;
+		co_gs_foreach_neighb(node, nbr) {
+			obstack_ptr_grow(&ob, nbr->irn);
+			++n_nodes;
+		}
+		nodes = obstack_finish(&ob);
+
+		/* get all interference edges between these */
+		n_edges = 0;
+		for (i=0; i<n_nodes; ++i)
+			for (o=0; o<i; ++o)
+				if (be_ifg_connected(ienv->co->cenv->ifg, nodes[i], nodes[o]))
+					add_edge(edges, nodes[i], nodes[o], &n_edges);
+
+		/* cover all these interference edges with maximal cliques */
+		while (n_edges) {
+			edge_t *e;
+			pset *clique = pset_new_ptr(8);
+			int growed;
+
+			/* get 2 starting nodes to form a clique */
+			for (e=set_first(edges); !e->n1; e=set_next(edges))
+				/*nothing*/ ;
+
+			remove_edge(edges, e->n1, e->n2, &n_edges);
+			pset_insert_ptr(clique, e->n1);
+			pset_insert_ptr(clique, e->n2);
+
+			/* while the clique is growing */
+			do {
+				growed = 0;
+
+				/* search for a candidate to extend the clique */
+				for (i=0; i<n_nodes; ++i) {
+					ir_node *member, *cand = nodes[i];
+					int is_cand;
+
+					/* if its already in the clique try the next */
+					if (pset_find_ptr(clique, cand))
+						continue;
+
+					/* are there all necessary interferences? */
+					is_cand = 1;
+					pset_foreach(clique, member) {
+						if (!find_edge(edges, cand, member)) {
+							is_cand = 0;
+							pset_break(clique);
+							break;
+						}
+					}
+
+					/* now we know if we have a clique extender */
+					if (is_cand) {
+						/* first remove all covered edges */
+						pset_foreach(clique, member)
+							remove_edge(edges, cand, member, &n_edges);
+
+						/* insert into clique */
+						pset_insert_ptr(clique, cand);
+						growed = 1;
+						break;
+					}
+				}
+			} while (growed);
+
+			/* now the clique is maximal. Finally add the constraint */
+			{
+				ir_node *member;
+				int var_idx, cst_idx, center_nr, member_nr;
+				char buf[16];
+
+				cst_idx = lpp_add_cst(ienv->lp, NULL, lpp_greater, pset_count(clique)-1);
+				center_nr = get_irn_node_nr(center);
+
+				pset_foreach(clique, member) {
+					member_nr = get_irn_node_nr(member);
+					var_idx = lpp_get_var_idx(ienv->lp, name_cdd_sorted(buf, 'y', center_nr, member_nr));
+					lpp_set_factor_fast(ienv->lp, cst_idx, var_idx, 1.0);
+				}
+			}
+
+			del_pset(clique);
+		}
+
+		del_set(edges);
+		obstack_free(&ob, NULL);
+	}
+}
+
+/**
+ *
+ */
+static void build_path_cstr(ilp_env_t *ienv) {
 
 }
 
@@ -185,8 +360,8 @@ static void ilp2_build(ilp_env_t *ienv) {
 	build_coloring_cstr(ienv);
 	build_interference_cstr(ienv);
 	build_affinity_cstr(ienv);
+	build_clique_star_cstr(ienv);
 	build_path_cstr(ienv);
-	build_clique_path_cstr(ienv);
 
 	lower_bound = co_get_lower_bound(ienv->co) - co_get_inevit_copy_costs(ienv->co);
 	lpp_set_bound(ienv->lp, lower_bound);
@@ -195,9 +370,9 @@ static void ilp2_build(ilp_env_t *ienv) {
 
 static void ilp2_apply(ilp_env_t *ienv) {
 	local_env_t *lenv = ienv->env;
-	double sol[];
+	double *sol;
 	lpp_sol_state_t state;
-	int count;
+	int i, count;
 
 	count = lenv->last_x_var - lenv->first_x_var + 1;
 	sol = xmalloc(count * sizeof(sol[0]));
@@ -208,7 +383,6 @@ static void ilp2_apply(ilp_env_t *ienv) {
 	}
 
 	for (i=0; i<count; ++i) {
-		char c;
 		int nodenr, color;
 		char var_name[16];