Program Analysis

Instructor: Shmuel (Mooly) Sagiv
Assistant: Noam Rinetzky
Thursday 15-18
Scriber 08

Advanced techniques for statically analyzing programs are discussed. These techniques allow 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 POWER POINT does not show certain mathematical characters use
fonts in a zip file, by clicking here. Make sure to extract
them to the appropriate directory, that is :

- C:\windows\Fonts - If you're on Win 9x
- C:\Winnt\fonts - If you're on NT

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

Examples
Course Requirements
Bibliography
Sample class notes
Schedule
Homework assignments

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).