Accurate Garbage Collection with LLVM

Collector	`llc` arguments	Linkage	`gcroot`	`gcread`	`gcwrite`
SemiSpace	`-gc=shadow-stack`	TODO FIXME	required	optional	optional
Ocaml	`-gc=ocaml`	provided by ocamlopt	required	optional	optional

-The llvm.gcroot 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 must be a constant or global value address).

-Consider the following fragment of Java code: -

The llvm.gcroot intrinsic is used to inform LLVM of a pointer +variable on the stack. The first argument must be an alloca instruction +or a bitcast of an alloca. The second contains a pointer to metadata that +should be associated with the pointer, and must be a constant or global +value address. If your target collector uses tags, use a null pointer for +metadata.

+ +

Consider the following fragment of Java code:

        {
@@ -179,29 +362,27 @@ Consider the following fragment of Java code:
        }

-This block (which may be located in the middle of a function or in a loop nest), -could be compiled to this LLVM code: -

This block (which may be located in the middle of a function or in a loop +nest), could be compiled to this LLVM code:

 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)
    ...
 
-   ;; 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.
-   %tmp = bitcast %Object** %X to i8**
-   call void %llvm.gcroot(i8** %tmp, i8* null)
+   ;; Java null-initializes pointers.
+   store %Object* null, %Object** %X
+
    ...
 
    ;; As the pointer goes out of scope, store a null value into
@@ -214,58 +395,104 @@ CodeBlock:
 
 
 
-  Allocating memory from the GC
+  Reading and writing references in the heap
 
 
 
 
-
-  void *llvm_gc_allocate(unsigned Size)
-
+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
+read barriers and write barriers, 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.
 
-The llvm_gc_allocate function is a global function defined by the
-garbage collector implementation to allocate memory.  It returns a
-zeroed-out block of memory of the appropriate size.
+Barriers often require access to the object pointer rather than the
+derived pointer (which is a pointer to the field within the
+object). Accordingly, these intrinsics take both pointers as separate arguments
+for completeness. In this snippet, %object is the object pointer, and 
+%derived is the derived pointer:
+
+    ;; 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 %obj, i32 0, i32 2, i32 %n
 
 
 
 
-
-  Reading and writing references to the heap
+
+  Write barrier: llvm.gcwrite
 
 
+
+void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)
+
+
 
 
+For write barriers, LLVM provides the llvm.gcwrite intrinsic
+function. It has exactly the same semantics as a non-volatile store to
+the derived pointer (the third argument).
+
+Many important algorithms require write barriers, including generational
+and concurrent collectors. Additionally, write barriers could be used to
+implement reference counting.
+
+The use of this intrinsic is optional if the target collector does use
+write barriers. If so, the collector will replace it with the corresponding
+store.
+
+
+
+
+
+  Read barrier: llvm.gcread
+
+
 
-  i8 *%llvm.gcread(i8 *, i8 **)

-  void %llvm.gcwrite(i8*, i8*, i8**)
+i8* @llvm.gcread(i8* %object, i8** %derived)

 
 
