Finite-state code generation

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

• AGT89: 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]
• ATLLW96: Ali-Reza Adl-Tabatabai , Geoff Langdale , Steven Lucco , Robert Wahbe, Efficient and language-independent mobile programs, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.127-136, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• DF80: Jack W. Davidson , Christopher W. Fraser, The Design and Application of a Retargetable Peephole Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.191-202, April 1980 [doi>10.1145/357094.357098]
• DF84: Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
• Eng96: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.160-170, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• FH95: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• FHP92a: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• FHP92b: 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]
• GG78: R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
• GG83: Ralph E. Griswold , Madge T. Griswold, ICON Programmng Language, Prentice Hall Professional Technical Reference, 1983
• HO82: 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]
• KR88: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• LY97: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• PLG88: 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]
• Pro95: Todd A. Proebsting, BURS automata generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.461-486, May 1995 [doi>10.1145/203095.203098]
• PW96: Todd A. Proebsting , Benjamin R. Whaley, One-Pass, Optimal Tree Parsing - With Or Without Trees, Proceedings of the 6th International Conference on Compiler Construction, p.294-308, April 24-26, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General
          Subjects: Standards

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Standardization, Theory