Inline the fastpath of PATypeHolder::get(). This is a small speedup in
[oota-llvm.git] / docs / GarbageCollection.html
1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2                       "http://www.w3.org/TR/html4/strict.dtd">
3 <html>
4 <head>
5   <meta http-equiv="Content-Type" Content="text/html; charset=UTF-8" >
6   <title>Accurate Garbage Collection with LLVM</title>
7   <link rel="stylesheet" href="llvm.css" type="text/css">
8   <style type="text/css">
9     .rowhead { text-align: left; background: inherit; }
10     .indent { padding-left: 1em; }
11     .optl { color: #BFBFBF; }
12   </style>
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>
23     <li><a href="#feature">GC features provided and algorithms
24       supported</a></li>
25     </ul>
26   </li>
27
28   <li><a href="#usage">Using the collectors</a>
29     <ul>
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
39   <li><a href="#core">Core support</a>
40     <ul>
41     <li><a href="#gcattr">Specifying GC code generation:
42       <tt>gc "..."</tt></a></li>
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>
58     <li><a href="#allocate">Allocating memory from the GC</a></li>
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>
64     </ul>
65   </li>
66
67   <li><a href="#plugin">Implementing a collector plugin</a>
68     <ul>
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>
79     </ul>
80   </li>
81
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   
91 </ol>
92
93 <div class="doc_author">
94   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and
95      Gordon Henriksen</p>
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
107 having to know the lifetimes of heap objects, making software easier to produce
108 and maintain. Many programming languages rely on garbage collection for
109 automatic memory management. There are two primary forms of garbage collection:
110 conservative and accurate.</p>
111
112 <p>Conservative garbage collection often does not require any special support
113 from either the language or the compiler: it can handle non-type-safe
114 programming languages (such as C/C++) and does not require any special
115 information from the compiler. The
116 <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is
117 an example of a state-of-the-art conservative collector.</p>
118
119 <p>Accurate garbage collection requires the ability to identify all pointers in
120 the program at run-time (which requires that the source-language be type-safe in
121 most cases). Identifying pointers at run-time requires compiler support to
122 locate all places that hold live pointer variables at run-time, including the
123 <a href="#gcroot">processor stack and registers</a>.</p>
124
125 <p>Conservative garbage collection is attractive because it does not require any
126 special compiler support, but it does have problems. In particular, because the
127 conservative garbage collector cannot <i>know</i> that a particular word in the
128 machine is a pointer, it cannot move live objects in the heap (preventing the
129 use of compacting and generational GC algorithms) and it can occasionally suffer
130 from memory leaks due to integer values that happen to point to objects in the
131 program. In addition, some aggressive compiler transformations can break
132 conservative garbage collectors (though these seem rare in practice).</p>
133
134 <p>Accurate garbage collectors do not suffer from any of these problems, but
135 they can suffer from degraded scalar optimization of the program. In particular,
136 because the runtime must be able to identify and update all pointers active in
137 the program, some optimizations are less effective. In practice, however, the
138 locality and performance benefits of using aggressive garbage allocation
139 techniques dominates any low-level losses.</p>
140
141 <p>This document describes the mechanisms and interfaces provided by LLVM to
142 support accurate garbage collection.</p>
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
153 <p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
154 collection intrinsics</a> that offer support for a broad class of
155 collector models. For instance, the intrinsics permit:</p>
156
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>
166
167 <p>We hope that the primitive support built into the LLVM IR is sufficient to
168 support a broad class of garbage collected languages including Scheme, ML, Java,
169 C#, 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
172 collectors are tightly coupled to object models, and LLVM is agnostic to object
173 models. Since LLVM is agnostic to object models, it would be inappropriate for
174 LLVM to dictate any particular collector. Instead, LLVM provides a framework for
175 garbage 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>
188
189 </div>
190
191 <!-- *********************************************************************** -->
192 <div class="doc_section">
193   <a name="usage">Using the collectors</a>
194 </div>
195 <!-- *********************************************************************** -->
196
197 <div class="doc_text">
198
199 <p>In general, using a collector implies:</p>
200
201 <ul>
202   <li>Emitting compatible code, including initialization in the main
203       program if necessary.</li>
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>
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>
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>
217     <th><tt>gc</tt> attribute</th>
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>
225     <td><tt>gc "shadow-stack"</tt></td>
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>
233     <td><tt>gc "ocaml"</tt></td>
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
243 collectors may require user programs to utilize.</p>
244
245 </div>
246
247 <!-- ======================================================================= -->
248 <div class="doc_subsection">
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
258 <p>The ShadowStack backend is invoked with the <tt>gc "shadow-stack"</tt>
259 function attribute.
260 Unlike many collectors which rely on a cooperative code generator to generate
261 stack maps, this algorithm carefully maintains a linked list of stack root
262 descriptors [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow
263 stack" mirrors the machine stack. Maintaining this data structure is slower
264 than using stack maps, but has a significant portability advantage because it
265 requires 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
268 program may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt>
269 and <tt>llvm.gcwrite</tt>.</p>
270
271 <p>ShadowStack is a code generator plugin only. It must be paired with a
272 compatible runtime.</p>
273
274 </div>
275
276 <!-- ======================================================================= -->
277 <div class="doc_subsection">
278   <a name="semispace">SemiSpace - A simple copying collector runtime</a>
279 </div>
280
281 <div class="doc_text">
282
283 <p>The SemiSpace runtime implements the <a href="runtime">suggested
284 runtime interface</a> and is compatible with the ShadowStack backend.</p>
285
286 <p>SemiSpace is a very simple copying collector. When it starts up, it
287 allocates two blocks of memory for the heap. It uses a simple bump-pointer
288 allocator to allocate memory from the first block until it runs out of space.
289 When it runs out of space, it traces through all of the roots of the program,
290 copying 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.
293 Enhancements 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
308 <p>The ocaml backend is invoked with the <tt>gc "ocaml"</tt> function attribute.
309 It supports the
310 <a href="http://caml.inria.fr/">Objective Caml</a> language runtime by emitting
311 a type-accurate stack map in the form of an ocaml 3.10.0-compatible frametable.
312 The linkage requirements are satisfied automatically by the <tt>ocamlopt</tt>
313 compiler when linking an executable.</p>
314
315 <p>The ocaml collector does not use read or write barriers, so the user program
316 may 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">
324   <a name="core">Core support</a><a name="intrinsics"></a>
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.
334 They are not intended to be a complete interface to any garbage collector.
335 Notably, heap allocation is not among the supplied primitives. A user program
336 will also need to interface with the runtime, using either the
337 <a href="#runtime">suggested runtime interface</a> or another interface
338 specified by the runtime.</p>
339
340 </div>
341
342 <!-- ======================================================================= -->
343 <div class="doc_subsection">
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
354 algorithm to the compiler. It is equivalent to specifying the collector name
355 programmatically 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
359 programs that use different garbage collection algorithms.</p>
360
361 </div>
362
363 <!-- ======================================================================= -->
364 <div class="doc_subsection">
365   <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
366 </div>
367
368 <div class="doc_code"><tt>
369   void @llvm.gcroot(i8** %ptrloc, i8* %metadata)
370 </tt></div>
371
372 <div class="doc_text">
373
374 <p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer
375 variable on the stack. The first argument <b>must</b> be a value referring to an alloca instruction
376 or a bitcast of an alloca. The second contains a pointer to metadata that
377 should be associated with the pointer, and <b>must</b> be a constant or global
378 value address. If your target collector uses tags, use a null pointer for
379 metadata.</p>
380
381 <p>Consider the following fragment of Java code:</p>
382
383 <pre>
384        {
385          Object X;   // A null-initialized reference to an object
386          ...
387        }
388 </pre>
389
390 <p>This block (which may be located in the middle of a function or in a loop
391 nest), could be compiled to this LLVM code:</p>
392
393 <pre>
394 Entry:
395    ;; In the entry block for the function, allocate the
396    ;; stack space for X, which is an LLVM pointer.
397    %X = alloca %Object*
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)
403    ...
404
405    ;; "CodeBlock" is the block corresponding to the start
406    ;;  of the scope above.
407 CodeBlock:
408    ;; Java null-initializes pointers.
409    store %Object* null, %Object** %X
410
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">
423   <a name="barriers">Reading and writing references in the heap</a>
424 </div>
425
426 <div class="doc_text">
427
428 <p>Some collectors need to be informed when the mutator (the program that needs
429 garbage collection) either reads a pointer from or writes a pointer to a field
430 of 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
432 code that needs to be executed is usually quite small and not on the critical
433 path of any computation, so the overall performance impact of the barrier is
434 tolerable.</p>
435
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
438 object). Accordingly, these intrinsics take both pointers as separate arguments
439 for 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 %object, i32 0, i32 2, i32 %n</pre></blockquote>
452
453 </div>
454
455 <!-- ======================================================================= -->
456 <div class="doc_subsubsection">
457   <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a>
458 </div>
459
460 <div class="doc_code"><tt>
461 void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
462 </tt></div>
463
464 <div class="doc_text">
465
466 <p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic
467 function. It has exactly the same semantics as a non-volatile <tt>store</tt> to
468 the derived pointer (the third argument).</p>
469
470 <p>Many important algorithms require write barriers, including generational
471 and concurrent collectors. Additionally, write barriers could be used to
472 implement reference counting.</p>
473
474 <p>The use of this intrinsic is optional if the target collector does use
475 write 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
485 <div class="doc_code"><tt>
486 i8* @llvm.gcread(i8* %object, i8** %derived)<br>
487 </tt></div>
488
489 <div class="doc_text">
490
491 <p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function.
492 It has exactly the same semantics as a non-volatile <tt>load</tt> from the
493 derived pointer (the second argument).</p>
494
495 <p>Read barriers are needed by fewer algorithms than write barriers, and may
496 have a greater performance impact since pointer reads are more frequent than
497 writes.</p>
498
499 <p>As with <tt>llvm.gcwrite</tt>, a target collector might not require the use
500 of 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
513 collection at runtime. A program should use these interfaces to accomplish the
514 tasks not supported by the intrinsics.</p>
515
516 <p>Unlike the intrinsics, which are integral to LLVM's code generator, there is
517 nothing unique about these interfaces; a front-end compiler and runtime are free
518 to agree to a different specification.</p>
519
520 <p class="doc_warning">Note: This interface is a work in progress.</p>
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>
532   void llvm_gc_initialize(unsigned InitialHeapSize);
533 </tt></div>
534
535 <p>
536 The <tt>llvm_gc_initialize</tt> function should be called once before any other
537 garbage collection functions are called. This gives the garbage collector the
538 chance to initialize itself and allocate the heap. The initial heap size to
539 allocate should be specified as an argument.
540 </p>
541
542 </div>
543
544 <!-- ======================================================================= -->
545 <div class="doc_subsection">
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
556 garbage collector implementation to allocate memory. It returns a
557 zeroed-out block of memory of the specified size, sufficiently aligned to store
558 any object.</p>
559
560 </div>
561
562 <!-- ======================================================================= -->
563 <div class="doc_subsection">
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>
570   void llvm_gc_collect();
571 </tt></div>
572
573 <p>
574 The <tt>llvm_gc_collect</tt> function is exported by the garbage collector
575 implementations to provide a full collection, even when the heap is not
576 exhausted. This can be used by end-user code as a hint, and may be ignored by
577 the garbage collector.
578 </p>
579
580 </div>
581
582 <!-- ======================================================================= -->
583 <div class="doc_subsection">
584   <a name="traceroots">Tracing GC pointers from the program stack</a>
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>
593 The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code
594 generator that iterates through all of the GC roots on the stack, calling the
595 specified function pointer with each record. For each GC root, the address of
596 the pointer and the meta-data (from the <a
597 href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
598 </p>
599 </div>
600
601 <!-- ======================================================================= -->
602 <div class="doc_subsection">
603   <a name="staticroots">Tracing GC pointers from static roots</a>
604 </div>
605
606 <div class="doc_text">
607 TODO
608 </div>
609
610
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
619 <p>User code specifies which collector plugin to use with the <tt>gc</tt>
620 function attribute or, equivalently, with the <tt>setCollector</tt> method of
621 <tt>Function</tt>.</p>
622
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
625 boilerplate code. LLVM's infrastructure provides access to several important
626 algorithms. For an uncontroversial collector, all that remains may be to emit
627 the assembly code for the collector's unique stack map data structure, which
628 might 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
639 using namespace llvm;
640
641 namespace {
642   class VISIBILITY_HIDDEN MyCollector : public Collector {
643   public:
644     MyCollector() {}
645   };
646   
647   CollectorRegistry::Add&lt;MyCollector&gt;
648   X("mygc", "My bespoke garbage collector.");
649 }</pre></blockquote>
650
651 <p>Using the LLVM makefiles (like the <a
652 href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample
653 project</a>), this can be built into a plugin using a simple makefile:</p>
654
655 <blockquote><pre
656 ># lib/MyGC/Makefile
657
658 LEVEL := ../..
659 LIBRARYNAME = <var>MyGC</var>
660 LOADABLE_MODULE = 1
661
662 include $(LEVEL)/Makefile.common</pre></blockquote>
663
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
666 platform-specific extension):</p>
667
668 <blockquote><pre
669 >$ cat sample.ll
670 define void @f() gc "mygc" {
671 entry:
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
677 as a language-specific compiler front-end.</p>
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
699 collector may do useful work. This matrix summarizes the supported (and planned)
700 features and correlates them with the collection techniques which typically
701 require 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
974 suitable for a wide variety of collectors, but does not currently extend to
975 multithreaded programs. This will be added in the future as there is
976 interest.</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
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();
992
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   }
1000 }</pre></blockquote>
1001
1002 <p>LLVM automatically computes a stack map. All a <tt>Collector</tt> needs to do
1003 is access it using <tt>CollectorMetadata::roots_begin()</tt> and
1004 -<tt>end()</tt>. If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code
1005 generation 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
1023 entry to the function. This prevents the reachability analysis from finding
1024 uninitialized values in stack roots at runtime, which will almost certainly
1025 cause it to segfault. This initialization occurs before custom lowering, so the
1026 two may be used together.</p>
1027
1028 <p>Since LLVM does not yet compute liveness information, this feature should be
1029 used by all collectors which do not custom lower <tt>llvm.gcroot</tt>, and even
1030 some 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
1044 flags allow the collector to perform any required transformation on the LLVM
1045 IR:</p>
1046
1047 <blockquote><pre
1048 >class MyCollector : public Collector {
1049 public:
1050   MyCollector() {
1051     CustomRoots = true;
1052     CustomReadBarriers = true;
1053     CustomWriteBarriers = true;
1054   }
1055   
1056   virtual bool initializeCustomLowering(Module &amp;M);
1057   virtual bool performCustomLowering(Function &amp;F);
1058 };</pre></blockquote>
1059
1060 <p>If any of these flags are set, then LLVM suppresses its default lowering for
1061 the corresponding intrinsics and instead passes them on to a custom lowering
1062 pass 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,
1074 then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the
1075 corresponding barriers.</p>
1076
1077 <p><tt>performCustomLowering</tt>, must comply with the same restrictions as <a
1078 href="WritingAnLLVMPass.html#runOnFunction"><tt>runOnFunction</tt></a>, and
1079 that <tt>initializeCustomLowering</tt> has the same semantics as <a
1080 href="WritingAnLLVMPass.html#doInitialization_mod"><tt>doInitialization(Module
1081 &amp;)</tt></a>.</p>
1082
1083 <p>The following can be used as a template:</p>
1084
1085 <blockquote><pre
1086 >#include "llvm/Module.h"
1087 #include "llvm/IntrinsicInst.h"
1088
1089 bool MyCollector::initializeCustomLowering(Module &amp;M) {
1090   return false;
1091 }
1092
1093 bool MyCollector::performCustomLowering(Function &amp;F) {
1094   bool MadeChange = false;
1095   
1096   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1097     for (BasicBlock::iterator II = BB-&gt;begin(), E = BB-&gt;end(); II != E; )
1098       if (IntrinsicInst *CI = dyn_cast&lt;IntrinsicInst&gt;(II++))
1099         if (Function *F = CI-&gt;getCalledFunction())
1100           switch (F-&gt;getIntrinsicID()) {
1101           case Intrinsic::gcwrite:
1102             // Handle llvm.gcwrite.
1103             CI-&gt;eraseFromParent();
1104             MadeChange = true;
1105             break;
1106           case Intrinsic::gcread:
1107             // Handle llvm.gcread.
1108             CI-&gt;eraseFromParent();
1109             MadeChange = true;
1110             break;
1111           case Intrinsic::gcroot:
1112             // Handle llvm.gcroot.
1113             CI-&gt;eraseFromParent();
1114             MadeChange = true;
1115             break;
1116           }
1117   
1118   return MadeChange;
1119 }</pre></blockquote>
1120
1121 </div>
1122
1123
1124 <!-- ======================================================================= -->
1125 <div class="doc_subsection">
1126   <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
1127 </div>
1128
1129 <div class="doc_text">
1130
1131 <p>LLVM can compute four kinds of safe points:</p>
1132
1133 <blockquote><pre
1134 >namespace GC {
1135   /// PointKind - The type of a collector-safe point.
1136   /// 
1137   enum PointKind {
1138     Loop,    //&lt; Instr is a loop (backwards branch).
1139     Return,  //&lt; Instr is a return instruction.
1140     PreCall, //&lt; Instr is a call instruction.
1141     PostCall //&lt; Instr is the return address of a call.
1142   };
1143 }</pre></blockquote>
1144
1145 <p>A collector can request any combination of the four by setting the 
1146 <tt>NeededSafePoints</tt> mask:</p>
1147
1148 <blockquote><pre
1149 >MyCollector::MyCollector() {
1150   NeededSafePoints = 1 &lt;&lt; GC::Loop
1151                    | 1 &lt;&lt; GC::Return
1152                    | 1 &lt;&lt; GC::PreCall
1153                    | 1 &lt;&lt; GC::PostCall;
1154 }</pre></blockquote>
1155
1156 <p>It can then use the following routines to access safe points.</p>
1157
1158 <blockquote><pre
1159 >for (iterator I = begin(), E = end(); I != E; ++I) {
1160   CollectorMetadata *MD = *I;
1161   size_t PointCount = MD-&gt;size();
1162
1163   for (CollectorMetadata::iterator PI = MD-&gt;begin(),
1164                                    PE = MD-&gt;end(); PI != PE; ++PI) {
1165     GC::PointKind PointKind = PI-&gt;Kind;
1166     unsigned PointNum = PI-&gt;Num;
1167   }
1168 }
1169 </pre></blockquote>
1170
1171 <p>Almost every collector requires <tt>PostCall</tt> safe points, since these
1172 correspond to the moments when the function is suspended during a call to a
1173 subroutine.</p>
1174
1175 <p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee
1176 that the application will reach a safe point within a bounded amount of time,
1177 even if it is executing a long-running loop which contains no function
1178 calls.</p>
1179
1180 <p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt>
1181 safe points to implement "stop the world" techniques using self-modifying code,
1182 where it is important that the program not exit the function without reaching a
1183 safe point (because only the topmost function has been patched).</p>
1184
1185 </div>
1186
1187
1188 <!-- ======================================================================= -->
1189 <div class="doc_subsection">
1190   <a name="assembly">Emitting assembly code:
1191     <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a>
1192 </div>
1193
1194 <div class="doc_text">
1195
1196 <p>LLVM allows a collector to print arbitrary assembly code before and after
1197 the rest of a module's assembly code. From the latter callback, the collector
1198 can print stack maps built by the code generator.</p>
1199
1200 <p>Note that LLVM does not currently have analogous APIs to support code
1201 generation in the JIT, nor using the object writers.</p>
1202
1203 <blockquote><pre
1204 >class MyCollector : public Collector {
1205 public:
1206   virtual void beginAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1207                              const TargetAsmInfo &amp;TAI);
1208
1209   virtual void finishAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1210                               const TargetAsmInfo &amp;TAI);
1211 }</pre></blockquote>
1212
1213 <p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to
1214 print portable assembly code to the <tt>std::ostream</tt>. The collector itself
1215 contains the stack map for the entire module, and may access the
1216 <tt>CollectorMetadata</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
1217 methods. Here's a realistic example:</p>
1218
1219 <blockquote><pre
1220 >#include "llvm/CodeGen/AsmPrinter.h"
1221 #include "llvm/Function.h"
1222 #include "llvm/Target/TargetMachine.h"
1223 #include "llvm/Target/TargetData.h"
1224 #include "llvm/Target/TargetAsmInfo.h"
1225
1226 void MyCollector::beginAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1227                                 const TargetAsmInfo &amp;TAI) {
1228   // Nothing to do.
1229 }
1230
1231 void MyCollector::finishAssembly(std::ostream &amp;OS, AsmPrinter &amp;AP,
1232                                  const TargetAsmInfo &amp;TAI) {
1233   // Set up for emitting addresses.
1234   const char *AddressDirective;
1235   int AddressAlignLog;
1236   if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) {
1237     AddressDirective = TAI.getData32bitsDirective();
1238     AddressAlignLog = 2;
1239   } else {
1240     AddressDirective = TAI.getData64bitsDirective();
1241     AddressAlignLog = 3;
1242   }
1243   
1244   // Put this in the data section.
1245   AP.SwitchToDataSection(TAI.getDataSection());
1246   
1247   // For each function...
1248   for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
1249     CollectorMetadata &amp;MD = **FI;
1250     
1251     // Emit this data structure:
1252     // 
1253     // struct {
1254     //   int32_t PointCount;
1255     //   struct {
1256     //     void *SafePointAddress;
1257     //     int32_t LiveCount;
1258     //     int32_t LiveOffsets[LiveCount];
1259     //   } Points[PointCount];
1260     // } __gcmap_&lt;FUNCTIONNAME&gt;;
1261     
1262     // Align to address width.
1263     AP.EmitAlignment(AddressAlignLog);
1264     
1265     // Emit the symbol by which the stack map can be found.
1266     std::string Symbol;
1267     Symbol += TAI.getGlobalPrefix();
1268     Symbol += "__gcmap_";
1269     Symbol += MD.getFunction().getName();
1270     if (const char *GlobalDirective = TAI.getGlobalDirective())
1271       OS &lt;&lt; GlobalDirective &lt;&lt; Symbol &lt;&lt; "\n";
1272     OS &lt;&lt; TAI.getGlobalPrefix() &lt;&lt; Symbol &lt;&lt; ":\n";
1273     
1274     // Emit PointCount.
1275     AP.EmitInt32(MD.size());
1276     AP.EOL("safe point count");
1277     
1278     // And each safe point...
1279     for (CollectorMetadata::iterator PI = MD.begin(),
1280                                      PE = MD.end(); PI != PE; ++PI) {
1281       // Align to address width.
1282       AP.EmitAlignment(AddressAlignLog);
1283       
1284       // Emit the address of the safe point.
1285       OS &lt;&lt; AddressDirective
1286          &lt;&lt; TAI.getPrivateGlobalPrefix() &lt;&lt; "label" &lt;&lt; PI-&gt;Num;
1287       AP.EOL("safe point address");
1288       
1289       // Emit the stack frame size.
1290       AP.EmitInt32(MD.getFrameSize());
1291       AP.EOL("stack frame size");
1292       
1293       // Emit the number of live roots in the function.
1294       AP.EmitInt32(MD.live_size(PI));
1295       AP.EOL("live root count");
1296       
1297       // And for each live root...
1298       for (CollectorMetadata::live_iterator LI = MD.live_begin(PI),
1299                                             LE = MD.live_end(PI);
1300                                             LI != LE; ++LI) {
1301         // Print its offset within the stack frame.
1302         AP.EmitInt32(LI-&gt;StackOffset);
1303         AP.EOL("stack offset");
1304       }
1305     }
1306   }
1307 }
1308 </pre></blockquote>
1309
1310 </div>
1311
1312
1313 <!-- *********************************************************************** -->
1314 <div class="doc_section">
1315   <a name="runtime-impl">Implementing a collector runtime</a>
1316 </div>
1317 <!-- *********************************************************************** -->
1318
1319 <div class="doc_text">
1320
1321 <p>Implementing a garbage collector for LLVM is fairly straightforward. The
1322 LLVM garbage collectors are provided in a form that makes them easy to link into
1323 the language-specific runtime that a language front-end would use. They require
1324 functionality from the language-specific runtime to get information about <a
1325 href="#gcdescriptors">where pointers are located in heap objects</a>.</p>
1326
1327 <p>The implementation must include the
1328 <a href="#allocate"><tt>llvm_gc_allocate</tt></a> and
1329 <a href="#explicit"><tt>llvm_gc_collect</tt></a> functions. To do this, it will
1330 probably have to <a href="#traceroots">trace through the roots
1331 from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors
1332 for heap objects</a>. Luckily, there are some <a href="#usage">example
1333 implementations</a> available.
1334 </p>
1335 </div>
1336
1337
1338 <!-- ======================================================================= -->
1339 <div class="doc_subsection">
1340   <a name="gcdescriptors">Tracing GC pointers from heap objects</a>
1341 </div>
1342
1343 <div class="doc_text">
1344 <p>
1345 The three most common ways to keep track of where pointers live in heap objects
1346 are (listed in order of space overhead required):</p>
1347
1348 <ol>
1349 <li>In languages with polymorphic objects, pointers from an object header are
1350 usually used to identify the GC pointers in the heap object. This is common for
1351 object-oriented languages like Self, Smalltalk, Java, or C#.</li>
1352
1353 <li>If heap objects are not polymorphic, often the "shape" of the heap can be
1354 determined from the roots of the heap or from some other meta-data [<a
1355 href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a
1356 href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can
1357 propagate the information around from meta data stored with the roots. This
1358 often eliminates the need to have a header on objects in the heap. This is
1359 common in the ML family.</li>
1360
1361 <li>If all heap objects have pointers in the same locations, or pointers can be
1362 distinguished just by looking at them (e.g., the low order bit is clear), no
1363 book-keeping is needed at all. This is common for Lisp-like languages.</li>
1364 </ol>
1365
1366 <p>The LLVM garbage collectors are capable of supporting all of these styles of
1367 language, including ones that mix various implementations. To do this, it
1368 allows the source-language to associate meta-data with the <a
1369 href="#gcroot">stack roots</a>, and the heap tracing routines can propagate the
1370 information. In addition, LLVM allows the front-end to extract GC information
1371 in any form from a specific object pointer (this supports situations #1 and #3).
1372 </p>
1373
1374 </div>
1375
1376
1377 <!-- *********************************************************************** -->
1378 <div class="doc_section">
1379   <a name="references">References</a>
1380 </div>
1381 <!-- *********************************************************************** -->
1382
1383 <div class="doc_text">
1384
1385 <p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
1386 W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
1387
1388 <p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
1389 strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
1390 PLDI'91.</p>
1391
1392 <p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
1393 explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
1394 conference on LISP and functional programming.</p>
1395
1396 <p><a name="henderson02">[Henderson2002]</a> <a
1397 href="http://citeseer.ist.psu.edu/henderson02accurate.html">
1398 Accurate Garbage Collection in an Uncooperative Environment</a>.
1399 Fergus Henderson. International Symposium on Memory Management 2002.</p>
1400
1401 </div>
1402
1403
1404 <!-- *********************************************************************** -->
1405
1406 <hr>
1407 <address>
1408   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1409   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1410   <a href="http://validator.w3.org/check/referer"><img
1411   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1412
1413   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1414   <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
1415   Last modified: $Date$
1416 </address>
1417
1418 </body>
1419 </html>