Class PropagationSystem

java.lang.Object

com.ibm.wala.fixedpoint.impl.AbstractFixedPointSolver<PointsToSetVariable>

com.ibm.wala.fixedpoint.impl.DefaultFixedPointSolver<PointsToSetVariable>

com.ibm.wala.ipa.callgraph.propagation.PropagationSystem

All Implemented Interfaces:

FixedPointConstants, IFixedPointSolver<PointsToSetVariable>, VerboseAction

public class PropagationSystem
extends DefaultFixedPointSolver<PointsToSetVariable>

System of constraints that define propagation for call graph construction

Nested Class Summary

Nested classes/interfaces inherited from class AbstractFixedPointSolver

AbstractFixedPointSolver.Statement

Modifier and Type	Class	Description
protected class	AbstractFixedPointSolver.Statement

Field Summary

Fields

Modifier and Type	Field	Description
protected final CallGraph	cg	Governing call graph;
protected final MutableMapping<InstanceKey>	instanceKeys	bijection from InstanceKey <=> Integer
protected final PointsToMap	pointsToMap	object that tracks points-to sets

Fields inherited from class AbstractFixedPointSolver

DEFAULT_PERIODIC_MAINTENANCE_INTERVAL, DEFAULT_VERBOSE_INTERVAL, verbose, workList

Modifier and Type	Field	Description
static final int	DEFAULT_PERIODIC_MAINTENANCE_INTERVAL
static final int	DEFAULT_VERBOSE_INTERVAL
static final boolean	verbose
protected Worklist	workList	worklist for the iterative solver

Fields inherited from interface FixedPointConstants

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

Modifier and Type	Field	Description
static final byte	CHANGED	A return value which indicates that a lhs has changed, and the statement might need to be evaluated again.
static final byte	CHANGED_AND_FIXED	A return value which indicates that lhs has changed, and the statement need not be evaluated again.
static final int	CHANGED_MASK	The bit-mask which defines the "CHANGED" flag
static final int	FIXED_MASK	The bit-mask which defines the "FIXED" flag
static final byte	NOT_CHANGED	A return value which indicates that lhs has not changed, and the statement might need to be evaluated again.
static final byte	NOT_CHANGED_AND_FIXED	A return value which indicates that lhs has not changed, and the statement need not be evaluated again.
static final int	SIDE_EFFECT_MASK	The bit-mask which defines the "SIDE EFFECT" flag

Constructor Summary

Constructors

Constructor	Description
PropagationSystem(CallGraph cg, PointerKeyFactory pointerKeyFactory, InstanceKeyFactory instanceKeyFactory)

Method Summary

Modifier and Type	Method	Description
PointerAnalysis<InstanceKey>	extractPointerAnalysis(PropagationCallGraphBuilder builder)
int	findOrCreateIndexForInstanceKey(InstanceKey key)
PointsToSetVariable	findOrCreatePointsToSet(PointerKey key)	If key is unified, returns the representative
NumberedGraph<PointsToSetVariable>	getAssignmentGraph()
Graph<PointsToSetVariable>	getFilterAsssignmentGraph()
IFixedPointSystem<PointsToSetVariable>	getFixedPointSystem()
Graph<PointsToSetVariable>	getFlowGraphIncludingImplicitConstraints()	NOTE: do not use this method unless you really know what you are doing.
int	getInstanceIndex(InstanceKey ik)
InstanceKey	getInstanceKey(int i)
IntSet	getInstanceKeysForClass(IClass klass)
int	getNumber(PointerKey p)
int	getNumberOfPointerKeys()	warning: this is _real_ slow; don't use it anywhere performance critical
int	getPeriodicMaintainInterval()	subclasses should override as desired.
Iterator<AbstractStatement<PointsToSetVariable, ?>>	getStatementsThatDef(PointsToSetVariable v)
Iterator<AbstractStatement>	getStatementsThatUse(PointsToSetVariable v)
Iterator<PointerKey>	getTransitiveRoots()
int	getVerboseInterval()	subclasses should override as desired.
protected void	initializeVariables()	Initialize all lattice vars in the system.
protected void	initializeWorkList()	Initialize the work list for iteration.j
boolean	isImplicit(PointerKey result)
boolean	isTransitiveRoot(PointerKey key)
boolean	isUnified(PointerKey result)
Iterator<PointerKey>	iteratePointerKeys()
PointerAnalysis<InstanceKey>	makePointerAnalysis(PropagationCallGraphBuilder builder)
protected PointsToSetVariable[]	makeStmtRHS(int size)
boolean	newConstraint(PointerKey lhs, AbstractOperator<PointsToSetVariable> op, PointerKey rhs)
boolean	newConstraint(PointerKey lhs, AbstractOperator<PointsToSetVariable> op, PointerKey rhs1, PointerKey rhs2)
boolean	newConstraint(PointerKey lhs, UnaryOperator<PointsToSetVariable> op, PointerKey rhs)	NB: this is idempotent ...
boolean	newConstraint(PointerKey lhs, InstanceKey value)
boolean	newFieldRead(PointerKey lhs, UnaryOperator<PointsToSetVariable> op, PointerKey rhs)
boolean	newFieldWrite(PointerKey lhs, UnaryOperator<PointsToSetVariable> op, PointerKey rhs)
void	newSideEffect(AbstractOperator<PointsToSetVariable> op, PointerKey[] arg0)
void	newSideEffect(AbstractOperator<PointsToSetVariable> op, PointerKey arg0, PointerKey arg1)
void	newSideEffect(UnaryOperator<PointsToSetVariable> op, PointerKey arg0)
void	performVerboseAction()	optional method used for performance debugging
protected void	periodicMaintenance()	a method that will be called every N evaluations.
void	recordImplicitPointsToSet(PointerKey key)	record that a particular points-to-set is represented implicitly.
protected void	registerFixedSet(PointsToSetVariable p, UnarySideEffect s)
void	revertToPreTransitive()
void	setPeriodicMaintainInterval(int periodicMaintainInteval)
void	setVerboseInterval(int verboseInterval)
void	unify(IntSet s)	Unify the points-to-sets for the variables identified by the set s
protected void	updateSideEffects(PointsToSetVariable p, PointsToSetVariable rep)

Methods inherited from class AbstractFixedPointSolver

addAllStatementsToWorkList, addToWorkList, changedVariable, emptyWorkList, getMaxEvalBetweenTopo, getMinSizeForTopSort, getNumberOfEvaluations, getStatements, getTopologicalGrowthFactor, incNumberOfEvaluations, initForFirstSolve, isChanged, isFixed, isSideEffect, lineBreak, newStatement, newStatement, newStatement, newStatement, newStatement, orderStatements, removeStatement, setMaxEvalBetweenTopo, setMinEquationsForTopSort, setTopologicalGrowthFactor, solve, toString

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(PointsToSetVariable v)	Call this method when the contents of a variable changes.
boolean	emptyWorkList()
int	getMaxEvalBetweenTopo()
int	getMinSizeForTopSort()
int	getNumberOfEvaluations()
Iterator<? extends INodeWithNumber>	getStatements()
double	getTopologicalGrowthFactor()
void	incNumberOfEvaluations()
void	initForFirstSolve()	Some setup which occurs only before the first solve
static boolean	isChanged(byte code)
static boolean	isFixed(byte code)
static boolean	isSideEffect(byte code)
static String	lineBreak(String string, int wrap)
boolean	newStatement(PointsToSetVariable lhs, NullaryOperator<PointsToSetVariable> operator, boolean toWorkList, boolean eager)	Add a step with zero operands on the right-hand side.
boolean	newStatement(PointsToSetVariable lhs, AbstractOperator<PointsToSetVariable> operator, PointsToSetVariable[] rhs, boolean toWorkList, boolean eager)	Add a step to the system with an arbitrary number of operands on the right-hand side.
boolean	newStatement(PointsToSetVariable lhs, AbstractOperator<PointsToSetVariable> operator, PointsToSetVariable op1, PointsToSetVariable op2, boolean toWorkList, boolean eager)	Add an equation with two operands on the right-hand side.
boolean	newStatement(PointsToSetVariable lhs, AbstractOperator<PointsToSetVariable> operator, PointsToSetVariable op1, PointsToSetVariable op2, PointsToSetVariable op3, boolean toWorkList, boolean eager)	Add a step with three operands on the right-hand side.
boolean	newStatement(PointsToSetVariable lhs, UnaryOperator<PointsToSetVariable> operator, PointsToSetVariable rhs, boolean toWorkList, boolean eager)	Add a step with one operand on the right-hand side.
void	orderStatements()
void	removeStatement(AbstractStatement<PointsToSetVariable, ?> 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 Object

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

Field Details

pointsToMap

protected final PointsToMap pointsToMap

object that tracks points-to sets

instanceKeys

protected final MutableMapping<InstanceKey> instanceKeys

bijection from InstanceKey <=> Integer

cg

protected final CallGraph cg

Governing call graph;

Constructor Details

PropagationSystem

public PropagationSystem(CallGraph cg,
 PointerKeyFactory pointerKeyFactory,
 InstanceKeyFactory instanceKeyFactory)

Method Details

makePointerAnalysis

public PointerAnalysis<InstanceKey> makePointerAnalysis(PropagationCallGraphBuilder builder)

Returns:

an object which encapsulates the pointer analysis result

registerFixedSet

protected void registerFixedSet(PointsToSetVariable p,
 UnarySideEffect s)

updateSideEffects

protected void updateSideEffects(PointsToSetVariable p,
 PointsToSetVariable rep)

getInstanceKeysForClass

public IntSet getInstanceKeysForClass(IClass klass)

Returns:

a set of integers representing the instance keys that correspond to a given class, or null if there are none.

Throws:

IllegalArgumentException - if klass is null

getInstanceKey

public InstanceKey getInstanceKey(int i)

Returns:

the instance key numbered with index i

getInstanceIndex

public int getInstanceIndex(InstanceKey ik)

initializeVariables

protected void initializeVariables()

Description copied from class: AbstractFixedPointSolver

Initialize all lattice vars in the system.

Specified by:

initializeVariables in class AbstractFixedPointSolver<PointsToSetVariable>

recordImplicitPointsToSet

public void recordImplicitPointsToSet(PointerKey key)

record that a particular points-to-set is represented implicitly.

findOrCreatePointsToSet

public PointsToSetVariable findOrCreatePointsToSet(PointerKey key)

If key is unified, returns the representative

Returns:

the dataflow variable that tracks the points-to set for key

findOrCreateIndexForInstanceKey

public int findOrCreateIndexForInstanceKey(InstanceKey key)

newConstraint

public boolean newConstraint(PointerKey lhs,
 UnaryOperator<PointsToSetVariable> op,
 PointerKey rhs)

NB: this is idempotent ... if the given constraint exists, it will not be added to the system; however, this will be more expensive since it must check if the constraint pre-exits.

Returns:

true iff the system changes

newConstraint

public boolean newConstraint(PointerKey lhs,
 AbstractOperator<PointsToSetVariable> op,
 PointerKey rhs)

newConstraint

public boolean newConstraint(PointerKey lhs,
 AbstractOperator<PointsToSetVariable> op,
 PointerKey rhs1,
 PointerKey rhs2)

newFieldWrite

public boolean newFieldWrite(PointerKey lhs,
 UnaryOperator<PointsToSetVariable> op,
 PointerKey rhs)

Returns:

true iff the system changes

newFieldRead

public boolean newFieldRead(PointerKey lhs,
 UnaryOperator<PointsToSetVariable> op,
 PointerKey rhs)

Returns:

true iff the system changes

newConstraint

public boolean newConstraint(PointerKey lhs,
 InstanceKey value)

Returns:

true iff the system changes

newSideEffect

public void newSideEffect(UnaryOperator<PointsToSetVariable> op,
 PointerKey arg0)

newSideEffect

public void newSideEffect(AbstractOperator<PointsToSetVariable> op,
 PointerKey[] arg0)

newSideEffect

public void newSideEffect(AbstractOperator<PointsToSetVariable> op,
 PointerKey arg0,
 PointerKey arg1)

initializeWorkList

protected void initializeWorkList()

Description copied from class: AbstractFixedPointSolver

Initialize the work list for iteration.j

Specified by:

initializeWorkList in class AbstractFixedPointSolver<PointsToSetVariable>

extractPointerAnalysis

public PointerAnalysis<InstanceKey> extractPointerAnalysis(PropagationCallGraphBuilder builder)

Returns:

an object that encapsulates the pointer analysis results

performVerboseAction

public void performVerboseAction()

Description copied from interface: VerboseAction

optional method used for performance debugging

Specified by:

performVerboseAction in interface VerboseAction

Overrides:

performVerboseAction in class AbstractFixedPointSolver<PointsToSetVariable>

getFixedPointSystem

public IFixedPointSystem<PointsToSetVariable> getFixedPointSystem()

Specified by:

getFixedPointSystem in interface IFixedPointSolver<PointsToSetVariable>

Overrides:

getFixedPointSystem in class DefaultFixedPointSolver<PointsToSetVariable>

Returns:

the set of statements solved by this IFixedPointSolver

iteratePointerKeys

public Iterator<PointerKey> iteratePointerKeys()

See Also:

• HeapModel.iteratePointerKeys()

getNumberOfPointerKeys

public int getNumberOfPointerKeys()

warning: this is _real_ slow; don't use it anywhere performance critical

getStatementsThatUse

public Iterator<AbstractStatement> getStatementsThatUse(PointsToSetVariable v)

getStatementsThatDef

public Iterator<AbstractStatement<PointsToSetVariable, ?>> getStatementsThatDef(PointsToSetVariable v)

getAssignmentGraph

public NumberedGraph<PointsToSetVariable> getAssignmentGraph()

getFilterAsssignmentGraph

public Graph<PointsToSetVariable> getFilterAsssignmentGraph()

getFlowGraphIncludingImplicitConstraints

public Graph<PointsToSetVariable> getFlowGraphIncludingImplicitConstraints()

NOTE: do not use this method unless you really know what you are doing. Functionality is fragile and may not work in the future.

revertToPreTransitive

public void revertToPreTransitive()

getTransitiveRoots

public Iterator<PointerKey> getTransitiveRoots()

isTransitiveRoot

public boolean isTransitiveRoot(PointerKey key)

periodicMaintenance

protected void periodicMaintenance()

Description copied from class: AbstractFixedPointSolver

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

Overrides:

periodicMaintenance in class AbstractFixedPointSolver<PointsToSetVariable>

getVerboseInterval

public int getVerboseInterval()

Description copied from class: AbstractFixedPointSolver

subclasses should override as desired.

Overrides:

getVerboseInterval in class AbstractFixedPointSolver<PointsToSetVariable>

setVerboseInterval

public void setVerboseInterval(int verboseInterval)

Parameters:

verboseInterval - The verboseInterval to set.

getPeriodicMaintainInterval

public int getPeriodicMaintainInterval()

Description copied from class: AbstractFixedPointSolver

subclasses should override as desired.

Overrides:

getPeriodicMaintainInterval in class AbstractFixedPointSolver<PointsToSetVariable>

setPeriodicMaintainInterval

public void setPeriodicMaintainInterval(int periodicMaintainInteval)

unify

public void unify(IntSet s)

Unify the points-to-sets for the variables identified by the set s

Parameters:

s - numbers of points-to-set variables

Throws:

IllegalArgumentException - if s is null

isUnified

public boolean isUnified(PointerKey result)

isImplicit

public boolean isImplicit(PointerKey result)

getNumber

public int getNumber(PointerKey p)

makeStmtRHS

protected PointsToSetVariable[] makeStmtRHS(int size)

Specified by:

makeStmtRHS in class AbstractFixedPointSolver<PointsToSetVariable>