DF00100
Advanced Compiler Construction (9hp)
ht1/2014

Goals
Give Ph.D. students or practitioners knowledge about advanced compiler technology, including program analysis, intermediate representations, compiler optimizations, code generation, compiler frameworks, run-time systems, and compilation techniques for parallel and embedded systems.

Prerequisites
Basic course in compiler construction, corresponding to the undergraduate courses Compilers and Interpreters, or Compiler Construction.
Basic course in data structures and algorithms.
Basic knowledge in processor architecture.
For the labs: Programming in C++/Linux.

Contents and schedule

Lecture blocks: 2 intensive weeks in Linköping.
In 2014, the course has moved to the autumn term. The lectures blocks have been scheduled for weeks 36 and 37/2014.
The detailed schedule is given below:

Date	Time	Location	Topic (with links to slides (PS/PDF) where available)	Lecturer
Week 36 - Focus on Program Analysis and High-Level Optimizations
Sep 01, 2014	13:15-16:30	Knuth	Introduction. (PDF) Multi-level intermediate representations. Principles of code generation, stack organisation and call sequences, local common subexpression elimination, DAGs, lowering. (PDF)	C. Kessler
Sep 02, 2014	09:15-10:45	Knuth	Control flow analysis	C. Kessler
Sep 02, 2014	11:00-11:45	Knuth	Lab introduction: LLVM Compiler Framework. Lab part 1, part 2	Erik Hansson
Sep 02, 2014	13:15-16:00	Knuth	Data flow analysis	C. Kessler
Sep 03, 2014	09:15-10:00	Knuth	Lesson 1: Control and data flow analysis	Erik Hansson
Sep 03, 2014	10:15-12:00	Knuth	Abstract interpretation. (PDF) (upd. 10/9)	Welf Löwe
Sep 03, 2014	13:15-16:00	Knuth	Interprocedural Analysis. Points-to Analysis. (PDF) (upd. 10/9)	Welf Löwe
Sep 04, 2014	09:15-12:00	Knuth	Dependence analysis, loop transformations, loop parallelization (PDF).	C. Kessler
Sep 04, 2014	13:15-16:00	Donald Knuth	Worst-case execution time analysis (PDF, updated 5/9)	S. Chattopadhyay
Sep 05, 2014	09:15-12:00	Knuth	Worst-case execution time analysis (cont.)	S. Chattopadhyay
Week 37 - Focus on SSA, Low-level Optimizations and Code Generation
Sep 08, 2014	13:15-14:00	Knuth	Lesson 1 (cont.): Data flow analysis	Erik Hansson
Sep 08, 2014	14:15-16:30	Knuth	Instruction selection (PDF) Register allocation (PDF)	C. Kessler
Sep 08, 2014	16:30-17:00	Knuth	Distribution of papers for student presentations.	C. Kessler
Sep 09, 2014	09:15-10:45	Knuth	Instruction scheduling (PDF).	C. Kessler
Sep 09, 2014	11:00-11:45	Knuth	Lesson 2: Dependence analysis and loop transformations	Erik Hansson
Sep 09, 2014	13:15-15:45	Knuth	Side note: Space-optimal scheduling for trees (PDF) Software pipelining (PDF)	C. Kessler
Sep 09, 2014	16:00-17:00	Knuth	Code generation for embedded processors, DSP processors, clustered VLIW architectures (PDF).	C. Kessler
Sep 10, 2014	09:15-10:00	Knuth	Lesson 3: Instruction scheduling, software pipelining	Erik Hansson
Sep 10, 2014	10:15-12:00	Knuth	SSA, construction and destruction, Memory SSA (PDF)	W. Löwe
Sep 10, 2014	13:15-17:00	Knuth	SSA based optimizations; Chi functions in lazy memory SSA based analysis (PDF)	W. Löwe
Sep 11, 2014	09:15-11:00	Knuth	Run-time parallelization and speculative parallelization (PDF) Auto-tuning (PDF)	C. Kessler
Sep 11, 2014	11:15-12:00	Knuth	Integrated code generation (PDF)	C. Kessler
Week 40:
Sep 29, 2014	09:15-...	Knuth	Student presentations	C. Kessler
Week 41:
Oct 1017, 2014	13:00-17:00	Knuth	Written exam (TEN1), Linköping	C. Kessler

Organization
Lectures, lessons, programming labs, a written assignment, and student paper presentations.

Lectures are given in 2 intensive weeks, usually 09:15-12 and 13:15-17 every day.

Lessons are problem solving sessions, discussing exercises to complement the lectures. The lessons are moderated by the course assistant, Erik Hansson. The exercise sets are available here.

Lab series (3hp) using the LLVM compiler system.
Lab introduction slides
Lab instructions, part 1.
Lab instructions, part 2.

The lab assistant, Erik Hansson, will supervise labs and correct lab reports.

The presentation part of the course consists of student presentations of about 30 minutes each (25 minutes presentation plus 5 minutes questions) on a recent paper in compiler technology, with a written summary of 1-2 pages. It also includes opposition of one other presentation.
See this link for detailed instructions and the list of assigned student papers.
For admission to the presentation it is required that at least 50% of the lectures and lessons have been attended.

Written exam: prel. friday 1017/10, 13-17. Room: Knuth, IDA, Linköping.
For participants from other sites: Contact the examiner in time if you intend to write the exam at your home university, and give the contact data of a teacher who will supervise your exam there.
No aids are allowed, except for a dictionary from English to your native language. Last admission time is 14:30.
For admission to the exam it is required that at least 50% of the lectures and lessons have been attended.

