Java Reference
In-Depth Information
Soln IN
Soln1
Soln2
OUT = f(IN)
Soln3
Soln OUT
(a)
(b)
Figure 14.45: (a) A meet lattice; (b) A node's transfer function.
•
Information converging at a node is combined as directed by the meet
lattice.
•
As described in Section 14.5, information is propagated through the data
flow evaluation graph to obtain a solution.
For the problems considered here, a flow graph's nodes represent some com-
ponent of a program's behavior and its edges represent potential transfer of
control between nodes. In posing an optimization problem as a data flow
framework, the resulting framework is said to be:
•
forward
, if the solution at a node can depend only on the program's
past behavior. Evaluating such problems involves propagating informa-
tion
forward
through the flow graph. Thus, the control flow graph in
Figure 14.41(b) serves as the data flow evaluation graph in Figure 14.42
for analyzing the availability of the expression
v
+
w
in the program of
Figure 14.41(a).
•
backward
, if the solution at a node can depend only on the program's
future behavior. The livevariablesproblem introduced in Section 14.3.2
is such a problem. For live variables, a suitable data flow evaluation
graph is the
reverse
control flow graph, as shown in Figure 14.44.
•
bidirectional
, if both past and future behavior is relevant.
In this chapter, we discuss only forward or backward problems, and we orient
the edges of a data flow evaluation graph in the direction of the data flow
problem. With this assumption, information always propagates in the direc-
tion of the graph's edges. It is convenient to augment data flow evaluation
