Register allocation is a mandatory task for almost every compiler
and consumes a significant portion of compile time. In a just-in-time
compiler, compile time is a particular issue because compilation
happens during program execution and contributes to the overall
application run time. Parallelization can help here. We developed a
theoretical model for parallel register allocation and show that it
can be used in practice without a negative impact on the quality of
the allocation result. Doing so reduces compilation latency, i.e., the
duration until the result of a compilation is available.
Our analysis shows that parallelization can theoretically decrease
allocation latency by almost 50%. We implemented an initial prototype which reduces the register allocation latency by 28% when
using four threads, compared to the single-threaded allocation.