Java Reference
In-Depth Information
addition of zero to an operand. But where should we check for this special
case? In each translation routine that might generate an add? In each code-
generation routine that might emit an add instruction?
Rather than distribute knowledge of special cases throughout transla-
tion and code-generation routines, it is often preferable to utilize a distinct
peephole optimization phase that looks for special cases and replaces them
with improved code.
Peephole optimization
may be performed on ASTs,
IR trees [TvSS82] or generated code [McK65]. As the term “peephole” sug-
gests, a small window of two or three instructions or nodes is examined. If
the instructions in the peephole match a particular pattern, they are replaced
with a replacement sequence. After replacement, the new instructions are
reconsidered for further optimization.
In general, we represent the collection of special cases that define a peep-
hole optimizer as a list of pattern-replacement pairs. Thus,
pattern
=⇒
replacement
means that if an instruction sequence or tree matching the pattern is seen, it
is replaced with the replacement sequence. If no pattern applies, the code
sequence remains unchanged. Clearly, the number of special cases that might
be included is unlimited. We will illustrate where peephole optimization can
be employed and the kinds of optimizations that can be realized.
In general there are three places where peephole optimization may be prof-
itably employed. After parsing and type checking, a program is represented
in AST form. Here, peephole optimization may be used to optimize the AST,
recognizing special cases at the source level that are independent of how a
construct is translated, or the code that is generated for it.
After translation, a programis represented in an IRor bytecode form. Here,
peephole optimization can recognize optimizations that simplify or restructure
an IR tree or bytecode sequence. These optimizations are independent of the
actual target machine or the exact code sequences used to implement an IR
tree or bytecodes.
Finally, after code generation, peephole optimization can replace pairs
or triples of target machine instructions with shorter or simpler instruction
sequences. At this level, the optimization is highly dependent on the details
of a machine's instruction set.
AST-Level Optimizations
In Figure 13.31 we illustrate optimizations that can simplify or improve an
AST representation of a program.
In (a), an if statement whose condition
