From e2c3a49c8029ebd9ef530101cc24c66562e3dff5 Mon Sep 17 00:00:00 2001 From: mike-m Date: Fri, 7 May 2010 00:28:04 +0000 Subject: Revert r103213. It broke several sections of live website. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103219 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/GarbageCollection.html | 1387 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1387 insertions(+) create mode 100644 docs/GarbageCollection.html (limited to 'docs/GarbageCollection.html') diff --git a/docs/GarbageCollection.html b/docs/GarbageCollection.html new file mode 100644 index 0000000000..d0b651eb64 --- /dev/null +++ b/docs/GarbageCollection.html @@ -0,0 +1,1387 @@ + + + + + Accurate Garbage Collection with LLVM + + + + + +
+ Accurate Garbage Collection with LLVM +
+ +
    +
  1. Introduction + +
    2. + +
  2. Getting started + +
    3. + +
  3. Core support + +
    4. + +
  4. Compiler plugin interface + +
    5. + +
  5. Implementing a collector runtime + +
    6. + +
  6. References
    7. + +
+ +
+

Written by Chris Lattner and + Gordon Henriksen

+
+ + +
+ Introduction +
+ + +
+ +

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 +and maintain. Many programming languages rely on garbage collection for +automatic memory management. There are two primary forms of garbage collection: +conservative and accurate.

+ +

Conservative garbage collection often does not require any special support +from either the language or the compiler: it can handle non-type-safe +programming languages (such as C/C++) and does not require any special +information from the compiler. The +Boehm collector is +an example of a state-of-the-art conservative collector.

+ +

Accurate garbage collection requires the ability to identify all pointers in +the program at run-time (which requires that the source-language be type-safe in +most cases). Identifying pointers at run-time requires compiler support to +locate all places that hold live pointer variables at run-time, including the +processor stack and registers.

+ +

Conservative garbage collection is attractive because it does not require any +special compiler support, but it does have problems. In particular, because the +conservative garbage collector cannot know that a particular word in the +machine is a pointer, it cannot move live objects in the heap (preventing the +use of compacting and generational GC algorithms) and it can occasionally suffer +from memory leaks due to integer values that happen to point to objects in the +program. In addition, some aggressive compiler transformations can break +conservative garbage collectors (though these seem rare in practice).

+ +

Accurate garbage collectors do not suffer from any of these problems, but +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 collection +techniques dominates any low-level losses.

+ +

This document describes the mechanisms and interfaces provided by LLVM to +support accurate garbage collection.

+ +
+ + +
+ Goals and non-goals +
+ +
+ +

LLVM's intermediate representation provides garbage +collection intrinsics that offer support for a broad class of +collector models. For instance, the intrinsics permit:

+ + + +

We hope that the primitive support built into the LLVM IR is sufficient to +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 +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.

+ +

The aspects of the binary interface with which LLVM's GC support is +concerned are:

+ + + +

There are additional areas that LLVM does not directly address:

+ + + +

In general, LLVM's support for GC does not include features which can be +adequately addressed with other features of the IR and does not specify a +particular binary interface. On the plus side, this means that you should be +able to integrate LLVM with an existing runtime. On the other hand, it leaves +a lot of work for the developer of a novel language. However, it's easy to get +started quickly and scale up to a more sophisticated implementation as your +compiler matures.

+ +
+ + +
+ Getting started +
+ + +
+ +

Using a GC with LLVM implies many things, for example:

+ + + +

To help with several of these tasks (those indicated with a *), LLVM +includes a highly portable, built-in ShadowStack code generator. It is compiled +into llc and works even with the interpreter and C backends.

+ +
+ + +
+ In your compiler +
+ +
+ +

To turn the shadow stack on for your functions, first call:

+ +
F.setGC("shadow-stack");
+ +

for each function your compiler emits. Since the shadow stack is built into +LLVM, you do not need to load a plugin.

+ +

