Java Reference
In-Depth Information
procedure
dominance
F
rontiers
(
G
f
,
DomTree
)
traverse tree
(
DomTree
)
order
BottomUp
at node
(
X
)
do
DF
(
X
)
←∅
foreach
Y
∈
Succ
(
X
)
do
if
idom
(
Y
)
X
then
∪{
Y
}
foreach
Z
|
X
=
idom
(
Z
)
do
foreach
Y
∈
DF
(
Z
)
do
if
idom
(
Y
)
DF
(
X
)
←
DF
(
X
)
59
X
then
DF
(
X
)
←
DF
(
X
)
∪{
Y
}
60
end
Figure 14.29: Computation of dominance frontiers.
In a bottom-up traversal of the dominator tree from Figure 14.27, node 6
initially appears in
DF
local
(10) due to the edge from 10 to 6, and the fact that
node 10 does not dominate node 6. Instead of testing for dominance, the
following lemma proves that immediate dominance su
ces:
Lemma 14.17
If
(
Y
,
Z
)
∈E
f
then Y
Z
⇐⇒
Y
=
idom
(
Z
)
Proof: The
,if
Y
dominates
Z
, then the
edge (
Y
,
Z
) guarantees that
Y
appears just before
Z
on all paths from
root
.
Therefore,
Y
=
idom
(
Z
).
⇐=
implication is trivial. For
=⇒
Thus, a better definition of
DF
local
is:
Equation 14.18
DF
local
(
X
)
={
Y
∈
Succ
(
X
)
|
idom
(
Y
)
X
}
Thus, node 6 is added to
DF
(10) because 10
idom
(6). Node 6 then appears in
DF
up
(10) by Equation 14.16.
When moving up the dominator tree to node 9, node 6 is included in
DF
(9)
because of node 10's contribution to its parent in Equation 14.16. Node 8 is
included in
DF
local
(9) by Equation 14.18.
DF
up
(9) includes both nodes 6 and 8,
which are added to
DF
(3) when we move up the dominator tree. In computing
DF
up
(3) by Equation 14.16, we find that node 1 dominates all nodes in
DF
(3)
so
DF
up
(3)
. Due to our bottom-up traversal of the dominator tree, the
test for general dominance in Equation 14.16 can be simplified to immediate
dominance:
= {}
DF
up
(
Z
)
={
Y
∈
DF
(
Z
)
|
idom
(
Y
)
parent
(
Z
)
}
The improved dominance frontier algorithm is shown in Figure 14.29.
Marker
59
computes
DF
local
(
X
) on-the-fly without needing to devote stor-
age to it. Marker
60
operates similarly for
DF
up
(
Z
). The dominator tree is