Fast and flexible instruction selection with on-demand tree-parsing automata

ABSTRACT

Tree parsing as supported by code generator generators like BEG, burg, iburg, lburg and ml-burg is a popular instruction selection method. There are two existing approaches for implementing tree parsing: dynamic programming, and tree-parsing automata; each approach has its advantages and disadvantages. We propose a new implementation approach that combines the advantages of both existing approaches: we start out with dynamic programming at compile time, but at every step we generate a state for a tree-parsing automaton, which is used the next time a tree matching the state is found, turning the instruction selector into a fast tree-parsing automaton. We have implemented this approach in the Gforth code generator. The implementation required little effort and reduced the startup time of Gforth by up to a factor of 2.5.

REFERENCES

• 1: 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]
• 2: 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]
• 3: M. Anton Ertl , David Gregg, Combining stack caching with dynamic superinstructions, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C. [doi>10.1145/1059579.1059583]
• 4: H. Emmelmann , F.-W. Schröer , L. Landwehr, BEG: a generation for efficient back ends, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.227-237, June 19-23, 1989, Portland, Oregon, United States
• 5: 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]
• 6: 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]
• 7: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 8: 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]
• 9: 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]
• 10: Jan Heering , Paul Klint , Jan Rekers, Incremental Generation of Parsers, IEEE Transactions on Software Engineering, v.16 n.12, p.1344-1351, December 1990 [doi>10.1109/32.62443]
• 11: 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]
• 12: 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]
• 13: Eric Schnarr , James R. Larus, Fast out-of-order processor simulation using memoization, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.283-294, October 02-07, 1998, San Jose, California, United States

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
automaton, dynamic programming, instruction selection, lazy, tree parsing