Java Reference
In-Depth Information
27. Machines like the MIPS and Sparc have
delayed branch instructions
.
That is, the instruction immediately following a branch is executed
prior
to transferring control to the target of the branch.
Often, compilers simply generate a nop instruction after a branch, ef-
fectively hiding the e
ects of the delayed branch. Suggest a peephole
optimization pattern for unconditional branches followed by a nop that
swaps the instruction prior to the branch into the “delay slot” that fol-
lows it. Can this optimization always be done, or must some conditions
be met to make the swap valid?
Nowconsider a delayed
conditional
branch inwhich the value of a register
is tested. If the condition is met, the instruction following the conditional
branch is executed, and then the branch is taken. Otherwise, instructions
following the conditional branch are executed (as usual); no branch is
taken. Suggest a peephole optimization pattern that allows the instruc-
tion preceding a conditional branch to be moved after it as long as the
swapped instruction does not a
ff
ff
ect the register tested by the conditional
branch.
28. Many architectures include a
load-negative
instruction that loads the nega-
tion of a value into a register. That is, the value, while being loaded, is
subtracted from zero, with the di
erence stored into the register. Suggest
two instruction-level peephole optimization patterns that can make use
of a load-negative instruction.
ff
29. After a peephole optimization is performed, the optimized instruction
that is substituted for the original instructions is reconsidered for further
peephole optimizations. Give at least three examples of cases in which
peephole optimizations may be profitably cascaded.
30. Assume we have a peephole optimizer that has
n
replacement patterns.
The most obvious approach to implementing such an optimizer is to try
each pattern in turn, leading to an optimizer whose speed is proportional
to
n
.
Suggest an alternative implementation, based on hashing, that is largely
independent of
n
. That is, the number of patterns considered may be
doubled without automatically doubling the optimizer's execution time.
31. The
Sethi-Ullman numbering
algorithm presented in Section 13.2 as-
sumed that all expression tree nodes are
binary
. Develop a generalization
of the Sethi-Ullman numbering algorithm given in Figure 13.9 that can
be applied to trees whose nodes have an arbitrary number of children.
