Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / ad93c4f936d220570535711262e0fff8857f798a / . / docs / GarbageCollection.html
blob: 4b5bd50aca1c9c0899f9721a5b205086cda095ed [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
154collection intrinsics</a> which offer support for a broad class of
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
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]283<p>The SemiSpace runtime implements with the <a href="runtime">suggested
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]284runtime interface</a> and is compatible 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">
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]324 <a name="core">Core support</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
354algorithm to the compiler. It is equivalent to specify the collector name
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
359programs which use different garbage collection algorithms.</p>
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 Lattner1df4f752007-09-21 17:30:40 +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
375variable on the stack. The first argument <b>must</b> be an alloca instruction
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**
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
442<blockquote><pre
443> ;; An array type.
444 %class.Array = type { %class.Object, i32, [0 x %class.Object*] }
445...
446
447 ;; Load the object pointer from a gcroot.
448 %object = load %class.Array** %object_addr
449
450 ;; Compute the derived pointer.
451 %derived = getelementptr %obj, 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
Duncan Sands8036ca42007-03-30 12:22:09 +0000[diff] [blame]597href="#roots"><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 Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1087#include "llvm/Instructions.h"
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) {
1094 const Module *M = F.getParent();
1095
1096 Function *GCReadInt = M-&gt;getFunction("llvm.gcread"),
1097 *GCWriteInt = M-&gt;getFunction("llvm.gcwrite"),
1098 *GCRootInt = M-&gt;getFunction("llvm.gcroot");
1099
1100 bool MadeChange = false;
1101
1102 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1103 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
1104 if (CallInst *CI = dyn_cast&lt;CallInst&gt;(II++))
1105 if (Function *F = CI->getCalledFunction())
1106 if (F == GCWriteInt) {
1107 // Handle llvm.gcwrite.
1108 CI->eraseFromParent();
1109 MadeChange = true;
1110 } else if (F == GCReadInt) {
1111 // Handle llvm.gcread.
1112 CI->eraseFromParent();
1113 MadeChange = true;
1114 } else if (F == GCRootInt) {
1115 // Handle llvm.gcroot.
1116 CI->eraseFromParent();
1117 MadeChange = true;
1118 }
1119
1120 return MadeChange;
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1121}</pre></blockquote>
1122
1123</div>
1124
1125
1126<!-- ======================================================================= -->
1127<div class="doc_subsection">
1128 <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
1129</div>
1130
1131<div class="doc_text">
1132
1133<p>LLVM can compute four kinds of safe points:</p>
1134
1135<blockquote><pre
1136>namespace GC {
1137 /// PointKind - The type of a collector-safe point.
1138 ///
1139 enum PointKind {
1140 Loop, //&lt; Instr is a loop (backwards branch).
1141 Return, //&lt; Instr is a return instruction.
1142 PreCall, //&lt; Instr is a call instruction.
1143 PostCall //&lt; Instr is the return address of a call.
1144 };
1145}</pre></blockquote>
1146
1147<p>A collector can request any combination of the four by setting the
1148<tt>NeededSafePoints</tt> mask:</p>
1149
1150<blockquote><pre
1151>MyCollector::MyCollector() {
1152 NeededSafePoints = 1 &lt;&lt; GC::Loop
1153 | 1 &lt;&lt; GC::Return
1154 | 1 &lt;&lt; GC::PreCall
1155 | 1 &lt;&lt; GC::PostCall;
1156}</pre></blockquote>
1157
1158<p>It can then use the following routines to access safe points.</p>
1159
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1160<blockquote><pre
1161>for (iterator I = begin(), E = end(); I != E; ++I) {
1162 CollectorMetadata *MD = *I;
1163 size_t PointCount = MD-&gt;size();
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1164
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1165 for (CollectorMetadata::iterator PI = MD-&gt;begin(),
1166 PE = MD-&gt;end(); PI != PE; ++PI) {
1167 GC::PointKind PointKind = PI-&gt;Kind;
1168 unsigned PointNum = PI-&gt;Num;
1169 }
1170}
1171</pre></blockquote>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1172
1173<p>Almost every collector requires <tt>PostCall</tt> safe points, since these
1174correspond to the moments when the function is suspended during a call to a
1175subroutine.</p>
1176
1177<p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee
1178that the application will reach a safe point within a bounded amount of time,
1179even if it is executing a long-running loop which contains no function
1180calls.</p>
1181
1182<p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt>
1183safe points to implement "stop the world" techniques using self-modifying code,
1184where it is important that the program not exit the function without reaching a
1185safe point (because only the topmost function has been patched).</p>
1186
1187</div>
1188
1189
1190<!-- ======================================================================= -->
1191<div class="doc_subsection">
1192 <a name="assembly">Emitting assembly code:
1193 <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a>
1194</div>
1195
1196<div class="doc_text">
1197
1198<p>LLVM allows a collector to print arbitrary assembly code before and after
1199the rest of a module's assembly code. From the latter callback, the collector
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1200can print stack maps built by the code generator.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1201
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1202<p>Note that LLVM does not currently have analogous APIs to support code
1203generation in the JIT, nor using the object writers.</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1204
1205<blockquote><pre
1206>class MyCollector : public Collector {
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1207public:
1208 virtual void beginAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1209 const TargetAsmInfo &amp;TAI);
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1210
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1211 virtual void finishAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1212 const TargetAsmInfo &amp;TAI);
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1213}</pre></blockquote>
1214
1215<p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1216print portable assembly code to the <tt>std::ostream</tt>. The collector itself
1217contains the stack map for the entire module, and may access the
1218<tt>CollectorMetadata</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
1219methods. Here's a realistic example:</p>
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1220
1221<blockquote><pre
1222>#include "llvm/CodeGen/AsmPrinter.h"
1223#include "llvm/Function.h"
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1224#include "llvm/Target/TargetMachine.h"
1225#include "llvm/Target/TargetData.h"
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1226#include "llvm/Target/TargetAsmInfo.h"
1227
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1228void MyCollector::beginAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1229 const TargetAsmInfo &amp;TAI) {
1230 // Nothing to do.
1231}
1232
1233void MyCollector::finishAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1234 const TargetAsmInfo &amp;TAI) {
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1235 // Set up for emitting addresses.
1236 const char *AddressDirective;
1237 int AddressAlignLog;
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1238 if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) {
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1239 AddressDirective = TAI.getData32bitsDirective();
1240 AddressAlignLog = 2;
1241 } else {
1242 AddressDirective = TAI.getData64bitsDirective();
1243 AddressAlignLog = 3;
1244 }
1245
1246 // Put this in the data section.
1247 AP.SwitchToDataSection(TAI.getDataSection());
1248
1249 // For each function...
Gordon Henriksenad93c4f2007-12-11 00:30:17 +0000[diff] [blame^]1250 for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1251 CollectorMetadata &amp;MD = **FI;
1252
1253 // Emit this data structure:
1254 //
1255 // struct {
1256 // int32_t PointCount;
1257 // struct {
1258 // void *SafePointAddress;
1259 // int32_t LiveCount;
1260 // int32_t LiveOffsets[LiveCount];
1261 // } Points[PointCount];
1262 // } __gcmap_&lt;FUNCTIONNAME&gt;;
1263
1264 // Align to address width.
1265 AP.EmitAlignment(AddressAlignLog);
1266
1267 // Emit the symbol by which the stack map can be found.
1268 std::string Symbol;
1269 Symbol += TAI.getGlobalPrefix();
1270 Symbol += "__gcmap_";
1271 Symbol += MD.getFunction().getName();
1272 if (const char *GlobalDirective = TAI.getGlobalDirective())
1273 OS &lt;&lt; GlobalDirective &lt;&lt; Symbol &lt;&lt; "\n";
1274 OS &lt;&lt; TAI.getGlobalPrefix() &lt;&lt; Symbol &lt;&lt; ":\n";
1275
1276 // Emit PointCount.
1277 AP.EmitInt32(MD.size());
1278 AP.EOL("safe point count");
1279
1280 // And each safe point...
1281 for (CollectorMetadata::iterator PI = MD.begin(),
1282 PE = MD.end(); PI != PE; ++PI) {
1283 // Align to address width.
1284 AP.EmitAlignment(AddressAlignLog);
1285
1286 // Emit the address of the safe point.
1287 OS &lt;&lt; AddressDirective
1288 &lt;&lt; TAI.getPrivateGlobalPrefix() &lt;&lt; "label" &lt;&lt; PI-&gt;Num;
1289 AP.EOL("safe point address");
1290
1291 // Emit the stack frame size.
1292 AP.EmitInt32(MD.getFrameSize());
1293 AP.EOL("stack frame size");
1294
1295 // Emit the number of live roots in the function.
1296 AP.EmitInt32(MD.live_size(PI));
1297 AP.EOL("live root count");
1298
1299 // And for each live root...
1300 for (CollectorMetadata::live_iterator LI = MD.live_begin(PI),
1301 LE = MD.live_end(PI);
1302 LI != LE; ++LI) {
1303 // Print its offset within the stack frame.
1304 AP.EmitInt32(LI-&gt;StackOffset);
1305 AP.EOL("stack offset");
1306 }
1307 }
1308 }
1309}
1310</pre></blockquote>
1311
1312</div>
1313
1314
1315<!-- *********************************************************************** -->
1316<div class="doc_section">
1317 <a name="runtime-impl">Implementing a collector runtime</a>
1318</div>
1319<!-- *********************************************************************** -->
1320
1321<div class="doc_text">
1322
1323<p>Implementing a garbage collector for LLVM is fairly straightforward. The
1324LLVM garbage collectors are provided in a form that makes them easy to link into
1325the language-specific runtime that a language front-end would use. They require
1326functionality from the language-specific runtime to get information about <a
1327href="#gcdescriptors">where pointers are located in heap objects</a>.</p>
1328
1329<p>The implementation must include the
1330<a href="#allocate"><tt>llvm_gc_allocate</tt></a> and
1331<a href="#explicit"><tt>llvm_gc_collect</tt></a> functions. To do this, it will
1332probably have to <a href="#traceroots">trace through the roots
1333from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors
1334for heap objects</a>. Luckily, there are some <a href="#gcimpls">example
1335implementations</a> available.
1336</p>
1337</div>
1338
1339
1340<!-- ======================================================================= -->
1341<div class="doc_subsection">
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1342 <a name="gcdescriptors">Tracing GC pointers from heap objects</a>
1343</div>
1344
1345<div class="doc_text">
1346<p>
1347The three most common ways to keep track of where pointers live in heap objects
1348are (listed in order of space overhead required):</p>
1349
1350<ol>
1351<li>In languages with polymorphic objects, pointers from an object header are
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1352usually used to identify the GC pointers in the heap object. This is common for
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1353object-oriented languages like Self, Smalltalk, Java, or C#.</li>
1354
1355<li>If heap objects are not polymorphic, often the "shape" of the heap can be
1356determined from the roots of the heap or from some other meta-data [<a
1357href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1358href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can
1359propagate the information around from meta data stored with the roots. This
1360often eliminates the need to have a header on objects in the heap. This is
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1361common in the ML family.</li>
1362
1363<li>If all heap objects have pointers in the same locations, or pointers can be
1364distinguished just by looking at them (e.g., the low order bit is clear), no
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1365book-keeping is needed at all. This is common for Lisp-like languages.</li>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1366</ol>
1367
1368<p>The LLVM garbage collectors are capable of supporting all of these styles of
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1369language, including ones that mix various implementations. To do this, it
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1370allows the source-language to associate meta-data with the <a
1371href="#roots">stack roots</a>, and the heap tracing routines can propagate the
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1372information. In addition, LLVM allows the front-end to extract GC information
1373in any form from a specific object pointer (this supports situations #1 and #3).
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1374</p>
1375
1376</div>
1377
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1378
1379<!-- *********************************************************************** -->
1380<div class="doc_section">
1381 <a name="references">References</a>
1382</div>
1383<!-- *********************************************************************** -->
1384
1385<div class="doc_text">
1386
1387<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
1388W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
1389
1390<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1391strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1392PLDI'91.</p>
1393
1394<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1395explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1396conference on LISP and functional programming.</p>
1397
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1398<p><a name="henderson02">[Henderson2002]</a> <a
1399href="http://citeseer.ist.psu.edu/henderson02accurate.html">
1400Accurate Garbage Collection in an Uncooperative Environment</a>.
1401Fergus Henderson. International Symposium on Memory Management 2002.</p>
1402
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]1403</div>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1404
Gordon Henriksen326e24f2007-09-27 19:31:36 +0000[diff] [blame]1405
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1406<!-- *********************************************************************** -->
1407
1408<hr>
1409<address>
1410 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1411 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1412 <a href="http://validator.w3.org/check/referer"><img
1413 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1414
1415 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
Reid Spencer05fe4b02006-03-14 05:39:39 +0000[diff] [blame]1416 <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]1417 Last modified: $Date$
1418</address>
1419
1420</body>
1421</html>