Re: Back End Generators

bill@amber.ssd.csd.harris.com (Bill Leonard)
Fri, 21 Oct 1994 02:43:10 GMT

          From comp.compilers

Related articles
Back End Generators heronj@smtplink.NGC.COM (John Heron) (1994-10-12)
Re: Back End Generators heronj@smtplink.NGC.COM (John Heron) (1994-10-12)
Re: Back End Generators hbaker@netcom.com (1994-10-14)
Re: Back End Generators johnmce@world.std.com (1994-10-16)
Re: Back End Generators adrian@platon.cs.rhbnc.ac.uk (1994-10-16)
Re: Back End Generators chase@centerline.com (1994-10-21)
Re: Back End Generators pardo@cs.washington.edu (1994-10-21)
Re: Back End Generators bill@amber.ssd.csd.harris.com (1994-10-21)
Re: Back End Generators smucker@cs.wisc.edu (1994-10-21)
Re: Back End Generators Peter.Damron@Eng.Sun.COM (1994-10-18)
Re: Back End Generators hbaker@netcom.com (1994-10-28)
Re: Back End Generators anton@mips.complang.tuwien.ac.at (1994-10-24)
Re: Back End Generators davidm@Rational.COM (1994-10-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: bill@amber.ssd.csd.harris.com (Bill Leonard)
Keywords: code, tools
Organization: Harris Computer Systems, Ft. Lauderdale FL
References: 94-10-094 94-10-112
Date: Fri, 21 Oct 1994 02:43:10 GMT

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
--


Post a followup to this message

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