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
On 2008-04-27, at 21:29, Lane Schwartz wrote:> Hi guys,Hi Lane! This is a lot of questions. I'm not going to answer each individually, but will instead give general guidance to help you avoid the pain points…> 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.This is correct. Think of the llvm.gcroot intrinsic call as an annotation on a stack variable (an alloca). Like noalias, it doesn't generate any code itself. Rather, it instructs the code generator to keep track of the location of the variable in the stack frame. You must store your allocated pointer into this variable. Since you are using a copying collector, you must also reload the value of this variable before each use. This is to guard against the possibility that the collector has been invoked, updating the contents of the alloca. As for the compiler plugin interface, I suggest you ignore it initially and use the provided shadow-stack option for the time being. The shadow stack generates significantly suboptimal code, but will let you avoid writing some platform-specific code. Instead, simply copy the llvm_cg_walk_gcroots routine from the semispace example. Call it from your collection routine in order to visit each gcroot on the runtime stack. The shadow stack lets you find roots by automatically emitting a function prologue and an epilogue to push and pop gcroot entries on a stack as the program runs. This avoids the need to traverse the native call stack. If your language becomes sufficiently performance sensitive, you can later investigate implementing a custom Collector plugin. A few additional notes:> 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. > [...] > 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.These function names are entirely optional. Your runtime can use any names and prototypes it likes to provide this functionality. A bump- ptr allocator might easily inline part of its allocation routine.> 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; }You can just emit loads and stores directly if your read/write barriers do nothing. Also, there's nothing special about the llvm_gc_read or llvm_gc_write functions any more; they will not be called unless you call them yourself. — Gordon
On Sun, 2008-04-27 at 22:34 -0400, Gordon Henriksen wrote:> On 2008-04-27, at 21:29, Lane Schwartz wrote: > > 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; } > > You can just emit loads and stores directly if your read/write > barriers do nothing. Also, there's nothing special about the > llvm_gc_read or llvm_gc_write functions any more; they will not be > called unless you call them yourself.Gordon: Since GC strategies change as implementations mature, is there a way to go ahead and emit these calls, but then in a simple implementation indicate somewhere that they should be trivially inlined? This would allow us to debug things without imposing performance penalties on the simple implementation. Actually, I can see wanting to inline these even in barrier-oriented GC implementations... shap
On Sun, Apr 27, 2008 at 9:34 PM, Gordon Henriksen <gordonhenriksen at mac.com> wrote:> As for the compiler plugin interface, I suggest you ignore it > initially and use the provided shadow-stack option for the time being. > The shadow stack generates significantly suboptimal code, but will let > you avoid writing some platform-specific code. Instead, simply copy > the llvm_cg_walk_gcroots routine from the semispace example. Call it > from your collection routine in order to visit each gcroot on the > runtime stack. > > The shadow stack lets you find roots by automatically emitting a > function prologue and an epilogue to push and pop gcroot entries on a > stack as the program runs. This avoids the need to traverse the native > call stack. If your language becomes sufficiently performance > sensitive, you can later investigate implementing a custom Collector > plugin.OK. This is helpful in trying to understand what the Collector plugin is. So is it correct then that the Collector plugin is the GC's view into the backend? In other words, most garbage collectors have to have some knowledge of how the runtime stack is actually laid out. ShadowStack skirts around this issue by maintaining a "shadow" stack, so when the GC needs info about the runtime stack, ShadowStack instead provides info about the "shadow" stack. But most collector plugins would instead have to know about the actual layout of the runtime stack. Is that right? If so, then a Collector plugin would need to have info about every supported backend lays out the runtime stack? Thanks, Lane