10
$\begingroup$

I am working on a new backend for a programming language using LLVM IR. This language makes a distinction between basic values and pointers to nodes on the heap, and uses a copying collector for memory management. In an existing backend for this language, basic values are kept on the system stack but pointers are kept on a separate stack. This makes finding the root nodes of the active set in garbage collection trivial, as we can just traverse the separate stack without inspecting stack frames/maps. This backend thus reserves (a) the system stack pointer, (b) a separate stack pointer for the pointer stack; (c) a heap pointer to quickly allocate new nodes.

Ideally I would like to keep as close to the existing backend as possible, so that at least to start with I could reuse the existing garbage collector. This would for example be possible if I could instruct LLVM to keep an extra stack to spill ptr values to. However, I have not been able to find anything that may enable me to do this. As an alternative I have looked at LLVM's GC intrinsics. From what I understand, I could use LLVM safepoints, but this would require me to unwind the stack in a more complicated and slower manner than the current backend does. I see that there are benefits as well (e.g., two stacks and a heap makes it difficult to decide where they should be allocated; keeping pointers in stack frames makes debugging easier), but at this point they are less important. Is there no way to mimic what the current backend does?

A related point concerns memory allocation. To mimic what the current backend does, I now malloc a heap at the start of the program and keep a heap pointer in a register. I'm wondering if there is a more idiomatic way to do this in LLVM (instead of manually spelling out the increase of the heap pointer each time). For example, would it be possible to use alloca with a custom address space instead? The docs say that alloca allocates stack space, but it is not clear to me what the behavior is with a custom address space. Would it be possible to use a custom address space and use alloca for heap allocation? (This may seem like a separate question, but the idea for this comes from the safepoints document, which suggests using a separate address space for pointers that need to be visited by GC – so it may be related.)

I don't think the constraints are very exotic: (1) the need to distinguish basic values and pointers; (2) fast allocation; (3) ideally, fast unwinding of the stack. What is the most idiomatic way to accomplish this in LLVM? And, are there perhaps any toy examples around on the web to illustrate it?

An added complication is that I want to target WebAssembly in addition to x86. I can imagine that implementing a separate address space as outlined above would be doable for x86 by reserving one register for the heap pointer. But WebAssembly has no concept of registers. I think it should be possible to work around this, either by keeping the heap pointer in a global variable or by writing a transformation that turns the heap pointer into a function argument / return value. Nevertheless, please keep this in mind in your answers if possible.

$\endgroup$
3
  • 1
    $\begingroup$ Regarding your added complication: WebAssembly Garbage Collection is in Stage 5, which means it is already accepted into the spec, just hasn't been merged yet. Supported by most of the major engines (Chrome, Firefox, Safari, Node.js, Deno, Wasmtime). $\endgroup$ Commented Dec 8, 2024 at 19:59
  • $\begingroup$ @JörgWMittag Thanks! I hadn’t thought about that. I think I’d have some complications, because in this (lazy) language we often have to overwrite nodes (thunks) with nodes of other type/size (head normal forms). But I’ll definitely keep it in mind! $\endgroup$ Commented Dec 8, 2024 at 21:02
  • 1
    $\begingroup$ @JörgWMittag, GC is merged in the Wasm 3.0 draft, which can currently be found at the bottom of the Wasm spec page. $\endgroup$ Commented Dec 9, 2024 at 6:44

2 Answers 2

Reset to default
0
$\begingroup$

Leveraging the fact that many systems use lazy initialization, you can pre-allocate memory for an additional stack (let’s call it the "mirror stack") of a predetermined size (e.g., 8 MB) for each thread. You can store the mirror stack’s address in a thread-local variable. To prevent the garbage collector from scanning the entire mirror stack, you can divide it into virtual blocks and create a map of the utilized blocks. You can see a similar solution implemented in the SGCL library for C++.

$\endgroup$
1
  • $\begingroup$ This question is really about whether there are ways to specify how stacks are to be used (and specifically which values should be spilled to which stack). $\endgroup$ Commented Mar 10 at 17:59
-1
$\begingroup$ 
; Global variables
@heap_ptr = global i8* null
@ptr_stack = global [1024 x i8*] zeroinitializer
@ptr_stack_top = global i64 0

; Initialize heap
define void @init_heap(i64 %size) {
  %heap = call i8* @malloc(i64 %size)
  store i8* %heap, i8** @heap_ptr
  ret void
}

; Allocate memory
define i8* @allocate(i64 %size) {
  %ptr = load i8*, i8** @heap_ptr
  %new_ptr = getelementptr i8, i8* %ptr, i64 %size
  store i8* %new_ptr, i8** @heap_ptr
  ret i8* %ptr
}

; Push pointer onto stack
define void @push_ptr(i8* %ptr) {
  %top = load i64, i64* @ptr_stack_top
  %idx = getelementptr [1024 x i8*], [1024 x i8*]* @ptr_stack, i64 0, i64 %top
  store i8* %ptr, i8** %idx
  %new_top = add i64 %top, 1
  store i64 %new_top, i64* @ptr_stack_top
  ret void
}

; Pop pointer from stack
define i8* @pop_ptr() {
  %top = load i64, i64* @ptr_stack_top
  %new_top = sub i64 %top, 1
  store i64 %new_top, i64* @ptr_stack_top
  %idx = getelementptr [1024 x i8*], [1024 x i8*]* @ptr_stack, i64 0, i64 %new_top
  %ptr = load i8*, i8** %idx
  ret i8* %ptr
}

; Example function with safepoint
define void @example_function() gc "your-gc-strategy" {
  %ptr = alloca i8*
  call void @llvm.gcroot(i8** %ptr, i8* null)
  
  ; Safepoint
  call void @llvm.gc.safepoint()
  
  ret void
}
$\endgroup$
1
  • 7
    $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$ Commented Feb 16 at 2:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.