Java Reference
In-Depth Information
procedure
eliminate
C
ross
B
ack
E
dges
()
N
f
←N
f
foreach
Y
∈N
f
do
foreach
X
∈
Preds
(
Y
)
do
37
foreach
s
∈
sneaky
(
X
,
Y
)
do
E
f
←E
f
∪{
(
s
,
Y
)
}
38
end
function
{
nodes
}
return
{
s
|
s
is a sneaky ancestor of
Y
using edge (
X
,
Y
)
sneaky
(
X
,
Y
)
returns
}
end
Figure 14.20: Elimination of back and cross edges.
Suppose
Y
has multiple sneaky ancestors,
s
1
and
s
2
,where
s
1
is an ancestor
of
s
2
in the DFST. Since
s
1
can reach
Y
without involving
s
2
,node
s
2
cannot
dominate
Y
. Introducing the edge (
s
2
G
f
would be superfluous for
computing
idom
(
Y
). In processing edges to
Y
,Marker
38
in Figure 14.20 need
place only one edge in
,
Y
)into
G
f
—for the
sneakiest
ancestor of
Y
:
Definition 14.9
The
semidominator
1
of Y, denoted sdom
(
Y
)
, is the depth-first
number of the
sneakiest
DFST ancestor of Y. Because sdom
(
Y
)
is sneaky, there
must be a flow graph path from sdom
(
Y
)
to Y that avoids all of Y's ancestors
between itself and sdom
(
Y
)
.
Although a semidominator is formally defined as the depth-first number of
a node, it is often convenient to refer to the node instead of its depth-first
number. A node with depth-first number
n
can therefore be denoted as
n
,
avoiding the
vertex
(
n
) notation, when this is clear in context.
The depth-first numbering of a graph allows a more formal definition of
sdom
(
Y
):
Definition 14.10
GivennodessandY,s
Y, let P be the set of all paths in
G
f
of the form
s
→
v
1
→
v
2
→...→
v
n
→
Y
such that
∀
i
dfn
(
v
i
)
>
dfn
(
Y
)
. All such paths are sneaky, since no v
i
can be a
proper ancestor of Y. Then
sdom
(
Y
)
=
min
s
∗
→
Y
∈
P
dfn
(
s
)
1
Literally
half
-dominator, the term
semidominator
is taken from the paper describing the fast
dominance algorithm [LT79]. The use of this name becomes clearer when we compute immediate
dominators from semidominators.
