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

article

Free access

Finite-state code generation

Authors:

Christopher W. Fraser,

Todd A. ProebstingAuthors Info & Claims

ACM SIGPLAN Notices, Volume 34, Issue 5

Pages 270 - 280

https://doi.org/10.1145/301631.301680

Published: 01 May 1999 Publication History

Abstract

This paper describes GBURG, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses). A stack-based virtual machine---known as the Lean Virtual Machine (LVM)---tuned for fast code generation is also described. GBURG translates the two-page LVM-to-x86 specification into a code generator that fits entirely in an 8 KB I-cache and that emits x86 code at 3.6 MB/set on a 266-MHz P6. Our just-in-time code generator translates and executes small benchmarks at speeds within a factor of two of executables derived from the conventional compile-time code generator on which it is based.

References

[1]

Alfred V. Aho, Mahedevan Ganapathi, and Steven W. K. Tjiang. Code generation using tree matching and dynamic programming. A CM Transactions on Programming Languages and Systems, 11(4):491-516, October 1989.

Digital Library

[2]

Ali-Reza Adl-Tabatabai, Geoff Langdale, Steven Lucco, and Robert Wahbe. Efficient and language-independent mobile programs. In Proceedings of the SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 127-136, 1996.

Digital Library

[3]

Jack W. Davidson and Christopher W. Fraser. The design and application of a retargetable peephole optimizer. A CM Transactions on Programming Languages and Systems, 2(2):191-202, April 1980.

Digital Library

[4]

Jack W. Davidson and Christopher W. Fraser. Code selection through object code optimization. A CM Transactions on Programming Languages and Systems, 6(4):7-32, October 1984.

Digital Library

[5]

D.R. Engler. VCODE: a retargetable, extensible, very fast dynamic code generation system. In Proceedings of the SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 160-170, May 1996.

Digital Library

[6]

Christopher W. Fraser and David R. Hanson. A Retargetable C Compiler: Design and implementation. Benjamin/Cummings, Redwood City, California, 1995.

Digital Library

[7]

Christopher W. Fraser, David R. Hanson, and Todd A. Proebsting. Engineering a simple, efficient code-generator generator. A UM Letters on Programming Languages and Systems, 1(3):213- 226, September 1992.

Digital Library

[8]

Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG fast optimal instruction selection and tree parsing. $IGPLAN Notices, 27(4):68-76, April 1992.

Digital Library

[9]

R. Steven Glanville and Susan L. Graham. A new method for compiler code generation. In Proceedings of the 5th Annual Symposium on Principles of Programming Languages, pages 231-240, 1978.

Digital Library

[10]

Ralph E. Griswold and Madge T. Griswold. The Icon Programming Language. Prentice-Hall, Inc., 1983. ISBN 0-13- 449777-5.

Digital Library

[11]

Christoph M. Hoffmann and Michael J. O'Donnell. Pattern matching in trees. Journal of the ACM, 29(1):68-95, january 1982.

Digital Library

[12]

Brian W. Kernighan and Dennis M Ritchie. The C Programming Language. Prentice-Hall, Inc., second edition, 1988. ISBN 0-13-110370-9.

Digital Library

[13]

Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley, 1997. ISBN 0-201- 63452-X.

Digital Library

[14]

Eduardo Pelegri-Llopart and Susan L. Graham. Optimal code generation for expression trees: An application of BURS theory. In Proceedings of the 15th Annual Symposium on Principles of Programming Languages, pages 294- 308, New York, 1988. ACM.

Digital Library

[15]

Todd A. Proebsting. BURS automata generation. A CM Transactions on Programming Languages and Systems, 17(3):461-486, May 1995.

Digital Library

[16]

Todd A. Proebsting and Benjamin R. Whaley. One-pass, optimal tree parsing with or without trees. In 1996 Inter- ~ational Conference on Compiler Construction, pages 294--308, April 1996.

Digital Library

Cited By

