Class SSAPropagationCallGraphBuilder
java.lang.Object
com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder
com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder
- All Implemented Interfaces:
CallGraphBuilder<InstanceKey>
,HeapModel
,InstanceKeyFactory
,PointerKeyFactory
- Direct Known Subclasses:
AstSSAPropagationCallGraphBuilder
,nCFABuilder
,ZeroXCFABuilder
public abstract class SSAPropagationCallGraphBuilder
extends PropagationCallGraphBuilder
implements HeapModel
This abstract base class provides the general algorithm for a call graph builder that relies on
propagation through an iterative dataflow solver, and constraints generated by statements in SSA
form.
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
Modifier and TypeClassDescriptionprotected static class
A visitor that generates constraints based on statements in SSA form.protected static class
sets bingo to true when it visits an interesting instructionNested classes/interfaces inherited from class com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder
PropagationCallGraphBuilder.ArrayLoadOperator, PropagationCallGraphBuilder.ArrayStoreOperator, PropagationCallGraphBuilder.FilterOperator, PropagationCallGraphBuilder.GetFieldOperator, PropagationCallGraphBuilder.InstanceArrayStoreOperator, PropagationCallGraphBuilder.InstancePutFieldOperator, PropagationCallGraphBuilder.InverseFilterOperator, PropagationCallGraphBuilder.MutableBoolean, PropagationCallGraphBuilder.PutFieldOperator, PropagationCallGraphBuilder.TypedPointerKey
-
Field Summary
Modifier and TypeFieldDescriptionstatic final boolean
Should we periodically clear out soft reference caches in an attempt to help the GC?protected static final boolean
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
Interval which defines the period to clear soft reference cachesFields inherited from class com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder
assignOperator, callGraph, cha, contextSelector, DEBUG_GENERAL, entrypointCallSites, filterOperator, instanceKeyFactory, inverseFilterOperator, options, pointerKeyFactory, system
-
Constructor Summary
ModifierConstructorDescriptionprotected
SSAPropagationCallGraphBuilder
(IMethod abstractRootMethod, AnalysisOptions options, IAnalysisCacheView cache, PointerKeyFactory pointerKeyFactory) -
Method Summary
Modifier and TypeMethodDescriptionprotected 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 nodeprotected void
addNodePassthruExceptionConstraints
(CGNode node, IRView ir, DefUse du) Add constraints to represent the flow of exceptions to the exceptional return value for this nodeprotected void
addNodeValueConstraints
(CGNode node, MonitorUtil.IProgressMonitor monitor) Hook for subclasses to add pointer flow constraints based on values in a given nodeboolean
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) getCaughtExceptionTypes
(SSAGetCaughtExceptionInstruction instruction, IRView ir) static List
<ProgramCounter> getIncomingPEIs
(IRView ir, ISSABasicBlock bb) getInstanceKeyForPEI
(CGNode node, ProgramCounter instr, TypeReference type) static InstanceKey
getInstanceKeyForPEI
(CGNode node, ProgramCounter x, TypeReference type, InstanceKeyFactory ikFactory) 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) getTargetPointerKey
(CGNode target, int index) TODO: enhance this logic using type inference TODO!!!: enhance filtering to consider concrete types, not just cones.getTargetsForCall
(CGNode caller, SSAAbstractInvokeInstruction instruction, InstanceKey[][] invs) getUniqueCatchKey
(SSAAbstractInvokeInstruction call, IRView ir, CGNode node) precondition: hasUniqueCatchBlock(call,node,cg)boolean
hasNoInterestingUses
(CGNode node, int vn, DefUse du) protected static boolean
protected boolean
isConstantRef
(SymbolTable symbolTable, int valueNumber) protected void
iterateCrossProduct
(CGNode caller, SSAAbstractInvokeInstruction call, InstanceKey[][] invariants, Consumer<InstanceKey[]> f) makeInterestingVisitor
(CGNode node, int vn) protected IPointsToSolver
makeVisitor
(CGNode node) protected void
processCallingConstraints
(CGNode caller, SSAAbstractInvokeInstruction instruction, CGNode target, InstanceKey[][] constParams, PointerKey uniqueCatchKey) protected boolean
Methods inherited from class com.ibm.wala.ipa.callgraph.propagation.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
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface com.ibm.wala.ipa.callgraph.propagation.HeapModel
getClassHierarchy
Methods inherited from interface com.ibm.wala.ipa.callgraph.propagation.InstanceKeyFactory
getInstanceKeyForAllocation, getInstanceKeyForConstant, getInstanceKeyForMetadataObject, getInstanceKeyForMultiNewArray
Methods inherited from interface com.ibm.wala.ipa.callgraph.propagation.PointerKeyFactory
getFilteredPointerKeyForLocal, getPointerKeyForArrayContents, getPointerKeyForExceptionalReturnValue, getPointerKeyForInstanceField, getPointerKeyForLocal, getPointerKeyForReturnValue, getPointerKeyForStaticField
-
Field Details
-
PERIODIC_WIPE_SOFT_CACHES
public static final boolean PERIODIC_WIPE_SOFT_CACHESShould we periodically clear out soft reference caches in an attempt to help the GC?- See Also:
-
WIPE_SOFT_CACHE_INTERVAL
public static final int WIPE_SOFT_CACHE_INTERVALInterval which defines the period to clear soft reference caches- See Also:
-
SHORT_CIRCUIT_SINGLE_USES
protected static final boolean SHORT_CIRCUIT_SINGLE_USESAn 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.Doesn't play well with pre-transitive solver; turning off for now.
- See Also:
-
monitor
-
-
Constructor Details
-
SSAPropagationCallGraphBuilder
protected SSAPropagationCallGraphBuilder(IMethod abstractRootMethod, AnalysisOptions options, IAnalysisCacheView cache, PointerKeyFactory pointerKeyFactory)
-
-
Method Details
-
getCFAContextInterpreter
-
getInstanceKeyForPEI
public static InstanceKey getInstanceKeyForPEI(CGNode node, ProgramCounter x, TypeReference type, InstanceKeyFactory ikFactory) - Returns:
- the instance key that represents the exception of type _type_ thrown by a particular PEI.
- Throws:
IllegalArgumentException
- if ikFactory is null
-
addConstraintsFromNode
protected boolean addConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException Visit all instructions in a node, and add dataflow constraints induced by each statement in the SSA form.- Specified by:
addConstraintsFromNode
in classPropagationCallGraphBuilder
- Returns:
- true iff any new constraints are added.
- Throws:
CancelException
-
unconditionallyAddConstraintsFromNode
protected boolean unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException - Specified by:
unconditionallyAddConstraintsFromNode
in classPropagationCallGraphBuilder
- Throws:
CancelException
-
makeVisitor
- Returns:
- a visitor to examine instructions in the ir
-
addNodeInstructionConstraints
protected void addNodeInstructionConstraints(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException Add pointer flow constraints based on instructions in a given node- Throws:
CancelException
-
addNodeValueConstraints
protected void addNodeValueConstraints(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException Hook for subclasses to add pointer flow constraints based on values in a given node- Throws:
CancelException
-
addBlockInstructionConstraints
protected void addBlockInstructionConstraints(CGNode node, IRView ir, SSACFG.BasicBlock b, SSAPropagationCallGraphBuilder.ConstraintVisitor v, MonitorUtil.IProgressMonitor monitor) throws CancelException Add constraints for a particular basic block.- Throws:
CancelException
-
addNodePassthruExceptionConstraints
-
hasUniqueCatchBlock
- Returns:
- true iff there's a unique catch block which catches all exceptions thrown by a certain call site.
-
getUniqueCatchKey
public PointerKey getUniqueCatchKey(SSAAbstractInvokeInstruction call, IRView ir, CGNode node) throws IllegalArgumentException, IllegalArgumentException precondition: hasUniqueCatchBlock(call,node,cg)- Returns:
- the unique pointer key which catches the exceptions thrown by a call
- Throws:
IllegalArgumentException
- if ir == nullIllegalArgumentException
- if call == null
-
getIncomingPEIs
- Returns:
- a List of Instructions that may transfer control to bb via an exceptional edge
- Throws:
IllegalArgumentException
- if ir is null
-
processCallingConstraints
protected void processCallingConstraints(CGNode caller, SSAAbstractInvokeInstruction instruction, CGNode target, InstanceKey[][] constParams, PointerKey uniqueCatchKey) -
iterateCrossProduct
protected void iterateCrossProduct(CGNode caller, SSAAbstractInvokeInstruction call, InstanceKey[][] invariants, Consumer<InstanceKey[]> f) -
getTargetsForCall
protected Set<CGNode> getTargetsForCall(CGNode caller, SSAAbstractInvokeInstruction instruction, InstanceKey[][] invs) -
hasNoInterestingUses
-
makeInterestingVisitor
protected SSAPropagationCallGraphBuilder.InterestingVisitor makeInterestingVisitor(CGNode node, int vn) -
getTargetPointerKey
TODO: enhance this logic using type inference TODO!!!: enhance filtering to consider concrete types, not just cones. precondition: needs Filter- Returns:
- an IClass which represents
-
contentsAreInvariant
A value is "invariant" if we can figure out the instances it can ever point to locally, without resorting to propagation.- Returns:
- true iff the contents of the local with this value number can be deduced locally, without propagation
-
contentsAreInvariant
-
getInvariantContents
public InstanceKey[] getInvariantContents(SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber, HeapModel hm) precondition:contentsAreInvariant(valueNumber)- Returns:
- the complete set of instances that the local with vn=valueNumber may point to.
-
getInvariantContents
protected InstanceKey[] getInvariantContents(SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber, HeapModel hm, boolean ensureIndexes) -
isConstantRef
-
iteratePointerKeys
- Specified by:
iteratePointerKeys
in interfaceHeapModel
- Returns:
- an Iterator of all PointerKeys that are modeled.
-
getCaughtExceptionTypes
public static Set<IClass> getCaughtExceptionTypes(SSAGetCaughtExceptionInstruction instruction, IRView ir) -
getInstanceKeyForPEI
- Specified by:
getInstanceKeyForPEI
in interfaceInstanceKeyFactory
- Returns:
- the instance key that represents the exception of type _type_ thrown by a particular PEI.
-
makeSolver
- Specified by:
makeSolver
in classPropagationCallGraphBuilder
-