Java Reference
In-Depth Information
framework that is
not
rapid
. Although most computers provision an entire
word of storage to hold an integer value, program optimization can try to
determine the numberofbits that are actually required to represent all values
held by a given variable name. This analysis involves examining the values
that a given name can hold. Of course, if such information is unavailable or
too di
cult to discern, then
⊥
can indicate that a name should occupy a full
word.
Figure 14.55 shows a simple program (no branches or loops) for analyzing
the right numberofbits. After Marker
98
,
q
requires 2 bits, because the value
held in
w
requires that many bits. After
a
←
b
,
a
requires the same 4 bits needed
for
b
. After Marker
99
,
w
also needs 4 bits. The assignment at Marker
100
takes 7 bits—the maximum number of bits taken by
a
(4) and
d
(7).
To study the rapidness of the number of bits problem, Figure 14.57 is
the flow graph from Figure 14.53(a), with the statements from Figure 14.55
placed in some of the graph's nodes. Iterative evaluation of this problem
proceeds as shown in Figure 14.58. Any “news” about the problem that hits
node 8 takes two more passes to propagate to node 1. If the number of bits
problem were
rapid
, then any instance of the problem for the flow graph
shown in Figure 14.53(a) should converge in 3 passes, because of the number
and structure of that graph's back edges. However, Figure 14.58 shows 7
iterations are required for convergence. Exercise 50 explores this further.
We next turn to an examination of the
quality
of the solution computed by
data flow analysis. We begin with the following lemma:
Lemma 14.25
Given a monotone data flow framework
D=
(
G
eg
,
L
,F
)
,
a
b
(
∀
f
∈F
)(
∀
a
,
b
∈
A
)
f
(
a
∧
b
)
f
(
a
)
∧
f
(
b
)
f
Proof: Left as Exercise 40.
Lemma 14.25 is the essence of a data flow framework's approximation of a
program's actual behavior. On arrival to the node shown in Lemma 14.25,
one of
a
or
b
is presented. The e
ff
ect of executing
f
on either input is either
f
(
a
)or
f
(
b
). Thus,
f
's behavior given either input is best summarized as
f
(
a
)
∧
f
(
b
). However, iterative analysis does not allow
f
to act separately on
a
or
b
.Instead,
a
∧
b
is computed, and
f
is applied to that lattice element.
