Garbage collection is a widely used technique that frees the programmer from having to know the lifetimes of heap objects, making software easier to produce @@ -118,20 +118,18 @@ conservative garbage collectors (though these seem rare in practice).
they can suffer from degraded scalar optimization of the program. In particular, because the runtime must be able to identify and update all pointers active in the program, some optimizations are less effective. In practice, however, the -locality and performance benefits of using aggressive garbage allocation +locality and performance benefits of using aggressive garbage collection techniques dominates any low-level losses.This document describes the mechanisms and interfaces provided by LLVM to support accurate garbage collection.
-LLVM's intermediate representation provides garbage collection intrinsics that offer support for a broad class of @@ -151,14 +149,14 @@ collector models. For instance, the intrinsics permit:
support a broad class of garbage collected languages including Scheme, ML, Java, C#, Perl, Python, Lua, Ruby, other scripting languages, and more. -However, LLVM does not itself provide a garbage collector—this should +
However, LLVM does not itself provide a garbage collector—this should be part of your language's runtime library. LLVM provides a framework for compile time code generation plugins. The role of these plugins is to generate code and data structures which conforms to the binary interface specified by the runtime library. This is similar to the relationship between LLVM and DWARF debugging info, for example. The difference primarily lies in the lack of an established standard in the domain -of garbage collection—thus the plugins.
+of garbage collection—thus the plugins.The aspects of the binary interface with which LLVM's GC support is concerned are:
@@ -198,13 +196,15 @@ compiler matures.Using a GC with LLVM implies many things, for example:
@@ -246,14 +246,12 @@ compiler matures. includes a highly portable, built-in ShadowStack code generator. It is compiled into llc and works even with the interpreter and C backends. -To turn the shadow stack on for your functions, first call:
@@ -276,11 +274,11 @@ switching to a more advanced GC.The shadow stack doesn't imply a memory allocation algorithm. A semispace collector or building atop malloc are great places to start, and can @@ -292,10 +290,8 @@ doing so is very simple. (This code is heavily commented to help you understand the data structure, but there are only 20 lines of meaningful code.)
-/// @brief The map for a single function's stack frame. One of these is
+
+/// @brief The map for a single function's stack frame. One of these is
/// compiled as constant data into the executable for each function.
///
/// Storage of metadata values is elided if the %metadata parameter to
@@ -334,20 +330,22 @@ void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {
// For roots [0, NumMeta), the metadata pointer is in the FrameMap.
for (unsigned e = R->Map->NumMeta; i != e; ++i)
- Visitor(&R->Roots[i], R->Map->Meta[i]);
+ Visitor(&R->Roots[i], R->Map->Meta[i]);
// For roots [NumMeta, NumRoots), the metadata pointer is null.
for (unsigned e = R->Map->NumRoots; i != e; ++i)
- Visitor(&R->Roots[i], NULL);
+ Visitor(&R->Roots[i], NULL);
}
-}Unlike many GC algorithms which rely on a cooperative code generator to compile stack maps, this algorithm carefully maintains a linked list of stack @@ -372,13 +370,15 @@ in order to improve performance.
This section describes the garbage collection facilities provided by the LLVM intermediate representation. The exact behavior @@ -390,19 +390,17 @@ intended to be a complete interface to any garbage collector. A program will need to interface with the GC library using the facilities provided by that program.
-The gc function attribute is used to specify the desired GC style to the compiler. Its programmatic equivalent is the setGC method of Function.
@@ -418,16 +416,16 @@ programs that use different garbage collection algorithms (or none at all).The llvm.gcroot intrinsic is used to inform LLVM that a stack
variable references an object on the heap and is to be tracked for garbage
collection. The exact impact on generated code is specified by a
Consider the following fragment of Java code:
+
{
Object X; // A null-initialized reference to an object
...
@@ -465,7 +463,7 @@ the stack frame.
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.
@@ -494,11 +492,11 @@ CodeBlock:
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 @@ -534,19 +532,17 @@ require the corresponding barrier. Such a GC plugin will replace the intrinsic calls with the corresponding load or store instruction if they are used.
-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). The exact code generated is specified @@ -559,16 +555,16 @@ implement reference counting.
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). The exact code generated is specified by @@ -580,13 +576,17 @@ writes.
User code specifies which GC code generation to use with the gc function attribute or, equivalently, with the setGC method of @@ -617,7 +617,7 @@ conforms to the binary interface defined by library, most essentially the using namespace llvm; namespace { - class VISIBILITY_HIDDEN MyGC : public GCStrategy { + class LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy { public: MyGC() {} }; @@ -666,14 +666,12 @@ $ 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.
-GCStrategy provides a range of features through which a plugin may do useful work. Some of these are callbacks, some are algorithms that can @@ -958,11 +956,11 @@ interest.
LLVM automatically computes a stack map. One of the most important features of a GCStrategy is to compile this information into the executable in @@ -1014,11 +1012,11 @@ for collector plugins which implement reference counting or a shadow stack.
- + -MyGC::MyGC() {
@@ -1039,12 +1037,12 @@ this feature should be used by all GC plugins. It is enabled by default.
-
+
-
+
For GCs which use barriers or unusual treatment of stack roots, these
flags allow the collector to perform arbitrary transformations of the LLVM
@@ -1129,11 +1127,11 @@ bool MyGC::performCustomLowering(Function &F) {
-
+
-
+
LLVM can compute four kinds of safe points:
@@ -1193,11 +1191,11 @@ safe point (because only the topmost function has been patched).
-
+
-
+
LLVM allows a plugin to print arbitrary assembly code before and after the
rest of a module's assembly code. At the end of the module, the GC can compile
@@ -1229,7 +1227,7 @@ generation in the JIT, nor using the object writers.
using namespace llvm;
namespace {
- class VISIBILITY_HIDDEN MyGCPrinter : public GCMetadataPrinter {
+ class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter {
public:
virtual void beginAssembly(std::ostream &OS, AsmPrinter &AP,
const TargetAsmInfo &TAI);
@@ -1341,14 +1339,15 @@ void MyGCPrinter::finishAssembly(std::ostream &OS, AsmPrinter &AP,
+
-
+
References
-
+
-
+
[Appel89] Runtime Tags Aren't Necessary. Andrew
W. Appel. Lisp and Symbolic Computation 19(7):703-705, July 1989.
@@ -1379,7 +1378,7 @@ Fergus Henderson. International Symposium on Memory Management 2002.
src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01">
Chris Lattner
- LLVM Compiler Infrastructure
+ LLVM Compiler Infrastructure
Last modified: $Date$