X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillremat.c;h=0de1bdca138bc8cad4581be244cd15f1a9665bdc;hb=97927c8e372f337e8342b698072facf4ffa453ad;hp=bd50b975e05f8ddac90660a0cd83e0091e2bd3e0;hpb=a1e68eec23322c45c678083ca14f5a82a84aef19;p=libfirm

diff --git a/ir/be/bespillremat.c b/ir/be/bespillremat.c
index bd50b975e..0de1bdca1 100644
--- a/ir/be/bespillremat.c
+++ b/ir/be/bespillremat.c
@@ -33,24 +33,27 @@
 #include "iredges.h"
 #include "execfreq.h"
 #include "irvrfy.h"
+#include "irbackedge_t.h"
 
 #include <lpp/lpp.h>
 #include <lpp/mps.h>
 #include <lpp/lpp_net.h>
 #include <lpp/lpp_cplex.h>
 //#include <lc_pset.h>
-#include <libcore/lc_bitset.h>
+//#include <libcore/lc_bitset.h>
 
 #include "be_t.h"
 #include "belive_t.h"
 #include "besched_t.h"
 #include "beirgmod.h"
 #include "bearch.h"
+#include "beabi.h"
 #include "benode_t.h"
 #include "beutil.h"
 #include "bespillremat.h"
 #include "bespill.h"
 #include "bepressurestat.h"
+#include "beprofile.h"
 
 #include "bechordal_t.h"
 
@@ -62,6 +65,8 @@
 #define DUMP_PROBLEM       1
 #define DUMP_MPS           2
 #define DUMP_SOLUTION      4
+#define DUMP_STATS         8
+#define DUMP_PRESSURE      16
 
 #define KEEPALIVE_REMATS   1
 #define KEEPALIVE_SPILLS   2
@@ -98,6 +103,8 @@ static const lc_opt_enum_mask_items_t dump_items[] = {
 	{ "problem",  DUMP_PROBLEM  },
 	{ "mps",      DUMP_MPS      },
 	{ "solution", DUMP_SOLUTION },
+	{ "stats",    DUMP_STATS },
+	{ "pressure", DUMP_PRESSURE },
 	{ NULL,       0 }
 };
 
@@ -137,9 +144,9 @@ static const lc_opt_table_entry_t options[] = {
 	LC_OPT_ENT_ENUM_INT ("remats",  "type of remats to insert (none, briggs, noinverse or all)",&remats_var),
 	LC_OPT_ENT_BOOL     ("repair_schedule",  "repair the schedule by rematting once used nodes",&opt_repair_schedule),
 	LC_OPT_ENT_BOOL     ("no_enlage_liveness",  "do not enlarge liveness of operands of remats",&opt_no_enlarge_liveness),
-	LC_OPT_ENT_BOOL     ("remat_while_live",  "remat only values that can be used by real ops", &opt_remat_while_live),
+	LC_OPT_ENT_BOOL     ("remat_while_live",  "only remat where rematted value was live",       &opt_remat_while_live),
 
-	LC_OPT_ENT_ENUM_MASK("dump", "dump problem, mps or solution",                               &dump_var),
+	LC_OPT_ENT_ENUM_MASK("dump", "dump problem, mps, solution, stats or pressure",              &dump_var),
 	LC_OPT_ENT_BOOL     ("log",  "activate the lpp log",                                        &opt_log),
 	LC_OPT_ENT_INT      ("timeout",  "ILP solver timeout",                                      &opt_timeout),
 
@@ -186,6 +193,9 @@ typedef struct _spill_ilp_t {
 	set                          *interferences;
 	ir_node                      *m_unknown;
 	set                          *memoperands;
+#ifndef SCHEDULE_PHIM
+	pset                         *phims;
+#endif
 	DEBUG_ONLY(firm_dbg_module_t * dbg);
 } spill_ilp_t;
 
@@ -416,6 +426,9 @@ static double
 execution_frequency(const spill_ilp_t *si, const ir_node * irn)
 {
 #define FUDGE 0.001
+	if(be_profile_has_data())
+		return ((double)be_profile_get_block_execcount(get_block(irn))) + FUDGE;
+
 #ifndef EXECFREQ_LOOPDEPH
 	return get_block_execfreq(si->chordal_env->exec_freq, get_block(irn)) + FUDGE;
 #else
@@ -486,11 +499,11 @@ get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node *
 		if(!is_rematerializable(si, op))
 			return NULL;
 
-		remat = obstack_alloc(si->obst, sizeof(*remat));
-		remat->op = op;
-		remat->cost = get_cost(si, op);
-		remat->value = dest_value;
-		remat->proj = proj;
+		remat          = obstack_alloc(si->obst, sizeof(*remat));
+		remat->op      = op;
+		remat->cost    = get_cost(si, op);
+		remat->value   = dest_value;
+		remat->proj    = proj;
 		remat->inverse = 0;
 	} else {
 		arch_inverse_t     inverse;
@@ -759,6 +772,55 @@ sched_put_before(const spill_ilp_t * si, ir_node * insert, ir_node * irn)
   sched_add_after(insert, irn);
 }
 
+static ir_node *
+next_post_remat(const ir_node * irn)
+{
+	op_t      *op;
+    ir_node   *next;
+
+	if(is_Block(irn)) {
+		next = sched_block_first_nonphi(irn);
+	} else {
+		next = sched_next_op(irn);
+	}
+
+	if(sched_is_end(next))
+		return NULL;
+
+	op = get_irn_link(next);
+	if(op->is_remat && !op->attr.remat.pre) {
+		return next;
+	}
+
+	return NULL;
+}
+
+
+static ir_node *
+next_pre_remat(const spill_ilp_t * si, const ir_node * irn)
+{
+	op_t      *op;
+	ir_node   *ret;
+
+	if(is_Block(irn)) {
+		ret = sched_block_last_noncf(si, irn);
+		ret = sched_next(ret);
+		ret = sched_prev_op(ret);
+	} else {
+		ret = sched_prev_op(irn);
+	}
+
+	if(sched_is_end(ret) || is_Phi(ret))
+		return NULL;
+
+	op = (op_t*)get_irn_link(ret);
+	if(op->is_remat && op->attr.remat.pre) {
+		return ret;
+	}
+
+	return NULL;
+}
+
 /**
  * Tells you whether a @p remat can be placed before the irn @p pos
  */
@@ -976,17 +1038,6 @@ is_start_block(const ir_node * bb)
 	return get_irg_start_block(get_irn_irg(bb)) == bb;
 }
 
-static int
-is_before_frame(const ir_node * bb, const ir_node * irn)
-{
-	const ir_node  *frame  = get_irg_frame(get_irn_irg(bb));
-
-	if(is_start_block(bb) && sched_get_time_step(frame) >= sched_get_time_step(irn))
-		return 1;
-	else
-		return 0;
-}
-
 static int
 is_merge_edge(const ir_node * bb)
 {
@@ -1011,6 +1062,58 @@ is_diverge_edge(const ir_node * bb)
 		return 1;
 }
 
+static void
+get_live_end(spill_ilp_t * si, ir_node * bb, pset * live)
+{
+	ir_node        *irn;
+	int i;
+
+	be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
+		irn = be_lv_get_irn(si->lv, bb, i);
+
+		if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
+			pset_insert_ptr(live, irn);
+		}
+	}
+
+	irn = sched_last(bb);
+
+	/* all values eaten by control flow operations are also live until the end of the block */
+	sched_foreach_reverse(bb, irn) {
+		int  i;
+
+		if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
+
+		for(i=get_irn_arity(irn)-1; i>=0; --i) {
+			ir_node *arg = get_irn_n(irn,i);
+
+			if(has_reg_class(si, arg)) {
+				pset_insert_ptr(live, arg);
+			}
+		}
+	}
+	/*
+	 * find values that are used by remats at end of block
+	 * and insert them into live set
+	 */
+	foreach_pre_remat(si, bb, irn) {
+		int       n;
+
+		for (n=get_irn_arity(irn)-1; n>=0; --n) {
+			ir_node        *remat_arg = get_irn_n(irn, n);
+
+			if(!has_reg_class(si, remat_arg)) continue;
+
+			/* if value is becoming live through use by remat */
+			if(!pset_find_ptr(live, remat_arg)) {
+				DBG((si->dbg, LEVEL_4, "  value %+F becoming live through use by remat at end of block %+F\n", remat_arg, irn));
+
+				pset_insert_ptr(live, remat_arg);
+			}
+		}
+	}
+}
+
 static void
 walker_regclass_copy_insertor(ir_node * irn, void * data)
 {
@@ -1041,7 +1144,6 @@ walker_regclass_copy_insertor(ir_node * irn, void * data)
 	}
 }
 
-
 /**
  * Insert (so far unused) remats into the irg to
  * recompute the potential liveness of all values
@@ -1050,13 +1152,18 @@ static void
 walker_remat_insertor(ir_node * bb, void * data)
 {
 	spill_ilp_t    *si = data;
-	spill_bb_t     *spill_bb;
 	ir_node        *irn;
 	int             n, i;
-	pset           *live = pset_new_ptr_default();
+	pset           *live;
+	pset           *post_remats;
+	remat_t        *remat;
+
+	/* skip start block, no remats to do there */
+	if(is_start_block(bb)) return;
 
 	DBG((si->dbg, LEVEL_3, "\t Entering %+F\n\n", bb));
 
+	live = pset_new_ptr_default();
 	be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
 		ir_node        *value = be_lv_get_irn(si->lv, bb, i);
 
@@ -1066,76 +1173,45 @@ walker_remat_insertor(ir_node * bb, void * data)
 		}
 	}
 
-	spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb));
-	set_irn_link(bb, spill_bb);
-
 	irn = sched_last(bb);
 	while(!sched_is_end(irn)) {
 		ir_node   *next;
-		op_t      *op;
 		pset      *args;
 		ir_node   *arg;
-		pset      *remat_args;
+		pset      *used;
 
 		next = sched_prev(irn);
 
-		DBG((si->dbg, LEVEL_5, "\t at %+F (next: %+F)\n", irn, next));
+		/* delete defined value from live set */
+		if(has_reg_class(si, irn)) {
+			pset_remove_ptr(live, irn);
+		}
 
 		if(is_Phi(irn) || is_Proj(irn)) {
-			op_t      *op;
-
-			if(has_reg_class(si, irn)) {
-				pset_remove_ptr(live, irn);
-			}
-
-			op = obstack_alloc(si->obst, sizeof(*op));
-			op->is_remat = 0;
-			op->attr.live_range.args.reloads = NULL;
-			op->attr.live_range.ilp = ILP_UNDEF;
-			set_irn_link(irn, op);
-
 			irn = next;
 			continue;
 		}
 
-		op = obstack_alloc(si->obst, sizeof(*op));
-		op->is_remat = 0;
-		op->attr.live_range.ilp = ILP_UNDEF;
-		op->attr.live_range.args.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
-		memset(op->attr.live_range.args.reloads, 0xFF, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
-		set_irn_link(irn, op);
-
 		args = pset_new_ptr_default();
+		used = pset_new_ptr_default();
 
-		/* collect arguments of op */
+		/* collect arguments of op and set args of op already live in epilog */
 		for (n = get_irn_arity(irn)-1; n>=0; --n) {
 			ir_node        *arg = get_irn_n(irn, n);
 
 			pset_insert_ptr(args, arg);
-		}
-
-		/* set args of op already live in epilog */
-		pset_foreach(args, arg) {
 			if(has_reg_class(si, arg)) {
 				pset_insert_ptr(live, arg);
+				pset_insert_ptr(used, arg);
 			}
 		}
-		/* delete defined value from live set */
-		if(has_reg_class(si, irn)) {
-			pset_remove_ptr(live, irn);
-		}
-
-
-		remat_args = pset_new_ptr_default();
 
 		/* insert all possible remats before irn */
 		pset_foreach(args, arg) {
 			remat_info_t   *remat_info,
 						    query;
-			remat_t        *remat;
 
-			/* continue if the operand has the wrong reg class
-			 */
+			/* continue if the operand has the wrong reg class */
 			if(!has_reg_class(si, arg))
 				continue;
 
@@ -1153,41 +1229,34 @@ walker_remat_insertor(ir_node * bb, void * data)
 					ir_node  *remat_irn = NULL;
 
 					DBG((si->dbg, LEVEL_4, "\t  considering remat %+F for arg %+F\n", remat->op, arg));
-					if(opt_remat_while_live) {
-						if(pset_find_ptr(live, remat->value)) {
-							remat_irn = insert_remat_before(si, remat, irn, live);
-						}
-					} else {
-						remat_irn = insert_remat_before(si, remat, irn, live);
-					}
+					remat_irn = insert_remat_before(si, remat, irn, live);
+
 					if(remat_irn) {
 						for(n=get_irn_arity(remat_irn)-1; n>=0; --n) {
 							ir_node  *remat_arg = get_irn_n(remat_irn, n);
 
-							if(!has_reg_class(si, remat_arg)) continue;
-
-							pset_insert_ptr(remat_args, remat_arg);
+							/* collect args of remats which are not args of op */
+							if(has_reg_class(si, remat_arg) && !pset_find_ptr(args, remat_arg)) {
+								pset_insert_ptr(used, remat_arg);
+							}
 						}
 					}
 				}
 			}
 		}
 
-		/* now we add remat args to op's args because they could also die at this op */
-		pset_foreach(args,arg) {
-			if(pset_find_ptr(remat_args, arg)) {
-				pset_remove_ptr(remat_args, arg);
-			}
-		}
-		pset_foreach(remat_args,arg) {
-			pset_insert_ptr(args, arg);
+		/* do not place post remats after jumps */
+		if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) {
+			del_pset(used);
+			del_pset(args);
+			break;
 		}
 
 		/* insert all possible remats after irn */
