Digital computer register allocation and code spilling using interference graph coloring
First Claim
1. A machine-executed method for allocating a plurality R of internal registers of a computer for the storage of a plurality of values to be defined and reference during execution of a program by said computer, wherein each one of said plurality of values is "live" during a particular portion of the execution of said program, said particular portion being referred to as a "live range" of said each one value, and wherein two lives range overlapping is referred to as an "interference", the method comprising the steps of:
- (a) constructing an interference graph having one node for each live range of said program and an edge for each interference between two live ranges;
(b) assigning one of R distinct colors to each node in said graph such that no two of said nodes which are connected by one of said edges are assigned the same one of said R colors, leaving any given nod uncolored when said given node cannot be assigned a color different from all others of nodes which are connected to said given node;
(c) for each node left uncolored in step (b), modifying said program such that certain ones of said live ranges corresponding to said uncolored nodes are transformed into a plurality of smaller live ranges;
(d) repeating steps (a) through (c) above until no nodes in said interference graph are left uncolored in step (b);
(e) assigning each one of said R colors to a unique one of said R registers, the assignment of a particular one of said R colors to a particular one of said R registers signifying that a value whose live range was represented in step (a) by node to which said particular one of said R colors was assigned in step (b) above will be stored in said particular register.
0 Assignments
0 Petitions
Accused Products
Abstract
A method is disclosed for allocating internal machine registers in a digital computer for use in storing values defined and referenced by a computer program. An allocator in accordance with the present invention constructs a interference graph having a node therein for the live range of each value defined by a computer program, and having an edge between every two nodes whose associated live ranges interfere with each other. The allocator models the register allocation process as a graph-coloring problem, such that for a computer having R registers, the allocator of the present invention iteratively attempts to R-color the interference graph. The interference graph is colored to the extent possible on each iteration before a determination is made that one or more live ranges must be spilled. After spill code has been added to the program to transform spilled live ranges into multiple smaller live ranges, the allocator constructs a new interference graph and the process is repeated.
-
Citations
8 Claims
-
1. A machine-executed method for allocating a plurality R of internal registers of a computer for the storage of a plurality of values to be defined and reference during execution of a program by said computer, wherein each one of said plurality of values is "live" during a particular portion of the execution of said program, said particular portion being referred to as a "live range" of said each one value, and wherein two lives range overlapping is referred to as an "interference", the method comprising the steps of:
-
(a) constructing an interference graph having one node for each live range of said program and an edge for each interference between two live ranges; (b) assigning one of R distinct colors to each node in said graph such that no two of said nodes which are connected by one of said edges are assigned the same one of said R colors, leaving any given nod uncolored when said given node cannot be assigned a color different from all others of nodes which are connected to said given node; (c) for each node left uncolored in step (b), modifying said program such that certain ones of said live ranges corresponding to said uncolored nodes are transformed into a plurality of smaller live ranges; (d) repeating steps (a) through (c) above until no nodes in said interference graph are left uncolored in step (b); (e) assigning each one of said R colors to a unique one of said R registers, the assignment of a particular one of said R colors to a particular one of said R registers signifying that a value whose live range was represented in step (a) by node to which said particular one of said R colors was assigned in step (b) above will be stored in said particular register. - View Dependent Claims (2, 3, 4)
-
-
5. A machine-executed method for allocating the use during execution of a program of a fixed number R of registers in a computer, such that any two values defined by said program whose live ranges overlap are not stored in the same one of said registers, comprising the steps of:
-
(a) constructing a graph having nodes and edges therein, wherein each node corresponding to one live range of a value defined by sad program, and wherein each edge between two nodes in said graph in said graph represents an overlap of the live ranges corresponding to said two nodes; (b) performing an R-coloring of said interference graph wherein for each one node in the graph, a color is assigned to said one node which differs from any color assigned to any node connected to said one node by an edge, and wherein any node having R or more nodes connected thereto by an edge is left uncolored; (c) for each node left uncolored in step (b), inserting spill code instructions into said computer program to split the live range corresponding to said uncolored node into a plurality of shorter live ranges; (d) repeating steps (a) through (c) until no node is left uncolored in step (b). - View Dependent Claims (6, 7, 8)
-
Specification