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 transformati...

Full description

Saved in:
Bibliographic Details
Main Authors: Cooper, Keith D., Dasgupta, Anshuman
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Costs
Design optimization
Java
Optimizing compilers
Profitability
Program processors
Runtime environment
Software and its engineering > Software notations and tools > Compilers
Software and its engineering > Software notations and tools > Compilers > Runtime environments
Virtual machining
Virtual manufacturing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1109/CGO.2006.35