Java Reference
In-Depth Information
/
Called from Marker
101
/
procedure
place
P
his
(
V
)
foreach
node
∈N
cg
do
node
.
hasPhi
←
node
.
processed
←
false
103
(
de f
.
getNode())
foreach
de f
∈
de f s
(
V
)
do call
add
N
ode
104
worklist
←∅
while
worklist
∅
do
X
←
worklist
.
pickAndRemove()
foreach
Y
∈
DF
(
X
)
do
105
if not
Y
.
hasPhi
then
Y
.
hasPhi
←
true
At node
Y
,place
V
← φ
106
(
V
,...,
V
)
call
add
N
ode
(
Y
)
107
end
procedure
(
node
)
if not
node
.
processed
then
worklist
←
worklist
∪{
node
}
node
.
processed
←
true
add
N
ode
end
Figure 14.65: Placement of
φ
-functions.
assignment may in turn meet other names for
V
,sothe
-placement algorithm
iterates over dominance frontiers until all nodes needing
φ
φ
-functions have
them.
The algorithm for placing
φ
-functions is given in Figure 14.65. The method
place
is called separately for each variable
V
in a program. Prior to
processing the variable
V
,Marker
104
sets the per-node flags
hasPhi
and
processed
to
false
.
P
his
•
The
hasPhi
flag keeps track of whether its associated node already has a
φ
-function for the current variable
V
. Only one such function is needed
at any node.
•
The
processed
flag keeps track of whether a definition of
V
has been put
on the
worklist
for the current variable
V
.
Marker
105
considers definition sites for
V
in any order. For each node
X
that
defines
V
,Marker
106
ensures that every node
Y
in
DF
(
X
)hasa
φ
-function
for
V
. Recall that the arity of the
φ
-function is determined by the number of
inedges to node
Y
.Each
φ
-function placed in the program is itself a definition