Functional unit switching for the allocation of registers

• US 5,987,259 A
• Filed: 06/30/1997
• Issued: 11/16/1999
• 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 J.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/885,567
• Time in Patent Office: 869 Days
• Field of Search: 395/390, 395/393, 395/394, 395/561-564, 395/705, 395/706, 395/707, 395/708, 395/709, 395/800.01
• US Class Current: 717/152
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A method and apparatus for allocating registers when compiling code is provided. In response to determining there are insufficient registers associated with a first functional unit of a processor to allocate to a region of code, instructions associated with the region designated for execution on a first functional of processor that may be executed by second functional unit are detected. Those instructions generated for execution on the first functional unit are replaced with the instructions executed on the second functional unit.

Claims

1. In a computer system, a method of minimizing registers spills when allocating a first set of registers to be used during the execution of a set of computer instructions, wherein the first set of registers is associated with a first functional unit, the method comprising the steps of:

detecting whether a first subset of computer instructions from said set of computer instructions may be executed by a second functional unit, said first subset of computer instructions specifying the use of one or more registers from said first set of registers; and

if detecting that said first subset of computer instructions may be executed by said second functional unit, then performing the steps of;

generating a second subset of computer instructions, wherein said second subset of computer instructions specifies the use of a second subset of registers associated with said second functional unit, and

replacing said first subset of computer instructions with said second subset of computer instructions.

2. The method of claim 1, wherein:

the method includes the step of determining whether there are sufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring any register from said first set of registers; and

the step of detecting is performed in response to determining that there are insufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring a register from said first set of registers.

3. The method of claim 2, wherein the step of detecting whether said first subset of computer instructions may be executed by said second functional unitincludes detecting whether a second set of registers associated with said second functional unit is dirty, wherein said second set of registers is dirty if any register from said second set of registers has been previously allocated to any intermediate value.

4. The method of claim 2, wherein the method of detecting includes the steps of:

generating one or more expression trees based on said set of computer instructions; and

identifying a set of expression trees representing instructions executable by said second functional unit.

5. The method of claim 4, wherein:

the method further include the steps of;

determining a cost effectiveness associated with a particular expression tree from said set of expression trees, said cost effectiveness associated with any expression tree being based on executing any instructions represented by said particular expression tree on said second functional unit, and

selecting said particular expression tree from said set of expression trees based on the cost effectiveness associated with said particular expression tree; and

the step of generating said second subset of computer instructions includes generating said second subset of computer instructions based on said particular expression tree.

6. The method of claim 4, further including the step of selecting a particular expression tree from said set of expression trees based on there being sufficient registers from a second set of registers to allocate to any intermediate value required by instructions represented by said particular expression tree, said second set of registers being associated with said second functional unit.

7. The method of claim 1, wherein:

the method includes the step of determining whether said set of computer instructions may be colored; and

the step of detecting is performed in response to detecting that said set of computer instructions may not be colored.

8. A computer program embodied in a computer-readable medium for minimizing register spills when allocating a first set of registers associated with a first functional unit to be used during the execution of a set of computer instructions, said computer program comprising:

a first code segment for detecting whether a first subset of computer instructions may be executed by a second functional unit, said first subset of computer instructions specifying the use of one or more registers from said first set of registers; and

a second code segment for generating a second subset of computer instructions when detecting that said first subset of computer instructions may be executed by said second functional unit, wherein said second subset of computer instructions specifies the use of a second subset of registers associated with said second functional unit.

a third code segment for replacing said first subset of computer instructions with said second subset of computer instructions in response to generating said second subset of computer instructions.

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

the computer program further comprising a fourth code segment for determining whether there are sufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring any register from said first set of registers, wherein said first set of registers is associated with said first functional unit; and

the first code segment further includes code for detecting whether said first subset of computer instructions may be executed by said second functional unit in response to determining that there are insufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring a register from said first set of registers.

10. The computer program embodied in a computer readable medium of claim 9, wherein the second code segment further includes code for detecting whether said first subset of computer instructions may be executed by said second functional unit by detecting whether a second set of registers associated with said second functional unit is dirty, wherein said second set of registers is dirty if any register from said second set of registers has been previously allocated to any intermediate value.

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

a sixth code segment for generating one or more expression trees based on said set of computer instructions; and

a seventh code segment for identifying a set of expression trees representing instructions executable by said second functional unit.

12. The computer program embodied in a computer readable medium of claim 8, wherein:

the computer program further comprising a fifth code segment for determining whether said set of computer instructions may be colored; and

the first code segment further includes code for detecting whether said first subset of computer instructions may be executed by said second functional unit in response to detecting that said set of computer instructions may not be colored.

13. A computer system comprising:

a memory;

a processor coupled to said memory;

a compiler stored in said memory for execution by said processor;

said compiler adapted to allocate a first set of registers to be used during the execution of a set of computer instructions, wherein said first set of registers is associated with a first functional unit;

said compiler adapted to detect whether a first subset of computer instructions may be executed by a second functional unit, said first subset of computer instructions specifying the use of one or more registers from said first set of registers; and

said compiler adapted to respond to detecting that said first subset of computer instructions may be executed by said second functional unit, by;

generating a second subset of computer instructions, wherein said second subset of computer instructions specified the use of one or more registers from a second subset of registers associated with said second functional unit, and

replacing said first subset of computer instructions with said second subset of computer instructions.

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

said compiler adapted to determine whether there are sufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring any register from said first set of registers; and

said compiler adapted to detect in response to determining that there are insufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring a register from said first set of registers.

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

said compiler adapted to determine whether said set of computer instructions may be colored; and

said compiler adapted to detect in response to detecting that said set of computer instructions may not be colored.

16. The computer system of claim 13, further comprising said compiler adapted to detect whether said first subset of computer instructions may be executed by said second functional unit by detecting whether a second set of registers associated with said second functional unit is dirty, wherein said second set of registers is dirty if any register from said second set of registers has been previously allocated to any intermediate value.

17. A computer data signal embodied in a carrier wave and representing a computer program for minimizing register spills when allocating a first set of registers associated with a first functional unit to be used during the execution of a set of computer instructions, said computer program comprising:

a first code segment for detecting whether a first subset of computer instructions may be executed by a second functional unit, said first subset of computer instructions specifying the use of one or more registers from said first set of registers; and

a second code segment for generating a second subset of computer instructions when detecting that said first subset of computer instructions may be executed by said second functional unit, wherein said second subset of computer instructions specifies the use of a second subset of registers associated with said second functional unit;

a third code segment for replacing said first subset of computer instructions with said second subset of computer instructions in response to generating said second subset of computer instructions.

18. The computer data signal representing a computer program of claim 17, wherein:

the computer program further comprising a fourth code segment for determining whether there are sufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring any register from said first set of registers, wherein said first set of registers is associated with said first functional unit; and

the first code segment further includes code for detecting whether said first subset of computer instructions may be executed by said second functional unit in response to determining that there are insufficient registers from said first set of registers to allocate to each intermediate value in said set of computer instructions requiring a register from said first set of registers.

19. The computer data signal representing a computer program of claim 18, wherein the second code segment further includes code for detecting whether said first subset of computer instructions may be executed by said second functional unit by detecting whether a second set of registers associated with said second functional unit is dirty, wherein said second set of registers is dirty if any register from said second set of registers has been previously allocated to any intermediate value.

20. The computer data signal representing a computer program of claim 17, wherein:

the computer program further comprising a fifth code segment for determining whether said set of computer instructions may be colored; and

the first code segment further includes code for detecting whether said first subset of computer instructions may be executed by said second functional unit in response to detecting that said set of computer instructions may not be colored.