Java Reference
In-Depth Information
(d) How are solutions summarized at common control flow points?
(e) How would you determine very busy expressions for a
set
of ex-
pressions?
(f) Formally define the framework for verybusyexpressions.
(g) Prove or disprove that your framework is
rapid
.
(h) Prove or disprove that your framework is
distributive
.
39. The following data flow problems are known as the
bit-vectoring data
flow problems
:
•
availableexpressions (Section 14.3.1 and Exercise 35)
•
livevariables (Section 14.3.2 and Exercise 36)
•
verybusyexpressions (Exercise 38)
•
reachingdefinitions (Exercise 37)
Summarize these problems by entering each into its proper position in
the following table:
Forward
Backward
Any path
All paths
The columns refer to whether information is pushed forward or back-
ward to achieve a solution to the problem. The rows refer to how informa-
tion is summarized by the meet (
) operator: information is conserved
if it occurs on any paths or all paths.
∧
40. From Definition 14.22 and the lattice properties given in Figure 14.46,
prove Lemma 14.25.
41. Prove the following lemma:
Lemma 14.33
For a lattice where the meet operator (
∧
) is set intersec-
tion (
∩
) or set union (
∪
):
•
(
∀
x
∈
A
)(
∀
y
∈
A
)(
∀
z
∈
A
)(
x
∧
y
)
∪
z
=
(
x
∪
z
)
∧
(
y
∪
z
)
•
(
∀
x
∈
A
)(
∀
y
∈
A
)(
∀
z
∈
A
)(
x
∧
y
)
∩
z
=
(
x
∩
z
)
∧
(
y
∩
z
)
