Java Reference
In-Depth Information
bneq $reg,$0,L2
beq $reg,$0,L1
⇒
⇒
b L1
L1:
b L2
L1:
L1:
L1:
(a)
(b)
⇒
b L1
b L2
L1:
b L2
L1:
b L2
move $reg,$reg
⇒
(nothing)
(d)
(c)
sw $reg,loc
sw $reg,loc
⇒
lw $reg,loc
(e)
Figure 13.34: Code-Level Peephole Optimizations
register and conditionally branches if it is zero.
Recognizing replacement patterns must be done quickly if peephole opti-
mization is to be fast. Operator-operand combinations are hashed to applicable
patterns. Also, the size of a peephole window is normally limited to two or
three instructions. Using a carefully hashed implementation, speeds of several
thousand instructions per second have been achieved [DF84].
The concept of analyzing physically adjacent instructions has been gener-
alized to
logically adjacent instructions
[DF82]. Two instructions are logically
adjacent if they are linked by flow of control or if they are una
ected by inter-
vening instructions. (The “branch chain” of Figure 13.34 (c) is a good example
of this.) By analyzing logically adjacent instructions it is possible to remove
jump chains (jumps to jump instructions) and redundant computations (for
example, unnecessarily setting a condition code). Detecting logical adjacency
can be costly, so care is required to keep peephole optimization fast.
ff
In [DF80], ways of automating the creation of peephole optimizers are dis-
cussed. The idea is to define the e
ect of target machine instructions at the
register-transfer level
(RTL). At this level, instructions are seen to modify
primitive hardware locations, including memory (represented as a vector
M
),
registers (represented as a vector
R
), the
PC
(program counter), various condi-
tion codes, and so on. A target machine instruction may have more than one
e
ff
ect and its definition at the RTL may include more than one assignment.
The peephole optimizer (PO) operates by considering pairs of instructions,
expanding them to their RTL definitions, simplifying the combined definitions,
ff
