Improving GC intrinsics in LLVM

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Improving GC intrinsics in LLVM

Talin-3
A couple people have asked about this, so I wanted to describe my proposals for improving LLVM's garbage collection intrinsics.

Currently the llvm.gcroot intrinsic associates a set of GC metadata with a value, specifically a value produced by an alloca instruction. In the proposed scheme, GC metadata would instead be associated with a *type*.

The most general approach would be to introduce a new derived type called AnnotatedType, which is essentially a tuple consisting of (base type, id, metadata). The base type can be any valid LLVM type, including another AnnotatedType. The 'id' argument is an integer constant that is used to determine what kind of annotation this is. The 'metadata' argument is a const void* pointer, similar to the existing llvm.gcroot() argument, which can point to any constant data structure.

There would be a fixed set of annotation ids, one of which would be GC_ROOT. Other kinds of type annotations could be introduced later for other purposes.

AnnnotatedType instances would be folded/uniqued just like all other derived types.

LLVM optimizers and code generators would need to be modified to unwrap the base type whenever an annotated type was encountered. Ideally, transformations on values and types would preserve the annotations where possible. For example, when loading a memory location into an SSA value, if the type of the source memory location has an annotation, then the SSA value's type would have the same annotation.

In some cases, the presence of the annotation would disable certain kinds of backend transformations on those values.

Annotations would not be preserved through dereference. Instead, the contained type must have its own annotation if that is desired.

Most likely, different annotation types would have different rules for propagating onto intermediate and derived values. (This is why it's a fixed set rather than open-ended extensible).

The ultimate consumer of the GC_ROOT annotation would be a GCStrategy pass much like today. The GCStrategy pass would, for each function, be able to iterate through all local values (either allocas or SSA values) that were annotated with the GC_ROOT annotation. It could then generate whatever stack maps or register maps it wanted. It could use the metadata argument of the annotated type, or ignore it, depending on the specifics of the GC algorithm used.

Motivations: There are several advantages to this approach. First, it would be much less work for the frontend developer, since intermediate values (and particularly SSA values) would automatically inherit the "root" aspect from their source values. Thus, no more spilling and reloading of SSA values around safe points (spilling might still happen, but the frontend developer would not need to be aware of it). Secondly, optimization passes would now be able to more intelligently handle roots - instead of merely forbidding any optimizations on roots at all, they would be able to preserve roots through the transformation. An obvious example of this is mem2reg - it could convert memory locations which are roots into SSA values which are roots.

A final note: This is not something that I can personally work on, since I know very little about optimization and code generation. I'm mainly a parser / interpreter guy. This is more of a wish :)

--
-- Talin

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev