<br><br><div class="gmail_quote">On Fri, Feb 4, 2011 at 10:57 AM, Carlo Alberto Ferraris <span dir="ltr"><<a href="mailto:cafxx@strayorange.com">cafxx@strayorange.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Hi everybody,<br>
I'd like to try implementing a pass that transforms all functions (and<br>
function calls, returns, etc.) to CPS, so that TCO can get rid of all<br>
(or most of) the function calling overhead (because, as you probably<br>
know, the side effect of using CPS is that all function calls become<br>
tail calls).<br>
That being said, and since I'm pretty new to LLVM, I'd like to ask a<br>
couple of things to the veterans:<br>
1. Can you see anything really wrong with the general idea of having<br>
such a transformation?<br>
2. Has anybody worked on something like this in the past? Are there any<br>
starting points you'd suggest I should take a look at?<br>
3. Do you have any advice about which direction should I take?<br></blockquote><div><br></div><div>Hello Carlo,</div><div><br></div><div>I think you might find these two papers very interesting:</div><div><a href="http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf">http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf</a></div>

<div><br></div><div><a href="http://research.microsoft.com/en-us/um/people/akenn/sml/CompilingWithContinuationsContinued.pdf">http://research.microsoft.com/en-us/um/people/akenn/sml/CompilingWithContinuationsContinued.pdf</a></div>

<div><br></div><div>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.</div><div><br>

</div><div>The second paper contains a description of a CPS internal language as used by a compiler which targeted .NET intermediate language.</div><div><br></div><div>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.</div>

<div><br></div><div>Cheers!</div><div>-- Ben</div></div>