Engineering a Compiler

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.

CHAPTER 1 Overview of Compilation 1.1 Introduction 1.2 Compiler Structure 1.3 Overview of Translation 1.3.1 The Front End 1.3.2 The Optimizer 1.3.3 The Back End 1.4 Summary and Perspective CHAPTER 2 Scanners 2.1 Introduction 2.2 Recognizing Words 2.2.1 A Formalism for Recognizers 2.2.2 Recognizing More Complex Words 2.3 Regular Expressions 2.3.1 Formalizing the Notation 2.3.2 Examples 2.3.3 Closure Properties of REs 2.4 From Regular Expression to Scanner 2.4.1 Nondeterministic Finite Automata 2.4.2 Regular Expression to NFA: Thompson’s Construction 2.4.3 NFA to DFA: The Subset Construction 2.4.4 DFA to Minimal DFA: Hopcroft’s Algorithm 2.4.5 Using a DFA as a Recognizer 2.5 Implementing Scanners 2.5.1 Table-Driven Scanners 2.5.2 Direct-Coded Scanners 2.5.3 Hand-coded Scanners 2.5.4 Handling Keywords 2.6 Advanced Topics 2.6.1 DFA to Regular Expression 2.6.2 Another Approach to DFA Minimization: Brzozowski’s Algorithm 2.6.3 Closure-free Regular Expressions 2.7 Chapter Summary and Perspective CHAPTER 3 Parsers 3.1 Introduction 3.2 Expressing Syntax 3.2.1 Why Not Regular Expressions? 3.2.2 Context-Free Grammars 3.2.3 More Complex Examples 3.2.4 Encoding Meaning into Structure 3.2.5 Discovering a Derivation for an Input String 3.3 Top-Down Parsing 3.3.1 Transforming a Grammar for Top-Down Parsing 3.3.2 Top-Down Recursive-Descent Parsers 3.3.3 Table-Driven LL(1) Parsers 3.4 Bottom-Up Parsing 3.4.1 The LR(1) Parsing Algorithm 3.4.2 Building LR(1) Tables 3.4.3 Errors in the Table Construction 3.5 Practical Issues 3.5.1 Error Recovery 3.5.2 Unary Operators 3.5.3 Handling Context-Sensitive Ambiguity 3.5.4 Left versus Right Recursion 3.6 Advanced Topics 1 3.6.1 Optimizing a Grammar 3.6.2 Reducing the Size of LR(1) Tables 3.7 Summary and Perspective CHAPTER 4 Context-Sensitive Analysis 4.1 Introduction 4.2 An Introduction to Type Systems 4.2.1 The Purpose of Type Systems 4.2.2 Components of a Type System 4.3 The Attribute-Grammar Framework 4.3.1 Evaluation Methods 4.3.2 Circularity 4.3.3 Extended Examples 4.3.4 Problems with the Attribute-Grammar Approach 4.4 Ad Hoc Syntax-Directed Translation 4.4.1 Implementing Ad Hoc Syntax-Directed Translation 4.4.2 Examples 4.5 Advanced Topics 4.5.1 Harder Problems in Type Inference 4.5.2 Changing Associativity 4.6 Summary and Perspective CHAPTER 5 Intermediate Representations 5.1 Introduction 5.1.1 A Taxonomy of Intermediate Representations 5.2 Graphical IRs 5.2.1 Syntax-Related Trees 5.2.2 Graphs 5.2.3 Review Questions 5.3 Linear IRs 5.3.1 Stack-Machine Code 5.3.2 Three-Address Code 5.3.3 Representing Linear Codes 5.3.4 Building a Control-flow Graph from a Linear Code 5.4 Mapping Values to Names 5.4.1 Naming Temporary Values 5.4.2 Static Single-Assignment Form 5.4.3 Memory Models 5.5 Symbol Tables 5.5.1 Hash Tables 5.5.2 Building a Symbol Table 5.5.3 Handling Nested Scopes 5.5.4 The Many Uses for Symbol Tables 5.5.5 Other Uses for Symbol Table Technology 5.6 Summary and Perspective CHAPTER 6 The Procedure Abstraction 6.1 Introduction 6.2 Procedure Calls 6.3 Name Spaces 2 6.3.1 Name Spaces of Algol-like Languages 6.3.2 Runtime Structures to Support Algol-like Languages 6.3.3 Name Spaces of Object-Oriented Languages 6.3.4 Runtime Structures to Support Object-Oriented Languages 6.4 Communicating Values Between Procedures 6.4.1 Passing Parameters 6.4.2 Returning Values 6.4.3 Establishing Addressability 6.5 Standardized Linkages 6.6 Advanced Topics 6.6.1 Explicit Heap Management 6.6.2 Implicit Deallocation 6.7 Summary and Perspective CHAPTER 7 Code Shape 7.1 Introduction 7.2 Assigning Storage Locations 7.2.1 Placing Runtime Data Structures 7.2.2 Layout for Data Areas 7.2.3 Keeping Values in Registers 7.3 Arithmetic Operators 7.3.1 Reducing Demand for Registers 7.3.2 Accessing Parameter Values 7.3.3 Function Calls in an Expression 7.3.4 Other Arithmetic Operators 7.3.5 Mixed-Type Expressions 7.3.6 Assignment as an Operator 7.4 Boolean and Relational Operators 7.4.1 Representations 7.4.2 Hardware Support for Relational Operations 7.5 Storing and Accessing Arrays 7.5.1 Referencing a Vector Element 7.5.2 Array Storage Layout 7.5.3 Referencing an Array Element 7.5.4 Range Checking 7.6 Character Strings 7.6.1 String Representations 7.6.2 String Assignment 7.6.3 String Concatenation 7.6.4 String Length 7.7 Structure References 7.7.1 Understanding Structure Layouts 7.7.2 Arrays of Structures 7.7.3 Unions and Runtime Tags 7.7.4 Pointers and Anonymous Values 7.8 Control-Flow Constructs 7.8.1 Conditional Execution 7.8.2 Loops and Iteration 7.8.3 Case Statements 7.9 Procedure Calls 7.9.1 Evaluating Actual Parameters 7.9.2 Saving and Restoring Registers 7.10 Summary and Perspective CHAPTER 8 Introduction to Optimization 8.1 Introduction 8.2 Background 8.2.1 Examples 8.2.2 Considerations for Optimization 8.2.3 Opportunities for Optimization 8.3 Scope of Optimization 8.4 Local Optimization 8.4.1 Local Value Numbering 8.4.2 Tree-height Balancing 8.5 Regional Optimization 8.5.1 Superlocal Value Numbering 8.5.2 Loop Unrolling 8.6 Global Optimization 8.6.1 Finding Uninitialized Variables with Live Information 8.6.2 Global Code Placement 8.7 Interprocedural Optimization 8.7.1 Inline Substitution 8.7.2 Procedure Placement 8.7.3 Compiler Organization for Interprocedural Optimization 8.8 Summary and Perspective CHAPTER 9 Data-Flow Analysis 9.1 Introduction 9.2 Iterative Data-Flow Analysis 9.2.1 Dominance 9.2.2 Live Variable Analysis 9.2.3 Limitations on Data-Flow Analysis 9.2.4 Other Data-Flow Problems 9.3 Static Single-Assignment Form 9.3.1 A Simple Method for Building SSA Form 9.3.2 Dominance Frontiers 9.3.3 Placing f-Functions 9.3.4 Renaming 9.3.5 Translation Out of SSA Form 9.3.6 Using Static Single Assignment Form 9.4 Interprocedural Analysis 9.4.1 Call Graph Construction 9.4.2 Interprocedural Constant Propagation 9.5 Advanced Topics 9.5.1 Structural Data-Flow Algorithms and Reducibility 9.5.2 Speeding up the Iterative Dominance Framework 9.6 Summary and Perspective CHAPTER 10 Scalar Optimizations 10.1 Introduction 10.2 Eliminating Useless and Unreachable Code 10.2.1 Eliminating Useless Code 10.2.2 Eliminating Useless Control Flow 10.2.3 Eliminating Unreachable Code 10.3 Code Motion 10.3.1 Lazy Code Motion 10.3.2 Code Hoisting 10.4 Specialization 10.4.1 Tail Call Optimization 10.4.2 Leaf Call Optimization 10.4.3 Parameter Promotion 10.5 Redundancy Elimination 10.5.1 Value Identity versus Name Identity 10.5.2 Dominator-based Value Numbering 10.6 Enabling Other Transformations 10.6.1 Superblock Cloning 10.6.2 Procedure Cloning 10.6.3 Loop Unswitching 10.6.4 Renaming 10.7 Advanced Topics 10.7.1 Combining Optimizations 10.7.2 Strength Reduction 10.7.3 Choosing an Optimization Sequence 10.8 Summary and Perspective CHAPTER 11 Instruction Selection 11.1 Introduction 11.2 Code Generation 11.3 Extending the Simple Tree-Walk Scheme 11.4 Instruction Selection via Tree-Pattern Matching 11.4.1 Rewrite Rules 11.4.2 Finding a Tiling 11.4.3 Tools 11.5 Instruction Selection via Peephole Optimization 11.5.1 Peephole Optimization 11.5.2 Peephole Transformers 11.6 Advanced Topics 11.6.1 Learning Peephole Patterns 11.6.2 Generating Instruction Sequences 11.7 Summary and Perspective CHAPTER 12 Instruction Scheduling 12.1 Introduction 12.2 The Instruction-Scheduling Problem 12.2.1 Other Measures of Schedule Quality 12.2.2 What Makes Scheduling Hard? 12.3 Local List Scheduling 12.3.1 The Algorithm 12.3.2 Scheduling Operations with Variable Delays 12.3.3 Extending the Algorithm 12.3.4 Tie Breaking in the List Scheduling Algorithm 12.3.5 Forward versus Backward List Scheduling 12.3.6 Improving the Efficiency of List Scheduling 12.4 Regional Scheduling 12.4.1 Scheduling Extended Basic Blocks 12.4.2 Trace Scheduling 12.4.3 Cloning for Context 12.5 Advanced Topics 12.5.1 The Strategy of Software Pipelining 12.5.2 An Algorithm for Software Pipelining 12.6 Summary and Perspective CHAPTER 13 Register Allocation 13.1 Introduction 13.2 Background Issues 13.2.1 Memory versus Registers 13.2.2 Allocation versus Assignment 13.2.3 Register Classes 13.3 Local Register Allocation and Assignment 13.3.1 Top-Down Local Register Allocation 13.3.2 Bottom-Up Local Register Allocation 13.3.3 Moving Beyond Single Blocks 13.4 Global Register Allocation and Assignment 13.4.1 Discovering Global Live Ranges 13.4.2 Estimating Global Spill Costs 13.4.3 Interferences and the Interference Graph 13.4.4 Top-Down Coloring 13.4.5 Bottom-Up Coloring 13.4.6 Coalescing Copies to Reduce Degree 13.4.7 Comparing Top-Down and Bottom-Up Global Allocators 13.4.8 Encoding Machine Constraints in the Interference Graph 13.5 Advanced Topics 13.5.1 Variations on Graph-Coloring Allocation 13.5.2 Global Register Allocation over SSA Form 13.6 Summary and Perspective CHAPTER A ILOC A.1 Introduction A.2 Naming Conventions A.3 Individual Operations A.3.1 Arithmetic A.3.2 Shifts A.3.3 Memory Operations A.3.4 Register-to-Register Copy Operations A.4 Control-Flow Operations A.4.1 Alternate Comparison and Branch Syntax A.4.2 Jumps A.5 Representing SSA Form CHAPTER B Data Structures B.1 Introduction B.2 Representing Sets B.2.1 Representing Sets as Ordered Lists B.2.2 Representing Sets as Bit Vectors B.2.3 Representing Sparse Sets B.3 Implementing Intermediate Representations B.3.1 Graphical Intermediate Representations B.3.2 Linear Intermediate Forms B.4 Implementing Hash Tables B.4.1 Choosing a Hash Function B.4.2 Open Hashing B.4.3 Open Addressing B.4.4 Storing Symbol Records B.4.5 Adding Nested Lexical Scopes B.5 A Flexible Symbol-Table Design