Java Reference
In-Depth Information
in
loop
???
Node Transfer Function
Cf
C
(
in
C
)
C
=
in
C
D
Df
D
(
in
D
)
=
z = v+w
E
f
E
(
in
E
)
=
in
E
Avail
E
(a)
(b)
Figure 14.52: Is
v
+
w
available throughout this loop? (a) Subgraph of
Figure 14.41; (b) Transfer functions.
Marker
96
marks only those nodes for evaluation that are successors of a node
whose output solution has changed. Marker
97
requests another pass over
the nodes only if information changes along a back edge.
14.5.2
Initialization
We now return to the discussion of how to
initialize
a framework's solutions
for iterative evaluation. In the algorithms of Figures 14.48 and 14.51, Mark-
ers
84
and
91
set all solutions initially to
.Foravailableexpressions,this
means that every node is initially assumed to make every expression avail-
able. This approach may seem unsound because we are initially assuming
something that will likely turn out to be false. However, when the algorithm
of Figure 14.51 is applied to the availableexpressions problem given in Fig-
ure 14.41, the answer shown in Figure 14.42 is correctly obtained (Exercise 29).
In fact, if we initially assume that all solutions are
,then
we do not always compute the best possible answer (Exercise 30). If we view
a data flow problem as seeking the solution to a set of equations, then an
interesting issue can arise when a flow graph has loops. Figure 14.52 is a
subgraph of our example from Figure 14.41(b). The edges in the subgraph
show the interdependence of one node's solution on other nodes.
We know that the best, correct solution for this subgraph should show
v
+
w
available everywhere (Figure 14.42). But how is such a solution determined?
Figure 14.52(b) shows the transfer functions for the subgraph's nodes. Let
in
loop
denote the input to the loop—the input to node
C
from outside the loop,
shown as
Avail
⊥
instead of
in Figure 14.52(a). The inputs to
C
and
E
are mathematically
