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<h1> 17 Accurate Garbage Collection with LLVM 18</h1> 19 20<ol> 21 <li><a href="#introduction">Introduction</a> 22 <ul> 23 <li><a href="#feature">Goals and non-goals</a></li> 24 </ul> 25 </li> 26 27 <li><a href="#quickstart">Getting started</a> 28 <ul> 29 <li><a href="#quickstart-compiler">In your compiler</a></li> 30 <li><a href="#quickstart-runtime">In your runtime library</a></li> 31 <li><a href="#shadow-stack">About the shadow stack</a></li> 32 </ul> 33 </li> 34 35 <li><a href="#core">Core support</a> 36 <ul> 37 <li><a href="#gcattr">Specifying GC code generation: 38 <tt>gc "..."</tt></a></li> 39 <li><a href="#gcroot">Identifying GC roots on the stack: 40 <tt>llvm.gcroot</tt></a></li> 41 <li><a href="#barriers">Reading and writing references in the heap</a> 42 <ul> 43 <li><a href="#gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a></li> 44 <li><a href="#gcread">Read barrier: <tt>llvm.gcread</tt></a></li> 45 </ul> 46 </li> 47 </ul> 48 </li> 49 50 <li><a href="#plugin">Compiler plugin interface</a> 51 <ul> 52 <li><a href="#collector-algos">Overview of available features</a></li> 53 <li><a href="#stack-map">Computing stack maps</a></li> 54 <li><a href="#init-roots">Initializing roots to null: 55 <tt>InitRoots</tt></a></li> 56 <li><a href="#custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, 57 <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a></li> 58 <li><a href="#safe-points">Generating safe points: 59 <tt>NeededSafePoints</tt></a></li> 60 <li><a href="#assembly">Emitting assembly code: 61 <tt>GCMetadataPrinter</tt></a></li> 62 </ul> 63 </li> 64 65 <li><a href="#runtime-impl">Implementing a collector runtime</a> 66 <ul> 67 <li><a href="#gcdescriptors">Tracing GC pointers from heap 68 objects</a></li> 69 </ul> 70 </li> 71 72 <li><a href="#references">References</a></li> 73 74</ol> 75 76<div class="doc_author"> 77 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and 78 Gordon Henriksen</p> 79</div> 80 81<!-- *********************************************************************** --> 82<h2> 83 <a name="introduction">Introduction</a> 84</h2> 85<!-- *********************************************************************** --> 86 87<div> 88 89<p>Garbage collection is a widely used technique that frees the programmer from 90having to know the lifetimes of heap objects, making software easier to produce 91and maintain. Many programming languages rely on garbage collection for 92automatic memory management. There are two primary forms of garbage collection: 93conservative and accurate.</p> 94 95<p>Conservative garbage collection often does not require any special support 96from either the language or the compiler: it can handle non-type-safe 97programming languages (such as C/C++) and does not require any special 98information from the compiler. The 99<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is 100an example of a state-of-the-art conservative collector.</p> 101 102<p>Accurate garbage collection requires the ability to identify all pointers in 103the program at run-time (which requires that the source-language be type-safe in 104most cases). Identifying pointers at run-time requires compiler support to 105locate all places that hold live pointer variables at run-time, including the 106<a href="#gcroot">processor stack and registers</a>.</p> 107 108<p>Conservative garbage collection is attractive because it does not require any 109special compiler support, but it does have problems. In particular, because the 110conservative garbage collector cannot <i>know</i> that a particular word in the 111machine is a pointer, it cannot move live objects in the heap (preventing the 112use of compacting and generational GC algorithms) and it can occasionally suffer 113from memory leaks due to integer values that happen to point to objects in the 114program. In addition, some aggressive compiler transformations can break 115conservative garbage collectors (though these seem rare in practice).</p> 116 117<p>Accurate garbage collectors do not suffer from any of these problems, but 118they can suffer from degraded scalar optimization of the program. In particular, 119because the runtime must be able to identify and update all pointers active in 120the program, some optimizations are less effective. In practice, however, the 121locality and performance benefits of using aggressive garbage collection 122techniques dominates any low-level losses.</p> 123 124<p>This document describes the mechanisms and interfaces provided by LLVM to 125support accurate garbage collection.</p> 126 127<!-- ======================================================================= --> 128<h3> 129 <a name="feature">Goals and non-goals</a> 130</h3> 131 132<div> 133 134<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage 135collection intrinsics</a> that offer support for a broad class of 136collector models. For instance, the intrinsics permit:</p> 137 138<ul> 139 <li>semi-space collectors</li> 140 <li>mark-sweep collectors</li> 141 <li>generational collectors</li> 142 <li>reference counting</li> 143 <li>incremental collectors</li> 144 <li>concurrent collectors</li> 145 <li>cooperative collectors</li> 146</ul> 147 148<p>We hope that the primitive support built into the LLVM IR is sufficient to 149support a broad class of garbage collected languages including Scheme, ML, Java, 150C#, Perl, Python, Lua, Ruby, other scripting languages, and more.</p> 151 152<p>However, LLVM does not itself provide a garbage collector—this should 153be part of your language's runtime library. LLVM provides a framework for 154compile time <a href="#plugin">code generation plugins</a>. The role of these 155plugins is to generate code and data structures which conforms to the <em>binary 156interface</em> specified by the <em>runtime library</em>. This is similar to the 157relationship between LLVM and DWARF debugging info, for example. The 158difference primarily lies in the lack of an established standard in the domain 159of garbage collection—thus the plugins.</p> 160 161<p>The aspects of the binary interface with which LLVM's GC support is 162concerned are:</p> 163 164<ul> 165 <li>Creation of GC-safe points within code where collection is allowed to 166 execute safely.</li> 167 <li>Computation of the stack map. For each safe point in the code, object 168 references within the stack frame must be identified so that the 169 collector may traverse and perhaps update them.</li> 170 <li>Write barriers when storing object references to the heap. These are 171 commonly used to optimize incremental scans in generational 172 collectors.</li> 173 <li>Emission of read barriers when loading object references. These are 174 useful for interoperating with concurrent collectors.</li> 175</ul> 176 177<p>There are additional areas that LLVM does not directly address:</p> 178 179<ul> 180 <li>Registration of global roots with the runtime.</li> 181 <li>Registration of stack map entries with the runtime.</li> 182 <li>The functions used by the program to allocate memory, trigger a 183 collection, etc.</li> 184 <li>Computation or compilation of type maps, or registration of them with 185 the runtime. These are used to crawl the heap for object 186 references.</li> 187</ul> 188 189<p>In general, LLVM's support for GC does not include features which can be 190adequately addressed with other features of the IR and does not specify a 191particular binary interface. On the plus side, this means that you should be 192able to integrate LLVM with an existing runtime. On the other hand, it leaves 193a lot of work for the developer of a novel language. However, it's easy to get 194started quickly and scale up to a more sophisticated implementation as your 195compiler matures.</p> 196 197</div> 198 199</div> 200 201<!-- *********************************************************************** --> 202<h2> 203 <a name="quickstart">Getting started</a> 204</h2> 205<!-- *********************************************************************** --> 206 207<div> 208 209<p>Using a GC with LLVM implies many things, for example:</p> 210 211<ul> 212 <li>Write a runtime library or find an existing one which implements a GC 213 heap.<ol> 214 <li>Implement a memory allocator.</li> 215 <li>Design a binary interface for the stack map, used to identify 216 references within a stack frame on the machine stack.*</li> 217 <li>Implement a stack crawler to discover functions on the call stack.*</li> 218 <li>Implement a registry for global roots.</li> 219 <li>Design a binary interface for type maps, used to identify references 220 within heap objects.</li> 221 <li>Implement a collection routine bringing together all of the above.</li> 222 </ol></li> 223 <li>Emit compatible code from your compiler.<ul> 224 <li>Initialization in the main function.</li> 225 <li>Use the <tt>gc "..."</tt> attribute to enable GC code generation 226 (or <tt>F.setGC("...")</tt>).</li> 227 <li>Use <tt>@llvm.gcroot</tt> to mark stack roots.</li> 228 <li>Use <tt>@llvm.gcread</tt> and/or <tt>@llvm.gcwrite</tt> to 229 manipulate GC references, if necessary.</li> 230 <li>Allocate memory using the GC allocation routine provided by the 231 runtime library.</li> 232 <li>Generate type maps according to your runtime's binary interface.</li> 233 </ul></li> 234 <li>Write a compiler plugin to interface LLVM with the runtime library.*<ul> 235 <li>Lower <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> to appropriate 236 code sequences.*</li> 237 <li>Compile LLVM's stack map to the binary form expected by the 238 runtime.</li> 239 </ul></li> 240 <li>Load the plugin into the compiler. Use <tt>llc -load</tt> or link the 241 plugin statically with your language's compiler.*</li> 242 <li>Link program executables with the runtime.</li> 243</ul> 244 245<p>To help with several of these tasks (those indicated with a *), LLVM 246includes a highly portable, built-in ShadowStack code generator. It is compiled 247into <tt>llc</tt> and works even with the interpreter and C backends.</p> 248 249<!-- ======================================================================= --> 250<h3> 251 <a name="quickstart-compiler">In your compiler</a> 252</h3> 253 254<div> 255 256<p>To turn the shadow stack on for your functions, first call:</p> 257 258<div class="doc_code"><pre 259>F.setGC("shadow-stack");</pre></div> 260 261<p>for each function your compiler emits. Since the shadow stack is built into 262LLVM, you do not need to load a plugin.</p> 263 264<p>Your compiler must also use <tt>@llvm.gcroot</tt> as documented. 265Don't forget to create a root for each intermediate value that is generated 266when evaluating an expression. In <tt>h(f(), g())</tt>, the result of 267<tt>f()</tt> could easily be collected if evaluating <tt>g()</tt> triggers a 268collection.</p> 269 270<p>There's no need to use <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> over 271plain <tt>load</tt> and <tt>store</tt> for now. You will need them when 272switching to a more advanced GC.</p> 273 274</div> 275 276<!-- ======================================================================= --> 277<h3> 278 <a name="quickstart-runtime">In your runtime</a> 279</h3> 280 281<div> 282 283<p>The shadow stack doesn't imply a memory allocation algorithm. A semispace 284collector or building atop <tt>malloc</tt> are great places to start, and can 285be implemented with very little code.</p> 286 287<p>When it comes time to collect, however, your runtime needs to traverse the 288stack roots, and for this it needs to integrate with the shadow stack. Luckily, 289doing so is very simple. (This code is heavily commented to help you 290understand the data structure, but there are only 20 lines of meaningful 291code.)</p> 292 293<pre class="doc_code"> 294/// @brief The map for a single function's stack frame. One of these is 295/// compiled as constant data into the executable for each function. 296/// 297/// Storage of metadata values is elided if the %metadata parameter to 298/// @llvm.gcroot is null. 299struct FrameMap { 300 int32_t NumRoots; //< Number of roots in stack frame. 301 int32_t NumMeta; //< Number of metadata entries. May be < NumRoots. 302 const void *Meta[0]; //< Metadata for each root. 303}; 304 305/// @brief A link in the dynamic shadow stack. One of these is embedded in the 306/// stack frame of each function on the call stack. 307struct StackEntry { 308 StackEntry *Next; //< Link to next stack entry (the caller's). 309 const FrameMap *Map; //< Pointer to constant FrameMap. 310 void *Roots[0]; //< Stack roots (in-place array). 311}; 312 313/// @brief The head of the singly-linked list of StackEntries. Functions push 314/// and pop onto this in their prologue and epilogue. 315/// 316/// Since there is only a global list, this technique is not threadsafe. 317StackEntry *llvm_gc_root_chain; 318 319/// @brief Calls Visitor(root, meta) for each GC root on the stack. 320/// root and meta are exactly the values passed to 321/// <tt>@llvm.gcroot</tt>. 322/// 323/// Visitor could be a function to recursively mark live objects. Or it 324/// might copy them to another heap or generation. 325/// 326/// @param Visitor A function to invoke for every GC root on the stack. 327void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) { 328 for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) { 329 unsigned i = 0; 330 331 // For roots [0, NumMeta), the metadata pointer is in the FrameMap. 332 for (unsigned e = R->Map->NumMeta; i != e; ++i) 333 Visitor(&R->Roots[i], R->Map->Meta[i]); 334 335 // For roots [NumMeta, NumRoots), the metadata pointer is null. 336 for (unsigned e = R->Map->NumRoots; i != e; ++i) 337 Visitor(&R->Roots[i], NULL); 338 } 339}</pre> 340 341</div> 342 343<!-- ======================================================================= --> 344<h3> 345 <a name="shadow-stack">About the shadow stack</a> 346</h3> 347 348<div> 349 350<p>Unlike many GC algorithms which rely on a cooperative code generator to 351compile stack maps, this algorithm carefully maintains a linked list of stack 352roots [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow stack" 353mirrors the machine stack. Maintaining this data structure is slower than using 354a stack map compiled into the executable as constant data, but has a significant 355portability advantage because it requires no special support from the target 356code generator, and does not require tricky platform-specific code to crawl 357the machine stack.</p> 358 359<p>The tradeoff for this simplicity and portability is:</p> 360 361<ul> 362 <li>High overhead per function call.</li> 363 <li>Not thread-safe.</li> 364</ul> 365 366<p>Still, it's an easy way to get started. After your compiler and runtime are 367up and running, writing a <a href="#plugin">plugin</a> will allow you to take 368advantage of <a href="#collector-algos">more advanced GC features</a> of LLVM 369in order to improve performance.</p> 370 371</div> 372 373</div> 374 375<!-- *********************************************************************** --> 376<h2> 377 <a name="core">IR features</a><a name="intrinsics"></a> 378</h2> 379<!-- *********************************************************************** --> 380 381<div> 382 383<p>This section describes the garbage collection facilities provided by the 384<a href="LangRef.html">LLVM intermediate representation</a>. The exact behavior 385of these IR features is specified by the binary interface implemented by a 386<a href="#plugin">code generation plugin</a>, not by this document.</p> 387 388<p>These facilities are limited to those strictly necessary; they are not 389intended to be a complete interface to any garbage collector. A program will 390need to interface with the GC library using the facilities provided by that 391program.</p> 392 393<!-- ======================================================================= --> 394<h3> 395 <a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a> 396</h3> 397 398<div> 399 400<div class="doc_code"><tt> 401 define <i>ty</i> @<i>name</i>(...) <span style="text-decoration: underline">gc "<i>name</i>"</span> { ... 402</tt></div> 403 404<p>The <tt>gc</tt> function attribute is used to specify the desired GC style 405to the compiler. Its programmatic equivalent is the <tt>setGC</tt> method of 406<tt>Function</tt>.</p> 407 408<p>Setting <tt>gc "<i>name</i>"</tt> on a function triggers a search for a 409matching code generation plugin "<i>name</i>"; it is that plugin which defines 410the exact nature of the code generated to support GC. If none is found, the 411compiler will raise an error.</p> 412 413<p>Specifying the GC style on a per-function basis allows LLVM to link together 414programs that use different garbage collection algorithms (or none at all).</p> 415 416</div> 417 418<!-- ======================================================================= --> 419<h3> 420 <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a> 421</h3> 422 423<div> 424 425<div class="doc_code"><tt> 426 void @llvm.gcroot(i8** %ptrloc, i8* %metadata) 427</tt></div> 428 429<p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM that a stack 430variable references an object on the heap and is to be tracked for garbage 431collection. The exact impact on generated code is specified by a <a 432href="#plugin">compiler plugin</a>.</p> 433 434<p>A compiler which uses mem2reg to raise imperative code using <tt>alloca</tt> 435into SSA form need only add a call to <tt>@llvm.gcroot</tt> for those variables 436which a pointers into the GC heap.</p> 437 438<p>It is also important to mark intermediate values with <tt>llvm.gcroot</tt>. 439For example, consider <tt>h(f(), g())</tt>. Beware leaking the result of 440<tt>f()</tt> in the case that <tt>g()</tt> triggers a collection.</p> 441 442<p>The first argument <b>must</b> be a value referring to an alloca instruction 443or a bitcast of an alloca. The second contains a pointer to metadata that 444should be associated with the pointer, and <b>must</b> be a constant or global 445value address. If your target collector uses tags, use a null pointer for 446metadata.</p> 447 448<p>The <tt>%metadata</tt> argument can be used to avoid requiring heap objects 449to have 'isa' pointers or tag bits. [<a href="#appel89">Appel89</a>, <a 450href="#goldberg91">Goldberg91</a>, <a href="#tolmach94">Tolmach94</a>] If 451specified, its value will be tracked along with the location of the pointer in 452the stack frame.</p> 453 454<p>Consider the following fragment of Java code:</p> 455 456<pre class="doc_code"> 457 { 458 Object X; // A null-initialized reference to an object 459 ... 460 } 461</pre> 462 463<p>This block (which may be located in the middle of a function or in a loop 464nest), could be compiled to this LLVM code:</p> 465 466<pre class="doc_code"> 467Entry: 468 ;; In the entry block for the function, allocate the 469 ;; stack space for X, which is an LLVM pointer. 470 %X = alloca %Object* 471 472 ;; Tell LLVM that the stack space is a stack root. 473 ;; Java has type-tags on objects, so we pass null as metadata. 474 %tmp = bitcast %Object** %X to i8** 475 call void @llvm.gcroot(i8** %X, i8* null) 476 ... 477 478 ;; "CodeBlock" is the block corresponding to the start 479 ;; of the scope above. 480CodeBlock: 481 ;; Java null-initializes pointers. 482 store %Object* null, %Object** %X 483 484 ... 485 486 ;; As the pointer goes out of scope, store a null value into 487 ;; it, to indicate that the value is no longer live. 488 store %Object* null, %Object** %X 489 ... 490</pre> 491 492</div> 493 494<!-- ======================================================================= --> 495<h3> 496 <a name="barriers">Reading and writing references in the heap</a> 497</h3> 498 499<div> 500 501<p>Some collectors need to be informed when the mutator (the program that needs 502garbage collection) either reads a pointer from or writes a pointer to a field 503of a heap object. The code fragments inserted at these points are called 504<em>read barriers</em> and <em>write barriers</em>, respectively. The amount of 505code that needs to be executed is usually quite small and not on the critical 506path of any computation, so the overall performance impact of the barrier is 507tolerable.</p> 508 509<p>Barriers often require access to the <em>object pointer</em> rather than the 510<em>derived pointer</em> (which is a pointer to the field within the 511object). Accordingly, these intrinsics take both pointers as separate arguments 512for completeness. In this snippet, <tt>%object</tt> is the object pointer, and 513<tt>%derived</tt> is the derived pointer:</p> 514 515<blockquote><pre> 516 ;; An array type. 517 %class.Array = type { %class.Object, i32, [0 x %class.Object*] } 518 ... 519 520 ;; Load the object pointer from a gcroot. 521 %object = load %class.Array** %object_addr 522 523 ;; Compute the derived pointer. 524 %derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote> 525 526<p>LLVM does not enforce this relationship between the object and derived 527pointer (although a <a href="#plugin">plugin</a> might). However, it would be 528an unusual collector that violated it.</p> 529 530<p>The use of these intrinsics is naturally optional if the target GC does 531require the corresponding barrier. Such a GC plugin will replace the intrinsic 532calls with the corresponding <tt>load</tt> or <tt>store</tt> instruction if they 533are used.</p> 534 535<!-- ======================================================================= --> 536<h4> 537 <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a> 538</h4> 539 540<div> 541 542<div class="doc_code"><tt> 543void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived) 544</tt></div> 545 546<p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic 547function. It has exactly the same semantics as a non-volatile <tt>store</tt> to 548the derived pointer (the third argument). The exact code generated is specified 549by a <a href="#plugin">compiler plugin</a>.</p> 550 551<p>Many important algorithms require write barriers, including generational 552and concurrent collectors. Additionally, write barriers could be used to 553implement reference counting.</p> 554 555</div> 556 557<!-- ======================================================================= --> 558<h4> 559 <a name="gcread">Read barrier: <tt>llvm.gcread</tt></a> 560</h4> 561 562<div> 563 564<div class="doc_code"><tt> 565i8* @llvm.gcread(i8* %object, i8** %derived)<br> 566</tt></div> 567 568<p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function. 569It has exactly the same semantics as a non-volatile <tt>load</tt> from the 570derived pointer (the second argument). The exact code generated is specified by 571a <a href="#plugin">compiler plugin</a>.</p> 572 573<p>Read barriers are needed by fewer algorithms than write barriers, and may 574have a greater performance impact since pointer reads are more frequent than 575writes.</p> 576 577</div> 578 579</div> 580 581</div> 582 583<!-- *********************************************************************** --> 584<h2> 585 <a name="plugin">Implementing a collector plugin</a> 586</h2> 587<!-- *********************************************************************** --> 588 589<div> 590 591<p>User code specifies which GC code generation to use with the <tt>gc</tt> 592function attribute or, equivalently, with the <tt>setGC</tt> method of 593<tt>Function</tt>.</p> 594 595<p>To implement a GC plugin, it is necessary to subclass 596<tt>llvm::GCStrategy</tt>, which can be accomplished in a few lines of 597boilerplate code. LLVM's infrastructure provides access to several important 598algorithms. For an uncontroversial collector, all that remains may be to 599compile LLVM's computed stack map to assembly code (using the binary 600representation expected by the runtime library). This can be accomplished in 601about 100 lines of code.</p> 602 603<p>This is not the appropriate place to implement a garbage collected heap or a 604garbage collector itself. That code should exist in the language's runtime 605library. The compiler plugin is responsible for generating code which 606conforms to the binary interface defined by library, most essentially the 607<a href="#stack-map">stack map</a>.</p> 608 609<p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p> 610 611<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM GC plugin 612 613#include "llvm/CodeGen/GCStrategy.h" 614#include "llvm/CodeGen/GCMetadata.h" 615#include "llvm/Support/Compiler.h" 616 617using namespace llvm; 618 619namespace { 620 class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy { 621 public: 622 MyGC() {} 623 }; 624 625 GCRegistry::Add<MyGC> 626 X("mygc", "My bespoke garbage collector."); 627}</pre></blockquote> 628 629<p>This boilerplate collector does nothing. More specifically:</p> 630 631<ul> 632 <li><tt>llvm.gcread</tt> calls are replaced with the corresponding 633 <tt>load</tt> instruction.</li> 634 <li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding 635 <tt>store</tt> instruction.</li> 636 <li>No safe points are added to the code.</li> 637 <li>The stack map is not compiled into the executable.</li> 638</ul> 639 640<p>Using the LLVM makefiles (like the <a 641href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample 642project</a>), this code can be compiled as a plugin using a simple 643makefile:</p> 644 645<blockquote><pre 646># lib/MyGC/Makefile 647 648LEVEL := ../.. 649LIBRARYNAME = <var>MyGC</var> 650LOADABLE_MODULE = 1 651 652include $(LEVEL)/Makefile.common</pre></blockquote> 653 654<p>Once the plugin is compiled, code using it may be compiled using <tt>llc 655-load=<var>MyGC.so</var></tt> (though <var>MyGC.so</var> may have some other 656platform-specific extension):</p> 657 658<blockquote><pre 659>$ cat sample.ll 660define void @f() gc "mygc" { 661entry: 662 ret void 663} 664$ llvm-as < sample.ll | llc -load=MyGC.so</pre></blockquote> 665 666<p>It is also possible to statically link the collector plugin into tools, such 667as a language-specific compiler front-end.</p> 668 669<!-- ======================================================================= --> 670<h3> 671 <a name="collector-algos">Overview of available features</a> 672</h3> 673 674<div> 675 676<p><tt>GCStrategy</tt> provides a range of features through which a plugin 677may do useful work. Some of these are callbacks, some are algorithms that can 678be enabled, disabled, or customized. This matrix summarizes the supported (and 679planned) features and correlates them with the collection techniques which 680typically require them.</p> 681 682<table> 683 <tr> 684 <th>Algorithm</th> 685 <th>Done</th> 686 <th>shadow stack</th> 687 <th>refcount</th> 688 <th>mark-sweep</th> 689 <th>copying</th> 690 <th>incremental</th> 691 <th>threaded</th> 692 <th>concurrent</th> 693 </tr> 694 <tr> 695 <th class="rowhead"><a href="#stack-map">stack map</a></th> 696 <td>✔</td> 697 <td></td> 698 <td></td> 699 <td>✘</td> 700 <td>✘</td> 701 <td>✘</td> 702 <td>✘</td> 703 <td>✘</td> 704 </tr> 705 <tr> 706 <th class="rowhead"><a href="#init-roots">initialize roots</a></th> 707 <td>✔</td> 708 <td>✘</td> 709 <td>✘</td> 710 <td>✘</td> 711 <td>✘</td> 712 <td>✘</td> 713 <td>✘</td> 714 <td>✘</td> 715 </tr> 716 <tr class="doc_warning"> 717 <th class="rowhead">derived pointers</th> 718 <td>NO</td> 719 <td></td> 720 <td></td> 721 <td></td> 722 <td></td> 723 <td></td> 724 <td>✘*</td> 725 <td>✘*</td> 726 </tr> 727 <tr> 728 <th class="rowhead"><em><a href="#custom">custom lowering</a></em></th> 729 <td>✔</td> 730 <th></th> 731 <th></th> 732 <th></th> 733 <th></th> 734 <th></th> 735 <th></th> 736 <th></th> 737 </tr> 738 <tr> 739 <th class="rowhead indent">gcroot</th> 740 <td>✔</td> 741 <td>✘</td> 742 <td>✘</td> 743 <td></td> 744 <td></td> 745 <td></td> 746 <td></td> 747 <td></td> 748 </tr> 749 <tr> 750 <th class="rowhead indent">gcwrite</th> 751 <td>✔</td> 752 <td></td> 753 <td>✘</td> 754 <td></td> 755 <td></td> 756 <td>✘</td> 757 <td></td> 758 <td>✘</td> 759 </tr> 760 <tr> 761 <th class="rowhead indent">gcread</th> 762 <td>✔</td> 763 <td></td> 764 <td></td> 765 <td></td> 766 <td></td> 767 <td></td> 768 <td></td> 769 <td>✘</td> 770 </tr> 771 <tr> 772 <th class="rowhead"><em><a href="#safe-points">safe points</a></em></th> 773 <td></td> 774 <th></th> 775 <th></th> 776 <th></th> 777 <th></th> 778 <th></th> 779 <th></th> 780 <th></th> 781 </tr> 782 <tr> 783 <th class="rowhead indent">in calls</th> 784 <td>✔</td> 785 <td></td> 786 <td></td> 787 <td>✘</td> 788 <td>✘</td> 789 <td>✘</td> 790 <td>✘</td> 791 <td>✘</td> 792 </tr> 793 <tr> 794 <th class="rowhead indent">before calls</th> 795 <td>✔</td> 796 <td></td> 797 <td></td> 798 <td></td> 799 <td></td> 800 <td></td> 801 <td>✘</td> 802 <td>✘</td> 803 </tr> 804 <tr class="doc_warning"> 805 <th class="rowhead indent">for loops</th> 806 <td>NO</td> 807 <td></td> 808 <td></td> 809 <td></td> 810 <td></td> 811 <td></td> 812 <td>✘</td> 813 <td>✘</td> 814 </tr> 815 <tr> 816 <th class="rowhead indent">before escape</th> 817 <td>✔</td> 818 <td></td> 819 <td></td> 820 <td></td> 821 <td></td> 822 <td></td> 823 <td>✘</td> 824 <td>✘</td> 825 </tr> 826 <tr class="doc_warning"> 827 <th class="rowhead">emit code at safe points</th> 828 <td>NO</td> 829 <td></td> 830 <td></td> 831 <td></td> 832 <td></td> 833 <td></td> 834 <td>✘</td> 835 <td>✘</td> 836 </tr> 837 <tr> 838 <th class="rowhead"><em>output</em></th> 839 <td></td> 840 <th></th> 841 <th></th> 842 <th></th> 843 <th></th> 844 <th></th> 845 <th></th> 846 <th></th> 847 </tr> 848 <tr> 849 <th class="rowhead indent"><a href="#assembly">assembly</a></th> 850 <td>✔</td> 851 <td></td> 852 <td></td> 853 <td>✘</td> 854 <td>✘</td> 855 <td>✘</td> 856 <td>✘</td> 857 <td>✘</td> 858 </tr> 859 <tr class="doc_warning"> 860 <th class="rowhead indent">JIT</th> 861 <td>NO</td> 862 <td></td> 863 <td></td> 864 <td class="optl">✘</td> 865 <td class="optl">✘</td> 866 <td class="optl">✘</td> 867 <td class="optl">✘</td> 868 <td class="optl">✘</td> 869 </tr> 870 <tr class="doc_warning"> 871 <th class="rowhead indent">obj</th> 872 <td>NO</td> 873 <td></td> 874 <td></td> 875 <td class="optl">✘</td> 876 <td class="optl">✘</td> 877 <td class="optl">✘</td> 878 <td class="optl">✘</td> 879 <td class="optl">✘</td> 880 </tr> 881 <tr class="doc_warning"> 882 <th class="rowhead">live analysis</th> 883 <td>NO</td> 884 <td></td> 885 <td></td> 886 <td class="optl">✘</td> 887 <td class="optl">✘</td> 888 <td class="optl">✘</td> 889 <td class="optl">✘</td> 890 <td class="optl">✘</td> 891 </tr> 892 <tr class="doc_warning"> 893 <th class="rowhead">register map</th> 894 <td>NO</td> 895 <td></td> 896 <td></td> 897 <td class="optl">✘</td> 898 <td class="optl">✘</td> 899 <td class="optl">✘</td> 900 <td class="optl">✘</td> 901 <td class="optl">✘</td> 902 </tr> 903 <tr> 904 <td colspan="10"> 905 <div><span class="doc_warning">*</span> Derived pointers only pose a 906 hazard to copying collectors.</div> 907 <div><span class="optl">✘</span> in gray denotes a feature which 908 could be utilized if available.</div> 909 </td> 910 </tr> 911</table> 912 913<p>To be clear, the collection techniques above are defined as:</p> 914 915<dl> 916 <dt>Shadow Stack</dt> 917 <dd>The mutator carefully maintains a linked list of stack roots.</dd> 918 <dt>Reference Counting</dt> 919 <dd>The mutator maintains a reference count for each object and frees an 920 object when its count falls to zero.</dd> 921 <dt>Mark-Sweep</dt> 922 <dd>When the heap is exhausted, the collector marks reachable objects starting 923 from the roots, then deallocates unreachable objects in a sweep 924 phase.</dd> 925 <dt>Copying</dt> 926 <dd>As reachability analysis proceeds, the collector copies objects from one 927 heap area to another, compacting them in the process. Copying collectors 928 enable highly efficient "bump pointer" allocation and can improve locality 929 of reference.</dd> 930 <dt>Incremental</dt> 931 <dd>(Including generational collectors.) Incremental collectors generally have 932 all the properties of a copying collector (regardless of whether the 933 mature heap is compacting), but bring the added complexity of requiring 934 write barriers.</dd> 935 <dt>Threaded</dt> 936 <dd>Denotes a multithreaded mutator; the collector must still stop the mutator 937 ("stop the world") before beginning reachability analysis. Stopping a 938 multithreaded mutator is a complicated problem. It generally requires 939 highly platform specific code in the runtime, and the production of 940 carefully designed machine code at safe points.</dd> 941 <dt>Concurrent</dt> 942 <dd>In this technique, the mutator and the collector run concurrently, with 943 the goal of eliminating pause times. In a <em>cooperative</em> collector, 944 the mutator further aids with collection should a pause occur, allowing 945 collection to take advantage of multiprocessor hosts. The "stop the world" 946 problem of threaded collectors is generally still present to a limited 947 extent. Sophisticated marking algorithms are necessary. Read barriers may 948 be necessary.</dd> 949</dl> 950 951<p>As the matrix indicates, LLVM's garbage collection infrastructure is already 952suitable for a wide variety of collectors, but does not currently extend to 953multithreaded programs. This will be added in the future as there is 954interest.</p> 955 956</div> 957 958<!-- ======================================================================= --> 959<h3> 960 <a name="stack-map">Computing stack maps</a> 961</h3> 962 963<div> 964 965<p>LLVM automatically computes a stack map. One of the most important features 966of a <tt>GCStrategy</tt> is to compile this information into the executable in 967the binary representation expected by the runtime library.</p> 968 969<p>The stack map consists of the location and identity of each GC root in the 970each function in the module. For each root:</p> 971 972<ul> 973 <li><tt>RootNum</tt>: The index of the root.</li> 974 <li><tt>StackOffset</tt>: The offset of the object relative to the frame 975 pointer.</li> 976 <li><tt>RootMetadata</tt>: The value passed as the <tt>%metadata</tt> 977 parameter to the <a href="#gcroot"><tt>@llvm.gcroot</tt></a> intrinsic.</li> 978</ul> 979 980<p>Also, for the function as a whole:</p> 981 982<ul> 983 <li><tt>getFrameSize()</tt>: The overall size of the function's initial 984 stack frame, not accounting for any dynamic allocation.</li> 985 <li><tt>roots_size()</tt>: The count of roots in the function.</li> 986</ul> 987 988<p>To access the stack map, use <tt>GCFunctionMetadata::roots_begin()</tt> and 989-<tt>end()</tt> from the <tt><a 990href="#assembly">GCMetadataPrinter</a></tt>:</p> 991 992<blockquote><pre 993>for (iterator I = begin(), E = end(); I != E; ++I) { 994 GCFunctionInfo *FI = *I; 995 unsigned FrameSize = FI->getFrameSize(); 996 size_t RootCount = FI->roots_size(); 997 998 for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(), 999 RE = FI->roots_end(); 1000 RI != RE; ++RI) { 1001 int RootNum = RI->Num; 1002 int RootStackOffset = RI->StackOffset; 1003 Constant *RootMetadata = RI->Metadata; 1004 } 1005}</pre></blockquote> 1006 1007<p>If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code generation by 1008a custom lowering pass, LLVM will compute an empty stack map. This may be useful 1009for collector plugins which implement reference counting or a shadow stack.</p> 1010 1011</div> 1012 1013 1014<!-- ======================================================================= --> 1015<h3> 1016 <a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a> 1017</h3> 1018 1019<div> 1020 1021<blockquote><pre 1022>MyGC::MyGC() { 1023 InitRoots = true; 1024}</pre></blockquote> 1025 1026<p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon 1027entry to the function. This prevents the GC's sweep phase from visiting 1028uninitialized pointers, which will almost certainly cause it to crash. This 1029initialization occurs before custom lowering, so the two may be used 1030together.</p> 1031 1032<p>Since LLVM does not yet compute liveness information, there is no means of 1033distinguishing an uninitialized stack root from an initialized one. Therefore, 1034this feature should be used by all GC plugins. It is enabled by default.</p> 1035 1036</div> 1037 1038 1039<!-- ======================================================================= --> 1040<h3> 1041 <a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, 1042 <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a> 1043</h3> 1044 1045<div> 1046 1047<p>For GCs which use barriers or unusual treatment of stack roots, these 1048flags allow the collector to perform arbitrary transformations of the LLVM 1049IR:</p> 1050 1051<blockquote><pre 1052>class MyGC : public GCStrategy { 1053public: 1054 MyGC() { 1055 CustomRoots = true; 1056 CustomReadBarriers = true; 1057 CustomWriteBarriers = true; 1058 } 1059 1060 virtual bool initializeCustomLowering(Module &M); 1061 virtual bool performCustomLowering(Function &F); 1062};</pre></blockquote> 1063 1064<p>If any of these flags are set, then LLVM suppresses its default lowering for 1065the corresponding intrinsics and instead calls 1066<tt>performCustomLowering</tt>.</p> 1067 1068<p>LLVM's default action for each intrinsic is as follows:</p> 1069 1070<ul> 1071 <li><tt>llvm.gcroot</tt>: Leave it alone. The code generator must see it 1072 or the stack map will not be computed.</li> 1073 <li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li> 1074 <li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li> 1075</ul> 1076 1077<p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified, 1078then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the 1079corresponding barriers.</p> 1080 1081<p><tt>performCustomLowering</tt> must comply with the same restrictions as <a 1082href="WritingAnLLVMPass.html#runOnFunction"><tt 1083>FunctionPass::runOnFunction</tt></a>. 1084Likewise, <tt>initializeCustomLowering</tt> has the same semantics as <a 1085href="WritingAnLLVMPass.html#doInitialization_mod"><tt 1086>Pass::doInitialization(Module&)</tt></a>.</p> 1087 1088<p>The following can be used as a template:</p> 1089 1090<blockquote><pre 1091>#include "llvm/Module.h" 1092#include "llvm/IntrinsicInst.h" 1093 1094bool MyGC::initializeCustomLowering(Module &M) { 1095 return false; 1096} 1097 1098bool MyGC::performCustomLowering(Function &F) { 1099 bool MadeChange = false; 1100 1101 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 1102 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) 1103 if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) 1104 if (Function *F = CI->getCalledFunction()) 1105 switch (F->getIntrinsicID()) { 1106 case Intrinsic::gcwrite: 1107 // Handle llvm.gcwrite. 1108 CI->eraseFromParent(); 1109 MadeChange = true; 1110 break; 1111 case Intrinsic::gcread: 1112 // Handle llvm.gcread. 1113 CI->eraseFromParent(); 1114 MadeChange = true; 1115 break; 1116 case Intrinsic::gcroot: 1117 // Handle llvm.gcroot. 1118 CI->eraseFromParent(); 1119 MadeChange = true; 1120 break; 1121 } 1122 1123 return MadeChange; 1124}</pre></blockquote> 1125 1126</div> 1127 1128 1129<!-- ======================================================================= --> 1130<h3> 1131 <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a> 1132</h3> 1133 1134<div> 1135 1136<p>LLVM can compute four kinds of safe points:</p> 1137 1138<blockquote><pre 1139>namespace GC { 1140 /// PointKind - The type of a collector-safe point. 1141 /// 1142 enum PointKind { 1143 Loop, //< Instr is a loop (backwards branch). 1144 Return, //< Instr is a return instruction. 1145 PreCall, //< Instr is a call instruction. 1146 PostCall //< Instr is the return address of a call. 1147 }; 1148}</pre></blockquote> 1149 1150<p>A collector can request any combination of the four by setting the 1151<tt>NeededSafePoints</tt> mask:</p> 1152 1153<blockquote><pre 1154>MyGC::MyGC() { 1155 NeededSafePoints = 1 << GC::Loop 1156 | 1 << GC::Return 1157 | 1 << GC::PreCall 1158 | 1 << GC::PostCall; 1159}</pre></blockquote> 1160 1161<p>It can then use the following routines to access safe points.</p> 1162 1163<blockquote><pre 1164>for (iterator I = begin(), E = end(); I != E; ++I) { 1165 GCFunctionInfo *MD = *I; 1166 size_t PointCount = MD->size(); 1167 1168 for (GCFunctionInfo::iterator PI = MD->begin(), 1169 PE = MD->end(); PI != PE; ++PI) { 1170 GC::PointKind PointKind = PI->Kind; 1171 unsigned PointNum = PI->Num; 1172 } 1173} 1174</pre></blockquote> 1175 1176<p>Almost every collector requires <tt>PostCall</tt> safe points, since these 1177correspond to the moments when the function is suspended during a call to a 1178subroutine.</p> 1179 1180<p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee 1181that the application will reach a safe point within a bounded amount of time, 1182even if it is executing a long-running loop which contains no function 1183calls.</p> 1184 1185<p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt> 1186safe points to implement "stop the world" techniques using self-modifying code, 1187where it is important that the program not exit the function without reaching a 1188safe point (because only the topmost function has been patched).</p> 1189 1190</div> 1191 1192 1193<!-- ======================================================================= --> 1194<h3> 1195 <a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a> 1196</h3> 1197 1198<div> 1199 1200<p>LLVM allows a plugin to print arbitrary assembly code before and after the 1201rest of a module's assembly code. At the end of the module, the GC can compile 1202the LLVM stack map into assembly code. (At the beginning, this information is not 1203yet computed.)</p> 1204 1205<p>Since AsmWriter and CodeGen are separate components of LLVM, a separate 1206abstract base class and registry is provided for printing assembly code, the 1207<tt>GCMetadaPrinter</tt> and <tt>GCMetadataPrinterRegistry</tt>. The AsmWriter 1208will look for such a subclass if the <tt>GCStrategy</tt> sets 1209<tt>UsesMetadata</tt>:</p> 1210 1211<blockquote><pre 1212>MyGC::MyGC() { 1213 UsesMetadata = true; 1214}</pre></blockquote> 1215 1216<p>This separation allows JIT-only clients to be smaller.</p> 1217 1218<p>Note that LLVM does not currently have analogous APIs to support code 1219generation in the JIT, nor using the object writers.</p> 1220 1221<blockquote><pre 1222>// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer 1223 1224#include "llvm/CodeGen/GCMetadataPrinter.h" 1225#include "llvm/Support/Compiler.h" 1226 1227using namespace llvm; 1228 1229namespace { 1230 class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter { 1231 public: 1232 virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP, 1233 const TargetAsmInfo &TAI); 1234 1235 virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP, 1236 const TargetAsmInfo &TAI); 1237 }; 1238 1239 GCMetadataPrinterRegistry::Add<MyGCPrinter> 1240 X("mygc", "My bespoke garbage collector."); 1241}</pre></blockquote> 1242 1243<p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to 1244print portable assembly code to the <tt>std::ostream</tt>. The collector itself 1245contains the stack map for the entire module, and may access the 1246<tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt> 1247methods. Here's a realistic example:</p> 1248 1249<blockquote><pre 1250>#include "llvm/CodeGen/AsmPrinter.h" 1251#include "llvm/Function.h" 1252#include "llvm/Target/TargetMachine.h" 1253#include "llvm/Target/TargetData.h" 1254#include "llvm/Target/TargetAsmInfo.h" 1255 1256void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP, 1257 const TargetAsmInfo &TAI) { 1258 // Nothing to do. 1259} 1260 1261void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP, 1262 const TargetAsmInfo &TAI) { 1263 // Set up for emitting addresses. 1264 const char *AddressDirective; 1265 int AddressAlignLog; 1266 if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) { 1267 AddressDirective = TAI.getData32bitsDirective(); 1268 AddressAlignLog = 2; 1269 } else { 1270 AddressDirective = TAI.getData64bitsDirective(); 1271 AddressAlignLog = 3; 1272 } 1273 1274 // Put this in the data section. 1275 AP.SwitchToDataSection(TAI.getDataSection()); 1276 1277 // For each function... 1278 for (iterator FI = begin(), FE = end(); FI != FE; ++FI) { 1279 GCFunctionInfo &MD = **FI; 1280 1281 // Emit this data structure: 1282 // 1283 // struct { 1284 // int32_t PointCount; 1285 // struct { 1286 // void *SafePointAddress; 1287 // int32_t LiveCount; 1288 // int32_t LiveOffsets[LiveCount]; 1289 // } Points[PointCount]; 1290 // } __gcmap_<FUNCTIONNAME>; 1291 1292 // Align to address width. 1293 AP.EmitAlignment(AddressAlignLog); 1294 1295 // Emit the symbol by which the stack map entry can be found. 1296 std::string Symbol; 1297 Symbol += TAI.getGlobalPrefix(); 1298 Symbol += "__gcmap_"; 1299 Symbol += MD.getFunction().getName(); 1300 if (const char *GlobalDirective = TAI.getGlobalDirective()) 1301 OS << GlobalDirective << Symbol << "\n"; 1302 OS << TAI.getGlobalPrefix() << Symbol << ":\n"; 1303 1304 // Emit PointCount. 1305 AP.EmitInt32(MD.size()); 1306 AP.EOL("safe point count"); 1307 1308 // And each safe point... 1309 for (GCFunctionInfo::iterator PI = MD.begin(), 1310 PE = MD.end(); PI != PE; ++PI) { 1311 // Align to address width. 1312 AP.EmitAlignment(AddressAlignLog); 1313 1314 // Emit the address of the safe point. 1315 OS << AddressDirective 1316 << TAI.getPrivateGlobalPrefix() << "label" << PI->Num; 1317 AP.EOL("safe point address"); 1318 1319 // Emit the stack frame size. 1320 AP.EmitInt32(MD.getFrameSize()); 1321 AP.EOL("stack frame size"); 1322 1323 // Emit the number of live roots in the function. 1324 AP.EmitInt32(MD.live_size(PI)); 1325 AP.EOL("live root count"); 1326 1327 // And for each live root... 1328 for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI), 1329 LE = MD.live_end(PI); 1330 LI != LE; ++LI) { 1331 // Print its offset within the stack frame. 1332 AP.EmitInt32(LI->StackOffset); 1333 AP.EOL("stack offset"); 1334 } 1335 } 1336 } 1337} 1338</pre></blockquote> 1339 1340</div> 1341 1342</div> 1343 1344<!-- *********************************************************************** --> 1345<h2> 1346 <a name="references">References</a> 1347</h2> 1348<!-- *********************************************************************** --> 1349 1350<div> 1351 1352<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew 1353W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p> 1354 1355<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for 1356strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN 1357PLDI'91.</p> 1358 1359<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using 1360explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM 1361conference on LISP and functional programming.</p> 1362 1363<p><a name="henderson02">[Henderson2002]</a> <a 1364href="http://citeseer.ist.psu.edu/henderson02accurate.html"> 1365Accurate Garbage Collection in an Uncooperative Environment</a>. 1366Fergus Henderson. International Symposium on Memory Management 2002.</p> 1367 1368</div> 1369 1370 1371<!-- *********************************************************************** --> 1372 1373<hr> 1374<address> 1375 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img 1376 src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a> 1377 <a href="http://validator.w3.org/check/referer"><img 1378 src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a> 1379 1380 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> 1381 <a href="http://llvm.org/">LLVM Compiler Infrastructure</a><br> 1382 Last modified: $Date: 2011-08-12 02:17:17 -0400 (Fri, 12 Aug 2011) $ 1383</address> 1384 1385</body> 1386</html> 1387