| Speaker | Prof. Dr. Helmut Seidl |
| Location | MI 00.13.009A |
| Date | Wednesdays & Thursdays 10:00 - 12:00 |
| Module | IN2053 |
Contents
The lecture is meant for students doing Master studies who are interested in compiler technology.
Programs which we write should be both efficient and easily to maintain. In particular, maintainability means that programs should be well-structured and easily understandable also by humans. Being well-structured and easily readable, though, may often come at the price oft a degradation in efficiency at run-time.
For this reason, most compilers offer an optimization phase in which the source program is analyzed and where various transformations are applied to automatically improve efficiency. In some cases, it may happen that the attempt for improvement overshoots the target and results in programs which are perhaps fast but are no longer equivalent to the original program.
In the lecture, we give an overview over standard techniques for improving the quality of the generated code. In particular, we are interested in methods which guarantee that the resulting code still is equivalent to the source program.
The topics covered:
- Intra-procedural analysis and optimizations
- Abstract Interpretation and Interval Analysis
- Interprocedural optimizations
- Exploitation of hardware features such as registers, pipelines, caches, specific instructions
- Optimization of functional languages
- Optimization of Prolog
Last year slides
Exam
NEW: Repetition exam review will take place on Tuesday, April 30 16:15 - 17:15 in the room 02.07.034. You may also review your end-of-term exam, if you missed the appointment in March.
The written exam will take place on Tuesday, February 26, 10:30 - 12:30 in the hall 102, Interims Hörsaal 2. The only allowed auxiliary material is one A4 (double-sided) cheat sheet.
The repetition exam is on Friday, April 12, 10:30 - 12:30 in the lecture hall MW 1801, Ernst-Schmidt-Hörsaal. You can register for the re-exam between March 18 and April 1.
Exercises
Exercises take place on Wednesdays 12:30 - 14:00 in 02.07.014.
Please prepare the corresponding sheet below.
24.10. 01.pdf 01sol.pdf
31.10. 02.pdf 02sol.pdf
07.11. exercise sheet 2, ex. 2-4
14.11. 03.pdf 03sol.pdf
21.11. 04.pdf 04sol.pdf This exercise session is CANCELLED because of illness, apologies for a short notice. We will discuss the solutions/questions you had next week.
28.11. 05.pdf 05sol.pdf
06.12 15:00 06.pdf 06sol.pdf
12.12 07.pdf 07sol.pdf
19.12 08.pdf 08sol.pdf
09.01 09.pdf 09sol.pdf
16.01 10.pdf 10sol.pdf
23.01 11.pdf 11sol.pdf
30.01 12.pdf 12sol.pdf
06.02 13.pdf 13sol.pdf
13.02 Office hours. No new exercise sheet, please prepare your questions
If you have any questions regarding organization or content of the exercises, please contact Anastasiia Izycheva (izycheva@in.tum.de).
Projects
UPDATE: The presentations take place on March 7 starting at 10:30 am in the room 02.09.014. We planned the time until 14:15
@Project teams only: If you have a good reason why you can't make it for the presentations, please email Anastasiia Izycheva as soon as possible.
Students who are not involved in the projects are not required to attend the presentations.
For the implementation projects you can use a Java front-end for a very restricted C.
To get a grade bonus you will have to submit an artefact and present your project.
Presentation schedule
| Time | Topic |
|---|---|
| 10:30 | Loop unrolling, bounds detection and constant propagation |
| 11:00 | Function inlining, unrolling for recursive functions and tail-call optimization |
| 11:30-12:15 | Lunch break |
| 12:15 | Software pipelining |
| 12:45 | Dynamic calls |
| 13:15 | Interval Analysis with the interval set domain |
| 13:45 | SSA form |
List of projects
Talks:
- 1 person - Software pipelining
- 2 people - Polyhedral model and affine scheduling + any optimization based on the polyhedral model
- 3 people - PBQP talk + implementation + register allocation using PBQP
Implementations:
- 2 people - Loop unrolling + find loop bounds + constant propagation
- 2 people - Function inlining (different strategies - provide the call graph) + unroll for recursive functions + tail call optimization
- 2 people - Deal with dynamic calls:
- adaption of syntax/semantics
- analysis of functions (function pointers) residing in blocks
- extended call-graph construction
- extend Points-to analysis for function calls (pointers)
- 1 person - Interval Analysis with the interval set domain
- 2 people - SSA form
Bibliography
- Helmut Seidl, Reinhard Wilhelm and Sebastian Hack. Compiler Design - Analysis and Transformation. Springer, 2012.
- Helmut Seidl, Reinhard Wilhelm and Sebastian Hack. Übersetzerbau 3: Analyse und Transformation. Springer, 2010.