Please use this identifier to cite or link to this item:
Title: Fast, frequency-based, integrated register allocation and instruction scheduling
Authors: Cutcutache, I. 
Wong, W.-F. 
Keywords: Code generation
Instruction scheduling
Register allocation
Issue Date: 2008
Citation: Cutcutache, I., Wong, W.-F. (2008). Fast, frequency-based, integrated register allocation and instruction scheduling. Software - Practice and Experience 38 (11) : 1105-1126. ScholarBank@NUS Repository.
Abstract: Instruction scheduling and register allocation are two of the most important optimization phases in modern compilers as they have a significant impact on the quality of the generated code. Unfortunately, the objectives of these two optimizations are in conflict with one another. The instruction scheduler attempts to exploit instruction-level parallelism and requires many operands to be available in registers. On the other hand, the register allocator wants register pressure to be kept low so that the amount of spill code can be minimized. Currently these two phases are done separately, typically in three passes: prepass scheduling, register allocation and postpass scheduling. But this separation can lead to poor results. Previous works attempted to solve the phase-ordering problem by combining the instruction scheduler with graph-coloring-based register allocators. The latter tend to be computationally expensive. Linear-scan register allocators, on the other hand, are simple, fast and efficient. In this paper, we describe our effort to integrate instruction scheduling with a linear-scan allocator. Furthermore, our integrated optimizer is able to take advantage of execution frequencies obtained through profiling. Our integrated register allocator and instruction scheduler achieved good code quality with significantly reduced compilation times. On the SPEC2000 benchmarks running on a 900 MHz Itanium II, compared with Open IMPACT, we halved the time spent in instruction scheduling and register allocation with negligible impact on execution times. Copyright © 2007 John Wiley & Sons, Ltd.
Source Title: Software - Practice and Experience
ISSN: 00380644
DOI: 10.1002/spe.860
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 24, 2021


checked on Feb 16, 2021

Page view(s)

checked on Feb 16, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.