Set-Based Program Analysis (Extended Abstract)

) Nevin Heintze and Joxan Jaffar y 1 January 1991 Summary Program analysis involves approximating the semantics of programs. One important kind of approximation, that of ignoring intervariable dependencies, is widely used for reasons of decidability and efficiency. This paper addresses program analysis wherein ignoring intervariable dependencies is the only kind of approximation used. Starting with the collecting semantics of a program, it is shown that there is a natural formalization of this approximation in which program variables are associated with sets of values. Further, this formalization is applicable to both the imperative and logic programming paradigms. An algorithm is then presented which inputs an imperative or logic program and constructs an explicit representation of its approximate semantics. It therefore provides the most accurate analysis possible, given that intervariables dependencies are ignored during analysis. School of Computer Science, Carnegie Mellon ..