垃圾收集与LLVM¶

摘要 ¶

本文介绍了如何为LLVM集成一个编译器，构建支持垃圾收集的语言。 请注意，LLVM本身不提供垃圾收集器 ，您必须自行提供。

快速开始 ¶

首先，你应该选择一个垃圾收集策略。 LLVM包括许多内置的，但你也可以实现一个自定义的可加载插件。注意，垃圾收集器的策略是在描述LLVM应该如何生成代码，使得生成的代码与垃圾收集器和运行时正确交互，并不是垃圾收集器本身的描述。

接下来，用你选择的收集策略标记您生成的函数。从C++代码中，您可以调用：

F.setGC(<collector description name>);

这将产生像下面的中间代码片段：

define void @foo() gc "<collector description name>" { ... }

当为你的函数生成LLVM IR时，你将需要：

使用 @ llvm.gcread 和/或 @ llvm.gcwrite 代替标准的加载和存储指令。这些内部函数用于表示加载和存储的barriers。如果你收集器不需要这样的barriers，你可以跳过这一步。
使用您的垃圾收集器的运行时库提供的内存分配程序
如果您的垃圾收集器需要它们，可以根据您的运行时的二进制接口生成类型映射。 LLVM不参与这个过程。特别是，LLVM类型系统不适合通过编译器传送这些信息。
插入与垃圾收集器交互所需的任何协调代码。许多收集器需要运行某些代码来定期检查flags并有条件地调用运行时功能。这通常被称为safepoint轮询。（译者注：safepoint的概念是进行垃圾收集动作时，可以安全执行的位置，通常是函数开始前后，所有寄存器中的指针都被保存到栈中时，这时对栈中适当位置扫描，即可获取所有引用的入口点。）

您将需要在生成的IR中确定根（例如：引用堆对象的收集器需要知道），让LLVM可以把他们编码进你最终的栈映射表。根据选择的收集器策略，这是可以通过使用 @ llvm.gcroot 内部函数或 gc.statepoint 重定位序列来实现。

不要忘记为计算表达式时生成的每个中间值创建一个根。在 h(f(), g()) 表达式中，如果 g() 触发了一个收集动作，那么 f() 的结果也应该可以很容易地被收集。

最后，你需要你的运行时库与生成的可执行程序（对于静态编译）链接或保证对应的符号可以在运行时被链接（对于JIT编译器）。

导言 ¶

什么是垃圾收集？¶

垃圾收集是一种广泛应用的技术，允许开发者不必关心堆对象的生存期，使得软件更容易构建和维护。许多编程语言依赖垃圾回收的自动内存管理特性。垃圾收集器有以下两种主要形式：保守的和准确的。

保守垃圾收集往往不需要从任一语言或编译的任何特殊的支持：它可以处理非类型安全的编程语言（例如C / C++），并且不需要从编译器获取任何特殊的信息。这款 Boehm collector 是一个最先进的保守收集器的例子。

准确垃圾收集需要在运行时（这需要源语言是类型安全在大多数情况下），以确定在程序中的所有指针的能力。在运行时确定的指针，需要编译器的支持，以找到在运行时保持住指针变量的所有地方，包括：processor stack and registers。

保守的垃圾收集是有吸引力的，因为它不需要任何特殊的编译器的支持，但它确实有问题。特别是，由于保守的垃圾收集器不能*知道*，在机器一个特定的word可能是一个指针，它不能在堆中移动活动对象（导致不能使用压缩和世代GC算法），它可能偶尔发生内存泄漏，因为某些整数值可能恰好等于某个指针地址。此外，一些激进的编译器转换可能打破保守的垃圾收集器（虽然这些似乎在实践中罕见）。（译者注：保守的垃圾收集器将栈中所有可能的值都当做假想的指针，如果某个不是指针的数字被当做指针，那么将会导致某些可以被回收的元素一直不被回收，如果恰好是某个比较大的树结构的根，则会有大量内存泄露。不过这种收集器之所以实用，就是因为发生特殊情况的概率非常小。）

准确的垃圾收集器不会受到这些问题的困扰，但他们可能会在标量优化时受到影响。特别是，由于在运行时必须能够识别和更新所有在程序中的活指针，一些优化会变得不太有效。然而在实践中，采用积极的垃圾收集技术的局部性和性能优势要胜过任何底层优化的损失。

