Skip to main content

Trace Register Allocation Policies: Compile-time vs. Performance Trade-offs

Eisl, Josef and Marr, Stefan and Würthinger, Thomas and Mössenböck, Hanspeter (2017) Trace Register Allocation Policies: Compile-time vs. Performance Trade-offs. In: Proceedings of the 14th International Conference on Managed Languages and Runtimes. ACM-ICPS International Conference Proceeding Series . ACM, New York, USA, pp. 92-104. ISBN 978-1-4503-5340-3. (doi:10.1145/3132190.3132209) (KAR id:63807)

PDF Author's Accepted Manuscript
Language: English
Download (331kB) Preview
[thumbnail of manlang17-eisl-et-al-trace-register-allocation-policies.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


Register allocation is an integral part of compilation, regardless of whether a compiler aims for fast compilation or optimal code quality. State-of-the-art dynamic compilers often use global register allocation approaches such as linear scan. Recent results suggest that non-global trace-based register allocation approaches can compete with global approaches in terms of allocation quality. Instead of processing the whole compilation unit (i.e., method) at once, a trace-based register allocator divides the problem into linear code segments, called traces. In this work, we present a register allocation framework that can exploit the additional flexibility of traces to select different allocation strategies based on the characteristics of a trace. This provides us with fine-grained control over the trade-off between compile time and peak performance in a just-in-time compiler. Our framework features three allocation strategies: a linear-scan-based approach that achieves good code quality, a single-pass bottom-up strategy that aims for short allocation times, and an allocator for trivial traces. To demonstrate the flexibility of the framework, we select 8 allocation policies and show their impact on compile time and peak performance. This approach can reduce allocation time by 7–43 at a peak performance penalty of about 1–11 on average. For systems that do not focus on peak performance, our approach allows to adjust the time spent for register allocation, and therefore the overall compilation time, thus finding the optimal balance between compile time and peak performance according to an application's requirements.

Item Type: Book section
DOI/Identification number: 10.1145/3132190.3132209
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Stefan Marr
Date Deposited: 08 Nov 2017 21:59 UTC
Last Modified: 16 Feb 2021 13:49 UTC
Resource URI: (The current URI for this page, for reference purposes)
Marr, Stefan:
  • Depositors only (login required):


Downloads per month over past year