Java Reference
In-Depth Information
X
1
A
E
X
2
B
C
F
G
X
3
D
H
(a)
(b)
(c)
Figure 14.15: Flow graph examples for dominance.
act as fibers along which light can be transmitted. To find the nodes dominated
by
X
, imagine that
X
is opaque: any light entering
X
is blocked and cannot
be transmitted along edges leaving
X
. Nodes that fall in the resulting shadow
cast by
X
are strictly dominated by
X
. With node 3 opaque in Figure 14.16,
light cannot travel to nodes 9 or 10. Thus node 3 dominates nodes 3, 9, and 10.
Light reaches node 4 from node 2, so 4 is not dominated by node 3.
We first examine an algorithm that determines
all
dominators of each node in
aflowgraph
N
f
,E
f
). The algorithm is based on the observation that
anode
Z
is dominated by itself and by any node that dominates
all
of
Z
's
predecessors. In other words, to reach
Z
, control flow must pass through one
of
Z
's flow graph predecessors. Any node
Y
that dominates each predecessor
of
Z
must appear on every path from
root
to
Z
.
G
f
=
(
Equation 14.4
The nodes that dominate Z can be determined as follows:
dom
(
Z
)
={
Z
}∪
dom
(
Y
)
∈
E
f
(
Y
,
Z
)
Each node of the flow graph contributes such an equation, and we seek a
solution that satisfies every equation while providing the best answer. This
style of problem formulation is very similar to the formulation of the data flow
problems we study in Section 14.4, so it is worthwhile to examine this method
in some detail.
Consider applying Equation 14.4 to the graph shown in Figure 14.15(c).
Applying Equation 14.4 to node
E
yields
dom
(
E
)
={
E
}
. The equation written
