Java Reference
In-Depth Information
procedure
D
eriving
G
raphs
(
G
f
)
repeat
interval
← find
G
f
)
header
←
interval
.
getHeader()
intvnodes
←
interval
.
getNodes()
I
nterval
(
foreach
(
y
,
z
)
∈E
f
|
y
∈
intvnodes
and
z
intvnodes
do
61
E
f
←
(
E
f
−{
(
y
,
z
)
}
)
∪{
(
header
,
z
)
}
E
f
←E
f
−{
(
header
,
header
)
}
62
N
f
←
(
N
f
−
intvnodes
)
∪{
header
}
63
until
nochange
end
Figure 14.31: Deriving graphs of
G
f
=
(
N
f
,E
f
,
root
).
Viewed as a relation, intervals
partition
a control flowgraph. A trivial partition
that satisfiesDefinition 14.19 places eachnode in its own interval. This achieves
the
minimum fixed point
, which is not the solution truly of interest. The
algorithms discussed here compute the
maximum fixed point
,whichplaces
as many nodes as possible into the same interval.
The interval structure of a programcan be computed by repeatedlyfinding
and eliminating intervals as shown in Figure 14.31. Each time an interval is
found, a new graph is essentially
derived
by replacing the nodes and edges
inside the interval with a single node—the interval's
header
—which serves
to summarize the eliminated nodes. Any edges from nodes within the found
interval to nodes outside that interval are replaced by an edge from the inter-
val's header at Marker
61
. If the header node has a loop to itself, then this
is eliminated at Marker
62
. Except for the header node, all of the interval's
nodes are deleted at Marker
63
. This process continues until nomore intervals
can be found. If the final derived graph is acyclic, then the graph is
reducible
as discussed in Section 14.2.2.
Definition 14.19 does not induce unique interval partitions of the graph
shown in Figure 14.32. For example,
{
2
,
3
,
4
,
5
,
8
}
could be an interval of the
graph in Figure 14.32, but so could
. Definition 14.19 can be extended
to induce unique partitions, and two such methods are considered below.
{
2
,
3
,
4
,
8
}
Cocke-Allen Method
Although there is not a unique partition of nodes that satisfies Definition 14.19,
one partition of interest is due to Cocke and Allen [All70, Coc70] and to
Hecht and Ullman [HU72]. Their method produces
maximum intervals
while
satisfying Definition 14.19.
The algorithm shown in Figure 14.33 begins with node 0 of Figure 14.32
as the first header. Marker
65
cannot find any other nodes to place in
I
(0)
