Engineering a Compiler

This document, "Engineering a Compiler: VAX-11 Code Generation and Optimization," is a book that chronicles the practical experiences of a four-member programming team at Digital Equipment Corporation in building a production-quality compiler. Published in 1982, it focuses primarily on the often "lesser-known" aspects of compiler design: the "back end" phases related to code generation and optimization for the VAX-11 architecture.

Key aspects covered include:

• Compiler Philosophy: The book emphasizes a practical, engineering-driven approach to compiler design, stressing empirical development and continuous improvement over purely theoretical methods.
• Compiler Architecture: It details the modular structure of their compiler, which was initially based on an existing PL/I compiler. A core design principle is the use of a machine-independent Intermediate Language (IL) as a bridge between language-specific "front ends" and the machine-specific "back end."
• Table-Building Language (TBL): A custom high-level language used to define compiler actions, including parsing, semantic reduction, and code generation, which are then interpreted by small, unique interpreters.
• Front End (Parsing & Semantic Analysis): Describes how the front end processes source code, builds a Symbol Table (for program objects like variables and procedures), and creates trees representing operations, which are then transformed into the IL.
• Write Tree Phase: A crucial component that accepts front-end trees, reduces them (performs initial optimizations like constant folding), and translates them into a linear sequence of IL operators, collecting vital usage information.
• Global Optimization: This significant phase performs advanced optimizations on the IL, such as loop invariant removal, common subexpression elimination, value propagation, and selecting variables for register assignment. It relies on constructing and analyzing flow graphs of the program.
• Local Code Generation: Transforms the optimized IL operators into skeletal VAX-11 machine instructions and manages the allocation of compiler temporaries (T-regs).
• Register Allocation: A distinct phase that assigns specific hardware registers (or memory locations) to the temporaries and selected local variables, based on usage patterns and availability.
• Peephole Optimization: The final optimization phase that scans the generated code for specific patterns within small instruction sequences and replaces them with shorter or faster equivalents.
• Multi-Language Support: A notable achievement highlighted is the successful development of a second "front end" for a C compiler that utilized the same common back end (VAX-11 Code Generator and its optimization phases), proving its language-independence.

The document includes numerous code examples and diagrams to illustrate the concepts, with a glossary for PL/I and compiler-specific terms. It serves as a valuable resource for understanding the practical challenges and solutions in building highly optimized compilers for specific hardware architectures.