Call-graph flattening for LLVM

I just published the source code of the pilot implementation of the call-graph flattening transform (CGF) for LLVM. This is the same implementation used in my thesis.

What CGF does is basically getting rid, during compilation, of the notion of “functions”. It does this by merging all the code together and by statically managing the stack during compilation. This means, ideally, getting the same benefits of inlining (no call overhead, callsite specialization) but without code duplication. Besides, many other optimizations are possible thanks to CGF, such as inter-procedural code motion. Moreover, since CGF is practically equivalent to continuation-passing style (CPS), there are interesting possibilities for efficient non-linear control flow semantics (exception handling, coroutines, etc.)

Currently the code is not ready for general usage because there are some cases (e.g. indirect recursion) that are not detected. Also, there are some parts of LLVM, such as the register spiller and the register allocator, that choke on CGF-transformed code because of the (potentially) huge number of PHI nodes and branches. For examples and a detailed account of open problems see chapter 4 of the thesis.

I’m planning to keep working on the implementation (and submitting LLVM bug reports) until the transformation is ready to be used on real-world code. If you have any suggestions or questions about this, don’t hesitate to get in touch with me.

Be Sociable, Share!

4 comments

  1. Hi,
    I found you’re site while searching for a CPS transform for LLVM.
    It’d be really interesting reading your thesis but the link is broken…

Leave a Reply

Your email address will not be published. Required fields are marked *