Package com.ibm.wala.dataflow.IFDS

Class TabulationSolver<T,P,F>

java.lang.Object
com.ibm.wala.dataflow.IFDS.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 Details

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

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

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

    • progressMonitor

      protected final MonitorUtil.IProgressMonitor progressMonitor
      A progress monitor. can be null.

  • Constructor Details

  • Method Details

    • makeWorklist

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

    • make

      public static <T, P, F> TabulationSolver<T,P,F> make(TabulationProblem<T,P,F> p)
      Parameters:
      p - a description of the dataflow problem to solve
      Throws:
      IllegalArgumentException - if p is null

    • solve

      public TabulationResult<T,P,F> solve() throws CancelException
      Solve the dataflow problem.
      Returns:
      a representation of the result
      Throws:
      CancelException

    • 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:
      d2 - note that s_p must be an entry for procof(n)
      Returns:
      set of d1 s.t. <s_p, d1> -> <n, d2> 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:
      d1 - the entry fact
      gotReuse - whether existing summary edges were applied

    • computeBinaryFlow

      protected IntSet computeBinaryFlow(int call_d, int exit_d, IBinaryReturnFlowFunction f)
      Returns:
      f(call_d, exit_d);

    • computeFlow

      protected IntSet computeFlow(int d1, IUnaryFlowFunction f)
      Returns:
      f(d1)

    • computeInverseFlow

      protected IntSet computeInverseFlow(int d2, IReversibleFlowFunction f)
      Returns:
      f^{-1}(d2)

    • popFromWorkList

      protected PathEdge<T> popFromWorkList()

    • propagate

      protected boolean propagate(T s_p, int i, T n, int j)
      Propagate the fact <s_p,i> -> <n, j> has arisen as a path edge. Returns <code>true</code> 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

    • getLocalPathEdges

      public LocalPathEdges getLocalPathEdges(T s_p)

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

    • getSummarySources

      public IntSet getSummarySources(T n2, int d2, T n1) throws UnsupportedOperationException
      Returns:
      set of d1 s.t. (n1,d1) -> (n2,d2) is recorded as a summary edge, or null if none found
      Throws:
      UnsupportedOperationException - unconditionally

    • getProblem

      public TabulationProblem<T,P,F> getProblem()

    • getSeeds

      public Collection<PathEdge<T>> getSeeds()

    • getProgressMonitor

      public MonitorUtil.IProgressMonitor getProgressMonitor()

    • getCurPathEdge

      protected PathEdge<T> getCurPathEdge()

    • getCurSummaryEdge

      protected PathEdge<T> getCurSummaryEdge()

    • newNormalExplodedEdge

      protected void newNormalExplodedEdge(PathEdge<T> edge, T m, int d3)
      Indicates that due to a path edge <s_p, d1> -> <n, d2> (the 'edge' parameter) and a normal flow function application, a new path edge <s_p, d1> -> <m, d3> was created. To be overridden in subclasses. We also use this function to record call-to-return flow.

    • newCallExplodedEdge

      protected void newCallExplodedEdge(PathEdge<T> edge, T calleeEntry, int d3)
      Indicates that due to a path edge 'edge' <s_p, d1> -> <n, d2> and application of a call flow function, a new path edge <calleeEntry, d3> -> <calleeEntry, d3> was created. To be overridden in subclasses.

    • newSummaryEdge

      protected void newSummaryEdge(PathEdge<T> edgeToCallSite, PathEdge<T> calleeSummaryEdge, T returnSite, int d5)
      Combines [25] and [26-28]. In the caller we have a path edge 'edgeToCallSite' <s_c, d3> -> <c, d4>, where c is the call site. In the callee, we have path edge 'calleeSummaryEdge' <s_p, d1> -> <e_p, d2>. Of course, there is a call edge <c, d4> -> <s_p, d1>. Finally, we have a return edge <e_p, d2> -> <returnSite, d5>.