Set-Based Analysis
Program Analysis
The purpose of program analysis is to find out
information about a program's run-time behavior. One of the main applications of
program analysis is in compiler optimization. The idea of approximating program
behaviour is central to program analysis because, for pragmatic and theoretical
reasons, programs cannot be analyzed exactly.
The Set-Based Approach
In set-based analysis (SBA), programs are
approximated using a very simple abstraction: programs variables are viewed as
sets of values. In essence, this corresponds to ignoring inter-variable
dependencies, but making no approximation of the underlying space of values. SBA
provides an intuitive, abstract and non-algorithmic view of what the analysis
will achieve, in combination with an accurate and uniform treatment of
data-structures.
While SBA can be formulated as an abstract interpretation in a
straightforward way, the corresponding iterative fixpoint computation does not
usually terminate (the sets generated by a set-based approximation are typically
infinite). Instead, new algorithmic techniques are needed to reason directly
about (arbitrary) sets of values. This has motivated the developed the calculus
of set constraints.
Some SBA Papers
Some Related Papers
nch@agere.com