Register Allocator

[Vishal Soni]

Hi,

I read the #parrotsketch log from today. I cannot join the IRC now. The
Graph based Register allocation is good for statically compiled languages
like C. The real value of Graph Based allocation comes when you have limited
number of registers and have to spill some of the variables to memory. Which
variable goes to memory is decided by a cost function. The other issue might
be Def-Usage (DU) chains. In a 9000 lines sub this might be getting to
large. Going to Single Static Assignment(SSA) form eliminates the need of DU
chains. I plan on implementing SSA in Byte Code Generator. But that is
future. I need some decisions to be made on POST nodes to continue my work
with BCG.

In Parrot we do not have to worry about spilling as we can assume we have
infinite number of registers of I,P,N and C type. Linear Scan allocation is
good but would require some time to implement as it goes after the data
collected from live varaible analysis.

The simpler solution is to not do any optimization for reducing the number
of registers. This is fine for now as we are in a development phase. IMHO
getting things working is more important than optimization.

I should be able to hack up a vanilla register allocation scheme that does
no live variable analysis to find overlapping registers to reduce the number
of registers. Currently I have implemented this scheme in Byte Code
Generator (compilers/bcg/src/bcg_reg_alloc_vanilla.c). All this does is it
makes sure each varaible gets a unique register. The quality of the code
generate might not be good but this should be very fast in compile time
performance compared to Graph Based allocator. This should be simple to do
and we can still keep the graph allocator but only run it when the
optimization flag -Ox is used.

Let me know your thoughts. I'll try to catch you guys later on IRC.

--
Thanks,
Vishal

[Chromatic]

On Tuesday 15 August 2006 12:23:34 Vishal Soni wrote:

> I should be able to hack up a vanilla register allocation scheme that does
> no live variable analysis to find overlapping registers to reduce the
> number of registers. Currently I have implemented this scheme in Byte Code
> Generator (compilers/bcg/src/bcg_reg_alloc_vanilla.c). All this does is it
> makes sure each varaible gets a unique register. The quality of the code
> generate might not be good but this should be very fast in compile time
> performance compared to Graph Based allocator. This should be simple to do
> and we can still keep the graph allocator but only run it when the
> optimization flag -Ox is used.
>
> Let me know your thoughts. I'll try to catch you guys later on IRC.

Rakudo is nearly in a state where this could come in handy.

-- c