X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillilp.c;h=0a334792241e073f6836cb3703168c631908b848;hb=7ce0bb4ead9ca9c526a3a26bb8469915bf966f12;hp=8c6f7856ade5e7be14c49cf1ad7e629eeed014de;hpb=fd36bead18e3a2d5d6d5b9129c15c1c959e8c8a7;p=libfirm

diff --git a/ir/be/bespillilp.c b/ir/be/bespillilp.c
index 8c6f7856a..0a3347922 100644
--- a/ir/be/bespillilp.c
+++ b/ir/be/bespillilp.c
@@ -33,16 +33,19 @@
 #include "bearch.h"
 #include "benode_t.h"
 #include "beutil.h"
+#include "bespillilp.h"
 
 #define BIGM 1000.0
 
 #define MAX(a,b) ((a) > (b) ? (a) : (b))
 
-#define DBG_LEVEL SET_LEVEL_0
+#define DBG_LEVEL SET_LEVEL_3
 
-#undef DUMP_SOLUTION
-#undef DUMP_ILP
+#define DUMP_SOLUTION
+#define DUMP_ILP
+#undef  DUMP_STATS
 
+#undef  SOLVE_LOCAL
 #define LPP_SERVER "i44pc52"
 #define LPP_SOLVER "cplex"
 
@@ -52,16 +55,34 @@
 
 #define is_end_of_block_use(lr) (is_Block((lr)->user))
 
+/**
+ * Reloads on edges.
+ */
+typedef struct _edge_reload_t {
+	ir_node *irn;
+	ir_node *bl;
+	int pos;
+	int in_mem_var;
+	struct _edge_reload_t *next;
+} edge_reload_t;
+
+typedef struct _spill_stat_t {
+	int n_spills;
+	int n_reloads;
+	int n_remat;
+} spill_stat_t;
+
 typedef struct _spill_ilp_t {
-  const be_main_session_env_t *session_env;
-  const arch_register_class_t *cls;
+	const arch_register_class_t *cls;
+	const be_main_session_env_t *session;
 	firm_dbg_module_t *dbg;
-  lpp_t *lpp;
+	lpp_t *lpp;
 	set *irn_use_heads;
-  set *live_ranges;
-	set *spill_ctx;
-	pset *remove_phis;
-  struct obstack *obst;
+	set *live_ranges;
+	set *first_uses;
+	spill_env_t *senv;
+	edge_reload_t *edges;
+	struct obstack *obst;
 	int enable_store : 1;
 	int enable_remat : 1;
 } spill_ilp_t;
@@ -77,41 +98,31 @@ typedef struct _irn_use_head_t {
 } irn_use_head_t;
 
 struct _live_range_t {
-  struct list_head list;
+	struct list_head list;
 	irn_use_head_t *use_head;
-  ir_node *user;
-  ir_node *irn;
+	ir_node *user;
+	ir_node *irn;
 	int pos;
-  int in_mem_var;
-  int is_remat_var;
+	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);
-}
+/*
+ * Associates the first use of a live-in in a block
+ * with its live range.
+ */
+typedef struct _first_use_t {
+	ir_node *bl;
+	ir_node *irn;       /**< A value live in at bl. */
+	live_range_t *lr;   /**< The live range for the first use of irn in bl. */
+} first_use_t;
 
-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)
+static INLINE int has_reg_class(const spill_ilp_t *si, const ir_node *irn)
 {
-	const spill_ctx_t *p = a;
-	const spill_ctx_t *q = b;
-  return !(p->user == q->user && p->spilled == q->spilled);
+  return arch_irn_has_reg_class(si->session->main_env->arch_env,
+      irn, arch_pos_make_out(0), si->cls);
 }
 
 static int cmp_live_range(const void *a, const void *b, size_t n)
@@ -130,6 +141,45 @@ static int cmp_irn_use_head(const void *a, const void *b, size_t n)
 	return !(p->irn == q->irn);
 }
 