-Several of the more interesting garbage collectors (e.g., generational
-collectors) need to be informed when the mutator (the program that needs garbage
-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 (and not on the critical path of any 
-computation), so the overall performance impact of the inserted code is 
-tolerable.
+
 
-To support garbage collectors that use read or write barriers, LLVM provides
-the llvm.gcread and llvm.gcwrite 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, 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
-(llvm_gc_read and llvm_gc_write respectively), which are then
-inlined into the code.
-
+For read barriers, LLVM provides the llvm.gcread intrinsic function.
+It has exactly the same semantics as a non-volatile load from the
+derived pointer (the second argument).
 
-
-If you are writing a front-end for a garbage collected language, every load or
-store of a reference from or to the heap should use these intrinsics instead of
-normal LLVM loads/stores.
+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.
+
+As with llvm.gcwrite, a target collector might not require the use
+of this intrinsic.
+
+
+
+
+
+  Recommended runtime interface
+
+
+
+
+
+LLVM specifies the following recommended runtime interface to the garbage
+collection at runtime. A program should use these interfaces to accomplish the
+tasks not supported by the intrinsics.
+
+Unlike the intrinsics, which are integral to LLVM's code generator, there is
+nothing unique about these interfaces; a front-end compiler and runtime are free
+to agree to a different specification.
+
+Note: This interface is a work in progress.
 
 
 
@@ -277,18 +504,36 @@ normal LLVM loads/stores.
 
 
 
-  void %llvm_gc_initialize(unsigned %InitialHeapSize)
+  void llvm_gc_initialize(unsigned InitialHeapSize);
 
 
 
 The llvm_gc_initialize 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.  The initial heap size
-to allocate should be specified as an argument.
+garbage collection functions are called. This gives the garbage collector the
+chance to initialize itself and allocate the heap. The initial heap size to
+allocate should be specified as an argument.
 
 
 
 
+
+
+  Allocating memory from the GC
+
+
+
+
+
+  void *llvm_gc_allocate(unsigned Size);
+
+
+The llvm_gc_allocate function is a global function defined by the
+garbage collector implementation to allocate memory. It returns a
+zeroed-out block of memory of the specified size, sufficiently aligned to store
+any object.
+
+
+
 
 
   Explicit invocation of the garbage collector
@@ -297,206 +542,806 @@ to allocate should be specified as an argument.
 
 
 
-  void %llvm_gc_collect()
+  void llvm_gc_collect();
 
 
 
 The llvm_gc_collect function is exported by the garbage collector
 implementations to provide a full collection, even when the heap is not
-exhausted.  This can be used by end-user code as a hint, and may be ignored by
+exhausted. This can be used by end-user code as a hint, and may be ignored by
 the garbage collector.
 
 
 
 
-
-
-
-  Implementing a garbage collector
+
+
+  Tracing GC pointers from the program stack
 
-
 
 
+  
+     void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
+  
 
 
-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 where pointers are located in heap objects.
-
-
-The
-implementation must include the llvm_gc_allocate and llvm_gc_collect functions, and it must implement
-the read/write barrier functions as well.  To
-do this, it will probably have to trace through the roots
-from the stack and understand the GC descriptors
-for heap objects.  Luckily, there are some example
-implementations available.
+The llvm_cg_walk_gcroots function is a function provided by the code
+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 llvm.gcroot intrinsic) are provided.
 
 
 
-
 
 
-  Implementing llvm_gc_read and llvm_gc_write
+  Tracing GC pointers from static roots
 
 
 
-  
-    void *llvm_gc_read(void*, void **)

-    void llvm_gc_write(void*, void *, void**)
- 
+TODO
+
 
-
-These functions must be implemented in every garbage collector, even if
-they do not need read/write barriers.  In this case, just load or store the
-pointer, then return.
-
 
-
-If an actual read or write barrier is needed, it should be straight-forward to
-implement it.
-
+
+
+  Implementing a collector plugin
+
+
+
+
+
+To implement a collector plugin, it is necessary to subclass
+llvm::Collector, 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 emit
+the assembly code for the collector's unique stack map data structure, which
+might be accomplished in as few as 100 LOC.
+
+To subclass llvm::Collector and register a collector:
+
+// lib/MyGC/MyGC.cpp - Example LLVM collector plugin
+
+#include "llvm/CodeGen/Collector.h"
+#include "llvm/CodeGen/Collectors.h"
+#include "llvm/CodeGen/CollectorMetadata.h"
+#include "llvm/Support/Compiler.h"
+
+using namespace llvm;
+
+namespace {
+  class VISIBILITY_HIDDEN MyCollector : public Collector {
+  public:
+    MyCollector() {}
+  };
+  
+  CollectorRegistry::Add<MyCollector>
+  X("mygc", "My custom garbage collector.");
+}
+
+Using the LLVM makefiles (like the sample
+project), this can be built into a plugin using a simple makefile:
+
+# lib/MyGC/Makefile
+
+LEVEL := ../..
+LIBRARYNAME = MyGC
+LOADABLE_MODULE = 1
+
+include $(LEVEL)/Makefile.common
+
+
+
+Once the plugin is compiled, user code may be compiled using llc
+-load=MyGC.so -gc=mygc (though MyGC.so may have some
+other platform-specific extension).
+
+
+To use a collector in a tool other than llc, simply assign a
+Collector to the llvm::TheCollector variable:
+
+TheCollector = new MyGC();
+
 
 
 
 
 
-  Callback functions used to implement the garbage collector
+  Overview of available features
 
 
 
