1029 lines · plain
1=====================================2Garbage Collection with LLVM3=====================================4 5.. contents::6 :local:7 8Abstract9========10 11This document covers how to integrate LLVM into a compiler for a language which12supports garbage collection. **Note that LLVM itself does not provide a13garbage collector.** You must provide your own.14 15Quick Start16============17 18First, you should pick a collector strategy. LLVM includes a number of built-in19ones, but you can also implement a loadable plugin with a custom definition.20Note that the collector strategy is a description of how LLVM should generate21code such that it interacts with your collector and runtime, not a description22of the collector itself.23 24Next, mark your generated functions as using your chosen collector strategy.25From C++, you can call:26 27.. code-block:: c++28 29 F.setGC(<collector description name>);30 31 32This will produce IR like the following fragment:33 34.. code-block:: llvm35 36 define void @foo() gc "<collector description name>" { ... }37 38 39When generating LLVM IR for your functions, you will need to:40 41* Use ``@llvm.gcread`` and/or ``@llvm.gcwrite`` in place of standard load and42 store instructions. These intrinsics are used to represent load and store43 barriers. If your collector does not require such barriers, you can skip44 this step.45 46* Use the memory allocation routines provided by your garbage collector's47 runtime library.48 49* If your collector requires them, generate type maps according to your50 runtime's binary interface. LLVM is not involved in the process. In51 particular, the LLVM type system is not suitable for conveying such52 information through the compiler.53 54* Insert any coordination code required for interacting with your collector.55 Many collectors require running application code to periodically check a56 flag and conditionally call a runtime function. This is often referred to57 as a safepoint poll.58 59You will need to identify roots (i.e. references to heap objects your collector60needs to know about) in your generated IR, so that LLVM can encode them into61your final stack maps. Depending on the collector strategy chosen, this is62accomplished by using either the ``@llvm.gcroot`` intrinsics or a63``gc.statepoint`` relocation sequence.64 65Don't forget to create a root for each intermediate value that is generated when66evaluating an expression. In ``h(f(), g())``, the result of ``f()`` could67easily be collected if evaluating ``g()`` triggers a collection.68 69Finally, you need to link your runtime library with the generated program70executable (for a static compiler) or ensure the appropriate symbols are71available for the runtime linker (for a JIT compiler).72 73 74Introduction75============76 77What is Garbage Collection?78---------------------------79 80Garbage collection is a widely used technique that frees the programmer from81having to know the lifetimes of heap objects, making software easier to produce82and maintain. Many programming languages rely on garbage collection for83automatic memory management. There are two primary forms of garbage collection:84conservative and accurate.85 86Conservative garbage collection often does not require any special support from87either the language or the compiler: it can handle non-type-safe programming88languages (such as C/C++) and does not require any special information from the89compiler. The `Boehm collector90<https://hboehm.info/gc/>`__ is an example of a91state-of-the-art conservative collector.92 93Accurate garbage collection requires the ability to identify all pointers in the94program at run-time (which requires that the source-language be type-safe in95most cases). Identifying pointers at run-time requires compiler support to96locate all places that hold live pointer variables at run-time, including the97:ref:`processor stack and registers <gcroot>`.98 99Conservative garbage collection is attractive because it does not require any100special compiler support, but it does have problems. In particular, because the101conservative garbage collector cannot *know* that a particular word in the102machine is a pointer, it cannot move live objects in the heap (preventing the103use of compacting and generational GC algorithms) and it can occasionally suffer104from memory leaks due to integer values that happen to point to objects in the105program. In addition, some aggressive compiler transformations can break106conservative garbage collectors (though these seem rare in practice).107 108Accurate garbage collectors do not suffer from any of these problems, but they109can suffer from degraded scalar optimization of the program. In particular,110because the runtime must be able to identify and update all pointers active in111the program, some optimizations are less effective. In practice, however, the112locality and performance benefits of using aggressive garbage collection113techniques dominates any low-level losses.114 115This document describes the mechanisms and interfaces provided by LLVM to116support accurate garbage collection.117 118Goals and non-goals119-------------------120 121LLVM's intermediate representation provides :ref:`garbage collection intrinsics122<gc_intrinsics>` that offer support for a broad class of collector models. For123instance, the intrinsics permit:124 125* semi-space collectors126 127* mark-sweep collectors128 129* generational collectors130 131* incremental collectors132 133* concurrent collectors134 135* cooperative collectors136 137* reference counting138 139We hope that the support built into the LLVM IR is sufficient to support a140broad class of garbage collected languages including Scheme, ML, Java, C#,141Perl, Python, Lua, Ruby, other scripting languages, and more.142 143Note that LLVM **does not itself provide a garbage collector** --- this should144be part of your language's runtime library. LLVM provides a framework for145describing the garbage collector's requirements to the compiler. In particular,146LLVM provides support for generating stack maps at call sites, polling for a147safepoint, and emitting load and store barriers. You can also extend LLVM -148possibly through a loadable :ref:`code generation plugins <plugin>` - to149generate code and data structures which conform to the *binary interface*150specified by the *runtime library*. This is similar to the relationship between151LLVM and DWARF debugging info, for example. The difference primarily lies in152the lack of an established standard in the domain of garbage collection --- thus153the need for a flexible extension mechanism.154 155The aspects of the binary interface with which LLVM's GC support is156concerned are:157 158* Creation of GC safepoints within code where collection is allowed to execute159 safely.160 161* Computation of the stack map. For each safe point in the code, object162 references within the stack frame must be identified so that the collector may163 traverse and perhaps update them.164 165* Write barriers when storing object references to the heap. These are commonly166 used to optimize incremental scans in generational collectors.167 168* Emission of read barriers when loading object references. These are useful169 for interoperating with concurrent collectors.170 171There are additional areas that LLVM does not directly address:172 173* Registration of global roots with the runtime.174 175* Registration of stack map entries with the runtime.176 177* The functions used by the program to allocate memory, trigger a collection,178 etc.179 180* Computation or compilation of type maps, or registration of them with the181 runtime. These are used to crawl the heap for object references.182 183In general, LLVM's support for GC does not include features which can be184adequately addressed with other features of the IR and does not specify a185particular binary interface. On the plus side, this means that you should be186able to integrate LLVM with an existing runtime. On the other hand, it can187have the effect of leaving a lot of work for the developer of a novel188language. We try to mitigate this by providing built-in collector strategy189descriptions that can work with many common collector designs and easy190extension points. If you don't already have a specific binary interface191you need to support, we recommend trying to use one of these built-in collector192strategies.193 194.. _gc_intrinsics:195 196LLVM IR Features197================198 199This section describes the garbage collection facilities provided by the200:doc:`LLVM intermediate representation <LangRef>`. The exact behavior of these201IR features is specified by the selected :ref:`GC strategy description202<plugin>`.203 204Specifying GC code generation: ``gc "..."``205-------------------------------------------206 207.. code-block:: text208 209 define <returntype> @name(...) gc "name" { ... }210 211The ``gc`` function attribute is used to specify the desired GC strategy to the212compiler. Its programmatic equivalent is the ``setGC`` method of ``Function``.213 214Setting ``gc "name"`` on a function triggers a search for a matching subclass215of GCStrategy. Some collector strategies are built in. You can add others216using either the loadable plugin mechanism, or by patching your copy of LLVM.217It is the selected GC strategy which defines the exact nature of the code218generated to support GC. If none is found, the compiler will raise an error.219 220Specifying the GC style on a per-function basis allows LLVM to link together221programs that use different garbage collection algorithms (or none at all).222 223.. _gcroot:224 225Identifying GC roots on the stack226----------------------------------227 228LLVM currently supports two different mechanisms for describing references in229compiled code at safepoints. ``llvm.gcroot`` is the older mechanism;230``gc.statepoint`` has been added more recently. At the moment, you can choose231either implementation (on a per :ref:`GC strategy <plugin>` basis). Longer232term, we will probably either migrate away from ``llvm.gcroot`` entirely, or233substantially merge their implementations. Note that most new development234work is focused on ``gc.statepoint``.235 236Using ``gc.statepoint``237^^^^^^^^^^^^^^^^^^^^^^^^238:doc:`This page <Statepoints>` contains detailed documentation for239``gc.statepoint``.240 241Using ``llvm.gcwrite``242^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^243 244.. code-block:: llvm245 246 void @llvm.gcroot(i8** %ptrloc, i8* %metadata)247 248The ``llvm.gcroot`` intrinsic is used to inform LLVM that a stack variable249references an object on the heap and is to be tracked for garbage collection.250The exact impact on generated code is specified by the Function's selected251:ref:`GC strategy <plugin>`. All calls to ``llvm.gcroot`` **must** reside252inside the first basic block.253 254The first argument **must** be a value referring to an alloca instruction or a255bitcast of an alloca. The second contains a pointer to metadata that should be256associated with the pointer, and **must** be a constant or global value257address. If your target collector uses tags, use a null pointer for metadata.258 259A compiler which performs manual SSA construction **must** ensure that SSA260values representing GC references are stored into the alloca passed to the261respective ``gcroot`` before every call site and reloaded after every call.262A compiler which uses mem2reg to raise imperative code using ``alloca`` into263SSA form need only add a call to ``@llvm.gcroot`` for those variables which264are pointers into the GC heap.265 266It is also important to mark intermediate values with ``llvm.gcroot``. For267example, consider ``h(f(), g())``. Beware leaking the result of ``f()`` in the268case that ``g()`` triggers a collection. Note that stack variables must be269initialized and marked with ``llvm.gcroot`` in the function's prologue.270 271The ``%metadata`` argument can be used to avoid requiring heap objects to have272'isa' pointers or tag bits. [Appel89_, Goldberg91_, Tolmach94_] If specified,273its value will be tracked along with the location of the pointer in the stack274frame.275 276Consider the following fragment of Java code:277 278.. code-block:: java279 280 {281 Object X; // A null-initialized reference to an object282 ...283 }284 285This block (which may be located in the middle of a function or in a loop nest),286could be compiled to this LLVM code:287 288.. code-block:: llvm289 290 Entry:291 ;; In the entry block for the function, allocate the292 ;; stack space for X, which is an LLVM pointer.293 %X = alloca %Object*294 295 ;; Tell LLVM that the stack space is a stack root.296 ;; Java has type-tags on objects, so we pass null as metadata.297 %tmp = bitcast %Object** %X to i8**298 call void @llvm.gcroot(i8** %tmp, i8* null)299 ...300 301 ;; "CodeBlock" is the block corresponding to the start302 ;; of the scope above.303 CodeBlock:304 ;; Java null-initializes pointers.305 store %Object* null, %Object** %X306 307 ...308 309 ;; As the pointer goes out of scope, store a null value into310 ;; it, to indicate that the value is no longer live.311 store %Object* null, %Object** %X312 ...313 314Reading and writing references in the heap315------------------------------------------316 317Some collectors need to be informed when the mutator (the program that needs318garbage collection) either reads a pointer from or writes a pointer to a field319of a heap object. The code fragments inserted at these points are called *read320barriers* and *write barriers*, respectively. The amount of code that needs to321be executed is usually quite small and not on the critical path of any322computation, so the overall performance impact of the barrier is tolerable.323 324Barriers often require access to the *object pointer* rather than the *derived325pointer* (which is a pointer to the field within the object). Accordingly,326these intrinsics take both pointers as separate arguments for completeness. In327this snippet, ``%object`` is the object pointer, and ``%derived`` is the derived328pointer:329 330.. code-block:: llvm331 332 ;; An array type.333 %class.Array = type { %class.Object, i32, [0 x %class.Object*] }334 ...335 336 ;; Load the object pointer from a gcroot.337 %object = load %class.Array** %object_addr338 339 ;; Compute the derived pointer.340 %derived = getelementptr %object, i32 0, i32 2, i32 %n341 342LLVM does not enforce this relationship between the object and derived pointer343(although a particular :ref:`collector strategy <plugin>` might). However, it344would be an unusual collector that violated it.345 346The use of these intrinsics is naturally optional if the target GC does not347require the corresponding barrier. The GC strategy used with such a collector348should replace the intrinsic calls with the corresponding ``load`` or349``store`` instruction if they are used.350 351One known deficiency with the current design is that the barrier intrinsics do352not include the size or alignment of the underlying operation performed. It is353currently assumed that the operation is of pointer size and the alignment is354assumed to be the target machine's default alignment.355 356Write barrier: ``llvm.gcwrite``357^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^358 359.. code-block:: llvm360 361 void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)362 363For write barriers, LLVM provides the ``llvm.gcwrite`` intrinsic function. It364has exactly the same semantics as a non-volatile ``store`` to the derived365pointer (the third argument). The exact code generated is specified by the366Function's selected :ref:`GC strategy <plugin>`.367 368Many important algorithms require write barriers, including generational and369concurrent collectors. Additionally, write barriers could be used to implement370reference counting.371 372Read barrier: ``llvm.gcread``373^^^^^^^^^^^^^^^^^^^^^^^^^^^^^374 375.. code-block:: llvm376 377 i8* @llvm.gcread(i8* %object, i8** %derived)378 379For read barriers, LLVM provides the ``llvm.gcread`` intrinsic function. It has380exactly the same semantics as a non-volatile ``load`` from the derived pointer381(the second argument). The exact code generated is specified by the Function's382selected :ref:`GC strategy <plugin>`.383 384Read barriers are needed by fewer algorithms than write barriers, and may have a385greater performance impact since pointer reads are more frequent than writes.386 387.. _plugin:388 389.. _builtin-gc-strategies:390 391Built-In GC Strategies392======================393 394LLVM includes built-in support for several varieties of garbage collectors.395 396The Shadow Stack GC397----------------------398 399To use this collector strategy, mark your functions with:400 401.. code-block:: c++402 403 F.setGC("shadow-stack");404 405Unlike many GC algorithms which rely on a cooperative code generator to compile406stack maps, this algorithm carefully maintains a linked list of stack roots407[:ref:`Henderson2002 <henderson02>`]. This so-called "shadow stack" mirrors the408machine stack. Maintaining this data structure is slower than using a stack map409compiled into the executable as constant data, but has a significant portability410advantage because it requires no special support from the target code generator,411and does not require tricky platform-specific code to crawl the machine stack.412 413The tradeoff for this simplicity and portability is:414 415* High overhead per function call.416 417* Not thread-safe.418 419Still, it's an easy way to get started. After your compiler and runtime are up420and running, writing a :ref:`plugin <plugin>` will allow you to take advantage421of :ref:`more advanced GC features <collector-algos>` of LLVM in order to422improve performance.423 424 425The shadow stack doesn't imply a memory allocation algorithm. A semispace426collector or building atop ``malloc`` are great places to start, and can be427implemented with very little code.428 429When it comes time to collect, however, your runtime needs to traverse the stack430roots, and for this it needs to integrate with the shadow stack. Luckily, doing431so is very simple. (This code is heavily commented to help you understand the432data structure, but there are only 20 lines of meaningful code.)433 434.. code-block:: c++435 436 /// The map for a single function's stack frame. One of these is437 /// compiled as constant data into the executable for each function.438 ///439 /// Storage of metadata values is elided if the %metadata parameter to440 /// @llvm.gcroot is null.441 struct FrameMap {442 int32_t NumRoots; //< Number of roots in stack frame.443 int32_t NumMeta; //< Number of metadata entries. May be < NumRoots.444 const void *Meta[0]; //< Metadata for each root.445 };446 447 /// A link in the dynamic shadow stack. One of these is embedded in448 /// the stack frame of each function on the call stack.449 struct StackEntry {450 StackEntry *Next; //< Link to next stack entry (the caller's).451 const FrameMap *Map; //< Pointer to constant FrameMap.452 void *Roots[0]; //< Stack roots (in-place array).453 };454 455 /// The head of the singly-linked list of StackEntries. Functions push456 /// and pop onto this in their prologue and epilogue.457 ///458 /// Since there is only a global list, this technique is not threadsafe.459 StackEntry *llvm_gc_root_chain;460 461 /// Calls Visitor(root, meta) for each GC root on the stack.462 /// root and meta are exactly the values passed to463 /// @llvm.gcroot.464 ///465 /// Visitor could be a function to recursively mark live objects. Or it466 /// might copy them to another heap or generation.467 ///468 /// @param Visitor A function to invoke for every GC root on the stack.469 void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {470 for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {471 unsigned i = 0;472 473 // For roots [0, NumMeta), the metadata pointer is in the FrameMap.474 for (unsigned e = R->Map->NumMeta; i != e; ++i)475 Visitor(&R->Roots[i], R->Map->Meta[i]);476 477 // For roots [NumMeta, NumRoots), the metadata pointer is null.478 for (unsigned e = R->Map->NumRoots; i != e; ++i)479 Visitor(&R->Roots[i], NULL);480 }481 }482 483 484The 'Erlang' and 'OCaml' GCs485-----------------------------486 487LLVM ships with two example collectors which leverage the ``gcroot``488mechanisms. To our knowledge, these are not actually used by any language489runtime, but they do provide a reasonable starting point for someone interested490in writing a ``gcroot`` compatible GC plugin. In particular, these are the491only in-tree examples of how to produce a custom binary stack map format using492a ``gcroot`` strategy.493 494As their names imply, the binary format produced is intended to model that495used by the Erlang and OCaml compilers respectively.496 497.. _statepoint_example_gc:498 499The Statepoint Example GC500-------------------------501 502.. code-block:: c++503 504 F.setGC("statepoint-example");505 506This GC provides an example of how one might use the infrastructure provided507by ``gc.statepoint``. This example GC is compatible with the508:ref:`PlaceSafepoints` and :ref:`RewriteStatepointsForGC` utility passes509which simplify ``gc.statepoint`` sequence insertion. If you need to build a510custom GC strategy around the ``gc.statepoints`` mechanisms, it is recommended511that you use this one as a starting point.512 513This GC strategy does not support read or write barriers. As a result, these514intrinsics are lowered to normal loads and stores.515 516The stack map format generated by this GC strategy can be found in the517:ref:`stackmap-section` using a format documented :ref:`here518<statepoint-stackmap-format>`. This format is intended to be the standard519format supported by LLVM going forward.520 521The CoreCLR GC522-------------------------523 524.. code-block:: c++525 526 F.setGC("coreclr");527 528This GC leverages the ``gc.statepoint`` mechanism to support the529`CoreCLR <https://github.com/dotnet/coreclr>`__ runtime.530 531Support for this GC strategy is a work in progress. This strategy will532differ from533:ref:`statepoint-example GC<statepoint_example_gc>` strategy in534certain aspects like:535 536* Base-pointers of interior pointers are not explicitly537 tracked and reported.538 539* A different format is used for encoding stack maps.540 541* Safe-point polls are only needed before loop-back edges542 and before tail-calls (not needed at function-entry).543 544Custom GC Strategies545====================546 547If none of the built-in GC strategy descriptions met your needs above, you will548need to define a custom GCStrategy and possibly, a custom LLVM pass to perform549lowering. Your best example of where to start defining a custom GCStrategy550would be to look at one of the built-in strategies.551 552You may be able to structure this additional code as a loadable plugin library.553Loadable plugins are sufficient if all you need is to enable a different554combination of built-in functionality, but if you need to provide a custom555lowering pass, you will need to build a patched version of LLVM. If you think556you need a patched build, please ask for advice on llvm-dev. There may be an557easy way we can extend the support to make it work for your use case without558requiring a custom build.559 560Collector Requirements561----------------------562 563You should be able to leverage any existing collector library that includes the following elements:564 565#. A memory allocator which exposes an allocation function your compiled566 code can call.567 568#. A binary format for the stack map. A stack map describes the location569 of references at a safepoint and is used by precise collectors to identify570 references within a stack frame on the machine stack. Note that collectors571 which conservatively scan the stack don't require such a structure.572 573#. A stack crawler to discover functions on the call stack, and enumerate the574 references listed in the stack map for each call site.575 576#. A mechanism for identifying references in global locations (e.g. global577 variables).578 579#. If your collector requires them, an LLVM IR implementation of your collector's580 load and store barriers. Note that since many collectors don't require581 barriers at all, LLVM defaults to lowering such barriers to normal loads582 and stores unless you arrange otherwise.583 584 585Implementing a collector plugin586-------------------------------587 588User code specifies which GC code generation to use with the ``gc`` function589attribute or, equivalently, with the ``setGC`` method of ``Function``.590 591To implement a GC plugin, it is necessary to subclass ``llvm::GCStrategy``,592which can be accomplished in a few lines of boilerplate code. LLVM's593infrastructure provides access to several important algorithms. For an594uncontroversial collector, all that remains may be to compile LLVM's computed595stack map to assembly code (using the binary representation expected by the596runtime library). This can be accomplished in about 100 lines of code.597 598This is not the appropriate place to implement a garbage collected heap or a599garbage collector itself. That code should exist in the language's runtime600library. The compiler plugin is responsible for generating code which conforms601to the binary interface defined by the library, most essentially the :ref:`stack map602<stack-map>`.603 604To subclass ``llvm::GCStrategy`` and register it with the compiler:605 606.. code-block:: c++607 608 // lib/MyGC/MyGC.cpp - Example LLVM GC plugin609 610 #include "llvm/CodeGen/GCStrategy.h"611 #include "llvm/CodeGen/GCMetadata.h"612 #include "llvm/Support/Compiler.h"613 614 using namespace llvm;615 616 namespace {617 class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy {618 public:619 MyGC() {}620 };621 622 GCRegistry::Add<MyGC>623 X("mygc", "My bespoke garbage collector.");624 }625 626This boilerplate collector does nothing. More specifically:627 628* ``llvm.gcread`` calls are replaced with the corresponding ``load``629 instruction.630 631* ``llvm.gcwrite`` calls are replaced with the corresponding ``store``632 instruction.633 634* No safe points are added to the code.635 636* The stack map is not compiled into the executable.637 638Using the LLVM makefiles, this code639can be compiled as a plugin using a simple makefile:640 641.. code-block:: make642 643 # lib/MyGC/Makefile644 645 LEVEL := ../..646 LIBRARYNAME = MyGC647 LOADABLE_MODULE = 1648 649 include $(LEVEL)/Makefile.common650 651Once the plugin is compiled, code using it may be compiled using ``llc652-load=MyGC.so`` (though MyGC.so may have some other platform-specific653extension):654 655::656 657 $ cat sample.ll658 define void @f() gc "mygc" {659 entry:660 ret void661 }662 $ llvm-as < sample.ll | llc -load=MyGC.so663 664It is also possible to statically link the collector plugin into tools, such as665a language-specific compiler front-end.666 667.. _collector-algos:668 669Overview of available features670------------------------------671 672``GCStrategy`` provides a range of features through which a plugin may do useful673work. Some of these are callbacks, some are algorithms that can be enabled,674disabled, or customized. This matrix summarizes the supported (and planned)675features and correlates them with the collection techniques which typically676require them.677 678.. |v| unicode:: 0x2714679 :trim:680 681.. |x| unicode:: 0x2718682 :trim:683 684+------------+------+--------+----------+-------+---------+-------------+----------+------------+685| Algorithm | Done | Shadow | refcount | mark- | copying | incremental | threaded | concurrent |686| | | stack | | sweep | | | | |687+============+======+========+==========+=======+=========+=============+==========+============+688| stack map | |v| | | | |x| | |x| | |x| | |x| | |x| |689+------------+------+--------+----------+-------+---------+-------------+----------+------------+690| initialize | |v| | |x| | |x| | |x| | |x| | |x| | |x| | |x| |691| roots | | | | | | | | |692+------------+------+--------+----------+-------+---------+-------------+----------+------------+693| derived | NO | | | | | | **N**\* | **N**\* |694| pointers | | | | | | | | |695+------------+------+--------+----------+-------+---------+-------------+----------+------------+696| **custom | |v| | | | | | | | |697| lowering** | | | | | | | | |698+------------+------+--------+----------+-------+---------+-------------+----------+------------+699| *gcroot* | |v| | |x| | |x| | | | | | |700+------------+------+--------+----------+-------+---------+-------------+----------+------------+701| *gcwrite* | |v| | | |x| | | | |x| | | |x| |702+------------+------+--------+----------+-------+---------+-------------+----------+------------+703| *gcread* | |v| | | | | | | | |x| |704+------------+------+--------+----------+-------+---------+-------------+----------+------------+705| **safe | | | | | | | | |706| points** | | | | | | | | |707+------------+------+--------+----------+-------+---------+-------------+----------+------------+708| *in | |v| | | | |x| | |x| | |x| | |x| | |x| |709| calls* | | | | | | | | |710+------------+------+--------+----------+-------+---------+-------------+----------+------------+711| *before | |v| | | | | | | |x| | |x| |712| calls* | | | | | | | | |713+------------+------+--------+----------+-------+---------+-------------+----------+------------+714| *for | NO | | | | | | **N** | **N** |715| loops* | | | | | | | | |716+------------+------+--------+----------+-------+---------+-------------+----------+------------+717| *before | |v| | | | | | | |x| | |x| |718| escape* | | | | | | | | |719+------------+------+--------+----------+-------+---------+-------------+----------+------------+720| emit code | NO | | | | | | **N** | **N** |721| at safe | | | | | | | | |722| points | | | | | | | | |723+------------+------+--------+----------+-------+---------+-------------+----------+------------+724| **output** | | | | | | | | |725+------------+------+--------+----------+-------+---------+-------------+----------+------------+726| *assembly* | |v| | | | |x| | |x| | |x| | |x| | |x| |727+------------+------+--------+----------+-------+---------+-------------+----------+------------+728| *JIT* | NO | | | **?** | **?** | **?** | **?** | **?** |729+------------+------+--------+----------+-------+---------+-------------+----------+------------+730| *obj* | NO | | | **?** | **?** | **?** | **?** | **?** |731+------------+------+--------+----------+-------+---------+-------------+----------+------------+732| live | NO | | | **?** | **?** | **?** | **?** | **?** |733| analysis | | | | | | | | |734+------------+------+--------+----------+-------+---------+-------------+----------+------------+735| register | NO | | | **?** | **?** | **?** | **?** | **?** |736| map | | | | | | | | |737+------------+------+--------+----------+-------+---------+-------------+----------+------------+738| \* Derived pointers only pose a hazard to copying collections. |739+------------+------+--------+----------+-------+---------+-------------+----------+------------+740| **?** denotes a feature which could be utilized if available. |741+------------+------+--------+----------+-------+---------+-------------+----------+------------+742 743To be clear, the collection techniques above are defined as:744 745Shadow Stack746 The mutator carefully maintains a linked list of stack roots.747 748Reference Counting749 The mutator maintains a reference count for each object and frees an object750 when its count falls to zero.751 752Mark-Sweep753 When the heap is exhausted, the collector marks reachable objects starting754 from the roots, then deallocates unreachable objects in a sweep phase.755 756Copying757 As reachability analysis proceeds, the collector copies objects from one heap758 area to another, compacting them in the process. Copying collectors enable759 highly efficient "bump pointer" allocation and can improve locality of760 reference.761 762Incremental763 (Including generational collectors.) Incremental collectors generally have all764 the properties of a copying collector (regardless of whether the mature heap765 is compacting), but bring the added complexity of requiring write barriers.766 767Threaded768 Denotes a multithreaded mutator; the collector must still stop the mutator769 ("stop the world") before beginning reachability analysis. Stopping a770 multithreaded mutator is a complicated problem. It generally requires highly771 platform-specific code in the runtime, and the production of carefully772 designed machine code at safe points.773 774Concurrent775 In this technique, the mutator and the collector run concurrently, with the776 goal of eliminating pause times. In a *cooperative* collector, the mutator777 further aids with collection should a pause occur, allowing collection to take778 advantage of multiprocessor hosts. The "stop the world" problem of threaded779 collectors is generally still present to a limited extent. Sophisticated780 marking algorithms are necessary. Read barriers may be necessary.781 782As the matrix indicates, LLVM's garbage collection infrastructure is already783suitable for a wide variety of collectors, but does not currently extend to784multithreaded programs. This will be added in the future as there is785interest.786 787.. _stack-map:788 789Computing stack maps790--------------------791 792LLVM automatically computes a stack map. One of the most important features793of a ``GCStrategy`` is to compile this information into the executable in794the binary representation expected by the runtime library.795 796The stack map consists of the location and identity of each GC root in the797each function in the module. For each root:798 799* ``RootNum``: The index of the root.800 801* ``StackOffset``: The offset of the object relative to the frame pointer.802 803* ``RootMetadata``: The value passed as the ``%metadata`` parameter to the804 ``@llvm.gcroot`` intrinsic.805 806Also, for the function as a whole:807 808* ``getFrameSize()``: The overall size of the function's initial stack frame,809 not accounting for any dynamic allocation.810 811* ``roots_size()``: The count of roots in the function.812 813To access the stack map, use ``GCFunctionMetadata::roots_begin()`` and814-``end()`` from the :ref:`GCMetadataPrinter <assembly>`:815 816.. code-block:: c++817 818 for (iterator I = begin(), E = end(); I != E; ++I) {819 GCFunctionInfo *FI = *I;820 unsigned FrameSize = FI->getFrameSize();821 size_t RootCount = FI->roots_size();822 823 for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(),824 RE = FI->roots_end();825 RI != RE; ++RI) {826 int RootNum = RI->Num;827 int RootStackOffset = RI->StackOffset;828 Constant *RootMetadata = RI->Metadata;829 }830 }831 832If the ``llvm.gcroot`` intrinsic is eliminated before code generation by a833custom lowering pass, LLVM will compute an empty stack map. This may be useful834for collector plugins which implement reference counting or a shadow stack.835 836.. _init-roots:837 838Initializing roots to null839---------------------------840 841It is recommended that frontends initialize roots explicitly to avoid842potentially confusing the optimizer. This prevents the GC from visiting843uninitialized pointers, which will almost certainly cause it to crash.844 845As a fallback, LLVM will automatically initialize each root to ``null``846upon entry to the function. Support for this mode in code generation is847largely a legacy detail to keep old collector implementations working.848 849Custom lowering of intrinsics850------------------------------851 852For GCs which use barriers or unusual treatment of stack roots, the853implementor is responsible for providing a custom pass to lower the854intrinsics with the desired semantics. If you have opted in to custom855lowering of a particular intrinsic your pass **must** eliminate all856instances of the corresponding intrinsic in functions which opt in to857your GC. The best example of such a pass is the ShadowStackGC and its858ShadowStackGCLowering pass.859 860There is currently no way to register such a custom lowering pass861without building a custom copy of LLVM.862 863.. _safe-points:864 865Generating safe points866-----------------------867 868LLVM provides support for associating stackmaps with the return address of869a call. Any loop or return safepoints required by a given collector design870can be modeled via calls to runtime routines, or potentially patchable call871sequences. Using gcroot, all call instructions are inferred to be possible872safepoints and will thus have an associated stackmap.873 874.. _assembly:875 876Emitting assembly code: ``GCMetadataPrinter``877---------------------------------------------878 879LLVM allows a plugin to print arbitrary assembly code before and after the rest880of a module's assembly code. At the end of the module, the GC can compile the881LLVM stack map into assembly code. (At the beginning, this information is not882yet computed.)883 884Since AsmWriter and CodeGen are separate components of LLVM, a separate abstract885base class and registry is provided for printing assembly code, the886``GCMetadaPrinter`` and ``GCMetadataPrinterRegistry``. The AsmWriter will look887for such a subclass if the ``GCStrategy`` sets ``UsesMetadata``:888 889.. code-block:: c++890 891 MyGC::MyGC() {892 UsesMetadata = true;893 }894 895This separation allows JIT-only clients to be smaller.896 897Note that LLVM does not currently have analogous APIs to support code generation898in the JIT, nor using the object writers.899 900.. code-block:: c++901 902 // lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer903 904 #include "llvm/CodeGen/GCMetadataPrinter.h"905 #include "llvm/Support/Compiler.h"906 907 using namespace llvm;908 909 namespace {910 class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter {911 public:912 virtual void beginAssembly(AsmPrinter &AP);913 914 virtual void finishAssembly(AsmPrinter &AP);915 };916 917 GCMetadataPrinterRegistry::Add<MyGCPrinter>918 X("mygc", "My bespoke garbage collector.");919 }920 921The collector should use ``AsmPrinter`` to print portable assembly code. The922collector itself contains the stack map for the entire module, and may access923the ``GCFunctionInfo`` using its own ``begin()`` and ``end()`` methods. Here's924a realistic example:925 926.. code-block:: c++927 928 #include "llvm/CodeGen/AsmPrinter.h"929 #include "llvm/IR/Function.h"930 #include "llvm/IR/DataLayout.h"931 #include "llvm/Target/TargetAsmInfo.h"932 #include "llvm/Target/TargetMachine.h"933 934 void MyGCPrinter::beginAssembly(AsmPrinter &AP) {935 // Nothing to do.936 }937 938 void MyGCPrinter::finishAssembly(AsmPrinter &AP) {939 MCStreamer &OS = AP.OutStreamer;940 unsigned IntPtrSize = AP.getPointerSize();941 942 // Put this in the data section.943 OS.switchSection(AP.getObjFileLowering().getDataSection());944 945 // For each function...946 for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {947 GCFunctionInfo &MD = **FI;948 949 // A compact GC layout. Emit this data structure:950 //951 // struct {952 // int32_t PointCount;953 // void *SafePointAddress[PointCount];954 // int32_t StackFrameSize; // in words955 // int32_t StackArity;956 // int32_t LiveCount;957 // int32_t LiveOffsets[LiveCount];958 // } __gcmap_<FUNCTIONNAME>;959 960 // Align to address width.961 AP.emitAlignment(IntPtrSize == 4 ? 2 : 3);962 963 // Emit PointCount.964 OS.AddComment("safe point count");965 AP.emitInt32(MD.size());966 967 // And each safe point...968 for (GCFunctionInfo::iterator PI = MD.begin(),969 PE = MD.end(); PI != PE; ++PI) {970 // Emit the address of the safe point.971 OS.AddComment("safe point address");972 MCSymbol *Label = PI->Label;973 AP.emitLabelPlusOffset(Label/*Hi*/, 0/*Offset*/, 4/*Size*/);974 }975 976 // Stack information never change in safe points! Only print info from the977 // first call-site.978 GCFunctionInfo::iterator PI = MD.begin();979 980 // Emit the stack frame size.981 OS.AddComment("stack frame size (in words)");982 AP.emitInt32(MD.getFrameSize() / IntPtrSize);983 984 // Emit stack arity, i.e. the number of stacked arguments.985 unsigned RegisteredArgs = IntPtrSize == 4 ? 5 : 6;986 unsigned StackArity = MD.getFunction().arg_size() > RegisteredArgs ?987 MD.getFunction().arg_size() - RegisteredArgs : 0;988 OS.AddComment("stack arity");989 AP.emitInt32(StackArity);990 991 // Emit the number of live roots in the function.992 OS.AddComment("live root count");993 AP.emitInt32(MD.live_size(PI));994 995 // And for each live root...996 for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),997 LE = MD.live_end(PI);998 LI != LE; ++LI) {999 // Emit live root's offset within the stack frame.1000 OS.AddComment("stack index (offset / wordsize)");1001 AP.emitInt32(LI->StackOffset);1002 }1003 }1004 }1005 1006References1007==========1008 1009.. _appel89:1010 1011[Appel89] Runtime Tags Aren't Necessary. Andrew W. Appel. Lisp and Symbolic1012Computation 19(7):703-705, July 1989.1013 1014.. _goldberg91:1015 1016[Goldberg91] Tag-free garbage collection for strongly typed programming1017languages. Benjamin Goldberg. ACM SIGPLAN PLDI'91.1018 1019.. _tolmach94:1020 1021[Tolmach94] Tag-free garbage collection using explicit type parameters. Andrew1022Tolmach. Proceedings of the 1994 ACM conference on LISP and functional1023programming.1024 1025.. _henderson02:1026 1027[Henderson2002] `Accurate Garbage Collection in an Uncooperative Environment1028<http://citeseer.ist.psu.edu/henderson02accurate.html>`__1029