Automatic Derivation of Code Generators from Machine Descriptions

ABSTRACT

Work with compiler compilers has dealt principally with automatic generation of parsers and lexical analyzers. Until recently, little work has been done on formalizing and generating the back end of a compiler, particularly an optimizing compiler. This paper describes formalizations of machines and code generators and describes a scheme for the automatic derivation of code generators from machine descriptions. It was possible to separate all machine dependence from the code generation algorithms for a wide range of typical architectures (IBM-360, PDP-11, PDP-10, Intel 8080) while retaining good code quality. Heuristic search methods from work in artificial intelligence were found to be both fast and general enough for use in generation of code generators with the machine representation proposed. A scheme is proposed to perform as much analysis as possible at code generator generation time, resulting in a fast pattern-matching code generator. The algorithms and representations were implemented to test their practicality in use.

REFERENCES

• 1: ALLEN, F., CARTER, J., HARRISON, W., LOEWNER, P., TAPSCOTT, R., TREVILLYAN, L., AND WECMAN, M. The experimental compiling systems project. IBM Res. Rep. RC 6718 (#28922), IBM, Yorktown Heights, N. Y., 1977.
• 2: BARBACCI, M., BARNES, G., CATTELL, R., AND SIEWIOREK, D. ISPS reference manual. Tech. Rep. TR 79-137 (latest revision), Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, Pa., 1977.
• 3: BARBACCI, M., AND SIEWIOREK, D. The CMU RT-CAD system: An innovative approach to computer aided design. Carnegie-Mellon Univ. Comput. Sci. Rev., 1974-1975.
• 4: C. Gordon Bell , A. C. Newell, Computer structures: Readings and examples (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1971
• 5: CATTELL, R.G. A survey and critique of some models of code generation. Unnumbered Tech. Rep., Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, Pa., 1977.
• 6: Roderic Geoffrey Galton Cattell, Formalization and automatic derivation of code generators., 1978
• 7: Roderic G.G. Cattell , Joseph M. Newcomer , Bruce W. Leverett, Code generation in a machine-independent compiler, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.65-75, August 06-10, 1979, Denver, Colorado, United States
• 8: Michael Kelly Donegan, An approach to the automatic generation of code-generators., 1973
• 9: ELSON, M., AND RAKE, S.T. Code-generation technique for large-language compilers. IBM Syst. J. 9, 3 (1970), 166-188.
• 10: FELDMAN, J. A formal semantics for computer-oriented languages. Ph.D. dissertation, Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, Pa., 1964.
• 11: Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
• 12: Christopher Warwick Fraser, Automatic generation of code generators., 1977
• 13: Robert Steven Glanville, A machine independent algorithm for code generation and its use in retargetable compilers., 1977
• 14: 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]
• 15: HOBBS, S. Object code optimization. Unpublished thesis proposal, Comput. Sci., Carnegie- Mellon Univ., Pittsburgh, Pa., 1976.
• 16: 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]
• 17: LEIVE, G. The binding of modules to abstract digital hardware descriptions. Unpublished thesis proposal, Elec. Eng., Carnegie-Mellon Univ., Pittsburgh, Pa., 1977.
• 18: LEVERETT, B., CATTELL, R., HOBBS, S., NEWCOMER, J., REINER, A., SCHATZ, B., AND WULF, W. An overview of the production quality compiler-compiler project. Tech. Rep. TR 79-105, Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, Pa., Feb. 1979 (condensation to appear in IEEE Comput.).
• 19: LUCKHAM, D.C., PARK, D.M.R., AND PATERSON, M.S. On formalized computer programs. J. Comput. Syst. Sci. 4, 3 (1970), 220-249.
• 20: MCKEEMAN, W.M., HORNING, J.J., AND WORTMAN, D.B. A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J., 1970.
• 21: P. L. Miller, AUTOMATIC CREATION OF A CODE GENERATOR FROM A MACHINE DESCRIPTION, Massachusetts Institute of Technology, Cambridge, MA, 1971
• 22: Joseph Michael Newcomer, Machine-independent generation of optimal local code., 1975
• 23: OAKLEY, J.D. Automatic generation of diagnostics from ISP. Unpublished thesis proposal, Comput. Sci., Carnegie-Mellon Univ., Pittsburgh, Pa., Dec. 1976.
• 24: John Denniston Oakley, Symbolic execution of formal machine descriptions, 1979
• 25: REISER, J., ET AL. SAIL Stanford Artificial Intelligence Lab. Memo. AIM-289, Comput. Sci., Stanford Univ., Stanford, Calif., 1976.
• 26: RIPKEN, K. Formale Beschreibung von Maschinen, Implementierungen und optimierender Maschinencodeerzeugung aus attributierten Programmgraphe. Dissertation, Technische Univ. Munchen, Munich, Germany, 1977.
• 27: Hanan Samet, Automatically proving the correctness of translations involving optimized code., 1975
• 28: SIMONEAUX, D.C. High-level language compiling for user-definable architectures. Ph.D. dissertation, Elec. Eng., Naval Postgraduate School, 1975.
• 29: A. Snyder, A PORTABLE COMPILER FOR THE LANGUAGE C, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 30: Steven William Weingart, An efficient and systematic method of compiler code-generation., 1973
• 31: WroTE, J.R. JOSSLE: A language for specifying and structuring the semantic phase of translators. Ph.D. dissertation, Univ. California at Santa Barbara, 1973.
• 32: John Dryer Wick, Automatic generation of assemblers., 1975
• 33: Wmcox, T.R. Generating machine code for high-level programming languages. Ph.D. dissertation, Comput. Sci., Cornell Univ., Ithaca, N.Y., 1971.
• 34: 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
• 35: YOUNC, R. The coder: A program module for code generation in high-level language compilers. M.S. thesis, Comput. Sci., Univ. Illinois, Urbana, 1974.

INDEX TERMS

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

General Terms:
Design, Languages, Performance, Theory