Tech Report CS-89-11

An Efficient Algorithm for Incremental Data-Flow Analysis

F. Kenneth Zadeck

February 1989

Abstract:

This paper presents a new algorithm for data-flow analysis that works for data-flow problems in a new class, {\em partitionable} data-flow problems. While this class is a subset of the well-established {\em fast} class introduced by Graham and Wegman, most of the global data-flow problems that are commonly solved are shown to be in this class. This algorithm has two advantages over extant methods: \begin{enumerate} \item The algorithm is asymptotically faster than any extant algorithm when applied to the partitionable problems. \item The algorithm can be easily transformed into an efficient incremental algorithm. \end{enumerate}

(complete text in pdf)