-		pset_foreach(args, arg) {
+		post_remats = pset_new_ptr_default();
+		pset_foreach(used, arg) {
 			remat_info_t   *remat_info,
 						    query;
-			remat_t        *remat;
 
 			/* continue if the operand has the wrong reg class */
 			if(!has_reg_class(si, arg))
@@ -1202,27 +1271,26 @@ walker_remat_insertor(ir_node * bb, void * data)
 				continue;
 			}
 
-			/* do not place post remats after jumps */
-			if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) continue;
-
 			if(remat_info->remats_by_operand) {
 				pset_foreach(remat_info->remats_by_operand, remat) {
 					/* do not insert remats producing the same value as one of the operands */
 					if(!pset_find_ptr(args, remat->value)) {
 						DBG((si->dbg, LEVEL_4, "\t  considering remat %+F with arg %+F\n", remat->op, arg));
-						if(opt_remat_while_live) {
-							if(pset_find_ptr(live, remat->value)) {
-								insert_remat_after(si, remat, irn, live);
-							}
-						} else {
-							insert_remat_after(si, remat, irn, live);
+
+						/* only remat values that can be used by real ops */
+						if(!opt_remat_while_live || pset_find_ptr(live, remat->value)) {
+							pset_insert_ptr(post_remats, remat);
 						}
 					}
 				}
 			}
 		}
+		pset_foreach(post_remats, remat) {
+			insert_remat_after(si, remat, irn, live);
+		}
+		del_pset(post_remats);
 
-		del_pset(remat_args);
+		del_pset(used);
 		del_pset(args);
 		irn = next;
 	}
@@ -1232,19 +1300,12 @@ walker_remat_insertor(ir_node * bb, void * data)
 		pset     *live_out = pset_new_ptr_default();
 		ir_node  *value;
 
-		be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
-			value = be_lv_get_irn(si->lv, bb, i);
-
-			if (has_reg_class(si, value)) {
-				pset_insert_ptr(live_out, value);
-			}
-		}
+		get_live_end(si, bb, live_out);
 
 		/* add remats at end of block */
 		pset_foreach(live_out, value) {
 			remat_info_t   *remat_info,
 						   query;
-			remat_t        *remat;
 
 			query.irn = value;
 			query.remats = NULL;
@@ -1273,6 +1334,7 @@ walker_remat_insertor(ir_node * bb, void * data)
 				pset_insert_ptr(live_in, value);
 			}
 		}
+		/* add phis to live_in */
 		sched_foreach(bb, value) {
 			if(!is_Phi(value)) break;
 
@@ -1282,10 +1344,10 @@ walker_remat_insertor(ir_node * bb, void * data)
 		}
 
 		/* add remat2s at beginning of block */
+		post_remats = pset_new_ptr_default();
 		pset_foreach(live_in, value) {
 			remat_info_t   *remat_info,
 						   query;
-			remat_t        *remat;
 
 			query.irn = value;
 			query.remats = NULL;
@@ -1296,16 +1358,80 @@ walker_remat_insertor(ir_node * bb, void * data)
 				pset_foreach(remat_info->remats_by_operand, remat) {
 					DBG((si->dbg, LEVEL_4, "\t  considering remat2 %+F at beginning of block %+F\n", remat->op, bb));
 
-					/* put the remat here if all its args are available */
-					insert_remat_after(si, remat, bb, live_in);
-
+					/* put the remat here if all its args are available and result is still live */
+					if(!opt_remat_while_live || pset_find_ptr(live_in, remat->value)) {
+						pset_insert_ptr(post_remats, remat);
+					}
 				}
 			}
 		}
+		pset_foreach(post_remats, remat) {
+			insert_remat_after(si, remat, bb, live_in);
+		}
+		del_pset(post_remats);
 		del_pset(live_in);
 	}
 }
 
+static int
+can_be_copied(const ir_node * bb, const ir_node * irn)
+{
+	const ir_edge_t *edge    = get_block_succ_first(bb);
+	const ir_node   *next_bb = edge->src;
+	int             pos      = edge->pos;
+	const ir_node   *phi;
+
+	assert(is_merge_edge(bb));
+
+	sched_foreach(next_bb, phi) {
+		const ir_node  *phi_arg;
+
+		if(!is_Phi(phi)) break;
+
+		phi_arg = get_irn_n(phi, pos);
+
+		if(phi_arg == irn) {
+			return 1;
+		}
+	}
+	return 0;
+}
+
+/**
+ * Initialize additional node info
+ */
+static void
+luke_initializer(ir_node * bb, void * data)
+{
+	spill_ilp_t    *si = (spill_ilp_t*)data;
+	spill_bb_t     *spill_bb;
+	ir_node        *irn;
+
+	spill_bb = obstack_alloc(si->obst, sizeof(*spill_bb));
+	set_irn_link(bb, spill_bb);
+
+	sched_foreach(bb, irn) {
+		op_t      *op;
+
+		op = obstack_alloc(si->obst, sizeof(*op));
+		op->is_remat = 0;
+		op->attr.live_range.ilp = ILP_UNDEF;
+		if(is_Phi(irn)) {
+			if(opt_memcopies) {
+				op->attr.live_range.args.copies = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(irn));
+				memset(op->attr.live_range.args.copies, 0xFF, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(irn));
+			}
+		} else if(!is_Proj(irn)) {
+			op->attr.live_range.args.reloads = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
+			memset(op->attr.live_range.args.reloads, 0xFF, sizeof(*op->attr.live_range.args.reloads) * get_irn_arity(irn));
+		} else {
+			op->attr.live_range.args.reloads = NULL;
+		}
+		set_irn_link(irn, op);
+	}
+}
+
+
 /**
  * Preparation of blocks' ends for Luke Blockwalker(tm)(R)
  */
@@ -1321,18 +1447,28 @@ luke_endwalker(ir_node * bb, void * data)
 	spill_bb_t     *spill_bb = get_irn_link(bb);
 	int             i;
 
-
 	live = pset_new_ptr_default();
 	use_end = pset_new_ptr_default();
 
 	be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
 		irn = be_lv_get_irn(si->lv, bb, i);
 		if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
-			op_t      *op;
-
 			pset_insert_ptr(live, irn);
-			op = get_irn_link(irn);
-			assert(!op->is_remat);
+		}
+	}
+	/*
+	 * find values that are used by remats at end of block
+	 * and insert them into live set
+	 */
+	foreach_pre_remat(si, bb, irn) {
+		int       n;
+
+		for (n=get_irn_arity(irn)-1; n>=0; --n) {
+			ir_node        *remat_arg = get_irn_n(irn, n);
+
+			if(has_reg_class(si, remat_arg)) {
+				pset_insert_ptr(live, remat_arg);
+			}
 		}
 	}
 
@@ -1399,7 +1535,7 @@ luke_endwalker(ir_node * bb, void * data)
 			ilp_cst_t   rel_cst;
 
 			ir_snprintf(buf, sizeof(buf), "reload_%N_%N", bb, irn);
-			reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0);
+			reload = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), can_be_copied(bb, irn));
 			set_insert_keyval(spill_bb->reloads, irn, INT_TO_PTR(reload));
 
 			/* reload <= mem_out */
@@ -1460,55 +1596,6 @@ luke_endwalker(ir_node * bb, void * data)
 	del_pset(use_end);
 }
 
-static ir_node *
-next_post_remat(const ir_node * irn)
-{
-	op_t      *op;
-    ir_node   *next;
-
-	if(is_Block(irn)) {
-		next = sched_block_first_nonphi(irn);
-	} else {
-		next = sched_next_op(irn);
-	}
-
-	if(sched_is_end(next))
-		return NULL;
-
-	op = get_irn_link(next);
-	if(op->is_remat && !op->attr.remat.pre) {
-		return next;
-	}
-
-	return NULL;
-}
-
-
-static ir_node *
-next_pre_remat(const spill_ilp_t * si, const ir_node * irn)
-{
-	op_t      *op;
-	ir_node   *ret;
-
-	if(is_Block(irn)) {
-		ret = sched_block_last_noncf(si, irn);
-		ret = sched_next(ret);
-		ret = sched_prev_op(ret);
-	} else {
-		ret = sched_prev_op(irn);
-	}
-
-	if(sched_is_end(ret) || is_Phi(ret))
-		return NULL;
-
-	op = (op_t*)get_irn_link(ret);
-	if(op->is_remat && op->attr.remat.pre) {
-		return ret;
-	}
-
-	return NULL;
-}
-
 /**
  * Find a remat of value @p value in the epilog of @p pos
  */
@@ -1568,38 +1655,6 @@ add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn)
 	return spill;
 }
 
-static void
-get_live_end(spill_ilp_t * si, ir_node * bb, pset * live)
-{
-	ir_node        *irn;
-	int i;
-
-	be_lv_foreach(si->lv, bb, be_lv_state_end, i) {
-		irn = be_lv_get_irn(si->lv, bb, i);
-
-		if (has_reg_class(si, irn) && !pset_find_ptr(si->all_possible_remats, irn)) {
-			pset_insert_ptr(live, irn);
-		}
-	}
-
-	irn = sched_last(bb);
-
-	/* all values eaten by control flow operations are also live until the end of the block */
-	sched_foreach_reverse(bb, irn) {
-		int  i;
-
-		if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
-
-		for(i=get_irn_arity(irn)-1; i>=0; --i) {
-			ir_node *arg = get_irn_n(irn,i);
-
-			if(has_reg_class(si, arg)) {
-				pset_insert_ptr(live, arg);
-			}
-		}
-	}
-}
-
 /**
  *  Inserts ILP-constraints and variables for memory copying before the given position
  */
@@ -1660,7 +1715,6 @@ insert_mem_copy_position(spill_ilp_t * si, pset * live, const ir_node * block)
 		if(!has_reg_class(si, phi)) continue;
 
 		to_copy = get_irn_n(phi, pos);
-
 		to_copy_op = get_irn_link(to_copy);
 
 		to_copy_spill = set_find_spill(spill_bb->ilp, to_copy);
@@ -1717,7 +1771,6 @@ luke_blockwalker(ir_node * bb, void * data)
 	pset           *defs = pset_new_ptr_default();
 	const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
 
-
 	live = pset_new_ptr_default();
 
 	/****************************************
@@ -1763,49 +1816,48 @@ luke_blockwalker(ir_node * bb, void * data)
 				lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
 			}
 		}
-		/* maybe we should also assure that reg_out >= live_range etc. */
-	}
+		ir_snprintf(buf, sizeof(buf), "reg_out2_%N_%N", bb, irn);
+		cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0);
 
-	if(opt_memcopies)
-		insert_mem_copy_position(si, live, bb);
-
-	/* allow only one argument to die at pre remat. If two value die check_pre does
-	 * not ensure a correct register pressure FIXME (verify this is really necessary!) */
-	foreach_pre_remat(si, bb, tmp) {
-		pset    *remat_args = pset_new_ptr(get_irn_arity(tmp));
-		int      n;
-		ir_node  *remat_arg;
-		op_t     *remat_op = get_irn_link(tmp);
-
-		for(n=get_irn_arity(tmp)-1; n>=0; --n) {
-			remat_arg = get_irn_n(tmp, n);
-
-			if(has_reg_class(si, remat_arg)) {
-				pset_insert_ptr(remat_args, remat_arg);
+		/* value may only die at bb end if it is used for a mem copy */
+		/* reg_out + \sum copy - reload - remat - live_range >= 0 */
+		lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0);
+		if(reload != ILP_UNDEF) lpp_set_factor_fast(si->lpp, cst, reload, -1.0);
+		lpp_set_factor_fast(si->lpp, cst, op->attr.live_range.ilp, -1.0);
+		foreach_pre_remat(si, bb, tmp) {
+			op_t     *remat_op = get_irn_link(tmp);
+			if(remat_op->attr.remat.remat->value == irn) {
+				lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -1.0);
 			}
 		}
+		if(is_merge_edge(bb)) {
+			const ir_edge_t *edge = get_block_succ_first(bb);
+			const ir_node   *next_bb = edge->src;
+			int              pos = edge->pos;
+			const ir_node   *phi;
+
+			sched_foreach(next_bb, phi) {
+				const ir_node  *phi_arg;
+
+				if(!is_Phi(phi)) break;
 
-		if(pset_count(remat_args)) {
-			/* \sum_args reg_out >= #args * remat - 1 */
-			ir_snprintf(buf, sizeof(buf), "one_may_die_%N", tmp);
-			cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, -1.0);
-			lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -pset_count(remat_args));
+				phi_arg = get_irn_n(phi, pos);
 
-			pset_foreach(remat_args, remat_arg) {
-				spill = set_find_spill(spill_bb->ilp, remat_arg);
+				if(phi_arg == irn) {
+					op_t      *phi_op = get_irn_link(phi);
+					ilp_var_t  copy = phi_op->attr.live_range.args.copies[pos];
 
-				if(spill) {
-					lpp_set_factor_fast(si->lpp, cst, spill->reg_out, 1.0);
+					lpp_set_factor_fast(si->lpp, cst, copy, 1.0);
 				}
 			}
 		}
-
-		del_pset(remat_args);
 	}
 
+	if(opt_memcopies)
+		insert_mem_copy_position(si, live, bb);
+
 	/*
-	 * start new live ranges for values used by remats at end of block
-	 * and assure the remat args are available
+	 * assure the remat args are available
 	 */
 	foreach_pre_remat(si, bb, tmp) {
 		op_t     *remat_op = get_irn_link(tmp);
@@ -1814,29 +1866,22 @@ luke_blockwalker(ir_node * bb, void * data)
 		for (n=get_irn_arity(tmp)-1; n>=0; --n) {
 			ir_node        *remat_arg = get_irn_n(tmp, n);
 			op_t           *arg_op = get_irn_link(remat_arg);
-			ilp_var_t       prev_lr;
 
 			if(!has_reg_class(si, remat_arg)) continue;
 
-			/* if value is becoming live through use by remat */
-			if(!pset_find_ptr(live, remat_arg)) {
-				ir_snprintf(buf, sizeof(buf), "lr_%N_end%N", remat_arg, bb);
-				prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0);
-
-				arg_op->attr.live_range.ilp = prev_lr;
-				arg_op->attr.live_range.op = bb;
-
-				DBG((si->dbg, LEVEL_4, "  value %+F becoming live through use by remat at end of block %+F\n", remat_arg, tmp));
+			spill = set_find_spill(spill_bb->ilp, remat_arg);
+			assert(spill);
 
-				pset_insert_ptr(live, remat_arg);
-				add_to_spill_bb(si, bb, remat_arg);
-			}
+			/* arguments of remats have to be live until the very end of the block
+			 * remat = reg_out(remat_arg) and (reload(remat_arg) or live_range(remat_arg)),
+			 * no remats, they could be in wrong order
+			 */
 
-			/* remat <= live_rang(remat_arg) [ + reload(remat_arg) ] */
 			ir_snprintf(buf, sizeof(buf), "req_remat_%N_arg_%N", tmp, remat_arg);
 			cst = lpp_add_cst(si->lpp, buf, lpp_less, 0.0);
 
-			lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+			lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 3.0);
+			lpp_set_factor_fast(si->lpp, cst, spill->reg_out, -2.0);
 			lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, -1.0);
 
 			/* use reload placed for this argument */
