<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">
+ <link rel="stylesheet" href="_static/llvm.css" type="text/css">
<style type="text/css">
.rowhead { text-align: left; background: inherit; }
.indent { padding-left: 1em; }
</head>
<body>
-<div class="doc_title">
+<h1>
Accurate Garbage Collection with LLVM
-</div>
+</h1>
<ol>
<li><a href="#introduction">Introduction</a>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="introduction">Introduction</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Garbage collection is a widely used technique that frees the programmer from
having to know the lifetimes of heap objects, making software easier to produce
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
+locality and performance benefits of using aggressive garbage collection
techniques dominates any low-level losses.</p>
<p>This document describes the mechanisms and interfaces provided by LLVM to
support accurate garbage collection.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="feature">Goals and non-goals</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
collection intrinsics</a> that offer support for a broad class of
support a broad class of garbage collected languages including Scheme, ML, Java,
C#, Perl, Python, Lua, Ruby, other scripting languages, and more.</p>
-<p>However, LLVM does not itself provide a garbage collector—this should
+<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>
+of garbage collection—thus the plugins.</p>
<p>The aspects of the binary interface with which LLVM's GC support is
concerned are:</p>
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="quickstart">Getting started</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Using a GC with LLVM implies many things, for example:</p>
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">
+<h3>
<a name="quickstart-compiler">In your compiler</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>To turn the shadow stack on for your functions, first call:</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="quickstart-runtime">In your runtime</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>The shadow stack doesn't imply a memory allocation algorithm. A semispace
collector or building atop <tt>malloc</tt> are great places to start, and can
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
+<pre class="doc_code">
+/// @brief The map for a single function's stack frame. One of these is
/// compiled as constant data into the executable for each function.
///
/// Storage of metadata values is elided if the %metadata parameter to
// 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]);
+ 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);
+ Visitor(&R->Roots[i], NULL);
}
-}</pre></div>
+}</pre>
+
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="shadow-stack">About the shadow stack</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>Unlike many GC algorithms which rely on a cooperative code generator to
compile stack maps, this algorithm carefully maintains a linked list of stack
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="core">IR features</a><a name="intrinsics"></a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>This section describes the garbage collection facilities provided by the
<a href="LangRef.html">LLVM intermediate representation</a>. The exact behavior
need to interface with the GC library using the facilities provided by that
program.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a>
-</div>
+</h3>
+
+<div>
<div class="doc_code"><tt>
- define <i>ty</i> @<i>name</i>(...) <u>gc "<i>name</i>"</u> { ...
+ define <i>ty</i> @<i>name</i>(...) <span style="text-decoration: underline">gc "<i>name</i>"</span> { ...
</tt></div>
-<div class="doc_text">
-
<p>The <tt>gc</tt> function attribute is used to specify the desired GC style
to the compiler. Its programmatic equivalent is the <tt>setGC</tt> method of
<tt>Function</tt>.</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
-</div>
+</h3>
+
+<div>
<div class="doc_code"><tt>
void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
</tt></div>
-<div class="doc_text">
-
<p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM that a stack
variable references an object on the heap and is to be tracked for garbage
collection. The exact impact on generated code is specified by a <a
-href="#plugin">compiler plugin</a>.</p>
+href="#plugin">compiler plugin</a>. All calls to <tt>llvm.gcroot</tt> <b>must</b> reside
+ inside the first basic block.</p>
<p>A compiler which uses mem2reg to raise imperative code using <tt>alloca</tt>
into SSA form need only add a call to <tt>@llvm.gcroot</tt> for those variables
<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>
+<tt>f()</tt> in the case that <tt>g()</tt> triggers a collection. Note, that
+stack variables must be initialized and marked with <tt>llvm.gcroot</tt> in
+function's prologue.</p>
<p>The first argument <b>must</b> be a value referring to an alloca instruction
or a bitcast of an alloca. The second contains a pointer to metadata that
<p>Consider the following fragment of Java code:</p>
-<pre>
+<pre class="doc_code">
{
Object X; // A null-initialized reference to an object
...
<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>
+<pre class="doc_code">
Entry:
;; In the entry block for the function, allocate the
;; stack space for X, which is an LLVM pointer.
;; 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** %tmp, i8* null)
...
;; "CodeBlock" is the block corresponding to the start
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="barriers">Reading and writing references in the heap</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>Some collectors need to be informed when the mutator (the program that needs
garbage collection) either reads a pointer from or writes a pointer to a field
;; Compute the derived pointer.
%derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote>
-<p>The use of these intrinsics is naturally optional if the target GC does
-require the corresponding barrier. If so, the GC plugin will replace the
-intrinsic calls with the corresponding <tt>load</tt> or <tt>store</tt>
-instruction if they are used.</p>
-
-<p>LLVM does not enforce any particular relationship between the object and
-derived pointer (although a <a href="#plugin">plugin</a> might). However, it
-would be unusual that the derived pointer not be a <tt>getelementptr</tt> of the
-object pointer.</p>
+<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>
-</div>
+<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 class="doc_subsubsection">
+<h4>
<a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a>
-</div>
+</h4>
+
+<div>
<div class="doc_code"><tt>
void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
</tt></div>
-<div class="doc_text">
-
<p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic
function. It has exactly the same semantics as a non-volatile <tt>store</tt> to
the derived pointer (the third argument). The exact code generated is specified
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection">
+<h4>
<a name="gcread">Read barrier: <tt>llvm.gcread</tt></a>
-</div>
+</h4>
+
+<div>
<div class="doc_code"><tt>
i8* @llvm.gcread(i8* %object, i8** %derived)<br>
</tt></div>
-<div class="doc_text">
-
<p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function.
It has exactly the same semantics as a non-volatile <tt>load</tt> from the
derived pointer (the second argument). The exact code generated is specified by
</div>
+</div>
+
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="plugin">Implementing a collector plugin</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>User code specifies which GC code generation to use with the <tt>gc</tt>
function attribute or, equivalently, with the <tt>setGC</tt> method of
using namespace llvm;
namespace {
- class VISIBILITY_HIDDEN MyGC : public GCStrategy {
+ class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy {
public:
MyGC() {}
};
<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">
+<h3>
<a name="collector-algos">Overview of available features</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>GCStrategy</tt> provides a range of features through which a plugin
may do useful work. Some of these are callbacks, some are algorithms that can
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="stack-map">Computing stack maps</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>LLVM automatically computes a stack map. One of the most important features
of a <tt>GCStrategy</tt> is to compile this information into the executable in
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<blockquote><pre
>MyGC::MyGC() {
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
<tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>For GCs which use barriers or unusual treatment of stack roots, these
flags allow the collector to perform arbitrary transformations of the LLVM
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>LLVM can compute four kinds of safe points:</p>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>LLVM allows a plugin to print arbitrary assembly code before and after the
rest of a module's assembly code. At the end of the module, the GC can compile
using namespace llvm;
namespace {
- class VISIBILITY_HIDDEN MyGCPrinter : public GCMetadataPrinter {
+ class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter {
public:
virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
const TargetAsmInfo &TAI);
</div>
+</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="references">References</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
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>
+ <a href="http://llvm.org/">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff