Java Reference
In-Depth Information
procedure
intervals
C
ocke
A
llen
(
G
f
)
Nodes
←G
f
call
new
H
eader
(
Entry
)
while
∃
h
∈
Headers
|
not
Processed
(
h
)
do
call
process
H
eader
(
h
)
foreach
Y
|
(
X
,
Y
)
∈E
f
and
X
∈
I
(
h
)
and
Y
∈
Nodes
do
64
call
new
H
eader
(
Y
)
procedure
(
h
)
Nodes
←
Nodes
−{
h
}
Headers
←
Headers
∪{
h
}
Processed
(
h
)
new
H
eader
←
false
end
end
procedure
process
H
eader
(
h
)
Processed
(
h
)
←
true
while
∃
Y
∈
Nodes
|
Y
Entry
and
∀
(
X
,
Y
)
∈E
f
X
∈
I
(
h
)
do
65
I
(
h
)
∪
Y
Nodes
←
Nodes
−{
Y
}
←
I
(
h
)
end
Figure 14.33: Cocke-Allen interval construction.
(the interval with header 0). Such nodes must have all of their predecessors
in
I
(0). For example, node 1 receives several edges from nodes outside of
I
(0),
so it cannot join
I
(0). After Marker
64
makes a header out of node 1, then
its interval can include node 10, but not node 2. The interval
I
(2) grows to
include nodes 3 and 8. After both of those nodes join
I
(2), node 4 can join as
well. Node 5's only predecessor is now in
I
(2), so node 5 also joins
I
(2). Node 6
cannot join
I
(2) because of its edge from node 9, which is not in
I
(2).
The complete interval partition is shown in Figure 14.34. This style of
interval partitioning has the following disadvantages:
•
The algorithm results in a sequence of derived graphs in which a given
node may repeatedly appear. For example, nodes belonging to the out-
ermost interval appear in every graph of the sequence.
•
Because Cocke-Allen intervals are not strongly connected, an interval can
contain nodes that are usually considered outside a loop. For example,
node 5 in Figure 14.32 is an exit node from the loop comprising nodes 2,
3, 8, and 4. However, node 5 belongs to the Cocke-Allen interval
I
(2).
•
Some Cocke-Allen intervals may not correspond to loops at all. In Fig-
ure 14.32, node 7 is its own interval, but no iteration involves node 7. In
