Global Data Flow Analysis and Iterative Algorithms

ABSTRACT

Kildall has developed data propagation algorithms for code optimization in a general lattice theoretic framework. In another direction, Hecht and Ullman gave a strong upper bound on the number of iterations required for propagation algorithms when the data is represented by bit vectors and depth-first ordering of the flow graph is used. The present paper combines the ideas of these two papers by considering conditions under which the bound of Hecht and Ullman applies to the depth-first version of Kildall's general data propagation algorithm. It is shown that the following condition is necessary and sufficient: Let ƒ and g be any two functions which could be associated with blocks of a flow graph, let x be an arbitrary lattice element, and let 0 be the lattice zero. Then (*) (∀ƒ,g,x) [ƒg(0) ≥ g(0) ∧ ƒ(x) ∧ x]. Then it is shown that several of the particular instances of the techniques Kildall found useful do not meet condition (*).

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: ALLEN, F.E. Program optnni~atlon. Annual Review m Automatic Programming, Vol. 5, Pergamon Press, New York, 1969, 239-307.
• 3: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 4: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 5: 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]
• 6: 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]
• 7: John Hopcroft , Robert Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, v.16 n.6, p.372-378, June 1973 [doi>10.1145/362248.362272]
• 8: KAM, J.B., AN}) ULLMAN, J D Monotone data flow analysis frameworks TR-169, Dep. of Elec. Eng., Computer Sciences Lab., Princeton U., Princeton, N J, Jan 1975
• 9: KENNEDY, K A global flow analysis algorithm lnt J Computer Math. 3, 1 (Dec 1971), 5-15.
• 10: 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]
• 11: KNUTH, D.E. An empirmal study of FORTRAN programs. Software Pratt and Exper. 1, 2 (April 1971), 105-134
• 12: SCHAEFER, M. A Malhemahcal Theory of Global Flow Analysis Prentice-Hall, Englewood Chffs, N J., 1973.
• 13: ULLMAN, J D Fast algorithms for the elimination of commonsubexpressions Acta Informatwa Z, 3 (Dec. 1973), 191-213
• 14: VYSSOTSKY, V.A. Private communication to M.S. Hecht, June 1973

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: Sorting and searching

General Terms:
Algorithms, Measurement, Performance, Theory, Verification