<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
<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 (unsigned e = R->Map->NumRoots; i != e; ++i)
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>(...) <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
calls with the corresponding <tt>load</tt> or <tt>store</tt> instruction if they
are used.</p>
-</div>
-
<!-- ======================================================================= -->
-<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
<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
>#include "llvm/CodeGen/AsmPrinter.h"
#include "llvm/Function.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetData.h"
+#include "llvm/DataLayout.h"
#include "llvm/Target/TargetAsmInfo.h"
void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP,
// Set up for emitting addresses.
const char *AddressDirective;
int AddressAlignLog;
- if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) {
+ if (AP.TM.getDataLayout()->getPointerSize() == sizeof(int32_t)) {
AddressDirective = TAI.getData32bitsDirective();
AddressAlignLog = 2;
} else {
</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