X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt.c;h=818bbf0910a055261becd5b6dda2c0af600c37c4;hb=65f6cc39305e6880fe45709a8a2e1c24445395e3;hp=582c4e2cf1324495eacd271437f0f55ab7072324;hpb=0c92b911be3d9d02b4a49b2a142dab8d7ba978a6;p=libfirm

diff --git a/ir/be/becopyopt.c b/ir/be/becopyopt.c
index 582c4e2cf..818bbf091 100644
--- a/ir/be/becopyopt.c
+++ b/ir/be/becopyopt.c
@@ -1,23 +1,44 @@
+/*
+ * 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.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
 /**
- * Author:      Daniel Grund
- * Date:		12.04.2005
- * Copyright:   (c) Universitaet Karlsruhe
- * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ * @file
+ * @brief       Copy minimization driver.
+ * @author      Daniel Grund
+ * @date        12.04.2005
+ * @version     $Id$
+ *
+ * Main file for the optimization reducing the copies needed for:
+ * - Phi coalescing
+ * - Register-constrained nodes
+ * - Two-address code instructions
  */
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
-#ifdef HAVE_MALLOC_H
-#include <malloc.h>
-#endif
 
 #include "execfreq.h"
 #include "xmalloc.h"
 #include "debug.h"
 #include "pmap.h"
+#include "raw_bitset.h"
+#include "irnode.h"
 #include "irgraph.h"
 #include "irgwalk.h"
 #include "irprog.h"
@@ -28,11 +49,12 @@
 #include "irphase_t.h"
 #include "irprintf_t.h"
 
-
-#include "bearch.h"
+#include "bemodule.h"
+#include "bearch_t.h"
 #include "benode_t.h"
 #include "beutil.h"
 #include "beifg_t.h"
+#include "beintlive_t.h"
 #include "becopyopt_t.h"
 #include "becopystat.h"
 #include "belive_t.h"
@@ -41,11 +63,12 @@
 #include "benodesets.h"
 #include "bejavacoal.h"
 #include "bestatevent.h"
+#include "beirg_t.h"
+#include "error.h"
 
-#ifdef WITH_LIBCORE
 #include <libcore/lc_timing.h>
 #include <libcore/lc_opts.h>
-#endif /* WITH_LIBCORE */
+#include <libcore/lc_opts_enum.h>
 
 #define DUMP_BEFORE 1
 #define DUMP_AFTER  2
@@ -56,14 +79,13 @@
 #define COST_FUNC_LOOP     2
 #define COST_FUNC_ALL_ONE  3
 
-static unsigned dump_flags    = 0;
-static unsigned style_flags   = 0;
-static unsigned  do_stats     = 0;
+static unsigned   dump_flags  = 0;
+static unsigned   style_flags = 0;
+static unsigned   do_stats    = 0;
 static cost_fct_t cost_func   = co_get_costs_exec_freq;
-static unsigned algo          = CO_ALGO_HEUR2;
-static int improve            = 1;
+static unsigned   algo        = CO_ALGO_HEUR4;
+static int        improve     = 1;
 
