Java Reference
In-Depth Information
root
root
s
s
X
X
cross
Y
T
Y
Z
(a)
(b)
Figure 14.19: Sneaky behavior from cross and back edges can be
summarized by chord edges. Node
s
reaches
Y
using (a) the
cross edge
T
→
Y
, and (b) the back edge
Z
→
Y
. A dashed
chord edge summarizes this behavior in each case. The
triangles represent depth-first spanning subtrees.
Figure 14.19 shows how sneaky behavior reaching node
Y
(using cross or
back edges) can be summarized by a suitable chord edge directly to
Y
.The
algorithmshown in Figure 14.20 visits eachnode in the flowgraph to determine
the chord edges that can stand for the sneaky behavior due to cross and back
edges.
It constructs a graph
G
f
with no back or cross edges, such that the
immediate dominators of
G
f
are the same as the immediate dominators of the
input graph
G
f
.
Although the algorithm in Figure 14.20 appears to be simple, the com-
plexity of computing
sneaky
(
X
,
Y
)atMarker
38
has not been addressed. The
e
cient algorithmgiven in Figure 14.21 is based on the following observations:
•
With respect to node
Y
, only the sneakiest of its ancestors need be re-
membered.
•
The depth-first numbering provides an e
G
f
.
In particular, considering nodes in descending order of their depth-first
numbering allows an e
cient means of computing
cient implementation.
