Data Flow Analysis for Procedural Languages
Barry K. Rosen · Journal of the ACM · 1979
Global analysis and optimization techniques presuppose local data flow information about the effects of program statements on the values associated wRh names For procedure calls this information is not immediately available but can presumably be obtained through flow analysis of procedure bodies Accurate mformatlon proves to be surprisingly difficult to obtain This paper includes a language independent formulation of the problem, an interprocedural data flow algorithm, and a proof that the algorithm is correct Symbohc data flow analysis is introduced in the course of optimizing the algorithm We move much of the work outside of a loop by manipulating partially evaluated symbolic expressions for the data within the loop Foundational difficulties are revealed when the theory of data flow analysis is extended to support extensive optimization of procedural language programs Several widespread assumptions become false or ambiguous A few of the problems are resolved here Inductive arguments are facilitated by a simple path tree representation of control flow that allows for both recurslon and side effects
Cited by 70 works. doi:10.1145/322123.322135 Open-access PDF
Authors
References
- A contribution to the development of ALGOL
- Object code optimization
- Global common subexpression elimination
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- Tree-Manipulating Systems and Church-Rosser Theorems
- Data Flow Analysis in Software Reliability
- Global Data Flow Analysis and Iterative Algorithms
- A global flow analysis algorithm
- Fast algorithms for the elimination of common subexpressions
- A Simple Algorithm for Global Data Flow Analysis Problems