X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbecopyheur4.c;h=c28c807790f672b478e867bdb2be39b2d9431d46;hb=52b05829a843d8e3c06aac48e8123db9c71c6ef8;hp=caabae7a6c981c0850f2694ebfc7c37ee7d4f3f0;hpb=cb53b30cfd437f77f7a872c73a08c5f6f9e8b09e;p=libfirm

diff --git a/ir/be/becopyheur4.c b/ir/be/becopyheur4.c
index caabae7a6..c28c80779 100644
--- a/ir/be/becopyheur4.c
+++ b/ir/be/becopyheur4.c
@@ -1,13 +1,34 @@
-/**
- * This is the C implementation of the trivial mst algo
- * originally written in Java by Sebastian Hack.
- * Performs simple copy minimzation.
+/*
+ * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
  *
- * @author Christian Wuerdig
- * @date   27.04.2007
- * @id     $Id$
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
  */
 
+/**
+ * @file
+ * @brief       Simple copy minimization heuristics.
+ * @author      Christian Wuerdig
+ * @date        27.04.2007
+ * @version     $Id$
+ *
+ * This is the C implementation of the mst algorithm
+ * originally written in Java by Sebastian Hack.
+ * (also known as "heur3" :)
+ * Performs simple copy minimization.
+ */
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif /* HAVE_CONFIG_H */
@@ -15,7 +36,7 @@
 #include <float.h>
 
 #include "array.h"
-#include "irnode.h"
+#include "irnode_t.h"
 #include "bitset.h"
 #include "raw_bitset.h"
 #include "irphase_t.h"
@@ -23,17 +44,23 @@
 #include "pset_new.h"
 #include "xmalloc.h"
 #include "pdeq.h"
+#include "irprintf.h"
+#include "irbitset.h"
 
 #include "bearch.h"
 #include "beifg.h"
 #include "be_t.h"
 #include "becopyopt_t.h"
-#include "irbitset.h"
 
 #define COL_COST_INFEASIBLE       DBL_MAX
 #define AFF_NEIGHBOUR_FIX_BENEFIT 128.0
 #define NEIGHBOUR_CONSTR_COSTS    64.0
 
