An interprocedural data flow analysis algorithm
Jeffrey M. Barth · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · 1977
A new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on the procedure, and all of it subcalls. The algorithm is sufficiently powerful to be used on recursive programs and to deal with the sharing of variables which arises through reference parameters. The algorithm is unique in that it can compute all of this information in a single pass, not requiring a prepass to compute calling relationships or sharing patterns. A lower bound for the computational complexity of gathering interprocedural data flow information is derived and the algorithm is shown to be asymptotically optimal. The algorithm has been implemented and it is practical for use even on quite large programs.
Cited by 41 works. doi:10.1145/512950.512962 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Revised report on the algorithmic language ALGOL 60
- PASCAL User Manual and Report
- Compiler construction for digital computers
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- Interprocedural Data Flow Analysis.
- Solving path problems on directed graphs.
- Analysis of a simple algorithm global data flow problems
- Exposing Side-Effects in a PL/I Optimizing Compiler.
- Data Flow Analysis in the Presence of Procedure Calls