Java Reference
In-Depth Information
0
1
Header
Interval
2
10
Node
Members
0
{
0
}
3
8
1
{
1
,
10
}
9
{
9
}
2
{
2
,
3
,
8
,
4
,
5
}
4
9
6
{
6
}
7
{
7
}
5
6
7
Figure 14.34: Cocke-Allen partition of Figure 14.32.
fact, nodes 0 and 7 seem to be similar, since each is outside the scope of
any iteration.
Schwartz-Sharir Method
Interval construction is typically intended to reveal the
loop structure
of a flow
graph. The intervals found by the Cocke-Allen method represent loops, but
a given interval can contain nodes that are typically thought to be outside of
the interval's loop. In Figure 14.34, node 5 is in the Cocke-Allen interval with
header 2, but that node appears to part of the outer loop (with header 1) in
Figure 14.32.
The following extension to the definition of an interval can address this
problem:
Definition 14.20
A
Schwartz-Sharir interval
with
header
xisdefinedac-
cording to Definition 14.19 along with the following constraint:
The header node x can be reached from any node in I
(
x
)
along a path
contained in I
(
x
)
.
