X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=09cc2908bcff0bfece887a5cb09b84528351351e;hb=80a6158fdd766f42ee6c508a773bc114ff1b61f3;hp=ed0594091f30dbf192ecb6f549723f75bc013e1f;hpb=0c9b227b0f3dd1753e96ffa30be78fb064586631;p=libfirm

diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c
index ed0594091..09cc2908b 100644
--- a/ir/be/beraextern.c
+++ b/ir/be/beraextern.c
@@ -6,9 +6,11 @@
  *
  * Implementation of the RA-Interface for an external, (non-SSA) register allocator.
  *
- * The external register allocator is a program taking 2 arguments:
- *   1) An input file in which the cfg is defined
- *   2) An output file containing the essential actions performed during allocation
+ * The external register allocator is a program:
+ *    PROG -i INPUTFILE -o OUTPUTFILE
+ *
+ *   1) Input file defines the interference graph
+ *   2) Output file contains the instructions to perform
  *
 
 
@@ -26,15 +28,17 @@ node		::= node-info
 
 node-info	::= node-nr spill-costs .
 
-interf		::= 'interferences' '{' edge* '}' .			// Interference edges of the graph
+interf		::= 'interferences' '{' i-edge* '}' .		// Interference edges of the graph
 
-affinities	::= 'affinities' '{' edge* '}' .			// Affinity edges of the graph
+i-edge		::= '(' node-nr ',' node-nr ')' .
 
-edge		::= '(' node-nr ',' node-nr ')' .
+affinities	::= 'affinities' '{' a-edge* '}' .			// Affinity edges of the graph
 
+a-edge		::= '(' node-nr ',' node-nr ',' weight ')' .
 
-spill-costs, regcount, node-nr ::= integer .
 
+weight, regcount, node-nr ::= int32 .
+spill-costs ::= int32 .									// negative spill costs indicate unspillable
 
 The output file format
 -----------------------
@@ -54,14 +58,16 @@ alloc		::= node-nr reg-nr .
 #include "config.h"
 #endif
 
-#ifdef WIN32
-#include <malloc.h>
-#else
-#include <alloca.h>
+#ifdef HAVE_MALLOC_H
+ #include <malloc.h>
+#endif
+#ifdef HAVE_ALLOCA_H
+ #include <alloca.h>
 #endif
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <limits.h>
 #ifdef WITH_LIBCORE
 #include <libcore/lc_opts.h>
 #include <libcore/lc_opts_enum.h>
@@ -80,14 +86,20 @@ alloc		::= node-nr reg-nr .
 #include "irdom_t.h"
 #include "phiclass.h"
 
+#include "bemodule.h"
 #include "beraextern.h"
+#include "beabi.h"
 #include "bearch.h"
 #include "benode_t.h"
 #include "beirgmod.h"
-#include "besched.h"
+#include "besched_t.h"
 #include "beutil.h"
+#include "belive_t.h"
+#include "beinsn_t.h"
+
+#include "bessadestrsimple.h"
 
-typedef struct _var_info_t var_info_t;
+#define DBG_LEVEL 2
 
 /**
  * Environment with all the needed stuff
@@ -95,13 +107,14 @@ typedef struct _var_info_t var_info_t;
 typedef struct _be_raext_env_t {
 	arch_env_t *aenv;
 	const arch_register_class_t *cls;
+	be_irg_t *birg;
 	ir_graph *irg;
-	dom_front_info_t *dom_info;
 
 	FILE *f;				/**< file handle used for out- and input file */
-	set *vars;				/**< contains all var_info_t */
+	set *vars;				/**< contains all be_var_info_t */
 	int n_cls_vars;			/**< length of the array cls_vars */
-	var_info_t **cls_vars;	/**< only the var_infos for current cls. needed for double iterating */
+	be_var_info_t **cls_vars;	/**< only the var_infos for current cls. needed for double iterating */
+	DEBUG_ONLY(firm_dbg_module_t *dbg;)
 } be_raext_env_t;
 
 
@@ -154,6 +167,23 @@ static INLINE ir_node *get_first_phi(pset *s) {
 	return NULL;
 }
 
+static int get_loop_weight(ir_node *irn) {
+	int cost = 0;
+	ir_loop *loop = get_irn_loop(get_nodes_block(irn));
+
+	if (loop) {
+		int d = get_loop_depth(loop);
+		cost = d*d;
+	}
+	return cost+1;
+}
+
+#define get_const_weight(irn) (1)
+
+#define get_spill_weight(irn)    get_loop_weight(irn)
+#define get_reload_weight(irn)   get_loop_weight(irn)
+#define get_affinity_weight(irn) get_loop_weight(irn)
+
 /******************************************************************************
     _____                _            _____            _
    / ____|              | |          / ____|          (_)
@@ -165,286 +195,68 @@ static INLINE ir_node *get_first_phi(pset *s) {
                                                 |_|
  *****************************************************************************/
 
-static void handle_constraints_walker(ir_node *irn, void *env) {
-	be_raext_env_t *raenv = env;
-	arch_register_req_t req;
-	int pos, max;
-
-	/* handle output constraints
-	 * user -> irn    becomes    user -> cpy -> irn
-	 */
-	arch_get_register_req(raenv->aenv, &req, irn, -1);
-	if (arch_register_req_is(&req, limited)) {
-		ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), irn);
-		const ir_edge_t *edge;
-
-		/* all users of the irn use the copy instead */
-		sched_add_after(irn, cpy);
-		foreach_out_edge(irn, edge)
-			set_irn_n(edge->src, edge->pos, cpy);
-	}
-
-
-	/* handle input constraints by converting them into output constraints
-	 * of copies of the former argument
-	 * irn -> arg   becomes  irn -> copy -> arg
-     */
-	for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
-		arch_get_register_req(raenv->aenv, &req, irn, pos);
-		if (arch_register_req_is(&req, limited)) {
-			ir_node *arg = get_irn_n(irn, pos);
-			ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), arg);
+static void handle_constraints_insn(be_raext_env_t *env, be_insn_t *insn)
+{
+	ir_node *bl = get_nodes_block(insn->irn);
+	int i;
 
-			/* use the copy instead */
-			sched_add_before(irn, cpy);
-			set_irn_n(irn, pos, cpy);
+	for(i = 0; i < insn->use_start; ++i) {
+		be_operand_t *op = &insn->ops[i];
 
-			/* set an out constraint for the copy */
-			arch_set_register_req(raenv->aenv, -1, &req);
+		if(op->has_constraints) {
+			ir_node *cpy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
+			sched_add_before(insn->next_insn, cpy);
+			edges_reroute(op->carrier, cpy, env->irg);
 		}
 	}
-}
-
-static void handle_constraints(be_raext_env_t *raenv) {
-	irg_block_walk_graph(raenv->irg, NULL, handle_constraints_walker, raenv);
-}
 
