While the term “compiler design” in the title of this book covers a wide range of topics, from parsing and symbol table construction to type checking and code generation, the book is in fact quite specialized. It offers an in-depth exposition on the specific use of aggressive optimizations on intermediate representations of code. The authors bring together many of the results from the last few decades in a coherent and detailed manner, and the result is an excellent resource for those wanting to understand some of the complex issues in building realistic, industrial-strength compilers.

Over half the volume is taken up by chapter 1, “Foundations and Intraprocedural Optimization,” which introduces the concept of static analysis via well-known optimizations such as dead code elimination, constant folding, and partial redundancy elimination. Early on, the authors introduce the concept of an applicability condition that ensures that optimizing transformations maintain the semantic properties of the program. The basis of the semantic descriptions is in control flow graphs, where each edge represents a transformation on the program state and a computation is a path through a control flow graph from a starting point to an ending point. The information that justifies the optimizations (for example, the values of variables or calculated expressions) is characterized by systems of inequalities, leading directly to the notions of partial orders and lattices. With this motivation, the authors introduce the method of fixed-point iteration as a way to calculate the information associated with each point of a control flow graph. After laying this foundation, the authors introduce more optimizations and related techniques, such as interval analysis and points-to analysis. Each transformation is explained with illustrated examples, which show the programs and annotated control flow graphs.

The next two chapters are much shorter, but cover important concepts and extensions. Chapter 2 is concerned with interprocedural optimizations. Optimizing across procedures is complicated by the fact that computations must be considered as nested paths, and the program state, now called a configuration, must capture the stack of called procedures. The authors explain some of the difficulties in using this extension to the semantic basis, and introduce two methods to cope with these difficulties: demand-driven analysis and the call-string approach. Chapter 3 looks at functional languages, which are associated with particular kinds of optimizations. These optimizations require a different approach to representing semantic properties, so the authors introduce a new type of value analysis and a strictness analysis.

The book makes no attempt to cover the wide area of compiler design, and should not be seen as a general textbook for undergraduate study. The authors provide motivation and definitions for many of the concepts in static analysis, and illustrate these ideas through example programs that can be optimized. However, the approach is mathematical and formal, with an emphasis on explaining the correctness of the transformations rather than providing pseudocode to implement them. As such, understanding the concepts involves a fair amount of rigorous, mathematical thinking. As a result, the book is really more suitable for advanced study. In particular, readers will need to have a good grounding in the semantics of programming languages to follow the descriptions of the arguments for correctness.

Muchnick’s well-known reference for compiler optimizations [1] provides detailed explanations and algorithms for many of the same optimizations. While Muchnick extends to over 800 pages, and covers other advanced topics as well, the volume being reviewed here is less than 200 pages long, and is much more focused on explaining the foundations of static analysis using the concise notation of formal semantics. This more mathematical approach is particularly suited for researchers in the area, who will benefit from learning how to argue for the correctness of sophisticated optimizations, which are important aspects of advanced compilers that must produce efficient code that truly represents the original program.