| blob | 8747e93079d453ac3ad639f635b38990687852d3 |
3 <html>
4 <head>
7 </head>
8 <body>
11 Accurate Garbage Collection with LLVM
12 </div>
14 <ol>
16 <ul>
18 </ul>
19 </li>
22 <ul>
27 </ul>
28 </li>
31 <ul>
32 <li><a href="#llvm_gc_readwrite">Implementing <tt>llvm_gc_read</tt> and <tt>llvm_gc_write</tt></a></li>
34 </ul>
35 </li>
37 <ul>
39 </ul>
40 </li>
42 <!--
43 <li><a href="#codegen">Implementing GC support in a code generator</a></li>
44 -->
45 </ol>
49 </div>
51 <!-- *********************************************************************** -->
54 </div>
55 <!-- *********************************************************************** -->
59 <p>Garbage collection is a widely used technique that frees the programmer from
60 having to know the life-times of heap objects, making software easier to produce
61 and maintain. Many programming languages rely on garbage collection for
62 automatic memory management. There are two primary forms of garbage collection:
63 conservative and accurate.</p>
65 <p>Conservative garbage collection often does not require any special support
66 from either the language or the compiler: it can handle non-type-safe
67 programming languages (such as C/C++) and does not require any special
68 information from the compiler. The [LINK] Boehm collector is an example of a
69 state-of-the-art conservative collector.</p>
71 <p>Accurate garbage collection requires the ability to identify all pointers in
72 the program at run-time (which requires that the source-language be type-safe in
73 most cases). Identifying pointers at run-time requires compiler support to
74 locate all places that hold live pointer variables at run-time, including the
77 <p>
78 Conservative garbage collection is attractive because it does not require any
79 special compiler support, but it does have problems. In particular, because the
81 machine is a pointer, it cannot move live objects in the heap (preventing the
82 use of compacting and generational GC algorithms) and it can occasionally suffer
83 from memory leaks due to integer values that happen to point to objects in the
84 program. In addition, some aggressive compiler transformations can break
85 conservative garbage collectors (though these seem rare in practice).
86 </p>
88 <p>
89 Accurate garbage collectors do not suffer from any of these problems, but they
90 can suffer from degraded scalar optimization of the program. In particular,
91 because the runtime must be able to identify and update all pointers active in
92 the program, some optimizations are less effective. In practice, however, the
93 locality and performance benefits of using aggressive garbage allocation
94 techniques dominates any low-level losses.
95 </p>
97 <p>
98 This document describes the mechanisms and interfaces provided by LLVM to
99 support accurate garbage collection.
100 </p>
102 </div>
104 <!-- ======================================================================= -->
107 </div>
111 <p>
112 LLVM provides support for a broad class of garbage collection algorithms,
113 including compacting semi-space collectors, mark-sweep collectors, generational
114 collectors, and even reference counting implementations. It includes support
117 collection). All LLVM code generators support garbage collection, including the
118 C backend.
119 </p>
121 <p>
122 We hope that the primitive support built into LLVM is sufficient to support a
123 broad class of garbage collected languages, including Scheme, ML, scripting
124 languages, Java, C#, etc. That said, the implemented garbage collectors may
125 need to be extended to support language-specific features such as finalization,
126 weak references, or other features. As these needs are identified and
127 implemented, they should be added to this specification.
128 </p>
130 <p>
131 LLVM does not currently support garbage collection of multi-threaded programs or
132 GC-safe points other than function calls, but these will be added in the future
133 as there is interest.
134 </p>
136 </div>
138 <!-- *********************************************************************** -->
141 </div>
142 <!-- *********************************************************************** -->
146 <p>This section describes the interfaces provided by LLVM and by the garbage
147 collector run-time that should be used by user programs. As such, this is the
148 interface that front-end authors should generate code for.
149 </p>
151 </div>
153 <!-- ======================================================================= -->
156 </div>
162 </tt></div>
164 <p>
166 on the stack. The first argument contains the address of the variable on the
167 stack, and the second contains a pointer to metadata that should be associated
170 specified location to initialize the pointer.</p>
172 <p>
173 Consider the following fragment of Java code:
174 </p>
176 <pre>
177 {
178 Object X; // A null-initialized reference to an object
179 ...
180 }
181 </pre>
183 <p>
184 This block (which may be located in the middle of a function or in a loop nest),
185 could be compiled to this LLVM code:
186 </p>
188 <pre>
189 Entry:
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 ...
195 ;; "CodeBlock" is the block corresponding to the start
196 ;; of the scope above.
197 CodeBlock:
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 ...
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>
210 </div>
212 <!-- ======================================================================= -->
215 </div>
220 sbyte *%llvm_gc_allocate(unsigned %Size)
221 </tt></div>
224 garbage collector implementation to allocate memory. It returns a
225 zeroed-out block of memory of the appropriate size.</p>
227 </div>
229 <!-- ======================================================================= -->
232 </div>
237 sbyte *%llvm.gcread(sbyte *, sbyte **)<br>
238 void %llvm.gcwrite(sbyte*, sbyte*, sbyte**)
239 </tt></div>
241 <p>Several of the more interesting garbage collectors (e.g., generational
242 collectors) need to be informed when the mutator (the program that needs garbage
243 collection) reads or writes object references into the heap. In the case of a
244 generational collector, it needs to keep track of which "old" generation objects
245 have references stored into them. The amount of code that typically needs to be
246 executed is usually quite small (and not on the critical path of any
247 computation), so the overall performance impact of the inserted code is
248 tolerable.</p>
250 <p>To support garbage collectors that use read or write barriers, LLVM provides
252 intrinsic has exactly the same semantics as a non-volatile LLVM load and the
253 second has the same semantics as a non-volatile LLVM store, with the
254 additions that they also take a pointer to the start of the memory
255 object as an argument. At code generation
256 time, these intrinsics are replaced with calls into the garbage collector
259 inlined into the code.
260 </p>
262 <p>
263 If you are writing a front-end for a garbage collected language, every load or
264 store of a reference from or to the heap should use these intrinsics instead of
265 normal LLVM loads/stores.</p>
267 </div>
269 <!-- ======================================================================= -->
272 </div>
277 void %llvm_gc_initialize(unsigned %InitialHeapSize)
278 </tt></div>
280 <p>
282 garbage collection functions are called. This gives the garbage collector the
283 chance to initialize itself and allocate the heap spaces. The initial heap size
284 to allocate should be specified as an argument.
285 </p>
287 </div>
289 <!-- ======================================================================= -->
292 </div>
297 void %llvm_gc_collect()
298 </tt></div>
300 <p>
302 implementations to provide a full collection, even when the heap is not
303 exhausted. This can be used by end-user code as a hint, and may be ignored by
304 the garbage collector.
305 </p>
307 </div>
310 <!-- *********************************************************************** -->
313 </div>
314 <!-- *********************************************************************** -->
318 <p>
319 Implementing a garbage collector for LLVM is fairly straight-forward. The LLVM
320 garbage collectors are provided in a form that makes them easy to link into the
321 language-specific runtime that a language front-end would use. They require
322 functionality from the language-specific runtime to get information about <a
324 </p>
326 <p>The
327 implementation must include the <a
334 implementations</a> available.
335 </p>
336 </div>
339 <!-- ======================================================================= -->
342 </div>
346 void *llvm_gc_read(void*, void **)<br>
347 void llvm_gc_write(void*, void *, void**)
348 </tt></div>
350 <p>
352 they do not need read/write barriers. In this case, just load or store the
353 pointer, then return.
354 </p>
356 <p>
357 If an actual read or write barrier is needed, it should be straight-forward to
358 implement it.
359 </p>
361 </div>
363 <!-- ======================================================================= -->
366 </div>
369 <p>
370 Garbage collector implementations make use of call-back functions that are
371 implemented by other parts of the LLVM system.
372 </p>
373 </div>
375 <!--_________________________________________________________________________-->
378 </div>
382 void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
383 </tt></div>
385 <p>
387 generator that iterates through all of the GC roots on the stack, calling the
388 specified function pointer with each record. For each GC root, the address of
389 the pointer and the meta-data (from the <a
391 </p>
392 </div>
394 <!--_________________________________________________________________________-->
397 </div>
400 TODO
401 </div>
404 <!--_________________________________________________________________________-->
407 </div>
410 <p>
411 The three most common ways to keep track of where pointers live in heap objects
412 are (listed in order of space overhead required):</p>
414 <ol>
415 <li>In languages with polymorphic objects, pointers from an object header are
416 usually used to identify the GC pointers in the heap object. This is common for
417 object-oriented languages like Self, Smalltalk, Java, or C#.</li>
420 determined from the roots of the heap or from some other meta-data [<a
423 propagate the information around from meta data stored with the roots. This
424 often eliminates the need to have a header on objects in the heap. This is
425 common in the ML family.</li>
427 <li>If all heap objects have pointers in the same locations, or pointers can be
428 distinguished just by looking at them (e.g., the low order bit is clear), no
429 book-keeping is needed at all. This is common for Lisp-like languages.</li>
430 </ol>
432 <p>The LLVM garbage collectors are capable of supporting all of these styles of
433 language, including ones that mix various implementations. To do this, it
434 allows the source-language to associate meta-data with the <a
436 information. In addition, LLVM allows the front-end to extract GC information
437 from in any form from a specific object pointer (this supports situations #1 and
438 #3).
439 </p>
445 </div>
449 <!-- *********************************************************************** -->
452 </div>
453 <!-- *********************************************************************** -->
457 <p>
458 To make this more concrete, the currently implemented LLVM garbage collectors
460 If you are interested in implementing an algorithm, there are many interesting
461 possibilities (mark/sweep, a generational collector, a reference counting
462 collector, etc), or you could choose to improve one of the existing algorithms.
463 </p>
465 </div>
467 <!-- ======================================================================= -->
470 </div>
473 <p>
474 SemiSpace is a very simple copying collector. When it starts up, it allocates
475 two blocks of memory for the heap. It uses a simple bump-pointer allocator to
476 allocate memory from the first block until it runs out of space. When it runs
477 out of space, it traces through all of the roots of the program, copying blocks
478 to the other half of the memory space.
479 </p>
481 </div>
483 <!--_________________________________________________________________________-->
485 Possible Improvements
486 </div>
490 <p>
491 If a collection cycle happens and the heap is not compacted very much (say less
492 than 25% of the allocated memory was freed), the memory regions should be
493 doubled in size.</p>
495 </div>
497 <!-- *********************************************************************** -->
500 </div>
501 <!-- *********************************************************************** -->
509 strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
513 explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
514 conference on LISP and functional programming.</p>
516 </div>
518 <!-- *********************************************************************** -->
520 <hr>
521 <address>
529 Last modified: $Date$
530 </address>
532 </body>
533 </html>