Engineering a Compiler, 2nd Edition

The proliferation of processors, environments, and constraints on systems has cast compiler technology into a wider variety of settings, changing the compiler and compiler writer’s role. No longer is execution speed the sole criterion for judging compiled code. Today, code might be judged on how small it is, how much power it consumes, how well it compresses, or how many page faults it generates. In this evolving environment, the task of building a successful compiler relies upon the compiler writer’s ability to balance and blend algorithms, engineering insights, and careful planning. Today’s compiler writer must choose a path through a design space that is filled with diverse alternatives, each with distinct costs, advantages, and complexities.

Engineering a Compiler explores this design space by presenting some of the ways these problems have been solved, and the constraints that made each of those solutions attractive. By understanding the parameters of the problem and their impact on compiler design, the authors hope to convey both the depth of the problems and the breadth of possible solutions. Their goal is to cover a broad enough selection of material to show readers that real tradeoffs exist, and that the impact of those choices can be both subtle and far-reaching.

Authors Keith Cooper and Linda Torczon convey both the art and the science of compiler construction and show best practice algorithms for the major passes of a compiler. Their text re-balances the curriculum for an introductory course in compiler construction to reflect the issues that arise in current practice.

• Focuses on the back end of the compiler-reflecting the focus of research and development over the last decade.
• Uses the well-developed theory from scanning and parsing to introduce concepts that play a critical role in optimization and code generation.
• Introduces the student to optimization through data-flow analysis, SSA form, and a selection of scalar optimizations.
• Builds on this background to teach modern methods in code generation: instruction selection, instruction scheduling, and register allocation.
• Presents examples in several different programming languages in order to best illustrate the concept.
• Provides end-of-chapter exercises, with on-line solutions available to instructors.

This entirely revised second edition of Engineering a Compiler is full of technical updates and new material covering the latest developments in compiler technology. In this comprehensive text you will learn important techniques for constructing a modern compiler. Leading educators and researchers Keith Cooper and Linda Torczon combine basic principles with pragmatic insights from their experience building state-of-the-art compilers. They will help you fully understand important techniques such as compilation of imperative and object-oriented languages, construction of static single assignment forms, instruction scheduling, and graph-coloring register allocation.

• In-depth treatment of algorithms and techniques used in the front end of a modern compiler
• Focus on code optimization and code generation, the primary areas of recent research and development
• Improvements in presentation including conceptual overviews for each chapter, summaries and review questions for sections, and prominent placement of definitions for new terms
• Examples drawn from several different programming languages

Changes This Edition

The second edition of Engineering a Compiler presents both perspectives: big-picture views of the problems in compiler construction and detailed discussions of algorithmic alternatives. In preparing the second edition of Engineering a Compiler, we focused on the usability of the book, both as a textbook and as a reference for professionals. Specifically, we:

• Improved the flow of ideas to help the student who reads the book sequentially. Chapter introductions explain the purpose of the chapter, lay out the major concepts, and provide a high-level overview of the chapter’s subject matter. Examples have been reworked to provide continuity across chapters. In addition, each chapter begins with a summary and a set of keywords to aid the user who treats Engineering a Compiler as a reference book.
• Added section reviews and review questions at the end of each major section. The review questions provide a quick check as to whether or not the reader has understood the major points of the section.
• Moved definitions of key terms into the margin adjacent to the paragraph where they are first defined and discussed.
• Revised the material on optimization extensively so that it provides broader coverage of the possibilities for an optimizing compiler.

Compiler development today focuses on optimization and on code generation. A newly hired compiler writer is far more likely to port a code generator to a new processor or modify an optimization pass than to write a scanner or parser. The successful compiler writer must be familiar with current best-practice techniques in optimization, such as the construction of static single-assignment form, and in code generation, such as software pipelining. They must also have the background and insight to understand new techniques as they appear during the coming years.

Finally, they must understand the techniques of scanning, parsing, and semantic elaboration well enough to build or modify a front end. Our goal for the second edition of Engineering a Compiler has been to create a text and a course that exposes students to the critical issues in modern compilers and provides them with the background to tackle those problems. We have retained, from the first edition, the basic balance of material. Front ends are commodity components; they can be purchased from a reliable vendor or adapted from one of the many open-source systems. At the same time, optimizers and code generators are custom-crafted for particular processors and, sometimes, for individual models, because performance relies so heavily on specific low-level details of the generated code. These facts affect the way that we build compilers today; they should also affect the way that we teach compiler construction.

Read a Sample Chapter from Engineering a Compiler on “Practical Issues”

Even with automatic parser generators, the compiler writer must manage several issues to produce a robust, efficient parser for a real programming language. This chapter addresses several issues that arise in practice.

Table of Contents

Chapter 1. Overview of Compilation
Chapter 2. Scanners
Chapter 3. Parsers
Chapter 4. Context-Sensitive Analysis
Chapter 5. Intermediate Representations
Chapter 6. The Procedure Abstraction
Chapter 7. Code Shape
Chapter 8. Introduction to Optimization
Chapter 9. Data-Flow Analysis
Chapter 10. Scalar Optimizations
Chapter 11. Instruction Selection
Chapter 12. Instruction Scheduling
Chapter 13. Register Allocation
Appendix A. ILOC
Appendix B. Data Structures