Java Reference
In-Depth Information
14.3
Introduction to Data Flow Analysis
As discussed in Section 14.1, an optimizing compiler is typically organized
as a series of
passes
. Each pass may require approximate information about
the program's runtime behavior to do its job.
Data flow frameworks
o
ff
er a
unified and mathematically appealing structure for such analysis.
In Section 14.4 we present a more rigorous formulation of data flow frame-
works. Here, we discuss some
data flow problems
informally, examining a
few popular optimization problems and reasoning about their data flow for-
mulation. For each problem, we are interested in the following:
•
What is the e
ff
ect of a code sequence on the solution to the problem?
•
When branching in a program converges, how do we summarize the
solution so that we need not keep track of branch-specific behavior?
•
What are the best and worst possible solutions?
We use the program and
control flow graph
shown in Figure 14.41 as an
example.
Local solutions
to the above questions are combined by data flow analysis
to arrive at a
global solution
. By local, we mean information that is present
on a given edge because of an adjacent node's behavior. By global, we mean
that a solution can be found for every edge of a flow graph.
Figure 14.41 contains several computations of the expression
v
+
w
.Ifwecan
show that the particular value of
v
+
w
computed at Marker
83
is already
available
, then there is no need to recompute the expression at Marker
83
.
More specifically, an expression
expr
is available at edge
e
of a flow graph if
the past behavior of the program necessarily includes a computation of the
value of
expr
as it would appear on edge
e
.Theavailable expressions data
flow problem analyzes programs to determine such information.
To so l ve the available expressions problem, a compiler must examine a
program to determine that expression
expr
is available at edge
e
, regardless of
how the program arrives at edge
e
. If a compiler simply executed a program to
find such information, then an infinite loop could prevent the compiler from
finishing. Finding such loops is in general
undecidable
[Mar03]. Compilers
instead perform
static analysis
, which symbolically interprets a program and
avoids infinite loops.
Returning to our example,
v
+
w
is available at Marker
83
if every path
arriving at Marker
83
computes
v
+
w
without a subsequent change to
v
or
w
.
