Class WorklistBasedOptimisticCallgraphBuilder

java.lang.Object

com.ibm.wala.cast.js.callgraph.fieldbased.FieldBasedCallGraphBuilder

com.ibm.wala.cast.js.callgraph.fieldbased.WorklistBasedOptimisticCallgraphBuilder

public class WorklistBasedOptimisticCallgraphBuilder
extends FieldBasedCallGraphBuilder

Optimistic call graph builder that propagates inter-procedural data flow iteratively as call edges are discovered. Slower, but potentially more sound than PessimisticCallGraphBuilder.

This variant uses a worklist algorithm, generally making it scale better than OptimisticCallgraphBuilder, which repeatedly runs the pessimistic algorithm.

Author:

mschaefer

Nested Class Summary

Nested classes/interfaces inherited from class FieldBasedCallGraphBuilder

FieldBasedCallGraphBuilder.CallGraphResult

Modifier and Type	Class	Description
static class	FieldBasedCallGraphBuilder.CallGraphResult	Full result of call graph computation

Field Summary

Fields

Modifier and Type	Field	Description
int	ITERATION_CUTOFF	The maximum number of iterations to perform.

Fields inherited from class FieldBasedCallGraphBuilder

cache, cha, constructors, options, supportFullPointerAnalysis, targetSelector

Modifier and Type	Field	Description
protected final IAnalysisCacheView	cache
protected final IClassHierarchy	cha
protected final JavaScriptConstructorFunctions	constructors
protected final AnalysisOptions	options
protected final boolean	supportFullPointerAnalysis
final MethodTargetSelector	targetSelector

Constructor Summary

Constructors

Constructor	Description
WorklistBasedOptimisticCallgraphBuilder(IClassHierarchy cha, AnalysisOptions options, IAnalysisCacheView cache, boolean supportFullPointerAnalysis, int bound)

Method Summary

Modifier and Type	Method	Description
void	addFlowEdge(FlowGraph flowgraph, Vertex from, Vertex to, Set<Vertex> worklist)
FlowGraph	buildFlowGraph(MonitorUtil.IProgressMonitor monitor)	Build a flow graph for the program to be analysed.
Set<Pair<CallVertex, FuncVertex>>	extractCallGraphEdges(FlowGraph flowgraph, MonitorUtil.IProgressMonitor monitor)	Extract call edges from the flow graph into high-level representation.
void	processPendingCallWorklist(FlowGraph flowgraph, Map<Vertex, Set<FuncVertex>> pendingCallWorklist, VertexFactory factory, Map<Vertex, MutableIntSet> reachingFunctions, Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices, Set<Vertex> worklist, OrdinalSetMapping<FuncVertex> mapping)
void	processPendingReflectiveCallWorklist(FlowGraph flowgraph, Map<Vertex, Set<FuncVertex>> pendingReflectiveCallWorklist, Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices, Set<Vertex> worklist)

Methods inherited from class FieldBasedCallGraphBuilder

addEdgeToJSCallGraph, buildCallGraph, extract, extract, flowGraphFactory, handleFunctionCallOrApplyInvocation

Modifier and Type	Method	Description
boolean	addEdgeToJSCallGraph(JSCallGraph cg, CallSiteReference site, IMethod target, CGNode caller)
FieldBasedCallGraphBuilder.CallGraphResult	buildCallGraph(Iterable<? extends Entrypoint> eps, MonitorUtil.IProgressMonitor monitor)	Main entry point: builds a flow graph, then extracts a call graph and returns it.
JSCallGraph	extract(FlowGraph flowgraph, Iterable<? extends Entrypoint> eps, MonitorUtil.IProgressMonitor monitor)	Extract a call graph from a given flow graph.
JSCallGraph	extract(SSAContextInterpreter interpreter, FlowGraph flowgraph, Iterable<? extends Entrypoint> eps, MonitorUtil.IProgressMonitor monitor)
protected FlowGraph	flowGraphFactory()
boolean	handleFunctionCallOrApplyInvocation(FlowGraph flowgraph, MonitorUtil.IProgressMonitor monitor, JSCallGraph cg, CallVertex callVertex, CGNode caller, CallSiteReference site, IMethod target)

Methods inherited from class Object

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

Field Details

ITERATION_CUTOFF

public int ITERATION_CUTOFF

The maximum number of iterations to perform.

Constructor Details

WorklistBasedOptimisticCallgraphBuilder

public WorklistBasedOptimisticCallgraphBuilder(IClassHierarchy cha,
 AnalysisOptions options,
 IAnalysisCacheView cache,
 boolean supportFullPointerAnalysis,
 int bound)

Method Details

buildFlowGraph

public FlowGraph buildFlowGraph(MonitorUtil.IProgressMonitor monitor)
                         throws CancelException

Description copied from class: FieldBasedCallGraphBuilder

Build a flow graph for the program to be analysed.

Specified by:

buildFlowGraph in class FieldBasedCallGraphBuilder

Throws:

CancelException

extractCallGraphEdges

public Set<Pair<CallVertex, FuncVertex>> extractCallGraphEdges(FlowGraph flowgraph,
 MonitorUtil.IProgressMonitor monitor)
                                                        throws CancelException

Description copied from class: FieldBasedCallGraphBuilder

Extract call edges from the flow graph into high-level representation.

Overrides:

extractCallGraphEdges in class FieldBasedCallGraphBuilder

Throws:

CancelException

processPendingCallWorklist

public void processPendingCallWorklist(FlowGraph flowgraph,
 Map<Vertex, Set<FuncVertex>> pendingCallWorklist,
 VertexFactory factory,
 Map<Vertex, MutableIntSet> reachingFunctions,
 Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices,
 Set<Vertex> worklist,
 OrdinalSetMapping<FuncVertex> mapping)

processPendingReflectiveCallWorklist

public void processPendingReflectiveCallWorklist(FlowGraph flowgraph,
 Map<Vertex, Set<FuncVertex>> pendingReflectiveCallWorklist,
 Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices,
 Set<Vertex> worklist)

addFlowEdge

public void addFlowEdge(FlowGraph flowgraph,
 Vertex from,
 Vertex to,
 Set<Vertex> worklist)