Engineering a Compiler

Citation

Cooper, K. D., & Torczon, L. (2022). Engineering a Compiler (3rd ed.). Morgan Kaufmann (Elsevier).

Chapter Summary

The book has fourteen chapters and two appendices, about 755 pages of chapter text in all. The publisher describes the third edition as covering the latest developments in compiler technology, with new chapters on semantic elaboration (the problems that arise in generating code from ad-hoc syntax-directed translation schemes in a generated parser), on runtime support for naming and addressability, and on code shape for expressions, assignments and control structures. Page counts below are the chapter lengths implied by the published page ranges.

Chapter 1: Overview of Compilation

The 26-page opening chapter is an overview of compilation that precedes the chapters on the individual phases.

Chapters 2–3: Scanners; Parsers

The two front-end chapters, about 58 and 73 pages, deal with recognizing the words of a program and its grammatical structure. Together they occupy roughly one sixth of the chapter text, a small share compared with the later chapters.

Chapter 4: Intermediate Representations

This chapter (49 pages) turns to the internal forms in which a compiler holds a program while it analyzes and transforms it.

Chapter 5: Syntax-Driven Translation

Chapter 5 (65 pages) covers translation driven by the syntax of the source program. The publisher's description of new material on semantic elaboration refers to generating code from ad-hoc syntax-directed translation schemes in a generated parser, which is the subject this chapter's title points to.

Chapter 6: Implementing Procedures

The chapter (51 pages) is about how procedures are implemented. The publisher lists runtime support for naming and addressability among the topics given new treatment, which fits this chapter's subject.

Chapter 7: Code Shape

Code Shape (52 pages) addresses the form of the code generated for expressions, assignments and control structures, which the publisher also lists as a new chapter topic.

Chapters 8–10: Introduction to Optimization; Data-Flow Analysis; Scalar Optimization

The three optimization chapters make up about 194 pages. They move from an introduction to optimization (69 pages) through data-flow analysis (68 pages), the analysis machinery that optimizations rely on, to scalar optimization (57 pages).

Chapters 11–13: Instruction Selection; Instruction Scheduling; Register Allocation

The code-generation chapters (42, 46 and 50 pages) cover choosing target instructions, ordering them, and assigning values to registers. The publisher notes that the book covers bottom-up methods of register allocation at the local scope.

Chapter 14: Runtime Optimization

The last chapter (43 pages) addresses optimization performed while the program runs.

Appendices A–B

Appendix A (ILOC, 12 pages) and Appendix B (Data Structures, 23 pages) are followed by a bibliography and index.

Key Concepts

Chapters 1–7: From Source to Code

• Compiler structure: the phases a compiler passes a program through.
• Intermediate representations: the internal program forms used for analysis and transformation.
• Semantic elaboration and syntax-driven translation: producing meaning and code from parse results.
• Procedures, naming and code shape: how names, procedure calls and expressions are realized in generated code.

Chapters 8–14: Optimization and Back End

• Data-flow analysis: the analysis underlying optimization.
• Scalar optimization: improvements to the code of single procedures.
• Instruction selection, scheduling and register allocation: the three steps of code generation.
• Runtime optimization: optimization at run time.

Critical Analysis

Strengths

• Emphasis visible in the structure. Optimization and code generation (Chapters 8 to 14) take about half of the chapter text, while the scanner and parser chapters take about a sixth. This matches the publisher's statement that the book pays particular attention to code optimization and code generation.
• A focus on abstraction. The publisher says the book concentrates on how compilers and interpreters implement abstraction, tying the material to the languages that students already know.
• From practising compiler builders. According to the publisher's author notes, Cooper leads and Torczon is a principal investigator on the Massively Scalar Compiler Project at Rice University, and the publisher describes the book as combining basic principles with their experience of building state-of-the-art compilers.
• Support material for courses. Elsevier lists instructor course files for two courses (COMP 412 and COMP 506), an image collection and other resources, and the author notes say Cooper teaches compiler construction at undergraduate and graduate level.

Limitations

• Large. At more than 800 pages including appendices and index, courses will need to select from it.
• A back-end bias. Because the front end takes only two chapters, readers who want to learn parsing and lexical analysis in depth will need another text, and no chapter is devoted to language design or type systems.
• Audience level. The publisher gives the readership as primarily graduate students with some undergraduates, professional compiler writers and system software developers, which suggests demanding material for a first compilers course.
• Instructor-only resources. Course files and other teaching resources are reserved for registered instructors, so independent learners need to design their own projects.

Where It Fits in the Course

Cooper and Torczon is the back-end-heavy textbook of the course books. Aho, Lam, Sethi and Ullman's Compilers: Principles, Techniques, and Tools (the "Dragon Book") covers lexical analysis, parsing, syntax-directed translation, intermediate code, code generation and optimization in one volume and is the long-standing reference, and the two are alternatives or complements. For a first project-based exposure, Nystrom's Crafting Interpreters builds two interpreters for a small language and is free online, while Thain's Introduction to Compilers and Language Design is a compact freely available text for a one-semester course that builds a compiler from a small C-like language to assembly. Either can precede this book.

Pierce's Types and Programming Languages is a graduate treatment of type systems and complements the optimization focus of this book with the theory of languages, which Cooper and Torczon do not cover in a chapter of its own.

How to Use This Book

The book is for readers who already have data structures and algorithms and some systems background, and who want to understand how compilers generate and optimize code. It fits an upper-level compilers course and a first graduate course, and compiler writers and system software developers.

A practical plan:

• Core: Chapter 1, then Chapters 4 to 7, which connect a parsed program to generated code. Chapters 2 and 3 can be read quickly, or replaced by a lighter text, if scanning and parsing are already familiar.
• Optimization: Chapters 8 to 10 in order, since data-flow analysis (Chapter 9) underlies scalar optimization (Chapter 10).
• Back end: Chapters 11 to 13, which can be read in sequence or by interest.
• Optional: Chapter 14, and the appendices (ILOC and data structures) for reference.
• Practice: build a small compiler alongside the reading, adding one phase at a time, and use the chapter exercises to check each algorithm.