US5339428A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compiler allocating a register to a data item used between a use and store of another data item previously allocated to the register
Assignee: Hewlett Packard Development Co LP
•
Filing: 1991-09-04
•
Granted: 1994-08-16
•
Expires: 2011-09-04
Abstract
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.
Inventors
- 👤 Curt K. Burmeister
- 👤 Kevin W. Harris
- 👤 William B. Noyce
- 👤 Steven O. Hobbs
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 16:39
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/441
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
225 words
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.
Claim 2
Independent Claim
225 words
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.
Claim 3
Dependent Claim
44 words
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.
Claim 4
Dependent Claim
38 words
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.
Claim 5
Dependent Claim
130 words
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.
Claim 6
Dependent Claim
40 words
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.
Claim 7
Dependent Claim
30 words
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.
Claim 8
Dependent Claim
189 words
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.
Claim 9
Dependent Claim
189 words
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.
Claim 10
Dependent Claim
28 words
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.
Claim 11
Dependent Claim
28 words
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.
Claim 12
Dependent Claim
39 words
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.
Claim 13
Dependent Claim
37 words
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.
Claim 14
Dependent Claim
117 words
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.
Claim 15
Dependent Claim
38 words
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.
Claim 16
Independent Claim
193 words
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.
Claim 17
Independent Claim
193 words
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.
Claim 18
Dependent Claim
36 words
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.
Claim 19
Dependent Claim
17 words
A method according to claim 15 wherein said step of allocating is responsive to said separate lists.
Claim 20
Dependent Claim
41 words
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.
Claim 21
Dependent Claim
211 words
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.
Claim 22
Dependent Claim
211 words
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.
Claim 23
Dependent Claim
32 words
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.
References Cited (Backward Citations)
US4435753A
Cited
US4571678A
Cited
US4642764A
Cited
US4667290A
Cited
US4656582A
Cited
US4782444A
Cited
US4953084A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-15 | 1998-02-14 | 1998-08-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-15 | 2002-02-14 | 2002-08-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-15 | 2006-02-14 | 2006-08-16 | $7700.00 | Window Closed / Lapsed |