Engineering a Compiler

1;Front Cover;1 2;About the Authors;5 3;Engineering a Compiler;6 4;Copyright;7 5;Dedication;8 6;About the Cover;9 7;Table of Contents;10 8;Preface;20 9;Chapter 1. Overview of Compilation;26 9.1;1.1 Introduction;26 9.2;1.2 Compiler Structure;31 9.3;1.3 Overview of Translation;34 9.4;1.4 Summary and Perspective;46 9.5;Chapter Notes;47 9.6;Exercises;48 10;Chapter 2. Scanners;50 10.1;2.1 Introduction;50 10.2;2.2 Recognizing Words;52 10.3;2.3 Regular Expressions;59 10.4;2.4 From Regular Expression to Scanner;67 10.5;2.5 Implementing Scanners;84 10.6;2.6 Advanced Topics;99 10.7;2.7 Chapter Summary and Perspective;103 10.8;Chapter Notes;103 10.9;Exercises;105 11;Chapter 3. Parsers;108 11.1;3.1 Introduction;108 11.2;3.2 Expressing Syntax;110 11.3;3.3 Top-Down Parsing;121 11.4;3.4 Bottom-Up Parsing;141 11.5;3.5 Practical Issues;166 11.6;3.6 Advanced Topics;172 11.7;3.7 Summary and Perspective;180 11.8;Chapter Notes;181 11.9;Exercises;182 12;Chapter 4. Context-Sensitive Analysis;186 12.1;4.1 Introduction;186 12.2;4.2 An Introduction to Type Systems;189 12.3;4.3 The Attribute-Grammar Framework;207 12.4;4.4 Ad Hoc Syntax-Directed Translation;223 12.5;4.5 Advanced Topics;236 12.6;4.6 Summary and Perspective;240 12.7;Chapter Notes;241 12.8;Exercises;242 13;Chapter 5. Intermediate Representations;246 13.1;5.1 Introduction;246 13.2;5.2 Graphical IRs;251 13.3;5.3 Linear IRs;260 13.4;5.4 Mapping Values to Names;268 13.5;5.5 Symbol Tables;278 13.6;5.6 Summary and Perspective;289 13.7;Chapter Notes;289 13.8;Exercises;290 14;Chapter 6. The Procedure Abstraction;294 14.1;6.1 Introduction;294 14.2;6.2 Procedure Calls;297 14.3;6.3 Name Spaces;301 14.4;6.4 Communicating Values Between Procedures;322 14.5;6.5 Standardized Linkages;333 14.6;6.6 Advanced Topics;337 14.7;6.7 Summary and Perspective;347 14.8;Chapter Notes;348 14.9;Exercises;349 15;Chapter 7. Code Shape;356 15.1;7.1 Introduction;356 15.2;7.2 Assigning Storage Locations;359 15.3;7.3 Arithmetic Operators;367 15.4;7.4 Boolean and Re
lational Operators;375 15.5;7.5 Storing and Accessing Arrays;384 15.6;7.6 Character Strings;394 15.7;7.7 Structure References;399 15.8;7.8 Control-Flow Constructs;405 15.9;7.9 Procedure Calls;417 15.10;7.10 Summary and Perspective;421 15.11;Chapter Notes;422 15.12;Exercises;423 16;Chapter 8. Introduction to Optimization;430 16.1;8.1 Introduction;430 16.2;8.2 Background;432 16.3;8.3 Scope of Optimization;442 16.4;8.4 Local Optimization;445 16.5;8.5 Regional Optimization;462 16.6;8.6 Global Optimization;470 16.7;8.7 Interprocedural Optimization;482 16.8;8.8 Summary and Perspective;494 16.9;Chapter Notes;495 16.10;Exercises;496 17;Chapter 9. Data-Flow Analysis;500 17.1;9.1 Introduction;500 17.2;9.2 Iterative Data-Flow Analysis;502 17.3;9.3 Static Single-Assignment Form;520 17.4;9.4 Interprocedural Analysis;544 17.5;9.5 Advanced Topics;551 17.6;9.6 Summary and Perspective;558 17.7;Chapter Notes;559 17.8;Exercises;560 18;Chapter 10. Scalar Optimizations;564 18.1;10.1 Introduction;564 18.2;10.2 Eliminating Useless and Unreachable Code;569 18.3;10.3 Code Motion;576 18.4;10.4 Specialization;585 18.5;10.5 Redundancy Elimination;590 18.6;10.6 Enabling Other Transformations;594 18.7;10.7 Advanced Topics;600 18.8;10.8 Summary and Perspective;617 18.9;Chapter Notes;618 18.10;Exercises;619 19;Chapter 11. Instruction Selection;622 19.1;11.1 Introduction;622 19.2;11.2 Code Generation;625 19.3;11.3 Extending the Simple Treewalk Scheme;628 19.4;11.4 Instruction Selection via Tree-Pattern Matching;635 19.5;11.5 Instruction Selection via Peephole Optimization;646 19.6;11.6 Advanced Topics;657 19.7;11.7 Summary and Perspective;659 19.8;Chapter Notes;660 19.9;Exercises;662 20;Chapter 12. Instruction Scheduling;664 20.1;12.1 Introduction;664 20.2;12.2 The Instruction-Scheduling Problem;668 20.3;12.3 Local List Scheduling;676 20.4;12.4 Regional Scheduling;686 20.5;12.5 Advanced Topics;691 20.6;12.6 Summary and Perspective;698 20.7;Chapter Notes;698 20.8;Exercises;700 21;Chapter 13. Registe
r Allocation;704 21.1;13.1 Introduction;704 21.2;13.2 Background Issues;706 21.3;13.3 Local Register Allocation and Assignment;709 21.4;13.4 Global Register Allocation and Assignment;718 21.5;13.5 Advanced Topics;738 21.6;13.6 Summary and Perspective;743 21.7;Chapter Notes;744 21.8;Exercises;745 22;Appendix A. ILOC;750 22.1;A.1 Introduction;750 22.2;A.2 Naming Conventions;752 22.3;A.3 Individual Operations;753 22.4;A.4 Control-Flow Operations;756 22.5;A.5 Representing SSA Form;758 23;Appendix B. Data Structures;762 23.1;B.1 Introduction;762 23.2;B.2 Representing Sets;763 23.3;B.3 Implementing Intermediate Representations;768 23.4;B.4 Implementing Hash Tables;775 23.5;B.5 A Flexible Symbol-Table Design;785 23.6;Appendix Notes;787 24;Bibliography;790 25;Index;812