Java Reference
In-Depth Information
In practice, the behavior of a program is captured bymultiple flow graphs,
each of di
ering granularity, according to the expected benefits of optimiza-
tion at various levels. For example, each node of the procedure call graph is a
procedure that is itself represented by an intraprocedural control flow graph.
Theory and practice alike suggest the benefits of this organization, and a com-
piler designer must consider the expense and expected benefits of representing
program behavior at a given level.
ff
From an optimization point of view, the nodes of a control flow graph repre-
sent a
sequence
of operations. E
ciency considerations aside, a sequence could
correspond to a single machine instruction or to an entire program, because at
some level, each can be viewed as a sequence of instructions whose execution
modifies the state of a computation. However, the choice of node compo-
sition deserves careful attention, because the chosen level of representation
substantially a
ciency of analysis and optimization.
Suppose a variable x is always assigned the constant value 2 or 3 within a
program. If the behavior of the entire program is represented by a single flow
graph node, then x is not constant with respect to this level of representation.
On the other hand, if a node represents a single machine instruction, then there
are many more points at which a variable could be constant. However, such
fine granularity is ine
ff
ects the precision and e
cient for most programs. In our example, x most likely
retains the same value for a large number of instructions.
Thus, the representation level must be chosen with care: su
ciently fine
to represent useful information yet su
ciently coarse to avoid excessive re-
dundancy. Some popular approaches are as follows:
•
Programmers tend to construct procedureswhose statements accomplish
meaningful changes in program state. Thus, a common strategy is to
associate a node with each statement. Often, extra nodes are introduced
to place the flow graph in a canonical form (see Figure 14.40 on page 597).
•
Another approach especially suitable for language-independent opti-
mization is to associate a node with each statement or instruction of the
compiler's intermediate language (see Chapter 10).
•
If a given level of granularity is too fine, then instructions can be grouped
into maximal straight-line sequences, or
basic blocks
.Anodethenrep-
resents the longest sequence that is entered only at its first operation and
terminates after any operation with more than one successor. Thus, in
any trace of a program's execution, no instruction from a basic block can
appear unless all instructions of that block appear, and the instructions
of a basic block always appear in the same order.
