Class AbstractRTABuilder

java.lang.Object

com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder

com.ibm.wala.ipa.callgraph.propagation.rta.AbstractRTABuilder

All Implemented Interfaces:

CallGraphBuilder<InstanceKey>

Direct Known Subclasses:

BasicRTABuilder

public abstract class AbstractRTABuilder
extends PropagationCallGraphBuilder

Abstract superclass of various RTA flavors

Nested Class Summary

Nested classes/interfaces inherited from class PropagationCallGraphBuilder

PropagationCallGraphBuilder.ArrayLoadOperator, PropagationCallGraphBuilder.ArrayStoreOperator, PropagationCallGraphBuilder.FilterOperator, PropagationCallGraphBuilder.GetFieldOperator, PropagationCallGraphBuilder.InstanceArrayStoreOperator, PropagationCallGraphBuilder.InstancePutFieldOperator, PropagationCallGraphBuilder.InverseFilterOperator, PropagationCallGraphBuilder.MutableBoolean, PropagationCallGraphBuilder.PutFieldOperator, PropagationCallGraphBuilder.TypedPointerKey

Modifier and Type	Class	Description
final class	PropagationCallGraphBuilder.ArrayLoadOperator	Binary op: <dummy>:= ArrayLoad( <arrayref>) Side effect: Creates new equations.
final class	PropagationCallGraphBuilder.ArrayStoreOperator	Binary op: <dummy>:= ArrayStore( <arrayref>) Side effect: Creates new equations.
class	PropagationCallGraphBuilder.FilterOperator	The FilterOperator is a filtered set-union.
class	PropagationCallGraphBuilder.GetFieldOperator	Binary op: <dummy>:= GetField( <ref>) Side effect: Creates new equations.
final class	PropagationCallGraphBuilder.InstanceArrayStoreOperator	Update the points-to-set for an array contents to include a particular instance key.
final 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 final 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 final HashSet<IClass>	allocatedClasses	set of classes (IClass) discovered to be allocated
protected final Set<IClass>	clinitProcessed	set of classes whose clinit are processed
protected final boolean	clone2Assign	Should we change calls to clone() to assignments?
protected static final boolean	DEBUG
protected static final int	DEBUG_LEVEL

Fields inherited from class PropagationCallGraphBuilder

assignOperator, callGraph, cha, contextSelector, DEBUG_GENERAL, entrypointCallSites, filterOperator, instanceKeyFactory, inverseFilterOperator, options, pointerKeyFactory, system

Modifier and Type	Field	Description
static final com.ibm.wala.ipa.callgraph.propagation.AssignOperator	assignOperator	Singleton operator for assignments
protected final ExplicitCallGraph	callGraph	The call graph under construction
final IClassHierarchy	cha	Governing class hierarchy
protected ContextSelector	contextSelector	A context selector which may use information derived from the propagation-based dataflow.
protected static final boolean	DEBUG_GENERAL
protected final Set<CallSiteReference>	entrypointCallSites	Set of calls (CallSiteReferences) that are created by entrypoints
final PropagationCallGraphBuilder.FilterOperator	filterOperator	singleton operator for filter
protected InstanceKeyFactory	instanceKeyFactory	An object that abstracts how to model instances in the heap.
protected final PropagationCallGraphBuilder.InverseFilterOperator	inverseFilterOperator	singleton operator for inverse filter
protected final 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

Constructors

Modifier	Constructor	Description
protected	AbstractRTABuilder(IClassHierarchy cha, AnalysisOptions options, IAnalysisCacheView cache, ContextSelector appContextSelector, SSAContextInterpreter appContextInterpreter)

Method Summary

