Load/Store Range Analysis for Global Register Allocation

Abstract

Live range splitting techniques divide the live ranges of variables into live range segments to improve global register allocation. We present a new technique for live range splitting called load/store range analysis. This analysis localizes the profits and the register requirements of every access to every variable to provide a fine granularity of candidates for register allocation. Load/Store range analysis is based on the data flow analysis algorithm for def-use chaining. Experiments on a small suite of C and FORTRAN benchmark programs show that a graph coloring register allocator operating on load/store ranges often provides better allocations than the same allocator operating on live ranges. Experimental results also show that the computational cost of using load/store ranges for register allocation is moderately more than the cost of using live ranges. 1 Introduction The goal of register allocation is to map variables in an intermediate language program to either registers or mem...