Java Reference
In-Depth Information
1
2
3
11
4
9
12
13
5
8
10
6
7
Figure 14.23: Dominator-equivalent flow graph from Figure 14.13 with
only chord and DFST tree edges. The chord edges represent
the semindominator relation (Figure 14.22) for nodes whose
parent is not their semidominator.
at Marker
50
can determine if
sdom
(
Z
)dominates
Z
.If
Y
=
sdom
(
Z
) happens
to dominate
Z
,then
Y
is established as
idom
(
Z
)atMarker
52
.Otherwise,
we have the situation described previously for Figure 14.23 and shown more
explicitly in Figure 14.25. Some ancestor
s
of
Z bypasses Y
by semidominating
t
.Inthiscase,if
s
is the lowest-numbered node to bypass
Y
with respect to
Z
,
then nodes
t
and
Z
have the same immediate dominator:
Lemma 14.13
In the situation shown in Figure 14.25, dom
(
t
)
=
dom
(
Z
)
if s is
the lowest-numbered semidominator of all ancestors of Z between sdom
(
Z
)
and Z.
Proof: Left as Exercise 21.
Corollary 14.14
In Lemma 14.13, if s
=
sdom
(
Z
)
then idom
(
Z
)
=
vertex
(
s
)
.
Figure 14.26 shows a trace of the loop at Marker
48
. Although the loop counts
down by depth-first number, the actual node under consideration is node
Z
,
semidominated by node
Y
,atMarker
49
. Figure 14.26 shows the accomplice
t
found at Marker
50
by calling
.Node
s
is set to
t
's semidominator and
then compared to
Z
's semidominator at Marker
51
.
eval
