A precise inter-procedural data flow algorithm
Eugene Wimberly Myers · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1981
Data flow analysis is well understood at the intra-procedural level and efficient algorithms are available. When inter-procedural mechanisms such as recursion, procedure nesting, and pass-by-reference aliasing are introduced, the data flow problems become much more difficult. The avail, live, and must-summary data flow problems are shown to be NP-complete in the presence of aliasing. However, an algorithm is presented with O(SET*EDGE) time performance where EDGE is the size of the program's flow graph and SET is a possible exponential number which reflects the number of aliasing patterns of the program. It is argued that in practice SET is small and on the order of the number of variables of the program.
Cited by 211 works. doi:10.1145/567532.567556 Open-access PDF
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The complexity of theorem-proving procedures
- A unified approach to global program optimization
- Flow Analysis of Computer Programs
- A program data flow analysis procedure
- Global common subexpression elimination
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- Data Flow Analysis in Software Reliability
- Global Data Flow Analysis and Iterative Algorithms
- A practical interprocedural data flow analysis algorithm