This paper proposes the idea of Trace Register Allocation, a register allocation approach that is tailored for just-in-time (JIT) compilation in the context of virtual machines with run-time feedback.
The basic idea is to offload costly operations such as spilling and splitting to less frequently executed branches and to focus on efficient register allocation for the hot parts of a program. This is done by performing register allocation on traces instead of on the program as a whole.
We believe that the basic approach is compatible to Linear Scan, the predominant register allocation algorithm for just-in-time compilation, in both code quality and allocation time, while our design leads to a simpler and more extensible solution. This extensibility allows us to add further enhancements in order to optimize the allocation based on the run-time profile of the application and thus to outperform current Linear Scan implementations.
I am a PhD student and research assistant at the Institute for System Software of the Johannes Kepler University Linz, Austria. In 2014 I received my MSc in computer science from the Vienna University of Technology where I was working on the CACAO VM. Currently, I am working on the Graal OpenJDK Project where my focus is on backend optimization and register allocation.