Efficient tree pattern matching (extended abstract): an aid to code generation

ABSTRACT

We show that tree pattern matching has significant advantages in the specification and implementation of efficient code generators. We present a top-down tree-matching algorithm that is particularly well suited to code generation applications. Finally, we present a new back-end language that incorporates tree pattern matching with dynamic programming into a uniform framework for the specification and implementation of efficient code generators.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
• 3: A. V. Aho , S. C. Johnson, Optimal Code Generation for Expression Trees, Journal of the ACM (JACM), v.23 n.3, p.488-501, July 1976 [doi>10.1145/321958.321970]
• 4: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 5: A. V. Aho , S. C. Johnson , J. D. Ullman, Code-generation for machines with multiregister operations, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.21-28, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512953]
• 6: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 7: John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
• 8: Roderic Geoffrey Galton Cattell, Formalization and automatic derivation of code generators., Carnegie Mellon University, Pittsburgh, PA, 1978
• 9: Christopher Warwick Fraser, Automatic generation of code generators., Yale University, New Haven, CT, 1977
• 10: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, The University of Wisconsin - Madison, 1980
• 11: Mahadevan Ganapathi , Charles N. Fischer, Description-driven code generation using attribute grammars, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.108-119, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582165]
• 12: Mahadevan Ganapathi , Charles N. Fischer , John L. Hennessy, Retargetable Compiler Code Generation, ACM Computing Surveys (CSUR), v.14 n.4, p.573-592, Dec. 1982 [doi>10.1145/356893.356897]
• 13: Mahadevan Ganapathi , Charles N. Fischer, Instruction selection by attributed parsing, Stanford University, Stanford, CA, 1984
• 14: Mahadevan Ganapathi , Charles N. Fischer, Attributed linear intermediate representations for retargetable code generators, Software—Practice & Experience, v.14 n.4, p.347-364, April 1984 [doi>10.1002/spe.4380140406]
• 15: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., University of California, Berkeley, 1977
• 16: 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]
• 17: 17. S. L. Graham, "Table-Driven Code Generation", IEEE Computer, Vol. 13 No. 8, pp. 25-34, August 1980.
• 18: Robert Rettig Henry, Graham/glanville code generators (compiler, parser, programming language), University of California, Berkeley, 1984
• 19: 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]
• 20: 20. G. Huet and J.-J. Levy. "Call by need computations in non-ambiguous linear term rewriling systems". TR 359. IRIA Laboria. LeChesnay. France, 1979.
• 21: 21. S. C. Johnson, "YACC - Yet Another Compiler Compiler", Computer Sciences Technical Report #32. Bell Telephone Laboratories, Murray Hill. New Jersey, 1975.
• 22: S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512771]
• 23: Hans Hermann Kron, Tree templates and subtree transformational grammars., University of California, Santa Cruz, 1975
• 24: 24. H.-W. Lang, M. Schimmler and H. Schmeck, "Matching Tree Patterns sublinear on the average", Technical Report, Department of Informatik, University of Kiel, Kiel, West Germany, 1980.
• 25: 25. H. Lunell, "Code Generator Writing Systems", Software Systems Research Center, S-58183, Linkoping, Sweden, 1983.
• 26: 26. K. Ripken, "Formale Beschreibun von Maschinen, Implementierungen und Optimicrender Maschinen-codeerzcugung aus Attributierten Programmgraphe", TUMINFO-7731, Institut fur Informatik, Technische Universitat Munchen, Munich, West Germany, July 1977.
• 27: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• 28: 28. S. Tjiang, Private communication, October 1984.
• 29: Stephen Gibbs Wasilew, A compiler writing system with optimization capabilities for complex object order structures, Northwestern University, Evanston, IL, 1972
• 30: Steven William Weingart, An efficient and systematic method of compiler code-generation., Yale University, New Haven, CT, 1973
• 31: 31. W. Wulf, B. Leverett, R. Cattell, S. Hobbs, J. Newcomer, A. Reiner and B. Schatz, "An Overview of the Production Quality Compiler-Compiler Project", IEEE Computer Vol. 13 No. 8. pp. 38-49, August 1980.
• 32: 32. W. A. Wulf. "PQCC: A Machine-Relative Compiler Technology", IEEE 4th International COMPSAC Conference, pp. 24 - 36, Chicago, October 1980.

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

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Languages, Performance, Theory