Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2005-Mar-08
An algorithm is disclosed that allocates machine registers for IBM System/370 architecture. The above figure depicts a flow chart for an improved register allocator, the major task of which is to assign unlimited "symbolic registers" (SR) to the finite register set on the hardware. Following is a summary of each stage in the process: 1. Right Number of Names (RNN). A SR may have several disjoint lifetimes, i.e., different sequences of instructions in which it can reside in distinct real registers. RNN calculates the lifetimes of all SRs, and separates the disjoint lifetimes of each SR into different "names". Each of these names is actually assigned to a register. 2. Reduce Register Pressure (RRP) and RX Rematerialization. The register pressure at an instruction is the number of names alive at that instruction.