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