X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fberaextern.c;h=fcc14bbaea2d149aa4c869e17e7873e06e422d29;hb=48071aea23fabc99044488d12757f274bc956fae;hp=adc330f3e3f2d7ad2f89bae60e99a6155765f76a;hpb=f0df704b76a6902c398d3d201c83d99448cd0584;p=libfirm

diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c
index adc330f3e..fcc14bbae 100644
--- a/ir/be/beraextern.c
+++ b/ir/be/beraextern.c
@@ -6,74 +6,50 @@
  *
  * 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
  *
 
 
 The input file format
 ----------------------
 
-inputfile	::= regs cfg .
-
-regs		::= 'regs' regcount 'saved-by-caller' reg-list 'saved-by-callee' reg-list .						// Anzahl der register (0..regcount-1), die zur Verfuegung stehen
-
-reg-list	::= reg-nr
-			  | reg-nr reg-list
+inputfile	::= regs nodes interf affinities .
 
-cfg			::= 'cfg' ident '{' block* edge* '}' .		// Steuerflussgraph der Prozedur
+regs		::= 'regs' regcount .						// Anzahl der register (0..regcount-1), die zur Verfuegung stehen
 
-block		::= 'block' block-nr '{' insn* '}' .		// Grundblock im cfg versehen mit einer nummer
+nodes		::= 'nodes' '{' node* '}' .					// All nodes in the graph
 
-edge		::= 'cf-edge' block-nr block-nr .			// Steuerflusskante src-->tgt
+node		::= node-info
+			  | node-info '<' reg-nr '>' .				// Reg-nr is present in case of constraints
 
-insn		::= gen-insn 								// Befehl in einem block
-			  | copy-insn .
+node-info	::= node-nr spill-costs .
 
-gen-insn	::= 'insn' insn-nr '{' uses defs '}' .
-copy-insn	::= 'copy' insn-nr '{' uses defs '}' .
-call-insn	::= 'call' insn-nr '{' uses defs '}' .
+interf		::= 'interferences' '{' i-edge* '}' .		// Interference edges of the graph
 
-defs		::= 'def' var-list .						// Liste der definierten/verwendeten Variablen
-uses		::= 'use' var-list .
+i-edge		::= '(' node-nr ',' node-nr ')' .
 
-var-list	::= var-ref
-			  | var-ref var-list .
+affinities	::= 'affinities' '{' a-edge* '}' .			// Affinity edges of the graph
 
-var-ref		::= var-nr
-			  | var-nr '<' reg-nr '>' .					// reg-nr gibt register constraint an.
+a-edge		::= '(' node-nr ',' node-nr ',' weight ')' .
 
 
-ident		::= non-whitespace-char* .
-regcount, block-nr, insn-nr, reg-nr, var-nr ::= integer .
-
+weight, regcount, node-nr ::= int32 .
+spill-costs ::= int32 .									// negative spill costs indicate unspillable
 
 The output file format
 -----------------------
 
-outputfile	::= action* assign*.
-
-action		::= 'spill'  loc var-nr					// insert a spill    spill(var-nr);
-			  | 'reload' loc new-var-nr  var-nr		// insert a reload   new-var-nr := reload(var-nr);
-			  | 'setarg' insn-nr pos var-nr			// change a usage to insn(..., var-nr, ...)  (equals set_irn_n)
-			  | 'copy'   loc var-nr var-nr			// insert a copy     var-nr[1] := var-nr[2];
+outputfile	::= spills | allocs .
 
-assign		::= 'assign' var-nr reg-nr .			// assign var-nr the register reg-nr
+spills		::= 'spills' node-nr+ .
 
-loc			::= 'before' insn-nr
-			  | 'after'  insn-nr .
-
-
-Constraints for output file
----------------------------
-1) The returned actions must result in a non-ssa-program
-   equivalent to the former input.
-2) All names (numbers) must be defined before their first use.
-   Numbers already occuring in the input file are implicitly defined in the output file.
-3) All spills of a variable must precede the first reload of this variable
-4) Each reload must define a new variable name
+allocs		::= 'allocs' alloc* .
 
+alloc		::= node-nr reg-nr .
 
 
 ******** End of file format docu ********/
@@ -82,14 +58,16 @@ Constraints for output file
 #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>
@@ -104,17 +82,23 @@ Constraints for output file
 #include "irnode_t.h"
 #include "irgraph_t.h"
 #include "irgwalk.h"
+#include "iredges_t.h"
 #include "irdom_t.h"
 #include "phiclass.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
@@ -122,12 +106,15 @@ 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_lv_t *lv;
 	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 */
