Register allocation methods having upward pass for determining and propagating variable usage information and downward pass for binding; both passes utilizing interference graphs via coloring
First Claim
Patent Images
1. A computer-implemented method for allocating variables among physical registers of a target computer during conversion of a higher level code portion to a form readable by the target computer, comprising the steps of:
- generating a hierarchical tile tree corresponding to an underlying control structure of the code portion and including a root tile having a first code block with no predecessor and a second code block with no successor and a set of basic tiles corresponding to at least one of loop control structures and conditional control structures, the root tile being hierarchically superior to the basic tiles and at least a first one of the basic tiles being hierarchically superior to at least a second one of the basic tiles;
determining variable usage within the tiles beginning with hierarchically inferior tiles and proceeding to hierarchically superior tiles, the variable usage for hierarchically superior tiles including summary variable usage of hierarchically inferior tiles;
assigning variables to a number of pseudo registers based upon the variable usage within the tile for each tile, the number of pseudo registers being limited by the number of physical registers;
determining variable usage within the code section for each tile beginning with hierarchically superior tiles and proceeding to hierarchically inferior tiles, the variable usage for hierarchically inferior tiles including variable usage of hierarchically superior tiles; and
binding the pseudo registers to the physical registers such that conflicts between variables used within a tile and variables used in the code section outside of the tile are resolved to reduce variable usage costs within the entire code section.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides methods for allocating physical registers within a compiler phase to achieve efficient operation of a target CPU. The methods of the present invention allocate variables between physical registers and memory to accommodate local as well as global code structure. Such methods facilitate the location of variables that are heavily accessed at a portion of the code in a physical register during the execution thereof.
82 Citations
34 Claims
-
1. A computer-implemented method for allocating variables among physical registers of a target computer during conversion of a higher level code portion to a form readable by the target computer, comprising the steps of:
-
generating a hierarchical tile tree corresponding to an underlying control structure of the code portion and including a root tile having a first code block with no predecessor and a second code block with no successor and a set of basic tiles corresponding to at least one of loop control structures and conditional control structures, the root tile being hierarchically superior to the basic tiles and at least a first one of the basic tiles being hierarchically superior to at least a second one of the basic tiles; determining variable usage within the tiles beginning with hierarchically inferior tiles and proceeding to hierarchically superior tiles, the variable usage for hierarchically superior tiles including summary variable usage of hierarchically inferior tiles; assigning variables to a number of pseudo registers based upon the variable usage within the tile for each tile, the number of pseudo registers being limited by the number of physical registers; determining variable usage within the code section for each tile beginning with hierarchically superior tiles and proceeding to hierarchically inferior tiles, the variable usage for hierarchically inferior tiles including variable usage of hierarchically superior tiles; and binding the pseudo registers to the physical registers such that conflicts between variables used within a tile and variables used in the code section outside of the tile are resolved to reduce variable usage costs within the entire code section. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A computer-implemented method for allocating variables among physical registers and a separate memory of a target computer during conversion of a higher level code portion to a form readable by the target computer, comprising the steps of:
-
generating a hierarchical tile tree that corresponds to an underlying control structure of the code portion and including a root the having a first code block with no predecessor and a second code block with no successor and a set of basic tiles corresponding to at least one of loop control structures and conditional control structures, the root tile being hierarchically superior to the basic tiles and at least a first one of the basic tiles being hierarchically superior to at least a second one of the basic tiles; determining variable usage within tiles for the tiles beginning with hierarchically inferior tiles and proceeding to hierarchically superior tiles, the variable usage within tiles for hierarchically superior tiles including summary variable usage of hierarchically inferior tiles; determining variable usage globally within the code portion for the tiles beginning with hierarchically superior tiles and proceeding to hierarchically inferior tiles, the variable usage for hierarchically inferior tiles including variable usage of hierarchically superior tiles; allocating variables to physical registers response to the vocal variable usage and the global variable such that conflicts among variables within individual tiles and variables used in the code portion outside the tile are resolved to reduce variable usage costs; and inserting code to spill to the memory variables not allocated to physical registers. - View Dependent Claims (25, 26)
-
-
27. A computer-implemented method for allocating variables among physical registers of a target computer during conversion of a higher level code portion to a form readable by the target computer, comprising the steps of:
-
generating a hierarchical tile tree corresponding to an underlying control structure of the code portion, the hierarchical tile tree defining parent-child relationships among the tiles; determining during a first phase variable usage within the tiles beginning with hierarchically inferior tiles and proceeding to hierarchically superior tiles, the variable usage within the tiles being determined by; constructing and coloring a tile interference graph to identify conflicts within each leaf tile, the interference graphs incorporating preference information; assigning in accordance with the interference graph coloring variables to pseudo registers and tentatively designating variables that cannot be assigned to pseudo registers to spill, the number of pseudo registers being limited by the number of physical registers; constructing and coloring tile interference graphs to identify conflicts within hierarchically superior tiles and, for each hierarchically superior tile, designating variables to be assigned to pseudo registers or to be spilled, the designation determined by the variable usage within each hierarchically superior tile and within its child tiles, the interference graph for each hierarchically superior tile incorporating preference information and tile summary variables from its child tiles, the number of summary variables being limited by the number of pseudo registers; determining in a second phase variable usage within the code section beginning with hierarchically superior tiles and proceeding to hierarchically inferior tiles, the variable usage within the tiles of the code section being determined by; constructing and coloring tile interference graphs to identify conflicts within each hierarchically inferior tile and, for each hierarchically inferior tile, designating variables used within the tile or that are live across the tile to be assigned to physical registers or to be spilled, the designation determined by the variable usage within the tile and by the register allocation in the corresponding parent tile and the interference graph for each hierarchically inferior tile incorporating preference information from itself and its parent tiles; inserting spill code at tile entry or exit edges if all variables cannot be assigned to physical registers, the assignment of variables to physical registers reducing variable usage costs within the entire code section. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34)
-
Specification