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.
14.7.2 Renaming
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
.
 
 
Search WWH ::




Custom Search