Java Reference
In-Depth Information
procedure
semi
D
ominators
(
G
f
)
foreach
X
∈N
f
do
sdom
(
X
)
←
dfn
(
X
)
null
for
n
=
NumNodes
downto
2
do
s
.
head
(
X
)
←
ancestor
(
X
)
←
Y
←
vertex
(
n
)
foreach
X
∈
Pred
(
Y
)
do
39
a
← eval
(
X
)
40
if
sdom
(
a
)
<
sdom
(
Y
)
41
then
sdom
(
Y
)
←
sdom
(
a
)
s
.
next
(
Y
)
←
s
.
head
(
vertex
(
sdom
(
Y
)))
42
s
.
head
(
vertex
(
sdom
(
Y
)))
←
Y
43
ancestor
(
Y
)
←
parent
(
Y
)
44
N
f
←N
f
E
f
←{
45
(
vertex
(
sdom
(
Y
))
,
Y
)
|
Y
∈N
f
}
E
f
←E
f
∪{
all DFST tree edges
}
end
function
eval
(
X
)
returns
node
sneakiest
←∞
for
p
=
X
repeat
p
←
ancestor
(
p
)
do
if
p
=⊥
then return
accomplice
else
if
sdom
(
p
)
46
<
sneakiest
then
accomplice
←
p
sneakiest
←
sdom
(
p
)
end
Figure 14.21: Semidominator algorithm.
sdom
(
Y
)
+
→
Y
such that all intermediate nodes are depth-first numbered
greater than
Y
. Such a path prevents any ancestor of
Y
between itself and
sdom
(
Y
) from dominating
Y
.
Lemma 14.11's one-way implication helps explain the term
semidominator
:
sdom
(
Y
) is sometimes the immediate dominator of
Y
. However, it is possible
that
sdom
(
Y
) does not even dominate
Y
, as shown by the examples above and
by the illustration in Figure 14.25. Even in this case,
sdom
(
Y
) plays a role in
computing
Y
's immediate dominator in the algorithm of Figure 14.24. This
algorithm performs two passes (described below) to compute the immediate
dominators for
N
f
.
In the first pass, Marker
48
considers nodes in the reverse order of their
N
f
. The dominators of
N
f
are also the dominators of
