X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyheur2.c;h=c2478654efd9104c90047f942ad99771464c0a0f;hb=fe36fbcb66909a979e16111b8dc8cee19088fede;hp=df212f51fa1cf426afbb462d3ad3498fd19655b1;hpb=83d77a73fc9f2a6bfa9bfc55e3fbc0398b08e7b6;p=libfirm

diff --git a/ir/be/becopyheur2.c b/ir/be/becopyheur2.c
index df212f51f..c2478654e 100644
--- a/ir/be/becopyheur2.c
+++ b/ir/be/becopyheur2.c
@@ -1,18 +1,33 @@
+/*
+ * Copyright (C) 1995-2008 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.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
 
 /**
- * More experiments on coalescing.
- * @author Sebastian Hack
- * @date   14.04.2006
+ * @file
+ * @brief       More experiments on coalescing.
+ * @author      Sebastian Hack
+ * @date        14.04.2006
+ * @version     $Id$
  */
-
-#ifdef HAVE_CONFIG_H
 #include "config.h"
-#endif
 
-#ifdef WITH_LIBCORE
-#include <libcore/lc_opts.h>
-#include <libcore/lc_opts_enum.h>
-#endif /* WITH_LIBCORE */
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
 
 #include <stdlib.h>
 #include <limits.h>
@@ -20,6 +35,7 @@
 #include "list.h"
 #include "pdeq.h"
 #include "bitset.h"
+#include "raw_bitset.h"
 
 #include "debug.h"
 #include "bitfiddle.h"
@@ -30,28 +46,28 @@
 #include "irprintf.h"
 #include "irtools.h"
 
+#include "bemodule.h"
 #include "beabi.h"
-#include "benode_t.h"
+#include "benode.h"
 #include "becopyopt.h"
 #include "becopyopt_t.h"
 #include "bechordal_t.h"
+#include "beirg.h"
 
 #define DUMP_BEFORE 1
 #define DUMP_AFTER  2
 #define DUMP_CLOUD  4
 #define DUMP_ALL    2 * DUMP_CLOUD - 1
 
-static int    dump_flags      = 0;
-static int    subtree_iter    = 4;
-static double constr_factor   = 0.5;
-
-/* Options using libcore */
-#ifdef WITH_LIBCORE
+static unsigned dump_flags      = 0;
+static int      subtree_iter    = 4;
+static int      max_depth       = 20;
+static double   constr_factor   = 0.9;
 
 static const lc_opt_enum_mask_items_t dump_items[] = {
 	{ "before",  DUMP_BEFORE },
-    { "after",   DUMP_AFTER  },
-    { "cloud",   DUMP_CLOUD  },
+	{ "after",   DUMP_AFTER  },
+	{ "cloud",   DUMP_CLOUD  },
 	{ "all",     DUMP_ALL    },
 	{ NULL,      0 }
 };
@@ -61,19 +77,13 @@ static lc_opt_enum_mask_var_t dump_var = {
 };
 
 static const lc_opt_table_entry_t options[] = {
-	LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud",             &dump_var),
-	LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes (standard: 3)",             &subtree_iter),
+	LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                                         &dump_var),
+	LC_OPT_ENT_INT      ("iter", "iterations for subtree nodes",                           &subtree_iter),
 	LC_OPT_ENT_DBL      ("cf",   "factor of constraint importance (between 0.0 and 1.0)",  &constr_factor),
-	{ NULL }
+	LC_OPT_ENT_INT      ("max",  "maximum recursion depth",                                &max_depth),
+	LC_OPT_LAST
 };
 
