Lehrstuhl Informatik II   
Sprachen und Beschreibungsstrukturen      
   Home Lehre Wintersemester 17/18 Vorlesungen Program Optimization login

Program Optimization

Dozent:Prof. Dr. Helmut Seidl
Ort/Zeit:Room: 00.13.009A; Lecture: Mon. 12:15-13:45, Wed. 10:00-11:30, Exercises: Thu. 10:00-12:00,
ModulNummer:IN2053
Beschreibung:    This course is about standard techniques used to optimize general purpose programming languages. How to avoid redundant computation, replace expensive computations with cheaper ones, and/or exploit hardware.

Announcements

  • no exercise session on Thursday 07.12.2017
  • no lecture on Monday, 13.11.2017; small lecture + exercise session on Wednesday 15.11.2017; lecture (instead of exercise session) on Thursday 16.11.2017
  • The list of projects is available here: projects.txt
  • At the exam, the only allowed auxiliary material is a (double-sided) A4 cheat sheet.
  • The repetition exam takes place on 27.03.2018, 10:30-12:30, in room Hans-Fischer-Hörsaal, CH21010 (room code: 5401.01.101K). The registration period is 05-19.03.2018.

Overview

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

Lectures

Slides

Exercises

If you have any questions regarding organization or content of the exercises, please contact Eugen Zalinescu (eugen.zalinescu@in.tum.de).

# Date Keywords Sheet Solutions Remarks
01 19.10.2017 Simple imperative language, CFGs, semantics 01.pdf 01sol.pdf  
02 26.10.2017 Constraint systems, lattice theory 02.pdf 02sol.pdf  
03 02.11.2017 Round-Robin, MOP, distributive functions 03.pdf 03sol.pdf  
04 09.11.2017 (True) liveness, monotonic analysis framework 04.pdf 04sol.pdf  
05 15.11.2017 Superfluous moves, transformations 1-3 05.pdf 05sol.pdf  
06 23.11.2017 Constant propagation, interval analysis 06.pdf 06sol.pdf  
07 30.11.2017 Alias analysis, worklist algorithm 07.pdf 07sol.pdf  
08 14.12.2017 Copy-constant analysis, Sharir/Pnueli-Cousot 08.pdf 08sol.pdf  
09 21.12.2017 Call string approach, SSA form 09.pdf 09sol.pdf updated: more detailed solution for ex.1
10 11.01.2018 SSA form, VLIWs, Difference Constraints 10.pdf 10sol.pdf  
11 18.01.2018 Omega Test, Loop bounds, Presburger Arithmetic 11.pdf 11sol.pdf  
12 25.01.2018 Inlining, deforestation, strictness analysis 12.pdf 12sol.pdf  
13 01.02.2018 Top/Total strictness analysis, BDDs 13.pdf 13sol.pdf  

Bibliography



TUM - Lehrstuhl Informatik II (Sprachen und Beschreibungsstrukturen) Thanks: Tango and TinyMCE     Generationszeit: 9 ms