The goal of An Introduction to the Theory of Optimizing Compilers is to give the reader a solid understanding of modern optimizing compilers. The theory is focused on

• control flow graphs, including algorithms for computing dominance, dominance frontiers, and control dependence,
  
• static single assignment form (SSA form) including recent advances in translation from SSA form based on fast liveness checking and coalescing, and
  
• loop transformations.
  

We also cover instruction scheduling and register allocation.

The optimization techniques we present include constant propagation with conditional branches, partial redundancy elimination, hash-based and global value numbering, operator strength reduction, dead code elimination, control flow graph simplification based
on postdominators, translation from SSA form based on coalescing, unimodular loop transformations, modulo scheduling, and iterative register coalescing.

The book is to a high degree self-contained and is intended to be suitable both for self-study and university courses. For completeness we provide a review of fundamentals, including sections on sets and relations, graphs, number theory, and some linear algebra.





Prerequisites

The reader is assumed to have studied algorithms and data structures, but no knowledge about compiler front-ends is necessary.




About the author

Dr. Jonas Skeppstedt has done research on optimizing compilers and multicore computer architecture in Lund, Chalmers, and USC in Los Angeles; his lmpcc compiler was rewarded ISO C certification in 2003 for C99; has taught optimizing compilers at Lund University for many years and has developed safety-critical C code for the new European Rail Traffic Management System (ERTMS), and helped German lawyers as expert witness on the C programming language.