Class PropagationCallGraphBuilder
- java.lang.Object
-
- com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder
-
- All Implemented Interfaces:
CallGraphBuilder
- Direct Known Subclasses:
AbstractRTABuilder
,SSAPropagationCallGraphBuilder
public abstract class PropagationCallGraphBuilder extends Object implements CallGraphBuilder
This abstract base class provides the general algorithm for a call graph builder that relies on propagation through an iterative dataflow solver TODO: This implementation currently keeps all points to sets live ... even those for local variables that do not span interprocedural boundaries. This may be too space-inefficient .. we can consider recomputing local sets on demand.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
PropagationCallGraphBuilder.ArrayLoadOperator
Binary op::= ArrayLoad( <arrayref>) Side effect: Creates new equations. class
PropagationCallGraphBuilder.ArrayStoreOperator
Binary op::= ArrayStore( <arrayref>) Side effect: Creates new equations. class
PropagationCallGraphBuilder.FilterOperator
The FilterOperator is a filtered set-union.class
PropagationCallGraphBuilder.GetFieldOperator
Binary op::= GetField( ) Side effect: Creates new equations. class
PropagationCallGraphBuilder.InstanceArrayStoreOperator
Update the points-to-set for an array contents to include a particular instance key.class
PropagationCallGraphBuilder.InstancePutFieldOperator
Update the points-to-set for a field to include a particular instance key.protected class
PropagationCallGraphBuilder.InverseFilterOperator
protected static class
PropagationCallGraphBuilder.MutableBoolean
class
PropagationCallGraphBuilder.PutFieldOperator
Operator that represents a putfieldstatic class
PropagationCallGraphBuilder.TypedPointerKey
A pointer key that delegates to an untyped variant, but adds a type filter
-
Field Summary
Fields Modifier and Type Field Description protected static com.ibm.wala.ipa.callgraph.propagation.AssignOperator
assignOperator
Singleton operator for assignmentsprotected ExplicitCallGraph
callGraph
The call graph under constructionIClassHierarchy
cha
Governing class hierarchyprotected ContextSelector
contextSelector
A context selector which may use information derived from the propagation-based dataflow.protected static boolean
DEBUG_GENERAL
protected Set<CallSiteReference>
entrypointCallSites
Set of calls (CallSiteReferences) that are created by entrypointsPropagationCallGraphBuilder.FilterOperator
filterOperator
singleton operator for filterprotected InstanceKeyFactory
instanceKeyFactory
An object that abstracts how to model instances in the heap.protected PropagationCallGraphBuilder.InverseFilterOperator
inverseFilterOperator
singleton operator for inverse filterprotected AnalysisOptions
options
Special rules for bypassing Java callsprotected PointerKeyFactory
pointerKeyFactory
Meta-data regarding how pointers are modeledprotected PropagationSystem
system
The system of constraints used to build this graph
-
Constructor Summary
Constructors Modifier Constructor Description protected
PropagationCallGraphBuilder(IClassHierarchy cha, AnalysisOptions options, AnalysisCache cache, PointerKeyFactory pointerKeyFactory)
-
Method Summary
-
-
-
Field Detail
-
DEBUG_GENERAL
protected static final boolean DEBUG_GENERAL
- See Also:
- Constant Field Values
-
pointerKeyFactory
protected PointerKeyFactory pointerKeyFactory
Meta-data regarding how pointers are modeled
-
cha
public final IClassHierarchy cha
Governing class hierarchy
-
options
protected final AnalysisOptions options
Special rules for bypassing Java calls
-
entrypointCallSites
protected final Set<CallSiteReference> entrypointCallSites
Set of calls (CallSiteReferences) that are created by entrypoints
-
system
protected PropagationSystem system
The system of constraints used to build this graph
-
callGraph
protected final ExplicitCallGraph callGraph
The call graph under construction
-
assignOperator
protected static final com.ibm.wala.ipa.callgraph.propagation.AssignOperator assignOperator
Singleton operator for assignments
-
filterOperator
public final PropagationCallGraphBuilder.FilterOperator filterOperator
singleton operator for filter
-
inverseFilterOperator
protected final PropagationCallGraphBuilder.InverseFilterOperator inverseFilterOperator
singleton operator for inverse filter
-
contextSelector
protected ContextSelector contextSelector
A context selector which may use information derived from the propagation-based dataflow.
-
instanceKeyFactory
protected InstanceKeyFactory instanceKeyFactory
An object that abstracts how to model instances in the heap.
-
-
Constructor Detail
-
PropagationCallGraphBuilder
protected PropagationCallGraphBuilder(IClassHierarchy cha, AnalysisOptions options, AnalysisCache cache, PointerKeyFactory pointerKeyFactory)
- Parameters:
cha
- governing class hierarchyoptions
- governing call graph construction optionspointerKeyFactory
- factory which embodies pointer abstraction policy
-
-
Method Detail
-
getSystem
public PropagationSystem getSystem()
-
createEmptyCallGraph
protected ExplicitCallGraph createEmptyCallGraph(IClassHierarchy cha, AnalysisOptions options)
-
isJavaLangObject
protected boolean isJavaLangObject(IClass klass)
- Returns:
- true iff the klass represents java.lang.Object
-
makeCallGraph
public CallGraph makeCallGraph(AnalysisOptions options) throws IllegalArgumentException, CancelException
-
makeCallGraph
public CallGraph makeCallGraph(AnalysisOptions options, MonitorUtil.IProgressMonitor monitor) throws IllegalArgumentException, CallGraphBuilderCancelException
Description copied from interface:CallGraphBuilder
Build a call graph.- Specified by:
makeCallGraph
in interfaceCallGraphBuilder
- Parameters:
options
- an object representing controlling options that the call graph building algorithm needs to know.- Returns:
- the built call graph
- Throws:
IllegalArgumentException
CallGraphBuilderCancelException
-
makeSystem
protected PropagationSystem makeSystem(AnalysisOptions options)
-
makeSolver
protected abstract IPointsToSolver makeSolver()
-
customInit
protected void customInit()
-
addConstraintsFromNode
protected abstract boolean addConstraintsFromNode(CGNode n, MonitorUtil.IProgressMonitor monitor) throws CancelException
Add constraints for a node.- Parameters:
monitor
-- Returns:
- true iff any new constraints are added.
- Throws:
CancelException
-
addConstraintsFromNewNodes
protected boolean addConstraintsFromNewNodes(MonitorUtil.IProgressMonitor monitor) throws CancelException
Add constraints from newly discovered nodes. Note: the act of adding constraints may discover new nodes, so this routine is iterative.- Returns:
- true iff any new constraints are added.
- Throws:
CancelException
-
getPointerKeyForLocal
public PointerKey getPointerKeyForLocal(CGNode node, int valueNumber)
- Returns:
- the PointerKey that acts as a representative for the class of pointers that includes the local variable identified by the value number parameter.
-
getFilteredPointerKeyForLocal
public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node, int valueNumber, FilteredPointerKey.TypeFilter filter)
- Returns:
- the PointerKey that acts as a representative for the class of pointers that includes the local variable identified by the value number parameter.
-
getFilteredPointerKeyForLocal
public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node, int valueNumber, IClass filter)
-
getFilteredPointerKeyForLocal
public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node, int valueNumber, InstanceKey filter)
-
getPointerKeyForReturnValue
public PointerKey getPointerKeyForReturnValue(CGNode node)
- Returns:
- the PointerKey that acts as a representative for the class of pointers that includes the return value for a node
-
getPointerKeyForExceptionalReturnValue
public PointerKey getPointerKeyForExceptionalReturnValue(CGNode node)
- Returns:
- the PointerKey that acts as a representative for the class of pointers that includes the exceptional return value
-
getPointerKeyForStaticField
public PointerKey getPointerKeyForStaticField(IField f)
- Returns:
- the PointerKey that acts as a representative for the class of pointers that includes the contents of the static field
-
getPointerKeyForInstanceField
public PointerKey getPointerKeyForInstanceField(InstanceKey I, IField field)
- Returns:
- the PointerKey that acts as a representation for the class of pointers that includes the given instance field. null if there's some problem.
- Throws:
IllegalArgumentException
- if I is nullIllegalArgumentException
- if field is null
-
getPointerKeyForArrayContents
public PointerKey getPointerKeyForArrayContents(InstanceKey I)
TODO: expand this API to differentiate between different array indices- Parameters:
I
- an InstanceKey representing an abstract array- Returns:
- the PointerKey that acts as a representation for the class of pointers that includes the given array contents, or null if none found.
- Throws:
IllegalArgumentException
- if I is null
-
assignInstanceToCatch
protected void assignInstanceToCatch(PointerKey exceptionVar, Set<IClass> catchClasses, InstanceKey e)
Handle assign of a particular exception instance into an exception variable- Parameters:
exceptionVar
- points-to set for a variable representing a caught exceptioncatchClasses
- set of TypeReferences that the exceptionVar may catche
- a particular exception instance
-
addAssignmentsForCatchPointerKey
protected void addAssignmentsForCatchPointerKey(PointerKey exceptionVar, Set<IClass> catchClasses, PointerKey e)
Generate a set of constraints to represent assignment to an exception variable in a catch clause. Note that we use FilterOperator to filter out types that the exception handler doesn't catch.- Parameters:
exceptionVar
- points-to set for a variable representing a caught exceptioncatchClasses
- set of TypeReferences that the exceptionVar may catche
- points-to-set representing a thrown exception that might be caught.
-
catches
public static boolean catches(Set<IClass> catchClasses, IClass klass, IClassHierarchy cha)
- Parameters:
catchClasses
- Set of TypeReferenceklass
- an Exception Class- Returns:
- true iff klass is a subclass of some element of the Set
- Throws:
IllegalArgumentException
- if catchClasses is null
-
representsNullType
public static boolean representsNullType(InstanceKey key) throws IllegalArgumentException
- Throws:
IllegalArgumentException
-
getClassHierarchy
public IClassHierarchy getClassHierarchy()
-
getOptions
public AnalysisOptions getOptions()
-
getJavaLangObject
public IClass getJavaLangObject()
-
getCallGraph
public ExplicitCallGraph getCallGraph()
-
setContextInterpreter
public void setContextInterpreter(SSAContextInterpreter interpreter)
Subclasses must register the context interpreter before building a call graph.
-
getPointerAnalysis
public PointerAnalysis<InstanceKey> getPointerAnalysis()
- Specified by:
getPointerAnalysis
in interfaceCallGraphBuilder
- Returns:
- the Pointer Analysis information computed as a side-effect of call graph construction.
-
getPropagationSystem
public PropagationSystem getPropagationSystem()
-
getPointerKeyFactory
public PointerKeyFactory getPointerKeyFactory()
-
setPointerKeyFactory
public void setPointerKeyFactory(PointerKeyFactory pkFact)
BEGIN Custom change: setter for pointerkey factory
-
getContextInterpreter
public RTAContextInterpreter getContextInterpreter()
END Custom change: setter for pointerkey factory
-
getTargetForCall
protected CGNode getTargetForCall(CGNode caller, CallSiteReference site, IClass recv, InstanceKey[] iKey)
- Parameters:
caller
- the caller nodeiKey
- an abstraction of the receiver of the call (or null if not applicable)- Returns:
- the CGNode to which this particular call should dispatch.
-
getContextSelector
public ContextSelector getContextSelector()
- Returns:
- the context selector for this call graph builder
-
setContextSelector
public void setContextSelector(ContextSelector selector)
-
getInstanceKeys
public InstanceKeyFactory getInstanceKeys()
-
setInstanceKeys
public void setInstanceKeys(InstanceKeyFactory keys)
-
getInstanceKeyForAllocation
public InstanceKey getInstanceKeyForAllocation(CGNode node, NewSiteReference allocation)
- Returns:
- the InstanceKey that acts as a representative for the class of objects that includes objects allocated at the given new instruction in the given node
-
getInstanceKeyForMultiNewArray
public InstanceKey getInstanceKeyForMultiNewArray(CGNode node, NewSiteReference allocation, int dim)
- Parameters:
dim
- the dimension of the array whose instance we would like to model. dim == 0 represents the first dimension, e.g., the [Object; instances in [[Object; e.g., the [[Object; instances in [[[Object; dim == 1 represents the second dimension, e.g., the [Object instances in [[[Object;- Returns:
- the InstanceKey that acts as a representative for the class of array contents objects that includes objects allocated at the given new instruction in the given node
-
getInstanceKeyForConstant
public <T> InstanceKey getInstanceKeyForConstant(TypeReference type, T S)
-
getInstanceKeyForMetadataObject
public InstanceKey getInstanceKeyForMetadataObject(Object obj, TypeReference objType)
-
haveAlreadyVisited
public boolean haveAlreadyVisited(CGNode node)
-
markAlreadyVisited
protected void markAlreadyVisited(CGNode node)
-
markDiscovered
public void markDiscovered(CGNode node)
record that we've discovered a node
-
markChanged
protected void markChanged(CGNode node)
-
wasChanged
protected boolean wasChanged(CGNode node)
-
getMutableInstanceKeysForClass
protected MutableIntSet getMutableInstanceKeysForClass(IClass klass)
-
filterForClass
protected IntSet filterForClass(IntSet S, IClass klass)
- Parameters:
klass
- a class- Returns:
- an int set which represents the subset of S that correspond to subtypes of klass
-
getSolver
protected IPointsToSolver getSolver()
-
addConstraintsFromChangedNode
public void addConstraintsFromChangedNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException
Add constraints when the interpretation of a node changes (e.g. reflection)- Parameters:
monitor
-- Throws:
CancelException
-
unconditionallyAddConstraintsFromNode
protected abstract boolean unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException
- Throws:
CancelException
-
getAnalysisCache
public AnalysisCache getAnalysisCache()
- Specified by:
getAnalysisCache
in interfaceCallGraphBuilder
- Returns:
- A cache of various analysis artifacts used during call graph construction.
-
-