Java Reference
In-Depth Information
8. Dominance is defined by Definition 14.3 on page 566. A related concept
is
postdominance
, which can be defined as follows:
Definition 14.28
A graph has a distinguished
exit node
if it contains one
node z such that z has no successors and z can be reached from all nodes in
the graph.
Definition 14.29
If a graph
G
f
has a distinguished exit node z, then the
reverse
of
G
f
is the flow graph defined by
(
N
f
,{
(
x
,
y
)
|
(
y
,
x
)
∈E
f
},
z
)
and
G
f
is said to be
reversible
.
Definition 14.30
•
Node Z
postdominates
node Y if every path from Y includes node Z.
A node always postdominates itself.
•
Node Z
strictly postdominates
YifZ
Y and Z postdominates Y.
•
The
immediate postdominator
of node Y is the
closest
strict post-
dominator of Y.
•
The
postdominator forest
for
G
f
has nodes
N
f
;ZisaparentofY
in this forest if and only i
ff
Z immediately postdominates Y.
If
G
f
has an exit node, then the postdominator forest is a tree.
Draw the postdominator tree for each of the flow graphs shown in Fig-
ure 14.15.
9. Given the definition of
postdominance
from Exercise 8, prove the fol-
lowing theorem:
Theorem 14.31
Node X dominates node Y in a reversible flow graph
G
f
i
ff
node Y postdominates node X in the reverse of
G
f
.
10. Use Theorem 14.31 to create an algorithm that computes the postdomi-
nators of a flow graph.