本文档描述了由LLVM提供支持和维护的准确垃圾收集器的机制和接口。

目标和非目标 ¶

LLVM的中间表示为 garbage collection intrinsics 等很多收集器模型提供支持。例如，这些内置的收集器模型被支持：

半空间垃圾收集器
标记 - 清除垃圾收集器
世代垃圾收集
增量式垃圾收集器
并发垃圾收集器
合作式垃圾收集器
参考计数

我们希望在LLVM IR上建立对垃圾收集的支持，使其能够支持一大类需要垃圾回收的语言，包括 Scheme，ML，Java，C#，Perl，Python，Lua，Ruby，其他脚本语言等。

需要注意的是LLVM 本身不提供垃圾回收 — 这应该是你的语言的运行时库的一部分。 LLVM提供了描述垃圾收集要求编译器的框架。特别是，LLVM提供用于产生调用堆栈的结构表，轮询safepoint，并发读写屏障（barriers）的支持。您还可以扩展LLVM - 可以通过一个可加载的 code generation plugins - 生成一套符合 二进制接口 和 运行时库 的指定代码和数据结构。这类似于，如LLVM和DWARF调试信息之间的关系。所不同的，主要在于缺乏垃圾收集的领域标准—因此需要一个灵活的扩展机制。

与LLVM的GC支持有关的二进制接口有：

在可以安全执行收集代码的位置创建GC safepoints
堆栈映射表的计算。为代码中的每个安全点，堆栈帧中的对象的引用必须确定，使得收集器可以遍历和或许更新它们。
存储堆对象引用的时候发出Write barriers。这些都是世代收集，增量扫描常用的操作。
加载对象引用的时候发出Read barriers。这些对并发收集器交互操作非常有用。

还有其他方面的LLVM不能直接解决：

运行时全局根的注册。
运行时栈映射表的注册。
分配内存时使用的函数，触发垃圾收集等。
类型映射表的计算或编译，或在运行时注册该表。这些都是在堆中爬取对象引用所必要的信息。（译者注：类型表对于GC非常重要，因为在堆中，所有内存都是一片连续的数据，你必须能够知道其中哪些是指针，哪些不是，所以必须有所有类型的元数据）

一般情况下，LLVM对GC支持不包括可充分解决与IR的其他功能，并且不指定一个特定的二进制接口功能。从有利的一面，这意味着你应该能够LLVM与现有的运行时集成。另一方面，它为新语言的开发者留下了很多工作。我们试图通过提供内置的收集策略的描述，可以与许多常见设计的收集器易于扩展整合，以减轻这部分工作量。如果你还没有，你需要支持特定的二进制接口，我们建议您尝试使用这些内置在收集策略之一。

LLVM IR特性 ¶

本节介绍所提供的垃圾收集设施 LLVM intermediate representation。选定的这些IR的确切行为可以参考这里： GC strategy description。

指定GC代码的生成: `gc "..."`¶

define <returntype> @name(...) gc "name" { ... }

该 gc 功能属性用于指定所需的GC策略编译器。其方案相当于是 Function 的 setGC 方法。

在一个函数上设置 gc "name" 会触发搜索来尝试匹配GCStrategy的子类。一些收集器的策略是内置的。您可以添加其他的策略或者使用可加载插件机制，或者直接编写Patching修改LLVM。是被选的GC策略定义了支持GC的代码的确切性质。如果没有找到，编译器会产生一个错误。

指定的GC，在每个函数的基础上，允许LLVM使用不同的垃圾收集算法（或没有）

在栈上识别GC根 ¶

LLVM目前支持在safepoints描述编译代码引用两种不同的机制。 llvm.gcroot 是旧的机制; gc.statepoint 已经成为最新特性。目前，您可以选择执行（以 GC strategy 为基础）。从长期来看，我们可能要么远离 llvm.gcroot 实现完全迁移或实质上合并它们的实现。请注意，大多数新的开发工作主要集中在 gc.statepoint 。

使用 `gc.statepoint`¶

This page 包含了 gc.statepoint 详细文档。

使用 `llvm.gcwrite`¶

void @llvm.gcroot(i8** %ptrloc, i8* %metadata)

