Modern Compiler Implementation in C

Description

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