DF00100 Advanced Compiler Construction
(PhD course, 9hp, spring 2021)
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
Lectures, lessons, lab introduction: 2 intensive weeks (weeks 6 and 7).
In spring 2021, due to the pandemic restrictions, the course will be given entirely on distance via zoom.
The preliminary schedule is given below. Slides may be updated shortly before/after each lecture.
Date | Time | Location | Topic (with links to slides (PS/PDF) where available) | Lecturer |
Week 6 - Focus on Program Analysis and High-Level Optimizations | ||||
Tuesday 09/2/2021 | 09:15-12:00 | Zoom | Introduction. (PDF) Multi-level intermediate representations. Principles of code generation, stack organisation and call sequences, local common subexpression elimination, DAGs, lowering. (PDF) |
Christoph Kessler |
09/2/2021 | 13:15-14:00 | Zoom |
Lab introduction: LLVM Compiler Framework. Lab part 1, Lab part 2 |
August Ernstsson |
09/2/2021 | 14:15-16:00 | Zoom | Control flow analysis (PDF) | Christoph Kessler |
Wednesday 10/2/2021 | 09:15-12:00 | Zoom | Data flow analysis (PDF) | Christoph Kessler |
10/2/2021 | 15:15-17:00 | Zoom | Abstract interpretation. (PDF) | Welf Löwe |
Thursday 11/2/2021 | 09:15-12:00 | Zoom | Interprocedural Analysis. Points-to Analysis. (PDF) | Welf Löwe |
11/2/2021 | 13:15-14:00 | Zoom | Lesson 1: Control and data flow analysis | Christoph Kessler |
11/2/2021 | (time slot reserved for SaS staff meeting) | - | ||
Friday 12/2/2021 | 09:15-12:00 | Zoom | Dependence analysis, loop transformations, loop parallelization (PDF) | Christoph Kessler |
12/2/2021 | 13:15-14:00 | Zoom | Reserve time slot for continuation of Lesson 1 | Christoph Kessler |
12/2/2021 | 15:15-17:00 | Zoom | Guest lecture: The Open-source Modelica Compiler (PDF) | Martin Sjölund |
Week 7 - Focus on SSA, Low-level Optimizations and Code Generation | ||||
Monday 15/2/2021 | 13:15-16:00 | Zoom | Instruction selection (PDF) Register allocation (PDF) |
Christoph Kessler |
Tuesday 16/2/2021 | 09:15-12:00 | Zoom | Instruction scheduling (PDF). Side note: Space-optimal scheduling for trees (PDF, for self-study) Software pipelining (PDF) |
Christoph Kessler |
16/2/2021 | 13:15-14:00 | Zoom | Lesson 2: Dependence analysis and loop transformations | August Ernstsson |
16/2/2021 | 14:15-16:00 | Zoom | Code generation for embedded processors, DSP processors,
clustered VLIW architectures.
(PDF, only partly covered). Integrated code generation (PDF) |
Christoph Kessler |
Wednesday 17/2/2021 | 09:15-11:00 | Zoom | Selected advanced topics: Compilation for actors and stream computing: task fusion, scheduling, mapping, DVFS (MP4 recorded lecture 25min, watch off-line) Data transfer fusion optimization (PDF); Auto-tuning (PDF) |
Christoph Kessler |
17/2/2021 | 11:15-12:00 | Zoom | Lesson 3: Instruction scheduling, software pipelining | August Ernstsson |
Wednesday 17/2/2021 | 13:15-16:00 | Zoom | SSA, construction and destruction, Memory SSA. SSA-based optimizations. (PDF) | Welf Löwe |
Thursday 18/2/2021 | 09:15-12:00 | Zoom | More SSA based optimizations; Chi functions in lazy memory SSA based analysis (PDF) | Welf Löwe |
18/2/2021 | 12:15-13:00 | Zoom | Assignment of papers for student presentations. | Christoph Kessler |
Week 12: | ||||
24/3/2021 | 09:00-10:00 | Zoom | Guest lecture; | |
24/3/2021 | 10:00-17:00 | Zoom | Student presentations | |
Week 13: | ||||
31/3/2021 | 09:00-13:00 | Zoom | Written/oral exam (TEN1) | Christoph Kessler |
Organization
Lectures, lessons, compiler framework programming labs, and student presentations of compiler research papers.
Lectures are, where possible, given in 2 intensive weeks, usually 09:15-12:00 and 13:15-16:00 every day.
Lessons are problem solving sessions, discussing exercises to complement the lectures. The exercise sets are available here.
Lab series (3hp) using the LLVM compiler system.
Lab introduction (2021)
Lab instructions, part 1 (2021)
Lab instructions, part 2 (2021).
The lab assistant,
August Ernstsson,
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 selected/assigned student papers.
For admission to the presentation it is required
that at least 50% of the lectures and lessons have been attended.
Written/oral exam: prel. wednesday 31/3, 09-13, on distance. Room: Zoom.
No aids are allowed, except for a dictionary from English
to your native language.
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.
The LiU TekNat library has 2 copies.)
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 LiU TekNat 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 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.
- C. Kessler: Compiling for VLIW DSPs. Book chapter in the Handbook of Signal Processing Systems, Third edition, 2019. 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.
-
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.) - Christoph Kessler, Sebastian Litzinger, Jörg Keller:
Static Scheduling of Moldable Streaming Tasks with Task Fusion for Parallel Systems with DVFS.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) 39(11), pages 4166-4178, Nov. 2020.
DOI: 10.1109/TCAD.2020.3013054
- Christoph Kessler: Global Optimization of Operand Transfer Fusion in Heterogeneous Computing. Proc. 22nd International Workshop on Software and Compilers for Embedded Systems (SCOPES-2019), St. Goar, Germany, May 2019. ACM. DOI: 10.1145/3323439.3323981
- 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.
Available in the LiU TekNat library. - 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.)
- Short introduction to SSA (slide set)
Christoph Kessler (course leader)
Welf Löwe (guest lecturer)
Martin Sjölund (guest lecturer)
August Ernstsson (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.
Admission to the exam requires 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: August Ernstsson) Deadline: 6 April 2021
- PRE1:
Paper presentation, opposition and written summary 1.5hp (Christoph)
Deadline (summary): 6 April 2021
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 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 about their result. For potential acceptance of the certificate towards other graduate education programs please contact your program coordinator before joining the course.
Comments
This has been a CUGS Advanced Graduate Course 2002-2014.
The course is usually offered every other year.
It is not open to undergraduate students.
This page is maintained by Christoph Kessler
Page responsible: Webmaster
Last updated: 2021-03-23