Trustworthy compilers

Trustworthy Compilers......Page 5
Contents......Page 9
Preface......Page 15
Acknowledgments......Page 21
1. Introduction......Page 23
1.1. The Concept of a Trustworthy Compiler......Page 24
1.2. Kinds of Compilers......Page 26
1.3. Evolution of Java Compilers......Page 27
1.4. Compilation for .NET......Page 28
1.5. Phases of Compilation......Page 29
1.6. Overview of Compiler Development Principles and Technologies......Page 30
1.7. History of Compiler Development in the U.S.S.R. and in Russia......Page 35
Exercises to Chapter 1......Page 37
2.1. The Trustworthy Computing (TWC) Initiative......Page 38
2.2. TWC and Trustworthy Compilers......Page 39
2.3. Verified Compilers......Page 46
2.4. Spec#: Microsoft’s Approach to Verifying Compilers......Page 48
2.5. Perspectives of Verified and Verifying Compilation......Page 50
Exercises to Chapter 2......Page 51
3.1. Token Classes......Page 53
3.2. The Output of the Lexical Analyzer......Page 55
3.3. Processing White Spaces, Comments, and New Lines......Page 56
3.4. Theoretical Models of Lexical Analysis......Page 57
3.6. Processing Identifiers and Keywords......Page 60
3.7. The Architecture of a Lexical Analyzer and the Principles of Its Implementation......Page 64
3.8. The Lexical Analyzer Generator Lex......Page 67
3.9. Lexical Analyzer Generation in ANTLR......Page 70
Exercises to Chapter 3......Page 73
4. Parsing and Trustworthy Methods of Syntax Error Recovery......Page 74
4.1. Basic Concepts and Principles of Parsing......Page 75
4.2. Recursive Descent and Simple Lookahead Mechanism......Page 77
4.3. Overview of Error Recovery in Parsing: Error Recovery for Recursive Descent......Page 84
4.4. LR(1) and LALR(1) Parsing......Page 89
4.5. Error Recovery in LR Parsing......Page 103
4.6. The Yacc Parser Generator......Page 104
4.7. The Bison Parser Generator: Generalized LR Parsing......Page 109
4.8. The Yacc++, JavaCC, SableCC, ANTLR, and CoCo/R Object-Oriented Parser Generators......Page 111
Exercises to Chapter 4......Page 117
5.1. Basic Concepts and Principles of Semantic Analysis......Page 119
5.2. Formal Model of Semantic Analysis: Attributed Grammars......Page 121
5.3. Definition Systems with Forward References and the Algorithm of Their One-Pass Analysis......Page 125
5.4. Commonly Used Semantic Attributes for Program Constructs......Page 129
5.5. Design Flaws of the Semantic Attribute Evaluation and Our Efficient Methods to Speed It Up......Page 133
5.6. Lookup—Traditional and Novel Techniques......Page 136
5.7. Typing and Type-Checking: Basic Concepts......Page 140
5.8. Representing Types at Compile Time......Page 143
5.9. Efficient Method and Algorithm to Represent and Handle Types with Structural Identity......Page 145
5.10. Type Identity and Type Compatibility......Page 148
5.11. Type-Checking, Typing Error Diagnostics, and Recovery......Page 150
5.12. Code Trustworthiness Checks During Semantic Analysis......Page 153
5.13. Checks for Context Restrictions in Semantic Analysis......Page 161
5.14. Intermediate Code Generation—Principles and Architectural Models......Page 163
5.15. Postfix (Reverse Polish) Notation......Page 164
5.16. PCC Trees......Page 168
5.17. Triples......Page 171
5.18. Summary of the Chapter......Page 172
Exercises to Chapter 5......Page 173
6.1. Basic Concepts and Trustworthiness of Optimizations......Page 174
6.2. Optimizations as Mixed Computations......Page 176
6.3. Overview of the Most Common Kinds of Optimizations......Page 177
6.4. Control Flow and Data Flow Dependencies......Page 184
6.5. Static Single Assignment (SSA)......Page 185
6.7. Optimization in Sun Studio Compilers......Page 187
6.8. Optimizations of the Java Bytecode......Page 189
6.10. Optimizations during JIT Compilation......Page 192
Exercises to Chapter 6......Page 195
7.1. Target Platforms for Code Generation......Page 196
7.2. Overview of Code Generation Tasks and Goals......Page 197
7.3. Specifics of Code Generation for .NET......Page 201
7.4. Specifics of Code Generation for SPARC Architecture......Page 202
7.5. Representing Types and Addressing Variables......Page 203
7.6. Representing Procedures, Functions, and Methods......Page 208
7.7. Principles of SPARC Architecture......Page 212
7.8. Example of Code Generation for SPARC Architecture......Page 214
7.9. Generation of Debugging Information......Page 217
7.10. Code Generation for Declarations (Definitions), Expressions, and Statements......Page 219
Exercises to Chapter 7......Page 221
8.1. The Tasks of the Runtime......Page 222
8.2. The Relationship of the Runtime and the Operating System (OS)......Page 224
8.3. JIT Compilation......Page 225
8.4. The Architecture of FJIT––JIT Compiler for SSCLI/Rotor......Page 233
8.5. The Architecture of Optimizing JIT Compiler for SSCLI/Rotor......Page 234
8.6. AOT Compilation......Page 242
Exercises to Chapter 8......Page 243
9. Graph Grammars and Graph Compilers......Page 244
9.1. Basic Concepts of Graph Grammars and Graph Compilers......Page 245
9.2. Categorical Approach to Graph Transformations......Page 248
9.3. Reserved Graph Grammars (RGGs)......Page 252
9.4. Layered Graph Grammars......Page 254
9.5. Meta-Modeling Approach to Graph Grammars and Diameta Editor......Page 255
9.6. Hypergraph Approach to Graph Grammars in Diagen......Page 257
9.7. Graph Compiler Generation Tools......Page 259
Exercises to Chapter 9......Page 260
10. Microsoft Phoenix, Phoenix-Targeted Tools, and Our Phoenix Projects......Page 261
10.1. History of Phoenix and of Our Phoenix Projects......Page 262
10.2. Overview of Phoenix Architecture......Page 264
10.3. Phoenix-Based Tools, Passes, Phases, and Plug-Ins......Page 268
10.4. Phoenix Primitives: Strings and Names......Page 269
10.5. Phoenix Intermediate Representation (IR)......Page 270
10.6. Phoenix Symbol System......Page 275
10.7. Phoenix Type System......Page 279
10.8. Data Flow Analysis, Control Flow Analysis, Graphs, and Static Single Assignment (SSA) in Phoenix......Page 282
10.9. Overview of Other Phoenix Features......Page 286
10.10. Example of a Phoenix-Based Plug-In......Page 287
10.11. Phoenix-Fete—A Compiler Front-End Development Toolkit and Environment Targeted to Phoenix......Page 289
10.11.1. Architectural Specifics of Phoenix-FETE......Page 290
10.11.2. The Input Grammar Meta-Language......Page 291
10.11.3. The Current Status of the Implementation......Page 293
Exercises to Chapter 10......Page 296
Conclusions......Page 299
References......Page 301
Index......Page 307