Your compiler must also use @llvm.gcroot as documented. +Don't forget to create a root for each intermediate value that is generated +when evaluating an expression. In h(f(), g()), the result of +f() could easily be collected if evaluating g() triggers a +collection.

+ +

There's no need to use @llvm.gcread and @llvm.gcwrite over +plain load and store for now. You will need them when +switching to a more advanced GC.

+ +
+ + +
+ In your runtime +
+ +
+ +

The shadow stack doesn't imply a memory allocation algorithm. A semispace +collector or building atop malloc are great places to start, and can +be implemented with very little code.

+ +

When it comes time to collect, however, your runtime needs to traverse the +stack roots, and for this it needs to integrate with the shadow stack. Luckily, +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
+///        compiled as constant data into the executable for each function.
+/// 
+/// Storage of metadata values is elided if the %metadata parameter to
+/// @llvm.gcroot is null.
+struct FrameMap {
+  int32_t NumRoots;    //< Number of roots in stack frame.
+  int32_t NumMeta;     //< Number of metadata entries. May be < NumRoots.
+  const void *Meta[0]; //< Metadata for each root.
+};
+
+/// @brief A link in the dynamic shadow stack. One of these is embedded in the
+///        stack frame of each function on the call stack.
+struct StackEntry {
+  StackEntry *Next;    //< Link to next stack entry (the caller's).
+  const FrameMap *Map; //< Pointer to constant FrameMap.
+  void *Roots[0];      //< Stack roots (in-place array).
+};
+
+/// @brief The head of the singly-linked list of StackEntries. Functions push
+///        and pop onto this in their prologue and epilogue.
+/// 
+/// Since there is only a global list, this technique is not threadsafe.
+StackEntry *llvm_gc_root_chain;
+
+/// @brief Calls Visitor(root, meta) for each GC root on the stack.
+///        root and meta are exactly the values passed to
+///        @llvm.gcroot.
+/// 
+/// Visitor could be a function to recursively mark live objects. Or it
+/// might copy them to another heap or generation.
+/// 
+/// @param Visitor A function to invoke for every GC root on the stack.
+void visitGCRoots(void (*Visitor)(void **Root, const void *Meta)) {
+  for (StackEntry *R = llvm_gc_root_chain; R; R = R->Next) {
+    unsigned i = 0;
+    
+    // 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]);
+    
+    // For roots [NumMeta, NumRoots), the metadata pointer is null.
+    for (unsigned e = R->Map->NumRoots; i != e; ++i)
+      Visitor(&R->Roots[i], NULL);
+  }
+}
+ + +
+ About the shadow stack +
+ +
+ +

Unlike many GC algorithms which rely on a cooperative code generator to +compile stack maps, this algorithm carefully maintains a linked list of stack +roots [Henderson2002]. This so-called "shadow stack" +mirrors the machine stack. Maintaining this data structure is slower than using +a stack map compiled into the executable as constant data, but has a significant +portability advantage because it requires no special support from the target +code generator, and does not require tricky platform-specific code to crawl +the machine stack.

+ +

The tradeoff for this simplicity and portability is:

+ + + +

Still, it's an easy way to get started. After your compiler and runtime are +up and running, writing a plugin will allow you to take +advantage of more advanced GC features of LLVM +in order to improve performance.

+ +
+ + +
+ IR features +
+ + +
+ +

This section describes the garbage collection facilities provided by the +LLVM intermediate representation. The exact behavior +of these IR features is specified by the binary interface implemented by a +code generation plugin, not by this document.

+ +

These facilities are limited to those strictly necessary; they are not +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.

