Garbage collection questions

Couple of questions:

1. void llvm_gc_write(void *V, void *ObjPtr, void **FieldPtr)

I haven't seen an adequate explanation of these, but I'm guessing:
  void *V: value being written to the field
  void *ObjPtr: current value of the field (ie. ObjPtr == *FieldPtr
upon entry to llvm_gc_write)
  void **FieldPtr: address of the field being written

2. The current semispace collector includes some code which says it
should be in a code-generator library. If I were to write a collector,
should I also include this code for the time being? Or will this soon
be refactored into an external interface?

3. void %llvm.gcroot(<ty>** %ptrloc, <ty2>* %metadata)

I don't see an implementation of the llvm.gcroot intrinsic in the
semispace collector, so is it implemented elsewhere? Semispace has a
function with the same signature, but it's not in the public GC
interface ( http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/runtime/GC/GCInterface.h).
Or is this simply because the llvm_cg_walk_gcroots callback hasn't
been refactored as an external interface (as per #2 above)?

That's it for now. :slight_smile:

Sandro

Couple of questions:

Ok, it's been a long while since I've worked on the GC stuff, but I'll try to help :slight_smile:

1. void llvm_gc_write(void *V, void *ObjPtr, void **FieldPtr)

I haven't seen an adequate explanation of these, but I'm guessing:
void *V: value being written to the field
void *ObjPtr: current value of the field (ie. ObjPtr == *FieldPtr
upon entry to llvm_gc_write)
void **FieldPtr: address of the field being written

Close: ObjPtr is designed to be a pointer to the head of an object. For example, to codegen:

Obj->Field = Ptr;

you'd want to compile it as:

llvm_gc_write(Ptr, Obj, &Obj->Field);

This is used by the GC if it keeps bits in the object header or other things. If the GC you plan to use doesn't need this info, you don't need to provide it obviously. :slight_smile:

2. The current semispace collector includes some code which says it
should be in a code-generator library. If I were to write a collector,
should I also include this code for the time being?

Yes, I would suggest including it.

Or will this soon be refactored into an external interface?

Right now, noone is pushing the GC interfaces forward. Contributions to help are welcome!

3. void %llvm.gcroot(<ty>** %ptrloc, <ty2>* %metadata)

I don't see an implementation of the llvm.gcroot intrinsic in the
semispace collector, so is it implemented elsewhere? Semispace has a
function with the same signature, but it's not in the public GC
interface ( http://llvm.cs.uiuc.edu/cvsweb/cvsweb.cgi/llvm/runtime/GC/GCInterface.h).
Or is this simply because the llvm_cg_walk_gcroots callback hasn't
been refactored as an external interface (as per #2 above)?

The llvm.gcroot intrinsic is turned into magic in the code generator that clients aren't supposed to know about. The public interface to this magic is the llvm_cg_walk_gcroots API function, which provides the dynamic values of the roots.

-Chris

Makes sense. A few more questions:

1. Any generic LLVM GC must be customised for a given front-end,
correct? In other words, it requires front-end information regarding
the layout of pointers within a block in order to fully trace the
reference graph. Or am I missing something? Is semispace a drop-in for
any front-end that utilizes the llvm.gc* intrinsics?

  1a. Semispace isn't actually complete/working is it? Its
llvm_gc_collect() implementation doesn't actually seem to do anything,
ie. no copying, no space switching, etc. :slight_smile:

2. Are there any GC tests available that I can use to test a GC implementation?

3. The description for llvm.gcroot
(http://llvm.cs.uiuc.edu/docs/GarbageCollection.html#roots) indicates
it's used to identify roots on the stack. A front-end can also use it
to identify global static data can it not?

Sandro

I've written a reference-counting garbage collector for LLVM, but I'm
still unclear on a few things.

The following piece of code that appears on
http://llvm.cs.uiuc.edu/docs/GarbageCollection.html is unclear:

   ;; As the pointer goes out of scope, store a null value into
   ;; it, to indicate that the value is no longer live.
   store %Object* null, %Object** %X
   ...

How exactly does this indicate X is no longer live? Is this internal
code-generator logic/magic?

The problem I'm currently unsure of, is how roots would affect
refcounts. Should the gcread/gcwrite not be used with stack refs, etc?

1. If root refs are NOT included in the count, then objects of
refcount 0 must be tracked in a list of scheduled deletions, but will
be continually deferred until the root goes out of scope (the deletion
list is filtered during a collection by the roots callback).

2. If root refs ARE included in the count, then this deferral overhead
is avoided, at the expense of more refcount increment/decrement costs
(on entry and exit from each function).

I'm wondering which would be preferable. The collector is currently
written assuming #1 is the case, as this is what the docs seemed to
imply. Shall I just post the code?

Sandro

Again, sorry for the delay. :frowning:

I've written a reference-counting garbage collector for LLVM, but I'm
still unclear on a few things.

Cool!

The following piece of code that appears on
http://llvm.cs.uiuc.edu/docs/GarbageCollection.html is unclear:

  ;; As the pointer goes out of scope, store a null value into
  ;; it, to indicate that the value is no longer live.
  store %Object* null, %Object** %X
  ...

How exactly does this indicate X is no longer live? Is this internal
code-generator logic/magic?

No, this just prevents the GC from accidentally thinking that *X is live through that pointer. The collector cannot distinguish between pointers that are out of scope from those that aren't, so this lets it consider all pointers to be in scope, without causing any "dead" pointers to mark objects.

The problem I'm currently unsure of, is how roots would affect
refcounts. Should the gcread/gcwrite not be used with stack refs, etc?

1. If root refs are NOT included in the count, then objects of
refcount 0 must be tracked in a list of scheduled deletions, but will
be continually deferred until the root goes out of scope (the deletion
list is filtered during a collection by the roots callback).

2. If root refs ARE included in the count, then this deferral overhead
is avoided, at the expense of more refcount increment/decrement costs
(on entry and exit from each function).

I'm wondering which would be preferable. The collector is currently
written assuming #1 is the case, as this is what the docs seemed to
imply. Shall I just post the code?

I would suggest doing experiments to determine which has the higher overhead. Refcounting as a whole is expensive, so you need to find a design that fits your constraints/application.

-Chris

Makes sense. A few more questions:

1. Any generic LLVM GC must be customised for a given front-end,
correct? In other words, it requires front-end information regarding
the layout of pointers within a block in order to fully trace the
reference graph. Or am I missing something?

Correct. The GC implementation and the front-end need to communicate through some descriptors that they can choose to define in any way they like.

Is semispace a drop-in for
any front-end that utilizes the llvm.gc* intrinsics?

I don't understand.

1a. Semispace isn't actually complete/working is it? Its
llvm_gc_collect() implementation doesn't actually seem to do anything,
ie. no copying, no space switching, etc. :slight_smile:

Yup, it's not done. :frowning:

2. Are there any GC tests available that I can use to test a GC implementation?

No, not really.

3. The description for llvm.gcroot
(http://llvm.cs.uiuc.edu/docs/GarbageCollection.html#roots) indicates
it's used to identify roots on the stack. A front-end can also use it
to identify global static data can it not?

This is like the first question: the GC impl and the front-end need to communicate to each other where the globals are and their types, but LLVM doesn't specify how this happens.

One way to think about what LLVM provides: it provides the ability to walk the stack, accurately collecting GC heap references out of the stack frames. These references can optionally be associated with metadata.

It's up to the front-end and runtime (GC impl) to decide how to use this basic support to communicate most effectively. Note that if, for example, a conservative collector is enough, you can just strap one to LLVM without using this functionality at all. :slight_smile:

-Chris

> How exactly does this indicate X is no longer live? Is this internal
> code-generator logic/magic?

No, this just prevents the GC from accidentally thinking that *X is live
through that pointer. The collector cannot distinguish between
pointers that are out of scope from those that aren't, so this lets it
consider all pointers to be in scope, without causing any "dead" pointers
to mark objects.

Does this mean some pointers from the roots might be null? I figured
only in-scope variables/roots would be in the llvm_gc_root_chain. Does
this list ever shorten?

I would suggest doing experiments to determine which has the higher
overhead. Refcounting as a whole is expensive, so you need to find a
design that fits your constraints/application.

I don't actually have an application at the moment; I'm just learning
about garbage collection. Reference counting seemed the most
straightforward at the time, and LLVM provided an environment free of
any superfluous distractions in which to learn and experiment with the
raw algorithms.

I've attached the lazy ref-counting collector if anyone's interested.
There are a few suggested enhancements in the source for those who
might want to extend it, such as bounds for real-time constraints, or
adding generations to reduce the overhead of filtering out the live
roots. :slight_smile:

Sandro

refcount.c (7.52 KB)

consider all pointers to be in scope, without causing any "dead" pointers
to mark objects.

Does this mean some pointers from the roots might be null?

Well sure, if they are null. e.g.:

int *X = NULL;

X would be null. Is that what you mean?

I figured
only in-scope variables/roots would be in the llvm_gc_root_chain.

That is correct, "global" roots have to be managed separately.

Does this list ever shorten?

It changes dynamically based on what functions are currently live.

I would suggest doing experiments to determine which has the higher
overhead. Refcounting as a whole is expensive, so you need to find a
design that fits your constraints/application.

I don't actually have an application at the moment; I'm just learning
about garbage collection. Reference counting seemed the most
straightforward at the time, and LLVM provided an environment free of
any superfluous distractions in which to learn and experiment with the
raw algorithms.

Ok, cool!

I've attached the lazy ref-counting collector if anyone's interested.
There are a few suggested enhancements in the source for those who
might want to extend it, such as bounds for real-time constraints, or
adding generations to reduce the overhead of filtering out the live
roots. :slight_smile:

Unfortunately, I don't have time to look at it, but I hope others will!

Thanks!

-Chris

By the way, how are you testing this? Do you have a front-end that is outputing garbage collected code? If so, it would be very cool to include it and your garbage collector with the LLVM distribution, assuming they are smallish.

Alternatively, when you get happy with your refcount'd collector and are convinced that it is working right, lemme know and we can include just it with mainline LLVM. Having a working GC implementation would be a great help to people using the LLVM GC hooks.

Thanks!

-Chris

By the way, how are you testing this? Do you have a front-end that is
outputing garbage collected code? If so, it would be very cool to include
it and your garbage collector with the LLVM distribution, assuming they
are smallish.

I'm not working on a front-end, so right now refcount.c has only been
thoroughly inspected by eye. I'd appreciate any ideas for tests I can
run, particularly ones that would also be useful for other GCs.

Alternatively, when you get happy with your refcount'd collector and are
convinced that it is working right, lemme know and we can include just it
with mainline LLVM. Having a working GC implementation would be a great
help to people using the LLVM GC hooks.

That'd be great. Perhaps we can reach this point with a sufficiently
comprehensive test suite of some sort.

Sandro

I think I was just confused with the code-generator magic that manages
the roots. It's clear now. :slight_smile:

Sandro