该 llvm.gcroot 内部命令用来告诉LLVM一个堆栈变量引用了堆中的某个对象，这个引用应该被垃圾收集器所追踪。生成的代码的确切影响由所选择的函数指定 GC strategy 。所有调用 llvm.gcroot 的语句必须驻留在本函数的第一个基本块内。（译者注：一般编写代码时的临时变量都会在栈上开辟一块内存空间，指针也不例外， llvm.gcroot 正是指明了这样一种关系，某个栈上的临时变量引用了某个堆上的对象，这样垃圾回收器就可以追踪当前所有被引用的对象，正是从一系列的gcroot开始。必须驻留在第一个基本块中，也是出于安全的考虑，很可能某些操作会导致这个内存加载到寄存器中，没有及时更新回内存，导致垃圾回收器监测了错误的内存地址。）

第一个参数必须是一个地址，指向指令alloca分配的地址或者alloca的一个bitcast转换。第二包含一个指向应与该指针相关联的元数据，**必须**是常量或全局值地址。如果你的目标收集器使用标签，用一个空指针作为元数据。

手动执行静态单赋值（SSA）构建的编译器必须确保代表GC引用的被存储在alloca分配的地址的SSA值，在每次调用点之前能传递给相应的 gcroot 并在每次调用后重新加载。采用mem2reg提高代码性能的编译器，只需要对于那些指向GC堆的指针变量添加一个 @llvm.gcroot 调用。

同样重要的是，标记带有 llvm.gcroot 的中间变量。例如，考虑 h(f(), g()) 。在 g() 触发一个收集动作时，必须小心 f() 的返回值发生泄露。请注意，堆栈变量必须在函数的开头部分被初始化并用 llvm.gcroot` 标记。（译者注：这个内存泄露的例子是说，如果嵌套函数调用，返回值会存储到了两个临时变量中，必须小心地标记这些用到的中间变量，假设f()返回了一个对象，存储在临时变量a1中，并没有用gcroot标记，那么g()函数内触发了一次垃圾回收，就会因为a1没有被标记为gcroot，对应的内存被标记为没有引用，就可能会被这次垃圾回收给回收掉，造成g()调用结束后，f()的返回值已经不可用了。这样不可用的内存地址传入h函数时必然会发生异常。）

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.

考虑如下的Java代码片段：

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

这个块（可能位于一个函数的中间或循环嵌套）可以被编译成这个LLVM代码：

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** %tmp, 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
   ...

在堆中读取和写入引用 ¶

当mutator（需要垃圾收集的程序）从堆对象的字段读取指针或写入指针时，需要通知某些收集器。插入这些点的代码片段分别被称为*读屏障*和*写屏障*。需要执行的代码量通常很小，且不在任何计算的关键路径上，因此屏障的整体性能影响是可以接受的。

屏障（Barriers）常常需要访问*对象指针*而非*衍生指针*（这是一个指针字段对象内）。因此，这些内在需要两个指针作为独立完整的参数。在这个片段中，%object 是对象指针，%derived 是派生的指针：

;; 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不强制制定对象和派生的指针之间的这种关系（虽然具体为 collector strategy ）。然而，很少有垃圾收集器违反它。

使用这些内在的是自然可选如果目标的GC不需要相应屏障。如果使用他们这样的收集器所使用的GC策略应更换相应的 load 或 store 指令的内部调用。

当前设计的一个已知缺陷是屏障内在函数不包括所执行的基础操作的大小或对齐。目前假定操作是指针大小，并且地址对齐被认为是目标机器的默认对齐。

写屏障： `llvm.gcwrite`¶

void @llvm.gcwrite(i8* %value, i8* %object, i8** %derived)

对于写障碍，LLVM提供了 llvm.gcwrite 固有功能。它具有完全相同的语义非易失性 store 到派生的指针（第三个参数）。参考：GC strategy 产生的确切的代码是由函数的选择指定。

许多重要的算法需要编写屏障，包括分代和并发收集器。另外，可以使用写屏障来实现引用计数。

读障碍： `llvm.gcread`¶

i8* @llvm.gcread(i8* %object, i8** %derived)

对于读障碍，LLVM提供了 llvm.gcread 固有功能。它具有同样的语义从派生的指针（第二个参数）的非易失性``load``。 GC strategy 产生的确切的代码是由函数的选择指定。

读相对写来说，较少需要障碍，但仍然可能更大程度地影响性能，因为指针读取比写更频繁。

建于GC策略 ¶

LLVM包含对几种垃圾收集器的内置支持。

影子堆栈GC（Shadow Stack GC）¶

要使用此收集器策略，请使用以下标签标记您的函数：

F.setGC("shadow-stack");

不同于依靠合作代码生成器来编译堆栈映射表的很多GC算法，该算法谨慎地保持着堆根链表 [Henderson2002]。这种所谓的 “shadow stack” 是机器堆栈的一个镜像。保持这种数据结构比使用编译成可执行固定数据堆栈映射慢，但有一个显著可移植性的优点，因为它不需要目标代码生成器的特殊支持，并且不需要棘手的特定平台代码，来抓取本机堆栈。

这种简洁性和便携性的代价是：

每次函数调用的开销很高。
不是线程安全的。

不过，这是一个简单的入门方法。编译器和运行库启动并运行后，编写一个 plugin 可以让您利用LLVM的更高级GC功能<collector-algos>来提高性能。

该影子堆栈算法，并不需要编写内存分配算法。一个半空间收集器或构建在 ``malloc` 上的分配器就是一个很好的入手点，可以用很少的代码来实现。

