Java Reference
In-Depth Information
lw
$t1,i
sll
$t1,$t1,2
lw
$t2,a($fp)
addi
$t2,$t2,1
sw
$t2,b($t1)
Figure 13.30: Improved MIPS code for b[i]=a+1
piler. Fraser and Henry discuss a solution to the encoding problem in [FH91].
Proebsting created BURG [Pro91], a simple and e
cient tool for generating
BURS-style code generators. Using a very clean implementation and inge-
nious state-elimination techniques, least-cost code generators for a variety of
architectures can be created very e
ciently.
13.5.2
Instruction Selection Using Twig
Other code-generation systems based on tree pattern matching and dynamic
programming have been developed. They di
er primarily from BURS in
how they do tree pattern matching and in the fact that they do dynamic
programming as a compiler runs rather than when it is built.
Aho, Ganapathi, andTjiang [AGT89] created a treemanipulation language
and system called
Twig
. Given a specification of tree patterns and associated
costs, Twig generates a top-down tree automaton that will find the least-cost
cover of a subject tree. Twig uses fast top-down Ho
ff
mann-O'Donnell [HO82]
pattern matching in parallel with dynamic programming to find the least-cost
cover.
Starting at the root of possible instruction trees, paths to each of the tree's
children are traced. Whenever such a path is correctly traced, a counter is
incremented. When the counter equals the number of children a pattern tree
has, a potential match is recognized. Using costs and dynamic programming,
the least-cost cover for an entire IR tree can be found.
The costs associated with patterns in Twig are more general than those
ff
a
orded by any BURS system. Twig may compute the cost of a pattern dy-
namically, depending on semantic information available at compile-time. This
flexibility further allows Twig to abort certain matches if semantic predicates
are not satisfied. Thus, the applicability of Twig's patterns is context sensi-
tive. BURS does not have this flexibility since all costs must be fixed prior
to compilation to allow precomputation of dynamic programming decisions.
The great advantage of BURS is its speed. All possible matches are anticipated
in advance and tabulated. Twig must recognize partial matches and update
counters as instruction selection proceeds. Given the huge IR trees that often
ff
