Analysis of a simple algorithm global data flow problems

ABSTRACT

There is an ordering of the nodes of a flow graph G which topologically sorts the dominance relation and can be found in 0(edges) steps. This ordering is the reverse of the order in which a node is last visited while growing any depth-first spanning tree of G. Moreover, if G is reducible, then this ordering topologically sorts the "dag" of G. Thus, for a reducible flow graph (rfg) there is a simple algorithm to compute the dominators of each node in 0(edges) bit vector steps.The main result of this paper relates two parameters of an rfg. If G is reducible, d is the largest number of back edges found in any cycle-free path in G, and k is the length of the interval derived sequence of G, then k≥d. From this result it follows that there is a very simple bit propagation algorithm (indeed, the obvious one) which also uses the above ordering, and is at least as good as the interval algorithm for solving all known global data flow problems such as "available expressions" and "live variables."

REFERENCES

• 1: A. V. Aho , J. E. Hopcroft , J. D. Ullman, On finding lowest common ancestors in trees, Proceedings of the fifth annual ACM symposium on Theory of computing, p.253-265, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804056]
• 2: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 3: {A1} F. E. Allen, "Program Optimization," Annual Review Automatic Programming, Vol. 5, Pergamon Press, New York, 1969.
• 4: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 5: {A3} F. E. Allen, "A Basis for Program Optimization," Proc. IFIP Conf. 71, North Holland Publishing Co., Amsterdam, 1971.
• 6: {AC} F. E. Allen and J. Cocke, "Graph-Theoretic Constructs for Program Control Flow Analysis," IBM Research Report RC 3923, T.J. Watson Research Center, Yorktown Heights, N.Y., July 1972.
• 7: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 8: C. P. Earnest , K. G. Balke , J. Anderson, Analysis of Graphs by Ordering of Nodes, Journal of the ACM (JACM), v.19 n.1, p.23-42, Jan. 1972 [doi>10.1145/321679.321683]
• 9: {HeU1} M. S. Hecht and J. D. Ullman, "Flow Graph Reducibility," SIAM J. Computing, Vol. 1, No. 2, pp. 188-202, June 1972.
• 10: {HeU2} M. S. Hecht and J. D. Ullman, "Characterizations of Reducible Flow Graphs," TR-118, Computer Science Laboratory, Electrical Eng. Dept., Princeton Univ., Jan. 1973.
• 11: {HoU} J. E. Hopcroft and J. D. Ullman, "An n log n Algorithm for Detecting Reducible Graphs," Proc. 6th Annual Princeton Conf. on Information Sciences and Systems, pp. 119-122, March 1972.
• 12: {Ke} K. Kennedy, "A Global Flow Analysis Algorithm," International J. Computer Math., Vol. 3, pp. 5-15, Dec. 1971.
• 13: {Ki} G. A. Kildall, "Global Expression Optimization at Compile Time," in this proceedings, Oct. 1973.
• 14: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 15: {P} R. T. Prosser, "Applications of Boolean Matrices to the Analysis of Flow Diagrams," Proc. Eastern Joint Computer Conf., Spartan Books, New York, pp. 133-138, Dec. 1959.
• 16: Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
• 17: {S} M. Schaefer, A Mathematical Theory of Global Flow Analysis, to appear, Prentice Hall, Englewood Cliffs, N.J., 1973.
• 18: {T1} R. E. Tarjan, "Depth-First Search and Linear Graph Algorithms," SIAM J. Computing, Vol. 1, No. 2, pp. 146-160, June 1972.
• 19: {T2} R. E. Tarjan, "Finding Dominators in Directed Graphs," to appear in Proc. 7th Annual Princeton Conf. on Information Sciences and Systems, March 1973.
• 20: Robert Tarjan, Testing flow graph reducibility, Proceedings of the fifth annual ACM symposium on Theory of computing, p.96-107, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804040]
• 21: {U1} J. D. Ullman, "Fast Algorithms for the Elimination of Common Subexpressions," TR-106, Computer Science Laboratory, Dept. of Electrical Eng., Princeton Univ., March 1972.
• 22: {U2} J. D. Ullman, "A Fast Algorithm for the Elimination of Common Subexpressions," Proc. 13th Symposium on Switching and Automata Theory, pp. 161-176, Oct. 1972.
• 23: {V} V. A. Vyssotsky, private communication of June 7, 1973.

INDEX TERMS

Keywords:
available expressions, code optimization, depth-first spanning tree, dominance, flow graph, global data flow analysis, interval analysis, live variables, reducibility