Accurate Garbage Collection with LLVM
  1. Introduction
  2. Interfaces for user programs
  3. Implementing a garbage collector
  4. GC implementations available

Written by Chris Lattner


Garbage collection is a widely used technique that frees the programmer from having to know the life-times of heap objects, making software easier to produce and maintain. Many programming languages rely on garbage collection for automatic memory management. There are two primary forms of garbage collection: conservative and accurate.






GC features provided and algorithms supported

LLVM provides support for a broad class of garbage collection algorithms, including compacting semi-space collectors, mark-sweep collectors, generational collectors, and even reference counting implementations. It includes support for read and write barriers, and associating meta-data with stack objects (used for tagless garbage collection). All LLVM code generators support garbage collection, including the C backend.

We hope that the primitive support built into LLVM is sufficient to support a broad class of garbage collected languages, including Scheme, ML, scripting languages, Java, C#, etc. That said, the implemented garbage collectors may need to be extended to support language-specific features such as finalization, weak references, or other features. As these needs are identified and implemented, they should be added to this specification.

LLVM does not currently support garbage collection of multi-threaded programs or GC-safe points other than function calls, but these will be added in the future as there is interest.

Interfaces for user programs

This section describes the interfaces provided by LLVM and by the garbage collector run-time that should be used by user programs. As such, this is the interface that front-end authors should generate code for.

Identifying GC roots on the stack: llvm.gcroot
void %llvm.gcroot(<ty>** %ptrloc, <ty2>* %metadata)

The llvm.gcroot intrinsic is used to inform LLVM of a pointer variable on the stack. The first argument contains the address of the variable on the stack, and the second contains a pointer to metadata that should be associated with the pointer (which must be a constant or global value address). At runtime, the llvm.gcroot intrinsic stores a null pointer into the specified location to initialize the pointer.

Consider the following fragment of Java code:



   ;; In the entry block for the function, allocate the
   %X = alloca %Object*

   ;; "CodeBlock" is the block corresponding to the start
   ;;  of the scope above.
   ;; Initialize the object, telling LLVM that it is now live.
   ;; Java has type-tags on objects, so it doesn't need any
   ;; metadata.
   call void %llvm.gcroot(%Object** %X, sbyte* null)

   store %Object* null, %Object** %X
Allocating memory from the GC
sbyte *%llvm_gc_allocate(unsigned %Size)


Reading and writing references to the heap
sbyte *%llvm.gcread(sbyte *, sbyte **)
void %llvm.gcwrite(sbyte*, sbyte*, sbyte**)

Several of the more interesting garbage collectors (e.g., generational collectors) need to be informed when the mutator (the program that needs garbage collection) reads or writes object references into the heap. In the case of a generational collector, it needs to keep track of which "old" generation objects have references stored into them. The amount of code that typically needs to be executed is usually quite small (and not on the critical path of any computation), so the overall performance impact of the inserted code is tolerable.

To support garbage collectors that use read or write barriers, LLVM provides the llvm.gcread and llvm.gcwrite intrinsics. The first intrinsic has exactly the same semantics as a non-volatile LLVM load and the second has the same semantics as a non-volatile LLVM store, with the additions that they also take a pointer to the start of the memory object as an argument. At code generation time, these intrinsics are replaced with calls into the garbage collector (llvm_gc_read and llvm_gc_write respectively), which are then inlined into the code.

If you are writing a front-end for a garbage collected language, every load or store of a reference from or to the heap should use these intrinsics instead of normal LLVM loads/stores.

Garbage collector startup and initialization
void %llvm_gc_initialize(unsigned %InitialHeapSize)

The llvm_gc_initialize function should be called once before any other garbage collection functions are called. This gives the garbage collector the chance to initialize itself and allocate the heap spaces. The initial heap size to allocate should be specified as an argument.

Explicit invocation of the garbage collector
void %llvm_gc_collect()


Implementing a garbage collector

Implementing a garbage collector for LLVM is fairly straight-forward. The LLVM garbage collectors are provided in a form that makes them easy to link into the language-specific runtime that a language front-end would use. They require functionality from the language-specific runtime to get information about where pointers are located in heap objects.

The implementation must include the llvm_gc_allocate and llvm_gc_collect functions, and it must implement the read/write barrier functions as well. To do this, it will probably have to trace through the roots from the stack and understand the GC descriptors for heap objects. Luckily, there are some example implementations available.

Implementing llvm_gc_read and llvm_gc_write
void *llvm_gc_read(void*, void **)
void llvm_gc_write(void*, void *, void**)

These functions must be implemented in every garbage collector, even if they do not need read/write barriers. In this case, just load or store the pointer, then return.

If an actual read or write barrier is needed, it should be straight-forward to implement it.

Callback functions used to implement the garbage collector

Garbage collector implementations make use of call-back functions that are implemented by other parts of the LLVM system.

Tracing GC pointers from the program stack


Tracing GC pointers from static roots
Tracing GC pointers from heap objects




Making this efficient

GC implementations available

To make this more concrete, the currently implemented LLVM garbage collectors all live in the llvm/runtime/GC/* directories in the LLVM source-base. If you are interested in implementing an algorithm, there are many interesting possibilities (mark/sweep, a generational collector, a reference counting collector, etc), or you could choose to improve one of the existing algorithms.

SemiSpace - A simple copying garbage collector


Possible Improvements

If a collection cycle happens and the heap is not compacted very much (say less than 25% of the allocated memory was freed), the memory regions should be doubled in size.





Valid CSS! Valid HTML 4.01! Chris Lattner
LLVM Compiler Infrastructure