Package com.ibm.wala.ipa.callgraph.propagation

Class PropagationCallGraphBuilder

  • All Implemented Interfaces:
    CallGraphBuilder
    Direct Known Subclasses:
    AbstractRTABuilder, SSAPropagationCallGraphBuilder
    public abstract class PropagationCallGraphBuilder
extends Object
implements CallGraphBuilder
    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 Detail

      • pointerKeyFactory

        protected PointerKeyFactory pointerKeyFactory
        Meta-data regarding how pointers are modeled

      • 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

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

      • 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 Detail

      • PropagationCallGraphBuilder

        protected PropagationCallGraphBuilder​(IClassHierarchy cha,
                                      AnalysisOptions options,
                                      AnalysisCache cache,
                                      PointerKeyFactory pointerKeyFactory)
        Parameters:
        cha - governing class hierarchy
        options - governing call graph construction options
        pointerKeyFactory - factory which embodies pointer abstraction policy

    • Method Detail

      • isJavaLangObject

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

      • customInit

        protected void customInit()

      • 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.

      • 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

      • 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

      • getJavaLangObject

        public IClass getJavaLangObject()

      • setContextInterpreter

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

      • setPointerKeyFactory

        public void setPointerKeyFactory​(PointerKeyFactory pkFact)
        BEGIN Custom change: setter for pointerkey factory

      • getContextInterpreter

        public RTAContextInterpreter getContextInterpreter()
        END Custom change: setter for pointerkey factory

      • 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)

      • 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

      • 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