-	pmap *nodes;	/**< maps nodes numbers (int) to the node (ir_node*) having that node_nr */
+	FILE *f;				/**< file handle used for out- and input file */
+	set *vars;				/**< contains all be_var_info_t */
+	int n_cls_vars;			/**< length of the array cls_vars */
+	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;
 
 
@@ -147,7 +134,6 @@ typedef struct _be_raext_env_t {
 #define pset_foreach(pset, irn)  for(irn=pset_first(pset); irn; irn=pset_next(pset))
 #define set_foreach(set, e)  for(e=set_first(set); e; e=set_next(set))
 
-
 /**
  * Checks if _the_ result of the irn belongs to the
  * current register class (raenv->cls)
@@ -155,666 +141,539 @@ typedef struct _be_raext_env_t {
  */
 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
 
+static INLINE ir_node *get_first_non_phi(pset *s) {
+	ir_node *irn;
 
-/**
- * Checks if the irn uses or defines values of the
- * current register class (raenv->cls)
- */
-static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
-	int max, i;
-
-	/* check arguments */
-	for (i=0, max=get_irn_arity(irn); i<max; ++i)
-		if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
-			return 1;
-
-	/* check result(s) */
-	if (get_irn_mode(irn) == mode_T) {
-		ir_node *proj;
-		for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
-			if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
-				return 1;
-		return 0;
-	} else {
-		return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
-	}
+	pset_foreach(s, irn)
+		if (!is_Phi(irn)) {
+			pset_break(s);
+			return irn;
+		}
 
-	assert(0 && "Where did you come from???");
+	assert(0 && "There must be a non-phi-irn in this");
+	return NULL;
 }
 
-/******************************************************************************
-     _____ _____              _____            _
-    / ____/ ____|  /\        |  __ \          | |
-   | (___| (___   /  \ ______| |  | | ___  ___| |_ _ __
-    \___ \\___ \ / /\ \______| |  | |/ _ \/ __| __| '__|
-    ____) |___) / ____ \     | |__| |  __/\__ \ |_| |
-   |_____/_____/_/    \_\    |_____/ \___||___/\__|_|
-
- *****************************************************************************/
-
-#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)
+static INLINE ir_node *get_first_phi(pset *s) {
+	ir_node *irn;
 
-/**
- * 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;
+	pset_foreach(s, irn)
+		if (is_Phi(irn)) {
+			pset_break(s);
+			return irn;
 		}
 
-		/* 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;
+	assert(0 && "There must be a phi in this");
+	return NULL;
 }
 
+static int get_loop_weight(ir_node *irn) {
+	int cost = 0;
+	ir_loop *loop = get_irn_loop(get_nodes_block(irn));
 
-/**
- * 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);
-		}
+	if (loop) {
+		int d = get_loop_depth(loop);
+		cost = d*d;
 	}
+	return cost+1;
 }
 
+#define get_const_weight(irn) (1)
 
-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");
-	/* TODO
-	phi_class_compute(raenv->irg);
-	irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
-	*/
-}
+#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)
 
 /******************************************************************************
-   __      __   _       ___   __      __
-   \ \    / /  | |     |__ \  \ \    / /
-    \ \  / /_ _| |___     ) |  \ \  / /_ _ _ __ ___
-     \ \/ / _` | / __|   / /    \ \/ / _` | '__/ __|
-      \  / (_| | \__ \  / /_     \  / (_| | |  \__ \
-       \/ \__,_|_|___/ |____|     \/ \__,_|_|  |___/
+    _____                _            _____            _
+   / ____|              | |          / ____|          (_)
+  | |     ___  _ __  ___| |_ _ __   | |     ___  _ __  _  ___  ___
+  | |    / _ \| '_ \/ __| __| '__|  | |    / _ \| '_ \| |/ _ \/ __|
+  | |___| (_) | | | \__ \ |_| |     | |___| (_) | |_) | |  __/\__ \
+   \_____\___/|_| |_|___/\__|_|      \_____\___/| .__/|_|\___||___/
+                                                | |
+                                                |_|
  *****************************************************************************/
 
-/**
- * This struct maps a variable (nr) to
- *  1) the values belonging to this variable
- *  2) the spills of this variable
- */
-struct _var_info_t {
-	int var_nr;		/* the key for comparesion */
-	pset *values;	/* the ssa-values belonging to this variable */
-	pset *spills;	/* the spills of this variable */
-	pset *reloads;	/* the relaods of this variable */
-	unsigned reload_phase:1;	/* 0 initially, 1 if a reload of this var has been inserted */
-};
+static void handle_constraints_insn(be_raext_env_t *env, be_insn_t *insn)
+{
+	ir_node *bl = get_nodes_block(insn->irn);
+	int i;
 
-/**
- * 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))
+	for(i = 0; i < insn->use_start; ++i) {
+		be_operand_t *op = &insn->ops[i];
 
-/* TODO insn-nr handling if ext defines new ones */
-#define pmap_insert_sth(pmap, key, val)	pmap_insert(pmap, (void *)key, (void *)val)
-#define pmap_get_sth(pmap, key)			pmap_get(pmap, (void *)key)
-
-
-#define HASH_VAR_NR(var_nr) var_nr
+		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);
+		}
+	}
 
+	for(i = insn->use_start; i < insn->n_ops; ++i) {
+		be_operand_t *op = &insn->ops[i];
 
+		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);
+		}
+	}
+}
 
-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;
+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);
 
-	return v1->var_nr != v2->var_nr;
-}
+	ir_node *irn;
+	be_insn_env_t ie;
+	struct obstack obst;
 
-static INLINE var_info_t *var_find(set *vars, int var_nr) {
-	var_info_t vi;
-	vi.var_nr = var_nr;
+	ie.cls           = raenv->cls;
+	ie.aenv          = raenv->aenv;
+	ie.obst          = &obst;
+	ie.ignore_colors = NULL;
+	obstack_init(&obst);
 
-	return set_find(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
-}
+	irn = sched_first(bl);
+	while(!sched_is_end(irn)) {
+		be_insn_t *insn = be_scan_insn(&ie, irn);
 
-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;
+		if(insn->has_constraints)
+			handle_constraints_insn(raenv, insn);
 
-	found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
+		if(be_is_Barrier(irn))
+			active = !active;
 
-	if (!found->values) {
-		found->values  = pset_new_ptr(1);
-		found->spills  = pset_new_ptr(1);
-		found->reloads = pset_new_ptr(1);
+		irn = insn->next_insn;
+		obstack_free(&obst, insn);
 	}
-
-	return found;
 }
 
-/**
- * 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);
+static void handle_constraints(be_raext_env_t *raenv) {
+	irg_block_walk_graph(raenv->irg, NULL, handle_constraints_block, raenv);
+}
 
-	/* var 2 value mapping */
-	pset_insert_ptr(vi->values, irn);
 
-	/* value 2 var mapping */
-	set_var_info(irn, vi);
 
-	return vi;
-}
 
-/**
- * Adds a spill to a variable. Sets all pointers accordingly.
- */
-static INLINE var_info_t *var_add_spill(be_raext_env_t *raenv, int var_to_spill, ir_node *before) {
-	var_info_t *vi = var_find_or_insert(raenv->vars, var_to_spill);
-	ir_node *blk, *tospill, *spill;
+/******************************************************************************
+    _____
+   |  __ \
+   | |  | |_   _ _ __ ___  _ __   ___ _ __
+   | |  | | | | | '_ ` _ \| '_ \ / _ \ '__|
+   | |__| | |_| | | | | | | |_) |  __/ |
+   |_____/ \__,_|_| |_| |_| .__/ \___|_|
+                          | |
+                          |_|
+ *****************************************************************************/
 
-	assert(pset_count(vi->values) && "There are no values associated to this variable (yet?)");
-	assert(!vi->reload_phase && "I have already seen a reload for this variable, so you cant spill anymore!");
 
-	/* add spill to graph and schedule */
-	blk     = get_nodes_block(before);
-	tospill = dom_up_search(vi->values, before); /* which value gets spilled */
-	spill   = be_new_Spill(raenv->cls, raenv->irg, blk, tospill, tospill); /* the corresponding spill node */
+static void extract_vars_of_cls(be_raext_env_t *raenv) {
+	int count = 0;
+	be_var_info_t *vi;
 
-	sched_add_before(before, spill);
+	raenv->cls_vars = xmalloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars));
+	assert(raenv->cls_vars);
 
-	/* the spill also points to the var_info of the spilled node */
-	set_var_info(spill, vi);
+	set_foreach(raenv->vars, vi)
+		if (is_res_in_reg_class(get_first_non_phi(vi->values)))
+			raenv->cls_vars[count++] = vi;
 
-	/* remember the spill */
-	pset_insert_ptr(vi->spills, spill);
+	raenv->cls_vars = realloc(raenv->cls_vars, count * sizeof(*raenv->cls_vars));
+	assert(raenv->cls_vars);
 
-	return vi;
+	raenv->n_cls_vars = count;
 }
 
+
 /**
- * Adds a reload to a variable. Sets all pointers accordingly.
+ * Check if node irn has a limited-constraint at position pos.
+ * If yes, dump it to FILE raenv->f
  */
-static INLINE var_info_t *var_add_reload(be_raext_env_t *raenv, int var_to_reload, int var_nr_for_reload, ir_node *before) {
-	var_info_t *vi = var_find_or_insert(raenv->vars, var_to_reload);
-	ir_node *blk, *spill, *reload;
-
-	assert(pset_count(vi->spills) && "There are no spills associated to this variable (yet?)");
-	/* now we enter the reload phase, so no more spills are allowed */
-	vi->reload_phase = 1;
+static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
+	bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
+	arch_register_req_t req;
 
-	/* add reload to graph and schedule */
-	blk    = get_nodes_block(before);
-	spill  = pset_first(vi->spills); /* For now use an arbitrary spill node. This is corrected later in fix_reloads */
-	pset_break(vi->spills);
-	reload = be_new_Reload(raenv->cls, raenv->irg, blk, get_irn_mode(get_irn_n(spill, 0)), spill);
+	arch_get_register_req(raenv->aenv, &req, irn, pos);
+	if (arch_register_req_is(&req, limited)) {
+		int reg_nr;
+		req.limited(req.limited_env, bs);
+		reg_nr = bitset_next_set(bs, 0);
+		fprintf(raenv->f, "<%d>", reg_nr);
+		assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
+	}
+}
 
