Node listings for reducible flow graphs

ABSTRACT

In [1], Kennedy conjectures that for every n node reducible flow graph, there is a sequence of nodes (with repetitions) of length O(nlogn) such that all acyclic paths are subsequences thereof. Such a sequence would, if it could be found easily, enable one to do various kinds of global data flow analyses quickly. We show that for all reducible flow graphs such a sequence does exist, even if the number of edges is much larger than n. If the number of edges is O(n), the node listing can be found in O(nlogn) time.

REFERENCES

• 1: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• 2: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 3: D. E. Knuth, "An empirical study of FORTRAN programs," Software: Practice and Experience1:2, (April, 1971), 105-134.
• 4: 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]
• 5: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 6: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 7: M. Schaefer, A Mathematical Theory of Global Flow Analysis, Prentice-Hall, Englewood Cliffs, N. J., 1973.
• 8: K. Kennedy, "A global flow analysis algorithm," Int. J. Comp. Math.3 (December, 1971), 5-15.
• 9: 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]
• 10: J. Kam and J. D. Ullman, "Global optimization problems and iterative algorithms," TR 146, Computer Science Laboratory, Princeton University, January, 1974.
• 11: Susan L. Graham , Mark Wegman, A fast and usually linear algorithm for global flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-34, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512979]
• 12: Charles Matthew Geschke, Global program optimizations., 1973
• 13: Malcolm C. Newey, Notes on a problem involving permutations as subsequences., Stanford University, Stanford, CA, 1973
• 14: M. S. Hecht and J. D. Ullman, "Flow graph reducibility," SIAM J. Computing1:2 (June, 1972), 188-202.
• 15: 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]
• 16: J. D. Ullman, "Fast algorithms for the elimination of common subexpressions," Acta Informatica2 (December, 1973), 191-213.
• 17: P. M. Lewis II, R. E. Stearns, and J. Hartmanis, "Memory bounds for recognition of context-free and context-sensitive languages," IEEE Conference Record of 6th Annual ACM Symposium on Switching Circuit Theory and Logical Design, October, 1966, pp. 191-202.
• 18: R. E. Tarjan, "Testing flow graph reducibility," J. Computer and System Sciences9:3 (December, 1974), 355-365.
• 19: G. Markowsky, Unpublished memorandum, December, 1974.
• 20: R. E. Tarjan, private communication, December, 1974.

INDEX TERMS

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

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Mathematical induction

General Terms:
Theory