Class BoundedTabulationSolver<T,P,F>

java.lang.Object

com.ibm.wala.dataflow.IFDS.TabulationSolver<T,P,F>

com.ibm.wala.dataflow.IFDS.BoundedTabulationSolver<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

public class BoundedTabulationSolver<T,P,F>
extends TabulationSolver<T,P,F>

A TabulationSolver that gives up after a finite bound.

Nested Class Summary

Nested classes/interfaces inherited from class TabulationSolver

TabulationSolver.Result, TabulationSolver.Worklist

Modifier and Type	Class	Description
class	TabulationSolver.Result
protected class	TabulationSolver.Worklist

Field Summary

Fields inherited from class TabulationSolver

DEBUG_LEVEL, flowFunctionMap, PERIODIC_WIPE_SOFT_CACHES, progressMonitor, summaryEdges, supergraph, verbose

Modifier and Type	Field	Description
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
protected final IFlowFunctionMap<T>	flowFunctionMap	A map from an edge in a supergraph to a flow function
protected static final boolean	PERIODIC_WIPE_SOFT_CACHES	Should we periodically clear out soft reference caches in an attempt to help the GC?
protected final MonitorUtil.IProgressMonitor	progressMonitor	A progress monitor.
protected final Map<P, LocalSummaryEdges>	summaryEdges	A map from Object (procedure) -> LocalSummaryEdges.
protected final ISupergraph<T,P>	supergraph	The supergraph which induces this dataflow problem
protected static final boolean	verbose

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	BoundedTabulationSolver(TabulationProblem<T,P,F> p, int bound, MonitorUtil.IProgressMonitor monitor)

Method Summary

Modifier and Type	Method	Description
static <T,P,F> BoundedTabulationSolver<T,P,F>	createBoundedTabulationSolver(TabulationProblem<T,P,F> p, int bound, MonitorUtil.IProgressMonitor monitor)
int	getNumSteps()
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.
void	resetBound()

Methods inherited from class TabulationSolver

addSeed, addToWorkList, computeBinaryFlow, computeFlow, computeInverseFlow, findOrCreateCallFlowEdges, findOrCreateLocalPathEdges, findOrCreateLocalSummaryEdges, getCurPathEdge, getCurSummaryEdge, getInversePathEdges, getLocalPathEdges, getProblem, getProgressMonitor, getResult, getSeeds, getSummarySources, getSupergraph, initialize, make, makeWorklist, newCallExplodedEdge, newNormalExplodedEdge, newSummaryEdge, performVerboseAction, popFromWorkList, processCall, processExit, processParticularCallee, recordCall, solve, tendToSoftCaches

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 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	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	newSummaryEdge(PathEdge<T> edgeToCallSite, PathEdge<T> calleeSummaryEdge, T returnSite, int d5)	Combines [25] and [26-28].
protected final 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 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.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

BoundedTabulationSolver

protected BoundedTabulationSolver(TabulationProblem<T,P,F> p,
 int bound,
 MonitorUtil.IProgressMonitor monitor)

Method Details

createBoundedTabulationSolver

public static <T,P,F>
BoundedTabulationSolver<T,P,F> createBoundedTabulationSolver(TabulationProblem<T,P,F> p,
 int bound,
 MonitorUtil.IProgressMonitor monitor)

propagate

protected boolean propagate(T s_p,
 int i,
 T n,
 int j)

Description copied from class: TabulationSolver

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.

Overrides:

propagate in class TabulationSolver<T,P,F>

Parameters:

s_p - entry block

i - dataflow fact on entry

n - reached block

j - dataflow fact reached

getNumSteps

public int getNumSteps()

resetBound

public void resetBound()