-	sched_add_before(before, reload);
+#define UNSPILLABLE -1
 
-	/* create a new variable for the result of the reload */
-	assert(!var_find(raenv->vars, var_nr_for_reload) && "Each reload must define a new variable");
-	var_add_value(raenv, var_nr_for_reload, reload);
+static INLINE int get_spill_costs(be_raext_env_t *raenv, be_var_info_t *vi) {
+	ir_node *irn;
+	int c_spills=0, c_reloads=0;
 
-	/* remember the reload */
-	pset_insert_ptr(vi->reloads, reload);
+	pset_foreach(vi->values, irn) {
+		if (arch_irn_is(raenv->aenv, irn, ignore) || be_is_Reload(irn)) {
+			pset_break(vi->values);
+			return UNSPILLABLE;
+		}
 
-	return vi;
-}
+		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))
+					c_reloads += get_reload_weight(edge->src);
+		} else {
+			/* number of spills is the number of non-phi values for this var */
+			c_spills += get_spill_weight(irn);
+		}
+	}
 
-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 (yet?) exist");
-	return vi->values;
+	return c_spills + c_reloads;
 }
 
-static INLINE pset *get_var_spills(be_raext_env_t *raenv, int var_nr) {
-	var_info_t *vi = var_find(raenv->vars, var_nr);
-	assert(vi && "Variable does not (yet?) exist");
-	return vi->spills;
-}
+static void dump_nodes(be_raext_env_t *raenv) {
+	FILE *f = raenv->f;
+	int i;
 
-static INLINE pset *get_var_reloads(be_raext_env_t *raenv, int var_nr) {
-	var_info_t *vi = var_find(raenv->vars, var_nr);
-	assert(vi && "Variable does not (yet?) exist");
-	return vi->reloads;
-}
+	fprintf(f, "\nnodes {\n");
 
-/**
- * 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;
-	ir_node *n;
-	int nr;
-	pset *vals;
+	for (i=0; i<raenv->n_cls_vars; ++i) {
+		be_var_info_t *vi = raenv->cls_vars[i];
 
-	vals = get_phi_class(irn);
+		if (vi->var_nr == SET_REMOVED)
+			continue;
 
-	if (!vals) {
-		/* not a phi class member, value == var */
-		vals = pset_new_ptr(1);
-		pset_insert_ptr(vals, irn);
+		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");
 	}
 
-	/* values <--> var mapping */
-	n = pset_first(vals);
-	nr = get_irn_node_nr(n);
-	for (; n; n=pset_next(vals))
-		var_add_value(raenv, nr, n);
+	fprintf(f, "}\n");
+	fflush(f);
 }
 
-/******************************************************************************
-                         _         _____                 _ _
-       /\               | |       |  __ \               | | |
-      /  \   _ __  _ __ | |_   _  | |__) |___  ___ _   _| | |_
-     / /\ \ | '_ \| '_ \| | | | | |  _  // _ \/ __| | | | | __|
-    / ____ \| |_) | |_) | | |_| | | | \ \  __/\__ \ |_| | | |_
-   /_/    \_\ .__/| .__/|_|\__, | |_|  \_\___||___/\__,_|_|\__|
-            | |   | |       __/ |
-            |_|   |_|      |___/
- *****************************************************************************/
 
