Article

Free access

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator

Authors:

Thomas W. Christopher,

Philip J. Hatcher,

Ronald C. KukukAuthors Info & Claims

SIGPLAN '84: Proceedings of the 1984 SIGPLAN symposium on Compiler construction

Pages 25 - 36

https://doi.org/10.1145/502874.502877

Published: 01 June 1984 Publication History

PDF eReader

Abstract

We have performed an investigation of using a dynamic programming to generate optimized code in a Graham-Glanville style code generator We use Earley's algorithm rather than an IR algorithm for parsing in the code generator Not only does the use of Earley's algorithm make the construction of the code generator very easy it allows the selection of optimal code by dynamic programming (using a modification of the technique developed by Lvon) We compare two implementations of this technique to conventional hand-coded code generators using a subset of BASIC as the source language Further we discuss the use of this technique in an experimental C compiler.

References

[1]

Aho, A. V. and Johnson, S. C. "Optimal Code Generation For Expression Trees" JACM 23,3(July 76) 488-501.

Digital Library

Google Scholar

[2]

Bird, P. L. "An Implementation of a Code Generator Specification Language for Table Driven Code Generators" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 44-55.

Digital Library

Google Scholar

[3]

Cattell, R. G. G. "Automatic Derivation of Code Generators from Machine Descriptions" TOPLAS 2,2 (Apr. 1980) 173-190

Digital Library

Google Scholar

[4]

Crawford, J. "Engineering a Production Code Generator" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 205-215.

Digital Library

Google Scholar

[5]

Earley, J. "An Efficient Context-Free Parsing Algorithm" CACM 13,2 (Feb 70) 94-102.

Digital Library

Google Scholar

[6]

Glanville, R. S. "A Machine Independent Algorithm for Code Generation and Its Use in Retargetable Compilers" Phd Dissertation, Univ. of California, Berkeley, 1977.

Digital Library

Google Scholar

[7]

Graham, S. L. "Table-Driven Code Generation" Computer, 13,8 (Aug. 1980) 25-34.

Digital Library

Google Scholar

[8]

Graham, S. L., Henry, R. R., Schulman, R. A. "An Experiment in Table Driven Code Generation" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 32-43.

Digital Library

Google Scholar

[9]

Johnson, S. C. "A Portable Compiler: Theory and Practice" Proceedings of the Fifth ACM Symposium on Principles of Programming Languages, Jan 1978.

Digital Library

Google Scholar

[10]

Krumme, D. W., Ackley, D. H. "A Practical Method for Code Generation Based on Exhaustive Search" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 185-196.

Digital Library

Google Scholar

[11]

Landwehr, R., Jansohn, H-S, Goos, G. "Experience with an Automatic Code Generator Generator" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 56-66.

Digital Library

Google Scholar

[12]

Lyon, G. "Syntax-Directed Least-Errors Analysis for Context Free Languages: A Practical Approach" CACM 17,1 (Jan 74) 3-14.

Digital Library

Google Scholar

Cited By

View all

Yang W(2010)A Fast General Parser for Automatic Code GenerationMethods and Tools of Parallel Programming Multicomputers10.1007/978-3-642-14822-4_4(30-39)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14822-4_4
Katoen JNymeyer A(2000)Pattern-matching algorithms based on term rewrite systemsTheoretical Computer Science10.1016/S0304-3975(00)00041-4238:1-2(439-464)Online publication date: 6-May-2000
https://dl.acm.org/doi/10.1016/S0304-3975%2800%2900041-4
Ganapathi MFischer C(1988)Integrating code generation and peephole optimizationActa Informatica10.1007/BF0026884625:1(85-109)Online publication date: 1-Jan-1988
https://dl.acm.org/doi/10.1007/BF00268846
Show More Cited By

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator
1. Software and its engineering
  1. Software notations and tools

Recommendations

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator
Proceedings of the SIGPLAN '84 symposium on compiler construction

We have performed an investigation of using a dynamic programming to generate optimized code in a Graham-Glanville style code generator We use Earley's algorithm rather than an IR algorithm for parsing in the code generator Not only does the use of ...
Graham/glanville code generators (compiler, parser, programming language)
Limitations of Graham-Glanville style code generation

In recent years, the Graham-Glanville approach to code generation has become an increasingly important influence on new compiler writing projects. Initial enthusiasm prompted by the early research results has now fueled projects with more practical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGPLAN '84: Proceedings of the 1984 SIGPLAN symposium on Compiler construction

June 1984

328 pages

ISBN:0897911393

DOI:10.1145/502874

General Chair:
Mary Van Deusen
IBM
,
Program Chair:
Susan L. Graham
University of California, Berkeley

ACM SIGPLAN Notices Volume 19, Issue 6
Proceedings of the SIGPLAN '84 symposium on compiler construction
June 1984
318 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/502949
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1984

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
485
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)31

Reflects downloads up to 04 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yang W(2010)A Fast General Parser for Automatic Code GenerationMethods and Tools of Parallel Programming Multicomputers10.1007/978-3-642-14822-4_4(30-39)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14822-4_4
Katoen JNymeyer A(2000)Pattern-matching algorithms based on term rewrite systemsTheoretical Computer Science10.1016/S0304-3975(00)00041-4238:1-2(439-464)Online publication date: 6-May-2000
https://dl.acm.org/doi/10.1016/S0304-3975%2800%2900041-4
Ganapathi MFischer C(1988)Integrating code generation and peephole optimizationActa Informatica10.1007/BF0026884625:1(85-109)Online publication date: 1-Jan-1988
https://dl.acm.org/doi/10.1007/BF00268846
Spector DTurner P(1987)Limitations of Graham-Glanville style code generationACM SIGPLAN Notices10.1145/24686.2469622:2(100-107)Online publication date: 1-Feb-1987
https://dl.acm.org/doi/10.1145/24686.24696
Horspool R(1987)An Alternative to the Graham-Glanville Code-Generation MethodIEEE Software10.1109/MS.1987.2307044:3(33-39)Online publication date: 1-May-1987
https://dl.acm.org/doi/10.1109/MS.1987.230704
Hatcher PChristopher T(1986)High-quality code generation via bottom-up tree pattern matchingProceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/512644.512655(119-130)Online publication date: 1-Jan-1986
https://dl.acm.org/doi/10.1145/512644.512655
Yang W(2010)A fast general parser for automatic code generationProceedings of the Second Russia-Taiwan conference on Methods and tools of parallel programming multicomputers10.5555/1927517.1927523(30-39)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.5555/1927517.1927523
Shankar P(2010)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420040579.ch15Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch15
Shankar P(2009)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420043839.ch17(17-1-17-36)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch17
Horspool RScheunemann A(2006)Automating the selection of code templatesSoftware: Practice and Experience10.1002/spe.438015050915:5(503-514)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380150509
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator

Graham/glanville code generators (compiler, parser, programming language)

Limitations of Graham-Glanville style code generation