Class ZeroXContainerCFABuilder

java.lang.Object

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

com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder

com.ibm.wala.ipa.callgraph.propagation.cfa.ZeroXCFABuilder

com.ibm.wala.ipa.callgraph.propagation.cfa.ZeroXContainerCFABuilder

All Implemented Interfaces:

CallGraphBuilder<InstanceKey>, HeapModel, InstanceKeyFactory, PointerKeyFactory

public class ZeroXContainerCFABuilder
extends ZeroXCFABuilder

0-X-CFA Call graph builder which analyzes calls to "container methods" in a context which is defined by the receiver instance.

Nested Class Summary

Nested classes/interfaces inherited from class SSAPropagationCallGraphBuilder

SSAPropagationCallGraphBuilder.ConstraintVisitor, SSAPropagationCallGraphBuilder.InterestingVisitor

Modifier and Type	Class	Description
protected static class	SSAPropagationCallGraphBuilder.ConstraintVisitor	A visitor that generates constraints based on statements in SSA form.
protected static class	SSAPropagationCallGraphBuilder.InterestingVisitor	sets bingo to true when it visits an interesting instruction

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 SSAPropagationCallGraphBuilder

monitor, PERIODIC_WIPE_SOFT_CACHES, SHORT_CIRCUIT_SINGLE_USES, WIPE_SOFT_CACHE_INTERVAL

Modifier and Type	Field	Description
MonitorUtil.IProgressMonitor	monitor
static final boolean	PERIODIC_WIPE_SOFT_CACHES	Should we periodically clear out soft reference caches in an attempt to help the GC?
protected static final boolean	SHORT_CIRCUIT_SINGLE_USES	An optimization: if we can locally determine that a particular pointer p has exactly one use, then we don't actually create the points-to-set for p, but instead short-circuit by propagating the final solution to the unique use.
static final int	WIPE_SOFT_CACHE_INTERVAL	Interval which defines the period to clear soft reference caches

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
ZeroXContainerCFABuilder(IClassHierarchy cha, AnalysisOptions options, IAnalysisCacheView cache, ContextSelector appContextSelector, SSAContextInterpreter appContextInterpreter, int instancePolicy)

Method Summary

Modifier and Type	Method	Description
protected ContextSelector	makeContainerContextSelector(IClassHierarchy cha, ZeroXInstanceKeys keys)

Methods inherited from class ZeroXCFABuilder

make, make, makeInstanceKeys

Modifier and Type	Method	Description
static ZeroXCFABuilder	make(Language l, IClassHierarchy cha, AnalysisOptions options, IAnalysisCacheView cache, ContextSelector appContextSelector, SSAContextInterpreter appContextInterpreter, int instancePolicy)
static SSAPropagationCallGraphBuilder	make(AnalysisOptions options, IAnalysisCacheView cache, IClassHierarchy cha, ClassLoader cl, AnalysisScope scope, String[] xmlFiles, byte instancePolicy)
protected ZeroXInstanceKeys	makeInstanceKeys(IClassHierarchy cha, AnalysisOptions options, SSAContextInterpreter contextInterpreter, int instancePolicy)	subclasses can override as desired

Methods inherited from class SSAPropagationCallGraphBuilder

addBlockInstructionConstraints, addConstraintsFromNode, addNodeInstructionConstraints, addNodePassthruExceptionConstraints, addNodeValueConstraints, contentsAreInvariant, contentsAreInvariant, getCaughtExceptionTypes, getCFAContextInterpreter, getIncomingPEIs, getInstanceKeyForPEI, getInstanceKeyForPEI, getInvariantContents, getInvariantContents, getTargetPointerKey, getTargetsForCall, getUniqueCatchKey, hasNoInterestingUses, hasUniqueCatchBlock, isConstantRef, iterateCrossProduct, iteratePointerKeys, makeInterestingVisitor, makeSolver, makeVisitor, processCallingConstraints, unconditionallyAddConstraintsFromNode

Modifier and Type	Method	Description
protected void	addBlockInstructionConstraints(CGNode node, IRView ir, SSACFG.BasicBlock b, SSAPropagationCallGraphBuilder.ConstraintVisitor v, MonitorUtil.IProgressMonitor monitor)	Add constraints for a particular basic block.
protected boolean	addConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor)	Visit all instructions in a node, and add dataflow constraints induced by each statement in the SSA form.
protected void	addNodeInstructionConstraints(CGNode node, MonitorUtil.IProgressMonitor monitor)	Add pointer flow constraints based on instructions in a given node
protected void	addNodePassthruExceptionConstraints(CGNode node, IRView ir, DefUse du)	Add constraints to represent the flow of exceptions to the exceptional return value for this node
protected void	addNodeValueConstraints(CGNode node, MonitorUtil.IProgressMonitor monitor)	Hook for subclasses to add pointer flow constraints based on values in a given node
boolean	contentsAreInvariant(SymbolTable symbolTable, DefUse du, int valueNumber)	A value is "invariant" if we can figure out the instances it can ever point to locally, without resorting to propagation.
protected boolean	contentsAreInvariant(SymbolTable symbolTable, DefUse du, int[] valueNumbers)
static Set<IClass>	getCaughtExceptionTypes(SSAGetCaughtExceptionInstruction instruction, IRView ir)
SSAContextInterpreter	getCFAContextInterpreter()
static List<ProgramCounter>	getIncomingPEIs(IRView ir, ISSABasicBlock bb)
InstanceKey	getInstanceKeyForPEI(CGNode node, ProgramCounter instr, TypeReference type)
static InstanceKey	getInstanceKeyForPEI(CGNode node, ProgramCounter x, TypeReference type, InstanceKeyFactory ikFactory)
InstanceKey[]	getInvariantContents(SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber, HeapModel hm)	precondition:contentsAreInvariant(valueNumber)
protected InstanceKey[]	getInvariantContents(SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber, HeapModel hm, boolean ensureIndexes)
PointerKey	getTargetPointerKey(CGNode target, int index)	TODO: enhance this logic using type inference TODO!!!: enhance filtering to consider concrete types, not just cones.
protected Set<CGNode>	getTargetsForCall(CGNode caller, SSAAbstractInvokeInstruction instruction, InstanceKey[][] invs)
PointerKey	getUniqueCatchKey(SSAAbstractInvokeInstruction call, IRView ir, CGNode node)	precondition: hasUniqueCatchBlock(call,node,cg)
boolean	hasNoInterestingUses(CGNode node, int vn, DefUse du)
protected static boolean	hasUniqueCatchBlock(SSAAbstractInvokeInstruction call, IRView ir)
protected boolean	isConstantRef(SymbolTable symbolTable, int valueNumber)
protected void	iterateCrossProduct(CGNode caller, SSAAbstractInvokeInstruction call, InstanceKey[][] invariants, Consumer<InstanceKey[]> f)
Iterator<PointerKey>	iteratePointerKeys()
protected SSAPropagationCallGraphBuilder.InterestingVisitor	makeInterestingVisitor(CGNode node, int vn)
protected IPointsToSolver	makeSolver()
protected SSAPropagationCallGraphBuilder.ConstraintVisitor	makeVisitor(CGNode node)
protected void	processCallingConstraints(CGNode caller, SSAAbstractInvokeInstruction instruction, CGNode target, InstanceKey[][] constParams, PointerKey uniqueCatchKey)
protected boolean	unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor)

Methods inherited from class PropagationCallGraphBuilder

addAssignmentsForCatchPointerKey, addConstraintsFromChangedNode, addConstraintsFromNewNodes, assignInstanceToCatch, catches, createEmptyCallGraph, customInit, filterForClass, getAnalysisCache, getCallGraph, getClassHierarchy, getContextInterpreter, getContextSelector, getFilteredPointerKeyForLocal, getFilteredPointerKeyForLocal, getFilteredPointerKeyForLocal, getInstanceKeyForAllocation, getInstanceKeyForConstant, getInstanceKeyForMetadataObject, getInstanceKeyForMultiNewArray, getInstanceKeys, getInstanceKeysForClass, getJavaLangObject, getMutableInstanceKeysForClass, getOptions, getPointerAnalysis, getPointerKeyFactory, getPointerKeyForArrayContents, getPointerKeyForExceptionalReturnValue, getPointerKeyForInstanceField, getPointerKeyForLocal, getPointerKeyForReturnValue, getPointerKeyForStaticField, getPropagationSystem, getSolver, getSystem, getTargetForCall, haveAlreadyVisited, isJavaLangObject, makeCallGraph, makeCallGraph, makeSystem, 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 ExplicitCallGraph	createEmptyCallGraph(IMethod abstractRootMethod, AnalysisOptions options)
protected void	customInit()
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()
PointerAnalysis<InstanceKey>	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()
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 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	setPointerKeyFactory(PointerKeyFactory pkFact)
protected boolean	wasChanged(CGNode node)

Methods inherited from class Object

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

Methods inherited from interface HeapModel

getClassHierarchy

Modifier and Type	Method	Description
IClassHierarchy	getClassHierarchy()

Methods inherited from interface InstanceKeyFactory

getInstanceKeyForAllocation, getInstanceKeyForConstant, getInstanceKeyForMetadataObject, getInstanceKeyForMultiNewArray

Modifier and Type	Method	Description
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)

Methods inherited from interface PointerKeyFactory

getFilteredPointerKeyForLocal, getPointerKeyForArrayContents, getPointerKeyForExceptionalReturnValue, getPointerKeyForInstanceField, getPointerKeyForLocal, getPointerKeyForReturnValue, getPointerKeyForStaticField

Modifier and Type	Method	Description
FilteredPointerKey	getFilteredPointerKeyForLocal(CGNode node, int valueNumber, FilteredPointerKey.TypeFilter filter)
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)

Constructor Details

ZeroXContainerCFABuilder

public ZeroXContainerCFABuilder(IClassHierarchy cha,
 AnalysisOptions options,
 IAnalysisCacheView cache,
 ContextSelector appContextSelector,
 SSAContextInterpreter appContextInterpreter,
 int instancePolicy)

Parameters:

cha - governing class hierarchy

options - call graph construction options

appContextSelector - application-specific logic to choose contexts

appContextInterpreter - application-specific logic to interpret a method in context

Throws:

IllegalArgumentException - if options is null

Method Details

makeContainerContextSelector

protected ContextSelector makeContainerContextSelector(IClassHierarchy cha,
 ZeroXInstanceKeys keys)

Returns:

an object which creates contexts for call graph nodes based on the container disambiguation policy