2002-05-03 Dietmar Maurer <dietmar@ximian.com>

	* emit-x86.c (arch_allocate_regs): improved register allocation

svn path=/trunk/mono/; revision=4246

1 files changed, 64 insertions, 0 deletions

diff --git a/docs/jit-regalloc b/docs/jit-regalloc
new file mode 100644
index 00000000000..ca54b4564f9
--- /dev/null
+++ b/docs/jit-regalloc
@@ -0,0 +1,64 @@
+Register Allocation
+===================
+
+The current JIT implementation uses a tree matcher to generate code. We use a
+simple algorithm to allocate registers in trees, and limit the number of used
+temporary register to 4 when evaluating trees. So we can use 2 registers for
+global register allocation.  
+
+Register Allocation for Trees
+=============================
+
+We always evaluate trees from left to right. When there are no more registers
+available we need to spill values to memory. Here is the simplified algorithm.
+
+gboolean 
+tree_allocate_regs (tree, exclude_reg)
+{
+	if (!tree_allocate_regs (tree->left, -1))
+	        return FALSE;
+  
+	if (!tree_allocate_regs (tree->right, -1)) {
+	  
+		tree->left->spilled == TRUE;
+
+		free_used_regs (tree->left);
+
+		if (!tree_allocate_regs (tree->right, tree->left->reg))
+			return FALSE;
+	}
+
+	free_used_regs (tree->left);
+	free_used_regs (tree->right);
+
+	/* try to allocate a register (reg != exclude_reg) */
+	if ((tree->reg = next_free_reg (exclude_reg)) != -1)
+	        return TRUE;
+  
+	return FALSE;
+}
+
+The emit routing actually spills the registers:
+
+tree_emit (tree)
+{
+
+	tree_emit (tree->left);
+
+	if (tree->left->spilled)
+		save_reg (tree->left->reg);
+
+	tree_emit (tree->right);
+	
+	if (tree->left->spilled)
+		restore_reg (tree->left->reg);
+
+
+	emit_code (tree);
+}
+
+
+Global Register Allocation
+==========================
+
+TODO.