+	for(i = insn->use_start; i < insn->n_ops; ++i) {
+		be_operand_t *op = &insn->ops[i];
 
-/******************************************************************************
-     _____ _____              _____            _
-    / ____/ ____|  /\        |  __ \          | |
-   | (___| (___   /  \ ______| |  | | ___  ___| |_ _ __
-    \___ \\___ \ / /\ \______| |  | |/ _ \/ __| __| '__|
-    ____) |___) / ____ \     | |__| |  __/\__ \ |_| |
-   |_____/_____/_/    \_\    |_____/ \___||___/\__|_|
-
- *****************************************************************************/
-
-#define mark_as_done(irn, pos)			set_irn_link(irn, INT_TO_PTR(pos+1))
-#define has_been_done(irn, pos)			(PTR_TO_INT(get_irn_link(irn)) > pos)
-
-/**
- * Insert a copy for the argument of @p start_phi found at position @p pos.
- * Also searches a phi-loop of arbitrary length to detect and resolve
- *   the class of phi-swap-problems. To search for a loop recursion is used.
- *
- * 1) Simplest case (phi with a non-phi arg):
- *     A single copy is inserted.
- *
- * 2) Phi chain (phi (with phi-arg)* with non=phi arg):
- *     Several copies are placed, each after returning from recursion.
- *
- * 3) Phi-loop:
- *     On detection a loop breaker is inserted, which is a copy of the start_phi.
- *     This copy then pretends beeing the argumnent of the last phi.
- *     Now case 2) can be used.
- *
- * The values of @p start_phi and @p pos never change during recursion.
- *
- * @p raenv      Environment with all the stuff needed
- * @p start_phi  Phi node to process
- * @p pos        Argument position to insert copy/copies for
- * @p curr_phi   Phi node currently processed during recursion. Equals start_phi on initial call
- *
- * @return NULL  If no copy is necessary
- *         NULL  If the phi has already been processed at this pos
- *               Link field is used to keep track of processed positions
- *         In all other cases the ir_node *copy which was placed is returned.
- */
-static ir_node *insert_copies(be_raext_env_t *raenv, ir_node *start_phi, int pos, ir_node *curr_phi) {
-	ir_node *arg = get_irn_n(curr_phi, pos);
-	ir_node *arg_blk = get_nodes_block(arg);
-	ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
-	ir_node *curr_cpy, *last_cpy;
-
-	assert(is_Phi(start_phi) && is_Phi(curr_phi));
-
-	if (has_been_done(start_phi, pos))
-		return NULL;
-
-	/* In case this is a 'normal' phi we insert into
-	 * the schedule before the pred_blk irn */
-	last_cpy = pred_blk;
-
-	/* If we detect a loop stop recursion. */
-	if (arg == start_phi) {
-		ir_node *loop_breaker;
-		if (start_phi == curr_phi) {
-			/* Phi directly uses itself. No copy necessary */
-			return NULL;
+		if(op->has_constraints) {
+			ir_node *cpy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
+			sched_add_before(insn->irn, cpy);
+			set_irn_n(insn->irn, op->pos, cpy);
+			be_set_constr_limited(cpy, BE_OUT_POS(0), &op->req);
 		}
-
-		/* At least 2 phis are involved */
-		/* Insert a loop breaking copy (an additional variable T) */
-		loop_breaker = be_new_Copy(raenv->cls, raenv->irg, pred_blk, start_phi);
-		sched_add_before(pred_blk, loop_breaker);
-
-		arg = loop_breaker;
 	}
-
-	/* If arg is a phi in the same block we have to continue search */
-	if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
-		last_cpy = insert_copies(raenv, start_phi, pos, arg);
-
-	/* Insert copy of argument (may be the loop-breaker) */
-	curr_cpy = be_new_Copy(raenv->cls, raenv->irg, pred_blk, arg);
-	set_irn_n(curr_phi, pos, curr_cpy);
-	mark_as_done(curr_phi, pos);
-	sched_add_before(last_cpy, curr_cpy);
-	return curr_cpy;
 }
 
+static void handle_constraints_block(ir_node *bl, void *data)
+{
+	be_raext_env_t *raenv = data;
+	int active            = bl != get_irg_start_block(raenv->irg);
 
-/**
- * Perform simple SSA-destruction with copies.
- * The order of processing _must_ be
- *  for all positions {
- *    for all phis {
- *      doit
- *    }
- *  }
- * else the magic to keep track of processed phi-positions will fail in
- * function 'insert_copies'
- */
-static void ssa_destr_simple_walker(ir_node *blk, void *env) {
-	be_raext_env_t *raenv = env;
-	int pos, max;
-	ir_node *phi;
-
-	/* for all argument positions of the phis */
-	for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
-
-		/* for all phi nodes (which are scheduled first) */
-		sched_foreach(blk, phi) {
-			if (!is_Phi(phi))
-				break;
-
-			raenv->cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
-			insert_copies(raenv, phi, pos, phi);
-		}
-	}
-}
-
-
-static void ssa_destr_simple(be_raext_env_t *raenv) {
-	be_clear_links(raenv->irg);
-	irg_block_walk_graph(raenv->irg, ssa_destr_simple_walker, NULL, raenv);
-}
-
-
-static void ssa_destr_rastello(be_raext_env_t *raenv) {
-	assert(0 && "NYI");
-	exit(0xDeadBeef);
-	/*
-	phi_class_compute(raenv->irg);
-	irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
-	*/
-}
-
-/******************************************************************************
-   __      __   _       ___   __      __
-   \ \    / /  | |     |__ \  \ \    / /
-    \ \  / /_ _| |___     ) |  \ \  / /_ _ _ __ ___
-     \ \/ / _` | / __|   / /    \ \/ / _` | '__/ __|
-      \  / (_| | \__ \  / /_     \  / (_| | |  \__ \
-       \/ \__,_|_|___/ |____|     \/ \__,_|_|  |___/
- *****************************************************************************/
-
-/**
- * This struct maps a variable (nr) to the values belonging to this variable
- */
-struct _var_info_t {
-	int var_nr;		/* the key */
-	pset *values;	/* the ssa-values belonging to this variable */
-};
-
-#define SET_REMOVED -1
-
-/**
- * The link field of an irn points to the var_info struct
- * representing the corresponding variable.
- */
-#define set_var_info(irn, vi)				set_irn_link(irn, vi)
-#define get_var_info(irn)					((var_info_t *)get_irn_link(irn))
-
-#define HASH_VAR_NR(var_nr) var_nr
-
-static int compare_var_infos(const void *e1, const void *e2, size_t size) {
-	const var_info_t *v1 = e1;
-	const var_info_t *v2 = e2;
-
-	if (v1->var_nr == SET_REMOVED || v2->var_nr == SET_REMOVED)
-		return 1;
-
-	return v1->var_nr != v2->var_nr;
-}
-
-static INLINE var_info_t *var_find(set *vars, int var_nr) {
-	var_info_t vi;
-	vi.var_nr = var_nr;
-
-	return set_find(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
-}
-
-static INLINE var_info_t *var_find_or_insert(set *vars, int var_nr) {
-	var_info_t vi, *found;
-	memset(&vi, 0, sizeof(vi));
-	vi.var_nr = var_nr;
-
-	found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
-
-	if (!found->values)
-		found->values  = pset_new_ptr(1);
+	ir_node *irn;
+	be_insn_env_t ie;
+	struct obstack obst;
 
-	return found;
-}
+	ie.cls           = raenv->cls;
+	ie.aenv          = raenv->aenv;
+	ie.obst          = &obst;
+	ie.ignore_colors = NULL;
+	obstack_init(&obst);
 
-/**
- * Adds a value to a variable. Sets all pointers accordingly.
- */
-static INLINE var_info_t *var_add_value(be_raext_env_t *raenv, int var_nr, ir_node *irn) {
-	var_info_t *vi = var_find_or_insert(raenv->vars, var_nr);
+	irn = sched_first(bl);
+	while(!sched_is_end(irn)) {
+		be_insn_t *insn = be_scan_insn(&ie, irn);
 
-	/* var 2 value mapping */
-	pset_insert_ptr(vi->values, irn);
+		if(insn->has_constraints)
+			handle_constraints_insn(raenv, insn);
 
-	/* value 2 var mapping */
-	set_var_info(irn, vi);
+		if(be_is_Barrier(irn))
+			active = !active;
 
-	return vi;
+		irn = insn->next_insn;
+		obstack_free(&obst, insn);
+	}
 }
 
-static INLINE pset *get_var_values(be_raext_env_t *raenv, int var_nr) {
-	var_info_t *vi = var_find(raenv->vars, var_nr);
-	assert(vi && "Variable does not exist");
-	return vi->values;
+static void handle_constraints(be_raext_env_t *raenv) {
+	irg_block_walk_graph(raenv->irg, NULL, handle_constraints_block, raenv);
 }
 
-/**
- * Define variables (numbers) for all SSA-values.
- * All values in a phi class get assigned the same variable name.
- * The link field maps values to the var-name
- */
-static void values_to_vars(ir_node *irn, void *env) {
-	be_raext_env_t *raenv = env;
-	int nr;
-	pset *vals;
-
-	vals = get_phi_class(irn);
-
-	if (vals) {
-		nr = get_irn_node_nr(get_first_phi(vals));
-	} else {
-		/* not a phi class member, value == var */
-		nr = get_irn_node_nr(irn);
-		vals = pset_new_ptr(1);
-		pset_insert_ptr(vals, irn);
-	}
 
-	/* values <--> var mapping */
-	pset_foreach(vals, irn)
-		var_add_value(raenv, nr, irn);
-}
 
 
 /******************************************************************************
@@ -461,9 +273,9 @@ static void values_to_vars(ir_node *irn, void *env) {
 
 static void extract_vars_of_cls(be_raext_env_t *raenv) {
 	int count = 0;
-	var_info_t *vi;
+	be_var_info_t *vi;
 
-	raenv->cls_vars = malloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars));
+	raenv->cls_vars = xmalloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars));
 	assert(raenv->cls_vars);
 
 	set_foreach(raenv->vars, vi)
@@ -495,24 +307,31 @@ static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos)
 	}
 }
 
-static INLINE int get_spill_costs(var_info_t *vi) {
+#define UNSPILLABLE -1
+
+static INLINE int get_spill_costs(be_raext_env_t *raenv, be_var_info_t *vi) {
 	ir_node *irn;
-	int n_spills=0, n_reloads=0;
+	int c_spills=0, c_reloads=0;
 
 	pset_foreach(vi->values, irn) {
+		if (arch_irn_is(raenv->aenv, irn, ignore) || be_is_Reload(irn)) {
+			pset_break(vi->values);
+			return UNSPILLABLE;
+		}
+
 		if (is_Phi(irn)) {
 			/* number of reloads is the number of non-phi uses of all values of this var */
 			const ir_edge_t *edge;
 			foreach_out_edge(irn, edge)
 				if (!is_Phi(edge->src))
-					n_reloads++;
+					c_reloads += get_reload_weight(edge->src);
 		} else {
 			/* number of spills is the number of non-phi values for this var */
-			n_spills++;
+			c_spills += get_spill_weight(irn);
 		}
 	}
 
-	return n_spills + n_reloads;
+	return c_spills + c_reloads;
 }
 
 static void dump_nodes(be_raext_env_t *raenv) {
@@ -522,25 +341,27 @@ static void dump_nodes(be_raext_env_t *raenv) {
 	fprintf(f, "\nnodes {\n");
 
 	for (i=0; i<raenv->n_cls_vars; ++i) {
-		var_info_t *vi = raenv->cls_vars[i];
+		be_var_info_t *vi = raenv->cls_vars[i];
 
 		if (vi->var_nr == SET_REMOVED)
 			continue;
 
-		fprintf(f, "%d %d", vi->var_nr, get_spill_costs(vi));
+		fprintf(f, "%d %d", vi->var_nr, get_spill_costs(raenv, vi));
 		dump_constraint(raenv, get_first_non_phi(vi->values), -1);
 		fprintf(f, "\n");
 	}
 
 	fprintf(f, "}\n");
+	fflush(f);
 }
 
 
 static void dump_interferences(be_raext_env_t *raenv) {
 	int i,o;
-	var_info_t *vi1, *vi2;
+	be_var_info_t *vi1, *vi2;
 	ir_node *irn1, *irn2;
 	FILE *f = raenv->f;
+	be_lv_t *lv = raenv->birg->lv;
 
 	fprintf(f, "\ninterferences {\n");
 
@@ -558,31 +379,39 @@ static void dump_interferences(be_raext_env_t *raenv) {
 
 			pset_foreach(vi1->values, irn1)
 				pset_foreach(vi2->values, irn2)
-					if (values_interfere(irn1, irn2)) {
+					if (values_interfere(lv, irn1, irn2)) {
 						pset_break(vi1->values);
 						pset_break(vi2->values);
 						fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
+						goto NextVar;
 					}
+
+NextVar: ;
 		}
 	}
 	fprintf(f, "}\n");
 }
 
-
 static void dump_affinities_walker(ir_node *irn, void *env) {
 	be_raext_env_t *raenv = env;
 	arch_register_req_t req;
 	int pos, max;
-	var_info_t *vi1, *vi2;
+	be_var_info_t *vi1, *vi2;
 
-	vi1 = get_var_info(irn);
+	if (arch_get_irn_reg_class(raenv->aenv, irn, -1) != raenv->cls || arch_irn_is(raenv->aenv, irn, ignore))
+		return;
+
+	vi1 = be_get_var_info(irn);
 
 	/* copies have affinities */
-	/* TODO? remove this case by adding should_be_equal requirements */
-	if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) {
-		vi2 = get_var_info(get_irn_n(irn, 0));
+	if (arch_irn_class_is(raenv->aenv, irn, copy)) {
+		ir_node *other = be_get_Copy_op(irn);
+
+		if (! arch_irn_is(raenv->aenv, other, ignore)) {
+			vi2 = be_get_var_info(other);
 
-		fprintf(raenv->f, "(%d, %d)\n",  vi1->var_nr, vi2->var_nr);
+			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
+		}
 	}
 
 
@@ -590,17 +419,17 @@ static void dump_affinities_walker(ir_node *irn, void *env) {
 	for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
 		arch_get_register_req(raenv->aenv, &req, irn, pos);
 
-		if (arch_register_req_is(&req, should_be_same)) {
-			vi2 = get_var_info(req.other);
+		if (arch_register_req_is(&req, should_be_same) && arch_irn_is(raenv->aenv, req.other_same, ignore)) {
+			vi2 = be_get_var_info(req.other_same);
 
-			fprintf(raenv->f, "(%d, %d)\n",  vi1->var_nr, vi2->var_nr);
+			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
 		}
 	}
 }
 
 
 static void dump_affinities(be_raext_env_t *raenv) {
-	fprintf(raenv->f, "\ninterferences {\n");
+	fprintf(raenv->f, "\naffinities {\n");
 	irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv);
 	fprintf(raenv->f, "}\n");
 }
@@ -614,6 +443,7 @@ static void dump_to_file(be_raext_env_t *raenv, char *filename) {
 
 	if (!(f = fopen(filename, "wt"))) {
 		fprintf(stderr, "Could not open file %s for writing\n", filename);
+		assert(0);
 		exit(0xdeadbeef);
 	}
 	raenv->f = f;
@@ -646,10 +476,12 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) {
 	char cmd_line[1024];
 	int ret_status;
 
-	snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", prog_to_call, out_file, result_file);
+	snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file);
+	cmd_line[sizeof(cmd_line) - 1] = '\0';
 
 	ret_status = system(cmd_line);
 	assert(ret_status != -1 && "Invokation of external register allocator failed");
+	assert(ret_status == 0 && "External register allocator is unhappy with sth.");
 }
 
 /******************************************************************************
@@ -667,27 +499,39 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) {
  * Spill a variable and add reloads before all uses.
  */
 static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) {
-	var_info_t *vi = var_find(raenv->vars, var_nr);
+	be_var_info_t *vi = be_var_find(raenv->vars, var_nr);
 	ir_node *spill=NULL, *ctx, *irn;
-	const ir_edge_t *edge;
+	ir_mode *mode;
+	const ir_edge_t *edge, *ne;
 	pset *spills  = pset_new_ptr(4);	/* the spills of this variable */
 	pset *reloads = pset_new_ptr(4);	/* the reloads of this variable */
+	be_lv_t *lv = raenv->birg->lv;
+	be_dom_front_info_t *dom_front = raenv->birg->dom_front;
 	int new_size, n_spills, n_reloads;
 
 	assert(vi && "Variable nr does not exist!");
 	assert(pset_count(vi->values) && "There are no values associated to this variable");
 
-	/* the spill context is set to an arbitrary node of the phi-class */
-	ctx = get_first_phi(vi->values);
+	/* the spill context is set to an arbitrary node of the phi-class,
+	 * or the node itself if it is not member of a phi class
+	 */
+	if (pset_count(vi->values) == 1)
+		ctx = get_first_non_phi(vi->values);
+	else
+		ctx = get_first_phi(vi->values);
+
+	DBG((raenv->dbg, LEVEL_2, "Spill context: %+F\n", ctx));
 
 	/* for each value of this variable insert the spills */
 	pset_foreach(vi->values, irn) {
-		if (is_Phi(irn))
+		if (is_Phi(irn)) {
+			sched_remove(irn);
 			continue;
+		}
 
 		/* all ordinary nodes must be spilled */
-		spill = be_new_Spill(raenv->cls, raenv->irg, get_nodes_block(irn), irn, ctx);
-		sched_add_after(irn, spill);
+		DBG((raenv->dbg, LEVEL_2, "  spilling %+F\n", irn));
+		spill = be_spill(raenv->aenv, irn);
 
 		/* remember the spill */
 		pset_insert_ptr(spills, spill);
@@ -695,23 +539,26 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr)
 
 	assert(spill && "There must be at least one non-phi-node");
 
+	mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
+
 	/* insert reloads and wire them arbitrary*/
 	pset_foreach(vi->values, irn)
-		foreach_out_edge(irn, edge) {
+		foreach_out_edge_safe(irn, edge, ne) {
 			ir_node *reload, *src = edge->src;
-			if (is_Phi(src))
+			if (is_Phi(src) || be_is_Spill(src))
 				continue;
 
 			/* all real uses must be reloaded */
-			reload = be_new_Reload(raenv->cls, raenv->irg, get_nodes_block(src), get_irn_mode(get_irn_n(spill, 0)), spill);
-			sched_add_before(src, reload);
+			DBG((raenv->dbg, LEVEL_2, "  reloading before %+F\n", src));
+			reload = be_reload(raenv->aenv, raenv->cls, edge->src, mode, spill);
+			set_irn_n(edge->src, edge->pos, reload);
 
 			/* remember the reload */
 			pset_insert_ptr(reloads, reload);
 		}
 
 	/* correct the reload->spill pointers... */
-	be_introduce_copies_for_set(raenv->dom_info, spills, reloads);
+	be_ssa_constr_set(dom_front, lv, spills);
 
 
 	/****** correct the variable <--> values mapping: ******
@@ -734,16 +581,16 @@ static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr)
 
 		/* ...add new vars for each non-phi-member */
 		pset_foreach(spills, irn) {
-			ir_node *spilled = get_irn_n(irn, 0);
-			raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(spilled), spilled);
+			ir_node *spilled = get_irn_n(irn, be_pos_Spill_val);
+			raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(spilled), spilled);
 		}
 	}
 
 	/* add new variables for all reloads */
