Java Reference
In-Depth Information
Property
Te s t
X
−→
tree
Y
parent
(
Y
)
=
X
X
−→
chord
Y dfn
(
X
)
<
dfn
(
Y
) nd
parent
(
Y
)
X
X
−→
back
Y
Y
X
X
−→
cross
Y dfn
(
X
)
≥
dfn
(
Y
) nd
Y
X
Figure 14.14: Determining the relationship of edge
X
→
Y
.
Definition 14.3
•
Node Y
dominates
node Z, denoted Y
Z, i
ff
every path in
G
f
from root
to Z includes node Y. A node always dominates itself.
•
Node Y
strictly dominates
Z, denoted Y
Z, i
ff
Y
ZandY
Z.
•
The
immediate dominator
of node Z, denoted idom
(
Z
)
, is the closest strict
dominator of Z:
Y
=
idom
(
Z
)
⇐⇒
(
Y
Zand
∀
X
Z
,
X
Y
)
•
The
dominator tree
for
G
f
has nodes
N
f
; Y is a parent of Z in this tree i
ff
Y
=
idom
(
Z
)
.
As a simple example, consider a sequence of nodes
X
1
,...,
X
n
where control
flow enters the sequence only at
X
1
, exits only after
X
n
, and control transfers
only from node
X
i
to node
X
i
+1
. Such an example is shown in Figure 14.15(a)
for
n
=
,
X
2
3. Recalling the discussion of Section 14.2.1, such a sequence is es-
sentially a basic block and might be represented by a single node in the flow
graph. However, if the nodes are distinct in the flow graph as shown in Fig-
ure 14.15(a), then each
X
i
dominates nodes in
{
X
j
|
j
≥
i
}
, strictly dominates
nodes in
, and immediately dominates node
X
i
+1
.
As another example, consider the flow graph for an if-then-else state-
ment as shown in Figure 14.15(b). In this graph, node
A
immediately domi-
nates nodes
B
,
C
,and
D
. The control flow graph in Figure 14.15(c) models a
loop where node
F
decides whether to continue or terminate the loop. Node
E
dominates all of the nodes; node
F
dominates nodes
F
,
G
,and
H
;nodes
G
and
H
dominate only themselves.
A visual interpretation of dominance is shown in Figure 14.16. Suppose
the
root
node of a flow graph is a light source, and the edges of the flow graph
{
X
j
|
j
>
i
}
