Browse Prior Art Database

Least Recently Used Algorithm to Assist Register Allocation

IP.com Disclosure Number: IPCOM000051141D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Karp, AH: AUTHOR [+2]

Abstract

It is important to minimize the number of vector registers which have contents saved on task switches and subroutine calls. The proposed algorithm and associated hardware is efficient enough to allow the use of dynamic register allocation instead of the currently used static method.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Least Recently Used Algorithm to Assist Register Allocation

It is important to minimize the number of vector registers which have contents saved on task switches and subroutine calls. The proposed algorithm and associated hardware is efficient enough to allow the use of dynamic register allocation instead of the currently used static method.

Consider a machine having N vector registers. A least recently used (LRU) register is proposed consisting of N slots, each N bits wide initialized to all 1's. The algorithm is:
1. Fetch an instruction.
2. If only one register is used in the instruction, find the

rightmost zero bit in the slot. If more than one

register is used, use the slot with its rightmost 0 bit

closest to the left. (See the example.)
3. Set the slots corresponding to registers used in the

instruction to all zeros with a 1 in the rightmost position.
4. For those registers with a 0 in the bit slice selected in

step 2, shift the slots left 1 position, propagating

the low order 1.

At any time, the least recently used registers are those with 1's farthest to the left in the register. The selective shifting in step 4 can be achieved by shifting all the slots and using the selected slice to gate the store-back into the LRU.

To select the K least recently used registers, the following algorithm is proposed.
1. Set I = 0.
2. Examine bit I in each slot and find O<J<N values of 1.
3. Record the registers found, and set these slots to all zeros

with a 1 in the rightmost position.
4. If the total found is sufficient, it is then done; else, set

I equals I + 1, and repeat from step 2.

For example,...