Java Reference
In-Depth Information
•
The comparison operator
. The meet lattice includes a reflexive partial
order, denoted by
. Given two solutions
a
and
b
from set
A
,itmustbe
true that
a
b
or
a
b
.If
a
b
, then solution
a
is no better than solution
b
. Further, if
a
≺
b
, then solution
a
is strictly worse than
b
—optimization
based on solution
a
will not be as good as with solution
b
.If
a
b
,then
solutions
a
and
b
are incomparable.
For example, consider the problemof livevariables, computed for the set
of variables
. As discussed in Section 14.3.2, the storage associated
with variables found
not
to be live can be reused. Thus, optimization is
improved when fewer variables are found to be live. So, the set
{
v
,
w
}
{
v
,
w
}
is
worse than the set
{
v
}
or the set
{
w
}
.Inotherwords,
{
v
,
w
}{
v
}
and
{
v
,
w
}{
w
}
. However, the solution
{
v
}
cannot be compared with the
set
). In both cases, one variable is live, and data flow
analysis cannot prefer one to the other for livevariables.
{
w
}
(
{
v
}
{
w
}
At this point, it is important to develop an intuitive understanding of the lattice,
especially its distinguished elements
. For each analysis problem there
is some solution that admits the greatest amount of optimization. This solution
is always
and
⊥
in the lattice. Recalling available expressions, the best solution
would make
every
expression available—all recomputations could then be
eliminated. Correspondingly,
represents the solution that admits the least
amount of optimization. A simple device for remembering this arrangement
is that
⊥
is always drawn at the top of a lattice diagram, as in Heaven (i.e.,
good optimization);
⊥
is always drawn at the bottom, as in Hell (i.e., poor
optimization).
For availableexpressions,
⊥
implies that
no
expressions can be eliminated.
For livevariables,
represents
that all variables are live. Recall that liveness means only that a variable's
current value
might
be used in the future. Assurance that a variable's current
valueisusefulisadi
represents that no variables are live, while
⊥
ff
erent optimizationproblem, as considered by Exercise 38.
are helpful for understanding data
flow frameworks, a more rigorous specification of the lattice's properties is
given in Figure 14.46.
While the informal notions of
and
⊥
Some texts introduce the
join lattice
, in which the best solution is
⊥
and
the worst solution is
. Fortunately, it is possible to study all of data flow
analysis using only the
meet lattices
we have introduced here. Intuitively, a
join lattice can be turned into a meet lattice by flipping it upside down. The
resulting data flow framework then solves the
complement
of the join lattice's
problem. For example, a deadvariablesanalysis could be performed on a join
lattice, but we can solve livevariables instead using a meet lattice.
