vasco
Class InterProceduralAnalysis<M,N,A>

java.lang.Object
  vasco.InterProceduralAnalysis<M,N,A>

Type Parameters:

M - the type of a method

N - the type of a node in the CFG

A - the type of a data flow value

Direct Known Subclasses:

BackwardInterProceduralAnalysis, ForwardInterProceduralAnalysis, OldForwardInterProceduralAnalysis

public abstract class InterProceduralAnalysis<M,N,A>
extends Object

A generic inter-procedural analysis which is fully context-sensitive.

This class is a base for forward and backward inter-procedural analysis classes. This inter-procedural analysis framework is fully context sensitive even in the presence of recursion and uses data flow values reaching a method to distinguish contexts.

Author:

Rohan Padhye

See Also:

Context, ContextTransitionTable, CallSite

Field Summary

protected Map<M,List<Context<M,N,A>>>	contexts A mapping from methods to a list of contexts for quick lookups.
protected ContextTransitionTable<M,N,A>	contextTransitions A record of transitions from calling context and call-site to called method and called context.
protected boolean	freeResultsOnTheFly A flag, if set, directs the analysis to free memory storing data flow values of individual statements once a context has been analysed and would not be required to be re-analysed.
protected boolean	reverse true if the direction of analysis is backward, or false if it is forward.
protected boolean	verbose Whether to print information about contexts.
protected NavigableSet<Context<M,N,A>>	worklist A work-list of contexts to process.

Constructor Summary

InterProceduralAnalysis(boolean reverse)
Constructs a new inter-procedural analysis.

Method Summary

abstract A	boundaryValue(M entryPoint) Returns the initial data flow value at the program entry points.
abstract A	copy(A src) Returns a copy of the given data flow value.
abstract void	doAnalysis() Performs the actual data flow analysis.
Set<CallSite<M,N,A>>	getCallers(Context<M,N,A> target) Returns the callers of a value context.
Context<M,N,A>	getContext(M method, A value) Retrieves a particular value context if it has been constructed.
List<Context<M,N,A>>	getContexts(M method) Returns a list of value contexts constructed for a given method.
ContextTransitionTable<M,N,A>	getContextTransitionTable() Returns a reference to the context transition table used by this analysis.
DataFlowSolution<N,A>	getMeetOverValidPathsSolution() Returns a meet-over-valid-paths solution by merging data flow values across contexts for each program point.
Set<M>	getMethods() Returns all methods for which at least one context was created.
Map<M,Context<M,N,A>>	getTargets(CallSite<M,N,A> callSite) Returns the target of a call-site.
abstract A	meet(A op1, A op2) Returns the meet of two data flow values.
abstract ProgramRepresentation<M,N>	programRepresentation() Returns a program representation on top of which the inter-procedural analysis runs.
abstract A	topValue() Returns the default data flow value (lattice top).

Methods inherited from class java.lang.Object

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

Field Detail

worklist

protected final NavigableSet<Context<M,N,A>> worklist

A work-list of contexts to process.

contexts

protected final Map<M,List<Context<M,N,A>>> contexts

A mapping from methods to a list of contexts for quick lookups.

contextTransitions

protected final ContextTransitionTable<M,N,A> contextTransitions

A record of transitions from calling context and call-site to called method and called context.

reverse

protected final boolean reverse

true if the direction of analysis is backward, or false if it is forward.

freeResultsOnTheFly

protected boolean freeResultsOnTheFly

A flag, if set, directs the analysis to free memory storing data flow values of individual statements once a context has been analysed and would not be required to be re-analysed.

This setting is only useful for analyses that aggregate secondary results on the fly (e.g. call graph analysis that can do away with points-to information once the calls for a particular context have been resolved). This is not safe for use in analyses whose results will be directly used later (e.g. liveness analysis).

Memory is freed when a context is removed from the work-list and no context reachable from it in the transition table is also on the work-list. This ensures that the removed context will not be added again on the work-list for re-analysis of any statement.

