Characterizations of Reducible Flow Graphs

ABSTRACT

It is established that if G is a reducible flow graph, then edge (n, m) is backward (a back latch) if and only if either n = m or m dominates n in G. Thus, the backward edges of a reducible flow graph are unique. Further characterizations of reducibility are presented. In particular, the following are equivalent: (a) G = (N, E, n0) is reducible. (b) The “dag” of G is unique. (A dag of a flow graph G is a maximal acyclic flow graph which is a subgraph of G.) (c) E can be partitioned into two sets E1 and E2 such that E1 forms a dag D of G and each (n, m) in E2 has n = m or m dominates n in G. (d) Same as (c), except each (n, m) in E2 has n = m or m dominates n in D. (e) Same as (c), except E2 is the back edge set of a depth-first spanning tree for G. (f) Every cycle of G has a node which dominates the other nodes of the cycle. Finally, it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducible flow graph.

REFERENCES

• 1: H~CHT, M. S., AND ULLMAN, J.D. Flow graph reducibility. SIAM J. Computing 1,2 (June 1972), 188-202.
• 2: HOPCROFT, J. E., AND ULLMAN, J.D. An n log n algorithm for detecting reducible graphs. Proc. 6th Annual Princeton Conf. on Information Sciences and Systems, March 1972, pp. 119-122.
• 3: ULLMAN, J.D. Fast algorithms for the elimination of common subexpressions. Acta Infor. matica $, 3 (Dec. 1973), 191-213.
• 4: ALLEN, F.E. Program optimization. Annual Rev. Automatic Prog., Vol. 5, Pergamon Press, New York, 1969.
• 5: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 6: ALL~N, F.E. A basis for program optimization. Proc. IFIP Conf. 71, Vol. 1, North-Holland Publishing Co., Amsterdam, 1971, 385-390.
• 7: ALLEN, F. E., AND COCK~, J. Graph-theoretic constructs for program control flow analysis. IBM Res. Rep. RC 3923, T. J. Watson Research Center, Yorktown Heights, N.Y., July 1972.
• 8: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 9: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 10: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 11: KENNEDY, K. A global flow analysis algorithm. Internat. J. Computer Math. 3 (Dec. 1971), 5-15.
• 12: TARJAN, R.E. Depth-first search and linear graph algorithms. SIAM J. Computing 1, 2 (Sept. 1972) 146-160.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory, Verification