[LLVMdev] Why LLVM should NOT have garbage collection intrinsics

[Gordon Henriksen]

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