Minimizing register spills by using register moves

• US 9,009,692 B2
• Filed: 12/26/2009
• Issued: 04/14/2015
• Est. Priority Date: 12/26/2009
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Kalogeropulos, Spiros, Tirumalai, Partha P., Song, Yonghong
• Primary Examiner(s): Alrobaye, Idriss N
• Assistant Examiner(s): TAYLOR, BROOKE JAZMOND
• Application Number:
  US12/647,484
• Publication Number:
  US 20110161945A1
• Time in Patent Office: 1,935 Days
• Field of Search: 717/152
• 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 system comprising:

a compiler; and

a memory;

wherein the compiler comprises;

first instructions configured to generate code from a computer program, wherein said generating the code comprises performing register allocation for a plurality of variables of the computer program, and wherein the register allocation results in a plurality of spilled variables; and

second instructions configured to;

determine that a period of use of at least two spilled variables is covered by a period of availability of an available register;

determine a priority of each of the at least two spilled variables, wherein the priority is based at least in part on a number of cycles executed from a stack memory store instruction to a stack memory load instruction for a respective spilled variable;

determine to store a first spilled variable in the available register responsive to determining the first spilled variable has a highest priority of the at least two spilled variables;

wherein in response to the second instructions determining to store the first spilled variable in the available register, the first instructions are configured to modify the code to allocate the first spilled variable to the available register by replacing stack memory store and load instructions corresponding to the first spilled variable with inter-register-file move instructions.

2. The system 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 system as recited in claim 2, wherein the instruction type of the at least two spilled variables is one of the following:

integer, floating-point, multimedia, and cryptographic.

4. The system as recited in claim 2, wherein the priority of each of the at least two spilled variables is further based on a number of cycles executed from the stack memory load instruction to a first use of the respective spilled variable, wherein a shorter distance from the stack memory store instruction to the stack memory load instruction for the respective spilled variable corresponds to a higher calculated performance cost and a higher priority, and wherein a shorter distance from the stack memory load instruction to the first use of the respective spilled variable corresponds to a higher calculated performance cost and a higher priority.

5. The system 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.

6. The system as recited in claim 2, wherein the priority of each of the at least two spilled variables is proportional to a sum of an inverse of the number of cycles executed from the stack memory instruction to the stack memory load instruction for the respective spilled variable and an inverse of the number of cycles executed from the stack memory load instruction to the first use of the respective spilled variable.

7. The system as recited in claim 2, wherein the inter-register-file move instructions are machine instructions that move data directly between a first register file and the alternate register file, and wherein the alternate register file is not directly accessible by the instruction type of the at least two spilled variables.

8. A computer implemented method for compiling a computer program, the method comprising:

generating, by the computer, code from the computer program, wherein said generating the code comprises performing register allocation for a plurality of variables of the computer program, and wherein the register allocation results in a plurality of spilled variables;

determining that a period of use of at least two spilled variables is covered by a period of availability of an available register;

determining a priority of each of the at least two spilled variables, wherein the priority is based at least in part on a number of cycles executed from a stack memory store instruction to a stack memory load instruction for a respective spilled variable;

determining to store a first spilled variable in the available register responsive to determining the first spilled variable has a highest priority of the at least two spilled variables;

and

modifying, by the computer, the code to allocate the first spilled variable to the available register by replacing stack memory store and load instructions corresponding to the first spilled variable with inter-register-file move instructions, in response to determining to store the first spilled variable in the available register.

9. The method as recited in claim 8, 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.

10. The method as recited in claim 9, wherein the instruction type of the at least two spilled variables is one of the following:

integer, floating-point, multimedia, and cryptographic.

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

12. The method as recited in claim 9, wherein the priority of each of the at least two spilled variables is further based on a number of cycles executed from the stack memory load instruction to a first use of the respective spilled variable, wherein a shorter distance from the stack memory store instruction to the stack memory load instruction for the respective spilled variable corresponds to a higher calculated performance cost and a higher priority, and wherein a shorter distance from the stack memory load instruction to the first use of the respective spilled variable corresponds to a higher calculated performance cost and a higher priority.

13. The method as recited in claim 9, wherein the priority of each of the at least two spilled variables is proportional to a sum of an inverse of the number of cycles executed from the stack memory instruction to the stack memory load instruction for the respective spilled variable and an inverse of the number of cycles executed from the stack memory load instruction to the first use of the respective spilled variable.

14. The method as recited in claim 13, wherein the inter-register-file move instructions are machine instructions that move data directly between a first register file and the alternate register file, and wherein the alternate register file is not directly accessible by the instruction type of the at least two spilled variables 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.

15. A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by a computer system to compile a computer program, wherein in said compiling, the program instructions are executable by the computer system to:

generate code from the computer program, wherein said generating the code comprises performing register allocation for a plurality of variables of the computer program, and wherein the register allocation results in a plurality of spilled variables;

determine that a period of use of at least two spilled variables is covered by a period of availability of an available register;

determine a priority of each of the at least two spilled variables, wherein the priority is based at least in s art on a number of cycles executed from a stack memory store instruction to a stack memory load instruction for a respective spilled variable;

determine to store a first spilled variable in the available register responsive to determining the first spilled variable has a highest priority of the at least two spilled variables;

and

modify the code to allocate the first spilled variable to the available register by replacing stack memory store and load instructions corresponding to the first spilled variable with inter-register-file move instructions, in response to determining to store the first spilled variable in the available register.

16. The non-transitory storage medium as recited in claim 15, 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.

17. The non-transitory storage medium as recited in claim 16, wherein the priority of each of the at least two spilled variables is further based on a number of cycles executed from the stack memory load instruction to a first use of the respective spilled variable, wherein a shorter distance from the stack memory store instruction to the stack memory load instruction for the respective spilled variable corresponds to a higher calculated performance cost and a higher priority, and wherein a shorter distance from the stack memory load instruction to the first use of the respective spilled variable corresponds to a higher calculated performance cost and a higher priority.