LLVM 垃圾回收¶

摘要 ¶

本文档介绍了如何将 LLVM 集成到支持垃圾回收的语言的编译器中。请注意，LLVM 本身不提供垃圾回收器。 您必须提供自己的垃圾回收器。

快速入门 ¶

首先，您应该选择一种收集器策略。LLVM 包含许多内置策略，但您也可以使用自定义定义来实现可加载插件。请注意，收集器策略是对 LLVM 应如何生成代码以使其与您的收集器和运行时交互的描述，而不是对收集器本身的描述。

接下来，将您生成的函数标记为使用您选择的收集器策略。从 c++ 中，您可以调用

F.setGC(<collector description name>);

这将生成如下 IR 片段

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

在为您的函数生成 LLVM IR 时，您需要

使用 @llvm.gcread 和/或 @llvm.gcwrite 代替标准加载和存储指令。这些内联函数用于表示加载和存储屏障。如果您的收集器不需要此类屏障，您可以跳过此步骤。
使用您的垃圾回收器的运行时库提供的内存分配例程。
如果您的收集器需要类型映射，请根据您的运行时的二进制接口生成类型映射。LLVM 不参与此过程。特别是，LLVM 类型系统不适合通过编译器传递此类信息。
插入与您的收集器交互所需的任何协调代码。许多收集器需要运行应用程序代码以定期检查标志并有条件地调用运行时函数。这通常被称为安全点轮询。

您需要识别在您生成的 IR 中的根（即，您的收集器需要了解的堆对象的引用），以便 LLVM 可以将它们编码到您的最终堆栈映射中。根据选择的收集器策略，这可以通过使用 @llvm.gcroot 内联函数或 gc.statepoint 重定位序列来完成。

不要忘记为评估表达式时生成的每个中间值创建根。在 h(f(), g()) 中，如果评估 g() 触发垃圾回收，则 f() 的结果很容易被回收。

最后，您需要将您的运行时库与生成的程序可执行文件（对于静态编译器）链接，或者确保运行时链接器可以使用相应的符号（对于 JIT 编译器）。

简介 ¶

什么是垃圾回收？¶

垃圾回收是一种广泛使用的技术，它可以使程序员不必了解堆对象的生命周期，从而使软件更易于生产和维护。许多编程语言依赖垃圾回收来实现自动内存管理。垃圾回收主要有两种形式：保守式和精确式。

保守式垃圾回收通常不需要来自语言或编译器的任何特殊支持：它可以处理非类型安全的编程语言（例如 C/C++），并且不需要来自编译器的任何特殊信息。Boehm 收集器是先进的保守式收集器的一个例子。

精确式垃圾回收需要能够在运行时识别程序中的所有指针（这在大多数情况下要求源语言是类型安全的）。在运行时识别指针需要编译器支持来定位所有在运行时保存活动指针变量的位置，包括处理器堆栈和寄存器。

保守式垃圾回收很有吸引力，因为它不需要任何特殊的编译器支持，但它确实存在问题。特别是，由于保守式垃圾回收器无法知道机器中的特定字是指针，因此它无法在堆中移动活动对象（从而阻止了压缩和分代 GC 算法的使用），并且由于恰好指向程序中对象的整数值，它有时会遭受内存泄漏。此外，一些激进的编译器转换可能会破坏保守式垃圾回收器（尽管这种情况在实践中似乎很少见）。

精确式垃圾回收器不会遭受任何这些问题，但它们可能会降低程序的标量优化。特别是，由于运行时必须能够识别和更新程序中所有活动的指针，因此某些优化效果较差。然而，在实践中，使用激进的垃圾回收技术的局部性和性能优势胜过任何低级损失。

本文档描述了 LLVM 提供的机制和接口，以支持精确式垃圾回收。

目标和非目标 ¶

LLVM 的中间表示提供了垃圾回收内联函数，为广泛的收集器模型提供支持。例如，这些内联函数允许

半空间收集器
标记-清除收集器
分代收集器
增量收集器
并发收集器
协作收集器
引用计数

我们希望内置于 LLVM IR 中的支持足以支持广泛的垃圾回收语言，包括 Scheme、ML、Java、C#、Perl、Python、Lua、Ruby、其他脚本语言等等。

请注意，LLVM 本身不提供垃圾回收器——这应该是您的语言运行时库的一部分。LLVM 提供了一个框架，用于向编译器描述垃圾回收器的要求。特别是，LLVM 提供对在调用站点生成堆栈映射、轮询安全点以及发出加载和存储屏障的支持。您还可以扩展 LLVM - 可能通过可加载的代码生成插件 - 以生成符合运行时库指定的二进制接口的代码和数据结构。这类似于 LLVM 和 DWARF 调试信息之间的关系，例如。主要区别在于垃圾回收领域缺乏既定标准——因此需要灵活的扩展机制。

LLVM 的 GC 支持关注的二进制接口方面是

在允许安全执行垃圾回收的代码中创建 GC 安全点。
堆栈映射的计算。对于代码中的每个安全点，必须识别堆栈帧内的对象引用，以便收集器可以遍历并可能更新它们。
将对象引用存储到堆时的写屏障。这些通常用于优化分代收集器中的增量扫描。
加载对象引用时发出读屏障。这些对于与并发收集器互操作很有用。

LLVM 没有直接解决的其他领域是

向运行时注册全局根。
向运行时注册堆栈映射条目。
程序用于分配内存、触发垃圾回收等的函数。
类型映射的计算或编译，或将它们注册到运行时。这些用于爬取堆以查找对象引用。

总的来说，LLVM 对 GC 的支持不包括可以使用 IR 的其他特性充分解决的功能，并且不指定特定的二进制接口。从好的方面来说，这意味着您应该能够将 LLVM 与现有的运行时集成。另一方面，它可能会给新语言的开发人员留下大量工作。我们尝试通过提供可以与许多常见收集器设计和简易扩展点配合使用的内置收集器策略描述来缓解这种情况。如果您还没有需要支持的特定二进制接口，我们建议尝试使用这些内置收集器策略之一。

LLVM IR 特性 ¶

本节介绍 LLVM 中间表示提供的垃圾回收工具。这些 IR 特性的确切行为由选定的GC 策略描述指定。

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

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

gc 函数属性用于向编译器指定所需的 GC 策略。其编程等效项是 Function 的 setGC 方法。

在函数上设置 gc "name" 会触发搜索匹配的 GCStrategy 子类。一些收集器策略是内置的。您可以使用可加载插件机制或通过修补您的 LLVM 副本来添加其他策略。正是选定的 GC 策略定义了为支持 GC 而生成的代码的确切性质。如果找不到，编译器将引发错误。

在每个函数的基础上指定 GC 样式允许 LLVM 将使用不同垃圾回收算法（或根本不使用）的程序链接在一起。

识别堆栈上的 GC 根 ¶

LLVM 目前支持两种不同的机制来描述安全点处编译代码中的引用。llvm.gcroot 是较旧的机制；gc.statepoint 是最近添加的。目前，您可以选择任一实现（在每个GC 策略的基础上）。从长远来看，我们可能会完全放弃 llvm.gcroot，或者基本上合并它们的实现。请注意，大多数新的开发工作都集中在 gc.statepoint 上。

使用 `gc.statepoint`¶

此页面包含 gc.statepoint 的详细文档。

使用 `llvm.gcwrite`¶

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

llvm.gcroot 内联函数用于通知 LLVM 堆栈变量引用堆上的对象，并且将被跟踪以进行垃圾回收。生成的代码的确切影响由函数的选定GC 策略指定。所有对 llvm.gcroot 的调用必须位于第一个基本块内。

第一个参数必须是引用 alloca 指令或 alloca 的位转换的值。第二个参数包含指向应与指针关联的元数据的指针，并且必须是常量或全局值地址。如果您的目标收集器使用标签，请使用空指针作为元数据。

