Fast, frequency-based, integrated register allocation and instruction scheduling

Abstract

Instruction scheduling and register allocation are two of the important optimization phases in modern compilers as they have 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 ILP and requires many operands to be available in registers, while the register allocator wants register pressure to be kept low in order to minimize the spill code. Currently these two phases are done separately, typically in three passes: pre-pass scheduling, register allocation and post-pass scheduling. But this separation can lead to poor results. Previous research attempted to solve the phase ordering problem by combining instruction scheduling with graph-coloring register allocators, which are computationally expensive. Linear scan register allocators, on the other hand, are simple, fast and efficient. In this thesis we describe our effort to integrate instruction scheduling with a linear scan allocator.