X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady.c;h=f171e66d57f59823f7a894c75b371f63830d23c1;hb=48f0393daa5d5a14ed7e3e32ee2b090759c9371e;hp=6462e1b9a82fdc1a65a2f5ab25aa5531da4d6975;hpb=fd1a2c6ca51ee2b6ff838581b79cf7a3c4553e36;p=libfirm

diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c
index 6462e1b9a..f171e66d5 100644
--- a/ir/be/bespillbelady.c
+++ b/ir/be/bespillbelady.c
@@ -47,10 +47,20 @@
 #define DBG_SLOTS  32
 #define DBG_TRACE  64
 #define DBG_WORKSET 128
-#define DEBUG_LVL 0 //(DBG_START | DBG_DECIDE | DBG_WSETS | DBG_FIX | DBG_SPILL)
 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
-typedef struct _workset_t workset_t;
+/**
+ * An association between a node and a point in time.
+ */
+typedef struct _loc_t {
+  ir_node *irn;        /**< A node. */
+  unsigned time;       /**< A use time (see beuses.h). */
+} loc_t;
+
+typedef struct _workset_t {
+	int len;			/**< current length */
+	loc_t vals[0];		/**< inlined array of the values/distances in this working set */
+} workset_t;
 
 typedef struct _belady_env_t {
 	struct obstack ob;
@@ -68,10 +78,12 @@ typedef struct _belady_env_t {
 	spill_env_t *senv;	/**< see bespill.h */
 } belady_env_t;
 
-struct _workset_t {
-	int len;			/**< current length */
-	loc_t vals[0];		/**< inlined array of the values/distances in this working set */
-};
+static int loc_compare(const void *a, const void *b)
+{
+	const loc_t *p = a;
+	const loc_t *q = b;
+	return p->time - q->time;
+}
 
 void workset_print(const workset_t *w)
 {
@@ -217,14 +229,19 @@ static INLINE void *new_block_info(struct obstack *ob) {
 static INLINE unsigned get_distance(belady_env_t *env, const ir_node *from, unsigned from_step, const ir_node *def, int skip_from_uses)
 {
 	int flags = arch_irn_get_flags(env->arch, def);
-	unsigned dist = be_get_next_use(env->uses, from, from_step, def, skip_from_uses);
+	unsigned dist;
 
 	assert(! (flags & arch_irn_flags_ignore));
 
-	/* we have to keep nonspillable nodes in the workingset */
+	/* We have to keep nonspillable nodes in the workingset */
 	if(flags & arch_irn_flags_dont_spill)
 		return 0;
 
+	dist = be_get_next_use(env->uses, from, from_step, def, skip_from_uses);
+
+	if(USES_IS_INFINITE(dist))
+		dist = USES_INFINITY;
+
 	return dist;
 }
 
@@ -296,8 +313,10 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) {
 		if (! workset_contains(ws, val)) {
 			DBG((dbg, DBG_DECIDE, "    insert %+F\n", val));
 			to_insert[demand++] = val;
-			if (is_usage)
+			if (is_usage) {
+				DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, env->instr));
 				be_add_reload(env->senv, val, env->instr);
+			}
 		}
 		else {
 			assert(is_usage || "Defined value already in workset?!?");
@@ -317,8 +336,10 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) {
 	/* Only make more free room if we do not have enough */
 	if (len > max_allowed) {
 		/* get current next-use distance */
-		for (i = 0; i < ws->len; ++i)
-			workset_set_time(ws, i, get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage));
+		for (i = 0; i < ws->len; ++i) {
+			unsigned dist = get_distance(env, env->instr, env->instr_nr, workset_get_val(ws, i), !is_usage);
+			workset_set_time(ws, i, dist);
+		}
 
 		/*
 			FIX for don't spill nodes:
@@ -603,6 +624,7 @@ static void fix_block_borders(ir_node *blk, void *data) {
 
 			/* irnb is not in memory at the end of pred, so we have to reload it */
 			DBG((dbg, DBG_FIX, "    reload %+F\n", irnb));
+			DBG((dbg, DBG_SPILL, "Reload %+F before %+F,%d\n", irnb, blk, i));
 			be_add_reload_on_edge(env->senv, irnb, blk, i);
 
 next_value:
@@ -619,16 +641,16 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t
 	belady_env_t env;
 
 	FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady");
-	//firm_dbg_set_mask(dbg, DBG_WSETS);
+	//firm_dbg_set_mask(dbg, DBG_SPILL);
 
 	/* init belady env */
 	obstack_init(&env.ob);
 	env.cenv      = chordal_env;
 	env.arch      = chordal_env->birg->main_env->arch_env;
 	env.cls       = chordal_env->cls;
-	env.n_regs    = arch_count_non_ignore_regs(env.arch, env.cls);
+	env.n_regs    = env.cls->n_regs - be_put_ignore_regs(chordal_env->birg, chordal_env->cls, NULL);
 	env.ws        = new_workset(&env, &env.ob);
-	env.uses      = be_begin_uses(chordal_env->irg, chordal_env->lv, chordal_env->birg->main_env->arch_env, env.cls);
+	env.uses      = be_begin_uses(chordal_env->irg, chordal_env->exec_freq, chordal_env->lv);
 	if(spill_env == NULL) {
 		env.senv = be_new_spill_env(chordal_env);
 	} else {
@@ -636,8 +658,6 @@ void be_spill_belady_spill_env(const be_chordal_env_t *chordal_env, spill_env_t
 	}
 	DEBUG_ONLY(be_set_spill_env_dbg_module(env.senv, dbg);)
 
-	DBG((dbg, LEVEL_1, "running on register class: %s\n", env.cls->name));
-
 	be_clear_links(chordal_env->irg);
 	/* Decide which phi nodes will be spilled and place copies for them into the graph */
 	irg_block_walk_graph(chordal_env->irg, spill_phi_walker, NULL, &env);