1995 | Thomas Reps, Susan Horwitz, and Moovy Sagiv
The paper presents a method to solve a broad class of interprocedural dataflow analysis problems in polynomial time by transforming them into graph reachability problems. The key restrictions are that the set of dataflow facts must be finite, and the dataflow functions must distribute over the confluence operator (union or intersection). This approach includes classical separable problems like reaching definitions, available expressions, and live variables, as well as non-separable problems such as truly-live variables, copy constant propagation, and possibly-uninitialized variables. The authors introduce the IFDS (Interprocedural, Finite, Distributive, Subset) framework, which generalizes Sharir and Pnueli's "functional approach" and handles programs with procedure calls, parameters, and both global and local variables. They demonstrate how to represent distributive functions compactly and convert IFDS problems into realizable-path reachability problems in an exploded supergraph. The Tabulation Algorithm, a dynamic programming approach, is presented to solve these reachability problems efficiently. Preliminary experimental results show that the Tabulation Algorithm is accurate and cost-effective for the possibly-uninitialized variables problem. The paper also discusses related work, including previous interprocedural dataflow analysis frameworks, pointwise computation of fixed points, flow-sensitive side-effect analysis, demand algorithms, and the IDE framework.The paper presents a method to solve a broad class of interprocedural dataflow analysis problems in polynomial time by transforming them into graph reachability problems. The key restrictions are that the set of dataflow facts must be finite, and the dataflow functions must distribute over the confluence operator (union or intersection). This approach includes classical separable problems like reaching definitions, available expressions, and live variables, as well as non-separable problems such as truly-live variables, copy constant propagation, and possibly-uninitialized variables. The authors introduce the IFDS (Interprocedural, Finite, Distributive, Subset) framework, which generalizes Sharir and Pnueli's "functional approach" and handles programs with procedure calls, parameters, and both global and local variables. They demonstrate how to represent distributive functions compactly and convert IFDS problems into realizable-path reachability problems in an exploded supergraph. The Tabulation Algorithm, a dynamic programming approach, is presented to solve these reachability problems efficiently. Preliminary experimental results show that the Tabulation Algorithm is accurate and cost-effective for the possibly-uninitialized variables problem. The paper also discusses related work, including previous interprocedural dataflow analysis frameworks, pointwise computation of fixed points, flow-sensitive side-effect analysis, demand algorithms, and the IDE framework.