path: root/docs/GarbageCollection.rst

=====================================
Accurate Garbage Collection with LLVM
=====================================

.. contents::
   :local:

Introduction
============

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
and maintain.  Many programming languages rely on garbage collection for
automatic memory management.  There are two primary forms of garbage collection:
conservative and accurate.

Conservative garbage collection often does not require any special support from
either the language or the compiler: it can handle non-type-safe programming
languages (such as C/C++) and does not require any special information from the
compiler.  The `Boehm collector
<http://www.hpl.hp.com/personal/Hans_Boehm/gc/>`__ is an example of a
state-of-the-art conservative collector.

Accurate garbage collection requires the ability to identify all pointers in the
program at run-time (which requires that the source-language be type-safe in
most cases).  Identifying pointers at run-time requires compiler support to
locate all places that hold live pointer variables at run-time, including the
:ref:`processor stack and registers <gcroot>`.

Conservative garbage collection is attractive because it does not require any
special compiler support, but it does have problems.  In particular, because the
conservative garbage collector cannot *know* that a particular word in the
machine is a pointer, it cannot move live objects in the heap (preventing the
use of compacting and generational GC algorithms) and it can occasionally suffer
from memory leaks due to integer values that happen to point to objects in the
program.  In addition, some aggressive compiler transformations can break
conservative garbage collectors (though these seem rare in practice).

Accurate garbage collectors do not suffer from any of these problems, but they
can suffer from degraded scalar optimization of the program.  In particular,
because the runtime must be able to identify and update all pointers active in
the program, some optimizations are less effective.  In practice, however, the
locality and performance benefits of using aggressive garbage collection
techniques dominates any low-level losses.

This document describes the mechanisms and interfaces provided by LLVM to
support accurate garbage collection.

Goals and non-goals
-------------------

