mono/docs/local-regalloc.txt

* Proposal for the local register allocator

	The local register allocator deals with allocating registers
	for temporaries inside a single basic block, while the global 
	register allocator is concerned with method-wide allocation of 
	variables.
	The global register allocator uses callee-saved register for it's 
	purpouse so that there is no need to save and restore these registers
	at call sites.

	There are a number of issues the local allocator needs to deal with:
	*) some instructions expect operands in specific registers (for example
		the shl instruction on x86, or the call instruction with thiscall
		convention, or the equivalent call instructions on other architectures, 
		such as the need to put output registers in %oX on sparc)
	*) some instructions deliver results only in specific registers (for example
		the div instruction on x86, or the call instructionson on almost all
		the architectures).
	*) it needs to know what registers may be clobbered by an instruction
		(such as in a method call)
	*) it should avoid excessive reloads or stores to improve performance
	
	While which specific instructions have limitations is architecture-dependent,
	the problem shold be solved in an arch-independent way to reduce code duplication.
	The register allocator will be 'driven' by the arch-dependent code, but it's 
	implementation should be arch-independent.

	To improve the current local register allocator, we need to
	keep more state in it than the current setup that only keeps busy/free info.

	Possible state information is:

	free: the resgister is free to use and it doesn't contain useful info
	freeable: the register contains data loaded from a local (there is 
		also info about _which_ local it contains) as a result from previous
		instructions (like, there was a store from the register to the local)
	moveable: it contains live data that is needed in a following instruction, but
		the contents may be moved to a different register
	busy: the register contains live data and it is placed there because
		the following instructions need it exactly in that register
	allocated: the register is used by the global allocator

	The local register allocator will have the following interfaces:

	int get_register ();
		Searches for a register in the free state. If it doesn't find it,
		searches for a freeable register. Sets the status to moveable.
		Looking for a 'free' register before a freeable one should allow for
		removing a few redundant loads (though I'm still unsure if such
		things should be delegated entirely to the peephole pass).
	
	int get_register_force (int reg);
		Returns 'reg' if it is free or freeable. If it is moveable, it moves it 
		to another free or freeable register.
		Sets the status of 'reg' to busy.
	
	void set_register_freeable (int reg);
		Sets the status of 'reg' to freeable.
	
	void set_register_free (int reg);
		Sets the status of 'reg' to free.

	void will_clobber (int reg);
		Spills the register to the stack. Sets the status to freeable.
		After the clobbering has occurred, set the status to free.

	void register_unspill (int reg);
		Un-spills register reg and sets the status to moveable.

	FIXME: how is the 'local' information represented? Maybe a MonoInst* pointer.

	Note: the register allocator will insert instructions in the basic block
	during it's operation.

* Examples

	Given the tree (on x86 the right argument to shl needs to be in ecx):

	store (local1, shl (local1, call (some_arg)))

	At the start of the basic block, the registers are set to the free state.
	The sequence of instructions may be:
		instruction		register status -> [%eax %ecx %edx]
		start                                       free free free
		eax = load local1                           mov  free free
		/* call clobbers eax, ecx, edx */
		spill eax                                   free free free
		call                                        mov  free free
		/* now eax contains the right operand of the shl */
		mov %eax -> %ecx                            free busy free
		un-spill                                    mov  busy free
		shl %cl, %eax                               mov  free free
	
	The resulting x86 code is:
		mov $fffc(%ebp), %eax
		mov %eax, $fff0(%ebp)
		push some_arg
		call func
		mov %eax, %ecx
		mov $fff0(%ebp), %eax
		shl %cl, %eax
		
	Note that since shl could operate directly on memory, we could have:
	
		push some_arg
		call func
		mov %eax, %ecx
		shl %cl, $fffc(%ebp)

	The above example with loading the operand in a register is just to complicate
	the example and show that the algorithm should be able to handle it.

	Let's take another example with the this-call call convention (the first argument 
	is passed in %ecx).
	In this case, will_clobber() will be called only on %eax and %edx, while %ecx
	will be allocated with get_register_force ().
	Note: when a register is allocated with get_register_force(), it should be set
	to a different state as soon as possible.

	store (local1, shl (local1, this-call (local1)))

		instruction		register status -> [%eax %ecx %edx]
		start                                       free free free
		eax = load local1                           mov  free free
		/* force load in %ecx */
		ecx = load local1                           mov  busy free
		spill eax                                   free busy free
		call                                        mov  free free
		/* now eax contains the right operand of the shl */
		mov %eax -> %ecx                            free busy free
		un-spill                                    mov  busy free
		shl %cl, %eax                               mov  free free

	What happens when a register that we need to allocate with get_register_force ()
	contains an operand for the next instruction?

		instruction		register status -> [%eax %ecx %edx]
		eax = load local0                           mov  free free
		ecx = load local1                           mov  mov  free
		get_register_force (ecx) here.
		We have two options: 
			mov %ecx, %edx
		or:
			spill %ecx
		The first option is way better (and allows the peephole pass to
		just load the value in %edx directly, instead of loading first to %ecx).
		This doesn't work, though, if the instruction clobbers the %edx register
		(like in a this-call). So, we first need to clobber the registers
		(so the state of %ecx changes to freebale and there is no issue
		with get_register_force ()).
		What if an instruction both clobbers a register and requires it as 
		an operand? Lets' take the x86 idiv instruction as an example: it
		requires the dividend in edx:eax and returns the result in eax,
		with the modulus in edx.
	
	store (local1, div (local1, local2))
		
		instruction		register status -> [%eax %ecx %edx]
		eax = load local0                           mov  free free
		will_clobber eax, edx                       free mov  free
		force mov %ecx, %eax                        busy free free
		set %edx                                    busy free busy
		idiv                                        mov  free free
	
	Note: edx is set to free after idiv, because the modulus is not needed
	(if it was a rem, eax would have been freed).
	If we load the divisor before will_clobber(), we'll have to spill
	eax and reload it later. If we load it just after the idiv, there is no issue.
	In any case, the algorithm should give the correct results and allow the operation.
		
	Working recursively on the isntructions there shouldn't be huge issues
	with this algorithm (though, of course, it's not optimal and it may
	introduce excessive spills or register moves). The advantage over the current
	local reg allocator is that:
	1) the number of spills/moves would be smaller anyway
	2) a separate peephole pass could be able to eliminate reg moves
	3) we'll be able to remove the 'forced' spills we currently do with
		the return value of method calls

* Issues

	How to best integrate such a reg allocator with the burg stuff.

	Think about a call os sparc with two arguments: they got into %o0 and %o1
	and each of them sets the register as busy. But what if the values to put there
	are themselves the result of a call? %o0 is no problem, but for all the 
	next argument n the above algorithm would spill all the 0...n-1 registers...

* Papers

	More complex solutions to the local register allocator problem:
	http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-33.html

	Combining register allocation and instruction scheduling:
	http://citeseer.nj.nec.com/motwani95combining.html

	More on LRA euristics:
	http://citeseer.nj.nec.com/liberatore97hardness.html

	Linear-time optimal code scheduling for delayedload architectures
	http://www.cs.wisc.edu/~fischer/cs701.f01/inst.sched.ps.gz

	Precise Register Allocation for Irregular Architectures
	http://citeseer.nj.nec.com/kong98precise.html

	Allocate registers first to subtrees that need more of them.
	http://www.upb.de/cs/ag-kastens/compii/folien/comment401-409.2.pdf