Interprocedural Control Flow Analysis (Extended version)

Abstract

Control Flow Analysis is a widely used approach for analysing functional and object oriented programs and recently it has also successfully been used to analyse more challenging notions of computation involving concurrency. However, once the applications become more demanding also the analysis needs to be more precise in its ability to deal with mutable state (or side-effects) and to perform polyvariant (or context-sensitive) analysis. Several insights in Data Flow Analysis and Abstract Interpretation show how to do so for imperative programs but the techniques have not had much impact on Control Flow Analysis because of the less abstract way in which the techniques are normally expressed. In this paper we show how to incorporate a number of key insights from Data Flow Analysis involving such advanced interprocedural techniques as call strings and assumption sets using Abstract Interpretation to induce the analyses from a general collecting semantics.