If you're interested by this and haven't seen it already, Marc Feeley's talk about compiling Scheme to C is really awesome, and has been posted here at least once. I think it was targeted at people new to Scheme compilers (he diverges to explain why first class continuations are useful) so it's also pretty accessible.

http://www.iro.umontreal.ca/~boucherd/mslug/meetings/2004102...

Nice writeup on their use of the Cheney Trampoline. As is always the case in such discussions, I'll mention these three fine books for Scheme implementers:

* Lisp in small pieces, by Christian Queinnec

* Compiling with continuations, by Andrew Appel

* Anatomy of Lisp, by John Allen

If you want to go further, Matt Mights papers on static analysis are excellent: http://matt.might.net/#papers

Older versions of techniques like those described in these papers were the basis of the Stalin scheme compiler by Sisskind. From Sisskind's research statement:

Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely ecient code. Stalin utilizes a large collection of static-analysis techniques. It performs a novel form of polyvariant flow analysis that uses iterated monovariant flow analysis to perform flow-directed splitting: cloning of specialized copies of procedures and per-call-site assignment of targets to such clones. It uses the results of flow analysis to perform life-time analysis, escape analysis, points-to analysis, and must-alias analysis. These analyses support a novel form of lightweight closure conversion that eliminates most closure slots, using techniques such as variable globalization and localization, compresses the static backchain, and usually eliminates most closures from programs. It also uses the above analyses to support flow-directed region-based storage management, where run-time garbage collection is replaced with static allocation and deallocation on a per-abstract-value and per-program-point basis. It also performs flow-directed lightweight CPS conversion, using extensions of the techniques pioneered with Screamer, to support extremely ecient rst-class continuations. Finally, it supports ow-directed inlining and low-level representation selection to choose the implementation (or nonimplementation) of tags, tag checking, and tag dispatching on a per-abstract-value and per-program-point basis. This eliminates most run-time tags, tag checking, tagging, tag stripping, tag dispatching, boxing, and unboxing from programs. These analyses and optimizations allow Stalin to generate extremely efficient code that outperforms all other Scheme compilers by factors ranging between two and one hundred, particularly for numerically intensive code. Stalin often generates code that outperforms handwritten c and Fortran code.

-- ftp://ftp.ecn.purdue.edu/qobi/research-statement.pdf

Although flow analysis has been extensively published about, I couldn't find much information using the results of it for the stuff he describes. Does anybody have pointers?

Most of this sounds like a _very_ big bag of hefty tricks. Closure conversion, lambda lifting, escape analysis and allocating on the stack, partial evaluation, etc.

Maybe there are more clues over at https://engineering.purdue.edu/~qobi/papers.html

Do you rank them in this order? I have "Compiling with continuations" and consider it my favorite 'compilers' book by far.

To be completely honest, I'm reading Queinnec's book at the moment, and don't know the others first hand. They're just on my reading list.

Lisp in small pieces is a fantastic book for Lisp implementers. It starts off with a simple eval and then increases in scope and complexity. It's very complete. You can see the contents in PDF here: http://assets.cambridge.org/97805215/45662/toc/9780521545662...

Allen's book is considered a definite classic, though, and has a sizeable (and perhaps, aging?) fan base.

NB. While Lisp in Small Pieces is very, very good, it's not actually complete as it doesn't cover garbage collection at all, which is a bit of a shame.

Fascinating approach. I would be interested to see benchmarks on the n-Queens solution in translated C vs hand-written C.

This is great! However, I'd love to see this for Stalin.