[LLVMdev] Why LLVM should NOT have garbage collection intrinsics
Gordon Henriksen
gordonhenriksen at me.com
Sun Mar 1 07:32:47 PST 2009
On 2009-03-01, at 05:41, Mark Shannon wrote:
> Gordon Henriksen wrote:
>
>>> The semantics of llvm.gcroot are vague: "At compile-time, the code
>>> generator generates information to allow the runtime to find the
>>> pointer at GC safe points."
>>>
>>> Vague, ill-specified interfaces are worse than none.
>>
>> There's nothing ill-defined about the semantics of gcroot except
>> insofar as GC code generation is pluggable.
>>
>
> Sorry, but "At compile-time, the code generator generates
> information to allow the runtime to find the pointer at GC safe
> points." does not really say anything. No one could possibly
> implement this "specification".
llvm.gcroot is an interface to a runtime library (or binary format)
only through the mediation of the GC plugin, so the exact front-to-
back behavior is undefined, yes. Likewise, the 'add' instruction does
not specify by what machine instruction the addition will be
performed, yet it is not vague.
What is communicated to the plugins themselves through the presence of
a llvm.gcroot call is detailed lower in the document, in the
Implementing a GC Plugin section.
This is abstract and complex, but not imprecise. Still, if you'd like
to propose improved wording for GarbageCollection.html that makes this
clearer for you, I'd be happy to incorporate it.
> I would like to implement a generational collector for llvm, but I
> cannot do so in a portable way.
You'll certainly need to map roots on the stack and use write barriers.
• shadow-stack is an easy, portable way to bring up root discovery.
You can switch to static stack maps later (with the requirement that
your runtime be able to crawl the machine stack, which is out-of-scope
for LLVM unless Talin makes some progress with his GC building blocks).
• As you observe, your write barrier can be written in LLVM IR without
the use of the llvm.gcwrite intrinsic if you so desire. Otherwise, you
can perform the IR-to-IR transform to eliminate llvm.gcwrite using the
performCustomLowering hook.
What else is blocking you?
> By the way, I think that adding a GC pointer type is an unnecessary
> burden on the the back-ends, front-ends really should be able to
> handle this.
I don't see how these points mesh together into a single concern, but
I can address your three points:
• On your concern for "burdening the backends." You've used this straw
man before. LLVM backends are not monoliths; they actually share a
great deal of code. All current GC changes were made in the shared
codebase, making the cost-to-implement and maintain O(1), not O(N). I
see no reason this would change in the future.
• On whether the back-end need be involved. As I've already discussed
WRT stack layout, the back-end must be involved because only it knows
how stack frames and code are laid out. I'd like to reemphasize that
back ends can and do introduce or delete both control flow and calls
in the program--adding safe points which are not (as such) represented
in LLVM IR. Thus, the front-end cannot know even the set of all safe
points (much less their locations). From that, it follows that
liveness and stack maps cannot be computed by the front-end, precisely
because they need be computed at said unknown safe points. Finally, I
hope it's abundantly obvious that register maps are impossible for the
front-end to compute.
• On whether a GC pointer type is necessary in the IR. 'llvm.gcroot'
as it stands today basically makes GC pointer manipulation code opaque
to all of LLVM's optimizations, both front- and back-end. (The root
alloca 'escapes', so mem2reg can't hack on it, and all is lost.) The
generated code is full of redundant memory operations as a result.
There's true redundancy, and there's the redundancy required when
passing a safe point without register maps. Allowing SSA values to be
GC roots directly (rather than merely pointing to roots) would enable
improvements in this area.
> The current trio of gcroot, gcread and gcwrite is OK, BUT GC
> implementations should be able to translate them to llvm-IR so that
> the optimisers and back-ends can do their jobs without worrying
> about GC details.
GC plugins can already eliminate GC intrinsics prior to code
generation, for cases where the GC scheme can be represented as pure
IR. In the tree, shadow-stack is implemented as a pure IR transform.
http://llvm.org/docs/GarbageCollection.html#custom
But this is not the interesting case, since it has limitations as I
discussed above (and could've been written without the intrinsics in
the first place).
— Gordon
More information about the llvm-dev
mailing list