Engineering a production code generator

ABSTRACT

This paper describes the structure of a code generator formed by merging the best aspects of three code generation techniques: Graham-Glanville parser-driven code generation [G] [GG] [GR] [HG], the register allocation/spill mechanism from the Portable C Compiler [J], and a code template expander [W]. The Graham-Glanville method was modified to use a standard LALR parser and table builder, and the register allocation method was extended in several significant ways in order to make optimal use of a machine with characterized registers. This code generator is a part of the Pascal-86 compiler developed by Intel Corporation as one of several compilers supporting its iAPX-86 (8086) microprocessor family. The language supported by the compiler is an extension of the Draft International Standard Pascal, level 0. Object code generated by this method compares favorably to code produced by other compilers for the 8086, as well as Pascal compilers for other machines. Since its release in March 1981, the code generator has proved to be quite reliable and easy to maintain.

REFERENCES

• 1: 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]
• 2: 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
• 3: Roderic Geoffrey Galton Cattell, Formalization and automatic derivation of code generators., 1978
• 4: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
• 5: 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]
• 6: S.L. Graham, "Table-Driven Code Generation", IEEE Computer, August 1980, pp. 25-34.
• 7: Mahadevan Ganapathi, Retargetable code generation and optimization using attribute grammars, 1980
• 8: Susan L. Graham , Robert R. Henry , Robert A. Schulman, An experiment in table driven code generation, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.32-43, June 23-25, 1982, Boston, Massachusetts, United States
• 9: 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]
• 10: K. Ripken, "Formale Beschreibung von Maschinen, Implementierungen und Optimierender Maschinencode-erseugung aus Attributierten Programmgraphen", PhD Dissertation, Technische Universitat Munchen, 1977.
• 11: B. Speelpenning, "A Review of Ripken's Thesis", December 1977, unpublished.
• 12: 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]
• 13: Thomas Richard Wilcox, Generating machine code for high-level programming languages, 1971
• 14: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Languages