+ +
+ + +
+ Specifying GC code generation: gc "..." +
+ +
+ define ty @name(...) gc "name" { ... +
+ +
+ +

The gc function attribute is used to specify the desired GC style +to the compiler. Its programmatic equivalent is the setGC method of +Function.

+ +

Setting gc "name" on a function triggers a search for a +matching code generation plugin "name"; it is that plugin which defines +the exact nature of the code generated to support GC. If none is found, the +compiler will raise an error.

+ +

Specifying the GC style on a per-function basis allows LLVM to link together +programs that use different garbage collection algorithms (or none at all).

+ +
+ + +
+ Identifying GC roots on the stack: llvm.gcroot +
+ +
+ void @llvm.gcroot(i8** %ptrloc, i8* %metadata) +
+ +
+ +

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 compiler plugin.

+ +

A compiler which uses mem2reg to raise imperative code using alloca +into SSA form need only add a call to @llvm.gcroot for those variables +which a pointers into the GC heap.

+ +

It is also important to mark intermediate values with llvm.gcroot. +For example, consider h(f(), g()). Beware leaking the result of +f() in the case that g() triggers a collection.

+ +

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.

+ +

The %metadata argument can be used to avoid requiring heap objects +to have 'isa' pointers or tag bits. [Appel89, Goldberg91, Tolmach94] If +specified, its value will be tracked along with the location of the pointer in +the stack frame.

+ +

Consider the following fragment of Java code:

+ +
+       {
+         Object X;   // A null-initialized reference to an object
+         ...
+       }
+
+ +

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:
+   ;; Java null-initializes pointers.
+   store %Object* null, %Object** %X
+
+   ...
+
+   ;; As the pointer goes out of scope, store a null value into
+   ;; it, to indicate that the value is no longer live.
+   store %Object* null, %Object** %X
+   ...
+
+ +
+ + +
+ Reading and writing references in the heap +
+ +
+ +

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

LLVM does not enforce this relationship between the object and derived +pointer (although a plugin might). However, it would be +an unusual collector that violated it.

+ +

The use of these intrinsics is naturally optional if the target GC does +require the corresponding barrier. Such a GC plugin will replace the intrinsic +calls with the corresponding load or store instruction if they +are used.

+ +
+ + +
+ 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). The exact code generated is specified +by a compiler plugin.

+ +

Many important algorithms require write barriers, including generational +and concurrent collectors. Additionally, write barriers could be used to +implement reference counting.

+ +
+ + +
+ Read barrier: llvm.gcread +
+ +
+i8* @llvm.gcread(i8* %object, i8** %derived)
+
+ +
+ +

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 +a compiler plugin.

+ +

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.

+ +
+ + +
+ Implementing a collector plugin +
+ + +
+ +

User code specifies which GC code generation to use with the gc +function attribute or, equivalently, with the setGC method of +Function.

+ +

To implement a GC plugin, it is necessary to subclass +llvm::GCStrategy, 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 +compile LLVM's computed stack map to assembly code (using the binary +representation expected by the runtime library). This can be accomplished in +about 100 lines of code.

+ +

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 +conforms to the binary interface defined by library, most essentially the +stack map.

+ +

To subclass llvm::GCStrategy and register it with the compiler:

+ +
// lib/MyGC/MyGC.cpp - Example LLVM GC plugin
+
+#include "llvm/CodeGen/GCStrategy.h"
+#include "llvm/CodeGen/GCMetadata.h"
+#include "llvm/Support/Compiler.h"
+
+using namespace llvm;
+
+namespace {
+  class VISIBILITY_HIDDEN MyGC : public GCStrategy {
+  public:
+    MyGC() {}
+  };
+  
+  GCRegistry::Add<MyGC>
+  X("mygc", "My bespoke garbage collector.");
+}
+ +

This boilerplate collector does nothing. More specifically:

+ + + +

Using the LLVM makefiles (like the sample +project), this code can be compiled as 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 +
+ +
+ +

GCStrategy provides a range of features through which a plugin +may do useful work. Some of these are callbacks, some are algorithms that can +be enabled, disabled, or customized. This matrix summarizes the supported (and +planned) features and correlates them with the collection techniques which +typically require them.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
AlgorithmDoneshadow stackrefcountmark-sweepcopyingincrementalthreadedconcurrent
stack map✔✘✘✘✘✘
initialize roots✔✘✘✘✘✘✘✘
derived pointersNO✘*✘*
custom lowering✔
gcroot✔✘✘
gcwrite✔✘✘✘
gcread✔✘
safe points
in calls✔✘✘✘✘✘
before calls✔✘✘
for loopsNO✘✘
before escape✔✘✘
emit code at safe pointsNO✘✘
output
assembly✔✘✘✘✘✘
JITNO✘✘✘✘✘
objNO✘✘✘✘✘
live analysisNO✘✘✘✘✘
register mapNO✘✘✘✘✘
+
* 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 roots.
+
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.

