Java Reference
In-Depth Information
Marker
40
in Figure 14.21 invokes the
eval
function on each predeces-
sor
X
of node
Y
.The
method considers
X
and all of its ancestors that
have already been visited thus far by Marker
39
, returning the one that has
the sneakiest semidominator. That ancestor is received as
a
at Marker
40
.
If
sdom
(
a
) is sneakier than what has been found so far for
Y
,then
Y
's se-
mindominator is updated at Marker
41
.Eachnode
Y
contributes a single
edge (
sdom
(
Y
)
eval
E
f
at Marker
45
.
Marker
37
in Figure 14.20 does not consider nodes in any particular order,
but the fast algorithm in Figure 14.21 considers nodes in reverse order of their
depth-first numbering. When visiting node
Y
, semidominators have already
been computed for any cross or back edges to
Y
, because the source of each
such edge is depth-first numbered greater than
Y
.
At Markers
42
and
43
, the algorithm maintains a linked list of nodes
with the same semidominator. This structure is used in Figure 14.24 to visit all
nodes semidominated by a given node.
The computation of semidominators for the graph shown in Figure 14.13
is given in Figure 14.22. Figure 14.23 shows the graph
,
Y
)to
G
f
created from the
graph of Figure 14.13, with all cross and back edges eliminated in favor of tree
and chord edges.
Dominators of a Graph with Tree and Chord Edges
The fast dominance algorithm is next concerned with determining immediate
dominators for graphs with neither cross nor back edges, such as the one
shown in Figure 14.23. If node
n
receives a curved edge, then the source of that
edge is
n
's semidominator; otherwise,
n
's DFST parent is its semidominator.
For example, a curved edge in Figure 14.23 shows that node 3 serves as node 5's
semidominator, with node 4 as node 5's parent in the DFST. Node 9 receives
no curved edges, so its semidominator is its DFST parent, node 3.
Unfortunately, a node may not be dominated by its semidominator. For
example, node 5 is semidominated by node 3, but Figure 14.18 indicates that
dom
(5)
. Thus node 3 does not dominate node 5, so it certainly cannot
serve as 5's immediate dominator. This situation happens when a node's
semidominator is
bypassed
by one of its ancestors.
={
1
,
5
}
In Figure 14.23, node 3
would have dominated node 5 if not for the edge 2
4, which bypasses 3.
Node 2 would have then dominated node 5 except that it also is bypassed by
the edge 1
→
→
3.
Lemma 14.11
If sdom
(
Y
)
dominates Y, then sdom
(
Y
)
is the immediate domina-
tor of Y.
Proof: We need only show that no ancestor of
Y
between itself and
sdom
(
Y
)candominate
Y
. From Definition 14.10, there must be a path
