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="#intrinsics">Collection intrinsics</a>
  40     <ul>
  41     <li><a href="#gcroot">Identifying GC roots on the stack:
  42       <tt>llvm.gcroot</tt></a></li>
  43     <li><a href="#barriers">Reading and writing references in the heap</a>
  44       <ul>
  45       <li><a href="#gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a></li>
  46       <li><a href="#gcread">Read barrier: <tt>llvm.gcread</tt></a></li>
  47       </ul>
  48     </li>
  49     </ul>
  50   </li>
  51
  52   <li><a href="#runtime">Recommended runtime interface</a>
  53     <ul>
  54     <li><a href="#initialize">Garbage collector startup and
  55     initialization</a></li>
  56     <li><a href="#allocate">Allocating memory from the GC</a></li>
  57     <li><a href="#explicit">Explicit invocation of the garbage
  58     collector</a></li>
  59     <li><a href="#traceroots">Tracing GC pointers from the program
  60     stack</a></li>
  61     <li><a href="#staticroots">Tracing GC pointers from static roots</a></li>
  62     </ul>
  63   </li>
  64
  65   <li><a href="#plugin">Implementing a collector plugin</a>
  66     <ul>
  67     <li><a href="#collector-algos">Overview of available features</a></li>
  68     <li><a href="#stack-map">Computing stack maps</a></li>
  69     <li><a href="#init-roots">Initializing roots to null:
  70       <tt>InitRoots</tt></a></li>
  71     <li><a href="#custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
  72       <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a></li>
  73     <li><a href="#safe-points">Generating safe points:
  74       <tt>NeededSafePoints</tt></a></li>
  75     <li><a href="#assembly">Emitting assembly code:
  76       <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a></li>
  77     </ul>
  78   </li>
  79
  80   <li><a href="#runtime-impl">Implementing a collector runtime</a>
  81     <ul>
  82       <li><a href="#gcdescriptors">Tracing GC pointers from heap
  83       objects</a></li>
  84     </ul>
  85   </li>
  86
  87   <li><a href="#references">References</a></li>
  88
  89 </ol>
  90
  91 <div class="doc_author">
  92   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and
  93      Gordon Henriksen</p>
  94 </div>
  95
  96 <!-- *********************************************************************** -->
  97 <div class="doc_section">
  98   <a name="introduction">Introduction</a>
  99 </div>
 100 <!-- *********************************************************************** -->
 101
 102 <div class="doc_text">
 103
 104 <p>Garbage collection is a widely used technique that frees the programmer from
 105 having to know the lifetimes of heap objects, making software easier to produce
 106 and maintain. Many programming languages rely on garbage collection for
 107 automatic memory management. There are two primary forms of garbage collection:
 108 conservative and accurate.</p>
 109
 110 <p>Conservative garbage collection often does not require any special support
 111 from either the language or the compiler: it can handle non-type-safe
 112 programming languages (such as C/C++) and does not require any special
 113 information from the compiler. The
 114 <a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is
 115 an example of a state-of-the-art conservative collector.</p>
 116
 117 <p>Accurate garbage collection requires the ability to identify all pointers in
 118 the program at run-time (which requires that the source-language be type-safe in
 119 most cases). Identifying pointers at run-time requires compiler support to
 120 locate all places that hold live pointer variables at run-time, including the
 121 <a href="#gcroot">processor stack and registers</a>.</p>
 122
 123 <p>Conservative garbage collection is attractive because it does not require any
 124 special compiler support, but it does have problems. In particular, because the
 125 conservative garbage collector cannot <i>know</i> that a particular word in the
 126 machine is a pointer, it cannot move live objects in the heap (preventing the
 127 use of compacting and generational GC algorithms) and it can occasionally suffer
 128 from memory leaks due to integer values that happen to point to objects in the
 129 program. In addition, some aggressive compiler transformations can break
 130 conservative garbage collectors (though these seem rare in practice).</p>
 131
 132 <p>Accurate garbage collectors do not suffer from any of these problems, but
 133 they can suffer from degraded scalar optimization of the program. In particular,
 134 because the runtime must be able to identify and update all pointers active in
 135 the program, some optimizations are less effective. In practice, however, the
 136 locality and performance benefits of using aggressive garbage allocation
 137 techniques dominates any low-level losses.</p>
 138
 139 <p>This document describes the mechanisms and interfaces provided by LLVM to
 140 support accurate garbage collection.</p>
 141
 142 </div>
 143
 144 <!-- ======================================================================= -->
 145 <div class="doc_subsection">
 146   <a name="feature">GC features provided and algorithms supported</a>
 147 </div>
 148
 149 <div class="doc_text">
 150
 151 <p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
 152 collection intrinsics</a> which offer support for a broad class of
 153 collector models. For instance, the intrinsics permit:</p>
 154
 155 <ul>
 156   <li>semi-space collectors</li>
 157   <li>mark-sweep collectors</li>
 158   <li>generational collectors</li>
 159   <li>reference counting</li>
 160   <li>incremental collectors</li>
 161   <li>concurrent collectors</li>
 162   <li>cooperative collectors</li>
 163 </ul>
 164
 165 <p>We hope that the primitive support built into the LLVM IR is sufficient to
 166 support a broad class of garbage collected languages including Scheme, ML, Java,
 167 C#, Perl, Python, Lua, Ruby, other scripting languages, and more.</p>
 168
 169 <p>However, LLVM does not itself implement a garbage collector. This is because
 170 collectors are tightly coupled to object models, and LLVM is agnostic to object
 171 models. Since LLVM is agnostic to object models, it would be inappropriate for
 172 LLVM to dictate any particular collector. Instead, LLVM provides a framework for
 173 garbage collector implementations in two manners:</p>
 174
 175 <ul>
 176   <li><b>At compile time</b> with <a href="#plugin">collector plugins</a> for
 177   the compiler. Collector plugins have ready access to important garbage
 178   collector algorithms. Leveraging these tools, it is straightforward to
 179   emit type-accurate stack maps for your runtime in as little as ~100 lines of
 180   C++ code.</li>
 181
 182   <li><b>At runtime</b> with <a href="#runtime">suggested runtime
 183   interfaces</a>, which allow front-end compilers to support a range of
 184   collection runtimes.</li>
 185 </ul>
 186
 187 </div>
 188
 189 <!-- *********************************************************************** -->
 190 <div class="doc_section">
 191   <a name="usage">Using the collectors</a>
 192 </div>
 193 <!-- *********************************************************************** -->
 194
 195 <div class="doc_text">
 196
 197 <p>In general, using a collector implies:</p>
 198
 199 <ul>
 200   <li>Emitting compatible code, including initialization in the main
 201       program.</li>
 202   <li>Loading a compiler plugin if the collector is not statically linked with
 203       your compiler. For <tt>llc</tt>, use the <tt>-load</tt> option.</li>
 204   <li>Selecting the collection algorithm with <tt>llc -gc=</tt> or by setting
 205       <tt>llvm::TheCollector</tt>.</li>
 206   <li>Linking your final executable with the garbage collector runtime.</li>
 207 </ul>
 208
 209 <p>This table summarizes the available runtimes.</p>
 210
 211 <table>
 212   <tr>
 213     <th>Collector</th>
 214     <th><tt>llc</tt> arguments</th>
 215     <th>Linkage</th>
 216     <th><tt>gcroot</tt></th>
 217     <th><tt>gcread</tt></th>
 218     <th><tt>gcwrite</tt></th>
 219   </tr>
 220   <tr valign="baseline">
 221     <td><a href="#semispace">SemiSpace</a></td>
 222     <td><tt>-gc=shadow-stack</tt></td>
 223     <td>TODO FIXME</td>
 224     <td>required</td>
 225     <td>optional</td>
 226     <td>optional</td>
 227   </tr>
 228   <tr valign="baseline">
 229     <td><a href="#ocaml">Ocaml</a></td>
 230     <td><tt>-gc=ocaml</tt></td>
 231     <td><i>provided by ocamlopt</i></td>
 232     <td>required</td>
 233     <td>optional</td>
 234     <td>optional</td>
 235   </tr>
 236 </table>
 237
 238 <p>The sections for <a href="#intrinsics">Collection intrinsics</a> and
 239 <a href="#runtime">Recommended runtime interface</a> detail the interfaces that
 240 collectors may require user programs to utilize.</p>
 241
 242 </div>
 243
 244 <!-- ======================================================================= -->
 245 <div class="doc_subsection">
 246   <a name="shadow-stack">ShadowStack - A highly portable collector</a>
 247 </div>
 248
 249 <div class="doc_code"><tt>
 250   Collector *llvm::createShadowStackCollector();
 251 </tt></div>
 252
 253 <div class="doc_text">
 254
 255 <p>The ShadowStack collector is invoked with <tt>llc -gc=shadow-stack</tt>.
 256 Unlike many collectors which rely on a cooperative code generator to generate
 257 stack maps, this algorithm carefully maintains a linked list of stack root
 258 descriptors [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow
 259 stack," mirrors the machine stack. Maintaining this data structure is slower
 260 than using stack maps, but has a significant portability advantage because it
 261 requires no special support from the target code generator.</p>
 262
 263 <p>The ShadowStack collector does not use read or write barriers, so the user
 264 program may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt>
 265 and <tt>llvm.gcwrite</tt>.</p>
 266
 267 <p>The ShadowStack collector is a compiler plugin only. It must be paired with a
 268 compatible runtime.</p>
 269
 270 </div>
 271
 272 <!-- ======================================================================= -->
 273 <div class="doc_subsection">
 274   <a name="semispace">SemiSpace - A simple copying collector runtime</a>
 275 </div>
 276
 277 <div class="doc_text">
 278
 279 <p>The SemiSpace runtime implements with the <a href="runtime">suggested
 280 runtime interface</a> and is compatible the ShadowStack collector's code
 281 generation.</p>
 282
 283 <p>SemiSpace is a very simple copying collector. When it starts up, it
 284 allocates two blocks of memory for the heap. It uses a simple bump-pointer
 285 allocator to allocate memory from the first block until it runs out of space.
 286 When it runs out of space, it traces through all of the roots of the program,
 287 copying blocks to the other half of the memory space.</p>
 288
 289 <p>This runtime is highly experimental and has not been used in a real project.
 290 Enhancements would be welcomed.</p>
 291
 292 </div>
 293
 294 <!-- ======================================================================= -->
 295 <div class="doc_subsection">
 296   <a name="ocaml">Ocaml - An Objective Caml-compatible collector</a>
 297 </div>
 298
 299 <div class="doc_code"><tt>
 300   Collector *llvm::createOcamlCollector();
 301 </tt></div>
 302
 303 <div class="doc_text">
 304
 305 <p>The ocaml collector is invoked with <tt>llc -gc=ocaml</tt>. It supports the
 306 <a href="http://caml.inria.fr/">Objective Caml</a> language runtime by emitting
 307 a type-accurate stack map in the form of an ocaml 3.10.0-compatible frametable.
 308 The linkage requirements are satisfied automatically by the <tt>ocamlopt</tt>
 309 compiler when linking an executable.</p>
 310
 311 <p>The ocaml collector does not use read or write barriers, so the user program
 312 may use <tt>load</tt> and <tt>store</tt> instead of <tt>llvm.gcread</tt> and
 313 <tt>llvm.gcwrite</tt>.</p>
 314
 315 </div>
 316
 317
 318 <!-- *********************************************************************** -->
 319 <div class="doc_section">
 320   <a name="intrinsics">Collection intrinsics</a>
 321 </div>
 322 <!-- *********************************************************************** -->
 323
 324 <div class="doc_text">
 325
 326 <p>This section describes the garbage collection facilities provided by the
 327 <a href="LangRef.html">LLVM intermediate representation</a>.</p>
 328
 329 <p>These facilities are limited to those strictly necessary for compilation.
 330 They are not intended to be a complete interface to any garbage collector.
 331 Notably, heap allocation is not among the supplied primitives. A user program
 332 will also need to interface with the runtime, using either the
 333 <a href="#runtime">suggested runtime interface</a> or another interface
 334 specified by the runtime.</p>
 335
 336 </div>
 337
 338 <!-- ======================================================================= -->
 339 <div class="doc_subsection">
 340   <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
 341 </div>
 342
 343 <div class="doc_code"><tt>
 344   void %llvm.gcroot(i8** %ptrloc, i8* %metadata)
 345 </tt></div>
 346
 347 <div class="doc_text">
 348
 349 <p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer
 350 variable on the stack. The first argument <b>must</b> be an alloca instruction
 351 or a bitcast of an alloca. The second contains a pointer to metadata that
 352 should be associated with the pointer, and <b>must</b> be a constant or global
 353 value address. If your target collector uses tags, use a null pointer for
 354 metadata.</p>
 355
 356 <p>Consider the following fragment of Java code:</p>
 357
 358 <pre>
 359        {
 360          Object X;   // A null-initialized reference to an object
 361          ...
 362        }
 363 </pre>
 364
 365 <p>This block (which may be located in the middle of a function or in a loop
 366 nest), could be compiled to this LLVM code:</p>
 367
 368 <pre>
 369 Entry:
 370    ;; In the entry block for the function, allocate the
 371    ;; stack space for X, which is an LLVM pointer.
 372    %X = alloca %Object*
 373
 374    ;; Tell LLVM that the stack space is a stack root.
 375    ;; Java has type-tags on objects, so we pass null as metadata.
 376    %tmp = bitcast %Object** %X to i8**
 377    call void %llvm.gcroot(%i8** %X, i8* null)
 378    ...
 379
 380    ;; "CodeBlock" is the block corresponding to the start
 381    ;;  of the scope above.
 382 CodeBlock:
 383    ;; Java null-initializes pointers.
 384    store %Object* null, %Object** %X
 385
 386    ...
 387
 388    ;; As the pointer goes out of scope, store a null value into
 389    ;; it, to indicate that the value is no longer live.
 390    store %Object* null, %Object** %X
 391    ...
 392 </pre>
 393
 394 </div>
 395
 396 <!-- ======================================================================= -->
 397 <div class="doc_subsection">
 398   <a name="barriers">Reading and writing references in the heap</a>
 399 </div>
 400
 401 <div class="doc_text">
 402
 403 <p>Some collectors need to be informed when the mutator (the program that needs
 404 garbage collection) either reads a pointer from or writes a pointer to a field
 405 of a heap object. The code fragments inserted at these points are called
 406 <em>read barriers</em> and <em>write barriers</em>, respectively. The amount of
 407 code that needs to be executed is usually quite small and not on the critical
 408 path of any computation, so the overall performance impact of the barrier is
 409 tolerable.</p>
 410
 411 <p>Barriers often require access to the <em>object pointer</em> rather than the
 412 <em>derived pointer</em> (which is a pointer to the field within the
 413 object). Accordingly, these intrinsics take both pointers as separate arguments
 414 for completeness. In this snippet, <tt>%object</tt> is the object pointer, and
 415 <tt>%derived</tt> is the derived pointer:</p>
 416
 417 <blockquote><pre
 418 >    ;; An array type.
 419     %class.Array = type { %class.Object, i32, [0 x %class.Object*] }
 420 ...
 421
 422     ;; Load the object pointer from a gcroot.
 423     %object = load %class.Array** %object_addr
 424
 425     ;; Compute the derived pointer.
 426     %derived = getelementptr %obj, i32 0, i32 2, i32 %n</pre></blockquote>
 427
 428 </div>
 429
 430 <!-- ======================================================================= -->
 431 <div class="doc_subsubsection">
 432   <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a>
 433 </div>
 434
 435 <div class="doc_code"><tt>
 436 void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
 437 </tt></div>
 438
 439 <div class="doc_text">
 440
 441 <p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic
 442 function. It has exactly the same semantics as a non-volatile <tt>store</tt> to
 443 the derived pointer (the third argument).</p>
 444
 445 <p>Many important algorithms require write barriers, including generational
 446 and concurrent collectors. Additionally, write barriers could be used to
 447 implement reference counting.</p>
 448
 449 <p>The use of this intrinsic is optional if the target collector does use
 450 write barriers. If so, the collector will replace it with the corresponding
 451 <tt>store</tt>.</p>
 452
 453 </div>
 454
 455 <!-- ======================================================================= -->
 456 <div class="doc_subsubsection">
 457   <a name="gcread">Read barrier: <tt>llvm.gcread</tt></a>
 458 </div>
 459
 460 <div class="doc_code"><tt>
 461 i8* @llvm.gcread(i8* %object, i8** %derived)<br>
 462 </tt></div>
 463
 464 <div class="doc_text">
 465
 466 <p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function.
 467 It has exactly the same semantics as a non-volatile <tt>load</tt> from the
 468 derived pointer (the second argument).</p>
 469
 470 <p>Read barriers are needed by fewer algorithms than write barriers, and may
 471 have a greater performance impact since pointer reads are more frequent than
 472 writes.</p>
 473
 474 <p>As with <tt>llvm.gcwrite</tt>, a target collector might not require the use
 475 of this intrinsic.</p>
 476
 477 </div>
 478
 479 <!-- *********************************************************************** -->
 480 <div class="doc_section">
 481   <a name="runtime">Recommended runtime interface</a>
 482 </div>
 483 <!-- *********************************************************************** -->
 484
 485 <div class="doc_text">
 486
 487 <p>LLVM specifies the following recommended runtime interface to the garbage
 488 collection at runtime. A program should use these interfaces to accomplish the
 489 tasks not supported by the intrinsics.</p>
 490
 491 <p>Unlike the intrinsics, which are integral to LLVM's code generator, there is
 492 nothing unique about these interfaces; a front-end compiler and runtime are free
 493 to agree to a different specification.</p>
 494
 495 <p class="doc_warning">Note: This interface is a work in progress.</p>
 496
 497 </div>
 498
 499 <!-- ======================================================================= -->
 500 <div class="doc_subsection">
 501   <a name="initialize">Garbage collector startup and initialization</a>
 502 </div>
 503
 504 <div class="doc_text">
 505
 506 <div class="doc_code"><tt>
 507   void llvm_gc_initialize(unsigned InitialHeapSize);
 508 </tt></div>
 509
 510 <p>
 511 The <tt>llvm_gc_initialize</tt> function should be called once before any other
 512 garbage collection functions are called. This gives the garbage collector the
 513 chance to initialize itself and allocate the heap. The initial heap size to
 514 allocate should be specified as an argument.
 515 </p>
 516
 517 </div>
 518
 519 <!-- ======================================================================= -->
 520 <div class="doc_subsection">
 521   <a name="allocate">Allocating memory from the GC</a>
 522 </div>
 523
 524 <div class="doc_text">
 525
 526 <div class="doc_code"><tt>
 527   void *llvm_gc_allocate(unsigned Size);
 528 </tt></div>
 529
 530 <p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the
 531 garbage collector implementation to allocate memory. It returns a
 532 zeroed-out block of memory of the specified size, sufficiently aligned to store
 533 any object.</p>
 534
 535 </div>
 536
 537 <!-- ======================================================================= -->
 538 <div class="doc_subsection">
 539   <a name="explicit">Explicit invocation of the garbage collector</a>
 540 </div>
 541
 542 <div class="doc_text">
 543
 544 <div class="doc_code"><tt>
 545   void llvm_gc_collect();
 546 </tt></div>
 547
 548 <p>
 549 The <tt>llvm_gc_collect</tt> function is exported by the garbage collector
 550 implementations to provide a full collection, even when the heap is not
 551 exhausted. This can be used by end-user code as a hint, and may be ignored by
 552 the garbage collector.
 553 </p>
 554
 555 </div>
 556
 557 <!-- ======================================================================= -->
 558 <div class="doc_subsection">
 559   <a name="traceroots">Tracing GC pointers from the program stack</a>
 560 </div>
 561
 562 <div class="doc_text">
 563   <div class="doc_code"><tt>
 564      void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
 565   </tt></div>
 566
 567 <p>
 568 The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code
 569 generator that iterates through all of the GC roots on the stack, calling the
 570 specified function pointer with each record. For each GC root, the address of
 571 the pointer and the meta-data (from the <a
 572 href="#roots"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
 573 </p>
 574 </div>
 575
 576 <!-- ======================================================================= -->
 577 <div class="doc_subsection">
 578   <a name="staticroots">Tracing GC pointers from static roots</a>
 579 </div>
 580
 581 <div class="doc_text">
 582 TODO
 583 </div>
 584
 585
 586 <!-- *********************************************************************** -->
 587 <div class="doc_section">
 588   <a name="plugin">Implementing a collector plugin</a>
 589 </div>
 590 <!-- *********************************************************************** -->
 591
 592 <div class="doc_text">
 593
 594 <p>To implement a collector plugin, it is necessary to subclass
 595 <tt>llvm::Collector</tt>, which can be accomplished in a few lines of
 596 boilerplate code. LLVM's infrastructure provides access to several important
 597 algorithms. For an uncontroversial collector, all that remains may be to emit
 598 the assembly code for the collector's unique stack map data structure, which
 599 might be accomplished in as few as 100 LOC.</p>
 600
 601 <p>To subclass <tt>llvm::Collector</tt> and register a collector:</p>
 602
 603 <blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM collector plugin
 604
 605 #include "llvm/CodeGen/Collector.h"
 606 #include "llvm/CodeGen/Collectors.h"
 607 #include "llvm/CodeGen/CollectorMetadata.h"
 608 #include "llvm/Support/Compiler.h"
 609
 610 using namespace llvm;
 611
 612 namespace {
 613   class VISIBILITY_HIDDEN MyCollector : public Collector {
 614   public:
 615     MyCollector() {}
 616   };
 617
 618   CollectorRegistry::Add&lt;MyCollector&gt;
 619   X("mygc", "My custom garbage collector.");
 620 }</pre></blockquote>
 621
 622 <p>Using the LLVM makefiles (like the <a
 623 href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample
 624 project</a>), this can be built into a plugin using a simple makefile:</p>
 625
 626 <blockquote><pre
 627 ># lib/MyGC/Makefile
 628
 629 LEVEL := ../..
 630 LIBRARYNAME = <var>MyGC</var>
 631 LOADABLE_MODULE = 1
 632
 633 include $(LEVEL)/Makefile.common</pre></blockquote>
 634
 635 <blockquote><pre
 636 ></pre></blockquote>
 637
 638 <p>Once the plugin is compiled, user code may be compiled using <tt>llc
 639 -load=<var>MyGC.so</var> -gc=mygc</tt> (though <var>MyGC.so</var> may have some
 640 other platform-specific extension).</p>
 641
 642 <!-- BEGIN FIXME: Gross -->
 643 <p>To use a collector in a tool other than <tt>llc</tt>, simply assign a
 644 <tt>Collector</tt> to the <tt>llvm::TheCollector</tt> variable:</p>
 645
 646 <blockquote><pre
 647 >TheCollector = new MyGC();</pre></blockquote>
 648 <!-- /FIXME GROSS -->
 649
 650 </div>
 651
 652 <!-- ======================================================================= -->
 653 <div class="doc_subsection">
 654   <a name="collector-algos">Overview of available features</a>
 655 </div>
 656
 657 <div class="doc_text">
 658
 659 <p>The boilerplate collector above does nothing. More specifically:</p>
 660
 661 <ul>
 662   <li><tt>llvm.gcread</tt> calls are replaced with the corresponding
 663       <tt>load</tt> instruction.</li>
 664   <li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding
 665       <tt>store</tt> instruction.</li>
 666   <li>No stack map is emitted, and no safe points are added.</li>
 667 </ul>
 668
 669 <p><tt>Collector</tt> provides a range of features through which a plugin
 670 collector may do useful work. This matrix summarizes the supported (and planned)
 671 features and correlates them with the collection techniques which typically
 672 require them.</p>
 673
 674 <table>
 675   <tr>
 676     <th>Algorithm</th>
 677     <th>Done</th>
 678     <th>shadow stack</th>
 679     <th>refcount</th>
 680     <th>mark-sweep</th>
 681     <th>copying</th>
 682     <th>incremental</th>
 683     <th>threaded</th>
 684     <th>concurrent</th>
 685   </tr>
 686   <tr>
 687     <th class="rowhead"><a href="#stack-map">stack map</a></th>
 688     <td>&#10004;</td>
 689     <td></td>
 690     <td></td>
 691     <td>&#10008;</td>
 692     <td>&#10008;</td>
 693     <td>&#10008;</td>
 694     <td>&#10008;</td>
 695     <td>&#10008;</td>
 696   </tr>
 697   <tr>
 698     <th class="rowhead"><a href="#init-roots">initialize roots</a></th>
 699     <td>&#10004;</td>
 700     <td>&#10008;</td>
 701     <td>&#10008;</td>
 702     <td>&#10008;</td>
 703     <td>&#10008;</td>
 704     <td>&#10008;</td>
 705     <td>&#10008;</td>
 706     <td>&#10008;</td>
 707   </tr>
 708   <tr class="doc_warning">
 709     <th class="rowhead">derived pointers</th>
 710     <td>NO</td>
 711     <td></td>
 712     <td></td>
 713     <td></td>
 714     <td></td>
 715     <td></td>
 716     <td>&#10008;*</td>
 717     <td>&#10008;*</td>
 718   </tr>
 719   <tr>
 720     <th class="rowhead"><em><a href="#custom">custom lowering</a></em></th>
 721     <td>&#10004;</td>
 722     <th></th>
 723     <th></th>
 724     <th></th>
 725     <th></th>
 726     <th></th>
 727     <th></th>
 728     <th></th>
 729   </tr>
 730   <tr>
 731     <th class="rowhead indent">gcroot</th>
 732     <td>&#10004;</td>
 733     <td>&#10008;</td>
 734     <td>&#10008;</td>
 735     <td></td>
 736     <td></td>
 737     <td></td>
 738     <td></td>
 739     <td></td>
 740   </tr>
 741   <tr>
 742     <th class="rowhead indent">gcwrite</th>
 743     <td>&#10004;</td>
 744     <td></td>
 745     <td>&#10008;</td>
 746     <td></td>
 747     <td></td>
 748     <td>&#10008;</td>
 749     <td></td>
 750     <td>&#10008;</td>
 751   </tr>
 752   <tr>
 753     <th class="rowhead indent">gcread</th>
 754     <td>&#10004;</td>
 755     <td></td>
 756     <td></td>
 757     <td></td>
 758     <td></td>
 759     <td></td>
 760     <td></td>
 761     <td>&#10008;</td>
 762   </tr>
 763   <tr>
 764     <th class="rowhead"><em><a href="#safe-points">safe points</a></em></th>
 765     <td></td>
 766     <th></th>
 767     <th></th>
 768     <th></th>
 769     <th></th>
 770     <th></th>
 771     <th></th>
 772     <th></th>
 773   </tr>
 774   <tr>
 775     <th class="rowhead indent">in calls</th>
 776     <td>&#10004;</td>
 777     <td></td>
 778     <td></td>
 779     <td>&#10008;</td>
 780     <td>&#10008;</td>
 781     <td>&#10008;</td>
 782     <td>&#10008;</td>
 783     <td>&#10008;</td>
 784   </tr>
 785   <tr>
 786     <th class="rowhead indent">before calls</th>
 787     <td>&#10004;</td>
 788     <td></td>
 789     <td></td>
 790     <td></td>
 791     <td></td>
 792     <td></td>
 793     <td>&#10008;</td>
 794     <td>&#10008;</td>
 795   </tr>
 796   <tr class="doc_warning">
 797     <th class="rowhead indent">for loops</th>
 798     <td>NO</td>
 799     <td></td>
 800     <td></td>
 801     <td></td>
 802     <td></td>
 803     <td></td>
 804     <td>&#10008;</td>
 805     <td>&#10008;</td>
 806   </tr>
 807   <tr>
 808     <th class="rowhead indent">before escape</th>
 809     <td>&#10004;</td>
 810     <td></td>
 811     <td></td>
 812     <td></td>
 813     <td></td>
 814     <td></td>
 815     <td>&#10008;</td>
 816     <td>&#10008;</td>
 817   </tr>
 818   <tr class="doc_warning">
 819     <th class="rowhead">emit code at safe points</th>
 820     <td>NO</td>
 821     <td></td>
 822     <td></td>
 823     <td></td>
 824     <td></td>
 825     <td></td>
 826     <td>&#10008;</td>
 827     <td>&#10008;</td>
 828   </tr>
 829   <tr>
 830     <th class="rowhead"><em>output</em></th>
 831     <td></td>
 832     <th></th>
 833     <th></th>
 834     <th></th>
 835     <th></th>
 836     <th></th>
 837     <th></th>
 838     <th></th>
 839   </tr>
 840   <tr>
 841     <th class="rowhead indent"><a href="#assembly">assembly</a></th>
 842     <td>&#10004;</td>
 843     <td></td>
 844     <td></td>
 845     <td>&#10008;</td>
 846     <td>&#10008;</td>
 847     <td>&#10008;</td>
 848     <td>&#10008;</td>
 849     <td>&#10008;</td>
 850   </tr>
 851   <tr class="doc_warning">
 852     <th class="rowhead indent">JIT</th>
 853     <td>NO</td>
 854     <td></td>
 855     <td></td>
 856     <td class="optl">&#10008;</td>
 857     <td class="optl">&#10008;</td>
 858     <td class="optl">&#10008;</td>
 859     <td class="optl">&#10008;</td>
 860     <td class="optl">&#10008;</td>
 861   </tr>
 862   <tr class="doc_warning">
 863     <th class="rowhead indent">obj</th>
 864     <td>NO</td>
 865     <td></td>
 866     <td></td>
 867     <td class="optl">&#10008;</td>
 868     <td class="optl">&#10008;</td>
 869     <td class="optl">&#10008;</td>
 870     <td class="optl">&#10008;</td>
 871     <td class="optl">&#10008;</td>
 872   </tr>
 873   <tr class="doc_warning">
 874     <th class="rowhead">live analysis</th>
 875     <td>NO</td>
 876     <td></td>
 877     <td></td>
 878     <td class="optl">&#10008;</td>
 879     <td class="optl">&#10008;</td>
 880     <td class="optl">&#10008;</td>
 881     <td class="optl">&#10008;</td>
 882     <td class="optl">&#10008;</td>
 883   </tr>
 884   <tr class="doc_warning">
 885     <th class="rowhead">register map</th>
 886     <td>NO</td>
 887     <td></td>
 888     <td></td>
 889     <td class="optl">&#10008;</td>
 890     <td class="optl">&#10008;</td>
 891     <td class="optl">&#10008;</td>
 892     <td class="optl">&#10008;</td>
 893     <td class="optl">&#10008;</td>
 894   </tr>
 895   <tr>
 896     <td colspan="10">
 897       <div><span class="doc_warning">*</span> Derived pointers only pose a
 898            hazard to copying collectors.</div>
 899       <div><span class="optl">&#10008;</span> in gray denotes a feature which
 900            could be utilized if available.</div>
 901     </td>
 902   </tr>
 903 </table>
 904
 905 <p>To be clear, the collection techniques above are defined as:</p>
 906
 907 <dl>
 908   <dt>Shadow Stack</dt>
 909   <dd>The mutator carefully maintains a linked list of stack root
 910       descriptors.</dd>
 911   <dt>Reference Counting</dt>
 912   <dd>The mutator maintains a reference count for each object and frees an
 913       object when its count falls to zero.</dd>
 914   <dt>Mark-Sweep</dt>
 915   <dd>When the heap is exhausted, the collector marks reachable objects starting
 916       from the roots, then deallocates unreachable objects in a sweep
 917       phase.</dd>
 918   <dt>Copying</dt>
 919   <dd>As reachability analysis proceeds, the collector copies objects from one
 920       heap area to another, compacting them in the process. Copying collectors
 921       enable highly efficient "bump pointer" allocation and can improve locality
 922       of reference.</dd>
 923   <dt>Incremental</dt>
 924   <dd>(Including generational collectors.) Incremental collectors generally have
 925       all the properties of a copying collector (regardless of whether the
 926       mature heap is compacting), but bring the added complexity of requiring
 927       write barriers.</dd>
 928   <dt>Threaded</dt>
 929   <dd>Denotes a multithreaded mutator; the collector must still stop the mutator
 930       ("stop the world") before beginning reachability analysis. Stopping a
 931       multithreaded mutator is a complicated problem. It generally requires
 932       highly platform specific code in the runtime, and the production of
 933       carefully designed machine code at safe points.</dd>
 934   <dt>Concurrent</dt>
 935   <dd>In this technique, the mutator and the collector run concurrently, with
 936       the goal of eliminating pause times. In a <em>cooperative</em> collector,
 937       the mutator further aids with collection should a pause occur, allowing
 938       collection to take advantage of multiprocessor hosts. The "stop the world"
 939       problem of threaded collectors is generally still present to a limited
 940       extent. Sophisticated marking algorithms are necessary. Read barriers may
 941       be necessary.</dd>
 942 </dl>
 943
 944 <p>As the matrix indicates, LLVM's garbage collection infrastructure is already
 945 suitable for a wide variety of collectors, but does not currently extend to
 946 multithreaded programs. This will be added in the future as there is
 947 interest.</p>
 948
 949 </div>
 950
 951 <!-- ======================================================================= -->
 952 <div class="doc_subsection">
 953   <a name="stack-map">Computing stack maps</a>
 954 </div>
 955
 956 <div class="doc_text">
 957
 958 <blockquote><pre
 959 >CollectorMetadata &amp;MD = ...;
 960 unsigned FrameSize = MD.getFrameSize();
 961 size_t RootCount = MD.roots_size();
 962
 963 for (CollectorMetadata::roots_iterator RI = MD.roots_begin(),
 964                                        RE = MD.roots_end(); RI != RE; ++RI) {
 965   int RootNum = RI->Num;
 966   int RootStackOffset = RI->StackOffset;
 967   Constant *RootMetadata = RI->Metadata;
 968 }</pre></blockquote>
 969
 970 <p>LLVM automatically computes a stack map. All a <tt>Collector</tt> needs to do
 971 is access it using <tt>CollectorMetadata::roots_begin()</tt> and
 972 -<tt>end()</tt>. If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code
 973 generation by a custom lowering pass, LLVM's stack map will be empty.</p>
 974
 975 </div>
 976
 977
 978 <!-- ======================================================================= -->
 979 <div class="doc_subsection">
 980   <a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a>
 981 </div>
 982
 983 <div class="doc_text">
 984
 985 <blockquote><pre
 986 >MyCollector::MyCollector() {
 987   InitRoots = true;
 988 }</pre></blockquote>
 989
 990 <p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon
 991 entry to the function. This prevents the reachability analysis from finding
 992 uninitialized values in stack roots at runtime, which will almost certainly
 993 cause it to segfault. This initialization occurs before custom lowering, so the
 994 two may be used together.</p>
 995
 996 <p>Since LLVM does not yet compute liveness information, this feature should be
 997 used by all collectors which do not custom lower <tt>llvm.gcroot</tt>, and even
 998 some that do.</p>
 999
1000 </div>
1001
1002
1003 <!-- ======================================================================= -->
1004 <div class="doc_subsection">
1005   <a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>,
1006     <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a>
1007 </div>
1008
1009 <div class="doc_text">
1010
1011 <p>For collectors with barriers or unusual treatment of stack roots, these
1012 flags allow the collector to perform any required transformation on the LLVM
1013 IR:</p>
1014
1015 <blockquote><pre
1016 >class MyCollector : public Collector {
1017 public:
1018   MyCollector() {
1019     CustomRoots = true;
1020     CustomReadBarriers = true;
1021     CustomWriteBarriers = true;
1022   }
1023
1024 protected:
1025   virtual Pass *createCustomLoweringPass() const {
1026     return new MyGCLoweringFunctionPass();
1027   }
1028 };</pre></blockquote>
1029
1030 <p>If any of these flags are set, then LLVM suppresses its default lowering for
1031 the corresponding intrinsics and instead passes them on to a custom lowering
1032 pass specified by the collector.</p>
1033
1034 <p>LLVM's default action for each intrinsic is as follows:</p>
1035
1036 <ul>
1037   <li><tt>llvm.gcroot</tt>: Pass through to the code generator to generate a
1038                             stack map.</li>
1039   <li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li>
1040   <li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li>
1041 </ul>
1042
1043 <p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified,
1044 the custom lowering pass <strong>must</strong> eliminate the corresponding
1045 barriers.</p>
1046
1047 <p>This template can be used as a starting point for a lowering pass:</p>
1048
1049 <blockquote><pre
1050 >#include "llvm/Function.h"
1051 #include "llvm/Module.h"
1052 #include "llvm/Instructions.h"
1053
1054 namespace {
1055   class VISIBILITY_HIDDEN MyGCLoweringFunctionPass : public FunctionPass {
1056     static char ID;
1057   public:
1058     MyGCLoweringFunctionPass() : FunctionPass(intptr_t(&amp;ID)) {}
1059
1060     const char *getPassName() const { return "Lower GC Intrinsics"; }
1061
1062     bool runOnFunction(Function &amp;F) {
1063       Module *M = F.getParent();
1064
1065       Function *GCReadInt  = M-&gt;getFunction("llvm.gcread"),
1066                *GCWriteInt = M-&gt;getFunction("llvm.gcwrite"),
1067                *GCRootInt  = M-&gt;getFunction("llvm.gcroot");
1068
1069       bool MadeChange = false;
1070
1071       for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1072         for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;)
1073           if (CallInst *CI = dyn_cast&lt;CallInst&gt;(II++))
1074             if (Function *F = CI->getCalledFunction())
1075               if (F == GCWriteInt) {
1076                 // Handle llvm.gcwrite.
1077                 CI->eraseFromParent();
1078                 MadeChange = true;
1079               } else if (F == GCReadInt) {
1080                 // Handle llvm.gcread.
1081                 CI->eraseFromParent();
1082                 MadeChange = true;
1083               } else if (F == GCRootInt) {
1084                 // Handle llvm.gcroot.
1085                 CI->eraseFromParent();
1086                 MadeChange = true;
1087               }
1088
1089       return MadeChange;
1090     }
1091   };
1092
1093   char MyGCLoweringFunctionPass::ID = 0;
1094 }</pre></blockquote>
1095
1096 </div>
1097
1098
1099 <!-- ======================================================================= -->
1100 <div class="doc_subsection">
1101   <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a>
1102 </div>
1103
1104 <div class="doc_text">
1105
1106 <p>LLVM can compute four kinds of safe points:</p>
1107
1108 <blockquote><pre
1109 >namespace GC {
1110   /// PointKind - The type of a collector-safe point.
1111   ///
1112   enum PointKind {
1113     Loop,    //&lt; Instr is a loop (backwards branch).
1114     Return,  //&lt; Instr is a return instruction.
1115     PreCall, //&lt; Instr is a call instruction.
1116     PostCall //&lt; Instr is the return address of a call.
1117   };
1118 }</pre></blockquote>
1119
1120 <p>A collector can request any combination of the four by setting the
1121 <tt>NeededSafePoints</tt> mask:</p>
1122
1123 <blockquote><pre
1124 >MyCollector::MyCollector() {
1125   NeededSafePoints = 1 &lt;&lt; GC::Loop
1126                    | 1 &lt;&lt; GC::Return
1127                    | 1 &lt;&lt; GC::PreCall
1128                    | 1 &lt;&lt; GC::PostCall;
1129 }</pre></blockquote>
1130
1131 <p>It can then use the following routines to access safe points.</p>
1132
1133 <blockquote><pre>
1134 CollectorMetadata &amp;MD = ...;
1135 size_t PointCount = MD.size();
1136
1137 for (CollectorMetadata::iterator PI = MD.begin(),
1138                                  PE = MD.end(); PI != PE; ++PI) {
1139   GC::PointKind PointKind = PI-&gt;Kind;
1140   unsigned PointNum = PI-&gt;Num;
1141 }</pre></blockquote>
1142
1143 <p>Almost every collector requires <tt>PostCall</tt> safe points, since these
1144 correspond to the moments when the function is suspended during a call to a
1145 subroutine.</p>
1146
1147 <p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee
1148 that the application will reach a safe point within a bounded amount of time,
1149 even if it is executing a long-running loop which contains no function
1150 calls.</p>
1151
1152 <p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt>
1153 safe points to implement "stop the world" techniques using self-modifying code,
1154 where it is important that the program not exit the function without reaching a
1155 safe point (because only the topmost function has been patched).</p>
1156
1157 </div>
1158
1159
1160 <!-- ======================================================================= -->
1161 <div class="doc_subsection">
1162   <a name="assembly">Emitting assembly code:
1163     <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a>
1164 </div>
1165
1166 <div class="doc_text">
1167
1168 <p>LLVM allows a collector to print arbitrary assembly code before and after
1169 the rest of a module's assembly code. From the latter callback, the collector
1170 can print stack maps from <tt>CollectorModuleMetadata</tt> populated by the code
1171 generator.</p>
1172
1173 <p>Note that LLVM does not currently support garbage collection code generation
1174 in the JIT, nor using the object writers.</p>
1175
1176 <blockquote><pre
1177 >class MyCollector : public Collector {
1178   virtual void beginAssembly(Module &amp;M, std::ostream &amp;OS, AsmPrinter &amp;AP,
1179                              const TargetAsmInfo &amp;TAI) const;
1180
1181   virtual void finishAssembly(Module &amp;M, CollectorModuleMetadata &amp;MMD,
1182                               std::ostream &amp;OS, AsmPrinter &amp;AP,
1183                               const TargetAsmInfo &amp;TAI) const;
1184 }</pre></blockquote>
1185
1186 <p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to
1187 print portable assembly code to the <tt>std::ostream</tt>. The collector may
1188 access the stack maps for the entire module using the methods of
1189 <tt>CollectorModuleMetadata</tt>. Here's a realistic example:</p>
1190
1191 <blockquote><pre
1192 >#include "llvm/CodeGen/AsmPrinter.h"
1193 #include "llvm/Function.h"
1194 #include "llvm/Target/TargetAsmInfo.h"
1195
1196 void MyCollector::finishAssembly(Module &amp;M,
1197                                  CollectorModuleMetadata &amp;MMD,
1198                                  std::ostream &amp;OS, AsmPrinter &amp;AP,
1199                                  const TargetAsmInfo &amp;TAI) const {
1200   // Set up for emitting addresses.
1201   const char *AddressDirective;
1202   int AddressAlignLog;
1203   if (TAI.getAddressSize() == sizeof(int32_t)) {
1204     AddressDirective = TAI.getData32bitsDirective();
1205     AddressAlignLog = 2;
1206   } else {
1207     AddressDirective = TAI.getData64bitsDirective();
1208     AddressAlignLog = 3;
1209   }
1210
1211   // Put this in the data section.
1212   AP.SwitchToDataSection(TAI.getDataSection());
1213
1214   // For each function...
1215   for (CollectorModuleMetadata::iterator FI = MMD.begin(),
1216                                          FE = MMD.end(); FI != FE; ++FI) {
1217     CollectorMetadata &amp;MD = **FI;
1218
1219     // Emit this data structure:
1220     //
1221     // struct {
1222     //   int32_t PointCount;
1223     //   struct {
1224     //     void *SafePointAddress;
1225     //     int32_t LiveCount;
1226     //     int32_t LiveOffsets[LiveCount];
1227     //   } Points[PointCount];
1228     // } __gcmap_&lt;FUNCTIONNAME&gt;;
1229
1230     // Align to address width.
1231     AP.EmitAlignment(AddressAlignLog);
1232
1233     // Emit the symbol by which the stack map can be found.
1234     std::string Symbol;
1235     Symbol += TAI.getGlobalPrefix();
1236     Symbol += "__gcmap_";
1237     Symbol += MD.getFunction().getName();
1238     if (const char *GlobalDirective = TAI.getGlobalDirective())
1239       OS &lt;&lt; GlobalDirective &lt;&lt; Symbol &lt;&lt; "\n";
1240     OS &lt;&lt; TAI.getGlobalPrefix() &lt;&lt; Symbol &lt;&lt; ":\n";
1241
1242     // Emit PointCount.
1243     AP.EmitInt32(MD.size());
1244     AP.EOL("safe point count");
1245
1246     // And each safe point...
1247     for (CollectorMetadata::iterator PI = MD.begin(),
1248                                      PE = MD.end(); PI != PE; ++PI) {
1249       // Align to address width.
1250       AP.EmitAlignment(AddressAlignLog);
1251
1252       // Emit the address of the safe point.
1253       OS &lt;&lt; AddressDirective
1254          &lt;&lt; TAI.getPrivateGlobalPrefix() &lt;&lt; "label" &lt;&lt; PI-&gt;Num;
1255       AP.EOL("safe point address");
1256
1257       // Emit the stack frame size.
1258       AP.EmitInt32(MD.getFrameSize());
1259       AP.EOL("stack frame size");
1260
1261       // Emit the number of live roots in the function.
1262       AP.EmitInt32(MD.live_size(PI));
1263       AP.EOL("live root count");
1264
1265       // And for each live root...
1266       for (CollectorMetadata::live_iterator LI = MD.live_begin(PI),
1267                                             LE = MD.live_end(PI);
1268                                             LI != LE; ++LI) {
1269         // Print its offset within the stack frame.
1270         AP.EmitInt32(LI-&gt;StackOffset);
1271         AP.EOL("stack offset");
1272       }
1273     }
1274   }
1275 }
1276 </pre></blockquote>
1277
1278 </div>
1279
1280
1281 <!-- *********************************************************************** -->
1282 <div class="doc_section">
1283   <a name="runtime-impl">Implementing a collector runtime</a>
1284 </div>
1285 <!-- *********************************************************************** -->
1286
1287 <div class="doc_text">
1288
1289 <p>Implementing a garbage collector for LLVM is fairly straightforward. The
1290 LLVM garbage collectors are provided in a form that makes them easy to link into
1291 the language-specific runtime that a language front-end would use. They require
1292 functionality from the language-specific runtime to get information about <a
1293 href="#gcdescriptors">where pointers are located in heap objects</a>.</p>
1294
1295 <p>The implementation must include the
1296 <a href="#allocate"><tt>llvm_gc_allocate</tt></a> and
1297 <a href="#explicit"><tt>llvm_gc_collect</tt></a> functions. To do this, it will
1298 probably have to <a href="#traceroots">trace through the roots
1299 from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors
1300 for heap objects</a>. Luckily, there are some <a href="#gcimpls">example
1301 implementations</a> available.
1302 </p>
1303 </div>
1304
1305
1306 <!-- ======================================================================= -->
1307 <div class="doc_subsection">
1308   <a name="gcdescriptors">Tracing GC pointers from heap objects</a>
1309 </div>
1310
1311 <div class="doc_text">
1312 <p>
1313 The three most common ways to keep track of where pointers live in heap objects
1314 are (listed in order of space overhead required):</p>
1315
1316 <ol>
1317 <li>In languages with polymorphic objects, pointers from an object header are
1318 usually used to identify the GC pointers in the heap object. This is common for
1319 object-oriented languages like Self, Smalltalk, Java, or C#.</li>
1320
1321 <li>If heap objects are not polymorphic, often the "shape" of the heap can be
1322 determined from the roots of the heap or from some other meta-data [<a
1323 href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a
1324 href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can
1325 propagate the information around from meta data stored with the roots. This
1326 often eliminates the need to have a header on objects in the heap. This is
1327 common in the ML family.</li>
1328
1329 <li>If all heap objects have pointers in the same locations, or pointers can be
1330 distinguished just by looking at them (e.g., the low order bit is clear), no
1331 book-keeping is needed at all. This is common for Lisp-like languages.</li>
1332 </ol>
1333
1334 <p>The LLVM garbage collectors are capable of supporting all of these styles of
1335 language, including ones that mix various implementations. To do this, it
1336 allows the source-language to associate meta-data with the <a
1337 href="#roots">stack roots</a>, and the heap tracing routines can propagate the
1338 information. In addition, LLVM allows the front-end to extract GC information
1339 in any form from a specific object pointer (this supports situations #1 and #3).
1340 </p>
1341
1342 </div>
1343
1344
1345 <!-- *********************************************************************** -->
1346 <div class="doc_section">
1347   <a name="references">References</a>
1348 </div>
1349 <!-- *********************************************************************** -->
1350
1351 <div class="doc_text">
1352
1353 <p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
1354 W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
1355
1356 <p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
1357 strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
1358 PLDI'91.</p>
1359
1360 <p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
1361 explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
1362 conference on LISP and functional programming.</p>
1363
1364 <p><a name="henderson02">[Henderson2002]</a> <a
1365 href="http://citeseer.ist.psu.edu/henderson02accurate.html">
1366 Accurate Garbage Collection in an Uncooperative Environment</a>.
1367 Fergus Henderson. International Symposium on Memory Management 2002.</p>
1368
1369 </div>
1370
1371
1372 <!-- *********************************************************************** -->
1373
1374 <hr>
1375 <address>
1376   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1377   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1378   <a href="http://validator.w3.org/check/referer"><img
1379   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
1380
1381   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1382   <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
1383   Last modified: $Date$
1384 </address>
1385
1386 </body>
1387 </html>