Tuesday, March 6, 2012

LLVM, CPS

I've done quite a bit of work these past two months on writing an LLVM backend.
Rather than directly translate the current design (one giant function), I'm trying to map function to function, and use llvm's support for tail calls to get arguments-in-registers to work.

This requires a 'real' CPS transform, and one that's up near the front of the chain of passes, not the last thing before the backend.

The CPS transform introduces 'continuation functions' - these are similar to normal functions, except they take a single argument.  They are targeted by SSA 'terminators' like branch, jump, etc...

A continuation function corresponds to a 'basic block' in SSA - think of the phi insn as if it took the single argument and moved it into the correct register.

If every function were a tail call, we could emit all the code as basic blocks with branches of various kinds. Sadly, some calls are not tail calls.  This requires that we render the continuation function as a real function, and that all 'jumps' to it are tail calls.

Needless to say, this is a pretty major rewrite of Irken.  I've already made three failed swipes at it, but I hope to find the time to get it working within the next few months.