Method and system for register allocation using multiple interference graphs

• US 5,901,317 A
• Filed: 03/25/1996
• Issued: 05/04/1999
• Est. Priority Date: 03/25/1996
• 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): Voeltz, Emanuel Todd
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/621,409
• Time in Patent Office: 1,135 Days
• Field of Search: 395/709
• US Class Current: 717/156
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

Allocation of real registers to virtual or symbolic registers represented by nodes in an interference graph is performed with a compiler using a primary interference graph and a secondary interference graph. The primary interference graph contains the standard edges indicating latency between virtual registers represented by nodes linked by the edges. Secondary links between nodes indicate conditional conflicts which can be tolerated but which, if avoided in the register allocation process, improve the execution speed of program segments. The conditional conflict specifically referenced is the requirement for paired register designation in single precision floating point operations in which registers are identified as pairs, rather than as individual registers.

Claims

1. A computer implemented method for use in a compiler for allocating real registers in a CPU to instructions of a target computer program which are to be executed on the CPU, said method comprising the steps of:

creating a representation of a primary interference graph having nodes representing virtual registers and primary edges linking nodes with concurrent latency, the number of edges of a given node being the degree of the node;

creating a representation of a second interference graph having nodes representing virtual registers and secondary edges linking nodes with conditional conflicts;

selecting nodes from the primary interference graph having degrees less than the number of CPU registers until all nodes have been selected; and

allocating real registers to said selected nodes by first determining whether a register can be allocated for a selected node using the edges of both the primary and secondary interference graphs and, if so, allocating a real register on that basis; and

, if not, allocating a real register using the edges of the primary graph alone.

2. The method of claim 1 wherein the step of allocating is performed on nodes in the reverse order from which the nodes were originally selected.

3. The method of claim 1 wherein the secondary interference graph edges link a virtual register requiring use of a paired register with another virtual register.

4. A computer system comprising:

a central processing unit (CPU) having a finite number of allocatable registers; and

a compiler including a first procedure for creating a representation of a primary interference graph having nodes representing virtual registers and primary edges linking nodes with concurrent latency, the number of edges of a given node being the degree of the node, a second procedure for creating a representation of a secondary interference graph having nodes representing virtual registers and secondary edges linking nodes with conditional conflicts;

a third procedure for selecting nodes from the primary interference graph having a degree less than the number of CPU registers until all nodes have been selected from the primary interference graph; and

a fourth procedure for allocating real registers to the selected nodes by first determining whether a register can be allocated for a selected node using the edges of both the primary and secondary interference graphs and, if so, allocating a real register on that basis; and

, if not, allocating a real register using the edges of the primary graph alone.

5. The computer system of claim 4 wherein said fourth procedure is performed on nodes in the reverse order from which the nodes were originally selected.

6. The computer system of claim 4 wherein the secondary interference graph edges link a virtual register requiring use of a paired register with another virtual register.

7. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for optimizing allocation of real registers in a computer system, the computer program product comprising;

a first set of computer readable program code devices for creating a representation of a primary interference graph having nodes representing virtual registers and primary edges linking nodes with concurrent latency, the number of edges of a given node being the degree of the node, and for creating a representation of a secondary interference graph having nodes representing virtual registers and secondary edges linking nodes with conditional conflicts;

a second set of computer readable program code devices configured to cause a computer to select nodes from the primary interference graph having degrees less than the number of real registers in the computer system until all nodes have been selected; and

a third set of computer readable program code devices configured to cause a computer to allocate real registers to the selected nodes by first determining whether a real register can be allocated for a selected node using the edges of both the primary and secondary interference graphs and, if so, allocating a real register on that basis; and

, if not, allocating a real register using the edges of the primary graph alone.

8. The computer program product of claim 7 wherein said first set of computer readable program code devices is configured to cause a computer to create a representation of a secondary interference graph having secondary edges linking a virtual register requiring use of a paired register with another virtual register.

9. The computer program product of claim 7 wherein said third set of computer readable program code devices is configured to cause a computer to perform the allocation of real registers in the reverse order from which the nodes were originally selected.