[LLVMdev] Interfacing llvm with a precise, relocating GC

[Philip Reames]

On 10/25/13 1:10 PM, Ben Karel wrote:
>
>
>
> On Thu, Oct 24, 2013 at 6:42 PM, Sanjoy Das <sanjoy at azulsystems.com 
> <mailto:sanjoy at azulsystems.com>> wrote:
>
>     Hi Rafael, Andrew,
>
>     Thank you for the prompt reply.
>
>     One approach we've been considering involves representing the
>     constraint "pointers to heap objects are invalidated at every
>     safepoint" somehow in the IR itself.  So, if %a and %b are values the
>     GC is interested in, the safepoint at the back-edge of a loop might
>     look like:
>
>       ; <label>: body
>         %a = phi i32 [ %a.relocated, %body ] [ %a.initial_value, %pred ]
>         %b = phi i32 [ %b.relocated, %body ] [ %b.initial_value, %pred ]
>         ;; Use %a and %b
>
>         ;; The safepoint starts here
>         %a.relocated = @llvm.gc_relocate(%a)
>         %b.relocated = @llvm.gc_relocate(%b)
>         br %body
>
>     This allows us to not bother with relocating derived pointers pointing
>     inside %a and %b, since it is semantically incorrect for llvm to reuse
>     them in the next iteration of the loop. 
>
>
> This is the right general idea, but you can already express this 
> constraint in LLVM as it exists today, by using llvm.gcroot().  As you 
> noted, this also solves the interior-pointer problem by making it the 
> front end's job to convey to LLVM when it would/would not be safe to 
> cache interior pointers across loop iterations. The invariant that a 
> front-end must maintain is that any pointer which is live across a 
> given potential-GC-point must be reloaded from its root after a 
> (relocating) GC might have occurred. This falls naturally out of the 
> viewpoint that %a is not an object pointer, it's the name of an object 
> pointer's value at a given point in time. So, of course, whenever that 
> object pointer's value might change, there must be a new name.
To rephrase, you're saying that the current gcroot mechanism is 
analogous to a boxed object pointer.  We could model a safepoint by 
storing the unboxed value into the box, applying an opaque operation to 
the box, and reloading the raw object pointer from the box.  (The opaque 
operator is key to prevent the store/load pair from being removed.  It 
also implements the actual safepoint operation.)  Is this a correct 
restatement?

Here's an example:
gcroot a = ...; b = ...;
object* ax = *a, bx = *b;
repeat 500000 iterations {
   spin for 50 instructions
   *a = ax;
   *b = bx;
   safepoint(a, b)
   ax = *a;
   bx = *b;
}

If so, I would agree with you that this is a correct encoding of object 
relocation.  I think what got me confused was using the in-tree examples 
to reverse engineer the semantics.  Both the Erlang and Ocaml examples 
insert safepoints after all the LLVM IR passes are run and derived 
pointers were inserted.  This was the part that got me thinking that the 
gcroot semantics were unsuitable for a precise relocating collector.  If 
you completely ignored these implementations and inserted the full 
box/safepoint call/unbox implementation at each safepoint before 
invoking any optimizations, I think this would be correct.

One problem with this encoding is that there does not currently exist an 
obvious mechanism to describe a safepoint in the IR itself.  (i.e. there 
is no llvm.gcsafepoint)  You could model this with a "well known" 
function which a custom GCStrategy recorded a stackmap on every call.  
It would be good to extend the existing intrinsics with such a mechanism.

At least if I'm reading things right, the current *implementation* is 
not a correct implementation of the intended semantics.  In particular, 
the safepoint operation which provides the opaque manipulation of the 
boxed gcroots is not preserved into the SelectionDAG.  As a result, 
optimizations on the SelectionDAG could eliminate the now adjacent 
box/unbox pairs.  This would break a relocating collector.

Leaving this aside, there are also a number of performance problems with 
the current implementation.  I'll summarize them here for now, but will 
expand into approaches for resolving each if this looks like the most 
likely implementation strategy.
1) Explicitly adding box/safepoint/unbox prevents creation of derived 
pointers.  This prevents optimizations such as loop-blocking.  Ideally, 
we'd rather let the derived pointers be created and capture them for 
updating at the safepoint.
2) The redundant loads and stores required for box/unbox.  (These might 
be partially eliminated by other optimization passes.)
3) The inability to allocate GC roots to registers.
4) Frame sizes are implicitly doubled since both an unboxed and boxed 
representation of every object pointer is required.

Frankly, I think that (3) is likely solvable, but that (1) and (4) could 
be fatal for a high performance implementation.  I don't have hard 
numbers on that; I'm simply stating my intuition.

>
> The fact that the mutable memory associated with a gcroot() is 
> allocated on the stack (rather than, say, a machine register) is an 
> implementation detail; fixing it doesn't require altering the 
> (conceptual) interface for LLVM's existing GC support, AFAICT.
While in principal, I agree with you here, in practice the difference is 
actually quite significant.  I am not convinced that the implementation 
would be straight forward.  Let's set this aside for the moment and 
focus on the more fundamental questions.
>
>     We lower gc_relocate to a
>     pseudo opcode which lowered into nothing after register allocation.
>
>     The problem is, of course, the performance penalty.  Does it make
>     sense to get the register allocator "see" the gc_relocate instruction
>     as a copy so that they get the same register / slot?  Will that
>     violate the intended semantics of gc_relocate (for example, after
>     assigning the same register / slot to %a and %a.relocated, are there
>     passes that will try to cache derived pointers across loop
>     iterations)?
>
>     Thanks,
>     -- Sanjoy
>
>
>     _______________________________________________
>     LLVM Developers mailing list
>     LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>
>     http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu          http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131025/c75e46b2/attachment.html>