+#define DBG_AFF_CHUNK(env, level, chunk) DEBUG_ONLY(if (firm_dbg_get_mask((env)->dbg) & (level)) dbg_aff_chunk((env), (chunk));)
+#define DBG_COL_COST(env, level, cost)   DEBUG_ONLY(if (firm_dbg_get_mask((env)->dbg) & (level)) dbg_col_cost((env), (cost));)
+
+static int last_chunk_id = 0;
+
 typedef struct _col_cost_t {
 	int    col;
 	double cost;
@@ -41,8 +68,9 @@ typedef struct _col_cost_t {
 
 typedef struct _aff_chunk_t {
 	bitset_t *nodes;
-	double   weight;
+	int      weight;
 	unsigned weight_consistent : 1;
+	int      id;
 } aff_chunk_t;
 
 typedef struct _aff_edge_t {
@@ -62,26 +90,72 @@ typedef struct _co_mst_env_t {
 	be_ifg_t         *ifg;           /**< the interference graph */
 	const arch_env_t *aenv;          /**< the arch environment */
 	copy_opt_t       *co;            /**< the copy opt object */
+	DEBUG_ONLY(firm_dbg_module_t *dbg);
 } co_mst_env_t;
 
 /* stores coalescing related information for a node */
 typedef struct _co_mst_irn_t {
-	ir_node     *irn;
-	aff_chunk_t *chunk;
-	bitset_t    *adm_colors;
-	int         int_neigh;
-	int         col;
-	int         init_col;
-	int         tmp_col;
-	unsigned    fixed     : 1;
-	unsigned    tmp_fixed : 1;
+	ir_node     *irn;              /**< the irn this information belongs to */
+	aff_chunk_t *chunk;            /**< the chunk this irn belongs to */
+	bitset_t    *adm_colors;       /**< set of admissible colors for this irn */
+	ir_node     **int_neighs;      /**< ARR_D of all interfering neighbours (cached for speed reasons) */
+	int         int_aff_neigh;     /**< number of interfering affinity neighbours */
+	int         col;               /**< color currently assigned */
+	int         init_col;          /**< the initial color */
+	int         tmp_col;           /**< a temporary assigned color */
+	unsigned    fixed     : 1;     /**< the color is fixed */
+	unsigned    tmp_fixed : 1;     /**< the color is temporary fixed */
 } co_mst_irn_t;
 
-
 #define get_co_mst_irn(mst_env, irn) (phase_get_or_set_irn_data(&(mst_env)->ph, (irn)))
 
 typedef int decide_func_t(co_mst_irn_t *node, int col);
 
+#ifdef DEBUG_libfirm
+
+/**
+ * Write a chunk to stderr for debugging.
+ */
+static void dbg_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
+	int idx;
+	if (c->weight_consistent)
+		ir_fprintf(stderr, " $%d ", c->weight);
+	ir_fprintf(stderr, "{");
+	bitset_foreach(c->nodes, idx) {
+		ir_node *n = get_idx_irn(env->co->irg, idx);
+		ir_fprintf(stderr, " %+F,", n);
+	}
+	ir_fprintf(stderr, "}");
+}
+
+/**
+ * Dump all admissible colors to stderr.
+ */
+static void dbg_admissible_colors(co_mst_env_t *env, co_mst_irn_t *node) {
+	int idx;
+	if (bitset_popcnt(node->adm_colors) < 1)
+		fprintf(stderr, "no admissible colors?!?");
+	else {
+		bitset_foreach(node->adm_colors, idx)
+			fprintf(stderr, " %d", idx);
+	}
+}
+
+/**
+ * Dump color-cost pairs to stderr.
+ */
+static void dbg_col_cost(co_mst_env_t *env, col_cost_t *cost) {
+	int i;
+	for (i = 0; i < env->n_regs; ++i) {
+		if (cost[i].cost == COL_COST_INFEASIBLE)
+			fprintf(stderr, " (%d, INF)", cost[i].col);
+		else
+			fprintf(stderr, " (%d, %.1f)", cost[i].col, cost[i].cost);
+	}
+}
+
+#endif /* DEBUG_libfirm */
+
 static INLINE int get_mst_irn_col(co_mst_irn_t *node) {
 	return node->tmp_fixed ? node->tmp_col : node->col;
 }
@@ -107,13 +181,19 @@ static int decider_always_yes(co_mst_irn_t *node, int col) {
 	return 1;
 }
 
-/* compares two affinity edges */
+/* > compares two affinity edges by its weight */
 static int cmp_aff_edge(const void *a, const void *b) {
 	const aff_edge_t *e1 = a;
 	const aff_edge_t *e2 = b;
 
+	if (e2->weight == e1->weight) {
+		if (e2->src->node_idx == e1->src->node_idx)
+			return QSORT_CMP(e2->tgt->node_idx, e1->tgt->node_idx);
+		else
+			return QSORT_CMP(e2->src->node_idx, e1->src->node_idx);
+	}
 	/* sort in descending order */
-	return e1->weight < e2->weight ? 1 : -1;
+	return QSORT_CMP(e2->weight, e1->weight);
 }
 
 /* compares to color-cost pairs */
@@ -129,8 +209,10 @@ static int cmp_col_cost(const void *a, const void *b) {
  */
 static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
 	aff_chunk_t *c = xmalloc(sizeof(*c));
+	c->weight            = -1;
 	c->weight_consistent = 0;
 	c->nodes             = bitset_irg_malloc(env->co->irg);
+	c->id                = last_chunk_id++;
 	pset_new_insert(&env->chunkset, c);
 	return c;
 }
@@ -153,7 +235,6 @@ static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
 	bitset_set(c->nodes, get_irn_idx(node->irn));
 }
 
-
 /**
  * In case there is no phase information for irn, initialize it.
  */
@@ -162,22 +243,26 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
 	co_mst_env_t *env = ph->priv;
 
 	if (res != old) {
-		void                      *neigh_it = be_ifg_neighbours_iter_alloca(env->ifg);
 		const arch_register_req_t *req;
-		ir_node                   *m;
-
-		res->irn       = irn;
-		res->chunk     = new_aff_chunk(env);
-		res->fixed     = 0;
-		res->tmp_fixed = 0;
-		res->tmp_col   = -1;
-		res->int_neigh = 0;
-		res->col       = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
-		res->init_col  = res->col;
+		void     *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
+		ir_node  *neigh;
+		unsigned len;
+
+		res->irn           = irn;
+		res->chunk         = new_aff_chunk(env);
+		res->fixed         = 0;
+		res->tmp_fixed     = 0;
+		res->tmp_col       = -1;
+		res->int_neighs    = NULL;
+		res->int_aff_neigh = 0;
+		res->col           = arch_register_get_index(arch_get_irn_register(env->aenv, irn));
+		res->init_col      = res->col;
 
 		/* add note to new chunk */
 		aff_chunk_add_node(res->chunk, res);
 
+		DB((env->dbg, LEVEL_4, "Creating phase info for %+F, chunk %d\n", irn, res->chunk->id));
+
 		/* set admissible registers */
 		res->adm_colors = bitset_obstack_alloc(phase_obst(ph), env->n_regs);
 
@@ -185,19 +270,43 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
 		req = arch_get_register_req(env->aenv, irn, -1);
 		if (arch_register_req_is(req, limited))
 			rbitset_copy_to_bitset(req->limited, res->adm_colors);
+		else
+			bitset_set_all(res->adm_colors);
 
 		/* exclude global ignore registers as well */
 		bitset_andnot(res->adm_colors, env->ignore_regs);
 
-		/* calculate the number of interfering neighbours */
-		be_ifg_foreach_neighbour(env->ifg, neigh_it, irn, m) {
-			if (! arch_irn_is(env->aenv, m, ignore))
-				res->int_neigh++;
-		}
+		/* set the number of interfering affinity neighbours to -1, they are calculated later */
+		res->int_aff_neigh = -1;
+
+		/* build list of interfering neighbours */
+		len = 0;
+		/* count them first as an obstack array cannot be extended */
+		be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
+			len++;
+		res->int_neighs = NEW_ARR_D(ir_node *, phase_obst(ph), len);
+		len = 0;
+		be_ifg_foreach_neighbour(env->ifg, nodes_it, irn, neigh)
+			res->int_neighs[len++] = neigh;
+	}
+	return res;
+}
+
+/**
+ * Check if affinity chunk @p chunk interferes with node @p irn.
+ */
+static INLINE int aff_chunk_interferes(co_mst_env_t *env, aff_chunk_t *chunk, ir_node *irn) {
+	co_mst_irn_t *node = get_co_mst_irn(env, irn);
+	ir_node      *neigh;
+	int          i;
 
+	for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
+		neigh = node->int_neighs[i];
+		if (! arch_irn_is(env->aenv, neigh, ignore) && bitset_is_set(chunk->nodes, get_irn_idx(neigh)))
+			return 1;
 	}
 