-
-Garbage collector implementations make use of call-back functions that are
-implemented by other parts of the LLVM system.
-
+
+The boilerplate collector above does nothing. More specifically:
+
+
+  llvm.gcread calls are replaced with the corresponding
+      load instruction.
+  llvm.gcwrite calls are replaced with the corresponding
+      store instruction.
+  No stack map is emitted, and no safe points are added.
+
+
+Collector provides a range of features through which a plugin
+collector may do useful work. This matrix summarizes the supported (and planned)
+features and correlates them with the collection techniques which typically
+require them.
+
+
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+    
+    
+    
+    
+    
+    
+    
+    
+  
+  
+    
+  
+Algorithm Done shadow stack refcount mark-sweep copying incremental threaded concurrent
stack map ✔ ✘ ✘ ✘ ✘ ✘
initialize roots ✔ ✘ ✘ ✘ ✘ ✘ ✘ ✘
derived pointers NO ✘* ✘*
custom lowering ✔ 
gcroot ✔ ✘ ✘ 
gcwrite ✔ ✘ ✘ ✘
gcread ✔ ✘
safe points 
in calls ✔ ✘ ✘ ✘ ✘ ✘
before calls ✔ ✘ ✘
for loops NO ✘ ✘
before escape ✔ ✘ ✘
emit code at safe points NO ✘ ✘
output 
assembly ✔ ✘ ✘ ✘ ✘ ✘
JIT NO ✘ ✘ ✘ ✘ ✘
obj NO ✘ ✘ ✘ ✘ ✘
live analysis NO ✘ ✘ ✘ ✘ ✘
register map NO ✘ ✘ ✘ ✘ ✘

+      * Derived pointers only pose a
+           hazard to copying collectors.
+      ✘ in gray denotes a feature which
+           could be utilized if available.
+    
+
+To be clear, the collection techniques above are defined as:
+
+
+  Shadow Stack
+  The mutator carefully maintains a linked list of stack root
+      descriptors.
+  Reference Counting
+  The mutator maintains a reference count for each object and frees an
+      object when its count falls to zero.
+  Mark-Sweep
+  When the heap is exhausted, the collector marks reachable objects starting
+      from the roots, then deallocates unreachable objects in a sweep
+      phase.
+  Copying
+  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.
+  Incremental
+  (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.
+  Threaded
+  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.
+  Concurrent
+  In this technique, the mutator and the collector run concurrently, with
+      the goal of eliminating pause times. In a cooperative 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.
+
+
+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.
+
 
 
-
-
-  Tracing GC pointers from the program stack
+
+
+  Computing stack maps
 
 
 
-  
-     void llvm_cg_walk_gcroots(void (*FP)(void **Root, void *Meta));
-  
 
-
-The llvm_cg_walk_gcroots function is a function provided by the code
-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 llvm.gcroot intrinsic) are provided.
-
+CollectorMetadata &MD = ...;
+unsigned FrameSize = MD.getFrameSize();
+size_t RootCount = MD.roots_size();
+
+for (CollectorMetadata::roots_iterator RI = MD.roots_begin(),
+                                       RE = MD.roots_end(); RI != RE; ++RI) {
+  int RootNum = RI->Num;
+  int RootStackOffset = RI->StackOffset;
+  Constant *RootMetadata = RI->Metadata;
+}
+
+LLVM automatically computes a stack map. All a Collector needs to do
+is access it using CollectorMetadata::roots_begin() and
+-end(). If the llvm.gcroot intrinsic is eliminated before code
+generation by a custom lowering pass, LLVM's stack map will be empty.
+
 
 
-
-
-  Tracing GC pointers from static roots
+
+
+
+  Initializing roots to null: InitRoots
 
 
 
-TODO
+
+MyCollector::MyCollector() {
+  InitRoots = true;
+}
+
+When set, LLVM will automatically initialize each root to null upon
+entry to the function. This prevents the reachability analysis from finding
+uninitialized values in stack roots at runtime, which will almost certainly
+cause it to segfault. This initialization occurs before custom lowering, so the
+two may be used together.
+
+Since LLVM does not yet compute liveness information, this feature should be
+used by all collectors which do not custom lower llvm.gcroot, and even
+some that do.
+
 
 
 
-
-
-  Tracing GC pointers from heap objects
+
+
+  Custom lowering of intrinsics: CustomRoots, 
+    CustomReadBarriers, and CustomWriteBarriers
 
 
 
-
-The three most common ways to keep track of where pointers live in heap objects
-are (listed in order of space overhead required):
 
