Class SSAPropagationCallGraphBuilder
- java.lang.Object
-
- com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder
-
- com.ibm.wala.ipa.callgraph.propagation.SSAPropagationCallGraphBuilder
-
- All Implemented Interfaces:
CallGraphBuilder
,HeapModel
,InstanceKeyFactory
,PointerKeyFactory
- Direct Known Subclasses:
AstSSAPropagationCallGraphBuilder
,DexSSAPropagationCallGraphBuilder
,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
Nested Classes 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 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
Fields Modifier and Type Field Description MonitorUtil.IProgressMonitor
monitor
static boolean
PERIODIC_WIPE_SOFT_CACHES
Should we periodically clear out soft reference caches in an attempt to help the GC?protected static 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 int
WIPE_SOFT_CACHE_INTERVAL
Interval which defines the period to clear soft reference caches-
Fields 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
Constructors Modifier Constructor Description protected
SSAPropagationCallGraphBuilder(IClassHierarchy cha, AnalysisOptions options, AnalysisCache cache, PointerKeyFactory pointerKeyFactory)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description protected void
addBlockInstructionConstraints(CGNode node, ControlFlowGraph<SSAInstruction,ISSABasicBlock> cfg, 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, IR ir, DefUse du)
Add constraints to represent the flow of exceptions to the exceptional return value for this nodeprotected 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, IR ir)
SSAContextInterpreter
getCFAContextInterpreter()
static List<ProgramCounter>
getIncomingPEIs(IR 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, IR ir, CGNode node)
precondition: hasUniqueCatchBlock(call,node,cg)boolean
hasNoInterestingUses(CGNode node, int vn, DefUse du)
protected static boolean
hasUniqueCatchBlock(SSAAbstractInvokeInstruction call, IR ir)
protected boolean
isConstantRef(SymbolTable symbolTable, int valueNumber)
protected void
iterateCrossProduct(CGNode caller, SSAAbstractInvokeInstruction call, IntSet parameters, InstanceKey[][] invariants, VoidFunction<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 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 Detail
-
PERIODIC_WIPE_SOFT_CACHES
public static final boolean PERIODIC_WIPE_SOFT_CACHES
Should we periodically clear out soft reference caches in an attempt to help the GC?- See Also:
- Constant Field Values
-
WIPE_SOFT_CACHE_INTERVAL
public static final int WIPE_SOFT_CACHE_INTERVAL
Interval which defines the period to clear soft reference caches- See Also:
- Constant Field Values
-
SHORT_CIRCUIT_SINGLE_USES
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. Doesn't play well with pre-transitive solver; turning off for now.- See Also:
- Constant Field Values
-
monitor
public MonitorUtil.IProgressMonitor monitor
-
-
Constructor Detail
-
SSAPropagationCallGraphBuilder
protected SSAPropagationCallGraphBuilder(IClassHierarchy cha, AnalysisOptions options, AnalysisCache cache, PointerKeyFactory pointerKeyFactory)
-
-
Method Detail
-
getCFAContextInterpreter
public SSAContextInterpreter getCFAContextInterpreter()
-
getInstanceKeyForPEI
public static InstanceKey getInstanceKeyForPEI(CGNode node, ProgramCounter x, TypeReference type, InstanceKeyFactory ikFactory)
- Parameters:
node
-x
-type
-- 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
- See Also:
com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder#addConstraintsFromNode(com.ibm.wala.ipa.callgraph.CGNode)
-
unconditionallyAddConstraintsFromNode
protected boolean unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException
- Specified by:
unconditionallyAddConstraintsFromNode
in classPropagationCallGraphBuilder
- Throws:
CancelException
-
makeVisitor
protected SSAPropagationCallGraphBuilder.ConstraintVisitor makeVisitor(CGNode node)
- 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
-
addBlockInstructionConstraints
protected void addBlockInstructionConstraints(CGNode node, ControlFlowGraph<SSAInstruction,ISSABasicBlock> cfg, SSACFG.BasicBlock b, SSAPropagationCallGraphBuilder.ConstraintVisitor v, MonitorUtil.IProgressMonitor monitor) throws CancelException
Add constraints for a particular basic block.- Throws:
CancelException
-
addNodePassthruExceptionConstraints
protected void addNodePassthruExceptionConstraints(CGNode node, IR ir, DefUse du)
Add constraints to represent the flow of exceptions to the exceptional return value for this node- Parameters:
node
-ir
-
-
hasUniqueCatchBlock
protected static boolean hasUniqueCatchBlock(SSAAbstractInvokeInstruction call, IR ir)
- 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, IR 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
public static List<ProgramCounter> getIncomingPEIs(IR ir, ISSABasicBlock bb)
- 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, IntSet parameters, InstanceKey[][] invariants, VoidFunction<InstanceKey[]> f)
-
getTargetsForCall
protected Set<CGNode> getTargetsForCall(CGNode caller, SSAAbstractInvokeInstruction instruction, InstanceKey[][] invs)
-
makeInterestingVisitor
protected SSAPropagationCallGraphBuilder.InterestingVisitor makeInterestingVisitor(CGNode node, int vn)
-
getTargetPointerKey
public PointerKey getTargetPointerKey(CGNode target, int index)
TODO: enhance this logic using type inference TODO!!!: enhance filtering to consider concrete types, not just cones. precondition: needs Filter- Parameters:
target
-- Returns:
- an IClass which represents
-
contentsAreInvariant
protected 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.- Parameters:
valueNumber
-- Returns:
- true iff the contents of the local with this value number can be deduced locally, without propagation
-
contentsAreInvariant
protected boolean contentsAreInvariant(SymbolTable symbolTable, DefUse du, int[] valueNumbers)
-
getInvariantContents
public InstanceKey[] getInvariantContents(SymbolTable symbolTable, DefUse du, CGNode node, int valueNumber, HeapModel hm)
precondition:contentsAreInvariant(valueNumber)- Parameters:
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
protected boolean isConstantRef(SymbolTable symbolTable, int valueNumber)
-
iteratePointerKeys
public Iterator<PointerKey> iteratePointerKeys()
- Specified by:
iteratePointerKeys
in interfaceHeapModel
- Returns:
- an Iterator of all PointerKeys that are modeled.
-
getCaughtExceptionTypes
public static Set<IClass> getCaughtExceptionTypes(SSAGetCaughtExceptionInstruction instruction, IR ir)
-
getInstanceKeyForPEI
public InstanceKey getInstanceKeyForPEI(CGNode node, ProgramCounter instr, TypeReference type)
- Specified by:
getInstanceKeyForPEI
in interfaceInstanceKeyFactory
- Returns:
- the instance key that represents the exception of type _type_ thrown by a particular PEI.
-
makeSolver
protected IPointsToSolver makeSolver()
- Specified by:
makeSolver
in classPropagationCallGraphBuilder
-
-