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

• US 5,339,428 A
• Filed: 09/04/1991
• Issued: 08/16/1994
• Est. Priority Date: 09/04/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Burmeister, Curt K., Harris, Kevin W., Hobbs, Steven O., Noyce, William B.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): ELLCESSOR, LARR
• Application Number:
  US07/754,549
• Time in Patent Office: 1,077 Days
• Field of Search: 395/700, 395/650, 395/375, 364/DIG. 1, 364/DIG. 2
• US Class Current: 717/146
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A compiler includes a register allocation method making use of the concept of assigning temporary items to lifetime holes if such holes exist that are suitable. The compiler includes a front end for converting the input code to an intermediate representation, then this input representation is traversed to identify all of the temporary items, and to find all of the holes in the temporary items. Lists are maintained of the identified temporaries and holes. Register allocation then includes assigning temporaries to registers so long as there are free registers, and if holes are available in already-assigned temporaries then these holes are used in assigning registers. After all the available registers and holes are used, remaining temporaries are unallocated and thus represent memory references.

Claims

1. A method of allocating registers in a compiler, comprising the steps of:

a) identifying temporary items in a unit of code, each of said temporary items requiring storage;

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 temporary items within said unit of code;

c) identifying holes in the lifetime of said 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 store of said each one of said temporary items within said unit of code; and

d) allocating to said registers said each of said temporary items, including

forming a list for each of said registers of said each of said temporary items and said holes associated with said each of said temporary items allocated to said each of said registers;

allocating to one of said registers a first one of said temporary items, said first temporary item having a hole;

locating in said list a second one of said temporary items, said second temporary item having a lifetime fitting within said hole in said first temporary item; and

allocating to said one register said second temporary item.

2. A method according to claim 1 including the step of making a list of said temporary items sorted by starting lifetime wherein said each of said temporary items are allocated to registers in the order said temporary items appear in said temporary items list.

3. A method according to claim 1 including the steps of converting an input code into an intermediate language expressed as an ordered list of tuples, and from said list creating a flow graph of said unit of code.

4. A method according to claim 1 wherein there are a number of said registers as defined by an architecture of a computer which is to execute object code generated by said compiler, and the method includes the steps of:

making a list of said temporary items sorted by starting lifetime, wherein said each of said temporary items are allocated in the order in which said temporary items appear in said temporary items list; and

forming a list for a selected one of said registers of ones of said temporary items assigned to said one register and holes in lifetimes of said ones of said temporary items, using said lists of temporary items, wherein said allocating said second temporary item uses said list of temporary items assigned to said selected register.

5. A method according to claim 4 including the steps of converting an input code into an intermediate language expressed as an ordered list of tuples, and from said list of tuples creating a flow graph of said unit of code.

6. A method according to claim 1, wherein said identifying holes further includes recording said holes in a list of holes for each of said each one of said temporary items.

7. 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.

8. Apparatus according to claim 7 wherein said means for identifying and recording temporary items includes means for generating a list of said temporary items sorted by starting lifetime.

9. Apparatus according to claim 7 wherein said means for identifying and recording holes includes means for generating a list of said holes for each of said temporary items.

10. Apparatus according to claim 7 wherein said means for allocating includes means for generating a list for each register of the ones of said temporary items and the ones of said holes in said ones of said temporary items.

11. Apparatus according to claim 7 including means for converting an input code into an intermediate language expressed as an ordered list of tuples, and for creating from said list a flow graph of said unit of code.

12. Apparatus according to claim 7 wherein there are a number of said registers as defined by an architecture of a computer which is to execute object code generated by said compiler, and the apparatus includes:

means for making a list of said temporary items sorted by starting lifetime, wherein said allocating means allocates said temporary items in the order said temporary items appear in said temporary items list; and

means responsive to data in said list of temporary items for forming a list for a selected one of said registers of ones of said temporary items allocated to said selected register, wherein said means for allocating to said one register uses said list for said selected register.

13. Apparatus according to claim 12 including means for converting an input code into an intermediate language expressed as an ordered list of tuples, and from said list of tuples creating a flow graph of said unit of code.

14. 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.

15. A method according to claim 14 wherein said list of identified temporary items are sorted by starting lifetime and wherein said identified temporary items are allocated to registers in the order they appear in said list.

16. A method according to claim 15 wherein said step of allocating is responsive to said separate lists.

17. A method according to claim 16 including the steps of converting said unit of code into an intermediate language expressed as an ordered list of tuples, and from said list of tuples creating a flow graph of said unit of code.

18. 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.

19. Apparatus according to claim 18 wherein said lists are sorted by starting lifetime and wherein said allocating means allocates registers to said temporary items in the order they appear in said list.