Re: Back End Generators

John Heron <heronj@smtplink.NGC.COM> writes:
>The other day I was reading a Henry Baker article in SIGPLAN about using
>simulated annealing as a theoretical framework for thinking about garbage
>collection. It occured to me that this technnique might be useful in auto-
>matic code generation systems. You know, the type of thing where you give
>a definitionof your intermediate code, your machine and its timing, and
>build a code generator. Might be good for generating peephole optimizers
>too. I did a real quick literature search, and didn't find anything. Is
>this my idea or is someone else to blame? It seems kind of obvious... If
>you've already tried it or know of someone who did, I'd be interested in
>their results, or if not, then I'd appreciate any reactions.


(GC + code generation in the same paragraph: perhaps Computer Science
hasn't become so specialized and fragmented after all!)


The following paper doesn't mention the phrase 'simulated annealing', but
could probably utilize this technique:


"Precise Instruction Scheduling without a Precise Machine Model". ACM
Comput. Arch. News 19,2 (Dec. 1991), 4-8. Also in my ftp directory.


>Another related question is: are there any other discrete approximations
>to optimization that might be applied. Genetic algorithms perhaps? I'm not
>totally sure what they are. I looked at a book once, and I remember saying
>to myself "This looks like AI stuff, I'm not interested." Maybe, my loss!


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.


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.


            Henry Baker
            Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.
--

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