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
On Fri, Feb 4, 2011 at 7: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?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.
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>
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 On Sat, Feb 5, 2011 at 4: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? > > B.R., > Carlo Alberto Ferraris > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >