Class AstSSAPropagationCallGraphBuilder

java.lang.Object

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

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

com.ibm.wala.cast.ipa.callgraph.AstSSAPropagationCallGraphBuilder

All Implemented Interfaces:

CallGraphBuilder<InstanceKey>, HeapModel, InstanceKeyFactory, PointerKeyFactory

Direct Known Subclasses:

AstJavaSSAPropagationCallGraphBuilder, CrossLanguageSSAPropagationCallGraphBuilder, JSSSAPropagationCallGraphBuilder

public abstract class AstSSAPropagationCallGraphBuilder
extends SSAPropagationCallGraphBuilder

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	AstSSAPropagationCallGraphBuilder.AstConstraintVisitor
static class	AstSSAPropagationCallGraphBuilder.AstInterestingVisitor
static class	AstSSAPropagationCallGraphBuilder.AstPointerAnalysisImpl

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

Modifier and Type	Field	Description
static final boolean	DEBUG_PROPERTIES
static final boolean	DEBUG_TYPE_INFERENCE

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

Modifier	Constructor	Description
protected	AstSSAPropagationCallGraphBuilder(IMethod fakeRootClass, AnalysisOptions options, IAnalysisCacheView cache, PointerKeyFactory pointerKeyFactory)

Method Summary

Modifier and Type	Method	Description
protected ExplicitCallGraph	createEmptyCallGraph(IMethod fakeRootClass, AnalysisOptions options)
protected abstract AbstractFieldPointerKey	fieldKeyForUnknownWrites(AbstractFieldPointerKey fieldKey)	If the given fieldKey represents a concrete field, return the corresponding field key that represents all writes to unknown fields that could potentially alias fieldKey
abstract GlobalObjectKey	getGlobalObject(Atom language)
boolean	hasNoInterestingUses(CGNode node, int vn, DefUse du)
protected boolean	isUncataloguedField(IClass type, String fieldName)	each language can specify whether a particular field name should be stored in object catalogs or not.
SSAContextInterpreter	makeDefaultContextInterpreters(SSAContextInterpreter appContextInterpreter, AnalysisOptions options, IClassHierarchy cha)
protected SSAPropagationCallGraphBuilder.InterestingVisitor	makeInterestingVisitor(CGNode node, int vn)
protected PropagationSystem	makeSystem(AnalysisOptions options)
SSAPropagationCallGraphBuilder.ConstraintVisitor	makeVisitor(CGNode node)
protected abstract boolean	sameMethod(CGNode opNode, String definingMethod)	Is definingMethod the same as the method represented by opNode? We need this since the names for methods in some languages don't map in the straightforward way to the CGNode
protected abstract boolean	useObjectCatalog()	should we maintain an object catalog for each instance key, storing the names of all known properties of the instance key? required to handle EachElementGetInstructions.

Methods inherited from class SSAPropagationCallGraphBuilder

addBlockInstructionConstraints, addConstraintsFromNode, addNodeInstructionConstraints, addNodePassthruExceptionConstraints, addNodeValueConstraints, contentsAreInvariant, contentsAreInvariant, getCaughtExceptionTypes, getCFAContextInterpreter, getIncomingPEIs, getInstanceKeyForPEI, getInstanceKeyForPEI, getInvariantContents, getInvariantContents, getTargetPointerKey, getTargetsForCall, getUniqueCatchKey, hasUniqueCatchBlock, isConstantRef, iterateCrossProduct, iteratePointerKeys, makeSolver, 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)
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 IPointsToSolver	makeSolver()
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, 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, 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 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 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)

Field Details

DEBUG_TYPE_INFERENCE

public static final boolean DEBUG_TYPE_INFERENCE

See Also:

• Constant Field Values

DEBUG_PROPERTIES

public static final boolean DEBUG_PROPERTIES

See Also:

• Constant Field Values

Constructor Details

AstSSAPropagationCallGraphBuilder

protected AstSSAPropagationCallGraphBuilder(IMethod fakeRootClass,
 AnalysisOptions options,
 IAnalysisCacheView cache,
 PointerKeyFactory pointerKeyFactory)

Method Details

useObjectCatalog

protected abstract boolean useObjectCatalog()

should we maintain an object catalog for each instance key, storing the names of all known properties of the instance key? required to handle EachElementGetInstructions.

See Also:

• AstSSAPropagationCallGraphBuilder.AstConstraintVisitor.visitPut(SSAPutInstruction)
• AstSSAPropagationCallGraphBuilder.AstConstraintVisitor.visitEachElementGet(EachElementGetInstruction)

isUncataloguedField

protected boolean isUncataloguedField(IClass type,
 String fieldName)

each language can specify whether a particular field name should be stored in object catalogs or not. By default, always return false.

getGlobalObject

public abstract GlobalObjectKey getGlobalObject(Atom language)

makeDefaultContextInterpreters

public SSAContextInterpreter makeDefaultContextInterpreters(SSAContextInterpreter appContextInterpreter,
 AnalysisOptions options,
 IClassHierarchy cha)

makeSystem

protected PropagationSystem makeSystem(AnalysisOptions options)

Overrides:

makeSystem in class PropagationCallGraphBuilder

createEmptyCallGraph

protected ExplicitCallGraph createEmptyCallGraph(IMethod fakeRootClass,
 AnalysisOptions options)

Overrides:

createEmptyCallGraph in class PropagationCallGraphBuilder

makeInterestingVisitor

protected SSAPropagationCallGraphBuilder.InterestingVisitor makeInterestingVisitor(CGNode node,
 int vn)

Overrides:

makeInterestingVisitor in class SSAPropagationCallGraphBuilder

hasNoInterestingUses

public boolean hasNoInterestingUses(CGNode node,
 int vn,
 DefUse du)

Overrides:

hasNoInterestingUses in class SSAPropagationCallGraphBuilder

makeVisitor

public SSAPropagationCallGraphBuilder.ConstraintVisitor makeVisitor(CGNode node)

Overrides:

makeVisitor in class SSAPropagationCallGraphBuilder

Returns:

a visitor to examine instructions in the ir

fieldKeyForUnknownWrites

protected abstract AbstractFieldPointerKey fieldKeyForUnknownWrites(AbstractFieldPointerKey fieldKey)

If the given fieldKey represents a concrete field, return the corresponding field key that represents all writes to unknown fields that could potentially alias fieldKey

sameMethod

protected abstract boolean sameMethod(CGNode opNode,
 String definingMethod)

Is definingMethod the same as the method represented by opNode? We need this since the names for methods in some languages don't map in the straightforward way to the CGNode