Java Reference
In-Depth Information
Node
Z
at
t
at
s
at
idom
(
Z
)
SameDomAs
(
Z
)
Y
49
50
51
52
53
13
12
11
12
12
11
11
13
13
11
11
10
9
10
10
9
9
8
7
6
5
4
3
5
4
2
4
6
4
2
4
8
4
2
4
9
9
3
3
2
4
3
1
3
7
3
1
3
11
11
2
2
1
2
2
1
1
3
3
1
1
Figure 14.26: Trace of the loop at Marker
48
.
Given the information as shown in Figure 14.26, the final pass processes
nodes in
increasing
order of their depth-first number, startingwith node 2. Each
node either has its immediate dominator already computed in Figure 14.26, or
else its immediate dominator is known to be the same as some node of lower
depth-first number. Nodes 2 and 3 are known to have node 1 as their immediate
dominator. Node 4 has the same immediate dominator as node 3, which can
now be resolved as node 1. Nodes 5 and 6 have the same immediate dominator
as node 4, which can now be resolved as node 1. This process continues until
the dominator tree is obtained, as shown in Figure 14.27.
Sections 14.2.6 and 14.2.7 discuss dominators of a flow graph. If
X
∈
dom
(
Y
),
then
X
appears on all paths in the flow graph from
root
to
Y
. Figure 14.16 on
page 568 provides a visual interpretation of dominance. If the
root
of the flow
graph is a light source and light is transmitted along edges, then nodes strictly
dominated by
X
are in the shadow cast by making
X
opaque, so that no light
