Register resource allocation feedback

• US 6,139,200 A
• Filed: 06/30/1997
• Issued: 10/31/2000
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Goebel, Kurt
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US08/885,563
• Time in Patent Office: 1,219 Days
• Field of Search: 395/709
• US Class Current: 717/159
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Techniques for allocating registers when generating code is described. A snapshot is generated when generating code. The snapshot contains sufficient information to restore the state of generating code that existed at the point when the snapshot was generated so that the generation of code can proceed from that point. A first set of code optimizations is generated. In response to determining that the first set of code optimizations fails to meet efficiency criteria, the generation of code proceeds based on the snapshot without incorporating the first set of code optimizations. Feedback is generated by analyzing the allocation of registers based on the first set of code optimizations. A second set of code optimizations is based on the feedback. Feedback includes information such as the number of spills occurring based on the first set of code optimizations. In addition, an allocation of registers based on a second set of code optimizations is performed in parallel with an allocation of registers based on the first set of code optimizations. Generation of code proceeds based on the second set of code optimizations when the second set of code optimizations causes less spilling the first set of code optimizations.

Claims

1. In a computer system a method for allocating registers while generating code into a set of instructions executed by said computer system said method comprising the steps of:

generating a snapshot of the current state of said generating of said code, said snapshot providing sufficient information to proceed with said generating of said code from the point where said snapshot was generated;

generating a first set of code optimizations;

determining whether said first set of code optimizations meets efficiency criteria; and

if determining said first set of code optimizations does not meet said efficiency criteria, then proceeding with said generating of said code without incorporating said first set of code optimizations based on said snapshot.

2. The method of claim 1, wherein:

the method includes the step of generating feedback based on analyzing whether said registers may be allocated based on said first set of code optimizations; and

the step of proceeding with said generating of said code includes generating a second set of code optimizations based on said feedback.

3. The method of claim 2, wherein the feedback includes data indicating a number of spills.

4. The method of claim 1, further including the steps of:

generating a second set of code optimizations;

allocating registers based on said first set of code optimizations; and

allocating said registers based on said second set of code optimizations, said step of allocating said registers based on said second set of code optimizations being performed in parallel with said step of allocating said registers based on said first set of code optimizations.

5. The method of claim 4, further including the step of in response to determining said second set of code optimizations meets said efficiency criteria, proceeding with said generating of said code based on said second set of code optimizations.

6. The method of claim 5, wherein said efficiency criteria includes said second set of code optimizations causing less spilling than any set of optimizations generated since generating said snapshot.

7. The method of claim 1, wherein:

the method further including the step of allocating registers based on said first set of code optimizations; and

the step of determining whether said first set of code optimizations meets said efficiency criteria is based on said step of allocating.

8. The method of claim 7, wherein the step of determining whether said first set of code optimizations meets efficiency criteria is based on the increase in the amount of code which may be executed in parallel due to incorporating said first set of code optimizations.

9. A computer program embodied in a computer-readable medium for minimizing spilling when allocating registers while generating code, said computer program comprising:

a first code segment for generating a snapshot of the current state of said generating of said code, said snapshot providing sufficient information to proceed with said generating of said code from the point where said snapshot was generated;

a first code segment for generating a first set of code optimizations;

a second code segment for determining whether said first set of code optimizations meets efficiency criteria; and

a third code segment for proceeding with said generating of said code without incorporating said first set of code optimizations based on said snapshot if determining said first set of code optimizations does not meet said efficiency criteria.

10. The computer program embodied in a computer-readable medium of claim 9, wherein:

the computer program further comprises a fourth code segment for generating feedback based on analyzing whether said registers may be allocated based on said first set of code optimizations; and

the third code segment further includes code for proceeding with said generating of said code by generating a second set of code optimizations based on said feedback.

11. The computer program embodied in a computer-readable medium of claim 9, further comprising:

a fifth code segment for generating a second set of code optimizations; and

a sixth code segment for performing in parallel the;

allocating of said registers based on said first set of code optimizations, and

allocating of said registers based on said second set of code optimizations.

12. A computer system comprising:

a memory;

a processor coupled to said memory;

a code generator stored in said memory for execution by said processor;

said code generator being adapted to generate a snapshot of the current state of said generating of said code, said snapshot providing sufficient information to proceed with said generating of said code from the point where said snapshot was generated;

said code generator being adapted to generate a first set of code optimizations;

said code generator being adapted to determine whether said first set of code optimizations meets efficiency criteria; and

said code generator being adapted to proceed with said generating of said code without incorporating said first set of code optimizations based on said snapshot when determining said first set of code optimizations does not meet said efficiency criteria.

13. The computer system of claim 12, further comprising:

said code generator adapted to generate feedback based on analyzing whether said registers may be allocated based on said first set of code optimizations; and

said code generator adapted to proceed with said generating of said code by generating a second set of code optimizations based on said feedback.

14. A computer data signal embodied in a carrier wave representing a computer program for minimizing spilling when allocating registers while generating code, said computer program comprising:

a first code segment for generating a snapshot of the current state of said generating of said code, said snapshot providing sufficient information to proceed with said generating of said code from the point where said snapshot was generated;

a first code segment for generating a first set of code optimizations;

a second code segment for determining whether said first set of code optimizations meets efficiency criteria; and

a third code segment for proceeding with said generating of said code without incorporating said first set of code optimizations based on said snapshot if determining said first set of code optimizations does not meet said efficiency criteria.

15. The computer data signal embodied in a carrier wave representing a computer program of claim 14, wherein:

the computer program further comprises a fourth code segment for generating feedback based on analyzing whether said registers may be allocated based on said first set of code optimizations; and

the third code segment further includes code for proceeding with said generating of said code by generating a second set of code optimizations based on said feedback.

16. The computer data signal embodied in a carrier wave representing a computer program of claim 14, further comprising:

a fifth code segment for generating a second set of code optimizations; and

a sixth code segment for performing in parallel the;

allocating of said registers based on said first set of code optimizations, and

allocating of said registers based on said second set of code optimizations.