From b267d8d2e4100aa20cc3771b1b8558d9e0302ed1 Mon Sep 17 00:00:00 2001
From: Sebastian Hack <hack@ipd.info.uni-karlsruhe.de>
Date: Tue, 16 Aug 2005 11:52:40 +0000
Subject: [PATCH] Misc changes Added ILP spilling

---
 ir/be/Makefile.in   |   2 +-
 ir/be/bearch.c      |  12 +
 ir/be/bearch.h      |  25 ++
 ir/be/bearch_firm.c |  85 +++---
 ir/be/bechordal.c   |  70 ++++-
 ir/be/bechordal_t.h |   8 +
 ir/be/beirgmod.c    | 272 +++++++-----------
 ir/be/beirgmod.h    |   4 +-
 ir/be/belive.c      |  45 ++-
 ir/be/belive.h      |   3 +-
 ir/be/bemain.c      |  42 ++-
 ir/be/benode.c      | 173 +++++-------
 ir/be/benode_t.h    |  12 +-
 ir/be/bespillilp.c  | 672 ++++++++++++++++++++++++++++++++++++++++++++
 ir/be/bespillilp.h  |  20 ++
 15 files changed, 1100 insertions(+), 345 deletions(-)
 create mode 100644 ir/be/bespillilp.c
 create mode 100644 ir/be/bespillilp.h

diff --git a/ir/be/Makefile.in b/ir/be/Makefile.in
index 9197cb3b3..621aa98b7 100644
--- a/ir/be/Makefile.in
+++ b/ir/be/Makefile.in
@@ -26,7 +26,7 @@ SOURCES += 	Makefile.in besched.h belistsched.h belistsched.c \
 	becopyoptmain.c becopyopt.c becopyheur.c \
 	becopyilp.c becopystat.c bearch_firm.c bearch.c bechordal_draw.c \
 	bechordal_draw.h beirgmod.c beirgmod.h benode.c benode_t.h \
-	bessadestr.c beifg.c
+	bessadestr.c beifg.c bespillilp.c
 
 include $(topdir)/MakeRules
 
diff --git a/ir/be/bearch.c b/ir/be/bearch.c
index 26adb9716..7d7cd0f17 100644
--- a/ir/be/bearch.c
+++ b/ir/be/bearch.c
@@ -105,6 +105,12 @@ int arch_get_allocatable_regs(const arch_env_t *env, const ir_node *irn,
   return 0;
 }
 
+int arch_get_n_operands(const arch_env_t *env, const ir_node *irn, int in_out)
+{
+  const arch_irn_ops_t *ops = get_irn_ops(env, irn);
+	return ops->get_n_operands(ops, irn, in_out);
+}
+
 int arch_is_register_operand(const arch_env_t *env,
     const ir_node *irn, int pos)
 {
@@ -168,3 +174,9 @@ extern arch_irn_class_t arch_irn_classify(const arch_env_t *env, const ir_node *
   const arch_irn_ops_t *ops = get_irn_ops(env, irn);
   return ops->classify(ops, irn);
 }
+
+extern arch_irn_flags_t arch_irn_get_flags(const arch_env_t *env, const ir_node *irn)
+{
+  const arch_irn_ops_t *ops = get_irn_ops(env, irn);
+  return ops->get_flags(ops, irn);
+}
diff --git a/ir/be/bearch.h b/ir/be/bearch.h
index 122ce485f..5d0226769 100644
--- a/ir/be/bearch.h
+++ b/ir/be/bearch.h
@@ -196,6 +196,13 @@ typedef enum _arch_irn_class_t {
   arch_irn_class_branch
 } arch_irn_class_t;
 
+/**
+ * Some flags describing a node in more detail.
+ */
+typedef enum _arch_irn_flags_t {
+	arch_irn_flags_spillable = 1,
+	arch_irn_flags_rematerializable = 2
+} arch_irn_flags_t;
 
 /*
  * Some words about positions and indices:
@@ -305,9 +312,19 @@ struct _arch_irn_ops_t {
    */
   arch_irn_class_t (*classify)(const arch_irn_ops_t *self, const ir_node *irn);
 
+	/**
+	 * Get the flags of a node.
+	 * @param self The irn ops themselves.
+	 * @param irn The node.
+	 * @return A set of flags.
+	 */
+	arch_irn_flags_t (*get_flags)(const arch_irn_ops_t *self, const ir_node *irn);
 
 };
 
+extern int
+arch_get_n_operands(const arch_env_t *env, const ir_node *irm, int in_out);
+
 /**
  * Get the register requirements for a node.
  * @param env The architecture environment.
@@ -400,6 +417,14 @@ extern void arch_set_irn_register(const arch_env_t *env,
  */
 extern arch_irn_class_t arch_irn_classify(const arch_env_t *env, const ir_node *irn);
 
+/**
+ * Get the flags of a node.
+ * @param env The architecture environment.
+ * @param irn The node.
+ * @return The flags.
+ */
+extern arch_irn_flags_t arch_irn_get_flags(const arch_env_t *env, const ir_node *irn);
+
 #define arch_irn_has_reg_class(env, irn, pos, cls) \
   ((cls) == arch_get_irn_reg_class(env, irn, pos))
 
diff --git a/ir/be/bearch_firm.c b/ir/be/bearch_firm.c
index 7ee7165b1..21747f3b7 100644
--- a/ir/be/bearch_firm.c
+++ b/ir/be/bearch_firm.c
@@ -21,7 +21,7 @@
 
 #include "irreflect.h"
 
-#define N_REGS 512
+#define N_REGS 6
 
 static arch_register_t datab_regs[N_REGS];
 
@@ -29,10 +29,8 @@ static arch_register_class_t reg_classes[] = {
   { "datab", N_REGS, datab_regs },
 };
 
-static ir_op *op_push_end;
 static ir_op *op_push;
 static ir_op *op_imm;
-static type *push_type;
 
 typedef struct {
 	enum { imm_Const, imm_SymConst } tp;
@@ -83,14 +81,21 @@ static void firm_init(void)
 	 * Create some opcodes and types to let firm look a little
 	 * bit more like real machines.
 	 */
-	if(!op_push_end) {
-		op_push_end = new_ir_op(get_next_ir_opcode(), "PushEnd",
-				op_pin_state_pinned, 0, oparity_unary, 0, 0);
-	}
-
 	if(!op_push) {
-		op_push = new_ir_op(get_next_ir_opcode(), "Push",
+		rflct_sig_t *sig;
+		int push_opc = get_next_ir_opcode();
+
+		op_push = new_ir_op(push_opc, "Push",
 				op_pin_state_pinned, 0, oparity_binary, 0, 0);
+
+		sig = rflct_signature_allocate(1, 3);
+		rflct_signature_set_arg(sig, 0, 0, "Store", RFLCT_MC(Mem), 0, 0);
+		rflct_signature_set_arg(sig, 1, 0, "Block", RFLCT_MC(BB), 0, 0);
+		rflct_signature_set_arg(sig, 1, 1, "Store", RFLCT_MC(Mem), 0, 0);
+		rflct_signature_set_arg(sig, 1, 2, "Arg", RFLCT_MC(Datab), 0, 0);
+
+		rflct_new_opcode(push_opc, "Push", false);
+		rflct_opcode_add_signature(push_opc, sig);
 	}
 
 	if(!op_imm) {
@@ -98,9 +103,6 @@ static void firm_init(void)
 				op_pin_state_pinned, 0, oparity_zero, 0, sizeof(imm_attr_t));
 	}
 
-	if(!push_type)
-		push_type = new_type_pointer(new_id_from_str("push_ptr"), get_glob_type());
-
 }
 
 static int firm_get_n_reg_class(void)
