Browse Prior Art Database

Register Allocation

IP.com Disclosure Number: IPCOM000060310D
Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 6 page(s) / 48K

Publishing Venue

IBM

Related People

Davis, MA: AUTHOR

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 21% of the total text.

Page 1 of 6

Register Allocation

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. Since each name needs a real register, the register pressure at every point in the program must be less than or equal to the number of available hardware registers for register allocation to succeed. RRP reduces register pressure at points where it is too high by "spilling", i.e., storing some live values into memory, and later reloading them. Earlier compiler phases express all operations in terms of register-to-register (RR) instructions; this is most efficient when an SR is used several times. However, if the SR is only used once, it is often possible to employ a single memory to register (RX) instruction to achieve the same effect as the two instruction sequence of: Load, RR instruction. RX Rematerialization converts such sequences into the equivalent RX instruction where possible. 3. Right Number of Names (RNN). RNN is run again after spilling because the STORE/LOAD pairs break single lifetimes into several lifetimes, and RX rematerialization eliminates the need for some registers altogether, so RNN yields a result different from the first time. More important, it is easier to allocate registers for the resulting "names". 4. Build Interference Graph (BIG). Two names are said to interfere if their lifetimes overlap. The interference relation is represented by the interference graph (IG), which is an undirected graph with names as nodes, and edges connecting interfering names. A coloring of a graph is an assignment of integers (real registers) to nodes (names) such that adjacent nodes (interfering names) are assigned different integers (real registers).

Register allocation is equivalent to coloring the interference graph with real register colors. BIG constructs the interference graph by examining each instruction and adding edges between all names which are live at that point. The IG is also exploited to express some of the irregularities of the hardware. For instance, to prevent register zero (R0) from being used as a base or index register, R0 is made to interfere with every name appearing as a base or index in some instruction. This process is also accomplished during the scan of the program. 5. Co...