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>