@@ -1881,6 +1926,7 @@ luke_blockwalker(ir_node * bb, void * data)
 		op = get_irn_link(irn);
 		/* skip remats */
 		if(op->is_remat) continue;
+
 		DBG((si->dbg, LEVEL_4, "\t  at node %+F\n", irn));
 
 		/* collect defined values */
@@ -1900,30 +1946,32 @@ luke_blockwalker(ir_node * bb, void * data)
 		used =       pset_new_ptr(pset_count(live) + get_irn_arity(irn));
 		remat_defs = pset_new_ptr(pset_count(live));
 
-		for (n=get_irn_arity(irn)-1; n>=0; --n) {
-			ir_node        *irn_arg = get_irn_n(irn, n);
-			if(has_reg_class(si, irn_arg)) {
-				set_insert_keyval(args, irn_arg, (void*)n);
-				pset_insert_ptr(used, irn_arg);
+		if(!is_start_block(bb) || !be_is_Barrier(irn)) {
+			for (n=get_irn_arity(irn)-1; n>=0; --n) {
+				ir_node        *irn_arg = get_irn_n(irn, n);
+				if(has_reg_class(si, irn_arg)) {
+					set_insert_keyval(args, irn_arg, (void*)n);
+					pset_insert_ptr(used, irn_arg);
+				}
 			}
-		}
-		foreach_post_remat(irn, tmp) {
-			op_t    *remat_op = get_irn_link(tmp);
+			foreach_post_remat(irn, tmp) {
+				op_t    *remat_op = get_irn_link(tmp);
 
-			pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value);
+				pset_insert_ptr(remat_defs, remat_op->attr.remat.remat->value);
 
-			for (n=get_irn_arity(tmp)-1; n>=0; --n) {
-				ir_node        *remat_arg = get_irn_n(tmp, n);
-				if(has_reg_class(si, remat_arg)) {
-					pset_insert_ptr(used, remat_arg);
+				for (n=get_irn_arity(tmp)-1; n>=0; --n) {
+					ir_node        *remat_arg = get_irn_n(tmp, n);
+					if(has_reg_class(si, remat_arg)) {
+						pset_insert_ptr(used, remat_arg);
+					}
 				}
 			}
-		}
-		foreach_pre_remat(si, irn, tmp) {
-			for (n=get_irn_arity(tmp)-1; n>=0; --n) {
-				ir_node        *remat_arg = get_irn_n(tmp, n);
-				if(has_reg_class(si, remat_arg)) {
-					pset_insert_ptr(used, remat_arg);
+			foreach_pre_remat(si, irn, tmp) {
+				for (n=get_irn_arity(tmp)-1; n>=0; --n) {
+					ir_node        *remat_arg = get_irn_n(tmp, n);
+					if(has_reg_class(si, remat_arg)) {
+						pset_insert_ptr(used, remat_arg);
+					}
 				}
 			}
 		}
@@ -2096,40 +2144,6 @@ skip_one_must_die:
 			}
 		}
 
-		/* allow only one argument to die at pre remat. If two value die check_pre does
-		 * not ensure a correct register pressure FIXME (verify this is really necessary!) */
-		foreach_pre_remat(si, irn, tmp) {
-			pset    *remat_args = pset_new_ptr(get_irn_arity(tmp));
-			int      n;
-			ir_node  *remat_arg;
-			op_t     *remat_op = get_irn_link(tmp);
-
-			for(n=get_irn_arity(tmp)-1; n>=0; --n) {
-				remat_arg = get_irn_n(tmp, n);
-
-				if(has_reg_class(si, remat_arg)) {
-					pset_insert_ptr(remat_args, remat_arg);
-				}
-			}
-
-			if(pset_count(remat_args)) {
-				/* \sum_args next(lr) >= #args * remat - 1 */
-				ir_snprintf(buf, sizeof(buf), "one_may_die_%N", tmp);
-				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, -1.0);
-				lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, -pset_count(remat_args));
-
-				pset_foreach(remat_args, remat_arg) {
-					op_t  *arg_op = get_irn_link(remat_arg);
-
-					if(arg_op->attr.live_range.ilp != ILP_UNDEF) {
-						lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0);
-					}
-				}
-			}
-
-			del_pset(remat_args);
-		}
-
 		/***********************************************************
 		 *  I T E R A T I O N  O V E R  U S E S  F O R  E P I L O G
 		 **********************************************************/
@@ -2148,7 +2162,7 @@ skip_one_must_die:
 
 			/* new live range for each used value */
 			ir_snprintf(buf, sizeof(buf), "lr_%N_%N", arg, irn);
-			prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, is_before_frame(bb, irn)?1.0:0.0);
+			prev_lr = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 0.0);
 
 			/* the epilog stuff - including post_use, check_post, check_post_remat */
 			ir_snprintf(buf, sizeof(buf), "post_use_%N_%N", arg, irn);
@@ -2165,7 +2179,26 @@ skip_one_must_die:
 				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
 				lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
 				lpp_set_factor_fast(si->lpp, cst, arg_op->attr.live_range.ilp, 1.0);
