Optimal Data Flow Analysis via Observational Equivalence

Bernhard Steffen

Abstract: In [18] a three level model was presented to establish a concept of completeness or optimality for data flow analysis algorithms in the framework of abstract interpretation [2]. The notion of observational equivalence which we introduce here generalizes the idea of the three level model, which can only deal with hierarchies of abstract interpretations. Investigating this more general notion, it actually turns out that the three level model is general in a theoretical sense: it determines the most abstract computation level which delivers complete results. However, consideration of other aspects of data flow analysis profit from the extra generality of our observation directed approach. For example the completeness or optimality proof for a ``real life'' optimizer could be shortened significantly this way.


Previous | Index | Next