Class PropagationCallGraphBuilder

java.lang.Object
com.ibm.wala.ipa.callgraph.propagation.PropagationCallGraphBuilder
All Implemented Interfaces:
CallGraphBuilder<InstanceKey>
Direct Known Subclasses:
AbstractRTABuilder, SSAPropagationCallGraphBuilder
public abstract class PropagationCallGraphBuilder extends Object implements CallGraphBuilder<InstanceKey>
This abstract base class provides the general algorithm for a call graph builder that relies on propagation through an iterative dataflow solver

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.

  • Field Details

    • DEBUG_GENERAL

      protected static final boolean DEBUG_GENERAL
      See Also:

    • pointerKeyFactory

      protected PointerKeyFactory pointerKeyFactory
      Meta-data regarding how pointers are modeled

    • cha

      public final IClassHierarchy cha
      Governing class hierarchy

    • options

      protected final AnalysisOptions options
      Special rules for bypassing Java calls

    • entrypointCallSites

      protected final Set<CallSiteReference> entrypointCallSites
      Set of calls (CallSiteReferences) that are created by entrypoints

    • system

      protected PropagationSystem system
      The system of constraints used to build this graph

    • callGraph

      protected final ExplicitCallGraph callGraph
      The call graph under construction

    • assignOperator

      public static final com.ibm.wala.ipa.callgraph.propagation.AssignOperator assignOperator
      Singleton operator for assignments

    • filterOperator

      public final PropagationCallGraphBuilder.FilterOperator filterOperator
      singleton operator for filter

    • inverseFilterOperator

      protected final PropagationCallGraphBuilder.InverseFilterOperator inverseFilterOperator
      singleton operator for inverse filter

    • contextSelector

      protected ContextSelector contextSelector
      A context selector which may use information derived from the propagation-based dataflow.

    • instanceKeyFactory

      protected InstanceKeyFactory instanceKeyFactory
      An object that abstracts how to model instances in the heap.

  • Constructor Details

    • PropagationCallGraphBuilder

      protected PropagationCallGraphBuilder(IMethod abstractRootMethod, AnalysisOptions options, IAnalysisCacheView cache, PointerKeyFactory pointerKeyFactory)
      Parameters:
      options - governing call graph construction options
      pointerKeyFactory - factory which embodies pointer abstraction policy

  • Method Details

    • getSystem

      public PropagationSystem getSystem()

    • createEmptyCallGraph

      protected ExplicitCallGraph createEmptyCallGraph(IMethod abstractRootMethod, AnalysisOptions options)

    • isJavaLangObject

      protected boolean isJavaLangObject(IClass klass)
      Returns:
      true iff the klass represents java.lang.Object

    • makeCallGraph

      public CallGraph makeCallGraph(AnalysisOptions options) throws IllegalArgumentException, CancelException
      Throws:
      IllegalArgumentException
      CancelException

    • makeCallGraph

      public CallGraph makeCallGraph(AnalysisOptions options, MonitorUtil.IProgressMonitor monitor) throws IllegalArgumentException, CallGraphBuilderCancelException
      Description copied from interface: CallGraphBuilder
      Build a call graph.
      Specified by:
      makeCallGraph in interface CallGraphBuilder<InstanceKey>
      Parameters:
      options - an object representing controlling options that the call graph building algorithm needs to know.
      Returns:
      the built call graph
      Throws:
      IllegalArgumentException
      CallGraphBuilderCancelException

    • makeSystem

      protected PropagationSystem makeSystem(AnalysisOptions options)

    • makeSolver

      protected abstract IPointsToSolver makeSolver()

    • customInit

      protected void customInit()

    • addConstraintsFromNode

      protected abstract boolean addConstraintsFromNode(CGNode n, MonitorUtil.IProgressMonitor monitor) throws CancelException
      Add constraints for a node.
      Returns:
      true iff any new constraints are added.
      Throws:
      CancelException

    • addConstraintsFromNewNodes

      protected boolean addConstraintsFromNewNodes(MonitorUtil.IProgressMonitor monitor) throws CancelException
      Add constraints from newly discovered nodes. Note: the act of adding constraints may discover new nodes, so this routine is iterative.
      Returns:
      true iff any new constraints are added.
      Throws:
      CancelException

    • getPointerKeyForLocal

      public PointerKey getPointerKeyForLocal(CGNode node, int valueNumber)
      Returns:
      the PointerKey that acts as a representative for the class of pointers that includes the local variable identified by the value number parameter.

    • getFilteredPointerKeyForLocal

      public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node, int valueNumber, FilteredPointerKey.TypeFilter filter)
      Returns:
      the PointerKey that acts as a representative for the class of pointers that includes the local variable identified by the value number parameter.

    • getFilteredPointerKeyForLocal

      public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node, int valueNumber, IClass filter)

    • getFilteredPointerKeyForLocal

      public FilteredPointerKey getFilteredPointerKeyForLocal(CGNode node, int valueNumber, InstanceKey filter)

    • getPointerKeyForReturnValue

      public PointerKey getPointerKeyForReturnValue(CGNode node)
      Returns:
      the PointerKey that acts as a representative for the class of pointers that includes the return value for a node

    • getPointerKeyForExceptionalReturnValue

      public PointerKey getPointerKeyForExceptionalReturnValue(CGNode node)
      Returns:
      the PointerKey that acts as a representative for the class of pointers that includes the exceptional return value

    • getPointerKeyForStaticField

      public PointerKey getPointerKeyForStaticField(IField f)
      Returns:
      the PointerKey that acts as a representative for the class of pointers that includes the contents of the static field

    • getPointerKeyForInstanceField

      public PointerKey getPointerKeyForInstanceField(InstanceKey I, IField field)
      Returns:
      the PointerKey that acts as a representation for the class of pointers that includes the given instance field. null if there's some problem.
      Throws:
      IllegalArgumentException - if I is null
      IllegalArgumentException - if field is null

    • getPointerKeyForArrayContents

      public PointerKey getPointerKeyForArrayContents(InstanceKey I)
      TODO: expand this API to differentiate between different array indices
      Parameters:
      I - an InstanceKey representing an abstract array
      Returns:
      the PointerKey that acts as a representation for the class of pointers that includes the given array contents, or null if none found.
      Throws:
      IllegalArgumentException - if I is null

    • assignInstanceToCatch

      protected void assignInstanceToCatch(PointerKey exceptionVar, Set<IClass> catchClasses, InstanceKey e)
      Handle assign of a particular exception instance into an exception variable
      Parameters:
      exceptionVar - points-to set for a variable representing a caught exception
      catchClasses - set of TypeReferences that the exceptionVar may catch
      e - a particular exception instance

    • addAssignmentsForCatchPointerKey

      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. Note that we use FilterOperator to filter out types that the exception handler doesn't catch.
      Parameters:
      exceptionVar - points-to set for a variable representing a caught exception
      catchClasses - set of TypeReferences that the exceptionVar may catch
      e - points-to-set representing a thrown exception that might be caught.

    • catches

      public static boolean catches(Set<IClass> catchClasses, IClass klass, IClassHierarchy cha)
      Parameters:
      catchClasses - Set of TypeReference
      klass - an Exception Class
      Returns:
      true iff klass is a subclass of some element of the Set
      Throws:
      IllegalArgumentException - if catchClasses is null

    • representsNullType

      public static boolean representsNullType(InstanceKey key) throws IllegalArgumentException
      Throws:
      IllegalArgumentException

    • getClassHierarchy

      public IClassHierarchy getClassHierarchy()
      Specified by:
      getClassHierarchy in interface CallGraphBuilder<InstanceKey>

    • getOptions

      public AnalysisOptions getOptions()

    • getJavaLangObject

      public IClass getJavaLangObject()

    • getCallGraph

      public ExplicitCallGraph getCallGraph()

    • setContextInterpreter

      public void setContextInterpreter(SSAContextInterpreter interpreter)
      Subclasses must register the context interpreter before building a call graph.

    • getPointerAnalysis

      public PointerAnalysis<InstanceKey> getPointerAnalysis()
      Specified by:
      getPointerAnalysis in interface CallGraphBuilder<InstanceKey>
      Returns:
      the Pointer Analysis information computed as a side-effect of call graph construction.

    • getPropagationSystem

      public PropagationSystem getPropagationSystem()

    • getPointerKeyFactory

      public PointerKeyFactory getPointerKeyFactory()

    • setPointerKeyFactory

      public void setPointerKeyFactory(PointerKeyFactory pkFact)

    • getContextInterpreter

      public RTAContextInterpreter getContextInterpreter()

    • getTargetForCall

      protected CGNode getTargetForCall(CGNode caller, CallSiteReference site, IClass recv, InstanceKey[] iKey)
      Parameters:
      caller - the caller node
      iKey - an abstraction of the receiver of the call (or null if not applicable)
      Returns:
      the CGNode to which this particular call should dispatch.

    • getContextSelector

      public ContextSelector getContextSelector()
      Returns:
      the context selector for this call graph builder

    • setContextSelector

      public void setContextSelector(ContextSelector selector)

    • getInstanceKeys

      public InstanceKeyFactory getInstanceKeys()

    • setInstanceKeys

      public void setInstanceKeys(InstanceKeyFactory keys)

    • getInstanceKeyForAllocation

      public InstanceKey getInstanceKeyForAllocation(CGNode node, NewSiteReference allocation)
      Returns:
      the InstanceKey that acts as a representative for the class of objects that includes objects allocated at the given new instruction in the given node

    • getInstanceKeyForMultiNewArray

      public InstanceKey getInstanceKeyForMultiNewArray(CGNode node, NewSiteReference allocation, int dim)
      Parameters:
      dim - the dimension of the array whose instance we would like to model. dim == 0 represents the first dimension, e.g., the [Object; instances in [[Object; e.g., the [[Object; instances in [[[Object; dim == 1 represents the second dimension, e.g., the [Object instances in [[[Object;
      Returns:
      the InstanceKey that acts as a representative for the class of array contents objects that includes objects allocated at the given new instruction in the given node

    • getInstanceKeyForConstant

      public <T> InstanceKey getInstanceKeyForConstant(TypeReference type, T S)

    • getInstanceKeyForMetadataObject

      public InstanceKey getInstanceKeyForMetadataObject(Object obj, TypeReference objType)

    • haveAlreadyVisited

      public boolean haveAlreadyVisited(CGNode node)

    • markAlreadyVisited

      protected void markAlreadyVisited(CGNode node)

    • markDiscovered

      public void markDiscovered(CGNode node)
      record that we've discovered a node

    • markChanged

      protected void markChanged(CGNode node)

    • wasChanged

      protected boolean wasChanged(CGNode node)

    • getMutableInstanceKeysForClass

      protected MutableIntSet getMutableInstanceKeysForClass(IClass klass)

    • getInstanceKeysForClass

      protected IntSet getInstanceKeysForClass(IClass klass)

    • filterForClass

      protected IntSet filterForClass(IntSet S, IClass klass)
      Parameters:
      klass - a class
      Returns:
      an int set which represents the subset of S that correspond to subtypes of klass

    • getSolver

      protected IPointsToSolver getSolver()

    • addConstraintsFromChangedNode

      public void addConstraintsFromChangedNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException
      Add constraints when the interpretation of a node changes (e.g. reflection)
      Throws:
      CancelException

    • unconditionallyAddConstraintsFromNode

      protected abstract boolean unconditionallyAddConstraintsFromNode(CGNode node, MonitorUtil.IProgressMonitor monitor) throws CancelException
      Throws:
      CancelException

    • getAnalysisCache

      public IAnalysisCacheView getAnalysisCache()
      Specified by:
      getAnalysisCache in interface CallGraphBuilder<InstanceKey>
      Returns:
      A cache of various analysis artifacts used during call graph construction.