执行手动 SSA 构建的编译器必须确保表示 GC 引用的 SSA 值在每次调用站点之前存储到传递给相应 gcroot 的 alloca 中，并在每次调用后重新加载。使用 mem2reg 将使用 alloca 的命令式代码提升为 SSA 形式的编译器只需要为那些指向 GC 堆的指针的变量添加对 @llvm.gcroot 的调用。

使用 llvm.gcroot 标记中间值也很重要。例如，考虑 h(f(), g())。当 g() 触发垃圾回收时，请注意泄漏 f() 的结果。请注意，堆栈变量必须在函数的序言中初始化并使用 llvm.gcroot 标记。

%metadata 参数可用于避免要求堆对象具有 ‘isa’ 指针或标签位。[Appel89, Goldberg91, Tolmach94] 如果指定，其值将与堆栈帧中指针的位置一起跟踪。

考虑以下 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（需要垃圾回收的程序）从堆对象的字段读取指针或将指针写入堆对象的字段时得到通知。在这些点插入的代码片段分别称为读屏障和写屏障。需要执行的代码量通常很小，并且不在任何计算的关键路径上，因此屏障的总体性能影响是可以容忍的。

屏障通常需要访问对象指针而不是派生指针（它是指向对象内字段的指针）。因此，这些内联函数将两个指针作为单独的参数，以保持完整性。在此代码片段中，%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 不强制执行对象指针和派生指针之间的这种关系（尽管特定的收集器策略可能会强制执行）。但是，违反它的收集器将是不寻常的。

如果目标 GC 不需要相应的屏障，则自然可以选择不使用这些内联函数。如果使用了屏障内联函数，则使用此类收集器的 GC 策略应将内联函数调用替换为相应的 load 或 store 指令。

当前设计的一个已知缺陷是屏障内联函数不包括执行的底层操作的大小或对齐方式。目前假定操作是指针大小，并且对齐方式假定为目标机器的默认对齐方式。

写屏障：`llvm.gcwrite`¶

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

对于写屏障，LLVM 提供了 llvm.gcwrite 内联函数。它与对派生指针（第三个参数）的非易失性 store 具有完全相同的语义。生成的代码的确切代码由函数的选定GC 策略指定。

许多重要算法都需要写屏障，包括分代和并发收集器。此外，写屏障可用于实现引用计数。

读屏障：`llvm.gcread`¶

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

对于读屏障，LLVM 提供了 llvm.gcread 内联函数。它与从派生指针（第二个参数）的非易失性 load 具有完全相同的语义。生成的代码的确切代码由函数的选定GC 策略指定。

与写屏障相比，需要读屏障的算法更少，并且可能具有更大的性能影响，因为指针读取比写入更频繁。

内置 GC 策略 ¶

LLVM 包括对多种垃圾回收器的内置支持。

影子堆栈 GC ¶

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

F.setGC("shadow-stack");

与许多依赖协作代码生成器来编译堆栈映射的 GC 算法不同，此算法仔细维护堆栈根的链表 [Henderson2002]。这种所谓的“影子堆栈”镜像了机器堆栈。维护此数据结构比使用编译到可执行文件作为常量数据的堆栈映射要慢，但具有显着的移植性优势，因为它不需要目标代码生成器的任何特殊支持，也不需要棘手的平台特定代码来爬取机器堆栈。

这种简单性和可移植性的权衡是

每个函数调用的开销很高。
非线程安全。

尽管如此，这仍然是入门的简单方法。在您的编译器和运行时启动并运行后，编写一个插件将使您能够利用 LLVM 的更高级的 GC 功能来提高性能。

影子堆栈并不意味着内存分配算法。半空间收集器或构建在 malloc 之上是很好的起点，并且可以用很少的代码实现。

