vasco
Class OldForwardInterProceduralAnalysis<M,N,A>

java.lang.Object
  vasco.InterProceduralAnalysis<M,N,A>
      vasco.OldForwardInterProceduralAnalysis<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:

PointsToAnalysis

Deprecated. This is the old API from the initial SOAP '13 submission without call/return flow functions. It is only here for a temporary period while the PointsToAnalysis class is migrated to the new API. After that work is done, this class will be permanently removed from VASCO.

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

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

This class essentially captures a forward data flow problem which can be solved using the context-sensitive inter-procedural analysis framework as described in InterProceduralAnalysis.

This is the class that client analyses will extend in order to perform forward-flow inter-procedural analysis.

Author:

Rohan Padhye

Field Summary

protected Stack<Context<M,N,A>>

analysisStack Deprecated.

Fields inherited from class vasco.InterProceduralAnalysis

contexts, contextTransitions, freeResultsOnTheFly, reverse, verbose, worklist

Constructor Summary

OldForwardInterProceduralAnalysis()
Deprecated. Constructs a new forward-flow inter-procedural analysis.

Method Summary

void	doAnalysis() Deprecated. Performs the actual data flow analysis.
protected abstract A	flowFunction(Context<M,N,A> context, N unit, A in) Deprecated.
protected void	initContext(Context<M,N,A> context, A entryValue) Deprecated. Creates a new context and initialises data flow values.
protected A	processCall(Context<M,N,A> callerContext, N callNode, M method, A entryValue) Deprecated. Processes a call statement.

Methods inherited from class vasco.InterProceduralAnalysis

boundaryValue, copy, getCallers, getContext, getContexts, getContextTransitionTable, getMeetOverValidPathsSolution, getMethods, getTargets, meet, programRepresentation, topValue

Methods inherited from class java.lang.Object

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

Field Detail

analysisStack

protected Stack<Context<M,N,A>> analysisStack

Deprecated.

Constructor Detail

OldForwardInterProceduralAnalysis

public OldForwardInterProceduralAnalysis()

Deprecated.

Constructs a new forward-flow inter-procedural analysis.

Method Detail

doAnalysis

public void doAnalysis()

Deprecated.

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.

Specified by:

doAnalysis in class InterProceduralAnalysis<M,N,A>

initContext

protected void initContext(Context<M,N,A> context,
                           A entryValue)

Deprecated.

Creates a new context and initialises data flow values.

The following steps are performed:

1. Initialise all nodes to default flow value (lattice top).
2. Initialise the entry nodes (heads) with a copy of the entry value.
3. Add entry points to work-list.
4. Push this context on the top of the analysis stack.

Parameters:

context - the context to initialise

entryValue - the data flow value at the entry of this method

processCall

protected A processCall(Context<M,N,A> callerContext,
                        N callNode,
                        M method,
                        A entryValue)

Deprecated.

Processes a call statement.

Retrieves a value context for the callee if one exists with the given entry value, or else creates a new one and adds the transition to the context transition table.

If the callee context has already been analysed, returns the resulting exit value. For newly created contexts the result would be null, as they are obviously not analysed even once.

Note that this method is not directly called by doAnalysis, but is instead called by flowFunction when a method call statement is encountered. The reason for this design decision is that client analyses may want their own setup and tear down sequences before a call is made (similar to edge flow functions at the call and return site). Also, analyses may want to choose which method call to process at an invoke statement in the case of virtual calls (e.g. a points-to analysis may build the call-graph on-the-fly).

Therefore, it is the responsibility of the client analysis to detect an invoke expression when implementing flowFunction, and suitably invoke processCall with the input data flow value which may be different from the IN/OUT value of the node due to handling of arguments, etc. Similarly, the result of processCall may be modified by the client to handle return values, etc. before returning from flowFunction. Ideally, flowFunction should return null if and only if processCall returns null.

Parameters:

callerContext - the analysis context at the call-site

callNode - the calling statement

method - the method being called

entryValue - the data flow value at the entry of the called method.

Returns:

the data flow value at the exit of the called method, if available, or null if unavailable.

flowFunction

protected abstract A flowFunction(Context<M,N,A> context,
                                  N unit,
                                  A in)

Deprecated.