Tailoring graph-coloring register allocation for runtime compilation
Tailoring graph-coloring register allocation for runtime compilation
复制标题
DOI：
10.1109/cgo.2006.35
复制
发表时间：
2006-03
期刊：
影响因子：
--
通讯作者：
K. Cooper;A. Dasgupta
中科院分区：
文献类型：
--
作者：
K. Cooper;A. Dasgupta
即时编译器在应用程序执行期间被调用，因此需要确保快速编译时间。因此，运行时编译器设计者不愿意实现编译时密集型优化算法。相反，他们倾向于选择更快但效率较低的转型。在本文中，我们探讨了一种重要优化的权衡——全局寄存器分配。我们提出了一个图形着色寄存器分配器，它已针对运行时编译进行了重新设计。与标准图形着色技术 Chaitin-Briggs (1994) 相比，重新制定的算法需要相当少的分配时间，并且产生的分配仅比 Chaitin-Briggs 的分配稍差。我们的实验结果表明，在运行时编译环境中的大多数基准测试中，分配器的性能优于线性扫描和 Chaitin-Briggs 分配器。通过提高分配效率和保持优化质量，所提出的算法提高了运行时编译器的图形着色寄存器分配策略的适用性和盈利能力。
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 (1994), 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.