com.ibm.wala.ipa.callgraph.propagation
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 java.lang.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

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 putfield
static class	PropagationCallGraphBuilder.TypedPointerKey A pointer key that delegates to an untyped variant, but adds a type filter

Field Summary

protected static com.ibm.wala.ipa.callgraph.propagation.AssignOperator	assignOperator Singleton operator for assignments
protected ExplicitCallGraph	callGraph The call graph under construction
protected IClassHierarchy	cha Governing class hierarchy
protected ContextSelector	contextSelector A context selector which may use information derived from the propagation-based dataflow.
protected static boolean	DEBUG_GENERAL
protected java.util.Set<CallSiteReference>	entrypointCallSites Set of calls (CallSiteReferences) that are created by entrypoints
PropagationCallGraphBuilder.FilterOperator	filterOperator singleton operator for filter
protected InstanceKeyFactory	instanceKeyFactory An object that abstracts how to model instances in the heap.
protected PropagationCallGraphBuilder.InverseFilterOperator	inverseFilterOperator singleton operator for inverse filter
protected AnalysisOptions	options Special rules for bypassing Java calls
protected PointerKeyFactory	pointerKeyFactory Meta-data regarding how pointers are modeled
protected PropagationSystem	system The system of constraints used to build this graph

Constructor Summary

protected

PropagationCallGraphBuilder(IClassHierarchy cha, AnalysisOptions options, AnalysisCache cache, PointerKeyFactory pointerKeyFactory)

Method Summary

protected void	addAssignmentsForCatchPointerKey(PointerKey exceptionVar, java.util.Set<IClass> catchClasses, PointerKey e) Generate a set of constraints to represent assignment to an exception variable in a catch clause.
void	addConstraintsFromChangedNode(CGNode node, MonitorUtil.IProgressMonitor monitor) Add constraints when the interpretation of a node changes (e.g.
protected boolean	addConstraintsFromNewNodes(MonitorUtil.IProgressMonitor monitor) Add constraints from newly discovered nodes.
protected abstract boolean	addConstraintsFromNode(CGNode n, MonitorUtil.IProgressMonitor monitor) Add constraints for a node.
protected void	assignInstanceToCatch(PointerKey exceptionVar, java.util.Set<IClass> catchClasses, InstanceKey e) Handle assign of a particular exception instance into an exception variable
static boolean	catches(java.util.Set<IClass> catchClasses, IClass klass, IClassHierarchy cha)
protected ExplicitCallGraph	createEmptyCallGraph(IClassHierarchy cha, AnalysisOptions options)
protected void	customInit()
protected IntSet	filterForClass(IntSet S, IClass klass)
AnalysisCache	getAnalysisCache()
ExplicitCallGraph	getCallGraph()
IClassHierarchy	getClassHierarchy()
RTAContextInterpreter	getContextInterpreter()
ContextSelector	getContextSelector()
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, FilteredPointerKey.TypeFilter filter)
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, IClass filter)
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, InstanceKey filter)
InstanceKey	getInstanceKeyForAllocation(CGNode node, NewSiteReference allocation)
InstanceKey	getInstanceKeyForClassObject(TypeReference type)
<T> InstanceKey	getInstanceKeyForConstant(TypeReference type, T S)
InstanceKey	getInstanceKeyForMultiNewArray(CGNode node, NewSiteReference allocation, int dim)
InstanceKeyFactory	getInstanceKeys()
protected IntSet	getInstanceKeysForClass(IClass klass)
IClass	getJavaLangObject()
protected MutableIntSet	getMutableInstanceKeysForClass(IClass klass)
AnalysisOptions	getOptions()
PointerAnalysis	getPointerAnalysis()
PointerKeyFactory	getPointerKeyFactory()
PointerKey	getPointerKeyForArrayContents(InstanceKey I) TODO: expand this API to differentiate between different array indices
PointerKey	getPointerKeyForExceptionalReturnValue(CGNode node)
PointerKey	getPointerKeyForInstanceField(InstanceKey I, IField field)
PointerKey	getPointerKeyForLocal(CGNode node, int valueNumber)
PointerKey	getPointerKeyForReturnValue(CGNode node)
PointerKey	getPointerKeyForStaticField(IField f)
PropagationSystem	getPropagationSystem()
protected IPointsToSolver	getSolver()
protected CGNode	getTargetForCall(CGNode caller, CallSiteReference site, IClass recv, InstanceKey[] iKey)
boolean	haveAlreadyVisited(CGNode node)
protected boolean	isJavaLangObject(IClass klass)
CallGraph	makeCallGraph(AnalysisOptions options)
CallGraph	makeCallGraph(AnalysisOptions options, MonitorUtil.IProgressMonitor monitor) Build a call graph.
protected abstract IPointsToSolver	makeSolver()
protected PropagationSystem	makeSystem(AnalysisOptions options)
protected void	markAlreadyVisited(CGNode node)
protected void	markChanged(CGNode node)
void	markDiscovered(CGNode node) record that we've discovered a node
static boolean	representsNullType(InstanceKey key)
void	setContextInterpreter(SSAContextInterpreter interpreter) Subclasses must register the context interpreter before building a call graph.
void	setContextSelector(ContextSelector selector)
void	setInstanceKeys(InstanceKeyFactory keys)
protected abstract boolean	unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor)
protected boolean	wasChanged(CGNode node)

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG_GENERAL

protected static final boolean DEBUG_GENERAL

See Also:

Constant Field Values

pointerKeyFactory

protected final PointerKeyFactory pointerKeyFactory

Meta-data regarding how pointers are modeled

cha

protected final IClassHierarchy cha

Governing class hierarchy

options

protected final AnalysisOptions options

Special rules for bypassing Java calls

entrypointCallSites

protected final java.util.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 hierarchy

options - governing call graph construction options

pointerKeyFactory - factory which embodies pointer abstraction policy

Method Detail

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 java.lang.IllegalArgumentException,
                               CancelException

Throws:

java.lang.IllegalArgumentException

CancelException

makeCallGraph

public CallGraph makeCallGraph(AnalysisOptions options,
                               MonitorUtil.IProgressMonitor monitor)
                        throws java.lang.IllegalArgumentException,
                               CallGraphBuilderCancelException

Description copied from interface: CallGraphBuilder

Build a call graph.

Specified by:

makeCallGraph in interface CallGraphBuilder

Parameters:

options - an object representing controlling options that the call graph building algorithm needs to know.

Returns:

the built call graph

Throws:

java.lang.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:

java.lang.IllegalArgumentException - if I is null

java.lang.IllegalArgumentException - 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:

java.lang.IllegalArgumentException - if I is null

assignInstanceToCatch

protected void assignInstanceToCatch(PointerKey exceptionVar,
                                     java.util.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 exception

catchClasses - set of TypeReferences that the exceptionVar may catch

e - a particular exception instance

addAssignmentsForCatchPointerKey

protected void addAssignmentsForCatchPointerKey(PointerKey exceptionVar,
                                                java.util.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 exception

catchClasses - set of TypeReferences that the exceptionVar may catch

e - points-to-set representing a thrown exception that might be caught.

catches

public static boolean catches(java.util.Set<IClass> catchClasses,
                              IClass klass,
                              IClassHierarchy cha)

Parameters:

catchClasses - Set of TypeReference

klass - an Exception Class

Returns:

true iff klass is a subclass of some element of the Set

Throws:

java.lang.IllegalArgumentException - if catchClasses is null

representsNullType

public static boolean representsNullType(InstanceKey key)
                                  throws java.lang.IllegalArgumentException

Throws:

java.lang.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 getPointerAnalysis()

Specified by:

getPointerAnalysis in interface CallGraphBuilder

Returns:

the Pointer Analysis information computed as a side-effect of call graph construction.

getPropagationSystem

public PropagationSystem getPropagationSystem()

getPointerKeyFactory

public PointerKeyFactory getPointerKeyFactory()

getContextInterpreter

public RTAContextInterpreter getContextInterpreter()

getTargetForCall

protected CGNode getTargetForCall(CGNode caller,
                                  CallSiteReference site,
                                  IClass recv,
                                  InstanceKey[] iKey)

Parameters:

caller - the caller node

iKey - 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)

getInstanceKeyForClassObject

public InstanceKey getInstanceKeyForClassObject(TypeReference type)

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)

getInstanceKeysForClass

protected IntSet getInstanceKeysForClass(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 interface CallGraphBuilder

Returns:

A cache of various analysis artifacts used during call graph construction.