[LLVMdev] Garbage collection implementation

Angelos Manousaridis amanous at softlab.ece.ntua.gr
Tue Jun 23 06:29:22 PDT 2009

I am using LLVM as the last stage of a compiler in order to easily produce a
binary in native code. My compiler is implemented in Ocaml and has various
layers of languages. In the last layer prior to LLVM, I have a value which has
been converted to CPS, closure and hoisting (of functions).

I am now trying to write a garbage collector for this language. The shadow
stack is not suitable for me, because essentially there is no stack in my case!
All the function calls are tail calls and without tail recursive optimization
and stack re-use, the binary is useless.

My goal for now is to write a simple stop-the-world, semispace collector. To
cut a long story sort, I need to implement an allocation function like this:

if ( there is enough space ) {
  allocate space;
} else {
  dump all live physical registers on the stack;
  garbage collect;
  restore from stack, using the new locations;

The tricky part is the "dump all live registers". I spent quite some time
reading the documentation and have come up to two alternatives. Either
implement a new pass which reads the live variable analysis and spills all
registers to the stack at this point, or implement a new intrinsic which spills
all registers to the stack (after gc, I have to reload registers manually).

Neither of these ideas appears easy, and I am wondering if there is a simpler
way around this. To my understanding, there is neither a register map or any
sort of runtime-contract regarding the registers. Also, I need to work my way
among the LLVM optimizations which move values around registers (for instance
the fastcc convention which is essential for tail recursive optimization).

Angelos Manousaridis

More information about the llvm-dev mailing list