-	pset_foreach(reloads, irn)
-		raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(irn), irn);
-
-
+	pset_foreach(reloads, irn) {
+		assert(get_irn_node_nr(irn) != 1089);
+		raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(irn), irn);
+	}
 
 	del_pset(spills);
 	del_pset(reloads);
@@ -765,6 +612,7 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 
 	if (!(f = fopen(filename, "rt"))) {
 		fprintf(stderr, "Could not open file %s for reading\n", filename);
+		assert(0);
 		exit(0xdeadbeef);
 	}
 	raenv->f = f;
@@ -787,7 +635,7 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 		is_allocation = 1;
 		while (fscanf(f, " %d %d ", &var_nr, &reg_nr) == 2) {
 			ir_node *irn;
-			pset *vals = get_var_values(raenv, var_nr);
+			pset *vals = be_get_var_values(raenv->vars, var_nr);
 
 			assert(vals && "Variable nr does not exist!");
 			pset_foreach(vals, irn)
@@ -804,6 +652,34 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 	return is_allocation;
 }
 
+static void check_allocation(be_raext_env_t *raenv) {
+	int i, o;
+	be_lv_t *lv = raenv->birg->lv;
+
+	for (i=0; i<raenv->n_cls_vars; ++i) {
+		be_var_info_t *vi1 = raenv->cls_vars[i];
+
+		if (vi1->var_nr == SET_REMOVED)
+			continue;
+
+		for (o=0; o<i; ++o) {
+			be_var_info_t *vi2 = raenv->cls_vars[o];
+			ir_node *irn1, *irn2;
+
+			if (vi2->var_nr == SET_REMOVED)
+				continue;
+
+			pset_foreach(vi1->values, irn1)
+				pset_foreach(vi2->values, irn2)
+					if (values_interfere(lv, irn1, irn2) && arch_get_irn_register(raenv->aenv, irn1) == arch_get_irn_register(raenv->aenv, irn2)) {
+						dump_ir_block_graph_sched(raenv->irg, "ERROR");
+						ir_fprintf(stdout, "SSA values %+F and %+F interfere. They belong to variable %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr);
+						assert(0 && "ERROR graph dumped");
+					}
+		}
+	}
+}
+
 /******************************************************************************
     __  __       _
    |  \/  |     (_)
@@ -816,8 +692,8 @@ static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 /**
  * Default values for options
  */
-static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple;
-static char callee[128] = "echo";
+static char callee[128] = "\"E:/user/kimohoff/public/register allocator\"";
+//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
 
 
 /**
@@ -829,59 +705,72 @@ static char callee[128] = "echo";
  * Read in results and apply them
  *
  */
-static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
-	be_raext_env_t raenv;
+static void be_ra_extern_main(be_irg_t *birg) {
+	be_main_env_t *env = birg->main_env;
+	ir_graph *irg = birg->irg;
+
+ 	be_raext_env_t raenv;
 	int clsnr, clss;
-	var_info_t *vi;
 
-	compute_doms(irg);
+	be_assure_dom_front(birg);
+	be_assure_liveness(birg);
+	edges_assure(irg);
 
 	raenv.irg      = irg;
+	raenv.birg     = birg;
 	raenv.aenv     = env->arch_env;
-	raenv.dom_info = be_compute_dominance_frontiers(irg);
-	raenv.vars     = new_set(compare_var_infos, 64);
+	FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern");
 
 	/* Insert copies for constraints */
-	handle_constraints(&raenv);
-	dump_ir_block_graph_sched(irg, "-extern-constr");
+	for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
+		raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
+		handle_constraints(&raenv);
+	}
 
-	/* SSA destruction respectively transformation into "Conventional SSA" */
-	ssa_destr(&raenv);
-	dump_ir_block_graph_sched(irg, "-extern-ssadestr");
+	be_dump(irg, "-extern-constr", dump_ir_block_graph_sched);
 
+	/* SSA destruction respectively transformation into "Conventional SSA" */
+	raenv.vars = be_ssa_destr_simple(irg, env->arch_env);
+	be_dump(irg, "-extern-ssadestr", dump_ir_block_graph_sched);
 
-	/* Mapping of SSA-Values <--> Variables */
-	phi_class_compute(irg);
-	be_clear_links(irg);
-	irg_walk_graph(irg, values_to_vars, NULL, &raenv);
 
 	/* For all register classes */
 	for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
-		int done = 0;
+		int done, round = 1;
 		char out[256], in[256];
 
 		raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
-		ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
-		ir_snprintf(in, sizeof(in), "%F-%s.ra.res", irg, raenv.cls->name);
 
 		extract_vars_of_cls(&raenv);
 
-		while (!done) {
+		do {
+			ir_snprintf(out, sizeof(out), "%F-%s-%d.ra", irg, raenv.cls->name, round);
+			ir_snprintf(in, sizeof(in), "%F-%s-%d.ra.res", irg, raenv.cls->name, round);
+
+			be_liveness(irg);
+
 			dump_to_file(&raenv, out);
 			execute(callee, out, in);
 			done = read_and_apply_results(&raenv, in);
-		}
+			be_abi_fix_stack_nodes(birg->abi, birg->lv);
+
+			ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round);
+			be_dump(irg, in, dump_ir_block_graph_sched);
+
+			round++;
+		} while (!done);
+
+		check_allocation(&raenv);
 
 		free(raenv.cls_vars);
 	}
 
-	dump_ir_block_graph_sched(irg, "-extern-alloc");
+	be_dump(irg, "-extern-alloc", dump_ir_block_graph_sched);
 
 	/* Clean up */
-	set_foreach(raenv.vars, vi)
-		del_pset(vi->values);
-	del_set(raenv.vars);
-	be_free_dominance_frontiers(raenv.dom_info);
+	free_ssa_destr_simple(raenv.vars);
+
+	be_invalidate_liveness(birg);
 }
 
 /******************************************************************************
@@ -897,14 +786,16 @@ static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
 
 #ifdef WITH_LIBCORE
 
-static const lc_opt_enum_const_ptr_items_t ssa_destr_items[] = {
-	{ "simple",    ssa_destr_simple },
-	{ "rastello",  ssa_destr_rastello },
+
+static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = {
+	{ "simple",     (int (*)(void)) be_ssa_destr_simple }, /* TODO make (void*) casts nicer */
 	{ NULL,      NULL }
 };
 
-static lc_opt_enum_const_ptr_var_t ssa_destr_var = {
-	(const void **) &ssa_destr, ssa_destr_items
+static set* (*ssa_destr)(ir_graph*,const arch_env_t*) = be_ssa_destr_simple;
+
+static lc_opt_enum_func_ptr_var_t ssa_destr_var = {
+	 (int (**)(void)) &ssa_destr, ssa_destr_items
 };
 
 static const lc_opt_table_entry_t be_ra_extern_options[] = {
@@ -913,17 +804,19 @@ static const lc_opt_table_entry_t be_ra_extern_options[] = {
 	{ NULL }
 };
 
-static void be_ra_extern_register_options(lc_opt_entry_t *root) {
-	lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext");
+static be_ra_t be_ra_external_allocator = {
+	be_ra_extern_main
+};
+
+void be_init_raextern(void) {
+	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+	lc_opt_entry_t *blocksched_grp = lc_opt_get_grp(be_grp, "ra");
+	lc_opt_entry_t *ext_grp = lc_opt_get_grp(blocksched_grp, "ext");
 
-	lc_opt_add_table(grp, be_ra_extern_options);
+	lc_opt_add_table(ext_grp, be_ra_extern_options);
+
+	be_register_allocator("ext", &be_ra_external_allocator);
 }
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_raextern);
 
 #endif /* WITH_LIBCORE */
-
-const be_ra_t be_ra_external_allocator = {
-#ifdef WITH_LIBCORE
-	be_ra_extern_register_options,
-#endif
-	be_ra_extern_main
-};