de.rwth.dfa.jvm
Class GraphSolver

java.lang.Object
  |
  +--de.rwth.dfa.jvm.Solver
        |
        +--de.rwth.dfa.jvm.GraphSolver

Direct Known Subclasses:

FactorisedFlowGraphSolver

public abstract class GraphSolver

extends Solver

An abstract class for a graph based JVM abstraction solver. The solution is computed using the classical iterative algorithm provided by the class DataFlowSolver.

To get a working implementation, the methods createGraph(), getInit(Graph.Node,boolean), getFunction(Graph.Node), and transferSolution(FlowGraph,Graph.NodeDyer,boolean,boolean,Object[]))must be provided.

Version:

$Id: GraphSolver.java,v 1.3 2002/09/17 06:53:53 mohnen Exp $

Author:

Markus Mohnen

Fields inherited from class de.rwth.dfa.jvm.Solver

abstraction, iterations, memory, methodExceptions, methodInstrs, methodName, stopwatch

Constructor Summary

GraphSolver(Abstraction abstraction, java.lang.String methodName, de.fub.bytecode.generic.InstructionList methodInstrs, de.fub.bytecode.classfile.CodeException[] methodExceptions)
Creates a new GraphSolver instance with out stop watch.

GraphSolver(Abstraction abstraction, java.lang.String methodName, de.fub.bytecode.generic.InstructionList methodInstrs, de.fub.bytecode.classfile.CodeException[] methodExceptions, Stopwatch stopwatch)
Creates a new GraphSolver instance with stop watch.

Method Summary

protected void	compute(java.lang.Object[] solution, boolean isForward, boolean isAll) Implements the graph based solution: A graph is created using createGraph().
protected abstract RootedGraph	createGraph() Supposed to compute the graph from the method to be analyzed.
protected abstract java.lang.Object	getFunction(RootedGraph.Node n) Supposed to compute the transfer function value of a node.
protected abstract java.lang.Object	getInit(RootedGraph.Node n, boolean isForward) Supposed to compute the initial value of a node.
protected abstract void	transferSolution(RootedGraph graph, Graph.NodeDyer gsolution, boolean isForward, boolean isAll, java.lang.Object[] solution) Supposed to transfer a graph based solution to an array.

Methods inherited from class de.rwth.dfa.jvm.Solver

getIterations, getMemory, getSolution

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphSolver

public GraphSolver(Abstraction abstraction,
                   java.lang.String methodName,
                   de.fub.bytecode.generic.InstructionList methodInstrs,
                   de.fub.bytecode.classfile.CodeException[] methodExceptions,
                   Stopwatch stopwatch)

Creates a new GraphSolver instance with stop watch.

Parameters:

abstraction - an Abstraction value

methodName - a String value

methodInstrs - an InstructionList value

methodExceptions - a CodeException[] value

stopwatch - a Stopwatch value

GraphSolver

public GraphSolver(Abstraction abstraction,
                   java.lang.String methodName,
                   de.fub.bytecode.generic.InstructionList methodInstrs,
                   de.fub.bytecode.classfile.CodeException[] methodExceptions)

Creates a new GraphSolver instance with out stop watch.

Parameters:

abstraction - an Abstraction value

methodName - a String value

methodInstrs - an InstructionList value

methodExceptions - a CodeException[] value

stopwatch - a Stopwatch value

Method Detail

compute

protected void compute(java.lang.Object[] solution,
                       boolean isForward,
                       boolean isAll)
                throws java.lang.IllegalArgumentException

Implements the graph based solution:

1. A graph is created using createGraph().
2. If there is a stop watch, stopwatch.split("graph creation") is executed.
3. An initial coloring of the graph is done using getInit(Node).
4. The transfer functions of the nodes are computed using getFunction(Node).
5. If there is a stop watch, stopwatch.split("solver init") is executed.
6. The solution and the number of iterations are computed using DataFlowSolver.
7. If there is a stop watch, stopwatch.split("solving") is executed.
8. The solution is transfered from graph level to instruction level using transferSolution(FlowGraph,Graph.NodeDyer,boolean,boolean,Object[])).
9. If there is a stop watch, stopwatch.split("transfer") is executed.

Overrides:

compute in class Solver

Parameters:

solution - an Object[] value

isForward - a boolean value

isAll - a boolean value

Throws:

java.lang.IllegalArgumentException - if an error occurs

createGraph

protected abstract RootedGraph createGraph()

Supposed to compute the graph from the method to be analyzed.

Returns:

a RootedGraph value

getInit

protected abstract java.lang.Object getInit(RootedGraph.Node n,
                                            boolean isForward)

Supposed to compute the initial value of a node. It must be an element of the lattice of the abstraction.

Parameters:

n - a Graph.Node value

isForward - a boolean value

Returns:

an Object value

getFunction

protected abstract java.lang.Object getFunction(RootedGraph.Node n)

Supposed to compute the transfer function value of a node. It must be an monotonic endomorphism on the lattice of the abstraction.

Parameters:

n - a Graph.Node value

Returns:

an Object value

transferSolution

protected abstract void transferSolution(RootedGraph graph,
                                         Graph.NodeDyer gsolution,
                                         boolean isForward,
                                         boolean isAll,
                                         java.lang.Object[] solution)

Supposed to transfer a graph based solution to an array.

Parameters:

graph - a RootedGraph value

gsolution - a Graph.NodeDyer value

isForward - a boolean value

isAll - a boolean value

solution - an Object[] value