但是，当需要收集时，您的运行时需要遍历堆栈根，因此需要与影子堆栈集成。幸运的是，这样做很简单。（这段代码被大量的评论来帮助你理解数据结构，但是只有20行有意义的代码。）

/// @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);
  }
}

The ‘Erlang’ and ‘Ocaml’ GCs ¶

LLVM附带两个利用 gcroot 机制的示例收集器。据我们所知，这些实际上并没有被任何语言运行时使用，但是它们为有兴趣编写 gcroot 兼容GC的插件的人提供了一个合理的起点。特别是，这些是树型示例中唯一如何使用gcroot策略生成自定义二进制堆栈映射格式的示例。

因为顾名思义，所产生的二进制格式是为了模拟Erlang和OCaml编译器分别使用的格式。

Statepoint示例GC ¶

F.setGC("statepoint-example");

这个GC提供了一个例子，说明如何使用gc.statepoint提供的基础结构。这个示例GC兼容 PlaceSafepoints 和 RewriteStatepointsForGC 实用Pass，可以简化gc.statepoint序列的插入。如果你需要在 gc.statepoints 机制周围建立一个自定义GC策略，建议你使用这个策略作为起点。

此GC策略不支持读取或写入屏障。结果，这些内部函数被降级为正常的加载和存储。

这个GC策略生成的堆栈映射格式可以在以下文件的 Stack Map Section 中找到 ref:here <statepoint-stackmap-format> 。这种格式旨在成为LLVM向前发展的标准格式。

CoreCLR GC ¶

F.setGC("coreclr");

这个GC利用gc.statepoint机制来支持 CoreCLR 运行时。

这个GC策略的支持是一项正在进行的工作。这个策略与 statepoint-example GC 在某些方面有所不同，如：

内部指针的基本指针没有明确的跟踪和报告。
编码堆栈映射使用不同的格式。
安全点轮询仅在回送边缘之前和尾部呼叫之前需要（在函数入口处不需要）。

自定义GC策略 ¶

如果内置的GC策略描述中没有一个满足您的需求，则需要定义一个自定义GCStrategy，并可能需要定制LLVM通道来执行降低操作。从哪里开始定义定制的GCStrategy最好的例子就是看看内置的策略之一。

您可以将这些附加代码构建为可加载的插件库。如果您只需要启用内置功能的不同组合，则可加载插件就足够了，但是如果您需要提供自定义降级通道，则需要构建LLVM的修补版本。如果您认为您需要修补版本，请咨询llvm-dev的建议。可能有一个简单的方法，我们可以扩展支持，使其为您的用例工作，而无需自定义生成。

垃圾收集器要求 ¶

您应该能够使用用包含以下元素的任何现有的垃圾收集器库：

一个内存分配器，它提供了编译后的代码可以调用的分配函数。
堆栈映射的二进制格式。堆栈映射在一个safepoint描述引用的位置，在精确的收集器中用于标识机器堆栈上的堆栈帧内的引用。请注意，保守扫描堆栈的收集器不需要这样的结构。
一个堆栈搜寻器发现调用堆栈上的函数，并枚举堆栈映射中列出的每个调用点的引用。
用于识别全局位置（例如全局变量）中的引用的机制。
如果您的收集器需要它们，您的收集器的LLVM IR实施会加载和存储屏障。请注意，由于许多垃圾收集器完全不需要任何屏障，LLVM默认将这些障碍降至正常的装载和存储，除非您另有安排。

