Java Reference
In-Depth Information
1
2
3
11
4
9
12
13
5
8
10
6
7
Figure 14.13: Superposition of edges from Figure 14.10 on the DFST
of Figure 14.12. Back edges are bold, cross edges are
dashed, and chord edges are dotted. All other edges are tree
edges from the DFST.
Thus, once the depth-first numbering has been computed, a
constant-time
test
can determine if
X
is a ancestor of
Y
. Figure 14.14 shows how to use the
structures developed by the algorithm of Figure 14.9 to determine the type of
an edge
X
→
Y
with respect to a DFST. The property satisfied by a flow graph
edge or path is denoted below the edge or path symbol.
Another useful set of abstractions for program analysis and optimization are
the dominance data structures—in particular, the
dominator tree
of a flow
graph. The dominators of node
Z
act like a sequence of gates in a flow
graph: control flow can reach
Z
only by passing through
Z
's dominators. The
various forms of dominance are defined with respect to a control flow graph
G
f
=
(
N
f
,E
f
,
root
) as follows:
