Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1995-12-06
2001-03-13
Banankhah, Majid (Department: 2755)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06202203
ABSTRACT:
A portion of the Disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to optimizing compilers for development of computer programs for use on a computer, and more particularly to value numbering.
2. Description of the Related Art
A problem addressed by the optimizing compiler prior art is equivalence of expressions. Value numbering is a conventional technique for identifying expressions of equivalent values. A value number in the prior art is a symbolic execution of a basic block of code, in which all variables entering that basic block of code (straight line code) are given distinct symbolic values or value numbers. The technique of value numbering is used for common subexpression elimination within a basic block, where if a symbolic value is computed twice within the same basic block, then it may be eliminated the second time. However, use of the prior art value number techniques are limited to a single basic block or an extended basic block (two adjacent basic blocks). The prior art techniques do not provide optimizations such as common subexpression elimination or redundancy removal beyond basic blocks and extended basic blocks to an entire program consisting of multiple extended basic blocks.
Value numbering optimization may be understood by reference to the optimizing compiler art.
FIG. 1
illustrates a procedure for translating a program
10
to create an executable binary object program
12
. A lexical/syntax analysis
14
is conducted to transform source program
10
to a first intermediate language program
16
. First intermediate language program
16
is then processed by an optimization routine
18
to create a second intermediate language program
20
, which is then directly interpreted by the code generation routine
22
to create object program
12
.
Optimization routine
18
is illustrated in
FIG. 2
as it is understood in the art. Optimization processing is achieved by first performing a control flow analysis in routine
24
of first intermediate language
16
. Control flow analysis routine
24
provides the control flow data
26
, which are then passed to a data-flow analysis routine
28
wherein first intermediate language program
16
is analyzed for data flow. Conventional value numbering may be regarded as part of this data flow analysis. Data-flow analysis routine
28
produces the data-flow data
30
. Finally, a program transformation procedure
32
accepts control flow data
26
, data-flow data
30
, and first intermediate language program
16
to produce second intermediate language program
20
. Optimization routine
18
may use value numbering to enable the program transformation procedure
32
to perform various optimizations such as induction variable analysis, dependence analysis, and loop fusion.
Many methods for value numbering are known in the art. For instance, in Rosen et al. (B. Rosen, M. Wegman, and K. Zadeck, “Global Value Numbers and Redundant Computations”, Fifteenth ACM Principles of Programming Languages Symposium, 12-27, January 1988, San Diego, Calif.), a program is translated into Static Single Assignment Form (SSA). See Cytron et al. (R. Cytron and J. Ferrante, “An Efficient Method for Computing Static Single Assignment Form”, Sixteenth Annual ACM Symposium on Principles of Programming Languages Symposium, 25-35, January 1989), and then value numbering is performed locally in basic blocks.
Thus, practitioners in the art generally employ value numbers only within basic blocks or extended basic blocks to perform various optimizations, and there is an accordingly clearly-felt need in the art for a global value numbering that may be performed globally across an entire computer program.
SUMMARY OF THE INVENTION
The invention disclosed herein comprises a method of, system for, and computer program product for providing a fast and efficient way of performing global value numbering beyond basic blocks and extended basic blocks on a complete topological ordering of basic blocks in a program. Global value numbering makes use of an unknown value number and iterative processing of a worklist containing expressions assigned an unknown value number. A hash table is used to reduce storage and processing time.
In one aspect of the present invention, value numbering is performed globally within an entire program.
In another aspect of the present invention, a fast and efficient technique for performing global value numbering based on Static Single Assignment Form (SSA) is provided.
The present invention has the advantage of providing improved compilation optimization.
The present invention has the further advantage of improved optimization with reduced compilation time.
The present invention has the further advantage of improved optimization with reduced storage.
REFERENCES:
patent: 4398249 (1983-08-01), Pardo et al.
patent: 4642764 (1987-02-01), Auslander et al.
patent: 4656583 (1987-04-01), Auslander et al.
patent: 4802091 (1989-01-01), Cocke et al.
patent: 5327561 (1994-07-01), Choi et al.
patent: 5448737 (1995-09-01), Burke et al.
patent: 5659754 (1997-08-01), Grove et al.
patent: 5768596 (1998-06-01), Chow et al.
patent: 5790867 (1998-08-01), Schmidt et al.
A. V. Aho, R. Sethi, J. D. Ullman, Compilers Principles, Techniques, and Tools, Addison Wesley, pp. 292-293, 528-533, 634-636, 709, 1986.
J. Choi, R. Cytron, J. Ferrnate, “On the Efficient Engineering of Ambitious Program Analysis”, IEEE Trans. Software Eng. vol. 20, No. 2, pp 105-114, 1994.
B. K. Rosen, M. N. Wegmen, and F. K. Zadeck, “Global value numbers and redundant computations”, 15th ACM Principles of Programming Languages Symposium, San Diego, CA, pp. 12-27, 1988.
H. Y.Saade, et al, “Value Numbering in the Context of Merging Control Flow”, IBM Technical Disclosure Bulletin, vol. 25, No. 12, pp. 6338-6341, May 1983.
C. Click, “Global Code Motion Global Value Numbering”, ACM, pp. 246-257, Jun. 1995.
K. Pingali, et al, “Dependence Flow Graphs: An Agebraic Approach to Program Dependencies”, ACM, pp. 67-78, 1990.
Rosen et al, Global Value Numbers and Redundant Computations, ACM, pp. 12-27, Dec. 1988.
E. Morel and C. Renvoise, “Global Optimization by Suppression of Partial Redundancies”, Communications of the ACM, vol. 22, No. 2, Feb. 1979, p. 96-103.
B. Rosen, M. Wegman, and K. Zadeck, “Global Value Numbers and Redundant Computations”, Fifteenth ACM Principles of Programming Languages Symposium, 12-27, Jan. 1988, San Diego, CA.
R. Cytron and J. Ferrante, “An Efficient Method for Computing Static Single Assignment Form”, Sixteenth Annual ACM Symposium on Principles of Programming Languages Symposium, 25-35, Jan. 1989. Also published as “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph”, RC 14756, Jul. 10, 1989, IBM Research Report.
B. Alpern, N. Wegman, and F. Zadeck, “Detecting Equality of Values in Programs”, Conf. Rec. Fifteenth ACM Symposium on Principles of Programming Languages Symposium, 1-11, Jan. 1988.
Takimoto et al, “Partial Redundancy Elimination Based on Phi Function Motion”, Japan Science, p. 21-30.
Banankhah Majid
International Business Machines - Corporation
Johnson Prentiss Wayne
Lao Sue
LandOfFree
Method of, system for, and computer program product for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of, system for, and computer program product for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of, system for, and computer program product for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438557