Josef Eisl, David Leopoldseder, Hanspeter Mössenböck,
"Parallel Trace Register Allocation"
: Proceeding ManLang´18 Proceedings of the 15th International Conference on Managed Languages & Runtimes Article No. 7, ACM New York, NY, USA, 9-2018, ISBN: 978-1-4503-6424-9
Parallel Trace Register Allocation
Sprache des Titels:
Proceeding ManLang´18 Proceedings of the 15th International Conference on Managed Languages & Runtimes Article No. 7
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.