llvm dev - Mar 2011 - [LLVMdev] A working garbage collector - finally :)

Well, after many months of effort, my LLVM-based garbage collector is
finally passing its unit tests. This represents a significant milestone for
me in the development of my programming language, Tart.

The collector itself is fairly rudimentary - a single-generation, copying
collector. It does not yet support multi-threaded programs, but in practice
there's no serious obstacle to supporting threading due to the fact that the
collector does not need any mutable global variables.

The stack tracer is based on the paper I posted a few months back, which I
have now transferred over to the LLVM wiki. It's meant to be a practical
introduction to the task of building a garbage collector in LLVM:

    http://wiki.llvm.org/Building_a_stack_crawler_in_LLVM

Here's a sample of one of the unit tests. It's checking that the tracer
can
properly distinguish between two states of a union, one state having a
traceable object (a String), and the other state containing a non-traceable
value (a float):

  def testCollectUnionLocalVar {
    var u:String or float = newString("Hello");
    tart.gc.GC.collect();
    assertTrue(u isa String);
    assertEq("Hello", typecast[String](u));
    u = 1.0;
    tart.gc.GC.collect();
    assertFalse(u isa String);
  }

The heart of the collector is the TraceAction class - which is invoked for
each pointer reference. The tracer for the Tart language is written, of
course, in Tart, although the style is not the normal Tart style due to the
need to deal with low-level objects such as addresses and pointers:

  private final class TraceActionImpl : TraceAction {
    protected def tracePointer(ptrAddr:Address[Object]) {
      let addr:Address[ubyte] = Memory.bitCast(ptrAddr[0]);
      if fromSpace.contains(addr) {
        let header:Address[ObjectHeader] = Memory.bitCast(addr);
        // A gcstate of 0 means that 'header' is the head of a
statically
        // allocated object instance, in which case we need not do
        // anything since it will be traced as a static root.
        if (header.gcstate != 0) {
          if (header.gcstate & uint(GCFlags.RELOCATED)) != 0 {
            ptrAddr[0] = header.newLocation;
          } else {
            let size = header.gcstate & uint(~3);
            let newAddr:Address[ubyte] = toSpace.alloc(size);
            Memory.arrayCopy(newAddr, addr, size);
            header.newLocation = ptrAddr[0] = Memory.bitCast(newAddr);
            header.gcstate = uint(GCFlags.RELOCATED);
          }
        }
      }
    }
  }

  /** Static instance of the trace action. */
  let TRACE_ACTION = TraceActionImpl();

The collect function simply invokes the trace action on the stack roots, the
static roots, and the surviving members in the to-space:

  @LinkageName("GC_collect") def collect() {
    // Swap the spaces.
    toSpace, fromSpace = fromSpace, toSpace;
    toSpace.pos = toSpace.begin;

    // Trace static roots and runtime stack
    GCRuntimeSupport.traceStack(TRACE_ACTION);
    GCRuntimeSupport.traceStaticRoots(TRACE_ACTION);

    // Trace all remaining live objects.
    var tracePos = toSpace.begin;
    while (tracePos < toSpace.pos) {
      let header:Address[ObjectHeader] = Memory.bitCast(tracePos);
      let obj:Object = Memory.bitCast[Address[ubyte], Object](tracePos);
      let length = header.gcstate;
      TRACE_ACTION.traceObject(obj);
      tracePos += length;
    }
  }

If you are curious about the Tart language ("Tart is to C++ as Python is to
Perl") you can check it out at http://tart.googlecode.com or join the
tart-dev mailing list on Google groups.

-- Talin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110220/24e90bd8/attachment.html>

Since you are using a copying collector, may I ask how do you handle 
registers holding pointers to intermediate values?

The example I am considering is something like

void foo(void);
void f(long long *v, long long n) {
   long long int i;
   for (i = 0; i < n; ++i) {
     v[i] = i;
     foo();
   }
}

If *v points to gc memory, we can start the function with

%v.addr = alloca i64*, align 8
%foobar = bitcast i64** %v.addr to i8**
call void @llvm.gcroot(i8** %foobar, i8* null)
store i64* %v, i64** %v.addr, align 8

but nothing prevents llvm from putting the call to foo in between the 
computation of &v[i] and the store by using a callee saved register. If 
GC moves moves v during the call to foo, the next store will be wrong.
> -- Talin
>
Cheers,
Rafael

Where's the problem?  A pointer to v's alloca escapes to llvm.gcroot,
so the optimizers should know that foo could modify the value it
holds.  foo() might also read v[i] through the escaped pointer, so the
store will have to happen before the call.

Reid

2011/3/8 Rafael Ávila de Espíndola <rafael.espindola at
gmail.com>:
> Since you are using a copying collector, may I ask how do you handle
> registers holding pointers to intermediate values?
>
> The example I am considering is something like
>
> void foo(void);
> void f(long long *v, long long n) {
>   long long int i;
>   for (i = 0; i < n; ++i) {
>     v[i] = i;
>     foo();
>   }
> }
>
> If *v points to gc memory, we can start the function with
>
> %v.addr = alloca i64*, align 8
> %foobar = bitcast i64** %v.addr to i8**
> call void @llvm.gcroot(i8** %foobar, i8* null)
> store i64* %v, i64** %v.addr, align 8
>
> but nothing prevents llvm from putting the call to foo in between the
> computation of &v[i] and the store by using a callee saved register. If
> GC moves moves v during the call to foo, the next store will be wrong.
>
>> -- Talin
>>
>
> Cheers,
> Rafael
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>