+static irn_use_head_t *get_use_head(spill_ilp_t *si, const ir_node *irn)
+{
+	irn_use_head_t templ;
+	templ.irn = (ir_node *) irn;
+	return set_find(si->irn_use_heads, &templ, sizeof(templ), HASH_PTR(irn));
+}
+
+static int cmp_first_use(const void *a, const void *b, size_t n)
+{
+  const first_use_t *p = a;
+  const first_use_t *q = b;
+
+  return !(p->irn == q->irn && p->bl == q->bl);
+}
+
+static void add_first_use(spill_ilp_t *si, ir_node *bl, ir_node *irn, live_range_t *lr)
+{
+	first_use_t templ;
+	templ.bl    = bl;
+	templ.irn   = irn;
+	templ.lr    = lr;
+
+	set_insert(si->first_uses, &templ, sizeof(templ),
+			HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
+}
+
+static live_range_t *get_first_use_lr(spill_ilp_t *si, ir_node *bl, ir_node *irn)
+{
+	first_use_t *res;
+	first_use_t templ;
+	templ.bl    = bl;
+	templ.irn   = irn;
+
+	res = set_find(si->first_uses, &templ, sizeof(templ),
+			HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)));
+
+	return res ? res->lr : NULL;
+}
+
 /**
  * Checks, if a vertain node can be recomputed at a certain position.
  * @param si    The spill ILP environment.
@@ -141,7 +191,7 @@ static int cmp_irn_use_head(const void *a, const void *b, size_t n)
 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;
+  const arch_env_t *arch_env    = si->session->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) {
@@ -152,42 +202,28 @@ static INLINE int can_remat(const spill_ilp_t *si, const ir_node *irn, pset *liv
 	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;
+	live_range_t lr, *res;
 	irn_use_head_t iuh, *head;
 	int is_new;
-  unsigned hash = HASH_COMBINE(HASH_PTR(irn), HASH_PTR(user));
+	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.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);
+	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);
-  }
+	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;
@@ -205,121 +241,136 @@ static live_range_t *get_live_range(spill_ilp_t *si, ir_node *irn, ir_node *user
 
 	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());
+	return res;
 }
 
-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);
+static void print_live_set(spill_ilp_t *si, pset *s) {
+	ir_node *n;
+	for(n=pset_first(s); n; n=pset_next(s))
+		DBG((si->dbg, LEVEL_3, "    %+F\n", n));
 }
 
-#if 0
-static void annotate_live_ranges(ir_node *irn, void *data)
+static void process_block(ir_node *bl, 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);
+	char buf[128];
+	int i, n, skipped=0;
+	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;
 
-		lr_set = get_irn_link(bl);
+	DBG((si->dbg, LEVEL_3, "\n"));
+	DBG((si->dbg, LEVEL_3, "Processing %+F\n", bl));
 
+	/*
+	 * Get all live-end values of this block
+	 */
+	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));
+		}
 	}
-}
-#endif
+	DBG((si->dbg, LEVEL_3, "Live-End:\n"));
+	print_live_set(si, live);
 
-
-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) {
+	/*
+	 * Walk through the schedule of this block from end to begin.
+	 * Phis are handled togther with live ins after this loop.
+	 */
+	for(irn = sched_last(bl); !sched_is_begin(irn) && !is_Phi(irn); irn = sched_prev(irn)) {
 		ir_node *l;
 		int cst;
+		int relevant_args, results;
 		int demand;
-		int n_live;
+		int n_cand;
 		int must_be_in_mem;
+		pset *cand;
+
+		/*
+		 * Determine the number of results
+		 */
+		/* Special handling of Projs */
+		if(is_Proj(irn)) {
+			if(has_reg_class(si, irn)) {
+				assert(pset_find_ptr(live, irn) && "node must be live");
+				pset_remove_ptr(live, irn);
+				skipped++;
+			}
 
-		/* We handle phi togther with live ins after this loop (see below). */
-		if(is_Phi(irn))
-			break;
+			DBG((si->dbg, LEVEL_2, "Skipped %+F\n", irn));
+			continue;
+		}
 
-		if(has_reg_class(si, irn))
-			pset_remove_ptr(live, irn);
+		DBG((si->dbg, LEVEL_1, "Irn %+F\n", irn));
+		if(skipped > 0) {
+			/* ModeT node */
+			assert(get_irn_mode(irn) == mode_T && "node before projs must be tuple");
+			results = skipped;
+			skipped = 0;
+		} else {
+			/* Normal node */
+			if(has_reg_class(si, irn)) {
+				assert(get_irn_mode(irn) != mode_T && "node must not be a tuple");
+				assert(pset_find_ptr(live, irn) && "node must be live");
+				pset_remove_ptr(live, irn);
+				results = 1;
+			} else {
+				results = 0;
+			}
+		}
 
-		demand = register_demand(si, irn);
-		n_live = pset_count(live);
+		/* cand holds the irns which may be spilled */
+		cand = pset_new_ptr(8);
+		for(l=pset_first(live); l; l=pset_next(live))
+			pset_insert_ptr(cand, l);
 
 		/*
-		 * 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.
+		 * Determine number of arguments
 		 */
-		must_be_in_mem = MAX(n_live - (n_regs - demand), 0);
+		relevant_args = 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)) {
+				DBG((si->dbg, LEVEL_2, "  arg %+F\n", op));
+				relevant_args++;
+				/* arguments must not be spilled */
+				if(pset_find_ptr(cand, op))
+					pset_remove_ptr(cand, op);
+			}
+		}
 
