diff options
| -rw-r--r-- | docs/GarbageCollection.html | 1389 | ||||
| -rw-r--r-- | docs/GarbageCollection.rst | 1051 | ||||
| -rw-r--r-- | docs/subsystems.rst | 7 |
3 files changed, 1055 insertions, 1392 deletions
diff --git a/docs/GarbageCollection.html b/docs/GarbageCollection.html deleted file mode 100644 index 5bc70f1bb0..0000000000 --- a/docs/GarbageCollection.html +++ /dev/null @@ -1,1389 +0,0 @@ -<!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="_static/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> - -<h1> - Accurate Garbage Collection with LLVM -</h1> - -<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> - -<!-- *********************************************************************** --> -<h2> - <a name="introduction">Introduction</a> -</h2> -<!-- *********************************************************************** --> - -<div> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="feature">Goals and non-goals</a> -</h3> - -<div> - -<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> - -<!-- *********************************************************************** --> -<h2> - <a name="quickstart">Getting started</a> -</h2> -<!-- *********************************************************************** --> - -<div> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="quickstart-compiler">In your compiler</a> -</h3> - -<div> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="quickstart-runtime">In your runtime</a> -</h3> - -<div> - -<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> - -<pre class="doc_code"> -/// @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> - -<!-- ======================================================================= --> -<h3> - <a name="shadow-stack">About the shadow stack</a> -</h3> - -<div> - -<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> - -<!-- *********************************************************************** --> -<h2> - <a name="core">IR features</a><a name="intrinsics"></a> -</h2> -<!-- *********************************************************************** --> - -<div> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a> -</h3> - -<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> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a> -</h3> - -<div> - -<div class="doc_code"><tt> - void @llvm.gcroot(i8** %ptrloc, i8* %metadata) -</tt></div> - -<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>. All calls to <tt>llvm.gcroot</tt> <b>must</b> reside - inside the first basic block.</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. Note, that -stack variables must be initialized and marked with <tt>llvm.gcroot</tt> in -function's prologue.</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 class="doc_code"> - { - 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 class="doc_code"> -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** %tmp, 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> - -<!-- ======================================================================= --> -<h3> - <a name="barriers">Reading and writing references in the heap</a> -</h3> - -<div> - -<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> - -<!-- ======================================================================= --> -<h4> - <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a> -</h4> - -<div> - -<div class="doc_code"><tt> -void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived) -</tt></div> - -<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> - -<!-- ======================================================================= --> -<h4> - <a name="gcread">Read barrier: <tt>llvm.gcread</tt></a> -</h4> - -<div> - -<div class="doc_code"><tt> -i8* @llvm.gcread(i8* %object, i8** %derived)<br> -</tt></div> - -<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> - -</div> - -<!-- *********************************************************************** --> -<h2> - <a name="plugin">Implementing a collector plugin</a> -</h2> -<!-- *********************************************************************** --> - -<div> - -<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 LLVM_LIBRARY_VISIBILITY 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> - -<!-- ======================================================================= --> -<h3> - <a name="collector-algos">Overview of available features</a> -</h3> - -<div> - -<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-Sweep</dt> - <dd>When the heap is exhausted, the collector marks reachable objects starting - from the roots, then deallocates unreachable objects in a sweep - phase.</dd> - <dt>Copying</dt> - <dd>As reachability analysis proceeds, the collector copies objects from one - heap area to another, compacting them in the process. Copying collectors - enable highly efficient "bump pointer" allocation and can improve locality - of reference.</dd> - <dt>Incremental</dt> - <dd>(Including generational collectors.) Incremental collectors generally have - all the properties of a copying collector (regardless of whether the - mature heap is compacting), but bring the added complexity of requiring - write barriers.</dd> - <dt>Threaded</dt> - <dd>Denotes a multithreaded mutator; the collector must still stop the mutator - ("stop the world") before beginning reachability analysis. Stopping a - multithreaded mutator is a complicated problem. It generally requires - highly platform specific code in the runtime, and the production of - carefully designed machine code at safe points.</dd> - <dt>Concurrent</dt> - <dd>In this technique, the mutator and the collector run concurrently, with - the goal of eliminating pause times. In a <em>cooperative</em> collector, - the mutator further aids with collection should a pause occur, allowing - collection to take advantage of multiprocessor hosts. The "stop the world" - problem of threaded collectors is generally still present to a limited - extent. Sophisticated marking algorithms are necessary. Read barriers may - be necessary.</dd> -</dl> - -<p>As the matrix indicates, LLVM's garbage collection infrastructure is already -suitable for a wide variety of collectors, but does not currently extend to -multithreaded programs. This will be added in the future as there is -interest.</p> - -</div> - -<!-- ======================================================================= --> -<h3> - <a name="stack-map">Computing stack maps</a> -</h3> - -<div> - -<p>LLVM automatically computes a stack map. One of the most important features -of a <tt>GCStrategy</tt> is to compile this information into the executable in -the binary representation expected by the runtime library.</p> - -<p>The stack map consists of the location and identity of each GC root in the -each function in the module. For each root:</p> - -<ul> - <li><tt>RootNum</tt>: The index of the root.</li> - <li><tt>StackOffset</tt>: The offset of the object relative to the frame - pointer.</li> - <li><tt>RootMetadata</tt>: The value passed as the <tt>%metadata</tt> - parameter to the <a href="#gcroot"><tt>@llvm.gcroot</tt></a> intrinsic.</li> -</ul> - -<p>Also, for the function as a whole:</p> - -<ul> - <li><tt>getFrameSize()</tt>: The overall size of the function's initial - stack frame, not accounting for any dynamic allocation.</li> - <li><tt>roots_size()</tt>: The count of roots in the function.</li> -</ul> - -<p>To access the stack map, use <tt>GCFunctionMetadata::roots_begin()</tt> and --<tt>end()</tt> from the <tt><a -href="#assembly">GCMetadataPrinter</a></tt>:</p> - -<blockquote><pre ->for (iterator I = begin(), E = end(); I != E; ++I) { - GCFunctionInfo *FI = *I; - unsigned FrameSize = FI->getFrameSize(); - size_t RootCount = FI->roots_size(); - - for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(), - RE = FI->roots_end(); - RI != RE; ++RI) { - int RootNum = RI->Num; - int RootStackOffset = RI->StackOffset; - Constant *RootMetadata = RI->Metadata; - } -}</pre></blockquote> - -<p>If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code generation by -a custom lowering pass, LLVM will compute an empty stack map. This may be useful -for collector plugins which implement reference counting or a shadow stack.</p> - -</div> - - -<!-- ======================================================================= --> -<h3> - <a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a> -</h3> - -<div> - -<blockquote><pre ->MyGC::MyGC() { - InitRoots = true; -}</pre></blockquote> - -<p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon -entry to the function. This prevents the GC's sweep phase from visiting -uninitialized pointers, which will almost certainly cause it to crash. This -initialization occurs before custom lowering, so the two may be used -together.</p> - -<p>Since LLVM does not yet compute liveness information, there is no means of -distinguishing an uninitialized stack root from an initialized one. Therefore, -this feature should be used by all GC plugins. It is enabled by default.</p> - -</div> - - -<!-- ======================================================================= --> -<h3> - <a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, - <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a> -</h3> - -<div> - -<p>For GCs which use barriers or unusual treatment of stack roots, these -flags allow the collector to perform arbitrary transformations of the LLVM -IR:</p> - -<blockquote><pre ->class MyGC : public GCStrategy { -public: - MyGC() { - CustomRoots = true; - CustomReadBarriers = true; - CustomWriteBarriers = true; - } - - virtual bool initializeCustomLowering(Module &M); - virtual bool performCustomLowering(Function &F); -};</pre></blockquote> - -<p>If any of these flags are set, then LLVM suppresses its default lowering for -the corresponding intrinsics and instead calls -<tt>performCustomLowering</tt>.</p> - -<p>LLVM's default action for each intrinsic is as follows:</p> - -<ul> - <li><tt>llvm.gcroot</tt>: Leave it alone. The code generator must see it - or the stack map will not be computed.</li> - <li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li> - <li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li> -</ul> - -<p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified, -then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the -corresponding barriers.</p> - -<p><tt>performCustomLowering</tt> must comply with the same restrictions as <a -href="WritingAnLLVMPass.html#runOnFunction"><tt ->FunctionPass::runOnFunction</tt></a>. -Likewise, <tt>initializeCustomLowering</tt> has the same semantics as <a -href="WritingAnLLVMPass.html#doInitialization_mod"><tt ->Pass::doInitialization(Module&)</tt></a>.</p> - -<p>The following can be used as a template:</p> - -<blockquote><pre ->#include "llvm/Module.h" -#include "llvm/IntrinsicInst.h" - -bool MyGC::initializeCustomLowering(Module &M) { - return false; -} - -bool MyGC::performCustomLowering(Function &F) { - bool MadeChange = false; - - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) - if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) - if (Function *F = CI->getCalledFunction()) - switch (F->getIntrinsicID()) { - case Intrinsic::gcwrite: - // Handle llvm.gcwrite. - CI->eraseFromParent(); - MadeChange = true; - break; - case Intrinsic::gcread: - // Handle llvm.gcread. - CI->eraseFromParent(); - MadeChange = true; - break; - case Intrinsic::gcroot: - // Handle llvm.gcroot. - CI->eraseFromParent(); - MadeChange = true; - break; - } - - return MadeChange; -}</pre></blockquote> - -</div> - - -<!-- ======================================================================= --> -<h3> - <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a> -</h3> - -<div> - -<p>LLVM can compute four kinds of safe points:</p> - -<blockquote><pre ->namespace GC { - /// PointKind - The type of a collector-safe point. - /// - enum PointKind { - Loop, //< Instr is a loop (backwards branch). - Return, //< Instr is a return instruction. - PreCall, //< Instr is a call instruction. - PostCall //< Instr is the return address of a call. - }; -}</pre></blockquote> - -<p>A collector can request any combination of the four by setting the -<tt>NeededSafePoints</tt> mask:</p> - -<blockquote><pre ->MyGC::MyGC() { - NeededSafePoints = 1 << GC::Loop - | 1 << GC::Return - | 1 << GC::PreCall - | 1 << GC::PostCall; -}</pre></blockquote> - -<p>It can then use the following routines to access safe points.</p> - -<blockquote><pre ->for (iterator I = begin(), E = end(); I != E; ++I) { - GCFunctionInfo *MD = *I; - size_t PointCount = MD->size(); - - for (GCFunctionInfo::iterator PI = MD->begin(), - PE = MD->end(); PI != PE; ++PI) { - GC::PointKind PointKind = PI->Kind; - unsigned PointNum = PI->Num; - } -} -</pre></blockquote> - -<p>Almost every collector requires <tt>PostCall</tt> safe points, since these -correspond to the moments when the function is suspended during a call to a -subroutine.</p> - -<p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee -that the application will reach a safe point within a bounded amount of time, -even if it is executing a long-running loop which contains no function -calls.</p> - -<p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt> -safe points to implement "stop the world" techniques using self-modifying code, -where it is important that the program not exit the function without reaching a -safe point (because only the topmost function has been patched).</p> - -</div> - - -<!-- ======================================================================= --> -<h3> - <a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a> -</h3> - -<div> - -<p>LLVM allows a plugin to print arbitrary assembly code before and after the -rest of a module's assembly code. At the end of the module, the GC can compile -the LLVM stack map into assembly code. (At the beginning, this information is not -yet computed.)</p> - -<p>Since AsmWriter and CodeGen are separate components of LLVM, a separate -abstract base class and registry is provided for printing assembly code, the -<tt>GCMetadaPrinter</tt> and <tt>GCMetadataPrinterRegistry</tt>. The AsmWriter -will look for such a subclass if the <tt>GCStrategy</tt> sets -<tt>UsesMetadata</tt>:</p> - -<blockquote><pre ->MyGC::MyGC() { - UsesMetadata = true; -}</pre></blockquote> - -<p>This separation allows JIT-only clients to be smaller.</p> - -<p>Note that LLVM does not currently have analogous APIs to support code -generation in the JIT, nor using the object writers.</p> - -<blockquote><pre ->// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer - -#include "llvm/CodeGen/GCMetadataPrinter.h" -#include "llvm/Support/Compiler.h" - -using namespace llvm; - -namespace { - class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter { - public: - virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP, - const TargetAsmInfo &TAI); - - virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP, - const TargetAsmInfo &TAI); - }; - - GCMetadataPrinterRegistry::Add<MyGCPrinter> - X("mygc", "My bespoke garbage collector."); -}</pre></blockquote> - -<p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to -print portable assembly code to the <tt>std::ostream</tt>. The collector itself -contains the stack map for the entire module, and may access the -<tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt> -methods. Here's a realistic example:</p> - -<blockquote><pre ->#include "llvm/CodeGen/AsmPrinter.h" -#include "llvm/Function.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/DataLayout.h" -#include "llvm/Target/TargetAsmInfo.h" - -void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP, - const TargetAsmInfo &TAI) { - // Nothing to do. -} - -void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP, - const TargetAsmInfo &TAI) { - // Set up for emitting addresses. - const char *AddressDirective; - int AddressAlignLog; - if (AP.TM.getDataLayout()->getPointerSize() == sizeof(int32_t)) { - AddressDirective = TAI.getData32bitsDirective(); - AddressAlignLog = 2; - } else { - AddressDirective = TAI.getData64bitsDirective(); - AddressAlignLog = 3; - } - - // Put this in the data section. - AP.SwitchToDataSection(TAI.getDataSection()); - - // For each function... - for (iterator FI = begin(), FE = end(); FI != FE; ++FI) { - GCFunctionInfo &MD = **FI; - - // Emit this data structure: - // - // struct { - // int32_t PointCount; - // struct { - // void *SafePointAddress; - // int32_t LiveCount; - // int32_t LiveOffsets[LiveCount]; - // } Points[PointCount]; - // } __gcmap_<FUNCTIONNAME>; - - // Align to address width. - AP.EmitAlignment(AddressAlignLog); - - // Emit the symbol by which the stack map entry can be found. - std::string Symbol; - Symbol += TAI.getGlobalPrefix(); - Symbol += "__gcmap_"; - Symbol += MD.getFunction().getName(); - if (const char *GlobalDirective = TAI.getGlobalDirective()) - OS << GlobalDirective << Symbol << "\n"; - OS << TAI.getGlobalPrefix() << Symbol << ":\n"; - - // Emit PointCount. - AP.EmitInt32(MD.size()); - AP.EOL("safe point count"); - - // And each safe point... - for (GCFunctionInfo::iterator PI = MD.begin(), - PE = MD.end(); PI != PE; ++PI) { - // Align to address width. - AP.EmitAlignment(AddressAlignLog); - - // Emit the address of the safe point. - OS << AddressDirective - << TAI.getPrivateGlobalPrefix() << "label" << PI->Num; - AP.EOL("safe point address"); - - // Emit the stack frame size. - AP.EmitInt32(MD.getFrameSize()); - AP.EOL("stack frame size"); - - // Emit the number of live roots in the function. - AP.EmitInt32(MD.live_size(PI)); - AP.EOL("live root count"); - - // And for each live root... - for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI), - LE = MD.live_end(PI); - LI != LE; ++LI) { - // Print its offset within the stack frame. - AP.EmitInt32(LI->StackOffset); - AP.EOL("stack offset"); - } - } - } -} -</pre></blockquote> - -</div> - -</div> - -<!-- *********************************************************************** --> -<h2> - <a name="references">References</a> -</h2> -<!-- *********************************************************************** --> - -<div> - -<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew -W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p> - -<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for -strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN -PLDI'91.</p> - -<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using -explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM -conference on LISP and functional programming.</p> - -<p><a name="henderson02">[Henderson2002]</a> <a -href="http://citeseer.ist.psu.edu/henderson02accurate.html"> -Accurate Garbage Collection in an Uncooperative Environment</a>. -Fergus Henderson. International Symposium on Memory Management 2002.</p> - -</div> - - -<!-- *********************************************************************** --> - -<hr> -<address> - <a href="http://jigsaw.w3.org/css-validator/check/referer"><img - src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a> - <a href="http://validator.w3.org/check/referer"><img - src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a> - - <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> - <a href="http://llvm.org/">LLVM Compiler Infrastructure</a><br> - Last modified: $Date$ -</address> - -</body> -</html> diff --git a/docs/GarbageCollection.rst b/docs/GarbageCollection.rst new file mode 100644 index 0000000000..b0b2718409 --- /dev/null +++ b/docs/GarbageCollection.rst @@ -0,0 +1,1051 @@ +===================================== +Accurate Garbage Collection with LLVM +===================================== + +.. contents:: + :local: + +.. sectionauthor:: Chris Lattner <sabre@nondot.org> and + Gordon Henriksen + +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. + +.. _feature: + +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. + +.. _quickstart: + +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. + +.. _quickstart-compiler: + +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. + +.. _quickstart-runtime: + +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); + } + } + +.. _shadow-stack: + +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 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. + +.. _gcattr: + +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. +The exact impact on generated code is specified by a :ref:`compiler plugin +<plugin>`. All calls to ``llvm.gcroot`` **must** reside inside the first basic +block. + +A compiler which uses mem2reg to raise imperative code using ``alloca`` into SSA +form need only add a call to ``@llvm.gcroot`` for those variables which a +pointers into the GC heap. + +It is also important to mark intermediate values with ``llvm.gcroot``. For +example, consider ``h(f(), g())``. Beware leaking the result of ``f()`` in the +case that ``g()`` triggers a collection. Note, that stack variables must be +initialized and marked with ``llvm.gcroot`` in function's prologue. + +The first argument **must** be a value referring to an alloca instruction or a +bitcast of an alloca. The second contains a pointer to metadata that should be +associated with the pointer, and **must** be a constant or global value +address. If your target collector uses tags, use a null pointer for metadata. + +The ``%metadata`` argument can be used to avoid requiring heap objects to have +'isa' pointers or tag bits. [Appel89_, Goldberg91_, Tolmach94_] If specified, +its value will be tracked along with the location of the pointer in the stack +frame. + +Consider the following fragment of Java code: + +.. code-block:: java + + { + Object X; // A null-initialized reference to an object + ... + } + +This block (which may be located in the middle of a function or in a loop nest), +could be compiled to this LLVM code: + +.. code-block:: llvm + + 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** %tmp, 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 + ... + +.. _barriers: + +Reading and writing references in the heap +------------------------------------------ + +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 *read +barriers* and *write barriers*, 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. + +Barriers often require access to the *object pointer* rather than the *derived +pointer* (which is a pointer to the field within the object). Accordingly, +these intrinsics take both pointers as separate arguments for completeness. In +this snippet, ``%object`` is the object pointer, and ``%derived`` is the derived +pointer: + +.. code-block:: llvm + + ;; 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 + +LLVM does not enforce this relationship between the object and derived pointer +(although a plugin_ might). However, it would be an unusual collector that +violated it. + +The use of these intrinsics is naturally optional if the target GC does require +the corresponding barrier. Such a GC plugin will replace the intrinsic calls +with the corresponding ``load`` or ``store`` instruction if they are used. + +.. _gcwrite: + +Write barrier: ``llvm.gcwrite`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +.. code-block:: llvm + + void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived) + +For write barriers, LLVM provides the ``llvm.gcwrite`` intrinsic function. It +has exactly the same semantics as a non-volatile ``store`` to the derived +pointer (the third argument). The exact code generated is specified by a +compiler plugin_. + +Many important algorithms require write barriers, including generational and +concurrent collectors. Additionally, write barriers could be used to implement +reference counting. + +.. _gcread: + +Read barrier: ``llvm.gcread`` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +.. code-block:: llvm + + i8* @llvm.gcread(i8* %object, i8** %derived) + +For read barriers, LLVM provides the ``llvm.gcread`` intrinsic function. It has +exactly the same semantics as a non-volatile ``load`` from the derived pointer +(the second argument). The exact code generated is specified by a compiler +plugin_. + +Read barriers are needed by fewer algorithms than write barriers, and may have a +greater performance impact since pointer reads are more frequent than writes. + +.. _plugin: + +Implementing a collector plugin +=============================== + +User code specifies which GC code generation to use with the ``gc`` function +attribute or, equivalently, with the ``setGC`` method of ``Function``. + +To implement a GC plugin, it is necessary to subclass ``llvm::GCStrategy``, +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. + +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 :ref:`stack map +<stack-map>`. + +To subclass ``llvm::GCStrategy`` and register it with the compiler: + +.. code-block:: c++ + + // 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 LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy { + public: + MyGC() {} + }; + + GCRegistry::Add<MyGC> + X("mygc", "My bespoke garbage collector."); + } + +This boilerplate collector does nothing. More specifically: + +* ``llvm.gcread`` calls are replaced with the corresponding ``load`` + instruction. + +* ``llvm.gcwrite`` calls are replaced with the corresponding ``store`` + instruction. + +* No safe points are added to the code. + +* The stack map is not compiled into the executable. + +Using the LLVM makefiles (like the `sample project +<http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/>`__), this code +can be compiled as a plugin using a simple makefile: + +.. code-block:: make + + # lib/MyGC/Makefile + + LEVEL := ../.. + LIBRARYNAME = MyGC + LOADABLE_MODULE = 1 + + include $(LEVEL)/Makefile.common + +Once the plugin is compiled, code using it may be compiled using ``llc +-load=MyGC.so`` (though MyGC.so may have some other platform-specific +extension): + +:: + + $ cat sample.ll + define void @f() gc "mygc" { + entry: + ret void + } + $ llvm-as < sample.ll | llc -load=MyGC.so + +It is also possible to statically link the collector plugin into tools, such as +a language-specific compiler front-end. + +.. _collector-algos: + +Overview of available features +------------------------------ + +``GCStrategy`` 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. + +.. |v| unicode:: 0x2714 + :trim: + +.. |x| unicode:: 0x2718 + :trim: + ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| Algorithm | Done | Shadow | refcount | mark- | copying | incremental | threaded | concurrent | +| | | stack | | sweep | | | | | ++============+======+========+==========+=======+=========+=============+==========+============+ +| stack map | |v| | | | |x| | |x| | |x| | |x| | |x| | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| initialize | |v| | |x| | |x| | |x| | |x| | |x| | |x| | |x| | +| roots | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| derived | NO | | | | | | **N**\* | **N**\* | +| pointers | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| **custom | |v| | | | | | | | | +| lowering** | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *gcroot* | |v| | |x| | |x| | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *gcwrite* | |v| | | |x| | | | |x| | | |x| | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *gcread* | |v| | | | | | | | |x| | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| **safe | | | | | | | | | +| points** | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *in | |v| | | | |x| | |x| | |x| | |x| | |x| | +| calls* | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *before | |v| | | | | | | |x| | |x| | +| calls* | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *for | NO | | | | | | **N** | **N** | +| loops* | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *before | |v| | | | | | | |x| | |x| | +| escape* | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| emit code | NO | | | | | | **N** | **N** | +| at safe | | | | | | | | | +| points | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| **output** | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *assembly* | |v| | | | |x| | |x| | |x| | |x| | |x| | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *JIT* | NO | | | **?** | **?** | **?** | **?** | **?** | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| *obj* | NO | | | **?** | **?** | **?** | **?** | **?** | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| live | NO | | | **?** | **?** | **?** | **?** | **?** | +| analysis | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| register | NO | | | **?** | **?** | **?** | **?** | **?** | +| map | | | | | | | | | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| \* Derived pointers only pose a hasard to copying collections. | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ +| **?** denotes a feature which could be utilized if available. | ++------------+------+--------+----------+-------+---------+-------------+----------+------------+ + +To be clear, the collection techniques above are defined as: + +Shadow Stack + The mutator carefully maintains a linked list of stack roots. + +Reference Counting + The mutator maintains a reference count for each object and frees an object + when its count falls to zero. + +Mark-Sweep + When the heap is exhausted, the collector marks reachable objects starting + from the roots, then deallocates unreachable objects in a sweep phase. + +Copying + As reachability analysis proceeds, the collector copies objects from one heap + area to another, compacting them in the process. Copying collectors enable + highly efficient "bump pointer" allocation and can improve locality of + reference. + +Incremental + (Including generational collectors.) Incremental collectors generally have all + the properties of a copying collector (regardless of whether the mature heap + is compacting), but bring the added complexity of requiring write barriers. + +Threaded + Denotes a multithreaded mutator; the collector must still stop the mutator + ("stop the world") before beginning reachability analysis. Stopping a + multithreaded mutator is a complicated problem. It generally requires highly + platform specific code in the runtime, and the production of carefully + designed machine code at safe points. + +Concurrent + In this technique, the mutator and the collector run concurrently, with the + goal of eliminating pause times. In a *cooperative* collector, the mutator + further aids with collection should a pause occur, allowing collection to take + advantage of multiprocessor hosts. The "stop the world" problem of threaded + collectors is generally still present to a limited extent. Sophisticated + marking algorithms are necessary. Read barriers may be necessary. + +As the matrix indicates, LLVM's garbage collection infrastructure is already +suitable for a wide variety of collectors, but does not currently extend to +multithreaded programs. This will be added in the future as there is +interest. + +.. _stack-map: + +Computing stack maps +-------------------- + +LLVM automatically computes a stack map. One of the most important features +of a ``GCStrategy`` is to compile this information into the executable in +the binary representation expected by the runtime library. + +The stack map consists of the location and identity of each GC root in the +each function in the module. For each root: + +* ``RootNum``: The index of the root. + +* ``StackOffset``: The offset of the object relative to the frame pointer. + +* ``RootMetadata``: The value passed as the ``%metadata`` parameter to the + ``@llvm.gcroot`` intrinsic. + +Also, for the function as a whole: + +* ``getFrameSize()``: The overall size of the function's initial stack frame, + not accounting for any dynamic allocation. + +* ``roots_size()``: The count of roots in the function. + +To access the stack map, use ``GCFunctionMetadata::roots_begin()`` and +-``end()`` from the :ref:`GCMetadataPrinter <assembly>`: + +.. code-block:: c++ + + for (iterator I = begin(), E = end(); I != E; ++I) { + GCFunctionInfo *FI = *I; + unsigned FrameSize = FI->getFrameSize(); + size_t RootCount = FI->roots_size(); + + for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(), + RE = FI->roots_end(); + RI != RE; ++RI) { + int RootNum = RI->Num; + int RootStackOffset = RI->StackOffset; + Constant *RootMetadata = RI->Metadata; + } + } + +If the ``llvm.gcroot`` intrinsic is eliminated before code generation by a +custom lowering pass, LLVM will compute an empty stack map. This may be useful +for collector plugins which implement reference counting or a shadow stack. + +.. _init-roots: + +Initializing roots to null: ``InitRoots`` +----------------------------------------- + +.. code-block:: c++ + + MyGC::MyGC() { + InitRoots = true; + } + +When set, LLVM will automatically initialize each root to ``null`` upon entry to +the function. This prevents the GC's sweep phase from visiting uninitialized +pointers, which will almost certainly cause it to crash. This initialization +occurs before custom lowering, so the two may be used together. + +Since LLVM does not yet compute liveness information, there is no means of +distinguishing an uninitialized stack root from an initialized one. Therefore, +this feature should be used by all GC plugins. It is enabled by default. + +.. _custom: + +Custom lowering of intrinsics: ``CustomRoots``, ``CustomReadBarriers``, and ``CustomWriteBarriers`` +--------------------------------------------------------------------------------------------------- + +For GCs which use barriers or unusual treatment of stack roots, these flags +allow the collector to perform arbitrary transformations of the LLVM IR: + +.. code-block:: c++ + + class MyGC : public GCStrategy { + public: + MyGC() { + CustomRoots = true; + CustomReadBarriers = true; + CustomWriteBarriers = true; + } + + virtual bool initializeCustomLowering(Module &M); + virtual bool performCustomLowering(Function &F); + }; + +If any of these flags are set, then LLVM suppresses its default lowering for the +corresponding intrinsics and instead calls ``performCustomLowering``. + +LLVM's default action for each intrinsic is as follows: + +* ``llvm.gcroot``: Leave it alone. The code generator must see it or the stack + map will not be computed. + +* ``llvm.gcread``: Substitute a ``load`` instruction. + +* ``llvm.gcwrite``: Substitute a ``store`` instruction. + +If ``CustomReadBarriers`` or ``CustomWriteBarriers`` are specified, then +``performCustomLowering`` **must** eliminate the corresponding barriers. + +``performCustomLowering`` must comply with the same restrictions as +`FunctionPass::runOnFunction <WritingAnLLVMPass.html#runOnFunction>`__ +Likewise, ``initializeCustomLowering`` has the same semantics as +`Pass::doInitialization(Module&) +<WritingAnLLVMPass.html#doInitialization_mod>`__ + +The following can be used as a template: + +.. code-block:: c++ + + #include "llvm/Module.h" + #include "llvm/IntrinsicInst.h" + + bool MyGC::initializeCustomLowering(Module &M) { + return false; + } + + bool MyGC::performCustomLowering(Function &F) { + bool MadeChange = false; + + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) + if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) + if (Function *F = CI->getCalledFunction()) + switch (F->getIntrinsicID()) { + case Intrinsic::gcwrite: + // Handle llvm.gcwrite. + CI->eraseFromParent(); + MadeChange = true; + break; + case Intrinsic::gcread: + // Handle llvm.gcread. + CI->eraseFromParent(); + MadeChange = true; + break; + case Intrinsic::gcroot: + // Handle llvm.gcroot. + CI->eraseFromParent(); + MadeChange = true; + break; + } + + return MadeChange; + } + +.. _safe-points: + +Generating safe points: ``NeededSafePoints`` +-------------------------------------------- + +LLVM can compute four kinds of safe points: + +.. code-block:: c++ + + namespace GC { + /// PointKind - The type of a collector-safe point. + /// + enum PointKind { + Loop, //< Instr is a loop (backwards branch). + Return, //< Instr is a return instruction. + PreCall, //< Instr is a call instruction. + PostCall //< Instr is the return address of a call. + }; + } + +A collector can request any combination of the four by setting the +``NeededSafePoints`` mask: + +.. code-block:: c++ + + MyGC::MyGC() { + NeededSafePoints = 1 << GC::Loop + | 1 << GC::Return + | 1 << GC::PreCall + | 1 << GC::PostCall; + } + +It can then use the following routines to access safe points. + +.. code-block:: c++ + + for (iterator I = begin(), E = end(); I != E; ++I) { + GCFunctionInfo *MD = *I; + size_t PointCount = MD->size(); + + for (GCFunctionInfo::iterator PI = MD->begin(), + PE = MD->end(); PI != PE; ++PI) { + GC::PointKind PointKind = PI->Kind; + unsigned PointNum = PI->Num; + } + } + +Almost every collector requires ``PostCall`` safe points, since these correspond +to the moments when the function is suspended during a call to a subroutine. + +Threaded programs generally require ``Loop`` safe points to guarantee that the +application will reach a safe point within a bounded amount of time, even if it +is executing a long-running loop which contains no function calls. + +Threaded collectors may also require ``Return`` and ``PreCall`` safe points to +implement "stop the world" techniques using self-modifying code, where it is +important that the program not exit the function without reaching a safe point +(because only the topmost function has been patched). + +.. _assembly: + +Emitting assembly code: ``GCMetadataPrinter`` +--------------------------------------------- + +LLVM allows a plugin to print arbitrary assembly code before and after the rest +of a module's assembly code. At the end of the module, the GC can compile the +LLVM stack map into assembly code. (At the beginning, this information is not +yet computed.) + +Since AsmWriter and CodeGen are separate components of LLVM, a separate abstract +base class and registry is provided for printing assembly code, the +``GCMetadaPrinter`` and ``GCMetadataPrinterRegistry``. The AsmWriter will look +for such a subclass if the ``GCStrategy`` sets ``UsesMetadata``: + +.. code-block:: c++ + + MyGC::MyGC() { + UsesMetadata = true; + } + +This separation allows JIT-only clients to be smaller. + +Note that LLVM does not currently have analogous APIs to support code generation +in the JIT, nor using the object writers. + +.. code-block:: c++ + + // lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer + + #include "llvm/CodeGen/GCMetadataPrinter.h" + #include "llvm/Support/Compiler.h" + + using namespace llvm; + + namespace { + class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter { + public: + virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP, + const TargetAsmInfo &TAI); + + virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP, + const TargetAsmInfo &TAI); + }; + + GCMetadataPrinterRegistry::Add<MyGCPrinter> + X("mygc", "My bespoke garbage collector."); + } + +The collector should use ``AsmPrinter`` and ``TargetAsmInfo`` to print portable +assembly code to the ``std::ostream``. The collector itself contains the stack +map for the entire module, and may access the ``GCFunctionInfo`` using its own +``begin()`` and ``end()`` methods. Here's a realistic example: + +.. code-block:: c++ + + #include "llvm/CodeGen/AsmPrinter.h" + #include "llvm/Function.h" + #include "llvm/Target/TargetMachine.h" + #include "llvm/DataLayout.h" + #include "llvm/Target/TargetAsmInfo.h" + + void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP, + const TargetAsmInfo &TAI) { + // Nothing to do. + } + + void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP, + const TargetAsmInfo &TAI) { + // Set up for emitting addresses. + const char *AddressDirective; + int AddressAlignLog; + if (AP.TM.getDataLayout()->getPointerSize() == sizeof(int32_t)) { + AddressDirective = TAI.getData32bitsDirective(); + AddressAlignLog = 2; + } else { + AddressDirective = TAI.getData64bitsDirective(); + AddressAlignLog = 3; + } + + // Put this in the data section. + AP.SwitchToDataSection(TAI.getDataSection()); + + // For each function... + for (iterator FI = begin(), FE = end(); FI != FE; ++FI) { + GCFunctionInfo &MD = **FI; + + // Emit this data structure: + // + // struct { + // int32_t PointCount; + // struct { + // void *SafePointAddress; + // int32_t LiveCount; + // int32_t LiveOffsets[LiveCount]; + // } Points[PointCount]; + // } __gcmap_<FUNCTIONNAME>; + + // Align to address width. + AP.EmitAlignment(AddressAlignLog); + + // Emit the symbol by which the stack map entry can be found. + std::string Symbol; + Symbol += TAI.getGlobalPrefix(); + Symbol += "__gcmap_"; + Symbol += MD.getFunction().getName(); + if (const char *GlobalDirective = TAI.getGlobalDirective()) + OS << GlobalDirective << Symbol << "\n"; + OS << TAI.getGlobalPrefix() << Symbol << ":\n"; + + // Emit PointCount. + AP.EmitInt32(MD.size()); + AP.EOL("safe point count"); + + // And each safe point... + for (GCFunctionInfo::iterator PI = MD.begin(), + PE = MD.end(); PI != PE; ++PI) { + // Align to address width. + AP.EmitAlignment(AddressAlignLog); + + // Emit the address of the safe point. + OS << AddressDirective + << TAI.getPrivateGlobalPrefix() << "label" << PI->Num; + AP.EOL("safe point address"); + + // Emit the stack frame size. + AP.EmitInt32(MD.getFrameSize()); + AP.EOL("stack frame size"); + + // Emit the number of live roots in the function. + AP.EmitInt32(MD.live_size(PI)); + AP.EOL("live root count"); + + // And for each live root... + for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI), + LE = MD.live_end(PI); + LI != LE; ++LI) { + // Print its offset within the stack frame. + AP.EmitInt32(LI->StackOffset); + AP.EOL("stack offset"); + } + } + } + } + +References +========== + +.. _appel89: + +[Appel89] Runtime Tags Aren't Necessary. Andrew W. Appel. Lisp and Symbolic +Computation 19(7):703-705, July 1989. + +.. _goldberg91: + +[Goldberg91] Tag-free garbage collection for strongly typed programming +languages. Benjamin Goldberg. ACM SIGPLAN PLDI'91. + +.. _tolmach94: + +[Tolmach94] Tag-free garbage collection using explicit type parameters. Andrew +Tolmach. Proceedings of the 1994 ACM conference on LISP and functional +programming. + +.. _henderson02: + +[Henderson2002] `Accurate Garbage Collection in an Uncooperative Environment +<http://citeseer.ist.psu.edu/henderson02accurate.html>`__ + diff --git a/docs/subsystems.rst b/docs/subsystems.rst index f863d1fc6d..275955be6e 100644 --- a/docs/subsystems.rst +++ b/docs/subsystems.rst @@ -22,6 +22,7 @@ Subsystem Documentation SystemLibrary SourceLevelDebugging WritingAnLLVMBackend + GarbageCollection .. FIXME: once LangRef is Sphinxified, HowToUseInstrMappings should be put under LangRef's toctree instead of this page's toctree. @@ -49,9 +50,9 @@ Subsystem Documentation Information on how to write a new alias analysis implementation or how to use existing analyses. - -* `Accurate Garbage Collection with LLVM <GarbageCollection.html>`_ - + +* :doc:`GarbageCollection` + The interfaces source-language compilers should use for compiling GC'd programs. |