Re: Back End Generators (Henry G. Baker)
Fri, 14 Oct 1994 15:06:36 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 (1994-10-14)
Re: Back End Generators (1994-10-16)
Re: Back End Generators (1994-10-16)
Re: Back End Generators (1994-10-21)
Re: Back End Generators (1994-10-21)
Re: Back End Generators (1994-10-21)
Re: Back End Generators (1994-10-21)
[4 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Henry G. Baker)
Keywords: code, tools
Organization: nil
References: 94-10-094
Date: Fri, 14 Oct 1994 15:06:36 GMT

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

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 for info on ftp-able papers.

Post a followup to this message

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