[LLVMdev] llvm.gcroot suggestion

[Talin]

On Thu, Feb 17, 2011 at 1:07 PM, Talin <viridia at gmail.com> wrote:

> On Wed, Feb 16, 2011 at 4:51 PM, Talin <viridia at gmail.com> wrote:
>
>> I think I'm one of the few people actually using LLVM's support for
>> garbage collection, and so far I've found it very difficult to generate code
>> that uses llvm.gcroot() correctly.
>>
>> In the current scheme, it is the frontend's responsibility to insure that
>> any intermediate SSA values containing references to garbage collectible
>> objects are copied to stack variables so that the GC strategy can calculate
>> offsets for them. It is also the frontend's responsibility to reload those
>> values after a sync point, since the collector may have moved them around.
>> An additional chore is creating all of the allocas for those roots, which
>> have to be in the first block of the function (because that's where allocas
>> go according to my understanding of the rules of IR.)
>>
>> What this means is that the frontend is forced to generate very
>> inefficient IR, with dozens of alloca slots at the beginning of the
>> function, each marked as a root. It also has to initialize each of these
>> roots to a known value, even if the root is only "live" for a very small
>> part of the CFG. This is because currently there's no way for the frontend
>> to tell LLVM that a given root has a limited lifespan (since calls to
>> llvm.gcroot also have to be in the first block), and so you have to take a
>> conservative approach and treat every root as if it were live for the entire
>> function.
>>
>> It seems to me that "gc-rootness" should not be an aspect of an alloca, as
>> it currently is now, but rather an aspect of a Value, similar to the way
>> llvm.dbg.value() works.
>>
>> Let's imagine a new intrinsic, llvm.gcvalue(), which takes as its
>> arguments a Value and a metadata pointer, and returns that same value as its
>> result. The frontend can "wrap" any value, of any type, with llvm.gcvalue(),
>> which is a signal to LLVM that this value is a garbage collection root. It
>> would then be the responsibility of LLVM's code generator (or possibly some
>> lowering pass) to insure that this value lives on the stack during sync
>> points, and is reloaded after a sync point if it is still needed. During a
>> sync point, these values would be treated exactly the way llvm.gcroot works
>> today - that is, they live on the stack, and the GCStrategy gets passed a
>> list of stack offsets and metadata pointers. The main difference is that
>> only the values that are actually 'live' during the sync point are lowered
>> from SSA values to allocas.
>>
>> This approach offers a bunch of advantages that I can think of:
>>
>>    - LLVM knows much more about the liveness of values than the frontend
>>    does, and could compute a much more optimal and minimal stack map for each
>>    sync point. That is, two variables whose lifetimes do not overlap can use
>>    the same stack location for their roots to be stored in, and the stack maps
>>    generated by the GCStrategy would reflect this.
>>    - If at some future time LLVM supports register maps for garbage
>>    collection, you would not have to update your frontend. Since we're marking
>>    values, not stack slots, the frontend doesn't have to care where the
>>    variable is stored, so all frontends can take advantage of improvements in
>>    the representation of stack maps.
>>    - Writing frontends gets a lot easier, since the frontend is no longer
>>    responsible for generating and initializing allocas for every root. It also
>>    means a lot fewer opportunities for generating incorrect code.
>>
>> What do you think?
>>
>
> So a few additional thoughts: I think that it would be best to keep the
> existing llvm.gcroot() call in addition to having llvm.gvcalue().
> llvm.gcroot() would be used for marking allocas as roots, and llvm.gcvalue()
> would mark SSA values as roots.
>
> In fact, if I could go back in time, I would rename them to correspond
> exactly with the llvm.dbg intrinsics. So in addition to llvm.dbg.declare()
> and llvm.dbg.value(), we'd also have llvm.gc.declare() and llvm.gc.value(),
> with analogous uses.
>
> Note that it is important that the LLVM GC intrinsics should not assume
> that the their arguments are pointers, as they could in some cases be
> structs or arrays that contain pointers. LLVM should make no assumptions
> about the internal structure of a GC root, that is an issue for the
> language's GCStrategy pass to worry about - typically the frontend will use
> the metadata argument to communicate the structure of a root to the
> GCStrategy. The only thing that LLVM has to guarantee is that during a sync
> point, it will be possible to associate each live root with an address in
> memory somewhere.
>
> As far as implementation goes, I'm assuming that there would be some pass
> that converts llvm.gcvalue() intrinsics into llvm.gcroot() intrinsics by
> temporarily storing the the root into an alloca and then reloading it as
> needed. (Actually you would probably want something richer than the current
> llvm.gcroot that allows an explicit begin and end so that information about
> liveness can be preserved. How about llvm.gc.beginroot() intrinsic to
> indicate that a given alloca should be considered a root starting at that
> point in the CFG, and llvm.gc.endroot() to indicate that the specified root
> no longer needs to be considered a root. This is much better than the
> current method of assigning NULL to a root, as it accommodates non-pointer
> roots, and avoids the extra pointer store which is not needed in many
> cases.)
>
> What is unclear to me is exactly when this should occur relative to other
> passes, but I think what you would want to do is perform optimization and
> liveness analysis first - thereby eliminating potentially dead roots before
> they are converted to memory locations. Unfortunately, I can't say too much
> about this, as I am not a backend person - I know very little about
> optimization and code generation in general or LLVM's backend passes in
> particular.
>
> There would also need to be some way to tell the code generator not to
> reload values after a sync point if the collector doesn't require it, such
> as a mark-and-sweep or other non-copying algorithm. The most straightforward
> way to handle this would be as an argument to the pass that does the
> lowering of llvm.gcvalue intrinsics.
>

Thinking about it even more, here's a short summary of what I would propose:

   - *llvm.gc.value*(value, metadata) - marks an SSA value as a garbage
   collection root. This remains in effect for the lifetime of the SSA value.
   - *llvm.gc.declare*(alloca, metadata) - marks an alloca as a garbage
   collection root. This intrinsic tells LLVM that it should start treating the
   alloca as a GC root from that point in the CFG onward.
   - *llvm.gc.undeclare*(alloca) - tells LLVM that the alloca should no
   longer be considered a GC root. If llvm.undeclare() is never called, then
   the alloca is treated as a root until the end of the function.

One other thing I thought of was that it would be convenient to declare
function parameters with llvm.gc.value(). However, I can get around not
having that as a feature.

-- 
-- Talin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110217/922a0159/attachment.html>