heros.solver

Class IDESolver<N,D,M,V,I extends InterproceduralCFG<N,M>>

java.lang.Object

heros.solver.IDESolver<N,D,M,V,I>

Type Parameters:

N - The type of nodes in the interprocedural control-flow graph.

D - The type of data-flow facts to be computed by the tabulation problem.

M - The type of objects used to represent methods.

V - The type of values to be computed along flow edges.

I - The type of inter-procedural control-flow graph being used.

Direct Known Subclasses:

BiDiIDESolver.SingleDirectionSolver, IFDSSolver, JimpleIDESolver

public class IDESolver<N,D,M,V,I extends InterproceduralCFG<N,M>>
extends java.lang.Object

Solves the given IDETabulationProblem as described in the 1996 paper by Sagiv, Horwitz and Reps. To solve the problem, call solve(). Results can then be queried by using resultAt(Object, Object) and resultsAt(Object). Note that this solver and its data structures internally use mostly LinkedHashSets instead of normal HashSets to fix the iteration order as much as possible. This is to produce, as much as possible, reproducible benchmarking results. We have found that the iteration order can matter a lot in terms of speed.

Field Summary

Fields

Modifier and Type	Field and Description
protected EdgeFunction<V>	allTop
protected <any>	computedInterPEdges
protected <any>	computedIntraPEdges
protected boolean	computeValues
static boolean	DEBUG
static <any>	DEFAULT_CACHE_BUILDER
long	durationFlowFunctionApplication
long	durationFlowFunctionConstruction
protected EdgeFunctions<N,D,M,V>	edgeFunctions
protected EdgeFunctionCache<N,D,M,V>	efCache
protected <any>	endSummary
protected CountingThreadPoolExecutor	executor
protected FlowFunctionCache<N,D,M>	ffCache
long	flowFunctionApplicationCount
long	flowFunctionConstructionCount
protected FlowFunctions<N,D,M>	flowFunctions
protected boolean	followReturnsPastSeeds
protected I	icfg
protected <any>	incoming
protected java.util.Map<N,java.util.Set<D>>	initialSeeds
protected JumpFunctions<N,D,V>	jumpFn
protected static Logger	logger
protected int	numThreads
long	propagationCount
protected java.util.Set<N>	unbalancedRetSites
protected <any>	val
protected JoinLattice<V>	valueLattice
protected D	zeroValue

Constructor Summary

Constructors

Constructor and Description
IDESolver(IDETabulationProblem<N,D,M,V,I> tabulationProblem) Creates a solver for the given problem, which caches flow functions and edge functions.
IDESolver(IDETabulationProblem<N,D,M,V,I> tabulationProblem, CacheBuilder flowFunctionCacheBuilder, CacheBuilder edgeFunctionCacheBuilder) Creates a solver for the given problem, constructing caches with the given CacheBuilder.

Method Summary

Modifier and Type	Method and Description
protected void	addIncoming(N sP, D d3, N n, D d2)
protected void	awaitCompletionComputeValuesAndShutdown() Awaits the completion of the exploded super graph.
protected java.util.Set<D>	computeCallFlowFunction(FlowFunction<D> callFlowFunction, D d1, D d2) Computes the call flow function for the given call-site abstraction
protected java.util.Set<D>	computeCallToReturnFlowFunction(FlowFunction<D> callToReturnFlowFunction, D d1, D d2) Computes the call-to-return flow function for the given call-site abstraction
protected java.util.Set<D>	computeNormalFlowFunction(FlowFunction<D> flowFunction, D d1, D d2) Computes the normal flow function for the given set of start and end abstractions-
protected java.util.Set<D>	computeReturnFlowFunction(FlowFunction<D> retFunction, D d1, D d2, N callSite, java.util.Set<D> callerSideDs) Computes the return flow function for the given set of caller-side abstractions.
protected java.util.Set<<any>>	endSummary(N sP, D d3)
protected java.lang.String	getDebugName() Returns a String used to identify the output of this solver in debug mode.
protected CountingThreadPoolExecutor	getExecutor() Factory method for this solver's thread-pool executor.
protected java.util.Map<N,java.util.Set<D>>	incoming(D d1, N sP)
protected V	joinValueAt(N unit, D fact, V curr, V newVal)
void	printStats()
protected void	processExit(PathEdge<N,D> edge) Lines 21-32 of the algorithm.
protected void	propagate(D sourceVal, N target, D targetVal, EdgeFunction<V> f, N relatedCallSite, boolean isUnbalancedReturn) Propagates the flow further down the exploded super graph, merging any edge function that might already have been computed for targetVal at target.
protected void	propagateUnbalancedReturnFlow(N retSiteC, D targetVal, EdgeFunction<V> edgeFunction, N relatedCallSite)
protected D	restoreContextOnReturnedFact(N callSite, D d4, D d5) This method will be called for each incoming edge and can be used to transfer knowledge from the calling edge to the returning edge, without affecting the summary edges at the callee.
V	resultAt(N stmt, D value) Returns the V-type result for the given value at the given statement.
java.util.Map<D,V>	resultsAt(N stmt) Returns the resulting environment for the given statement.
protected void	scheduleEdgeProcessing(PathEdge<N,D> edge) Dispatch the processing of a given edge.
void	solve() Runs the solver on the configured problem.
protected void	submitInitialSeeds() Schedules the processing of initial seeds, initiating the analysis.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_CACHE_BUILDER

public static <any> DEFAULT_CACHE_BUILDER

logger

protected static final Logger logger

computedIntraPEdges

protected <any> computedIntraPEdges

computedInterPEdges

protected <any> computedInterPEdges

DEBUG

public static final boolean DEBUG

executor

protected CountingThreadPoolExecutor executor

numThreads

protected int numThreads

jumpFn

protected final JumpFunctions<N,D,V> jumpFn

icfg

protected final I extends InterproceduralCFG<N,M> icfg

endSummary

protected final <any> endSummary

incoming

protected final <any> incoming

unbalancedRetSites

protected final java.util.Set<N> unbalancedRetSites

flowFunctions

protected final FlowFunctions<N,D,M> flowFunctions

edgeFunctions

protected final EdgeFunctions<N,D,M,V> edgeFunctions

initialSeeds

protected final java.util.Map<N,java.util.Set<D>> initialSeeds

valueLattice

protected final JoinLattice<V> valueLattice

allTop

protected final EdgeFunction<V> allTop

val

protected final <any> val

flowFunctionApplicationCount

public long flowFunctionApplicationCount

flowFunctionConstructionCount

public long flowFunctionConstructionCount

propagationCount

public long propagationCount

durationFlowFunctionConstruction

public long durationFlowFunctionConstruction

durationFlowFunctionApplication

public long durationFlowFunctionApplication

zeroValue

protected final D zeroValue

ffCache

protected final FlowFunctionCache<N,D,M> ffCache

efCache

protected final EdgeFunctionCache<N,D,M,V> efCache

followReturnsPastSeeds

protected final boolean followReturnsPastSeeds

computeValues

protected final boolean computeValues

Constructor Detail

IDESolver

public IDESolver(IDETabulationProblem<N,D,M,V,I> tabulationProblem)

Creates a solver for the given problem, which caches flow functions and edge functions. The solver must then be started by calling solve().

IDESolver

public IDESolver(IDETabulationProblem<N,D,M,V,I> tabulationProblem,
                 CacheBuilder flowFunctionCacheBuilder,
                 CacheBuilder edgeFunctionCacheBuilder)

Creates a solver for the given problem, constructing caches with the given CacheBuilder. The solver must then be started by calling solve().

Parameters:

flowFunctionCacheBuilder - A valid CacheBuilder or null if no caching is to be used for flow functions.

edgeFunctionCacheBuilder - A valid CacheBuilder or null if no caching is to be used for edge functions.

Method Detail

solve

public void solve()

Runs the solver on the configured problem. This can take some time.

submitInitialSeeds

protected void submitInitialSeeds()

Schedules the processing of initial seeds, initiating the analysis. Clients should only call this methods if performing synchronization on their own. Normally, solve() should be called instead.

awaitCompletionComputeValuesAndShutdown

protected void awaitCompletionComputeValuesAndShutdown()

Awaits the completion of the exploded super graph. When complete, computes result values, shuts down the executor and returns.

scheduleEdgeProcessing

protected void scheduleEdgeProcessing(PathEdge<N,D> edge)

Dispatch the processing of a given edge. It may be executed in a different thread.

Parameters:

edge - the edge to process

computeCallFlowFunction

protected java.util.Set<D> computeCallFlowFunction(FlowFunction<D> callFlowFunction,
                                                   D d1,
                                                   D d2)

Computes the call flow function for the given call-site abstraction

