Java Reference
In-Depth Information
by some transfer function in
. A transfer function can be applied to any
lattice value
a
to obtain the compile-time estimation of the program fragment's
behavior given the conditions represented by
a
.
F
Having specified a data flowproblemas a data flow framework,we now turn to
evaluating the framework to obtain an answer to the associated problem. Each
flow graph node provides an equation in terms of the solution presented into
that node. The challenge here is to determine an assignment of solutions from
the lattice
A
that satisfies all of the equations while providing the best possible
optimization. Section 14.5.1 describes an iterative approach to evaluate data
flow frameworks. Each node initially asserts a solution of
,whichwetakeon
faith as correct for now. We revisit the issue of
initialization
in Section 14.5.2.
Evaluation continues until convergence is achievedwithno changes in solution
throughout the graph. The speed of reaching convergence and the quality of
the solution are discussed in Sections 14.5.3 and 14.5.4.
14.5.1
Iteration
The most straightforward approach to evaluating a data flow framework is
simply to iterate over the nodes and edges of the evaluation graph until con-
vergence is reached. The simple iterative evaluation algorithm is shown in
Figure 14.48. On visiting a given node
Y
,Marker
87
computes the input for
the transfer function at
Y
as the
meet
of the current solutions at
Y
's prede-
cessors in the evaluation graph. Recall that the edges of the evaluation graph
are already oriented in the direction of the data flow problem. Marker
88
then establishes the new solution at node
Y
.Marker
89
detects if the new
solution di
ers from the previous solution at
Y
. If the solution has changed,
then Marker
90
forces another round of node evaluations.
When the algorithm has finished, we have computed the data flow prob-
lem's MFP solution. We say the solution is the
maximum
fixed point because
it is as high (toward
ff
) in the lattice as possible while still being safe. This is
related to the framework's initialization, as discussed in Section 14.5.2.
We next consider applying this algorithm to the example shown in Fig-
ure 14.49. Marker
86
does not specify an order in which nodes should be
considered. If we consider nodes in the order [ 2
1 ] then the evaluations
occur as shown in Figure 14.50. This evaluation required four passes over
,
5
,
4
,
3
,
N
eg
as follows:
1. The input
IN
Y
to each node
Y
is the initialized value
.Becausethe
output of node 4 changes from its initialized value of
to its computed
value
⊥
, another pass is required.