LLVM's intermediate representation provides :ref:`garbage collection intrinsics
<gc_intrinsics>` that offer support for a broad class of collector models.  For
instance, the intrinsics permit:

* semi-space collectors

* mark-sweep collectors

* 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.

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
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 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
  safely.

* Computation of the stack map.  For each safe point in the code, object
  references within the stack frame must be identified so that the collector may
  traverse and perhaps update them.

* Write barriers when storing object references to the heap.  These are commonly
  used to optimize incremental scans in generational collectors.

* Emission of read barriers when loading object references.  These are useful
  for interoperating with concurrent collectors.

There are additional areas that LLVM does not directly address:

* Registration of global roots with the runtime.

* Registration of stack map entries with the runtime.

* The functions used by the program to allocate memory, trigger a collection,
  etc.

* Computation or compilation of type maps, or registration of them with the
  runtime.  These are used to crawl the heap for object references.

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.

Getting started
===============

Using a GC with LLVM implies many things, for example:

* Write a runtime library or find an existing one which implements a GC heap.

  #. Implement a memory allocator.

  #. Design a binary interface for the stack map, used to identify references
     within a stack frame on the machine stack.\*

  #. Implement a stack crawler to discover functions on the call stack.\*

  #. Implement a registry for global roots.

  #. Design a binary interface for type maps, used to identify references
     within heap objects.

  #. Implement a collection routine bringing together all of the above.

* Emit compatible code from your compiler.

  * Initialization in the main function.

  * Use the ``gc "..."`` attribute to enable GC code generation (or
    ``F.setGC("...")``).

  * Use ``@llvm.gcroot`` to mark stack roots.

  * Use ``@llvm.gcread`` and/or ``@llvm.gcwrite`` to manipulate GC references,
    if necessary.

  * Allocate memory using the GC allocation routine provided by the runtime
    library.

  * Generate type maps according to your runtime's binary interface.

* Write a compiler plugin to interface LLVM with the runtime library.\*

  * Lower ``@llvm.gcread`` and ``@llvm.gcwrite`` to appropriate code
    sequences.\*

  * Compile LLVM's stack map to the binary form expected by the runtime.

* Load the plugin into the compiler.  Use ``llc -load`` or link the plugin
  statically with your language's compiler.\*

* Link program executables with the runtime.

To help with several of these tasks (those indicated with a \*), LLVM includes a
highly portable, built-in ShadowStack code generator.  It is compiled into
``llc`` and works even with the interpreter and C backends.

In your compiler
----------------

To turn the shadow stack on for your functions, first call:

.. code-block:: c++

  F.setGC("shadow-stack");

for each function your compiler emits. Since the shadow stack is built into
LLVM, you do not need to load a plugin.

Your compiler must also use ``@llvm.gcroot`` as documented.  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 easily be collected
if evaluating ``g()`` triggers a collection.

There's no need to use ``@llvm.gcread`` and ``@llvm.gcwrite`` over plain
``load`` and ``store`` for now.  You will need them when switching to a more
advanced GC.

In your runtime
---------------

The shadow stack doesn't imply a memory allocation algorithm.  A semispace
collector or building atop ``malloc`` are great places to start, and can be
implemented with very little code.

When it comes time to collect, however, your runtime needs to traverse the stack
roots, and for this it needs to integrate with the shadow stack.  Luckily, doing
so is very simple. (This code is heavily commented to help you understand the
data structure, but there are only 20 lines of meaningful code.)

.. code-block:: c++

  /// @brief The map for a single function's stack frame.  One of these is
  ///        compiled as constant data into the executable for each function.
  ///
  /// Storage of metadata values is elided if the %metadata parameter to
  /// @llvm.gcroot is null.
  struct FrameMap {
    int32_t NumRoots;    //< Number of roots in stack frame.
    int32_t NumMeta;     //< Number of metadata entries.  May be < NumRoots.
    const void *Meta[0]; //< Metadata for each root.
  };

  /// @brief A link in the dynamic shadow stack.  One of these is embedded in
  ///        the stack frame of each function on the call stack.
  struct StackEntry {
    StackEntry *Next;    //< Link to next stack entry (the caller's).
    const FrameMap *Map; //< Pointer to constant FrameMap.
    void *Roots[0];      //< Stack roots (in-place array).
  };

  /// @brief The head of the singly-linked list of StackEntries.  Functions push
  ///        and pop onto this in their prologue and epilogue.
  ///
  /// Since there is only a global list, this technique is not threadsafe.
  StackEntry *llvm_gc_root_chain;

  /// @brief Calls Visitor(root, meta) for each GC root on the stack.
  ///        root and meta are exactly the values passed to
  ///        @llvm.gcroot.
  ///
  /// Visitor could be a function to recursively mark live objects.  Or it
  /// might copy them to another heap or generation.
  ///
  /// @param Visitor A function to invoke for every GC root on the stack.
  void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {
    for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {
      unsigned i = 0;

      // For roots [0, NumMeta), the metadata pointer is in the FrameMap.
      for (unsigned e = R->Map->NumMeta; i != e; ++i)
        Visitor(&R->Roots[i], R->Map->Meta[i]);

      // For roots [NumMeta, NumRoots), the metadata pointer is null.
      for (unsigned e = R->Map->NumRoots; i != e; ++i)
        Visitor(&R->Roots[i], NULL);
    }
  }

About the shadow stack
----------------------

Unlike many GC algorithms which rely on a cooperative code generator to compile
stack maps, this algorithm carefully maintains a linked list of stack roots
[:ref:`Henderson2002 <henderson02>`].  This so-called "shadow stack" mirrors the
machine stack.  Maintaining this data structure is slower than using a stack map
compiled into the executable as constant data, but has a significant portability
advantage because it requires no special support from the target code generator,
and does not require tricky platform-specific code to crawl the machine stack.

The tradeoff for this simplicity and portability is:

* High overhead per function call.

* Not thread-safe.

Still, it's an easy way to get started.  After your compiler and runtime are up
and running, writing a :ref:`plugin <plugin>` will allow you to take advantage
of :ref:`more advanced GC features <collector-algos>` of LLVM in order to
improve performance.

.. _gc_intrinsics:

IR features
===========

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.

Specifying GC code generation: ``gc "..."``
-------------------------------------------

.. code-block:: llvm

  define ty @name(...) gc "name" { ...

The ``gc`` function attribute is used to specify the desired GC style 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.

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``
--------------------------------------------------

.. code-block:: llvm

  void @llvm.gcroot(i8** %ptrloc, i8* %metadata)

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.
T