实现一个收集器插件 ¶

用户代码指定哪个GC代码生成与 gc 函数属性一起使用，或者等同于 Function 的 setGC 方法。

要实现一个GC插件，需要继承 llvm :: GCStrategy ，这可以通过几行样板代码完成。 LLVM的基础架构提供了对几个重要算法的访问。对于一个没有争议的收集器，剩下的可能是编译LLVM的计算堆栈映射到汇编代码（使用运行时库期望的二进制表示）。这可以在大约100行代码中完成。

这不是实现垃圾收集堆或垃圾收集器本身的适当位置。该代码应该存在于该语言的运行时库中。编译器插件负责生成符合库定义的二进制接口的代码，最基本的是 stack map。

要继承“`llvm :: GCStrategy”并将其注册到编译器：

// 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 LLVM_LIBRARY_VISIBILITY MyGC : public GCStrategy {
  public:
    MyGC() {}
  };

  GCRegistry::Add<MyGC>
  X("mygc", "My bespoke garbage collector.");
}

这个示例收集器什么都不做。进一步来说：

llvm.gcread calls are replaced with the corresponding load instruction.
llvm.gcwrite calls are replaced with the corresponding store instruction.
没有安全点（safepoint）被添加到代码。
堆栈映射不会编译到可执行文件中。

使用LLVM makefiles，可以使用简单的makefile将此代码编译为插件：

# lib/MyGC/Makefile

LEVEL := ../..
LIBRARYNAME = MyGC
LOADABLE_MODULE = 1

include $(LEVEL)/Makefile.common

一旦插件被编译，使用它的代码可以使用 llc -load = MyGC.so 来编译（尽管MyGC.so可能有一些其他特定于平台的扩展）：

$ cat sample.ll
define void @f() gc "mygc" {
entry:
  ret void
}
$ llvm-as < sample.ll | llc -load=MyGC.so

还可以将收集器插件静态链接到工具，如特定于语言的编译器前端。

可用特性概述 ¶

``GCStrategy``提供了一系列功能，通过它，插件可以做有用的工作。其中一些是回调，一些是可以启用，禁用或定制的算法。下表总结了已经支持（和计划支持）的功能，并将它们与通常需要它们的垃圾收集技术相关联。

Algorithm	Done	Shadow stack	refcount	mark- sweep	copying	incremental	threaded	concurrent
stack map	✔			✘	✘	✘	✘	✘
initialize roots	✔	✘	✘	✘	✘	✘	✘	✘
derived pointers	NO						N*	N*
custom lowering	✔
gcroot	✔	✘	✘
gcwrite	✔		✘			✘		✘
gcread	✔							✘
safe points
in calls	✔			✘	✘	✘	✘	✘
before calls	✔						✘	✘
for loops	NO						N	N
before escape	✔						✘	✘
emit code at safe points	NO						N	N
output
assembly	✔			✘	✘	✘	✘	✘
JIT	NO			?	?	?	?	?
obj	NO			?	?	?	?	?
live analysis	NO			?	?	?	?	?
register map	NO			?	?	?	?	?
* Derived pointers only pose a hasard to copying collections.
？表示可用时，有价值的功能。

需要明确的是，上面的收集技术被定义为：

影子堆栈（Shadow Stack）: 增变器仔细维护了一个堆栈根的链表。
引用计数: 增变器维护每个对象的引用计数，并在计数降到零时释放对象。
标记-清扫算法: 当堆空间用尽时，收集器将从根开始标记可到达的对象，然后在扫描阶段释放不可达对象。
拷贝式垃圾收集: 随着可达性分析的进行，收集器将对象从一个堆区域复制到另一个堆区域，并将它们压缩在过程中。复制收集器可实现高效的“凹凸指针”分配，并可改善参考的局部性。
增量回收: （包括世代收集器）增量收集器通常具有复制收集器的所有属性（不管堆是否压缩），但是增加了需要编写屏障的复杂性。
Threaded: 表示多线程的增变器;在开始可达性分析之前，收集器必须仍然停止增变器（“停止整个世界”）。停止多线程增变是一个复杂的问题。它通常要求运行时具有高度特定于平台的代码，并在安全的地方生产精心设计的机器代码。
concurrent=50: 在这种技术中，增变器和收集器同时运行，其目标是消除暂停时间。在一个合作收集器中，增变器进一步援助收集应暂停发生，允许收集利用多处理器主机。Threaded收集器的“停止世界”问题通常仍然存在有限的程度。复杂的标记算法是必要的。阅读屏障可能是必要的。

如矩阵所示，LLVM的垃圾收集基础结构已经适用于各种各样的收集器，但目前不扩展到多线程程序。由于这是热门话题，很可能将在未来加入更多种收集器。

计算堆栈映射 ¶

LLVM自动计算堆栈映射。GCStrategy 最重要的特性之一就是将这些信息编译成运行时库期望的二进制表示形式的可执行文件。

堆栈图由模块中每个函数中每个GC根的位置和标识组成。对于每个根：

RootNum: 根的索引。
StackOffset: 对象相对于帧指针的偏移量。
RootMetadata: 作为 ％metadata 参数来传递给 @ llvm.gcroot 内在的值。

另外，对于整个函数：

getFrameSize(): 函数的初始堆栈框架的整体大小，

不考虑任何动态分配。
roots_size(): 函数中根的数量。

要访问堆栈映射，可以使用：GCFunctionMetadata::roots_begin() 和 end() ，参见 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;
  }
}

如果在代码生成之前通过自定义降级Pass去除了 llvm.gcroot 内部函数，LLVM将计算一个空的堆栈映射。这可能对实现引用计数或影子堆栈的收集器插件有用。

将根初始化为null：`InitRoots`¶

MyGC::MyGC() {
  InitRoots = true;
}

设置后，LLVM将在进入该函数时自动将每个根初始化为 null 。这可以防止GC的扫描阶段访问未初始化的指针，这几乎肯定会导致崩溃。这个初始化发生在自定义降低之前，所以两者可以一起使用。

由于LLVM尚未计算活跃度信息，因此无法区分未初始化的堆栈根与已初始化的堆。所以，这个功能应该被所有的GC插件使用。它是默认启用的。

自定义降级内部函数：`CustomRoots`, `CustomReadBarriers`, and `CustomWriteBarriers`¶

对于使用屏障或堆栈根的异常处理的GC，这些标志允许收集器执行LLVM IR的任意转换：

class MyGC : public GCStrategy {
public:
  MyGC() {
    CustomRoots = true;
    CustomReadBarriers = true;
    CustomWriteBarriers = true;
  }
};

如果设置了这些标志中的任何一个，则LLVM会禁止相应内部函数的默认降低。相反，您必须提供一个自定义Pass，以根据需要降低内部函数。如果您已经选择了自定义降低某个特定的内在因素，那么您必须**删除选择加入到GC中的相应内在函数的所有实例。这种传球的最好的例子是ShadowStackGC，它是ShadowStackGCLowering传球。

目前没有办法在没有构建LLVM的定制副本的情况下注册这样的自定义降级Pass。

生成安全点: `NeededSafePoints`¶

LLVM可以计算四种安全点：

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.
  };
}

收集器可以通过设置NeededSafePoints掩码来请求这四者的任意组合：

MyGC::MyGC()  {
  NeededSafePoints = 1 << GC::Loop
                   | 1 << GC::Return
                   | 1 << GC::PreCall
                   | 1 << GC::PostCall;
}

然后它可以使用以下例程来访问安全点。

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;
  }
}

几乎每个收集器要求 PostCall 安全点，因为这些对应于函数在调用子例程期间暂停的时刻。

多线程程序通常需要使用 Loop 安全点来保证应用程序在有限的时间内到达安全点，即使它正在执行一个不包含函数调用的长时间运行的循环。

螺纹收集器也可能需要 Return 和 PreCall 安全点来实现使用自修改代码来“停止世界”的技术，在那里重要的是程序不能在没有达到安全点的情况下退出函数（因为只有最上面的功能已被修复）。

生成汇编代码： `GCMetadataPrinter`¶

LLVM允许插件在模块的汇编代码的其余部分之前和之后打印任意汇编代码。在模块结束时，GC可以将LLVM堆栈映射编译为汇编代码。（起初，这个信息还没有计算出来。）

由于AsmWriter和CodeGen是LLVM的独立组件，因此为打印汇编代码， GCMetadaPrinter 和 GCMetadataPrinterRegistry 提供了独立的抽象基类和注册表。如果 GCStrategy 设置了 UsesMetadata ，AsmWriter将查找这样的子类：

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

这种分离式设计可以让只含有JIT的编译器缩减体积。

请注意，LLVM目前没有类似的API来支持JIT中的代码生成，也没有使用对象写入器。

// lib/MyGC/MyGCPrinter.cpp - Example LLVM GC printer

#include "llvm/CodeGen/GCMetadataPrinter.h"
#include "llvm/Support/Compiler.h"

using namespace llvm;

namespace {
  class LLVM_LIBRARY_VISIBILITY MyGCPrinter : public GCMetadataPrinter {
  public:
    virtual void beginAssembly(AsmPrinter &AP);

    virtual void finishAssembly(AsmPrinter &AP);
  };

  GCMetadataPrinterRegistry::Add<MyGCPrinter>
  X("mygc", "My bespoke garbage collector.");
}

收集器应使用“AsmPrinter”来打印便携式汇编代码。收集器本身包含整个模块的堆栈映射，可以使用自己的 begin() 和 end() 方法访问GCFunctionInfo。这是一个真实的例子：

#include "llvm/CodeGen/AsmPrinter.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/Target/TargetAsmInfo.h"
#include "llvm/Target/TargetMachine.h"

void MyGCPrinter::beginAssembly(AsmPrinter &AP) {
  // Nothing to do.
}

void MyGCPrinter::finishAssembly(AsmPrinter &AP) {
  MCStreamer &OS = AP.OutStreamer;
  unsigned IntPtrSize = AP.TM.getSubtargetImpl()->getDataLayout()->getPointerSize();

  // Put this in the data section.
  OS.SwitchSection(AP.getObjFileLowering().getDataSection());

  // For each function...
  for (iterator FI = begin(), FE = end(); FI != FE; ++FI) {
    GCFunctionInfo &MD = **FI;

    // A compact GC layout. Emit this data structure:
    //
    // struct {
    //   int32_t PointCount;
    //   void *SafePointAddress[PointCount];
    //   int32_t StackFrameSize; // in words
    //   int32_t StackArity;
    //   int32_t LiveCount;
    //   int32_t LiveOffsets[LiveCount];
    // } __gcmap_<FUNCTIONNAME>;

    // Align to address width.
    AP.EmitAlignment(IntPtrSize == 4 ? 2 : 3);

    // Emit PointCount.
    OS.AddComment("safe point count");
    AP.EmitInt32(MD.size());

    // And each safe point...
    for (GCFunctionInfo::iterator PI = MD.begin(),
                                  PE = MD.end(); PI != PE; ++PI) {
      // Emit the address of the safe point.
      OS.AddComment("safe point address");
      MCSymbol *Label = PI->Label;
      AP.EmitLabelPlusOffset(Label/*Hi*/, 0/*Offset*/, 4/*Size*/);
    }

    // Stack information never change in safe points! Only print info from the
    // first call-site.
    GCFunctionInfo::iterator PI = MD.begin();

    // Emit the stack frame size.
    OS.AddComment("stack frame size (in words)");
    AP.EmitInt32(MD.getFrameSize() / IntPtrSize);

    // Emit stack arity, i.e. the number of stacked arguments.
    unsigned RegisteredArgs = IntPtrSize == 4 ? 5 : 6;
    unsigned StackArity = MD.getFunction().arg_size() > RegisteredArgs ?
                          MD.getFunction().arg_size() - RegisteredArgs : 0;
    OS.AddComment("stack arity");
    AP.EmitInt32(StackArity);

    // Emit the number of live roots in the function.
    OS.AddComment("live root count");
    AP.EmitInt32(MD.live_size(PI));

    // And for each live root...
    for (GCFunctionInfo::live_iterator LI = MD.live_begin(PI),
                                       LE = MD.live_end(PI);
                                       LI != LE; ++LI) {
      // Emit live root's offset within the stack frame.
      OS.AddComment("stack index (offset / wordsize)");
      AP.EmitInt32(LI->StackOffset);
    }
  }
}

参考文献 ¶

[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