Register Allocation in Optimizing Compilers

The subject of this treatise is code optimization in compilers. I discuss both general strategies of optimizing compiler design and specific techniques for achieving individual optimizations. I am only secondarily interested in introducing new optimizations and algorithms; my goal is to integrate a comprehensive set of optimizations into a retargetable compiler. I introduce new formalizations of techniques that are, in many cases, already known. A compiler is retargetable if it can easily be adapted to changes in the machine for which it generates code. These include changing to a completely different machine (different instruction set). In the broadest sense they also include changes to the run-time conventions. Historically, it has proven to be difficult to achieve both retargetability and a high degree of code optimization with a single compiler design. I describe the design and implementation of part of a compiler that achieves both of those goals. I focus on a set of techniques somewhat loosely known as register allocation. This is the process of mapping data items in the source program onto storage locations in the target machine. Data items include variables, results of expression evaluations, results of hidden (implicit) computations, and frequently-used constants. Storage locations include accumulators, index registers, base registers, and (not least) memory locations.