Java Reference
In-Depth Information
•
Both
w
and
x
have constant (albeit di
erent) values at nodes
10
and
9
.
When a meet is taken coming into
11
,
w
'svalueiscomputedasthemeet
of 1 and 5, which yields
ff
⊥
. Similarly, the value for
x
coming into
11
is
⊥
.
Thus, the expression
w
+
x
inside
11
is computed as
⊥
.
While the variables
w
and
x
have di
ff
erent values coming into
11
,their
sum does not.
If the transfer function at
11
is applied to the values
emitted from
9
,then
w
+
x
=
5
+
3
=
8. Applying the transfer function
to the output of
10
yields
w
+
x
=
1
+
7
=
8. The meet of those two values
finds
w
=
8, but this solution is not computed by the iterative algorithm
of Figure 14.51.
This observation is actually a proof that constant propagation is
not
a
distributive framework
.
SSA form is introduced in Chapter 10 as an intermediate language in which
each variable name is assigned exactly once. Figure 10.5 on page 412 shows a
programbefore and after its translation into SSA form. We can now study how
this translation is accomplished, as it is based on some of the advanced com-
piler structures presented in this chapter. Figure 14.62 shows a program and
its control flow graph. The SSA construction algorithm requires the graph's
dominator tree and dominance frontiers, which are shown in Figure 14.63.
Based on these structures, there are two phases to the SSA construction
algorithm. The algorithm shown Figure 14.64 computes SSA form variable by
variable, with the phases shown in Figures 14.65 and 14.67.
In the first phase, the location of each
φ
-function is determined. Each
φ
-function represents the convergence (i.e., meet) of two or more names of
a given variable. The
arity
(number of parameters) for a given
-function is
determined by the number of edges into the node containing the function.
All nodes with
φ
-functions must have at least two incoming edges. In Fig-
ure 14.62(b), examples of such nodes include 8, 9, and 11, but node 10 would
never host a
φ
φ
-function.
While having at least two inedges is necessary for a node to host a
φ
-
function, it is not su
cient. At least two distinct names for a given variable
must reach a node to require a
-function for the name. If Figure 14.62(b)
contained an assignment to a variable
x
in node 1, then the only node to
receive a
φ
-function for
x
would be the Stop node. While nodes such as 8
have two inedges, the same name for variable
x
flows on both edges, so no
φ
φ
-function is necessary.
