Java Reference
In-Depth Information
and 11. The bytecodes may be interpreted by a bytecode interpreter. Alterna-
tively, we may wish to further the translation process and produce machine
instructions native to a particular computer of interest.
The first problem we will face is
instruction selection
. Instruction se-
lection is highly target-machine dependent; it involves choosing a particular
instruction sequence to realize a portion of the intermediate representation.
Even for one simple bytecode instruction we may have a choice of possible
implementations. For example, the iinc instruction, which adds a constant to
a local variable, might be implemented by loading the variable into a register,
loading the constant into a second register, doing a register-to-register add,
and storing the result back into the variable. Alternatively, we might choose
to keep the variable in a register, allowing implementation using only a single
add-immediate instruction.
Besides instruction selection, we must also deal with
register allocation
and
code scheduling
. Register allocation aims to use registers e
ectively by
minimizing register spilling (storing a value held in a register and reloading
the register with something else). Because memory transactions take con-
siderably more time than arithmetic instructions on most processors, even a
few unnecessary loads and stores can significantly reduce the speed of an in-
struction sequence. Code scheduling is concerned with the order in which
generated instructions are executed. Not all valid instruction orderings are
equally good—some incur unnecessary delays.
We shall first consider how bytecodes may be e
ff
ciently translated to
machine-level instructions. Techniques that optimize the code we generate
will be considered next, particularly the translation of expressions in tree
forms. A variety of techniques that support e
cient use of registers, especially
graph coloring will be discussed. Approaches to code scheduling will next
be studied. Techniques that allow us to easily and automatically retarget a
code generator to a new computer will then be discussed. Finally, a form of
optimization that is particularly useful at the code-generation level, peephole
optimization, will be studied.
We will first consider how to translate the bytecodes produced by the tech-
niques discussed in Chapter 11 into conventional machine code. Each com-
puter architecture has its own machine instruction set. Examples include the
Intel x86 architecture, the Sparc, the Alpha, the PowerPC, and the MIPS.
In this chapter we use the MIPS R3000 instruction set. This architecture is
clean, easy to use, and a good representative of modern
reduced instruction
set computer
(RISC) architectures. The MIPS R3000 is also supported by
SPIM [Lar90], a widely available MIPS interpreter written in C.