-#define INVALID_FILE_FORMAT assert(0 && "Invalid file format.")
+static void dump_interferences(be_raext_env_t *raenv) {
+	int i,o;
+	be_var_info_t *vi1, *vi2;
+	ir_node *irn1, *irn2;
+	FILE *f = raenv->f;
 
-static INLINE int is_before(const char *s, size_t len) {
-	if (!strncmp(s, "before", len))
-		return 1;
-	if (!strncmp(s, "after", len))
-		return 0;
-	INVALID_FILE_FORMAT;
-	return -1;
-}
+	fprintf(f, "\ninterferences {\n");
 
-static void fix_reloads(be_raext_env_t *raenv) {
-	var_info_t *vi;
-	set_foreach(raenv->vars, vi)
-		be_introduce_copies_pset(raenv->dom_info, vi->spills);
-}
+	for (i=0; i<raenv->n_cls_vars; ++i) {
+		vi1 = raenv->cls_vars[i];
 
-/**
- * Read in the actions performed by the external allocator.
- * Apply these transformations to the irg.
- */
-static void read_and_apply_results(be_raext_env_t *raenv, char *filename) {
-	FILE *f;
-	var_info_t *vi;
-	int phase=0;
+		if (vi1->var_nr == SET_REMOVED)
+			continue;
 
-	if (!(f = fopen(filename, "rt"))) {
-		fprintf(stderr, "Could not open file %s for reading\n", filename);
-		exit(0xdeadbeef);
-	}
-	raenv->f = f;
+		for (o=i+1; o<raenv->n_cls_vars; ++o) {
+			vi2 = raenv->cls_vars[o];
 
+			if (vi2->var_nr == SET_REMOVED)
+				continue;
 
+			pset_foreach(vi1->values, irn1)
+				pset_foreach(vi2->values, irn2)
+					if (values_interfere(raenv->lv, irn1, irn2)) {
+						pset_break(vi1->values);
+						pset_break(vi2->values);
+						fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
+						goto NextVar;
+					}
 
-	/* parse the file */
-	while (phase == 0) {
-		int loc, var_use_ident, var_def_ident, pos;
-		char where[16];
+NextVar: ;
+		}
+	}
+	fprintf(f, "}\n");
+}
 
-		/* handle a spill */
-		if (fscanf(f, " spill %6s %d %d ", &where, &loc, &var_use_ident) == 3) {
+static void dump_affinities_walker(ir_node *irn, void *env) {
+	be_raext_env_t *raenv = env;
+	arch_register_req_t req;
+	int pos, max;
+	be_var_info_t *vi1, *vi2;
 
-			/* determine the node to insert the spill before */
-			ir_node *anchor = pmap_get_sth(raenv->nodes, loc);
-			assert(anchor && "insn-nr does not exist");
-			if (!is_before(where, sizeof(where)))
-				anchor = sched_next(anchor);
+	if (arch_get_irn_reg_class(raenv->aenv, irn, -1) != raenv->cls || arch_irn_is(raenv->aenv, irn, ignore))
+		return;
 
-			var_add_spill(raenv, var_use_ident, anchor);
-		}
+	vi1 = be_get_var_info(irn);
 
-		/* handle a reload */
-		else if (fscanf(f, " reload %s %d %d %d ", &where, &loc, &var_def_ident, &var_use_ident) == 4) {
+	/* copies have affinities */
+	if (arch_irn_class_is(raenv->aenv, irn, copy)) {
+		ir_node *other = be_get_Copy_op(irn);
 
-			/* determine the node to insert the spill before */
-			ir_node *anchor = pmap_get_sth(raenv->nodes, loc);
-			assert(anchor && "insn-nr does not exist");
-			if (!is_before(where, sizeof(where)))
-				anchor = sched_next(anchor);
+		if (! arch_irn_is(raenv->aenv, other, ignore)) {
+			vi2 = be_get_var_info(other);
 
-			var_add_reload(raenv, var_use_ident, var_def_ident, anchor);
+			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
 		}
+	}
 
-		/* handle a set_irn_n */
-		else if (fscanf(f, " setarg %d %d %d ", &loc, &pos, &var_use_ident) == 3) {
-			ir_node *to_change, *new_arg;
-			var_info_t *vi = var_find(raenv->vars, var_use_ident);
-			assert(vi && vi->values && "New argument does not exist");
 
-			to_change = pmap_get_sth(raenv->nodes, loc);
-			assert(to_change && "insn-nr does not exist");
+	/* should_be_equal constraints are affinites */
+	for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
+		arch_get_register_req(raenv->aenv, &req, irn, pos);
 
-			new_arg = dom_up_search(vi->values, to_change);
-			set_irn_n(to_change, pos, new_arg);
-		}
+		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);
 
-		/* handle a copy insertion */
-		else if (fscanf(f, " copy %s %d %d %d ", &where, &loc, &var_def_ident, &var_use_ident) == 4) {
-			/* TODO
-				Ziel der Kopie ist Variable die bereits existiert
-				Ziel der Kopie ist eine neue Variable
-			*/
+			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
 		}
-
-		else
-			phase++;
 	}
+}
 
-	fix_reloads(raenv);
 
-	while (phase == 1) {
-		int var_use_ident, reg_nr;
+static void dump_affinities(be_raext_env_t *raenv) {
+	fprintf(raenv->f, "\naffinities {\n");
+	irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv);
+	fprintf(raenv->f, "}\n");
+}
 
-		/* assign register */
-		if (fscanf(f, " assign %d %d ", &var_use_ident, &reg_nr) == 2) {
-			pset *vals = get_var_values(raenv, var_use_ident);
-			ir_node *irn;
+/**
+ * Dump all information needed by the external
+ * register allocator to a single file.
+ */
+static void dump_to_file(be_raext_env_t *raenv, char *filename) {
+	FILE *f;
 
-			assert(vals && "Variable does not (yet?) exist!");
-			pset_foreach(vals, irn)
-				arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, var_use_ident));
-		}
-		else
-			phase++;
+	if (!(f = fopen(filename, "wt"))) {
+		fprintf(stderr, "Could not open file %s for writing\n", filename);
+		assert(0);
+		exit(0xdeadbeef);
 	}
+	raenv->f = f;
 
-	if (!feof(f))
-		INVALID_FILE_FORMAT;
+	/* dump register info */
+	fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
 
