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

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 int	CUTOFF A constant which constrains computation in getBoundOnNumberOfTargets
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 modelled
protected PropagationSystem	system The system of constraints used to build this graph
static java.util.Set<TypeReference>	THROWABLE_SET A singleton set holding the java.lang.Throwable TypeReference

Constructor Summary

protected

PropagationCallGraphBuilder(IClassHierarchy cha, WarningSet warnings, AnalysisOptions options, PointerKeyFactory pointerKeyFactory)

Method Summary

protected void	addAssignmentsForCatchPointerKey(PointerKey exceptionVar, java.util.Set catchClasses, PointerKey e) Generate a set of constraints to represent assignment to an exception variable in a catch clause.
void	addConstraintsFromChangedNode(CGNode node) Add constraints when the interpretation of a node changes (e.g.
protected boolean	addConstraintsFromNewNodes() Add constraints from newly discovered nodes.
protected abstract boolean	addConstraintsFromNode(CGNode n) Add constraints a node.
protected void	assignInstanceToCatch(PointerKey exceptionVar, java.util.Set catchClasses, InstanceKey e) Handle assign of a particular exception instance into an exception variable
static boolean	catches(java.util.Set catchClasses, IClass klass, IClassHierarchy cha)
protected ExplicitCallGraph	createEmptyCallGraph(IClassHierarchy cha, AnalysisOptions options)
protected void	customInit()
protected IntSet	filterForClass(IntSet S, IClass klass)
protected int	findOrCreateBoundFromIClassHierarchy(MethodReference m) TODO: optimize this by taking an IMethod rather than a MethodReference, to avoid more class hierarchy lookups
protected int	getBoundOnNumberOfTargets(CGNode caller, CallSiteReference site)
ExplicitCallGraph	getCallGraph()
IClassHierarchy	getClassHierarchy()
RTAContextInterpreter	getContextInterpreter()
ContextSelector	getContextSelector()
protected byte	getDefaultDispatchBoundHeuristic()
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)
InstanceKey	getInstanceKeyForConstant(TypeReference type, java.lang.Object S)
InstanceKey	getInstanceKeyForMultiNewArray(CGNode node, NewSiteReference allocation, int dim)
InstanceKeyFactory	getInstanceKeys()
protected IntSet	getInstanceKeysForClass(IClass klass)
IClass	getJavaLangObject()
IClass	getJavaLangThrowable()
protected MutableIntSet	getMutableInstanceKeysForClass(IClass klass)
AnalysisOptions	getOptions()
PointerAnalysis	getPointerAnalysis()
PointerFlowGraphFactory	getPointerFlowGraphFactory()
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()
java.lang.String	getStringConstantForInstanceKey(InstanceKey I)
CGNode	getTargetForCall(CGNode caller, CallSiteReference site, InstanceKey iKey)
WarningSet	getWarnings()
boolean	haveAlreadyVisited(CGNode node)
protected boolean	isJavaLangObject(IClass klass)
CallGraph	makeCallGraph(AnalysisOptions options) 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)
void	setWarnings(WarningSet set)
protected abstract boolean	unconditionallyAddConstraintsFromNode(CGNode node)
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 modelled

THROWABLE_SET

public static final java.util.Set<TypeReference> THROWABLE_SET

A singleton set holding the java.lang.Throwable TypeReference

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.

CUTOFF

protected static final int CUTOFF

A constant which constrains computation in getBoundOnNumberOfTargets

See Also:

Constant Field Values

Constructor Detail

PropagationCallGraphBuilder

protected PropagationCallGraphBuilder(IClassHierarchy cha,
                                      WarningSet warnings,
                                      AnalysisOptions options,
                                      PointerKeyFactory pointerKeyFactory)

Parameters:

cha - governing class hierarchy

warnings - an object to track analysis warnings

options - governing call graph construction options

pointerKeyFactory - factory which embodies pointer abstraction policy

Method Detail