Note that the data flow values at the entry/exit of the context are not freed, and hence it is still used to terminate recursion or as a cache hit for arbitrary call sites with same values.

The default value for this flag is false.

verbose

protected boolean verbose

Whether to print information about contexts.

Constructor Detail

InterProceduralAnalysis

public InterProceduralAnalysis(boolean reverse)

Constructs a new inter-procedural analysis.

Parameters:

reverse - true if the analysis is in the reverse direction, false if it is in the forward direction

Method Detail

boundaryValue

public abstract A boundaryValue(M entryPoint)

Returns the initial data flow value at the program entry points. For forward analyses this is the IN value at the ENTRY to each entry method, while for backward analyses this is the OUT value at the EXIT to each entry method.

Note that this method will be called exactly once per entry point specified by the program representation.

Parameters:

entryPoint - an entry point specified by the program representation

Returns:

the data flow value at the boundary

See Also:

ProgramRepresentation.getEntryPoints()

copy

public abstract A copy(A src)

Returns a copy of the given data flow value.

Parameters:

src - the data flow value to copy

Returns:

a new data flow value which is a copy of the argument

doAnalysis

public abstract void doAnalysis()

Performs the actual data flow analysis.

A work-list of contexts is maintained, each with it's own work-list of CFG nodes to process. For each node removed from the work-list of the newest context, the meet of values along incoming edges (in the direction of analysis) is computed and then the flow function is processed depending on whether the node contains a call or not. If the resulting data flow value has changed, then nodes along outgoing edges (in the direction of analysis) are also added to the work-list.

Analysis starts with the context for the program entry points with the given boundary values and ends when the work-list is empty.

See the SOAP '13 paper for the full algorithm in Figure 1.

getCallers

public Set<CallSite<M,N,A>> getCallers(Context<M,N,A> target)

Returns the callers of a value context.

Parameters:

target - the value context

Returns:

the call-sites which transition to the value context

getContext

public Context<M,N,A> getContext(M method,
                                 A value)

Retrieves a particular value context if it has been constructed.

Parameters:

method - the method whose value context to find

value - the data flow value at the entry (forward flow) or exit (backward flow) of the method

Returns:

the value context, if one is found with the given parameters, or null otherwise

getContexts

public List<Context<M,N,A>> getContexts(M method)

Returns a list of value contexts constructed for a given method.

Parameters:

method - the method whose contexts to retrieve

Returns:

an unmodifiable list of value contexts of the given method

getContextTransitionTable

public ContextTransitionTable<M,N,A> getContextTransitionTable()

Returns a reference to the context transition table used by this analysis.

Returns:

a reference to the context transition table used by this analysis

getMeetOverValidPathsSolution

public DataFlowSolution<N,A> getMeetOverValidPathsSolution()

Returns a meet-over-valid-paths solution by merging data flow values across contexts for each program point.

This method should not be invoked if the flag freeResultsOnTheFly had been set during analysis.

Returns:

a meet-over-valid-paths data flow solution

getMethods

public Set<M> getMethods()

Returns all methods for which at least one context was created.

Returns:

an unmodifiable set of analysed methods

getTargets

public Map<M,Context<M,N,A>> getTargets(CallSite<M,N,A> callSite)

Returns the target of a call-site.

Parameters:

callSite - the call-site whose targets to retrieve

Returns:

a map of target methods to their respective contexts

meet

public abstract A meet(A op1,
                       A op2)

Returns the meet of two data flow values.

Parameters:

op1 - the first operand

op2 - the second operand

Returns:

a new data flow which is the result of the meet operation of the two operands

programRepresentation

public abstract ProgramRepresentation<M,N> programRepresentation()

Returns a program representation on top of which the inter-procedural analysis runs. The program representation is used to build control flow graphs of individual procedures and resolve targets of virtual call sites.

Returns:

The program representation underlying this analysis

topValue

public abstract A topValue()

Returns the default data flow value (lattice top).

Returns:

the default data flow value (lattice top)