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 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
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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
TabulationSolver.Result
protected class
TabulationSolver.Worklist
-
Field Summary
Fields Modifier and Type Field Description protected static int
DEBUG_LEVEL
DEBUG_LEVEL: 0 No output 1 Print some simple stats and warning information 2 Detailed debugging 3 Also print worklistsprotected IFlowFunctionMap<T>
flowFunctionMap
A map from an edge in a supergraph to a flow functionprotected static boolean
PERIODIC_WIPE_SOFT_CACHES
Should we periodically clear out soft reference caches in an attempt to help the GC?protected MonitorUtil.IProgressMonitor
progressMonitor
A progress monitor.protected Map<P,LocalSummaryEdges>
summaryEdges
A map from Object (procedure) -> LocalSummaryEdges.protected ISupergraph<T,P>
supergraph
The supergraph which induces this dataflow problemprotected static boolean
verbose
-
Constructor Summary
Constructors Modifier Constructor Description protected
TabulationSolver(TabulationProblem<T,P,F> p, MonitorUtil.IProgressMonitor monitor)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addSeed(PathEdge<T> seed)
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
findOrCreateCallFlowEdges(T s_p)
protected LocalPathEdges
findOrCreateLocalPathEdges(T s_p)
protected LocalSummaryEdges
findOrCreateLocalSummaryEdges(P proc)
protected PathEdge<T>
getCurPathEdge()
protected PathEdge<T>
getCurSummaryEdge()
protected IntSet
getInversePathEdges(T s_p, T n, int d2)
LocalPathEdges
getLocalPathEdges(T s_p)
TabulationProblem<T,P,F>
getProblem()
MonitorUtil.IProgressMonitor
getProgressMonitor()
IntSet
getResult(T node)
get the bitvector of facts that hold at the entry to a given nodeCollection<PathEdge<T>>
getSeeds()
IntSet
getSummarySources(T n2, int d2, T n1)
ISupergraph<T,P>
getSupergraph()
protected void
initialize()
Start tabulation with the initial seeds.static <T,P,F>
TabulationSolver<T,P,F>make(TabulationProblem<T,P,F> p)
protected ITabulationWorklist<T>
makeWorklist()
Subclasses can override this to plug in a different worklist implementation.protected void
performVerboseAction()
protected PathEdge<T>
popFromWorkList()
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(T s_p, int i, T n, int j)
Propagate the fact-> 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 factTabulationResult<T,P,F>
solve()
Solve the dataflow problem.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.
-
-
-
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.
-
progressMonitor
protected final MonitorUtil.IProgressMonitor progressMonitor
A progress monitor. can be null.
-
-
Constructor Detail
-
TabulationSolver
protected TabulationSolver(TabulationProblem<T,P,F> p, MonitorUtil.IProgressMonitor monitor)
- Parameters:
p
- a description of the dataflow problem to solve- Throws:
IllegalArgumentException
- if p is null
-
-
Method Detail
-
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:
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 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
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 factgotReuse
- 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)
-
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 blocki
- dataflow fact on entryn
- reached blockj
- dataflow fact reached
-
getLocalPathEdges
public LocalPathEdges getLocalPathEdges(T s_p)
-
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()
-
-