joeq.Compiler.Dataflow
Class Problem

java.lang.Object
  extended by 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


Copyright © 2001-2008 John Whaley. All Rights Reserved.