Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 9abd8af71e1516346f43c8e9978b7dba1fa0e939 / . / docs / GarbageCollection.html
blob: 91be23967462660e0e5793cc5f9dc0810e67a8c4 [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>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]24 <li><a href="#allocate">Allocating memory from the GC</a></li>
25 <li><a href="#barriers">Reading and writing references to the heap</a></li>
26 <li><a href="#explicit">Explicit invocation of the garbage collector</a></li>
27 </ul>
28 </li>
29
30 <li><a href="#gcimpl">Implementing a garbage collector</a>
31 <ul>
32 <li><a href="#llvm_gc_readwrite">Implementing <tt>llvm_gc_read</tt> and <tt>llvm_gc_write</tt></a></li>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]33 <li><a href="#callbacks">Callback functions used to implement the garbage collector</a></li>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]34 </ul>
35 </li>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]36 <li><a href="#gcimpls">GC implementations available</a>
37 <ul>
38 <li><a href="#semispace">SemiSpace - A simple copying garbage collector</a></li>
Chris Lattner0b02dbc2004-07-09 05:03:54 +0000[diff] [blame]39 </ul>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]40 </li>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]41
42<!--
43 <li><a href="#codegen">Implementing GC support in a code generator</a></li>
44-->
45</ol>
46
47<div class="doc_author">
48 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
49</div>
50
51<!-- *********************************************************************** -->
52<div class="doc_section">
53 <a name="introduction">Introduction</a>
54</div>
55<!-- *********************************************************************** -->
56
57<div class="doc_text">
58
59<p>Garbage collection is a widely used technique that frees the programmer from
60having to know the life-times of heap objects, making software easier to produce
61and maintain. Many programming languages rely on garbage collection for
62automatic memory management. There are two primary forms of garbage collection:
63conservative and accurate.</p>
64
65<p>Conservative garbage collection often does not require any special support
66from either the language or the compiler: it can handle non-type-safe
67programming languages (such as C/C++) and does not require any special
68information from the compiler. The [LINK] Boehm collector is an example of a
69state-of-the-art conservative collector.</p>
70
71<p>Accurate garbage collection requires the ability to identify all pointers in
72the program at run-time (which requires that the source-language be type-safe in
73most cases). Identifying pointers at run-time requires compiler support to
74locate all places that hold live pointer variables at run-time, including the
75<a href="#roots">processor stack and registers</a>.</p>
76
77<p>
78Conservative garbage collection is attractive because it does not require any
79special compiler support, but it does have problems. In particular, because the
80conservative garbage collector cannot <i>know</i> that a particular word in the
81machine is a pointer, it cannot move live objects in the heap (preventing the
82use of compacting and generational GC algorithms) and it can occasionally suffer
83from memory leaks due to integer values that happen to point to objects in the
84program. In addition, some aggressive compiler transformations can break
85conservative garbage collectors (though these seem rare in practice).
86</p>
87
88<p>
89Accurate garbage collectors do not suffer from any of these problems, but they
90can suffer from degraded scalar optimization of the program. In particular,
91because the runtime must be able to identify and update all pointers active in
92the program, some optimizations are less effective. In practice, however, the
93locality and performance benefits of using aggressive garbage allocation
94techniques dominates any low-level losses.
95</p>
96
97<p>
98This document describes the mechanisms and interfaces provided by LLVM to
99support accurate garbage collection.
100</p>
101
102</div>
103
104<!-- ======================================================================= -->
105<div class="doc_subsection">
106 <a name="feature">GC features provided and algorithms supported</a>
107</div>
108
109<div class="doc_text">
110
111<p>
112LLVM provides support for a broad class of garbage collection algorithms,
113including compacting semi-space collectors, mark-sweep collectors, generational
114collectors, and even reference counting implementations. It includes support
115for <a href="#barriers">read and write barriers</a>, and associating <a
116href="#roots">meta-data with stack objects</a> (used for tagless garbage
117collection). All LLVM code generators support garbage collection, including the
118C backend.
119</p>
120
121<p>
122We hope that the primitive support built into LLVM is sufficient to support a
123broad class of garbage collected languages, including Scheme, ML, scripting
124languages, Java, C#, etc. That said, the implemented garbage collectors may
125need to be extended to support language-specific features such as finalization,
126weak references, or other features. As these needs are identified and
127implemented, they should be added to this specification.
128</p>
129
130<p>
131LLVM does not currently support garbage collection of multi-threaded programs or
132GC-safe points other than function calls, but these will be added in the future
133as there is interest.
134</p>
135
136</div>
137
138<!-- *********************************************************************** -->
139<div class="doc_section">
140 <a name="interfaces">Interfaces for user programs</a>
141</div>
142<!-- *********************************************************************** -->
143
144<div class="doc_text">
145
146<p>This section describes the interfaces provided by LLVM and by the garbage
147collector run-time that should be used by user programs. As such, this is the
148interface that front-end authors should generate code for.
149</p>
150
151</div>
152
153<!-- ======================================================================= -->
154<div class="doc_subsection">
155 <a name="roots">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
156</div>
157
158<div class="doc_text">
159
160<div class="doc_code"><tt>
161 void %llvm.gcroot(&lt;ty&gt;** %ptrloc, &lt;ty2&gt;* %metadata)
162</tt></div>
163
164<p>
165The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer variable
166on the stack. The first argument contains the address of the variable on the
167stack, and the second contains a pointer to metadata that should be associated
168with the pointer (which <b>must</b> be a constant or global value address). At
169runtime, the <tt>llvm.gcroot</tt> intrinsic stores a null pointer into the
170specified location to initialize the pointer.</p>
171
172<p>
173Consider the following fragment of Java code:
174</p>
175
176<pre>
177 {
178 Object X; // A null-initialized reference to an object
179 ...
180 }
181</pre>
182
183<p>
184This block (which may be located in the middle of a function or in a loop nest),
185could be compiled to this LLVM code:
186</p>
187
188<pre>
189Entry:
190 ;; In the entry block for the function, allocate the
191 ;; stack space for X, which is an LLVM pointer.
192 %X = alloca %Object*
193 ...
194
195 ;; "CodeBlock" is the block corresponding to the start
Reid Spencer03d186a2004-05-25 08:45:31 +0000[diff] [blame]196 ;; of the scope above.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]197CodeBlock:
198 ;; Initialize the object, telling LLVM that it is now live.
199 ;; Java has type-tags on objects, so it doesn't need any
200 ;; metadata.
201 call void %llvm.gcroot(%Object** %X, sbyte* null)
202 ...
203
204 ;; As the pointer goes out of scope, store a null value into
205 ;; it, to indicate that the value is no longer live.
206 store %Object* null, %Object** %X
207 ...
208</pre>
209
210</div>
211
212<!-- ======================================================================= -->
213<div class="doc_subsection">
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]214 <a name="allocate">Allocating memory from the GC</a>
215</div>
216
217<div class="doc_text">
218
219<div class="doc_code"><tt>
220 sbyte *%llvm_gc_allocate(unsigned %Size)
221</tt></div>
222
223<p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the
Chris Lattneraab3aff2004-06-09 03:59:05 +0000[diff] [blame]224garbage collector implementation to allocate memory. It returns a
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]225zeroed-out block of memory of the appropriate size.</p>
226
227</div>
228
229<!-- ======================================================================= -->
230<div class="doc_subsection">
231 <a name="barriers">Reading and writing references to the heap</a>
232</div>
233
234<div class="doc_text">
235
236<div class="doc_code"><tt>
Chris Lattner728f03f2004-07-22 05:49:38 +0000[diff] [blame]237 sbyte *%llvm.gcread(sbyte *, sbyte **)<br>
238 void %llvm.gcwrite(sbyte*, sbyte*, sbyte**)
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]239</tt></div>
240
241<p>Several of the more interesting garbage collectors (e.g., generational
242collectors) need to be informed when the mutator (the program that needs garbage
243collection) reads or writes object references into the heap. In the case of a
244generational collector, it needs to keep track of which "old" generation objects
245have references stored into them. The amount of code that typically needs to be
Chris Lattneraab3aff2004-06-09 03:59:05 +0000[diff] [blame]246executed is usually quite small (and not on the critical path of any
247computation), so the overall performance impact of the inserted code is
248tolerable.</p>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]249
250<p>To support garbage collectors that use read or write barriers, LLVM provides
251the <tt>llvm.gcread</tt> and <tt>llvm.gcwrite</tt> intrinsics. The first
252intrinsic has exactly the same semantics as a non-volatile LLVM load and the
Chris Lattner728f03f2004-07-22 05:49:38 +0000[diff] [blame]253second has the same semantics as a non-volatile LLVM store, with the
254additions that they also take a pointer to the start of the memory
255object as an argument. At code generation
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]256time, these intrinsics are replaced with calls into the garbage collector
257(<tt><a href="#llvm_gc_readwrite">llvm_gc_read</a></tt> and <tt><a
258href="#llvm_gc_readwrite">llvm_gc_write</a></tt> respectively), which are then
259inlined into the code.
260</p>
261
262<p>
263If you are writing a front-end for a garbage collected language, every load or
264store of a reference from or to the heap should use these intrinsics instead of
265normal LLVM loads/stores.</p>
266
267</div>
268
269<!-- ======================================================================= -->
270<div class="doc_subsection">
271 <a name="initialize">Garbage collector startup and initialization</a>
272</div>
273
274<div class="doc_text">
275
276<div class="doc_code"><tt>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]277 void %llvm_gc_initialize(unsigned %InitialHeapSize)
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]278</tt></div>
279
280<p>
281The <tt>llvm_gc_initialize</tt> function should be called once before any other
282garbage collection functions are called. This gives the garbage collector the
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]283chance to initialize itself and allocate the heap spaces. The initial heap size
284to allocate should be specified as an argument.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]285</p>
286
287</div>
288
289<!-- ======================================================================= -->
290<div class="doc_subsection">
291 <a name="explicit">Explicit invocation of the garbage collector</a>
292</div>
293
294<div class="doc_text">
295
296<div class="doc_code"><tt>
297 void %llvm_gc_collect()
298</tt></div>
299
300<p>
301The <tt>llvm_gc_collect</tt> function is exported by the garbage collector
302implementations to provide a full collection, even when the heap is not
303exhausted. This can be used by end-user code as a hint, and may be ignored by
304the garbage collector.
305</p>
306
307</div>
308
309
310<!-- *********************************************************************** -->
311<div class="doc_section">
312 <a name="gcimpl">Implementing a garbage collector</a>
313</div>
314<!-- *********************************************************************** -->
315
316<div class="doc_text">
317
318<p>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]319Implementing a garbage collector for LLVM is fairly straight-forward. The LLVM
320garbage collectors are provided in a form that makes them easy to link into the
321language-specific runtime that a language front-end would use. They require
322functionality from the language-specific runtime to get information about <a
323href="#gcdescriptors">where pointers are located in heap objects</a>.
324</p>
325
326<p>The
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]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>
Chris Lattner728f03f2004-07-22 05:49:38 +0000[diff] [blame]346 void *llvm_gc_read(void*, void **)<br>
347 void llvm_gc_write(void*, void *, void**)
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]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
Chris Lattner728f03f2004-07-22 05:49:38 +0000[diff] [blame]358implement it.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]359</p>
360
361</div>
362
363<!-- ======================================================================= -->
364<div class="doc_subsection">
Chris Lattner0b02dbc2004-07-09 05:03:54 +0000[diff] [blame]365 <a name="callbacks">Callback functions used to implement the garbage collector</a>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]366</div>
367
Chris Lattner0b02dbc2004-07-09 05:03:54 +0000[diff] [blame]368<div class="doc_text">
369<p>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]370Garbage collector implementations make use of call-back functions that are
371implemented by other parts of the LLVM system.
Chris Lattner0b02dbc2004-07-09 05:03:54 +0000[diff] [blame]372</p>
373</div>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]374
375<!--_________________________________________________________________________-->
376<div class="doc_subsubsection">
377 <a name="traceroots">Tracing GC pointers from the program stack</a>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]378</div>
379
380<div class="doc_text">
381 <div class="doc_code"><tt>
382 void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
383 </tt></div>
384
385<p>
386The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code
387generator that iterates through all of the GC roots on the stack, calling the
388specified function pointer with each record. For each GC root, the address of
389the pointer and the meta-data (from the <a
390href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
391</p>
392</div>
393
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]394<!--_________________________________________________________________________-->
395<div class="doc_subsubsection">
396 <a name="staticroots">Tracing GC pointers from static roots</a>
397</div>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]398
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]399<div class="doc_text">
400TODO
401</div>
402
403
404<!--_________________________________________________________________________-->
405<div class="doc_subsubsection">
406 <a name="gcdescriptors">Tracing GC pointers from heap objects</a>
407</div>
408
409<div class="doc_text">
410<p>
411The three most common ways to keep track of where pointers live in heap objects
412are (listed in order of space overhead required):</p>
413
414<ol>
415<li>In languages with polymorphic objects, pointers from an object header are
416usually used to identify the GC pointers in the heap object. This is common for
417object-oriented languages like Self, Smalltalk, Java, or C#.</li>
418
419<li>If heap objects are not polymorphic, often the "shape" of the heap can be
420determined from the roots of the heap or from some other meta-data [<a
421href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a
422href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can
423propagate the information around from meta data stored with the roots. This
424often eliminates the need to have a header on objects in the heap. This is
425common in the ML family.</li>
426
427<li>If all heap objects have pointers in the same locations, or pointers can be
428distinguished just by looking at them (e.g., the low order bit is clear), no
429book-keeping is needed at all. This is common for Lisp-like languages.</li>
430</ol>
431
432<p>The LLVM garbage collectors are capable of supporting all of these styles of
433language, including ones that mix various implementations. To do this, it
434allows the source-language to associate meta-data with the <a
435href="#roots">stack roots</a>, and the heap tracing routines can propagate the
436information. In addition, LLVM allows the front-end to extract GC information
437from in any form from a specific object pointer (this supports situations #1 and
438#3).
439</p>
440
441<p><b>Making this efficient</b></p>
442
443
444
445</div>
446
447
448
449<!-- *********************************************************************** -->
450<div class="doc_section">
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]451 <a name="gcimpls">GC implementations available</a>
452</div>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]453<!-- *********************************************************************** -->
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]454
455<div class="doc_text">
456
457<p>
458To make this more concrete, the currently implemented LLVM garbage collectors
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]459all live in the <tt>llvm/runtime/GC/*</tt> directories in the LLVM source-base.
460If you are interested in implementing an algorithm, there are many interesting
461possibilities (mark/sweep, a generational collector, a reference counting
462collector, etc), or you could choose to improve one of the existing algorithms.
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]463</p>
464
465</div>
466
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]467<!-- ======================================================================= -->
468<div class="doc_subsection">
Chris Lattner0b02dbc2004-07-09 05:03:54 +0000[diff] [blame]469 <a name="semispace">SemiSpace - A simple copying garbage collector</a>
Chris Lattner9b2a1842004-05-27 05:52:10 +0000[diff] [blame]470</div>
471
472<div class="doc_text">
473<p>
474SemiSpace is a very simple copying collector. When it starts up, it allocates
475two blocks of memory for the heap. It uses a simple bump-pointer allocator to
476allocate memory from the first block until it runs out of space. When it runs
477out of space, it traces through all of the roots of the program, copying blocks
478to the other half of the memory space.
479</p>
480
481</div>
482
483<!--_________________________________________________________________________-->
484<div class="doc_subsubsection">
485 Possible Improvements
486</div>
487
488<div class="doc_text">
489
490<p>
491If a collection cycle happens and the heap is not compacted very much (say less
492than 25% of the allocated memory was freed), the memory regions should be
493doubled in size.</p>
494
495</div>
496
497<!-- *********************************************************************** -->
498<div class="doc_section">
499 <a name="references">References</a>
500</div>
501<!-- *********************************************************************** -->
502
503<div class="doc_text">
504
505<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
506W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
507
508<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
509strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
510PLDI'91.</p>
511
512<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
513explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
514conference on LISP and functional programming.</p>
515
516</div>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]517
518<!-- *********************************************************************** -->
519
520<hr>
521<address>
522 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
523 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
524 <a href="http://validator.w3.org/check/referer"><img
525 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
526
527 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
Reid Spencer05fe4b02006-03-14 05:39:39 +0000[diff] [blame]528 <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Chris Lattner0d8c2db2004-05-23 21:02:20 +0000[diff] [blame]529 Last modified: $Date$
530</address>
531
532</body>
533</html>