Engineering a Compiler (eBook)

Front Cover 1
About the Authors 5
Engineering a Compiler 6
Copyright 7
Dedication 8
About the Cover 9
Table of Contents 10
Preface 20
Chapter 1. Overview of Compilation 26
1.1 Introduction 26
1.2 Compiler Structure 31
1.3 Overview of Translation 34
1.4 Summary and Perspective 46
Chapter Notes 47
Exercises 48
Chapter 2. Scanners 50
2.1 Introduction 50
2.2 Recognizing Words 52
2.3 Regular Expressions 59
2.4 From Regular Expression to Scanner 67
2.5 Implementing Scanners 84
2.6 Advanced Topics 99
2.7 Chapter Summary and Perspective 103
Chapter Notes 103
Exercises 105
Chapter 3. Parsers 108
3.1 Introduction 108
3.2 Expressing Syntax 110
3.3 Top-Down Parsing 121
3.4 Bottom-Up Parsing 141
3.5 Practical Issues 166
3.6 Advanced Topics 172
3.7 Summary and Perspective 180
Chapter Notes 181
Exercises 182
Chapter 4. Context-Sensitive Analysis 186
4.1 Introduction 186
4.2 An Introduction to Type Systems 189
4.3 The Attribute-Grammar Framework 207
4.4 Ad Hoc Syntax-Directed Translation 223
4.5 Advanced Topics 236
4.6 Summary and Perspective 240
Chapter Notes 241
Exercises 242
Chapter 5. Intermediate Representations 246
5.1 Introduction 246
5.2 Graphical IRs 251
5.3 Linear IRs 260
5.4 Mapping Values to Names 268
5.5 Symbol Tables 278
5.6 Summary and Perspective 289
Chapter Notes 289
Exercises 290
Chapter 6. The Procedure Abstraction 294
6.1 Introduction 294
6.2 Procedure Calls 297
6.3 Name Spaces 301
6.4 Communicating Values Between Procedures 322
6.5 Standardized Linkages 333
6.6 Advanced Topics 337
6.7 Summary and Perspective 347
Chapter Notes 348
Exercises 349
Chapter 7. Code Shape 356
7.1 Introduction 356
7.2 Assigning Storage Locations 359
7.3 Arithmetic Operators 367
7.4 Boolean and Relational Operators 375
7.5 Storing and Accessing Arrays 384
7.6 Character Strings 394
7.7 Structure References 399
7.8 Control-Flow Constructs 405
7.9 Procedure Calls 417
7.10 Summary and Perspective 421
Chapter Notes 422
Exercises 423
Chapter 8. Introduction to Optimization 430
8.1 Introduction 430
8.2 Background 432
8.3 Scope of Optimization 442
8.4 Local Optimization 445
8.5 Regional Optimization 462
8.6 Global Optimization 470
8.7 Interprocedural Optimization 482
8.8 Summary and Perspective 494
Chapter Notes 495
Exercises 496
Chapter 9. Data-Flow Analysis 500
9.1 Introduction 500
9.2 Iterative Data-Flow Analysis 502
9.3 Static Single-Assignment Form 520
9.4 Interprocedural Analysis 544
9.5 Advanced Topics 551
9.6 Summary and Perspective 558
Chapter Notes 559
Exercises 560
Chapter 10. Scalar Optimizations 564
10.1 Introduction 564
10.2 Eliminating Useless and Unreachable Code 569
10.3 Code Motion 576
10.4 Specialization 585
10.5 Redundancy Elimination 590
10.6 Enabling Other Transformations 594
10.7 Advanced Topics 600
10.8 Summary and Perspective 617
Chapter Notes 618
Exercises 619
Chapter 11. Instruction Selection 622
11.1 Introduction 622
11.2 Code Generation 625
11.3 Extending the Simple Treewalk Scheme 628
11.4 Instruction Selection via Tree-Pattern Matching 635
11.5 Instruction Selection via Peephole Optimization 646
11.6 Advanced Topics 657
11.7 Summary and Perspective 659
Chapter Notes 660
Exercises 662
Chapter 12. Instruction Scheduling 664
12.1 Introduction 664
12.2 The Instruction-Scheduling Problem 668
12.3 Local List Scheduling 676
12.4 Regional Scheduling 686
12.5 Advanced Topics 691
12.6 Summary and Perspective 698
Chapter Notes 698
Exercises 700
Chapter 13. Register Allocation 704
13.1 Introduction 704
13.2 Background Issues 706
13.3 Local Register Allocation and Assignment 709
13.4 Global Register Allocation and Assignment 718
13.5 Advanced Topics 738
13.6 Summary and Perspective 743
Chapter Notes 744
Exercises 745
Appendix A. ILOC 750
A.1 Introduction 750
A.2 Naming Conventions 752
A.3 Individual Operations 753
A.4 Control-Flow Operations 756
A.5 Representing SSA Form 758
Appendix B. Data Structures 762
B.1 Introduction 762
B.2 Representing Sets 763
B.3 Implementing Intermediate Representations 768
B.4 Implementing Hash Tables 775
B.5 A Flexible Symbol-Table Design 785
Appendix Notes 787
Bibliography 790
Index 812