X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=mono%2Fmini%2Flinear-scan.c;h=df681a68ac1bfe2210099fb04e1d977c4aa78bc3;hb=95149da03ea22c4e6f7e9feda77ea2808fbf6586;hp=a77ef1ba5571475535efb65b57d41ff40d1036f3;hpb=538d3bb80572334c18ae117ea7703406a4a22872;p=mono.git

diff --git a/mono/mini/linear-scan.c b/mono/mini/linear-scan.c
index a77ef1ba557..df681a68ac1 100644
--- a/mono/mini/linear-scan.c
+++ b/mono/mini/linear-scan.c
@@ -10,6 +10,10 @@
 #include "mini.h"
 #include <mono/metadata/debug-helpers.h>
 
+#ifndef DISABLE_JIT
+
+static void mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask);
+
 GList *
 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
 {
@@ -71,10 +75,16 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_ma
 {
 	GList *l, *a, *active = NULL;
 	MonoMethodVar *vmv, *amv;
-	int max_regs, gains [sizeof (regmask_t) * 8];
+	int max_regs, n_regvars;
+	int gains [sizeof (regmask_t) * 8];
 	regmask_t used_regs = 0;
 	gboolean cost_driven;
 
+ 	if (vars && (((MonoMethodVar*)vars->data)->interval != NULL)) {
+ 		mono_linear_scan2 (cfg, vars, regs, used_mask);
+ 		return;
+ 	}
+
 	cost_driven = TRUE;
 
 #ifdef DEBUG_LSCAN
@@ -105,19 +115,21 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_ma
 			vmv->range.last_use.abs_pos);
 #endif
 		/* expire old intervals in active */
-		while (active) {
-			amv = (MonoMethodVar *)active->data;
+		if (!cfg->disable_reuse_registers) {
+			while (active) {
+				amv = (MonoMethodVar *)active->data;
 
-			if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
-				break;
+				if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
+					break;
 
 #ifdef DEBUG_LSCAN
-			printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos, 
-				amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
+				printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos, 
+						amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 #endif
-			active = g_list_delete_link (active, active);
-			regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
-			gains [amv->reg] += amv->spill_costs;
+				active = g_list_delete_link (active, active);
+				regs = g_list_prepend (regs, GINT_TO_POINTER (amv->reg));
+				gains [amv->reg] += amv->spill_costs;
+			}
 		}
 
 		if (active && g_list_length (active) == max_regs) {
@@ -185,44 +197,33 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_ma
 		gains [amv->reg] += amv->spill_costs;
 	}
 
+	n_regvars = 0;
 	for (l = vars; l; l = l->next) {
 		vmv = l->data;
 		
 		if (vmv->reg >= 0)  {
 			if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
+				if (cfg->verbose_level > 2) {
+					printf ("ALLOCATED R%d(%d) TO HREG %d COST %d\n", cfg->varinfo [vmv->idx]->dreg, vmv->idx, vmv->reg, vmv->spill_costs);
+				}
 				cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 				cfg->varinfo [vmv->idx]->dreg = vmv->reg;
-				if (cfg->verbose_level > 2)
-					printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
+				n_regvars ++;
 			} else {
 				if (cfg->verbose_level > 2)
-					printf ("COSTLY: %s R%d C%d C%d %s\n", mono_method_full_name (cfg->method, TRUE), vmv->idx, vmv->spill_costs, mono_arch_regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
+					printf ("COSTLY: R%d C%d C%d %s\n", vmv->idx, vmv->spill_costs, mono_arch_regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
 				vmv->reg = -1;
 			}
 		}
 
 		if (vmv->reg == -1) {
-			if ((vmv->range.first_use.abs_pos >> 16) == (vmv->range.last_use.abs_pos >> 16)) {
-				/*
-				 * This variables is only used in a single basic block so
-				 * convert it into a virtual register.
-				 * FIXME: This increases register pressure in the local
-				 * allocator, leading to the well known 'branches inside
-				 * basic blocks screw up the allocator' problem.
-				 */
-#if 0
-				//#ifdef MONO_ARCH_HAS_XP_LOCAL_REGALLOC
-				cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
-				cfg->varinfo [vmv->idx]->dreg = mono_regstate_next_int (cfg->rs);
-#endif
-			}
-			else {
-				if (cfg->verbose_level > 2)
-					printf ("NOT REGVAR: %d\n", vmv->idx);
-			}
+			if (cfg->verbose_level > 2)
+				printf ("NOT REGVAR: %d\n", vmv->idx);
 		}
 	}
 
+	mono_jit_stats.regvars += n_regvars;
+
 	/* Compute used regs */
 	used_regs = 0;
 	for (l = vars; l; l = l->next) {
@@ -244,3 +245,269 @@ mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_ma
 	g_list_free (vars);
 }
 
+static gint
+compare_by_interval_start_pos_func (gconstpointer a, gconstpointer b)
+{
+	MonoMethodVar *v1 = (MonoMethodVar*)a;
+	MonoMethodVar *v2 = (MonoMethodVar*)b;
+
+	if (v1 == v2)
+		return 0;
+	else if (v1->interval->range && v2->interval->range)
+		return v1->interval->range->from - v2->interval->range->from;
+	else if (v1->interval->range)
+		return -1;
+	else
+		return 1;
+}
+
+#if 0
+#define LSCAN_DEBUG(a) do { a; } while (0)
+#else
+#define LSCAN_DEBUG(a)
+#endif
+
+/* FIXME: This is x86 only */
+static inline guint32
+regalloc_cost (MonoCompile *cfg, MonoMethodVar *vmv)
+{
+	MonoInst *ins = cfg->varinfo [vmv->idx];
+
+	/* Load if it is an argument */
+	return (ins->opcode == OP_ARG) ? 1 : 0;
+}
+
+void
+mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
+{
+	GList *unhandled, *active, *inactive, *l;
+	MonoMethodVar *vmv;
+	gint32 free_pos [sizeof (regmask_t) * 8];
+	gint32 gains [sizeof (regmask_t) * 8];
+	regmask_t used_regs = 0;
+	int n_regs, n_regvars, i;
+
+	for (l = vars; l; l = l->next) {
+		vmv = l->data;
+		LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg->varinfo [vmv->idx]->dreg, vmv->range.first_use.abs_pos, 
+							 vmv->range.last_use.abs_pos, vmv->spill_costs));
+	}
+
+	LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg->method, TRUE)));
+
+	n_regs = g_list_length (regs);
+	memset (gains, 0, n_regs * sizeof (gint32));
+	unhandled = g_list_sort (g_list_copy (vars), compare_by_interval_start_pos_func);
+	active = NULL;
+	inactive = NULL;
+
+	while (unhandled) {
+		MonoMethodVar *current = unhandled->data;
+		int pos, reg, max_free_pos;
+		gboolean changed;
+
+		unhandled = g_list_delete_link (unhandled, unhandled);
+
+		LSCAN_DEBUG (printf ("Processing R%d: ", cfg->varinfo [current->idx]->dreg));
+		LSCAN_DEBUG (mono_linterval_print (current->interval));
+		LSCAN_DEBUG (printf ("\n"));
+
+		if (!current->interval->range)
+			continue;
+			
+		pos = current->interval->range->from;
+
+		/* Check for intervals in active which expired or inactive */
+		changed = TRUE;
+		/* FIXME: Optimize this */
+		while (changed) {
+			changed = FALSE;
+			for (l = active; l != NULL; l = l->next) {
+				MonoMethodVar *v = (MonoMethodVar*)l->data;
+
+				if (v->interval->last_range->to < pos) {
+					active = g_list_delete_link (active, l);
+					LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
+					changed = TRUE;
+					break;
+				}
+				else if (!mono_linterval_covers (v->interval, pos)) {
+					inactive = g_list_append (inactive, v);
+					active = g_list_delete_link (active, l);
+					LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg->varinfo [v->idx]->dreg));
+					changed = TRUE;
+					break;
+				}
+			}
+		}
+
+		/* Check for intervals in inactive which expired or active */
+		changed = TRUE;
+		/* FIXME: Optimize this */
+		while (changed) {
+			changed = FALSE;
+			for (l = inactive; l != NULL; l = l->next) {
+				MonoMethodVar *v = (MonoMethodVar*)l->data;
+
+				if (v->interval->last_range->to < pos) {
+					inactive = g_list_delete_link (inactive, l);
+					LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
+					changed = TRUE;
+					break;
+				}
+				else if (mono_linterval_covers (v->interval, pos)) {
+					active = g_list_append (active, v);
+					inactive = g_list_delete_link (inactive, l);
+					LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg->varinfo [v->idx]->dreg));
+					changed = TRUE;
+					break;
+				}
+			}
+		}
+
+		/* Find a register for the current interval */
+		for (i = 0; i < n_regs; ++i)
+			free_pos [i] = ((gint32)0x7fffffff);
+
+		for (l = active; l != NULL; l = l->next) {
+			MonoMethodVar *v = (MonoMethodVar*)l->data;
+
+			if (v->reg >= 0) {
+				free_pos [v->reg] = 0;
+				LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v->reg, v->spill_costs));
+			}
+		}
+
+		for (l = inactive; l != NULL; l = l->next) {
+			MonoMethodVar *v = (MonoMethodVar*)l->data;
+			gint32 intersect_pos;
+
+			if (v->reg >= 0) {
+				intersect_pos = mono_linterval_get_intersect_pos (current->interval, v->interval);
+				if (intersect_pos != -1) {
+					free_pos [v->reg] = intersect_pos;
+					LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v->reg, intersect_pos));
+				}
+			}
+		}
+
+		max_free_pos = -1;
+		reg = -1;
+		for (i = 0; i < n_regs; ++i)
+			if (free_pos [i] > max_free_pos) {
+				reg = i;
+				max_free_pos = free_pos [i];
+			}
+
+		g_assert (reg != -1);
+
+		if (free_pos [reg] >= current->interval->last_range->to) {
+			/* Register available for whole interval */
+			current->reg = reg;
+			LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, cfg->varinfo [current->idx]->dreg));
+
+			active = g_list_append (active, current);
+			gains [current->reg] += current->spill_costs;
+		}
+		else {
+			/* 
+			 * free_pos [reg] > 0 means there is a register available for parts
+			 * of the interval, so splitting it is possible. This is not yet
+			 * supported, so we spill in this case too.
+			 */
+
+			/* Spill an interval */
+
+			/* FIXME: Optimize the selection of the interval */
+
+			if (active) {
+				GList *min_spill_pos;
+#if 0
+				/* 
+				 * This favors registers with big spill costs, thus larger liveness ranges,
+				 * thus actually leading to worse code size.
+				 */
+				guint32 min_spill_value = G_MAXINT32;
+
+				for (l = active; l != NULL; l = l->next) {
+					vmv = (MonoMethodVar*)l->data;
+
+					if (vmv->spill_costs < min_spill_value) {
+						min_spill_pos = l;
+						min_spill_value = vmv->spill_costs;
+					}
+				}
+#else
+				/* Spill either the first active or the current interval */
+				min_spill_pos = active;
+#endif
+				vmv = (MonoMethodVar*)min_spill_pos->data;
+				if (vmv->spill_costs < current->spill_costs) {
+				//				if (vmv->interval->last_range->to < current->interval->last_range->to) {
+					gains [vmv->reg] -= vmv->spill_costs;
+					vmv->reg = -1;
+					LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg->varinfo [vmv->idx]->dreg));
+					active = g_list_delete_link (active, min_spill_pos);
+				}
+				else
+					LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current->spill_costs));
+			}
+			else
+				LSCAN_DEBUG (printf ("\tSpilled current\n"));
+		}
+	}
+
+	/* Decrease the gains by the cost of saving+restoring the register */
+	for (i = 0; i < n_regs; ++i) {
+		if (gains [i]) {
+			/* FIXME: This is x86 only */
+			gains [i] -= cfg->method->save_lmf ? 1 : 2;
+			if (gains [i] < 0)
+				gains [i] = 0;
+		}
+	}
+
+	/* Do the actual register assignment */
+	n_regvars = 0;
+	for (l = vars; l; l = l->next) {
+		vmv = l->data;
+
+		if (vmv->reg >= 0) {
+			int reg_index = vmv->reg;
+
+			/* During allocation, vmv->reg is an index into the regs list */
+			vmv->reg = GPOINTER_TO_INT (g_list_nth_data (regs, vmv->reg));
+
+			if ((gains [reg_index] > regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
+				if (cfg->verbose_level > 2)
+					printf ("REGVAR R%d G%d C%d %s\n", cfg->varinfo [vmv->idx]->dreg, gains [reg_index], regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
+				cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
+				cfg->varinfo [vmv->idx]->dreg = vmv->reg;
+				n_regvars ++;
+			}
+			else {
+				if (cfg->verbose_level > 2)
+					printf ("COSTLY: %s R%d G%d C%d %s\n", mono_method_full_name (cfg->method, TRUE), cfg->varinfo [vmv->idx]->dreg, gains [reg_index], regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
+				vmv->reg = -1;
+			}
+		}
+	}
+
+	mono_jit_stats.regvars += n_regvars;
+
+	/* Compute used regs */
+	used_regs = 0;
+	for (l = vars; l; l = l->next) {
+		vmv = l->data;
+		
+		if (vmv->reg >= 0)
+			used_regs |= 1LL << vmv->reg;
+	}
+
+	*used_mask |= used_regs;
+
+	g_list_free (active);
+	g_list_free (inactive);
+}
+
+#endif /* #ifndef DISABLE_JIT */