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, CFABuilder

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 class	SSAPropagationCallGraphBuilder.ConstraintVisitor A visitor that generates constraints based on statements in SSA form.
protected static class	SSAPropagationCallGraphBuilder.InterestingVisitor

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, CUTOFF, DEBUG_GENERAL, entrypointCallSites, filterOperator, instanceKeyFactory, inverseFilterOperator, options, pointerKeyFactory, system, THROWABLE_SET

Constructor Summary

protected

SSAPropagationCallGraphBuilder(ClassHierarchy cha, WarningSet warnings, AnalysisOptions options, PointerKeyFactory pointerKeyFactory)

Method Summary

protected void	addBlockInstructionConstraints(CGNode node, ControlFlowGraph cfg, SSACFG.BasicBlock b, SSAPropagationCallGraphBuilder.ConstraintVisitor v) Add constraints for a particular basic block.
protected boolean	addConstraintsFromNode(CGNode node) Visit all instructions in a node, and add dataflow constraints induced by each statement in the SSA form.
protected void	addNodeInstructionConstraints(CGNode node, IR ir, DefUse du) 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.
static java.util.Set<TypeReference>	getCaughtExceptionTypes(SSAGetCaughtExceptionInstruction instruction, IR ir)
SSAContextInterpreter	getCFAContextInterpreter()
static java.util.List<ProgramCounter>	getIncomingPEIs(IR ir, IBasicBlock 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	getUniqueCatchKey(SSAAbstractInvokeInstruction call, IR ir, CGNode node) precondition: hasUniqueCatchBlock(call,node,cg)
boolean	hasNoInterestingUses(int vn, DefUse du)
protected static boolean	hasUniqueCatchBlock(SSAAbstractInvokeInstruction call, IR ir)
protected boolean	isConstantRef(SymbolTable symbolTable, int valueNumber)
java.util.Iterator	iteratePointerKeys()
protected SSAPropagationCallGraphBuilder.InterestingVisitor	makeInterestingVisitor(int vn)
protected IPointsToSolver	makeSolver()
protected SSAPropagationCallGraphBuilder.ConstraintVisitor	makeVisitor(ExplicitCallGraph.ExplicitNode node, IR ir, DefUse du, ExplicitCallGraph callGraph)
protected boolean	unconditionallyAddConstraintsFromNode(CGNode node)

Methods inherited from class com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder

addAssignmentsForCatchPointerKey, addConstraintsFromChangedNode, addConstraintsFromNewNodes, assignInstanceToCatch, catches, createEmptyCallGraph, customInit, filterForClass, findOrCreateBoundFromClassHierarchy, getBoundOnNumberOfTargets, getCallGraph, getClassHierarchy, getContextInterpreter, getContextSelector, getDefaultDispatchBoundHeuristic, getFilteredPointerKeyForLocal, getFilteredPointerKeyForLocal, getFilteredPointerKeyForLocal, getInstanceKeyForAllocation, getInstanceKeyForClassObject, getInstanceKeyForConstant, getInstanceKeyForMultiNewArray, getInstanceKeys, getInstanceKeysForClass, getJavaLangObject, getJavaLangThrowable, getMutableInstanceKeysForClass, getOptions, getPointerAnalysis, getPointerFlowGraphFactory, getPointerKeyFactory, getPointerKeyForArrayContents, getPointerKeyForExceptionalReturnValue, getPointerKeyForInstanceField, getPointerKeyForLocal, getPointerKeyForReturnValue, getPointerKeyForStaticField, getPropagationSystem, getSolver, getStringConstantForInstanceKey, getTargetForCall, getWarnings, haveAlreadyVisited, isJavaLangObject, makeCallGraph, makeSystem, markAlreadyVisited, markChanged, markDiscovered, setContextInterpreter, setContextSelector, setInstanceKeys, setWarnings, 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, getStringConstantForInstanceKey

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(ClassHierarchy cha,
                                         WarningSet warnings,
                                         AnalysisOptions options,
                                         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)

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.

See Also:

PropagationCallGraphBuilder.addConstraintsFromNode(com.ibm.wala.ipa.callgraph.CGNode)

unconditionallyAddConstraintsFromNode

protected boolean unconditionallyAddConstraintsFromNode(CGNode node)

Specified by:

unconditionallyAddConstraintsFromNode in class PropagationCallGraphBuilder

Parameters:

node -

makeVisitor

protected SSAPropagationCallGraphBuilder.ConstraintVisitor makeVisitor(ExplicitCallGraph.ExplicitNode node,
                                                                       IR ir,
                                                                       DefUse du,
                                                                       ExplicitCallGraph callGraph)

Parameters:

node -

ir -

callGraph -

Returns:

a visitor to examine instructions in the ir

addNodeInstructionConstraints

protected void addNodeInstructionConstraints(CGNode node,
                                             IR ir,
                                             DefUse du)

Add pointer flow constraints based on instructions in a given node

Parameters:

node -

ir -

addBlockInstructionConstraints

protected void addBlockInstructionConstraints(CGNode node,
                                              ControlFlowGraph cfg,
                                              SSACFG.BasicBlock b,
                                              SSAPropagationCallGraphBuilder.ConstraintVisitor v)

Add constraints for a particular basic block.

Parameters:

node -

cfg -

b -

v -

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)

Parameters:

call -

ir -

Returns:

true iff there's a unique catch block which catches all exceptions thrown by a certain call site.

getUniqueCatchKey

protected PointerKey getUniqueCatchKey(SSAAbstractInvokeInstruction call,
                                       IR ir,
                                       CGNode node)

precondition: hasUniqueCatchBlock(call,node,cg)

Returns:

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

getIncomingPEIs

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

Returns:

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

Throws:

java.lang.IllegalArgumentException - if ir is null

hasNoInterestingUses

public boolean hasNoInterestingUses(int vn,
                                    DefUse du)

makeInterestingVisitor

protected SSAPropagationCallGraphBuilder.InterestingVisitor makeInterestingVisitor(int vn)

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

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 iteratePointerKeys()

Specified by:

iteratePointerKeys in interface HeapModel

Returns:

an Iterator of all PointerKeys that are modelled.

getCaughtExceptionTypes

public static java.util.Set<TypeReference> 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