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="#gcdescriptors">GC descriptor format for heap objects</a></li>
  25     <li><a href="#allocate">Allocating memory from the GC</a></li>
  26     <li><a href="#barriers">Reading and writing references to the heap</a></li>
  27     <li><a href="#explicit">Explicit invocation of the garbage collector</a></li>
  28     </ul>
  29   </li>
  30
  31   <li><a href="#gcimpl">Implementing a garbage collector</a>
  32     <ul>
  33     <li><a href="#llvm_gc_readwrite">Implementing <tt>llvm_gc_read</tt> and <tt>llvm_gc_write</tt></a></li>
  34     <li><a href="#traceroots">Tracing the GC roots from the program stack</a></li>
  35     <li><a href="#gcimpls">GC implementations available</a></li>
  36     </ul>
  37   </li>
  38
  39 <!--
  40   <li><a href="#codegen">Implementing GC support in a code generator</a></li>
  41 -->
  42 </ol>
  43
  44 <div class="doc_author">
  45   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
  46 </div>
  47
  48 <!-- *********************************************************************** -->
  49 <div class="doc_section">
  50   <a name="introduction">Introduction</a>
  51 </div>
  52 <!-- *********************************************************************** -->
  53
  54 <div class="doc_text">
  55
  56 <p>Garbage collection is a widely used technique that frees the programmer from
  57 having to know the life-times of heap objects, making software easier to produce
  58 and maintain.  Many programming languages rely on garbage collection for
  59 automatic memory management.  There are two primary forms of garbage collection:
  60 conservative and accurate.</p>
  61
  62 <p>Conservative garbage collection often does not require any special support
  63 from either the language or the compiler: it can handle non-type-safe
  64 programming languages (such as C/C++) and does not require any special
  65 information from the compiler.  The [LINK] Boehm collector is an example of a
  66 state-of-the-art conservative collector.</p>
  67
  68 <p>Accurate garbage collection requires the ability to identify all pointers in
  69 the program at run-time (which requires that the source-language be type-safe in
  70 most cases).  Identifying pointers at run-time requires compiler support to
  71 locate all places that hold live pointer variables at run-time, including the
  72 <a href="#roots">processor stack and registers</a>.</p>
  73
  74 <p>
  75 Conservative garbage collection is attractive because it does not require any
  76 special compiler support, but it does have problems.  In particular, because the
  77 conservative garbage collector cannot <i>know</i> that a particular word in the
  78 machine is a pointer, it cannot move live objects in the heap (preventing the
  79 use of compacting and generational GC algorithms) and it can occasionally suffer
  80 from memory leaks due to integer values that happen to point to objects in the
  81 program.  In addition, some aggressive compiler transformations can break
  82 conservative garbage collectors (though these seem rare in practice).
  83 </p>
  84
  85 <p>
  86 Accurate garbage collectors do not suffer from any of these problems, but they
  87 can suffer from degraded scalar optimization of the program.  In particular,
  88 because the runtime must be able to identify and update all pointers active in
  89 the program, some optimizations are less effective.  In practice, however, the
  90 locality and performance benefits of using aggressive garbage allocation
  91 techniques dominates any low-level losses.
  92 </p>
  93
  94 <p>
  95 This document describes the mechanisms and interfaces provided by LLVM to
  96 support accurate garbage collection.
  97 </p>
  98
  99 </div>
 100
 101 <!-- ======================================================================= -->
 102 <div class="doc_subsection">
 103   <a name="feature">GC features provided and algorithms supported</a>
 104 </div>
 105
 106 <div class="doc_text">
 107
 108 <p>
 109 LLVM provides support for a broad class of garbage collection algorithms,
 110 including compacting semi-space collectors, mark-sweep collectors, generational
 111 collectors, and even reference counting implementations.  It includes support
 112 for <a href="#barriers">read and write barriers</a>, and associating <a
 113 href="#roots">meta-data with stack objects</a> (used for tagless garbage
 114 collection).  All LLVM code generators support garbage collection, including the
 115 C backend.
 116 </p>
 117
 118 <p>
 119 We hope that the primitive support built into LLVM is sufficient to support a
 120 broad class of garbage collected languages, including Scheme, ML, scripting
 121 languages, Java, C#, etc.  That said, the implemented garbage collectors may
 122 need to be extended to support language-specific features such as finalization,
 123 weak references, or other features.  As these needs are identified and
 124 implemented, they should be added to this specification.
 125 </p>
 126
 127 <p>
 128 LLVM does not currently support garbage collection of multi-threaded programs or
 129 GC-safe points other than function calls, but these will be added in the future
 130 as there is interest.
 131 </p>
 132
 133 </div>
 134
 135 <!-- *********************************************************************** -->
 136 <div class="doc_section">
 137   <a name="interfaces">Interfaces for user programs</a>
 138 </div>
 139 <!-- *********************************************************************** -->
 140
 141 <div class="doc_text">
 142
 143 <p>This section describes the interfaces provided by LLVM and by the garbage
 144 collector run-time that should be used by user programs.  As such, this is the
 145 interface that front-end authors should generate code for.
 146 </p>
 147
 148 </div>
 149
 150 <!-- ======================================================================= -->
 151 <div class="doc_subsection">
 152   <a name="roots">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a>
 153 </div>
 154
 155 <div class="doc_text">
 156
 157 <div class="doc_code"><tt>
 158   void %llvm.gcroot(&lt;ty&gt;** %ptrloc, &lt;ty2&gt;* %metadata)
 159 </tt></div>
 160
 161 <p>
 162 The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer variable
 163 on the stack.  The first argument contains the address of the variable on the
 164 stack, and the second contains a pointer to metadata that should be associated
 165 with the pointer (which <b>must</b> be a constant or global value address).  At
 166 runtime, the <tt>llvm.gcroot</tt> intrinsic stores a null pointer into the
 167 specified location to initialize the pointer.</p>
 168
 169 <p>
 170 Consider the following fragment of Java code:
 171 </p>
 172
 173 <pre>
 174        {
 175          Object X;   // A null-initialized reference to an object
 176          ...
 177        }
 178 </pre>
 179
 180 <p>
 181 This block (which may be located in the middle of a function or in a loop nest),
 182 could be compiled to this LLVM code:
 183 </p>
 184
 185 <pre>
 186 Entry:
 187    ;; In the entry block for the function, allocate the
 188    ;; stack space for X, which is an LLVM pointer.
 189    %X = alloca %Object*
 190    ...
 191
 192    ;; "CodeBlock" is the block corresponding to the start
 193    ;;  of the scope scope above.
 194 CodeBlock:
 195    ;; Initialize the object, telling LLVM that it is now live.
 196    ;; Java has type-tags on objects, so it doesn't need any
 197    ;; metadata.
 198    call void %llvm.gcroot(%Object** %X, sbyte* null)
 199    ...
 200
 201    ;; As the pointer goes out of scope, store a null value into
 202    ;; it, to indicate that the value is no longer live.
 203    store %Object* null, %Object** %X
 204    ...
 205 </pre>
 206
 207 </div>
 208
 209 <!-- ======================================================================= -->
 210 <div class="doc_subsection">
 211   <a name="gcdescriptors">GC descriptor format for heap objects</a>
 212 </div>
 213
 214 <div class="doc_text">
 215
 216 <p>
 217 TODO: Either from root meta data, or from object headers.  Front-end can provide a
 218 call-back to get descriptor from object without meta-data.
 219 </p>
 220
 221 </div>
 222
 223 <!-- ======================================================================= -->
 224 <div class="doc_subsection">
 225   <a name="allocate">Allocating memory from the GC</a>
 226 </div>
 227
 228 <div class="doc_text">
 229
 230 <div class="doc_code"><tt>
 231   sbyte *%llvm_gc_allocate(unsigned %Size)
 232 </tt></div>
 233
 234 <p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the
 235 garbage collector implementation to allocate memory.  It should return a
 236 zeroed-out block of memory of the appropriate size.</p>
 237
 238 </div>
 239
 240 <!-- ======================================================================= -->
 241 <div class="doc_subsection">
 242   <a name="barriers">Reading and writing references to the heap</a>
 243 </div>
 244
 245 <div class="doc_text">
 246
 247 <div class="doc_code"><tt>
 248   sbyte *%llvm.gcread(sbyte **)<br>
 249   void %llvm.gcwrite(sbyte*, sbyte**)
 250 </tt></div>
 251
 252 <p>Several of the more interesting garbage collectors (e.g., generational
 253 collectors) need to be informed when the mutator (the program that needs garbage
 254 collection) reads or writes object references into the heap.  In the case of a
 255 generational collector, it needs to keep track of which "old" generation objects
 256 have references stored into them.  The amount of code that typically needs to be
 257 executed is usually quite small, so the overall performance impact of the
 258 inserted code is tolerable.</p>
 259
 260 <p>To support garbage collectors that use read or write barriers, LLVM provides
 261 the <tt>llvm.gcread</tt> and <tt>llvm.gcwrite</tt> intrinsics.  The first
 262 intrinsic has exactly the same semantics as a non-volatile LLVM load and the
 263 second has the same semantics as a non-volatile LLVM store.  At code generation
 264 time, these intrinsics are replaced with calls into the garbage collector
 265 (<tt><a href="#llvm_gc_readwrite">llvm_gc_read</a></tt> and <tt><a
 266 href="#llvm_gc_readwrite">llvm_gc_write</a></tt> respectively), which are then
 267 inlined into the code.
 268 </p>
 269
 270 <p>
 271 If you are writing a front-end for a garbage collected language, every load or
 272 store of a reference from or to the heap should use these intrinsics instead of
 273 normal LLVM loads/stores.</p>
 274
 275 </div>
 276
 277 <!-- ======================================================================= -->
 278 <div class="doc_subsection">
 279   <a name="initialize">Garbage collector startup and initialization</a>
 280 </div>
 281
 282 <div class="doc_text">
 283
 284 <div class="doc_code"><tt>
 285   void %llvm_gc_initialize()
 286 </tt></div>
 287
 288 <p>
 289 The <tt>llvm_gc_initialize</tt> function should be called once before any other
 290 garbage collection functions are called.  This gives the garbage collector the
 291 chance to initialize itself and allocate the heap spaces.
 292 </p>
 293
 294 </div>
 295
 296 <!-- ======================================================================= -->
 297 <div class="doc_subsection">
 298   <a name="explicit">Explicit invocation of the garbage collector</a>
 299 </div>
 300
 301 <div class="doc_text">
 302
 303 <div class="doc_code"><tt>
 304   void %llvm_gc_collect()
 305 </tt></div>
 306
 307 <p>
 308 The <tt>llvm_gc_collect</tt> function is exported by the garbage collector
 309 implementations to provide a full collection, even when the heap is not
 310 exhausted.  This can be used by end-user code as a hint, and may be ignored by
 311 the garbage collector.
 312 </p>
 313
 314 </div>
 315
 316
 317 <!-- *********************************************************************** -->
 318 <div class="doc_section">
 319   <a name="gcimpl">Implementing a garbage collector</a>
 320 </div>
 321 <!-- *********************************************************************** -->
 322
 323 <div class="doc_text">
 324
 325 <p>
 326 Implementing a garbage collector for LLVM is fairly straight-forward.  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 **)<br>
 347     void llvm_gc_write(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.  Note that we may add a pointer to the start of the memory object
 359 as a parameter in the future, if needed.
 360 </p>
 361
 362 </div>
 363
 364 <!-- ======================================================================= -->
 365 <div class="doc_subsection">
 366   <a name="traceroots">Tracing the GC roots from the program stack</a>
 367 </div>
 368
 369 <div class="doc_text">
 370   <div class="doc_code"><tt>
 371      void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
 372   </tt></div>
 373
 374 <p>
 375 The <tt>llvm_cg_walk_gcroots</tt> function is a function provided by the code
 376 generator that iterates through all of the GC roots on the stack, calling the
 377 specified function pointer with each record.  For each GC root, the address of
 378 the pointer and the meta-data (from the <a
 379 href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
 380 </p>
 381 </div>
 382
 383
 384 <!-- ======================================================================= -->
 385 <div class="doc_subsection">
 386   <a name="gcimpls">GC implementations available</a>
 387 </div>
 388
 389 <div class="doc_text">
 390
 391 <p>
 392 To make this more concrete, the currently implemented LLVM garbage collectors
 393 all live in the llvm/runtime/GC directory in the LLVM source-base.
 394 </p>
 395
 396 <p>
 397 TODO: Brief overview of each.
 398 </p>
 399
 400 </div>
 401
 402
 403 <!-- *********************************************************************** -->
 404
 405 <hr>
 406 <address>
 407   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 408   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 409   <a href="http://validator.w3.org/check/referer"><img
 410   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
 411
 412   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
 413   <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br>
 414   Last modified: $Date$
 415 </address>
 416
 417 </body>
 418 </html>