Register Allocation Via Coloring
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Auslander, MA: AUTHOR [+6]
Overview of Register Allocation: A method of operation of the Register Allocation Phase of a typical PL/I compiler is herein described. It is the responsibility of this phase to map the unlimited number of symbolic registers assumed in the intermediate language into the 17 real machine registers, namely, the 16 general-purpose registers (R0-R15) and the condition-code (CC), which we assume for illustrative purposes in this article.
Register Allocation Via Coloring
1. Overview of Register Allocation:
A method of operation of the Register Allocation Phase of a typical PL/I compiler is herein described. It is the responsibility of this phase to map the unlimited number of symbolic registers assumed in the intermediate language into the 17 real machine registers, namely, the 16 general-purpose registers (R0- R15) and the condition-code (CC), which we assume for illustrative purposes in this article.
The essence of this approach is that it is uniform and systematic. Compiler back-ends must deal with the idiosyncrasies of the machine instructions, for example, register pairs, the fact that register RO is an invalid base register, and that the contents of some machine registers are destroyed as a side-effect of particular instructions.
In the present approach, all these idiosyncrasies are entered in a uniform manner in our data structure, the interference graph. Afterwards this data structure is manipulated in a very systematic way.
Also, the approach has a rather different personality than traditional ones because global register allocation across entire procedures is done. Furthermore, except for the register which always contains the address of the DSA (Dynamic Storage Area) and is the anchor for all addressability, all other registers are considered to be part of a uniform pool and all computations compete on an equal basis for these registers. Most compilers reserve subsets of the registers for specific purposes; we do the exact opposite.
In the compiler a deliberate effort is made to make things as hard as possible for register allocation, i.e., to keep as many computations as possible in registers rather than in storage. For example, automatic scalars are usually kept in registers rather than in the DSA, and subroutine linkage also attempts to pass as much information as possible through registers. It is the responsibility of code generation and optimization to take advantage of the unlimited number of registers allowed in the intermediate language in order to minimize the number of loads and stores in the program, since these are much more expensive than register-to-register instructions. Then hopefully register allocation will map all these registers into the 17 that are actually available in the hardware. If not, it is register allocation's responsibility to put back into the object program the minimum amount of spill code, i.e., of stores and reloads of registers, that is needed.
As long as no spill code need be introduced, it is believed that this approach to register allocation does a better job than can be done by hand-coders. For example, if there is a slight change in a program, when it is recompiled, the Register Allocation Phase may produce a completely different allocation to accommodate the change. A hand-coder would be irresponsible to proceed in such a fashion. It is also believed that the present compiler succeeds in keeping things in registe...