+			}
+
+			/* forall post remat which use arg add a similar cst */
+			foreach_post_remat(irn, remat) {
+				int      n;
 
+				for (n=get_irn_arity(remat)-1; n>=0; --n) {
+					ir_node    *remat_arg = get_irn_n(remat, n);
+					op_t       *remat_op = get_irn_link(remat);
+
+					if(remat_arg == arg) {
+						DBG((si->dbg, LEVEL_3, "\t  found remat with arg %+F in epilog of %+F\n", arg, irn));
+
+						/* post_use >= remat */
+						ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++);
+						cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
+						lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
+						lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
+					}
+				}
 			}
 
 			/* if value is not an arg of op and not possibly defined by post remat
@@ -2187,27 +2220,7 @@ skip_one_must_die:
 				}
 			}
 
-
-			/* forall post remat which use arg add a similar cst */
-			foreach_post_remat(irn, remat) {
-				int      n;
-
-				for (n=get_irn_arity(remat)-1; n>=0; --n) {
-					ir_node    *remat_arg = get_irn_n(remat, n);
-					op_t       *remat_op = get_irn_link(remat);
-
-					if(remat_arg == arg) {
-						DBG((si->dbg, LEVEL_3, "\t  found remat with arg %+F in epilog of %+F\n", arg, irn));
-
-						ir_snprintf(buf, sizeof(buf), "post_use_%N_%N-%d", arg, irn, p++);
-						cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
-						lpp_set_factor_fast(si->lpp, cst, post_use, -1.0);
-						lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
-					}
-				}
-			}
-
-			if(opt_memoperands) {
+			if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) {
 				for(n = get_irn_arity(irn)-1; n>=0; --n) {
 					if(get_irn_n(irn, n) == arg && arch_possible_memory_operand(arch_env, irn, n)) {
 						ilp_var_t       memoperand;
@@ -2235,7 +2248,63 @@ skip_one_must_die:
 		/* just to be sure */
 		check_post = ILP_UNDEF;
 
-
+		/* allow original defintions to be removed */
+		if(opt_repair_schedule) {
+			pset_foreach(defs, tmp) {
+				op_t      *tmp_op = get_irn_link(tmp);
+				spill_t   *spill = set_find_spill(spill_bb->ilp, tmp);
+#if 1
+				ilp_var_t  delete;
+				assert(spill);
+
+				ir_snprintf(buf, sizeof(buf), "delete_%N", tmp);
+				delete = lpp_add_var_default(si->lpp, buf, lpp_binary, -1.0*get_cost(si, irn)*execution_frequency(si, bb), 0.0);
+
+				/* op may not be killed if its first live_range is 1 */
+				ir_snprintf(buf, sizeof(buf), "killorig-lr_%N", tmp);
+				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, delete, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, 1.0);
+
+				/* op may not be killed if it is spilled after the definition */
+				ir_snprintf(buf, sizeof(buf), "killorig-spill_%N", tmp);
+				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, delete, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0);
+#else
+				ilp_var_t  keep;
+				assert(spill);
+
+				ir_snprintf(buf, sizeof(buf), "keep_%N", tmp);
+				keep = lpp_add_var_default(si->lpp, buf, lpp_binary, get_cost(si, irn)*execution_frequency(si, bb), 1.0);
+
+				/* op may not be killed if its first live_range is 1 */
+				ir_snprintf(buf, sizeof(buf), "killorig-lr_%N", tmp);
+				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0);
+				lpp_set_factor_fast(si->lpp, cst, keep, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, -1.0);
+
+				/* op may not be killed if it is spilled after the definition */
+				ir_snprintf(buf, sizeof(buf), "killorig-spill_%N", tmp);
+				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 0.0);
+				lpp_set_factor_fast(si->lpp, cst, keep, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, spill->spill, -1.0);
+#endif
+			}
+		} else {
+			pset_foreach(defs, tmp) {
+				op_t      *tmp_op = get_irn_link(tmp);
+				spill_t   *spill = set_find_spill(spill_bb->ilp, tmp);
+				assert(spill);
+
+				/* live_range or spill should be 1
+				   TODO: lr should be live until first use */
+				ir_snprintf(buf, sizeof(buf), "nokillorig_%N", tmp);
+				cst = lpp_add_cst_uniq(si->lpp, buf, lpp_greater, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, tmp_op->attr.live_range.ilp, 1.0);
+				lpp_set_factor_fast(si->lpp, cst, spill->spill, 1.0);
+			}
+		}
 
 
 		/******************
@@ -2252,7 +2321,7 @@ skip_one_must_die:
 			pset_remove_ptr(live, tmp);
 		}
 
-		if(opt_memoperands) {
+		if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) {
 			ir_snprintf(buf, sizeof(buf), "one_memoperand_%N", irn);
 			one_memoperand = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 1.0);
 		}
@@ -2274,7 +2343,7 @@ skip_one_must_die:
 			assert(spill);
 
 			ir_snprintf(buf, sizeof(buf), "reload_%N_%N", arg, irn);
-			op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), is_before_frame(bb, irn)?0.0:1.0);
+			op->attr.live_range.args.reloads[i] = lpp_add_var_default(si->lpp, buf, lpp_binary, opt_cost_reload*execution_frequency(si, bb), 1.0);
 
 			/* reload <= mem_out */
 			ir_snprintf(buf, sizeof(buf), "req_reload_%N_%N", arg, irn);
@@ -2296,7 +2365,7 @@ skip_one_must_die:
 				}
 			}
 
