|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)|
|[4 later articles]|
|From:||firstname.lastname@example.org (Henry G. Baker)|
|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.
Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.
Return to the
Search the comp.compilers archives again.