Compiler Construction

Core Course

People

Sebastian Hack, Simon Moll, Johannes Doerfert

General Information

The course treats compiler construction for imperative programming languages. This includes lexical, syntactical, and semantic analysis as well as static program analysis, optimization, and code generation. This course provides all necessary theoretical knowledge required to implement a compiler from scratch, which forms the practical part of the lecture.

Modus Operandi

There will be eight voluntary mini tests which will take place in the last 20 minutes within the tutorial. Additionally, there will be voluntary exercises. To get a course certificate, students must pass the final exam and the project. Final grades will be based on the exam and the project.

Lecture

Type: core lecture (9 credit points)
Place: lecture hall I (HS 1), building E1 3
Time: Tuesday 16–18 (c.t.) and Friday 14–16 (c.t.)
First Meeting: Tuesday 2015-10-20, 16–18 (c.t.)

Tutorial

Place: E1.3 SR 14
Time: Wednesday 10–12 (c.t.) and 14–16 (c.t.)
First Tutorial: Wednesday 2015-10-28

Exams

Place: E1.3, HS 002
Exam: Monday, 2016-02-29, 10–12 (s.t.)
Re-exam: Monday, 2016-04-11, 10–12 (s.t.)

Support

We use a GitLab to manage the course project.
We use a Forum as an official communication channel.
We run nightly tests on your project to provide you with feedback about your progress.

Material

Slides

Date	Topic
2015-10-23	Lexical Analysis
2015-10-27	Context-free Grammars, Pushdown Automata
2015-11-03	Top-Down Parsing (LL)
2015-11-10, 2015-11-14	Bottom-Up Parsing (LR)
2015-11-17	Semantic Analysis
2015-11-20 — 2015-12-01	Program Analysis
2015-12-04	Intervals, Pentagons
2015-12-08	Global Value Numbering
2015-12-11	SSA Introduction (accessible from UdS IP range only)
2015-12-14	SSA Construction via Dominance Frontiers (lecture notes coming soon)
2015-12-18	Simple and Efficient SSA Construction, IR construction, LLVM-IR generation
2016-01-05	Introduction to Code Generation Graph-Coloring Register Allocation
2016-01-08, 2016-12-12	Register Allocation of SSA-form Programs
2016-01-15	Instruction Selection using PBQP
2016-01-19	Loop Transformations, Example Code
2016-01-27	Scheduling in the Polyhedral Model
2016-01-29	Data Flow Analysis in Loop Nests

Exercises

Project Material

The final draft of C1X, dated 12 April 2011
Pretty printed example C file
LLVM-IR generation examples
Using SSA in Constant Propagation: Constant Propagation with Conditional Branches
Cytron et al.'s dominance frontier technique: Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
The libfirm approach to SSA construction: Simple and Efficient Construction of Static Single Assignment Form

Literature

The course is mainly built on these books:

Helmut Seidl, Reinhard Wilhelm, Sebastian Hack. Compiler Design - Syntactic and Semantic Analysis, Springer 2013.
The german version is available online from the university IP address space.
Helmut Seidl, Reinhard Wilhelm, Sebastian Hack. Compiler Design - Analysis and Transformation, Springer 2012.
The german version is available online from the university IP address space.

The library has several copies of the english version of the book.

The following books are among the "standard" compiler textbooks:

Andrew Appel, Jens Palsberg. Modern Compiler Implementation in Java, Cambridge University Press 2002
Keith Cooper, Linda Torczon. Engineering a Compiler, 2nd Edition, Morgan Kaufman 2011
Bob Morgan. Building an Optimizing Compiler, Digital Press, 1998
Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman. Compilers: Principles, Techniques, and Tools, 2nd Edition, Addison Wesley, 2006

The following textbooks are stanard references for loop transformations:

Michael Wolfe. High-Performance Compilers for Parallel Computing
Randy Allen, Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach

The following textbook provides a good introduction into the theory of polyhedra and linear programming:

Dimitris Bertsimas, John N. Tsitsiklis. Introduction to Linear Optimization