@@ -142,7 +144,12 @@ firm_get_irn_reg_req(const arch_irn_ops_t *self,
 
 static int firm_get_n_operands(const arch_irn_ops_t *self, const ir_node *irn, int in_out)
 {
-  int sig = rflct_get_signature(irn);
+  int sig;
+
+	while(is_Proj(irn))
+		irn = get_Proj_pred(irn);
+
+	sig = rflct_get_signature(irn);
   return rflct_get_args_count(get_irn_opcode(irn), sig, in_out >= 0);
 }
 
@@ -207,12 +214,38 @@ static arch_irn_class_t firm_classify(const arch_irn_ops_t *self, const ir_node
 	return res;
 }
 
+static arch_irn_flags_t firm_get_flags(const arch_irn_ops_t *self, const ir_node *irn)
+{
+	arch_irn_flags_t res = arch_irn_flags_spillable;
+
+	if(get_irn_op(irn) == op_imm)
+		res |= arch_irn_flags_rematerializable;
+
+	switch(get_irn_opcode(irn)) {
+		case iro_Add:
+		case iro_Sub:
+		case iro_Shl:
+		case iro_Shr:
+		case iro_Shrs:
+		case iro_And:
+		case iro_Or:
+		case iro_Eor:
+		case iro_Not:
+			res |= arch_irn_flags_rematerializable;
+		default:
+			res = res;
+	}
+
+	return res;
+}
+
 static const arch_irn_ops_t irn_ops = {
   firm_get_irn_reg_req,
   firm_get_n_operands,
   firm_set_irn_reg,
   firm_get_irn_reg,
-  firm_classify
+  firm_classify,
+	firm_get_flags
 };
 
 static const arch_irn_ops_t *firm_get_irn_ops(const arch_irn_handler_t *self,
@@ -225,19 +258,12 @@ const arch_irn_handler_t firm_irn_handler = {
   firm_get_irn_ops,
 };
 
-static ir_node *new_PushEnd(ir_graph *irg, ir_node *bl, ir_node *arg)
-{
-	ir_node *ins[1];
-	ins[0] = arg;
-	return new_ir_node(NULL, irg, bl, op_push_end, mode_P, 1, ins);
-}
-
 static ir_node *new_Push(ir_graph *irg, ir_node *bl, ir_node *push, ir_node *arg)
 {
 	ir_node *ins[2];
 	ins[0] = push;
 	ins[1] = arg;
-	return new_ir_node(NULL, irg, bl, op_push, mode_P, 2, ins);
+	return new_ir_node(NULL, irg, bl, op_push, mode_M, 2, ins);
 }
 
 static ir_node *new_Imm(ir_graph *irg, ir_node *bl, ir_node *cnst)
@@ -274,42 +300,38 @@ static void prepare_walker(ir_node *irn, void *data)
 		ir_node *bl   = get_nodes_block(irn);
 		ir_graph *irg = get_irn_irg(bl);
 
-		ir_node *ins[1];
 		ir_node *store   = get_Call_mem(irn);
 		ir_node *ptr     = get_Call_ptr(irn);
 		type *ct         = get_Call_type(irn);
 		int np           = get_Call_n_params(irn) > 0 ? 1 : 0;
 
 		if(np > 0) {
+			ir_node *ins[1];
 			char buf[128];
 			ir_node *nc;
 			ir_node *push;
 			int i, n;
 			type *nt;
 
-			push = new_PushEnd(irg, bl, get_Call_param(irn, 0));
+			store = new_Push(irg, bl, store, get_Call_param(irn, 0));
 
 			for(i = 1, n = get_Call_n_params(irn); i < n; ++i) {
-				push = new_Push(irg, bl, push, get_Call_param(irn, i));
+				store = new_Push(irg, bl, store, get_Call_param(irn, i));
 			}
 
 			snprintf(buf, sizeof(buf), "push_%s", get_type_name(ct));
 
 			n = get_method_n_ress(ct);
-			nt = new_type_method(new_id_from_str(buf), 1, n);
+			nt = new_type_method(new_id_from_str(buf), 0, n);
 			for(i = 0; i < n; ++i)
 				set_method_res_type(nt, i, get_method_res_type(ct, i));
 
-			set_method_param_type(nt, 0, push_type);
-
-			ins[0] = push;
-			nc = new_r_Call(irg, bl, store, ptr, 1, ins, nt);
+			nc = new_r_Call(irg, bl, store, ptr, 0, ins, nt);
 			exchange(irn, nc);
 			set_irn_link(nc, nc);
 		}
 	}
 
-#if 0
 	else if(opc == iro_Const || opc == iro_SymConst) {
 		ir_node *bl   = get_nodes_block(irn);
 		ir_graph *irg = get_irn_irg(bl);
@@ -318,7 +340,6 @@ static void prepare_walker(ir_node *irn, void *data)
 		exchange(irn, imm);
 		set_irn_link(imm, imm);
 	}
-#endif
 
 }
 
diff --git a/ir/be/bechordal.c b/ir/be/bechordal.c
index 9af202217..d1fb81f00 100644
--- a/ir/be/bechordal.c
+++ b/ir/be/bechordal.c
@@ -259,7 +259,8 @@ static INLINE border_t *border_add(be_chordal_env_t *env, struct list_head *head
 
 static INLINE int has_reg_class(const be_chordal_env_t *env, const ir_node *irn)
 {
-  return arch_irn_has_reg_class(env->session_env->main_env->arch_env, irn, arch_pos_make_out(0), env->cls);
+  return arch_irn_has_reg_class(env->session_env->main_env->arch_env,
+			irn, arch_pos_make_out(0), env->cls);
 }
 
 /**
@@ -303,10 +304,11 @@ static void pressure(ir_node *block, void *env_ptr)
 	 * They are necessary to build up real intervals.
 	 */
 	for(irn = pset_first(live_end); irn; irn = pset_next(live_end)) {
-		DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
-		bitset_set(live, get_irn_graph_nr(irn));
-		if(has_reg_class(env, irn))
+		if(has_reg_class(env, irn)) {
+			DBG((dbg, LEVEL_3, "\tMaking live: %+F/%d\n", irn, get_irn_graph_nr(irn)));
+			bitset_set(live, get_irn_graph_nr(irn));
 			border_use(irn, step, 0);
+		}
 	}
 	++step;
 
@@ -618,3 +620,63 @@ set *be_ra_get_ifg_nodes(const be_chordal_env_t *env) {
 }
 
 #endif
+
+typedef struct {
+	const be_main_session_env_t *env;
+	const arch_register_class_t *cls;
+} check_pressure_info_t;
+
+
+static int check_pressure_has_class(const check_pressure_info_t *i, const ir_node *irn)
+{
+  return arch_irn_has_reg_class(i->env->main_env->arch_env,
+      irn, arch_pos_make_out(0), i->cls);
+}
+
+static void check_pressure_walker(ir_node *bl, void *data)
+{
+	check_pressure_info_t *info = data;
+	int n_regs = arch_register_class_n_regs(info->cls);
+
+	pset *live = pset_new_ptr_default();
+	int step = 0;
+	ir_node *irn;
+  irn_live_t *li;
+
+  live_foreach(bl, li) {
+    if(live_is_end(li) && check_pressure_has_class(info, li->irn)) {
+      ir_node *irn = (ir_node *) li->irn;
+      pset_insert_ptr(live, irn);
+    }
+  }
+
+	sched_foreach_reverse(bl, irn) {
+		int i, n;
+		int pressure = pset_count(live);
+
+		if(pressure > n_regs) {
+			ir_node *x;
+			ir_printf("%+10F@%+10F: pressure to high: %d\n", bl, irn, pressure);
+			for(x = pset_first(live); x; x = pset_next(live))
+				ir_printf("\t%+10F\n", x);
+		}
+
+		if(check_pressure_has_class(info, irn))
+			pset_remove_ptr(live, irn);
+
+		for(i = 0, n = get_irn_arity(irn); i < n; i++) {
+			ir_node *op = get_irn_n(irn, i);
+			if(check_pressure_has_class(info, op) && !is_Phi(irn))
+				pset_insert_ptr(live, op);
+		}
+		step++;
+	}
+}
+
+void be_check_pressure(const be_main_session_env_t *env, const arch_register_class_t *cls)
+{
+	check_pressure_info_t i;
+	i.env = env;
+	i.cls = cls;
+	irg_block_walk_graph(env->irg, check_pressure_walker, NULL, &i);
+}
diff --git a/ir/be/bechordal_t.h b/ir/be/bechordal_t.h
index 684e60f41..35317c69a 100644
--- a/ir/be/bechordal_t.h
+++ b/ir/be/bechordal_t.h
@@ -131,4 +131,12 @@ void be_ra_chordal_done(be_chordal_env_t *info);
  */
 void be_ra_chordal_init(void);
 
+/**
+ * Check the register pressure in a graph.
+ * @param env The sesion env.
+ * @param cls The register class to consider.
+ */
+void be_check_pressure(const be_main_session_env_t *env, const arch_register_class_t *cls);
+
+
 #endif /* _BECHORDAL_T_H */
diff --git a/ir/be/beirgmod.c b/ir/be/beirgmod.c
index 07ff6c390..e3b662df4 100644
--- a/ir/be/beirgmod.c
+++ b/ir/be/beirgmod.c
@@ -25,11 +25,12 @@
 #include "besched_t.h"
 #include "belive_t.h"
 #include "benode_t.h"
+#include "beutil.h"
 
 #include "beirgmod.h"
 
 #define DBG_MODULE firm_dbg_register("firm.be.irgmod")
-#define DBG_LEVEL 0 //SET_LEVEL_4
+#define DBG_LEVEL 0 // SET_LEVEL_4
 
 struct _dom_front_info_t {
   pmap *df_map;
@@ -49,66 +50,9 @@ static INLINE ir_node *get_idom(ir_node *bl)
   return idom == NULL ? bl : idom;
 }
 
-static void compute_df_local(ir_node *bl, void *data)
-{
-  pmap *df_map = ((dom_front_info_t *) data)->df_map;
-  ir_node *idom = get_Block_idom(bl);
-  pset *df = pmap_get(df_map, bl);
-  int i, n;
-
-  /*
-   * In the case that the immediate dominator is NULL, the
-   * block is the start block and its immediate dominator
-   * must be itself, else it is inserted into its own
-   * dominance frontier.
-   */
-  if(idom == NULL)
-  	idom = bl;
-
-  /*
-   * Create a new dom frot set for this node,
-   * if none exists.
-   */
-  if(!df)
-  	pmap_insert(df_map, bl, pset_new_ptr(16));
-
-  for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
-
-    /* The predecessor block */
-    ir_node *pred = get_nodes_block(get_irn_n(bl, i));
-
-    /* The dominance frontier set of the predecessor. */
-    pset *df = pmap_get(df_map, pred);
-	  if(!df) {
-	  	df = pset_new_ptr(16);
-	  	pmap_insert(df_map, pred, df);
-	  }
-
-    assert(df && "dom front set must have been created for this node");
-
-    if(pred != idom && bl)
-      pset_insert_ptr(df, bl);
-  }
-}
-
-static void compute_df_up(ir_node *bl, void *data)
-{
-  pmap *df_map = ((dom_front_info_t *) data)->df_map;
-  ir_node *y;
-
-  for(y = get_Block_dominated_first(bl); y; y = get_Block_dominated_next(y)) {
-    ir_node *w;
-    pset *df = pmap_get(df_map, y);
-
-    for(w = pset_first(df); w; w = pset_next(df))
-      if(!block_dominates(bl, w) || bl == w)
-        pset_insert_ptr(df, w);
-  }
-}
-
 static void compute_df(ir_node *n, pmap *df_map)
 {
-  ir_node *y, *c;
+  ir_node *c;
   const ir_edge_t *edge;
   pset *df = pset_new_ptr_default();
 
@@ -133,7 +77,7 @@ static void compute_df(ir_node *n, pmap *df_map)
     df_c = pmap_get(df_map, c);
 
     for(w = pset_first(df_c); w; w = pset_next(df_c)) {
-      if(!block_dominates(n, w))
+      if(get_idom(w) != n)
         pset_insert_ptr(df, w);
     }
   }
