Advanced Compiler Design and Implementation
- 1st Edition - August 1, 1997
- Imprint: Morgan Kaufmann
- Author: Steven Muchnick
- Language: English
- Hardback ISBN:9 7 8 - 1 - 5 5 8 6 0 - 3 2 0 - 2
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 4 9 8 7 1 - 3
From the Foreword by Susan L. Graham:This book takes on the challenges of contemporary languages and architectures, and prepares the reader for the new compiling problems th… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteFrom the Foreword by Susan L. Graham:
This book takes on the challenges of contemporary languages and
architectures, and prepares the reader for the new compiling problems that
will inevitably arise in the future.
The definitive book on advanced compiler design
This comprehensive, up-to-date work examines advanced issues in the design
and implementation of compilers for modern processors. Written for
professionals and graduate students, the book guides readers in designing
and implementing efficient structures for highly optimizing compilers for
real-world languages. Covering advanced issues in fundamental areas of
compiler design, this book discusses a wide array of possible code
optimizations, determining the relative importance of optimizations, and
selecting the most effective methods of implementation.
* Lays the foundation for understanding the major issues of advanced
compiler design
* Treats optimization in-depth
* Uses four case studies of commercial compiling suites to illustrate
different approaches to compiler structure, intermediate-code design, and
optimization—these include Sun Microsystems's compiler for SPARC, IBM's for
POWER and PowerPC, DEC's for Alpha, and Intel's for Pentium an related
processors
* Presents numerous clearly defined algorithms based on actual cases
* Introduces Informal Compiler Algorithm Notation (ICAN), a language devised
by the author to communicate algorithms effectively to people
Advanced Compiler Design and Implementation
by Steven Muchnick
Preface
1 Introduction to Advanced Topics
1.1 Review of Compiler Structure
1.2 Advanced Issues in Elementary Topics
1.3 The Importance of Code Optimization
1.4 Structure of Optimizing Compilers
1.5 Placement of Optimizations in Aggressive Optimizing Compilers
1.6 Reading Flow Among the Chapters
1.7 Related Topics Not Covered in This Text
1.8 Target Machines Used in Examples
1.9 Number Notations and Data Sizes
1.10 Wrap-Up
1.11 Further Reading
1.12 Exercises
2 Informal Compiler Algorithm Notation (ICAN)
2.1 Extended Backus-Naur Form Syntax Notation
2.2 Introduction to ICAN
2.3 A Quick Overview of ICAN
2.4 Whole Programs
2.5 Type Definitions
2.6 Declarations
2.7 Data Types and Expressions
2.8 Statements
2.9 Wrap-Up
2.10 Further Reading
2.11 Exercises
3 Symbol-Table Structure
3.1 Storage Classes, Visibility, and Lifetimes
3.2 Symbol Attributes and Symbol-Table Entries
3.3 Local Symbol-Table Management
3.4 Global Symbol-Table Structure
3.5 Storage Binding and Symbolic Registers
3.6 Approaches to Generating Loads and Stores
3.7 Wrap-Up
3.8 Further Reading
3.9 Exercises
4 Intermediate Representations
4.1 Issues in Designing an Intermediate Language
4.2 High-Level Intermediate Languages
4.3 Medium-Level Intermediate Languages
4.4 Low-Level Intermediate Languages
4.5 Multi-Level Intermediate Languages
4.6 Our Intermediate Languages: MIR, HIR, and LIR
4.7 Representing MIR, HIR, and LIR in ICAN
4.8 ICAN Naming of Data Structures and Routines that Manipulate Intermediate Code
4.9 Other Intermediate-Language Forms
4.10 Wrap-Up
4.11 Further Reading
4.12 Exercises
5 Run-Time Support
5.1 Data Representations and Instructions
5.2 Register Usage
5.3 The Local Stack Frame
5.4 The Run-Time Stack
5.5 Parameter-Passing Disciplines
5.6 Procedure Prologues, Epilogues, Calls, and Returns
5.7 Code Sharing and Position-Independent Code
5.8 Symbolic and Polymorphic Language Support
5.9 Wrap-Up
5.10 Further Reading
5.11 Exercises
6 Producing Code Generators Automatically
6.1 Introduction to Automatic Generation of Code Generators
6.2 A Syntax-Directed Technique
6.3 Introduction to Semantics-Directed Parsing
6.4 Tree Pattern Matching and Dynamic Programming
6.5 Wrap-Up
6.6 Further Reading
6.7 Exercises
7 Control-Flow Analysis
7.1 Approaches to Control-Flow Analysis
7.2 Depth-First Search, Preorder Traversal, Postorder Traversal, and Breadth-First Search
7.3 Dominators
7.4 Loops and Strongly Connected Components
7.5 Reducibility
7.6 Interval Analysis and Control Trees
7.7 Structural Analysis
7.8 Wrap-Up
7.9 Further Reading
7.10 Exercises
8 Data-Flow Analysis
8.1 An Example: Reaching Definitions
8.2 Basic Concepts: Lattices, Flow Functions, and Fixed Points
8.3 Taxonomy of Data-Flow Problems and Solution Methods
8.4 Iterative Data-Flow Analysis
8.5 Lattices of Flow Functions
8.6 Control-Tree-Based Data-Flow Analysis
8.7 Structural Analysis
8.8 Interval Analysis
8.9 Other Approaches
8.10 Du-Chains, Ud-Chains, and Webs
8.11 Static Single-Assignment (SSA) Form
8.12 Dealing with Arrays, Structures, and Pointers
8.13 Automating Construction of Data-Flow Analyzers
8.14 More Ambitious Analyses
8.15 Wrap-Up
8.16 Further Reading
8.17 Exercises
9 Dependence Analysis and Dependence Graphs
9.1 Dependence Relations
9.2 Basic-Block Dependence DAGs
9.3 Dependences in Loops
9.4 Dependence Testing
9.5 Program-Dependence Graphs
9.6 Dependences Between Dynamically Allocated Objects
9.7 Wrap-Up
9.8 Further Reading
9.9 Exercises
10 Alias Analysis
10.1 Aliases in Various Real Programming Languages
10.2 The Alias Gatherer
10.3 The Alias Propagator
10.4 Wrap-Up
10.5 Further Reading
10.6 Exercises
11 Introduction to Optimization
11.1 Global Optimizations Discussed in Chapters 12 Through 18
11.2 Flow Sensitivity and May vs. Must Information
11.3 Importance of Individual Optimizations
11.4 Order and Repetition of Optimizations
11.5 Further Reading
11.6 Exercises
12 Early Optimizations
12.1 Constant-Expression Evaluation (Constant Folding)
12.2 Scalar Replacement of Aggregates
12.3 Algebraic Simplifications and Reassociation
12.4 Value Numbering
12.5 Copy Propagation
12.6 Sparse Conditional Constant Propagation
12.7 Wrap-Up
12.8 Further Reading
12.9 Exercises
13 Redundancy Elimination
13.1 Common-Subexpression Elimination
13.2 Loop-Invariant Code Motion
13.3 Partial-Redundancy Elimination
13.4 Redundancy Elimination and Reassociation
13.5 Code Hoisting
13.6 Wrap-Up
13.7 Further Reading
13.8 Exercises
14 Loop Optimizations
14.1 Induction-Variable Optimizations
14.2 Unnecessary Bounds-Checking Elimination
14.3 Wrap-Up
14.4 Further Reading
14.5 Exercises
15 Procedure Optimizations
15.1 Tail-Call Optimization and Tail-Recursion Elimination
15.2 Procedure Integration
15.3 In-Line Expansion
15.4 Leaf-Routine Optimization and Shrink Wrapping
15.5 Wrap-Up
15.6 Further Reading
15.7 Exercises
16 Register Allocation
16.1 Register Allocation and Assignment
16.2 Local Methods
16.3 Graph Coloring
16.4 Priority-Based Graph Coloring
16.5 Other Approaches to Register Allocation
16.6 Wrap-Up
16.7 Further Reading
16.8 Exercises
17 Code Scheduling
17.1 Instruction Scheduling
17.2 Speculative Loads and Boosting
17.3 Speculative Scheduling
17.4 Software Pipelining
17.5 Trace Scheduling
17.6 Percolation Scheduling
17.7 Wrap-Up
17.8 Further Reading
17.9 Exercises
18 Control-Flow and Low-Level Optimizations
18.1 Unreachable-Code Elimination
18.2 Straightening
18.3 If Simplifications
18.4 Loop Simplifications
18.5 Loop Inversion
18.6 Unswitching
18.7 Branch Optimizations
18.8 Tail Merging or Cross Jumping
18.9 Conditional Moves
18.10 Dead-Code Elimination
18.11 Branch Prediction
18.12 Machine Idioms and Instruction Combining
18.13 Wrap-Up
18.14 Further Reading
18.15 Exercises
19 Interprocedural Analysis and Optimization
19.1 Interprocedural Control-Flow Analysis: The Call Graph
19.2 Interprocedural Data-Flow Analysis
19.3 Interprocedural Constant Propagation
19.4 Interprocedural Alias Analysis
19.5 Interprocedural Optimizations
19.6 Interprocedural Register Allocation
19.7 Aggregation of Global References
19.8 Other Issues in Interprocedural Program Management
19.9 Wrap-Up
19.10 Further Reading
19.11 Exercises
20 Optimization for the Memory Hierarchy
20.1 Impact of Data and Instruction Caches
20.2 Instruction-Cache Optimization
20.3 Scalar Replacement of Array Elements
20.4 Data-Cache Optimization
20.5 Scalar vs. Memory-Oriented Optimizations
20.6 Wrap-Up
20.7 Further Reading
20.8 Exercises
21 Case Studies of Compilers and Future Trends
21.1 the Sun Compilers for SPARC
21.2 The IBM XL Compilers for the POWER and PowerPC Architectures
21.3 Digital Equipment's Compilers for Alpha
21.4 The Intel Reference Compilers for the Intel 386 Architecture
21.5 Future Trends in Compiler Design and Implementation
21.6 Further Reading
A Guide to Assembly Languages Used in This Book
A.1 Sun SPARC Versions 8 and 9 Assembly Language
A.2 IBM POWER and PowerPC Assembly Language
A.3 DEC Alpha Assembly Language
A.4 Intel 386 Architecture Assembly Language
A.5 Hewlett-Packard's PA-RISC Assembly Language
B Representation of Sets, Sequences, Trees, DAGs, and Functions
B.1 Representation of Sets
B.2 Representation of Sequences
B.3 Representation of Trees and DAGs
B.4 Representation of Functions
B.5 Further Reading
C Software Resources
View Appendix C with live links to download sites
C.1 Finding and Accessing Software on the Internet
C.2 Machine Simulators
C.3 Compilers
C.4 Code-Generator Generators: BURG and IBURG
C.5 Profiling Tools
Bibliography
Indices
by Steven Muchnick
Preface
1 Introduction to Advanced Topics
1.1 Review of Compiler Structure
1.2 Advanced Issues in Elementary Topics
1.3 The Importance of Code Optimization
1.4 Structure of Optimizing Compilers
1.5 Placement of Optimizations in Aggressive Optimizing Compilers
1.6 Reading Flow Among the Chapters
1.7 Related Topics Not Covered in This Text
1.8 Target Machines Used in Examples
1.9 Number Notations and Data Sizes
1.10 Wrap-Up
1.11 Further Reading
1.12 Exercises
2 Informal Compiler Algorithm Notation (ICAN)
2.1 Extended Backus-Naur Form Syntax Notation
2.2 Introduction to ICAN
2.3 A Quick Overview of ICAN
2.4 Whole Programs
2.5 Type Definitions
2.6 Declarations
2.7 Data Types and Expressions
2.8 Statements
2.9 Wrap-Up
2.10 Further Reading
2.11 Exercises
3 Symbol-Table Structure
3.1 Storage Classes, Visibility, and Lifetimes
3.2 Symbol Attributes and Symbol-Table Entries
3.3 Local Symbol-Table Management
3.4 Global Symbol-Table Structure
3.5 Storage Binding and Symbolic Registers
3.6 Approaches to Generating Loads and Stores
3.7 Wrap-Up
3.8 Further Reading
3.9 Exercises
4 Intermediate Representations
4.1 Issues in Designing an Intermediate Language
4.2 High-Level Intermediate Languages
4.3 Medium-Level Intermediate Languages
4.4 Low-Level Intermediate Languages
4.5 Multi-Level Intermediate Languages
4.6 Our Intermediate Languages: MIR, HIR, and LIR
4.7 Representing MIR, HIR, and LIR in ICAN
4.8 ICAN Naming of Data Structures and Routines that Manipulate Intermediate Code
4.9 Other Intermediate-Language Forms
4.10 Wrap-Up
4.11 Further Reading
4.12 Exercises
5 Run-Time Support
5.1 Data Representations and Instructions
5.2 Register Usage
5.3 The Local Stack Frame
5.4 The Run-Time Stack
5.5 Parameter-Passing Disciplines
5.6 Procedure Prologues, Epilogues, Calls, and Returns
5.7 Code Sharing and Position-Independent Code
5.8 Symbolic and Polymorphic Language Support
5.9 Wrap-Up
5.10 Further Reading
5.11 Exercises
6 Producing Code Generators Automatically
6.1 Introduction to Automatic Generation of Code Generators
6.2 A Syntax-Directed Technique
6.3 Introduction to Semantics-Directed Parsing
6.4 Tree Pattern Matching and Dynamic Programming
6.5 Wrap-Up
6.6 Further Reading
6.7 Exercises
7 Control-Flow Analysis
7.1 Approaches to Control-Flow Analysis
7.2 Depth-First Search, Preorder Traversal, Postorder Traversal, and Breadth-First Search
7.3 Dominators
7.4 Loops and Strongly Connected Components
7.5 Reducibility
7.6 Interval Analysis and Control Trees
7.7 Structural Analysis
7.8 Wrap-Up
7.9 Further Reading
7.10 Exercises
8 Data-Flow Analysis
8.1 An Example: Reaching Definitions
8.2 Basic Concepts: Lattices, Flow Functions, and Fixed Points
8.3 Taxonomy of Data-Flow Problems and Solution Methods
8.4 Iterative Data-Flow Analysis
8.5 Lattices of Flow Functions
8.6 Control-Tree-Based Data-Flow Analysis
8.7 Structural Analysis
8.8 Interval Analysis
8.9 Other Approaches
8.10 Du-Chains, Ud-Chains, and Webs
8.11 Static Single-Assignment (SSA) Form
8.12 Dealing with Arrays, Structures, and Pointers
8.13 Automating Construction of Data-Flow Analyzers
8.14 More Ambitious Analyses
8.15 Wrap-Up
8.16 Further Reading
8.17 Exercises
9 Dependence Analysis and Dependence Graphs
9.1 Dependence Relations
9.2 Basic-Block Dependence DAGs
9.3 Dependences in Loops
9.4 Dependence Testing
9.5 Program-Dependence Graphs
9.6 Dependences Between Dynamically Allocated Objects
9.7 Wrap-Up
9.8 Further Reading
9.9 Exercises
10 Alias Analysis
10.1 Aliases in Various Real Programming Languages
10.2 The Alias Gatherer
10.3 The Alias Propagator
10.4 Wrap-Up
10.5 Further Reading
10.6 Exercises
11 Introduction to Optimization
11.1 Global Optimizations Discussed in Chapters 12 Through 18
11.2 Flow Sensitivity and May vs. Must Information
11.3 Importance of Individual Optimizations
11.4 Order and Repetition of Optimizations
11.5 Further Reading
11.6 Exercises
12 Early Optimizations
12.1 Constant-Expression Evaluation (Constant Folding)
12.2 Scalar Replacement of Aggregates
12.3 Algebraic Simplifications and Reassociation
12.4 Value Numbering
12.5 Copy Propagation
12.6 Sparse Conditional Constant Propagation
12.7 Wrap-Up
12.8 Further Reading
12.9 Exercises
13 Redundancy Elimination
13.1 Common-Subexpression Elimination
13.2 Loop-Invariant Code Motion
13.3 Partial-Redundancy Elimination
13.4 Redundancy Elimination and Reassociation
13.5 Code Hoisting
13.6 Wrap-Up
13.7 Further Reading
13.8 Exercises
14 Loop Optimizations
14.1 Induction-Variable Optimizations
14.2 Unnecessary Bounds-Checking Elimination
14.3 Wrap-Up
14.4 Further Reading
14.5 Exercises
15 Procedure Optimizations
15.1 Tail-Call Optimization and Tail-Recursion Elimination
15.2 Procedure Integration
15.3 In-Line Expansion
15.4 Leaf-Routine Optimization and Shrink Wrapping
15.5 Wrap-Up
15.6 Further Reading
15.7 Exercises
16 Register Allocation
16.1 Register Allocation and Assignment
16.2 Local Methods
16.3 Graph Coloring
16.4 Priority-Based Graph Coloring
16.5 Other Approaches to Register Allocation
16.6 Wrap-Up
16.7 Further Reading
16.8 Exercises
17 Code Scheduling
17.1 Instruction Scheduling
17.2 Speculative Loads and Boosting
17.3 Speculative Scheduling
17.4 Software Pipelining
17.5 Trace Scheduling
17.6 Percolation Scheduling
17.7 Wrap-Up
17.8 Further Reading
17.9 Exercises
18 Control-Flow and Low-Level Optimizations
18.1 Unreachable-Code Elimination
18.2 Straightening
18.3 If Simplifications
18.4 Loop Simplifications
18.5 Loop Inversion
18.6 Unswitching
18.7 Branch Optimizations
18.8 Tail Merging or Cross Jumping
18.9 Conditional Moves
18.10 Dead-Code Elimination
18.11 Branch Prediction
18.12 Machine Idioms and Instruction Combining
18.13 Wrap-Up
18.14 Further Reading
18.15 Exercises
19 Interprocedural Analysis and Optimization
19.1 Interprocedural Control-Flow Analysis: The Call Graph
19.2 Interprocedural Data-Flow Analysis
19.3 Interprocedural Constant Propagation
19.4 Interprocedural Alias Analysis
19.5 Interprocedural Optimizations
19.6 Interprocedural Register Allocation
19.7 Aggregation of Global References
19.8 Other Issues in Interprocedural Program Management
19.9 Wrap-Up
19.10 Further Reading
19.11 Exercises
20 Optimization for the Memory Hierarchy
20.1 Impact of Data and Instruction Caches
20.2 Instruction-Cache Optimization
20.3 Scalar Replacement of Array Elements
20.4 Data-Cache Optimization
20.5 Scalar vs. Memory-Oriented Optimizations
20.6 Wrap-Up
20.7 Further Reading
20.8 Exercises
21 Case Studies of Compilers and Future Trends
21.1 the Sun Compilers for SPARC
21.2 The IBM XL Compilers for the POWER and PowerPC Architectures
21.3 Digital Equipment's Compilers for Alpha
21.4 The Intel Reference Compilers for the Intel 386 Architecture
21.5 Future Trends in Compiler Design and Implementation
21.6 Further Reading
A Guide to Assembly Languages Used in This Book
A.1 Sun SPARC Versions 8 and 9 Assembly Language
A.2 IBM POWER and PowerPC Assembly Language
A.3 DEC Alpha Assembly Language
A.4 Intel 386 Architecture Assembly Language
A.5 Hewlett-Packard's PA-RISC Assembly Language
B Representation of Sets, Sequences, Trees, DAGs, and Functions
B.1 Representation of Sets
B.2 Representation of Sequences
B.3 Representation of Trees and DAGs
B.4 Representation of Functions
B.5 Further Reading
C Software Resources
View Appendix C with live links to download sites
C.1 Finding and Accessing Software on the Internet
C.2 Machine Simulators
C.3 Compilers
C.4 Code-Generator Generators: BURG and IBURG
C.5 Profiling Tools
Bibliography
Indices
- Edition: 1
- Published: August 1, 1997
- Imprint: Morgan Kaufmann
- Language: English
- Hardback ISBN: 9781558603202
- eBook ISBN: 9780080498713
SM
Steven Muchnick
After an early career as a professor of computer science, Steven Muchnick applied his knowledge of compilers as a vital member of the teams that developed two computer architectures, PA-RISC at Hewlett-Packard and SPARC at Sun Microsystems. Upon completion of the initial work on each architecture, he served as the leader of the advanced compiler design and implementation groups for these systems.