-	fclose(f);
+	/* dump the interference graph */
+	dump_nodes(raenv);
+	dump_interferences(raenv);
+	dump_affinities(raenv);
 
-	/* Free the psets held in the variable-infos */
-	set_foreach(raenv->vars, vi) {
-		del_pset(vi->values);
-		del_pset(vi->spills);
-		del_pset(vi->reloads);
-	}
+	fclose(f);
 }
 
 /******************************************************************************
-    _____
-   |  __ \
-   | |  | |_   _ _ __ ___  _ __   ___ _ __
-   | |  | | | | | '_ ` _ \| '_ \ / _ \ '__|
-   | |__| | |_| | | | | | | |_) |  __/ |
-   |_____/ \__,_|_| |_| |_| .__/ \___|_|
-                          | |
-                          |_|
+    ______                     _
+   |  ____|                   | |
+   | |__  __  _____  ___ _   _| |_ ___
+   |  __| \ \/ / _ \/ __| | | | __/ _ \
+   | |____ >  <  __/ (__| |_| | ||  __/
+   |______/_/\_\___|\___|\__,_|\__\___|
  *****************************************************************************/
 
-
 /**
- * Check if node irn has a limited-constraint at position pos.
- * If yes, dump it to FILE raenv->f
+ * Execute the external register allocator specified in the
+ * firm-option firm.be.ra.ext.callee
  */
-static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
-	bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
-	arch_register_req_t req;
+static void execute(char *prog_to_call, char *out_file, char *result_file) {
+	char cmd_line[1024];
+	int ret_status;
 
-	arch_get_register_req(raenv->aenv, &req, irn, pos);
-	if (arch_register_req_is(&req, limited)) {
-		int reg_nr;
-		req.limited(irn, pos, bs);
-		reg_nr = bitset_next_set(bs, 0);
-		fprintf(raenv->f, " <%d>", reg_nr);
-		assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
-	}
+	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.");
 }
 
+/******************************************************************************
+                         _         _____                 _ _
+       /\               | |       |  __ \               | | |
+      /  \   _ __  _ __ | |_   _  | |__) |___  ___ _   _| | |_
+     / /\ \ | '_ \| '_ \| | | | | |  _  // _ \/ __| | | | | __|
+    / ____ \| |_) | |_) | | |_| | | | \ \  __/\__ \ |_| | | |_
+   /_/    \_\ .__/| .__/|_|\__, | |_|  \_\___||___/\__,_|_|\__|
+            | |   | |       __/ |
+            |_|   |_|      |___/
+ *****************************************************************************/
 
 /**
- * Dump all blocks and instructions in that block
+ * Spill a variable and add reloads before all uses.
  */
-static void dump_blocks(ir_node *blk, void *env) {
-	be_raext_env_t *raenv = env;
-	ir_node *irn;
-	FILE *f = raenv->f;
-	int nr = get_irn_node_nr(blk);
+static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) {
+	be_var_info_t *vi = be_var_find(raenv->vars, var_nr);
+	ir_node *spill=NULL, *ctx, *irn;
+	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 */
+	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,
+	 * 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)) {
+			sched_remove(irn);
+			continue;
+		}
 
-	pmap_insert_sth(raenv->nodes, nr, blk);
+		/* all ordinary nodes must be spilled */
+		DBG((raenv->dbg, LEVEL_2, "  spilling %+F\n", irn));
+		spill = be_spill(raenv->aenv, irn);
 
-	/* begin block scope */
-	fprintf(f, "\n");
-	fprintf(f, "  block %d {\n", nr);
+		/* remember the spill */
+		pset_insert_ptr(spills, spill);
+	}
 
-	/* for each instruction */
-	for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
-		int max, i;
-		int node_nr;
+	assert(spill && "There must be at least one non-phi-node");
 
-		if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
-			continue;
+	mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
 
-		/* kind of instruction */
-		if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy)
-			fprintf(f, "    copy");
-		else if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_call)
-			fprintf(f, "    call");
-		else
-			fprintf(f, "    insn");
-
-		/* number */
-		node_nr = get_irn_node_nr(irn);
-		fprintf(f, " %ld {\n", node_nr);
-
-		pmap_insert_sth(raenv->nodes, node_nr, irn);
-
-
-		/*
-		 * print all uses
-		 */
-		fprintf(f, "      use");
-		for (i=0, max=get_irn_arity(irn); i<max; ++i) {
-			ir_node *arg = get_irn_n(irn, i);
-			if (arch_irn_has_reg_class(raenv->aenv, arg, -1, raenv->cls)) {
-				fprintf(f, " %d", get_var_info(arg)->var_nr);
-				dump_constraint(raenv, irn, i);
-			}
-		}
-		fprintf(f,"\n");
-
-		/*
-		 * print all defs
-		 */
-		fprintf(f, "      def");
-		/* special handling of projs */
-		if (get_irn_mode(irn) == mode_T) {
-			for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
-				if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
-					fprintf(f, " %d", get_var_info(irn)->var_nr);
-					dump_constraint(raenv, irn, -1);
-				}
-			irn = sched_prev(irn); /* for outer loop */
-		} else {
-			if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
-				fprintf(f, " %d", get_var_info(irn)->var_nr);
-				dump_constraint(raenv, irn, -1);
-			}
+	/* insert reloads and wire them arbitrary*/
+	pset_foreach(vi->values, irn)
+		foreach_out_edge_safe(irn, edge, ne) {
+			ir_node *reload, *src = edge->src;
+			if (is_Phi(src) || be_is_Spill(src))
+				continue;
+
+			/* all real uses must be reloaded */
+			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);
 		}
