Register allocation and spilling via graph coloring
First Claim
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, andassigning registers to the nodes of said reduced graph by graph coloring techniques.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12)
-
Specification