Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-05-04
2001-06-19
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06249910
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to compiler technology. More particularly, the invention relates to incrementally updating static single assignment (SSA) form for cloned variable name definitions.
BACKGROUND OF THE INVENTION
Most compilers perform optimizations on a source program in order to produce object code that executes faster and which consumes minimal memory space. SSA is an intermediate representation of a source program that is typically used during the optimization phase of a compiler. The SSA form requires each program variable to be defined only once. This form is simpler and efficient for use in several optimizations, such as register promotion, loop unrolling, code motion, constant propagation, dead code elimination, partial redundancy elimination, and the like.
FIG. 1A
illustrates a control flow graph
100
depicting the intermediate representation of a source program. The variable, x, is defined in nodes
102
,
104
and used in nodes
106
,
108
. A definition is an instruction that assigns a value to a variable (e.g., “x=”) and a use is an instruction that uses the value assigned to the variable (e.g., “=x”). Since the variable, x, is defined more than once, the intermediate representation is not in SSA form.
In order to represent a source program in SSA form, a variable is represented by one or more cloned variable names. A phi-function (&PHgr;-function) is used at join points to define a cloned variable name that represents the definitions of the variable and the associated cloned variable name definitions that can reach the join point.
FIG. 1B
shows the control graph
100
in SSA form. There are multiple cloned variable names representing x: a first cloned variable name, x
1
, is defined in node
102
and is used in nodes
106
,
108
; a second cloned variable name, x
2
, is defined in node
104
and used in node
108
; and a third cloned variable name, x
3
, is defined and used in node
108
. The phi-function (&PHgr;(x
1
,x
2
)) in join node
108
is used to indicate the definitions of x that reach the join node
108
. The cloned variable name x
3
is assigned the definition that reaches the join node
108
, which in this case can be either x
i
or x
2
. The multiple cloned variable names x
1
, x
2
, x
3
are used to conform the intermediate representation to SSA form. The variable x is replaced by the multiple cloned variable names, x
1
, x
2
, x
3
, each of which is defined only once thereby satisfying the SSA form.
A compiler can perform one or more optimization phases where each optimization phase can leave the intermediate representation in non-SSA form. The task of reconstructing the entire program into the SSA form after each optimization phase is time consuming and expensive. For this reason, incremental SSA update techniques have been proposed. The incremental SSA update techniques reconstruct portions of a program that were affected by a particular optimization technique into SSA form after the optimization occurs. The incremental SSA update techniques avoid reconstructing the entire program after each optimization is performed. However, the incremental SSA update techniques need to be efficient in order to be practical for commercial implementations.
SUMMARY OF THE INVENTION
The present invention pertains to an apparatus and a method for incrementally updating a source code representation having cloned variable name definitions to static single assignment (SSA) form. A source program is processed by a compiler to produce a target program that is executed on a computer. The compiler can represent the source program in an intermediate code representation to which one or more optimizations or program transformations are applied. The SSA form is used by the program transformations and at times the application of a program transformation can result in non-SSA form. The incremental SSA update apparatus and method described herein transforms the intermediate code representation back into the SSA form so that additional processing can be performed.
The incremental SSA update procedure receives an intermediate representation of a source program in non-SSA form having one or more cloned variable name definitions that correspond to an original variable name. The intermediate representation includes a control flow graph having nodes representing basic blocks. Each node includes instructions that use or define variables. A definition or definition instruction is an instruction that assigns a value to a variable and a use or use instruction is an instruction that uses the value assigned to the variable. The incremental SSA update procedure renames each definition of an original variable name with a new cloned variable name in order to ensure that there is only one definition associated with each name. The original variable name is effectively replaced by the multiple cloned variable names.
The incremental SSA update procedure collects an original variable name and its corresponding cloned variable names. An iterative dominance frontier set is formed for the nodes containing cloned variable name definitions and an original variable name definition. A single phi-function is inserted in each node in the iterative dominance frontier set and is assigned to a new cloned variable name. The calculation of the iterative dominance frontier set is computed only once since all the names are considered simultaneously. In addition, only a single phi-function is inserted for each node in the iterative dominance frontier set thereby eliminating unnecessary duplicates.
The incremental SSA update procedure proceeds to alter each use of an original variable name to the cloned variable name that reaches the use. The arguments of the inserted phi-functions are then updated with the cloned variable names that reach the inserted phi-functions. Finally, the method eliminates all dead instructions including the original variable definitions, redundant cloned variable definitions, and redundant inserted phi-functions. By eliminating each of these names simultaneously, the method guarantees that no new dead instructions remain which may have been inserted by either the program transformation or the incremental SSA update procedure.
An advantage of each of these above mentioned improvements is a reduction in the compilation time and in the amount of memory space required for the compilation process. The computational efficiency reduces the overhead expense incurred in using the apparatus and method thereby making its use practical for commercial implementations of any compilation or optimization process.
REFERENCES:
patent: 5293631 (1994-03-01), Rau et al.
patent: 5327561 (1994-07-01), Choi et al.
patent: 5448734 (1995-09-01), Burke et al.
patent: 5659754 (1997-08-01), Grove et al.
patent: 5724565 (1998-03-01), Dubey et al.
patent: 5768596 (1998-06-01), Chow et al.
patent: 5920716 (1999-07-01), Johnson et al.
patent: 5978588 (1999-11-01), Wallace
patent: 5991540 (1999-11-01), Radigan
patent: 6029005 (1999-11-01), Radigan
“Incremental Computation of Static Single Assignment Form” IBM Corporation Jong-Deok Choi et al., Nov. 1995.*
“Efficiently Computing Static Single Assignment Form and the Control Dependence Graph” R Cytron et al IBM Research, Oct. 1991.*
Choi, Jong-Deok, et al.; Incremental Computation Of Static Single Assignment Form; Nov. 1995; Technical Report TR ADTI-1995-019, published by IBM, Software Solutions Division, Application Development Technology Institute, San Jose California.
Cyton, Ron, et.; Efficiently Computing Static Single Assignment Form And The Control Dependence Graph; published ACM Transactions on Programming Languages and Systems, vol. 13, No. 4, Oct. 1991, pp. 451-990.
Gillies David Mitford
Ju Dz-ching
Sastry A. V. S.
Hartnett Clare T.
Hewlett--Packard Company
Nguyen-Ba Hoang-Vu Antony
Powell Mark R.
LandOfFree
Apparatus and method for incrementally update static single... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for incrementally update static single..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for incrementally update static single... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505688