Java Reference
In-Depth Information
most recently formed containing interval. For the header 2,
ReachUnder
is
initialized at Marker
68
to
{
C
ur
I
nt
(4)
}={
4
}
, because 4 was not previously
associated with any interval.
The
ReachUnder
set is extended by the loop at Marker
69
.Anode
y
is
mapped to its containing interval
h
at Marker
70
,where
head
(
y
) changes from
⊥
2. Marker
71
then considers
predecessors of
y
, which can also reach the header by a path using a back
edge.
to
h
. In our example, this establishes
head
(4)
=
In our example, Marker
71
considers nodes 3 and 8. The mapping
C
is applied to these nodes, and
ReachUnder
includes the unmapped
nodes 3 and 8 after the loop at Marker
71
.Astheset
ReachUnder
grows,
the loop at Marker
69
considers only unmapped nodes. Thus, the loop at
Marker
69
will next choose either node 3 or node 8. If node 3 is chosen, then
head
(3)
ur
I
nt
2 is established at Marker
70
, and the loop at Marker
69
adds node
2to
ReachUnder
.
Our example now has
ReachUnder
= {
=
,withnodes2and8un-
mapped. Our example continues as loop Marker
69
considers node 8. After
mapping
Header
(8)
4
,
3
,
8
,
2
}
2,
ReachUnder
does not change because node 8's sole
predecessor is already in
ReachUnder
. Loop Marker
69
excludes the header
h
for the following reasons:
=
•
Even though node 2 belongs in the interval with header 2, we leave
head
(2)
, so that an interval's header node can represent its interval
for subsequent containment in outer intervals.
= ⊥
•
If the header
h
were processed as any other node in
ReachUnder
, then the
loop at Marker
69
would include nodes that can reach
h
by tree, chord,
or cross edges to
h
. Such nodes are not necessarily strongly connected
with
h
,and
ReachUnder
already contains the appropriate predecessors of
h
after Marker
68
.
Thus, loop Marker
69
is finished and the interval with header 2 is complete.
The algorithm continues as loop Marker
66
looks for a lower-numbered
node that receives a back edge. Such a node is found when loop Marker
66
reaches node 1. The set of nodes with back edges to node 1 is
{
4
,
8
,
6
,
9
}
.
Applying C
to these nodes allows nodes 4 and 8 to be represented by their
header node 2. At Marker
68
,
ReachUnder
is initialized to
ur
I
nt
. Eventually,
the loop at Marker
69
maps these nodes to the interval with header 1. The set
ReachUnder
is eventually expanded at Marker
71
to include nodes 5 and 10.
When the loop at Marker
66
is finished processing the header 1,
head
(
y
)
{
2
,
6
,
9
}
=
1
for
y
∈{
. The header node 1 remains unmapped.
All strongly connected regions are now identified, but nodes outside any
loop remain unmapped. The algorithm maps all such nodes into an interval
headed by the root of the flow graph at Marker
74
. Alternatively, the flow
graph could be augmented with an edge from its exit to its entry, rendering
2
,
5
,
6
,
9
,
10
}
