[LLVMdev] llvm.gcroot suggestion

[Talin]

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.

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