Modern Compiler Implementation in C

Cover......Page 0
Half Title......Page 2
Title Page......Page 4
Copyright......Page 5
Content......Page 6
Preface......Page 10
Part I Fundamentals of Compilation......Page 12
1 Introduction......Page 14
1.1 Modules and interfaces......Page 15
1.2 Tools and software......Page 16
1.3 Data structures for tree languages......Page 18
2 Lexical Analysis......Page 27
2.1 Lexical tokens......Page 28
2.2 Regular expressions......Page 29
2.3 Finite automata......Page 32
2.4 Nondeterministic finite automata......Page 35
2.5 Lex: a lexical analyzer generator......Page 41
3 Parsing......Page 50
3.1 Context-free grammars......Page 52
3.2 Predictive parsing......Page 57
3.3 LR parsing......Page 67
3.4 Using parser generators......Page 80
3.5 Error recovery......Page 87
4.1 Semantic actions......Page 99
4.2 Abstract parse trees......Page 103
5.1 Symbol Tables
......Page 114
5.2 Bindings for the Tiger compiler......Page 123
5.3 Type-checking expressions......Page 126
5.4 Type-checking declarations......Page 129
6 Activation Records......Page 136
6.1 Stack frames......Page 138
6.2 Frames in the Tiger compiler......Page 146
7 Translation to
Intermediate Code......Page 161
7.1 Intermediate representation trees......Page 162
7.2 Translation into trees......Page 165
7.3 Declarations......Page 181
8 Basic Blocks and Traces......Page 187
8.1 Canonical trees......Page 188
8.2 Taming conditional branches......Page 196
9 Instruction Selection......Page 202
9.1 Algorithms for instruction selection......Page 205
9.2 CISC machines......Page 213
9.3 Instruction selection for the Tiger compiler......Page 216
10 Liveness Analysis......Page 229
10.1 Solution of dataflow equations......Page 231
10.2 Liveness in the Tiger compiler......Page 240
11 Register Allocation......Page 246
11.1 Coloring by simplification......Page 247
11.2 Coalescing......Page 250
11.3 Precolored nodes......Page 254
11.4 Graph coloring implementation......Page 259
11.5 Register allocation for trees......Page 268
12 Putting It All Together......Page 276
Part II Advanced Topics......Page 282
13.1 Mark-and-sweep collection......Page 284
13.2 Reference counts......Page 289
13.3 Copying collection......Page 291
13.4 Generational collection......Page 296
13.5 Incremental collection......Page 298
13.6 Baker’s algorithm......Page 301
13.7 Interface to the compiler......Page 302
14.1 Classes......Page 310
14.2 Single inheritance of data fields......Page 313
14.3 Multiple inheritance......Page 315
14.4 Testing class membership......Page 317
14.6 Classless languages......Page 321
14.7 Optimizing object-oriented programs......Page 322
15 Functional Programming Languages......Page 326
15.1 A simple functional language......Page 327
15.2 Closures......Page 329
15.3 Immutable variables......Page 330
15.4 Inline expansion......Page 337
15.5 Closure conversion......Page 343
15.6 Efficient tail recursion......Page 346
15.7 Lazy evaluation......Page 348
16 Polymorphic Types......Page 361
16.1 Parametric polymorphism......Page 362
16.2 Type inference......Page 370
16.3 Representation of polymorphic variables......Page 380
16.4 Resolution of static overloading......Page 389
17 Dataflow Analysis......Page 394
17.1 Intermediate representation for flow analysis......Page 395
17.2 Various dataflow analyses......Page 398
17.3 Transformations using dataflow analysis......Page 403
17.4 Speeding up dataflow analysis......Page 404
17.5 Alias analysis......Page 413
18 Loop Optimizations......Page 421
18.1 Dominators......Page 424
18.2 Loop-invariant computations......Page 429
18.3 Induction variables......Page 430
18.4 Array-bounds checks......Page 436
18.5 Loop unrolling......Page 440
19 Static Single-Assignment
Form......Page 444
19.1 Converting to SSA form......Page 447
19.2 Efficient computation of the dominator tree......Page 455
19.3 Optimization algorithms using SSA......Page 462
19.4 Arrays, pointers, and memory......Page 468
19.5 The control-dependence graph......Page 470
19.6 Converting back from SSA form......Page 474
19.7 A functional intermediate form......Page 475
20 Pipelining and
Scheduling......Page 485
20.1 Loop scheduling without resource bounds......Page 489
20.2 Resource-bounded loop pipelining......Page 493
20.3 Branch prediction......Page 501
21 The Memory Hierarchy......Page 509
21.1 Cache organization......Page 510
21.2 Cache-block alignment......Page 513
21.3 Prefetching......Page 515
21.4 Loop interchange......Page 521
21.5 Blocking......Page 522
21.6 Garbage collection and the memory hierarchy......Page 525
A.2 Declarations......Page 529
A.3 Variables and expressions......Page 532
A.4 Standard library......Page 536
A.5 Sample Tiger programs......Page 537
Bibliography......Page 539
Index......Page 548