Complexity of Data Flow Analysis for Non-Separable Frameworks

Abstract — The complexity of round robin iterative data flow analysis has been traditionally defined as 1 + d where d is the depth of a control flow graph. However, this bound is restricted to bit vector frameworks, which by definition, are separable. For non-separable frameworks, the complexity of analysis is influenced by the interdependences of program entities, hence the bound of 1 + d is not applicable. This motivates the need for capturing the interdependences of entities to define a general complexity measure. We propose Degree of dependence δ which quantifies the effect of non-separability on the complexity of analysis for a particular problem instance. We define the complexity bound of 1 + δ + d which explains the complexity of round robin analysis of general nonseparable data flow problems. Like d, δ is a theoretical concept useful for understanding the complexity rather than estimating it. In bit vector frameworks the bound 1 + δ + d reduces to 1 + d due to δ = 0. Apart from being general, our bound is also precise, as corroborated by empirical results. Index Terms — Data flow analysis, Complexity, Constant propagatio