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
Fields Modifier and Type Field Description protected CallGraph
cg
Governing call graph;protected MutableMapping<InstanceKey>
instanceKeys
bijection from InstanceKey <=>Integerprotected 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
Constructors Constructor Description PropagationSystem(CallGraph cg, PointerKeyFactory pointerKeyFactory, InstanceKeyFactory instanceKeyFactory)
-
Method Summary
-
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
-
-
-
-
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<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 classAbstractFixedPointSolver<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 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, 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 classAbstractFixedPointSolver<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 interfaceVerboseAction
- Overrides:
performVerboseAction
in classAbstractFixedPointSolver<PointsToSetVariable>
-
getFixedPointSystem
public IFixedPointSystem<PointsToSetVariable> getFixedPointSystem()
- Specified by:
getFixedPointSystem
in interfaceIFixedPointSolver<PointsToSetVariable>
- Overrides:
getFixedPointSystem
in classDefaultFixedPointSolver<PointsToSetVariable>
- Returns:
- the set of statements solved by this
IFixedPointSolver
-
iteratePointerKeys
public Iterator<PointerKey> 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> 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 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 classAbstractFixedPointSolver<PointsToSetVariable>
-
getVerboseInterval
public int getVerboseInterval()
Description copied from class:AbstractFixedPointSolver
subclasses should override as desired.- Overrides:
getVerboseInterval
in classAbstractFixedPointSolver<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 classAbstractFixedPointSolver<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:
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 classAbstractFixedPointSolver<PointsToSetVariable>
-
-