CPS

Hi everybody,
I'd like to try implementing a pass that transforms all functions (and function calls, returns, etc.) to CPS, so that TCO can get rid of all (or most of) the function calling overhead (because, as you probably know, the side effect of using CPS is that all function calls become tail calls).
That being said, and since I'm pretty new to LLVM, I'd like to ask a couple of things to the veterans:
1. Can you see anything really wrong with the general idea of having such a transformation?
2. Has anybody worked on something like this in the past? Are there any starting points you'd suggest I should take a look at?
3. Do you have any advice about which direction should I take?

B.R.,
Carlo Alberto Ferraris

Hi Carlo,

I haven't tried implementing CPS with llvm before, but I do know there
have been a couple conversations about it in the past. First off,
Chris Lattner wrote up about explicitly managed stack frames here:

http://www.nondot.org/sabre/LLVMNotes/ExplicitlyManagedStackFrames.txt

I'd also suggest googling around for "llvm cps" as perhaps your
questions have been answered elsewhere. I hope this helps.

Hello Carlo,

I think you might find these two papers very interesting:
http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf

http://research.microsoft.com/en-us/um/people/akenn/sml/CompilingWithContinuationsContinued.pdf

The first is Guy Steele’s classic paper Debunking the “Expensive Procedure Call” Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO.

The second paper contains a description of a CPS internal language as used by a compiler which targeted .NET intermediate language.

It contains a description of a CPS language which has much in common with the core of LLVM’s SSA form. As the paper notes, invocations of second-class continuations correspond to jumps between basic blocks. LLVM’s br i1 … corresponds to “case z of k1 k2” in the CPS language. You may also find it useful because it contains both an elegant conversion from “direct-style” lambda terms to CPS terms, as well as lists of optimizations to perform on CPS terms.

Cheers!
– Ben

CPS conversion doesn't necessarily get rid of function-calling
overhead. A tail call is indeed a jump, but constructing the closure
of the continuation is usually more expensive than constructing a
stack frame.

Having said that, it's an interesting topic. For example, CPS
conversion makes the implementation of call/cc trivial, which might
make LLVM a more attractive target for implementing functional
languages, cooperative software threading, etc. I'm sure lots of
folks would be interested in hearing more about your work.

Mark Leone