Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-06-16
2001-10-09
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06301704
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to optimization of computer programs and more particularly to efficient performance of optimizing compilation.
2. Related Art
Current global scalar optimization technology requires the compiler to transform a source code program into an equivalent intermediate representation (IR). Based on the IR, the compiler then generates additional information about the program, e.g., the places in the program where each variable is defined and used (referred to as use-def information). A global scalar optimization procedure uses the IR and the program information to transform the IR. This transformed version of the IR, once compiled, should execute more quickly than the original version of the program. In this sense, the program has undergone an optimization during compilation.
Some global scalar optimizations, however, fail to transform the program information when they transform the IR into a new IR. If so, the program information, which has not been transformed, is no longer useful for purposes of subsequent optimization. If additional optimizations are to be performed, they must be performed on the current, transformed version of the IR, to which the previously generated program information no longer corresponds. That program information is now irrelevant. Hence an additional optimization will require that new program information be generated, based on the new IR, before this IR can be further optimized. Therefore, any optimization that transforms the current version of the IR only, and, in so doing, renders the existing program information obsolete, necessitates regeneration of the program information if subsequent optimization is required. This regeneration represents costly overhead each time a subsequent global scalar optimization procedure is performed.
Therefore, what is needed is a method, system, and computer program product for global scalar optimization that operates on a source program to produce an IR and its associated program information, where each optimization procedure transforms the program information as well as the IR. This would allow performance of subsequent optimization procedures without having to regenerate updated program information each time.
SUMMARY OF THE INVENTION
The present invention is a method and system for using static single assignment (SSA) form as a program representation and a medium for performing global scalar optimization. A compiler first expresses the computer program in SSA form, which serves as both the IR and the program information. The compiler can then perform one or more static single assignment (SSA)-based, SSA-preserving global scalar optimization procedures on the SSA form. Such a procedure modifies the SSA form of the program while preserving the utility of the SSA form for purposes of subsequent optimizations.
An advantage of the present invention is that when the SSA form is transformed during an SSA-based, SSA-preserving optimization procedure, the program information incorporated in the SSA form is necessarily transformed as well. A subsequent SSA-based, SSA-preserving optimization therefore does not require separate regeneration or updating of program information before the optimization can be executed. This saves time during the optimization process.
Further features and advantages of the invention as well as the operation of various embodiments of the present invention are described in detail below with reference to the accompanying drawings.
REFERENCES:
patent: 5659754 (1997-08-01), Grove et al.
patent: 5768596 (1998-06-01), Chow et al.
Chow et al., “A New Algorithm for Partial Redundancy Elimination based on SSA Form”,Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation(PLDI), Jun. 15-18, 1997, pp. 273-286.
Chow et al., “Effective Representation of Aliases and Indirect Memory Operations in SSA Form”,Proceedings of the Sixth International Conference on Compiler Construction, Apr. 1996, pp. 253-267.
Cocke, J. and Ken Kennedy, “An Algorithm for Reduction of Operator Strength”,Communications of the ACM, vol. 20, No. 11, Nov. 1977, pp. 850-856.
Cytron et al., “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph”,ACM Transactions on Programming Language and Systems, vol. 13, No. 4, Oct. 1991, pp. 451-490.
Kennedy et al., “Strength Reduction via SSAPRE”,Proceedings of the Seventh International Conference on Compiler Construction, Mar. 1998, pp. 144-158.
Liu et al., “Loop Induction Variable Canonicalization in Parallelizing Compilers”,Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques(PACT '96), 1996, pp. 228-237.
K. Cooper and T. Simpson, “Value-driven Code Motion”, Technical Report CRPC-TR95637-S, Dept. of Computer Science, Rice University, Oct. 1995.
J. Choi, R. Cytron, and J. Ferrante, “Automatic Construction of Sparse Data Flow Evalution Graphs”,Conference Record of the Eighteenth ACM Symposium on Principles of Programming Languages, pp. 55-66, Jan. 1991.
K. Drechsler and M. Stadel, “A Variation of Knoop, Rüthing and Steffen's Lazy Code Motion”,ACM SIGPLAN Notices, 28(5):29-38, May 1993.
Knoop, J. et al., “Optimal Code Motion: Theory and Practice”,ACM Trans. on Programming Languages and Systems, 16(4):1117-1155, Jul. 1994.
Knoop, J. et al., “Lazy Code Motion”,Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 224-234, Jun. 1992.
Dhamdhere, D. et al., “How to Analyze Large Programs Efficiently and Informatively”,Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 212-223, Jun. 1992.
Johnson, R., “Efficient Program Analysis Using Dependence Flow Graphs”, Technical Report (PhD Thesis), Dept. of Computer Science, Cornell University, pp. iii-xi and 1-230, Aug. 1994.
P. Briggs and K. Cooper, “Effective Partial Redundancy Elimination”,Proceedings of the ACM SIGPLAN '94 Conference on Programming language Design and Implementation, pp. 159-170, Jun. 1994.
Muchnick, Steven S.,Advanced Compiler Design and Implementation, Morgan Kauffman Publishers, Inc., 1997, pp. 745-746.
E. Morel and C. Renvoise, “Global Optimization by Suppression of Partial Redundancies”,Communications of the ACM, vol. 22, No. 2, Feb. 1979, pp. 96-103.
Chan Sun
Chow Frederick
Dahl Peter
Kennedy Robert
Liu Shin-Ming
Powell Mark R.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
Vo Ted T.
LandOfFree
Method, system, and computer program product for using... 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, system, and computer program product for using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and computer program product for using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574345