Re: IMCC Register Allocation Algorithm
Bin packing looks better because I don't think SSA has been implemented yet. Linear Search looks perfect for SSA code, but Bin Packing would be better for Parrot. (Bin Packing views allocation as a bin packing problem and solves it heuristically.) On Jun 29, 2006, at 11:20 PM, Vishal Soni wrote:Hi Everyone,Currently IMCC uses a Graph Coloring based Register allocation algorithm.The implementation is a trimmed down version of Brigg's Allocator.I came across this research paper that talks about the new registerallocation algorithm "Linear Scan Allocation"for dynamically compiledlanguages. Parrot perfectly fits the mold of dynamically compiled language.The Linear Scan Allocator is faster at register allocation process and seemsto have the same execution time for the code. For more information pleaserefer to the research paper from IBM on Liner Scan Allocationhttp://www.research.ibm.com/jalapeno/papers/toplas99.pdfLet me know what your thoughts are and would it be worth implementing thisalgorithm to see how it performs compared to graph coloring algorithm.Please share your thoughts accordingly-- Thanks,Vishal Sincerely,Watson Ladd---"Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety."-- Benjamin Franklin PGP.sig Description: This is a digitally signed message part
IMCC Register Allocation Algorithm
Hi Everyone, Currently IMCC uses a Graph Coloring based Register allocation algorithm. The implementation is a trimmed down version of Brigg's Allocator. I came across this research paper that talks about the new register allocation algorithm Linear Scan Allocationfor dynamically compiled languages. Parrot perfectly fits the mold of dynamically compiled language. The Linear Scan Allocator is faster at register allocation process and seems to have the same execution time for the code. For more information please refer to the research paper from IBM on Liner Scan Allocation http://www.research.ibm.com/jalapeno/papers/toplas99.pdf Let me know what your thoughts are and would it be worth implementing this algorithm to see how it performs compared to graph coloring algorithm. Please share your thoughts accordingly -- Thanks, Vishal
Re: IMCC Register Allocation Algorithm
On Thursday 29 June 2006 20:20, Vishal Soni wrote: Let me know what your thoughts are and would it be worth implementing this algorithm to see how it performs compared to graph coloring algorithm. Please share your thoughts accordingly It'd be very useful not only to have two implementations to compare with a real benchmark on actual programs, but to do incidental IMCC cleanups while implementing the other system. (Pluggable allocators is probably too much work, but minor refactorings and documentations are always nice, if nothing else.) -- c
