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