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