Engineering a Compiler [Hardcover]

Keith Cooper (Author), Linda Torczon (Author)

Book Description

Publication Date: November 10, 2003 | ISBN-10: 155860698X | ISBN-13: 978-1558606982 | Edition: 1

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.

Editorial Reviews

Amazon.com Review

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.

---

--This text refers to an alternate Hardcover edition.

Review

Keith Cooper and Linda Torczon are leading compilers researchers who have also built several state-of-the-art compilers. This book adeptly spans both worlds, by explaining both time-tested techniques and new algorithms, and by providing practical advice on engineering and constructing a compiler. Engineering a Compiler is a rich survey and exposition of the important techniques necessary to build a modern compiler.
-Jim Larus, Microsoft Research

A wonderful introduction to the theory, practice, and lore of modern compilers. Cooper and Torczon convey the simple joys of this subject that
follow from the elegant interplay between compilation and the rest of computer science. If you're looking for an end-to-end tour of compiler
construction annotated with a broad range of practical experiences, this is the book.
-Michael D. Smith, Harvard University

Modern compilers have played critical roles in areas such as software development tools, application performance, and processor design. This book has done an excellent job of illustrating various state-of-the-art technologies for an advanced compiler, in particular, optimization and code generation, the core of modern compilers. Compilers have evolved into complicated software and what makes a good compiler largely lies in the wisdom of engineering during design and development. The readers of this book can certainly learn how to construct a modern compiler with various engineering trade-offs.

-Roy Ju, Senior Researcher,Microprocessor Research Labs, Intel Corp.

As researchers, the authors have made major contributions to the literature and as teachers, they have produced leaders in the field. The combination is reflected in a book that is rich with the insight of great research and written with the clarity of experienced teachers. The result is an outstanding text.

-Steve Blackburn, The Australian National University

See all Editorial Reviews

Product Details

• Hardcover: 801 pages
• Publisher: Morgan Kaufmann; 1 edition (November 10, 2003)
• Language: English
• ISBN-10: 155860698X
• ISBN-13: 978-1558606982
• Product Dimensions: 9.1 x 8.1 x 1.6 inches
• Shipping Weight: 4.2 pounds
• Average Customer Review: 3.6 out of 5 stars  See all reviews (14 customer reviews)
• Amazon Best Sellers Rank: #95,800 in Books (See Top 100 in Books)
  • #2 in Books > Computers & Technology > Programming > Languages & Tools > Compiler Design
  • #3 in Books > Computers & Technology > Programming > Languages & Tools > Compilers
  • #34 in Books > Computers & Technology > Hardware > Microprocessors & System Design

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

95 of 95 people found the following review helpful:

5.0 out of 5 stars Super compiler text!, February 21, 2005

By 

Jos van Roosmalen (The Netherlands, Europe) - See all my reviews
(REAL NAME)   

This review is from: Engineering a Compiler (Hardcover)

This is really a super compiler text. It is also one of the most recent compiler books you can buy.

First of all this is a theoretical book. If you read the title 'Engineering a compiler' as 'Coding/Building a compiler' you would be disappointed! So, if you're looking for a learing-by-coding book, this is not for you (but I have some recommendations at the end of this review in the latest paragraph). The difference with most of the other theoretical books is that this book is not a dry text. It has also a nice layout. It gives plenty of examples, and all topics are well connected to each other. It's a pleasure to read for not native English people, so native English people can read it pretty fast.

This book read like a novel.. It does contain enough diagrams, tables, etc. but not too much (crowded), and everything is well explained.

You can read this book as a compiler introduction book. But I can only recommend this to B.Sc/M.Sc Computer Science students (like me). You don't need to have a M.Sc in Mathematics to understand this text, (all the math, eg. liveness graphs are well explained), but you will understand everything better if you have some background in algorithms (design), pseudocode, etc. like you gained during your B.Sc program. People without formal computer science education I would recommend to read a practical book first (see at the end of this review), because you may find else this text too theoretical.

This book focus on code optimizations. According to the authors (and me) compiler front ends (scanning/parsing/etc) are commodities today, and the backend (codegeneration) is where the difference is made nowadays. So if you're looking for a introduction text into compiler optimization this book is for you!

