+.. _builtin-gc-strategies:
+
+Built In GC Strategies
+======================
+
+LLVM includes built in support for several varieties of garbage collectors.
+
+The Shadow Stack GC
+----------------------
+
+To use this collector strategy, mark your functions with:
+
+.. code-block:: c++
+
+ F.setGC("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.
+
+
+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);
+ }
+ }
+
+
+The 'Erlang' and 'Ocaml' GCs
+-----------------------------
+
+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
+only in tree examples of how to produce a custom binary stack map format using
+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
+-------------------------
+
+.. code-block:: c++
+
+ F.setGC("statepoint-example");
+
+This GC provides an example of how one might use the infrastructure provided
+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
+====================
+
+If none of the built in GC strategy descriptions met your needs above, you will
+need to define a custom GCStrategy and possibly, a custom LLVM pass to perform
+lowering. Your best example of where to start defining a custom GCStrategy
+would be to look at one of the built in strategies.
+
+You may be able to structure this additional code as a loadable plugin library.
+Loadable plugins are sufficient if all you need is to enable a different
+combination of built in functionality, but if you need to provide a custom
+lowering pass, you will need to build a patched version of LLVM. If you think
+you need a patched build, please ask for advice on llvm-dev. There may be an
+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.
+
+