然而，当需要回收时，您的运行时需要遍历堆栈根，为此，它需要与影子堆栈集成。幸运的是，这样做非常简单。（此代码已进行了大量注释，以帮助您理解数据结构，但只有 20 行有意义的代码。）

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

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

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

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

“Erlang” 和 “Ocaml” GC ¶

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

顾名思义，生成的二进制格式旨在模拟 Erlang 和 OCaml 编译器使用的格式。

Statepoint 示例 GC ¶

F.setGC("statepoint-example");

此 GC 提供了一个示例，说明如何使用 gc.statepoint 提供的基础设施。此示例 GC 与简化 gc.statepoint 序列插入的 PlaceSafepoints 和 RewriteStatepointsForGC 实用程序 pass 兼容。如果您需要围绕 gc.statepoints 机制构建自定义 GC 策略，建议您以此策略为起点。

此 GC 策略不支持读或写屏障。因此，这些内联函数被降低为普通的加载和存储。

此 GC 策略生成的堆栈映射格式可以在堆栈映射节中找到，格式记录在此处。此格式旨在成为 LLVM 未来支持的标准格式。

CoreCLR GC ¶

F.setGC("coreclr");

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

对此 GC 策略的支持正在进行中。此策略在某些方面与 statepoint-example GC 策略不同，例如

内部指针的基指针未显式跟踪和报告。
堆栈映射的编码使用不同的格式。
仅在循环返回边和尾调用之前才需要安全点轮询（函数入口处不需要）。

自定义 GC 策略 ¶

如果上述内置 GC 策略描述都不能满足您的需求，您将需要定义自定义 GCStrategy，并且可能需要自定义 LLVM pass 来执行降低。您定义自定义 GCStrategy 的最佳起点示例是查看内置策略之一。

您可以将此附加代码构造为可加载插件库。如果您只需要启用内置功能的不同组合，则可加载插件就足够了，但是如果您需要提供自定义降低 pass，则需要构建 LLVM 的修补版本。如果您认为需要修补版本，请在 llvm-dev 上寻求建议。可能有一种简单的方法可以扩展支持以使其适用于您的用例，而无需自定义构建。

收集器要求 ¶

您应该能够利用任何现有的收集器库，其中包括以下元素

一个内存分配器，它公开您的编译代码可以调用的分配函数。
堆栈映射的二进制格式。堆栈映射描述了安全点处引用的位置，并被精确收集器用于识别机器堆栈上堆栈帧内的引用。请注意，保守扫描堆栈的收集器不需要这样的结构。
一个堆栈爬取器，用于发现调用堆栈上的函数，并枚举每个调用站点的堆栈映射中列出的引用。
一种用于识别全局位置（例如，全局变量）中的引用的机制。
如果您的收集器需要加载和存储屏障，则需要您的收集器的加载和存储屏障的 LLVM IR 实现。请注意，由于许多收集器根本不需要屏障，因此 LLVM 默认将此类屏障降低为普通加载和存储，除非您另行安排。

实现收集器插件 ¶

用户代码使用 gc 函数属性或等效地使用 Function 的 setGC 方法来指定要使用的 GC 代码生成。

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

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

要子类化 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 调用会被替换为相应的 load 指令。
llvm.gcwrite 调用会被替换为相应的 store 指令。
没有安全点被添加到代码中。
堆栈映射不会被编译到可执行文件中。

使用 LLVM makefile，这段代码可以使用简单的 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 提供了一系列功能，插件可以通过这些功能执行有用的工作。其中一些是回调，一些是可以启用、禁用或自定义的算法。此矩阵总结了受支持（和计划中）的功能，并将它们与通常需要它们的收集技术相关联。

算法	完成	影子堆栈	引用计数	标记-清除	复制	增量	线程化	并发
堆栈映射	✔			✘	✘	✘	✘	✘
初始化根	✔	✘	✘	✘	✘	✘	✘	✘
派生指针	否						否*	否*
自定义降低	✔
gcroot	✔	✘	✘
gcwrite	✔		✘			✘		✘
gcread	✔							✘
安全点
在调用中	✔			✘	✘	✘	✘	✘
在调用之前	✔						✘	✘
用于循环	否						否	否
在逃逸之前	✔						✘	✘
在安全点发出代码	否						否	否
输出
汇编	✔			✘	✘	✘	✘	✘
JIT	否			?	?	?	?	?
obj	否			?	?	?	?	?
活动分析	否			?	?	?	?	?
寄存器映射	否			?	?	?	?	?
* 派生指针仅对复制收集构成风险。
? 表示一个功能，如果可用，则可以使用。

为了清楚起见，上述收集技术的定义如下

影子堆栈: mutator 仔细维护堆栈根的链表。
引用计数: mutator 维护每个对象的引用计数，并在对象的计数降至零时释放该对象。
标记-清除: 当堆耗尽时，收集器从根开始标记可达对象，然后在清除阶段取消分配不可达对象。
复制: 随着可达性分析的进行，收集器将对象从一个堆区域复制到另一个堆区域，在此过程中压缩它们。复制收集器可以实现高效的“bump pointer”分配，并可以提高引用的局部性。
增量: （包括分代收集器。）增量收集器通常具有复制收集器的所有属性（无论成熟堆是否正在压缩），但带来了需要写入屏障的额外复杂性。
线程化: 表示多线程 mutator；收集器仍然必须在开始可达性分析之前停止 mutator（“停止世界”）。停止多线程 mutator 是一个复杂的问题。它通常需要在运行时使用高度平台特定的代码，并在安全点生成精心设计的机器代码。
并发: 在这种技术中，mutator 和收集器并发运行，目标是消除暂停时间。在协作式收集器中，如果发生暂停，mutator 还会进一步协助收集，从而使收集能够利用多处理器主机。“停止世界”的线程收集器问题通常仍然在有限程度上存在。精密的标记算法是必要的。读取屏障可能是必要的。

正如矩阵所示，LLVM 的垃圾回收基础设施已经适用于各种各样的收集器，但目前尚未扩展到多线程程序。这将在未来根据需求添加。

计算堆栈映射 ¶

LLVM 自动计算堆栈映射。 GCStrategy 最重要的功能之一是将此信息编译到运行时库期望的二进制表示的可执行文件中。

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

RootNum：根的索引。
StackOffset：对象相对于帧指针的偏移量。
RootMetadata：作为 %metadata 参数传递给 @llvm.gcroot intrinsic 的值。

此外，对于整个函数

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

如果 llvm.gcroot intrinsic 在代码生成之前被自定义降低 pass 消除，LLVM 将计算一个空的堆栈映射。这对于实现引用计数或影子堆栈的收集器插件可能很有用。

将根初始化为 null ¶

建议前端显式初始化根，以避免可能混淆优化器。这可以防止 GC 访问未初始化的指针，这几乎肯定会导致其崩溃。

作为后备方案，LLVM 将在进入函数时自动将每个根初始化为 null。代码生成中对此模式的支持在很大程度上是一个遗留细节，旨在保持旧的收集器实现正常工作。

intrinsics 的自定义降低 ¶

对于使用屏障或对堆栈根进行不寻常处理的 GC，实现者有责任提供自定义 pass 以使用所需的语义来降低 intrinsics。如果您选择加入特定 intrinsic 的自定义降低，则您的 pass 必须消除选择加入您的 GC 的函数中所有相应的 intrinsic 实例。这种 pass 的最佳示例是 ShadowStackGC 及其 ShadowStackGCLowering pass。

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

生成安全点 ¶

LLVM 提供对将堆栈映射与调用的返回地址关联的支持。给定收集器设计所需的任何循环或返回安全点都可以通过调用运行时例程或潜在的可修补调用序列来建模。使用 gcroot，所有调用指令都被推断为可能的安全点，因此将具有关联的堆栈映射。

发出汇编代码：`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.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

文档

参与其中

附加链接

本页