Class BasicRTABuilder

java.lang.Object

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

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

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

All Implemented Interfaces:

CallGraphBuilder<InstanceKey>

public class BasicRTABuilder
extends AbstractRTABuilder

TODO: refactor to eliminate more redundancy with SSACallGraphBuilder

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 inherited from class AbstractRTABuilder

allocatedClasses, clinitProcessed, clone2Assign, DEBUG, DEBUG_LEVEL

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

Constructor	Description
BasicRTABuilder(IClassHierarchy cha, AnalysisOptions options, IAnalysisCacheView cache, ContextSelector contextSelector, SSAContextInterpreter contextInterpreter)

Method Summary

Modifier and Type	Method	Description
protected RTASelectorKey	getKeyForSelector(Selector selector)
protected PointerKey	getKeyForSite(CallSiteReference site)
protected UnaryOperator<PointsToSetVariable>	makeDispatchOperator(CallSiteReference site, CGNode node)
protected void	updateSetsForNewClass(IClass klass, InstanceKey iKey, CGNode node, NewSiteReference n)	Perform needed bookkeeping when a new class is discovered.

Methods inherited from class AbstractRTABuilder

addConstraintsFromNode, createEmptyCallGraph, customInit, getAllocatedTypes, getPointerAnalysis, getRTAContextInterpreter, makeContextInterpreter, makeContextSelector, makeSolver, makeSystem, processClassInitializer, unconditionallyAddConstraintsFromNode, visitInvoke, visitNew

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()
PointerAnalysis<InstanceKey>	getPointerAnalysis()
protected RTAContextInterpreter	getRTAContextInterpreter()
protected SSAContextInterpreter	makeContextInterpreter(SSAContextInterpreter appContextInterpreter)
protected ContextSelector	makeContextSelector(ContextSelector appContextSelector)
protected IPointsToSolver	makeSolver()
protected PropagationSystem	makeSystem(AnalysisOptions options)
protected void	processClassInitializer(IClass klass)
protected boolean	unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor)
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

Constructor Details

BasicRTABuilder

public BasicRTABuilder(IClassHierarchy cha,
 AnalysisOptions options,
 IAnalysisCacheView cache,
 ContextSelector contextSelector,
 SSAContextInterpreter contextInterpreter)

Method Details

updateSetsForNewClass

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

Perform needed bookkeeping when a new class is discovered.

Specified by:

updateSetsForNewClass in class AbstractRTABuilder

getKeyForSite

protected PointerKey getKeyForSite(CallSiteReference site)

Specified by:

getKeyForSite in class AbstractRTABuilder

getKeyForSelector

protected RTASelectorKey getKeyForSelector(Selector selector)

makeDispatchOperator

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

Specified by:

makeDispatchOperator in class AbstractRTABuilder