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
 
Search WWH ::




Custom Search