+ +
+ + +
+ Computing stack maps +
+ +
+ +

LLVM automatically computes a stack map. One of the most important features +of a GCStrategy is to compile this information into the executable in +the binary representation expected by the runtime library.

+ +

The stack map consists of the location and identity of each GC root in the +each function in the module. For each root:

+ + + +

Also, for the function as a whole:

+ + + +

To access the stack map, use GCFunctionMetadata::roots_begin() and +-end() from the GCMetadataPrinter:

+ +
for (iterator I = begin(), E = end(); I != E; ++I) {
+  GCFunctionInfo *FI = *I;
+  unsigned FrameSize = FI->getFrameSize();
+  size_t RootCount = FI->roots_size();
+
+  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;
+  }
+}
+ +

If the llvm.gcroot intrinsic is eliminated before code generation by +a custom lowering pass, LLVM will compute an empty stack map. This may be useful +for collector plugins which implement reference counting or a shadow stack.

+ +
+ + + +
+ Initializing roots to null: InitRoots +
+ +
+ +
MyGC::MyGC() {
+  InitRoots = true;
+}
+ +

When set, LLVM will automatically initialize each root to null upon +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.

+ +

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.

+ +
+ + + +
+ Custom lowering of intrinsics: CustomRoots, + CustomReadBarriers, and CustomWriteBarriers +
+ +
+ +

For GCs which use barriers or unusual treatment of stack roots, these +flags allow the collector to perform arbitrary transformations of the LLVM +IR:

+ +
class MyGC : public GCStrategy {
+public:
+  MyGC() {
+    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 calls +performCustomLowering.

+ +

LLVM's default action for each intrinsic is as follows:

+ + + +

If CustomReadBarriers or CustomWriteBarriers are specified, +then performCustomLowering must eliminate the +corresponding barriers.

+ +

performCustomLowering must comply with the same restrictions as FunctionPass::runOnFunction. +Likewise, initializeCustomLowering has the same semantics as Pass::doInitialization(Module&).

+ +

The following can be used as a template:

+ +
#include "llvm/Module.h"
+#include "llvm/IntrinsicInst.h"
+
+bool MyGC::initializeCustomLowering(Module &M) {
+  return false;
+}
+
+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 (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;
+}
+ +
+ + + +
+ Generating safe points: NeededSafePoints +
+ +
+ +

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:

+ +
MyGC::MyGC() {
+  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) {
+  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;
+  }
+}
+
+ +

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

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 +the LLVM stack map into assembly code. (At the beginning, this information is not +yet computed.)

+ +

Since AsmWriter and CodeGen are separate components of LLVM, a separate +abstract base class and registry is provided for printing assembly code, the +GCMetadaPrinter and GCMetadataPrinterRegistry. The AsmWriter +will look for such a subclass if the GCStrategy sets +UsesMetadata:

+ +
MyGC::MyGC() {
+  UsesMetadata = true;
+}
+ +

This separation allows JIT-only clients to be smaller.

+ +

Note that LLVM does not currently have analogous APIs to support code +generation in the JIT, nor using the object writers.

+ +
// 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.");
+}
+ +

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 +GCFunctionInfo 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 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 entry 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");
+      }
+    }
+  }
+}
+
+ +
+ + + +
+ 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.

+ +
+ + + + +
+
+ Valid CSS + Valid HTML 4.01 + + Chris Lattner
+ LLVM Compiler Infrastructure
+ Last modified: $Date$ +
+ + + -- cgit v1.2.3