Java Reference
In-Depth Information
graphs with a Start and Stop node, and an edge from Start to Stop,asshown
in Figures 14.42 and 14.44.
In compilers where space is at a premium, nodes of a control flow graph
typically correspond to the
maximal
straight-line sequences (the
basic blocks
)
of a program. While this design conserves space, program analysis and opti-
mization must then occur at two levels:
within
and
between
the basic blocks.
These two levels are called
local
and
global data flow analysis
, respectively.
An extra level of analysis complicates our discussion and can increase the
expense of writing, maintaining, and documenting an optimizing compiler.
We therefore formulate data flow evaluation graphs whose nodes model the
e
instruction.
ects of perhaps a single JVM or MIPS
R
ff
As with all lattices, the
meet lattice
represents a partial order imposed on a
set. Formally, the meet lattice is defined by the tuple
A
,,⊥,,∧
L
=
which has the following components:
•
A
solution space
A
. In a data flow framework, the relevant set is the
space of all possible solutions to the data flow problem. Exercise 36
considers the live variables problem, posed over a set of
n
variables.
Since each variable is either live or not live, the set of possible solutions
contains 2
n
elements. Fortunately, we need not enumerate or represent
all elements in this large set. In fact, some data flow problems (e.g.,
constantpropagationdiscussed in Section 14.6) have an infinite solution
space.
•
The
meet operator
. The partial order present in the lattice directs how
to combine (summarize) multiple solutions to a data flow problem. In
Figure 14.42, the first node of the outer loop receives two edges—
v
+
w
is
available on one edge and not available on the other. The meet operation
(
∧
is associa-
tive and commutative, so multiple solutions are easily summarized by
applying
∧
) serves to summarize the two solutions. Mathematically,
∧
∧
pairwise in any order.
•
Distinguished elements
. Lattices associated with data flow
frameworks always include the following distinguished elements of
A
:
and
⊥
-
intuitively is the solution that allows the most optimization.
-
⊥
intuitively is the solution that prevents or inhibits optimization.
