Register allocation and spilling via graph coloring

• US 4,571,678 A
• Filed: 11/05/1982
• Issued: 02/18/1986
• Est. Priority Date: 11/05/1982
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chaitin, Gregory J.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/439,523
• Time in Patent Office: 1,201 Days
• Field of Search: 364/300, 364/200 MS File
• US Class Current: 717/156
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

In an optimizing compiler which receives a high level source language program and produces machine interpretable instructions, a method for assigning computational data utilized by the program to a limited number of high speed machine registers in a target CPU and more particularly to such a method for determining that there are not enough registers available in the CPU to store all of the data required at the given point in time and for the determining which data should be stored in the system memory until they are actually needed. Said method being further characterized in that method utilizes a graph reduction and coloring approach in making the "spill" decisions.

Claims

1. In an optimizing compiler for converting a high level source language program into a machine executable program, the improvement which comprises a register allocation procedure which receives as input an intermediate language specifying storage requirements for the program as an unlimited number of symbolic registers and which produces a modified intermediate language for the program wherein all symbolic register assignments are converted to real machine registers or storage designations, said procedure comprising the steps of:

generating an interference graph for said program,

allocating registers to said program via graph reduction and graph coloring techniques without spilling,

when it is determined that further graph reduction is blocked and that spilling must occur, removing any remaining nodes in the interference graph by either making a spill determination or by further graph reduction steps until the graph is completely reduced,

generating spill code for those nodes removed on the basis of spill determinations, and

assigning registers to the nodes of said reduced graph by graph coloring techniques.

2. A register allocation procedure as set forth in claim 1, including removing those nodes during graph reduction steps which are defined as having a degree G<

N wherein N is the number of machine registers available in the target CPU for the storage of computational data elements and wherein nodes having a degree G≧

N can only be removed as spill candidates.

3. A register allocation procedure as set forth in claim 2, including determining the cost of spilling the nodes remaining in the graph after it has been determined that spilling must occur and consecutively removing nodes which must be spilled on a cost per edge basis.

4. A register allocation procedure as set forth in claim 3, including rewriting the intermediate language program with spill code replacing all symbolic registers representing nodes removed by said spill decisions and

using this rewritten intermediate language program as a next input to said complete register allocation procedure, and repeating said procedure until it is determined that the particular version of the intermediate language is colorable via graph coloring techniques without further spill processing.

5. In an optimizing compiler for converting a high level source language program into a machine executable program, the improvement which comprises a register allocation procedure which receives as input an intermediate language specifying storage requirements for the program as an unlimited number (K) of symbolic registers and which produces a modified intermediate language for the program wherein all symbolic register assignments are converted to real machine registers or storage designations, said procedure comprising the steps of:

generating an interference graph for a K-node program which comprises constructing a symmetrical bit matrix in storage for the program which has a dimension of K bits by K bits wherein the bit at row I and column J is a "1" if and only if nodes I and J are adjacent (must be live concurrently) calculating the degree of each node from said matrix,

creating a table of K adjacency vectors for said nodes,

said procedure further including coalescing nodes which comprise copy operations,

keeping said matrix current and chaining together adjacency vectors of nodes which have been coalesced,

rewriting the intermediate language program in terms of the coalesced nodes of the interference graph and

rerunning the new intermediate language program as a new input to the overall graph coloring procedure, and assigning real register numbers to said nodes by graph coloring techniques.

6. A register allocation procedure as set forth in claim 5 including removing nodes from said graph by graph reduction techniques until the graph is completely reduced.

7. A register allocation procedure as set forth in claim 6 including initiating a spilling procedure when further graph reduction is blocked by nodes having too high a degree which procedure includes removing any remaining nodes in the interference graph by making spill determinations or by further graph reduction steps, when possible, until the graph is completely reduced,

modifying the current intermediate language program by generating spill code for those nodes removed on the basis of spill determinations and assigning registers by graph coloring techniques to all nodes of said graph which were removed by permissible graph reduction techniques.

8. A register allocation procedure as set forth in claim 7, including removing nodes during graph reduction steps which are defined as those having a degree G<

N wherein N is the number of machine registers available in the target CPU for the storage of computations and wherein nodes having a degree G≧

N can only be removed as spill candidates.

9. A register allocation procedure as set forth in claim 8, including determining the cost of spilling all nodes remaining in the graph after it has been determined that spilling must occur and sequentially removing nodes which must be spilled based on such cost determinations.

10. A register allocation procedure as set forth in claim 9, including rewriting the intermediate language program with spill code replacing all symbolic registers representing nodes removed by said spill determinations and

using the rewritten intermediate language program as a next input to said overall register allocation procedure and

repeating said procedure until it is determined that the particular version of the intermediate language is colorable via graph coloring techniques without further spill processing.

11. In an optimizing compiler for converting a high level source language program into a machine executable program, the improvement which comprises a register allocation procedure which receives as input an intermediate language specifying storage requirements for the program as an unlimited number of symbolic registers and which produces a modified intermediate language for the program wherein all symbolic registers assignments are converted into real machine registers or storage designations, said procedure comprising the steps of:

generating an interference graph for said program,

combining nodes of said graph to remove the register copy operations,

rebuilding said graph to reflect said node removal,

determining if there is a node with a degree G less than the number of machine registers N available, and if such a node is present,

removing the node and its edges from the graph,

determining if all nodes of the graph have been removed and if not,

returning to said node removal step,

if all nodes have been removed rebuilding the graph a node at a time together with the respective edges in the inverse order of their removal and assigning register numbers to the nodes,

rewriting the complete program intermediate language replacing symbolic registers by real machine register numbers at which point the procedure is exited,

upon a determination that a node remains in the graph during the node determined step of a degree G equal to or greater than N branching to a spilling procedure which comprises making a weighted spill cost per node determination for each remaining node,

consecutively removing nodes as spill candidates based on said spill cost determination and after each spill removal,

determining if any of the remaining nodes can be removed by normal graph reduction techniques and if not removing a further node as spill candidates until all of the nodes have been removed from the graph by either graph reduction or as spill candidates,

determining after each node removal if all nodes have been removed and after a positive determination is made,

inserting spill code in the intermediate language for all nodes removed as spill candidates and utilizing the rewritten intermediate language with the spill code inserted as a new intermediate language input to the overall register procedure and repeating said procedure until it is ascertained that complete register coloring is possible without the necessity of initiating a spill procedure.

12. A register allocation procedure as set forth in claim 11, wherein the step of determining the cost of spilling a node comprises determining said cost per edge and wherein nodes are spilled consecutively with increasing costs per edge.