de.rwth.dfa
Class DataFlowSolver

java.lang.Object
  |
  +--de.rwth.dfa.DataFlowSolver

public class DataFlowSolver

extends java.lang.Object

Implements the text-book graph based data flow analysis algorithm. Given a data flow problem, it computes the maximum fixed point (MPF) solution.

Version:

$Id: DataFlowSolver.java,v 1.2 2002/09/17 06:53:53 mohnen Exp $

Author:

Markus Mohnen

Field Summary

protected boolean	forward Forward (along the edges) or backward (opposite the edges) data flow problem?
protected Graph.NodeDyer	functions The transfer functions for the computation.
protected RootedGraph	g The graph to operate on.
protected Graph.NodeDyer	inits The initial values for the computation.
protected boolean	isAll Universal (meet) or existential (join) data flow problem?
protected long	iterations Number of iterations computed so far.
protected long	iterationsBound Upper bound for the number of iterations.
protected Lattice	l The lattice for the values and on which the functions operate.
protected java.lang.Class	worklistFactory The class used to create a new work list.

Constructor Summary

DataFlowSolver(RootedGraph g, Graph.NodeDyer inits, Graph.NodeDyer functions, boolean isAll, boolean forward)
Creates a new DataFlowSolver instance with default upper bound and work list StackWorklist.

DataFlowSolver(RootedGraph g, Graph.NodeDyer inits, Graph.NodeDyer functions, boolean isAll, boolean forward, long iterationsBound, java.lang.Class worklistFactory)
Creates a new DataFlowSolver instance.

Method Summary

protected void	addDepending(Worklist worklist, Graph.Node node) Adds all nodes which depend on a specific node in the graph of this solver to a work list.
long	getIterations() Returns the number of iterations used in solve().
protected java.lang.Object	recompute(Graph.Node node, Graph.NodeDyer values) Recomputes the value for node in the graph of this data flow solver.
Graph.NodeDyer	solve() Solves this data flow problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

g

protected RootedGraph g

The graph to operate on.

inits

protected Graph.NodeDyer inits

The initial values for the computation. Always a coloring of g

functions

protected Graph.NodeDyer functions

The transfer functions for the computation. Always a coloring of g

l

protected Lattice l

The lattice for the values and on which the functions operate.

isAll

protected boolean isAll

Universal (meet) or existential (join) data flow problem?

forward

protected boolean forward

Forward (along the edges) or backward (opposite the edges) data flow problem?

iterations

protected long iterations

Number of iterations computed so far.

iterationsBound

protected long iterationsBound

Upper bound for the number of iterations.

worklistFactory

protected java.lang.Class worklistFactory

The class used to create a new work list.

Constructor Detail

DataFlowSolver

public DataFlowSolver(RootedGraph g,
                      Graph.NodeDyer inits,
                      Graph.NodeDyer functions,
                      boolean isAll,
                      boolean forward,
                      long iterationsBound,
                      java.lang.Class worklistFactory)
               throws java.lang.IllegalArgumentException

Creates a new DataFlowSolver instance. The data flow problem is described by a graph g, colorings of the graph giving initial values and transfer function, kind of problem, and direction of control flow in the graph. The functions must be monotonic on the underlying lattice! Otherwise, the computation may be complete nonsense and terminate only when the upper bound of iterations is reached.

Parameters:

g - a RootedGraph value

inits - a Graph.NodeDyer value

functions - a Graph.NodeDyer value

isAll - a boolean value

forward - a boolean value

iterationsBound - a long value

worklistFactory - a Class value

Throws:

java.lang.IllegalArgumentException - if

1. One of the colorings in functions is not a Function.
2. One of the colorings in functions does not have identical domain and range (endomorphism).
3. One of the colorings in functions does not have a Lattice as domain and range.
4. Not all colorings in functions have the same domain and range.
5. One of the colorings in inits is not an element of the unique Lattice determined by functions.

DataFlowSolver

public DataFlowSolver(RootedGraph g,
                      Graph.NodeDyer inits,
                      Graph.NodeDyer functions,
                      boolean isAll,
                      boolean forward)
               throws java.lang.IllegalArgumentException

Creates a new DataFlowSolver instance with default upper bound and work list StackWorklist.

Parameters:

g - a RootedGraph value

inits - a Graph.NodeDyer value

functions - a Graph.NodeDyer value

isAll - a boolean value

forward - a boolean value

Throws:

java.lang.IllegalArgumentException - if an error occurs

See Also:

DataFlowSolver(RootedGraph, Graph.NodeDyer, Graph.NodeDyer, boolean , boolean, long, Class)

Method Detail

getIterations

public long getIterations()

Returns the number of iterations used in solve().

Returns:

a long value: If solve was not called so for, -1

recompute

protected java.lang.Object recompute(Graph.Node node,
                                     Graph.NodeDyer values)
                              throws FunctionException

Recomputes the value for node in the graph of this data flow solver.

Parameters:

node - a Graph.Node value

values - a Graph.NodeDyer value

Returns:

an Object value

Throws:

FunctionException - if on the functions in the functions of this data flow solver throws this exception.

addDepending

protected void addDepending(Worklist worklist,
                            Graph.Node node)

Adds all nodes which depend on a specific node in the graph of this solver to a work list.

Parameters:

worklist - a Worklist value

node - a Graph.Node value

solve

public Graph.NodeDyer solve()
                     throws java.lang.InstantiationException,
                            java.lang.IllegalAccessException,
                            java.lang.ClassCastException,
                            FunctionException,
                            java.lang.IllegalArgumentException

Solves this data flow problem.

Returns:

a Graph.NodeDyer value: The results as coloring of the graph.

Throws:

java.lang.InstantiationException - if this exception is caused by creating a new instance of the work list factory.

java.lang.IllegalAccessException - if this exception is caused by creating a new instance of the work list factory.

java.lang.ClassCastException - if the new instance created by the work list factory is not a work list.

FunctionException - if one of the functions throws it

java.lang.IllegalArgumentException - if the number of iterations reaches the upper bound.