Set Based Program Analysis
Abstract
The central component of standard approaches to compile-time program analysis is an abstract domain for approximating program values. Importantly, the domain must be chosen so that an iterative fixed point computation over the domain terminates. This requirement represents a substantial restriction on the accuracy of the analysis. Furthermore, it leads to complex and often chaotic behavior. We present an alternative approach to program analysis, called set based analysis. A key feature of set based analysis is that reasoning about a program's run-time behavior is reduced to reasoning about constraints on sets of program values. Set based analysis incorporates just a single notion of approximation: all dependencies arising from the treatment of program variables are ignored. The main advantage of set based analysis is improved accuracy, due to the absence of an abstract domain. Additionally, the use of a very simple and uniform notion of approximation leads to program analysis that is easier to understand and less sensitive to minor program modifications.... Compiler optimization, Program analysis, Dataflow anal Abstract interpretation, Set constraints, Tree automata, Regular term languages, Operational semantics, Program approximation, Types, Logic programming, Functional programming, Imperative programming, collecting semantics, Environment constraints.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1992
- Accession Number
- ADA260979
Entities
People
- Nevin Heintze
Organizations
- Carnegie Mellon University