<li><a href="#safe-points">Generating safe points:
<tt>NeededSafePoints</tt></a></li>
<li><a href="#assembly">Emitting assembly code:
- <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a></li>
+ <tt>GCMetadataPrinter</tt></a></li>
</ul>
</li>
<div class="doc_text">
<p>LLVM's intermediate representation provides <a href="#intrinsics">garbage
-collection intrinsics</a> which offer support for a broad class of
+collection intrinsics</a> that offer support for a broad class of
collector models. For instance, the intrinsics permit:</p>
<ul>
your compiler. For <tt>llc</tt>, use the <tt>-load</tt> option.</li>
<li>Selecting the collection algorithm by applying the <tt>gc "..."</tt>
attribute to your garbage collected functions, or equivalently with
- the <tt>setCollector</tt> method.</li>
+ the <tt>setGC</tt> method.</li>
<li>Linking your final executable with the garbage collector runtime.</li>
</ul>
<div class="doc_text">
-<p>The SemiSpace runtime implements with the <a href="runtime">suggested
-runtime interface</a> and is compatible the ShadowStack backend.</p>
+<p>The SemiSpace runtime implements the <a href="runtime">suggested
+runtime interface</a> and is compatible with the ShadowStack backend.</p>
<p>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
<!-- *********************************************************************** -->
<div class="doc_section">
- <a name="core">Core support</a>
+ <a name="core">Core support</a><a name="intrinsics"></a>
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
<p>The <tt>gc</tt> function attribute is used to specify the desired collector
-algorithm to the compiler. It is equivalent to specify the collector name
-programmatically using the <tt>setCollector</tt> method of
-<tt>Function</tt>.</p>
+algorithm to the compiler. It is equivalent to specifying the collector name
+programmatically using the <tt>setGC</tt> method of <tt>Function</tt>.</p>
<p>Specifying the collector on a per-function basis allows LLVM to link together
-programs which use different garbage collection algorithms.</p>
+programs that use different garbage collection algorithms.</p>
</div>
</div>
<div class="doc_code"><tt>
- void %llvm.gcroot(i8** %ptrloc, i8* %metadata)
+ 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 of a pointer
-variable on the stack. The first argument <b>must</b> be an alloca instruction
+variable on the stack. 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
;; 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)
+ call void @llvm.gcroot(i8** %X, i8* null)
...
;; "CodeBlock" is the block corresponding to the start
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.
+<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 %obj, i32 0, i32 2, i32 %n</pre></blockquote>
+ %derived = getelementptr %object, i32 0, i32 2, i32 %n</pre></blockquote>
</div>
generator that iterates through all of the GC roots on the stack, calling the
specified function pointer with each record. For each GC root, the address of
the pointer and the meta-data (from the <a
-href="#roots"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
+href="#gcroot"><tt>llvm.gcroot</tt></a> intrinsic) are provided.
</p>
</div>
<div class="doc_text">
-<p>User code specifies which collector plugin to use with the <tt>gc</tt>
-function attribute or, equivalently, with the <tt>setCollector</tt> method of
+<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 collector plugin, it is necessary to subclass
-<tt>llvm::Collector</tt>, which can be accomplished in a few lines of
+<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 emit
the assembly code for the collector's unique stack map data structure, which
might be accomplished in as few as 100 LOC.</p>
-<p>To subclass <tt>llvm::Collector</tt> and register a collector:</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 is
+compatible with that runtime library.</p>
+
+<p>To subclass <tt>llvm::GCStrategy</tt> and register it with the compiler:</p>
-<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM collector plugin
+<blockquote><pre>// lib/MyGC/MyGC.cpp - Example LLVM GC plugin
-#include "llvm/CodeGen/Collector.h"
-#include "llvm/CodeGen/Collectors.h"
-#include "llvm/CodeGen/CollectorMetadata.h"
+#include "llvm/CodeGen/GCStrategy.h"
+#include "llvm/CodeGen/GCMetadata.h"
#include "llvm/Support/Compiler.h"
using namespace llvm;
namespace {
- class VISIBILITY_HIDDEN MyCollector : public Collector {
+ class VISIBILITY_HIDDEN MyGC : public GCStrategy {
public:
- MyCollector() {}
+ MyGC() {}
};
- CollectorRegistry::Add<MyCollector>
+ GCRegistry::Add<MyGC>
X("mygc", "My bespoke garbage collector.");
}</pre></blockquote>
<blockquote><pre
>for (iterator I = begin(), E = end(); I != E; ++I) {
- CollectorMetadata *MD = *I;
- unsigned FrameSize = MD->getFrameSize();
- size_t RootCount = MD->roots_size();
+ GCFunctionInfo *FI = *I;
+ unsigned FrameSize = FI->getFrameSize();
+ size_t RootCount = FI->roots_size();
- for (CollectorMetadata::roots_iterator RI = MD->roots_begin(),
- RE = MD->roots_end();
- RI != RE; ++RI) {
+ 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>LLVM automatically computes a stack map. All a <tt>Collector</tt> needs to do
-is access it using <tt>CollectorMetadata::roots_begin()</tt> and
+<p>LLVM automatically computes a stack map. All a <tt>GCStrategy</tt> needs to do
+is access it using <tt>GCFunctionMetadata::roots_begin()</tt> and
-<tt>end()</tt>. If the <tt>llvm.gcroot</tt> intrinsic is eliminated before code
generation by a custom lowering pass, LLVM's stack map will be empty.</p>
<div class="doc_text">
<blockquote><pre
->MyCollector::MyCollector() {
+>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 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.</p>
+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, this feature should be
-used by all collectors which do not custom lower <tt>llvm.gcroot</tt>, and even
-some that do.</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_text">
-<p>For collectors with barriers or unusual treatment of stack roots, these
-flags allow the collector to perform any required transformation on the LLVM
+<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 MyCollector : public Collector {
+>class MyGC : public GCStrategy {
public:
- MyCollector() {
+ MyGC() {
CustomRoots = true;
CustomReadBarriers = true;
CustomWriteBarriers = true;
};</pre></blockquote>
<p>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.</p>
+the corresponding intrinsics and instead calls
+<tt>performCustomLowering</tt>.</p>
<p>LLVM's default action for each intrinsic is as follows:</p>
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>runOnFunction</tt></a>, and
-that <tt>initializeCustomLowering</tt> has the same semantics as <a
-href="WritingAnLLVMPass.html#doInitialization_mod"><tt>doInitialization(Module
-&)</tt></a>.</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/Instructions.h"
+#include "llvm/IntrinsicInst.h"
-bool MyCollector::initializeCustomLowering(Module &M) {
+bool MyGC::initializeCustomLowering(Module &M) {
return false;
}
-bool MyCollector::performCustomLowering(Function &F) {
- const Module *M = F.getParent();
-
- Function *GCReadInt = M->getFunction("llvm.gcread"),
- *GCWriteInt = M->getFunction("llvm.gcwrite"),
- *GCRootInt = M->getFunction("llvm.gcroot");
-
+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 (CallInst *CI = dyn_cast<CallInst>(II++))
- if (Function *F = CI->getCalledFunction())
- if (F == GCWriteInt) {
+ 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();
+ CI->eraseFromParent();
MadeChange = true;
- } else if (F == GCReadInt) {
+ break;
+ case Intrinsic::gcread:
// Handle llvm.gcread.
- CI->eraseFromParent();
+ CI->eraseFromParent();
MadeChange = true;
- } else if (F == GCRootInt) {
+ break;
+ case Intrinsic::gcroot:
// Handle llvm.gcroot.
- CI->eraseFromParent();
+ CI->eraseFromParent();
MadeChange = true;
+ break;
}
return MadeChange;
<tt>NeededSafePoints</tt> mask:</p>
<blockquote><pre
->MyCollector::MyCollector() {
+>MyGC::MyGC() {
NeededSafePoints = 1 << GC::Loop
| 1 << GC::Return
| 1 << GC::PreCall
<blockquote><pre
>for (iterator I = begin(), E = end(); I != E; ++I) {
- CollectorMetadata *MD = *I;
+ GCFunctionInfo *MD = *I;
size_t PointCount = MD->size();
- for (CollectorMetadata::iterator PI = MD->begin(),
- PE = MD->end(); PI != PE; ++PI) {
+ for (GCFunctionInfo::iterator PI = MD->begin(),
+ PE = MD->end(); PI != PE; ++PI) {
GC::PointKind PointKind = PI->Kind;
unsigned PointNum = PI->Num;
}
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="assembly">Emitting assembly code:
- <tt>beginAssembly</tt> and <tt>finishAssembly</tt></a>
+ <a name="assembly">Emitting assembly code: <tt>GCMetadataPrinter</tt></a>
</div>
<div class="doc_text">
-<p>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.</p>
+<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
->class MyCollector : public Collector {
-public:
- virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
- const TargetAsmInfo &TAI);
+>// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer
- virtual void finishAssembly(std::ostream &OS, AsmPrinter &AP,
- const TargetAsmInfo &TAI);
+#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>CollectorMetadata</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
+<tt>GCFunctionInfo</tt> using its own <tt>begin()</tt> and <tt>end()</tt>
methods. Here's a realistic example:</p>
<blockquote><pre
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetAsmInfo.h"
-void MyCollector::beginAssembly(std::ostream &OS, AsmPrinter &AP,
+void MyGCPrinter::beginAssembly(std::ostream &OS, AsmPrinter &AP,
const TargetAsmInfo &TAI) {
// Nothing to do.
}
-void MyCollector::finishAssembly(std::ostream &OS, AsmPrinter &AP,
+void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP,
const TargetAsmInfo &TAI) {
// Set up for emitting addresses.
const char *AddressDirective;
// For each function...
for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
- CollectorMetadata &MD = **FI;
+ GCFunctionInfo &MD = **FI;
// Emit this data structure:
//
AP.EOL("safe point count");
// And each safe point...
- for (CollectorMetadata::iterator PI = MD.begin(),
+ for (GCFunctionInfo::iterator PI = MD.begin(),
PE = MD.end(); PI != PE; ++PI) {
// Align to address width.
AP.EmitAlignment(AddressAlignLog);
AP.EOL("live root count");
// And for each live root...
- for (CollectorMetadata::live_iterator LI = MD.live_begin(PI),
+ for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
LE = MD.live_end(PI);
LI != LE; ++LI) {
// Print its offset within the stack frame.
<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="#gcimpls">example
+for heap objects</a>. Luckily, there are some <a href="#usage">example
implementations</a> available.
</p>
</div>
<p>The LLVM garbage collectors are capable of supporting all of these styles of
language, including ones that mix various implementations. To do this, it
allows the source-language to associate meta-data with the <a
-href="#roots">stack roots</a>, and the heap tracing routines can propagate the
+href="#gcroot">stack roots</a>, 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).
</p>
<hr>
<address>
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ 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" alt="Valid HTML 4.01!"></a>
+ 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>