Java Reference
In-Depth Information
•
The meet operator is applied using the lattice shown in Figure 14.59. The
lattice is applied separately for each variable of interest.
•
The transfer function at node
Y
interprets the node by substituting the
node's incoming solution for each variable used in the node's expression.
Suppose node
v
is computed using the variables in set
U
. The solution
for variable
v
after node
Y
is computed as follows:
-
If any variable in
U
has value
⊥
,then
v
has value
⊥
. For example,
if
x
has value
⊥
, then the expression
w
+
x
has value
⊥
even if
w
is
.
-
Otherwise, if any variable in
U
has value
constant or
,then
v
has value
.For
.
-
Finally, if all variables in
U
have constant value, then the expression
is evaluated and the constant value is assigned to
v
.
example, if
y
has value
, then the expression
y
+
2isalso
Figure 14.61 shows the evaluation of Figure 14.60 by the algorithm from
Figure 14.51.
Initially, the value of every solution is
.Eachnodeisthen
considered in interval order: [ 1
2]. Nodes
5
and
14
are straightforward, in that they assert values for
w
and
y
, respectively,
regardless of their input solutions. When
13
,
3
,
4
,
14
,
5
,
13
,
6
,
7
,
8
,
9
,
10
,
11
,
12
,
is evaluated, the current value
for
y
is
, which could be any constant. Thus, with
w
=
y
+
2,
w
can also be
any constant and its solution is emitted as
.When
7
is evaluated, the input
value for
y
is computed as the meet of
6
's value of 5 with
13
's value of
.
Thus, at least for this iteration,
w
has the value 5 and
7
computes
y
using
y
=
w
−
3. It is important to notice that
y
is ultimately found to be the
constant 3 only because we initially gave it a value of
2
=
.
The rest of the nodes are processed in the first iteration as shown in Fig-
ure 14.61, but no constants are found except those emitted by a single node
based on an assignment from a constant. In the second iteration, the solutions
for all the variables are propagated along the back edges, but all solutions
converge in this iteration.
The example in Figure 14.60 serves to illustrate the following features of
constantpropagation:
•
The graph has a path to
13
that avoids initialization of
y
.Dataflow
evaluation in Figure 14.61 nonetheless finds that
y
is constant almost
everywhere in the flow graph. Although an uninitialized variable may
indicate a programming error, the optimizer can assume an uninitialized
variable has any value of choice without fear of contradiction.
If a programming language's semantics insist on implicit initialization
of all variables (e.g. to 0), then such initialization must be represented
by an assignment to these variables at the Start node.
