|
|
|
 |
TR-CIS-2002-01 (6/21/2002)
Gleb Naumovich
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.