-			if(opt_memoperands) {
+			if(opt_memoperands && (!is_start_block(bb) || be_is_Barrier(irn))) {
 				n_memoperands = 0;
 				for(n = get_irn_arity(irn)-1; n>=0; --n) {
 					if(get_irn_n(irn, n) == arg) {
@@ -2336,7 +2405,6 @@ skip_one_must_die:
 			}
 		}
 
-
 		/* requirements for remats */
 		foreach_pre_remat(si, irn, tmp) {
 			op_t        *remat_op = get_irn_link(tmp);
@@ -2388,7 +2456,15 @@ skip_one_must_die:
 		del_set(args);
 		del_pset(defs);
 		defs = pset_new_ptr_default();
+
+		/* skip everything above barrier in start block */
+		if(is_start_block(bb) && be_is_Barrier(irn)) {
+			assert(pset_count(live) == 0);
+			break;
+		}
+
 	}
+	del_pset(defs);
 
 
 
@@ -2405,7 +2481,6 @@ skip_one_must_die:
 	}
 
 	/* construct mem_outs for all values */
-
 	set_foreach(spill_bb->ilp, spill) {
 		ir_snprintf(buf, sizeof(buf), "mem_out_%N_%N", spill->irn, bb);
 		cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0.0);
@@ -2426,10 +2501,6 @@ skip_one_must_die:
 				int   n;
 				op_t *op = get_irn_link(spill->irn);
 
-				/* do we have to copy a phi argument? */
-				op->attr.live_range.args.copies = obstack_alloc(si->obst, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(spill->irn));
-				memset(op->attr.live_range.args.copies, 0xFF, sizeof(*op->attr.live_range.args.copies) * get_irn_arity(spill->irn));
-
 				for(n=get_irn_arity(spill->irn)-1; n>=0; --n) {
 					const ir_node  *arg = get_irn_n(spill->irn, n);
 					double          freq=0.0;
@@ -2475,17 +2546,17 @@ skip_one_must_die:
 
 	foreach_post_remat(bb, tmp) {
 		int         n;
-		pset       *remat_args = pset_new_ptr(get_irn_arity(tmp));
 		op_t       *remat_op = get_irn_link(tmp);
+		pset       *remat_args = pset_new_ptr(get_irn_arity(tmp));
 		ir_node    *remat_arg;
 
 		for (n=get_irn_arity(tmp)-1; n>=0; --n) {
 			remat_arg = get_irn_n(tmp, n);
+
 			if(has_reg_class(si, remat_arg)) {
 				pset_insert_ptr(remat_args, remat_arg);
 			}
 		}
-		assert(pset_count(remat_args) > 0 && "post remats should have at least one arg");
 
 		/* remat + \sum live_range(remat_arg) <= |args| */
 		ir_snprintf(buf, sizeof(buf), "one_must_die_%N", tmp);
@@ -2493,8 +2564,22 @@ skip_one_must_die:
 		lpp_set_factor_fast(si->lpp, cst, remat_op->attr.remat.ilp, 1.0);
 
 		pset_foreach(remat_args, remat_arg) {
+			if(pset_find_ptr(live, remat_arg)) {
+				op_t       *remat_arg_op = get_irn_link(remat_arg);
+				lpp_set_factor_fast(si->lpp, cst, remat_arg_op->attr.live_range.ilp, 1.0);
+			}
+		}
+		del_pset(remat_args);
+	}
+
+	foreach_post_remat(bb, tmp) {
+		int  n;
+
+		for(n=get_irn_arity(tmp)-1; n>=0; --n) {
+			ir_node  *remat_arg = get_irn_n(tmp, n);
+
 			/* if value is becoming live through use by remat2 */
-			if(!pset_find_ptr(live, remat_arg)) {
+			if(has_reg_class(si, remat_arg) && !pset_find_ptr(live, remat_arg)) {
 				op_t       *remat_arg_op = get_irn_link(remat_arg);
 				ilp_cst_t   nomem;
 
@@ -2514,22 +2599,9 @@ skip_one_must_die:
 				/* optimization: all memory stuff should be 0, for we do not want to insert reloads for remats */
 				ir_snprintf(buf, sizeof(buf), "nomem_%N_%N", remat_arg, bb);
 				nomem = lpp_add_cst_uniq(si->lpp, buf, lpp_equal, 0.0);
-
 				lpp_set_factor_fast(si->lpp, nomem, spill->spill, 1.0);
-				if(spill_bb->reloads) {
-					keyval_t *keyval = set_find_keyval(spill_bb->reloads, remat_arg);
-
-					if(keyval) {
-						ilp_var_t reload = PTR_TO_INT(keyval->val);
-						lpp_set_factor_fast(si->lpp, nomem, reload, 1.0);
-					}
-				}
-			} else {
-				op_t       *remat_arg_op = get_irn_link(remat_arg);
-				lpp_set_factor_fast(si->lpp, cst, remat_arg_op->attr.live_range.ilp, 1.0);
 			}
 		}
-		del_pset(remat_args);
 	}
 
 	/* L\U is empty at bb start */
@@ -2712,13 +2784,14 @@ skip_one_must_die:
 
 	/* walk forward now and compute constraints for placing spills */
 	/* this must only be done for values that are not defined in this block */
-	/* TODO are these values at start of block? if yes, just check whether this is a diverge edge and skip the loop */
 	pset_foreach(live, irn) {
 		/*
 		 * if value is defined in this block we can anways place the spill directly after the def
 		 *    -> no constraint necessary
 		 */
-		if(!is_Phi(irn) && get_nodes_block(irn) == bb) continue;
+		if(!is_Phi(irn) && get_nodes_block(irn) == bb) {
+			assert(0);
+		}
 
 
 		spill = set_find_spill(spill_bb->ilp, irn);
@@ -3388,11 +3461,17 @@ clean_remat_info(spill_ilp_t * si)
 		pset_foreach(remat_info->remats, remat)
 		{
 			if(remat->proj && get_irn_n_edges(remat->proj) == 0) {
+				if(sched_is_scheduled(remat->proj)) {
+					sched_remove((ir_node*)remat->proj);
+				}
 				set_irn_n((ir_node*)remat->proj, -1, bad);
 				set_irn_n((ir_node*)remat->proj, 0, bad);
 			}
 
 			if(get_irn_n_edges(remat->op) == 0) {
+				if(sched_is_scheduled(remat->op)) {
+					sched_remove((ir_node*)remat->op);
+				}
 				for (n=get_irn_arity(remat->op)-1; n>=-1; --n) {
 					set_irn_n((ir_node*)remat->op, n, bad);
 				}
@@ -3412,9 +3491,6 @@ delete_unnecessary_remats(spill_ilp_t * si)
 		ir_node  *bad = get_irg_bad(si->chordal_env->irg);
 
 		if(si->keep) {
-//			ir_node   *end = get_irg_end(si->chordal_env->irg);
-//			ir_node  **keeps;
-
 			for (n=get_irn_arity(si->keep)-1; n>=0; --n) {
 				ir_node        *keep_arg = get_irn_n(si->keep, n);
 				op_t           *arg_op = get_irn_link(keep_arg);
@@ -3446,18 +3522,6 @@ delete_unnecessary_remats(spill_ilp_t * si)
 
 				set_irn_n(si->keep, n, bad);
 			}
-#if 0
-			for (i = 0, n = get_End_n_keepalives(end); i < n; ++i) {
-				ir_node        *end_arg = get_End_keepalive(end, i);
-
-				if(end_arg != si->keep) {
-					obstack_grow(si->obst, &end_arg, sizeof(end_arg));
-				}
-			}
-			keeps = obstack_finish(si->obst);
-			set_End_keepalives(end, n-1, keeps);
-			obstack_free(si->obst, keeps);
-#endif
 		} else {
 			DBG((si->dbg, LEVEL_2, "\t  no remats to delete (none have been inserted)\n"));
 		}
@@ -3510,6 +3574,19 @@ get_spills_for_value(spill_ilp_t * si, const ir_node * value)
 	return spills;
 }
 
+static ir_node *
+new_r_PhiM_nokeep(ir_graph * irg, ir_node *block, int arity, ir_node **in)
+{
+	ir_node  *res;
+
+	assert( get_irn_arity(block) == arity );
+
+	res = new_ir_node(NULL, irg, block, op_Phi, mode_M, arity, in);
+	res->attr.phi_backedge = new_backedge_arr(irg->obst, arity);
+
+	return res;
+}
+
 /**
  * @param before   The node after which the spill will be placed in the schedule
  */
@@ -3554,7 +3631,7 @@ insert_mem_phi(spill_ilp_t * si, ir_node * phi)
 		ins[n] = si->m_unknown;
 	}
 
-	mem_phi =  new_r_Phi(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins, mode_M);
+	mem_phi =  new_r_PhiM_nokeep(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins);
 
 	defs = set_insert_def(si->values, phi);
 	assert(defs);
@@ -3565,6 +3642,8 @@ insert_mem_phi(spill_ilp_t * si, ir_node * phi)
 
 #ifdef SCHEDULE_PHIM
 	sched_add_after(phi, mem_phi);
+#else
+	pset_insert_ptr(si->phims, mem_phi);
 #endif
 
 	if(opt_keep_alive & KEEPALIVE_SPILLS)
@@ -3906,6 +3985,7 @@ walker_reload_placer(ir_node * bb, void * data) {
 
 						reload = insert_reload(si, arg, insert_pos);
 
+						assert(reload && "no reload returned");
 						set_irn_n(irn, n, reload);
 
 						if(opt_keep_alive & KEEPALIVE_RELOADS)
@@ -3923,13 +4003,13 @@ walker_reload_placer(ir_node * bb, void * data) {
 static void
 walker_collect_used(ir_node * irn, void * data)
 {
-	lc_bitset_t   *used = data;
+	bitset_t   *used = data;
 
-	lc_bitset_set(used, get_irn_idx(irn));
+	bitset_set(used, get_irn_idx(irn));
 }
 
 struct kill_helper {
-	lc_bitset_t  *used;
+	bitset_t  *used;
 	spill_ilp_t  *si;
 };
 
@@ -3945,7 +4025,7 @@ walker_kill_unused(ir_node * bb, void * data)
 		ir_node     *next = sched_next(irn);
 		int          n;
 
-		if(!lc_bitset_is_set(kh->used, get_irn_idx(irn))) {
+		if(!bitset_is_set(kh->used, get_irn_idx(irn))) {
 			if(be_is_Spill(irn) || be_is_Reload(irn)) {
 				DBG((kh->si->dbg, LEVEL_1, "\t SUBOPTIMAL! %+F IS UNUSED (cost: %g)\n", irn, get_cost(kh->si, irn)*execution_frequency(kh->si, bb)));
 #if 0
@@ -3964,18 +4044,41 @@ walker_kill_unused(ir_node * bb, void * data)
 	}
 }
 
+#ifndef SCHEDULE_PHIM
+static void
+kill_unused_phims(spill_ilp_t * si, struct kill_helper * kh)
+{
+	ir_node  *phi;
+	ir_node  *bad = get_irg_bad(si->chordal_env->irg);
+	int       n;
+
+	pset_foreach(si->phims, phi) {
+		if(!bitset_is_set(kh->used, get_irn_idx(phi))) {
+
+			set_nodes_block(phi, bad);
+			for (n=get_irn_arity(phi)-1; n>=0; --n) {
+				set_irn_n(phi, n, bad);
+			}
+		}
+	}
+}
+#endif
+
 static void
 kill_all_unused_values_in_schedule(spill_ilp_t * si)
 {
-	struct kill_helper kh;
+	struct kill_helper  kh;
 
-	kh.used = lc_bitset_malloc(get_irg_last_idx(si->chordal_env->irg));
+	kh.used = bitset_malloc(get_irg_last_idx(si->chordal_env->irg));
 	kh.si = si;
 
 	irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, kh.used);
+#ifndef SCHEDULE_PHIM
+	kill_unused_phims(si, &kh);
+#endif
 	irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, &kh);
 
-	lc_bitset_free(kh.used);
+	bitset_free(kh.used);
 }
 
 void
@@ -4074,20 +4177,22 @@ rewire_uses(spill_ilp_t * si)
 	set_foreach(si->values, defs) {
 		pset           *nodes;
 		const ir_node  *next = defs->remats;
+		int             orig_kept = 0;
 
 		if(next) {
 			nodes = pset_new_ptr_default();
-			pset_insert_ptr(nodes, defs->value);
+			if(sched_is_scheduled(defs->value)) {
+				pset_insert_ptr(nodes, defs->value);
+				orig_kept = 1;
+			}
 
 			while(next) {
 				pset_insert_ptr(nodes, next);
 				next = get_irn_link(next);
 			}
 
-			if(pset_count(nodes) > 1) {
-				DBG((si->dbg, LEVEL_4, "\t    %d new definitions for value %+F\n", pset_count(nodes)-1, defs->value));
-				be_ssa_constr_set(dfi, si->lv, nodes);
-			}
+			DBG((si->dbg, LEVEL_4, "\t    %d new definitions for value %+F\n", pset_count(nodes)-orig_kept, defs->value));
+			be_ssa_constr_set(dfi, si->lv, nodes);
 
 			del_pset(nodes);
 		}
@@ -4128,18 +4233,22 @@ writeback_results(spill_ilp_t * si)
 static int
 get_n_regs(spill_ilp_t * si)
 {
-	int     arch_n_regs = arch_register_class_n_regs(si->cls);
-	int     free = 0;
-	int     i;
+	int       arch_n_regs = arch_register_class_n_regs(si->cls);
 
-	for(i=0; i<arch_n_regs; i++) {
-		if(!arch_register_type_is(&si->cls->regs[i], ignore)) {
-			free++;
-		}
-	}
+	bitset_t *arch_regs = bitset_malloc(arch_n_regs);
+	bitset_t *abi_regs = bitset_malloc(arch_n_regs);
+
+	arch_put_non_ignore_regs(si->chordal_env->birg->main_env->arch_env, si->cls, arch_regs);
+    be_abi_put_ignore_regs(si->chordal_env->birg->abi, si->cls, abi_regs);
+
+	bitset_andnot(arch_regs, abi_regs);
+	arch_n_regs = bitset_popcnt(arch_regs);
 
-	DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", free, si->cls->name));
-	return free;
+	bitset_free(arch_regs);
+	bitset_free(abi_regs);
+
+	DBG((si->dbg, LEVEL_1, "\tArchitecture has %d free registers in class %s\n", arch_n_regs, si->cls->name));
+	return arch_n_regs;
 }
 
 static void
@@ -4274,7 +4383,11 @@ be_spill_remat(const be_chordal_env_t * chordal_env)
 	/* compute phi classes */
 //	phi_class_compute(chordal_env->irg);
 
-	be_analyze_regpressure(chordal_env, "-pre");
+	if(opt_dump_flags & DUMP_STATS)
+		be_analyze_regpressure(chordal_env, "-pre");
+
+	DBG((si.dbg, LEVEL_2, "\t initializing\n"));
+	irg_block_walk_graph(chordal_env->irg, luke_initializer, NULL, &si);
 
 	if(opt_remats) {
 		/* collect remats */
@@ -4302,7 +4415,6 @@ be_spill_remat(const be_chordal_env_t * chordal_env)
 	be_liveness_recompute(si.lv);
 
 	/* build the ILP */
-
 	DBG((si.dbg, LEVEL_1, "\tBuilding ILP\n"));
 	DBG((si.dbg, LEVEL_2, "\t endwalker\n"));
 	irg_block_walk_graph(chordal_env->irg, luke_endwalker, NULL, &si);
@@ -4357,7 +4469,7 @@ be_spill_remat(const be_chordal_env_t * chordal_env)
 	assert(lpp_is_sol_valid(si.lpp)
 	       && "solution of ILP must be valid");
 
-	DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, is_zero(si.lpp->objval)?0.0:si.lpp->objval));
+	DBG((si.dbg, LEVEL_1, "\t%s: iterations: %d, solution time: %g, objective function: %g, best bound: %g\n", problem_name, si.lpp->iterations, si.lpp->sol_time, is_zero(si.lpp->objval)?0.0:si.lpp->objval, is_zero(si.lpp->best_bound)?0.0:si.lpp->best_bound));
 
 	if(opt_dump_flags & DUMP_SOLUTION) {
 		FILE           *f;
@@ -4374,12 +4486,20 @@ be_spill_remat(const be_chordal_env_t * chordal_env)
 		}
 	}
 
+#ifndef SCHEDULE_PHIM
+	si.phims = pset_new_ptr_default();
+#endif
 	writeback_results(&si);
 
+
 #endif				/* SOLVE */
 
 	kill_all_unused_values_in_schedule(&si);
 
+#if !defined(SCHEDULE_PHIM) && defined(SOLVE)
+	del_pset(si.phims);
+#endif
+
 	if(opt_keep_alive & (KEEPALIVE_SPILLS | KEEPALIVE_RELOADS))
 		be_dump(chordal_env->irg, "-spills-placed", dump_ir_block_graph);
 
@@ -4394,9 +4514,11 @@ be_spill_remat(const be_chordal_env_t * chordal_env)
 
 	irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si);
 
-	dump_pressure_graph(&si, dump_suffix2);
+	if(opt_dump_flags & DUMP_PRESSURE)
+		dump_pressure_graph(&si, dump_suffix2);
 
-	be_analyze_regpressure(chordal_env, "-post");
+	if(opt_dump_flags & DUMP_STATS)
+		be_analyze_regpressure(chordal_env, "-post");
 
 	if(opt_verify & VERIFY_DOMINANCE)
 		be_check_dominance(chordal_env->irg);