Engineering a Compiler

by Cooper; Torczon

• ISBN13: 9781558606982
• ISBN10: 155860698X
• eBook ISBN(s): 9780080472676, 9781558606982
• Additional ISBN(s): 9780120884780
• Format: Hardcover
• Copyright: 2003-10-27
• Publisher: Elsevier Science
• More Book Details
• Purchase Benefits

Summary

Today's compiler writer must choose a path through a design space that is filled with diverse alternatives. "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.

Table of Contents

About the Authors	iv
About the Cover	viii
Preface	xxi
CHAPTER 1 Overview of Compilation	1	(26)
1.1 Introduction	1	(2)
1.2 Why Study Compiler Construction?	3	(1)
1.3 The Fundamental Principles of Compilation	4	(1)
1.4 Compiler Structure	5	(3)
1.5 High-Level View of Translation	8	(15)
1.5.1 Understanding the Input	8	(5)
1.5.2 Creating and Maintaining the Run Time Environment	13	(2)
1.5.3 Improving the Code	15	(1)
1.5.4 Creating the Output Program	16	(7)
1.6 Desirable Properties of a Compiler	23	(1)
1.7 Summary and Perspective	24	(3)
CHAPTER 2 Scanning	27	(46)
2.1 Introduction	27	(2)
2.2 Recognizing Words	29	(7)
2.2.1 A Formalism for Recognizers	31	(2)
2.2.2 Recognizing More-Complex Words	33	(2)
2.2.3 Automating Scanner Construction	35	(1)
2.3 Regular Expressions	36	(8)
2.3.1 Formalizing the Notation	37	(2)
2.3.2 Examples	39	(3)
2.3.3 Properties of RES	42	(2)
2.4 From Regular Expression to Scanner and Back	44	(17)
2.4.1 Nondeterministic Finite Automata	45	(3)
2.4.2 Regular Expression to NFA: Thompson's Construction	48	(3)
2.4.3 NFA to DFA: The Subset Construction	51	(4)
2.4.4 DFA to Minimal DFA: Hopcroft's Algorithm	55	(4)
2.4.5 DFA to Regular Expression	59	(1)
2.4.6 Using a DFA as a Recognizes	60	(1)
2.5 Implementing Scanners	61	(6)
2.5.1 Table-Driven Scanners	62	(2)
2.5.2 Direct-Coded Scanners	64	(1)
2.5.3 Handling Keywords	65	(1)
2.5.4 Specifying Actions	65	(2)
2.6 Advanced Topics	67	(4)
2.7 Summary and Perspective	71	(2)
CHAPTER 3 Parsing	73	(78)
3.1 Introduction	73	(1)
3.2 Expressing Syntax	74	(15)
3.2.1 Context-Free Grammars	75	(4)
3.2.2 Constructing Sentences	79	(4)
3.2.3 Encoding Meaning into Structure	83	(3)
3.2.4 Discovering a Specific Derivation	86	(1)
3.2.5 Context-Free Grammars versus Regular Expressions	87	(2)
3.3 Top-Down Parsing	89	(18)
3.3.1 Example	90	(4)
3.3.2 Complications in Top-Down Parsing	94	(1)
3.3.3 Eliminating Left Recursion	94	(3)
3.3.4 Eliminating the Need to Backtrack	97	(4)
3.3.5 Top-Down Recursive-Descent Parsers	101	(6)
3.4 Bottom-Up Parsing	107	(13)
3.4.1 Shift-Reduce Parsing	108	(4)
3.4.2 Finding Handles	112	(3)
3.4.3 LR(1) Parsers	115	(5)
3.5 Building LR(1) Tables	120	(13)
3.5.1 LR(1) Items	121	(1)
3.5.2 Constructing the Canonical Collection	122	(5)
3.5.3 Filling in the Tables	127	(2)
3.5.4 Errors in the Table Construction	129	(4)
3.6 Practical Issues	133	(7)
3.6.1 Error Recovery	134	(1)
3.6.2 Unary Operators	135	(1)
3.6.3 Handling Context-Sensitive Ambiguity	136	(2)
3.6.4 Left versus Right Recursion	138	(2)
3.7 Advanced Topics	140	(7)
3.7.1 Optimizing a Grammar	141	(2)
3.7.2 Reducing the Size of LR(1) Tables	143	(4)
3.8 Summary and Perspective	147	(4)
CHAPTER 4 Context-Sensitive Analysis	151	(58)
4.1 Introduction	151	(3)
4.2 An Introduction to Type Systems	154	(17)
4.2.1 The Purpose of Type Systems	154	(6)
4.2.2 Components of a Type System	160	(11)
4.3 The Attribute-Grammar Framework	171	(17)
4.3.1 Evaluation Methods	175	(1)
4.3.2 Circularity	176	(1)
4.3.3 Extended Examples	177	(8)
4.3.4 Problems with the Attribute-Grammar Approach	185	(3)
4.4 Ad Hoc Syntax-Directed Translation	188	(14)
4.4.1 Implementing Ad Hoc Syntax-Directed Translation	190	(3)
4.4.2 Examples	193	(9)
4.5 Advanced Topics	202	(4)
4.5.1 Harder Problems in Type Inference	202	(2)
4.5.2 Changing Associativity	204	(2)
4.6 Summary and Perspective	206	(3)
CHAPTER 5 Intermediate Representations	209	(42)
5.1 Introduction	209	(1)
5.2 Taxonomy	210	(3)
5.3 Graphical IRS	213	(9)
5.3.1 Syntax-Related Trees	213	(5)
5.3.2 Graphs	218	(4)
5.4 Linear IRS	222	(6)
5.4.1 Stack-Machine Code	224	(1)
5.4.2 Three-Address Code	224	(1)
5.4.3 Representing Linear Codes	225	(3)
5.5 Static Single-Assignment Form	228	(3)
5.6 Mapping Values to Names	231	(7)
5.6.1 Naming Temporary Values	233	(2)
5.6.2 Memory Models	235	(3)
5.7 Symbol Tables	238	(11)
5.7.1 Hash Tables	239	(2)
5.7.2 Building a Symbol Table	241	(1)
5.7.3 Handling Nested Scopes	242	(4)
5.7.4 The Many Uses for Symbol Tables	246	(3)
5.8 Summary and Perspective	249	(2)
CHAPTER 6 The Procedure Abstraction	251	(56)
6.1 Introduction	251	(3)
6.2 Control Abstraction	254	(2)
6.3 Name Spaces	256	(19)
6.3.1 Name Spaces of Algol-like Languages	257	(5)
6.3.2 Activation Records	262	(6)
6.3.3 Name Spaces of Object-Oriented Languages	268	(7)
6.4 Communicating Values between Procedures	275	(5)
6.4.1 Passing Parameters	275	(4)
6.4.2 Returning Values	279	(1)
6.5 Establishing Addressability	280	(6)
6.5.1 Trivial Base Addresses	280	(1)
6.5.2 Local Variables of Other Procedures	281	(5)
6.6 Standardized Linkages	286	(4)
6.7 Managing Memory	290	(15)
6.7.1 Memory Layout	290	(5)
6.7.2 Algorithms to Manage the Heap	295	(4)
6.7.3 Implicit Deallocation	299	(6)
6.8 Summary and Perspective	305	(2)
CHAPTER 7 Code Shape	307	(76)
7.1 Introduction	307	(2)
7.2 Assigning Storage Locations	309	(4)
7.2.1 Laying Out Data Areas	310	(1)
7.2.2 Keeping a Value in a Register	310	(2)
7.2.3 Machine Idiosyncrasies	312	(1)
7.3 Arithmetic Operators	313	(9)
7.3.1 Reducing Demand for Registers	315	(3)
7.3.2 Accessing Parameter Values	318	(1)
7.3.3 Function Calls in an Expression	319	(1)
7.3.4 Other Arithmetic Operators	319	(1)
7.3.5 Mixed Type Expressions	320	(1)
7.3.6 Assignment as an Operator	321	(1)
7.3.7 Commutativity, Associativity, and Number Systems	321	(1)
7.4 Boolean and Relational Operators	322	(11)
7.4.1 Representations	323	(5)
7.4.2 Hardware Support for Relational Operations	328	(4)
7.4.3 Choosing a Representation	332	(1)
7.5 Storing and Accessing Arrays	333	(11)
7.5.1 Referencing a Vector Element	333	(2)
7.5.2 Array Storage Layout	335	(2)
7.5.3 Referencing an Array Element	337	(6)
7.5.4 Range Checking	343	(1)
7.6 Character Strings	344	(6)
7.6.1 String Representations	344	(1)
7.6.2 String Assignment	345	(4)
7.6.3 String Concatenation	349	(1)
7.6.4 String Length	349	(1)
7.7 Structure References	350	(5)
7.7.1 Loading and Storing Anonymous values	351	(1)
7.7.2 Understanding Structure Layouts	352	(1)
7.7.3 Arrays of Structures	353	(1)
7.7.4 Unions and Run Time Tags	354	(1)
7.8 Control-Flow Constructs	355	(13)
7.8.1 Conditional Execution	356	(3)
7.8.2 Loops and Iteration	359	(5)
7.8.3 Case Statements	364	(4)
7.8.4 Break Statements	368	(1)
7.9 Procedure Calls	368	(5)
7.9.1 Evaluating Actual Parameters	369	(1)
7.9.2 Procedure-valued Parameters	370	(1)
7.9.3 Saving and Restoring Registers	370	(2)
7.9.4 Optimizations for Leaf Procedures	372	(1)
7.10 Implementing Object-Oriented Languages	373	(8)
7.10.1 Single Class, No Inheritance	373	(2)
7.10.2 Single Inheritance	375	(6)
7.11 Summary and Perspective	381	(2)
CHAPTER 8 Introduction to Code Optimization	383	(50)
8.1 Introduction	383	(3)
8.2 Background	386	(7)
8.2.1 An Example from LINPACK	387	(1)
8.2.2 Considerations for Optimization	388	(4)
8.2.3 Opportunities for Optimization	392	(1)
8.3 Redundant Expressions	393	(11)
8.3.1 Building a Directed Acyclic Graph	394	(4)
8.3.2 value Numbering	398	(5)
8.3.3 Lessons from Redundancy Elimination	403	(1)
8.4 Scope of Optimization	404	(4)
8.4.1 Local Methods	404	(1)
8.4.2 Superlocal Methods	405	(1)
8.4.3 Regional Methods	405	(2)
8.4.4 Global Methods	407	(1)
8.4.5 Whole-Program Methods	407	(1)
8.5 Value Numbering Over Regions Larger Than Basic Blocks	408	(9)
8.5.1 Superlocal Value Numbering	408	(5)
8.5.2 Dominator-Based Value Numbering	413	(4)
8.6 Global Redundancy Elimination	417	(7)
8.6.1 Computing Available Expressions	419	(2)
8.6.2 Replacing Redundant Computations	421	(2)
8.6.3 Putting It Together	423	(1)
8.7 Advanced Topics	424	(6)
8.7.1 Cloning to Increase Context	425	(2)
8.7.2 Inline Substitution	427	(3)
8.8 Summary and Perspective	430	(3)
CHAPTER 9 Data-Flow Analysis	433	(58)
9.1 Introduction	433	(2)
9.2 Iterative Data-Flow Analysis	435	(19)
9.2.1 Live Variables	435	(9)
9.2.2 Properties of the Iterative LIVEOUT Solver	444	(3)
9.2.3 Limitations on Data-Flow Analysis	447	(3)
9.2.4 Other Data-Flow Problems	450	(4)
9.3 Static Single-Assignment Form	454	(25)
9.3.1 A Simple Method for Building SSA Form	456	(1)
9.3.2 Dominance	457	(6)
9.3.3 Placing ø-Functions	463	(3)
9.3.4 Renaming	466	(8)
9.3.5 Reconstructing Executable Code from SSA Form	474	(5)
9.4 Advanced Topics	479	(9)
9.4.1 Structural Data-Flow Algorithms and Reducibility	480	(3)
9.4.2 Interprocedural Analysis	483	(5)
9.5 Summary and Perspective	488	(3)
CHAPTER 10 Scalar Optimizations	491	(54)
10.1 Introduction	491	(3)
10.2 A Taxonomy for Transformations	494	(4)
10.2.1 Machine-Independent Transformations	494	(2)
10.2.2 Machine-Dependent Transformations	496	(2)
10.3 Example Optimizations	498	(25)
10.3.1 Eliminating Useless and Unreachable Code	498	(7)
10.3.2 Code Motion	505	(10)
10.3.3 Specialization	515	(3)
10.3.4 Enabling Other Transformations	518	(5)
10.3.5 Redundancy Elimination	523	(1)
10.4 Advanced Topics	523	(19)
10.4.1 Combining Optimizations	523	(4)
10.4.2 Strength Reduction	527	(11)
10.4.3 Other Objectives for Optimization	538	(2)
10.4.4 Choosing an Optimization Sequence	540	(2)
10.5 Summary and Perspective	542	(3)
CHAPTER 11 Instruction Selection	545	(40)
11.1 Introduction	545	(7)
11.1.1 Building Retargetable Compilers	548	(4)
11.2 A Simple Tree-Walk Scheme	552	(6)
11.3 Instruction Selection via Tree-Pattern Matching	558	(11)
11.3.1 Rewrite Rules	559	(6)
11.3.2 Finding a Tiling	565	(3)
11.3.3 Tools	568	(1)
11.4 Instruction Selection via Peephole Optimization	569	(11)
11.4.1 Peephole Optimization	570	(8)
11.4.2 Peephole Transformers	578	(2)
11.5 Advanced Topics	580	(2)
11.5.1 Learning Peephole Patterns	580	(1)
11.5.2 Generating Instruction Sequences	581	(1)
11.6 Summary and Perspective	582	(3)
CHAPTER 12 Instruction Scheduling	585	(34)
12.1 Introduction	585	(2)
12.2 The Instruction-Scheduling Problem	587	(8)
12.2.1 Other Measures of Schedule Quality	593	(1)
12.2.2 What Makes Scheduling Hard?	593	(2)
12.3 List Scheduling	595	(10)
12.3.1 Efficiency Concerns	598	(1)
12.3.2 Other Priority Schemes	599	(1)
12.3.3 Forward versus Backward List Scheduling	600	(3)
12.3.4 Why Use List Scheduling?	603	(2)
12.4 Advanced Topics	605	(12)
12.4.1 Regional Scheduling	605	(9)
12.4.2 Cloning for Context	614	(3)
12.5 Summary and Perspective	617	(2)
CHAPTER 13 Register Allocation	619	(40)
13.1 Introduction	619	(1)
13.2 Background Issues	620	(4)
13.2.1 Memory versus Registers	621	(1)
13.2.2 Allocation versus Assignment	622	(1)
13.2.3 Register Classes	623	(1)
13.3 Local Register Allocation and Assignment	624	(5)
13.3.1 Top-Down Local Register Allocation	625	(1)
13.3.2 Bottom-Up Local Register Allocation	626	(3)
13.4 Moving Beyond Single Blocks	629	(4)
13.4.1 Liveness and Live Ranges	630	(1)
13.4.2 Complications at Block Boundaries	631	(2)
13.5 Global Register Allocation and Assignment	633	(18)
13.5.1 Discovering Global Live Ranges	635	(2)
13.5.2 Estimating Global Spill Costs	637	(2)
13.5.3 Interferences and the Interference Graph	639	(3)
13.5.4 Top-Down Coloring	642	(2)
13.5.5 Bottom-Up Coloring	644	(2)
13.5.6 Coalescing Live Ranges to Reduce Degree	646	(2)
13.5.7 Review and Comparison	648	(1)
13.5.8 Encoding Machine Constraints in the Interference Graph	649	(2)
13.6 Advanced Topics	651	(6)
13.6.1 Variations on Graph-Coloring Allocation	651	(3)
13.6.2 Harder Problems in Register Allocation	654	(3)
13.7 Summary and Perspective	657	(2)
APPENDIX A ILOC	659	(14)
A.1 Introduction	659	(3)
A.2 Naming Conventions	662	(1)
A.3 Individual Operations	662	(4)
A.3.1 Arithmetic	662	(1)
A.3.2 Shifts	663	(1)
A.3.3 Memory Operations	664	(1)
A.3.4 Register-to-Register Copy Operations	665	(1)
A.4 An Example	666	(1)
A.5 Control-Flow Operations	667	(3)
A.5.1 Alternate Comparison and Branch Syntax	668	(1)
A.5.2 Jumps	669	(1)
A.6 Representing SSA Form	670	(3)
APPENDIX B Data Structures	673	(30)
B.1 Introduction	673	(1)
B.2 Representing Sets	674	(5)
B.2.1 Representing Sets as Ordered Lists	675	(2)
B.2.2 Representing Sets as Bit Vectors	677	(1)
B.2.3 Representing Sparse Sets	678	(1)
B.3 Implementing Intermediate Representations	679	(7)
B.3.1 Graphical Intermediate Representations	679	(5)
B.3.2 Linear Intermediate Forms	684	(2)
B.4 Implementing Hash Tables	686	(12)
B.4.1 Choosing a Hash Function	688	(1)
B.4.2 Open Hashing	689	(2)
B.4.3 Open Addressing	691	(2)
B.4.4 Storing Symbol Records	693	(1)
B.4.5 Adding Nested Lexical Scopes	694	(4)
B.5 A Flexible Symbol Table Design	698	(5)
Bibliograpy	703	(22)
Exercises	725	(54)
Index	779