Global Data Flow Analysis and Iterative Algorithms
John B. Kam, Jeffrey David Ullman · Journal of the ACM · 1976
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 (*).
Cited by 304 works. doi:10.1145/321921.321938 Open-access PDF
Authors
References
- An empirical study of FORTRAN programs
- A unified approach to global program optimization
- Control flow analysis
- Algorithm 447: efficient algorithms for graph manipulation
- Global common subexpression elimination
- A global flow analysis algorithm
- Fast algorithms for the elimination of common subexpressions
- Characterizations of Reducible Flow Graphs
- Analysis of a simple algorithm global data flow problems
- Global expression optimization during compilation