The students gain a comprehensive understanding of the theoretical
foundations and practical applications of program analysis and
optimization in compiler construction. They learn to valuate the
potential and limitations of automatic analyses and
optimizations. Beyond applications in compiler construction, this
allows them to design and write software in a style that, where
possible, comprehensibility, maintainability, and robustness is
prioritized over unnecessary performance considerations.

The course is concerned with the theory and practice of program
analysis and optimization, which is an essential field of research in
the area of programming languages and compilers. The course stretches
from the theoretical foundations to practical applications and the
automatic generation of program analyses and
optimizations. Theoretical and practical assignments as part of the
tutorial offer the opportunity to independently apply and practice
various analysis and optimization techniques, to prove properties they
meet, and to gain hands-on experience of the SATIrE tool used for
practical assignments. SATIrE integrates various tools for the
analysis and optimization of object-oriented languages, among these
the Program Analyzer Generator (PAG).

The course considers in particular the following topics and their
realization by means of SATIrE:

• Foundations and applications of program analysis and optimization
• Data-flow analysis (forward, backward, existential, universal)
• Data-flow frameworks (intraprocedural, interprocedural)
• Machine-independent optimizations, in particular syntactic and semantic redundancy elimination
• Points-to, alias, and shape analysis
• Analysis and optimization of object-oriented programs
• Generators for analysis and optimization, especially SATIrE
• ...

In detail:

Part I: Introduction

• Motivation
• Classical Gen/Kill data flow analyses

Part II: Intraprocedural Data Flow Analysis

• Intraprocedural data flow analysis framework
• Gen/Kill data flow analyses revisited
• Constant propagation and folding
• Partial redundancy elimination (PRE)
• PRE: Busy code motion
• PRE: Lazy code motion
• PRE: Sparse code motion
• PRE: Summary, looking ahead

Part III: Interprocedural Data Flow Analysis

• Foundations
• Interprocedural data flow analysis framework
• The functional approach
• The context information approach
• Applications

Part IV: Extensions, other Settings

• Alias and heap analyses
• Optimizations for object-oriented languages

Part V: Conclusions

• Summary, looking ahead
  

References

Appendices

• Mathematical foundations
• Flow graphs, pragmatics of representation
• Implementing busy and lazy code motion
• Lazy strength reduction

The preliminary course meeting and the first lecture take 
place on Tueday, 3 October 2017, 3.15 - 4.45 pm, in "Hörsaal GM7
Kleiner Schiffbau", Bauteil BD Hoftrakt (1st Floor), Room number BD01B41,
Getreidemarkt 9.

ECTS Break Down:

The course is assigned 3.0 ECTS points. This corresponds to an average
workload of 75 hours. This average workload is divided among the
various parts of the course as follows:

• Attending the lectures, pre- and post-processing: 35 hours.
• Assignments and excercise interviews: 35 hours.
• Preparation for the examination and oral examination: 5 hours.

Assessment of the programming assignments and the oral examination
on the lecture and tutorial materials. Further information on the
examination modalities are given on the homepage of the course.

The course extends the course 185.311 Compiler Construction and
complements the courses 185.274 Advanced Compiler Construction and
185.276 Analysis and Verification. The course is thus especially
recommended for students who would like to focus on the field of
programming languages and compilers, and plan to work on a project or
to write a seminar or master's thesis in this field.