Yun SOh S(2007)Automatic Generation of Code Optimizer for DFA Pattern MatchingThe KIPS Transactions:PartA10.3745/KIPSTA.2007.14-A.1.03114A:1(31-38)Online publication date: 28-Feb-2007
https://doi.org/10.3745/KIPSTA.2007.14-A.1.031
Yun SOh S(2005)Table-Driven Code OptimizerProceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies10.1109/PDCAT.2005.232(59-64)Online publication date: 5-Dec-2005
https://dl.acm.org/doi/10.1109/PDCAT.2005.232
Sunglim Yun Seman Oh (2005)Table-Driven Code OptimizerInternational Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06)10.1109/CIMCA.2005.1631509(444-449)Online publication date: 2005
https://doi.org/10.1109/CIMCA.2005.1631509
Show More Cited By

Index Terms

Finite-state code generation

Recommendations

Finite-state code generation
PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation

This paper describes GBURG, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching ...
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 ...
Retargetable code generation for application-specific processors
Special issue: Parallel computing technologies

An approach of intelligent retargetable compiler is introduced to overcome the gap between hardware and software development and to increase performance of embedded systems. It focuses on knowledgeable treatment of code generation where knowledge about ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 34, Issue 5

May 1999

304 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/301631

Editors:
Barbara G. Ryder
Rutgers Univ., New Brunswick, NJ
,
Benjamin G. Zorn
Univ. of Colorado, Boulder
,
A. Michael Berman
Rowan Univ., Glassboro, NJ

Issue’s Table of Contents

PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation
May 1999
304 pages
ISBN:1581130945
DOI:10.1145/301618
Chairmen:
Barbara G. Ryder
Rutgers Univ., New Brunswick, NJ
,
Benjamin G. Zorn
Univ. of Colorado, Boulder, and Microsoft Research

Copyright © 1999 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Published in SIGPLAN Volume 34, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
825
Total Downloads

Downloads (Last 12 months)91
Downloads (Last 6 weeks)14

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yun SOh S(2007)Automatic Generation of Code Optimizer for DFA Pattern MatchingThe KIPS Transactions:PartA10.3745/KIPSTA.2007.14-A.1.03114A:1(31-38)Online publication date: 28-Feb-2007
https://doi.org/10.3745/KIPSTA.2007.14-A.1.031
Yun SOh S(2005)Table-Driven Code OptimizerProceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies10.1109/PDCAT.2005.232(59-64)Online publication date: 5-Dec-2005
https://dl.acm.org/doi/10.1109/PDCAT.2005.232
Sunglim Yun Seman Oh (2005)Table-Driven Code OptimizerInternational Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC'06)10.1109/CIMCA.2005.1631509(444-449)Online publication date: 2005
https://doi.org/10.1109/CIMCA.2005.1631509
Allen JJin J(2003)Code generation for just-in-time compiled mobile collector agentsSelected papers from the 2002 Pan-Sydney workshop on Visualisation - Volume 2210.5555/1164094.1164095(1-4)Online publication date: 1-May-2003
https://dl.acm.org/doi/10.5555/1164094.1164095
Aycock J(2003)A brief history of just-in-timeACM Computing Surveys10.1145/857076.85707735:2(97-113)Online publication date: 1-Jun-2003
https://dl.acm.org/doi/10.1145/857076.857077
Orpaz AWeiss SHenkel JHu XGupta RParameswaran S(2002)A study of CodePackProceedings of the tenth international symposium on Hardware/software codesign10.1145/774789.774811(103-108)Online publication date: 6-May-2002
https://dl.acm.org/doi/10.1145/774789.774811
Orpaz AWeiss S(2002)A study of CodePack: optimizing embedded code spaceProceedings of the Tenth International Symposium on Hardware/Software Codesign. CODES 2002 (IEEE Cat. No.02TH8627)10.1109/CODES.2002.1003609(103-108)Online publication date: 2002
https://doi.org/10.1109/CODES.2002.1003609

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 Issue’s Table of Contents