An experiment in table driven code generation

ABSTRACT

We have constructed a local code generator for the VAX-112 using a parser-like instruction pattern matcher. The code generator replaces the second pass of the UNIX3 Portable “Crdquo; compiler. This paper describes the design of the code generator and the special considerations imposed by the pattern matching process. We summarize the structure of the machine description grammar and its associated semantic actions, as well as the tools we developed to manipulate the large VAX description. In our experience, this approach makes the instruction selection phase of the compiler easier and faster to implement, and more likely to be correct than traditional techniques.

REFERENCES

• 1: R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
• 2: John Crawford, Engineering a production code generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.205-215, June 23-25, 1982, Boston, Massachusetts, United States
• 3: Jack Winfred Davidson, Simplifying code generation through peephole optimization, 1981
• 4: Stuart I. Feldman, Implementation of a portable Fortran 77 compiler using modern tools, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.98-106, August 06-10, 1979, Denver, Colorado, United States
• 5: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, 1980
• 6: Robert Giegerich, Automatic generation of machine specific code optimizers, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.75-81, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582162]
• 7: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
• 8: 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]
• 9: Graham, S.L. "Table Driven Code Generation", IEEE Computer 13(8), pp. 25-33 (August, 1980).
• 10: Gujral, I. S. Retargetable Code Generation for ADA10 Compilers, TP 127, Softech, Waltham, MA. (December, 1981).
• 11: Henry, R.R. "The Code Generator Generator's Work Station: Experiments with the Graham-Glanville Machine Independent Algorithms for Code Generation", Master's Project Report, UCB/ERL M81/47, Electronics Research Laboratory, University of California, Berkeley (June, 1981).
• 12: Jansohn, H.S. and Landwehr R. "CGSS: Ein System zur Automatischen Erzeugung von Codegeneratoren", Universitat Karlsruhe, Karlsruhe, West Germany (July, 1980).
• 13: Johnson, S.C. and Ritchie, D.M., "Portability of C programs and the UNIX System", Bell System Technical Journal 57(6), pp. 2021-2048 (July. 1979).
• 14: Johnson, S.C. Personal Communication, (July, 1981).
• 15: Joy, W.N., Graham, S.L., Haley, C.B. Berkeley Pascal User's Manual Version 1.1,. Computer Science Division, University of California, Berkeley. (April, 1979).
• 16: Rudolf Landwehr , Hans-Stephan Jansohn , Gerhard Goos, Experience with an automatic code generator generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.56-66, June 23-25, 1982, Boston, Massachusetts, United States
• 17: Thomas M. Morgan , Lawrence A. Rowe, Analyzing exotic instructions for a retargetable code generator, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.197-204, June 23-25, 1982, Boston, Massachusetts, United States
• 18: Schulman, R.A. "A Reimplementation of the Second Pass of the Portable C Compiler", Master's Project Report, Electronics Research Laboratory, University of California, Berkeley (to appear).
• 19: 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]

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: Retargetable compilers

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

General Terms:
Languages