.. contents::
:local:
-Introduction
-============
+Abstract
+========
This document covers how to integrate LLVM into a compiler for a language which
supports garbage collection. **Note that LLVM itself does not provide a
You will need to identify roots (i.e. references to heap objects your collector
needs to know about) in your generated IR, so that LLVM can encode them into
your final stack maps. Depending on the collector strategy chosen, this is
-accomplished by using either the ''@llvm.gcroot'' intrinsics or an
-''gc.statepoint'' relocation sequence.
+accomplished by using either the ``@llvm.gcroot`` intrinsics or an
+``gc.statepoint`` relocation sequence.
Don't forget to create a root for each intermediate value that is generated when
evaluating an expression. In ``h(f(), g())``, the result of ``f()`` could
executable (for a static compiler) or ensure the appropriate symbols are
available for the runtime linker (for a JIT compiler).
+
+Introduction
+============
+
What is Garbage Collection?
-===========================
+---------------------------
Garbage collection is a widely used technique that frees the programmer from
having to know the lifetimes of heap objects, making software easier to produce
* generational collectors
-* reference counting
-
* incremental collectors
* concurrent collectors
* cooperative collectors
-We hope that the primitive support built into the LLVM IR is sufficient to
-support a broad class of garbage collected languages including Scheme, ML, Java,
-C#, Perl, Python, Lua, Ruby, other scripting languages, and more.
+* reference counting
-However, LLVM does not itself provide a garbage collector --- this should be
-part of your language's runtime library. LLVM provides a framework for compile
-time :ref:`code generation plugins <plugin>`. The role of these plugins is to
+We hope that the support built into the LLVM IR is sufficient to support a
+broad class of garbage collected languages including Scheme, ML, Java, C#,
+Perl, Python, Lua, Ruby, other scripting languages, and more.
+
+Note that LLVM **does not itself provide a garbage collector** --- this should
+be part of your language's runtime library. LLVM provides a framework for
+describing the garbage collectors requirements to the compiler. In particular,
+LLVM provides support for generating stack maps at call sites, polling for a
+safepoint, and emitting load and store barriers. You can also extend LLVM -
+possibly through a loadable :ref:`code generation plugins <plugin>` - to
generate code and data structures which conforms to the *binary interface*
specified by the *runtime library*. This is similar to the relationship between
LLVM and DWARF debugging info, for example. The difference primarily lies in
the lack of an established standard in the domain of garbage collection --- thus
-the plugins.
+the need for a flexible extension mechanism.
The aspects of the binary interface with which LLVM's GC support is
concerned are:
-* Creation of GC-safe points within code where collection is allowed to execute
+* Creation of GC safepoints within code where collection is allowed to execute
safely.
* Computation of the stack map. For each safe point in the code, object
In general, LLVM's support for GC does not include features which can be
adequately addressed with other features of the IR and does not specify a
particular binary interface. On the plus side, this means that you should be
-able to integrate LLVM with an existing runtime. On the other hand, it leaves a
-lot of work for the developer of a novel language. However, it's easy to get
-started quickly and scale up to a more sophisticated implementation as your
-compiler matures.
-
-Runtime Requirements
-====================
-
-LLVM does not provide a garbage collector. You should be able to leverage any existing collector library that includes the following elements:
-
-#. A memory allocator which exposes an allocation function your compiled
- code can call.
-
-#. A binary format for the stack map. A stack map describes the location
- of references at a safepoint and is used by precise collectors to identify
- references within a stack frame on the machine stack. Note that collectors
- which conservatively scan the stack don't require such a structure.
-
-#. A stack crawler to discover functions on the call stack, and enumerate the
- references listed in the stack map for each call site.
-
-#. A mechanism for identifying references in global locations (e.g. global
- variables).
-
-#. If you collector requires them, an LLVM IR implementation of your collectors
- load and store barriers. Note that since many collectors don't require
- barriers at all, LLVM defaults to lowering such barriers to normal loads
- and stores unless you arrange otherwise.
+able to integrate LLVM with an existing runtime. On the other hand, it can
+have the effect of leaving a lot of work for the developer of a novel
+language. We try to mitigate this by providing built in collector strategy
+descriptions that can work with many common collector designs and easy
+extension points. If you don't already have a specific binary interface
+you need to support, we recommend trying to use one of these built in collector
+strategies.
.. _gc_intrinsics:
This section describes the garbage collection facilities provided by the
:doc:`LLVM intermediate representation <LangRef>`. The exact behavior of these
-IR features is specified by the binary interface implemented by a :ref:`code
-generation plugin <plugin>`, not by this document.
-
-These facilities are limited to those strictly necessary; they are not intended
-to be a complete interface to any garbage collector. A program will need to
-interface with the GC library using the facilities provided by that program.
+IR features is specified by the selected :ref:`GC strategy description
+<plugin>`.
Specifying GC code generation: ``gc "..."``
-------------------------------------------
.. code-block:: llvm
- define ty @name(...) gc "name" { ...
+ define <returntype> @name(...) gc "name" { ... }
-The ``gc`` function attribute is used to specify the desired GC style to the
+The ``gc`` function attribute is used to specify the desired GC strategy to the
compiler. Its programmatic equivalent is the ``setGC`` method of ``Function``.
-Setting ``gc "name"`` on a function triggers a search for a matching code
-generation plugin "*name*"; it is that plugin which defines the exact nature of
-the code generated to support GC. If none is found, the compiler will raise an
-error.
+Setting ``gc "name"`` on a function triggers a search for a matching subclass
+of GCStrategy. Some collector strategies are built in. You can add others
+using either the loadable plugin mechanism, or by patching your copy of LLVM.
+It is the selected GC strategy which defines the exact nature of the code
+generated to support GC. If none is found, the compiler will raise an error.
Specifying the GC style on a per-function basis allows LLVM to link together
programs that use different garbage collection algorithms (or none at all).
.. _gcroot:
-Identifying GC roots on the stack: ``llvm.gcroot``
---------------------------------------------------
+Identifying GC roots on the stack
+----------------------------------
+
+LLVM currently supports two different mechanisms for describing references in
+compiled code at safepoints. ``llvm.gcroot`` is the older mechanism;
+``gc.statepoint`` has been added more recently. At the moment, you can choose
+either implementation (on a per :ref:`GC strategy <plugin>` basis). Longer
+term, we will probably either migrate away from ``llvm.gcroot`` entirely, or
+substantially merge their implementations. Note that most new development
+work is focused on ``gc.statepoint``.
+
+Using ``gc.statepoint``
+^^^^^^^^^^^^^^^^^^^^^^^^
+:doc:`This page <Statepoints>` contains detailed documentation for
+``gc.statepoint``.
+
+Using ``llvm.gcwrite``
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
.. code-block:: llvm
The ``llvm.gcroot`` intrinsic is used to inform LLVM that a stack variable
references an object on the heap and is to be tracked for garbage collection.
-The exact impact on generated code is specified by a :ref:`compiler plugin
-<plugin>`. All calls to ``llvm.gcroot`` **must** reside inside the first basic
-block.
+The exact impact on generated code is specified by the Function's selected
+:ref:`GC strategy <plugin>`. All calls to ``llvm.gcroot`` **must** reside
+inside the first basic block.
+
+The first argument **must** be a value referring to an alloca instruction or a
+bitcast of an alloca. The second contains a pointer to metadata that should be
+associated with the pointer, and **must** be a constant or global value
+address. If your target collector uses tags, use a null pointer for metadata.
-A compiler which uses mem2reg to raise imperative code using ``alloca`` into SSA
-form need only add a call to ``@llvm.gcroot`` for those variables which a
-pointers into the GC heap.
+A compiler which performs manual SSA construction **must** ensure that SSA
+values representing GC references are stored in to the alloca passed to the
+respective ``gcroot`` before every call site and reloaded after every call.
+A compiler which uses mem2reg to raise imperative code using ``alloca`` into
+SSA form need only add a call to ``@llvm.gcroot`` for those variables which
+are pointers into the GC heap.
It is also important to mark intermediate values with ``llvm.gcroot``. For
example, consider ``h(f(), g())``. Beware leaking the result of ``f()`` in the
case that ``g()`` triggers a collection. Note, that stack variables must be
initialized and marked with ``llvm.gcroot`` in function's prologue.
-The first argument **must** be a value referring to an alloca instruction or a
-bitcast of an alloca. The second contains a pointer to metadata that should be
-associated with the pointer, and **must** be a constant or global value
-address. If your target collector uses tags, use a null pointer for metadata.
-
The ``%metadata`` argument can be used to avoid requiring heap objects to have
'isa' pointers or tag bits. [Appel89_, Goldberg91_, Tolmach94_] If specified,
its value will be tracked along with the location of the pointer in the stack
%derived = getelementptr %object, i32 0, i32 2, i32 %n
LLVM does not enforce this relationship between the object and derived pointer
-(although a :ref:`plugin <plugin>` might). However, it would be an unusual
-collector that violated it.
+(although a particular :ref:`collector strategy <plugin>` might). However, it
+would be an unusual collector that violated it.
+
+The use of these intrinsics is naturally optional if the target GC does not
+require the corresponding barrier. The GC strategy used with such a collector
+should replace the intrinsic calls with the corresponding ``load`` or
+``store`` instruction if they are used.
-The use of these intrinsics is naturally optional if the target GC does require
-the corresponding barrier. Such a GC plugin will replace the intrinsic calls
-with the corresponding ``load`` or ``store`` instruction if they are used.
+One known deficiency with the current design is that the barrier intrinsics do
+not include the size or alignment of the underlying operation performed. It is
+currently assumed that the operation is of pointer size and the alignment is
+assumed to be the target machine's default alignment.
Write barrier: ``llvm.gcwrite``
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
For write barriers, LLVM provides the ``llvm.gcwrite`` intrinsic function. It
has exactly the same semantics as a non-volatile ``store`` to the derived
-pointer (the third argument). The exact code generated is specified by a
-
compiler :ref:`plugin <plugin>`.
+pointer (the third argument). The exact code generated is specified by the
+
Function's selected :ref:`GC strategy <plugin>`.
Many important algorithms require write barriers, including generational and
concurrent collectors. Additionally, write barriers could be used to implement
For read barriers, LLVM provides the ``llvm.gcread`` intrinsic function. It has
exactly the same semantics as a non-volatile ``load`` from the derived pointer
-(the second argument). The exact code generated is specified by a
-
:ref:`compiler plugin <plugin>`.
+(the second argument). The exact code generated is specified by the Function's
+
selected :ref:`GC strategy <plugin>`.
Read barriers are needed by fewer algorithms than write barriers, and may have a
greater performance impact since pointer reads are more frequent than writes.
.. _plugin:
-Built In Collectors
-====================
+.. _builtin-gc-strategies:
+
+Built In GC Strategies
+======================
LLVM includes built in support for several varieties of garbage collectors.
The 'Erlang' and 'Ocaml' GCs
-----------------------------
-LLVM ships with two example collectors which leverage the ''gcroot''
+LLVM ships with two example collectors which leverage the ``gcroot``
mechanisms. To our knowledge, these are not actually used by any language
runtime, but they do provide a reasonable starting point for someone interested
-in writing an ''gcroot' compatible GC plugin. In particular, these are the
+in writing an ``gcroot`` compatible GC plugin. In particular, these are the
only in tree examples of how to produce a custom binary stack map format using
-a ''gcroot'' strategy.
+a ``gcroot`` strategy.
As there names imply, the binary format produced is intended to model that
used by the Erlang and OCaml compilers respectively.
+.. _statepoint_example_gc:
The Statepoint Example GC
-------------------------
F.setGC("statepoint-example");
This GC provides an example of how one might use the infrastructure provided
-by ''gc.statepoint''.
+by ``gc.statepoint``. This example GC is compatible with the
+:ref:`PlaceSafepoints` and :ref:`RewriteStatepointsForGC` utility passes
+which simplify ``gc.statepoint`` sequence insertion. If you need to build a
+custom GC strategy around the ``gc.statepoints`` mechanisms, it is recommended
+that you use this one as a starting point.
+
+This GC strategy does not support read or write barriers. As a result, these
+intrinsics are lowered to normal loads and stores.
+The stack map format generated by this GC strategy can be found in the
+:ref:`stackmap-section` using a format documented :ref:`here
+<statepoint-stackmap-format>`. This format is intended to be the standard
+format supported by LLVM going forward.
+
+The CoreCLR GC
+-------------------------
+
+.. code-block:: c++
+
+ F.setGC("coreclr");
+
+This GC leverages the ``gc.statepoint`` mechanism to support the
+`CoreCLR <https://github.com/dotnet/coreclr>`__ runtime.
+
+Support for this GC strategy is a work in progress. This strategy will
+differ from
+:ref:`statepoint-example GC<statepoint_example_gc>` strategy in
+certain aspects like:
+
+* Base-pointers of interior pointers are not explicitly
+ tracked and reported.
+
+* A different format is used for encoding stack maps.
+
+* Safe-point polls are only needed before loop-back edges
+ and before tail-calls (not needed at function-entry).
Custom GC Strategies
====================
easy way we can extend the support to make it work for your use case without
requiring a custom build.
+Collector Requirements
+----------------------
+
+You should be able to leverage any existing collector library that includes the following elements:
+
+#. A memory allocator which exposes an allocation function your compiled
+ code can call.
+
+#. A binary format for the stack map. A stack map describes the location
+ of references at a safepoint and is used by precise collectors to identify
+ references within a stack frame on the machine stack. Note that collectors
+ which conservatively scan the stack don't require such a structure.
+
+#. A stack crawler to discover functions on the call stack, and enumerate the
+ references listed in the stack map for each call site.
+
+#. A mechanism for identifying references in global locations (e.g. global
+ variables).
+
+#. If you collector requires them, an LLVM IR implementation of your collectors
+ load and store barriers. Note that since many collectors don't require
+ barriers at all, LLVM defaults to lowering such barriers to normal loads
+ and stores unless you arrange otherwise.
+
Implementing a collector plugin
-------------------------------
projects / oota-llvm.git / blobdiff