Engineering a Compiler

Front Cover
Engineering a Compiler
Copyright
Contents
About the Authors
About the Cover
Preface
Changes in the Third Edition
Organization
Approach
Philosophy
A Word About Programming Exercises
Additional Materials
Acknowledgments
1 Overview of Compilation
1.1 Introduction
1.2 Compiler Structure
1.3 Overview of Translation
1.3.1 The Front End
Checking Syntax
Intermediate Representations
1.3.2 The Optimizer
Analysis
Transformation
1.3.3 The Back End
Instruction Selection
Register Allocation
Instruction Scheduling
Interactions Among Code-Generation Components
1.4 Engineering
1.5 Summary and Perspective
Chapter Notes
Exercises
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 of Regular Expressions
2.3.3 Closure Properties of REs
2.4 From Regular Expression to Scanner
2.4.1 Nondeterministic Finite Automata
Equivalence of NFAs and DFAs
2.4.2 RE to NFA: Thompson's Construction
2.4.3 NFA to DFA: The Subset Construction
Example
Fixed-Point Computations
2.4.4 DFA to Minimal DFA
Examples
2.4.5 Using a DFA as a Scanner
Model of Execution
Finding Syntactic Categories
The Role of Whitespace
FORTRAN 66
PYTHON
2.5 Implementing Scanners
2.5.1 Table-Driven Scanners
Avoiding Excess Roll Back
2.5.2 Direct-Coded Scanners
Reducing the Overhead of Table Lookup
Replacing the Table-Driven Scanner's While Loop
2.5.3 Hand-Coded Scanners
2.5.4 Practical Implementation Issues
Buffering the Input Stream
Compressing the Transition Table
2.6 Advanced Topics
2.6.1 DFA to Regular Expression
2.6.2 Closure-Free Regular Expressions
2.6.3 An Alternative DFA Minimization Algorithm
2.7 Summary and Perspective
Chapter Notes
Exercises
3 Parsers
3.1 Introduction
3.2 Expressing Syntax
3.2.1 Why Not Use 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
A Top-Down Parser with Oracular Choice
Eliminating Left Recursion
Example
Parsing with Epsilon Productions
Backtrack-Free Parsing
Left-Factoring to Eliminate Backtracking
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
Handle Finding
Parsing an Erroneous Input String
Using LR Parsers
Using More Lookahead
3.4.2 Building LR(1) Tables
LR(1) Items
Constructing the Canonical Collection
Computing Closure
Computing Goto
The Algorithm
Building the Canonical Collection
Filling in the Tables
Handle Finding, Revisited
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.6 Advanced Topics
3.6.1 Optimizing a Grammar
3.6.2 Reducing the Size of LR(1) Tables
Shrinking the Grammar
Combining Rows or Columns
Directly Encoding the Table
Using Other Construction Algorithms
3.7 Summary and Perspective
Chapter Notes
Exercises
4 Intermediate Representations
4.1 Introduction
4.2 An IR Taxonomy
4.3 Graphical IRs
4.3.1 Syntax-Related Trees
Parse Trees
Abstract Syntax Trees
Directed Acyclic Graphs
4.3.2 Graphs
Control-Flow Graph
Block Length
Dependence Graph
Call Graph
4.4 Linear IRs
4.4.1 Stack-Machine Code
4.4.2 Three-Address Code
4.4.3 Representing Linear Codes
4.4.4 Building the CFG from Linear Code
Complications in CFG Construction
4.5 Symbol Tables
4.5.1 Name Resolution
Lexical Scopes
Inheritance Hierarchies
Hierarchical Tables
Other Scopes
4.5.2 Table Implementation
Implementing the Mapping
Linear List
Tree
Hash Map
Static Map
Implementing the Repository
4.6 Name Spaces
4.6.1 Name Spaces in the IR
4.6.2 Static Single-Assignment Form
4.7 Placement of Values in Memory
4.7.1 Memory Models
4.7.2 Keeping Values in Registers
4.7.3 Assigning Values to Data Areas
4.8 Summary and Perspective
Chapter Notes
Exercises
5 Syntax-Driven Translation
5.1 Introduction
5.2 Background
5.3 Syntax-Driven Translation
5.3.1 A First Example
5.3.2 Translating Expressions
Implementation in an LR(1) Parser
Handling Nonlocal Computation
Form of the Grammar
Tailoring Expressions to Context
5.3.3 Translating Control-Flow Statements
5.4 Modeling the Naming Environment
5.4.1 Lexical Hierarchies
5.4.2 Inheritance Hierarchies
5.4.3 Visibility
5.4.4 Performing Compile-Time Name Resolution
5.5 Type Information
5.5.1 Uses for Types in Translation
5.5.2 Components of a Type System
Base Types
Compound and Constructed Types
Arrays
Strings
Enumerated Types
Structures and Variants
Objects and Classes
Type Equivalence
5.5.3 Type Inference for Expressions
Interprocedural Aspects of Type Inference
5.6 Storage Layout
5.6.1 Storage Classes and Data Areas
5.6.2 Layout Within a Virtual Address Space
5.6.3 Storage Assignment
5.6.4 Fitting Storage Assignment into Translation
5.6.5 Alignment Restrictions and Padding
5.7 Advanced Topics
5.7.1 Grammar Structure and Associativity
5.7.2 Harder Problems in Type Inference
Type-Consistent Uses and Constant Function Types
Type-Consistent Uses and Unknown Function Types
Dynamic Changes in Type
5.7.3 Relative Offsets and Cache Performance
5.8 Summary and Perspective
Chapter Notes
Exercises
6 Implementing Procedures
6.1 Introduction
6.2 Background
6.3 Runtime Support for Naming
6.3.1 Runtime Support for Algol-Like Languages
Local Storage
Reserving Space for Local Data
Initializing Variables
Space for Saved Register Values
Allocating Activation Records
Stack Allocation of Activation Records
Heap Allocation of Activation Records
Static Allocation of Activation Records
Coalescing Activation Records
6.3.2 Runtime Support for Object-Oriented Languages
6.4 Passing Values Between Procedures
6.4.1 Passing Parameters
Call by Value
Call by Reference
Space for Parameters
6.4.2 Returning Values
6.4.3 Establishing Addressability for Nonlocal Variables
Variables with Static Base Addresses
Local Variables of the Current Procedure
Local Variables of Other Procedures
Access Links
Global Display
6.5 Standardized Linkages
6.6 Advanced Topics
6.6.1 Explicit Heap Management
First-Fit Allocation
Multipool Allocators
Debugging Help
6.6.2 Implicit Deallocation
Reference Counting
Batch Collectors
Identifying Live Data
Mark-Sweep Collectors
Copying Collectors
Comparing the Techniques
6.7 Summary and Perspective
Chapter Notes
Exercises
7 Code Shape
7.1 Introduction
7.2 Arithmetic Operators
7.2.1 Function Calls in an Expression
7.2.2 Mixed-Type Expressions
7.2.3 Reducing Demand for Registers
7.3 Access Methods for Values
7.3.1 Access Methods for Scalar Variables
Variables Stored in a Register
Variables Stored in Memory
Local Variables
Local Variables of Surrounding Scopes
Static and Global Variables
Variables Passed as Parameters
Variables Stored in the Heap
7.3.2 Access Methods for Aggregates
Structure Elements
Object Members
Vectors
Strings
Multidimensional Arrays
Accessing Array-Valued Parameters
7.3.3 Range Checks
7.4 Boolean and Relational Operators
7.4.1 Hardware Support for Relational Expressions
Short-Circuit Evaluation
7.4.2 Variations in Hardware Support
Conditional Move Operations
Predicated Execution
Condition Codes
7.5 Control-Flow Constructs
7.5.1 Conditional Execution
7.5.2 Loops and Iteration
For Loops
FORTRAN's DO Loop
While Loops
Until Loops
Expressing Iteration as Tail Recursion
Break Statements
7.5.3 Case Statements
Linear Search
Direct Address Computation
Binary Search
7.6 Operations on Strings
7.6.1 String Length
7.6.2 String Assignment
7.6.3 String Concatenation
7.6.4 Optimization of String Operations
7.7 Procedure Calls
7.7.1 Evaluating Actual Parameters
7.7.2 Saving and Restoring Registers
7.8 Summary and Perspective
Chapter Notes
Exercises
8 Introduction to Optimization
8.1 Introduction
8.2 Background
8.2.1 Examples
Improving an Array-Address Calculation
Improving a Loop Nest in LINPACK
8.2.2 Considerations for Optimization
Safety
Profitability
Risk
8.2.3 Opportunities for Optimization
8.3 Scope of Optimization
8.4 Local Optimization
8.4.1 Local Value Numbering
The Algorithm
Extending the Algorithm
The Role of Naming
The Impact of Indirect Assignments
8.4.2 Tree-Height Balancing
Candidate Trees
High-Level Sketch of the Algorithm
Phase 1: Finding Candidate Trees
Phase 2: Rebuilding the Block in Balanced Form
A Larger Example
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 Sets
Defining the Data-Flow Problem
Solving the Data-Flow Problem
Gathering Initial Information
Solving the LiveOut Equations
Finding Uninitialized Variables
Other Uses for Live Variables
8.6.2 Global Code Placement
Obtaining Profile Data
Constructing Chains as Hot Paths in the CFG
Performing Code Layout
A Final Example
8.7 Interprocedural Optimization
8.7.1 Inline Substitution
The Transformation
The Decision Procedure
8.7.2 Procedure Placement
Example
8.7.3 Pragmatics of Interprocedural Optimization
8.8 Summary and Perspective
Chapter Notes
Exercises
9 Data-Flow Analysis
9.1 Introduction
9.2 Iterative Data-Flow Analysis
9.2.1 Dominance
Termination
Correctness
Efficiency
9.2.2 Live-Variable Analysis
Termination
Correctness
Efficiency
9.2.3 Limitations on Data-Flow Analysis
9.2.4 Other Data-Flow Problems
Available Expressions
Reaching Definitions
Anticipable Expressions
Interprocedural Summary Problems
9.3 Static Single-Assignment Form
9.3.1 A Naive Method for Building SSA Form
9.3.2 Dominance Frontiers
Dominator Trees
Computing Dominance Frontiers
9.3.3 Placing ϕ-Functions
Example
Efficiency Improvements
9.3.4 Renaming
Example
A Final Improvement
9.3.5 Translation out of SSA Form
The Naive Translation
Problems with the Naive Translation
The Lost-Copy Problem
The Swap Problem
A Unified Approach to Out-of-SSA Translation
Phase One
Phase Two
Phase Three
9.3.6 Using SSA Form
9.4 Interprocedural Analysis
9.4.1 Call-Graph Construction
9.4.2 Interprocedural Constant Propagation
The Algorithm
Jump Function Implementation
Extending the Algorithm
9.5 Advanced Topics
9.5.1 Structural Data-Flow Analysis and Reducibility
9.5.2 Speeding up the Iterative Dominance Framework
9.6 Summary and Perspective
Chapter Notes
Exercises
10 Scalar Optimization
10.1 Introduction
10.2 Dead Code Elimination
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
Subtleties in Evaluating and Rewriting Operations
Effectiveness
10.7.2 Strength Reduction
Linear-Function Test Replacement
10.7.3 Choosing an Optimization Sequence
10.8 Summary and Perspective
Chapter Notes
Exercises
11 Instruction Selection
11.1 Introduction
11.2 Background
11.2.1 The Impact of ISA Design on Selection
Duplicate Implementations
Address Modes
Level of Abstraction
Register Use
Costs
11.2.2 Motivating Example
11.2.3 Ad-Hoc Matching
11.3 Selection via Peephole Optimization
11.3.1 Peephole Optimization
11.3.2 The Simplifier
Recognizing Dead Values
Physical Versus Logical Windows
11.3.3 The Matcher
11.4 Selection via Tree-Pattern Matching
11.4.1 Representing Trees
11.4.2 Rewrite Rules
11.4.3 Computing Tilings
11.4.4 Tools
11.5 Advanced Topics
11.5.1 Learning Peephole Patterns
11.5.2 Generating Instruction Sequences
11.6 Summary and Perspective
Chapter Notes
Exercises
12 Instruction Scheduling
12.1 Introduction
12.2 Background
12.2.1 Architectural Features That Affect Performance
12.2.2 The Instruction Scheduling Problem
Schedule Quality
What Makes Scheduling Hard?
12.3 Local Scheduling
12.3.1 The Algorithm
12.3.2 Renaming
12.3.3 Building the Dependence Graph
12.3.4 Computing Priorities
12.3.5 List Scheduling
Scheduling Operations with Variable Delays
12.3.6 Forward Versus Backward List Scheduling
12.4 Regional Scheduling
12.4.1 Superlocal Scheduling
12.4.2 Trace Scheduling
Trace Construction
Examples
Scheduling
12.4.3 Cloning for Context
12.5 Advanced Topics
12.5.1 The Strategy Behind Software Pipelining
12.5.2 An Algorithm for Software Pipelining
Estimating Kernel Size
Scheduling the Kernel
Generating Prolog and Epilog Code
12.5.3 A Final Example
12.6 Summary and Perspective
Chapter Notes
Exercises
13 Register Allocation
13.1 Introduction
13.2 Background
13.2.1 A Name Space for Allocation: Live Ranges
13.2.2 Interference
13.2.3 Spill Code
13.2.4 Register Classes
13.3 Local Register Allocation
13.3.1 Renaming in the Local Allocator
13.3.2 Allocation and Assignment
13.4 Global Allocation via Coloring
13.4.1 Find Global Live Ranges
13.4.2 Build an Interference Graph
13.4.3 Coalesce Copy Operations
13.4.4 Estimate Global Spill Costs
Accounting for Execution Frequencies
Negative Spill Costs
Infinite Spill Costs
13.4.5 Color the Graph
Why Does This Work?
13.4.6 Insert Spill and Restore Code
13.4.7 Handling Overlapping Register Classes
Describing Register Classes
Coloring with Overlapping Classes
Coloring
Assignment
Coalescing
Coloring with Disjoint Classes
Forcing Specific Register Placement
13.5 Advanced Topics
13.5.1 Variations on Coalescing
Conservative and Iterated Coalescing
Biased Coloring
Iterated Coalescing
13.5.2 Variations on Spilling
Spilling Partial Live Ranges
Clean Spilling
Rematerialization
Live-Range Splitting
Implementing Splitting
Promotion of Ambiguous Values
13.5.3 Other Forms of Live Ranges
Allocation Based on SSA Names
Allocation Based on Linear Intervals
Allocation Based on Hierarchical Coloring
13.6 Summary and Perspective
Chapter Notes
Exercises
14 Runtime Optimization
14.1 Introduction
14.2 Background
14.2.1 Execution Model
14.2.2 Compilation Triggers
14.2.3 Granularity of Optimization
14.2.4 Sources of Improvement
14.2.5 Building a Runtime Optimizer
14.3 Hot-Trace Optimization
14.3.1 Flow of Execution
14.3.2 Linking Traces
14.4 Hot-Method Optimization
14.4.1 Hot-Methods in a Mixed-Mode Environment
14.4.2 Hot-Methods in a Native-Code Environment
14.5 Advanced Topics
14.5.1 Levels of Optimization
14.5.2 On-Stack Replacement
14.5.3 Code Cache Management
14.5.4 Managing Changes to the Source Code
14.6 Summary and Perspective
Chapter Notes
Exercises
A ILOC
A.1 Introduction
A.2 Naming Conventions
A.3 Computational Operations
A.4 Data Movement Operations
A.5 Control-Flow Operations
A.6 Opcode Summary Tables
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.2.4 The Role of Hash Tables
B.3 IR Implementation
B.3.1 Graphical Intermediate Representations
Representing Trees
Mapping Arbitrary Trees to Binary Trees
Representing Arbitrary Graphs
B.3.2 Linear Intermediate Forms
Implementing Operations
Variant Node Sizes
B.4 Implementing Hash Tables
B.4.1 Choosing a Hash Function
Multiplicative Hash Functions
Universal Hash Functions
B.4.2 Open Hashing
B.4.3 Open Addressing
B.4.4 Storing Symbol Records
B.5 A Flexible Symbol-Table Design
Appendix Notes
Bibliography
Index
Back Cover