Program Optimization

The lecture starts with basic dataflow analyses like availability of expressions or liveness of variables together with the optimizing transformations enabled by these analyses. Motivated by the examples, we develop the theoretical background on complete lattices and monotone functions necessary for program analysis methods. Subsequently, we discuss more sophisticated analyses such as constant propagation. By discussing interval analysis, we present general methods for the case where ordinary fixpoint computation will not terminate. Further topics are:

• interprocedural analysis;
• pointer analysis;
• fixpoint algorithms. We also consider hardware dependent optimizations such as:
• register allocation;
• instruction selection;
• instruction scheduling and also optimizations to improve the cache behavior.

Participants know the often occurring conflict between good structure and readability of a program as well as the highest possible efficiency of the execution of the program which is likewise desired. They know the techniques to increase the efficiency of the program execution through optimizing transformations of a compiler. They are able to apply these to small example programs and are able to develop new analyses and optimizations on their own.

The assessment is by means of a written exam of 120 minutes. Some assignments offer small problems from the area of lattice theory by which students may demonstrate how well they are acquainted with basic concepts of program analysis and in how far they are able to apply these concepts in an original way. Other assignments evaluate how well students are able to apply the learnt analyses and transformations to small example programs. Further assignments ask to develop new analyses and optimizations. The successful completion of homework asignments may contribute to the grade as a bonus. The exact details for this are timely announced at the beginning of the lecture.

Bachelor Informatics, basic knowledge in programming languages or compilers

• Seidl, Wilhelm, Hack: Compiler Design. Analysis and Transformation. Springer Verlag, 2012

By means of a presentation, either by slides or whiteboard, the lecture presents fundamental techniques for the analysis and optimization of programs and illustrates these by means of small examples. Accompanying assignments for individual study deepen the understanding of the concepts explained in the lecture, train students to apply the learnt analyses and optimizations to example programs and develop the skill to realize analyses and optimizations on their own.