Register-sensitive selection, duplication, and sequencing of instructions

Abstract

In this paper, we present a new framework for selecting, duplicating and sequencing instructions so as to decrease register pressure. The motivation for this work is to target current and future high-performance processors where reductions in register pressure in the compiled programs can lead to improved performance. For instruction selection and duplication, a unique feature of our approach is the ability to perform these transformations on intermediate-language instructions in a general dependence graph that contains both true and non-true dependences, unlike past work that restricted their attention to a single expression tree or a single expression dag. For instruction sequencing, we present a new algorithm for reducing register pressure that is based on backwards scheduling. We present preliminary performance results to validate our approach. Our results show that register-sensitive instruction duplication can deliver significant speedups (up to 1.22×) for the SPECint95 benchmarks on an IA-32 processor. We also show that register-sensitive sequencing delivers smaller speedups (up to 1.12×) for the SPECjvm and Java Grande benchmarks on a PowerPC processor (when utilizing two-thirds of its registers). We expect to see more significant speedups due to register-sensitive sequencing on processors with fewer registers than the PowerPC (such as the IA-32).