Java Reference
In-Depth Information
Finally, we can consider data flow evaluation in the context of a meet
lattice. While this is discussed more fully in Section 14.5, we can identify some
points (elements) of interest in the lattice in addition to
and
⊥
:
•
Some point in the lattice represents the best solution for a given data flow
problem. That solution holds no matter what path is taken at runtime
in the control flow graph. If each possible path is considered separately,
then the best solution would be the
meet
of each of those path's solutions.
Most programs contain loops and have apparently an infinite number of
such paths.
Nonetheless, for some problems (Section 14.5.4), it is possible to compute
the lattice element known as the
meet over all paths
(MOP) solution even
for programs with an infinite number of possible paths.
•
Consider any lattice element
b
such that
b
MOP
. Suchanelementis
safe
in the sense that optimization based on
b
cannot contradict information
on any possible program path. The
⊥
element is always safe but results
in the least amount of optimization.
Correspondingly, consider any element
a
for which
MOP
≺
a
.Suchan
element is
unsafe
in the sense that optimization based on
a
may not
properly preserve a program's meaning. The
element may or may not
be unsafe, depending on MOP, because
MOP
.
•
Data flow evaluation (Section 14.5) terminates by finding a safe solution
at or belowMOP. This solution is called the
maximumfixed point
(MFP)
as it represents the fixed point of the computation and it is as good a
solution as can be computed by an iterative approach that summarizes
a node's inputs using
meet
.
These issues are considered again in Section 14.5.4.
Our data flow framework needs a mechanism to describe the e
ects of a frag-
ment of program code—specifically, the code represented by a path through
the flow graph. Consider a single node of the data flow evaluation graph.
Referring to Figure 14.45(b), a solution is present on entry to the node and the
transfer function is responsible for converting this input solution to a value
that holds after the node executes. Mathematically, the node's behavior can be
modeled as a
function
whose domain and range are the meet lattice
A
.
We denote the set of all such
transfer functions
inadataflowframework
ff
as
. Each functionmust be
total
—defined on every possible input. Moreover,
we shall require each function to behave
monotonically
—the function cannot
produce a better result when presented with a worse input:
F
