Global Data Flow Analysis and Iterative Algorithms

TLDR

Kildall introduced lattice‑theoretic data propagation algorithms for code optimization, while Hecht and Ullman established a tight iteration bound for bit‑vector data using depth‑first flow‑graph ordering. This paper investigates when Hecht and Ullman’s bound applies to the depth‑first variant of Kildall’s general data propagation algorithm. The authors derive a necessary and sufficient condition (*) that characterizes when the bound holds for any pair of block functions and lattice elements. They show that several of Kildall’s useful techniques fail to satisfy condition (*), indicating the bound does not universally apply.

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 (*).