Java Reference
In-Depth Information
b
←
15
w
←
3
d
←
127
/
At this point, b takes 4 bits; w takes 2 bits; d takes 7 bits
/
98
q
←
w
a
←
b
w
←
a
99
b
←
a
d
100
Figure 14.55: Program for the number of bits problem. The
operator
performs some bit-wise operation, creating a result whose
size is the same as the larger of the two operands.
a
f
Figure 14.56: Flow graph to illustrate a rapid framework.
if the data flow problem is
rapid
[KU76, Ros78]:
Definition 14.24
A data flow framework is
rapid
i
ff
∀
a
∈
A
,∀
f
∈F,
a
∧
f
(
)
f
(
a
)
To appreciate this definition, consider the flow graph shown in Figure 14.56.
The path through the node will apply the transfer function
f
. Iterative eval-
uation would compute the loop edge as having the value
f
(
a
). The next time
through, evaluation will compute the meet of the two values,
a
∧
f
(
a
), as the
new input to
f
, computing
f
(
a
∧
f
(
a
)). This process continues until the output
of the node stops “lowering” in the lattice.
If the framework in Figure 14.56 is rapid, then for every
a
∈
A
,
a
∧
f
(
)
f
(
a
). In other words,
f
acting on the best possible information (
) can meet
a
,
and the result is no better than if
f
were to act on
a
itself. In terms of the data
flow lattice,
a
∧
f
(
) arrives at an element that is the same as, or lower in the
lattice than,
f
(
a
), which drives us toward convergence at least as well as if
f
had a chance to act on
a
in the evaluation.
Exercises 38, 32, and 42 investigate the rapidness of the frameworks we
have studied thus far. It is also instructive to study the following data flow
