Retargetable, Modular Instruction Selection
Using a Machine-Independent, Type-Based Tiling
of Low-Level Intermediate Code
We present a novel variation on the standard technique of selecting
instructions by tiling an intermediate-code tree.
Typical compilers use a different set of tiles for every target machine.
By analyzing a formal model of machine-level computation, we have
developed a set of tiles that is machine-independent while
retaining the expressive power of machine code.
Using this tileset, we reduce the number of tilers required from one
per machine to one per architectural family (e.g., register architecture or
Because the tiler is the part of the instruction selector that is
most difficult to reason about,
our technique makes it possible to retarget an instruction selector with
significantly less effort than standard techniques.
Retargeting effort is further reduced by applying an earlier result
the machine-dependent implementation of our tileset automatically
from a declarative
description of instructions' semantics.
Our design has the additional benefit of enabling modular reasoning
about three aspects of code generation that are not typically
the semantics of the compiler's intermediate representation,
the semantics of the target instruction set,
and the techniques needed to generate good target code.
The paper is available as
US Letter PostScript (476K),
US Letter PDF (230K).