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>