Optimal code generation for expression trees: an application BURS theory

ABSTRACT

A Rewrite System is a collection of rewrite rules of the form &agr; &bgr; where &agr; and &bgr; are tree patterns. A rewrite system can be extended by associating a cost with each rewrite rule, and by defining the cost of a rewrite sequence as the sum of the costs of all the rewrite rules in the sequence. The REACHABILITY problem for a rewrite system R is, given an input tree T and a fixed goal tree G, to determine if there exists a rewrite sequence in R, rewriting T into G and, if so, to obtain one such sequence. The C-REACHABILITY problem is similar except that the obtained sequence must have minimal cost among all those sequences writing T into G. This paper introduces a class of rewrite systems called Bottom-Up Rewrite Systems (BURS), and a table-driven algorithm to solve REACHABILITY for member of the class. This algorithm is then modified to solve C-REACHABILITY and specialized for a subclass of BURS so that all cost manipulation is encoded into the tables and is not performed explicitly at solving time. The subclass extends the simple machine grammars [AGH84], rewrite systems used to describe target machine architectures for code generation, by allowing additional types of rewrite rules such as commutativity transformations. A table-driven code generator based on solving C-REACHABILITY has been implemented and tested with several machine descriptions. The code generator solves C-REACHABILITY faster than a comparable solver based on Graham-Glanville techniques [AGH84] (a non-optimal technique), yet requires only slightly larger tables. The code generator runs much faster than recent proposals to solve C-REACHABILITY that use pattern matching and deal with costs explicitly at solving time [AGT86, HeD87, WeW86]. The BURS theory generalizes and unifies the bottom-up approaches of Henry/Damron [HeD87] and Weisgerber/Wilhelm [WeW86].

REFERENCES

• AUJ77: 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]
• AGT86: 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]
• AGH84: Philippe Aigrain , Susan L. Graham , Robert R. Henry , Marshall Kirk McKusick , Eduardo Pelegri-Llopart, Experience with a Graham-Glanville style code generator, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.13-24, June 17-22, 1984, Montreal, Canada
• Cha87: 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]
• GaJ80: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• GIG78: 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]
• GrH84: S. L. Graham and R. R. Henry, "Machine Descriptions for Compiler Code Generation: Experience Since JCIT-3", IEEE 1984 Proceedings of the 4th Jerusalem Conference on Information Technology (.ICIT), Jerusalem, Israel, 1984.
• Hat85: Philip John Hatcher, A tool for high-quality code generation (compiling), 1985
• HaC: 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]
• Hen84: Robert Rettig Henry, Graham/glanville code generators (compiler, parser, programming language), 1984
• Hen87: R. R. Henry, Personal Communication, August 1987.
• HeD87: R. R. Henry and P. C. D~tmron, "Code Generation Using Tree Pattern Matchers", Technical Report 87-02-04, University of Washington, February 10, 1987.
• Joh78: S. C. Johnson, YACC: Yet Another Compiler- Compiler, Bell Laboratories, Murray Hill, NJ, July 1978.
• KMP84: S. E. Keller , J. A. Perkins , T. F. Payton , S. P. Mardinly, Tree transformation techniques and experiences, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.190-201, June 17-22, 1984, Montreal, Canada
• Pat85: David A. Patterson, Reduced instruction set computers, Communications of the ACM, v.28 n.1, p.8-21, Jan. 1985 [doi>10.1145/2465.214917]
• Pel87: E. Pelegri-Llopart, Tree Transformation Systems in Compiler Systems (tentative title), Phi) Dissertation, EECS-University of California, Berkeley, December 1987.
• Rip77: K. Ripken, "Formale Beschreibung yon Maschinen, Implementieurungen und optimierender Maschinencodeerzeugung aus attributierten Programmgraphen", PhD Dissertation, Technische Universitat Munchen, Munich, West Germany, July 1977.
• Tha73: J. W. Thatcher, "Tree Automata: An informal Survey", in Currents in the Theory of Computing, A. V. Aho (editor), Prentice Hall, Englewood Cliffs, NJ, 1973, 143-172.
• WeW86: B. Weisgerber and R. Wilhelm, Two Tree Pattern Matcher for Code Selection (Including Targeting), Technical Report, Universitat des Saarlandes, Saarbrucken, W. Germany, February 1986.

INDEX TERMS

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

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

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Languages, Theory