Advanced Compiler Design and Implementation

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