N
- The control flow graph's node value type.L
- Lattice element type.abstract class DataFlowAnalysis<N,L extends LatticeElement>
extends java.lang.Object
Annotatable.setAnnotation(com.google.javascript.jscomp.graph.Annotation)
to the
given control flow graph's nodes in form of LatticeElement
after calling analyze()
.
As a guideline, the following is a list of behaviors that any analysis can take:
x
for any x
must also be x
.
isForward()
.
LatticeElement
.
Function.apply(F)
.
flowThrough(Object, LatticeElement)
.
createEntryLattice()
.
createInitialEstimateLattice()
.
Upon execution of the analyze()
method, nodes of the input
control flow graph will be annotated with a DataFlowAnalysis.FlowState
object that
represents maximum fixed point solution. Any previous annotations at the
nodes of the control flow graph will be lost.
Modifier and Type | Class and Description |
---|---|
(package private) static class |
DataFlowAnalysis.BranchedFlowState<L extends LatticeElement>
The in and out states of a node.
|
(package private) static class |
DataFlowAnalysis.BranchedForwardDataFlowAnalysis<N,L extends LatticeElement> |
(package private) static class |
DataFlowAnalysis.FlowState<L extends LatticeElement>
The in and out states of a node.
|
(package private) static class |
DataFlowAnalysis.MaxIterationsExceededException
The exception to be thrown if the analysis has been running for a long
number of iterations.
|
Modifier and Type | Field and Description |
---|---|
private ControlFlowGraph<N> |
cfg |
(package private) JoinOp<L> |
joinOp |
static int |
MAX_STEPS |
protected java.util.Set<DiGraph.DiGraphNode<N,ControlFlowGraph.Branch>> |
orderedWorkSet |
Constructor and Description |
---|
DataFlowAnalysis(ControlFlowGraph<N> targetCfg,
JoinOp<L> joinOp)
Constructs a data flow analysis.
|
Modifier and Type | Method and Description |
---|---|
(package private) void |
analyze()
Finds a fixed-point solution using at most
MAX_STEPS
iterations. |
(package private) void |
analyze(int maxSteps)
Finds a fixed-point solution.
|
(package private) static void |
computeEscaped(Scope jsScope,
java.util.Set<Var> escaped,
AbstractCompiler compiler)
Compute set of escaped variables.
|
(package private) abstract L |
createEntryLattice()
Gets the incoming state of the entry node.
|
(package private) abstract L |
createInitialEstimateLattice()
Gets the state of the initial estimation at each node.
|
protected boolean |
flow(DiGraph.DiGraphNode<N,ControlFlowGraph.Branch> node)
Performs a single flow through a node.
|
(package private) abstract L |
flowThrough(N node,
L input)
Computes the output state for a given node and input state.
|
(package private) ControlFlowGraph<N> |
getCfg()
Returns the control flow graph that this analysis was performed on.
|
(package private) L |
getExitLatticeElement()
Returns the lattice element at the exit point.
|
protected void |
initialize()
Initializes the work list and the control flow graph.
|
(package private) abstract boolean |
isForward()
Checks whether the analysis is a forward flow analysis or backward flow
analysis.
|
protected L |
join(L latticeA,
L latticeB) |
protected void |
joinInputs(DiGraph.DiGraphNode<N,ControlFlowGraph.Branch> node)
Computes the new flow state at a given node's entry by merging the
output (input) lattice of the node's predecessor (successor).
|
private final ControlFlowGraph<N> cfg
final JoinOp<L extends LatticeElement> joinOp
protected final java.util.Set<DiGraph.DiGraphNode<N,ControlFlowGraph.Branch>> orderedWorkSet
public static final int MAX_STEPS
DataFlowAnalysis(ControlFlowGraph<N> targetCfg, JoinOp<L> joinOp)
Typical usage
DataFlowAnalysis dfa = ... dfa.analyze();
analyze()
annotates the result to the control flow graph by
means of Annotatable.setAnnotation(com.google.javascript.jscomp.graph.Annotation)
without any
modification of the graph itself. Additional calls to analyze()
recomputes the analysis which can be useful if the control flow graph
has been modified.final ControlFlowGraph<N> getCfg()
analyze()
is called and before
the graph has been modified.L getExitLatticeElement()
abstract boolean isForward()
true
if it is a forward analysis.abstract L flowThrough(N node, L input)
node
- The node.input
- Input lattice that should be read-only.final void analyze()
MAX_STEPS
iterations.analyze(int)
final void analyze(int maxSteps)
Annotatable.setAnnotation(Annotation)
.
Initially, each node's input and output flow state contains the value
given by createInitialEstimateLattice()
(with the exception of the
entry node of the graph which takes on the createEntryLattice()
value. Each node will use the output state of its predecessor and compute a
output state according to the instruction. At that time, any nodes that
depends on the node's newly modified output value will need to recompute
their output state again. Each step will perform a computation at one node
until no extra computation will modify any existing output state anymore.
maxSteps
- Max number of iterations before the method stops and throw
a DataFlowAnalysis.MaxIterationsExceededException
. This will prevent the
analysis from going into a infinite loop.abstract L createInitialEstimateLattice()
abstract L createEntryLattice()
protected void initialize()
protected boolean flow(DiGraph.DiGraphNode<N,ControlFlowGraph.Branch> node)
true
if the flow state differs from the previous state.protected void joinInputs(DiGraph.DiGraphNode<N,ControlFlowGraph.Branch> node)
node
- Node to compute new join.static void computeEscaped(Scope jsScope, java.util.Set<Var> escaped, AbstractCompiler compiler)