Program Analysis
Shmuel (Mooly) Sagiv
>
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
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
TBA
- Course
Overview
Class Notes by Moria Abadi and Priel Levy
Original Powerpoint
- Operational Semantics (Revised)
Class Notes by Itay Rosenblatt and Eylon Yogev
Original Powerpoint
- Iterative Dataflow Analysis (Part 1)
Class Notes by Ghila Castelnuovo and Ohad Shacham
Original Powerpoint
- Iterative Dataflow Analysis (Part 2) Mathematical Background
Class Notes by by Omer Tripp and Guy Ilany
Original Powerpoint
- Abstract Interpretation
Class Notes by Yaron Koral and Hila Peleg
Original Powerpoint
- Applications
of Abstract Interpretation
Class Notes by Yorai Geffen and Barak Itkin
Original
Powerpoint
- Precision of Abstract Interpretation
Class Notes by Jenny Falkovich and Dekel Cohen
Original
Powerpoint
-
Interprocedural Analysis
Original
Powerpoint
Class Notes by Amit Perelstein & Hen Amar
-
String Analysis
Original
Powerpoint
Class Notes by Ariel Jarovsky and Liron Schiff
-
Shape Analysis
Original
Powerpoint
Class Notes by Eran Kravitz & Oren Zomer
- Typestate Verification by Eran Yahav
Original
Powerpoint
- Counter Example Guided Refinement
Original Powerpoint
BLAST Page
Homework Assignments
For
further information Email:msagiv@post.tau.ac.il