Engineering a simple, efficient code-generator generator

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Engineering a simple, efficient code-generator generator

Full text

Pdf (854 KB)

Source

ACM Letters on Programming Languages and Systems (LOPLAS) archive
Volume 1 , Issue 3 (September 1992) table of contents

Pages: 213 - 226

Year of Publication: 1992

ISSN:1057-4514

Authors

Christopher W. Fraser	AT & T Bell Labs, Murray Hill, NJ
David R. Hanson	Princeton Univ., Princeton, NJ
Todd A. Proebsting	Univ. of Arizona, Tucson

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 116, Citation Count: 50

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/151640.151642 What is a DOI?

ABSTRACT

Many code-generator generators use tree pattern matching and dynamic programming. This paper describes a simple program that generates matchers that are fast, compact, and easy to understand. It is simpler than common alternatives: 200–700 lines of Icon or 950 lines of C versus 3000 lines of C for Twig and 5000 for burg. Its matchers run up to 25 times faster than Twig's. They are necessarily slower than burg's BURS (bottom-up rewrite system) matchers, but they are more flexible and still practical.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	2	A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
	3	Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
	4	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	5	A. Balachandran , D. M. Dhamdhere , S. Biswas, Efficient retargetable code generation using bottom-up tree pattern matching, Computer Languages, v.15 n.3, p.127-140, 1990 [doi>10.1016/0096-0551(90)90006-B]
	6	D. R. Chase, An improvement to bottom-up tree pattern matching, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.168-177, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41640]
	7	H. Emmelmann , F.-W. Schröer , L. Landwehr, BEG: a generation for efficient back ends, ACM SIGPLAN Notices, v.24 n.7, p.227-237, July 1989
	8	FERDINAND, C., SEIDL, H., AND WILHELM, R. Tree automata for code selection. In Code Generation--Concepts, Tools. Techniques, Proceedings of the International Workshop on Code Generation (DagstuhI, Germany), R. Giegerich and S. L. Graham, Eds. Springer-Verlag, New York, 1991, 30-50.
	9	C. W. Fraser, A language for writing code generators, ACM SIGPLAN Notices, v.24 n.7, p.238-245, July 1989
	10	Christopher W. Fraser , David R. Hanson, A code generation interface for ANSI C, Software—Practice & Experience, v.21 n.9, p.963-988, Sept. 1991 [doi>10.1002/spe.4380210906]
	11	Christopher W. Fraser, A retargetable compiler for ANSI C, ACM SIGPLAN Notices, v.26 n.10, p.29-43, Oct. 1991 [doi>10.1145/122616.122621]
	12	Christopher W. Fraser , Robert R. Henry, Hard-coding bottom-up code generation tables to save time and space, Software—Practice & Experience, v.21 n.1, p.1-12, Jan. 1991 [doi>10.1002/spe.4380210102]
	13	Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
	14	Ralph E. Griswold , Madge T. Griswold, The ICON Programming Language, Annabooks, 1996
	15	Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
	16	PELEGRI~-LLOPART, E. Tree transformation in compiler systems. Ph.D. thesis, Computer Science Division, Dept. of Electrical Engineering and Computer Science, Univ. of California, Berkeley, Calif., Dec. 1987.
	17	E. Pelegrí-Llopart , S. L. Graham, Optimal code generation for expression trees: an application BURS theory, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.294-308, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73586]
	18	Todd A. Proebsting, Simple and efficient BURS table generation, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.331-340, June 15-19, 1992, San Francisco, California, United States
	19	STANDARDS PERFORMANCE EVALUATION CORP. SPEC Benchmark Suite Release 1.0. Standards Performance Evaluation Corp., Oct. 1989.

CITED BY 50

	Sreeranga P. Rajan , Masahiro Fujita , Ashok Sudarsanam , Sharad Malik, Development of an optimizing compiler for a Fujitsu fixed-point digital signal processor, Proceedings of the seventh international workshop on Hardware/software codesign, p.2-6, March 1999, Rome, Italy
	Extending Graham-Glanville techniques for optimal code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.6, p.973-1001, Nov. 2000
	Todd A. Proebsting, BURS automata generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.461-486, May 1995
	Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, ACM SIGPLAN Notices, v.30 n.6, p.103-115, June 1995
	Ashok Sudarsanam , Sharad Malik, Simultaneous reference allocation in code generation for dual data memory bank ASIPs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.242-264, April 2000
	J. Van Praet , D. Lanneer , W. Geurts , G. Goossens, Processor modeling and code selection for retargetable compilation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.277-307, July 2001
	Christoph von Praun , Thomas R. Gross, Object race detection, ACM SIGPLAN Notices, v.36 n.11, p.70-82, 11/01/2001
	Anthony M. Sloane, An evaluation of an automatically generated compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.5, p.691-703, Sept. 1995
	Mark S. Peercy , Marc Olano , John Airey , P. Jeffrey Ungar, Interactive multi-pass programmable shading, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.425-432, July 2000
	M. Anton Ertl, Optimal code selection in DAGs, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.242-249, January 20-22, 1999, San Antonio, Texas, United States
	Rainer Leupers, Code generation for embedded processors, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain
	Steven Bashford , Rainer Leupers, Constraint driven code selection for fixed-point DSPs, Proceedings of the 36th ACM/IEEE conference on Design automation, p.817-822, June 21-25, 1999, New Orleans, Louisiana, United States
	Jens Wagner , Rainer Leupers, C Compiler Design for an Industrial Network Processor, ACM SIGPLAN Notices, v.36 n.8, p.155-164, Aug. 2001
	Ashok Sudarsanam , Sharad Malik , Masahiro Fujita, A retargetable compilation methodology for embedded digital signal processors using a machine-dependent code optimizaton library, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Qin Zhao , Bart Mesman , Twan Basten, Static resource models for code-size efficient embedded processors, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.219-250, May 2003
	Gert Goossens , Johan Van Praet , Dirk Lanneer , Werner Geurts , Augusli Kifli , Clifford Liem , Pierre G. Paulin, Embedded software in real-time signal processing systems: design technologies, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Graph-based code selection techniques for embedded processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.4, p.794-814, Oct. 2000
	Christopher W. Fraser , Todd A. Proebsting, Finite-static code generation, ACM SIGPLAN Notices, v.34 n.5, p.270-280, May 1999
	Elizabeth I. Leonard , Constance L. Heitmeyer, Program Synthesis from Formal Requirements Specifications Using APTS, Higher-Order and Symbolic Computation, v.16 n.1-2, p.63-92, March-June 2003
	Oege De Moor , David Lacey , Eric Van Wyk, Universal Regular Path Queries, Higher-Order and Symbolic Computation, v.16 n.1-2, p.15-35, March-June 2003
	Uwe Kastens , Dinh Khoi Le , Adrian Slowik , Michael Thies, Feedback driven instruction-set extension, ACM SIGPLAN Notices, v.39 n.7, July 2004
	Dai Guilan , Zhang Suqing , Tian Jinlan , Jiang Weidu, A study of compiler techniques for multiple targets in compiler infrastructures, ACM SIGPLAN Notices, v.37 n.6, June 2002
	Dai Guilan , Tian Jinlan , Zhang Suqing , Jiang Weidu, An abstract intermediate representation in compilation systems, ACM SIGPLAN Notices, v.38 n.2, February 2003
	Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000
	Paul Klint , Ralf Lämmel , Chris Verhoef, Toward an engineering discipline for grammarware, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.3, p.331-380, July 2005
	David R. Hanson , Todd A. Proebsting, A research C# compiler, Software—Practice & Experience, v.34 n.13, p.1211-1224, 10 November 2004
	Raghavendra Rao Loka, Compilation reuse and hybrid compilation: an experiment, ACM SIGPLAN Notices, v.41 n.4, April 2006
	J. Eliot B. Moss , Trek Palmer , Timothy Richards , Edward K. Walters, II , Charles C. Weems, CISL: a class-based machine description language for co-generation of compilers and simulators, International Journal of Parallel Programming, v.33 n.2, p.231-246, June 2005
	Antony L. Hosking, Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Manuel Hohenauer , Christoph Schumacher , Rainer Leupers , Gerd Ascheid , Heinrich Meyr , Hans van Someren, Retargetable code optimization with SIMD instructions, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea
	Bernd Mathiske , Doug Simon , Dave Ungar, The Project Maxwell assembler system, Proceedings of the 4th international symposium on Principles and practice of programming in Java, August 30-September 01, 2006, Mannheim, Germany
	Jonathan Riehl, Assimilating MetaBorg:: embedding language tools in languages, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA
	John G. Allen , Jesse S. Jin, Code generation for just-in-time compiled mobile collector agents, Selected papers from the 2002 Pan-Sydney workshop on Visualisation, p.1-4, December 01, 2002, Sydney, Australia
	M. Anton Ertl , Kevin Casey , David Gregg, Fast and flexible instruction selection with on-demand tree-parsing automata, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Stefan Farfeleder , Andreas Krall , Edwin Steiner , Florian Brandner, Effective compiler generation by architecture description, ACM SIGPLAN Notices, v.41 n.7, July 2006
	Bowen Alpern , Maria Butrico , Anthony Cocchi , Julian Dolby , Stephen J. Fink , David Grove , Ton Ngo, Experiences Porting the Jikes RVM to Linux/IA32, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.51-64, August 01-02, 2002
	David Ryan Koes , Seth Copen Goldstein, Near-optimal instruction selection on dags, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA
	Florian Brandner , Dietmar Ebner , Andreas Krall, Compiler generation from structural architecture descriptions, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
	Stefan Kraemer , Rainer Leupers , Gerd Ascheid , Heinrich Meyr, Interactive presentation: SoftSIMD - exploiting subword parallelism using source code transformations, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Dietmar Ebner , Florian Brandner , Bernhard Scholz , Andreas Krall , Peter Wiedermann , Albrecht Kadlec, Generalized instruction selection using SSA-graphs, ACM SIGPLAN Notices, v.43 n.7, July 2008
	Mikhail Chalabine , Christoph Kessler, A Formal Framework for Automated Round-Trip Software Engineering in Static Aspect Weaving and Transformations, Proceedings of the 29th International Conference on Software Engineering, p.137-146, May 20-26, 2007
	Rainer Leupers , Peter Marwedel, Retargetable Generation of Code Selectors from HDL Processor Models, Proceedings of the 1997 European conference on Design and Test, p.140, March 17-20, 1997
	K. John Gough, Bottom-up tree rewriting tool MBURG, ACM SIGPLAN Notices, v.31 n.1, p.28-31, Jan. 1996
	Jianjiang Ceng , Manuel Hohenauer , Rainer Leupers , Gerd Ascheid , Heinrich Meyr , Gunnar Braun, C Compiler Retargeting Based on Instruction Semantics Models, Proceedings of the conference on Design, Automation and Test in Europe, p.1150-1155, March 07-11, 2005
	Partha Biswas , Girish Venkataramani, Comprehensive isomorphic subtree enumeration, Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, October 19-24, 2008, Atlanta, GA, USA
	Paolo Bonzini , Laura Pozzi, Recurrence-aware instruction set selection for extensible embedded processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.10, p.1259-1267, October 2008
	Manuel Hohenauer , Felix Engel , Rainer Leupers , Gerd Ascheid , Heinrich Meyr, A SIMD optimization framework for retargetable compilers, ACM Transactions on Architecture and Code Optimization (TACO), v.6 n.1, p.1-27, March 2009
	Jean Bovet , Terence Parr, ANTLRWorks: an ANTLR grammar development environment, Software—Practice & Experience, v.38 n.12, p.1305-1332, October 2008
	Matthias Grumer , Manuel Wendt , Christian Steger , Reinhold Weiss , Ulrich Neffe , Andreas Muehlberger, Power profile estimation and compiler-based software optimization for mobile devices, Journal of Embedded Computing, v.3 n.3, p.231-239, August 2009
	Sara El-Shobaky , Ahmed El-Mahdy , Ahmed El-Nahas, Automatic vectorization using dynamic compilation and tree pattern matching technique in Jikes RVM, Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, p.63-69, July 06-06, 2009, Genova, Italy

INDEX TERMS

Primary Classification:
D. Software
D.3 PROGRAMMING LANGUAGES
D.3.4 Processors
Subjects: Translator writing systems and compiler generators

General Terms:
Languages

Keywords:
Icon programming language, code generation, code-generator generator, dynamic programming, tree pattern matching

REVIEW

"Robert Ballance : Reviewer"

Unlike papers that focus on the theory of pattern matching or its application to code generation, this paper focuses on engineering the pattern matcher. The paper will interest programmers confronted with time or space requirements as well more...

Collaborative Colleagues:

Christopher W. Fraser: colleagues

David R. Hanson: colleagues

Todd A. Proebsting: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player