Modifier and Type	Method	Description
protected boolean	addConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor)	Visit all instructions in a node, and add dataflow constraints induced by each statement relevant to RTA
protected ExplicitCallGraph	createEmptyCallGraph(IMethod fakeRootClass, AnalysisOptions options)
protected void	customInit()
Set<IClass>	getAllocatedTypes()
protected abstract PointerKey	getKeyForSite(CallSiteReference site)
PointerAnalysis<InstanceKey>	getPointerAnalysis()
protected RTAContextInterpreter	getRTAContextInterpreter()
protected SSAContextInterpreter	makeContextInterpreter(SSAContextInterpreter appContextInterpreter)
protected ContextSelector	makeContextSelector(ContextSelector appContextSelector)
protected abstract UnaryOperator<PointsToSetVariable>	makeDispatchOperator(CallSiteReference site, CGNode node)
protected IPointsToSolver	makeSolver()
protected PropagationSystem	makeSystem(AnalysisOptions options)
protected void	processClassInitializer(IClass klass)
protected boolean	unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor)
protected abstract void	updateSetsForNewClass(IClass klass, InstanceKey iKey, CGNode node, NewSiteReference ns)	Perform needed bookkeeping when a new class is discovered.
void	visitInvoke(CGNode node, CallSiteReference site)	Add a constraint for a call instruction
void	visitNew(CGNode node, NewSiteReference newSite)	Add a constraint for an allocate

Methods inherited from class PropagationCallGraphBuilder

addAssignmentsForCatchPointerKey, addConstraintsFromChangedNode, addConstraintsFromNewNodes, assignInstanceToCatch, catches, filterForClass, getAnalysisCache, getCallGraph, getClassHierarchy, getContextInterpreter, getContextSelector, getFilteredPointerKeyForLocal, getFilteredPointerKeyForLocal, getFilteredPointerKeyForLocal, getInstanceKeyForAllocation, getInstanceKeyForConstant, getInstanceKeyForMetadataObject, getInstanceKeyForMultiNewArray, getInstanceKeys, getInstanceKeysForClass, getJavaLangObject, getMutableInstanceKeysForClass, getOptions, getPointerKeyFactory, getPointerKeyForArrayContents, getPointerKeyForExceptionalReturnValue, getPointerKeyForInstanceField, getPointerKeyForLocal, getPointerKeyForReturnValue, getPointerKeyForStaticField, getPropagationSystem, getSolver, getSystem, getTargetForCall, haveAlreadyVisited, isJavaLangObject, makeCallGraph, makeCallGraph, markAlreadyVisited, markChanged, markDiscovered, representsNullType, setContextInterpreter, setContextSelector, setInstanceKeys, setPointerKeyFactory, wasChanged

Modifier and Type	Method	Description
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.
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 void	assignInstanceToCatch(PointerKey exceptionVar, Set<IClass> catchClasses, InstanceKey e)	Handle assign of a particular exception instance into an exception variable
static boolean	catches(Set<IClass> catchClasses, IClass klass, IClassHierarchy cha)
protected IntSet	filterForClass(IntSet S, IClass klass)
IAnalysisCacheView	getAnalysisCache()
ExplicitCallGraph	getCallGraph()
IClassHierarchy	getClassHierarchy()
RTAContextInterpreter	getContextInterpreter()
ContextSelector	getContextSelector()
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, IClass filter)
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, FilteredPointerKey.TypeFilter filter)
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, InstanceKey filter)
InstanceKey	getInstanceKeyForAllocation(CGNode node, NewSiteReference allocation)
<T> InstanceKey	getInstanceKeyForConstant(TypeReference type, T S)
InstanceKey	getInstanceKeyForMetadataObject(Object obj, TypeReference objType)
InstanceKey	getInstanceKeyForMultiNewArray(CGNode node, NewSiteReference allocation, int dim)
InstanceKeyFactory	getInstanceKeys()
protected IntSet	getInstanceKeysForClass(IClass klass)
IClass	getJavaLangObject()
protected MutableIntSet	getMutableInstanceKeysForClass(IClass klass)
AnalysisOptions	getOptions()
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()
PropagationSystem	getSystem()
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 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	setPointerKeyFactory(PointerKeyFactory pkFact)
protected boolean	wasChanged(CGNode node)