Parameters:

callFlowFunction - The call flow function to compute

d1 - The abstraction at the current method's start node.

d2 - The abstraction at the call site

Returns:

The set of caller-side abstractions at the callee's start node

computeCallToReturnFlowFunction

protected java.util.Set<D> computeCallToReturnFlowFunction(FlowFunction<D> callToReturnFlowFunction,
                                                           D d1,
                                                           D d2)

Computes the call-to-return flow function for the given call-site abstraction

Parameters:

callToReturnFlowFunction - The call-to-return flow function to compute

d1 - The abstraction at the current method's start node.

d2 - The abstraction at the call site

Returns:

The set of caller-side abstractions at the return site

processExit

protected void processExit(PathEdge<N,D> edge)

Lines 21-32 of the algorithm. Stores callee-side summaries. Also, at the side of the caller, propagates intra-procedural flows to return sites using those newly computed summaries.

Parameters:

edge - an edge whose target node resembles a method exits

propagateUnbalancedReturnFlow

protected void propagateUnbalancedReturnFlow(N retSiteC,
                                             D targetVal,
                                             EdgeFunction<V> edgeFunction,
                                             N relatedCallSite)

restoreContextOnReturnedFact

protected D restoreContextOnReturnedFact(N callSite,
                                         D d4,
                                         D d5)

This method will be called for each incoming edge and can be used to transfer knowledge from the calling edge to the returning edge, without affecting the summary edges at the callee.

Parameters:

callSite -

d4 - Fact stored with the incoming edge, i.e., present at the caller side

d5 - Fact that originally should be propagated to the caller.

Returns:

Fact that will be propagated to the caller.

computeReturnFlowFunction

protected java.util.Set<D> computeReturnFlowFunction(FlowFunction<D> retFunction,
                                                     D d1,
                                                     D d2,
                                                     N callSite,
                                                     java.util.Set<D> callerSideDs)

Computes the return flow function for the given set of caller-side abstractions.

Parameters:

retFunction - The return flow function to compute

d1 - The abstraction at the beginning of the callee

d2 - The abstraction at the exit node in the callee

callSite - The call site

callerSideDs - The abstractions at the call site

Returns:

The set of caller-side abstractions at the return site

computeNormalFlowFunction

protected java.util.Set<D> computeNormalFlowFunction(FlowFunction<D> flowFunction,
                                                     D d1,
                                                     D d2)

Computes the normal flow function for the given set of start and end abstractions-

Parameters:

flowFunction - The normal flow function to compute

d1 - The abstraction at the method's start node

d1 - The abstraction at the current node

Returns:

The set of abstractions at the successor node

propagate

protected void propagate(D sourceVal,
                         N target,
                         D targetVal,
                         EdgeFunction<V> f,
                         N relatedCallSite,
                         boolean isUnbalancedReturn)

Propagates the flow further down the exploded super graph, merging any edge function that might already have been computed for targetVal at target.

Parameters:

sourceVal - the source value of the propagated summary edge

target - the target statement

targetVal - the target value at the target statement

f - the new edge function computed from (s0,sourceVal) to (target,targetVal)

relatedCallSite - for call and return flows the related call statement, null otherwise (this value is not used within this implementation but may be useful for subclasses of IDESolver)

isUnbalancedReturn - true if this edge is propagating an unbalanced return (this value is not used within this implementation but may be useful for subclasses of IDESolver)

joinValueAt

protected V joinValueAt(N unit,
                        D fact,
                        V curr,
                        V newVal)

endSummary

protected java.util.Set<<any>> endSummary(N sP,
                                          D d3)

incoming

protected java.util.Map<N,java.util.Set<D>> incoming(D d1,
                                                     N sP)

addIncoming

protected void addIncoming(N sP,
                           D d3,
                           N n,
                           D d2)

resultAt

public V resultAt(N stmt,
                  D value)

Returns the V-type result for the given value at the given statement. TOP values are never returned.

resultsAt

public java.util.Map<D,V> resultsAt(N stmt)

Returns the resulting environment for the given statement. The artificial zero value is automatically stripped. TOP values are never returned.

getExecutor

protected CountingThreadPoolExecutor getExecutor()

Factory method for this solver's thread-pool executor.

getDebugName

protected java.lang.String getDebugName()

Returns a String used to identify the output of this solver in debug mode. Subclasses can overwrite this string to distinguish the output from different solvers.

printStats

public void printStats()