vasco
Class ForwardInterProceduralAnalysis<M,N,A>

java.lang.Object
  extended by vasco.InterProceduralAnalysis<M,N,A>
      extended by vasco.ForwardInterProceduralAnalysis<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:
CopyConstantAnalysis, SignAnalysis

public abstract class ForwardInterProceduralAnalysis<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
 
Fields inherited from class vasco.InterProceduralAnalysis
contexts, contextTransitions, freeResultsOnTheFly, reverse, verbose, worklist
 
Constructor Summary
ForwardInterProceduralAnalysis()
          Constructs a new forward-flow inter-procedural analysis.
 
Method Summary
abstract  A callEntryFlowFunction(Context<M,N,A> context, M targetMethod, N node, A inValue)
          Processes the inter-procedural flow function for a method call at the start of the call, to handle parameters.
abstract  A callExitFlowFunction(Context<M,N,A> context, M targetMethod, N node, A exitValue)
          Processes the inter-procedural flow function for a method call at the end of the call, to handle return values.
abstract  A callLocalFlowFunction(Context<M,N,A> context, N node, A inValue)
          Processes the intra-procedural flow function for a method call at the call-site itself, to handle propagation of local values that are not involved in the call.
 void doAnalysis()
          Performs the actual data flow analysis.
protected  Context<M,N,A> initContext(M method, A entryValue)
          Creates a new value context and initialises data flow values for its nodes.
abstract  A normalFlowFunction(Context<M,N,A> context, N node, A inValue)
          Processes the intra-procedural flow function of a statement that does not contain a method call.
 
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
 

Constructor Detail

ForwardInterProceduralAnalysis

public ForwardInterProceduralAnalysis()
Constructs a new forward-flow inter-procedural analysis.

Method Detail

doAnalysis

public 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.

Specified by:
doAnalysis in class InterProceduralAnalysis<M,N,A>

initContext

protected Context<M,N,A> initContext(M method,
                                     A entryValue)
Creates a new value context and initialises data flow values for its nodes.

The following steps are performed:

  1. Construct the context.
  2. Initialise IN/OUT for all nodes and add them to the work-list
  3. Initialise the IN of entry points with a copy of the given entry value.
  4. Add this new context to the given method's mapping.
  5. Add this context to the global work-list.

Parameters:
method - the method whose context to create
entryValue - the data flow value at the entry of this method

normalFlowFunction

public abstract A normalFlowFunction(Context<M,N,A> context,
                                     N node,
                                     A inValue)
Processes the intra-procedural flow function of a statement that does not contain a method call.

Parameters:
context - the value context at the call-site
node - the statement whose flow function to process
inValue - the data flow value before the statement
Returns:
the data flow value after the statement

callEntryFlowFunction

public abstract A callEntryFlowFunction(Context<M,N,A> context,
                                        M targetMethod,
                                        N node,
                                        A inValue)
Processes the inter-procedural flow function for a method call at the start of the call, to handle parameters.

Parameters:
context - the value context at the call-site
targetMethod - the target (or one of the targets) of this call site
node - the statement containing the method call
inValue - the data flow value before the call
Returns:
the data flow value at the entry to the called procedure

callExitFlowFunction

public abstract A callExitFlowFunction(Context<M,N,A> context,
                                       M targetMethod,
                                       N node,
                                       A exitValue)
Processes the inter-procedural flow function for a method call at the end of the call, to handle return values.

Parameters:
context - the value context at the call-site
targetMethod - the target (or one of the targets) of this call site
node - the statement containing the method call
exitValue - the data flow value at the exit of the called procedure
Returns:
the data flow value after the call (returned component)

callLocalFlowFunction

public abstract A callLocalFlowFunction(Context<M,N,A> context,
                                        N node,
                                        A inValue)
Processes the intra-procedural flow function for a method call at the call-site itself, to handle propagation of local values that are not involved in the call.

Parameters:
context - the value context at the call-site
node - the statement containing the method call
inValue - the data flow value before the call
Returns:
the data flow value after the call (local component)