Methods inherited from class Object

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

Field Details

DEBUG_LEVEL

protected static final int DEBUG_LEVEL

See Also:

• Constant Field Values

DEBUG

protected static final boolean DEBUG

See Also:

• Constant Field Values

clone2Assign

protected final boolean clone2Assign

Should we change calls to clone() to assignments?

See Also:

• Constant Field Values

clinitProcessed

protected final Set<IClass> clinitProcessed

set of classes whose clinit are processed

allocatedClasses

protected final HashSet<IClass> allocatedClasses

set of classes (IClass) discovered to be allocated

Constructor Details

AbstractRTABuilder

protected AbstractRTABuilder(IClassHierarchy cha,
 AnalysisOptions options,
 IAnalysisCacheView cache,
 ContextSelector appContextSelector,
 SSAContextInterpreter appContextInterpreter)

Method Details

getRTAContextInterpreter

protected RTAContextInterpreter getRTAContextInterpreter()

addConstraintsFromNode

protected boolean addConstraintsFromNode(CGNode node,
 MonitorUtil.IProgressMonitor monitor)

Visit all instructions in a node, and add dataflow constraints induced by each statement relevant to RTA

Specified by:

addConstraintsFromNode in class PropagationCallGraphBuilder

Returns:

true iff any new constraints are added.

processClassInitializer

protected void processClassInitializer(IClass klass)

visitInvoke

public void visitInvoke(CGNode node,
 CallSiteReference site)

Add a constraint for a call instruction

Throws:

IllegalArgumentException - if site is null

makeDispatchOperator

protected abstract UnaryOperator<PointsToSetVariable> makeDispatchOperator(CallSiteReference site,
 CGNode node)

getKeyForSite

protected abstract PointerKey getKeyForSite(CallSiteReference site)

visitNew

public void visitNew(CGNode node,
 NewSiteReference newSite)

Add a constraint for an allocate

Throws:

IllegalArgumentException - if newSite is null

updateSetsForNewClass

protected abstract void updateSetsForNewClass(IClass klass,
 InstanceKey iKey,
 CGNode node,
 NewSiteReference ns)

Perform needed bookkeeping when a new class is discovered.

customInit

protected void customInit()

Overrides:

customInit in class PropagationCallGraphBuilder

getAllocatedTypes

public Set<IClass> getAllocatedTypes()

Returns:

set of IClasses determined to be allocated

makeSolver

protected IPointsToSolver makeSolver()

Specified by:

makeSolver in class PropagationCallGraphBuilder

makeContextSelector

protected ContextSelector makeContextSelector(ContextSelector appContextSelector)

makeContextInterpreter

protected SSAContextInterpreter makeContextInterpreter(SSAContextInterpreter appContextInterpreter)

unconditionallyAddConstraintsFromNode

protected boolean unconditionallyAddConstraintsFromNode(CGNode node,
 MonitorUtil.IProgressMonitor monitor)

Specified by:

unconditionallyAddConstraintsFromNode in class PropagationCallGraphBuilder

createEmptyCallGraph

protected ExplicitCallGraph createEmptyCallGraph(IMethod fakeRootClass,
 AnalysisOptions options)

Overrides:

createEmptyCallGraph in class PropagationCallGraphBuilder

makeSystem

protected PropagationSystem makeSystem(AnalysisOptions options)

Overrides:

makeSystem in class PropagationCallGraphBuilder

getPointerAnalysis

public PointerAnalysis<InstanceKey> getPointerAnalysis()

Specified by:

getPointerAnalysis in interface CallGraphBuilder<InstanceKey>

Overrides:

getPointerAnalysis in class PropagationCallGraphBuilder

Returns:

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

See Also:

• CallGraphBuilder.getPointerAnalysis()