joeq.Compiler.Dataflow
Class Problem

java.lang.Object
  joeq.Compiler.Dataflow.Problem

Direct Known Subclasses:

LivenessAnalysis, ReachingDefs

public abstract class Problem
extends Object

Problem

Version:

$Id: Problem.java 1931 2004-09-22 22:17:47Z joewhaley $

Author:

John Whaley

Constructor Summary

Problem()

Method Summary

Fact	apply(TransferFunction tf, Fact f) Applies the transfer function to the given dataflow value, yielding another dataflow value.
abstract Fact	boundary() Returns the boundary value for this dataflow problem.
TransferFunction	closure(TransferFunction tf) Returns the closure of the given transfer function.
boolean	compare(Fact f1, Fact f2) Compares two dataflow facts, returning true if they are equal and false otherwise.
TransferFunction	compose(TransferFunction tf1, TransferFunction tf2) Returns the composition of two transfer functions.
abstract boolean	direction() Returns true if this is a forward dataflow problem, false if it is a backward dataflow problem.
abstract TransferFunction	getTransferFunction(Object e) Returns the transfer function for the given code element.
void	initialize(jwutil.graphs.Graph g) Performs necessary initialization for this dataflow problem.
abstract Fact	interior() Returns the value that the interior points should be initialized to.
Fact	merge(Fact f1, Fact f2) Combines two dataflow values, returning a new value that is the confluence of the two.

Methods inherited from class java.lang.Object

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

Constructor Detail

Problem

public Problem()

Method Detail

initialize

public void initialize(jwutil.graphs.Graph g)

Performs necessary initialization for this dataflow problem.

Parameters:

g - graph of locations that we will run over

direction

public abstract boolean direction()

Returns true if this is a forward dataflow problem, false if it is a backward dataflow problem.

Returns:

direction

boundary

public abstract Fact boundary()

Returns the boundary value for this dataflow problem. For a forward problem, this is the value at the entrypoint, whereas for a backward problem, this is the value at the exitpoint.

Returns:

boundary value

interior

public abstract Fact interior()

Returns the value that the interior points should be initialized to.

Returns:

value for interior points

getTransferFunction

public abstract TransferFunction getTransferFunction(Object e)

Returns the transfer function for the given code element.

Parameters:

e - code element

Returns:

transfer function for the given code element

apply

public Fact apply(TransferFunction tf,
                  Fact f)

Applies the transfer function to the given dataflow value, yielding another dataflow value.

Parameters:

tf - transfer function

f - dataflow value

Returns:

resulting dataflow value

compare

public boolean compare(Fact f1,
                       Fact f2)

Compares two dataflow facts, returning true if they are equal and false otherwise.

Parameters:

f1 - first fact

f2 - second fact

Returns:

true if they match, false otherwise

merge

public Fact merge(Fact f1,
                  Fact f2)

Combines two dataflow values, returning a new value that is the confluence of the two.

Parameters:

f1 - first fact

f2 - second fact

Returns:

confluence of the two facts

compose

public TransferFunction compose(TransferFunction tf1,
                                TransferFunction tf2)

Returns the composition of two transfer functions. The default implementation simply returns a transfer function that applies each of the transfer functions in turn.

Parameters:

tf1 - first transfer function

tf2 - second transfer function

Returns:

composed transfer function

closure

public TransferFunction closure(TransferFunction tf)

Returns the closure of the given transfer function. The closure is a transfer function that is equivalent to composing the given transfer function with itself repeatedly until the value stablizes. (A monotone lattice with finite descending chains guarantees this.)

Parameters:

tf -

Returns:

transfer function representing the closure