Java Reference
In-Depth Information
42. Prove that all four bit-vectoring data flow problems in Exercise 39 are
rapid
. Instead of writing four separate proofs, base your proof on the
generic form of a transfer function
f
Y
(
in
)
=
(
in
−
Kill
Y
)
∪
Gen
Y
=
(
in
∩
NKill
Y
)
∪
Gen
Y
and Lemma 14.33. The above reformulation of
NKill
Y
as the complement
of
KILL
Y
allows the transfer function to be stated in terms of set union
and intersection.
43. Prove or disprove that constant propagation is a
rapid
data flowproblem.
44. Prove or disprove that availableexpressions is a
distributive
data flow
problem (Definition 14.26).
45. Generalize the proof from Exercise 44 to prove or disprove that all four
bit-vectoring data flow problems in Exercise 39 are
distributive
.Use
Lemma 14.33 and the generic form of the transfer function given in
Exercise 42.
46. Prove or disprove that constant propagation is a
distributive
data flow
problem.
47. Consider generalizing the problem of constant propagation to that of
range analysis
. For each variable, we wish to associate a minimum and
maximum value, such that the actual value of the variable (at that site
in the program) at runtime is guaranteed to fall between the two values.
For example, consider the following program.
x
←
5
y
←
3
if
p
then
z
←
x
+
y
else
115
z
←
x
−
y
w
←
z
After their assignment, variable
x
has range 5
116
...
5andvariable
y
has
range 3
...
3. The e
ff
ect of Marker
115
gives
z
the range 8
...
8. The e
ff
ect
of Marker
116
gives
z
the range 2
...
2. The assignment for
w
therefore
gets the range 2
...
8.