-void be_co2_register_options(lc_opt_entry_t *grp)
-{
-	lc_opt_entry_t *co2_grp = lc_opt_get_grp(grp, "co2");
-	lc_opt_add_table(co2_grp, options);
-}
-#endif
-
 /*
   ____  _             _
  / ___|| |_ __ _ _ __| |_
@@ -99,7 +109,7 @@ typedef struct {
 } col_cost_pair_t;
 
 typedef struct {
-	phase_t     ph;
+	ir_phase     ph;
 	copy_opt_t *co;
 	bitset_t   *ignore_regs;
 	co2_irn_t  *touched;
@@ -110,7 +120,7 @@ typedef struct {
 } co2_t;
 
 struct _co2_irn_t {
-	ir_node         *irn;
+	const ir_node   *irn;
 	affinity_node_t *aff;
 	co2_irn_t       *touched_next;
 	col_t            tmp_col;
@@ -160,12 +170,17 @@ struct _co2_cloud_t {
 	struct list_head  list;
 };
 
+typedef struct {
+	co2_cloud_irn_t *src, *tgt;
+	int costs;
+} edge_t;
+
 #define FRONT_BASE(ci,col)  ((ci)->fronts + col * (ci)->mst_n_childs)
 
 #define get_co2_irn(co2, irn)         ((co2_irn_t *)       phase_get_or_set_irn_data(&co2->ph, irn))
 #define get_co2_cloud_irn(co2, irn)   ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
 
-static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
+static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data)
 {
 	co2_t *env         = (co2_t *) ph;
 	affinity_node_t *a = get_affinity_info(env->co, irn);
@@ -175,12 +190,12 @@ static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
 	memset(ci, 0, size);
 	INIT_LIST_HEAD(&ci->changed_list);
 	ci->touched_next = env->touched;
-	ci->orig_col     = get_irn_col(env->co, irn);
+	ci->orig_col     = get_irn_col(irn);
 	env->touched     = ci;
 	ci->irn          = irn;
 	ci->aff          = a;
 
-	if(a) {
+	if (a) {
 		co2_cloud_irn_t *cci = (co2_cloud_irn_t *) ci;
 		INIT_LIST_HEAD(&cci->cloud_list);
 		cci->mst_parent   = cci;
@@ -193,8 +208,8 @@ static void *co2_irn_init(phase_t *ph, ir_node *irn, void *data)
 
 static int cmp_clouds_gt(const void *a, const void *b)
 {
-	const co2_cloud_t **p = a;
-	const co2_cloud_t **q = b;
+	const co2_cloud_t * const *p = a;
+	const co2_cloud_t * const *q = b;
 	double c = CLOUD_WEIGHT(*p);
 	double d = CLOUD_WEIGHT(*q);
 	return QSORT_CMP(d, c);
@@ -213,29 +228,42 @@ static int col_cost_pair_lt(const void *a, const void *b)
 	return QSORT_CMP(c, d);
 }
 
-static col_t get_col(co2_t *env, ir_node *irn)
+int cmp_edges(const void *a, const void *b)
+{
+	const edge_t *p = a;
+	const edge_t *q = b;
+	return QSORT_CMP(q->costs, p->costs);
+}
+
+static col_t get_col(co2_t *env, const ir_node *irn)
 {
 	co2_irn_t *ci = get_co2_irn(env, irn);
 	return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
 }
 
-static INLINE int color_is_fix(co2_t *env, ir_node *irn)
+static inline int color_is_fix(co2_t *env, const ir_node *irn)
 {
 	co2_irn_t *ci = get_co2_irn(env, irn);
 	return ci->fixed || ci->tmp_fixed;
 }
 
-static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
+static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
 {
-	if(!ci->adm_cache) {
-		arch_register_req_t req;
+	if (ci->adm_cache == NULL) {
+		const arch_register_req_t *req;
 		ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
-		arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
-		if(arch_register_req_is(&req, limited)) {
-			req.limited(req.limited_env, ci->adm_cache);
+		req = arch_get_register_req_out(ci->irn);
+
+		if (arch_register_req_is(req, limited)) {
+			int i, n;
+
+			n = env->n_regs;
+			for (i = 0; i < n; ++i) {
+				if (rbitset_is_set(req->limited, i))
+					bitset_set(ci->adm_cache, i);
+			}
 			ci->is_constrained = 1;
-		}
-		else {
+		} else {
 			bitset_copy(ci->adm_cache, env->ignore_regs);
 			bitset_flip_all(ci->adm_cache);
 		}
@@ -244,40 +272,39 @@ static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
 	return ci->adm_cache;
 }
 
-static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
+static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
 {
 	bitset_copy(bs, get_adm(env, ci));
 	return bs;
 }
 
-static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
+static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
 {
 	bitset_t *bs = get_adm(env, ci);
 	return bitset_is_set(bs, col);
 }
 
-static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
+static inline int is_constrained(co2_t *env, co2_irn_t *ci)
 {
-	if(!ci->adm_cache)
+	if (!ci->adm_cache)
 		get_adm(env, ci);
 	return ci->is_constrained;
 }
 
-static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
+static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
 {
-	bitset_t *aux = bitset_alloca(env->co->cls->n_regs);
-	arch_register_req_t req;
-
-	arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
+	const arch_register_req_t *req = arch_get_register_req_out(irn);
 
-	if(arch_register_req_is(&req, limited)) {
-		bitset_pos_t elm;
-		int n_constr;
+	if (arch_register_req_is(req, limited)) {
+		unsigned n_regs   = env->co->cls->n_regs;
+		unsigned n_constr = 0;
+		unsigned i;
 
-		req.limited(req.limited_env, aux);
-		n_constr = bitset_popcnt(aux);
-		bitset_foreach(aux, elm) {
-			col_costs[elm].costs  = add_saturated(col_costs[elm].costs, costs / n_constr);
+		n_constr = rbitset_popcnt(req->limited, n_regs);
+		for (i = 0; i < n_regs; ++i) {
+			if (rbitset_is_set(req->limited, i)) {
+				col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
+			}
 		}
 	}
 }
@@ -294,14 +321,14 @@ static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *co
  */
 static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
 {
-	ir_node *irn       = ci->irn;
+	const ir_node *irn = ci->irn;
 	be_ifg_t *ifg      = env->co->cenv->ifg;
 	int n_regs         = env->co->cls->n_regs;
 	bitset_t *forb     = bitset_alloca(n_regs);
 	affinity_node_t *a = ci->aff;
 
 	bitset_pos_t elm;
-	ir_node *pos;
+	const ir_node *pos;
 	void *it;
 	int i;
 
@@ -309,16 +336,16 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co
 	admissible_colors(env, ci, forb);
 	bitset_flip_all(forb);
 
-	for(i = 0; i < n_regs; ++i) {
+	for (i = 0; i < n_regs; ++i) {
 		col_costs[i].col   = i;
 		col_costs[i].costs = 0;
 	}
 
-	if(a) {
+	if (a) {
 		neighb_t *n;
 
 		co_gs_foreach_neighb(a, n) {
-			if(color_is_fix(env, n->irn)) {
+			if (color_is_fix(env, n->irn)) {
 				col_t col = get_col(env, n->irn);
 				col_costs[col].costs = add_saturated(col_costs[col].costs, -n->costs * 128);
 			}
@@ -330,7 +357,7 @@ static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *co
 	it = be_ifg_neighbours_iter_alloca(ifg);
 	be_ifg_foreach_neighbour(ifg, it, irn, pos) {
 		col_t col = get_col(env, pos);
-		if(color_is_fix(env, pos)) {
+		if (color_is_fix(env, pos)) {
 			col_costs[col].costs  = INT_MAX;
 		}
 		else {
@@ -352,11 +379,12 @@ static void single_color_cost(co2_t *env, co2_irn_t *ci, col_t col, col_cost_pai
 	int n_regs = env->co->cls->n_regs;
 	int i;
 
-	for(i = 0; i < n_regs; ++i) {
+	for (i = 0; i < n_regs; ++i) {
 		seq[i].col   = i;
 		seq[i].costs = INT_MAX;
 	}
 
+	(void) ci;
 	assert(is_color_admissible(env, ci, col));
 	seq[col].col = 0;
 	seq[0].col   = col;
@@ -381,53 +409,33 @@ static void materialize_coloring(struct list_head *h)
 	}
 }
 
-typedef struct {
-	co2_irn_t *ci;
-	col_t col;
-} col_entry_t;
-
-static col_entry_t *save_coloring(struct obstack *obst, struct list_head *changed)
-{
-	co2_irn_t *pos;
-	col_entry_t ent;
-
-	list_for_each_entry(co2_irn_t, pos, changed, changed_list) {
-		ent.ci  = pos;
-		ent.col = pos->tmp_col;
-		pos->tmp_col = 0;
-		obstack_grow(obst, &ent, sizeof(ent));
-	}
-	memset(&ent, 0, sizeof(ent));
-	obstack_grow(obst, &ent, sizeof(ent));
-	return obstack_finish(obst);
-}
-
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
-static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth);
+static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
 
-static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
+static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
 {
 	int n_regs         = env->co->cls->n_regs;
 	be_ifg_t *ifg      = env->co->cenv->ifg;
 	co2_irn_t *ci      = get_co2_irn(env, irn);
 	int res            = 0;
-	int n_aff          = 0;
 
 	int i;
 
-	for(i = 0; i < n_regs; ++i) {
+	if (depth >= max_depth)
+	  return 0;
+
+	for (i = 0; i < n_regs; ++i) {
 		col_t tgt_col  = col_list[i].col;
 		unsigned costs = col_list[i].costs;
 		int neigh_ok   = 1;
 
 		struct list_head changed;
-		ir_node *n;
+		const ir_node *n;
 		void *it;
 
 		DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
 
 		/* If the costs for that color (and all successive) are infinite, bail out we won't make it anyway. */
-		if(INFEASIBLE(costs)) {
+		if (INFEASIBLE(costs)) {
 			DB((env->dbg, LEVEL_4, "\t\t%2{firm:indent}color %d infeasible\n", depth, tgt_col));
 			ci->tmp_fixed = 0;
 			return 0;
@@ -448,7 +456,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l
 		be_ifg_foreach_neighbour(ifg, it, irn, n) {
 
 			/* try to re-color the neighbor if it has the target color. */
-			if(get_col(env, n) == tgt_col) {
+			if (get_col(env, n) == tgt_col) {
 				struct list_head tmp;
 
 				/*
@@ -460,7 +468,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l
 				INIT_LIST_HEAD(&tmp);
 				neigh_ok = change_color_not(env, n, tgt_col, &tmp, depth + 1);
 				list_splice(&tmp, &changed);
-				if(!neigh_ok)
+				if (!neigh_ok)
 					break;
 			}
 		}
@@ -470,7 +478,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l
 		We managed to assign the target color to all neighbors, so from the perspective
 		of the current node, every thing was ok and we can return safely.
 		*/
-		if(neigh_ok) {
+		if (neigh_ok) {
 			DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}color %d(%d) was ok\n", depth, tgt_col, costs));
 			list_splice(&changed, parent_changed);
 			res = 1;
@@ -488,7 +496,7 @@ static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct l
 	return res;
 }
 
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
+static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
 {
 	co2_irn_t *ci = get_co2_irn(env, irn);
 	int res       = 0;
@@ -497,8 +505,8 @@ static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list
 	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}clearing %+F(%d) of color %d\n", depth, irn, col, not_col));
 
 	/* the node does not have to forbidden color. That's fine, mark it as visited and return. */
-	if(col != not_col) {
-		if(!ci->tmp_fixed) {
+	if (col != not_col) {
+		if (!ci->tmp_fixed) {
 			ci->tmp_col     = col;
 			ci->tmp_fixed   = 1;
 		}
@@ -508,9 +516,9 @@ static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list
 	}
 
 	/* The node has the color it should not have _and_ has not been visited yet. */
-	if(!color_is_fix(env, irn)) {
+	if (!color_is_fix(env, irn)) {
 		int n_regs            = env->co->cls->n_regs;
-		col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
+		col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
 
 		/* Get the costs for giving the node a specific color. */
 		determine_color_costs(env, ci, csts);
@@ -529,7 +537,7 @@ static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list
 	return res;
 }
 
-static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
+static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
 {
 	co2_irn_t *ci = get_co2_irn(env, irn);
 	col_t col     = get_col(env, irn);
@@ -538,8 +546,8 @@ static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct l
 	DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying to set %+F(%d) to color %d\n", depth, irn, col, tgt_col));
 
 	/* the node has the wanted color. That's fine, mark it as visited and return. */
-	if(col == tgt_col) {
-		if(!ci->tmp_fixed) {
+	if (col == tgt_col) {
+		if (!ci->tmp_fixed) {
 			ci->tmp_col     = col;
 			ci->tmp_fixed   = 1;
 			list_add(&ci->changed_list, parent_changed);
@@ -549,9 +557,9 @@ static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct l
 		goto end;
 	}
 
-	if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
+	if (!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
 		int n_regs           = env->co->cls->n_regs;
-		col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
+		col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
 
 		/* Get the costs for giving the node a specific color. */
 		single_color_cost(env, ci, tgt_col, seq);
@@ -566,167 +574,19 @@ end:
 	return res;
 }
 
-static void front_inval_color(co2_cloud_irn_t *ci, col_t col)
-{
-	int *base = FRONT_BASE(ci, col);
-	memset(base, -1, ci->mst_n_childs * sizeof(base[0]));
-}
-
-typedef struct {
-	co2_cloud_irn_t *src, *tgt;
-	int costs;
-} edge_t;
-
-int cmp_edges(const void *a, const void *b)
-{
-	const edge_t *p = a;
-	const edge_t *q = b;
-	return QSORT_CMP(q->costs, p->costs);
-}
-
-static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
-{
-	while(ci != ci->mst_parent)
-		ci = ci->mst_parent;
-	return ci;
-}
-
-
-static int cmp_parent(const void *a, const void *b)
-{
-	const co2_cloud_irn_t *p = a;
-	const co2_cloud_irn_t *q = b;
-	return QSORT_CMP(q->mst_costs, p->mst_costs);
-}
-
-static void fill_tmp_coloring(co2_cloud_irn_t *ci, col_t col)
-{
-	int n_regs = ci->cloud->env->n_regs;
-	int i, j;
-
-	for(i = 0; i < ci->mst_n_childs; ++i) {
-		co2_cloud_irn_t *c = ci->mst_childs[i];
-		for(j = 0; j < n_regs; ++j) {
-			int costs = c->col_costs[j];
-			if(INFEASIBLE(costs))
-				c->tmp_coloring[j].costs = INT_MAX;
-			else {
-				int add = j != (int) col ? c->mst_costs : 0;
-				c->tmp_coloring[j].costs = add + costs;
-			}
-			c->tmp_coloring[j].col = j;
-		}
-		qsort(c->tmp_coloring, n_regs, sizeof(c->tmp_coloring[0]), col_cost_pair_lt);
-	}
-}
-
-static void determine_start_colors(co2_cloud_irn_t *ci, col_cost_pair_t *seq)
-{
-	int n_regs    = ci->cloud->env->n_regs;
-	bitset_t *adm = bitset_alloca(n_regs);
-	int i, j;
-
-	// TODO: Prefer some colors depending on the neighbors, etc.
-
-	admissible_colors(ci->cloud->env, &ci->inh, adm);
-	for(i = 0; i < n_regs; ++i) {
-		seq[i].col   = i;
-
-		if (!bitset_is_set(adm, i))
-			seq[i].costs = INT_MAX;
-		else {
-			seq[i].costs = 0;
-			for(j = 0; j < ci->mst_n_childs; ++j) {
-				co2_cloud_irn_t *child = ci->mst_childs[j];
-				if (!INFEASIBLE(child->col_costs[i]))
-					seq[i].costs -= ci->mst_childs[j]->col_costs[i];
-			}
-		}
-	}
-
-	qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
-}
-
-static int push_front(co2_cloud_irn_t *ci, int *front)
-{
-	co2_t *env   = ci->cloud->env;
-	int n_regs   = env->n_regs;
-	int min_diff = INT_MAX;
-	int min_chld = -1;
-	int i;
-
-	for(i = 0; i < ci->mst_n_childs; ++i) {
-		co2_cloud_irn_t *child = ci->mst_childs[i];
-		int idx = front[i];
-
-
-		if(idx + 1 < n_regs) {
-			int diff = child->tmp_coloring[idx].costs - child->tmp_coloring[idx + 1].costs;
-			if(diff < min_diff) {
-				min_diff = diff;
-				min_chld = i;
-			}
-		}
-	}
-
-	if(min_chld >= 0) {
-		co2_cloud_irn_t *child = ci->mst_childs[min_chld];
-		DBG((env->dbg, LEVEL_3, "\tsmallest diff with child %+F on index %d is %d\n", child->inh.irn, front[min_chld], min_diff));
-		front[min_chld] += 1;
-	}
-
-	return min_chld;
-}
-
-static int color_subtree(co2_cloud_irn_t *ci, col_t col, struct list_head *changed, int depth)
-{
-	int n_childs = ci->mst_n_childs;
-	/*
-		select the front for the given color.
-		The front will determine the colors of the children.
-	*/
-	int *front = FRONT_BASE(ci, col);
-	int i, ok = 1;
-
-	ok = change_color_single(ci->cloud->env, ci->inh.irn, col, changed, 0);
-	for(i = 0; i < n_childs && ok; ++i) {
-		co2_cloud_irn_t *child = ci->mst_childs[i];
-		col_t col              = front[i];
-
-		ok = color_subtree(child, col, changed, depth + 1);
-	}
-
-	return ok;
-}
-
-static int try_coloring(co2_cloud_irn_t *ci, col_t col, int *front, int *initial_ok, int depth)
-{
-	co2_t *env = ci->cloud->env;
-	struct list_head changed;
-	int i, ok = 1;
-
-	INIT_LIST_HEAD(&changed);
-	*initial_ok = ok = change_color_single(env, ci->inh.irn, col, &changed, depth + 1);
-
-	for (i = 0; i < ci->mst_n_childs && ok; ++i) {
-		co2_cloud_irn_t *child = ci->mst_childs[i];
-		col_t tgt_col = child->tmp_coloring[front[i]].col;
-
-		ok = color_subtree(child, tgt_col, &changed, depth + 1);
-	}
-
-	reject_coloring(&changed);
-
-	return ok;
-}
-
+/**
+ * Examine the costs of the current coloring concerning a MST subtree.
+ * @param ci  The subtree root.
+ * @param col The color of @p ci.
+ * @return    The best coloring for that subtree under the assumption that @p ci has color @p col.
+ */
 static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
 {
 	int *front = FRONT_BASE(ci, col);
 	int cost   = 0;
 	int i;
 
-	for(i = 0; i < ci->mst_n_childs; ++i) {
+	for (i = 0; i < ci->mst_n_childs; ++i) {
 		co2_cloud_irn_t *chld = ci->mst_childs[i];
 		col_t chld_col        = front[i];
 
@@ -737,97 +597,15 @@ static int examine_subtree_coloring(co2_cloud_irn_t *ci, col_t col)
 	return cost;
 }
 
-static int cloud_mst_build_colorings(co2_cloud_irn_t *ci, int depth)
-{
-	co2_t *env           = ci->cloud->env;
-	int n_regs           = env->n_regs;
-	col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
-	int *front           = alloca(ci->mst_n_childs * sizeof(front[0]));
-	int best_col         = -1;
-	int best_cost        = INT_MAX;
-
-
-	int i;
-
-	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}build colorings: %+F\n", depth, ci->inh.irn));
-
-	for (i = 0; i < ci->mst_n_childs; ++i)
-		cloud_mst_build_colorings(ci->mst_childs[i], depth + 1);
-
-	for (i = 0; i < n_regs; ++i)
-		ci->col_costs[i] = INT_MAX;
-
-	/* Sort the children according to the cost of the affinity edge they have to the current node. */
-	// qsort(child, ci->mst_n_childs, sizeof(childs[0]), cmp_parent);
-
-	determine_start_colors(ci, seq);
-	// qsort(seq, n_regs, sizeof(seq[0]), col_cost_pair_lt);
-
-	for(i = 0; i < n_regs; ++i) {
-		col_t col = seq[i].col;
-		int costs = seq[i].costs;
-		int done  = 0;
-
-		if(INFEASIBLE(costs))
-			break;
-
-		/*
-			Judge, if it is worthwhile trying this color.
-			If another color was so good that we cannot get any better, bail out here.
-			Perhaps???
-		*/
-
-		DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}%+F trying color %d\n", depth, ci->inh.irn, col));
-
-		/* This sorts the tmp_coloring array in the children according to the costs of the current color. */
-		fill_tmp_coloring(ci, col);
-
-		/* Initialize the front. It gives the indexes into the color tmp_coloring array. */
-		memset(front, 0, ci->mst_n_childs * sizeof(front));
-
-		/*
-			As long as we have color configurations to try.
-			We try the best ones first and get worse over and over.
-		*/
-		while (!done) {
-			int j, try_push;
-
-			if (try_coloring(ci, col, front, &try_push, depth + 1)) {
-				int *res_front = FRONT_BASE(ci, col);
-				int costs;
-
-				for(j = 0; j < ci->mst_n_childs; ++j) {
-					co2_cloud_irn_t *child = ci->mst_childs[j];
-					col_t col              = child->tmp_coloring[front[j]].col;
-					res_front[j] = col;
-				}
-
-				costs = examine_subtree_coloring(ci, col);
-				ci->col_costs[col] = costs;
-				done = 1;
-
-				/* Set the current best color. */
-				if(costs < best_cost) {
-					best_cost = costs;
-					best_col  = col;
-				}
-			}
-
-			DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %s\n", depth, done ? "ok" : "failed"));
-
-			/* Worsen the configuration, if that one didn't succeed. */
-			if (!done)
-				done = try_push ? push_front(ci, front) < 0 : 1;
-		}
-	}
-
-	DBG((env->dbg, LEVEL_2, "%2{firm:indent} %+F\n", depth, ci->inh.irn));
-	for(i = 0; i < n_regs; ++i)
-		DBG((env->dbg, LEVEL_2, "%2{firm:indent}  color %d costs %d\n", depth, i, ci->col_costs[i]));
-
-	return best_col;
-}
-
+/**
+ * Determine color badnesses of a node.
+ * Badness means that it is unlikely that the node in question can
+ * obtain a color. The higher the badness, the more unlikely it is that
+ * the node can be assigned that color.
+ * @param ci      The node.
+ * @param badness An integer array as long as there are registers.
+ * @note          The array <code>badness</code> is not cleared.
+ */
 static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
 {
 	co2_t *env     = ci->cloud->env;
@@ -837,7 +615,7 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
 	bitset_t *bs   = bitset_alloca(n_regs);
 
 	bitset_pos_t elm;
-	ir_node *irn;
+	const ir_node *irn;
 	void *it;
 
 	admissible_colors(env, &ci->inh, bs);
@@ -851,30 +629,26 @@ static void node_color_badness(co2_cloud_irn_t *ci, int *badness)
 		co2_irn_t *ni = get_co2_irn(env, irn);
 
 		admissible_colors(env, ni, bs);
-		if(bitset_popcnt(bs) == 1) {
+		if (bitset_popcnt(bs) == 1) {
 			bitset_pos_t c = bitset_next_set(bs, 0);
 			badness[c] += ci->costs;
 		}
 
-		else if(ni->fixed) {
+		else if (ni->fixed) {
 			col_t c = get_col(env, ni->irn);
 			badness[c] += ci->costs;
 		}
 	}
 	be_ifg_neighbours_break(ifg, it);
-
-}
-
-static int cloud_color_badness(co2_cloud_t *cloud)
-{
-	int *badness = alloca(cloud->env->n_regs * sizeof(badness[0]));
-	int i;
-
-	memset(badness, 0, cloud->env->n_regs * sizeof(badness[0]));
-	for(i = 0; i < cloud->n_memb; ++i)
-		node_color_badness(cloud->seq[i], badness);
 }
 
+/**
+ * Determine the badness of a MST subtree.
+ * The badness is written into the <code>color_badness</code> array of each node and accumulated in the parents.
+ * @see node_color_badness() for a definition of badness.
+ * @param ci    The root of the subtree.
+ * @param depth Depth for debugging purposes.
+ */
 static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
 {
 	co2_t *env     = ci->cloud->env;
@@ -883,33 +657,36 @@ static void determine_color_badness(co2_cloud_irn_t *ci, int depth)
 	node_color_badness(ci, ci->color_badness);
 
 	/* Collect the color badness for the whole subtree */
-	for(i = 0; i < ci->mst_n_childs; ++i) {
+	for (i = 0; i < ci->mst_n_childs; ++i) {
 		co2_cloud_irn_t *child = ci->mst_childs[i];
 		determine_color_badness(child, depth + 1);
 
-		for(j = 0; j < env->n_regs; ++j)
+		for (j = 0; j < env->n_regs; ++j)
 			ci->color_badness[j] += child->color_badness[j];
 	}
 
-	for(j = 0; j < env->n_regs; ++j)
+	for (j = 0; j < env->n_regs; ++j)
 		DBG((env->dbg, LEVEL_2, "%2{firm:indent}%+F col %d badness %d\n", depth, ci->inh.irn, j, ci->color_badness[j]));
 }
 
+/**
+ * Unfix all nodes in a MST subtree.
+ */
 static void unfix_subtree(co2_cloud_irn_t *ci)
 {
 	int i;
 
 	ci->inh.fixed = 0;
-	for(i = 0; i < ci->mst_n_childs; ++i)
+	for (i = 0; i < ci->mst_n_childs; ++i)
 		unfix_subtree(ci->mst_childs[i]);
 }
 
 static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 {
 	co2_t *env           = ci->cloud->env;
-	col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
+	col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
 	int is_root          = ci->mst_parent == ci;
-	col_t parent_col     = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
+	col_t parent_col     = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
 	int min_badness      = INT_MAX;
 	int best_col_costs   = INT_MAX;
 	int best_col         = -1;
@@ -919,7 +696,7 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 	struct list_head changed;
 	int ok, i, j;
 
-	for(i = 0; i < n_regs; ++i) {
+	for (i = 0; i < n_regs; ++i) {
 		int badness = ci->color_badness[i];
 
 		seq[i].col   = i;
@@ -929,7 +706,7 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 	}
 
 	/* If we are not the root and the parent's color is allowed for this node give it top prio. */
-	if(!is_root && is_color_admissible(env, &ci->inh, parent_col))
+	if (!is_root && is_color_admissible(env, &ci->inh, parent_col))
 		seq[parent_col].costs = min_badness - 1;
 
 	/* Sort the colors. The will be processed in that ordering. */
@@ -937,9 +714,8 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 
 	DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}starting top-down coalesce for %+F\n", depth, ci->inh.irn));
 	INIT_LIST_HEAD(&changed);
-	for(i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
+	for (i = 0; i < (best_col < 0 ? n_regs : n_iter); ++i) {
 		col_t col    = seq[i].col;
-		int costs    = seq[i].costs;
 		int add_cost = !is_root && col != parent_col ? ci->mst_costs : 0;
 
 		int subtree_costs, sum_costs;
@@ -949,7 +725,7 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 		unfix_subtree(ci);
 		INIT_LIST_HEAD(&changed);
 		ok = change_color_single(env, ci->inh.irn, col, &changed, depth);
-		if(ok) {
+		if (ok) {
 			materialize_coloring(&changed);
 			ci->inh.fixed = 1;
 		}
@@ -957,42 +733,34 @@ static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
 		else
 			continue;
 
-		for(j = 0; j < ci->mst_n_childs; ++j) {
+		for (j = 0; j < ci->mst_n_childs; ++j) {
 			co2_cloud_irn_t *child = ci->mst_childs[j];
 			ok = coalesce_top_down(child, j, depth + 1) >= 0;
-			if(ok)
+			if (ok)
 				child->inh.fixed = 1;
 			else
 				break;
 		}
 
 		/* If the subtree could not be colored, we have to try another color. */
-		if(!ok)
+		if (!ok)
 			continue;
 
 		subtree_costs      = examine_subtree_coloring(ci, col);
 		sum_costs          = subtree_costs + add_cost;
 		DBG((env->dbg, LEVEL_2, "\t%2{firm:indent}-> %+F costing %d + %d is ok.\n", depth, ci->inh.irn, subtree_costs, add_cost));
 
-		if(sum_costs < best_col_costs) {
+		if (sum_costs < best_col_costs) {
 			best_col           = col;
 			best_col_costs     = sum_costs;
 			ci->col_costs[col] = subtree_costs;
 		}
 
-		if(sum_costs == 0)
+		if (sum_costs == 0)
 			break;
-
-		/* If we are at the root and we achieved an acceptable amount of optimization, we finish. */
-#if 0
-		if(is_root && (ci->cloud->inevit * stop_percentage < ci->cloud->inevit - sum_costs)) {
-			assert(best_col != -1);
-			break;
-		}
-#endif
 	}
 
-	if(!is_root) {
+	if (!is_root) {
 		int *front = FRONT_BASE(ci->mst_parent, parent_col);
 		front[child_nr] = best_col;
 	}
@@ -1007,7 +775,7 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i
 	int costs           = 0;
 	neighb_t *n;
 
-	if(ci->cloud)
+	if (ci->cloud)
 		return;
 
 	/* mark the node as visited and add it to the cloud. */
@@ -1020,7 +788,7 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i
 	co_gs_foreach_neighb(a, n) {
 		costs += n->costs;
 		DB((env->dbg, LEVEL_3, "\t\tneigh %+F cost %d\n", n->irn, n->costs));
-		if(be_ifg_connected(ifg, a->irn, n->irn))
+		if (be_ifg_connected(ifg, a->irn, n->irn))
 			cloud->inevit += n->costs;
 	}
 
@@ -1033,7 +801,7 @@ static void populate_cloud(co2_t *env, co2_cloud_t *cloud, affinity_node_t *a, i
 	cloud->n_memb++;
 
 	/* If this is the heaviest node in the cloud, set it as the cloud's master. */
-	if(costs >= curr_costs) {
+	if (costs >= curr_costs) {
 		curr_costs    = costs;
 		cloud->master = ci;
 	}
@@ -1063,9 +831,6 @@ static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
 	populate_cloud(env, cloud, a, 0);
 	cloud->freedom = (cloud->n_memb * env->n_regs) / cloud->freedom;
 
-	/* Allocate space for the best colors array, where the best coloring is saved. */
-	// cloud->best_cols = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->best_cols[0]));
-
 	/* Also allocate space for the node sequence and compute that sequence. */
 	cloud->seq    = phase_alloc(&env->ph, cloud->n_memb * sizeof(cloud->seq[0]));
 
@@ -1081,7 +846,7 @@ static co2_cloud_t *new_cloud(co2_t *env, affinity_node_t *a)
 
 static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
 {
-	ir_node *irn = ci->inh.irn;
+	const ir_node *irn = ci->inh.irn;
 	int *front   = FRONT_BASE(ci, col);
 	int i, ok;
 	struct list_head changed;
@@ -1090,38 +855,43 @@ static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
 
 	DBG((ci->cloud->env->dbg, LEVEL_2, "%2{firm:indent}setting %+F to %d\n", depth, irn, col));
 	ok = change_color_single(ci->cloud->env, irn, col, &changed, depth);
-	assert(ok && "Color changing may not fail while committing the coloring");
+	// assert(ok && "Color changing may not fail while committing the coloring");
 	materialize_coloring(&changed);
 
- 	for(i = 0; i < ci->mst_n_childs; ++i) {
+ 	for (i = 0; i < ci->mst_n_childs; ++i) {
 		apply_coloring(ci->mst_childs[i], front[i], depth + 1);
 	}
 }
 
+static co2_cloud_irn_t *find_mst_root(co2_cloud_irn_t *ci)
+{
+	while (ci != ci->mst_parent)
+		ci = ci->mst_parent;
+	return ci;
+}
+
+
 static void process_cloud(co2_cloud_t *cloud)
 {
 	co2_t *env  = cloud->env;
 	int n_regs  = env->n_regs;
 	int n_edges = 0;
-	int *mst_edges = malloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
+	int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
 	pdeq *q;
 
-	struct list_head changed;
 	edge_t *edges;
 	int i;
 	int best_col;
 
-	memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
-
 	/* Collect all edges in the cloud on an obstack and sort the increasingly */
 	obstack_init(&cloud->obst);
-	for(i = 0; i < cloud->n_memb; ++i) {
+	for (i = 0; i < cloud->n_memb; ++i) {
 		co2_cloud_irn_t *ci = cloud->seq[i];
 		neighb_t *n;
 
 		co_gs_foreach_neighb(ci->inh.aff, n) {
 			co2_cloud_irn_t *ni = get_co2_cloud_irn(cloud->env, n->irn);
-			if(ci->index < ni->index) {
+			if (ci->index < ni->index) {
 				edge_t e;
 				e.src   = ci;
 				e.tgt   = ni;
@@ -1136,13 +906,13 @@ static void process_cloud(co2_cloud_t *cloud)
 
 	/* Compute the maximum spanning tree using Kruskal/Union-Find */
 	DBG((env->dbg, LEVEL_2, "computing spanning tree of cloud with master %+F\n", cloud->master->inh.irn));
-	for(i = 0; i < n_edges; ++i) {
+	for (i = 0; i < n_edges; ++i) {
 		edge_t *e        = &edges[i];
 		co2_cloud_irn_t *rs = find_mst_root(e->src);
 		co2_cloud_irn_t *rt = find_mst_root(e->tgt);
 
 		/* if the union/find roots are different */
-		if(rs != rt) {
+		if (rs != rt) {
 			int si = e->src->index;
 			int ti = e->tgt->index;
 
@@ -1160,15 +930,15 @@ static void process_cloud(co2_cloud_t *cloud)
 	cloud->master->mst_parent = cloud->master;
 	cloud->mst_root = cloud->master;
 	q = new_pdeq1(cloud->master);
-	while(!pdeq_empty(q)) {
+	while (!pdeq_empty(q)) {
 		co2_cloud_irn_t *ci = pdeq_getl(q);
 		int ofs    = ci->index * cloud->n_memb;
 		int end    = ofs + cloud->n_memb;
 		int i;
 
 		ci->mst_n_childs = 0;
-		for(i = ofs; i < end; ++i) {
-			if(mst_edges[i] != 0) {
+		for (i = ofs; i < end; ++i) {
+			if (mst_edges[i] != 0) {
 				int other = i - ofs;
 				co2_cloud_irn_t *child = cloud->seq[i - ofs];
 
@@ -1194,28 +964,23 @@ static void process_cloud(co2_cloud_t *cloud)
 
 
 	DBG((env->dbg, LEVEL_3, "mst:\n"));
-	for(i = 0; i < cloud->n_memb; ++i) {
-		co2_cloud_irn_t *ci = cloud->seq[i];
+	for (i = 0; i < cloud->n_memb; ++i) {
+		DEBUG_ONLY(co2_cloud_irn_t *ci = cloud->seq[i]);
 		DBG((env->dbg, LEVEL_3, "\t%+F -> %+F\n", ci->inh.irn, ci->mst_parent->inh.irn));
 	}
 
-	for(i = 0; i < cloud->n_memb; ++i) {
+	for (i = 0; i < cloud->n_memb; ++i) {
 		co2_cloud_irn_t *ci = cloud->seq[i];
 		int n_childs = ci->mst_n_childs;
 		int j;
 
-		ci->col_costs       = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
-		ci->tmp_coloring    = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
-		ci->fronts          = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
-		ci->color_badness   = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
-		memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
-		memset(ci->col_costs,     0, n_regs * sizeof(ci->col_costs[0]));
-		memset(ci->tmp_coloring,  0, n_regs * sizeof(ci->tmp_coloring[0]));
-		memset(ci->fronts,        0, n_regs * n_childs * sizeof(ci->fronts[0]));
+		ci->col_costs       = OALLOCNZ(&cloud->obst, int,             n_regs);
+		ci->tmp_coloring    = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
+		ci->fronts          = OALLOCNZ(&cloud->obst, int,             n_regs * n_childs);
+		ci->color_badness   = OALLOCNZ(&cloud->obst, int,             n_regs);
 
-		for(j = 0; j < env->n_regs; j++)
+		for (j = 0; j < env->n_regs; j++)
 			ci->col_costs[j] = INT_MAX;
-
 	}
 
 	determine_color_badness(cloud->mst_root, 0);
@@ -1229,7 +994,7 @@ static void process_cloud(co2_cloud_t *cloud)
 		cloud->mst_root->inh.irn, best_col, examine_subtree_coloring(cloud->mst_root, best_col)));
 
 	/* Fix all nodes in the cloud. */
-	for(i = 0; i < cloud->n_memb; ++i)
+	for (i = 0; i < cloud->n_memb; ++i)
 		cloud->seq[i]->inh.fixed = 1;
 
 	/* Free all space used while optimizing this cloud. */
@@ -1241,7 +1006,7 @@ static int cloud_costs(co2_cloud_t *cloud)
 	int i, costs = 0;
 	neighb_t *n;
 
-	for(i = 0; i < cloud->n_memb; ++i) {
+	for (i = 0; i < cloud->n_memb; ++i) {
 		co2_irn_t *ci = (co2_irn_t *) cloud->seq[i];
 		col_t col = get_col(cloud->env, ci->irn);
 		co_gs_foreach_neighb(ci->aff, n) {
@@ -1268,21 +1033,24 @@ static void process(co2_t *env)
 	co_gs_foreach_aff_node(env->co, a) {
 		co2_cloud_irn_t *ci = get_co2_cloud_irn(env, a->irn);
 
-		if(!ci->cloud) {
-			co2_cloud_t *cloud = new_cloud(env, a);
+		if (!ci->cloud) {
+			new_cloud(env, a);
 			n_clouds++;
 		}
 	}
 
 	i = 0;
-	clouds = xmalloc(n_clouds * sizeof(clouds[0]));
+	clouds = XMALLOCN(co2_cloud_t*, n_clouds);
 	list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
 		clouds[i++] = pos;
 	qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
 
-	for(i = 0; i < n_clouds; ++i) {
+	for (i = 0; i < n_clouds; ++i) {
 		init_costs  += cloud_costs(clouds[i]);
+
+		/* Process the cloud. */
 		process_cloud(clouds[i]);
+
 		all_costs   += clouds[i]->costs;
 		final_costs += cloud_costs(clouds[i]);
 
@@ -1292,7 +1060,8 @@ static void process(co2_t *env)
 			FILE *f;
 
 			ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_cloud_%d.dot", env->co->irg, env->co->cls->name, i);
-			if(f = fopen(buf, "wt")) {
+			f = fopen(buf, "wt");
+			if (f != NULL) {
 				be_ifg_dump_dot(env->co->cenv->ifg, env->co->irg, f, &ifg_dot_cb, env);
 				fclose(f);
 			}
@@ -1306,12 +1075,11 @@ static void process(co2_t *env)
 
 static void writeback_colors(co2_t *env)
 {
-	const arch_env_t *aenv = env->co->aenv;
 	co2_irn_t *irn;
 
-	for(irn = env->touched; irn; irn = irn->touched_next) {
+	for (irn = env->touched; irn; irn = irn->touched_next) {
 		const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
-		arch_set_irn_register(aenv, irn->irn, reg);
+		arch_set_irn_register((ir_node*)irn->irn, reg);
 	}
 }
 
@@ -1325,9 +1093,9 @@ static void writeback_colors(co2_t *env)
                                                            |_|            |___/
 */
 
-static const char *get_dot_color_name(int col)
+static const char *get_dot_color_name(size_t col)
 {
-	static const char *names[] = {
+	static const char *const names[] = {
 		"blue",
 		"red",
 		"green",
@@ -1361,21 +1129,20 @@ static const char *get_dot_color_name(int col)
 		"palevioletred"
 	};
 
-	return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
+	return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
 }
 
-static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
+static const char *get_dot_shape_name(co2_irn_t *ci)
 {
-	arch_register_req_t req;
+	const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
 
-	arch_get_register_req(env->co->aenv, &req, ci->irn, BE_OUT_POS(0));
-	if(arch_register_req_is(&req, limited))
+	if (arch_register_req_is(req, limited))
 		return "diamond";
 
-	if(ci->fixed)
+	if (ci->fixed)
 		return "rectangle";
 
-	if(ci->tmp_fixed)
+	if (ci->tmp_fixed)
 		return "hexagon";
 
 	return "ellipse";
@@ -1383,13 +1150,15 @@ static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
 
 static void ifg_dump_graph_attr(FILE *f, void *self)
 {
+	(void) self;
 	fprintf(f, "overlay=false");
 }
 
 static int ifg_is_dump_node(void *self, ir_node *irn)
 {
-	co2_t *env = self;
-	return !arch_irn_is(env->co->aenv, irn, ignore);
+	const arch_register_req_t *req = arch_get_register_req_out(irn);
+	(void)self;
+	return !(req->type & arch_register_req_type_ignore);
 }
 
 static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
@@ -1400,17 +1169,17 @@ static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
 
 	char buf[128] = "";
 
-	if(ci->aff) {
+	if (ci->aff) {
 		co2_cloud_irn_t *cci = (void *) ci;
 		if (cci->cloud && cci->cloud->mst_root == cci)
 			peri = 2;
 
-		if(cci->cloud && cci->cloud->mst_root)
-			snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
+		if (cci->cloud && cci->cloud->mst_root)
+			ir_snprintf(buf, sizeof(buf), "%+F", cci->cloud->mst_root->inh.irn);
 	}
 
 	ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
-		get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
+		get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
 }
 
 static void ifg_dump_at_end(FILE *file, void *self)
@@ -1418,38 +1187,25 @@ static void ifg_dump_at_end(FILE *file, void *self)
 	co2_t *env = self;
 	affinity_node_t *a;
 
-#if 0
-	co2_cloud_t *pos;
-
-	list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list) {
-		int i;
-
-		for(i = 0; i < pos->n_memb - 1; ++i) {
-			fprintf(file, "\tn%d -- n%d [style=dotted color=green];\n", get_irn_idx(pos->seq[i]->inh.irn), get_irn_idx(pos->seq[i+1]->inh.irn));
-		}
-	}
-#endif
-
-
 	co_gs_foreach_aff_node(env->co, a) {
 		co2_cloud_irn_t *ai = get_co2_cloud_irn(env, a->irn);
 		int idx = get_irn_idx(a->irn);
 		neighb_t *n;
 
-		if(ai->mst_parent != ai)
+		if (ai->mst_parent != ai)
 			fprintf(file, "\tn%d -- n%d [style=dotted color=blue arrowhead=normal];\n", idx, get_irn_idx(ai->mst_parent->inh.irn));
 
 		co_gs_foreach_neighb(a, n) {
 			int nidx = get_irn_idx(n->irn);
 			co2_cloud_irn_t *ci = get_co2_cloud_irn(env, n->irn);
 
-			if(idx < nidx) {
+			if (idx < nidx) {
 				const char *color = get_col(env, a->irn) == get_col(env, n->irn) ? "black" : "red";
 				const char *arr = "arrowhead=dot arrowtail=dot";
 
-				if(ci->mst_parent == ai)
+				if (ci->mst_parent == ai)
 					arr = "arrowtail=normal";
-				else if(ai->mst_parent == ci)
+				else if (ai->mst_parent == ci)
 					arr = "arrowhead=normal";
 
 				fprintf(file, "\tn%d -- n%d [label=\"%d\" %s style=dashed color=%s weight=0.01];\n", idx, nidx, n->costs, arr, color);
@@ -1468,28 +1224,26 @@ static be_ifg_dump_dot_cb_t ifg_dot_cb = {
 	ifg_dump_at_end
 };
 
-
-void co_solve_heuristic_new(copy_opt_t *co)
+int co_solve_heuristic_new(copy_opt_t *co)
 {
-	char buf[256];
+	char  buf[256];
 	co2_t env;
-	FILE *f;
+	FILE  *f;
 
-	phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
+	phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
 	env.touched     = NULL;
 	env.visited     = 0;
 	env.co          = co;
 	env.n_regs      = co->cls->n_regs;
 	env.ignore_regs = bitset_alloca(co->cls->n_regs);
-	arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
-	bitset_flip_all(env.ignore_regs);
-	be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
+	be_put_ignore_regs(co->cenv->birg, co->cls, env.ignore_regs);
 	FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
 	INIT_LIST_HEAD(&env.cloud_head);
 
-	if(dump_flags & DUMP_BEFORE) {
+	if (dump_flags & DUMP_BEFORE) {
 		ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_before.dot", co->irg, co->cls->name);
-		if(f = fopen(buf, "wt")) {
+		f = fopen(buf, "wt");
+		if (f != NULL) {
 			be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
 			fclose(f);
 		}
@@ -1497,9 +1251,10 @@ void co_solve_heuristic_new(copy_opt_t *co)
 
 	process(&env);
 
-	if(dump_flags & DUMP_AFTER) {
+	if (dump_flags & DUMP_AFTER) {
 		ir_snprintf(buf, sizeof(buf), "ifg_%F_%s_after.dot", co->irg, co->cls->name);
-		if(f = fopen(buf, "wt")) {
+		f = fopen(buf, "wt");
+		if (f != NULL) {
 			be_ifg_dump_dot(co->cenv->ifg, co->irg, f, &ifg_dot_cb, &env);
 			fclose(f);
 		}
@@ -1507,4 +1262,22 @@ void co_solve_heuristic_new(copy_opt_t *co)
 
 	writeback_colors(&env);
 	phase_free(&env.ph);
+	return 0;
 }
+
+void be_init_copyheur2(void)
+{
+	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
+	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
+	lc_opt_entry_t *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
+
+	static co_algo_info copyheur = {
+		co_solve_heuristic_new, 0
+	};
+
+	lc_opt_add_table(co2_grp, options);
+	be_register_copyopt("heur2", &copyheur);
+}
+
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);