Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-12-02
2001-09-18
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06292938
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to optimizing compilers for computer programs, and more specifically, to retargeting optimized code by matching tree patterns in directed acyclic graphs.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found in Section 9 of the “Detailed Description of the Preferred Embodiment.” Each of these publications is incorporated by reference herein.)
Programmers write computer programs in high level languages such as assembler language, COBOL, FORTRAN, C, C++, etc. A group of statements written in a language is referred to as source code. Before the source code can be executed, the statements within the source code must be transformed to object code.
Much work has been devoted to building optimizing compilers that generate optimized object code. However, it is often difficult to modify an optimizing compiler built for one target processor to generate optimized object code for a different target processor.
There is also the problem of using tree pattern matching systems (e.g., TWIG [1], BEG [14], BURS [8, 17, 24]) to perform retargetable code generation after code optimization.
In the tree pattern matching approach, the target instruction set is specified by a set of tree patterns defined on the input intermediate language (IL). Analogous to the generation of parsing tables, the tree patterns are translated to pattern matching tables at “compiler-compile” time. An efficient dynamic programming method then uses these tables at compile-time to obtain a minimum-cost parse for each input tree of IL instructions. Automating the generation of pattern matching tables and the process of finding a minimum-cost tree parse leads to significant savings in the programming effort and complexity required for building a code generator. (The terms “tree parsing” and “tree pattern matching” are used interchangeably.)
However, there is a basic mismatch between the ILs that have been used for tree pattern matching and the ILs used by industry-strength optimizing back-ends. ILs used for tree pattern matching are typically structured as a list of expression trees. ILs used in industry-strength optimizing back-ends instead typically use a structure such as quadruples [2] or RTL [21] so as to get the maximum flexibility in code optimization. The optimized code for a basic block in such an IL is structured more generally as a Directed Acyclic Graph (DAG) of instruction nodes [2] defined by true dependences and augmented by anti, output and memory dependences [25]. Since DAGs cannot be fed into a retargetable code generator based on tree pattern matching, the challenge is to identify trees within each basic block DAG so that tree pattern matching can be used to generate correct and efficient target code from the optimized code for a basic block.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for performing retargetable object code generation for a specific processor by matching tree patterns in directed acyclic graphs derived from the source code.
An object of the present invention is to use a tree pattern matching system to perform retargetable code generation after code optimization. Another object of the present invention is to partition block directed acyclic graphs (DAGs), obtained from optimized intermediate code, into trees that can be input to the tree pattern matching system. Yet other objects of the present invention include providing a partitioning method, identifying legality constraints for the partitioning method, and incorporating duplication into the code generation.
REFERENCES:
patent: 4782444 (1988-11-01), Munshi et al.
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5493675 (1996-02-01), Faiman, Jr. et al.
patent: 5613117 (1997-03-01), Davidson et al.
patent: 5836014 (1998-11-01), Faiman, Jr. et al.
patent: 5894576 (1999-04-01), Bharadwaj
Aho et al. Compilers, Principles, Techniques, and Tools. Addison-Wesley . pp. 546-554, Mar. 1988.*
Alfred V. Aho, Mahadevan Ganapathi, and Steven W.K. Tjiang, Code Generation Using Tree Mathing and Dynamic Programming, ACM TOPLAS, 11(4), Oct. 1989, pp. 491-516.
A.V. Aho, R. Sethi, and J.D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986, pp. 290-293.
Ali-Reza Ald-Tabatabai, Geoff Langdate, Steven Lucco, and Robert Wahbe, Efficient and Language-Independent Mobile Programs, In Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, ACM Press, May 1996, pp. 127-136.
M. Auslander and M. Hopkins, An Overview of the PL.8 Compiler, Proceedings of the Sigplan '82 Symposium on Compiler Construction, 17(6):22-31, Jun. 1982.
M.E. Benitez and Jack W. Davidson, A Portable Global Optimizer and Linker, Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, 23(7):329-338, Jun. 1988, Atlanta, Georgia.
Robert J. Blainey, Instruction Scheduling in the TOBEY Compiler, IBM Journal of Research and Development, 38(5):577-593, Sep. 1994.
The Standard Performance Evaluation Corporation, SEPC CPU95 Benchmarks, http://open.specbench.org/osg/cpu95/, ©1996-1999 (1997).
C.W. Fraser, R.R. Henry, and T.A. Proebsting, Burg-Fast Optimal Instruction Selection and Tree Parsing, In Proceedings of the ACM SIGPLAN Notices, 1992, 27(4):68-76, Apr. 1992.
Ron Cytron and Jeanne Ferrants, What's in a Name? Or the Value of Renaming for Parallelism Detection and Storage Allocation, Proceedings of the 1987 International Conference on Parallel Processing, pp. 19-27, Aug. 1987.
Ron Cytron, Jim Lipkis, and Edit Schonbert, A Compiler-Assisted Approach to SPMD Execution, Supercomputing 90, Nov. 1990, pp. 398-406.
Jack W. Davidson and Christopher W. Frase, The Design and Application of a Retargetable Peephole Optimizer, ACM TOPLAS, 2,(2):191-202, Apr. 1980.
Jack W. Davidson and Christopher W. Fraser, Code Selection Through Object Code Optimization, ACM TOPLAS, 6(4), Oct. 1984, pp 505-526.
David A. Dunn and Wei-Chung Hsu, Instruction Scheduling for the HP PA-8000, IEEE 1996, pp. 298-307.
H. Emmelman, F.W. Schroer, and R. Landwehr, BEG-A generator for Efficient Back Ends, Proceedings of the SIGPLAN 1989 Conference on Programming Language Design and Implementation, 23(7):227-237, Jul. 1989.
Christian Ferdinand, Helmut Seidl, and Reinhard Wilhelm, Tree Automata for Code Selection, Acta Informatics, (31):741-760, 1994.
C. Fraser, D. Hanson, A Retargetable C Compiler—Design and Implementation, The Benjamin/Cummings Publishing Company, Inc., 1995, pp 373-405.
C. Fraser and D. Hanson, and T.A. Proebsting, Engineering a simple, Efficient Code-Generator Generator, ACM Letters on Programming Languages and Systems, 1(3):212-226, Sep. 1992.
M. Ganapathi and Charles N. Fischer, Affix Grammar-Driven Code Generation, ACM Transactions on Programming Languages and Systems, 4(7):560-599, 1985.
R.S. Glanville and Susan L. Graham, A New Method for Compiler Code Generation, Proceedings of the Fifth Annual ACM Symposium on Principles of Programming Languages, Jan. 1978, pp. 231-240.
Roger Hoover and Kenneth Zadeck, Generating Machine-Specific Optimizing Compilers, Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 219-229, Jan. 1996.
Steven S. Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann Publishers, Inc., San Francisco, California, 1997, pp 486-494.
Kevin O'Brien, Kathryn M. O'Brien, Martin Hopkins, Arvin Shepherd, and Ron Unrau, XIL and YIL: The Intermediate Languages of TOBEY,
Sarkar Vivek
Serrano Mauricio Jose
Simons Barbara Bluestein
Chaki Kakali
Gates & Cooper LLP
International Business Machines - Corporation
Zhen Wei
LandOfFree
Retargeting optimized code by matching tree patterns in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Retargeting optimized code by matching tree patterns in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Retargeting optimized code by matching tree patterns in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452617