Java Reference
In-Depth Information
modeled as follows.
∧
f
C
(
in
C
)
= ∧
f
C
(
in
C
)
=
f
C
(
in
C
)
in
C
=
f
E
(
in
E
)
in
E
=
f
D
(
in
D
)
∧
in
loop
=
in
E
∧
in
loop
=
f
C
(
in
C
)
∧
in
loop
In other words, the input to node
C
depends on the output of node
C
!This
circularity seems unresolvable, unless we reason that the first time we evaluate
C
's transfer function, we can assume some prior result.
Computationally, the same problem arises. The iterative approach de-
scribed in Section 14.5.1 will encounter
C
as the first node in Figure 14.52. The
input to
C
must be evaluated at that point, but that input depends on the result
coming from node
E
, which has not yet been examined. Because the graph
contains a loop, looking at
E
before
C
does not o
er any relief.
When we first evaluate the solution for node
C
, we have the following
choices concerning the solution from
E
:
ff
f
E
(
in
E
)
= ⊥
(
optimistic
)
f
E
(
in
E
)
=
(
pessimistic
)
It is safe to assume that
v
+
w
is
not available
previously from
E
, in which case
we initially assume pessimistically that
f
E
(
in
E
)
=⊥
. However, when
⊥
meets
in
loop
,weobtain
as the input to node
C
. Propagation forward would then
show
v
+
w
to be unavailable everywhere in Figure 14.52(a), except on the edge
marked
Avail
. This solution is safe, but not as good as we can obtain.
It is more daring to make the optimistic assumption that
v
+
wis
avail-
able:
⊥
. Based on this assumption, we obtain the result shown in
Figure 14.42, with
v
+
w
available everywhere in the inner loop. We can safely
initialize all solutions to
f
E
(
in
E
)
=
, counting on the meet operator to combine all facts
safely throughout the computation. If a given point in the flow graph is unsafe
at
, then it will be lowered in the lattice as evaluation proceeds to a safe value.
Because data flow problems are solved at compile-time, they are expected
to terminate. Monotonicity (Definition 14.22) helps in this regard, because
solutions at any point in a flow graph can only move toward
as evaluation
proceeds. However, to ensure convergence, the distance from any data flow
solution to
⊥
⊥
must be bounded:
