Abstract
We propose a new technique for constructing code-generator generators, which combines the advantages of the Graham-Glanville parsing technique and the bottom-up tree parsing approach. Machine descriptions are similar to Yacc specifications. The construction effectively generates a pushdown automaton as the matching device. This device is able to handle ambigious grammars, and can be used to generate locally optimal code without the use of heuristics. Cost computations are performed at preprocessing time. The class of regular tree grammars augmented with costs that can be handled by our system properly includes those that can be handled by bottom-up systems based on finite-state tree parsing automata. Parsing time is linear in the size of the subject tree. We have tested the system on specifications for some systems and report table sizes.
- Aho, A. and Ganapathi, M. 1985. Efficient tree pattern matching: An aid to code generation. In Proc. 12th ACM Symp. on Principles of Programming Languages. 334-340. Google Scholar
- Balachandran, A., Dhamdhere, D., and Biswas, S. 1990. Efficient retargetable code generation using bottom up tree pattern matching. Computer Languages 3, 15, 127-140. Google Scholar
- Chase, D. 1987. An improvement to bottom up tree pattern matching. In Proc. of the 14th ACM Symp. on Principles of Programming Languages. 168-177. Google Scholar
- Christopher, T., Hatcher, P., and Kukuk, R. 1984. Using dynamic programming to generate optimised code in a Graham-Glanville style code generator. In Proceedings of the ACM SIGPLAN 1984 Symposium on Compiler Construction. 25-36. Google Scholar
- Ferdinand, C., Seidl, H., and Wilhelm, R. 1994. Tree automata for code selection. Acta Informatica 31, 741-760. Google Scholar
- Fraser, C. and Hanson, D. 1995. A Retargetable C Compiler: Design and Implementation. Benjamin/Cummings, Redwood City, Redwood City, California. Google Scholar
- Fraser, C., Hanson, D., and Proebsting, T. 1992. Engineering a simple, efficient code-generator generator. ACM Letters on Prog. Lang. and Systems 1, 3, 213-226. Google Scholar
- Ganapathi, M. and Fischer, C. 1985. Affix grammar driven code generation. ACM Trans. Program. Lang. Syst. 7, 4, 560-599. Google Scholar
- Gantait, A. 1996. Design of a bottom-up tree pattern matching algorithm and its application to code generation. M.E.Project Report, Dept of Computer Science and Automation, Indian Institute of Science, Bangalore, India.Google Scholar
- Graham., S. and Glanville, R. 1978. A new approach to compiler code generation. In Proc. of the 5th ACM Symp. om Principles of Programming Languages. 231-240. Google Scholar
- Hatcher, P. and Christopher, T. 1986. High-quality code generation via bottom-up tree pattern matching. In Proc. of the 13th ACM Symp. on Principles of Programming Languages. 119-130. Google Scholar
- Henry, R.andDamron, P.1989. Performance of table driven generators using tree pattern matching. Tech. Rep. 89-02-02, Computer Science Dept, Univ of Washington.Google Scholar
- Hoffman, C. and O'Donnell, M. 1982. Pattern matching in trees. Journal of the ACM 29, 1, 68-95. Google Scholar
- Hopcroft, J. and Ullman, J. 1979. An Introduction to Automata Theory, Languages and Computation. Addison Wesley. Google Scholar
- Johnson, S. 1975. Yacc - yet another compiler compiler. Tech. Rep. TR 32, AT & T, Bell Laboratories, New Jersey, USA.Google Scholar
- Kumar, R. 1992. Retargetable code generation using bottom-up tree pattern matching. M.E. Project Report, Dept of Computer Science and Automation, Indian Institute of Science, Bangalore, India.Google Scholar
- Neumann, A. and Seidl, H. 1998. Locating matches of tree patterns in forests. In Proceedings of 18th FSTTCS, LNCS 1530. 134-145. Google Scholar
- Nymeyer, A. and Katoen, J. 1997. Code generation based on formal BURS theory and heuristic search. Acta Informatica 34, 8, 597-636.Google Scholar
- Pelegri-Llopart, E. and Graham., S. 1988. Optimal code generation for expression trees. In Proc. of the 15th ACM Symp. on Principles of Programming Languages. 119-129. Google Scholar
- Proebsting, T. 1995. BURS automata generation. ACM Trans. Program. Lang. Syst. 17, 3, 461-486. Google Scholar
- Proebsting, T. and Whaley, B. 1996. One-pass optimal tree parsing- with or without trees. In International Conference on Compiler Construction. 294-308. Google Scholar
- Shankar, P., Gantait, A., Yuvaraj, A., and Madhavan, M. 2000. A new algorithm for linear regular tree pattern matching. Theor. Comput. Sci. 242, 125-142. Google Scholar
- Weisberger, B. and Willhelm, R. 1988. Two tree pattern matchers for code selection. In Compile compilers and high speed compilation, LNCS 371. 215-229. Google Scholar
Index Terms
- Extending Graham-Glanville techniques for optimal code generation
Recommendations
BURS automata generation
A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small code-generator generator implementation produces BURS tables efficiently, even for complex instruction set descriptions. The algorithm does not ...
A fast general parser for automatic code generation
MTPP'10: Proceedings of the Second Russia-Taiwan conference on Methods and tools of parallel programming multicomputersThe code generator in a compiler attempts to match a subject tree against a collection of tree-shaped patterns for generating instructions. Tree-pattern matching may be considered as a generalization of string parsing. We propose a new generalized LR (...
Reviews
Robert Ballance
Code generation is the phase in a compiler when the compiler translates from an internal, high-level representation of the program into actual machine instructions. Often, the high-level representation is a tree. Fundamentally, instruction selection can be treated as tree rewriting via pattern matching. The actual selection criterion is some cost model. One effective cost model is the execution time of an instruction. In 1978, Glanville and Graham showed that one could treat instruction selection by first linearizing the internal form of the program, and then applying the pattern matching techniques inherent in a parser. While this approach works both in theory and practice, the resulting grammars that describe a set of instruction selection rules are themselves unruly, and prone to ambiguities. Controlling the choices made by the parser is tricky. This paper extends the Glanville-Graham techniques to optimal code generation over a restricted set of input grammars. The input grammars are restricted to normal-form tree grammars in which each rule represents either a single internal tree node having fixed arity, a chain rule, or a terminal production. They then require that the input program be a postorder linearization of the program being compiled. Given these restrictions (their effects are documented in the paper), they can proceed to build an augmented parsing automaton similar to a LR(0) parser that properly disambiguates alternative instruction sequences and directs the code generator to the least cost alternative. The paper is accompanied by appropriate examples that guide the reader’s intuition as well as by the formal definitions and proofs required to support their results. Some practical results are provided, although I would have enjoyed seeing more discussion of both the limitations of the approach as well as practical experience. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments