Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 0d8c2db1c9c3b541e247ef27a37b4a23e2e7d939 / . / docs / GarbageCollection.html
blob: fd5c900ec41e2f63efa1302ac8adc2749c422d32 [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>
5 <title>Accurate Garbage Collection with LLVM</title>
6 <link rel="stylesheet" href="llvm.css" type="text/css">
7</head>
8<body>
9
10<div class="doc_title">
11 Accurate Garbage Collection with LLVM
12</div>
13
14<ol>
15 <li><a href="#introduction">Introduction</a>
16 <ul>
17 <li><a href="#feature">GC features provided and algorithms supported</a></li>
18 </ul>
19 </li>
20
21 <li><a href="#interfaces">Interfaces for user programs</a>
22 <ul>
23 <li><a href="#roots">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a></li>
24 <li><a href="#gcdescriptors">GC descriptor format for heap objects</a></li>
25 <li><a href="#allocate">Allocating memory from the GC</a></li>
26 <li><a href="#barriers">Reading and writing references to the heap</a></li>
27 <li><a href="#explicit">Explicit invocation of the garbage collector</a></li>
28 </ul>
29 </li>
30
31 <li><a href="#gcimpl">Implementing a garbage collector</a>
32 <ul>
33 <li><a href="#llvm_gc_readwrite">Implementing <tt>llvm_gc_read</tt> and <tt>llvm_gc_write</tt></a></li>
34 <li><a href="#traceroots">Tracing the GC roots from the program stack</a></li>
35 <li><a href="#gcimpls">GC implementations available</a></li>
36 </ul>
37 </li>
38
39<!--
40 <li><a href="#codegen">Implementing GC support in a code generator</a></li>
41-->
42</ol>
43
44<div class="doc_author">
45 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
46</div>
47
48<!-- *********************************************************************** -->
49<div class="doc_section">
50 <a name="introduction">Introduction</a>
51</div>
52<!-- *********************************************************************** -->
53
54<div class="doc_text">
55
56<p>Garbage collection is a widely used technique that frees the programmer from
57having to know the life-times of heap objects, making software easier to produce
58and maintain. Many programming languages rely on garbage collection for
59automatic memory management. There are two primary forms of garbage collection:
60conservative and accurate.</p>
61
62<p>Conservative garbage collection often does not require any special support
63from either the language or the compiler: it can handle non-type-safe
64programming languages (such as C/C++) and does not require any special
65information from the compiler. The [LINK] Boehm collector is an example of a
66state-of-the-art conservative collector.</p>
67
68<p>Accurate garbage collection requires the ability to identify all pointers in
69the program at run-time (which requires that the source-language be type-safe in
70most cases). Identifying pointers at run-time requires compiler support to
71locate all places that hold live pointer variables at run-time, including the
72<a href="#roots">processor stack and registers</a>.</p>
73
74<p>
75Conservative garbage collection is attractive because it does not require any
76special compiler support, but it does have problems. In particular, because the
77conservative garbage collector cannot <i>know</i> that a particular word in the
78machine is a pointer, it cannot move live objects in the heap (preventing the
79use of compacting and generational GC algorithms) and it can occasionally suffer
80from memory leaks due to integer values that happen to point to objects in the
81program. In addition, some aggressive compiler transformations can break
82conservative garbage collectors (though these seem rare in practice).
83</p>
84
85<p>
86Accurate garbage collectors do not suffer from any of these problems, but they
87can suffer from degraded scalar optimization of the program. In particular,
88because the runtime must be able to identify and update all pointers active in
89the program, some optimizations are less effective. In practice, however, the
90locality and performance benefits of using aggressive garbage allocation
91techniques dominates any low-level losses.
92</p>
93
94<p>
95This document describes the mechanisms and interfaces provided by LLVM to
96support accurate garbage collection.
97</p>
98
99</div>
100
101<!-- ======================================================================= -->
102<div class="doc_subsection">
103 <a name="feature">GC features provided and algorithms supported</a>
104</div>
105
106<div class="doc_text">
107
108<p>
109LLVM provides support for a broad class of garbage collection algorithms,
110including compacting semi-space collectors, mark-sweep collectors, generational
111collectors, and even reference counting implementations. It includes support
112for <a href="#barriers">read and write barriers</a>, and associating <a
113href="#roots">meta-data with stack objects</a> (used for tagless garbage
114collection). All LLVM code generators support garbage collection, including the
115C backend.
116</p>
117
118<p>
119We hope that the primitive support built into LLVM is sufficient to support a
120broad class of garbage collected languages, including Scheme, ML, scripting
121languages, Java, C#, etc. That said, the implemented garbage collectors may
122need to be extended to support language-specific features such as finalization,
123weak references, or other features. As these needs are identified and
124implemented, they should be added to this specification.
125</p>
126
127<p>
128LLVM does not currently support garbage collection of multi-threaded programs or
129GC-safe points other than function calls, but these will be added in the future
130as there is interest.
131</p>
132
133</div>
134
135<!-- *********************************************************************** -->
136<div class="doc_section">
137 <a name="interfaces">Interfaces for user programs</a>
138</div>
139<!-- *********************************************************************** -->
140
141<div class="doc_text">
142
143<p>This section describes the interfaces provided by LLVM and by the garbage
144collector run-time that should be used by user programs. As such, this is the
145interface that front-end authors should generate code for.
146</p>
147
148</div>
149
150<!-- ======================================================================= -->
151<div class="doc_subsection">
152 <a name="roots">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
153</div>
154
155<div class="doc_text">
156
157<div class="doc_code"><tt>
158 void %llvm.gcroot(&lt;ty&gt;** %ptrloc, &lt;ty2&gt;* %metadata)
159</tt></div>
160
161<p>
162The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer variable
163on the stack. The first argument contains the address of the variable on the
164stack, and the second contains a pointer to metadata that should be associated
165with the pointer (which <b>must</b> be a constant or global value address). At
166runtime, the <tt>llvm.gcroot</tt> intrinsic stores a null pointer into the
167specified location to initialize the pointer.</p>
168
169<p>
170Consider the following fragment of Java code:
171</p>
172
173<pre>
174 {
175 Object X; // A null-initialized reference to an object
176 ...
177 }
178</pre>
179
180<p>
181This block (which may be located in the middle of a function or in a loop nest),
182could be compiled to this LLVM code:
183</p>
184
185<pre>
186Entry:
187 ;; In the entry block for the function, allocate the
188 ;; stack space for X, which is an LLVM pointer.
189 %X = alloca %Object*
190 ...
191
192 ;; "CodeBlock" is the block corresponding to the start
193 ;; of the scope scope above.
194CodeBlock:
195 ;; Initialize the object, telling LLVM that it is now live.
196 ;; Java has type-tags on objects, so it doesn't need any
197 ;; metadata.
198 call void %llvm.gcroot(%Object** %X, sbyte* null)
199 ...
200
201 ;; As the pointer goes out of scope, store a null value into
202 ;; it, to indicate that the value is no longer live.
203 store %Object* null, %Object** %X
204 ...
205</pre>
206
207</div>
208
209<!-- ======================================================================= -->
210<div class="doc_subsection">
211 <a name="gcdescriptors">GC descriptor format for heap objects</a>
212</div>
213
214<div class="doc_text">
215
216<p>
217Either from root meta data, or from object headers. Front-end can provide a
218call-back to get descriptor from object without meta-data.
219</p>
220
221</div>
222
223<!-- ======================================================================= -->
224<div class="doc_subsection">
225 <a name="allocate">Allocating memory from the GC</a>
226</div>
227
228<div class="doc_text">
229
230<div class="doc_code"><tt>
231 sbyte *%llvm_gc_allocate(unsigned %Size)
232</tt></div>
233
234<p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the
235garbage collector implementation to allocate memory. It should return a
236zeroed-out block of memory of the appropriate size.</p>
237
238</div>
239
240<!-- ======================================================================= -->
241<div class="doc_subsection">
242 <a name="barriers">Reading and writing references to the heap</a>
243</div>
244
245<div class="doc_text">
246
247<div class="doc_code"><tt>
248 sbyte *%llvm.gcread(sbyte **)<br>
249 void %llvm.gcwrite(sbyte*, sbyte**)
250</tt></div>
251
252<p>Several of the more interesting garbage collectors (e.g., generational
253collectors) need to be informed when the mutator (the program that needs garbage
254collection) reads or writes object references into the heap. In the case of a
255generational collector, it needs to keep track of which "old" generation objects
256have references stored into them. The amount of code that typically needs to be
257executed is usually quite small, so the overall performance impact of the
258inserted code is tolerable.</p>
259
260<p>To support garbage collectors that use read or write barriers, LLVM provides
261the <tt>llvm.gcread</tt> and <tt>llvm.gcwrite</tt> intrinsics. The first
262intrinsic has exactly the same semantics as a non-volatile LLVM load and the
263second has the same semantics as a non-volatile LLVM store. At code generation
264time, these intrinsics are replaced with calls into the garbage collector
265(<tt><a href="#llvm_gc_readwrite">llvm_gc_read</a></tt> and <tt><a
266href="#llvm_gc_readwrite">llvm_gc_write</a></tt> respectively), which are then
267inlined into the code.
268</p>
269
270<p>
271If you are writing a front-end for a garbage collected language, every load or
272store of a reference from or to the heap should use these intrinsics instead of
273normal LLVM loads/stores.</p>
274
275</div>
276
277<!-- ======================================================================= -->
278<div class="doc_subsection">
279 <a name="initialize">Garbage collector startup and initialization</a>
280</div>
281
282<div class="doc_text">
283
284<div class="doc_code"><tt>
285 void %llvm_gc_initialize()
286</tt></div>
287
288<p>
289The <tt>llvm_gc_initialize</tt> function should be called once before any other
290garbage collection functions are called. This gives the garbage collector the
291chance to initialize itself and allocate the heap spaces.
292</p>
293
294</div>
295
296<!-- ======================================================================= -->
297<div class="doc_subsection">
298 <a name="explicit">Explicit invocation of the garbage collector</a>
299</div>
300
301<div class="doc_text">
302
303<div class="doc_code"><tt>
304 void %llvm_gc_collect()
305</tt></div>
306
307<p>
308The <tt>llvm_gc_collect</tt> function is exported by the garbage collector
309implementations to provide a full collection, even when the heap is not
310exhausted. This can be used by end-user code as a hint, and may be ignored by
311the garbage collector.
312</p>
313
314</div>
315
316
317<!-- *********************************************************************** -->
318<div class="doc_section">
319 <a name="gcimpl">Implementing a garbage collector</a>
320</div>
321<!-- *********************************************************************** -->
322
323<div class="doc_text">
324
325<p>
326Implementing a garbage collector for LLVM is fairly straight-forward. The
327implementation must include the <a
328href="#allocate"><tt>llvm_gc_allocate</tt></a> and <a
329href="#explicit"><tt>llvm_gc_collect</tt></a> functions, and it must implement
330the <a href="#llvm_gc_readwrite">read/write barrier</a> functions as well. To
331do this, it will probably have to <a href="#traceroots">trace through the roots
332from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors
333for heap objects</a>. Luckily, there are some <a href="#gcimpls">example
334implementations</a> available.
335</p>
336</div>
337
338
339<!-- ======================================================================= -->
340<div class="doc_subsection">
341 <a name="llvm_gc_readwrite">Implementing <tt>llvm_gc_read</tt> and <tt>llvm_gc_write</tt></a>
342</div>
343
344<div class="doc_text">
345 <div class="doc_code"><tt>
346 void *llvm_gc_read(void **)<br>
347 void llvm_gc_write(void*, void**)
348 </tt></div>
349
350<p>
351These functions <i>must</i> be implemented in every garbage collector, even if
352they do not need read/write barriers. In this case, just load or store the
353pointer, then return.
354</p>
355
356<p>
357If an actual read or write barrier is needed, it should be straight-forward to
358implement it. Note that we may add a pointer to the start of the memory object
359as a parameter in the future, if needed.
360</p>
361
362</div>
363
364<!-- ======================================================================= -->
365<div class="doc_subsection">
366 <a name="traceroots">Tracing the GC roots from the program stack</a>
367</div>
368
369<div class="doc_text">
370 <div class="doc_code"><tt>
371 void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
372 </tt></div>
373
374<p>
375The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code
376generator that iterates through all of the GC roots on the stack, calling the
377specified function pointer with each record. For each GC root, the address of
378the pointer and the meta-data (from the <a
379href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
380</p>
381</div>
382
383
384<!-- ======================================================================= -->
385<div class="doc_subsection">
386 <a name="gcimpls">GC implementations available</a>
387</div>
388
389<div class="doc_text">
390
391<p>
392To make this more concrete, the currently implemented LLVM garbage collectors
393all live in the llvm/runtime/GC directory in the LLVM source-base.
394</p>
395
396<p>
397TODO: Brief overview of each.
398</p>
399
400</div>
401
402
403<!-- *********************************************************************** -->
404
405<hr>
406<address>
407 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
408 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
409 <a href="http://validator.w3.org/check/referer"><img
410 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
411
412 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
413 <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br>
414 Last modified: $Date$
415</address>
416
417</body>
418</html>