Compiler allocating a register to a data item used between a use and store of another data item previously allocated to the register

Apparatus for allocating registers in a compiler, comprising:

• a) means for identifying and recording temporary items in a unit of code, each of said temporary items requiring storage;
• b) means for identifying and recording a lifetime of each one of said temporary items, said lifetime of said each of said temporary items being an interval of time between the creation and the last use of said each of said of said temporary items in said unit of code;
• c) means for identifying and recording holes in the lifetime of each one of said temporary items, said hole in the lifetime of said each one of said temporary items being an interval of time between a use and a store of said each one of said temporary items in said unit of code;
• and
• d) means responsive to said recorded temporary items, lifetimes of temporary items and holes in lifetime for allocating to one of said registers one of said temporary items having a lifetime fitting within one of said holes of a second of said temporary items, said second temporary item having been previously allocated to said one register.

A method of allocating registers in an optimization of a unit of code for running on a computer architecture having a given number of registers, comprising the steps of:

• a) identifying temporary items in said unit of code;
• b) identifying a lifetime of each one of said temporary items, said lifetime of said each of said temporary items being an interval of time between the creation and the last use of said each of said of said temporary items in said unit of code;
• c) identifying holes in the lifetime of each one of said temporary items said hole in the lifetime of said each one of said temporary items being an interval of time between a use and a store of said each one of said temporary items within said unit of code;
• and
• d) allocating said registers to as many of said temporary items as there are registers available in said given number at any point in said unit, including storing for each register in separate lists said identified temporary items and said identified holes and allocating registers to the ones of said temporary items whose lifetimes fit within said holes.

Apparatus for allocating registers in an optimization stage of a compiler for generating object code for running on a computer architecture having a given number of registers, from a unit of high-level code, comprising:

• a) means for identifying temporary items in said unit of code;
• b) means for identifying a lifetime of each one of said temporary items, said lifetime of said each of said temporary items being an interval of time between the creation and the last use of said each of said of said temporary items in said unit of code;
• c) means for identifying holes in the lifetime of each one of said temporary items said hole in the lifetime of said each one of said temporary items being an interval of time between a use and a store of said each one of said temporary items within said unit of code;
• and
• d) means for allocating said registers to as many of said temporary items as there are registers available in said given number at any point in said unit of code, including storing for each register in separate lists said identified temporary items and said identified holes and allocating said registers to the ones of said temporary items whose lifetime fits within one of said holes.