Java Reference
In-Depth Information
Start
Node
Y F
(
Y
)
Start
{}
1
Stop
1
{
Stop
}
2
{
2
,
Stop
}
3
{
8
}
2
4
{
6
}
5
{
6
}
6
{
8
}
3
7
8
7
{
8
}
8
{
2
,
Stop
}
4
5
6
9
9
{
2
,
9
,
Stop
}
10
{
11
}
11
{
2
,
9
,
Stop
}
10
11
12
{
2
,
Stop
}
Stop
{}
12
(a)
(b)
Figure 14.63: (a) Dominator tree and (b) Dominance frontiers for the
control flow graph in Figure 14.62.
foreach
V
∈
Variables
do
call
place
P
his
(
V
)
101
call
rename
(
V
)
102
Figure 14.64: Algorithm for computing SSA form.
14.7.1 Placing
φ
-Functions
The structure we use for determining where to place
-functions is the
dom-
inance frontier graph
, which is summarized for our example in Figure 14.63.
If a definition of a variable
V
occurs at node
X
,then
DF
(
X
)isthesetofnodes
where that definition will meet other definitions. Thus a
φ
-function for
V
is
required at every node in
DF
(
Y
). Suppose node 4 in Figure 14.62 contained an
assignment to variable
V
. Consulting
DF
(4) in Figure 14.63, node 6 requires a
φ
φ
-function. We know the form of the code introduced at node 6 must be:
V
=φ
(
V
,
V
)
At node 6, two di
erent names for
V
will reach the node, but we do not yet
know which ones. The result of the
ff
φ
-function is a new assignment to
V
.That
