Java Reference
In-Depth Information
(a) Sketch the data flow lattice for a single variable. Be specific about
the values for
.
(b) Is this a forward or backward propagation problem?
(c) If the variable
v
could have range
r
1
or
r
2
, describe how to compute
the meet of these two ranges.
and
⊥
48. Prove or disprove that rangeanalysis is a
rapid
data flow problem.
49. Prove or disprove that rangeanalysisis a
distributive
data flowproblem.
50. Figure 14.58 shows the evaluation of the numberofbits problem for the
flow graph shown in Figure 14.57. The number of iterations taken to
reach convergence proves that the numberofbits problem is not
rapid
.
Construct a di
erent proof, based on Definition 14.24. In other words,
find an
f
and
a
for an instance of the numberofbitsproblem that violates
Definition 14.24.
Hint:
The instance given in Figure 14.57 provides
inspiration for finding a suitable
f
and
a
.
ff
51. Given a monotone data flow framework, is it decidable whether a node's
transfer function always returns the same value? In other words, can it
be decided for an arbitrary
f
∈F
=
k
?Ifthis
is undecidable, provide a proof. It is decidable, provide an algorithm.
that (
∃
k
∈
A
)(
∀
a
∈
A
)
f
(
a
)
52. Given a monotone data flow framework, is it decidable whether a node's
transfer function always returns its input? In other words, can it be de-
cided for an arbitrary
f
∈F
=
a
? If this is undecidable,
provide a proof. It is decidable, provide an algorithm.
that (
∀
a
∈
A
)
f
(
a
)
53. Consider the following definition:
Definition 14.34
A data flow framework is
idempotent
i
ff
(
∀
a
∈
A
)(
∀
f
∈F
)
f
(
f
(
x
))
=
f
(
x
)
Prove or disprove that the
bit-vectoring data flow problems
are idem-
potent.
54. Verify that the dominator and dominance frontiers shown in Figure 14.63
are correct for the flow graph shown in Figure 14.62(b).
