Google Summer of Code: Rodrigo Sol
A little while ago, Rodrigo Sol at the Federal University of Minas Gerais submitted a Google Summer of Code proposal to create a new register allocator for TraceMonkey. I’m pleased to announce his proposal was accepted!
Rodrigo’s project idea is to implement Register Allocation By Puzzle Solving, a paper in PLDI 2008 by his advisor, Fernando Pereira, and Jens Palsberg. The paper describes a register allocation algorithm based on a model of fitting puzzle pieces (program values) into a board (the register file). Their results show allocation speed equal to the fastest good allocators (such as LLVMs) and also high performance for the generated code (in the register allocation aspect), which sounds like exactly what we’d love to have in TraceMonkey.
The end result will be a new register allocator for nanojit, TraceMonkey’s back-end code generator. Initially, I’m hoping Rodrigo’s allocator will reduce the number of spills and register-to-register moves, which should improve performance by an as yet unknown amount on all TraceMonkey applications. It should also help other applications that use nanojit, such as the simple regular expression compiler I coded up a while back. (Side note: if anyone out there is looking for a compiler-related project, extending and/or redesigning that compiler might be fun.) Later on, I hope the new allocator will help enable other TraceMonkey advances, such as carrying values in registers across trace loop edges and from one trace to another.
Rodrigo has a wiki for his project, including a blog and links to related articles and papers.