Code generation in a machine-independent compiler

ABSTRACT

This paper presents some code generation issues in the context of the PQCC Production-Quality Compiler-Compiler project [8]. The approach taken is unusual in several ways. The machine-dependent information for selection of code sequences, register assignments, etc., has been separated throughout, in tabular form, from the machine-independent algorithms. This not only greatly simplifies the development of code generators for new machines or languages, but paves the way for automatic generation of these tables from formal machine descriptions such as ISP [1]. A parse-tree-like internal program representation is used, facilitating the use of context and data dependency information about expressions. The code generation process has been broken into several phases. This leads to simplification and better understanding of the code generation process, and also allows important improvements in the quality of generated code. The algorithms for preliminary determination of addressing modes, allocation of registers and other locations, and the code selection case analysis are discussed. The algorithms described in the paper are being implemented and used in the PQCC compiler.

REFERENCES

• 1: C. Gordon Bell , A. C. Newell, Computer structures: Readings and examples (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1971
• 2: R.G.G. Cattell. Formalization and Automatic Derivation of Code Generators. (to appear).
• 3: Roderic Geoffrey Galton Cattell, Formalization and automatic derivation of code generators., 1978
• 4: R.G.G. Cattell. Using Machine Descriptions for Automatic Generation of Code Generators. In Proceedings of the 3rd Jerusalem Conference on Information Technology, pages 503-507. North-Holland, 1978.
• 5: Digital Equipment Corporation. VAX-11/780 Architecture Handbook. 1977.
• 6: 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]
• 7: Richard Karl Johnsson, An approach to global register allocation., 1976
• 8: B.W. Leverett, R.G.G. Cattell, S.O. Hobbs, J.M. Newcomer, A.H. Reiner, B.R. Schatz, W.A. Wulf. An Overview of the Production Quality Compiler-Compiler Project. Technical Report CMU-CS-79-105, Carnegie-Mellon University, Computer Science Department, February, 1979.
• 9: Lawrence Livermore Laboratories. S-1 Processor Manual. 1978.
• 10: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 11: Knut Ripken. Formale Beschreibung von Maschinen, Implementierungen und optimierender Maschinecode-erzeugung aus attributierten Programmgraphen. PhD thesis, Technische Universitat Munchen, July, 1977. In German; reviewed in English by Bert Speelpenning, A Review of Ripken's Thesis, unpublished.
• 12: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages