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 supergraphP
- type of a procedure (like a box in an RSM)F
- type of factoids propagated when solving this problem
- Direct Known Subclasses:
BoundedTabulationSolver
,PartiallyBalancedTabulationSolver
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.
-
Nested Class Summary
Modifier and TypeClassDescriptionclass
protected class
-
Field Summary
Modifier and TypeFieldDescriptionprotected static final int
DEBUG_LEVEL: 0 No output 1 Print some simple stats and warning information 2 Detailed debugging 3 Also print worklistsprotected final IFlowFunctionMap
<T> A map from an edge in a supergraph to a flow functionprotected static final boolean
Should we periodically clear out soft reference caches in an attempt to help the GC?protected final MonitorUtil.IProgressMonitor
A progress monitor.protected final Map
<P, LocalSummaryEdges> A map from Object (procedure) -> LocalSummaryEdges.protected final ISupergraph
<T, P> The supergraph which induces this dataflow problemprotected static final boolean
-
Constructor Summary
ModifierConstructorDescriptionprotected
TabulationSolver
(TabulationProblem<T, P, F> p, MonitorUtil.IProgressMonitor monitor) -
Method Summary
Modifier and TypeMethodDescriptionvoid
Restart tabulation from a particular path edge.protected void
addToWorkList
(T s_p, int i, T n, int j) protected IntSet
computeBinaryFlow
(int call_d, int exit_d, IBinaryReturnFlowFunction f) protected IntSet
computeFlow
(int d1, IUnaryFlowFunction f) protected IntSet
computeInverseFlow
(int d2, IReversibleFlowFunction f) protected CallFlowEdges
protected LocalPathEdges
protected LocalSummaryEdges
protected IntSet
getInversePathEdges
(T s_p, T n, int d2) getLocalPathEdges
(T s_p) get the bitvector of facts that hold at the entry to a given nodegetSeeds()
getSummarySources
(T n2, int d2, T n1) protected void
Start tabulation with the initial seeds.static <T,
P, F> TabulationSolver <T, P, F> make
(TabulationProblem<T, P, F> p) protected ITabulationWorklist
<T> Subclasses can override this to plug in a different worklist implementation.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.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.protected void
Combines [25] and [26-28].protected final void
protected void
processCall
(PathEdge<T> edge) Handle lines [14 - 19] of the algorithm, propagating information into and across a call site.protected void
processExit
(PathEdge<T> edge) Handle lines [21 - 32] of the algorithm, propagating information from an exit node.protected void
processParticularCallee
(PathEdge<T> edge, int callNodeNum, Collection<T> allReturnSites, T calleeEntry) handle a particular callee for some call node.protected boolean
Propagate the fact <s_p,i> -> <n, j> has arisen as a path edge.protected void
recordCall
(T callNode, T callee, int d1, boolean gotReuse) invoked when a callee is processed with a particular entry factsolve()
Solve the dataflow problem.protected void
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.
-
Field Details
-
DEBUG_LEVEL
protected static final int DEBUG_LEVELDEBUG_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_CACHESShould we periodically clear out soft reference caches in an attempt to help the GC?- See Also:
-
supergraph
The supergraph which induces this dataflow problem -
flowFunctionMap
A map from an edge in a supergraph to a flow function -
summaryEdges
A map from Object (procedure) -> LocalSummaryEdges. -
progressMonitor
A progress monitor. can be null.
-
-
Constructor Details
-
TabulationSolver
- Parameters:
p
- a description of the dataflow problem to solve- Throws:
IllegalArgumentException
- if p is null
-
-
Method Details
-
makeWorklist
Subclasses can override this to plug in a different worklist implementation. -
make
- Parameters:
p
- a description of the dataflow problem to solve- Throws:
IllegalArgumentException
- if p is null
-
solve
Solve the dataflow problem.- Returns:
- a representation of the result
- Throws:
CancelException
-
initialize
protected void initialize()Start tabulation with the initial seeds. -
addSeed
-
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
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
-
processCall
-
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 processedcallNodeNum
- the number of the call node in the supergraphallReturnSites
- 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
-
computeBinaryFlow
- Returns:
- f(call_d, exit_d);
-
computeFlow
- Returns:
- f(d1)
-
computeInverseFlow
- Returns:
- f^{-1}(d2)
-
popFromWorkList
-
propagate
-
getLocalPathEdges
-
addToWorkList
-
findOrCreateLocalPathEdges
-
findOrCreateLocalSummaryEdges
-
findOrCreateCallFlowEdges
-
getResult
-
getSupergraph
- Returns:
- Returns the supergraph.
-
getSummarySources
- 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
-
getSeeds
-
getProgressMonitor
-
getCurPathEdge
-
getCurSummaryEdge
-
newNormalExplodedEdge
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
-
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>.
-