Java Reference
In-Depth Information
We have introduced the notion of a data flow framework informally, relying on
examples drawn from optimizing compilers. In this section, we formalize the
notion of a
data flowframework
. Aswe examine these details, it will be helpful
to refer to the available expressions and livevariablesproblems introduced in
Section 14.3. The components of a data flow framework
D=
(
G
eg
,
L
,F
)areas
follows:
•
An
evaluation graph
G
eg
. This directed graph's nodes typically rep-
resent some aspect of a program's behavior. A node may represent a
single instruction, a nonbranching sequence of instructions, or an entire
procedure. The graph's edges represent a relation over the nodes. For
example, the edges may indicate potential transfer of control by branch-
ing or by procedure call. We assume the graph's edges are oriented in
the “direction” of the data flow problem.
•
A
meet lattice
L
. This is a mathematical structure that describes the
solution space of the data flow problem and designates how to combine
multiple solutions in a safe (conservative) way. It is convenient to present
such lattices as
Hasse diagrams
.The
meet
of two elements can be found
by tracing down the diagram from those elements until the traces first
meet at a common point. For example, the lattice in Figure 14.45(a)
specifies
Soln
1and
Soln
2 meet at
Soln
3.
•
Asetof
transfer functions
. Each function models the behavior of a
possible node (or path of nodes) with respect to the optimization problem
under study. Figure 14.45(b) depicts a generic transfer function. A
transfer function's input is the solution that holds on entry to the node.
If multiple edges converge at the node, then a
meet
may be taken of those
edges' solutions to form the node's input. The transfer function specifies
how the node's output is computed given its input.
F
We next examine each of these components in some detail. Ryder andMarlowe
o
er a more thorough treatment of data flow frameworks and their proper-
ties [MR90].
ff
The
data flow evaluation graph
is constructed for an optimization problem,
so that evaluation of this graph produces a solution to the problem:
•
Transfer functions are associated with each node.