-		if(must_be_in_mem > 0) {
+		/*
+		 * Determine, how many values must be in memory.
+		 * We have 'n_regs' registers.
+		 * The instr. needs 'demand'.
+		 * So (R:= n_regs - demand) registers can be used for candidates 'cand'.
+		 * The rest (M:= n_cand - R) must reside in memory.
+		 */
+		demand = MAX(results, relevant_args);
+		n_cand = pset_count(cand);
+		must_be_in_mem = n_cand - (n_regs - demand);
 
-			/*
-			 * The constraint limiting the pressure at this label to
-			 * the number of free registers.
-			 */
-			ir_snprintf(buf, sizeof(buf), "cp_%N_%d", bl, step);
+		DBG((si->dbg, LEVEL_1, "  Demand: %d, Cands: %d, InMem: %d\n", demand, n_cand, must_be_in_mem));
+		DBG((si->dbg, LEVEL_3, "  Cand-Set:\n"));
+		print_live_set(si, cand);
+
+		/*
+		 * Generate the corresponding constraint spilling
+		 * enough candidates at this label.
+		 */
+		if(must_be_in_mem > 0) {
+			ir_snprintf(buf, sizeof(buf), "cp_%N_%N_%d", bl, irn, step);
 			cst = lpp_add_cst(si->lpp, buf, lpp_greater, must_be_in_mem);
 
-			for(l = pset_first(live); l; l = pset_next(live)) {
+			for(l = pset_first(cand); l; l = pset_next(cand)) {
 				live_range_t *lr = get_irn_link(l);
 				lpp_set_factor_fast(si->lpp, cst, lr->in_mem_var, 1.0);
 			}
@@ -330,17 +381,17 @@ static void process_block(ir_node *bl, void *data)
 
 			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);
-				}
+//				/*
+//				 * 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) {
+//					DBG((si->dbg, LEVEL_3, " Resetting %+F to 0:\n", op));
+//					lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 0.0);
+//				}
 
 				/*
 				 * Check, if the node is a rematerializable node and
@@ -379,12 +430,16 @@ static void process_block(ir_node *bl, void *data)
 			}
 		}
 
-			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);
-			}
+		/*
+		 * Insert arguments of current instr into the live set
+		 */
+		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))
+				pset_insert_ptr(live, op);
+		}
 
+		del_pset(cand);
 		step++;
 	}
 
@@ -392,9 +447,11 @@ static void process_block(ir_node *bl, void *data)
 		goto end;
 
 	/*
-	 * Here, only the phis in the block and the values live in are in the
-	 * live set.
+	 * Here, the live set contains
+	 * - phis of the block
+	 * - live-in values of the block
 	 *
+	 * TODO: comment is wrong
 	 * 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
@@ -405,41 +462,41 @@ static void process_block(ir_node *bl, void *data)
 		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);
+		/* Deprecated: Can be done with the first uses map */
+		if(is_phi)
+			lr->use_head->closest_use = lr;
 
-			lpp_set_factor_fast(si->lpp, cst, op_lr->in_mem_var, 1.0);
-		}
-#endif
+		/*
+		 * Remind the liverange of the first use of a live (or phi) in the
+		 * current block.
+		 */
+		add_first_use(si, bl, irn, lr);
 
 		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);
+			edge_reload_t *edge  = obstack_alloc(si->obst, sizeof(edge[0]));
+
+			ir_snprintf(buf, sizeof(buf), "edge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn);
+			edge->in_mem_var = lpp_add_var(si->lpp, buf, lpp_binary, COST_LOAD);
+			edge->bl         = bl;
+			edge->irn        = end_node;
+			edge->pos        = i;
 
-			ir_snprintf(buf, sizeof(buf), "cpred_%N_%N_%d", lr->irn, bl, i);
-			cst = lpp_add_cst(si->lpp, buf, lpp_equal, 0.0);
+			ir_snprintf(buf, sizeof(buf), "cedge_%N_%N_%N_%N", bl, pred_bl, end_node, op_lr->irn);
+			cst = lpp_add_cst(si->lpp, buf, lpp_less, 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);
+			lpp_set_factor_fast(si->lpp, cst, edge->in_mem_var, -1.0);
 		}
 	}
 
 end:
