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

读取和写入堆中的引用 ¶

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

屏障通常需要访问对象指针而不是派生指针（它是对象内字段的指针）。因此，为了完整起见，这些内联函数将这两个指针作为单独的参数。在此代码段中，%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 编译器分别使用的格式。

状态点示例 GC ¶

F.setGC("statepoint-example");

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

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

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

CoreCLR GC ¶

F.setGC("coreclr");

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

对该 GC 策略的支持正在开发中。此策略在某些方面将不同于状态点示例 GC 策略，例如

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

自定义 GC 策略 ¶

如果上面内置的 GC 策略描述都不满足您的需求，则需要定义一个自定义的 GCStrategy，并可能需要一个自定义的 LLVM 传递来执行降低操作。定义自定义 GCStrategy 的最佳示例是查看其中一个内置策略。

您可以将此附加代码构建为可加载的插件库。如果只需要启用内置功能的不同组合，则可加载的插件就足够了，但如果需要提供自定义降低传递，则需要构建 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 通过一系列功能提供了一系列功能，插件可以通过这些功能执行有用的工作。其中一些是回调，一些是可以启用、禁用或自定义的算法。此矩阵总结了支持的（和计划的）功能，并将它们与通常需要它们的收集技术相关联。

算法	已完成	影子栈	引用计数	标记-清除	复制	增量	线程	并发
栈图	✔			✘	✘	✘	✘	✘
初始化根	✔	✘	✘	✘	✘	✘	✘	✘
派生指针	否						N*	N*
自定义降低	✔
gcroot	✔	✘	✘
gcwrite	✔		✘			✘		✘
gcread	✔							✘
安全点
在调用中	✔			✘	✘	✘	✘	✘
调用前	✔						✘	✘
对于循环	否						N	N
转义前	✔						✘	✘
在安全点发出代码	否						N	N
输出
组件	✔			✘	✘	✘	✘	✘
JIT	否			?	?	?	?	?
obj	否			?	?	?	?	?
活跃分析	否			?	?	?	?	?
寄存器映射	否			?	?	?	?	?
* 派生指针只会对复制收集造成危害。
? 表示如果可用可以利用的功能。

需要明确的是，上面定义的收集技术如下

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

如矩阵所示，LLVM 的垃圾回收基础设施已经适用于各种收集器，但目前尚未扩展到多线程程序。未来会根据兴趣添加此功能。

计算栈图 ¶

LLVM 自动计算栈图。GCStrategy 的最重要功能之一是将这些信息编译到可执行文件中，以运行时库期望的二进制表示形式。

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

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

此外，对于整个函数

getFrameSize()：函数初始栈帧的总大小，
不考虑任何动态分配。
roots_size()：函数中根的数量。

要访问栈图，请使用 GCMetadataPrinter 中的 GCFunctionMetadata::roots_begin() 和 -end()

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 本质，则 LLVM 将计算一个空的栈图。这对于实现引用计数或影子栈的收集器插件可能很有用。

将根初始化为 null ¶

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

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

自定义降低内在函数 ¶

对于使用屏障或对栈根进行特殊处理的 GC，实现者负责提供自定义传递以降低具有所需语义的内在函数。如果您已选择自定义降低特定内在函数，则您的传递**必须**消除在选择加入您的 GC 的函数中所有相应内在函数的实例。此类传递的最佳示例是 ShadowStackGC 及其 ShadowStackGCLowering 传递。

目前没有办法在不构建 LLVM 的自定义副本的情况下注册此类自定义降低传递。

生成安全点 ¶

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] 运行时标签并非必要。Andrew W. Appel。Lisp 和符号计算 19(7):703-705，1989 年 7 月。

[Goldberg91] 强类型编程语言的无标签垃圾回收。Benjamin Goldberg。ACM SIGPLAN PLDI’91。

[Tolmach94] 使用显式类型参数的无标签垃圾回收。Andrew Tolmach。1994 年 ACM Lisp 和函数式编程会议论文集。

[Henderson2002] 非合作环境中的精确垃圾回收

文档

参与贡献

其他链接

此页面