@@ -150,14 +94,6 @@ dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
   info->df_map = pmap_create();
   compute_df(get_irg_start_block(irg), info->df_map);
 
-#if 0
-  /*
-   * This must be called as a post walker, since the dom front sets
-   * of all predecessors must be created when a block is reached.
-   */
-  dom_tree_walk_irg(irg, NULL, compute_df_local, info);
-  dom_tree_walk_irg(irg, NULL, compute_df_up, info);
-#endif
   return info;
 }
 
@@ -177,57 +113,22 @@ pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
   return pmap_get(info->df_map, block);
 }
 
-/**
- * Algorithm to place the Phi-Functions.
- * @see Appel, Modern Compiler Implementation in Java, 2nd ed., p. 399ff
- *
- * This function takes an original node and a set of already placed
- * copies of that node called @p copies. It places phi nodes at the
- * iterated dominance frontiers of these copies and puts these phi nodes
- * in the @p copies set, since they are another form of copies of the
- * original value.
- *
- * The rename phase (see below) is responsible for fixing up the usages
- * of the original node.
- *
- * @param orig The original node.
- * @param copies A set contianing nodes representing a copy of the
- * original node. Each node must be inserted into the block's schedule.
- * @param copy_blocks A set in which the blocks are recorded which
- * contain a copy. This is just for efficiency in later phases (see
- * rename).
- */
-static void place_phi_functions(ir_node *orig, pset *copies,
-    pset *copy_blocks, dom_front_info_t *df_info)
+static void determine_phi_blocks(ir_node *orig, pset *copies,
+    pset *copy_blocks, pset *phi_blocks, dom_front_info_t *df_info)
 {
-  int i;
-  ir_node *orig_block = get_nodes_block(orig);
-  ir_graph *irg = get_irn_irg(orig);
-  ir_mode *mode = get_irn_mode(orig);
+	ir_node *bl;
+	ir_node *orig_block = get_nodes_block(orig);
   pdeq *worklist = new_pdeq();
-  pset *phi_blocks = pset_new_ptr(8);
-  ir_node **ins = NULL;
-  void *it;
   firm_dbg_module_t *dbg = DBG_MODULE;
 
-  /*
-   * Allocate an array for all blocks where the copies and the original
-   * value were defined.
-   */
-  int n_orig_blocks = pset_count(copy_blocks);
-  ir_node **orig_blocks = malloc(n_orig_blocks * sizeof(orig_blocks[0]));
-
   /*
    * Fill the worklist queue and the rest of the orig blocks array.
    */
-  for(it = pset_first(copy_blocks), i = 0; it; it = pset_next(copy_blocks)) {
-    ir_node *copy_block = it;
-
-   	assert(block_dominates(orig_block, copy_block)
+  for(bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) {
+   	assert(block_dominates(orig_block, bl)
        	&& "The block of the copy must be dominated by the block of the value");
 
-    pdeq_putr(worklist, copy_block);
-    orig_blocks[i++] = copy_block;
+    pdeq_putr(worklist, bl);
   }
 
   while(!pdeq_empty(worklist)) {
@@ -240,67 +141,24 @@ static void place_phi_functions(ir_node *orig, pset *copies,
 	    DBG((dbg, LEVEL_3, "\t%+F\n", y));
 
     for(y = pset_first(df); y; y = pset_next(df)) {
-      int n_preds = get_irn_arity(y);
-
       if(!pset_find_ptr(phi_blocks, y)) {
-        ir_node *phi;
-        int insert = 1;
-
-        /*
-         * Set the orig node as the only operand of the
-         * phi node.
-         */
-        ins = realloc(ins, n_preds * sizeof(ins[0]));
-        for(i = 0; i < n_preds; ++i)
-          ins[i] = orig;
-
-        /* Insert phi node */
-        phi = new_r_Phi(irg, y, n_preds, ins, mode);
-        DBG((dbg, LEVEL_2, "    inserting phi %+F with %d args in block %+F\n",
-              phi, n_preds, y));
-
-        /*
-         * The phi node itself is also a copy of the original
-         * value. So put it in the copies set also, so that
-         * the rename phase can treat them right.
-         */
-        pset_insert_ptr(copies, phi);
-        pset_insert_ptr(copy_blocks, y);
-
-        /*
-         * Insert the phi node into the schedule if it
-         * can occur there (PhiM's are not to put into a schedule.
-         */
-        if(to_appear_in_schedule(phi))
-          sched_add_before(sched_first(y), phi);
-
-        /* Insert the phi node in the phi blocks set. */
         pset_insert_ptr(phi_blocks, y);
 
-        /*
-         * If orig or a copy of it were not defined in y,
-         * add y to the worklist.
-         */
-        for(i = 0; i < n_orig_blocks; ++i)
-          if(orig_blocks[i] == y) {
-            insert = 0;
-            break;
-          }
+				/*
+				 * Clear the link field of a possible phi block, since
+				 * the possibly created phi will be stored there. See,
+				 * search_def()
+				 */
+				set_irn_link(y, NULL);
 
-        if(insert)
-          pdeq_putr(worklist, y);
+				if(!pset_find_ptr(copy_blocks, y))
+					pdeq_putr(worklist, y);
 
       }
     }
   }
 
-  del_pset(phi_blocks);
   del_pdeq(worklist);
-
-  free(orig_blocks);
-
-  if(ins)
-    free(ins);
 }
 
 /**
@@ -323,12 +181,12 @@ static void place_phi_functions(ir_node *orig, pset *copies,
  * original node.
  * @return The valid copy for usage.
  */
-static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks)
+static ir_node *search_def(ir_node *usage, int pos, pset *copies,
+		pset *copy_blocks, pset *phi_blocks, ir_mode *mode)
 {
   ir_node *curr_bl;
   ir_node *start_irn;
   firm_dbg_module_t *dbg = DBG_MODULE;
-  firm_dbg_set_mask(dbg, DBG_LEVEL);
 
   curr_bl = get_nodes_block(usage);
 
@@ -359,7 +217,7 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
       ir_node *irn;
 
       /* Look at each instruction from last to first. */
-      for(irn = start_irn; !is_Block(irn); irn = sched_prev(irn)) {
+			sched_foreach_reverse_from(start_irn, irn) {
 
         /* Take the first copy we find. */
         if(pset_find_ptr(copies, irn))
@@ -367,6 +225,34 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
       }
     }
 
+		else if(pset_find_ptr(phi_blocks, curr_bl)) {
+			ir_node *phi = get_irn_link(curr_bl);
+
+			if(!phi) {
+				int i, n_preds = get_irn_arity(curr_bl);
+				ir_graph *irg = get_irn_irg(curr_bl);
+				ir_node **ins = malloc(n_preds * sizeof(ins[0]));
+
+				for(i = 0; i < n_preds; ++i)
+					ins[i] = new_r_Unknown(irg, mode);
+
+				phi = new_r_Phi(irg, curr_bl, n_preds, ins, mode);
+				DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
+
+				set_irn_link(curr_bl, phi);
+				sched_add_after(curr_bl, phi);
+				free(ins);
+
+				for(i = 0; i < n_preds; ++i) {
+					ir_node *arg = search_def(phi, i, copies, copy_blocks, phi_blocks, mode);
+					DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
+					set_irn_n(phi, i, arg);
+				}
+			}
+
+			return phi;
+		}
+
     /* If were not done yet, look in the immediate dominator */
     curr_bl = get_Block_idom(curr_bl);
     if(curr_bl)
@@ -376,11 +262,14 @@ static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blo
   return NULL;
 }
 
-static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
+static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks,
+		pset *phi_blocks, pset *ignore_uses)
 {
   int i = 0;
   int n_outs = 0;
   const ir_edge_t *edge;
+	ir_mode *mode = get_irn_mode(orig);
+
   firm_dbg_module_t *dbg = DBG_MODULE;
 
   struct {
@@ -390,7 +279,7 @@ static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
 
   /* Count the number of outs. */
   foreach_out_edge(orig, edge)
-    n_outs++;
+    n_outs += !pset_find_ptr(ignore_uses, get_edge_src_irn(edge));
 
   /*
    * Put all outs into an array.
@@ -399,9 +288,11 @@ static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
    */
   outs = malloc(n_outs * sizeof(outs[0]));
   foreach_out_edge(orig, edge) {
-    outs[i].irn = get_edge_src_irn(edge);
-    outs[i].pos = get_edge_src_pos(edge);
-    i += 1;
+		if(!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) {
+			outs[i].irn = get_edge_src_irn(edge);
+			outs[i].pos = get_edge_src_pos(edge);
+			i += 1;
+		}
   }
 
   /*
@@ -412,7 +303,7 @@ static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
     ir_node *irn = outs[i].irn;
     int pos = outs[i].pos;
 
-    def = search_def(irn, pos, copies, copy_blocks);
+    def = search_def(irn, pos, copies, copy_blocks, phi_blocks, mode);
     DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
 
     if(def != NULL)
@@ -432,7 +323,7 @@ static void fix_usages(ir_node *orig, pset *copies, pset *copy_blocks)
  *
  * @param copies The set of all copies made (including the phi functions).
  */
-static void remove_odd_phis(pset *copies)
+static void remove_odd_phis(pset *copies, pset *unused_copies)
 {
   ir_node *irn;
 
@@ -443,23 +334,39 @@ static void remove_odd_phis(pset *copies)
 
       assert(sched_is_scheduled(irn) && "phi must be scheduled");
       for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
-        illegal = is_Bad(get_irn_n(irn, i));
+        illegal = get_irn_n(irn, i) == NULL;
 
       if(illegal)
         sched_remove(irn);
     }
   }
+
+  for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
+		sched_remove(irn);
+	}
 }
 
