diff options
Diffstat (limited to 'docs/GarbageCollection.html')
| -rw-r--r-- | docs/GarbageCollection.html | 1387 |
1 files changed, 1387 insertions, 0 deletions
diff --git a/docs/GarbageCollection.html b/docs/GarbageCollection.html new file mode 100644 index 0000000000..d0b651eb64 --- /dev/null +++ b/docs/GarbageCollection.html @@ -0,0 +1,1387 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" + "http://www.w3.org/TR/html4/strict.dtd"> +<html> +<head> + <meta http-equiv="Content-Type" Content="text/html; charset=UTF-8" > + <title>Accurate Garbage Collection with LLVM</title> + <link rel="stylesheet" href="llvm.css" type="text/css"> + <style type="text/css"> + .rowhead { text-align: left; background: inherit; } + .indent { padding-left: 1em; } + .optl { color: #BFBFBF; } + </style> +</head> +<body> + +<div class="doc_title"> + Accurate Garbage Collection with LLVM +</div> + +<ol> + <li><a href="#introduction">Introduction</a> + <ul> + <li><a href="#feature">Goals and non-goals</a></li> + </ul> + </li> + + <li><a href="#quickstart">Getting started</a> + <ul> + <li><a href="#quickstart-compiler">In your compiler</a></li> + <li><a href="#quickstart-runtime">In your runtime library</a></li> + <li><a href="#shadow-stack">About the shadow stack</a></li> + </ul> + </li> + + <li><a href="#core">Core support</a> + <ul> + <li><a href="#gcattr">Specifying GC code generation: + <tt>gc "..."</tt></a></li> + <li><a href="#gcroot">Identifying GC roots on the stack: + <tt>llvm.gcroot</tt></a></li> + <li><a href="#barriers">Reading and writing references in the heap</a> + <ul> + <li><a href="#gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a></li> + <li><a href="#gcread">Read barrier: <tt>llvm.gcread</tt></a></li> + </ul> + </li> + </ul> + </li> + + <li><a href="#plugin">Compiler plugin interface</a> + <ul> + <li><a href="#collector-algos">Overview of available features</a></li> + <li><a href="#stack-map">Computing stack maps</a></li> + <li><a href="#init-roots">Initializing roots to null: + <tt>InitRoots</tt></a></li> + <li><a href="#custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, + <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a></li> + <li><a href="#safe-points">Generating safe points: + <tt>NeededSafePoints</tt></a></li> + <li><a href="#assembly">Emitting assembly code: + <tt>GCMetadataPrinter</tt></a></li> + </ul> + </li> + + <li><a href="#runtime-impl">Implementing a collector runtime</a> + <ul> + <li><a href="#gcdescriptors">Tracing GC pointers from heap + objects</a></li> + </ul> + </li> + + <li><a href="#references">References</a></li> + +</ol> + +<div class="doc_author"> + <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and + Gordon Henriksen</p> +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="introduction">Introduction</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>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.</p> + +<p>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 +<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is +an example of a state-of-the-art conservative collector.</p> + +<p>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 +<a href="#gcroot">processor stack and registers</a>.</p> + +<p>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 <i>know</i> 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).</p> + +<p>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.</p> + +<p>This document describes the mechanisms and interfaces provided by LLVM to +support accurate garbage collection.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="feature">Goals and non-goals</a> +</div> + +<div class="doc_text"> + +<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage +collection intrinsics</a> that offer support for a broad class of +collector models. For instance, the intrinsics permit:</p> + +<ul> + <li>semi-space collectors</li> + <li>mark-sweep collectors</li> + <li>generational collectors</li> + <li>reference counting</li> + <li>incremental collectors</li> + <li>concurrent collectors</li> + <li>cooperative collectors</li> +</ul> + +<p>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.</p> + +<p>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 <a href="#plugin">code generation plugins</a>. The role of these +plugins is to generate code and data structures which conforms to the <em>binary +interface</em> specified by the <em>runtime library</em>. 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.</p> + +<p>The aspects of the binary interface with which LLVM's GC support is +concerned are:</p> + +<ul> + <li>Creation of GC-safe points within code where collection is allowed to + execute safely.</li> + <li>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.</li> + <li>Write barriers when storing object references to the heap. These are + commonly used to optimize incremental scans in generational + collectors.</li> + <li>Emission of read barriers when loading object references. These are + useful for interoperating with concurrent collectors.</li> +</ul> + +<p>There are additional areas that LLVM does not directly address:</p> + +<ul> + <li>Registration of global roots with the runtime.</li> + <li>Registration of stack map entries with the runtime.</li> + <li>The functions used by the program to allocate memory, trigger a + collection, etc.</li> + <li>Computation or compilation of type maps, or registration of them with + the runtime. These are used to crawl the heap for object + references.</li> +</ul> + +<p>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.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="quickstart">Getting started</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>Using a GC with LLVM implies many things, for example:</p> + +<ul> + <li>Write a runtime library or find an existing one which implements a GC + heap.<ol> + <li>Implement a memory allocator.</li> + <li>Design a binary interface for the stack map, used to identify + references within a stack frame on the machine stack.*</li> + <li>Implement a stack crawler to discover functions on the call stack.*</li> + <li>Implement a registry for global roots.</li> + <li>Design a binary interface for type maps, used to identify references + within heap objects.</li> + <li>Implement a collection routine bringing together all of the above.</li> + </ol></li> + <li>Emit compatible code from your compiler.<ul> + <li>Initialization in the main function.</li> + <li>Use the <tt>gc "..."</tt> attribute to enable GC code generation + (or <tt>F.setGC("...")</tt>).</li> + <li>Use <tt>@llvm.gcroot</tt> to mark stack roots.</li> + <li>Use <tt>@llvm.gcread</tt> and/or <tt>@llvm.gcwrite</tt> to + manipulate GC references, if necessary.</li> + <li>Allocate memory using the GC allocation routine provided by the + runtime library.</li> + <li>Generate type maps according to your runtime's binary interface.</li> + </ul></li> + <li>Write a compiler plugin to interface LLVM with the runtime library.*<ul> + <li>Lower <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> to appropriate + code sequences.*</li> + <li>Compile LLVM's stack map to the binary form expected by the + runtime.</li> + </ul></li> + <li>Load the plugin into the compiler. Use <tt>llc -load</tt> or link the + plugin statically with your language's compiler.*</li> + <li>Link program executables with the runtime.</li> +</ul> + +<p>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 <tt>llc</tt> and works even with the interpreter and C backends.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="quickstart-compiler">In your compiler</a> +</div> + +<div class="doc_text"> + +<p>To turn the shadow stack on for your functions, first call:</p> + +<div class="doc_code"><pre +>F.setGC("shadow-stack");</pre></div> + +<p>for each function your compiler emits. Since the shadow stack is built into +LLVM, you do not need to load a plugin.</p> + +<p>Your compiler must also use <tt>@llvm.gcroot</tt> as documented. +Don't forget to create a root for each intermediate value that is generated +when evaluating an expression. In <tt>h(f(), g())</tt>, the result of +<tt>f()</tt> could easily be collected if evaluating <tt>g()</tt> triggers a +collection.</p> + +<p>There's no need to use <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> over +plain <tt>load</tt> and <tt>store</tt> for now. You will need them when +switching to a more advanced GC.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="quickstart-runtime">In your runtime</a> +</div> + +<div class="doc_text"> + +<p>The shadow stack doesn't imply a memory allocation algorithm. A semispace +collector or building atop <tt>malloc</tt> are great places to start, and can +be implemented with very little code.</p> + +<p>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.)</p> + +</div> + +<div class="doc_code"><pre +>/// @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 +/// <tt>@llvm.gcroot</tt>. +/// +/// 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); + } +}</pre></div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="shadow-stack">About the shadow stack</a> +</div> + +<div class="doc_text"> + +<p>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 [<a href="#henderson02">Henderson2002</a>]. 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.</p> + +<p>The tradeoff for this simplicity and portability is:</p> + +<ul> + <li>High overhead per function call.</li> + <li>Not thread-safe.</li> +</ul> + +<p>Still, it's an easy way to get started. After your compiler and runtime are +up and running, writing a <a href="#plugin">plugin</a> will allow you to take +advantage of <a href="#collector-algos">more advanced GC features</a> of LLVM +in order to improve performance.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="core">IR features</a><a name="intrinsics"></a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>This section describes the garbage collection facilities provided by the +<a href="LangRef.html">LLVM intermediate representation</a>. The exact behavior +of these IR features is specified by the binary interface implemented by a +<a href="#plugin">code generation plugin</a>, not by this document.</p> + +<p>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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a> +</div> + +<div class="doc_code"><tt> + define <i>ty</i> @<i>name</i>(...) <span style="text-decoration: underline">gc "<i>name</i>"</span> { ... +</tt></div> + +<div class="doc_text"> + +<p>The <tt>gc</tt> function attribute is used to specify the desired GC style +to the compiler. Its programmatic equivalent is the <tt>setGC</tt> method of +<tt>Function</tt>.</p> + +<p>Setting <tt>gc "<i>name</i>"</tt> on a function triggers a search for a +matching code generation plugin "<i>name</i>"; 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.</p> + +<p>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).</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a> +</div> + +<div class="doc_code"><tt> + void @llvm.gcroot(i8** %ptrloc, i8* %metadata) +</tt></div> + +<div class="doc_text"> + +<p>The <tt>llvm.gcroot</tt> 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 <a +href="#plugin">compiler plugin</a>.</p> + +<p>A compiler which uses mem2reg to raise imperative code using <tt>alloca</tt> +into SSA form need only add a call to <tt>@llvm.gcroot</tt> for those variables +which a pointers into the GC heap.</p> + +<p>It is also important to mark intermediate values with <tt>llvm.gcroot</tt>. +For example, consider <tt>h(f(), g())</tt>. Beware leaking the result of +<tt>f()</tt> in the case that <tt>g()</tt> triggers a collection.</p> + +<p>The first argument <b>must</b> 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 <b>must</b> be a constant or global +value address. If your target collector uses tags, use a null pointer for +metadata.</p> + +<p>The <tt>%metadata</tt> argument can be used to avoid requiring heap objects +to have 'isa' pointers or tag bits. [<a href="#appel89">Appel89</a>, <a +href="#goldberg91">Goldberg91</a>, <a href="#tolmach94">Tolmach94</a>] If +specified, its value will be tracked along with the location of the pointer in +the stack frame.</p> + +<p>Consider the following fragment of Java code:</p> + +<pre> + { + Object X; // A null-initialized reference to an object + ... + } +</pre> + +<p>This block (which may be located in the middle of a function or in a loop +nest), could be compiled to this LLVM code:</p> + +<pre> +Entry: + ;; In the entry block for the function, allocate the + ;; stack space for X, which is an LLVM pointer. + %X = alloca %Object* + + ;; Tell LLVM that the stack space is a stack root. + ;; Java has type-tags on objects, so we pass null as metadata. + %tmp = bitcast %Object** %X to i8** + call void @llvm.gcroot(i8** %X, i8* null) + ... + + ;; "CodeBlock" is the block corresponding to the start + ;; of the scope above. +CodeBlock: + ;; Java null-initializes pointers. + store %Object* null, %Object** %X + + ... + + ;; As the pointer goes out of scope, store a null value into + ;; it, to indicate that the value is no longer live. + store %Object* null, %Object** %X + ... +</pre> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="barriers">Reading and writing references in the heap</a> +</div> + +<div class="doc_text"> + +<p>Some collectors need to be informed when the mutator (the program that needs +garbage collection) either reads a pointer from or writes a pointer to a field +of a heap object. The code fragments inserted at these points are called +<em>read barriers</em> and <em>write barriers</em>, respectively. The amount of +code that needs to be executed is usually quite small and not on the critical +path of any computation, so the overall performance impact of the barrier is +tolerable.</p> + +<p>Barriers often require access to the <em>object pointer</em> rather than the +<em>derived pointer</em> (which is a pointer to the field within the +object). Accordingly, these intrinsics take both pointers as separate arguments +for completeness. In this snippet, <tt>%object</tt> is the object pointer, and +<tt>%derived</tt> is the derived pointer:</p> + +<blockquote><pre> + ;; An array type. + %class.Array = type { %class.Object, i32, [0 x %class.Object*] } + ... + + ;; Load the object pointer from a gcroot. + %object = load %class.Array** %object_addr + + ;; Compute the derived pointer. + %derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote> + +<p>LLVM does not enforce this relationship between the object and derived +pointer (although a <a href="#plugin">plugin</a> might). However, it would be +an unusual collector that violated it.</p> + +<p>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 <tt>load</tt> or <tt>store</tt> instruction if they +are used.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsubsection"> + <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a> +</div> + +<div class="doc_code"><tt> +void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived) +</tt></div> + +<div class="doc_text"> + +<p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic +function. It has exactly the same semantics as a non-volatile <tt>store</tt> to +the derived pointer (the third argument). The exact code generated is specified +by a <a href="#plugin">compiler plugin</a>.</p> + +<p>Many important algorithms require write barriers, including generational +and concurrent collectors. Additionally, write barriers could be used to +implement reference counting.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsubsection"> + <a name="gcread">Read barrier: <tt>llvm.gcread</tt></a> +</div> + +<div class="doc_code"><tt> +i8* @llvm.gcread(i8* %object, i8** %derived)<br> +</tt></div> + +<div class="doc_text"> + +<p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function. +It has exactly the same semantics as a non-volatile <tt>load</tt> from the +derived pointer (the second argument). The exact code generated is specified by +a <a href="#plugin">compiler plugin</a>.</p> + +<p>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.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="plugin">Implementing a collector plugin</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>User code specifies which GC code generation to use with the <tt>gc</tt> +function attribute or, equivalently, with the <tt>setGC</tt> method of +<tt>Function</tt>.</p> + +<p>To implement a GC plugin, it is necessary to subclass +<tt>llvm::GCStrategy</tt>, which can be accomplished in a few lines of +boilerplate code. LLVM's infrastructure provides access to several important +algorithms. For an uncontroversial collector, all that remains may be to +compile LLVM's computed stack map to assembly code (using the binary +representation expected by the runtime library). This can be accomplished in +about 100 lines of code.</p> + +<p>This is not the appropriate place to implement a garbage collected heap or a +garbage collector itself. That code should exist in the language's runtime +library. The compiler plugin is responsible for generating code which +conforms to the binary interface defined by library, most essentially the +<a href="#stack-map">stack map</a>.</p> + +<p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p> + +<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM GC plugin + +#include "llvm/CodeGen/GCStrategy.h" +#include "llvm/CodeGen/GCMetadata.h" +#include "llvm/Support/Compiler.h" + +using namespace llvm; + +namespace { + class VISIBILITY_HIDDEN MyGC : public GCStrategy { + public: + MyGC() {} + }; + + GCRegistry::Add<MyGC> + X("mygc", "My bespoke garbage collector."); +}</pre></blockquote> + +<p>This boilerplate collector does nothing. More specifically:</p> + +<ul> + <li><tt>llvm.gcread</tt> calls are replaced with the corresponding + <tt>load</tt> instruction.</li> + <li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding + <tt>store</tt> instruction.</li> + <li>No safe points are added to the code.</li> + <li>The stack map is not compiled into the executable.</li> +</ul> + +<p>Using the LLVM makefiles (like the <a +href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample +project</a>), this code can be compiled as a plugin using a simple +makefile:</p> + +<blockquote><pre +># lib/MyGC/Makefile + +LEVEL := ../.. +LIBRARYNAME = <var>MyGC</var> +LOADABLE_MODULE = 1 + +include $(LEVEL)/Makefile.common</pre></blockquote> + +<p>Once the plugin is compiled, code using it may be compiled using <tt>llc +-load=<var>MyGC.so</var></tt> (though <var>MyGC.so</var> may have some other +platform-specific extension):</p> + +<blockquote><pre +>$ cat sample.ll +define void @f() gc "mygc" { +entry: + ret void +} +$ llvm-as < sample.ll | llc -load=MyGC.so</pre></blockquote> + +<p>It is also possible to statically link the collector plugin into tools, such +as a language-specific compiler front-end.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="collector-algos">Overview of available features</a> +</div> + +<div class="doc_text"> + +<p><tt>GCStrategy</tt> provides a range of features through which a plugin +may do useful work. Some of these are callbacks, some are algorithms that can +be enabled, disabled, or customized. This matrix summarizes the supported (and +planned) features and correlates them with the collection techniques which +typically require them.</p> + +<table> + <tr> + <th>Algorithm</th> + <th>Done</th> + <th>shadow stack</th> + <th>refcount</th> + <th>mark-sweep</th> + <th>copying</th> + <th>incremental</th> + <th>threaded</th> + <th>concurrent</th> + </tr> + <tr> + <th class="rowhead"><a href="#stack-map">stack map</a></th> + <td>✔</td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + </tr> + <tr> + <th class="rowhead"><a href="#init-roots">initialize roots</a></th> + <td>✔</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead">derived pointers</th> + <td>NO</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td>✘*</td> + <td>✘*</td> + </tr> + <tr> + <th class="rowhead"><em><a href="#custom">custom lowering</a></em></th> + <td>✔</td> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + </tr> + <tr> + <th class="rowhead indent">gcroot</th> + <td>✔</td> + <td>✘</td> + <td>✘</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + </tr> + <tr> + <th class="rowhead indent">gcwrite</th> + <td>✔</td> + <td></td> + <td>✘</td> + <td></td> + <td></td> + <td>✘</td> + <td></td> + <td>✘</td> + </tr> + <tr> + <th class="rowhead indent">gcread</th> + <td>✔</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td>✘</td> + </tr> + <tr> + <th class="rowhead"><em><a href="#safe-points">safe points</a></em></th> + <td></td> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + </tr> + <tr> + <th class="rowhead indent">in calls</th> + <td>✔</td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + </tr> + <tr> + <th class="rowhead indent">before calls</th> + <td>✔</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead indent">for loops</th> + <td>NO</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + </tr> + <tr> + <th class="rowhead indent">before escape</th> + <td>✔</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead">emit code at safe points</th> + <td>NO</td> + <td></td> + <td></td> + <td></td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + </tr> + <tr> + <th class="rowhead"><em>output</em></th> + <td></td> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + <th></th> + </tr> + <tr> + <th class="rowhead indent"><a href="#assembly">assembly</a></th> + <td>✔</td> + <td></td> + <td></td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + <td>✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead indent">JIT</th> + <td>NO</td> + <td></td> + <td></td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead indent">obj</th> + <td>NO</td> + <td></td> + <td></td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead">live analysis</th> + <td>NO</td> + <td></td> + <td></td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + </tr> + <tr class="doc_warning"> + <th class="rowhead">register map</th> + <td>NO</td> + <td></td> + <td></td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + <td class="optl">✘</td> + </tr> + <tr> + <td colspan="10"> + <div><span class="doc_warning">*</span> Derived pointers only pose a + hazard to copying collectors.</div> + <div><span class="optl">✘</span> in gray denotes a feature which + could be utilized if available.</div> + </td> + </tr> +</table> + +<p>To be clear, the collection techniques above are defined as:</p> + +<dl> + <dt>Shadow Stack</dt> + <dd>The mutator carefully maintains a linked list of stack roots.</dd> + <dt>Reference Counting</dt> + <dd>The mutator maintains a reference count for each object and frees an + object when its count falls to zero.</dd> + <dt>Mark-Sw |