-
-  del_pset(live);
+	del_pset(live);
 }
 
 /**
@@ -484,149 +541,58 @@ 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)
-{
-	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);
-		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)
+static int is_mem_phi(const ir_node *phi, void *data)
 {
-	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);
-	else
-		return spill_irn(si, lr->irn, lr->irn);
+	spill_ilp_t *si = data;
+	return is_spilled(si, get_use_head(si, phi)->closest_use);
 }
 
-
 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);
-	}
+	edge_reload_t *edge;
 
 	/* 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);
+		live_range_t *lr;
 
 		/* 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);
-			// int rematd  = !is_zero(lpp_get_var_sol(si->lpp, lr->is_remat_var));
-
-			if(spilled && !is_end_of_block_use(lr)) {
-				ir_node *bl      = get_nodes_block(lr->user);
-				ir_node *spill   = spill_live_range(si, lr);
-				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);
+		list_for_each_entry(live_range_t, lr, &uh->head, list) {
+			if(is_spilled(si, lr) && !is_end_of_block_use(lr))
+				be_add_reload(si->senv, lr->irn, lr->user);
 		}
-    }
-
-	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);
+	for(edge = si->edges; edge; edge = edge->next) {
+		if(!is_zero(edge->in_mem_var))
+			be_add_reload_on_edge(si->senv, edge->irn, edge->bl, edge->pos);
 	}
+
+	be_insert_spills_reloads(si->senv, NULL);
 }
 
 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;
+	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   = 0;
+	obstack_init(&obst);
+	si.session         = session_env;
+	si.obst            = &obst;
+	si.dbg             = firm_dbg_register("be.ra.spillilp");
+	si.senv            = be_new_spill_env(si.dbg, session_env, cls, is_mem_phi, &si);
+	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.first_uses      = new_set(cmp_first_use, 4096);
+	si.edges           = NULL;
+	si.enable_remat    = 0;
+	si.enable_store    = 0;
 
 	firm_dbg_set_mask(si.dbg, DBG_LEVEL);
 	irg_block_walk_graph(session_env->irg, process_block, NULL, &si);
@@ -636,6 +602,7 @@ void be_spill_ilp(const be_main_session_env_t *session_env,
 #ifdef DUMP_ILP
 	{
 		FILE *f;
+		char buf[256];
 
 		ir_snprintf(buf, sizeof(buf), "spill-%s.ilp", problem_name);
 		if((f = fopen(buf, "wt")) != NULL) {
@@ -646,10 +613,11 @@ void be_spill_ilp(const be_main_session_env_t *session_env,
 #endif
 
 	DBG((si.dbg, LEVEL_1, "%F\n", session_env->irg));
-//	lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
+#ifdef SOLVE_LOCAL
 	lpp_solve_cplex(si.lpp);
-	assert(lpp_is_sol_valid(si.lpp) && "ILP not feasible");
-
+#else
+	lpp_solve_net(si.lpp, LPP_SERVER, LPP_SOLVER);
+#endif
 	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",
@@ -660,22 +628,42 @@ void be_spill_ilp(const be_main_session_env_t *session_env,
 #ifdef DUMP_SOLUTION
 	{
 		FILE *f;
+		char buf[256];
 
 		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);
+				fprintf(f, "%20s %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);
+	writeback_results(&si);
+
+#ifdef DUMP_STATS
+	{
+		FILE *f;
+
+		ir_snprintf(buf, sizeof(buf), "%s-spill.stat", problem_name);
+		if((f = fopen(buf, "wt")) != NULL) {
+			fprintf(f, "%20s: %d\n", "nodes", set_count(si.irn_use_heads));
+			fprintf(f, "%20s: %d\n", "vars", si.lpp->var_next);
+			fprintf(f, "%20s: %d\n", "csts", si.lpp->cst_next);
+			fprintf(f, "%20s: %f\n", "sol time", si.lpp->sol_time);
+			fprintf(f, "%20s: %d\n", "spills", si->stats.n_spills);
+			fprintf(f, "%20s: %d\n", "reloads", si->stats.n_reloads);
+			fprintf(f, "%20s: %d\n", "remats", si->stats.n_remat);
+			fclose(f);
+		}
+	}
+#endif
+
+	del_set(si.irn_use_heads);
+	del_set(si.live_ranges);
+	free_lpp(si.lpp);
+	obstack_free(&obst, NULL);
 }