Minimizing Register Spills by Using Register Moves

• US 20110161945A1
• Filed: 12/26/2009
• Published: 06/30/2011
• Est. Priority Date: 12/26/2009
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Song, Yonghong, Tirumalai, Partha P., Kalogeropulos, Spiros
• Granted Patent: US 9,009,692 B2
• Time in Patent Office: Days
• US Class Current: 717/152
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A system and method for minimizing register spills during compilation. A compiler reallocates spilled variables from stack memory to other available registers. Although a corresponding register file may not have available registers for storage, the compiler identifies available registers in other locations for storage. The compiler identifies available registers in an alternate register file, wherein the alternate register file may be a floating-point register file which is then used for spilled integer variables. Other instruction type combinations between spilled variables and alternate register files are possible. When an available register within the alternate register file is identified, the compiler modifies the program instructions to allocate the corresponding spilled variable to the available register.

Claims

1. A compiler comprising:

first instructions configured to generate code; and

second instructions configured to;

detect a plurality of spilled variables corresponding to program instructions of a computer program; and

identify an available register for storing a first spilled variable of the plurality of spilled variables;

wherein in response to identifying said available register, the first instructions are configured to modify the program instructions to allocate the first spilled variable to the available register.

2. The compiler as recited in claim 1, wherein the second instructions are further configured to identify an alternate register file comprising the available register, wherein the alternate register file is a dedicated register file for an instruction type different from an instruction type of the first spilled variable.

3. The compiler as recited in claim 2, wherein the instruction type of the first spilled variable is one of the following:

integer, floating-point, multimedia, and cryptographic.

4. The compiler as recited in claim 2, wherein the first instructions are further configured to replace stack memory store and load instructions corresponding to the first spilled variable with inter-register-file move instructions.

5. The compiler as recited in claim 2, wherein the second instructions are further configured to determine a period of use of the first spilled variable is covered by a period of availability of the available register.

6. The compiler as recited in claim 2, wherein, in order to identify the available register, the second instructions are further configured to identify assigned and non-utilized registers prior to identifying unassigned registers within the alternate register file.

7. The compiler as recited in claim 6, wherein the second instructions are further configured to determine the first spilled variable has a higher priority than a second spilled variable, wherein the second spilled variable has a period of use that is covered by the period of availability of the available register.

8. The compiler as recited in claim 7, wherein the second instructions are further configured to determine the higher priority at least by determining a first cycle distance for the first spilled variable is less than a first cycle distance for the second spilled variable, wherein the first cycle distance is a number of cycles executed from a store instruction to a corresponding location in a stack memory to the load instruction from the corresponding location in the stack memory.

9. A computer implemented method comprising:

detecting by the computer a plurality of spilled variables corresponding to program instructions of a computer program;

identifying an available register for storing a first spilled variable of the plurality of spilled variables; and

modifying the program instructions to allocate the first spilled variable to the available register, in response to identifying said available register.

10. The method as recited in claim 9, further comprising identifying an alternate register file comprising the available register, wherein the alternate register file is a dedicated register file for an instruction type different from an instruction type of the first spilled variable.

11. The method as recited in claim 10, wherein the instruction type of the first spilled variable is one of the following:

integer, floating-point, multimedia, and cryptographic.

12. The method as recited in claim 10, further comprising replacing stack memory store and load instructions corresponding to the first spilled variable with inter-register-file move instructions.

13. The method as recited in claim 10 further comprising, identifying assigned and non-utilized registers prior to identifying registers within the alternate register file, in order to identify the available register.

14. The method as recited in claim 10, further comprising determining a period of use of the first spilled variable is covered by a period of availability of the available register.

15. The method as recited in claim 13, further comprising determining the first spilled variable has a higher priority than a second spilled variable, wherein the second spilled variable has a period of use that is covered by the period of availability of the available register.

16. The method as recited in claim 15, further comprising determining the higher priority at least by determining a second cycle distance for the first spilled variable is less than a second cycle distance for the second spilled variable, wherein the second cycle distance is a number of cycles executed from a load instruction from a corresponding location in stack memory to the first use of that loaded value in the computer program.

17. A computer readable storage medium storing program instructions, wherein the program instructions are executable to:

detect a plurality of spilled variables corresponding to program instructions of a computer program;

identify an available register for storing a first spilled variable of the plurality of spilled variables; and

modify the program instructions to allocate the first spilled variable to the available register, in response to identifying said available register.

18. The storage medium as recited in claim 17, wherein the program instructions are further executable to identifying an alternate register file comprising the available register, wherein the alternate register file is a dedicated register file for an instruction type different from an instruction type of the first spilled variable.

19. The storage medium as recited in claim 18, wherein the program instructions are further executable to replace stack memory store and load instructions corresponding to the first spilled variable with inter-register-file move instructions.

20. The storage medium as recited in claim 18, wherein the program instructions are further executable to determine a period of use of the first spilled variable is covered by a period of availability of the available register.