More Web Proxy on the site http://driver.im/

Article

Free access

An experiment in table driven code generation

Authors:

Susan L. Graham,

Robert R. Henry,

Robert A. SchulmanAuthors Info & Claims

SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction

Pages 32 - 43

https://doi.org/10.1145/800230.806978

Published: 01 June 1982 Publication History

Abstract

We have constructed a local code generator for the VAX-11² using a parser-like instruction pattern matcher. The code generator replaces the second pass of the UNIX³ Portable “Crdquo; compiler. This paper describes the design of the code generator and the special considerations imposed by the pattern matching process. We summarize the structure of the machine description grammar and its associated semantic actions, as well as the tools we developed to manipulate the large VAX description. In our experience, this approach makes the instruction selection phase of the compiler easier and faster to implement, and more likely to be correct than traditional techniques.

References

[1]

Cattell, R.G., "Automatic Derivation of Code Generators from Machine Descriptions", ACM Transactions on Programming Languages and Systems 2(2), pp. 173-190 (April, 1980).

Digital Library

[2]

Crawford, John. "Engineering a Production Code Generator", Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction, (June 23-25, 1982).

Digital Library

[3]

Davidson, J.W. Simplifying Code Generation Through Peephole Optimization, PhD Dissertation, TR 81-19, Department of Computer Science, University of Arizona (December, 1981).

Digital Library

[4]

Feldman, S.I., "Implementation of a Portable Fortran 77 Compiler Using Modern Tools", Proceedings of the SIGPLAN Symposium on Compiler Construction, 14(8) pp 98-106 (August, 1979).

Digital Library

[5]

Ganapathi, M. "Retargetable Code Generation and Optimization Using Attribute Grammars", PhD Dissertation, TR #406, Computer Science Department, University of Wisconsin, Madison, WI (1980).

Digital Library

[6]

Giegerich, R. "Automatic Generation of Machine Specific Code Optimizers", in Conf. Record Ninth ACM Symp. Principles of Programming Languages, (January 25-27, 1982).

Digital Library

[7]

Glanville, R.S. "A Machine Independent Algorithm for Code Generation and its Use in Retargetable Compilers", PhD Dissertation, UCB CS-78-01, Computer Science Division, EECS, University of California, Berkeley (December, 1977).

Digital Library

[8]

Glanville, R.S., and Graham, S.L. "A New Method for Compiler Code Generation", Conf. Record Fifth ACM Symp. Principles of Programming Languages (January, 1978).

Digital Library

[9]

Graham, S.L. "Table Driven Code Generation", IEEE Computer 13(8), pp. 25-33 (August, 1980).

Digital Library

[10]

Gujral, I. S. Retargetable Code Generation for ADA10 Compilers, TP 127, Softech, Waltham, MA. (December, 1981).

[11]

Henry, R.R. "The Code Generator Generator's Work Station: Experiments with the Graham-Glanville Machine Independent Algorithms for Code Generation", Master's Project Report, UCB/ERL M81/47, Electronics Research Laboratory, University of California, Berkeley (June, 1981).

[12]

Jansohn, H.S. and Landwehr R. "CGSS: Ein System zur Automatischen Erzeugung von Codegeneratoren", Universitat Karlsruhe, Karlsruhe, West Germany (July, 1980).

[13]

Johnson, S.C. and Ritchie, D.M., "Portability of C programs and the UNIX System", Bell System Technical Journal 57(6), pp. 2021-2048 (July. 1979).

[14]

Johnson, S.C. Personal Communication, (July, 1981).

[15]

Joy, W.N., Graham, S.L., Haley, C.B. Berkeley Pascal User's Manual Version 1.1,. Computer Science Division, University of California, Berkeley. (April, 1979).

[16]

Landwehr, R., Jansohn, H.S., and Goos, G. "Experience with an Automatic Code Generator Generator", Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction, (June 23-25, 1982).

Digital Library

[17]

Morgan, Thomas M. and Rowe, Lawrence A., "Analyzing Exotic Instructions for a Retargetable Cede Generator", Proceedings of the ACM SIGPLAN '82 Symposium on Compiler Construction, (June 23-25, 1982).

