<li><a href="#interfaces">Interfaces for user programs</a>
<ul>
<li><a href="#roots">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a></li>
- <li><a href="#gcdescriptors">GC descriptor format for heap objects</a></li>
<li><a href="#allocate">Allocating memory from the GC</a></li>
<li><a href="#barriers">Reading and writing references to the heap</a></li>
<li><a href="#explicit">Explicit invocation of the garbage collector</a></li>
<li><a href="#gcimpl">Implementing a garbage collector</a>
<ul>
<li><a href="#llvm_gc_readwrite">Implementing <tt>llvm_gc_read</tt> and <tt>llvm_gc_write</tt></a></li>
- <li><a href="#traceroots">Tracing the GC roots from the program stack</a></li>
- <li><a href="#gcimpls">GC implementations available</a></li>
+ <li><a href="#callbacks">Callback functions used to implement the garbage collector</a></li>
+ </ul>
+ </li>
+ <li><a href="#gcimpls">GC implementations available</a>
+ <ul>
+ <li><a href="#semispace">SemiSpace - A simple copying garbage collector</a></li>
</ul>
</li>
<p>Conservative garbage collection often does not require any special support
from either the language or the compiler: it can handle non-type-safe
programming languages (such as C/C++) and does not require any special
-information from the compiler. The [LINK] Boehm collector is an example of a
-state-of-the-art conservative collector.</p>
+information from the compiler. The
+<a href="http://www.hpl.hp.com/personal/Hans_Boehm/gc/">Boehm collector</a> is
+an example of a state-of-the-art conservative collector.</p>
<p>Accurate garbage collection requires the ability to identify all pointers in
the program at run-time (which requires that the source-language be type-safe in
<div class="doc_text">
<div class="doc_code"><tt>
- void %llvm.gcroot(<ty>** %ptrloc, <ty2>* %metadata)
+ void %llvm.gcroot(i8** %ptrloc, i8* %metadata)
</tt></div>
<p>
The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM of a pointer variable
on the stack. The first argument contains the address of the variable on the
stack, and the second contains a pointer to metadata that should be associated
-with the pointer (which <b>must</b> be a constant or global value address). At
-runtime, the <tt>llvm.gcroot</tt> intrinsic stores a null pointer into the
-specified location to initialize the pointer.</p>
+with the pointer (which <b>must</b> be a constant or global value address).</p>
<p>
Consider the following fragment of Java code:
%X = alloca %Object*
...
+ ;; Java null-initializes pointers.
+ store %Object* null, %Object** %X
+
;; "CodeBlock" is the block corresponding to the start
;; of the scope above.
CodeBlock:
;; Initialize the object, telling LLVM that it is now live.
;; Java has type-tags on objects, so it doesn't need any
;; metadata.
- call void %llvm.gcroot(%Object** %X, sbyte* null)
+ %tmp = bitcast %Object** %X to i8**
+ call void %llvm.gcroot(i8** %tmp, i8* null)
...
;; As the pointer goes out of scope, store a null value into
</div>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="gcdescriptors">GC descriptor format for heap objects</a>
-</div>
-
-<div class="doc_text">
-
-<p>
-TODO: Either from root meta data, or from object headers. Front-end can provide a
-call-back to get descriptor from object without meta-data.
-</p>
-
-</div>
-
<!-- ======================================================================= -->
<div class="doc_subsection">
<a name="allocate">Allocating memory from the GC</a>
<div class="doc_text">
<div class="doc_code"><tt>
- sbyte *%llvm_gc_allocate(unsigned %Size)
+ void *llvm_gc_allocate(unsigned Size)
</tt></div>
<p>The <tt>llvm_gc_allocate</tt> function is a global function defined by the
-garbage collector implementation to allocate memory. It should return a
+garbage collector implementation to allocate memory. It returns a
zeroed-out block of memory of the appropriate size.</p>
</div>
<div class="doc_text">
<div class="doc_code"><tt>
- sbyte *%llvm.gcread(sbyte **)<br>
- void %llvm.gcwrite(sbyte*, sbyte**)
+ i8 *%llvm.gcread(i8 *, i8 **)<br>
+ void %llvm.gcwrite(i8*, i8*, i8**)
</tt></div>
<p>Several of the more interesting garbage collectors (e.g., generational
collection) reads or writes object references into the heap. In the case of a
generational collector, it needs to keep track of which "old" generation objects
have references stored into them. The amount of code that typically needs to be
-executed is usually quite small, so the overall performance impact of the
-inserted code is tolerable.</p>
+executed is usually quite small (and not on the critical path of any
+computation), so the overall performance impact of the inserted code is
+tolerable.</p>
<p>To support garbage collectors that use read or write barriers, LLVM provides
the <tt>llvm.gcread</tt> and <tt>llvm.gcwrite</tt> intrinsics. The first
intrinsic has exactly the same semantics as a non-volatile LLVM load and the
-second has the same semantics as a non-volatile LLVM store. At code generation
+second has the same semantics as a non-volatile LLVM store, with the
+additions that they also take a pointer to the start of the memory
+object as an argument. At code generation
time, these intrinsics are replaced with calls into the garbage collector
(<tt><a href="#llvm_gc_readwrite">llvm_gc_read</a></tt> and <tt><a
href="#llvm_gc_readwrite">llvm_gc_write</a></tt> respectively), which are then
<div class="doc_text">
<div class="doc_code"><tt>
- void %llvm_gc_initialize()
+ void %llvm_gc_initialize(unsigned %InitialHeapSize)
</tt></div>
<p>
The <tt>llvm_gc_initialize</tt> function should be called once before any other
garbage collection functions are called. This gives the garbage collector the
-chance to initialize itself and allocate the heap spaces.
+chance to initialize itself and allocate the heap spaces. The initial heap size
+to allocate should be specified as an argument.
</p>
</div>
<div class="doc_text">
<p>
-Implementing a garbage collector for LLVM is fairly straight-forward. The
+Implementing a garbage collector for LLVM is fairly straight-forward. The LLVM
+garbage collectors are provided in a form that makes them easy to link into the
+language-specific runtime that a language front-end would use. They require
+functionality from the language-specific runtime to get information about <a
+href="#gcdescriptors">where pointers are located in heap objects</a>.
+</p>
+
+<p>The
implementation must include the <a
href="#allocate"><tt>llvm_gc_allocate</tt></a> and <a
href="#explicit"><tt>llvm_gc_collect</tt></a> functions, and it must implement
<div class="doc_text">
<div class="doc_code"><tt>
- void *llvm_gc_read(void **)<br>
- void llvm_gc_write(void*, void**)
+ void *llvm_gc_read(void*, void **)<br>
+ void llvm_gc_write(void*, void *, void**)
</tt></div>
<p>
<p>
If an actual read or write barrier is needed, it should be straight-forward to
-implement it. Note that we may add a pointer to the start of the memory object
-as a parameter in the future, if needed.
+implement it.
</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="traceroots">Tracing the GC roots from the program stack</a>
+ <a name="callbacks">Callback functions used to implement the garbage collector</a>
+</div>
+
+<div class="doc_text">
+<p>
+Garbage collector implementations make use of call-back functions that are
+implemented by other parts of the LLVM system.
+</p>
+</div>
+
+<!--_________________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="traceroots">Tracing GC pointers from the program stack</a>
</div>
<div class="doc_text">
generator that iterates through all of the GC roots on the stack, calling the
specified function pointer with each record. For each GC root, the address of
the pointer and the meta-data (from the <a
-href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
+href="#roots"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
</p>
</div>
+<!--_________________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="staticroots">Tracing GC pointers from static roots</a>
+</div>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
+<div class="doc_text">
+TODO
+</div>
+
+
+<!--_________________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="gcdescriptors">Tracing GC pointers from heap objects</a>
+</div>
+
+<div class="doc_text">
+<p>
+The three most common ways to keep track of where pointers live in heap objects
+are (listed in order of space overhead required):</p>
+
+<ol>
+<li>In languages with polymorphic objects, pointers from an object header are
+usually used to identify the GC pointers in the heap object. This is common for
+object-oriented languages like Self, Smalltalk, Java, or C#.</li>
+
+<li>If heap objects are not polymorphic, often the "shape" of the heap can be
+determined from the roots of the heap or from some other meta-data [<a
+href="#appel89">Appel89</a>, <a href="#goldberg91">Goldberg91</a>, <a
+href="#tolmach94">Tolmach94</a>]. In this case, the garbage collector can
+propagate the information around from meta data stored with the roots. This
+often eliminates the need to have a header on objects in the heap. This is
+common in the ML family.</li>
+
+<li>If all heap objects have pointers in the same locations, or pointers can be
+distinguished just by looking at them (e.g., the low order bit is clear), no
+book-keeping is needed at all. This is common for Lisp-like languages.</li>
+</ol>
+
+<p>The LLVM garbage collectors are capable of supporting all of these styles of
+language, including ones that mix various implementations. To do this, it
+allows the source-language to associate meta-data with the <a
+href="#roots">stack roots</a>, and the heap tracing routines can propagate the
+information. In addition, LLVM allows the front-end to extract GC information
+from in any form from a specific object pointer (this supports situations #1 and
+#3).
+</p>
+
+<p><b>Making this efficient</b></p>
+
+
+
+</div>
+
+
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
<a name="gcimpls">GC implementations available</a>
</div>
+<!-- *********************************************************************** -->
<div class="doc_text">
<p>
To make this more concrete, the currently implemented LLVM garbage collectors
-all live in the llvm/runtime/GC directory in the LLVM source-base.
+all live in the <tt>llvm/runtime/GC/*</tt> directories in the LLVM source-base.
+If you are interested in implementing an algorithm, there are many interesting
+possibilities (mark/sweep, a generational collector, a reference counting
+collector, etc), or you could choose to improve one of the existing algorithms.
</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="semispace">SemiSpace - A simple copying garbage collector</a>
+</div>
+
+<div class="doc_text">
<p>
-TODO: Brief overview of each.
+SemiSpace is a very simple copying collector. When it starts up, it allocates
+two blocks of memory for the heap. It uses a simple bump-pointer allocator to
+allocate memory from the first block until it runs out of space. When it runs
+out of space, it traces through all of the roots of the program, copying blocks
+to the other half of the memory space.
</p>
</div>
+<!--_________________________________________________________________________-->
+<div class="doc_subsubsection">
+ Possible Improvements
+</div>
+
+<div class="doc_text">
+
+<p>
+If a collection cycle happens and the heap is not compacted very much (say less
+than 25% of the allocated memory was freed), the memory regions should be
+doubled in size.</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="references">References</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p><a name="appel89">[Appel89]</a> Runtime Tags Aren't Necessary. Andrew
+W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.</p>
+
+<p><a name="goldberg91">[Goldberg91]</a> Tag-free garbage collection for
+strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
+PLDI'91.</p>
+
+<p><a name="tolmach94">[Tolmach94]</a> Tag-free garbage collection using
+explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
+conference on LISP and functional programming.</p>
+
+</div>
<!-- *********************************************************************** -->
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br>
+ <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff