[LLVMdev] Interfacing llvm with a precise, relocating GC
Philip Reames
listmail at philipreames.com
Mon Oct 28 12:11:22 PDT 2013
On 10/26/13 9:08 AM, Ben Karel wrote:
>
>
>
> On Fri, Oct 25, 2013 at 8:35 PM, Philip Reames
> <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote:
>
> 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?
>
>
> What does it mean to model a safepoint?
Er, not quite sure what your question is.
My intent was to describe an abstract model which provides the correct
semantics for a safepoint. Is your confusion about my definition of
"safepoint"? Or my desire for an abstract model? Let me know and I'll
try to explain.
>
> 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.
>
>
> Since GC safepoints aren't explicitly represented at the IR level,
> either, SelectionDAG is a red herring: regular IR-level optimizations
> need the same scrutiny. But safepoints won't be inserted arbitrarily.
> Because there are only four places where safe points can occur
> (pre/post call, loop, return), there are essentially only two
> optimizations that might break a relocating collector: a call being
> reordered with the stores and loads surrounding it, or constant
> propagation of an alloca's contents across a loop backedge without
> eliminating the backedge (iff the GC plugin requests loop safepoints).
> Neither of these are performed by LLVM, AFAICT, which implies that the
> implementation is not broken in the way you suggested.
I agree that the SelectionDAG bit was a red herring. It turned out I
had misread the code involved with selecting safepoints. I had been
under the impression that ran between LLVM IR opts and SelectionDAG
opts. It doesn't; instead, it runs after machine dependent optimization
and register allocation. Sorry for the resulting confusion. It's
definitely time for me to transition to actually trying out examples
rather than simply relying on code inspection.
On a different note, your response was based on two assumptions that
seem problematic. I'm not trying to address your argument directly,
just pointing out possible issues for future discussions.
1) You're assuming that these are the only place a reasonable GC might
want to place safepoints. This is untrue. As an example, you'd like
the optimizer to be able to move a safepoint outside a bounded loop with
a small trip count. Not sure how this might effect things; just want to
get it out there.
2) You're basing your arguments on what LLVM currently does, not what
would be semantically correct for it to do. Given how quickly LLVM is
evolving, this is problematic. (I'm not saying your reasoning is
otherwise right or wrong. I haven't thought it through yet.)
>
> But if you can prove me wrong by producing an example that LLVM
> optimizations break, that would be cool :-)
I'm sure I'll have broken examples in the future, but not just yet. :)
> 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 <mailto: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/20131028/d3a4dee3/attachment.html>
More information about the llvm-dev
mailing list