Abstract:

Just-in-time compilers are invoked during application execution and therefore need to ensure fast compilation times. Consequently, runtime compiler designers are averse to implementing compile-time intensive optimization algorithms. Instead, they tend to select faster but less effective transformations. In this paper, we explore this trade-off for an important optimization ⓠglobal register allocation. We present a graph-coloring register allocator that has been redesigned for runtime compilation. Compared to Chaitin-Briggs [7], a standard graph-coloring technique, the reformulated algorithm requires considerably less allocation time and produces allocations that are only marginally worse than those of Chaitin-Briggs. Our experimental results indicate that the allocator performs better than the linear-scan and Chaitin-Briggs allocators on most benchmarks in a runtime compilation environment. By increasing allocation efficiency and preserving optimization quality, the presented algorithm increases the suitability and profitability of a graph-coloring register allocation strategy for a runtime compiler.

Published:

"Tailoring Graph-coloring Register Allocation For Runtime Compilation", Keith D. Cooper and Anshuman Dasgupta.
Proceedings of the 2006 International Symposium on Code Generation and Optimization (CGO'06), New York, New York, 2006.

Download:

• Tailoring Graph-coloring Register Allocation For Runtime Compilation (PDF)