mono/docs/jit-regalloc

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.