Register allocation is a mandatory task for almost every compiler
and consumes a signicant 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
. We implemented an initial pro-
totype which reduces the register allocation latency by
using four threads, compared to the single-threaded allocation.