[LLVMdev] getting started with IR needing GC

[Lane Schwartz]

On Mon, Apr 21, 2008 at 8:13 PM, Gordon Henriksen
<gordonhenriksen at mac.com> wrote:
>
> Hi Terence,
>
>
> I think you're getting hung up on the details of the shadow stack collector.
> The shadow stack is a GC that is possible within this framework, but of
> course could be implemented without any special support. Its presence is
> more misleading than anything else. Taking a step back, the concepts are:
>
>
> llvm.gcroot instructs the code generator --> My GC needs to be able to find
> this variable on the stack at runtime.
> gc "x" instructs the code generator --> My GC will use the method "x" to
> find variables on the stack at runtime.
>
> Typically, a metadata table (similar to exception handling tables) will be
> emitted. Its structure is fundamentally map<void*,list<int>>, where the key
> is the address of a safe point in code (for instance, the address following
> a 'call' instruction), and the ints indicate the offsets of the live roots
> within the stack frame. LLVM does not define such a data structure, but the
> runtime-specific Collector subclass and the GC runtime itself must agree to
> a common format in order to interoperate.

Hi guys,

I am also trying to understand the garbage collection framework. I've
built up a tiny frontend for a very simple language, and I'd like to
try adding a simple garbage collector. I guess I'll walk through my
understanding of the required steps - I'd appreciate it if you guys
could correct where I misunderstand and help fill in the gaps.

Currently, my frontend creates a normal LLVM IR of a program. Before
adding GC, all variables are allocated by doing an alloca or malloc,
then by doing a store of the alloca to the variable.

Now let's assume I want to add a simple copying garbage collector.

I write an implementation called copycollector.c (based on
semispace.c) that implements the functions declared in GCInterface.h.

When my frontend generates LLVM IR code for a program, it should also
generate a call (early in the IR code) to llvm_gc_initialize. This
function uses the system calloc to allocate two big blocks of memory,
then stores pointers to that memory in static variables.

Since this is a simple copying collector, the functions llvm_gc_read
and llvm_gc_write won't really do much:
void *llvm_gc_read(void *ObjPtr, void **FieldPtr) { return *FieldPtr; }
void llvm_gc_write(void *V, void *ObjPtr, void **FieldPtr) { *FieldPtr = V; }

There is also a function called llvm_gc_allocate. Now, instead of
using alloca or malloc, my frontend generates a call to
llvm_gc_allocate.

Up to this point I feel pretty good about what's going on. But now
things get a bit fuzzy.

I somehow need to inform the garbage collection runtime (my
copycollector.c) about my variables - specifically about gc roots. So,
after I get new memory using llvm_gc_initialize, I think I should
generate an @llvm.gcroot intrinsic. But what do I pass it? The
@llvm.gcroot intrinsic takes an i8**, but llvm_gc_initialize returns a
void *. I don't really understand what happens when I generate an
@llvm.gcroot intrinsic. Conceptually, I'm announcing that I have a
variable that could serve as a GC root. But what exactly is happening?
And do I need to care what's happening?

Now, back to the collector runtime... When llvm_gc_collect is called,
I need to walk through the GC space, starting with the GC roots. How
do I get access to the GC roots?

Then there is the collector plugin. I guess there will be a
MyCustomCollector which inherits from Collector . I really don't
understand what this class does and why I need it. Let's say I have a
simple copying GC, and let's say I have a very simple set of types in
my language. When I store a variable in GC space, I'll store a char at
the beginning of the memory for that variable that simply indicates
the type (and I'll be able to infer the size from the type). Given
that, I assume I won't ever need use the collector metadata (in
@llvm.gcroot, llvm_cg_walk_gcroots, or via CollectorMetadata). Is that
right?

What does it mean for the plugin to compute a stack map?

When are the methods of the plugin called? Who is responsible for calling them?

When is the constructor of the plugin called?

What is the relationship between the plugin and the GC runtime?

In the GC docs, section "Tracing GC pointers from heap objects", there
is the following statement: "In addition, LLVM allows the front-end to
extract GC information in any form from a specific object pointer
(this supports situations #1 and #3)." Is there an example where this
is done? What API can I look at to see how to do this?

Thanks for all the help. I know this is a lot of questions. I'd really
like to get a basic GC up and running.

Thanks,
Lane