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

PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation

Pages 270 - 280

https://doi.org/10.1145/301618.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

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
Show More Cited By

Index Terms

Finite-state code generation

Recommendations

Finite-state code generation

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 ...
Towards Self-Verification in Finite Difference Code Generation
Correctness'17: Proceedings of the First International Workshop on Software Correctness for HPC Applications

Code generation from domain-specific languages is becoming increasingly popular as a method to obtain optimised low-level code that performs well on a given platform and for a given problem instance. Ensuring the correctness of generated codes is ...
Routine run-time code generation

Run-time code generation (RTCG) would be used routinely if application programmers had a facility with which they could easily create their own run-time code generators, because it would offer benefits both in terms of the efficiency of the code that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI99

Sponsor:

PLDI99: Conference on Programming Language Design and Implementation 1999

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

PLDI '99 Paper Acceptance Rate 26 of 130 submissions, 20%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

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

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
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

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