Allocating register halves independently

Patent metadata

Field	Value
Publication number	US-9696975-B2
Application number	US-87575310-A
Country	US
Kind code	B2
Filing date	Sep 3, 2010
Priority date	Sep 3, 2010
Publication date	Jul 4, 2017
Grant date	Jul 4, 2017

Abstract

Register halves are allocated independently when performing register allocation during program compilation, thereby effectively doubling the number of registers which are available for allocation, which in turn may reduce spill code and improve run-time performance. When hardware registers are 64 bits wide, for example, an architecture supporting the present invention provides some number of separate hardware instructions that operate on the 32-bit high-word and/or the 32-bit low word of the hardware registers as if those 32-bit words are separate registers. Such hardware instructions are able to manipulate the register halves independently, leaving the other register half untouched. A register coloring algorithm using in the compilation process is invoked using the number of register halves, instead of the number of hardware registers.

First claim

The invention claimed is:

1. A computer-implemented method of allocating registers in a computing system during compilation of program code, comprising:
determining a count of hardware registers available for allocating during the compilation;
doubling the determined count of hardware registers to reflect independent usage of halves of the hardware registers;
invoking a register coloring algorithm to build an interference graph using the doubled count of hardware registers as a number of registers to be allocated, wherein building the interference graph further comprises:
programmatically consulting a data structure that specifies, for each of a plurality of operation codes in the program code to be compiled, restrictions on allocating operands of the operation code to hardware registers;
responsive to the programmatically consulting determining that a selected operand of a particular operation code must use a full hardware register, causing an allocator to allocate both a high-word half and a low-word half of a hardware register to the selected operand;
responsive to the programmatically consulting determining that the selected operand is allocatable to a register half and must use the high-word half of a hardware register, adding an interference to the interference graph between the selected operand and all low-word halves of the hardware registers to force the selected operand to be allocated to a high-word register half; and
responsive to the programmatically consulting determining that the selected operand is allocatable to a register half and must use the low-word half of a hardware register, adding an interference to the interference graph between the selected operand and all high-word halves of the hardware registers to force the selected operand to be allocated to a low-word register half; and

independently allocating the halves of the hardware registers by the allocator, when generating compiled program code during the compilation, according to results of the register coloring algorithm, thereby causing the compiled program code to specify concurrently storing, in at least one of the hardware registers, a first operand in the high-word half of the hardware register and a second operand in the low-word half of the hardware register, the first and second operands being distinct from and unrelated to one another.

2. The method according to claim 1 , wherein the register coloring algorithm colors vertices of the interference graph using a number of distinct colors that is limited to the doubled count.

3. The method according to claim 1 , wherein:
adding the interference to the interference graph between the selected operand and all low-word halves of the hardware registers comprises adding the interference to vertices of the interference graph; and
adding the interference to the interference graph between the selected operand and all high-word halves of the hardware registers comprises adding the interference to vertices of the interference graph.

4. A system for allocating registers in a computing system during compilation of program code, comprising:
a computer comprising a processor; and
instructions which are executable, using the processor, to implement functions comprising:
determining a count of hardware registers available for allocating during the compilation;
doubling the determined count of hardware registers to reflect independent usage of halves of the hardware registers;
invoking a register coloring algorithm to build an interference graph using the doubled count of hardware registers as a number of registers to be allocated, wherein building the interference graph further comprises:
programmatically consulting a data structure that specifies, for each of a plurality of operation codes in the program code to be compiled, restrictions on allocating operands of the operation code to hardware registers;
responsive to the programmatically consulting determining that a selected operand of a particular operation code must use a full hardware register, causing an allocator to allocate both a high-word half and a low-word half of a hardware register to the selected operand;
responsive to the programmatically consulting determining that the selected operand is allocatable to a register half and must use the high-word half of a hardware register, adding an interference to the interference graph between the selected operand and all low-word halves of the hardware registers to force the selected operand to be allocated to a high-word register half; and
responsive to the programmatically consulting determining that the selected operand is allocatable to a register half and must use the low-word half of a hardware register, adding an interference to the interference graph between the selected operand and all high-word halves of the hardware registers to force the selected operand to be allocated to a low-word register half; and

independently allocating the halves of the hardware registers by the allocator, when generating compiled program code during the compilation, according to results of the register coloring algorithm, thereby causing the compiled program code to specify concurrently storing, in at least one of the hardware registers, a first operand in the high-word half of the hardware register and a second operand in the low-word half of the hardware register, the first and second operands being distinct from and unrelated to one another.

5. The system according to claim 4 , wherein the register coloring algorithm colors vertices of the interference graph using a number of distinct colors that is limited to the doubled count.

6. The system according to claim 4 , wherein:
adding the interference to the interference graph between the selected operand and all low-word halves of the hardware registers comprises adding the interference to vertices of the interference graph; and
adding the interference to the interference graph between the selected operand and all high-word halves of the hardware registers comprises adding the interference to vertices of the interference graph.

7. A computer program product for allocating registers in a computing system during compilation of program code, the computer program product comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therein, the computer readable program code configured for:
determining a count of hardware registers available for allocating during the compilation;
doubling the determined count of hardware registers to reflect independent usage of halves of the hardware registers;
invoking a register coloring algorithm to build an interference graph using the doubled count of hardware registers as a number of registers to be allocated, wherein building the interference graph further comprises:
programmatically consulting a data structure that specifies, for each of a plurality of operation codes in the program code to be compiled, restrictions on allocating operands of the operation code to hardware registers;
responsive to the programmatically consulting determining that a selected operand of a particular operation code must use a full hardware register, causing an allocator to allocate both a high-word half and a low-word half of a hardware register to the selected operand;
responsive to the programmatically consulting determining that the selected operand is allocatable to a register half and must use the high-word half of a hardware register, adding an interference to the interference graph between the selected operand and all low-word halves of the hardware registers to force the selected operand to be allocated to a high-word register half; and
responsive to the programmatically consulting determining that the selected operand is

Assignees

• Belanger David P
• Lapkowski Christopher A
• Lee Chwan-Hang
• IBM

Inventors

• Belanger David P
• Lapkowski Christopher A
• Lee Chwan-Hang

Classifications

• G06F8/441 Primary

  Register allocation; Assignment of physical memory space to logical memory space · CPC title