Java Reference
In-Depth Information
Unfortunately, the passes of a compiler can interact in subtle ways. For
example,
code motion
can rearrange a program's computations to make better
use of a given architecture. However, as the distance between a variable's
definition and its uses increases, so does the pressure on the
register allocator
.
Thus, it is often the case that a compiler's optimizations are somewhat at
odds with each other. Ideally, the passes of an optimizing compiler should
be fairly independent, so that they can be reordered and retried as situations
require [CGH
+
05].
This section describes structures that represent a program's flow of control.
A flow graph is essentially a finite-state automaton whose nodes represent
various locations in a program and whose edges indicate possible transition
among these locations. As a system of highways interconnects cities on a map,
so do flow graphs serve as a roadmap for optimization. The nodes of a flow
graph represent sites where optimization information can be generated or con-
sumed; the graph's edges are conduits for combining and further propagating
such information.
Definition 14.1
A
flow graph
N,E,
root
)
is a directed graph:
N
is a set
(of nodes) and
E
is a binary relation on
N
. The root node is the distinguished
entry node of the flow graph:
∀
X
∈N,
G=
(
(
X
,
root
)
E
.
Although flow graphs are quite general, we are concerned with representing
the following levels of program behavior:
•
A
control flow graph
G
cf
represents potential execution paths within
a procedure. Generally, each node in
N
cf
corresponds to a
straight-line
sequence of operations; each edge in
E
cf
represents potential transfer
of execution from the end of one sequence to the beginning of another.
Control flow graphs are used in
intraprocedural analyses
.
•
A
procedure call graph
G
pc
represents potential execution paths between
the procedures of a program. Each node in
N
pc
corresponds to a proce-
dure of the program; each edge in
E
pc
represents a potential procedure
call. Procedure call graphs are used in
interprocedural analyses
.
The diversity of programming constructs such as loops, alternate entry points,
procedure exits, recursion, and arbitrary goto statements could conceivably
yield flow graphs of no discernible structure. However, trends in program-
ming languages and software development practices tend to yield programs
whose structure is relatively clear and whose flow graphs enjoy properties
conducive to e
cient analysis.
