Re: Back End Generators

hbaker@netcom.com (Henry G. Baker) writes:
> There are lots of very interesting CG techniques. One of my favorites
> is CG via _parsing_, which uses an inherently ambiguous grammar to
> recognize a parse tree, and then uses dynamic programming to pick the
> winning parses based on their execution-time costs. The code
> generation itself is via a standard Knuth attributed grammar. Very
> elegant.
>
> There's also Granville-Graham (???), whose details I don't recall, but it
> seems to try to put together pieces in interesting ways.


I believe the name is Graham-Glanville, though I may still have the
spelling of Glanville slightly wrong. I think Graham-Glanville is also
based on parsing the intermediate form.


> Finally, there's more-or-less _exhaustive search_ for the absolute
> best way to generate code for important expressions -- e.g., the inner
> loop of a compression program. I don't recall the name off the top of
> my head, but the reference is in my paper referenced above.


There is also the approach used in the PQCC project at Carnegie-Mellon. It
uses pattern matching as the basis of its code generator, but the big
innovation (IMHO) of PQCC is its all-encompassing approach to the back end.
It addresses more than just code generation, including register allocation,
constant folding, algebraic transformations, etc. in the whole framework.
(We have been using an adaptation of PQCC for about 10 years now, with
great success.)


The primary downfall of other approaches, including Graham-Glanville, have
been their limitation to code generation alone. Code generation and
register allocation, for instance, are very closely bound together. Some
approaches try to generate code first, assuming an infinite register set,
and then bind registers, spilling where necessary. Others try to allocate
registers first, and then generate code. Both approaches have difficulty
with complicated code and/or complicated architectures.
--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.csd.harris.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.