Java Reference
In-Depth Information
Definition 14.19 requires that all nodes in
I
(
h
) are reachable from the header
node
h
by paths contained in
I
(
h
). The additional constraint in Definition 14.20
makes the nodes of an interval
strongly connected
. All nodes in an interval
can reach each other without including any nodes outside the interval. For
example, the Schwartz-Sharir interval with header 2 in Figure 14.32 excludes
node 5, which is instead placed in the interval with header 1.
The algorithm in Figure 14.35 is taken from Schwartz and Sharir [SS78,
SS79], which in turn is based on an algorithm by Tarjan [Tar72]. Irreducible
graphs are detected in Figure 14.35 at Marker
73
. Exercises 23 and 24 explore
approaches for dealing with irreducible flow graphs (see Figure 14.8(b)). The
algorithm's e
ciency is obtained as follows:
•
Nodes are considered in a “clever” order. In comparison to the algorithm
in Figure 14.33, this fast algorithm considers nodes in the
reverse order
of their depth-first numbering, discovering inner intervals before outer
ones.
•
Throughout its analysis, the algorithm maintains
path-compressed
in-
formation to evaluate C
ur
I
nt
(
X
): the interval
currently associated
with
node
X
. Initially, C
ur
I
nt
(
X
) returns its input node
X
. As the algorithm
proceeds, C
(
X
) continues to return the header node of the most
recently formed interval that includes, directly or indirectly, the node
X
.
ur
I
nt
As an example, consider how the evaluation of C
( 3 ) changes as loops
are discovered from innermost to outermost. Node 3 initially participates in
no interval, so C
ur
I
nt
( 3 ) returns 3. Node 3 subsequently joins the innermost
interval with header 2; at that point, C
ur
I
nt
2. This interval will eventu-
ally be incorporated into the outermost interval with header 1, at which time
C
ur
I
nt
(3)
=
1.
We next apply the algorithm in Figure 14.35 to the flow graph shown in
Figure 14.32, with the results shown inFigure 14.36. Note that eachvertex of the
flowgraph is already labeledwith its depth-first number. Marker
66
considers
the flow graph nodes in reverse order of their depth-first numbering, so that
headers of inner loops are processed before headers of outer loops. Marker
68
determines if node
h
can be the header of an interval by looking for
back edges
to node
h
, applying the constant-time test described in Section 14.2.4. A back
edge to
h
originates at some node
l
in the depth-first spanning subtree rooted
at
h
.Thus,
h
and
l
are in a strongly-connected interval with header
h
.Node2
is the first header so identified in Figure 14.32, as shown in Figure 14.36.
The set
ReachUnder
contains those nodes that can reach the header
h
by
paths ending with a back edge to
h
. Intuitively, such nodes belong in a loop
with single-entry
h
. The set is initialized at Marker
68
to contain the source
of any back edge. Instead of adding a node
v
directly to
ReachUnder
,the
algorithm consistently adds C
ur
I
nt
(3)
=
ur
I
nt
(
v
), so that a node
v
is represented by its