-		fprintf(f,"\n");
 
-		/* end of insn scope */
-		fprintf(f, "    }\n");
-	}
+	/* correct the reload->spill pointers... */
+	be_ssa_constr_set(raenv->dom_info, raenv->lv, spills);
 
-	/* end the block scope */
-	fprintf(f, "  }\n");
-}
 
+	/****** correct the variable <--> values mapping: ******
+	 *
+	 *  - if we had a phi class it gets split into several new variables
+	 *  - all reloads are new variables
+	 */
+	n_spills = pset_count(spills);
+	n_reloads = pset_count(reloads);
 
-/**
- * Dump all control flow edges of this irg
- */
-static void dump_edges(ir_node *blk, void *env) {
-	be_raext_env_t *raenv = env;
-	int i, max;
+	/* first make room for new pointers in the cls_var array */
+	new_size = raenv->n_cls_vars + n_reloads + ((n_spills>1) ? n_spills : 0);
+	raenv->cls_vars = realloc(raenv->cls_vars, (new_size) * sizeof(*raenv->cls_vars));
+	assert(raenv->cls_vars && "Out of mem!?");
 
-	if (get_irg_start_block(get_irn_irg(blk)) == blk)
-		return;
+	/* if we had a real phi-class, we must... */
+	if (pset_count(spills) > 1) {
+		/* ...remove the old variable corresponding to the phi class */
+		vi->var_nr = SET_REMOVED;
 
-	/* dump cf edges in the flow-order "pred succ" */
-	for (i=0, max=get_irn_arity(blk); i<max; ++i) {
-		ir_node *pred = get_Block_cfgpred_block(blk, i);
-		fprintf(raenv->f, "  cf_edge %ld %ld\n", get_irn_node_nr(pred), get_irn_node_nr(blk));
+		/* ...add new vars for each non-phi-member */
+		pset_foreach(spills, irn) {
+			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) {
+		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);
 }
 
+#define INVALID_FILE_FORMAT assert(0 && "Invalid file format.")
+#define BUFLEN 32
+#define BUFCONV " %32s "
 
 /**
- * Dump all information needed by the external
- * register allocator to a single file.
+ * Read in the actions performed by the external allocator.
+ * Apply these transformations to the irg.
+ * @return 1 if an allocation was read in. 0 otherwise.
  */
-static void dump_to_file(be_raext_env_t *raenv, char *filename) {
+static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 	FILE *f;
-	int i, reg_count;
+	char buf[BUFLEN];
+	int is_allocation = 0;
 
-	if (!(f = fopen(filename, "wt"))) {
-		fprintf(stderr, "Could not open file %s for writing\n", filename);
+	if (!(f = fopen(filename, "rt"))) {
+		fprintf(stderr, "Could not open file %s for reading\n", filename);
+		assert(0);
 		exit(0xdeadbeef);
 	}
 	raenv->f = f;
 
-	/* dump register info */
-	reg_count = arch_register_class_n_regs(raenv->cls);
-	fprintf(f, "regs %d", reg_count);
+	/* read the action */
+	if (fscanf(f, BUFCONV, buf) != 1)
+		INVALID_FILE_FORMAT;
 
-	fprintf(f, " saved-by-caller");
-	for (i=0; i<reg_count; ++i)
-		if (arch_register_type_is(arch_register_for_index(raenv->cls, i), caller_saved))
-			fprintf(f, " %d", i);
+	/* do we spill */
+	if (!strcmp(buf, "spills")) {
+		int var_nr;
+		while (fscanf(f, " %d ", &var_nr) == 1)
+			var_add_spills_and_reloads(raenv, var_nr);
+	} else
 
-	fprintf(f, " saved-by-callee");
-	for (i=0; i<reg_count; ++i)
-		if (arch_register_type_is(arch_register_for_index(raenv->cls, i), callee_saved))
-			fprintf(f, " %d", i);
+	/* or do we allocate */
+	if (!strcmp(buf, "allocs")) {
+		int var_nr, reg_nr;
 
-	fprintf(f, "\n");
+		is_allocation = 1;
+		while (fscanf(f, " %d %d ", &var_nr, &reg_nr) == 2) {
+			ir_node *irn;
+			pset *vals = be_get_var_values(raenv->vars, var_nr);
 
-	/* dump the cfg */
+			assert(vals && "Variable nr does not exist!");
+			pset_foreach(vals, irn)
+				arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, reg_nr));
+		}
+	} else
+		INVALID_FILE_FORMAT;
 
-	fprintf(f, "cfg %s {\n", filename);
-	irg_block_walk_graph(raenv->irg, NULL, dump_blocks, raenv);
-	irg_block_walk_graph(raenv->irg, NULL, dump_edges, raenv);
-	fprintf(f, "}\n");
+	if (!feof(f))
+		INVALID_FILE_FORMAT;
 
 	fclose(f);
+
+	return is_allocation;
 }
 
+static void check_allocation(be_raext_env_t *raenv) {
+	int i, o;
 
-/******************************************************************************
-    ______                     _
-   |  ____|                   | |
-   | |__  __  _____  ___ _   _| |_ ___
-   |  __| \ \/ / _ \/ __| | | | __/ _ \
-   | |____ >  <  __/ (__| |_| | ||  __/
-   |______/_/\_\___|\___|\__,_|\__\___|
- *****************************************************************************/
+	for (i=0; i<raenv->n_cls_vars; ++i) {
+		be_var_info_t *vi1 = raenv->cls_vars[i];
 
-/**
- * Execute the external register allocator specified in the
- * firm-option firm.be.ra.ext.callee
- */
-static void execute(char *prog_to_call, char *out_file, char *result_file) {
-	char cmd_line[1024];
-	int ret_status;
+		if (vi1->var_nr == SET_REMOVED)
+			continue;
 
-	snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", prog_to_call, out_file, result_file);
+		for (o=0; o<i; ++o) {
+			be_var_info_t *vi2 = raenv->cls_vars[o];
+			ir_node *irn1, *irn2;
 
-	ret_status = system(cmd_line);
-	assert(ret_status != -1 && "Invokation of external register allocator failed");
+			if (vi2->var_nr == SET_REMOVED)
+				continue;
+
+			pset_foreach(vi1->values, irn1)
+				pset_foreach(vi2->values, irn2)
+					if (values_interfere(raenv->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");
+					}
+		}
+	}
 }
 
 /******************************************************************************
@@ -829,8 +688,9 @@ static void execute(char *prog_to_call, char *out_file, char *result_file) {
 /**
  * Default values for options
  */
-static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple;
-static char callee[128] = "echo";
+static set* (*ssa_destr)(ir_graph*,const arch_env_t*) = be_ssa_destr_simple;
+static char callee[128] = "\"E:/user/kimohoff/public/register allocator\"";
+//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
 
 
 /**
@@ -842,46 +702,74 @@ 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 be_ra_timer_t *be_ra_extern_main(const be_irg_t *bi) {
+	be_main_env_t *env = bi->main_env;
+	ir_graph *irg = bi->irg;
+
+ 	be_raext_env_t raenv;
 	int clsnr, clss;
 
 	compute_doms(irg);
+	edges_assure(irg);
 
+	raenv.lv       = be_liveness(irg);
 	raenv.irg      = irg;
 	raenv.aenv     = env->arch_env;
 	raenv.dom_info = be_compute_dominance_frontiers(irg);
-	raenv.vars     = new_set(compare_var_infos, 64);
-	raenv.nodes    = pmap_create();
-	/* SSA destruction */
-	ssa_destr(&raenv);
+	FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern");
+
+	/* Insert copies for constraints */
+	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);
+	}
 
-	be_clear_links(irg);
-	phi_class_compute(irg);
-	irg_walk_graph(irg, values_to_vars, NULL, &raenv);
+	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);
 