-void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *copy_nodes[])
+void be_introduce_copies_ignore(dom_front_info_t *info, ir_node *orig,
+		int n, ir_node *copy_nodes[], pset *ignore_uses)
 {
   pset *copies = pset_new_ptr(2 * n);
   pset *copy_blocks = pset_new_ptr(2 * n);
+	pset *phi_blocks = pset_new_ptr(2 * n);
   int save_optimize = get_optimize();
   int save_normalize = get_opt_normalize();
   firm_dbg_module_t *dbg = DBG_MODULE;
   int i;
 
+#if 0
+	{
+		static int ser = 0;
+		char buf[128];
+
+		snprintf(buf, sizeof(buf), "-post-%d", ser++);
+		dump_ir_block_graph_sched(get_irn_irg(orig), buf);
+	}
+#endif
+
   firm_dbg_set_mask(dbg, DBG_LEVEL);
   DBG((dbg, LEVEL_1, "Introducing following copies of %+F\n", orig));
 
@@ -488,14 +395,27 @@ void be_introduce_copies(dom_front_info_t *info, ir_node *orig, int n, ir_node *
   /*
    * Place the phi functions and reroute the usages.
    */
-  place_phi_functions(orig, copies, copy_blocks, info);
-  fix_usages(orig, copies, copy_blocks);
-  remove_odd_phis(copies);
+  determine_phi_blocks(orig, copies, copy_blocks, phi_blocks, info);
+  fix_usages(orig, copies, copy_blocks, phi_blocks, ignore_uses);
 
   /* reset the optimizations */
   set_optimize(save_optimize);
   set_opt_normalize(save_normalize);
 
   del_pset(copies);
+  del_pset(phi_blocks);
   del_pset(copy_blocks);
+
+
+}
+
+void be_introduce_copies(dom_front_info_t *info, ir_node *orig,
+		int n, ir_node *copy_nodes[])
+{
+	static pset *empty_set = NULL;
+
+	if(!empty_set)
+		empty_set = pset_new_ptr_default();
+
+	be_introduce_copies_ignore(info, orig, n, copy_nodes, empty_set);
 }
diff --git a/ir/be/beirgmod.h b/ir/be/beirgmod.h
index 15b7de7bf..498e30d81 100644
--- a/ir/be/beirgmod.h
+++ b/ir/be/beirgmod.h
@@ -55,7 +55,9 @@ void be_free_dominance_frontiers(dom_front_info_t *info);
  * @param n			The number of copies ypu introduce.
  * @param copies	An array of nodes which are copies of @p orig.
  */
+void be_introduce_copies_ignore(dom_front_info_t *info, ir_node *orig,
+    int n, ir_node *copies[], pset *irgore_uses);
+
 void be_introduce_copies(dom_front_info_t *info, ir_node *orig,
     int n, ir_node *copies[]);
-
 #endif
diff --git a/ir/be/belive.c b/ir/be/belive.c
index ae6940a3d..98d98f301 100644
--- a/ir/be/belive.c
+++ b/ir/be/belive.c
@@ -73,7 +73,7 @@ static void live_end_at_block(ir_node *def, ir_node *block,
       mark_live_in(block, def);
 
       for(i = 0, n = get_irn_arity(block); i < n; ++i)
-        live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1);
+        live_end_at_block(def, get_Block_cfgpred_block(block, i), visited, 1);
     }
 
   }
@@ -120,17 +120,8 @@ static void liveness_for_node(ir_node *irn, void *env)
      * value as live out of that block.
      */
     if(is_Phi(use)) {
-      int i, n;
-
-      /* Mark the node as a phi operand, since a use by a phi was found. */
-      /* get_node_live_info(irn)->is_phi_op = 1; */
-
-      for(i = 0, n = get_irn_arity(use); i < n; ++i) {
-        if(get_irn_n(use, i) == irn) {
-          ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
-          live_end_at_block(irn, pred_block, visited, 0);
-        }
-      }
+			ir_node *pred_block = get_Block_cfgpred_block(use_block, edge->pos);
+			live_end_at_block(irn, pred_block, visited, 0);
     }
 
     /*
@@ -166,6 +157,36 @@ void be_liveness(ir_graph *irg)
   if(live_info->live)
     del_set(live_info->live);
 
+	ir_fprintf(stderr, "%F\n", irg);
+
   live_info->live = new_set(cmp_irn_live, 8192);
   irg_walk_graph(irg, liveness_for_node, NULL, NULL);
 }
+
+static void dump_liveness_walker(ir_node *bl, void *data)
+{
+	FILE *f = data;
+	const irn_live_t *li;
+	char buf[64];
+
+	ir_fprintf(f, "%+F\n", bl);
+	live_foreach(bl, li) {
+		strcpy(buf, "");
+
+		if(live_is_in(li))
+			strcat(buf, "in ");
+
+		if(live_is_end(li))
+			strcat(buf, "end ");
+
+		if(live_is_out(li))
+			strcat(buf, "out ");
+
+		ir_fprintf(f, "\t%+20F %s\n", li->irn, buf);
+	}
+}
+
+void be_liveness_dump(ir_graph *irg, FILE *f)
+{
+	irg_block_walk_graph(irg, dump_liveness_walker, NULL, f);
+}
diff --git a/ir/be/belive.h b/ir/be/belive.h
index fcc126808..cf9c6fb1f 100644
--- a/ir/be/belive.h
+++ b/ir/be/belive.h
@@ -20,7 +20,7 @@ void be_liveness(ir_graph *irg);
  * @param f The output.
  * @param irg The graph.
  */
-void be_liveness_dump(FILE *f, ir_graph *irg);
+void be_liveness_dump(ir_graph *irg, FILE *f);
 
 /**
  * Check, if a node is live in at a block.
@@ -46,4 +46,5 @@ int (is_live_out)(const ir_node *block, const ir_node *irn);
  */
 int (is_live_end)(const ir_node *block, const ir_node *irn);
 
+
 #endif
diff --git a/ir/be/bemain.c b/ir/be/bemain.c
index 213f926e7..b5a35be34 100644
--- a/ir/be/bemain.c
+++ b/ir/be/bemain.c
@@ -8,6 +8,7 @@
 #endif
 
 #include <stdarg.h>
+#include <mcheck.h>
 
 #include "obst.h"
 #include "bitset.h"
@@ -36,7 +37,7 @@
 #include "bearch_firm.h"
 #include "benode_t.h"
 #include "beirgmod.h"
-//#include "bespillilp.h"
+#include "bespillilp.h"
 
 #include "beasm_dump_globals.h"
 #include "beasm_asm_gnu.h"
