com.ibm.wala.fixedpoint.impl
Class AbstractFixedPointSolver<T extends IVariable<?>>

java.lang.Object
  com.ibm.wala.fixedpoint.impl.AbstractFixedPointSolver<T>

All Implemented Interfaces:

FixedPointConstants, IFixedPointSolver<T>, VerboseAction

Direct Known Subclasses:

DefaultFixedPointSolver

public abstract class AbstractFixedPointSolver<T extends IVariable<?>>
extends java.lang.Object
implements IFixedPointSolver<T>, FixedPointConstants, VerboseAction

Represents a set of IFixedPointStatements to be solved by a IFixedPointSolver

Implementation Note: The set of steps and variables is internally represented as a graph. Each step and each variable is a node in the graph. If a step produces a variable that is used by another step, the graph has a directed edge from the producer to the consumer. Fixed-point iteration proceeds in a topological order according to these edges.

Nested Class Summary

protected class

AbstractFixedPointSolver.Statement

Field Summary

static int	DEFAULT_PERIODIC_MAINTENANCE_INTERVAL
static int	DEFAULT_VERBOSE_INTERVAL
static boolean	verbose
protected Worklist	workList worklist for the iterative solver

Fields inherited from interface com.ibm.wala.fixpoint.FixedPointConstants

CHANGED, CHANGED_AND_FIXED, CHANGED_MASK, FIXED_MASK, NOT_CHANGED, NOT_CHANGED_AND_FIXED, SIDE_EFFECT_MASK

Constructor Summary

AbstractFixedPointSolver()

Method Summary

void	addAllStatementsToWorkList() Add all to the work list.
void	addToWorkList(AbstractStatement s) Add a step to the work list.
void	changedVariable(T v) Call this method when the contents of a variable changes.
boolean	emptyWorkList()
int	getMaxEvalBetweenTopo()
int	getMinSizeForTopSort()
int	getNumberOfEvaluations()
protected int	getPeriodicMaintainInterval() subclasses should override as desired.
java.util.Iterator	getStatements()
double	getTopologicalGrowthFactor()
protected int	getVerboseInterval() subclasses should override as desired.
void	incNumberOfEvaluations()
void	initForFirstSolve() Some setup which occurs only before the first solve
protected abstract void	initializeVariables() Initialize all lattice vars in the system.
protected abstract void	initializeWorkList() Initialize the work list for iteration.j
static boolean	isChanged(byte code)
static boolean	isFixed(byte code)
static boolean	isSideEffect(byte code)
static java.lang.String	lineBreak(java.lang.String string, int wrap)
protected abstract T[]	makeStmtRHS(int size)
void	newStatement(T lhs, AbstractOperator<T> operator, T[] rhs, boolean toWorkList, boolean eager) Add a step to the system with an arbitrary number of operands on the right-hand side.
void	newStatement(T lhs, AbstractOperator<T> operator, T op1, T op2, boolean toWorkList, boolean eager) Add an equation with two operands on the right-hand side.
void	newStatement(T lhs, AbstractOperator<T> operator, T op1, T op2, T op3, boolean toWorkList, boolean eager) Add a step with three operands on the right-hand side.
void	newStatement(T lhs, NullaryOperator<T> operator, boolean toWorkList, boolean eager) Add a step with zero operands on the right-hand side.
boolean	newStatement(T lhs, UnaryOperator<T> operator, T rhs, boolean toWorkList, boolean eager) Add a step with one operand on the right-hand side.
void	orderStatements()
void	performVerboseAction() optional method used for performance debugging
protected void	periodicMaintenance() a method that will be called every N evaluations.
void	removeStatement(AbstractStatement<T,?> s)
void	setMaxEvalBetweenTopo(int i)
void	setMinEquationsForTopSort(int i)
void	setTopologicalGrowthFactor(double d)
boolean	solve(MonitorUtil.IProgressMonitor monitor) Solve the set of dataflow graph.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.ibm.wala.fixpoint.IFixedPointSolver

getFixedPointSystem

Field Detail

verbose

public static final boolean verbose

DEFAULT_VERBOSE_INTERVAL

public static final int DEFAULT_VERBOSE_INTERVAL

See Also:

Constant Field Values

DEFAULT_PERIODIC_MAINTENANCE_INTERVAL

public static final int DEFAULT_PERIODIC_MAINTENANCE_INTERVAL

See Also:

Constant Field Values

workList

protected Worklist workList

worklist for the iterative solver

Constructor Detail

AbstractFixedPointSolver

public AbstractFixedPointSolver()

Method Detail

makeStmtRHS

protected abstract T[] makeStmtRHS(int size)

initForFirstSolve

public void initForFirstSolve()

