Extending Graham-Glanville techniques for optimal code generation

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.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi, Efficient tree pattern matching (extended abstract): an aid to code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.334-340, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318663]
• 2: 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]
• 3: 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]
• 4: Thomas W. Christopher , Philip J. Hatcher , Ronald C. Kukuk, Using dynamic programming to generate optimized code in a Graham-Glanville style code generator, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.25-36, June 17-22, 1984, Montreal, Canada
• 5: Christian Ferdinand , Helmut Seidl , Reinhard Wilhelm, Tree automata for code selection, Acta Informatica, v.31 n.9, p.741-760, Nov. 1994
• 6: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 7: 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]
• 8: Mahadevan Ganapathi , Charles N. Fischer, Affix grammar driven code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.560-599, Oct. 1985 [doi>10.1145/4472.4486]
• 9: 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.
• 10: 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]
• 11: Philip J. Hatcher , Thomas W. Christopher, High-quality code generation via bottom-up tree pattern matching, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-130, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512655]
• 12: 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.
• 13: 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]
• 14: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 15: Johnson, S. 1975. Yacc - yet another compiler compiler. Tech. Rep. TR 32, AT & T, Bell Laboratories, New Jersey, USA.
• 16: 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.
• 17: Andreas Neumann , Helmut Seidl, Locating Matches of Tree Patterns in Forests, Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, p.134-145, December 17-19, 1998
• 18: Nymeyer, A. and Katoen, J. 1997. Code generation based on formal BURS theory and heuristic search. Acta Informatica 34, 8, 597-636.
• 19: 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]
• 20: 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]
• 21: 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
• 22: Priti Shankar , Amitrajan Gantait , A. R. Yuvaraj , Maya Madhavan, A new algorithm for linear regular tree pattern matching, Theoretical Computer Science, v.242 n.1-2, p.125-142, July 6, 2000 [doi>10.1016/S0304-3975(98)00205-9]
• 23: Beatrix Weisgerber , Reinhard Wilhelm, Two Tree Pattern Matchers for Code Selection, Proceedings of the 2nd CCHSC Workshop on Compiler Compilers and High Speed Compilation, p.215-229, October 10-14, 1988

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.4 Processors
          Subjects: Translator writing systems and compiler generators

General Terms:
Algorithms, Languages

Keywords:
code-generator generator, optimal code generation, tree pattern matching