Program Analysis

Shmuel (Mooly) Sagiv Wed 9-12

Advanced techniques for statically analyzing programs are discussed. These techniques allows one to answer computationally hard questions about programs in an efficient albeit conservative way. They are also referred to as abstract interpretation since the algorithms interpret the program on a simplified abstract domain. The techniques are useful in compilers in order to generate more efficient code and in other programming language environments such as debuggers and code quality checkers.

For an interesting note on static analysis click here.

Important Message

If your POWERPOINT does not show certain mathematical characters use fonts in a zip file, by clicking here. Make sure to extract
them to the appropriate directory,

Alternatively, you can extract them anywhere, and install them via the control panel

Examples
Course Requirements
Bibliography
Schedule
Homework assignments
Home Exam

Example Program Analysis Problems

Constant Propagation: Determine if a variable always has a constant value at a point in a program (Click here to see example programs and their constants). Compilers can improve the running time of the generated code by evaluating constants at compile time. Constant propagation algorithms are also used to guide other compiler optimizations.
May be Uninitialized: Determine if a variable may be used in the program before an initialization. Debugging tools such as the Unix lint report the variables which may be uninitialized.
Strictness Analysis: An analysis that allows the optimization of lazy functional programs by identifying the parameters that can be passed by value thus avoiding the need to build closures and opening up opportunities for parallel evaluation.
In-Line Update Analysis: This analysis allows us to determine the points in the program at which it is safe to destroy a data object because there are no longer references to it. A notable result by Hudak, is that, for the first time, a functional version of the quicksort algorithm can be made to run in linear space using this analysis.
Mode Analysis: Significant performance can be achieved in PROLOG interpreters if it is known how the logical variables are used in a relation (i.e., as input or output variables or a mixture of the two).

Course Requirements

Prepare course notes 15%
Theoretical assignments 35%
Final exam 50%

Bibliography

The course book Principles of Program Analysis by Nielson, Nielson and Hankin is available in Dionon.

Python Implementation of Chaotic Iterations

Course Schedule

Homework Assignments

Sample Exams

Last year

For further information Email:msagiv@post.tau.ac.il