Class AbstractFixedPointSolver<T extends IVariable<T>>
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<T>>
extends Object
implements IFixedPointSolver<T>, FixedPointConstants, VerboseAction
Represents a set of
IFixedPointStatement
s 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
-
Field Summary
Modifier and TypeFieldDescriptionstatic final int
static final int
static final boolean
protected Worklist
worklist for the iterative solverFields 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
-
Method Summary
Modifier and TypeMethodDescriptionvoid
Add all to the work list.void
Add a step to the work list.void
changedVariable
(T v) Call this method when the contents of a variable changes.boolean
int
int
int
protected int
subclasses should override as desired.Iterator
<? extends INodeWithNumber> double
protected int
subclasses should override as desired.void
void
Some setup which occurs only before the first solveprotected abstract void
Initialize all lattice vars in the system.protected abstract void
Initialize the work list for iteration.jstatic boolean
isChanged
(byte code) static boolean
isFixed
(byte code) static boolean
isSideEffect
(byte code) static String
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
void
optional method used for performance debuggingprotected void
a method that will be called every N evaluations.void
void
setMaxEvalBetweenTopo
(int i) void
setMinEquationsForTopSort
(int i) void
setTopologicalGrowthFactor
(double d) boolean
solve
(MonitorUtil.IProgressMonitor monitor) Solve the set of dataflow graph.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 Details
-
verbose
public static final boolean verbose -
DEFAULT_VERBOSE_INTERVAL
public static final int DEFAULT_VERBOSE_INTERVAL- See Also:
-
DEFAULT_PERIODIC_MAINTENANCE_INTERVAL
public static final int DEFAULT_PERIODIC_MAINTENANCE_INTERVAL- See Also:
-
workList
worklist for the iterative solver
-
-
Constructor Details
-
AbstractFixedPointSolver
public AbstractFixedPointSolver()
-
-
Method Details
-
makeStmtRHS
-
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
Solve the set of dataflow graph.PRECONDITION: graph is set up
- Specified by:
solve
in interfaceIFixedPointSolver<T extends IVariable<T>>
- 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
-
lineBreak
-
removeStatement
-
toString
-
getStatements
-
addToWorkList
Add a step to the work list.- Parameters:
s
- the step to add
-
addAllStatementsToWorkList
public void addAllStatementsToWorkList()Add all to the work list. -
changedVariable
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
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) -
getMaxEvalBetweenTopo
public int getMaxEvalBetweenTopo() -
getTopologicalGrowthFactor
public double getTopologicalGrowthFactor() -
setMaxEvalBetweenTopo
public void setMaxEvalBetweenTopo(int i) -
setTopologicalGrowthFactor
public void setTopologicalGrowthFactor(double 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.
-