| <!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">GC features provided and algorithms | |
| supported</a></li> | |
| </ul> | |
| </li> | |
| <li><a href="#usage">Using the collectors</a> | |
| <ul> | |
| <li><a href="#shadow-stack">ShadowStack - | |
| A highly portable collector</a></li> | |
| <li><a href="#semispace">SemiSpace - | |
| A simple copying collector runtime</a></li> | |
| <li><a href="#ocaml">Ocaml - | |
| An Objective Caml-compatible collector</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="#runtime">Recommended runtime interface</a> | |
| <ul> | |
| <li><a href="#initialize">Garbage collector startup and | |
| initialization</a></li> | |
| <li><a href="#allocate">Allocating memory from the GC</a></li> | |
| <li><a href="#explicit">Explicit invocation of the garbage | |
| collector</a></li> | |
| <li><a href="#traceroots">Tracing GC pointers from the program | |
| stack</a></li> | |
| <li><a href="#staticroots">Tracing GC pointers from static roots</a></li> | |
| </ul> | |
| </li> | |
| <li><a href="#plugin">Implementing a collector plugin</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 allocation | |
| 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">GC features provided and algorithms supported</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 implement a garbage collector. This is because | |
| collectors are tightly coupled to object models, and LLVM is agnostic to object | |
| models. Since LLVM is agnostic to object models, it would be inappropriate for | |
| LLVM to dictate any particular collector. Instead, LLVM provides a framework for | |
| garbage collector implementations in two manners:</p> | |
| <ul> | |
| <li><b>At compile time</b> with <a href="#plugin">collector plugins</a> for | |
| the compiler. Collector plugins have ready access to important garbage | |
| collector algorithms. Leveraging these tools, it is straightforward to | |
| emit type-accurate stack maps for your runtime in as little as ~100 lines of | |
| C++ code.</li> | |
| <li><b>At runtime</b> with <a href="#runtime">suggested runtime | |
| interfaces</a>, which allow front-end compilers to support a range of | |
| collection runtimes.</li> | |
| </ul> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_section"> | |
| <a name="usage">Using the collectors</a> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_text"> | |
| <p>In general, using a collector implies:</p> | |
| <ul> | |
| <li>Emitting compatible code, including initialization in the main | |
| program if necessary.</li> | |
| <li>Loading a compiler plugin if the collector is not statically linked with | |
| your compiler. For <tt>llc</tt>, use the <tt>-load</tt> option.</li> | |
| <li>Selecting the collection algorithm by applying the <tt>gc "..."</tt> | |
| attribute to your garbage collected functions, or equivalently with | |
| the <tt>setGC</tt> method.</li> | |
| <li>Linking your final executable with the garbage collector runtime.</li> | |
| </ul> | |
| <p>This table summarizes the available runtimes.</p> | |
| <table> | |
| <tr> | |
| <th>Collector</th> | |
| <th><tt>gc</tt> attribute</th> | |
| <th>Linkage</th> | |
| <th><tt>gcroot</tt></th> | |
| <th><tt>gcread</tt></th> | |
| <th><tt>gcwrite</tt></th> | |
| </tr> | |
| <tr valign="baseline"> | |
| <td><a href="#semispace">SemiSpace</a></td> | |
| <td><tt>gc "shadow-stack"</tt></td> | |
| <td>TODO FIXME</td> | |
| <td>required</td> | |
| <td>optional</td> | |
| <td>optional</td> | |
| </tr> | |
| <tr valign="baseline"> | |
| <td><a href="#ocaml">Ocaml</a></td> | |
| <td><tt>gc "ocaml"</tt></td> | |
| <td><i>provided by ocamlopt</i></td> | |
| <td>required</td> | |
| <td>optional</td> | |
| <td>optional</td> | |
| </tr> | |
| </table> | |
| <p>The sections for <a href="#intrinsics">Collection intrinsics</a> and | |
| <a href="#runtime">Recommended runtime interface</a> detail the interfaces that | |
| collectors may require user programs to utilize.</p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="shadow-stack">ShadowStack - A highly portable collector</a> | |
| </div> | |
| <div class="doc_code"><tt> | |
| Collector *llvm::createShadowStackCollector(); | |
| </tt></div> | |
| <div class="doc_text"> | |
| <p>The ShadowStack backend is invoked with the <tt>gc "shadow-stack"</tt> | |
| function attribute. | |
| Unlike many collectors which rely on a cooperative code generator to generate | |
| stack maps, this algorithm carefully maintains a linked list of stack root | |
| descriptors [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow | |
| stack" mirrors the machine stack. Maintaining this data structure is slower | |
| than using stack maps, but has a significant portability advantage because it | |
| requires no special support from the target code generator.</p> | |
| <p>The ShadowStack collector does not use read or write barriers, so the user | |
| program may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt> | |
| and <tt>llvm.gcwrite</tt>.</p> | |
| <p>ShadowStack is a code generator plugin only. It must be paired with a | |
| compatible runtime.</p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="semispace">SemiSpace - A simple copying collector runtime</a> | |
| </div> | |
| <div class="doc_text"> | |
| <p>The SemiSpace runtime implements the <a href="runtime">suggested | |
| runtime interface</a> and is compatible with the ShadowStack backend.</p> | |
| <p>SemiSpace is a very simple copying collector. When it starts up, it | |
| allocates two blocks of memory for the heap. It uses a simple bump-pointer | |
| allocator to allocate memory from the first block until it runs out of space. | |
| When it runs out of space, it traces through all of the roots of the program, | |
| copying blocks to the other half of the memory space.</p> | |
| <p>This runtime is highly experimental and has not been used in a real project. | |
| Enhancements would be welcomed.</p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="ocaml">Ocaml - An Objective Caml-compatible collector</a> | |
| </div> | |
| <div class="doc_code"><tt> | |
| Collector *llvm::createOcamlCollector(); | |
| </tt></div> | |
| <div class="doc_text"> | |
| <p>The ocaml backend is invoked with the <tt>gc "ocaml"</tt> function attribute. | |
| It supports the | |
| <a href="http://caml.inria.fr/">Objective Caml</a> language runtime by emitting | |
| a type-accurate stack map in the form of an ocaml 3.10.0-compatible frametable. | |
| The linkage requirements are satisfied automatically by the <tt>ocamlopt</tt> | |
| compiler when linking an executable.</p> | |
| <p>The ocaml collector does not use read or write barriers, so the user program | |
| may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt> and | |
| <tt>llvm.gcwrite</tt>.</p> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_section"> | |
| <a name="core">Core support</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>.</p> | |
| <p>These facilities are limited to those strictly necessary for compilation. | |
| They are not intended to be a complete interface to any garbage collector. | |
| Notably, heap allocation is not among the supplied primitives. A user program | |
| will also need to interface with the runtime, using either the | |
| <a href="#runtime">suggested runtime interface</a> or another interface | |
| specified by the runtime.</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>(...) <u>gc "<i>collector</i>"</u> { ... | |
| </tt></div> | |
| <div class="doc_text"> | |
| <p>The <tt>gc</tt> function attribute is used to specify the desired collector | |
| algorithm to the compiler. It is equivalent to specifying the collector name | |
| programmatically using the <tt>setGC</tt> method of <tt>Function</tt>.</p> | |
| <p>Specifying the collector on a per-function basis allows LLVM to link together | |
| programs that use different garbage collection algorithms.</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 of a pointer | |
| variable on the stack. 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>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> | |
| </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).</p> | |
| <p>Many important algorithms require write barriers, including generational | |
| and concurrent collectors. Additionally, write barriers could be used to | |
| implement reference counting.</p> | |
| <p>The use of this intrinsic is optional if the target collector does use | |
| write barriers. If so, the collector will replace it with the corresponding | |
| <tt>store</tt>.</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).</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> | |
| <p>As with <tt>llvm.gcwrite</tt>, a target collector might not require the use | |
| of this intrinsic.</p> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_section"> | |
| <a name="runtime">Recommended runtime interface</a> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_text"> | |
| <p>LLVM specifies the following recommended runtime interface to the garbage | |
| collection at runtime. A program should use these interfaces to accomplish the | |
| tasks not supported by the intrinsics.</p> | |
| <p>Unlike the intrinsics, which are integral to LLVM's code generator, there is | |
| nothing unique about these interfaces; a front-end compiler and runtime are free | |
| to agree to a different specification.</p> | |
| <p class="doc_warning">Note: This interface is a work in progress.</p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="initialize">Garbage collector startup and initialization</a> | |
| </div> | |
| <div class="doc_text"> | |
| <div class="doc_code"><tt> | |
| void llvm_gc_initialize(unsigned InitialHeapSize); | |
| </tt></div> | |
| <p> | |
| The <tt>llvm_gc_initialize</tt> function should be called once before any other | |
| garbage collection functions are called. This gives the garbage collector the | |
| chance to initialize itself and allocate the heap. The initial heap size to | |
| allocate should be specified as an argument. | |
| </p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="allocate">Allocating memory from the GC</a> | |
| </div> | |
| <div class="doc_text"> | |
| <div class="doc_code"><tt> | |
| void *llvm_gc_allocate(unsigned Size); | |
| </tt></div> | |
| <p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the | |
| garbage collector implementation to allocate memory. It returns a | |
| zeroed-out block of memory of the specified size, sufficiently aligned to store | |
| any object.</p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="explicit">Explicit invocation of the garbage collector</a> | |
| </div> | |
| <div class="doc_text"> | |
| <div class="doc_code"><tt> | |
| void llvm_gc_collect(); | |
| </tt></div> | |
| <p> | |
| The <tt>llvm_gc_collect</tt> function is exported by the garbage collector | |
| implementations to provide a full collection, even when the heap is not | |
| exhausted. This can be used by end-user code as a hint, and may be ignored by | |
| the garbage collector. | |
| </p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="traceroots">Tracing GC pointers from the program stack</a> | |
| </div> | |
| <div class="doc_text"> | |
| <div class="doc_code"><tt> | |
| void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta)); | |
| </tt></div> | |
| <p> | |
| The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code | |
| generator that iterates through all of the GC roots on the stack, calling the | |
| specified function pointer with each record. For each GC root, the address of | |
| the pointer and the meta-data (from the <a | |
| href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided. | |
| </p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="staticroots">Tracing GC pointers from static roots</a> | |
| </div> | |
| <div class="doc_text"> | |
| TODO | |
| </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 emit | |
| the assembly code for the collector's unique stack map data structure, which | |
| might be accomplished in as few as 100 LOC.</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 is | |
| compatible with that runtime library.</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>Using the LLVM makefiles (like the <a | |
| href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample | |
| project</a>), this can be built into 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>The boilerplate collector above 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 stack map is emitted, and no safe points are added.</li> | |
| </ul> | |
| <p><tt>Collector</tt> provides a range of features through which a plugin | |
| collector may do useful work. 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 root | |
| descriptors.</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> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="stack-map">Computing stack maps</a> | |
| </div> | |
| <div class="doc_text"> | |
| <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>LLVM automatically computes a stack map. All a <tt>GCStrategy</tt> needs to do | |
| is access it using <tt>GCFunctionMetadata::roots_begin()</tt> and | |
| -<tt>end()</tt>. If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code | |
| generation by a custom lowering pass, LLVM's stack map will be empty.</p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a> | |
| </div> | |
| <div class="doc_text"> | |
| <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> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, | |
| <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a> | |
| </div> | |
| <div class="doc_text"> | |
| <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>: Pass through to the code generator to generate a | |
| stack map.</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> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a> | |
| </div> | |
| <div class="doc_text"> | |
| <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> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a> | |
| </div> | |
| <div class="doc_text"> | |
| <p>LLVM allows a GC 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 print stack | |
| maps built by the code generator. (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>GCMetadaPrinterRegistry</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>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 VISIBILITY_HIDDEN 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/Target/TargetData.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.getTargetData()->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 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 class="doc_section"> | |
| <a name="runtime-impl">Implementing a collector runtime</a> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_text"> | |
| <p>Implementing a garbage collector for LLVM is fairly straightforward. The | |
| LLVM garbage collectors are provided in a form that makes them easy to link into | |
| the language-specific runtime that a language front-end would use. They require | |
| functionality from the language-specific runtime to get information about <a | |
| href="#gcdescriptors">where pointers are located in heap objects</a>.</p> | |
| <p>The implementation must include the | |
| <a href="#allocate"><tt>llvm_gc_allocate</tt></a> and | |
| <a href="#explicit"><tt>llvm_gc_collect</tt></a> functions. To do this, it will | |
| probably have to <a href="#traceroots">trace through the roots | |
| from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors | |
| for heap objects</a>. Luckily, there are some <a href="#usage">example | |
| implementations</a> available. | |
| </p> | |
| </div> | |
| <!-- ======================================================================= --> | |
| <div class="doc_subsection"> | |
| <a name="gcdescriptors">Tracing GC pointers from heap objects</a> | |
| </div> | |
| <div class="doc_text"> | |
| <p> | |
| The three most common ways to keep track of where pointers live in heap objects | |
| are (listed in order of space overhead required):</p> | |
| <ol> | |
| <li>In languages with polymorphic objects, pointers from an object header are | |
| usually used to identify the GC pointers in the heap object. This is common for | |
| object-oriented languages like Self, Smalltalk, Java, or C#.</li> | |
| <li>If heap objects are not polymorphic, often the "shape" of the heap can be | |
| determined from the roots of the heap or from some other meta-data [<a | |
| href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a | |
| href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can | |
| propagate the information around from meta data stored with the roots. This | |
| often eliminates the need to have a header on objects in the heap. This is | |
| common in the ML family.</li> | |
| <li>If all heap objects have pointers in the same locations, or pointers can be | |
| distinguished just by looking at them (e.g., the low order bit is clear), no | |
| book-keeping is needed at all. This is common for Lisp-like languages.</li> | |
| </ol> | |
| <p>The LLVM garbage collectors are capable of supporting all of these styles of | |
| language, including ones that mix various implementations. To do this, it | |
| allows the source-language to associate meta-data with the <a | |
| href="#gcroot">stack roots</a>, and the heap tracing routines can propagate the | |
| information. In addition, LLVM allows the front-end to extract GC information | |
| in any form from a specific object pointer (this supports situations #1 and #3). | |
| </p> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_section"> | |
| <a name="references">References</a> | |
| </div> | |
| <!-- *********************************************************************** --> | |
| <div class="doc_text"> | |
| <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> |