《Essentials of Compilation》

【实例截图】

【核心代码】

Contents
1 Preliminaries 5
1.1 Abstract Syntax Trees and Racket Structures . . . . . . . . . 5
1.2 Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Example Compiler: a Partial Evaluator . . . . . . . . . . . . 14
2 Integers and Variables 17
2.1 The R Var Language . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Extensible Interpreters via Method Overriding . . . . 19
2.1.2 Definitional Interpreter for R Var . . . . . . . . . . . . . 21
2.2 The x86 Int Assembly Language . . . . . . . . . . . . . . . . . 23
2.3 Planning the trip to x86 via the C Var language . . . . . . . . 27
2.3.1 The C Var Intermediate Language . . . . . . . . . . . . 30
2.3.2 The x86 Var dialect . . . . . . . . . . . . . . . . . . . . 30
2.4 Uniquify Variables . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Remove Complex Operands . . . . . . . . . . . . . . . . . . . 32
2.6 Explicate Control . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.7 Select Instructions . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8 Assign Homes . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.9 Patch Instructions . . . . . . . . . . . . . . . . . . . . . . . . 38
2.10 Print x86 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.11 Challenge: Partial Evaluator for R Var . . . . . . . . . . . . . 40
3 Register Allocation 41
3.1 Registers and Calling Conventions . . . . . . . . . . . . . . . 42
3.2 Liveness Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Build the Interference Graph . . . . . . . . . . . . . . . . . . 50
v
vi CONTENTS
3.4 Graph Coloring via Sudoku . . . . . . . . . . . . . . . . . . . 52
3.5 Patch Instructions . . . . . . . . . . . . . . . . . . . . . . . . 57
3.6 Print x86 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.7 Challenge: Move Biasing . . . . . . . . . . . . . . . . . . . . . 59
3.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 Booleans and Control Flow 67
4.1 The R If Language . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 Type Checking R If Programs . . . . . . . . . . . . . . . . . . 69
4.3 The C If Intermediate Language . . . . . . . . . . . . . . . . . 75
4.4 The x86 If Language . . . . . . . . . . . . . . . . . . . . . . . 76
4.5 Shrink the R If Language . . . . . . . . . . . . . . . . . . . . 78
4.6 Uniquify Variables . . . . . . . . . . . . . . . . . . . . . . . . 78
4.7 Remove Complex Operands . . . . . . . . . . . . . . . . . . . 79
4.8 Explicate Control . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.9 Select Instructions . . . . . . . . . . . . . . . . . . . . . . . . 85
4.10 Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . 86
4.10.1 Liveness Analysis . . . . . . . . . . . . . . . . . . . . . 86
4.10.2 Build the Interference Graph . . . . . . . . . . . . . . 88
4.11 Patch Instructions . . . . . . . . . . . . . . . . . . . . . . . . 88
4.12 An Example Translation . . . . . . . . . . . . . . . . . . . . . 88
4.13 Challenge: Remove Jumps . . . . . . . . . . . . . . . . . . . . 89
5 Tuples and Garbage Collection 93
5.1 The R Vec Language . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . 96
5.2.1 Graph Copying via Cheney’s Algorithm . . . . . . . . 99
5.2.2 Data Representation . . . . . . . . . . . . . . . . . . . 101
5.2.3 Implementation of the Garbage Collector . . . . . . . 104
5.3 Shrink . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4 Expose Allocation . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5 Remove Complex Operands . . . . . . . . . . . . . . . . . . . 107
5.6 Explicate Control and the C Vec language . . . . . . . . . . . . 107
5.7 Select Instructions and the x86 Global Language . . . . . . . . 107
5.8 Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . 113
5.9 Print x86 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.10 Challenge: Simple Structures . . . . . . . . . . . . . . . . . . 115
5.11 Challenge: Generational Collection . . . . . . . . . . . . . . . 115
CONTENTS vii
6 Functions 119
6.1 The R Fun Language . . . . . . . . . . . . . . . . . . . . . . . . 119
6.2 Functions in x86 . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2.1 Calling Conventions . . . . . . . . . . . . . . . . . . . 124
6.2.2 Efficient Tail Calls . . . . . . . . . . . . . . . . . . . . 125
6.3 Shrink R Fun . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.4 Reveal Functions and the R FunRef language . . . . . . . . . . 127
6.5 Limit Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.6 Remove Complex Operands . . . . . . . . . . . . . . . . . . . 128
6.7 Explicate Control and the C Fun language . . . . . . . . . . . . 129
6.8 Select Instructions and the x86 callq∗ Language . . . . . . . . 130
6.9 Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . 133
6.9.1 Liveness Analysis . . . . . . . . . . . . . . . . . . . . . 133
6.9.2 Build Interference Graph . . . . . . . . . . . . . . . . 133
6.9.3 Allocate Registers . . . . . . . . . . . . . . . . . . . . 133
6.10 Patch Instructions . . . . . . . . . . . . . . . . . . . . . . . . 133
6.11 Print x86 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.12 An Example Translation . . . . . . . . . . . . . . . . . . . . . 135
7 Lexically Scoped Functions 139
7.1 The R λ Language . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.2 Reveal Functions and the F 2 language . . . . . . . . . . . . . 144
7.3 Closure Conversion . . . . . . . . . . . . . . . . . . . . . . . . 144
7.4 An Example Translation . . . . . . . . . . . . . . . . . . . . . 146
7.5 Expose Allocation . . . . . . . . . . . . . . . . . . . . . . . . 146
7.6 Explicate Control and C Clos . . . . . . . . . . . . . . . . . . . 147
7.7 Select Instructions . . . . . . . . . . . . . . . . . . . . . . . . 147
7.8 Challenge: Optimize Closures . . . . . . . . . . . . . . . . . . 149
7.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . 151
8 Dynamic Typing 153
8.1 Representation of Tagged Values . . . . . . . . . . . . . . . . 158
8.2 The R Any Language . . . . . . . . . . . . . . . . . . . . . . . . 158
8.3 Cast Insertion: Compiling R Dyn to R Any . . . . . . . . . . . . 165
8.4 Reveal Casts . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.5 Remove Complex Operands . . . . . . . . . . . . . . . . . . . 168
8.6 Explicate Control and C Any . . . . . . . . . . . . . . . . . . . 168
8.7 Select Instructions . . . . . . . . . . . . . . . . . . . . . . . . 168
8.8 Register Allocation for R Any . . . . . . . . . . . . . . . . . . . 170
viii CONTENTS
9 Loops and Assignment 173
9.1 The R While Language . . . . . . . . . . . . . . . . . . . . . . . 173
9.2 Assignment and Lexically Scoped Functions . . . . . . . . . . 177
9.3 Cyclic Control Flow and Dataflow Analysis . . . . . . . . . . 178
9.4 Convert Assignments . . . . . . . . . . . . . . . . . . . . . . . 182
9.5 Remove Complex Operands . . . . . . . . . . . . . . . . . . . 185
9.6 Explicate Control and C ? . . . . . . . . . . . . . . . . . . . . 186
9.7 Select Instructions . . . . . . . . . . . . . . . . . . . . . . . . 187
9.8 Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . 187
9.8.1 Liveness Analysis . . . . . . . . . . . . . . . . . . . . . 188
9.9 Challenge: Arrays . . . . . . . . . . . . . . . . . . . . . . . . 188
9.9.1 Data Representation . . . . . . . . . . . . . . . . . . . 190
9.9.2 Reveal Casts . . . . . . . . . . . . . . . . . . . . . . . 193
9.9.3 Expose Allocation . . . . . . . . . . . . . . . . . . . . 194
9.9.4 Remove Complex Operands . . . . . . . . . . . . . . . 194
9.9.5 Explicate Control . . . . . . . . . . . . . . . . . . . . . 194
9.9.6 Select Instructions . . . . . . . . . . . . . . . . . . . . 194
10 Gradual Typing 197
10.1 Type Checking R ? , Casts, and R cast . . . . . . . . . . . . . . 197
10.2 Interpreting R cast . . . . . . . . . . . . . . . . . . . . . . . . 205
10.3 Lower Casts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
10.4 Differentiate Proxies . . . . . . . . . . . . . . . . . . . . . . . 210
10.5 Reveal Casts . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
10.6 Closure Conversion . . . . . . . . . . . . . . . . . . . . . . . . 214
10.7 Explicate Control . . . . . . . . . . . . . . . . . . . . . . . . . 214
10.8 Select Instructions . . . . . . . . . . . . . . . . . . . . . . . . 214
10.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . 216
11 Parametric Polymorphism 219
11.1 Compiling Polymorphism . . . . . . . . . . . . . . . . . . . . 222
11.2 Erase Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
12 Appendix 231
12.1 Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
12.2 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . 231
12.3 x86 Instruction Set Quick-Reference . . . . . . . . . . . . . . 233
12.4 Concrete Syntax for Intermediate Languages . . . . . . . . . 235
Index 237
CONTENTS ix
Bibliography 253