Testing flow graph reducibility

ABSTRACT

Many problems in program optimization have been solved by applying a technique called interval analysis to the flow graph of the program. A flow graph which is susceptible to this type of analysis is called reducible. This paper describes an algorithm for testing whether a flow graph is reducible. The algorithm uses depth-first search to reveal the structure of the flow graph and a good method for computing disjoint set unions to determine reducibility from the search information. When the algorithm is implemented on a random access computer, it requires O(E log* E) time to analyze a graph with E edges, where log* x &equil; min{i/logix≤1}. The time bound compares favorably with the O(E log E) bound of a previously known algorithm.

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: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 3: Ullman, J. D., "Fast Algorithms for the Elimination of Common Subexpressions", 13th Annual Symposium on Switching and Automata Theory, IEEE (October, 1972), 161-176.
• 4: Kennedy, R., "A Global Flow Analysis Algorithm", International J. Computer Mathematics, Vol. 3, No. 1 (December, 1971), 5-16.
• 5: Shaeffer, M., "A Mathematical Theory of Global Program Analysis", unpublished notes, System Development Corporation, Santa Monica, Calif., 1971.
• 6: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 7: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 8: Allen, F. E., "Program Optimization", Annual Review in Automatic Programming, Vol. 5, Pergammon Press, New York, 1969.
• 9: Hecht, M. S. and Ullman, J. D., "Flow Graph Reducibility", SIAM J. Computing, Vol. 1, No. 2 (June, 1972), 188-202.
• 10: Cocke, J. and Miller, R. E., "Some Analysis Techniques for Optimizing Computer Programs", Proc. Second International Conference on System Sciences, Honolulu, Hawaii, 1969.
• 11: Tarjan, R., "Depth-First Search and Linear Graph Algorithms", SIAM J. Computigg, Vol. 1, No. 2 (June, 1972), 146-159.
• 12: Tarjan, R., "Finding Dominators in Directed Graphs", unpublished, Cornell University, (December, 1972).
• 13: Fischer, M., "Efficiency of Equivalence Algorithms", Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York, 1972, 153-168.
• 14: Hopcroft, J. E. and Ullman, J. D., "Set Merging Algorithms", submitted to SIAM J. Computing.
• 15: Tarjan, R., "On the Efficiency of a Good but Not Linear Set Union Algorithm", TR 72-148, Department of Computer Science, Cornell University (November, 1972).
• 16: Cook, S. A., "Linear Time Simulation of Two-Way Pushdown Automata", Proc. IFIP Congress, 1971, TA-2, North Holland Publishing Co., Amsterdam, 1972, 174-179.
• 17: Busacker, R. G. and Saaty, T. L., Finite Graphs and Networks: An Introduction with Applications, McGraw-Hill Book Co., New York, 1965.
• 18: Ullman, J. D., private communication, December, 1972.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Algorithm, Code optimization, Complexity, Depth-first search, Directed graph, Flow analysis, Flow graph, Interval analysis, Program optimization, Reducibility, Set union algorithm, Tree