I’m looking at garbage collection with statepoints in LLVM, and with substantial difficulty I’ve got to a point where I have a working example, which I intend to fit the actual GC into later. This post is my attempt to help others get started on statepoints with less difficulty. It begins with a brief explanation of the problem that statepoints solve, then describes how to use statepoints in practice, and presents example code with a simulated garbage collector.
(This has nothing to do with Klipspringer but there’s no website for the project that it does belong to yet, so I’m posting it here for now, along with the other fairly general programming posts on the blog.)
Basics
Garbage collection (GC) is what a runtime does to make unused memory available for reuse. Essentially, it’s done by traversing all active objects, starting from the pointers currently held in variables, and following them to discover other pointers in the objects they point to, until all objects currently reachable in the running process have been discovered. The discovered objects can then be relocated to get rid of space between them, and all other previously allocated memory can be marked as free.
The starting point of GC is to find all pointers held in variables. Variables have two flavours:
- Globally allocated ones (not necessarily all globally accessible), each with a specific memory address in the data segment. The compiler frontend has tabs on these and can allow GC to access them, so no problem.
- Local variables dynamically allocated on the call stack. These are trickier to find, and finding them is the topic of this text.
Assuming, for simplicity, that the program is single-threaded (and therefore has one uniquely defined call stack), the garbage collector can look back into the call stack, using libunwind for instance, to find the stack frame of each function call in the chain of calls that has led to the garbage collector itself. Those are all the active stack frames in the current process state. But what in those stack frames are pointer variables? The garbage collector needs a stack map to know that.
Each function in the program has its own layout for its stack frame. There might be multiple instances on the call stack if the function was called recursively, but they’re all laid out in the same way. (This is a slight simplification, because the stack frame may vary between different scopes in the same function, but never mind, statepoints account for that.) Mostly, nobody else than the function itself needs to know the layout of its stack frame, but if the function invokes GC, or if it calls a function (that calls a function…) that may invoke GC – when the current pool of free memory runs out for example – then the garbage collector needs to know, in order to find any GC-able pointer location in the stack frame.
Some active GC-able pointers may temporarily be held in registers rather than actual named variables, but register contents are also pushed on the stack, and restored (possibly by some hardware mechanism) when the called function returns. Hence, the garbage collector can find and modify callers’ register values on the stack.
Statepoints
Enter the concept of a safepoint, or statepoint as we shall call it to harmonise with LLVM terminology. A statepoint, which is located at a function call, corresponds to a record of all locations in the current stack frame (including registers) that holds GC-able pointers. This record is associated with the statepoint location in the code, i.e., the address of the call instruction in the code segment.
The frontend should insert a statepoint at the call of any function that might invoke GC. In the LLVM IR, a GC strategy name should first be attached to any function containing one or more statepoints. The strategy name to use is statepoint-example, until you implement your own strategy (if you do). Then each call instruction associated with a statepoint needs to be replaced with GC intrinsics, but you probably don’t want to have your frontend do that directly. Instead, the frontend can just tag all GC-able pointers with addrspace(1), and we can use the rewrite-statepoints-for-gc pass to insert the intrinsics.
For example, here’s a tiny LLVM IR example consisting of the function foo, which calls functions bar and baz, ready for statepoints rewrite:
define void @foo(ptr addrspace(1) %0, ptr addrspace(1) %1) gc "statepoint-example" { call void @bar() call void @baz(ptr addrspace(1) %0, ptr addrspace(1) %1) ret void }
After rewrite-statepoints-for-gc, the function looks like this:
define void @foo(ptr addrspace(1) %0, ptr addrspace(1) %1) gc "statepoint-example" { %statepoint_token = call token (i64, i32, ptr, i32, i32, ...) @llvm.experimental.gc.statepoint.p0(i64 2882400000, i32 0, ptr elementtype(void ()) @bar, i32 0, i32 0, i32 0, i32 0) [ "gc-live"(ptr addrspace(1) %0, ptr addrspace(1) %1) ] %3 = call coldcc ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %statepoint_token, i32 0, i32 0) ; (%0, %0) %4 = call coldcc ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %statepoint_token, i32 1, i32 1) ; (%1, %1) %statepoint_token1 = call token (i64, i32, ptr, i32, i32, ...) @llvm.experimental.gc.statepoint.p0(i64 2882400000, i32 0, ptr elementtype(void (ptr addrspace(1), ptr addrspace(1))) @baz, i32 2, i32 0, ptr addrspace(1) %3, ptr addrspace(1) %4, i32 0, i32 0) [ "gc-live"(ptr addrspace(1) %3, ptr addrspace(1) %4) ] %5 = call coldcc ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %statepoint_token1, i32 0, i32 0) ; (%3, %3) %6 = call coldcc ptr addrspace(1) @llvm.experimental.gc.relocate.p1(token %statepoint_token1, i32 1, i32 1) ; (%4, %4) ret void }
You can probably see why most frontend authors prefer not to generate that directly. Note that the rewrite pass introduced new SSAs for the pointer parameters %0 and %1. After a call, the pointers may have been changed by relocation in GC, and since SSAs cannot be changed, the new SSAs %3 and %4 are set to the possibly modified values after calling bar. Then %3 and %4 are used as arguments to baz, and %5 and %6 become the new SSAs for the same variables (parameters) after return from baz.
When the code with GC intrinsics is compiled to CPU specific target code – which unfortunately doesn’t work for that many targets, but at least the major 64-bit architectures are supported – a stackmaps section is included in the object code. The AArch64 assembly code generated for my Mac from the code above begins like this:
.build_version macos, 15, 0 .section __TEXT,__text,regular,pure_instructions .globl _foo ; -- Begin function foo .p2align 2 _foo: ; @foo .cfi_startproc ; %bb.0: sub sp, sp, #32 stp x29, x30, [sp, #16] ; 16-byte Folded Spill .cfi_def_cfa_offset 32 .cfi_offset w30, -8 .cfi_offset w29, -16 stp x0, x1, [sp] bl _bar Ltmp0: ldp x0, x1, [sp] bl _baz Ltmp1: ldp x29, x30, [sp, #16] ; 16-byte Folded Reload add sp, sp, #32 ret .cfi_endproc ; -- End function .section __LLVM_STACKMAPS,__llvm_stackmaps __LLVM_StackMaps: .byte 3 .byte 0 .short 0 .long 1 .long 0 .long 2 .quad _foo .quad 32 .quad 2 .quad 2882400000 .long Ltmp0-_foo .short 0 .short 7 .byte 4 .byte 0 .short 8 .short 0
The last part (which I didn’t include in its entirety) is the stackmaps section, in stack map format. The runtime should parse this data (in its binary form) and build a lookup table that maps the code address of each statepoint to a record with information about the stack frame at that point. The garbage collector, when looking back into the call stack, can then look up the frame record for each frame it finds, and use it to access GC-able pointers on the stack.
Demonstration
I’ve put together a working example which doesn’t do any actual GC, but does demonstrate how a garbage collector can use the stack maps to locate and modify GC-able pointers. The full example code is available for download as a zip file [bug fixed August 2026], and only the most interesting and relevant parts of the code are shown below.
It’s likely that my implementation is lacking in some aspects (this is work in progress for me), and I would appreciate any comments that point out deficiencies or helps understanding!
The example has a memory management interface that consists of two functions defined in gc-simulation.c:
const char *allocate(const char *s) { return s; } void relocate() { // We’ll get to the implementation of this in a while. }
The idea is that allocate simulates allocating a GC-able string. It actually just returns the same pointer that it gets as a parameter, but we can have the caller believe that the return value is a managed pointer. The relocate function simulates the actual GC (we’ll look at the details of what it does below).
Preparing the mutator
Our example client code – the mutator in garbage collection lingo – which uses this simulated memory management, is a function called changes, which is based on this C code file called changes.c:
#include <stdio.h> #include <stdint.h> const char *allocate(const char *s); void relocate(); void changes() { const char *s1 = allocate("So the days float through my eyes"); const char *s2 = allocate("But still the days seem the same"); printf("Before:\n%s\n%s\n\n", s1, s2); relocate(); printf("After:\n%s\n%s\n", s1, s2); }
The changes function “allocates” two strings, writes them to standard output, calls relocate, and then prints the strings again. The compiler frontend should insert statepoints at function calls, but rather than building a whole frontend for that purpose, we can generate LLVM IR from changes.c with Clang and then hand-edit that. The command to generate LLVM IR is:
clang -O -S -emit-llvm changes.c
We get a file changes.ll which we can open in a text editor, insert gc "statepoint-example" and addrspace(1) in the appropriate places (let’s just leave everything else as it is), and save as changes-gc.ll. The core part, the changes function, looks like this after insertion:
define void @changes() local_unnamed_addr #0 gc "statepoint-example" { %1 = tail call ptr addrspace(1) @allocate(ptr noundef nonnull @.str) #3 %2 = tail call ptr addrspace(1) @allocate(ptr noundef nonnull @.str.1) #3 %3 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.2, ptr addrspace(1) noundef %1, ptr addrspace(1) noundef %2) tail call void @relocate() #3 %4 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.3, ptr addrspace(1) noundef %1, ptr addrspace(1) noundef %2) ret void }
My version of changes-gc.ll is included in the zip file for reference, but in case your system isn’t exactly like mine you’d better generate and edit your own version. We run the rewrite-statepoints-for-gc pass on changes-gc.ll, producing an LLVM bitcode file changes-gc-rewritten.bc, using the opt command like this:
opt -passes="rewrite-statepoints-for-gc" -o changes-gc-rewritten.bc changes-gc.ll
Loading the stack maps
Stack maps are placed in their own segment of process memory, not the data segment that contains the normal global variables. Linking together different object files that place data in the same segment makes the data in the same segment from all the object files wind up in a contiguous area of process memory when the program is loaded.
The way to read data from the stackmaps segment, consisting entirely of one stackmaps section, varies a bit between platforms. For one thing, LLVM names the segment and section differently depending on whether the object/executable format is Mach-O or ELF, and what code to write for accessing nonstandard segments also varies between platforms. In the Mach-O executable on the Mac I have on my lap, this works for accessing the stackmaps segment:
#include <mach-o/getsect.h> #include <mach-o/ldsyms.h> // ... unsigned long size; const uint8_t *data = getsectiondata(&_mh_execute_header, "__LLVM_STACKMAPS", "__llvm_stackmaps", &size);
This sets data to point to the beginning of __llvm_stackmaps, and size to the total size of the section, where stack maps are lined up according to the stack map format. In my example code, the stack map parsing is done by the load_stackmaps function in the file gc-simulation.c. The code is rather boring and I’m not putting it in this post (get it from the zip file if you want the details). What you need to know about it before reading on is just that for each frame record in the stack maps, it inserts a block of memory containing a framerec struct and a number of locrec structs into a hash table, with the statepoint memory address (the IP, also know as PC, pushed to the stack by the call), as the lookup key. The framerec and locrec structs look like this:
struct framerec { uint64_t ip; uint16_t nlocs; uint16_t padding; // Array of nloc locrec structs follows. }; struct locrec { int32_t off; uint16_t locsz; uint16_t reg; uint8_t what; };
(The order of the members in locref is a bit unintuitive for alignment reasons.) The what member of locrec corresponds to the location type, the first byte of the location data, which is a value from 1 to 5. My code just skips over locations of type 4 and 5, because they are constants. Constants have no memory location, so there’s nothing to relocate, no memory address to modify, and I don’t expect constants to be generated by my frontend. Some constants, describing flags and calling convention etc., appear with statepoint data, but as far I can see right now I have no use for them.
Furthermore, I don’t see what to do with locations of type 2, direct, because they have no memory address to modify either. I don’t think my frontend will cause any locations of this type, but the code checks if they appear and I’ll deal with it if they do and ignore it otherwise.
Consequently, the only two location types that are currently treated in a meaningful way in my code are 1, register, and 3, indirect. Both of them make use of the reg register number field, and type 3 also uses the off offset value, which is typically (always?) combined with the register number of SP (the stack pointer).
The locsz (location size) value is currently not used in my code, I’m not sure if it’s going to be needed for something. So far I’ve only seen locations of type 3 and always with location size 8.
Using the stack maps
Finally, we get to the implementation of the relocate method, which looks into the call stack, looks up the frame record for each frame found there, and uses information from the frame record to modify values on the stack. I use libunwind for reading from the stack, which is simple and appears widely available.
The core code is shown below. We loop over the stack, pick the IP from each frame and use the lookup function (not shown) to find the corresponding frame record in the hash table. (See the full file in the source zip if you are interested in the hash table implementation.) If a frame record is found, we loop over the location records attached to it and check the location type of each. If it’s type 1 (meaning register), we set the register with the given number to the relocation address (a pointer to the static string from the top of the code block), and if it’s type 3 (meaning indirect), we get the content of the register and combine it with the offset value to find the location to modify.
static char *changed = "Turn and face the strange changes"; unw_cursor_t cursor; unw_context_t uc; unw_getcontext(&uc); unw_init_local(&cursor, &uc); while (unw_step(&cursor) > 0) { unw_word_t ip; unw_get_reg(&cursor, UNW_REG_IP, &ip); struct framerec *fr = lookup(ip); if (fr == NULL) { continue; } struct locrec *lr = (struct locrec *) (fr+1); for (unsigned i = 0; i < fr->nlocs; i++) { unw_word_t regval; switch (lr[i].what) { case 1: unw_set_reg(&cursor, lr[i].reg, (uintptr_t) changed); break; case 3: unw_get_reg(&cursor, lr[i].reg, ®val); *(char **) (uintptr_t) (regval + lr[i].off) = changed; break; default: // should be impossible fprintf(stderr, "unsupported location type %u\n", lr[i].what); exit(1); } } }
Running the simulation
The full GC simulation program is built by compiling gc-simulation.c together with changes-gc-rewritten.bc, using the command:
clang -Wall -Wno-bitwise-op-parentheses -O -o gc-simulation gc-simulation.c changes-gc-rewritten.bc
The main function in gc-simulation.c calls load_stackmaps to initialize the frame record hash table. Then it calls changes, which prints the same two string pointer variables before and after calling relocate, resulting in the following output:
Before: So the days float through my eyes But still the days seem the same After: Turn and face the strange changes Turn and face the strange changes
Bugs and workarounds
Despite having been in use for at least ten years, the LLVM statepoint intrinsics retain “experimental” as part of their names, and the implementation appears quite rough and unpolished, in both documentation and operation. The LLVM bug tracker has (at the time of writing) a number of open issues relating to statepoints.
Several of the issues note that rewrite-statepoints-for-gc crashes for some inputs where alloca SSAs (pointers to local variables allocated on the stack) are used in connection with statepoint intrinsics. It’s perhaps not entirely surprising that the statepoint code appears to handle those badly: reading the documentation made me wonder how on earth the intrinsics would handle alloca constructs, and I ventured to find out by testing the rewriting pass on this function:
define void @changes() local_unnamed_addr gc "statepoint-example" { %a1 = alloca ptr, align 8, addrspace(1) %c3 = call ptr addrspace(1) @allocate(ptr noundef @.str) store ptr addrspace(1) %c3, ptr addrspace(1) %a1, align 8 call void @relocate() %p8 = load ptr addrspace(1), ptr addrspace(1) %a1, align 8 %p9 = load ptr addrspace(1), ptr addrspace(1) %a1, align 8 call i32 (ptr, ...) @printf(ptr noundef @.str.3, ptr addrspace(1) noundef %p8, ptr addrspace(1) noundef %p9) ret void }
Indeed, this makes rewrite-statepoints-for-gc crash with a stack trace and ask me to submit a bug report. (An error message would have been nicer.)
Update July 2026: I’ve realized that the alloca in the code above doesn’t make sense: it states that the allocated stack slot is in addrspace(1), not that the content of the stack slot is in addrspace(1). Correcting it makes the crash go away. However, instead of crashing, rewrite-statepoints-for-gc fails silently: it fails to relocate any pointers held in alloca-ed stack slots. Consequently, the following is still relevant.
However, when I run ordinary optimization on the code with Clang’s -O option and without the rewrite pass, the function comes out like this:
define void @changes() local_unnamed_addr gc "statepoint-example" { %c3 = tail call ptr addrspace(1) @allocate(ptr noundef nonnull @.str) tail call void @relocate() %1 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str.3, ptr addrspace(1) noundef %c3, ptr addrspace(1) noundef %c3) ret void }
The alloca is gone. (I suppose it has something to do with the mem2reg pass, but running only mem2reg isn’t enough, apparently.) Then rewrite-statepoints-for-gc can be run on that version of the code instead, which works just fine.
So it appears that it’s okay for the frontend to simplify its output by consistently using alloca for variables as long as you run optimization passes to remove unnecessary stack allocation before rewrite-statepoints-for-gc.
Conclusion
This post is essentially what I would have wanted – and frankly expected – to find when I started looking into LLVM statepoints some time ago, but I couldn’t find any comprehensible example. The official LLVM statepoint documentation leaves much to be desired, and I had to puzzle together fragments of information from various sources such as library documentation (not all directly related to LLVM), mailing list archive and other discussion fora, and one very informative other blog post.
Some details are still fuzzy to me, but at least the example works, and it would have helped me immensely to get to see such an example myself when I started exploring the topic. The basic code is, however, likely to improve as I keep developing my own frontend and runtime.
I would welcome any comments that point out errors, helps the explanation, or adds pointers to information that I have missed!