@@ -90,13 +91,12 @@ be_init_session_env(be_main_session_env_t *env,
 
 static void prepare_graph(be_main_session_env_t *s)
 {
-	/*
-	 * Duplicate consts in each block
-	 * (This is just for the firm dummy backend)
-	 */
-	// localize_consts(s->irg);
+	/* set the current graph (this is important for several firm functions) */
 	current_ir_graph = s->irg;
 
+	/* Let the isa prepare the graph. */
+	s->main_env->arch_env->isa->prepare_graph(s->irg);
+
 	/* Remove critical edges */
 	remove_critical_cf_edges(s->irg);
 
@@ -108,7 +108,7 @@ static void prepare_graph(be_main_session_env_t *s)
 	s->dom_front = be_compute_dominance_frontiers(s->irg);
 
 	/* Ensure, that the ir_edges are computed. */
-	edges_assure(s->irg);
+	edges_activate(s->irg);
 
 	/* Compute loop nesting information (for weighting copies) */
 	if (get_irg_loopinfo_state(s->irg) != (loopinfo_valid & loopinfo_cf_consistent))
@@ -162,28 +162,44 @@ static void be_main_loop(void)
 
 			DBG((env.dbg, LEVEL_1, "----> Reg class: %s\n", cls->name));
 
-			be_numbering(irg);
-			be_liveness(irg);
+      be_spill_ilp(&session, cls);
+			dump_ir_block_graph_sched(session.irg, "-spill");
 
-			//be_spill_ilp(&session, cls);
+			be_liveness(irg);
+			be_numbering(irg);
+			be_check_pressure(&session, cls);
+
+#if 0
+			{
+				FILE *f;
+				char buf[128];
+				ir_snprintf(buf, sizeof(buf), "%F_%s-live.txt", irg, cls->name);
+				if((f = fopen(buf, "wt")) != NULL) {
+					be_liveness_dump(session.irg, f);
+					fclose(f);
+				}
+			}
+#endif
 
 			chordal_env = be_ra_chordal(&session, cls);
 
 #ifdef DUMP_ALLOCATED
 			dump_allocated_irg(env.arch_env, irg, "");
 #endif
+#if 0
 			copystat_collect_cls(chordal_env);
 
 			be_copy_opt(chordal_env);
 
 			be_ssa_destruction(chordal_env);
 			be_ssa_destruction_check(chordal_env);
+#endif
 			be_ra_chordal_check(chordal_env);
 
 			be_ra_chordal_done(chordal_env);
 			be_numbering_done(irg);
 		}
-		dump_ir_block_graph(session.irg, "-post");
+		dump_ir_block_graph_sched(session.irg, "-post");
 
 		copystat_dump(irg);
 		copystat_dump_pretty(irg);
@@ -195,7 +211,10 @@ void be_main(int argc, const char *argv[])
 	assembler_t *gnu_assembler;
 	FILE *asm_output_file;
 
+	mtrace();
 	be_main_loop();
+	muntrace();
+
 	gnu_assembler = gnuasm_create_assembler();
 	asm_output_file = fopen("asm_output.asm", "w");
 
@@ -203,4 +222,5 @@ void be_main(int argc, const char *argv[])
 	gnuasm_dump(gnu_assembler, asm_output_file);
 	gnuasm_delete_assembler(gnu_assembler);
 	fclose(asm_output_file);
+
 }
diff --git a/ir/be/benode.c b/ir/be/benode.c
index 748a22696..b7a53f047 100644
--- a/ir/be/benode.c
+++ b/ir/be/benode.c
@@ -133,20 +133,52 @@ ir_node *new_Copy(const be_node_factory_t *factory,
   return new_ir_node(NULL, irg, bl, op, get_irn_mode(in), 1, ins);
 }
 
-#if 0
-ir_node *be_spill(const be_node_factory_t *factory, ir_node *irn)
+ir_node *be_spill(
+		const be_node_factory_t *factory,
+		const arch_env_t *arch_env,
+		ir_node *irn)
 {
-  ir_node *bl = get_nodes_block(irn);
-  ir_graph *irg = get_irn_irg(bl);
-  ir_node *spill =
-    new_Spill(factory, arch_get_irn_reg_class(irn), irg, bl, irn);
-  sched_add_after(irn, spill);
+  const arch_register_class_t *cls
+		= arch_get_irn_reg_class(arch_env, irn, arch_pos_make_out(0));
+  ir_node *bl    = get_nodes_block(irn);
+  ir_graph *irg  = get_irn_irg(bl);
+  ir_node *spill = new_Spill(factory, cls, irg, bl, irn);
+
+	ir_node *insert;
+
+	/*
+	 * search the right insertion point. a spill of a phi cannot be put
+	 * directly after the phi, if there are some phis behind the one which
+	 * is spilled.
+	 */
+	insert = sched_next(irn);
+	while(is_Phi(insert) && !sched_is_end(insert))
+		insert = sched_next(insert);
+
+	sched_add_before(insert, spill);
   return spill;
 }
-#endif
 
+ir_node *be_reload(
+		const be_node_factory_t *factory,
+		const arch_env_t *arch_env,
+		const arch_register_class_t *cls,
+		ir_node *irn, int pos, ir_mode *mode, ir_node *spill)
+{
+	ir_node *reload;
+
+  ir_node *bl   = get_nodes_block(irn);
+  ir_graph *irg = get_irn_irg(bl);
+
+	assert(is_Spill(factory, spill)
+			|| (is_Phi(spill) && get_irn_mode(spill) == mode_M));
 
+  reload = new_Reload(factory, cls, irg, bl, mode, spill);
 
+	set_irn_n(irn, pos, reload);
+  sched_add_before(irn, reload);
+  return reload;
+}
 
 /**
  * If the node is a proj, reset the node to the proj's target and return
@@ -174,10 +206,12 @@ be_node_get_irn_reg_req(const arch_irn_ops_t *_self,
     arch_register_req_t *req, const ir_node *irn, int pos)
 {
   be_op_t *bo;
+	int index = arch_pos_get_index(pos);
   const be_node_factory_t *factory =
     container_of(_self, const be_node_factory_t, irn_ops);
 
-  pos = arch_pos_make_out(redir_proj(&irn, arch_pos_get_index(pos)));
+	if(arch_pos_is_out(pos))
+		pos = arch_pos_make_out(redir_proj(&irn, index));
 
   bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
 
@@ -185,9 +219,9 @@ be_node_get_irn_reg_req(const arch_irn_ops_t *_self,
     int i;
 
     req->type = arch_register_req_type_normal;
-    req->cls = bo->cls;
+    req->cls  = bo->cls;
 
-    for(i = 0; i < bo->n_pos; ++pos)
+    for(i = 0; i < bo->n_pos; ++i)
       if(pos == bo->pos[i])
         return req;
   }
@@ -244,10 +278,23 @@ arch_irn_class_t be_node_classify(const arch_irn_ops_t *_self, const ir_node *ir
   idx = redir_proj(&irn, 0);
   bo = pmap_get(factory->irn_op_map, get_irn_op(irn));
 
-  /* TODO Implement */
+	switch(bo->kind) {
+#define XXX(a) case node_kind_ ## a: return arch_irn_class_ ## a;
+		XXX(spill)
+		XXX(reload)
+		XXX(perm)
+		XXX(copy)
+#undef XXX
+	}
+
   return 0;
 }
 
+arch_irn_class_t be_node_get_flags(const arch_irn_ops_t *_self, const ir_node *irn)
+{
+	return 0;
+}
+
 static const arch_irn_ops_t *
 be_node_get_irn_ops(const arch_irn_handler_t *_self, const ir_node *irn)
 {
@@ -270,7 +317,7 @@ int is_Spill(const be_node_factory_t *f, const ir_node *irn)
 {
   be_op_t *bo;
   bo = pmap_get(f->irn_op_map, get_irn_op(irn));
-  return bo->kind == node_kind_spill;
+  return bo != NULL && bo->kind == node_kind_spill;
 }
 
 be_node_factory_t *be_node_factory_init(be_node_factory_t *factory,
@@ -290,6 +337,7 @@ be_node_factory_t *be_node_factory_init(be_node_factory_t *factory,
   factory->irn_ops.set_irn_reg     = be_node_set_irn_reg;
   factory->irn_ops.get_irn_reg     = be_node_get_irn_reg;
   factory->irn_ops.classify        = be_node_classify;
+  factory->irn_ops.get_flags       = be_node_get_flags;
 
   for(i = 0, n = isa->get_n_reg_class(); i < n; ++i) {
     const arch_register_class_t *cls = isa->get_reg_class(i);
@@ -298,31 +346,31 @@ be_node_factory_t *be_node_factory_init(be_node_factory_t *factory,
     ent = get_op(factory, cls, node_kind_spill);
     snprintf(buf, sizeof(buf), "Spill_%s", cls->name);
     ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned,
-        0, 0, oparity_unary, 0);
+        0, oparity_unary, 0, 0);
     ent->n_pos = ARRSIZE(templ_pos_Spill);
     ent->pos = templ_pos_Spill;
     pmap_insert(factory->irn_op_map, ent->op, ent);
 
     ent = get_op(factory, cls, node_kind_reload);
     snprintf(buf, sizeof(buf), "Reload_%s", cls->name);
-    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0, 0,
-        oparity_unary, sizeof(const arch_register_t *));
+    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0,
+        oparity_unary, 0, sizeof(const arch_register_t *));
     ent->n_pos = ARRSIZE(templ_pos_Reload);
     ent->pos = templ_pos_Reload;
     pmap_insert(factory->irn_op_map, ent->op, ent);
 
     ent = get_op(factory, cls, node_kind_copy);
     snprintf(buf, sizeof(buf), "Copy_%s", cls->name);
-    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0, 0,
-        oparity_unary, sizeof(const arch_register_t *));
+    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0,
+        oparity_unary, 0, sizeof(const arch_register_t *));
     ent->n_pos = ARRSIZE(templ_pos_Copy);
     ent->pos = templ_pos_Copy;
     pmap_insert(factory->irn_op_map, ent->op, ent);
 
     ent = get_op(factory, cls, node_kind_perm);
     snprintf(buf, sizeof(buf), "Perm_%s", cls->name);
-    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0, 0,
-        oparity_variable, sizeof(const arch_register_t) * cls->n_regs);
+    ent->op = new_ir_op(get_next_ir_opcode(), buf, op_pin_state_pinned, 0,
+        oparity_variable, 0, sizeof(const arch_register_t) * cls->n_regs);
     ent->n_pos = 2 * cls->n_regs;
     ent->pos = obstack_alloc(&factory->obst, sizeof(ent->pos[0]) * ent->n_pos);
     for(j = 0; j < ent->n_pos; j += 2) {
@@ -406,88 +454,3 @@ ir_node *insert_Perm_after(const be_main_session_env_t *env,
   }
   return perm;
 }
-
-#if 0
-typedef struct _phi_perm_info_t {
-  const be_main_session_env_t *env;
-  const arch_register_class_t *cls;
-  pmap *perm_map;
-} phi_perm_info_t;
-
-static void clear_link(ir_node *irn, void *data)
-{
-  set_irn_link(irn, NULL);
-}
-
-static void collect_phis(ir_node *irn, void *data)
-{
-  phi_perm_info_t *pi = data;
-  if(is_Phi(irn) && arch_irn_has_reg_class(pi->env->main_env->arch_env,
-        irn, arch_pos_make_out(0), pi->cls)) {
-
-    ir_node *bl = get_nodes_block(irn);
-    set_irn_link(irn, get_irn_link(bl));
-    set_irn_link(bl, irn);
-  }
-}
-
-/* This is only semi-ugly :-) */
-#define INT_TO_PTR(i) ((void *) ((char *) 0 + (i)))
-#define PTR_TO_INT(p) ((int) ((char *) (p) - (char *) 0))
-
-static void insert_phi_perms(ir_node *bl, void *data)
-{
-  phi_perm_info_t *pi = data;
-  ir_graph *irg = pi->env->irg;
-
-  assert(is_Block(bl));
-
-  /* If the link flag is NULL, this block has no phis. */
-  if(get_irn_link(bl)) {
-    int i, n;
-
-    /* Look at all predecessors of the phi block */
-    for(i = 0, n = get_irn_arity(bl); i < n; ++i) {
-      ir_node *pred_bl = get_Block_cfgpred_block(bl, i);
-      ir_node *phi, *perm;
-      ir_node **in;
-      int n_phis = 0;
-      int j;
-
-      for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi))
-        n_phis++;
-
-      in = malloc(n_phis * sizeof(in[0]));
-
-      /* Look at all phis in this block */
-      j = 0;
-      for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi))
-        in[j++] = get_irn_n(phi, i);
-
-      perm = new_Perm(pi->env->main_env->node_factory, pi->cls, irg, pred_bl, n_phis, in);
-
-      j = 0;
-      for(phi = get_irn_link(bl); phi; phi = get_irn_link(phi)) {
-        ir_node *proj = new_r_Proj(irg, pred_bl, perm, get_irn_mode(phi), j++);
-        set_irn_n(phi, i, proj);
-      }
-
-      free(in);
-    }
-  }
-}
-
-void be_insert_phi_perms(const be_main_session_env_t *env,
-    const arch_register_class_t *cls)
-{
-  phi_perm_info_t pi;
-
-  pi.env = env;
-  pi.cls = cls;
-  pi.perm_map = pmap_create();
-
-  irg_walk_graph(env->irg, clear_link, collect_phis, &pi);
-  irg_block_walk_graph(env->irg, insert_phi_perms, NULL, &pi);
-  pmap_destroy(pi.perm_map);
-}
-#endif
diff --git a/ir/be/benode_t.h b/ir/be/benode_t.h
index be56b72fd..d3afbd59f 100644
--- a/ir/be/benode_t.h
+++ b/ir/be/benode_t.h
@@ -55,8 +55,16 @@ ir_node *new_Copy(const be_node_factory_t *factory,
     const arch_register_class_t *cls,
     ir_graph *irg, ir_node *block, ir_node *in);
 
-ir_node *be_spill(const be_node_factory_t *factory, const arch_env_t *env, ir_node *irn);
-ir_node *be_reload(const be_node_factory_t *factory, const arch_env_t *env, ir_node *irn);
+ir_node *be_spill(
+		const be_node_factory_t *factory,
+		const arch_env_t *arch_env,
+		ir_node *irn);
+
+ir_node *be_reload(
+		const be_node_factory_t *factory,
+		const arch_env_t *arch_env,
+		const arch_register_class_t *cls,
+		ir_node *irn, int pos, ir_mode *mode, ir_node *spill);
 
 int is_Spill(const be_node_factory_t *f, const ir_node *irn);
 
