+<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 GC 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 print stack
+maps built by the code generator. (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>GCMetadaPrinterRegistry</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>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 VISIBILITY_HIDDEN 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 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="runtime-impl">Implementing a collector runtime</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p>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 <a
+href="#gcdescriptors">where pointers are located in heap objects</a>.</p>
+
+<p>The implementation must include the
+<a href="#allocate"><tt>llvm_gc_allocate</tt></a> and
+<a href="#explicit"><tt>llvm_gc_collect</tt></a> functions. To do this, it will
+probably have to <a href="#traceroots">trace through the roots
+from the stack</a> and understand the <a href="#gcdescriptors">GC descriptors
+for heap objects</a>. Luckily, there are some <a href="#usage">example
+implementations</a> available.