If you're looking for a more practical book I advice you to read 'Programming Language Processors in Java' from Watt & Brown. In that book you learn to build a nice stack virtual machine in Java with 'advanced features' like records (structs), procedures/functions, arrays and so on. That book is a good companion for 'Engineering a Compiler' to give you some practical insight. If you're looking for a Language Design book I advice you to look at 'Programming Language Pragmatics'. Both books are worth the money...

26 of 26 people found the following review helpful:

4.0 out of 5 stars Depends on what you want, June 12, 2007

By 

wiredweird "wiredweird" (Earth, or somewhere nearby) - See all my reviews
(HALL OF FAME REVIEWER)    (TOP 500 REVIEWER)   

Amazon Verified Purchase

This review is from: Engineering a Compiler (Hardcover)

What it is: A great introduction to basic concepts in contemporary compilers.
What it's not: A handbook for someone thrown in at the deep end of commercial compiler development.

I can imagine a very good one-term course in compiler construction built around this text. After a brief introduction, it gets immediately into the classic topics of lexical scanning, parsing, and syntax analysis. These three chapters help any beginner understand the multiple levels of processing, from the character level, up through reorganizing grammars for practical parsing and table-driven techniques, to the lower levels of sematic analysis. This includes a very brief discussion of type systems and type inference - less than 20 pages, on a topic that whole books devote themselves to. These 200 pages typify what you'll see in the rest of the book: a lot of attention paid to lexical analysis, a problem largely eliminated by automated tools (lex and yacc being the best known), and thin mention of the harder problems that differ significantly across languages and applications of languages.

Chapter 5 addresses the critical issue of intermediate representation, the data structures that represent the program during analysis, optimization, and code generation. Chapter 6 is titled "The Procedure Abstraction." It deals with much more than its name suggests, including procedure activation records (generalizations of stack frames), parameter passing, stack management, symbol visibility and scoping, and scraps of symbol table organization - important stuff, but hard to understand as "procedure abstaction." The next chapter deals with "Code Shape," a grab-bag including value representations, arrays and strings, control constructs, and procedures (again). It also presents a very few pages, at the end, on object oriented language - hardly enough to scratch the surface, let alone build competence. And, for lack of a better place to stick them, I would have expected support for parallelism and exceptions to appear here, but this book seems to omit the topics altogether.

Code analysis and optimization appear in chapters 8-10. That includes a competent introduction to static single assignment notation, a staple of current compiler technology mentioned earlier, in the section on intermediate representation. This covers a range of basics, but omits all significant mention of arrays, the workhorses of performance computing. Chapters 11-13 introduce the basics of instruction selection, scheduling, and register allocation. Although it mentions some hardware effects, like out-of-order execution in superscalar architecture, discussion stays close the instruction sets of popular processors. As a result, it omits mention of SIMD, VLIW, DSP, and more exotic architectures, the ones most in need of good code generation. Compiler-specific support libraries, e.g. the kind that make up for lack of hardware divide instructions, should have appeared somewhere around here, but are oddly absent.

The authors present an adequate introduction for the beginner, someone who's still not sure what a hash table is (see appendix B). It introduces many basic topics, but doesn't go into a lot of depth in any of them. The student who finishes this book will understand most major issues of classical compiler construction. I just can't see a serious, working competence coming out of this text, though. I give it four stars as an academic introduction, but a lot less for anyone with immediate problems to solve.

-- wiredweird

30 of 32 people found the following review helpful:

4.0 out of 5 stars I'd rather call it "A guide for engineering a compiler", September 2, 2004

By 

H. Kim (Worcester, MA United States) - See all my reviews
(REAL NAME)   

This review is from: Engineering a Compiler (Hardcover)

This book deals with all the issues you will face while engineering a MODERN compiler. Each subject is rather a brief instroduction than a thorough discussion, but detailed enough to give readers a good introduction working as a good pointer when you need a more detailed information.

Also the author tries very hard to cover as much subjects as possible you have to deal with when you design a language and implment a compiler for it.

I'd use this book not as a thorough compiler algorithm bible but as a guide to follow when implementing my compiler.
By following each chapter in the book, at least you will know what problems you should slove. If the problem is simple enough, the solution is in the book. For more complicated problems, you gotta dig into the internet.

In my opinion, this book is the best compiler engineering guide ever I read.