A fast and usually linear algorithm for global flow analysis

ABSTRACT

A new algorithm for global flow analysis on reducible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst case time bound of 0(e log2e) function operations. In programming terms, the number of operations is shown to be proportional to e + the number of exit nodes from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. It is shown that by relaxing these time bounds, a yet wider class of function spaces can be handled.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 3: Angluin, D., Private communication, July 1974.
• 4: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 5: Floyd, R. W., "Assigning Meanings to Programs," Proceedings American Mathematical Society Symposia in Applied Mathematics, Vol. 19, 1967, pp. 19-32.
• 6: Amelia Fong , John Kam , Jeffrey Ullman, Application of lattice algebra to loop optimization, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512977]
• 7: Hecht, M. S. and Ullman, J. D., "Flow Graph Reducibility," SIAM Journal of Computing, Vol. 1, No. 2, June 1972, pp. 188-202.
• 8: Matthew S. Hecht , Jeffrey D. Ullman, Analysis of a simple algorithm global data flow problems, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.207-217, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512946]
• 9: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 10: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 11: Kam, J. and Ullman, J. D., "Global Optimization Problems and Iterative Algorithms," TR-146, Department of Electrical Engineering, Princeton University, January 1974.
• 12: Kennedy, K., "A Global Flow Analysis Algorithm," International Journal of Computer Mathematics, Vol. 3, December 1971, pp. 5-15.
• 13: Kennedy, K., "A Comparison of Algorithms for Global Data Flow Analysis," Rice Technical Report 476-093-1, Rice University, February 1974.
• 14: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 15: Paterson, M., unpublished memorandum, University of Warwick, Coventry, England, April 1972. See also {19}.
• 16: W. W. Peterson , T. Kasami , N. Tokura, On the capabilities of while, repeat, and exit statements, Communications of the ACM, v.16 n.8, p.503-512, Aug. 1973 [doi>10.1145/355609.362337]
• 17: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 18: Tarjan, R. E., "Depth-first Search and Linear Graph Algorithms," SIAM Journal of Computing Vol. 1, No. 2, September 1972, pp. 146-160.
• 19: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 20: Ullman, J. D., "Fast Algorithms for the Elimination of Common Subexpressions, Acta Informatica, Vol. 2, No. 3, December 1973, pp. 191-213.
• 21: Wegman, M., Ph.D. Dissertation, in progress.
• 22: Wirth, N., "The Programming Language PASCAL," Acta Informatica, Vol. 1, No. 1, 1971, pp. 35-63.
• 23: William A. Wulf, A case against the GOTO, ACM SIGPLAN Notices, v.7 n.11, November 1972 [doi>10.1145/987361.987372]