Java Reference
In-Depth Information
procedure
simple
D
ominance
F
rontiers
(
G f , dom )
DomBy ( X )
←{ Z | X dom ( Z )
}
56
foreach X ∈N f do
57
foreach Y DomBy ( X ) do
foreach Z Succ ( Y ) do
if Z DomBy ( X )
58
−{ X }
then DF ( X )
DF ( X )
∪{ Z }
end
Figure 14.28: Simple dominance frontiers algorithm.
Consider the dominance frontiers of nodes 3, 9, and 10, as shown in the
following table:
Node Nodes dominated
DF ( X )
X
by X
3
{
3
,
9
,
10
}
{
4
,
8
,
6
}
9
{
9
,
10
}
{
8
,
6
}
10
{
10
}
{
6
}
The second column shows nodes that fall in the shadow of X when X is
opaque, and the third column shows the dominance frontier of X , which can
be computed by inspection or by the above definition. The dominance frontier
of node 3 contains node 4, along with the dominance frontiers computed for
nodes 9 and 10. Notice the relationship between nodes 3, 9, and 10 in the
dominator tree shown in Figure 14.27. If we express the dominance frontier
for node X in terms of its children in the dominator tree, then a single pass
over the tree su
ces to compute the dominance frontiers of all nodes. We
therefore express the dominance frontier of a given node as the contribution
of two intermediate sets, DF local and DF up , as follows:
Equation 14.16
Z | X = idom ( Z ) DF up ( Z )
DF ( X )
= DF local ( X )
def
= { Y Succ ( X )
DF local ( X )
| X Y }
def
= { Y DF ( Z )
DF up ( Z )
| idom ( Z )
Y }
The local contribution comes from successors of X not strictly dominated by
X . In our example, node 4 is in DF local (3). The up contribution comes from the
dominance frontiers of nodes that are immediately dominated by X .Inour
example, nodes 6 and 8 are passed from node 9 to its immediate dominator,
node 3.
 
Search WWH ::




Custom Search