Some setup which occurs only before the first solve

emptyWorkList

public boolean emptyWorkList()

Returns:

true iff work list is empty

solve

public boolean solve(MonitorUtil.IProgressMonitor monitor)
              throws CancelException

Solve the set of dataflow graph.

PRECONDITION: graph is set up

Specified by:

solve in interface IFixedPointSolver<T extends IVariable<?>>

Returns:

true iff the evaluation of some equation caused a change in the value of some variable.

Throws:

CancelException

performVerboseAction

public void performVerboseAction()

Description copied from interface: VerboseAction

optional method used for performance debugging

Specified by:

performVerboseAction in interface VerboseAction

lineBreak

public static java.lang.String lineBreak(java.lang.String string,
                                         int wrap)

removeStatement

public void removeStatement(AbstractStatement<T,?> s)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getStatements

public java.util.Iterator getStatements()

addToWorkList

public void addToWorkList(AbstractStatement s)

Add a step to the work list.

Parameters:

s - the step to add

addAllStatementsToWorkList

public void addAllStatementsToWorkList()

Add all to the work list.

changedVariable

public void changedVariable(T v)

Call this method when the contents of a variable changes. This routine adds all graph using this variable to the set of new graph.

Parameters:

v - the variable that has changed

newStatement

public void newStatement(T lhs,
                         NullaryOperator<T> operator,
                         boolean toWorkList,
                         boolean eager)

Add a step with zero operands on the right-hand side. TODO: this is a little odd, in that this equation will never fire unless explicitly added to a work list. I think in most cases we shouldn't be creating this nullary form.

Parameters:

lhs - the variable set by this equation

operator - the step operator

Throws:

java.lang.IllegalArgumentException - if lhs is null

newStatement

public boolean newStatement(T lhs,
                            UnaryOperator<T> operator,
                            T rhs,
                            boolean toWorkList,
                            boolean eager)

Add a step with one operand on the right-hand side.

Parameters:

lhs - the lattice variable set by this equation

operator - the step's operator

rhs - first operand on the rhs

Returns:

true iff the system changes

Throws:

java.lang.IllegalArgumentException - if operator is null

newStatement

public void newStatement(T lhs,
                         AbstractOperator<T> operator,
                         T op1,
                         T op2,
                         boolean toWorkList,
                         boolean eager)

Add an equation with two operands on the right-hand side.

Parameters:

lhs - the lattice variable set by this equation

operator - the equation operator

op1 - first operand on the rhs

op2 - second operand on the rhs

newStatement

public void newStatement(T lhs,
                         AbstractOperator<T> operator,
                         T op1,
                         T op2,
                         T op3,
                         boolean toWorkList,
                         boolean eager)

Add a step with three operands on the right-hand side.

Parameters:

lhs - the lattice variable set by this equation

operator - the equation operator

op1 - first operand on the rhs

op2 - second operand on the rhs

op3 - third operand on the rhs

Throws:

java.lang.IllegalArgumentException - if lhs is null

newStatement

public void newStatement(T lhs,
                         AbstractOperator<T> operator,
                         T[] rhs,
                         boolean toWorkList,
                         boolean eager)

Add a step to the system with an arbitrary number of operands on the right-hand side.

Parameters:

lhs - lattice variable set by this equation

operator - the operator

rhs - the operands on the rhs

initializeVariables

protected abstract void initializeVariables()

Initialize all lattice vars in the system.

initializeWorkList

protected abstract void initializeWorkList()

Initialize the work list for iteration.j

orderStatements

public void orderStatements()

isChanged

public static boolean isChanged(byte code)

isSideEffect

public static boolean isSideEffect(byte code)

isFixed

public static boolean isFixed(byte code)

getMinSizeForTopSort

public int getMinSizeForTopSort()

setMinEquationsForTopSort

public void setMinEquationsForTopSort(int i)

Parameters:

i -

getMaxEvalBetweenTopo

public int getMaxEvalBetweenTopo()

getTopologicalGrowthFactor

public double getTopologicalGrowthFactor()

setMaxEvalBetweenTopo

public void setMaxEvalBetweenTopo(int i)

Parameters:

i -

setTopologicalGrowthFactor

public void setTopologicalGrowthFactor(double d)

Parameters:

d -

getNumberOfEvaluations

public int getNumberOfEvaluations()

incNumberOfEvaluations

public void incNumberOfEvaluations()

periodicMaintenance

protected void periodicMaintenance()

a method that will be called every N evaluations. subclasses should override as desired.

getVerboseInterval

protected int getVerboseInterval()

subclasses should override as desired.

getPeriodicMaintainInterval

protected int getPeriodicMaintainInterval()

subclasses should override as desired.