Java Reference
In-Depth Information
site for
V
.Marker
107
makes sure that the definition site is considered by the
algorithm for further
φ
placement. Figure 14.66 shows the results of placing
φ
-functions for our example.
The final step in constructing SSA form is to rename all of the definition sites so
they are unique. While we simply add subscripts to create unique names, the
variables
i
2
and
i
3
are as distinct from each other as are
x
and
y
.Thesubscripts
enable us to visually track the origin of each name and to see the progress of
the renaming algorithm.
The primary structure used in the renaming algorithm is the
dominator
tree
, although the control flow graph is also consulted. Each definition site is
given a unique name by adding a subscript, as described above. The challenge
for this part of SSA construction is determining the unique definition site that
reaches a given use of a variable name. There are two cases:
•
Each original (non-
) use of a variable name
v
is reached by the definition
of
v
that appears in the node that most closely dominates that use.
φ
•
Agiven use of
v
in a
-function is reached by the definition of
v
that flows
on its associated inedge to the node containing the
φ
φ
-function. From the
definition of
dominance frontiers
,ifa
-function appears at some node
Z
,then
Z
is in the dominance frontier of
X
,and
X
must dominate some
predecessor
Y
of
Z
. The definition of
v
that reaches
Y
is the definition
that reaches the use of
v
using the edge (
Y
,
Z
) into the
φ
-function at
Z
.
When the algorithm is at a node
Y
, it can check whether a
φ
-function
exists at a successor
Z
of
Y
and forward the appropriate name for
v
to
the
φ
φ
-function.
The algorithm for renaming variables is in Figure 14.67, and the results of
applying the algorithm to our example are shown in Figure 14.68.
Markers
108
and
109
initialize the
stack
and
version
variables, which are
used in the
method. The
stack
keeps track of the version of the
current variable
V
that reaches any ordinary uses. The
version
variable keeps
track of the name that will be created for the next definition of
V
(
V
version
). The
renaming algorithm makes the following assumptions:
rename
H
elper
•
The
Start
node is assumed to contain a definition of every variable,
which the algorithm will number as version 0. Thus, the
stack
, while
initially empty, receives the definition of
V
from
Start
in the initial call to
rename
D
omtree
.