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.
Author(s): Keith Cooper, Linda Torczon
Edition: 2
Publisher: Elsevier Science & Technology
Year: 2011
Language: English
Pages: 825
Front Cover
About the Authors
Engineering a Compiler
Copyright
Dedication
About the Cover
Table of Contents
Preface
Chapter 1. Overview of Compilation
1.1 Introduction
1.2 Compiler Structure
1.3 Overview of Translation
1.4 Summary and Perspective
Chapter Notes
Exercises
Chapter 2. Scanners
2.1 Introduction
2.2 Recognizing Words
2.3 Regular Expressions
2.4 From Regular Expression to Scanner
2.5 Implementing Scanners
2.6 Advanced Topics
2.7 Chapter Summary and Perspective
Chapter Notes
Exercises
Chapter 3. Parsers
3.1 Introduction
3.2 Expressing Syntax
3.3 Top-Down Parsing
3.4 Bottom-Up Parsing
3.5 Practical Issues
3.6 Advanced Topics
3.7 Summary and Perspective
Chapter Notes
Exercises
Chapter 4. Context-Sensitive Analysis
4.1 Introduction
4.2 An Introduction to Type Systems
4.3 The Attribute-Grammar Framework
4.4 Ad Hoc Syntax-Directed Translation
4.5 Advanced Topics
4.6 Summary and Perspective
Chapter Notes
Exercises
Chapter 5. Intermediate Representations
5.1 Introduction
5.2 Graphical IRs
5.3 Linear IRs
5.4 Mapping Values to Names
5.5 Symbol Tables
5.6 Summary and Perspective
Chapter Notes
Exercises
Chapter 6. The Procedure Abstraction
6.1 Introduction
6.2 Procedure Calls
6.3 Name Spaces
6.4 Communicating Values Between Procedures
6.5 Standardized Linkages
6.6 Advanced Topics
6.7 Summary and Perspective
Chapter Notes
Exercises
Chapter 7. Code Shape
7.1 Introduction
7.2 Assigning Storage Locations
7.3 Arithmetic Operators
7.4 Boolean and Relational Operators
7.5 Storing and Accessing Arrays
7.6 Character Strings
7.7 Structure References
7.8 Control-Flow Constructs
7.9 Procedure Calls
7.10 Summary and Perspective
Chapter Notes
Exercises
Chapter 8. Introduction to Optimization
8.1 Introduction
8.2 Background
8.3 Scope of Optimization
8.4 Local Optimization
8.5 Regional Optimization
8.6 Global Optimization
8.7 Interprocedural Optimization
8.8 Summary and Perspective
Chapter Notes
Exercises
Chapter 9. Data-Flow Analysis
9.1 Introduction
9.2 Iterative Data-Flow Analysis
9.3 Static Single-Assignment Form
9.4 Interprocedural Analysis
9.5 Advanced Topics
9.6 Summary and Perspective
Chapter Notes
Exercises
Chapter 10. Scalar Optimizations
10.1 Introduction
10.2 Eliminating Useless and Unreachable Code
10.3 Code Motion
10.4 Specialization
10.5 Redundancy Elimination
10.6 Enabling Other Transformations
10.7 Advanced Topics
10.8 Summary and Perspective
Chapter Notes
Exercises
Chapter 11. Instruction Selection
11.1 Introduction
11.2 Code Generation
11.3 Extending the Simple Treewalk Scheme
11.4 Instruction Selection via Tree-Pattern Matching
11.5 Instruction Selection via Peephole Optimization
11.6 Advanced Topics
11.7 Summary and Perspective
Chapter Notes
Exercises
Chapter 12. Instruction Scheduling
12.1 Introduction
12.2 The Instruction-Scheduling Problem
12.3 Local List Scheduling
12.4 Regional Scheduling
12.5 Advanced Topics
12.6 Summary and Perspective
Chapter Notes
Exercises
Chapter 13. Register Allocation
13.1 Introduction
13.2 Background Issues
13.3 Local Register Allocation and Assignment
13.4 Global Register Allocation and Assignment
13.5 Advanced Topics
13.6 Summary and Perspective
Chapter Notes
Exercises
Appendix A. ILOC
A.1 Introduction
A.2 Naming Conventions
A.3 Individual Operations
A.4 Control-Flow Operations
A.5 Representing SSA Form
Appendix B. Data Structures
B.1 Introduction
B.2 Representing Sets
B.3 Implementing Intermediate Representations
B.4 Implementing Hash Tables
B.5 A Flexible Symbol-Table Design
Appendix Notes
Bibliography
Index