Old exams:
Part 1 (PDF), Part 2 (PDF), Solution proposal part 2 (PDF)

Literature
You should be able to follow the course mainly based on the slide material only. The following books and papers are recommended as additional reading wherever necessary:

Books:

No textbook covers the entire course contents completely. But parts of either of the following books and articles can be useful as accompanying text for a major part of the course (these are also available in the local library):

• Alfred Aho, Monica Lam, Ravi Sethi, Jeffrey Ullman: Compilers: Principles, Techniques, and Tools. Second edition, Addison-Wesley, 2006.
  The course book of the undergraduate compiler course. If you already have it, use it.
• Steven Muchnick: Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. (Quite expensive, but recommended reading. Kvartersbibliotek B has 2 copies (kursref).)
  Errata for early printings
• alternatively: Keith Cooper, Linda Torczon: Engineering a Compiler. Morgan Kaufmann, 2003.
• Y.N. Srikant, P. Shankar (ed.): The compiler design handbook: optimizations and machine code generation, CRC Press, 2003.
  (Available in the Campus Valla library, also the first edition..
  More complete and more up to date than Muchnick's book, but a collection of independent chapters rather than a monograph, and expensive.)
  In particular, chapters 1 (WCET/WCEE analysis, using e.g. abstract interpretation techniques), 5 (Optimizations for memory hierarchy), 7 (Energy-aware compiler optimizations), 11 (SSA form), 16 (ADLs for retargetable compiling), 17 (Instruction selection), 18 (DSP VLIW compiler), 19 (Instruction scheduling), 20 (Software pipelining). The first edition contains a chapter on dataflow analysis.
• Fisher, Faraboschi, Young: Embedded Computing - A VLIW Approach to Architecture, Compilers, and Tools. Morgan Kaufmann, 2005.
  Available in the Campus-Valla library.

Papers:

• C. Kessler: Compiling for VLIW DSPs. Book chapter in the Handbook of Signal Processing Systems 2010. Preprint, 38 pages, handed out to registered students.
• David Bacon, Susan Graham, Oliver Sharp: Compiler Transformations for High-Performance Computing. ACM Computing Surveys, December 1994, Volume 26 Issue 4. preprint
• David A. Padua and Michael J. Wolfe:
  Advanced compiler optimizations for supercomputers.
  Comm. ACM 29(12), Dec. 1986.
• Vicki Allan et al.: Software Pipelining. ACM Computing Surveys 27(3): 367-432, Sept. 1995.
  (Chapter 18 of Srikant's book contains a short version of this article.)
• R. Wilhelm et al.: The worst-case execution time problem - overview of methods and survey tools. ACM Trans. on Embedded Computing Systems, 2008

Further background reading:

• Randy Allen, Ken Kennedy: Optimizing compilers for modern architectures. Morgan Kaufmann, 2002. (Covers e.g. dependence analysis, loop optimizations, cache optimizations, parallelization, interprocedural analysis and optimization.)
• Michael Scott: Programming Language Pragmatics. Morgan Kaufmann, 2000. (Excellent summary of concepts in programming languages and their implementation in compilers. Chapter 13 gives a summary of code optimization.)
• Joseph A. Fisher, Paolo Faraboschi, Cliff Young: Embedded Computing - A VLIW Approach to Architecture, Compilers, and Tools. Morgan Kaufmann, 2005.
• Peter Marwedel, Gert Goossens (Eds.): Code Generation for Embedded Processors. Kluwer International Series in Engineering and Computer Science, 1995.
• Rainer Leupers: Retargetable Code Generation for Digital Signal Processors. Kluwer, 1997. (Available in Kvartersbibliotek B.)
• Rainer Leupers: Code Optimization Techniques for Embedded Processors. Kluwer, 2000. (Available in Kvartersbibliotek B.)
• Hennessy, Patterson: Computer Architecture, a Quantitative Approach, Third Edition. Morgan Kaufmann, 2003. (Chapter 4 gives an overview of compiler optimizations for ILP.)

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)

Teachers
Christoph Kessler (course leader)
Welf Löwe (guest lecturer)
S. Chattopadhyay (guest lecturer)
Erik Hansson (course assistant)

Examiner
Christoph Kessler
Welf Löwe (guest examiner)

Examination
TEN1: Written or oral exam, 4.5hp (date see schedule).
No aids are allowed.
In the case of a written exam, remote exams are possible.

Admission to the exam requires physical presence in at least 50% of all lectures and lessons.
Passing the exam is mandatory for getting any credit points on the course.

LAB2: Compiler framework lab with written report 3hp (course assistant: Erik Hansson) Deadline: 5 october 2014

PRE1: Presentation, opposition and written summary 1.5hp (Christoph) Deadline (summary): 19 october 2014
For admission to the presentation it is required that at least 50% of the lectures and lessons have been attended.

Credit
Up to 9hp for the entire course, provided that the written exam is passed.
Admission to the exam and presentation requires physical presence in at least 50% of all lectures and lessons.

Note: Those who pass the course but are not IDA graduate students receive a paper certificate (intyg) about their result. For potential acceptance of the credits for undergraduate education programs please contact your responsible program coordinator (grundutbildningsledare) and show him/her your certificate.

Comments
CUGS Advanced Graduate Course

This page is maintained by Christoph Kessler (chrke \at ida \dot liu \dot se)