X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady.c;h=c5e58b727dc4f628439b472e7fd9eed32e22ba14;hb=205396c4f4f5abe7abd6dc2350c8c398a7623afc;hp=48b0bb1109d6a5ce29306cc3a751243639773170;hpb=508dbb88a1f5caddda5d515d0d81bb300d75d5ab;p=libfirm

diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c
index 48b0bb110..c5e58b727 100644
--- a/ir/be/bespillbelady.c
+++ b/ir/be/bespillbelady.c
@@ -6,15 +6,7 @@
  *
  */
 #ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
-
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
-
-#ifdef HAVE_MALLOC_H
-#include <malloc.h>
+#include "config.h"
 #endif
 
 #include "obst.h"
@@ -29,9 +21,10 @@
 #include "iredges_t.h"
 #include "ircons_t.h"
 #include "irprintf.h"
+#include "xmalloc.h"
 
 #include "beutil.h"
-#include "bearch.h"
+#include "bearch_t.h"
 #include "bespillbelady.h"
 #include "beuses_t.h"
 #include "besched_t.h"
@@ -342,18 +335,28 @@ static void displace(belady_env_t *env, workset_t *new_vals, int is_usage) {
 
 static void belady(ir_node *block, void *env);
 
-static loc_t to_take_or_not_to_take(belady_env_t *env, ir_node* first, ir_node *node, ir_node *block, ir_loop *loop) {
+/** Decides whether a specific node should be in the start workset or not
+ *
+ * @param env      belady environment
+ * @param first
+ * @param node     the node to test
+ * @param block    the block of the node
+ * @param loop     the loop of the node
+ */
+static loc_t to_take_or_not_to_take(belady_env_t *env, ir_node* first,
+		                            ir_node *node, ir_node *block,
+									ir_loop *loop)
+{
 	be_next_use_t next_use;
 	loc_t loc;
 	loc.time = USES_INFINITY;
+	loc.irn = node;
 
 	if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, node)) {
 		loc.time = USES_INFINITY;
 		return loc;
 	}
 
-	loc.irn = node;
-
 	/* We have to keep nonspillable nodes in the workingset */
 	if(arch_irn_get_flags(env->arch, node) & arch_irn_flags_dont_spill) {
 		loc.time = 0;
@@ -364,9 +367,12 @@ static loc_t to_take_or_not_to_take(belady_env_t *env, ir_node* first, ir_node *
 	next_use = be_get_next_use(env->uses, first, 0, node, 0);
 	if(USES_IS_INFINITE(next_use.time)) {
 		// the nodes marked as live in shouldn't be dead, so it must be a phi
+		assert(is_Phi(node));
 		loc.time = USES_INFINITY;
 		DBG((dbg, DBG_START, "    %+F not taken (dead)\n", node));
-		assert(is_Phi(node));
+		if(is_Phi(node)) {
+			be_spill_phi(env->senv, node);
+		}
 		return loc;
 	}
 
@@ -421,8 +427,6 @@ static void compute_live_ins(ir_node *block, void *data) {
 				ARR_APP1(loc_t, delayed, loc);
 			else
 				ARR_APP1(loc_t, starters, loc);
-		} else {
-			be_spill_phi(env->senv, irn);
 		}
 	}
 
@@ -441,13 +445,24 @@ static void compute_live_ins(ir_node *block, void *data) {
 	}
 
 	pressure            = be_get_loop_pressure(env->loop_ana, env->cls, loop);
+	assert(ARR_LEN(delayed) <= pressure);
 	free_slots          = env->n_regs - ARR_LEN(starters);
-	free_pressure_slots = env->n_regs - pressure;
+	free_pressure_slots = env->n_regs - (pressure - ARR_LEN(delayed));
 	free_slots          = MIN(free_slots, free_pressure_slots);
 	/* append nodes delayed due to loop structure until start set is full */
 	for (i = 0; i < ARR_LEN(delayed) && i < free_slots; ++i) {
 		DBG((dbg, DBG_START, "    delayed %+F taken\n", delayed[i].irn));
 		ARR_APP1(loc_t, starters, delayed[i]);
+		delayed[i].irn = NULL;
+	}
+
+	/* spill all delayed phis which didn't make it into start workset */
+	for (i = ARR_LEN(delayed) - 1; i >= 0; --i) {
+		ir_node *irn = delayed[i].irn;
+		if (irn && is_Phi(irn)) {
+			DBG((dbg, DBG_START, "    spilling delayed phi %+F\n", irn));
+			be_spill_phi(env->senv, irn);
+		}
 	}
 	DEL_ARR_F(delayed);
 
@@ -651,16 +666,27 @@ next_value:
 	}
 }
 
-void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) {
+/**
+ * Do spilling for a register class on a graph using the belady heuristic.
+ * In the transformed graph, the register pressure never exceeds the number
+ * of available registers.
+ *
+ * @param birg  The backend graph
+ * @param cls   The register class to spill
+ */
+static void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) {
 	be_spill_belady_spill_env(birg, cls, NULL);
 }
 
 void be_spill_belady_spill_env(be_irg_t *birg, const arch_register_class_t *cls, spill_env_t *spill_env) {
 	belady_env_t env;
 	ir_graph *irg = be_get_birg_irg(birg);
+	int n_regs;
 
-	FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady");
-	//firm_dbg_set_mask(dbg, DBG_SPILL);
+	/* some special classes contain only ignore regs, nothing to do then */
+	n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
+	if(n_regs == 0)
+		return;
 
 	be_invalidate_liveness(birg);
 	be_assure_liveness(birg);
@@ -674,7 +700,7 @@ void be_spill_belady_spill_env(be_irg_t *birg, const arch_register_class_t *cls,
 	env.arch      = birg->main_env->arch_env;
 	env.cls       = cls;
 	env.lv        = be_get_birg_liveness(birg);
-	env.n_regs    = env.cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
+	env.n_regs    = n_regs;
 	env.ws        = new_workset(&env, &env.ob);
 	env.uses      = be_begin_uses(irg, env.lv);
 	env.loop_ana  = be_new_loop_pressure(birg);
@@ -710,6 +736,7 @@ void be_init_spillbelady(void)
 	};
 
 	be_register_spiller("belady", &belady_spiller);
+	FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady");
 }
 
 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady);