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

java.lang.Object
  com.ibm.wala.fixedpoint.impl.AbstractFixedPointSolver<T>
      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 com.ibm.wala.fixedpoint.impl.AbstractFixedPointSolver

AbstractFixedPointSolver.Statement

Field Summary

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

Fields inherited from class com.ibm.wala.fixedpoint.impl.AbstractFixedPointSolver

DEFAULT_PERIODIC_MAINTENANCE_INTERVAL, DEFAULT_VERBOSE_INTERVAL, verbose, workList

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

PropagationSystem(CallGraph cg, PointerKeyFactory pointerKeyFactory, InstanceKeyFactory instanceKeyFactory)

Method Summary

PointerAnalysis	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.
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.
java.util.Iterator<AbstractStatement>	getStatementsThatDef(PointsToSetVariable v)
java.util.Iterator<AbstractStatement>	getStatementsThatUse(PointsToSetVariable v)
java.util.Iterator	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	isTransitiveRoot(PointerKey key)
boolean	isUnified(PointerKey result)
java.util.Iterator<PointerKey>	iteratePointerKeys()
PointerAnalysis	makePointerAnalysis(PropagationCallGraphBuilder builder)
protected PointsToSetVariable[]	makeStmtRHS(int size)
void	newConstraint(PointerKey lhs, AbstractOperator<PointsToSetVariable> op, PointerKey rhs)
void	newConstraint(PointerKey lhs, AbstractOperator<PointsToSetVariable> op, PointerKey rhs1, PointerKey rhs2)
boolean	newConstraint(PointerKey lhs, InstanceKey value)
boolean	newConstraint(PointerKey lhs, UnaryOperator<PointsToSetVariable> op, PointerKey rhs) NB: this is idempotent ...
boolean	newFieldRead(PointerKey lhs, UnaryOperator<PointsToSetVariable> op, PointerKey rhs, PointerKey container)
boolean	newFieldWrite(PointerKey lhs, UnaryOperator<PointsToSetVariable> op, PointerKey rhs, PointerKey container)
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 com.ibm.wala.fixedpoint.impl.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

Methods inherited from class java.lang.Object

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

Field Detail

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 Detail

PropagationSystem

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

Method Detail

makePointerAnalysis

public PointerAnalysis 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:

java.lang.IllegalArgumentException - if klass is null

getInstanceKey

public InstanceKey getInstanceKey(int i)

Returns:

the instance key numbered with index i

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

Parameters:

key -

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 void newConstraint(PointerKey lhs,
                          AbstractOperator<PointsToSetVariable> op,
                          PointerKey rhs)

newConstraint

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

newFieldWrite

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

Returns:

true iff the system changes

newFieldRead

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

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 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 java.util.Iterator<PointerKey> iteratePointerKeys()

getNumberOfPointerKeys

public int getNumberOfPointerKeys()

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

getStatementsThatUse

public java.util.Iterator<AbstractStatement> getStatementsThatUse(PointsToSetVariable v)

getStatementsThatDef

public java.util.Iterator<AbstractStatement> 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 java.util.Iterator 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)

Parameters:

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:

java.lang.IllegalArgumentException - if s is null

isUnified

public boolean isUnified(PointerKey result)

getNumber

public int getNumber(PointerKey p)

makeStmtRHS

protected PointsToSetVariable[] makeStmtRHS(int size)

Specified by:

makeStmtRHS in class AbstractFixedPointSolver<PointsToSetVariable>