| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| "http://www.w3.org/TR/html4/strict.dtd"> |
| <html> |
| <head> |
| <meta http-equiv="Content-Type" Content="text/html; charset=UTF-8" > |
| <title>Accurate Garbage Collection with LLVM</title> |
| <link rel="stylesheet" href="llvm.css" type="text/css"> |
| <style type="text/css"> |
| .rowhead { text-align: left; background: inherit; } |
| .indent { padding-left: 1em; } |
| .optl { color: #BFBFBF; } |
| </style> |
| </head> |
| <body> |
| |
| <div class="doc_title"> |
| Accurate Garbage Collection with LLVM |
| </div> |
| |
| <ol> |
| <li><a href="#introduction">Introduction</a> |
| <ul> |
| <li><a href="#feature">Goals and non-goals</a></li> |
| </ul> |
| </li> |
| |
| <li><a href="#quickstart">Getting started</a> |
| <ul> |
| <li><a href="#quickstart-compiler">In your compiler</a></li> |
| <li><a href="#quickstart-runtime">In your runtime library</a></li> |
| <li><a href="#shadow-stack">About the shadow stack</a></li> |
| </ul> |
| </li> |
| |
| <li><a href="#core">Core support</a> |
| <ul> |
| <li><a href="#gcattr">Specifying GC code generation: |
| <tt>gc "..."</tt></a></li> |
| <li><a href="#gcroot">Identifying GC roots on the stack: |
| <tt>llvm.gcroot</tt></a></li> |
| <li><a href="#barriers">Reading and writing references in the heap</a> |
| <ul> |
| <li><a href="#gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a></li> |
| <li><a href="#gcread">Read barrier: <tt>llvm.gcread</tt></a></li> |
| </ul> |
| </li> |
| </ul> |
| </li> |
| |
| <li><a href="#plugin">Compiler plugin interface</a> |
| <ul> |
| <li><a href="#collector-algos">Overview of available features</a></li> |
| <li><a href="#stack-map">Computing stack maps</a></li> |
| <li><a href="#init-roots">Initializing roots to null: |
| <tt>InitRoots</tt></a></li> |
| <li><a href="#custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, |
| <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a></li> |
| <li><a href="#safe-points">Generating safe points: |
| <tt>NeededSafePoints</tt></a></li> |
| <li><a href="#assembly">Emitting assembly code: |
| <tt>GCMetadataPrinter</tt></a></li> |
| </ul> |
| </li> |
| |
| <li><a href="#runtime-impl">Implementing a collector runtime</a> |
| <ul> |
| <li><a href="#gcdescriptors">Tracing GC pointers from heap |
| objects</a></li> |
| </ul> |
| </li> |
| |
| <li><a href="#references">References</a></li> |
| |
| </ol> |
| |
| <div class="doc_author"> |
| <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> and |
| Gordon Henriksen</p> |
| </div> |
| |
| <!-- *********************************************************************** --> |
| <div class="doc_section"> |
| <a name="introduction">Introduction</a> |
| </div> |
| <!-- *********************************************************************** --> |
| |
| <div class="doc_text"> |
| |
| <p>Garbage collection is a widely used technique that frees the programmer from |
| having to know the lifetimes of heap objects, making software easier to produce |
| and maintain. Many programming languages rely on garbage collection for |
| automatic memory management. There are two primary forms of garbage collection: |
| conservative and accurate.</p> |
| |
| <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 |
| <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 |
| most cases). Identifying pointers at run-time requires compiler support to |
| locate all places that hold live pointer variables at run-time, including the |
| <a href="#gcroot">processor stack and registers</a>.</p> |
| |
| <p>Conservative garbage collection is attractive because it does not require any |
| special compiler support, but it does have problems. In particular, because the |
| conservative garbage collector cannot <i>know</i> that a particular word in the |
| machine is a pointer, it cannot move live objects in the heap (preventing the |
| use of compacting and generational GC algorithms) and it can occasionally suffer |
| from memory leaks due to integer values that happen to point to objects in the |
| program. In addition, some aggressive compiler transformations can break |
| conservative garbage collectors (though these seem rare in practice).</p> |
| |
| <p>Accurate garbage collectors do not suffer from any of these problems, but |
| they can suffer from degraded scalar optimization of the program. In particular, |
| because the runtime must be able to identify and update all pointers active in |
| the program, some optimizations are less effective. In practice, however, the |
| locality and performance benefits of using aggressive garbage collection |
| techniques dominates any low-level losses.</p> |
| |
| <p>This document describes the mechanisms and interfaces provided by LLVM to |
| support accurate garbage collection.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="feature">Goals and non-goals</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>LLVM's intermediate representation provides <a href="#intrinsics">garbage |
| collection intrinsics</a> that offer support for a broad class of |
| collector models. For instance, the intrinsics permit:</p> |
| |
| <ul> |
| <li>semi-space collectors</li> |
| <li>mark-sweep collectors</li> |
| <li>generational collectors</li> |
| <li>reference counting</li> |
| <li>incremental collectors</li> |
| <li>concurrent collectors</li> |
| <li>cooperative collectors</li> |
| </ul> |
| |
| <p>We hope that the primitive support built into the LLVM IR is sufficient to |
| support a broad class of garbage collected languages including Scheme, ML, Java, |
| C#, Perl, Python, Lua, Ruby, other scripting languages, and more.</p> |
| |
| <p>However, LLVM does not itself provide a garbage collector—this should |
| be part of your language's runtime library. LLVM provides a framework for |
| compile time <a href="#plugin">code generation plugins</a>. The role of these |
| plugins is to generate code and data structures which conforms to the <em>binary |
| interface</em> specified by the <em>runtime library</em>. This is similar to the |
| relationship between LLVM and DWARF debugging info, for example. The |
| difference primarily lies in the lack of an established standard in the domain |
| of garbage collection—thus the plugins.</p> |
| |
| <p>The aspects of the binary interface with which LLVM's GC support is |
| concerned are:</p> |
| |
| <ul> |
| <li>Creation of GC-safe points within code where collection is allowed to |
| execute safely.</li> |
| <li>Computation of the stack map. For each safe point in the code, object |
| references within the stack frame must be identified so that the |
| collector may traverse and perhaps update them.</li> |
| <li>Write barriers when storing object references to the heap. These are |
| commonly used to optimize incremental scans in generational |
| collectors.</li> |
| <li>Emission of read barriers when loading object references. These are |
| useful for interoperating with concurrent collectors.</li> |
| </ul> |
| |
| <p>There are additional areas that LLVM does not directly address:</p> |
| |
| <ul> |
| <li>Registration of global roots with the runtime.</li> |
| <li>Registration of stack map entries with the runtime.</li> |
| <li>The functions used by the program to allocate memory, trigger a |
| collection, etc.</li> |
| <li>Computation or compilation of type maps, or registration of them with |
| the runtime. These are used to crawl the heap for object |
| references.</li> |
| </ul> |
| |
| <p>In general, LLVM's support for GC does not include features which can be |
| adequately addressed with other features of the IR and does not specify a |
| particular binary interface. On the plus side, this means that you should be |
| able to integrate LLVM with an existing runtime. On the other hand, it leaves |
| a lot of work for the developer of a novel language. However, it's easy to get |
| started quickly and scale up to a more sophisticated implementation as your |
| compiler matures.</p> |
| |
| </div> |
| |
| <!-- *********************************************************************** --> |
| <div class="doc_section"> |
| <a name="quickstart">Getting started</a> |
| </div> |
| <!-- *********************************************************************** --> |
| |
| <div class="doc_text"> |
| |
| <p>Using a GC with LLVM implies many things, for example:</p> |
| |
| <ul> |
| <li>Write a runtime library or find an existing one which implements a GC |
| heap.<ol> |
| <li>Implement a memory allocator.</li> |
| <li>Design a binary interface for the stack map, used to identify |
| references within a stack frame on the machine stack.*</li> |
| <li>Implement a stack crawler to discover functions on the call stack.*</li> |
| <li>Implement a registry for global roots.</li> |
| <li>Design a binary interface for type maps, used to identify references |
| within heap objects.</li> |
| <li>Implement a collection routine bringing together all of the above.</li> |
| </ol></li> |
| <li>Emit compatible code from your compiler.<ul> |
| <li>Initialization in the main function.</li> |
| <li>Use the <tt>gc "..."</tt> attribute to enable GC code generation |
| (or <tt>F.setGC("...")</tt>).</li> |
| <li>Use <tt>@llvm.gcroot</tt> to mark stack roots.</li> |
| <li>Use <tt>@llvm.gcread</tt> and/or <tt>@llvm.gcwrite</tt> to |
| manipulate GC references, if necessary.</li> |
| <li>Allocate memory using the GC allocation routine provided by the |
| runtime library.</li> |
| <li>Generate type maps according to your runtime's binary interface.</li> |
| </ul></li> |
| <li>Write a compiler plugin to interface LLVM with the runtime library.*<ul> |
| <li>Lower <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> to appropriate |
| code sequences.*</li> |
| <li>Compile LLVM's stack map to the binary form expected by the |
| runtime.</li> |
| </ul></li> |
| <li>Load the plugin into the compiler. Use <tt>llc -load</tt> or link the |
| plugin statically with your language's compiler.*</li> |
| <li>Link program executables with the runtime.</li> |
| </ul> |
| |
| <p>To help with several of these tasks (those indicated with a *), LLVM |
| includes a highly portable, built-in ShadowStack code generator. It is compiled |
| into <tt>llc</tt> and works even with the interpreter and C backends.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="quickstart-compiler">In your compiler</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>To turn the shadow stack on for your functions, first call:</p> |
| |
| <div class="doc_code"><pre |
| >F.setGC("shadow-stack");</pre></div> |
| |
| <p>for each function your compiler emits. Since the shadow stack is built into |
| LLVM, you do not need to load a plugin.</p> |
| |
| <p>Your compiler must also use <tt>@llvm.gcroot</tt> as documented. |
| Don't forget to create a root for each intermediate value that is generated |
| when evaluating an expression. In <tt>h(f(), g())</tt>, the result of |
| <tt>f()</tt> could easily be collected if evaluating <tt>g()</tt> triggers a |
| collection.</p> |
| |
| <p>There's no need to use <tt>@llvm.gcread</tt> and <tt>@llvm.gcwrite</tt> over |
| plain <tt>load</tt> and <tt>store</tt> for now. You will need them when |
| switching to a more advanced GC.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="quickstart-runtime">In your runtime</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>The shadow stack doesn't imply a memory allocation algorithm. A semispace |
| collector or building atop <tt>malloc</tt> are great places to start, and can |
| be implemented with very little code.</p> |
| |
| <p>When it comes time to collect, however, your runtime needs to traverse the |
| stack roots, and for this it needs to integrate with the shadow stack. Luckily, |
| doing so is very simple. (This code is heavily commented to help you |
| understand the data structure, but there are only 20 lines of meaningful |
| code.)</p> |
| |
| </div> |
| |
| <div class="doc_code"><pre |
| >/// @brief The map for a single function's stack frame. One of these is |
| /// compiled as constant data into the executable for each function. |
| /// |
| /// Storage of metadata values is elided if the %metadata parameter to |
| /// @llvm.gcroot is null. |
| struct FrameMap { |
| int32_t NumRoots; //< Number of roots in stack frame. |
| int32_t NumMeta; //< Number of metadata entries. May be < NumRoots. |
| const void *Meta[0]; //< Metadata for each root. |
| }; |
| |
| /// @brief A link in the dynamic shadow stack. One of these is embedded in the |
| /// stack frame of each function on the call stack. |
| struct StackEntry { |
| StackEntry *Next; //< Link to next stack entry (the caller's). |
| const FrameMap *Map; //< Pointer to constant FrameMap. |
| void *Roots[0]; //< Stack roots (in-place array). |
| }; |
| |
| /// @brief The head of the singly-linked list of StackEntries. Functions push |
| /// and pop onto this in their prologue and epilogue. |
| /// |
| /// Since there is only a global list, this technique is not threadsafe. |
| StackEntry *llvm_gc_root_chain; |
| |
| /// @brief Calls Visitor(root, meta) for each GC root on the stack. |
| /// root and meta are exactly the values passed to |
| /// <tt>@llvm.gcroot</tt>. |
| /// |
| /// Visitor could be a function to recursively mark live objects. Or it |
| /// might copy them to another heap or generation. |
| /// |
| /// @param Visitor A function to invoke for every GC root on the stack. |
| void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) { |
| for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) { |
| unsigned i = 0; |
| |
| // For roots [0, NumMeta), the metadata pointer is in the FrameMap. |
| for (unsigned e = R->Map->NumMeta; i != e; ++i) |
| Visitor(&R->Roots[i], R->Map->Meta[i]); |
| |
| // For roots [NumMeta, NumRoots), the metadata pointer is null. |
| for (unsigned e = R->Map->NumRoots; i != e; ++i) |
| Visitor(&R->Roots[i], NULL); |
| } |
| }</pre></div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="shadow-stack">About the shadow stack</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>Unlike many GC algorithms which rely on a cooperative code generator to |
| compile stack maps, this algorithm carefully maintains a linked list of stack |
| roots [<a href="#henderson02">Henderson2002</a>]. This so-called "shadow stack" |
| mirrors the machine stack. Maintaining this data structure is slower than using |
| a stack map compiled into the executable as constant data, but has a significant |
| portability advantage because it requires no special support from the target |
| code generator, and does not require tricky platform-specific code to crawl |
| the machine stack.</p> |
| |
| <p>The tradeoff for this simplicity and portability is:</p> |
| |
| <ul> |
| <li>High overhead per function call.</li> |
| <li>Not thread-safe.</li> |
| </ul> |
| |
| <p>Still, it's an easy way to get started. After your compiler and runtime are |
| up and running, writing a <a href="#plugin">plugin</a> will allow you to take |
| advantage of <a href="#collector-algos">more advanced GC features</a> of LLVM |
| in order to improve performance.</p> |
| |
| </div> |
| |
| <!-- *********************************************************************** --> |
| <div class="doc_section"> |
| <a name="core">IR features</a><a name="intrinsics"></a> |
| </div> |
| <!-- *********************************************************************** --> |
| |
| <div class="doc_text"> |
| |
| <p>This section describes the garbage collection facilities provided by the |
| <a href="LangRef.html">LLVM intermediate representation</a>. The exact behavior |
| of these IR features is specified by the binary interface implemented by a |
| <a href="#plugin">code generation plugin</a>, not by this document.</p> |
| |
| <p>These facilities are limited to those strictly necessary; they are not |
| intended to be a complete interface to any garbage collector. A program will |
| need to interface with the GC library using the facilities provided by that |
| program.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="gcattr">Specifying GC code generation: <tt>gc "..."</tt></a> |
| </div> |
| |
| <div class="doc_code"><tt> |
| define <i>ty</i> @<i>name</i>(...) <span style="text-decoration: underline">gc "<i>name</i>"</span> { ... |
| </tt></div> |
| |
| <div class="doc_text"> |
| |
| <p>The <tt>gc</tt> function attribute is used to specify the desired GC style |
| to the compiler. Its programmatic equivalent is the <tt>setGC</tt> method of |
| <tt>Function</tt>.</p> |
| |
| <p>Setting <tt>gc "<i>name</i>"</tt> on a function triggers a search for a |
| matching code generation plugin "<i>name</i>"; it is that plugin which defines |
| the exact nature of the code generated to support GC. If none is found, the |
| compiler will raise an error.</p> |
| |
| <p>Specifying the GC style on a per-function basis allows LLVM to link together |
| programs that use different garbage collection algorithms (or none at all).</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="gcroot">Identifying GC roots on the stack: <tt>llvm.gcroot</tt></a> |
| </div> |
| |
| <div class="doc_code"><tt> |
| void @llvm.gcroot(i8** %ptrloc, i8* %metadata) |
| </tt></div> |
| |
| <div class="doc_text"> |
| |
| <p>The <tt>llvm.gcroot</tt> intrinsic is used to inform LLVM that a stack |
| variable references an object on the heap and is to be tracked for garbage |
| collection. The exact impact on generated code is specified by a <a |
| href="#plugin">compiler plugin</a>.</p> |
| |
| <p>A compiler which uses mem2reg to raise imperative code using <tt>alloca</tt> |
| into SSA form need only add a call to <tt>@llvm.gcroot</tt> for those variables |
| which a pointers into the GC heap.</p> |
| |
| <p>It is also important to mark intermediate values with <tt>llvm.gcroot</tt>. |
| For example, consider <tt>h(f(), g())</tt>. Beware leaking the result of |
| <tt>f()</tt> in the case that <tt>g()</tt> triggers a collection.</p> |
| |
| <p>The first argument <b>must</b> be a value referring to an alloca instruction |
| or a bitcast of an alloca. The second contains a pointer to metadata that |
| should be associated with the pointer, and <b>must</b> be a constant or global |
| value address. If your target collector uses tags, use a null pointer for |
| metadata.</p> |
| |
| <p>The <tt>%metadata</tt> argument can be used to avoid requiring heap objects |
| to have 'isa' pointers or tag bits. [<a href="#appel89">Appel89</a>, <a |
| href="#goldberg91">Goldberg91</a>, <a href="#tolmach94">Tolmach94</a>] If |
| specified, its value will be tracked along with the location of the pointer in |
| the stack frame.</p> |
| |
| <p>Consider the following fragment of Java code:</p> |
| |
| <pre> |
| { |
| Object X; // A null-initialized reference to an object |
| ... |
| } |
| </pre> |
| |
| <p>This block (which may be located in the middle of a function or in a loop |
| nest), could be compiled to this LLVM code:</p> |
| |
| <pre> |
| Entry: |
| ;; In the entry block for the function, allocate the |
| ;; stack space for X, which is an LLVM pointer. |
| %X = alloca %Object* |
| |
| ;; Tell LLVM that the stack space is a stack root. |
| ;; Java has type-tags on objects, so we pass null as metadata. |
| %tmp = bitcast %Object** %X to i8** |
| call void @llvm.gcroot(i8** %X, i8* null) |
| ... |
| |
| ;; "CodeBlock" is the block corresponding to the start |
| ;; of the scope above. |
| CodeBlock: |
| ;; Java null-initializes pointers. |
| store %Object* null, %Object** %X |
| |
| ... |
| |
| ;; As the pointer goes out of scope, store a null value into |
| ;; it, to indicate that the value is no longer live. |
| store %Object* null, %Object** %X |
| ... |
| </pre> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="barriers">Reading and writing references in the heap</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>Some collectors need to be informed when the mutator (the program that needs |
| garbage collection) either reads a pointer from or writes a pointer to a field |
| of a heap object. The code fragments inserted at these points are called |
| <em>read barriers</em> and <em>write barriers</em>, respectively. The amount of |
| code that needs to be executed is usually quite small and not on the critical |
| path of any computation, so the overall performance impact of the barrier is |
| tolerable.</p> |
| |
| <p>Barriers often require access to the <em>object pointer</em> rather than the |
| <em>derived pointer</em> (which is a pointer to the field within the |
| object). Accordingly, these intrinsics take both pointers as separate arguments |
| for completeness. In this snippet, <tt>%object</tt> is the object pointer, and |
| <tt>%derived</tt> is the derived pointer:</p> |
| |
| <blockquote><pre> |
| ;; An array type. |
| %class.Array = type { %class.Object, i32, [0 x %class.Object*] } |
| ... |
| |
| ;; Load the object pointer from a gcroot. |
| %object = load %class.Array** %object_addr |
| |
| ;; Compute the derived pointer. |
| %derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote> |
| |
| <p>LLVM does not enforce this relationship between the object and derived |
| pointer (although a <a href="#plugin">plugin</a> might). However, it would be |
| an unusual collector that violated it.</p> |
| |
| <p>The use of these intrinsics is naturally optional if the target GC does |
| require the corresponding barrier. Such a GC plugin will replace the intrinsic |
| calls with the corresponding <tt>load</tt> or <tt>store</tt> instruction if they |
| are used.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsubsection"> |
| <a name="gcwrite">Write barrier: <tt>llvm.gcwrite</tt></a> |
| </div> |
| |
| <div class="doc_code"><tt> |
| void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived) |
| </tt></div> |
| |
| <div class="doc_text"> |
| |
| <p>For write barriers, LLVM provides the <tt>llvm.gcwrite</tt> intrinsic |
| function. It has exactly the same semantics as a non-volatile <tt>store</tt> to |
| the derived pointer (the third argument). The exact code generated is specified |
| by a <a href="#plugin">compiler plugin</a>.</p> |
| |
| <p>Many important algorithms require write barriers, including generational |
| and concurrent collectors. Additionally, write barriers could be used to |
| implement reference counting.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsubsection"> |
| <a name="gcread">Read barrier: <tt>llvm.gcread</tt></a> |
| </div> |
| |
| <div class="doc_code"><tt> |
| i8* @llvm.gcread(i8* %object, i8** %derived)<br> |
| </tt></div> |
| |
| <div class="doc_text"> |
| |
| <p>For read barriers, LLVM provides the <tt>llvm.gcread</tt> intrinsic function. |
| It has exactly the same semantics as a non-volatile <tt>load</tt> from the |
| derived pointer (the second argument). The exact code generated is specified by |
| a <a href="#plugin">compiler plugin</a>.</p> |
| |
| <p>Read barriers are needed by fewer algorithms than write barriers, and may |
| have a greater performance impact since pointer reads are more frequent than |
| writes.</p> |
| |
| </div> |
| |
| <!-- *********************************************************************** --> |
| <div class="doc_section"> |
| <a name="plugin">Implementing a collector plugin</a> |
| </div> |
| <!-- *********************************************************************** --> |
| |
| <div class="doc_text"> |
| |
| <p>User code specifies which GC code generation to use with the <tt>gc</tt> |
| function attribute or, equivalently, with the <tt>setGC</tt> method of |
| <tt>Function</tt>.</p> |
| |
| <p>To implement a GC plugin, it is necessary to subclass |
| <tt>llvm::GCStrategy</tt>, which can be accomplished in a few lines of |
| boilerplate code. LLVM's infrastructure provides access to several important |
| algorithms. For an uncontroversial collector, all that remains may be to |
| compile LLVM's computed stack map to assembly code (using the binary |
| representation expected by the runtime library). This can be accomplished in |
| about 100 lines of code.</p> |
| |
| <p>This is not the appropriate place to implement a garbage collected heap or a |
| garbage collector itself. That code should exist in the language's runtime |
| library. The compiler plugin is responsible for generating code which |
| conforms to the binary interface defined by library, most essentially the |
| <a href="#stack-map">stack map</a>.</p> |
| |
| <p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p> |
| |
| <blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM GC plugin |
| |
| #include "llvm/CodeGen/GCStrategy.h" |
| #include "llvm/CodeGen/GCMetadata.h" |
| #include "llvm/Support/Compiler.h" |
| |
| using namespace llvm; |
| |
| namespace { |
| class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy { |
| public: |
| MyGC() {} |
| }; |
| |
| GCRegistry::Add<MyGC> |
| X("mygc", "My bespoke garbage collector."); |
| }</pre></blockquote> |
| |
| <p>This boilerplate collector does nothing. More specifically:</p> |
| |
| <ul> |
| <li><tt>llvm.gcread</tt> calls are replaced with the corresponding |
| <tt>load</tt> instruction.</li> |
| <li><tt>llvm.gcwrite</tt> calls are replaced with the corresponding |
| <tt>store</tt> instruction.</li> |
| <li>No safe points are added to the code.</li> |
| <li>The stack map is not compiled into the executable.</li> |
| </ul> |
| |
| <p>Using the LLVM makefiles (like the <a |
| href="http://llvm.org/viewvc/llvm-project/llvm/trunk/projects/sample/">sample |
| project</a>), this code can be compiled as a plugin using a simple |
| makefile:</p> |
| |
| <blockquote><pre |
| ># lib/MyGC/Makefile |
| |
| LEVEL := ../.. |
| LIBRARYNAME = <var>MyGC</var> |
| LOADABLE_MODULE = 1 |
| |
| include $(LEVEL)/Makefile.common</pre></blockquote> |
| |
| <p>Once the plugin is compiled, code using it may be compiled using <tt>llc |
| -load=<var>MyGC.so</var></tt> (though <var>MyGC.so</var> may have some other |
| platform-specific extension):</p> |
| |
| <blockquote><pre |
| >$ cat sample.ll |
| define void @f() gc "mygc" { |
| entry: |
| ret void |
| } |
| $ llvm-as < sample.ll | llc -load=MyGC.so</pre></blockquote> |
| |
| <p>It is also possible to statically link the collector plugin into tools, such |
| as a language-specific compiler front-end.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="collector-algos">Overview of available features</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p><tt>GCStrategy</tt> provides a range of features through which a plugin |
| may do useful work. Some of these are callbacks, some are algorithms that can |
| be enabled, disabled, or customized. This matrix summarizes the supported (and |
| planned) features and correlates them with the collection techniques which |
| typically require them.</p> |
| |
| <table> |
| <tr> |
| <th>Algorithm</th> |
| <th>Done</th> |
| <th>shadow stack</th> |
| <th>refcount</th> |
| <th>mark-sweep</th> |
| <th>copying</th> |
| <th>incremental</th> |
| <th>threaded</th> |
| <th>concurrent</th> |
| </tr> |
| <tr> |
| <th class="rowhead"><a href="#stack-map">stack map</a></th> |
| <td>✔</td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr> |
| <th class="rowhead"><a href="#init-roots">initialize roots</a></th> |
| <td>✔</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead">derived pointers</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td>✘*</td> |
| <td>✘*</td> |
| </tr> |
| <tr> |
| <th class="rowhead"><em><a href="#custom">custom lowering</a></em></th> |
| <td>✔</td> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| </tr> |
| <tr> |
| <th class="rowhead indent">gcroot</th> |
| <td>✔</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| </tr> |
| <tr> |
| <th class="rowhead indent">gcwrite</th> |
| <td>✔</td> |
| <td></td> |
| <td>✘</td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td></td> |
| <td>✘</td> |
| </tr> |
| <tr> |
| <th class="rowhead indent">gcread</th> |
| <td>✔</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| </tr> |
| <tr> |
| <th class="rowhead"><em><a href="#safe-points">safe points</a></em></th> |
| <td></td> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| </tr> |
| <tr> |
| <th class="rowhead indent">in calls</th> |
| <td>✔</td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr> |
| <th class="rowhead indent">before calls</th> |
| <td>✔</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead indent">for loops</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr> |
| <th class="rowhead indent">before escape</th> |
| <td>✔</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead">emit code at safe points</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr> |
| <th class="rowhead"><em>output</em></th> |
| <td></td> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| <th></th> |
| </tr> |
| <tr> |
| <th class="rowhead indent"><a href="#assembly">assembly</a></th> |
| <td>✔</td> |
| <td></td> |
| <td></td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| <td>✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead indent">JIT</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead indent">obj</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead">live analysis</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| </tr> |
| <tr class="doc_warning"> |
| <th class="rowhead">register map</th> |
| <td>NO</td> |
| <td></td> |
| <td></td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| <td class="optl">✘</td> |
| </tr> |
| <tr> |
| <td colspan="10"> |
| <div><span class="doc_warning">*</span> Derived pointers only pose a |
| hazard to copying collectors.</div> |
| <div><span class="optl">✘</span> in gray denotes a feature which |
| could be utilized if available.</div> |
| </td> |
| </tr> |
| </table> |
| |
| <p>To be clear, the collection techniques above are defined as:</p> |
| |
| <dl> |
| <dt>Shadow Stack</dt> |
| <dd>The mutator carefully maintains a linked list of stack roots.</dd> |
| <dt>Reference Counting</dt> |
| <dd>The mutator maintains a reference count for each object and frees an |
| object when its count falls to zero.</dd> |
| <dt>Mark-Sweep</dt> |
| <dd>When the heap is exhausted, the collector marks reachable objects starting |
| from the roots, then deallocates unreachable objects in a sweep |
| phase.</dd> |
| <dt>Copying</dt> |
| <dd>As reachability analysis proceeds, the collector copies objects from one |
| heap area to another, compacting them in the process. Copying collectors |
| enable highly efficient "bump pointer" allocation and can improve locality |
| of reference.</dd> |
| <dt>Incremental</dt> |
| <dd>(Including generational collectors.) Incremental collectors generally have |
| all the properties of a copying collector (regardless of whether the |
| mature heap is compacting), but bring the added complexity of requiring |
| write barriers.</dd> |
| <dt>Threaded</dt> |
| <dd>Denotes a multithreaded mutator; the collector must still stop the mutator |
| ("stop the world") before beginning reachability analysis. Stopping a |
| multithreaded mutator is a complicated problem. It generally requires |
| highly platform specific code in the runtime, and the production of |
| carefully designed machine code at safe points.</dd> |
| <dt>Concurrent</dt> |
| <dd>In this technique, the mutator and the collector run concurrently, with |
| the goal of eliminating pause times. In a <em>cooperative</em> collector, |
| the mutator further aids with collection should a pause occur, allowing |
| collection to take advantage of multiprocessor hosts. The "stop the world" |
| problem of threaded collectors is generally still present to a limited |
| extent. Sophisticated marking algorithms are necessary. Read barriers may |
| be necessary.</dd> |
| </dl> |
| |
| <p>As the matrix indicates, LLVM's garbage collection infrastructure is already |
| suitable for a wide variety of collectors, but does not currently extend to |
| multithreaded programs. This will be added in the future as there is |
| interest.</p> |
| |
| </div> |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="stack-map">Computing stack maps</a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>LLVM automatically computes a stack map. One of the most important features |
| of a <tt>GCStrategy</tt> is to compile this information into the executable in |
| the binary representation expected by the runtime library.</p> |
| |
| <p>The stack map consists of the location and identity of each GC root in the |
| each function in the module. For each root:</p> |
| |
| <ul> |
| <li><tt>RootNum</tt>: The index of the root.</li> |
| <li><tt>StackOffset</tt>: The offset of the object relative to the frame |
| pointer.</li> |
| <li><tt>RootMetadata</tt>: The value passed as the <tt>%metadata</tt> |
| parameter to the <a href="#gcroot"><tt>@llvm.gcroot</tt></a> intrinsic.</li> |
| </ul> |
| |
| <p>Also, for the function as a whole:</p> |
| |
| <ul> |
| <li><tt>getFrameSize()</tt>: The overall size of the function's initial |
| stack frame, not accounting for any dynamic allocation.</li> |
| <li><tt>roots_size()</tt>: The count of roots in the function.</li> |
| </ul> |
| |
| <p>To access the stack map, use <tt>GCFunctionMetadata::roots_begin()</tt> and |
| -<tt>end()</tt> from the <tt><a |
| href="#assembly">GCMetadataPrinter</a></tt>:</p> |
| |
| <blockquote><pre |
| >for (iterator I = begin(), E = end(); I != E; ++I) { |
| GCFunctionInfo *FI = *I; |
| unsigned FrameSize = FI->getFrameSize(); |
| size_t RootCount = FI->roots_size(); |
| |
| for (GCFunctionInfo::roots_iterator RI = FI->roots_begin(), |
| RE = FI->roots_end(); |
| RI != RE; ++RI) { |
| int RootNum = RI->Num; |
| int RootStackOffset = RI->StackOffset; |
| Constant *RootMetadata = RI->Metadata; |
| } |
| }</pre></blockquote> |
| |
| <p>If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code generation by |
| a custom lowering pass, LLVM will compute an empty stack map. This may be useful |
| for collector plugins which implement reference counting or a shadow stack.</p> |
| |
| </div> |
| |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="init-roots">Initializing roots to null: <tt>InitRoots</tt></a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <blockquote><pre |
| >MyGC::MyGC() { |
| InitRoots = true; |
| }</pre></blockquote> |
| |
| <p>When set, LLVM will automatically initialize each root to <tt>null</tt> upon |
| entry to the function. This prevents the GC's sweep phase from visiting |
| uninitialized pointers, which will almost certainly cause it to crash. This |
| initialization occurs before custom lowering, so the two may be used |
| together.</p> |
| |
| <p>Since LLVM does not yet compute liveness information, there is no means of |
| distinguishing an uninitialized stack root from an initialized one. Therefore, |
| this feature should be used by all GC plugins. It is enabled by default.</p> |
| |
| </div> |
| |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="custom">Custom lowering of intrinsics: <tt>CustomRoots</tt>, |
| <tt>CustomReadBarriers</tt>, and <tt>CustomWriteBarriers</tt></a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>For GCs which use barriers or unusual treatment of stack roots, these |
| flags allow the collector to perform arbitrary transformations of the LLVM |
| IR:</p> |
| |
| <blockquote><pre |
| >class MyGC : public GCStrategy { |
| public: |
| MyGC() { |
| CustomRoots = true; |
| CustomReadBarriers = true; |
| CustomWriteBarriers = true; |
| } |
| |
| virtual bool initializeCustomLowering(Module &M); |
| virtual bool performCustomLowering(Function &F); |
| };</pre></blockquote> |
| |
| <p>If any of these flags are set, then LLVM suppresses its default lowering for |
| the corresponding intrinsics and instead calls |
| <tt>performCustomLowering</tt>.</p> |
| |
| <p>LLVM's default action for each intrinsic is as follows:</p> |
| |
| <ul> |
| <li><tt>llvm.gcroot</tt>: Leave it alone. The code generator must see it |
| or the stack map will not be computed.</li> |
| <li><tt>llvm.gcread</tt>: Substitute a <tt>load</tt> instruction.</li> |
| <li><tt>llvm.gcwrite</tt>: Substitute a <tt>store</tt> instruction.</li> |
| </ul> |
| |
| <p>If <tt>CustomReadBarriers</tt> or <tt>CustomWriteBarriers</tt> are specified, |
| then <tt>performCustomLowering</tt> <strong>must</strong> eliminate the |
| corresponding barriers.</p> |
| |
| <p><tt>performCustomLowering</tt> must comply with the same restrictions as <a |
| href="WritingAnLLVMPass.html#runOnFunction"><tt |
| >FunctionPass::runOnFunction</tt></a>. |
| Likewise, <tt>initializeCustomLowering</tt> has the same semantics as <a |
| href="WritingAnLLVMPass.html#doInitialization_mod"><tt |
| >Pass::doInitialization(Module&)</tt></a>.</p> |
| |
| <p>The following can be used as a template:</p> |
| |
| <blockquote><pre |
| >#include "llvm/Module.h" |
| #include "llvm/IntrinsicInst.h" |
| |
| bool MyGC::initializeCustomLowering(Module &M) { |
| return false; |
| } |
| |
| bool MyGC::performCustomLowering(Function &F) { |
| bool MadeChange = false; |
| |
| for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) |
| for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) |
| if (IntrinsicInst *CI = dyn_cast<IntrinsicInst>(II++)) |
| if (Function *F = CI->getCalledFunction()) |
| switch (F->getIntrinsicID()) { |
| case Intrinsic::gcwrite: |
| // Handle llvm.gcwrite. |
| CI->eraseFromParent(); |
| MadeChange = true; |
| break; |
| case Intrinsic::gcread: |
| // Handle llvm.gcread. |
| CI->eraseFromParent(); |
| MadeChange = true; |
| break; |
| case Intrinsic::gcroot: |
| // Handle llvm.gcroot. |
| CI->eraseFromParent(); |
| MadeChange = true; |
| break; |
| } |
| |
| return MadeChange; |
| }</pre></blockquote> |
| |
| </div> |
| |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="safe-points">Generating safe points: <tt>NeededSafePoints</tt></a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>LLVM can compute four kinds of safe points:</p> |
| |
| <blockquote><pre |
| >namespace GC { |
| /// PointKind - The type of a collector-safe point. |
| /// |
| enum PointKind { |
| Loop, //< Instr is a loop (backwards branch). |
| Return, //< Instr is a return instruction. |
| PreCall, //< Instr is a call instruction. |
| PostCall //< Instr is the return address of a call. |
| }; |
| }</pre></blockquote> |
| |
| <p>A collector can request any combination of the four by setting the |
| <tt>NeededSafePoints</tt> mask:</p> |
| |
| <blockquote><pre |
| >MyGC::MyGC() { |
| NeededSafePoints = 1 << GC::Loop |
| | 1 << GC::Return |
| | 1 << GC::PreCall |
| | 1 << GC::PostCall; |
| }</pre></blockquote> |
| |
| <p>It can then use the following routines to access safe points.</p> |
| |
| <blockquote><pre |
| >for (iterator I = begin(), E = end(); I != E; ++I) { |
| GCFunctionInfo *MD = *I; |
| size_t PointCount = MD->size(); |
| |
| for (GCFunctionInfo::iterator PI = MD->begin(), |
| PE = MD->end(); PI != PE; ++PI) { |
| GC::PointKind PointKind = PI->Kind; |
| unsigned PointNum = PI->Num; |
| } |
| } |
| </pre></blockquote> |
| |
| <p>Almost every collector requires <tt>PostCall</tt> safe points, since these |
| correspond to the moments when the function is suspended during a call to a |
| subroutine.</p> |
| |
| <p>Threaded programs generally require <tt>Loop</tt> safe points to guarantee |
| that the application will reach a safe point within a bounded amount of time, |
| even if it is executing a long-running loop which contains no function |
| calls.</p> |
| |
| <p>Threaded collectors may also require <tt>Return</tt> and <tt>PreCall</tt> |
| safe points to implement "stop the world" techniques using self-modifying code, |
| where it is important that the program not exit the function without reaching a |
| safe point (because only the topmost function has been patched).</p> |
| |
| </div> |
| |
| |
| <!-- ======================================================================= --> |
| <div class="doc_subsection"> |
| <a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a> |
| </div> |
| |
| <div class="doc_text"> |
| |
| <p>LLVM allows a plugin to print arbitrary assembly code before and after the |
| rest of a module's assembly code. At the end of the module, the GC can compile |
| the LLVM stack map into assembly code. (At the beginning, this information is not |
| yet computed.)</p> |
| |
| <p>Since AsmWriter and CodeGen are separate components of LLVM, a separate |
| abstract base class and registry is provided for printing assembly code, the |
| <tt>GCMetadaPrinter</tt> and <tt>GCMetadataPrinterRegistry</tt>. The AsmWriter |
| will look for such a subclass if the <tt>GCStrategy</tt> sets |
| <tt>UsesMetadata</tt>:</p> |
| |
| <blockquote><pre |
| >MyGC::MyGC() { |
| UsesMetadata = true; |
| }</pre></blockquote> |
| |
| <p>This separation allows JIT-only clients to be smaller.</p> |
| |
| <p>Note that LLVM does not currently have analogous APIs to support code |
| generation in the JIT, nor using the object writers.</p> |
| |
| <blockquote><pre |
| >// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer |
| |
| #include "llvm/CodeGen/GCMetadataPrinter.h" |
| #include "llvm/Support/Compiler.h" |
| |
| using namespace llvm; |
| |
| namespace { |
| class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter { |
| public: |
| virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP, |
| const TargetAsmInfo &TAI); |
| |
| virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP, |
| const TargetAsmInfo &TAI); |
| }; |
| |
| GCMetadataPrinterRegistry::Add<MyGCPrinter> |
| X("mygc", "My bespoke garbage collector."); |
| }</pre></blockquote> |
| |
| <p>The collector should use <tt>AsmPrinter</tt> and <tt>TargetAsmInfo</tt> to |
| print portable assembly code to the <tt>std::ostream</tt>. The collector itself |
| contains the stack map for the entire module, and may access the |
| <tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt> |
| methods. Here's a realistic example:</p> |
| |
| <blockquote><pre |
| >#include "llvm/CodeGen/AsmPrinter.h" |
| #include "llvm/Function.h" |
| #include "llvm/Target/TargetMachine.h" |
| #include "llvm/Target/TargetData.h" |
| #include "llvm/Target/TargetAsmInfo.h" |
| |
| void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP, |
| const TargetAsmInfo &TAI) { |
| // Nothing to do. |
| } |
| |
| void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP, |
| const TargetAsmInfo &TAI) { |
| // Set up for emitting addresses. |
| const char *AddressDirective; |
| int AddressAlignLog; |
| if (AP.TM.getTargetData()->getPointerSize() == sizeof(int32_t)) { |
| AddressDirective = TAI.getData32bitsDirective(); |
| AddressAlignLog = 2; |
| } else { |
| AddressDirective = TAI.getData64bitsDirective(); |
| AddressAlignLog = 3; |
| } |
| |
| // Put this in the data section. |
| AP.SwitchToDataSection(TAI.getDataSection()); |
| |
| // For each function... |
| for (iterator FI = begin(), FE = end(); FI != FE; ++FI) { |
| GCFunctionInfo &MD = **FI; |
| |
| // Emit this data structure: |
| // |
| // struct { |
| // int32_t PointCount; |
| // struct { |
| // void *SafePointAddress; |
| // int32_t LiveCount; |
| // int32_t LiveOffsets[LiveCount]; |
| // } Points[PointCount]; |
| // } __gcmap_<FUNCTIONNAME>; |
| |
| // Align to address width. |
| AP.EmitAlignment(AddressAlignLog); |
| |
| // Emit the symbol by which the stack map entry can be found. |
| std::string Symbol; |
| Symbol += TAI.getGlobalPrefix(); |
| Symbol += "__gcmap_"; |
| Symbol += MD.getFunction().getName(); |
| if (const char *GlobalDirective = TAI.getGlobalDirective()) |
| OS << GlobalDirective << Symbol << "\n"; |
| OS << TAI.getGlobalPrefix() << Symbol << ":\n"; |
| |
| // Emit PointCount. |
| AP.EmitInt32(MD.size()); |
| AP.EOL("safe point count"); |
| |
| // And each safe point... |
| for (GCFunctionInfo::iterator PI = MD.begin(), |
| PE = MD.end(); PI != PE; ++PI) { |
| // Align to address width. |
| AP.EmitAlignment(AddressAlignLog); |
| |
| // Emit the address of the safe point. |
| OS << AddressDirective |
| << TAI.getPrivateGlobalPrefix() << "label" << PI->Num; |
| AP.EOL("safe point address"); |
| |
| // Emit the stack frame size. |
| AP.EmitInt32(MD.getFrameSize()); |
| AP.EOL("stack frame size"); |
| |
| // Emit the number of live roots in the function. |
| AP.EmitInt32(MD.live_size(PI)); |
| AP.EOL("live root count"); |
| |
| // And for each live root... |
| for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI), |
| LE = MD.live_end(PI); |
| LI != LE; ++LI) { |
| // Print its offset within the stack frame. |
| AP.EmitInt32(LI->StackOffset); |
| AP.EOL("stack offset"); |
| } |
| } |
| } |
| } |
| </pre></blockquote> |
| |
| </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> |
| |
| <p><a name="henderson02">[Henderson2002]</a> <a |
| href="http://citeseer.ist.psu.edu/henderson02accurate.html"> |
| Accurate Garbage Collection in an Uncooperative Environment</a>. |
| Fergus Henderson. International Symposium on Memory Management 2002.</p> |
| |
| </div> |
| |
| |
| <!-- *********************************************************************** --> |
| |
| <hr> |
| <address> |
| <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
| src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a> |
| <a href="http://validator.w3.org/check/referer"><img |
| src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a> |
| |
| <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
| <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br> |
| Last modified: $Date$ |
| </address> |
| |
| </body> |
| </html> |