-
-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#.
+For collectors with barriers or unusual treatment of stack roots, these
+flags allow the collector to perform any required transformation on the LLVM
+IR:
+
+class MyCollector : public Collector {
+public:
+  MyCollector() {
+    CustomRoots = true;
+    CustomReadBarriers = true;
+    CustomWriteBarriers = true;
+  }
+  
+protected:
+  virtual Pass *createCustomLoweringPass() const {
+    return new MyGCLoweringFunctionPass();
+  }
+};
+
+If any of these flags are set, then LLVM suppresses its default lowering for
+the corresponding intrinsics and instead passes them on to a custom lowering
+pass specified by the collector.
+
+LLVM's default action for each intrinsic is as follows:
+
+
+  llvm.gcroot: Pass through to the code generator to generate a
+                            stack map.
+  llvm.gcread: Substitute a load instruction.
+  llvm.gcwrite: Substitute a store instruction.
+
+
+If CustomReadBarriers or CustomWriteBarriers are specified,
+the custom lowering pass must eliminate the corresponding
+barriers.
+
+This template can be used as a starting point for a lowering pass:
+
+#include "llvm/Function.h"
+#include "llvm/Module.h"
+#include "llvm/Instructions.h"
+
+namespace {
+  class VISIBILITY_HIDDEN MyGCLoweringFunctionPass : public FunctionPass {
+    static char ID;
+  public:
+    MyGCLoweringFunctionPass() : FunctionPass(intptr_t(&ID)) {}
+    
+    const char *getPassName() const { return "Lower GC Intrinsics"; }
+    
+    bool runOnFunction(Function &F) {
+      Module *M = F.getParent();
+      
+      Function *GCReadInt  = M->getFunction("llvm.gcread"),
+               *GCWriteInt = M->getFunction("llvm.gcwrite"),
+               *GCRootInt  = M->getFunction("llvm.gcroot");
+      
+      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 (CallInst *CI = dyn_cast<CallInst>(II++))
+            if (Function *F = CI->getCalledFunction())
+              if (F == GCWriteInt) {
+                // Handle llvm.gcwrite.
+                CI->eraseFromParent();
+                MadeChange = true;
+              } else if (F == GCReadInt) {
+                // Handle llvm.gcread.
+                CI->eraseFromParent();
+                MadeChange = true;
+              } else if (F == GCRootInt) {
+                // Handle llvm.gcroot.
+                CI->eraseFromParent();
+                MadeChange = true;
+              }
+      
+      return MadeChange;
+    }
+  };
+
+  char MyGCLoweringFunctionPass::ID = 0;
+}
 
-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 [Appel89, Goldberg91, Tolmach94].  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.
+
 
-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.
-
 
-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 stack roots, 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).
-
+
+
+  Generating safe points: NeededSafePoints
+
 
-Making this efficient
+
 
+LLVM can compute four kinds of safe points:
+
+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.
+  };
+}
+
+A collector can request any combination of the four by setting the 
+NeededSafePoints mask:
+
+MyCollector::MyCollector() {
+  NeededSafePoints = 1 << GC::Loop
+                   | 1 << GC::Return
+                   | 1 << GC::PreCall
+                   | 1 << GC::PostCall;
+}
+
+It can then use the following routines to access safe points.
+
++CollectorMetadata &MD = ...;
+size_t PointCount = MD.size();
+
+for (CollectorMetadata::iterator PI = MD.begin(),
+                                 PE = MD.end(); PI != PE; ++PI) {
+  GC::PointKind PointKind = PI->Kind;
+  unsigned PointNum = PI->Num;
+}
+
+Almost every collector requires PostCall safe points, since these
+correspond to the moments when the function is suspended during a call to a
+subroutine.
+
+Threaded programs generally require Loop 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.
+
+Threaded collectors may also require Return and PreCall
+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).
+
+
 
 
+
+
+  Emitting assembly code:
+    beginAssembly and finishAssembly
 
 
+
+
+LLVM allows a collector to print arbitrary assembly code before and after
+the rest of a module's assembly code. From the latter callback, the collector
+can print stack maps from CollectorModuleMetadata populated by the code
+generator.
+
+Note that LLVM does not currently support garbage collection code generation
+in the JIT, nor using the object writers.
+
+class MyCollector : public Collector {
+  virtual void beginAssembly(Module &M, std::ostream &OS, AsmPrinter &AP,
+                             const TargetAsmInfo &TAI) const;
+
+  virtual void finishAssembly(Module &M, CollectorModuleMetadata &MMD,
+                              std::ostream &OS, AsmPrinter &AP,
+                              const TargetAsmInfo &TAI) const;
+}
+
+The collector should use AsmPrinter and TargetAsmInfo to
+print portable assembly code to the std::ostream. The collector may
+access the stack maps for the entire module using the methods of
+CollectorModuleMetadata. Here's a realistic example:
+
+#include "llvm/CodeGen/AsmPrinter.h"
+#include "llvm/Function.h"
+#include "llvm/Target/TargetAsmInfo.h"
+
+void MyCollector::finishAssembly(Module &M,
+                                 CollectorModuleMetadata &MMD,
+                                 std::ostream &OS, AsmPrinter &AP,
+                                 const TargetAsmInfo &TAI) const {
+  // Set up for emitting addresses.
+  const char *AddressDirective;
+  int AddressAlignLog;
+  if (TAI.getAddressSize() == 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 (CollectorModuleMetadata::iterator FI = MMD.begin(),
+                                         FE = MMD.end(); FI != FE; ++FI) {
+    CollectorMetadata &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 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 (CollectorMetadata::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 (CollectorMetadata::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");
+      }
+    }
+  }
+}
+
+
+
 
 
 
 
-  GC implementations available
+  Implementing a collector runtime
 
 
 
 
 
-
-To make this more concrete, the currently implemented LLVM garbage collectors
-all live in the llvm/runtime/GC/* 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.
-
+Implementing a garbage collector for LLVM is fairly straightforward. 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 where pointers are located in heap objects.
 
+The implementation must include the
+llvm_gc_allocate and
+llvm_gc_collect functions. To do this, it will
+probably have to trace through the roots
+from the stack and understand the GC descriptors
+for heap objects. Luckily, there are some example
+implementations available.
+
 
 
+
 
 
-  SemiSpace - A simple copying garbage collector
+  Tracing GC pointers from heap objects
 
 
 
 
-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.
-
+The three most common ways to keep track of where pointers live in heap objects
+are (listed in order of space overhead required):
 
-
+
+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#.
 
-
-
-  Possible Improvements
-
+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 [Appel89, Goldberg91, Tolmach94]. 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.
 
-
+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.
+
 
-
-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.
+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 stack roots, and the heap tracing routines can propagate the
+information. In addition, LLVM allows the front-end to extract GC information
+in any form from a specific object pointer (this supports situations #1 and #3).
+
 
 
 
+
 
 
   References
@@ -509,15 +1354,21 @@ doubled in size.
 W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.
 
 [Goldberg91] Tag-free garbage collection for
-strongly typed programming languages.  Benjamin Goldberg. ACM SIGPLAN
+strongly typed programming languages. Benjamin Goldberg. ACM SIGPLAN
 PLDI'91.
 
 [Tolmach94] Tag-free garbage collection using
-explicit type parameters.  Andrew Tolmach.  Proceedings of the 1994 ACM
+explicit type parameters. Andrew Tolmach. Proceedings of the 1994 ACM
 conference on LISP and functional programming.
 
+[Henderson2002] 
+Accurate Garbage Collection in an Uncooperative Environment.
+Fergus Henderson. International Symposium on Memory Management 2002.
+
 
 
+
 
 
 
diff --git a/docs/Lexicon.html b/docs/Lexicon.html
index dac1ead4311..fbe09564c75 100644
--- a/docs/Lexicon.html
+++ b/docs/Lexicon.html
@@ -30,13 +30,19 @@
     
     - D -
     
+      DAG
+      Derived Pointer
       DSA
       DSE
     
+    - G -
+      GC
+    
     - I -
     
       IPA
       IPO
+      ISel
     
     - L -
     
@@ -44,6 +50,10 @@
       LICM
       Load-VN
     
+    - O -
+    
+      Object Pointer
+    
     - P -
     
       PRE
@@ -51,13 +61,16 @@
     - R -
     
       Reassociation
+      Root
     
     - S -
     
+      Safe Point
       SCC
       SCCP
+      SDISel
       SRoA
-      SSA
+      Stack Map
     
   
 
@@ -92,13 +105,23 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
     subexpression compuation. For example (a+b)*(a+b) has two
     subexpressions that are the same: (a+b). This optimization would
     perform the addition only once and then perform the multiply (but only if
-    its compulationally correct/safe).
+    it's compulationally correct/safe).
   
 
 
 - D -
 
   
+    DAG
+    Directed Acyclic Graph
+    Derived Pointer
+    A pointer to the interior of an object, such that a garbage collector
+    is unable to use the pointer for reachability analysis. While a derived
+    pointer is live, the corresponding object pointer must be kept in a root,
+    otherwise the collector might free the referenced object. With copying
+    collectors, derived pointers pose an additional hazard that they may be
+    invalidated at any safe point. This term is used in
+    opposition to object pointer.
     DSA
     Data Structure Analysis
     DSE
@@ -106,6 +129,24 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
   
 
 
+- G -
+
+  
+    GC
+    Garbage Collection. The practice of using reachability analysis instead
+    of explicit memory management to reclaim unused memory.
+  
+
+
+- H -
+
+  
+    Heap
+    In garbage collection, the region of memory which is managed using
+    reachability analysis.
+  
+
+
 - I -
 
   
@@ -116,6 +157,8 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
     Inter-Procedural Optimization. Refers to any variety of code
     optimization that occurs between procedures, functions or compilation units
     (modules).
+    ISel
+    Instruction Selection.
   
 
 
@@ -131,6 +174,17 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
   
 
 
+
+- O -
+
+  
+    Object Pointer
+    A pointer to an object such that the garbage collector is able to trace
+    references contained within the object. This term is used in opposition to
+    derived pointer.
+  
+
+
 
 - P -
 
@@ -147,7 +201,12 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
     Reassociation
 Rearranging
     associative expressions to promote better redundancy elimination and other
     optimization.  For example, changing (A+B-A) into (B+A-A), permitting it to
-    be optimized into (B+0) then (B).
+    be optimized into (B+0) then (B).
+    Root
 In garbage collection, a
+    pointer variable lying outside of the heap from which
+    the collector begins its reachability analysis. In the context of code
+    generation, "root" almost always refers to a "stack root"—a local or
+    temporary variable within an executing function.
   
 
 
@@ -155,6 +214,16 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
 - S -
 
   
+    Safe Point
+    In garbage collection, it is necessary to identify stack
+    roots so that reachability analysis may proceed. It may be infeasible to
+    provide this information for every instruction, so instead the information
+    may is calculated only at designated safe points. With a copying collector,
+    derived pointers must not be retained across
+    safe points and object pointers must be
+    reloaded from stack roots.
+    SDISel
+    Selection DAG Instruction Selection.
     SCC
     Strongly Connected Component
     SCCP
@@ -163,6 +232,10 @@ href="http://www.program-transformation.org/Transform/BURG">BURG tool.
     Scalar Replacement of Aggregates
     SSA
     Static Single Assignment
+    Stack Map
+    In garbage collection, metadata emitted by the code generator which
+    identifies roots within the stack frame of an executing
+    function.
   
 
 
diff --git a/docs/llvm.css b/docs/llvm.css
index 69ae45538fc..3564171126d 100644
--- a/docs/llvm.css
+++ b/docs/llvm.css
@@ -13,7 +13,7 @@ address     { clear: right; }
 
 TR, TD      { border: 2px solid gray; padding: 4pt 4pt 2pt 2pt; }
 TH          { border: 2px solid gray; font-weight: bold; font-size: 105%; 
-              color: black; background: url("img/lines.gif");
+              background: url("img/lines.gif");
               font-family: "Georgia,Palatino,Times,Roman,SanSerif"; text-align:center;
               vertical-align: middle; }
 TABLE       { text-align: center; border: 2px solid black; 
diff --git a/runtime/GC/SemiSpace/README.txt b/runtime/GC/SemiSpace/README.txt
new file mode 100644
index 00000000000..0ddf2e0426b
--- /dev/null
+++ b/runtime/GC/SemiSpace/README.txt
@@ -0,0 +1,5 @@
+//===----------------------------------------------------------------------===//
+
+Possible enhancement: 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.

Algorithm	Done	shadow stack	refcount	mark-sweep	copying	incremental	threaded	concurrent
stack map	✔			✘	✘	✘	✘	✘
initialize roots	✔	✘	✘	✘	✘	✘	✘	✘
derived pointers	NO						✘*	✘*
custom lowering	✔
gcroot	✔	✘	✘
gcwrite	✔		✘			✘		✘
gcread	✔							✘
safe points
in calls	✔			✘	✘	✘	✘	✘
before calls	✔						✘	✘
for loops	NO						✘	✘
before escape	✔						✘	✘
emit code at safe points	NO						✘	✘
output
assembly	✔			✘	✘	✘	✘	✘
JIT	NO			✘	✘	✘	✘	✘
obj	NO			✘	✘	✘	✘	✘
live analysis	NO			✘	✘	✘	✘	✘
register map	NO			✘	✘	✘	✘	✘
+ * Derived pointers only pose a + hazard to copying collectors. + ✘ in gray denotes a feature which + could be utilized if available. +