Accession Number : ADA260979


Title :   Set Based Program Analysis


Descriptive Note : Doctoral thesis,


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE


Personal Author(s) : Heintze, Nevin


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a260979.pdf


Report Date : Oct 1992


Pagination or Media Count : 373


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.


Descriptors :   *SYSTEMS APPROACH , *COMPUTER PROGRAM VERIFICATION , *COMPILERS , REQUIREMENTS , OPTIMIZATION , COMPUTATIONS , ENVIRONMENTS , MODIFICATION , REASONING , COMPUTER PROGRAMMING , BEHAVIOR , AUTOMATA , LOGIC , VALUE , SEMANTICS , ACCURACY , THESES , PROTOTYPES , TIME , VARIABLES , STANDARDS


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE