<ol>
<li><a href="#introduction">Introduction</a>
<ul>
- <li><a href="#feature">GC features provided and algorithms
- supported</a></li>
+ <li><a href="#feature">Goals and non-goals</a></li>
</ul>
</li>
- <li><a href="#usage">Using the collectors</a>
+ <li><a href="#quickstart">Getting started</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>
+ <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>
</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>
+ <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="#safe-points">Generating safe points:
<tt>NeededSafePoints</tt></a></li>
<li><a href="#assembly">Emitting assembly code:
- <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a></li>
+ <tt>GCMetadataPrinter</tt></a></li>
</ul>
</li>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="feature">GC features provided and algorithms supported</a>
+ <a name="feature">Goals and non-goals</a>
</div>
<div class="doc_text">
<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
-collection intrinsics</a> which offer support for a broad class of
+collection intrinsics</a> that offer support for a broad class of
collector models. For instance, the intrinsics permit:</p>
<ul>
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>
+<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><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>
+ <li>Registration of global roots with the runtime.</li>
+ <li>Registration of stack map entries with the runtime.</li>
+ <li>The functions used by the program to allocate memory, trigger a
+ collection, etc.</li>
+ <li>Computation or compilation of type maps, or registration of them with
+ the runtime. These are used to crawl the heap for object
+ references.</li>
</ul>
+<p>In general, LLVM's support for GC does not include features which can be
+adequately addressed with other features of the IR and does not specify a
+particular binary interface. On the plus side, this means that you should be
+able to integrate LLVM with an existing runtime. On the other hand, it leaves
+a lot of work for the developer of a novel language. However, it's easy to get
+started quickly and scale up to a more sophisticated implementation as your
+compiler matures.</p>
+
</div>
<!-- *********************************************************************** -->
<div class="doc_section">
- <a name="usage">Using the collectors</a>
+ <a name="quickstart">Getting started</a>
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
-<p>In general, using a collector implies:</p>
+<p>Using a GC with LLVM implies many things, for example:</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>setCollector</tt> method.</li>
- <li>Linking your final executable with the garbage collector runtime.</li>
+ <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>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>
+<p>To help with several of these tasks (those indicated with a *), LLVM
+includes a highly portable, built-in ShadowStack code generator. It is compiled
+into <tt>llc</tt> and works even with the interpreter and C backends.</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="shadow-stack">ShadowStack - A highly portable collector</a>
+ <a name="quickstart-compiler">In your compiler</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>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>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>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>ShadowStack is a code generator plugin only. It must be paired with a
-compatible runtime.</p>
+<p>There's no need to use <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> over
+plain <tt>load</tt> and <tt>store</tt> for now. You will need them when
+switching to a more advanced GC.</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="semispace">SemiSpace - A simple copying collector runtime</a>
+ <a name="quickstart-runtime">In your runtime</a>
</div>
<div class="doc_text">
-<p>The SemiSpace runtime implements with the <a href="runtime">suggested
-runtime interface</a> and is compatible the ShadowStack backend.</p>
+<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>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>
+<p>When it comes time to collect, however, your runtime needs to traverse the
+stack roots, and for this it needs to integrate with the shadow stack. Luckily,
+doing so is very simple. (This code is heavily commented to help you
+understand the data structure, but there are only 20 lines of meaningful
+code.)</p>
</div>
+<div class="doc_code"><pre
+>/// @brief The map for a single function's stack frame. One of these is
+/// compiled as constant data into the executable for each function.
+///
+/// Storage of metadata values is elided if the %metadata parameter to
+/// @llvm.gcroot is null.
+struct FrameMap {
+ int32_t NumRoots; //< Number of roots in stack frame.
+ int32_t NumMeta; //< Number of metadata entries. May be < NumRoots.
+ const void *Meta[0]; //< Metadata for each root.
+};
+
+/// @brief A link in the dynamic shadow stack. One of these is embedded in the
+/// stack frame of each function on the call stack.
+struct StackEntry {
+ StackEntry *Next; //< Link to next stack entry (the caller's).
+ const FrameMap *Map; //< Pointer to constant FrameMap.
+ void *Roots[0]; //< Stack roots (in-place array).
+};
+
+/// @brief The head of the singly-linked list of StackEntries. Functions push
+/// and pop onto this in their prologue and epilogue.
+///
+/// Since there is only a global list, this technique is not threadsafe.
+StackEntry *llvm_gc_root_chain;
+
+/// @brief Calls Visitor(root, meta) for each GC root on the stack.
+/// root and meta are exactly the values passed to
+/// <tt>@llvm.gcroot</tt>.
+///
+/// Visitor could be a function to recursively mark live objects. Or it
+/// might copy them to another heap or generation.
+///
+/// @param Visitor A function to invoke for every GC root on the stack.
+void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {
+ for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {
+ unsigned i = 0;
+
+ // For roots [0, NumMeta), the metadata pointer is in the FrameMap.
+ for (unsigned e = R->Map->NumMeta; i != e; ++i)
+ Visitor(&R->Roots[i], R->Map->Meta[i]);
+
+ // For roots [NumMeta, NumRoots), the metadata pointer is null.
+ for (unsigned e = R->Map->NumRoots; i != e; ++i)
+ Visitor(&R->Roots[i], NULL);
+ }
+}</pre></div>
+
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="ocaml">Ocaml - An Objective Caml-compatible collector</a>
+ <a name="shadow-stack">About the shadow stack</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>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 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>
+<p>The tradeoff for this simplicity and portability is:</p>
-</div>
+<ul>
+ <li>High overhead per function call.</li>
+ <li>Not thread-safe.</li>
+</ul>
+<p>Still, it's an easy way to get started. After your compiler and runtime are
+up and running, writing a <a href="#plugin">plugin</a> will allow you to take
+advantage of <a href="#collector-algos">more advanced GC features</a> of LLVM
+in order to improve performance.</p>
+
+</div>
<!-- *********************************************************************** -->
<div class="doc_section">
- <a name="core">Core support</a>
+ <a name="core">IR features</a><a name="intrinsics"></a>
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
<p>This section describes the garbage collection facilities provided by the
-<a href="LangRef.html">LLVM intermediate representation</a>.</p>
+<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 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>
+<p>These facilities are limited to those strictly necessary; they are not
+intended to be a complete interface to any garbage collector. A program will
+need to interface with the GC library using the facilities provided by that
+program.</p>
</div>
</div>
<div class="doc_code"><tt>
- define <i>ty</i> @<i>name</i>(...) <u>gc "<i>collector</i>"</u> { ...
+ define <i>ty</i> @<i>name</i>(...) <u>gc "<i>name</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 specify the collector name
-programmatically using the <tt>setCollector</tt> method of
+<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>Specifying the collector on a per-function basis allows LLVM to link together
-programs which use different garbage collection algorithms.</p>
+<p>Setting <tt>gc "<i>name</i>"</tt> on a function triggers a search for a
+matching code generation plugin "<i>name</i>"; it is that plugin which defines
+the exact nature of the code generated to support GC. If none is found, the
+compiler will raise an error.</p>
+
+<p>Specifying the GC style on a per-function basis allows LLVM to link together
+programs that use different garbage collection algorithms (or none at all).</p>
</div>
</div>
<div class="doc_code"><tt>
- void %llvm.gcroot(i8** %ptrloc, i8* %metadata)
+ 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 an alloca instruction
+<p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM that a stack
+variable references an object on the heap and is to be tracked for garbage
+collection. The exact impact on generated code is specified by a <a
+href="#plugin">compiler plugin</a>.</p>
+
+<p>A compiler which uses mem2reg to raise imperative code using <tt>alloca</tt>
+into SSA form need only add a call to <tt>@llvm.gcroot</tt> for those variables
+which a pointers into the GC heap.</p>
+
+<p>It is also important to mark intermediate values with <tt>llvm.gcroot</tt>.
+For example, consider <tt>h(f(), g())</tt>. Beware leaking the result of
+<tt>f()</tt> in the case that <tt>g()</tt> triggers a collection.</p>
+
+<p>The first argument <b>must</b> be a value referring to an alloca instruction
or a bitcast of an alloca. The second contains a pointer to metadata that
should be associated with the pointer, and <b>must</b> be a constant or global
value address. If your target collector uses tags, use a null pointer for
metadata.</p>
+<p>The <tt>%metadata</tt> argument can be used to avoid requiring heap objects
+to have 'isa' pointers or tag bits. [<a href="#appel89">Appel89</a>, <a
+href="#goldberg91">Goldberg91</a>, <a href="#tolmach94">Tolmach94</a>] If
+specified, its value will be tracked along with the location of the pointer in
+the stack frame.</p>
+
<p>Consider the following fragment of Java code:</p>
<pre>
;; 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)
+ call void @llvm.gcroot(i8** %X, i8* null)
...
;; "CodeBlock" is the block corresponding to the start
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.
+<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 %obj, i32 0, i32 2, i32 %n</pre></blockquote>
+ %derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote>
+
+<p>LLVM does not enforce this relationship between the object and derived
+pointer (although a <a href="#plugin">plugin</a> might). However, it would be
+an unusual collector that violated it.</p>
+
+<p>The use of these intrinsics is naturally optional if the target GC does
+require the corresponding barrier. Such a GC plugin will replace the intrinsic
+calls with the corresponding <tt>load</tt> or <tt>store</tt> instruction if they
+are used.</p>
</div>
<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>
+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>
-<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>
<!-- ======================================================================= -->
<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>
+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>
-<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="#roots"><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 class="doc_text">
-<p>User code specifies which collector plugin to use with the <tt>gc</tt>
-function attribute or, equivalently, with the <tt>setCollector</tt> method of
+<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 collector plugin, it is necessary to subclass
-<tt>llvm::Collector</tt>, which can be accomplished in a few lines of
+<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>
+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>To subclass <tt>llvm::Collector</tt> and register a collector:</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>
-<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM collector plugin
+<p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p>
-#include "llvm/CodeGen/Collector.h"
-#include "llvm/CodeGen/Collectors.h"
-#include "llvm/CodeGen/CollectorMetadata.h"
+<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 MyCollector : public Collector {
+ class VISIBILITY_HIDDEN MyGC : public GCStrategy {
public:
- MyCollector() {}
+ MyGC() {}
};
- CollectorRegistry::Add<MyCollector>
+ 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 can be built into a plugin using a simple makefile:</p>
+project</a>), this code can be compiled as a plugin using a simple
+makefile:</p>
<blockquote><pre
># lib/MyGC/Makefile
<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>
+<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>
<dl>
<dt>Shadow Stack</dt>
- <dd>The mutator carefully maintains a linked list of stack root
- descriptors.</dd>
+ <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>
<div class="doc_text">
+<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) {
- CollectorMetadata *MD = *I;
- unsigned FrameSize = MD->getFrameSize();
- size_t RootCount = MD->roots_size();
+ GCFunctionInfo *FI = *I;
+ unsigned FrameSize = FI->getFrameSize();
+ size_t RootCount = FI->roots_size();
- for (CollectorMetadata::roots_iterator RI = MD->roots_begin(),
- RE = MD->roots_end();
- RI != RE; ++RI) {
+ 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>Collector</tt> needs to do
-is access it using <tt>CollectorMetadata::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>
+<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>
<div class="doc_text">
<blockquote><pre
->MyCollector::MyCollector() {
+>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 reachability analysis from finding
-uninitialized values in stack roots at runtime, which will almost certainly
-cause it to segfault. This initialization occurs before custom lowering, so the
-two may be used together.</p>
+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, this feature should be
-used by all collectors which do not custom lower <tt>llvm.gcroot</tt>, and even
-some that do.</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_text">
-<p>For collectors with barriers or unusual treatment of stack roots, these
-flags allow the collector to perform any required transformation on the LLVM
+<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 MyCollector : public Collector {
+>class MyGC : public GCStrategy {
public:
- MyCollector() {
+ MyGC() {
CustomRoots = true;
CustomReadBarriers = true;
CustomWriteBarriers = true;
};</pre></blockquote>
<p>If any of these flags are set, then LLVM suppresses its default lowering for
-the corresponding intrinsics and instead passes them on to a custom lowering
-pass specified by the collector.</p>
+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.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>
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>runOnFunction</tt></a>, and
-that <tt>initializeCustomLowering</tt> has the same semantics as <a
-href="WritingAnLLVMPass.html#doInitialization_mod"><tt>doInitialization(Module
-&)</tt></a>.</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/Instructions.h"
+#include "llvm/IntrinsicInst.h"
-bool MyCollector::initializeCustomLowering(Module &M) {
+bool MyGC::initializeCustomLowering(Module &M) {
return false;
}
-bool MyCollector::performCustomLowering(Function &F) {
- const Module *M = F.getParent();
-
- Function *GCReadInt = M->getFunction("llvm.gcread"),
- *GCWriteInt = M->getFunction("llvm.gcwrite"),
- *GCRootInt = M->getFunction("llvm.gcroot");
-
+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 (CallInst *CI = dyn_cast<CallInst>(II++))
- if (Function *F = CI->getCalledFunction())
- if (F == GCWriteInt) {
+ 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();
+ CI->eraseFromParent();
MadeChange = true;
- } else if (F == GCReadInt) {
+ break;
+ case Intrinsic::gcread:
// Handle llvm.gcread.
- CI->eraseFromParent();
+ CI->eraseFromParent();
MadeChange = true;
- } else if (F == GCRootInt) {
+ break;
+ case Intrinsic::gcroot:
// Handle llvm.gcroot.
- CI->eraseFromParent();
+ CI->eraseFromParent();
MadeChange = true;
+ break;
}
return MadeChange;
<tt>NeededSafePoints</tt> mask:</p>
<blockquote><pre
->MyCollector::MyCollector() {
+>MyGC::MyGC() {
NeededSafePoints = 1 << GC::Loop
| 1 << GC::Return
| 1 << GC::PreCall
<blockquote><pre
>for (iterator I = begin(), E = end(); I != E; ++I) {
- CollectorMetadata *MD = *I;
+ GCFunctionInfo *MD = *I;
size_t PointCount = MD->size();
- for (CollectorMetadata::iterator PI = MD->begin(),
- PE = MD->end(); PI != PE; ++PI) {
+ for (GCFunctionInfo::iterator PI = MD->begin(),
+ PE = MD->end(); PI != PE; ++PI) {
GC::PointKind PointKind = PI->Kind;
unsigned PointNum = PI->Num;
}
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="assembly">Emitting assembly code:
- <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a>
+ <a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a>
</div>
<div class="doc_text">
-<p>LLVM allows a collector to print arbitrary assembly code before and after
-the rest of a module's assembly code. From the latter callback, the collector
-can print stack maps built by the code generator.</p>
+<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
->class MyCollector : public Collector {
-public:
- virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
- const TargetAsmInfo &TAI);
+>// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer
- virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP,
- const TargetAsmInfo &TAI);
+#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>CollectorMetadata</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
+<tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
methods. Here's a realistic example:</p>
<blockquote><pre
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetAsmInfo.h"
-void MyCollector::beginAssembly(std::ostream &OS, AsmPrinter &AP,
+void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP,
const TargetAsmInfo &TAI) {
// Nothing to do.
}
-void MyCollector::finishAssembly(std::ostream &OS, AsmPrinter &AP,
+void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP,
const TargetAsmInfo &TAI) {
// Set up for emitting addresses.
const char *AddressDirective;
// For each function...
for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
- CollectorMetadata &MD = **FI;
+ GCFunctionInfo &MD = **FI;
// Emit this data structure:
//
// Align to address width.
AP.EmitAlignment(AddressAlignLog);
- // Emit the symbol by which the stack map can be found.
+ // Emit the symbol by which the stack map entry can be found.
std::string Symbol;
Symbol += TAI.getGlobalPrefix();
Symbol += "__gcmap_";
AP.EOL("safe point count");
// And each safe point...
- for (CollectorMetadata::iterator PI = MD.begin(),
+ for (GCFunctionInfo::iterator PI = MD.begin(),
PE = MD.end(); PI != PE; ++PI) {
// Align to address width.
AP.EmitAlignment(AddressAlignLog);
AP.EOL("live root count");
// And for each live root...
- for (CollectorMetadata::live_iterator LI = MD.live_begin(PI),
+ for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
LE = MD.live_end(PI);
LI != LE; ++LI) {
// Print its offset within the stack frame.
</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="#gcimpls">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="#roots">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>
<hr>
<address>
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ 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" alt="Valid HTML 4.01!"></a>
+ 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>
projects / oota-llvm.git / blobdiff