Package com.ibm.wala.dataflow.IFDS

Class TabulationSolver<T,​P,​F>

  • Type Parameters:
    T - type of node in the supergraph
    P - type of a procedure (like a box in an RSM)
    F - type of factoids propagated when solving this problem
    Direct Known Subclasses:
    BoundedTabulationSolver, PartiallyBalancedTabulationSolver
    public class TabulationSolver<T,​P,​F>
extends Object
    A precise interprocedural tabulation solver.

    See Reps, Horwitz, Sagiv POPL 95.

    This version differs in some ways from the POPL algorithm. In particular ...

    • to support exceptional control flow ... there may be several return sites for each call site.
    • it supports an optional merge operator, useful for non-IFDS problems and widening.
    • it stores summary edges at each callee instead of at each call site.

    • Field Detail

      • DEBUG_LEVEL

        protected static final int DEBUG_LEVEL
        DEBUG_LEVEL:
        • 0 No output
        • 1 Print some simple stats and warning information
        • 2 Detailed debugging
        • 3 Also print worklists
        See Also:
        Constant Field Values

      • verbose

        protected static final boolean verbose

      • PERIODIC_WIPE_SOFT_CACHES

        protected 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

      • supergraph

        protected final ISupergraph<T,​P> supergraph
        The supergraph which induces this dataflow problem

      • flowFunctionMap

        protected final IFlowFunctionMap<T> flowFunctionMap
        A map from an edge in a supergraph to a flow function

      • summaryEdges

        protected final Map<P,​LocalSummaryEdges> summaryEdges
        A map from Object (procedure) -> LocalSummaryEdges.

    • Method Detail

      • makeWorklist

        protected ITabulationWorklist<T> makeWorklist()
        Subclasses can override this to plug in a different worklist implementation.

      • initialize

        protected void initialize()
        Start tabulation with the initial seeds.

      • addSeed

        public void addSeed​(PathEdge<T> seed)
        Restart tabulation from a particular path edge. Use with care.

      • tendToSoftCaches

        protected void tendToSoftCaches()
        For some reason (either a bug in our code that defeats soft references, or a bad policy in the GC), leaving soft reference caches to clear themselves out doesn't work. Help it out. It's unfortunate that this method exits.

      • performVerboseAction

        protected final void performVerboseAction()

      • processExit

        protected void processExit​(PathEdge<T> edge)
        Handle lines [21 - 32] of the algorithm, propagating information from an exit node. Note that we've changed the way we record summary edges. Summary edges are now associated with a callee (s_p,exit), where the original algorithm used a call, return pair in the caller.

      • getInversePathEdges

        protected IntSet getInversePathEdges​(T s_p,
                                     T n,
                                     int d2)
        Parameters:
        s_p -
        n -
        d2 - note that s_p must be an entry for procof(n)
        Returns:
        set of d1 s.t. -> is a path edge, or null if none found

      • processCall

        protected void processCall​(PathEdge<T> edge)
        Handle lines [14 - 19] of the algorithm, propagating information into and across a call site.

      • processParticularCallee

        protected void processParticularCallee​(PathEdge<T> edge,
                                       int callNodeNum,
                                       Collection<T> allReturnSites,
                                       T calleeEntry)
        handle a particular callee for some call node.
        Parameters:
        edge - the path edge being processed
        callNodeNum - the number of the call node in the supergraph
        allReturnSites - a set collecting return sites for the call. This set is mutated with the return sites for this callee.
        calleeEntry - the entry node of the callee in question

      • recordCall

        protected void recordCall​(T callNode,
                          T callee,
                          int d1,
                          boolean gotReuse)
        invoked when a callee is processed with a particular entry fact
        Parameters:
        callNode -
        callee -
        d1 - the entry fact
        gotReuse - whether existing summary edges were applied

      • popFromWorkList

        protected PathEdge<T> popFromWorkList()

      • propagate

        protected boolean propagate​(T s_p,
                            int i,
                            T n,
                            int j)
        Propagate the fact -> has arisen as a path edge. Returns true iff the path edge was not previously observed.
        Parameters:
        s_p - entry block
        i - dataflow fact on entry
        n - reached block
        j - dataflow fact reached

      • addToWorkList

        protected void addToWorkList​(T s_p,
                             int i,
                             T n,
                             int j)

      • findOrCreateLocalPathEdges

        protected LocalPathEdges findOrCreateLocalPathEdges​(T s_p)

      • findOrCreateLocalSummaryEdges

        protected LocalSummaryEdges findOrCreateLocalSummaryEdges​(P proc)

      • findOrCreateCallFlowEdges

        protected CallFlowEdges findOrCreateCallFlowEdges​(T s_p)

      • getResult

        public IntSet getResult​(T node)
        get the bitvector of facts that hold at the entry to a given node
        Returns:
        IntSet representing the bitvector

      • getSupergraph

        public ISupergraph<T,​P> getSupergraph()
        Returns:
        Returns the supergraph.

      • getCurPathEdge

        protected PathEdge<T> getCurPathEdge()

      • getCurSummaryEdge

        protected PathEdge<T> getCurSummaryEdge()