Java Reference
In-Depth Information
Lemma 14.5
If X
Yin
G
f
, then X must be an ancestor of Y in the depth-first
spanning tree of
G
f
.
Proof: Suppose by contradiction that
X
is not an ancestor of
Y
in the
DFST. Then there exists a path (of tree edges) from
root
to
Y
that does not
contain
X
,so
X
cannot dominate
Y
.
It follows that the immediate dominator of
Y
,
idom
(
Y
),isaproperancestorof
Y
in the DFST.
Recall from Section 14.2.4 that edges of a flow graph are classified as
tree, chord, back, or cross edges with respect to a DFST of the flow graph.
Figure 14.13 shows such a classification for the edges of Figure 14.10 with
respect to the DFST show in Figure 14.12. The fast algorithm uses these edge
classifications and performs the following steps:
1. A new graph
G
f
with the same nodes, tree edges, and
at least
the same chord edges as found in a DFST for
G
f
is created from
G
f
. However,
G
f
has neither cross nor back edges. With respect to dominance, the e
ects
of all cross and back edges are represented by
forward
(tree or chord)
edges in
ff
G
f
.
2. Immediate dominators are computed for
G
f
, which contains su
cient
chord edges so that
X
=
idom
(
Y
)in
G
f
i
ff
X
=
idom
(
Y
)in
G
f
.
In other words, the algorithm eliminates back and cross edges in favor of tree
and (potentially new) chord edges. This reduces the original problem to the
simpler problem of computing immediate dominance for graphs having only
forward edges.
Elimination of Cross and Back Edges
From Lemma 14.5, we know that
Y
's immediate dominator is some DFST
ancestor of
Y
.
Lemma 14.6
Node s can be the immediate dominator of Y only if there is a flow
graph path
(
s
+
p
=
→
Y
)
such that s and Y are the only DFST ancestors of Y in p.
Proof: Suppose that
s
dominates
Y
, but no such path
p
exists in the flow
graph. The flow graph must then contain a path
s
+
→
W
+
→
Y
