TDDC86 Compiler Optimizations and Code Generation

Course information

Course organization
Course contents
Course literature

Organization

The lectures introduce the theory and are complemented by lessons with exercises. This part should equip you with an overview of the subject and provide the necessary background to be able to understand and critically review recent research articles in advanced compiler technology. The theory part is examined by a written exam.
There is also a project that can be done alone or in groups of two students.
Both the written exam and the project must be passed to pass the course.

Project: The project task consists either of an experimental self-study of selected optimizations in a modern compiler framework or of a critical review of a recent conference paper or journal article in compiler technology (two related papers/articles for groups of 2 students).
The project result is to be presented both by an oral presentation with opposition of another project, and by a written summary paper. The course therefore concludes with a simulated compiler workshop (announced as seminar sessions (SE) in the web schedule) where the project results are presented for all participants. Presence during the seminar sessions is mandatory.
For more details, see the project page.

Course contents

• Design of intermediate representations.
• Program analysis:
  Control flow analysis, Data flow analysis, Dependence analysis, Interprocedural analysis.
• Target-independent optimizations:
  Common subexpression elimination, Loop transformations, loop parallelization.
• Static single assignment (SSA) form.
• Code generation:
  Instruction selection. Local and global instruction scheduling. Software pipelining. Register allocation.
  Phase ordering problems and integrated code generation. Code generation issues for DSP and embedded processors.

and, as time permits,

• Code generation for parallel systems.
• Just-in-time (JIT) compilation.
• Compiling object-oriented programming languages.
• Exception handling.
• Garbage collection.

Course literature

This is an advanced course, and there is no single textbook that covers everything. The following books can be used for background reading. They are all available in the library.

• Aho, Lam, Sethi, Ullman: Compilers Principles, Techniques, and Tools, Second Edition. Addison-Wesley, 2006/2007.
  Available at Kvartersbibliotek B.
• Aho, Sethi, Ullman: Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986. Chapter 10.
  Available at Kvartersbibliotek B.
• Muchnick: Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997.
  Available at Kvartersbibliotek B.
• Cooper, Torczon: Engineering a compiler. Morgan Kaufmann, 2004.
  Available at Kvartersbibliotek B.
• Srikant, Shankar: The Compiler Design Handbook, Second Edition. CRC Press, 2008.
  Available at Kvartersbibliotek B, also the first edition..
• Fisher, Faraboschi, Young: Embedded Computing - A VLIW Approach to Architecture, Compilers, and Tools. Morgan Kaufmann, 2005.
  Available at Kvartersbibliotek B.

Reading directions are given for the books by Aho/Lam/Sethi/Ullman and Muchnick on the lectures page.

Further material

• C. Kessler: Compiling for VLIW DSPs. Draft 2009, handed out.

For repetition of some foundations (course prerequisites) in graph-theory, computer architecture, system software:

• slides on DFS
• slides on trees and tree traversals
• Review of processor architecture concepts and system software (assembler, linker, loader)

Conferences and Journals

For the literature studies in the project work, we recommend in the first place the ACM Digital Library, with ACM SIGPLAN conferences such as
PLDI (Programming Language Design and Implementation) (TOC),
LCTES (Languages, Compilers and Tools for Embedded Systems) (TOC) , or
CGO (Code Generation and Optimization) (TOC),
and journals such as
ACM TOPLAS (Transactions on Programming Languages and Systems) (TOC).
Also, the IEEE/ACM conferences
PACT (Parallel Architecture and Compilation Techniques) (TOC) (TOC2) and
MICRO (Int. Symp. on Microarchitecture) (TOC)
feature many compiler-related papers. Other relevant conferences are
CC, HiPEAC, SCOPES and CASES.
Furthermore, most conferences and journals on parallel processing, such as PPoPP, EuroPar, IPDPS, or IJPP, can also contain relevant material.

Page responsible: Christoph W Kessler
Last updated: 2009-08-28