Java Reference
In-Depth Information
need to be translated, even a little extra processing at each node can represent
a significant slowdown.
One of the first instruction selection techniques based on tree rewriting was
that of Cattell [Cat80]. First, the e
ect of each instruction was described using
a register-transfer notation. Then, a code generator “discovered” appropriate
code sequences by matching instructions against IR trees. That is, the code
generator explored ways to decompose an IR tree into combinations of special
primitive trees, using backtracking if necessary. Because this process could be
very slow, a catalog of the tree patterns that were implemented was precom-
puted. At compile-time, this catalog was searched to find available instruction
sequences.
Glanville and Graham [GG78] observed that the problemof matching code
templates against an IR tree is very similar to the problem of matching pro-
ductions against a token sequence during parsing. They cleverly reformulated
the template-matching problem in context-free parsing terms. Using standard
shift-reduce parsers augmented to handle multiple template matches, instruc-
tion selection could be automated.
A limitation of the Graham-Glanville approach is that it is purely syntactic.
It simply matches, in a context-free manner, sequences of symbols. Ganapathi
and Fischer [GF85] suggested adding attributes to code templates. Attributes
allow types, sizes, and values to influence instruction selection.
The
back-end generator
(BEG) [ESL89] finds a least-cost cover of the
tree using dynamic programming techniques that are essentially identical to
Twig's. Like Twig, BEG can guard patterns with semantic predicates. A BEG
specification, in addition to having instruction patterns, includes a description
of the register set of the target machine. This specification automatically gener-
ates the register allocator. Experiments show code quality and code-generation
times to be comparable to handwritten code generators.
Fraser, Hanson, and Proebsting [FHP92] developed a code-generator gen-
erator based on naive pattern matching and dynamic programming. This
system,
iburg
, maintains the same interface as BURG. Although iburg code
generators are slower than those generated by BURG, iburg presents a simple
and e
ff
cient framework for the development of pattern-based code generators.
To produce high-quality code, it is necessary to recognize amultitude of special
cases. For example, it is clear we would like to avoid generating code for an
