com.ibm.wala.ipa.callgraph.propagation
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, 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

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

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

protected

SSAPropagationCallGraphBuilder(IClassHierarchy cha, AnalysisOptions options, AnalysisCache cache, PointerKeyFactory pointerKeyFactory)

Method Summary

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 node
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
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.
protected boolean	contentsAreInvariant(SymbolTable symbolTable, DefUse du, int[] valueNumbers)
static java.util.Set<IClass>	getCaughtExceptionTypes(SSAGetCaughtExceptionInstruction instruction, IR ir)
SSAContextInterpreter	getCFAContextInterpreter()
static java.util.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)
protected 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)
protected PointerKey	getTargetPointerKey(CGNode target, int index) TODO: enhance this logic using type inference TODO!!!: enhance filtering to consider concrete types, not just cones.
protected java.util.Set<CGNode>	getTargetsForCall(CGNode caller, CallSiteReference site)
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, CallSiteReference site, IntSet parameters, VoidFunction<InstanceKey[]> f)
java.util.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, getInstanceKeyForClassObject, getInstanceKeyForConstant, getInstanceKeyForMultiNewArray, getInstanceKeys, getInstanceKeysForClass, getJavaLangObject, getMutableInstanceKeysForClass, getOptions, getPointerAnalysis, getPointerKeyFactory, getPointerKeyForArrayContents, getPointerKeyForExceptionalReturnValue, getPointerKeyForInstanceField, getPointerKeyForLocal, getPointerKeyForReturnValue, getPointerKeyForStaticField, getPropagationSystem, getSolver, getTargetForCall, haveAlreadyVisited, isJavaLangObject, makeCallGraph, makeCallGraph, makeSystem, markAlreadyVisited, markChanged, markDiscovered, representsNullType, setContextInterpreter, setContextSelector, setInstanceKeys, 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, getInstanceKeyForClassObject, getInstanceKeyForConstant, 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

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:

java.lang.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 class PropagationCallGraphBuilder

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 class PropagationCallGraphBuilder

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 java.lang.IllegalArgumentException,
                                    java.lang.IllegalArgumentException

precondition: hasUniqueCatchBlock(call,node,cg)

Returns:

the unique pointer key which catches the exceptions thrown by a call

Throws:

java.lang.IllegalArgumentException - if ir == null

java.lang.IllegalArgumentException - if call == null

getIncomingPEIs

public static java.util.List<ProgramCounter> getIncomingPEIs(IR ir,
                                                             ISSABasicBlock bb)

Returns:

a List of Instructions that may transfer control to bb via an exceptional edge

Throws:

java.lang.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,
                                   CallSiteReference site,
                                   IntSet parameters,
                                   VoidFunction<InstanceKey[]> f)

getTargetsForCall

protected java.util.Set<CGNode> getTargetsForCall(CGNode caller,
                                                  CallSiteReference site)

hasNoInterestingUses

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

makeInterestingVisitor

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

getTargetPointerKey

protected 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

protected 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 java.util.Iterator<PointerKey> iteratePointerKeys()

Specified by:

iteratePointerKeys in interface HeapModel

Returns:

an Iterator of all PointerKeys that are modeled.

getCaughtExceptionTypes

public static java.util.Set<IClass> getCaughtExceptionTypes(SSAGetCaughtExceptionInstruction instruction,
                                                            IR ir)

getInstanceKeyForPEI

public InstanceKey getInstanceKeyForPEI(CGNode node,
                                        ProgramCounter instr,
                                        TypeReference type)

Specified by:

getInstanceKeyForPEI in interface InstanceKeyFactory

Returns:

the instance key that represents the exception of type _type_ thrown by a particular PEI.

makeSolver

protected IPointsToSolver makeSolver()

Specified by:

makeSolver in class PropagationCallGraphBuilder