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 java.lang.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

class	TabulationSolver.Result
protected class	TabulationSolver.Worklist

Field Summary

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 java.util.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

Constructor Summary

protected

TabulationSolver(TabulationProblem<T,P,F> p, MonitorUtil.IProgressMonitor monitor)

Method Summary

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
java.util.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, java.util.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 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 java.lang.Object

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

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 java.util.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:

java.lang.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:

java.lang.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,
                                       java.util.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:

callNode -

callee -

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 -> has arisen as a path edge. Returns true 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 java.lang.UnsupportedOperationException

Returns:

set of d1 s.t. (n1,d1) -> (n2,d2) is recorded as a summary edge, or null if none found

Throws:

java.lang.UnsupportedOperationException - unconditionally

getProblem

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

getSeeds

public java.util.Collection<PathEdge<T>> getSeeds()

getProgressMonitor

public MonitorUtil.IProgressMonitor getProgressMonitor()

getCurPathEdge

protected PathEdge<T> getCurPathEdge()

getCurSummaryEdge

protected PathEdge<T> getCurSummaryEdge()