[LLVMdev] CPS

[Ben Karel]

On Fri, Feb 4, 2011 at 10:57 AM, Carlo Alberto Ferraris <
cafxx at strayorange.com> wrote:

> 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?
>

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110205/881142dd/attachment.html>