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