Register allocation method and apparatus for truncating runaway lifetimes of program variables in a computer system
First Claim
1. A computer apparatus comprising:
- (A) a central processing unit having a plurality of registers, the central processing unit executing a first instruction stream and in response to the first instruction stream, the central processing unit operates on information stored in the plurality of registers;
(B) a compiler for generating the first instruction stream from a second instruction stream, the second instruction stream having a plurality of variables, the compiler including;
a liveness calculator for determining for each of the plurality of variables a first span of the second instruction stream for which a selected one of the plurality of variables is live, wherein the selected variable is live at a first given point in the second instruction stream if the second instruction stream contains along some forward path from the first given point a first instruction that uses the selected variable before encountering a second instruction that defines the selected variable, and wherein the first span defines a lifetime for the selected variable;
a runaway lifetime detector for determining whether at least one of the plurality of variables is live in at least one predetermined location within the second instruction stream, wherein a variable that is live at the predetermined location has a runaway lifetime; and
a runaway lifetime truncator for inserting a third instruction into the second instruction stream to eliminate at least one runaway lifetime.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for truncating runaway lifetimes of program variables calculates liveness for each variable based on upwardly exposed uses. Reaching definitions are then calculated for at least the program variables that have runaway lifetimes. The liveness information is compared to the reaching definition information to determine whether a variable that is live upon entry to a basic block has a definition that reaches the end of each predecessor block, or has a use within the basic block. If the reaching definition for a variable reaches the beginning of the block and if there is a predecessor block for which there is no reaching definition, the variable has a runaway lifetime. The variable also has a runaway lifetime if there is a use of the variable in a block without a reaching definition for the variable at the beginning of the block. The runaway lifetime is truncated by inserting an instruction such as a pseudo-definition of the variable into the instruction stream at an appropriate place. Once runaway lifetimes are truncated using this method, subsequent stages of the compiler may calculate liveness by performing a single dataflow analysis which calculates lifetimes based on upwardly exposed uses.
-
Citations
20 Claims
-
1. A computer apparatus comprising:
-
(A) a central processing unit having a plurality of registers, the central processing unit executing a first instruction stream and in response to the first instruction stream, the central processing unit operates on information stored in the plurality of registers; (B) a compiler for generating the first instruction stream from a second instruction stream, the second instruction stream having a plurality of variables, the compiler including; a liveness calculator for determining for each of the plurality of variables a first span of the second instruction stream for which a selected one of the plurality of variables is live, wherein the selected variable is live at a first given point in the second instruction stream if the second instruction stream contains along some forward path from the first given point a first instruction that uses the selected variable before encountering a second instruction that defines the selected variable, and wherein the first span defines a lifetime for the selected variable; a runaway lifetime detector for determining whether at least one of the plurality of variables is live in at least one predetermined location within the second instruction stream, wherein a variable that is live at the predetermined location has a runaway lifetime; and a runaway lifetime truncator for inserting a third instruction into the second instruction stream to eliminate at least one runaway lifetime. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer apparatus for generating a first instruction stream executable on a central processing unit from a second instruction stream, the second instruction stream having a plurality of variables, the computer apparatus comprising:
-
a liveness calculator for determining for each of the plurality of variables a first span of the second instruction stream for which a selected one of the plurality of variables is live, wherein the selected variable is live at a first given point in the second instruction stream if the second instruction stream contains along some forward path from the first given point a first instruction that uses the selected variable before encountering a second instruction that defines the selected variable, and wherein the first span defines a lifetime for the selected variable; a runaway lifetime detector for determining whether at least one of the plurality of variables is live in at least one predetermined location within the second instruction stream, wherein a variable that is live at the predetermined location has a runaway lifetime; and a runaway lifetime truncator for inserting a third instruction into the second instruction stream to eliminate at least one runaway lifetime. - View Dependent Claims (9, 10)
-
-
11. A program product comprising:
-
a recordable media; and a compiler recorded on the recordable media, the compiler being used to generate a first instruction stream executable on a central processing unit in a computer apparatus from a second instruction stream, the second instruction stream having a plurality of variables, the compiler including; a liveness calculator for determining for each of the plurality of variables a first span of the second instruction stream for which a selected one of the plurality of variables is live, wherein the selected variable is live at a first given point in the second instruction stream if the second instruction stream contains along some forward path from the first given point a first instruction that uses the selected variable before encountering a second instruction that defines the selected variable, and wherein the first span defines a lifetime for the selected variable; a runaway lifetime detector for determining whether at least one of the plurality of variables is live in at least one predetermined location within the second instruction stream, wherein a variable that is live at the predetermined location has a runaway lifetime; and a runaway lifetime truncator for inserting a third instruction into the second instruction stream to eliminate at least one runaway lifetime. - View Dependent Claims (12, 13)
-
-
14. A method for determining the lifetimes of a plurality of variables within an instruction stream, comprising the steps of:
-
calculating at least one liveness bit vector corresponding to whether each of the plurality of variables is live at a particular location in the instruction stream, wherein the selected variable is live if the instruction stream contains along some forward path a first instruction that uses the selected variable before encountering a second instruction that defines the selected variable, and wherein a first span of the instruction stream for which the selected variable is live defines a lifetime for the selected variable; determining from at least one of the liveness bit vectors whether at least one of the plurality of variables is live in at least one predetermined location within the second instruction stream, wherein a variable that is live at the predetermined location has a runaway lifetime; and inserting at least one instruction into the instruction stream for truncating at least one of the runaway lifetimes. - View Dependent Claims (15, 16, 17, 18)
-
-
19. A computer implemented method for allocating a plurality of registers within a central processing unit to a plurality of variables within an instruction stream, comprising the steps of:
-
determining a plurality of lifetimes for the plurality of variables; determining whether any of the lifetimes are runaway lifetimes by determining whether any of the plurality of variables are live at the beginning of the instruction stream; truncating at least one runaway lifetime by inserting an instruction into the instruction stream; building an interference graph with a plurality of nodes and a plurality of edges, each live range corresponding to one of the plurality of nodes in the interference graph, the edges of the interference graph representing interferences between nodes; and coloring the interference graph with a number of colors not to exceed the number of the plurality of registers within the central processing unit.
-
-
20. A method for distributing a program product comprising the steps of:
-
initiating a connection between a first computer system and a second computer system; transmitting the program product from the first computer system to the second computer system, the program product being a compiler, the compiler being used to generate a first instruction stream from a second instruction stream, the second instruction stream having a plurality of variables, the compiler including a liveness calculator for determining for each of the plurality of variables a first span of the second instruction stream for which a selected one of the plurality of variables is live, wherein the selected variable is live at a first given point in the second instruction stream if the second instruction stream contains along some forward path from the first given point a first instruction that uses the selected variable before encountering a second instruction that defines the selected variable, and wherein the first span defines a lifetime for the selected variable, and wherein the compiler further comprises a runaway lifetime detector for determining whether at least one of the plurality of variables is live in at least one predetermined location within the second instruction stream, wherein a variable that is live at the predetermined location has a runaway lifetime, and wherein the compiler further comprises a runaway lifetime truncator for inserting a third instruction into the second instruction stream to eliminate at least one runaway lifetime.
-
Specification