|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 email@example.com (1994-10-14)|
|Re: Back End Generators firstname.lastname@example.org (1994-10-16)|
|Re: Back End Generators email@example.com (1994-10-16)|
|Re: Back End Generators firstname.lastname@example.org (1994-10-21)|
|Re: Back End Generators email@example.com (1994-10-21)|
|Re: Back End Generators firstname.lastname@example.org (1994-10-21)|
|Re: Back End Generators email@example.com (1994-10-21)|
|Re: Back End Generators Peter.Damron@Eng.Sun.COM (1994-10-18)|
|[3 later articles]|
|From:||firstname.lastname@example.org (John McEnerney)|
|Organization:||The World Public Access UNIX, Brookline, MA|
|Date:||Sun, 16 Oct 1994 16:04:53 GMT|
>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
This was the Graham-Glanville algorithm; it was Glanville's PhD thesis.
I seem to have lost the original paper. The idea was to use an LR parser
to recognize substrings in a prefix representation of the IR tree, and
associate code generation actions with the parse. There have been several
follow-up papers on this. The only commercial compiler I have heard of
that used this was an old Intel cross-compiler for x86 development.
My favorite was Davidson & Fraser's "Code Selection through Object Code
Optimization". The idea was to generate simple instructions, then
optimize them into more complex instructions/addressing modes by
examining logically adjacent instructions and doing symbolic substitution
on their algebraic definitions, looking for a new instruction whose
algebraic definition has the combined effect. This approach is used in
the gcc compiler; it generates incredibly good code for CISC machines
like the 680x0.
But I've strayed too far from the original topic...
Return to the
Search the comp.compilers archives again.