-#ifdef WITH_LIBCORE
 static const lc_opt_enum_mask_items_t dump_items[] = {
 	{ "before",  DUMP_BEFORE },
 	{ "after",   DUMP_AFTER  },
@@ -88,6 +110,7 @@ static const lc_opt_enum_mask_items_t algo_items[] = {
 #ifdef WITH_JVM
 	{ "heur3",  CO_ALGO_HEUR3 },
 #endif /* WITH_JVM */
+	{ "heur4",  CO_ALGO_HEUR4 },
 #ifdef WITH_ILP
 	{ "ilp",    CO_ALGO_ILP   },
 #endif /* WITH_ILP */
@@ -126,7 +149,7 @@ static const lc_opt_table_entry_t options[] = {
 	LC_OPT_ENT_ENUM_MASK     ("style",   "dump style for ifg dumping",                              &style_var),
 	LC_OPT_ENT_BOOL          ("stats",   "dump statistics after each optimization",                 &do_stats),
 	LC_OPT_ENT_BOOL          ("improve", "run heur3 before if algo can exploit start solutions",    &improve),
-	{ NULL }
+	LC_OPT_LAST
 };
 
 /* Insert additional options registration functions here. */
@@ -134,22 +157,29 @@ extern void be_co_ilp_register_options(lc_opt_entry_t *grp);
 extern void be_co2_register_options(lc_opt_entry_t *grp);
 extern void be_co3_register_options(lc_opt_entry_t *grp);
 
-void co_register_options(lc_opt_entry_t *grp)
+void be_init_copycoal(void)
 {
-	lc_opt_entry_t *co_grp = lc_opt_get_grp(grp, "co");
-	lc_opt_add_table(co_grp, options);
+	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 *co_grp = lc_opt_get_grp(chordal_grp, "co");
 
-	be_co2_register_options(co_grp);
-	be_co3_register_options(co_grp);
-#ifdef WITH_ILP
-	be_co_ilp_register_options(co_grp);
-#endif
+	lc_opt_add_table(co_grp, options);
 }
-#endif
 
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copycoal);
 
 #undef QUICK_AND_DIRTY_HACK
 
+static int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
+{
+	if (env->ifg)
+		return be_ifg_connected(env->ifg, a, b);
+	else
+		return values_interfere(env->birg, a, b);
+}
+
+
 /******************************************************************************
     _____                           _
    / ____|                         | |
@@ -163,9 +193,6 @@ void co_register_options(lc_opt_entry_t *grp)
 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
 
-void be_copy_opt_init(void) {
-}
-
 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
 {
 	const char *s1, *s2, *s3;
@@ -197,7 +224,7 @@ void free_copy_opt(copy_opt_t *co) {
 }
 
 int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
-	arch_register_req_t req;
+	const arch_register_req_t *req;
 	const arch_register_t *reg;
 
 	if (arch_irn_is(co->aenv, irn, ignore))
@@ -207,47 +234,19 @@ int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
 	if (arch_register_type_is(reg, ignore))
 		return 0;
 
-	if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(co->aenv, irn, &req))
+	req = arch_get_register_req(co->aenv, irn, -1);
+	if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(req))
 		return 1;
 
 	return 0;
 }
 
-int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn) {
-	const ir_edge_t *edge;
-	const arch_register_t *reg;
-
-	assert(0 && "Is buggy and obsolete. Do not use");
-
-	if (arch_irn_is(co->aenv, irn, ignore))
-		return 0;
-
-	reg = arch_get_irn_register(co->aenv, irn);
-	if (arch_register_type_is(reg, ignore))
-		return 0;
-
-	foreach_out_edge(irn, edge) {
-		ir_node *n = edge->src;
-
-		if (!nodes_interfere(co->cenv, irn, n) || irn == n) {
-			arch_register_req_t req;
-			arch_get_register_req(co->aenv, &req, n, -1);
-
-			if(is_Reg_Phi(n) ||
-			   is_Perm(co->aenv, n) ||
-			   (arch_register_req_is(&req, should_be_same) && req.other_same == irn)
-			  )
-				return 1;
-		}
-	}
-
-	return 0;
-}
-
 int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos) {
 	int cost = 0;
 	ir_loop *loop;
 	ir_node *root_block = get_nodes_block(root);
+	(void) co;
+	(void) arg;
 
 	if (is_Phi(root)) {
 		/* for phis the copies are placed in the corresponding pred-block */
@@ -267,6 +266,7 @@ int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, in
 	int res;
 	ir_node *root_bl = get_nodes_block(root);
 	ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
+	(void) arg;
 	res = get_block_execfreq_ulong(co->cenv->birg->exec_freq, copy_bl);
 
 	/* don't allow values smaller than one. */
@@ -275,6 +275,10 @@ int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, in
 
 
 int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node *arg, int pos) {
+	(void) co;
+	(void) root;
+	(void) arg;
+	(void) pos;
 	return 1;
 }
 
