Java Reference
In-Depth Information
This section describes the program call graph
G
pc
, which is the interprocedural
counterpart of the control flow graph. In general, construction of an accurate
G
pc
can be considerablymore di
cult than construction of a control flowgraph.
In some languages, methods are dispatched
virtually
, which can make it
di
cult to decide which method is actually called. For languages with higher-
order functions or procedure variables, sophisticated data flow techniques are
required even to
approximate
the procedure call graph [GC01]. Here, we limit
our discussion to construction of
direct
procedure call graphs, which are useful
for interprocedural analysis and straightforward to compute.
Each procedure corresponds to a node of
G
pc
. An edge is placed between
nodes
P
and
Q
if
P
can invoke
Q
by its name (i.e., procedure variables are
not allowed). Any sequence of procedure invocations (without return) has a
corresponding path in this flow graph. Because a flow graph can only simulate
finite-state behavior, we cannot expect
G
pc
to model the stack-like behavior of
procedure calls.
Although the graph of Figure 14.8(b) reflects how procedures might
call
each other, returns from procedure calls at not explicitly represented. For
example, the graph does not show any transfer of control from
R
to
P
when
R
returns from a call by
P
.A
supergraph
[Mye81] could be created with an edge
from
R
and
Q
to
P
, showing the behavior of return statements. However,
such a graph cannot easily distinguish between
P
and
R
calling each other
recursively and the situation where
R
returns control to
P
.
Optimizations and data flow analyses can be formulated over control
flow graphs and procedure call graphs alike. Although the techniques for
describing and solving these problems are similar, we expect more accurate
solutions for intraprocedural problems because intraprocedural control flow
analysis is generally more accurate.
One abstraction of a flowgraph is its
depth-first spanning tree
(DFST), which is
useful for computing the dominator tree (Section 14.2.5) and interval partition
(Section 14.2.9) of a flow graph. The DFST of a flow graph contains all of the
flow graph's nodes and just enough of the flow graph's edges to constitute a
tree.
The depth-first search algorithm shown in Figure 14.9 builds the DFST of a
flow graph while computing its depth-first numbering. The algorithm accepts
aflowgraph
G
f
=
(
N
f
,E
f
)andtakes
O
(
E
f
)timeand
O
(
N
f
) space to produce
the following data structures:
