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 problempublic class TabulationSolver<T,P,F> extends Object
See Reps, Horwitz, Sagiv POPL 95.
This version differs in some ways from the POPL algorithm. In particular ...
Modifier and Type | Class and Description |
---|---|
class |
TabulationSolver.Result |
protected class |
TabulationSolver.Worklist |
Modifier and Type | Field and 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 worklists
|
protected IFlowFunctionMap<T> |
flowFunctionMap
A map from an edge in a supergraph to a flow function
|
protected 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 problem
|
protected static boolean |
verbose |
Modifier | Constructor and Description |
---|---|
protected |
TabulationSolver(TabulationProblem<T,P,F> p,
MonitorUtil.IProgressMonitor monitor) |
Modifier and Type | Method and 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 node
|
Collection<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
|
protected void |
recordCall(T callNode,
T callee,
int d1,
boolean gotReuse)
invoked when a callee is processed with a particular entry fact
|
TabulationResult<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.
|
protected static final int DEBUG_LEVEL
protected static final boolean verbose
protected static final boolean PERIODIC_WIPE_SOFT_CACHES
protected final ISupergraph<T,P> supergraph
protected final IFlowFunctionMap<T> flowFunctionMap
protected final Map<P,LocalSummaryEdges> summaryEdges
protected final MonitorUtil.IProgressMonitor progressMonitor
protected TabulationSolver(TabulationProblem<T,P,F> p, MonitorUtil.IProgressMonitor monitor)
p
- a description of the dataflow problem to solveIllegalArgumentException
- if p is nullprotected ITabulationWorklist<T> makeWorklist()
public static <T,P,F> TabulationSolver<T,P,F> make(TabulationProblem<T,P,F> p)
p
- a description of the dataflow problem to solveIllegalArgumentException
- if p is nullpublic TabulationResult<T,P,F> solve() throws CancelException
CancelException
protected void initialize()
public void addSeed(PathEdge<T> seed)
protected void tendToSoftCaches()
protected final void performVerboseAction()
protected void processExit(PathEdge<T> edge)
protected IntSet getInversePathEdges(T s_p, T n, int d2)
s_p
- n
- d2
- note that s_p must be an entry for procof(n)protected void processCall(PathEdge<T> edge)
protected void processParticularCallee(PathEdge<T> edge, int callNodeNum, Collection<T> allReturnSites, T calleeEntry)
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 questionprotected void recordCall(T callNode, T callee, int d1, boolean gotReuse)
callNode
- callee
- d1
- the entry factgotReuse
- whether existing summary edges were appliedprotected 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 boolean propagate(T s_p, int i, T n, int j)
true
iff the path edge was not previously
observed.s_p
- entry blocki
- dataflow fact on entryn
- reached blockj
- dataflow fact reachedpublic LocalPathEdges getLocalPathEdges(T s_p)
protected LocalPathEdges findOrCreateLocalPathEdges(T s_p)
protected LocalSummaryEdges findOrCreateLocalSummaryEdges(P proc)
protected CallFlowEdges findOrCreateCallFlowEdges(T s_p)
public IntSet getResult(T node)
public ISupergraph<T,P> getSupergraph()
public IntSet getSummarySources(T n2, int d2, T n1) throws UnsupportedOperationException
UnsupportedOperationException
- unconditionallypublic TabulationProblem<T,P,F> getProblem()
public Collection<PathEdge<T>> getSeeds()
public MonitorUtil.IProgressMonitor getProgressMonitor()