@@ -298,7 +302,8 @@ static int ou_max_ind_set_costs(unit_t *ou) {
 	ir_node **safe, **unsafe;
 	int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
 	bitset_t *curr;
-	int max, pos, curr_weight, best_weight = 0;
+	bitset_pos_t pos;
+	int max, curr_weight, best_weight = 0;
 
 	/* assign the nodes into two groups.
 	 * safe: node has no interference, hence it is in every max stable set.
@@ -379,7 +384,6 @@ static int ou_max_ind_set_costs(unit_t *ou) {
 static void co_collect_units(ir_node *irn, void *env) {
 	copy_opt_t *co = env;
 	unit_t *unit;
-	arch_register_req_t req;
 
 	if (!is_curr_reg_class(co, irn))
 		return;
@@ -418,30 +422,31 @@ static void co_collect_units(ir_node *irn, void *env) {
 			/* Else insert the argument of the phi to the members of this ou */
 			DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
 
-			/* Check if arg has occurred at a prior position in the arg/list */
-			arg_pos = 0;
-			for (o=0; o<unit->node_count; ++o)
-				if (unit->nodes[o] == arg) {
-					arg_pos = o;
-					break;
+			if (! arch_irn_is(co->aenv, arg, ignore)) {
+				/* Check if arg has occurred at a prior position in the arg/list */
+				arg_pos = 0;
+				for (o=1; o<unit->node_count; ++o) {
+					if (unit->nodes[o] == arg) {
+						arg_pos = o;
+						break;
+					}
 				}
 
-			if (!arg_pos) { /* a new argument */
-				/* insert node, set costs */
-				unit->nodes[unit->node_count] = arg;
-				unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
-				unit->node_count++;
-			} else { /* arg has occured before in same phi */
-				/* increase costs for existing arg */
-				unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
+				if (!arg_pos) { /* a new argument */
+					/* insert node, set costs */
+					unit->nodes[unit->node_count] = arg;
+					unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
+					unit->node_count++;
+				} else { /* arg has occurred before in same phi */
+					/* increase costs for existing arg */
+					unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
+				}
 			}
 		}
 		unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
 		unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
-	} else
-
-	/* Proj of a perm with corresponding arg */
-	if (is_Perm_Proj(co->aenv, irn)) {
+	} else if (is_Perm_Proj(co->aenv, irn)) {
+		/* Proj of a perm with corresponding arg */
 		assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
 		unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
 		unit->costs = xmalloc(2 * sizeof(*unit->costs));
@@ -449,21 +454,55 @@ static void co_collect_units(ir_node *irn, void *env) {
 		unit->nodes[0] = irn;
 		unit->nodes[1] = get_Perm_src(irn);
 		unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
-	} else
-
-	/* Src == Tgt of a 2-addr-code instruction */
-	if (is_2addr_code(co->aenv, irn, &req)) {
-		ir_node *other = req.other_same;
-		if (!nodes_interfere(co->cenv, irn, other)) {
-			unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
-			unit->costs = xmalloc(2 * sizeof(*unit->costs));
-			unit->node_count = 2;
-			unit->nodes[0] = irn;
-			unit->nodes[1] = other;
-			unit->costs[1] = co->get_costs(co, irn, other, -1);
+	} else {
+		const arch_register_req_t *req =
+			arch_get_register_req(co->aenv, irn, -1);
+
+		/* Src == Tgt of a 2-addr-code instruction */
+		if (is_2addr_code(req)) {
+			ir_node *other  = get_irn_n(skip_Proj(irn), req->other_same[0]);
+			ir_node *other2 = NULL;
+			int      count;
+
+			if (arch_irn_is(co->aenv, other, ignore) ||
+					nodes_interfere(co->cenv, irn, other)) {
+				other = NULL;
+			}
+			if (req->other_same[1] != -1) {
+				other2 = get_irn_n(skip_Proj(irn), req->other_same[1]);
+				if (arch_irn_is(co->aenv, other2, ignore) ||
+						nodes_interfere(co->cenv, irn, other2)) {
+					other2 = NULL;
+				}
+			}
+			count = 1 + (other != NULL) + (other2 != NULL && other != other2);
+
+			if (count > 1) {
+				int i = 0;
+
+				unit->nodes = xmalloc(count * sizeof(*unit->nodes));
+				unit->costs = xmalloc(count * sizeof(*unit->costs));
+				unit->node_count = count;
+				unit->nodes[i] = irn;
+				if (other != NULL) {
+					++i;
+					unit->nodes[i] = other;
+					unit->costs[i] = co->get_costs(co, irn, other, -1);
+				}
+				if (other2 != NULL) {
+					if (other == other2) {
+						unit->costs[i] += co->get_costs(co, irn, other2, -1);
+					} else {
+						++i;
+						unit->nodes[i] = other2;
+						unit->costs[i] = co->get_costs(co, irn, other2, -1);
+					}
+				}
+			}
+		} else {
+			assert(0 && "This is not an optimizable node!");
 		}
-	} else
-		assert(0 && "This is not an optimizable node!");
+	}
 
 	/* Insert the new unit at a position according to its costs */
 	if (unit->node_count > 1) {
@@ -698,21 +737,21 @@ void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
 static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
 	const affinity_node_t *n1 = k1;
 	const affinity_node_t *n2 = k2;
+	(void) size;
 
 	return (n1->irn != n2->irn);
 }
 
 static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 	affinity_node_t new_node, *node;
-	neighb_t new_nbr, *nbr;
-	int allocnew;
+	neighb_t        *nbr;
+	int             allocnew = 1;
 
 	new_node.irn        = n1;
 	new_node.degree     = 0;
 	new_node.neighbours = NULL;
 	node = set_insert(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn));
 
-	allocnew = 1;
 	for (nbr = node->neighbours; nbr; nbr = nbr->next)
 		if (nbr->irn == n2) {
 			allocnew = 0;
@@ -721,11 +760,11 @@ static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
 
 	/* if we did not find n2 in n1's neighbourhood insert it */
 	if (allocnew) {
-		obstack_grow(&co->obst, &new_nbr, sizeof(new_nbr));
-		nbr = obstack_finish(&co->obst);
+		nbr        = obstack_alloc(&co->obst, sizeof(*nbr));
 		nbr->irn   = n2;
 		nbr->costs = 0;
 		nbr->next  = node->neighbours;
+
 		node->neighbours = nbr;
 		node->degree++;
 	}
@@ -744,7 +783,6 @@ static INLINE void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs
 static void build_graph_walker(ir_node *irn, void *env) {
 	copy_opt_t *co = env;
 	int pos, max;
-	arch_register_req_t req;
 	const arch_register_t *reg;
 
 	if (!is_curr_reg_class(co, irn) || arch_irn_is(co->aenv, irn, ignore))
@@ -754,22 +792,31 @@ static void build_graph_walker(ir_node *irn, void *env) {
 	if (arch_register_type_is(reg, ignore))
 		return;
 
-	/* Phis */
-	if (is_Reg_Phi(irn))
+	if (is_Reg_Phi(irn)) { /* Phis */
 		for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
 			ir_node *arg = get_irn_n(irn, pos);
 			add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
 		}
-
-	/* Perms */
-	else if (is_Perm_Proj(co->aenv, irn)) {
+	}
+	else if (is_Perm_Proj(co->aenv, irn)) { /* Perms */
 		ir_node *arg = get_Perm_src(irn);
 		add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
 	}
-
-	/* 2-address code */
-	else if (is_2addr_code(co->aenv, irn, &req))
-		add_edges(co, irn, req.other_same, co->get_costs(co, irn, req.other_same, 0));
+	else { /* 2-address code */
+		const arch_register_req_t *req = arch_get_register_req(co->aenv, irn, -1);
+		if (is_2addr_code(req)) {
+			const int *i;
+			for (i = req->other_same; i != ENDOF(req->other_same); ++i) {
+				ir_node *other;
+
+				if (*i == -1) break;
+
+				other = get_irn_n(skip_Proj(irn), *i);
+				if (! arch_irn_is(co->aenv, other, ignore))
+					add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
+			}
+		}
+	}
 }
 
 void co_build_graph_structure(copy_opt_t *co) {
@@ -806,7 +853,6 @@ void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 {
 	be_ifg_t *ifg  = co->cenv->ifg;
 	int *color_map = alloca(co->cls->n_regs * sizeof(color_map[0]));
-	bitset_t *adm  = bitset_alloca(co->cls->n_regs);
 
 	ir_node *irn;
 	void *it, *nit;
@@ -839,17 +885,15 @@ void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 			int idx            = PTR_TO_INT(get_irn_link(irn));
 			affinity_node_t *a = get_affinity_info(co, irn);
 
-			arch_register_req_t req;
+			const arch_register_req_t *req;
 			ir_node *adj;
 
-			arch_get_register_req(co->aenv, &req, irn, BE_OUT_POS(0));
-			if(arch_register_req_is(&req, limited)) {
-				bitset_clear_all(adm);
-				req.limited(req.limited_env, adm);
-				for(i = 0; i < co->cls->n_regs; ++i)
-					if(!bitset_is_set(adm, i) && color_map[i] >= 0)
+			req = arch_get_register_req(co->aenv, irn, BE_OUT_POS(0));
+			if(arch_register_req_is(req, limited)) {
+				for(i = 0; i < co->cls->n_regs; ++i) {
+					if(!rbitset_is_set(req->limited, i) && color_map[i] >= 0)
 						fprintf(f, "%d %d -1\n", color_map[i], idx);
-
+				}
 			}
 
 
@@ -877,7 +921,7 @@ void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
 }
 
 typedef struct _appel_clique_walker_t {
-	phase_t ph;
+	ir_phase ph;
 	const copy_opt_t *co;
 	int curr_nr;
 	int node_count;
@@ -907,6 +951,7 @@ static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
 	return res == 0 ? 1 : res;
 #else
 	ir_loop *loop = get_irn_loop(bl);
+	(void) env;
 	if(loop) {
 		int d = get_loop_depth(loop);
 		return 1 + d * d;
@@ -915,9 +960,10 @@ static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
 #endif
 }
 
-static void *appel_clique_walker_irn_init(phase_t *phase, ir_node *irn, void *old)
+static void *appel_clique_walker_irn_init(ir_phase *phase, ir_node *irn, void *old)
 {
 	appel_block_info_t *res = NULL;
+	(void) old;
 
 	if(is_Block(irn)) {
 		appel_clique_walker_t *d = (void *) phase;
@@ -950,15 +996,16 @@ static int appel_get_live_end_nr(appel_clique_walker_t *env, ir_node *bl, ir_nod
 	return -1;
 }
 
-static int appel_dump_clique(appel_clique_walker_t *env, pset *live, ir_node *bl, int curr_nr, int start_nr)
+static int appel_dump_clique(appel_clique_walker_t *env, const ir_nodeset_t *live, ir_node *bl, int curr_nr, int start_nr)
 {
 	ir_node **live_arr = alloca(env->co->cls->n_regs * sizeof(live_arr[0]));
 	ir_node *irn;
 	int n_live;
 	int j;
+	ir_nodeset_iterator_t iter;
 
 	n_live = 0;
-	foreach_pset(live, irn)
+	foreach_ir_nodeset(live, irn, iter)
 		live_arr[n_live++] = irn;
 
 	/* dump the live after clique */
@@ -1000,7 +1047,8 @@ static void appel_walker(ir_node *bl, void *data)
 	appel_block_info_t *bli    = phase_get_or_set_irn_data(&env->ph, bl);
 	struct obstack *obst       = &env->obst;
 	void *base                 = obstack_base(obst);
-	pset *live                 = pset_new_ptr_default();
+	ir_nodeset_t live;
+	ir_nodeset_iterator_t iter;
 	be_lv_t *lv                = env->co->cenv->birg->lv;
 
 	int n_insns  = 0;
@@ -1023,7 +1071,7 @@ static void appel_walker(ir_node *bl, void *data)
 		n_nodes++;
 
 	bli->n_phi = 0;
-	insns = malloc(n_nodes * sizeof(insns[0]));
+	insns = xmalloc(n_nodes * sizeof(insns[0]));
 
 	/* Put all insns in an array. */
 	irn = sched_first(bl);
@@ -1034,8 +1082,9 @@ static void appel_walker(ir_node *bl, void *data)
 		irn = insn->next_insn;
 	}
 
-	DBG((env->co->cenv->dbg, LEVEL_2, "%+F\n", bl));
-	be_liveness_end_of_block(lv, env->co->aenv, env->co->cls, bl, live);
+	DBG((dbg, LEVEL_2, "%+F\n", bl));
+	ir_nodeset_init(&live);
+	be_liveness_end_of_block(lv, env->co->aenv, env->co->cls, bl, &live);
 
 	/* Generate the bad and ugly. */
 	for(i = n_insns - 1; i >= 0; --i) {
@@ -1044,7 +1093,7 @@ static void appel_walker(ir_node *bl, void *data)
 		/* The first live set has to be saved in the block border set. */
 		if(i == n_insns - 1) {
 			j = 0;
-			foreach_pset(live, irn) {
+			foreach_ir_nodeset(&live, irn, iter) {
 				bli->live_end[j]    = irn;
 				bli->live_end_nr[j] = curr_nr + j;
 				++j;
@@ -1057,21 +1106,20 @@ static void appel_walker(ir_node *bl, void *data)
 				ir_node *op   = insn->ops[j].carrier;
 				bitset_t *adm = insn->ops[j].regs;
 				int k;
-				int nr;
+				size_t nr;
 
 				if(!insn->ops[j].has_constraints)
 					continue;
 
 				nr = 0;
-				foreach_pset(live, irn) {
+				foreach_ir_nodeset(&live, irn, iter) {
 					if(irn == op) {
-						pset_break(live);
 						break;
 					}
 					++nr;
 				}
 
-				assert(nr < pset_count(live));
+				assert(nr < ir_nodeset_size(&live));
 
 				for(k = 0; k < env->co->cls->n_regs; ++k) {
 					int mapped_col = env->color_map[k];
@@ -1082,11 +1130,11 @@ static void appel_walker(ir_node *bl, void *data)
 		}
 
 		/* dump the clique and update the stuff. */
-		curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
+		curr_nr = appel_dump_clique(env, &live, bl, curr_nr, start_nr);
 
 		/* remove all defs. */
 		for(j = 0; j < insn->use_start; ++j)
-			pset_remove_ptr(live, insn->ops[j].carrier);
+			ir_nodeset_remove(&live, insn->ops[j].carrier);
 
 		if(is_Phi(insn->irn) && arch_irn_consider_in_reg_alloc(env->co->aenv, env->co->cls, insn->irn)) {
 			bli->phi[bli->n_phi]    = insn->irn;
@@ -1097,21 +1145,21 @@ static void appel_walker(ir_node *bl, void *data)
 		/* add all uses */
 		else
 			for(j = insn->use_start; j < insn->n_ops; ++j)
-				pset_insert_ptr(live, insn->ops[j].carrier);
+				ir_nodeset_insert(&live, insn->ops[j].carrier);
 	}
 
 	/* print the start clique. */
-	curr_nr = appel_dump_clique(env, live, bl, curr_nr, start_nr);
+	curr_nr = appel_dump_clique(env, &live, bl, curr_nr, start_nr);
 
 	i = 0;
-	foreach_pset(live, irn) {
+	foreach_ir_nodeset(&live, irn, iter) {
 		bli->live_in[i]    = irn;
 		bli->live_in_nr[i] = PTR_TO_INT(get_irn_link(irn));
 		++i;
 	}
 	bli->n_live_in = i;
 
-	del_pset(live);
+	ir_nodeset_destroy(&live);
 	free(insns);
 	obstack_free(obst, base);
 	env->curr_nr = curr_nr;
@@ -1161,7 +1209,7 @@ void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f)
 
 	be_liveness_recompute(lv);
 	obstack_init(&env.obst);
-	phase_init(&env.ph, "appel_clique_dumper", co->irg, PHASE_DEFAULT_GROWTH, appel_clique_walker_irn_init);
+	phase_init(&env.ph, "appel_clique_dumper", co->irg, PHASE_DEFAULT_GROWTH, appel_clique_walker_irn_init, NULL);
 	env.curr_nr = co->cls->n_regs;
 	env.co = co;
 	env.f = f;
@@ -1208,7 +1256,7 @@ void co_dump_appel_graph_cliques(const copy_opt_t *co, FILE *f)
 	                                                          |_|            |___/
 */
 
-static const char *get_dot_color_name(int col)
+static const char *get_dot_color_name(size_t col)
 {
 	static const char *names[] = {
 		"blue",
@@ -1254,6 +1302,7 @@ typedef struct _co_ifg_dump_t {
 
 static void ifg_dump_graph_attr(FILE *f, void *self)
 {
+	(void) self;
 	fprintf(f, "overlap=scale");
 }
 
@@ -1267,25 +1316,27 @@ static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
 {
 	co_ifg_dump_t *env         = self;
 	const arch_register_t *reg = arch_get_irn_register(env->co->aenv, irn);
-	arch_register_req_t req;
+	const arch_register_req_t *req;
 	int limited;
 
-	arch_get_register_req(env->co->aenv, &req, irn, BE_OUT_POS(0));
-	limited = arch_register_req_is(&req, limited);
+	req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
+	limited = arch_register_req_is(req, limited);
 
 	if(env->flags & CO_IFG_DUMP_LABELS) {
 		ir_fprintf(f, "label=\"%+F", irn);
 
+#if 0
+		// TODO fix this...
 		if((env->flags & CO_IFG_DUMP_CONSTR) && limited) {
 			bitset_t *bs = bitset_alloca(env->co->cls->n_regs);
 			req.limited(req.limited_env, bs);
 			ir_fprintf(f, "\\n%B", bs);
 		}
+#endif
 		ir_fprintf(f, "\" ");
-	}
-
-	else
+	} else {
 		fprintf(f, "label=\"\" shape=point " );
+	}
 
 	if(env->flags & CO_IFG_DUMP_SHAPE)
 		fprintf(f, "shape=%s ", limited ? "diamond" : "ellipse");
@@ -1347,11 +1398,12 @@ void co_dump_ifg_dot(const copy_opt_t *co, FILE *f, unsigned flags)
 
 void co_solve_park_moon(copy_opt_t *opt)
 {
-
+	(void) opt;
 }
 
 static int void_algo(copy_opt_t *co)
 {
+	(void) co;
 	return 0;
 }
 
@@ -1365,20 +1417,21 @@ static int void_algo(copy_opt_t *co)
 */
 
 typedef struct {
-	co_algo_t *algo;
+	co_algo_t  *algo;
 	const char *name;
-	int can_improve_existing;
+	int        can_improve_existing;
 } co_algo_info_t;
 
 static co_algo_info_t algos[] = {
-	{ void_algo,                "none",  0 },
-	{ co_solve_heuristic,       "heur1", 0 },
-	{ co_solve_heuristic_new,   "heur2", 0 },
-	{ co_solve_heuristic_java,  "heur3", 0 },
+	{ void_algo,               "none",  0 },
+	{ co_solve_heuristic,      "heur1", 0 },
+	{ co_solve_heuristic_new,  "heur2", 0 },
+	{ co_solve_heuristic_java, "heur3", 0 },
+	{ co_solve_heuristic_mst,  "heur4", 0 },
 #ifdef WITH_ILP
-	{ co_solve_ilp2,            "ilp",   1 },
+	{ co_solve_ilp2,           "ilp",   1 },
 #endif
-	{ NULL,                     "",      0 }
+	{ NULL,                    "",      0 }
 };
 
 /*
@@ -1390,19 +1443,33 @@ static co_algo_info_t algos[] = {
 
 */
 
+static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
+{
+	FILE *result;
+	char buf[1024];
+
+	ir_snprintf(buf, sizeof(buf), "%s%F_%s%s", prefix, env->irg, env->cls->name, suffix);
+	result = fopen(buf, "wt");
+	if(result == NULL) {
+		panic("Couldn't open '%s' for writing.", buf);
+	}
+
+	return result;
+}
+
 void co_driver(be_chordal_env_t *cenv)
 {
-#ifdef WITH_LIBCORE
-	lc_timer_t *timer = lc_timer_register("firm.be.copyopt", "runtime");
-#endif
+	lc_timer_t          *timer = lc_timer_register("firm.be.copyopt", "runtime");
 	co_complete_stats_t before, after;
-	copy_opt_t *co;
-	co_algo_t  *algo_func;
-	int was_optimal = 0;
+	copy_opt_t          *co;
+	co_algo_t           *algo_func;
+	int                 was_optimal = 0;
 
-	if(algo < 0 || algo >= CO_ALGO_LAST)
+	if (algo >= CO_ALGO_LAST)
 		return;
 
+	be_liveness_assure_chk(be_get_birg_liveness(cenv->birg));
+
 	co = new_copy_opt(cenv, cost_func);
 	co_build_ou_structure(co);
 	co_build_graph_structure(co);
@@ -1419,24 +1486,28 @@ void co_driver(be_chordal_env_t *cenv)
 	be_stat_ev_ull("co_init_unsat",   before.unsatisfied_edges);
 
 	/* Dump the interference graph in Appel's format. */
-	if(dump_flags & DUMP_APPEL) {
-		FILE *f = be_chordal_open(cenv, "", ".apl");
+	if (dump_flags & DUMP_APPEL) {
+		FILE *f = my_open(cenv, "", ".apl");
 		co_dump_appel_graph(co, f);
 		fclose(f);
 	}
 
-	if(dump_flags & DUMP_BEFORE) {
-		FILE *f = be_chordal_open(cenv, "", "-before.dot");
+	if (dump_flags & DUMP_BEFORE) {
+		FILE *f = my_open(cenv, "", "-before.dot");
 		co_dump_ifg_dot(co, f, style_flags);
 		fclose(f);
 	}
 
 	/* if the algo can improve results, provide an initial solution with heur3 */
-	if(improve && algos[algo].can_improve_existing) {
+	if (improve && algos[algo].can_improve_existing) {
 		co_complete_stats_t stats;
 
-		/* produce a heuristical solution */
+		/* produce a heuristic solution */
+#ifdef WITH_JVM
 		co_solve_heuristic_java(co);
+#else
+		co_solve_heuristic(co);
+#endif /* WITH_JVM */
 
 		/* do the stats and provide the current costs */
 		co_complete_stats(co, &stats);
@@ -1445,34 +1516,29 @@ void co_driver(be_chordal_env_t *cenv)
 
 #ifdef WITH_JVM
 	/* start the JVM here so that it does not tamper the timing. */
-	if(algo == CO_ALGO_HEUR3)
+	if (algo == CO_ALGO_HEUR3)
 		be_java_coal_start_jvm();
-#endif
+#endif /* WITH_JVM */
 
 	algo_func = algos[algo].algo;
 
-#ifdef WITH_LIBCORE
+	/* perform actual copy minimization */
 	lc_timer_reset_and_start(timer);
-#endif
-
 	was_optimal = algo_func(co);
-
-#ifdef WITH_LIBCORE
 	lc_timer_stop(timer);
-	be_stat_ev("co_time", lc_timer_elapsed_msec(timer));
-#endif
 
+	be_stat_ev("co_time", lc_timer_elapsed_msec(timer));
 	be_stat_ev_ull("co_optimal", was_optimal);
 
-	if(dump_flags & DUMP_AFTER) {
-		FILE *f = be_chordal_open(cenv, "", "-after.dot");
+	if (dump_flags & DUMP_AFTER) {
+		FILE *f = my_open(cenv, "", "-after.dot");
 		co_dump_ifg_dot(co, f, style_flags);
 		fclose(f);
 	}
 
 	co_complete_stats(co, &after);
 
-	if(do_stats) {
+	if (do_stats) {
 		ulong64 optimizable_costs = after.max_costs - after.inevit_costs;
 		ulong64 evitable          = after.costs     - after.inevit_costs;