-	return res;
+	return 0;
 }
 
 /**
@@ -208,18 +317,17 @@ static void *co_mst_irn_init(ir_phase *ph, ir_node *irn, void *old) {
  * @return 1 if there are interferences between nodes of c1 and c2, 0 otherwise.
  */
 static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
-	void *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
-	int  idx;
+	int idx;
+
+	if (c1 == c2)
+		return 0;
 
-	/* check if there is a node in c1 having an interfering neighbour in c2 */
-	bitset_foreach(c1->nodes, idx) {
+	/* check if there is a node in c2 having an interfering neighbor in c1 */
+	bitset_foreach(c2->nodes, idx) {
 		ir_node *n = get_idx_irn(env->co->irg, idx);
-		ir_node *neigh;
 
-		be_ifg_foreach_neighbour(env->ifg, nodes_it, n, neigh) {
-			if (bitset_is_set(c2->nodes, get_irn_idx(neigh)))
-				return 1;
-		}
+		if (aff_chunk_interferes(env, c1, n))
+			return 1;
 	}
 
 	return 0;
@@ -230,8 +338,14 @@ static INLINE int aff_chunks_interfere(co_mst_env_t *env, aff_chunk_t *c1, aff_c
  * are no interference edges from c1 to c2).
  * @return 1 if successful, 0 if not possible
  */
-static INLINE int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
-	if (! aff_chunks_interfere(env, c1, c2) && c1 != c2) {
+static int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk_t *c2) {
+	DB((env->dbg, LEVEL_4, "Attempt to let c1 (id %d): ", c1->id));
+	DBG_AFF_CHUNK(env, LEVEL_4, c1);
+	DB((env->dbg, LEVEL_4, "\n\tabsorb c2 (id %d): ", c2->id));
+	DBG_AFF_CHUNK(env, LEVEL_4, c2);
+	DB((env->dbg, LEVEL_4, "\n"));
+
+	if (c1 != c2 && ! aff_chunks_interfere(env, c1, c2)) {
 		int idx;
 
 		bitset_or(c1->nodes, c2->nodes);
@@ -243,9 +357,11 @@ static INLINE int aff_chunk_absorb(co_mst_env_t *env, aff_chunk_t *c1, aff_chunk
 			mn->chunk = c1;
 		}
 
+		DB((env->dbg, LEVEL_4, " ... absorbed, c2 deleted\n"));
 		delete_aff_chunk(env, c2);
 		return 1;
 	}
+	DB((env->dbg, LEVEL_4, " ... c1 interferes with c2, skipped\n"));
 	return 0;
 }
 
@@ -264,30 +380,24 @@ static INLINE aff_chunk_t *get_aff_chunk(co_mst_env_t *env, ir_node *irn) {
  */
 static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
 	if (! c->weight_consistent) {
-		double w = 0.0;
-		int    idx;
+		int w = 0;
+		int idx;
 
 		bitset_foreach(c->nodes, idx) {
 			ir_node         *n  = get_idx_irn(env->co->irg, idx);
 			affinity_node_t *an = get_affinity_info(env->co, n);
-			co_mst_irn_t    *n1 = get_co_mst_irn(env, n);
 
 			if (an != NULL) {
 				neighb_t *neigh;
 				co_gs_foreach_neighb(an, neigh) {
 					ir_node      *m    = neigh->irn;
 					int          m_idx = get_irn_idx(m);
-					co_mst_irn_t *n2;
 
 					/* skip ignore nodes */
 					if (arch_irn_is(env->aenv, m, ignore))
 						continue;
 
-					n2 = get_co_mst_irn(env, m);
-
-					/* record the edge in only one direction */
-					if (idx < m_idx)
-						w += (double)neigh->costs / (double)(1 + n1->int_neigh + n2->int_neigh);
+					w += bitset_is_set(c->nodes, m_idx) ? neigh->costs : 0;
 				}
 			}
 		}
@@ -297,6 +407,35 @@ static void aff_chunk_assure_weight(co_mst_env_t *env, aff_chunk_t *c) {
 	}
 }
 
+/**
+ * Count the number of interfering affinity neighbours
+ */
+static int count_interfering_aff_neighs(co_mst_env_t *env, affinity_node_t *an) {
+	neighb_t     *neigh;
+	ir_node      *irn  = an->irn;
+	co_mst_irn_t *node = get_co_mst_irn(env, irn);
+	int          res   = 0;
+
+	co_gs_foreach_neighb(an, neigh) {
+		ir_node *n = neigh->irn;
+		int     i;
+
+		/* skip ignore nodes */
+		if (arch_irn_is(env->aenv, n, ignore))
+			continue;
+
+		/* check if the affinity neighbour interfere */
+		for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
+			if (node->int_neighs[i] == n) {
+				++res;
+				break;
+			}
+		}
+	}
+	return res;
+}
+
+
 /**
  * Build chunks of nodes connected by affinity edges.
  * We start at the heaviest affinity edge.
@@ -308,7 +447,7 @@ static void build_affinity_chunks(co_mst_env_t *env) {
 	void        *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
 	aff_edge_t  *edges    = NEW_ARR_F(aff_edge_t, 0);
 	ir_node     *n;
-	int         i;
+	int         i, len;
 	aff_chunk_t *curr_chunk;
 	pset_new_iterator_t iter;
 
@@ -327,24 +466,31 @@ static void build_affinity_chunks(co_mst_env_t *env) {
 
 		if (an != NULL) {
 			neighb_t *neigh;
-			co_gs_foreach_neighb(an, neigh) {
-				ir_node      *m    = neigh->irn;
-				int          m_idx = get_irn_idx(m);
-				co_mst_irn_t *n2;
-
-				/* skip ignore nodes */
-				if (arch_irn_is(env->aenv, m, ignore))
-					continue;
 
-				n2 = get_co_mst_irn(env, m);
+			if (n1->int_aff_neigh < 0)
+				n1->int_aff_neigh = count_interfering_aff_neighs(env, an);
+			co_gs_foreach_neighb(an, neigh) {
+				ir_node *m    = neigh->irn;
+				int     m_idx = get_irn_idx(m);
 
 				/* record the edge in only one direction */
 				if (n_idx < m_idx) {
-					aff_edge_t edge;
+					co_mst_irn_t *n2;
+					aff_edge_t   edge;
 
-					edge.src    = n;
-					edge.tgt    = m;
-					edge.weight = (double)neigh->costs / (double)(1 + n1->int_neigh + n2->int_neigh);
+					/* skip ignore nodes */
+					if (arch_irn_is(env->aenv, m, ignore))
+						continue;
+
+					edge.src = n;
+					edge.tgt = m;
+
+					n2 = get_co_mst_irn(env, m);
+					if (n2->int_aff_neigh < 0) {
+						affinity_node_t *am = get_affinity_info(env->co, m);
+						n2->int_aff_neigh = count_interfering_aff_neighs(env, am);
+					}
+					edge.weight = (double)neigh->costs / (double)(1 + n1->int_aff_neigh + n2->int_aff_neigh);
 					ARR_APP1(aff_edge_t, edges, edge);
 				}
 			}
@@ -352,17 +498,26 @@ static void build_affinity_chunks(co_mst_env_t *env) {
 	}
 
 	/* now: sort edges and build the affinity chunks */
-	qsort(edges, ARR_LEN(edges), sizeof(edges[0]), cmp_aff_edge);
-	for (i = 0; i < ARR_LEN(edges); ++i) {
+	len = ARR_LEN(edges);
+	qsort(edges, len, sizeof(edges[0]), cmp_aff_edge);
+	for (i = 0; i < len; ++i) {
 		aff_chunk_t *c1 = get_aff_chunk(env, edges[i].src);
 		aff_chunk_t *c2 = get_aff_chunk(env, edges[i].tgt);
 
+		DBG((env->dbg, LEVEL_1, "edge (%u,%u) %f\n", edges[i].src->node_idx, edges[i].tgt->node_idx, edges[i].weight));
+
 		(void)aff_chunk_absorb(env, c1, c2);
 	}
 
 	/* now insert all chunks into a priority queue */
 	foreach_pset_new(&env->chunkset, curr_chunk, iter) {
 		aff_chunk_assure_weight(env, curr_chunk);
+
+		DBG((env->dbg, LEVEL_1, "entry #%d", curr_chunk->id));
+		DBG_AFF_CHUNK(env, LEVEL_1, curr_chunk);
+		DBG((env->dbg, LEVEL_1, "\n"));
+
+
 		pqueue_put(env->chunks, curr_chunk, curr_chunk->weight);
 	}
 
@@ -377,16 +532,18 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
 {
 	waitq *nodes = new_waitq();
 
+	DBG((env->dbg, LEVEL_1, "\nExpanding new chunk (id %d) from %+F:", chunk->id, node->irn));
+
 	/* init queue and chunk */
 	waitq_put(nodes, node);
 	bitset_set(visited, get_irn_idx(node->irn));
 	aff_chunk_add_node(chunk, node);
+	DB((env->dbg, LEVEL_1, " %+F", node->irn));
 
 	/* as long as there are nodes in the queue */
 	while (! waitq_empty(nodes)) {
-		co_mst_irn_t    *n    = waitq_get(nodes);
-		affinity_node_t *an   = get_affinity_info(env->co, n->irn);
-		int             n_idx = get_irn_idx(n->irn);
+		co_mst_irn_t    *n  = waitq_get(nodes);
+		affinity_node_t *an = get_affinity_info(env->co, n->irn);
 
 		/* check all affinity neighbors */
 		if (an != NULL) {
@@ -402,11 +559,10 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
 
 				n2 = get_co_mst_irn(env, m);
 
-				if (n_idx < m_idx                                 &&
-					! bitset_is_set(visited, m_idx)               &&
-					decider(n2, col)                              &&
-					! n2->fixed                                   &&
-					! aff_chunks_interfere(env, chunk, n2->chunk) &&
+				if (! bitset_is_set(visited, m_idx)       &&
+					decider(n2, col)                      &&
+					! n2->fixed                           &&
+					! aff_chunk_interferes(env, chunk, m) &&
 					bitset_is_set(orig_chunk->nodes, m_idx))
 				{
 					/*
@@ -414,11 +570,12 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
 						- neighbour is not visited
 						- neighbour likes the color
 						- neighbour has not yet a fixed color
-						- the new chunk doesn't interfere with the chunk of the neighbour
+						- the new chunk doesn't interfere with the neighbour
 						- neighbour belongs or belonged once to the original chunk
 					*/
 					bitset_set(visited, m_idx);
 					aff_chunk_add_node(chunk, n2);
+					DB((env->dbg, LEVEL_1, " %+F", n2->irn));
 					/* enqueue for further search */
 					waitq_put(nodes, n2);
 				}
@@ -426,6 +583,8 @@ static void expand_chunk_from(co_mst_env_t *env, co_mst_irn_t *node, bitset_t *v
 		}
 	}
 
+	DB((env->dbg, LEVEL_1, "\n"));
+
 	del_waitq(nodes);
 }
 
@@ -519,32 +678,49 @@ static INLINE void reject_coloring(waitq *nodes) {
  * Determines the costs for each color if it would be assigned to node @p node.
  */
 static void determine_color_costs(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs) {
-	affinity_node_t *an       = get_affinity_info(env->co, node->irn);
-	void            *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
+	affinity_node_t *an = get_affinity_info(env->co, node->irn);
 	neighb_t        *aff_neigh;
-	ir_node         *int_neigh;
-	int             idx;
+	int             idx, i;
 
 	col_cost_init(env, costs, 0.0);
 
 	/* calculate (negative) costs for affinity neighbours */
-	co_gs_foreach_neighb(an, aff_neigh) {
-		ir_node      *m     = aff_neigh->irn;
-		co_mst_irn_t *neigh = get_co_mst_irn(env, m);
-		double       c      = (double)aff_neigh->costs;
-
-		/* calculate costs for fixed affinity neighbours */
-		if (neigh->tmp_fixed || neigh->fixed) {
-			int col = get_mst_irn_col(neigh);
-			costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
+	if (an != NULL) {
+		co_gs_foreach_neighb(an, aff_neigh) {
+			ir_node      *m = aff_neigh->irn;
+			co_mst_irn_t *neigh;
+			double       c;
+
+			/* skip ignore nodes */
+			if (arch_irn_is(env->aenv, m, ignore))
+				continue;
+
+			neigh = get_co_mst_irn(env, m);
+			c     = (double)aff_neigh->costs;
+
+			/* calculate costs for fixed affinity neighbours */
+			if (neigh->tmp_fixed || neigh->fixed) {
+				int col = get_mst_irn_col(neigh);
+				costs[col].cost -= c * AFF_NEIGHBOUR_FIX_BENEFIT;
+			}
 		}
 	}
 
 	/* calculate (positive) costs for interfering neighbours */
-	be_ifg_foreach_neighbour(env->ifg, nodes_it, node->irn, int_neigh) {
-		co_mst_irn_t *neigh  = get_co_mst_irn(env, int_neigh);
-		int          col     = get_mst_irn_col(neigh);
-		int          col_cnt = bitset_popcnt(neigh->adm_colors);
+	for (i = 0; i < ARR_LEN(node->int_neighs); ++i) {
+		co_mst_irn_t *neigh;
+		int          col, col_cnt;
+		ir_node      *int_neigh;
+
+		int_neigh = node->int_neighs[i];
+
+		/* skip ignore nodes */
+		if (arch_irn_is(env->aenv, int_neigh, ignore))
+			continue;
+
+		neigh   = get_co_mst_irn(env, int_neigh);
+		col     = get_mst_irn_col(neigh);
+		col_cnt = bitset_popcnt(neigh->adm_colors);
 
 		if (neigh->tmp_fixed || neigh->fixed) {
 			/* colors of fixed interfering neighbours are infeasible */
@@ -615,17 +791,22 @@ static int change_node_color_excluded(co_mst_env_t *env, co_mst_irn_t *node, int
 static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *costs, waitq *changed_ones) {
 	int   i;
 	waitq *local_changed = new_waitq();
+	waitq *tmp           = new_waitq();
+
+	DBG((env->dbg, LEVEL_1, "\tRecoloring %+F with color-costs", node->irn));
+	DBG_COL_COST(env, LEVEL_1, costs);
+	DB((env->dbg, LEVEL_1, "\n"));
 
 	for (i = 0; i < env->n_regs; ++i) {
-		void    *nodes_it = be_ifg_nodes_iter_alloca(env->ifg);
-		int     tgt_col   = costs[i].col;
-		int     neigh_ok  = 1;
-		ir_node *neigh;
+		int tgt_col  = costs[i].col;
+		int neigh_ok = 1;
+		int j;
 
 		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
 		if (costs[i].cost == COL_COST_INFEASIBLE) {
 			node->tmp_fixed = 0;
 			del_waitq(local_changed);
+			del_waitq(tmp);
 			return 0;
 		}
 
@@ -638,8 +819,18 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost
 		waitq_put(local_changed, node);
 
 		/* try to color all interfering neighbours with current color forbidden */
-		be_ifg_foreach_neighbour(env->ifg, nodes_it, node->irn, neigh) {
-			co_mst_irn_t *nn = get_co_mst_irn(env, neigh);
+		for (j = 0; j < ARR_LEN(node->int_neighs); ++j) {
+			co_mst_irn_t *nn;
+			ir_node      *neigh;
+
+			neigh = node->int_neighs[j];
+
+			/* skip ignore nodes */
+			if (arch_irn_is(env->aenv, neigh, ignore))
+				continue;
+
+			nn = get_co_mst_irn(env, neigh);
+
 			/*
 				Try to change the color of the neighbor and record all nodes which
 				get changed in the tmp list. Add this list to the "changed" list for
@@ -647,15 +838,12 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost
 				we bail out and try the next color.
 			*/
 			if (get_mst_irn_col(nn) == tgt_col) {
-				waitq *tmp = new_waitq();
-
 				/* try to color neighbour with tgt_col forbidden */
 				neigh_ok = change_node_color_excluded(env, nn, tgt_col, tmp);
 
 				/* join lists of changed nodes */
 				while (! waitq_empty(tmp))
 					waitq_put(local_changed, waitq_get(tmp));
-				del_waitq(tmp);
 
 				if (! neigh_ok)
 					break;
@@ -671,6 +859,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost
 			while (! waitq_empty(local_changed))
 				waitq_put(changed_ones, waitq_get(local_changed));
 			del_waitq(local_changed);
+			del_waitq(tmp);
 			return 1;
 		}
 		else {
@@ -680,6 +869,7 @@ static int recolor_nodes(co_mst_env_t *env, co_mst_irn_t *node, col_cost_t *cost
 	}
 
 	del_waitq(local_changed);
+	del_waitq(tmp);
 	return 0;
 }
 
@@ -692,6 +882,7 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col,
 
 	/* if node already has the target color -> good, temporary fix it */
 	if (col == tgt_col) {
+		DBG((env->dbg, LEVEL_4, "\t\tCNC: %+F has already color %d, fix temporary\n", node->irn, tgt_col));
 		if (! node->tmp_fixed) {
 			node->tmp_fixed = 1;
 			node->tmp_col   = tgt_col;
@@ -706,10 +897,29 @@ static int change_node_color(co_mst_env_t *env, co_mst_irn_t *node, int tgt_col,
 	*/
 	if (! (node->fixed || node->tmp_fixed) && bitset_is_set(node->adm_colors, tgt_col)) {
 		col_cost_t *costs = alloca(env->n_regs * sizeof(costs[0]));
+		int        res;
+
 		col_cost_init_single(env, costs, tgt_col);
-		return recolor_nodes(env, node, costs, changed_ones);
+
+		DBG((env->dbg, LEVEL_4, "\t\tCNC: Attempt to recolor %+F ===>>\n", node->irn));
+		res = recolor_nodes(env, node, costs, changed_ones);
+		DBG((env->dbg, LEVEL_4, "\t\tCNC: <<=== Recoloring of %+F %s\n", node->irn, res ? "succeeded" : "failed"));
+
+		return res;
 	}
 
+	DEBUG_ONLY(
+		if (firm_dbg_get_mask(env->dbg) & LEVEL_4) {
+			if (node->fixed || node->tmp_fixed)
+				DB((env->dbg, LEVEL_4, "\t\tCNC: %+F has already fixed color %d\n", node->irn, col));
+			else {
+				DB((env->dbg, LEVEL_4, "\t\tCNC: color %d not admissible for %+F (", tgt_col, node->irn));
+				dbg_admissible_colors(env, node);
+				DB((env->dbg, LEVEL_4, ")\n"));
+			}
+		}
+	)
+
 	return 0;
 }
 
@@ -725,11 +935,18 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 	bitset_t    *visited;
 	int         col, idx;
 
+	DB((env->dbg, LEVEL_2, "fragmentizing chunk #%d", c->id));
+	DBG_AFF_CHUNK(env, LEVEL_2, c);
+	DB((env->dbg, LEVEL_2, "\n"));
+
+
 	/* check which color is the "best" for the given chunk */
 	for (col = 0; col < env->k; ++col) {
 		int         one_good = 0;
 		aff_chunk_t *local_best;
 
+		DB((env->dbg, LEVEL_3, "\ttrying color %d\n", col));
+
 		/* try to bring all nodes of given chunk to the current color. */
 		bitset_foreach(c->nodes, idx) {
 			ir_node      *irn  = get_idx_irn(env->co->irg, idx);
@@ -737,10 +954,9 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 
 			assert(! node->fixed && "Node must not have a fixed color.");
 
-			one_good = change_node_color(env, node, col, changed_ones);
-
-			if (one_good)
-				break;
+			DB((env->dbg, LEVEL_4, "\t\tBringing %+F from color %d to color %d ...\n", irn, node->col, col));
+			one_good |= change_node_color(env, node, col, changed_ones);
+			DB((env->dbg, LEVEL_4, "\t\t... %+F attempt from %d to %d %s\n", irn, node->col, col, one_good ? "succeeded" : "failed"));
 		}
 
 		/* try next color when failed */
@@ -750,13 +966,20 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 		/* fragment the chunk according to the coloring */
 		local_best = fragment_chunk(env, col, c, tmp_chunks);
 
-		/* check if the local best is global best */
+		/* search the best of the good list
+		   and make it the new best if it is better than the current */
 		if (local_best) {
 			aff_chunk_assure_weight(env, local_best);
 
+			DB((env->dbg, LEVEL_4, "\t\tlocal best chunk (id %d) for color %d: ", local_best->id, col));
+			DBG_AFF_CHUNK(env, LEVEL_4, local_best);
+
 			if (! best_chunk || best_chunk->weight < local_best->weight) {
 				best_chunk = local_best;
 				best_color = col;
+				DB((env->dbg, LEVEL_4, "\n\t\t... setting global best chunk (id %d), color %d\n", best_chunk->id, best_color));
+			} else {
+				DB((env->dbg, LEVEL_4, "\n\t\t... omitting, global best is better\n"));
 			}
 		}
 
@@ -779,6 +1002,10 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 		return;
 	}
 
+	DB((env->dbg, LEVEL_2, "\tbest chunk #%d ", best_chunk->id));
+	DBG_AFF_CHUNK(env, LEVEL_2, best_chunk);
+	DB((env->dbg, LEVEL_2, "using color %d\n", best_color));
+
 	/* get the best fragment from the best list and color it */
 	bitset_foreach(best_chunk->nodes, idx) {
 		ir_node      *irn  = get_idx_irn(env->co->irg, idx);
@@ -786,17 +1013,16 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 		int          res;
 
 		res = change_node_color(env, node, best_color, changed_ones);
-		assert(res && "Coloring failed");
+		assert(res && "color manifesting failed");
 		node->fixed = 1;
-		node->col   = node->tmp_col;
 		node->chunk = best_chunk;
 	}
 
-	/* fix colors */
+	/* materialize colors on changed nodes */
 	while (! waitq_empty(changed_ones)) {
 		co_mst_irn_t *n = waitq_get(changed_ones);
-		n->fixed = 1;
-		n->col   = n->tmp_col;
+		n->tmp_fixed = 0;
+		n->col       = n->tmp_col;
 	}
 
 	/* remove the nodes in best chunk from original chunk */
@@ -825,7 +1051,6 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
 	}
 
 	/* clear obsolete chunks and free some memory */
-	delete_aff_chunk(env, c);
 	delete_aff_chunk(env, best_chunk);
 	bitset_free(visited);
 	del_waitq(changed_ones);
@@ -836,20 +1061,19 @@ static void color_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
  */
 int co_solve_heuristic_mst(copy_opt_t *co)
 {
-	unsigned     n_regs       = co->cenv->cls->n_regs;
+	unsigned     n_regs       = co->cls->n_regs;
 	bitset_t     *ignore_regs = bitset_alloca(n_regs);
 	unsigned     k;
 	ir_node      *irn;
 	co_mst_env_t mst_env;
 
-	memset(&mst_env, 0, sizeof(mst_env));
-
 	/* init phase */
 	phase_init(&mst_env.ph, "co_mst", co->irg, PHASE_DEFAULT_GROWTH, co_mst_irn_init, &mst_env);
 
-	k = be_put_ignore_regs(co->cenv->birg, co->cenv->cls, ignore_regs);
+	k = be_put_ignore_regs(co->cenv->birg, co->cls, ignore_regs);
 	k = n_regs - k;
 
+	FIRM_DBG_REGISTER(mst_env.dbg, "firm.be.co.heur4");
 	mst_env.n_regs      = n_regs;
 	mst_env.k           = k;
 	mst_env.chunks      = new_pqueue();
@@ -859,13 +1083,18 @@ int co_solve_heuristic_mst(copy_opt_t *co)
 	mst_env.aenv        = co->aenv;
 	pset_new_init(&mst_env.chunkset);
 
+	DBG((mst_env.dbg, LEVEL_1, "==== Coloring %+F, class %s ====\n", co->irg, co->cls->name));
+
 	/* build affinity chunks */
 	build_affinity_chunks(&mst_env);
 
 	/* color chunks as long as there are some */
 	while (! pqueue_empty(mst_env.chunks)) {
 		aff_chunk_t *chunk = pqueue_get(mst_env.chunks);
+
 		color_aff_chunk(&mst_env, chunk);
+		DB((mst_env.dbg, LEVEL_4, "<<<====== Coloring chunk (%d) done\n", chunk->id));
+		delete_aff_chunk(&mst_env, chunk);
 	}
 
 	/* apply coloring */
@@ -873,11 +1102,18 @@ int co_solve_heuristic_mst(copy_opt_t *co)
 		co_mst_irn_t *mirn = get_co_mst_irn(&mst_env, irn);
 		const arch_register_t *reg;
 
+		if (arch_irn_is(mst_env.aenv, irn, ignore))
+			continue;
+
 		assert(mirn->fixed && "Node should have fixed color");
 
-		reg = arch_register_for_index(co->cenv->cls, mirn->col);
+		/* skip nodes where color hasn't changed */
+		if (mirn->init_col == mirn->col)
+			continue;
+
+		reg = arch_register_for_index(co->cls, mirn->col);
 		arch_set_irn_register(co->aenv, irn, reg);
-		ir_printf("%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col);
+		DB((mst_env.dbg, LEVEL_1, "%+F set color from %d to %d\n", irn, mirn->init_col, mirn->col));
 	}
 
 	/* free allocated memory */