diff --git a/ir/be/bespillilp.c b/ir/be/bespillilp.c
new file mode 100644
index 000000000..535c22ccd
--- /dev/null
+++ b/ir/be/bespillilp.c
@@ -0,0 +1,672 @@
+/**
+ * @file   bespillilp.c
+ * @date   15.07.2005
+ * @author Sebastian Hack
+ *
+ * ILP based spilling
+ *
+ * Copyright (C) 2005 Universitaet Karlsruhe
+ * Released under the GPL
+ */
+#include <math.h>
+
+#include "hashptr.h"
+#include "debug.h"
+#include "obst.h"
+#include "set.h"
+#include "list.h"
+#include "pmap.h"
+
+#include "irprintf.h"
+#include "irgwalk.h"
+#include "irnode_t.h"
+#include "ircons_t.h"
+
+#include <lpp/lpp.h>
+#include <lpp/lpp_net.h>
+
+#include "be_t.h"
+#include "belive_t.h"
+#include "besched_t.h"
+#include "beirgmod.h"
+#include "bearch.h"
+#include "benode_t.h"
+#include "beutil.h"
+
+#define BIGM 1000.0
+
+#define MAX(a,b) ((a) > (b) ? (a) : (b))
+
+#define DBG_LEVEL SET_LEVEL_3
+
+#define DUMP_SOLUTION
+#define DUMP_ILP
+
+#define LPP_SERVER "i44pc52"
+#define LPP_SOLVER "cplex"
+
+#define COST_LOAD      10
+#define COST_STORE     50
+#define COST_REMAT     (-9)
+
+#define is_end_of_block_use(lr) (is_Block((lr)->user))
+
+typedef struct _spill_ilp_t {
+  const be_main_session_env_t *session_env;
+  const arch_register_class_t *cls;
+	firm_dbg_module_t *dbg;
+  lpp_t *lpp;
+	set *irn_use_heads;
+  set *live_ranges;
+	set *spill_ctx;
+	pset *remove_phis;
+  struct obstack *obst;
+	int enable_store : 1;
+	int enable_remat : 1;
+} spill_ilp_t;
+
+typedef struct _live_range_t live_range_t;
+
+typedef struct _irn_use_head_t {
+	struct list_head head;
+	ir_node *irn;
+	int spill_var;
+	int n_uses;
+	live_range_t *closest_use;
+} irn_use_head_t;
+
+struct _live_range_t {
+  struct list_head list;
+	irn_use_head_t *use_head;
+  ir_node *user;
+  ir_node *irn;
+	int pos;
+  int in_mem_var;
+  int is_remat_var;
+};
+
+typedef struct _spill_ctx_t {
+	ir_node *spilled;  /**< The spilled node. */
+	ir_node *user;     /**< The node this spill is for. */
+	ir_node *spill;    /**< The spill itself. */
+} spill_ctx_t;
+
+static int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
+{
+  return arch_irn_has_reg_class(si->session_env->main_env->arch_env,
+      irn, arch_pos_make_out(0), si->cls);
+}
+
+static int register_demand(spill_ilp_t *si, const ir_node *irn)
+{
+	const arch_env_t *arch_env = si->session_env->main_env->arch_env;
+	int n_in = arch_get_n_operands(arch_env, irn, 0);
+	int n_out = arch_get_n_operands(arch_env, irn, -1);
+
+	return MAX(n_in, n_out);
+}
+
+static int cmp_spill_ctx(const void *a, const void *b, size_t n)
+{
+	const spill_ctx_t *p = a;
+	const spill_ctx_t *q = b;
+  return !(p->user == q->user && p->spilled == q->spilled);
+}
+
+static int cmp_live_range(const void *a, const void *b, size_t n)
+{
+  const live_range_t *p = a;
+  const live_range_t *q = b;
+
+  return !(p->user == q->user && p->irn == q->irn && p->pos == q->pos);
+}
+
+static int cmp_irn_use_head(const void *a, const void *b, size_t n)
+{
+  const irn_use_head_t *p = a;
+  const irn_use_head_t *q = b;
+
+	return !(p->irn == q->irn);
+}
+
+/**
+ * Checks, if a vertain node can be recomputed at a certain position.
+ * @param si    The spill ILP environment.
+ * @param irn   The node to recompute.
+ * @param live  The nodes live at the place where @p irn shall be
+ *              recomputed.
+ * @return      1, if irn can be recomputed, 0 if not.
+ */
+static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *live)
+{
+	int i, n;
+  const arch_env_t *arch_env    = si->session_env->main_env->arch_env;
+	int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
+
+	for(i = 0, n = get_irn_arity(irn); i < n && remat; ++i) {
+		ir_node *op = get_irn_n(irn, i);
+		remat &= !has_reg_class(si, op) || pset_find_ptr(live, op);
+	}
+
+	return remat;
+}
+
+static spill_ctx_t *get_spill_ctx(spill_ilp_t *si, ir_node *spilled, ir_node *ctx_irn)
+{
+	spill_ctx_t templ, *res;
+
+	templ.spilled = spilled;
+	templ.user    = ctx_irn;
+	templ.spill   = NULL;
+
+	res = set_insert(si->spill_ctx, &templ, sizeof(templ),
+			HASH_COMBINE(HASH_PTR(spilled), HASH_PTR(ctx_irn)));
+
+	return res;
+}
+
+static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user, int pos)
+{
+  live_range_t lr, *res;
+	irn_use_head_t iuh, *head;
+	int is_new;
+  unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
+
+  lr.user    = user;
+  lr.irn     = irn;
+  lr.pos     = pos;
+  lr.in_mem_var = -1;
+	lr.is_remat_var = -1;
+
+  res = set_insert(si->live_ranges, &lr, sizeof(lr), hash);
+	is_new = res->in_mem_var == -1;
+
+  if(is_new) {
+    char buf[128];
+    ir_snprintf(buf, sizeof(buf), "m_%s%N_%N_%d",
+				is_Phi(irn) ? "phi_" : "", irn, user, MAX(pos, 0));
+    res->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, pos >= 0 ? COST_LOAD : 0.0);
+  }
+
+	memset(&iuh, 0, sizeof(iuh));
+	iuh.irn = irn;
+	iuh.n_uses = -1;
+	head = set_insert(si->irn_use_heads, &iuh, sizeof(iuh), HASH_PTR(irn));
+	if(head->n_uses == -1) {
+		head->n_uses = 0;
+		INIT_LIST_HEAD(&head->head);
+	}
+
+	if(is_new) {
+		list_add_tail(&res->list, &head->head);
+		head->n_uses++;
+	}
+
+	res->use_head = head;
+
+  return res;
+}
+
+static live_range_t *lookup_live_range(const spill_ilp_t *si, ir_node *irn,
+		ir_node *user, int pos)
+{
+  live_range_t lr;
+  unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
+
+  lr.user    = user;
+  lr.irn     = irn;
+  lr.pos     = pos;
+  lr.in_mem_var = -1;
+
+  return set_find(si->live_ranges, &lr, sizeof(lr), hash);
+}
+
+static void create_block_live_range_sets(ir_node *bl, void *data)
+{
+	assert(is_Block(bl));
+	set_irn_link(bl, pset_new_ptr_default());
+}
+
+static void delete_block_live_range_sets(ir_node *bl, void *data)
+{
+	assert(is_Block(bl));
+
+	del_pset(get_irn_link(bl));
+	set_irn_link(bl, NULL);
+}
+
+#if 0
+static void annotate_live_ranges(ir_node *irn, void *data)
+{
+	const ir_edge_t *edge;
+
+	foreach_out_edge(irn, edge) {
+		pset *lr_set;
+
+		ir_node *user = edge->use;
+		int pos       = edge->pos;
+		ir_node *bl   = get_nodes_block(user);
+
+		if(is_Phi(user))
+			bl = get_Block_cfgpred_block(bl, pos);
+
+		lr_set = get_irn_link(bl);
+
+	}
+}
+#endif
+
+
+static void process_block(ir_node *bl, void *data)
+{
+	char buf[128];
+	int i, n;
+  spill_ilp_t *si  = data;
+  int step         = 0;
+  int n_regs       = arch_register_class_n_regs(si->cls);
+	int n_preds      = get_irn_arity(bl);
+  pset *live       = pset_new_ptr_default();
+  irn_live_t *li;
+  ir_node *irn;
+
+  /* as always, bring the live end nodes to life here */
+  live_foreach(bl, li) {
+    if(live_is_end(li) && has_reg_class(si, li->irn)) {
+      ir_node *irn = (ir_node *) li->irn;
+      pset_insert_ptr(live, irn);
+
+      /*
+       * The "user" of the live range to the end of a block
+       * is the block itself. This is quite arbitrary.
+       */
+      set_irn_link(irn, get_live_range(si, irn, bl, -1));
+    }
+  }
+
+	sched_foreach_reverse(bl, irn) {
+		ir_node *l;
+		int cst;
+		int demand;
+		int n_live;
+		int must_be_in_mem;
+
+		/* We handle phi togther with live ins after this loop (see below). */
+		if(is_Phi(irn))
+			break;
+
+		if(has_reg_class(si, irn))
+			pset_remove_ptr(live, irn);
+
+		demand = register_demand(si, irn);
+		n_live = pset_count(live);
+
+		/*
+		 * Determine, how many values (which are not used at the label)
+		 * must be in memory.
+		 * demand means the number of registers, the operation will consume.
+		 * So there are n_regs - demand registers available to store values
+		 * which are not used at this label. The rest must reside in memory.
+		 */
+		must_be_in_mem = MAX(n_live - (n_regs - demand), 0);
+
+		if(must_be_in_mem > 0) {
+
+			/*
+			 * The constraint limiting the pressure at this label to
+			 * the number of free registers.
+			 */
+			ir_snprintf(buf, sizeof(buf), "cp_%N_%d", bl, step);
+			cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
+
+			for(l = pset_first(live); l; l = pset_next(live)) {
+				live_range_t *lr = get_irn_link(l);
+				lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
+			}
+		}
+
+		for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
+			ir_node *op = get_irn_n(irn, i);
+
+			if(has_reg_class(si, op)) {
+				live_range_t *op_lr = get_live_range(si, op, irn, i);
+
+				set_irn_link(op, op_lr);
+
+				/*
+				 * The operand is reloaded at its usage, so it must not occur
+				 * in the constraint which determines which values live at the
+				 * instruction must reside in memory.
+				 */
+				if(must_be_in_mem > 0) {
+					lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
+				}
+
+				/*
+				 * Check, if the node is a rematerializable node and
+				 * if its operands are live here.
+				 */
+				if(si->enable_remat && can_remat(si, op, live)) {
+					int cst;
+					int j, n;
+					int n_operands = 0;
+
+					for(j = 0, n = get_irn_arity(op); j < n; ++j)
+						n_operands += has_reg_class(si, get_irn_n(op, j));
+
+					/* Make the remat constraint for this operand */
+					ir_snprintf(buf, sizeof(buf), "ce1_%N_%N_%d", op, irn, i);
+					cst = lpp_add_cst(si->lpp, buf, lpp_less, n_operands);
+
+					/* Make the rematerialize variable for the operand */
+					ir_snprintf(buf, sizeof(buf), "e_%N_%N_%d", op, irn, i);
+					op_lr->is_remat_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_REMAT);
+					lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, n_operands);
+
+					for(j = 0, n = get_irn_arity(op); j < n; ++j) {
+						ir_node *oop = get_irn_n(op, j);
+						if(has_reg_class(si, oop)) {
+							live_range_t *lr = get_irn_link(oop);
+							lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
+						}
+					}
+
+					ir_snprintf(buf, sizeof(buf), "ce2_%N_%N_%d", op, irn, i);
+					cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
+					lpp_set_factor_fast(si->lpp, cst, op_lr->is_remat_var, 1.0);
+					lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, -1.0);
+				}
+			}
+		}
+
+			for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
+				ir_node *op = get_irn_n(irn, i);
+				if(has_reg_class(si, op) && !is_Phi(irn))
+					pset_insert_ptr(live, op);
+			}
+
+		step++;
+	}
+
+	/*
+	 * Here, only the phis in the block and the values live in are in the
+	 * live set.
+	 *
+	 * If a value is live in, it must be in a register in all predecessor
+	 * blocks or in memory at the end of all predecessor blocks. Also, the
+	 * closest use in the current block must then be from register or
+	 * memory, respectively.
+	 */
+	for(irn = pset_first(live); irn; irn = pset_next(live)) {
+		live_range_t *lr = get_irn_link(irn);
+		int is_phi = is_Phi(irn) && get_nodes_block(irn) == bl;
+		int cst;
+
+		if(is_phi)
+			lr->use_head->closest_use = lr;
+
+		assert(has_reg_class(si, irn));
+		assert(is_Phi(irn) || is_live_in(bl, irn));
+
+#if 0
+		ir_snprintf(buf, sizeof(buf), "c%s_%N_%N", (is_phi ? "phi" : "li"), irn, bl);
+		cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
+		lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -n_preds);
+
+		for(i = 0; i < n_preds; ++i) {
+			ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
+			ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
+			live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
+
+			lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
+		}
+#endif
+
+		for(i = 0; i < n_preds; ++i) {
+			ir_node *pred_bl     = get_Block_cfgpred_block(bl, i);
+			ir_node *end_node    = is_phi ? get_irn_n(irn, i) : irn;
+			live_range_t *op_lr  = get_live_range(si, end_node, pred_bl, -1);
+
+			ir_snprintf(buf, sizeof(buf), "cpred_%N_%N_%d", lr->irn, bl, i);
+			cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
+			lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
+			lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, -1.0);
+		}
+	}
+
+  del_pset(live);
+}
+
+/**
+ * Add the costs for a store.
+ *
+ * If one of the uses is from memory, add additional costs for the
+ * spill.
+ *
+ * m_1 + ... + m_n - M * s <= 0
+ *
+ * @param si The ILP spilling environment.
+ */
+static void add_store_costs(spill_ilp_t *si)
+{
+	char buf[64];
+	irn_use_head_t *uh;
+	double costs = si->enable_store ? COST_STORE : 0.0;
+
+	for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
+		int cst;
+		live_range_t *lr;
+
+		ir_snprintf(buf, sizeof(buf), "cs_%N", uh->irn);
+		cst = lpp_add_cst(si->lpp, buf, lpp_less, 0);
+
+		ir_snprintf(buf, sizeof(buf), "s_%N", uh->irn);
+		uh->spill_var = lpp_add_var(si->lpp, buf, lpp_binary, costs);
+		lpp_set_factor_fast(si->lpp, cst, uh->spill_var, -BIGM);
+
+    list_for_each_entry(live_range_t, lr, &uh->head, list)
+			lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
+	}
+}
+
+static INLINE int is_zero(double x)
+{
+  return fabs(x) < 0.00001;
+}
+
+static int is_spilled(const spill_ilp_t *si, const live_range_t *lr)
+{
+	return !is_zero(lpp_get_var_sol(si->lpp, lr->in_mem_var));
+}
+
+static ir_node *spill_irn(spill_ilp_t *si, ir_node *irn, ir_node *ctx_irn)
+{
+  const be_node_factory_t *fact = si->session_env->main_env->node_factory;
+  const arch_env_t *arch_env    = si->session_env->main_env->arch_env;
+	spill_ctx_t *ctx;
+
+	ctx = get_spill_ctx(si, irn, ctx_irn);
+	if(ctx->spill)
+		return ctx->spill;
+
+	ctx->spill = be_spill(fact, arch_env, irn);
+	return ctx->spill;
+}
+
+static ir_node *spill_phi(spill_ilp_t *si, ir_node *phi, ir_node *ctx_irn, pset *rem_phis)
+{
+	int i, n;
+	ir_mode *mode = get_irn_mode(phi);
+	ir_node **ins;
+	ir_node *bl = get_nodes_block(phi);
+	ir_graph *irg = get_irn_irg(bl);
+	spill_ctx_t *ctx;
+
+	assert(is_Phi(phi));
+
+	ctx = get_spill_ctx(si, phi, ctx_irn);
+	if(ctx->spill)
+		return ctx->spill;
+
+	n    = get_irn_arity(phi);
+	ins  = malloc(n * sizeof(ins[0]));
+
+	for(i = 0; i < n; ++i)
+		ins[i]  = new_r_Unknown(irg, mode_M);
+
+	ctx->spill = new_r_Phi(irg, bl, n, ins, mode_M);
+	free(ins);
+
+	for(i = 0; i < n; ++i) {
+		ir_node *arg = get_irn_n(phi, i);
+		ir_node *res;
+
+		if(is_Phi(arg))
+			res = spill_phi(si, arg, ctx_irn, rem_phis);
+		else
+			res = spill_irn(si, arg, ctx_irn);
+
+		set_irn_n(ctx->spill, i, res);
+	}
+
+	return ctx->spill;
+}
+
+static ir_node *spill_live_range(spill_ilp_t *si, live_range_t *lr, pset *rem_phis)
+{
+	const live_range_t *closest = lr->use_head->closest_use;
+
+	if(is_Phi(lr->irn) && closest && is_spilled(si, closest))
+		return spill_phi(si, lr->irn, lr->irn, rem_phis);
+	else
+		return spill_irn(si, lr->irn, lr->irn);
+}
+
+
+static void writeback_results(spill_ilp_t *si)
+{
+  const be_node_factory_t *fact = si->session_env->main_env->node_factory;
+  const arch_env_t *arch_env    = si->session_env->main_env->arch_env;
+	ir_node *irn;
+	irn_use_head_t *uh;
+	pset *rem_phis = pset_new_ptr_default();
+
+	for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
+		if(is_Phi(uh->irn) && is_spilled(si, uh->closest_use))
+			pset_insert_ptr(rem_phis, uh->irn);
+	}
+
+	/* Look at each node and examine the usages. */
+	for(uh = set_first(si->irn_use_heads); uh; uh = set_next(si->irn_use_heads)) {
+    live_range_t *lr;
+    ir_node **reloads;
+
+    int n_reloads           = 0;
+    ir_node *irn            = uh->irn;
+		ir_mode *mode           = get_irn_mode(irn);
+
+		/* Go through all live ranges of the node. */
+    list_for_each_entry(live_range_t, lr, &uh->head, list) {
+      int spilled = is_spilled(si, lr);
+
+      if(spilled && !is_end_of_block_use(lr)) {
+				ir_node *bl      = get_nodes_block(lr->user);
+				ir_node *spill   = spill_live_range(si, lr, rem_phis);
+				ir_node *reload  = new_Reload(fact, si->cls,
+						si->session_env->irg, bl, mode, spill);
+
+				obstack_ptr_grow(si->obst, reload);
+        n_reloads++;
+
+				sched_add_before(lr->user, reload);
+			}
+    }
+
+		if(n_reloads > 0) {
+			reloads = obstack_finish(si->obst);
+			be_introduce_copies_ignore(si->session_env->dom_front, irn,
+					n_reloads, reloads, rem_phis);
+			obstack_free(si->obst, reloads);
+		}
+  }
+
+	for(irn = pset_first(rem_phis); irn; irn = pset_next(rem_phis)) {
+		int i, n;
+
+		for(i = 0, n = get_irn_arity(irn); i < n; ++i)
+			set_irn_n(irn, i, new_r_Bad(si->session_env->irg));
+		sched_remove(irn);
+	}
+}
+
+void be_spill_ilp(const be_main_session_env_t *session_env,
+    const arch_register_class_t *cls)
+{
+	char buf[256];
+	char problem_name[256];
+  struct obstack obst;
+  spill_ilp_t si;
+
+	ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", session_env->irg, cls->name);
+
+  obstack_init(&obst);
+  si.obst           = &obst;
+	si.dbg            = firm_dbg_register("be.ra.spillilp");
+  si.session_env    = session_env;
+  si.cls            = cls;
+  si.lpp            = new_lpp(problem_name, lpp_minimize);
+  si.irn_use_heads  = new_set(cmp_irn_use_head, 4096);
+  si.live_ranges    = new_set(cmp_live_range, 16384);
+  si.spill_ctx      = new_set(cmp_spill_ctx, 4096);
+	si.enable_remat   = 1;
+	si.enable_store   = 1;
+
+	firm_dbg_set_mask(si.dbg, DBG_LEVEL);
+  irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
+	if(si.enable_store)
+		add_store_costs(&si);
+
+	DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
+  lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
+	assert(lpp_is_sol_valid(si.lpp) && "ILP not feasible");
+
+  // assert(lpp_is_sol_valid(si.lpp) && "solution of ILP must be valid");
+
+	DBG((si.dbg, LEVEL_1, "\tnodes: %d, vars: %d, csts: %d\n",
+				set_count(si.irn_use_heads), si.lpp->var_next, si.lpp->cst_next));
+	DBG((si.dbg, LEVEL_1, "\titerations: %d, solution time: %g\n",
+				si.lpp->iterations, si.lpp->sol_time));
+
+#ifdef DUMP_ILP
+	{
+		FILE *f;
+
+		ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
+		if((f = fopen(buf, "wt")) != NULL) {
+			lpp_dump_plain(si.lpp, f);
+			fclose(f);
+		}
+	}
+#endif
+
+#ifdef DUMP_SOLUTION
+	{
+		FILE *f;
+
+		ir_snprintf(buf, sizeof(buf), "spill-%s.sol", problem_name);
+		if((f = fopen(buf, "wt")) != NULL) {
+			int i;
+			for(i = 0; i < si.lpp->var_next; ++i) {
+				lpp_name_t *name = si.lpp->vars[i];
+				fprintf(f, "%10s %4d %10f\n", name->name, name->nr, name->value);
+			}
+			fclose(f);
+		}
+	}
+#endif
+  writeback_results(&si);
+
+  del_set(si.irn_use_heads);
+  del_set(si.live_ranges);
+  free_lpp(si.lpp);
+  obstack_free(&obst, NULL);
+}
diff --git a/ir/be/bespillilp.h b/ir/be/bespillilp.h
new file mode 100644
index 000000000..23f2a0b21
--- /dev/null
+++ b/ir/be/bespillilp.h
@@ -0,0 +1,20 @@
+
+/**
+ * @file   bespillilp.h
+ * @date   27.07.2005
+ * @author Sebastian Hack
+ *
+ * Copyright (C) 2005 Universitaet Karlsruhe
+ * Released under the GPL
+ */
+
+#ifndef _BESPILLILP_H
+#define _BESPILLILP_H
+
+#include "bearch.h"
+#include "be_t.h"
+
+void be_spill_ilp(const be_main_session_env_t *env,
+    const arch_register_class_t *cls);
+
+#endif /* _BESPILLILP_H */
-- 
2.20.1