Tailoring Graph-coloring Register Allocation For Runtime Compilation
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 , 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.
"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.