Java Reference
In-Depth Information
procedure
fast
D
ominators
(
G
f
)
foreach
X
∈N
f
do
ancestor
(
X
)
←
null
47
for
n
=
NumNodes
downto
1
do
Y
←
vertex
(
n
)
48
foreach
{
Z
|
n
=
sdom
(
Z
)
}
do
49
t
← eval
(
Z
)
s
←
sdom
(
t
)
50
if
s
=
n
then
51
idom
(
Z
)
←
Y
52
else
idom
(
Z
)
null
SameDomAs
(
Z
)
←
53
←
t
foreach
c
∈
Children
(
Y
)
do
ancestor
(
c
)
←
Y
54
for
n
=
2
to
NumNodes
do
Z
←
vertex
(
n
)
if
idom
(
Z
)
55
=
null
then
idom
(
Z
)
←
idom
(
SameDomAs
(
Z
))
idom
(
root
)
←
null
end
Figure 14.24: Algorithm for computing immediate dominators of a
graph with no cross or back edges. The function
is taken
from Figure 14.21, but the
ancestor
map is reset at Marker
47
.
eval
s
Y
t
Z
Figure 14.25: A node's semidominator does not necessarily dominate
that node.
