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

TimeTopic
10:30Loop unrolling, bounds detection and constant propagation
11:00Function inlining, unrolling for recursive functions and tail-call optimization
11:30-12:15Lunch break
12:15Software pipelining
12:45Dynamic calls
13:15Interval Analysis with the interval set domain
13:45SSA 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.