Digital Library

[18]

Schulman, R.A. "A Reimplementation of the Second Pass of the Portable C Compiler", Master's Project Report, Electronics Research Laboratory, University of California, Berkeley (to appear).

[19]

Sethi, R. and Ullman, J.D. "The Generation of Optimal Code for Expressions", JACM 17(4), pp. 715-728 (1970).

Digital Library

Cited By

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
Hanson D(2006)Simple code optimizationsSoftware: Practice and Experience10.1002/spe.438013080813:8(745-763)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380130808
Graham SKessler PMcKusick M(2006)An execution profiler for modular programsSoftware: Practice and Experience10.1002/spe.438013080313:8(671-685)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380130803
Show More Cited By

Index Terms

An experiment in table driven code generation
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers
      2. Source code generation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching

Recommendations

An experiment in table driven code generation
Proceedings of the 1982 SIGPLAN symposium on Compiler construction

We have constructed a local code generator for the VAX-11² using a parser-like instruction pattern matcher. The code generator replaces the second pass of the UNIX³ Portable “Crdquo; compiler. This paper describes the design of the code generator and ...
Affix grammar driven code generation

Affix grammars are used to describe the instruction set of a target architecture for purposes of compiler code generation. A code generator is obtained automatically for a compiler using attributed parsing techniques. A compiler built on this model can ...
Improving SIMD code generation in QEMU
DATE '15: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition

Modern processors are often enhanced using SIMD instructions, such as the MMX, SSE, and AVX instructions set in the x86 architecture, or the NEON instruction set in the ARM architecture. Using these SIMD instructions could significantly increase ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction

June 1982

357 pages

ISBN:0897910745

DOI:10.1145/800230

ACM SIGPLAN Notices Volume 17, Issue 6
Proceedings of the 1982 SIGPLAN symposium on Compiler construction
June 1982
347 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/872726
Issue’s Table of Contents

Copyright © 1982 Authors.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1982

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
649
Total Downloads

Downloads (Last 12 months)108
Downloads (Last 6 weeks)15

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Hanson D(2006)Simple code optimizationsSoftware: Practice and Experience10.1002/spe.438013080813:8(745-763)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380130808
Graham SKessler PMcKusick M(2006)An execution profiler for modular programsSoftware: Practice and Experience10.1002/spe.438013080313:8(671-685)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380130803
Graham SKessler PMcKusick M(2004)gprofACM SIGPLAN Notices10.1145/989393.98940139:4(49-57)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1145/989393.989401
Goossens GVan Praet JLanneer DGeurts WKifli ALiem CPaulin P(2001)Embedded software in real-time signal processing systemsReadings in hardware/software co-design10.5555/567003.567041(433-451)Online publication date: 1-Jun-2001
https://dl.acm.org/doi/10.5555/567003.567041
Goossens GVan Praet JLanneer DGeurts WKifli ALiem CPaulin P(1997)Embedded software in real-time signal processing systems: design technologiesProceedings of the IEEE10.1109/5.55871885:3(436-454)Online publication date: Mar-1997
https://doi.org/10.1109/5.558718
Oudshoorn MMarlin C(1993)Interpretive language implementation from a layered operational modelProceedings of ICCI'93: 5th International Conference on Computing and Information10.1109/ICCI.1993.315401(71-76)Online publication date: 1993
https://doi.org/10.1109/ICCI.1993.315401
McConnell CJohnson R(1992)Using static single assignment form in a code optimizerACM Letters on Programming Languages and Systems10.1145/151333.1513681:2(152-160)Online publication date: 1-Jun-1992
https://dl.acm.org/doi/10.1145/151333.151368
Kuo YKung LJeng GCheng T(1990)A retargetable compiler for the generation of control routines of a microprocessor-based digital systemNinth Annual International Phoenix Conference on Computers and Communications. 1990 Conference Proceedings10.1109/PCCC.1990.101658(469-476)Online publication date: 1990
https://doi.org/10.1109/PCCC.1990.101658
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
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents