Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 7eb01bfc1645abbed0ee898a5df7ff9e4f407c38 / . / docs / GarbageCollection.html
blob: 91768f1e53397a3a2851ae231b947c83f262e7a8 [file] [log] [blame]
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]5 <meta http-equiv="Content-Type" Content="text/html; charset=UTF-8" >
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]6 <title>Accurate Garbage Collection with LLVM</title>
7 <link rel="stylesheet" href="llvm.css" type="text/css">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]8 <style type="text/css">
9 .rowhead { text-align: left; background: inherit; }
10 .indent { padding-left: 1em; }
11 .optl { color: #BFBFBF; }
12 </style>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]13</head>
14<body>
15
16<div class="doc_title">
17 Accurate Garbage Collection with LLVM
18</div>
19
20<ol>
21 <li><a href="#introduction">Introduction</a>
22 <ul>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]23 <li><a href="#feature">GC features provided and algorithms
24 supported</a></li>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]25 </ul>
26 </li>
27
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]28 <li><a href="#usage">Using the collectors</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]29 <ul>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]30 <li><a href="#shadow-stack">ShadowStack -
31 A highly portable collector</a></li>
32 <li><a href="#semispace">SemiSpace -
33 A simple copying collector runtime</a></li>
34 <li><a href="#ocaml">Ocaml -
35 An Objective Caml-compatible collector</a></li>
36 </ul>
37 </li>
38
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]39 <li><a href="#core">Core support</a>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]40 <ul>
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]41 <li><a href="#gcattr">Specifying GC code generation:
42 <tt>gc "..."</tt></a></li>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]43 <li><a href="#gcroot">Identifying GC roots on the stack:
44 <tt>llvm.gcroot</tt></a></li>
45 <li><a href="#barriers">Reading and writing references in the heap</a>
46 <ul>
47 <li><a href="#gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a></li>
48 <li><a href="#gcread">Read barrier: <tt>llvm.gcread</tt></a></li>
49 </ul>
50 </li>
51 </ul>
52 </li>
53
54 <li><a href="#runtime">Recommended runtime interface</a>
55 <ul>
56 <li><a href="#initialize">Garbage collector startup and
57 initialization</a></li>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]58 <li><a href="#allocate">Allocating memory from the GC</a></li>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]59 <li><a href="#explicit">Explicit invocation of the garbage
60 collector</a></li>
61 <li><a href="#traceroots">Tracing GC pointers from the program
62 stack</a></li>
63 <li><a href="#staticroots">Tracing GC pointers from static roots</a></li>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]64 </ul>
65 </li>
66
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]67 <li><a href="#plugin">Implementing a collector plugin</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]68 <ul>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]69 <li><a href="#collector-algos">Overview of available features</a></li>
70 <li><a href="#stack-map">Computing stack maps</a></li>
71 <li><a href="#init-roots">Initializing roots to null:
72 <tt>InitRoots</tt></a></li>
73 <li><a href="#custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
74 <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a></li>
75 <li><a href="#safe-points">Generating safe points:
76 <tt>NeededSafePoints</tt></a></li>
77 <li><a href="#assembly">Emitting assembly code:
78 <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a></li>
Chris Lattner0b02dbc2004-07-09 05:03:54 +0000[diff] [blame]79 </ul>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]80 </li>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]81
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]82 <li><a href="#runtime-impl">Implementing a collector runtime</a>
83 <ul>
84 <li><a href="#gcdescriptors">Tracing GC pointers from heap
85 objects</a></li>
86 </ul>
87 </li>
88
89 <li><a href="#references">References</a></li>
90
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]91</ol>
92
93<div class="doc_author">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]94 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and
95 Gordon Henriksen</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]96</div>
97
98<!-- *********************************************************************** -->
99<div class="doc_section">
100 <a name="introduction">Introduction</a>
101</div>
102<!-- *********************************************************************** -->
103
104<div class="doc_text">
105
106<p>Garbage collection is a widely used technique that frees the programmer from
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]107having to know the lifetimes of heap objects, making software easier to produce
108and maintain. Many programming languages rely on garbage collection for
109automatic memory management. There are two primary forms of garbage collection:
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]110conservative and accurate.</p>
111
112<p>Conservative garbage collection often does not require any special support
113from either the language or the compiler: it can handle non-type-safe
114programming languages (such as C/C++) and does not require any special
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]115information from the compiler. The
Jeff Cohen65fc36b2007-04-18 17:26:14 +0000[diff] [blame]116<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is
117an example of a state-of-the-art conservative collector.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]118
119<p>Accurate garbage collection requires the ability to identify all pointers in
120the program at run-time (which requires that the source-language be type-safe in
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]121most cases). Identifying pointers at run-time requires compiler support to
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]122locate all places that hold live pointer variables at run-time, including the
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]123<a href="#gcroot">processor stack and registers</a>.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]124
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]125<p>Conservative garbage collection is attractive because it does not require any
126special compiler support, but it does have problems. In particular, because the
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]127conservative garbage collector cannot <i>know</i> that a particular word in the
128machine is a pointer, it cannot move live objects in the heap (preventing the
129use of compacting and generational GC algorithms) and it can occasionally suffer
130from memory leaks due to integer values that happen to point to objects in the
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]131program. In addition, some aggressive compiler transformations can break
132conservative garbage collectors (though these seem rare in practice).</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]133
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]134<p>Accurate garbage collectors do not suffer from any of these problems, but
135they can suffer from degraded scalar optimization of the program. In particular,
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]136because the runtime must be able to identify and update all pointers active in
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]137the program, some optimizations are less effective. In practice, however, the
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]138locality and performance benefits of using aggressive garbage allocation
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]139techniques dominates any low-level losses.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]140
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]141<p>This document describes the mechanisms and interfaces provided by LLVM to
142support accurate garbage collection.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]143
144</div>
145
146<!-- ======================================================================= -->
147<div class="doc_subsection">
148 <a name="feature">GC features provided and algorithms supported</a>
149</div>
150
151<div class="doc_text">
152
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]153<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]154collection intrinsics</a> that offer support for a broad class of
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]155collector models. For instance, the intrinsics permit:</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]156
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]157<ul>
158 <li>semi-space collectors</li>
159 <li>mark-sweep collectors</li>
160 <li>generational collectors</li>
161 <li>reference counting</li>
162 <li>incremental collectors</li>
163 <li>concurrent collectors</li>
164 <li>cooperative collectors</li>
165</ul>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]166
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]167<p>We hope that the primitive support built into the LLVM IR is sufficient to
168support a broad class of garbage collected languages including Scheme, ML, Java,
169C#, Perl, Python, Lua, Ruby, other scripting languages, and more.</p>
170
171<p>However, LLVM does not itself implement a garbage collector. This is because
172collectors are tightly coupled to object models, and LLVM is agnostic to object
173models. Since LLVM is agnostic to object models, it would be inappropriate for
174LLVM to dictate any particular collector. Instead, LLVM provides a framework for
175garbage collector implementations in two manners:</p>
176
177<ul>
178 <li><b>At compile time</b> with <a href="#plugin">collector plugins</a> for
179 the compiler. Collector plugins have ready access to important garbage
180 collector algorithms. Leveraging these tools, it is straightforward to
181 emit type-accurate stack maps for your runtime in as little as ~100 lines of
182 C++ code.</li>
183
184 <li><b>At runtime</b> with <a href="#runtime">suggested runtime
185 interfaces</a>, which allow front-end compilers to support a range of
186 collection runtimes.</li>
187</ul>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]188
189</div>
190
191<!-- *********************************************************************** -->
192<div class="doc_section">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]193 <a name="usage">Using the collectors</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]194</div>
195<!-- *********************************************************************** -->
196
197<div class="doc_text">
198
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]199<p>In general, using a collector implies:</p>
200
201<ul>
202 <li>Emitting compatible code, including initialization in the main
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]203 program if necessary.</li>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]204 <li>Loading a compiler plugin if the collector is not statically linked with
205 your compiler. For <tt>llc</tt>, use the <tt>-load</tt> option.</li>
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]206 <li>Selecting the collection algorithm by applying the <tt>gc "..."</tt>
207 attribute to your garbage collected functions, or equivalently with
208 the <tt>setCollector</tt> method.</li>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]209 <li>Linking your final executable with the garbage collector runtime.</li>
210</ul>
211
212<p>This table summarizes the available runtimes.</p>
213
214<table>
215 <tr>
216 <th>Collector</th>
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]217 <th><tt>gc</tt> attribute</th>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]218 <th>Linkage</th>
219 <th><tt>gcroot</tt></th>
220 <th><tt>gcread</tt></th>
221 <th><tt>gcwrite</tt></th>
222 </tr>
223 <tr valign="baseline">
224 <td><a href="#semispace">SemiSpace</a></td>
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]225 <td><tt>gc "shadow-stack"</tt></td>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]226 <td>TODO FIXME</td>
227 <td>required</td>
228 <td>optional</td>
229 <td>optional</td>
230 </tr>
231 <tr valign="baseline">
232 <td><a href="#ocaml">Ocaml</a></td>
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]233 <td><tt>gc "ocaml"</tt></td>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]234 <td><i>provided by ocamlopt</i></td>
235 <td>required</td>
236 <td>optional</td>
237 <td>optional</td>
238 </tr>
239</table>
240
241<p>The sections for <a href="#intrinsics">Collection intrinsics</a> and
242<a href="#runtime">Recommended runtime interface</a> detail the interfaces that
243collectors may require user programs to utilize.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]244
245</div>
246
247<!-- ======================================================================= -->
248<div class="doc_subsection">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]249 <a name="shadow-stack">ShadowStack - A highly portable collector</a>
250</div>
251
252<div class="doc_code"><tt>
253 Collector *llvm::createShadowStackCollector();
254</tt></div>
255
256<div class="doc_text">
257
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]258<p>The ShadowStack backend is invoked with the <tt>gc "shadow-stack"</tt>
259function attribute.
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]260Unlike many collectors which rely on a cooperative code generator to generate
261stack maps, this algorithm carefully maintains a linked list of stack root
262descriptors [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]263stack" mirrors the machine stack. Maintaining this data structure is slower
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]264than using stack maps, but has a significant portability advantage because it
265requires no special support from the target code generator.</p>
266
267<p>The ShadowStack collector does not use read or write barriers, so the user
268program may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt>
269and <tt>llvm.gcwrite</tt>.</p>
270
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]271<p>ShadowStack is a code generator plugin only. It must be paired with a
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]272compatible runtime.</p>
273
274</div>
275
276<!-- ======================================================================= -->
277<div class="doc_subsection">
278 <a name="semispace">SemiSpace - A simple copying collector runtime</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]279</div>
280
281<div class="doc_text">
282
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]283<p>The SemiSpace runtime implements the <a href="runtime">suggested
284runtime interface</a> and is compatible with the ShadowStack backend.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]285
286<p>SemiSpace is a very simple copying collector. When it starts up, it
287allocates two blocks of memory for the heap. It uses a simple bump-pointer
288allocator to allocate memory from the first block until it runs out of space.
289When it runs out of space, it traces through all of the roots of the program,
290copying blocks to the other half of the memory space.</p>
291
292<p>This runtime is highly experimental and has not been used in a real project.
293Enhancements would be welcomed.</p>
294
295</div>
296
297<!-- ======================================================================= -->
298<div class="doc_subsection">
299 <a name="ocaml">Ocaml - An Objective Caml-compatible collector</a>
300</div>
301
302<div class="doc_code"><tt>
303 Collector *llvm::createOcamlCollector();
304</tt></div>
305
306<div class="doc_text">
307
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]308<p>The ocaml backend is invoked with the <tt>gc "ocaml"</tt> function attribute.
309It supports the
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]310<a href="http://caml.inria.fr/">Objective Caml</a> language runtime by emitting
311a type-accurate stack map in the form of an ocaml 3.10.0-compatible frametable.
312The linkage requirements are satisfied automatically by the <tt>ocamlopt</tt>
313compiler when linking an executable.</p>
314
315<p>The ocaml collector does not use read or write barriers, so the user program
316may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt> and
317<tt>llvm.gcwrite</tt>.</p>
318
319</div>
320
321
322<!-- *********************************************************************** -->
323<div class="doc_section">
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]324 <a name="core">Core support</a><a name="intrinsics"></a>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]325</div>
326<!-- *********************************************************************** -->
327
328<div class="doc_text">
329
330<p>This section describes the garbage collection facilities provided by the
331<a href="LangRef.html">LLVM intermediate representation</a>.</p>
332
333<p>These facilities are limited to those strictly necessary for compilation.
334They are not intended to be a complete interface to any garbage collector.
335Notably, heap allocation is not among the supplied primitives. A user program
336will also need to interface with the runtime, using either the
337<a href="#runtime">suggested runtime interface</a> or another interface
338specified by the runtime.</p>
339
340</div>
341
342<!-- ======================================================================= -->
343<div class="doc_subsection">
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]344 <a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a>
345</div>
346
347<div class="doc_code"><tt>
348 define <i>ty</i> @<i>name</i>(...) <u>gc "<i>collector</i>"</u> { ...
349</tt></div>
350
351<div class="doc_text">
352
353<p>The <tt>gc</tt> function attribute is used to specify the desired collector
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]354algorithm to the compiler. It is equivalent to specifying the collector name
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]355programmatically using the <tt>setCollector</tt> method of
356<tt>Function</tt>.</p>
357
358<p>Specifying the collector on a per-function basis allows LLVM to link together
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]359programs that use different garbage collection algorithms.</p>
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]360
361</div>
362
363<!-- ======================================================================= -->
364<div class="doc_subsection">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]365 <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
366</div>
367
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]368<div class="doc_code"><tt>
Chris Lattner17340552008-04-24 06:00:30 +0000[diff] [blame]369 void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]370</tt></div>
371
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]372<div class="doc_text">
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]373
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]374<p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]375variable on the stack. The first argument <b>must</b> be a value referring to an alloca instruction
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]376or a bitcast of an alloca. The second contains a pointer to metadata that
377should be associated with the pointer, and <b>must</b> be a constant or global
378value address. If your target collector uses tags, use a null pointer for
379metadata.</p>
380
381<p>Consider the following fragment of Java code:</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]382
383<pre>
384 {
385 Object X; // A null-initialized reference to an object
386 ...
387 }
388</pre>
389
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]390<p>This block (which may be located in the middle of a function or in a loop
391nest), could be compiled to this LLVM code:</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]392
393<pre>
394Entry:
395 ;; In the entry block for the function, allocate the
396 ;; stack space for X, which is an LLVM pointer.
397 %X = alloca %Object*
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]398
399 ;; Tell LLVM that the stack space is a stack root.
400 ;; Java has type-tags on objects, so we pass null as metadata.
401 %tmp = bitcast %Object** %X to i8**
Chris Lattner17340552008-04-24 06:00:30 +0000[diff] [blame]402 call void @llvm.gcroot(i8** %X, i8* null)
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]403 ...
404
405 ;; "CodeBlock" is the block corresponding to the start
Reid Spencer03d186a2004-05-25 08:45:31 +0000[diff] [blame]406 ;; of the scope above.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]407CodeBlock:
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]408 ;; Java null-initializes pointers.
409 store %Object* null, %Object** %X
410
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]411 ...
412
413 ;; As the pointer goes out of scope, store a null value into
414 ;; it, to indicate that the value is no longer live.
415 store %Object* null, %Object** %X
416 ...
417</pre>
418
419</div>
420
421<!-- ======================================================================= -->
422<div class="doc_subsection">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]423 <a name="barriers">Reading and writing references in the heap</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]424</div>
425
426<div class="doc_text">
427
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]428<p>Some collectors need to be informed when the mutator (the program that needs
429garbage collection) either reads a pointer from or writes a pointer to a field
430of a heap object. The code fragments inserted at these points are called
431<em>read barriers</em> and <em>write barriers</em>, respectively. The amount of
432code that needs to be executed is usually quite small and not on the critical
433path of any computation, so the overall performance impact of the barrier is
434tolerable.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]435
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]436<p>Barriers often require access to the <em>object pointer</em> rather than the
437<em>derived pointer</em> (which is a pointer to the field within the
438object). Accordingly, these intrinsics take both pointers as separate arguments
439for completeness. In this snippet, <tt>%object</tt> is the object pointer, and
440<tt>%derived</tt> is the derived pointer:</p>
441
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]442<blockquote><pre>
443 ;; An array type.
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]444 %class.Array = type { %class.Object, i32, [0 x %class.Object*] }
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]445 ...
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]446
447 ;; Load the object pointer from a gcroot.
448 %object = load %class.Array** %object_addr
449
450 ;; Compute the derived pointer.
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]451 %derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]452
453</div>
454
455<!-- ======================================================================= -->
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]456<div class="doc_subsubsection">
457 <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]458</div>
459
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]460<div class="doc_code"><tt>
461void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
462</tt></div>
463
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]464<div class="doc_text">
465
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]466<p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic
467function. It has exactly the same semantics as a non-volatile <tt>store</tt> to
468the derived pointer (the third argument).</p>
469
470<p>Many important algorithms require write barriers, including generational
471and concurrent collectors. Additionally, write barriers could be used to
472implement reference counting.</p>
473
474<p>The use of this intrinsic is optional if the target collector does use
475write barriers. If so, the collector will replace it with the corresponding
476<tt>store</tt>.</p>
477
478</div>
479
480<!-- ======================================================================= -->
481<div class="doc_subsubsection">
482 <a name="gcread">Read barrier: <tt>llvm.gcread</tt></a>
483</div>
484
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]485<div class="doc_code"><tt>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]486i8* @llvm.gcread(i8* %object, i8** %derived)<br>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]487</tt></div>
488
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]489<div class="doc_text">
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]490
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]491<p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function.
492It has exactly the same semantics as a non-volatile <tt>load</tt> from the
493derived pointer (the second argument).</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]494
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]495<p>Read barriers are needed by fewer algorithms than write barriers, and may
496have a greater performance impact since pointer reads are more frequent than
497writes.</p>
498
499<p>As with <tt>llvm.gcwrite</tt>, a target collector might not require the use
500of this intrinsic.</p>
501
502</div>
503
504<!-- *********************************************************************** -->
505<div class="doc_section">
506 <a name="runtime">Recommended runtime interface</a>
507</div>
508<!-- *********************************************************************** -->
509
510<div class="doc_text">
511
512<p>LLVM specifies the following recommended runtime interface to the garbage
513collection at runtime. A program should use these interfaces to accomplish the
514tasks not supported by the intrinsics.</p>
515
516<p>Unlike the intrinsics, which are integral to LLVM's code generator, there is
517nothing unique about these interfaces; a front-end compiler and runtime are free
518to agree to a different specification.</p>
519
520<p class="doc_warning">Note: This interface is a work in progress.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]521
522</div>
523
524<!-- ======================================================================= -->
525<div class="doc_subsection">
526 <a name="initialize">Garbage collector startup and initialization</a>
527</div>
528
529<div class="doc_text">
530
531<div class="doc_code"><tt>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]532 void llvm_gc_initialize(unsigned InitialHeapSize);
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]533</tt></div>
534
535<p>
536The <tt>llvm_gc_initialize</tt> function should be called once before any other
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]537garbage collection functions are called. This gives the garbage collector the
538chance to initialize itself and allocate the heap. The initial heap size to
539allocate should be specified as an argument.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]540</p>
541
542</div>
543
544<!-- ======================================================================= -->
545<div class="doc_subsection">
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]546 <a name="allocate">Allocating memory from the GC</a>
547</div>
548
549<div class="doc_text">
550
551<div class="doc_code"><tt>
552 void *llvm_gc_allocate(unsigned Size);
553</tt></div>
554
555<p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the
556garbage collector implementation to allocate memory. It returns a
557zeroed-out block of memory of the specified size, sufficiently aligned to store
558any object.</p>
559
560</div>
561
562<!-- ======================================================================= -->
563<div class="doc_subsection">
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]564 <a name="explicit">Explicit invocation of the garbage collector</a>
565</div>
566
567<div class="doc_text">
568
569<div class="doc_code"><tt>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]570 void llvm_gc_collect();
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]571</tt></div>
572
573<p>
574The <tt>llvm_gc_collect</tt> function is exported by the garbage collector
575implementations to provide a full collection, even when the heap is not
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]576exhausted. This can be used by end-user code as a hint, and may be ignored by
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]577the garbage collector.
578</p>
579
580</div>
581
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]582<!-- ======================================================================= -->
583<div class="doc_subsection">
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]584 <a name="traceroots">Tracing GC pointers from the program stack</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]585</div>
586
587<div class="doc_text">
588 <div class="doc_code"><tt>
589 void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
590 </tt></div>
591
592<p>
593The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code
594generator that iterates through all of the GC roots on the stack, calling the
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]595specified function pointer with each record. For each GC root, the address of
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]596the pointer and the meta-data (from the <a
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]597href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]598</p>
599</div>
600
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]601<!-- ======================================================================= -->
602<div class="doc_subsection">
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]603 <a name="staticroots">Tracing GC pointers from static roots</a>
604</div>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]605
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]606<div class="doc_text">
607TODO
608</div>
609
610
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]611<!-- *********************************************************************** -->
612<div class="doc_section">
613 <a name="plugin">Implementing a collector plugin</a>
614</div>
615<!-- *********************************************************************** -->
616
617<div class="doc_text">
618
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]619<p>User code specifies which collector plugin to use with the <tt>gc</tt>
620function attribute or, equivalently, with the <tt>setCollector</tt> method of
621<tt>Function</tt>.</p>
622
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]623<p>To implement a collector plugin, it is necessary to subclass
624<tt>llvm::Collector</tt>, which can be accomplished in a few lines of
625boilerplate code. LLVM's infrastructure provides access to several important
626algorithms. For an uncontroversial collector, all that remains may be to emit
627the assembly code for the collector's unique stack map data structure, which
628might be accomplished in as few as 100 LOC.</p>
629
630<p>To subclass <tt>llvm::Collector</tt> and register a collector:</p>
631
632<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM collector plugin
633
634#include "llvm/CodeGen/Collector.h"
635#include "llvm/CodeGen/Collectors.h"
636#include "llvm/CodeGen/CollectorMetadata.h"
637#include "llvm/Support/Compiler.h"
638
639using namespace llvm;
640
641namespace {
642 class VISIBILITY_HIDDEN MyCollector : public Collector {
643 public:
644 MyCollector() {}
645 };
646
647 CollectorRegistry::Add&lt;MyCollector&gt;
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]648 X("mygc", "My bespoke garbage collector.");
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]649}</pre></blockquote>
650
651<p>Using the LLVM makefiles (like the <a
652href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample
653project</a>), this can be built into a plugin using a simple makefile:</p>
654
655<blockquote><pre
656># lib/MyGC/Makefile
657
658LEVEL := ../..
659LIBRARYNAME = <var>MyGC</var>
660LOADABLE_MODULE = 1
661
662include $(LEVEL)/Makefile.common</pre></blockquote>
663
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]664<p>Once the plugin is compiled, code using it may be compiled using <tt>llc
665-load=<var>MyGC.so</var></tt> (though <var>MyGC.so</var> may have some other
666platform-specific extension):</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]667
668<blockquote><pre
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]669>$ cat sample.ll
670define void @f() gc "mygc" {
671entry:
672 ret void
673}
674$ llvm-as &lt; sample.ll | llc -load=MyGC.so</pre></blockquote>
675
676<p>It is also possible to statically link the collector plugin into tools, such
677as a language-specific compiler front-end.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]678
679</div>
680
681<!-- ======================================================================= -->
682<div class="doc_subsection">
683 <a name="collector-algos">Overview of available features</a>
684</div>
685
686<div class="doc_text">
687
688<p>The boilerplate collector above does nothing. More specifically:</p>
689
690<ul>
691 <li><tt>llvm.gcread</tt> calls are replaced with the corresponding
692 <tt>load</tt> instruction.</li>
693 <li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding
694 <tt>store</tt> instruction.</li>
695 <li>No stack map is emitted, and no safe points are added.</li>
696</ul>
697
698<p><tt>Collector</tt> provides a range of features through which a plugin
699collector may do useful work. This matrix summarizes the supported (and planned)
700features and correlates them with the collection techniques which typically
701require them.</p>
702
703<table>
704 <tr>
705 <th>Algorithm</th>
706 <th>Done</th>
707 <th>shadow stack</th>
708 <th>refcount</th>
709 <th>mark-sweep</th>
710 <th>copying</th>
711 <th>incremental</th>
712 <th>threaded</th>
713 <th>concurrent</th>
714 </tr>
715 <tr>
716 <th class="rowhead"><a href="#stack-map">stack map</a></th>
717 <td>&#10004;</td>
718 <td></td>
719 <td></td>
720 <td>&#10008;</td>
721 <td>&#10008;</td>
722 <td>&#10008;</td>
723 <td>&#10008;</td>
724 <td>&#10008;</td>
725 </tr>
726 <tr>
727 <th class="rowhead"><a href="#init-roots">initialize roots</a></th>
728 <td>&#10004;</td>
729 <td>&#10008;</td>
730 <td>&#10008;</td>
731 <td>&#10008;</td>
732 <td>&#10008;</td>
733 <td>&#10008;</td>
734 <td>&#10008;</td>
735 <td>&#10008;</td>
736 </tr>
737 <tr class="doc_warning">
738 <th class="rowhead">derived pointers</th>
739 <td>NO</td>
740 <td></td>
741 <td></td>
742 <td></td>
743 <td></td>
744 <td></td>
745 <td>&#10008;*</td>
746 <td>&#10008;*</td>
747 </tr>
748 <tr>
749 <th class="rowhead"><em><a href="#custom">custom lowering</a></em></th>
750 <td>&#10004;</td>
751 <th></th>
752 <th></th>
753 <th></th>
754 <th></th>
755 <th></th>
756 <th></th>
757 <th></th>
758 </tr>
759 <tr>
760 <th class="rowhead indent">gcroot</th>
761 <td>&#10004;</td>
762 <td>&#10008;</td>
763 <td>&#10008;</td>
764 <td></td>
765 <td></td>
766 <td></td>
767 <td></td>
768 <td></td>
769 </tr>
770 <tr>
771 <th class="rowhead indent">gcwrite</th>
772 <td>&#10004;</td>
773 <td></td>
774 <td>&#10008;</td>
775 <td></td>
776 <td></td>
777 <td>&#10008;</td>
778 <td></td>
779 <td>&#10008;</td>
780 </tr>
781 <tr>
782 <th class="rowhead indent">gcread</th>
783 <td>&#10004;</td>
784 <td></td>
785 <td></td>
786 <td></td>
787 <td></td>
788 <td></td>
789 <td></td>
790 <td>&#10008;</td>
791 </tr>
792 <tr>
793 <th class="rowhead"><em><a href="#safe-points">safe points</a></em></th>
794 <td></td>
795 <th></th>
796 <th></th>
797 <th></th>
798 <th></th>
799 <th></th>
800 <th></th>
801 <th></th>
802 </tr>
803 <tr>
804 <th class="rowhead indent">in calls</th>
805 <td>&#10004;</td>
806 <td></td>
807 <td></td>
808 <td>&#10008;</td>
809 <td>&#10008;</td>
810 <td>&#10008;</td>
811 <td>&#10008;</td>
812 <td>&#10008;</td>
813 </tr>
814 <tr>
815 <th class="rowhead indent">before calls</th>
816 <td>&#10004;</td>
817 <td></td>
818 <td></td>
819 <td></td>
820 <td></td>
821 <td></td>
822 <td>&#10008;</td>
823 <td>&#10008;</td>
824 </tr>
825 <tr class="doc_warning">
826 <th class="rowhead indent">for loops</th>
827 <td>NO</td>
828 <td></td>
829 <td></td>
830 <td></td>
831 <td></td>
832 <td></td>
833 <td>&#10008;</td>
834 <td>&#10008;</td>
835 </tr>
836 <tr>
837 <th class="rowhead indent">before escape</th>
838 <td>&#10004;</td>
839 <td></td>
840 <td></td>
841 <td></td>
842 <td></td>
843 <td></td>
844 <td>&#10008;</td>
845 <td>&#10008;</td>
846 </tr>
847 <tr class="doc_warning">
848 <th class="rowhead">emit code at safe points</th>
849 <td>NO</td>
850 <td></td>
851 <td></td>
852 <td></td>
853 <td></td>
854 <td></td>
855 <td>&#10008;</td>
856 <td>&#10008;</td>
857 </tr>
858 <tr>
859 <th class="rowhead"><em>output</em></th>
860 <td></td>
861 <th></th>
862 <th></th>
863 <th></th>
864 <th></th>
865 <th></th>
866 <th></th>
867 <th></th>
868 </tr>
869 <tr>
870 <th class="rowhead indent"><a href="#assembly">assembly</a></th>
871 <td>&#10004;</td>
872 <td></td>
873 <td></td>
874 <td>&#10008;</td>
875 <td>&#10008;</td>
876 <td>&#10008;</td>
877 <td>&#10008;</td>
878 <td>&#10008;</td>
879 </tr>
880 <tr class="doc_warning">
881 <th class="rowhead indent">JIT</th>
882 <td>NO</td>
883 <td></td>
884 <td></td>
885 <td class="optl">&#10008;</td>
886 <td class="optl">&#10008;</td>
887 <td class="optl">&#10008;</td>
888 <td class="optl">&#10008;</td>
889 <td class="optl">&#10008;</td>
890 </tr>
891 <tr class="doc_warning">
892 <th class="rowhead indent">obj</th>
893 <td>NO</td>
894 <td></td>
895 <td></td>
896 <td class="optl">&#10008;</td>
897 <td class="optl">&#10008;</td>
898 <td class="optl">&#10008;</td>
899 <td class="optl">&#10008;</td>
900 <td class="optl">&#10008;</td>
901 </tr>
902 <tr class="doc_warning">
903 <th class="rowhead">live analysis</th>
904 <td>NO</td>
905 <td></td>
906 <td></td>
907 <td class="optl">&#10008;</td>
908 <td class="optl">&#10008;</td>
909 <td class="optl">&#10008;</td>
910 <td class="optl">&#10008;</td>
911 <td class="optl">&#10008;</td>
912 </tr>
913 <tr class="doc_warning">
914 <th class="rowhead">register map</th>
915 <td>NO</td>
916 <td></td>
917 <td></td>
918 <td class="optl">&#10008;</td>
919 <td class="optl">&#10008;</td>
920 <td class="optl">&#10008;</td>
921 <td class="optl">&#10008;</td>
922 <td class="optl">&#10008;</td>
923 </tr>
924 <tr>
925 <td colspan="10">
926 <div><span class="doc_warning">*</span> Derived pointers only pose a
927 hazard to copying collectors.</div>
928 <div><span class="optl">&#10008;</span> in gray denotes a feature which
929 could be utilized if available.</div>
930 </td>
931 </tr>
932</table>
933
934<p>To be clear, the collection techniques above are defined as:</p>
935
936<dl>
937 <dt>Shadow Stack</dt>
938 <dd>The mutator carefully maintains a linked list of stack root
939 descriptors.</dd>
940 <dt>Reference Counting</dt>
941 <dd>The mutator maintains a reference count for each object and frees an
942 object when its count falls to zero.</dd>
943 <dt>Mark-Sweep</dt>
944 <dd>When the heap is exhausted, the collector marks reachable objects starting
945 from the roots, then deallocates unreachable objects in a sweep
946 phase.</dd>
947 <dt>Copying</dt>
948 <dd>As reachability analysis proceeds, the collector copies objects from one
949 heap area to another, compacting them in the process. Copying collectors
950 enable highly efficient "bump pointer" allocation and can improve locality
951 of reference.</dd>
952 <dt>Incremental</dt>
953 <dd>(Including generational collectors.) Incremental collectors generally have
954 all the properties of a copying collector (regardless of whether the
955 mature heap is compacting), but bring the added complexity of requiring
956 write barriers.</dd>
957 <dt>Threaded</dt>
958 <dd>Denotes a multithreaded mutator; the collector must still stop the mutator
959 ("stop the world") before beginning reachability analysis. Stopping a
960 multithreaded mutator is a complicated problem. It generally requires
961 highly platform specific code in the runtime, and the production of
962 carefully designed machine code at safe points.</dd>
963 <dt>Concurrent</dt>
964 <dd>In this technique, the mutator and the collector run concurrently, with
965 the goal of eliminating pause times. In a <em>cooperative</em> collector,
966 the mutator further aids with collection should a pause occur, allowing
967 collection to take advantage of multiprocessor hosts. The "stop the world"
968 problem of threaded collectors is generally still present to a limited
969 extent. Sophisticated marking algorithms are necessary. Read barriers may
970 be necessary.</dd>
971</dl>
972
973<p>As the matrix indicates, LLVM's garbage collection infrastructure is already
974suitable for a wide variety of collectors, but does not currently extend to
975multithreaded programs. This will be added in the future as there is
976interest.</p>
977
978</div>
979
980<!-- ======================================================================= -->
981<div class="doc_subsection">
982 <a name="stack-map">Computing stack maps</a>
983</div>
984
985<div class="doc_text">
986
987<blockquote><pre
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]988>for (iterator I = begin(), E = end(); I != E; ++I) {
989 CollectorMetadata *MD = *I;
990 unsigned FrameSize = MD-&gt;getFrameSize();
991 size_t RootCount = MD-&gt;roots_size();
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]992
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]993 for (CollectorMetadata::roots_iterator RI = MD-&gt;roots_begin(),
994 RE = MD-&gt;roots_end();
995 RI != RE; ++RI) {
996 int RootNum = RI->Num;
997 int RootStackOffset = RI->StackOffset;
998 Constant *RootMetadata = RI->Metadata;
999 }
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1000}</pre></blockquote>
1001
1002<p>LLVM automatically computes a stack map. All a <tt>Collector</tt> needs to do
1003is access it using <tt>CollectorMetadata::roots_begin()</tt> and
1004-<tt>end()</tt>. If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code
1005generation by a custom lowering pass, LLVM's stack map will be empty.</p>
1006
1007</div>
1008
1009
1010<!-- ======================================================================= -->
1011<div class="doc_subsection">
1012 <a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a>
1013</div>
1014
1015<div class="doc_text">
1016
1017<blockquote><pre
1018>MyCollector::MyCollector() {
1019 InitRoots = true;
1020}</pre></blockquote>
1021
1022<p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon
1023entry to the function. This prevents the reachability analysis from finding
1024uninitialized values in stack roots at runtime, which will almost certainly
1025cause it to segfault. This initialization occurs before custom lowering, so the
1026two may be used together.</p>
1027
1028<p>Since LLVM does not yet compute liveness information, this feature should be
1029used by all collectors which do not custom lower <tt>llvm.gcroot</tt>, and even
1030some that do.</p>
1031
1032</div>
1033
1034
1035<!-- ======================================================================= -->
1036<div class="doc_subsection">
1037 <a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
1038 <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a>
1039</div>
1040
1041<div class="doc_text">
1042
1043<p>For collectors with barriers or unusual treatment of stack roots, these
1044flags allow the collector to perform any required transformation on the LLVM
1045IR:</p>
1046
1047<blockquote><pre
1048>class MyCollector : public Collector {
1049public:
1050 MyCollector() {
1051 CustomRoots = true;
1052 CustomReadBarriers = true;
1053 CustomWriteBarriers = true;
1054 }
1055
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1056 virtual bool initializeCustomLowering(Module &amp;M);
1057 virtual bool performCustomLowering(Function &amp;F);
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1058};</pre></blockquote>
1059
1060<p>If any of these flags are set, then LLVM suppresses its default lowering for
1061the corresponding intrinsics and instead passes them on to a custom lowering
1062pass specified by the collector.</p>
1063
1064<p>LLVM's default action for each intrinsic is as follows:</p>
1065
1066<ul>
1067 <li><tt>llvm.gcroot</tt>: Pass through to the code generator to generate a
1068 stack map.</li>
1069 <li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li>
1070 <li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li>
1071</ul>
1072
1073<p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified,
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1074then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the
1075corresponding barriers.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1076
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1077<p><tt>performCustomLowering</tt>, must comply with the same restrictions as <a
1078href="WritingAnLLVMPass.html#runOnFunction"><tt>runOnFunction</tt></a>, and
1079that <tt>initializeCustomLowering</tt> has the same semantics as <a
1080href="WritingAnLLVMPass.html#doInitialization_mod"><tt>doInitialization(Module
1081&amp;)</tt></a>.</p>
1082
1083<p>The following can be used as a template:</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1084
1085<blockquote><pre
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1086>#include "llvm/Module.h"
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1087#include "llvm/IntrinsicInst.h"
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1088
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1089bool MyCollector::initializeCustomLowering(Module &amp;M) {
1090 return false;
1091}
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1092
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1093bool MyCollector::performCustomLowering(Function &amp;F) {
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1094 bool MadeChange = false;
1095
1096 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
Gordon Henriksen74f4ded2007-12-22 23:34:26 +0000[diff] [blame]1097 for (BasicBlock::iterator II = BB-&gt;begin(), E = BB-&gt;end(); II != E; )
1098 if (IntrinsicInst *CI = dyn_cast&lt;IntrinsicInst&gt;(II++))
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1099 if (Function *F = CI-&gt;getCalledFunction())
1100 switch (F-&gt;getIntrinsicID()) {
1101 case Intrinsic::gcwrite:
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1102 // Handle llvm.gcwrite.
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1103 CI-&gt;eraseFromParent();
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1104 MadeChange = true;
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1105 break;
1106 case Intrinsic::gcread:
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1107 // Handle llvm.gcread.
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1108 CI-&gt;eraseFromParent();
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1109 MadeChange = true;
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1110 break;
1111 case Intrinsic::gcroot:
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1112 // Handle llvm.gcroot.
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1113 CI-&gt;eraseFromParent();
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1114 MadeChange = true;
Gordon Henriksen0adede02007-12-22 23:32:32 +0000[diff] [blame]1115 break;
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1116 }
1117
1118 return MadeChange;
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1119}</pre></blockquote>
1120
1121</div>
1122
1123
1124<!-- ======================================================================= -->
1125<div class="doc_subsection">
1126 <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
1127</div>
1128
1129<div class="doc_text">
1130
1131<p>LLVM can compute four kinds of safe points:</p>
1132
1133<blockquote><pre
1134>namespace GC {
1135 /// PointKind - The type of a collector-safe point.
1136 ///
1137 enum PointKind {
1138 Loop, //&lt; Instr is a loop (backwards branch).
1139 Return, //&lt; Instr is a return instruction.
1140 PreCall, //&lt; Instr is a call instruction.
1141 PostCall //&lt; Instr is the return address of a call.
1142 };
1143}</pre></blockquote>
1144
1145<p>A collector can request any combination of the four by setting the
1146<tt>NeededSafePoints</tt> mask:</p>
1147
1148<blockquote><pre
1149>MyCollector::MyCollector() {
1150 NeededSafePoints = 1 &lt;&lt; GC::Loop
1151 | 1 &lt;&lt; GC::Return
1152 | 1 &lt;&lt; GC::PreCall
1153 | 1 &lt;&lt; GC::PostCall;
1154}</pre></blockquote>
1155
1156<p>It can then use the following routines to access safe points.</p>
1157
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1158<blockquote><pre
1159>for (iterator I = begin(), E = end(); I != E; ++I) {
1160 CollectorMetadata *MD = *I;
1161 size_t PointCount = MD-&gt;size();
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1162
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1163 for (CollectorMetadata::iterator PI = MD-&gt;begin(),
1164 PE = MD-&gt;end(); PI != PE; ++PI) {
1165 GC::PointKind PointKind = PI-&gt;Kind;
1166 unsigned PointNum = PI-&gt;Num;
1167 }
1168}
1169</pre></blockquote>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1170
1171<p>Almost every collector requires <tt>PostCall</tt> safe points, since these
1172correspond to the moments when the function is suspended during a call to a
1173subroutine.</p>
1174
1175<p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee
1176that the application will reach a safe point within a bounded amount of time,
1177even if it is executing a long-running loop which contains no function
1178calls.</p>
1179
1180<p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt>
1181safe points to implement "stop the world" techniques using self-modifying code,
1182where it is important that the program not exit the function without reaching a
1183safe point (because only the topmost function has been patched).</p>
1184
1185</div>
1186
1187
1188<!-- ======================================================================= -->
1189<div class="doc_subsection">
1190 <a name="assembly">Emitting assembly code:
1191 <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a>
1192</div>
1193
1194<div class="doc_text">
1195
1196<p>LLVM allows a collector to print arbitrary assembly code before and after
1197the rest of a module's assembly code. From the latter callback, the collector
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1198can print stack maps built by the code generator.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1199
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1200<p>Note that LLVM does not currently have analogous APIs to support code
1201generation in the JIT, nor using the object writers.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1202
1203<blockquote><pre
1204>class MyCollector : public Collector {
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1205public:
1206 virtual void beginAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1207 const TargetAsmInfo &amp;TAI);
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1208
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1209 virtual void finishAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1210 const TargetAsmInfo &amp;TAI);
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1211}</pre></blockquote>
1212
1213<p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1214print portable assembly code to the <tt>std::ostream</tt>. The collector itself
1215contains the stack map for the entire module, and may access the
1216<tt>CollectorMetadata</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
1217methods. Here's a realistic example:</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1218
1219<blockquote><pre
1220>#include "llvm/CodeGen/AsmPrinter.h"
1221#include "llvm/Function.h"
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1222#include "llvm/Target/TargetMachine.h"
1223#include "llvm/Target/TargetData.h"
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1224#include "llvm/Target/TargetAsmInfo.h"
1225
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1226void MyCollector::beginAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1227 const TargetAsmInfo &amp;TAI) {
1228 // Nothing to do.
1229}
1230
1231void MyCollector::finishAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1232 const TargetAsmInfo &amp;TAI) {
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1233 // Set up for emitting addresses.
1234 const char *AddressDirective;
1235 int AddressAlignLog;
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1236 if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) {
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1237 AddressDirective = TAI.getData32bitsDirective();
1238 AddressAlignLog = 2;
1239 } else {
1240 AddressDirective = TAI.getData64bitsDirective();
1241 AddressAlignLog = 3;
1242 }
1243
1244 // Put this in the data section.
1245 AP.SwitchToDataSection(TAI.getDataSection());
1246
1247 // For each function...
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame]1248 for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1249 CollectorMetadata &amp;MD = **FI;
1250
1251 // Emit this data structure:
1252 //
1253 // struct {
1254 // int32_t PointCount;
1255 // struct {
1256 // void *SafePointAddress;
1257 // int32_t LiveCount;
1258 // int32_t LiveOffsets[LiveCount];
1259 // } Points[PointCount];
1260 // } __gcmap_&lt;FUNCTIONNAME&gt;;
1261
1262 // Align to address width.
1263 AP.EmitAlignment(AddressAlignLog);
1264
1265 // Emit the symbol by which the stack map can be found.
1266 std::string Symbol;
1267 Symbol += TAI.getGlobalPrefix();
1268 Symbol += "__gcmap_";
1269 Symbol += MD.getFunction().getName();
1270 if (const char *GlobalDirective = TAI.getGlobalDirective())
1271 OS &lt;&lt; GlobalDirective &lt;&lt; Symbol &lt;&lt; "\n";
1272 OS &lt;&lt; TAI.getGlobalPrefix() &lt;&lt; Symbol &lt;&lt; ":\n";
1273
1274 // Emit PointCount.
1275 AP.EmitInt32(MD.size());
1276 AP.EOL("safe point count");
1277
1278 // And each safe point...
1279 for (CollectorMetadata::iterator PI = MD.begin(),
1280 PE = MD.end(); PI != PE; ++PI) {
1281 // Align to address width.
1282 AP.EmitAlignment(AddressAlignLog);
1283
1284 // Emit the address of the safe point.
1285 OS &lt;&lt; AddressDirective
1286 &lt;&lt; TAI.getPrivateGlobalPrefix() &lt;&lt; "label" &lt;&lt; PI-&gt;Num;
1287 AP.EOL("safe point address");
1288
1289 // Emit the stack frame size.
1290 AP.EmitInt32(MD.getFrameSize());
1291 AP.EOL("stack frame size");
1292
1293 // Emit the number of live roots in the function.
1294 AP.EmitInt32(MD.live_size(PI));
1295 AP.EOL("live root count");
1296
1297 // And for each live root...
1298 for (CollectorMetadata::live_iterator LI = MD.live_begin(PI),
1299 LE = MD.live_end(PI);
1300 LI != LE; ++LI) {
1301 // Print its offset within the stack frame.
1302 AP.EmitInt32(LI-&gt;StackOffset);
1303 AP.EOL("stack offset");
1304 }
1305 }
1306 }
1307}
1308</pre></blockquote>
1309
1310</div>
1311
1312
1313<!-- *********************************************************************** -->
1314<div class="doc_section">
1315 <a name="runtime-impl">Implementing a collector runtime</a>
1316</div>
1317<!-- *********************************************************************** -->
1318
1319<div class="doc_text">
1320
1321<p>Implementing a garbage collector for LLVM is fairly straightforward. The
1322LLVM garbage collectors are provided in a form that makes them easy to link into
1323the language-specific runtime that a language front-end would use. They require
1324functionality from the language-specific runtime to get information about <a
1325href="#gcdescriptors">where pointers are located in heap objects</a>.</p>
1326
1327<p>The implementation must include the
1328<a href="#allocate"><tt>llvm_gc_allocate</tt></a> and
1329<a href="#explicit"><tt>llvm_gc_collect</tt></a> functions. To do this, it will
1330probably have to <a href="#traceroots">trace through the roots
1331from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]1332for heap objects</a>. Luckily, there are some <a href="#usage">example
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1333implementations</a> available.
1334</p>
1335</div>
1336
1337
1338<!-- ======================================================================= -->
1339<div class="doc_subsection">
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1340 <a name="gcdescriptors">Tracing GC pointers from heap objects</a>
1341</div>
1342
1343<div class="doc_text">
1344<p>
1345The three most common ways to keep track of where pointers live in heap objects
1346are (listed in order of space overhead required):</p>
1347
1348<ol>
1349<li>In languages with polymorphic objects, pointers from an object header are
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1350usually used to identify the GC pointers in the heap object. This is common for
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1351object-oriented languages like Self, Smalltalk, Java, or C#.</li>
1352
1353<li>If heap objects are not polymorphic, often the "shape" of the heap can be
1354determined from the roots of the heap or from some other meta-data [<a
1355href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1356href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can
1357propagate the information around from meta data stored with the roots. This
1358often eliminates the need to have a header on objects in the heap. This is
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1359common in the ML family.</li>
1360
1361<li>If all heap objects have pointers in the same locations, or pointers can be
1362distinguished just by looking at them (e.g., the low order bit is clear), no
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1363book-keeping is needed at all. This is common for Lisp-like languages.</li>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1364</ol>
1365
1366<p>The LLVM garbage collectors are capable of supporting all of these styles of
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1367language, including ones that mix various implementations. To do this, it
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1368allows the source-language to associate meta-data with the <a
Chris Lattner05d67092008-04-24 05:59:56 +0000[diff] [blame]1369href="#gcroot">stack roots</a>, and the heap tracing routines can propagate the
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1370information. In addition, LLVM allows the front-end to extract GC information
1371in any form from a specific object pointer (this supports situations #1 and #3).
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1372</p>
1373
1374</div>
1375
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1376
1377<!-- *********************************************************************** -->
1378<div class="doc_section">
1379 <a name="references">References</a>
1380</div>
1381<!-- *********************************************************************** -->
1382
1383<div class="doc_text">
1384
1385<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
1386W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
1387
1388<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1389strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1390PLDI'91.</p>
1391
1392<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1393explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1394conference on LISP and functional programming.</p>
1395
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1396<p><a name="henderson02">[Henderson2002]</a> <a
1397href="http://citeseer.ist.psu.edu/henderson02accurate.html">
1398Accurate Garbage Collection in an Uncooperative Environment</a>.
1399Fergus Henderson. International Symposium on Memory Management 2002.</p>
1400
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1401</div>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1402
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1403
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1404<!-- *********************************************************************** -->
1405
1406<hr>
1407<address>
1408 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1409 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1410 <a href="http://validator.w3.org/check/referer"><img
1411 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1412
1413 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
Reid Spencer05fe4b02006-03-14 05:39:39 +0000[diff] [blame]1414 <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1415 Last modified: $Date$
1416</address>
1417
1418</body>
1419</html>