Program Analysis
Shmuel (Mooly) Sagiv
Thursday 16-19 Orenshtein 111
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 POWERPOMT 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
Contents
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.
Course Schedule
10. August 8 16-19 Scriber 309, Concurrent Programs
Homework Assignments
For
further information Email:msagiv@post.tau.ac.il