Package 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 Object implements IFixedPointSolver<T>, FixedPointConstants, VerboseAction
Represents a set ofIFixedPointStatement
s to be solved by aIFixedPointSolver
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
Nested Classes Modifier and Type Class Description protected class
AbstractFixedPointSolver.Statement
-
Field Summary
Fields Modifier and Type Field Description 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
Constructors Constructor Description AbstractFixedPointSolver()
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description 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.Iterator
getStatements()
double
getTopologicalGrowthFactor()
protected int
getVerboseInterval()
subclasses should override as desired.void
incNumberOfEvaluations()
void
initForFirstSolve()
Some setup which occurs only before the first solveprotected abstract void
initializeVariables()
Initialize all lattice vars in the system.protected abstract void
initializeWorkList()
Initialize the work list for iteration.jstatic boolean
isChanged(byte code)
static boolean
isFixed(byte code)
static boolean
isSideEffect(byte code)
static String
lineBreak(String string, int wrap)
protected abstract T[]
makeStmtRHS(int size)
boolean
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, 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.boolean
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.boolean
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.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 debuggingprotected 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.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
-
-
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 interfaceIFixedPointSolver<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 interfaceVerboseAction
-
removeStatement
public void removeStatement(AbstractStatement<T,?> s)
-
getStatements
public 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 boolean 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 equationoperator
- the step operator- Throws:
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 equationoperator
- the step's operatorrhs
- first operand on the rhs- Returns:
- true iff the system changes
- Throws:
IllegalArgumentException
- if operator is null
-
newStatement
public boolean 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 equationoperator
- the equation operatorop1
- first operand on the rhsop2
- second operand on the rhs
-
newStatement
public boolean 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 equationoperator
- the equation operatorop1
- first operand on the rhsop2
- second operand on the rhsop3
- third operand on the rhs- Throws:
IllegalArgumentException
- if lhs is null
-
newStatement
public boolean 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 equationoperator
- the operatorrhs
- 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.
-
-