createEmptyCallGraph

protected ExplicitCallGraph createEmptyCallGraph(IClassHierarchy cha,
                                                 AnalysisOptions options)

getDefaultDispatchBoundHeuristic

protected byte getDefaultDispatchBoundHeuristic()

isJavaLangObject

protected boolean isJavaLangObject(IClass klass)

Parameters:

klass -

Returns:

true iff the klass represents java.lang.Object

makeCallGraph

public CallGraph makeCallGraph(AnalysisOptions options)

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

makeSystem

protected PropagationSystem makeSystem(AnalysisOptions options)

makeSolver

protected abstract IPointsToSolver makeSolver()

customInit

protected void customInit()

addConstraintsFromNode

protected abstract boolean addConstraintsFromNode(CGNode n)

Add constraints a node.

Returns:

true iff any new constraints are added.

addConstraintsFromNewNodes

protected boolean addConstraintsFromNewNodes()

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.

getPointerKeyForLocal

public PointerKey getPointerKeyForLocal(CGNode node,
                                        int valueNumber)

Parameters:

node -

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)

Parameters:

node -

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,
                                                        IClass filter)

getFilteredPointerKeyForLocal

public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node,
                                                        int valueNumber,
                                                        InstanceKey filter)

getPointerKeyForReturnValue

public PointerKey getPointerKeyForReturnValue(CGNode node)

Parameters:

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)

Parameters:

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

getClassHierarchy

public IClassHierarchy getClassHierarchy()

getOptions

public AnalysisOptions getOptions()

getJavaLangObject

public IClass getJavaLangObject()

getJavaLangThrowable

public IClass getJavaLangThrowable()

getCallGraph

public ExplicitCallGraph getCallGraph()

getWarnings

public WarningSet getWarnings()

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.

getPointerFlowGraphFactory

public PointerFlowGraphFactory getPointerFlowGraphFactory()

Specified by:

getPointerFlowGraphFactory in interface CallGraphBuilder

getPropagationSystem

public PropagationSystem getPropagationSystem()

getPointerKeyFactory

public PointerKeyFactory getPointerKeyFactory()

getContextInterpreter

public RTAContextInterpreter getContextInterpreter()

getBoundOnNumberOfTargets

protected int getBoundOnNumberOfTargets(CGNode caller,
                                        CallSiteReference site)

Parameters:

caller - the caller node

Returns:

the maximum number of nodes this call might resolve to, or -1 if there is no known bound

findOrCreateBoundFromIClassHierarchy

protected int findOrCreateBoundFromIClassHierarchy(MethodReference m)

TODO: optimize this by taking an IMethod rather than a MethodReference, to avoid more class hierarchy lookups

Parameters:

m -

Returns:

the number of implementations of this method in the class hierarchy

getTargetForCall

public CGNode getTargetForCall(CGNode caller,
                               CallSiteReference site,
                               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 InstanceKey getInstanceKeyForConstant(TypeReference type,
                                             java.lang.Object S)

getStringConstantForInstanceKey

public java.lang.String getStringConstantForInstanceKey(InstanceKey I)

getInstanceKeyForClassObject

public InstanceKey getInstanceKeyForClassObject(TypeReference type)

haveAlreadyVisited

public boolean haveAlreadyVisited(CGNode node)

markAlreadyVisited

protected void markAlreadyVisited(CGNode node)

Parameters:

node -

markDiscovered

public void markDiscovered(CGNode node)

record that we've discovered a node

Parameters:

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

setWarnings

public void setWarnings(WarningSet set)

Parameters:

set -

getSolver

protected IPointsToSolver getSolver()

addConstraintsFromChangedNode

public void addConstraintsFromChangedNode(CGNode node)

Add constraints when the interpretation of a node changes (e.g. reflection)

Parameters:

node -

unconditionallyAddConstraintsFromNode

protected abstract boolean unconditionallyAddConstraintsFromNode(CGNode node)