-	dump_ir_block_graph_sched(irg, "-extern-ssadestr");
 
 	/* For all register classes */
 	for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
+		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);
 
-		dump_to_file(&raenv, out);
+		extract_vars_of_cls(&raenv);
+
+		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(bi->abi, raenv.lv);
 
-		execute(callee, out, in);
+			ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round);
+			be_dump(irg, in, dump_ir_block_graph_sched);
 
-		read_and_apply_results(&raenv, in);
+			round++;
+		} while (!done);
+
+		check_allocation(&raenv);
+
+		free(raenv.cls_vars);
 	}
 
+	be_dump(irg, "-extern-alloc", dump_ir_block_graph_sched);
+
 	/* Clean up */
-	pmap_destroy(raenv.nodes);
-	del_set(raenv.vars);
+	free_ssa_destr_simple(raenv.vars);
 	be_free_dominance_frontiers(raenv.dom_info);
+	be_liveness_free(raenv.lv);
 
+	return NULL;
 }
 
 /******************************************************************************
@@ -897,14 +785,14 @@ 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 (*)()) 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 lc_opt_enum_func_ptr_var_t ssa_destr_var = {
+	 (int (**)()) &ssa_destr, ssa_destr_items
 };
 
 static const lc_opt_table_entry_t be_ra_extern_options[] = {