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