Data Flow Analysis Frameworks for Concurrent Programs

Data flow analysis is a well studied family of static program analyses. A rich theoretical basis for data flow analysis has been developed. Central to this theory is the concept of data flow framework. These frameworks are a semantically well-founded formalism for specifying a data flow analysis. A variety of solution algorithms for problems specified as data flow frameworks have been developed. The bulk of the research on data flow analysis has been done in the context of analysis of sequential programs. Unfortunately, a number of important assumptions of this work are violated when we apply data flow analysis results to concurrent programs. In this paper, we extend data flow frameworks for sequential program analysis to accommodate concurrent programs. We present solution algorithms for these extended frameworks and reason about their convergence and complexity. 1 This work was supported by the Advanced Research Projects Agency under Grant F30602-94-C-0137. 1 Introduction Data f..