You are previewing Modern Compiler Implementation in C.
O'Reilly logo
Modern Compiler Implementation in C

Book Description

This new, expanded textbook describes all phases of a modern compiler: lexical analysis, parsing, abstract syntax, semantic actions, intermediate representations, instruction selection via tree matching, dataflow analysis, graph-coloring register allocation, and runtime systems. It includes good coverage of current techniques in code generation and register allocation, as well as functional and object-oriented languages, that are missing from most books. In addition, more advanced chapters are now included so that it can be used as the basis for a two-semester or graduate course. The most accepted and successful techniques are described in a concise way, rather than as an exhaustive catalog of every possible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actual C header files. The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compiler design. The second part, Advanced Topics, which includes the advanced chapters, covers the compilation of object-oriented and functional languages, garbage collection, loop optimizations, SSA form, loop scheduling, and optimization for cache-memory hierarchies.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Contents
  6. Preface
  7. Part I: Fundamentals of Compilation
    1. 1. Introduction
      1. 1.1 Modules and interfaces
      2. 1.2 Tools and software
      3. 1.3 Data structures for tree languages
    2. 2. Lexical Analysis
      1. 2.1 Lexical tokens
      2. 2.2 Regular expressions
      3. 2.3 Finite automata
      4. 2.4 Nondeterministic finite automata
      5. 2.5 Lex: a lexical analyzer generator
    3. 3. Parsing
      1. 3.1 Context-free grammars
      2. 3.2 Predictive parsing
      3. 3.3 LR parsing
      4. 3.4 Using parser generators
      5. 3.5 Error recovery
    4. 4. Abstract Syntax
      1. 4.1 Semantic actions
      2. 4.2 Abstract parse trees
    5. 5. Semantic Analysis
      1. 5.1 Symbol tables
      2. 5.2 Bindings for the Tiger compiler
      3. 5.3 Type-checking expressions
      4. 5.4 Type-checking declarations
    6. 6. Activation Records
      1. 6.1 Stack frames
      2. 6.2 Frames in the Tiger compiler
    7. 7. Translation to Intermediate Code
      1. 7.1 Intermediate representation trees
      2. 7.2 Translation into trees
      3. 7.3 Declarations
    8. 8. Basic Blocks and Traces
      1. 8.1 Canonical trees
      2. 8.2 Taming conditional branches
    9. 9. Instruction Selection
      1. 9.1 Algorithms for instruction selection
      2. 9.2 CISC machines
      3. 9.3 Instruction selection for the Tiger compiler
    10. 10. Liveness Analysis
      1. 10.1 Solution of dataflow equations
      2. 10.2 Liveness in the Tiger compiler
    11. 11. Register Allocation
      1. 11.1 Coloring by simplification
      2. 11.2 Coalescing
      3. 11.3 Precolored nodes
      4. 11.4 Graph coloring implementation
      5. 11.5 Register allocation for trees
    12. 12. Putting It All Together
  8. Part II: Advanced Topics
    1. 13. Garbage Collection
      1. 13.1 Mark-and-sweep collection
      2. 13.2 Reference counts
      3. 13.3 Copying collection
      4. 13.4 Generational collection
      5. 13.5 Incremental collection
      6. 13.6 Baker’s algorithm
      7. 13.7 Interface to the compiler
    2. 14. Object-Oriented Languages
      1. 14.1 Classes
      2. 14.2 Single inheritance of data fields
      3. 14.3 Multiple inheritance
      4. 14.4 Testing class membership
      5. 14.5 Private fields and methods
      6. 14.6 Classless languages
      7. 14.7 Optimizing object-oriented programs
    3. 15. Functional Programming Languages
      1. 15.1 A simple functional language
      2. 15.2 Closures
      3. 15.3 Immutable variables
      4. 15.4 Inline expansion
      5. 15.5 Closure conversion
      6. 15.6 Efficient tail recursion
      7. 15.7 Lazy evaluation
    4. 16. Polymorphic Types
      1. 16.1 Parametric polymorphism
      2. 16.2 Type inference
      3. 16.3 Representation of polymorphic variables
      4. 16.4 Resolution of static overloading
    5. 17. Dataflow Analysis
      1. 17.1 Intermediate representation for flow analysis
      2. 17.2 Various dataflow analyses
      3. 17.3 Transformations using dataflow analysis
      4. 17.4 Speeding up dataflow analysis
      5. 17.5 Alias analysis
    6. 18. Loop Optimizations
      1. 18.1 Dominators
      2. 18.2 Loop-invariant computations
      3. 18.3 Induction variables
      4. 18.4 Array-bounds checks
      5. 18.5 Loop unrolling
    7. 19. Static Single-Assignment Form
      1. 19.1 Converting to SSA form
      2. 19.2 Efficient computation of the dominator tree
      3. 19.3 Optimization algorithms using SSA
      4. 19.4 Arrays, pointers, and memory
      5. 19.5 The control-dependence graph
      6. 19.6 Converting back from SSA form
      7. 19.7 A functional intermediate form
    8. 20. Pipelining and Scheduling
      1. 20.1 Loop scheduling without resource bounds
      2. 20.2 Resource-bounded loop pipelining
      3. 20.3 Branch prediction
    9. 21. The Memory Hierarchy
      1. 21.1 Cache organization
      2. 21.2 Cache-block alignment
      3. 21.3 Prefetching
      4. 21.4 Loop interchange
      5. 21.5 Blocking
      6. 21.6 Garbage collection and the memory hierarchy
  9. Appendix: Tiger Language Reference Manual
    1. A.1 Lexical issues
    2. A.2 Declarations
    3. A.3 Variables and expressions
    4. A.4 Standard library
    5. A.5 Sample Tiger programs
  10. Bibliography
  11. Index