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.