Accurate Garbage Collection with LLVM

-LLVM does not currently support garbage collection of multi-threaded programs or -GC-safe points other than function calls, but these will be added in the future -as there is interest. -

+ +

In general, using a collector implies:

+ +

Emitting compatible code, including initialization in the main + program if necessary.
Loading a compiler plugin if the collector is not statically linked with + your compiler. For llc, use the -load option.
Selecting the collection algorithm by applying the gc "..." + attribute to your garbage collected functions, or equivalently with + the setCollector method.
Linking your final executable with the garbage collector runtime.

+ +

This table summarizes the available runtimes.

+ + + + + + + + + + + + + + + + + + + + + + + + + + +

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

+ +

The sections for Collection intrinsics and +Recommended runtime interface detail the interfaces that +collectors may require user programs to utilize.

+ +

The ShadowStack backend is invoked with the gc "shadow-stack" +function attribute. +Unlike many collectors which rely on a cooperative code generator to generate +stack maps, this algorithm carefully maintains a linked list of stack root +descriptors [Henderson2002]. This so-called "shadow +stack" mirrors the machine stack. Maintaining this data structure is slower +than using stack maps, but has a significant portability advantage because it +requires no special support from the target code generator.

+ +

The ShadowStack collector does not use read or write barriers, so the user +program may use load and store instead of llvm.gcread +and llvm.gcwrite.

+ +

ShadowStack is a code generator plugin only. It must be paired with a +compatible runtime.

+ +

The SemiSpace runtime implements the suggested +runtime interface and is compatible with the ShadowStack backend.

+ +

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.

+ +

This runtime is highly experimental and has not been used in a real project. +Enhancements would be welcomed.

+ +

The ocaml backend is invoked with the gc "ocaml" function attribute. +It supports the +Objective Caml language runtime by emitting +a type-accurate stack map in the form of an ocaml 3.10.0-compatible frametable. +The linkage requirements are satisfied automatically by the ocamlopt +compiler when linking an executable.

+ +

The ocaml collector does not use read or write barriers, so the user program +may use load and store instead of llvm.gcread and +llvm.gcwrite.

+ +

This section describes the interfaces provided by LLVM and by the garbage -collector run-time that should be used by user programs. As such, this is the -interface that front-end authors should generate code for. -

This section describes the garbage collection facilities provided by the +LLVM intermediate representation.

+ +

These facilities are limited to those strictly necessary for compilation. +They are not intended to be a complete interface to any garbage collector. +Notably, heap allocation is not among the supplied primitives. A user program +will also need to interface with the runtime, using either the +suggested runtime interface or another interface +specified by the runtime.

The gc function attribute is used to specify the desired collector +algorithm to the compiler. It is equivalent to specifying the collector name +programmatically using the setCollector method of +Function.

+ +

Specifying the collector on a per-function basis allows LLVM to link together +programs that use different garbage collection algorithms.

+ +

-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). At -runtime, the llvm.gcroot intrinsic stores a null pointer into the -specified location to initialize the pointer.

-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 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 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:

        {
@@ -177,25 +387,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)
    ...
 
    ;; "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)
+   ;; Java null-initializes pointers.
+   store %Object* null, %Object** %X
+
    ...
 
    ;; As the pointer goes out of scope, store a null value into
@@ -208,69 +420,104 @@ CodeBlock:
 
 
 
-  GC descriptor format for heap objects
+  Reading and writing references in the heap
 
 
 
 
-
-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.
-
+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.
+
+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 %object, i32 0, i32 2, i32 %n
 
 
 
 
-
-  Allocating memory from the GC
+
+  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
+
+
 
-  sbyte *%llvm_gc_allocate(unsigned %Size)
+i8* @llvm.gcread(i8* %object, i8** %derived)

 
 
-The llvm_gc_allocate function is a global function defined by the
-garbage collector implementation to allocate memory.  It should return a
-zeroed-out block of memory of the appropriate size.
+
+
+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).
+
+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.
 
 
 
-
-
-  Reading and writing references to the heap
+
+
+  Recommended runtime interface
 
+
 
 
 
-
-  sbyte *%llvm.gcread(sbyte **)

-  void %llvm.gcwrite(sbyte*, sbyte**)
-
+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.
 
-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, 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.  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.
-
+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.
 
-
-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.
+Note: This interface is a work in progress.
 
 
 
@@ -282,17 +529,36 @@ normal LLVM loads/stores.
 
 
 
-  void %llvm_gc_initialize()
+  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.
+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
@@ -301,105 +567,840 @@ chance to initialize itself and allocate the heap spaces.
 
 
 
-  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.
 
 
 
 
+
+
+  Tracing GC pointers from the program stack
+
+
+
+  
+     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.
+
+
+
+
+
+  Tracing GC pointers from static roots
+
+
+
+TODO
+
+
 
 
 
-  Implementing a garbage collector
+  Implementing a collector plugin
 
 
 
 
 
-
-Implementing a garbage collector for LLVM is fairly straight-forward.  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.
-
+User code specifies which collector plugin to use with the gc
+function attribute or, equivalently, with the setCollector method of
+Function.
+
+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 bespoke 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, code using it may be compiled using llc
+-load=MyGC.so (though MyGC.so may have some other
+platform-specific extension):
+
+$ cat sample.ll
+define void @f() gc "mygc" {
+entry:
+        ret void
+}
+$ llvm-as < sample.ll | llc -load=MyGC.so
+
+It is also possible to statically link the collector plugin into tools, such
+as a language-specific compiler front-end.
+
 
 
+
+
+  Overview of available features
+
+
+
+
+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.
+
+
 
 
 
-  Implementing llvm_gc_read and llvm_gc_write
+  Computing stack maps
 
 
 
-  
-    void *llvm_gc_read(void **)

-    void llvm_gc_write(void*, void**)
- 
 
-
-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.
-
+for (iterator I = begin(), E = end(); I != E; ++I) {
+  CollectorMetadata *MD = *I;
+  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.
 
-
-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.
-
+
+
+
+
+
+  Initializing roots to null: InitRoots
+
+
+
+
+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 the GC roots from the program stack
+  Custom lowering of intrinsics: CustomRoots, 
+    CustomReadBarriers, and CustomWriteBarriers
 
 
 
-  
-     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.
-
+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;
+  }
+  
+  virtual bool initializeCustomLowering(Module &M);
+  virtual bool performCustomLowering(Function &F);
+};
+
+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,
+then performCustomLowering must eliminate the
+corresponding barriers.
+
+performCustomLowering, must comply with the same restrictions as runOnFunction, and
+that initializeCustomLowering has the same semantics as doInitialization(Module
+&).
+
+The following can be used as a template:
+
+#include "llvm/Module.h"
+#include "llvm/IntrinsicInst.h"
+
+bool MyCollector::initializeCustomLowering(Module &M) {
+  return false;
+}
+
+bool MyCollector::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;
+}
+
 
 
 
 
 
-  GC implementations available
+  Generating safe points: NeededSafePoints
 
 
 
 
-
-To make this more concrete, the currently implemented LLVM garbage collectors
-all live in the llvm/runtime/GC directory in the LLVM source-base.
+
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.
+
+for (iterator I = begin(), E = end(); I != E; ++I) {
+  CollectorMetadata *MD = *I;
+  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 built by the code generator.
+
+Note that LLVM does not currently have analogous APIs to support code
+generation in the JIT, nor using the object writers.
+
+class MyCollector : public Collector {
+public:
+  virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
+                             const TargetAsmInfo &TAI);
+
+  virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP,
+                              const TargetAsmInfo &TAI);
+}
+
+The collector should use AsmPrinter and TargetAsmInfo to
+print portable assembly code to the std::ostream. The collector itself
+contains the stack map for the entire module, and may access the
+CollectorMetadata using its own begin() and end()
+methods. Here's a realistic example:
+
+#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 MyCollector::beginAssembly(std::ostream &OS, AsmPrinter &AP,
+                                const TargetAsmInfo &TAI) {
+  // Nothing to do.
+}
+
+void MyCollector::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) {
+    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");
+      }
+    }
+  }
+}
+
+
+
+
+
+
+
+  Implementing a collector runtime
+
+
+
+
+
+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.
 
+
 
+
+
+
+  Tracing GC pointers from heap objects
+
+
+
 
-TODO: Brief overview of each.
+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#.
+
+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
+in any form from a specific object pointer (this supports situations #1 and #3).
 
 
 
 
 
+
+
+  References
+
+
+
+
+
+[Appel89] Runtime Tags Aren't Necessary. Andrew
+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
+PLDI'91.
+
+[Tolmach94] Tag-free garbage collection using
+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.
+
+
+
+
 
 
 
@@ -410,7 +1411,7 @@ TODO: Brief overview of each.
   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!">
 
   Chris Lattner

-  LLVM Compiler Infrastructure

+  LLVM Compiler Infrastructure

   Last modified: $Date$

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. +