Java Reference
In-Depth Information
Property
Explanation
The combination of two identical solutions is
trivial.
a
∧
a
=
a
If
a
is worse than
b
, then combining
a
and
b
must yield
a
;if
a
=
b
, then the combination is
simply
a
, as above.
a
b
⇐⇒
a
∧
b
=
a
The combination of
a
and
b
can be no better
than
a
or
b
.
a
∧
b
a
a
∧
b
b
Since
is the best solution, combining with
a
∧=
a
changes nothing.
Since
is the worst solution, any combination
that includes
⊥
a
∧⊥=⊥
⊥
will be
⊥
.
Figure 14.46: Meet lattice properties.
Definition 14.22
A data flow framework is
monotone
i
ff
(
∀
a
,
b
∈
A
)(
∀
f
∈F
)
a
b
⇐⇒
f
(
a
)
f
(
b
)
Consider the availableexpressions problem, posed for the expressions
v
+
w
,
w
+
y
,and
a
+
b
. Figure 14.47 shows some fragments of a program and explains
the transfer function that models each fragment's e
ects. The last example
in Figure 14.47 shows the most general form of a transfer function for this
problem. This is often written in the form
f
(
in
)
ff
∪
GEN
,where
KILL
and
GEN
are node-specific constants that represent the expressions that
become unavailable and available, respectively, due to the node's behavior.
The complete set of transfer functions
=
(
in
−
KILL
)
for available expressions includes
all such functions for every possible value of
KILL
and
GEN
.Ifthereare
n
expressions in an available expressions problem, then there are 2
n
possible
values for
KILL
. The same argument holds for
GEN
, so that the total size of
F
F
is
O
(2
n
).
Because transfer functions are
mathematical
, they can model not only the
e
ff
ects of a single node but also the e
ff
ects along any
path
through a program.
If a node with transfer function
f
is followed by a node with transfer function
ect of both nodes on input
a
is modeled by
g
(
f
(
a
)). In
other words, any potential program behavior—brief or lengthy—is modeled
g
, then the cumulative e
ff
