TECHNICAL REPORT ARCHIVE


Using the Observer Design Pattern for Implementation of Data Flow Analyses

TR-CIS-2002-01 (6/21/2002)
Gleb Naumovich

pdf version of this paper

Abstract
Data flow analysis is used widely in program compilation, understanding, design, and analysis tools. In data flow analysis, problem-specific information is associated with nodes and/or edges in the flow graph representation of a program or component and re-computed iteratively. A popular data flow analysis design relies on a worklist that stores all nodes and edges whose data flow information has to be re-computed. While this approach is straightforward, it has some drawbacks. First, the presence of the worklist makes data flow algorithms centralized, which may reduce effectiveness of parallel implementations of these algorithms. Second, the worklist approach is difficult to implement in a way that minimizes the amount of information passed between flow graph nodes.

In this paper, we propose to use the well-known Observer pattern for implementation of data flow analyses. We argue that such implementations are more object-oriented in nature, as well as less centralized, than worklist-based ones. We show that by adopting this Observer-based view, data flow analyses that minimize the amount of information passed between flow graph nodes can be implemented easier than by using the worklist view. We present experimental data indicating that for some types of data flow problems, even single-threaded implementations of Observer-based data flow analysis have better run times than comparable worklist-based implementations.

Back to previous page