TCOLAda and the “Middle End” of the PQCC Ada compiler

ABSTRACT

A compiler is traditionally partitioned into a (mostly) machine independent Front End which performs lexical, syntactic, and semantic analysis, and a machine dependent Back End which performs optimization and code generation. In the Ada compiler being implemented at Carnegie-Mellon University in the PQCC project, it is useful to identify a set of phases occurring at the start of the Back End - i.e., “Middle End” - after semantic analysis but before optimization. These phases, known collectively as “CWVM” (an abbreviation for “Compiler Writer's Virtual Machine”) make basic representational choices and reflect these in an expanded program tree. This paper describes both TCOLAda - the intermediate language interface produced by the Front End - and the phases comprising CWVM. TCOLAda is a graph structured high level representation of the source program which includes both the symbol table and the program tree. The CWVM phases perform transformations of the TCOLAda graph which fall into three categories: language oriented (e.g., expansion of checking for constructs such as array indexing), virtual machine oriented (e.g., translation of up-level addressing into “display” vector accesses), and actual machine oriented (e.g., expansion of component selection into address arithmetic).

REFERENCES

• 1: Proc. of SIGPLAN Symposium on the Ada Programming Language, December 1980.
• 2: "Types and Type Resolution in Ada: an Implementation Report", in {ACM 80}.
• 3: B.M. Brosgol, J.M. Newcomer, D.A. Lamb, D.R. Levine, M.S. Van Deusen, W.A. Wulf. TCOLAda: Revised Report on an Intermediate Representation for the Preliminary Ada Language. Technical Report CMU-CS-80-105, Carnegie-Mellon University, February 1980.
• 4: M. Dausmann, S. Drossopoulou, G. Goos, G. Persch, G. Winterstein. AIDA-An Informal Introduction, University of Karlsruhe, Germany, February 1980.
• 5: Digital Equipment Corporation..VAX-11/780 Architecture Handbook, 1977.
• 6: U.S. Department of Defense. Reference Manual for the Ada Programming Language. Proposed Standard Document, July 1980.
• 7: B.W. Leverett. The Packing Problem in Optimizing Compilers, Ph.D. Thesis. Carnegie-Mellon University, to be published.
• 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", Computer, Vol. 13, No. 8, August 1980.
• 9: Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
• 10: M. Sherman, M. Borkan. "A Flexible Semantic Analyzer for Ada," in {ACM 80}.
• 11: C. Wetherell and A. Shannon. LR: Automatic Parser Generator and LR(1) Parser, Lawrence Livermore Laboratory, Preprint UCRL-82926, June 1979.
• 12: W. Wulf, P. Feiler, J. Zinnikas, R. Brender. "A Quantitative Technique for Comparing the Quality of Compiler Code Generation", Tech. Report, Carnegie-Mellon Univ. (to be published).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Ada

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Tools
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages